CPU 스케쥴링 정리

devdo·2021년 12월 25일

CPU 스케쥴링 운영체제

컴퓨터구조

목록 보기

2/2

CPU Scheduling이란?

OS가 CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업 => 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것이라 볼 수 있음.
프로세스들에게 자원을 최대한 공평하게 배분하며 처리율과 CPU 이용률을 증가시키고, 오버헤드, 응답시간(Response time / Turnaround time), 대기시간을 최소화하기 위한 기법
선점형 스케줄링(Preemptive Scheduling) 과 비선점형 스케줄링(Non-preemptive / Cooperative Scheduling) 이 있음
메모리에 여러 개의 프로세스를 올려놓고(다중 프로그래밍), CPU의 가동시간을 적절히 나누어(시분할) 각각의 프로세스에게 분배하여 실행

프로세스 상태 전이

생성(New)
제일 첫번째로 New에서 Ready로 전이되는 과정입니다. 프로세스가 생성되고 나서 생성된 프로세스는 준비(Ready) 상태에 머뭅니다. 준비 상태는 CPU를 점유하고 있는 상태가 아니라, CPU를 점유하길 희망하는 상태입니다. 준비 상태에서 실행 상태로 넘어가려면 작업 스케줄러가 선택해 주어야만 합니다.

디스패치(Dispatch)
디스패치란 준비 상태에서 실행 상태로 전이되는 과정을 말하며, 이는 작업 스케줄러가 해당 프로세스를 선택하여 실행되어지는 것으로, 이때 실행된 프로세스가 CPU를 점유하게 됩니다.

인터럽트(Interrupt)
인터럽트 신호를 받게되면, 실행중이던 프로세스는 준비 상태로 전이되고, 우선순위(Priority)가 높은 프로세스를 실행 상태로 전이시킵니다. (프로세스는 각각 우선순위를 부여받고, 우선순위에 따라 프로세스가 준비 상태로 전이되거나, 실행 상태로 전이됩니다.)

입출력 혹은 이벤트 대기(I/O or event wait)
CPU를 점유하고 있는 프로세스가 입출력 처리를 해야만 하는 상황이라면, 실행되고 있는 프로세스는 실행 상태에서 대기/보류 상태로 바뀝니다. 그리고 대기 상태로 바뀐 프로세스는 입출력 처리가 모두 끝날때까지 대기 상태로 머뭅니다. 그리고 실행 상태이던 프로세스가 대기 상태로 전이됨과 함께, 준비 상태이던 또다른 프로세스가 실행 상태로 전이됩니다. 또한 대기 상태인 프로세스는 우선순위가 부여되지 않으며 스케줄러에 의해 선택될 수 없습니다.

입출력 혹은 이벤트 완료(I/O or event completion)
입출력 처리가 끝난 프로세스는 대기 상태에서 준비 상태로 전이되어 스케줄러에게 선택될 수 있게 됩니다. 추가로 프로세스를 종료(Terminate)시킬 때에도 Blocked 상태를 거칠 수 있다는 사실을 기억해 두시길 바랍니다.

출처: https://blog.hexabrain.net/256 [끝나지 않는 프로그래밍 일기]

비선점 vs 선점 스케줄링

비선점 스케줄링

프로세스가 입출력 요구 등으로 CPU를 자진 반납할 때까지 CPU에 의한 실행을 보장해주는 스케줄링이다. 작업 실행 시간 전체 또는 한번의 CPU 배당에 적용된다.
모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야할 수도 있다. (convey 현상)
처리시간 편차가 적은 특정 프로세스 환경에 용이

선점 스케줄링

시분할 시스템에서 타임슬라이스가 소진되었거나 인터럽트 혹은 시스템 호출 종료로 인한 여파로 높은 우선순위의 프로세스가 현 프로세스보다를 강제로 중단시키고 CPU를 회수하는 스케쥴링 방식이다.
비교적 응답이 빠르다는 장점이 있지만, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드를 초래
실시간 응답환경, Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 할 경우 등에 유용

CPU 스케쥴링	종류
비선점 스케쥴링	FCFS(First-Come-Fist-Served) / 최단 작업 우선(SJF, Shortest Job First) / 우선순위 스케줄링 (Priority Scheduling)
선점 스케쥴링	라운드 로빈 스케줄링 / 다단계 큐 스케줄링 / 다단계 피드백 큐 스케줄링

비선점 알고리즘 1. FCFS(First-Come-Fist-Served)

프로세스 도착순으로 CPU를 배정한다. 즉, 준비 큐에 도착한 순서대로 CPU를 배정한다. (실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS를 적용한다.)
시분할 시스템에서는 백그라운드 또는 실시간 프로세스 등의 타임 슬라이스를 적용하지 않는 프로세스에 대해서도 사용할 수 있다.
호위 효과(Convoy Effect) 문제가 있다. 즉, 수행 중인 긴 작업을 여러 개의 짧은 작업이 기다릴 수 있다. 이는 짧은 작업의 반환시간과 대기시간을 늘려 평균반환시간과 평균대기시간을 늘린다.
따라서 도착 순서 이외에 특별한 추가 정보를 얻을 수 없는 경우(배치 작업 등의 장기 스케줄러)에 주로 활용한다.

비선점 알고리즘 2. 최단 작업우선(SJF, Shortest Job First)

대기하는 작업 중 CPU Burst Time이 가장 작은 작업에 CPU를 할당하는 기법
평균 대기 시간에 있어서는 최적의 알고리즘 (두번째 수행되는 작업이 가장 짧은 시간을 대기하려면 첫번째 작업이 전체 중 가장 짧은 작업이어야 한다. 이는 세번째, 네번째도 마찬가지이다. 결국엔 SJF와 동일하다.)
다만 도착시점(arrival time)을 고려하면 아직 도착하지 않은 프로세스는 스케줄링의 대상이 되지 않기 때문에 더 긴 프로세스가 먼저 할당될 수 있다.
Burst Time이 동일할 경우 FCFS로 도착순으로 처리한다.
문제점 : 사실상 CPU의 Burst Time은 미리 알기 어렵다. 장기 스케줄링에서는 작업시간 예측치를 함께 제출할 수 있다. 하지만 단기 스케줄링에서는 다음 CPU Burst Time을 미리 알 수 없어 사용하기 어렵다.
해결방안 : 이전 Burst Time을 분석해 다음 Burst Time을 예측한다. 다음 Burst Time을 이전 Burst Time들의 지수적 평균으로 간주하는 방법이 주로 쓰인다.
Burst Time : CPU가 일을 수행하는 시간

선점 알고리즘 1. 라운드 로빈(Round Robin) 스케줄링

준비 큐를 원형 큐로 간주하고 순환식으로 각 프로세스에게 작은 단위의 시간량(타임퀀텀)만큼씩 CPU를 할당한다.
실행상태의 프로세스는 타임퀀텀이 지나면 선점된다. (타임퀀텀은 타임슬라이스와 마찬가지의 개념이다.)
새로운 프로세스가 부가될 때는 큐의 맨 뒤에 덧붙여 진다.
물론 입출력이 발생하면 CPU를 자진반납한다.
이론상 N개의 프로세스가 1/N 속도로 동시에 실행되는 셈이다. 준비 큐에 N개의 프로세스가 있고, 타임슬라이스가 Q이면 각 프로세스는 (N-1)* Q 시간 이내에 다음 슬라이스를 받게된다. (문맥교환 시간은 고려하지 않았다.)
아무리 짧은 작업이라도 앞선 다른 작업이 큐 앞에 있다면 한 번이라도 각각의 타임퀀텀을 거쳐야하기 때문에 일반적으로 평균반환시간이 SJF보단 크다. 하지만 모든 프로세스가 공정하게 기회를 얻게되어 기아상태가 발생하지 않는다는 장점이 있다.
타임퀀텀의 크기에 따라 성능이 큰 영향을 받는다. 타임퀀텀이 매우 커지면 FCFS와 유사해진다. 매우 작아지면 잦은 문맥교환에 따라 오버헤드가 커져 처리율이 감소한다.
일반적으로 타임퀀텀이 커지면 평균 반환시간이 개선될 수 있다. 많은 작업이 한번에 처리될 확률이 증가되기 때문이다. 다만 많은 짧은 작업이 긴 작업들보다 순서상 늦게 처리되는 경우가 발생할 수 있어 무조건 그런 것은 아니다. 만약 대부분의 프로세스가 타임퀀텀내에 하나의 CPU Burst를 처리한다면 평균반환시간이 개선될 것이다. 따라서 80% 정도의 CPU Burst Time은 타임퀀텀보다 짧도록 조정하는 것이 가장 적절하다.

선점 알고리즘 2. 다단계 큐 스케줄링

목적에 맞도록 우선순위들을 정하고, 그 우선순위마다 준비 큐를 따로 설정하는 것이다.
가장 높은 우선 순위 큐의 프로세스에 CPU를 할당한다.
각 큐는 독자적으로 라운드로빈이나 FCFS같은 알고리즘을 사용할 수 있다.
대화형, 배치 등 프로세스의 성격에 따라 우선 순위를 부여한다. (예 : 시스템작업 / 대화형 작업 / 대화형 편집 / 일괄 처리 / 학생 작업)