Difference between queue and mailbox

Hi All,

I have attended lot of interviews one moth back. All the interviewers asked this question. But I don't know the exact answer.

If any one knows please reply back.


Thanks and Regards,
Karalamoorthy

One difference i know is like in mailbox we can suspend the operation using get() , put() in mailboxes. that is why it is very efficient in using for communication between two threads

Mailboxes are implemented with a combination of queues and semaphores.

The key feature of a mailbox is that it guarantees a test of the size of the queue with a push and pop of data as an atomic operation. That means if multiple threads are blocked waiting to push data onto a full queue using the mailbox put() method, as soon as space becomes available for a single piece of data, only thread will see that space is available and be allowed to push data onto the queue. Without that atomic guarantee, another thread could push data onto the queue in the time that your thread checked the size of the queue and pushed data onto the queue.

Similar for the get() method, if more than one thread is trying to pop data off the queue, only one thread will see that there is data queue and pop the data off the queue, the other threads will wait their turn in FIFO order.

If there is only one thread doing put()s and only one other thread doing gets() to a mailbox, you really don't need the extra overhead of a mailbox, but it is convenient to use the put() and get() methods of a mailbox that combine the test and set operations on the queue.

dave_59 said:

Mailboxes are implemented with a combination of queues and semaphores.

The key feature of a mailbox is that it guarantees a test of the size of the queue with a push and pop of data as an atomic operation. That means if multiple threads are blocked waiting to push data onto a full queue using the mailbox put() method, as soon as space becomes available for a single piece of data, only thread will see that space is available and be allowed to push data onto the queue. Without that atomic guarantee, another thread could push data onto the queue in the time that your thread checked the size of the queue and pushed data onto the queue.

Similar for the get() method, if more than one thread is trying to pop data off the queue, only one thread will see that there is data queue and pop the data off the queue, the other threads will wait their turn in FIFO order.

If there is only one thread doing put()s and only one other thread doing gets() to a mailbox, you really don't need the extra overhead of a mailbox, but it is convenient to use the put() and get() methods of a mailbox that combine the test and set operations on the queue.

Click to expand...

Hi Dave,

I am not able to completely understand what you told about atomic operation. If more than one thread is waiting to push on malibox, whenever mailbox will have space any of the thread can put items in mailbox. Which will be similar situation as queue.

As well if many thread has been blocked execution for getting data, whenever mailbox will get data any of the thread can get data and start executing the code.


Can you explain in more descriptive manner.

For semaphores and mailboxes, we typically refer to the test and set operations as being atomic -- uninterruptible. A put() has to test that there is space, then pushes onto an internal queue. A get() has to test there there is something in the internal queue, then pop() off the internal queue. If a user tries to do this using a simple queue, they have to break these operations into separate statements:

There are two problems with this code when there are multiple threads doing a put(), or multiple threads doing a get().

The first is that when there are multiple threads waiting on the size of the queue to change, there is no guaranteed ordering which thread will wake up and proceed when the condition is satisfied. Mailboxes/semaphores guarantee that the order that the threads suspend is the same as the order they wake up (FIFO order First In/First Out).

The other problem is there is no guaranteed ordering of statements between two or more concurrently running threads. It's possible for multiple threads to wake up when the queue size changes so that either q.size < MAXSIZE is true for a put(), or q.size > 0 for a get(). All the threads could execute the test and succeed, then all the threads do their set operation when only one operation should have been allowed. Mailboxes/semaphores guarantee that put() and get() act atomically so that no other thread interrupt the test and set operation. So only one thread will succeed in the put() or get().