[운영체제] CPU 스케줄링 & 선점/비선점 스케줄링 알고리즘

CPU Scheduling이 필요한 이유 ?

멀티프로그래밍을 지원하는 운영체제에서 효율적으로 일을 처리하기 위해서 process 스케줄링이 필요하다. single CPU에서는 오직 하나의 process만이 CPU를 사용할 수 있으며, 다른 process들은 CPU를 사용하기 전까지 대기를 한다.

( 여기서 process 스케줄링은 thread 스케줄링과 같은 의미로도 사용할 수 있다. )

스케줄링에는 두가지 이슈가 있다.

• CPU Burst에 들어온 프로그램이 여러게 있는데, 누구한테 먼저 줄것인가 ?
• CPU를 다 쓰고 I/O를 할때까지 한 process에게 CPU를 계속 줄것인가 아니면 중간에 CPU를 뺏어서 다른 프로세스에게 넘겨줄 것인가 ?

CPU를 중간에 뺏지 않는다면 긴 프로세스 하나때문에 다른 프로세스들이 대기해야하는 문제가 생긴다.

공평하게 자원을 주면서도 너무 오래기다리지 않도록, 즉 효율적으로 결정해야 할 것이다.

Scheduling Algorithms

스케줄링 알고리즘은 크게 두가지로 나눠볼 수 있다. 우선, 강제로 CPU를 뺏지 않는 방법. 다 쓰고 자진 반납할때까지 보장해주는 방법인 Non-preemptive 와 강제로 CPU를 빼앗아서 사용하는 Preemptive 방법이다. 현대의 OS에서는 거의 대부분 Preemptive 방식을 사용한다.

Scheduling Criteria (성능 척도)

System 입장에서의 성능 척도

• CPU utilization (이용률) : CPU가 얼마나 바쁘게 일을 하는가. 즉, CPU가 일하는 상태인 시간의 비율이다.
• Thoroughput (처리량) : 주어진 시간안에 얼마만큼의 job을 처리했는가.

Process 입장에서의 성능 척도

• Turnaround time (처리시간, 소요시간) :process 가 대기를 시작해서부터 종료할때까지 걸리는 시간
• Waiting time (대기시간) : ready queue에서 대기한 시간의 총합
• Response time (응답시간) : ready queue에 들어와서 CPU사용 요청을 하고나서 처음으로 CPU를 얻기까지의 시간

FCFS (First-Come-First-Served)

• 가장 먼저 CPU에게 요청을 건 process가 가장 먼저 CPU를 할당받는다.
• Non-Preemptive 방식

ex) 은행에서 대기표를 뽑아서 먼저 온 사람부터 일처리를 한다.

• Waiting time P1 = 0, P2 = 24, P3 = 27
• Average waiting time : (0+24+27)/3 = 17
  
  

• Average Waiting time : (0+3+6)/3 = 3

따라서 FCFS는 process의 burst time에 따라 성능이 달라질 수 있다.

SJF (Shortest Job First)

• CPU가 점유되지 않은 상태일때, CPU burst 가 가장 작은 process에게 할당되는 알고리즘
• Two Schemes:

1. Nonpreemptive 방식 : 일단 CPU를 잡으면 이번 CPU burst가 완료할 때까지 CPU를 선점당하지 않는다.
   
   

• Average Waiting time : (0+3+9+16)/4 = 7
• 한편, 이 프로세스들을 FCFS 방식으로 스케줄링 했다면 평균 대기 시간은 (0+6+14+21)/4 = 10.25일 것이다.

FCFS 방식으로 스케줄링하는 경우

• SJF는 최적의 방법일 것이다. 그렇지만 실제로 CPU 스케줄링에는 적용할 수 없다. next CPU burst의 길이를 정확하게 알 수 있는 방법이 없기 때문이다.
• CPU 사용 추정 : 과거 CPU 사용 내역을 통해서 예측은 가능하다. → Exponential Average
  
  

다음과 같은 점화식이 성립한다.

여기서 Tn은 nth CPU burst 를 뜻하고, 𝛕는 예측할 CPU next burst시간이다. α 값은 0 ~ 1 사이이다.
점화식을 풀면 다음과 같다.

 

 

즉, 현재와 가까운 최신의 CPU 사용 이력은 가중치를 높게 반영하고, 오래된 CPU 이력은 가중치를 낮게 반영해서 예측한다는 의미이다.

1. Preemptive 방식 : 완료 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 process가 도착하면 CPU를 빼앗는다. 이 방법을 SRTF (Shortest-Remaining-Time-First) 라고도 한다.

0초일때 P1밖에 없는 상태여서 P1이 실행되다가, 1초일때 P1의 남은 busrt time 인 7보다 더 짧은 burst time 4를 가진 P2이 들어와서 CPU를 빼앗아 preemptive하게 실행된다.

Priority Scheduling

Highest priority 를 가진 process에게 CPU를 할당한다. SJF도 Priority Scheduling에 속한다고 볼 수 있다. 각 process에는 integer 로 표현되는 우선순위를 부여한다. 이 우선순위에 따라서 스케줄링이 이루어진다.

• Two Schemes: preemptive 방식과 non-preemptive 방식
• 단점 : Starvation (= indefinit blocking) lower priority 를 가진 process가 영원히 실행되지 않을 가능성이 있다. 특정 프로세스가 지나치게 차별받는 현상
• 해결방법 : Aging 기아현상을 해결하는 방법으로는 Aging이 있다. 시간이 지남에 따라서, priority를 업데이트해주는 방법이다.

Round Robin

Preemptive 방식

• 동작 방식 : 각 process가 할당시간이 지나면 선점당하고 ready queue 가장 뒤에 가서 다시 줄을 서는 방식으로 동작한다. 즉, ready queue는 circular queue처럼 동작한다고 이해할 수 있다.
• 예시

• time quantum : 각 process는 동일한 크기의 할당시간 (=time slice, time quantum) 을 가진다. 이 time quantum 은 10 ~ 100ms 길이를 가진다.
• 특징 :
  - ‘할당시간’을 아주 크게 잡으면 결국 FIFO와 동일한 알고리즘이 될 것이다. 그리고 할당시간을 지나치게 짧게 잡으면 context switch 가 매우 빈번히 발생하여 오버헤드가 커질 것이다.

- n개의 프로세스가 ready queue에 있고 할당 시간이 q time-unit 인 경우, 프로세스는 최대 q time-unit 단위로 CPU 시간의 1/n를 얻는다. 즉, 모든 프로세스가 돌아가면서 자기차례가 오기 때문에 어떤 프로세스도 (n-1)q time-unit 이상 기다리지 않게 된다.

- 일반적으로 SJF보다 average turnaround time이 길지만, Round-Robin의 response time(응답시간)이 SJF보다 더 짧다. → 응답시간이 짧은것이 Round-Robin의 가장 큰 장점이다 !!

- 각각의 process CPU Burst 길이가 긴것과 짧은것이 섞여있을 때 유리하게 작동 (실제로는 대부분 process들의 실행시간이 들쑥날쑥해서 유리함)

 

 

---

사진 출처 : Abraham-Silberschatz, Operating System Concepts 10th, 2018