강의 링크 : https://core.ewha.ac.kr/publicview/C0101020140328151311578473?vmode=f

모든 프로세스들은 I/O 버스트 가 일어난다.

I/O 버스트
I/O 실행으로 인해 명령을 보내고 명령을 기다리는 과정
CPU 버스트
프로세스가 CPU 에게 자원을 할당받아 명령을 수행하는 과정

프로세스들은 I/O 버스트가 더 많은 프로세스들도 있고 CPU 버스트가 많은 프로세스들도 존재한다.

프로세스 별 CPU의 자원을 필요로 하는 정도 , I/O 가 일어나는 정도가 모두 다르기 때문에

이러한 특징에 따라서 프로세스에게 CPU의 자원을 적절하게 분배해야 하며 이러한 기술을 CPU Scheduling 이라 한다.

CPU Scheduling Algorithm

다양한 CPU 스케줄링 기법이 있는데 크게 두 범주로 나누면

자진 반납을 할 때 까지 CPU 를 강제로 뺏지 않는 방법 [비선점형] , 자진반납이 끝나지 않아도 강제로 뻇는 방법 [선점형] 이 이 있다.

기준	설명
우선순위 스케줄링	작업에 우선순위 수준을 할당하고, 그 우선순위에 따라 작업을 스케줄링합니다.
라운드 로빈 스케줄링	각 작업에 고정된 시간 슬롯을 할당하고, 작업은 순환적으로 스케줄링됩니다.
먼저 온 순서대로 스케줄링 (FCFS)	작업은 도착한 순서대로 스케줄링되며, 먼저 도착한 작업이 먼저 스케줄링됩니다.
최단 작업 다음 (SJN) 스케줄링	작업의 실행 시간을 기준으로 하여, 가장 짧은 실행 시간을 가진 작업이 먼저 스케줄링됩니다.
다단계 큐 스케줄링	작업을 다양한 우선순위 수준의 여러 큐로 구성하고, 우선순위에 따라 작업을 스케줄링합니다.

다음과 같이 다양한 알고리즘이 존재하는데 이를 평가 할 수 있는 성능 척도들이 존재한다.

Scheduling Criteria

성능 척도	설명
시스템 입장에서의 성능 척도	이용률: CPU가 시스템을 얼마나 효율적으로 사용하는지의 척도 처리량: 단위 시간당 완료된 프로세스의 수
프로그램 입장에서의 성능 척도	평균 대기 시간: 프로세스가 대기하는 시간의 평균 평균 반환 시간: 프로세스의 실행 및 대기 시간을 고려한 평균 반환 시간 응답 시간: 사용자 입력에 대한 시스템의 응답까지 걸리는 시간

와 같은 평가 척도들이 존재한다.

이런 평가 척도도 두 가지로 분류 할 수 있다.

하나는 시스템 입장에서의 성능 척도 , 프로그램 입장에서의 성능 척도로 나눌 수 있다.

• 시스템 입장에서의 성능 척도 : 이용률 , 처리량
• 프로그램 입장에서의 성능 척도 : 평균 대기 시간 , 평균 반환 시간 , 응답 시간

---

CPU Utilization , Throughput (이용률 , 처리량)

가능한 CPU를 바쁘게 일 시켜라 ~~

주어진 시간동안 CPU 가 몇 개의 프로그램을 처리했는가를 평가한다.

Turnaround time (소요시간, 반환 시간)

프로세스 입장에서는 CPU를 받을 때 까지 대기하고 다 사용한 후 I/O 를 하러 자원을 반납 할 때 가지 걸린 시간을 의미한다.

Wating time (대기 시간)

CPU를 쓰고자 하더라도 ready queue 에서 기다리는 시간이 필요하다.

순수하게 줄에 서서 기다리는 시간을 Wating time 이라고 한다.

Response time (응답 시간)

프로그램이 ready queue 에 들어와서 처음으로 CPU 를 얻을 때 까지 기다린 시간을 의미한다.

Wating time 과 뭐가 다른가?

Wating time
선점형 알고리즘같은 경우엔 CPU 자원을 할당 해도 자신의 작업이 끝나지 않았음에도 불구하고 자원을 강제로 반납 당하고 다시 레디큐에서 대기하는 시간들도 존재한다.
이 떄 작업이 끝날 때 까지 기다린 총 시간을 wating time 이라고 한다.

Response time
최초로 ready queue 에 들어와서 CPU 자원을 할당 받을 때 까지의 시간을 의미한다.
Response time 은 사용자 경험에 큰 영향을 미친다.

---

CPU 스케줄링 알고리즘

FCFS (First Come First Served)

먼저 들어온 프로그램 별로 먼저 처리하는 것이다.

Nonpreemptive (비선점형) 스케줄링 기법이다.

이러한 경우 먼저 들어온 프로세스가 CPU Burst 시간이 길고 이후 프로세스들이 I/O Burst 가 긴 경우

첫 프로세스를 기다리느라 많은 시간을 비효율적으로 소비 할 수 있다.

동일한 프로세스들이라고 하더라도 어떤 순서에 따라 왔느냐에 따라 프로세스별 Wating time 이 다르게 된다.

만약 I/O Burst 가 긴 프로세스들이 먼저 왔다면 프로세스를 빠르게 처리하고 CPU 를 반납하겠지만

CPU Burst 가 긴 프로세스들이 먼저 온다면 프로세스를 오랫동안 점유하고 있어 대기시간이 길어진다.

이런 형상을 Convoy effect 라고 한다.

Convoy effect : 매우 짧은 처리 시간을 갖는 프로세스가 긴 처리시간을 갖는 프로세스 다음에서 대기하고 있는 상황

SJF (Shortest-Job-First)

각 프로세스의 CPU Burst 시간을 계산하여 가장 짧은 CPU Burst 를 갖는 프로세스에게 먼저 CPU 를 할당해주는 알고리즘이다.

모두가 행복해져요 ~

CPU Burst 가 짧은 프로세스부터 시작되기 때문에 프로세스 별 Average Wating time 이 짧다.

두 가지 전략으로 사용 될 수 있다.

• Nonpreemptive
  일단 CPU 를 잡으면 CPU Burst가 완료 날 때 까지 CPU 를 선점당하지 않는다.
• Preemptive
  CPU 를 잡고 실행 중에도 더 짧은 CPU Burst 를 가진 프로세스가 들어오면 CPU 를 반납한다.

  이러한 경우를 Shortest-Remaning-Time-First(SRTF) 라 부른다.
  이 때 빼앗긴 프로세스는 레디큐의 맨 앞에 존재한다.

이 때 SJF 는 Average Wating time 을 짧게 하는 Optimal Algorithm 이다.

특히 Preemptive 형태가 그럴 것이다.

NonPreemptive 한 경우에는 프로세스가 선점되어있는 동안 도착한 프로세스 들 중 CPU Burst 가 짧은 순으로 시행된다.

Preemptive 한 경우에는 시행 중이더라도 더 짧은 프로세스가 존재한다면 CPU 를 반납한다.

위 예제와 같은 상황에서 SJF보다 최적의 결과는 나올 수 없다.

엄청나게 좋아보이지만 두 가지 문제점이 존재한다.

Starvation

단어가 상당히 무섭다.

SJF 는 극단적으로 짧은 CPU Burst를 가진 프로세스를 선호한다.

그렇다면 CPU Burst가 매우 긴 프로세스는 영원히 CPU 자원을 받지 못할 수 있다.

자기보다 짧은 CPU Burst를 가진 프로세스들이 우루루루 들어온다면 .. 자기 차례 되기 전에 또 우루루루 들어온다면 ..
쫄쫄 굶어유 ..

다음 CPU Burst time 을 어떻게 예측할 것인데 ?

프로세스가 들어왔을 때 프로세스 별 CPU Burst time 을 완벽하게 예상 할 수 없다.

추정 할 뿐이다.

과거의 프로세스의 CPU Burst time 을 이용하여 지수평활법을 이용하여 추정한다.

프로세들은 항상 유사한 패턴을 보이기 때문에 유사하게 추정 할 수 있다.

$\alpha$ 는 이전 과거들의 가중치를 얼마나 살펴볼 것이느냐에 대한 내용으로 낮을 수록 이전 burst time 을 많이 고려한다.

Priority Scheduling

우선순위 스케줄링으로 우선순위 별로 스케줄링 한다.

이 때 다른 프로세스가 CPU 를 할당하고 있을 때 더 높은 우선순위를 가진 프로세스가 등장 했을 때

CPU를 강제로 반환하면 Premptive , 기다리면 NonPremptive 이다.

우선순위를 결정하는 방법은 다양하며, SJF 도 CPU Burst time을 우선순위로 두는 우선순위 스케줄링이다.

Solution - Aging

이전처럼 우선순위 스케줄링은 우선순위가 낮은 프로세스의 경우 너무 오래 기다리게 되는 문제가 존재한다고 했다.

이런 경우 발생하는 문제를 Starvation 이라고 하였다.

Starvation 을 막기 위해 오래 기다린 프로세스의 경우 우선순위를 높혀준다.

Round Robin (RR)

현대적인 스케줄링은 Round Robin 기법에 기반한 스케줄링 기법을 사용한다.

각 프로세스는 동일한 크기와 할당 시간을 가지며 할당 시간이 지나고 나면 CPU 를 반환한다.

특징

• CPU 를 처음으로 얻을 때 까지의 응답 시간이 빠르다.
  N 개의 프로세스들이 존재하고 프로세스 별 할당 시간이 q 라면 최악의 경우에 N-1 * q 만 기다려도 첫 번째 CPU 를 받을 수 있다.
• 프로세스들의 CPU Burst time 을 예상할 필요가 없다. (절대적인 할당 기간을 기다리기 때문에)
• 할당 시간이 짧은 프로세스들의 경우 조금의 반복 이후에는 레디큐에서 제거되며, 할당 시간이 긴 프로세스는 오랜 기간동안 반복한다.

q 가 클 경우

FCFS와 동일한 알고리즘이 된다.

q가 작을 경우

잦은 context switch 로 인해 오버헤드가 늘어난다.

특별한 케이스를 생각해보자

Round Robin 은 프로세스들의 CPU Burst time 을 예상하지 못할 경우 사용하는 알고리즘이다.

만약 CPU Burst time 이 모두 100초로 동일한 프로세스 10개가 있을 경우

FCFS 나 Round Robin 을 사용하면 모두 $1000$초가 되는 순간 레디큐에 존재하는 프로세스들이 사라질 것이다.

100초 사용, 100초 사용 .... 100초 사용

하지만 차이점은 Round Robin 은 시분할 형태로 990초부터 프로세스들이 종료되고 사라지고

FCFS 는 프로세스 별 CPU Burst time 만큼 사용한 경우 하나씩 종료되어 사라진다.