[OS] 4. CPU 스케줄링

[OS] 4. CPU 스케줄링

2022. 4. 1. 14:47ㆍMajor`/운영체제

다중 프로그래밍의 목적은 "CPU를 항상 바쁘게 하자"이다.
반드시 여러 프로세스들 중 하나의 프로세스에게는 CPU가 할당되어야 하고, 해당 프로세스가 I/O 요청을 기다리면 "context switch"를 통해서 다른 프로세스에게 CPU를 할당해줘야 한다.

>> 이 때 필요한 기술이 CPU 스케줄링이다.

프로세스의 실행은 CPU burst - I/O burst 사이를 교대로 왔다 갔다 하며 수행된다

마지막 CPU burst에는 또 다른 I/O burst가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다

"CPU Bound Process"는 CPU burst time이 굉장히 긴 프로세스이고, I/O burst time은 굉장히 짧기 때문에 user와 interactive하지 않은 batch system이다
"I/O Bound Process"는 I/O burst time이 굉장히 긴 프로세스이므로 user와 interactive가 굉장히 좋다

CPU Bound Process만 메모리에 올리게 된다면 CPU만 굉장히 열심히 쓰고 user와의 interactive가 필요한 프로세스가 올라오지 않아서 user 입장에서는 response time이 굉장히 길어지고 I/O 장치의 이용률이 굉장히 낮아진다.

I/O Bound Process는 user와 interactive한 process이므로, 만약에 CPU bound process가 CPU를 할당받고 너무 오랫동안 CPU를 놔주지 않으면 I/O bound process에 대한 응답시간이 너무 길어져서 user의 입장에서 답답할 것이다

>> CPU Bound Process & I/O Bound Process들에게 적절히 CPU를 할당해주는 CPU 스케줄링이 필요하다

물론 공평하게 CPU를 할당해주는 것도 중요하지만, user와의 interaction을 중요시하는 I/O Bound Process들에게 CPU를 우선적으로 할당해주는 "효율성"또한 중요하다

CPU 스케줄러

ready 상태의 프로세스들 중에서 CPU를 할당해줄 프로세스를 고르는 "OS의 kernel code"

Dispatcher

CPU의 제어권을 "CPU 스케줄러에 의해 선택된 프로세스"에게 실제로 넘겨주는 역할을 수행하는 "OS의 kernel code"
- 이 과정을 "context switch"라고 하고, "context switch"를 직접 수행해주는 code가 Dispatcher이다

$$ Dispatcher가 수행하는 작업 $$

"context switch"
kernel mode -> user mode로 전환
프로그램을 다시 시작하기 위해서 user program을 적절한 위치로 JUMP하는 일

CPU 스케줄링이 필요한 경우

1. running → waiting(blocked)

해당 프로세스가 I/O관련 작업을 필요로 하고, 직접 OS에게 System Call을 통해서 요청하는 것이기 때문에 "CPU를 자진 반납"

2. running → ready

Timer Interrupt에 의해서 해당 프로세스는 CPU를 더 쓰고싶어 하지만 정해진 time quantum에 의해서 "강제로 CPU 반납"

3. waiting(blocked) → ready

만약 I/O 작업을 모두 마쳤다면 device controller가 CPU에 interrupt를 건다. 이를 통해서 CPU의 제어권은 OS로 넘어가게 되고, OS의 특정 kernel code를 통해서 CPU가 local buffer에 존재하는 데이터들을 프로세스에게 copy해준다 : "강제로 CPU 빼앗음"

4. terminated

해당 프로세스는 자신의 일을 모두 마치고 종료되었기 때문에 "CPU를 자진 반납"

>> (1) / (4)는 CPU를 자진 반납하므로 "비선점(Nonpreemptive)"

>> (2) / (3)는 CPU를 강제로 빼앗기 때문에 "선점(Preemptive)"

선점(Preemptive)이란 어떤 프로세스가 CPU를 할당받더라도 수행이 완료되기전에 언제든지 빼앗을 수 있다
선점형 스케줄링은 다음 고려를 해야 한다

공유 데이터 접근에 대한 고려
kernel mode중 선점에 대한 고려
중요한 OS 활동 중 인터럽트 발생에 대한 고려

비선점(Nonpreemptive)이란 어떤 프로세스가 CPU를 할당받으면 수행이 종료되거나 자진으로 반납하지 않는 이상 절대로 CPU를 빼앗지 못한다

스케줄링 성능 척도 (Scheduling Criteria)

$ 시스템 입장 $

1. CPU 이용률 (CPU Utilization)

전체 시간동안 CPU가 놀지 않고 일을 수행한 시간
→ 높을 수록 좋다

2. 처리량 (Throughput)

ready queue에 있는 프로세스들 중에서 단위 시간동안 몇개의 프로세스를 처리했나
→ 높을 수록 좋다

$ 프로세스 입장 $

1. 소요/반환 시간 (Turnaround Time)

ready queue에 도착하고, 해당 프로세스가 종료될 때까지 걸린 시간
→ 빠를 수록 좋다

2. 대기 시간 (Waiting Time)

프로세스가 ready queue에서 대기한 총 시간
→ 빠를 수록 좋다

3. 응답 시간 (Response Time)

ready queue에 도착하고 "처음 CPU 할당 받을때까지" 걸린 시간
→ 빠를 수록 좋다
→ interactive system에서 굉장히 중요하다 (Time Sharing)

>> process입장에서는 CPU를 최대한 빨리 얻고(응답 시간), 최대한 빨리 일을 끝내는게 가장 좋다(반환/대기 시간)

Example) 중국집

시스템 : 사장? 프로그램 : 손님?

사장입장
CPU 이용률 : 요리사가 열심히 요리를 하면 더 좋다
처리율 : 요리사가 단위 시간동안 최대한 많은 손님들에게 요리를 해주면 매출이 올라간다

손님입장
반환시간 : 최대한 음식 빨리 먹고 나가면 시간상 효율이 좋다
대기시간 : 코스 요리를 시켰으면 중간중간 요리 대기시간이 적으면 좋다
응답시간 : 코스 요리를 시키고 처음 요리가 빨리 나올수록 빨리 음식을 먹어서 더 좋다

FCFS : First Come First Served

"비선점 스케줄링"
- 먼저 온 프로세스에게 먼저 CPU를 할당해준다

프로세스	Burst Time
p1	24
p2	3
p3	3

만약 p1 - p2 - p3순으로 도착했다면 (거의 동시에 0초에 도착했고 순서가 p1 - p2 - p3)

반환 시간 : 24
대기 시간 : 0
응답 시간 : 0

반환 시간 : 27
대기 시간 : 24
응답 시간 : 24

반환 시간 : 30
대기 시간 : 27
응답 시간 : 27

ATT (Average Turnaround Time) : (24 + 27 + 30) / 3 = 27
AWT (Average Waiting Time) : (0 + 24 + 27) / 3 = 17
ART (Average Response Time) : (0 + 24 + 27) / 3 = 17

하지만 CPU burst time이 짧은 프로세스가 먼저 도착한다면? p2 - p3 - p1 (거의 동시에 0초에 도착했고 순서가 p2 - p3 - p1)

반환 시간 : 30
대기 시간 : 6
응답 시간 : 6

반환 시간 : 3
대기 시간 : 0
응답 시간 : 0

반환 시간 : 6
대기 시간 : 6
응답 시간 : 6

ATT (Average Turnaround Time) : (3 + 6 + 30) / 3 = 13
AWT (Average Waiting Time) : (0 + 3 + 6) / 3 = 3
ART (Average Response Time) : (0 + 3 + 6) / 3 = 3

AWT에서 굉장히 큰 차이를 보여준다

"Convoy Effect"

먼저 도착한 프로세스가 CPU Burst Process이고, CPU를 굉장히 오랫동안 잡고 있기 때문에 뒤에 다른 프로세스들의 앞의 프로세스 때문에 대기시간이 엄청 길어지는 현상

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 반납하기를 기다리는 현상

SJF : Shortest-Job First

CPU Burst time이 제일 짧은 프로세스에게 먼저 CPU를 할당해주자

비선점 SJF

현재를 기준으로 CPU Burst Time이 제일 짧은 프로세스에게 CPU 할당

중간에 CPU Burst Time이 더 짧은 프로세스가 도착해도 현재 실행 중인 프로세스로부터 CPU를 빼앗지 않는다
해당 프로세스가 종료가 되어야 그때 CPU 스케줄링이 이루어진다

선점 SJF : SRTF (Shortest Remaining Time First)

현재를 기준으로 CPU Burst Time이 제일 짧은 프로세스에게 CPU 할당

중간에 CPU Burst Time이 더 짧은 프로세스가 도착하면 즉시 현재 실행중인 프로세스로부터 CPU를 빼앗고 더 짧은 프로세스에게 새로 CPU를 할당한다
프로세스가 도착할때마다 그때 CPU Burst Time을 각각 비교해서 CPU 스케줄링이 이루어진다

>> 실질적으로 "선점 SJF : SRTF"가 Minimum AWT를 보장해준다

어떤 스케줄링과 비교해도 AWT는 SRTF가 가장 짧다

Example) 비선점 SJF

프로세스	Arrival Time	Burst Time
p1	0	7
p2	2	4
p3	4	1
p4	5	4

반환 시간 : 7
대기 시간 : 0
응답 시간 : 0

반환 시간 : 4
대기 시간 : 6
응답 시간 : 6

반환 시간 : 1
대기 시간 : 3
응답 시간 : 3

반환 시간 : 4
대기 시간 : 7
응답 시간 : 7

ATT (Average Turnaround Time) : (7 + 4 + 1 + 4) / 4 = 4
AWT (Average Waiting Time) : (0 + 6 + 3 + 7) / 4 = 4
ART (Average Response Time) : (0 + 6 + 3 + 7) / 4 = 4

Example) 선점 SJF : SRTF

프로세스	Arrival Time	Burst Time
p1	0	7
p2	2	4
p3	4	1
p4	5	4

1. p1이 0초에 도착했으니까 일단 시작
2. p2가 2초에 도착했으니까 CPU 스케줄링 시작

p1 burst time = 6
p2 burst time = 4
p2가 더 짧으니 2초에 p2 시작

3. p3가 4초에 도착했으니까 CPU 스케줄링 시작

p1 burst time = 6
p2 burst time = 2
p3 burst time = 1
p3가 가장 짧으니까 4초에 p3 시작

4. p4가 5초에 도착했으니까 CPU 스케줄링 시작 & p3는 burst time이 1이니까 5초에 p3 종료

p1 burst time = 6
p2 burst time = 2
p4 burst time = 4
p2가 가장 짧으니까 5초에 p2 다시 시작

5. 7초에 p2가 종료되고 CPU 스케줄링 시작

p1 burst time = 6
p4 burst time = 4
p4가 더 짧으니 7초에 p4 시작

6. 11초에 p4 종료되고 p1은 16초까지 실행

p1

반환 시간 : 16
대기 시간 : 9
응답 시간 : 0

반환 시간 : 5
대기 시간 : 1
응답 시간 : 0

반환 시간 : 1
대기 시간 : 0
응답 시간 : 0

반환 시간 : 6
대기 시간 : 2
응답 시간 : 2

ATT (Average Turnaround Time) : (16 + 5 + 1 + 6) / 4 = 7
AWT (Average Waiting Time) : (9 + 1 + 0 + 2) / 4 = 3
ART (Average Response Time) : (0 + 0 + 0 + 2) / 4 = 0.5

선점 SJF : SRTF의 문제점

1) Starvation (기아 현상)

SJF는 CPU Burst Time을 우선순위로 보기 때문에 CPU Burst Time이 과도하게 긴 프로세스는 영원히 CPU 할당을 받지 못할 수 있다

1초짜리 5개와 100초짜리 1개가 있는데 100초짜리 프로세스는 "1초짜리 5개 다 쓰면 내 차례가 오겠구나"라고 생각을 하고 계속 기다리는데 도중에 100초보다 짧은 프로세스가 계속 들어오면 결국 100초짜리 프로세스는 영원히 CPU 할당을 받지 못한다

2) CPU Burst Time 미리 알 수 없다 : 비현실적

사용 도중에 해당 프로세스에 대한 I/O, branch, ... 등등이 발생한다
따라서 각 프로세스에 대한 CPU Burst Time을 정확히 미리 알 수 없고 "추정"만 가능하다

※ Exponential Averaging

결국 현재까지는 각 프로세스에 대한 CPU Burst Time을 알고있으니까 해당 정보들을 활용해서 미래의 프로세스 CPU Burst Time을 "예측"할 수 있다

t(n) (그냥 영어 t) = 실제 CPU 사용 시간 >> n번째 프로세스 실제 CPU 사용 시간
T(n+1) (타우) = CPU 사용 추정 시간 >> (n+1)번째 프로세스 CPU 사용 시간 추정치
(n+1)번째 프로세스 사용하려면 과거의 (0 ~ n)까지의 프로세스 CPU 사용 시간은 이미 존재한다

Priority Scheduling : 우선순위 스케줄링

우선순위가 제일 높은 프로세스에게 CPU를 할당

각 프로세스에게 "Integer : Priority Num"을 부여한다
시스템에 따라 우선순위를 측정하는 방법은 다르지만 일반적으로 Priority Num이 작을수록 우선순위가 높다

다른 관점에서 보면 SJF도 일종의 Priority Scheduling이다
>> SJF는 CPU Burst Time을 우선순위로 본다

비선점 Priority Scheduling

현재를 기준으로 우선순위 제일 높은 프로세스에게 CPU 할당

중간에 우선순위가 더 높은 프로세스가 ready queue에 도착해도 현재 프로세스로부터 CPU를 빼앗지 않는다

선점 Priority Scheduling

현재를 기준으로 우선순위 제일 높은 프로세스에게 CPU 할당

중간에 우선순위가 더 높은 프로세스가 ready queue에 도착하면 즉시 현재 프로세스로부터 CPU를 빼앗아서 우선순위가 더 높은 프로세스에게 새로 할당해준다

Priority Scheduling 문제점

1) Starvation (기아 현상) / Indefinite Blocking

선점 SJF와 동일한 문제이다
물론 효율성이 중요한건 맞지만, 어떤 프로세스에 대한 지나친 차별또한 방지해야 한다

>> Aging 기법을 통한 해결

일정 시간이 지나면 우선순위를 점차 증가시켜줘서 Starvation을 막아준다

→ 우선순위가 동일할 경우 "Round-Robin"을 도입해준다

Round Robin (RR)

"선점형 스케줄링"
현대적인 CPU 스케줄링의 기법이다

우리가 일반적으로 프로세스에게 CPU를 할당해줄 때 OS는 특정 시간(Time quantum)을 설정해줘서 CPU를 할당해준다
여기서 해당 프로세스는 고정된 Time Quantum이 종료되면 CPU를 강제로 빼앗기게 된다 : "선점형 스케줄링"

RR에서는 각 프로세스는 동일한 크기의 Time Quantum을 가지게 된다
그리고 Time Quantum이 종료되면 ready queue의 맨 뒤에 줄을 서게 된다

보통 Time Quantum은 10ms ~ 100ms 사이이다

RR의 장점

"응답 시간(Response Time)이 굉장히 빨라진다"
→ Time Quantum에 의해서 CPU를 주고 빼앗고를 반복하기 때문에 어느 프로세스든지 일단 CPU를 할당받을 수 있기 때문에 응답시간이 빨라진다

※ Example) 현재 ready queue에 n개의 프로세스가 존재 & 각 프로세스의 time quantum = q

적어도 각각의 프로세스들은 "(n-1)q"만 기다리면 CPU를 할당받을 수 있다
이말은 "어떤 프로세스도 (n-1)q 이상 기다리지 않는다"라는 의미와 동일하다
물론 CPU Burst Time이 긴 프로세스는 상대적으로 오래 기다리고, CPU Burst Time이 짧은 프로세스는 상대적으로 짧게 기다린다

"대기 시간"이 CPU Burst Time에 비례한다

극단적 Time Quantum

1) Time Quantum이 매우 길다

결국 FCFS와 동일한 스케줄링 알고리즘이 된다

2) Time Quantum이 매우 짧다

RR에는 굉장히 이상적인 time quantum이다
하지만, "Context Switch Overhead"가 굉장히 커진다

자주 CPU 할당 대상을 변경해줘야 하기 때문이고, 결론적으로 전체적 시스템 성능이 안좋아질 수 있다
극단적으로 말하면 프로세스에게 할당된 CPU 시간은 그 시간 전체를 프로세스에게 어떤 일을 수행하기 위해 쓰는게 아니라 "context switch"할 때 주로 쓰게 된다. 따라서 time quantum동안 context switch만 발생하고 프로세스가 진전되지 않을 수 있다

Example) RR with Time Quantum = 20

프로세스	Burst Time
p1	53
p2	17
p3	68
p4	24

p1 : 0 ~ 20까지 실행
-> p1 remaining burst time = 33

p2 : 20 ~ 37까지 실행
-> p2의 burst time 17이므로 20보다 작음
-> p2 종료

p3 : 37 ~ 57까지 실행
-> p3 remaining burst time = 48

p4 : 57 ~ 77까지 실행
-> p4 ~ = 4

p1 : 77 ~ 97까지 실행
-> p1 ~ = 13

p3 : 97 ~ 117까지 실행
-> p3 ~ = 28

p4 : 117 ~ 121까지 실행
-> p4 종료

p1 : 121 ~ 134까지 실행
-> p1 종료

p3 : 134 ~ 154까지 실행
-> p3 ~= 8

p3 : 154 ~ 162까지 실행
-> p3 종료

반환 시간 : 134
대기 시간 : 81
응답 시간 : 0

반환 시간 : 37
대기 시간 : 20
응답 시간 : 20

반환 시간 : 162
대기 시간 : 94
응답 시간 : 37

반환 시간 : 121
대기 시간 : 97
응답 시간 : 57

ATT (Average Turnaround Time) : (134 + 37 + 162 + 121) / 4 = 113.5
AWT (Average Waiting Time) : (81 + 20 + 94 + 97) / 4 = 73
ART (Average Response Time) : (0 + 20 + 37 + 57) / 4 = 28.5

(n-1)q = (4-1)20 = 60이다
간트 차트를 보게되면 어느 프로세스도 60초를 넘어서 기다린 프로세스가 없다

>> RR은 SJF보다 ATT/AWT는 더 길어질 수 있지만 ART는 더 짧다

RR은 CPU Burst Time을 정확히 모를 때 효과적인 방법이지만, CPU Burst time이 모두 동일할 경우 별로 효율적이지 못한 CPU 스케줄링 알고리즘이다
예를 들어서 CPU Burst Time이 모두 100초인 4개의 프로세스를 FCFS로 스케줄링해주면 100/200/300/400에 차례대로 종료되고 빠져나갈 수 있지만, RR은 400초에 동시에 종료가 될 수 있다

일반적으로 CPU Burst의 80%가 Time Quantum보다 짧을 것을 권장한다

Multilevel Queue

앞에 설명한 FCFS/SJF/Priority/RR은 모두 ready queue가 하나가 존재한다는 가정에서 이루어지는 스케줄링이다
Multilevel Queue의 경우 ready queue를 여러개로 분할하는 CPU 스케줄링 알고리즘이다

대표적으로 foreground queue & background queue로 나눠준다
각 프로세스들은 일단 foreground queue나 background queue에 들어가게 되면 다른 queue로 변경이 불가능하다

foreground queue

user와의 interaction을 중요시하는 프로세스들의 존재한다
여기서는 RR 방식을 활용해서 스케줄링 해준다

RR방식이 response time이 짧아서 user와의 interaction을 중요시하는 프로세스에게 효과적이다

background queue

user와의 interaction과 관계없이 batch system형태의 프로세스들의 존재한다
여기서는 FCFS 방식을 활용해서 스케줄링 해준다

>> 각 queue 내부에서의 프로세스에 대한 CPU 스케줄링은 RR or FCFS방식으로 수행해주는데 전체적으로 보면 "어느 큐에게 CPU의 선택권을 줄까"라는 문제를 해결해줘야 한다

1. Fixed Priority Scheduling

무조건 foreground queue를 기준으로 생각한다
→ foreground queue에 프로세스가 없는 경우에만 background queue를 고려하는 방식이다

이렇게 하게되면 foreground queue에 프로세스가 계속 들어가면 background queue는 절대 고려를 하지 못할 것이다 : Starvation 발생

2. Time Slice

foreground & background에 대한 Time Slice를 정해준다

ex) foreground = 80% & background = 20%

이렇게 하면 background queue에 존재하더라도 어차피 한번쯤은 CPU를 할당받기 때문에 starvation이 발생하지 않는다

>> 하지만, Multilevel Queue의 가장 큰 단점은 "한번 foreground나 background queue로 들어가게 되면 다른 큐로의 이동이 불가능하다"라는 점이다

물론 스케줄링 오버헤드에 관한 장점은 존재하지만, 융통성이 부족한 스케줄링이다
이러한 문제를 해결 : Multilevel Feedback Queue

Multilevel Feedback Queue

Multilevel Feedback Queue도 여러 ready queue가 존재하지만 "각 프로세스가 queue간에 이동이 가능하다"라는 장점이 있다

1. 일단 모든 프로세스가 처음 도착을 하게되면 가장 높은 우선순위인 RR : Time Quantum 8의 큐에 넣는다

2. 해당 프로세스가 queue에서 작업을 완료하면 그냥 빠져나가는거고, 작업을 완료하지 못하면 하위 큐로 내쫓아진다

3. 결국 계속해서 수행하게 되면 CPU Burst Time이 긴 프로세스는 최종적으로 FCFS에 들어가서 수행하게 된다

>> 결국 어떠한 프로세스라도 일단 최상위 큐로 들어가서 CPU를 한번은 할당을 받기 때문에 응답속도가 좋은 방법이다

고려사항

1. Ready Queue의 개수
2. 각 Queue에서의 스케줄링 알고리즘
3. 프로세스가 다른 Queue로 이동할 때의 조건

프로세스를 상위 Queue로 보내는 조건
프로세스를 하위 Queue로 내쫓는 조건

4. 프로세스가 처음 Queue에 들어갈 때 어느 Queue로 들어가야 하는지 결정

스레드 스케줄링

프로세스를 여러개의 스레드로 나누면서 스레드는 user thread & kernel thread로 구별된다
현재 OS의 스케줄 대상은 결국 process가 아니라 kernel thread를 대상으로 스케줄링한다
user thread는 user library를 통해서 관리가 되고 kernel은 user thread의 존재를 알지 못한다
따라서 user thread는 결국 1:1/N:1/N:M 모델의 kernel thread에 Mapping되어야 한다

1) Local Scheduling

$ user level thread $
OS는 각각의 user thread의 존재를 모르고 일반적인 프로세스로 인식한다
따라서 OS는 그냥 해당 프로세스에게 CPU를 할당해준다

>> 여기서 해당 프로세스내에 존재하는 여러 user thread간에 "경쟁?"을 하게 된다

CPU를 할당받은 프로세스는 본인 내부에서 어떤 user thread에게 스케줄해줄지 "thread library"를 통해서 결정한다 >> PCS : Process-Contention Scope

2) Global Scheduling

$ kernel level thread $
OS가 이미 user thread의 존재를 알고 있고, 일반적 CPU 스케줄링과 비슷하게 어떤 user thread를 스케줄할지 OS가 결정해준다 >> SCS : System-Contention Scope

멀티프로세서 스케줄링

지금까지 위의 여러 CPU 스케줄링은 CPU가 하나인것을 기준으로 설명한 방식이다
만약 CPU가 여러개 존재한다면? 여러 thread를 병렬적으로 실행할 수 있기 때문에 "Load Sharing"이 가능해진다

Load Sharing : CPU끼리 공동 Queue? / 각 CPU를 위한 별도의 Queue?

Heterogeneous Processor?

ready queue에 한줄로 세워서 각 CPU가 알아서 꺼내게 할 수 있다
하지만 특정 job은 특정 CPU만 수행가능한 경우 문제가 복잡해진다

SMP : Symmetric Multiprocessing

모든 CPU가 대등하고, 각 CPU가 알아서 스케줄링 해주는 방식이다
- 각 CPU마다 ready queue가 존재한다
- 그런데 각 CPU마다 존재하는 ready queue안에는 모두 동일한 개수의 프로세스가 있지는 않을 것이다

>> 이러면 ready queue에 프로세스가 적은 CPU의 경우 빨리 끝내서 쉬게 되고, ready queue에 프로세스가 많은 CPU는 계속 일하게 된다

따라서 놀고 있는 CPU에게 다른 CPU의 ready queue로부터 job을 할당해줘야 CPU가 노는 시간이 줄게 된다 : Load Balancing

▶ Pull Migration

일이 없는 CPU가 일이 많은 CPU로부터 job 빼앗기

▶ Push Migration

일이 많은 CPU가 일이 없는 CPU에게 job 주기

ASMP : Asymmetric Multiprocessing

여러 CPU 중, 어느 한 CPU가 "리더"역할을 수행해준다
>> 이러면 해당 CPU를 제외한 나머지 CPU들은 "리더 CPU"의 데이터 접근/공유에 대한 control에 따른다
따라서 ASMP방식은 ready queue가 1개 존재한다

Real-Time Scheduling

Real-Time System은 "Deadline"이 존재하고 해당 Dealine을 지키지 않는다면 시스템에 치명적인 영향을 줄 수 있다. 그래서 반드시 "Deadline"내에 job을 끝내야 한다

Hard Real-Time Scheduling

정해진 Deadline안에 반드시 끝나도록 스케줄링 해야 한다

Soft Real-Time Scheduling

얼추 비슷하게 Deadline을 맞추고, 아주 조금 Deadline을 맞추지 못해도 시스템에 매우 큰 약영향을 미치지는 않는다
대신에 일반 프로세스에 비해 훨씬 높은 우선순위를 갖도록 해줘야 한다

2가지 지연시간

다음 2가지 지연시간이 실질적인 Real-Time OS 성능을 좌우한다

1) Interrupt Latency

실질적으로 interrupt가 발생하면 "context switch"과정이 일어난다
여기서 "context switch time"을 최소화하는 것이 Real-Time OS에 매우 중요한 일이다

2) Dispatch Latency

Dispatch Latency는 Dispatcher가 어느 프로세스를 block시키고, 다른 프로세스를 시작하는 데까지 걸리는 시간이다
CPU를 즉시 사용해야 하는 real-time task가 존재한다면 이러한 Dispatch Latency를 최소화해야 한다

1) Priority-Based Scheduling

Real-Time OS에서 가장 중요한 것은 Real-Time Process가 CPU를 필요로 하는 바로 그 시간에 즉시 CPU를 할당해주는 것이 굉장히 중요하다
이를 구현하는 가장 대표적인 방법은 선점형 우선순위 알고리즘이다

>> 하지만 이러한 방식은 Soft Real-Time 기능을 제공해줄 수는 있지만 Hard Real-Time에서는 Dealine을 정확하게 지켜야 하기 때문에 추가적인 스케줄링 기법이 필요하다

$ 프로세스들은 주기적이다

각 프로세스들은 일정한 간격으로 CPU가 필요하고, 각각의 주기 프로세스들은 CPU를 할당 받았을 때 고정된 time quantum, deadline, 주기 p가 정해져 있다
- 0 ≤ t ≤ d ≤ p
따라서 각 task의 실행 빈도는 1/p이다

2) Rate Monotonic Scheduling

각 task마다 우선순위를 할당해주는 스케줄링 기법
각각의 task가 System에 들어가게 되면 결국 period가 짧은 task가 우선순위를 높게 받을 것이다

>> CPU를 더 자주 필요로 하는 task에 더 높은 우선순위를 주게 하려는 방식

p1의 주기는 50이고 수행 시간은 20이다
p2의 주기는 100이고 수행 시간은 35이다

여기서 p2가 p1보다 우선순위가 높다고 가정하자

그러면 p2는 오자마자 시작하고 35초에 자신의 수행을 마무리 할 것이다

그리고 이후에 p1이 시작되는데 p1은 수행시간이 20이므로 "55"에 끝난다

하지만 p1의 주기는 50이고 수행 종료시간이 55이므로 p1은 마감시간을 충족시키지 못한다

p1의 CPU 이용률은 20/50 = 0.4
p2의 CPU 이용률은 35/100 = 0.35

따라서 두 프로세스의 총 CPU 이용률은 75%가 된다

(1)

하지만 Rate-Monotonic Scheduling을 사용하면 "주기가 짧은 프로세스가 높은 우선순위"를 갖게 된다
따라서 주기가 짧은 p1이 p2보다 높은 우선순위를 보유하게 되었다

p1 주기 : 50 / 100 / 150 / ...
p2 주기 : 100 / 200 / 300 / ...

1. p1이 먼저 수행을 시작해서 20이 종료한다
2. 그 이후에 p2가 수행을 시작해서 50에 종료한다

아직 p2는 5가 남았지만 p1의 주기가 돌아왔기 때문에 p1에 선점당한다

3. 선점한 p1은 수행을 시작해서 70에 종료한다
4. p2는 남은 5를 수행해서 75에 종료된다

따라서 두 프로세스는 본인의 수행을 모두 본인들의 주기 안에 마무리하였다

p1의 CPU 이용률은 20/50 = 0.4
p2의 CPU 이용률은 35/100 = 0.35

따라서 두 프로세스의 총 CPU 이용률은 75%가 된다

(2)

이 경우는 p1의 주기는 50이고 수행시간은 25이다 & p2의 주기는 80이고 수행시간은 35이다

따라서 주기가 짧은 p1이 더 높은 우선순위를 갖고 스케줄링 될 것이다

1. 먼저 p1이 수행해서 25에 종료한다
2. p2는 수행해서 50에 종료한다

마찬가지로 p1의 주기가 돌아왔기 때문에 p1에 선점
p2는 35중에 25를 수행했기 때문에 아직 10이 남은 상태

3. p1은 수행해서 75에 종료한다
4. p2는 남은 10을 수행해서 85에 종료한다

이 때 p2의 주기는 80인데 85에 종료했기 때문에 p2는 마감시간을 충족시키지 못하였다

p1의 CPU 이용률은 25/50 = 0.5
p2의 CPU 이용률은 35/80 = 0.4375

따라서 두 프로세스의 총 CPU 이용률은 93.75%가 된다

Rate-Monotonic 스케줄링의 경우 "N개의 프로세스를 스케줄 하는데 있어서 최악의 경우 CPU 이용률"은 N×(2^1/N - 1)이 된다

만약 시스템에 1개의 프로세스만 존재한다면 CPU 이용률은 100%
이 후 프로세스가 증가함에 따라서 69%까지 떨어진다

만약 두 프로세스가 존재할 경우 CPU 이용률은 약 83%가 한계이다

그러나 (2)의 경우 CPU 이용률이 한계를 넘어선 93.75%이므로 두 프로세스가 마감시간을 충족시키는 것을 보장할 수 없다

3) Earliest Deadline First Scheduling

마감시간을 기준으로 우선순위를 동적으로 부여해주는 스케줄링이다

마감시간이 빠를수록 우선순위가 높아진다

프로세스가 실행 가능하게 되면 본인의 deadline을 system에 알려야 한다
그러면 시스템 내에서의 우선순위는 새로 실행 가능하게 된 프로세스의 deadline에 맞춰서 새로 스케줄링된다

이 점이 "우선순위가 고정되어 있는" Rate-Monotonic과 다른점이다

위의 p1, p2의 주기 & 수행 시간은 Rate-Monotonic 에서는 마감시간을 충족시키지 못했던 조건들이다

그러면 Earliest-Deadline에서도 충족시키지 못할까?

처음에는 p1의 마감시간이 p2보다 빠르기 때문에 p1이 우선순위가 더 높다

1. p1이 처음에 수행해서 25에 종료된다
2. 이후에 p2가 시작된다

그러나 여기서 p2가 50까지 일단 수행을 한다고 보자
그러면 p2의 마감시간은 80이고, p1의 마감시간은 100이 된다

>> 따라서 50이 된 순간 p2의 우선순위가 p1보다 더 높기 때문에 p2는 50이후에도 계속 수행을한다

R-M에서는 50에 바로 p1에 선점을 당하였다

따라서 p2는 25 ~ 60까지 수행한다

3. p1이 60 ~ 85까지 수행을 한다

4. p2가 다시 수행을 시작한다

100이 된 순간을 보자
100이 된 순간 p1의 마감시간은 150이고 p2의 마감시간은 160이다
따라서 이때는 p1의 우선순위가 더 높아진다

>> p2는 100까지 수행 후 p1에 선점당한다

5. p1은 100 ~ 125까지 수행한다
6. p2는 125 ~ 160까지 수행한다

이 처럼 두 프로세스모두 자신의 마감시간을 만족시켰다

그러나 실제로 Earliest-Deadline은 "프로세스 간/인터럽트 핸들링 때의 context switch 비용때문에 100%의 CPU 이용률은 불가능하다"

4) Proportional Share Scheduling

어느 CPU가 특정 T의 시간만 있으면 Deadline안에 작업을 끝낼 수 있다면 시스템에서 해당 CPU에게 T라는 시간을 할당해준다
하지만 남은 몫에 대해서 새로운 프로세스가 그 이상의 몫을 요구하게 되면 승인 컨트롤러는 해당 프로세스의 시스템 진입을 거부한다

T=100이라고 가정하고 프로세스 A는 50 & B는 15 & C는 20만큼 받는다고 하자
그러면 총 85가 할당되었다

근데 프로세스 D가 오자마자 40을 달라고 한다
이러면 85 + 40 > 100이므로 할당량이 부족하기 때문에 "승인 컨트롤러"는 D의 시스템 진입을 거부한다

저작자표시 변경금지

Coding