Cache Affinity / job의 실행 시간 예측

멀티 프로세스 멀티 코어

프로세서: 칩, 소켓

멀티 코어: 한 프로세서에 여러 개의 코어

멀티 프로세서: 여러 개의 프로세서

모던 컴퓨터는 멀티코어..

이제 많아서 매니 코어라고도 하는데, 하이퍼스레딩까지

 

문제.

패럴랠 프로드램, 병렬 처리.. 어떻게 스케줄링 할 것인가(로드 밸런싱)

 

캐시: 작고 빠른 메모리. L1, L2, LLC..

지역성(로컬리티) : 특정한 데이터가 많이 사용된다

시간적 지역성: 최근에 사용한 데이터를 많이 사용함 (반복문, 스택)

공간적 지역성: 어떤 데이터를 쓰면 그 주변 데이터도 많이 씀 (배열)

-> 프로그램이 가지는 내재적 특성, 이걸 스케줄링 시 활용

 

CPU는 가능하면 메모리로 안내려가고 캐시에서 데이터를 가져오는게 좋음(캐시 히트)

그래서 라이트할 때도 지연 쓰기를 할 정도

 

캐시 어피니티 (캐시 친화도)

기존에 접근했던 데이터가 캐시나 TLB(Translation Loakaside Buffer, 가상 메모리 주소 물리 주소로 변환할 때 쓰는 캐시)에 남아있을 수 있음. -> 스케줄링 될 때 기존에 실행되었던 CPU에서 다시 수행되는 것이 좋음

 

SQMS (Single Queue Multiprocessor Scheduling)

프로세서는 여러 개인데 큐 하나 쓰기

장점: 단순함

단점: 캐시 어피니티 신경 못씀, 확장성(큐가 공유라 락해줘야 해서 줄이 길어지고 느려짐)

 

MQMS (Multi Queue Multiprocessor Scheduling)

장점: 캐시 어피니티, 락할 상황 줄어듦

단점: 로드 밸런싱 필요(migration, work stealing)

 

O(1) 스케줄러: 멀티 큐 방식, MLFQ 방식과 비슷

CFS (Complete Fare Share) 스케줄러: 멀티 큐, Stride 스케줄링과 비슷

BF 스케줄러: 싱글 큐, 프로포셔널 쉐어.. 현재 진행 중

---

정책의 비교

- 애널리틱 모델 (강의)

- Queuing Theory (확률이 등장)

- 시뮬레이션

- 구현 (가장 정확한데 오래 걸림)

 

시뮬레이션은 수학적인 것보다 리얼하고 구현보다 만들기 편함

---

시뮬레이션 할 때 보통 잡의 실행 시간을 같이 주는데, 이걸 어떻게 아나

1. 사용자가 알려줌 (인스트럭션 개수. CPU 속도 등을 통해)

2. 예측

 

Expotential Moving Average

과거를 보고 작업의 미래를 예측

예측 시간과 실제 시간에 알파(가중치)와 1 - 알파를 곱해서 더함 = 다음 예측 시간

예) 알파 = 0.5, 첫 CPU Burst : 6 / 예측 CPU Burst : 10 -> 다음 예측 CPu Bursr : 8