운영체제 10장 - Multiprocessor and Real-Time Scheduling


스케줄링의 대상이되는 병렬처리기의 종류
느슨하게 연결된 분산 병렬 컴퓨터 - 클러스터라고 부름, 데이터 센터에서 구성되는 리눅스 머신의 연결, 
기능적으로 여러 코어가 들어가서 하나는 master - general purpose processor가 들어가서 os를 동작시키고, 다른건 응용처리를 하는 프로세서. 
긴밀하게 연결된 멀티프로세서 - gpu, 일기예보 계산에 사용되는 대규모 병렬처리기


병렬처리를 할때 synchronization하는 크기에 따라서 병렬처리를 구분
Fine grain - gpu
medium - 병렬 프로세싱, 멀티태스킹
Coarse - concurrent processing
very coarse - distributed processing, 인터넷 서비스가 예시


독립적인 병렬처리는 동기화가 전혀 없는 프로세스가 있을때
그것을 여러개의 프로세스를 사용해서 처리하는것
이런 경우는 암달의 법칙에서 본것처럼, 시리얼하게 처리되는 부분이 없기에
처리기를 더 넣을수록 성능은 선형적으로 증가하게 된다


여러개의 프로세스가 동시에 도는 상황을 말함


하나의 애플리케이션에서 여러개의 스레드를 두고 스레드들이 동기화하면서 여러개의 처리기에서 돌아가는 병렬처리를 의미
과제에서 하는 스레드 프로그램이 병렬처리기에서 돌아간다면 그 예시라고 할수 있다


gpu프로그램에서 cuda를 사용할때 프로그래밍 하는것처럼
아주 미세한 단계에서 동기화를 하는 병렬처리를 의미
매트랩에서 벡터연산 병렬처리가 예시


이러한 병렬처리기를 사용할때, os에서 어떤 기능을 제공해야 하는가?
병렬처리기를 스케줄링하는 기능을 제공해야 한다
개념은 간단한데 생각할 점이 많다

생각해야 할점
- 어떻게 디스패치
- 멀티프로그래밍을 어떻게 구현
- 프로세스에 할당하는것은 어떻게
- 병렬처리기에 스케줄링하는 메커니즘 자체를 어떻게 구현?


프로세스를 어떻게 프로세서에게 할당할 것인가
만약 모든 프로세서가 동일하다면, 동적으로 또는 정적으로 결정하여 나눠준다
정적으로 한 프로세스에게 permanently하게 assign한다면, 
장점은 스케줄링 기능의 오버헤드가 적다. 캐시가 망가진다거나 캐시가 hit가 안되는 그런 일은 없다
고정적으로 assign의 단점은 놀고있는게 있어도 활용할수가 없다는것

이것을 해결하기위해 다이나믹하게 프로세서를 할당하는 방법이다


프로세스에게 프로세스를 동적으로 정적으로 할당하던간에
그 할당하는 프로그램이 돌아가는 프로세스가 필요하다
구성하는 방법에는 master를 두는 방법이 있고, 아무나 하게 하는 방법이 있다


master - 특정 프로세서가 프로세스에게 프로세서를 할당하는 역할을 한다
slave - 나머지는 master에게 요청을 하고, 요청하면 master가 할당해주는 방법
자원의 충돌이 생겼을때 master가 다 해결하기때문에 쉽게 해결 가능하다
그러나 master 고장시 전체 시스템을 못쓴다, 그리고 master에게 요청이 몰리면 성능에 bottleneck이 된다는 단점이 있다


peer 방법은 각 프로세서가 스스로 스케줄링 하도록 하는 방법
실행할 프로세서의 풀을 만들어놓고 각 프로세서가 비면 가져다가 실행하는 방법이다
공통적인 풀을 사용해서 여러 프로세서가 병렬로 돌기 때문에
이 자체 구현에 있어서도 병렬처리의 동기화라는 문제를 갖는다


일반적으로 특정 프로세서에 프로세스를 할당하는 방법을 두지 않고
하나의 큐를 두고 그것을 공유하며 우선순위에 따라서 여러개의 큐를 구성해서 쓰면서 우선순위에 따라서 각 프로세서에 프로세스들을 할당하게 된다
이러한 것을 멀티서버를 갖는 큐잉 시스템으로 모델링 할 수 있다


1개, 2개 프로세서를 가질때 성능 측정, 듀얼 프로세서를 쓰면 throughput이 좋아진다
SRT는 그 간격이 더 벌어진다


스레드 스케줄링
스레드는 프로세스 나머지 부분에서 분리가 되어, cpu에 관련된 부분만 빼낸것
애플리케이션은 여러개의 스레드로 구성될 수 있고 그것들은 같은 주소공간에서 동시에 돌아갈수 있다
유니프로세서에서는 스레드는 하나의 애플리케이션에서 여러 기능을 동시에 수행할수 있다는 장점이 있고, IO overlap이 가능하다는 장점이 있다
멀티프로세서에서는 진정한 parallelism을 구현할수 있다


스레드를 스케줄링 하는 방법
Load Sharing
Gang Scheduling
Dedicated Processor Assignment
Dynamic Scheduling
 


Load Sharing 
가장 간단한 방법, 부하를 어떤 centeralized 하지 않고 여러 프로세서에게 나눠주는 방법
FCFS방법으로, 작은수의 스레드 먼저, 선점버전 사용가능

단점으로는 부하를 모두 담아두는 큐를 유지하게 되는데, 그 큐의 상호배제를 유지하기 위해서, synchronization하게 되고 성능에 bottleneck이 될 수 있다
그리고 동적으로 여러 프로세스에게 돌아다니면서 실행되기 때문에, cpu를 빼앗긴 스레드는 동일한 cpu에서 시작되지 않을 수 있다. 그러면 캐쉬가 망가져서 덜 효율적이게 된다
어떤 프로그램의 스레드들이 한꺼번에 동시에 프로세서를 할당받지 못해서 성능이 급격히 떨어지는 문제가 생길 수 있다.



Gang Scheduling
그러한 것을 방지하기 위해서 프로세스에 속한 모든 스레드를 동시에 할당하는 방법
장점 - 동시할당이 됨 synchronization으로 인한 blocking 문제 해결가능, medium grain, fine grain에서 유용하게 사용

낭비를 줄이기 위해서는 gang(그룹)들간에 동일하게 cpu를 나눠줄 필요는 없다
우측처럼 나눠준다면 idle시간을 줄일수 있을것이다


Dedicated Processor Assignment
애플리케이션이 스케쥴링 되어 각 스레드를 한번 할당하게되면 애플리케이션 끝날때까지 그대로 두는것
장점 - 오버헤드가 있어도 병렬처리기가 대규모라면 성능의 손실은 무시가능, 캐시의 hit rate가 높기에 프로그램을 빨리 실행가능


병렬처리기를 잘못 구성하면 성능이 급격히 떨어지는것을 볼 수 있다
처리기를 넣는다고 해서 항상 성능이 좋아지는것은 아니다, 문맥교환이나 캐시의 오염으로 인해 처리기를 늘렸을때 성능이 떨어질 수 있다


Dynamic Scheduling
동적으로 프로세서를 할당