[OS] CPU 스케줄링

CPU 스케줄링은 multiprogrammed 운영체제에서 기저가 되며, CPU를 여러 프로세스들이 스위칭하며 사용하기 때문에 보다 생산적이다.

5.1 Basic Concepts

CPU 스케줄링을 하는 목적은 CPU utilization을 최대화하기 위함이다.

I/O 요청과 같은 일을 처리하기 위해서 프로세스는 기다리며 시간을 낭비하게 된다.

이를 idle time이라고 하는데, CPU가 idle일 때 다른 프로세스를 처리하도록 스케줄링하므로써 CPU utilization을 극대화 할 수 있다.

 

CPU Scheduler

CPU가 idle이 되면, 운영체제는 ready queue에서 프로세스를 하나 선택하여 실행하게 된다.

이 선택을 하는 것이 CPU schduler이다.

ready queue는 꼭 FIFO 형태로 구현될 필요는 없으며 FIFO, priority queue, tree, unordered linked list 등으로 구현되기도 한다.

이렇게 구현된 ready queue에는 CPU에 할당되기를 기다리는 프로세스들의 PCB가 레코드로 들어있다.

 

Preemptive and Nonpreemptive Scheduling

CPU 스케줄링은 다음과 같은 상황에 따라 결정될 수 있다.

1. running state → waiting state
2. running state → ready state
3. waitng state → ready state
4. terminate

상황 1, 4일 경우에만 스케줄링이 일어나는 경우를 nonpreemptive 또는 cooperative 라고 하며

상황 2, 3의 경우도 고려하는 경우는 preemptive라고 한다.

• Nonpreemptive 스케줄링
  • CPU가 한 번 할당되면 프로세스가 종료되거나 waiting state가 되기까지 프로세스를 유지한다.
  • 응답 시간이 예측 가능함
• Preemptive 스케줄링
  • CPU에 프로세스가 할당된 상태여도 다른 프로세스가 CPU를 차지할 수 있는 기법
  • 우선순위가 높은 프로세스 먼저 수행해야할 때 유리
  • 빠른 응답 시간이 요구될 때 유리
  • 대부분의 현대 운영체제 시스템은 이 방식을 사용한다.
  • Race condition이 발생할 수 있음
  • 많은 오버헤드 초래

Dispatcher

CPU 스케줄러의 컴포넌트 중 하나로, CPU 코어의 컨트롤을 프로세스에게 부여하는 모듈이다.

Dispatcher는 매 context switch마다 호출되므로 속도가 빨라야하며, dispatcher가 프로세스를 바꾸는 과정에서 발생하는 지연 시간을 dispatch latency라고 한다.

 

5.2 Scheduling Criteria

• CPU utilization
• Throughput : 단위 시간 당 프로세스 완료 개수
• Turnaround time
  • 프로세스가 submit된 후 부터 완료되기까지의 시간
  • ready queue 대기 시간 + 실행 시간 + I/O 시간
• Waiting time : ready queue에서의 대기 시간
• Response time : submit된 시간부터 첫 응답까지의 시간

 

5.3 Scheduling Algorithms

• FCFS (First-Come First-Serve, FIFO)
  • 가장 간단한 스케줄링 기법
  • 먼저 들어온 프로세스를 먼저 CPU에 할당
  • 비선점
• SJF (Shortest-Job-First)
  • 처리해야할 작업의 시간이 가장 적은 프로세스를 CPU에 할당
  • 평균 대기 시간(avg waiting time)이 가장 적은 최적의 알고리즘
  • 각 프로세스가 필요한 작업의 시간을 미리 알기 어렵다는 단점
  • 비선점
• SRTF
• RR (Round-Robin)
  • FIFO 스케줄링 기법을 선점형 기법으로 구현한 방법
  • FIFO 형태의 큐에 적재되지만, 주어진 시간 할당량(Time Slice) 내에 작업을 마쳐야하며, 그러지 못한 프로세스는 다시 ready queue로 적재된다.
  • 선점 (time slice 때문)
• Priority
  • 각 작업, 프로세스마다 우선 순위가 주어지며, 우선 순위가 높은 작업부터 CPU에 할당
  • 우선 순위가 낮은 프로세스의 경우 indefinite blocking 또는 starvation에 빠질 수 있음
  • Aging 기법
    • ready queue에서 대기가 길어질 수록 우선 순위가 높아지는 방식
    • starvation 문제를 해결
• Multilevel Feedback Queue
  • 프로세스들이 각각의 특성에 따라 서로 다른 ready queue에 저장됨
  • CPU 처리 시간이 긴 경우는 낮은 우선 순위의 큐에, 짧은 경우는 높은 우선 순위의 큐에 배치되는 형태