CPU 스케줄링 (CPU Scheduling)

공룡책(10판) Chapter 5 요약

용어들이 넘 많이 나오고 복잡해지고 있어!

기본 개념 _ Basic Concepts

멀티프로그래밍의 목적은 곧 CPU 이용률을 최대화 하는 것이다. 하나의 프로세스는 I/O 요청이 완료되기를 기다리며 놀 수 있는데, 이런 대기 시간은 낭비이기에 어떻게든 굴려먹어야 한다. 중요한 컴퓨터 자원인 CPU 자원을 프로세스에 할당, 대기, 양도 등 과정에서 CPU 스케줄링은 운영체제 설계의 핵심이라고 할 수 있다.

- CPU-I/O 버스트 사이클 _ CPU-I/O Burst Cycle

프로세스는 CPU 실행과 I/O 대기의 사이클로 구성된다. CPU 버스트 부터 시작되어 왔다갔다 한다. 그러다 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르고 실행 종료 시스템 요청과 함께 끝난다. 여기서 CPU 버스트란 CPU 명령을 실행하는 것, I/O 버스트는 I/O를 요청하고 기다리는 것이다.

CPU 버스트가 많은 프로세스를 CPU 바운드 프로세스 (계산 위주로 하는 프로세스), I/O 버스트가 많으면 I/O 바운드 프로세스 (사용자 대화형 프로세스) 라고 한다.

- CPU 스케줄러 _ CPU Scheduler

스케줄러는 ready 상태에 있는 프로세스들 중에서 CPU를 할당(allocate) 해줄수 있는 것을 선택한다.

ready 큐는

• Linked list 큐, Binary tree
• FIFO 큐 (선입선출 큐)
• Priority 큐 (우선순위 큐)

로 구현할 수 있다. 큐의 레코드는 일반적으로 PCB이다.

스케줄링에서는 우선순위를 부여할 방법이 가장 핵심이 될 것임.

- 선점 및 비선점 스케줄링 _ Preemptive and Nonpreemptive Scheduling

스케줄링은 다음 네 가지 상황에서 발생한다.

1. 프로세스가 실행(running) 상테에서 대기(waiting) 상태로 전환될 때; I/O 요청, 자식을 기다리는 wait() 호출
2. 프로세스가 실행(running) 상태에서 준비(ready) 상태로 전환될 때; 인터럽트 발생
3. 프로세스가 대기(waiting) 상태에서 준비(ready) 상태로 전환될 때; I/O의 종료
4. 프로세스가 종료(terminate) 될 때

1, 4 에서만 스케줄링이 발생하면 비선점형 스케줄링이다.

선점에 있어서 신경써야 할 것들은 다음이 있다.

• 선점 스케줄링에서 다수의 프로세스에 의해 데이터가 공유 될 때 데이터 일관성 문제
• 공유 커널 데이터 구조의 엑세스의 경쟁 조건 방지를 위한 락이 필요
• 인터럽트에 의해서 영향을 받는 부분에 대한 동시 사용 제한 (인터럽트 불능화)

- 디스패처 _ Dispatcher

CPU 코어에 CPU 스케줄러가 선택한 프로세스 컨트롤을 넘겨주는 모듈이다.

• 디스패처가 할 일
  • 컨텍스트를 프로세스에서 다른 프로세스로 넘겨주기
  • 유저 모드로 전환
  • 새로운 프로세스의 적당한 위치로 이동(jump)하여 resume

스케줄러와 디스패처의 역할의 다름에 주목하고, 실제 스위치는 디스패처가 하며, 디스패처는 모든 프로세스의 컨텍스트 스위칭 시 호출되기에 빨라야한다. 프로세스를 정지하고 다른 프로세스의 수행을 시작할때까지 걸리는 시간을 디스패치 지연(dispatch latency) 라고 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+-----------------------+ 
|        P0 실행        |
+-----------------------+   ---
            |                |
+-----------------------+    |
|        PCB0 에        |    |
|       상태 저장       |    |
+-----------------------+    |
            |              디스패치 지연
+-----------------------+    |
|       PCB1 에서       |    |
|       상태 복원       |    |
+-----------------------+    |
            |                |
+-----------------------+   ---
|        P1 실행        |
+-----------------------+ 
            |

컨텍스트 스위치가 얼마나 자주 발생하는가? vmstat 의 cs 값 확인한다.

1
2
3
4
5
6

dwkim@DESKTOP-A4LF2TT:~$ vmstat 1 3
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 1  0      0 6108328  15088 262392    0    0   247  1113   82  155  1  1 98  0  0
 0  0      0 6107580  15096 262384    0    0     0 18444   80  314  0  0 100  0  0
 0  0      0 6107808  15096 262392    0    0     0 20480  119  349  0  0 100  0  0

스케줄링 기준 _ Scheduling Criteria

다음은 CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이다.

• CPU 이용률 (utilization)
• 처리량 (throughput) : 단위 시간당 완료된 프로세스의 개수
• 총처리 시간(turnaround time) : 프로세스의 제출 시간과 완료 시간의 간격
• 대기 시간 (waiting time) : 레디 큐에서의 대기 하면서 보낸 시간의 합
• 응답 시간 (response time) : 대화식 시스템이나 주로 UI에서 사용, 응답이 나올 때 까지의 시간

CPU 이용률 및 처리량을 최대화, 나머지를 최소화하는것이 바람직하다. 최적화를 위해, 응답 시간에 대해서는 편차(variance)를 최소화하는게 중요하다고 제시되고 있다고 한다.

스케줄링 알고리즘 _ Scheduling Algorithms

여러 CPU 스케줄링 알고리즘들에 대해 알아본다.

- 선입 선처리 스케줄링 FCFS _ First-Come, First-Served

가장 간단한 알고리즘으로 이름 그대로 먼저 요청한 프로세스한테 먼저 배정된다. FIFO Queue로 사용하기가 편리하다. 허나 평균대기 시간은 굉장히 길 수 있다.

참여한 각 프로세스의 시작, 종료 시각을 포함하여 스케줄 기법을 도시하는 막대형 차트인 Gantt 차트로 다음 프로세스들을 살펴보자.

1
2
3
4
5
6
7
8
9
10
11
12

프로세스    버스트 시간
-----------------------
p1          24
p2          3
p3          3
-----------------------

Gantt 차트
+------------------------+---+---+
|                      p1| p2| p3|
+------------------------+---+---+
0                       24  27  30 (ms)

Gantt 차트로 대기 시간(waiting time)을 계산하면 total 0+24+27=51 평균 대기 시간은 17ms 이다.

이번엔 p2, p3, p1 순서로 도착하였다고 하면,

1
2
3
4
5

Gantt 차트
+---+---+------------------------+
| p2| p3|                      p1|
+---+---+------------------------+
0   3   6                       30

total 6+0+3=9 평균 대기 시간은 3ms 이다. 프로세스의 CPU 버스트 시간에 따라 차이가 많이 난다.

FCFS는 비선점형이고, 다른 프로세스들이 하나의 긴 프로세스를 CPU가 처리하는동안 기다리는 걸 convoy effect (호위 효과, 호송 효과, 똥차 효과; 오지게 길막한다고 똥차효과란다) 라 하며, 이때문에 FCFS로는 좋은 효율을 얻을 수 없다. 특히 하나의 CPU바운드 프로세스와 많은 io프로세스를 가정하면, waiting time 측면에서 엄청 늘어날 수밖에 없게 된다.

• waiting time 이 아닌 총처리 시간으로도 (turnaround time) 계산해보자
  • 처음의 차트
    • 전체 24+27+30=81 평균 27ms
  • 순서가 바뀌었을 때
    • 전체 3+6+30=39 평균 13ms

- 최단 작업 우선 스케줄링 SJF _ Shortest Job First

CPU 버스트의 길이에 의해 스케줄링이 된다. 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄링 되기에 최단 다음 CPU 버스트(shortest-next-CPU-burst) 알고리즘이라고 하기도 한다. 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당한다.

각 프로세스의 다음 CPU 버스트를 가지고 계산한다고 가정, CPU가 available할 때 next CPU버스트가 가장 작은것을 배정한다. 같다면 FCFS 적용

1
2
3
4
5
6
7
8
9
10
11
12
13

프로세스    버스트 시간
-----------------------
p1          6
p2          8
p3          7
p4          3
-----------------------

Gantt 차트
+---+------+-------+--------+
| p4|    p1|     p3|      p2|
+---+------+-------+--------+
0   3      9      16       24 (ms)

짧은걸 먼저 실행하고, 도착 순서와 무관하다. 대기 시간은 3+16+9+0=28, 평균 7 ms이다. 총처리 시간은 전체 3+9+16+24=52, 평균 13 ms이다.

이처럼 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가지기에 최적임을 증명할 수 있다. 하지만 다음 CPU버스트의 길이를 알 방법이 없어 CPU 스케줄링 수준에서는 구현할 수 없다고 한다. 그래서 근사한 방법으로 이전의 CPU 버스트들의 길이를 지수(exponential) 평균한 것으로 예측한다.

t_n은 n번째 CPU 버스트의 길이이고, 타우(τ)_n+1은 다음 CPU 버스트이 예측값이다. τ_n은 과거의 역사이고, 알파는 확률이라는데.. 잘 모르겠다..

아무튼 SJF 알고리즘은 선점형이거나 비선점형일 수 있는데, 선점형 SJF 알고리즘은 최소 잔여 시간 우선 SRTF (Shortest Remaining Time First) 라고도 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13

프로세스    도착 시간    버스트 시간
------------------------------------
p1          0            8
p2          1            4
p3          2            9
p4          3            5
------------------------------------

Gantt 차트
+---+------+-------+--------+-----------+
| p1|    p2|     p4|      p1|         p3|
+---+------+-------+--------+-----------+
0   1      5      10       17          26 (ms)

도착하고 나서 잔여 시간을 생각하여 p2에게 먼저 스케줄링이 할당되는 것을 알 수 있다.

- 라운드 로빈 스케줄링 _ Round-Robin Scheduling

정해진 시간을 공평히 쪼개서 쓰는 방법이다.

시간 할당량(time quantum), 타임슬라이스(time slice) 라는 작은 단위의 시간을 정의하여 한 프로세스에 한번의 시간 할당량 동안 동작한다. 준비 큐는 원형 큐(circular queue)로 동작한다. 타이머를 설정하고 시간 할당량보다 긴 cpu 버스트를 가지고 있으면 인터럽트를 하고 컨텍스트 스위치가 일어나는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12

프로세스    버스트 시간
-----------------------
p1          24
p2          3
p3          3
-----------------------

// 시간 할당량을 4ms로 할 때, Gantt 차트
+----+---+---+----+----+----+----+----+
|  p1| p2| p3|  p1|  p1|  p1|  p1|  p1|
+----+---+---+----+----+----+----+----+
0    4   7  10   14   18   22   26   30 (ms)

RR 알고리즘은 시간 할당량의 크기에 영향을 많이 받는다. 시간 할당량이 적을수록 Context switch의 횟수가 늘어나기 때문에, Context switch의 시간만큼 손해를 보므로 할당량 크기를 잘 정해야 한다. 너무 클 경우에는 FCFS와 다를 바 없어진다.

- 우선순위 스케줄링 _ Priority Scheduling

우선순위가 높은 프로세스를 CPU에 할당하는 방식

순위가 같은 경우 FCFS를 적용한다. SJF는 우선순위 스케줄링의 한 경우로 다음 CPU 버스트에 반비례하여 높은 순위를 가지는 방식이라 할 수 있겠다.

선점형 우선순위 스케줄링은 새로 도착한 프로세스의 우선순위가 높으면 CPU를 선점하게끔 하고, 비선점형의 경우는 준비 큐의 머리 부분에 새로운 프로세스를 할당한다. 이 우선순위 스케줄링 알고리즘의 주요 문제로는 기아(starvation), 무한 봉쇄(indefinite blocking)가 있다. 이는 우선순위 priority가 낮은 녀석이 계속 기다리기만 하는 현상이다.

해결 방안으로는 노화(aging) 방법이 있다. 오랜 시간을 기다리면 priority를 점진적으로 높여 주자는 것.

- 다단계 큐 스케줄링 MLQ : Multi-Level Queue Scheduling

스케줄링 방법을 여러개 섞어서 사용하는 것으로 우선순위마다 별도의 큐를 갖게 하는 것이다. 프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하여 사용한다. foreground, background 프로세스를 구분하여 스케줄링 방법을 사용하는 예가 있을 수 있겠다.

분리된 레디 큐에 각각의 프라이어리티

여러 큐를 가지고 있을 때 다음과 같은 우선순위를 갖는다.

실시간 > 시스템 > 대화형 > 배치 프로세스

- 다단계 피드백 큐 스케줄링 MLFQ : Multi-Level Feedback Queue Scheduling

프로세스가 여러 큐들 사이를 이동하는 것을 허용하는 것이다.

여러 개 섞는 걸로 모자라 피드백까지 받아서 반영한다. 다단계 피드백 큐 스케줄링을 결정하기 위한 매개변수가 여럿 있다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

가장 일반적인 스케줄링이라고 할 수 있겠다. 허나 위 값들을 선정하는 방법이 필요하기에 가장 복잡한 알고리즘이다.

스레드 스케줄링 _ Thread Scheduling

사용자 수준의 스레드와 커널 수준 스레드의 쟁점에 관한 이야기이다.

다대일, 다대다 모델에서 스레드 라이브러리는 사용자 수준 스레드를 LWP (Light Weight Process, 경량 프로세스) 에서 동작하도록 스케줄링한다. 이 때, 스케줄링 경쟁이 프로세스 내에서 발생하여 프로세스-경쟁 범위(process-contention scope)라 한다.

LWP 상에서의 스케줄은 CPU 상에서 실행 중인 것을 의미하지 않으며, CPU 상에서 실행되려면 운영체제가 LWP의 커널 스레드를 CPU로 스케줄 하여야 한다. 이 때 CPU로 스케줄하는 결정을 하기 위하여 커널은 시스템-경쟁 범위(system-contention scope)를 사용한다.

즉, 커널의 입장에서는 커널 스레드만 스케줄링 해주면 되는 것이고 커널 스레드는 유저 스레드를 매핑만 해주면 된다. O/S 커널은 CPU 스케줄링을 커널 스레드를 가지고 적용한다.

다중 처리기 스케줄링 _ Multiple-Processor Scheduling

- 접근방법

다중 CPU 환경에서는 앞서 이야기한 것보다 복잡해진다. 그리하여 두 가지 스케줄링 접근법을 제시한다.

• 비대칭 다중 처리 (asymmetric multiprocessing) : 오직 하나의 코어만 시스템 자료 구조에 접근하여 자료 공유의 필요성을 감소시킨다.
• 대칭 다중 처리(symmetric multiprocessing, SMP) : 각 프로세서는 스스로 스케줄링한다. 이를 관리하기 위한 전략으로 다음을 고려한다.
  • 모든 스레드가 공통 준비 큐를 가지는 경우
  • 각 프로세서가 자신만의 스레드 큐를 가지는 경우

대부분의 최신 운영체제는 SMP를 지원한다.

- 다중 코어 프로세서

스케줄링 문제에서 복잡한 사항으로, 메모리 스톨(memory stall)은 프로세서가 메모리보다 빠르게 동작하기에, 메모리에서의 데이터 가용을 기다리며 많은 시간을 허비하는 현상이다. 이를 해결하기 위하여 최근의 하드웨어 설계는 다중 스레드 처리 코어를 구현한다. 하나의 코어에 2개 이상의 하드웨어 스레드가 할당되어 메모리를 기다리는 동안 코어가 다른 스레드로 전환하여 일을 수행하게끔 하는 것이다. 이 기술은 칩 다중 스레딩(chip multithreading, CMT)로 불리며 인텔 프로세서에서는 하이퍼스레딩 혹은 동시 다중 스레딩이라는 용어를 사용한다고 한다.

- 부하 균등화

SMP 시스템에서 여러 프로세서를 최대한 활용하려면 부하를 균등하게 배분하는 것 또한 중요할 것이다. 부하 균등화(load balancing) 는 각 프로세서가 자신만의 스레드 큐를 가지는 시스템에서 사용되는 방법이다. 부하 균등화를 수행하는 방식으로 push이주, pull 이주가 있다. 바쁜 녀석이 덜바쁜 녀석에게 push 하거나 반대의 상황에서 pull 하는 방식이다.

실시간 CPU 스케줄링 _ Real-Time CPU Scheduling

실시간 OS에서는 주어진 시간 내에 task를 완료할 수 있어야 한다. 시스템은 연성, 경성으로 구분된다.

• 연성 실시간 (soft realtime) : 크리티컬한 프로세스가 반드시 그 시간에 끝나진 않지만 아닌 프로세스보다 먼저 끝나도록 보장한다.
• 경성 실시간 (hard realtime) : 태스크는 반드시 마감시간까지 서비스를 받아야 한다.

프로세스 스케줄링에 대한 쟁점에 대해 알아보자.

- 지연시간 최소화

이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간을 이벤트 지연시간(Event Laentcy)이라 한다.

• 인터럽트 지연시간 : CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴(ISR)이 시작하기까지의 시간
• 디스패치 지연시간 : 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간

이러한 지연시간들이 실시간 시스템의 성능을 좌우한다.

- 우선순위 기반 스케줄링

실시간 운영체제에서 가장 중요한 기능은 실시간 프로세스에 CPU가 필요 할 때 바로 응답을 해주는 것으로, 실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 지원해야만 한다. 이는 연성 실시간 기능을 제공할 수 있게 한다. 경성 실시간 시스템에서는 마감시간 내에 확실히 수행되는 것을 보장해야 하기에 부가적인 방법이 필요하다.

- Rate-Monotonic 스케줄링

선점 가능한 정적 우선순위 정책을 이용하여 주기 태스크들을 스케줄 한다. CPU를 더 자주 필요로 하는 태스크에 더 높은 우선순위를 주려는 원리에 기반을 두고 있다. Rate-Monotonic 스케줄링 기법이 스케줄 할 수 없는 프로세스 집합의 경우 정적 우선순위를 쓰는 다른 알고리즘 역시 스케줄 할 수 없기에 최적이라고 할 수 있다. 이 제약으로는 CPU 이용률은 한계가 있다는 것으로 N개의 프로세스를 스케줄 하는데 있어 최악의 경우 CPU 이용률은 N(2^1/N - 1) 이다.

- Earliset Deadline First 스케줄링

마감시간에 따라서 우선순위를 동적으로 부여한다. 마감시간이 빠를수록 우선순위는 높아지고, 반대의 경우 낮아진다. EDF 정책에서는, 프로세스가 실행 가능하게 되면 자신의 마감시간을 시스템에 알려야 한다. 이를 통해 다시 우선순위가 조정된다.

- 일정 비율의 몫 스케줄링

모든 응용들에 T개의 시간 몫을 할당하여 동작한다. 한 개의 응용이 N개의 시간 몫을 할당받으면 그 응용은 모든 프로세스 시간 중 N/T 시간을 할당받게 된다. 각 시간 몫을 할당받는 것을 보장하는 승인 제어 정책과 함께 동작하여야 한다. 정책은 범위 내의 몫을 요구하는 클라이언트들에게만 실행을 허락한다.

- POSIX 실시간 스케줄링

POSIX는 다음과 같이 실시간 스레드를 위하여 두 개의 스케줄링 클래스를 정의한다.

• SCHED FIFO : FIFO큐를 사용하여 먼저 온 것을 먼저 서비스하는 정책에 따라 스레드를 스케줄한다.
• SCHED RR : 라운드 로빈 정책을 사용하여 같은 우선순위의 스레드에 시간 할당량을 제공한다.

POSIX API는 스케줄링 정책에 관한 정보를 저장하고 얻어내는 다음과 같은 두 개의 함수를 제공한다.

• pthread_attr_getschedpolicy(pthread_attr_t *attr, int *policy)
• pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy)

위의 함수의 첫 번째 인자는 스레드의 속성 집합에 대한 포인터이고, 두 번째 인자는 현재의 스케줄링 정책이거나, SCHED_FIFO, SCHED_RR, SCHED_OTHER와 같은 정책을 표현하는 정수 값이다.

알고리즘 평가 부분도 넣고 싶은데 천천히 넣자..

양이 많아지고 이제 많이 어렵다..! 중요 부분을 추리는 법이 더 필요할 듯 싶다.