CPU 스케줄링
주어진 프로세스들이 여러 개인 경우 어떤 순서대로 CPU를 얼마 동안 배정하여 프로세스를 처리할지를 결정하는 스케줄링
CPU 스케줄링 단계
- 상위단계 스케줄링
- 시스템에 들어오는 작업들을 선택하여 프로세스를 생성한 후 프로세스 준비 큐에 전달하는 역할
- 입출력(I/O) 중심 작업과 연산 중심 작업을 균형있게 선택하도록 작업 순서를 결정한다.
- 중간단계 스케줄링
- CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 임시 대기 시킨 후 활성화하여 시스템에 대한 부하를 조절하는 역할
- 하위단계 스케줄링
- 사용 가능한 CPU를 준비상태의 어느 프로세스에 할당할지를 결정하는 역할 * 디스패처 ?
- 스케줄러가 어떤 프로세스를 기준에 맞게 선택한다면 선택된 프로세스를 CPU에 할당해주는 실제적인 실행 주체
- 문맥 교환이 일어날 때 이전의 프로세스의 상태를 저장하고 다음 프로세스를 복원하는 실제 처리 과정을 담당
- 사용 가능한 CPU를 준비상태의 어느 프로세스에 할당할지를 결정하는 역할 * 디스패처 ?
스케줄링 기법
- 선점 스케줄링
- 진행 중인 작업에 인터럽트를 걸고 다른 작업에 CPU를 할당하는 스케줄링 방식
- 우선 순위가 높은 프로세스를 긴급하게 처리 해야 할 경우 유용
- 잦은 문맥 교환에 따른 오버헤드가 발생할 수 있다.
- 비선점 스케줄링
- 프로세스가 CPU를 할당받아 실행이 시작되면 프로세스 자체가 I/O 인터럽트를 걸거나 프로세스를 종료할 때까지 다른 프로세스가 강제로 CPU를 뺴앗을 수 없는 스케줄링 방식
- 모든 프로세스가 우선순위에 관계없이 실행되지만 프로세스의 배치에 따라 효율 차이가 발생할 수 있다.
스케줄링 성능 기준
- 시스템(CPU) 관점
- CPU 이용률(CPU utilization) 전체 시간 중에서 CPU가 일을 한 시간의 비율
- 처리량(thoughtput) 주어진 시간 동안 대기 큐에서 기다리고 있는 프로세스 중 CPU 버스트를 처리한 개수
- 사용자(프로세스) 관점
- 반환 시간(Turn-around time) 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간, 즉 대기 큐에서 대기한 시간과 실제로 CPU를 사용한 시간의 합
- 대기 시간(Waiting time) 프로세스가 CPU를 할당받아 실행되기 전 대기 상태일 때의 시간
- 응답 시간(Response time) 프로세스가 대기 큐에 들어온 후 최초로 CPU를 얻기까지 기다린 시간
CPU 스케줄링 알고리즘
- FCFS 스케줄링 (First-Come First-Served)
- 대기 큐에서 도착순서에 따라 디스패치되며, 일단 프로세스가 CPU를 차지하면 그 프로세스의 수행이 완료된 후에 다음 프로세스가 CPU를 차지하고 수행되는 비선점형 방식
- 짧은 작업이 긴 작업을 기다리게 되기도 하고 중요한 프로세스가 나중에 수행될 수도 있기 때문에 대화식 시스템에는 적합하지 않다.
- SJP 스케줄링 (Shortest Job First)
- 대기 큐에서 기다리는 프로세스 중 실행 시간이 짧다고 예상되는 것을 먼저 수행하는 비선점형 방식
- 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 계속해서 들어오는 경우 CPU를 할당받지 못한다.
- 실제 대기 상태에 있는 프로세스의 실행 시간을 정확하게 예상하기 어렵다.
- SRTF 스케줄링 (Shortest Remaning Time First)
- SJF 스케줄링의 선점형 방식, 먼저 들어온 프로세스가 CPU를 할당받았더라도 남은 처리 시간이 뒤에 온 프로세스의 실행 시간보다 길면 뒤에 온 프로세스에 CPU를 할당하는 방식
- 잦은 문맥 교환이 일어나고 그에 따른 오버헤드가 커진다.
- RR 스케줄링 (Round-Robin)
- 프로세세에게 각각 동일한 CPU 할당 시간(time quantum)을 부여하여 실행하는 선점형 방식
- 모든 프로세스가 최초 응답 시간을 빠르게 보장 받을 수 있기 때문에 여러 종류의 프로세스가 같이 실행되는 환경에서 효과적이다.
- 할당 시간이 너무 짧을 경우 잦은 문맥 교환으로 오버헤드가 발생할 수 있고, 할당 시간이 긴 경우에는 CPU의 효율성이 떨어지고 FCFS 스케줄링과 다를 바 없어진다.
- HRN 스케줄링 (Highest Responese Ratio Next)
- 대기 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치하여 실행하는 비선점형 방식
- 수행시간의 길이와 대기 시간을 모두 고려하여 우선순위를 정해 SJF 스케줄링의 단점을 보완할 수 있다.
- 다단계 큐 스케줄링 (Multi-level Queue)
- 우선순위에 따라 준비 큐를 여러 개로 분할하여 관리하는 방식
- 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 우선순위는 고정형 우선순위를 사용하며 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
- 다단계 피드백 큐 스케줄링 (Multi-level Feedback Queue)
- 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완하는 선점형 방식
- 다단계 큐 스케줄링은의 경우 우선순위에는 변화가 없지만, 다단계 피드백 큐 스케줄링의 경우 CPU를 사용하고 난 뒤 프로세스의 우선순위가 낮아지며, 원래 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.