[운영체제] CPU 스케줄러

Q. 스케줄러는 무엇이며, 스케줄링을 하는데 있어서 중요한 것은 무엇인가?

스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위를 기반으로 CPU를 할당받게 해주는 역할을 한다. 스케줄러가 스케줄링을 하는데에는 2가지 중요한 요소가 있다. 첫 번째, 스케줄링의 최대 관심사는 무엇인가, 즉, 스케줄링의 기준은 무엇인가? 이다. 스케줄링의 기준이 될 수 있는 대표적인 예로는 대기 시간(waiting time), CPU 할당 시간(allocation time) 등이 있다. 두 번째, 스케줄링을 어떻게 구현할 것인가? 이다. 스케줄링을 구현할 때는 반드시 자료구조의 구현이 따른다. 어떠한 자료구조를 이용하여 스케줄링을 구현할 것인지를 결정하는 것이 스케줄링에 중요한 요소이다. 대표적으로, 링크드 리스트, 해쉬 리스트, 비트 맵, 레드 블랙 트리(리눅스) 등 다양한 자료구조를 사용하지만, 정밀하고 견고한 운영체제일 수록 스케줄링에 사용하는 자료구조의 실행시간을 최대한 줄여나가는 것이 중요하다. 최소한 O(log n) 수준으로 실행 시간을 낮춰야 한다.

Q. 스케줄링의 목표는 무엇인가?

스케줄링의 목표에는 3가지가 있다. CPU 활용을 최대화하자, 평균 대기 시간을 최소화하자. 처리량을 최대화하자. 스케줄링은 멀티 프로세싱 운영 체제를 디자인하는 일과 컴퓨터의 멀티태스킹 작업을 만들어내는 데에 있어서 핵심 개념이다.

Q.  스케줄링 알고리즘에는 무엇이 있나?

FCFS(First Come, First Served), SJF(Shortest Job First), Priority Scheduling, RR(Round Robin) Scheduling 등이 있다.

Q. FCFS(FIrst Come, First Served) 스케줄링은 무엇인가? 그리고 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  FCFS는 First Come, First Served 의 약자이다. 즉, 먼저 온 사람 먼저 대접한다는 뜻으로, CPU를 처음 요구한 프로세스가 CPU를 처음 사용한다는 의미의 스케줄링 알고리즘이다. 구현할 때는 FIFO (First In FIrst Out) 큐 자료구조를 사용한다. FCFS는 스케줄링 특성상 비선점 스케줄링 알고리즘이며, CPU를 사용하고 있는 프로세스 자기 자신이 CPU를 놓아줄 때까지 CPU를 다른 프로세스에게 양보하지 않는다. 이러한 특성은 콘보이 효과를 불러 일으킨다. 콘보이 효과란, CPU를 매우 오래 사용하는 프로세스가 도착하게 되면, 다른 프로세스가 CPU를 사용하는데 기다리는 대기 시간이 매우 커지는 현상을 말한다. 콘보이 효과는 비선점 스케줄링을 사용할 때만 발생한다. FCFS 스케줄링은 콘보이 효과때문에 평균 대기시간이 매우 형편없는 스케줄링 알고리즘이다. FCFS는 비선점 스케줄링 알고리즘의 장점을 그대로 가진다. 비선점 스케줄링 알고리즘은 모든 프로세스가 공평한 조건으로 CPU를 사용할 수 있게 해주며, 반응 시간을 예측할 수 있다.

Q. SJF 알고리즘은 무엇인가? 그리고 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  SJF는 Shortest Job First 의 약자이다. 가장 시간이 적게 걸리는 작업을 먼저한다는 뜻으로, SJF의 정의는 CPU가 릴리즈되어 있을 때, 가장 시간이 적게 걸리는 프로세스가 선택되어 실행된다는 것이다. SJF는 비선점 스케줄링과 선점 스케줄링 두가지 종류가 있고, 선점형 SJF는 SRTF(Shortest Remaining Time First)라고도 한다. SJF는 스케줄링 알고리즘 중에서 최소의 평균 대기 시간을 위해 최적화된 스케줄링 알고리즘이다. (즉, 스케줄링 알고리즘 중에서 평균 대기 시간을 가장 적게 가지는 스케줄링 알고리즘이다.) 

 SJF의 단점도 있다. SJF에서 최소의 오버헤드로 최적의 성능을 보장하도록 알고리즘을 구현하는 것이 힘들다는 것이 SJF의 단점이다. 선점형 SJF에서는 프로세스들끼리 서로 끼어들기 때문에, 다음 CPU 점유 시간을 예측하는 것이 매우 힘들다. (SJF는 CPU 점유 시간 자체를 예측해야만 구현할 수 있는 스케줄링 알고리즘이다. 즉, 미래를 예측해야 한다는 특성 자체가 SJF 알고리즘을 구현하는 것을 어렵게 만드는 것이다.) 이러한 특성은 제대로 성능을 발휘하는 선점형 SJF를 구현하는 것이 힘들게 한다. 

Q. Priority Scheduling 은 무엇인가? 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  높은 우선순위를 가진 프로세스가 항상 먼저 CPU를 사용할 수 있도록 구현한다. 우선순위 기반 스케줄링에는 치명적인 단점 이슈가 있다. 바로 Starvation(굶주림)이다. 우선순위가 낮은 프로세스는 영원히 작동하지 않을 수 있다. (우선순위가 낮은 프로세스의 대기 시간이 무한정 늘어날 수 있다.) Starvation의 해결책은 바로 Aging-method이다.   레디 큐에서 오랜 시간을 기다린 프로세스는 계속해서 우선순위를 높히게 하는 기법이다. 이러한 에이징 메서드 기법을 통해서 우선순위가 낮은 프로세스도 최대 한도의 대기 시간을 가질 수 있다. 참고로, 우선순위 스케줄링은 선점형 SJF와 비슷한 경향을 가지고 있다. 우선순위 스케줄링에서의 각 프로세스의 우선순위가 선점형 SJF 스케줄링에서의 예측 CPU 점유 시간과 동일한 역할을 한다. 우선순위가 높을 수록, 먼저 CPU를 사용할 수 있게 해주듯이, 예측 CPU 점유 시간이 짧을 수록 먼저 CPU를 사용할 수 있게 해준다는  것이 매우 흡사하다.

Q. Round Robin(RR) 스케줄링은 무엇인가? 어떤 특징과 장단점을 가지는가?

  Round Robin 스케줄링은 각각의 프로세스가 공평하게 시간 간격 동안 CPU를 활용할 수 있도록 하는 스케줄링 알고리즘이다. 정해진 시간 간격이 끝나면, CPU를 사용하고 있던 프로세스는 선점적으로 추방당한다. (레디 큐에 다시 들어가게 된다.) 여기서 정해진 시간 간격을 Time Quantum 이라고 한다. 

만약 레디 큐에 n개의 프로세스와 q의 time qunatum을 가지고 있다고 가정하면, 모든 프로세스는 최대한 (n-1)q 시간 안에 CPU 사용을 시작하게 됨을 보장할 수 있다. 따라서, 라운드 로빈은 SJF 스케줄링 보다 반응 시간 최적화에 있어서는 더 탁월한 스케줄링 알고리즘이다. (하지만 대기 시간의 최적화는 SJF가 더 좋은 편이다.)