[Operating System] Process Scheduling

 

 

 

스케쥴링 방식은 스케쥴러가 실행되는 시간 간격에 따라 Long-Term / Medium-Term / Short-Term 세 가지로 구분된다. 

 

지금까지 계속 언급하던 Process Scheduling은 모두 Short-Term Scheduling을 의미하고,  I/O 장치를 대상으로 하는 스케쥴링은 I/O Scheduling을 의미한다.

 

 

 

 

Long-Term Scheduling은 생성은 됐지만 아직 메모리에 올라오지 않은 New 프로세스에 대해 수행된다. 

아직 가상 주소 공간에 있는 프로세스 중 메모리에 들어갈 프로세스를 선별하는 작업이다. 

 

Medium-Term Scheduling은 메모리에 올라왔다가 일시적으로 보조기억장치로 Swap-Out 되는 프로세스들에 대해 어떤 프로세스를 다시 메모리에 올릴지를 결정하는 작업으로, Ready / Block 상태인 프로세스 모두에 대해 수행된다. 

 

Short-Term Scheduling은 Ready 상태에 있는 프로세스를 Running 상태로 변경하는 작업이다. 

 

 

 

 

Batch Job은 즉시 실행할 필요가 없는 프로그램으로, 대기 Queue에 들어가서 대기하게 된다. 

대기 Queue에서 Ready Queue로 누구를 옮길지 결정하는 작업이 Long-Term Scheduling이다. 

 

Ready Queue에서 누구에게 CPU를 할당할 지를 결정하는 작업은 Short-Term Scheduling이고, 일반적으로 들어온 순서대로 할당하거나 Time Slice를 기준으로 할당한다. 

 

CPU를 사용하던 프로세스가 입출력을 요청하면 해당 요청이 끝날 때 까지 실행할 수 없게 된다. 

I/O 장치에게 명령하고 해당 프로세스를 Blocked Queue로 옮긴 후 입출력 작업이 끝나면 다시 Ready Queue로 옮겨진다.

 

Blocked Queue에 있다가 메모리가 부족해지면 Blocked, Suspended Queue로 옮겨지는데, Mideum-Term Scheduling은 Blocked, Suspended Queue를 대상으로 Ready, Suspended Queue로 옮기는 작업이다. 

 

Interactive Job은 Batch Job과는 다르게 바로바로 실행되어야 하는 프로세스로, New 상태를 거치지 않고 바로 Ready Queue로 들어간다.

 

프로그램을 실행할 때 arg로 &를 주면 Batch Job으로 실행되고, CPU가 한가할 때 처리하게 된다. 

CPU가 "한가할 때" 처리하게 되니 Interactive Job으로 실행하는 것 보다 실제 프로그램의 실행 시간이 더 짧다. 

 

Long-Term, Mid-Term Scheduling은 상대적으로 자주 실행되는 스케쥴링이 아니기에 운영체제 성능에 큰 영향을 미치지 않는다.

자주 실행되는 Short-Term Scheduling이 가장 자주 실행되고 가장 중요하다고 할 수 있다. 

 

User Process의 Time Slice는 보통 100ms이고, Short-Term Scheduling은 저 Time Slice가 끝나기도 전에 실행되는 경우가 많다. 

Short-Term Scheduling에서 수행되는 작업을 살펴보자.

 

 

 

 

Enqueuer - 새로 Ready 상태가 된 프로세스를 Ready Queue에 집어넣는 역할을 수행한다.

Ready Queue는 우선순위에 따라 등급을 매기고 운영체제는 여러 Queue를 차등적으로 만들어서 사용한다. 

일단 우선순위가 결정되기에 스케쥴러의 작업이 여기서 끝날 수도 있고, 아래 세 가지 작업을 추가로 수행할 수도 있다. 

새로 들어온 프로세스의 우선순위가 현재 CPU가 할당된 프로세스의 우선순위보다 같거나 낮으면 Queue에 넣는 것으로 작업이 끝나지만, 새로 들어온 프로세스의 우선순위가 더 높다면 아래 세 가지 작업을 수행한다.

 

Context Saver - 새로 들어온 프로세스의 우선순위가 더 높기에 Context Switch를 수행한다. 

현재 실행되고 있는 프로세스의 Context를 PCB에 저장하고 CPU를 뺏는다.

 

Scheduling Algorithm - Ready Queue에서 다음으로 실행할 프로세스를 고른다.

 

Dispatcher - 선택된 프로세스에게 해당하는 Context가 있다면 복원하고 CPU를 배정한다. 

 

 

프로세스가 Terminated을 때, 프로세스가 Running 상태에서 Blocked 상태로 갔을 때, 프로세스가 Running 상태에서 Ready 상태로 갔을 때, 프로세스가 Ready 상태로 들어올 때 Scheduler가 실행된다.

 

마지막 두 상황은 특정 프로세스가 CPU를 뺏기는 Preemptive 스케쥴링이고, 처음 두 상황은 Non-Preemptive 스케쥴링이다.

 

 

 

---

 

 

 

 

사용자가 바라보는 성능이 좋은 알고리즘과 시스템이 바라보는 성능이 좋은 알고리즘은 서로 다르다. 

사용자 관점에서는 Response Time이 짧을수록 좋은 알고리즘이고, 시스템 관점에서는 CPU의 활용도를 높이는 알고리즘이 좋은 알고리즘이다.

 

아래는 우선순위를 결정할 때 사용하는 지표이다.

 

CPU Utilization - 전체 CPU 동작 시간과 사용자 프로그램의 실행해 걸린 시간에 대한 비율

Throughput - 단위 시간당 실행을 마친 프로세스의 수 

Turnaround Time - 프로세스가 만들어진 후 부터 끝날 때 까지 걸린 시간 

Response Time - 사용자가 명령어를 시작한 순간부터 프로그램이 실제로 작업을 시작할 때 까지의 시간 

Waiting Time - Ready Queue에서 프로세스가 대기한 시간 (Block 상태는 포함하지 않는다)

 

Priorities

준비 상태에 있는 프로세스들의 PCB에 기록된 우선순위를 보고 제일 높은 프로세스를 선택한다. 

Queue에 있는 모든 프로세스를 순차적으로 확인해야 하니 매우 비효율적이다. 

 

 

 

 

 

따라서 우선순위별로 Queue를 만들어 빠르게 탐색한다.

실제 구현은 static하지 않고 dynamic하게 할당되기에 해당하는 프로세스가 없다면 공간을 차지하지 않는다. 

 

프로세스가 처음 생성될 때 우선순위가 정해져야 하는데, 초기값으로 Base Priority를 사용한다.

이 값만 사용하는건 아니고 동적 우선순위를 함께 사용한다. 

 

우선순위를 활용한 스케쥴링은 간단하지만 Starvation이 발생할 수 있다.

우선순위가 낮은 프로세스는 CPU를 할당받기까지 계속 기다려야 할 수 있다. 

 

Unix나 Linux에서는 Ready Queue가 너무 오래 기다리게 되면 우선순위를 높여 언젠가는 CPU를 할당받을 수 있도록 설정했다.

 

 

First-Come-First-Served (FCFS, FIFO)

 

 

A가 들어오면 아무도 없으니 A에게 CPU를 할당한다.

B가 도착했을 때 CPU는 A를 실행하는 중이니 B에게 CPU를 할당할 수 없다. A가 끝날 때 까지 기다린다....

 

이런 식으로 실행하면 CPU-Bound Process를 실행할 때 매우 유리하다. 

I/O가 없다고 치면, 일단 CPU를 받은 후 작업이 끝날 때 까지 CPU를 사용할 수 있다.

 

반면 CPU 연산보다 I/O 작업이 더 많은 I/O-Bound Process를 실행할 때는 매우 비효율적이다.

또한, 금방 끝나는 프로세스를 먼저 처리할 시 더 효과적으로 실행할 수 있는 경우가 있는데.. FCFS 방식은 이 부분을 커버하지 못한다.

 

 

Round-Robin

 

Time Sharing System에서 사용되는 스케쥴링 방법이다.

Time Slice가 경과되면 Context Switch가 발생하고, 중단될 때 마다 해당 프로세스의 상태를 PCB에 저장하기에 추후 이어서 실행할 수 있다. 

Response Time이 좋은 알고리즘으로, 짧은 프로그램도 조금만 기다리면 실행될 수 있다. 

 

이 때 Time Slice를 어느 정도로 설정할 지가 매우 중요하다. 

길면 Context Switch가 발생하지 않지만 Response Time은 줄어든다. 

 

운영체제 개발자들은 적절한 선에서 Time Slice를 설정하는데.. 이건 개발자들의 경험에 기반.. 

 

 

Shortest Process Next 

 

Ready Queue에 들어있는 프로세스 중 실행시간이 가장 짧은 프로세스를 다음으로 실행하는 방식이다. 

B가 실행을 마친 시점에 C, D, E 프로세스가 도착했는데 그 중 실행시간이 가장 짧은 E를 먼저 실행한다.

 

실행시간을 Priority로 설정한 우선순위 기반 스케쥴링으로, 이 방법을 사용하려면 모든 프로세스의 실행 시간을 알고 있어야 한다.

General Purpose Computer에서는 사용하기 어렵지만, 특정 작업만 수행하는 컴퓨터에서는 사용할 수 있다. 

 

 

Shortest Remaining Time First 

 

남은 시간이 짧은 프로세스를 먼저 실행하는 알고리즘으로, Shortest Process Next 알고리즘과는 다르게 Preemptive 하게 동작한다.

즉, 프로세스를 실행하면서 남은 시간이 줄어들텐데, 그 때 마다 스케쥴링을 수행해 CPU를 뺏어오는 방식이다. 

 

 

Feedback

 

 

여러 Ready Queue를 사용하고, 프로세스가 생성되면 무조건 첫 번째 Queue에 넣어준다.

Round Robin과 동일하지만, 프로세스의 Time Slice가 끝나면 같은 Queue로 돌아가지 않고 다음 단계의 Queue로 들어가게 된다.

 

Queue의 단계가 커질수록 할당받는 Time Slice의 길이도 길어지고, 우선순위도 낮아진다.

결국 제일 높은 단계의 Queue에서는 실행 시간이 긴 프로세스만 남게 된다. 

 

 

 

---

 

 

 

UNIX 운영체제는 예전에 Priority Base Round Robin Scheduling 알고리즘을 사용한다. 

 

 

 

 

Base Priority를 기반으로 한 Dynamic Priority를 사용한다. (Bawse Priority = 60, Time Slice = 1sec, 60 clock interrupts/sec)

 

Clock Interrupt 발생 시 그 시점의 레지스터 값을 모두 Kernel Stack에 저장하고 Mode Change로 Kernel에 들어간다.

Kernel은 Interrupt를 처리하는 과정에서 Clock을 초기화하고 CPU count 값을 1 증가시킨다.

이후 User Mode로 돌아가기 전에 시스템 관리를 통해 상태를 확인한다.

 

CPU count가 60이 되면 해당 프로세스가 CPU를 할당받은 후 1초가 지나갔음을 의미하고, Time Slice가 만료됨을 의미한다.

이후 해당 프로세스의 상태값을 PCB에 저장하고 그 다음에 실행할 프로세스를 결정한다. 

 

운영체제는 시스템 관리 작업을 최대한 자주 실행해야 하고, 그렇기에 Clock Interrupt를 1초에 60번 발생하도록 설정한다.

 

프로세스 A가 실행되고 나서 1초가 지났다. A의 CPU count는 60이고, B와 C의 CPU count는 0이다.

스케쥴러는 모든 프로세스의 CPU count 값을 반으로 줄이고, 나눈 값에서 또 반을 나누고 현재 Priority 수치에 그 값을 더해준다.

이렇게 Dynamic Priority를 계산하고, 추후 스케쥴링 시 Dynamic Priority가 가장 작은 프로세스를 우선해서 스케쥴링한다.

 

프로세스가 CPU Time을 가지지 않고 쉬는 시간이 있으면 Priority값이 떨어지고, 우선순위는 높아진다. (나머지는 버림)

 

실행 중인 프로세스가 I/O 요청 시 Blocked 상태가 되는데, 이 때 프로세스는 자신에게 할당된 Time Slice를 모두 사용하지 못하고 CPU를 뺏긴다.

실행 중인 프로세스가 Interrupt 되고 그 결과 우선순위가 더 높은 프로세스가 깨어나는 경우에도 프로세스는 Time Slice를 모두 사용하지 못하고 CPU를 뺏긴다. 

 

Time Slice를 모두 사용하지 못하고 뺏기는 경우 해당 알고리즘에 따라 당연히 우선순위가 더 높아지니 다음 CPU를 더 빨리 받을 수 있다. 

 

 

Linux 운영체제는 예전에 O(1) Scheduler를 사용하다가 요즘은 CFS(Completely Fair Scheduler) 를 사용한다.

 

 

---

 

 

 

Text Editor / Compiler 

에디터는 우선순위가 높고 컴파일러는 우선순위가 낮다. (Interactive / Non-Interactive)

 

에디터는 우선순위가 높지만 사용자의 Input을 받아야 작동할 수 있고, Input을 받을 때는 Blocked 상태로 대기하게 된다.

그동안 우선순위가 낮은 컴파일러에게 CPU가 할당되는데, 이 때 사용자가 Input을 수행하면 Keyboard Interrupt가 발생해 Kernel Mode로 이동해 Interrupt를 처리한다.

 

이 과정에서 Blocked된 에디터를 Ready 상태로 바꾸고, 스케쥴러가 실행된다.

스케쥴러를 실행해 우선순위를 따지는데, 에디터가 컴파일러보다 우선순위가 높기에 Context Switch가 발생한다. 

CPU를 뺏긴 컴파일러 프로세스는 Ready Queue로 들어간다. (CPU가 주어져도 실행되지 못할 때 Blocked Queue로 이동한다)

 

에디터는 다시 실행되고 입력받은 문자열을 모니터같은 출력 장치에 출력하고 또 Input을 기다리기 위해 Blocked 상태로 대기한다.

이후 컴파일러에게 CPU가 다시 할당되고, 이전에 중단됐던 부분부터 이어서 실행한다. 

 

 

(전제 : Single Core CPU / Virtual Memory Address 사용)