FIFO - 먼저들어오는거 먼저하는것
SJF - 짧은거 먼저하는것
SRTF - 짧은거 먼저하는대 새로운거 들어오면 뺏어서 더 짧은거 먼저하는거
Priority - 우선순위 먼저인거
RR - 짧은 시간동안 계쏙 뱅뱅돌면서 하는 것
MLQ - 우선순위에 따라 큐를 분리한것
MLFQ - 큐를 옮겨탈 수 있는 것
HRN - 짧으면서도 오래 대기한 것을 우선순위줍니다.
최소작업 우선 스케줄링(SJF, Shortest Job First)의 장단점
How do we determine the length of the processing time?
- Could ask the user
- Estimate
4번 입니다.
강제로 빼앗아 사용합니다.
선점이 있는 친구 입니다.
우선순위 스케줄링
"내부적"으로 우선순위 높은 것들
- 다음 cpu버스트 시간이 짧다
- 제한 시간이 있는 것(실시간 작업같은건 제한시간이 있습니다.)
- 기억장소 요청량 적으면
- 사용 파일 수가 적으면
- 평균 CPU 버스트에 대한 평균 "입출력 버스트"의 비율 (=입출력 하는 횟수) 가 높다면(입출력은 cpu를 조금 사용합니다.)
- 전면
비선점 우선 순위 스케줄링 예
처음에 P1밖에 도착안했으니 우선순위 상관없이 실행합니다.
10이라는 시간이 되었을 때 이미 다른 프로세스들은 도착해 있습니다.
P3이 우선순위가 높아서 가장 먼저 실행 합니다.
대기시간 = 실행시간 - 도착시간
선점 우선 순위 스케줄링 예
P3가 들어오면 P3부터 시작합니다.
천채적으로 반환시간과 대기시간이 선점 스케줄링이 더 짧습니다.
그렇다면 선점이 무조건 좋은건가?
선점으로만 하면 스케줄러가 복잡해집니다.
우선순위가 낮은 프로세스는 더욱 더 기아상태가 발생합니다.
우선순위 스케줄링
FIFO도 대기시간이 높은애가 우선순위가 높습니다.
SJF는 cpu버스트시간을 우선순위로 둡니다.
이런것들은 모두 다 기아가 발생할 수 있습니다.
해결하려면 에이징을 해야합니다.
에이징이란?
기다린 시간에 비례하여 우선순위를 높이는 방법
우선순위 스케줄링이 장단점이 있지요?
라운드 로빈 스케줄링
규정 시간량 => cpu사용시간
순환 큐로 쓰면 좋습니다.
그리고 식분할 시스템에 적합합니다.
대화식 사용자에게 적당한 응답시간을 제공할 수 있습니다.
라운드 로빈 스케줄링 예
P3는 왜이렇게 조그만가요?
P3는 실행시간이 6밖에 안되니
앞에서 5하고 1남은 것을 마무리 한것입니다
대기시간은 어떻게 계산될 까요?
(마지막 시간 - 실행 시간 - 도착 시간)
라운드 로빈 할 때 시간 퀀텀을 어떻게 설정할까요?
규정시간량을 작게하면
전체적으로 짧은 프로세스를 먼저 처리 합니다.
반환시간 증가 요인 -> cpu에 들어가 있는 것을 많이 바꾼다!
규정시간량을 크게하면 FIFO가 됩니다.
그게 뭐가 나쁘냐?
호위효과가 나타납니다.
사실 라운드 로빈은 이러한 상황을 해결하려 하는 것 입니다.
규정 시간량을 크게하면
규정시간량을 1로도 해보고.. 2로도 해보고....
그런데 짧게하면 문맥교환 오버해드가 커진다는 것을 고려도 안했는데
규정 시간량을 적절하게 사용하는게 좋습니다.
사진을 보면 길게하는게 좋아보이지만
아닙니다, 컴퓨터의 사정에 따라 다릅니다.
규정시간을 1과 10으로 높고 똑같은 프로세스 3개를 돌립니다.
라운드 로빈 하는 이유
프로세스가 FIFO와 같아지지 않으면서 짧은 job을 먼저 끝내려고 하는 것 입니다.
다단계 큐 스케줄링(MLQ, MultiLevel Queue)
시스템 프로세스는 빨리빨리 처리해야 되서
이 안에서 라운드 로빈을 합니다.
학생 프로세스는 느려도 상관 없으니
FIFO를 해도 됩니다.
우선순위 스케줄링과 다단계 큐 스케줄링의 같은점과 차이점
| 우선순위 | 다단계 큐 | |
| 공통점 | 우선순위 같은거 함 | |
| 차이점 | 각 큐마다 어떤 스케줄링을 할지 결정합니다. | |
우선순위 스케줄링은 시스템 -> 대화식... -> 학생 순으로 꼭 해야했습니다.
다단계 큐는 어떤 큐만 먼저 끝내게 가능합니다.
다단계 피드백 큐 (MLFQ, MultiLevel Feedback Queue) 스케줄링
- 처음에 quantum = 8이라는 시간을 소모하면
- 그 다음 quantum = 16으로 들어가고
- 그 다음 FCFS로 들어갑니다.
내가 짧은 job이면 quantum=8에서 끝냈을 꺼고
길면 FCFS에 가서 끝내면 될 것입니다.
규정시간을 소모하면 우선순위가 떨어집니다.
기본순위가 떨어지면 에이징으로 올릴 수 도 있습니다.
4번입니다.
각 큐 안에서는 기본적으로 라운드 로빈합니다.
기본적으로 먼저들어온게 먼저실행됩니다.(FIFO)
중간에 짧은 시간을 소모하고 나면 내팽겨 집니다. 어디로?
우선순위가 낮은 큐로 옮겨 갑니다.
큐를 옮겨 탈 수 있느냐 없느냐?
오래 기다리면 에이징에 의해 높은 우선순위로 가야하는데 얼마나 기다려야 하는가?
얼마나 소모하면 내려보낼 것인가?
cpu 할당비율은 하나의 큐 쭉할 수도 있도
여러개를 조금씩 할당할 수 도 있습니다.
커집니다.
기본적으로 라운드 로빈으로 돌립니다.
각 큐의 타임슬라이스가 있습니다.
1번 입니다.
여기서 말하는 것은 준비 상태 프로세스들을 이야기 한 것입니다.
자동으로 입출력 => 짧은 것은 위쪽 큐에서 끝납니다.
HRN(Highest Response-ratio Next) 스케줄링
여기서 응답시간이란?
대기시간과 실행한 시간을 합쳐서 무슨일이 일어난 시간이 응답시간 입니다.
응답시간 : 대기한 시간 +서비스를 받을 시간
응답 비율이란 것은 : (대기한 시간 +서비스를 받을 시간) /서비스를 받을 시간
작업한 것분의 응답시간 입니다.
응답 비율이 크다는 것의 의미는?
cpu burst가 같다면 대기시간이 길어지면 길어질 수록 응답비율이 커집니다.
대기시간이 같다면 cpu burst가 짧은게 우선순위가 높습니다.
FIFO에서 짧은 높이 먼저 하게 하고
SJF 에서 오래된 놈도 할 수 있게 합니다.
HRN 예
P4의 응답비율을 계산해 봅시다.
P4의 대기시간은 (10 - 3) = 7입니다.
P4의 실행시간은 4입니다.
(7 + 4) / 4 입니다.
10초 순간에 다음 프로세스를 결정해야 합니다.
P5의 응답비율을 계산해 봅시다.
10초 순간에 도착한 놈의 대기시간을 정해야 합니다.
P5의 대기시간은 (10 - 4) = 6 입니다.
P4의 실행시간은 14입니다.
(6 + 14) / 14 입니다.
10초 순간에 다음 프로세스를 결정해야 합니다.
P2의 응답비율을 계산해 봅시다.
(10초 순간에 도착한 놈의 대기시간을 정해야 합니다.)
P2의 대기시간은 (10 - 1) = 9 입니다.
P2의 실행시간은 28입니다.
(9 + 28) / 28 입니다.
응답 비율이 높은것이 다음 프로세스가 됩니다!!!!!
즉, 10초에 P2,3,4,5중 응답비율이 가장 높았던건 P4 였습니다.
각 프로세스가 끝날 때 마다 프로세스의 대기시간이 달라지게 됩니다.
Priority와 SJF 입니다.
FIFO는 어떻게든 끝내게 됩니다.
- RR(time slice가 짧으니깐)
- MLFQ(FIFO와 RR의 중간점에 있는 것입니다.
- FCFS
'Computer Science > OS' 카테고리의 다른 글
| 메모리 관리 개념, 정책, 메모리의 구조, 프로세스 주소 바인딩, (0) | 2021.11.30 |
|---|---|
| 실제로 os에서 사용되는 스케쥴링, 다중프로세서에서 강결합된 공유 메모리 주소 2가지 비교, 다중 프로세서 스레드 스케줄링 (0) | 2021.11.30 |
| 스케쥴링 큐, 장기,단기,중기 스케줄링/ 선입선처리, 최소작업, 우선순위 스케줄링 (0) | 2021.11.23 |
| 교착 상태 회복, 기아상태,교착상태 정리, 프로세스 스케줄링 (0) | 2021.11.22 |
| 은행가 알고리즘 코드, 시간복잡도, 회복 알고리즘 (0) | 2021.11.16 |
