• Mutex

• Semaphore

• Condition Variable

Mutex

If you understand the phrase "mutually exclusive" then you already know the basic idea of a mutex. Mutexes, or mutual exclusions, are used to protect data structures in multi-threaded processes. By coordinating multiple threads accessing the same data a mutex prevents interference between threads that may cause instability in the program. Threads take turns locking the mutex (accessing the resource) one at a time. Waiting threads are queued up and take their turn locking (accessing) the shared resource as each previous thread unlocks (releases) the mutex. Only the thread that has locked the mutex can access the data structure to read or write to it.

• Analogy: This is similar to needing a key to access the restroom at a gas station.

  • The clerk at the counter who controls access to the key is like the mutex.
    

  • The restroom is like the data structure.
    

  • An individual needing to use the restroom is like a thread.
    

  If someone (a thread) wants to use the bathroom (data structure) they must request permission from the clerk (mutex), who only has 1 key to give out. The person who currently possesses the key (locks the mutex) has access to use the restroom and everyone else must wait. Once the key is returned to the clerk (the mutex is unlocked) anyone waiting for the restroom may then attempt to get the key from the clerk. Eventually each waiting person will get their turn, but in this way the restroom cannot be used by more than one person at a time. [Please disregard the 'human factor' in this analogy, which allows individuals to break rules. Thankfully computers are much less prone to do so.]

Semaphore

Semaphores have 2 features - they count resources and they snooze threads. They can either count up from 0 or down from a preset starting point. In both cases a value of 0 indicates that there are no available resources. When the count is 0 a semaphore tells threads to wait until the resource count is >0. Because of the potential to permit multiple threads access to the same resource (ex: a job queue), the individual data structures are often protected directly by a mutex and the semaphore acts as a second layer of regulation.

Note that a semaphore can behave much like a mutex if the count never exceeds 1. Like a mutex, a semaphore limited to 1 can only allow 1 thread past its "check point" in the process. This effectively removes the possibility of another thread using the same data simultaneously.

green

green

purple

• Analogy - counting down: This is similar to waiting in a single line for access to any one of a number of check stands, like you might do at some "big box" stores (ex: Fry's Electronics). There are so many check stands that you can't see which are open for sure, more than one check stand might become available simultaneously so multiple customers could move forward at the same time, and it would be embarrassing and awkward to leave the line only to find that the space you thought was available isn't and there's nowhere to go. In real life this can be resolved with lights above each check stand to indicate when one is available. The eyes and brains of the customers provide the remainder of the problem-solving. In programming terms, you resolve this with mutexes and a semaphore.

  • A semaphore is used in lieu of lights to provide a count of available data structures (check stands). The semaphore allows the same number of threads (customers) as available data structures (check stands) to simultaneously attempt to access the data (approach the check stands). If there is no available data (check stands are all in use or all closed) then the semaphore tells all the threads (customers) to wait.

  • A mutex protects each data structure (check stand) from being accessed by more than one thread (customer) at a time. (See above for mutex details.)

  When the store opens in the morning, the semaphore count indicates the total number of check stands (data structures) - let's say 8. It remains unchanged until a customer (thread) enters the line and checks the semaphore to see if there is an open check stand. Since there are 8 open, and the customer only needs 1, the customer leaves the line and picks a check stand to use. When the customer enters the check stand (s)he locks the mutex for that stand (in real life this could be equivalent to just taking up the space there). When the mutex is locked and the stand is in use the semaphore is decremented to 7. green

  The next customer to enter the line will see that there are 7 available check stands and can repeat the process. When a customer has completed his/her transaction and unlocks the mutex the semaphore count is then incremented (raised) by 1 to indicate that the stand is now available for another customer. This process repeats for each customer wishing to check out as long as there is at least 1 available check stand. If the store gets busy and the check stands fill up with more customers waiting in line, then the other feature of the semaphore comes into play. Customers in excess of 8 are instructed, by the semaphore, to wait in line until the count is a positive number. When it is, a customer can leave the line and enter an available check stand. If more than one check stand becomes available simultaneously this creates the possibility that more than one customer may leave the line and head for a check stand at the same time. This moves the line along faster but could also result in a jam where two customers are trying to gain access to the same check stand. (Imagine them both putting their purchases on the counter together, getting them mixed up and 'contaminating' each others' purchases.) This is where a mutex becomes valuable. Each check stand has it's own mutex to prevent multiple customers from trying to process their transactions through the same check stand. Whoever locks the mutex first (puts the first item on the counter) gets to use that check stand and the other customer is blocked and must find another available check stand to complete their transaction. As above, as customers finish transactions and vacate check stands the semaphore is incremented. At the end of the day when all the customers are gone and all the check stands are empty the semaphore will again read 8.

  Analogy - counting up: This is similar to a car wash using a counter display to show the number of recently washed cars waiting for the drying team to dry them.

  • The cars are what are waiting to be worked on (data available for processing).
  • The Dryers (threads) are the people who need to work on the cars (data) next.

  • The counter (semaphore) keeps track of how many cars (data) are waiting and tells the Dryers (threads) to stop and rest if there aren't any (count=0).

  Under normal circumstances the Dryers dry cars as they come out of the car wash. In most cases the semaphore count would alternate between 0 and 1. However, if something slowed down the drying process (ex: the car wash becomes very busy and temporarily runs out of dry towels; several small cars follow several big cars; the drying crew is smaller or slower than usual...) it is possible that a backlog of cars to be dried could form. In that case the semaphore would continue to increment (count up) as cars exited the car wash, and would decrement (count down) as cars were taken for drying. When the Dryers finally get to the last car and the count is 0 they would be able to take a break.

Condition Variable

Condition variables in SDL are used to monitor the status of other variables and alert waiting functions when there has been a change. (The "variable" that they monitor is the "condition" (changed or unchanged) of some complex state.) They do not protect directly like mutexes do. Instead they coordinate threads by monitoring for changes, keeping threads waiting when there is nothing to do, and alerting them when change occurs. This saves time and resources by preventing threads from trying to work on data that isn't available and from constantly checking data that isn't changing.

Note that the state that the condition variable is monitoring must always be protected by a mutex so that when the condition variable indicates a change, only one thread can read and potentially change the variable at a time.

• Analogy: This is similar to getting an alert when you have received a text message. The alert does not tell you who it is from or what it says (at least not on older phones), just that a message has been received. You then have to look for the details of the message yourself.

  • The condition variable monitors your inbox and produces an alert telling you when there has been a change in the number of messages (the state being monitored).

  • You are like a thread waiting for information to arrive in the inbox.

  • It is useless to keep getting out your phone and checking the inbox if there is nothing new there. Having an alert tell you as soon as something has arrived saves you time and energy and ensures that you know the moment a new message becomes available instead of finding it eventually when you get around to checking again. Similarly, condition variables help to keep threads busy when there is something to do but idle when there isn't.

An Analogy Using All Three

• Imagine a buffet-style restaurant. You, the customer (one of the threads), would like to utilize the goods and services (data structures) available at this restaurant. When you enter the restaurant you are first met by a Host(ess) (another thread). (S)He asks for the number of individuals in your party. (S)He assigns your party size to a read-only variable (PartySize=x) that will follow you through the restaurant so no one else has to ask the same question. green

  The Host(ess) then checks to see if there is an available table of an appropriate size (TableSize=x).

  • Semaphores track the number of available tables of each size (ex: 4 of TableSize=2, 8 of TableSize=4, 5 of TableSize=6, etc.).

    • They are decremented (reduced) from the maximum number of tables of each size as patrons are seated (ex: 4 decremented to 3 of TableSize=2 when a couple is seated).

    • They are incremented (increased) up to the maximum number as patrons leave and the tables are cleaned for the next guests (ex: 3 incremented to 4 of TableSize=6 when a family leaves).

  • ?? A mutex protects the semaphores from being changed by more than one restaurant worker at a time. (ex: If the Host(ess) is changing the value because a party is being let in then a Busser cannot simultaneously change the value when a table of the same size has just been cleaned. The Busser could, however, change the value for a table of a different size.) ?? green

  • A condition variable monitors the semaphores for changes. When a semaphore count changes the condition variable alerts the Host(ess) to check the counts to see if a waiting Party can be seated.

  The Host(ess) checks the appropriate semaphore for the table size needed for your party (TableSize > PartySize). If the value is 0 you and your party are requested to wait. If the value is >1 your party is allowed to enter the buffet line.

  • ?? The Host(ess) locks the mutex and decrements (reduces the count by 1) the semaphore for that size table, so (s)he knows it is taken and does not accidentally assign it to another party while you are sitting there. ??

  The next person you meet is the Buffet Manager (another thread).
  • (Please bear with the analogy a little at this point. While this may not occur in a real restaurant, it is not inconceivable and fits the situation well.)
  The Buffet Manager's job is to ensure that no one passes through the buffet unless it is ready for them.
  • There are 5 types of Hardware (plate, cup, spoon, fork, and knife) being monitored in this example.
    • Each has a variable holding a current count (ex: forks=18, spoons=20, knives=11, etc.)

    • Each variable is protected by its own mutex. This prevents a Patron from taking Hardware (and decrementing the variables) while a busser is refilling the Hardware (and incrementing the variables), which may confuse the count.

    • Each variable is monitored by a single condition variable that watches for the values to change. A change in any one variable triggers the condition variable, which alerts the Buffet Manager to check and see if there is now enough Hardware to send the next party through.

  • There are 3 categories of people who interact directly with the Hardware counts.
    • Patrons (in Parties, ex: Jones-Party of 3) who take Hardware to use and cause the count to be decremented.
    • Bussers who bring clean Hardware back and cause the count to be incremented.
    • The Buffet Manager who reads the variable counts and ensures that the requirements are met.
  • There are 2 requirements that must be met to be allowed into the buffet by the Buffet Manager.

    • The previous Party must have left the buffet (Patrons=0), so the quantity of Hardware that they took is reflected accurately in the counts. green

    • There must be enough of each type of Hardware available to send an entire party through together. green

  In order to know when it is OK to send a Party through the buffet, the Buffet Manager waits for the buffet to be empty of Patrons. green

  Then, (s)he must check the Hardware variables and compare them to the PartySize variable for your Party (all counts must be > PartySize). If the initial check when your Party approaches finds that there is enough Hardware your Party is allowed to pass. If a count is too low the Buffet Manager waits on the condition variable and your Party waits in line.

  • Because of the mutex on each variable the Buffet Manager can only view the current counts when no one else is interacting with the Hardware. This ensures that the Buffet Manager is basing his/her decision to send a group through on current, accurate counts. green

  • If your Party has to wait, you will wait until the condition variable alerts the Buffet Manager that a Hardware count has changed. (This is more efficient than requiring the Buffet Manager to constantly check for changes or having only periodic checks that may leave Patrons waiting in line unnecessarily.) This alert tells the Buffet Manager to check the numbers again to see if the counts have become high enough for each type of Hardware to let the next Party through the buffet line. If, following an alert, there is still not enough Hardware ready for the next Party, then the Buffet Manager can go back to other tasks and ignore the counts until another alert from the condition variable comes through. Once there are enough pieces of Hardware available for the next Party to pass through, the Buffet Manager ushers them to the buffet line.

  Once your Party is through the buffet you move to the table that was reserved for you by the Host(ess). After your Party departs, a Busser removes all the Hardware (and everything else) from the table and takes it to the kitchen to be washed by Dishwashers (yet more threads).

  • At the kitchen a semaphore tracks the number of Hardware pieces that are arriving to be washed.

    • If the count is >1 the Dishwashers take turns pre-cleaning the Hardware and taking them to the dish-washers to be cleaned. When a Dishwasher takes Hardware the relevant semaphore(s) is/are decremented to indicate that there are fewer pieces of Hardware remaining to be cleaned. If the count is still >1 other Dishwashers will continue to take as many pieces as they can carry and will decrement the count appropriately.

    • green

    • If the count is 0 the Dishwashers can be performing other tasks like unloading the dish-washing machines and preparing cleaned Hardware for Bussers to take back to the buffet, or they can be on a break.

  • In order to ensure that dirty Hardware never remains at the dirty station any longer than necessary a condition variable is in place to alert the Dishwashers whenever the count changes (?? up ??). green

    This way a Dishwasher won't stay on a break if there is work to be done.