SJF(Shortest Job First)(non-preemptive)
CPU를 사용하는 시간이 가장 짧은 것을 고르는 것
SJF를 사용하게 되면 (모든 작업이 동시에 들어왔다면) ready queue에서 기다리는 평균 시간이 가장 짧다는 것을 증명할 수 있다.
문제점
이 job이 CPU를 얼마나 사용할지 예측할 수 없다.
그래서 추측하는 방식을 사용하고 운이 좋지 않으면 starvation이 생길 수 있다.
SRTF(Shortest Remaining Time First)(preemptive)
SJF의 preemptive 버전이다.
새로운 프로세스가 들어오면 다시 생각하여 preemtion을 진행한다.
remaining time < burst이면 preempt한다.
RR(Round Robin)
- Ready Q가 circular FIFO Q처럼 다뤄진다.
- 각 job에게 시간이 주어져 있다(time slice or time quantum)
- Great for timesharing
-> no starvation(FIFO방식)
-> 전형적으로 SJF보다 평균 turnaround시간이 길지만 응답시간이 더 좋다.- Preemptive(FIFO이면서 즉, 먼저 들어온 것이 먼저 실행함)
- time quantum을 정하는 것이 주요 이슈
A rule of thumb : CPU burst의 80%가 time quantum보다 짧아야 한다.
Longer quantum : 높은 throughput(turnaround가 줄어듦)
Shorter quantum : Shorter response but throughput이 안좋음.
Priority Scheduling
job을 선택할 때 가장 높은 우선 순위의 프로세스를 선택한다.
SJF: priority scheduling, CPU사용량이 가장 작다면 우선순위를 가진다.
RR or FIFO(same priority)
preemtive(SRTF vs non-preemptive(SJF)
우선권은 동적으로 조정된다.
MLFQ(Multi Level Feedback Queue)로 구현한다.
문제점
starvation이 생길 수 있다. 높은 우선권을 가진 jobs가 끝도 없이 보충되면 낮은 우선권을 가진 job은 동작할 수 없다.
Aging기법을 사용한다.
오래기다리면 우선순위를 높인다.
CPU를 많이 쓰는 프로세스의 우선순위를 낮춘다.
Priority inversion problem(우선순위 역변 문제)
낮은 우선순위의 프로세스(lock을 갖고 있음) 때문에 높은 우선순위의 프로세스가 동작하지 못하는 상황
해결 방법
1. PIP(Priority inheritance protocol)
-> 높은 우선순위 job이 우선순위를 낮은 우선순위 job(높은 우선순위 job이 요구하는 리소스를 갖고 있는)에게 기부하는 것
2. PCP(Priority Ceiling Protocol)
-> 낮은 우선순위 스레드의 우선순위는 그낮은 우선순위 스레드가 리소스(lock)를 가질 때 바로 최고의 우선순위를 갖게 된다.(빨리 cs를 벗어나도록 한다.)
-> priority ceiling value가 미리 정의되어 있어야 한다.
Multi Level Feedback Queue
multilevel queue란? 다양한 큐를 왔다갔다 하며 priority를 조정한다. 즉, 다양한 큐 사이에서 job이 움직이도록 허락해주는 스케줄링
multilevel queue란? 다양한 큐를 왔다갔다 할 때, 큐에서 큐로 넘어갈 수 있도록 해준다. 해당 큐에서 작업이 끝나지 않으면 다음 큐로 넘겨서 작업하는 것을 반복한다.
큐는 우선권을 가지고 있다.
프로세스가 CPU를 너무 많이 사용하면 낮은 우선순위로 옮긴다.
I/O bound 와 interactive 프로세스들을 높은 우선순위 큐로 옮긴다. 이렇게 하면, CPU를 빨리빨리 많이 받을 수 있음
프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 높은 우선순위 큐로 옮긴다. -> starvation을 예방한다.(Aging 기법처럼)
유닉스 스케줄러
preemptive
priority-based
time-shared(based on RR)
MLFQ(프로세스는 동적으로 우선순위를 바꾼다)
CPU-bound process보다 I/O bound process가 먼저 선택되도록 정책을 잡고 있다. I/O bound process는 보통 short CPU burst. 좋은 interactive response를 제공한다. 그렇다고 해서 CPU-bound process가 크게 영향을 받지 않는다.
no starvation(use aging)
