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

 

[목차]

 

1. CPU Scheduling

 

2. Scheduling Criteria

 

3. Scheduling Algorithm 

 

4.  Multiple-Processor Scheduling

 

 

 

참고)

- https://parksb.github.io/article/9.html

- KOCW 공개강의 (2014-1. 이화여자대학교 - 반효경)

- Sogang Univ. Operating System Lecture Note (2018-2. Prof. Youngjae Kim)

  1. CPU Scheduling

 

스케줄러(Scheduler)는 언제, 어떤 프로세스를 선택해서 CPU에서 실행시키는지 선택하는 모듈(Module)이다. 멀티프로그래밍의 목적이 CPU 효율 극대화이므로 적절한 스케줄링이 필요하다. 

 

기본적으로 프로세스는 CPU만 사용하는 단계(CPU burst)와 I/O 작업만 하는 단계(I/O burst)의 반복으로 구성된 사이클의 형태로 수행된다. 

CPU burst time의 분포에 따라 프로그램의 특성을 나타낼 수 있는데, 짧고 많은 CPU burst가 존재하는 프로그램을 I/O-bound Job, 길고 적은 CPU burst가 존재하는 프로그램을 CPU-bound Job이라고 부른다.

I/O-bound Job은 CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 Job이다. 반면 CPU-bound Job은 계산 위주의 Job이다. 

그래프로 표현하면 아래와 같다. 

 

이러한 여러 Job이 섞여있기 때문에 CPU 스케줄링이 필요하다. 

CPU Scheduler는 메모리에서 Ready 상태의 프로세스 중 어떤 프로세스를 CPU에 할당해줄지 선택한다. CPU 스케줄링으로 인해 변경되는 프로세스의 상태는 다음과 같다. 

 

1) Running → Waiting(Blocked) : I/O 요청이나 자식의 종료를 위해 wait( ) 함수 호출한 경우

2) Running → Ready : 인터럽트가 발생한 경우

3) Waiting → Ready : I/O 작업이 끝난 경우

4) Terminate

 

여기서 1)과 4)는 Non-preemptive (비선점) 방식이고, 그 외의 모든 과정은 preemptive(선점) 방식이다. 

 

Preemptive 방식은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이고, Non-preemptive 방식은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다. 

Preemptive 스케줄링은 여러 프로세스가 데이터를 공유하고 있는 경우, 경쟁 상태(Race condition)의 문제점을 낳을 수 있다. 만약 한 프로세스가 데이터를 수정하고 있는 동안에 다른 프로세스의 수행을 위해 preempted 된다면, 다른 프로세스는 일관성이 없는 상태의 데이터를 읽게 된다. 

 

Dispatcher는 CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘겨주는 모듈이다. 즉, Context switching이나 커널 모드에서 유저 모드로 스위칭하는 작업등을 수행한다. 한 프로세스를 멈추고 다른 프로세스를 실행하는 데까지 걸리는 시간을 Dispatch latency라고 부른다. 

 

 

 

  2. Scheduling Criteria

 

CPU 스케줄링 알고리즘은 여러 종류가 있는데, 각 알고리즘의 성능을 평가하는 기준(Performance measure, 성능 척도)이 있다. 

 

1. 시스템 입장에서의 성능 척도

 

 - CPU 이용률 (CPU Utilization) : 전체 시간 중 CPU가 쉬지 않고 일한 시간

 - 처리량 (Throughput) : 단위 시간당 수행 완료한 프로세스의 수

 

2. 프로그램 입장에서의 성능 척도

 

 - 소요 시간 (Turnaround Time) : 프로세스가 Ready queue에서 대기한 시간부터 작업을 완료하는데 걸리는 시간

 - 대기 시간 (Waiting Time) : 프로세스가 Ready queue에서 대기한 시간

 - 응답 시간 (Response Time) : 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간

 

프로그램 입장에선 소요, 대기, 응답 시간이 모두 최소가 될수록 좋고, 시스템 입장에선 CPU 이용률과 처리량이 모두 최대가 될수록 좋다. 

 

 

  3. Scheduling Algorithm

 

이제 여러 스케줄링 알고리즘에 대해 알아보자. 처음엔, 다음과 같은 조건이 주어져 있다고 가정하자. 

 

1) 모든 작업은 동일한 시간만큼 수행된다. 

2) 모든 작업은 동일한 시간에 도착한다. 

3) 모든 작업은 오직 CPU만 사용한다. (no I/O)

4) 각각의 작업이 수행될 시간을 이미 알고 있다. 

 

 

1. FCFS Scheduling

 

FCFS 스케줄링은 First Come First Served의 약자로 CPU에 먼저 도착하는 순서대로 프로세스를 할당해주는 방식이다.

각 작업이 종료될 때까지 CPU를 빼앗지 않으므로 Non-Premptive 방식이며, FIFO 방식의 큐(Queue)와 동일하다.

구현하기 쉬워 간단한 시스템에 자주 사용된다.

 

Gantt Chart는 작업들이 CPU에 어떻게 스케줄링되는지를 보여주는 차트를 말한다. 

 

모든 작업들의 수행 시간과 도착 시간이 동일하므로 어떤 식으로 스케줄링을 하더라도 동일한 성능을 갖는다. 

하지만 만약 "1) 모든 작업은 동일한 시간만큼 수행된다" 라는 조건이 제거되면 어떨까?

P1 = 20, P2 = 5, P3 = 5만큼의 수행 시간이 걸린다고 하면, 평균 대기 시간은 15가 된다. 각 작업별로 수행 시간이 다를 때 FCFS 스케줄링 방식이 효율적일까?

 

위와 같이 수행 시간이 짧은 작업인 P2와 P3을 먼저 수행하게 되면 평균 대기 시간은 5가 된다. 즉, FCFS 방식은 효율적인 방식이 아니다. 

이처럼 하나의 긴 프로세스로 인해 나머지 프로세스가 오래 기다리게 되어 CPU 효율성이 낮아지는 문제점을 Convoy Effect라고 한다. Convoy Effect가 발생하면 CPU와 I/O 둘 중 하나는 아무것도 하지 않을 수도 있다.

예시처럼 짧은 프로세스를 먼저 수행하는 방식을 Shortest Job First 스케줄링이라고 한다. 

 

 

2. SJF (Shortest Job First) Scheduling

 

SJF(Shortest Job First) 스케줄링은 Convoy Effect를 해결하기 위한 방식이다. 프로세스의 수행 시간이 짧은 순서대로 CPU에 할당한다. SJF 스케줄링은 항상 주어진 프로세스에 대해 최소의 평균 대기 시간을 보장한다. 즉, 항상 최적(Optimal) 임이 보장된다. 

하지만, 수행시간이 긴 프로세스는 계속 뒤로 밀려나는 기아(Starvation) 현상이 발생할 수 있다.

또, 각 프로세스가 얼마나 CPU를 사용할지 모르는 경우 사용하기가 어렵다. 단지 추정만 가능한데, 과거의 CPU burst time을 이용하여 예측하는 지수 평활법(exponential averaging)을 사용한다. 최근 가중치를 더 많이 반영하는 방식이다.

 

$t_n$ = 실제 n번째 CPU burst의 길이

$w_{n+1}$ = n+1번째 CPU burst 길이의 추정 값

$\alpha$, $0 \leq \alpha \leq 1$

→ $ w_{n+1} = \alpha t_n + (1-\alpha)w_n$

 

 

SJF 방식은 Non-preemptive와 Preemptive 두 방식이 존재한다. 

 

1) Non-preemptive SJF

 

프로세스가 한번 CPU를 잡으면 이번 CPU burst 시간이 만료될 때까지 CPU를 뺏기지 않는다. 

하지만 만약 "2) 모든 작업은 동일한 시간에 도착한다"의 조건을 만족하지 않는다면 어떻게 될까?

 

프로세스들이 모두 다른 시간에 도착한다고 가정하자. 현재 도착한 프로세스 중 시간이 가장 짧은 프로세스에 CPU를 할당하고, 한번 실행을 시작하면 완료될 때까지 CPU를 빼앗기지 않는다면 위처럼 평균 대기 시간은 4가 된다. 

이 값이 과연 최적일까?

 

2) Preemptive SJF

 

결론부터 말하자면, 위의 결과는 최적이 아니다. 아래처럼 프로세스를 나누어서 실행해보자. 

이 경우는 평균 대기 시간이 3이며, 최적의 경우이다. 

따라서, 새로운 프로세스가 도착했을 때, 현재 남아있는 작업 중 가장 빨리 끝나는 작업부터 CPU를 할당해주는 Preemptive 방식을 이용하면 평균 대기 시간을 더 줄일 수 있다. 이 방식을 SRTF(Shortest Remaining Time First) 혹은 STCF(Shortest Time-to-Completion First)라고도 부른다. 

하지만 여전히 기아(Starvation) 현상을 막을 수 없다. 

 

 

3. Round Robin (RR) scheduling

 

때때로, 작업이 언제 끝나는지보다 언제 시작되는지가 더 중요할 수도 있다. 

Round Robin 스케줄링은 각 프로세스가 주로 10 ~ 100ms의 동일한 크기의 할당 시간(Time quantum)을 갖는다. 할당 시간이 끝나면 프로세스는 자동으로 선점(Preempted)당하고, Ready queue의 제일 뒤에 가서 다시 줄을 선다. 

n개의 프로세스가 Ready queue에 존재하고, 할당 시간이 q라면 어떤 프로세스도 (n-1)q 이상 기다리지 않으므로 기아 현상이 발생하지 않는다. 따라서 응답 시간이 빠르다는 장점이 있다. 

 

다만, 일반적으로 SJF보다 평균 소요 시간(Average Turnaround Time)은 길다. 

 

 

아래는 할당 시간에 따른 평균 소요 시간을 그래프로 나타낸 것이다. 

평균 소요 시간은 할당 시간이 커진다고 해서 반드시 증가하는 것은 아니다. 할당 시간 q가 클수록 FCFS의 방식과 유사하고, q가 작을수록 Context switch의 오버헤드가 커지기 때문에 적절한 할당 시간을 배정하는 것이 중요하다. 

 

4. Priority Scheduling

 

우선순위 스케줄링은 특정 기준으로 프로세스에게 우선순위를 부여해 우선순위가 제일 높은 프로세스에게 CPU를 할당하는 방식이다. 일반적으로 숫자가 작으면 우선순위가 높은 것을 의미하며, SJF도 일종의 우선순위 스케줄링이다.

 

다만 이 방식 또한 우선순위가 낮은 프로세스가 계속해서 수행되지 않는 기아 현상이 발생할 수 있는데, 이를 에이징(Aging) 기법을 통해 해결한다. 에이징 기법은 시간이 지날수록 오래 대기한 프로세스의 우선순위를 높이는 방식이다. 

다른 스케줄링 알고리즘과 결합해서 사용할 수 있어 선점, 비선점 모두 가능하다. 

 

 

5. MLFQ (Multi-Level Feedback Queue)

 

MLFQ에 앞서, Multi-Level Queue에 대해서 먼저 알아보자. 

Multi-Level Queue는 Ready Queue를 여러 개로 분할한 것이다. 각 큐는 독립적인 스케줄링 알고리즘을 가진다. 

 

Foreground task 같은 Interactive 프로그램은 응답 시간이 중요하기 때문에 Round Robin 스케줄링으로, Background Task 같은 Batch 프로그램은 소요시간이 중요하기 때문에 FCFS 스케줄링을 사용한다. 

 

 

큐 사이에서도 스케줄링이 필요한데, Foreground 작업을 먼저 다 수행한 후, Background 작업을 수행하는 고정된 우선순위 스케줄링을 이용할 수 있다. 따라서 이 방식은 기아 현상이 발생할 수 있다.

또는, 각 큐에 CPU Time을 적절한 비율로 할당하는 Time slice 방식을 사용할 수도 있다. 예를 들어 80%는 Foreground에, 20%는 Background에 사용한다. 

 

Multi-Level Feedback Queue는 여기에 프로세스가 큐들 사이에서 이동할 수 있는 성질이 추가된 것이다. 우선순위를 부여해서 에이징(aging) 기법을 통해 구현될 수 있다. 우선순위는 프로세스들의 과거 CPU burst time을 이용하여 미래의 행동을 예상하여 부여한다. 이를 이용하여 기아 현상을 해결할 수 있다. 

MLFQ 스케줄러를 정의하는 변수(Parameter)들은 다음과 같다. 

 

- Queue의 개수

- 각 Queue를 위한 스케줄링 알고리즘

- 프로세스를 상위/하위 Queue로 보내는 기준

- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 Queue를 결정하는 기준

 

할당 시간이 8ms, 16ms인 RR 방식의 두 Queue와 FCFS 방식의 한 Queue가 있는 예를 들어보자. 

 

다음과 같이 스케줄링된다.

새로운 작업이 Q0에 들어간다. CPU를 할당받아 8ms만큼 작업을 수행하고, 작업을 다 못 끝내면 Q1로 내려간다. 그리고 Q1에서 기다리다가 CPU를 할당받아 16ms만큼 작업을 수행한다. 또 작업을 다 못 끝내면 FCFS으로 내려가서 오직 Q0과 Q1이 비어있을 때 작업을 이어나간다.  

 

 

  4. Multiple-Processor Scheduling

 

CPU가 여러 개 있을 때 어느 CPU에 할당할지를 결정하는 것이 CPU 스케줄링이다. CPU가 많을수록 더 복잡하다.

단순하게 모든 프로세서가 동일한 프로세서라고 가정하자. 

 

- 비대칭 방식(Asymmetric multiprocessing) : 오직 한 프로세서가 시스템 데이터에 대한 접근과 공유를 책임지고, 나머지 프로세서는 해당 CPU를 따르는 방식이다.

- 대칭 방식(Symmetric multiprocessing, SMP) : 각 프로세서가 각자 알아서 스케줄링하는 방식이다. 

 

SMP 방식을 위해 Load Balancing(부하 균등) 이라는 기법이 사용된다. Load Balancing은 SMP 시스템에서 일부 프로세서에 작업이 몰리지 않도록 부하를 적절히 공유하는 기법이다. 주로 각 프로세서가 자신만의 큐를 가지고 있는 시스템에서만 필요하다. 이 또한 분배하는 주체에 따라 두 방식으로 나뉜다. 

 

- Push migration : 주기적으로 각 프로세서를 체크하여 바쁜 프로세서인 경우 다른 프로세서로 작업을 분배한다. 

- Pull migration : 쉬고 있는 프로세서가 바쁜 프로세서에서 기다리고 있는 작업을 가져온다. 

 

두 방식이 동시에 구현될 수도 있다. 예를 들어, 특정 시간 단위마다 프로세서를 체크하면서 작업이 분배되다가, 어떤 프로세서의 큐가 비게 되면 해당 큐가 작업을 가져오는 방식이다.

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^