Operating Systems

Instructor: Prof. Smruti R. Sarangi

Lectures: 11 AM to 12 PM (Tue, Thu, Fri), LH 316

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:

Date	Lecture	Topics	Link to the Video
Jan 6th	1	Introduction to the course	What is an OS? [slides [Introduction]]
Jan 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 [Architectural Fundamentals of OSes]]
Jan 12th	3		1. x86 assembly 2. Compilation and linking
Jan 13th	4		1. Static and dynamic linking Links: link1, link2, link3 [very detailed]
Jan 17th	5	Virtual memory and segmentation
Jan 19th	6	Virtual memory, I/O, DMA Process management	I/O instructions Introduction to processes [slides [Processes]]
Jan 20th	7	Processes	task_struct structure, thread_info
Jan 24th	8		Process states, the kernel stack, the current macro
Jan 31st	9		CPU local state, the current pointer, process priorities, sched_info, mm_struct and the Maple tree
Feb 1st	10		Link to the video Radix tree, pid_t process number, pid structure, namespaces, Van Emde Boas tree, I/O fields and ptracing,
Feb 2nd	11		fork, clone, and execve. The copy_process function
Feb 3rd	12		Context switches, switching to user and kernel processes.
Feb 4th	13	Synchronization	Locks and semaphores. [Slides: Synchronization and scheduling]
Feb 10th	14	Minor-I paper discussion, interrupts	Minor-I paper discussion. The Interrupt Descriptor Table. Library calls: the flow of printf The write system call's flow: syscall to ksys_write [Slides: Communication with Processes]
Feb 14th	15	Interrupt handling	signal handler, LAPIC and I/O APIC link
Feb 16th	16		Detailed design of the LAPIC and APIC, interrupt domains, kernel-based data structures. IRQ handling routines.
Feb 17th	17		Linked lists in the kernel, soft IRQs, threaded IRQs, work queues
Feb 21st	18	Exception and signal handling	Exception handlers, Basic signal handling, kernel code
Feb 23rd	19	Signal handling and concurrency	Entering and exiting signal handlers. Pthreads, locks, and lock-free programs (atomics) [Slides: Synchronization and scheduling]
Feb 28th	20	Synchronization mechanisms	1. Basic definitions 2. Semaphores 3. Mutexes 4. Bounded queues
2nd March	21		5. Reader writer locks Sequential consistency and linearizability Atomic variables and volatile ints Barriers and phasers
3rd March	22		Memory consistency, spinlocks, 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]
10th March	23	Introduction to Scheduling	Youtube video
14th March	24	Synchronization and RCU	Kernel-level semaphores, Basics of the RCU mechanism
16th March	25	RCU details, Scheduling	RCU and overview of scheduling
17th March	26		Banker's algorithm. Basic scheduling code in Linux.
20th March	27		Scheduling code on Linux. CFS, RT, and Deadline scheduling.
Minor 2
28th March	28	Minor 2 questions and scheduling	1. Minor 2 question paper discussion 2. Discussion on RT and deadline scheduling
29th March	29	Real-Time Scheduling	EDF, RMS, and DMS Scheduling
31st March	30		PIP, HLP, and PCP protocols
1st April	31	Memory Systems	Code for the buffer overflow attack: link Code reuse attack: link Stuxnet worm: link Basic notions of the free list, stack distance, optimal, and LRU replacement algorithms.
6th April	32		Stack-based algorithms, Belady's anomaly, Thrashing, PGD design
Extra Class 1	33	I/O Systems: Introduction	I/O protocols, [Slides: I/O Systems] Youtube Video
Extra Class 2	34		Storage devices Youtube video
11th April	35	Memory Systems [Slides: Memory Systems]	struct page, struct folio, TLB accesses
13th April	36		Lazy TLB accesses, zones, MG-LRU structures
14th April	37	Memory Systems: Page replacement, aging and eviction	MG-LRU replacement, PI controller, Bloom filters, reverse mapping, lru_gen_look_around, Aging and eviction, thrashing
	38
16th April	39	Kernel memory allocation	Youtube Video Slab, Slub, and Buddy memory allocation
25th April	40	Device Drivers and File Systems	Block device drivers
27th April	41		File Systems
28th April	42	Virtual machines	VMs: Para-virtualization, Type 0, Type 1, Type 2