Question

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

a. Which variable has a race condition? What are the items on stack 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 that an item is correctly pushed onto the stack as stack[i] by P0 first and then popped out by P1? What is the value of i? What is the value of top when P0 is done with pushing? What is the value of top when P1 is done with popping?

c. In which order LINES A, B, X, and Y are executed such that an item stack[j]is correctly popped out of the stack by P1 first and then P0 pushes an item onto the stack as stack[k]? What are the values of j and k? What is the value of top when P1 is done with popping? What is the value of top when P0 is done with pushing?

d. In which order LINES A, B, X, and Y are executed such that P0 adds an item onto the stack as stack[8] first, then P1 reads stack[7], finally top still remains as 8 after both P0 and P1 are done? This is a case where P0’s push operation is voided. e. In which order LINES A, B, X, and Y are executed such that P0 first incorrectly replaced the original item stack[7] on stack with its new item, then P1 reads stack[8] with a random value, finally top still remains as 8 after both P0 and P1 are done? This is a case where 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

}

Answer 1

1. Firstly we need to understand the meaning of race condition. Whenever two processes, that can access shared data, try to amend it (shared data) at the same time, race condition occurs i.e. both the processes are racing to access/amend the shared data.

• Here, in the given question, the variable top will undergo race condition because both the processes P0(push) and P1(pop) are trying to access top and amending it simultaneously.
• Also, the items on stack when top is equal to 8 are

stack[0]

stack[1]

stack[2]

stack[3]

stack[4]

stack[5]

stack[6]

stack[7]

stack[8]

2. Correct order of execution :

Line A

Line B

Line X

Line Y

• The value of i after one successful push and pop is 8

Lets say (top=8), therefore i=8.

• While push, stack[8]=item //i=8

        i++ // i=9 value of top incremented by 1 when P0 id done pushing.

• While pop, top- - //i=8

                   stack[8]=item //i=8 value of top decremented by 1 when P1 is done popping.

3. Correct order of execution :

Line X

Line Y

Line A

Line B

The value of j=7 and k=9

Lets say k=8

• While pop, j- - //j=7

                  stack[7]=item //j=7 value of top decremented by 1 when P1 id done popping.

The value of top when push is done top= 7.

• While push, stack[8]=item //k=8

        k++ // k=9 value of top incremented by 1 when P0 id done pushing.

The value of top when push is done top= 9.

4. Correct order of execution :

Line A

Line B

Line X

Line Y