[전공생이 설명하는 OS] 프로세스 스케줄링(feat. 알고리즘 장단점 비교)
1. Scheduling 분류 3가지
(1) Long-term schedule
- job scheduler 라고도 한다.
- 제출된 프로그램 실행 요청 중에서 어떤 것을 프로세스로 실행시킬 지 결정하는 스케줄링이다.
- 사용자가 OS에 프로그램 실행 요청을 제출 -> `요청 대기큐`
- OS는 `요청 대기큐` 중 어떤 프로그램을 `ready state 큐`로 admit 할지 결정해야한다.
- admit 되어서 실행가능한 대기 상태가 되면, 프로그램에 대한 PCB가 만들어져 프로세스가 된다.
(2) Mid-term schedule
- swapper 라고도 하며, 보통 swap function 을 가리키는 말.
- multiprogramming 의 정도를 결정하는 요인이 된다.
- swap out, swap in 할 대상의 프로세스를 결정한다.
(3) Short-term schedule
- cpu scheduler 또는 dispatcher 라고도 하며, 흔히 cpu 관점에서 말하는 스케줄링에 해당한다.
- cpu를 점유할 프로세스를 선택하는 문제.
- clock interrupt, io interrupt, signals, system call 등의 경우에 발생할 수 있다.
2. Scheduling Algorithms
여기에서는 short-term sechduling 을 다룬다. 즉 multi-process 환경에서 자원(cpu)을 얼마나 공정하고 효과적으로 분배할 수 있는가에 대한 솔루션들이 되겠다. 아래와 같은 용어들의 정의가 필요하다.
- decision mode : \(preemptive\) 또는 \(nonpreemptive\)
- selection function : 다음 프로세스를 고르기 위한 우선순위 계산 함수
- turnarround time : 프로그램이 제출된 이후 완료될 때까지 걸린 시간.
- response time : 프로그램이 제출된 이후 처음으로 반응하기까지 걸린 시간. 편의상 처음 cpu 점유하기까지 걸린 시간으로 계산하기도 함. turnarround time 보다 유저입장에서 더 중요한 요소로 여겨진다.
- deadline : 사용자가 제출한 예상시간 내에 얼마나 잘 처리했는지를 나타냄. real time system 에서 중요함.
- throughput : 단위시간 당 처리하는 프로세스의 개수
- utilization : 자원(cpu, io device)을 얼마나 효율적으로 사용하는 지 나타낸 지표
- fairness : 얼마나 공정하게 자원을 배분하는지 나타낸 지표.
(1) FCFS
- First Come First Serve의 준말로 가장 간단한 방식, FIFO와 동일하다.
- \(selection function = max[w]\), where w = total waiting time
- \(decision \ mode: non \ preemptive\)
- 장점
: 구현 방식이 가장 간단하다.
: starvation이 발생하지 않는다.
- 단점
: convoy effect(짧은 작업을 수행하기 위해 오랫동안 기다려야하는 현상)가 발생.
: cpu bound job 이 io bound job 에 비해 더 유리하다.
: 작업시간이 긴 프로세스일수록 더 유리하다.
(2) Round Robin
- FCFS에서 convoy effect를 보완한 형태이다.
- FIFO 기반은 동일하지만, 일정한 time quantum 이상 cpu를 점유하는것을 방지한다.
- time quantum 결정 문제가 굉장히 중요하다.
- 장점
: 구현 방식이 가장 간단하다.
: starvation이 발생하지 않는다.
- 단점
: time quantum 결정 문제 존재.
: cpu bound job 이 io bound job 에 비해 더 유리하다.
(3) SPN
- (Shortest Process Next)
- 예상 실행 시간이 가장 짧은 프로세스부터 작업하는 방식. 최적에 가깝다.
- \(selection \ function = min[s]\), where s is total service time required by the process
- \(decision \ mode: non \ preemptive\)
- 장점
: turnarround time 이 최적에 가깝다. => throughput 이 높다
- 단점
: 예상 실행 시간을 예측하는 것이 어렵다.
: workload 에 따라서 starvation이 발생할 수 있다.
(4) SRT
- (Shortest Remaining Time)
- SPN의 preemption 버전
- 새로운 프로세스가 제출되는 순간에 preemption 발생, 남은 시간이 가장 짧은 순서대로 작업.
- \(selection \ function = min[s-e]\), where s is 예상 소요시간, e is 실행된 시간
- 장점
: turnarround time 이 최적에 가깝다. => throughput 이 높다
- 단점
: 예상 실행 시간을 예측하는 것이 어렵다.
: workload 에 따라서 starvation이 발생할 수 있다.
(5) HRRN
- (High Response Ratio Next)
- SPN 에서 starvation을 방지하기 위해 고안된 방식
- 예상 소요시간이 짧고, 총 대기시간이 긴 프로세스를 선택한다.
- \(selection \ function = max[w/s+1]\), where s is 예상 소요시간, e is 실행된 시간
- 장점
: throughput 이 높은 편이다.
: 균형이 잘 잡혀있다.
: starvation이 발생하지 않는다.
- 단점
: 예상 실행 시간을 예측하는 것이 어렵다.
(6) Multilevel Feedback
- time quantum 이 다른 여러개의 queue 를 사용하는 방식 (Round Robin + FCFS)
- 위로 갈수록 time quantum이 짧고 우선순위가 높다. 마지막 큐는 FCFS 방식.
- time out 이 발생하면 다음 단계의 큐로 이동하는 원리 => cpu bound job 의 우선순위가 낮아진다.
- 기존에 io bound job 이 Round Robin과 FCFS 에서 불리하던 것을 보완하는 방식
- 변형이 많이 존재한다.
- starvation이 발생할 수 있다.
3. 시뮬레이션 결과
50000개의 프로세스로 시뮬레이션 한 결과이다. x축에서 오른쪽으로 갈수록 실행시간이 긴 프로세스다. 실제 os 에서는 다양한 process로 인해 workload 마다 성능이 다르다. 아래의 그래프로는 long process의 선호도만 파악할 수 있다.
(1) Turnarround time
- 가로로 일직선이 RoundRobin이다. RoundRobin은 모든 프로세스를 time quantum 씩 잘라서 골고루 분배한다고 생각하면 된다. 결국 각 프로세스의 종료는 전체적인 시간의 평균 정도로 모이는 듯하다.
- 반환시간은 전체적으로 SRT가 가장 성능이 우수하지만 90~100 정도의 길이가 긴 프로세스에 대해서는 급격하게 반환시간이 증가하는 모습을 보인다.
- FCFS 는 long process 에 대한 선호가 분명해 보인다. convoy effect 가 가장 심하다.
- response time이 최적인 SPN도 대체로 응답시간이 좋은 편이라는 것을 알 수 있지만, 0~20 구간의 short process 에서는 그렇지 않다. response time과 turnarround time 이 항상 비례하는 것이 아님을 볼 수 있다.
- HRRN 은 FCFS와 RR의 중간정도의 선호도를 갖는것으로 보인다.
- FB은 FCFS의 long process 에 대한 선호를 줄이기 위한 방법이었다. 확실히 반환시간이 대체적으로 짧은 프로세스에 대해서 좋다.
(2) Wait time
- 대체로 모든 알고리즘이, 프로세스 실행 기간이 길어질수록 총 대기시간이 길어지는 것을 확인할 수 있다.
- FCFS는 들어온 순서대로 기다리기 때문에, 같은 실행시간을 갖는 프로세스들이 모여있을 때 대기시간이 일정한 것을 볼 수 있다. FCFS는 response time 도 그렇고 확실히 long process에 대한 선호가 분명하다.
- HRRN 은 FCFS와 RR의 중간정도의 선호를 보인다.
- FB과 SRT는 response time에서와 마찬가지로 short process에 대한 선호가 있다.
4. Round Robin 심화
(1) time quantum 결정문제
[time quantum 조절 효과]
: 위의 그래프를 이용하여 비교해보면 더 쉽다.
q 가 작아지면 SPN의 그래프와 유사해지고, q가 증가하면 FCFS 와 유사해진다.
- (time quantum 감소) -> (response time 감소) -> SPN과 비슷
- io utilization에 효과적
- context switch가 빈번해짐
- turnarround time 향상은 보장 불가
- (time quantum 증가) -> (response time 증가) -> FCFS와 비슷
- context switch 가 덜 발생
- cpu bound job 의 time out interrupt 가 덜 발생
[적절한 time quantum 찾기]
: 통계적으로 접근해야함. 한번의 time quantum에 수행해도 되는 작업을 여러번으로 쪼개서 작업하게 되면, context switch에 따른 오버헤드 비용이 발생함. 따라서 평균치보다는 조금 더 크게 time quantum을 잡아야 함.
(2) io bound job 에 대한 보상
: RR은 long process 또는 cpu bound job 에 대한 선호가 있다. io bound job 의 경우에는 time quantum 만큼 cpu 를 사용하지 못하고 다시 queue 로 돌아가서 대기해야하기 때문이다. 이를 보완한 방식이 Virtual Round Robin 방식이다. Multi-level Feedback Queue와 비슷한 구조이다. time slice를 다 사용하지 않은 프로세스는 auxilliary queue에 대기한다. time slice를 다 소진한 프로세스보다 우선순위를 높게 준다. 즉 io bound job에 대해 reward를 부여하는 방식이다.
반면 Multi-level Feedback Queue는 cpu bound job에 대해 penalty를 부여하는 방식이다.