[운영체제] Multiprocessor Scheduling

멀티프로세서 스케줄링에는 다음의 세 가지 설계 이슈들이 있다.

• 프로세스를 어느 처리기에 할당할 것인가?
• 각 처리기에서 멀티프로그래밍을 지원할 것인가?
• 다음번 실행 프로세스로 어떤 프로세스를 고를 것인가?

 

Processor Affinity (처리기 친화성)

- 준비상태의 쓰레드를 그 쓰레드가 전에 실행되었던 처리기에 스케줄링하는 것이 합리적이다.

 

- Processor Affinity는 처리기 전용 지역 캐시(local caches) 때문에 중요하다. 

• 스레드가 수행할 때 수행되었던 처리기 전용 캐시에 데이터가 여전히 남아 있을 수 있기 때문에 성능이 개선될 수 있다.
• 다른 처리기에 변경되어 수행되는 것은 필요한 데이터가 새로운 처리기에 다시 로드되어야 하고 지난 처리기의 캐시 라인들이 무효화되어야 한다는 것을 의미한다.

Soft Affinity : 
Hard Affinity : 

 

 

Multiprocessor Scheduling

 

Assignment of processes to processors

- 처리기 전체를 하나의 자원 집합으로 간주하여 처리기에 대한 요구가 있을 때마다 어느 것이든 사용 가능한 처리기를 프로세스에게 할당해준다.

 

 

Global queue (single queue) , Single Queue Multiprocessor Scheduling(SQMS)

 

- 프로세스에게 처리기가 처음에 한번 할당되고 난 후 끝날 때까지 바뀌지 않기 때문에 스케줄링 기능이 단순해져 오버헤드가 줄어든다는 장점이 있다.

 

- 아무 이용가능한 처리기를 스케줄링함.

 

 

 

Static Assignment (multi queue) , Multi-Queue Multiprocessor Scheduling (MQMS)

 

장점 : Scalability 좋음 : Mutual Exclusion 불필요, 여러 개의 CPU가 있어도 상관없음, Cache affinity

 

단점 : 워크로드 불균형 (load imbalance) -> migration

 

 

 

 

 

Use of multiprogramming on individual processors

어느 한 순간에 여러 처리기가 쉬고 있다면, 처리기 한 개의 입장에서 이용률을 높이기 위해 멀티프로그래밍을 사용하는 것이 오히려 전체 성능에 도움을 주지 않을 수도 있다.

 

 

Actual dispatching of a process

- 간단한 스케줄링 정책일수록 오버헤드가 적기 때문에 더 효과적일 수 있다.

- 복잡한 스케줄링 알고리즘보다는 간단한 것이 훨씬 좋다.

 

 

멀티 프로그래밍 단일처리기 스케줄링 기법들에서는 FCFS 같은 단순 정책보다는 우선순위나 과거 행적에 기반한 고급 정책들이 좋은 성능을 보인다.

- 단일 처리기 시스템에서 어떤 특정 상황에 대해 효과가 있었던 스케줄링 정책이 처리기가 두 개로 늘어나면 그 효용성이 현저히 떨어진다.

- 처리기의 개수가 더 늘어날 경우 더 심해질 것이 분명하다.

 

 

 

 

 

Thread Scheduling (쓰레드 스케줄링)

- 하나의 응용프로그램은 여러 개의 쓰레드들로 구성될 수 있고, 이 쓰레드들은 동일한 주소 공간 내에서 서로 협력하며 병행 실행 된다.

 

- 쓰레드를 사용함으로써 얻을 수 있는 가치는 멀티프로세서 시스템에서 극대화된다.

 

- 쓰레드 간 통신이 매우 빈번하게 발생하는 응용프로그램의 경우에는 쓰레드 관리 방법이나 쓰레드 스케줄링 방식이 조금만 바뀌어도 전체 성능에 중대한 영향을 미칠 수 있으므로 조심해야 한다.

 

Load sharing (부하 공유)

- 프로세스들은 어떤 특정 처리기에 고정되어 할당되지 않는다.

Gang scheduling (갱 스케줄링)

- 서로 관련되어 있는 쓰레드들을 그룹으로 묶은 후 그룹으로 묶여진 처리기들 상에서 일대일 방식으로 실행함.

Dedicated processor assignment (전용 처리기 할당)

- 쓰레드를 어떤 특정 처리기에 고정 할당

 

 

 

Load Sharing (부하 공유)

장점

- 가장 간단한 방법

- 여러 처리기들에게 부하가 공평하게 분산된다. 

- 모든 처리기가 엑세스할 수 있는 전역 큐를 둘 수 있다.

 

단점

- 모든 처리기가 접근하는 전역 큐는 상호 배제 조건이 유지되는 방식으로 관리되어야 한다.

- 선점 모드 스케줄링 정책에 의해 실행이 끊겼던 쓰레드가 나중에 다시 실행을 재개하더라도 전에 실행되던 처리기와 동일한 처리기에서 실행되지 않을 가능성이 높다.

- 모두 소속을 구분하지 않고 취급되기 때문에 어느 한 프로세스에 속한 쓰레드들 모두가 동시에 처리기를 할당받지는 못할 수도 있다. -> 성능 구짐

 

 

 

 

 

Gang Scheduling (갱 스케줄링)

한 번에 여러 개의 프로세스를 동시에 여러 개의 처리기로 스케줄링하는 방식이다.

 

- 한 응용프로그램을 위한 것으로서 한 응용프로그램 내의 모든 쓰레드가 동시에 실행 중이지 않으면 성능에 치명적인 문제가 발생하는 경우에 효과가 큰 스케줄링 방식이다.

 

장점

- 서로 밀접한 관계가 있는 프로세스들이 그룹을 이루어 동시에 실행된다면 동기화로 인한 블록을 최대한 줄일 수 있다.

- 단 한번의 스케줄링으로 여러 프로세스들을 한번에 여러 처리기로 스케줄링하기 때문에 스케줄링 오버헤드가 줄어든다.

- 서로 협력하면서 실행되는 쓰레드들을 한꺼번에 스케줄링하면 자원 할당에 드는 시간을 절약할 수 있음.

 

 

 

 

Processor 할당을 어떻게 할 것인가?

 

 

시스템에 N개의 처리기와 M개의 응용프로그램이 있고 각 응용프로그램은 N개 이하의 쓰레드로 구성되어 있다고 가정하자.

왼쪽 그림 같은 경우에 처리기는 4개이고 응용 프로그램은 2개인데 한 응용프로그램에는 쓰레드가 4개, 다른 응용 프로그램에는 쓰레드가 하나 밖에 없는 경우를 생각해보자.

응용 4프로그램이 실행될 때에는 3개의 처리기를 쉬게할 수 밖에 없으므로 자원의 37.5% 낭비

 

오른쪽 그림은 쓰레드의 수에 따라 차등을 두어 처리기 시간을 배정하는 것도 좋은 대안이 될 수 있다.

-> 전체 시간의 4/5가 할당될 것이고 응용프로그램에는 1/5 만큼만 할당되어 처리기 낭비율을 15%로 낮출 수 있다.

 

 

 

Dedicated Processor Assignment (전용 처리기 할당)

응용프로그램이 스케줄링될 때 소속 쓰레드들 각각마다 하나의 처리기가 고정 할당되고 실행을 완료할 때까지 쓰레드-처리기 할당 상황이 변하지 않는다.

 

응용프로그램 내의 어떤 쓰레드가 입출력 대기나 쓰레드 간 동기화 등의 이유로 실행이 선점된다면 그 사이 해당 처리기가 쉬어야만 하기 때문에 멀티프로그래밍을 지원하지 않는 방법이다.

 

 

처리기 시간의 낭비가 매우 심함. (만약 응용프로그램 내의 어떤 쓰레드가 입출력 대기나 쓰레드 간 동기화 등의 이유로 실행이 선점된다면 그 사이 해당 처리기가 쉬어야만 하기 때문)

 

 

이런 시스템은 언제사용?

- Processor가 아주 많은 시스템인 경우

프로세서 활용도는 더 이상 효율성이나 성능에 대한 지표만큼 중요하지 않다.

 

 

 

Windows Scheduling (윈도우 스케줄링)

- 스케줄링의 기본 단위는 프로세스가 아닌 쓰레드이다.

- 우선순위 기반 쓰레드가 비실시간 쓰레드들에 비해 높은 우대를 받는다.

- 선점모드 스케줄링을 구현하고 있음.

- 우선순위 수준이 같은 모든 활성 쓰레드들은 라운드-로빈 방식으로 스케줄링된다.

- 멀티프로세서 스케줄링으로 어떤 처리기에서도 실행된다.