Operating Systems: A Linux Kernel-Oriented Perspective

Smruti R. Sarangi

(The full version of the book is to be released in mid 2024)

Creative Commons CC-BY-ND 4.0  license  


Slides Link
Introduction
Basics of Computer Architecture
Processes
System calls, Interrupts and Signals
Scheduling and Synchronization
Memory Systems
The I/O Systems, Storage Devices and Device Drivers
Security and Virtualization

Homeworks/Lab Assignments:

  Easy Hard
A1 Link Link
A2 Link Link
A3 Link Link

Guide to Linux kernel hacking by Abhishek Safui.

Lectures and Slides:

Date
Lecture
Topics
Details
January 6th 1 Introduction to the course What is an OS?
January 10th 2 Overview of the computer architecture needed for an OS course 1. Context switches
2. Privileged and non-privileged instructions
3. Rings
4. The timer chip
5. Interrupts and system calls
January 11th 3 1. x86 assembly
2. Linking and loading
January 13th 4 1. Static and dynamic linking
Links: link1, link2, link3 [very detailed]
January 17th 5 Virtual memory and segmentation  
January 18th 6 Virtual memory, I/O, DMA
Process management
I/O instructions
Introduction to processes
January 20th 7 Processes task_struct structure, thread_info, process state
January 24th 8 The current macro (stack address and segmentation based), process priorities, mm_struct, Maple tree, Anonymous and non-anonymous VM areas.
January 25th 9 pids, namespaces, pid structure, radix trees, and bitmaps
January 31st 10 Radix and Van Emde Boas trees, I/O and ptrace fields; fork, clone, and execve
February 1st 11 Processes: Task Switching The copy process function, capturing the hardware context, types of context switches, returning back to the user program,
February 3rd 12 Context Switches and Library Calls

Context switches, switching to user and kernel processes.
Library calls: the flow of printf
The write system call's flow: syscall to ksys_write

February 4th 13 Synchronization: Concepts, locks, and semaphores Locks and semaphores.
February 10th 14 Minor-I paper discussion Discussion of the Minor-I paper, Signal handling (with an example)
February 14th 15 Interrupt handling and signals IRQs, LAPIC, I/O APIC, IRQ domains, the irq_desc data structure link
February 15th 16 Interrupt handling flow, Soft IRQs, Threaded IRQs
February 17th 17 Work queues, linked lists, and signal handlers
February 21st 18 Signal handling and concurrency Kernel code for signal handlers and signal context switches, atomic primitives, pthreads
February 22nd 19 Lock-free and wait-free programming

1. Basic definitions
2. Semaphores
3. Mutexes
4. Bounded queues

February 28th 20 Atomics, non-blocking programs, and memory models 5. Reader writer locks
Obstruction freedom, lock freedom, and wait freedom
Barriers and Phasers
Basic memory consistency concepts
Reference on memory models: Advanced Computer Architecture
1st March 21 Spin locks and Mutexes Additional reference: pointer to the paper on ticket locks and MCS locks
[Paper] Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors
John M. Mellor-Crummey, Michael L. Scott, ACM TOCS, 1991 [link]
3rd March 22 Lockdep and RCUs The lockdep mechanism and RCUs
All the references are embedded in the slides.
10th March 23 Introduction to Scheduling Youtube video
14th March 24 RCU mechanisms and scheduling (introduction and priority-based)
15th March 25 Banker's algorithm, introduction to the Linux scheduler code
17th March 26 sched_entity, rq, and the CFS scheduler
21st March 27 Real Time Systems

EDF
Proof of the optimality of EDF

RMS
[Paper] Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Liu and Layland, Journal of the ACM, 1973

[Paper] The Rate Monotonic Scheduling Algorithm: Event Characterization and Average Case Behavior, Lehoczky, Sha, and Ding. IEEE Real Time Systems Symposium, 1989

DMS
[Paper] Deadline Monotonic Scheduling, Audsley, 1990
22nd March 28 EDF (utilization bound <= 1), PIP, HLP, and PCP protocols
Minor 2
25th March 29 Introduction to Memory Systems  
28th March 30 Minor 2 discussion

1. Discussion of the Minor 2 question paper
2. Introduction to memory systems: systems without virtual memory
3. Internal and external fragmentation
4. The notion of stack distance

31st March 31 Memory Systems 1. LRU and clock-based page replacement
2. Belady's anomaly
3. Thrashing
1st April 32

Code for the buffer overflow attack: link
Code reuse attack: link
Stuxnet worm: link

Linux page directory and page access

5th April 33 Pages and folios, zones, mem_section structures, TLB ASIC/PCID
Extra Class 1 34 I/O Systems: Introduction

I/O Protocols

Youtube Video

Extra Class 2 35

Storage devices
Youtube video

11th April 36 Memory Systems Partitions of physical memory, basic page replacement.
12th April 37 MG-LRU page replacement algorithm, Bloom filters, PI controller for page replacement
14th April 38 Reverse mapping, lru_gen_look_around, thrashing
16th April 39 Youtube Video Slab, Slub, and Buddy allocation
25th April 40 I/O and File Systems Block device drivers
26th April 41 File systems
28th April 42 Virtual Machines VMs: Para-virtualization, Type 0, Type 1, Type 2