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)
문제점
- starvation : 버스트 시간이 긴 프로세스들이 CPU를 무한히 대기하게 됨
- SRTF의 경우새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없음
Priority Scheduling
- 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당
- 선점형의 경우 더 높은 우선순위의 프로세스가 도착하면 선점당함
- 비선점형의 경우 더 높은 우선순위의 프로세스가 도착하면 준비 큐의 head로 넣어짐
문제점
- starvation : 우선순위가 낮은 프로세스들이 CPU를 무한히 대기하게 됨
해결책
- aging : 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
Priority Scheduling
- 시분할 시스템에 적합
- 각 프로세스는 시간 할당량(time quantum) 또는 시간 조각(time slice)라는 작은 단위의 시간을 획득하고, 이 시간이 지나면 프로세스는 선점되고 준비완료 큐의 tail에 추가됨
장점
- 준비 완료 큐에 n개의 프로세스가 있고 시간 할당량이 q이면, 각 프로세스는 자신의 다음 시간 할당량이 할당될 때 까지 (n-1) x q 시간 이상을 대기하지 않음. 즉 response time이 빨라짐
성능
- 시간 할당량이 매우 크면, FCFS랑 같아짐
- 시간 할당량이 작으면 문맥 전환으로 인한 오버헤드가 발생함(최소 문맥 교환 시간 10 마이크로초 미만) 보다 커야함
- 적정한 시간 할당량을 부여하는 것이 과제
상정 리 교수님이 시험문제로 냈던 내용이네요!~~