Multiprocessor Scheduling

Multiprocessor Scheduling

1. multicore: 다수의 cpu코어가 하나의 single chip에 내장

cpu가 증가한다고 더 빨라지는 것은 아니다. thread를 이용해 병렬로 동작하게 해야함

 

2. 

Cache(SRAM)	Main Memory(DRAM)
-정적으로 동작 -메인메모리에서 자주 사용되는 데이터의 복사본을 저장 -전원을 공급되고 있는 한 내용을 저장 -접근속도가 빠르지만 가격이 비싸고 집적도가 낮아서 대량제작이 어렵고 구조가 복잡 -시간 지역성: 데이터에 한번 접근하면 가까운 시일내에 똑같은 데이터를 다시 접근하기 쉬움 -공간 지역성: 특정 X주소에 접근했을 때 주변 데이터를 접근하게 쉬움 -실제 느린 메모리를 빠르게 보이게끔 만들어줌	-데이터들을 저장 -캐시메모리에 비해 접근속도가 느리지만 -가격이 저렴 -집적도가 높아서 대용량제작 쉬움

3. 캐시 일관성(Cache coherence)문제 해결

Bus snooping

메모리 업데이트에 대해 해당 버스를 주시

cpu가 data 업데이트를 목격하게 되면 기존 캐시 데이터를 무효화시키던지 update

 

synchronization 개념을 적용

mutual exclusion을 적용함으로써 정확도를 보장 

보호해야하는 부분을 lock() 을 해줌->가실행 

cpu의 갯수가 증가할 수록 동기화된 자료구조에 접근하는게 느려짐 연산속도가 느려질 수 있다.

 

4. 캐시 친화성(Cache Affinity)

cpu를 재할당할 때 같은 cpu를 할당하자.

cache에는 최근 접근했던 데이터를 저장, 같은 프로세스를 다시 재할당하면 캐시가 저장된 데이터를 가지고 있기 때문에 빠르게 실행할 수 있음

 

5.SQMS(single que multiprocessor scheduling)

-단일 큐 

-각각의 cpu가다음 job을 pick

-locking을 하면 성능저하-> 확장성이 결여된 단점

-캐시 친화성이 없는 알고리즘 => 하나의 프로세스가 동일한 cpu에서 동작하게 하자는게 캐시 친화성인데 a가 cpu0, cpu1...

=> 캐시친화성을 부여: cpu0에서만 실행 a, e만 서로다른 cpu로 이동 =>단일큐로 하면 복잡하게 됨

-장점은 구현이 간단하지만 단점은 확장성이 좋지않고 캐시친화성 문제

 

6.MQMS

-다수의 큐로 구성

-각각의 큐 내부에 scheduling방식 적용

-job이 system에 들어왔을 대 하나의 큐에만 놓여짐

-큐를 분리해서 동작함으로써 동기화, 정보 공유같은 문제를 방지

-확장성 측면이나 캐시친화성 측면에서 장점

 

7. MQMS 문제점

Load Imbalance 로드 불균형 문제 해결방법

1) Migration 이주

2) switching 

 

8. work stealing

큐에서 job을 이동시킬 때 work stealing방식을 적용

source 큐는 작업량이 적음

target queue의 일이 더 많으면 작업을 스틸 

단점: overhead, 확장성 측면에서 문제

 

9. Linux Multiprocessor Schedulers

1)time-sharing withe time slice

시분할 방식으로 동작 가능

time slice를 가진것만 실행 

time interrupt가 발생할 때 마다 time slice값을 줄임

time slice=0이 되면 다른 프로세스가 선택됨

모든 프로세스가 time slice=0이 되면 time slice를 다시 재할당

 

2) real-time withe priority

140단계 우선순위가 있다

더 높은 우선순위 먼저 실행

lower the value, the higher priority

=> time slice를 가지면서 우선순위가 높은 프로세스부터 스케쥴링하게 됨

 

10. Linux Multiprocessor Schedulers 종류

1) O(1) scheduler

입력크기에 관계없이 일정시간에 동작

우선순위가 높은것을 선택, 설정된 시간내에 동작, 

설정된 시간이 프로세스 수랑 관계없이 설정=> o(1)

0~99 실시간 프로세스

100~139 비실시간 프로세스

비실시간 프로세스는 time slice를 받을 대 우선순위에 따라 다른값을 받게 됨

active arry- 시간이 남을 프로세스 집합

expired arry - 시간이 모두 소진

active array가 비면 두 array 교환

 

2)CFS(complete fair scheduling) scheduler

가중치에근거해서 sclie 

1나면 1.25차이가 나도록 time slice

5가 나면 3배가 나도록

 

11. 알고리즘 평가

1) deterministic modeling

gantt chart=> simple, fast, 알고리즘 설명이나 예시 제공 시 유용하게 사용

2) implementation 구현 : 어려움 존재

3) simulation

program model

number generation : unifor, exponential등 방식 적요

expensive: 시간 많이 소요, 저장공간 많이 듦

4)queueing model

수학적 모델, arrival rate, service rate값을 통해 도출가능, 제한된 조건에서만 평가가능