CPU Scheduling
태그 :
- 개념
- Process 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업 Multi-Processor 환경하에서 Processor 간의 우선순위를 저장함으로써 CPU 활용을 극대화하기 위한 방법
I. CPU의 효율적인 사용, CPU(프로세스) 스케줄링의 개요
가. CPU Scheduling 의 정의
- Process 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업
- Multi-Processor 환경하에서 Processor 간의 우선순위를 저장함으로써 CPU 활용을 극대화하기 위한 방법
나. CPU Scheduling의 기준
- 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스 제공
- I/O Bound와 CPU Bound 프로세스의 적절한 혼용
- Process의 작업형태, 우선순위, Burst시간, 잔여실행시간을 복합적으로 고려
다. CPU Scheduling의 요건(Scheduling Criteria)
|
요건 |
설명 |
|
처리능력 (Throughput) 최대화 |
주어진 시간에 최대한 많은 작업 처리 (처리된 프로세스 수/시간) |
|
반환(경과)시간 (Turnaround time) 최소화 |
전체작업 수행시간을 최소화 (system in à system out 시간) |
|
대기시간 (waiting time) 최소화 |
ready queue에서 기다리는 시간 최소화 |
|
응답시간 (Response time) 최소화 |
대화식 시스템에서 첫 응답까지의 시간 최소화 |
|
CPU 이용률(Utilization) 극대화 |
CPU를 정해진 시간 내 100% 가동 |
II. Process 상태전이도와 Scheduler의 종류 및 역할
가. 프로세스 상태 전이도
나. Scheduler의 종류 및 역할
|
종류 |
역할 |
|
Scheduling Queue |
• 주 기억 장치의 할당을 기다림 (보류상태, 디스크에 위치) |
|
장기(Job) Scheduler |
• 프로세스 선택, 주기억장치 할당 (보류준비) |
|
중기(Process) Scheduler |
• 프로세스 수에 따라 디스크로 보냄 (대기보류) |
|
단기 Scheduler |
• 실행 준비된 프로세스에 CPU 할당 (준비실행) |
III. CPU scheduling 기법과 알고리즘
가. Scheduling 기법
|
구분 |
선점(Preemptive) 스케줄링 |
비선점(Non-preemptive) 스케줄링 |
|
개념 |
- 한 프로세스가 CPU 를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유 가능 - 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 |
- 한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유불가 |
|
장점 |
- 비교적 빠른 응답 - 대화식 시분할 시스템에 적합 |
- 응답시간 예상이 용이 - 모든 프로세스에 대한 요구를 공정하게 처리 |
|
단점 |
- 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래 |
- 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기 |
나. CPU scheduling 알고리즘
1) 선점 스케줄링 알고리즘
|
알고리즘 |
처리방식 |
|---|---|
|
RR |
- Round Robin - 대화식 사용자를 위한 시분할 시스템(Time Sharing System)을 위해 고안 - 준비뷰(FCFS)에 의해 보내진 각 프로세스는 같은 크기의 CPU 시간을 할당 받음 - 프로세스가 할당된 시간 내에 처리 완료 못하면 준비큐 리스트의 가장 뒤로 보내지고 CPU는 대기중인 다음 프로세스로 넘어감 - 할당 시간이 가장 중요하며, 일반적으로 시간 할당량은 100 밀리 초에서 1,2초 사이 값 - 할당시간이 크면 FCFS 와 같게 되고, 작으면 문맥 교환이 자주 발생
|
|
SRT |
- Short Remaining Time - 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 - 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨 - 긴 작업은 SJF 보다 대기 시간이 길다 |
|
다단계 큐 |
- Multi-level Queue - 작업들을 여러 종류의 그룹의 분할 - 여러 개의 큐를 이용 상위단계 작업에 의해 하위단계 작업이 선점 당함 - 준비 상태 큐를 여러 종류로 분할(작업 분류별 묶음) 하지만 다른 큐로 작업 이동 불가 - 각 큐는 자신만의 독자적인 스케줄링을 가짐
|
|
다단계 피드백 큐 |
- Multi-level Feedback Queue - 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU Time Slice (Quantum)를 부여 - 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동 (맨 마지막 단계에서는 Round Robin 처리) - 하위단계일수록 할당시간은 증가 (공평성 부여)
|
2) 다단계 큐와 다단계 피드백 큐의 비교
|
구분 |
다단계 큐 |
다단계 피드백 큐 |
|
대기 큐 Time Quantum |
동일 |
다름 |
|
우선순위 |
작업별 |
순서별 |
|
큐간 이동 |
없음 |
있음 |
|
공통점 |
무한대기방지, 선점 스케줄링 |
|
※ SRT(Shortest Remaining Time First)
- 신규프로세스가 들어오는 시점에 각 프로세스의 남은 시간을 체크
1) 대기시간
- P1 = 1 + 2 = 3, P2 = 0, P3 = 8, P4 = 0, P5 = 3
- 평균 대기시간 = (3 + 8 + 3) / 5 = 2.4
2) 반환시간(turnaround time)
- P1 = 8-0 = 8, P2 = 2-1 = 1, P3 = 16-2 = 14, P4 = 5-3 = 2, P5 = 11-4 = 7
- 평균 반환 시간 = (8 + 1 + 14 + 2 + 7) / 5 = 6.4
3) 비선점 스케줄링 알고리즘
|
알고리즘 |
처리방식 |
|---|---|
|
우선순위 스케줄링 |
- 각 프로세스에 우선순위가 주어지고 우선순위에 따라 CPU 할당 - 동일한 우선순위간은 FCFS 처리 - 우선순위 결정 : 관리자에 의한 결정, 자원요구량에 의한 결정, CPU처리 시간에 의한 결정, 시스템에서 보낸 시간에 의한 결정 등 사용 - 우선순위가 높은 작업이 계속적으로 들어오게 될 우선순위가 낮은 프로세스는 Starvation 발생 à Aging 기법으로 해결가능 |
|
기한부 스케줄링 |
- 작업들이 명시된 시간이나 기한내에 완료되도록 계획 - 사용자는 사전에 작업이 요구하는 정확한 자원을 제시 - 작업시간이나 상황 등 정보를 미리 예측하기가 어려움 |
|
FCFS |
- First Come First Service - 프로세스가 대기큐(준비큐)에 도착한 순서에 따라 CPU 할당 - 가장 간단한 스케줄링 알고리즘으로 FIFO(First Input First Out)알고리즘 이라고 함 - Convoy Effect 발생 가능 (Burst time이 긴 프로세스가 CPU 독점) - 단독적 사용이 거의 없으며, 다른 스케줄링 알고리즘에 보조적으로 사용 (우선순위 스케줄링, RR 스케줄링 등) |
|
SJF |
- Shortest Job First - 준비 큐 내의 작업중 수행시간이 가장 짧다고 판단되는 것을 먼저 수행 - 각 프로세스에서 CPU 버스트 길이를 비교하여 CPU 가 이용 가능해지면 가장 작은 CPU 버스트를 가진 프로세스를 할당 - 주어진 프로세스 집합에 대해서 평균대기 시간이 최소가 되는 최적 알고리즘 - CPU 요구시간이 긴 작업과 짧은 작업간의 불평등 심하여, CPU 요구시간이 긴 프로세스는 Starvation 발생 à HRN 사용 |
|
HRN |
- Highest Response Ratio Next - Response Ratio = [대기시간+서비스 시간) /서비스 시간 - 대기중인 프로세스 중 현재 Response Ratio 가 가장 높은 것을 선택 - 대기중인 프로세스 중 현재 Response Ratio 가 가장 높은 것을 선택 - SJF의 약점을 보완한 기법으로 긴 작업과 짧은 작업간의 불평등을 완화 |
※ SJF(Shortest Job First)
- 실행 시간이 가장 짧은 작업 순으로 CPU수행
1) 대기 시간
- P1 = 0, P2 = 4, P3 = 9, P4 = 3, P5 = 4
- 평균 대기 시간 = (4+9+3+4) / 5 = 4
2) 반환 시간(turnaround time)
- P1 = 5-0 = 5, P2 = 6-1 = 5, P3 = 16-2 = 14, P4 = 8-3 = 5, P5 = 11-4 = 7
- 평균 반환 시간 = (5+5+14+5+7) / 5 = 7.2
※ HRN(Highest Response Ratio Next)
- 우선순위 = (대기시간 + 서비스 받을 시간) / 서비스 받을 시간
- 5초일 때에 HRN에 따른 우선순위 계산
P2 = (4 + 1) / 1 = 5, P3 = (3 + 5) / 5 = 1.6, P4 = (2 + 2) / 2 = 2, P5 = (1 + 3) / 3 = 1.3
따라서, 우선순위가 가장 높은 P2가 CPU를 선점함.
- 6초일 때에 HRN에 따른 우선순위 계산
P3 = (4 + 5) / 5 = 1.8, P4 = (3 + 2) / 2 = 2.5, P5 = (2 + 3) / 3 = 1.6
따라서, 우선순위가 가장 높은 P4가 CPU를 선점함.
- 8초일 때에 HRN에 따른 우선순위 계산
P3 = (6 + 5) / 5 = 2.2, P5 = (3 + 3) / 3 = 2
따라서, 우선순위가 가장 높은 P3가 CPU를 선점함
1) 대기 시간
- P1 = 0, P2 = 4, P3 = 6, P4 = 3, P5 = 9
- 평균 대기 시간 = (4+6+3+9) / 5 = 4.4
2) 반환 시간(turnaround time)
- P1 = 5-0 = 5, P2 = 6-1 = 5, P3 = 13-2 = 11, P4 = 8-3 = 5, P5 = 16-4 = 12
- 평균 반환 시간(turnaround time) = (5+5+11+5+12) / 5 = 7.6
IV. CPU scheduling 선택 고려사항 및 기술동향
가. CPU scheduling 선택 고려사항
- I/O Bound, CPU Bound
- 프로세스의 작업 형태[일괄처리형/대화형,실시간형]
- 프로세스의 우선순위
- 프로세스의 페이지 뷰재율
- 프로세스의 자원 선점율 고려
- 프로세스의 버스트 시간 고려
- 프로세스의 잔여 실행시간 고려
나. CPU scheduling 기술동향
- Multi-thread 기반의 Scheduling Algorithm이 요구됨
- 실시간 시스템의 경우 정해진 시간 내에 완료되는 것이 보장될 때에만 CPU를 할당하는 Scheduling 기법의 적용
- 멀티미디어, 가상현실 시스템과 같은 복잡한 응용에 적합한 Scheduling Algorithm 연구가 활발히 추진되어야 함
- NVC (Network Virtual Computing) 환경에서 CPU Scheduling 방안의 연구가 진행중임
- 작업유형 측면 : 컴퓨터 작업 유형 즉, 대화형/일괄처리형이냐에 따른 적절한 CPU 스케줄링 선택을 통한 컴퓨팅 자원의 극대화 필요함
- 실시간 시스템 측면 : embedded 시스템, RTOS 등 실시간 기반의 시스템 활용의 다양화로 빠른 응답을 처리할 수 있는 별도의 CPU 스케줄링 개발 필요
<기출 풀이>
다음표와 같이 작업이 제출되었을 때 SJF(Shortest Job First)정책으로 스케줄링 할 때의 평균 Turnaround 시간을 구하시오.
|
작업 |
제출시간 |
실행시간 |
|
X |
0 |
4 |
|
Y |
1 |
6 |
|
Z |
2 |
3 |
① 가장 먼저 제출된 X작업 실행
② 1시간경과후, Y작업이 제출 되었으나, X작업은 1시간동안 수행되어 3시간 실행시간, Y작업은 6시간 수행시간을 갖으므로, X작업 수행 지속 (또한 SJF는 비선점이므로 X작업에 의해 할당된 CPU가 선점 될 수 없음)
③ 총 2시간경과후, Z작업이 제출 되고, X작업은 2시간 수행되어 2시간 실행시간, Z작업은 3시간 수행시간이므로, X작업 수행 지속 (또한 SJF는 비선점이므로 X작업에 의해 할당된 CPU가 선점 될 수 없음)
④ 총 4시간경과후, X작업이 완료되고, Y와 Z작업중 실행시간이 작은 Z작업이 먼저 수행됨
⑤ 총 7시간경과후, Z작업이 완료되고, Y작업이 실행됨
⑥ 총 13시간경과후, Y작업까지 완료되고 모든 작업 완료
Turnaround 시간 : 대기시간 + 실행시간
대기시간 = 앞 프로세스 실행시간 – 도착시간
X 작업 : 4시간
Z 작업 : (4-2) + 3 시간 = 5시간
Y 작업 : (7-1) + 6 시간 = 12시간
평균 : 4 + 5 + 12 = 21시간 /3 = 7시간
HRN(Highest Response-ratio Next)방식으로 스케줄링 할 경우, 입력된 작업이 다음과 같을 때 우선순위가 가장 높은 작업을 선정하는 절차를 나타내시오.
|
작업 |
대기시간 |
서비스 시간 |
|
A |
5 |
5 |
|
B |
10 |
6 |
|
C |
15 |
7 |
|
D |
20 |
8 |
- HRN 방식의 스케줄링은 SJF의 단점을 보완하여 서비스 시간이 긴 작업이 무한정 기다리는 기아(Starvation) 현상을 해결한 스케줄링 기법임
-우선순위 = (대기시간 + 서비스 시간)/서비스 시간, 값이 높을수록 우선순위를 가짐.
- 위의 표를 기준으로 우선순위를 산정해 보면
A : (5+5)/5 = 2
B : (10+6)/6 = 2.67
C : (15+7)/7 = 3.14
D : (20+8)/8 = 3.5
- 우선순위는 D → C → B → A → 순임
I/O bound & CPU bound
