스레드 잠금 알고리즘2(필터 잠금, 램포트 잠금 알고리즘)

*용어 정리

lock 메서드 내부는 진입영역과 대기영역으로 나눌 수 있다.

진입영역(doorway): 유한한 단계로 되어 있다.(while문을 제외한 부분)

대기영역(waiting): 무한한 단계를 밟을 수도 있다.(while문 부분)

 

1. 필터 잠금 알고리즘

: Peterson 알고리즘은 스레드 2개에 대한 상호배제(mutual exclusion) 알고리즘-> 스레드 n개로 확장한 알고리즘

Peterson 알고리즘처럼 상호배제와 무기아조건을 만족한다.

Fig1. The FilterLock Algorithm

스레드 n개 존재 시

level[]: 길이 n인 배열로, level[i]는 i번 스레드의 현재 레벨을 기록한다.->이 배열은 0번 스레드부터 (n-1)번 스레드까지 각 스레드의 현재 시점의 레벨을 알려준다.

victim[]: 길이 n인 배열로, victim[i]는 i 레벨의 희생자 스레드 번호를 기록한다.(희생자 스레드란 가장 최근에 작업을 한 스레드이다)

->이 배열은 0번 레벨부터 (n-1)번 레벨까지 가장 최근에 각 레벨로 올라간  스레드번호를 알려준다.

 

 

로직: 레벨이 (n-1)개 존재한다. n개의 스레드는 모두 처음에 0레벨인데, 스레드들이 하나씩 작업 (공유객체를 수정하는 작업이라서 lock,unlock함수가 포함된 작업) 을 하려고 lock() 함수를 호출하면 for문의 첫번째 cycle을 돌면서 해당 스레드의 레벨이 1로 올라가게 된다. 이 때 while문이 중요한데, 다른 스레드 중에 레벨이 나(현재 스레드)의 레벨보다 높은 녀석이 있으면서 나의 레벨에서 가장 최근에 작업한 게 나라면(이 부분이 왜 꼭 필요한지 아직 잘 모르겠다) 대기상태에 들어간다. 

->해석: 만약 n개의 스레드가 모두 작업을 하고 싶어 하면 lock을 순차적으로 호출할 것이다. 처음에는 모두 0레벨에서 시작하고, (n-1)번 도는 for문을 하나씩 돌며 레벨이 하나씩 높아진다. 만약 m번 스레드가 0부터 1~(n-1)레벨을 거치며 for문을 다 돌게 되면 lock 함수가 끝나고 작업을 본격적으로 하게 된다.(임계구역 진입) 그 작업이 끝나면 m번 스레드의 레벨은 0으로 초기화되고, 다시 작업을 하고 싶다면 다른 스레드들과 경쟁하며 lock함수의 for문을 처음부터 다시 돌아야 한다.

 

=>임계구역에 진입하기 위한 이러한 과정들이 복잡해보이지만 실제로는 스레드들을 하나의 레벨 체계/규칙으로 관리하며 상호배제 원리 하에 순차적으로 작업하게 하는 스레드 관리 알고리즘이다.

 

핵심적인 로직 요약: 작업을 하고자 lock함수를 호출한 스레드들끼리 경쟁하여 1부터 (n-1)레벨까지 하나씩 레벨업을 하고, (n-1)레벨까지 도달한 스레드는 lock 함수가 종료되어 작업을 수행하고 unlock을 호출하며 작업을 종료한다. 이 때 lock 함수의 for문 속에 있는 while 문이 스레드들이 질서있게 대기하거나 레벨업하도록 기준을 제시한다. 레벨이 가장 높은 스레드가 while문을 통과해 lock을 먼저 종료하고 작업할 수 있을 것이다. 

 

한계점: while문을 보면, 다른 스레드들 중에  레벨이 현재 스레드보다 높은 스레드가 있으면 대기해야 하므로 배열을 탐색해야 하고 for루프를 돌기 때문에 lock함수를 호출한 스레드들이 임계영역(lock함수를 지나서 작업할 수 있는 영역)에 진입하기까지 시간이 오래 걸리고 비효율적일 수 있다. 

공정성의 측면에서도, 먼저 lock함수를 호출한 스레드가 먼저 임계영역에 도달할 것을 보장할 수 없다. 이는 필터잠금 알고리즘이 선입선처리(FCFS)방식을 따르지 않음을 의미한다. 

 

2. 램포트의 빵집 잠금 알고리즘

램포트 알고리즘은 상호배제와 무교착, 무기아조건을 만족하며 선입선처리(FCFS) 방식이다.

Fig2. Lamport's Bakery Algorithm

스레드 n개가 접근할 때

flag[]: flag[i]는 i번 스레드가 lock함수 진행 중에 있는지 여부를 true/false로 알려준다.

label[]: label[i]는 lock 함수를 실행한 i번 스레드가 가지고 있는 라벨링된 번호를 알려준다.(스레드들은 lock함수를 실행할 때 새 번호표를 뽑는다-라벨링)

 

lock 함수

-진입 영역: 현재 스레드의 id i에 대해 flag[i]값을 true로 설정하고(스레드가 작업을 하려고 진입 영역에 진입함.) 해당 스레드의 라벨 값을 얻는다.(번호표 뽑는다.) 

-대기 영역: 만약 다른 스레드 중에 (flag값이 true인 스레드가 있으며) 동시에 (그 스레드의 라벨 값이 현재 스레드의 라벨값보다 작거나 라벨값이 같다면 스레드 id값이 작은) 경우가 존재한다면 현재 스레드는 대기한다.

현재 스레드 외에 다른 스레드 중에 lock함수를 호출한 것이 없거나 더 우선적인 번호표를 뽑고 대기하고 있는 것이 없다면 현재 스레드는 while 루프를 탈출하고 작업을 수행(lock 함수 종료)한다. 

 

unlock 함수

현재 스레드의 작업이 끝나면 스레드 id i에 대해 flag[i]=0으로 설정하고 스레드 호출한 함수가 종료된다.

 

<->순차적 타임스탬프 알고리즘: scan&label 과정을 통해 스레드가 번호표를 뽑아서 선입선처리방식으로 연산이 된다는 점은 Lamport's 알고리즘과 유사하지만, 이 알고리즘은 앞의 잠금 알고리즘들과는 달리 concurrent(병렬) 연산이 아닌, sequential(순차적) 연산이다.

 

*wait-free알고리즘이라고, while문의 loop를 돌면서 대기상태에 계속 머물러 있는 시간을 예측 가능하도록 한정하는 알고리즘도 존재하지만 구현이 어렵다고 한다. 

 

정리

 Peterson 알고리즘이 스레드 2개에 대한 잠금 알고리즘이었다면 FilterLock 알고리즘은 이를 스레드 n개에 대한 잠금 알고리즘으로 확장시켰다. Lamport 알고리즘은 이에 추가적으로 선입선처리 방식을 포함하도록 발전했다.

 FilterLock은 n개의 레벨 내에 n개의 스레드를 위치시키고 for문과 while문을 이용해 스레드들을 관리하며 순차적으로 작업하도록 했다.

 Lamport는 번호표의 개념을 도입해 새롭게 함수를 실행한 스레드는 가장 큰 숫자의 번호표를 갖게 되어 먼저 lock을 호출한 스레드들 다음으로 작업하도록 했다.

 

그러나, 이 알고리즘들은 스레드의 수가 많아져 label의 크기가 매우 커진다면 label 필드가 오버플로우되어 0이 되고 선입선처리가 깨질 수도 있다. 또한 n개의 스레드가 병렬로 함께 수행되려고 하면 n개의 서로 다른 위치에 대해 지속적으로 읽기와 쓰기를 해야한다는 점이 실용적이지 않다. 그렇기에 다중프로세서 프로그램에서는 읽기-쓰기와는 다른 종류의 동기화연산을 사용해야 한다.