운영체제 - 9(CPU스케줄링2, 쓰레드/다중 프로세서 스케줄링)

스케줄링 알고리즘

 

 

1. Multilevel Queue Scheduling

(Queue를 여러개 두어 우선순위 스케줄링)

 

- 서로 다른 유형별로 구분하여 분리처리

- 유형에 맞는 스케줄링 알고리즘을 각각 따로 적용

Ex) 대화형 프로세스 - 일괄처리/Round-robin(실시간으로 즉각즉각 스케줄링이 되어야 하기때문에)

* 문제점

- 프로세스를 초기에 어떠한 Queue에 넣으면 계속 거기 있어야 하고 우선순위가 높은/낮은 Queue로 옮겨줄 수 없어 신축성 있는 스케줄링이 어렵다. - 우선순위가 밀려 기아 상태로 들어설 가능성이 있다.

 

2. HRN(Highest Response-Rate Next) 스케줄링

- 비선점 스케줄링 기법으로 가변적 우선순위를 두어 때에따라 우선순위가 변하게함

 

많이 기다렸다면 Or 서비스 받을시간이 적다면

우선순위가 높다

 

 

3. 알고리즘의 평가

 

- 최적의 스케줄링 알고리즘을 선택하는것은 중요

- 알고리즘 선택기준 : 프로세서 이용률, 응답시간, 처리율 등(평균 반환시간 / 평균 대기시간)

 

** 평균 대기시간 : FCFS > RR > 비선점SJF => 대기시간이 짧을수록 좋으므로 비선점 SJF가 좋은 알고리즘

 

*** SJF 스케줄링 알고리즘의 문제점 : 현실성 X(프로세스를 실행하기도 전에 작업시간이 얼마나 걸릴지 예측 불가)

 

---

 

쓰레드 스케줄링

 

1. 단일/다중 CPU에서 멀티쓰레드 처리개념

 

**쓰레드를 쓰는 이유 : 병행성을 높여 성능을 높이기 위해

=> 이 쓰레드를 처리하는 것은 CPU, 따라서 단일 CPU에서 멀티쓰레드 처리는 쉽지않다

 

2. 3가지 모델

 

1) Many to One Model

: N개의 User-thread가 1개의 Kernel thread 공유

=> User thread는 Kernel thread를 공유하므로 효율적이나 Kernel이 하나이므로 multi 효과가 없음

 

2) One to One Model

: 1:1로 대응하여 User thread와 Kernel thread가 N개씩 같은 수를 가짐

=> 병행성 효과는 좋으나 User가 Kernel thread를 과다하게 생성하는 문제 발생 - 과한 Resource 사용 문

 

3) Many to Many Model

(Many to One Model + One to One Model)

: User thread가 Kernel thread를 무작정 만드는 것이 아니라 Kernel에 갯수제한을 두어 만듬 - Multiplexing

 

---

다중 프로세서 스케줄링

 

- CPU가 여러개인 경우 어떻게 스케줄링해줄 것이냐

=> 여태까지는 1개의 CPU(프로세서)

 

1. 부하공유(Load Sharing) 스케줄링

- CPU당 스케줄링 이벤트가 발생

- 스케줄러는 어떤 CPU에서든지 실행될 수 있으며 Single Shared Queue를 공유함

 

2. 전용 프로세서 할당 스케줄링

- CPU 각각 자신만의 큐를 가짐

- Per-CPU Ready Queue

3. 갱(Gang) 스케줄링

- 한 프로세스에 속한 여러 쓰레드들을 동시에 스케줄링

- 쓰레드간 문맥교환 횟수를 줄일 수 있어 효율적

 

4. 동적 스케줄링(Load Balancing)

- CPU 간 준비 큐의 크기가 같도록 관리 => 부하 균등

* 균등을 위한 2가지 기능(지속적인 모니터링)

1) Push Migration

: 커널은 주기적으로 Queue Size를 점검하여 크기가 작은 Q로 쓰레드를 이동시킴

2) Pull Migration

: Queue가 Empty 상태가 되면 다른 Queue의 쓰레드를 가져옴

* 프로세스 연관성 문제

 프로세스가 다른 Queue에 Migration 되면, 이전 CPU 내의 캐시에 저장해 놓은 데이터를 사용할 수 없음

** 문제점 해결을 위한 2가지 방안

1) Soft Affinity

: Migration을 그냥 그대로 일부 허용

2) Hard Affinity

: Migration을 강력하게 불허

 

---

프로세스 스케줄링 사례

 

 

1. Window

 

1) 쓰레드 단위로 스케줄링

2) 선점방식 알고리즘 채택

3) Multilevel Feedback Queue + Priority 스케줄링 선택(실제로 작업관리자에서 우선순위 변경가능)

 

2. Linux

 

1) Linux Kernel 이전/이후로 대폭 변화함

2) 이전 : Priority 스케줄링만 사용 => 단순 명료하나 Overhead 발생문제

3) 이후 : Multilevel Queue + Priority 스케줄링 알고리즘 사용

     - 3개 클래스로 분류하여 클래스마다 다른 스케줄링 방법 적용