[OS] 4. Process Scheduling

https://simple-coding-place.tistory.com/21

[OS] Process

https://simple-coding-place.tistory.com/22

[OS] Thread

위 두 글에 Multi Process와 Multi Thread의 Context Switching에 대해 설명되어있다.

 

Scheduling

Multi Process, Multi Thread 환경에서 모든 Process와 Thread를 동시에 실행시킬 수 있을 만큼 많은 CPU를 가지고 있다면 좋겠지만 현실적으로는 불가능한 일이다.

 

따라서 운영체제는 제한된 코어의 CPU를 바탕으로 어떤 Process를 실행시킬 것인지 선택해야 하는데,

이 과정을 Scheduling 이라고 한다.

 

Process가 동작할 때 이미 메모리에 올라가 있는 데이터를 바탕으로 연산 등의 작업을 수행하는 것을 `CPU burst` 라고 하며, I/O 작업을 수행하는 과정을 I/O burst라고 한다.

이러한 용어를 바탕으로, I/O burst가 빈번한 task를 I/O bound job이라고 하고 CPU burst가 긴 작업을 CPU bound job이라고 한다.

 

이처럼 컴퓨터에서 실행되는 프로세스는 동일한 형태의 작업만을 수행하는 것이 아니라 어떤 프로세스는 I/O bound job을 처리하고 있고 어떤 프로세스는 CPU bound job을 수행하고 있다.

 

그렇다면 둘 중 CPU 점유 시간이 긴 task는 어떤 job일까?

당연히 CPU burst가 긴 CPU bound job이 CPU를 주로 점유하게 된다.

 

만약 이를 적절하게 분배해주지 못하면, CPU burst time이 짧은 I/O bound job은 CPU를 거의 점유하지 못할 것이며, 이는 사용자가 원하는 특정 프로그램이 CPU 자원을 거의 할당받지 못해 긴 시간을 대기해야 하는 문제를 야기한다.

이러한 이유로 Process Scheduling이 필요한 것이다.

 

Scheduling Criteria

CPU가 프로세스를 스케줄링하는 과정에서, 평가 요소로 사용하는 몇 가지 척도가 존재한다.

이를 `Scheduling Criteria`라고 한다.

 

이러한 Scheduling 과정에서 사용하는 지표로 `CPU utilization`, `Throughput`, `Waiting Time`, `Response Time`과 `Turnaround Time`이 존재한다.

 

CPU utilization은 전체 시간 중 CPU가 놀지 않고 일한 시간을 말한다.

Throughput은 주어진 시간 동안 몇 개의 task를 완료했는지를 평가하는 척도에 해당한다.

 

Waiting Time은 Ready Queue에서 대기한 시간의 총 합을 의미한다.

Response Time의 경우 작업이 Queue에 등록된 후 최초 실행될 때까지 걸린 시간을 의미하며

Turnaround Time의 경우 실행시간과 대기 시간의 합으로, 작업이 Queue에 등록된 후 완전히 종료될 때 까지의 시간을 말한다.

 

Scheduling Algorithm은 이러한 Criteria 요소들을 고려하려 결정된다.

 

Scheduling의 종류

 

대표적인 Process Scheduling 알고리즘에는 FIFO, SJF, Round Robin, Multi Level Feedback Queue등이 있다.

 

FIFO

First In First Out의 준말로, `FCFS(First Come First Serve)` 라고도 한다.

 

단순히 큐에 도착한 순서대로 CPU 자원을 할당하는 방식이다.

 

이미 실행 중인 프로세스의 자원을 빼앗지 않는 `Non Preemptive` 방식의 스케줄링에 해당한다.

 

SJF

Shortest Job First의 준말로, 말 그대로 가장 짧은 작업(CPU burst time이 짧은 작업)을 먼저 수행하는 방식이다.

 

다만 수행시간이 긴 작업의 경우 무한히 대기하는 상황이 발생할 수도 있다.

 

현재 수행 중인 작업보다 더 짧은 CPU burst time을 가지는 작업이 들어오는 경우 해당 작업에 CPU 자원을 양보하도록 구현하는 경우 `Preemptive SJF`이며, 한 번 CPU를 잡으면 양보하지 않게 구현하면 `Non-Preemptive SJF`이다.

 

 

Priority Scheduling

process마다 priority를 부여하여, 높은 우선순위를 가진 프로세스에게 CPU 점유 우선권을 제공하는 스케줄링 방법이다.

 

SJF와 마찬가지로, 더 높은 우선순위의 프로세스가 CPU 자원을 빼앗아 사용할 수 있으면 Preemptive, 그렇지 않으면 Non-Preemptive이다.

 

다만 우선순위가 매우 낮은 프로세스의 경우 영원히 CPU를 점유하지 못하는 starvation 문제가 발생할 수 있는데,

aging 등의 개념을 도입하여, 너무 오래 기다린 프로세스의 우선순위를 높여주는 방식으로 문제를 해결한다.

 

Round Robin

FIFO(FCFS) 방식에 의해 큐에 입력된 프로세스들에 대해 동일한 시간의 `Time Quantum`만큼만 작업을 진행하고, 다음 프로세스에게 권한을 넘겨준 후 동일한 방식을 반복하는 것을 말한다.

 

예를 들어, Time Quantum을 2초라고 설정하고 Process `A`,  `B`, `C`가 순서대로 큐에 들어있다고 가정하자

 

OS는 A를 2초 실행한 후 A를 큐의 맨 뒤로 옮기고, B를 2초 실행하고 B를 큐의 맨 뒤로 옮긴 후

C를 2초 실행하고 다시 큐의 맨 뒤로 이동시킨다.

 

이 과정을 반복하면 모든 프로세스들이 공평한 시간 만큼 CPU를 점유하게 할 수 있다.

따라서 Response time을 높일 수 있다는 장점이 있고, CPU burst time이 짧으면서 빈번하게 발생하는 I/O bound job에게 효율적으로 동작한다.

 

하지만 `Context Switching`이 너무 자주 일어나기 때문에 이에 따른 Overhead가 너무 커진다는 단점이 있으며,

Time Quantum을 너무 크게 잡으면 FIFO와 유사한 방식으로 동작하기 때문에 적절한 크기를 설정해주는 것이 중요하다.

 

프로세스가 실행되는 도중 멈추고 다른 프로세스가 자원을 할당받는 방식이기 때문에 `Preemtive` 방식이다.

Multi Level Queue

Queue를 여러개 설정하고, 각 Queue가 전담하는 태스크를 설정하는 방식이다.

 

각 Queue에는 Priority, 즉 우선순위를 부여한다.

우선 순위가 높은 Queue에 작업이 있을 경우, 우선적으로 처리하게된다.

 

아래 그림을 보면 쉽게 이해할 수 있다.

 

시스템 작업이 가장 높은 우선순위를 가지기 때문에 학생 작업 Queue에 아무리 많은 작업이 쌓여 있어도, 시스템 작업 Queue가 비어있지 않다면 실행될 수 없다

(학생 작업은 가장 낮은 Priority를 가지기 때문에 대화형, 편집, 일괄처리형 또한 모두 비어있어야 할 것이다.)

 

이러한 알고리즘에 의해 Starvation이 발생하는 것을 막기 위해 Queue 마다 Time Quantum을 차등적으로 설정한다.

 

Multi Level Feedback Queue

가장 일반적으로 사용되는 Scheduling 방식이다.

 

Priority에 따라 Round Robin으로 작동하는 Queue를 여러개 만들고, 높은 Priority를 가지는 Queue는 짧은 Time Quantum을 사용하고 낮은 Priority를 가지는 Queue일수록 긴 time quantum을 사용한다.

 

Time Quantum을 이렇게 설정하는 이유는, queue에 들어온 작업에 대해 Priority를 측정하기 위한 것이다.

아래 그림을 보면 Time quantum의 차등적 설정 이유와 작동 방식에 대해 알 수 있다.

 

https://hyelie.tistory.com/entry/OS-Process-Scheduling

그림을 간단하게 설명하자면,

 

새로운 프로세스가 생성되면 우선 priority가 가장 높은 Queue에 들어가게 된다.

이후 짧은 Time Quantum 내로 작업을 완료하지 못하면, Priority가 더 낮은 Queue로 이동한다.

 

즉, 높은 Priority를 가진 Queue 일수록 Time Quantum을 작게 하는 이유는 해당 Process가 짧은 Time Quantum 내로 작업을 완료하지 못하면 하위 Queue로 이동시키기 위함이다.

 

만약 높은 Priority Queue에 대해서 큰 Time Quantum 값을 배정한다면, 각 프로세스들의 Queue 이동 여부를 검사하는데 많은 시간이 소요될 것이다.