[OS] CPU Scheduling | preemptive & non-preemptive | 스케줄링 알고리즘 | 스케줄러 알고리즘 평가

스케줄링 개념

앞단원까지 cpu는 hw 자원의 효율적인 사용을 위해 context-switching을 통해 마치 concurrency(동시병렬)한 것처럼 hw 자원들을 사용한다고 배웠다. 이러한 context-switching을 관장하는 것이 CPU scheduling이다. 말 그대로 cpu의 스케쥴을 관리한다.

 

[스케쥴링 전제]

• 일단 스케쥴러의 판단 하에 있으려면, 프로세스들은 모두 메모리에 load가 되어있는 상태이어야 한다.
• multi programming 환경이어야 한다. batch programming은 schedule을 나눈다는 가정 자체가 성립 안되니 당연하다.

[cpu schedular의 역할]

• 스케줄러가 ready queue에서 작업을 선택해서 CPU burst하고 나머지는 I/O하면 효율적으로 사용할 수 있다.
• i/o는 scheduler의 역할이 아니다. 

---

스케줄링 종류

Preemptive 선수치기/선매권

 priority inversion일 때, 선수치기를 할 수 있다. 

♦︎ priority inversion: running 작업보다 중요한 작업이 ready queue에 올라온 상태

• 이 작업 또한 스케줄러가 관리한다.
• 그래서 어떤 process가 만들어지거나 I/O가 끝난 process가 ready queue에 들어오면 누구인지 확인해야 하므로 overhead가 크다.
• overhead라는 위험이 있지만, 하나의 프로세스가 독점하는 상황을 방지할 수 있다. 

[스케줄러가 작동하는 경우]

1. 프로세스가 생성될 때. 우선순위를 확인하기 위해서 스케줄러 작동
2. i/o가 끝나고 ready로 갈 때
3. time interrupt가 발생할 때

non-preemptive

ready queue에 아무리 중요한 작업이 올라와도 자기가 하던 일을 쭉 하는 것

 

[스케줄러가 작동하는 경우]

1. 프로세스가 다 종료되고 끝났을 때
2. 프로세스 i/o 끝나서 blocked ➡️ running

---

스케줄링 알고리즘

총 5가지에 대해서 알아보자

FCFS
RR
SJF
SRT
Priority

 

스케줄링 알고리즘 평가 기준

1. user-oriented
   • user의 request에 대한 average response time.(waiting time)
   • interactive(게임, 브라우저 처럼 요청과 반응이 지속적으로 번갈아 동작 ↔ batch)
   • min(turnaround time)(cpu burst와 i/o가 번갈아가면서 프로세스 끝내는 것, 프로세스의 처음부터 끝까지)
   • 평균 응답 시간의 편차가 최소화되어야 한다.
2. system-oriented
   • 단위 시간 안에 해치우는 작업량(throughout)이 max
   • cpu 뿐만 아니라 device controller 등 hw 자원을 최대한 많이 활용한다. (FCFS는 processor utilization을 잘 못하는 것.)
   • 서버가 켜져있는데 아무더 안쓰면 아까비요 utilization이 안좋다.
3. other-oriented: non-performance
   • Fairness: OS나 user로부터 특별한 가이드가 없는 상태에서 모든 process를 공평하게 대해야 하고, 어떤 프로세스도 starvation을 겪으면 안된다.
   • hw resources의 balance

---

FCFS(First-Come-First-Served) - FIFO, Run-Until-Done

하나의 프로세스가 끝날 때까지 독점하는 것. ➡️ non-preemptive

 

• 하나의 프로세스의 burst time이 끝날 때까지 기다려야 하니까 독점 가능성이 높다. 

♦︎ convoy effect: Low CPU and I/O device utilization

• 해결 방법이 있긴 하다. cpu랑 i/o 중에 io가 먼저 돌아가야함. 그래야 device controller 돌아가는 동안 cpu가 일하니까cpu 먼저 돌아가면 device controller 일 안한다..

결론적으로 burst time이 짧은 것부터 먼저 돌린다. 하지만, process의 burst time은 if-else branch가 포함될 경우, 예측이 불가능하다. 

 

---

Round-Robin

time quantum을 주고 process를 running하다가 수행 시간이 남아도 ready로 되돌린다. 

수행하는 도중에 우선권을 넘겨주고 받는 거니까 Preemptive

위 예시 1에서 P1은 24, P2는 3, P3는 3이라는 시간이 필요한데 P1,P2,P3 모두 3시간씩 부여 ➡️ 4시간씩 부여하는 방식으로 running을 하는 것을 볼 수 있다.

• 짧은 프로세스한테는 좋지만 긴 프로세스는 계속 time slice에 맞춰서 동작을 해야하므로 Response time이 길어진다.
• 근데 time quantum마다 계속 프로세스를 바꿔줘야 하는데 오버헤드가 왜 low지??

---

SJF(Shortest-Job-First)

말 그대로 짧은 프로세스가 있으면 non-preemptive하게 먼저 수행하는 것. 긴 프로세스는 짧은 프로세스가 끝날 때까지 기다려야 하니까 패널티 부여된다. optimal for short processes..

 

[Just 이론, Not 현실..]

• 다음 cpu burst를 돌려보지도 않고 정하기가 힘들다.
• 따라서 Approximation: 프로세스가 과거에 수행했던 시간을 통계로 내서 예측한다.
  •  하지만 if-else를 생각하면 input data에 따라서 프로세스 동작 과정이 달라지기 때문에 예상하기 힘들다.
  • 통계치를 branch마다 다 측정해야 하니까 overhead 크다

---

SRT(Shortest-Remaining-Time)

ready queue와 실행 중인 프로세스의 잔여 시간을 비교해서 더 짧은 것들을 먼저 돌린다. ➡️ preemptive

priority inversion: 역전되어있는 상황. 더 짧은 게 ready queue에 있으면 running 프로세스를 바꾸어 준다.

• 얘도 SJF랑 마찬가지로 짧은 프로세스한테는 optimal하지만 긴 프로세스에게는 Response time도 길고, Fairness하지 않으며 Starvation이 발생할 수 있다.
• cpu burst time을 측정하여 프로세스 상태를 바꿔 주어야 하므로 overhead 크다.