1. 스케줄링 큐를 통해 프로세스 줄 세우기

CPU가 모든 프로세스의 PCB를 하나하나 방문하면서 우선순위를 확인하고 실행 순서를 결정하는 방식은 효율이 떨어진다. CPU 자원을 효율을 높이려면 앞선 방식의 반대로 생각하면 된다. 즉, 미리 프로세스들에게 줄 서는 방법을 알려주고 줄을 선 순서대로 실행만 하면 CPU 자원을 효율적으로 활용할 수 있을 것이다. 이때 프로세스들이 줄을 서는 공간을 스케줄링 큐라고 부른다.

스케줄링 큐는 두 가지이다.

1. 준비 큐
   CPU를 이용하기 위해 기다리는 줄

2. 대기 큐
   입출력장치를 이용하기 위해 기다리는 줄

2. 다양한 알고리즘으로 스케줄링 큐 다루기

CPU 스케줄링 알고리즘에서 중요한건 알고리즘 이름보다는 작동 방식, 알고리즘 장단점이 중요하다. 서로 어떤 부분을 보완해 주는지 확인해보자.

1. 선입 선처리 스케줄링 (First Come First Served)

   단순 준비 큐에 삽입된 프로세스 먼저 처리

   • 프로세스 대기 시간이 매우 길어질 수 있음 (호위 효과)

2. 라운드 로빈 스케줄링 (Roun Robin)

   타임 슬라이스 동안만 큐에 삽입된 프로세스 먼저 처리

   타임 슬라이스 크기에 따라 장단점 발생 (너무 크면 선입 선처리와 다를게 없고, 너무 짧으면 오버해드가 일어날 가능성 높음)

3. 최단 작업 우선 스케줄링 (Shorest Job First)

   실행 시간이 짧은 프로세스 먼저 처리

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

   타임 슬라이스 동안만 남은 시간이 짧은 프로세스 먼저 처리

5. 우선순위 스케줄링

   우선순위 높은 프로세스 먼저 처리 (우선 순위가 같다면 선입 선처리 스케줄링)

   • 우선순위 낮은 프로세스의 실행이 계속 연기되는 기아 현상 (starvation)
     → 오래된 프로세스의 우선순위를 점차 높이는 에이징 (aging) 으로 해결

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

   우선순위 별로 여러 개의 준비 큐를 사용하여 우선순위가 높은 큐를 먼저 처리.

   • 큐마다 다른 타임 슬라이스와 스케줄링 방식 적용가능
   • queue 간의 이동이 불가능해 기아 현상 (starvation)

7. 다단계 피드백 큐 스케줄링 (Multi Level Feedback Queue, 가장 일반적)

   가장 먼저 온 준비 단계 프로세스를 높은 우선순위로 두고 처리 후 아직 종료가 되지 않았다면, 우선 순위가 낮은 큐로 이동 시킴. 이때 대기를 오래한 프로세스의 우선순위는 aging을 통해 다시 높여줌.

   자연스럽게 CPU 집중 프로세스는 우선 순위가 낮아짐

사진 출처 : 혼자 공부하는 컴퓨터 구조와 운영 체제