[운영체제] 프로세스 스케줄링(Process Scheduling)

Scheduling queues

스케줄링 큐는 운영 체제의 프로세스 스케줄링 시스템에서 사용되는 여러 큐를 말한다.
이 큐들은 프로세스의 상태에 따라 다양한 작업을 관리하고, 시스템 자원에 대한 접근을 조정하는 데 사용되는데 대표적인 스케줄링 큐는 다음과 같다.

1. 작업 큐(Job Queue)
   시스템에 있는 모든 프로세스를 포함하는 큐로 시스템에 진입한 모든 프로세스가 포함되며, 이들은 메모리에 로드되기를 기다린다.
   그리고 작업 큐에서 process가 생성되면 Ready로 이동하는데 Ready에서는 동시에 degree of multiprogram만큼만 잡고 있는다.
   
   
2. 준비 큐(Ready Queue)
   CPU에서 실행될 준비가 완료된 프로세스들이 대기하는 큐로 프로세스들은 CPU 할당을 기다리며, 단기 스케줄러에 의해 CPU에 할당 된다.
   
   
3. 대기 큐(Wait Queue)
   I/O과 같은 특정 이벤트를 기다리는 프로세스들이 있는 큐로 대기 상태의 프로세스는 필요한 이벤트가 발생할 때까지 이 큐에 머무른다.
   
   
4. 중단 큐(Suspend Queue)
   메모리에서 일시적으로 제거되었거나, 다른 이유로 실행 중지된 프로세스들이 대기하는 큐로 Suspend Ready와 Suspend Wait 큐가 포함된다.
   여기서 Suspend Ready 큐는 메모리가 부족하거나 다른 이유로 Ready 큐에서 잠시 제거된 프로세스들이 대기하는 큐이고,  Suspend Wait 큐는 대기 상태의 프로세스 중 메모리에서 일시적으로 제거된 프로세스들이 대기하는 큐이다.

CPU의 다양한 시간

도착 시간 (Arrival Time, AT)

프로세스가 준비 큐에 도착한 시간을 의미하는 것으로, 스케줄링 알고리즘에서 이 시간은 프로세스가 시스템에 진입한 순간으로 간주된다.

 

버스트 시간 (Burst Time, BT)

프로세스가 CPU를 차지하여 실행을 완료하는 데 필요한 실제 시간을 의미한다.

 

완료 시간 (Completion Time, CT)

프로세스가 실행을 완료하고 준비 큐를 떠나는 시간으로 프로세스가 시작된 후 완료될 때까지 걸린 전체 시간을 뜻한다.

 

전환 시간 (Turnaround Time, TAT)

프로세스가 도착해서 완료될 때까지 걸린 전체 시간으로, 버스트 시간과 대기 시간을 포함한다.
시간 계산은 CT - AT로 하는데 BT가 한번이 아닐 경우가 있고, 실행되면서 기다리는 시간(WT)도 발생할 수 있어 TAT와 BT는 다르다.

 

대기 시간 (Waiting Time, WT)

프로세스가 준비 큐에서 대기하는 데 소요된 총 시간으로,. 이는 프로세스가 CPU를 할당받기 위해 기다린 시간을 의미한다.

시간 계산은 TAT - BT로 한다.

 

응답 시간 (Response Time, RT)

프로세스가 준비 큐에 도착한 후 처음으로 CPU를 할당받기까지 걸린 시간으로, 시분할 시스템에서 사용자가 시스템의 반응을 느끼는 데 중요한 지표이다.

CPU Scheduling Algorithm

CPU 스케줄링 알고리즘은 프로세스를 어떻게 CPU에 할당할지 결정하는 데 사용된다.

이 알고리즘은 크게 선점형(Preemptive)과 비선점형(Non-Preemptive)으로 나눌 수 있다. 

• 선점형 스케줄링 (Preemptive Scheduling)
  선점형 스케줄링에서는 프로세스가 CPU를 할당받은 후에도, 우선순위가 더 높은 프로세스가 도착하거나 특정 조건이 만족될 경우, 현재 실행 중인 프로세스를 중단하고 새로운 프로세스에 CPU를 할당할 수 있다.
  타임 쉐어링(Time Sharing) 시스템에서 자주 사용되며, 이는 프로세스에 고정된 시간 할당량을 주고, 할당 시간이 끝나면 다음 프로세스로 전환한다.
  선점형 스케줄링의 예시로는 Round-Robin, Shortest Remaining Time First등이 있다.
  
  
• 비선점형 스케줄링 (Non-Preemptive Scheduling)
  비선점형 스케줄링에서는 한번 CPU를 할당받은 프로세스가 작업을 완료하거나 대기 상태로 전환될 때까지 CPU를 계속 사용하는 것이다.
  대표적인 비선점형 스케줄링의 예시는 First Come First Serve(FCFS), Shortest Job First(SJF) 등이 있다.

간트 차트(Gantt Chart)

프로세스의 도착 시간과 버스트 시간에 따른 CPU 할당 순서를 시각적으로 표현한 차트

 

First Come First Serve (FCFS)
FCFS는 가장 간단한 비선점형 스케줄링 알고리즘으로, 먼저 도착한 프로세스를 먼저 처리한다.
이 방식은 대기 큐를 관리하는 데 Queue 자료 구조를 사용하며, 시간 복잡도는 O(N)이다.

각각의 프로세스의 도착 시간과 종료 시간

FCFS의 간트 차트

 

P1은 시간 0부터 3단위 시간 동안 실행된다.

P2는 시간 2에 도착하지만 P1이 실행중 이여서 시간 3부터 6단위 시간 동안 실행된다.

P3는 시간 4에 도착하지만 P2가 완료된 후인 시간 9부터 시작하여 4단위 시간 동안 실행된다.

 

컨보이 효과(Convoy Effect)

주로 컴퓨터 시스템의 CPU 스케줄링에서 발생하는 현상으로 FCFS와 같은 비선점형 스케줄링 알고리즘에서 자주 나타난다.
컨보이 효과의 주된 특징과 영향은 다음과 같다.

1. 긴 버스트 시간의 프로세스
   컨보이 효과는 하나의 긴 버스트 시간을 가진 프로세스가 CPU를 점유할 때 발생하기 때문에 이 프로세스는 CPU를 오랜 시간 동안 차지하게 되며, 다른 프로세스들은 이를 기다려야 한다.
   
   
2. 대기 시간의 증가
   긴 프로세스가 CPU를 점유하고 있는 동안, 나머지 프로세스들은 Ready 큐에서 대기해야 하기 때문에 시스템의 평균 대기 시간이 증가하게 된다.
   
   
3. 자원 활용도 감소
   긴 프로세스가 CPU를 독점하는 동안 I/O와 같은 다른 자원은 충분히 활용되지 않아 전체 시스템의 자원 활용도를 낮춰 효율성 감소로 이어진다.

Shortest Job First (SJF)

각 프로세스의 버스트 시간을 기준으로 작은 작업을 먼저 스케줄링하는 알고리즘이다.

Min Heap 데이터 구조를 사용하여 N개의 자료에서 가장 작은 값을 확인하기 위해서 $\log N$만큼의 시간이 걸림으로 시간 복잡도는 $O(N \log N )$이다.

SJF의 간트 차트

P1은 시간 0부터 3단위 시간 동안 실행된다.

P3는 P1이 완료된 후인 시간 3부터 4단위 시간 동안 실행되고, P2는 P3가 완료된 후인 시간 7부터 6단위 시간 동안 실행된다.

 

SJF의 장점은 throughput(단위시간당 완료된 프로세스 수)이 크고, 가장 적은 평균waiting time을 가진다는 것이다..

단점은 Starvation이 존재한다는 것으로 BT가 긴 프로세스의 경우 우선순위에 계속 밀려서 자원을 할당 받지 못하는 상태가 생겨 무한히 대기할 수도 있다.

 

Prediction Technique

예측 기법은 CPU 스케줄링에서 프로세스의 버스트 시간을 예측하는 데 사용되는 방법을 말하는데 여기에는 크게 정적(Static)과 동적(Dynamic) 방식으로 나뉜다.

1. 정적 예측 기법 (Static Prediction Technique)
   이 방법에서는 BT를 예측하는 순간부터 실행 시간 내내 해당 예측값이 고정되고 바뀌지 않는다.
   • 프로세스 크기로 예측: 이전에 완료된 프로세스와 새로운 프로세스의 크기가 유사한 경우, 유사한 버스트 시간을 할당하여 예측한다.
     
     
   • 프로세스 유형으로 예측: 시스템 프로세스와 사용자 프로세스로 나눠, 시스템 프로세스는 일반적으로 사용자 프로세스보다 높은 우선순위와 더 짧은 버스트 시간을 가진다는 점을 이용해서 예측한다.
     사용자 프로세스는 상호작용형, 포그라운드, 백그라운드로 나누어지며, 이 순서대로 우선순위를 가진다.
2. 동적 예측 기법 (Dynamic Prediction Technique)
   동적 예측 기법에서는 BT가 지속적으로 변경되거나 특정 매개변수에 따라 달라진다.
   • 단순 평균 (Simple Averaging): 실제 프로세스 실행 시간은 완료될 때까지 알 수 없으므로, 이전 프로세스의 버스트 시간의 평균을 사용하여 새로운 프로세스의 버스트 시간을 예측한다.
     
     
   • 지수 평균 (Exponential Averaging): 새로운 예측값은 $t'_{n+1} = \alpha t_n + (1 - \alpha)  t'_n$ 공식에 따라 결정된다.
     여기서 $\alpha$는 평활 인자(smoothing factor)로, 0과 1 사이의 값을 갖는다.

 

Shortest Remaining Time First (SRTF)

각 프로세스의 남은 BT을 기준으로 작업을 스케줄링한다.

 

Min Heap 데이터 구조를 사용하여 N개의 자료에서 가장 작은 값을 확인하기 위해서 $\log N$만큼의 시간이 걸림으로 시간 복잡도는 $O(N \log N )$이다.

 

그리고 Preemptive(선점형) 스케줄링 알고리즘 이기 때문에 새로운 프로세스가 도착하거나, 기존 프로세스의 버스트 시간이 변경되면, 스케줄러는 남은 버스트 시간이 가장 짧은 프로세스를 다시 선택하여 CPU를 할당한다.

 

예를들어 시간 1에서 10단위 시간의 버스트 시간을 가진 프로세스가 있다면 1에 도착한 프로세스가 CPU를 할당받아 실행을 시작한다. 이때 시간 2에서 5단위 시간의 버스트 시간을 가진 새로운 프로세스가 도착하면 이 프로세스의 버스트 시간은 5단위 시간으로, 현재 실행 중인 프로세스의 남은 버스트 시간(9단위 시간)보다 짧아 새로 도착한 프로세스가 실행이 된다.

SRTF의 간트 차트

 

SRTF는 컨보이 효과를 방지하는 방법 중 하나로 긴 버스트 시간을 가진 프로세스로 인해 다른 프로세스들이 지나치게 오래 대기하는 상황을 줄일 수 있다.

 

다만 실제 시스템에서는 프로세스의 정확한 버스트 시간을 미리 알 수 없기 때문에, SRTF를 완벽하게 구현하는 것은 실질적으로 어렵다.

 

그러나 동적 예측 기법을 사용하여 버스트 시간을 추정하고, 이를 기반으로 SRTF와 유사한 스케줄링을 적용할 수 있다.

 

SRTF는 평균 대기 시간을 최소화하는 데 효과적이지만, 빈번한 Context Switching으로 인한 오버헤드가 발생할 수 있으며, Starvation이 발생할 가능성이 있다.

 

Round robin scheduling algorithm

각 프로세스에 고정된 시간 할당량(Time quantum)을 부여하여 해당 할당량 만큼씩 작업을 처리하는 알고리즘이다.

 

이때 만약 TQ가 무한대이면 FCFS와 동일한 알고리즘이된다.

 

그리고 만약 TQ가 매우 작으면  Context Switching이 매우 많아지게 되어 response time이 줄어들게 된다

 

Round Robin 스케줄링 알고리즘은 일반적으로 순환 큐(circular queue) 형태로 구현된다.

 

Context switching은 Reday와 Run의 상태로 바뀌는 과정을 의미한다.

라운드 로빈 알고리즘

 

모든 프로세스는 동일한 길이의 CPU 시간을 할당받기 때문에, Round Robin은 매우 공평한 스케줄링 방법으로 특정 프로세스에 대한 기아 현상을 방지한다.

 

Longest Job First (LJF)

프로세스의 버스트 시간을 기준으로 가장 긴 작업을 먼저 처리하는 CPU 스케줄링 방식이다.

이는 비선점형 스케줄링 알고리즘으로, 각 프로세스는 시작하면 완료될 때까지 CPU를 계속 사용한다.

LJF의 간트 차트

P1은 버스트 시간이 가장 길어서 가장 먼저 실행되며 7단위 시간 동안 실행된다.

남은 프로세스중에서 P2가 BT가 가장 길기 때문에 P2를 4단위 시간동안 실행한다.

마지막으로 P3가 실행되며 2단위 시간 동안 실행된다.

 

LJF 스케줄링은 평균 대기 시간을 최소화하는 데 효과적이지 않고, 특히 짧은 작업들이 긴 작업들에 의해 지연될 수 있어 기아 현상이 발생한다.

 

Longest Remaining Time First (LRTF)

각 프로세스의 남은 버스트 시간을 기준으로 시간이 가장 긴 프로세스에게 CPU를 할당한다.

Preemptive이기 때문에 매 순간 비교하여 가장 큰 작업을 먼저 처리한다.

LRTF의 간트 차트

 

P1은 시간 0에 도착하여 처음에 CPU를 할당받아 실행을 시작한다.

P2는 시간 2에 도착하고 이때 P1의 남은 버스트 시간이 5이기 때문에 P2의 4보다 길어 P1이 CPU를 선점한다.

P3는 시간 4에 도착하고 이때 P1은 3, P2는 4, P3는 2의 단위 시간이 남았기 때문에 P2를 할당 한다.

이제 매 순간마다 남은 시간이 가장 긴 프로세스를 할당한다.

 

LRTF 스케줄링은 남은 버스트 시간이 가장 긴 프로세스에 CPU를 우선적으로 할당하기 때문에, 평균 대기 시간을 최소화하는 데 효과적이다.

 

Highest Response Ratio Next (HRRN)

비선점형 알고리즘 중 하나로, 각 프로세스에 대한 응답 비율(Response Ratio)을 계산하여 스케줄링 한다.

Response Ratio = $\frac{WT + BT}{ BT }$ (WT: waiting time, BT: burst time)

HRRN의 간트 차트

 

P1은 처음에 CPU를 할당받아 실행을 시작한다.

Non-Preemptive이기 때문에 중간에 멈추지 멈추지 않고 진행이 되고 작업이 끝났을 때 P2의 응답 비율 $\frac{5 + 4}{4}$보다 P3의 응답 비율 $\frac{3 + 2}{2}$이 더 크기 때문에 P3가 실행이 된다.

 

HRRN 스케줄링은 평균 대기 시간을 줄이면서 프로세스의 우선순위를 공평하게 관리할 수 있는 효과적인 방법이다.

 

Priority Scheduling

프로세스에 우선순위를 할당하여 CPU 스케줄링을 결정하는 방식으로 우선순위가 높은 프로세스가 먼저 CPU를 할당받는다.

 

우선순위 스케줄링은 정적(Static)과 동적(Dynamic) 우선순위로 구분될 수 있으며 선점형(Preemptive)과 비선점형(Non-Preemptive)으로 나뉜다.

 

• 정적 우선순위(Static Priority)
  정적 우선순위는 Fixed Priority라고도 불리는데 프로세스가 시스템에 진입할 때 결정되고 그 후에는 변경되지 않는다.
  
  
• 동적 우선순위(Dynamic Priority)
  동적 우선순위는 Changes at Regular Interval of Time라는 특징을 갖는 것으로 프로세스의 실행 중 정기적으로 또는 특정 조건에 따라 우선순위가 변경될 수 있다.
  예를 들어, 프로세스가 오랫동안 대기하면 우선순위가 점점 증가하는 방식으로 우선순위가 조정될 수 있다.