Concurrent Work Stealing with Go

Work stealing is a powerful technique for load balancing in concurrent systems. It allows worker threads to dynamically acquire tasks from other threads when they become idle, ensuring efficient utilization of all available cores. This challenge asks you to implement a basic work-stealing queue in Go to facilitate this pattern.

Problem Description

You are tasked with implementing a work-stealing queue in Go. The queue should support two primary operations: push (adding work to the tail of the queue) and pop (attempting to retrieve work from the head of the queue). If the head is empty, the pop operation should attempt to "steal" work from the tail of another queue. The queue should be thread-safe, allowing multiple goroutines to concurrently push and pop work items. The work items are represented by simple integers.

Key Requirements:

• Thread-Safe: The queue must be safe for concurrent access from multiple goroutines.
• Push Operation: Adds a work item to the tail of the queue.
• Pop Operation: Attempts to retrieve a work item from the head of the queue. If the head is empty, it attempts to steal from the tail of another queue. If both the head and stealing attempts fail, it returns an error.
• Work Stealing: If the queue is empty, the pop operation should attempt to steal a work item from the tail of another queue. For simplicity, assume there's only one other queue to steal from.
• Error Handling: The pop operation should return an error if no work is available (both head and stealing fail).

Expected Behavior:

• Multiple goroutines can concurrently push work items onto the queue.
• Multiple goroutines can concurrently pop work items from the queue.
• Work stealing should occur when a pop operation finds an empty queue.
• The queue should maintain a reasonable level of fairness (though strict fairness is not required).
• The pop operation should return an error if no work is available after attempting to steal.

Edge Cases to Consider:

• Empty queue: What happens when a pop operation is called on an empty queue?
• Concurrent pushes and pops: How does the queue handle multiple goroutines pushing and popping simultaneously?
• Stealing from an empty queue: What happens if the queue being stolen from is also empty?
• Multiple queues: While the problem simplifies to one other queue for stealing, consider how the concept would scale.

Examples

Example 1:

Input:
Queue: Empty
Goroutine 1: pop()
Output: Error: No work available
Explanation: The queue is empty, and there's no other queue to steal from.

Example 2:

Input:
Queue 1: [1, 2, 3]
Queue 2: [4, 5]
Goroutine 1: pop() from Queue 1
Output: 1
Explanation: The head of Queue 1 is 1, so it's popped.

Example 3:

Input:
Queue 1: []
Queue 2: [4, 5]
Goroutine 1: pop() from Queue 1
Output: 5
Explanation: Queue 1 is empty. The pop operation attempts to steal from Queue 2's tail, successfully retrieving 5.

Example 4:

Input:
Queue 1: []
Queue 2: []
Goroutine 1: pop() from Queue 1
Output: Error: No work available
Explanation: Queue 1 is empty, and Queue 2 is also empty. Stealing fails.

Constraints

• The work items are represented as integers.
• The queue should be implemented using Go's built-in concurrency primitives (e.g., mutexes, channels).
• The maximum number of work items in a queue should not exceed 1000.
• The performance should be reasonable for a basic implementation; highly optimized performance is not the primary goal.
• Assume only one other queue exists for stealing purposes.

Notes

• Consider using a mutex to protect the queue's internal state.
• Channels can be used to communicate between the push and pop operations.
• Think about how to handle the case where the stealing queue is also empty.
• The stealing operation should be non-blocking; it should return quickly if it cannot steal any work.
• Focus on correctness and thread safety first, then consider performance optimizations.
• You don't need to implement a full work-pool system; just the work-stealing queue itself.