5.3 스케줄링 알고리듬(Scheduling Algorithms)
프로세스가 하나라고 가정한 상태에서 알고리즘을 설명한다.
5.3.1 선입 선처리 스케줄링(First Come, First Served Scheduling, FCFS)
CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다. FIFO Queue로 쉽게 관리할 수 있다.
비선점(Nonpreemptive) 알고리듬 이다.
프로세스가 Ready Queue에 집입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다. CPU가 가용 준비상태가 되면, Ready Queue 의 앞부분에 있는 프로세스에 할당 된다.
평균 대기시간은 종종 대단히 길 수 있다. 위와 같은 상황에서 평균 대기 시간의 최대값은 (0+24+27)/3 = 17ms 이다. 평균 대기시간의 최소값은 (0+3+6)/3 = 3ms 이다.
따라서 FCFS Policy에서의 평균대기 시간은 일반적으로 최소가 아니며, 프로세스의 CPU 버스트 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있다.
추가적으로 하나의 CPU 중심(CPU Bound) 프로세스와 많은 수의 I/O 중심(I/O Bound) 프로세스를 갖는다고 가정한다. 최악의 상황에서 CPU 중심 프로세스가 CPU를 할당받아 점유하고 있다. 그동안 다른 프로세스들은 I/O를 끝내고 Ready Queue로 이동하여 CPU 할당을 기다릴 것이다. CPU 중심 프로세스가 CPU Burst를 종료하고 CPU 할당을 해제하고 I/O 중심 프로세스에게 할당될 것이다. I/O 중심 프로세스들은 CPU Burst 시간이 작아 빠르게 종료되고 I/O Queue로 이동될 것이다. 따라서 CPU 중심 프로세스가 끝날 때 까지 모든 I/O 프로세스들은 다시 Ready Queue에서 대기하게 된다. 이러한 상황을 호위 효과(Convoy Effect)라고 한다.
5.3.2 최단 작업 우선 스케줄링(Shortest Job First Scheduling)
각 프로세스에 다음 CPU 버스트 길이를 연관시킨다. CPU가 이용 가능해지면, 가장 작은 CPU 버스트 시간을 가진 프로세스에게 할당된다. 두 프로세스가 동일한 길이의 CPU 버스트 시간을 가지면, 선입 선처리 스케줄링을 이용한다. 특히 이 스케줄링은 프로세스의 전체 길이가 아닌 다음 CPU 버스트 길이에 의해 스케줄링된다는 것을 이해 해야 한다.
위와 같은 상황에서 평균 대기시간의 최소값은 (0+3+9+16)/4 = 7ms이다. SJF 알고리듬은 주어진 프로세스 집합에 대해 항상 최소 평균 대기시간을 가진다는 점에서 최적임을 증명할 수 있다. 짧은 프로세스를 긴 프로세스의 앞으로 이동함으로써, 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가하는 것보다 더 많이 줄일 수 있다.
하지만 시스템은 다음 CPU 버스트 시간의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다. 아래는 SJF와 근사한 방법을 사용 하는것이다. 다음 CPU 버스트 시간을 과거 내역을 통해 예측하여 사용한다.
τ = 다음 CPU 버스트에 대한 예측값
t = n번 째 CPU 버스트 길이
α = 최근의 값과 이전 값의 상대 가중치
SJF 알고리듬은 선점형이거나 비선점형일 수 있다. 앞의 프로스세가 실행되는 동안 새로운 프로스세가 준비 큐에 도착하면 선택이 발생한다. 새로운 프로세스가 현재 실행되고있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트 시간을 가질 수도 있다. 선점형 SJF 알고리듬은 현재 실행하는 프로세스를 선점할 것이고, 비선점형 알고리듬은 현재 실행하고 있는 프로세스가 CPU 버스트를 끝내도록 기다린다.
위는 선점형 SJF 알고리듬을 사용했을때의 상황을 나타낸다. P1이 0시간에 도착했음에도 불구하고 더 짧은 CPU 버스트를 가진 P2가 1초가 지난후 선점된다. 따라서 평균 대기 시간은 [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 6.5 ms 이다. 만약 비선점형 SJF라면, 7.75 ms이다.
5.3.3 라운드 로빈 스케줄링(Round Robin Scheduling)
라운드 로빈(RR) 알고리듬은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 타임 슬라이스(Time slice)라고 하는 작은 단위의 시간을 정의한다. Ready Queue는 원형 큐로 동작하며 CPU 스케줄러는 Ready Queue를 돌면서 한 번에 한 프로세스에 한 번의 타임 슬라이스 동안 CPU를 할당한다. 새로운 프로세스가 Ready Queue에 들어갈때는 Tail 부분에 들어가게 된다. 현대의 운영체제 스케줄러로 사용된다.
P1~P3는 순서대로 Ready Queue에 들어갔다고 정의한다. 타임 슬라이스는 4ms로 정의한다. 대신 P2 처럼 타임 슬라이스를 다 채우지 않고 종료된다면 다음 프로세스에게 선점된다. P1은 6ms(10 - 4)를 기다리고 P2는 4ms. P3는 7ms를 기다려 평균 대기시간은 17/3 = 5.66ms가 된다.
알고리듬을 생각해보자면
1. 항상 Ready Queue(2차 배열이라 가정)에서 첫 번째 프로세스를 선택한다.
2. 타임 슬라이스 만큼 실행
3. 프로세스가 종료되지 않은 경우 Ready Queue의 Tail 부분에 추가 한다.
여기서 새로운 프로세스가 추가될때마다 Ready Queue 의 Tail부분에 추가되는 방식이다.
RR 알고리듬에서 타임 슬라이스가 매우 크면 FCFS 알고리듬과 같아지며, 매우 작아진다면 매우 많은 문맥 교환(Context Switch)를 야기한다. 즉, 오버헤드가 증가해 프로세스의 실행이 느려진다. 따라서 타임 슬라이스가 문맥 교환 시간과 비교해 더 클것을 원한다. 문맥 교환시간이 타임 슬라이스의 10%에 근접한다면, CPU는 항상 10%를 문맥 교환에 사용한다. 현대 운영체제들은 문맥 교환 시간이 10us 미만이라 타임 슬라이스를 10~100ms를 할당한다.
5.3.4 우선순위 스케줄링(Priority Scheduling)
각 프로세스와 연관되며 스케줄러는 우선 순위가 가장 높은 프로세스에 대해 먼저 CPU를 할당 해준다. 위의 SJF 알고리듬이 우선순위 스케줄링 중 한가지 방식이다.
우선순위의 수가 낮을수록 높은 우선순위를 가진다고 정의한다. P1~P5는 시간 0에 동시에 도착했다. 평균 대기시간은 8.2ms이다.
우선순위는 내부적 또는 외부적으로 정의될 수 있다.
내부적 정의 : 시스템 내부의 측정 가능한 양들을 사용하여 우선순위를 계산한다. E.g. 시간제한, 메모리요구, 열린 파일 수, 평균 I/O 대 CPU Burst 비율 등..
외부적 정의 : 운영체제 외부의 기준으로 설정한다. E.g. 프로세스의 중요성, 사용하는 요금제, 작업을 원하는 부서 등..
새로운 프로세스가 Ready Queue 에 도착하면 우선 순위가 확인된다. 만약 선점형 방식일때 새 프로세스의 우선순위고 높다면 선점된다. 비선점형 방식일때는 새 프로세스가 도착하여도 선점되지 않으며 대신 우선 순위가 높은 프로세스를 Ready Queue의 Head 에 넣는다.
이러한 우선순위 알고리듬에는 기아 상태(Starvation) 문제가 있다. 낮은 우선순위의 프로세스가 있을때 높은 우선순위의 프로세스가 계속 선점 된다면, 낮은 우선순위의 프로세스는 절대 스케줄될 수가 없다.
해결법으로 노화(Aging)이 있다. 이는 시스템에 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 상승 시킨다. 따라서 높은 우선순위를 가질 수 있게 되며 스케줄 가능한 상태가 된다.
5.2.5 다단계 큐 스케줄링(Multilevel Queue Scheduling)
우선순위 및 라운드 로빈 알고리듬은 단일 큐를 사용해 모든 프로세스를 관리한다. 하지만 우선순위 높은 프로세스를 선택하기위해 O(n)의 시간 복잡도를 가질 수 있다. 따라서 우선순위마다의 별도의 큐를 가지도록 하여 프로세스들을 스케줄 하게 한다.
예를들어 배치 프로세스보다 실시간 프로세스에게 더높은 큐를 할당하고, 백그라운드 프로세스보다 포그라운드 프로세스에게 더 높은 큐를 할당하는 방법이다. 또한, 각 큐에는 FCFS, RR등 자체 스케줄링 알고리듬이 사용 될 수있다. 추가로, 큐와 큐 사이에 스케줄링도 반드시 있어야 하며, 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다.
5.3.6 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
위의 다단계 큐 스케줄링에서는 프로세스들이 시스템 진입시에 영구적으로 하나의 큐에 할당된다. 하지만 이러한 방식은 스케줄링 오버헤드가 적으나 융퉁성이 부족하고 기아 문제가 발생할 수 있다. 따라서 큐 간에 프로세스를 이동할 수 있게 만든다면 좀더 효과적인 스케줄 방법일 것이다.
프로세스들을 CPU 버스트 성격에 따라서 구분한다. 한 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위 큐로 이동된다. 이 방법에서는 I/O중심의 프로세스와 Interactive 중심 프로세스들을 높은 우선순위의 큐에 넣는다. 마찬 가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
1. 프로세스 0가 Queue 0에 할당된다.
2. 만약 Queue 0의 프로세스가 8ms 이내에 완료되지 않으면 Queue 1의 Tail에 삽입된다.
3. 만약 Queue 1의 프로세스가 16ms 이내에 완료되지 않으면 Queue 2의 Tail에 삽입된다.
Ch5.4 ~ 5.8 은 이후에..
'책 > 운영체제' 카테고리의 다른 글
| 운영체제 Ch09_'Main Memory-2' (0) | 2021.01.11 |
|---|---|
| 운영체제 Ch09_'Main Memory-1' (0) | 2021.01.11 |
| 운영체제 Ch05_'CPU Scheduling-1' (0) | 2021.01.11 |
| 운영체제 Ch04_'Thread and Concurrency-2' (0) | 2021.01.10 |
| 운영체제 Ch04_'Thread and Concurrency-1' (0) | 2021.01.10 |