1. 개요2. 서론3. 스케줄링 알고리즘
3.1. FCFS 스케줄링 (First Come First Serve Scheduling)3.2. SJF 스케줄링 (Shortest Job First Scheduling)
4. 기타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)이라는 기술로 구현한다. 프로세스 스케줄링은 운영체제가 하는 가장 중요한 일 중 하나이다. 이 문서는 유명한 프로세스 스케줄링 알고리즘에 대해 서술하는 문서이다.
다른 말로는 스레드 스케줄링(Thread Scheduling)이라는 개념이 있다. 과거에는 프로그램 실행 흐름이 프로세스 밖에 없었으나 프로세스보다 작은 실행 흐름인 스레드가 등장하면서 현재 운영체제의 스케줄링은 스레드를 최소 단위로 하고 있다. 즉 스레드가 명령 실행을 담당하고 프로세스는 이러한 스레드들을 모아놓고 메모리를 할당하고 자원을 공유시키는 하나의 그룹이라고 보면 된다.
2. 서론
서론에서는 이 문서에서 사용될 중요한 개념들을 정리한다.2.1. 프로세스 상태 (Process State)
프로세스는 다음 5가지 상태 중 하나를 가진다.- 생성(create) : 프로세스가 생성되는 중이다.
- 실행(running) : 프로세스가 프로세서를 차지하여 명령어들이 실행되고 있다.
- 준비(ready) : 프로세스가 프로세서를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리고 있다.
- 대기(waiting) : 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말한다.
- 종료(terminated) : 프로세스의 실행이 종료되었다.
아래는 프로세스의 상태전이이다.
- 디스패치(Dispatch) : 프로세스가 준비 상태에서 실행 상태로 전환되었다.
- 타이머 런아웃(Timer Runout) : 프로세스가 실행 상태에서 준비상태로 전환되었다. 일반적으로 선점 프로세스에서 발생한다.[2]
- 블록(Block) : 프로세스가 자원 부족, I/O 입출력대기, 인터럽트 등 다른 사유에 의해 실행 상태에서 대기 상태로 전환되었다.
- 활성화(Wake-up) : 프로세스가 부족한 자원을 재할당 받았다는 등의 사유로 대기 상태에서 준비 상태로 전환되었다.
CPU가 한 프로세스를 처리하다가 다른 프로세스로 전환하면서 컨텍스트 스위칭(문맥교환)이 발생한다. 프로세스가 사용하는 레지스터 등 여러 자원들을 메인 메모리에 저장하고 다음 프로세스가 사용하는 자원들을 메인 메모리에서 가져온다. 문맥교환은 전환시간이 짧을 수록 더욱 자주 발생하여 오버헤드가 높아진다. 문맥교환은 PCB(Process Control Block)에 의해 이루어진다.
운영체제는 준비 큐(Ready Queue), 대기 큐 (Waiting Queue) 등의 자료구조를 두어 이들 프로세스를 관리한다.
준비 큐는 준비 상태에 있는 프로세스들을 모아놓은 큐(Queue)이다. 운영체제는 CPU 스케줄러(CPU Scheduler)를 통해 준비 큐에 있는 프로세스 중 한 프로세스를 골라 다음에 실행시킨다.
2.2. 선점(preemptive)과 비선점(non-preemptive)
프로세스 스케줄링은 다음 네 가지 경우에 일어날 수 있다.- 프로세스가 실행 상태(running)에서 대기 상태(waiting)으로 전환될 때
- 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전환될 때
- 프로세스가 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때
- 프로세스가 종료되었을 때(terminated)
프로세스 스케줄링이 위의 네 가지 경우 모두에 일어난다면 이를 선점(preemptive) 스케줄링이라 한다. 선점 스케줄링 시스템에서는 운영체제가 프로세스에 할당되었던 CPU를 자체적으로 판단하여 뺏어올 수 있다. 선점 스케줄링은 마이크로소프트의 Windows 9x 운영체제(Windows 95, Windows 98, Windows 98 SE, Windows Me)부터 32비트 프로세스 한정으로 도입되었다.[3] Windows NT 계열과[4] 애플의 Mac OS X 등은 다단계 피드백 큐 스케줄링을 사용한다.
프로세스 스케줄링을 처음 배울 때 사람들이 가장 헷갈려 하는 것 중 하나가 선점과 비선점의 개념이다. 이름만 들었을때는 선점 스케줄링 시스템에서는 한 프로세스가 CPU를 '선점(먼저 차지)'해 자신의 작업이 다 끝날때까지 반환하지 않는것처럼 들린다. 하지만 위에서 서술했듯이 이는 비선점 스케줄링 시스템의 특징이다. 선점 스케줄링은 운영체제가 CPU를 먼저 '선점(preemptive)'하여 필요하다면 CPU를 프로세스로부터 뺏을 수 있는 스케줄링 방법이고, 비선점은 그 반대라고 이해하면 좋을 것 같다.[5]
선점 스케줄링과 비선점 스케줄링 중 어느 방식이 더 효휼적일까?
- 어떤 시스템에서는 선점 스케줄링을 구현하기 위해 필요한 하드웨어(ex. 타이머 등)가 없어 어쩔 수 없이 비선점 스케줄링을 사용할 수밖에 없다.
- 선점 시스템에서는 프로세스 간 공유 자원에 대한 문제가 발생할 수 있다. 만약 한 프로세스가 자원을 사용한 상태(예를 들어, 한 파일을 읽고 있을 때)에서 프로세스 전환이 일어나서 다른 프로세스가 running 상태가 되었는데, 이 두 번째 프로세스도 같은 자원에 접근하면 문제가 발생한다. 가끔씩 볼 수 있는 뮤텍스 관련 블루스크린이 선점 시스템의 상호배제 관련한 영역에서 문제가 발생해서 뜨는 것이다.
- 선점 시스템에서 만약 커널 프로세스가 중요한 작업을 하던 중 프로세스 전환이 일어난다면 어떻게 될까? UNIX 운영체제에서는 만약 커널 데이터가 수정되고 있을 때는 프로세스 전환을 하지 않는 전략을 사용하여 이 문제를 해결한다. 하지만 실시간 시스템(real-time system)에서 이는 문제가 된다.
3. 스케줄링 알고리즘
운영체제가 다음번 실행될 프로세스를 정하는 방법으로 아래와 같은 알고리즘이 있다.이때 각 알고리즘들의 효용성을 따지는 다양한 기준들이 있다.
- CPU 이용률(CPU utilization) : CPU를 얼마나 바쁘게 하는가. 높을수록 좋다.[단위 : %]
- 처리율(Throughput) : 단위시간당 얼마나 많은 프로세스들이 완료되는가. 클 수록 좋다.[단위 : 개]
- 소요시간(Turnaround time) : 프로세스가 요청된 후 완료하기까지 얼마나 걸리는가. 메모리 접근 시간, 대기 큐에서의 대기 시간, CPU에서의 실행 시간, I/O 시간 등의 합으로 계산한다. 짧을수록 좋다. [단위 : 초]
- 대기시간(Waiting time) : 프로세스가 대기 큐에서 기다리는 시간의 합. 짧을수록 좋다. [단위 : 초]
- 반응시간(Response time) : 프로세스가 요청된 후 첫 번째 응답을 받기까지 걸리는 시간. 주로 상호교환 시스템(interactive system)에서 사용된다. 짧을수록 좋다. [단위 : 초]
프로세스 스케줄링을 정확히 묘사하려면 프로세스 전환[6]에 소요되는 시간, CPU 한차례 사용시간(CPU burst time[7]), I/O 한차례 사용시간(I/O burst time) 등을 모두 보여야 하겠지만, 그렇게 한다면 논의가 너무 복잡해지므로
CPU 스케줄링의 결과는 Gantt Chart를 이용해 보일 수 있다. Gantt Chart는 프로세스가 CPU를 사용하기 시작한 시간과 종료된 시간을 나타낸 막대그래프이다.
3.1. FCFS 스케줄링 (First Come First Serve Scheduling)
FCFS 스케줄링은 가장 간단한 스케줄링 알고리즘으로, CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는 스케줄링 방법이다. FCFS 스케줄링은 비선점 스케줄링 방식이다. 급식소나 티켓 발부처에서 줄 서는 것을 생각하면 된다. FCFS 스케줄링은 큐(Queue)를 이용하면 쉽게 구현할 수 있다.3.1.1. 비전공자의 관점에서
예를 들어 어느 지하철역이 있다. 그런데 일반 열차든 급행 열차든 특급 열차든 통행이 가능한 선로는 한 방향에 하나이다. 그러면 일반 열차가 아무리 느려도 먼저 왔으면 일반 열차가 그 역에서 승객을 태우고 출발해야 다음 열차가 들어올 수 있고, 그 역을 통과하는 특급 열차라도 앞 열차가 승객을 태우고 있으면 앞 열차를 추월할 수 없어서 앞 열차가 승객을 태우고 출발할 때까지 기다려야 한다.이 말인 즉, 아무리 순위가 높거나, 정차 시간이 짧더라도, 먼저 도착한 열차에게 우선 순위가 부여된다.
3.1.2. 전공자의 관점에서
다음과 같은 CPU 한차례 사용시간(CPU burst time)을 갖는 프로세스 P1, P2, P3가 P1, P2, P3의 순서로 들어왔다고 하자.| 프로세스 | CPU 한차례 사용시간[ms] |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
FCFS 스케줄링은 구현은 간단하지만 효율적이진 않다. 위의 예에서 프로세스들의 평균 대기 시간(average waiting time)을 계산해보자.
- P1 : 실행되기까지 0ms 걸렸다. → 대기시간 = 0 [ms]
- P2 : 실행되기까지 24ms 걸렸다. → 대기시간 = 24 [ms]
- P3 : 실행되기까지 27ms 걸렸다. → 대기시간 = 27 [ms]
하지만 만약 P2, P3, P1의 순서로 프로세스들이 실행된다고 해보자.
- P1 : 실행되기까지 6ms 걸렸다. → 대기시간 = 6 [ms]
- P2 : 실행되기까지 0ms 걸렸다. → 대기시간 = 0 [ms]
- P3 : 실행되기까지 3ms 걸렸다. → 대기시간 = 3 [ms]
FCFS 스케줄링은 프로세스가 들어오는 순서에 따라서만 결과가 바뀌기 때문에
3.2. SJF 스케줄링 (Shortest Job First Scheduling)
그렇다면 어떻게 convoy effect를 줄일 수 있을까? FCFS 스케줄링에서는 큰 CPU 한차례 사용시간(CPU burst time)을 가지는 프로세스가 큐에 처음으로 들어오면 convoy effect 발생하였다. 그렇다면 CPU 한차례 사용시간(CPU burst time)이 작은 프로세스부터 먼저 끝낸다면 convoy effect를 최소화할 수 있을 것이다. 이 알고리즘을 SJF 스케줄링이라 한다.이때 SJF는 선점 스케줄링일수도 있고 비선점 스케줄링일 수도 있다. 비선점 SJF 스케줄링에서는 프로세스가 실행되는 도중 더 작은 CPU 한차례 사용시간(CPU burst time)을 가지는 프로세스가 들어오더라도 실행되던 프로세스가 스스로 대기 상태(waiting) 또는 종료 상태(terminated)가 되기 전에는 문맥 전환이 일어나지 않는다. 하지만 선점 SJF 스케줄링에서는 문맥 전환이 일어난다. 선점 SJF 스케줄링은 SRTF 스케줄링(Shortest Remaining Time First Scheduling)이라고도 한다.
이후 문단은 이해를 쉽게 하기위해 선점형 방식인 SJF와 HRN을 먼저 비교하고 이후에 SRTF에 대해서 알아보자.
SJF는 이름 그대로 Shortest, 가장 작은 실행시간을 가진 프로세스를 우선하기 때문에 대기시간이 긴 프로세스는 무한정 기다리게되는 기아 상태가 된다. 여기서 기아는 흔히 '아프리카 같이 음식이 부족해 굶고있는' 기아와 의미가 같다고 보면 된다.(...) 간단한 예시로 이해해보자.
예를들어 경기장에 화장실이 단 1개만 있으며 100명의 사람이 화장실 사용을 기다리고 있다고 생각해보자. 이 때 관리자가 나타나 한명씩 물어보기 시작한다.
"A씨는 똥을 얼마나 빨리 쌀 수 있소?"
A씨는 똥을 5초만에 싸고 나올 수 있다고 답한다.
"B씨는 똥을 얼마나 빨리 쌀 수 있소?"
B씨는 똥을 2초만에 싸고 나올 수 있다고 답한다.
"김나무씨는 똥을 얼마나 빨리 쌀 수 있소?"
김나무씨는 변비가 있어 5분이 걸린다고 답한다. 그러자 관리자는 "빨리 쌀 수 있는 사람이 있으니 줄 뒤로 가십시오" 하고 김나무씨를 줄 맨 뒤로 보냈다.
이렇게 앞의 99명을 기다리고 똥을 싸면 좋으려만 계속 경기장에 사람이 몰려들고... 김나무씨는 순위에서 밀려 계속 똥을 못싸게 되었다.
예시가 더럽긴 해도 이러한 김나무씨의 상황을 "기아 현상"이라고 한다. 프로세스의 실행 시간(버스트 시간)이 길어 계속해서 후순위로 밀어지게 되는 것이다.
그렇다면 김나무씨는 영원히 못싸게 되는 것일까? 그것은 아니다. 에이징기법 을 통해 김나무씨도 똥을 쌀 수 있다.
에이징기법은 대기시간에 가중치를 두는 프로세스 스케줄링 기법이다. 화장실 앞에 서있는 시간(대기시간)이 길어질수록 가중치는 점차 상승하게 되어, 앞전보다 훨씬 빠르게 화장실(자원)을 얻을 수 있게 된다. 예시를 보며 이해해보자.
- 김나무의 초기 똥 싸는 시간(실행시간) : 300초
- 김나무가 화장실 앞에서 기다린 시간(대기시간) : 0초
- 김나무의 HRN : 1
처음에는 기다린 시간이 없다고 가정한다. 만약 똥 싸는 시간이 300초 보다 빠른 사람이 온다면 그들에게 화장실을 넘겨줘야한다.
- 김나무의 초기 똥 싸는 시간(실행시간) : 300초
- 김나무가 화장실 앞에서 기다린 시간(대기시간) : 120초
- 김나무의 HRN : 1.4
김나무는 화장실 앞에서 2분을 기다렸다. 이제 김나무의 우선순위는 (실행시간+대기시간)/실행시간 을 계산하여 1.4가 된다. 여기서 2분을 더 기다렸다고 가정해보자
- 김나무의 초기 똥 싸는 시간(실행시간) : 300초
- 김나무가 화장실 앞에서 기다린 시간(대기시간) : 240초
- 김나무의 HRN : 1.8
확인해보면 김나무의 HRN(Highest Response Ratio Next)이 높아지는 것을 알 수 있다. HRN이 높을 수록 우선순위가 높아진다. 즉 HRN은 SJF의 불평등함을 해소한 것이다. 그럼 김나무 말고 다른 사람을 불러와보자.
- 김나무의 초기 똥 싸는 시간(실행시간) : 300초
- 김나무가 화장실 앞에서 기다린 시간(대기시간) : 240초
- 김나무의 HRN : 1.8
- 이위키의 초기 똥 싸는 시간(실행시간) : 60초
- 이위키가 화장실 앞에서 기다린 시간(대기시간) : 10초
- 이위키의 HRN : 1.16
불평등이 해소됨에 따라 김나무가 똥을 싸는 시간은 300초나 소요되지만 HRN이 높아짐에 따라 김나무가 우선적으로 화장실 사용권을 얻게 되었다!
3.2.1. SRTF 스케줄링 (Shortest Remaining Time First Scheduling)
프로세스 도착 시간을 따지지 않고, 한 프로세스가 실행 중이라도 다른 프로세스가 도착한 시간을 기준으로 남은 처리 시간과 다른 프로세스의 처리 시간을 비교하여 스케줄 순서를 결정하는 방식이다.예를 들어 A 프로세스 처리 시간이 40 ms인데, 프로세스 처리 시작하고 5 ms 지나서 처리 시간이 20 ms인 B 프로세스가 도착했다고 치자. 이 때 A 프로세스의 남은 처리 시간이 35 ms이지만, B 프로세스의 처리 시간보다 길기 때문에 A 프로세스는 대기 상태에 들어가고, B 프로세스가 처리될 때까지 기다려야 한다.
그런데 B 프로세스가 도착 후 5 ms(A 프로세스 도착 후 10 ms) 지났을 때 처리 시간이 8 ms인 C 프로세스가 도착하면 이 시점에서 B 프로세스는 남은 처리 시간이 15 ms이므로 C 프로세스의 처리 시간보다 길기 때문에 B 프로세스는 대기 상태가 되고, C 프로세스가 작업을 하게 된다.
5 ms 지나서 처리 시간이 40 ms인 D 프로세스가 들어와도 C 프로세스의 남은 처리 시간(3 ms)보다 길어서 C 프로세스는 계속해서 작업을 진행하고, C 프로세스가 작업이 끝나는 시점에서 A, B, D 모두의 남은 처리 시간을 비교하는데, 이 시점에서 A 프로세스는 남은 시간이 35 ms, B 프로세스는 남은 시간이 15 ms, D 프로세스는 남은 시간이 40 ms이므로 B - A - D 순으로 작업을 진행하게 된다.
3.3. 우선순위 스케줄링 (Priority Scheduling)
각 프로세스들마다 우선순위를 배정한다. 만약 우선순위가 동일하다면 FCFS 기법을 이용하여 처리하게 된다.우선순위 스케줄링은 비선점 기법이다.
3.4. RR 스케줄링 (Round Robin Scheduling)
프로세스들 간에 우선순위를 두지 않고, 순서대로 시간단위로 프로세스에 자원을 할당시켜준다. 쉽게 생각하여 화장실을 돌아가면서 사용하다가 자기에게 할당된 시간이 다되면 바로 끊고 나와, 화장실 사용을 기다리는 줄 맨뒤로 가는 방식이다. 다른 방식으로 시분할(Sequence) 스케줄링이라고도하나 RR로 쓰이는 경우가 일반적이다.시간적으로 10ms~100ms 정도가 프로세스에 할당된다. 해당 시간동안 프로세스는 자원을 받아 실행될 수 있다.
이런 스케줄링이 늘 그렇듯이 시간간격이 너무 좁을 경우 문맥교환에 의한 오버헤드가 과다하게 발생하게된다.
3.5. MQ 스케줄링 (Multilevel Queue Scheduling)
3.6. MFQ 스케줄링 (Multilevel Feedback Queue Scheduling)
4. 기타
컴퓨터 네트워크 관리 기술 중 하나인 서비스품질(QoS)을 위해 패킷을 처리하는 알고리즘과 원천 기술이 동일하다.[1] execute와 run은 모두 한국어로 '실행하다'로 번역된다. 하지만 컴퓨터에서 이 두 단어의 뜻은 조금 다른데, execute는 '어떤 프로그램을 메모리에 올려서 프로세서가 처리할 수 있게 하다'의 의미이고, run은 'execute된 프로그램(이때부터는 프로그램이라 하지 않고 프로세스라 한다)을 실제로 프로세서가 읽어 명령들을 처리하다'의 의미이다. 단일프로세서 시스템에서도 여러 개의 프로그램을 execute할 수 있다. (메모리 용량이 허용하는 이상 execute 가능하다.) 하지만 이들 중 프로세서는 한 번에 오직 단 하나의 프로세스만 run할 수 있다.(= 오직 단 하나의 프로세스만이 CPU를 사용할 수 있다.) 쉽게 말하면 여러분은 책상에 여러 과목 책을 올려 둘 수 있지만(execute) 공부는 한번에 한 과목만 할 수 있다.(run)[2] 예를들어 버스트시간(실행시간)이 100ms로 설정된 RR 알고리즘에서 A라는 프로세스가 100ms 내에 작업을 끝내지 못했거나, 작업을 마쳤음에도 어떠한 사유에 의해 자원반환을 하지 않을 경우 타이머 런아웃 상태가 된다.[3] 16비트 프로세스는 하위 호환을 위해 Windows 3.x에 사용되었던 비선점 스케줄링으로 동작했다.[4] 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, Windows 10, Windows 11.[5] 근데 이렇게 이해하면 'The process is preempted'라는 문장의 해석이 이상해진다. 이 문장의 뜻은 '그 프로세스는 preempt되었다(= 더 이상 running 상태에 있지 않다 = 다른 프로세스가 CPU를 차지하였다)'이다. preempt의 해석을 어원인 empty의 뜻으로 해석하면 의미가 통한다. 'The process is preempted' = '그 프로세스는 비워졌다(버려졌다).', 'preemptive' = '버려질 수 있는' 이게 다 preemptive를 누군가가 처음 번역할 때 선점(preoccupancy)이라고 번역해서 그렇다. 번역가를 죽입시다. 번역가는 나의 원수[6] 문맥 전환(Context Switching)이라고도 한다.[7] CPU burst time은 프로세스가 실행(running) 상태에 진입한 후 대기(waiting) 또는 종료(terminated) 상태로 변하기까지의 시간을 의미한다. 비선점 시스템에서는 CPU가 프로세스의 CPU burst time동안 그 프로세스에게 독점적으로 할당된다.