CareerCup

Use 2 counting and 1 binary semaphore;
counting : full, empty
binary : lock
normal queue operation : enqueue, dequeue
initialize full=0 , empty=MAX_SIZE_ARRAY, s=1

void threadSafeEnqueue( int i)
{
  wait(empty);//checks whether there is empty slot available
  wait(lock);//aquire a lock for queuing
  enqueue(i);
  signal(lock);//release lock so other canperfor their operations
  signal(full);//since one element is inserted full will be incremented
}

int threadSafeDequeue()
{
  wait(full);//checks whether there is atleast one element in array else wait
  wait(lock);//aquire a lock
  int i = dequeue();
  signal(lock);//release lock so other canperfor their operations
  signal(empty);//since one element is removed increase empty count
}

Here is my version of code. Let me know any flaw in my way of designing the queue.

public class Queue {
	
	private Boolean isFull;

	private Integer size;

	private Integer[] arr;

	public Queue(Integer size) {
		this.size = size;
		arr = new Integer[size];
		isFull = false;
	}
	
	public synchronized void add(Integer value) throws InterruptedException
	{
		if(isFull) this.wait();
		int i = 0;
		for (; i < size; i++) {
			if(arr[i] == null)
			{
				arr[i] = value;
				break;
			}
		}
		if(i+1==size) isFull = true;
	}
	
	public synchronized Integer remove()
	{
		Integer firstElement = arr[0];
		
		for (int i = 0; i < size; i++) {
			if(i==size-1)
			{
				arr[i] = null;
			}else
			{
				arr[i] = arr[i+1];
			}
		}
		
		if(isFull)
		{
			isFull = false;
			this.notify();
		}
		return firstElement;
		
	}
	
	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] != null)
				s.append(arr[i]+", ");
		}
		return s.toString();
	}
	
	public static void main(String[] args) {
		Queue queue = new Queue(5);
		for (int i = 0; i < 10; i++) {
			new Thread(new AddThread(queue)).start();
			try {
				TimeUnit.SECONDS.sleep(2);
				System.out.println(queue);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		
		for (int i = 0; i < 10; i++) {
			new Thread(new RemoveThread(queue)).start();
			try {
				TimeUnit.SECONDS.sleep(2);
				System.out.println(queue);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
}

this is essentially a producer consumer problem, i think the flaw in the above solution is remove function just goes ahead and removes the values without checking if the add function is acting on the same memory area. I think its explained well in wikipedia.

remove function has to take care of empty queue condition. need to take care of multiple producers and consumers. wikipedia has references for these cases

class Queue
{
	pritvate:
		const int Queue_Size=100;
		int index;
		int queue[Queue_Size];

		Mutex queueMutex;
		ConditionVariable emptySpaceCondition;

	public:

		Queue():index(-1)
		{
	
		};

		void Push(int value)
		{
			queueMutex.lock();
			while(index>=99)
			{	
				emptySpaceCondition.wait(queueMutex);
			}

			//critical section

			index++;
			queue[index]=value;

			queueMutex.unlock();

		};


		int Pop()
		{
			int result;
			queueMutex.lock();
			
			if(index>=0)
			{
				result=queue[--index];
			}

			queueMutex.unlock();

			emptySpaceCondition.wake();

			return result;
		};	

		bool isEmpty()
		{
			queueMutex.lock();
			bool result=(index==-1);
			queueMutex.unlock();
		};
};

Java code:

public class SharedQueue implements Runnable{
static int size=5;
static int[] queue=new int[size];
static int putAt=0;
static int deleteAt=0;
static int numElements=0;
static int id=0;

static Delete del;
static Add add;

public void run(){
Random r=new Random();

if(r.nextInt(2)==0)
add.add(r.nextInt());
else
del.delete();
}

public static void main(String[] args)
{
SharedQueue q=new SharedQueue();
del=new Delete(q);
add=new Add(q);

Thread[] t=new Thread[50];

for(int i=0;i<50;i++)
{
t[i]=new Thread(q);
t[i].start();
}
}
}

class Delete{
static SharedQueue q;

public Delete(SharedQueue q)
{
this.q=q;
}

public int delete()
{
int num;

synchronized(q){
while(q.numElements==0){
try {
q.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
synchronized(this)
{
num = q.queue[q.deleteAt];
if(q.deleteAt<q.size-1)
q.deleteAt++;
else
q.deleteAt=0;
}
synchronized(q){
q.numElements--;
System.out.println("deleted "+num+" "+q.numElements);
q.notifyAll();
}
return num;
}
}

class Add{
static SharedQueue q;
public Add(SharedQueue q)
{
this.q=q;
}

public void add(int x)
{
synchronized(q){
while(q.numElements==q.size){
try {
q.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

}
synchronized(this){

if(q.putAt==q.size-1)
q.putAt=0;
else
q.putAt++;

q.queue[q.putAt]=x;
}

synchronized(q){
q.numElements++;
System.out.println("added "+x+" "+q.numElements);
q.notifyAll();
}
}
}