Lecture Topics
• Synch issues
• Conservative synchronization design
• Semaphores
• Reader/writer synchronization
• Selecting a synchronization mechanism
ECE391 EXAM 1
• EXAM 1 – March 2 (Tuesday); 6:00pm – 8:00pm – Detailed instructions will be provided soon
• Conflict Exam
– Deadline to request conflict exam: Friday February 26
(by email to: kalbarcz@Illinois.edu)
• Exam 1 Synchronous Review Session
• (potentially in collaboration with HKN)
– Tentative Saturday February 27
– Precise information will be provided the next week
ECE391 EXAM 1
• Topics covered by EXAM 1
– Materia covered in lectures (Lecture1 – Lecture10) • x86 Assembly
• C-CallingConvention
• Synchronization
• Interrupt control (using PIC)
– Material covered in discussions – MP1
• NO Lecture on Tuesday, March 2
Another Philosophy Lesson
• Synchronization issues
– five hungry philosophers
– five chopsticks
• Protocol
– take left chopstick (or wait)
– take right chopstick (or wait)
– eat
– releaserightchopstick
– release left chopstick
– digest
– repeat
problems? deadlock!
Another Philosophy Lesson (cont.)
• How about the following protocol?
– take left chopstick (or wait)
– if right chopstick is free, take it
– else release left chopstick and start over – eat
– release right – release left – digest
– repeat
• Does this work? © Steven Lumetta, Zbigniew Kalbarczyk
ECE391
Another Philosophy Lesson (cont.)
• What if all philosophers act in lock-step (same speed)?
left left left left left release release release release release
left left left left left release release release release release left left left left left
(ad infinitum)
• Called a livelock
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Another Philosophy Lesson (cont.)
• To solve the problem, need (partial) lock ordering – e.g., call chopsticks #1 through #5
– protocol: take lower-numbered, then take higher-numbered – two philosophers try to get #1 first
– can’t form a loop of waiting philosophers
– thus someone will be able to eat
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Conservative Synchronization Design
• Getting synchronization correct can be hard – it’s the focus of several research communities
• On uniprocessor
– mentally insert handler code between every pair of adjacent instructions
– ask whether anything bad can happen
– if so, prevent with CLI/STI
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
•
Conservative Synchronization Design (cont)
On a multiprocessor
– consider all possible interleavings of instructions
– amongst all pieces of (possibly concurrent) code
– ask whether anything bad can happen
– if so, use a lock to force serialization
– good luck!
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
• •
Conservative Synchronization Design (cont)
What does “bad” mean, anyway?
A conservative but systematic definition if any data written by one piece of code
are also read or written by another piece of code
these two pieces must be atomic with respect to each other
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Conservative Synchronization Design (cont)
not shared
• What variables are shared?
• step 0: ignore the parts that don’t touch shared data
• step 1: calculate read & write sets
• step 2: check for R/W, W/W relationships
– must be atomic!
• step 3: add lock(s) to guarantee atomic execution (pick order if > 1 locks)
• step 4: optimize if desired
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Conservative Synchronization Design – Example Code Analysis
• Read/write sets – move
reads position, velocity writes position
reads position
reads velocity
reads mass, velocity writes velocity writes mass
Lock1
– dist
– speed
– momentum
– stop
– change_mass
Lock2
move dist speed stop momentum
Lock3
change_mass
Edges in graph imply need for atomicity
Conservative Synchronization Design – Example Code Analysis (cont)
• Each lock = circle in graph
• All edges must be contained in some circle
• One lock suffices, but prevents parallelism (performance)
• Could use three (as shown above);
then MUST pick a lock order!
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Role of Semaphores
• Recall our philosophical friends
• Five philosophers
• Three pairs of chopsticks (one “lock” per pair)
• Problem: how do you get a pair?
• Option 1: walk around the table until you find a pair free – lots of walking
– other people may cut in front of you
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
•
Role of Semaphores
Option 2: pick a target pair and wait for it to be free – other pairs may be on the table
– but you’re still waiting hungrily for your chosen pair
Instead, use a semaphore! – an atomic counter
– proberen (P for short, meaning test/decrement) – verhogen (V for short, meaning increment)
– Dutch courtesy of E. Dijkstra
•
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
• When are semaphores useful?
• Fixed number of resources to be allocated dynamically – physical devices
– virtual devices
– entries in a static array
– logical channels in a network
• Linux semaphores have a critical difference from Linux spin locks
– can block (sleep) and let other programs run (spin locks do not block)
– thus must not be used by interrupt handlers
– used for system calls, particularly with long critical sections
Semaphores
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Linux Semaphore API
void sema_init (struct semaphore* sem, int val);
Initialize dynamically to a specified value
void init_MUTEX (struct semaphore* sem);
Initialize dynamically to value one (mutual exclusion)
void down (struct semaphore* sem);
Wait on the semaphore (P)
void up (struct semaphore* sem);
Signal the semaphore (V)
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Linux Semaphore API (cont.)
• If critical section needs both semaphores and spin locks – Get all semaphores first!
– Linux expects not to be preempted while holding spin locks – Semaphore code voluntarily relinquishes processor
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Reader/Writer Problem: The Philosophers and Their Newspaper
• Philosophers like to read newspaper
– each philosopher reads frequently, taking short breaks between
– multiple philosophers may read at same time
• different sections or or just over another’s shoulder
• Paper carrier delivers new paper – once per day (infrequently)
– must change all sections at once
• Reader/writer synchronization supports this style – allows many (in theory infinite) readers simultaneously – at most one writer (and never at same time as readers)
• What if newspaper is always being read? starvation!