OS - Scheduling Algorithm

안녕하세요 BeePeach입니다 :)

 

오늘 공부해볼 내용은 Scheduling Algorithm(스케쥴링 알고리즘)입니다.

 

이전 포스팅에서 가정한 것처럼 CPU는 한 번에 한 개의 프로세스만 사용할 수 있습니다.

그럼 여러개의 프로세스를 실행할 때 프로세스 스케쥴러가 어떤 프로세스를 먼저 실행시키도록 할까요??

 

목적에 맞춰서 적절한 알고리즘을 택하겠죠?

스케쥴링 알고리즘이란 스케쥴러가 여러 개의 프로세스를 효과적이고 효율적으로 실행시키도록 관리하는 것을 말합니다.

이 알고리즘에는 여러 종류가 있는데요.

 

간단한 알고리즘 몇가지를 알아보려고 합니다.

 

 

---

 

First Come First Served(FCFS)

 

FCFS는 First In First Out(FIFO)로도 불립니다.

프로세스가 스케쥴러에 등록된 순서대로 프로세스를 실행합니다.

이전에 우리가 공부했던 배치 처리 시스템과 똑같습니다.

 

FCFS는 구현이 간단하다는 장점이 있습니다.

하지만 다중프로그램 사용에는 적합하지 않습니다.

 

 

 

 

Shortest Job Next(SJN)

 

SJN은 Shortest Job First(SJF)라고도 불립니다.

실행시간이 가장 짧은 프로세스부터 실행합니다.

 

짧은 프로세스는 빨리 처리된다는 장점이 있습니다.

단점은 계속 짧은 프로세스가 들어온다면 실행시간이 긴 프로세스는 starvation에 빠질 수 있습니다.

즉 특정 프로세스가 계속 실행이 미뤄져서 실행이 안될수 있습니다.

 

 

 

Priority

우선순위대로 프로세스를 실행시킵니다.

미리 지정된 우선순위를 따르면 Static Priority

스케쥴러가 동적으로 우선순위를 관리한다면 Dynamic Priority라고 합니다.

 

단점으로는 우선순위가 높은 프로세스가 starvation상황에 놓일 수 있습니다.

그리고 우선순위가 같다면 어떻게 처리해줘야할지 정해줘야 합니다.

 

 

RoundRobin

모든 프로세스들을 특정 시간으로 나누어서 돌아가며 실행시킵니다.

이전에 공부한 시분할 시스템을 생각해주시면 됩니다.

 

장점으로는 모든 프로세스가 돌아가며 실행이 되므로 응답 시간이 짧아지므로 멀티 프로세싱에 적합합니다.

단점으로는 context swicting이 많이 일어나게 되므로 이전 알고리즘에 비해 높은 CPU 성능을 요구합니다.

 

 

프로세스 A, B, C에 대해서 각각 알고리즘 별로 프로세스가 어떻게 스케줄 되는지를 보여주는 그림입니다.

괄호 안에 숫자는 우선순위를 나타내고 높을수록 우선순위가 높다고 가정하겠습니다.

 

FCFS는 A를 먼저 처리하고 B, C를 처리합니다.

 

SJF는 가장 짧은 A를 먼저 처리하고 C, B를 처리합니다.

 

Priority는 우선순위가 가장 높은 B부터 처리합니다.

 

Round Robin은 각 프로세스를 돌아가며 처리합니다.

 

 

---

 

참고자료

 

https://data-flair.training/blogs/scheduling-algorithms-in-operating-system/