[OS] CPU Scheduling

CPU Scheduling 이란?

• 멀티 프로그래밍 OS의 기초
• 목적: 1) 여러 프로그램을 동시에 실행, 2) CPU 활용을 극대화

💡 멀티 프로그래밍이란? 단일 프로세스에서 여러 개의 프로그램이 동시에 실행되는 것.

Histogram of CPU-burst duration

위의 히스토그램에서 볼 수 있듯이, 일반적으로 CPU-burst(CPU가 running인 상태)시간보다 I/O-burst 시간이 더 길다. 즉, CPU를 더 효율적으로 활용할 수 있는 방안을 생각해 볼 수 있다.

CPU Scheduler 란?

• 메인 메모리에 적재된 프로세스 중 ready 상태의 프로세스를 선택하여 CPU에 allocate 하는 프로그램
• 스케줄러는 어떤 방식으로 프로세스를 선택하는가?
  • Linked List or Binary Tree
  • FIFO Queue
  • Priority Queue: 우선순위를 어떻게 결정할까?

Preemptive(선점형) vs Non-Preemptive(비선점형)

• Non-Preemptive Scheduling
  • 프로세스가 terminated 혹은 waiting 상태가 되기 전까지 CPU 할당이 유지
• Preemptive Scheduling
  • Scheduler에 의해 프로세스의 CPU 할당이 결정

Decision making for CPU-Scheduling

1. running to waiting
2. running to waiting
3. waiting to ready
4. terminated

• No.1, No.4: 비선점형
• No.2, No.3: 비선점형 혹은 선점형

Dispatcher란?

• CPU Scheduler에 의해 선택된 프로세스에게 CPU 코어 제어권을 넘겨주는 module
• Dispatcher의 기능
  • 하나의 프로세스에서 다른 프로세스로 context를 switching
  • user mode로 switching
  • user program을 resume하기 위해 적절한 위치로 이동
• Dispatcher의 흐름
  • 실행 중인 프로세스(P0)의 PCB를 save
  • ready 상태인 프로세스(P1)의 PCB를 restore
  • 프로세스(P1)에게 CPU 코어 제어권 할당 후 resume
• 위 과정의 지연 시간을 Dispatcher Latency 라고 한다.

Context Switching마다 Dispatcher가 실행되므로 Dispatcher는 가능한 최대한 빨라야 한다.

Scheduling Criteria

• CPU Utilization: 최대한 CPU가 바쁘게 유지
• Throughput: 단위 시간 당 실행되는 프로세스의 수
• Turnaround time: CPU가 submission되서 completion 될 때까지 프로세스가 실행된 시간
• Waiting time: 프로세스가 ready queue에서 기다리는 시간 합산
• Response time

CPU Scheduling Problem

• 핵심 문제: CPU 코어 제어권을 할당 받을 ready queue의 프로세스를 어떤 기준으로 결정?

Solutions

• FCFS(First-Come, First-Served): 수십년 전의 OS에서나 사용
• SJF(Shortest Job First), SRTF(Shortest Remaining Time First)
• RR(Round-Robin): 프로세스가 정해진 시간 분량만큼만 실행. 시분할과 관련된 개념
• Priority Based
• MLQ(Multi-Level Feedback Queue)

FCFS Scheduling

• 정의: First-Come, First Served, 가장 단순한 CPU Scheduling Algorithm
  • 먼저 CPU 사용 요청을 한 프로세스를 먼저 할당하는 구조
  • FIFO queue로 쉽게 구현 가능
  • Non-Preemptive
• 문제점
  • Convoy Effect(호송 효과; 똥차 효과)
    • 먼저 실행되는 프로세스의 실행 시간이 크면, 프로세스들의 waiting time, turnaround time이 증가
    • 즉, FCFS Policy을 따르면 waiting time이 최소 시간이 아니고, 실행 순서에 따라 가변적이다.
    • 만약 한 개의 CPU 집약적인 작업과 여러 개의 I/O 집약적인 작업이 실행되는 상황이라면?

SJF Scheduling

• 정의: Shortest-Job-First, CPU burst time이 가장 작은 프로세스를 먼저 할당하는 구조
  • SJF는 각 프로세스와 연관: CPU가 사용 가능하다면, 다음 CPU burst time이 가장 작은 프로세스를 할당
  • 만약 여러 개의 프로세스가 같은 CPU burst time을 갖는다면, FCFS 스케줄링에 따른다.