9. CPU Scheduling 1

운영체제

9. CPU Scheduling 1

홍비 2022. 2. 19. 18:09

이화여자대학교 반효경 교수님의 운영체제 강의 10강을 듣고 정리한 내용이다.

📄 Process Management 복습

컴퓨터 프로그램이 실행되면, CPU에서 instruction 실행과 오래 걸리는 I/O 작업 실행이 번갈아가면서 실행됨
CPU burst가 짧다 = I/O가 끼어드는 시간 多
CPU burst는 모든 프로그램이 동일하지 않고, 짧거나 긴 프로그램이 섞여 있음 → CPU Scheduling이 필요한 이유
- ready queue에 들어와있는 프로그램 중 CPU 넘겨줄 프로그램을 선정(결정)
- 이 때, 고려할 것은 두 가지
  1. 누구에게 CPU를 넘겨줄 것인가
  2. 준다면, 계속 쓰게 할 것인가 아니면 중간에 CPU를 뺏어올 것인가
- CPU scheduling은 크게 두가지로 나뉨
  1. Non-preemptive (비선점형) ; Cooperative(협조적) - 한 프로세스가 CPU에 할당되면, 프로세스가 종료 혹은 대기 상태에 전환될 때까지 CPU 점유
  2. Preemptive (선점형) - 거의 대부분에서 사용됨

✏️ Scheduling Criteria(= Performance index, Performance measure; 성능 척도)

CPU Scheduling의 성능을 평가하기 위한 척도로, 두 가지로 분류됨
1. 시스템 입장에서의 성능 척도 - CPU Utilization, Throughput
2. 프로그램 입장에서의 성능 척도 - Turnaround time, Waiting time, Response time

1. 시스템 입장에서의 성능 척도

- CPU Utilization(CPU 이용률)

Keep the CPU as busy as possible(= CPU를 가능한 한/바쁘게 일을 시켜라)
전체 시간 중 CPU가 놀지 않고 일한 시간의 비율
개념상 CPU 이용률은 0~100%이나, 실제 시스템 상에서는 40~90%의 범위 가짐

- Throughput(처리량)

# of processes that complete their execution per time
단위 시간당 처리할 수 있는 업무 단위량(= 시간당 몇 개의 작업을 처리하는가?); 단위 시간당 완료된 프로세스의 개수
긴 프로세스의 경우 몇 초에 한 프로세스, 짧은 트랜잭션인 경우 초당 수십개의 프로세스 완료

2. 프로그램 입장에서의 성능 척도

- Turnaround time(소요시간, 반환시간; 총처리 시간)

amount of time to execute a particular process
CPU를 사용하러 들어와서 ~ CPU를 다 쓰고 나갈 때까지 걸린 시간(프로세스의 제출 시간과 완료 시간의 간격)
작업이 ready queue에 들어가서 나오는 시간의 차이로, 짧아야 좋음
총처리 시간 = 준비 큐에서 대기한 시간 + CPU에서 실행하는 시간 + I/O 시간을 합한 시간

- Waiting time(대기 시간)

amount of time a process has been waiting in the ready queue
순수하게 기다리는 시간
CPU가 서비스를 받기 위해 ready queue에서 얼마나 기다렸는가(준비 큐에서 대기하면서 보낸 시간의 합)
스케줄링 알고리즘은 단지 프로세스가 준비 큐에서 대기하는 시간의 양에만 영향을 줌

- Response time(응답 시간)

amount of time it takes from when a request was submitted unit the first response is produced, not output(for time-sharing environment)
ready queue에 들어와서 처음으로 최초의 CPU를 얻기까지의 시간
첫 응답이 나올 때까지(시작되는 데까지) 걸리는 시간(응답을 출력하는 데 걸리는 시간이 아님)
가장 중요한 성능 척도

📌 처음으로 CPU를 얻는 시간이 사용자 응답과 관련해 매우 중요한 개념임

ex) 중국집 운영

<사장의 입장 (시스템의 입장)>

Utilization - 높으면 좋음. 고용주의 입장에서는 주방장이 놀지 않고 많이 일하면 좋음
Throughput - 높으면 좋음. 중국집에서 단위 시간당 손님을 몇 명 먹여 내보냈는가

<손님의 입장 (프로그램의 입장)>

Turnaround time - 고객이 중국집에 와서 주문 후 식사를 받고 다 먹고 나가는 시간까지
Waiting time - 밥 먹은 시간이 아닌 기다린 시간들
Response time - 첫 번째 음식이 나올 때까지 기다린 시간

→ 즉 CPU 이용률과 처리량을 최대화하고, 총처리 시간, 대기 시간, 응답 시간을 최소화 하는 것이 바람직함

✏️ Scheduling Algorithms

FCFS(First-Come First-Served, 선입선출; FIFO, First-In First-Out)
SJF(Shortest Job First; 최단 작업 우선 스케줄링)
SRTF(Shortest-Remaining-Time-First; 최소 잔류 시간 우선 스케줄링)
Priority Scheduling(우선순위 스케줄링)
RR(Round Robin)
Multilevel Queue(다단계 큐)
Multilevel Feedback Queue(다단계 피드백 큐)

1. FCFS(First-Come First-Served)

비선점형 Scheduling
- 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하든지 또는 I/O 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU 점유

만약 작업시간이 긴 프로세스가 먼저 도착하면, 뒤에 온 프로세스들은 하염없이 기다림 → 그닥 좋은 스케쥴링은 아님
앞에 어떤 프로세스가 있느냐에 따라 성능이 많이 달라짐
Case 2 - Convoy effect (호위 효과) - short process behind long process
- Convoy effect는 1차 세계대전 때 처음 사용됐으며, 컴퓨터 시스템에서는 큐에서 오래 기다리는 현상을 설명하는 용어
- 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것
- 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳음
대화영 시스템에서 특히 문제가 됨

2. SJF(Shortest-Job-First; 최단 작업 우선)

선점형이나 비선점형일 수 있음
SJF is optimal
- 주어진 프로세스들에 대해 minimum average waiting time(최소의 평균 대기 시간)을 보장
- 짧은 프로세스를 긴 프로세스의 앞으로 이동함으로써, 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가하는 것보다 더 많이 줄일 수 있음
각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용함
두 가지 경우가 있음
1. Non-preemptive - 일단 CPU를 잡으면 이번 CPU burst가 완료될 떄까지 CPU를 선점당하지 않음
2. Preemptive - 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗기며, 이 방법은 Shortest-Remaining-Time-First(SRTF)라고도 부름

비선점 SJF는 CPU를 다 쓰고 나가는 시점에서 Scheduling을 할지 말지 결정
선점 SJF는 새로운 프로세스가 도착하면 Scheduling을 결정
SJF의 average waiting time은 어떠한 알고리즘을 사용하더라도 3초(위의 예제)보다 더 적은 waiting time은 없음
SJF의 문제점 두 가지
1. SJF는 극단적으로 CPU 사용 시간이 짧은 job을 선호함 - CPU 사용시간이 긴 프로세스는 영원히 작업을 못할 수 있음(기아 현상;Starvation)
2. CPU 사용 시간을 미리 알 수 없음 - CPU를 과거에 얼마나 썼는지로 예측 가능(비슷한 패턴을 나타내므로, 과거의 흔적을 가지고 추정)

* 다음번 CPU Burst Time의 예측

다음번 CPU Burst Time은 어떻게 알 수 있는가? → input data, branch 등
과거의 CPU burst time을 이용해서 추청이 가능(=exponential averaging)
- $t_{n}$ - length of the $ n^{th} $ CPU burst (가장 최근의 CPU burst 값, 즉 실제 CPU 사용 시간)
- $\tau_{n}$ - CPU burst의 예측값
- $\tau_{n+1}$ - 다음 CPU burst의 예측값
- $\alpha$ - 최근 값과 과거의 값에 대한 가중치($0\leq \alpha \leq 1$)
- 즉, 예측값 $\tau_{n+1}$을 구하는 공식은 $\tau_{n+1} = \alpha t_n + (1-\alpha) \tau_{n} $

** Exponential Averaging

미래 예측 시에 많이 사용하며, 과거 데이터와 최근 데이터의 비율을 적절히 반영
$\alpha=1$이면,
- $\tau_{n+1} = \tau_{n}$
- 과거 기록을 전적으로 의지(recent history does not count)
$\alpha=0$이면,
- $\tau_{n+1}=t_{n}$
- 최근 CPU burst time 값에 의지(Only the actual last CPU burst counts)
전개를 해보면 최근의 값에 더 가중치를 많이 주는 것을 확인할 수 있음

3. Priority Scheduling

우선순위 스케줄링
A priority number(integer) is associated with each process
highest priority를 가진 프로세스에게 CPU 할당(smaller integer = highest priority)
우선순위가 높은 프로세스가 오면 CPU를 뺏을 수 있느냐의 관점에 따라 preemptive / nonpreemptive 두 가지 종류로 나뉨
우선순위가 같은 프로세스들은 선입선처리 순서로 스줄
SJF도 일종의 priority scheduling
- priority = predicted next CPU burst time
문제점 - Starvation(기아 현상) : low priority processes may never execute
해결방법 - Aging(노화) : as time progresses increase the priority of the process

4. RR(Round Robin)

현대 시스템의 CPU Scheduling은 RR에 기반
선점형 스케줄링
각 프로세스는 동일한 크기의 할당 시간(time quantum; time slice)을 가짐(일반적으로 10~100ms)
할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에 가서 다시 대기
- 유일하게 실행 가능한 프로세스가 아니라면 두번 이상의 시간 할당량을 할당받는 프로세스는 없음
n개의 프로세스가 ready queue에 있고 할당시간이 $q$ time unit인 경우, 각 프로세스는 최대 $q$ time unit 단위로 CPU 시간의 $1/n$ 을 얻음
- 어떤 프로세스도 $(n-1)q$ time unit 이상 기다리지 않음
RR 알고리즘의 성능 및 총처리 시간은 시간 할당량의 크기에 매우 많은 영향을 받음
할당시간 $q$를 크게 잡으면 FCFS, 작게 잡으면 Context Switch 오버헤드가 커짐
일반적으로 SJF보다 average turnaround time은 길지만, response time은 더 짧아짐
CPU 버스트의 80%은 시간 할댱량보다 짧아야 함(운영체제 책 발췌)

저작자표시