[OS] 스케줄러

Choi Sang Rok·2022년 7월 19일

FCFS OS Operation System RR SJF scheduler 스케줄러 운영체제

Nexters 21기 CS 스터디의 첫 번째 주제로 이어서 스케줄러에 대해 포스팅하게 되었습니다. 스케줄러를 왜 사용하는지와 스케줄링 알고리즘의 종류에 대해 알아봅시다.

📕스케줄러

어떤 프로세스에게 자원을 할당할지 결정하는 운영체제 커널의 모듈

다중 프로그래밍(Multi-programming)에서는, CPU의 이용을 극대화하기 위해 항상 어떤 프로세스가 실행될 수 있도록 하고, 시분할(Time-Shared)은 프로세스 간 문맥 전환이 빠르게 이루어질 수 있도록 해야 합니다.

운영체제는 스케줄러를 통해 CPU를 사용하려고 하는 프로세스 사이의 우선 순위를 관리하고 이것을 스케줄링 이라고 부릅니다.

프로세스는 일생 동안 다양한 스케줄링 큐 사이를 이동하는데, 프로세스를 스케줄링하기 위한 Queue에는 세 가지 종류가 존재합니다.

작업 큐(Job Queue) : 시스템 안의 모든 프로세스들로 구성
준비 큐(ready queue) : 메인 메모리에 존재하며, 준비 완료 상태에서 실행을 대기하는 프로세스들로 구성
장치 대기 큐(device queue) : 특정 입/출력장치를 대기하는 프로세스들의 리스트들로 구성

스케줄러의 종류

단기 스케줄러(CPU Scheduler) : CPU와 메모리 사이를 담당하는 스케줄러
- 실행 준비가 완료되어 준비 큐에 있는(메모리에 존재하는) 프로세스들 중에서 선택하여 CPU를 할당
- 단기 스케줄러는 자주 수행되므로 빨라야 함
중기 스케줄러(Swapper) : 메모리에서 CPU를 점유하기 위해 경쟁하는 프로세스를 디스크로 보내는 스케줄러
- 시분할 시스템(Time-shared)과 같은일부 운영체제에서 도입
- 다중 프로그래밍의 정도를 완화
- 차후 다시 프로세스를 메모리로 불러와서 중단되었던 지점에서 실행을 재개하는 스와핑(swapping) 기능을 함
장기 스케줄러(Job Scheduler) : 메모리와 디스크 사이를 담당하는 스케줄러
- 디스크 상의 프로세스를 선택하여 준비 큐로 저장(메모리로 적재)
- 다중 프로그래밍의 정도(메모리에 있는 프로세스의 수) 제어
- 수십 초 내지 수 분 단위로 호출되기 때문에, 속도가 느릴 수 있음

✒스케줄링

스케줄러가 메모리 내의 프로세스에게 CPU를 할당하는 것

스케줄링의 목적

CPU 이용률 최대화 (Max CPU utilization)
처리량 최대화 (Max throughput)
총 처리 시간 최소화 (Min turnaround time)
대기 시간 최소화 (Min waiting time)
응답 시간 최소화 (Min response time)

CPU의 스케줄링 결정은 다음 네 가지 상황 하에 발생합니다.

실행 상태 → 대기 상태(I/O 요청이나 자식 프로세스들 중의 하나가 종료되기를 기다리기 위해 wait를 호출할 때
실행 상태 → 준비 완료 상태(인터럽트가 발생할 때)
대기 상태 → 준비 완료 상태(I/O의 종료 시)
실행 상태 → 종료 상태

스케줄링은 비 선점 스케줄링과, 선점 스케줄링으로 나뉘어 집니다.

비 선점 스케줄링

한 프로세스가 CPU를 할당 받으면 다른 프로세스에 CPU 할당이 불가능합니다.

위 스케줄링 상황 중 1번과 2번인 경우, 현재 실행중인 프로세스도 없는 상황에서 준비 큐에 존재하는 프로세스를 실행시켜야 하므로 협조적인 성격을 가집니다.
스케줄러의 작업량이 적고 문맥 교환 오버헤드가 작지만, 처리율이 떨어집니다.
일괄 작업 방식 스케줄러에 사용됩니다.(FCFS, SJF, Priority)

선점 스케줄링

현재 실행중인 프로세스를 밀어내고 더 우선 순위가 높은 프로세스를 스케줄링 합니다.

문맥 교환 오버헤드가 많음
공유 메모리를 사용할 경우, 이전 프로세스 데이터 내용을 선점된 프로세스가 영향을 줄 수 있으므로 조정에 필요한 비용을 유발합니다.
커널 프로세스 선점으로 생기는 경쟁을 통해 커널의 데이터 보안 문제가 발생합니다.
시분할 방식 스케줄러에 사용됩니다.(RR, SRT, 다단계 큐, 다단계 피드백 큐)

⚙스케줄링 알고리즘

다음 문제를 통해 FCFS, SJF, SRTF, Pritority Scheduling, RR을 이해해 보겠습니다.

다음과 같은 상황에서, 각 스케줄링 알고리즘에 대해 Gantt 차트를 그려 비교해 보겠습니다.

평균 대기시간 = 대기시간/프로세스 개수

대기시간 = 처리시간 - 버스트 시간

처리 시간 = 완료 시간 - 도착 시간

FCFS

먼저 도착한 프로세스에게 서비스 해주는 방식
비선점형 스케줄링
CPU를 할당받으면 버스트가 완료되기 전까지 CPU를 반환하지 않음

문제점

convoy effect : 버스트 시간이 짧은 프로세스들이 늦게오면 CPU를 양도 받기를 기다려야해서 CPU와 장치 이용률이 저하됨

SJF

버스트가 가장 짧은 프로세스에게 먼저 CPU를 할당
위의 경우는 비선점형의 경우로, 자신의 CPU 버스트를 끝내기 전에는 선점되지 않음
선점형의 경우에는 남은 시간 보다도 더 짧은 CPU 버스트가 도착하면 그 프로세스가 선점됨(SRTF, Shortest-Remaining-Time-First, SRTF)

문제점