6. CPU Scheduling

OS의 중요 기능 2가지 중 하나인 'HW 자원에 대한 배분'

∴ OS가 각 프로세스들에게 CPU를 어떻게 배분?? 이걸 알아야 함.

 

(CPU) Scheduling이란?

: 어떻게 프로세스들에게 CPU의 사용을 할당할 것인가.

 

- Multiprogramming이란 기법이 발전하게 되면서 CPU Scheduling이 발전함.

-> 멀티프로그래밍: Memory 내의 Ready State의 프로세스들 중 하나에 CPU를 할당하는 방법.

 

- CPU 스케줄링 목표: CPU 사용률과 처리량의 최대화

CPU-I/O Burst Cycle

프로세스 수행 사이클

- CPU-I/O Burst Cycle

: 프로세스가 CPU Burst와 I/O Burst를 번갈아 가며 수행을 함.

- CPU Burst: CPU로 연산을 수행하는 시간

- I/O Burst: I/O 처리를 위해 기다리는 시간

 

- Process 분류에 따른 CPU Burst 특징

- CPU-Bound Process: 짧은 주기의 긴 CPU Burst

- I/O-Bound Process: 긴 주기의 짧은 CPU Burst

 

CPU Burst Time으로 어떤 프로세스, 시스템이든 간에 대체로 3~5ms 정도 CPU Burst를 사용하고 이후는 계속해서 차지를 거의 안함.

그렇다면 언제 실행 대상인 프로세스가 바뀔까...??

일단 Scheduling의 결정(돌리는 프로세스에 대한 변경)은

1. Running -> Waiting 상태로 바뀔 때(Interrupt나 I/O 대기 상태가 됨)

2. Running -> Ready 상태로 바뀔 때

3. 수행이 종료되었을 때

4. Ready -> Running 상태로 바뀔 때

이뤄진다.

 

스케줄링의 종류

1. 비선점형 스케줄링(Non-preemptive Schekduling)

: 실행 중인 프로세스의 CPU 사용을 강제로 멈추게 하지 않고 자연스럽게 프로세스가 CPU 사용을 그만둘 때 다른 프로세스를 실행시키는 스케줄링 기법.

- [Running -> Waiting], [Ready -> Running] 일 때 수행 가능하며 요즘 잘 안 쓰이는 방식임.

 

2. 선점형 스케줄링(Pre-emptive Scheduling)

: OS가 프로세스들의 스케줄링에 적극 개입, 일정 시간을 넘어서 점유하고 있는 프로세스를 강제로 멈춰서 다른 프로세스들의 실행을 보장해주는 스케줄링 기법.

 

스케줄링 정하는 기준

1. CPU 사용률: 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율. 크면 Good.

2. 처리량(Throughput): CPU가 단위 시간 당 처리하는 프로세스의 개수. 크면 Good.

3. 응답 시간(Response Time): 상호작용하던 System에서 요청 후 첫 응답이 올 때까지의 시간. 짧으면 Good.

4. 대기 시간(Waiting Time): 프로세스가 Ready Queue에서 대기하는 시간의 총합. 짧으면 Good.

5. Turnaround Time: 프로세스가 시작해서 끝날 때까지 걸리는 총 시간

 

이러한 기준들을 고려하여 이상적인 스케줄러를 만드는데 사실 현실적으로 모든 조건 만족하는 것은 만들기 Hard!

∴ 시스템의 용도에 따라 스케줄링의 요구사항을 맞춤 -> 이에 알맞은 스케줄링 알고리즘이 필요함.

ex. 슈퍼 컴퓨터: CPU 사용률 / 개인용 컴퓨터: 응답시간 / 워크 스테이션: 처리량

 

스케줄링 알고리즘(Scheduling Algorithms)

1. FCFS(First-Come, First-Served) Scheduling

: 먼저 CPU 할당을 요청한 프로세스에 CPU를 먼저 할당한다.

- 비선점형 스케줄링

- 작업의 수행 순서에 따라 대기시간이 변함. -> ∴ 대기시간이 짧아야 하는 작업의 경우엔 맞지 않은 알고리즘임

2. Short-Job-First Scheduling

: 다음 CPU Burst Time이 가장 짧은 프로세스에 CPU를 먼저 할당한다.

 

- 비선점형 스케줄링: 한번 CPU 할당 받으면 자신 CPU Burst Time 끝날 때까지 안 놓음.

 

- 선점형 스케줄링: CPU 할당 받아 수행 중이더라도 CPU Burst Time이 자신의 현재 남은 시간보다 짧은 시간인 프로세스가 생성되면 그거에 CPU를 양보함.(= SRTF(Shortest Remaining Time First Scheduling))

위와 같은 예시가 있다 하자.

1) 비선점형 스케줄링: 일단 제일 먼저 도착한 P1 실행 - 그러다 P2옴 - 무시하고서 계속 실행 - 그러다 P3옴 - 무시하고서 계속 실행 - 그러다 P4옴 - 무시하고서 계속 실행 - 7초일 때 P1 끝남 - 당시 제일 적은 Burst Time인 P3 실행 - 8초에 P3 끝남 - 그 다음엔 둘이 같으니 먼저 온거(P2) 실행 - 12초에 P2 끝남 - P4 실행 - 16초에 P4 끝남

대기 시간은

P1: 0초에 와서 0초에 시작함 -> 0초

P2: 2초에 와서 8초에 시작함 -> 6초

P3: 4초에 와서 7초에 시작함 -> 3초

P4: 5초에 와서 12초에 시작함 -> 7초

∴ 평균 대기시간: 4초

2) 선점형 스케줄링: 일단 제일 먼저 도착한 P1 실행 - 그러다 2초에 P2옴 - P1은 자기 남은 시간 5초보다 P2의 4초 Burst Time이 짧으니 P2 실행 - 4초에 P3옴 - P2의 남은 2초보다 P3의 1초가 짧으니 P3 실행 - 5초에 P3끝나면서 P4도 옴 - P1:5초, P2: 2초 남은 상황에 P4는 4초이니 P2, P4, P1 순으로 실행함.

대기 시간은

P1: 0초에 와서 실행하다 멈추고 9초 대기하다가 실행해서 완료 -> 9초

P2: 2초에 와서 실행하다 멈추고 1초 대기하다가 실행해서 완료 -> 1초

P3: 4초에 와서 바로 실행해서 완료 -> 0초

P4: 5초에 와서 대기하다가 7초에 시작함 -> 2초

∴ 평균 대기시간: 3초

3. Priority Scheduling

: 미리 주어진 우선순위에 따라 CPU를 할당한다

 

- 비선점형 스케줄링

- 선점형 스케줄링: 새로 생성된 프로세스가 현재 실행 중인 프로세스보다 높은 우선순위를 가지면 CPU를 양보함.

 

<문제점>

기아 상태(Starvation) 발생할 수 있음!!!!

: 왜 생기냐고? 낮은 우선순위 프로세스의 경우엔 계속 밀리잖아...그러다보면 계속 밀려서 수행이 아예 안될 수 있음.

 

- 해결책: Aging 기법

: 할당을 기다리는 시간에 따라 우선순위를 증가시키는 방법

ex. 대기시간이 길어지면 점점 우선순위 값을 높여줌으로서 기아 상태를 해소시킴

4. Round-Robin Scheduling

: Time Quantum(시간 단위, 보통 10-100ms임)을 정해두고 그만큼 수행 후 Ready Queue의 끝에 넣어두고 다음 프로세스로 넘기는 방식으로 순회한다

- 선점형 스케줄링

- 문맥 전환이 많지만 응답 시간이 짧다.

 

만약 n개의 프로세스가 있고 Time Quantum이 q시간이면...

각 프로세스는 최대 (n-1)*q 시간만 대기한다.(앞에가 모두 Time Quantum을 꽉꽉 채워서 끝낸다는 가정이 최악임.)

만약 q가 엄청 크면 FCFS와 비슷하게 동작하고 / q가 작은데 만약 context switching time이 이보다 크다면(즉, 오버헤드가 크다면) 효율이 매우 떨어짐. 

5. Multilevel Queue Shceduling

: Ready Queue를 여러개로 분리하고 각 Queue마다 다른 스케줄링 알고리즘을 사용하는 기법

 

- Foreground Queue: 상호작용이 많은 프로세스를 위한 Queue -> 주로 Round-Robin 기법 사용

- Background Queue: CPU 연산 작업을 주로 수행하는 프로세스를 위한 Queue -> 주로 FCFS 사용 

 

핵심: 어떠한 알고리즘을 어떠한 몇 개의 Queue로 나눠서 사용할 건지, 각 Queue들을 OS에서 어떻게 관리할 것인지.

6. Multilevel Feedback Queue Scheduling

: Multilevel Queue에서 프로세스들이 서로 다른 Queue로 이동할 수 있도록 한 스케줄링 기법

-> 간단히 생각하면 수행하다가 원하는 스케줄링 방식의 Queue로 이동시키는 방식임.

 

- 필요 요소

1. Queue의 개수

2. 각 Queue마다의 스케줄링 기법

3. 언제 프로세스를 한 단계 높은 Queue로 옮길지.

4. 언제 프로세스를 한 단계 낮은 Queue로 옮길지.

5. 어떤 프로세스가 특정한 기능을 필요할 때 그걸 제공하는 Queue로 이동 시켜줄 방법.

 

예를 들면...

 

어떤 프로세스를 Round-Robin 방식으로 수행 중임.

근데 이게 time quantum인 8초를 지나도 안 끝내짐.

근데 나 이거 해야해.

그래서 tq가 16초인 Queue로 옮김.

근데 16초 지나도 안 끝나짐.

그럼 에이씨 몰라 넌 FCFS 형에 처한다!!하고 FCFS Queue로 옮김.

-> 이런 식으로 상황에 따라, 혹은 해당 프로세스의 기능에 따라 Queue를 옮겨서 수행하는 방식임.

 

Multiple Processor Scheduling

: 하나의 시스템에서 여러개의 CPU를 사용 시, CPU Scheduling이 복잡해진다

-> 각각의 CPU에 서로 다른 I/O 장치가 연결되어 있으면 그걸 하나의 시스템에서 사용하는데에 복잡하고, 각 CPU들이 서로 다른 종류이면 각 CPU마다의 명령어 셋, 처리 속도 등이 달라서 복잡해짐.

 

멀티 프로세싱에는 2가지가 있음.

 

1. 비대칭 멀티프로세싱

- 하나의 CPU만이 시스템 자료구조(스케줄링, I/O 작업 등)를 관리(즉, 각자 역할이 정해짐)

-> 모든 CPU가 서로 공유하며 접근하는 것보다 더 간단하게 데이터 공유가 이루어짐.

 

2. 대칭 멀티프로세싱

- 다같이 관리를 같이 함.

-> 서로 공유 및 멀티 스레딩 개념이 문제없이 해결되게 설계되어야 하고 비대칭에 비해 복잡함.

 

스케줄링 방식

1. Processor Affinity(친밀도)

: CPU는 지가 하던 프로세스 작업에 대해 계속 그것만 맡음

-> 이러면 캐시를 쌓고 그럼에 따라 더 효율적으로 수행 가능~

 

2. Load Balancing

: 하나의 CPU에 몰리지 않게 잘 조절해서 배정해주는 것.

ex1. CPU가 모두 동일하면 동일한 프로세스들을 수행할 수 있기에 나눠줘서 수행 가능.

ex2. CPU가 각각 Ready Queue를 갖고 있으면 일부 CPU에 몰릴 수도 있음.

ex3. CPU들이 하나의 Ready Queue를 두고서 사용하면 사용 가능한 CPU들에 차례로 프로세스를 배정해 줌.

-> 이렇게 다양한 가능성이 있으니 필요에 따라 설계해서 프로세스들이 하나의 CPU에 몰리지 않게 배정해줘야 함.