스케줄링 알고리즘 Scheduling algorithm

출처 : https://www.guru99.com/cpu-scheduling-algorithms.html

 

스케줄링 알고리즘 (Scheduling algorithm)

• 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정

 

CPU Scheduling 문제점의 Solution

• FCFS : First come, Fist Seerved
• SJF : Shortest Job First (SRTF : Shortest Remaning Time First)
• RR : Round Robin, Time Sharing
• Priority Based
  • MLQ : Multi Level Queue
  • MLFQ : Multi Level Feedback Queue

 

FCFS

• 가장 간단, 먼저 요청 -> 먼저 할당
• CPU burst time 에 따라서 Waiting time이 달라짐
• Nonpreemptive
• Convoy Effect : 하나의 긴 프로세스를 처리하기 위해 뒤의 짧은 프로세스들이 오래 기다려야 하는 효과 -> 정렬시간에 따라 waiting time이 다를 수 있음

Convoy Effect : https://www.geeksforgeeks.org/convoy-effect-operating-systems/

 

SJF

• Shortest Job First -> CPU Burst Time을 알기 어렵기 때문에 이론적 사용, 실제 사용 X
• 처리 시간이 긴 프로세스 앞에 시간이 짧은 프로세스를 놓으면
  • waiting time 이 줄어들어 waiting time 측면에서 최적
• 정확한 CPU Burst Time을 얻을 수 없기 때문에 근사적 계산
  • 예측 방법
    • 과거에 많이 쓰면 현재도 많이 쓸 것이다 -> 지수적 평균
    • Tn+1 = ATn + (1 - A)Tn
• 선점일 수도 있고, 비선점일 수도 있음
• 실행 중에도 짧은 게 들어오면 Context Switching

 

SRTF

• Shortest Remaining Time First -> Preemptive SJF

 

Round-Robin Scheduling

• Preemptive FCFS with a time quantum
• 보통 시간 할당량 (time quantum)은 10 ~ 100 ms
• Readyqueue -> circular queue
• Readyqueue를 circular로 돌면서 시간 단위로 allocate 한다.
• waiting time은 길지만, 다른 알고리즘과 혼용하기 때문에 필수적이다.
• time quantum에 의존적

 

Priority-base Scheduling

• 우선순위가 높은 순서로 CPU에 allocate
• 우선순위가 Equal이면 FCFS
• SJF는 CPU Burst Time을 기준으로 하는 Priority-base Scheduling
• 무한대로 대기하는 프로세스가 발생할 수 있다. (기아 상태)
  • 이를 회피하기 위해 aging이라는 개념을 사용한다. 대기가 길면, priority가 증가

 

Combining RR and Priority

• 만약 Priority가 같은 것 -> RR

 

Multi Level Queue

• Priority-base가 단일 큐라면, multi level은 기아 상태를 해결하기 위해 priority에 따른 각각의 ready queue를 만들어 배치한다.
• RR 과 함께 사용할 때에도 효과적이다.
• 각 큐는 다른 알고리즘을 사용할 수 있다.
• 각 큐는 CPU 사용량이 다르다
  • foreground queue 는 80%, background queue 20%

 

Multi Level Feedback Queue

• Multi Level Queue의 경우 프로세스가 다른 Queue에 이동하지 않는 반면, Multi Level Feedback Queue는 CPU Burst 성격에 따라 이동이 가능하다.
• 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동시키기 위함이다.
• 포그라운드(대화형)프로세스들은 높은 우선순위를 갖는다. (대체로 CPU Burst Time이 짧다.)
• 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. (기아 상태 예방)