The Non-Blocking Michael Scott Queue

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.

• Queue Management
• Non-Blocking Data Structure
• Thread Collaboration
• CAS Operations
• Efficient Queue Handling

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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

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.

Presentation Transcript

1. Non Blocking Michael Scott Queue Presented by : Gurudatta Patil 203050062

2. Michael and Scott Queue [1996] Threads help each other

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

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

5. 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

6. 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

7. 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.

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

9. 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

10. 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

11. 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

12. 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

13. 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

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

15. 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; }}}}}

16. Summary Based on CAS-like operations Use CAS-loop pattern Threads help one another

17. Thank You !