[ SNU 강의 ] CPU Scheduling | 쉽게 배우는 운영체제 8,9주차

Resource

preemtible resource

양보가 가능한 resource
한 프로세스가 점유한 상태에서 다른 프로세스에게 양보할 수 있는 자원
CPU (양보해야 할 시점이 됐을 때 state를 안전하게 대피시키고 양보
memory

nonpreemtible resource

한 프로세스가 점유하면 사용을 마칠 때까지 다른 프로세스에게 양보할 수 없는 자원
프린터

CPU Burst

스케쥴링을 하려고 해도 기준(단위)가 있어야 한다
이를 정한 것이 CPU Burst

유저 프로그램이 일을 수행하다가 blocking system call을 한다
그러면 io에서 wait를 하게 됨
wait를 하는 동안 waiting 상태에 가있다
원하는 상태가 오게 되면 다시 프로그램을 수행시킴.

이렇게 프로그램의 수행을 보면
io를 기다리는 부분, cpu를 기다리는 부분 등 시간을 나눌 수 있다.
여기서 프로그램의 수행 중, 연속적으로 CPU를 사용하는 단절된 구간을 CPU Burst리고 부른다
그리고 이 cpu burst가 스케쥴링의 단위가 된다.
I/O Burst는 프로그램 수행 중 I/O의 완료를 기다리며 블록되는 구간

CPU Burst의 크기?

cpu burst의 사이즈에 따라 스케쥴링 기법이 달라진다.
따라서 크기가 중요함
CPU Burst의 크기가 큰 것? | CPU intensive한 애들은 크다
CPU Burst의 크기가 작은 것? | 터치스크린을 처리한다든가, I/O 사용이 잦은 애들은 작다

CPU 스케쥴링

어떤 이유에선가 현재 프로세스가 수행되면 안될 때

1. 누구에게 할당할 것인가
2. 할당받은 애가 얼마나 오랫동안 CPU를 점유할 것인가
   를 결정하는 것이 CPU 스케쥴링

언제 일어날까?

• ready -> running
  dispaching.
  dispacher가 돌아서 running 상태로 간다
• running -> ready
  preemtive scheduling
  하드웨어 인터럽트를 통해서만 가능
  하드웨어 인터럽트가 걸리면 OS 스케쥴러가 수행되고 당장 시스템을 빼앗는다
• running -> waiting
  nonpreemtive scheduling
  자기 스스로 CPU를 호출해서 waiting으로 가는 것
• running -> terminate
  nonpreemtive scheduling
• waiting -> ready
  preemtive scheduling의 한 부분
  ready로 가려면 async 이벤트가 발생해야 하기 때문

스케쥴링 기법

FIFO

먼저 온 것을 먼저 처리하기
옛날에 일반적으로 사용했다.
cpu burst 단위로 FIFO를 한다

• job에서는 nonpreemtive 스케쥴링인데 - finished가 경계
• process에서는 preemtive 스케쥴링 - blocked가 경계
  단점 : block이 일어나지 않으면 절대 넘어가지 않는다.
  이를 막으려면 timer을 걸어 맥시멈을 준다

SJF (shorted job first)

최적화를 위해서는 짧은애들을 먼저 처리해야 한다! (waiting time을 줄이기 위해)
그런데..!
이렇게 하면 OS가 테스크의 남은 CPU Burst Size를 예측해야 하는데 이게 불가능.

라운드 로빈 스케쥴링

하지만 FIFO로 스케쥴링을 하되
timeout interrupt가 발생하면
이 job은 cpu burst가 길다고 가정하고
뒤로 넘겨버린 후
다음걸 불러오면 된다
그러나...!?!?
timeout을 얼마로 잡아야 하는지의 문제가 생긴다
Time Slice(Time Quantum)의 문제

CPU burst의 사이즈가 균질하다면 fifo가 좋고,
차이가 심하다면 라운드로빈이 좋다.

Adaptive Scheduling

Workload의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케줄링 기법

• CPU Bound Process : 대부분의 시간을 Cpu 연산.
  cpu utilization과 throughput이 중요하다(주어진 시간 안에 얼마나 많은 cpu bound process들이 수행을 끝냈나)
• I/O Bound Process : 대부분의 시간은 waiting, Cpu 연산은 짧다
  짧은 response time이 중요하다.

그런데 Adaptive Scheduling을 하려면 OS가 뭐가 CPU스케쥴링이고 I/O 스케쥴링인지를 알아야 한다

Priority-based Scheduling

프로세스들에게 선호도를 매기고, 선호도가 높은 프로세스를 먼저 수행하는 스케쥴링 기법

Starvation | 수행할 준비를 마치고 CPU를 할당받기를 기다리는 프로세스가 무기한 연기되는 현상
이런 문제가 발생한다.

Fair Share Scheduling | Bandwith Scheduling | Propotional Share Scheduling

대기 중인 프로세스들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 스케줄링 기법

performance isolation
퍼포먼스를 많이 찾이할 것 같은 app이 들어왔을 때도 Bandwidth Scheduling이 필요하다.
이 스케쥴링이 보편화되어있다.