<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://homeostasis.scs.carleton.ca/wiki/index.php?action=history&amp;feed=atom&amp;title=Operating_Systems_2026F_Lecture_15</id>
	<title>Operating Systems 2026F Lecture 15 - Revision history</title>
	<link rel="self" type="application/atom+xml" href="https://homeostasis.scs.carleton.ca/wiki/index.php?action=history&amp;feed=atom&amp;title=Operating_Systems_2026F_Lecture_15"/>
	<link rel="alternate" type="text/html" href="https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2026F_Lecture_15&amp;action=history"/>
	<updated>2026-11-16T21:37:56Z</updated>
	<subtitle>Revision history for this page on the wiki</subtitle>
	<generator>MediaWiki 1.42.1</generator>
	<entry>
		<id>https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2026F_Lecture_15&amp;diff=25235&amp;oldid=prev</id>
		<title>Soma: Created page with &quot;==Video==  Video from the lectures given on November 12th and 13th, 2026 are now available: * [https://homeostasis.scs.carleton.ca/~soma/os-2026f/lectures/comp3000-2026f-lec15a-20261112.mp4 Lecture 15A] * [https://homeostasis.scs.carleton.ca/~soma/os-2026f/lectures/comp3000-2026f-lec15b-20261113.mp4 Lecture 15B]  ==Notes==  ===Lecture 15A===  &lt;pre&gt; Lecture 15A ----------- Semaphores &amp; condition variables  kernel modules  A2 is graded A3 will be posted today  Mutual exclu...&quot;</title>
		<link rel="alternate" type="text/html" href="https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2026F_Lecture_15&amp;diff=25235&amp;oldid=prev"/>
		<updated>2026-11-13T20:31:16Z</updated>

		<summary type="html">&lt;p&gt;Created page with &amp;quot;==Video==  Video from the lectures given on November 12th and 13th, 2026 are now available: * [https://homeostasis.scs.carleton.ca/~soma/os-2026f/lectures/comp3000-2026f-lec15a-20261112.mp4 Lecture 15A] * [https://homeostasis.scs.carleton.ca/~soma/os-2026f/lectures/comp3000-2026f-lec15b-20261113.mp4 Lecture 15B]  ==Notes==  ===Lecture 15A===  &amp;lt;pre&amp;gt; Lecture 15A ----------- Semaphores &amp;amp; condition variables  kernel modules  A2 is graded A3 will be posted today  Mutual exclu...&amp;quot;&lt;/p&gt;
&lt;p&gt;&lt;b&gt;New page&lt;/b&gt;&lt;/p&gt;&lt;div&gt;==Video==&lt;br /&gt;
&lt;br /&gt;
Video from the lectures given on November 12th and 13th, 2026 are now available:&lt;br /&gt;
* [https://homeostasis.scs.carleton.ca/~soma/os-2026f/lectures/comp3000-2026f-lec15a-20261112.mp4 Lecture 15A]&lt;br /&gt;
* [https://homeostasis.scs.carleton.ca/~soma/os-2026f/lectures/comp3000-2026f-lec15b-20261113.mp4 Lecture 15B]&lt;br /&gt;
&lt;br /&gt;
==Notes==&lt;br /&gt;
&lt;br /&gt;
===Lecture 15A===&lt;br /&gt;
&lt;br /&gt;
&amp;lt;pre&amp;gt;&lt;br /&gt;
Lecture 15A&lt;br /&gt;
-----------&lt;br /&gt;
Semaphores &amp;amp;&lt;br /&gt;
condition variables&lt;br /&gt;
&lt;br /&gt;
kernel modules&lt;br /&gt;
&lt;br /&gt;
A2 is graded&lt;br /&gt;
A3 will be posted today&lt;br /&gt;
&lt;br /&gt;
Mutual exclusion&lt;br /&gt;
 - think a stretch of railroad track, you&lt;br /&gt;
   only want one train on it at a time&lt;br /&gt;
 - so you want trains to have exclusive access&lt;br /&gt;
   to a track. Thus the presence of one&lt;br /&gt;
   excludes the presence of another&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
Mutual exclusion refers to critical sections of code&lt;br /&gt;
 - code interacting with shared resources&lt;br /&gt;
&lt;br /&gt;
regular code   &amp;lt;-- can run as many copies in parallel&lt;br /&gt;
                   as we want&lt;br /&gt;
...&lt;br /&gt;
critical code   &amp;lt;-- only one copy of this can run&lt;br /&gt;
                    at any time&lt;br /&gt;
...&lt;br /&gt;
regular code&lt;br /&gt;
&lt;br /&gt;
Why bother with critical sections?&lt;br /&gt;
 - because we don&amp;#039;t want corrupted data structures&lt;br /&gt;
&lt;br /&gt;
Typical way to protect critical sections of code and their associated data is to use mutexes, or binary semaphores&lt;br /&gt;
&lt;br /&gt;
semaphores are the &amp;quot;signalling lights&amp;quot; of computation to prevent trains from running into each other&lt;br /&gt;
 - and a mutex is just a stop and go signal&lt;br /&gt;
 - general semaphores can have many values (numbers)&lt;br /&gt;
&lt;br /&gt;
Mutexs are normally talked about as &amp;quot;locks&amp;quot;&lt;br /&gt;
 - code grabs a lock before accessing key data&lt;br /&gt;
   or other resources&lt;br /&gt;
 - code releases the lock when done&lt;br /&gt;
&lt;br /&gt;
What happens if someone else has the lock?&lt;br /&gt;
 - either grabbing the lock fails,&lt;br /&gt;
 - or you block (wait)  &amp;lt;--- common version&lt;br /&gt;
&lt;br /&gt;
What does it mean for a process to sleep?&lt;br /&gt;
 - it means the process is no longer running on any core&lt;br /&gt;
&lt;br /&gt;
The kernel has many processes active:&lt;br /&gt;
 - some are actively running (using a core)&lt;br /&gt;
 - some are ready to run (waiting for a core)&lt;br /&gt;
 - some are sleeping/blocked (waiting for an event)&lt;br /&gt;
&lt;br /&gt;
When a process goes to sleep&lt;br /&gt;
 - the process sets a handler to be called when&lt;br /&gt;
   an event occurs&lt;br /&gt;
 - it then gives up the CPU it is using&lt;br /&gt;
&lt;br /&gt;
It takes time (CPU cycles) to put a process to sleep&lt;br /&gt;
and wake it up again&lt;br /&gt;
&lt;br /&gt;
Why?&lt;br /&gt;
 - because there&amp;#039;s a lot of state associated with a running program, and that all has to be saved and then restored&lt;br /&gt;
&lt;br /&gt;
So when the expected wait is short, we busy wait&lt;br /&gt;
 (that&amp;#039;s what spinlocks do)&lt;br /&gt;
&lt;br /&gt;
Condition variables are used to coordinate behavior&lt;br /&gt;
 - wake up other threads/processes when&lt;br /&gt;
   they were waiting for an event&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
You don&amp;#039;t want to implement condition variables, semaphores, or mutexs on your own. They are very tricky to get right. Why?&lt;br /&gt;
&lt;br /&gt;
 - the memory hierarchy!&lt;br /&gt;
&lt;br /&gt;
Remember a variable in your code maps to multiple values in memory&lt;br /&gt;
 - registers, L1-L3 cache, main memory, maybe even swap&lt;br /&gt;
   (will explain swap later)&lt;br /&gt;
 - registers, L1-L3 are duplicated between cores&lt;br /&gt;
&lt;br /&gt;
It is possible to keep the copies perfectly in sync,&lt;br /&gt;
but then there&amp;#039;s (almost) no point in keeping copies!&lt;br /&gt;
&lt;br /&gt;
To do any kind of concurrency coordination, you need&lt;br /&gt;
reliable communication. If you&amp;#039;re doing it with&lt;br /&gt;
shared memory, you have to make sure state is REALLY shared&lt;br /&gt;
 - so you have to use special CPU instructions&lt;br /&gt;
&lt;br /&gt;
We have two kinds of instructions&lt;br /&gt;
 - test &amp;amp; set  &amp;lt;- if + assignment&lt;br /&gt;
 - swap        &amp;lt;- swap two variables (values in memory)&lt;br /&gt;
&lt;br /&gt;
Both of these work &amp;quot;atomically&amp;quot;&lt;br /&gt;
 - as if they are indivisible&lt;br /&gt;
&lt;br /&gt;
transactions in databases are used to get atomic-like semantics&lt;br /&gt;
 - if we get interrupted in the middle of a transaction,&lt;br /&gt;
   any changes get undone&lt;br /&gt;
&lt;br /&gt;
Transactions&lt;br /&gt;
 - think about buying airline tickets&lt;br /&gt;
   (or concert tickets with reserved seating)&lt;br /&gt;
 - it inherently involves multiple steps&lt;br /&gt;
   - pay for the ticket&lt;br /&gt;
   - reserve the actual seat&lt;br /&gt;
   - update customer information,&lt;br /&gt;
     show they own the ticket&lt;br /&gt;
 - we want the purchase to happen atomically, but&lt;br /&gt;
   in practice it involves lots of steps&lt;br /&gt;
 - so with a transaction, we keep records so we can undo intermediate steps&lt;br /&gt;
   - only on a &amp;quot;commit&amp;quot; is the purchase completed&lt;br /&gt;
     and it can&amp;#039;t be undone&lt;br /&gt;
 &lt;br /&gt;
 &lt;br /&gt;
Swap two values in X and Y&lt;br /&gt;
&lt;br /&gt;
 Z = X&lt;br /&gt;
 X = Y&lt;br /&gt;
 Y = Z&lt;br /&gt;
&lt;br /&gt;
Linux kernel modules&lt;br /&gt;
 - real kernel programming!&lt;br /&gt;
&lt;br /&gt;
So, what&amp;#039;s a kernel module?&lt;br /&gt;
&lt;br /&gt;
The linux kernel is big program&lt;br /&gt;
 - so we want to decompose it&lt;br /&gt;
&lt;br /&gt;
One way to decompose a kernel is into multiple processes&lt;br /&gt;
 - &amp;quot;microkernel architecture&amp;quot;&lt;br /&gt;
 - what is actually running in supervisor mode is&lt;br /&gt;
   a relatively small bit of code&lt;br /&gt;
 - everything else runs in regular processes&lt;br /&gt;
&lt;br /&gt;
The linux kernel is a &amp;quot;monolithic&amp;quot; kernel&lt;br /&gt;
 - everything is in the same address space&lt;br /&gt;
   (like a process, but not quite)&lt;br /&gt;
&lt;br /&gt;
A kernel module is just code that gets loaded into the address space of the kernel&lt;br /&gt;
&lt;br /&gt;
so is a kernel module the same as eBPF?&lt;br /&gt;
 - eBPF has restrictions, limitations&lt;br /&gt;
 - kernel modules can do everything and anything&lt;br /&gt;
   (and there are almost no checks)&lt;br /&gt;
&lt;br /&gt;
Most modules are for device drivers&lt;br /&gt;
&lt;br /&gt;
What&amp;#039;s a device driver?&lt;br /&gt;
&lt;br /&gt;
The kernel abstracts system hardware&lt;br /&gt;
 - to give a uniform interface to regular applications&lt;br /&gt;
&lt;br /&gt;
The core kernel implements the basic abstractions&lt;br /&gt;
device drivers implement the mapping between&lt;br /&gt;
the abstractions and the specifics of the hardware&lt;br /&gt;
 - different hardware, different device driver&lt;br /&gt;
&lt;br /&gt;
One peculiarity of the Linux kernel is it doesn&amp;#039;t provide a stable API or ABI to kernel modules&lt;br /&gt;
 - VERY different from Windows or macOS&lt;br /&gt;
&amp;lt;/pre&amp;gt;&lt;br /&gt;
&lt;br /&gt;
===Lecture 15B===&lt;br /&gt;
&lt;br /&gt;
&amp;lt;pre&amp;gt;&lt;br /&gt;
Lecture 15B&lt;br /&gt;
-----------&lt;br /&gt;
A2 is graded&lt;br /&gt;
 - will upload today&lt;br /&gt;
&lt;br /&gt;
Midterms are almost there&lt;br /&gt;
 - will be finished in the next few days&lt;br /&gt;
&lt;br /&gt;
A3 is almost done&lt;br /&gt;
 - you&amp;#039;ll get a week&lt;br /&gt;
 - it is just a file copy program based on T6 code&lt;br /&gt;
&lt;br /&gt;
Mutexs are binary semaphores&lt;br /&gt;
 - used to enforce mutual exclusion, hence the name&lt;br /&gt;
&lt;br /&gt;
Mutexes are like the ad-hoc traffic lights used when only one lane is available for traffic&lt;br /&gt;
 - actually it is all traffic lights!&lt;br /&gt;
&lt;br /&gt;
Semaphores, esp mutexs, are for enforcing mutual exclusion&lt;br /&gt;
condition variables are used to &amp;quot;wake up&amp;quot; another process/thread&lt;br /&gt;
that is waiting (for a condition to be reached)&lt;br /&gt;
&lt;br /&gt;
CPUs (cores) are shared resources&lt;br /&gt;
&lt;br /&gt;
When a process &amp;quot;sleeps&amp;quot;, it is giving up its current CPU (that it was running on) and is allowing another process to run (or thread)&lt;br /&gt;
 - so this means the process is relying on some event to happen,&lt;br /&gt;
   and when that event happens it wants to be woken up&lt;br /&gt;
   (i.e., get the CPU back)&lt;br /&gt;
&lt;br /&gt;
So what sort of events?&lt;br /&gt;
 - timer going off&lt;br /&gt;
 - I/O to be completed&lt;br /&gt;
 - another process to communicate&lt;br /&gt;
 - network traffic to arrive&lt;br /&gt;
 - (any system call to complete)&lt;br /&gt;
&lt;br /&gt;
Deciding which process or thread should get access to which CPU is the problem of CPU scheduling&lt;br /&gt;
 - will discuss more soon!&lt;br /&gt;
&lt;br /&gt;
Going to sleep only makes sense if the wait is long enough&lt;br /&gt;
 - giving up and getting back on a CPU takes some work&lt;br /&gt;
   (have to save and restore CPU state, including caches and address space)&lt;br /&gt;
&lt;br /&gt;
So for short waits, what do you do?&lt;br /&gt;
 - you spin!&lt;br /&gt;
 - i.e., you run a tight loop that checks for the condition to be true&lt;br /&gt;
 - there are kinds of mutexs known as spinlocks that do this&lt;br /&gt;
   (mostly used in the kernel)&lt;br /&gt;
&lt;br /&gt;
DO NOT WRITE MUTUAL EXCLUSION PRIMITIVES FROM SCRATCH&lt;br /&gt;
 - they require carefully written assembly to work properly!&lt;br /&gt;
&lt;br /&gt;
Why? the memory hierarchy!&lt;br /&gt;
 - many copies of in-use variables&lt;br /&gt;
   (between caches, registers, main memory)&lt;br /&gt;
 - and for concurrency we need those variables to have the same&lt;br /&gt;
   value at the same time&lt;br /&gt;
   - so the copies have to be kept in sync!&lt;br /&gt;
   - but we can&amp;#039;t even see many of the copies from our code!&lt;br /&gt;
&lt;br /&gt;
To get around these issues, you need to use special assembly language instructions&lt;br /&gt;
 - test &amp;amp; set&lt;br /&gt;
 - swap&lt;br /&gt;
&lt;br /&gt;
The idea of these instructions is they do a set of operations &amp;quot;atomically&amp;quot; which normally would not be&lt;br /&gt;
&lt;br /&gt;
atomic = indivisible (original greek?)&lt;br /&gt;
&lt;br /&gt;
We need this atomic property to make sure we don&amp;#039;t have TOCTTOU&lt;br /&gt;
&lt;br /&gt;
if (x) then y&lt;br /&gt;
&lt;br /&gt;
How do we know x is still true when we do y?&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
To swap the value of X and Y&lt;br /&gt;
&lt;br /&gt;
 Z = X&lt;br /&gt;
 X = Y&lt;br /&gt;
 Y = Z&lt;br /&gt;
&lt;br /&gt;
If you can make a swap atomic, you can grab a lock by just swapping a value and checking the old value to see whether the lock was available&lt;br /&gt;
&lt;br /&gt;
the general form of making groups of operations atomic is transactions&lt;br /&gt;
 - from databases&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
KERNEL MODULES&lt;br /&gt;
 - that&amp;#039;s next week!&lt;br /&gt;
&lt;br /&gt;
kernel modules let us add and remove code from a running kernel&lt;br /&gt;
 - but don&amp;#039;t we already have that with eBPF?&lt;br /&gt;
&lt;br /&gt;
eBPF is limited in its functionality&lt;br /&gt;
 - designed to monitor the system, not provide raw functionality&lt;br /&gt;
   (but that is changing)&lt;br /&gt;
 - limited by a verifier&lt;br /&gt;
&lt;br /&gt;
How do we decompose kernel functionality?&lt;br /&gt;
 - because its a big program dealing with complex problems!&lt;br /&gt;
&lt;br /&gt;
Why can&amp;#039;t we just use processes?&lt;br /&gt;
 - some do! microkernels!&lt;br /&gt;
&lt;br /&gt;
so some code has to be in the kernel (managing CPU &amp;amp; address spaces)&lt;br /&gt;
 - but rest can go in processes&lt;br /&gt;
 - what code is the rest?&lt;br /&gt;
&lt;br /&gt;
Big advantage of microkernels is they can be easier to debug&lt;br /&gt;
 - you can trace, restart processes easily&lt;br /&gt;
&lt;br /&gt;
Linux uses a &amp;quot;monolithic&amp;quot; architecture instead&lt;br /&gt;
 - kernel only uses one address space, rather than many&lt;br /&gt;
   that are separated by protection boundaries (e.g. processes)&lt;br /&gt;
&lt;br /&gt;
Linux kernel modules are just code that is loaded into the kernel&amp;#039;s address space&lt;br /&gt;
 - no real protections against this code doing whatever it wants,&lt;br /&gt;
   for good or ill&lt;br /&gt;
&lt;br /&gt;
Most kernel modules are for device drivers&lt;br /&gt;
&lt;br /&gt;
Device drivers are adaptors between the specifics of hardware and the abstractions of the kernel&lt;br /&gt;
&lt;br /&gt;
Why are all of the modules duplicated between even minor versions of the kernel?&lt;br /&gt;
 - because the Linux kernel doesn&amp;#039;t offer a stable API or ABI to&lt;br /&gt;
   kernel modules&lt;br /&gt;
&lt;br /&gt;
Android is a mess in part because of this lack of a stable API and ABI&lt;br /&gt;
 - not Linux&amp;#039;s fault, it is Google&amp;#039;s fault!&lt;br /&gt;
&amp;lt;/pre&amp;gt;&lt;/div&gt;</summary>
		<author><name>Soma</name></author>
	</entry>
</feed>