스케쥴링 알고리즘(Schduling Algorithm)

FIFO(First In First Out) Scheduler

프로세스가 레디 큐에 진입하면 이 프로레스의 프로세스 제어블록(PCB)을 큐의 끝에 연결합니다.
CPU가 가용상태로 변경되면 레디 큐의 앞부분에 있는 프로세스에 할당됩니다. 동시에, 레디 큐에서 제거됩니다.

 

개념	준비 상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 방식입니다.
특징	1. 공평성 2. 중요한 작업이 덜 중요한 작업을 기다리는 상황이 있을 수 있다.
장점	구현 용이(Queue), 공평성 증가
단점	평균 응답 시간이 길다.
예시	Queue, 화장실 대기줄

 

 

SJF(Shortest Job First) Scheduler

CPU 점유시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식입니다.

 

개념	준비 상태 큐에 있는 프로세스들 중에 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 방식
특징	1. 짧은 평균 대기시간을 제공하는 방식 2. 실행시간이 긴 프로세스는 할당 순위가 계속 뒤로 미뤄져 무한 대기 현상(Starvation)이 발생할 수 있습니다.
장점	평균 대기시간 최소화, 시스템 내 포르세스 수 최소화, 메모리 절약
단점	무한 대기 현상(Starvation) 발생, 정확한 실행 시간을 알수 없습니다.

 

 

RR(Round-Robin) Scheduler

프로세스에게 각각 동일한 CPU 할당시간을 부여하여 CPU를 이용하게 합니다.

개념	할당시간(Time Quantum)동안만 실행한 후에, 실행이 완료되지 않은 경우 다음 프로세스에게 CPU를 넘기고, 레디 큐의 가장 뒤로 배치하는 방식입니다.
특징	시분할 시스템중 하나입니다.
장점	특정 프로세스의 자원 독점을 방지합니다.
단점	할당시간(Time Quantum)이 작은 경우, Context Switching Overhead가 큽니다.

 

 

기타 개념
PCB(Process Control Block) : PCB에 다음 프로세스 정보 저장합니다.
무한 대기 현상(Starvation) : 프로세스가 무한으로 실행할수 있는 기회가 없어 실행 하지 못하고 계속 대기하는 현상입니다.
할당시간(Time Quantum) : 해당 프로세스에게 주어진 시간입니다.
컨텍스트 스위칭(Context Switching) : CPU에서 실행할 프로세스를 변경하는 기술입니다.

Example of PCB