CPU 스케줄링 알고리즘의 효율성 평가 기준
- CPU 사용률이 높은가?
- CPU 사용률(CPU Utilization)은 CPU가 실제로 작업을 수행하는 시간의 비율
- 높은 CPU 사용률은 시스템 자원을 최대한 활용하고 있음을 의미
- 단위 시간당 작업을 마친 프로세스의 수(처리량)가 높은가?
처리량(Throughput)은 단위 시간당 완료된 프로세스의 수를 의미
- 높은 처리량은 시스템이 많은 작업을 신속하게 처리하고 있음을 나타냄
- 작업을 요청한 프로세스가 작업을 시작하기 전 대기하는 시간이 짧은가?
대기 시간(Waiting Time)은 프로세스가 CPU를 할당받기 위해 대기 큐에 머무는 시간을 의미- 짧은 대기 시간은 시스템이 프로세스의 요청을 빠르게 처리하고 있음을 나타냄
- 응답 시간(Response Time)
- 프로세스가 처음 요청을 제출한 후 처음으로 응답을 받을 때까지의 시간
- 반환 시간(Turnaround Time)
- 반환 시간은 프로세스가 시작해서 종료될 때까지 걸리는 전체 시간
- 이는 대시 시간과 실행 시간을 모두 포함
- 공정성(Fairness)
- 모든 프로세스가 공평하게 CPU 시간을 할당받는 것을 의미
- 특정 프로세스가 무한정 기다리지 않도록 보장하는 것이 중요
비선점형 스케줄링 알고리즘
- 한 번 CPU를 할당받은 프로세스가 자발적으로 CPU를 놓을 때까지 실행되는 방식
- 즉, 한 프로세스가 실행 중일 때 다른 프로세스가 CPU를 강제로 차지할 수 없음
- 컨텍스트 스위칭에 대한 부하가 적음
- 프로세스가 자발적으로 CPU를 놓을 때까지 실행되므로, 빈번한 컨텍스트 스위칭이 발생하지 않음
1. FCFS(First-Come, First-Served)
FCFS는 도착한 순서대로 프로세스를 처리하는 가장 간단한 스케줄링 알고리즘- 프로세스가 큐에 도착한 순서대로 CPU를 할당받아 실행
- 공정성 측면에서 유리하지만, 평균 대기 시간이 길어질 수 있음(컨보이 효과)
- 응답 시간이 불확실함
컨보이 효과(Convoy Effect)
- 긴 작업이 먼저 도착하면 뒤에 있는 짧은 작업들이 오랫동안 대기하게 되어 평균 대기 시간이 길어질 수 있음
- 응답 시간이 불확실함
2. SJF(Shortest Job First)
SJF는 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식- 모든 프로세스의 실행 시간을 미리 알고 있어야 함
- 평균 대기 시간이 가장 짧음
- 짧은 작업들이 빠르게 처리됨
- 실행 시간을 미리 알 수 없는 경우가 많아 구현이 어려울 수 있음
- 긴 작업이 계속 뒤로 밀려나
기아(Starvation) 현상이 발생할 수 있음
3. 우선순위 스케줄링(Priority Scheduling)
- 각 프로세스에 우선순위를 부여하고 우선순위가 높은 프로세스에게 먼저 CPU를 할당
- 동일한 우선순우의 프로세스는 FCFS 방식으로 처리
- 중요도가 높은 작업을 우선 처리할 수 있음
- 우선 순위가 낮은 프로세스가 무한정 대기하게 되는 기아현상이 발생할 수 있음
- 우선순윌르 동적으로 조정하지 않으면 시스템의 유연성이 떨어질 수 있음
HW + SW = 1