DRAFT |
Thread Synchronization Primitives
Primary Include: SDL_mutex.h
Other Includes: SDL_thread.h, SDL_stdinc.h, SDL_error.h
Contents
Introduction
Functions in this group provide thread synchronization primitives for functions in the Thread Management group.
There are 3 primitives available in SDL, the:
Mutex
If you understand the phrase "mutually exclusive" then you already know the basic idea of a mutex. Mutex, or mutual exclusion, functions are used to protect data structures in multi-threaded processes. By coordinating multiple threads using or calling the same data source 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 based on the mutex algorithm? / based on the OS? 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 anyone waiting for the restroom may then attempt to get the key from the clerk. Eventually each waiting person will get their turn, but the restroom cannot be used by more than one person at a time in this way. (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 count. They count up from 0 or down from a preset starting point. In both cases the critical value is 0. For a semaphore counting up, 0 indicates that there is nothing available to be used/worked on. For a semaphore counting down, 0 indicates that something has run out. Exactly how to use or interpret a semaphore depends upon the application. Semaphore functions are used to determine whether a data structure is available to be allocated to a thread, and then potentially permits multiple threads access to the data (if the count is >1). (Often the individual data structures are protected directly by a mutex and the semaphore acts as a 2nd layer of regulation.)
Note that a semaphore can behave much like a mutex if the max count is set to 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.
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 (eg: 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, 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 check stands that can be accessed by all the threads (customers) simultaneously.
A mutex protects each data structure (check stand) from being accessed by more than one thread (customer) at a time.
When the store opens in the morning, the semaphore count indicates the total number of check stands (let's say 8). It remains unchanged until a customer enters the line and checks the semaphore to see if there is an open check stand. Since there are 8 open, and the customer (thread) 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. The next customer to enter the line will see that there are 7 available check stands and can repeat the process. When the 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 semaphore becomes very handy. Customers in excess of 8 continue to wait in line until the semaphore indicates a positive number. Then, that number of customers can leave the line and enter an available check stand. This allows for the possibility that more than one check stand may become simultaneously available, allowing more than one customer to leave the line and head for a check stand at the same time, and moving the line along faster. The individual mutexes at each check stand prevent multiple customers from leaving the line and trying to process their transactions through the same check stand. Whoever locks the mutex first gets to use that check stand and the other customer (thread) must find the other available check stand(s) before completing their transactions. 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 structures available for processing).
- The Dryers (threads) are the people that need to work on the cars (data) next.
- The semaphore keeps track of how many cars are waiting.
Under normal circumstances the Dryers dry cars as they come out of the car wash. In most cases the semaphore count would not exceed 1. However, if something slowed down the drying process (ex: the car wash became very busy and temporarily ran out of dry towels; a number of small cars followed a number of big cars; the drying crew was smaller or slower than usual...) it is possible that a backlog of cars to be dried could form. In that case the semaphore (a big digital display perhaps) would continue to increment (count up) as cars exited the car wash, and would decrement (count down) as cars were taken for drying.
Condition Variable
Condition variables in SDL are used to monitor the status of a data structure or structures and alert waiting functions when there has been a change. (The "variable" that they monitor is the "condition" of another variable.) They do not protect directly like mutexes do (and semaphores can if their max count is 1). Instead they coordinate threads by monitoring for changes and alerting 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.
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, just that a message has been received. You have to then look for the details of the message yourself. In this analogy the condition variable is the alert telling you that there has been a change in the number of messages in your inbox (the data structure being monitored). You are like a thread waiting for information in the inbox. It is useless to keep getting out your phone and checking if there is nothing there. Having an alert tell you as soon as something has arrived saves you time and energy and ensures that you know the moment the message becomes available instead of 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.
Here is an analogy that utilizes all three primitives together:
Imagine a buffet-style restaurant. You, the customer, (one of the threads) are waiting 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) (a thread). (S)He asks for the number of individuals in your party and checks to see if there is an available table. (It wouldn't do to send you through the buffet line only to have you find nowhere to sit.) green
Semaphores track the number of available tables of each size.
- They are decremented (reduced) from the maximum number of tables of each size as patrons are seated.
- They are incremented (increased) up to the maximum number as patrons leave and the tables are cleaned for the next guests.
A mutex protects the count from being changed by more than one restaurant worker at a time. (ex: If the Host(ess) is changing the number then a Busser cannot be simultaneously changing the number.)
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 the next Party can be seated.
The Host(ess) checks the appropriate semaphore for the table size needed for your party. If the number is 0 you are requested to wait. If the number is >1 you are allowed to enter the buffet line. <<Color2(green,Can a semaphore count be protected by a mutex? How is that handled - if the
In addition, the Host(ess) also 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.
Once a table is available you are ushered through to the next phase. The next person you meet is the Buffet Manager (another thread). (You'll have to be a little flexible with the analogy at this point.) One of the Buffet Manager's jobs is to ensure that no one passes through the buffet line unless a plate, cup, spoon, fork, and knife (the hardware) is available for them. (We're not going to address the actual food here, but it could work similarly to the hardware.) Unfortunately (s)he is not able to see the stacks of hardware at the buffet from where (s)he greets the patrons. In addition, there must be enough available to send each entire party through together.
- There are 3 categories of people who interact directly with the hardware -
- Patrons who take hardware to use,
- Bussers who bring clean hardware back,
- and the Buffet Manager who ensures that patrons will be able to find the hardware they will need to eat with before sending a party through the buffet line.
To prevent confusion, there is a mutex protecting the hardware from being changed by more than one person at a time (in this case it could be as simple as the physical space to access the hardware being limited to the size of one person).
- When a Busser adds hardware (s)he increments (increases) the count for that type of hardware by the number of pieces that are returned.
- When a Patron takes a piece of hardware to use, the count is decremented (decreased) for that type of hardware.
- The Buffet Manager does not send a group through the buffet line if there aren't enough pieces of all types of hardware for each member of the party to be able to take one piece.
In order to know when it is OK to send a party through the buffet the Buffet Manager must check the semaphores? / some other quantity-tracking data structure? that are monitoring the available count of each type of hardware. Because of the mutex 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 back on current, accurate counts.
In order to make the process of checking as efficient as possible a condition variable is set up to alert the Buffet Manager whenever a hardware count changes, rather than requiring the Buffet Manager to constantly check for changes. This alert tells the Buffet Manager to check the numbers again to see if the count has 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 again. Once there are enough pieces of hardware available for the next party to pass through, the Buffet Manager ushers them to the buffet line.
