[운영체제 공룡책] 5. CPU Scheduling

CPU 스케줄링

5.1 Basic Concepts

• CPU scheduling은 멀티 프로그래밍 OS 시스템에서 필수
  • 멀티프로그래밍(multiprogramming)의 목표는 동시에 여러 프로세스가 수행되고, CPU 사용률을 극대화시키는 것임
  • CPU 사용하는 구간을 CPU burst, I/O 이벤트를 처리/대기하는 구간은 I/O burst라고 함
• 프로세스 에 CPU burst가 많으면 cpu-bound, I/O burst가 많다면 I/O-bound
• CPU schduler
  • 누구에게 CPU를 줄 것이냐? ready 상태의 프로세스 중 어떤 프로세스에게 CPU를 할당(allocates)할 것인지에 대한 문제가 cpu shceduling
  • 어떻게 선택할 것인지? Linked List or Binary Trre? FIFO Queue? Priority Queue?
• Preemptive(선점형) - next process가 기존 process 강제로 쫒아냄 vs Non-preemptive (비선점형) - 못쫒아냄. 자발적으로 나오기 전 까지는 프로세스에게 할당된 CPU를 계속 점유하도록 유지
• Dicision making for CPU scheduling
  • running to waiting 상태
  • running to ready 상태
  • waiting to ready 상태
  • terminates 상태
  • 1번, 4번 상태는 non-preemptive
  • 그러나 2번, 3번 상태는 preemptive or non-preemptive 선택 필요! 선점형이 선택지가 넓으니 효율적임. 그럼 선점형을 어떻게 구현할 것인가 또 고민해봐야함
• dispatcher
  • CPU core의 제어권(control)을 넘겨주는 것
  • content switch 하는 모듈을 dispatcher
  • 문맥교환, 유저모드로 변경, 적당한 시점에 프로세스를 resume(재개)하는 것
• dispatcher는 가능한 빨라야함! P0 → P1 문맥 교환하는 데에 소요되는 시간을 dispatch latency 라고 함. 이게 자주, 오래 걸리게 된다면? CPU 효율 망함
  

  

5.2 Scheduling Criteria

• 스케쥴링의 목표
  • CPU utilization - CPU 사용률 극대화
  • Throughput : 시간 단위당 완료되는 프로세스의 수를 늘림
  • Turnaround time : 프로세스 실행에서 종료되기까지의 시간을 짧게 함
  • Waiting time : 어떤 프로세스가 ready queue에서 대기하는 시간. 이것을 최소화함
  • Response time : 응답시간 최소화 (ex: UI)

스케줄링 알고리즘

5.3 Scheduling Algorithms

• CPU Scheduling Problem : Ready Queue에 있는 프로세스들 중 어떤 프로세스에게 CPU Core를 할당해줄 것인가?
• Scheduling
  • FCFS : First-Come, First-Served
  • SJF : Shortest Job First (SRTF : Shortest Remaining Time First)
  • RR : Round-Robin
  • Priority-based (우선순위)
  • MLQ : Multi-Level Queue
  • MLFQ : Multi-Level Feedback Queue (현대적인 OS)
• FCFS : 선입선출
  • FCFS 문제점 : Convoy Effect (호송효과, 똥차효과, 진상손님)
• SJF: 작업이 짧게 남은 것을 먼저 처리하자
  • 장점 : 최대 효율을 얻을 수 있음! provably optimal! waiting time의 평균 소요시간 최소화함
  • 문제점 : 컨셉은 간단하나 구현할 수 없음. 각 task가 어느정도 자원을 소모할 지 예측할 수 없음
  • 정확하게 구현할 수 없다면 근사치를 구해서 next CPU burst를 예측해보면 어떨까?
    • 과거를 통해 미래를 예측하자! 컨셉 : 과거에 CPU를 많이 쓴 process는 현재에도 많이 쓰지 않을까? 지수적 평균(exponential average)를 적용해서 최근에 많이 쓴 process에게 가중치를 줌
    • SJF는 선점형(preemptive)일 수도, 비선점형(non-preemptive)일 수 있음 (근데 SJF가 비선점형인게 의미가 있나??? 모든 프로세스가 동시에 들어오지 않을텐데)
  • Preemptive SJF == SRTF (Shortest Remaining Time First) : 새로운 프로세스가 왔을 때 CPU burst가 더 적다면 기존 작업을 중지시키고 새로운 프로세스에게 CPU를 할당해줌!
• RR : 시분할! 타임 슬라이싱! 그리고 RR은 당연 preemptive임
  • preemptive FCFS with a time quantum
  • RR은 종종 평균 waiting time이 오래 걸린다!
  • 하지만 RR은 단독으로 사용하지 않고 SJF와 섞어씀
  • RR은 time quantum size에 따라 효율이 달라짐. 너무 잦으면 디스패쳐 레이턴시 때문에 효율이 떨어지고 너무 간격이 넓으면 FCFS 처럼 효율 떨어짐
• Priority-base 우선순위 : 우선순위에 따라 자원을 할당하고, 우선순위가 동일한 경우에는 FCFS 순서로 처리 가능함
  • SJF 역시 우선순위 알고리즘의 한 종류임
  • 우선순위 역시 선점형(=SRTF), 비선점형(=SJF) 가능함
  • 문제점 : starvation 기아상태. indefinite blocking 무한대기. 후에 데드락과 연관됨
  • 스케쥴러 입장에서 기아 상태를 해결할 수 있는 방법은? aging 오래 대기한 프로세스에게 가점을 줘서 우선순위가 높아질 수 있도록 함
  • RR과 우선순위를 혼합하여 사용 가능! 우선순위가 동일할 경우 RR을 사용하여 처리
• Multi-Level Queue(MLQ) → 현대적 컴퓨터!
  • N개의 ready queue를 두고 각 큐마다 다른 우선순위를 부여함
  • 
  • 기아상태 방지를 위해 MLQ에 aging 을 적용해본다면?
  • 
• 현대 OS에서 프로세스 스케쥴링은 하지 않음. 스레드를 사용하면 되니깐!
  • 스레드 스케쥴링 공부하기 어려우니까 프로세스로 다룬거임
  • kernel threads CPU 스케쥴링은 커널 스레드를 가지고 스케쥴링한다고 보면 됨! 프로세스 아님!
  • 유저 스레드는 스레드 라이브러리가 관리하기 때문에 커널은 스레드가 어떻게 관리되는 지 관심 없음
• Real-Time OS (상식 차원에서 공부)
  • 윈도우와 리눅스는 실시간 OS가 아님
  • 실시간 OS랑 주어진 시간 내에 작업을 완료할 수 있어야함
  • Soft realtime : 반드시 그 시간 내에 끝나지 않지만, 우선순위가 높은 프로세스가 항상 먼저 실행되야함 (데드라인 보장 X)
  • Hard realtime : 반드시 데드라인을 지켜야함

퀴즈

틀렸던 것만 따로 정리함