Mutexes: Why you need them…
Attribution: I thank Jerry Cain at Stanford for inspiring the following content
Airline Ticket Agent example to illustrate the need for a mutex
Each of 10 ticket agents tries to sell airline tickets until 100 total tickets are sold.
static int numTickets = 100;
static void agent(size_t id) {
while(numTickets > 0) {
numTickets–; // sell a ticket
cout << oslock << “Sold a ticket…” , id, numTickets << endl << osunlock;
if (shouldTakeBreak()) { // introduce randomness to influence thread scheduler
takeBreak();
}
}
}
Problem:
numTickets– is not atomic. What if a thread commits to sell a ticket by going into the while loop and gets swapped off the processor before completely executing numTickets–; Thread has not flushed out the new value to the global variable: numTickets;
numTickets– may be realized by 3 assembly instructions.
While loop test is separated from the decrement.
int main() {
thread agents[10];
for ( size_t i = 0; i < 10; i++) {
agents[i] = thread(agent, 101+i);
}
for (thread &t : agents) {
t.join();
}
return 0;
}
Solution:
Treat the numTickets– as a transaction. It is a shared global with a race condition amongst many threads. A mutex can protect this critical region. So, rewriting the agent(), we have:
static int numTickets = 100;
static mutex numTicketsLock;
static void agent(size_t id) {
while(true) {
numTicketsLock.lock(); // lock the bathroom door
if(numTickets == 0) break; // leaving the locked bathroom through the window
numTickets–; // sell a ticket
cout << oslock << “Sold a ticket…” , id, numTickets << endl << osunlock;
numTicketsLock.unlock();
if (shouldTakeBreak()) { // introduce randomness to influence thread scheduler
takeBreak();
}
}
numTicketsLock.unlock(); // in case the thread left through the window
}
Dining Philosophers example
Deadlock
Semaphores – Permission Slips
int main() {
thread philosophers[5];
for (size_t i = 0; i < 5; i++) {
philosophers[i] = thread(philosophize , i);
}
for(thread &t : philosophers) {
t.join();
}
return 0;
}
Now, for the threaded function. We could model the forks as an array of booleans or we could realize that fork acquisition can simply be modeled by mutexes.
static mutex forks[5];
static void philosophize(size_t id) {
for(size_t i = 0; i < 3; i++) {
think(id); // a random sleep call
eat(id);
}
}
static void eat(size_t id) {
size_t right = id;
size_t left = (right + 1) % 5;
forks[right].lock();
forks[left].lock();
cout << oslock << “…” , id << endl << osunlock;
sleep_for(…);
forks[right].unlock();
forks[left].unlock();
}
Problem:
Above solution has deadlock
Sorry, the comment form is closed at this time.