중앙처리장치 스케줄링(CPU Scheduling)

5. 중앙처리장치 스케줄링(CPU Scheduling)

5.1 기본 개념(Basic Concepts)

▶ 다중 프로그래밍의 목적: 항상 실행중인 프로세스를 가지게 함으로써 중앙처리장치 이용률을 최대화하는 것

5.1.1 중앙처리장치/입출력 버스트 주기(CPU-I/O Burst Cycle)

▶ 프로세스 실행

- CPU 실행(CPU burst)과 입출력 대기(I/O burst)의 순환으로 구성됨

단, CPU 버스트로 시작하고 종료함

[그림 5.1] 중앙처리장치와 입출력 버스트의 교대 순서

- CPU 버스트의 소요 시간: 지수형(exponential) 또는 초지수형(hyper-exponential)

[그림 5.2] 중앙처리장치 버스트 시간의 히스토그램

① 입출력 중심 작업: 다수의 짧은 CPU 버스트

② 중앙처리장치 중심 작업: 소수의 긴 CPU 버스트

5.1.2 중앙처리장치 스케줄러(CPU Scheduler)

▶ 중앙처리장치 스케줄러: 단기 스케줄러

  중앙처리장치가 유휴 상태가 될 때마다 운영체제는 준비 큐에 있는 프로세스들(프로세스 제어 블록; PCB) 중에서 하나를 선택하여 실행

5.1.3 선점 스케줄링(Preemptive Scheduling)

▶ 중앙처리장치 스케줄링 결정의 발생 조건: 프로세스의 상태가 다음과 같이 변화할 때

1) 실행 상태 → 대기 상태: ex) 입출력 요청, 자식 프로세스의 종료를 기다리는 호출

2) 실행 상태 → 준비 상태: ex) 인터럽트 발생

3) 대기 상태 → 준비 상태: ex) 입출력의 종료

4) 실행 상태 → 종료 상태: ex) 프로세스의 종료

* 1)과 4)의 경우에만 스케줄링이 발생하면 비선점(nonpreemptive)이라 하고, 그렇지 않으면 선점(preemptive)이라고 함

▶ 선점 알고리즘의 특징

- 선점 스케줄링을 위해 타이머와 같은 특정 하드웨어를 요구할 수 있음

- 동기화를 위한 비용 증가: 공유 자료에 대한 접근 조정 필요 → 6장 참조

  ex) 선점을 한 프로세스가 이전 프로세스가 조작 중이었던 자료에 접근해선 안됨

- 커널 자료구조의 불일치를 방지하기 위해, 문맥교환을 수행하기 전에 시스템 호출이 완료되거나 I/O 요청이 완료되기를 기다려야 함: 그러나 이 방법은 멀티프로세싱과 실시간 컴퓨팅을 지원하기에는 부적합함 → 5.4-5.5절 참조

5.1.4 디스패처(Dispatcher)

▶ 디스패처: 중앙처리장치의 제어를 단기 스케줄러가 선택한 프로세스에게 부여하는 모듈

- 문맥 교환

- 사용자 모드로 전환

- 사용자 프로그램의 적절한 위치로 이동

▶ 디스패치 지연(dispatch latency): 디스패처가 한 프로세스를 중단시키고 다른 프로세스의 수행을 시작하도록 하는 시간

→ 가능한 짧아야 함

5.2 스케줄링 기준(Scheduling Criteria)

▶ 기준

① 중앙처리장치 이용률(utilization): CPU 수행 시간/시스템 구동 시간 (%) (↑)

② 처리율(throughput): 단위 시간당 완료되는 프로세스 수 (↑)

③ 반환 시간(turnaround time): 프로세스가 시스템에 진입하여 완료되기까지의 시간 (↓)

- 기억장치에 들어가는 시간

- 준비 큐에서 대기하는 시간 → “④에 해당”

- 중앙처리장치에서의 실행 시간

- 입출력 시간

④ 대기 시간(waiting time): 준비 큐에서 대기하는 시간 (↓)

→ 중앙처리장치 스케줄링 알고리즘에 따라 실질적으로 영향받는 요소임

⑤ 반응 시간(response time): 작업을 제출한 후 첫 응답이 나올 때까지의 시간 (↓)

→ 대화식 시스템의 경우 반환 시간보다 적합

▶ 대부분의 경우에는 평균을 최적화하지만, 균일한 서비스를 제공하기 위해서는 최대나 최소를 최적화하는 것이 바람직함

ex) 대화형 시스템(시분할 시스템)의 경우, 응답 시간을 예측할 수 있도록 평균 응답 시간보다는 응답 시간의 변동폭을 최적화하는 것이 바람직함

▶ 본 장에서 사용하는 기준: “평균 대기 시간”

5.3 스케줄링 알고리즘(Scheduling Algorithm)

5.3.1 선입 선처리 스케줄링(First-Come First-Served; FCFS Scheduling)

▶ 개념: 중앙처리장치를 요구하는 순으로 할당

→ 선입선출(FIFO) 큐로 구현, 제일 간단

▶ (예1) 프로세스  CPU 버스트 시간(msec)

           P1          24

           P2           3

           P3           3

1) 작업 P1, P2, P3의 순으로 들어 온 경우: p.142의 첫 번째 간트 차트(Gantt chart)

→ 평균 대기 시간 = (0 + 24 + 27) / 3 = 17

2) 작업 P2, P3, P1의 순으로 들어 온 경우: p.142의 두 번째 간트 차트(Gantt chart)

→ 평균 대기 시간 = (6 + 0 + 3) / 3 = 3

▶ (예2) 하나의 중앙처리장치 중심 작업과 다수의 입출력 중심 작업이 존재하는 경우

→ ‘호위 효과(convey effect)’: 

  CPU 중심 작업이 수행되는 동안 다수의 입출력 중심 작업이 준비 큐에서 기다리게 되고, CPU 중심 작업이 입출력을 하는 동안 다수의 입출력 중심 작업은 수행을 신속히 마치고 장치 큐에서 기다리게 됨

5.3.2 최소 작업 우선 스케줄링(Shortest-Job-First; SJF Scheduling)

▶ 개념: 중앙처리장치 버스트 시간이 가장 작은 프로세스를 선택

        단, 동일할 경우는 선입선출 스케줄링을 적용

→ 최적 알고리즘: 평균 대기 시간을 최소로 함

▶ (예) 프로세스  CPU 버스트 시간

          P1             6

          P2             8

          P3             7

          P4             3

→ P.143의 간트 차트: 평균 대기 시간 = (3 + 16 + 9 + 0) / 4 = 7

   cf. 선입선출 스케줄링의 경우: (0 + 6 + 14 + 21) / 4 = 10.25

▶ 단점: CPU 버스트 시간을 예상하기 어려움

→ 차기 버스트 시간의 예측: 이전 버스트 시간의 지수적 평균

  

    -  → 최근 상황을 전혀 고려하지 않음

    -  → 최근 상황만 고려함

    -  → 최근 상황과 과거 상황을 동등하게 고려함

    [그림 5.3] 다음 중앙처리장치 버스트의 길이 추정

  

           ---------------------------------> 영향이 지수적으로 점점 감소함

▶ 선점 SJF 스케줄링: 최소 잔여 시간 우선(Shortest Remaining Time First) 스케줄링

▶ (예) 프로세스  도착 시간  버스트 시간

          P1         0           8

          P2         1           4

          P3         2           9

          P4         3           5

1) 선점 SJF의 경우: p.146의 간트 차트

평균 대기 시간 = [(10-1) + (1-1) + (17-2) + (5-3)] / 4 = 26 / 4 = 6.5

2) 비선점 SJF의 경우: 

       P1         P2     P4           P3

  0           8      12       17             26

평균 대기 시간 = [(0-0) + (8-1) + (17-2) + (12-3)] / 4 = 31 / 4 = 7.75

5.3.3 우선 순위 스케줄링(Priority Scheduling)

▶ 개념: 우선 순위가 높은 프로세스에 CPU 할당

        단, 동일한 경우에는 FCFS로 처리

▶ SJF: 우선 순위 p가 차기 버스트 시간의 예상치 의 역수인 경우

→ 즉, 

▶ (예) 프로세스  버스트 시간  우선 순위(작을수록 높은 우선 순위인 경우)

          P1         10           3

          P2          1           1

          P3          2           3

          P4          1           4

          P5          5           2

1) 비선점 우선 순위의 경우: p.147의 간트 차트

평균 대기 시간 = [(6-0) + (0-0) + (16-0) + (18-0) + (1-0)] / 5 = 41 / 5 = 8.2

2) 선점 우선 순위의 경우: 동일(동일한 시간에 들어왔기 때문)

▶ 우선 순위의 종류

- 내부적 요소: 제한 시간, 기억 장소 요구량, 개방된 파일 수, 평균 입출력 버스트와 평균 CPU 버스트의 비율 등

- 외부적 요소: 프로세스의 중요성, 사용료, 담당 부서, 정책적인 요인 등

▶ 문제점: ‘무한 봉쇄(indefinite blocking)’ 또는 ‘기아 상태(starvation)’

  부하가 큰 시스템에서 우선 순위가 낮은 작업이 무한정 CPU를 기다리거나 심지어 시스템 고장으로 유실되는 현상

→ 해결책: “에이징(aging)” - 체류 시간에 비례하여 우선 순위를 높여 주는 방법

5.3.4 라운드 로빈 스케줄링(Round-Robin Scheduling)

▶ 개념: 원형 준비 상태 큐의 각 프로세스에 일정한 시간량(time quantum) 혹은 시간 할당량(time slice)씩 CPU를 할당하는 선점 알고리즘

→ 시분할 시스템에서 사용

▶ 중앙처리 버스트와 시간 할당량과의 관계

- 시간 할당량 이내에 프로세스가 끝나거나 입출력을 요구한 경우: 프로세스를 큐에서 제거하고 즉시 다음 작업 시작

- 시간 할당량보다 CPU 버스트 시간이 큰 경우: 운영체제에 의해 인터럽트되고 중단된 프로세스는 큐의 맨 뒤로 이동함

▶ (예) 프로세스  버스트 시간  (시간량 = 4)

          P1         24

          P2          3

          P3          3

→ p.149의 간트 도표

  평균 대기 시간 = (6 + 4 + 7) / 3 = 17 / 3 = 5.66

▶ 시간 할당량(q)

- 大: FCFS

- 小: 프로세서 공유(processor sharing)

→ 단일 프로세서가 v 속도인 경우, n개의 프로세서가 v/n의 속도로 실행하는 것과 동일한 효과

ex) CDC(Control Data Corporation)에서 한 세트의 하드웨어와 10 세트의 레지스터로 10개의 주변장치 프로세서들을 구현

▶ 문맥 교환(context switch)과 시간 할당량의 관계

[그림 5.4] 시간 할당량이 작을수록 문맥 교환이 증가함을 나타냄

→ 규정 시간량을 문맥 교환에 소요되는 시간보다 충분히 크게 하는 것이 바람직함

▶ 반환 시간(turn around time)과 시간 할당량의 관계

[그림 5.5] 시간 할당량에 따라 반환 시간이 다양하게 변화함을 나타냄

→ 한 프로세스 집합에 대해, 시간 할당량이 증가할수록 평균 반환 시간이 반드시 개선되는 것은 아님

▶ 대체적으로 중앙처리장치 버스트의 80%는 시간 할당량보다 짧아야 함

5.3.5 다단계 큐 스케줄링(Multilevel Queue Scheduling)

▶ 개념: 기억장치 요구량, 프로세스 우선순위, 프로세스 유형과 같은 프로세스들의 특성에 따라 여러 준비 상태 큐 중에서 한 곳에 넣고, 각 큐마다 고유의 스케줄링 알고리즘을 채택하는 방식

[그림 5.6] 다단계 큐 스케줄링

▶ 전면 작업(foreground job) ↔ 후면 작업(background job)

- 전면 작업(대화형): 반응 시간 짧음 → 라운드로빈 스케줄링

- 후면 작업(일괄처리형): 반응 시간 긺 → 선입선출(FCFS) 스케줄링 

→ 전면 작업이 후면 작업보다 높은 우선 순위를 가짐

▶ 큐들간의 스케줄링 방법

1) 고정 우선 순위 선점 스케줄링: 전면 작업 > 후면 작업

2) 큐들간의 시간 분배: 전면 작업-80%, 후면 작업-20%

5.3.6 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

▶ 개념: 프로세스가 들어가는 큐가 고정되지 않고 큐 사이를 이동 가능하게 함으로써, 서로 다른 CPU 버스트 특성을 가진 프로세스들을 분리시킬 수 있게 하는 방식

- CPU 버스트 시간이 큰 경우, 시간 할당량이 크고 우선 순위가 낮은 단계 큐로 이동

- 낮은 우선 순위 큐에서 오래 기다린 경우, 시간 할당량이 작고 우선 순위가 높은 단계 큐로 이동

▶ 고려 사항: (예) [그림 5.7] 다단계 귀환 큐

① 큐의 수: ex) 3개

② 각 큐에 대한 스케줄링 알고리즘: ex) 0-1: 라운드 로빈, 2: FCFS

③ 작업을 보다 높은 우선 순위의 큐로 올려주는 시기를 결정하는 방법: ex) 없음(aging 가능)

④ 작업을 보다 낮은 우선 순위의 큐로 내려주는 시기를 결정하는 방법: ex) 시간 할당량 초과시

⑤ 프로세스가 서비스를 필요로 할 때 들어가게 될 큐를 결정하는 방법: ex) 최상단 큐

5.4 다중 프로세서 스케줄링(Multiple-Processor Scheduling)

▶ 개념: 여러 개의 CPU가 존재하는 경우

▶ 이종 시스템(heterogeneous system): 다수의 처리기가 서로 다른 시스템

→ 처리기별로 독자적인 큐와 스케줄링 알고리즘을 가지며, 프로세스들은 처리기별로 분류되어 처리됨

▶ 동종 시스템(homogeneous system): 다수의 처리기가 동일한 시스템

→ ‘부하 공유(load sharing)’

① 독립된 준비 상태 큐를 두는 방법

큐

processor 1

② 공통의 준비 상태 큐를 두는 방법

  2-1) 동등 관계: 각 처리기별로 별개의 스케줄링 알고리즘 사용

공통 큐

processor1

  2-2) 주종 관계: master에 의한 공통의 스케줄링 알고리즘 사용

공통 큐

slave1

master

5.5 실시간 스케줄링(Real-Time Scheduling)

▶ 경성 실시간 시스템(hard real-time system): 정해진 시간내에 특정 작업이 완료되기를 요구

- 프로세스가 작업 완료나 입출력 수행에 필요한 시간의 양을 제출하면,

- 스케줄러는 프로세스가 정해진 시간에 완료되는 것이 보장될 경우 수행하고, 그렇지 않으면 거절

- 이를 위해, 각 동작에 소요되는 최대 시간을 알고 있어야 함

→ 특수 시스템에서 사용(범용의 운영체제 시스템에서는 사용 안함)

▶ 연성 실시간 시스템(soft real-time system): 중요한 프로세스가 높은 우선 순위를 갖게 하는 방법

(요구 사항)

1) 우선 순위 스케줄링을 제공하고, 실시간 프로세스는 가장 높은 우선 순위를 유지해야 함: 에이징을 허용하지 않음

2) 디스패치 지연이 적어야 함: 문맥 교환 직전에 시스템 호출이 요구되거나 입출력이 발생할 경우 대기해야 하는 문제의 해결

① 시스템 호출에 선점 지점(preemption point)를 삽입하여 대기 시간을 줄임

② 커널 전체를 선점 가능하도록 하고, 동기화 기법을 사용함

▶ 디스패치 지연의 구성: [그림 5.8] 디스패치 지연

→ ‘대립(conflicts)’의 요소

- 커널에서 수행되고 있는 프로세스의 선점

- 높은 우선 순위 프로세스가 필요로 하는 경우, 낮은 우선 순위 프로세스의 자원 해제

- 현재 프로세스에서 높은 우선 순위 프로세스로의 문맥 교환

5.6 알고리즘의 평가(Algorithm Evaluation)

▶ 일반적으로 스케줄링 알고리즘의 선택은 매우 어려움

→ 우선, 스케줄링 알고리즘의 선택 기준(5.2절)을 결정해야 함

ex) 평균 대기 시간

5.6.1 결정적 모형(Deterministic Modeling)

▶ 개념: 특정 작업 부하에 대한 알고리즘의 성능을 평가하는 분석적 방법”

▶ 예: 프로세스  버스트 시간

         P1          10

         P2          29

         P3           3

         P4           7

         P5          12

- 간트 차트: p.158-159

① FCFS의 경우: 평균 대기 시간 = (0+10+39+42+49)/5 = 28

② 비선점 SJF의 경우: 평균 대기 시간 = (10+32+0+3+20)/5 = 13

③ 라운드 로빈(시간 할당량 = 10)의 경우: 평균 대기 시간 = (0+32+20+23+40)/5 = 23

- 일반적으로 결정성 모형은 매우 특수하고 정확한 지식을 필요로 하기 때문에 사용하기에 곤란함

5.6.2 큐잉 모형(Queueing Model)

▶ 개념: 작업들에 대한 CPU 버스트와 I/O 버스트의 분포, 그리고 작업의 도착 시간 분포로부터 근사치나 추정치를 구하고, 이를 토대로 평균 처리율, 사용율, 대기 시간 등을 계산하는 분석적 방법

→ ‘큐잉 네트워크 분석’: 큐잉 분석은 스케줄링 알고리즘을 비교하는데 유용하지만, 적용할 수 있는 알고리즘과 분포의 종류에 한계가 있음

5.6.3 모의 실험(Simulation)

▶ 개념: 컴퓨터 시스템 모형의 프로그램을 이용하여 통계적으로 분석하는 방법

- 난수 발생기(random number generator): 균일(uniform), 지수(exponential), 포아송(poisson)의 수학적으로 혹은 경험적으로 결정

- 추적 테이프(trace tape): [그림 5.9] 모의 실험에 의한 중앙처리장치 스케줄러의 평가

→ 모의 실험을 위한 컴퓨터 사용 시간의 비용이 크고, 추적 테이프를 사용하는 경우는 대량의 기억 공간을 요구함

5.6.4 구현(Implementation)

▶ 개념: 실제 코드로 작성해 운영체제에 넣고 실행해보는 방법

→ 고비용