https://homeostasis.scs.carleton.ca/wiki/index.php?action=history&feed=atom&title=Operating_Systems_2019W_Lecture_17 2026-04-05T17:00:48Z Revision history for this page on the wiki MediaWiki 1.42.1 https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2019W_Lecture_17&diff=22280&oldid=prev 2019-03-18T22:30:00Z

<p>Created page with &quot;==Video== Video for the lecture given on March 18, 2019 [https://homeostasis.scs.carleton.ca/~soma/os-2019w/lectures/comp3000-2019w-lec17-20190318.m4v is now available]. ==N...&quot;</p> <p><b>New page</b></p><div>==Video==<br /> <br /> Video for the lecture given on March 18, 2019 [https://homeostasis.scs.carleton.ca/~soma/os-2019w/lectures/comp3000-2019w-lec17-20190318.m4v is now available].<br /> <br /> ==Notes==<br /> <br /> &lt;pre&gt;<br /> Lecture 17<br /> ----------<br /> <br /> Wednesday will be &quot;online&quot; (likely)<br /> <br /> Concurrency<br /> -----------<br /> <br /> First, asynchronous programming (e.g., node)<br /> - non-blocking I/O<br /> - so, you use callbacks to continue after long operations (such as I/O)<br /> - in node, is done in a single-threaded application<br /> - execution is purely sequential, never parallel (in the program)<br /> <br /> Concurrent programming is when you have parallel executions that can interact<br /> - processes running on separate data, not communicating are NOT concurrent<br /> - but once they communicate or share resources, they are concurrent<br /> <br /> Concurrent programming is hard because the relative speed of programs determines how the system behaves<br /> - A faster than B != B faster than A<br /> <br /> Relational databases were developed to manage concurrent access to data<br /> <br /> Regular applications should normally use databases to manage concurrent access to data. But the operating system can&#039;t (because databases depend on the OS!)<br /> <br /> <br /> Transactions are a way of making sets of non-atomic operations atomic<br /> - atomic =&gt; indivisible<br /> <br /> How do you make something that is divisible, indivisible?<br /> - all operations succeed or none of them do<br /> - if anything fails in the middle, undo the rest<br /> <br /> Airline reservations<br /> - reserve a seat (seat map)<br /> - pay for the seat (payments)<br /> - get customer information (customers)<br /> <br /> Think of these as three tables<br /> <br /> A transaction allows us to either update all three tables or none of the tables<br /> - cancel a transaction, and all parts of it are undone as if they never happened<br /> <br /> <br /> In the kernel, we can&#039;t use ready-made transactions, but we simulate them all the time when we allocate resources<br /> - we don&#039;t want to get into weird states were only some of the resources have been allocated. That&#039;s how you get memory leaks or worse.<br /> - most common resources we wish to access are data structures<br /> <br /> To mediate access to data structures, we use locks<br /> <br /> A lock is just a means of enforcing exclusive access of some kind<br /> - can treat reads and writes differently<br /> <br /> Files can have advisory or mandatory locks<br /> - can you bypass the lock or not<br /> <br /> For in-memory data structures, all locks are advisory<br /> - which makes them painful to debug<br /> <br /> <br /> Classic locks are semaphores, specifically mutexes<br /> - a mutex is a binary semaphore (semaphore with a value of 0 or 1)<br /> <br /> If you try to get it (down on a mutex), if it succeeds, you own the lock<br /> If you don&#039;t get it, you wait until it is free (blocking)<br /> If you don&#039;t get it, lock attempt fails (non-blocking)<br /> <br /> If you block, you can either<br /> - busy wait (for in-memory data structures)<br /> - sleep (for I/O)<br /> <br /> Your code should hold onto locks for as little time as possible<br /> <br /> A critical section is the part of your code that interacts with the shared resource. This is the part that should be protected by a lock.<br /> - critical sections should be short<br /> - they should release locks always<br /> <br /> deadlock<br /> - parts of system can never get resources they need because they are held by another part of the system<br /> - Alice has a fork, Bob has a knife, but both Alice and Bob need a fork and knife to eat their food.<br /> - participants in a deadlock &quot;starve&quot;<br /> <br /> How to resolve deadlock?<br /> - timeouts<br /> - kill someone<br /> - doesn&#039;t work in the kernel<br /> - start over<br /> - reboot<br /> &lt;/pre&gt;</div>

Soma