Find what the maximum and minimum values of x are after processes complete execu

Question

Find what the maximum and minimum values of x are after processes complete execution. Also, (please see picture below)

4. [40 points] Consider a shared variable x, initialized to zero, is operated on by four processes A,B, C, and D. Processes A and B increment x by one while processes C and D decrement x by two. Each process, before reading, performs wait on a semaphore S and signal on S after store. S is initialized with 2 (i.e., S-2). Find what the maximum and minimum values of x are after processes complete execution. Also, show the two sequences (i.e., trace the sequence of interleavings of statements - context switches) for getting these maximum and minimum values. Find the visual representation of these four processes in memory below wait(s) read(x) wait(s) read(x) wait(s) read(x) wait(s) read(x) write(x) signal(x) write(x) signal(x) write(x) signal(x) write(x) signal(x)

Explanation / Answer

Lets consider the given question:

1 Shared variable X = 0

2 There are 4 processes A, B, C, & D

3. So in memory   X= 0

4. Process A & B reads X from memory , increments by 1 and stores it back

            READ X

            X=X+1

            STORE X

5. Process C& D reads X from memory , decrements by 2 and stores it back

            READ X

            X=X-2

            STORE X

6. Each process invokes a Semophore S initialized to 2

7. Each operation is wrapped by wait and signal operations respectively.

8. Here, S=2 indicates that two max processes can run at the same time.

Execution:

Process A executes S=1, X=1 but it doesn’t update the x variable.

Then process C executes S=0, it decrements x, now x= -2 and signal semaphore S=1

Now process B executes S=0, X=-4, signal semaphore S=1

Now process D updates X=1, S=2 Then process X executes X=2

So from the above we see that the maximum value X takes is 2 & minimum it takes can be -4.

The context switching is elaborated below:

A executes statement 1 : Decreases the semaphone count by 1. S = 1 now.

A executes statement 2 : Reads x from memory and copies into internal register.

C executes statement 1 : Decreases the semaphore count by 1. S = 0 now. Now, both W, Y are in critical section and no other process can go inside it.

C executes statements 2-4 : Reads x (i.e. 0), decrements it by 2 and writes back. Now, x = -2

C executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 1. Now, some other process can go inside ciritcal section.

D executes statement 1 : Decreases the semaphore count by 1. S = 0 now. Now, both W, Z are in critical section and no other process can go inside it.

D executes statements 2-4 : Reads x (i.e. -2), decrements it by 2 and writes back. Now, x = -4

D executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 1. Now, some other process can go inside cirtical section.

A executes statement 3-4 : Increments x (i.e., 0, which it read long back) to 1, writes it back to memory. x = 1.

A executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 2. Now, some other processes can go inside cirtical section.

B executes statement 1-5 : X reads the value of x (i.e., 1) and increments it by 1 and writes back to memory. x = 2 now.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.