[OS] CPU Scheduling Algorithm

FCFS (First-Come First-Served)

• 먼저 온 순서대로 처리
• nonpreemptive(비선점형) scheduling 방식에 해당됨
• 그다지 효율적이지는 않음
  • CPU를 오래 쓰는 프로그램이 CPU를 잡아버리면 interactive한 job들이 계속 대기해야 함

Gantt Chart

• CPU를 짧게 쓰는 프로그램들이 먼저 도착했을 경우에는 average waiting time이 매우 짧아짐
  
  
• 즉, 도착한 순서에 따라서 큰 영향을 받게 됨
  • Convoy effect : 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 지나치게 오래 기다려야 하는 현상

---

SJF (Shortest-Job-First)

• CPU를 짧게 쓰는(=CPU burst가 짧은) 프로그램에게 CPU를 먼저 주는 방식
• average waiting time을 최소화하는 알고리즘
  • 그 중에서도 SRTF가 이에 해당함

Nonpreemptive한 방식

• 현재 CPU를 기다리는 프로세스 중 가장 짧은 프로세스에게 CPU를 주고, 더 짧은 프로세스가 도착하더라도 일단 배정된 프로세스가 CPU를 사용하도록 보장해주는 방식
• 한 프로세스가 CPU를 다 쓰고 나가는 시점에 스케줄링을 할지 말지를 결정

Preemptive한 방식 (=SRTF)

• SRTF : Shortest-Remaining-Time-First

• CPU를 줬다고 하더라도, 더 짧은 프로세스가 도착하면 CPU를 뺏어서 더 짧은 프로세스에게 할당하는 방식

• 이때 ‘더 짧은 프로세스’라 함은, 현재 CPU를 가지고 있는 프로세스의 남은 burst 길이 vs 새로운 프로세스의 전체 길이 를 비교해서 더 짧은 경우를 의미

• 새로운 프로세스가 도착하면 언제든지 스케줄링이 일어날 수 있음

Gantt Chart

• non-preemptive
  
• preemptive
  

문제점

• starvation
  • 극단적으로 CPU 사용시간이 짧은 job을 선호함 → CPU 사용시간이 긴 프로세스는 영원히 CPU를 받지 못할 수 있음
• CPU 사용시간을 미리 알 수 없음
  • branch, user input 등을 예측할 수 없음
  • 추정할 수는 있음
    • user interaction이 있는 경우 CPU burst가 짧음
    • 과거에 CPU를 사용한 흔적 등으로 예측
      • Exponential average
        • 최근 CPU 사용시간이 이전 값보다 더 큰 영향을 미침

---

Priority Scheduling

• 우선순위가 가장 높은 프로세스에게 CPU를 주는 방식
  • 일반적으로 우선순위는 integer로 표현
  • 높은 우선순위 = 작은 integer
• non-preemptive/preemptive 방식을 생각해볼 수 있음
• SJF도 priority scheduling의 일종이라고 볼 수 있음
  • priority = CPU 사용시간으로 정의한 priority scheduling 방식

aging 기법

• 특정 프로세스가 지나치게 차별받는 것을 막기 위한 방식; starvation problem의 해결책
• 오래 기다리면 우선순위를 높여주는 방식
  • 아무리 낮은 우선순위를 가지고 있더라도 시간이 지나면 우선순위가 높아질 것

---

Round Robin (RR)

• 현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링은 RR에 기반함
• CPU를 줄 때 할당시간(time quantum)을 세팅해서 주고, 할당시간이 끝나면 timer interrupt로 인해 CPU를 빼앗기고 ready queue에서 다시 줄을 서는 방식
• response time이 빠름
  • =CPU를 최초로 얻기까지 걸리는 시간이 빠름
  • 조금씩 CPU를 줬다뺏었다 하기 때문
  • ex) ready queue에 n개의 프로세스가 있고, 할당 시간이 q time unit일 경우, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음
• 누가 CPU를 오래 쓸지 모르는 상황에서 굳이 예측할 필요가 없이, CPU를 짧게 쓰는 프로세스가 빠르게 CPU를 쓰고 나갈 수 있음
• waiting time이 본인이 CPU를 사용하려는 시간에 비례함
  • CPU를 짧게 쓰는 프로세스는 한번 할당되었을 때 바로 끝낼 수 있으므로 한번만 기다리면 되고, 길게 쓰는 프로세스는 할당됐다가 뺏겼다..를 반복
• q time unit의 크기
  • q가 클 경우
    • ⇒ FCFS와 동일하게 동작
  • q가 작을 경우
    • ⇒ RR의 철학 상으로는 이상적이나, context switch 오버헤드가 커짐
• CPU 사용시간이 짧고 긴 프로세스들이 섞여있을 때 사용하기 좋은 알고리즘임
  • 동일한 CPU 사용시간을 가진 프로세스가 여러 개 있는 경우, 즉 100초짜리 프로세스 10개가 있을 경우 다같이 1000초가 되는 지점에 끝나게 됨
• context를 save하고, switch하는 것이 가능하기 때문에 가능한 알고리즘임

Gantt Chart

• 일반적으로 SJF보다 average turnaround time/waiting time은 길지만 response time은 더 짧음

---

Multilevel Queue

• 이전까지와는 달리 한줄서기가 아니라 여러 줄 서기 방식
  • ready queue를 여러 개로 분할
• 줄마다 우선순위가 다름
  • 출신에 따라서 줄을 서고, priority 순서대로 줄을 처리
• 해야하는 고민
  • 프로세스를 어느 줄에 집어넣을 것인가?
  • 무조건 우선순위가 높은 줄에 우선권을 주는가?
    • 우선순위가 낮은 줄은 starvation problem이 있지 않을까?
• 차별적인 방식

예시

• ready queue 분할 방식
  • foreground (interactive한 job)
  • background (batch - no human interaction job)
• 각 큐에 대한 스케줄링 알고리즘
  • foreground - RR
    • response time 줄이기 위함
  • background - FCFS
    • 어차피 CPU burst가 길기 때문에 context switch 오버헤드 줄이기 위함
• 큐에 대한 스케줄링
  • Fixed priority scheduling 사용 시,
    • foreground 모두 처리 후 background 처리
    • 이 경우 starvation이 발생할 수 있음
  • time slice 방식 사용 시,
    • 각 queue에 CPU time을 적절한 비율로 할당하는 방식
    • ex) 80%는 foreground, 20%는 background에 할당

Multilevel Feedback Queue

• 경우에 따라서 프로세스가 줄 간에 이동할 수 있는 스케줄링 방법
• multilevel feedback queue scheduler 정의에 필요한 파라미터
  • queue를 몇 개 둘 것인가?
  • 각 queue에서는 어떤 scheduling을 사용할 것인가?
  • process를 상위/하위 queue로 보내는 기준?
  • 프로세스가 들어갈 queue를 결정하는 기준?
• 일반적으로 적용하는 방식
  • 처음 들어오는 프로세스는 우선순위가 가장 높은 queue에 넣음
  • 우선순위가 높은 queue에는 RR time quantum을 짧게 줌
    • 아래 queue로 갈수록 RR time quantum을 길게 줌
    • 마지막 queue는 FCFS로 처리
  • 맨 위 queue에서 할당 시간이 끝나면 아래 queue로 강등 → 반복.. 하는 방식으로 처리
  • 이 경우, CPU burst가 짧은 job은 최상위 queue에서 처리를 끝내고 빠져나갈 수 있음
  • CPU burst가 길 경우 점점 아래 queue로 이동, 할당 시간은 더 받게 되지만 queue간의 우선순위에서 밀리게 됨
  • CPU 사용시간이 짧은 job에게 우선순위를 크게 주는 방식

---

특이케이스에서의 CPU Scheduling

Multiple-Processor Scheduling

• CPU가 여러 개 있는 경우의 CPU Scheduling 방식
• Homogeneous Processor인 경우
  • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가도록 함
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 다른 방식으로 해결해야 함
    • ex) 미용실 손님에게 전담 선생님이 있는 경우
• Load Sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 한 줄 queue가 아닌 각각의 프로세서에 별개의 queue를 두는 방식을 사용할 수 있음
    • ex) 마트에서 각 계산대에 줄서기
• Symmetric Multiprocessing (SMP)
  • 모든 CPU가 대등함
  • 각 프로세서가 알아서 스케줄링 결정
• Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고, 나머지 프로세서는 거기에 따름
  • ex) ElasticSearch의 master node와 같은 느낌인가?

Real-time scheduling

• deadline이 있는 job
  • 정해진 시간 안에 반드시 끝나야 하는 job
• hard real-time systems
  • 그때그때 스케줄링하기보다는, 미리 스케줄링을 해서 적재적소에 배치되도록 함
• soft real-time computing
  • soft real-time task는 일반 프로세스보다 높은 priority를 부여해서 처리

Thread scheduling

• Local Scheduling
  • User level thread에서 사용
    • 사용자 프로세스가 직접 thread를 관리하고, 운영체제는 thread의 존재를 모르는 경우
  • OS는 그냥 해당 프로세스에 CPU를 할당하는 것이고(thread의 존재를 모르니), 해당 프로세스 내에서 어떤 Thread에 CPU를 줄지는 해당 프로세스 내부에서 결정
• Global Scheduling
  • Kernel level thread에서 사용
    • 운영체제가 직접 thread를 관리
  • 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지를 결정

---

Algorithm Evaluation

• 어떤 알고리즘이 좋은가? 평가방법

Queueing models

• 이론적인 방식
• CPU에 도착하는 도착율(arrival rate)과 CPU가 처리를 끝낸 처리율(service rate)의 정보가 확률분포로 주어질 때, 여러 성능척도 결과를 계산
  • 얼마나 기다렸는지 등..

Implementation(구현) & Measurement(성능 측정)

• 실제 시스템에 구현해서 실행해보고 측정하는 방식

Simulation(모의 실험)

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력을 하여 결과 비교
• implementation & measurement가 어려울 때 해볼 수 있는 방식
• trace : simulation에 들어가는 input data (test case 같은 느낌)

---

질문

• SJF를 preemptive한 방식으로 구현하기 위해서는 ready queue에 새로운 프로세스가 도착할 때마다 CPU에게 interrupt를 걸어야하나? 어떻게 새로운 프로세스가 도착했음을 알고, 그것이 더 짧은 프로세스임을 알고, CPU 제어권을 넘기는가?
• Priority scheduling에서 우선순위를 정의하는 방식?
• multilevel queue에서 우선순위 높은 queue의 프로세스가 끝나서 두번째 queue의 프로세스를 처리하던 중 첫번째 queue에 프로세스가 채워지면 preeptive하게 작동하는가? 이것도 두가지 방식으로 나누어질 수 있는건가?
• time slice방식에서 각 queue에 CPU time을 비율로 할당한다는 것의 의미? 어떤 것에 대한 비율인거지? 그냥 하나의 time unit을 지정해서 이에 대한 비율인 것인가
• 별개의 queue를 두는 방식이 왜 load sharing과 관련이 있는가?
  

---

참고 링크

KOCW 운영체제 - 이화여대 반효경 교수 (2014-1) 10, 11강