CPU 스케줄링이 필요한 이유

I/O bound job
- CPU로 연산을 수행하는 시간보다, I/O에 많은 시간이 필요한 작업
  ex) 사용자와 상호작용하는 프로그램
CPU bound job
- 계산 위주의 작업
  ex) 과학 계산 프로그램 등

만약 CPU bound job 위주로 스케줄링을 하게되면, I/O bound job은 연산을 못할
뿐더러, I/O 장치까지 연산을 못하게 됩니다.
그래서 적절한 균형을 유지하여, CPU와 I/O 장치를 최대한 효율적으로 사용하기 위해서
CPU 스케줄링이 필요합니다.

CPU Scheduler 7 Dispatcher

CPU Scheduler
- Ready 상태의 프로세스 중에서 CPU를 할당할 프로세스를 고르는 역할

CPU Dispatcher
- CPU Scheduler가 선택한 프로세스에 CPU 제어권을 넘기는 역할
  이 과정이 바로 Context switch!

다음과 같은 경우에 CPU 스케줄링이 필요한데요.
크게 자진 반납과 강제 회수로 나뉩니다.

자진 반납(nonpreemtive)
- Running→Blocked : I/O를 요청하는 시스템콜
- Terminate
강제 회수(preemtive)
- Running→Ready : 할당시간 만료(Timer interrupt)
- Blocked→Ready : I/O 완료 후 인터럽트

CPU Scheduling Criteria

CPU 스케줄링 방법은 여러가지가 있는데, 이 중에서 어떤 방법이 어떤 점이 좋은지 판단하여
사용해야 하는데요.
그래서 CPU 성능을 평가할 척도가 필요합니다.

이용률(CPU Utilization) : CPU가 노는시간 없이 최대한 효율적으로 사용하게 하는지
처리량(Throughput) : 단위시간 내에 처리 완료한 프로세스들의 양
소요시간, 반환시간(Turnaround time) : 특정한 프로세스를 처리하는데 걸리는 시간
대기시간(Waiting time) : 프로세스가 ready queue에서 대기한 시간
응답시간(Response time) : 요청한 시점부터 처음으로 CPU를 얻는데까지 걸린 시간
(시분할 시스템에 대한 척도)

CPU Scheduling Algorithms

FCFS(First-Come First-Served)

nonpreemtive 한 스케줄링 기법으로, 먼저 온 순서대로 CPU를 할당해주는 스케줄링 방법 입니다.

대기시간
- P1 : 0
- P2 : 24
- P3 : 27
- 평균 : 17

대기시간
- P1 : 6
- P2 : 0
- P3 : 3
- 평균 : 3

FCFS는 도착순서에 따라 대기시간이 일정하지 않게 바뀌고, 상대적으로 짧은 프로세스는 길게 기다리는 단점이 있습니다.

SJF(Shortest-Job-First)

각 프로세스의 다음번 CPU burst time이 가장 짧은 프로세스에게 먼저 CPU 제어권을 할당합니다.
기본적으로 Nonpreemptive 한 방법이라서, CPU Burst 동안은 CPU 제어권을 뺏기지 않습니다.

CPU burst time이 짧은 순서대로 CPU 제어권을 할당하기 때문에 평균 대기시간이 짧다는 장점이 있습니다.
SJF is optimal 이라고도 하는데, 이 방법보다 평균 대기시간을 더 줄이는 방법이 없기 때문입니다.

평균 대기시간 : (0 + 6 + 3 + 7)/4 = 4

SRTF(Shortest-Remaining-Time-First)

SRTF 스케줄링 방법은 SJF같은 범주에 속하는 같은 매커니즘을 가진 방법이지만 Preemtive 하다는 점이 다릅니다.
현재 실행인 프로세스의 남은 burst time 보다 더 짧은 것이 나타나면, 그 프로세스에게 CPU 제어권을 넘겨주는 방법인데요
이 방법은 오히려 SJF 보다 평균 대기시간 더 짧은 특징이 있습니다.
이전에 말했던 SJF is optimal를 보면 사실, SRTF 가 더 적절하다고 말할수도 있습니다.

평균 대기시간 : (9+1+0+2)/4 = 3

SJF & SRJF 의 치명적인 단점

기아 현상(Starvation)

효율성만을 고려하여 짧은 작업에게 CPU 제어권을 먼저 주기 때문에, 긴 작업은 제어권을 얻지 못하는 기아 현상(Starvation)이 발생할 수 있습니다.

다음 CPU Burst time을 예측

다음번 CPU Burst time 정확히 알 수 없기 때문에, 여러 조건들로 추정할 수 밖에 없습니다.
해당 프로세스의 과거 CPU Burst time을 이용해서 추정하는 방법이 있는데요.
짧게 사용할것이라고 예측하고 CPU를 넘겨줬는데 예상외로 길게 사용하면, 안정적인 스케줄링이 안된다는 단점이 있습니다.

Priority Scheduling

각 프로세스들에게 우선순위를 부여하고, 높은 우선순위를 가진 프로세스에게 CPU 제어권을 할당하는 방법입니다.
SJF, SRJF도 일종의 Priority Scheduling이라고 할 수 있습니다.

이 방법도 역시 우선순위가 낮은 프로세스가 제어권을 얻지 못하는 기아 현상이 발생하는 단점이 있습니다.
그래서 이를 해결하는 방법으로 Aging 이라는 방법이 고안되었습니다.
이는 오래 기다린 프로세스의 우선순위를 높여주어, 무한정 기다리는 경우를 줄이는 방법입니다.

RR(Round Robin)

각 프로세스가 동일한 할당 시간(time quantum)을 가지는 방법입니다.
이 방법은 작업이 끝나지 않더라도 제어권을 뺏어오는 방법이기 때문에, preemptive 한 방법입니다.

프로세스는 할당된 시간을 모두 소모하면 제어권을 다음 프로세스에게 넘겨주고, ready queue의 제일 뒤로 가서 기다립니다.

Round Robin은 할당시간을 적당히 조절하는것도 중요한데요.
이유는 다음과 같습니다.

단위 시간이 큼
- 공정하게 시간이 분배되지 않을 가능성이 크다.
  (FCFS 처럼 동작할 가능성이 높음)
단위 시작이 작음
- 너무 잦은 context switch로 인한 오버헤드의 증가로 CPU 성능이 저하됨
  (CPU 이용률이 감소함)

Round Robin은 끝나지 않아도 제어권을 뺏어오기 때문에, 한 프로세스가 완료되는데 걸리는 시간이 상대적으로 깁니다.
이를 정리하면 평균 처리량은 SJF보다 길지만, 응답 시간은 더 짧다고 할 수 있습니다.

Multilevel Queue

지금까지의 스케줄링 방식들은 한 종류의 ready queue만 있다는 가정하에 설명되었습니다.
하지만, ready queue를 특성에 따라 분리할 수 있는데요.
아래에서 알아보겠습니다.

foreground : 상호작용이 필요한 프로세스
- 상호작용은 짧은 응답시간이 중요하기 때문에 RR 로 스케줄링 합니다.
background : 상호작용이 필요없는 프로세스
- 짧은 응답시간이 필요없기 때문에 FCFS

Multilevel Feedback Queue

Multilevel Queue 처럼 특성에 따라 여러가지로 나눠서 ready queue를 관리하는 방법인데요.
이와 다른점은 프로세스가 다른 큐로 이동이 가능하다는 점 입니다.
(예를들면, Aging 같은 방식)

Multilevel-feedback-queue-scheduler를 정의하는 요소들

Queue의 수
각 큐의 scheduling algorithm
프로세스를 상위 큐로 보내는 기준
프로세스를 하위 큐로 보내는 기준
프로세스가 CPU 서비스를 받으로 할 때 들어갈 큐를 결정하는 기준

위는 Multilevel Feedback Queue의 한 예시입니다.

첫번째와 두번째 Queue의 알고리즘은 RR입니다.
첫번째 큐로 들어왔을때 8의 시간동안 처리를 완료하면 큐를 나가겠지만. 처리할 작업이 남았다면 하위 큐로 이동합니다.
두 번째 큐에서는 더 긴 시간을 할당받는데, 그래도 처리를 하지 못하면 다시 세번째 큐로 이동합니다.
세번째 큐는 FCFS 스케줄링 방식을 사용하기 때문에, 자신의 작업을 모두 처리하게 됩니다.

첫번째와 두번째 큐는 preemptive 한 스케줄링 방식이기 때문에, 작업이 끝나지 않아도 다음 큐로 쫒겨납니다.
하지만 마지막 세번째 큐로 오게되면 nonpreemptive 하기 때문에, 자신의 작업 시간을 보장받게 됩니다.
그리고 이 예시의 세번째 큐는 상위 큐로 가는 방법(기준)이 없기 때문에, 해당 큐에서 처리가 완료될 수 있도록
FCFS를 사용한 것을 알 수 있습니다.

저작자표시 비영리 변경금지

JW공부스토리