SystemProgramming-CPU 스케줄링

1. 알터네이팅 시퀀스

알터네이팅 시퀀스(Alternating sequence)는 번갈아가면서 일어나는 일련의 사건이나 현상을 의미합니다. 컴퓨터에서 CPU 버스트와 I/O 버스트는 알터네이팅 시퀀스의 예시입니다.

 

2. CPU Burst Cycle

 

 

CPU Scheduler

일반적으로는 레디큐에서 순서대로 들어온 ready상태의 프로세스를 선택합니다.

 

이 결정은 언제 일어날 수 있습니다.
(1) 프로세스가 실행에서 대기 상태로 전환됩니다(예: I/O 요청),
(2) 프로세스가 실행에서 준비 상태로 전환(예: 시간 슬라이스 만료)(3) 프로세스가 대기에서 준비 상태로 전환(예: I/O 완료), 
(4) 프로세스가 종료될때

(1)과 (4)에 따른 일정은 선제적이지 않습니다. (2)와 (3)에 따른 일정은 선제적이다.

 

 

프로세스 스케줄링에서 시간 슬라이스란 CPU가 한 번에 한 프로세스를 실행하는 시간입니다. 일반적으로 운영체제는 시간 슬라이스를 설정하고, 이 시간이 지나면 실행 중인 프로세스를 중지하고 다음으로 실행할 프로세스를 선택합니다. 이때 선택된 프로세스는 준비(Ready)상태인 프로세스 중 하나입니다.

마찬가지로, I/O 요청을 한 프로세스는 실행 중인 상태에서 대기(Waiting) 상태로 전환됩니다. 이때 대기 상태로 전환된 프로세스는 레디큐에서 제외됩니다. I/O 작업이 완료되면 해당 프로세스는 다시 레디큐에 추가되고, 다른 준비 상태의 프로세스보다 우선적으로 CPU를 할당받습니다.

따라서, (2)와 (3)에 따른 프로세스 선택은 선제적(선행적)입니다. 시간 슬라이스 만료 또는 I/O 완료와 같은 이벤트가 발생하면, 이전에 실행 중이던 프로세스와 같은 우선순위를 가진 준비 상태의 프로세스 중 하나가 선택됩니다. 이 선택은 레디큐에서 순서대로 들어온 프로세스가 아니라, 이전에 실행 중인 프로세스와 같은 우선순위를 가진 프로세스 중 하나를 선택하는 것입니다.

 

Dispatcher

디스패처(Dispatcher)는 운영체제에서 프로세스의 실행을 관리하는 중요한 구성요소입니다. CPU 스케줄러가 실행할 프로세스를 선택하면, 그 프로세스에 CPU 제어권을 넘겨주는 역할을 합니다. 이때 디스패처가 수행하는 작업은 다음과 같습니다:

• 문맥 교환(Context Switching): 현재 실행중인 프로세스의 상태를 저장하고, 선택된 프로세스의 상태를 복원합니다. 이는 CPU 레지스터 값 및 관련 정보의 저장 및 복원을 포함합니다.
• 모드 전환(Mode Switching): 디스패처는 CPU를 사용자 모드로 전환합니다. 이는 일반적으로 사용자 프로세스가 운영체제 기능에 접근할 수 없도록 하는 보안 기능입니다.
• 선택된 프로세스 재시작: 디스패처는 선택된 프로세스가 다음에 실행될 위치로 점프합니다.

디스패처의 성능은 Dispatch Latency라는 개념으로 측정됩니다. Dispatch Latency는 디스패처가 현재 실행중인 프로세스를 중지하고 다른 프로세스를 실행하기까지 걸리는 시간을 의미합니다. 이는 CPU 스케줄링의 오버헤드(Scheduling Overhead)로 간주됩니다.

 

스케줄링 기준

CPU 스케줄링은 다양한 기준에 따라 프로세스를 선택하고 CPU 자원을 할당합니다. 이때 사용되는 기준들에 대해 설명해드리겠습니다.

• CPU 사용률(CPU Utilization): CPU를 최대한 이용하도록 스케줄링하는 기준입니다. 이는 CPU가 100% 점유 상태에 있을 때 가장 이상적인 상태입니다. 하지만, 이 기준만으로 스케줄링을 수행하면 다른 기준들에 불이익을 줄 수 있습니다.
• 처리량(Throughput): 단위 시간당 완료되는 프로세스의 수를 측정하는 기준입니다. 이 기준은 시스템의 성능 측정에 중요한 역할을 합니다.
• 회전시간(Turnaround Time): 프로세스가 요청을 제출한 시점부터 완료될 때까지 걸리는 시간입니다. 이 기준은 사용자가 요청을 완료하는 데 걸리는 총 시간을 의미합니다.
• 대기시간(Waiting Time): 프로세스가 준비 큐에서 기다리는 시간을 총합한 값입니다. 이 기준은 사용자가 처리되기까지 기다리는 데 걸리는 시간을 의미합니다.
• 응답시간(Response Time): 프로세스가 요청을 제출한 시점부터 첫 번째 응답이 생성될 때까지 걸리는 시간입니다. 이 기준은 사용자가 응답을 받기까지 걸리는 시간을 의미합니다.

이런 스케줄링 알고리즘의 최종 목표는 아래와 같습니다.1. CPU를 Maximize

2. 처리량 Maximize

3. 회전시간 최소화

4. 대기시간 최소화

5. 응답시간 최소화(평균 응답시간보다의 차이를 최소화)

 

스케줄링 알고리즘 -  FCFS (First Come First-Served)

FIFO와 유사한 구조이다. 프로세스 P1 ~ P3이 존재하고 버스트타임이 24, 3, 3(sec) 일 때.

 

1. 프로세스가 P1, P2, P3순으로 도착했다고 생각해보자,

평균 Waiting Time은 0 + 24 + 27 = 51, 51/3 =17(sec)이다.

 

2. 프로세스가 P2, P3, P1순으로 도착했다고 생각해보자.

평균 Wating Time은 0 + 3 + 6 = 9, 9/3 = 3(sec)이다.

 

1번의 케이스보다 훨씬 낫다. 어떻게 도착했냐에 따라 평균대기시간이 극명하게 나뉜다.

 

Shortest-Job-First (SJF)

가장 적은 CPU burst시간을 가진 애들부터 집어넣는다. 여기에는 두가지 버전이 존재한다.

1. Non-preemptive

process	arrival time(sec)	burst time(sec)
P1  P2  P3  P4	0 2 4 5	7 4 1 4

위의 표와 같을 때,

1. 도착시간이 우선수위 되어 P1 이 먼저 선정된다.

2. P1진행중 P3와 P2, P4 모두 도착하므로. 그중 burstTime이 가장 짧은 순서대로 P3 -> P2 -> P4순으로 진행된다.

이때 평균 waiting Time은 (0+3+6+7)/4 = 4 이다.

 

2. Preemptive SJF 상황일 때

프로세스가 실행중이더라도 우선순위에 따라 burstTime이 짧은 녀석이 도착하면 바로 실행시킨다.

 

P1 P1 P2 P2 P3 P2 P2 P4 P4 P4 P4 P1 P1 P1 P1 P1 P1 순서이다.

 

1. P1은 0에 도착 먼저 실행

2. P2가 2에 도착 P1의 burstTime이 5, P2는 4이므로 P2실행

3. P3가 4에 도착 P1의 burstTime이 2, P3는 1이므로 P3실행

4. P3종료

5. P4가 5에 도착, P2의 bustTime이 2, P4는 4이므로 P2실행

6. P2종료

7. P1의 bustTime이 5, P4는 4 이므로 P4 실행

8. P4종료

9. 남은 P1실행

 

평균 Waiting 시간 

P1 = 9, P2 = 1, P3 = 0, P4 = 2

9 + 1 + 2 = 12, 12/4 = 3

CPU 버스트 시간을 정확히 예측할 수 없을 때 오버헤드가 발생할 수 있습니다.

다음 CPU버스트 시간을 정확히 예측해야한다는 단점이 존재합니다.

 

 

Priority Scheduling

우선순위 스케줄링은 각 프로세스에 우선순위 번호(정수)를 할당합니다.

이후 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당됩니다. 우선순위가 가장 높은 프로세스는 가장 작은 정수 값을 가집니다.

우선순위 스케줄링은 SJF(Shortest-Job-First) 스케줄링의 일종입니다.

SJF 스케줄링은 예측된 다음 CPU 버스트 시간을 우선순위로 사용하는 것입니다.

우선순위 스케줄링의 문제점 중 하나는 Starvation(기아)입니다. 우선순위가 낮은 프로세스는 실행되지 않을 수 있습니다. 이를 해결하기 위해 Aging 기법을 사용합니다. 시간이 지남에 따라 프로세스의 우선순위를 증가시키는 것입니다. 이를 통해 우선순위가 낮은 프로세스가 실행될 기회가 생기게 됩니다.

 

Round Robin (RR)

각프로세스는 CPU타임의 작은 부분을 얻습니다. 보통 10 ~ 100밀리초입니다.

라운드 로빈 알고리즘은 먼저 ready queue에 있는 가장 오래된 프로세스를 선택합니다. 이 프로세스는 시간 할당량 만큼 CPU를 할당받게 되고, 이 시간이 지나면 프로세스는 ready queue의 끝에 다시 추가됩니다. 만약 프로세스가 자발적으로 I/O 요청 등으로 블록 상태(blocked state)로 전환된다면, 다음에 CPU를 할당받을 때 ready queue의 시작부터 다시 수행됩니다.

 

 

process	burst time
P1 P2 P3  P4	3 4 6 2

프로세스와 버스트타임이 위와 같을 때, RR방식으로 스케줄링을 하면.

time quantum of 2 라고 정했을 때

P1 ~ P4까지 2를 먼저 돌린다. 이러면 P4는 완료된다.

P1(1) -> P2(2) -> P3(4) 를 진행한다.

응답시간의 경우 P1 = 0, P2 = 2 P3 = 4 P4 = 6 이고

평균 응답 시간의 경우 0 + 2 + 4 + 6 = 12, 12/4 = 3이다.