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



📕스케줄러


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

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

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

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

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

스케줄러의 종류

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




✒스케줄링


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


스케줄링의 목적

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

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

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

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


비 선점 스케줄링

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

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

선점 스케줄링

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

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


⚙스케줄링 알고리즘

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

image

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

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

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

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



image
FCFS

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

문제점

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


image
SJF

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

문제점

  • starvation : 버스트 시간이 긴 프로세스들이 CPU를 무한히 대기하게 됨
  • SRTF의 경우새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없음


image

Priority Scheduling

  • 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당
  • 선점형의 경우 더 높은 우선순위의 프로세스가 도착하면 선점당함
  • 비선점형의 경우 더 높은 우선순위의 프로세스가 도착하면 준비 큐의 head로 넣어짐

문제점

  • starvation : 우선순위가 낮은 프로세스들이 CPU를 무한히 대기하게 됨

해결책

  • aging : 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
    image

Priority Scheduling

  • 시분할 시스템에 적합
  • 각 프로세스는 시간 할당량(time quantum) 또는 시간 조각(time slice)라는 작은 단위의 시간을 획득하고, 이 시간이 지나면 프로세스는 선점되고 준비완료 큐의 tail에 추가됨

장점

  • 준비 완료 큐에 n개의 프로세스가 있고 시간 할당량이 q이면, 각 프로세스는 자신의 다음 시간 할당량이 할당될 때 까지 (n-1) x q 시간 이상을 대기하지 않음. 즉 response time이 빨라짐

성능

  • 시간 할당량이 매우 크면, FCFS랑 같아짐
  • 시간 할당량이 작으면 문맥 전환으로 인한 오버헤드가 발생함(최소 문맥 교환 시간 10 마이크로초 미만) 보다 커야함
  • 적정한 시간 할당량을 부여하는 것이 과제
profile
android_developer

2개의 댓글

comment-user-thumbnail
2022년 7월 19일

상정 리 교수님이 시험문제로 냈던 내용이네요!~~

답글 달기
comment-user-thumbnail
2022년 10월 4일

버스트 블레이드 쎈가요?

답글 달기