CPU Scheduling(스케줄링) - 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링, Fair-share 스케줄링, 실시간 스케줄링

<다단계 큐 스케줄링>

정적 우선순위를 사용하는 스케줄링을 구현 할 때 가장 적합한 자료구조다.

같은 우선순위 값을 가지는 프로세스들을 위해 큐가 필요함과 동시에 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요하게 된다.

프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식이다.

정적 우선순위이므로 큐들 간에 프로세스의 이동이 불가능하다.

<다단계 피드백 큐 스케줄링>

짧은 프로세스에게 유리하도록 해 줄 수 있으며, 입출력 프로세스를 우대함으로써 CPU를 포함한 전체 자원들의 활용도를 높여(짧은 연산 후 입출력을 발생하면 CPU는 다른 프로세스에게 주어지고 이때부터 입출력 작업과 CPU 연산이 병행하여 진행) 시스템의 성능을 높일 수 있는 기법이다.

동적 우선순위를 기반으로 하는 선점 방식으로 운영된다.

여러 단계(우선순위 개수만큼)의 큐가 있으며 각 단계마다 서로 다른 CPU 시간 할당량을 가진다.

(우선순위가 높은 단계의 큐일수록 시간 할당량은 작도록 함)

새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 CPU를 할당받아 실행되다가 그 큐의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감으로써 결과적으로 우선순위가 한 단계 낮아지게 된다.

각 단계에서도 그 단계 큐의 시간 할당량을 다 사용할 때까지 계속 실행된다면 다음 단계의 큐로 들어가게 되며, 마지막 단계에서는 더 내려갈 단계가 없으므로 라운드 로빈 방식으로 실행될 것이다. 어느 단계든 시간 할당량이 끝나기 전에 입출력으로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가도록 함으로써 우선순위를 높여 준다.

 

<Fair-share 스케줄링>

프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각각의 그룹에 할애된 일정량의 CPU 시간은 그 그룹에만 영향을 미치도록 하는 스케줄링 기법이다.

그룹별로 일정량의 CPU 시간을 할애했을 때, 특정 그룹에 속한 프로세스의 과도한 CPU 사용은 그 그룹 내의 다른 프로세스들에게만 불이익을 줄 뿐, 다른 그룹으로까지 파급되지 않도록 하겠다는 것이다.

예) 전체 프로세스 : A, B, C, D ,E, F

A, B : 1그룹 -> CPU 시간의 50% 할애

C, D : 2그룹 -> CPU 시간의 25% 할애

E, F : 3그룹 -> CPU 시간의 25% 할애

시분할을 기본으로 ACBEADBF의 순서대로 스케줄을 할 경우, 1그룹은 CPU 시간의 50%를 그리고 나머지 그룹은 각각 25%를 사용하게 될 것이므로 의도대로 됨을 알 수 있다. (A, B는 2번씩, C, D, E, F는 1번씩)

만약 A에게 더 많은 CPU 시간을 주어야 할 경우에는 ACAEADBF와 같은 예의 순서로 스케줄을 함으로써, A가 B보다 더 사용한 CPU 시간은 B의 CPU 시간 축소를 초래하되 타 그룹의 프로세스들은 영향받지 않게 하는 것이다.

<실시간 스케줄링>

실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템이다.

- 경성 실시간 시스템 : 작업이 마감시한(Deadline) 내에 완료되지 않으면 (시스템이 중지되는 등의) 치명적인 결과를 초래하는 시스템

- 연성 실시간 시스템 : 작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등 피해가 발생하지만 시스템은 계속해서 운영 가능한 시스템

[실시간 시스템에서의 스케줄링]

모든 프로세스들이 정해진 마감시한 내에 완료되도록 해야 하는 것이 관건인데, 정적과 동적 방법으로 나뉜다.

- 정적인 방법 : 프로세스들의 특징과 개수를 알 수 있는 경우에 유용

- 동적인 방법 : 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용

[RM(Rate Monotonic) 알고리즘]

정적 스케줄링 방식이며, 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용된다.

프로세스들은 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정하고 주기가 짧을수록 높은 우선순위를 받게 된다.

낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기게 되는 선점 방식이다.

 

[CPU 사용률(U) 구하는 방법]

 

[EDF(Earliest Deadline First) 알고리즘]

프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링이다.

동적이란 새로운 프로세스가 도착할 때 바로 대응할 수 있다는 것을 의미한다. 우선순위에 의해 실행 중 CPU를 뺏길 수 있으며, 한 프로세스의 실행이 완료될 경우에는 마감 시한이 가장 가까운 것을 찾아 스케줄한다.

모든 프로세스가 주기적일 필요는 없으며 주기가 있을 경우에는 마감시한을 주기로, 그렇지 않을 경우는 마감시한이 알려져야 한다.

 

EDF 기법은 새로운 프로세스의 동적인 수용이 허용되나, 그럴 때마다 가능한 스케줄을 찾기 위한 계산을 해야 하는 부담이 존재하는 단점이 있다.

[EDF의 CPU 사용률 구하는법]

 

 

 

시간 4에 도착한 P2는 마감시한이 P1보다 빠르므로 선점하게 되고, 시간 5에 도착하는 P3는 마감시한이 더 늦기 때문에 P2를 선점하지 못하고 기다린다. 그 후, 차례대로 P3, P1이 CPU를 할당받아 실행된다.

 

Copyrightⓒ2014 By 휴먼사이언스