[운영체제] CPU 스케쥴링

프로세스 관리는 OS의 역할 중 가장 중요한 부분입니다.

OS는 메모리 공간과 자원을 프로세스에게 할당하고 할당한 것들을 다른 프로세스가 간섭하지 못하도록 보호하며, 프로세스마다 우선순위를 부여하고, 프로세스 동기화를 하는 등 프로세스의 전반적인 모든 것에 관여합니다.

---

Process State

프로그램이 RAM으로 올라와 실행되고 종료되기까지, 프로세스는 5가지의 상태를 갖습니다.

상태를 포함한 프로세스에 대한 정보는 운영체제 내부의 PCB(Process Control Block)라는 자료구조에 담깁니다.

New : SSD에 있던 프로그램이 RAM으로 적재되는 상태

Ready : 프로세스가 CPU의 서비스를 받길 기다리는 상태

Running : 프로세스가 CPU의 서비스를 받는 상태

Waiting : 프로세스가 I/O의 서비스를 받길 기다리는 상태

Terminated : 프로세스가 종료되는 상태

 

OS가 SSD로부터 올라온 프로세스의 작업을 마무리 짓고 내려보내기까지 어떤 과정을 거치는지 알 필요가 있습니다.

---

Scheduling

RAM에 적재된 프로세스는 한 개가 아니기 때문에 프로세스가 CPU의 서비스를 받으려면 순서를 기다려야 합니다.

이 순서는 몇 가지 Queue에 의해 관리가 되며 스케쥴링을 위한 Queue는 크게 세 종류가 있습니다.

 

Job Queue

RAM은 용량이 적기 때문에 원하는 프로그램을 모두 RAM으로 옮길 수 없습니다.

따라서 RAM으로 올라올 프로그램을 정하는 큐가 Job Queue이며, 이 큐는 Job Scheduler에 의해 관리됩니다.

프로세스 상태 관점에서 이 스케쥴러는 프로세스를 New에서 Ready로 상태 전이시켜주는 것을 담당합니다.

또한, 프로세스는 연산의 비중이 높은 프로세스와 입출력의 비중이 높은 프로세스로 나뉘는데, 두 종류의 프로세스의 균형을 맞추는 것도 이 스케쥴러가 담당합니다.

프로그램이 RAM으로 올라오는 일은 상대적으로 덜 일어나기 때문에 Job Scheduler는 Long Term Scheduler라고도 합니다.

 

Ready Queue

RAM으로 올라온 프로세스는 CPU의 서비스를 받기 위해 또 줄을 서야 합니다.

일찍 도착한 프로세스가 먼저 CPU를 사용하는 것이 타당해 보이지만 몇 가지 이유에 의해 효율적이지 못하게 됩니다.

어떤 정책이 CPU를 가장 잘 굴릴 수 있을지 OS를 잘 설계해야 하며, 규정된 정책 하에 CPU에 프로세스를 보내주는 일을 CPU scheduler가 담당합니다. 이런 작업은 빈번히 발생되기 때문에 Short Term Scheduler라고 합니다.

이 스케쥴러는 프로세스를 Ready에서 Running로 상태 전이시켜줍니다.

 

Device Queue

프로세스가 CPU가 아닌 다른 장치를 사용하는 것도 있다는 것을 언급했었습니다.

해당 장치를 어느 프로세스가 사용할지 결정하는 스케쥴러는 Device Scheduler입니다.

Waiting상태에 있던 프로세스가 입출력 서비스를 받으면 다시 Ready상태로 돌아갑니다.

 

Medium Term Scheduler

RAM으로 올라온 프로그램 중 근래에 사용되지 않았던 프로세스는 굳이 RAM에 있을 이유가 없습니다.

SSD는 프로그램을 저장하는 파일 시스템(File System)이 주 기능이지만 SSD 내에는 사용되지 않는 프로세스를 담아두는 공간인 백킹 스토어(Backing Store)가 일부 존재합니다.

스케쥴러는 사용되지 않는 프로세스의 주소 공간을 SSD의 백킹 스토어로 옮겨놓고 나중에 RAM으로 데려옵니다.

---

Context Switching

스케쥴러에 의해 CPU의 서비스를 받는 프로세스가 변할 때, CPU는 프로세스의 정보를 FCB에 저장하고 다음 프로세스의 정보를 FCB에서 읽어와 레지스터에 적재시켜야 하는데 이를 문맥 전환(Context Switching)이라고 합니다. 

 

Context Switching이 일어나기 위해서는 스케쥴러를 빌려 어떤 프로세스로 전환될지 결정해야 합니다.

전환될 프로세스가 결정되면 OS의 dispatcher라는 요소에 의해 프로세스의 정보가 PCB에 적재되고 복원됩니다. 

적재되고 복원되는 과정은 자주 일어나는데, 이 과정이 많이 일어나면 부담은 심해집니다.

이 부담을 Context Switching Overhead라고 하며, OS를 설계 시 Overhead를 줄이는 쪽으로 만들어야 합니다.

 

---

Scheduling Algorithm

스케쥴링 알고리즘에는 여러 가지가 있고 어떤 스케쥴링이 좋은지 나타내는 척도가 몇 가지 존재합니다.

CPU 이용률(CPU Utilization) : CPU가 놀지 않고 일하는 비율

처리율(Throughput) : 시간당 작업 처리율

반환 시간(Turnaround Time) : 프로세스가 New 상태에서 Terminated 상태까지 가는데 걸린 시간

대기 시간(Waiting Time) : CPU의 서비스를 받기 위해 Ready Queue에서 기다린 시간

응답 시간(Response Time) : 사용자가 요청한 후 첫 응답이 나올 때까지 걸리는 시간 

연산이 많은 프로세스는 반환 시간이 중요하며 입출력이 많은 프로세스는 응답 시간이 중요합니다.

 

Preemptive

한 프로세스가 CPU를 사용하고 있음에도 해당 프로세스를 쫓아내고 다음 프로세스가 CPU를 사용하는 방식입니다.

이를 선점(Preemptive)이라고 하며, CPU의 서비스를 받고 있는 프로세스를 끝날 때까지 기다리면 비선점 방식입니다.

스케쥴링 알고리즘은 비선점과 선점 두 방식 중 적어도 하나를 지니고 있습니다.

 

FCFS(First-Come, First-Served)

Ready Queue에 먼저 도착한 프로세스가 먼저 CPU의 서비스를 받는 방식입니다.

그러나 Ready Queue내의 작업시간이 짧은 프로세스가 먼저 CPU의 서비스를 받는 게 평균 작업시간이 짧기 때문에 작업시간이 긴 프로세스가 Ready Queue에 먼저 도착했다면 다른 프로세스의 대기 시간이 길어지게 됩니다.

작업시간이 긴 프로세스에 의해 다른 프로세스가 묶여있는 단점을 FCFS방식의 호위 효과(Convoy Effect)라고 합니다.

CPU의 서비스를 받고 있는 프로세스를 다른 프로세스가 밀어내지 않기 때문에 비선점 방식의 알고리즘입니다.

 

SJF(shotest job first)

Ready Queue에 도착한 프로세스 중에서 작업시간이 짧은 프로세스가 먼저 CPU의 서비스를 받는 방식입니다.

하지만 어떤 프로세스가 작업시간이 짧은지 예측해야 하기 때문에 현실적인 방법은 아닙니다.

설계에 따라서 선점과 비선점 방식을 둘 다 사용할 수 있습니다.

 

Priority

Ready Queue에 Priority가 담긴 정보가 담겨있어서 해당 순서대로 CPU의 서비스를 받는 방식입니다.

하지만 자신보다 Priority가 더 높은 프로세스가 Ready Queue에 계속 담기면 그 프로세스는 영원히 실행되지 않습니다.

이를 기아(Starvation) 상태라고 하는데, Ageing이라는 요소를 추가하여 문제를 해결할 수 있습니다.

설계에 따라서 선점과 비선점 방식을 둘 다 사용할 수 있습니다.

 

RR(Round-Robin)

시간을 나눠서(Time sharing) Ready Queue에 존재하는 프로세스가 CPU의 서비스를 단위 시간 동안 받아서 일부만 실행되고 다시 Ready Queue로 돌아가는 것을 반복하는 방식입니다.

단위 시간이 매우 크면 FCFS 방식과 같고 매우 짧으면 마치 여러 개의 프로세스가 동시에 실행되는 것처럼 보입니다.

(싱글코어 기준 동시에 실행되는 것이 아니라 동시에 실행되는 것처럼 보이는 것이기 때문에 Concurrency의 성격)

다음 프로세스로 넘어갈 때 이전 프로세스 정보를 FCB에 저장하고 다음 프로세스 정보를 불러와야 하는데, 단위 시간이 짧으면 짧을수록 이 과정이 빈번히 일어나서 Cotnext Swtiching Overhgead가 커지는 단점이 있습니다.

RR 방식은 프로세스가 끝나지 않아도 다음 프로세스로 넘어가기 때문에 선점 방식만이 존재합니다.

---

[Ready Queue가 여러 개인 경우]

 

Multi-level Queue(MQ)

프로세스들은 몇 가지 종류의 프로세스로 나눌 수 있는데, CPU로 향하는 Ready Queue를 프로세스 종류만큼 둬서 각 프로세스가 자신에게 맞는 Ready Queue에서 CPU의 서비스를 받도록 대기하는 방식입니다.

각 Ready Queue들은 다른 Ready Queue와는 독립적으로 작동하며, Ready Queue마다 스케쥴링 정책을 달리할 수 있습니다.

 

Multi-level Feedback Queue(MFQ)

Multi-level Queue는 Priority가 낮은 Ready Queue가 Starvation 상태에 빠질 수 있는 단점이 있습니다.

MFQ는 프로세스가 다른 Ready Queue에도 들어갈 수 있도록 허용하여 MQ의 단점을 보완합니다.

---

프로세스의 생성과 소멸

부팅을 시키면 OS가 SSD에서 RAM으로 이동하고 루트 프로세스를 생성합니다

모든 프로세스는 PID(Process Identifier)를 가지고 있는데, 루트 프로세스는 0번 PID를 부여받습니다. 

이후에, fork System Call에 의해 새로운 자식 프로세스가 생성됩니다.

자식 프로세스는 부모 프로세스의 PCB를 복사하는데, PID와 메모리 주소 등의 정보는 새로 갱신됩니다.

 

exec System Call은 새로운 프로세스를 SSD로부터 가져올 수 있습니다.

이 때, PID 정보는 새로 갱신이 되지 않고, 가져온 프로세스가 기존 프로세스 위에 덮어 씌워집니다.

 

마지막으로, exit System Call에 의해 프로세스가 종료되며 종료될 때는 프로세스가 가진 자원을 OS에게 반납합니다.