선점형 프로세스 스케줄링 - RR, SRT, MFQ

 

👊 RR(Round Robin)

 

먼저 온 순서대로 처리하는 FIFO 방식을 따르되, "시간할당량"만큼씩만 번갈아가며 처리하는 방식

동일한 시간할당량을 사용하는 시분할 처리 시스템에 효과적이다.

시간할당량 안에 작업을 마치지 않으면 대기 큐의 맨 뒤로 밀린다.

시간할당량이 크면 비선점의 FIFO와 동일하다.

시간할당량이 작으면 인터럽트수, 문맥교환수와 오버헤드(간접부담비용)가 증가한다.

적절한 응답시간을 보장해주는 대화식 사용자에게 효과적이다.

 

RR 평균반환시간 계산하기

작업	서비스시간	도착시간
A	56	0
B	34	3
C	18	5

 

평균실행시간 = (56+34+18) / 3 = 36
A의 대기시간 = (8+10) + (10+8) + 10 + 4 - 0 = 50
B의 대기시간 = 10 + (10+10) + (8+10) + 10 - 3 = 55
C의 대기시간 = (10+10) + (10+10) - 5 = 35
평균대기시간 = (50+55+35) / 3 = 46.7
평균반환시간 = 82.7

 

❗️주의사항 : 만약 프로세스A가 실행상태에 돌입했을 때, 프로세스B의 제출(RAM에 도착, 적재)이 아직 끝나지 않았다면 큐에 등록되지 않는다. 다음을 보자(시간할당량=2초).

작업	실행시간	도착시간
P1	3	0
P2	4	1
P3	2	3

일반적인 경우라면 P2 다음에 P3가 실행되어야 할 것 같지만, P2가 실행에 들어간 시점인 "2초"에 아직 P3가 도착하지 않았으므로 운영체제는 P3를 프로세스로서 인지하고 있지 않다. 따라서 P2 다음에는 P1이 실행되며, P1 다음에 P3이 실행된다.

---

👊 SRT

 

처음에는 프로세스를 FIFO로 실행을 하다가, 중간에 도착하는 다른 프로세스들 중 실행시간이 더 짧은 것이 발견되는 순간 그 프로세스로 넘어가는 방식

더 짧은 것으로 옮겨가는 것은 분명 효율적이지만, 예를 들어 0.01초만 마저 하면 끝나는 프로세스 차례인데, 0.000000001초짜리가 들어와서 CPU할당을 뺏긴다면 불필요한 인터럽트+문맥교환+오버헤드를 유발한다.

따라서 어느 정도 시간할당량은 무시하는 "임계치"를 적용한다.

 

SRT 평균 반환시간 계산

작업	실행시간	도착시간
A	24	0
B	6	1
C	3	2

A가 순서상 먼저 실행되다가 1초 후 B가 도착했는데, 보니까 B가 6초짜리여서 24초짜리인 A를 중단시키고 B를 실행함

B가 실행되다가 1초 후 C가 도착했는데, 보니까 C가 3초짜리여서 6초짜리인 B를 중단시키고 C를 실행함

가장 짧은 C를 모두 끝낸 후, 그 다음으로 가장 짧은 B를 모두 끝낸 후, 남은 A를 마저 끝냄

---

👊 MFQ(Multi-level Feedback Queue, 다단계 피드백 큐)

 

여러 개의 대기 큐를 두어 짧은 작업이나 입출력 위주의 작업을 먼저 실행시켜서 끝내버리도록 하는 방식

각 큐마다 시간할당량이 다르게 존재하며, 낮은 큐일수록 시간할당량이 커진다.

각각의 큐들은 종속적으로 연결되어 있다.

CPU를 시간할당량만큼 사용한 프로세스는 낮은 큐로 이동된다.

맨 마지막 단계의 큐는 RR을 사용하여 모두 처리하여 종료될 때까지 반복된다.