CPU 스케줄링 알고리즘: FIFO, SJF, RR

 

FIFO (First In First Out)

: CPU 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식

• 먼저 들어온 작업이 먼저 나가는 방식
• 먼저 들어온 프로세스가 완전히 끝나야만, 다음 프로세스를 실행할 수 있음

 

 

 

FIFO의 장단점

장점: 단순하고 직관적임

 

단점

1. 앞에 있는 프로세스가 끝나야만 이후의 프로세스를 실행할 수 있기 때문에
   → 실행 시간이 짧지만 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함
   • ex) 마트 계산대 줄에서 껌 1개 산 손님이 먼저 온 30만원어치 산 손님의 계산을 기다려야 함
2. I/O 작업이 있다면, CPU는 I/O 작업이 끝날 때까지 쉬고 있기 때문에 CPU 사용률이 감소함
   • ex) 마트 계산대에서 계산원(CPU)이 손님에게 돈을 받으려고 하는데, 손님이 지갑에서 돈을 뒤져서 현금을 꺼냄(= I/O 작업). 계산원은 손님이 돈을 다 꺼내서 계산할 때까지 멍 때리며 기다림

• FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능 차이가 심해서 현대 운영체제에선 잘 쓰이지 않음
  • 일괄 처리 시스템에 쓰임

 

 

 

---

SJF (Shortest Job First)

: Burst Time이 짧은 프로세스 먼저 실행하는 방식

• 개요
  • FIFO 알고리즘에선 Burst Time이 짧은게 먼저 실행되면, 평균 대기 시간이 짧아짐
    → 그럼 Burst Time이 짧은 프로세스를 먼저 실행하는 알고리즘을 만들자!
    ⇒ SJF 알고리즘
• 이론적으로 FIFO 보다 성능이 더 좋음
  • But, 실제로 구현하려니 문제가 생김 → 그래서 SJF는 사용되지 않음 (실패한 알고리즘)

 

 

 

SJF의 문제점

1. Burst Time 예측이 어려움
   
   • 어떤 브라우저가 얼마나 실행될지 예측이 어려움
     • ex) 인터넷 브라우저에서 뮤직 플레이어 실행
       → 브라우저는 날씨만 확인하고 끌 수도 있고, 쇼핑하느라 계속 켜둘 수도 있음
       ⇒ 실행 시간 예측 불가능
       

       

2. Burst Time이 긴 프로세스는 실행이 밀림
   • SJF는 Burst Time이 짧은 프로세스 먼저 실행됨 →  Burst Time이 긴 프로세스는 뒤로 밀려남
     ⇒ 실행 중 Burst Time이 짧은 프로세스가 중간에 계속 들어오면 → Burst Time이 긴 프로세스는 계속 뒤로 밀려남
     ⇒ 불공평함

 

 

 

---

RR (Round Robin)

: 한 프로세스에게 일정 시간만큼 CPU를 할당하고, 할당 시간이 지나면 이 프로세스의 CPU를 빼앗아 큐의 가장 뒷부분으로 보낸 뒤 다른 프로세스에게 일정 시간 CPU를 할당하는 방법

• FIFO 알고리즘의 단점을 해결하고자 만들어짐
  
  • FIFO 알고리즘의 단점: 먼저 들어온 프로세스가 전부 끝나야 다음 프로세스가 실행됨
    

    

• 타임 슬라이스(Time Slice) & 타임 퀀텀(Time Quantum) : 프로세스에게 할당하는 일정 시간

 

 

 

예시 - 타임 슬라이스가 10초인 시스템의 평균 대기 시간

• 타임 슬라이스(작업 시간): 10초
• 이 프로세스들은 동시에 큐에 들어왔고, 실행 순서는 P1 → P2 → P3 순서임
• 각 프로세스의 Burst Time
  
  • P1: 25초
  • P2: 4초
  • P3: 10초

 

 

실행 순서 및 대기 시간

1. P1의 Burst Time: 25초
   
   • P1은 큐에 들어오자마자 실행되기 때문에 대기 시간: 0초
   • P1은 타임 슬라이스 10초만큼 실행하다가 끊고 P2에게 CPU를 뺏김 + P1의 남은 작업은 큐의 가장 뒤로 이동함
   • 실행 후 남은 작업: 15초
2. P2의 Burst Time: 4초
   
   • P2는 P1이 실행하는 10초를 기다렸기 때문에 대기 시간: 10초
   • P2는 Burst Time이 4초이기 때문에 4초가 지나면 P3에게 양보하고 작업을 마침
   • 실행 완료 (Burst Time이 4초라 타임 슬라이스 다 안 씀)
3. P3의 Burst Time: 10초
   
   • P3는 P1과 P2의 실행이 완료될 때까지 기다렸기 때문에 대기 시간: 14초
   • P3는 Burst Time인 10초 동안 실행하고 작업을 마침
   • 실행 완료 (Burst Time이 10초)
4. P1의 남은 Burst Time: 15초가 다시 실행
   
   • P1은 P2와 P3의 실행이 완료될 때까지 기다렸기 때문에 대기 시간: 14초
   • 현재 P1은 Burst Time이 15초로 타임 슬라이스보다 크기 때문에 타임 슬라이스 값인 10초만 실행함 + P1의 남은 작업은 큐의 마지막으로 이동함(5초 남은 상태)
   • 실행 후 남은 작업: 5초
5. P1의 남은 Burst Time: 5초가 다시 실행
   • 대기 중인 프로세스가 없어서 바로 실행되기 때문에 대기 시간: 0초
   • 실행 완료

 

 

평균 대기 시간 계산

RR의 평균 대기 시간 : (0 + 10 + 14 + 14 + 0) / 3 = 12.67초

• RR 알고리즘 평균 대기 시간: 12.67초
• FIFO 알고리즘 평균 대기 시간: 18초
• 이 상황에서는 RR의 평균 대기 시간이 더 짧지만, 다른 상황에서는 FIFO 알고리즘과 RR 알고리즘의 평균 대기 시간이 비슷할 수도 있음→ 평균 대기 시간이 비슷하다면, RR 알고리즘이 더 비효율적인 방식임(컨텍스트 스위칭 오버헤드 때문)

 

 

 

RR 알고리즘의 특징

• RR 알고리즘은 컨텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가됨
• RR 알고리즘의 성능은 타임 슬라이스 값에 따라 크게 달라짐
  
  • 타임 슬라이스가 큰 경우: 타임 슬라이스가 무한대일 경우
    
    • 먼저 들어온 프로세스의 작업이 완료될 때까지 실행하니 FIFO 알고리즘이 되어버림
      • ex) 웹 브라우저와 뮤직 플레이어를 실행시키면
        → 웹 브라우저와 뮤직 플레이어를 5초씩 번갈아가며 끊어 실행하니 프로그램이 자주 끊김
  • 타임 슬라이스가 작은 경우: 타임 슬라이스가 1ms일 경우
    
    • 프로세스들이 동시에 동작하는 것처럼 느껴짐
      • ex) 웹 브라우저와 뮤직 플레이어를 실행시키면
        → 웹 브라우저와 뮤직 플레이어가 동시에 동작하는 것처럼 느껴짐
    • 타임 슬라이스를 너무 작게 설정할 경우
      • 컨텍스트 스위칭이 너무 자주 일어남
      • 타임 슬라이스에서 실행되는 프로세스의 처리량 < 컨텍스트 스위칭을 처리하는 양이 훨씬 커짐
        → 오버헤드가 너무 큰 상황 발생

 

 

 

최적의 타임 슬라이스를 설정하는 방법

• 사용자가 느끼기에 여러 프로세스가 버벅거리지 않고 동시에 실행되는 것처럼 느껴지게 해야 함
• 오버헤드가 너무 크지 않는 값으로 해야 함
• Windows는 타임 슬라이스가 20ms, Unix는 100ms로 굉장히 짧음