CS - Operating System - CPU Scheduling

스케줄링

 

CPU 사용량을 최대로 하기 위해 프로세스를 잘 배정하는 것.

 

조건 : 오버헤드 최저, 사용률 최대, 기아 현상 최저

 

목표 - 시스템에 따라 조금씩 다르다

 

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

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

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

 

 

선점 / 비선점 스케줄링

 

선점 (preemptive)

 

OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우(처리시간 예측 어려움)

 

비선점(non-preemptive)

 

프로세스 종료 혹은 I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이함)

 

 

프로세스 상태

 

 

선점 스케줄링 : Interrupt, I/O or Event Completion, I/O or Event Wait, Exit

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

 

 

프로세스 상태 전이

 

승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.

 

스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것

 

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

 

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

 

입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.

 

 

CPU 스케줄링의 종류

비선점 스케줄링

프로세스 작업이 종료될때까지 다른 프로세스에 cpu 할당이 불가능한 방식이 비선점 방식.

프로세스 종료 순서가 예측 가능하나 대기시간이 길어질 가능성이 존재.

 

1. FCFS ( First Come First Served )

 

큐에 도착한 순서대로 CPU 할당하는 방식.

실행 시간이 긴게 앞에 있으면 평균 대기 시간이 길어진다.

대기 시간이 길어지는 convoy effect 발생

 

2. SJF (Shortest Job First)

 

수행시간이 가장 짧은 것이 먼저 실행

FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리

수행시간이 긴 프로세스에 cpu 할당이 안되는 starvation 발생.

 

3. HRN ( Highest Response-ratio Next )

 

우선순위를 계산하여 점유 불평등을 보완한 방법 (SJF의 단점 보완)

우선순위 = (대기시간 + 실행시간) / (실행시간)

오래된 작업일수록 우선순위를 높이는 방법 (aging)을 통해 SJF의 단점을 보완

 

선점 스케줄링

프로세스를 중단하고 cpu를 다른 프로세스에 할당 가능한 방식.

대기시간이 짧아지나 프로세스 종료 순서가 예측 불가능해질 수 있다.

 

1. Priority Scheduling

 

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

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

Aging 방법으로 Starvation 문제 해결 가능

 

2. Round Robin

 

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

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

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

라운드 로빈은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰입니다.

 

3. Mulitilevel - Queue (다단계 큐)

 

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS등 다른 스케줄링 알고리즘을 적용한 것을 말합니다.

큐 간의 프로세스 이동이 불가능해 스케줄링 부담은 적지만 유연성이 떨어지는 특징이 있습니다.

 

4. SRF

 

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존의 작업은 중단되지 않으나 SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘.

 

 

CPU 스케줄링 척도

 

 

1. Response Time

 

작업이 처음 실행되기까지 걸린 시간

 

2. Turnaround Time

 

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