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 Mon Tue Wed Thu Fri Other
1
02 Jan
LEC 1: Introduction
Resource management, high-level services.
03 Jan
LEC 2: Introduction
Protection and isolation, why study OS?
05 Jan
LEC 3: x86 ISA
General registers, eip, eflags, assembly.
2
09 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.
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 walkthrough. Quiz 3.
02 Feb
LEC 15: FS
Optimizations, crash consistency via ordering.
Labs
Lab 1 due. Lab 2 out.
6
06 Feb
LEC 16: FS
fsck, write-ahead logging.
07 Feb
LEC 17: FS
Metadata journaling, xv6 walkthrough. Quiz 4.
09 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. Quiz 5.
Labs
Lab 2 due.
8
20 Feb
Break
21 Feb
Break
23 Feb
Break
Lab
Lab 3 out.
9
27 Feb
Minor Exam
28 Feb
Minor Exam
01 Mar
Mid-term Project Evaluation
10
04 Mar
Moved
Moved to 9 Mar 6:30–7:30pm.
05 Mar
LEC 22
Minor exam review.
06 Mar
LEC 23: Processes
TSS, kernel stack, IO protection.
08 Mar
Maha Shivratri
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.
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
14
01 Apr
Project
Project out.
02 Apr
LEC 31: Paging
Thrashing, KSM, paging in xv6. Quiz 6
03 Apr
LEC 32: Paging
xv6 setting up initial page tables. Quiz 7
05 Apr
LEC 33: Paging
Setting up process page tables, fork semantics
Lab 4 due.
15
09 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
Reminor Exam on 14 Apr
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
LEC-39 cancelled.
LEC40 and LEC41 will be 1.5 hours each, Project Due
17
23 Apr
LEC 40: OS Organization
Deadlocks, locking discipline, Microkernel, exokernel. Quiz 9
24 Apr
LEC 41: Virtualization
Trap-and-emulate, unikernels.
LEC 42 cancelled
LEC28 & LEC29 will be 1.5 hrs.
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