priority queue (for concurrent)

1. 개념

 array-based PQ, Tree-based PQ, Heap-based PQ, Skip-list-based PQ가 있다. removeMin, add를 할 수 있는 structure를 만들 것이다.

2. array-based PQ

 그냥 array에 priority 값을 index로 사용하고, removeMin을 하면 0부터 차례대로 읽어나가는 것이다. 예상 가능한 문제점들이 있다. 쉬우니까 생략한다.

3. tree-based PQ

 priority 값을 index로 사용하는데, 그 위로 모든 노드 값이 0인 binary tree가 있다고 생각하자. add를 하면 root까지 올라가야 하는데, 올라갈때 오른쪽으로 올라간다면 그 부모노드에게 ++, 왼쪽으로 가면 그대로 둔다. removeMin을 하면 root에서 1 이상이면 -- 후 왼쪽으로 이동, 아니면 오른쪽으로 이동한다. 각 operation별의 concurrency는 있겠지만, 둘이 동시에 실행하면 add가 채 끝나기 전에 removeMin에게 overtaken 될 수 있다. 무슨 말이냐면, 다른 노드에 의해 자신까지 올 수 있는 길이 생길 수 있다는 것인데, 총 8개의 노드(1~8)가 있을 때, 3, 4에 add 하고, 3을 담당한 쓰레드가 heap 상의 인덱스 1에서 멈추고, 4를 담당한 쓰레드는 완료했다고 치자. 그리고 removeMin 하면 3이 overtaken 된다.

4. Heap-based PQ

 이건 add, removeMin 둘다 자식노드와 부모노드를 lock하는데, 부모노드부터 lock한다. removeMin은 예상할 수 있듯이, 셋을 lock하여 어디로 내려갈지 정하는 것이고, add는 둘을 lock 하여 올라간다. add할때는 node의 상태를 busy로 바꿔서 parent가 busy면 아닐때까지 lock을 잠그려고 시도하고 풀고 반복하면서 spin lock하고, parent는 lock을 잡은 채로 큰 자식노드와 부모노드를 바꾸고 그곳으로 내려간다. 즉 removeMin은 add에 상관없이 쭉쭉 내려가고, add는 서로 순서가 바뀌지 않게 조심해서 올라간다. add가 보던게 removeMin에 의해서 올라갈 수 있기 때문에, 자신의 id가 node에 없다면 그냥 올라간다. 따라서 concurrency가 있으므로 linearizable 하다.

5. skip-list-based PQ (lazy skip-list)

 linearizable 하지 않지만, 앞에서 배웠듯이 quiescent consistency를 만들어낼 수 있다. 그리고 heap-based PQ를 성능에서 압도한다. 그냥 removeMin은 skip-list에서 첫 번째 원소를 빼는 것이고, add는 추가하는 것이다. 물론, lazy skip-list에서 발생한 문제는 또 일어날 것이고, 그렇기 때문에 말했듯이 constraint로 quiescent consistency를 만들어내야 한다.