[운영체제] Lect10) Multiprocessor and Real-Time Scheduling

멀티 프로세서 시스템이란 뭘까? 2가지 특징이 있다

- 프로세서가 여러 개이지만, 메인 메모리가 딱 하나다

- 하나의 OS가 시스템 전체를 관리한다

 

멀티 프로세서 시스템에서는 동기화(Synchronization) 개념이 매우 중요하다

Process들이 얼마나 자주 동기화를 하느냐 성분표

 

[멀티 프로세서 시스템 스케줄링 디자인 이슈들]

- 동기화 빈도

- 프로세서 수

 

프로세서에 프로세스를 할당하는 방법은 2가지가 있다

방법 1: 각각의 프로세서마다 별도의 레디-큐를 둔다

방법 2: 전역 큐를 둔다 (큐가 c.s. 안에 있어야 한다) - Mutual Exclusion

요즘에는 방법 2를 채택한다

 

멀티 프로그래밍을 쓸까? 말까?

동기화가 자주 일어나지 않는다면 문맥 전환이 적어 오버헤드가 적기 때문에 멀티 프로그래밍을 잘 사용할 수 있지만

동기화가 자주 일어난다면 문맥 전환이 잦아 오버헤드가 크기 때문에 멀티 프로그래밍을 안 하는 게 더 나을 수 있다

 

<프로세스 디스패칭 순서>

9장에서는 '순서'가 가장 중요했지만 Multiprocessor System에서는 어떤 순서로 dispatch 해도 response time이 다 비슷해 크게 상관이 없다

 

 

 

ㅁ스레드 스케줄링(Thread Scheduling)

4가지

 

ㅇLoad Sharing: 스레드 단위 스케줄링

[CPU 개수 <= application의 스레드 개수]

(한 application 스레드를 동시에 실행 x)

 

레디-큐에 스레드 별로 줄을 슨다

전역 큐(FCFS)

 

단점 3가지

- 전역 큐가 Mutual Exclusion 때문에 c.s. 안에 있어야 한다 - 병목현상

- 캐시가 덜 효율적이다 -> 시스템 성능 ↓

- 한 application에서 나온 스레드들이 동시에 작업된다는 보장 x

 

이러한 단점들이 있어도 CPU 개수가 적을 때는 이게 최선이기 때문에 많이 사용한다

 

 

ㅇGang Scheduling: application 단위 스케줄링

[CPU 갯수 >= application의 스레드 개수]

(한 application 스레드를 동시에 실행 ㅇ)

 

레디-큐에 application 별로 줄을 슨다 (Gang == application 라 생각하자 ㅋㅎ)

<Time Sharing>

Example of Scheduling Groups with Four and One Threads

 

 

ㅇDedicated Processor Assignment: Process / Thread Switching 없이 끝까지 실행하는 방식

Gang Scheduling의 특화버전이다

(Gang Scheduling 보다 CPU 개수가 훨씬 多)

 

단점: Processor fragmentation problem

 

 

ㅇDynamic Scheduling: 동적으로 되면 해주고 안되면 안 해준다

OS가 스케줄링 역할의 반만 한다

OS는 Process를 프로세서에 할당해 주는 역할만!

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

ㅁReal-Time Scheduling

Hard real-time task: 반드시 deadline을 지켜야 한다 (못 지키면 컴퓨터가 터진다 ㅋㅋㅋㅋ)

Soft real-time task: deadline을 지키는 게 필수는 아니다

periodic task: 주기와 데드락이 정해져 있는

aperiodic task: 주기와 데드락이 정해져 있지 않은

 

여기서 우리가 중점적으로 다룰 것은 periodic한 Soft real-time task 이다

1. Earliest-deadline Scheduling: 데드라인을 보고 우선순위를 정한다

 

 

2. Rate Monotonic Scheduling: 데드라인이 아닌 주기를 본다

주기가 짧으면 우선순위가 올라간다

 

더 많이 사용하는 방식이다

 

 

ㅇPriority Inversion(우선순위 역전): 우선순위가 높은 Process보다 낮은 Process가 먼저 실행되는 경우

동기화 기법: lock (e.g. 뮤텍스 락)

unbounded priority inversion

 

ㅇPriority Inversion(우선순위 상속)

T3가 T1의 우선순위를 상속받는다 (T3의 우선순위가 1이 된다)

 

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

[OS별 스케줄링 시스템]

ㅁWindows: 우선순위 큐 총 32개

16개: Real-time task를 위한 큐

- FCFS (같은 큐 안에서는 RR)

16개: Non-real-time task를 위한 큐

- Feedback 큐

Windows Thread Dispatching Priorites

 

우선순위 피드백 시스템 기반이며, 프로세서를 많이 사용하고 범위가 정해져 있다

 

(Windows는 애초에 처음부터 멀티 프로세서 시스템을 가정하고 만든 OS이다)

 

 

 

 

ㅁUNIX SVR4(UNIX의 최신버전 - Windows와 유사하다): 우선순위 큐 총 160개

(우선순위 1) 60개: for Real-time Process

(우선순위 2) 40개: for 커널모드 Process

(우선순위 3) 60개: for 유저모드 Process

 

UNIX SVR4 Dispatch Queues

 

 

똑같이 Windows와 유사하다!

우선순위 피드백 시스템 기반이며, 프로세서를 많이 사용하고 범위가 정해져 있다

 

 

ㅁLinux: 우선순위 큐 총 140개

100개: Real-time task를 위한 큐 (2가지 종류가 있다)

- FIFO

- RR

40개: Non-real-time task를 위한 큐

 

FIFO라 할지라도 우선순위가 더 높은 task가 나타나면 CPU를 뺏긴다

Linux 스케줄링 자료구조

 

 

 

 

 

 

 

 

 

참고 및 출처: Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham)