scheduling Alogrithm의 목표는 다음과 같다.
-
NO starvation
starvation: queue에서 더큰 우선순위를 가지는 process들이 계속 실행되다가 어떤 process의 차례가 오지않는 현상
-
Fairness: 각 process에게 CPU를 공평하게 공유하는 것
-
Balance: 시스템의 모든 파트가 바쁘게 움직일 수 있도록 하는것
어느 하나에만 작업량이 몰려 있다면, 처리 속도도 느리고 비효율 적이다.
scheduling 기준
- CPU 활용: CPU가 놀면 안됨
- Throughput: 시간단위당 실행을 완료하는 프로세스 수
- Turnaround time: 줄을 서기 시작 ~ 실행 끝까지의 시간
- waiting time: ready queue에서 기다린 시간
- Response time: job의 시작 부터 끝까지의 시간
FCFS/FIFO
✍️FCFS(Fisrt Come First Served)
-
job이 도착한 순서대로 scheduled
-
일반적으로 non-preemptive
preemtive: 중간에 자리를 뺏김
-
job이 동등하게 취급됨: no starvation
-
문제: 금방끝나는 job이 앞에 오래걸리는 job들 때문에 오래 기다리게 되어 Turnaround가 높아진다.
-
CPU만 할일이 많아지고 scheduler는 할일이 없다.
response time이 짧은것이 앞에 있는게 평균 turnaround 시간이 훨씬 짧다.
Preemptive scheduling
✍️Non-preemptive scheduling
- scheduler는 실행중인 작업이 자발적으로 CPU를 양보할때까지 기다린다.
- resource를 받으면 실행이 끝까지 보장됨.
✍️Preemptive scheduling
- scheduler는 job을 중간에 강제로 context switch 할 수 있다.
SJF (Shortest job first)
- CPU를 사용량이 가장 적은 것부터 선택
- waiting time에 최소시간을 보장한다.
- Non-preemptive
- Priority scheduling
✍️ problem
- starve할 가능성이 있다.
- 미래의 CPU burst size를 알 수가 없다.
예를들어 P1이먼저 들어와서 실행되고 있었고, P2,P3가 들어왔다.
그러면, P1이 다 끝날때까지 기다렸다가 p2와 p3중 실행시간이 더짧은 p2를 먼저 실행시킨다.
starvation
- resource를 보유하고 있는 process가 계속 있어서 실행하고 싶은 process가 계속 실행되지 못하고 밀리는 상황 (리소스는 CPU나 lock일 수 있다.)
- 잘못된 scheduling policy는 starvation을 유발 할 수 있다.
낮은 prioriy job들은 높은 priority job들이 계속 할당된다면 실행되지 못할지도 모른다.
STCF(Shortest time completion first)
- SJF(shortest job first)의 preemptive version
- 현재 job의 남아있는 시간보다 더 낮은 시간이 남은 job이 들어오면 먼저 실행한다.
RR(Round Robin)
✍️ 원형 FIFO queue처럼 다뤄진다.
✍️ 모든 job들은 time slice가 주어진다.(or scheduing quantum)
- 한 process에 time slice가 주어지면 주어진 time slice 동안만 실행되고 맨뒤로 이동
- 너무 짧으면 context switch가 자주 일어나서 overhead가 커진다.
- 너무 길면 Round Robin을 하는 의미가 없어진다. FIFO처럼 실행됨.
- 적당한 시간을 줘야한다.
✍️ time slice 시간동안 process가 실행되고 맨뒤로 이동, 다음 process 실행
예를들어, quantum이 4라고 하자.
각 process들이 4만큼만 실행하고 있다.
그리고, 남은 시간은 맨뒤로 줄서서 4만큼씩 다시 실행한다.
✍️ preemptive
✍️ No starvation
✍️ resopnse time 향상 (time sharing에 좋다.)
✍️ waiting time은 quantum에 따라 다르다.
priority scheduling
✍️ 각 job들은 priority가 있다.
✍️ CPU는 높은 priority를 가진 job을 할당받는다.
- preemptive or nonpreemptive 모두 가능하다.
✍️starvation problem
- 낮은 priority를 갖은 process들은 높은 priority를 가진 process들이 계쏙 들어오면 실행되지 않을 수도 있다.
- 해결방법: Aging or Priority boosting
process가 age를 먹으면 priority를 높인다.
priority inversion
✍️priority inversion problem
여러 작업에서 동시에 사용할 수없는 resource가 있다고 가정하자.
가장 낮은 10 priority를 가진 thread(data gethering task)가 실행하면서 lock을 걸어놓고 메모리 접근을 막고 write하고 있었다. 그런데 높은 priority를 가진 30 priority의 thread(Bus task)가 들어와서 우선순위에 따라 bus task가 실행되었다. bus task에서 resource에 접근하려고 봤더니 lock이 걸려있어서 interrupt가 발생하였고, data gathering task가 lock을 release할때까지 기다려야 되는 상황이 되었다. 그래서 bus task는 block 되었다.
다시 data gathering task를 진행하다 보니까 중간 priority 20을 가지는 process가 들어와서 실행되었다.(priority 30은 block 상태, 10,20만 ready queue에 있어서 우선순위에 따라 20이 실행됨)
원래는 가장 높은 priority의 task가 먼저 실행이 끝나야 하는데 중간 priority task가 가로채버린 것이다.
lock이란? 어떤 thread가 공유자원을 사용하고 있을때 다른 thread가 공유자원에 접근하지 못하게 막는것.
✍️Priority Inversion solution
- priority inheritance protocol(PIP)
높은 priority가 resource를 잡으려했는데 row priority가 잡고있다면 순간적으로 row priority의 priority를 boosting 시켜준다. 그래서 중간에 다른 thread가 와도 밀어내질 못한다.
결과적으로, high priority와 lowr priority가 high priority로 같아진다.
resource를 해제하면 다시 원래 상태로 돌아감.
- 낮은 priority가 resource를 잡는다고 boosting 시켜주지는 않기 때문에 프로그램 성능이 낮아지지는 않는다.
- Priority ceiling protocol(PCP)
낮은 priority thread의 priority는 resource가 할당되면 즉시 증가한다.
어차피 빠르게 잡고 놔주면 되므로
priority ceiling 값은 미리 결정 되어야만 한다.
구현하기는 쉽지만, 리소스를 잡을때마다 priority boosting을 시켜주면 프로그램 성능이 낮아질 수 밖에 없다.
