컴퓨터 운영체제 CPU 스케줄링

CPU 스케줄링

스케줄링(Scheduling)은 운영 체제의 기본 기능으로, 모든 시스템 자원은 사용되기 전에 스케줄링되어야 합니다. CPU는 시스템 자원의 하나로, 프로세스가 작업을 처리하려면 우선 CPU를 할당받아야 합니다. CPU 스케줄링이란 CPU를 언제 어느 프로세스에게 할당할 것인지를 결정하는 작업입니다.

 

스케줄링의 목적

CPU 스케줄링 기법을 결정할 때는 아래와 같은 목적을 고려해야 합니다.
공정한 스케줄링 - 스케줄링을 할 때 모든 프로세스를 공평하게 취급해야 하며 어떤 프로세스도 무한정 지연되지 않아야 합니다.
처리량의 최대화 - 프로세스들의 단위 시간당 처리량을 최대화하도록 스케줄링해야 합니다.
응답 시간의 최소화 - 대화식 사용자에게 응답 시간을 최소화하도록 스케줄링해야 합니다.
예측 가능한 반환 시간 - 시스템 부하에 관계없이 작업은 동일한 시간 내에 동일한 비용으로 완료되어 반환 시간을 예측할 수 있어야 합니다.
균형 있는 자원 사용 - 유휴 상태의 자원을 사용하는 프로세스에 양질의 서비스를 제공하여 시스템 자원들이 골고루 사용되도록 해야 합니다.
응답 시간과 자원 활용 간의 조화 - 응답 시간을 최소화하려면 충분한 자원을 확보해야 합니다. 자원을 균형 있게 활용하려면 응답 시간이 커질 수밖에 없으므로, 응용에 따라 응답 시간과 자원 활용도를 적절하게 조화시켜야 합니다.
프로세스 실행의 무한 연기 배제 - 특정 프로세스의 실행이 무한 연기되지 않도록 노화(aging) 기법을 사용하여 실행을 보장해야 합니다.
우선순위제 실시 - 프로세스에 우선순위를 부여하고 우선순위가 높은 프로세스가 먼저 실행되도록 합니다.
시스템의 과도한 부하 방지 - 시스템에 과도한 부하가 걸리면 새로운 프로세스의 생성을 자제하거나 개별 프로세스의 서비스를 줄이도록 스케줄링하여 부하를 방지합니다.

 

 

스케줄링의 성능 기준

CPU 스케줄링 기법의 성능을 비교하는 기준은 아래와 같습니다.
CPU 활용률 - CPU 활용률은 CPU가 작동한 총 시간 대비 실제 사용 시간을 의미합니다.
처리율 - 단위 시간당 완료된 프로세스의 개수를 의미합니다.
반환 시간 - 작업의 제출부터 완료되기까지 소요된 시간입니다.
대기 시간 - 프로세스가 준비 큐에서 스케줄링이 될 때까지 기다리는 시간입니다.
응답 시간 - 대화형 시스템에서 터미널을 통해 입력한 명령의 처리 결과가 나올 때까지의 시간입니다.

 

CPU 스케줄링 기법 종류

CPU 스케줄링 기법을 알고리즘에 따라 분류하면 아래와 같습니다.
FCFS(First-Come First-Served) - 이 기법은 프로세스들이 준비 큐(Ready Queue)에 도착한 순서대로 CPU를 할당하는 비선점 방식입니다.
라운드 로빈(Round-Robin) - 이 기법은 FCFS 기법으로 프로세스를 처리하되, 프로세스마다 동일한 CPU 시간(Time Quantum)을 할당합니다. 프로세스가 할당된 시간 내에 처리를 완료하지 못한다면 대기 중인 프로세스에게 CPU를 양도하고 준비 큐의 맨 뒤로 이동합니다. 할당된 시간이 끝나면 다음 프로세스가 CPU를 차지하므로 선점 방식입니다.
SJF(Shortest Job First) - 이 기법은 준비 큐에서 대기하고 있는 프로세스 중 예상 실행 시간이 가장 짧은 것을 우선 처리하는 비선점 방식입니다.
SRT(Shortest Remaining Time) - 이 기법은 준비 큐에서 대기하는 프로세스 중 잔여 실행 시간이 가장 짧을 것으로 예상되는 프로세스를 우선 처리하는 선점 방식입니다.
HRN(Highest Response Ratio Next) - 이 기법은 실행 시간이 짧은 작업을 우선 처리하여 긴 작업의 대기시간이 길어지는 SJF 기법의 단점을 보완한 비선점 방식입니다. 스케줄링 시점에서 매번 프로세스의 응답률(우선순위)을 계산한 후 가장 높은 응답률을 가진 프로세스를 우선 처리합니다. 응답률은'(대기 시간 + 서비스 시간)/서비스 시간'으로 구합니다.
우선순위(Priority) - 이 기법은 프로세스마다 우선순위를 부여하고 최상위 우선순위 프로세스를 먼저 처리하는 비선점 방식입니다. 동일한 우선순위를 가진 프로세스들은 FCFS 방식으로 CPU를 할당받으며, 상위 우선순위 큐가 비면 그다음 우선순위 큐의 프로세스들이 CPU를 할당받습니다.
MLQ(Multi-Level Queue) - 이 기법은 작업을 특성에 따라 다수의 그룹으로 분류하고, 각 그룹마다 별도의 준비 큐를 배정하여 스케줄링하는 방식입니다. 각 큐마다 별도의 스케줄링 알고리즘을 적용합니다. 보통 시스템에는 최고 우선순위를 가지는 상위 단계부터 최저 우선순위를 갖는 하위 단계까지 총 5개의 준비 큐(시스템 작업, 대화형 작업, 편집 작업, 일괄 처리형 작업, 학생 작업 등)가 존재합니다. 하위 단계의 작업이 실행 중일 때 상위 단계의 큐에 새로운 작업이 들어오면 실행 중인 작업을 중단하고 CPU를 반환하는 선점 방식입니다.
MFQ(Multi-Level Feedback Queue) - 이 기법은 입출력 위주 프로세스와 CPU 위주 프로세스의 특성에 따라 CPU 할당량을 다르게 부여하는 선점 방식입니다. 새로운 프로세스는 최고 우선순위를 가지는 단계 1에서 수행을 시작하고, CPU 할당량 내에 작업을 완료하지 못하면 단계 2로 이동합니다. 단계 n에서는 작업이 완료될 때까지 라운드 로빈 방식으로 반복 처리됩니다.