Starting from:
$29.99
Homework 3_Semaphores
Homework 3
1.(30 pts) Consider the following code example for allocating and releasing processes (i.e., tracking number of processes), #define MAX_PROCS 255 int number_of_processes = 0; /* the implementation of fork() calls this function */ int allocate_process() { int new_pid; if (number_of_processes == MAX_PROCS) return -1; else { /* allocate process resources and assign the PID to new_pid */ ++number_of_processes; return new_pid; } } /* the implementation of exit() calls this function */ void release_process() { /* release process resources */ --number_of_processes; } a.Identify the race condition(s). b. Assume you have amutex lock namedmutexwiththe operationsacquire()andrelease(). Indicate where the locking needs to be placed to prevent the racecondition(s). c.Could we replace the integer variable int number_of_processes = 0; with the atomic integer atomic_t number_of_processes = 0; to prevent the race condition(s)? Whyor why not?
2.(40 pts) The following partial code is abounded-buffer monitorin which the buffers are embeddedwithin the monitor (with two conditionvariables). Assume anycondition variablecondhastwo methods:cond.wait()and cond.signal(). Please implement theproduce()andconsume()methodsin pseudo code(no need to have actual .c program). Youcannotmodify existing code andcannothave any additional synchronizationmechanisms. monitor bounded_buffer { int items[MAX_ITEMS]; /* MAX_ITEM is a constant defined elsewhere */ int numItems = 0; /* # of items in the items array */ condition full, empty; void produce(int v); /* deposit the value v to the items array */ int consume(); /* remove the last item from items, and return the value */ } 3.(30 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 concurrently.
2
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; Pr1: 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. Please use pseudo code (which utilizes semaphores) to enforce execution order of the following process execution diagram.
Your pseudo code must specify semaphore initialization followed by the code for each process Pr1, Pr2, …, Pr9, similar to the example. For simplicity, please do NOT reuse any semaphore.
1.(30 pts) Consider the following code example for allocating and releasing processes (i.e., tracking number of processes), #define MAX_PROCS 255 int number_of_processes = 0; /* the implementation of fork() calls this function */ int allocate_process() { int new_pid; if (number_of_processes == MAX_PROCS) return -1; else { /* allocate process resources and assign the PID to new_pid */ ++number_of_processes; return new_pid; } } /* the implementation of exit() calls this function */ void release_process() { /* release process resources */ --number_of_processes; } a.Identify the race condition(s). b. Assume you have amutex lock namedmutexwiththe operationsacquire()andrelease(). Indicate where the locking needs to be placed to prevent the racecondition(s). c.Could we replace the integer variable int number_of_processes = 0; with the atomic integer atomic_t number_of_processes = 0; to prevent the race condition(s)? Whyor why not?
2.(40 pts) The following partial code is abounded-buffer monitorin which the buffers are embeddedwithin the monitor (with two conditionvariables). Assume anycondition variablecondhastwo methods:cond.wait()and cond.signal(). Please implement theproduce()andconsume()methodsin pseudo code(no need to have actual .c program). Youcannotmodify existing code andcannothave any additional synchronizationmechanisms. monitor bounded_buffer { int items[MAX_ITEMS]; /* MAX_ITEM is a constant defined elsewhere */ int numItems = 0; /* # of items in the items array */ condition full, empty; void produce(int v); /* deposit the value v to the items array */ int consume(); /* remove the last item from items, and return the value */ } 3.(30 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 concurrently.
2
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; Pr1: 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. Please use pseudo code (which utilizes semaphores) to enforce execution order of the following process execution diagram.
Your pseudo code must specify semaphore initialization followed by the code for each process Pr1, Pr2, …, Pr9, similar to the example. For simplicity, please do NOT reuse any semaphore.
1 file (478.7KB)
