Operating Systems: A Kernel-Oriented Perspective

Course: COL 331 and COL 633
Semester II, 2022-23
Credits: 5 (3-0-4)

Instructor: Prof. Smruti R. Sarangi

Hall of fame:

All these students completed all three Linux kernel based assignments successfully. They created
their own IPC mechanisms, system calls, real-time process schedulers and wrote a device driver.
They are fully "kernel trained", and can write large non-trivial portions of kernel code on their own.
They are listed in alphabetical order. They worked on the latest Linux kernel (version 6).

Abhishek Safui Akarsh Jain
Aniruddha Deb Divyamsingh Solanki
Divyansh Mittal Harihar S
Kushal Gupta Pranay Shah
Ramanuj Goel Rishabh Dhiman
Rohit Kumar Sachit Sachdeva
Somaditya Singh Tanish Tuteja
Vaibhav Mishra  

Abhishek Safui and Ramanuj Goel went a step forward and
implemented some changes in the kernel that are extremely
difficult to do. One such example is adding a new scheduler
class in the kernel (version 6.1).

Lectures: 10-11 AM (Tue, Wed, Fri), LH 108

Piazza link:    Link

Office Hours: Just send me an e-mail.

Evaluation Criteria: Minor 1 and 2 (15% each), Major: 30%, Three assignments (10% + 15% + 15%)
Passing criteria: 18% in theory and 12% in the assignments (both the criteria need to be met)
Audit criteria: 24% in theory and 16% in the assignments (again both the criteria need to be met)
For those who miss a minor, there will be an extra minor towards the end of the course, which will be much harder.
There will be no assignment deadline extensions unless there is a serious personal reason or a medical reason

Teaching Assistants:

1. Dipen Kumar
2. Nikita Bhamu
3. Yashashwee Chakraborty
4. Harshit Verma
5. Abhisek Panda
6. Rahul Kanyal
7. Rohith V.


Reference Books
[Textbook] Understanding the Linux Kernel: From I/O Ports to Process Management, Third Edition, Bovet and Cesati

Slides Link
Basics of Computer Architecture
System calls, Interrupts and Signals
Scheduling and Synchronization
Memory Systems
I/O Systems, Device Drivers and Virtualization

Homeworks/Lab Assignments:

  Easy Hard
A1 Link Link
A2 Link Link
A3 Link Link

Lectures and Slides:

January 6th 1 Introduction to the course What is an OS? [slides [Introduction]]
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
[slides [Architecture fundamentals]]
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 [slides [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 [slides [Communication with Processes]]

February 4th 13 Synchronization: Concepts, locks, and semaphores Locks and semaphores. [slides [Synchronization and Scheduling]]
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

Proof of the optimality of EDF

[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

[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 [Slides: 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, [Slides: I/O Systems]

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