CPU 스케줄링

CPU 스케줄링

멀티프로세싱, 멀티 프로그래밍에서 CPU를 적절히 할당하는 방식으로 최대한 CPU효율을 높인다.

스케쥴링 방식은 크게 선점/비선점으로 나뉘는데, 쉽게 말하면 중간에 CPU를 뺏을 수 있는지 없는지를 말한다.

 

dispatcher

dispatcher는 문맥교환이 발생할 때 프로세스에 CPU를 할당해주는 역할을 하는 일종의 모듈이다.

• 유저모드를 바꿔주기도 한다.
• 실행중인 프로세스의 PCB를 저장하고 실행할 프로세스의 PCB를 복원하는 과정에서 발생하는 dispatcher latency는 짧아야 한다.

 

스케줄링의 종류

장기(상위) 스케줄링 –작업 스케줄링

프로세스가 자원을 사용하는 시기를 결정하여 대기 큐(ready queue)로 전달하는 작업

 

프로그램들이 주 기억 장치에 적재될 시기를 결정하는 것과 같은 스케줄링으로 다소 느린 작업 계획

 

중기(중위) 스케줄링

프로세스가 여러 개의 CPU 중에 어떤 CPU를 할당 받을 것인가를 결정하는 작업

 

중기 스케줄러는 프로세스의 주 기억장치로부터 빼낼 수 있으므로 필요한 경우에는 다중 프로그래밍의 정도를 낮추어(CPU를 할당 받으려는 프로세스가 많을 때, 프로세스 상태를 대기(wait)시키고 활성화해서 부하를 조절) 시스템의 전반적인 효율을 높여주거나 특정 프로세스에 대한 처리를 원활하게 해줄 수 있는 효과를 얻을 수 있다

 

단기(하위) 스케줄링 – 프로세스 스케줄링

여러개의 프로세스가 하나의 CPU를 점유하기 위한 시기를 결정하기 위한 작업으로 프로세스 스케줄링이라고한다

디스패치, 인터럽트를 통한 문맥교환 등을 수행하는 것처럼 짧은 시간에 처리해야하는 작업 계획이다.

 

프로세스 스케줄링의 성능 평가 기준

CPU 이용률: CPU를 쉬지 않고 몇 퍼센르를 이용하는가의 기준 (늘려야 함)

처리 능력: 단위 시간당 처리할 수 있는 CPU의 작업량(늘려야 함)

대기시간: 준비 상태에서 대기하는 시간(줄여야함)

응답시간: 입력에 대해 처음 반응하는 시간(줄여야 함)

반환시간: 작업을 지시하고 그 결과가 되돌아오는 시간(줄여야함)

 

선점형 방식과 비선점형 방식

 

선점형 방식이란

- 하나의 프로세스가 CPU를 점유하고 있을떄는 다른 프로세스가 현재 사용 중인 프로세스를 중단시키고 CPU를 차지할 수 있는 방식이다.

- 선점형 방식들은 높은 우선 순위의 프로세스들이 긴급을 필요로 할 때 유용

- 빠른 응답시간을 필요로하는 대화식 시분할 실시간 처리에 적당

 

선점형 방식

RR(Round-Robin)

라운드 로빈이란

시간 할당량 안에 작업을 마치지 않으면 준비 대기 리스트의 가장 뒤로 배치되는 방식이다

 

라운드 로빈의 특징

- 동일한 시간 할당량을 사용하는 시분할 처리 시스템에 효과적으로 적용된다.

- 시간 할당량이 크면 비선점의 FIFO와 동일하다

- 시간 할당량이 적으면 문맥교환수와 오버헤드가 증가한다

- 적절한 응답시간을 보장해주는 대화식 사용자에게 효과적이다.

 

SRT(Shortest Remaining Time)

SRT이란

작업이 끝나기까지 남아있는 실행 시간의 추정치가 가장 작은 프로세스를 먼저 실행하는 방식

 

SRT의 특징

- 서비스를 받은 시간을 기록해야하기 때문에 오버헤드가 증가

- 평균대기 시간과 대기시간의 분산도 크다

- 임계치를 사용한다.

 

MFQ(Multi level Feedback Queue)

- 짧은 작업이나 입출력 위주의 작업에 우선순위를 부여하기 위해서 개발된 방식

- 큐가 여러 개이며 우선순위가 있다.

- 큐의 우선순위는 동적으로 변경 가능하다

- 두 작업의 우선순위가 동일하면 두 작업 간에 RoundRobin 스케줄링을 사용하여 수행

- 각 큐마다 시간 할당량이 존재하며 낮은 큐일수록 시간 할당량은 커진다.

- 각각의 큐들은 종속적으로 연결되어있다.

- CPU를 시간할당량만큼 사용한 프로세스는 낮은 큐로 이동한다.

- 맨 마지막 단계의 큐는 FIFO를 사용한다.

 

비 선점형이란

- CPU를 점유하고 있을 때는 다른 프로세스가 현재 실행중이 프로세스를 중단시킬 수 없다.

- 일단 CPU를 할당 받으면 다른 프로세스가 CPUF를 강제적으로 빼앗을 수 없는 방식이다.

- CPU를 사용하고 있는 현재의 프로세스가 종료된 후 다른 프로세스에 CPU를 할당한다 즉 실행이 완료될 때 까지 CPU를 독점한다

- 비 선점형 방식들은 모든 프로세스를 관리하는데 공정하다

- 프로세스의 실행 예측치를 미리 통보하고 프로세스를 수행 한다면 응답시간의 예측이 용이하다

- 일괄처리 시스템에 적당하다.

 

비 선점형 방식

HRN(Highest Responese Ratio Next)

HRN이란

작업의 서비스 받을 시간과 그 작업이 서비스를 기다린 시간으로 결정되는 우선순위에 따라 CPU 할당한다

 

HRN의 특징

- FIFO와 SJF의 단점을 보완하여 개발된 방법

- 긴 작업과 짧은 작업간의 불평등을 해소할 수 있다

- 대시 시간이 긴 프로세스의 경우 우선순위가 높아진다

- HRN은 실행 시간 추정과 선점 기능 때문에 스케줄러가 복잡해지고 남은 계산 시간을 저장해 놓아야하는 단점을 보완하였다.

- HRN의 우선순위 공식에 따라 수치가 큰 값부터 낮은 순으로 우선순위가 부여된다.

 

FIFO(First IN First Out)

FIFO란

입력된 순으로 처리되는 방식이다

 

FIFO의 특징

- 입력된 순으로 처리되기 때문에 공평하다

- 알고리즘이 간단하고 구현하기 쉽다

- 짧은 작업이나 중요한 작업을 오랫동안 기다리게 할 수 있다

- 평균 반환시간이 길다

 

SJF(SHort Job First)

SJF란

작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행시키는 방식

 

SJF의 특징

- FIFO보다 평균 대기 시간이 작지만 긴 작업의 경우 FIFO기법보다 더 크고 예측이 더욱 어렵다

- 실행 시간이 많은 작업일 경우 무한 대기 상태가 발생할 수도 있다.

- 무한 대기 상태를 방지하기 위해 aging 기법을 사용하여 해결

 

혼합형

MLQ(Multi level Queue, MQ)

- 선점형, 비 선점형 방식이다.

- 우선순위 큐에 따라 알고리즘을 달리 적용한다

- 우선순위가 가장 높은 큐에서는 비선점형으로 사용된다.

- 우선순위가 낮은 큐에서는 선점형으로 사용된다

- 상위 큐가 우선순위가 가장 높은 큐로 신속한 처리를 필요로 하는 시스템 프로세스가 입력된다.

- 중위는 대화형 프로세스, 하위는 일괄처리 프로세스가 입력된다.

- 대기 리스트(우선순위 큐)간 프로세스 이동은 안 됨

- 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어짐

- 우선순위가 낮은 프로세스가 오랬동안 CPU 할당을 기다리는 기아 현상이 발생할 수도 있음

 

MLQ와 MFQ의 차이점

가장 큰 차이점은 MLQ 스케줄링의 경우 큐와 큐 사이에 프로세스들이 이동을 할 수 없는 반면, MFQ 스케줄링의 경우 큐 사이에 프로세스들이 이동을 할 수 있다. 따라서 MFQ 스케줄링에 비해 MLQ 스케줄링은 스케줄링 부담이 적지만 유연성은 떨어진다.

 

또한 MLQ 스케줄링의 경우 하위 단계의 큐에 있을수록 CPU 할당을 받지 못하여 기아 현상이 발생할 수도 있지만 MFQ 스케줄링의 경우는 에이징 기법을 통해 기아 현상을 예방할 수 있습니다.