What is difference between Mailbox and Queue.

It is very common question asked in interview.

Apparently there is not difference between queue and mailbox. Both can store data (push or put) and we can get stored data from is (pop and get.)

Difference lies when there is multiple thread (or process), putting or getting element to or from queue. For a single thread or process there is no difference between queue and mailbox.

I will show you with example below, how it affects.

Mailbox is special class (enhanced functionality of queue) in std package of system verilog. It can be bounded or unbounded. Bounded means size of mailbox is fixed, you can not put more element more than its defined size.

mailbox mbx = new(4);

Above mailbox can only store 4 element. If we try to put more element then 4 it will block the method until space is created.

Bounded Queue : Can we make that??? Yes we can mimic it as below.

task put(input int data);
  wait(q.size < 4); // test
  q.push_back(data); // set
endtask
task get(output int data);
 wait(q.size > 0); // test
  q.pop_front(data); // set 

endtask

Here we only push element if size is less than 4. If it is single thread doing this there is no difference (except we have to add wait statement).

But what mailbox is provide is : above test and set operation are performed atomically (uninterrupted). While for queue it is two different process. (test and set).

There are two problem using that queue approach.

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

2. 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 < 4 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().