[26] 시스템 보안 :: 프로세스 스케줄링 알고리즘, FIFO, SJF, HRN, RR, SRT, MLQ, MFQ

  이전 포스팅에 이어서 프로세스 스케줄링 알고리즘의 여러 종류들을 정리해보겠다. 가장 먼저 FIFO(First In First Out) 스케줄링이란, CPU를 먼저 요청하는 순서대로 CPU를 할당받는 알고리즘이다. 이 방식은 비선점형 스케줄링 방식으로, 한 프로세스가 CPU를 차지하여 연산하고 있을 때, 이것을 중지시켜서 빼앗을 수 없다. FIFO 스케줄링은 FCFS(First Come First Service) 스케줄링이라고도 하며, 선입선처리 큐로 쉽게 관리할 수 있다. 다음으로 SJF(Shortest Job First) 스케줄링은, 가장 짧게 CPU를 사용할 프로세스에게 가장 먼저 CPU를 할당해주는 알고리즘이다. 즉, 가장 작은 CPU 버스트를 갖는 프로세스에게 CPU를 할당해준다. 만약 두 프로세스가 동일한 길이의 CPU 버스트를 갖는다면, 선입선처리 방식을 적용해준다. SJF 방식에서는 긴 CPU 버스트 길이를 갖는 프로세스가 계속해서 연산을 수행하지 못하는 불평등한 문제가 발생한다. SJF 방식 또한 비선점 방식이다. HRN(Highest Response ratio Next) 스케줄링이란, SJF의 단점을 보완한 방식으로 CPU를 할당받기 위해 기다렸던 대기 시간 또한 스케줄링하는데 고려할 점으로 사용한다. 다시 말해 CPU 버스트 길이가 긴 프로세스도, 대기 시간이 수록 우선순위가 높아져서 CPU를 보다 빨리 할당받을 수 있다는 의미이다. HRN도 한 작업이 마칠 때까지 다른 작업이 선점할 수 없는 비선점 방식이다.

  위에서는 비선점 스케줄링 방식들을 정리해보았는데, 이번에는 선점 스케줄링 방식들을 정리해보겠다. RR(Round Robin) 스케줄링은, 시분할 시스템을 위해 만들어진 스케줄링 기법으로서, 시간 할당량만큼 CPU를 프로세스에게 할당하는 방식이다. 시간 할당량의 크기는 RR 스케줄링 알고리즘의 성능을 결정한다. 시간 할당량이 매우 크다면, RR 정책은 FIFO 정책과 유사하게 된다. 반면에 시간 할당량이 매우 작다면, RR 정책은 너무 많은 문맥 교환이 일어나서 비효율적이게 된다. 따라서 적절한 시간 할당량을 정하는 것이 RR 알고리즘의 성능에 중요한 영향을 끼치는 것이다. SRT(Shortest Remaining Time) 스케줄링 방식은, 준비 큐에 있는 프로세스들 중에서 가장 짧은 CPU 연산 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다. 이 경우, 어떤 한 프로세스가 CPU를 차지하고 있다고 해도 CPU 연산 시간이 짧은 프로세스가 준비 큐로 들어오면, 기존의 프로세스로부터 CPU를 빼앗아 차지하게 된다. MLQ(Multi Level Queue) 스케줄링이란, 여러 개의 준비 완료 큐를 사용하는 것으로 각 큐는 자신의 스케줄링 알고리즘을 갖고 있다. 어떤 큐는 RR 알고리즘을 쓰고 또 다른 큐는 FIFO 알고리즘을 사용할 수 있는 것이다. 보통 MLQ에서의 각 큐는, 시스템 프로세스를 위한 큐, 대화형 프로세스를 위한 큐, 대화형 편집 프로세스를 위한 큐, 일괄처리 프로세스를 위한 큐, 학생 프로세스를 위한 큐들이 있다. 이와 비슷하게 MFQ(Multi Feedback Queue) 스케줄링이란, 입출력 요청 프로세스와 CPU 연산 프로세스를 다르게 구분하여 각기 다른 타임 슬라이스를 부여하는 것을 의미한다. 그리고 각 프로세스들은 큐 사이를 이동하여 다닐 수 있는데, 처음에는 우선순위가 가장 높은 큐에 들어가게 된다. 그러다가 우선순위가 낮아지게 되면 가장 마지막 큐에 들어가서 RR 방식에 의해 처리된다. 참고로 UNIX 시스템이 이 MFQ 방식을 사용하고 있다.