CPU Scheduling
동작할 수 있는 프로세스들 중에 어떤 프로세스가 다음에 동작할 것인가를 결정한다.(context switch)
빈번히 일어나고 빠르고 효율적으로 결정할 수 있어야 한다.
이 화살표마다 스케쥴링을 결정해야 한다.
스케쥴링 알고리즘의 목표
1. 모든 시스템은 no starvation(누군가는 배고프지 않도록), fairness, balance(골고루 바쁘도록)를 지켜야 한다.
2. batch systems(한 번에 하나의 작업 처리)
throughput: 시간 당 얼마나 많은 작업을 처리할 것인가
turnaround time: job이 시작해서 끝날 때까지의 시간을 최소화하면 throughput이 좋아진다.
CPU utilization: 올타임으로 CPU를 바쁘게 만든다.
3. 인터랙티브 시스템
반응 시간이 빠르도록
proportionality: 유저의 기대치를 충족시킨다.
4. Real time 시스템
deadline을 충족: 무인자동차 시스템의 deadline이 지켜지지 않으면 사고가 발생할 수 있다.
예측성: 멀티미디어를 스트리밍하는데 끊기지 않도록 한다.
starvation
- 다른 프로세스가 자원(락, CPU)을 갖고 있기 때문에 프로세스가 진행되는 것을 방해받는 상황
- 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 CPU에서 동작하는 것으로부터 막는 것
- 동기화는 또한 starvation을 야기할 수 있다. 한 스레드가 항상 다른 스레드를 이길 수 있다.(락을 잡는다)
Non-preemptive scheduling
- 스케쥴러가 작동하고 있는 job을 기다리며 자발적으로 CPU를 양보한다.
- job은 상호협력해야 한다
Preemptive scheduling
- 스케쥴러는 context switch를 가로챌 수 있다.
- 프로세스는 공유 자원을 업데이트하는 도중에 뺏길 수 있다. -> 문제가 없어야 한다.
- 시스템 콜에서 preemptive 고려할 것
CPU burst vs I/O burst
전자의 경우 CPU를 많이 사용하고 후자의 경우 I/O를 많이 해서 I/O를 기다리는 시간이 길다. 대부분 I/O 바운드 프로세스를 사용한다.
CPU 스케쥴링은 대부분 ready queue에서 일어난다.
여러 프로세스 중 누구를 pick할 것인가가 주요 이슈이다.
FCFS(First-come, first-served)/FIFO(First-in, first-out)
jobs은 그들이 도착한 순서에 따라 스케쥴된다.(실생활에서 줄 서는 것과 같다.
전형적으로 non-preemptive이다. jobs는 동일하게 취급되어 no starvation
하지만 문제가 있다.
평균적으로 기다리는 시간이 길다. 작은 jobs은 긴 시간을 기다려야 한다.
I/O와 CPU의 overlap이 좋지 않을 수 있다.
-> 서로 기다려야 해서 overlap이 잘 안된다.
