https://homeostasis.scs.carleton.ca/wiki/index.php?action=history&feed=atom&title=Operating_Systems_2022F_Lecture_14 2026-04-05T22:41:56Z Revision history for this page on the wiki MediaWiki 1.42.1 https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2022F_Lecture_14&diff=24128&oldid=prev 2022-11-03T20:12:55Z

<p>Created page with &quot;==Video== Video from the lecture given on November 3, 2022 is now available: * [https://homeostasis.scs.carleton.ca/~soma/os-2022f/lectures/comp3000-2022f-lec14-20221103.m4v video] * [https://homeostasis.scs.carleton.ca/~soma/os-2022f/lectures/comp3000-2022f-lec14-20221103.cc.vtt auto-generated captions] Video is also available through Brightspace (Resources-&gt;Zoom meeting-&gt;Cloud Recordings tab) ==Notes== &lt;pre&gt; Lecture 14 ---------- Assignment 3 has not yet been relea...&quot;</p> <p><b>New page</b></p><div>==Video==<br /> <br /> Video from the lecture given on November 3, 2022 is now available:<br /> * [https://homeostasis.scs.carleton.ca/~soma/os-2022f/lectures/comp3000-2022f-lec14-20221103.m4v video]<br /> * [https://homeostasis.scs.carleton.ca/~soma/os-2022f/lectures/comp3000-2022f-lec14-20221103.cc.vtt auto-generated captions]<br /> Video is also available through Brightspace (Resources-&gt;Zoom meeting-&gt;Cloud Recordings tab)<br /> <br /> ==Notes==<br /> <br /> &lt;pre&gt;<br /> Lecture 14<br /> ----------<br /> <br /> Assignment 3 has not yet been released<br /> - hoping to post tomorrow<br /> - due date will be 11th at earliest, will update once assignment is posted<br /> <br /> Tutorial 7 is *almost* ready, that will be out by tomorrow definitely<br /> - you can start looking at it now if you want<br /> <br /> So tutorial due dates move with the assignment due dates<br /> - so you have some more time on 5 and 6<br /> <br /> A3 is based on T5 and T6, NOT T7<br /> <br /> Deadlock<br /> --------<br /> - one class of concurrency bugs<br /> - see the textbook for others<br /> <br /> What is deadlock?<br /> - type of situation in which progress on a computation stops because everyone is waiting on a resource that will never become available because another part of the system is holding onto it<br /> <br /> Dining philopher&#039;s problem<br /> - five philosophers sitting around the table<br /> - have food in front of them that they need 2 utensils to eat<br /> - but there are only 5 utensils at the table<br /> - problem: how do we make sure that the philosophers eat?<br /> <br /> What algorithm works?<br /> <br /> Think of the basic approach:<br /> - grab the utensil on the left<br /> - grab the one on the right<br /> - eat<br /> - put utensil on the right down<br /> - put utensil on the left down<br /> <br /> Why can this result in everyone starving?<br /> <br /> If everyone tries to eat at the same time, they will all have a left fork<br /> and will never put it down<br /> <br /> What if we add a one second timeout? (i.e., if you don&#039;t get the right utensil in one second you put down the left one)<br /> - but then you get everyone picking up and putting down the left utensil in unison, they all still starve<br /> <br /> you can add in random timeout, that mostly works<br /> - but the pauses can go on for arbitrarily long<br /> <br /> Dining philosopher&#039;s problem results in deadlock because four conditions all hold:<br /> - mutual exclusion (only one has a utensil at a time)<br /> - hold-and-wait (holding on to some resources when they don&#039;t have all that<br /> they need to eat)<br /> - no preemption (no stealing utensils)<br /> - circular wait (they are sitting in a circle)<br /> <br /> All these have to hold to get deadlock, break any one of them and you can avoid it<br /> <br /> The trick with solutions to this problem isn&#039;t to avoid deadlock, it is to avoid deadlock *efficiently*<br /> - minimize delays due to resource contention<br /> <br /> <br /> Classic way to avoid deadlock issues is to just have one master lock<br /> - used by old versions of Linux, still in place (I think) in the standard Python runtime<br /> <br /> But if you do this, then you minimize parallelism<br /> - only one lock means every time a shared resource is needed, we&#039;re down to a single thread running<br /> <br /> In a parallel system, you want all parts of the system to keep running all the time<br /> - waiting on other threads/processes reduces overall performance<br /> - how to minimize the waiting for resources (resource contention)?<br /> <br /> Temptation is to make LOTS of locks, one for each resource<br /> - but the more locks we add, the higher risk of deadlock<br /> <br /> Simplest solution to avoid deadlock is to always allocate resources (locks) in a fixed order<br /> - A, B, C but never A, C, B<br /> - avoids circular dependence<br /> <br /> But what in your code enforces that you grab locks always in the same order?<br /> NOTHING<br /> <br /> Why is there so much discussion of deadlock in concurrency theory and in OS courses?<br /> - easy to formalize<br /> - many possible algorithms<br /> <br /> In practice, we add in timeouts and try to allocate resources in a fixed order<br /> <br /> In Tutorial 6:<br /> - 3000pc-fifo uses pipes, works<br /> - 3000pc-rendezvous uses shared memory<br /> - is fast, but deadlocks<br /> - 3000pc-rendezvous uses shared memory, timeouts<br /> - not as fast because it pauses randomly, but works<br /> <br /> Note that the shared memory versions use functions from the pthread library<br /> (which is specially linked in). pthread is a standard UNIX library (part of POSIX), but it is implemented differently on different systems, because system calls related to concurrency aren&#039;t standardized<br /> - note the clone system call, used to make threads, is not standard, it is Linux specific<br /> <br /> Why does 3000pc-rendezvous deadlock? What is happening?<br /> - I didn&#039;t realize this would happen when I made it<br /> - 3000pc-rendezvous-timeout was a bugfix!<br /> <br /> So what actually happens?<br /> - both the producer and consumer go to sleep at the same time<br /> <br /> Compare 3000pc-rendezvous and 3000pc-rendezvous-timeout<br /> - logic in 3000pc-rendezvous is much simpler, but it deadlock<br /> - all 3000pc-rendezvous-timeout does is adds timeouts to waiting for all locks and condition variables, because sometimes things go wrong<br /> <br /> spinlocks are a kind of mutex which &quot;busy waits&quot;:<br /> - when waiting for the lock to be available, just do while(1)<br /> - so CPU is &quot;spinning&quot; while waiting for the lock to be available<br /> - not so efficient, but most efficient strategy when wait should be short<br /> <br /> But if the wait is going to be longer, you don&#039;t want to consume CPU time doing nothing - that just makes your CPU hot for no good reason<br /> <br /> Instead, we want to sleep while waiting, to get woken up when the resource is available<br /> <br /> The mutex&#039;s we are using sleep rather than busy wait<br /> <br /> Why not always sleep? For that we have to understand CPU scheduling<br /> <br /> When you look at the STAT column in ps, you&#039;ll see many letter codes<br /> - S: sleeping<br /> - R: running<br /> - I: idle kernel thread<br /> - Z: zombie (terminated, waiting for wait)<br /> <br /> What is the difference between a process sleeping and running?<br /> - running: it is executing instructions on a CPU core<br /> - sleeping: it is waiting to execute instructions, it isn&#039;t doing anything now<br /> <br /> <br /> <br /> process executing<br /> - in running mode<br /> - on a CPU core in user mode<br /> - registers hold process&#039;s state<br /> <br /> runnable process<br /> - could be on a CPU or could be waiting<br /> - is not waiting on any events, just needs to get back on the CPU<br /> <br /> process sleep<br /> - in sleep mode<br /> - NOT on a CPU core, instead state is stored in process data structure<br /> in kernel<br /> - thus has no state in registers<br /> - waiting for an event to happen<br /> <br /> <br /> Process states are just an abstraction over how the CPU is shared between processes<br /> - a CPU core can be executing a process OR it can be executing kernel code<br /> - when executing a process, it is in user mode<br /> - when executing the kernel, it is in supervisor mode<br /> <br /> How does the CPU switch between running a process in user mode and the kernel in supervisor mode?<br /> <br /> One way: the process makes a system call<br /> - syscall instruction causes CPU to switch to kernel mode, jump to<br /> system call handler routine in the kernel and execution proceeds from there<br /> <br /> BUT, what if a process never makes a system call?<br /> - say if it is just crunching some data?<br /> <br /> Interrupts are events generated by the hardware that have to be handled by the kernel<br /> - hardware generates interrupt<br /> - CPU switches to supervisor mode, handles the interrupt event<br /> <br /> What sort of hardware generate interrupts? well, basically everything except for RAM (and maybe it does on some systems if it detects errors)<br /> - keyboard, mouse<br /> - CPU (divide by zero, syscall instructions, etc)<br /> - SSD<br /> - sound, video<br /> - network<br /> - timers &lt;--- very important<br /> <br /> EVERY time you hit a key, some part of the system has to handle the keypress<br /> - to a first approximation, every keypress generates an interrupt<br /> <br /> Basically when a device needs attention from the CPU, it sends the CPU an interrupt<br /> - the interrupt causes the CPU to stop what it is doing and run code<br /> registered as the designated handler for that interrupt<br /> <br /> signals are like interrupt handlers for processes<br /> - but it is a metaphorical connection, a signal is an OS abstraction<br /> while interrupts are a feature of the hardware<br /> <br /> <br /> Fun fact<br /> - on old macs (before OS X), if you held the mouse button down<br /> it wouldn&#039;t be able to receive any network traffic and in fact all<br /> running programs would pause<br /> <br /> <br /> I&#039;ve discussed here how we go from running a process to running the kernel<br /> - basically, interrupts<br /> <br /> How do we get from the kernel to running a process? that&#039;s scheduling, and<br /> is for next time!<br /> &lt;/pre&gt;</div>

Soma