운영체제 - CPU 스케쥴링 알고리즘 ( FCFS, SJF, SRTF, Priority, RR ), 기아 현상

스케쥴링 알고리즘 ( Scheduling Algorithm )
。스케쥴링 큐에서 CPU 제어권의 할당을 대기하는 Ready Queue에 적재된 프로세스 중 CPU Core의 제어권을 배정할 우선순위 프로세스를 결정하는 알고리즘
▶ 스케쥴링 알고리즘을 통해 프로세스 실행순서 결정 후 단기 스케쥴러에 의해 선택되어 디스패처를 통해 프로세스에게 CPU 할당

MLQ , MLFQ

스케쥴링 종류

선점형 스케쥴링 ( Preemtive Scheduling )
。CPU가 배정된 프로세스가 CPU 스케쥴러에 의해 CPU를 강제로 회수
▶ 더 높은 우선순위 프로세스가 발생 시 CPU를 회수

。FCFS, SRTF, RR, Priority-based

비선점형 스케쥴링 ( Non-Preemtive Scheduling )
。CPU가 배정된 프로세스가 Waiting status로 변경되거나 Terminate될때까지 CPU를 계속 점유
▶ 안정성은 좋으나 효율이 좋지않음

。FCFS, SJF, Priority-based

기아 ( Starvation )
。 먼저 Ready Queue에 적재되어 Ready 상태로 높은 값의 Priority를 갖는 특정 프로세스보다 Ready Queue에 유입되는 낮은 값의 Priority를 갖는 프로세스들이 우선 Execute되어 무한정으로 대기하는 현상
▶ indefinite blocking라고 한다.

。Dead Lock에서도 나오는 개념

• SJF, SRTF, Priority-based는 기아현상에 주의
  
  
• 기아 해결법 : aging
  。오랜 기간동안 Ready Queue에서 대기중인 프로세스에 대해 priority 값을 점진적으로 감소시키는 기법

FCFS 스케쥴링 ( First-Come , First-Served )
。가장 간단한 CPU Scheduling Algorithm
▶ 비선점형 스케쥴링 방식

。CPU를 가장 먼저 요청한 프로세스에게 CPU를 먼저 배정
▶ FIFO Queue를 통해 쉽게 구현가능

。먼저 subimit된 프로세스의 burst에 따라서 Average Waiting time이 크게 변한다.
▶ 소요시간이 긴 프로세스가 먼저 도착 시 전체 효율이 감소

• FCFS 스케쥴링의 문제점

  • Average waiting time이 다른 스케쥴링에 비해 최소가 되지않음
    
    
  • 프로세스마다의 CPU Burst의 변화가 클 경우 Average waiting time과 Average Turnaround time의 변화폭도 상당히 변화
    
    
  • 비선점형 스케쥴링( Non-preemtive ) 방식
    。프로세스에 CPU를 배정하여 Execute할때 중간에 CPU를 회수하지 않으므로.
    
    
  • 호송 효과( Convoy Effect )
    。 CPU를 오래 점유하는 프로세스가 먼저 Execute되어, 그 뒤에 짧은 실행 시간을 가진 프로세스들이 불필요하게 오래 대기하는 현상
    ▶ burst가 작은 프로세스들이 먼저 Execute하는 것에 비해서 CPU 사용률이 낮게 도출
    
    ex ) ML 등을 수행하는 아주 큰 CPU Bound 하나와 다수의 I/O Bound로 구성 시
    
    。SJF를 사용하여 해결

• 
  
  
• 원리 : 사전설정
  。time : 0부터 시작
  。각 프로세스( $P1,P2,P3$ )의 CPU brust가 ms 기준으로 다음과 같음
  
  
  
• FCFS 스케쥴로 Waiting time, Turnaround time 계산
  
  。Waiting time : 각 프로세스의 실행전까지 대기시간
  。Turnaround time : 각 프로세스의 Execute 시 제출부터 완료까지의 시간

  • FIFO Queue로 프로세스가 $P1$→$P2$→$P3$ 순으로 들어온 경우
    。FCFS policy로 Gantt Chart에 의해 다음처럼 표현
    

    • Waiting time 계산
      。각 프로세스의 Waiting time
      $P_1 : 0$ , $P_2:24$ , $P_3:27$
      ▶ $P_3$ 실행까지 $P_1+P_2=27$초를 대기
      
      
      Total Waiting time :
      $0+24+27=51$
      。Average Waiting time : $\frac{51}{3}=17$
      
      。먼저 Submit된 $P_1$의 Burst가 매우 크므로 $P_2$ , $P_3$의 Waiting time이 크게 도출
      
      Turnaround time 계산
      。각 프로세스의 Turnaround time
      $P_1 : 24$ , $P_2 : 27$ , $P_3 : 30$
      ▶ 각각의 프로세스의 제출부터 완료까지의 Waiting time + CPU Burst을 도출
      
      。Total Turnaround time : $24+27+30=81$
      。Average Turnaround time : $\frac{81}{3}=27$

  • 
    
    
  • FIFO Queue로 프로세스가 $P2$→$P3$→$P1$ 순으로 들어온 경우
    

    • Waiting time 계산
      。각 프로세스의 Waiting time
      $P_1 : 6$ , $P_2:0$ , $P_3:3$
      。Total Waiting time :
      $6+0+3=9$
      。Average Waiting time : $\frac{9}{3}=3$
      
      。먼저 Submit된 $P_2,P_3$의 Burst가 작으므로 앞전의 예제의 Waiting time보다 획기적으로 작게 도출
      
      
    • Turnaround time 계산
      。각 프로세스의 Turnaround time
      $P_1 : 30$ , $P_2 : 3$ , $P_3 : 6$
      ▶ 각각의 프로세스의 제출부터 완료까지의 Waiting time + CPU Burst을 도출
      
      。Total Turnaround time : $30+3+6=39$
      。Average Turnaround time : $\frac{39}{3}=13$

SJF 스케쥴링 ( Shortest next CPU burst First ) = SRTF ( Shortest Remaining Time First )
。Ready Queue에서 각 프로세스에서 실행할 CPU burst 중 가장 짧은 CPU Burst를 가진 프로세스에 우선적으로 CPU를 배정하는 알고리즘
▶ 프로세스의 next CPU burst가 서로 동일한 경우, FCFS 스케줄링 방식으로 CPU를 배정

next CPU burst = predicted CPU burst

。제공된 프로세스들에 대해 SJF 스케쥴링 시 최소 Average Waiting time을 제공하므로 최적화된 스케줄링 기법
▶ FCFS와 비교하여 짧은 next CPU Burst를 지닌 프로세스를 먼저 Execute할 경우 전체 프로세스의 Waiting time이 감소하므로.

。 SJF 스케쥴링은 비선점형 스케쥴링 또는 선점형 스케쥴링( = SRTF 스케쥴링 )으로 구현

• SJF / SRTF는 기아 현상( Starvation )에 주의
  。CPU Burst가 긴 프로세스의 경우 오랜시간동안 CPU를 할당받지 못해 기아현상이 발생할 수 있다.
  ▶ 기아현상 : 우선순위가 낮은 프로세스가 장시간동안 자원을 할당받지 못한 상태
  
  
• SJF 원리 : 사전설정
  각 프로세스의 Burst time(ms)
  $P_1:6$ , $P_2:8$ , $P_3:7$ , $P_4:3$
  
  
• SJF 스케쥴로 Waiting time, Turnaround time 계산
  。Burst time가 작은 프로세스 순으로 스케쥴링
  ▶ $P_4$ → $P_1$ → $P_3$ → $P_2$
  

  • Waiting time 계산
    。각 프로세스의 Waiting time
    $P_1 : 3$ , $P_2:16$ , $P_3:9$ , $P_4:0$
    。Total Waiting time :
    $3+16+9+0=28$
    。Average Waiting time : $\frac{28}{4}=7$
    
    
  • Turnaround time 계산
    。각 프로세스의 Turnaround time
    $P_1 : 9$ , $P_2 : 24$ , $P_3 : 16$ , $P_4:3$
    
    。Total Turnaround time : $9+24+16+3=52$
    。Average Turnaround time : $\frac{52}{4}=13$

• 
  
  
• SJF 스케쥴링의 문제점
  。각 프로세스의 next CPU burst를 알 수 없으므로 구현이 어렵다
  ▶ 해당 task의 작업처리시간을 정확히 예측할 수 없으므로.
  
  。따라서, next CPU Burst를 근사적으로 예측

  • 프로세스의 next CPU Burst를 예측하는 방법
    。과거시점에서 측정된 CPU Burst들을 통해 exponential average를 도출
    
    $\tau_{n+1} = \alpha t_n+(1-\alpha)\tau_n$
    
    。$t_n$ : $n$번 CPU Burst 실제값
    。$\tau_n$ : $n$번 next CPU Burst 예측값
    。$\tau_{n+1}$ : $n+1$번의 next CPU Burst의 예측값
    。$\alpha=[0,1]$ : 가중치
    
    ▶ $\alpha$값을 조정하면서 과거의 CPU Burst 예측값과 최근 CPU Burst간의 가중치를 부여가능
    ▶ $\alpha\approx0$에 가까울 경우 과거 예측값을 중점적으로 반영
    
    。$\alpha=\frac{1}{2}$ 일때, $\tau_{2} = \alpha t_1+(1-\alpha)\tau_1$
    
    ▶ $8=\frac{1}{2}*10+\frac{1}{2}*6$
    
    。실제 CPU Burst( 검정 )에 매우 근사하게 도출

SRTF 스케쥴링( Shortest Remaining Time First )
。선점형 SJF 스케쥴링 방식

。CPU가 배정된 프로세스의 Remaining time보다 Ready Queue에 새로 적재된 프로세스의 예측된 next CPU Burst가 짧을 경우 해당 프로세스로 Context Switching 수행
▶ 비선점형 SJF 스케쥴링은 해당 경우 현재 CPU가 배정된 프로세스를 완료 시킨 후 next CPU Burst가 짧은 프로세스로 CPU 배정

• SRTF 원리 : 사전설정
  。각 프로세스의 Burst time(ms)과 Ready Queue에 들어온 Arrival time
  
  
  
• SRTF 스케쥴로 Waiting time 계산
  。현재 CPU 선점중인 프로세스의 Remaining time과 새로 Ready Queue로 들어온 프로세스의 next CPU burst를 비교 후 Context Switching을 수행

  SRTF 스케쥴링
  

  • $P_1$이 맨처음 Ready Queue 진입 후 CPU 배정되어 1ms 소요 후 $P_2$ Ready Queue 진입
    
    $P_1$ Remaining time= 8 - 1 = 7
    $P_2$ CPU Burst = 4
    
    ▶ $P_1$ Remaining time $>$ $P_2$ CPU Burst 이므로 $P_1, P_2$ 간 Context Switching
    
    
  • $P_2$ CPU 배정 후 1ms 소요 후 $P_3$ Ready Queue 진입
    
    $P_1$ Remaining time= 4 - 1 = 3
    $P_2$ CPU Burst = 9
    
    ▶ $P_2$ Remaining time $<$ $P_3$ CPU Burst 이므로 $P_2$ Execute 유지
    
    
  • $P_2$ CPU 배정 후 2ms 소요 후 $P_4$ Ready Queue 진입
    
    $P_1$ Remaining time= 4 - 2 = 2
    $P_2$ CPU Burst = 5
    
    ▶ $P_2$ Remaining time $<$ $P_4$ CPU Burst 이므로 $P_2$ Execute 유지
    ▶ 모든 프로세스가 Ready queue에 들어왔으므로 $P_2$는 Context Switching 없이 Execute
    
    
  • $P_2$ Terminate 후 CPU Burst가 가장 작은 프로세스로 CPU 할당
    
    CPU Burst : $P_1 : 7$ , $P_3 : 9$ , $P_4 : 5$
    
    ▶ $P_4$ → $P_1$ → $P_3$ 순으로 Execute
    
    。최종적으로 $P_1$ → $P_2$ → $P_4$ → $P_1$ → $P_3$ 순으로 Execute
    
    
  • Waiting time 계산
    。각 프로세스의 Waiting time
    $P_1 : 0-0 , 9-0$ , $P_2:1-1$ , $P_3:17-2$ , $P_4:5-3$
    ▶ waiting time에 arrival time을 고려하는 경우
    
    。Total Waiting time :
    $0+9+0+15+2=26$
    。Average Waiting time : $\frac{26}{4}=6.5$
    
    
  • SJF 스케쥴링으로 도출 시
    
    Average Waiting time :
    
    $\frac{0+(8-1)+(12-3)+(17-2)}{4}=7.75$
    
    ▶ SRTF 가 비선점형 SJF에 비해 효율적

Priority-based 스케쥴링

。PCB의 우선순위 정보( = Priority )를 기준으로 우선의 Priority를 갖는 프로세스에게 CPU 제어권을 배정하는 스케쥴링 방식
▶ 각 프로세스간 Priority가 동일한 경우 FCFS 스케쥴링

。SJF 스케쥴링의 경우 Priority-based 스케쥴링의 Special case.
▶ SJF의 Priority는 next CPU burst의 역순

。일반적으로 RR 스케쥴링 기법과 조합하여 사용

• Priority-based 스케쥴링은 선점형 스케쥴링이거나 비선점형 스케쥴링
  。비선점형 : Ready Queue에 더 높은 우선순위의 프로세스가 도착하더라도 대기
  
  。선점형 : Ready Queue에 더 높은 우선순위의 프로세스가 도착 시 CPU 제어권 회수
  
  
• Priority-base 스케쥴링 원리 : 사전설정
  
  
  
• Priority-based 스케쥴링의 문제점
  。기아현상
  ▶ Aging 기법으로 해결
  
  
• Round Robin , Prioirty-base 조합 원리
  
  。프로세스들을 우선 Priority를 기준으로 스케쥴링을 수행 후 동일한 Priority가 발생한 경우 Round Robin 스케쥴링을 사용하여 스케쥴링을 수행
  
  ▶ $P_2$ & $P_3$와 $P_4$ & $P_5$는 priority가 동일하므로 각각 RR 스케쥴링 수행

RR 스케쥴링 ( Round-Robin )

。Ready Queue에 적재된 프로세스들에게 각각 동일한 시분할을 통해 분할된 시간단위( quantum )를 부여하여 Interleaving을 수행하는 방식
▶ 선점형 FCFS 방식으로서 quantum을 최소화할 경우 가장 빠른 응답시간을 기대할 수 있음.

。FCFS 방식과 유사하므로 Ready Queue는 Circular Queue로 구현
▶ 할당시간( quantum )이 지난 프로세스는 Cirular Queue의 맨 뒤에서 다시 할당을 대기

。단기 스케쥴러는 1 time quantum 단위로 Ready Queue의 각 프로세스에게 CPU를 배정
▶ time quantum의 사이즈에 따라 Context Switching 빈도가 변화하면서 성능이 상당하게 변화

。RR policy의 average waiting time은 다른 스케쥴링에 비해 길 수 있어 최적은 아니지만, Priority-base 스케쥴링과 조합해서 사용 시 좋은 효율을 보임

• RR 스케쥴링은 Time Quantum Size에 따라 OS의 성능이 결정
  
  。Time Quantum Size에 따라 Context Switch의 빈도 변화
  ▶ Time quantum의 사이즈가 작을수록 Context Switch 빈도 증가
  
  。 Time quantum size가 너무 작아서 Context Switch의 발생이 잦을 경우 Dispatch Latency 때문에 성능이 좋지 않음
  ▶ time quantum = 0.001 ms , dispatch latency = 0.001 ms 인 경우 아무런 작업을 처리하지 못하고 프로세스를 Context Switch
  
  。 Time quantum의 사이즈가 클 경우 Context Switch가 거의 발생하지않아 비선점형인 FCFS와 동일한 특성을 지니게됨
  
  ▶ Time Quantum Size에 따른 turnaround time 변화

  • Time Quantum ( = Time Slice )
    。CPU 스케쥴링에서 각 프로세스에게 할당된 시간단위
    ▶ 10 ~ 100 ms의 매우 작은 시간 단위로 설정

• 
  
  
• RR 스케쥴링 원리
  。CPU Burst의 time quantum 대비 대소여부에 따라 2가지 case가 존재
  
  。선점형 프로세스이므로 CPU 회수 발생

  • 프로세스의 CPU Burst가 1 time quantum보다 작은 경우
    。CPU Burst 후 프로세스는 CPU를 자발적으로 해제 ( release the CPU voluntarily )
    ex ) 1 time quantum = 10 ms 일때 CPU Burst = 5 ms
    
    
  • 프로세스의 CPU Burst가 1 time quantum를 초과한 경우
    。timer가 OS에게 인터럽트를 전송 및 Context Switch를 실행
    ▶ CPU 회수된 프로세스는 Ready Queue 꼬리로 전달됨

• 
  
  
• RR 원리 : 사전설정
  각 프로세스의 Burst time(ms)
  $P_1:24$ , $P_2:3$ , $P_3:3$
  
  time quantum = 4ms
  
  
• RR 스케쥴로 Waiting time 계산

  • Circular Queue로 $P1$ → $P2$ → $P3$ 순으로 들어온 경우
    
    。$P_1$은 4ms 경과 후 $P_2$로 Context Switching 및 Ready Queue의 꼬리로 전달
    
    
  • Waiting time
    $P_1 : 10-4=6$ , $P_2=4$ , $P_3=7$
    
    Average Waiting time = $\frac{17}{3}=5.66$

MLQ 스케쥴링 ( Multi-Level Queue )

。Ready Queue내 프로세스들을 priority가 배정된 각 범주의 Ready Queue로 구분 및 priority에 따라 스케쥴링 수행

。각 Ready Queue는 독자적인 스케쥴링 알고리즘을 보유.

。각 범주 ( real-time , system , interactive , batch ,... )의 Ready Queue로 프로세스를 분할 후 priority의 순서대로 Ready Queue에 소속된 프로세스를 우선처리

• MLQ 스케쥴링 문제점
  。가장 높은 priority의 Ready Queue에 소속된 프로세스 수가 압도적으로 많아 그보다 낮은 priority의 Ready Queue에 소속된 프로세스가 Execute 되지 않을 수 있음
  ex ) 많은 작업량의 높은 priority의 CPU Bound에 의해 적은 작업량의 I/O Bound는 실행되지못함.
  ▶ MLFQ 스케쥴링 사용

MLFQ 스케쥴링 ( Multi-Level Feedback Queue )
。실제 OS에서 가장 자주 사용되는 스케쥴링 방식

。여러개의 우선순위가 다른 Ready Queue를 사용하여 하나의 Ready Queue에서 처리못한 프로세스를 우선순위가 더 높은 Ready Queue로 feedback하여 우선순위를 높여준다.

。MLQ 스케쥴링의 낮은 priority의 Ready Queue에 소속된 프로세스는 실행되지 않는 단점을 개선
▶ RR의 개념을 차용

• MLFQ 원리
  。큰 작업량의 높은 우선순위의 프로세스를 time quantum만큼 작업함으로써 다른 낮은 우선순위의 프로세스에 대한 Execute 기회를 제공
  ▶ 프로세스는 작업을 거칠때마다 할당된 time quantum이 증가하면서 점점 많은 CPU burst time을 할당받으면서 동시에 우선순위가 높아짐
  

  • 초기 큰 작업량을 보유한 높은 priority의 프로세스가 들어간 경우 8 ms 만큼 CPU를 배정 후 Context Switch를 발생시켜 Wait Queue로 전달
    。 이후 다음 priority의 프로세스에 CPU를 배정
    
    。Wait Queue로 전달된 프로세스는 더 높은 우선순위의 Ready Queue로 전달
    
    
  • 전달된 Wait Queue에서 Ready Queue를 통해 Running 시 다음번에 16 ms만큼 증가된 cpu burst time 동안 CPU를 배정.
    
    
  • 전달된 Wait Queue에서 Ready Queue를 통해 Running 시 작업이 완료될 때까지 CPU를 배정

스레드 스케쥴링 ( Thread Scheduling )
。대부분의 OS의 CPU Scheduling은 프로세스 보다는 Kernel Thread를 대상으로 스케쥴링을 지원
▶ 위 스케쥴링 알고리즘 개념을 프로세스에서 스레드로 대입하여 이해하기.

。User Thread는 User Level Library에 의해 생성 및 관리되므로 OS에 의해 인식되지않아 CPU Scheduler에 의한 스케쥴링은 적용되지않으나, Kernel Thread와 매핑하여 간접적으로 상호작용

실시간 운영체제( Real-time Operating System )의 스케쥴링

。Soft Realtime 또는 Hard Realtime의 스케쥴링은 Priority-base 스케쥴링 사용

• 실시간 ( Real-time ) 종류
  。실시간 : 정해진 시간 내 작업을 완료

  • Soft Realtime
    。critical real-time process가 스케쥴대로 완료될 보장은 없지만 non-critical real-time process보다는 우선 Execute될 보장이 있는 방식
    
    ex ) 전화에서 RF신호가 0.1초당 1MB 씩 처리할때, RF신호가 0.1001초 경과해서 처리해도 괜찮은 경우
    
    
  • Hard Realtime
    。task가 반드시 deadline 이내에 완료되야하는 방식