[전공생이 설명하는 OS] 프로세스 스케줄링(feat. 알고리즘 장단점 비교)

1. Scheduling 분류 3가지

7-state model 에 기반한 스케줄 모형도

(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 에 대한 보상

virtual Round Robin

  : 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를 부여하는 방식이다.