[OS] CPU 스케쥴링

출처 : https://docplayer.net/22163085-Cpu-scheduling-overview-cpu-scheduling-sgg7-8-9-chapter-5-basic-concepts-cpu-scheduler-scheduling-criteria-optimization-criteria.html

 

CPU 스케쥴링은 무엇일까? CPU 스케쥴링은 한정된 자원으로 최대한의 효율을 내기 위해 사용하는 기법이다.

 

대부분의 경우 I/O 작업이나, 입력 장치, 출력 장치의 작업 수행이 이루어질 때, CPU는 아이들 상태에 놓이게 된다.

스케쥴링은 낭비되는 자원을 좀 더 효율적으로 사용하기 위해 쓰는 방법.

 

또한 단일 CPU의 경우, 한 가지의 일을 한번에 밖에 처리하지 못하지만 우리는 노래도 들으면서 웹서핑까지 동시에 할 수 있다. 이런일이 가능한 것은, 스케쥴링 덕분이다.

 

현재의 운영체제들은 이러한 이론을 기반으로 프로세스 스케줄링(Process Scheduling)을 적용하고 있다.

 

 

스케줄링 상태

---

스케줄링은 크게 5가지의 상태를 가진다.

 

• 생성(create) : 프로세스가 생성되는 중이다.
• 실행(running) : 프로세스가 프로세서를 차지하여 명령어들이 실행되고 있다.
• 준비(ready) : 프로세스가 프로세서를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리고 있다.
• 대기(waiting) : 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말한다.
• 종료(terminated) : 프로세스의 실행이 종료되었다.

 

이러한 스케줄링은 4가지의 상태 변화를 갖게 되는데,

 

1. 프로세스가 실행 상태(running)에서 대기 상태(waiting)으로 전환될 때
2. 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전환될 때
3. 프로세스가 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때
4. 프로세스가 종료되었을 때(terminated)

 

여기서 1번과 4번은 프로세스 스스로가 자원을 사용하고 반환하므로 비선점 스케줄링이다.

2번과 3번은 운영체제에서 프로세스를 바꾸고, 제어할 수 있다 이 경우는 선점 스케줄링이다.

 

 

 

비선점 스케줄링 (non-preemptive Scheduling)과 선점 스케줄링 (Preemptive Scheduling)

---

출처 : https://medium.com/jungletronics/rtos-we-are-all-preemptive-scheduler-c2de5f050601

 

먼저 비선점 스케줄링을 살펴보자.

비선점 스케줄링은 어떤 프로세스가 자원을 사용할 때, 자발적으로 자원의 사용을 끊기 전까지 보장한다.

즉, 어느 한 프로세스의 작업이 전부 끝나면, 자원을 넘기게 된다.

 

이러한 비선점 스케줄링의 특징으로는,

---

• 모든 프로세스에 대한 요구를 공정하게 처리할 수 있다.
• 일괄처리방식에 적합하다.
• 중요한 짧은 작업이 중요하지 않은 긴 작업을 기다리는 등의 비효율이 발생한다.
• 응답 시간 예측이 용이하다.

 

특징답게, 리얼 타임(Real-Time) 방식에는 맞지 않아보인다.

우선순위가 없기 때문에, 중요한 작업의 빠릿한 작업 속도를 보장하지 못한다.

 

이러한 비선점 스케줄링을 위한 알고리즘으로는 FCFS, SJF, HRN 등이 있다.

 

---

FCFS

FCFS(First Come First Serve) 스케줄링 : CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는 방법이다.

대표적인 FIFO(First In First Out) 알고리즘이며, 이는 큐(Queue)라는 자료구조로 간단히 구현이 가능하다.

 

 

SJF(Shortest Job First Scheduling) 스케줄링 : CPU Burst(cpu 사용 시간)이 가장 짧은 프로세스 순으로 먼저 끝내는 방식.

이 방법은 선점형 방법과 비선점형 방법이 있다. 대신 둘 다 실제 컴퓨터 스케줄링으로 적용하기 어렵다는 점이 있는데, 이는 어떻게 CPU Burst(cpu 사용 시간)을 알아낼 수 있는지 계산하기 어렵기 때문이다.

---

 

그럼 이번에는 선점 스케줄링(Preemptive Scheduling)을 알아보자.

 

선점 스케줄링은 이미 자원을 할당받아 실행중인 프로세스를 중지하고, 다른 프로세스로 넘기는 것이 가능하다.

왜 "선점"이냐면, 운영체제가 프로세스에 대한 제어권을 "선점" 하고 있다고 생각하면 편하다.

 

이러한 선점 스케줄링의 특징을 나열하자면,

---

• 우선순위가 높은 프로세스 위주로 빠르게 처리할 수 있다.
• 빠른 응답시간을 요구하는 대화식 시분할 시스템에 주로 사용된다.
• 선점 시간 배당을 위한 타이머 클럭이 필요하며, 선점으로 인한 많은 오버헤드를 초래한다.

선점 스케줄링은 선점을 어떻게 해야할 지에 대한 기준을 정하기 위해 따로 타이머가 필요하다.

선점 프로세스의 가장 큰 약점은 아마도 공유되는 자원에 대한 오류가 발생할 수 있다. 중간에 프로세스를 바꾸기 때문에 공유된 자원이 있을 경우, 올바른 계산을 하지 못하게 될 수도 있다.

 

실시간 시스템에서 쓰인다고 한다.

 

선점 스케줄링을 구현하기 위한 여러가지 알고리즘이 있는데, SRT, RR, 선점 우선순위, MLQ, MLFQ 등이 있다.

---

라운드 로빈(Round Robin)

 

라운드 로빈(Round Robin) 스케줄링 : 시분할 시스템에서 이용되며, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 특정 시간 단위로 자원을 할당하는 방법. 특정 시간 단위가 길어질 수록 FCFS와 점점 비슷해진다.

 

우선순위 스케줄링

 

 

우선순위 스케줄링 : 말 그대로 우선순위가 높은 프로세스부터 실행하는 스케줄링이다. 프로세스의 중요도를 기준으로 우선순위로 삼는다. 우선순위는 CPU Burst나, I/O 시간, 등등을 이용해 내부적으로 계산해 매긴다. 문제라면 우선순위가 낮은 프로세스는 Starvation(무한 대기) 상태에 빠질 수 있으며, 이를 위한 해결책으로는 시간이 지날수록 우선 순위를 높이는 Aging(에이징) 방법이 있다.

 

 

 

---

사진 출처 : cppsecrets.com/users/1108979711510497121461151049710464115111109971051219746101100117/Python-Priority-Scheduling-Preemptive-Algorithm-with-Same-Arrival-Time.php,

tutorialspoint.dev/computer-science/operating-systems/program-shortest-job-first-sjf-scheduling-set-1-non-preemptive,

www.geeksforgeeks.org%2Fprogram-for-fcfs-cpu-scheduling-set-1%2F&psig=AOvVaw0kY7bJArMJIRz1xtrGKQJD