프로세스 스케줄링

소밍·2023년 7월 26일

CS 프로세스 스케줄링

1. Process Scheduling

운영체제에서 CPU를 사용할 수 있는 프로세스를 선택하고, CPU를 할당하는 작업
우선순위, 작업량 등을 고려하여 프로세스를 효율적으로 배치하여
운영체제는 CPU를 효율적으로 사용하며 시스템 전반적인 성능을 향상시킬 수 있음.
때문에 프로세스 스케줄링은 멀티 태스킹 작업을 만들어내는 데에 있어서 핵심적인 부분.

1-1. 스케줄링 장점

CPU의 활용 극대화
프로세스 처리율(시간 당 작업량) 늘릴 수 있음
프로세스는 필요한 자원을 할당받기 위해 큐에 대기.
그 큐에 있는 프로세스를 어떻게 스케쥴링하는지가 프로세스 스케줄링 알고리즘

1-2. 관련 용어

CPU 이용률 (CPU utilization)
- CPU를 얼마나 바쁘게 하는가. 높을수록 좋음. [단위 : %]
처리율 (Throughput)
- 단위 시간당 얼마나 많은 프로세스들이 완료되는가. 클 수록 좋음. [단위 : 개]
대기시간 (Waiting time)
- 프로세스가 대기 큐에서 기다리는 시간의 합. 짧을수록 좋음. [단위 : 초]
반환시간 or 소요시간 (Turnaround time)
- 작업을 완료하는데 소요되는 전체 시간으로 대기 시간과 실행 시간을 모두 포함 [단위 : 초]
- 메모리 접근 시간, 대기 큐에서의 대기 시간, CPU에서의 실행 시간, I/O 시간 등의 합으로 계산. 짧을수록 좋음.
반응시간 (Response time)
- 프로세스가 요청된 후 첫 번째 응답을 받기까지 걸리는 시간.
- 주로 상호교환 시스템(interactive system)에서 사용. 짧을수록 좋음. [단위 : 초]
선점방식
- 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 회수할 수 있는 방식
- CPU 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영 가능
- 잦은 문맥 교환으로 overhead가 커질 수 있음.
비선점 방식
- 프로세스가 자원을 할당 받았을 경우, 자원을 스스로 반납할 때까지 계속 그 자원을 사용하도록 허용하는 정책
- 필요한 context switching만 일어나므로 overhead가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 남.
실행 시간(Burst Time)
- 프로세스가 실행을 완료하는 데 필요한 CPU 시간

✦ context switching (문맥교환)

하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해,
이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업

✦ overhead (오버헤드)

어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리
A라는 처리를 단순하게 실행한다면 10초 걸리는데
안전성을 고려하고 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초

1-3. Process Scheduling 알고리즘

1-3-1. FCFS(First-Come, First-Served)

CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는 스케줄링 방법
비선점 방식 스케줄링이므로 대화형 작업에는 부적합
convoy effect가 발생할 수 있음

✦ convoy effect

커다란 한 프로세스가 끝날때까지 다른 모든 프로세스들이 계속 기다리는 현상

convoy effect는 CPU와 장치들의 사용률을 낮추기 때문에 지양.

1-3-2. SJF(Shortest-Job-First)

Burst Time이 작은 프로세스부터 먼저 스케줄링 하는 알고리즘
비선점형과 선점형 존재
SJF 스케줄링으로 평균 대기 시간 줄일 수 있음
다음 프로세스의 Burst Time을 예측하는 것이 어렵다는 문제가 존재
프로세스의 Burst Time이 길면 계속해서 후순위가 됨 -> 기아 현상(starvation)
convoy effect를 최소화할 수 있음

✦ 기아 현상 (starvation)

우선순위 기준에 따라 자원을 할당받는 상황에서
우선순위가 낮은 자료들이 계속해서 후순위가 되며 자원을 할당받지 못하는 현상

비선점형 SJF

비선점형에서는 실행되고 있는 프로세스는 끝까지 실행

선점형 SJF (SRTF ; Shortest Remaining Time First)

현재 실행되고 있는 프로세스의 남은 Burst time보다 도착한 다음 프로세스의 Burst time이 더 짧다면 다음 프로세스를 실행하도록 바꿈.

1-3-3. Priority

우선순위 높은 프로세스에 CPU 할당.
우선순위가 동일하다면 FCFS 기법을 이용하여 처리.
낮은 우선순위 프로세스가 후순위로 가기 때문에 기아문제 발생 가능
기아 문제 해결 위해 aging 기법(시간 지날수록 프로세스 우선순위 높이는 방식) 사용 가능

✦ aging

자원이 할당되기를 기다린 시간에 비례하여 우선순위를 부여함으로써 기아 현상을 방지하는 기법

1-3-4. RR(Round-Robin)

프로세스들 간에 우선순위를 두지 않고, 순서대로 시간단위로 프로세스에 자원 할당.
정해진 시간 할당량(또는 시간 간격)에 의해 실행을 제한
할당된 시간 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU를 독점하지 않고 공평하게 이용
대화형 시스템에서 사용되는 선점 스케줄링 방식
시간 할당량이 너무 크면 FCFS 스케줄링과 같아짐
시간 할당량이 너무 작으면 context switching에 따른 overhead가 크게 증가함
보통 시간 단위는 10 ms ~ 100 ms

✦ 시간 단위(Time Quantum)

프로세스에게 할당되는 최대 CPU 시간

1-3-5. Multilevel Queue

single queue에서는 모든 프로세서의 우선순위를 찾아야 하기 때문에 시간 복잡도가 O(n)
Multilevel Queue를 도입하면 우선순위가 높은 queue에서 먼저 schedule을 할 수 있기 때문에 시간 복잡도를 1로 줄일 수 있음.
특징에 따라 다른 알고리즘을 사용할 수 있다는 점이 가장 큰 장점
우선순위가 낮은 작업은 CPU 할당을 가지지 못하는 기아 현상 발생 가능
Time Slice를 통해 각 큐의 CPU time을 적절하게 할당해야 함
(foreground - RR에 80%, background - FCFS에 20%)

foreground queue	background queue
- interactive - cpu burst가 짧은 queue - 우선 순위 높음 - RR방식	- batch 등 긴 시간을 필요로 하는 작업 - 우선 순위 낮음 - FCFS 방식