[OS] 프로세스 스케줄링 ( Process Scheduling )

 

[OS] 프로세스(Process)란 무엇일까?

[OS] PCB란 무엇일까?

 

 

지난 포스팅에서 프로세스와 PCB에 대해서 다루어 보았다. 

 

 

 

 

Disk에 있는 프로그램(Program)이 실행되면 CPU가 처리할 수 있도록 RAM에 메모리가 할당되는데, 그 단위가 프로세스(Process)이다. CPU는 RAM에 접근하여 명령어를 읽고 데이터를 저장하며 연산을 수행한다. 

 

그런데 여기에는 문제가 있다. 

 

CPU는 한정되어 있지만 처리할 프로세스는 많다.

RAM은 한정되어 있지만 처리할 프로세스는 많다. 

 

한정된 자원으로 다양한 프로세스가 병렬적으로 처리되려면  스케줄링(Scheduling)이 필요하다. 

 

 

OS는 PCB로 프로세스를 제어한다.

 

 

 

 

준비큐는 처리기에 할당이 될 준비가 되어있는 프로세스들이 위치하는 큐이다. 프로세스가 CPU를 할당받았느냐, 준비큐에 대기하고 있느냐, RAM 메모리를 할당받았느냐, Disk에서 대기하고 있느냐에 따라 프로세스 상태는 달라진다. 프로세스의 상태에 따라 적용되는 스케줄링과 스케줄러가 달라지므로, 우선 프로세스 상태에 대해서 살펴보자.

 

 

 

프로세스 상태

 

 

 

 

 

준비큐에 들어있는 프로세스는 모두 RAM에 메모리를 할당받은 상태이다. 이를 '준비상태'라 부른다. 커널메모리에 PCB는 생성되었지만 RAM 할당이 승인되지 않아 준비큐에 들어가 있지 못하는 프로세스도 있다. 이를 '생성상태'라 부른다. 처리기를 할당받아 프로세스를 처리하다가 I/O가 발생하여 인터럽트된 프로세스도 있다. 이를 '블록상태'라 부른다.

 

 

 

 

 

블록상태인 프로세스는 블록큐에서 대기한다. I/O가 끝나는 이벤트가 발생하면 다시 준비큐에 들어가 처리기 할당을 기다린다.  그런데 만약 I/O가 길어진다면 블록상태에 있는 프로세스는 점점 증가한다. 블록상태는 RAM을 차지하고 있기에 새로운 프로세스가 RAM을 할당받지 못한다. 새로운 프로세스가 처리기를 할당받지 못하면 처리기는 유휴상태(idle)에 빠지고 효율이 떨어진다. 그러므로 블록상태에 있는 프로세스의 RAM 할당을 해제하므로써 RAM 메모리의 공간을 확보하는데, 이때의 상태를 '보류상태'라 부른다. 프로세스 보류는 프로세스의 일부나 전체를 Disk로 옮기는 스와핑(swapping)이라는 기술로 구현된다.

 

정리하면,

 

'생성상태'와 '보류상태'인 경우 RAM을 할당받지 못하고 Disk에서 대기한다. '준비상태'인 프로세스는 RAM메모리를 할당받아 언제든 처리기 할당을 받을 준비가 되어 있고 '블록상태'인 프로세스는 I/O 같은 이벤트가 끝나는대로 다시 준비큐에 들어갈 수 있는 상태이다.  이와 같이, 수많은 프로세스를 한정된 CPU, RAM 자원으로 처리하기 위해, 프로세스에는 다양한 상태가 존재한다. 다양한 상태는 일종의 '플래그'로 동작하여, OS가 프로세스의 상태를 식별하고 스케줄링하는데 사용된다.

 

 

스케줄러(Scheduler)의 종류

 

OS에는 스케줄링을 담당하는 스케줄러로 크게 3가지가 있다. 

 

1) 단기스케줄러 ( CPU 스케줄러 ) : 준비큐에서 대기하는 프로세스에게 CPU를 할당한다. 

2) 장기스케줄러 ( JOB 스케줄러 ) : 디스크에서 대기중인 프로세스에게 RAM 메모리를 할당한다. 

3) 중기스케줄러 ( Swapper ) : 스와핑(Swapping)으로 프로세스를 보류하여 메모리 공간을 확보한다.

 

 

스케줄링 정책

 

단기 스케줄러( CPU 스케줄러 )가 준비큐에 들어있는 프로세스에게 어떻게 CPU를 할당하는지 살펴보자. 

 

FCFS(First Come First Served)

 

준비큐에 먼저 들어온 프로세스부터 처리한다. 커널에 의한 인터럽트가 없는 이상 처리가 완료될 때까지 CPU를 반환하지 않는다.  FCFS 방식은 먼저 들어온 프로세스의 CPU Burst Time이 길면 준비큐에서 대기하고 있는 프로세스는 계속 대기할 수 밖에 없다. 

 

SJF (Shortest Job First)

 

준비큐에서 CPU Burst Time, 즉 CPU 사용시간이 가장 적은 프로세스에게 먼저 CPU를 할당하는 방식이다. FCFS의 단점을 보완하지만 역으로 CPU Burst Time이 긴 프로세스는 CPU를 할당받지 못할 수 있다. 

 

SRTF(Shortest Remaining Time First)

 

전체 CPU Burst Time이 아닌 잔여 CPU Burst Time으로 스케줄링 하는 방식이다. 또한 선점형이어서 잔여시간이 짧은 프로세스가 준비큐로 들어오면,  다른 프로세스가 사용중인 CPU를 선점할 수 있다.  이런 방식은 SJF보다 더 세밀하게 CPU BurstTime을 비교하므로 효율을 극대화할 수 있지만, CPU Burst Time이 긴 프로세스는 CPU를 할당받지 못하니 기아상태(Starvation)에 빠질 수 있다. 

 

Priority Scheduling

 

CPU 사용시간이 아닌 정수로 표현된 우선순위로 CPU를 할당하는 방식이다. 우선순위가 높은 프로세스가 준비큐에 들어오면 CPU를 선점하는 선점형 방식이 있고 준비큐의 가장 앞부분에 위치시키는 비선점형 방식이 있다. 그러나 이또한 우선순위가 낮으면 CPU를 할당 받지 못하는 기아상태(starvation)에 빠질 수 있다. 기아상태에 빠지는 경우를 방지하기 위해, 대기상태가 길어진 프로세스의 우선순위를 높히는 aging을 할 수 있다. 

 

Round Robin

 

가장 공정한 스케줄링 방식이다. 준비큐에 대기하고 있는 프로세스에게 모두 동일한 CPU 할당 시간을 부여한다. 부여된 할당시간을 모두 소모하면 준비큐 가장 뒤로 들어가 대기한다. PCB에 CPU 사용기록을 저장할 수 있으므로 언제든 대기하다가 다시 CPU를 사용할 수 있다. 가장 현대적인 스케줄링 방식이지만 CPU 할당시간이 커지면 FCFS랑 동일해지고 CPU 할당시간이 적으면 컨텍스트 스위칭이 자주  일어나 오버헤드가 증가할 수 있다. 

 

 

---

 

 

 

참고자료 

 

https://search.shopping.naver.com/book/catalog/32504635026

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/OS#%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%94