4. (20 pts) In an operating system processes can run concurrently. Sometimes we

Question

4. (20 pts) In an operating system processes can run concurrently. Sometimes we need to impose a specific order in execution of a set of processes. We represent the execution order for a set of processes using a process execution diagram. Consider the following process execution diagram. The diagram indicates that Pr1 must terminate before Pr2, Pr3 and Pr4 start execution. It also indicates that Pr4 should start after Pr2 and Pr3 terminate and Pr2 and Pr3 can run Pr2 Prl Pr4 Pr3 We can use semaphores in order to enforce the execution order. Semaphores have two operations as explained below. P (or wait) is used to acquire a resource. It waits for semaphore to become positive, then decrements it by 1. V (or signal) is used to release a resource. It increments the semaphore by 1, waking up the blocked processes, if any Assume that the semaphores s1, s2, and s3 are created with an initial value of 0 before processes Pr1, Pr2, Pr3, and Pr4 execute. The following pseudo code uses semaphores to enforce the execution order: s1-0; s2-0; s3-0; Pri: body; V(s1); V(s1); Pr2: P(s1); body; V(s2; Pr3: P(s1); body; V(s3); Pr4: P(s2); P(s3); body; It is obvious that a different process execution diagram may need different number of semaphores. Note we could consolidate s2 and s3 so that Pr3: .; Vs2) and Pr4: P(s2); P(s2). But we choose not to do so. That is, for each process that is followed by an immediate successor, we always create one new semaphore. Please use pseudo code (which utilizes semaphores) to enforce execution order of the following process execution diagram. Pr3 9 Pr1 Pr8 Pr9 Pr5 Pr7

Explanation / Answer

For the given process execution diagram, it is clear that Pr1 should execute first before all other processes.

Then Pr2, Pr5 and Pr6 can execute parallely. Pr7 shold execute after Pr6. Pr3 and Pr4+Pr8 can execute parallely. Pr9 should execute after Pr3, Pr8, Pr& get over.

So, assume semaphore s1,s2,s3,s4,s5,s6,s7 and s8 are created with initial value 0 before these 9 processes execute.

So, to enforce execution order following pseudo code should be used.

s1=0;s2=0;s3=0;s4=0;s5=0;s6=0;s7=0;s8=0;

Pr1: body;V(s1);V(s1);V(s1);

Pr2: P(s1);body;V(s2);V(s2);

Pr3: P(s2);body;V(s3);

Pr4: P(s2);body;V(s4);

Pr5: P(s1);body;V(s5);

Pr6: P(s1);body;V(s6);

Pr7: P(s6);body;V(s7);

Pr8: P(s4);P(s5);body;V(s8);

Pr9: P(s3);P(s7);P(s8);body;

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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