Multi-Processor Scheduling
Multiprocessor System에는 다음과 같이 분류된다.
- Loosely coupled || distributed multiprocessor || cluster
각각의 프로세서는 자기만의 메인 메모리와 I/O를 가진다. - Functionally specialized processor
specialized processor은 마스터 프로세서로 컨트롤 되고 서비스를 제공한다. - Tightly coupled multiprocessor
프로세서끼리 메인 메모리를 공유하고 os의 통합 컨트롤을 받는다.
Granularity
task를 수행하는 일의 양
특정 task를 수행하는데 instruction의 양
| Grain Size | Description | Synchromization Interval (instructions) |
|---|---|---|
| Fine | 단일 instruction에서 병렬 | < 20 |
| Medium | application 안에서 병렬 프로세싱, multitasking | 20~200 |
| Coarse | multiprogramming 환경에서의 병행 프로세스의 multiprocessing | 200~2000 |
| Very Coarse | 단일 computing 환경에서의 분산 처리 | 2000~1M |
| Independent | 여러 관계 없는 프로세스 | not applicable |
Independent Parallelism
프로세스 간 동기화가 없다
-> 독립적인 application 또는 job
ex) time-sharing system : 각각 유저는 특정 application에서 수행함
multiprocessor는 단일 프로세서의 multiprogrammed와 동일한 서비스를 제공한다.
Coarse and Very Coarse Grained Parallelism
프로세스 간 동기화가 됨
단일 프로세서의 multiprogrammed에서 병렬 processes를 다루기 쉽다.
Coarse
통신하거나 동기화해야 하는 concurrent process의 모음은 multiprocessor 구조를 사용하여 이점을 얻을 수 있다.
Very Coarse
process간 상호작용이 드물게 발생하는 경우, 분산 시스템이 좋은 방법을 제공해준다.
Medium-Grained Parallelism
단일 application은 단일 process 안에서 thread 모음을 구현할 수 있다.
thread간 상호작용이 빈번하게 일어나므로 scheduling 결정이 application 성능에 영향을 끼친다.
Fine-Grained Parallelism
단일 instruction에 병렬성이 내제되어 있다.
프로그래머가 병렬을 감지하는 것을 어렵다.
Design Issues
multiprocessor는 scheduling의 3가지 이슈가 있다.
- 프로세스가 프로세서에 할당
- 각각 processor의 multiprogramming의 사용
- process의 dispatching
Assignment of Processes to Processors
가정: 모든 프로세서는 같다.
- static
- dynamic
Static assignment
proccess가 하나의 processor에 영구적으로 할당이 된 경우 각 processor에 대해 short-term queue가 할당된다.
오버헤드가 덜 발생한다.
단점: 한개의 processor가 놀고 있는 상태일 수 있고 다른 processor는 backlog 상태일 수 있다.
-> common queue 사용
-> dynamic load balancing 사용 : threads는 다른 processor의 queue로 이동할 수 있다.
dynamic 과 static 방식은 process를 processor로 할당하는 2가지 방식이 있다.
- master/slave arcitecture
master는 job을 scheduling한다.
slave는 유저 프로그램을 실행하고 서비스가 필요한 경우 master에서 요청을 보낸다. - peer architecure
커널을 어떤 processor든지 실행할 수 있고, 각각의 processor들은 self-scheduling이 가능하다.
The Use of Multiprogramming on Individual Processors
coarse, independent application에서 각각 processor는 높은 이용률을 성취한다.
medium application에서는 각각 processor는 바쁘다.
Process Dispatching
다음 프로세스를 어떻게 선택할까?
1. 단일 프로세서에서의 multiprogrammed
이전 사용에 기반해 우선순위 사용하거나 정교한 scheduling algorithms을 사용하여 성능을 향상시킨다.
2. multiprocessor
단일 접근은 더육 효율적이고 오버헤드가 덜한다.
Thread Scheduling
- Load Sharing
- 프로세스는 각각의 processor에 할당되지 않는다.
-global queue 사용. 만약 어떤 processor가 쉬는 상태면 queue에서 선택한다. - Gang Scheduling
- 관련된 thread가 스케줄 되고, processor에 같은 시간에 실행된다. - Dedicated Processor Assignment
- 각 프로그램이 실행되는 동안 같은 수의 스레드가 같은 수의 processor에 할당된다.- 프로그램이 종료되면 다른 프로그램에 processor는 반환한다.
- Dynamic Scheduling
- process에 thread 수는 실행하는 동안 변경될 수 잇다.
Load Sharing
multiprocessors에서 흔하게 사용된다.
장점
- processor간 load가 균일하게 분산되고 작업이 이용가능한 동안 processor는 유후상태가 되지 않는다.
- scheduler 중심적이 아니다.
processor가 이용 가능할 때, scheduling routine은 processor가 다음 thread를 선택할 수 있다. - global queue가 우선순위, 과거 실행을 고려할 수 있다.
단점
- memory access bottlenecks
central queue가 상호배제되는 메모리 영역을 차지한다. - Less efficient caching
선점 thread는 같은 process의 local cache에 실행된다. - Seriously compromised performance
모든 threads는 같은 시간에 processor에 접근할 수 없다.
Gang Scheduling
thread의 동시 스케줄링이 가능하다.
장점
- 성능 증가
block의 동기화가 감소될 수 있고 process switching이 덜 필요하다. - scheduling 오버헤드가 감소된다.
scheduling 결정은 다수의 processor에 영향을 끼친다.
Dedicated Processor Assignment
application이 스케줄 되면, 각각 thread는 process에 할당된고 완료될 때까지 할당된다.
thread가 block되면 다른 thread도 동기화된다. -> processor는 유후상태가 된다.
Dynamic Scheduling
thread의 수를 동적으로 변경 가능하다.
job이 1개 또는 그 이상 processor 요청할 때
- processor가 유후상태이면, 요청에 만족하도록 그것을 사용함
- 요청한 작업이 새로 도착한 작업일 경우, 현재 두개 이상의 processor가 할당된 작업에서 하나를 가져와 하나의 processor를 할당
- 요청을 만족할지 못할 경우, processor를 사용할수 있게 되거나 job이 요청을 취소할 때까지 미해결 상태로 유지
- 프로세서에 대한 충족되지 않은 요청의 현재 대기열을 검색, 현재 프로세서가 없는 목록의 각 작업에 단일 processor를 할당, 목록을 다시 스캔하여 FCFS 기반으로 나머지 프로세서 할당
