CPU 스케줄링 알고리즘
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 프로그램 실행 시 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 지 결정한다. CPU 스케줄링 알고리즘의 목표는 다음과 같다.
- CPU 이용률 높게
- 주어진 시간에 많은 일을 하게
- 준비 큐(ready queue)에 있는 프로세스 적게
- 응답 시간 짧게CPU 스케줄링 알고리즘은 비선점형 방식과 선점형 방식으로 나뉜다.
비선점형 방식 (non-preemtive)
- 프로세스가 스스로 CPU 소유권을 포기하는 방식
- 강제로 프로세스 중지 X
- context switching으로 인한 부하 적음FCFS (First Come First Served)
- 큐에 도착한 순서대로 CPU 할당
- 길게 수행되는 프로세스 → 준비 큐에서 오래 기다리는 현상(convoy effect) 발생하는 단점 존재
- 실행 시간이 짧은 프로세스가 뒤로 가면 평균 대기 시간이 길어짐SJF (Shortest Job First)
- 실행 시간이 가장 짧은 프로세스 먼저 실행
- 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation) 발생
- 평균 대기 시간 가장 짧음
- 실제 실행 시간 알 수 없어서 과거 실행 시간 토대로 추측
- FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리HRN (Highest Response-ratio Next)
- 오래된 작업일수록 높은 우선순위를 부여(aging)
- 기존 SJF 스케줄링의 starvation 문제 보완
- 우선순위 = (대기시간 + 실행시간) / 실행시간선점형 방식 (preemtive)
- 현대 운영체제가 쓰는 방식
- 지금 사용하는 프로세스를 알고리즘에 의해 중단, 강제로 다른 프로세스에 CPU 소유권 할당Priority Scheduling
- 정적/동적으로 우선순위를 부여해 우선순위가 높은 순서대로 처리
- 우선 순위가 낮은 프로세스가 무한정 기다리는 starvation이 생길 수 있음
- aging 방법으로 starvation 문제 해결 가능RR (Round Robin)
- 우선순위 스케줄링 (priority scheduling) 의 일종
- 각 프로세스에 동일한 할당 시간(time quantum/time slice) 부여, 시간 안에 끝나지 않으면 다시 준비 큐 (ready queue)의 뒤로 가는 알고리즘
- q 할당 시간, N 개의 프로세스: (N - 1) * q 시간이 지나면 자기 차례 옴
- 할당 시간이 너무 크면 FCFS와 같게 됨
- 할당 시간이 너무 짧으면 context switching이 잦아져 오버헤드 증가
- 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아짐
- 로드밸런서 트래픽 분산 알고리즘SRTF (Shortest Remaining Time First)
- 중간에 더 짧은 작업이 들어오면 수행하던 프로세스 중지하고 해당 프로세스 수행MLQ (MultiLevel Queue)
- 우선순위에 따른 준비 큐를 여러 개 사용
- 큐마다 RR, FCFS 등 다른 스케줄링 알고리즘 적용
- 큐 간의 프로세스 이동 X → 스케줄링 부담 적음, 유연성 떨어짐
- 높은 우선순위: 시스템 프로세스 - FCFS
- 중간 우선순위: 상호 작용적인 프로세스 - SJF
- 낮은 우선순위: 배치 프로세스 - RRMFQ (Multilevel Feedback Queue)
- MLQ + 동적인 프로세스 우선 순위 변화 적용
- 큐 간의 프로세스 이동 O
- MLQ에서 자신의 time quantum을 다 채운 프로세스는 하위 준비 큐로 내려감
- 단계가 내려갈수록 time quantum 증가
- CPU Burst는 낮은 우선순위의 큐, I/O Burst는 높은 우선순위의 큐에 배치
- 가장 하위 큐는 FCFS 스케줄링
- 하위 큐에서 너무 오래 대기하면 다시 상위 큐로 이동 (starvation 예방)
- 짧은 작업에 유리, 입출력 위주 (interrupt가 잦은) 작업에 우선권 줌
- 처리 시간이 짧은 프로세스 먼저 처리, Turnaround 평균 시간을 줄여줌