[운영체제] CPU 스케줄링

멀티프로그래밍은

여러 개의 프로세스가 동시에 메모리에 로드되는데

각 프로세스가 cpu를 선점해서 concurrent하게 실행되는 것을

멀티 프로그래밍이라고 함 (멀티 테스킹)

 

concurrent의 목적

전제조건 : cpu가 매우 빨라서 놀고있을 때 시분할하여 cpu자원을 사용하는 것

cpu utilization을 늘리기 위해 스케줄링이 필요함

 

 

cpu 스케줄러

ready상태의 프로세스들 중에 cpu를 할당해줄 수 있는 프로세스를 선택

현 cpu running 중인 프로세스가 있고 ready인 프로세스 중 어느 프로세스를 선택할 것인가?

 

 

preemptive(선점형) vs non-preemptive (비선점형)

선점형 : 강제로 쫓아낼 수 있다. <-> 자발적으로 나가게

스케줄러가 할당 중인 프로세서를 쫓아낼 수 있다.

비선점형 : cpu를 프로세스가 선점하고 나면, release하기 전까지는 자발적 나오기 전 까지는 프로세스가 쓰도록 내버러둠

 

 

1. running -> waiting :  cpu선점 중이다가 I/O로

2. running -> ready 

3. waiting -> ready : 파일 입출력 끝남, cpu 점유하러 ready로 감

4. 프로세스 terminate

 

1, 4 -> 자발적으로 이동 (비선점형)

2, 3 -> ready로 갔으나 cpu를 선점할 우선순위가 높으면 cpu에 현 할당중인 프로세스를 쫓아낼 수 있죠!

(선점형(V) 또는 비선점형(비효율적))

 

 

 

dispatcher

context switch를 해주는 모듈

프로세스에게 cpu를 넘겨줌

(cpu running -> waiting or ready 쫓아냄 -> ready의 프로세스를 할당)

 

할 일:

cpu를 하나의 프로세스에서 다른 프로세스로 할당해주고

새로운 프로세스의 적당한 위치로 resume해줌

 

스케줄러 : 프로세스를 선택

dispatcher : 실제 context switching를 수행

 

 

dispatcher가 몹시 빨라야 함!

dispatcher latency는 가급적 짧아야한다.

 

 

 

dispatcher latency란?

프로세스를 멈추고 다른 프로세스를 running하는 시간

 

 

스케줄링 목표 

cpu utilizaion : cpu를 가장 많이 사용하기 busy

throughput : 단위시간 내 완료된 프로세스의 횟수 증가

turnaround time : 프로세스 도착 ~ 종료까지 시간 최소화

waiting time !중요! : 프로세스가 ready queue에서 대기하는 시간을 최소화

response time : 응답시간 최소화

 

 

 

<스케줄링 알고리즘의 종류>

1. FCFS : first come first served 먼저온 순서대로 처리, 공평

문제많음, 초창기 운영체제서 사용

2. SJF : shortest job first , SRTF : shortest remaining time first (남은 시간이 가장 적은 것)

아래부터 시분할 관련 time-sharing

3. RR : round-robin 정해진 시간만큼만

t1, t2, t3, ... ready queue에 있다가 정해진 시간만큼만 사용

4. priority-based : RR을 쓰는데, 우선순위를 부어

5. MLQ : multi-level queue : 우선순위에 따라 ready queue를 따로

6. MLFQ : multi level feedback queue : ready queue를 따로 + 우선순위 수정, 현대적 스케줄러

 

 

 

FCFS

가장 간단한 알고리즘

CPU를 먼저 요청한 프로세스에게 먼저 할당

queue에 넣어 대기시키고, 다 실행하면 나가고 ...

순서대로 처리

 

 

FCFS

p1 - p2 - p3

burst time

p1 24, 

p2 3

p3 3

 

waiting time

앞의 프로세스가 끝날 때까지 계속 대기

p1 = 0

p2 = 24

p3 = 27

total 51

average 51/3 = 17

average waiting time을 줄일 방법은?

 

 

p2 - p3 - p1

p1 = 6, pw = 0, p3 = 3

total = 9

average = 3

 

 

turnaround time : 도착 ~ 종료까지

 

 

p2 - p3 - p1

p1 = 30, p2 = 3, p3 = 6

total = 39

average = 13 

 

 

note

average waiting time이 cpu-burst time이 얼마냐에 따라 매우 달라짐

FCFS는 비선점형. 다 끝날때까지 기다림

 

cpu bound 1개와 I/O bound 여러 개가 있을 때 

(cpu 많이 쓰는 프로세스와 , cpu는 적게 쓰지만 I/O를 많이 쓰는 프로세스)

 

convoy effect 호송 효과, 똥차 효과

(스포츠카들이 똥차 때문에 막힌다)

cpu 다 쓸때까지 하염없이 기다려야함

cpu 잠깐만 쓰면 되는데

 

따라서 FCFS는 비효율적이다

 

 

 

 

SJF

sortest next cpu burst first 스케줄링

프로세스의 next CPU burst time을 계산하여 가장 작은 것을 할당

 

 

 

 

 

SJF : provabily optimal 최적이라는 것이 증명가능하다

이론적으로 최적

average waiting time이 최소다.

short 프로세스의 waiting time의 감소

 

실제 사용하는 알고리즘은 아니다.

구현이 불가하다

next CPU burst를 기준으로 삼는데 알수있는 방법이 없다.

cpu 얼마나 쓰는지 예측할 수 없다.

 

SJF를 엄격하게 구할 수 없고, 예측하여 근사적으로 구하자

predicted CPU burst가 가장 짧은 프로세스를 선택하자.

과거를 보자. previous cpu burst를 보자. 

 

과거에 측정된 값을 보고, 지수적 평균을 내자

알파가 0 --> 완전히 과거 기록만

알파가 1 --> 완전히 최근 기록만

 

 

 

SJF는 preemptive or non-premptive

새로운 프로세스가 ready queue에 도착했을 때

p1의 cpu burst time이 더 짧아도 cpu 선점 중인 p0가 끝날 때까지 기다려주는 경우 non-preemptive SJF

p1의 cpu burst time이 더 짧아서 p0를 ready queue에 넣고 p1가 cpu 선점할 경우 preemptive SJF

 

 

 

SRTF : shortest remaining time first : preemptive SJF

새 프로세스의 cpu burst가, 실행 중인 프로세스의 remaining time보다 더 작으면 새 프로세스를 선점한다.

 

 

 

 

 

 

 

 

선점형인 SRTF (효율적) < 비선점형인 SJF

 

 

 

RR

time sharing

round robin :  preemptive FCFS 시간단위를 줌 (time quantum, 보통 10 millisecond)

단위시간 내에 프로세스를 실행하고 단위시간이 끝나면 내보냄

circular queue

cpu burst가 한 시간단위보다 짧을 때

- 프로세스가 자발적으로 cpu release

 

cpu burst가 한 시간단위보다 길 때

 - 타이머가 interrupt

 - context swtich 실행

 - 프로세스가 ready queue의 끝tail에 들어감

 

 

 

RR에서 average waiting time이 좀 더 길 수 있다.

하지만 SJF와 섞어쓰는 순간, 유용

RR은 반드시 적용됨

 

RR은 preemptive

cpu burst가 한 시간단위보다 초과하면, 강제로 쫓겨남, 다시 ready queue로 돌아감

 

time quantum에 따라서 성능 달라짐

 

 

context switch마다 dispatch latency 발생!!

- dispatch latency를 최소화하는 것이 좋으나

- 그렇다고 quantum이 무한대가 되면 FCFS가 됨

- quaumtum이 너무 작으면 context switch가 너무 자주 일어나 dispatch latency가 길어짐

 

 

 

 

- time quantum을 너무 많이 줘도, 너무 적게 줘도 turnaround time이 줄어듦

- 적절히 turnaround time이 높게끔 quantum을 지정해줘야

 

 

Priority-base 우선순위 스케줄링

우선순위를 어떻게 부여할 것인가?

우선순위가 높은 프로세스에게 cpu 할당

우선순위가 같은 경우 FCFS

 

SJF - predicted next CPU burst가 짧을 경우 우선순위가 높다

 

 

 

preemptive : SRTF

non-preemptive : SJF

 

priority scheduling에서 항상 따르는 문제 : 

starvation 기아! indefinite blocking 무한정 대기

우선순위가 낮은 프로세스는 무한정 기다려야할지도 모른다.

 

해결방법 : aging

오래 기다린 시스템에게는 우선순위 높여주기

 

 

RR + Priority scheduling

- 우선순위를 우선적으로 보되

- 우선순위가 같을 경우, round-robin 스케줄링

 

 

 

Multi-level queue MLQ 스케줄링

우선순위에 따라 ready queue를 따로

 

 

 

 

 

 

 

Multi level feedback queue MLFQ 스케줄링

 

- 우선 여러 개의 큐가 존재

- 큐들은 각각 다른 레벨의 우선순위를 가지므로 multi level queue

- 과거의 수행 결과를 보고 우선순위를 변경해주는 식의 방법이므로 feedback이라는 단어도 추가됐습니다.

 

• 규칙 1 : 우선순위가 높은 프로세스들을 먼저 수행한다.
• 규칙 2 : 작업들이 같은 우선순위를 갖는다면 RR로 수행한다.
• 규칙 3 : 새로운 프로세스가 시스템에 들어가면 가장 높은 우선순위를 부여한다.
• 규칙 4 : 작업은 모든 우선순위에서 주어진 time quauntum를 모두 사용하면 우선순위가 감소한다.

규칙 5 : 일정 시간 후 시스템의 모든 작업을 우선순위가 가장 높은 큐로 이동한다.

 

 

modern OS

실제로는 Thread 스케줄링을 함, not process

컴퓨터에서 task로 사용하는 단위는 Thread

결론 : OS 커널은, 커널 Thread를 대상으로 CPU 스케줄링을 한다.

 

 

SQMS

하나의 큐에 작업들을 넣어서 처리하는 방법을 SQMS(Single Queue Multprocessor Scheduling)

 

- 단순하다는 장점

- 스케줄러가 여러 CPU에서 잘 작동하는지 확인하기 위해 Lock을 사용

- Lock을 사용하면 성능을 크게 저하시킬 수 있음

- 실제 프로그램 수행 시간보다 Lock을 처리하는 작업에 더 많은 시간을 사용할 수 있음

 

Lock : 여러 CPU가 동시에 공유 데이터가 접근할 때, 데이터의 일관성을 유지하기 위함

 

 

 

MQMS

SQMS에서의 문제점을 보완한 MQMS(Multi Queue Multiprocessor Scheduling)

 

- SQMS와의 차이점 : 큐가 여러 개

- 각각의 큐는 RR과 같은 특정한 스케줄링 방법을 사용

- 작업이 시스템에 들어오면 하나의 큐에만 배치되고, CPU 독립적으로 스케줄링

 

 

 

 

출처 : https://www.inflearn.com/course/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B3%B5%EB%A3%A1%EC%B1%85-%EC%A0%84%EA%B3%B5%EA%B0%95%EC%9D%98/dashboard [인프런]

출처: https://icksw.tistory.com/127 [PinguiOS]