1. mutex 알고리즘의 특징
앞서 4가지 mutex 알고리즘을 소개했다. 어떤 알고리즘의 progress condition에 따라 어떤 특성이 있다고 말할 수 있다. 직역하면 다음과 같다.
deadlock-free: 몇 쓰레드가 결국 lock을 얻는다. (blocking)
starvation-free: 모든 쓰레드가 결국 lock을 얻는다. (blocking)
lock-free: 몇 쓰레드가 호출한 method에 대해 return 받는다. (non-blocking)
wait-free: 모든 쓰레드가 호출한 method에 대해 return 받는다. (non-blocking)
수업에 따르면, wait-free는 모든 쓰레드가 다같이 몇 스텝씩 진행하는 것이고, deadlock-free는 몇 쓰레드가 먼저 진행하고 다른 쓰레드들이 진행하는 것이라고 하는데 정확한 설명이 없다...
※ bounded waiting, safety와 liveness
bounded waiting 또한 하나의 특성인데, r-bounded waiting이라고 하면 어떤 쓰레드가 자신을 r번 지나쳐서 먼저 실행할 수 있다는 것이다. peterson's algorithm은 r==1이고, filter algorithm은 r이 존재하지 않는다.
safety: bad never happens (mutex)
liveness: sometimes good happens (no deadlock?? 수업시간에 들었는데 맞나...)
2. MRSW/MRMW
MRSW는 multi-reader single-writer이고, MRMW는 multi-reader multi-writer이다.
각 알고리즘에 필요한 MRSW/MRMW register는 다음과 같다.
Peterson's algorithm: 2 MRSW(flag[2]), 2 MRSW(victim[2])
filter algorithm: N MRSW(flag[N]), N MRMW(victim[N])
bakery algorithm: N MRSW(flag[N]), N MRSW(label[N])
register가 MRSW/MRMW를 허용하지 않으면, 매번 메모리까지 오고가며 캐시에 update를 해야하므로 시간이 상당히 많이 걸리게 된다. 따라서 앞서 소개한 algorithm들은 위 공용 레지스터들이 필요하다.
3. mutual exclusion을 해결하기 위해서는 N개 이상의 MRSW 또는 MRMW가 필요하다.
수업시간에 증명하는 것인데, 자신이 critical section에 들어감을 표시하는 곳이 각자 있고, 어떤 한 쓰레드만 그런곳이 없을때를 생각한다. critical section에 들어갔는데 그 한 쓰레드가 들어가서 표시를 안했을때 다른 쓰레드가 같이 critical section에 들어갈 수 있음을 보이면 된다.
4. mutual exclusion을 해결하기 위해서는 2N개 이하의 MRSW가 있어도 된다.
왜냐하면 bakery algorithm이 2N MRSW로 구현할 수 있기 때문이다.
'분산시스템 (멀티코어 contention) - 수업' 카테고리의 다른 글
universality of consensus (0) | 2017.05.22 |
---|---|
consensus (0) | 2017.04.12 |
linearizability / sequential consistency (1) | 2017.04.12 |
from safe register to atomic register (0) | 2017.04.12 |
mutual exclusion (0) | 2017.04.12 |