[CS] 스케줄러

스케줄러

스케줄러는 어떤 프로세스에게 자원을 할당할지 결정하는 역할을 합니다.

운영체제는 스케줄러를 통해 CPU를 사용하려고 하는 프로세스 사이의 우선 순위를 관리합니다.

이것을 스케줄링이라고 부릅니다.

프로세스를 스케줄링하기 위한 스케줄링 큐에는 다음의 세 가지 종류가 존재합니다.

• 작업 큐(Job Queue) : 현재 시스템 내의 모든 프로세스의 집합
• 준비 큐(Ready Queue) : 메인 메모리에 존재하며, CPU를 할당받고 실행을 기다리는 프로세스의 집합
• 장치 대기 큐(Device Queue) : 특정 입/출력장치를 대기하는 프로세스의 집합

 

스케줄러의 종류

1. 장기 스케줄러 (Long-Term Scheduler 또는 Job Scheduler)

• 메모리와 디스크 사이의 스케줄링을 담당합니다.
• 많은 프로세스들이 한꺼번에 한정된 메모리에 올라올 경우, 대용량 메모리(디스크)에 임시로 저장합니다.
• 디스크에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue로 보낼지 결정하는 역할을 합니다.
• 프로세스에 메모리 및 각종 리소스를 할당합니다.
• 실행 중인 프로세스의 수를 제어합니다. (Degree of Multiprogramming)
• 프로세스의 상태 
  • New (시작 상태) -> Ready (준비 상태)
  • Running or Ready -> Terminated (종료 상태)

 

2. 단기 스케줄러 (Short-Term Scheduler 또는 CPU Scheduler)

• CPU와 메모리 사이의 스케줄링을 담당합니다.
• 따라서, 장기 스케줄러에 비해 매우 많이 호출됩니다.
• Ready Queue에 있는 프로세스 중 어떤 프로세스를 running 시킬지 결정합니다.
• Ready Queue에 있는 프로세스 중 먼저 도착한 프로세스에게 CPU를 할당한다. (Scheduler Dispatch)
• 프로세스의 상태
  • Ready -> Running -> Waiting -> Ready

 

3. 중기 스케줄러 (Medium-Term Scheduler 또는 Swapper)

• 시분할 시스템에서 추가로 사용하며, 메모리에 대한 가중을 완화시켜주기 위해 사용합니다.
• CPU를 차지하기 위한 경쟁이 심해질 때, 우선순위가 낮은 프로세스들을 잠시 제거한 뒤 나중에 경쟁이 완화되었을 때 다시 디스크에서 메모리로 불러와 중단되었던 지점부터 실행시킵니다. (Swapping)
• 현재 시스템에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 역할을 합니다.
• 프로세스의 상태
  • Ready -> Suspended (외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태)

 

CPU 스케줄링 (CPU Scheduling)

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 합니다.

이때, 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 CPU Scheduling 알고리즘이라고 합니다.

이는 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는가가 관건입니다.

• Preemptive (선점)
  • 한 프로세스가 CPU를 점유하고 있는 동안에도. I/O나 인터럽트가 발생하지 않았음에도 다른 프로세스는 해당 CPU를 강제로 점유할 수 있습니다.
• Non-Preemptive (비선점)
  • 한 프로세스가 CPU를 점유했다면, I/O나 인터럽트 발생 또는 프로세스가 종료될 때까지 다른 프로세스는 CPU를 점유하지 못합니다.

 

비선점형 스케줄링

1. FCFS(First Come First Served) 스케줄링

• 가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식입니다.
• 작성이 간단하고 이해하기 쉽습니다.
• 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생합니다. (Convoy Effect)

 

2. SJF(Shortest Job First) 스케줄링

• 다음 CPU burst time의 길이를 고려해서 스케줄링을 결정하는 방식입니다.
• 비선점형과 선점형이 따로 존재합니다. 
• 비선점형에서는 실행되고 있는 프로세스는 끝까지 실행합니다.
• 선점형에서는 다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 CPU를 먼저 할당합니다. (SRTF)
• 평균 대기 시간을 줄일 수 있지만 다음 프로세스의 CPU burst time을 예측하기 어렵다는 문제가 존재합니다.
• 사용 시간이 긴 프로세스는 거의 CPU를 할당받을 수 없는 현상이 발생합니다. (Starvation)

 

3. Priority 스케줄링

• 각각의 프로세스에 우선순위 넘버가 있어 가장 높은 우선순위의 프로세스에 CPU를 할당합니다.
• 선점형과 비선점형이 모두 가능합니다.
• SJF도 여기에 속합니다. (다음 CPU burst time이 우선순위 역할)
• 기아(Starvation) 문제가 발생할 수 있습니다. 
• 기아 문제를 해결하기 위해서 시간이 지날수록 프로세스의 우선순위를 높여주는 노화(aging)를 사용할 수 있습니다.

 

선점형 스케줄링

1. SRTF(Shortest Remaining Time First) 스케줄링

• 잔여 시간이 짧은 순서대로 프로세스를 수행합니다.
• 현재 CPU에서 실행 중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 가지는 프로세스가 도착하면 CPU가 선점됩니다.
• 선점형 SJF 스케줄링이라 불립니다.

 

2. Round Robin 스케줄링

• 시분할 시스템의 성질을 활용한 방법입니다.
• 모든 프로세스가 같은 우선순위를 가지고, Time Quantum(Time Slice)를 기반으로 스케줄링합니다.
• 일정 시간을 정하여 하나의 프로세스가 해당 시간 동안 수행하고 다시 대기 상태로 돌아갑니다.
• Time Quantum이 크면 FCFS와 같게 되고, 작으면 Context Switching이 잦아져서 오버헤드가 증가합니다.

 

3. Multi-Level Queue 스케줄링

• 프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue(준비 큐)를 여러 개 둡니다.
• 각 큐는 각자의 스케줄링 알고리즘을 가지고 있습니다.
• 각 큐 사이에서는 프로세스들이 이동할 수 없습니다.
• 일반적으로 Foreground 프로세스들은 Round Robin 방식을 사용하고, Background 프로세스는 FCFS를 사용합니다.
• 기아(Starvation) 문제가 발생할 수 있습니다.

 

4. Multi-Level Feedback Queue 스케줄링

• 기본 개념은 Multi-Level Queue와 동일하나, 각 큐 간에 프로세스들이 이동할 수 있다는 점이 다릅니다.
• 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로 위치합니다.