Understanding the Non-Blocking Michael Scott Queue

Slide Note

The Non-Blocking Michael Scott Queue, presented by Gurudatta Patil, is a thread-based data structure where threads help each other in managing a queue efficiently. Threads collaborate to add nodes at the tail and remove them from the head, ensuring smooth operation even in a non-empty queue scenario. The enqueue and dequeue processes involve utilizing Compare-and-Swap (CAS) operations to maintain the queue's integrity. Dive into this innovative queue design to explore its working principles and advantages.

valery Follow

Uploaded on Aug 31, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Non Blocking Michael Scott Queue Presented by : Gurudatta Patil 203050062

Michael and Scott Queue [1996] Threads help each other

Michael & Scott Queue Empty queue consist of head and tail pointers to a dummy node. Head Tail -

If nonempty, first node is still dummy. Enqueue adds at tail; dequeue removes at head. head tail - A(old) B(new)

Michel and Scott Queue : Enqueue 1) 2) CAS next pointer of tail node to new node. Use CAS to swing tail pointer. Head Tail - A

Michel and Scott Queue : Enqueue 1) 2) CAS next pointer of tail node to new node. Use CAS to swing tail pointer (any thread can help) Head Tail - A

Michael & Scott queue : dequeue head tail - A(old) Z(New) 1) 2) Read data in dummy s next node CAS head pointer to dummy s next node.

Michael & Scott queue : dequeue head tail - Z(New) 3) Discard old dummy node. 4) Node from which we read is new dummy.

void put (E item) { Node<E> newnode = new Node<>(item, null); Boolean success; do{ Node<E>curTail = tail.get(); Success = curTail.next.CAS(null,newnode); head tail tail.CAS(curTail , curTail.next.get()); } while (!success); } curTail newNode dummy 1 2 item

void put (E item) { Node<E> newnode = new Node<>(item, null); Boolean success; do{ Node<E>curTail = tail.get(); Success = curTail.next.CAS(null,newnode); //true head tail tail.CAS(curTail , curTail.next.get()); //true } while (!success); } curTail newNode dummy 1 2 item

void put (E item) { Node<E> newnode = new Node<>(item, null); Boolean success; do{ Node<E>curTail = tail.get(); Success = curTail.next.CAS(null,newnode); //true head tail tail.CAS(curTail , curTail.next.get()); //false } while (!success); } CurTail newNode dummy 1 2 item

void put (E item) { Node<E> newnode = new Node<>(item, null); Boolean success; do{ Node<E>curTail = tail.get(); another Success = curTail.next.CAS(null,newnode); //False head tail tail.CAS(curTail , curTail.next.get()); //False } while (!success); } CurTail newNode dummy 1 2 item

void put (E item) { Node<E> newnode = new Node<>(item, null); Boolean success; do{ Node<E>curTail = tail.get(); another Success = curTail.next.CAS(null,newnode); //False head tail tail.CAS(curTail , curTail.next.get()); //True } while (!success); } CurTail newNode dummy 1 2 item

Synchronization Blocking Non-Blocking Lock based CAS based Lock + Unlock CAS loop Invarient : before & After Semi-Invarient

Public void put(E item) { Node<E> newNode = new Node<>(item, null); While (true) { Node<E> currentTail = tail.get(); Node<E> tailNext = currenttail.next.get(); if(currentTail == tail.get() { If (tailNext != null) { tail.compareAndset(currentTail, tailNext); } else{ If (currentTail.next.compareAndset(null, newNode)) { tail.compareAndset(currentTail,newNode); Return; }}}}}