sjo200 - CS 대학원 수업 정리 블로그

2. Filter algorithm (for many threads, single core)

(쓰레드 개수=N) level[N]과 victim[N]을 갖는다. 한 쓰레드가 진입하고 싶으면 level 0부터 진입하고, N-1까지 진행한다. 여러 쓰레드가 특정 레벨에 존재할 수 있다. 어떤 쓰레드가 자신 level의 victim이 아니거나, 자신 외에 자신 이상의 레벨이 없으면 진행한다. Peterson's algorithm의 확장된 느낌이다.  하나의 쓰레드가 계속 진행되지 않을 수 있으므로 fairness가 부족한 것을 알 수 있다. 따라서 deadlock free 이다.

starvation free (deadlock free)

i = thread_id

for(L=0; L<N; L++)

  level[i] = L

  victim[L] = i;

  while(∃k != i; level[k] >= L && victim[L] == i);

    -critical section-

3. Bakery algorithm (for many threads, many cores)

(쓰레드 개수=N) flag[N]과 label[N]을 갖는다. 한 쓰레드가 진입하고 싶으면 flag[i]를 true로 만들고 번호를 읽어와 label[i]에 넣고, 자신의 차례가 올때까지 대기한다. 즉, 자신보다 빠른 순서의 쓰레드가 없을 때까지 기다린다. 오랫동안 사용할 경우, 32bit는 몇십년 내로 overflow가 발생한다. 64bit를 사용하면 반영구적으로 쓸 수 있다. 이렇듯, 영구적으로 사용하지 못하는 약점이 있다. 또한, label을 확인할 때마다 모든 쓰레드의 label을 한번에(atomic 하게) 확인해야 한다.

starvation free (deadlock free)

flag[i] = true;

label[i] = max(label[0], ..., label[N-1]) + 1;

while(∃k; flag[k] && (label[i], i) > (label[k], k));

4. Precedence Graph (for two/three threads, many cores)

-for two threads

쓰레드 A, B는 차례대로 0, 1 번을 뽑고 실행하게 된다. 다음 번호표는 2번을 뽑게 되고, 다음은 0번, 또 다음은 1번, ... 이렇게 영구적으로 사용할 수 있는 제한적인 bakery algorithm을 만들 수 있다.

     -for three threads

번호를 표시할때 12이면 1번 큰원의 작은 2를 말한다. 

예시 1) 쓰레드 A, B, C는 차례대로 00, 01, 10의 번호를 받는다. 

A가 일을 마쳐서 00이 없어지고, 다시 일이 생겨 새로 받으면 11을 받는다. B가 일을 마쳐서 01이 없어지고, 다시 일이 생겨 새로 받으면 21을 받는다.

예시 2) 쓰레드 A, B, C는 진행하다가 12, 21, 22의 번호를 갖게 되었다.

B가 일을 마쳐서 21이 없어지고, 다시 일이 생겨 새로 받으면 20을 받는다.

위와 같이, 두 쓰레드가 한 작은 원에 같이 돌 수 있고, 필요한 경우 다른 큰 원으로 옮겨가며 다른 이들이 갖고 있는 번호보다 늦은 순위의 번호를 받아야 한다.

영구적인 bakery algorithm 이지만, 모든 쓰레드의 위치를 파악하고 자신이 가야할 위치를 계산하고 옮기는 것을 atomic 하게 실행해야 하므로 시간이 오래 걸리며 공간복잡도 또한 non-linear하게 증가한다. 따라서 이론적으로 완벽할 뿐 실제로 쓰이지 않는다고 한다.

starvation free (deadlock free)