[운영체제] 4주차: CPU scheduling

모든 프로세스는 하나 이상의 thread로 구성된다. 2개 부터는 Multithread

Multithread는 자원 공유가 쉽다(한 프로세스의 자원을 그냥 읽어오므로)

프로세스끼리 자원공유는 Shared memory나 Message passing 등이 필요함

-> Multiprocess보다는 Multithread가 더 경제적으로 장점이 많다.

 

 

컴퓨터의 CPU는 물리적으로 한계가 있다.

Multiprocessor라도 프로세스의 수가 훨씬 더 많으면 일부 프로세스는 프로세서가 할당될 때까지 기다려야 함

-> 스케줄링이 필요하다.

 

CPU가 쉬는 시간을 조금이라도 더 줄여야 효율이 극대화된다.

: 멀티프로그래밍(이 확장되면 멀티태스킹)

 

메모리에 여러 개의 프로세스를 동시에 올려 필요할 때마다 CPU를 전환해서 프로세스에 할당하는 것

 

 

CPU-I/O Burst Cycle

CPU burst: CPU를 사용하는 시간

I/O burst: I/O를 사용하는 시간

 

최초 실행 시 CPU에 올라감:  CPU Burst

I/O 요청 및 I/O 작업: I/O Burst

 

-> 프로세스는 실행부터 종료까지 CPU Burst와 I/O Burst를 번갈아서 사용함

대부분의 짧은 CPU Burst 몇 개의 긴 CPU Burst로 구성된다.

 

 

 

 

CPU Scheduler

Ready queue에서 어느 프로세스에 CPU를 할당할 것인지 결정

 

스케줄러는 다음 시점에서 CPU 할당을 결정한다.

① Running -> Wating: CPU 자발적 반납 (Nonpreemtive)

② Running -> Ready: Time quantum 끝 = CPU를 뺏김 (Preemtive)

③ Wating -> Ready: 나보다 우선순위 높은 프로세스가 먼저 할당받음 = CPU를 뺏김 (Preemtive)

④ Terminate: CPU 자발적 반납 (Nonpreemtive)

 

 

Preemtive vs. Nonpreemtive

* 여기 중요함

 

Nonpreemtive

프로세스가 자발적으로 반납할 때까지 계속 CPU를 사용할 수 있게 함

 

Preemtive

CPU를 사용 중인 프로세스를 할당을 중단하고 다른 프로세스에게 할당할 수 있는 스케줄링

보통 특별한 H/W가 필요함 Ex) Time quantum을 이용한다면 Timer라는 H/W 필요

 

 

 

Dispatcher

Context switch와 관련된 모든 작업을 Dispatcher가 함

-> Context switch를 위한 주요한 모듈

 

Dispatch latency

Context switch에 드는 시간

 

 

 

Scheduling criteria

Ready queue에서 여러 개의 프로세스가 대기중일 때 어떤 기준으로 CPU를 스케줄링할 것인가?

 

CPU Utilization: 어떻게 해야 CPU가 가장 바쁜가?

Throughput: 주어진 Time unit 내에 얼마나 많은 프로세스가 작업을 같이 끝낼 수 있는가?
Turnaround time: Job이 submission되고나서부터 작업 완료까지 걸리는 시간

Waiting Time:이 최소화되게 끔 스케줄링 한다

Response time: 첫 번째 response가 나오는 시간

 

CPU Utilization이 최대화되려면 나머지 4개가 최소화되어야 함

 

평균값을 최소화, 분산을 최소화, ... 최적화에는 여러 방법이 있다.

 

 

 

Scheduling algorithm

Ready queue가 1개일 때

ⓐ FCFS(First-Come, First-Served) Scheduling

ⓑ SJF(Shortest-Job-First) Scheduling

ⓒ Priority Scheduling

ⓓ RR(Round-Robin) Scheduling

 

Ready queue가 여러 개일 때

ⓐ Multilevel Queue Scheduling

ⓑ Multilevel Feedback Queue Scheduling

 

 

FCFS

가장 구현하기 쉬움

Burst time 무시하고 그냥 선착순

비효율적임

Case 1: FCFS 방법대로 실행했을 때

 

 

Case 2: 순서를 바꾸면 Wating time이 크게 감소한다.

 

 

 

순서에 따라 Waiting time이 달라짐을 알 수 있다.

 

FCFS에서 waiting time은 minimum이 아니며 nonpreemtive로 실행된다.

즉 자발적 CPU 반납을 기다려야 한다.

 

 

Convoy effect

CPU Burst가 아주 큰 프로세스에 의해 다른 모든 프로세스의 대기시간이 증가하게 되는 현상

위의 Case 1의 경우 CPU Burst가 큰 프로세스에 먼저 CPU를 할당하는 바람에 Waiting time이 급격히 증가했다.

 

-> CPU Burst가 짧은 프로세스를 먼저 실행하는 게 Waiting time을 최소화하는 방법이다.

 

 

 

SJF

CPU Burst가 짧은 프로세스부터 CPU를 할당하는 방법

Nonpreemtive다. 즉 자발적 반납을 기다린다.

CPU Burst가 같다면 순서대로(FCFS)

 

Waiting time 면에서 보면 이게 최적이다.

문제는 다음 CPU의 CPU Burst를 알기가 어려움(미래의 일이니까)

과거의 CPU Burst들의 Exponential average로 예측할 수는 있으나 물론 정확하지 않음

아님 사용자가 CPU Burst를 입력해서 동작할 수도 있다

 

Shortest Remaing Time First Scheduling

SJF의 preemtive version

 

우선 순서대로 실행하다가 burst가 더 짧은 프로세스가 오면 걔로 갈아탐

 

 

0: 우선 $P_1$이 도착했으므로 그걸 실행한다.

1: $P_2$ 도착, $P_1$의 남은 burst보다 짧으므로 $P_2$로 갈아탐

2: $P_3$ 도착, $P_2$가 더 짧으므로 그대로 실행

3: $P_4$ 도착, $P_2$가 더 짧으므로 그대로 실행

4: $P_2$ 실행 끝.

5: $P_1$, $P_3$, $P_4$ 중 $P_4$의 burst가 가장 짧으므로 $P_4$ 실행

10: $P_4$ 실행 끝. $P_1$, $P_3$ 중 $P_1$의 남은 burst가 더 짧으므로 $P_1$ 실행

17: $P_1$ 실행 끝. $P_3$ 실행

26: $P_3$ 실행 종료

 

 

$P_1$의 waiting time: 0에서 도착해 1까지 실행, 1에서 대기했다가 10에서 실행 -> 10 - 1 - 0 = 9

$P_2$의 waiting time: 1에서 도착해 1까지 대기 후 쭉 실행 ->  1 - 1 = 0

$P_3$의 waiting time: 2에서 도착 후 17까지 대기 -> 17 - 2 = 15

$P_4$의 waiting time: 3에서 도착해 5에서 실행 -> 5 - 3 = 2

 

따라서 Average wating time은 (9+0+15+2)/4 = 6.5가 된다.

 

 

Priority scheduling

우선순위 높은 스레드 우선, 우선순위가 같으면 FCFS

우선순위는 OS가 어떤 기준에 의해 부여할 수도 있고 사용자가 지정할 수도 있다.

숫자가 낮은 게 높은 우선순위라고 가정한다.

 

SJF에서는 다음 CPU의 burst time이 기준

 

Preemtive, Nonpreemtive 다 가능

 

Indiefinite blocking[Starvation]

우선순위가 높은 프로세스가 계속 잡고 있으면 나머지는 다 기다려야 됨

-> Aging

우선순위가 낮은 프로세스의 우선순위를 조금씩 높여준다.

 

 

 

Round Robin

Multitasking이나 Time-sharing system에서 사용하는 대표적인 스케줄링 알고리즘

각 프로세스에 Time quantum(보통 10~100ms)

-> Preemtive만 가능

 

Time quantum=4인 경우

도착은 동시에 일어남

$P_1$의 waiting time: 4까지 실행 후 대기하다가 10에서 쭉 실행 -> 10 - 4 - 0= 6

$P_2$의 waiting time: 4까지 대기 후 쭉 실행 -> 4 - 0 = 4

$P_3$의 waiting time: 7까지 대기 후 쭉 실행 -> 7 - 0 = 7

 

따라서 Average wating time은 (6+4+7)/3 = 5.66이 된다.

 

 

Time quantum

Ready queue에 $n$개의 프로세스가 있고 Time quantum이 $q$라면

결국 각 프로세스는CPU의 $\frac{1}{n}$만큼 할당받게 된다. 단, 한 번에 $q$씩

즉 CPU 성능이 $C$라고 치면 각 프로세스는 $\frac{C}{n}$의 성능을 가진 CPU를 혼자 사용한 효과를 받는다.

또한 모든 프로세스는 $(n-1)q$보다 많이 기다리지 않는다.

 

따라서 중요한 issue는 time quantum이다.

이 값이 아주 크면 FCFS처럼 되고 너무 작으면 Context switch에 시간을 너무 많이 쓰게 된다.

 

 

Turnaround time

Job의 start부터 end까지의 시간.

이 시간도 time quantum에 따라 달라진다.

 

 

$q=1$이면 $P_1$이 끝나는 시간은 28, $P_2$가 끝나는 시간은 29, $P_3$가 끝나는 시간은 30이므로

평균 turnaround time은 29가 된다.

 

A rule of thumb(= 경험적 기준)

반드시 이렇게 해야 하는 건 아닌데 CPU burst의 80%가 Time quantum보다 짧게끔 하는 게 보통

* 수학적으로 엄밀하게 증명된 건 아니고 '해 보니까 이 정도면 되더라' 하는 값임

 

 

=============================================까지는 Ready queue가 하나일 때

 

 

Multilevel queue scheduling

Ready queue는 여러 개로 partition된다. Ex) foreground, background 하나 등 

프로세스는 각 프로세스의 특징에 따라 어느 queue에 들어갈 지 고정된다. 그래서 자기 queue에만 들어갈 수 있음

각 queue는 서로 다른 scheduling 알고리즘을 쓸 수 있다.

 

Queue는 우선순위가 있어 우선순위가 높은 Queue의 실행이 끝나야 낮은 우선순위가 실행될 수 있음

-> Queue 간 스케줄링이 필요하다.

 

Fixed Priority scheduling

우선순위가 높은 Queue의 실행이 끝나야 우선순위가 낮은 Queue 실행

-> Starvation 발생 가능

 

Time slice

우선순위에 따라 CPU 시간을 배분함

Ex) 60%, 20%, 10%, 5%, 5%

 

우선순위가 낮으면 그만큼 CPU를 띄엄띄엄 할당받긴 하지만 그래도 starvation은 없다.

 

 

 

Multilevel Feedback Queue Scheduling

Queue가 여러개 있지만 Multilevel queue scheduling과 달리 프로세스가 Queue를 왔다갔다 할 수 있음.

 

- 몇 개의 Queue를 쓸 것인가?

- 각 Queue에서 어떤 스케줄링 알고리즘을 쓸 것인가? - Time quantum은 얼마로 할 것인가?

- Queue를 옮기는 기준은 무엇으로 할 것인가?

등의 issue가 있다.

 

- Example

 

$Q_0$: RR, TQ = 8ms

$Q_1$: RR, TQ = 16ms

$Q_2$: FCFS

 

우선 $Q_0$에서 8의 TQ를 받아 실행된다. 그게 안 끝나면 그 다음으로 넘어감

$Q_1$에서 16의 TQ를 받아 실행된다. 그게 안 끝나면 그 다음으로 넘어가 FCFS로 실행된다.

$Q_1$ 실행이 끝나 $Q_0$, $Q_1$ 둘 다 비면 $Q_2$가 실행된다.

 

그런데 $Q_0$에서 프로세스가 계속 들어오면 $Q_2$의 프로세스는 실행되지 못 하는 문제가 발생한다.

그래서 일정 시간이 지나면 $Q_2$에서 $Q_0$로 보내는 방법이 필요해진다.

 

 

 

 

Thread scheduling

Multithread로 구성되면 스케줄링 단위는 thread가 된다.

 

Thread에는 User thread와 Kernel thread가 있다.

 

User thread에서 보면 Kernel thread마다 CPU의 Logical entity인 LWP가 할당되어 있어서

User thread에서는 실제 low-level을 보는 게 아니라 LWP를 CPU로 보게 됨

-> CPU가 아니라 LWP를 어느 Kernel에 할당할 것인가?

CPU를 바로 할당하는 게 아니라 CPU와 User thread 사이의 가상 CPU인 LWP를 대상으로 thread library가 스케줄링을 해주고이 LWP를 Kernel thread와 연계해 실제로 CPU를 할당받게됨

 

Kernel thread는 실제로 CPU가 할당되는 단위이므로

가상이 아닌 실제 CPU를 어느 Kernel에 할당할 지 결정하게 됨

 

즉 OS는 user thread가 아닌 kernel thread를 스케줄링 하고 user thread는 Thread library에 의해 스케줄링 되며,

따라서 User thread는 CPU에서 실행되기 위해 LWP를 통해 (간접적으로라도) Kernel thread에 mapping되어야 한다.

 

 

Multi-processor scheduling

CPU가 여러 개일 경우 CPU는 어떻게 스케줄링되는가?

 

Homogenous processor: Core 개념

 

Asymmetric multiprocessing: 프로세스 하나가 coordinator 역할을 해 나머지 프로세스에게 어떤 job을 줄 지 결정

Symmetric multiprocessing: 모든 프로세스가 동일하게 동작 (가장 많이 쓰이는 방법)

 

Processor affinity: 프로세서와 프로세스 간 유사도 점수를 이용해 어느 프로세서로 프로세스를 실행할 것인지 결정

$P_1$ 프로세스가 왼쪽에서 실행되다가 Context switch에 의해 Ready queue로 들어갔다고 하자.

즉 왼쪽 프로세서의 메모리에 $P_1$과 관련된 값들이 있다고 하자.

그러면 $P_1$이 다시 실행되려면 당연히 왼쪽에서 실행되는 게 더 빠르다.

따라서 왼쪽 프로세서의 유사도 점수를 더 높게 해서 $P_1$이 왼쪽 프로세서에서 실행되게 한다.

 

 

Load balancing

모든 프로세서가 바쁘게 한다

 

Push migration: 한 CPU의 작업이 많으면 다른 CPU로 좀 준다

Pull migration: 다른 CPU의 작업이 많고 내가 없으면 내가 좀 땡겨온다

 

 

 

Multicore processor

병목 현상 제거

속도가 빠르고 전력 소비도 적다.

 

코어가 하나라면 어느 한 시점에는 한 스레드만 실행할 수 있지만

코어가 여러 개면 동시에 여러 스레드를 실행할 수 있다.

-> Multithread가  더 유리해짐

 

 

 

 

Real-Time CPU Scheduling

실시간 시스템에서 CPU 스케줄링은 어떻게 일어나는가?

 

어떤 이벤트 발생 시 이벤트 처리까지 필요한 deadline이 설정되어 있어 그 deadline 내에 이벤트가 처리되어야 함

 

Hard real-time systems

반드시 Deadline 내에 작업이 끝나야 함

 

Soft real-time systems

Deadline에 얼추 맞게 끝내면 됨

 

 

Deadline 내에 작업을 끝낼 수 있는지 여부에는 다음의 두 latency가 영향을 미친다.

Interrupt latency

작업 중 Interrupt 발생 시 현재 작업을 중단한 후 Interrupt를 처리해야 한다.

따라서 Interrupt 처리가 빨리 끝날수록 Deadline 안에 작업을 끝낼 가능성이 높아진다.

 

Dispatch latency

Context switch가 얼마나 걸리는가?

 

이벤트 발생 시 현재 작업 중단 후 인터럽트 처리를 할 수 있는 프로세스 시작 -> Context switch

그런데 만약 인터럽트 처리를 위한 작업을 다른 프로세스가 사용 중이라면 반납까지 기다려야 한다: Conflict

반납 후 Interrupt 처리를 할 수 있는 프로세스를 위한 Dispatch 작업이 일어나고 Real-time process 실행

 

 

 

Real-time scheduling은 Priority-based scheduling -> Preemtive

Deadline까지 시간이 적은 작업부터 수행한다.

 

주기적으로 동작하는 프로세스가 있고, 실행 시간 $t$, deadline $d$, 주기 $p$에 대해

$0 \;\leq\; t \;\leq\; d \;\leq\; p$

라 하면, 이 작업의 속도는 $\frac{1}{p}$라 할 수 있다.

즉 다음과 같은 시스템에 Scheduling algorithm을 적용하는 것이다.

 

 

Rate monotonic Scheduling

우선순위는 주기의 역수다.

-> 자주 수행되는 프로세스일수록 우선순위가 높다.

 

Ex)

$P_1$의 주기는 50, processing time은 20이고 $P_2$의 주기는 100, processing time은 35다.

두 프로세스의 deadline은 다음 주기인 경우 작업은 위와 같이 진행된다.

 

 

 

그런데 다음의 경우 Deadline을 못 맞추게 된다.

 

 

Earliest Deadline First Scheduling(EDF)

Real Monostic scheduling에서 deadline을 지키지 못 하는 경우가 발생하는 것을 보완한 방법

우선순위는 deadline에 의해 결정된다.

 

Ex)

$P_1$의 주기는 50, processing time은 25이고 $P_2$의 주기는 80, processing time은 35다.

두 프로세스의 deadline은 다음 주기인 경우 작업은 위와 같이 진행된다.