스케줄링 알고리즘

1. First-Come First-Served (FCFS)

CPU 할당을 먼저 요청한 프로세스가 먼저 CPU를 할당 받는 가장 간단한 스케줄링 알고리즘이다.
FCFS은 FIFO 큐를 사용해 간단하게 구현할 수 있다. -> PCB linked list

2. Shortest-Job-First (SJF)

SJF 알고리즘은 CPU 할당을 요청한 프로세스들 중 바로 다음 CPU burst 시간이 가장 작은 프로세스를 선택하는 스케줄링 알고리즘이다.
항상 실행 시간이 짧은 작업을 가장 먼저 실행하므로 평균 대기시간이 가장 짧아 효율적이다.
하지만 SJF 알고리즘은 굉장히 효율적이지만 실제 시스템에 사용될 수 없다. -> 프로세스의 다음 CPU burst 시간을 알아낼 수 없기 때문이다
CPU burst 시간이 긴 프로세스는 starvation이 일어날 수 있다.

3. Round-Robin (RR)

RR 알고리즘은 프로세스가 프로세서에서 동작할 수 있는 시간을 할당해준다. -> 이 시간을 time slice라고 부른다.
모든 프로세스가 공정하게 시간을 할당받기에 starvation이 발생하지 않는다.
time slice가 너무 짧으면 context switching이 자주 일어나 오버헤드가 발생한다.

4. Priority Scheduling

Priority Scheduling은 프로세스가 Ready Queue에 도착하면 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서(CPU)를 할당하는 방식이다.
각 프로세스의 상대적 중요도를 명시 할 수 있다.
높은 우선순위 프로세스가 계속 오면 우선순위가 낮은 프로세스는 Starvation 현상을 겪을 수 있다.

5. Multilevel Queue Scheduling

Multilevel Queue Scheduling은 준비 상태 큐를 여러 종류별, 단계별로 분할해두고 자신만의 독자적인 스케줄링 구현이 가능하다.
각 큐는 절대적인 우선순위를 가지며(여기선 시스템 프로세스가 우선순위가 가장 높다) 우선순위 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행 할 수 없다.
여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버헤드가 발생
우선순위가 낮은 큐의 프로세스는 Starvation 현상이 일어 날 수 있다.

6. Multilevel Feedback Queue Scheduling

Multilevel Queue Scheduling의 starvation 문제를 해결하기 위해 CPU를 할당받지 못한 프로세스를 우선순위가 높은 큐로 이동시켜주는 방식이다.
프로세스의 사전 정보 없이도 최소작업 우선 스케줄링의 효과를 보여준다.
설계와 구현이 매우 복잡하다.