Operating System - CPU(resource, process...) Scheduling

 운영체제가 수행하는 핵심 작업 중 하나는 이용 가능한 자원을 관리하고 다양한 프로세스의 자원 요구를 스케줄링하는 것이에요. 이 자원 할당 및 스케줄링 정책은 다음의 세 가지 사항을 고려해야 하죠.

Differential responsiveness(반응 시간 차등화)

 다른 서비스 조건을 지닌 작업을 구별해야 해요. 그러면서도 운영체제는 모든 요구 조건을 포괄적으로 만족할 수 있도록 할당 및 스케줄링을 해야 하죠. 또 이런 결정을 동적으로 내려야 하죠. 만약 프로세스에게 입출력 장치를 할당했을 때 다른 프로세스가 이 장치를 요구할 것에 대비해 최대한 빨리 수행시켜야 하죠.

Faimess(공정성)

 특정 자원을 사용하고자 하는 모든 프로세스, 특히 비슷한 요구를 할 경우 그 자원에 동등하고 공정하게 접근할 수 있어야 해요.

Efficiency(효율성)

 작업 처리량을 극대화해 반응시간을 최소화하고 Time-sharing(시분할 時分割)의 경우 최대한 많은 사용자를 동시에(하는 것처럼) 수용해야 해요.

 

스케줄링의 단계

 프로세스 스케줄링은 수행 단계에 따라 3가지로 나뉘는데 이들은 스케줄링이 요구되는 시점을 기준으로 구분되어요.

Long-term scheduling(장기 스케줄링)

 어느 작업을 커널에 등록시켜 프로세스로 만들 것인가를 결정하는 것으로 작업 스케줄링이라고도 해요.

Batch processing system(일괄 처리 시스템)은 새로 작업이 들어오면 먼저 디스크에 놓아둔 채 일괄 처리 큐에서 대기하도록 한 후 장기 스케줄러를 거쳐 프로세스가 되도록 하고 시분할 시스템은 사용자의 접속 시도를 허용할지 말지를 결정하는 단계예요. 결과적으로 멀티프로그래밍의 정도를 조절하는 역할을 하게 되죠.

이 스케줄링은 수행 횟수가 적으며 FIFO 방식을 사용하지만 입출력 위주의 프로세스와 계산 위주의 프로세스의 수를 적절히 맞추기 위해 우선순위 방식을 사용할 수도 있어요. 

Medium-term scheduling(중기 스케줄링)

 Suspended 상태의 프로세스 중 어느 프로세스에게 메모리를 할당(스왑 인)할 것인가를 정해요.

Shor-term scheduling(단기 스케줄링)

 Ready 상태에 있는 프로세스 중 어느 프로세스에게 CPU를 할당할지 정해요. 프로세스 스케줄러 또는 Dispatcher에 의해 수행되죠. 또 입출력 또는 타임 아웃, 시스템 콜 등 여러 이유에 의해 가동되는데 횟수도 잦으니까 한 번에 드는 시간을 최대한 줄이는 것이 중요해요.

 

스케줄링의 목적과 기준

 스케줄링은 CPU를 줄 프로세스를 잘 선택해서 전체적인 시스템의 성능을 향상하기 위해 있어요. 응답 시간이 대표적인 지표인데 응답 시간은 프로세스의 요청에 대해 시스템이 최초로 출력할 때까지 (Real-time으로 체크한)걸린 시간이에요. 일괄 처리의 경우 요청부터 결과가 나올 때까지의 시간인 반환 시간이 중요 지표가 되고 얼마 후에 수행이 완료될 것이라는 예측 가능성도 지표로 활용할 수 있어요. 대화식 시스템의 경우 응답 시간이, 일괄 처리 시스템에서는 CPU가 얼마나 안 쉬고 일했는가를 나타내는 처리량 또한 중요한 지표이죠.

 

스케줄링 기법

 Non-pre-emptive(비선점)와 pre-emptive(선점) 스케줄링으로 나뉘는데 비선점 스케줄링은 한 프로세스가 CPU를 할당받고 작업 완료 등으로 CPU를 자진 반납할 때까지 CPU를 독점할 수 있는 방식이고 선점 스케줄링은 우선순위가 높은 프로세스가 CPU를 뺏을 수 있는 방식이에요.

FIFO(First In First Out)

 프로세스가 레디 큐에 도착한 순서대로 CPU를 할당받으며 자진 반납할 때까지 실행을 보장하는 비선점 방식의 스케줄링이에요.

SPN(SJF)(Shortest Process Next(Shortest Job First))

 레디 큐에서 기다리고 있는 프로세스 중 CPU 요구량이 가장 적은 프로세스를 먼저 실행해주는 비선점 방식의 스케줄링이에요.

SRT(Shortest Remaining Time)

 SPN을 선점 방식으로 운영하는 것이에요.

HRRN(Highest Response Ratio Next)

 가장 높은 반응률을 가진 프로세스를 먼저 수행하여 프로세스의 무한 대기 현상을 방지하기 위한 기법이에요.

RR(Round-Robin)

 FIFO 스케줄링을 기반으로 하지만 각 프로세스는 CPU를 사용할 수 있는 최대 시간을 가지며 그 시간 할당량을 다 쓰면 Time out 인터럽트에 의해 CPU를 뺏기는 선점 방식의 스케줄링이에요. 실제로는 원형 큐를 사용하며 우선순위가 함께 사용되어 우선순위가 높은 프로세스를 먼저 수행시킬 수도 있어요.

 

Real-time scheduling(실시간 스케줄링)

 실시간 시스템은 실행될 모든 프로세스가 정해진 시간 안에 완료되어야 하는 시스템이에요. 여기에는 작업이 마감(Deadline) 안에 완료되지 않으면 치명적인 결과가 나오는 경성(硬性) 실시간 시스템(hard real-time system)과 마감 안에 완료되지 않으면 데이터 손실 등 피해는 있으나 시스템의 운영은 가능한 연성(軟性) 실시간 시스템(soft real-time system)이 있어요.

RM algorithm(Rate Monotonic)

 프로세스들이 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감은 각자의 주기와 같을 때, 주기가 짧을수록 높은 우선순위를 받는 대표적인 정적 스케줄링 방식이자 선점 방식이에요.

EDF algorithm(Earliest Deadline First)

 프로세스의 마감이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링이에요.