햄버거집 '피크타임'으로 알아보는 CPU 스케줄링

이번 글에서는 햄버거집의 피크타임을 통해 CPU 스케줄링의 다양한 개념을 쉽게 이해해보려 합니다. 예를 들어, 평일 점심시간 많은 손님들이 햄버거를 주문할 때 주방은 전쟁터처럼 바쁘죠. 주방의 조리사들은 각 주문을 얼마나 효율적으로 처리할 수 있는지에 대한 고민을 하게 되는데요, 이것을 운영체제에서는 CPU 스케줄링이라고 합니다.

CPU 스케줄링이란?

제한된 자원 내에서 가장 좋은 퍼포먼스를 올릴 수 있는 방법을 찾는 과정

 

스케줄링의 종류

---

선점형 vs. 비선점형 스케줄링

• 선점형 스케줄링: 주방 매니저가 조리사를 중간에 멈추고 더 급한 주문 먼저 조리하게 하는 것과 같습니다. 예를 들어 유명한 블로거가 방문한다거나, 사장님이 최대한 빨리 조리를 해달라고 하면 하면 조리사는 현재 주문이 완료되지 않아도 최대한 빠르게 해당 주문을 처리해야겠죠.
• 비선점형 스케줄링: 조리사가 조리중인 햄버거를 완성한 후에 다음 주문을 시작하는 방식입니다. 새로 들어온 주문이 아무리 급해도 현재 주문을 먼저 처리합니다.

FCFS (First-Come, First-Served) 스케줄링

• FCFS 알고리즘: Queue에서의 FIFO랑같은 개념으로, 주문을 받은 순서대로 조리합니다. 합리적인 방법처럼 보이지만, 조리중 학교에서 햄버거 세트 200개처럼 단체 주문이 들어온다면, 그 이후에 주문한 손님은 200개가 조리되는 시간동안 기다려야하는 문제점이 발생합니다.
  
  사용 빈도: 이러한 이유로 실제로는 많이 사용되지 않습니다. 작은 수량을 주문한 사람이 이전의 모든 주문이 처리되기까지 기다려야 하므로 시간적인 지연이 발생합니다.

SJF (Shortest Job First) 스케줄링

• SJF 알고리즘: 조리 시간이 가장 짧은 햄버거부터 만들어서 대기 시간을 줄입니다. 
  
  사용 빈도: 이론적으로 효율적이지만, 당일에 단체주문이 올지 안올지 모르는 것 처럼 주문의 정확한 준비 시간을 예측하기 어려워 구현이 어렵습니다.

그러면 어떤 알고리즘이 주로 사용되죠?

• 라운드 로빈 스케줄링: 각 주문에 고정된 준비 시간을 할당합니다(time quantum). 정해진 조리 시간이 다 되면 다음 주문으로 넘어가 모든 주문이 공평하게 조리되도록 합니다.
  • 장점: 작업당 공평한 시간 분배, 반응 시간이 중요한 시스템에 적합합니다.
  • 단점: 타임 퀀텀이 너무 짧으면 주문 전환(컨텍스트 스위칭)에 많은 시간과 리소스가 소요되고, 해당 시간이 너무 길어지면 FCFS랑 비교했을 때 속도적인 메리트가 크지 않습니다.
• 우선순위 스케줄링: 긴급 주문이나 대량 주문에 높은 우선순위를 부여합니다.
  • 단점: 우선순위가 낮다면 오랫동안 기다려야 할 수 있습니다.(Starvation/Indefinite Blocking)
  • 해결 방법: 에이징 기법을 사용해 오래 대기한 주문의 우선순위를 점차 높이거나, 라운드 로빈과 혼합하여 공정성을 보장할 수 있습니다.
    
    에이징 기법 - 준비 큐에 오래 머무는 프로세스의 우선순위를 점진적으로 높여주는 방식

고급 스케줄링 기법

• 다단계 큐: 주방의 매니저는 주문을 종류별로 나누어 여러 개의 조리대(Queue)를 두어 작업을 분배합니다. 각 조리대에서는 무조건 배정된 조리만 진행하여 분업을 합니다. 햄버거, 사이드 메뉴, 음료수 주문을 각각 다른 큐로 관리하는 것이죠. 햄버거 큐에는 모든 햄버거 주문이 모여 있고, 사이드 메뉴 큐에는 감자튀김이나 샐러드 조리를 진행합니다. 음료수 큐도 마찬가지구요. 이런 식으로 큐를 나누면 각 조리사가 어떤 종류의 주문을 처리해야 할지 명확해집니다. 하지만 이러한 방식은 몇 가지 단점을 가지고 있는데요, 예를 들자면 햄버거 큐에 큰 주문이 밀렸을 때 사이드 메뉴 큐와 음료수 큐에서 작업이 이뤄지지 않는다면 전체 주방의 효율성이 떨어지는 상황이 발생할 수 있습니다. 즉 유연성이 부족해 특정 큐에 집중된 주문으로 인해 다른 큐가 대기하게 되는 문제가 생기는 것이죠.
  
  
• 다단계 피드백 큐: 반면 다단계 피드백 큐는 훨씬 더 동적입니다. 이 시스템에서는 각 주문의 상태나 처리 시간에 따라 주문이 다른 큐로 이동할 수 있습니다. 예를 들어 100개의 햄버거 주문이 들어온 경우 매니저는 햄버거 큐에서 50개를 처리하고 임시로 사이드 메뉴 큐에서 25개, 음료수 큐에서 25개를 작업하게 할 수 있습니다. 이렇게 하면 주방의 작업 흐름이 원활해져 대기 시간이 줄어들게 됩니다. 하지만 다단계 피드백 큐에도 몇 가지 단점이 존재합니다. 우선, 관리와 구현이 복잡할 수 있으며, 주문의 상태에 따라 큐를 이동시키는 규칙을 잘못 관리할 경우 혼란을 초래할 수 있습니다. 또한, 여러 큐 간에 주문이 이동하면서 우선순위가 애매해질 수 있어 고객의 대기 시간이 늘어날 위험이 있습니다. 더불어 각 큐에서 작업을 처리하는 동안 자원의 할당이 비효율적으로 이루어질 수 있고 특정 큐가 과부하에 걸리면 전체 시스템의 성능이 저하될 수 있습니다. 마지막으로 매니저(CPU)가 주문의 상태를 지속적으로 모니터링하고 조정해야 하므로 관리자의 업무 부담이 커질 수 있습니다.

실시간 스케줄링

실시간 스케줄링은 특히 시간에 민감한 작업을 처리할 때 중요한 역할을 합니다. 한 햄버거 가게에서는 점심시간에 많은 주문이 들어오고 그 중 일부는 즉시 제공되어야 하는 긴급한 주문이 있을 수 있는 것처럼 말이죠.

• Rate Monotonic 스케줄링: 고정된 우선순위에 따라 주문을 스케줄링합니다. 더 짧고 자주 일어나야 하는 작업일수록 높은 우선순위를 갖습니다.
  예를 들어 '햄버거', '치킨너겟', '치즈스틱' 세 가지 메뉴가 있을 때 햄버거는 5분마다 주문이 들어오고, 치킨너겟은 10분마다, 치즈스틱은 15분에 한번정도 주문이 들어옵니다. 이런 경우 기본 햄버거가 가장 자주 주문되기 때문에 가장 높은 우선순위를 부여받습니다. 조리사는 기본 햄버거 주문을 먼저 준비한 후, 치킨너겟, 마지막으로 치즈스틱을 조리합니다. Rate Monotonic 스케줄링은 짧고 자주 들어오는 주문에 높은 우선순위를 두는 것와 비슷합니다.
• Earliest Deadline First 스케줄링: 마감 기한에 따라 주문의 우선순위를 결정합니다. 마감 기한이 빠를수록 우선순위가 높아집니다. 이론적으로는 효율적이지만, 잦은 컨텍스트 스위칭으로 인해 리소스 측면에서 비효율적일 수 있습니다.
  점심시간에 특정 시간에 맞춰 배달해달라는 주문 두건이 들어왔을 때, 한 고객이 12시 10분까지 햄버거를 배달받고 싶어하고 다른 고객은 12시 5분까지 치킨버거을 받고싶은 상황입니다. 이때 마감 기한이 더 빠른 치킨버거 주문을 우선적으로 처리하는 것이 EDF 스케줄링입니다. 이렇게 마감 기한에 따라 우선순위를 정하면 모든 고객의 요구를 충족시킬 수 있지만, 잦은 주문 전환으로 인해 조리사에게는 부담이 될 수 있는데요. 조리사가 계속해서 주문을 바꾸면 리소스의 효율성이 떨어질 수 있기 때문입니다.

---

퀴즈

Q1. '맥도날드'에서는 주문이 들어온 순서대로 햄버거를 만듭니다. 이는 어떤 스케줄링 알고리즘과 유사한가요?
a) SJF (Shortest Job First)
b) 라운드 로빈
c) FCFS (First-Come, First-Served)
d) 우선순위 스케줄링

Q2. '버거킹'에서는 조리 시간이 짧은 메뉴부터 만듭니다. 이는 어떤 스케줄링 알고리즘과 유사한가요?
a) FCFS (First-Come, First-Served)
b) SJF (Shortest Job First)
c) 라운드 로빈
d) 다단계 큐

Q3. '롯데리아'에서는 각 주문에 3분씩 할당하여 순서대로 조리합니다. 3분이 지나면 다음 주문으로 넘어갑니다. 이는 어떤 스케줄링 알고리즘과 유사한가요?
a) 우선순위 스케줄링
b) FCFS (First-Come, First-Served)
c) SJF (Shortest Job First)
d) 라운드 로빈

Q4. 'KFC'에서는 VIP 고객의 주문을 우선적으로 처리합니다. 이는 어떤 스케줄링 알고리즘과 유사한가요?
a) 우선순위 스케줄링
b) FCFS (First-Come, First-Served)
c) SJF (Shortest Job First)
d) 다단계 피드백 큐

Q5. '맘스터치'에서는 주문을 햄버거, 사이드 메뉴, 음료로 나누어 각각 다른 조리사가 담당합니다. 이는 어떤 스케줄링 기법과 유사한가요?
a) 라운드 로빈
b) 우선순위 스케줄링
c) 다단계 큐
d) FCFS (First-Come, First-Served)

---

출처

https://github.com/jeonyeohun/Getting-Ready-For-Interview/blob/main/OperatingSystem/03_Scheduling.md