CPU Scheduling

CPU Scheduling

■ 멀티프로그래밍 

- CPU의 물리적인 갯수와 무관하게 프로그램이 수행되면 해당 프로그램이 끝나기 전에 다른 프로그램이 다시 시작해 수행하는 것. → 여러개의 프로그램이 번갈아가며(Content Switch) CPU를 점유함.

 

※ Content Switch: 현재 진행하고 있는 Task(Tread, Process)의 상태를 저장하고 다음 실행할 Task의 상태를 읽어 적용시키는 것.

 

 

■ Process scheduling vs Thread scheduling

- 현대의 OS에선 CPU scheduling의 단위는 Kernel-level Thread이다.

- Process scheduling, Thread scheduling은 바꿔서 사용할 수 있다.

- Thread scheduling은 Thread specific에 사용된다.

 

■ Basic Concept

멀티프로그래밍으로 CPU 확장.

└ 오직 한개의 core만 작동한다.

└ 최대한 CPU를 바쁘게 만들어야한다.

 

 

■ CPU-I/O burst Cycle

 

- 프로세스 실행은 CPU 실행 주기 및 I/O (=Input/Output) 대기로 구성.

 

- CPU burst

└ 프로세스가 프로세서를 사용하는 시간.

 

- I/O burst

└ 프로세스가 I/O를 기다리는 시간.

 

- 프로세스가 CPU burst와 I/O burst를 번갈아가며 처리.

 

※ Cycle은 시간단위로 scheduling이 이루어진다.

 

 

 

 

Clock Cycle

- Clock Pulse   /   Basic pipeline -

■ Clock Pulse: 특정한 주기를 가지고 올라갔다, 내려갔다를 반복함.

- Pulse가 한번 올라갈 경우, 내부적인 명령어 수행이 순차적으로 이루어짐.

 

 

■ Clock cycle

- pulse의 단위

- 일반적으로 Clock time(또는 Clock speed)이 높을수록 CPU가 빠름.
- Clock time(sec) = 1/Clock frequence (hz)

- 정해진 시간마다 한 cycle이 진행됨 → 그 단위는 frequency 역수가 됨.

 

- clock frequence가 빠르면 빠를수록 cycle time은 짧아진다.

└ 명령어 처리는 clock cycle에 의존하기 때문에 clock cycle time에 비례한다. clock frequency가 빨라져서 cycle time이 짧아지면, 같은 시간에 더 많은 명령어를 처리 가능.

 

 

 

CPU Scheduler

 

New: 프로세스가 만들어질 때

Running: 프로세스가 수행될 때

Waiting: 수행 명령이 올 때까지 기다릴 때 (Ready로 가기 전 대기)

Ready: Running에 들어갈 수 있을 때

Terminate: 프로세스가 종료될 때

 

 

 

- os 내부에 존재하며 CPU가 놀고 있으면 안된다.

- CPU가 어떠한 이유건 내가 아무것도 수행하고 있느 프로세스가 없을때 경우 os가 ready에 있는것 중

하나를 선택해 CPU에게 할당해준다.   ※ CPU Scheduler의 역할

 

 

■ When CPU Scheduling working 

• 프로세스가 실행되다가 wating으로 갈 때 (I/O를 기다릴 경우)
• 프로세스가 실행되다가 ready로 갈 때 (나에게 할당된 시간을 다 썼을 경우)
• wating에서 I/O 이벤트가 들어온 후 ready 단계로 갈 때 & running에서 프로세스가 끝난 후 terminate 상태로 갈 때 (= CPU가 더이상 일을 하지 않을때)

 

 

 

■ Preemptive Scheduling (중요!)

 

• Nonpreemtive (비선점 스케쥴링)

- 프로세스가 CPU를 해제하기 전까지 프로세스를 제거할 수 없다.

- CPU가 프로세스에 할당되면 프로세스가 종료되거나 대기 상태로 전환되어 CPU를 해제하기 전까지 상태를 유지한다.

- 외부에서 절대 간섭하지 못한다.

 

• Preemtive (선점 스케쥴링)

- 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.

- 효율적이기 때문에 윈도우를 포함한 현대의 운영체제, Mac, Linux, Unix는 Preemptive Scheduling 알고리즘을 사용한다.

- 상황에 따라 간섭이 가능하다.

 

 

※ 간섭의 유무에 따라 전체적인 성능의 판도가 바뀐다.

 

 

 

■ Dispatcher

Ready Queue에 있는 것 중 하나를 CPU scheduler가 선택하면, CPU에 할당하여 실 행하도록해줌.

 

Dispatchr module은 CPU scheduler가 선택한 프로세스에 CPU를 제공:

• Context 전환
• User mode 전환
• 프로그램 재실행을 위한 사용자 프로그램의 적절한 위치로의 이동

 

▶ Dispatcher Process

1단계: 어떠한 형태로든 실행이 끝남 (중단)

2단계: PCB(Process Controller Block)에 현재 state를 저장

3단계: 수행할 프로세스의 정보를 CPU에 적재

4단계: 수행한다.

 

1~3단계: Dispatch latency

└ 프로세스를 중지하고 다른 프로세스를 실행하는데 걸리는 시간.

└ 실제로 본래 프로세스의 역할과는 무관한 일을 하는 시간이다.

 

2~3단계: Content switch

└ 1, 4단계가 번갈아가며 수행하면서 Content switch 과정을 거치며 생기는 TIme less가 얼마나 생기는지 = Dispatch latency에 의해 결정된다. (빠르면 빠를수록 불필요한 시간이 줄어든다.)

└ Process, Thread를 나누는 이유이다. 이 과정이 Process는 빠르고 Thread는 짧기 때문.

 

 

 

■ Scheduling Criteria

 

CPU Utilization [CPU 이용률]

- 가능한 CPU를 바쁘게 유지해야한다.

└ CPU를 1시간을 켜놨을 때 실제로 CPU가 얼마나 움직였는가. 이는 좋은 지표이다.

 

 

Throunghput [처리량]

- 시간 단위당 실행을 완료하는 프로세스의 수.

└ 프로세스를 내가 n개 수행했는데 그 프로세스가 끝나는데 걸린 시간을 측정한 것.

 

 

Turnaround time [소요 시간]

- 특정 프로세스를 실행하는 시간

└ 프로세스 하나가 끝나는데 걸리는 평균적인 시간. (들쭉날쭉이면 안된다)

※ Throunghput과 비슷하지만 다르다. 

 

 

Waiting time [대기 시간]

- 프로세스가 대기열에서 대기 중인 시간.

└ 프로세스가 들어가면 실제로 수행되는 시간이 있고 Ready에서 기다리는 시간이있다. Ready에서 기다리는 시간이 평균적으로 얼마나 되는가?

 

 

Response time [응답 시간]

- 요청이 제출된 후 첫 번째 응답이 생성되기까지 걸리는 시간.

 

 

단순성을 위해 우리는 오직 하나의 CPU burst 그리고 평균 대기 시간을 고려한다.

뛰어난 Scheduling은 무엇인가? 무언가를 좋다 나쁘다를 판별하기 위해서는 기준이 존재해야한다. 

 

 

 

FCFS (First Come, Fisrt Served[=First out])

가장 손쉬운 알고리즘이다. 먼저 도착하면, 먼저 service를 받는다.

 

▶ Example with 3 processes

 

Burst Time = Process를 수행하는데 걸리는 시간.

P1~P3가 끝나는데 걸리는 총 시간 = 30

 

i)

P1은 전에 들어온 Queue가 없기 때문에 0 만큼 기다린다.

P2는 P1이 수행되는 시간이 24이기 때문에 24 만큼 기다린다.

P3는 P1, P2 (24+3) 끝나는 시간인 27만큼 기다린다.

 

ii)

P2, P3가 3이기 때문에 P1은 6 만큼 기다린다.

P2는 바로 시작하기 때문에 0 만큼 기다린다.

P3는 P2가 끝나고 바로 시작하기 때문에 3 만큼 기다린다.

 

→ 위와 같은 두가지(i, ii) 과정을 Convoy effect 라고 부른다.

하나의 큰 프로세서가 앞을 장악하고 있어 뒤의 Queue가 밀리는 경우를 말한다.

 

 

 

■ SJF (Shortext Job First)

각 Process에 CPU burst의 길이를 연결한다.

Queue에 Process가 쌓여있으면 가장 빨리 끝난 순서대로 수행한다.

 

 

Process이 빠른순으로 보는 것이 아닌 Burst Time이 빨리 끝난 순으로 나열.

┗ SJF는 average waiting time을 최소화하는 가장 좋은 솔루션이다.

 

 

 

다음 CPU burst의 길이를 어떻게 결정하는가?

┗ 사용자에게 물어본다, 예측한다.

 

 

■ Prediction of next CPU burst (다음 CPU burst 예측)

이를 알 수 있는 유일한 방법은 과거의 값으로 판단하는 방법 뿐이며 SJF를 사용하려면 이 과정을 반드시 거쳐야한다.

 

- 이전 CPU burst에 기초해 예측된 다음 CPU burst가 가장 짧은 프로세스를 선택.
- 지수 평균을 사용해 이전 CPU burst의 길이를 사용하여 수행.

 

 

▶ Expenential Averaging

 

 

→ 실제 수행된 시간

→ 예측된 시간

실제 수행된 시간이 많이 쓰여지기 시작하자, 예측된 시간도 증가된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

■ Shortest Remaining Time First

- SJF의 Preemptive(선점형) 버전이다.

- 새로운 프로세스가 Ready Queue에 도착할 경우 SJF를 사용하여 Schedule을 다시 설정한다.

- 새로운 Job이 Queue에 들어오면, 일단 Job을 멈추고 새로운 Job을 포함해 다시 scheduling을 진행하여 새롭게 할당한다.

 

 

Arrival Time: Ready Queue에 들어오는 시간

 

 

 

 

 

 

 

 

■ Round Robin (RR)

- Scheduling이 Interrupt가 걸리지 않는 이상 무조건 끝까지 수행하는 것이 Scheduling 기법들의 Base이다. 하지만, Time sharing 기법을 사용하면 각각의 프로그램이 한번에 사용할 수 있는 Time slice는 정해져있다.

 

- 기본적으로 FCFS를 사용한다. 하지만, Time slice가 끝나면 다른 곳에 넘겨준다.

- 구현이 쉽다.

 

 

 

 

4단위로 자름 -> p1 burst time은 24이고 p1이 schedule에서 6번 실행됨 (24/6)

P1이 먼저 들어와 수행 > Time이 되면 일단 멈추고 P2에게 양보 > P2, P3가 수행 (기본 Time slice보다 작음 → Time slice가 끝나기 전에 Job을 끝냄) > 이후로 다시 P1이 수행

 

P1 = 4

P2 + P3 = 6

10  - 4 = 6만큼 waiting

 

- Queue is large > FCFS

- Queue is small > Context 전환 Overhead 높음

 

 

■ Priority Scheduling (우선순위 예약)

CPU가 가장 높은 우선순위로 프로세스에 할당됨

- 우선 순위 번호가 각 프로세스와 연결됨.
- 일반적으로 가장 작은 정수는 가장 높은 우선순위와 같다.
- SJF는 Priority Scheduling의 특별한 버전이다.

 

▶Priority

내부 정보: 요구사항, 열려있는 파일의 수외부 정보: 프로세스의 중요성, 비용, 정책

 

 

average waiting time보다 Priority에 중점을 둔다.

┗ Priority의 오름차순으로 Process를 시작한다.

 

 

 

 

 

 

 

 

 

 

■ Starvation (중요!)

- Priority Scheduling (우선순위예약)은 일부 낮은 Priority Process를 무기한 대기 상태로 두는 것을 의미.

 

□ 해결방법

- Starvation의 문제 해결.

- 우선순위를 증가 시킨다.

 

□ RR 및 Priority Scheduling

- 가장 높은 우선 순위 프로세스를 실행.
- RR을 사용하여 동일한 우선 순위로 프로세스를 실행.

 

 

 

 

 

 

 

■ Multilevel Queue

- Ready Queue는 여러 대기열로 구성된다.
- 각 Priority scheduling이 별도의 대기열을 갖는다.

□ OS에선 Prioity 별로 Ready Queue를 만들어 둔다

- real time processes: 반드시 일정시간 내에 끝내야한다. (최우선)

- system processes: os에서 무언가 직접 만져야한다.

- interactive processes: 사용자와 서로 입출력을 주고 받아야하기 때문에 반응이 빨라야한다. (ex 마우스)

- batch processes: background에서 돌고있는 것.

 

 

■ Multilevel Feedback Queue

- 프로세스가 들어오면 Starvation을 방지하기 위해 Priority별로 최소한의 실행시간을 보장한다.

- 프로세스가 다양한 대기열 사이를 이동할 수 있음.

 

□매개변수에 의해 정의된 Multi level feedback Queue Scheduler:

- 대기 행렬의 수
- 각 큐에 대한 Scheduling algorithm
- 프로세스 업그레이드 시기를 결정하는 데 사용되는 방법
- 공정의 강등 시기를 결정하는 데 사용되는 방법
- 프로세스가 서비스를 필요로 할 때 프로세스가 입력할 대기열을 결정하는 데 사용되는 메서드

 

 

 

 

■ Approaches to Multiple Processor Scheduling

- 데이터를 공유하는 두 프로세스의 경우를 고려한다.
- Symmetric multiprocessing(SMP/대칭 멀티프로세싱)은 각 프로세서가 자체 스케줄링하는 곳이다.
- 모든 스레드는 공통 준비 대기열에 있을 수 있다 (a).
- 각 프로세서는 자체적인 개별 트레드 대기열을 가질 수 있다 (b).

- SMP scheduling -

• Common ready queue: T0, T1, T2와 같은 Job들을 Common하게 공유한다. 이 중 하나를 고르면 그 중 가장 만만한 것을 Core에 할당.
• Per core run queues: 프로세스가 각각의 Queue를 가지고 있기 때문에 하나씩 내부적으로 공유한다.

- Load balancing Issue 발생

 ┗ a의 경우에서 하나의 core가 놀거나 일을 많이하는 경우는 없다. 놀고 있는 core에 할당하기 때문.

 ┗ b의 경우 queue의 갯수에 따라 성능차이가 보임.

 

 

■ Simulanceous Multitherading (SMT)

- core에서 하드웨어적으로 스레드를 지원하는 것.

- Scheduling에 대해 캐시를 고려해야 한다.
- 하드웨어 스레드가 도입됨(인텔의 하이퍼스레딩)

 

 

- Processor의 Core 내부에 스레드를 위한 별도의 하드웨어가 들어가 있음.

 

 

 

 

 

 

 

- Processor가 보기엔 4 core 8 스레드지만 os가 보기엔 8 core이다.

 

 

 

 

 

 

■ Heterogeneous Multiprocessing (HMP)

- 명령 집합은 동일하지만 클럭 속도와 전력 면에서 차이가 있다.
- 작업의 특정 요구에 따라 특정 코어에 작업을 할당하여 전력 소비량 관리를 향상 시킨다.

 

 

Real Time CPU Scheduiling

Soft real time Systems

- 중요한 실시간 테스크가 가장 높은 우선 순위를 가지지만 테스크 예약 시기에 대한 보장은 없음.

- 시간을 지키지 않으면 품질이 급격하게 나빠짐. ㅡㅡ^;

 

Hard real time Systems- 테스크는 마감일까지 서비스되어야 함.

 

□ 이벤트 지연시간

- 이벤트 발생과 서비스 사이의 시간

 

 

□ Types of latencies

 

- Interrupt latency

 ┗ 서비스가 인터럽트를 중단하는 루틴의 도착부터 시작까지의 시간.

 

- Dispatch latency

 ┗ CPU에서 현재 프로세스를 제거하고 다른 프로세스로 전환하는 예약 시간.