CPU 스케줄링

nyoung·2023년 10월 12일

cs

목록 보기

6/10

📆 CPU 스케줄링(CPU Scheduling)

CPU 스케줄링이란?

CPU 스케줄링은 다수의 프로세스가 CPU 자원을 공유할 때 실행 순서를 관리하는 방법이다. 이 스케줄링은 프로세스의 우선순위, 대기 시간, 및 도착 시간을 고려하여 CPU에 할당되는 순서를 결정하며, 효율적인 자원 활용과 응답 시간 최소화를 목표로 한다.

CPU 스케줄링의 목표

공평성 : 모든 프로세스가 CPU를 공평하게 사용할 수 있어야 한다.
응답 시간 최소화 : 사용자 또는 응용 프로그램의 요청에 신속하게 응답해야 한다.
시스템 활용도 최대화 : CPU 자원을 최대한 활용하여 시스템 성능을 최적화해야 한다.

CPU 스케줄링이 발생하는 상황

프로세스 실행 시작 또는 종료
프로세스 대기 (I/O 작업 등)
우선 순위 변경
CPU 할당 시간을 초과했을 때 (타이머 인터럽트)
- 각 프로세스마다 지정된 최대 시간을 타임 퀸텀(Time Quantum) 또는 타임 슬라이스(Time Slice) 라고 부른다.

스케줄링 기법

선점 스케줄링(Preemptive Scheduling)
실행 중인 프로세스가 다른 프로세스에 의해 강제로 중단될 수 있는 방식. 우선순위가 높은 새로운 프로세스나 더 중요한 작업이 도착할 때, 현재 실행 중인 프로세스를 일시 중단하고 CPU를 새로운 프로세스에 할당.
Timeout 상황, I/O Interrupt, System call 등이 발생한 경우 현재 실행 상태에 있는 프로세스의 CPU를 강제로 회수하고 다른 프로세스에게 CPU를 할당해줄 수 있는 스케줄링 방식
비선점 스케줄링(Non-preemptive Scheduling)
한 번 CPU를 할당받은 프로세스는 자발적으로 완료될 때까지 실행을 유지하는 방식. 다른 프로세스가 도착하거나 우선순위가 높아지더라도 현재 실행 중인 프로세스는 중단되지 않는다. 대부분의 일반적인 데스크톱 및 서버 운영 체제에서 사용된다.

	선점 스케줄링 (Preemptive Scheduling)	비선점 스케줄링 (Non-preemptive Scheduling)
응답 시간	짧음	상대적으로 길음
프로세스 중단	가능	불가능
작업 완료 시간 예측	어려움	쉬움
작업 간 경쟁	발생함	발생하지 않음
대표적인 알고리즘	라운드 로빈, 우선 순위, 다단계 큐 등	FCFS, SJF 등

프로세스 상태 전이

생성(New): 프로세스가 생성되었지만 아직 CPU를 할당받지 못한 초기 상태입니다.
준비(Ready): 프로세스가 실행을 기다리는 상태로, CPU를 할당받을 준비가 된 상태입니다.
- 인터럽트(Interrupt) : CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 예외상황이 발생하여 처리가 필요할 경우에 마이크로프로세서에게 알려 처리할 수 있도록 하는 것. 인터럽트 신호를 받게되면, 실행중이던 프로세스는 준비 상태로 전이되고, 우선순위(Priority)가 높은 프로세스를 실행 상태로 전이시킨다.
실행(Running): dispatch에 의해 CPU를 할당받아 명령어를 실행 중인 상태입니다.
- 디스패치(Scheduler Dispatch) : 프로세스 상태를 변환하고 스케줄링 알고리즘을 사용하여 CPU를 프로세스에 할당하는 역할.
대기(Waiting/Blocked): 프로세스가 어떤 이벤트(예: 입출력 완료)가 발생할 때까지 대기하는 상태입니다.
- 입출력 혹은 이벤트 대기(I/O or event wait) : CPU를 점유하고 있는 프로세스가 I/O 작업을 기다리거나 특정 이벤트가 발생할때, 실행되고 있는 프로세스는 실행 상태에서 대기 상태에 있는 상태.
- 입출력 혹은 이벤트 완료(I/O or event completion) : 프로세스가 I/O 작업을 완료하거나 기다리던 이벤트가 발생하면, 해당 작업이 완료된 상태.
종료(Terminated): 프로세스의 실행이 완료된 상태이며, 종료된 프로세스의 자원은 반환됩니다.

📎 스케줄링 알고리즘

✅ 선점형

SRT(Shortest Remaining Time)
현재 실행 중인 프로세스의 남은 시간과 대기 큐에 프로세스의 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법 (비선점 기법인 SJF 알고리즘의 선점 형태로 변경한 기법) 평균 대기 시간을 최소화하는 데 효과적이지만, 실행 시간을 정확하게 예측하는 것이 어려워 긴 프로세스가 무한정으로 기다리는 기아 상태(Starvation State) 가 발생할 수 도 있다.
라운드 로빈 (Round Robin)
각 프로세스에 시간 할당량(time quantum) 을 부여하고, 각 프로세스가 할당량을 소비할 때까지 실행된다. 그 후, 다음 프로세스로 넘어가는 방식으로 공평한 CPU 사용을 지향한다. 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 시간이 작을 경우 오버헤드가 자주 발생된다.
우선 순위 (Priority Scheduling)
준비상태 큐에서 기다리는 각 프로세스에 우선순위를 할당하고, 우선순위가 높은 프로세스가 CPU를 선점할 수 있는 방식이다. 이를 통해 중요한 작업이 먼저 처리되도록 한다.
다단계 큐 (MLQ)
프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용한다. 작업들을 여러 종류의 그룹으로 분할. 큐들간에 프로세스 이동이 불가능하다. 각 큐는 자신만의 독자적인 스케줄링을 가진다. 상위 우선 순위의 큐가 Empty 이면 하위 우선순위의 큐의 프로세스가 수행된다.
다단계 피드백 큐 (MLFQ)
특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법. 새로운 프로세스는 높은 우선순위 큐에서 시작하며, 실행 시간이 길어질수록 낮은 우선순위 큐로 이동한다. 우선순위가 높은 단계의 큐일수록 시간 할당량을 작게 설정된다. Aging(노화) 메커니즘을 사용하여 기아 상태를 방지한다. 현대 OS에서 라운드 로빈 방식과 함께 가장 많이 사용되는 스케줄링 기법.

노화 메커니즘이란?

스케줄링에서 사용되는 기법으로, 일정 시간이나 특정 조건에 따라 우선순위를 조정하거나 증가시키는 방법이다. 주로 다단계 피드백 큐 스케줄링에서 활용되며, 기아 상태(Starvation)를 방지하고 모든 프로세스가 공정하게 CPU 자원을 이용할 수 있도록 한다.

노화 메커니즘의 작동 원리

스케줄러가 다음에 실행할 프로세스를 선택할 때, 우선순위와 노화 값을 함께 고려한다.
노화값은 프로세스의 대기 시간 또는 대기 큐에서 머문 시간에 기반하여 계산하므로 노화 값이 높을수록 프로세스의 우선순위가 증가하므로 오랫동안 대기한 프로세스에게 높은 우선순위를 부여한다.
따라서 오랫동안 대기한 프로세스의 우선순위가 높아져, 해당 프로세스는 상위 우선순위 큐로 이동하여 CPU를 할당받을 기회를 얻게 된다.

❎ 비선점형

FCFS (First-Come, First-Served)
가장 간단한 스케줄링 알고리즘 중 하나로, 먼저 도착한 프로세스가 먼저 CPU를 할당받는다.
응답 시간 예측이 어려워, 긴 프로세스가 먼저 도착하면 기다리는 시간이 길어질 수 있다.
SJF (Shortest Job First)
프로세스의 예상 실행 시간에 따라 우선순위를 정한다. 예상 실행 시간이 가장 짧은 프로세스가 먼저 실행되므로, 대기 시간을 최소화하고 자원을 효율적으로 활용할 수 있다.
but, 사용시간이 긴 프로세스는 거의 영원히 할당을 못받아 기아 상태가 발생할 수도 있다.
HRN (Highest Response ratio)
실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로 우선순위 계산 결과 값이 높은 것부터 우선순위가 부여된다. 대기 시간이 길수록 계산 결과가 높다. 우선순위 = (대기시간 + 서비스시간 / 서비스시간) 큰 프로세스일수록 우선순위가 낮으므로 평균 응답시간도 단축된다.