프로세스 스케줄링 알고리즘

운영체제가 프로세스 스케줄링을 위해 사용하는 실질적인 방법이다.

대표적인 CPU 할당을 위한 프로세스 스케줄링 알고리즘의 종류는 아래와 같다.

 

1. 선입 선처리 스케줄링(FIFO)

준비 큐에 삽입된 순서대로 CPU를 할당해주는 방식이다.

먼저 실행되는 프로세스들의 실행 시간이 길다면, 대기 중인 프로세스들이 기다리는 시간이 매우 길어질 수 있다.

 

2. 최단 작업 우선 스케줄링(Shortest Job First)

실행 시간이 가장 짧은 프로세스부터 CPU를 할당해주는 방식이다.

 

 

3. 라운드 로빈 스케줄링(Round Robin)

준비 큐에 삽입된 순서대로 CPU를 할당하지만, 정해진 시간(타임 슬라이스)만큼만 할당해주는 방식이다.

정해진 시간동안 전부 실행되지 못했다면, 맨 마지막 순서로 돌아가서 다시 기다린다.

 

 

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

- 정해진 시간만큼 CPU를 할당하되, 다음 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택하는 방식이다.

 

 

5. 우선순위 스케줄링

- 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행시키는 방식이다.

- 우선순위가 같다면, 선입 선처리로 처리한다.

- 우선순위가 낮은 프로세스는 무한정 실행되지 못하는 기아(Starvation)현상이 발생한다.

- 기아 현상 방지를 위해 오래 기다린 프로세스의 우선순위를 점차 높이는 에이징(Aging)기법을 사용한다.

6. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.

- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리한다.

- 우선순위가 가장 높은 큐가 비어 있으면, 그 다음 우선순위 큐를 처리한다.

- 우선 순위가 낮은 프로세스는 기아 현상이 발생할 수 있다.

 

 

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

- 큐 간의 이동이 가능한 다단계 큐 스케줄링이다.

- 우선순위가 가장 높은 큐부터 처리를 하되, 일정 시간(타임 슬라이스)동안 못 끝낸 경우 그 다음 우선 순위 큐로 다시 이동하여 대기한다.

- CPU 사용 시간이 길수록 우선 순위가 내려가게 된다.

 

즉, CPU 사용 시간이 긴 CPU 집중(CPU Bound) 프로세스는 우선 순위가 상대적으로 낮아지고, CPU 사용 시간이 짧고 입출력 작업이 많은 입출력 집중(I/O Bound) 프로세스는 우선 순위가 상대적으로 높아진다.

 

 

- 에이징 기법을 통해 기아 현상을 방지한다.

 

---

Reference

https://www.youtube.com/watch?v=isj4sZhoxjk&list=PLYH7OjNUOWLUz15j4Q9M6INxK5J3-59GC&index=3