단일처리 CPU 스케줄링 개념과 종류 (OS Scheduling 1)

 스케줄링

 다중 프로세스 처리를 위해 꼭 필요한 기본 개념입니다. 여기서는 단일처리의 경우 스케줄링 개념을 설명합니다. 스케줄링은 CPU를 프로세스들이 번갈아면서 좀 더 효율적으로 동작하게끔 합니다. 

 스케줄링의 목적은 CPU의 이용을 최대화 하는데 있습니다. 코어는 하나의 프로세스만 처리하는 것이 당연한 일입니다. (CMT 제외 ,CMT 칩 수준 스레딩 : 코어당 여러개의 스레드를 두어 메모리 스톨로 인한 이용률 저하를 막는데 있음) 그런데 프로세스가 I/O 요청으로 대기하고 있다면 CPU는 그저 쉬게 됩니다. 이는 성능에 있어서, 효율에 있어서 좋지 않습니다. 다른 밀려있는 수많은 프로세스를 수행하지 못하고 낭비됩니다. 때문에 스케줄링 작업을 하여 이를 방지합니다. 

 

CPU, I/O 버스트

 CPU 스케줄링에 있어서 기본적으로 알아야 합니다. 프로세스의 처리는 CPU에서의 처리와 I/O 대기로 이루어집니다. 이런 과정이 번갈아가며 일어나며 CPU에서의 처리를 CPU Burst (이하 CPU 버스트) I/O Burst라 합니다. 

 

디스패쳐 Dispatcher

 스케줄링 기능에 포함된 요소 중 하나입니다. CPU의 코어의 제어를 스케줄러가 선택한 프로세스에 주는 모듈입니다. 프로세스간 문맥을 교환해주거나 사용자 모드로 전환, 프로그램 재시작을 위해 적절한 위치로 이동하는 일을 합니다. 문맥 교환에 있어서 정지하고 다른 프로세스를 실행하는데 소요되는 시간을 디스패치 지연이라 합니다.

 

 

 

스케줄링 알고리즘

 스케줄링은 준비 큐에 프로세스를 어떻게 스케줄 할 것인가에 대한 것입니다. 코어에서는 모든 시간이 프로세서의 CPU 버스트들로 존재해야 합니다. 

 

선입선처리 스케줄링 FCFS (FIFO 스케줄링)

이 처리 알고리즘은 선입선출 큐로 되어 있습니다. 먼저 요청된 프로세스대로 처리하는 방식입니다. 이 스케줄링 방식은 구현이 쉽고 이해하기도 편리합니다. 그러나 평균 대기 시간이 길 수 도 있다는 것이 단점입니다. 무조건 긴것은 아니며 효율적으로 동작할 수도 있습니다. 또하나 단점으로 이 스케줄링의 경우 대화형 시스템에 적합하지 않습니다. 일정한 주기로 CPU를 점유해야하는 대화형 시스템의 경우 조건을 만족시켜주지 않기때문 입니다.

 

 최단 작업 우선 스케줄링 SJF

 작업이 최소인 작업을 우선 처리하는 알고리즘 입니다.

SJF 스케줄링

위 예 같은 경우 평균 대기시간이 (0+4+11)/3=5 입니다. sjf의 경우 최소의 대기시간을 가지게 됩니다. SJF 알고리즘은 최적이긴 하나 사실상 비현실적입니다. CPU 버스트의 길이를 정확히 알 수 없기 때문에 이전 CPU 버스트 기록에 의존하게 됩니다. $t_{n}$을 $n$번째burst 길이라 하고, $t_{n+1}$은 다음 CPU 버스트 길이를 $τ_{n+1}$를 다음 버스트 길이라 하고 0≤α≤1인 α일 때

$τ_{n+1} = αt_{n+1} + (1-α)τ_{n}$

α=0일때 이전에 대한 것은 영향이 없다는 것이고 1이라면 최근의 CPU 버스트 기록에 매우 의존적이라는 것입니다.

 

라운드 로빈 스케줄링 Round Robin (RR) Scheduling

 이 알고리즘은 선점형 스케줄링 알고리즘입니다. 시간 할당량이라는 일정 작은 단위의 시간을 정의합니다. 원형 큐로 돌면서 큐는 선입선출 형으로 동작합니다. CPU 버스트가 시간 할당량보다 적다면 다음 준비된 프로세스가 실행됩니다. 그러나 CPU 버스트가 시간 할당량보다 긴 경우, 인터럽트가 발생되고 현재 처리되던 프로세스는 다시 준비큐로 들어간 뒤 다음 프로세스가 동작합니다.

RR 예

 라운드 로빈 스케줄링에서는 준비큐에 혼자 남아있는 것이 아닌 이상 같은 프로세스가 연속적으로 할당받지 않습니다. 이 기법은 시간 할당량에 큰 영향을 받습니다. 위와 같은 경우 시간 할당량이 5입니다. 최대 5이며 그전에 끝난다면 인터럽트를 발생시키고 다음 프로세스를 위한 문맥교환을 진행합니다. 시간할당량이 너무 크면 FIFO와 같은 구조가 되버리고 너무 작다면 문맥교환이 많아져 성능 저하가 발생합니다. 

 

다단계 피드백 큐 스케줄링

 다단계 피드백 큐 스케줄링은 라운드 로빈 스케줄링 아래 별도의 큐를 가지면서 큐들 사이를 이동하는 것을 허용합니다. 다단계 큐 스케줄링의 경우 큐들의 사이를 이동할 수 없으나 이 기법은 큐 사이 이동이 가능합니다. CPU 버스트의 길이가 길다면 비교적 낮은 우선 순위의 큐로 이동하고 I/O 중심 프로세스 혹은 대화형 프로세스는 높은 우선순위의 큐에 넣습니다. 

다단계 피드백 큐 스케줄링

 예를 들면 위 그림과 같습니다.

 

다단계 피드백 큐의 정의 요소

• 큐의 개수
• 높은 우선 순위 큐로 올리는 시기의 방법
• 큐의 결정
• 각 큐의 스케줄링 알고리즘
• 높은 우선 순위에서 강등의 시기

 이 스케줄링의 알고리즘은 가장 일반적입니다. 하지만 위와 같은 정의요소 정의에 복잡함 때문에 설계가 어렵습니다.

 

정리 

 위의 스케줄링 알고리즘들은 단일 처리의 경우입니다. 다중 처리를 위한 알고리즘은 위 뼈대에서 추가적으로 스케줄링 알고리즘이 더 적용됩니다. 가장 일반적으로는 다단계 피드백 큐가 가장 효율적이고 이상적이며 일반적입니다.