Implementing a Wait-Free Queue in Go

Concurrent data structures are fundamental to modern software development, enabling multiple goroutines to access shared data safely. Traditional locking mechanisms, while effective, can lead to issues like deadlocks and priority inversion, where threads might wait indefinitely for resources. Wait-free algorithms, on the other hand, guarantee that every operation completes in a finite number of steps, regardless of the actions of other threads. This challenge will have you implement a basic wait-free queue in Go.

Problem Description

Your task is to implement a single-producer, single-consumer (SPSC) wait-free queue in Go. This queue should allow a single goroutine to enqueue elements and another single goroutine to dequeue elements, without any explicit locking. The core principle is to use atomic operations provided by Go's sync/atomic package to manage the queue's state, ensuring that operations are progress-guaranteed.

Key Requirements:

• Wait-Free Guarantee: Every Enqueue and Dequeue operation must complete in a bounded number of steps, irrespective of other concurrent operations.
• SPSC: The implementation should be optimized for a single producer and a single consumer.
• Atomic Operations: Utilize sync/atomic for all state modifications and reads that affect concurrency.
• Bounded Capacity: The queue should have a fixed, predefined capacity.
• Clear Return Values: Enqueue should indicate success or failure (e.g., if the queue is full). Dequeue should return the element and a boolean indicating if an element was successfully retrieved (e.g., if the queue was empty).

Expected Behavior:

• NewWaitFreeQueue(capacity int): Initializes a new wait-free queue with the given capacity.
• Enqueue(item interface{}) bool: Attempts to add an item to the queue. Returns true if successful, false if the queue is full.
• Dequeue() (interface{}, bool): Attempts to remove and return an item from the queue. Returns the item and true if successful, nil and false if the queue is empty.

Edge Cases:

• Enqueuing into a full queue.
• Dequeuing from an empty queue.
• Handling different data types (using interface{}).
• Queue with capacity 1.

Examples

Example 1:

package main

import "fmt"

func main() {
	q := NewWaitFreeQueue(3)

	fmt.Println(q.Enqueue(10)) // Output: true
	fmt.Println(q.Enqueue(20)) // Output: true
	fmt.Println(q.Enqueue(30)) // Output: true
	fmt.Println(q.Enqueue(40)) // Output: false (queue is full)

	item, ok := q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: 10, true

	item, ok = q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: 20, true

	fmt.Println(q.Enqueue(50)) // Output: true
	fmt.Println(q.Enqueue(60)) // Output: true

	item, ok = q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: 30, true

	item, ok = q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: 50, true

	item, ok = q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: 60, true

	item, ok = q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: <nil>, false (queue is empty)
}

Explanation: The producer adds elements until the queue is full. Then, elements are dequeued, and the producer continues to add. Finally, all elements are dequeued, resulting in an empty queue.

Example 2:

package main

import "fmt"

func main() {
	q := NewWaitFreeQueue(1)

	fmt.Println(q.Enqueue("hello")) // Output: true

	item, ok := q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: hello, true

	item, ok = q.Dequeue()
	fmt.Printf("%v, %v\n", item, ok) // Output: <nil>, false
}

Explanation: A queue with capacity 1 behaves as expected, holding one element at a time.

Constraints

• The queue capacity will be a positive integer between 1 and 1024 inclusive.
• The item passed to Enqueue can be of any Go type (interface{}).
• The implementation should be efficient, avoiding spin-locks or busy-waiting beyond what's inherent in atomic operations.

Notes

• Consider using a circular buffer approach for the underlying storage.
• You will likely need to manage head and tail indices atomically.
• The sync/atomic package provides functions like LoadUint64, StoreUint64, AddUint64, and CompareAndSwapUint64 which will be crucial.
• For a simple SPSC queue, you don't need to worry about multiple producers or consumers interfering with each other directly, but you still need to ensure atomicity of the head and tail updates to prevent race conditions even within the single producer/consumer model when operations might overlap or be reordered by the compiler/CPU.
• A common pattern for wait-free queues involves using sequence numbers or indices that are atomically updated. Think about how to signal that an element has been consumed or produced.