Coordination (a.k.a. Synchronization) Problems and Protocols
An Introduction
|
Prof. David Bernstein
James Madison University
|
|
Computer Science Department |
bernstdh@jmu.edu |
|
Review
-
Flow of Control:
- A sequence of control transfers (i.e., transitions between
instructions/steps)
- Concurrent Flows:
- Two flows, \(X\) and \(Y\),
are said to running concurrently iff
\(Y\) began after \(X\) began
and before \(X\) finished or
\(X\) began after \(Y\) began
and before \(Y\) finished
Motivation for Studying Coordination
- The Upside of Concurrent Flows:
- It is sometimes beneficial to solve problems using concurrent
flows
- The Downside of Concurrent Flows:
- Solving problems using concurrent flows often
involves coordination
- Coordination can itself cause problems
Communication
- The Assumption:
- The parties that are coordinating can communicate
- Communication Mechanisms:
-
Transient - The information is only available
at the time it is transmitted
-
Persistent - The information persists after it
is transmitted (until it is modified/destroyed)
- Properties of Communication Channels:
-
Synchronous - Both parties (the sender and
receiver) must participate at the same time
-
Asynchronous - The parties can participate
at different times
- Informal Definition:
- An agreement about how communication will proceed
- Formal Definition:
- An agreement that governs the procedures used to exchange
information between cooperating entities
Important Properties of Coordination Protocols
- Sequencing (a.k.a. Serialization):
- It is possible to ensure that one party uses a resource
before another party
- Mutual Exclusion:
- It is possible to exclude both parties from using a resource
at the same time
Important Properties of Coordination Protocols (cont.)
- Starvation Freedom:
- If one party wants to use a resource then it can do
so eventually
- Deadlock Freedom:
- If both parties want to use use a resource then one of them can
do so eventually
- Fault Tolerance:
- The protocol accounts for incorrect behavior of the
parties and/or problems with the channel
Demonstrating that Coordination Protocols have Specific Properties
- Testing:
- Is often inadequate, especially for nondeterministic systems
- Proofs:
- Are often necessary (as they are when demonstrating the
correctness of some kinds of algorithms)
Initiation Problems
- The Nature of the Problem:
- \(N\) parties have \(N\) independent
tasks to complete
- There is no benefit (or it is impossible) to subdivide tasks
- Irrelevant Properties of the Protocol:
- Sequencing - doesn't arise because the order doesn't matter
- Mutual Exclusion - doesn't arise because the tasks
are independent can't be subdivided
- Deadlock Freedom - doesn't arise beacsue the tasks
are independent (i.e., require no common resources)
- Required Properties of the Protocol:
- Starvation freedom for all parties (i.e., all parties can complete
their tasks)
Initiation Problems (cont.)
- An Example:
- Two housemates, Mark and Daryl, need to complete
two chores between them --
mowing the lawn and washing the dishes
- They have one lawn mower and a small sink (so each chore
can be performed by at most one person)
- Solutions:
- Only involve a mechanism for initially dividing up the
tasks between the parties
Owner-Borrower Problems
- The Nature of the Problem:
- Two parties need to share a resource that can only be used
by one party at a time
- One of the parties (ie., the owner) has priority
- Required Properties of the Protocol:
- Mutual Exclusion
- Deadlock Freedom for the Owner
Owner-Borrower Problems (cont.)
- An Example:
- Owen (a marine veterinarian) owns a large
exercise tank (that is dark and contains many plants,
rocks, etc...)
- Barbara (another marine veterinarian) borrows the tank
when it is not in use
- Owen treats orcas and Barbara treats baleen whales
- Both would like to have their animals use the tank
- An orca and a baleen whale can't be in the tank together
- Solutions:
- Involve different behaviors for the two parties (i.e,
are asymmetric)
Owner-Borrower Problems (cont.)
- An Important Characteristic of this Example:
- It isn't possible to look in the tank and see if it is
occupied so a communication mechanism is necessary
- An Observation about the Communication Mechanism:
- A transient mechanism (e.g., shouting) isn't desirable
because the message might be missed
Owner-Borrower Problems - An Incorrect Solution
- The Protocol:
- Neither Owen nor Barbara releases an animal
- Properties:
- Mutual Exlcusion - Yes
- Deadlock Freedom for the Owner - No
Owner-Borrower Problems - Another Incorrect Solution
- The Communication Mechanism:
- Each party has a flag that can be raised and lowered
- The Protocol:
- Check to see if the other parties flag is raised
- If not, release your animal then raise your flag
- Properties:
- Mutual Exlcusion - No (both parties can check, see no flag, and
release)
- Deadlock Freedom for the Owner - No
Owner-Borrower Problems - Still Another Incorrect Solution
- The Communication Mechanism:
- Each party has a flag that can be raised and lowered
- The Protocol:
- Check to see if the other parties flag is raised
- If not, raise your flag then release your animal
- Properties:
- Mutual Exlcusion - No (both parties can check, see no flag,
and then act)
- Deadlock Freedom for the Owner - No
Owner-Borrower Problems - A Solution
- The Communication Mechanism:
- Each party has a flag that can be raised and lowered
- The Foundation of the Protocol:
- When a party wants to release an animal they first raise
their flag and then looks at the other flag
- When their animal returns they lower their flag
- Owen's Release Details:
- Don't release an orca until Barbara's flag is lowered
- Barbara's Release Details:
- If Owen's flag is up then Barbara lowers her flag
- Barbara waits until Owen's flag is lowered then raises her flag
and releases a baleen whale
Owner-Borrower Problems - A Proof of Mutual Exclusion
- Assume the Contrary:
- Assume a baleen whale and an orca are both in the tank
- Finding a Contradiction:
- According to the protocol, when Owen looked his flag was
already up. So, Barbara's flag must not have been up
- Hence, Barbara must have looked after Owen looked
(because otherwise her flag would be up)
- However, if Barbara looked after Owen looked then she must have
seen Owen's flag raised and hence she would not have
released a baleen whale (which is a contradiction)
- An Interesting Aspect of this Proof:
- It only involves the starting and ending times of actions,
not their duration
Owner-Borrower Problems - Other Properties
- Proof of Deadlock Freedom for the Owner:
- If Owen and Barbara both raise their flags then Barbara
will eventually notice and lower hers, allowing Owen
to release an orca
- Starvation Freedom?
- No -- Barbara defers to Owen so Owen can keep Barbara's
baleen whales waiting forever
Producer-Consumer Problems
- The Nature of the Problem:
- One party produces a product, but only if no units
are available
- The other party attempts to consume a product, but only
if units are available
- Required Properties of the Protocol:
- Mutual Exclusion
- Starvation Freedom
Producer-Consumer Problems (cont.)
- An Example:
- There is a cougar pen (with solid walls, a roof, and two
doors)
- Carol has a cougar that she releases into the pen when it
is hungry and there is a meal in the pen
- Peter places a meal in the pen when there isn't one in the pen
and when the cougar is not in the pen
- Solutions:
- Involve different behaviors for the two parties
Producer-Consumer Problems (cont.)
- An Important Characteristic of this Example:
- It isn't possible to look in the pen and see if it is
occupied so a communication mechanism is needed
- An Observation about the Communication Mechanism:
- A transient mechanism (e.g., shouting) isn't desirable
because the message might be missed
Producer-Consumer Problems - A Solution
- The Communication Mechanism:
- There is a light on top of the pen that both
parties can turn on and off with switches
- The Foundation of the Protocol:
- Peter adds a meal when the light is on
- Carol releases the cougar when the light is off
- Peter's Details:
- Waits until the light is on
- Enters the pen
- Puts a meal in the pen
- Leaves the pen
- Turns the light off
- Carol's Release Details:
- Waits until the light is off
- Releases the cougar into the pen when it is hungry
- Waits until the cougar eats and exits the pen and
then turns the light on
Producer-Consumer Problems - A Proof of Mutual Exclusion
- A State Model:
- The Proof:
- There are no transitions between the "with Peter"
and "with Cougar" states
Producer-Consumer Problems - A Proof of Starvation Freedom
- Assume the Potential for Starvation:
- CougarHungry is true
- NoMeal is true
- The Proof:
- Regardless of the starting state, eventually, the system
will transition to OffWithCougar
Reader-Writer Problems
- The Nature of the Problem:
- There are one or more parties that modify (i.e., write to)
an entity's properties
- There are one or more parties that access (i.e., read from)
an entity's properties
- Required Properties of the Protocol:
- Each writer must have exclusive access to the entity
- Readers may share access to the entity
Reader-Writer Problems (cont.)
- Examples:
- Reservation Systems - multiple parties can obtain information
at the same time but only one party can make a reservation
at a time
- Backup Systems - multiple parties can retrieve archived files
at the same time but only one party can save a file at a time
- Variants:
- Favor Readers - Don't keep readers waiting unless a writer has
already been granted access
- Favor Writers - Readers must wait on writers, even if the writers
are themselves waiting on other parties
Rendezvous Problems
- The Nature of the Problem:
- There are two parties, Andrea and Bill, each of whom
performs two tasks in order, \((A1, A2)\)
for Andrea and \((B1, B2)\) for Bill
- Required Properties of the Protocol:
- Sequencing - \(A1\) must happen
before \(B2\) and \(B1\) must happen before
\(A2\)
- Starvation Freedom
- Deadlock Freedom
Rendezvous Problems (cont.)
- Number of Permutations:
- There are \(4! = 24\) possible orderings of the
four tasks
-
- Sequence-Satisfying Permutations:
- There are six permutations that satisfy the two
cross-person sequencing requirements:
(A1, B1, A2, B2), (A1, B1, B2, A2), (A1, B2, B1, A2),
(B1, A1, A2, B2), (B1, A1, B2, A2), (B1, A2, A1, B2)
- Only four of these are consistent with the within-person
sequencing:
(A1, B1, A2, B2), (A1, B1, B2, A2),
(B1, A1, A2, B2), (B1, A1, B2, A2)