4. CPU Scheduling

우리는 앞서, 하나의 CPU가 하나의 프로세스에 밖에 할당 되지 못한다는 것을 알았다. 

위의 이야기만 들으면 CPU가 하나인 상태로 하나의 프로세스가 끝날 때까지 할당시켜준다하면... 아마 우리의 컴퓨터는 매우 느려질 것이다. 프로세스 하나에 모든 자원을 할당하게되면 비용도 어마무시하지만,

CPU가 기다리는 시간이 길어지고 다른 프로세스는 현재 프로세스가 작업을 끝날떄까지 다 기다려하는 등 오버헤드가 많다.( 득보다 실이 너무너무너무  크다.)

 

이러한 문제를 해결하려면 CPU가 쉴 새없이 움직이도록 할당될 프로세스를 스케쥴링해줘야한다!!

 

여러 프로세스를 빠른 속도로 CPU가 조금씩 할당하고 다시 본래작업하는 프로세스로 돌아와 CPU를 할당 받는다면!!!

사용자의 시각으로 봤을 때는 마치 동시다발적으로 프로레스들이 동작하는 것 처럼 보이게된다.

(지금 우리의 컴퓨터가 그러하다)  

그렇다면 어떻게 CPU에 할당될 프로세스들을 스케쥴링할까? 

 

CPU 스케줄링이란?

CPU 스케줄링 알고리즘에는 여러가지가 있다.

그중에도 대표적인 

1. 선입 선처리 스케줄링*FCFS,

2. 최단 작업 우선 스케줄링*SJFS,

3. 라운드 로빈스케줄링*RRS,

4. 최소 잔여 시간 우선 스케줄링*SRT, 

5. 우선순위 스케줄링*PS,

6. 다단계 큐 스케줄링*MQS,

7. 다단계 피드백 큐 스케줄링*MFQS을 다뤄보고자 한다. 

 

각 스케줄링 알고리즘의 경우 장단점이 존재하는데 일단 원리를 알아보고 살펴보자. 

 

 

1. 선입 선처리 스케줄링*FCFS

해당 스케줄링 방법은 가장 쉽고 간단한 CPU 스케줄링 알고리즘이다.

이러한 유형의 알고리즘에서는 CPU를 요청하는 프로세스가 CPU 할당을 먼저 받으며,

 스케줄링 방법은 FIFO 큐로 관리할 수 있다.

프로세스가 준비 대기열에 들어가면 PCB(프로세스 제어 블록)가 대기열의 테일과 연결된다.

따라서 CPU가 사용 가능해지면 대기열의 시작 부분에 있는 프로세스에 할당해야 한다.

 

FCFS 방법의 특징:
 비선제적, 선제적인 스케줄링 알고리즘을 제공한다.
작업은 항상 선착순으로 실행된다
구현하고 사용하기 쉽다.
그러나 FCFS는 성능이 떨어지고, 일반적인 대기 시간이 상당히 높다.

 

 

2. 최단 작업 우선 스케줄링*SJFS

한 형태로, 실행 시간이 가장 짧은 프로세스가 다음에 실행되도록 선택되어야 하는 스케줄링 알고리즘이다.

이 스케줄링 방법은 사전 설정 또는 비사전 설정이 될 수 있다.

실행 대기 중인 다른 프로세스의 평균 대기 시간을 크게 단축한다.

SJF 스케줄링의 특성
이 값은 완료해야 하는 시간 단위로 각 작업과 연결되며.
이 방법에서는 CPU를 사용할 수 있을 때 완료 시간이 가장 짧은 다음 프로세스 또는 작업이 먼저 실행된다.
비선점적인 정책으로 구현된다.
이 알고리즘 방법은 작업이 완료되기를 기다리는 것이 중요하지 않은 배치 유형 처리에 유용하다.
우선 실행해야 할 짧은 작업을 제공함으로써 작업 산출량을 개선하는데, 이는 대부분 반환 시간이 짧다.

 

 

3. 라운드 로빈스케줄링*RRS

라운드 로빈은 가장 오래되고 간단한 스케줄링 알고리즘이다. 

이 알고리즘의 이름은 각 사람이 차례로 동일한 몫의 무언가를 얻는 라운드 로빈 원칙에서 유래했다.

멀티태스킹 알고리즘 스케줄링에 주로 사용된다. 이 알고리즘 방법은 프로세스의 기아가 없는 실행을 돕는다.

라운드 로빈 스케줄링의 특성
라운드 로빈은 시계(Timer)로 구동되는 하이브리드 모델이다
처리할 특정 작업에 할당된 최소 시간 조각이어야 한다. 그러나 공정에 따라 다를 수 있다.
이것은 특정 시간 제한 내에 이벤트에 응답하는 실시간 시스템이다.

 

 

4. 최소 잔여 시간 우선 스케줄링*SRT

SRT의 전체 형태는 최단 남은 시간이다.

 SJF 선제 스케줄링이라고도 한다. 이 방법에서는 프로세스가 완료에 가장 가까운 태스크에 할당된다.

이 방법은 새로운 준비 상태 프로세스가 이전 프로세스의 완료를 보류하는 것을 방지한다.

SRT 스케줄링 방법의 특징:
이 방법은 짧은 작업을 우선적으로 지정해야 하는 배치 환경에서 대부분 적용된다.
이는 필요한 CPU 시간을 알 수 없는 공유 시스템에서 이를 구현하는 데 이상적인 방법이 아니다.
각 프로세스를 다음 CPU 버스트의 길이로 연결하기에, 따라서 운영 체제는 이러한 길이를 사용하므로 프로세스를 가능한 한 짧은 시간으로 예약하는 데 도움이 된다.

 

 

5. 우선순위 스케줄링*PS

우선순위 스케줄링은 우선순위를 기반으로 프로세스를 스케줄링하는 방법이다.

이 방법에서 스케줄러는 우선순위에 따라 작업할 태스크를 선택한다.

우선순위 스케줄링은 또한 OS가 우선순위 할당을 포함하도록 도와준다.

우선순위가 높은 프로세스가 먼저 수행되어야 하는 반면,

동일한 우선순위를 가진 작업은 라운드 로빈 또는 FCFS 기반으로 수행된다.

우선 순위는 메모리 요구 사항, 시간 요구 사항 등에 따라 결정할 수 있다.

 

 

6. 다단계 큐 스케줄링*MQS

이 알고리즘은 준비 대기열을 다양한 개별 대기열로 분리한다.

 이 방법에서 프로세스는 프로세스 우선 순위, 메모리 크기 등과 같은 프로세스의 특정 속성을 기반으로 큐에 할당된다.

그러나 작업을 예약하려면 다른 유형의 알고리즘을 사용해야 하므로 독립적인 스케줄링 OS 알고리즘이 아니다.

다중 레벨 대기열 스케줄링의 특징:
일부 특성이 있는 프로세스에 대해 여러 개의 대기열을 유지해야 한다.
모든 큐는 별도의 스케줄링 알고리즘을 가질 수 있다.
각 대기열에 대해 우선 순위가 지정된다.

 

 

7. 다단계 피드백 큐 스케줄링*MFQS

MLFQ(Multilevel Feedback Queue Scheduling) CPU 스케줄링은

 MLQ(Multilevel Queue) 스케줄링과 유사하지만 이 프로세스에서는 큐 간에 이동할 수 있다.

따라서 다단계 대기열 스케줄링보다 훨씬 효율적이다. 

다단계 피드백 큐 스케줄링의 특성:
다단계 대기열 스케줄링 알고리즘에서 프로세스는 시스템에 진입할 때 대기열에

 영구적으로 할당되며 프로세스는 대기열 사이를 이동할 수 없다. 
프로세스가 대기열에 영구적으로 할당되므로 이 설정은 스케줄링 오버헤드가 적다는 장점이 있다, 
그러나 다른 한편으로는 융통성이 없다는 단점이 있다.

 

다단계 피드백 큐 스케줄링의 장점:
기존의 MLQ보다 더 유연하다.
서로 다른 대기열 간에 서로 다른 프로세스를 이동할 수 있다.
우선 순위가 낮은 대기열을 너무 오래 기다리는 프로세스를 우선 순위가 높은 대기열로 이동하여 기아를 방지한다.

 

MLFQ(Multilevel Feedback Queue Scheduling)