COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes
Winter 2022
About these reading notes
Chapter 28: Locks
Copyright By PowCoder代写 加微信 powcoder
28.1:Locks:TheBasicIdea………………. 28.2:PthreadLocks…………………..
28.3:Buildingalock ………………………………… 4 28.4:Evaluatinglocks ……………………………….. 4 28.5:ControllingInterrupts …………………………….. 4 28.6:AFailedAttempt:JustUsingLoads/Stores …………………… 4 28.7:BuildingWorkingSpinLockswithTest-and-set…………………. 5 28.8:Evaluatingspinlocks……………………………… 5 28.9:Compare-and-swap ……………………………… 5 28.10:Load-linkedandstore-conditional ………………………. 6 28.11:Fetchandadd ………………………………… 6 28.12:TooMuchSpinning:whatnow?………………………… 6 28.13:Asimpleapproach:Justyield,baby ……………………… 6 28.14:UsingQueues:Sleepinginsteadofspinning ………………….. 7 28.15:DifferentOS,DifferentSupport ………………………… 7
28.16: Two-phase locks . . . . 28.17:Summary……..
Chapter 30: Condition Variables
……………………………. 7 ……………………………. 7
…………….. 2 …………….. 3
……………………………. 8
30.1: Definition and routines .
30.2:Theproducer/consumer(boundedbuffer)problem . . . . . . . . . . . . . . . . . . . 8
ABrokenSolution ………………………………. 8 Better,butstillbroken:While,notif………………………. 9 TheSinglebufferproducer/consumersolution…………………. 9 Thecorrectproducer/consumersolution ……………………. 9
30.3:Coveringconditions ……………………………… 9
Chapter 32: Common concurrency bugs 9 32.1Whattypeofbugsexist? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 32.2Non-deadlockbugs ……………………………. 10 32.3 Deadlock bugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
About these reading notes
These are my own personal reading notes that I took (me, Franklin) as I read the textbook. I’m pro- viding these to you as an additional resource for you to use while you’re reading chapters from the textbook. These notes do not stand alone on their own — you might be able to get the idea of a chap- ter while reading these, but you’re definitely not going to get the chapter by reading these alone.
These notes are inconsistently all of the following:
• Mesummarizingpartsofthetext.
• Mecommentingonpartsofthetext.
• Measkingquestionstomyselfaboutthetext.
– …andsometimesansweringthosequestions.
The way that I would expect you to read or use these notes is to effectively permit me to be your in- ner monologue while you’re reading the textbook. As you’re reading chapters and sections within chapters, you can take a look at what I’ve written here to get an idea of how I’m thinking about this content.
Chapter 28: Locks
28.1: Locks: The Basic Idea
• Theauthorswritethisstatement“…andthusexactlyonethreadholdsthelockandpresumably is in a critical section.”
Why would they write “presumably” here? Isn’t a lock being locked a guarantee that a thread is in a critical section? Presumably means that there might not be a thread in the critical section. Did the thread lose the key?
• Ifyouwantadifferentanalogyforlockshere,thinkofamutexlockasa“talkingstick”;onlythe person who has the talking stick (has acquired the lock) is permitted to talk (enter the critical section). When the person who has the talking stick is done, they give it to the next person.
– Take this analogy of a talking stick and think about the previous question, e.g., “presum- ably someone has the talking stick and is talking”.
You might want to go back and remind yourself about what a thread is, and some of the issues related to threading (specifically critical sections).
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
• “Locksprovidesomeminimalamountofcontroloverschedulingtoprogrammers.”
The authors provide an explanation of this immediately below the statement, but make sure that you can convince yourself that this is true.
– Expandonthisidea:isthispreemptiveornon-preemptive? 28.2: Pthread Locks
• Thinkaboutthisideaofcourse-grainedvsfine-grainedlockingspecificallyintermsofalinked list: coarse-grained locking would mean that you’re putting a lock on the entire list itself, some- thing like:
struct LIST { pthread_mutex_t lock; struct NODE *head; // other stuff
Any time any thread wants to do anything to the list, you’d have to lock the entire list, so only one thread could ever change the list at a time.
Fine-grained locking would be more like putting a lock on every node in the list:
struct LIST {
struct NODE *head; // other stuff
struct NODE {
pthread_mutex_t lock; struct NODE *next; // other stuff
Any time a thread wants to do something with a specific node in the list, it would lock just that node. Other threads would be free to modify other parts of the list concurrently.
– OK, now expand on this idea in terms of a tree structure, with coarse-grained locking, where would you put the mutex? With fine-grained locking, where would you put the mu- texes?
• Remember that code in chapter 2 that had a global counter? Yeah, go ahead and add a lock to that. It’s figure 2.5, and you can find the source code for the code on GitHub.
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
28.3: Building a lock
• “Weneedhardwaresupport.”THEEND.
28.4: Evaluating locks
• Hey look, it’s this term “fairness” again! Where have you seen that before? What was the con- text?
– Hey look again, it’s this term “starve”! Where have you seen that before? What was the context?
– It’salmostlikethesetwocontextsarerelatedorsomething. 28.5: Controlling Interrupts
• “Compared to normal instruction execution, code that masks or unmasks interrupts tends to be executed slowly by modern CPUs.”
– Apointofclarification:maskingandunmaskingheremeansturningonandoff.
– Withthatinmind,theimplicationisthatmodernCPUsallowprogramstodothat,justthat
those programs run slowly. Is this real?
• TheauthorsclaimanOSmightturnoffinterruptsasaprimitivelockingmechanism.Thismeans
a couple of things:
1. Operatingsystemsaremulti-threaded.
2. Theydon’tnecessarilyhaveaccesstolibrarieslikePthreads.
Why wouldn’t an OS use a library like Pthreads?
28.6: A Failed Attempt: Just Using Loads/Stores
• Think about this concept of spin-locking in terms of what happened with pure round-robin when I/O was added, is the idea here any different?
– What was the solution for “fixing” this issue with round-robin? Can you use something similar to “fix” the performance problem here? (Mutual exclusion is a problem that’s not directly related).
• Reallyconvinceyourselfaboutwhat’shappeninginfigure28.2(onpg6)intermshowthisflag- based approach does not provide mutual exclusion.
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
28.7: Building Working Spin Locks with Test-and-set
• Ohgosh,there’san“aside”herethat’safullpage.
– Reallyconvinceyourselfthatthis“locking”and“unlocking”actuallyworkscomparedto figure 28.2.
– “Ofcourse,thislineofworkbecamequiteuselesswhenpeoplerealizeditismucheasier to assume a little hardware support…” Uh, yeah, it’s always easier when you let someone else do the hard work.
• What specific part of what’s happening with test-and-set is fundamentally different from the load and store idea in figure 28.2?
– Thinkaboutthisspecificallyinthesenseoffigure28.3whichinfuriatinglyspans2pages and has an “aside” in the middle of it. Figure 28.3 starts on pg 6, then resumes on pg 8.
28.8: Evaluating spin locks
• Trytothinkabouttheassessmentofperformancehereintermsofround-robinwithoutI/Osup- port. Are spin locks and plain round-robin suffering the same problems?
• SpinningononeCPU:wastedcycles.Spinningon𝑛CPUs?Perfection.
– What?Why?Whywould𝑛threadson𝑛“CPUs”(whereCPUhereisanyofCPU,core,thread-
ing unit) be OK for spin locks?
• The authors make an assertion that spin locks aren’t fair, but I feel like their explanation isn’t good enough; wouldn’t any locking mechanism be unfair if the current thread that holds the lock never gives it up?
– I’ll expand on their behalf: the basic idea of fairness here is more that if the threads were guaranteed to all give up their lock, eventually all of them would get access to it. That guarantee isn’t true with spinlocks. If we have 𝑛 threads, we have no guarantee about when or how the threads acquire the locks (we’re at the whim of the scheduler).
28.9: Compare-and-swap
• Convinceyourselfthatthisisactuallydifferentfromtestandset.(itis,Ipromise)
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
28.10: Load-linked and store-conditional
• Theauthorstellyoutostophere(midwaythroughpg11)andthinkabouthowyoumightbuild your own spin lock with the load-linked and store-conditional primitives. Do it!
– Theygiveananswerinfigure28.6. 28.11: Fetch and add
• THISISANATOMIC++OPERATION!Awwyiss.
• Consideringfigure28.7andthedescriptionoftheticketlock,whydoesn’ttheunlockfunction
also have to use the fetch and add instruction? Is mutual exclusion still guaranteed?
• OK, so here we’ve got something fair, “one important difference with [the ticket lock] solution
versus our previous attempts: it ensures progress for all threads.”
– Thinkreallyhardhere:we’retalkingaboutticketsandcountersandincrements,butwe’re implicitly talking about a data structure. What is the data structure? Hint: it’s like a list. But, uh, not just a list. It’s a list with an order. Yeah, that’s a good hint.
28.12: Too Much Spinning: what now?
• We’reagaintalkingaboutwastedtime.It’slikewekeephavingthesesameproblemsoverand over again. First with round-robin, now this. It’s ALMOST LIKE THEY ARE RELATED SOMEHOW.
28.13: A simple approach: Just yield, baby
• Yeah, OK, the thread that doesn’t get the lock should just give up its timeslice. OH HEY. IT’S AL- MOST LIKE THE PROBLEMS THAT WE SAW WITH ROUND-ROBIN ARE RELATED TO THIS PROBLEM SOMEHOW.
• The authors mentioned this directly before, but are implicitly mentioning it again here: “the yielding essentially deschedules itself”; locking mechanisms give the programmer (and the user space program) some amount of control over scheduling.
• Manythreadsyieldinghasissueswithcontextswitching:OHHEY,rememberhowwecouldset timeslices with scheduling? Remember how making that really small had problems with context switching?
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
28.14: Using Queues: Sleeping instead of spinning
• OOOOHHHH HEEEEEYYYYYY. It’s almost like round-robin and thread locking have similar prob- lems. Are they related to each other in some way? Remember what we did in round-robin when I/O was initiated?
• The authors describe two system calls here: park and unpark, but they’re Solaris (SunOS) system calls. Does Linux have anything similar? What about macOS? Windows? On Linux you can try searching with man -k.
• “Second,weuseaqueue”(thisisonthebottomofpg17).
– IT’SALMOSTLIKESCHEDULINGISRELATEDTOTHISSOMEHOW.
• Whatdoyouthinkthis“somethingbad”isthat’smentionedonpg18intermsofreleasingthe guard lock after park?
– Rememberhowtheauthorstalkedabout“presumably”there’sathreadinthecriticalsec- tion?
28.15: Different OS, Different Support
• Thinkingbacktotheprimitivesdescribedbefore,whatisafutex?
– AndréAlmeidawroteagreatblogpostthatdescribestheideaofafutexinLandinganew
syscall, part 1: What is a futex?
28.16: Two-phase locks
• Sometimes doing two things is better than doing one thing. What kind of circumstance does spinning work better than sleeping? (This is described earlier in the chapter).
28.17: Summary
• The summary here brings an important point: for user-space locking to work, there needs to
be both hardware and OS support.
Chapter 30: Condition Variables
• We skipped chapter 29 “Locked Data Structures”. If you want to see locks in practice, feel free to take a look at that chapter (there’s as much code as text in that chapter).
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
• We’veseenthisideaofjoiningbefore,forboththreadsandprocesses.Nowyoucanputaname to this idea.
• Figure30.2,whatisthis,aspinlock?Didn’twefigureoutthatthosewere“bad”?
30.1: Definition and routines
• “Aconditionvariableisanexplicitqueue…”There’sthatqueuedatastructureagain.
– Think back to chapter 28: we’re using a new term (condition variable), but isn’t this basi- cally just a lock?
• Thinkbacktoseveralweeksagonow:canyoudothiswithsignals?How?
• Convince yourself that the two changes to figure 30.3 that are defined in 30.4 (replacing the thr_exit and thr_join functions) can result in a condition where the parent gets stuck
waiting forever.
30.2: The producer/consumer (bounded buffer) problem
• Canyouthinkofanyreal-lifeanalogyforwhattheauthorsdescribeastheproducer/consumer problem?
• Theauthorsuseanunnamedshellpipe|asanexampleoftheboundedbufferproblem.Think back to when we looked at the kernel source code for pipes: what was that bounded buffer data structure?
• “The put routine assumes the buffer is empty”, how does it do that? Can it assume that, in general, without a lock? Can you think about how this is related to condition variables and signals before we get to the actual answer below?
A Broken Solution
• “However,puttingalockaroundthecodedoesn’twork;weneedsomethingmore.”Why?Why doesn’t a basic lock work here?
• Convince yourself about how this solution is broken using figure 30.9. This is getting difficult to think about 3 things running concurrently!
• This is a very subtle reference, but on pg 9 the authors write “An assertion triggers” — they’re very subtly referring to the use of assertions (i.e., assert.h) and design by contract here.
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
Better, but still broken: While, not if
• Again,convinceyourselfthatfigure30.10isbrokenusingthetraceinfigure30.11.
• Really importantly: these problems are coming from the fact that locks and threading are per- mitting us to have some control over scheduling, but the scheduler is kinda fighting back and
we can’t predict when the scheduler is going to take over.
The Single buffer producer/consumer solution
• Onceagain,convinceyourselfthatfigure30.13isindeedcorrectcomparedtothepreviousso-
lutions. What’s different about this specific solution compared to the others?
The correct producer/consumer solution
• Finally, and again, convince yourself that what the authors have done in in figure 30.14 is in- deed a correct and general solution to this problem (e.g., buffer size > 1, multiple producers, multiple consumers).
30.3: Covering conditions
• OK wat? A multi-threaded memory allocation library? We’ll eventually take a look at memory allocation (when we take a deep dive into memory management), but the general idea here is good to think about: you’ve got pthreads, they’re almost certainly going to call malloc at some point, how would the OS (or, in reality, the standard C library) actually handle multiple threads asking it to allocate memory for them on the heap?
• Thebroadcastvariantofcond_signaliskindofcool,itwakesupallthreadsthatareblocked on a condition variable instead of just one. Can you do this with the signals that we looked at with the kill and signal system calls?
– As an exercise, try creating multiple pthreads that register the same signal handler, then send the signal to your process.
Chapter 32: Common concurrency bugs
32.1 What type of bugs exist?
• FWIW: this book is kind of showing some age here: MySQL was acquired by Sun, which was acquired by Oracle, which is kind of a “bad thing” TM because Oracle itself is a huge RDBMS com-
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
pany, so owning two really big relational database implementations makes people kind of ner- vous. MySQL was forked to MariaDB.
Mozilla itself isn’t really a thing anymore, you’re probably more familiar with Firefox, which is ultimately derived from Mozilla’s codebase.
OpenOffice itself is also not really a thing anymore, but LibreOffice is (OpenOffice has its heritage in StarOffice, which was also at some point a Sun product, which was then bought by Oracle).
The Apache web server is the only software here that’s still what it was when this book was originally written. Good going, Apache.
END OF HISTORY LESSON.
• Why do you think “Non-Deadlock” concurrency bugs are more common than “Deadlock” con- currency bugs? At least in the table the authors are reproducing in figure 32.1, deadlock bugs are less frequent than non-deadlock bugs.
32.2 Non-deadlock bugs Atomicity-Violation bugs
• Atthetopofpg3,theauthorsinviteyoutotryfiguringoutthesolutiontotheatomicity-violation bug listed in figure 32.2. DO IT. Stop and think about it, how would you ensure that the value of thd->proc_info doesn’t change while it’s being used?
Order-violation bugs
• Ok,thisistrickytodo,buttrycoveringupthetextthat’simmediatelybelowfigure32.4andsee if you can figure out what the bug is in the code.
• Why does the solution for this bug use condition variables and locks? Why wouldn’t it just use a lock? Why does it have to use this additional variable mtInit? (Hint: is the code that follows the lock+condition variable in Thread 2 a critical section? Assuming that mState itself is a stack allocated local variable.)
Non-deadlock bugs: summary
• The authors reproduce a statistic here by Lu et al. that “(97%) of non-deadlock bugs…”, what are the other 3%?
– ThispaperiscalledLearningfromMistakes—AComprehensiveStudyonRealWorldCon- currency Bug Characteristics.
COMP 3430 Operating systems – Chapter 28, 30, 32 reading notes Winter 2022
32.3 Deadlock bugs
• Deadlockbugs
• BEFORE READING AFTER figure 32.6: Looking just at the code in figure 32.6, can you come up
with the sequence of execution and interruptions that would be required for a deadlock situa- tion to occur between thread 1 and thread 2?
Why do deadlocks occur?
• Checkoutthecurrent(-ish)JavaimplementationofVector#addAll.
The authors describe that this uses a lock, how does locking in Java differ from locking pthreads in C? Does the Vector class have anything related to threading in its imports? Try to translate the ideas in Java here (e.g., synchronized(this) with the corresponding pieces of locking in pthreads (e.g., the functions you call and the objects you create).
Conditions for deadlock
• Beabletoconvinceyourselfaboutthesefourconditions,specificallyfromtheperspectiveof“If one of these four conditions isn’t met, then deadlock cannot occur because…”
• We’veusedthisword“preemption”before,butinthecontextoftimeslices.Doestheuseofthe word preemption here match what you understand preemption to be in terms of timeslices?
Prevention: Circular wait
• TheLinuxkernelsourcecodethattheauthorsrefertoismm/filemap.c.
What the authors describe (lock ordering required by the kernel) is the huge block of comments
at the top of this file.
• This is outside the scope of our course, but: could lock ordering by identified by automated tools? For example, could static analysis software (programs that read and understand source code) be designed to identify patterns of lock acquisition and report errors when locks aren’t used in the same order? (Hint: the answer is “Yes”, but only to a limited extent).
• Istotalorpartialorderingrelevantwhenyouonlyhave1lock?
Prevention: Hold and wait
• Thesolutionhereistobasicallylocklockacquisition.(Yodawg).
• Canyouconvinceyo
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com