스케줄링
CPU 를 잘 사용하기 위해 프로세스를 잘 배정하기
조건
오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓
목표
- Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
- Interactive System: 빠른 응답 시간. 적은 대기 시간.
- Real-time System: 기한(deadline) 맞추기.
선점 / 비선점 스케줄링
비선점 (nonpreemptive)
프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이함)
- FCFS (First Come First Served)
큐에 도착한 순서대로 CPU 할당
실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐 - SJF (Shortest Job First)
수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
기아문제 발생 - HRN (Hightest Response-ratio Next)
우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
우선순위 = (대기시간 + 실행시간) / (실행시간)
선점 (preemptive)
OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리시간 예측 어려움)
- Priority Scheduling
정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
Aging 방법으로 Starvation 문제 해결 가능 - Round Robin
시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료하지 못한 프로세스는 레디 큐의 맨 뒤에 배치하는 방식
할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가 - Shortest Remaining Time First (SRTF)
CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식
SJF 방식에서 선점 방식만 다르다고 보면 된다.
기아 문제 발생 - Multilevel-Feedback-Queue (다단계 피드백 큐)
각 단계마다 하나의 큐를 두고, 큐 시간 할당량 내에 처리하지 못하면 다음 큐로 보내는 방식
단계가 커질수록 시간 할당량이 커지는 형태
CPU 스케줄링 척도
Response Time : 작업이 처음 실행되기까지 걸린 시간
Turnaround Time : 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간
프로세스 상태
선점 스케줄링 : 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 Scheduling이 무엇인지 설명하고, CPU 스케줄링의 종류에 대해 설명해주세요.
- Ready Queue에 있는 프로세스 중, 다음에 CPU를 할당할 프로세스를 선택하는 알고리즘을 CPU Scheduling이라고 합니다.
- 비선점 : FCFS, SJF, HRN
- 선점 : RR, SRTF, 다단계 피드백 큐
CPU의 성능 척도엔 무엇이 있는지 설명해주세요.
- CPU Utilization(이용률) : CPU가 놀지 않고 일한 시간
- Throughput(처리량) : 단위 시간당 처리량, CPU가 얼마나 많은 일을 했는지
- Turnaround Time(소요시간, 반환시간) : CPU 사용 시간 + 기다린 시간 (짧을수록 좋다)
- Waiting Time(대기시간) : 프로세스가 Ready Queue에서 기다린 전체 시간의 합
- Response Time(응답시간) : 프로세스가 Ready Queue에 들어가서 최초로 CPU 얻기까지 걸린 시간
선점(preemption)과 비선점(non-preemption)이 무엇인지 설명해주세요.
- 선점 방식은, 특정 프로세스가 실행 중이더라도 CPU 할당을 뺏어 다른 프로세스에 부여할 수 있는 방식입니다.
System Call, Time Quantum, Interrupt 등에 의해 선점이 일어납니다. - 비선점 방식은, 특정 프로세스가 실행 중이면 끝나기 전까지는 절대로 다른 프로세스에게 CPU를 뺏기지 않는 방식입니다.
