Synchronization

Learning outcomes:

• Explain what race conditions and critical sections are, and why mutual exclusion is needed
• Describe software and hardware solutions to mutual exclusion, and the locks used on multiprocessor systems
• Explain how semaphores and monitors synchronize processes and threads, using everyday examples
• Apply synchronization ideas to classic problems, such as the bounded buffer, readers and writers, and dining philosophers

Would you like to download my PowerPoint to follow along?

• Synchronization as a Concept
• Synchronization means coordinating processes and threads that run at the same time
• They may compete for the same resource, get in each other's way, or work together
• Concurrent: more than one thread exists at once. Asynchronous: they run on their own, and only sometimes need to coordinate
• Like coworkers sharing one printer, one kitchen, or one shared document
• Race Conditions
• A race condition happens when the result depends on who gets there first
• Everyday examples:
• Two people buy the last concert ticket at the same moment, and the site sells it twice
• Two ATMs take money from the same account at once, and the balance ends up wrong
• Two people edit the same cell in a shared spreadsheet, and one change disappears
• A context switch can happen at any moment, even in the middle of updating a value
• The fix: make sure only one process changes shared data at a time
• Example of a Critical Section
• Two cars approach an intersection, one on Road A and one on Road B
• If they get there at the same time, they crash
• The intersection is part of both roads: a critical section. Only one car should be in it at a time
• Traffic lights and stop signs provide mutual exclusion
• Mutual Exclusion
• Only one process at a time can use a shared resource
• Like a single-stall bathroom with a lock: one person inside, and everyone else waits
• Without it, shared data can be left half-changed (inconsistent)
• Others wait until the resource is unlocked, so access happens one at a time
• Waits must stay reasonable, or nothing gets done
• This is the most basic synchronization rule
• Critical Section
• A critical section is the part of a program that uses a shared resource
• Most code is safe to run at the same time as other code, but the parts that change shared data must be protected
• Only one thread can be in its critical section at once
• Keep critical sections short. If a thread gets stuck inside one, everyone else is stuck waiting
• Critical Sections in Two Processes
• Diagram: two processes, P1 and P2, each have a private variable y and share a variable x. Each one's critical section changes x, then copies it into y. If both run their critical sections at the same time, x can end up wrong
• Example of Critical Sections
• Shared resource: a printer buffer, with two processes
• The producer makes a character and places it in the buffer
• The consumer removes a character from the buffer and uses it
• Placing and removing are critical sections: they must not happen at the same instant
• Like a print queue: your computer adds jobs, and the printer takes them out
• The Critical Section Problem
• Every process using a shared resource must follow the same rules (a protocol)
• A good protocol gives:
• Mutual exclusion: only one process in the critical section at a time
• Progress: if no one is inside, someone waiting gets to go in
• Bounded waiting: no process waits forever
• Like a four-way stop: one car at a time, someone always goes, and everyone gets a turn
• Definition of a Critical Section Protocol
• Entry section: check whether anyone else is in the critical section. If so, wait. If not, put up a "busy" sign and go in
• Critical section: use the shared resource
• Exit section: take the sign down, so someone waiting can go in
• Like flipping the "occupied" sign on a bathroom door
• Synchronization Solutions
• Software solutions: rules the processes follow, using shared variables
• Hardware solutions: special instructions built into the processor
• Faster, and they make the software simpler to write
• Operating system tools build on these: locks, semaphores, and monitors
• Software Solutions
• Dekker's algorithm: the first correct solution for two threads
• Each thread raises a flag to say it wants in. If both want in, a "favored" thread goes first, and the favor takes turns
• It took several broken tries to get right, which shows how hard this is
• Peterson's algorithm: a simpler version of the same idea
• Lamport's bakery algorithm: works for any number of threads (Leslie Lamport: The Writings of Leslie Lamport)
• Like a deli counter: take a numbered ticket, and the lowest number goes next
• All three waste CPU time by checking again and again (busy waiting)
• Disabling Interrupts
• Turn off interrupts so the running thread can't be interrupted inside its critical section
• Only works with one processor. On a multi-core system it only stops one core, and the others keep going (Week 4)
• Like putting your phone on Do Not Disturb: it silences your phone, not your roommate's
• Can cause deadlock if the thread waits for I/O, because the I/O interrupt never gets through
• Rarely used today
• Test-and-Set Instruction
• A special instruction that checks a value and changes it in one step that can't be interrupted (atomic)
• Like checking that a seat is empty and sitting down in one move, so no one can slip in between
• Test-and-set: read a lock's value, and set it to "taken" at the same time
• Today's processors offer compare-and-swap, and Linux builds its locks on it (Linux kernel documentation: Generic Mutex Subsystem)
• The software still has to use these instructions correctly
• Semaphores
• A semaphore is a counter that controls access to a resource, like a traffic light
• Only two operations can change it:
• Wait (P): if the count is above 0, subtract 1 and go. If it's 0, wait in line
• Signal (V): add 1, and let the next waiting process go
• P and V come from Dutch words chosen by Edsger Dijkstra, who invented semaphores (E.W. Dijkstra: Cooperating sequential processes (EWD 123))
• The OS provides semaphores, so programs don't have to build their own (Linux manual page: sem_overview)
• Binary and Counting Semaphores
• Binary semaphore: 0 or 1, so one process at a time
• Like the single bathroom key at a gas station: take it, use it, and bring it back
• Counting semaphore: 0 or more, so up to that many processes at once
• Like a parking garage sign showing spaces left. When it reaches 0, the next car waits
• Or a print room with 3 printers: up to 3 jobs print at once
• Binary semaphores give mutual exclusion: wait before the critical section, and signal after
• Thread Synchronization with Semaphores
• Semaphores can also tell other threads that something happened
• Producer and consumer:
• The producer makes a value, then signals
• The consumer waits for that signal before reading the value
• The producer can't replace the value until it's been used
• Like a restaurant: the cook puts a plate in the window and rings the bell, and the server waits for the bell
• Monitors
• A monitor bundles shared data with the only procedures allowed to use it
• Like a room with one door and a guard: only one person inside at a time, and everyone else waits in line
• Mutual exclusion is enforced automatically at the door
• A thread inside can wait for something to happen (a condition variable), stepping out so someone else can go in
• Easier to use correctly than semaphores, because the rules are built in. Languages like Java build monitors in
• Synchronization Case Studies
• Classic problems that test a synchronization solution:
• Bounded buffer (producer and consumer)
• Readers and writers
• Dining philosophers
• Each one shows up in real systems you use every day
• Bounded-Buffer Problem
• A producer adds items to a buffer with a fixed number of slots, and a consumer takes them out
• Real examples:
• A print queue: your computer adds jobs, and the printer takes them out
• Video streaming: your device downloads ahead into a buffer while the player uses it up
• The producer waits if the buffer is full, and the consumer waits if it's empty
• Three semaphores solve it: a binary one to protect the buffer, one counting the full slots, and one counting the empty slots
• Readers and Writers Problem
• Many processes read shared data, and some write (change) it
• Any number of readers can read at the same time
• A writer needs the data to itself
• Like a class schedule posted online: thousands of students can view it at once, but while the registrar updates it, nobody should see a half-changed version
• Read/write locks, below, are built for this
• Read/Write Locks
• A read/write lock has two modes:
• Shared (read) mode: many readers hold it at once
• Exclusive (write) mode: one writer holds it, and nobody else
• Like a museum painting: crowds can look at it together, but a restorer works on it alone, with the room closed
• Linux uses read/write locks inside the kernel (Linux kernel documentation: Lock types and their rules)
• Locks on Multiprocessors
• Spin lock: keep checking until the lock is free
• Like standing at the bathroom door and trying the handle over and over
• Wastes CPU time, but reacts the instant the lock is released. Good for very short waits (Linux kernel documentation: Locking lessons)
• Sleep/wakeup lock: waiting processes sleep, and the lock holder wakes the next one when it's done
• Like sitting in a waiting room until your name is called
• Spin, then sleep: spin for a moment, then sleep if it's still taken. Linux's mutexes do this
• The Thundering Herd
• If every waiting process wakes up when a lock is released, they all rush for it, but only one can win
• Like a waiting room where everyone jumps up when one name is called
• The rest go back to sleep, after wasting time and CPU
• Sleep/wakeup locks avoid this by waking just the next process in line
• Linux's futexes let programs lock and unlock without calling the kernel at all, unless they actually have to wait (Linux manual page: futex)
• Dining Philosophers
• Five philosophers sit at a round table, with one chopstick between each pair
• Each one needs both chopsticks next to them to eat
• If everyone picks up their left chopstick at the same time, nobody can ever get a right one, and everyone waits forever
• That's deadlock, next week's topic (Week 7)
• It models any system where processes need more than one shared resource at once
• Message Passing and Synchronization
• Sending messages between processes also needs synchronization (Week 2)
• Asynchronous: the sender leaves the message in a mailbox and keeps going. The receiver waits until a message arrives
• Like sending a text message
• Synchronous: both processes take part at the same time, over a direct channel
• Like a phone call
• Synchronization and Crashes
• A bank transfer must take money out of one account and add it to another, as one atomic transaction
• If the system crashes halfway, recovery must either finish the transaction or undo it
• Systems use transaction logs and checkpoints for this, covered in the File Systems week
• Most real systems use both: logs for everyday recovery, and checkpoints for disasters
• Synchronization You've Seen
• Print queues: many computers share one printer, one job at a time
• Google Docs: several people type at once, and the system merges the changes so no one's work disappears (Google: What's different about the new Google Docs: Conflict resolution)
• Ticket and shopping sites: the last ticket or last item can only be sold once
• Databases lock records, so two cashiers can't sell the same item at the same time
• Your own computer: the OS uses locks thousands of times every second (Linux kernel documentation: Locking)

Suggested Activities and Discussion Topics:

• Discussion: two people try to buy the last concert ticket at the same moment. How is that a synchronization problem, and how could a system solve it?
• Activity: act out Lamport's bakery algorithm. Hand out numbered slips of paper, and have people take turns at a "critical section" (like writing on the whiteboard) in ticket order. What happens if two people get the same number?
• Activity: find a race condition in everyday life (a shared fridge, a group chat, a shared spreadsheet, a parking spot). Describe what goes wrong, and how a lock, semaphore, or other rule would fix it
• Activity: try the dining philosophers with 5 people and 5 pens around a table. Each person needs 2 pens to "eat" (write their name). Can you get stuck? What rule would prevent it?
• Discussion: a parking garage sign says "12 spaces left". How is that like a counting semaphore? What happens when it reaches 0?

Would you like to see some more classes? Click here