운영체제 강의노트 정리 - CPU 스케줄링

CPU 스케줄링

기본 개념

다중 프로그래밍은 CPU가 어떠한 프로세스를 항상 실행하게 하여 그 사용 효율을 극대화하는 것을 목적으로 한다.

CPU - I/O 버스트 주기

프로세스는 실행되는 동안, CPU 실행과 입출력 대기를 반복한다.

계산 중심 프로세스는 적은 수의, 매우 긴 CPU 버스트를 가지며, 입출력 중심 프로세스는 많은 수의, 짧은 CPU 버스트를 가진다.

일반적으로 짧은 CPU 버스트의 빈도가 많고, 8ms 이상의 CPU 버스트는 거의 없다.

CPU 성능이 발달할수록 프로세스는 입출력 중심 프로세스가 되는 경향이 있다.

CPU 스케줄러

CPU가 유휴 상태가 되면 준비 큐에 있는 프로세스를 하나 선택하여 실행한다. 이 선택은 CPU 스케줄러(단기 스케줄러)가 한다.

선점 스케줄러

CPU 스케줄링은 다음의 상황에서 발생한다.

• 프로세스가 실행중 상태에서 대기중 상태로 전환될 때 (입출력 요청)
• 프로세스가 실행중 상태에서 준비 상태로 전환될 때 (인터럽트 발생)
• 프로세스가 대기중 상태에서 준비 상태로 전환될 때 (입출력 완료)
• 프로세스가 종료될 때

비선점nonpreemptive 스케줄링 방식은 프로세스가 CPU에 할당되면 그 프로세스가 종료되거나 대기중 상태가 될 때까지 CPU를 점유하는 것을 말한다.

선점preemptive 스케줄링 방식은 어떠한 조건이 만족되면 현재 실행 중인 프로세스를 중단하고 다른 프로세스를 CPU에 할당하는 것을 말한다.

디스패처

Dispatcher. 스케줄러가 선택한 프로세스를 CPU에 할당한다.

문맥 전환 / 모드 전환의 책임이 있다.

디스패처가 하나의 프로세스를 중단하고 다른 프로세스를 실행하기까지 소요되는 시간을 디스패치 지연dispatch latency이라고 한다.

스케줄링 기준

CPU 사용 효율CPU utilization : 가능한 한 CPU가 계속 유용한 작업을 하도록 해야 한다.

처리율throughput : 시간당 완료되는 프로세스의 수를 최대화한다.

반환 시간turnaround time : 하나의 프로세스가 제시된 시점에서 그 프로세스가 종료되기까지 걸린 시간을 최소화한다.

대기 시간waiting time : 하나의 프로세스가 준비 큐에서 대기한 총 시간을 최소화한다.

응답 시간response time : 서비스를 요청한 후 그 서비스에 대한 첫 반응이 나오기까지의 시간을 최소화한다.

사용자 관점에서 반환 시간 / 대기 시간 / 응답 시간이 중요하며, 시스템 관점에서 CPU 사용 효율 / 처리율이 중요하다.

스케줄링 알고리즘

FCFS 알고리즘

선입선출 알고리즘. 먼저 요청한 프로세스 순으로 스케줄링한다.

비선점 방식이다.

큐를 활용하여 쉽게 구현할 수 있다.

호위 효과convoy effect가 일어날 수 있는 것이 단점이다. 이는 하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다려야 하는 현상을 말한다.

SJF 스케줄링

Shortest-Job-First. 다음 CPU 버스트 시간이 가장 짧은 프로세스 순으로 스케줄링한다.

같은 CPU 버스트 시간을 가지는 프로세스에 대해서는 FCFS 정책을 따른다.

평균 대기 시간 측면에서는 최적에 가까울 것이다.

프로세스의 다음 CPU 버스트 시간을 예측하는 것이 가장 어렵다.

선점 SJF 알고리즘은 SRTF(Shortest-Remaining-Time-First) 알고리즘이라고도 불린다.

이는 새로운 프로세스가 준비 큐에 도착하면 해당 프로세스의 CPU 버스트 시간과 현재 실행 중인 프로세스의 CPU 버스트 시간을 비교하여, 새로운 프로세스의 CPU 버스트 시간이 더 짧으면 현재 실행 중인 프로세스를 중단하고 새로운 프로세스를 할당한다.

우선순위 스케줄링

우선순위가 높은 프로세스에게 먼저 CPU를 할당한다. 같은 우선순위를 가지는 프로세스에 대해서는 FCFS 정책을 따른다.

SJF는 CPU 버스트 시간이 우선순위로 고려되는 우선순위 스케줄링 알고리즘이라고 말할 수 있다.

우선순위는 보통 정수값으로 나타내어지며, 낮은 수일수록 높은 우선순위를 나타낸다.

우선순위는 운영체제가 결정할 수도 있고, 사용자가 결정할 수도 있다.

선점 우선순위 방식에서는 현재 수행 중인 프로세스의 우선순위와 준비 큐에 도착한 프로세스의 우선순위를 비교하여, 준비 큐에 도착한 프로세스의 우선순위가 더 높으면 현재 실행 중인 프로세스를 중단하고 새로운 프로세스를 할당한다.

굶주림starvation 현상이 발생할 수 있다. 이는 우선순위가 낮은 프로세스는 평생 실행되지 않을 수 있다는 것을 의미한다.

이를 극복하기 위해 노화aging 기법을 사용하여, 대기하는 프로세스의 우선순위를 점전직으로 증가시켜 준다.

라운드 로빈 스케줄링

시분할 시스템에서 사용하는 알고리즘.

시간 조각time quantum, timeslice을 정의하여 이 시간이 경과될 때마다 현재 프로세스를 중단하고 다음 프로세스를 실행한다.

일반적으로 준비 큐를 순환 버퍼로 만들어 구현된다.

기본적으로 선점 방식이다.

성능은 시간 조각에 크게 의존한다. 그 크기가 매우 크면 라운드 로빈 알고리즘은 FCFS 알고리즘과 다를 바가 없게 되며, 반대로 매우 작으면 문맥 전환이 빈번하게 발생한다.

계산 중심 프로세스가 입출력 중심 프로세스보다 많은 시간을 할당받게 되는 것이 문제다. 일반적으로 입출력 중심 프로세스는 자신에게 할당된 시간 조각을 모두 사용하지 않고 입출력 큐에서 대기하게 되며, 이를 해결하기 위해 별도의 큐로 옮겨 해당 큐에 있는 프로세스에 우선적으로 시간 조각을 할당해준다.

반환 시간 또한 시간 조각의 크기에 의존한다.

다중 레벨 큐 스케줄링

준비 큐를 여러 개의 큐로 나누어 사용하며, 프로세스는 그 특성에 따라 특정 큐에 할당된다.

큐 간에 별도의 스케줄링 알고리즘을 사용한다.

다중 레벨 피드백 큐 스케줄링

일반적인 다중 레벨 큐 스케줄링은 유연성이 떨어지며, 다중 레벨 피드백 큐 스케줄링은 프로세스가 큐 간에 이동할 수 있게 해준다.

대화식 프로세스와 입출력 중심 프로세스는 상위 큐에 할당되고, CPU 중심 프로세스는 하위 큐에 할당된다.

다음은 다중 레벨 피드백 큐를 결정하는 파라미터다.

• 큐의 개수
• 각 큐의 스케줄링 알고리즘
• 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 프로세스를 낮은 우선순위 큐로 내려주는 시기를 결정하는 방법
• 프로세스가 준비 큐에 들어올 때 어떤 큐에 할당할지 결정하는 방법

다중 프로세서 스케줄링

특정 입출력 장치가 하나의 프로세서의 시스템 버스에만 연결되어 있다면, 그 장치를 사용하는 프로세스는 해당 프로세서에 할당되어야 한다.

일반적으로 공통된 준비 큐를 사용한다.

각 프로세서가 스스로 큐에서 할당할 프로세스를 선택하면 두 프로세서가 같은 프로세스를 선택하는 문제가 발생할 수 있으므로, 하나의 프로세서는 스케줄링만 담당하도록 할 수 있다.

실시간 스케줄링

실시간 시스템에서 엄격한 실시간 시스템은 반드시 정해진 시간 내에 프로세스의 수행을 완료해야 한다.

엄격한 실시간 시스템에서, 스케줄러는 프로세스가 끝나야 하는 시간 내에 수행을 완료할 수 없다고 판단하면 해당 프로세스의 할당을 거부한다.

완화된 실시간 시스템은 덜 제한적이므로, 실시간 프로세스에 높은 우선순위를 주고, 디스패치 지연이 작도록 하면 된다.

디스패치 지연을 최소화하려면, 시스템 호출 중간에 안전하게 중단할 수 있는 지점을 지정하여 이 지점에서 중단시킬 수 있도록 하고, 실시간 프로세스를 필요로 하는 자원을 낮은 우선순위의 프로세스가 사용하고 있는 경우 우선순위 상속 프로토콜을 이용하여 높은 우선순위를 갖도록 하여 빨리 완료하도록 할 수 있다.

알고리즘 평가

먼저 시스템의 요구사항을 분석하여 알고리즘을 비교할 기준을 정해야 한다.

기준이 정해졌으면 여러 분석 방법을 이용하여 그 기준에 가장 적합한 알고리즘을 선택한다.