[운영체제] Cpu Scheduling(공룡책 스터디 정리)

본 포스팅은 인프런 공룡책 강의를 기반으로 한 스터디 개인 정리를 위한 포스팅입니다.
잘못된 부분이 있다면 언제든 지적해주시면 감사하겠습니다!

Concept

멀티 프로그래밍 된 운영체제에서 적용하는 개념

💡 멀티 프로그래밍이란?

⇒ 한 개의 프로세서가 하나의 프로세스를 수행하는 동안 다른 프로세스에 접근할 수 있도록 하는 방법

⇒ 멀티 프로그래밍을 하려면 CPU의 처리속도가 빠르고 남는 시간이 있는 경우 Context Switching을 통해 다수의 프로세스를 접근할 수 있어야 함.

• 간단하게 설명해서 Ready Queue에 있는 프로세스들 중에 어떤 것을 Running Queue에 넣어 CPU할당을 시킬 것인지를 CPU Scheduling이라 함.
• 단순히 FIFO-Queue를 통해 먼저 큐에 들어온 프로세스에 대해 우선순위를 주는것 외에 작업 우선순위를 선정하는 기준에 신경써주어야 할 부분들이 많기 때문에 CPU Scheduling이 중요한 포인트가 됨.

---

용어 정리

CPU burst

- CPU 명령을 실행하는 것. (CPU를 대량 사용하는 경우에도 사용되는 용어)

CPU-burst Time

- 해당 프로세스가 CPU를 할당받고 끝날 때까지의 소요시간.

CPU-bound-Process

- CPU burst가 큰 프로세스 (CPU를 많이 잡아먹는 프로세스)

I/O burst

- I/O를 요청한 다음 기다리는 시간.

I/O-bound-Process

- I/O burst가 큰 프로세스

---

CPU Scheduling의 목적

CPU의 이용률(Utilization)의 증가

• CPU가 놀지 않도록 최대한 많은 사용량을 챙길 수 있도록

Troughput

• 단위시간 당 완료한 프로세스의 수를 최대화

Turnaround time

• 프로세스가 실행되고 종료될 때 까지의 시간을 최소화
• 하나의 작업을 얼마나 빠르게 마무리 하느냐의 기준

Waiting time

• 프로세스가 Ready Queue에서 대기하고 있는 시간의 합을 최소화
• 프로세스가 작업을 (마무리하는데까지 걸리는 시간 - CPU BurstTime)이라고 볼 수 도 있긴함.

Response time

• 사용자 관점에서 작업 요청 후 응답이 오는데 걸리는 응답시간을 최소화 (마우스 10번 클릭 시 9번만 클릭되는 경우는 Response time이 느린 것.)

---

 

Basic Concept

CPU Scheduling에는 아래 두 가지 종류가 있음.

---

Preemptive vs Non-Preemptive

Non-Preemptive(비선점)

• 프로세스가 Running 큐에서 자발적으로 나오기 전까지는 계속 쓰도록 내버려두는 것.

Preemptive(선점)

• CPU가 동작중인 프로세스를 어떤 이유에 의해서 쫒아낼 수 있다는 것.

다음 4가지 상황들에 대해

1. Running → Waiting (IO작업)

2. Running → Ready

3. Waiting → Ready

4. Running → Terminated(프로세스가 종료될 때)

• 1번과 4번은 Non-Preemptive
• 2번과 3번은 Preemptive or Non-Preemptive 둘 중 한 가지 방식을 적용가능.

 

---

Dispatcher

정의

실질적으로 Context Switch(문맥 교환)을 해주는 모듈

개념

CPU Scheduling에 의해 CPU할당을 할 프로세스를 정했다면 Dispatcher에 의해 현재 작업 수행중인 프로세스의 PCB를 저장하고, 다음 프로세스의 PCB를 불러오는 과정(Context Switch)을 수행

Dispatcher Latency

• Context Switching delay
• 순수 overhead (즉 쓸데없는 시간)
• latency가 짧을 수록 시스템의 효율성은 빠름

대부분 작업관리자를 열어 CPU가 100% 할당이 되는 경우는 이러한 dispatcher만 수행하다 정작 CPU할당 및 작업이 진행되지 않아 발생하는 경우.

 

---

CPU Scheduling 방식

💡
Waiting Time : 해당 프로세스가 CPU할당을 받기까지의 시간
Turnaround Time : 해당 프로세스가 (Ready Queue에 들어오고 난 후부터) 종료되는 시점의 시간

두 개의 시간 모두 모든 프로세스에 대해 total time, AVG time이 존재 AVG Time의 최적화가 CPU Schaduling의 목표

 

 

 

위 그림은 간트차트를 나타내는 그림

해당 간트차트를 통해 Waiting time 및 turnaround time을 계산할 수 있음.

---

1. FCFS

Non-Preemptive(비선점) 방식

먼저 온 프로세스를 가장 먼저 처리하는 방식 (초창기 방식)

해당 스케쥴링 방식은 간단하지만 가장 큰 문제점인 호송 효과(Convoy Effect) 발생 가능

 

호송효과란 ?
순차적으로 처리하는 스케쥴링의 방식에서 먼저 온 프로세스의 소요시간이 매우 클 경우 해당 프로세스를 처리하느라 뒤에 상대적으로 짧은 프로세스들의 대기시간이 길어지는 상황을 뜻함.
일명 똥차효과라고도 함(편도 1차선 도로에서 맨 앞 차가 늦게 갈 경우 뒤따르는 스포츠카들 마저도 늦게 가야하는 상황)

---

2. SJF (Shortest-Job-First)

Non-preemptive(비선점)

각 프로세스의 next-cpu-burst의 길이를 가지고 계산

Ready Queue에 들어오는 순서와 무관

이 방식은 가장 짧은 waiting time을 보장해준다는 장점이 있음.

 

💡
해당 방식의 문제점으로는
1) Starvation(공복) 문제가 있다. ⇒ 계속해서 실행시간이 짧은 프로세스들이 들어온다면 상대적으로 실행시간이 긴 프로세스는 starvation 발생
2) CPU burst time을 미리 측정하기 힘들다. ⇒ SJF 방식을 사용하려면 현재 큐에있는 프로세스들의 CPU burst time을 알아야하는데, 이걸 미리 아는것은 어려우므로 SJF를 쓰기 곤란하다.

 

---

3. SRTF (Shortest Remaining Time First)

SJF의 preemptive 버전

어떤 새로운 job이 들어왔을 때, 각 task의 남은 시간을 따져보고 가장 짧은 녀석에게 CPU를 할당

 

⚡ 예를 들어 0초 시점에 10초짜리의 작업을 수행하는 프로세스가 들어와서 CPU를 사용하고 있다가, 3초 시점에 6초 프로세스가 들어온다면 Context Switching 발생, 8초 프로세스가 들어온다면 기존 프로세스가 계속 선점.

---

3. RR (Round-Robin)

시분할 시스템을 위해 설계된 preemptive(선점형) 스케쥴링 방식

프로세스들 사이에 우선순위를 두지 않고(like FCFS), 순서대로 시간단위로 CPU를 할당하는 방식

 

⚡ 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU를 독점하지 않고 공평하게 이용될 수 있게 한다.

Example

예를 들어, 아래와 같이 4개의 프로세스가 주어지고 시간 할당량은 3으로 가정하자.

도착시간     0 1 2 3
프로세스     A B C D
CPU 사이클  6 3 1 4

처음에는 프로세스 A만 도착했으므로 바로 디스패치하여 실행시킨다. 시간 할당량 3이 지날 동안 프로세스 A는 계속 실행 중이고 준비 큐에는 프로세스 B,C,D가 순서대로 도착하여 기다리고 있다. 따라서 RR 알고리즘은 프로세스 A를 준비 큐의 맨 뒤로 배치시키고 다음 차례인 프로세스 B를 디스패치하여 실행시킨다.

시간 할당량 3이 지나는 동안 프로세스 B도 마침 종료를 하게되어 다음 순서인 프로세스 C를 디스패치하여 실행시킨다. 프로세스 C는 1만큼의 시간 만에 종료되어 바로 다음 순서인 프로세스 D를 디스패치하여 실행시킨다.

다시 시간 할당량 3이 지나도 프로세스 D는 종료하지 못하여 RR 스케줄링은 프로세스 D를 준비 큐의 맨 뒤로 배치시키고, 다음 차례인 프로세스 A를 디스패치하여 실행시킨다.

시간 할당량 3이 지나면 A도 종료가 되고, 마지막으로 프로세스 D를 디스패치하여 실행시키면 1만큼 지난 뒤 종료된다. 최종 결과는 아래와 같다.

0     3     6   7   10   13  14
|  A  |  B  | C | D |  A  | D |

각 프로세스가 준비 큐에 있었던 시간인 대기시간은, 프로세스 A는 3부터 10 사이인 7이 되고, 프로세스 B는 1(도착시간 기준)부터 3 사이인 2로, 프로세스 C는 2부터 6사이인 4, 프로세스 D는 3부터 7사이와 10부터 13 사이이므로 4+3=7이 된다.

그리고 반환시간은 프로세스 A는 13-0=13, 프로세스 B는 6-1=5, 프로세스 C는 7-2=5, 프로세스 D는 14-3=11이다. 아래는 프로세스의 대기시간과 반환시간을 정리한 것이다.

프로세스 A B C D
대기시간 7 2 4 7
반환시간 13 5 5 11

따라서 평균 대기시간은 (7+2+4+7)/4=5 이고, 평균 반환시간은 (13+5+5+11)/4=8.5가 된다.

 

성능

• 평균 CPU 소요시간에 대한 시간 간격 길이에 따라 달라짐.
• 간격이 너무 큰 경우 = FCFS
• 간격이 너무 짧은 경우 = 잦은 문맥교환(오버헤드 증가)
• 일반적인 규칙으로
  • 80%의 CPU 사이클을 처리할 수 있도록
  • 문맥교환에 걸리는 시간보다 100배 정도 길게 (문맥교환만 하다가 끝나지 않도록)

💡 요약

RR Scheduling

• 선점 스케줄링 알고리즘
• 준비 큐에 도착한 순서에 따라 디스패치하지만
• 정해진 시간 할당량에 의해 실행을 제한
• 시간 할당량 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치 • 대화형 운영체제에 유용

장점

• CPU를 독점하지 않고 공평하게 이용
• 대화형 운영체제에 유용

단점

• 시간 할당량이 너무 크면 FCFS 스케줄링과 같아짐
• 시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함

---

5. Priority Scheduling

말 그대로 우선순위가 높은 프로세스를 먼저 할당하는 방식

해당 방식의 고려할 점은 우선순위의 기준을 정하는 것!

또한 preemptive하게 할건지 Non-preemptive하게 할건지.

• 측정 가능한 변수들을 통해 결정
• 시간 제한, 메모리 요구량, 열린 파일의 수, 평균 I/O Burst비율 등

Starvation 문제 또한 고려해야함. (SJF의 경우와 마찬가지)

• Ready queue에 있는 우선순위가 낮은 프로세스의 경우 발생 가능

💡 Starvation -> Aging을 통해 해결

프로세스마다 나이라는 개념을 적용해서 어느 순간에는 할당을 받을 수 있도록.

---

6. RR and Priority Scheduling

높은 우선순위 프로세스를 중점으로 두되 같은 우선순위를 가진 프로세스에 대해서는 RR방식으로 적용

---

7. Multi-Level Queue(MLQ) Scheduling

분리되있는 Ready Queue에 각각의 우선순위를 두고 스케쥴링

 

위에서부터 순차적으로 CPU할당

But, 아래있는 Queue의 프로세스들은 할당이 안 될 수도 있음. (Starvation 문제)

 

이러한 Starvation문제에 대해 위 그림처럼 Time Quantum을 임의적으로 설정하여 모든 프로세스들에게 CPU 할당이 어느정도 가능하도록 해결할 수 있음.

 

---

Thread Scheduling

현대에 들어서는 프로세스가 아닌 커널 쓰레드를 활용하기 때문에 위의 방식들이 사용되지 않음.

지금까지 봐왔던 Scheduling 방식들을 커널 쓰레드에 적용.

 

---

Real-Time CPU Scheduling

프로세스의 deadline을 고려하여 스케줄링하는 알고리즘

Soft Realtime

• DeadLine 만족을 보장하지 않음.
• 중요한 실시간 프로세스가 그렇지 않은 프로세스에 비해 우선권만 가지고 있다.

Hard Realtime

• 데드라인(deadline)을 100% 만족한다는 것을 보장
• 어떠한 한 작업은 정해진 시간안에 반드시 서비스(수행)되어야 함.
  • 데드라인이 지난 후 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일한 결과

---

면접 예상 질문 정리

1. Round Robin 스케줄링에서 Time Quantum이 매우 커지면 어떻게 동작하나요? 반대로 매우 작아지면 어떻게 동작하나요?
2. CPU Scheduling의 방식 중 Priority Scheduling이 Preemptive, Non-preemptive 키워드를 사용하여 간략하게 설명해주세요.
3. 호송 효과 Convoy Effect와 호송 효과가 발생할 수 있는 스케줄링 알고리즘에 관해 설명해주세요

---

Refference

https://www.inflearn.com/course/운영체제-공룡책-전공강의

[지금 무료] 운영체제 공룡책 강의 - 인프런 | 강의