5. 운영체제 CPU 스케줄링

Ch.5 Process Scheduling

CPU 스케줄링 알고리즘, 평가기준

1. Scheduling Criteria

알고리즘을 평가할 때는 수행 시간(burst time)과 CPU 사용량(CPU utilization), 단위 시간 당 끝마친 프로세스의 수(Throughput), 하나의 프로세스가 끝날 때까지 걸리는 시간(Turnaround time), 레디 큐에서 대기한 시간(Wating time), 반응 시간(Response time)을 기준으로 한다.

2. Scheduling Algorithm

선점 : 우선순위에 따라 다른 프로세스가 자원을 강탈 할 수 있음. 응답성은 빠르지만, 오버헤드 많음.

비선점 : 한 프로세스가 시작되면, 끝날 때 까지 그 프로세스만 사용. 응답성 느리지만, 오버헤드 적음.

FCFS (First-Come, First-Served)

SJF (Shortest Job First)

프로세스의 burst time이 짧은 순서에 따라 프로세서에 할당한다. burst time이 짧은 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

SRF (Shortest Remaining Time First)

프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다. 수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

RR (Round Robin)

일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다. 시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

Priority Scheduling

어떤 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다. 다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다. but 우선 순위 낮으면 영원히 실행 되지 않는 기아현상 발생한다.

HRN 

우선순위 = (대기시간 + 서비스시간) / 서비스시간

다단계 큐(MLQ ; Multi Level Queue Scheduling)

• 여러단계의 큐를 만들어(각 큐는 독자적인 스케쥴링을 가지고 있다.) 상위단계에서 하위단계로 우선순위를 지정하여 실행
• 하위단계의 큐를 실행중에도 상위단계의 큐에 작업이 들어올 경우 CPU를 내주는 선점 스케쥴링
  
  

다단계 피드백 큐 스케쥴링(MFQ ; Multilevel Feedback Queue Scheduling)

• 다단계 큐와 비슷하나 모든 작업이 최상위 큐에서 실행되며 각 큐에선 할당시간이 존재한다.
• 하위단계 큐로 내려가면 우선순위는 감소하지만 할당시간이 증가한다.
• 
  

<예제>

다음 프로세스들의 집합을 생각해보자. CPU 버스트 시간 단위는 밀리초이다. 프로세스들은 시간0에 P1, P2, P3, P4, P5 순서로 도착한다고 가정한다.

프로세스	버스트 시간	우선순위
P1	2	2
P2	1	1
P3	8	4
P4	4	2
P5	5	3

a : 

FCFS

P1	P2	P3	P4	P5
2	3	11	15	20

SJF

P2	P1	P4	P5	P3
1	3	7	12	20

비선점 우선순위

P3	P5	P1	P4	P2
8	13	15	19	20

RR(단위2)

P1	P2	P3	P4	P5	P3	P4	P5	P3	P5	P3
2	3	5	7	9	11	13	15	17	18	20

     

b : 각 프로세스에 대한 총처리 시간

	P1	P2	P3	P4	P5	합계
FCFS	2	3	11	15	20	51
SJF	3	1	20	7	12	43
비선점우선순위	15	20	8	19	13	75
RR	2	3	20	13	18	56

c : 각 프로세스에 대한 대기 시간

	P1	P2	P3	P4	P5	합계
FCFS	0	2	3	11	15	31
SJF	1	0	12	3	7	23
비선점우선순위	13	19	0	15	8	55
RR	0	2	12	9	13	36

d : SJF 방식이 최소의 평균 대기시간을 보인다.