[운영체제] CPU Scheduling (3)

Multilevel Queue

: 줄마다 있는 우선순위 

프로세스를 어디에 넣을 것인가?

비지 않았다면 거기에만 우선권을 줌.

우선 순위가 낮은 프로세스는 starvation -> 이를 해결하기 위한 방안 소개.

 

- Ready Queue를 여러 개로 분할.

(foreground - interactive / background - batch : 사람과 interaction 없는 것만)

- 각 큐는 독립적인 스케쥴링 알고리즘을 가짐.

(forground : RR / background - FCFS : overhead 줄임.): 줄에 특성에 맞는 큐 별 스케쥴링 채택.- 큐에 대한 스케쥴링 필요: 어느 줄에 스케쥴링을 주고, 줄 안에서 누구에게 줄 지를 결정.  우선순위 높은 것이 비어 있을 때만 낮은 것에 줌. (starvation 발생할 가능성 있음.)   이를 방지하기 위해 어느정도 나눠서 주는 경우 생각할 필요 있음.

 

 

Multileve Feedback Queue

- 프로세스를 다른 큐로 이동 가능.

 : 프로세스가 줄 간에서 이동할 수 있는 경우.

 

각 큐에서는 어떤 스케쥴링을 사용할 것인가.

상위 큐 / 하위큐 승격/하강 보내는 기준.

 

 

Multilevel Queue

: 줄마다 우선순위 존재 (위로 갈수록 높고, 아래로 갈수록 낮음.)

 

우선 순위가 높은 CPU가 먼저 얻어야 하기 때문

 

Ready Queue를 여러 개로 분할

- foreground (interactive) -> RR을 쓰는게 응답 시간 짧게 함.

- background (batch - no human interaction) : CPU만 오랫동안 쓰는 프로세스, 줄에 넣는 기준이 있음. -> FCFS(context switch overhead를 줄이기 위함.)

: 줄에 특성에 맞는 queue 별 스케쥴링 필요

 

어떤 큐에 줄 것인가에 따라 스케쥴링 필요

starvation을 막기 위해 각 줄별로 어느정도 CPU 시간 나눔.

-> 가령 전체 시간 80%는 높은 줄 / 20%는 낮은 줄 

 

처음 들어오는 프로세스 -> 우선 순위 높은 큐 (RR에서 time quantum을 짧게 )

-> 아래 큐로 갈수록 time quantum이 길어지다가 -> 아래 큐에서는 FCFS로 사용 

 

 

Multiple - Processor Scheduling

: CPU가 여러 개인 경우

 

- Homogeneous processor

Queue에서 한 줄로 세워서 각 프로세스가 알아서 꺼내가게 할 수 있음.

특정 프로세스에 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해짐.

- Load sharing

부하를 적절히 조절하는 매커니즘 필요.

각각의 cpu마다 별도의 줄(큐)를 서게 할 수 있음.

- Symmetric Multiprocessing

: 모든 프로세스 알아서 스케쥴링 결정

- Asymmetric Multiprocessing

: 하나의 프로세스가 전체를 담당. 나머지 프로세스는 거기를 따름.

 

Real-time Scheduling

: 정해진 시간 안에 반드시 실행 되어야 함. deadline 보장

그때 그때 하기 보다는 미리 스케쥴링을 하여 배치함.

주기적으로 activate 해야 하는 작업들이 많기에 job을 보장받아야 함. 

 

 - Hard real-time systems : 정해진 시간 안에 반드시 끝내도록

- Soft real-time computing : 일반 프로세스에 비해 높은 우선순위 갖는 것을 처리

 

Thread Scheduling

: 프로세스 안에 있는 수행 단위 => Thread

 

- Local Scheduling

운영체제 모름. 사용자 프로세스가 직접 함.

프로세스에 cpu를 줄 지만을 결정.

- Global Scheduling

운영체제가 thread 존재 앎.

어떤 thread에게 cpu scheduling을 줄 지를 결정.

 

Algorithm Evaluation

어떤 알고리즘이 좋은지 평가할 수 있는 방법.

 

- Queuing Models 

이론적인 방법.

Queue에 job이 도착하여 쌓일 때 프로세스들을 cpu 능력에 따라 처리하고 빠져나감. (단위 시간 당 몇 개를 처리할 수 있는지)

- Implementation (구현) & Measurement (성능 측정)

이론적인 방법과 상반.

실제로 구현해보고 실제 작업(workload)에 대해 측정해 봄.

- Simulation 

구현을 하기 어려울 때 사용하는 방식. 실제로 하는 것이 아닌 모의 실험을 함.

알고리즘을 모의 프로그램으로 작성 후 trace 입력하여 결과 발표.