CH6. CPU Scheduling

#Basic Concepts

CPU 스케줄링: 다중 프로그램 운영체제의 기본

ㄴ다중 프로그램 목적: CPU 이용률 최대화

*CPU-I/O Burst Cycle

프로세스 실행: CPU 실행-입출력 대기의 사이클(CPU burst -> I/O burst)

 

-CPU-burst 시간의 히스토그램

주요 관심사: CPU burst 분포

ㄴ짧은 CPU burst ↑ (입출력 중심의 프로그램이 전형적으로 가짐)

*CPU 스케줄러(Short-term scheduler)

: CPU가 유휴 상태 시, 준비 큐에 있는 프로세스들 중 하나의 프로세스 선택

CPU를 그 프로세스에게 할당/ 큐는 다양한 방식으로 정렬 가능O

 

-CPU 스케줄링 결정이 발생하는 4가지 상황

1) running -> waiting

2) running -> ready

3) waiting -> ready

4) terminated

 

-CPU 스케줄링 시, 고려할 점

: 공유 데이터에 대한 접근 고려/ 커널 모드에 있는 동안 선점 고려/

아주 중요한 OS 작업 중에 인터럽트가 발생할 수 있다는 것 고려

*디스패처(Dispatcher)

: CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈

문맥 교환/ 사용자 모드로 전환/

프로그램을 다시 시작하기 위해 사용자 프로그램의 올바른 위치로 jump

 

-디스패처 지연(Dispatch latency)

: 디스패처가 하나의 프로세스를 중단시키고

다른 프로세스를 실행시키는 데까지 소요되는 시간

 

#Scheduling Criteria

-CPU 이용률(utilization)

: 가능한 CPU를 최대한 바쁘게 유지(40%-90%)

 

-처리량(throughput)

: 단위 시간당 완료된 프로세스의 개수

 

-총 처리 시간(turnaround time)

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

/ 메모리 대기 시간 + 준비 완료 큐 대기 시간 + CPU 시간 + 입출력 시간

 

-대기 시간(waiting time)

: 준비 완료 큐에서 대기하면서 보낸 시간의 합

 

-응답 시간(response time)

: 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간

/ 응답을 출력하는 데 걸리는 시간X

 

#Scheduling Alogorithms

*First-Come, First-Served (FCFS) 스케줄링

-호위 효과(Convoy effect)

: 긴 프로세스 다음에 존재하는 짧은 프로세스들이 겪는 효과

Case: 한 개의 CPU-집중 프로세스와 많은 입출력 집중 프로세스

ㄴCPU 장치 이용률 저하

*Shortest-Job-First (SJF) 스케줄링

: 준비 완료 큐에 있는 프로세스의 burst 길이 기준으로 가장 짧은 시간을 가진 프로세스를 스케줄

SJF는 개념적으로 최적의 스케줄러

: 주어진 프로세스 집합에 대해 언제나 최소의 평균 대기 시간 보장

=> 문제: 다음 CPU burst의 시간 어떻게 아는가?

 

-다음 CPU burst의 길이 결정

오직 길이 추정

다음 CPU burst 길이가 이전과 비슷하다고 가정

근사값이 가장 짧은 예상 CPU 버스트를 가진 프로세스 선택

지수 평균 이용

 

비선점 OR 선점

: 선점_최소 잔여 시간 우선(shortest-remaining-time-first)

*Priority (우선순위) 스케줄링

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

ㄴ우선순위 숫자(int형)가 각 프로세스에게 주어짐

/ 우선순위 같음 -> 선입선출/ 선점형 OR 비선점형

SJF = 우선순위 스케줄링_다음 CPU burst 예상 시간의 역수가 우선순위

문제: starvation_낮은 우선순위 프로세스는 실행되지 않을 수O

해결책: aging(노화)_일정한 시간마다 프로세스의 우선순위를 증가시킴

*Round-Robin 스케줄링

: 시분할 시스템 위해 설계

CPU 시간 할당량(time quantum q) 할당

보통 10-100 milliseconds

이 시간이 경과되면 프로세스는 선점되고 준비 큐의 마지막에 추가

시간 할당량 경과될 때마다 인터럽트(timer) 발생

 

-성능

q ↑ -> FIFO에 가까워 짐

q ↓ -> 오버헤드가 너무 큼

q는 문맥 교환 시간에 비해 충분히 커야 함

/ 보통 10ms < q < 100ms, 문맥 교환 시간 < 10usec

일반적으로 SJF 보다 총처리시간 ↑ but, 응답시간 더 좋음

-시간 할당량이 4인 RR예제

-시간 할당량과 문맥 교환 시간

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

프로세스 분류: foreground(interactive)/ background(batch)

준비 완료 큐 -> 다수의 큐로 분류

ㄴ프로세스는 지정된 큐에 영구적으로 할당

/ 각 큐는 각자의 스케줄링 알고리즘 고정

(foreground: RR/ background: FCFS)

*큐-큐 사이 스케줄링

-고정 우선순위 스케줄링

foreground 큐 프로세스 모드 스케줄 -> background 큐의 프로세스 스케줄

/ 기아 발생 가능O

 

-시간 할당

각 큐 일정량의 CPU 시간 할당

/ foreground 큐: 80% CPU 시간 할당 받음 -> RR 방식 스케줄링

/ background 큐: 20% 시간 할당 받음 -> FCFS 방식 스케줄링

highest priority

system processes > interactive processes > interactive editing processes

> batch processes > student processes

lowest priority

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

프로세스는 여러 큐 사이 이동

-다단계 피드백 큐 스케줄러 정의되는 매개변수 종류

큐의 개수/ 각 큐에서 사용하는 스케줄링 알고리즘

/ 프로세스 업그레이드 시기를 결정하는 데 사용되는 방법

/ 프로세스를 강등시키는 시기를 결정하는 데 사용되는 방법

/ 프로세스가 서비스를 받기 위해 들어갈 큐를 결정하는 데 사용되는 방법

 

-예제

세 개의 큐:

Q0 – 시간 할당량이 8인 RR

Q1 – 시간 할당량이 16인 RR

Q2 – FCFS

(스케줄링 예)

새로운 잡은 Q0로 진입

CPU를 얻게 되면 tim quantum 8 동안 실행

time quantum 8 후에 종료X -> 작업 Q1로 이동

time quantum 16 후에 종료X -> Q2로 이동

=> CPU brust가 긴 프로세스는 자동적으로 우선순위가 낮아짐