[운영체제] 스케줄링 알고리즘

프로세스의 상태 중에 ready(준비 상태)에 있는 프로세스 들은 큐에 담겨져 있는데,

어떤 기준으로 담겨있어야 cpu를 효율적으로 사용할 수 있을까??

 

먼저 어떤 알고리즘들이 있는지 알아보자.

---

1. FCFS 스케줄링

First Come First Served의 약자로, 먼저 들어온 순서대로 cpu를 할당받는 스케줄링이다.

한 프로세스가 끝나야 다음 프로세스가 cpu를 할당 받을 수 있음으로 비선점 알고리즘이다.

 

- 장점: 단순하고 공평하다.

 

- 단점: 처리시간이 긴 프로세스가 먼저 도착한다면 뒤에 있는 프로세스는 대기시간이 계속 길어져 시스템의 효율성이 떨어진다.

 

 

2. SJF 스케줄링

Shortest Job First로 실행시간이 짧은 순서대로 cpu를 할당받는 스케줄링이다.

sjf도 비선점 알고리즘이다.

하지만 실행시간을 정확히 예측할 수 없긴하다. 만약 입출력이 있는 프로세스라면 사용자가 얼마나 입출력을 할지 모르기 때문이다.

 

- 장점: 실행시간이 짧은 프로세스가 먼저 실행되기 때문에 시스템의 효율성이 좋다.

 

- 단점: 실행시간이 긴 프로세스가 순위가 계속계속 밀려 공평성이 떨어진다. (아사현상이 발생함)

 

 

3. HRN 스케줄링

Highest Response Ratio Next의 약자로, 대기시간과 cpu의 이용시간을 고려해서 우선순위를 결정하는 스케줄링이다.

(대기시간 + CPU 사용시간) / (CPU 사용시간) 이렇게 우선순위를 계산한다.

 

- 장점: 아사현상을 방지할 수 있다. 대기시간이 길어진다면 우선순위가 높아지기 때문이다.

 

- 한계: 그래도 아사현상이 말끔히 해결될 만큼은 아니기 때문에 여전히 공평성이 떨어진다.

 

4. 라운드 로빈 스케줄링

기본적으로 먼저 들어온 프로세스를 먼저 실행하지만 타임 슬라이스를 정해서, 해당 시간동안 작업을 완료하지 못하면 큐의 마지막에 다시 들어가는 스케줄링이다.

따라서 선점 알고리즘이다.

 

- 장점: 일정 시간동안 이후에는 다른 프로세스에게 넘겨주기 때문에 앞에 있는 긴 프로세스를 무작정 기다리지 않는다.

 

- 단점: 문맥 교환이 자주 발생한다.

 

5.  SRT 우선 스케줄링

Shortest Remaining Time의 약자로, 기본적으로 라운드 로빈 스케줄링을 사용하고, 남은 시간이 적은 프로세스가 cpu를 먼저 할당받는 방식이다.

 

- 장점: (SJF 스케줄링과 라운드 로빈 스케줄링의 장점)

 

- 단점: 주기적으로 남은 시간을 계산해야하고 문맥교환이 자주 발생한다.

 

6. 다단계 큐 스케줄링

MLQ (Multi Level Queue)라고도 쓰며, 우선순위에 따라 준비 큐를 여러개 사용하는 방식이다.

우선순위가 높은 큐의 프로세스가 다 끝나면 다음으로 높은 큐의 프로세스가 cpu를 점유한다.

그리고 각각의 큐는 다른 방식으로 큐를 관리한다.

우선순위가 높은 큐에서는 타임슬라이스를 작게 해서 반응속도를 높이고,

우선순위가 낮은 큐에서는 FCFS를 사용하는 식이다.

 

- 장점: 우선순위를 고정으로 사용하기 때문에 우선순위를 계산하지 않아도 된다.

 

- 단점: 우선순위가 높은 큐 프로세스의 작업이 모두 끝나면 다음 큐로 넘어가기 때문에 작업이 연기될 수 있는 문제가 있다.

 

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

MLFQ(Multi Level Feedback Queue)라고도 쓰며, 위의 스케줄링의 단점을 보안했다.

다단계 큐 스케줄링(6번)에서 다른점은 프로세스가 cpu를 사용했으면 같은 우선순위의 큐로 들어가는 것이 아니라 한단계 낮은 큐로 들어가는 것이다.

또한 우선순위가 낮을 수록 타임슬라이스가 길다는 것이다. 우선순위가 낮은 큐의 프로세스는 어렵게 얻은 기회이니 만큼 오랫동안 사용하도록 하기 위함이다.

 

---

그렇다면 리눅스의 경우에는 어떤 스케줄링을 사용할까?

CFS 스케줄링을 사용한다.

이는 Completely Fair Scheduler의 약자로 공평하게 CPU를 할당받도록 하는 스케줄러로, 

대기한 시간을 계산해서 동적으로 우선순위를 매긴다. 대기시간 이외로 여러가지 조건을 고려해서 우선순위를 매긴다.

 

 

---

ref

https://hasensprung.tistory.com/178