While completing a screen for a Software Development Engineer in Test (SDTE) position for Microsoft I had to implement a thread safe circular queue.
Implement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe. A really good observation was: Please do not to use existing class libraries for this question. Thanks!
My first attempt was obviously get more information about a circular queue and bring it back to my mind. That's because I had studied it a long time ago when I was in the beginning of the computer engineering course. If you don't use it you forget it. That's the truth.
This post aims to present an implementation of a thread safe circular queue in C#. I won't deal with theory. For theory, I advise you to read the Wikipedia article about circular queue (buffer) to get started.
I reused some code from the links I present in the references section at the end of this post.
I'll break down the code I implemented so that you can go through the functions that were asked in the problem statement.
class ThreadSafeCircularQueue { private int[] queue; private int head; private int tail; private int length; static Object thisLock = new Object(); public CircularQueue() { Initialize(); } ... }
The class ThreadSafeCircularQueue has five properties: an integer array (the queue) and the queue's head, tail and length. A static object thisLock is used to make the queue thread safe.
private void Initialize() { head = tail = -1; Console.Write("Circular Queue size: "); string length = Console.ReadLine(); this.length = int.Parse(length); queue = new int[this.length]; }
The function Initialize() does what its name means. The queue's head and tail are set to appropriate values and the user has the opportunity of specifying the queue's size (length) by entering an integer value. A new queue is then created and has the user specified size.
The Enqueue() and Dequeue() functions shown bellow do the hard work, that is, they control all the circular queue functionality.
The Enqueue() function receives an integer value to be enqueued. Note the use of the thisLock variable. It is used so that we get thread safety, that is, all the code section inside the lock statement can't be executed by two threads at the same time. This avoids the problem of two concurrent threads trying to access the queue data structure simultaneously. If it's not controlled in the source code level we can get invalid values in the queue what could lend to a corrupted queue. That's not what is expected. When the code section that is inside the lock statement is being executed by a thread and other thread reaches the same section of code, this second thread waits till the first thread exits such code section. This way the queue has a valid set of values and its data is maintained secure.
Firstly is checked if the queue is full. It is full when it's head points to index 0 and its tail points to length - 1 or when its tail + 1 equals the same value of head. Remember that it is a circular queue.
In case the queue is full a message is shown to the user. If it still has room we check if the "end" of the queue (tail) that points to the last element has an index of length minus 1. If it is then the tail will now point to the the "start" of the queue. The other possibility is to increment the tail variable. The position referenced by the tail variable is then used to enqueue the value parameter into the queue. Then the just enqueued value is printed in the screen. A check is done to verify if the head variable has a value of -1. If it's the case then head will point to index 0.
private void Enqueue(int value) { lock(thisLock) { if((head == 0 && tail == length - 1) (tail + 1 == head)) { Console.WriteLine("Circular queue is full."); return; } else { if(tail == length - 1) tail = 0; else tail++; queue[tail] = value; Console.WriteLine("In -> {0}", value); } if(head == -1) head = 0; } }
The Dequeue() function also uses the lock statement because it must be a thread safe function.
Firstly is checked if the queue's head points to -1. Remember that in the Initialize() function when the queue is initialized its head and tail variables are set to -1. If head has a value of -1 then the queue is empty and the user is informed about that. A value of -1 is returned to conform with the function signature that needs to return an integer value.
If the queue is not empty the integer variable v receives the value that is indexed in the queue's head position. The value 0 is then assigned to the position that was just dequeued.
Now it's necessary to update the head position inside the queue. To accomplish that it's checked if head is equal tail, if it is, then head = tail = -1. This last operation states that the queue is empty after the dequeue operation. Else it's checked if head is equal length - 1. If it is the case then head receives 0. The last possible condition increments the value of head. In the end the value being dequeued (v) is printed in the screen.
Printing the values in the screen is a good way of keeping track of what is going on while the program is running.
private void Dequeue() { lock(thisLock) { int value; if(head == -1) { Console.WriteLine("Circular queue is empty."); value = -1; } else { value = queue[head]; queue[head] = 0; if(head == tail) head = tail = -1; else if(head == length - 1) head = 0; else head++; } Console.WriteLine("Out -> {0}", value); } }
Now take a look at the Show() function bellow. Again the lock is present. Why? In an instant you'll get to the point. Hold your horses! :-)
A check is done to verify if the queue is empty. If it is the case the callee function just returns to the caller function. If it is not the case we proceed to show the values already present in the queue. If tail is less than head a for loop starting in 0 and ending in length - 1 iterates the queue and each value is written in the screen. Otherwise a for loop starting in 0 end ending in tail iterates the queue and each value is written in the screen.
private void Show() { lock(thisLock) { int i; if(head == -1) { Console.WriteLine("Circular queue is empty."); return; } else { if(tail < head) { //for(i = head; i <= size - 1; i++) for(i = 0; i <= length - 1; i++) Console.Write("{0} ", queue[i]); } else //for(i = head; i <= tail; i++) for(i = 0; i <= tail; i++) Console.Write("{0} ", queue[i]); Console.WriteLine(); } } }
The following is the EnqueueDequeue() function responsible for calling the Queue(), Dequeue() and Show() functions. In this function I execute a simple test case and comment the operations being carried out.
public void EnqueueDequeue() { Enqueue(1); Enqueue(2); Enqueue(3); Enqueue(4); Show(); Enqueue(5); // Circular queue is full! Dequeue(); Dequeue(); Dequeue(); Dequeue(); Dequeue(); // Circular queue is empty! Dequeue(); // Circular queue is empty! Show(); Enqueue(6); Show(); Enqueue(7); Show(); Dequeue(); Dequeue(); Enqueue(8); Enqueue(9); Show(); // Supposing a 4 size queue: 0 ¦ 0 ¦ 0 ¦ 0 // // 1 ¦ 0 ¦ 0 ¦ 0 <- Enqueue 1 // // 1 ¦ 2 ¦ 0 ¦ 0 <- Enqueue 2 // // 1 ¦ 2 ¦ 3 ¦ 0 <- Enqueue 3 // // 1 ¦ 2 ¦ 3 ¦ 4 <- Enqueue 4 // // 1 ¦ 2 ¦ 3 ¦ 4 <- Circular queue is full when trying to enqueue 5. // // 0 ¦ 2 ¦ 3 ¦ 4 <- Dequeue 1 // // 0 ¦ 0 ¦ 3 ¦ 4 <- Dequeue 2 // // 0 ¦ 0 ¦ 0 ¦ 4 <- Dequeue 3 // // 0 ¦ 0 ¦ 0 ¦ 0 <- Dequeue 4 // // 0 ¦ 0 ¦ 0 ¦ 0 <- Circular queue is empty when trying to dequeue. // // 0 ¦ 0 ¦ 0 ¦ 0 <- Circular queue is empty when trying to dequeue. // // 6 ¦ 0 ¦ 0 ¦ 0 <- Enqueue 6 // // 6 ¦ 7 ¦ 0 ¦ 0 <- Enqueue 7 // // 0 ¦ 7 ¦ 0 ¦ 0 <- Dequeue 6 // // 0 ¦ 0 ¦ 0 ¦ 0 <- Dequeue 7 // // 8 ¦ 0 ¦ 0 ¦ 0 <- Enqueue 8 // // 8 ¦ 9 ¦ 0 ¦ 0 <- Enqueue 9 // // * 0 is set in a position when dequeueing so that it's easier to watch the queue variable. }
Now the main start thread:
class Program { static void Main(string[] args) { ThreadSafeCircularQueue circularQueue = new ThreadSafeCircularQueue(); Thread[] threads = new Thread[10]; for(int i = 0; i < threads.Length; i++) { threads[i] = new Thread(new ThreadStart(circularQueue.EnqueueDequeue)); } for(int i = 0; i < threads.Length; i++) { threads[i].Start(); } Console.ReadLine(); } }
As you can see above I declare an object of type ThreadSafeCircularQueue. An array of 10 objects of type Thread is then created. In a for loop I instantiate each Thread passing to it a delegate that represents the method that'll be invoked when the thread begins executing.
In the subsequent for loop I call the Start() method of each thread and they start executing simultaneously, tough they won't concur when accessing the functions Enqueue(), Dequeue() and Show().
Visual Studio C# Console Application
You can get the Microsoft Visual Studio Project and the app executable at: http://leniel.googlepages.com/ThreadSafeCircularQueueCSharp.zip
References
During the research phase of this implementation I recurred to some sites to get more information regarding the circular queue data structure. The following list can provide you a better understanding of such a data structure.
Thread Safety articles
[1] Venners, Bill. Designing for Thread Safety: Using Synchronization, Immutable Objects, and Thread-Safe Wrappers. 1998. Available at <http://www.artima.com/designtechniques/threadsafety.html>. Accessed on April 29, 2008.
[2] Suess, Michael. A Short Guide to Mastering Thread-Safety. 2006. Available at <http://www.thinkingparallel.com/2006/10/15/a-short-guide-to-mastering-thread-safety/>. Accessed on April 29, 2008.
[3] Allen, K. Scott. Statics & Thread Safety: Part II. 2004. Available at <http://www.odetocode.com/Articles/314.aspx>. Accessed on April 29, 2008.
Circular Queue sample code
[4] Kumar, Nunna Santhosh. Circular Queue Implementation using Arrays in C++. Available at <http://www.sourcecodesworld.com/source/show.asp?ScriptID=887>. Accessed on April 29, 2008.
Thread material
[5] Albahari, Joseph. Threading in C#. 2007. Available at <http://www.albahari.com/threading/>. Accessed on April 29, 2008.
