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 ) 선점 예
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로 가거나 위에 그림은 밑으로 가지만 기아 상태 우려 시 위로 이동하게 될 수도 있다.