스케줄링이란?

목표

장기, 중기, 단기 스케줄러를 설명할 수 있다.
스케줄링의 비교 척도를 이해할 수 있다.
선점 스케줄링과 비선점 스케줄링의 차이점을 설명할 수 있다.
다양한 스케줄링의 장단점을 설명할 수 있다.

스케줄링이란?

스케줄링의 넓은 의미는 자원을 효율적으로 사용하기 위해 자원을 사용하는 순서를 결정짓는 작업입니다. 대부분 스케줄링이라고 하면 프로세스의 순서를 결정짓는 작업이라고 생각하는데 이는 스케줄링 중 단기 스케줄링에 해당하는 설명이다. 그렇다면 장기, 중기 스케줄링은 무엇인지 알아보도록 하겠습니다.

장기 스케줄러(Long-Term)

• 메모리와 디스크 사이의 스케줄링을 담당합니다.
• 실행할 작업을 준비 큐에서 꺼내 메인 메모리에 적재합니다.
• 메인 메모리에 적재된 프로세스의 양을 판단하여 조절하는 역할을 합니다. 이는 멀티프로그래밍의 정도와 관련 있습니다.
• Admit(생성-> 준비), Release(실행-> 종료)와 관련 있습니다.

중기 스케줄러(Mid-Term)

• 어떤 프로세스들이 CPU를 할당받을 것인지 결정합니다.
• CPU 사용에 대한 프로세스들을 중재하여 일시 보류 & 재활성화합니다.
• 메모리에서 디스크로 잠시 나가는 상태를 스왑 아웃(swap-out)이라고 합니다.
• 메모리에 여유가 생겨 다시 적재하는 것을 스왑 인(swap-in)이라고 합니다.
• 중기는 단기 스케줄러와 달리 CPU를 직접 할당하는 것이 아니라 CPU를 할당받을 수 있는 상황을 조절하는 스케줄러입니다.

단기 스케줄러(Dispatch)

• Dispatcher가 메모리 내의 준비 상태에 있는 작업 중 실행할 프로세스를 선택하여 CPU를 할당합니다.
• 일반적으로 스케줄러라 부르는 것은 대부분 단기 스케줄러를 의미합니다.

다음으로는 어떤 스케줄링이 가장 좋은지 알아보도록 하겠습니다. 가장 좋은 스케줄링이란 무엇일까요? 특정한 상황에 가장 좋은 스케줄링은 존재할 수 있지만 모든 상황에서 가장 좋은 스케줄링은 존재하지 않는다고 생각합니다. 그렇다면 스케줄링이 좋다고 말할 수 있는 비교 척도는 무엇이 있는지 알아보도록 하겠습니다.

 

스케줄링 비교 척도

• CPU 이용률: 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율을 말합니다.
• 응답 시간: 첫 응답이 오기까지 걸린 시간입니다.
• 대기 시간: 프로세스가 준비상태 큐에서 대기하는 시간입니다.
• 반환 시간: 프로세스가 시작해서 끝날 때까지 걸린 시간입니다.
• 처리량: CPU가 단위 시간당 처리하는 프로세스의 개수입니다.

 

선점 스케줄링

• 어떤 프로세스가 자원을 사용하고 있어도 우선순위가 더 높은 프로세스가 자원을 뺏을 수 있는 스케줄링입니다.
• 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 유용합니다.
• 선점 상황이 잦아지면 많은 오버헤드가 발생할 수 있습니다.
• Round Robin, SRTF, 다단계 큐, 다단계 피드백 큐는 선점 스케줄링입니다.

비선점 스케줄링

• 이미 할당된 자원을 다른 프로세스가 뺏을 수 없는 스케줄링입니다.
• 응답 시간의 예측이 가능합니다.
• 일괄 처리 방식에 적합합니다.
• 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생할 수 있습니다.
• FCFS, SJF, HRN은 비선점 스케줄링입니다.

 

FCFS(First Come First Service, 선입선출)

• 먼저 요청한 프로세스 순으로 스케줄링합니다.
• 비선점 스케줄링입니다.
• 장점: 공정한 스케줄링이며 일괄 처리 시스템에 적합합니다.
• 단점: 콘보이 효과가 일어날 수 있습니다. 즉 CPU를 오래 사용하는 프로세스가 도착하게 되면 다른 프로세스가 CPU를 사용하는데 기다리는 대기 시간이 커지는 현상이 일어날 수 있습니다.

 

SJF(Shortest Job First)

• CPU 작업 시간이 가장 짧은 프로세스 순으로 스케줄링합니다.
• 비선점 스케줄링입니다.
• 작업 시간이 동일할 경우 FCFS 정책을 따릅니다.
• 장점: 평균 대기 시간과 대기 응답 시간이 짧습니다.
• 단점: 기아 현상이 일어날 수 있습니다. 그뿐만 아니라 프로세스 생성 시 총 실행 시간에 대한 정확한 계산이 힘들다는 단점이 있습니다.

 

SRTF(Shortest-Remaining-Time-First)

• 선점 SJF 스케줄링입니다.
• 장점: 평균 대기 시간과 응답 대기 시간이 짧습니다.
• 단점: 실행 시간을 추정하는 작업이 추가로 필요합니다.

 

Round-Robin

• 시간 조각(time slice)을 정의하여 이 시간이 경과할 때마다 현재 프로세스를 중단하고 다음 프로세스를 실행합니다.
• 응답 시간이 짧아 시분할 시스템에서 주로 사용합니다.
• 선점 스케줄링입니다.
• 장점: 응답 시간이 짧습니다.
• 단점: 시간 조각이 긴 경우 FCFS와 동일하게 작동하여 FCFS의 단점을 Round-Robin에서도 볼 수 있습니다.

 

HRN(Highest Response Ratio Next)

• SJF의 기아 문제를 해결하기 위해서 등장한 스케줄링입니다.
• (대기시간 + 실행시간) / 실행시간을 우선순위로 하여 대기시간을 고려한 스케줄링입니다.
• 비선점 스케줄링입니다.

 

다단계 큐(MLQ, Multi-Level Queue)

• 프로세스들의 우선순위 개수만큼의 큐가 필요합니다.
• 프로세스들은 자신의 우선순위에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏깁니다.
• 각 큐는 라운드 로빈이나 FCFS 등 독자적 스케줄링을 사용할 수 있습니다.
• 시스템 작업, 대화형 작업, 대화형 편집, 일괄 처리, 학생 작업 순으로 우선순위가 높습니다.
• 선점 스케줄링입니다.
• 장점: 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적습니다.
• 단점: 큐들 간의 프로세스 이동이 불가하기 때문에 유연성이 떨어집니다. 그뿐만 아니라 우선순위가 낮은 큐는 계속해서 대기하는 기아 현상이 발생할 수 있습니다.

 

다단계 피드백 큐(MFQ, Multi-Level Feedback Queue)

• 다단계 큐와 달리 큐 사이의 프로세스 이동이 가능합니다.
• 해당 큐의 CPU 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어갑니다.
• 단계가 내려갈수록 시간 할당량이 증가합니다.
• 가장 하위 큐는 FCFS 스케줄링 방식으로 동작합니다.
• 맨 아래 큐에서 너무 오래 대기하면 다시 상위 큐로 이동합니다. (에이징 기법을 통한 기아상태 예방)
• 선점 스케줄링입니다.
• 다단계 피드백 큐 스케줄링의 경우 큐의 수, 각 큐에 대한 알고리즘, 우선순위 격상 또는 격하 시기 결정, 처음 프로세스들이 진입해야 할 큐 등 매우 복잡한 판단을 요구하기 때문에 실제로 사용을 하는 경우는 적습니다.