CPU 스케줄링

CPU 스케쥴링의 대상은 누구인가?

프로세스와 스레드

멀티 태스킹은 어떻게 가능한가?

CPU가 여러 프로세스들에게 시간을 분할(시분할, Time Slice)하여 

자원을 사용하게끔 동작하여 마치 동시에 실행되고 있는 것과 같이 동작 할 수 있다.

시간을 어떻게 분할하는지에 대한 연구가 CPU 스케쥴링이다.

선점형 스케쥴링? 비선점형 스케쥴링?

선점형 스케쥴링

- 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우

- 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 

장점 : 빠른 응답시간을 요구하는 시분할 시스템에 유용 

단점 : 높은 우선순위 프로세스들이 자주 들어오는 경우 오버헤드를 초래 

비선점형 스케쥴링

- 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유못함(빼앗을 수 없음)

장점 : 모든 프로세스들에게 공정하고 응답시간의 예측이 가능 

단점 : 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 함 

CPU 스케쥴링의 방법들

선점형 스케쥴링

하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 있는 방법. 

1) Round-Robin 기법

FCFS(First Come First Served)에 의해서 프로세스들이 할당됨

서로 다른 프로세스들은 같은 시간을 할당받음

할당된 시간이 지나면 작업이 완료되지 않더라도 중단되고, 다시 큐로 이동

장점 : 시분할 방식에 효과적이며, 골고루 서비스가 가능하고  대화식 시스템에 유리하다.

단점 : 타임 슬라이스 그러니까 시분할이 작으면 문맥교환에 많은 비용이 들어 퍼포먼스가 떨어지게 된다.

2) SRT(Shortest Remaining Time) 스케쥴링

가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다.

작업하는 중이라도 남은 큐 중에 더 짧게 소요 될 수 있다고 판단되는 프로세스가 준비되면

문맥교환 후 그 작업을 수행한다.

단점 : 긴 작업은 SJF(Shortes Job First)보다 오래 걸린다.

3) 다단계 큐(Multi Level Queue) 스케쥴링

- 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법

- 일반적으로 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등의 큐로 나누는 것

- 각 준비상태 큐는 독자적으로 스케쥴링을 할 수 있으므로 특성에 맞는 스케쥴링 기법을 각각 사용 할 수 있다. 

(예를 들어 foreground 작업은 라운드 로빈 스케줄링 방식의 큐에, 일괄처리 작업은 FCFS 스케줄링 방식의 큐에 둔다. 라운드 로빈 스케줄링 방식의 큐에 많은 CPU 시간을 할당할 수 있다.)

- 프로세스가 특정 준비 상태 큐로 이동하게 되면 다른 준비 상태 큐로 이동 할 수는 없다.

- 하위 단계에 있는 프로세스가 작업을 수행 중이더라도 상위 단계에 있는 큐에 작업이 들어오게 되면 컨텍스트 스위칭하여 CPU를 상위단계 큐의 프로세스에 할당해야 합니다.

4) 다단계 피드백 큐(Multi level Feedback Queue) 스케쥴링

다단계 큐 스케쥴링의 다른 큐 사이의 이동이 불가능한 점을 개선하여 만든 스케쥴링

- 각 준비 상태 큐마다 다른 시간 할당량을 부여하며 시간안에 완료되지 못한 작업들은 다음 단계의 큐로 넘어가게 됩니다. (즉, 실행 시간이 긴 작업에게 벌칙을 주는 방식이다. )

- 상위 단계일수록 우선순위가 높고 시간할당량이 작습니다.

- 요구하는 시간이 적은 프로세스, 입출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스을 기준으로 높은 우선순위를 할당하게 됩니다.

- 하위 단계의 프로세스가 작업중이더라도 상위 단계의 큐에 작업이 들어오게 되면 중단하고 상위 단계 작업을 수행하게 된다.

- 가장 최하위 단계의 큐에서는 라운드 로빈(RR) 스케쥴링 기법을 사용합니다.

- 맨 아래에서 너무 오래 머물면 aging 방식 사용

장점 : 적응(adaptive) 메커니즘 (각 큐의 CPU 할당 시간 정할 수 있다)

          가장 널리 사용되고, 일반적인 방법

단점 : 최상의 스케줄러를 정의하기 위한 요소를 찾기 어렵다.

비선점형 스케쥴링

프로세스에게 이미 할당된 CPU를 강제로 빼앗을 수 없고, 사용이 끝날 때까지 또는 

CPU를 할당 받은 프로세스가 스스로 넘길 때까지 기다려야 하는 방법. 

1) FCFS(First Come First Served) 스케줄링 = FIFO(First In First Out) 

대기 큐에 먼저 들어온 작업에게 CPU를 먼저 할당. 가장 간단한 스케쥴링 방법

2) SJF(Shortest Job First) 스케줄링

작업 시간이 가장 적은 프로세스에게 CPU를 먼저 할당하는 기법. 

- 장점 : 가장 짧은 평균 대기 시간을 제공

- 단점 : 실행시간이 긴 프로세스는 실행시간이 짧은 프로세스에게 밀려 무한 연기 상태가 발생         할 수 있다. 

3) HRN(Highest Response ratio Next) 스케줄링

실행시간이 긴 프로세스에게 불리한 점을 보완하여 실행시간+대기시간을 고려한 스케쥴링 기법

- 우선 순위 계산 공식을 활용하여 실행시간이 짧거나, 대기시간이 긴 프로세스에게 먼저 CPU자원을 할당(긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법)

- 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아진다

                  (대기시간 + 서비스를 받을 시간)

☞ 우선순위 = ------------------------------

                       서비스를 받은 시간

4) 기한부(DeadLine) 스케쥴링

프로세스에게 일정한 시간을 주어 그 시간안에 완료되도록 하는 메커니즘이다.

만약 그 시간안에 완료되지 못하면 다시 처음부터 작업을 시작해야 한다. 

5) 우선순위(Priority) 스케쥴링

준비 상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당해주어야 한다.

우선순위가 동일할 경우 FCFS 스케쥴링 기법을 활용한다.

우선순위는 프로세스의 종류나 특성에 따라 다르게 부여 될 수 있다.

가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태(starvation)가 될 수 있다.

스케쥴링의 목표

# 모든 시스템

* 공정성 (Fairness) : 모든 프로세스들에게 공정히 CPU 시간 할당

* 효율성 (Balance) : CPU의 사용률 극대화

 - CPU이용률과 처리량을 최대화하고 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는게 바람직한 스케줄링의 기준이 된다.

# Batch 시스템

- 높은 처리량 (High Throughput) : 시간당 처리되는 작업의 수 높임

- 짧은 반환시간 (Short turnaround time) : 작업이 시스템에 도착해서 완료 되는데 까지의 시간 최소화

# 대화식 시스템

- 짧은 응답시간 (Short Response Time) : 대화식 작업에 빠르게 CPU 할당

# 실시간 시스템

- 데드라인 만족 : 주어진 시간 안에 프로세스가 실행될 수 있게 함

# 상호 모순성

- 스케쥴링의 목표는 상호모순 일 수 있음

- 예를 들어 짧은 응답 시간과, 데드라인 만족은 서로 공존할 수  없음.

- 따라서 어떤 스케쥴링 목표를 세울지는 시스템의 특성에 따라 결정