Concurrent Access to Objects
This question asks about synchronizing methods for stack and queue objects.
(a) Bounded stacks can be de?ned as objects, each containing an array of up to n items. Here is apseudocode for one form of stack class.
class Stack private
contents : array[1..n] of int top : int
constructor
stack () = top := 0 public
push (x:int) : unit = if top <> then
top := top + 1; contents[top] := x
else raise stack full; pop ( ) : int =
if top > 0 then top := top - 1:
return contents[top+1] else raise stack empty;
end Stack
If stacks are going to be used in a concurrent programming language, what problem might occur if two threads invoke push and pop simultaneously? Explain.
(b) How would you solve this problem by using Java concurrency concepts? Explain.
(c) Suppose that, instead of stacks, we have queues:
class Queue private
contents : array[1..n] of int front, back : int
constructor
queue() = front := back := 1 public
insert (x:int) : unit =
if back+1 mod n != front then back := back+1 mod n; contents[back] := x
else raise queue full; remove ( ) : int =
if front != back then front := front+1 mod n; return contents[front]
else raise queue empty;
end Queue
Suppose that ?ve elements have been inserted into a queue object and none of them have been removed. Do we have the same concurrency problem as we did with push and pop when one thread invokes insert and another thread simultaneously invokes remove? Assume that n is 10. Explain.