CPU Scheduling

태그

1 more property

Scheduling

•

CPU를 잘 사용하기 위해 실행할 프로세스를 선택하는 것

•

오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓ 하도록 설계해야 한다.

•

목표

Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요

Interactive System: 빠른 응답 시간. 적은 대기 시간.

Real-time System: 기한(deadline) 맞추기.

선점 / 비선점 스케줄링

•

선점 (preemptive) : OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우

•

비선점 (nonpreemptive) : 프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 어려움)

프로세스 상태

승인 (Admitted)

•

프로세스 생성이 가능하여 승인됨.

스케줄러 디스패치 (Scheduler Dispatch)

•

준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것

인터럽트 (Interrupt)

•

예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

입출력 또는 이벤트 대기 (I/O or Event wait)

•

실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

입출력 또는 이벤트 완료 (I/O or Event Completion)

•

입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.

비선점 스케줄링 : Interrupt, Scheduler Dispatch

선점 스케줄링 : I/O or Event Wait

CPU 스케줄링의 종류

•

비선점 스케줄링

FCFS (First Come First Served)

•

큐에 도착한 순서대로 CPU 할당

•

실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐

SJF (Shortest Job First)

•

수행시간이 가장 짧다고 판단되는 작업을 먼저 수행

•

가장 짧은 평균 대기 시간을 가지고 있다.

•

하지만 실제로 프로세스의 CPU 점유시간(burst time)을 알 수 없기 때문에 비현실적이다.

•

선점 SJF도 존재한다.

•

선점 스케줄링

Priority Scheduling

•

정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리

•

우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음

•

Aging 방법(ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 올려주는 방법)으로 Starvation 문제 해결 가능

Round Robin

•

FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할달 받음

◦

Time Quantum or Time Slice : 실행의 최소 단위 시간

•

할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가

Multilevel-Queue (다단계 큐)

•

작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법

•

우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용

•

우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.

Multilevel-Feedback-Queue (다단계 피드백 큐)

•

다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로

◦

Time Quantum을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문

•

짧은 작업에 유리, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 줌

•

처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌

스케줄링의 척도 (Scheduling Criteria)

Scheduling criteria(척도)는 스케줄링의 효율을 분석하는 기준들이다.

CPU Utilization(이용률, %)

•

CPU가 수행되는 비율

Throughput(처리율, jobs/sec)

•

단위시간당 처리하는 작업의 수(처리량)

Turnaround time(반환시간)

•

실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될때까지 총 걸린 시간

Waiting time(대기시간)

•

CPU를 점유하기 위해서 ready queue에서 기다린 시간을 말한다.(다른 큐에서 대기한 시간은 제외한다.)

Response time(응답시간)

•

일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다. (작업이 제일 처음 실행되기까지 걸린 시간)