23.07.07 최초 작성
23.12.05 스케줄링 기법 추가

1. Process Scheduling 이란?

cpu의 제어권을 프로세스에 할당해 주는 작업. cpu는 일반적으로 하나의 작업을 수행 가능하기 때문에 스케줄링을 통해 concurrency를 확보한다.

1. Schedule In
   프로세스가 cpu 제어권을 넘겨받는 동작
2. Schedule Out
   프로세스가 cpu 제어권을 넘겨주는 동작

2. Time Sharing in Modern OS

하드웨어 타이머를 이용해 OS는 스케줄러를 작동시키는데 이 과정을 Time Sharing 기법이라고 한다.
OS가 타이머를 설정해 일정 주기 이후 인터럽트가 발생하도록 한다. 이 인터럽트가 인터럽트 핸들러를 작동시켜 cpu에 프로세스를 할당하며 일정 주기 이후 인터럽트가 발생해 다른 프로세스에 cpu 제어권을 할당한다.

3. Context Change

cpu가 다른 프로세스를 실행할 때 기존 프로세스의 실행 상태(task_control_block)등을 다른 곳에 저장하고(메모리) 새 프로세스의 실행 상태를 cpu에 불러오는 과정

4. Process Scheduling Overview

프로세스는 일반적으로 여러 개가 한 번에 수행되므로 그에 따른 순서가 필요하다. 이러한 순서를 대기하는 곳을 큐(queue)라고 부른다.

• Job Queue: 하드디스크에 있는 프로그램이 실행되기 위해 메인 메모리의 할당 순서를 기다리는 큐이다.

• Ready Queue: CPU 점유 순서를 기다리는 큐이다.

• Device Queue: I/O를 하기 위한 여러 장치가 있는데, 각 장치를 기다리는 큐가 각각 존재한다.

  각 큐 내부에 저장된 실제 데이터는 각 프로세스의 PCB가 저장되어 있다. 그리고 이런 프로세스의 처리 순서를 정해주는 알고리즘을 Scheduling이라고 한다.

5. Scheduling Criteria

5.1 Scheduling Algorithm Goals

1. 기근 현상(Starvation) 예방
2. 프로세스가 공평하게(Fairness) cpu를 활용할 수 있도록 하는 것
3. 모든 시스템을 활용할 수 있도록 하는 것(busy)

5.2 스케줄링 성능 평가 기준

1. cpu 활용도
2. Throughput
3. Turnaround Time
4. Waiting Time
5. Response Time

6. Preemptive Scheduling

1. Preemptive Scheduling
   • 한번 스케줄링 되면 cpu 제어권을 변경할 수 없는 스케줄링 기법
   • 현재 실행중인 프로세스를 강제로 CPU에서 실행 중지하고 새로운 프로세스 실행
2. Non-Preemptive Scheduling
   • 특정 상황에 따라 프로세스의 스케줄링 순서를 변경할 수 있는 스케줄링 기법
   • 프로세스가 자발적으로 스케줄링 요청

7. 스케줄링 기법

7.1 FCFS(First-Come, First-Served) / FIFO

• 작업들이 선착순으로 스케줄링 되는 방법
• 일반적으로 Non-preemptive
• 보통 기근(Starvation)현상이 없음
• Convoy effect가 발생함 (작업시간이 긴 프로세스가 먼저 오면 이후 작업은 지연이 발생함)

7.2 SJF(Shortest Job First)

• cpu 처리시간이 가장 작은 프로세스를 먼저 처리하는 방법
• 가장 적은 대기시간을 보장함
• Non-preemptive
• 기근현상이 발생할 경우가 많음

7.3 SRTF(Shortest Remaining Time First)

• SJF의 Preemptive 버전
• 새로운 작업이 오면 남은 작업시간이 적은 프로세스를 먼저 처리함

7.4 Priority Scheduling

• 프로세스 중 높은 중요도를 가진 프로세스를 먼저 처리하는 방법
• 낮은 중요도의 프로세스는 기근이 발생할 수 있음 -> Aging, Priority Boosting으로 해결

7.4.1 Priority Inversion

• 중요도가 낮은 프로세스를 먼저 처리하기 위해 높은 중요도의 프로세스에 lock을 걸어주는데 중간의 프로세스가 스케줄링되면 이 프로세스가 먼저 실행되고 이 때 처리하고자 하는 프로세스가 실행되지 못하는 현상

  해결법

1. PIP (Priority Inheritance Protocol)
   프로세스의 우선순위를 다른 프로세스에 상속시켜주는 방법
2. PCP (Priority Ceiling Protocol)
   처리하고자 하는 프로세스가 cpu의 제어권을 얻으면 해당 프로세스의 우선순위를 높여주는 방법

7.5 RR (Round Robin)

• 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Slice)로 CPU를 할당하는 방식의 cpu 스케줄링 기법
• 기근 현상 발생하지 않음
• 할당되는 시간이 클 경우 FIFO와 비슷해 짐
• 할당되는 시간이 작은 경우 context change에 의한 오버헤드 증가

7.6 CFS (Completely Fair Scheduler)

• 고정된 시간 간격에서 시스템의 스레드가 적어도 한번 실행하는 스케줄링 기법
• 각 프로세스의 가중치에 비례해서 cpu를 점유하도록 함
  (time slice = 프로세스의 가중치 X 주기 / 런큐에 있는 프로세스의 총 가중치)
• 기근, 대기시간 발생 위험 있음

8. Multilevel Queue Scheduling

우선순위를 가진 큐를 여러개 사용해 스케줄링하는 기법.

8.1 Multilevel Feedfack Queue

큐에 저장된 프로세스의 정보를 바탕으로 스케줄링 방법을 바꾸는 스케줄링 기법

결정 Parameter들

• 큐의 갯수
• 각 큐의 스케줄링 알고리즘
• 어떤 프로세스가 들어갈 큐를 결정하는 방법

8.2 Proportional Share Scheduling

각 큐에 정해진 처리시간을 설정하고 그 시간 안에 큐에서 프로세스를 처리하는 기법

9. Linux Scheduler

• CFS (Completely Fair Scheduling)
  Priority / Preemptive / Time-Shared Scheduling 베이스
• Aging을 사용해 기근 방지

10. Real Time Scheduling

10.1 Real-Time Systems

1. Soft Real Time System

• Real Time 프로세스가 먼저 실행되는 것을 보장함
• 주어진 시간(Deadline)안에 작업이 수행되지 않을 수도 있음

2. Hard Real Time System

• 주어진 시간(Deadline)안에 작업이 수행되어야 함
• 시간을 넘기면 안하느니만 못한 시스템

10.2 Real-Time cpu Scheduling

주기 p, 처리 시간 t, deadline d라 할 때
0 < t < d < p
Rate = 1/p

10.2.1 RMS (Rate Monotonic Scheduling)

• Rate가 큰 순서대로 스케줄링하는 방법
• 해당 방식으로도 스케줄링하지 못하면 다른 방식으로도 절대 적절한 스케줄링을 하지 못한다
• RMS에서 N개의 프로세스를 스케줄링할 때 가장 최악의 경우 다음과 같은 실행시간을 가진다
  

10.2.2 EDF(Earliest Deadline First)

• Deadline이 Priority인 스케줄링 방법 (Deadline이 작을수록 우선)
• 일반적으로 항상 cpu 활용을 100% 할 수 있다(Theoretically Optimal)