스케줄러 (Scheduler)

작업을 수행하기 위해 자원을 할당하는 작업을 스케줄링 이라고 하며 스케줄러 에 의해 수행된다

스케줄링은 동시성을 구현하기 위해 나온 개념이다. 하나의 코어를 가지고 있는 CPU 가 여러 작업을 번갈아 가며 실행하기 위해 실행 자원을 첫 번째 작업에게 부여 했다가, 다음 작업에게 자원을 할당 하는 것을 반복 함으로서 사람으로 하여금 '동시에' 실행 시키는 것으로 보이도록 하기 위함이다

스케줄러의 개념은 여러 용도로 사용되곤 한다

오늘 공부 할 개념은 여러 스케줄링 알고리즘을 공부 할 것이다

스케줄링 알고리즘

스케줄링 알고리즘에는 여러가지가 존재하며 각각의 구조적 장점들이 존재한다

• 선착순 스케줄링: FIFO(First In First Out) / FCFS(First Come, First Served)
• EDF(Earliest deadline first scheduling)
• 최단 시간 스케줄링: Shortest remaining time first
• 고정된 우선 순위 선제 스케줄링: Fixed priority pre-emptive scheduling
• 라운드 로빈 스케줄링: Round-robin scheduling

선착순 (FIFO)

가장 간단한 스케줄링 알고리즘

단순히, 준비된 대기열에 도착하는 순서대로 프로세스를 대기열에 넣는다

• Quere 개념을 기반으로 동작한다
• 컨텍스트 스위칭은 프로세스 종료 시에만 발생한다
  프로세스 대기열의 재구성이 필요 없으므로 재구성에 대한 오버헤드가 없음
• 긴 프로세스가 리소스를 과점유 할 가능성이 있다
• 처리 시간, 대기 시간 및 응답 시간은 도착 순서에 따라 다를 수 있다
• 우선순위가 존재하지 않으므로 최초 실행 뒤 완료까지의 시간이 길 수 있다

EDF (Earliest deadline first scheduling)

프로세스들이 각각 고유한 마감시간(데드라인) 을 가지고 있고, 마감 기한이 가장 빠른 프로세스 부터 먼저 처리 되는 알고리즘

가장 높은 CPU 사용률을 가진 알고리즘 이지만, 실제 환경에서는 프로세스의 도착 패턴, 시스템 오버헤드, 작업간 종속성 등 여러 요인으로 인해 최적화가 힘들 수 있다.

• 각 프로세스에는 데드라인 이 있다.
  데드라인: 프로세스가 완료되어야 하는 시간
• 모든 프로세스가 준비 상태로 들어오면 스케줄러는 데드라인이 가장 빠른 작업을 먼저 선택한다
• 데드라인이 동일한 프로세스가 여러 개 있는 경우, 스케줄러는 그 중 하나를 임의로 선택한다
• 새로운 프로세스가 도착했으나, 그 작업이 현재 실행중인 프로세스의 데드라인 보다 빠를 경우, 스케줄러는 현재 프로세스를 중단하고 새로운 프로세스를 시작한다

고정된 우선 순위 선제 스케줄링
(FPPS: Fixed priority pre-emptive scheduling)

모든 프로세스에 고정된 우선순위를 할당한다

스케줄러는 우선순위에 따라 준비된 대기열에서 프로세스를 정렬하고, 우선순위가 낮은 프로세스는 들어오는 우선 순위가 높은 프로세스에 의해 중단될 수 있다

• 순위 수가 제한되어 있다면 각 우선순위에 대해 하나씩 FIFO 대기열 모음으로 묶일 수 있다. 이 때 우선순위가 낮은 대기열의 프로세스는 우선순위가 높은 대기열이 비어있을 때 만 선택된다.

라운드 로빈 스케줄링(RR: Round-robin scheduling)

프로세스당 고정된 시간 단위를 할당하고 프로세스들의 컨텍스트 스위칭을 반복하며 순환한다. 프로세스가 시간 내에 완료되면 종료된다

• 컨텍스트 스위칭이 빈번히 일어나, 광범위한 오버헤드가 생긴다.
• 대기 시간이 길기 때문에 순수한 RR 에서는 데드라인이 거의 충족되지 않을 수 있다.