Is this a naive blocking queue?

265 Views Asked by At

Is the following a correct implementation of a blocking queue ?

Correct as in:

  1. Thread-safe, i.e., has the semantics of a queue in a multi thread scenario.
  2. If empty, blocks if trying to retrieve an element.
  3. If full (std::u8::MAX in this case), blocks if trying to add a new element.

From my static analysis, I would say it is safe from dead locks; but I know how tricky synchronization can be.

Is there anything obviously wrong with this implementation that would prevent me to use in production? (hypothetical scenario)
If this implementation is correct, what are the performance drawbacks compared to a proper BlockingQueue, and why?

Code

use std::collections::VecDeque;
use crate::Semaphore;
use std::sync::Mutex;

pub struct BlockingQueue<T> {
    non_empty_queue: Semaphore,
    bounded_queue: Semaphore,
    data: Mutex<VecDeque<T>>
}

impl<T> BlockingQueue<T> {
    pub fn poll(&self) -> T {
        self.non_empty_queue.decrement();
        let mut lock_guard = self.data.lock().expect("Unable to acquire lock ...");
        let result = lock_guard.pop_back().expect("Major flaw!");
        self.bounded_queue.increment();
        result
    }

    pub fn offer(&self, t: T) -> () {
        self.bounded_queue.decrement();
        let mut lock_guard = self.data.lock().expect("Unable to acquire lock ...");
        lock_guard.push_front(t);
        self.non_empty_queue.increment();
    }

    pub fn new() -> BlockingQueue<T> {
        BlockingQueue {
            non_empty_queue: Semaphore::new(0),
            bounded_queue: Semaphore::new(std::u8::MAX),
            data: Mutex::new(VecDeque::new())
        }
    }
}

Notes:

  1. The Semaphore is of my own creation. Lets just assume it is correctly implemented.
  2. bounded_queue attempts to prevent insertions beyond std::u8::MAX.
  3. non_empty_queue attemps to prevent "pops" when empty.
0

There are 0 best solutions below