프로세스 스케줄링

 

1. 개요
2. 서론
2.1. 프로세스 상태 (Process State)
2.2. 선점(preemptive)과 비선점(non-preemptive)
3. 스케줄링 알고리즘
3.1. FCFS 스케줄링 (First Come First Serve Scheduling)
3.2. SJF 스케줄링 (Shortest Job First Scheduling)
3.2.1. SRTF 스케줄링 (Shortest Remaining Time First Scheduling)
3.3. 우선순위 스케줄링 (Priority Scheduling)
3.4. RR 스케줄링 (Round Robin Scheduling)
3.5. MQ 스케줄링 (Multilevel Queue Scheduling)
3.6. MFQ 스케줄링 (Multilevel Feedback Queue Scheduling)


프로세스 스케줄링
(Process Scheduling)

1. 개요

단일프로세서 시스템(Single Processor System)에서는 한 번에 한 프로세스만 실행[1]될 수 있다. 하지만 프로세스가 항상 CPU를 사용하는 것은 아니다. 키보드나 마우스 등의 입력 장치에서 사용자의 입력을 기다리거나, 프린터 등의 느린 출력장치에서 데이터를 출력할 때 CPU는 일을 하지 않고 가만히 있는다. 일반적으로 프로세스는 CPU를 한차례 사용(CPU burst)하고 I/O를 한차례 사용(I/O burst)하는 주기를 반복한다. I/O를 사용하는 주기에서는 CPU를 사용하지 않는다. 그렇다면 여러 프로세스를 처리할 때, 한 프로세스가 모든 작업이 끝날때까지 기다렸다가 다음 프로세스를 실행하는 방법보다 '''한 프로세스를 실행 가능한 시점까지 실행하고, I/O 등 CPU를 사용하지 않는 작업을 할 때는 다른 프로세스를 실행한다'''면 CPU 사용 효율을 높일 수 있다.
오늘날의 운영체제는 위 아이디어를 프로세스 스케줄링(Process Scheduling)이라는 기술로 구현한다. 프로세스 스케줄링은 운영체제가 하는 가장 중요한 일 중 하나이다. 이 문서는 유명한 프로세스 스케줄링 알고리즘에 대해 서술하는 문서이다.

2. 서론

서론에서는 이 문서에서 사용될 중요한 개념들을 정리한다.

2.1. 프로세스 상태 (Process State)

프로세스는 다음 5가지 상태 중 하나를 가진다.
  • 생성(create) : 프로세스가 생성되는 중이다.
  • 실행(running) : 프로세스가 프로세서를 차지하여 명령어들이 실행되고 있다.
  • 준비(ready) : 프로세스가 프로세서를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리고 있다.
  • 대기(waiting) : 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말한다.
  • 종료(terminated) : 프로세스의 실행이 종료되었다.
운영체제는 준비 큐(Ready Queue), 대기 큐 (Waiting Queue) 등의 자료구조를 두어 이들 프로세스를 관리한다.
준비 큐는 준비 상태에 있는 프로세스들을 모아놓은 큐(Queue)이다. 운영체제는 CPU 스케줄러(CPU Scheduler)를 통해 준비 큐에 있는 프로세스 중 한 프로세스를 골라 다음에 실행시킨다.

2.2. 선점(preemptive)과 비선점(non-preemptive)

프로세스 스케줄링은 다음 네 가지 경우에 일어날 수 있다.
  • 프로세스가 실행 상태(running)에서 대기 상태(waiting)으로 전환될 때
  • 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전환될 때
  • 프로세스가 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때
  • 프로세스가 종료되었을 때(terminated)
프로세스 스케줄링이 첫 번째와 네 번째 경우에만 일어난다면 이를 비선점(non-preemptive, 또는 cooperative) 스케줄링이라 한다. 비선점 스케줄링 시스템에서는 프로세스가 대기 상태에 들어가거나 종료되지 않고서는 프로세스 전환이 일어나지 않는다. 비선점 스케줄링은 마이크로소프트 Windows 3.x까지 사용되었다.
프로세스 스케줄링이 위의 네 가지 경우 모두에 일어난다면 이를 선점(preemptive) 스케줄링이라 한다. 선점 스케줄링 시스템에서는 운영체제가 프로세스에 할당되었던 CPU를 자체적으로 판단하여 뺏어올 수 있다. 선점 스케줄링은 마이크로소프트의 Windows 9x 운영체제(Windows 95, Windows 98, Windows 98 SE, Windows Me)부터 32비트 프로세스 한정으로 도입되었다.[2] Windows NT 계열과[3] 애플의 Mac OS X 등은 다단계 피드백 큐 스케줄링을 사용한다.
프로세스 스케줄링을 처음 배울 때 사람들이 가장 헷갈려 하는 것 중 하나가 선점과 비선점의 개념이다. 이름만 들었을때는 선점 스케줄링 시스템에서는 한 프로세스가 CPU를 '선점(먼저 차지)'해 자신의 작업이 다 끝날때까지 반환하지 않는것처럼 들린다. 하지만 위에서 서술했듯이 이는 비선점 스케줄링 시스템의 특징이다. 선점 스케줄링은 운영체제가 CPU를 먼저 '선점(preemptive)'하여 필요하다면 CPU를 프로세스로부터 뺏을 수 있는 스케줄링 방법이고, 비선점은 그 반대라고 이해하면 좋을 것 같다.[4]
선점 스케줄링과 비선점 스케줄링 중 어느 방식이 더 효휼적일까? 이 질문에 정답은 없다. 상황에 따라 다르기 때문이다.
  • 어떤 시스템에서는 선점 스케줄링을 구현하기 위해 필요한 하드웨어(ex. 타이머 등)가 없어 어쩔 수 없이 비선점 스케줄링을 사용할 수밖에 없다.
  • 선점 시스템에서는 프로세스 간 공유 자원에 대한 문제가 발생할 수 있다. 만약 한 프로세스가 자원을 사용한 상태(예를 들어, 한 파일을 읽고 있을 때)에서 프로세스 전환이 일어나서 다른 프로세스가 running 상태가 되었는데, 이 두 번째 프로세스도 같은 자원에 접근하면 문제가 발생한다.
  • 선점 시스템에서 만약 커널 프로세스가 중요한 작업을 하던 중 프로세스 전환이 일어난다면 어떻게 될까? UNIX 운영체제에서는 만약 커널 데이터가 수정되고 있을 때는 프로세스 전환을 하지 않는 전략을 사용하여 이 문제를 해결한다. 하지만 실시간 시스템(real-time system)에서 이는 문제가 된다.

3. 스케줄링 알고리즘

운영체제가 다음번 실행될 프로세스를 정하는 방법으로 아래와 같은 알고리즘이 있다.
이때 각 알고리즘들의 효용성을 따지는 다양한 기준들이 있다.
  • CPU 이용률(CPU utilization) : CPU를 얼마나 바쁘게 하는가. 높을수록 좋다.[단위 : %]
  • 처리율(Throughput) : 단위시간당 얼마나 많은 프로세스들이 완료되는가. 클 수록 좋다.[단위 : 개]
  • 소요시간(Turnaround time) : 프로세스가 요청된 후 완료하기까지 얼마나 걸리는가. 메모리 접근 시간, 대기 큐에서의 대기 시간, CPU에서의 실행 시간, I/O 시간 등의 합으로 계산한다. 짧을수록 좋다. [단위 : 초]
  • 대기시간(Waiting time) : 프로세스가 대기 큐에서 기다리는 시간의 합. 짧을수록 좋다. [단위 : 초]
  • 반응시간(Response time) : 프로세스가 요청된 후 첫 번째 응답을 받기까지 걸리는 시간. 주로 상호교환 시스템(interactive system)에서 사용된다. 짧을수록 좋다. [단위 : 초]
프로세스 스케줄링을 정확히 묘사하려면 프로세스 전환[5]에 소요되는 시간, CPU 한차례 사용시간(CPU burst time[6]), I/O 한차례 사용시간(I/O burst time) 등을 모두 보여야 하겠지만, 그렇게 한다면 논의가 너무 복잡해지므로 CPU 한차례 사용시간만을 따지도록 하겠다.
CPU 스케줄링의 결과는 '''Gantt Chart'''를 이용해 보일 수 있다. Gantt Chart는 프로세스가 CPU를 사용하기 시작한 시간과 종료된 시간을 나타낸 막대그래프이다.

3.1. FCFS 스케줄링 (First Come First Serve Scheduling)

FCFS 스케줄링은 '''CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는''' 스케줄링 방법이다. FCFS 스케줄링은 '''비선점 스케줄링''' 방식이다. FCFS 스케줄링은 큐(Queue)를 이용하면 쉽게 구현할 수 있다.
다음과 같은 CPU 한차례 사용시간(CPU burst time)을 갖는 프로세스 P1, P2, P3가 P1, P2, P3의 순서로 들어왔다고 하자.
프로세스
CPU 한차례 사용시간[ms]
P1
24
P2
3
P3
3
이때 CPU 스케줄링의 결과는 다음과 같이 표현된다.
[image]
FCFS 스케줄링은 구현은 간단하지만 효율적이진 않다. 위의 예에서 프로세스들의 평균 대기 시간(average waiting time)을 계산해보자.
  • P1 : 실행되기까지 0ms 걸렸다. → 대기시간 = 0 [ms]
  • P2 : 실행되기까지 24ms 걸렸다. → 대기시간 = 24 [ms]
  • P3 : 실행되기까지 27ms 걸렸다. → 대기시간 = 27 [ms]
∴ 평균 대기 시간 = (0 + 24 + 27) / 3 = 17 [ms]
하지만 만약 P2, P3, P1의 순서로 프로세스들이 실행된다고 해보자.
[image]
  • P1 : 실행되기까지 6ms 걸렸다. → 대기시간 = 6 [ms]
  • P2 : 실행되기까지 0ms 걸렸다. → 대기시간 = 0 [ms]
  • P3 : 실행되기까지 3ms 걸렸다. → 대기시간 = 3 [ms]
∴ 평균 대기 시간 = (6 + 0 + 3) / 3 = 3 [ms]
FCFS 스케줄링은 프로세스가 들어오는 순서에 따라서만 결과가 바뀌기 때문에 효율적이지 못한 알고리즘이다. P1, P2, P3의 순으로 프로세스가 들어왔을때의 상황에서 P2, P3은 P1이라는 커다란 프로세스가 끝날때까지 계속 기다려야 한다. 이런 식으로 다른 모든 프로세스들이 커다란 한 프로세스가 끝날때까지 계속 기다리는 현상을 convey effect라 한다. convey effect는 CPU와 장치들의 사용률을 낮추기 때문에 되도록이면 지양해야 한다.

3.2. SJF 스케줄링 (Shortest Job First Scheduling)

그렇다면 어떻게 convey effect를 줄일 수 있을까? FCFS 스케줄링에서는 큰 CPU 한차례 사용시간(CPU burst time)을 가지는 프로세스가 큐에 처음으로 들어오면 convey effect 발생하였다. 그렇다면 '''CPU 한차례 사용시간(CPU burst time)이 작은 프로세스부터 먼저 끝낸다'''면 convey effect를 최소화할 수 있을 것이다. 이 알고리즘을 SJF 스케줄링이라 한다.
이때 SJF는 선점 스케줄링일수도 있고 비선점 스케줄링일 수도 있다. 비선점 SJF 스케줄링에서는 프로세스가 실행되는 도중 더 작은 CPU 한차례 사용시간(CPU burst time)을 가지는 프로세스가 들어오더라도 실행되던 프로세스가 스스로 대기 상태(waiting) 또는 종료 상태(terminated)가 되기 전에는 문맥 전환이 일어나지 않는다. 하지만 선점 SJF 스케줄링에서는 문맥 전환이 일어난다. 선점 SJF 스케줄링은 '''SRTF 스케줄링(Shortest Remaining Time First Scheduling)'''이라고도 한다.
우선 비선점 SJF 스케줄링부터 보자.

3.2.1. SRTF 스케줄링 (Shortest Remaining Time First Scheduling)


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


3.4. RR 스케줄링 (Round Robin Scheduling)


3.5. MQ 스케줄링 (Multilevel Queue Scheduling)


3.6. MFQ 스케줄링 (Multilevel Feedback Queue Scheduling)

[1] execute와 run은 모두 한국어로 '실행하다'로 번역된다. 하지만 컴퓨터에서 이 두 단어의 뜻은 조금 다른데, execute는 '어떤 프로그램을 메모리에 올려서 프로세서가 처리할 수 있게 하다'의 의미이고, run은 'execute된 프로그램(이때부터는 프로그램이라 하지 않고 프로세스라 한다)을 실제로 프로세서가 읽어 명령들을 처리하다'의 의미이다. 단일프로세서 시스템에서도 여러 개의 프로그램을 execute할 수 있다. (메모리 용량이 허용하는 이상 execute 가능하다.) 하지만 이들 중 프로세서는 한 번에 오직 단 하나의 프로세스만 run할 수 있다.(= 오직 단 하나의 프로세스만이 CPU를 사용할 수 있다.)[2] 16비트 프로세스는 하위 호환을 위해 Windows 3.x에 사용되었던 비선점 스케줄링으로 동작했다.[3] Windows NT 3.x, Windows NT 4.0, Windows 2000, Windows XP, Windows Server 2003, Windows Vista, Windows Server 2008, Windows 7, Windows Server 2008 R2, Windows 8, Windows Server 2012, Windows 8.1, Windows Server 2012 R2, Windows 10, Windows Server 2016, Windows Server 2019.[4] 근데 이렇게 이해하면 'The process is preempted'라는 문장의 해석이 이상해진다. 이 문장의 뜻은 '그 프로세스는 preempt되었다(= 더 이상 running 상태에 있지 않다 = 다른 프로세스가 CPU를 차지하였다)'이다. preempt의 해석을 어원인 empty의 뜻으로 해석하면 의미가 통한다. 'The process is preempted' = '그 프로세스는 비워졌다(버려졌다).', 'preemptive' = '버려질 수 있는' [5] 문맥 전환(Context Switching)이라고도 한다.[6] CPU burst time은 프로세스가 실행(running) 상태에 진입한 후 대기(waiting) 또는 종료(terminated) 상태로 변하기까지의 시간을 의미한다. 비선점 시스템에서는 CPU가 프로세스의 CPU burst time동안 그 프로세스에게 독점적으로 할당된다.

분류