[운영체제] CPU Scheduling

✔︎ CPU Scheduling이란 ?

CPU를 효율적으로 사용하기 위해 프로세스를 잘 배정하는 것

오버헤드와 기아현상을 줄이고 CPU 사용률을 높이기 위해 사용한다.

 

✔︎ CPU Scheduling Criteria

시스템 입장에서의 성능 척도 

CPU 이용률(Utilization) : CPU를 이용한 수치의 백분율

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

 

사용자 입장에서의 성능 척도 

Turnaround Time : CPU를 가져온 후 다 쓰고 나갈 때까지의 시간 (프로세스가 아닌 CPU를 가져온 후 나갈 때 까지의 시간)

Response Time : 작업 요청 후 응답이 오는데 걸리는 시간, ready 큐에서 최초의 CPU를 얻기까지의 시간 

Waiting Time : 대기 큐에서의 대기 시간, 매번 CPU를 기다리는 시간의 총합

 

목표

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

빠른 응답 시간과 적은 대기 시간 

기한(deadline) 맞추기 

균형있는 자원 사용, 반환 시간 예측, 실행의 무한 연기 배제

 

✔︎ CPU Scheduler & Dispatcher

CPU Scheduler 

Ready 상태 프로세스 중에서 CPU를 줄 프로세스를 고르는 역할

 

Dispatcher

CPU의 제어권을 CPU Scheduler로부터 선택된 프로세스에 넘기는 역할을 한다. 

위의 과정을 Context Switch라고 한다.

 

프로세스 상태 전이

 

Running - 현재 실행 중 

Ready - queue에 들어와 있는 상태

Blocked - I/O가 수행을 완료할 때까지 또는 이용가능한 리소스가 생길 때까지 기다려야 하는 상황에 blocked로 간다.

new - 프로세스가 생성되었을 때

exit - 프로세스가 종료되었을 때

 

Scheduling이 필요한 경우

1. Running → Blocked (I/O 요청하는 시스템 콜)
2. Running → Ready (timer interrupt)
3. Blocked → Ready (I/O 완료 후 인터럽트)
4. Terminate 

1, 4는 비선점형 2, 3은 선점형

---

✔︎ CPU Scheduling의 종류

CPU Scheduling 종류

구분	선점(Preemptive)	비선점(Non-Preemptive)
개념	OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우  P1이 CPU 점유, P2가 CPU 점유 가능	프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장 P1이 CPU 점유, P2는 대기
장점	빠른 응답, 시분할 시스템에 적합	응답시간 예상 가능, 공정한 처리
단점	오버헤드 발생(Context Switching) 처리 시간의 예측이 어려움	짧은 작업도 긴 대기 발생

 

1. 선점(Preemptive) 알고리즘

종류	주요 내용
Priority	프로세스에 우선순위 부여하여 우선순위에 따라 할당 정적 할당 : 실행 중 우선순위를 바꾸지 않음 동적 할당 : 상황 변화에 적응하여 우선 순위의 변경이 가능
Round Robin	같은 크기의 CPU를 할당하는 순환 할당 방식 FCFS에 의해 프로세스가 CPU를 할당 받으면 Time Slice에 의해 같은 시간의 CPU를 할당 분할 방식에 효과적이며 할당시간(Time Slice)의 크기가 중요함 할당시간이 크면 FCFS에 가까워짐
SRT	Short Remaining Time 대기 큐의 가장 짧은 소요시간의 Process 선택 실행 중 선점가능
Multi Level Queue	작업을 그룹화하여 여러 큐 관리 및 할당
Multi Level Feedback Queue	여러 개의 큐를 두고 큐마다 다른 시간 할당량(Time Slice) 부여 짧은 작업 유리, 입출력 작업에 우선권 부여 하위 단계일수록 할당시간이 커짐

 

2. 비선점(Non-Preemptive) 알고리즘

종류	주요 내용
FCFS	First Come First Service 도착한 순서대로 처리(일괄처리) Batch 작업에 주로 사용, 짧은 작업이 긴 작업을 기다리게 됨
SJF	Shortest Job First 준비 큐에서 가장 짧은 소요시간의 프로세스 실행 FCFS보다 평균 대기 시간 감소 긴 프로세스가 짧은 프로세스에게 계속 작업순위가 밀리게 되어 실행되지 못하는 기아현상(Starvation) 발생
HRN	Highest Response-ratio Next 긴 작업과 짧은 작업의 공정성을 고려한 방식  Response Ratio가 높은 것을 선택 * Response Ratio = (대기시간 + 처리시간) / 처리시간 SJF의 단점을 보완하여 Starvation 현상방지 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아짐

 

 

참고

https://m.blog.naver.com/scw0531/221417295183

https://data-engineer.tistory.com/49

https://www.crocus.co.kr/1369