CPU 스케줄링 (CPU Scheduling)

■ CPU 스케줄링 (CPU Scheduling)

 - CPU 자원을 프로세스(Process)에게 어떻게 배당할 것인지 결정하는 작업을 CPU 스케줄링이라 함

 - 프로세스 작업 수행을 위해 언제, 어느 프로세스에 CPU를 할당할 것인지를 결정하는 작업

 - Multi-Processor 환경에서 Processor 간의 우선순위를 지정함으로써 CPU 활용을 극대화하기 위한 방법

 

 ★ 스케줄링 평가 기준

기준	설명
CPU 사용률 (CPU Utilization) 극대화	전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
처리능력 (Throughput) 최대화	CPU가 단위 시간당 처리하는 프로세스의 개수
응답시간 (Response TIme) 최소화	대화식 시스템에서 요청 후 응답이 오기 시작할 때가지의 시간
대기시간 (Waiting Time) 최소화	프로세스가 준비 큐(Ready Queue) 내에서 대기하는 시간의 총합
반환시간 (Turnaround Time) 최소화	프로세스가 시작해서 끝날 때가지 걸리는 시간

 

 ★ Scheduler의 종류 및 역할

 

종류	역할
Scheduling Queue	- 주기억장치의 할당을 기다림(보류상태, 디스크에 위치)
장기(Long-term) Scheduler  = 작업(Job) Scheduler	- 스케줄러 원칙(알고리즘)에 따라 디스크 내의 작업을 어떤 순서로 메모리에 가져 올지 결정하는 프로그램 - 디스크와 같은 저장장치에 작업들을 저장해 놓고, 필요할 때 실행할 작업을 ready queue에서 꺼내 메모리에 적재한다 - 프로세스 선택, 주기억장치 할당(보류준비)
중기(Medium term) Scheduler	- 중기 스케줄러를 사용해 메모리에서 CPU를 쓰기 위해 경쟁하고 있는 프로세스들을 몇 개 줄여서 다중 프로그래밍의 정도를 완화하는 것이다 - 그리고 후에 다시 메모리로 불러와서 중단되었던 지점부터 다시 실행한다(스와핑 기법) - 새로운 프로세스를 계속해서 준비 큐에 넣는 것보다 시스템의 프로세스 수에 따라서 디스크로부터 교체 입ㆍ출력되는 프로세스를 조절하게 한다(대기보류)
단기(Short term) Scheduler	- 어떤 작업이 시스템의 자원을 차지할 것인가를 결정(큐에 적재)한다 - 실행 준비된 프로세스에 CPU 할당(준비실행)

 

 ★ 프로세스 우선순위와 스케줄링

  - 각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행한다

  - 우선순위가 다른 두 프로세스를 동시 실행할 때, 우선순위가 높은 프로세스가 작업을 마치지 않는다면(블로킹 상태가 되거나 I/O 작업을 하지 않는다면) 우선순위가 낮은 프로세스는 실행되지 않는다

  - 우선순위 값이 클수록 우선순위는 높다

  ⓐ public static final int MAX_PRIORITY=10 // 최대 우선순위

  ⓑ public static final int MIN_PRIORITY=1 // 최소 우선순위

  ⓒ public static final int NORM_PRIORITY=5 // 보통 우선순위 (기본값)

 

 ★ 프로세스 스케줄링 분류

 

 1. 선점 스케줄링

  - 선점(Preemptive) 스케줄링 기법은 한 프로세스가 CPU를 차지하고 있을 때 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 기법이다(선점은 일하고 있는 걸 끄집어 낼 수 있다)

  - 선점이라는 말의 뜻이 프로세스가 CPU 자원을 선점한다는 의미가 아니고, OS가 프로세스 자원을 선점하고 있다는 뜻이다

  - 선점 스케줄링 기법에는 RR(Round-Robin), SRT(Shortest-Remaining-Time), MLQ(Multi-Level Queue), MFQ(Multi-Level Feedback Queue) 등이 있다t

 

 2. 비선점 스케줄링

  - 비선점(Non-preemptive) 스케줄링 기법은 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 그 프로세스로부터 뺏을 수 없는 기법이다 (비선점은 일하는 걸 끄집어 낼 수 있다)

  - 비선점 스케줄링 기법에는 FCFS(First Come First Service), SJF(Shortest-Job-First), HRN(Highest Response-ratio Next) 등이 있다

 

구분	선점(Preemptive) 스케줄링	비선점(Non-preemptive) 스케줄링
개념	- 특정 프로세스가 CPU를 독점하는 것은 불가능 - 운영체제가 강제로 프로세스의 CPU 점유율 제어	- 프로세스가 CPU를 독점하는 것이 가능 - 프로세스가 스스로 CPU 점유를 포기해야 다른 프로세스가 실행
장점	- 비교적 빠른 응답 - 대화식 시분할 시스템에 적합	- 응답시간 예상이 용이 - 모든 프로세스에 대한 요구를 공정하게 처리
단점	- 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래 - 작업완료시간 예측이 어려움	- 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기 - 우선순위가 높은 프로세스의 처리 지연
종류	SRT, Round Robin, MLQ, MFG	FIFO, SJF, HRN

 

■ 프로세스 스케줄링 알고리즘

 

1. SRT (Shortest Remaining Time) 스케줄링

 - 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다

 - 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점된다

 - 긴 작업은 SJF보다 대기시간이 길다

 

2. RR (Round Robin, 순환할당) 스케줄링

 - 대화식 사용자를 위한 시분할 시스템(Time Sharing System)을 위해 고안되었다

 - 준비 큐(FCFS)에 의해 보내진 각 프로세스는 같은 크기의 CPU 시간을 할당 받는다

 - 일정한 시간 할당량 만큼 CPU를 점유하고 시간 할당량을 초과하면 다시 준비 큐로 되돌아온다

 - RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우 시간 할당량이 매우 크면 RR정책은 FCFS(선입선처리) 정책과 같다. 이와 반대로 시간 할당량이 매우 적다면 RR정책은 매우 많은 문맥 교환을 야기한다

 - 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 큐 리스트의 가장 뒤로 보내지고 CPU는 대기 중인 다음 프로세스로 넘어간다

 - 할당시간이 가장 중요하며, 일반적으로 시간 할당량은 100밀리 초에서 1, 2초 사이 값이다

 

3. MLQ (Multi-level Queue, 다단계 큐) 스케줄링

 - 각 작업들이 서로 다른 묶음으로 분류할 때 사용하는 알고리즘

 - 전면 작업은 후면 작업에 비해 높은 우선순위를 갖는 경우가 많다

 - 각 큐는 자신만의 독자적인 스케줄링을 가지며 다른 큐로 작업 이동이 불가능하다

 

4. MFQ (Multi-level Feedback Queue, 다단계 피드백 큐) 스케줄링

 - 프로세스는 CPU의 사용시간에 따라 입ㆍ출력 위주와 CPU 위주로 구분할 수 있다

 - 입ㆍ출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU Time Slice(Quantum)를 부여한다

 - 프로세스가 큐 사이를 이동하는 기법으로 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동(맨 마지막 단계에서는 Round Robin 처리)한다

 - 하위단계일수록 할당시간은 증가(공평성 부여)한다

 - UNIX 시스템은 다단계 피드백 큐 방식을 스케줄링 알고리즘으로 채택하고 있다

 

5. FCFS (First Come FIrst Service) 스케줄링 = FIFO (First Input First Out)

 - 가장 간단한 스케줄링 알고리즘으로 FIFO(First Input First Out) 큐로 쉽게 관리할 수 있다

 - 프로세스가 대기 큐(준비 큐)에 도착한 순서에 따라 CPU가 할당된다

 - Convoy Effect 발생 가능 (Burst Time이 긴 프로세스가 CPU 독점)

 - 단독적 사용이 거의 없으며, 다른 스케줄링 알고리즘에 보조적으로 사용(우선순위 스케줄링, RR 스케줄링 등) 한다

 

6. SJF (Shortest Job First, 최소작업우선) 스케줄링

 - 준비 큐 내의 작업 중 수행시간이 가장 짧다고 판단되는 것을 먼저 수행하는 방식이다

 - 각 프로세스에서 CPU 버스트 길이를 비교하여 CPU가 이용 가능해지면 가장 작은 CPU 버스트를 가진 프로세스를 할당한다

 - 주어진 프로세스 집합에 대해서 평균대기시간이 최소가 되는 최적 알고리즘이다

 - CPU 요구시간이 긴 작업과 짧은 작업 간의 불평등이 심하여, CPU 요구시간이 긴 프로세스는 기아(Starvation)가 발생하며 HRN 스케줄링을 사용한다

 

7. HRN (Highest Response ratio Next) 스케줄링

 - SJF의 약점을 보완한 기법으로 특히 긴 작업과 짧은 작업 간의 불평등을 완화한 기법이다

 - Response Ratio = [대기시간+서비스 시간]/서비스 시간

 - 대기 중인 프로세스 중 현재 Response Ratio가 가장 높은 것을 선택한다

 

※ 각 스케줄링 방식 비교

종류	방법	특징	비교
SRT	- 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행하는 방법	- 작업 처리는 SJF와 같이 작은 작업에 유리하다 - 긴 작업은 SJF보다 대기시간이 길다	선점
Round Robin	- FIFO 방식의 변형으로 일정한 시간을 부여하는 방법	- 할당시간이 크면 FIFO와 같다 - 시분할 방식에 효과적이다 - 할당시간이 작으면 문맥교환이 자주 발생한다	선점
MLQ	- 서로 다른 작업을 각각의 큐에서 Timeslice로 처리하는 방법	- 각각의 큐는 독자적인 스케줄링 알고리즘을 사용한다	선점
MFQ	- 하나의 준비상태 큐를 통하여 여러 개의 큐를 거쳐 일을 처리하는 방법	- CPU와 I/O 장치의 효율을 높일 수 있다	선점
FCFS	- 작업이 시스템에 들어오는 순서대로 수행하는 방법	- 간단하고 공평하다 - 반응속도 예측 가능 - 대화형에 부적합하다	비선점
SJF	- 준비 큐 내의 작업 중 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행하는 방법	- 작은 작업에 유리 - 큰 작업에는 상당한 시간이 걸린다	비선점
HRN	- SJF의 약점인 큰 작업에 시간이 오래 걸리는 점을 보완한 방법	- 에이징 기법으로 기아상태 해결	비선점