[운영체제] Scheduling

스케줄링

스케줄링은 보통 멀티프로그래밍을 가능하게 하는 운영 체제의 동작 기법이며 어느 프로세스를 CPU에 얼마큼 할당할지를 결정하는 기법입니다. CPU 외에 자원을 할당할 때 스케줄링 작업을 거치기도 합니다.

 

스케줄링 용어

• 멀티프로그래밍 : CPU의 활용 극대화, 많은 프로그램이 동시에 실행
• 시간 공유 : 프로세스들이 자원을 공유
• 프로세스 스케줄링 : CPU에서 실행될 프로세스를 선택
• Job Queue : 실행할 프로세스들의 PCB들의 모임
• Ready Qeueu : 실행을 위해 모든 준비가 완료된 프로세스들의 PCB 모임
• Device Qeueu(=waiting queue) : 자원을 사용 중이거나 사용하기 위해 기다리는 프로세스들의 모임, 각 장치들이 각자 고유의 큐를 가짐

Ready Qeueu

스케줄링의 종류

• 장기 스케줄링 : 프로세스가 자원을 사용을 요청하면 이를 ready queue로 보내는 스케줄링입니다. 다른 말로 프로세스를 메모리에 로딩합니다. 작업 스케줄러에 의해 수행되며 비교적 느린 시간에 수행이 됩니다. 많은 시간을 이용하여 장기 스케줄링에서는 I/O-bound, CPU bound를 잘 조절하여 효율적으로 ready queue를 만드는 것이 핵심입니다.
• 중기 스케줄링 : 입출력 등의 이벤트에 의해 preempted 된 프로세스들을 스케줄링하는 프로세스 교체 스케줄러입니다. 뒤에서 배울 Swapping을 담당하며 이벤트 처리가 끝나면 swap out 되어 ready queue로 보내줍니다.
• 단기 스케줄링 : CPU를 할당받는 특정 시기, 특정 시간을 프로세스에게 지정합니다. Context Switching이 이 스케줄러에 의해 수행되며 엄청 짧은 시간에 수행됩니다. 보통 CPU 가 idle 상태가 되면 새로운 프로세스를 선택하며 이때 동작을 합니다.

CPU를 사용하기 위해 프로세스는 먼저 job queue에서 준비를 하며, 실행 준비가 완료된 프로세스는 ready queue로 이동합니다. 그 후 스케줄링 알고리즘에 의해 CPU를 할당받게 되면 일정 시간만큼 CPU를 사용해 프로세스가 동작하게 됩니다. 사용 시간이 만려되면 다시 ready queue로 돌아가며 입출력, 통신 등 인터럽트가 발생하게 되면 각 장치의 device queue로 이동하며 CPU를 반환하게 됩니다.

따라서 프로세스는 running -> waiting(blocked), running -> ready(time expired), waiting -> ready, terminate 4가지 상황에서 스케줄링에 의해 움직이게 됩니다.

 

Dispatcher

이러한 프로세스의 과정 중 단기 스케줄러가 선택한 프로세스를 실제로 프로세서에게 할당해 주는 역할을 합니다. Context Switch를 실제로 행하여 레지스터와 프로세스 상태를 적재하고, 프로세스가 실행 중인 PC를 찾아 올바른 위치에서 시작할 수 있게 해 줍니다.

 

스케줄링의 목적

다양한 목적이 있지만 궁극적인 목표는 CPU 사용에 있어서 효율적으로, 프로세스에게 공정하게 자원을 사용하게끔 하는 것입니다. 보통 입출력 이벤트의 경우 CPU 동작 시간에 비해 큰 시간을 소모하므로 스케줄링이 없다면 한 프로세스가 실행 중 입출력 등 인터럽트에 의해 block이 되어 CPU는 긴 시간 동안 idle 상태가 되므로 자원을 낭비하게 됩니다. 이러한 idle 시간을 줄이고 효율적으로 자원을 사용할 수 있도록 합니다.

세분화하면 다음과 같습니다.

• 사용량 극대화 : idle 한 시간을 최소화하고 CPU 사용량을 극대화
• 대기시간 최소화 : Ready queue에 있는 프로세스들의 대기 시간을 최소화
• 응답 시간 최소화 : 작업을 시작하기까지 반응을 하는 시간을 최소화, 주로 context switch에 의해 발생하므로 이를 최소화함 = dispatcher의 성능
• 공정 : 모든 프로세스가 실행될 수 있도록 하며 모든 자원을 공정하게 사용하고 무한정 연기가 없도록 함
• 우선순위 : 프로세스마다 우선순위를 통해 적절히 동작

모든 기준을 맞추는 것은 거의 불가능에 가까우며 이들을 사용할 환경과 목표에 맞게 잘 조율하여 스케줄링 알고리즘을 작성할 필요가 있습니다. 예를 들어 실시간 의사소통이 필요한 일반 사용자용 컴퓨터의 경우 다른 기준보다 응답 시간을 최소화 함을 목표로 둡니다.

 

장기 스케줄러의 경우 ready queue로 보내주는 작업을 하며 비교적 느린 시간 동안 수행할 수 있으므로 복잡한 알고리즘을 수행할 수 있는 시간이 주어집니다. 이 긴 시간을 이용하여 현재 Ready queue에 존재하는 프로세스들의 I/O bound(입출력 시간), CPU bound(동작 시간)를 조합하여 적절히 배치하여 CPU의 사용량을 미리 극대화시킬 수 있습니다.

 

스케줄링 기법

 

비선점 스케줄링 : 할당된 프로세스를 CPU에서 강제로 내보낼 수 없으며 프로세스가 작업을 완료하거나 입출력 이벤트 등 인터럽트 발생 시에만 CPU를 반환하여 다른  프로세스가 사용할 수 있게 됩니다.

• 장점 : 복잡한 알고리즘이 필요 없으며 context switch발생이 매우 적으므로 응답 시간이 적습니다.
• 단점 : 공정성이 없으며 대기시간이 높습니다. 또한 우선순위에 의해 무한정 대기가 발생할 수 있으며 시스템에 중요한 작업을 빠르게 해결하지 못할 수 있습니다. 알고리즘에 따라 인터럽트가 발생하더라도 CPU를 반환하지 않는 경우도 있으며 사용 효율이 줄어듭니다.
• 단순 반복 작업에 유리하여 일괄 처리 방식에 적합합니다.

 

선점 스케줄링 : 할당된 프로세스가 내보내질 수 있으며 우선순위에 따라 동작하는 스케줄링 기법입니다. 우선순위가 높은 프로세스를 빠르게 처리할 수 있으며 주기적으로 인터럽트를 발생 시기는 타이머 인터럽트가 필요합니다.

• 장점 : 우선순위가 높은 프로세스를 빠르게 처리할 수 있으며 비선점 스케줄링에 비하여 대기시간이 적습니다. 적절한 알고리즘을 통해 공정성과 대기시간 최소화, CPU 사용률을 극대화시킬 수 있습니다.
• 단점 : 복잡한 알고리즘이 필요하며 구조 설계가 어렵습니다. 스케줄링 동작에 의해 기본적으로 오버헤드가 있으며 context switch가 자주 발생하므로 응답 시간이 늘어 이 또한 성능에 영향을 미칩니다. 
• 멀티프로그래밍 환경, 여러 개의 프로그램이 실시간으로 동작하는 환경에 사용됩니다. 일반적으로 대부분의 PC의 OS가 사용하는 스케줄링 기법은 선점 스케줄링입니다.