10. 스케줄링 알고리즘: Chapter 5. CPU Scheduling (Part 2)

1. First-Come, First-Served(FCFS)

FCFS는 먼저 온 프로세스가 먼저 CPU를 점유하는 방식이다. 이는 매우 단순하고 많이 사용하는 방법이지만, 모든 부분에서 효율적인 것은 아니다.

Process	Burst Time(msec)
P1	24
P2	3
P3	3

• Average Waiting Time = (0+24+27) / 3 = 17msec
• Average Turn-arounnd Time = (24 + 27 + 30) / 3 = 27msec

 P3, P2, P1 순서로 도착한다면

• Average Waiting Time = (6+3+0) / 3 = 3msec
• Average Turn-around Time = (3+6+30) / 3 = 13msec

Note :

1. FCFS에서 Averate Waiting Time

   일반적으로 최소가 아니고(not minimal) 상당히 다를 수(vary substantially) 있다.

1. Preemptive or non-preemptive?

   프로세스가 종료되기 전에 다른 프로세스가 선점하지 않기 때문에 Non-preemptive

2. 호송 효과(Convoy Effect)

   모든 다른 프로세스들이 하나의 긴 프로세스가 종료되어 CPU를 양도하기를 기다리는 현상

2. Shortest-Job-First(SJF)

• Shortest-Job-First = Shortest-next-CPU-burst-first
• CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식 → (프로세스 종료 시 다음 프로세스의 CPU burst time이 가장 작은 것에 CPU 할당)
  
• 두 개 이상의 프로세스의 점유 시간이 같다면 FCFS 방식으로 처리

Process	Burst Time(msec)
P1	6
P2	8
P3	7
P4	3

• Average Waiting Time = (3+16+9+0) / 4=7msec
• Average Turn-around Time = (9+24+16+3) / 4 = 13msec

Note :

1. 최소 평균 대기 시간을 위해 최적화 된 스케줄링 알고리즘

   CPU burst time이 작은 프로세스에 CPU를 먼저 할당해줌으로서 평균 대기 시간을 최소화 할 수 있다.

2. 비현실적인 방법

   next-CPU-burst를 알 수 있는 방법이 없다.

   → 측정된 과거의 CPU 소요시간의 지수 평균(Exponential Average)으로 다음 CPU 소요시간 예측

   $수식 : τ_{n+1} = ατ_n + (1 - α)τ_n$
   • 예시

   

3. preemptive 스케줄링 & non-preemptive 스케줄 모두 가능

   **→ preemptive 스케줄링이 더 효율적** 

   
   

(Shortest-Remaining-Time-First : Preemptive SJF Scheduling)

Process	Arrival Time	Burst Time(msec)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

non-preemptive SJF

• Average Waiting Time = (0+7+15+9) / 4 = 7.75msec
• Average Turn-around Time = (8+11+24+14) / 4 = 14.25msec

preemptive SJF (SRTF)

• Average Waiting Time = (9+0+15+2) / 4 = 6.5msec
• Average Turn-around Time = (17+4+24+7) / 4 = 13msec

3. Round-Robin(RR)

• 시분할 선점 FCFS 스케줄링 (preemptive FCFS with a time quantum)

  → Time Quantum( or time slice) : 아주 작은 시간 단위

  보통 10 ~ 100msec
  

• Ready Queue는 Circular Queue의 형태로 구현된다.

• 스케줄러가 Ready Queue를 돌며 CPU에게 각각의 프로세스를 1 time quantum만큼 할당한다.

  → “두 가지” 상황이 발생 가능

  1. 프로세스가 one time quantum 미만 CPU burst를 가지는 경우

     1. 프로세스가 자율적으로 반납

        → “preemptive!”

     2. 스케줄러가 Ready Queue의 다음 프로세스 진행

  2. 프로세스가 one time quantum 초과 CPU burst를 가지는 경우

     1. 타이머 종료 → OS가 interrupt 발생

     2. Context switch 실행

     3. 프로세스 Ready Queue의 맨 뒤에 위치

• Time Quantum = 4msec

Process	Burst Time(msec)
P1	24
P2	3
P3	3

• Average Waiting Time = (6+4+7) / 3 = 5.66msec
• Average Turn-around Time = (30+7+10) / 3 = 15.66msec

Note :

1. Average Waiting Time이 종종 길다.

2. Preemptive 스케줄링 알고리즘

   → 프로세스의 Burst Time이 one quantum time을 초과하는 경우 해당 프로세스는 Ready Queue로 돌아간다.

3. 성능은 시간 단위의 크기에 따라 결정된다.

• 시간 단위(Quantum)의 크기 조절의 필요성
  • 문제점 : Quantum이 작아질 때 context switch 발생 → dispatch latency 발생(성능 저하)
  • 해결 방안

    1. context switch의 횟수가 적을수록 좋음

    2. quantum의 크기는 process time에 맞추어 적당히 조절

       →quantum이 무한대로 커지면 FCFS와 같다.

• 시간 단위에 따라 달라지는 반환 시간
  

4. Priority-base Scheduling

• 우선 순위가 가장 높은 프로세스에 CPU를 할당하는 방식
  • 각 프로세스에 우선 순위 존재
  • 우선 순위가 같은 프로세스 → FCFS 스케줄링
• SJF도 Priority-base Scheduling → ∵ next Cpu Burst의 역순 = 높은 우선순위

Process	Burst Time(msec)	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

표에서 우선순위 값이 가장 낮은 순서대로 수행한 모습을 간트 차트로 나타내었다.

• Average Waiting Time = (6+0+16+18+1) = 8.2msec
• Average Turn-around Time = (16+1+18+19+6) = 12msec

1. preemptive & non-preemptive 스케줄링 모두 가능

   • preemptive : SRTF
   • non-preemptive : SJF

2. 우선순위를 정하는 방법은 크게 내부적인 요소와 외부적인 요소 두 가지로 나뉜다.

   • Internal: time limit, memory requirement, I/O to CPU burst(I/O작업은 길고, CPU 작업은 짧은 프로세스 우선) 등
   • External: amount of funds being paid, political factors 등

3. 기아(Starvation) 문제 = 무한 대기(Indefinite Blocking)

   • Blocked process : Ready Queue에 있지만 CPU를 기다리는 상
   • 우선 순위가 낮은 일부 프로세스의 경우 무기한 대기 가능성 존재

   → 에이징(Aging) : 오랫동안 대기하는 프로세스의 우선순위를 점차 높여서 기아(Starvation)문제 해결

3, 4) Combine Round-Robin + Priority base scheduling

• 우선순위가 높은 process 실행
• 우선순위가 같다면 RR(round-robin) 스케줄링을 한다.

5. Multilevel Queue(MLQ)

• 우선순위에 따라 Ready Queue를 여러 개 사용

우선순위 1 : real-time process : 실시간 처리 프로세스

우선순위 2 : system process : O/S 커널 수준의 프로세스

우선순위 3 : Interactive process : 유저 인터페이스를 담당하는 프로세스

우선순위 4 : Batch process : 일정량을 한 번에 처리하는 프로세스 ( Ex) 컴파일러)

Note:

1. Preemptive Scheduling Algorithm
2. Priority-base Scheduling과 마찬가지로 기아문제가 존재함
   
   

6. Multilevel Feedback Queue (MLFQ)

• 우선순위에 따라 나뉜 Ready Queue에 우선순위를 맞춰 시간 할당
• 모든 프로세스가 첫 번째 Ready Queue에 놓인 후 수행
• 만약 할당된 시간 안에 수행 x ?
  • 우선순위 하락
  • 다음 큐로 이동
• 우선순위가 낮은 큐에 Quantum time을 크게 할당 → 우선순위 낮은 프로세스에 CPU를 오랫동안 할당

Thread Scheduling

• 대부분의 최신 O/S → 커널 스레드(Kernel threads) 스케줄링
• 유저 스레드(User threads)는 라이브러리에 의해 관리된다.
  • 커널 스레드가 인식하지 못함 → 커널 스레드와 매핑만 해주면 된다.

Scheduling in Real-Time O/S

• Real-Time O/S : 제한된 시간 내에 원하는 작업을 처리하는 것을 보장하는 운영 체제

1. Soft Real-time

   • 작업이 데드라인을 초과하더라도 중대한 문제가 발생하지 않는다. ex) 전화기 : 통화 중 음성 끊김

2. Hard Real-time

   • 작업이 데드라인 안에 실행되어야 한다. ex) 우주선 : 조금만 잘못 계산해도 궤도가 달라짐
   
   

참고 :

Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.

주니온TV@Youtube: 자세히 보면 유익한 코딩 채널