CPU 스케줄링(CPU Scheduling)

CPU 스케줄링이란?

모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어한다. 이러한 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하기 위해 운영체제는 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 기다리게 할지를 결정하며 이를 CPU 스케줄링이라 한다.

 

프로세스 우선순위

아주 단순하게 생각했을 때, cpu를 사용하고 싶어하는 프로세스들에게 차례로 돌아가며 cpu를 이용하게 하는 방법이 있다.

하지만 이는 그닥 좋은 방법이 아니다. 이유는 프로세스마다 우선순위가 다르기 때문이다.이를 이해하기 위해 I/O bound 프로세스와 CPU bound 프로세스를 비교해보자.

( 이전 포스팅에서 언급했듯이 프로세스 우선순위는 PCB에 저장되어있다)

 

 

cpu burst : 프로세스가 실행되는 동안 CPU에서 연산을 처리하고있는 시간이다.

I/O burst : 프로세스가 실행되는 동안 입출력 장치에서 작업을 하고있는 시간이다. 예를 들면 키보드로 입력을 기다리고 받는 시간, 저장장치에 접근하는 시간 등이 포함된다.

 

일반적으로 I/O burst는 오랜 시간이 걸린다. 왜냐하면 CPU에 비해 입출력장치는 처리속도가 매우 느리기 때문이다.

 

CPU Bound Process : 프로세스가 실행되는 동안 CPU Burst시간이 I/O Burst시간보다 더 긴 process를 말한다. 복잡한 수학 연산, 컴파일, 그래픽 처리 작업 등의 경우 CPU Bound Process에 해당한다.

I/O Bound Process : 프로세스가 실행되는 동안 I/O Burst 시간이 CPU Burst 시간보다 더 긴 process를 말한다. 사용자와 상호작용 해야 하는 process가 대표적이다. 

 

I/O Burst 시간에 있는 동안 CPU는 Wait상태가 되며 입출력 장치가 처리해야하는 작업이 끝날 때 까지 CPU는 IDLE(유휴상태)에 돌입한다. 쉽게말해 I/O장치가 작업을 처리하는동안 CPU는 할 일이 없어 쉬고있다는 뜻이다. Process가 I/O 작업에 있는동안 CPU를 다른 프로세스에 할당하여 CPU를 놀지않고 다른 작업을 할 수 있게 한다면 좀 더 효율적이다.

 

아래 그림을 확인해보자. 네모로 표시된 부분은 CPU가 일하고 있는 상태이며 실선으로 표시되는 부분은 CPU가 쉬고있는 상태라고 할 수 있다. 위는 CPU Bound Process에 해당하고 아래는 I/O Bound Process에 해당한다. I/O Bound Process는 CPU IDLE상태가 매우 많은 반면 CPU Burst시간은 매우 짧다. 따라서 I/O Bound Process의 우선순위를 높게 잡아주면

I/O Bound Process는 짧게 cpu를 사용하고 다시 반환하여 이때 cpu를 CPU Burst Process에 할당할 수 있어 작업이 더 효율적으로 진행될 수 있음을 예상할 수 있다. 반면 CPU Burst Process의 우선순위가 높다면 I/O Burst Process는 잠깐만 cpu를 사용하면 금방 반환하고 입출력장치에서 작업이 진행될 수 있음에도 불구하고 프로세스가 작업이 중지된 상태로 오랫동안 대기해야 할 것이다.

 

 

프로세스 우선순위 확인

리눅스 터미널에서 ps -el명령어를 입력할 경우 프로세스 우선순위를 확인할 수 있다.

PRI(priority)가 우선순위를 뜻하며 프로세스마다 우선순위가 다른것을 확인할 수 있다.

nice명령어를 이용하면 프로세스의 우선순위를 변경할 수도 있다. 이것은 다른 포스팅에서 실습해보겠다.

 

스케줄링 큐

운영체제가 매번 모든 PCB를 검사하여 CPU에 프로세스를 할당하는것은 비효율적이다. Scheduling Queue에 대기하는 프로세스를 삽입하고 꺼내서 쓰는것이 조금더 효율적일것이다. Scheduling Queue에는 여러 종류가 있다.

cpu를 쓰고싶은 프로세스가 대기하는 ReadyQueue, 하드 디스크를 쓰고싶은 프로세스가 대기하는 Waiting Queue, 프린터를 쓰고 싶은 프로세스가 대기하는 Waiting Queue 등이 존재할것이다.

 

선점형 스케줄링 vs 비선점형 스케줄링

스케줄링 알고리즘은 크게 두가지 방식으로 구분될 수 있다. 하나는 선점형(preemitive)스케줄링 다른 하나는 비선점형(non-preemitive)스케줄링 방식이다. 

 

어떤 프로세스가 cpu를 할당하여 실행중이라고 가정하자. 이 때, 다른 프로세스가 지금 당장 cpu를 사용하길 요청한다면 어떻게 될까?

방법1 : 지금 CPU를 사용중인 프로세스로부터 cpu를 빼앗아 다른 프로세스에게 할당할 수 있다.

방법2 : CPU를 사용중인 프로세스의 작업이 끝 날 때까지 다른 급한 프로세스를 기다리게 하고 이후에 CPU를 요청한 프로세스에게 CPU를 할당해줄 수 있다.

 

선점형 스케줄링은 우선순위가 높은 프로세스가 언제든 끼어들어 cpu를 뺏을수 있다. 다만 문맥교환이 자주 발생하여 문맥교환 오버헤드가 커질 수 있다는 단점이 있다.

 

디스패처(Dispatcher)

cpu 스케줄링에 포함된 하나의 요소로 디스패처가 있다. 디스패처는 CPU의 제어를 스케줄러가 선택한 프로세스에게 주는 모듈이머 다음과 같은 작업을 진행한다.

1. 문맥교환(Context Switch)

2. 사용자 모드로 전환

3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

 

디스패처는 모든 프로세서의 문맥 교환시 호출되므로 최대한 빨리 수행되어야한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 Dispatch latency라 부른다.

스케줄 알고리즘

스케줄링 알고리즘에는 여러가지 방식이 존재한다. 단순한 방식부터 복잡한 방식까지 살펴보며 단순한 방식에서의 문제점을 복잡해진 스케줄링 알고리즘에서는 어떻게 해결했는지 살펴보겠다.

 

1.선입 선처리 스케줄링(First-Come,First-Served Scheduling)

2. 최단 작업 우선 스케줄링(Short-Job, First-Served Scheduling)

3. 우선순위 스케줄링(Priority Scheduling)

4. 라운드 로빈 스케줄링(Round-Robin Scheduling)

5. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

6. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

 

1. 선입 선처리 스케줄링(First-Come, First-Served Scheduling)

이하 FCFS 스케줄링의 경우 가장 간단한 방식의 스케줄링이다. 이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 선입 선처리 정책의 구현은 선입선출(FIFO)큐로 쉽게 관리할 수 있다. 프로세스가 Ready상태가 되면 PCB를 ReadyQueue의 가장 뒷단에 연결한다. 프로세스가 자유 상태가 되면 ReadyQueue의 가장 앞 부분에 있는 프로세스에게 할당된다.

 

FSFS 스케줄링의 예시를 Gantt차트로 나타내어 살펴보자.

Gantt 차트: 참여한 각 프로세스의 시작 시간과 종료 시간을 포함하여 특정 스케줄 기법을 도식화하는 막대형 차트이다.

P₁이 가장 먼저 도착하여 24초 동안 cpu를 할당받았으며 그이후 P₂, P₃가 차례로 CPU를 할당받았다.

<waiting time>

P₁: 0

P₂: 24

P₃: 27

average waiting time: (0+24+27)/3 = 17

임을 확인할 수 있다.

 

FCFS 스케줄링 방식은 비선점 방식이다. 일단 CPU가 한 프로세스에 할당되면 그 프로세스가 종료하든지 또는 입출력 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유한다.

 

단점: 하나의 CPU Bound Process와 여러 I/O Bound Process가 ReadyQueue에 존재한다고 가정하자. CPU Bound가 cpu에 할당되어 있는동안 I/O Bound process들은 입출력을 끝내고 다시 ReadyQueue로 이동하여 CPU를 기다린다. 이 시간동안 입출력 장치들은 유휴 상태가 된다. CPU Bound Process가 자신의 CPU Burst를 끝내고 입출력 장치로 이동한다. 모든 입출력 중심의 프로세스들은 매우 짧은 CPU Burst를 끝내고 다시 I/O Queue로 이동한다. CPU Bound Process는 다시 CPU를 할당받고 오랜 시간동안 CPU를 사용하는데 이동안 다시 I/O Bound Process들이 ReadyQueue에서 대기하게되며 입출력 장치들은 다시 유휴상태로 대기된다. 모든 다른 프로세스들이 하나의 프로세스가 cpu를 양도하기를 기다리는것을 호위 효과(Convoy Effect)라 한다 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때 보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.

 

2. 최단 작업 우선 스케줄링(Shortest-Job, First-Served Scheduling)

이하 SJF스케줄링알고리즘은 가장 작은 CPU Burst를 가진 프로세스에 cpu를 할당한다. 같은 CPU Burst를 가진 프로세스의 경우 먼저 cpu를 요청한 프로세스가 먼저 처리된다. 

SJF는 선점형으로 구현될수도 비선점형으로 구현될수도 있다. 비선점형의 경우를 살펴보겠다.

<Wating time>

P1: 0

P2: 6

P3: 3

P4: 7

Average Waiting Time: (0+6+3+7)/4= 4

 

SJFS 작업의 경우 최소의 평군 대기 시간을 가진다는 점에서 최적임이 증명가능하다.

SJF 알고리즘이 최적이긴 하지만, 실제로 CPU스케줄링으로 적용시키기에는 어려움이있다. 이유는 다음 CPU 버스트의 길이를 알 수 있는 방법이 없기때문이다. 이를 해결하기위해 하나의 방법은 이전 CPU버스트 시간을 다음 CPU버스트의 길이와 유사할것이라 가정하는것이다. 

CPU 버스트 길이의 근사 값을 계산해 가장 짧은 예상 CPU 버스트 길이를 가진 프로세스를 선택하는 것이다.

 

SJFS가 선점형일 경우 이를 최소 잔여시간 우선 스케줄링(Shortest Remaining Time First) 이라 부른다.

 

3. 우선순위 스케줄링(Priority Scheduling)

SJFS는 우선순위 스케줄링의 특수한 형태라고 할 수 있다. 우선순위를 다음 CPU Burst시간의 역으로 잡은 형태가 SJFS이다.우선순위는 정수로 나타나며 운영체제에 따라 작은값이 더 높은 우선순위를 가질 수도 큰 값이 더 높은 우선순위를 가질수도 있다.

여기서 우선순위는 값이 작을수록 우선순위가 높은것으로 가정한다.

<waiting time>

P1: 6

P2: 0

P3: 16

P4: 18

P5: 1

Average Waiting Time: (6+0+16+18+1)/5=8.2

 

우선순위는 내부적 혹은 위부적인 요인들로 결정될 수 있다.

내부적인 요인으로는 시간 제한, 메모리 요구, 열린 파일의 수, 평균 입출력 버스트의 평균 cpu버스트에 대한 비율등이 있다.

외부적인 요인으로는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 타입과 양, 그 작업을 후원하는 부서와같은 정치적인 요인에 의해 결정된다.

 

우선순위 스케줄링은 선점형 혹은 비선점형이 될 수 있다.

선점형에서 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다.

비선점형 에서는 단순히 ReadyQueue의 head부분에 새로운 프로세스를 넣는다.

 

단점:

우선순위 스케줄링 알고리즘의 문제는 기아(starvation)상태 이다.

우선순위 스케줄링 알고리즘을 사용 할 경우 낮은 우선순위 프로세스들이 무한히 대기하는 상태가 발생할 수 있다.

ReadyQueue에 계속해서 우선순위가 높은 프로세스들이 들어와 낮은 프로세스는 영원히 cpu를 할당받지 못할 수도 있다는 말이다.

실제로 1973년 MIT에서 IBM7094를 폐쇄했을때, 1967년에 입력된 낮은 우선순위의 프로세스가 아직도 수행되지 못하고 있는것을 발견했다고 한다.

 

Starvation을 해결하기위한 하나의 방법으로는 aging이 있다. aging은 오랫동안 시스템에서 대기하는 프로세스의 우선순위를 점진적으로 증가시켜주는 방식이다. 예를들어 10분마다 cpu를 점유하지 못한 프로세스의 우선순위를 1씩 상승시켜주는 방식이다.

 

4. 라운드 로빈 스케줄링(Round-Robin Scheduling)

라운드 로빈 스케줄링의 경우 FCFS스케줄링에 time slice(혹은 time quantum이라고도 한다.)을 도입한 방식이다.

이 스케줄링에서는 프로세스의 cpu burst time이 끝나지 않았더라도 time slice시간이 끝나면 운영체제에 인터럽트를 발생시켜 문맥교환을 일으킨다. 실행하던 프로세스는 ReadyQueue의 꼬리에 넣어지고 CPU 스케줄러는 다음 프로세스를 디스패치한다.

물론 CPU Burst시간이 time slice보다 짧을 경우 cpu burst시간이 끝나고 다음 프로세스가 cpu를 할당받는다.

 

여기서 Time Slice는 4ms라 가정한다.

<Waiting Time>

P1: 6

P2: 4

P3: 8

Average Waiting Time: 18/3 = 6ms

 

5. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

프로세스들이 쉽게 상이한 그룹으로 분류될 수 있는 상황을 위해 고안된 스케줄링 알고리즘이다.

예를들어 foreground process와 backgroundProcess의 경우 응답 시간에 대한 요구사항이 다르기 때문에 스케줄링 요구또한 다를것이다.

foreground process들에겐 background process보다 높은 우선순위를 부여해줄 수 있다.

 

다단계 큐 스케줄링은 ReadyQueue를 다수의 별도의 큐로 분류한다.

일반적으로 프로세스들은 메모리 크기, 프로세스의 우선순위 혹은 프로세스의 유형과 같은 특성에 따라 하나의 큐에 영구적으로 할당된다.

각 큐는 자신의 스케줄링 알고리즘을 가질 수 있다. 예를들어, foreground queue는 RR 알고리즘에 의해 스케줄될 수 있고 background queue는 선입 선처리 알고리즘에 의해 스케줄 될 수 있다.

 

추가로 큐와 큐 사이에 스케줄링도 있어야 하며 일반적으로 고정 우선순위 선점형 스케줄링으로 구현된다. 예를들어 포그라운드 큐는 백그라운드 큐보다 절대적으로 높은 우선순위를 가질 수 있다.

 

고정 우선순위 선점형 스케줄링으로 구현되는 경우 일괄처리 프로세스는 시스템 프로세스,대화형 프로세스, 대화형 편집 프로세스큐가 모두 비어있어야지만 cpu를 할당받을 수 있다. 일괄처리 프로세스가 실행되던 도중에 대화형 프로세스큐에 프로세스가 들어오면 선점되어 cpu를 반환할 것이다.

 

다른 방법으로 큐들 사이에 시간을 나누어 사용할 수도 있다. 각 큐는 cpu 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다. 예를들어 포그라운드 프로세스큐와 백그라운드 프로세스큐가 있다면 cpu시간의 80%를 포그라운드 프로세스큐에 20%를 백그라운드 프로세스 큐에 할당할 수 있다.

 

6. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다.

대조적으로 다단계 피드백 큐 스케줄링에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

 

예를 들어, 이런 상황이 있을 수 있다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동시킨다. 이 방법에서는 입출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위 큐에 넣는다. 마찬가지로 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 이러한 Aging기법은 starvation을 방지할 수 있다.

위 그림의 상황에서 cpu burst가 8ms이하인 모든 프로세스에게 최고의 우선순위를 부여한다. 이러한 프로세스는 빨리 cpu를 할당받아서 cpu버스트를 끝내고 다음의 입출력 버스트로 간다. 8ms~24ms 프로세스들은 0~8ms 프로세스에 비해 낮은 우선순위를 부여받지만 역시 서비스를 빨리 받는다. 24ms초과의 프로세스는 결국 2단계 큐로 들어서게 되며 0~1단계 큐가 비어야 스케줄링을 받을 수 있다.