# 10. CPU 스케줄링

[ CPU 스케줄링 ]

 

 

CPU 기능

- CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리 장치.

- 프로그램이 시작되어 메모리에 올라가면, 프로그램 카운터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가리킴

- CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행하게 된다.

 

# CPU 버스트, I/O 버스트

+ CPU 버스트: 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계 (계산 위주)

- I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

프로그램이 I/O를 한 번 수행한 후 다음번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 작업을 CPU 버스트라고 한다.

+ I/O버스트: I/O작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 작업 (IO의 비중이 큰 작업)

- CPU 스케줄러 : ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

 

# CPU 스케줄러: 준비 상태에 있는 프로세스들 중에 어떠한 프로세스에게 CPU를 할당할지를 결정하는 운영 체제의 코드

CPU 스케줄링이 발생하는 상황

(1) 실행 상태(running)에 있던 프로세스가 I/O 요청 등에 의해 block상태가 되는 경우

(2) 실행 상태에 있던 프로세스(running)가 타이머 인터럽트 발생에 의해 준비상태(ready)로 되는 경우

(3) I/O요청으로 block 상태에 있던 프로세스의 I/O작업이 완료(blocked)되어 인터럽트가 발생하고

그 결과 이 프로세스의 상태가 준비 상태(ready)로 바뀌는 경우

(4) CPU에서 실행 상태에 있는 프로세스가 종료되는 경우(terminate)

 

스케줄러 분류

+ 비선점형 방식 (nonpreemptive)

- CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법을 말한다.

: (1),(4)가 비선점형

+ 선점형 방식 (preemptive)

- 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법을 말한다.

: 타이머 인터럽트

: (2),(3)이 선점형

 

# 디스패처(dispatcher) : 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경 설정을 하는 커널 모듈. / CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.

현재 수행중이던 context를 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다,

* 디스패처 지연시간 : 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간

- 디스패치 지연시간의 대부분은 context switch 오버헤드가 해당

 

# 스케줄링 성능 평가 척도

+ cpu 활용도

cpu가 명령을 수행한 시간의 비율

cpu가 일을 하지 않고 idle 상태에 머무르는 시간을 최대한 줄이는 것이 중요한 목표

+ 처리량

주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수

cpu버스트가 짧은 프로세스에게 우선적으로 cpu를 할당하는 것이 처리량 증가에 도움

+ 소요 시간

프로세스가 CPU 요청 시점부터 CPU 버스트가 끝날 때까지 걸린 시간

+ 대기 시간

프로세스가 CPU 버스트 기간 중 준비 큐에서 기다린 시간의 합

+ 응답 시간

프로세스가 CPU 요청 시점부터 처음으로 CPU를 얻을 때까지 기다린 시간

 

# 스케줄링 알고리즘

+ FCFS (First Come First Serve)

 

 

 

 

 

 

프로세스가 ready queue에 도착한 시간 순서대로 cpu에 할당하는 방식

프로세스가 자발적으로 cpu를 반납할 때까지 cpu를 선점하지 않는다.

cpu 버스트가 긴 프로세스 하나가 cpu 버스트가 짧은 여러개의 프로세스보다 먼저 ready queue에 들어오게 되면 평균 대기 시간이 길어지게 된다. (콘보이 현상)

cpu 버스트가 짧은 프로세스가 여러개 들어오면 평균 대기 시간이 짧아진다

 

+ SJF (Shortest Job First) _비선점형

 

 

 

 

 

 

 

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 cpu를 할당하는 방식

평균 대기 시간을 가장 짧게하는 알고리즘으로 알려져 있다

선점형,비선점형으로 구현할 수 있다. (선점형 구현방식 : SRTF)

- ready queue에 도착한 프로세스가 가장 짧은 CPU 버스트를 가지고 있어서 CPU를 할당받고 작업중인데, CPU버스트가 더 짧은 프로세스가 도착한다면?

- 비선점형 방식에서는 현재 CPU를 점유하고 있는 프로세스가 CPU버스트를 모두 수행하고 스스로 CPU를 내어놓을 때까지 스케줄링을 하지 않는다.

- 선점형 방식에서는 CPU 버스트 시간이 더 짧은 프로세스에게 할당하게 된다.

cpu 버스트가 긴 프로세스는 ready queue에서 무한정 기다려야 하는 문제가 발생할 수 있다. (기아현상 (starvation))

cpu 버스트가 긴 프로세스들은 전체 시스템 성능 향상을 위해 희생

 

+ 우선순위 스케줄링 (proiroty scheduling)

 

 

 

 

 

 

 

우선 순위가 가장 높은 프로세스에게 제일 먼저 cpu를 할당하는 방식

우선순위는 priority number를 통해 표시하며 우선순위 값이 작을수록 높은 우선순위를 가지는 것으로 가정

비선점,선점형으로 구현 가능 // SJF는 일종의 우선순위 스케줄링

starvation 현상(낮은 우선 순위는 절대 실행되지 않는다.)을 막기위해서 aging기법 사용

- aging 기법: 기다리는 시간이 길어지면 우선순위를 조금 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 하는 방법

 

 

+ 라운드 로빈 스케줄링 (RR // round robin)

 

 

 

 

 

 

 

 

 

- 각 프로세스가 동일하게 cpu를 연속적으로 사용할 수 있는 시간이 특정 시간(할당 시간)으로 제한되며, 이 시간이 경과하면 이 프로세스로부터 cpu를 회수해 준비큐에 줄 서 있는 다른 프로세스에게 할당

- 시간을 초과한 프로세스는 ready queue의 가장 뒤로 들어가서 다음 차례를 기다린다.

- 할당시간을 길게하면 FCFS와 같은 결과를 나타냄 (CPU 버스트가 긴 프로세스가 오랜시간동안 점유하므로)

- 반면, 할당시간을 너무 짧게하면 context switch가 자주 발생해서 오버헤드가 커진다.

따라서 수십 밀리세컨드 정도의 규모로 설정

- 할당 시간이 완료되어 cpu를 회수하는 방법으로는 타이머 인터럽트를 사용하게 된다.

- cpu 버스트 시간이 할당시간보다 짧으면 버스트시간만큼 사용한 후 스스로 cpu 반납

 

 

 

+ 멀티 레벨 큐 (multi level queue)

priority

1 system processes high

2 interactive processes

3 interactive editing processes

4 batch processes

5 student processes low

 

 

큐를 여러개로 분할해 관리하는 스케줄링 기법

- reqdy queue는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 (back-ground queue)로 분할하여 운영

- 전위큐에서는 응답시간을 짧게하기 위해 Round Robin 을 사용, 계산 작업 위주인 후위 큐에서는 FCFS기법을 사용 (계산작업 위주의 프로세스는 응답시간이 큰 의미를 가지지 않음)

- 어느 큐에 먼저 cpu를 할당할 것인지를 결정하는 스케줄링이 필요

* 고정 우선순위 방식(fixed priority scheduling)

큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐가 비어 있을 때에만 서비스

전위 큐에 있는 프로세스에게 cpu를 먼저 할당하고, 전위 큐가 비었을때만 후위 큐 에게 cpu를 할당

* 타임 슬라이스(time slice)

기아 현상을 해소할 수 있는 방법

각 큐에 cpu 시간을 적절한 비율로 할당

예를들어, 전위 큐에는 80%의 시간을 후위 큐에는 20%의 시간을 할당

 

 

 

 

 

 

 

+ 멀티 레벨 피드백 큐 (multilevel feedback queue)

 

파라미터 : Queue의 수 / 각 큐의 스케줄링 알고리즘 / 프로세스를 상위 큐로 보내는 기준

/ 프로세스를 하위 큐로 내쫓는 기준 프로세스가 CPU 서비스를 받으려 할 때, 들어갈 큐를 결정하는 기준

 

 

 

 

 

 

 

 

CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티 레벨 큐 와 동일

프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다른다.

aging 기법을 활용해서 멀티 레벨 피드백 큐 방식으로 구현 가능

우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식

 

 

+ 다중 처리기 스케줄링

다중 처리기 시스템(multi processor system) 에서는 cpu가 여러개 이기 때문에 cpu가 큐에서 프로세스를 꺼내가는 메커니즘이 필요

cpu를 줄세우는 방식을 사용하면, 일부 cpu에 작업이 편중되는 현상이 발생할 수 있어서 cpu 별로 부하분산 시키는 매커니즘 필요

대칭형 다중 처리(symmentric multi processing)와 비대칭형 다중 처리(asymmetric multiprogramming)으로 나눌 수 있다.

대칭형은 cpu가 각자 알아서 스케줄링 결정하는 방식

비대칭형은 하나의 cpu가 다른 모든 cpu의 스케줄링 및 데이터의 접근을 책임지고 나머지는 거기에 따라 움직이는 방식

 

 

+ 실시간 스케줄링

time sharing system에서는 작업의 처리가 빠를수록 좋지만 특정 시간 이내에 처리하지 못했다고 심각한 문제가 발생하지 않음

hard real time system은 시간이 정확히 지켜져야 하므로 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링 되어야 한다. (원자로 제어, 미사일 발사 등등)

soft real time system은 데드랑니이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않는다 (멀티미디어 스트리밍)

hard real time system에서는 먼저 온 요청을 먼저 처리하기보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadling Fisrt) 스케줄링을 널리 사용

 

 

queueing models :확률분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산

 

implementation(구현) & Measurement (성능측정)

: 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교

 

Simulation (모의 실험)

: 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교