[OS] scheduling(1)

📌process scheduling 

: ready queue에 있는 프로세스 중 누구에게 다음 CPU 권한을 넘겨줄 것인지 OS가 결정하는 것

scheduling 기준 분류
- user oriented : TAT, reponse time, deadline …
- system oriented : throughput, processor utilization …
- fairness, balancing resource …
🌟모든 부분이 뛰어난 완벽한 scheduling algorithm은 존재하지 않는다!

scheduling 기준
- (maximize) CPU utilization : 최대한 CPU가 쉬는 시간이 없게 알차게 활용하는 것
- (maximize) throughput : 단위 시간당 처리된 일의 수 <서비스 제공자 입장에서 이득>
- (minimize) turnaround time (TAT) : 요청 시각부터 최종 완료까지의 시간
- (minimize) waiting time : ready queue에서 실행되기를 대기하는 시간의 합 → TAT와 response time에 영향을 준다
- (minimize) response time : 요청 시각부터 ‘내 요청이 수행되고 있구나!’를 알 수 있는 첫번째 응답까지의 시간
- fairmess : 최소한 한 번씩은 모든 프로세서에게 CPU권한을 주는 것 (O)  
    모든 프로세서에게 CPU권한을 동일하게 주는 것이 fairness가 아니다!  
    모든 프로세서가 한 번이라도 CPU권한을 받았다면 fairness하다.
    → starvation(실행되어야하지만 CPU권한을 한 번도 받지 못하는 경우)을 예방할 수 있다.
    
process scheduling
- long-term scheduling : 어느 프로그램을 memory로 올릴까?
- mid-term scheduling : disk와 memory 사이
    ex. swapping, 용량이 부족한데, block queue에서 어느 프로세스를 disk로 보내지?
- short-term scheduling : ready queue와 memory 사이
    ex. ready queue에 있는 프로세서 중에 누구에게 다음 CPU 권한을 주지?
    
terminology for scheduling
- non-preemptive (cooperative) scheduling : OS의 프로세스 강제종료가 불가능
- preemptive scheduling : OS의 프로세스 강제종료가 가능

📌scheduling 알고리즘 결정과정

: 단순화(가정) → 단순화 상황에서 동작 가능한 기법 만들기 → 실제 상황에서 돌려보기 → 안되는 부분은 해당 가정 지우고 개선 & 되는 부분은 유지 → 최종 알고리즘에 도달

 

- workload : 실제 사용자의 패턴
🌟workload assumptions <5가지 가정>
1. 모든 job의 실행시간이 동일하다.
2. 모든 job들은 동일시간에 시스템으로 들어온다.
3. 모든 job이 I/O 사용X. CPU만 사용한다.
4. 모든 job들의 실행시간을 이미 알고있다.
5. job을 한 번 실행하면, 중간에 멈추지 않는다. (non-preemptive)

🌟TAT 기준으로 위의 가정을 통해 알고리즘 결정과정을 진행해봅시다.
(TAT = 종료시간 - 출발시간)

 

가장 기본적인 스케쥴링 기법부터 가정을 확인해봅시다.
1. FIFO ( First in, First out) : 선입선출, 먼저 들어온 프로세스부터 수행 (FCFS)
- 가정 : 프로세스가 A-B-C 순서대로 거의 동시에 도착했다 / 각 프로세스의 실행시간은 10초

👇🏻 Gantt chart : 시간순으로 어떤 job이 얼마나 수행되었는지 표시한다.

❣️평균 TAT = (10+20+30) / 3 = 20초

✔️ 가정(1)을 지워보자! 각 job의 수행시간이 다를수도 있다면?
- 아까와 같은 조건에 A의 수행시간이 100초라고 가정

❣️평균 TAT = (100+110+120) / 3 = 110초
수행시간이 긴 A가 가장 먼저 들어왔기 때문에 전체 TAT가 증가한다.

convoy effect : long 프로세스에 의해 shrot 프로세스가 stuck되는 현상
- 나의 수행시간은 짧지만 먼저 들어온 프로세서의 수행시간이 길어 시스템 전체의 TAT가 늘어나는 현상
→  FCFS에서 수행시간 짧은 프로세스가 불리해진다. 성능을 높이기 위해서 오래 걸리는 프로세스를 뒤로 보내야한다!

2. SJF (Shortest job first)
- 가정 : A-B-C 순서로 거의 동시에 들어왔다. / 수행시간은 직전과 같다 (100/10/10)

❣️평균 TAT = (10+20+120) / 3 = 50초
짧은 B와 C를 먼저 수행했더니 TAT가 개선되었다! 

✔️ 가정(2)을 지워보자! 각 job이 다른 시간에 도착할 수도 있다면?
- 아까와 같은 조건에서, B와 C가 10초 경과 후 도착한다고 가정

❣️평균 TAT = (100+(110-10)+(120-10)) / 3 = 103.3초

한 번 실행한 프로세스를 종료 전에 멈출 수 없기 때문에(가정5에 의해) A가 종료된 후에 B, C가 수행되어 TAT가 다시 커진다.
→ 도중에 멈출 수 있게 해야한다! ✔️가정(5)을 지운다!

3. STCF (Shoortest time-to-completion first)
: 프로세스가 실행 중에 다른 프로세스가 도착한다면 1. 일단 멈추고 2. 실행중이던 프로세스의 남은 시간 VS 새로 들어온 프로세스의 실행시간 을 비교하여 짧은 것을 수행한다. (preemptive)
- 가정 : 직전과 같다.

❣️평균 TAT = (120+(20-10)+(30-10)) / 3 = 50초

B, C 도착 후에 비교를 거쳐 짧은 것을 먼저 수행했더니 TAT가 개선되었다!
→ <문제점> 수행시간이 긴 프로세스가 CPU권한을 받기 힘들어져 starvation이 발생할 수 있다.
OS는 해당 프로그램이 이전에 수행되었을 때의 수행시간을 기억하고, 이전 수행시간의 평균을 통해 이번에도 그만큼 수행 될 것이라고 추측하여 scheduling을 진행한다.
→ 최신 경향(점점 높아지거나 점점 낮아지는)을 반영하지 못한다 → 가중평균 필요

✔️ TAT를 만족시키는 알고리즘은 response time도 만족할 수 있는가?
- 가정 : ABC 동시도착 / 실행시간 5초 / time slice 1초

 (보기) SJF

❣️평균 response time = (0+5+10) / 3 = 10초

     평균 TAT = (5+10+15) / 3 = 10초

 

4. RR (Round robin) scheduling : time slice scheduling

❣️평균 response time = (0+1+2) / 3 = 1초

     평균 TAT = (13+14+15) / 3 = 14초

- SJF : reponse time 나쁘지만 / TAT가 좋다.
- RR : reponde time 좋지만 / TAT가 나쁘다.
→ 모든 것을 만족하는 알고리즘은 없다! time slice 작다고 다 좋은 것도 아니다!
time slice가 짧다면? reponse time은 좋지만 / context switching 비용이 더 큰 부분을 차지하는 overhead 발생

✔️ 가정(3)을 지워보자! 프로세스가 I/O를 사용한다면?
- 가정 : A-B순 동시도착 / A와 B가 CPU에서 실행되어야 하는 시간은 50초 / A는 10초에 한 번씩 I/O /

overlap을 통해 CPU utilization과 TAT, response time을 줄일 수 있다!

✔️ 가정(4)...는 다음 게시글에서 확인하세요!