[OS] 프로세스 스케줄러 및 CPU 스케줄러 및 알고리즘

2021. 11. 1. 18:55

스케줄러란 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 코드를 의미합니다. 스케줄러는 역할과 목적에 따라서 단기 스케줄러, 중기 스케줄러, 장기 스케줄러로 구분됩니다.

단기 스케줄러

장기 스케줄러

메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(디스크)에 임시로 저장됩니다. 대용량 메모리에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할을 합니다.
메모리와 디스크 사이의 스케줄링을 담당합니다.
하드 디스크에 있는 프로그램을 메모리에 로드하는 역할을 담당합니다.
메모리에 몇개의 프로그램이 올라갈 것인지 제어합니다.
프로세스의 상태의 변화 new -> ready

중기 스케줄러

CPU는 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 합니다. 이때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 스케줄링 알고리즘이라고 합니다.
스케줄링 알고리즘에는 비선점 스케줄링 방식과 선점 스케줄링 방식이 있습니다.

프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시간까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식입니다.
모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만 짧은 작업을 수행하는 프로세스가 긴 작업을 하는 프로세스 종료 시까지 대기해야할 수도 있습니다.
알고리즘 : FCFS, SJF, 우선순위 등

FCFS(First-Come-First-Served) 알고리즘

먼저 들어온 프로세스가 먼저 처리되는 알고리즘입니다. 흔히 많이 보던 FIFO, Queue와 같습니다.
장점
- 가장 간단한 스케줄링 알고리즘으로 구현이 쉽습니다.
단점
- 비선점식 알고리즘이기 때문에 대화식 프로세스에 적합하지 않습니다.
- 긴 작업을 해야하는 프로세스가 먼저 온 경우 짧은 작업으로 완료되는 프로세스의 대기시간이 길어지게 됩니다.

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스에게 자원을 할당하는 알고리즘입니다.
장점
- 실행 시간이 짧은 작업을 먼저 실행하기때문에 평균 대기시간이 다른 알고리즘에 비해 짧아집니다.
단점
- 짧은 작업들이 계속 생기는 경우 작업 시간이 긴 프로세스가 너무 오래 기다리는 현상이 발생합니다.
- 짧은 작업에 최우선으로 CPU를 할당하기 때문에 공평하지않습니다.

우선순위(비선점)

우선순위(선점)

하나의 프로세스가 CPU를 차지하고 있어도 우선순위가 높은 다른 프로세스가 대기하는 경우 현재 프로세스를 중단 시키고 우선순위가 높은 프로세스에게 CPU를 할당하는 스케줄링 방식입니다.
장점
- 응답이 빠릅니다.
단점
- 처리 시간을 예측하기 힘듭니다.
- 우선순위 프로세스들이 계속해서 들어오는 경우 오버헤드가 발생합니다.

RR(Roung-Robin)

현대적인 CPU 스케줄링 방식으로 각 프로세스는 동일한 할당 시간을 갖게되고 할당 시간이 지나고 나면 ready queue 맨 끝으로 가서 다시 CPU의 할당을 기다립니다.
장점
- 모든 프로세스가 공정하게 시간을 할당받습니다.
- 프로세스 최악의 응답시간을 아는데 유리합니다.
단점
- 하드웨어 타이머가 필요합니다.
- 작업 시간을 너무 짧게한 경우 Context Switching이 빈번하게 일어나 오버헤드가 발생합니다.

MLQ(Multilevel Queue)

준비 상태 큐를 여러 종류별, 단계별로 분할해두고 자신만의 독자적인 스케줄링 구현이 가능합니다.
각 큐는 절대적인 우선순위를 가지며 우선순위가 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행할 수 없습니다.
장점
- 응답이 빠릅니다.
단점
- 여러 준비 큐와 스케줄링 알고리즘을 사용하기 때문에 추가 오버헤드가 발생합니다.
- 우선순위가 낮은 큐의 프로세스가 오래 기다리는 현상이 발생합니다.

선장 일지