OS Notes 🐧

These notes are not intended to replace Atlidaki’s notes. They are a summary mostly of definitions that
doesn’t contain everything mentioned on the slides.

You are a commenter and can comment on anything you think is false or needs more information.

Lecture 01,02
Operating System (OS): A layer of software that acts as an abstraction between the
hardware and application software. It manages hardware resources and provides a
standardized, safe, and efficient environment for programs to run.

Kernel: The core, privileged part of the OS that implements the fundamental abstractions
and mechanisms. It is the "OS" code that runs in kernel mode.

Desirable Properties of an OS (remember SRPF)

●​ Security: Protection against malicious actors.
●​ Reliability: Resilience against accidental failures.
●​ Portability: Easy for apps to run on different hardware.
●​ Fairness: The system should be responsive and not let any one user/program
monopolize resources.

Design Principles of an OS (remember FPP)

●​ Fault Isolation: Errors in one running program do not affect any other program
●​ Principle of Least Privilege (PoPL): Any program has the minimum privileges
necessary to perform its function
●​ Preemption: The OS is always able to take control of the processor, regardless of
what programs are running

Hardware Mechanisms for OS Design

●​ Virtual Memory: A memory management technique that gives each process the
illusion of having its own large, contiguous address space. It is the primary
mechanism for implementing fault isolation.
●​ Dual-Mode Execution (User/Kernel Mode): A hardware feature (a mode bit) that
separates privileged OS code from unprivileged user code. User code cannot
execute privileged instructions or access protected memory regions directly.
●​ Timer Interrupt: A hardware timer that generates an interrupt at regular intervals.
This allows the OS to periodically gain control, which is the mechanism for
implementing preemption.
●​ Memory Hierarchy (Cache/L1/L2/L3/RAM): The organization of memory in a
computer into levels, with smaller, faster memory (cache) closer to the CPU and
 larger, slower memory (RAM) further away. The OS must manage memory access
patterns to optimize for this hierarchy.
●​ MMU (Memory Management Unit): Hardware that translates virtual addresses to
physical addresses.
●​ TLB (Translation Lookaside Buffer): A cache for the MMU, storing recent
virtual-to-physical address translations to speed up memory access.

Program Execution & Booting

●​ Instruction Pointer (%ip): A CPU register that holds the memory address of the
next instruction to execute.
●​ Execution Pipeline: The series of steps: SOS
(Fetch → Decode → Execute → Memory → Write-back) a CPU uses to process
instructions.
●​ Boot Process: The sequence BIOS/UEFI → Bootloader → OS Kernel that loads the
operating system into memory and starts it running.
●​ Real Mode vs. Protected Mode: CPU operating modes. Real mode is a simple,
legacy mode with no memory protection. Protected mode is the modern mode that
enables virtual memory, privilege levels, and multitasking.

—------------------------------------------------------------------------------------------------------------------------

Lecture 03

●​ Asynchronous Events: Caused by external hardware (e.g., timer, keyboard press).

The OS runs as an interrupt handler.
●​ Synchronous Events: Caused directly by the execution of a program's instructions.

Core OS Invocation Mechanisms

●​ Interrupt: An asynchronous event signaled by an external hardware device to get
the processor's attention. The OS runs as an interrupt handler.
●​ Exception: A synchronous event that occurs due to the execution of a program
instruction.
●​ System Call (Syscall): The fundamental, controlled interface for a user program to
request a service from the operating system kernel (e.g., create a process, read a
file).
●​ Interrupt Descriptor Table (IDT): A data structure in memory, set up by the OS at
boot, that maps interrupt and exception numbers to the memory addresses of
their corresponding handler routines in the kernel.

Exceptions invoking the OS (synchronous events , remember FAT)

 ●​ Fault: A recoverable exception (e.g., Page Fault). The instruction may be restarted
after the OS handles the fault. (remember this!)**
●​ Abort: A non-recoverable exception that often terminates the process (e.g.,
hardware error).
●​ Trap: An intentional exception used to enter the kernel. A trap is an exception in a
user process. It's also the usual way to invoke a kernel routine (a system call)
because those run with a higher priority than user code.

Exception Handler: The specific code within the operating system that is designed to deal
with a particular type of exception.

Portable Operating System Interface for UNIX (POSIX) is the IEEE standard for portable
UNIX-based OS syscall interfaces.

POSIX Defines
●​ Process: An instance of a program in execution.
●​ Thread: A single flow of control within a process.
●​ File: An object that can be read from and/or written to.

Linux: A monolithic, open-source, POSIX-compliant operating system kernel.

—------------------------------------------------------------------------------------------------------------------------

Lecture 04
Program Memory Layout (Virtual Address Space)
●​ .text Segment: Contains the executable instructions (machine code) of the
program. Typically read-only and executable. (read-execute perms)
●​ .rodata Segment: Contains read-only data, such as string constants and global
constants. (read-only perms)
●​ .data Segment: Contains initialized global and static variables. (read-write perms)
●​ .bss Segment: Contains uninitialized global and static variables. The OS
initializes this segment to zeros at load time. (read-write perms)
●​ Heap: A region for dynamic memory allocation during program execution (e.g., via
malloc in C). It grows towards higher memory addresses. (read-write perms)
●​ Stack: A region that manages function call execution. It stores local variables,
return addresses, and function parameters. It grows towards lower memory
addresses. (read-write perms)

Key Entities in Program Execution

 ●​ Loader: An OS component that reads an executable file from storage, sets up the
process's initial memory layout (stack, heap, code, data), and transfers control to it.
(The Loader is responsible for loading a program into memory)
●​ ELF (Executable and Linkable Format): The standard file format for executables,
object code, and shared libraries on Unix-like systems. It serves as the contract
between compilers/linkers and the OS loader.
●​ Process: An instance of a program in execution. It encompasses the code, data,
stack, heap, and kernel metadata (the "process control block").
●​ Symbol: A named identifier in a program, such as a function name or global variable.
Tools like nm and readelf are used to display them.

Linking Methods
●​ Static Linking: The process of copying all necessary library code directly into the
final executable at compile time.
○​ Advantage: Self-contained, portable.
○​ Disadvantage: Executable file bloat, as common library code is duplicated.
●​ Dynamic Linking: The process of deferring the resolution of some library references
until runtime.
○​ Advantage: Saves disk and memory space (shared libraries), easier to
update libraries.
○​ Disadvantage: More complex loading process, potential for "DLL hell".

Dynamic Linker (e.g., [Link]): A special shared library loaded by the OS Loader whose
job is to finish preparing a dynamically linked program for execution by loading the required
shared libraries and resolving the symbolic references between them.

/proc/<PID>/maps: A Linux pseudo-file that shows the memory map of a running process,
detailing the virtual address ranges, permissions, and backing files for each segment.

Important Observations
●​ The addresses seen by a program are virtual addresses, not physical ones. The OS
and MMU (Memory Management Unit) translate these to physical addresses.
●​ The transition from a passive executable file on disk to an active process in
memory is a complex process involving the loader and, for dynamic binaries, the
dynamic linker.

—------------------------------------------------------------------------------------------------------------------------

Lecture 05
Program: A passive file on disk containing instructions and data (the "recipe").
Process Control Block (PCB): A kernel data structure (task_struct in Linux) that stores all
information about a process (state, registers, memory map, open files, etc.).

A PCB contains (remember VECS):

●​ Virtual Address Space: The memory map (segments like .text, heap, stack).
●​ Execution State: The current values of the CPU registers, instruction pointer, and
stack pointer.
●​ Control Metadata: Scheduling info, user identity, and permissions.
●​ Shared Resources: A list of open files and network connections.

The key reason we use processes is to provide a powerful illusion of isolation.

Each process behaves as if it has:
●​ Exclusive access to memory: Two processes can use the same virtual address to
store different values.
●​ Exclusive use of the processor: The OS uses preemption and time-sharing to
create the illusion that each process has its own CPU.
●​ Exclusive use of storage: Processes can read files as if no other process is
modifying them.

Process Creation & Execution

●​ fork(): A system call that creates a new process by duplicating the calling
process. Returns the child's PID to the parent and 0 to the child.
●​ execve(): A system call that replaces the current process's memory space with a
new program. It loads the new program and starts its execution.
●​ waitpid(): A system call used by a parent process to wait for the state change (e.g.,
termination) of a child process.
●​ Classic Unix Pattern: fork() -> execve() (in child) -> waitpid() (in parent).

Process States
●​ Ready: Waiting to be assigned to a CPU.
●​ Running: Executing on a CPU.
●​ Waiting/Blocked: Unable to run until an external event occurs.
●​ Terminated: Finished execution.
○​ Zombie: A special terminated state where the process has exited, but its
parent has not yet called wait() to read its exit status. The PCB remains until
the parent collects it.
○​ Orphan: A process whose parent has terminated. The OS "re-parents" it to
the init process (PID 1), which will eventually call wait() to clean it up.

Process Scheduling
●​ Multiprogramming: The ability of an OS to run multiple processes concurrently on
a single CPU by switching between them.
●​ Context Switch: The process of saving the state of the currently running process
and loading the state of the next one to run. This is a core OS mechanism enabled
by the PCB.
●​ Preemption: The act of interrupting a running task to run another. This is typically
driven by a timer interrupt.
A scheduler is the component of the operating system that decides which process runs next
on the CPU.

—------------------------------------------------------------------------------------------------------------------------

Quiz 02

2)
●​ The bootloader is in ROM: No - The BIOS/UEFI firmware is in ROM. The
bootloader (e.g., GRUB) is a small program stored on the disk's first sector, which is
loaded into RAM by the BIOS.
●​ The stack is a static segment: No - The stack is a dynamic segment. Its size
changes at runtime as functions are called and return.
●​ A thread is a program in memory: No - A process is a program in memory. A
thread is a single sequence of execution within a process.
●​ POSIX was invented for portability: Yes - POSIX is a standard that ensures
applications can be easily ported between different Unix-like operating systems.
●​ A timer helps implement fault isolation: No - The primary mechanism for
implementing fault isolation is Virtual Memory, not the timer.
●​ A process is used to execute a program: Yes - A process is defined as "an
instance of a program in execution."
●​ A mode register helps implement preemption: No - A mode register (user/kernel
mode) helps implement dual-mode execution for security. The timer helps implement
preemption.
●​ A user space application can directly call a syscall: Yes - A user application can
directly invoke the syscall instruction (or its equivalent) to enter the kernel. It typically
uses a wrapper function from a library like glibc, but the direct invocation is possible.
●​ On a TLB miss, a main memory access must follow: Yes - A TLB miss means the
translation isn't in the fast TLB cache. The MMU must then perform a "page walk" by
accessing the page tables in main memory to find the correct translation.
●​ On x86, a double-fault is an exception of the type "fault": No - A double fault is
an abort. It's a severe error that occurs when the processor fails to handle a first fault
(e.g., a page fault during a page fault handler). It is generally not recoverable.

3)
(a) Disadvantages of Static Linking:
●​ Code Bloat (Storage): Every executable contains a full copy of the libraries it uses,
leading to much larger file sizes on disk.
 ●​ Code Bloat (Memory): If multiple statically-linked programs run, the same library
code is duplicated in RAM for each process, wasting physical memory.
●​ Difficult Updates: To update a library (e.g., for a security patch), every single
application that uses it must be recompiled and redistributed.
(b) Advantage and Disadvantage of Dynamic Linking:
●​ Advantage: Memory Sharing. Multiple running processes can share the same single
copy of a library in physical memory, saving RAM.
●​ Disadvantage: Dependency Hell. An executable won't run if the required shared
libraries (e.g., [Link].6) are missing, are the wrong version, or are incompatible.
(c) TLB Performance:
●​ Answer: Static Linking.
●​ Explanation: With static linking, only the library routines actually used by the
program are copied into its .text segment. These routines are packed together,
leading to good spatial locality. The program will likely need fewer code pages,
resulting in a higher TLB hit rate. Dynamic linking maps the entire library (including
unused functions) into the process's address space. This spreads the used routines
across more memory pages, hurting spatial locality and increasing TLB pressure,
likely leading to more misses.

●​ Spatial Locality is the principle that if a particular memory location is accessed, it is

very likely that nearby (adjacent) memory locations will be accessed in the near
future.
●​ TLB Hit Rate is the percentage of memory access attempts for which the required
virtual-to-physical address translation is found in the TLB.
●​ TLB Pressure is a state where the number of distinct memory pages a program
needs to access within a short time period approaches or exceeds the number of
entries available in the TLB.

Summary Relationship
1.​ Spatial Locality is a program's access pattern.
2.​ Good spatial locality leads to a high TLB Hit Rate because the program works
within a small set of memory pages.
3.​ Poor spatial locality (accessing many scattered pages) creates high TLB Pressure,
which forces a low TLB Hit Rate and kills performance.

4) Good enough explanation in the quiz answers

5)
(a) Why is k22inc problematic?
●​ The instruction does two things: 1) reg += 4, and 2) mem[reg] += const.
●​ A page fault could occur when accessing mem[reg] in the second step. Page
faults are a type of fault, and faults require the OS to fix the problem (e.g.,
load the page from disk) and then restart the faulting instruction from the
beginning.
●​ Here's the critical problem: When the fault occurs, the CPU state that the OS
saves already has the register %reg updated (+4). When the instruction is
 restarted, it will add 4 to the register again, and then try to access mem[reg].
Now it's trying to access mem[reg+8] instead of the intended mem[reg+4].
This makes the instruction's behavior dependent on whether a page fault
occurs, which is a severe bug.
(b) How can k22help fix this?
●​ You can use k22help <%reg> <const> before calling k22inc.
●​ k22help <%reg> <const> will "touch" the memory at mem[reg+const]. If that
memory is not mapped, it will trigger a page fault at a safe time. The OS
will handle it, and the page will be ready.
●​ Now, when you execute k22inc, the register update and the memory access
happen without an intervening page fault, ensuring correct behavior.
(c) Good enough explanation in the quiz answers

—------------------------------------------------------------------------------------------------------------------------

Lecture 06

IPC (Inter-Process Communication): Mechanisms provided by the OS that allow

processes to exchange data and coordinate their activities without using the same
address space.

Asynchronous IPC
●​ The sender "fires and forgets." The recipient is not necessarily waiting for the
message.
●​ Signal: A short, pre-defined notification sent to a process or thread. The recipient is
interrupted to handle it (e.g., SIGINT for interrupt, SIGSEGV for segmentation fault).
●​ Pending Signal: A signal that has been generated but not yet delivered to the target
process.
●​ Blocked Signal: A signal whose delivery is temporarily postponed by the target
process.
●​ Alternate Signal Stack: A separate stack used for executing signal handlers, crucial
for handling stack overflow errors.
Synchronous IPC
●​ The sender and recipient coordinate. The sender waits for the receiver to be
ready, and the receiver waits for the sender to send.
●​ Pipe: A unidirectional, kernel-managed communication channel. Reads block until
data is available.
●​ Shared Memory: A region of memory mapped into the address spaces of multiple
processes, enabling the fastest possible IPC by eliminating data copying.

Key System Calls & Their Purposes

 ●​ Asynchronous IPC (Signals)
○​ kill(pid, signo): The system call used to send a signal to a specific process
or process group. The name is a misnomer; it doesn't always "kill" the target.
○​ sigaction(signum, &act, &oldact): Used by a process to define a signal
"handler": Action to take upon delivery of a signal to it.
○​ sigwait() / sigwaitinfo(): System calls that allow a thread to synchronously
wait for a specific signal, instead of having it arrive asynchronously via an
interrupt. This is a cleaner way to handle signals in a multithreaded program.
●​ Synchronous IPC (Pipes & Shared Memory)
○​ pipe(int fds[2]): Creates an unnamed pipe. It is only visible to the process
that created it and its descendants.
○​ mkfifo(char *pathname, mode_t mode): Creates a named pipe (FIFO) that
appears as a file in the filesystem. This allows unrelated processes to
communicate, overcoming a major limitation of unnamed pipes.
○​ socket(int domain, int type, int protocol): Creates a bidirectional
communication endpoint. While often used for networking, sockets can also
be used for efficient IPC between processes on the same machine (using the
AF_UNIX domain).

Signal-Specific Details
●​ Unstoppable Signals: SIGKILL (9) and SIGSTOP (19) are special. They cannot be
caught, blocked, or ignored by a user process. The kernel guarantees it can always
terminate or stop a process using these signals. This is a critical failsafe.
●​ Who Handles the Signal? In a multithreaded process, a signal sent to the process
(e.g., from kill) is delivered to one arbitrary thread that is not blocking that signal. A
signal caused by a specific thread's action (e.g., SIGSEGV from an invalid memory
access) is delivered to that specific thread.

Key difference between threads and processes: Threads share the same memory
address space and resources, making creation and communication between them very
cheap. Processes are fully isolated.

All threads of a process share

●​ The code, data, and heap segments
●​ Shared system resources allocated to their process
●​ The same page table
Each thread has its own
●​ Status (e.g., ready, running, or waiting)
●​ Execution state (aka processor registers)
●​ Stack
●​ Program counter
●​ File descriptive table for open files

Page Table: A data structure used by the operating system in virtual memory systems to
store the mapping between virtual addresses and physical addresses, enabling memory
isolation and efficient memory management for processes.
Page Table Base Register: A CPU register that holds the physical address of the base
(starting location) of the page table for the current process.
Stack Pointer: A CPU register that points to the top of the current stack in memory, used for
managing function calls, local variables, and temporary data storage.
Program Counter: A CPU register that contains the memory address of the next instruction
to be executed by the processor.
General Purpose Register: A CPU register that can be used for various computational
tasks like storing data, addresses, or intermediate results during program execution.

Critical Trade-offs
●​ Fork vs. Thread Creation: fork() is heavy (duplicates entire address space). Thread
creation is light (shares existing address space).
●​ Pipes vs. Shared Memory: Pipes are simple and safe (kernel-managed) but slow
(data copying). Shared memory is fast (zero-copy) but complex (requires manual
synchronization).
●​ Isolation vs. Sharing: Processes provide strong fault isolation. Threads within a
process share everything, so a bug in one thread can corrupt data used by another.

Threads belonging to a process are by default not protected from each other.

Concurrency: The illusion that multiple tasks are making progress at the same time. This is
achieved by the OS rapidly switching (time-slicing) a single CPU core between
threads/processes.

Parallelism: Actually executing multiple tasks simultaneously. This requires multiple CPU
cores, where one thread runs on core 1 and another runs on core 2 at the exact same time.

The Relationship: You can have concurrency without parallelism (a single-core system).
You can have parallelism without concurrency (one compute-heavy thread per core).
Modern systems have both.

—------------------------------------------------------------------------------------------------------------------------

Lecture 07

●​ Kernel-Level Thread: A thread that is implemented and managed directly by the

operating system kernel.
●​ User-Level Thread: A thread that is implemented by a user-level library, without the
operating system kernel being aware of it.
●​ Multitasking (Time-Sharing): An OS feature where the processor is allocated to
multiple tasks with an upper bound (a time quantum), implemented via preemptive
scheduling.
 ●​ Uniprogramming: A model where a single program is loaded into memory and
executed to completion before the next one begins.
●​ Synchronization: The coordination of multiple threads that are accessing shared
resources to prevent inconsistent data and ensure correct execution.
●​ Load Balancing: The practice of distributing work fairly across multiple processors in
a system to maximize efficiency and utilization.
●​ Processor affinity (also known as CPU pinning or cache affinity): An operating
system scheduling policy that attempts to keep a specific process or thread
running on the same CPU core (or a specific set of cores) as much as possible.
●​ Latency: The time taken to complete a single operation from start to finish.
●​ Throughput: The total number of operations completed in a given unit of time.

Symmetric Multiprocessing (SMP) and Load Balancing:

●​ On multi-core systems, the OS scheduler must perform load balancing to distribute
threads evenly across all processors to maximize efficiency.
●​ This can conflict with processor affinity, as moving a thread to a different core can
cause it to lose the performance benefit of a "warm" cache.

—------------------------------------------------------------------------------------------------------------------------

Lecture 08

●​ Interleaving: The specific sequence in which the instructions of concurrent

operations are executed by the processor(s).
●​ Happens-Before Relationship: A partial ordering between events in a concurrent
system, indicating that one event must be seen to occur before another by all
threads.
●​ Sequential Consistency: The strongest memory model, where the result of any
execution is the same as if the operations of all processors were executed in some
sequential order, and the operations of each individual processor appear in this
sequence in the order specified by its program.
●​ Race Condition: A timing-dependent error in a system or process where the output
or result is unexpectedly and critically dependent on the sequence or timing of other
events.
●​ Data Race: A specific type of race condition that occurs when two or more threads
concurrently access the same memory location, at least one access is a write, and
the accesses are not synchronized (i.e., no "happens-before" ordering exists
between them).
●​ Atomic Operation: An operation that is performed as a single, indivisible unit of
execution. From the perspective of other threads, it either has fully completed or has
not started; there is no intermediate state.
 ●​ Logical clocks allow us to define a partial ordering of concurrent operations on a
multiprocessor system.

Reasons for race conditions (remember DSW):

●​ Data races: Non-atomic, unsynchronized, concurrent operations, at least one of
which mutating shared state
●​ Semantic ordering errors: Code that does not enforce the order programmers
intended to for a group of memory accesses
●​ Weak memory consistency models: Hardware/language rules where observed
memory operation order can differ from program order unless explicitly synchronized.

> A program contains a data race iif two or more threads

(1) access the same memory location concurrently AND
(2) at least one of these accesses is a write AND
(3) at least one of the accesses is not atomic AND
(4) neither happens before the other

The "Bottom-Line": To fix a data race, the non-atomic sequence of instructions

(LOAD-INCREMENT-STORE) must be made to appear as a single, indivisible atomic unit.

—------------------------------------------------------------------------------------------------------------------------

Lecture 09

The Hardware Reality: Why Sequential Consistency is Sacrificed

●​ Performance is the reason. Enforcing strict global order after every write would
mean the CPU spends most of its time waiting for cache coherency protocols to
invalidate lines on other cores, rather than doing useful work.
●​ Write Buffers are a key hardware optimization that creates this problem. They allow
a core to complete a store instruction immediately from its own perspective, even
though the change is not yet visible to others.
●​ Memory Barriers (Fences) are the explicit instructions a programmer (or compiler)
must use to tell the CPU: "Ensure all memory operations before this barrier are
visible to all other cores before any operations after this barrier are performed."

The Journey from Atomic Instructions to Locks

●​ Hardware Atomic Instructions: The foundation. The CPU provides instructions that
are indivisible for simple operations (e.g., atomic increment, compare-and-swap).
These are used to build higher-level synchronization primitives.
●​ Critical Section (CS): Any sequence of instructions that must be executed as if they
were a single, indivisible unit to maintain correctness. This is a code region.
●​ Mutual Exclusion: The property that ensures at most one thread executes in its
critical section at any time. This is a guarantee.
 ●​ Lock (or Mutex): The practical synchronization primitive that provides mutual
exclusion for a critical section. It is a tool.

Designing a solution to the CS problem

●​ Correctness properties (non-negotiable)
○​ Mutual exclusion: At most one thread inside the CS at any time
○​ Progress: If multiple threads attempt to enter the CS, one must be allowed to
proceed (a.k.a. liveness)
○​ Starvation-free: If a thread is waiting to enter the CS, it must eventually enter
(a.k.a. bounded-wait)
●​ Efficiency and Fairness properties (good to have)
●​ Resource-efficiency: Don't waste processor cycles while waiting
(busy-waiting) to enter the CS; voluntarily yield the processor
●​ Fairness: All threads must wait approximately the same amount of time
outside of the CS

Lock: A token-like synchronization primitive used to coordinate concurrent thread

accesses on CS
●​ While a thread cannot acquire the token, it waits until it acquires the token
●​ When a thread acquires the token, it holds it and no other thread can acquire it
●​ When a thread releases the token, any thread can acquire the token

—------------------------------------------------------------------------------------------------------------------------

Lecture 10

Trivial Uniprocessor Lock: On a system with a single CPU and no preemption, no lock is
needed! The thread cannot be interrupted, so mutual exclusion exists. The lock functions are
empty.

Uniprocessor with Preemption: On a single CPU that can preempt, the solution is to
disable preemption inside the critical section. This prevents a context switch at an
inopportune moment. This is a simple but effective lock for kernels.

Multiprocessor (SMP) Spinlock: For multiple CPUs, disabling preemption on one core
doesn't help against threads on other cores. We need a shared variable and an atomic
instruction.

●​ test_and_set Instruction: A hardware atomic instruction that reads a memory

location and sets it to a new value in a single, indivisible step. It returns the old value,
which is used to determine if the lock was acquired.
 ●​ Spinlock: A lock where a thread waits for it to become free by repeatedly checking
(spinning) in a loop. It is efficient for very short critical sections on multiprocessor
systems.
●​ Ticket Lock: A fair variant of a spinlock that ensures threads acquire the lock in the
order they requested it, thus preventing starvation.
●​ Sleeping Lock (Mutex): A lock where a thread that cannot acquire the lock will be
put to sleep (descheduled) and woken up when the lock is released. This is efficient
for longer critical sections.
●​ Lost Wakeup Problem: A concurrency bug where a thread is put to sleep after the
condition it was waiting for has already become true, causing it to potentially sleep
indefinitely. Solved by making the "check condition and sleep" operation atomic.
●​ Contention: The condition that occurs when multiple threads try to acquire the
same lock simultaneously. High contention serializes execution and hurts
performance.

Lock Granularity: The scope of data protected by a single lock.

●​ Coarse-Grained Locking: Using one lock to protect a large amount of data (e.g., a
global lock for an entire hash table). Simple but leads to high contention.
●​ Fine-Grained Locking: Using multiple locks to protect smaller, independent parts of
the data (e.g., a separate lock for each bucket in a hash table). Complex but enables
more parallelism and reduces contention.

Spinlocks: Spin continuously while trying to acquire the lock

●​ Do use when: Cost of 2*context switch > cost of instruction of cs
●​ Do use when: Relatively smaller CS
●​ Do NOT use when: CS contains operations that may sleep
Sleeping locks: Self-preempt and sleep if can't acquire the lock
●​ Do use when: Cost of 2*context switch << cost of instruction of cs
●​ Do use when: Relatively larger CS
●​ Do NOT use when: In interrupt handlers

Lock-Free Programming: A programming paradigm that uses atomic operations (like

Compare-and-Swap) to achieve synchronization without traditional locks. It can offer high
performance and avoid issues like deadlock and priority inversion, but is notoriously difficult
to implement correctly.

—------------------------------------------------------------------------------------------------------------------------

Lecture 11
What is a Deadlock?: A deadlock is a state where a set of threads are all blocked, each
waiting for a resource held by another, creating a circular dependency.

What causes a deadlock (remember MNHC)

●​ Mutual Exclusion: Exclusive access on a shared resource
●​ No preemption: Once the shared resource is obtained by a thread, it cannot be
taken away involuntarily
●​ Hold and Wait: A thread holding a shared resource is also waiting for additional
resources, held by other threads
●​ Circular Wait: There exists a set of waiting threads, T = {T₁, T₂, ...,T }, such that T₁
is waiting for a resource held by T₂, T₂ is waiting for a resource held by T₃, …, and T
is waiting for a resource held by T₁

How to prevent deadlocks (before they happen)? Remove one of the four AND
preconditions
●​ No Mutual Exclusion: No exclusive access on a shared resource
●​ Enable preemption: No thread can hold the shared resource for more than a given
time frame while others are trying to obtain it
●​ Avoid hold and wait: No thread can hold the shared resource while requesting
another, and must, instead, try to obtain all the necessary resources at once, at the
beginning
●​ Avoid circular waiting: Impose a hierarchical ordering on shared resource
acquisition

*The dining philosophers problem (will be on the midterm)*

Problem description: N philosophers sitting around a circular table
●​ Between each pair of philosophers there is a chopstick fork (N total)
●​ Each philosopher alternates between two activities: Thinking and Eating
●​ Rules to eat:
○​ Each philosopher needs two chopsticks to eat
○​ Each philosopher can take either their left or their right chopstick
○​ They cannot pick both chopsticks at once

What Can Go Wrong: (remember DLS)

1.​ Deadlock: Could happen if all philosophers simultaneously pick up their left
chopstick. Now each philosopher holds one chopstick and waits forever for their right
chopstick (which is held by their neighbor). No one can eat.
2.​ Livelock: Could happen if philosophers "politely" put down chopsticks when they
can't get both, then all try again simultaneously, creating an endless cycle of picking
up and putting down without anyone ever eating.
3.​ Starvation: Could happen if some philosophers repeatedly get both chopsticks while
others never succeed, even though the system as a whole makes progress.
The Solution:
1.​ Avoid Deadlocks:
○​ Break circular wait by having at least one philosopher use a different pick up
order
○​ Example: Philosopher N will not pick up chopstick N if chopstick 1 is already
held
2.​ Avoid Livelocks:
○​ Use random/exponential backoff so philosophers don't act in perfect
synchrony
○​ After failing to get both chopsticks, wait a random time before retrying
3.​ Avoid Starvation:
○​ Use a queue or aging/ticket mechanism
○​ Ensure philosophers get a turn based on how long they've been waiting

More Deadlock Prevention Strategies (not on altidakis’s notes):

1.​ Break Circular Wait:
○​ Number resources (chopsticks) and always acquire in increasing order
○​ Have one philosopher use reverse order (e.g., pick up right then left)
2.​ Alternative Approaches:
○​ Allow a philosopher to pick up chopsticks only if both are available (atomic
check)
○​ Use a central arbitrator (waiter) to manage chopstick allocation
○​ Limit the number of philosophers who can eat simultaneously (N-1
philosophers max)

—------------------------------------------------------------------------------------------------------------------------

Quiz 01

1.​
Fault isolation: No
2.​
Preemption: No
3.​
PoLP: No
4.​
This program prints the memory address of local variable x. If the MMU is enabled,
the address will be a virtual address (typically in the user-space range like 0x7fff...). If
the MMU is disabled, the address will be a direct physical address (often a much
lower value).
Remember: MMU -> Hardware that translates virtual addresses to physical addresses.

—------------------------------------------------------------------------------------------------------------------------
 Quiz 04

1)
Case 1: The new thread runs after p = &x in main thread.
Then p points to x (value 3), so printf("%d\n", *p) prints 3.

Case 2: The new thread runs before p = &x in main thread.

Then p is still NULL. Dereferencing NULL causes a segmentation fault (crash).

Case 3:
1.​ Main thread creates the child thread
2.​ Main thread sets p = &x.
3.​ Main thread immediately returns from main → process exits.
4.​ The child thread might not have had time to:
●​ Be scheduled to run at all, or
●​ Reach the printf statement before being killed.
Thus: No output appears.

2), 3) good enough explanation in the quiz 04 answers

—------------------------------------------------------------------------------------------------------------------------

Lecture 16

The Scheduling Problem & Goals

The fundamental problem is deciding how to dispatch k ready tasks to N available
processors. Scheduling is evaluated through two lenses:

●​ Quantitative Goals: Minimizing average completion time (turnaround), minimizing

latency (response time), and maximizing throughput.
●​ Qualitative Goals: Ensuring fairness (similar shares of CPU time), setting upper
bounds on latency, and maintaining a uniform load across processors.

Workload Requirements
Different workloads require different scheduling strategies:

●​ Hard Real-Time: Tasks must finish by strict deadlines (e.g., airbags). Uses Earliest
Deadline First (EDF).
●​ Soft Real-Time: Tasks need priority for performance (e.g., video streaming).
●​ CPU-Bound: Intensive computation tasks. These use Round Robin (RR) with large
time slices to avoid frequent context switches.
●​ I/O-Bound: Tasks that spend most of their time waiting for I/O. The scheduler should
favor these to minimize I/O device idle time.

Earliest Deadline First (EDF): An algorithm for hard real-time systems that prioritizes tasks
with the closest deadlines.

Priority Inversion: A scenario where a high-priority task is indirectly preempted by a

lower-priority task because both share a resource held by an even lower-priority task.

—------------------------------------------------------------------------------------------------------------------------

Lecture 17-18 (Memory Management)

What is virtual memory? A layer of abstraction -Translates virtual addresses into

physical addresses

Why Virtual Memory is Necessary

●​ Fault Isolation
●​ Illusion of continuous memory
●​ Frugal Resource Use:
○​ Demand paging: Postpone allocating physical memory until necessary
○​ Copy-On-Write: One physical replica of common readed-only code
●​ Performance: Programs can have a footprint as large as disk storage but run at
speeds close to CPU caches through locality and prefetching.

Memory Fragmentation

●​ Internal Fragmentation: Unused memory portions located inside a specific allocated

segment or page.
●​ External Fragmentation: Free memory blocks that are available but unusable
because their sizes do not fit the segments being requested.

Implementation Mechanisms

The lecture explores three main ways to implement virtual memory:

 ●​ Segmentation: Memory is divided into variable-sized segments (text, heap, stack). It
is limited by fragmentation (both internal and external).
●​ Single-Level Paging: Memory is divided into fixed-size "pages". However, mapping
a sparse 4GB address space in a 32-bit system would require a massive 4MB flat
array per process.
●​ Multi-Level Hierarchical Paging: Solves the size issue of flat page tables by
creating a hierarchy (e.g., Outer and Inner tables). Only the necessary parts of the
hierarchy need to be stored in physical memory.

Paging Details

●​ Page Table Entry (PTE): The individual index entry in a page table. In x86, it
includes specific status bits:
○​ Present (P): Must be 1 to map the page.
○​ Dirty (D): Indicates software has written to this page.
○​ Accessed (A): Indicates the page has been read or written recently.
●​ PFN (Page Frame Number): The physical address of the 4KB page frame in RAM.
●​ Minor Page Fault: Occurs when the page is in memory but not mapped in the
process's page table (e.g., Copy-On-Write or anonymous pages).
●​ Major Page Fault: Occurs when the page must be fetched from disk or swap space.

Handling Page Faults

When a processor tries to access a virtual address that is not currently mapped to
physical RAM, it triggers a Page Fault. The kernel's exception handler must then
decide whether to:

●​ SIGSEGV: Kill the process if the access is illegal.

●​ Fetch data: Bring the page from disk into RAM (Major Page Fault).
●​ Fix permissions: Handle Copy-On-Write or anonymous page allocation (Minor Page
Fault).

Caching and Locality

●​ Homonym Problem: A security/data leakage risk where, after a context switch, a

process might access leftover cache contents from a previous process.
●​ Synonym Problem (aka Aliasing): When different virtual addresses reference the
same physical data, potentially confusing hardware cache protocols.
●​ Working Set Model: “A process can be in main memory iff all the pages it is
currently using can be in main memory.”
●​ 80/20 Rule: A rule of thumb stating that 20% of memory receives 80% of total
accesses.

Replacement policies

Not all pages are equal: Reclaiming decision is made based on the the type of the occupied
pages
 ●​ File-backed pages: Dropped from the kernel's page cache first since they can be
reloaded later from the corresponding file.
●​ Anonymous pages w/o file backing: Must be written to the swap space in order to
be available for reloading; dropped next
●​ File-system-related kernel caches: Dropped last (next chapter)
●​ Last resort: Out-Of-Memory (OOM) killer terminates the process

Temporal locality states that if a particular memory location is referenced, it is highly likely
that the same location will be referenced again soon after.

Spatial locality states that if a particular memory location is referenced, it is highly likely that
nearby memory locations will be referenced soon after.

Replacement and Recovery

●​ CLOCK Algorithm: An "approximate LRU" (Last Recently Used) algorithm that uses
the "accessed" bit in the PTE to decide which pages to evict.
●​ Thrashing: A state where the system spends all its time swapping pages in and out
of disk; I/O utilization is 100% while CPU utilization drops to 0%.
●​ Out-Of-Memory (OOM) Killer: The kernel's last resort that terminates a process to
reclaim memory when the system is exhausted.
●​ Kernel oops(): A non-recoverable error when a page fault occurs in kernel mode at
an address not in user space.

Memory management syscalls

●​ mmap (void *addr, ...): Creates a new mapping in the virtual address space of the
calling process.
●​ munmap (void *addr, size_t length): Deletes the mappings for the specified
address range.
●​ mprotect (void *addr, size_t len, int prot): Updates the protections for page(s) in
range [addr, addr+len) to "prot".
●​ msync (void *addr, ...): Flushes to disk changes made to the in-kernel copy of a file
that was mapped into memory using mmap.
●​ mlock/unlock (void *addr, …): Locks/unlocks part or all of the calling process's
virtual address space into main mem. preventing that memory from being paged to
the swap area.

The Buddy Allocator: To handle requests for contiguous memory, the kernel uses a
"Buddy" system. It divides memory into power-of-2 blocks (e.g., 4KB, 8KB, 16KB). If a
requested size isn't available, it splits a larger block into two "buddies"

Memory Structures & Allocation

●​ mem_map: A global array where the kernel stores a struct page for every single
physical frame in the system.
●​ Physical Frame Tracking: The kernel tracks the status of physical frames (e.g., free,
reserved, or mapped to a process) using metadata in the struct page.
—------------------------------------------------------------------------------------------------------------------------

Lecture 19

What is a File?
A file is a named, persistent collection of bytes that survives reboots and power
failures.

Types include:
●​ Regular files: Text or binary data.
●​ Special files: Represent devices (e.g., /dev/tty, /dev/sda).
●​ Named pipes: For inter-process communication.
●​ Sockets: For network or local communication.
●​ Directories: Lists of files.
●​ Symbolic links: Shortcuts to other files/directories.

Why Do We Need Files?

●​ Provide persistent storage across system restarts.
●​ Allow data to be identified using human-readable names.
●​ Abstract away details of physical storage devices.

File Metadata (Information stored about each file)

●​ File identifier (e.g., inode in Linux)
●​ Access permissions
●​ Owner and group
●​ Size
●​ Timestamps
●​ Filename

What is a Directory?
A special file that contains a list of <filename, file identifier> pairs.
Directories organize files in a hierarchical, tree-like structure.

What is a POSIX File Descriptor?

A per-process unique integer that identifies an open file.
It makes file access efficient by avoiding repeated name lookups.

How it works:

1.​ Open file → OS stores file info in a system-wide table.

2.​ Process gets an integer (file descriptor) pointing to that entry.
 3.​ Process uses that integer for all subsequent operations (read, write, etc.).

Standard file descriptors:

●​ 0 = standard input
●​ 1 = standard output
●​ 2 = standard error

File-Related POSIX System Calls

●​ int open(const char *pathname, int flags): Opens a file and returns a file descriptor.
●​ int rename(const char *oldpath, const char *newpath): Renames or moves a file.
●​ int unlink(const char *pathname): Removes a file name from the filesystem; deletes
file if it’s the last link.
●​ int truncate(const char *path, off_t length): Resizes a file to a specified length.
●​ ssize_t read(int fd, void *buf, size_t count): Reads data from a file descriptor into a
buffer.
●​ ssize_t write(int fd, const void *buf, size_t count): Writes data from a buffer to a file
descriptor.
●​ off_t lseek(int fd, off_t offset, int whence): Moves the read/write position within a file.
●​ int fsync(int fd): Forces all pending writes to disk.

Safely Updating Files (Crash-Tolerant)

To update a file safely even if the system crashes:
1.​ Write new data to a temporary file.
2.​ Call fsync() on the temporary file.
3.​ Rename the temporary file to the target file (rename is atomic).
4.​ Call fsync() on the parent directory.
5.​ Ensure the temporary file no longer exists.

File Access Patterns

Sequential Access
●​ Data is read/written in order.
●​ Good for prefetching (predicting next reads).
●​ Examples: copying files, compiling code.

Random Access
●​ Reading/writing at arbitrary positions.
●​ Hard to optimize; defeats prefetching.
●​ Examples: database record updates.

—------------------------------------------------------------------------------------------------------------------------
 Lecture 20

Storage Basics
Files = abstraction for persistent data -> Need physical storage (like RAM for memory)

Still slower than Main Memory(RAM) → OS must:

●​ Prefetch data (anticipate reads)
●​ Do I/O asynchronously (hide latency)

Allocating storage space to files

Disk is split into fixed-size blocks.

Allocation strategies:

1. Contiguous Allocation
Allocate a contiguous set of blocks, of sufficient size to each file.
Advantages:
●​ Low storage overhead (just store start block + length)
●​ Fast sequential access (blocks are next to each other)
●​ Easy random access (math: block = start + offset)

Disadvantages:
●​ Hard to grow a file (need continuous space)
●​ External fragmentation (gaps between files)

2. Linked Allocation
Allocate a linked list of blocks, with each block holding a pointer to the next block
(essentially, per-file, an on-disk linked list).
Advantages:
●​ No external fragmentation (use any free block)
●​ Easy to grow files (just add another link)

Disadvantages:
●​ Slow random access (must follow links)
●​ Storage overhead (each block stores a pointer)
●​ Unreliable: lose one block → lose the rest of the file
●​ Can’t cache or optimize access patterns well

3. Indexed Allocation
Use a special index block (inode) to store pointers to the data blocks
Advantages:
●​ No fragmentation
●​ Easy to grow files
●​ Fast random access (all pointers in one place → cache in RAM)
Disadvantages:
●​ Sequential access may be slower (blocks scattered)
●​ Index block has limited size → can’t store pointers for huge files

4. Multi-level Indexed Allocation (Linux ext2/3)

A special type of indexed allocation where the index block (inode) doesn't just point directly
to data blocks—it can also point to more index blocks, creating a tree-like structure.
Advantages:
●​ No fragmentation
●​ Supports huge files (>4 TB)
●​ Fast random & sequential access (with caching)
●​ Index grows dynamically (on demand)

Disadvantages:
●​ More complex to implement
●​ Small overhead per file for indirect pointers
●​ More disk reads for very large files (multiple indirections)

Filesystem Layout
[Superblock] [Bitmap (inodes)] [Bitmap (data)] [Inodes] [Data Blocks]

●​ Superblock = filesystem metadata (root inode location)

●​ Bitmap = tracks free blocks/inodes
●​ Inodes = file metadata (size, pointers, etc.)
●​ Data blocks = actual file content

Paths & Names

●​ Humans use paths (/home/user/[Link])
●​ Filesystem uses inode numbers
●​ Hard link: Associates a name with an inode
●​ Soft link: Associates a name with an inode of a file containing paths to files

Linux Filesystem Data Structures

●​ Open file table (struct file): kernel’s view of open file
●​ Dentry cache: cached path → inode translations
●​ Page cache: cached file data in RAM
●​ Per-process fd table: maps fds (file descriptors) → kernel file objects

Crash Tolerance: Consistent Updates

Problem: Updating a file requires multiple disk writes. Crash → inconsistency.
 Data Bitmap Inode Outcome Explanation
Block Updated? Updated?
Written?

YES NO NO Missed The data hit the disk,

Update but because the
inode wasn't updated
to point to it, the file
system doesn't know
it exists. The update
is effectively lost.

NO YES NO Space Leak The bitmap says the

block is "occupied,"
but no inode points to
it. The file system
cannot use this block
for new files, but it
also can't free it
because it doesn't
know who owns it.

NO NO YES FS The inode points to a

Inconsistent block address, but
the new data wasn't
written there. When
you read the file, you
will read whatever
(Garbage garbage data
Data) happened to be
sitting at that address
on the disk
previously. This is a
severe security and
reliability issue.

Solutions:
●​ Ordered Writes
○​ Ensures inodes never point to uninitialized data!
 ○​ Can leak resources (fixable: run fsck periodically)
○​ Cannot reorder writes and execute asynchronously <= Dealbreaker
●​ Journaling (Write-Ahead Logging)
○​ Write all changes to a log first
○​ Then apply to actual filesystem
○​ If crash: replay log to recover
○​ Used in ext3/4

Fault Tolerance
A system's ability to continue operating correctly despite
hardware failure (i.e., faults) is called fault tolerance.

How to build fault tolerant systems using unreliable hardware?

Redundant Array of Inexpensive Disks (RAID): A technology that combines multiple
physical hard drives into one logical unit to improve:
●​ Performance (speed)
●​ Reliability (fault tolerance)
●​ Capacity (storage space)

RAID Level Mechanisms Explained

●​ RAID 0 (Striping): Splits data into blocks and writes them across multiple disks
simultaneously. This increases speed (throughput) but offers no redundancy.
●​ RAID 1 (Mirroring): Writes an exact copy of the data to two or more disks. If one
fails, the system reads from the surviving copy.
●​ RAID 4 (Dedicated Parity): Stripes data across disks but dedicates one specific disk
solely for parity (error recovery data). If a data disk fails, the parity disk is used to
reconstruct it.
●​ RAID 5 (Distributed Parity): Stripes both data and parity information across all
drives. There is no single "parity disk"; the recovery data is spread out, preventing
the bottleneck of RAID 4.
●​ RAID 6 (Double Distributed Parity): Similar to RAID 5 but calculates two distinct
parity blocks for every data block and distributes them across all drives. This allows
for two simultaneous failures.

RAID Level Comparison Table

RAID Mechanism Min. Fault Fault Tolerance
Level Disks Tolerance(Disks Ranking(Per
that can fail) Document)
RAID Striping ≥2 0 Disks Lowest
0

Splits data (Failure = Data Loss) (Worse than

across disks. single disk)

RAID Mirroring ≥2 1 Disk (per pair) Highest

1

Duplicates data (Or $N-1$ in (> RAID 6)

on drives. $N$-way mirror)

RAID Striping + ≥3 1 Disk Moderate

4 Dedicated
Parity

(> RAID 0)

Parity stored on
one dedicated
drive.

RAID Striping + ≥3 1 Disk Moderate

5 Distributed
Parity

(≈ RAID 4)

Parity spread
across all
drives.
 RAID Striping + ≥4 2 Disks High
6 Double Parity

(> RAID 5, <

Two parity RAID 1)
blocks per
stripe.

—------------------------------------------------------------------------------------------------------------------------

MORE USEFUL STUFF

Quizzes:
●​ [Link]
●​ [Link]

User level thread Kernel level thread

User threads are implemented by user Kernel threads are implemented by the
processes. OS.

The OS doesn’t recognize user level Kernel threads are recognized by the
threads. OS.

Implementation of User threads is easy. Implementation of Kernel thread is

complicated.

Context switch time is less. Context switch time is more.

Context switch requires no hardware Hardware support is needed.

support.
If one user level thread performs a If one kernel thread performs a blocking
blocking operation then the entire operation then another thread can
process will be blocked. continue execution.

Process states:
Ready to Waiting is NOT possible.
Waiting to Running is NOT possible.

Which combination of the following features will suffice to characterize an OS

as a multi-programmed OS?
●​ More than one program may be loaded into main memory at the same time for
execution. ✔
●​ If a program waits for certain events such as I/O, another program is immediately
scheduled for execution. ✔
●​ If the execution of program terminates, another program is immediately scheduled for
execution. X (Done in both Multiprogrammed and single programmed OSs)

Multitasking allows interactive user input, Multiprogramming does not

With Uniprogramming only one process can execute at a time; meanwhile all other
processes are waiting for the processor. With Multiprocessing more than one process can
be running simultaneously each on a different processor.

The return value for fork() is zero for the child process and a nonzero integer for
the parent process.

The child process is a duplicate of the parent process. (when using fork())

User level threads can NOT be scheduled by the kernel.

Bakery algorithm to solve CS problem: each process receives a number (may or may not
be unique) and the one with the lowest number is served next.

If one thread opens a file with read privileges then other threads in the same process can
also read from that file.
A thread is created faster than a process.

When the event for which a thread is blocked occurs, the thread moves to the ready queue.

Termination of the process terminates all threads within the process.

False sharing occurs when multiple threads access different variables that happen to reside
on the same cache line, causing unnecessary cache invalidations.

Processes vs Threads (also see below)

I
I
V

Processes vs Threads: