[OS] 운영체제(7장) CPU 스케줄링

1. 기본 개념

multiprogramming의 목적

• CPU 이용률 최대화

CPU-I/O Burst Cycle

• 프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성됨

CPU burst 분포

• (see next page)

CPU-burst 시간의 분포도

CPU Scheduler

ready queue에 있는 프로세스들 중 하나를 선택하여 이 프로세스에게 CPU를 할당함

CPU Scheduling 시점

CPU scheduling 결정은 process가 다음 상황일 때 발생 가능함

1. running 상태에서 waiting 상태로 전환 (예. I/O wait, child termination wait)
2. running 상태에서 ready 상태로 전환. (e.g. time-out)
3. waiting 상태에서 ready 상태로 전환. (e.g. I/O completion, event occur)
4. Terminate.

비선점(non-preemptive) 스케줄링 – cooperative 스케줄링

• 1번, 4번 경우는 선택의 여지가 없으며, 이 경우에만 스케줄링
  • 반드시 스케줄링하여 새 프로세스를 선택해야 함
  • 프로세스는 종료하거나 block될 때까지 CPU를 계속 점유
• (예) windows 3.x, 예전 Mac OS

선점(preemptive) 스케줄링

• 모든 경우에 스케줄링이 가능(2, 3번 경우 포함)
• CPU 독점을 방지하거나(timer 사용), 프로세스 우선순위를 반영하고자 할 때 2, 3번의 경우(ready queue가 변화)에 스케줄링 할 수 있음
• (예) 대부분의 현대 OS

Preemptive 스케줄링의 문제점과 해결책

• 공유 데이터의 일관성(consistence) 유지 문제
  • 선점 스케줄링 방식에서, process는 프로세스는 데이터를 변경하는 도중에 다 른 프로세스에게 선점되어 변경된 데이터를 저장하기 전에 CPU를 내어놓을 수 있다.
  • 다수의 프로세스가 데이터를 공유할 때에 경쟁적으로 데이터를 변경하면 데이터 일관성이 유지되지 않을 수가 있다. → 경쟁조건
  • 해결책 : 공유 데이터 접근에 대한 조정이 필요 → 동기화 방식 (5장)

user mode에서의 preemption

• 선점형스케줄링 을 하는 운영체제에서, 한 프로세스가 데이터를 변경하는 동안 선점되어 다른 프로세스가 같은 데이터를 읽거나 수정한다면 데이터 일관성이 유지되지 않을 수 있음

• 사용자 프로그램은 운영체제가 제공하는 동기화 방식을 사용하여 데이터 일관성 문제가 발생하지 않도록 작성해야 한다

Kernel mode에서의 preemption

Kernel mode에서의 공유 데이터 접근 문제

• 모든 커널 루틴은 커널 데이터를 공유함
• 커널은 system call을 통하여 요청된 프로세스의 작업을 처리할 수 있으며, 공유 데이터를 접근하는 커널 루틴이 실행되는 동안에, 인터럽트로 인해서 다른 커널 루틴에게 선점되면 공유 데이터 일관성 유지가 되지 않을 수 있다.
• 커널에서의 이러한 문제 발생은 시스템 전체에 영향을 주므로 위험함

운영체제 커널에서의 preemption 처리 방법

• 비선점형 커널 - 커널 내에서의 preemption을 허용하지 않음 (1) system call이 완료되거나 (2) I/O block 이 발생할 때까지 기다린 후에 context switching 을 수행

  • 실시간 컴퓨팅을 지원하는 데 부적합

• 선점형 커널 - 커널 내에서 preemption 을 허용

  • 커널 내에서 공유 데이터 접근에 대한 동기화 를 사용하여 커널을 작성해야 함

  • 실시간 컴퓨팅 지원에 적합

디스패처

• CPU의 제어권을 CPU 스케줄러가 선택한 프로세스에게 주는 모듈

• 다음작업 수행

  • context 스위칭
  • CPU
  • 동작 모드를 user mode 로 전환

• 선택한 프로세스가 다시 시작하도록 , user program 의 적절한 위치로 이동(jump)

Dispatch 지연(latency)

• 한프로세스를 정지하고 , 다른 프로세스의 수행을 시작할 때까지 소요되는 시간

• dispatch latency은 가능한 한 작아야 함( 빠르게 동작)

2. Scheduling기준(Criteria)

• CPU 이용률(utilization)

  • 0 – 100% (CPU를 가능한 한 바쁘게 유지)

• 처리량(Throughput)

  • 단위 시간당 수행이 완료된 프로세스

• 총 처리시간(Turnaround time)

  • 프로세스를 실행하는 데 소요된 시간

• 대기시간(Waiting time)

  • ready queue에서 대기하는 시간 (CPU 실행과 I/O 대기가 아닌 시간)

• 응답시간(Response time)

  • 대화형 시스템에서 요청을 한 후에 (첫 번째) 응답을 받을 때까지의 소요시간 (최종 출력을 얻는 시간이 아님)

최적화 기준

• 스케줄링 알고리즘 최적화 기준

  • CPU 이용률과 처리량 : 최대화
  • 총 처리 시간, 대기 시간, 응답 시간 : 최소화

• 최적화하는 값

  • 대부분의 경우 평균값을 최적화
  • 일부 경우에는 평균값 대신에 최대값 또는 최소값을 최적화
  • 대화형 시스템은, 응답시간의 변동폭(variance)를 최소화 → 합리적이고 예측 가능한 응답시간 제공

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

First-Come, First-Served (FCFS) Scheduling

호위효과(Convoy effect)

긴 프로세스 뒤에 짧은 프로세스들이 있는 경우에 짧은 프로세스는 긴 프로세스의 CPU busrt가 끝날 때까지 기다려야 함 → 짧은 프로세스들이 먼저 처리되도록 할 때보다 CPU와 장치 이용률이 저하됨

Shortest-Job-First (SJF) Scheduling

• 최단작업 우선(SJF) 스케줄링

  • Shortest Process Next(SPN), Shortest Request Next(SRN)라고도 함
  • 프로세스는 다음 CPU burst 길이가 연관되며 최단 다음 CPU burst를 갖는 프로세스를 스케줄링
  • 문제점 : 다음 CPU burst를 알기 어려움 → 해결책 : 예측(prediction)

• 두 가지 방식의 SJF 스케줄링

  • 비선점 SJF – process는 CPU burst를 끝낼 때까지 선점되지 않음
  • 선점 SJF – (새 프로세스의 CPU burst < 현재 프로세스의 잔여시간) 이면 현재 프로세스가 선점되어 스케줄링 → Shortest-Remaining-Time-First (SRTF). “preemptive SJF = SRTF”

• SJF는 대기시간이 최적임

  • 최소 평균 대기시간을 제공.

Non-Preemptive SJF

Preemptive SJF

다음 CPU Burst 길이 예측

다음 CPU Burst 길이를 미리 알 수 없음

해결책 : 다음 CPU Burst 길이 예측

• 이전 CPU Burst 길이를 사용하여 다음 CPU Burst 길이를 예측
  • 가정: 다음 CPU Burst 길이는 이전의 값과 비슷할 것이다.

예측값 : 지수 평균(exponential average) 사용

우선순위(Priority) Scheduling

• 프로세스는 우선순위 번호와 연관됨
  • 대개 우선순위가 높을 수록 작은 우선순위 번호를 가짐

• CPU는 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당

• 우선순위 정의에 고려되는 요인
  • 내부적 : 시간 제한, 메모리 요구, open file 수, I/O와 CPU의 비율 등
  • 외부적 : 프로세스 중요성, 비용의 유형과 액수, 정치적 요인 등

• 두 가지 방식의 Priority Scheduling – 선점, 비선점

• SJF 스케줄링은 priority 스케줄링의 특별한 경우임

  • priority = 다음 CPU burst time의 예측값 (작을수록 높은 우선순위)

• 문제점 : 기아 상태(starvation)/무한 봉쇄(indefinite blocking)

  • 낮은 우선순위의 process가 무한히 대기하여 수행되지 못할 수 있음
  • 해결책 ➔ 노화(aging)
  • 오랫동안 대기하는 process는 우선순위를 점진적으로 증가시킴

Round Robin (RR) Scheduling

• 시분할 시스템을 위해서 설계됨 – CPU 공유
• 각 프로세스에게 작은 양의 CPU 시간(time quantum) 할당
  • 크기: 대개 10-100 msec
• 실행 프로세스는 이 시간 경과 후 선점되어 ready queue의 끝으로 이동
• 타이머 인터럽트 사용

시간 할당량(time quantum)을 정하는 경험 법칙

• 전체 CPU burst time의 80% 정도가 quantum time보다 짧도록 정함

성능

• SJF 보다는 평균 총 처리시간(turnaround time)이 더 크다.
• 응답시간(response time)이 더 짧다.

다단계 큐 스케줄링

• Ready queue가 여러 개의 큐로 분할됨
• 각 큐는 자신의 스케줄링 알고리즘 사용
  • (예) foreground (interactive)용 큐 – RR background (batch)용 큐 – FCFS

스케줄링은 큐들 간에도 있어야 함

• 고정 우선순위 스케줄링
  • (예) foreground 작업을 모드 처리한 후에 background 작업을 수행
• 기아 상태(starvation) 가능성
  • Time slice – 각 큐마다 CPU 사용량/비율을 정해서 할당
  • (예) foregound 큐에 80%, background 큐에 20% 할당