2023-2024 Sem II

This course introduces the design and implementation of operating systems. In particular, we will slowly build the xv6 OS from scratch. Students should feel comfortable with hacking through an OS after having done this course.

Course Information

  • Prerequisites: COL106 and COP290.

    Note: The course includes programming assignments and thus expects proficiency with systems programming and debugging.

  • Credits: 3-0-4
  • Slot: K, Tuesday 5-6pm, Wednesday 12-1pm, Friday 5-6pm
  • Lecture hall: LH111
  • TAs:
    • Abhisek Panda: csz202445 AT cse.iitd.ac.in
    • Rohith Vishnumolakala: csy227589 AT cse.iitd.ac.in
    • Satyam Jay: anz238224 AT iitd.ac.in
    • Saurabh Verma: cs5190129 AT cse.iitd.ac.in
    • Ritesh Srivastava: jcs222656 AT csia.iitd.ac.in
    • Yashashwee Chakrabarty: mcs222057 AT cse.iitd.ac.in
    • Prateek Bhaisora: jcs232564 AT csia.iitd.ac.in
  • Reading material:

Grading criteria

  • 30% labs (programming assignments)
  • 20% project
  • 10% quizzes
  • 20% minor exam
  • 20% major exam
  • Upto 5% errata participation (bonus, optional)

Labs

  • Lab 1: mouse driver (5%), disk scheduling (1%)
  • Lab 2: crash consistency (5%), fsck (1%)
  • Lab 3: system call and scheduling (5%), valgrind (1%)
  • Lab 4: page replacement (12%)
  • Project: CoW fork along with page replacement (12% implementation + 5% viva and report + 3% project exam)

Policies

  • Ethics: Please re-read IITD honour code. Cheating will get an F in the course. Why should I not cheat?
  • Late policy: To help you cope with unexpected emergencies, you can hand in your labs solutions late. The total amount of lateness summed over all the lab deadlines must not exceed 72 hours. You can divide up your 72 hours among the labs however you like; you don’t have to ask or tell us. You can only use late hours for labs. There will be no makeup labs and no late time extensions.
  • Quizzes: Quizzes will be surprise. There will be no make up quizzes. We will count the scores from your best (n-1) quizzes where n is the total number of quizzes.
  • Audit criteria: 60% or more marks in total. 60% or more marks in major+minor exams. Attempted 75% of quizzes.
  • Errata participation: You can send pull requests to remove dead code, fix bugs and other grammatical mistakes, to receive upto 5% of bonus marks. These marks can only be used to improve grades D and above i.e, they cannot be used to move from grade F to grade D and they cannot be used to move from grade NF to NP.
  • Discussions should be done exclusively on Piazza. Please don’t send individual mails.
  • Makeup minor exam: For those who miss the minor exam, we will hold an extra minor towards the end of the course. Reminor will be much harder than the original minor exam.

Tentative topics

We will build an OS from scratch. We will learn topics as and when we add them to our OS. The topics will tentatively be covered in the following order:

  • Booting: Bootloader, ELF format
  • Input-output: Programmable interrupt controllers, traps, interrupt descriptor table
  • File system: FS layout, buffer cache layer, name layer, crash consistency, devices as files
  • Processes: memory segmentation, rings, process table, context switching, scheduling, system calls, exec system call
  • Memory virtualization: memory hierarchy, address translation mechanism, demand paging, page replacement, thrashing, fork system call
  • Concurrency and parallelism: data races, different types of locks
  • Shell: pipes, IO redirection

Whenever we implement something, we will also study some alternate implementations. Following topics will be covered without seeing their implementations.

  • Beyond OS: virtualization, shadow paging
  • Glimpse into OS research: power management, unikernels, persistent memory, transparent huge pages, disaggregated OS

Disclaimer: Actual course contents may differ.

Schedule

Week Tuesday Wednesday Friday Other
1 2 Jan
LEC 1: Introduction.
Resource management, high-level services.		 3 Jan
LEC 2: Introduction.
Protection and isolation, why study OS?		 5 Jan
LEC 3: x86 ISA.
general registers, eip, eflags, assembly.		  
2 9 Jan
LEC 4: x86 ISA.
esp, ebp, gcc calling convention, objdump.		 10 Jan
LEC 5: x86 ISA.
PIO, MMIO, volatile keyword.		 12 Jan
LEC 6: Booting.
BIOS, bootloader, 16-bit mode, segments. Quiz 1.		  
3 16 Jan
LEC 7: Booting.
ELF file format, segmented and flat memory models.		 17 Jan
LEC 8: Booting.
Code walkthrough.		 19 Jan
LEC 9: IO.
Polling, interrupts, DMA, PICs, IDT.		 20 Jan
LEC 10: IO.
Interrupt handling code walkthrough. Quiz 2. Lab 1 out.
4 23 Jan
LEC 11: IO.
HDDs, disk scheduling.		 24 Jan
LEC 12: IO.
RAID, buffer cache code walkthrough.		 26 Jan
Republic day		  
5 30 Jan
LEC 13: FS.
Abstractions, FAT filesystem		 31 Jan
LEC 14: FS. Indexed filesystem. xv6 code walkthrough. Quiz 3.		 2 Feb
LEC 15: FS. Optimizations, crash consistency via ordering.		 3 Feb
Lab 1 due. Lab 2 out.
6 6 Feb
LEC 16: FS.
fsck. Write-ahead logging.		 7 Feb
LEC 17: FS.
Metadata journaling, xv6 code walkthrough. Quiz 4.		 9 Feb
LEC 18: Cancelled. LEC19 and LEC21 will be 1.5 hr each.		  
7 13 Feb
LEC 19: Processes.
Address space: heap, stack. Memory APIs and bugs.		 14 Feb
LEC 20: Processes.
Memory allocator, free list		 16 Feb
LEC 21: Processes.
Slab, buddy allocators. Memory isolation. Protection levels. Quiz 5		 17 Feb
Lab 2 due.
8 20 Feb
break		 21 Feb
break		 23 Feb
break		 24 Feb
Lab 3 out.
9 27 Feb
Minor exam		 28 Feb
Minor exam		 1 Mar
Mid-term project evaluation		 4 Mar
Moved to 9 Mar 6:30-7:30pm.
10 5 Mar
LEC 22: Minor exam review.		 6 Mar
LEC 23: Processes
TSS, kernel stack, IO protection		 8 Mar
Maha Shivratri		 9 Mar
LEC 24: Processes
System calls, safe user parameter handling
11 12 Mar
LEC 25: Processes
Context switching		 13 Mar
LEC 26: Processes
Scheduling policies		 15 Mar
LEC 27: Processes IO aware scheduling, concurrency		 16 Mar
Lab 3 due. Lab 4 out.
12 19 Mar
LEC 28: Paging
Flexibility, multi-level page tables, PTEs, PDEs, TLBs, temporal and spatial locality		 20 Mar
LEC 29: Paging
TLB reach, working set, large pages, tagged TLB, swapping mechanism		 22 Mar
LEC 30: Paging
Page replacement policies		  
13 26 Mar
Semester break		 27 Mar
Semester break		 29 Mar
Good Friday		 1 Apr
Project out
14 2 Apr
LEC 31: Paging
Thrashing, KSM, paging in xv6. Quiz 6		 3 Apr
LEC 32: Paging
xv6 setting up initial page tables. Quiz 7		 5 Apr
LEC 33: Paging
Setting up process page tables, fork semantics		 6 Apr
Lab 4 due.
15 9 Apr
LEC 34: Shell
Fork copy-on-write, exec, wait, kill, init process, dup, IO redirection, pipes		 10 Apr
LEC 35: Parallelism
Starting other CPUs in xv6, user and kernel threads, races, bad spin lock designs		 12 Apr
LEC 36: Parallelism
Safety, liveness, Peterson algorithm, sequential consitency, x86 TSO memory model. Quiz 8		 14 Apr
Reminor exam
16 16 Apr
LEC 37: Parallelism
Fences, LOCK instructions, compiler barriers, xv6 spin locks, fair locks, condition variables, hybrid locks		 17 Apr
Ram Navami		 19 Apr
LEC 38: Parallelism
Semaphores, read-write locks		 20 Apr
Project due. LEC 39: Cancelled LEC40 and LEC41 will be 1.5 hours each
17 23 Apr
LEC 40: OS organization
Deadlocks, locking discipline, Microkernel, exokernel. Quiz 9		 24 Apr
LEC 41: Virtualization
Trap-and-emulate, unikernels		   27 Apr
LEC 42: Cancelled LEC28 and LEC29 will be 1.5 hr each
Encouraging student comments after the course
I am -----, a final year undergrad student, one of the few who took the COL331 course this semester apart from CS dept. My experience for the course was absolutely amazing, for past all 8 semesters I have tried out everything, ML, theoretical CS, CP, etc but still I was looking out for something which sparks my interest so much that I could work tirelessly towards it. And finally this course gave me that, low level systems programming, and it was all possible because of the way you taught the course, the frequent code walkthrough, especially the idea of reading in branches, helped a lot in understanding. The slides containing extracts from the actual x86-intel manual showed how much research and thought had been put into it, which I absolutely enjoyed referring to.

The lectures were interesting, especially the animation, which made understanding of the code much easier. I also liked the semaphores lecture in which we were making the locks. The exams were of the correct level of difficulty, as they seemed doable, but were interesting and challenging nonetheless. The TAs in this course were very helpful. I thank all of them for taking so many office hours and helping us with our problems in the code.

Exams