CPU Scheduling Algorithm

CPU Scheduling Algorithm

• Priority-based scheduling
  
  • 우선순위를 사용하는 알고리즘의 유형
  • FCFS scheduling
    • First Come First Serve, = FIFO
    • 프로세스가 도착한 순서대로 실행한다.
  • SJF scheduling
    • Shortest Job First
    • non-preemptive, preemptive(SRTF)
• RR scheduling
  • Round Robin
  • 우선순위라는 개념이 없다.
  • 모든 프로세스가 공평하게 CPU 시간을 나눠서 사용한다.
  • weighted round robin scheduling
• multilevel queue
  • priority based와 round robin 등 여러 스케줄링을 혼합해서 사용한다.

 

---

Priority-based Scheduling

Priority number(우선순위)를 사용하는 알고리즘의 유형을 지칭한다.

 

FCFS와 SJF 알고리즘도 priority-based scheduling 알고리즘이다.

FCFS는 도착시간을 priority로 사용하였고, SJF는 burst time을 priority로 사용하였다.

 

Priority number로는 integer를 사용하고, priority number가 작으면 우선순위가 높다고 생각한다.

CPU는 더 높은 우선순위를 가진 프로세스를 실행한다.

 

Starvation

Starvation 문제를 생각해야 한다.

Starvation이란 프로세스가 CPU를 할당받지 못하고 무한정 기다리는 상황을 말한다.

priority를 기다려서 실행할 순서가 되었지만, 또다시 자신보다 높은 priority를 가진 프로세스가 들어온다면 계속 기다려야 한다.

 

Aging

Aging은 starvation을 해결하는 방법이다.

시간이 지남에 따라 프로세스의 우선순위를 높여서 프로세스가 언젠가 실행될 수 있도록 한다.

 

---

First Come First Serve (FCFS) Scheduling

프로세스가 도착한 순서대로 실행한다.

들어온 순서에 따라서 average waiting time의 편차가 너무 크다.

 

예시 1

Burst time은 순수하게 프로세스가 실행해서 완료하는데 까지 걸리는 시간이다. (도중에 프로세스 상태가 바뀌지 않는다고 가정)

Burst time은 P1 = 24, P2 = 3, P3 = 3이 라고 하자.

근소한 차이로 P1 → P2 → P3의 순서로 도착했다고 가정하면 다음과 같은 순서로 실행된다.

 

이 때 각 프로세스의 waiting time은 P1 = 0, P2 = 24, P3 = 27 이 된다.

everage waiting time은 (0 + 24 + 27) / 3 = 17이 된다.

 

예시 2

근소한 차이로 프로세스가 P2 → P3 → P1의 순서로 도착한다고 가정하면, 다음과 같이 실행된다.

이 때 각 프로세스의 waiting time은 P1 = 6, P2 = 0, P3 = 3이 된다.

everage waiting time은 (6 + 0 + 3) / 3 = 3 이 된다.

 

---

Shortest-Job-First(SJF) Scheduling

burst time이 짧은 순서대로 프로세스를 실행한다.

 

두 가지 버전이 있다.

• non-preemptive
  • 현재 실행 중인 프로세스의 상태가 바뀌지 않는 경우에는 scheduling을 하지 않는다.
• preemptive
  • 현재 실행 중인 프로세스의 burst time 보다 새로 들어온 프로세스의 burst time이 짧으면 새로 들어온 프로세스로 전환한다.
  • 이런 방식은 SRTF(Shortest-Remaining-Time-First) scheduling이라 한다.
  • 일반적으로 non-preemptive 보다 더 우수한 average waiting time을 보인다.

 

Optimal but Infeasible

SJF는 average waiting time 측면에서 가장 optimal 한 알고리즘이다.

 

그러나 실제 상황에서는 infeasible 한 알고리즘이다. (embedded system 제외)

실제 상황에서는 프로세스의 burst time은 runtime 정보이기 때문에 직접 실행하기 전까지는 알 수가 없다.

때문에 구현이 불가능하다.

 

Execution Time Prediction

SJF 알고리즘을 적용할 수 있는 경우가 있다.

 

Embedded system에서는 실행 시간이 이미 정해져있기 때문에 SJF 알고리즘을 적용할 수 있다.

또한 일반적인 system에서도 moving average를 통해 실행시간을 예측할 수 있다.

 

 

Non-Preemptive 예시

현재 실행 중인 프로세스의 상태가 변하지 않는 이상 끝까지 처리하는 방식이다.

 

각 프로세스의 도착시간과 burst time이 다음과 같다고 하자.

 

non-preemptive 방식에서는 다음과 같이 실행 된다.

각 프로세스의 waiting time은 P1 = 0, P2 = 6, P3 = 3, P4 = 7 이 된다.

average waiting time = (0 + 6 + 3 + 7) / 4 = 4 가 된다.

 

Preemptive 예시

새로 들어온 프로세스의 burst time과 현재 진행중인 프로세스의 남아있는 burst time을 비교해서 더 짧은 프로세스 먼저 수행한다.

 

위와 같은 상황에서 preemptive scheduling을 한다고 하자.

 

2 시점에서 P1의 남은 burst time은 5가 되는데, 새로 들어온 P2의 burst time은 4 이다.

따라서 P1은 ready 상태로 가고 P2 가 실행된다.

 

마찬가지로 4 시점에서 P2의 남은 burst time은 2가 되는데 P3의 burst time은 1이다.

따라서 P2는 ready 상태로 가고 P3 가 실행된다.

 

각 프로세스의 waiting time은 P1 = 9, P2 = 1, P3 = 0, P4 = 2 가 된다.

average waiting time = (9 + 1 + 0 + 2) / 4 = 3 이다.

 

---

Round Robin(RR) Scheduling

우선순위라는 개념이 없다.

모든 프로세스가 공평하게 CPU 시간을 나눠서 사용한다.

 

스케줄링을 하는 시간, 즉 프로세스가 실행되는 시간을 time quantum이라 한다.

보통 10~100 millisecond 로 지정한다.

 

프로세스가 기다려야 할 시간이 결정되어있기 때문에 starvation 문제가 발생하지 않는다.

만약 프로세스가 ready queue의 n 번째 위치에 존재하고, time quantum이 q라면, 해당 프로세스는 (n-1)q 만큼의 시간을 기다리면 된다.

 

예시

time qantum = 20, 각 프로세스의 burst time은 P1 = 53, P2 = 17, P3 = 68, P4 = 24 라고 하자.

 

37 시점에서 이미 P2는 작업을 완료해서 terminate 되었기 때문에 이후에는 실행되지 않는다.

 

Weighted Round Robin

모든 프로세스가 동일한 시간만큼 동작하는 것이 아니라, 특정 프로세스에게 가중치를 줘서 더 많은 시간 동안 실행될 수 있도록 할 수 있다.

 

---

Multilevel Queue

대부분의 운영체제는 priority-based 와 round robin 등을 혼합해서 사용한다.

 

scheduling queue(ready queue)를 여러개를 두고 각 queue 마다 우선순위를 준다.

각 queue 안에서는 round robin 방식으로 실행을 한다.

따라서 queue level에서는 priority-based 방식으로 동작하고, queue 안에서는 round robin 방식으로 동작한다.

queue 내뷰에서 반드시 특정 알고리즘을 사용해야 하는 것은 아니다.

 

운영체제는 높은 우선순위를 가진 queue 먼저 수행을 한다.

따라서 높은 우선순위를 가진 queue에 프로세스가 들어있다면 아래 queue의 프로세스는 실행되지 않고 기다려야 한다.

 

Multilevel Feedback Queue

Multilevel queue와 유사하지만, 프로세스가 queue 안에서 이동할 수 있는 방식이다.

 

만약 프로세스가 너무 많은 CPU time을 사용한다면 낮은 우선순위의 큐로 이동시킬 수 있다.

이런 방식을 이용해서 aging을 구현한다.

 

예시

모든 프로세스들은 무조건 첫 번째 queue로 들어온다.

그리고 한 라운드가 끝나도 남는 프로세스들은 그 다음의 queue로 이동시킨다.

 

첫 번째 queue가 다 종료되어야 두 번째 queue가 실행이 된다.

만약 첫 번째 queue에 새로운 프로세스가 들어온다면 그 작업이 다 끝나야 두 번째 queue의 프로세스들이 실행이 된다.

 

두 번째 queue에서 한 라운드를 다 돌았을 때 프로세스가 남는다면, 남은 프로세스들을 세 번째 queue로 이동시킨다.

세 번째 queue에서는 time quantum의 개념이 없기 때문에 프로세스의 종료가 보장된다.