CPU scheduling
큐에 들어와있는 프로세스 중 어떤 프로세스를 다음에 동작시킬 것인가를 결정한다. 빈번히 일어나고 빠르고 효율적으로 결정할 수 있어야 한다.
빨간 부분마다 context switch 일어나고 이때 scheduling을 해준다.
scheduling 알고리즘의 목표
- 모든 시스템에서:
- no starvation : CPU 할당이 안되는 프로세스가 없어야 한다.
- Fairness : 모든 프로세스가 공정하게 CPU를 점유해야 하고
- Balance : 최대한 많은 하드웨어 자원이 동시에 사용되고 있어야 한다.
- Batch System에서: ex) 엔터 치면 몇시간동안 코로나 바이러스 분석하는 프로그램
- Throughput : 시간당 처리량이 많도록 해야 한다.
- Turnaround time : job이 시작해서 끝날때까지 시간을 최소화하면 throughput이 좋아진다.
- CPU Utilization : 올타임으로 CPU를 바쁘게 만든다.
- Interactive System에서:
- 반응속도가 빠르도록 한다.
- Real time System에서 :
- deadline을 충족 : ex)자율주행차에서ㅓ deadline이 지켜지지 않으면 사고난다.
- Predictability : 멀티미디어를 스트리밍하는데 끊기지 않도록 한다.
starvation
다른 프로세스가 자원(CPU)를 쓰고 있어서 또는 lock이 걸려있어서 다른 프로세스가 진행되지 않는 상태이다. 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스가 CPU를 점유하는 것을 막는 것이다. 동기화에서 lock이 starvation을 야기할 수 있다.
response time
프로세스가 CPU를 뺴앗기고 얼마나 기다려야 다시 CPU를 할당받을 수 있는가?
Non-preemptive scheduling
스케쥴러는 프로세스가 자발적으로 yield 할 때까지 그냥 기다린다. job이 상호 협력적이어야 가능.
Preemptive scheduling
스케쥴러가 context switch나 인터럽트로 CPU를 빼앗아온다.
CPU burst vs I/O burst
- CPU burst : CPU를 많이 사용 ex) 의학 데이터 분석..
- I/O burst : I/O를 많이 하여서 I/O를 기다리는 시간이 CPU를 사용하는 시간보다 상대적으로 길다.
**대부분 프로세스는 I/O burst가 많다.
CPU scheduling
ready queue에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할 것인가? 에 대한 고민
FCFS-First-come-first-served/FIFO
일찍 도착한 순으로 스케쥴링한다. non-preemptive하다. 순서대로 처리하면 언젠가는 CPU를 할당받기 때문에 starvation이 없다. 작은 job인데 긴 시간을 기다려야 할수도 있고, I/O와 CPU의 overlap이 좋지 않다. Batch System에 적합하다.
SJF(Shortest Job First)
CPU를 가장 짧게 쓰는 job을 먼저 스케쥴링한다. 모든 작업이 동시에 이루어질 수 있는 경우에만 평균 waiting time이 가장 짧다. non-preemptive하다. 다만, CPU 사용시간을 예측하는게 불가능해 추측하는 방식을 사용하고, CPU burst가 짧은 job이 계속 들어오면 starvation이 발생한다.
SRTF(Shortest Remaining Time First)
큐에 프로세스가 도달했을 때, 큐에 있는 작업들 중 남은 시간이 가장 짧은 job을 선택한다. SJF의 preemptive 버전이고 SRTF는 SJF보다 반응성이 좋다. 그렇다고 interactive system에 완벽히 좋지도 않다. 얘도 짧은 job이 계속 들어오면 starvation 생길 수 있다.
RR(Round Robin)
레디 큐가 원형 큐처럼 다뤄진다. 각 job에 시간이 주어지는데 이를 time quantum이라 한다. starvation이 없고 SJF보다 오래 기다릴 순 있지만 반응이 빠르다. 이는 timesharing이 좋다고도 한다. preemptive한 방식이다.
- Longer quantum : 높은 throughput(turnaround가 줄어듦)(context switch 적음)
- Shorter quantum : 반응속도 빠름(낮은 throughput)(context switch 많음)
Priority Scheduling
가장 우선순위가 높은 순으로 스케쥴링한다. preemptive할수도 있도 non-preemptive할수도 있다. 우선순위는 동적으로 조정 가능하고 Multi-Level-Feedback-Queue로 구현한다.
- SJF : 우선순위 스케쥴링의 일종으로 CPU 사용량이 작은 것이 높은 우선순위를 갖는다.
- RR or FIFO : 들어온 순서대로 처리하기 때문에 같은 우선순위를 갖는다.
Priority Scheduling 문제점
우선순위 높은 job이 계속 들어오면 starvation이 생길 수 있다. 이를 해결하기 위해 Aging 기법을 사용하면 되는데, 오래 기다린 프로세스의 우선순위를 높여주고 CPU time이 긴 프로세스의 우선순위를 조금씩 낮춘다.
Priority inversion problem(우선순위 역변 문제)
낮은 우선순위의 프로세스가 lock을 갖고 있어서 높은 프로세스가 동작하지 못하는 상황으로, 화성 탐사 로봇의 예가 있다. 이를 해결하기 위해 두 가지 방법이 있는데 ,
1. PIP(Priority inheritance protocol) : 높은 우선순위의 job이 낮은 우선순위의 job에게 기부하는 것으로, 화성 탐사선의 예제에서 높은 우선순위의 job이 낮은 우선순위의 job에 CPU를 기부하여 lock을 빨리 풀고 나오도록 한다.
2. PCP(Priority Ceiling Protocol) : 낮은 우선순위의 job이 lock을 가질 때 최고 우선순위를 주어서 빨리 lock을 풀고 나오도록 한다.
Multi Level Feedback Queue
여러개의 큐를 두어 왔다갔다 하면서 우선순위를 조정한다. job이 큐 사이를 이동할 수 있도록 한다. 해당 큐에서 작업이 끝나지 않으면 다음 큐로 넘겨서 작업하는 것을 반복한다. 어떤 job이 CPU를 너무 많이 쓰면 낮은 우선순위 큐로 내린다. I/O bound 와 interactive job들은 높은 우선순위 큐로 옮긴다. 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 높은 우선순위 큐로 옮겨서 starvation을 예방한다.
예제에서 Q0에 우선 들어오고, 8밀리세컨드동안 작업이 끝나지 않으면 Q1으로 내린다.
