CPU 스케줄링 알고리즘

3.4 CPU 스케줄링 알고리즘

 

CPU 스케줄링 알고리즘

• 어떤 프로세스에 CPU 소유권을 줄지 결정하는 알고리즘
• CPU 이용률 증가
• 처리량 증가
• 준비 큐 대기 프로세스 수 감소
• 응답 시간 최소화가 목표

---

3.4.1 비선점형 방식

비선점형 방식 (Non-preemptive)

• 프로세스가 스스로 CPU 소유권을 포기하는 방식
• 운영체제가 강제로 프로세스를 중지하지 않음
• 컨텍스트 스위칭으로 인한 부하가 적음

FCFS (First Come, First Served)

• 먼저 도착한 프로세스를 먼저 처리하는 알고리즘
• 실행 시간이 긴 프로세스가 앞에 있을 경우
• 준비 큐에서 오래 대기하는 현상 발생 (Convoy Effect)

SJF (Shortest Job First)

• 실행 시간이 가장 짧은 프로세스를 먼저 실행
• 평균 대기 시간이 가장 짧음
• 실행 시간이 긴 프로세스가 계속 실행되지 않는 starvation 발생
• 실제 실행 시간을 알 수 없어 과거 실행 시간을 기준으로 추정하여 사용

우선순위 스케줄링

• SJF의 starvation 문제를 보완한 알고리즘
• 오래 대기한 작업일수록 우선순위를 높이는 방식(aging) 사용
• FCFS 또는 SJF를 기반으로 구현 가능
• 선점형, 비선점형 방식 모두 존재

---

3.4.2 선점형 방식

선점형 방식 (Preemptive)

• 운영체제가 실행 중인 프로세스를 강제로 중단
• 다른 프로세스에 CPU 소유권을 할당
• 현대 운영체제에서 주로 사용

라운드 로빈 (Round Robin)

• 각 프로세스에 동일한 시간 할당량(q)을 부여
• 할당 시간 내에 끝나지 않으면 준비 큐의 뒤로 이동
• 프로세스가 N개일 경우 (N - 1) × q 시간 후 다시 실행
• 할당 시간이 크면 FCFS와 유사
• 할당 시간이 작으면 컨텍스트 스위칭 증가 → 오버헤드 증가
• 평균 응답 시간은 짧아짐
• 로드 밸런서의 트래픽 분산 알고리즘으로도 사용

SRF (Shortest Remaining Time First)

• SJF의 선점형 버전
• 실행 중 더 짧은 작업이 들어오면 현재 프로세스를 중단
• 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행

다단계 큐

• 우선순위별로 여러 개의 준비 큐 사용
• 각 큐마다 다른 스케줄링 알고리즘 적용
• 큐 간 프로세스 이동 불가
• 스케줄링 부담은 적음
• 유연성은 떨어짐

 

---