프로세스 스케줄링

CPU 스케줄링 : 프로세스가 CPU를 할당받는 방식을 관리하는 작업입니다. 여러 프로세스가 CPU를 사용하려 할 때, 어떤 프로세스가 CPU를 사용할 지 결정하는게 주 된 목적입니다.

 

CPU Burst : CPU가 짧은 시간동안 높은 처리량을 보이는 현상을 말합니다.

 

CPU 스케줄러 : CPU가 유휴 상태가(Idle) 될 때마다 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 이런 선택 절차를 수행하는게 CPU스케줄러.

 

CPU 스케줄링 결정은 네가지 상황에서 발생할 수 있다.

   1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때.

   2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때.

   3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때.

   4. 프로세스가 종료할 때.

 

Dispatcher : 디스패처(dispatcher)는 컴퓨터 운영체제에서 프로세스 관리와 관련된 중요한 기능을 수행하는 소프트웨어 구성 요소입니다. 아래와 같은 작업들을 합니다.

   1. 문맥 교환 (Context switching)

   2. 사용자 모드로 전환하는 일

   3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일

디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 최고로 빨리 수행되어야 합니다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 쇼요되는 시간을 디스패치 지연이라고 합니다.

 

스케줄링 기준 : 스케줄링 알고리즘들은 굉장히 많으며, 각자 다른 기준으로 우선순위를 정하게 됩니다. 아래와 같은 기준들이 있을 수 있습니다.

   1. CPU 이용률 (utilization)

   2. 처리량 (throughput) : 단위 시간마다 완료된 프로세스의 개수 = 처리량

   3. 총 처리 시간 : 프로세스 제출 시간과 완료 시간의 간격 = 대기시간 + 실행시간 + I/O시간

   4. 대기 시간 : 

   5. 응답 시간 : 

CPU이용률과 처리량을 최대화하고, 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는 것이 바람직하다.

 

스케줄링 알고리즘

   1. 선입 선처리 스케줄링 (First-Come First-Served)(FCFS) (비선점) : CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받는 방식입니다. 간단하고 쉽게 관리 될 수 있지만, 평균 대기 시간이 길어질 수 있습니다. 여러개의 프로세스들이 하나의 긴 프로세스가 끝나기를 기다리는 것을 호위 효과(Convey effect)라고 합니다.

   2. 최단 작업 우선 스케줄링 (Shortest Job First) : 이 알고리즘은 가작 장은 다음 CPU Burst를 가진 프로세스가 CPU를 할당받는다. 만약 같은 길이의 CPU Burst를 갖는다면, 선입 선처리 스케줄링을 적용한다. 최단 작업 우선 스케줄링은 선점 또는 비선점이 될 수 있다. 선점일 경우새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU버스트를 가진채로 준비 왼료 상태가 되면 CPU가 새로운 프로세스에 의해 선점될 것이고, 비선점일 경우, 현재 실행하고 있는 프로세스를 우선적으로 끝내도록 허용합니다.

   3. 라운드 로빈 (Round Robin, RR) : 라운드 로빈 스케줄링은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨다닐 수 있도록 선점이 추가된다. 시간 할당량, 또는 타임 슬라이스라고 하는 작은 단위의 시간을 정의한다. 시간 할당량은 일반적으로 10에서 100밀리초 동안이다. 준비 큐는 원형 큐로 동작한다. CPU 스케줄러는 준비 큐를 돌면서 한번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다. RR알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. RR알고리즘에서 Time Quantum이 무한으로 주어질 경우 FCFS 스케줄링이 된다. 반대로 TimeQuantum이 굉장히 적을 경우 Context switch가 많이 발생하기 때문에 많은 오버헤드가 발생할 수 있다.

   4. 우선순위 스케줄링 (Priority base Scheduling) : 프로세스에게 연관되어있는 특정 기준으로 우선순위를 매겨, 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당하는 스케줄링 방식입니다. 우선순위가 같은 프로세스들은 선입 선처리 순서로 스케줄된다. SJF알고리즘이 우선순의 스케줄링의 대표적인 예시입니다. 우선 순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(Indefinite blocking) 또는 기아 상태(Starvation)입니다. 우선 순위가 매우 낮은 프로세스들이 무한히 봉쇄될 수 있는데 이를 해결할 수 있는 해결 방안중 하나는 노화(aging)입니다.

   5. 다단계 큐 스케줄링 (Multilevel Queue Scheduling) : 우선순위 스케줄링과 라운드 로빈 스케줄링을 결합한 방식으로, 우선순위마다 각자의 큐를 부여하고, 우선순위가 높은 큐를 라운드 로빈 방식으로 처리합니다.