Operating Systems CMPSC 473
Concurrency: Mutual Exclusion
April 08, 2021 – Lecture 22 Instructor: Bhuvan Urgaonkar
Administrative matters
• Lecture 25 will be held on April 19 instead of April 20 • April 19, 3-4:30 pm, modified zoom link on canvas
• Project 3 sample outputs and grading: •…
•
Project 4:
Administrative matters
• Will be released on April 15 (and possibly a few days sooner)
• Due on April 29
• No extensions (just before finals week)
• Starter code will be well-documented and well-structured (I am personally going over it as it is being developed)
• 2 weeks will be adequate time and you will still get a lot out of it
• You will be given an unsynchronized multi-threaded “Mapreduce-style” wordcount application; you will need to eliminate race conditions using pthrerads locks and condition variables; you will perform a simple evaluation to study how parallelism helps/hurts performance
Quiz 22.1
• Name two ways in which a page fault trap is different from other traps
• Transparent to the process
• Not indicative of a bug in the process
•
Which of these is correct?
• Data races always lead to errors
• Data races may lead to errors
• Race conditions always lead to errors
• Race conditions may lead to errors
Quiz 22.2
•
Quiz 22.3
Which of these is/are correct?
• A data race may lead to a race condition
• A race condition can only occur if there is a data race
• A race condition occurs iff there is a data race
• Race conditions are flaws but data races are not so we only need to worry about race conditions
•
Quiz 22.4
Consider a shared linked list with a return_first function of the following type:
elem *return_first () {
elem *tmp = h;
if (!h) return NULL; h = h->next;
return tmp;
}
•
• •
Consider two threads A and B concurrently invoking return_first on the list shown above.
Is there a data race?
Is there a race condition? If yes, give an example interleaving of A and B that leads to an error
•
Quiz 22.5
Recall the race condition from last lecture that led to a lost update:
Single processor
•
Now consider the same 2-threaded program running on a multi-processor:
Multiple processors
•
Has the race condition gone away?
Why are we studying concurrency in an OS course?
• On a multiprocessor, multiple portions of the OS may run concurrently!
Multiple processors
Quiz 22.6
• Based on the material on the previous few slides, I claim that multiple portions of the OS may run concurrently even on a single processor. Explain.
interrupt 1
• Infact,theOSwasthefirstsoftwarewithinwhosecontext concurrency was studied! Good discussion on this in Sec 26.7 of OSTEP
interrupt 2
WordCount
• Wordcount:countthe#occurrencesofeachuniqueword in a text file
Mapreduce-based WordCount
• A number of “mappers” will parse subsets of the input file, create (word, 1) tuples for each word they encounter and insert each such tuple into a shared in-memory buffer
• A ”reducer” thread will sum the number of tuples for each word to get the final count for that word
• Many other commonly used applications can be written in this style
• Mapreduce first developed at Google ca. late 1990s/early 2000s
Producer
Producer and Consumer
Consumer
while (true) {
/* produce an item and put in nextProduced */
while (count == BUFFER_SIZE); // do nothing buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
while (true) {
while (count == 0); // do nothing
nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE;
}
count–;
/* consume the item in nextConsumed
• Shared variables: buffer and count
• Local variables: in, out, nextProduced, nextConsumed
• What could go wrong?
• Data races may lead to: • Correctness problems
undesirable?
Why are data races
• When the outcome is different from that expected by the programmer • Performanceproblems
• “starvation”, “livelock”, “deadlock”
• Wewillgooverseveralexamples(quizzes,project4,final)
• What makes data races particularly dangerous is that they may not always result in bugs
• “Heisenbugs”
• Passing some tests may not mean much!
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