운영체제_6

CPU 스케줄링 

1. Preemptive vs Non-preemptive

- 선점 vs 비선점

 

1.1. Preemptive

프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다. 즉, 프로세스가 정상적으로 수행 중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있는 것이다. 

 

1.2. Non-preemptive

preemptive의 반대. 한 프로세스가 한 번 CPU를 점유했다면. I/O(프로세스 상태가 실행->대기로 변경되는 경우) 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.

병원=non-preemptive
응급실=premptive

 

 

2. Scheduling criteria

Scheduling criteria(척도)는 스케줄링의 효율을 분석하는 기준이다.

- CPU utilization(이용률):
CPU가 얼마나 놀지 않고 부지런히 일하는가? 
- Throughput(처리율):
시간 당 몇 개의 작업을 처리하는가?
- Turnaround time(반환시간):
프로세스의 처음 시작(ready queue에 처음에 들어온 시간)부터 모든 작업을 끝내고 종료하는데 걸린 시간이다.
- Waiting time(대기시간):
CPU 서비스를 받기 위해서 ready queue에서의 대기시간이다. ex) 병원에서 의사 만나기 전 대기실에서의 대기 시간
- Response time(응답 시간):
첫 응답이 나올 때까지 걸리는 시간(프로세스 도착시간~CPU 서비스받는 시간) 

 

3. CPU Scheduling Algorithms

- First-Come, First-Served(FCFS)
- Shortest Job First(SJF)
- Priority
- Round-Robin(RR)
- Multilevel Queue
- Multilevel Feedback Queue

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

Gantt Chart

Find Average Waiting Time
A. p1->p2->p3 AWT=(0+24+27)/3=17 msec 
B. p2->p3->p1 AWT=(0+3+6)/3=3 msec 
FCFS 방식인 A는 B보다 AWT가 크다. 

• Convoy Effect (호위 효과)
  CPU 실행시간 많이 필요한 프로세스가 먼저 서비스받으면 나머지들은 오랫동안 기다리는 모습이 시중들이 따라다니는 모습 같아서 호위 효과라고 한다(단점).
• FCFS는 Non-Preemptive Scheduling 

 

3.2. Shortest Job First(SJF)

짧은 작업 먼저 서비스해준다.

대기시간을 줄이는 측면에서는 가장 좋다. 하지만 이 방식은 매우 비현실적이다(Not realistic). 왜냐하면 실제 컴퓨터 환경에서는 프로세스의 CPU 점유 시간을 알려면 실제로 수행하여 측정할 수밖에 없다. 이는 오버헤드가 매우 큰 작업으로 잘 사용하지 않는다(실행시간을 기억해야 하고, 일일이 시간을 계산해야 한다).

SJF는 preemptive와 non-preemptive 둘 다 사용 가능하다. 먼저, 아래의 표를 보자.

기존의 예제와 달리 도착시간(arrival time)이 추가되었다. 첫 번째로 non-preemptive의 간트 차트를 보자. 

가장 먼저 도착한 P1이 수행되는 동안 P2, P3, P4 모두 도착하지만, non-preemptive이므로 이미 수행 중인 프로세스가 끝날 때까지 기다려야 한다.

• Average Waiting Time(AWT) = (0+7+15+9​)/4=7.75 msec=7.75msec

두 번째는 preemptive SJF를 살펴보자.

이번에는 preemptive이므로 프로세스가 도착할 때마다, 어느 프로세스가 가장 짧은 것인지 선택해야 한다. 주목할 점은 P2 프로세스가 도착했을 때, 현재 남은 burst time 중 가장 짧은 프로세스가 P2이므로 P1을 수행하던 것을 멈추고 P2가 수행을 시작한다.

• Average Waiting Time(AWT) = (9+0+15+2​)/4=6.5 msec=6.5msec

Preemptive SJF는 예제에서 살펴보았듯이 현재 남아있는 시간 중 가장 짧은 프로세스를 선택하므로 Shortest-Remaining-Time-First(최소 잔여시간 우선)이라 불리기도 한다.

 

3.3. Priority

우선순위 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘이다. 

우선순위 기준은 무엇일까?
내부 요소: time limit, memory requirement
외부 요소: amount of funds being paid

Priority 스케줄링 역시 preemprive와 non-preemptive 두 방식 모두 사용할 수 있다.

Priority 스케줄링의 문제점은 Starvation(기아)이 있다. 

Starvation은 말 그대로 CPU의 점유를 오랫동안 하지 못하는 현상을 말한다.
Priority 스케줄링 방식에서 우선순위가 매우 낮은 프로세스가 ready queue에서 대기하고 있다고 가정해보자.
이 프로세스는 아무리 오래 기다려도 CPU를 점유하지 못할 가능성이 매우 크다. 실제 컴퓨터 환경에서는 새로운 프로세스가 자주 ready queue에 들어온다. 이러한 프로세스가 모두 우선순위가 높은 상태라면 이미 기다리고 있던 우선순위가 낮은 프로세스는 하염없이 기다리고만 있는 상태로 남아있을 수 있다.

이를 해결하는 방법 중 하나는 aging(나이를 먹음)이 있다.

aging은 순위가 낮아 queue에 오래 머물고 있는 프로세스의 우선순위를 높여준다.
운영체제는 queue를 주기적으로 조사해서 queue에 오래 머물고 있는 프로세스가 있으면 점진적으로 순위를 높여, 다른 프로세스가 queue에 들어와도 순위에 밀리지 않고 CPU를 점유할 수 있도록 한다. 

 

3.4. Round-Robin(RR)

프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간 단위(Time Quantum/Slice)로 CPU를 할당하는 방식이다. 

Round-Robin은 기본적으로 preemptive이다. 한 프로세스가 종료되기 전에 time quantum이 끝나면 다른 프로세스로 CPU를 넘겨주기 때문이다. Round Robin는 Time Quantum에 의존적이다. 

Time Quantum이 무한대가 되면? FCFS와 동일하다. 
Time Quantum이 0으로 수렴하면? Switching이 빈번하게 일어나기 때문에 프로세스들이 동시에 실행되는 것처럼 보인다. 0으로 수렴하면 context switching overhead가 빈번하다. 

 

3.5 Multilevel Queue

 

3.6 Multilevel Feedback Queue