CPU 스케줄러와 스케줄링 알고리즘
Table of contents
CPU 스케쥴러
- 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.
스케줄링
모든 프로세스가 자원을 공평하게 배정받아야 하고, 유휴 시간 없이 자원이 사용되도록 하고, 중요 프로세스가 먼저 작동하도록 하고, 적절한 시간 안에 프로세스의 요구에 반응하기 위해 스케줄링을 사용한다.
1. 고수준 스케줄링
고수준 스케줄링은 시스템 내의 전체 작업 수(1개 또는 여러개의 프로세스)를 조절한다.
작업 요청이 오면, 시스템의 상황을 고려하여 작업을 승인할지, 거부할지를 결정하므로 승인 스케줄링 이라고도 한다.
고수준 스케줄링에 따라 시스탬 내에서 동시에 실행 가능한 프로세스의 총 개수가 정해진다. 이 개수를 멀티프로그래밍 정도라고 한다.
2. 중간 수준 스케줄링
고수준 스케줄링이 승인한 프로세스를 , 시스템의 과부하 때문에 프로세스 수를 조절해야 한다면 일부를 보류 상태로 보내는 역할을 한다.
3. 저수준 스케줄링
어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 결정한다.
다중 큐
준비 상태의 다중 큐
프로세스의 준비상태란, CPU를 할당받기 전(실행 상태) 순서를 기다리는 상태이다.
프로세스는 저마다 중요도가 다르며 프로세스의 중요도는 PCB(프로세스 제어 블록)에 표시된다.
CPU 스케줄러는 모든 PCB를 탐색해서 가장 높은 우선순위의 프로세스에 CPU를 할당한다.
이 과정을 최적화하기 위해, 큐를 만들어서 우선순위별로 저장하여 관리한다.
각 프로세스는, 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.
기본적으로는 우선순위는 고정되어 있고, 프로세스 작업 중간에 우선순위가 바뀌는 변동 우선순위 방식은 구현하기 어렵지만, 시스템의 효율성을 높일 수 있다.
대기 상태의 다중 큐
대기 상태는 입출력이 완료되기를 기다리는 프로세스를 말한다.
시스템의 효율을 높이기 위해, 같은 입출력을 요구한 프로세스끼리 모아놓는다.
준비 상태의 다중 큐와 차이점이 있다면, 대기 큐는 여러개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다.
스케줄링 알고리즘
- 선점형 알고리즘 : 어떤 프로세스가 CPU를 할당받아서 실행 중이라도 운영체제가 CPU를 강제로 빼앗을 수 있다.
- 비선점형 알고리즘 : 프로세스가 작업이 끝날때까지 CPU를 놓지 않는 알고리즘인데, 효율이 떨어져서 지금은 거의 사용하지 않는다.
다단계 큐 스케줄링
고정형 우선순위란, 프로세스가 우선순위를 기준으로 정해진 큐에 들어가면, 무조건 들어간 순서대로 프로세스를 실행시킨다는 의미이다.
우선순위 큐 안에서는 고정형이지만, 크게 보면 우선순위 별로 큐가 나누어져 있고, 우선순위가 높은 큐에 프로세스가 계속 채워지면
낮은 우선순위 큐에서 대기하는 프로세스의 순서는 뒤로 미뤄지기 때문에, 선점형 방식이라고 할 수 있다.
다단계 피드백 큐 스케줄링
라운드 로빈 방식을 사용하는데, 주어진 타임 슬라이스 동안 작업을 끝내지 못한 프로세스는 한단계 아래의 우선순위로 들어간다.
-> 다단계 큐의 낮은 우선순위에 있는 프로세스의 순서가 계속 미뤄지는 문제점을 보완한 방식이다.
- 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는 프로세스(우선순위가 가장 낮은 프로세스)의 타임 슬라이스 크기는 얼마인가?
-> 무한대의 타임슬라이스, 즉 작업이 완전이 끝나야 다음 차례로 넘긴다는 의미이다.
- 다단계 피드백 큐 스케줄링에서 우선순위가 낮아질수록 타임 슬라이스의 크기는 어떻게 변하는가?
-> 커진다.
- 다단계 피드백 큐 스케줄링에서 마지막 큐(우선순위가 가장 낮은 큐)는 어떤 스케줄링 알고리즘 처럼 동작하는가?
-> FCFS 스케줄링 알고리즘
FCFS 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비 선점형 방식이다. (자료구조의 큐와 동일, FIFO구조)