Course Description

This course is a deep dive into systems and kernel programming. We will start with the basic concepts of shell, assembler, linkers and loaders, and end with a detailed discussion of how the Linux kernel works in practice. There will be additional tutorials to get students familiar with systems programming.

Prerequisites

Please note that while these concepts would be introduced in the refresher module and/or tutorials, but it would be easier for students who are comfortable with these concepts.

  • Familiarity with basics of Bash shell: You may either learn from the Bash Guide or use this book by Sumitabha Das.
  • Basics of programming in C language: Any book on C programming is sufficient. Concepts of pointers and dynamic memory allocation would be discussed in the class, so understanding of these concepts is not assumed.
  • Version control using git: You need to ensure that the code is properly tracked, as a large part of the learning would happen through trial and error. You need to be familiar with the basics of git as discussed here. Familiarity with advanced git would help you better manage code, but is not strictly necessary.
  • Utilizing makefiles to build programs: You need to understand how to use makefile to build programs. You can follow this basic tutorial to get familiar with it.
  • Debugging using gdb: Many of the programs are likely to be complex, and might require the use of a debugger. Any IDE-based debugger is fine, but you might want to be familiar with the basics of gdb, which is discussed in Appendix of Seyfarth.

For most of the course, you will need access to a Linux Virtual Machine (VM). A tutorial about creating and using Linux VM’s would be given in the refresher module.

Reference Books

  • Ray Seyfarth, Introduction to 64 Bit Assembly Language Programming for Linux and OS X (abbreviated as Seyfarth)
  • Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (available here, abbreviated as OSTEP)
  • Michael Kerrisk, The Linux Programming Interface: A Linux and UNIX System Programming Handbook (abbreviated as Kerrisk)
  • Robert Love, Linux Kernel Development (abbreviated as Love)

Weightage of Points

  • Assignments – 50
  • Midterms – 20
  • Final Examination – 30

Course Content

The overall structure of the course is described in the table. Please note that this is a rough structure and the structure might be modified depending on the feedback of students. We plan to provide 1-2 programming questions in each class that would be used to reinforce the concepts. While these are not graded, answering these questions would help students to handle the assignments.

Class Number Content References Exercises
1 Introduction to the class, basic concepts of OS, linker, loader, assembler, concept of instruction set architecture, x86-64 architecture and its backward compatibility, the first program in x86-64 assembly Seyfarth Chapter 1 Building assembly
2 Register naming in x86-64 machines, addressing modes, arithmetic and bitwise operations, concept of Program Status Word, conditional jumps and loops Seyfarth Chapters 5, 6, 8 Loop in assembly
3 Defining variables, constants and arrays in assembly, x86-64 calling convention, floating point arithmetic, concept of stack and heap, calling C library functions Seyfarth Chapter 9-11 Calling printf, Output using write
4 Calling assembly functions, structures in assembly and memory alignment Seyfarth Chapters 9, 13  
5 Embedding assembly in C Reference Link  
6 Abstractions in Linux, introduction to Process Management, process switching and context switching, interrupts, states of processes OSTEP Chapter 4, 6 Using fork
7 Fork and exec system calls and its variants, concepts of orphan, zombie and reaper processes OSTEP Chapter 5 + Kerrisk Chapter 2  
8 Concept of thread, user-level and kernel-level threads, differences between parallelism and concurrency OSTEP Chapter 26-27 + M11 reference  
9 Process scheduling concepts OSTEP Chapter 7  
10 Details of Linux process scheduling Love Chapter 4  
11 Internals of the Linux kernel, kernel memory primitives, organization of Linux system calls Love Chapters 5-6  
12 Linux kernel data structures and system calls Love Chapters 5-6  
13 Concept of interprocess communication and synchronization, types of primitives available, pipes and FIFOs Kerrisk Chapters 43-44  
14 Message Queues, shared memory and shared memory Kerrisk Chapters 52, 54  
15 Sockets and File Locks Kerrisk 55-57  
16 Interprocess synchronization, critical section problem, spin lock, test-and-set lock OSTEP Chapters 28, 29  
17 Producer-consumer and bounded buffer problems, semaphores and their implementation, monitors OSTEP Chapter 31, Appendix  
18 Memory Management of OS, concept of address space, problem of fragmentation, paging-based solutions OSTEP Chapters 13, 15, 18  
19 Hierarchical and inverted page tables, page replacement policies, additional exercises on paging OSTEP Chapter 20  
20 Segmentation and swapping, memory organization in Linux OSTEP Chapters 16, 23  
21 Discussion of bootup mechanisms Additional Reading Material  
22 Introduction to device management, block and character I/O OSTEP Chapter 36  
23 Working of hard disk and SSDs, I/O scheduler OSTEP Chapters 37, 44, Love Chapter 14  
24 Concept of file system and their organization OSTEP Chapters 39, 42, 43  
25 Virtual file system, internal organization in Linux Love Chapter 13  
26 Interrupt handling, top half and bottom half, tasklets, work queues and soft IRQs Love Chapters 7-8