Semaphores Assignment Instructions
Instructions
Problem #1:
The following code is for a producer and a consumer process. Assume that these processes are run in a multi-processing environment and answer the questions below. Remember that in a multi-processing environment, the producer can execute one or a few lines of code, followed by the consumer executing one or a few lines of code, followed by the producer again, and so on.
// semWait(x) => if (x.value == 1) x.value = 0 and can continue running else block until signaled on x
// semSignal(x) => x.value = 1. Process waiting on x can run
int n = 0; // number of items in the buffer
binary_semaphore s = 1; // mutex for buffer access
binary_semaphore delay = 0; // force consumer wait if buffer empty
void producer() // One producer
{
while (true) {
produce(); // Produce an item
semWait(s); // Wait on Buffer
append(); // Critial Section
n++; // Critical Section
if (n==1) semSignal(delay); // Critical Section
semSignal(s);
}
}
void consumer() // One consumer
{
semWait(delay);
while (true) {
semWait(s);
take(); // Critical Section
n–; // Critical Section
semSignal(s);
consume(); // Consume an item
if (n==0) semWait(delay);
}
}
void main()
{
n = 0;
parbegin (producer, consumer); // Create producer and consumer entities.
}
The table below traces through a possible outcome of running the processes above.
| Producer | Consumer | s | n | delay | |
| 1 | 0 | 0 | |||
| 1 | produce() | 1 | 0 | 0 | |
| 2 | semWait(s) | 0 | 0 | 0 | |
| 3 | append() | 0 | 0 | 0 | |
| 4 | n++ | 0 | 1 | 0 | |
| 5 | if (n==1) semSignal(delay) | 0 | 1 | 1 | |
| 6 | semSignal(s) | 1 | 1 | 1 | |
| 7 | semWait(delay) | 1 | 1 | 0 | |
| 8 | semWait(s) | 0 | 1 | 0 | |
| 9 | take() | 0 | 1 | 0 | |
| 10 | n– | 0 | 0 | 0 | |
| 11 | semSignal(s) | 1 | 0 | 0 | |
| 12 | consume() | 1 | 0 | 0 | |
| 13 | produce() | 1 | 0 | 0 | |
| 14 | semWait(s) | 0 | 0 | 0 | |
| 15 | append() | 0 | 0 | 0 | |
| 16 | n++ | 0 | 1 | 0 | |
| 17 | if (n==1) semSignal(delay) | 0 | 1 | 1 | |
| 18 | semSignal(s) | 1 | 1 | 1 | |
| 19 | if (n==0) semWait(delay) | 1 | 1 | 1 | |
| 20 | semWait(s) | 0 | 1 | 1 | |
| 21 | take() | 0 | 1 | 1 | |
| 22 | n– | 0 | 0 | 1 | |
| 23 | semSignal(s) | 1 | 0 | 1 | |
| 24 | consume() | 1 | 0 | 1 | |
| 25 | if (n==0) semWait(delay) | 1 | 0 | 0 | |
| 26 | semWait(s) | 0 | 0 | 0 | |
| 27 | take() | 0 | 0 | 0 | |
| 28 | n– | 0 | -1 | 0 |
Question 1: Describe the situation that results from running the processes above in a multiprocessing environment. Be very specific in your answer. Elaborate on what has happened in the above scenario and why.
Question 2: In the space below, rewrite the producer and consumer code in such a way that it fixes the problem you described above. Be sure to highlight your changes in yellow like this.
Problem #2:
The following code is for another producer and a consumer process. Assume that these processes are run in a multi-processing environment and answer the questions below. Remember that in a multi-processing environment, the producer can execute one or a few lines of code, followed by the consumer executing one or a few lines of code, followed by the producer again, and so on.
// semWait(x) => if (x.value == 1) x.value = 0 and can continue running else block until signaled on x
// semSignal(x) => x.value = 1. Process waiting on x can run
|
|
int n = 0; // number of items in the buffer
binary_semaphore s = 1; // mutex for buffer access binary_semaphore delay = 0; // force consumer wait if buffer empty
void producer() // One producer { while (true) { produce(); // Produce an item semWait(s); // Wait on Buffer append(); //Critical Section n++; // Critical Section semSignal(delay); // Critical Section semSignal(s); } }
void consumer() // One consumer { semWait(delay); while (true) { semWait(s); take(); // Critical Section n–; // Critical Section consume(); // Consume an item semWait(delay); } } |
void main()
{
n = 0;
parbegin (producer, consumer); // Create producer and consumer entities.
}
To trace through the possibilities, you may find it helpful to fill in the table below to keep track of the values in s, n, and delay. You may add as many rows as needed to the table. This table will not be graded, however. Only your answers to the questions below will be graded.
| Producer | Consumer | s | n | Delay | |
| 1 | 0 | 0 | |||
| 1 | |||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| 6 | |||||
| 7 | |||||
| 8 | |||||
| 9 | |||||
| 10 | |||||
| 11 | |||||
| 12 | |||||
| 13 | |||||
| 14 | |||||
| 15 |
Question 1: Describe the inevitable outcome of running these processes in a multiprocessing environment. Be very specific in your answer. Elaborate on what has happened and why.
Question 2: In the space below, rewrite the consumer and producer code in such a way that it fixes the problem you described above. Be sure to highlight your changes in yellow like this.
Problem #3:
In a minimum of 150 words, compare and contrast mutex locks and semaphores.
Problem #4:
In a minimum of 150 words, discuss the concept of priority inversion and describe one way to solve the problem.
Problem #5:
After reading section 5.7.2 in your textbook and “Concurrent Control with ‘Readers’ and ‘Writers’” in your Reading & Study folder, Describe the first and second variations of the Readers-Writers problem. Include in your discussion the problem that may result from either variation and a possible solution for each. You may express your answer to the “possible solution for each” in code or pseudo-code, but be sure to describe in your own words the algorithm that you are suggesting as a solution.
