CSE 120 Extra Concurrency Practice
Spring 2015
Quick Tips: Questions to ask.
Is there an overarching classic idiom?
- Mutual Exclusion
- Producer-Consumer
- Readers-Writers
What are the type of critical resources?
- How many instances of each type initially exist?
- How many can exist, max? (min?)
- Are instances created or consumed?
- Is there any type of conservation, e.g. trading spaces for boxes?
Are there any policies or other constraints? Eg,
- No more than 2 baskets or one cart
- Eating requires 2 chopsticks
- There need to be 3 firefighters to manage a hose, but no more than 4 can fit in the room
- Etc
Quick Tips: Things to remember
- Acquire mutexes and semaphores in a common order across your code, or be concerned about deadlock
- In a monitor solution, the conditions upon which a condition is signaled are often the same as the conditions upon which one waits for the same condition
- In a monitor solution, it is always safe to use a “while” instead of an “if” when checking the predicate (even if sometimes unnecessary)
- Generally monitors solutions have entry functions in pairs, one which acquires resources and one which releases them. This is not a requirement, sometimes all work can be done within the monitor, but it is an extremely common idiom to decrease contention within the monitor.
- One can’t see the value within a semaphore – as it couldn’t be used without risking a race.
- Condition variables require mutual exclusion to ensure that there isn’t a problem between checking the predicate and waiting or a “lost wake-up”. This is intrinsically provided by a monitor, but requires a mutex in other contexts.
- If stumped on a monitor solution, try working it backwards. Right the entry functions that release resources, then go back and write the ones that acquire them.
Problem 1 [15-213 @ CMU] Semaphores and Threads
Consider the following three threads and three semaphores:
/* Initialize semaphores */
s1 = 1; s2 = 0; s3 = 0;
/* Initialize x */
x = 0;
void thread1() {
x = x + 1;
}
void thread2() {
x = x + 2;
}
void thread3() {
x = x * 2;
}
- Add P(), V() semaphore operations (using semaphores s1, s2, s3) in the code for thread 1, 2 and 3 such that the concurrent execution of the three threads can only result in the value of x = 6.
Problem 2 [15-213 @ CMU]. Semaphores and Deadlock
This question tests your understanding of synchronization, deadlocks and the use of semaphores. Assume each function is executed by a unique thread on a uniprocessor system.
Consider the following C code:
/* Initialize semaphores */
mutex1 = 1;
mutex2 = 1;
mutex3 = 1;
mutex4 = 1;
void thread1() {
P(mutex4); _____
P(mutex2); _____
P(mutex3); _____
/* Access Data */
V(mutex4); _____
V(mutex2); _____
V(mutex3); _____
}
void thread2() {
P(mutex1); _____
P(mutex2); _____
P(mutex4); _____
/* Access Data */
V(mutex1); _____
V(mutex2); _____
V(mutex4); _____
}
- Is it possible for the code above to deadlock? Yes No
- If no, explain why not. If yes, then indicate a feasible sequence of calls to the P or V operations that will result in a deadlock. Place an ascending sequence number (1, 2, 3, and so on) next to each operation in the order that it is called, even if it never returns. For example, if a P operation is called but blocks and never returns, you should assign it a sequence number.
Problem 3 [15-213 @ CMU]. Produce-Consumer
This problem is about using semaphores to synchronize access to a shared bounded FIFO queue in a producer/consumer system with an arbitrary number of producers and consumers.
• The queue is initially empty and has a capacity of 10 data items.
• Producer threads call the insert function to insert an item onto the rear of the queue.
• Consumer threads call the remove function to remove an item from the front of the queue.
• The system uses three semaphores: mutex, items, and slots.
Your task is to use P and V semaphore operations to correctly synchronize access to the queue.
- What is the initial value of each semaphore?
mutex = ______
items = ______
slots = ______
- Add the appropriate P and V operations to the pseudo-code for the insert and remove functions:
void insert(int item) {
/* Insert sem ops here */
add_item(item);
/* Insert sem ops here */
}
intremove() {
/* Insert sem ops here */
item = remove_item();
/* Insert sem ops here */
return item;
}
Problem 4 [15-412 @ CMU]. Monitors and Condition Variables
Imagine a narrow bridge running North-South along a public roadway. The bridge is nominally two lanes, with one lane for each direction, and can accommodate two opposing cars simultaneously, but it is too narrow to properly accommodate even a single truck. As a result, a single truck must occupy both lanes in order for it to cross the bridge. Bicyclists can also use the bridge -- two bicycles can fit simultaneous per lane of travel.
Please assume the following in your answer:
- Cars and bicycles always travel in the right (proper) lane
- Cars and trucks cannot pass each other and, as a result, must be serviced in the relative order in which they arrive.
- Bicycles travel singly, or in pairs, across the bridge.
- Bicycles always travel in the right (proper) lane.
- As they approach the bridge, bicycles can ride in the curb-lane and, as a result, will pass cars and trucks that have not yet entered the bridge.
Please implement a monitor-paradigm solution to this problem using monitors. Your solution should be written in pseudo-code similar to that used within your textbook, C or C++, or Java. The goal of your solution is, of course, to provide a structure that maximizes the use of the bridge while preventing collisions.
Please also state the semantics of your solution: Mesa, Brinch Hanson, or Hoare.
Your monitor should include exactly the following entry procedures:
- EnterNorthBound (enumvehicle_type);
- EnterSouthBound (enumvehicle_type);
- ExitNorthBound (enumvehicle_type);
- ExitSouthBound (enumvehicle_type);
Whereenumvehicle_typeis one of CAR, BICYCLE, or TRUCK;
Problem 5 [15-412 @ CMU]. Semaphores
Please provide a solution to the problem posed inQuestion #4, but this time please use semaphores instead of a monitor. Specifically, the only concurrency control primitive you should use is the semaphore. Specifically, the semaphore should be a counting semaphore that includes exactly the following operations:
- P() // decrements count and blocks, as necessary
- V() // increments count and activates blocked thread, as necessary
- init(int n) // initializes semaphore to represent "n" resources.
Problem 6 [15-412 @ CMU]. Monitors and Condition Variables
Imagine a picnic buffet with salad, soup, and meat. Unfortunately, also assume that there are too few serving utensils: There is only one large serving fork and one large serving spoon.
Please assume the following in your answer:
- It requires both one fork and one spoon to get salad
- It requires one spoon to get soup.
- It requires one fork to get a piece of meat.
- No one will be grossed out, or sickened by, cross-contamination of food types via the serving utensils, so they can be shared between food items.
Please implement a monitor-paradigm solution to this problem using monitors. The goal of your solution is, of course, to provide a structure that ensures that ensures that everyone can access all types of food.
Your solution should be written in pseudo-code similar to that used within your textbook, C or C++, or Java. Please also state the semantics of your solution: Mesa, Brinch Hanson, or Hoare.
Your monitor should include exactly the following entry procedures:
- WantSalad ();
- DoneGettingSalad();
- WantMeat();
- DoneGettingMeat();
- WantSoup();
- DoneGettingSoup();
Problem 7 [15-412 @ CMU]. Semaphores
Please provide a solution to the problem posed inQuestion #6, but this time please use semaphores instead of a monitor. Specifically, the only concurrency control primitive you should use is the semaphore. Specifically, the semaphore should be a counting semaphore that includes exactly the following operations:
- P() // decrements count and blocks, as necessary
- V() // increments count and activates blocked thread, as necessary
- init(int n) // initializes semaphore to represent "n" resources.