10. CPU 스케쥴링

CPU Scheduling Algorithms

 

-FCFS ( First-Come, First-Served)

 

-SJF ( Shortest Job First)

 

-Priority

 

-RR (Round-Robin)

 

-Multilevel Queue

-Multilevel Feedback Queue

 

 

1. FCFS ( First-Come, First-Served )

 

: 먼저 온 프로세스를 먼저 서비스해준다. 

 

p1 (Burst time : 24ms ), p2 ( Burst time : 3ms) , p3 ( Burst Ttme : 3ms ) 순으로  들어왔다고 가정해보자.

 

p1은 아무도 안 기다렸으므로 0 p2는 24ms를 기다리고 p3은 27ms를 기다렸으니

 

평균 대기시간은 17ms이다.

 

 

만약 p3, p2, p1 순으로 왔다면

 

AWT는 (0 + 3 + 6 ) / 3 = 3ms이다.  

 

들어온 순서대로 처리한다면 대기시간 면에서 별로 좋지 않음을 알 수 있다.

 

 

이렇듯 FCFS는 비선점이다. 프로세스가 종료되어야 그다음 프로세스가 서비스를 받는 형태이다.

 

 

2. Shortest-Job-First

 

 

먼저 온 순서에 관계없이 가장 짧은 프로세스를 먼저 처리해주는 방식이다.

 

 

대기시간 줄이는 측면에서 언뜻봐서도 SJF는 가장 좋다. 하지만 이는 비현실적이다. 

 

실제로 이 프로세스가 CPU시간을 얼마나 사용할지는 돌려보아야 안다. 미리 프로세스의 걸리는 시간을 알 수가 없기

 

때문에 실제로는 불가능한 방법이다.

 

 

SJF는 선점 or 비선점 둘다 가능하다.

 

ex ) 선점 예

앞에 예제와 달리 선점 방법을 위해 Arrival Time도 추가

 

p1 : 8 -> 7 (p2가 4이기 때문에 p2가 도착 한순간 먼저 처리된다)

 

p2 : 4 -> 3 -> 2

 

p3 : 9

 

p4 : 5 

따라서 p1은 10 -1 초간 기다렸고 p2는 기다리지 않았고 p3는 2에 도착했으니 17 -2로 15초

 

p4는 3초에 와서 5에 서비스를 받았으니 5-3으로 2초이다.

 

 

3. Priority

 

우선순위는 일반적으로 정수 값으로 나타낸다. 숫자가 낮은 게 우선순위가 높은 것이다.

 

 

 

가장 우선순위가 높은 p2부터 진행이 되겠다

 

 

 

그렇다면 Priority를 정하는 방법은?

- 시간이 짧거나, 메모리를 적게 차지하거나, CPU를 적게 사용하거나 등

 

역시 비선점 선점 둘다 가능하다.

 

문제점? : starving(기아) 문제가 발생할 수 있다.

 

외부에서 계속 새로운 프로세스가 들어오고 이때 새로운 프로세스가 우선순위가 높다면 우선순위가 낮은

 

프로세스는 영원히 기다리게 되고 starving 상태가 될 수도 있다.

 

해결책 : aging 방법

 

-레디큐에 오래 머무른 프로세스를 점진적으로 우선순위를 높여주는 방식.

 

 

4. Round Robin

 

빙빙 돌면서 CPU 시간을 할당한다. 시분할 시스템에서 주로 사용된다.

 

이 방식은 당연히 선점 방식이다. 한 프로세스가 끝나지 않아도 시간이 지나면 자동으로 다음 프로세스가 받기 때문

 

p1은 4~ 11까지 7ms + 15~16 1ms 총 8ms를 기다린다.

 

p2는 4ms

 

p3는 7ms + 11~15 4ms 총 11ms를 기다린다.

 

 

TIme slice가 짧다면  문맥 전환( 한 프로세스의 모든 상태를 저장 후 다른 프로세스의 상태를 불러옴)이 잦게 일어나게 돼

고 오버헤드의 부담이 된다.

 

ATT

Average turnaround time = 최종적으로 마치고 나온 시간들의 평균

 

(위에 RR 예제는(32 + 7 + 16) / 3 이 된다.)

 

AWT

Average waiting time = 기다린 시간들의 평균

 

 

 

5. Multilevel queue

 

성격이 다른 프로세스들을 동일한 큐에 넣는 것이 맞는가에서 시작 되게 되는데

 

큐를 하나만 두지 말고 여러 개를 두는 것

 

 

예를 들면 성격이 다른 큐들을 만들고 그 큐에 맞는 프로세스만 들어올 수 있도록 하는 방식이다.

 

 

 

6. MultiLevel FeedBack Queue

 

처음 큐에서 끝이 안 난다면 다음 큐로 넘어가게 되는 방식이다.

 

 

너무 많은 cpu 사용 시 다른 queue로 가거나 위에 그림은 밑으로 가지만 기아 상태 우려 시 위로 이동하게 될 수도 있다.