Operating Systems CMPSC 473
Concurrency: Mutex Locks
April 13, 2021 – Lecture 23 Instructor: Bhuvan Urgaonkar
• Project 3 grading:
Administrative matters
• MUCH MORE lenient than originally planned, so please RELAX!
• Automated grading based on outputs entered on provided google forms
• Ifyououtputiswithinsomeerrorrangethenyouget1,else0
• Bonus: clock
• Bonus: graphs/explanation related to Expt 2: 10%
• Ifyourscore>70%youaredone
• If not, you have the option of meeting a TA and answering their questions
Administrative matters
• Project 4 information and tips:
• To be released tomorrow (4/14)
• Well-documented and working starter code (except intended race conditions, of course)
• I have personally gone over it with Raj • What you will need to know well:
• Solving the producer-consumer problem using pthreads locks and condition variables (optionally semaphores)
• Raj will be giving an overview and answering questions at 4 pm on Friday
• Makegooduseofthissession
• Ideally, skim/run the code and read the description beforehand
• Start early!
Administrative matters
• Changed/extra instructor Ohs
• 4/13: 6-8 pm
• 4/14: TBD
Amdahl’s Law
Amdahl’s Law
Quiz 23.1
• Suppose the following curves are seen for a multi-process (MP) and a multi-threaded (MT) implementation of the same program. Which is likely to be MP and which MT?
Quiz 23.2
• Foreachofthefollowing,discussif/howitislikelytoimpactthe dependence of the completion time of a highly parallelizable multi- threaded program on #processors.
• Context switching overhead
• Quantum length
• Scheduler runtime
• TLB and cache pollution
• Efficiencyofsynchronizationprimitives
Mutual Exclusion
• Certain parts of the program that access shared state must be executed in a mutually exclusive manner
• Called “critical sections”
• All other threads are forced to wait
• Only when the thread in its critical section leaves may another enter
do {
entry section
CRITICAL SECTION exit section
REMAINDER SECTION } while (TRUE);
Mutual Exclusion/Critical Section Problem (Mutex)
• Each process’s code is divided into four sections: entry
remainder
critical
exit
• entry: synchronize with others to ensure mutually exclusive access to the …
• critical: use some resource; when done, enter the…
• exit: clean up; when done, enter the…
• remainder: not interested in using the resource
Mutex Algorithms: Entry/Exit Sections
• The code for the entry and exit sections is allowed to assume that
• noprocessstaysinitscriticalsectionforever
• shared variables used in the entry and exit sections are not accessed during the critical and remainder sections
• Usage:
Critical Section
Release the lock
Mutex lock
Lock is locked
Acquire the lock
Lock is unlocked
• Equivalently,inourbanktransferexamples: • atomic { CRITICAL SECTION }
Data race – yes
Race condition – yes
Data race – no
Race condition – yes
Data race – no
Race condition – no
Data race – yes Race condition – no
• •
Mutual Exclusion: Discussion
Proper use of mutual exclusion renders critical sections “atomic”
• A piece of code is atomic if it appears to occur instantaneously at a point of time between its commencement and its completion
Data races can be detected automatically, race conditions may not be
• Removing data races doesn’t necessarily remove race conditions
• Additionally, “blindly” removing data races can cause liveness problems – coming up soon
Important to be clear on which code sections may or may not execute mutually exclusively with respect to each other:
• Remainder vs. remainder
• Critical vs. remainder
• Critical vs. critical
•
•
Quiz 23.3
For each of the following pairs of code, identify if they may or may not execute concurrently
• Red: using shared variable x, at least one writer
• Blue: using shared variable y, at least one writer
• Black: no shared variables
Mutex Via Disabling Interrupts
• One way to achieve mutex is to disable interrupts when someone is in their critical section
• Why does this work? • Pros:
• Simple!
• Very efficient for small critical sections; extensively used inside the kernel
• Cons:
• Not generally useful
• What if a trap occurs with interrupts disabled?
• What if certain interrupts are non-maskable?
• Efficient only for really small critical sections
Mutex w/o disabling interrupts is Non-trivial
• Howaboutconstructinga“lock”usingabooleanflagasshownbelow? Doesn’t work!
while (lock == 1) ; // Do nothing, just wait // position 1
lock = 1;
….. // Critical Section lock = 0;
• Consider threads t1 and t2. Suppose t1 is interrupted at position 1
• t1waswaitinguntillock==0.Beforeitannouncesitsturn(i.e.,setslock=1),
suppose t2 gets scheduled, sees that lock is 0, and enters its critical section
• Beforet2leavesitscriticalsection(i.e.,setslock=0),supposeitsdescheduled
• Since t1 was at position 1, it will set lock = 1 and also get into its critical section
• Now, two threads are in the critical section at the same time!
Software Solutions to Mutex
• Assumptions:
• Atomic loads and stores
• Sequentially consistent memory (read on your own, not on syllabus)
• Caveat:contemporaryprocessorsdon’toffereither!
• To learn more, consider taking CSE 511 or email me and I can point you to reading materials
Peterson’s Solution
• Two process solution
• Important: LOAD and STORE instructions are atomic
• The two processes share two variables:
• int turn;
• Booleanflag[2]
• The variable turn indicates whose turn it is to enter its critical section.
• The flag array is used to indicate if a process is ready to enter its critical section. flag[i] = true implies that process Pi is ready
Algorithm for Process Pi while (true) {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j);
CRITICAL SECTION flag[i] = FALSE;
}
REMAINDER SECTION
while (true) {
flag[0] = TRUE;
turn = 1;
while(flag[1] && turn == 1);
CRITICAL SECTION flag[0] = FALSE;
REMAINDER }
while (true) {
flag[1] = TRUE;
turn = 0;
while(flag[0] && turn == 0);
CRITICAL SECTION flag[1] = FALSE;
REMAINDER }
Another look at Peterson’s Mutex Algorithm
while (true) {
flag[0] = TRUE;
turn = 1;
while ( flag[1] && turn == 1);
P0’s CRITICAL SECTION flag[0] = FALSE;
P0’s REMAINDER SECTION }
Acquiring lock
while (true) {
flag[1] = TRUE;
turn = 0;
while ( flag[0] && turn == 0);
P1’s CRITICAL SECTION flag[1] = FALSE;
P1’s REMAINDER SECTION }
Releasing lock
Proof: Mutex
• P0 and P1 can never be in their critical sections together
• When P0 is in its critical section, either
• flag[1]==FALSE
• i.e.,P1hasleftitsCS
• Orturn==0
• i.e., P1 in its entry section but has let P0 go ahead and, therefore, is unable to proceed beyond its entry section till P0 comes out of its critical section
Note on Edgar W. Dijkstra and his Solution
• Firsttodefinephrasesmutualexclusion, critical section, remainder section
• Later invented semaphores (coming shortly)
• Anotherfamouscontribution:ShortestPath
Algorithm in graphs
• Turing award in 1972
• Wasaprof.atUnivofTexas
• Colorfulperson(combative,rarelyused computers), read more online
Leslie Lamport and his Solution
• Bakery algorithm
• Seminalworkonfaulttolerance
• Invented LaTeX
• Dijkstra prize in 2005
• Worked at DEC, now at MSR
• Turing award 2014
Bakery Algorithm
NO CRITICAL SECTION FOR YOU!!
Bakery Algorithm
Hardware Support for Mutex
• Modern machines provide special atomic hardware instructions
• e.g., #1: test memory word and set value
• e.g.,#2:swapcontentsoftwomemorywords
• “Easy” to devise locks using these instructions compared to using only LOADs/STOREs
TestAndndSet Instruction
Definition:
boolean TestAndSet (boolean *target) {
boolean rv = *target; *target = TRUE; return rv:
}
Mutex lock using TestAndSet
Shared boolean variable lock, initialized to false Solution:
while (true) {
while ( TestAndSet (&lock ));
/* do nothing
}
// critical section lock = FALSE;
// remainder section