80.2K

Verified Solution

Link Copied!

Problem A. The pseudocode as below illustrates the basic push() andpop() operations of an array-based stack, where top is initializedas 0 when the stack is empty. Assuming that at a given moment, SIZEis equal to 20, top is equal to 8, this code is used in aconcurrent environment (top and stack[] are in shared memorysection), process P0 is about to call push() and process P1 isabout to call pop() concurrently

a. Which variable has a race condition? What are the items onstack when top is equal to 8 (hint: stack[0], stack[1] …,stack[???])

b. In which order LINES A, B, X, and Y are executed such thatan item is correctly pushed onto the stack as stack[i] by P0 firstand then popped out by P1? What is the value of i? What is thevalue of top when P0 is done with pushing? What is the value of topwhen P1 is done with popping?

c. In which order LINES A, B, X, and Y are executed such thatan item stack[j]is correctly popped out of the stack by P1 firstand then P0 pushes an item onto the stack as stack[k]? What are thevalues of j and k? What is the value of top when P1 is done withpopping? What is the value of top when P0 is done withpushing?

d. In which order LINES A, B, X, and Y are executed such thatP0 adds an item onto the stack as stack[8] first, then P1 readsstack[7], finally top still remains as 8 after both P0 and P1 aredone? This is a case where P0’s push operation is voided. e. Inwhich order LINES A, B, X, and Y are executed such that P0 firstincorrectly replaced the original item stack[7] on stack with itsnew item, then P1 reads stack[8] with a random value, finally topstill remains as 8 after both P0 and P1 are done? This is a casewhere P1’s pop operation is voided.

void push(int item) {

if (top < SIZE) {

stack[top] = item; // LINE A

top++; // LINE B

} else

ERROR

}

int pop() {

if (top > 0) {

top--; // LINE X

return stack[top]; // LINE Y

} else

ERROR

}