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

스케줄링의 목적

프로세스 스케줄링이 왜 필요한가?

우리가 사용하는 대부분의 시스템은 하나의 프로세스만을 가지고 있지 않습니다. 여러 개의 프로세스가 시스템 내 존재하는 다중 프로그래밍(Multi-Programming) 환경입니다.

따라서 자원을 나누어 사용하기 위해서 할당 할 프로세스를 선택해야 합니다. 즉 자원을 할당 할 프로세스를 선택하는 것을 스케줄링이라고 얘기할 수 있습니다.

 

※ 자원을 관리하는 방법

시간 분할 (Time Sharing) 관리 : 하나의 자원을 여러 스레드들이 번갈아 가며 사용 (프로세서 스케줄링)

공간 분할 (Space Sharing) 관리 : 하나의 자원을 분할하여 동시에 사용 (메모리 분할)

 

다시 한번 스케줄링의 목적을 정리하면, 시스템의 성능 향상을 위해서 입니다.

이러한 시스템의 성능을 나타내는 지표는 다음과 같고, 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택합니다.

• 응답시간(Response Time) : 작업 요청으로부터 응답을 받을 때까지의 시간 (대화형, 실시간)
• 작업 처리량(Throughput) : 단위 시간 동안 완료된 작업의 수 (일괄 처리)
• 자원 활용도(Resource Utilization) : 주어진 시간 동안 자원이 활용된 시간 (비싼 장비)

 

스케줄링의 기준

스케줄링 기법이 고려하는 항목들은 다음과 같습니다.

• 프로세스의 특성 : I/O-bounded or Compute-bounded
• 시스템 특성 : Batch System or Interactive System
• 프로세스의 긴급성 : Real Time or Non-Real Time
• 프로세스의 우선순위
• 프로세스 총 실행시간

 

스케줄링의 단계

장기 스케줄링(Job Scheduling)

커널에 등록할 작업(Job)을 결정하는 역할

커널 내에 프로세스 수를 조절(다중 프로그래밍 정도를 조절)

중기 스케줄링(Memory Scheduling)

메모리 할당을 결정하는 역할

단기 스케줄링(CPU Scheduling)

프로세서(CPU)를 할당할 프로세스를 결정하는 역할

가장 빈번하게 발생하며, 매우 빨아야 함

 

프로세스 상태 변화와 스케줄링의 단계

 

 

스케줄링 알고리즘

FCFS(First-Come-First-Service)

먼저 도착한 프로세스를 먼저 처리하는 방식

무조건 도착한 순서대로 프로세스를 처리해야 하므로 Convoy Effect가 발생할 수 있음

RR(Round-Robin)

자원 사용 제한 시간(Time Quantum)을 두고 먼저 도착한 순서대로 프로세스를 처리하는 방식

프로세스는 할당된 시간이 지나면 자원을 반납해야함 (특정 프로세스의 독점 방지)

따라서 Context Switching Overhead가 큼, 시분할, 실시간 시스템에 적합

Time Quantum의 크기 설정이 성능의 중요한 역할을 함

SPN(Shortest-Process-Next)

실행시간(CPU 점유시간)이 짧은 순서대로 프로세스를 처리하는 방식

평균 대기 시간을 최소화하고, 많은 프로세스들에게 빠른 응답 시간을 제공할 수 있음

그러나 실행시간이 긴 프로세스는 계속 자원 할당을 받지 못해 기아(Starvation) 현상이 발생

SRTN(Shortest-Remaining-Time-Next)

비선점 스케줄링 방식인 SPN을 선점 형태로 변경한 방식

기본적으로 SPN과 비슷하지만 중요한 프로세스가 있으면 실행시간이 길어도 먼저 실행 가능

잔여 실행시간을 계속 추적하는 과정에서 Context Switching Overhead가 발생

구현 및 사용이 비현실적으로 어려움

HRN(High-Response-ratio-Next)

SPN에서 기아 현상이 발생하는 단점을 보완한 방식으로 대기 시간과 서비스 시간을 이용

우선순위 = (대기시간 + 서비스시간) / 서비스시간 이라는 공식의 에이징 기법을 사용

우선순위가 높은 순서대로 프로세스를 처리하는 방식

실행시간 예측이 필요하므로 Overhead 발생

MLQ(Multi-Level-Queue)

작업별 별도의 ready queue를 두어 프로세스를 처리하는 방식 (최초의 배정된 큐를 벗어날 수 없고, 각각의 큐에 자신만의 스케줄링 기법을 사용함)

큐 사이에는 우선 순위 기반의 스케줄링을 사용

우선순위가 높은 큐는 응답시간이 빠름

그러나 여러 개의 큐를 관리해야 하므로 스케줄링 overhead가 발생할 수 있음

우선순위가 낮은 큐는 기아 현상이 발생할 수 있음

MFQ(Multi-Level-Feedback-Queue)

프로세스의 큐간 이동이 허용된 MLQ

각 큐마다 시간 할당량을 다르게 배정

I/O-bounded 프로세스들을 상위 단계의 큐로, Compute-bounded 프로세스를 하위 단계의 큐로 이동시켜 우선순위를 높임

대기 시간이 지정된 시간을 초과한 프로세스들을 에이징 기법을 통해 상위 단계의 큐로 이동

대부분의 상용 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용

(프로세스의 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택)

 

 

 

참고

www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

[Course] Operating System (CPA310) - 운영체제 강의

junsday.tistory.com/29?category=897242

스케줄링 기법(Scheduling Method)