CS703 — Midterm Summary (Lectures 1–22)

📘 Lecture 1 — Overview of today’s lecture

📖 Overview: This lecture introduces the advanced operating systems course, covering objectives, prerequisites, and the fundamental concepts of operating systems. It explores the dual nature of an OS as both a virtual machine abstraction and a resource manager, and discusses key design issues, types of operating systems, and basic classifications of distributed and parallel systems.

🗂️ Topics Covered

The lecture covers course objectives and prerequisites from a design and research perspective, introduces the definition of an operating system from top-down and bottom-up views, details resource multiplexing techniques, explores major OS issues like structure, sharing, naming, security, and performance, discusses protection and security threats as a case study, and classifies different types of operating systems including mainframe, server, multiprocessor, PC, real-time, and embedded systems. It concludes with an overview of distributed and parallel systems.

📝 Lecture Summary

Course Objectives and Pre-requisites

The course takes an in-depth design perspective, focusing on why things are done in a certain way rather than just how. Students will learn to distinguish between good and bad designs, consider engineering tradeoffs, and understand practical aspects from a computer scientist’s viewpoint. The course includes a case study of the Linux kernel with comparisons to Windows where applicable, along with 4–5 programming assignments for hands-on training in using OS services. From a research perspective, students will read contemporary and classical research literature on OS topics.

🔑 Pre-requisites: Essential requirements are C/C++ programming and an undergraduate course on data structures (lists, stacks, queues, trees). A first course on operating systems is helpful but not strictly required as basics will be covered before deeper topics.

What is an operating system?

From a top-down view, the OS provides an extended or virtual machine abstraction to user programs, making programming easier than dealing directly with hardware. All services are invoked through system calls. From a bottom-up view, the OS acts as a resource manager for processors, memories, timers, disks, network interfaces, and other hardware, managing allocation of these resources to user programs in an orderly and controlled manner.

Resource multiplexing

The OS multiplexes resources in two ways: time multiplexing and space multiplexing. Time multiplexing involves different programs taking turns using a resource, with examples including CPU scheduling and printer sharing. Space multiplexing involves different programs getting a part of the resource, possibly at the same time, with the example of memory being divided among several running programs.

The major OS issues

The key design issues an OS must address include: Structure (how is the OS organized?), Sharing (how are resources shared across users?), Naming (how are resources named?), Security (how is integrity ensured?), Protection (how is one user/program protected from another?), Performance (how do we make it fast?), Reliability (what happens when something goes wrong?), Extensibility (can we add new features?), and Communication (how do programs exchange information, including across a network?).

Additional issues include: Concurrency (how are parallel activities created and controlled?), Scale (what happens as demands or resources increase?), Persistence (how do you make data last longer than program executions?), Distribution (how do multiple computers interact?), and Accounting (how do we track and charge for resource usage?).

💡 Why this matters: These issues represent the fundamental design challenges every OS must solve. Understanding them provides the framework for evaluating any operating system.

Protection and security as an example

Protection exists at multiple levels: from no protection at all, to protecting the OS from user programs, protecting one user's program from another, and protecting a program from itself. Security threats include: access by intruding individuals, access by intruding programs, denial of service (DoS), distributed denial of service (DDoS), spoofing, spam, worms, viruses, Trojan horses (knowingly downloaded bugs), and cookies/spyware (unknowingly downloaded).

Type of Operating Systems

Mainframe operating systems handle huge I/O activity with thousands of disks, providing batch processing (routine non-interactive jobs like claims processing), transaction processing (large numbers of small requests like bank check processing), and time-sharing (multiple remote users running jobs simultaneously, like database queries). Example: OS/390.

Server operating systems run on large PCs, workstations, or mainframes, serving multiple users over a network simultaneously, allowing sharing of hardware and software. Examples include web servers and database transaction servers. OS examples: Win2K, XP, and UNIX flavors.

Multiprocessor operating systems are variations of server operating systems with special provisions for connectivity and communication management between multiple CPUs.

PC operating systems provide a nice interface to a single user, typically used for word processing, spreadsheets, and Internet access.

Real-time operating systems are characterized by time as the key parameter — real-time response to events is more important than any other design goal. They are classified as hard real-time or soft real-time. Example applications: industrial process control, robotics, air traffic control, network routers, multimedia systems.

Embedded operating systems reside in small devices like PDAs, TV sets, microwave ovens, and mobile phones. They have characteristics of real-time systems (mainly soft real-time) with restraints on power consumption and memory usage. Examples: PalmOS, Windows CE. The pinnacle is smart-card systems.

Distributed Systems

Distributed systems distribute computation among several physical processors in a loosely coupled system, where each processor has its own local memory and processors communicate through communications lines (high-speed buses or telephone lines). Advantages include: resource sharing, computation speed-up through load sharing, reliability, and communications.

Parallel Systems

Parallel systems are multiprocessor systems with more than one CPU in close communication, forming a tightly coupled system where processors share memory and a clock, with communication through shared memory. Advantages include: increased throughput, economical benefits, increased reliability, graceful degradation, and fail-soft systems.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) The OS serves dual roles as both a virtual machine abstraction making hardware easier to program and a resource manager multiplexing resources in time and space. (2) The major design issues span structure, sharing, naming, security, protection, performance, reliability, extensibility, communication, concurrency, scale, persistence, distribution, and accounting. (3) Operating systems are classified into mainframe, server, multiprocessor, PC, real-time, embedded, distributed, and parallel types, each optimized for different workloads and constraints. (4) Protection and security exist at multiple levels, from protecting the OS from programs to defending against viruses, worms, and denial of service attacks. (5) Distributed systems are loosely coupled with independent memory, while parallel systems are tightly coupled with shared memory — each offering different advantages for computation and reliability.

🧠 Quick Revision Questions

1. What are the two views of an operating system, and what does each view emphasize?
2. Explain the difference between time multiplexing and space multiplexing with examples.
3. List at least six of the major OS design issues discussed in the lecture.
4. What is the key characteristic that distinguishes real-time operating systems from other types, and what are its two sub-categories?
5. What is the primary difference between a distributed system and a parallel system in terms of memory and communication?

📘 Lecture 2 — Overview of today’s lecture

📖 Overview: This lecture provides a comprehensive overview of the major components of an operating system, including process management, memory management, I/O, and file systems. It also explores different operating system architectures—monolithic, layered, microkernel, and virtual machine monitors—highlighting their trade-offs in performance, reliability, and complexity.

🗂️ Topics Covered

This lecture covers major OS components such as process management, memory management, I/O, secondary storage, file system, protection, accounting, shell, GUI, and networking. It then examines OS structure and internal architecture, comparing monolithic design, layering, microkernels, and virtual machine monitors. The lecture concludes with a re-cap of key structural design considerations.

📝 Lecture Summary

Major OS Components

The operating system consists of several major components that manage different aspects of the computer system. These include process management, memory management, I/O (input/output), secondary storage, file system, protection, accounting, shell (OS user interface), GUI (graphical user interface), and networking. Each component performs a specialized function that together enables the OS to manage hardware and provide services to user programs.

Process Operation

The OS provides a process abstraction interface that defines standard operations on processes. These operations include: create a process, delete a process, suspend a process, resume a process, clone a process, inter-process communication, inter-process synchronization, and create/delete a child process. These operations form the basic API for process management.

I/O

A large portion of the OS kernel deals with I/O—Windows XP contains millions of lines of code, including drivers. The OS provides a standard interface between programs and devices. Device drivers are routines that interact with specific device types; they encapsulate device-specific knowledge such as how to initialize a device, how to request I/O, and how to handle interrupts and errors. Examples include SCSI device drivers, Ethernet card drivers, video card drivers, and sound card drivers. Windows has approximately 35,000 device drivers.

Secondary Storage

Secondary storage (disk, tape) is persistent memory, often using magnetic media that survives power failures. Routines that interact with disks operate at a very low level in the OS and are used by many components. They handle scheduling of disk operations, head movement, error handling, and management of space on disk. These routines are usually independent of the file system, although cooperation can exist—file system knowledge of device details can help optimize performance, such as placing related files close together on disk.

File System

Secondary storage devices are crude and awkward to use directly (e.g., writing a 4096-byte block to a sector). File systems provide a convenient abstraction. A file is the basic long-term storage unit, and a directory is just a special kind of file.

🔑 Definition — File: The basic long-term storage unit managed by the file system.

Command interpreter (shell)

The command interpreter (shell) is a particular program that handles the interpretation of user commands and helps manage processes. On some systems, the command interpreter may be a standard part of the OS; on others, it is just non-privileged code that provides an interface to the user; on others, there may be no command language at all.

File system operations

The file system interface defines standard operations including file (or directory) creation and deletion, manipulation of files and directories, copy, and lock operations. File systems also provide higher-level services such as accounting and quotas, backup, indexing or search, and file versioning.

Accounting

The accounting component keeps track of resource usage, both to enforce quotas (e.g., "you're over the disk limit") or to produce bills. This is important for time-shared computers like mainframes.

Networking

An OS typically has a built-in communication infrastructure that implements: a network protocol software stack, a route lookup module to map a given destination address to a next hop, and a name lookup service to map a given name to a destination machine.

OS structure

It is not always clear how to stitch OS modules together. An OS consists of all these components plus many other components and system programs (e.g., bootstrap code, the init program). Major issues include: How do we organize all this? What are all the code modules, and where do they exist? How do they cooperate? This is a massive software engineering and design problem—designing a large complex program that performs well, is reliable, is extensible, and is backwards compatible.

Early structure: Monolithic

Traditionally, operating systems like UNIX and DOS were built as a monolithic entity where all OS components run in kernel mode.

Monolithic Design advantages:

• Cost of module interaction is low

Disadvantages:

• Hard to understand
• Hard to modify
• Unreliable
• Hard to maintain

The alternative is to find ways to organize the OS to simplify its design and implementation.

Layering

The traditional alternative approach is layering, which implements the OS as a set of layers, where each layer presents an enhanced virtual machine to the layer above. The first described layered system was Dijkstra's THE system, with layers: Layer 5 (job managers), Layer 4 (device managers), Layer 3 (console manager), Layer 2 (pager manager), Layer 1 (Kernel), Layer 0 (Hardware).

🔑 Definition — Layering: An OS design where the system is implemented as a set of layers, each presenting an enhanced virtual machine to the layer above.

Problems with layering: Layering imposes a hierarchical structure, but real systems are more complex. For example, the file system requires VM services (buffers), while VM would like to use files for its backing store. Strict layering is not flexible enough and causes poor performance because each layer crossing has overhead. There is a disjunction between model and reality—systems are modeled as layers but not really built that way.

Microkernel's

Microkernels became popular in the late 80's and early 90's, with a recent resurgence for small devices. The goal is to have minimum functionality in the kernel, with most OS functionality in user-level servers (e.g., file servers, terminal servers, memory servers). Each part becomes more manageable, and crashing of one service doesn't bring the system down.

• This results in better reliability (isolation between components)
• Ease of extension and customization
• Poor performance (due to user/kernel boundary crossing)

The kernel provides basic primitives such as transport of messages, loading programs into memory, and device handling. Policy decisions are made in user space while mechanisms are implemented in the microkernel. The microkernel lends itself well to object-oriented design principles and component-based design.

Disadvantage: Performance. Solutions: Reduce microkernel size or increase microkernel size.

💡 Why this matters: The microkernel architecture fundamentally trades performance for reliability and modularity—a key design decision in modern embedded and secure systems.

Virtual Machine Monitors

Virtual Machine Monitors (VMMs) export a virtual machine to user programs that resembles hardware. A virtual machine consists of all hardware features including user/kernel modes, I/O, interrupts, and everything a real machine has. A virtual machine may run any OS. Examples include Java Virtual Machine (JVM), VMware, and User-Mode Linux (UML).

• Advantage: Portability
• Disadvantage: Slow speed

💡 Why this matters: VMMs enable running multiple operating systems on a single physical machine, which is foundational to cloud computing and server virtualization.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) An operating system consists of many major components including process management, memory management, I/O, secondary storage, file system, protection, accounting, shell, GUI, and networking—each with specific responsibilities. (2) OS structure designs involve critical trade-offs: monolithic designs offer low module interaction cost but are hard to maintain, while layered designs provide structure but suffer from performance overhead and inflexibility. (3) Microkernels improve reliability and extensibility by putting most OS functionality in user-level servers, but the user/kernel boundary crossing significantly degrades performance. (4) Virtual Machine Monitors allow running any OS on a virtualized hardware platform, offering portability at the cost of speed. (5) The core software engineering challenge is designing a large complex OS program that simultaneously achieves good performance, reliability, extensibility, and backwards compatibility.

🧠 Quick Revision Questions

1. List at least five major components of an operating system and briefly describe the function of each.
2. What are the advantages and disadvantages of a monolithic OS design compared to a microkernel design?
3. What specific problem with strict layering does the example of "file system requires VM services, but VM needs files for backing store" illustrate?
4. In a microkernel architecture, where are policy decisions made versus where are mechanisms implemented?
5. What is the primary advantage and the primary disadvantage of using a Virtual Machine Monitor (VMM)?

📘 Lecture 3 — Overview of today’s lecture

📖 Overview: This lecture examines the ELF object file format in detail, explaining how object files are structured into sections and headers. It then covers the crucial processes of symbol relocation, external reference resolution, and static and shared library mechanisms in linking. Understanding these concepts is essential for grasping how programs are built from multiple source files into executable binaries.

🗂️ Topics Covered

The lecture begins with the ELF object file format, detailing the ELF header, program header table, and all key sections (.text, .data, .bss, .symtab, .rel.text, .rel.data, .debug). It uses an example C program to illustrate relocating symbols and resolving external references, showing relocation info for both .text and .data sections, and the merged executable output. The discussion covers merging relocatable object files into executables, strong and weak symbols with linker rules, linker puzzles, packaging commonly used functions via static libraries (.a archives), creating and using static libararies, linker algorithms for resolving references, disadvantages of static libraries, and finally shared libraries (DLLs) with dynamic linking mechanisms.

📝 Lecture Summary

[ELF Object File Format]

The ELF (Executable and Linkable Format) object file is structured into several key components. The Elf header contains metadata including the magic number (identifying the file as ELF), type (relocatable .o, executable, or shared .so), machine architecture, and byte ordering (endianness). The program header table specifies memory segments: page size, virtual addresses, and segment sizes for loading. The .text section holds the program code. The .data section contains initialized static data (global variables with initial values). The .bss section holds uninitialized static data — interpreted as "Block Started by Symbol" or humorously "Better Save Space" — it has a section header but occupies no space in the file. The .symtab section is the symbol table, listing procedure and static variable names along with section names and locations. The .rel.text section contains relocation info for .text: addresses of instructions that will need modification in the executable and instructions for how to modify them. The .rel.data section holds relocation info for .data: addresses of pointer data that need modification in the merged executable. The .debug section provides info for symbolic debugging (generated with gcc -g).

[Example C Program]

The lecture presents an example C program but does not show the full source code; instead, it proceeds directly to the relocation info for the object files.

[Relocating Symbols and Resolving External References]

Symbols are lexical entities that name functions and variables. Each symbol has a value (typically a memory address). Code consists of symbol definitions and symbol references. References can be either local (within the same file) or external (referring to symbols defined in other files).

🔑 Definition — Symbol: A lexical entity that names a function or variable, having a value (typically a memory address).

[m.o Relocation Info]

The lecture shows relocation info for m.o in a table format. The table includes columns for Offset (hexadecimal addresses like 0x0, 0x4, 0x5, 0x7, 0x8, 0x9, 0xa, 0xc), Type (R_386_32 or R_386_PC32), and Symbol (such as array, swap, .text, buf, bufp0, count). For example, at offset 0x0: Type R_386_32, Symbol array; at offset 0x4: Type R_386_PC32, Symbol swap; at offset 0x7: Type R_386_PC32, Symbol .text; at offset 0x8: Type R_386_32, Symbol buf; etc. The relocation information tells the linker which addresses need modification when combining object files.

[a.o Relocation Info (.text)]

The lecture presents relocation info for the .text section of a.o. The table shows Offset values (0x0, 0x5, 0x7, 0x8, 0xb, 0xc, 0xd, 0xe, 0x12, 0x1c), Type (R_386_PC32 or R_386_32), and Symbol (including _init, libc_init_first, atexit, main, _exit, bufp0, count, buf). For example: at offset 0x0: Type R_386_PC32, Symbol _init; at offset 0x5: Type R_386_PC32, Symbol libc_init_first; at offset 0x7: Type R_386_PC32, Symbol atexit; at offset 0x8: Type R_386_PC32, Symbol main; at offset 0xb: Type R_386_PC32, Symbol _exit; at offset 0xc: Type R_386_32, Symbol bufp0; etc.

[a.o Relocation Info (.data)]

The lecture shows relocation info for the .data section of a.o. The table has Offset (0x0, 0x4), Type (R_386_32 for both), and Symbol (buf and bufp0). This tells the linker to resolve references to buf and bufp0 in the data section.

[Executable after Relocation and External Reference Resolution (.text)]

The lecture shows the merged executable's .text section after relocation. It contains a startup sequence: at address 0x080480c0 <start>:

• call libc_init_first
• call _init
• call atexit
• call main
• call _exit

Note: The code that pushes arguments for each function is not shown.

[Executable After Relocation and External Reference Resolution (.data)]

The lecture shows a table for the merged executable's .data section with Address (e.g., memory addresses) and Initial Value for symbols like buf, bufp0, and count. For example, buf (16-byte array at address 0x08049010 with hex initial values) and bufp0 (initial pointer value pointing somewhere, e.g., 0x08049010).

[Merging Relocatable Object Files into an Executable Object File]

The lecture includes a diagram but no additional explanatory text. The concept is that the linker merges the sections from all input relocatable object files into a single executable, resolving all symbol references and performing relocation.

[Strong and Weak Symbols]

Program symbols are classified as either strong or weak. Strong symbols are procedures (functions) and initialized global variables. Weak symbols are uninitialized global variables. The Linker's Symbol Rules are:

• Rule 1: A strong symbol can only appear once.
• Rule 2: A weak symbol can be overridden by a strong symbol of the same name. References to the weak symbol resolve to the strong symbol.
• Rule 3: If there are multiple weak symbols, the linker can pick an arbitrary one.

🔑 Definition — Strong symbol: Procedures and initialized globals. 🔑 Definition — Weak symbol: Uninitialized globals.

📌 Example (implicit from rule 2): If file1.c defines int x = 5; (strong) and file2.c defines int x; (weak), the linker resolves all references to x to the strong definition with value 5.

[Linker Puzzles]

The lecture presents a slide titled "Linker Puzzles" but does not provide the specific puzzle content in the text. This section highlights common pitfalls that arise from the strong/weak symbol rules, such as accidental name collisions and unexpected behavior when global variables are declared multiple times.

[Packaging Commonly Used Functions]

How to package functions commonly used by programmers (e.g., Math, I/O, memory management, string manipulation)? The linker framework has awkward trade-offs:

• Option 1: Put all functions in a single source file. Programmers link a big object file into their programs, which is space and time inefficient.
• Option 2: Put each function in a separate source file. Programmers explicitly link appropriate binaries into their programs. This is more efficient but burdensome on the programmer.

The solution is static libraries (.a archive files): Concatenate related relocatable object files into a single file with an index (called an archive). Enhance the linker so it tries to resolve unresolved external references by looking for symbols in one or more archives. If an archive member file resolves a reference, link it into the executable.

[Static Libraries (archives)]

Static libraries further improve modularity and efficiency by packaging commonly used functions [e.g., C standard library (libc), math library (libm)]. The linker selects only the .o files in the archive that are actually needed by the program. Creating static libraries uses an archiver (e.g., ar) which allows incremental updates: recompile a function that changes and replace its .o file in the archive. Commonly used libraries include:

• libc.a (the C standard library) — 8 MB archive of 900 object files; provides I/O, memory allocation, signal handling, string handling, data and time, random numbers, integer math.
• libm.a (the C math library) — 1 MB archive of 226 object files; provides floating point math (sin, cos, tan, log, exp, sqrt, ...).

[Using Static Libraries]

The linker's algorithm for resolving external references is:

1. Scan .o files and .a files in command line order.
2. During the scan, keep a list of the current unresolved references.
3. As each new .o or .a file is encountered, try to resolve each unresolved reference against the symbols in that file.
4. If any entries remain in the unresolved list at end of scan, then error.

The problem with this algorithm is that command line order matters! The moral: put libraries at the end of the command line.

[Shared Libraries]

Static libraries have several disadvantages:

• Potential for duplicating lots of common code in the executable files on a filesystem (e.g., every C program needs the standard C library).
• Potential for duplicating lots of code in the virtual memory space of many processes.
• Minor bug fixes of system libraries require each application to explicitly relink.

The solution is shared libraries (also called dynamic link libraries or DLLs), whose members are dynamically loaded into memory and linked into an application at run-time. Dynamic linking can occur:

• When the executable is first loaded and run — common case for Linux, handled automatically by ld-linux.so.
• After the program has begun — in Linux, done explicitly by the user with dlopen(). This is the basis for High-Performance Web Servers.

Shared library routines can be shared by multiple processes.

📐 Formula / Mechanism: Dynamic linking → Library code loaded at run-time, not linked at compile-time. 💡 Why this matters: Shared libraries reduce disk and memory usage, allow independent updates to libraries without relinking applications, and enable runtime extensibility.

[Dynamically Linked Shared Libraries]

The lecture includes a diagram showing how dynamically linked shared libraries appear in the linking and loading process. The key concept is that the executable contains only stubs or pointers to shared library functions, which are resolved by the dynamic linker at load time.

[The Complete Picture]

The lecture shows the complete startup sequence for a C program:

• Start-up code in init segment (same for all C programs)
• At address 0x080480c0 <start>:
  1. call libc_init_first (startup code in .text)
  2. call _init (startup code in .init)
  3. call atexit (startup code in .text)
  4. call main (application's entry point)
  5. call _exit (return control to OS)

Note: The code that pushes the arguments for each function is not shown.

⭐ Key Takeaways

The ELF object file format is a fundamental concept — students must know the purpose of each section (especially .text, .data, .bss, .symtab, .rel.text, .rel.data) and the ELF header fields. Symbol relocation and external reference resolution are critical processes that the linker performs to combine object files into executables using relocation information (offsets, types, and symbol names). The distinction between strong symbols (procedures and initialized globals) and weak symbols (uninitialized globals), along with the three linker rules, is essential because they determine how the linker handles multiple definitions and are a common source of linker errors. Static libraries (.a archives) improve modularity by allowing the linker to select only needed object files, but command-line order matters for resolution. Finally, shared libraries (DLLs) overcome static library disadvantages by enabling dynamic linking at load time or runtime (via ld-linux.so and dlopen()), reducing duplication and allowing independent updates.

🧠 Quick Revision Questions

1. What information is stored in the ELF header, and what is the purpose of the .bss section?
2. What is the difference between a strong symbol and a weak symbol in the context of linking?
3. What are the three linker rules for handling strong and weak symbols?
4. How does the linker resolve external references when processing static libraries (.a archives), and why does command-line order matter?
5. What are two mechanisms by which dynamic linking of shared libraries can occur, and what are the key advantages of shared libraries over static libraries?

📘 Lecture 4 — Overview of today’s lecture

📖 Overview: This lecture introduces the fundamental concept of a process, its address space, and how the operating system manages multiple processes. It explains how the CPU's control flow is altered through exceptions, interrupts, traps, and faults, and describes the mechanisms for context switching and process state management. Understanding these concepts is critical for grasping how OSes achieve multitasking and resource management.

🗂️ Topics Covered

The lecture covers the definition of a process, private address spaces and their components, methods of executing the operating system (non-process kernel, execution within user processes, process-based OS), mechanisms for altering CPU control flow including interrupts, traps, faults, and aborts with examples. It also details context switching, process creation, and process state models including the two-state and five-state models with their transitions.

📝 Lecture Summary

Process

A process is defined as a program in execution — an instance of a program running on a computer. It is the entity that can be assigned to and executed on a processor. More formally, a process is a unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system instructions.

🔑 Definition — Process: A program in execution; an instance of a program running on a computer; the entity that can be assigned to and executed on a processor.

Private Address Spaces

Each process has its own private address space. This means that processes do not share memory with each other unless explicitly arranged. The address space contains all the memory locations a process can reference, including its code, data, heap, and stack.

💡 Why this matters: Private address spaces provide isolation between processes — if one process crashes, it does not affect others. This is a foundation of modern OS reliability and security.

Implementing the Process Abstraction

The OS must maintain data structures to manage processes, including:

• Process Control Block (PCB) – contains all information about a process
• Address space – the memory layout for the process
• Registers – saved when a process is not running

The Address Space

The address space of a process typically contains:

• Program code (instructions)
• Global variables (data segment)
• Heap (dynamically allocated memory)
• Stack (function call frames, local variables)

Execution of the Operating System

Three approaches exist for executing OS code:

• Non-process Kernel: Execute kernel outside of any process. OS code is executed as a separate entity that operates in privileged mode.
• Execution Within User Processes: OS software runs within the context of a user process. The process executes in privileged mode when executing OS code.
• Process-Based Operating System: Implement the OS as a collection of system processes. Useful in multi-processor or multi-computer environments.

Control Flow

Computers do only one thing: from startup to shutdown, a CPU simply reads and executes a sequence of instructions, one at a time. This sequence is the system's physical control flow (or flow of control).

Altering the Control Flow

Two basic mechanisms available to the programmer for changing control flow:

1. Jumps and branches
2. Function call and return using the stack discipline

Both react to changes in program state only — they are insufficient for reacting to changes in system state such as:

• Data arriving from a disk or a network adapter
• Instruction dividing by zero
• User hitting Ctrl-C at the keyboard
• System timer expiring

The system needs mechanisms for exceptional control flow.

Exceptional Control Flow

Mechanisms for exceptional control flow exist at all levels of a computer system.

• Low level Mechanism: Exceptions — change in control flow in response to a system event (i.e., change in system state). This is a combination of hardware and OS software.
• Higher Level Mechanisms: Process context switch, Signals, Nonlocal jumps (setjmp/longjmp). Implemented by either OS software (context switch and signals) or C language runtime library (nonlocal jumps).

System context for exceptions

Exceptions

An exception is a transfer of control to the OS in response to some event (i.e., change in processor state).

Asynchronous Exceptions (Interrupts)

Caused by events external to the processor:

• Indicated by setting the processor's interrupt pin
• Handler returns to "next" instruction

Examples:

• I/O interrupts: hitting Ctrl-C at the keyboard, arrival of a packet from a network, arrival of a data sector from a disk
• Hard reset interrupt: hitting the reset button
• Soft reset interrupt: hitting Ctrl-Alt-Delete on a PC

Interrupt Vectors

• Each type of event has a unique exception number k
• Index into a jump table (a.k.a., interrupt vector)
• Jump table entry k points to a function (exception handler)
• Handler for k is called each time exception k occurs

Synchronous Exceptions

Caused by events that occur as a result of executing an instruction:

• Traps: Intentional. Examples: system calls, breakpoint traps, special instructions. Returns control to "next" instruction.

• Faults: Unintentional but possibly recoverable. Examples: page faults (recoverable), protection faults (unrecoverable). Either re-executes faulting ( "current" instruction) or aborts.

• Aborts: Unintentional and unrecoverable. Examples: parity error, machine check. Aborts current program.

🔑 Definition — Trap: An intentional synchronous exception, such as a system call, that returns control to the next instruction. 🔑 Definition — Fault: An unintentional but possibly recoverable synchronous exception, such as a page fault. 🔑 Definition — Abort: An unintentional and unrecoverable synchronous exception that terminates the current program.

Trap Example — Opening a File

1. User calls open(filename, options)
2. Function open executes system call instruction int
3. OS must find or create file, get it ready for reading or writing
4. Returns integer file descriptor

📌 Example: When a user program calls open("data.txt", O_RDONLY), this triggers a trap. The CPU switches to kernel mode, the OS finds the file "data.txt" on disk, checks permissions, and returns a file descriptor (e.g., 3) that the program uses for subsequent read/write operations.

Fault Example #1 — Memory Reference (Recoverable)

1. User writes to a memory location
2. That portion (page) of user's memory is currently on disk
3. Page handler must load page into physical memory
4. Returns to faulting instruction
5. Successful on second try

📌 Example: A program tries to access address 0x8049600, but that page is currently swapped to disk. The MMU triggers a page fault. The OS's page fault handler loads the page from disk into physical RAM (e.g., at frame 42), updates the page table, and returns to re-execute the same instruction — this time it succeeds.

Fault Example #2 — Memory Reference (Unrecoverable)

1. User writes to a memory location
2. Address is not valid
3. Page handler detects invalid address
4. Sends SIGSEGV signal to user process
5. User process exits with "segmentation fault"

📌 Example: A program dereferences a null pointer: *ptr = 5; where ptr = NULL. The address 0x00000000 is not mapped in the process's address space. The OS's fault handler detects an invalid address, sends signal SIGSEGV (segmentation violation), and the process terminates with an error message.

The Abstract Machine Interface

This interface defines how user programs interact with the OS through exceptions and system calls.

Context Switching

Context switching is the mechanism by which the OS switches the CPU from executing one process to another. This involves saving the state (registers, program counter) of the current process and restoring the state of the next process to run.

🔑 Definition — Context Switching: The process of saving the state of the currently running process and restoring the state of another process to resume its execution.

When to Switch a Process

• Clock interrupt: Process has executed for the maximum allowable time slice
• I/O interrupt
• Memory fault: Memory address is in virtual memory so it must be brought into main memory
• Trap: Error or exception occurred — may cause process to be moved to Exit state
• Supervisor call: Such as file open

Process Creation

Steps for creating a new process:

1. Assign a unique process identifier
2. Allocate space for the process
3. Initialize process control block
4. Set up appropriate linkages (e.g., add new process to linked list used for scheduling queue)
5. Create or expand other data structures (e.g., maintain an accounting file)

Change of Process State

Steps when a process changes state:

1. Save context of processor including program counter and other registers
2. Update the process control block of the process that is currently in the Running state
3. Move process control block to appropriate queue – ready; blocked; ready/suspend
4. Select another process for execution
5. Update the process control block of the process selected
6. Update memory-management data structures
7. Restore context of the selected process

Two-State Process Model

A process may be in one of two states:

• Running: Currently being executed by the CPU
• Not-running: Not currently being executed — waiting to be scheduled

Not-Running Process in a Queue

Processes in the Not-running state are kept in a queue. When the scheduler decides to run a new process, it selects one from this queue, moves it to Running, and performs a context switch.

Five-state Model

Processes may be waiting for I/O. The model uses additional states:

• Running: Currently being run
• Ready: Ready to run
• Blocked: Waiting for an event (e.g., I/O)
• New: Just created, not yet admitted to set of runnable processes
• Exit: Completed/error exit

May have separate waiting queues for each event.

Five-State Model Transitions:

• Null → New: Process is created
• New → Ready: OS is ready to handle another process (Memory, CPU)
• Ready → Running: Select another process to run
• Running → Exit: Process has terminated
• Running → Ready: End of time slice or higher-priority process is ready
• Running → Blocked: Process is waiting for an event (I/O, Synchronization)
• Blocked → Ready: The event a process is waiting for has occurred — can continue
• Ready → Exit: Process terminated by OS or parent
• Blocked → Exit: Same reasons as above

📌 Example: A process is in the Running state reading data from a disk file. The read() system call triggers an I/O operation. The process cannot continue until data arrives, so the OS moves it from Running → Blocked. When the disk controller signals completion via an interrupt, the OS moves it from Blocked → Ready. When the scheduler picks it again, it goes from Ready → Running.

⭐ Key Takeaways

The lecture establishes that a process is a program in execution with its own private address space, and the OS must manage multiple processes through context switching and process state models. The CPU's normal sequential control flow is altered by exceptions — asynchronous exceptions (interrupts) from external devices and synchronous exceptions (traps, faults, aborts) caused by executing instructions. The five-state model (New, Ready, Running, Blocked, Exit) with its defined transitions is the standard framework for understanding process lifecycles, and context switching (saving/restoring process state) is the fundamental mechanism enabling multitasking.

🧠 Quick Revision Questions

1. What are the three approaches for executing the operating system, and when is each approach most appropriate?
2. Explain the difference between a trap, a fault, and an abort — provide one example of each.
3. List the seven steps involved in a process state change (context switch).
4. Draw and describe the five-state process model — what are all five states and all nine possible transitions?
5. What is the difference between an asynchronous exception (interrupt) and a synchronous exception? Give at least two examples of each type.

📘 Lecture 5 — Overview of today’s lecture

📖 Overview: This lecture continues the discussion on process management models and state machines, introducing the concept of process suspension. It details the contents of a Process Control Block (PCB) and examines the operating system control structures (memory, I/O, file tables). The lecture also provides a comprehensive overview of UNIX system calls for process management, including fork, exit, wait, and exec, with practical examples.

🗂️ Topics Covered

This lecture begins with a review of previous process states and then introduces a four-state model that includes suspend states (Ready Suspend and Blocked Suspend). It covers the detailed components of a Process Control Block, including process identification, processor state information (registers, stack pointers), and process control information (scheduling, data structuring, IPC, privileges). The lecture then shifts to UNIX SVR4 process states and modes of execution (user mode vs. kernel mode). Finally, it presents a series of example programs that demonstrate the use of key UNIX system calls: fork for creating processes, exit for destroying them, wait/waitpid for synchronization, and exec for running new programs, along with explanations of zombie processes and reaping.

📝 Lecture Summary

Re-view of the previous lecture

The lecture begins with a brief review of foundational concepts from the previous session, including process management models and state machines, setting the stage for the introduction of more advanced states.

Process management models and state machines (cont‘d from the previous lecture)

Suspending Processes

Suspending a process involves swapping part or all of it to disk. This is most useful when waiting for an event that will not arrive soon (e.g., a printer or keyboard). If not done well, it can slow the system down by increasing disk I/O activity. The state transition diagram includes four key states:

• Ready – In memory, ready to execute
• Blocked – In memory, waiting for an event
• Blocked Suspend – On disk, waiting for an event
• Ready Suspend – On disk, ready to execute

💡 Why this matters: The suspend states allow the operating system to free up main memory for other processes by temporarily moving blocked or ready processes to disk, improving overall system utilization.

Unix SVR4 Processes

UNIX SVR4 uses 9 process states. The "Preempted" and "Ready to run, in memory" states are nearly identical; a process may be preempted for a higher-priority process at the end of a system call. A Zombie state saves information to be passed to the parent of this process. Process 0 is the Swapper, created at boot. Process 1 is Init, which creates other processes.

What is in a process control block

Modes of Execution

There are two modes of execution:

• User mode: A less-privileged mode where user programs typically execute.
• System mode, control mode, or kernel mode: A more-privileged mode where the kernel of the operating system executes.

Operating System Control Structures

The operating system maintains information about the current status of each process and resource through tables constructed for each entity it manages:

• Memory Tables: Manage allocation of main memory and secondary memory to processes, protection attributes for shared memory, and information for virtual memory.
• I/O Tables: Track whether an I/O device is available or assigned, the status of an I/O operation, and the location in main memory used as source/destination for the I/O transfer.
• File Tables: Maintain information about the existence of files, their location on secondary memory, current status, and attributes (sometimes managed by a file management system).

Process Control Block

The Process Control Block (PCB) contains three main categories of information:

1. Process Identification Includes numeric identifiers such as:

• Identifier of this process
• Identifier of the process that created this process (parent process)
• User identifier

2. Processor State Information Includes:

• User-Visible Registers: Registers that may be referenced by the machine language while in user mode (typically 8 to 32, but some RISC implementations have over 100).
• Control and Status Registers: These control the operation of the processor, including:
  • Program counter: Contains the address of the next instruction to be fetched
  • Condition codes: Result of the most recent arithmetic or logical operation (e.g., sign, zero, carry, equal, overflow)
  • Status information: Includes interrupt enabled/disabled flags, execution mode
• Stack Pointers: Each process has one or more LIFO system stacks. A stack stores parameters and calling addresses for procedure and system calls. The stack pointer points to the top of the stack.

3. Process Control Information Includes:

• Scheduling and State Information: Needed by the OS to perform scheduling. Typical items include:
  • Process state: Defines readiness (e.g., running, ready, waiting, halted)
  • Priority: One or more fields for scheduling priority (e.g., default, current, highest-allowable)
  • Scheduling-related information: Depends on the scheduling algorithm (e.g., time waited, time executed)
  • Event: Identity of event the process awaits before resuming
• Data Structuring: A process may be linked to others in a queue, ring, or parent-child relationship. The PCB may contain pointers to other processes.
• Inter-process Communication: Various flags, signals, and messages associated with communication between two independent processes may be maintained in the PCB.
• Process Privileges: Processes are granted privileges regarding memory access, instruction types, and use of system utilities and services.

🔑 Definition — Process Control Block (PCB): A data structure in the operating system kernel that contains all information needed to manage a particular process, including its identification, processor state, and control information.

Operating system calls for process management in UNIX family of systems

Example programs invoking OS services for process management

fork: Creating new processes

The fork system call creates a new process (child process) that is identical to the calling process (parent process). It returns 0 to the child process and returns the child's PID to the parent process.

📐 Formula: int fork(void) → Creates a new process. Returns 0 to child, child's PID to parent, or -1 on error.

Fork Example #1: Parent and child both run the same code. They distinguish parent from child by the return value from fork. Both start with the same state, but each has a private copy, including a shared output file descriptor. The relative ordering of their print statements is undefined.

Fork Examples #2–5: In each of these examples, both parent and child can continue forking, demonstrating the recursive nature of process creation.

exit: Destroying Process

The exit system call terminates a process. It normally returns with status 0. The atexit() function registers functions to be executed upon exit.

📐 Formula: void exit(int status) → Terminates the calling process. Status 0 indicates normal termination.

Zombies

When a process terminates, it still consumes system resources (various tables maintained by the OS). This state is called a zombie—a living corpse, half alive and half dead. Reaping is performed by the parent on a terminated child. The parent is given exit status information, and the kernel then discards the process. If any parent terminates without reaping a child, the child will be reaped by the init process. Explicit reaping is only needed for long-running processes (e.g., shells and servers).

Zombie Example: The ps command shows a child process as "defunct." Killing the parent allows the child to be reaped.

Non-terminating Child Example: A child process can still be active even though the parent has terminated. It must be killed explicitly, or it will keep running indefinitely.

wait: Synchronizing with children

The wait system call suspends the current process until one of its children terminates. The return value is the PID of the child process that terminated. If child_status != NULL, the object it points to will be set to a status indicating why the child terminated.

📐 Formula: int wait(int *child_status) → Suspends calling process until a child terminates. Returns child's PID. Status information is stored in child_status.

Wait Example: If multiple children complete, they are taken in arbitrary order. Macros WIFEXITED and WEXITSTATUS can be used to get information about the exit status.

Waitpid

The waitpid system call can wait for a specific process and supports various options.

📐 Formula: waitpid(pid, &status, options) → Waits for a specific child process with the given PID. Allows more control than wait.

Wait/Waitpid Example Outputs: Examples fork10 (using wait) and fork11 (using waitpid) demonstrate the different behaviors.

exec: Running new programs

The exec system call loads and runs an executable at a given path with specified arguments. The path is the complete path of an executable. arg0 becomes the name of the process (typically identical to path or just the executable filename). "Real" arguments start with arg1. The list of args is terminated by a (char *)0 argument. It returns -1 if error, otherwise it doesn't return.

📐 Formula: int execl(char *path, char *arg0, char *arg1, ..., 0) → Replaces the current process image with a new program. Does not return on success.

💡 Why this matters: exec is how UNIX systems run entirely new programs within the same process. After fork, a child process typically calls exec to replace its copy of the parent's code with a new program.

⭐ Key Takeaways

For the exam, you must understand the four-state suspension model and differentiate between Ready, Blocked, Ready Suspend, and Blocked Suspend states. Master the three main categories of the Process Control Block: process identification, processor state information (user-visible, control/status registers, stack pointers), and process control information (scheduling, data structuring, IPC, privileges). Be able to explain zombie processes, including when they occur and how they are reaped through parent-child relationships or by init. Crucially, you must know the exact behavior of fork (returns PID to parent, 0 to child), wait/waitpid (suspends parent until child terminates), and exec (replaces the process image). Finally, be prepared to trace through fork example programs to determine how many processes are created and identify the output.

🧠 Quick Revision Questions

1. What are the four key states in the process suspension model, and what distinguishes "Blocked Suspend" from "Blocked"?
2. List the three main categories of information stored in a Process Control Block.
3. What does the fork() system call return to the parent process and to the child process?
4. Explain what a zombie process is and describe two ways it can be reaped (cleaned up).
5. What is the fundamental difference between how wait() and exec() affect a process's execution?

📘 Lecture 6 — Overview of today’s lecture

📖 Overview: This lecture continues the exploration of process management in operating systems, covering fork examples, process termination and zombie processes, synchronization via wait/waitpid, and introduces the critical concept of threads for achieving concurrency. Understanding these mechanisms is essential for building efficient, concurrent systems like web servers and parallel programs.

🗂️ Topics Covered

The lecture covers continuation of fork examples from the previous lecture, the concept of zombies and reaping processes, the wait and waitpid system calls in Linux, the need for threads within processes for concurrency, an introduction to threads, and a recap of the lecture covering exceptions, processes, spawning, terminating, reaping, and replacing processes.

📝 Lecture Summary

Fork Example #3

• Both parent and child can continue forking

Fork Example #4

• Both parent and child can continue forking

Fork Example #5

• Both parent and child can continue forking

exit: Destroying Process

• void exit(int status) exits a process. Normally, a process returns with status 0.
• atexit() registers functions to be executed upon exit.

Zombies

• When a process terminates, it still consumes system resources (various tables maintained by the OS). This is called a "zombie" — a living corpse, half alive and half dead.
• Reaping is performed by a parent on a terminated child. The parent is given exit status information, and then the kernel discards the process.
• What if Parent Doesn't Reap? If any parent terminates without reaping a child, then the child will be reaped by the init process. Only explicit reaping is needed for long-running processes, e.g., shells and servers.

🔑 Definition — Zombie: A process that has terminated but still consumes system resources because its parent has not yet reaped it. 💡 Why this matters: Zombie processes waste kernel resources (like process table entries). If too many accumulate, they can prevent new processes from being created.

📌 Zombie Example: The ps command shows the child process as "defunct". Killing the parent allows the orphaned child to be reaped by init.

📌 Non-terminating Child Example: A child process can still be active even though its parent has terminated. It must be killed explicitly, or else it will keep running indefinitely.

wait: Synchronizing with children

• *int wait(int child_status) suspends the current process until one of its children terminates. The return value is the pid of the child process that terminated.
• If child_status != NULL, then the object it points to will be set to a status indicating why the child process terminated.

📌 Wait Example: If multiple children have completed, wait will take them in an arbitrary order. Macros like WIFEXITED and WEXITSTATUS can be used to get information about the exit status.

Waitpid

• waitpid(pid, &status, options) can wait for a specific process. It has various options.

exec: Running new programs

• **int execl(char *path, char arg0, char arg1, ..., 0) loads and runs the executable at path with args arg0, arg1, ...
  • path is the complete path of an executable.
  • arg0 becomes the name of the process (typically identical to path or contains only the executable filename).
  • "Real" arguments to the executable start with arg1, etc.
  • The list of args is terminated by a (char *)0 argument.
• Returns -1 if error, otherwise doesn't return!

Summarizing

• Exceptions: Events that require nonstandard control flow, generated externally (interrupts) or internally (traps and faults).
• Processes: At any given time, the system has multiple active processes, but only one can execute at a time. Each process appears to have total control of the processor + private memory space.
• Spawning Processes: Call to fork — one call, two returns.
• Terminating Processes: Call exit — one call, no return.
• Reaping Processes: Call wait or waitpid.
• Replacing Program Executed by Process: Call execl (or variant) — one call, (normally) no return.

Concurrency

• Imagine a web server, which might like to handle multiple requests concurrently: while waiting for the credit card server to approve a purchase for one client, it could be retrieving the data requested by another client from disk, and assembling the response for a third client from cached information.
• Imagine a web client (browser), which might like to initiate multiple requests concurrently.
• Imagine a parallel program running on a multiprocessor, which might like to employ "physical concurrency": for example, multiplying a large matrix – split the output matrix into k regions and compute the entries in each region concurrently using k processors.

What’s in a process?

• A process consists of (at least):
  • an address space
  • the code for the running program
  • the data for the running program
  • an execution stack and stack pointer (SP) — traces state of procedure calls made
  • the program counter (PC), indicating the next instruction
  • a set of general-purpose processor registers and their values
  • a set of OS resources (open files, network connections, sound channels, ...)
• That's a lot of concepts bundled together! Decompose into:
  • an address space
  • threads of control
  • (other resources...)

What’s needed?

• In each of these examples of concurrency (web server, web client, parallel program):
  • Everybody wants to run the same code
  • Everybody wants to access the same data
  • Everybody has the same privileges
  • Everybody uses the same resources (open files, network connections, etc.)
• But you'd like to have multiple hardware execution states:
  • an execution stack and stack pointer (SP)
  • the program counter (PC)
  • a set of general-purpose processor registers and their values

How could we achieve this?

• Given the process abstraction as we know it: fork several processes and cause each to map to the same physical memory to share data.
• It's really inefficient:
  • space: PCB, page tables, etc.
  • time: creating OS structures, fork and copy address space, etc.

Can we do better?

• Key idea: separate the concept of a process (address space, etc.) from that of a minimal "thread of control" (execution state: PC, etc.).
• This execution state is usually called a thread, or sometimes, a lightweight process.

Threads and processes

• Most modern OS's (Mach, Chorus, NT, modern UNIX) therefore support two entities:
  • the process, which defines the address space and general process attributes (such as open files, etc.)
  • the thread, which defines a sequential execution stream within a process
• A thread is bound to a single process/address space. Address spaces, however, can have multiple threads executing within them. Sharing data between threads is cheap: all see the same address space. Creating threads is cheap too!
• Threads become the unit of scheduling. Processes/address spaces are just containers in which threads execute.

⭐ Key Takeaways

The fork() system call creates a child process that shares code with the parent and both can continue forking. A terminated process becomes a zombie if its parent does not reap it, consuming kernel resources until the init process adopts it. The wait() system call blocks the parent until a child terminates, returning the child's PID and exit status, while waitpid() allows waiting for a specific child with options. Concurrency is essential for modern systems like web servers, but creating multiple processes for each task is inefficient due to overhead from PCBs, page tables, and memory copying. Threads solve this by separating the execution state (PC, stack, registers) from the process (address space, resources), allowing multiple lightweight execution streams within a single process that share code, data, and resources cheaply.

🧠 Quick Revision Questions

1. What system resources does a zombie process still consume after termination?
2. What happens to a child process if its parent terminates without reaping it?
3. How does the wait() system call differ from waitpid() in terms of which child is waited for?
4. What are the three components of a process that are separated when introducing threads?
5. Why is using multiple processes (via fork) inefficient for achieving concurrency compared to using multiple threads?

📘 Lecture 7 — Overview of today’s lecture

📖 Overview: This lecture explores the design space for threads, comparing user-level and kernel-level thread implementations. It explains how threads are illustrated within an address space and examines the trade-offs between the two approaches, including their respective problems and advantages, which is crucial for understanding modern operating system design for concurrency.

🗂️ Topics Covered

The lecture covers the design space for threads, including the evolution from a traditional process address space to one with threads. It explains the process/thread separation and the benefits of multithreading even on uniprocessors. The lecture details kernel threads and user-level threads, including their implementations, scheduling strategies, context switching, and the problems that arise with I/O operations and lock preemption. Finally, it summarizes the pros and cons of both user-level and kernel-level thread implementations.

📝 Lecture Summary

The design space

The lecture begins by contrasting an old process address space (single process with a single thread of control) with a new process address space that includes threads, showing how multiple threads of execution can coexist within a single address space.

Process/thread separation

Concurrency (multithreading) is useful for handling concurrent events (e.g., web servers and clients), building parallel programs (e.g., matrix multiply, ray tracing), and improving program structure (the Java argument). Multithreading is useful even on a uniprocessor, even though only one thread can run at a time. Supporting multithreading by separating the concept of a process (address space, files, etc.) from that of a minimal thread of control (execution state) is a big win because creating concurrency does not require creating new processes, making it "faster / better / cheaper".

Kernel threads

With kernel threads, the OS manages threads and processes, meaning all thread operations are implemented in the kernel. The OS schedules all threads in a system. If one thread in a process blocks (e.g., on I/O), the OS knows about it and can run other threads from that process, making it possible to overlap I/O and computation inside a process.

Kernel threads are cheaper than processes because there is less state to allocate and initialize. However, they're still pretty expensive for fine-grained use, being orders of magnitude more expensive than a procedure call. Thread operations are all system calls, involving context switch and argument checks, and the kernel must maintain state for each thread.

User-level threads

To make threads cheap and fast, they need to be implemented at the user level, managed entirely by a user-level library (e.g., libpthreads.a). User-level threads are small and fast, with each thread represented simply by a PC, registers, a stack, and a small thread control block (TCB). Creating a thread, switching between threads, and synchronizing threads are done via procedure calls with no kernel involvement necessary, making user-level thread operations 10-100x faster than kernel threads.

User-level thread implementation

The kernel believes the user-level process is just a normal process running code, but this code includes the thread support library and its associated thread scheduler. The thread scheduler determines when a thread runs, using queues to keep track of what threads are doing (run, ready, wait), just like the OS and processes, but implemented at user-level as a library.

How to keep a user-level thread from hogging the CPU?

• Strategy 1: Cooperation — A thread willingly gives up the CPU by calling yield(). yield() calls into the scheduler, which context switches to another ready thread. What happens if a thread never calls yield()? It hogs the CPU.
• Strategy 2: Preemption — The scheduler requests a timer interrupt be delivered by the OS periodically, usually delivered as a UNIX signal. Signals are like software interrupts, but delivered to user-level by the OS. At each timer interrupt, the scheduler gains control and context switches as appropriate.

Thread context switch

For user-level threads, context switching is very simple:

• Save context of currently running thread: push machine state onto thread stack
• Restore context of the next thread: pop machine state from next thread's stack
• Return as the new thread: execution resumes at PC of next thread

This is done by assembly language and works at the level of the procedure calling convention. It cannot be implemented using procedure calls because a thread might be preempted (and then resumed) in the middle of a procedure call. C commands setjmp and longjmp are one way of doing it.

What if a thread tries to do I/O?

The kernel thread "powering" the user-level thread is lost for the duration of the synchronous I/O operation. One could have one kernel thread powering each user-level thread (no real difference from kernel threads), or have a limited-size "pool" of kernel threads powering all user-level threads in the address space, where the kernel schedules these threads obliviously to what's going on at user-level.

💡 Why this matters: The blocking I/O problem is the main limitation of user-level threads, requiring creative solutions to maintain performance.

What if the kernel preempts a thread holding a lock?

Other threads will be unable to enter the critical section and will block (stall). Solving this requires coordination between the kernel and the user-level thread manager through "scheduler activations". Each process can request one or more kernel threads, with the process given responsibility for mapping user-level threads onto kernel threads. The kernel promises to notify the user-level before it suspends or destroys a kernel thread.

Pros and Cons of User Level threads

Pros:

• Procedure invocation instead of system calls results in fast scheduling and much better performance.
• Could run on existing OSes that don't support threads.
• Customized scheduling is useful in many cases, e.g., for garbage collection.
• Kernel space not required for thread-specific data, scaling better for large numbers of threads.

Cons:

• Blocking system calls affect all threads. Solution 1: Make the system calls non-blocking (is this a good solution?). Solution 2: Write jacket or wrapper routines with select, but this requires re-writing parts of the system call library.
• Similar problem occurs with page faults; the whole process blocks.
• Voluntary yield to the run-time system is necessary for context switch. Solution: Run time system may request a clock signal.
• Programs that use multi-threading need to make system calls quite often; if they don't, there is usually no need to be multi-threaded.

Pros and cons of kernel level threads

Pros:

• Blocking system calls cause no problem.
• Page faults can be handled by scheduling another thread from the same process (if one is ready).

Cons:

• Cost of a system call is substantially greater. Solution: Thread recycling — don't destroy thread data structures when the thread is destroyed.

⭐ Key Takeaways

The fundamental trade-off in thread implementation is between speed and functionality: user-level threads are 10-100x faster than kernel threads because operations use procedure calls instead of system calls, but they suffer from blocking problems when a thread performs I/O or encounters a page fault. Kernel threads solve these blocking issues because the OS can schedule other threads from the same process, but they are more expensive due to system call overhead. The key decision factors include whether the application is I/O-bound or CPU-bound, the need for customized scheduling, and the scalability requirements for large numbers of threads. Understanding these trade-offs is essential for designing efficient concurrent systems, with modern solutions often employing a hybrid approach using scheduler activations or thread pools.

🧠 Quick Revision Questions

1. What is the main advantage of user-level threads over kernel-level threads in terms of performance?
2. What happens to a user-level thread's process when one of its threads performs a blocking I/O system call?
3. How does thread recycling solve one of the disadvantages of kernel-level threads?
4. What is the "scheduler activation" approach, and which problem does it solve?
5. Compare how page faults are handled in user-level threads versus kernel-level threads.

📘 Lecture 8 — POSIX Threads (pthreads) Standard Interface and Linux Processes/Threads

📖 Overview: This lecture bridges the gap between the theoretical concept of threads and their practical implementation in Linux. It introduces the POSIX threads (pthreads) standard interface for C programming and explores how Linux internally represents and manages processes and threads using the same underlying data structures. Understanding these concepts is crucial for writing efficient multi-threaded programs and for comprehending how modern operating systems handle concurrency.

🗂️ Topics Covered

The lecture begins with an overview of the POSIX threads (pthreads) standard interface, covering functions for creating, terminating, and synchronizing threads. It includes a simple "Hello, World" pthreads program to illustrate thread execution. The focus then shifts to how Linux treats processes and threads, explaining the clone() system call as the core mechanism for creating threads. The fields within the task_struct process descriptor are detailed, including the process/thread states and their finite state machine (FSM) in Linux. The lecture concludes with a look ahead and a recap.

📝 Lecture Summary

POSIX Threads (Pthreads) Interface

The Pthreads standard defines a portable interface for approximately 60 functions that manipulate threads from C programs. The key categories of these functions include:

• Creating and reaping threads: pthread_create is used to spawn a new thread, and pthread_join is used to wait for a specific thread to terminate and clean up its resources.
• Determining your thread ID: A thread can obtain its own unique identifier using the pthread_self function.
• Terminating threads: A thread can be terminated voluntarily by calling pthread_exit, or another thread can request its termination with pthread_cancel. The exit system call will terminate the entire process (all threads), while a simple ret (return from the thread's start function) terminates only the current thread.
• Synchronizing access to shared variables: The interface includes functions for mutexes (e.g., pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock) and condition variables (e.g., pthread_cond_init, pthread_cond_wait, pthread_cond_timedwait).

🔑 Definition — Pthreads: A standardized C programming interface (POSIX.1c, Threads extensions) for creating and manipulating threads.

The Pthreads "hello, world" Program

A simple "Hello, World" program demonstrates the basic usage of Pthreads. The main program uses pthread_create to create a new thread, passing it a function to execute. The main thread then calls pthread_join to wait for the newly created thread to finish its execution before the program exits. This illustrates the fundamental pattern of creating and reaping threads.

Processes and threads in Linux

Linux uses the same internal representation for both processes and threads. A thread is simply a new process that happens to share the same address space as its parent. This distinction is made when a new thread is created by the clone system call, as opposed to fork.

• fork(): Creates a new process with its own entirely new process context (address space, file descriptors, signal handlers, etc.). The child process is a complete, independent copy.
• clone(): Creates a new process with its own identity (a new PID) but is allowed to share various data structures of its parent. This fine-grained control is achieved through flags passed to the clone() system call.

🔑 Definition — clone(): A Linux-specific system call that creates a new process (task) with the ability to selectively share resources (like address space, file descriptors, etc.) with its parent, forming the basis for thread creation in Linux.

Main Flags for Linux clone

The clone() system call uses a set of flags to determine which parts of the parent's context are shared with the new child process. Key flags include:

• CLONE_FILES: Shares the table that identifies the open files. Both processes use the same set of file descriptors.
• CLONE_FS: Shares the table that identifies the root directory and the current working directory, as well as the value of the bit mask used to mask the initial file permissions of a new file (umask).
• CLONE_SIGHAND: Shares the table that identifies the signal handlers.
• CLONE_THREAD: Inserts this process into the same thread group as the parent. If this flag is true, it implicitly enforces CLONE_PARENT, making the new and parent tasks siblings. This is the key flag for creating a standard POSIX thread.
• CLONE_VM: Shares the address space (memory descriptor and all page tables). This is the fundamental flag for creating a thread that shares memory with its parent. 💡 Why this matters: Without CLONE_VM, clone() behaves more like fork(), creating a separate address space.

clone()

The clone() function is the core system call for creating both processes and threads in Linux.

• fork() is actually implemented as a wrapper around clone() with specific parameters.
• The general signature is clone(fp, data, flags, stack). (The asterisks indicate it's an internal kernel function not meant to be called directly from user space).
• fp is the function pointer for the thread's start routine.
• data is the pointer to the argument to be passed to the start routine.
• flags is a bitmask of the CLONE_* flags (e.g., CLONE_VM | CLONE_THREAD).
• stack is the address of the user stack that the new thread will use.
• Internally, clone() calls the do_fork() function, which is the common workhorse for creating new tasks in the kernel.

📐 Formula: fork() = clone(flags = SIGCHLD, stack = 0); → A standard fork() is equivalent to calling clone() with only the SIGCHLD flag (meaning the parent is notified of child termination) and a zero for the stack (indicating a new, separate stack should be created).

Internal Kernel threads

Linux has a small number of kernel threads that run continuously in the kernel space. These are also known as daemons.

• They do not have a user address space; they only have the kernel-mapped portion of the address space.
• They are created using the kernel_thread() function.
• Process 0 (idle process): The first process, created during boot, which runs when no other tasks are runnable.
• Process 1: Spawns several kernel threads before transitioning to user mode as /sbin/init. Key kernel threads include:
  • kflushd (bdflush): Flushes dirty buffers to disk under "memory pressure."
  • kupdate: Periodically flushes old buffers to disk.
  • kswapd: The swapping daemon.

Linux processes

In Linux terminology, processes are called tasks. The kernel maintains a list of process descriptors, which are data structures of type task_struct (defined in include/linux/sched.h).

• The maximum number of threads/processes allowed is dependent upon the amount of memory in the system.
• A user can check the current limit by viewing /proc/sys/kernel/threads_max. By writing to that file (as superuser), the limit can be changed on the fly.

Linux Process Identity

A process is identified externally by its PID (Process ID). Internally, the kernel uses the address of the task_struct descriptor to quickly access process information.

• PIDs are dynamically allocated and reused. They are 16-bit values (up to 32767) and the system avoids immediate reuse to prevent confusion.
• To efficiently find a task_struct from a PID, the kernel uses a hash table.
• The current macro gives a pointer to the task_struct of the currently executing process. So current->pid provides the PID of the current process.

do_fork()

The function do_fork() is the core kernel routine that performs the heavy lifting of creating a new task. Its key steps are:

1. alloc_task_struct(): Allocates a new task_struct for the new process.
2. find_empty_process(): Finds an available slot in the task list for the new process.
3. get_pid(): Allocates a unique PID for the new process.
4. Update ancestry: Sets up links between the new task and its parent, establishing the process tree.
5. Copy components based on flags: Duplicates or shares resources (memory, files, etc.) based on the flags passed to clone().
6. copy_thread(): Copies the processor-specific context (registers, kernel stack pointer) from the parent to the child and sets up the initial execution state for the new process.
7. Link into task list, update nr_tasks: Adds the new process's descriptor to the global list of tasks and increments the count of running tasks.
8. Set TASK_RUNNING: Sets the state of the new process to TASK_RUNNING, making it eligible to be scheduled for execution.
9. wake_up_process(): Wakes up the new process so the scheduler can consider it.

Linux data structures for processes

The process control blocks (or descriptors) are kept in circular linked lists. The implementation in the kernel uses the structure struct list_head as the node for these lists:

struct list_head {
    struct list_head *next, *prev;
};

These linked lists are circular, meaning there is no explicit head or tail node. One can start at any node and traverse the entire list. The task_struct contains a list_head member to link itself into this main task list.

Task struct contents

The task_struct contains a vast amount of information about a process. Key categories of fields include:

• Scheduling information: Information needed by the Linux scheduler, such as process priority (normal or real-time), scheduling policy, and a counter that tracks the remaining time quanta for the process.
• Identifiers: The PID, user ID (UID), group ID (GID), and other identifiers used for resource access privileges.
• Interprocess communication: Structures to support IPC mechanisms like those found in UNIX SVR4.
• Links: Pointers to the parent, siblings (processes with the same parent), and all children of this process.
• Times and timers: The process creation time, the amount of processor time consumed, and pointers to any associated interval timers. A timer can be single-use or periodic, and a signal is sent when it expires.
• File system: Pointers to the files opened by the process, as well as pointers to the current and root directories.
• Address space: The mm_struct which defines the virtual address space assigned to the process (memory descriptor and page tables).
• Processor-specific context: The registers and stack information that constitute the context of the process, saved during context switches.
• State: The execution state of the process.

Process State

The state of a process in Linux is stored in a field within the task_struct. The primary states are:

• Running (TASK_RUNNING): This state value corresponds to two states: A process is either executing on a CPU or it is ready to execute and waiting in a run queue. 💡 Why this matters: The scheduler only operates on processes in the TASK_RUNNING state.
• Interruptible (TASK_INTERRUPTIBLE): This is a blocked state. The process is waiting for an event (e.g., completion of I/O, a signal, or availability of a resource). It can be woken up by receiving a signal, which allows it to handle the signal before or instead of the event it was waiting for.
• Uninterruptible (TASK_UNINTERRUPTIBLE): This is another blocked state. The difference from TASK_INTERRUPTIBLE is that a process in this state is waiting directly on hardware conditions (e.g., waiting for a disk drive to become ready) and therefore will not handle any signals. It must wait for the specific hardware event to complete.
• Stopped (TASK_STOPPED): The process has been halted, typically by a signal (e.g., SIGSTOP or SIGTSTP). It can only resume execution by a positive action from another process (e.g., a SIGCONT signal). This is often used for debugging.
• Zombie (EXIT_ZOMBIE): The process has terminated (finished execution) but its task_struct still remains in the process table. This is because the parent process has not yet called wait() or waitpid() to read the child's exit status. Once the parent does, the zombie is reaped (its task_struct is deallocated). 💡 Why this matters: A zombie process uses up a process table slot but consumes no other system resources. If the parent fails to reap its children, a large number of zombies can accumulate.

🔑 Definition — Zombie: A process state where the process has finished execution but still has an entry in the process table (its task_struct), waiting for its parent to read its exit status.

⭐ Key Takeaways

The most critical concepts from this lecture are the Linux-specific approach to threads and the central role of the task_struct. Linux treats threads as lightweight processes that share resources via the clone() system call, which provides fine-grained control through flags like CLONE_VM and CLONE_THREAD. The task_struct is the master data structure for every process and thread, containing everything from scheduling information and memory maps to its execution state. Understanding the process state machine—especially the TASK_RUNNING, TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, and EXIT_ZOMBIE states—is fundamental to grasping process lifecycles and scheduling behavior.

🧠 Quick Revision Questions

1. What is the difference between fork() and clone() in Linux?
2. Name the key fields within a Linux task_struct that relate to file system information, memory management, and scheduling.
3. What does CLONE_VM do? Why is it critical for creating a thread?
4. A process is waiting for a signal. In which TASK_* state is it most likely to be?
5. What is the difference between an "interruptible" sleep and an "uninterruptible" sleep in Linux?

📘 Lecture 9 — Overview of today’s lecture

📖 Overview: This lecture addresses the fundamental challenge of coordinating multiple threads that access shared data in concurrent programs. It introduces the concepts of shared variable analysis, synchronization, critical sections, and the classic problems that arise when threads interleave their executions without proper control. Understanding these concepts is essential for writing correct and reliable multi-threaded programs.

🗂️ Topics Covered

This lecture covers shared variable analysis in multi-threaded C programs, the threads memory model and what resources are shared versus private, the concept of synchronization for controlling thread cooperation, concurrent execution and incorrect interleavings illustrated with badcnt.c, progress graphs for visualizing execution states, critical sections and unsafe regions, the classic bank account example demonstrating race conditions, the requirements for critical section solutions, and the "Too Much Milk" problem as a practical example of synchronization challenges.

📝 Lecture Summary

Shared Variables in Threaded C Programs

The question of which variables are shared in a threaded C program is not simply "global variables are shared" and "stack variables are private." Determining shared variables requires answering: what is the memory model for threads, how are variables mapped to memory instances, and how many threads reference each of these instances.

Threads Memory Model

Conceptually, each thread runs in the context of a process and has its own separate thread context including thread ID, stack, stack pointer, program counter, condition codes, and general purpose registers. All threads share the remaining process context: code, data, heap, and shared library segments of the process virtual address space, as well as open files and installed handlers. Operationally, this model is not strictly enforced because while register values are truly separate and protected, any thread can read and write the stack of any other thread. This mismatch between the conceptual and operational model is a source of confusion and errors.

What resources are shared?

Local variables are not shared because they refer to data on the stack and each thread has its own stack. You should never pass, share, or store a pointer to a local variable on another thread's stack. Global variables are shared because they are stored in the static data segment and accessible by any thread. Dynamic objects are shared because they are stored in the heap and shared if you can name them; in C, you can conjure up the pointer (e.g., void *x = (void *) 0xDEADBEEF), while in Java, strong typing prevents this and references must be passed explicitly.

Synchronization

Threads cooperate in multithreaded programs to share resources and access shared data structures (e.g., threads accessing a memory cache in a web server) and also to coordinate their execution (e.g., a disk reader thread hands off blocks to a network writer thread through a circular buffer). For correctness, we must control this cooperation and assume threads interleave executions arbitrarily and at different rates because scheduling is not under the application writer's control. We control cooperation using synchronization, which enables us to restrict the interleaving of executions. Note: this also applies to processes and across machines in a distributed system.

Shared Variable Analysis

A variable x is shared iff multiple threads reference at least one instance of x. In the example with variable instances: ptr, svar, and msgs are shared because they are referenced by main thread and peer threads. i and myid are NOT shared because they are only referenced by one thread each.

badcnt.c: An Improperly Synchronized Threaded Program

The lecture presents badcnt.c which is an improperly synchronized threaded program. The assembly code for the counter loop reveals why problems occur at the instruction level.

Concurrent Execution

The key idea is that in general, any sequentially consistent interleaving is possible, but some are incorrect. Notation: I_i denotes that thread i executes instruction I, and %eax_i is the contents of %eax in thread i's context. An incorrect ordering is shown where two threads increment the counter, but the result is 1 instead of 2 because the interleaving of load, increment, and store operations from both threads causes one update to be lost.

Progress Graphs

A progress graph depicts the discrete execution state space of concurrent threads. Each axis corresponds to the sequential order of instructions in a thread. Each point corresponds to a possible execution state (Inst₁, Inst₂). For example, (L₁, S₂) denotes the state where thread 1 has completed L₁ and thread 2 has completed S₂.

Trajectories in Progress Graphs

A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads. Example: H₁, L₁, U₁, H₂, L₂, S₁, T₁, U₂, S₂, T₂.

Critical Sections and Unsafe Regions

Instructions L, U, and S form a critical section with respect to the shared variable cnt. Instructions in critical sections (with respect to some shared variable) should not be interleaved. Sets of states where such interleaving occurs form unsafe regions.

Safe and Unsafe Trajectories

A trajectory is safe iff it doesn't touch any part of an unsafe region. A trajectory is correct with respect to cnt iff it is safe.

The classic example

Consider a function to withdraw money from a bank account:

int withdraw(account, amount) {
    int balance = get_balance(account);
    balance -= amount;
    put_balance(account, balance);
    return balance;
}

If a husband and wife share a bank account with a balance of $100.00 and both go to separate ATM machines to simultaneously withdraw $10.00, the execution of the two threads can be interleaved. One possible interleaving: get_balance (100), get_balance (100), balance -= amount (90), balance -= amount (90), put_balance (90), put_balance (90). The final balance is $90 instead of the correct $80. The bank loses $10 and the customers gain $10.

Race conditions and concurrency

An atomic operation is an operation that always runs to completion or not at all. It is indivisible and cannot be stopped in the middle. On most machines, memory reference and assignment (load and store) of words are atomic. However, many instructions are not atomic. For example, on most 32-bit architectures, double precision floating point store is not atomic because it involves two separate memory operations.

🔑 Definition — Atomic operation: An operation that always runs to completion or not at all. It is indivisible and cannot be stopped in the middle.

The crux of the problem

The problem is that two concurrent threads (or processes) access a shared resource (account) without any synchronization, which creates a race condition where the output is non-deterministic and depends on timing. We need mechanisms for controlling access to shared resources in the face of concurrency so we can reason about the operation of programs, essentially re-introducing determinism. Synchronization is necessary for any shared data structure: buffers, queues, lists, hash tables, scalars, and so on.

Synchronization related definitions

Mutual exclusion: ensuring that only one thread does a particular thing at a time. One thread doing it excludes all others.

🔑 Definition — Mutual exclusion: Ensuring that only one thread does a particular thing at a time. One thread doing it excludes all others.

Critical section: piece of code that only one thread can execute at one time. All other threads are forced to wait on entry. When a thread leaves a critical section, another can enter. Mutual exclusion is required inside the critical section.

🔑 Definition — Critical section: Piece of code that only one thread can execute at one time. All other threads are forced to wait on entry. When a thread leaves a critical section, another can enter.

The key idea is that all synchronization involves waiting.

Critical section solution requirements

Critical sections have the following requirements:

1. Mutual exclusion: at most one thread is in the critical section.
2. Progress: if thread T is outside the critical section, then T cannot prevent thread S from entering the critical section.
3. Bounded waiting (no starvation): if thread T is waiting on the critical section, then T will eventually enter the critical section. This assumes threads eventually leave critical sections.
4. Performance: the overhead of entering and exiting the critical section is small with respect to the work being done within it.

Synchronization: Too Much Milk

This is a classic synchronization problem. Person A looks in the fridge, sees no milk at 3:00 and leaves for the store at 3:05. Person B independently looks in the fridge at 3:10, sees no milk, and also leaves for the store. Both buy milk and return home with milk, resulting in too much milk.

Too much milk: Solution 1

Solution #1 attempts to use notes:

if (noMilk) {
    if (noNote) {
        leave Note;
        buy milk;
        remove note;
    }
}

This does not work because both threads could check for no note before either leaves a note, and then both would buy milk.

Too much milk: Solution 2

Solution #1 makes the problem worse because it fails only occasionally, making it very hard to debug. The constraint has to be satisfied independent of what the dispatcher does because the timer can go off and a context switch can happen at any time.

Solution #2:

• Thread A: leave note A, if (no Note from B) { if (noMilk) buy Milk; }, remove Note A.
• Thread B: leave note B, if (no Note from A) { if (noMilk) buy Milk; }, remove Note B.

💡 Why this matters: Solution #2 can still fail because if both threads leave notes before checking each other's notes, both may see no note from the other and both could proceed to buy milk.

⭐ Key Takeaways

The most critical concept from this lecture is that concurrent access to shared variables without synchronization creates race conditions where program behavior becomes non-deterministic and can produce incorrect results, as demonstrated by the bank account example where both withdrawals complete but only one is reflected in the balance. Students must understand that a variable is shared if multiple threads reference at least one instance of it, and that instructions in critical sections (like load, increment, store on a counter) must not be interleaved across threads to maintain correctness. Progress graphs provide a visual tool for understanding which interleavings are safe and which enter unsafe regions. The four requirements for any correct critical section solution are mutual exclusion, progress, bounded waiting, and performance. Finally, the "Too Much Milk" problem illustrates that simple solutions using only atomic load and store operations are often insufficient for synchronization.

🧠 Quick Revision Questions

1. What is the definition of a shared variable in a multi-threaded C program?
2. In the badcnt.c example, explain how the interleaving of assembly instructions from two threads can cause the final counter value to be 1 instead of 2.
3. What are the four requirements for a correct critical section solution, and what does each requirement mean?
4. In the bank account withdrawal example with a starting balance of $100, what sequence of interleaved operations from two threads withdrawing $10 each results in a final balance of $90?
5. Why does Solution #2 for the "Too Much Milk" problem fail to guarantee mutual exclusion?

📘 Lecture 10 — Overview of today’s lecture

📖 Overview: This lecture completes the analysis of concurrency examples, focusing on the “Too Much Milk” problem and its solution. It then introduces locks as a fundamental synchronization primitive, detailing their implementation via disabling interrupts, busy-waiting, and hardware atomic instructions like test&set. Finally, it introduces semaphores as a higher-level synchronization mechanism.

🗂️ Topics Covered

This lecture continues the previous discussion of concurrency with the “Too Much Milk Solution 3” and its summary. It then formally introduces locks, their definition, and three implementation strategies: disabling interrupts (flawed on uniprocessors), busy-waiting (with its performance problems), and using atomic read-modify-write instructions like test&set (suitable for multiprocessors). The lecture concludes with an introduction to semaphores, their definition, operations (wait and signal), blocking behavior, and the two main types (binary and counting).

📝 Lecture Summary

Too Much Milk Solution 3

This solution uses leaving notes to coordinate two threads (A and B) buying milk. Thread A leaves a note, then checks if B’s note is present; if so, it busy-waits. If not, it checks for milk and buys if needed. Thread B leaves a note and does the same, but only buys milk if there is no note from A.

🔑 Definition — Busy waiting: A thread continuously checks a condition in a loop while waiting, consuming CPU cycles without doing useful work.

📌 Example: Thread A checks “while (note B)” at point X. If B’s note is absent, it’s safe to proceed. If B’s note is present, A does not know if B will buy milk or is also waiting — so A loops. At point Y, B checks “if (no note A)”: if A’s note is absent, B knows it is safe to buy milk. If A’s note is present, B knows A is either buying or waiting for B to quit, so B can safely quit.

💡 Why this matters: This solution works but is complex, thread-specific, and uses busy waiting. It motivates the need for simpler, higher-level synchronization primitives like locks.

Locks

A lock is a synchronization mechanism that prevents more than one thread from entering a critical section at the same time. The Acquire() call waits until the lock is free, then grabs it. The Release() call unlocks it, waking up a waiter if any. These operations must be atomic to prevent race conditions.

🔑 Definition — Atomic operation: An operation that appears to happen instantaneously from the perspective of other threads — no intermediate state is visible.

📌 Example: With locks, the Too Much Milk problem becomes trivial: lock->Acquire(); if (noMilk) buy milk; lock->Release();

Implementing Locks with Disabling Interrupts (Uniprocessor Only)

On a uniprocessor, an interrupt can cause a context switch in the middle of an operation. Disabling interrupts prevents such external events, making the operation atomic. However, a flawed simple implementation is Lock::Acquire() { disable interrupts; } and Lock::Release() { enable interrupts; }.

🔑 Definition — Disabling interrupts: A hardware mechanism that tells the processor to delay handling of external events (like I/O interrupts) until interrupts are re-enabled.

📌 Example: If a thread uses the flawed implementation, it might disable interrupts and then take a page fault or do disk I/O. In that case, it needs interrupts to be enabled to handle the I/O completion. Also, disabling interrupts for a long critical section could cause keystrokes to be lost because the interrupt for one keystroke isn’t handled by the time the next one occurs.

Implementing Locks with Busy Waiting

In this approach, a Lock class has an integer value (FREE = 0, BUSY = 1). The Acquire() method disables interrupts, then busy-waits (while (value != FREE)) — during the wait, it briefly enables then disables interrupts to allow other events. When free, it sets value = BUSY and re-enables interrupts. Release() sets value = FREE.

📐 Formula: Lock::Acquire(): disable interrupts; while (value != FREE) { enable interrupts; disable interrupts; } value = BUSY; enable interrupts.

📌 Example: If a high-priority thread enters the busy-waiting loop for a lock held by a low-priority thread, the timer may go off but the low-priority thread might never run (depending on the scheduling policy). This is a priority inversion problem, and the busy-waiting consumes CPU cycles inefficiently.

Implementing Locks with Test and Set (Hardware Instruction)

On multiprocessors, disabling interrupts is insufficient. Modern processors provide atomic read-modify-write instructions that read a value from memory into a register and write a new value, all atomically. The test&set instruction reads a memory location, sets it to 1, and returns the old value.

🔑 Definition — Test&Set: An atomic instruction that reads a memory location, writes 1 back to it, and returns the original value.

📐 Formula: Lock::Acquire { while (test&set(value) == 1) ; // Do nothing } Lock::Release { value = 0; }

📌 Example: Initially, value = 0 (free). When thread A calls Acquire, test&set(value) reads 0 and sets value = 1. Since it returns 0, the loop exits, and A enters the critical section. If thread B tries to Acquire, test&set(value) reads 1 and sets it back to 1 (no change). It returns 1, so B busy-waits.

💡 Why this matters: This works on both uniprocessors and multiprocessors. The busy-wait can be modified to put the waiting thread to sleep, making it more efficient.

Semaphores — Introduction and Definition

Semaphores are a higher-level synchronization primitive, invented by Dijkstra. A semaphore is a variable manipulated atomically through two operations: wait (also called P or down) and signal (also called V or up). wait decrements the counter; signal increments it. If the counter falls below zero, the wait operation blocks the calling thread.

🔑 Definition — Semaphore: A synchronization primitive with a counter and a queue of waiting threads, accessed only through atomic wait and signal operations.

📌 Example: A binary semaphore (counter initialized to 1) provides exclusive access to a resource. A counting semaphore (counter initialized to N) allows up to N threads to access a resource concurrently.

🔑 Definition — Binary semaphore (mutex): A semaphore with a counter initialized to 1, used to guarantee mutually exclusive access. 🔑 Definition — Counting semaphore: A semaphore with a counter initialized to N, representing N units of a resource.

📌 Example: To protect a shared variable cnt updated by multiple threads, we initialize a semaphore mutex to 1. Each thread calls wait(mutex) before accessing cnt and signal(mutex) after, ensuring safe sharing.

⭐ Key Takeaways

The “Too Much Milk” problem demonstrates that simple load/store instructions are insufficient for reliable synchronization, motivating the need for locks and semaphores. Locks provide a straightforward Acquire/Release interface, but their implementation must be atomic. On a uniprocessor, disabling interrupts can achieve atomicity but has severe drawbacks (user code disabling interrupts, long critical sections causing lost keystrokes, and blocking I/O). Busy-waiting implementations waste CPU and can cause priority inversion. For multiprocessors, hardware atomic instructions like test&set are essential. Semaphores abstract synchronization further, using a counter and a blocking queue to provide both mutual exclusion (binary semaphore) and resource management (counting semaphore), making them more robust for general use.

🧠 Quick Revision Questions

1. What are the three main problems with the “Too Much Milk” Solution 3 that motivate the need for locks?
2. Why is the simple Lock::Acquire that just disables interrupts considered flawed? Provide two specific reasons.
3. Explain the key difference between implementing a lock with busy-waiting vs. without busy-waiting (using a queue).
4. How does the test&set instruction implement a lock, and why is it better than interrupt disabling on a multiprocessor?
5. What is the difference between a binary semaphore and a counting semaphore? In what scenario would you use each?

📘 Lecture 11 — Producer Consumer Problem, Semaphores, and Condition Variables

📖 Overview: This lecture addresses the classic producer-consumer synchronization problem using a bounded buffer. It explains how semaphores can be used for both mutual exclusion and scheduling constraints, and introduces condition variables and monitors as higher-level synchronization constructs. Understanding these concepts is crucial for designing correct concurrent systems where threads must coordinate access to shared resources.

🗂️ Topics Covered

The lecture covers the producer-consumer problem with a bounded buffer, including correctness constraints and a semaphore-based solution. It then explains the two distinct uses of semaphores: for mutual exclusion and for scheduling constraints. The lecture introduces monitors as a synchronization abstraction composed of a lock and condition variables, defines the condition variable operations (wait, signal, broadcast), and finally distinguishes between Hoare-style and Mesa-style monitor implementations.

📝 Lecture Summary

Producer-consumer with a bounded buffer

The problem involves a producer that puts items into a shared fixed-size buffer and a consumer that takes items out. Synchronization is needed to coordinate their access. Practical examples include multimedia processing (producer creates MPEG frames, consumer renders them) and event-driven graphical user interfaces (producer detects mouse clicks and keyboard hits, consumer retrieves events and paints the display). The goal is to avoid lockstep operation between producer and consumer by using a fixed-size buffer with synchronized access. The producer must wait if the buffer is full, and the consumer must wait if the buffer is empty.

🔑 Definition — Correctness constraints: The solution must satisfy three constraints: 1) Consumer must wait for producer to fill buffers if none are full (scheduling constraint). 2) Producer must wait for consumer to empty buffers if all are full (scheduling constraint). 3) Only one thread can manipulate the buffer queue at a time (mutual exclusion).

Semaphore solution

The solution uses a separate semaphore for each constraint. Semaphores are used in multiple ways simultaneously.

• Semaphore fullBuffers = 0 (initially, no item in buffer)
• Semaphore emptyBuffers = numBuffers (initially, number of empty slots; counts available resources)
• Semaphore mutex = 1 (no one using the buffer; used for mutual exclusion)

Producer() code:

emptyBuffers.P();          // wait for empty slot
mutex.P();                 // ensure exclusive access to buffer
put 1 item in buffer;
mutex.V();                 // release exclusive access
fullBuffers.V();           // signal that a full buffer is available

Consumer() code:

fullBuffers.P();           // wait for a full buffer
mutex.P();                 // ensure exclusive access to buffer
take 1 item out;
mutex.V();                 // release exclusive access
emptyBuffers.V();          // signal that an empty slot is available

📐 Formula: The sequence of operations shows that producer and consumer perform P and V operations on different semaphores. The producer waits on emptyBuffers and signals fullBuffers; the consumer waits on fullBuffers and signals emptyBuffers.

📌 Example: If the buffer has 5 slots initially: emptyBuffers = 5, fullBuffers = 0, mutex = 1. The first producer call executes emptyBuffers.P() (decrements to 4), then mutex.P() (decrements to 0), puts an item, then mutex.V() (increments to 1), then fullBuffers.V() (increments to 1). A consumer can now run.

💡 Why this matters: The order of P operations is important — if mutex.P() were done before emptyBuffers.P(), a deadlock could occur. The order of V operations is not critical because they release resources. The solution works for multiple producers and consumers without changes, as the semaphores manage the counts.

Two uses of semaphores

1. Mutual exclusion: The semaphore has an initial value of 1. P() is called before the critical section, and V() is called after the critical section. This ensures only one thread accesses the shared data at a time.

2. Scheduling constraints: Semaphores express generalized scheduling constraints—a way for a thread to wait for something. The initial value is typically 0 but not always. For example, implementing Thread's join (reaping) uses semaphores with an initial value of 0: ThreadJoin calls P() and ThreadFinish calls V().

🔑 Definition — Monitor: A monitor is a lock and zero or more condition variables for managing concurrent access to shared data. While textbooks describe monitors as a programming language construct where the lock is acquired automatically on calling any procedure, no widely-used language does this. In real-life operating systems (Windows, Linux, Solaris), monitors are used with explicit calls to locks and condition variables.

Condition variables

A condition variable is a queue of threads waiting for something inside a critical section. Key idea: make it possible to go to sleep inside a critical section by atomically releasing the lock at the same time as going to sleep. This prevents deadlock where a sleeping thread holds the lock, blocking others from entering.

Condition variables support three operations:

• Wait() — Release lock, go to sleep, re-acquire lock (releasing lock and going to sleep is atomic).
• Signal() — Wake up a waiter, if any.
• Broadcast() — Wake up all waiters.

Rule: Must hold the lock when doing condition variable operations.

A synchronized queue using condition variables:

AddToQueue() {
    lock.Acquire();
    put item on queue;
    condition.signal();
    lock.Release();
}

RemoveFromQueue() {
    lock.Acquire();
    while nothing on queue
        condition.wait(&lock);  // release lock; go to sleep; re-acquire lock
    remove item from queue;
    lock.Release();
    return item;
}

📌 Example: If the queue is empty and a consumer thread calls RemoveFromQueue, it acquires the lock, then enters the while loop. It calls condition.wait(&lock) which atomically releases the lock and puts the thread to sleep. When a producer calls AddToQueue, it acquires the lock, puts an item on the queue, calls condition.signal() (waking up the waiter), then releases the lock. The consumer then re-acquires the lock, exits the while loop, removes the item, releases the lock, and returns the item.

💡 Why this matters: The while loop (not an if) is critical because of Mesa-style semantics—the waiter may be woken up but another thread could have taken the item before it runs.

Mesa vs. Hoare monitors

The precise definition of signal and wait matters.

Mesa-style (most real operating systems): The signaller keeps the lock and the processor. The waiter is simply put on the ready queue with no special priority. The waiter may have to wait for the lock again.

Hoare-style (most textbooks): The signaller gives up the lock and CPU to the waiter; the waiter runs immediately. The waiter gives the lock and processor back to the signaller when it exits the critical section or if it waits again.

Readers/Writers problem

Motivation: Shared database (e.g., bank balances, airline seats) with two classes of users: Readers (never modify database) and Writers (read and modify database). Using a single lock on the database is overly restrictive. The goal is to allow many readers at the same time but only one writer at a time.

⭐ Key Takeaways

The producer-consumer problem with a bounded buffer requires three correctness constraints: consumer waits if no items, producer waits if buffer full, and mutual exclusion on buffer manipulation. Semaphores serve two distinct purposes—mutual exclusion (initial value 1) and scheduling constraints (initial value 0), and the order of P operations is critical to avoid deadlock. Condition variables allow a thread to sleep inside a critical section by atomically releasing the lock, supporting wait, signal, and broadcast operations with the rule that the lock must be held when using them. In Mesa-style monitors (used in real systems), the waiter is simply placed on the ready queue and may compete for the lock again, while Hoare-style (textbook) gives immediate control to the waiter. The Readers/Writers problem demonstrates that different types of access to shared data may require different synchronization strategies—multiple readers can coexist, but writing requires exclusive access.

🧠 Quick Revision Questions

1. What are the three correctness constraints for the producer-consumer problem with a bounded buffer, and which semaphore enforces each?
2. Why must the P() operation on the scheduling semaphore be performed before the P() operation on the mutex semaphore in the producer-consumer solution?
3. What is the key distinction between using a semaphore for mutual exclusion versus using it for scheduling constraints, in terms of initial value and operations?
4. How does a condition variable's Wait() operation atomically handle the release of the lock and going to sleep, and why is this atomicity necessary?
5. What is the difference between Mesa-style and Hoare-style monitors regarding what happens when a thread calls Signal() on a condition variable?

📘 Lecture 12 — Readers/Writers Problem & Thread Safety

📖 Overview: This lecture presents the classic readers/writers synchronization problem and its solution using condition variables. It then explores the duality between semaphores and monitors (condition variables), demonstrating how condition variables can be implemented using semaphores. Finally, the lecture introduces thread safety concepts, categorizing thread-unsafe functions and presenting methods to make functions reentrant and thread-safe.

🗂️ Topics Covered

The lecture covers the readers/writers problem with its constraints and solution using condition variables, including state variables (AR, AW, WR, WW) and conditions okToRead and okToWrite. It examines the duality of synchronization primitives and implements condition variables using semaphores as building blocks. The lecture then introduces thread safety, four classes of thread-unsafe functions (failing to protect shared variables, relying on persistent state, returning pointer to static variable, calling thread-unsafe functions), reentrant functions, and thread-safe C library functions.

📝 Lecture Summary

Readers/Writers

Constraints:

1. Readers can access database when no writers (Condition okToRead)
2. Writers can access database when no readers or writers (Condition okToWrite)
3. Only one thread manipulates state variables at a time

Basic structure of solution:

• Reader: wait until no writers → access database → check out -- wake up waiting writer
• Writer: wait until no readers or writers → access database → check out -- wake up waiting readers or writer

State variables:

• # of active readers -- AR = 0
• # of active writers -- AW = 0
• # of waiting readers -- WR = 0
• # of waiting writers -- WW = 0
• Condition okToRead = NIL
• Condition okToWrite = NIL
• Lock lock = FREE

Code:

Reader() {
    lock.Acquire();
    while ((AW + WW) > 0) { // check if safe to read if any writers, wait
        WR++;
        okToRead.Wait(&lock);
        WR--;
    }
    AR++;
    lock.Release();
    Access DB
    lock.Acquire();
    AR--;
    If (AR == 0 && WW > 0) // if no other readers still active, wake up writer
        okToWrite.Signal(&lock);
    lock.Release();
}

Writer() { // symmetrical
    lock.Acquire();
    while ((AW + AR) > 0) { // check if safe to write
        // if any readers or writers, wait
        WW++;
        okToWrite->Wait(&lock);
        WW--;
    }
    AW++;
    lock.Release();
    Access DB
    // check out
    lock.Acquire();
    AW--;
    if (WW > 0) // give priority to other writers
        okToWrite->Signal(&lock);
    else if (WR > 0)
        okToRead->Broadcast(&lock);
    lock.Release();
}

Questions:

1. Can readers or writers starve? Who and Why? — Writers could starve because readers are given priority (readers can join while writer is waiting)
2. Why does checkRead need a while? — Because multiple readers might be waiting; after a writer signals, the condition might change if another reader woke up first

💡 Why this matters: The readers/writers problem is fundamental in database systems and file systems where concurrent reads are safe but writes need exclusive access.

Semaphores and Monitors

Illustrate the differences by considering: can we build monitors out of semaphores?

Does this work?

Wait() { semaphore -> P(); }
Signal() { semaphore -> V(); }

Condition variables only work inside of a lock. Does this work?

Wait(Lock *lock) {
    lock->Release();
    Semaphore -> P();
    Lock -> Acquire();
}
Signal() {
    Semaphore -> V();
}

Key insight:

• What if thread signals and no one is waiting? No op.
• What if thread later waits? Thread waits.
• What if thread V's and no one is waiting? Increment.
• What if thread later does P? Decrement and continue.
• P + V are commutative — result is the same no matter what order they occur.
• Condition variables are NOT commutative. That's why they must be in a critical section — need to access state variables to do their job.

Does this fix the problem?

Signal() {
    if semaphore queue is not empty
        semaphore->V();
}

For one, not legal to look at contents of semaphore queue. But also: race condition — signaller can slip in after lock is released, and before wait. Then waiter never wakes up! Need to release lock and go to sleep atomically.

Implementation of condition variables using semaphores:

Semaphore mutex = 1; // This lock is outside of the condition object
Condition {
    Semaphore lock = 1;
    Semaphore waitSem = 0;
    Int numWaiters = 0;
}

wait(cond, mutex)                 signal(cond, mutex)
{                                 {
    P(cond.lock);                     P(cond.lock);
    cond.numWaiters++;                if (cond.numWaiters > 0)
    V(cond.lock);                     {
    V(mutex);                             V(cond.waitSem);
    P(cond.waitSem);                  }
    P(cond.lock);                     V(cond.lock);
    cond.numWaiters--;
    V(cond.lock);
    P(mutex);
}

Thread Safety

• Functions called from a thread must be thread-safe.
• We identify four (non-disjoint) classes of thread-unsafe functions:
  • Class 1: Failing to protect shared variables.
  • Class 2: Relying on persistent state across invocations.
  • Class 3: Returning a pointer to a static variable.
  • Class 4: Calling thread-unsafe functions.

Thread-Unsafe Functions

• Class 1: Failing to protect shared variables.

  • Fix: Use P and V semaphore operations.
  • Issue: Synchronization operations will slow down code.

• Class 3: Returning a ptr to a static variable.

  • Fixes:
    1. Rewrite code so caller passes pointer to struct: Requires changes in caller and callee.

       struct hostent *gethostbyname(char name) {
           static struct hostent h;
           <contact DNS and fill in h>
           return &h;
       }
       

    2. Lock-and-copy: Requires only simple changes in caller (and none in callee). However, caller must free memory.

       struct hostent *gethostbyname_ts(char *p) {
           struct hostent *q = Malloc(...);
           P(&mutex); /* lock */
           p = gethostbyname(name);
           *q = *p; /* copy */
           V(&mutex);
           return q;
       }
       hostp = Malloc(...));
       gethostbyname_r(name, hostp);
       

• Class 4: Calling thread-unsafe functions.

  • Calling one thread-unsafe function makes an entire function thread-unsafe.
  • Fix: Modify the function so it calls only thread-safe functions.

Reentrant Functions

• A function is reentrant iff it accesses NO shared variables when called from multiple threads.
• Reentrant functions are a proper subset of the set of thread-safe functions.
• The fixes to Class 2 and 3 thread-unsafe functions require modifying the function to make it reentrant.

Thread-Safe Library Functions

• All functions in the Standard C Library are thread-safe.
  • Examples: malloc, free, printf, scanf
• Most Unix system calls are thread-safe, with a few exceptions.

⭐ Key Takeaways

The readers/writers problem solution uses four state variables (AR, AW, WR, WW) and two condition variables (okToRead, okToWrite) protected by a single lock. Condition variables cannot be naively implemented with semaphores because semaphore P/V operations are commutative while condition variables are not — the lock release and sleep must be atomic to avoid race conditions. Thread-unsafe functions fall into four classes, with Class 3 (returning pointer to static variable) being fixable through lock-and-copy or rewriting callers to pass pointers. Reentrant functions are a proper subset of thread-safe functions that access no shared variables, making them inherently safe for concurrent use.

🧠 Quick Revision Questions

1. In the readers/writers solution, why must the Reader() use a while loop instead of an if statement when checking (AW + WW) > 0?
2. When a Writer finishes accessing the database, why does it first check if WW > 0 before checking WR > 0?
3. Why are semaphore P() and V() operations commutative, while condition variable Wait() and Signal() are not commutative?
4. In the implementation of condition variables using semaphores, why must V(mutex) and P(cond.waitSem) be separated by the count increment?
5. What is the difference between a thread-safe function and a reentrant function?

📘 Lecture 13 — Deadlocks

📖 Overview: This lecture provides a comprehensive introduction to deadlocks in operating systems, covering their formal definition, necessary conditions, detection methods, and various strategies for prevention and avoidance. Understanding deadlocks is critical for building robust concurrent systems where multiple processes or threads share resources.

🗂️ Topics Covered

The lecture covers the formal definition of a deadlock, the four necessary and sufficient conditions (mutual exclusion, no preemption, hold and wait, circular wait), detection through resource graphs, prevention techniques including removing one of the four conditions, the Banker's algorithm for deadlock avoidance, resource ordering, and current practices in commercial operating systems and databases.

📝 Lecture Summary

Overview of today’s lecture

This section introduces the main topics to be covered in Lecture 13, including the definition of deadlocks, detection methods, the four necessary and sufficient conditions for deadlock, examples, avoidance strategies, prevention techniques, and current practice in real systems.

Formal definition of a deadlock

A deadlock occurs when a set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. Usually, the event is the release of a currently held resource. None of the processes can run, release resources, or be awakened.

💡 Why this matters: This definition captures the essence of a deadlock — a self-sustaining cycle of waiting where no progress is possible.

Resource graph

A resource graph is used to model the relationship between processes and resources. It helps visualize which processes hold which resources and which resources processes are waiting for, making it easier to detect deadlocks.

Conditions for deadlock

Without all of the following four conditions, a deadlock cannot occur:

1. Mutual exclusion — resources cannot be shared (e.g., mutex on bounded buffer)
2. No preemption — if a process has a resource, it cannot be forcibly taken away
3. Hold and wait — processes hold allocated resources while waiting for additional ones
4. Circular wait — there exists a cycle of processes each waiting for a resource held by another in the cycle

Deadlock example

The lecture presents an example using a transfer function that operates on two accounts, each protected by a semaphore. Given two threads, a deadlock can occur if Thread 1 locks account a and waits for account b, while Thread 2 locks account b and waits for account a — creating a circular wait.

/* transfer x dollars from a to b */
void transfer(account *a, account *b, int x) {
    P(a->sema);
    P(b->sema);
    a->balance += x;
    b->balance -= x;
    V(a->sema);
    V(b->sema);
}

Deadlocks don’t require synch primitives

Deadlocks do not require locks; they just require circular constraints. An example is given with two threads that send and receive data using two circular buffers of size 4096 bytes. A full buffer causes the sender to block until the receiver removes data.

Example:

T1:                          T2:
send n bytes to T2          while(receive 4K of data)
;                           process data
while(receive data)         send 4K result to T1
display data                exit
exit

Solutions to Deadlock: Detect deadlock and fix

The first approach is to detect deadlocks and then fix them. Detection involves scanning the resource graph and detecting cycles. Fixing is the hard part and can be done by:

• Shooting the thread — force it to give up resources. However, this is not always possible; for instance, with a mutex, you cannot shoot a thread and leave the world in an inconsistent state.
• Rolling back actions of deadlocked threads (transactions) — this is a common technique in databases.

Transactions and two phase commit

In two-phase commit, all resources are acquired first. If any resource is blocked on, all previously acquired resources are released, and the transaction is retried.

Example (Printfile):

lock-file
lock-printer
lock-disk
do work
release all

Pros: Dynamic, simple, flexible Cons:

• Cost increases with the number of resources
• Length of critical section increases
• Hard to know what's needed a priori

Preventing deadlock

To prevent deadlock, one of the four conditions must be eliminated: a) No sharing — totally independent threads b) Preempt resources c) Make all threads request and reserve everything they'll need at the beginning

• Problem: Predicting future is hard, leading to over-estimation of resource needs (inefficient)

Banker's algorithm

The Banker's algorithm is more efficient than reserving all resources on startup. It works by:

• Stating maximum resource needs in advance
• Allocating resources dynamically when needed
• Waiting if granting a request would lead to deadlock (a request can be granted if some sequential ordering of requests is deadlock-free)

The algorithm allows the sum of maximum resource needs of all current threads to be greater than the total resources, as long as there is some way for all threads to finish without deadlock. For example, a thread can proceed if: total available resources - # allocated >= max remaining that might be needed by this thread.

In practice, the Banker's algorithm is rarely used since it requires predicting maximum resource requirements in advance.

Resource ordering

Resource ordering involves making everyone use the same ordering when accessing resources. For example, all threads must grab semaphores in the same order to prevent circular wait.

Current practice

• Microsoft SQL Server: The Database Engine automatically detects deadlock cycles. It chooses one session as a deadlock victim and terminates the current transaction with an error to break the deadlock.
• Oracle: Similar to SQL Server, plus multitable deadlocks can usually be avoided if transactions accessing the same tables lock those tables in the same order. For example, when both a master and detail table are updated, the master table is locked first, then the detail table.
• Windows internals (Linux no different): Unless they changed things significantly in Vista, the NT kernel architecture is described as a "deadlock minefield." With the multi-threaded re-entrant kernel, there is plenty of deadlock potential. Lock ordering is great in theory, and NT was originally designed with mutex levels, but they had to be abandoned due to complex interactions between memory management, the cache manager, and file systems.

⭐ Key Takeaways

The most critical points from this lecture are: deadlock occurs when each process in a set waits for an event only another in the set can cause, requiring all four conditions (mutual exclusion, no preemption, hold and wait, circular wait) simultaneously. Detection involves scanning resource graphs for cycles, while prevention requires eliminating at least one condition. The Banker's algorithm avoids deadlock by granting requests only if a safe sequence exists, but is rarely used in practice due to prediction difficulties. Real systems like SQL Server and Oracle automatically detect and resolve deadlocks by terminating a victim transaction, and commercial OS kernels still face significant deadlock challenges despite theoretical solutions.

🧠 Quick Revision Questions

1. What are the four necessary and sufficient conditions for a deadlock to occur?

2. How does a resource graph help in detecting deadlocks?

3. In the Banker's algorithm, what condition must be satisfied before a thread can proceed with its resource request?

4. What is the key difference between deadlock prevention and deadlock avoidance?

5. Why is resource ordering (locking resources in a consistent order) an effective strategy against deadlock, and why did NT kernel have to abandon it?

📘 Lecture 14 — Overview of today’s lecture

📖 Overview: This lecture explores the various paradigms of thread usage in operating systems, drawing from the Hauser et al. paper. It examines how threads are used to exploit CPU and I/O parallelism and for program structuring, while also discussing the pros and cons of different thread usage paradigms. Understanding these paradigms is crucial for designing robust and efficient multi-threaded applications.

🗂️ Topics Covered

The lecture begins with an overview of thread usage paradigms, covering uses of threads for CPU parallelism, I/O parallelism, and program structuring. It then details ten paradigms from the Hauser et al. paper: defer work, general pumps, slack processes, sleepers, one-shots, deadlock avoidance, rejuvenation, serializers, encapsulated fork, and exploiting parallelism. Each paradigm is explained with examples, and the lecture also discusses Bohr-bugs and Heisenbugs in the context of thread-related issues.

📝 Lecture Summary

Uses of threads

Threads are used for three main purposes in operating systems and applications. First, to exploit CPU parallelism, allowing a program to run two CPUs at once. Second, to exploit I/O parallelism, enabling the system to run I/O while computing or to perform multiple I/O operations simultaneously, such as listening to a window while running code (e.g., allowing commands during an interactive game). Third, threads are used for program structuring, for example, to implement timers.

Paradigms of thread usage (from Hauser et al paper)

The lecture outlines ten distinct paradigms of thread usage derived from the Hauser et al. paper. These paradigms include: defer work, general pumps, slack processes, sleepers, one-shots, deadlock avoidance, rejuvenation, serializers, encapsulated fork, and exploiting parallelism.

Defer work.

This is a very common scenario for thread usage. The client may see an unexpected response because something the client requested is fired off to happen in the background. Examples include forking off a document print operation, updating a window, or sending an email message. The issue arises if the thread hangs for some reason; the client may see confusing behavior on a subsequent request. 💡 Why this matters: Deferring work improves responsiveness but introduces complexity in error handling and state management.

Pumps

Pumps are components of producer-consumer pipelines that take input in, operate on it, then output it downstream. Their value is that they can absorb transient rate mismatches between producers and consumers. A slack process is a type of pump used to explicitly add delay, employed when trying to group small operations into batches.

Sleepers, one-shots

Sleepers and one-shots are threads that wait for some event, then trigger, then wait again. Examples include calling a procedure every 20ms or after some timeout. The lecture notes that you can think of a device interrupt handler as a kind of sleeper thread.

Deadlock avoiders

A deadlock avoider is a thread created to perform some action that might have blocked, launched by a caller who holds a lock and doesn’t want to wait. This prevents the caller from being blocked while holding the lock, which could otherwise lead to deadlock.

Bohr-bugs and Heisenbugs

Bruce Lindsey introduced these terms, referring to models of the atom. A Bohr-bug is like a Bohr nucleus — a nice solid little thing that you can hit reproducibly and hence can fix. A Heisenbug is hard to pin down; if you localize an instance, the bug shifts elsewhere. Heisenbugs result from non-deterministic executions, old corruption in data structures, and similar issues.

Task rejuvenation

This is a nasty style of thread. The application had multiple major subactivities, such as an input handler and renderer. When something awful happened, the approach was to create a new instance and pray. This is a reactive, unreliable method of handling failures. 💡 Why this matters: Rejuvenation is a sign of poor error handling design and should be avoided in favor of robust error recovery mechanisms.

Others

Serializers involve a queue and a thread that removes work from it and processes that work item by item. The code pattern is: for (;;) { get_next_event(); handle_event(); } Concurrency exploiters are used for multiple CPUs. Encapsulated forks are hidden threads used in library packages, where the library creates threads internally without the caller's explicit knowledge.

⭐ Key Takeaways

The lecture presents ten paradigms of thread usage, each with specific advantages and drawbacks. The most critical points for an exam are: understanding why defer work can lead to confusing client behavior if threads hang; grasping the role of pumps in absorbing rate mismatches in pipelines; recognizing that deadlock avoiders prevent blocking while holding locks; and being able to distinguish Bohr-bugs (reproducible) from Heisenbugs (non-deterministic and shifting). Additionally, you must understand that serializers process work item by item from a queue, while encapsulated forks hide thread creation in libraries.

🧠 Quick Revision Questions

1. What are the three main uses of threads mentioned in the lecture?
2. What is the primary issue with the "defer work" paradigm when a thread hangs?
3. What is a pump, and what value does it provide in producer-consumer pipelines?
4. What is the key difference between a Bohr-bug and a Heisenbug?
5. In the context of deadlock avoiders, why does a caller launch a new thread rather than performing the action directly?

📘 Lecture 15 — Threads considered marvelous

📖 Overview: This lecture examines the dual nature of threads—their benefits for handling blocking operations and their fundamental drawbacks stemming from non-determinism. It then transitions to event-oriented programming as an alternative paradigm and introduces CPU scheduling fundamentals, beginning with the First Come First Served (FCFS) algorithm and its convoy effect problem.

🗂️ Topics Covered

The lecture covers the benefits and harms of threads, classic thread-related issues like address space bloating and synchronization overhead, the event-oriented paradigm as a solution, goals of the perfect scheduler, problem cases in scheduling, and a detailed examination of First Come First Served (FCFS/FIFO) scheduling including the convoy effect with a numerical example.

📝 Lecture Summary

Threads considered marvelous

Threads are wonderful when some action may block for a while, such as a slow I/O operation or RPC. Your code remains clean and "linear". Moreover, aggregated performance is often far higher than without threading.

Threads considered harmful

They are fundamentally non-deterministic, hence invite Heisenbugs (bugs that disappear when you try to debug them). Reentrant code is really hard to write. Surprising scheduling can be a huge headache. When something "major" changes the state of a system, cleaning up threads running based on the old state is a pain.

Classic issues

Threads that get forked off, then block for some reason cause the address space soon to bloat due to number of threads increasing beyond a threshold, causing the application to crash. Erratic use of synchronization primitives makes the program incredibly hard to debug, with some problems seen only now and then. As threads grow in number, synchronization overhead becomes significant. Semaphore and lock queues become very large due to waiting threads.

💡 Why this matters: These classic issues explain why multithreaded programs often fail mysteriously in production but work fine in testing—the non-deterministic nature means bugs appear only under specific timing conditions.

Bottom line?

Concurrency bugs are incredibly common and very hard to track down and fix. Programmers find concurrency unnatural. The question becomes: try to package it better? Or identify software engineering paradigms that can ease the task of gaining high performance?

Event-oriented paradigm

The classic solution is to build an event-driven application and use threads as helpers. Connect each "external event source" to a main hand-crafted "event monitoring routine". This often will use signals or a kernel-supplied event notification mechanism to detect that I/O is available. Then package the event as an event object and put this on a queue. Kick off the event scheduler if it was asleep. The scheduler de-queues events, processes them one by one, and forks lightweight threads as needed (when blocking I/O is required). The Flash web server was built on this paradigm.

Problems with the architecture?

The event-oriented architecture only works if all the events show up and none is missed. It depends on the OS not "losing" events—the event notification mechanism must be efficient and scalable. The scheduler needs a way to block when no work to do and must be sure that event notification can surely wake it up. Common event notification mechanisms in Linux, Windows, etc. are select() and poll(). New much more efficient and scalable mechanisms include epoll (2.6 and above Linux kernel only) and IOCompletionPorts in Windows NT, XP, etc.

Goals of "the perfect scheduler"

The goals are to: minimize latency (metric = response time at user time scales ~50-150 milliseconds, or job completion time); maximize throughput (maximize number of jobs per unit time); maximize utilization (keep CPU and I/O devices busy—a recurring theme with OS scheduling); and ensure fairness (everyone gets to make progress, no one starves).

Problem cases

I/O goes idle because of blindness about job types. Optimization involves favoring jobs of type "A" over "B"—if there are lots of A's, B's starve. An interactive process gets trapped behind others, making response time worsen for no reason. Regarding priorities: if job A depends on job B, but A's priority is greater than B's priority, then B never runs.

First come first served (FCFS or FIFO)

This is the simplest scheduling algorithm: run jobs in the order that they arrive. In uni-programming, run until done (non-preemptive). In multi-programming, put job at back of queue when it blocks on I/O. The advantage is simplicity.

FCFS (2)

The disadvantage is that wait time depends on arrival order. It is unfair to later jobs, with the worst case being a long job arriving first.

📌 Example: three jobs (times: A=100, B=1, C=2) arrive nearly simultaneously. What's the average completion time?

• Order of execution: A first (100), then B (100+1=101), then C (101+2=103)
• Completion times: A=100, B=101, C=103
• Average completion time: (100+101+103) / 3 = 304/3 ≈ 101.33 time units

FCFS Convoy effect

A CPU-bound job will hold CPU until done, or it causes an I/O burst (rare occurrence, since the thread is CPU-bound). This creates long periods where no I/O requests are issued and the CPU is held. The result is poor I/O device utilization.

📌 Example: one CPU bound job, many I/O bound jobs:

1. CPU bound runs (I/O devices idle)
2. CPU bound blocks
3. I/O bound job(s) run, quickly block on I/O
4. CPU bound runs again
5. I/O completes
6. CPU bound still runs while I/O devices idle (continues...)

🔑 Definition — Convoy effect: The phenomenon where a single long CPU-bound job holds the CPU, causing many short I/O-bound jobs to wait, leading to poor I/O device utilization and overall system performance degradation.

⭐ Key Takeaways

Threads offer clean linear code and high performance for blocking operations, but introduce critical problems: non-determinism leading to Heisenbugs, address space bloat from blocked threads, and significant synchronization overhead. The event-oriented paradigm addresses this by using an event scheduler with lightweight threads, but depends on reliable OS event notification mechanisms like select(), poll(), epoll, or IOCompletionPorts. The perfect scheduler must balance latency, throughput, utilization, and fairness, but faces real problems like starvation, priority inversions, and the convoy effect. FCFS/FIFO scheduling, while simple, exhibits the convoy effect where a single CPU-bound job causes poor I/O utilization, demonstrated numerically with average completion time of 101.33 for jobs of lengths 100, 1, and 2.

🧠 Quick Revision Questions

1. What are Heisenbugs and why are they problematic in threaded programs?
2. Describe the classic issue where threads that get forked off and then block can cause application crashes.
3. How does the event-oriented paradigm solve threading problems, and what are its dependencies on the OS?
4. Why does the convoy effect cause poor I/O device utilization in FCFS scheduling?
5. Calculate the average completion time for jobs with lengths 5, 3, and 8 arriving nearly simultaneously under FCFS scheduling.

📘 Lecture 16 — Round robin (RR)

📖 Overview: This lecture introduces Round Robin scheduling as a solution to job monopolization, then explores its tradeoffs and disadvantages. It progresses to priority scheduling, discusses priority inversion and inheritance, and covers Shortest Time to Completion First (STCF) as an optimal approach, including its practical limitations and approximations like multi-level feedback queues.

🗂️ Topics Covered

The lecture covers Round Robin scheduling with its time slice mechanism and context switching tradeoffs, then moves to priority scheduling with static and dynamic priorities. It addresses thread dependencies through priority inversion and inheritance, explains Shortest Time to Completion First (STCF) and its optimality proof, discusses the challenge of predicting job length, and presents practical approximations including the elevator algorithm for disks and multi-level feedback queues.

📝 Lecture Summary

Round robin (RR)

Round Robin solves the problem of a job monopolizing the CPU by interrupting it. Each job runs for a defined time slice; when the time is up or the job blocks, it moves to the back of a FIFO queue. Most systems use some variant of this approach. The advantages are fair allocation of CPU across jobs and low average waiting time when job lengths vary.

🔑 Definition — Round Robin (RR): A CPU scheduling algorithm where each ready job runs for a fixed time slice, then is moved to the back of a FIFO queue, ensuring fair CPU distribution.

📐 Formula: Average completion time = (sum of completion times of all jobs) / (number of jobs)

📌 Example: If two jobs of time=100 each run under RR with a time slice, average completion time would be higher than FCFS because both jobs finish later; FCFS for same jobs gives completion times of 100 and 200 for an average of 150, while RR interleaving means both finish around 200, giving an average of ~200.

RR Time slice tradeoffs

Performance depends heavily on the length of the time slice. Context switching is not a free operation. If the time slice is set too high, you effectively get FCFS because processes finish or block before their slice is up anyway. If it's set too low, you spend all your time context switching between threads. Typical time slices are set to about 50-100 milliseconds, while context switches cost about 0.5-1 millisecond. The moral is that context switching is usually negligible (less than 1% per time slice) unless you context switch too frequently and lose all productivity.

💡 Why this matters: Choosing the right time slice is a critical design decision that balances responsiveness against overhead, directly impacting system performance.

Priority scheduling

Not all jobs are equal, so they are ranked. Each process has a priority; the system runs the highest priority ready job and uses round robin among processes of equal priority. Priorities can be static (fixed) or dynamic (changing over time), or both (as in Unix). Most systems use some variant of this approach. Common uses include coupling priority to job characteristics: to fight starvation, increase priority as time since last ran increases; to keep I/O busy, increase priority for jobs that often block on I/O. However, priorities can create deadlock because a high priority always runs over a low priority.

🔑 Definition — Priority scheduling: A scheduling algorithm where each process is assigned a priority, and the highest priority ready job is selected to run, with round robin among equal priorities.

Handling thread dependencies

Priority inversion occurs when a low-priority thread holds a lock needed by a high-priority thread. For example, T1 is high priority, T2 is low priority; T2 acquires lock L. In Scene 1: T1 tries to acquire L, fails, and spins, but T2 never gets to run. In Scene 2: T1 tries to acquire L, fails, and blocks; when T3 enters the system at medium priority, T2 still never gets to run. Scheduling means deciding who should make progress, and obviously a thread's importance should increase with the importance of those that depend on it. This leads to priority inheritance, where a lower-priority thread temporarily inherits the priority of a higher-priority thread waiting for a resource it holds.

🔑 Definition — Priority inheritance: A mechanism where a lower-priority thread temporarily inherits the priority of a higher-priority thread that is waiting for a resource held by the lower-priority thread.

Shortest time to completion first (STCF)

STCF (or shortest-job-first) runs whatever job has the least amount of work to do. It can be pre-emptive or non-pre-emptive. This algorithm is provably optimal: moving a shorter job before a longer job improves the waiting time of the short job more than it harms the waiting time of the long job.

📐 Formula: Average completion time = (sum of completion times) / (number of jobs)

📌 Example: Three jobs A (time=1), B (time=2), C (time=100). Under STCF: A finishes at 1, B at 3, C at 103. Average completion = (1+3+103)/3 = ~35. This compares to FCFS where if C runs first, average completion = (100+102+103)/3 = ~101.7.

STCF Optimality Intuition

Consider 4 jobs a, b, c, d run in lexical order. The first (a) finishes at time a, the second (b) finishes at time a+b, the third (c) finishes at time a+b+c, and the fourth (d) finishes at time a+b+c+d. Therefore, average completion = (4a+3b+2c+d)/4. Minimizing this requires that a ≤ b ≤ c ≤ d, meaning jobs should run in order of increasing length.

📐 Formula: Average completion time for n jobs run in order = (n×t₁ + (n-1)×t₂ + ... + 1×tₙ)/n

STCF – The Catch

The problem with STCF is how to know the job length in advance. It requires predicting how long a job will take, which is difficult in practice.

How to know job length?

One approach is to have the user tell us, and if they lie, kill the job — but this is not useful in practice. Alternatively, use the past to predict the future: a long-running job will probably take a long time more. View each job as a sequence of sequentially alternating CPU and I/O bursts. If previous CPU bursts in the sequence have run quickly, future ones will too (usually). The challenge is what to do when the past does not equal the future.

Approximate STCF

The approximation of STCF predicts the length of the current CPU burst using the length of the previous burst. The system records the length of the previous burst (0 when just created). At a scheduling event (unblock, block, exit, etc.), it picks the job with the smallest past run length off the ready queue.

Practical STCF

For disks, it is possible to predict the length of the next job! A job is a request from the disk, and job length approximates the cost of moving the disk arm to the position of the requested disk block (farther away = more costly). STCF for disks is called shortest-seek-time-first (SSTF): do the read/write request closest to the current position. It can be pre-emptive: if new jobs arrive that can be serviced on the way, do these too. The problem with SSTF is that it can starve faraway requests. The solution is the elevator algorithm: the disk arm has a direction, and it does the closest request in that direction, sweeping from one end to the other.

🔑 Definition — Elevator algorithm (SCAN): A disk scheduling algorithm where the disk arm moves in one direction, servicing the closest request in that direction, then reverses direction at the end, analogous to an elevator.

~STCF vs RR

Two processes P1 and P2: with a 1ms time slice, RR would switch to P1 9 times for no reason (since P1 would still be blocked on I/O). ~STCF offers better I/O utilization because it avoids unnecessary context switches.

Generalizing: priorities + history

~STCF is a good core idea but doesn't have enough state. The usual STCF problem is starvation (which occurs when long jobs never get CPU because shorter jobs keep arriving). The solution is to compute priority as a function of both CPU time the process has consumed and time since the process last ran.

Multi-level feedback queue (or exponential queue) is a priority scheme where priorities are adjusted to penalize CPU-intensive programs and favor I/O-intensive programs. It was pioneered by CTSS at MIT in 1962.

🔑 Definition — Multi-level feedback queue: A scheduling algorithm that uses multiple priority queues and adjusts process priorities dynamically based on observed behavior, penalizing CPU-bound processes and favoring I/O-bound processes.

Visual aid of a multi-level system

Priorities and time-slices change as needed depending on the characteristics of the process. Processes that use their full time slice (CPU-bound) get moved to lower priority queues with larger time slices, while processes that block before their slice ends (I/O-bound) stay at higher priority queues.

💡 Why this matters: Multi-level feedback queues provide a practical, adaptive scheduling approach that balances responsiveness for interactive tasks with throughput for CPU-intensive tasks without requiring a priori knowledge of job lengths.

⭐ Key Takeaways

Round Robin solves CPU monopolization by using time slices but suffers from context switching overhead and poor performance for equal-sized jobs compared to FCFS. Priority scheduling introduces ranking but can cause priority inversion, which is resolved by priority inheritance. STCF is provably optimal for minimizing average completion time but requires knowing job lengths in advance, which is impractical. Approximations like predicting from past behavior and multi-level feedback queues offer practical solutions that dynamically adjust priorities based on observed CPU and I/O patterns, with the elevator algorithm solving starvation in disk scheduling.

🧠 Quick Revision Questions

1. What is the main disadvantage of Round Robin scheduling when all jobs have equal size?
2. How does priority inheritance solve the priority inversion problem?
3. Why is STCF considered provably optimal, and what is its main practical limitation?
4. How does the multi-level feedback queue address the starvation problem in priority scheduling?
5. What is the elevator algorithm, and how does it solve the starvation problem in disk scheduling?

📘 Lecture 17 — Some Problems with Multilevel Queue Concept & Linux Scheduling & Lottery Scheduling & Multiprocessor Systems

📖 Overview: This lecture addresses fundamental flaws in traditional multilevel queue scheduling, introduces Linux's real-time scheduling classes as an improvement, proposes Lottery Scheduling as a probabilistic alternative to ad hoc priority systems, and classifies multiprocessor systems by coupling and granularity of parallelism. These concepts are critical for understanding how modern OSes balance fairness, responsiveness, and scalability across diverse workloads.

🗂️ Topics Covered

The lecture begins by diagnosing problems with multilevel queues (starvation and predictive inaccuracy). It then summarizes classic scheduling algorithms (FIFO, RR, STCF, Multilevel Feedback). Next, it covers Linux scheduling with its three classes (SCHED_FIFO, SCHED_RR, SCHED_OTHER) and specific rules. Lottery scheduling is introduced as a simpler, probabilistic method using tickets. Finally, the lecture classifies multiprocessor systems by coupling type and granularity of parallelism (coarse, medium, fine-grained).

📝 Lecture Summary

Some problems with multilevel queue concept

• Can’t low priority threads starve? The ad hoc fix is: when a thread is skipped over, increase its priority to prevent indefinite starvation.
• What about when past doesn’t predict future? Example: a CPU-bound process switches to I/O-bound. Past behavior is no longer a good predictor. The solution is to let past predictions age, so older data counts less toward the current view of the world.

🔑 Definition — Aging: A technique where the weight of a process's past behavior decreases over time, so recent behavior influences scheduling decisions more than older history.

Summary

• FIFO: + simple; - short jobs can get stuck behind long ones; poor I/O performance.
• RR: + better for short jobs; - poor when jobs are the same length.
• STCF: + optimal for average response time and average time-to-completion; - hard to predict the future; - unfair to long jobs.
• Multi-level feedback: + approximates STCF; - unfair to long-running jobs.

💡 Why this matters: No single algorithm is perfect; each trades off simplicity, fairness, responsiveness, and predictability.

Some Unix scheduling problems

• How does the priority scheme scale with the number of processes?
• How to give a process a given percentage of CPU?
• OS implementation problem: The OS takes precedence over user processes, but a user process can create lots of kernel work (e.g., many network packets arrive), forcing the OS to process them during read/write system calls.

Linux Scheduling

• Builds on traditional UNIX multi-level feedback queue scheduler by adding two new scheduling classes.
• Linux scheduling classes:
  • SCHED_FIFO: FCFS real-time threads.
  • SCHED_RR: round-robin real-time threads.
  • SCHED_OTHER: other non-real-time threads.
• Multiple priorities may be used within a class. Priorities in real-time classes are higher than non-real-time classes.
• Rules for SCHED_FIFO:
  1. The system will not interrupt a SCHED_FIFO thread except in the following cases: a. Another FIFO thread of higher priority becomes ready. b. The executing FIFO thread blocks on I/O, etc. c. The executing FIFO thread voluntarily gives up the CPU (e.g., terminates or yields).
  2. When an executing FIFO thread is interrupted, it is placed in the queue associated with its priority.
• SCHED_RR is similar to SCHED_FIFO except that there is a time-slice. On expiry of the time slice, if the thread is still executing, it is preempted and another thread from either SCHED_FIFO or SCHED_RR is selected.
• SCHED_OTHER is managed by the traditional UNIX scheduling algorithms (multi-level feedback queue).

Lottery scheduling: random simplicity

• Problem: The whole priority thing is really ad hoc. How to ensure processes will be equally penalized under load?
• Lottery scheduling: Very simple idea:
  • Give each process some number of lottery tickets.
  • On each scheduling event, randomly pick a ticket.
  • Run the winning process.
  • To give process P n% of CPU, give it (total tickets) * n%.
• How to use?
  • Approximate priority: low-priority → few tickets; high-priority → many tickets.
  • Approximate STCF: give short jobs more tickets, long jobs fewer.
  • Key: If a job has at least 1 ticket, it will not starve.
• Grace under load change:
  • Add or delete jobs (and their tickets) affects all proportionally.
  • Example: Give all jobs 1/n of CPU? 4 jobs, 1 ticket each → each gets (on average) 25% of CPU. Delete one job → automatically adjusts to 33% of CPU!
• Easy priority donation: Donate tickets to a process you’re waiting on. Its CPU% scales with tickets of all waiters.

🔑 Definition — Lottery Scheduling: A probabilistic CPU scheduling algorithm where each process receives a number of tickets, and a random ticket draw decides which process runs next; CPU share is proportional to ticket count.

📐 Formula: Process P gets n% of CPU = (tickets of P / total tickets) × 100% 📌 Example: With 4 jobs, each gets 1 ticket: total = 4 tickets. Each job gets (1/4) × 100% = 25% of CPU. If one job is deleted, total = 3 tickets, each remaining job gets (1/3) × 100% ≈ 33% of CPU.

Classifications of Multiprocessor Systems

• Loosely coupled or distributed multiprocessor, or cluster: Each processor has its own memory and I/O channels.
• Functionally specialized processors: Such as I/O processor, controlled by a master processor.
• Tightly coupled multiprocessing: Processors share main memory, controlled by operating system.

🔑 Definition — Tightly Coupled Multiprocessing: A multiprocessor architecture where all processors share a single main memory and are coordinated by the OS, enabling coherent data sharing.

Granularity of parallelism

• Coarse and Very Coarse-Grained Parallelism: Synchronization among processes at a very gross level (after > 2000 instructions on average). Good for concurrent processes on a multiprogrammed uniprocessor. Can be supported on a multiprocessor with little change.
• Medium grained parallelism: Single application is a collection of threads. Threads usually interact frequently.
• Fine-Grained Parallelism: Highly parallel applications. Specialized and fragmented area.

🔑 Definition — Granularity of Parallelism: The average amount of computation (in instructions) between synchronization points in a parallel program; coarse grain has large intervals, fine grain has small intervals.

⭐ Key Takeaways

For the exam, remember that multilevel queues suffer from starvation and predictive inaccuracy, solved by priority boosting and aging. Linux scheduling extends the traditional feedback queue with SCHED_FIFO (non-preemptible except by higher priority or blocking) and SCHED_RR (preemptible via time-slice). Lottery scheduling solves the ad hoc priority problem by allocating CPU proportionally via random ticket draws, automatically adjusting under load changes and enabling simple priority donation. Multiprocessor systems are classified by coupling (loosely coupled clusters vs. tightly coupled shared memory) and parallelism granularity (coarse > 2000 instructions, medium threads, fine-grained). STCF is optimal in theory but impractical because it requires predicting the future.

🧠 Quick Revision Questions

1. What two main problems does the multilevel queue concept face, and what are the ad hoc solutions?
2. List the three Linux scheduling classes and explain the key rule difference between SCHED_FIFO and SCHED_RR.
3. In lottery scheduling, if you have 5 jobs each with 10 tickets, what percentage of CPU does each get? What happens if you add two more jobs each with 10 tickets?
4. How does lottery scheduling automatically handle graceful adjustment when jobs are added or removed?
5. What is the difference between coarse-grained and fine-grained parallelism in terms of the number of instructions between synchronizations?

📘 Lecture 18 — Assignment of Processes to Processors

📖 Overview: This lecture covers how processes and threads are assigned to processors in multiprocessor systems, comparing different scheduling architectures. It also introduces real-time systems, distinguishing between hard and soft real-time requirements and outlining the characteristics of real-time operating systems.

🗂️ Topics Covered

The lecture covers assignment of processes to processors using group scheduling, global queues, master/slave architecture, and peer architecture. It then discusses process scheduling with single and multiple queues, thread scheduling and multiprocessor thread scheduling using dedicated processor assignment and dynamic scheduling. Load sharing, its disadvantages, gang scheduling, and dedicated processor assignment are explained in detail. Finally, the lecture introduces real-time systems, hard vs. soft real-time systems, and the characteristics of real-time operating systems including determinism, responsiveness, and user control.

📝 Lecture Summary

Assignment of Processes to Processors

Treat processors as a pooled resource and assign process to processors on demand. One approach is to permanently assign a process to a processor, known as group or gang scheduling. This dedicates a short-term queue for each processor, resulting in less overhead, but a processor could be idle while another processor has a backlog. An alternative is a global queue, where processes are scheduled to any available processor.

The master/slave architecture has key kernel functions always run on a particular processor. The master is responsible for scheduling, and the slave sends service requests to the master. Disadvantages are that failure of the master brings down the whole system and the master can become a performance bottleneck. The peer architecture allows the operating system to execute on any processor, with each processor doing self-scheduling, but this complicates the operating system.

Process Scheduling

Process scheduling uses a single queue for all processes, but multiple queues are used for priorities. All queues feed to the common pool of processors.

Thread Scheduling

Thread scheduling executes separate from the rest of the process. An application can be a set of threads that cooperate and execute concurrently in the same address space. Threads running on separate processors yield a dramatic gain in performance.

Multiprocessor Thread Scheduling

Dedicated processor assignment threads are assigned to a specific processor. Dynamic scheduling allows the number of threads to be altered during the course of execution.

Load Sharing

Load is distributed evenly across the processors. No centralized scheduler is required. Load sharing uses global queues and is the most commonly used paradigm, used by Linux, Windows, and several UNIX flavors on multi-processor machines.

Disadvantages of Load Sharing

The central queue needs mutual exclusion, which may be a bottleneck when more than one processor looks for work at the same time. Preemptive threads are unlikely to resume execution on the same processor, so cache use is less efficient. If all threads are in the global queue, all threads of a program will not gain access to the processors at the same time.

Gang Scheduling

Gang scheduling is the simultaneous scheduling of threads that make up a single process. It is useful for applications where performance severely degrades when any part of the application is not running, and threads often need to synchronize with each other.

Dedicated Processor Assignment

When an application is scheduled, its threads are assigned to processors using a graph theoretic optimization algorithm on the control flow graph (CFG) of the application where each node in the CFG is a thread. Disadvantages are that some processors may be idle and there is no multiprogramming of processors.

Real-Time Systems

The correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced. Tasks or processes attempt to control or react to events that take place in the outside world. These events occur in "real time" and tasks must be able to keep up with them.

Hard real-time systems

If deadlines are not met, results are catastrophic. Examples include air traffic control and aircraft auto-pilot.

Soft real-time systems

The system tries to meet all deadlines in a best effort manner, and succeeds in meeting most of them. The overall percentage of met deadlines is very high on the average. Missing a few occasionally does not result in catastrophic conditions.

Characteristics of Real-Time Operating Systems

Deterministic: Operations are performed at fixed, predetermined times or within predetermined time intervals. It is concerned with how long the operating system delays before acknowledging an interrupt and there is sufficient capacity to handle all the requests within the required time.

Responsiveness: How long, after acknowledgment, it takes the operating system to service the interrupt. This includes the amount of time to begin execution of the interrupt, the amount of time to perform the interrupt, and the effect of interrupt nesting.

User control: The user specifies priority, specifies paging, what processes must always reside in main memory, disks algorithms to use, and the rights of processes.

⭐ Key Takeaways

The key to multiprocessor scheduling is choosing between architectures like master/slave (single point of failure and bottleneck) and peer (complex but robust), and between approaches like gang scheduling (synchronized threads) and load sharing (efficient but has cache and bottleneck issues). Real-time systems are defined by their timing correctness, with hard real-time systems requiring absolute deadline adherence to avoid catastrophic failure, while soft real-time systems can tolerate occasional missed deadlines. The three critical characteristics of a real-time OS are determinism (predictable interrupt acknowledgment), responsiveness (fast interrupt handling), and user control (priority and resource allocation authority).

🧠 Quick Revision Questions

1. What are the two main approaches to assigning processes to processors, and what is the key difference between them?
2. Describe the major disadvantage of the master/slave architecture in multiprocessor systems.
3. Why does load sharing lead to inefficient cache use?
4. What is the fundamental difference between hard real-time and soft real-time systems regarding the consequences of missing a deadline?
5. List the three key characteristics of a real-time operating system and briefly explain what each one means.

📘 Lecture 19 — Characteristics of Real-Time Operating Systems

📖 Overview: This lecture examines the defining characteristics and features of Real-Time Operating Systems (RTOS), focusing on reliability, fail-soft operation, and specialized scheduling techniques. It also introduces fundamental concepts of dynamic memory allocation, comparing explicit and implicit allocators, and explains the process memory image structure.

🗂️ Topics Covered

The lecture covers the characteristics of RTOS including reliability and fail-soft operation, followed by detailed features such as fast process switching and priority-based preemptive scheduling. It then explores four categories of real-time scheduling: static table-driven, static priority-driven preemptive, dynamic planning-based, and dynamic best effort. Deadline scheduling information parameters are listed, followed by Rate Monotonic Scheduling (RMS). The lecture concludes with dynamic memory allocation concepts, comparing explicit vs. implicit allocators, and describes the process memory image with assumptions and constraints.

📝 Lecture Summary

Characteristics of Real-Time Operating Systems

Real-Time Operating Systems prioritize reliability because degradation of performance may have catastrophic consequences. The system must support fail-soft operation, which is the ability of a system to fail in such a way as to preserve as much capability and data as possible. This property contributes to system stability.

Features of Real-Time Operating Systems

RTOS systems are designed with specific features to meet timing constraints. These include fast process or thread switch, small size, and the ability to respond to external interrupts quickly. They support multitasking with inter-process communication tools such as semaphores, signals, and events. RTOS uses special sequential files that can accumulate data at a fast rate and implements preemptive scheduling based on priority. Other features include minimization of intervals during which interrupts are disabled, the ability to delay tasks for a fixed amount of time, and support for special alarms and timeouts.

Real-Time Scheduling

Real-time scheduling is classified into four approaches. Static table-driven scheduling determines at load or even compile time when a task begins execution. Static priority-driven preemptive scheduling uses a traditional priority-driven scheduler. Dynamic planning-based scheduling determines feasibility at run time. Dynamic best effort scheduling performs no feasibility analysis.

Deadline Scheduling

Deadline scheduling uses several pieces of information to make decisions: ready time, starting deadline, completion deadline, processing time, resource requirements, priority, and subtask scheduler.

💡 Why this matters: These parameters allow the scheduler to determine whether a set of tasks can meet their deadlines, which is critical for systems where timing failures can be catastrophic.

Rate Monotonic Scheduling

Rate Monotonic Scheduling (RMS) assigns priorities to tasks on the basis of their periods. The highest-priority task is the one with the shortest period. This is a static priority assignment that is optimal among fixed-priority scheduling algorithms.

Dynamic Memory Allocation

Dynamic memory allocation involves two types of allocators. An explicit memory allocator requires the application to allocate and free space (e.g., malloc and free in C). An implicit memory allocator requires the application to allocate space but does not free it manually (e.g., garbage collection in Java, ML, or Lisp). In both cases, the memory allocator provides an abstraction of memory as a set of blocks and gives out free memory blocks to the application.

🔑 Definition — explicit memory allocator: An allocator where the application both allocates and frees space (e.g., malloc/free in C) 🔑 Definition — implicit memory allocator: An allocator where the application allocates but does not free space (e.g., garbage collection in Java, ML, or Lisp)

Process Memory Image

The process memory image is assumed to be word addressed (each word can hold a pointer). The lecture notes the following constraints for applications and allocators. Applications: can issue arbitrary sequence of allocation and free requests; free requests must correspond to an already allocated block. Allocators: cannot control the number or size of allocated blocks; must respond immediately to all allocation requests (cannot reorder or buffer requests); must allocate blocks from free memory (can only place un-allocated blocks in free memory); must align blocks to satisfy all alignment requirements (e.g., 8 byte alignment for GNU malloc (libc malloc) on Linux machines).

⭐ Key Takeaways

Real-Time Operating Systems must be highly reliable because any performance degradation can lead to catastrophic outcomes, and they must support fail-soft operation to preserve data and capability during failures. Their features include fast process switching, quick interrupt response, priority-based preemptive scheduling, and inter-process communication tools. There are four types of real-time scheduling: static table-driven, static priority-driven preemptive, dynamic planning-based, and dynamic best effort. Rate Monotonic Scheduling assigns highest priority to the task with the shortest period. In dynamic memory allocation, explicit allocators require both allocation and freeing by the application, while implicit allocators handle freeing automatically through garbage collection, and all allocators must meet strict constraints regarding immediate response, alignment, and block management.

🧠 Quick Revision Questions

1. What are the two key characteristics of Real-Time Operating Systems related to failure and performance?
2. Name four specific features of an RTOS that help it meet timing requirements.
3. How does static priority-driven preemptive scheduling differ from dynamic planning-based scheduling?
4. In Rate Monotonic Scheduling, which task receives the highest priority?
5. What is the fundamental difference between an explicit memory allocator and an implicit memory allocator?

📘 Lecture 20 — Overview of today’s lecture

📖 Overview: This lecture covers the goals of a good memory allocator, the problem of memory fragmentation (internal and external), and implementation issues for memory allocators. It introduces implicit list-based allocators in detail, including how blocks are tracked, allocated, freed, and coalesced.

🗂️ Topics Covered

The lecture covers the goals of a good malloc/free system, including time performance and space utilization. It then explains internal and external fragmentation, and why fragmentation cannot be fully solved. Implementation issues such as knowing how much to free and tracking free blocks are discussed, followed by a detailed explanation of the implicit list-based allocator, including finding free blocks, allocating, freeing, and coalescing.

📝 Lecture Summary

Goals of Good malloc/free

The primary goals of a memory allocator are good time performance and good space utilization. For time, operations should ideally take constant time and certainly not linear time in the number of blocks. For space, user-allocated structures should make up a large fraction of the heap to minimize fragmentation. Other goals include good locality properties (allocations close in time should be close in space) and robustness (ability to check that a free pointer is valid and that memory references are to allocated space).

🔑 Definition — Fragmentation: Poor memory utilization caused by the inability to use available memory efficiently.

Internal Fragmentation

Internal fragmentation is the difference between the block size and the payload size for a given block. It is caused by overhead from maintaining heap data structures, padding for alignment purposes, or explicit policy decisions (e.g., not splitting a block). Internal fragmentation depends only on the pattern of previous requests, making it easy to measure.

External Fragmentation

External fragmentation occurs when there is enough aggregate heap memory, but no single free block is large enough to satisfy a request. Unlike internal fragmentation, external fragmentation depends on the pattern of future requests and is therefore difficult to measure.

💡 Why this matters: External fragmentation is a major challenge for allocators because it cannot be predicted or fully prevented.

Impossible to “solve” fragmentation

There is no "best" allocator because all designs involve tradeoffs. A theoretical result states that for any possible allocation algorithm, there exist streams of allocation and deallocation requests that defeat the allocator and force it into severe fragmentation. In practice, "pretty well" means about 20% fragmentation under many workloads.

Knowing How Much to Free

The standard method for knowing how much memory to free is to keep the length of a block in the word preceding the block. This word is often called the header field or header.

Keeping Track of Free Blocks

Four methods are described for keeping track of free blocks:

• Method 1: Implicit list — links all blocks using lengths.
• Method 2: Explicit list — uses pointers within the free blocks to link them.
• Method 3: Segregated free list — uses different free lists for different size classes.
• Method 4: Blocks sorted by size — uses a balanced tree (e.g., Red-Black tree) with pointers within each free block, using length as a key.

Method 1: Implicit List

The implicit list method requires identifying whether each block is free or allocated. This is typically done using an allocated flag stored in the block header.

Implicit List: Finding a Free Block

Three strategies are used to find a free block:

• First fit: Search the list from the beginning and choose the first free block that fits the request.
• Next fit: Like first-fit, but search the list from the location where the previous search ended.
• Best fit: Search the entire list and choose the free block with the closest size that fits the request.

Implicit List: Allocating in Free Block

When allocating in a free block, the allocator may need to split the block. Splitting divides the free block into two parts: one allocated block of the requested size and one remaining free block.

Implicit List: Freeing a Block

The simplest implementation of freeing a block only requires clearing the allocated flag:

void free_block(ptr p) { *p = *p & -2; }

Implicit List: Coalescing

Coalescing joins a freed block with the next and/or previous block if they are also free. This combines adjacent free blocks into a single larger free block, reducing external fragmentation.

Implicit List: Bidirectional Coalescing

To enable coalescing with the previous block, the allocator uses boundary tags (Knuth73). This replicates the size/allocated word at the bottom of free blocks, allowing traversal of the list backward. However, this requires extra space for the additional tag.

🔑 Definition — Boundary tags: A technique that replicates the size and allocated status at both the top and bottom of a block, enabling bidirectional traversal for coalescing.

⭐ Key Takeaways

The lecture establishes that memory allocators have primary goals of good time performance and space utilization, but fragmentation (both internal and external) is an inherent challenge that cannot be fully solved — any allocator can be defeated by a specific sequence of allocation and deallocation requests. Internal fragmentation depends on past requests and is easy to measure, while external fragmentation depends on future requests and is difficult to measure. Four methods for tracking free blocks are introduced, with the implicit list method being the most basic. Key operations in an implicit list allocator include finding a free block using first fit, next fit, or best fit; splitting during allocation; clearing the allocated flag during freeing; and coalescing with adjacent free blocks to reduce fragmentation. Boundary tags enable bidirectional coalescing but require extra overhead.

🧠 Quick Revision Questions

1. What are the two primary goals of a good memory allocator, and what are some additional goals?
2. What is the difference between internal fragmentation and external fragmentation?
3. Why is it impossible to have a "best" memory allocator?
4. Describe the four methods for keeping track of free blocks in a memory allocator.
5. What is coalescing in the context of an implicit list allocator, and how do boundary tags enable bidirectional coalescing?

📘 Lecture 21 — Overview of Today’s Lecture

📖 Overview: This lecture completes the discussion of explicit free list allocators, covering LIFO vs. address-ordered freeing policies and segregated free lists. It then explores how real program allocation patterns (ramps, peaks, plateaus) can be exploited for performance, and introduces the fundamentals of garbage collection as a form of automatic memory management.

🗂️ Topics Covered

The lecture covers explicit free list base allocator details including freeing with LIFO policy and segregated free lists, then moves to exploiting allocation patterns of programs by exploiting peaks via arena allocators, and concludes with an introduction to garbage collection including reference counting, memory as a graph, and the assumptions garbage collectors make about pointers.

📝 Lecture Summary

Explicit Free Lists

Explicit free lists maintain a linked list data structure of only the free blocks in the heap, rather than marking free/allocated status in the block headers themselves. Each free block contains pointers to the previous and next free block in the list, allowing the allocator to traverse only free blocks rather than all blocks when searching for a suitable free block.

🔑 Definition — Explicit Free List: A linked list that connects only the free blocks in the heap, where each free block contains a predecessor pointer and a successor pointer to other free blocks.

Allocating From Explicit Free Lists

When allocating from an explicit free list, the allocator searches the linked list of free blocks using a placement policy (e.g., first fit, best fit). Once a suitable block is found, it is removed from the free list. If the block is larger than needed, the remainder may be split and re-inserted into the free list as a smaller free block.

Freeing With Explicit Free Lists

The insertion policy determines where in the free list a newly freed block is placed. Two common policies exist:

1. LIFO (last-in-first-out) policy: Insert the freed block at the beginning of the free list. This is simple and fast but can lead to fragmentation over time.
2. Address-ordered policy: Insert freed blocks so that free list blocks are always in increasing address order (addr(pred) < addr(curr) < addr(succ)). This improves spatial locality and reduces fragmentation.

Freeing With a LIFO Policy

When freeing a block with LIFO policy, four cases arise depending on whether the adjacent blocks (previous and next in memory) are free or allocated:

• Case 1: a-a-a — Both neighbors are allocated. The freed block is simply inserted at the front of the free list as a single isolated free block.
• Case 2: a-a-f — The next block is free. The freed block is coalesced with the next free block, and the combined block is inserted at the front of the free list.
• Case 3: f-a-a — The previous block is free. The freed block is coalesced with the previous free block, which is already in the free list. The combined block remains at the previous block's position.
• Case 4: f-a-f — Both neighbors are free. The freed block is coalesced with both adjacent free blocks, and the combined block replaces them in the free list.

Explicit List Summary

• Comparison to implicit list: Allocation is linear time in the number of free blocks instead of total blocks — this is much faster when most memory is full.
• Disadvantages: Slightly more complicated allocate and free operations since blocks must be moved in and out of the list. Extra space is required for the links (2 extra words needed for each block).
• Main use: Linked lists are primarily used in conjunction with segregated free lists, where multiple linked lists are kept for different size classes or possibly for different types of objects.

Simple Segregated Storage

Simple segregated storage maintains a separate free list for each size class (e.g., 16-byte blocks, 32-byte blocks, 64-byte blocks). When a request comes in, the allocator goes directly to the appropriate size class list.

• No splitting: Blocks are never split; if a block of exact size is unavailable, the allocator may request more memory from the OS.
• Tradeoffs: This approach is very fast (O(1) allocation and free for fixed-size blocks) but can fragment badly because small blocks cannot be split to satisfy larger requests.

Segregated Fits

Segregated fits uses an array of free lists, each one for some size class. To allocate, the appropriate list is searched; to free a block, coalescing is performed and the block is placed on the appropriate list (optional).

• Tradeoffs: Faster search than sequential fits (log time for power-of-two size classes). Controls fragmentation better than simple segregated storage. However, coalescing can increase search times; deferred coalescing can help by postponing coalescing operations.

Known Patterns of Real Programs

Programs exhibit three common allocation patterns:

1. Ramps: Accumulate data monotonically over time (e.g., logging systems that keep growing).
2. Peaks: Allocate many objects, use them briefly, then free all of them (e.g., processing a single request or image).
3. Plateaus: Allocate many objects, use them for a long time (e.g., data structures that persist throughout the program's lifetime).

Exploiting Peaks

Peak phases involve allocating a lot of memory, then freeing everything at once. An arena allocator can exploit this pattern by allocating memory in large chunks and simply resetting the pointer to the beginning when the phase ends.

• Advantages: Allocation is just a pointer increment (very fast), free is essentially free (no per-block work), and no wasted space for tags or list pointers.

Implicit Memory Management: Garbage Collection

Garbage collection is the automatic reclamation of heap-allocated storage — the application never has to explicitly call free. The memory manager automatically detects when memory is no longer reachable and reclaims it.

Garbage Collection

The memory manager must determine when memory can be freed. This requires certain assumptions about pointers:

1. The memory manager can distinguish pointers from non-pointers (e.g., integers that happen to look like addresses).
2. All pointers point to the start of a block (no pointers into the middle of allocated regions).
3. Cannot hide pointers (e.g., by coercing them to an int and then back again), as the collector cannot track disguised references.

💡 Why this matters: These assumptions are critical because the garbage collector must accurately identify which memory locations contain valid pointers to heap objects. If these assumptions are violated, the collector may free memory that is still in use or fail to reclaim memory that should be freed.

Reference Counting

Reference counting is a garbage collection algorithm where each object maintains a reference count — the number of pointers pointing to it.

• Algorithm:
  • Each object has a "ref count" tracking how many pointers reference it.
  • The ref count is incremented when a new pointer is set to point to the object.
  • The ref count is decremented when a pointer is killed (e.g., overwritten or goes out of scope).
  • When the ref count reaches zero, the object is freed.

🔑 Definition — Reference Count: A counter associated with each object that tracks how many pointers currently reference that object; when it reaches zero, the object is reclaimed.

Problems with Reference Counting

Circular data structures always have ref count greater than zero because objects point to each other in a cycle, even when no external pointers reference the cycle. For example, if object A points to object B and object B points to object A, both have ref count ≥ 1, yet neither is reachable from the program's roots. This causes memory leaks since the garbage collector cannot reclaim cycles using reference counting alone.

📌 Example: Consider two objects, A and B, where A.next = B and B.prev = A. If the only pointer to A from the stack is removed, A and B still have ref counts of 1 each (pointing to each other), so neither is freed even though both are unreachable from the program.

Memory as a Graph

We view memory as a directed graph:

• Each block is a node in the graph.
• Each pointer is an edge in the graph.
• Root nodes are locations not in the heap that contain pointers into the heap (e.g., registers, locations on the stack, global variables).

Reachable memory includes all nodes that can be reached by following pointers starting from the root nodes. All memory that is not reachable from the roots is considered garbage and can be safely reclaimed.

Assumptions for Garbage Collection

The garbage collector relies on three key instructions/functions:

1. is_ptr(p): Determines whether a value p is a valid pointer (as opposed to data like an integer or float).
2. length(b): Returns the length of block b, not including the header (to know where pointers might be located within the block).
3. get_roots(): Returns all root nodes (registers, stack locations, global variables) that contain potential pointers into the heap.

⭐ Key Takeaways

The critical concepts from this lecture are: (1) Explicit free lists improve allocation speed by traversing only free blocks rather than all blocks, using either LIFO or address-ordered insertion policies; (2) Segregated free lists organize blocks by size class to further accelerate allocation and reduce fragmentation; (3) Real programs exhibit patterns (ramps, peaks, plateaus) that can be exploited — arena allocators leverage peak phases by using pointer increment allocation and batch-free operations; (4) Garbage collection automates memory reclamation by treating memory as a directed graph and reclaiming unreachable nodes, but relies on strict assumptions about pointer identification and structure; (5) Reference counting is simple but fails with circular data structures, motivating more sophisticated tracing collectors.

🧠 Quick Revision Questions

1. What are the four cases when freeing a block using LIFO policy, and how are they determined?
2. What is the key advantage of explicit free lists over implicit free lists, and what is the cost?
3. What is the difference between simple segregated storage and segregated fits, and what tradeoff does each make?
4. How does an arena allocator exploit peak-phase allocation patterns, and what are its three advantages?
5. Why does reference counting fail to reclaim circular data structures, and what assumption about pointers is essential for garbage collection to work correctly?

📘 Lecture 22 — Mark and Sweep Collecting

📖 Overview: This lecture covers a range of advanced operating system concepts, starting with memory management via the Mark and Sweep garbage collection algorithm. It then transitions into foundational OS topics including processes, address spaces, exceptions, process lifecycle (fork, exit, exec), synchronization primitives (semaphores, condition variables), deadlock conditions, thread usage paradigms, and basic scheduling with FCFS.

🗂️ Topics Covered

The lecture begins with Mark and Sweep garbage collection using depth-first traversal and length-based sweeping. It then defines an operating system from top-down and bottom-up views, covering time and space multiplexing. It lists types of operating systems and OS structures (monolithic, layered, micro-kernel). The ELF object file format is described with its header, program header table, and sections (.text, .data, .bss). Strong and weak symbols and linker rules are explained, along with static library creation. The lecture then moves to process definition, private address spaces, exceptions (asynchronous and synchronous), process creation, Unix SVR4 processes, Process Control Block (PCB), fork and exit system calls, zombies, exec, safe/unsafe trajectories, semaphores (for mutual exclusion and scheduling), condition variables, reentrant functions, deadlock definition and four necessary conditions, thread usage paradigms, and finally FCFS scheduling.

📝 Lecture Summary

Mark and Sweep Collecting

This section introduces garbage collection through the Mark and Sweep algorithm. It uses a depth-first traversal of the memory graph to mark all reachable objects, then sweeps through memory using lengths to find the next block of free or reclaimable memory. The algorithm identifies live objects by traversing from root references and collects dead objects by scanning the heap linearly.

🔑 Definition — Mark and Sweep: A garbage collection algorithm that first marks all reachable objects via graph traversal (often depth-first) and then sweeps through memory to reclaim unmarked objects, using block lengths to navigate.

What is an operating system?

An operating system is described from two perspectives. The top-down view focuses on the interface and services provided to applications (e.g., resource abstraction). The bottom-up view focuses on managing hardware resources. Two key multiplexing strategies are used: time multiplexing (sharing CPU over time) and space multiplexing (sharing memory or storage concurrently).

🔑 Definition — Time multiplexing: A resource sharing technique where the resource (like CPU) is allocated to different processes in time slices. Space multiplexing: A technique where the resource (like memory) is divided and allocated to multiple processes simultaneously.

Type of Operating Systems

Several categories of operating systems are listed: Main frame operating systems (e.g., IBM z/OS), Time-sharing systems (e.g., Unix), Multiprocessor operating systems (managing multiple CPUs), PC operating systems (e.g., Windows, Linux desktop), Real-time operating systems (guaranteeing timing constraints), and Embedded operating systems (for devices like phones, IoT).

OS Structure

Three OS architectures are presented:

• Monolithic Design: The entire OS runs in kernel space as a single large program, with all services tightly integrated.
• Layering: The OS is organized into hierarchical layers, where each layer provides services to the layer above and uses services from below.
• Micro-kernel: The kernel is minimal, providing only essential services (e.g., IPC, basic scheduling), while other services (e.g., file systems) run in user space.

ELF Object File Format

The Executable and Linkable Format (ELF) is described with its components: the Elf header (contains metadata like architecture, entry point), the Program header table (describes segments for loading), and three main sections: .text section (executable code), .data section (initialized global/static data), and .bss section (uninitialized global/static data, allocated at runtime).

🔑 Definition — ELF: A standard file format for executables, object code, shared libraries, and core dumps, consisting of a header, program header table, and sections.

Strong and Weak Symbols

Program symbols are classified as either strong or weak. A strong symbol is typically a function or initialized global variable. A weak symbol is one declared without initialization or with special attributes (e.g., __attribute__((weak)) in GCC).

Linker’s Symbol Rules

Three rules govern symbol resolution:

• Rule 1: A strong symbol can only appear once across all linked object files.
• Rule 2: A weak symbol can be overridden by a strong symbol of the same name.
• Rule 3: If there are multiple weak symbols, the linker can pick an arbitrary one.

📐 Formula/Rule: Rule 1: Strong → unique. Rule 2: Strong overrides weak. Rule 3: Multiple weak → any chosen.

Creating Static Libraries

This section describes the process of bundling multiple object files into a static library (e.g., .a file on Unix) using tools like ar, allowing programs to link against the library at compile time.

The Complete Picture

[This section heading appears but contains no substantive text beyond the heading itself in the provided lecture text. No summary is possible.]

Process

A process is defined as "a unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system instructions." It is the fundamental unit of work in an operating system.

Private Address Spaces

Each process is given its own private address space, meaning memory addresses used by one process do not refer to the same physical memory as those of another process. This provides isolation and protection between processes.

Asynchronous Exceptions (Interrupts)

These exceptions are caused by events external to the processor, such as I/O device completion, timer expiration, or hardware signals. They occur independently of the currently executing instruction.

Synchronous Exceptions

These exceptions are caused by the execution of an instruction itself. Three types are listed:

• Traps: Intentional exceptions (e.g., system calls).
• Faults: Potentially recoverable errors (e.g., page faults).
• Aborts: Unrecoverable errors (e.g., hardware failure).

Process Creation

The steps for creating a new process are:

1. Assign a unique process identifier (PID).
2. Allocate space for the process (memory for code, data, stack).
3. Initialize process control block (PCB) with state and metadata.

Unix SVR4 Processes

[This section heading appears but contains no substantive text beyond the heading in the provided lecture text. No summary is possible.]

Process Control Block

The Process Control Block (PCB) is a data structure maintained by the OS for each process, containing key information:

• Process state: e.g., running, ready, waiting, halted.
• Priority: Used for scheduling decisions.
• Scheduling-related information: e.g., CPU burst times, wait times.
• Event: The event the process is waiting for (if blocked).

fork: Creating new processes

The fork() system call creates a new process. The child process is an almost exact copy of the parent. The function call is: int fork(void). It returns 0 to the child, the child’s PID to the parent, or -1 on failure.

📌 Example: A parent process calls fork(). After the call, two processes (parent and child) exist, both executing the next instruction after fork. The parent sees the child’s PID as the return value; the child sees 0.

exit: Destroying Process

The exit() system call terminates the calling process. The call is: void exit(int status). The status value is passed to the parent process (via wait()). The process becomes a zombie until reaped.

Zombies

• Idea: A zombie is a process that has exited (via exit()) but whose exit status has not yet been read (reaped) by its parent. The process’s PCB is retained.
• Reaping: The parent uses wait() or waitpid() to obtain the child’s exit status, after which the OS can fully deallocate the PCB. If the parent exits first, the orphaned process is adopted by init (PID 1), which reaps it.

exec: Running new programs

The exec() family of system calls replaces the current process’s memory image with a new program. The call is: int execl(char *path, char *arg0, char *arg1, ..., 0). It loads the program at path and passes the arguments. If successful, it never returns; on failure, it returns -1.

Safe and Unsafe Trajectories

[This section heading appears but contains no substantive text beyond the heading in the provided lecture text. No summary is possible. In context, safe/unsafe trajectories relate to deadlock avoidance, where a safe trajectory avoids deadlock states.]

Semaphores

A semaphore is a synchronization primitive that is higher level than locks. It was invented by Dijkstra in 1968 as part of the THE operating system. A semaphore is an integer variable accessed through two atomic operations: P() (wait) and V() (signal).

Two uses of semaphores are identified:

• Mutual exclusion: Ensuring only one thread accesses a critical section at a time (binary semaphore).
• Scheduling constraints: Coordinating the order of execution (e.g., thread A must complete before thread B starts, using a counting semaphore).

🔑 Definition — Semaphore: A synchronization primitive with a counter, supporting atomic wait() (decrement, block if zero) and signal() (increment, wake a blocked thread if any).

Condition variables

A condition variable is a queue of threads waiting for something to happen inside a critical section. It provides three operations:

• Wait(): Release the lock, go to sleep, and re-acquire the lock when woken.
• Signal(): Wake up one waiter, if any.
• Broadcast(): Wake up all waiters.

Condition variables are always used with a mutex lock to protect the shared state being checked.

🔑 Definition — Condition variable: A synchronization primitive that allows threads to wait for a specific condition to become true within a critical section, releasing the lock while sleeping.

Reentrant Functions

[This section heading appears but contains no substantive text beyond the heading in the provided lecture text. No summary is possible. A reentrant function is one that can be safely called again before a previous invocation has completed, typically by not relying on static global data.]

Formal definition of a deadlock

A deadlock is formally defined: "A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause." This means processes hold some resources while waiting for others held by each other, creating a cycle.

Conditions for deadlock

All four conditions must hold simultaneously for a deadlock to occur:

1. Mutual exclusion: Resources cannot be shared; only one process can use a resource at a time.
2. No preemption: Resources cannot be forcibly taken away from a process; only the holder can release voluntarily.
3. Hold and wait: A process holds at least one resource while waiting to acquire additional resources.
4. Circular wait: A cycle exists in the resource allocation graph, where each process in the cycle waits for a resource held by the next.

📐 Formula (Rule): Without all four conditions, deadlock cannot occur.

Paradigms of thread usage (from Hauser et al paper)

This section lists several common patterns for using threads:

• Defer work: Offload work from a critical path.
• General pumps: Threads that continuously process items from a queue.
• Slack processes: Threads that run when idle, doing background work.
• Sleepers: Threads that sleep until a specific time or event.
• One-shots: Threads that perform a single task and then terminate.
• Deadlock avoidance: Threads designed to prevent deadlock via ordering.
• Rejuvenation: Periodic restart to avoid accumulating errors.
• Serializers: Threads that handle sequential access to shared resources.
• Encapsulated fork: Forking a thread to isolate risky code.
• Exploiting parallelism: Using multiple threads to speed up computation on multiple cores.

Scheduling: First come first served (FCFS or FIFO)

This is the simplest scheduling algorithm: Run jobs in the order that they arrive. It uses a FIFO queue. It is non-preemptive; once a job starts, it runs to completion or until it blocks.

📌 Example: Three processes arrive at time 0, 2, 4 with burst times of 5, 3, 1. FCFS schedules them in arrival order: P1 (0-5), P2 (5-8), P3 (8-9). Average waiting time = (0+3+4)/3 = 2.33 time units.

⭐ Key Takeaways

The Mark and Sweep algorithm uses depth-first traversal to mark live objects and linear sweeping to reclaim memory. Processes are isolated via private address spaces, and exceptions are classified as asynchronous (interrupts) or synchronous (traps, faults, aborts). Fork creates a copy of the process, exit terminates it (creating a zombie until reaped), and exec loads a new program. Semaphores enable both mutual exclusion and scheduling constraints, while deadlock requires all four conditions: mutual exclusion, no preemption, hold and wait, and circular wait. FCFS scheduling is simple but can cause long average waiting times (convoy effect).

🧠 Quick Revision Questions

1. Explain the two main phases of the Mark and Sweep garbage collection algorithm. How does depth-first traversal work during the mark phase?
2. What are the four conditions that must all hold for a deadlock to occur? Give a real-world example showing each condition.
3. Describe the difference between fork() and exec() system calls. What happens to the process’s address space in each case?
4. How does a semaphore differ from a condition variable? Provide one use case for each.
5. Why can a strong symbol appear only once across linked object files, but multiple weak symbols are allowed? What rule does this relate to in the linker?