Chapter5 프로세스 스케줄링(Multilevel Queue Scheduling Algorithm을 위한 여러가지 알고리즘)

1. 프로세스 스케줄링

1) Multilevel Queue Scheduling Algorithm

● 개요

하나의 프로세스는 전형적으로 I/O 요청이 완료되기를 기다려야 할 때까지 실행된다.

ready Queue는 프로세스 중에서 CPU 자원을 할당받고 언제든 실행이 가능한 상태들인 프로세스들이 대기하는 공간이다. CPU 스케줄링을 통하여 ready Queue에 있는 프로세스 중 하나를 CPU 자원을 할당 시키고 프로세스를 CPU 코어에서 실행하게 된다. (이를 run 상태라고 한다.)

만약 Run 상태인 프로세스가 I/O 작업이 발생하면 wating Queue에 프로세스의 PCB 정보를 넣음으로써 wating 상태로 만든다. 그리고 I/O작업이 종료되면 wating->ready 상태로 만든다.

 

스케줄링이라는 것을 통해 ready Queue에 있는 프로세스들 중 어떤 것을 선택해야 전체적으로 프로세스의 대기시간 즉 ready Queue에 있는 기간이 짧아지도록 할 수 있을까?

 

● 다른 CPU 스케줄러 알고리즘 정리

CPU 스케줄러 알고리즘에 대해 정리한다.

 

① First Come First Served(FCFS) 알고리즘 - 비선점

CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는 방식으로 FIFO Queue로 쉽게 관리 가능하다. 이 스케줄링 기법은 CPU가 한 프로세스에게 할당되면 해당 프로세스가 I/O 작업이 발생하거나 종료될 때까지 CPU를 점유한다(Non-Preemptive) 그로 인해 한 프로스세가 지나치게 오랫동안 CPU를 점유하는 것을 허용하기 때문에 큰 손해가 발생한다.

프로세스가 준비 큐에 진입하게 되면 이 프로세스의 PCB을 큐의 끝에 연결한다.

FCFS는 비선점형이다. -> CPU가 한 프로세스에 할당되면 종료 또는 I/O 처리로 CPU를 방출할 때까지 CPU를 점유하는 것을 말한다.

 

※ 호위 효과(convoy effect)

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과라고한다.

 

※ interactive, batch

프로세스에는 크게 사용자와 대화형으로 동작하는 foreground(interactive) 프로세스와 사용자 눈에는 보이지 않지만 커널이 실행하고 있는 background(batch) 두 종류의 프로세스로 분류할 수 있다.

이 둘간의 우선순위는 interactive가 더 높다.

 

foreground(interactive) 프로세스는 Round-Robin(RR) 스케줄링 기법이 사용된다.

background(batch)는 First Come First Served(FCFS) 스케줄링 기법이 사용된다.

 

 

② Shortest Job First 알고리즘(가장 성능이 좋음)

각 프로세스의 next CPU burst 길이를 고려한 알고리즘으로

가장 작은 next CPU burst를 가진 프로세스에 CPU를 할당한다.

두 프로세스가 동일한 길이의 next CPU burst를 가지면, 선입 선처리 스케줄링을 적용한다.

 

Shortest Job First 알고리즘은 다음 CPU burst의 길이를 알 수는 없다. -> 예측을 해야한다. CPU burst가 이전의 burst와 길이가 비슷하다고 기대할 수 있다. 따라서 다음 CPU burst 길이의 근삿값을 계산해 가장 짧은 예상 CPU burst를 가진 프로세스를 선택한다.

 

위 수식은 현재 n인 상태에서 CPU burst time이 t_n 일 때 n인 상태에서 다음 CPU burst를 예측한다. 이 예측 값을 A_n

이라고 한다. 이 두 값에 대해 가중치 알파 값을 각각 곱하여 n+1일 때의 CPU burst를 예측한다.

 

예를 들어

Arrival Time 0

처음 0 일 때 P1이 실행된다.

 

Arrival Time 1

P1(7) -> 괄호의 숫자는 Burst Time이다.

P2(4)

AT1(Arrival Time 1) 일 때는 P1이 잘 실행하다가 P1보다 BT(Burst Time)이 P2가 더 짧으므로 P1을 keep out 하고 P2를 실행한다.

 

Arrival Time2

AT2 일 때는 P1(7), P2(3) 인 상태에서 P2가 실행 중이었는데 새로운 P3(9) 작업이 도작한다. 하지만 기존에 실행 중이던 P2가 P3보다 더 shortest하기 때문에 P2의 실행을 이어간다.

 

이러한 방식의 문제점은 starvation(기아 상태) 현상을 야기한다. 이것은 작업이 많이 걸리는 프로세스는 작업이 계속해서 밀린다는 것이다. 따라서 이것에 대한 예방책으로 Round-Robin 방식이 등장한다.

 

 

③ Round Robin 알고리즘(선점형)

시간 할당량(time quantum), 또는 타임슬라이스(time slice)라고 하는 프로세스의 작은 시간 단위를 정의한다. CPU 스케줄러는 준비 큐를 돌면서 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다. Queue는 원형큐로 동작한다.

첫 번째 프로세스인 P1이 한 번의 time slice만큼 실행 후 interrupt를 발생시키도록 timer를 지정한다. 타이머가 종료하면 dispatch 한다.

만약 CPU burst가 time slice보다 작은 경우 CPU를 자발적으로 방출하고 스케줄러에 의해 다음 준비 큐의 프로세스를 진행시킨다.

만약 현지 실행 중인 프로세스의 CPU burst가 time slice보다 긴 경우 time slice만큼 실행 한 후 interrupt를 발생시켜 Context Switching이 발생한다.

 

이 알고리즘에서는 유일하게 실행 가능한 process가 아니라면 2번 이상의 time slice를 할당 받는 프로세스는 없다.

이 알고리즘은 한 한 번의 time slice을 초과하면 프로세스는 선점되고 준비큐로 돌아간다. 따라서 선점형이라 할 수 있다.

 

RR 알고리즘은 time slice의 크기에 매우 민감하게 반응한다.

 

 

 

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

SJF(Shortest Job First) 알고리즘은 우선순위 스케줄링의 특별한 형태이며, 우선 순위가 같은 프로세스들은 FCFS(First Come First Served) 순서로 스케줄링한다.

SJF에서는 예측된 CPU burst가 클수록 우선순위가 낮다.

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 예를 들어 내부적으로는 시간 제한, 메모리 요구, 평균 I/O burst 시간 등에 대한 비율로 우선순위를 계산할 수 있다.

 

우선순위 스케줄링은 선점형 또는 비선점형 일 수 있는데

 

※ 선점형인 경우

- 새롭게 도작한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교하여 만약 새로 들어온 프로세스가 더 우선순위가 높다면 현재 실행 중인 프로세스를 keep out 하고 새로운 프로세스가 CPU를 선점한다.

 

- 특정 프로세스가 CPU 를 독점하는것이 불가능(운영체제가 강제로 프로세스의 CPU 점유를 제어)하면 선점형

 

※ 비선점형인 경우

- 비선점형인 경우 새로운 프로세스가 더 우선순위가 높다면 준비 큐의 머리 부분에 새로운 프로세스를 넣는다.

 

- 특정 프로세스가 CPU 를 독점하는것이 가능 (프로세스가 스스로 CPU 점유를 포기해야만 다른 프로세스가 실행)하면 비선점형

 

우선순위 스케줄링의 주요 문제는 starvation이다. 이를 해결하기 위한 방법으로 아래 두 가지가 있다.

 

방법1) Aging

Aging이란 오랫동안 큐에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜준다.

 

방법2) Round Robin과 우선순위 스케줄링을 결합하는 방식 사용

시스템의 우선순위가 가장 높은 프로세스를 실행한다. 만약 우선순위가 같은 프로세스라면 Round Robin 스케줄링을 사용한다.

이 방식은 Multilevel Queue Scheduling Algorithm에서 하나의 Queue 내부에서 실제 수행되는 스케줄링 기법이다.

 

 

● Shortest Job First 알고리즘(비선점형)

ready Queue는 Multilevel Queue이지만 일단은 하나의 Queue로 되어있다고 상상하고 Shortest Job First 알고리즘이 무엇인지 정리할 것이다. 그리고 Multievel Queue가 왜 등장하였는지 정리한다.

 

우선, 원초적인 방식에서는 ready Queue는 우리가 아는 일반적은 First in First out 방식의 Queue 방식으로 ready Queue를 동작 시켰더니 즉 프로세스가 들어오는 순서대로 Run 상태로 만들었더니 ready Queue의 프로세스들의 대기 시간이 너무 길어지는 문제점이 발생한다. 즉 ready Queue의 프로세스들에게 CPU 자원을 골고루 할당하여 프로세스들을 실행시켜줘야하는데 들어온 순서대로 프로세스들을 Run 상태로 만들어 버리니 CPU의 성능이 떨어지는 문제가 발생한다.

 

이로 인해서 Shortest Job First 알고리즘이 등장하게 된다.

tesk의 길이가 짧은 프로세스를 먼저 실행하도록 만들었더니 프로세스들의 대기 시간이 줄어 CPU 성능이 좋아지게 된다.

Shortest Job First 알고리즘은 ready Queue에서 tesk 길이가 짧은 프로세스 하나를 선택하여 Run 하는 방식이므로 이는 Queue라고 할 수가 없다. (Queue는 FIFO이기 때문)

하지만 기존의 ready Queue명칭대로 그냥 쓰기로 한다.

따라서 ready Queue의 Queue는 우리가 생각하는 자료구조의 Queue의 동작 방식으로 동작한다고 생각하면 안된다.

 

하나의 ready Queue라고 가정하였기 때문에 이 Queue의 프로세스 들 중 Run 상태로 만들 프로세스 즉 tesk 길이가 짧은 프로세스를 선택하는 방법은 O(n) 시간이 걸릴 것이다. 그리고 tesk 길이가 짧은 순서로 Sorting(정렬) 할 때는 O(n log n)

시간이 걸릴 것이다. 따라서 이 시간 복잡도는 비효율적이다. 그래서 Sorting 할 필요 없이 가장 짧은 Shortest Job을 선택할 수 있도록 하는 또 다른 방법이 없을까? 해서 나온 것이 Multilevel Queue이다.

---