스케줄링 알고리즘
CPU 스케줄링 알고리즘의 종류는 다양하다. 운영체제마다 다른 스케줄링 알고리즘을 사용하고 있는데 여러가지 스케줄링 알고리즘을 살펴보자.
선입 선처리 스케줄링
선입 선처리 스케줄링은 FCFS 스케줄링(First Come First Served Scheduling)라고도 불리는데, 이는 CPU를 먼저 요청한 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식이다. 언뜻 보기에 공정한 방법이지만, 프로세스들이 기다리는 시간이 길어질 수 있다는 부작용이 있다.
예를 들어 가장 먼저 도착한 프로세스의 처리 시간이 15ms, 두 번째 세 번째 프로세스가 각각 5ms, 1ms라고 가정해보자. 이렇게 되면 세 번째 프로세스의 처리시간은 1ms이지만 앞선 프로세스에 의해 대기하는 시간은 20ms가 걸린다. 이런 현상을 호위 효과(convoy effect)라고 한다.
최단 작업 우선 스케줄링
선입 선처리 스케줄링에서 호위 효과라는 부작용을 확인 했는데, 이 부작용을 없애기 위한 단순한 방법은 처리 시간이 긴 프로세스를 나중에 처리하고 짧은 프로세스부터 처리하는 것이다.
이를 최단 작업 우선 스케줄링 ( SJF 스케줄링 : Shortest Job First Scheduling ) 이라고 한다.
SJF 스케줄링은 기본적으로 비선점형으로 분류되지만, 선점형 최단 작업 우선 스케줄링이라는 선점형 스케줄링으로 구현될 수도 있다.
라운드 로빈 스케줄링
라운드 로빈 스케줄링(round robin scheduling)은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다. 타임 슬라이스는 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.
큐에 삽입된 프로세스들은 삽입된 순서대로 정해진 시간만큼 CPU를 이용한다. 이때, 시간이 다 되어도 프로세스 처리가 이루어지지 않았다면 다시 큐의 맨 뒤로 이동한다.
이때 문맥 교환이 일어난다.
이 스케줄링 방식은 타임 슬라이스의 크기가 중요한데, 만약 슬라이스의 크기가 너무 크다면 선입 선처리 스케줄링에서 나타났던 호위 효과 부작용이 나타날 가능성이 크고, 슬라이스의 크기가 작다면 문맥 교환에 발생하는 비용이 크다.
최소 잔여 시간 우선 스케줄링
최소 잔여 시간 우선 스케줄링 ( SRT 스케줄링 : Shortest Remaining Time )은 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링이 합쳐진 스케줄링이다. 최소 잔여 시간 우선 스케줄링은 프로세스들이 정해진 시간만큼 CPU를 사용하고, CPU를 사용하는 다음 프로세스는 남아있는 작업시간이 가장 적은 프로세스가 선택된다.
우선순위 스케줄링
우선순위 스케줄링(priority scheduling)은 프로세스들에게 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.
우선순위 스케줄링은 우선순위가 높은 프로세스를 우선하여 처리하다보니 우선순위가 낮은 프로세스는
준비 큐에 먼저 삽입되어도 실행이 계속해서 연기될 수도 있다. 이를 기아(starvation)현상이라고 한다.
이를 방지하기 위한 대표적인 기법으로 에이징(aging)이 있다.
에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.
이를 이용하면 우선순위가 낮아도 계속 대기하고 있는 일이 없어진다.
다단계 큐 스케줄링
다단계 큐 스케줄링은 우선순위 스케줄링의 발전된 형태이다. 다단계 큐 스케줄링(multilevel queue scheduling)은 우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.
우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 큐가 비면 그다음 우선순위 큐에 있는 프로세스들을 처리한다.
이렇게 큐를 여러개 두면 프로세스 유형별로 우선순위를 구분하여 실행하기가 편해진다.
큐마다 다른 스케줄링 알고리즘을 사용할 수도 있고, 타임 슬라이스를 큐 별로 여러개를 지정할 수도 있다.
다단계 피드백 큐 스케줄링
바로 위의 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없다.
이렇게 되면 우선순위가 낮은 프로세스는 계속 연기될 가능성이 있다. 기아 현상이 다시 발생할 것이다.
다단계 피드백 큐 스케줄링(multilevel feedback)는 프로세스들이 큐 사이를 이동할 수 있다는 점에서 이를 해결한다.
새로 준비 상태에 든 프로세스가 들어오면 우선순위가 가장 높은 큐에 삽입되고 정해진 시간만큼 실행된다. 그리고 프로세스가 만약 정해진 시간동안 해당 큐에서 실행이 끝나지 않았다면 다음 우선순위 큐에 삽입되어 실행된다. 또, 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입된다. 결국 CPU를 오래 사용해야하는 프로세스는 우선순위가 점차 낮아진다.
즉, CPU를 오래 사용해야하는 CPU 집중 프로세스들은 우선순위가 점차 낮아지고, CPU를 적게 사용하는 입출력 집중 프로세스들은 자연스럽게 우선순위가 높은 큐에서 실행된다.
또한 낮은 큐에서 오래 대기하고 있는 프로세스를 해결하기 위해 에이징 기법을 사용하여 기아 현상을 예방할 수 있다.
다단계 피드백 큐 스케줄링은 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져있다.
