Operating Systems

Course: ELL 783 and ELL 405
Semester II, 2022-23
Credits: 4 (3-0-2)



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
.


Teaching Assistants:

1. Shruti Pandey
2. Nivedita Shrivastava
3. Akanksha Dixit

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

Lectures and Slides:

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