멀티프로세서 스케줄링

멀티프로세서 스케줄링

• SQMS (단일 큐 방식)
• MQMS (멀티 큐 방식)

 

❓ 병행성 concurrency

공유데이터 접근할 때, 올바른 연산 결과를 보장하기 위해(상호배제를 보장하는 위해) 락-프리(lock-free) 데이터 구조 사용.

하지만, 성능 측면에서 CPU의 개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느리게 되어 문제가 있다.

 

하지만, 더 많은 CPU를 추가해도 더 빨리 실행되지 않는 문제 발생!

이를 쓰레드를 이용(멀티 쓰레드 응용 프로그램)하면 더 많은 수의 CPU가 주어질 수록 더 빠르게 실행된다.

 

❓ Thread와 Process의 차이는?

    프로세스는 독립적, 높은 수준의 격리, 내결함성
자체 메모리 공간, 리소스 및 실행 환경을 갖춘 독립적인 프로그램으로 다른 프로세스와 격리되어 있으며 별도의 프로그램 인스턴스로 실행.
격리되어 있으므로 한 프로세스의 충돌이나 오류는 일반적으로 다른 프로세스에 영향을 미치지 않습니다.
    스레드는 한 프로세스 내의 동시 실행되고 데이터를 공유할 수 있음. 별령성
프로세스의 더 작은 단위로 위 프로세스와 동일한 메모리 공간과 리소스를 공유하며 동일한 프로세스 내의 여러 스레드가 동시에 코드를 실행할 수 있음. (쓰레드는 자신만의 스택을 갖고 있음)
한편, 한 스레드의 오류(예: 메모리 액세스 위반)가 잠재적으로 동일한 프로세스의 다른 스레드에 영향을 미칠 수 있음을 의미합니다.

 

 

❓ 쓰레드를 이용(멀티 쓰레드 응용 프로그램)하면 더 많은 수의 CPU가 주어질수록 더 빠르게 실행된다. 이유는?

병렬성 때문, 

---

멀티프로세서

여러개의 CPU 코어가 하나의 칩에 내장된 멀티코어 프로세스

 

❓ 단일 CPU 하드웨어와 멀티 CPU 하드웨어의 근본적인 차이

• 단일 프로세스간의 데이터 공유
• 하드웨어 캐시의 사용 방식

---

단일 CPU 하드웨어 

출처 : OSTEP-KOR

하드웨어 캐시 계층이 존재한다.

CPU는 우선 해당 데이터가 캐시에 존재하는지 검사한다. 캐시에 존재한다면, 데이터는 훨씬 빨리 접근되므로 프로그램은 빨리 실행한다.

 

CPU ↔ 메모리 : 수십 수백 nano second

CPU ↔ 캐시 : 수 nano second

---

❓ 캐시

메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하는 작고 빠른 메모리다.

캐시를 이용하면 시스템은 크고 느린 메모리를 빠른 메모리처럼 보이게 한다. 

 

❓ 캐시는 지역성에 기반한다.

시간지역성 temporal locality : 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다.

공간지역성 spatial locality : 주소 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다.

---

 

멀티 CPU 하드웨어

출처 : OSTEP-KOR

❓ 캐시 일관성 문제 

cache coherence

메모리에 데이터를 쓰는 것은 시간이 오래 걸리므로 메인 메모리에 기록하는 것은 보통 나중에 한다.

그래서 변경된 D′ 가 아니라 옛날 값인 D를 가져오는 문제가 발생할 수 있다.

 

❓ 캐시 일관성 해결책

기본적인 해결책은 하드웨어에 의해 제공된다.

 

캐시 일관성 프로토콜, 버스 스누핑(bus snooping)이란?

캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링 한다.

캐시 데이터에 대한 변경사항이 발생(더티 비트를 사용하여 추적)하면, 자신의 복사본을 무효화(invalidate) 시키거나 갱신한다.

하지만, 이러한 나중 쓰기(write-back) 캐시는 시스템 성능이 향상될 수 있지만 메인 메모리에 쓰기 연산이 지연되기 때문에 일관성 유지 문제를 훨씬 복잡하게 만든다.

 

캐시 친화성

cache affinity

CPU에서 실행될때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려 놓게 된다.

그래서 다음 번 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리하다. 왜냐하면 해당 CPU 캐시에 일부 정보다 이미 존재하고 있기 때문에 더욱 빠르게 실행될 것이기 때문!

 

그래서 멀티 프로세서 스케줄러는 스케줄링 결정을 내릴 때 캐시 친화성을 고려해 가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야 한다.

 

---

멀티프로세서 스케줄링

 

❓ 단일 큐 방식

single queue multiprocessor scheduling

출처 : OSTEP-KOR

장점 : 구현이 용이하고 워크로드의 균형을 맞추기 용이

단점 : 많은 개수의 프로세스에 대한 확장성과 캐시 친화성이 좋지 못하다.

 

❓ 멀티 큐 방식

라운드 로빈(작업이 끝날 때까지 기다리지 않고 일정 시간동안 실행한 후 실행 큐에 다음 작업으로 전환)으로 프로세스 실행된다고 가정해보자.

출처 : OSTEP-KOR

출처 : OSTEP-KOR

장점 : 확장성이 좋고 캐시 친화성이 좋음

출처 : OSTEP-KOR, 워크로드 불균형

출처 : OSTEP-KOR, 워크로드 불균형

단점 : 워크로드 불균형에 문제가 있고 구현이 복잡하다.

 

❓ 작업 훔치기

이러한 워크로그 불균형 문제를 해결하기 위한 한가지 방법으로는 작업훔치기 (work stealing)이 있다.

출처 : OSTEP-KOR, 작업 훔치기

작업의 개수가 낮은 큐가 가끔 다른 큐의 훨씬 많으 수의 작업이 있는지 검사하고 워크로드 균형을 맞추기 위해 대상에서 하나 이상의 작업을 가져온다.

멀티 큐 스케줄링으리 가장 중요한 목적은 확장성인데,  큐를 너무 자주 검사하면 높은 오버헤드로 확장성 문제가 생긴다. 반면, 다른 큐를 자주 검사하지 않으면 심각한 워크로드 불균형을 초래할 가능성이 있다.

그래서 큐 검사의 적절한 값을 찾아내는 것은 매우 어렵다.