Operating Systems: A Kernel-Oriented Perspective

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 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.

• For each assignment, there will be an easy and hard version. The latter will be based on the Linux kernel. The student
  can choose to do either one. Note that assignments may be associated with a viva that will check the student's understanding;
  if she does not do well in her viva, then she will get low marks regardless of the assignment that was submitted.
  
• Assignments (easy track): They will be based on xv6. The first assignment will be a solo assignment and the rest two
  will be done in groups.
• Assignments (hard track): All three will be solo assignments and will be graded quite seriously. They will have a bonus
  component associated with them. They will give the student, serious experience with the Linux kernel.
• If a student finishes all three assignments in the hard track, then she can carry the bonus marks (max: 12.5) to her course total.
  However, the caveat is that the bonus marks cannot be used to pass the student if she is otherwise failing. The bonus
  marks can thus help increase her grade.
• Please don't send any individual mails. For those who miss a minor or an assignment, we will hold an extra minor and issue an
  extra assignment towards the end of the course. Please note that to ensure a level playing field, this will be much harder than the
  original minor/assignment, respectively. The assignment needs to be done individually. No medical certificates need to be provided.
  

Teaching Assistants:

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

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

Homeworks/Lab Assignments:

Lectures and Slides:

Date	Lecture	Topics	Details
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	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	[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