Operating Systems

Course: COL331, COL633 and ELL405
Semester II, 2017-18
Credits: 5 (3-0-4)

Instructor: Prof. Smruti R. Sarangi

: Tuesday, Wednesday and Friday: 10 AM to 11 AM, LHC 318, Piazza link (code: col331col633)

Course Load: Minor 1, Minor 2, End term, 3 programming assignments

Evaluation: 18% (Minor 1), 18% (Minor 2), 24% (Major), Assignments (12% + 12% + 16%)
Passing Criteria: At least 12/40 in assignments AND at least 18/60 in theory

Policy for late assignments and re-minor:
1. We will hold one re-minor for people who have missed one minor at the end of the major exam. Note that
to ensure a level playing field, it will be significantly harder than the original minor exams. The student needs
to show documentary evidence such as a medical certificate to the TA on the day of the reminor. Please don't
send any mails to the instructor or the TAs regarding this.

2. Every homework will have a 3-day buffer period. (-15%) penalty per day.

3. Audit Criteria: 50% in theory, and 50% in the labs

Teaching Assistants:

Sandeep Kumar <anz178353@cse.iitd.ac.in>
Shubhankar Suman Singh <csz168113@cse.iitd.ac.in>
Ismi Abidi <csz158373@cse.iitd.ac.in>
Shaili Durgesh Shah <mcs162667@cse.iitd.ac.in>
Rajat Gupta <mcs162673@cse.iitd.ac.in>
Saurabh  Sharma <mcs162679@cse.iitd.ac.in>

Mansi Garg <Mansi.Garg.eet17@ee.iitd.ac.in>

Palakh Shangle <eet172292@ee.iitd.ac.in>

Abhishek Rose <csz178584@cse.iitd.ac.in>

Reference Books
[Textbook]  Operating Systems Concepts (Ninth Edition) by Abraham Silberschatz, Peter B. Galvin, Gerg Gagne
                   Link to slides.

Lectures and Slides:

January 3rd
Introduction and Course Policies

January 5th
Structure of an executable, linking -- static and dynamic
ELF format, DLLs in Linux
January 9th
Computer architecture review -- caches and pipelining
Link to slides and videos
OS as a Service Provider
January 10th
Life cycle of a system call -- broad concepts
Linux assembly tutorial
January 12th
1. Passing arguments to function calls -- via registers, via stack
2. Process control block (states)
3. Memory map of a process: text, data, stack, heap
4. Life cycle of a process. States: init, ready, waiting, running, terminated
5. Types of unanticipated events: hardware interrupts, exceptions, and system calls
6. System call and interrupt tables
7. Methods to send interrupts to the processor: internal queueing (till the
right time approaches), and the APIC (programmable interrupt controller)
8. Multitasking with different processes
1. Slides for chapter 2 and 3 from the book
2. Link to the task_struct data structure
in the Linux kernel
3. More about processes --> link
4. Wikipedia article on APICs --> link
OS as a Process Manager
January 16th
1. Life cycle of a process
2. Notion of the timer chip, and multitasking, jiffy in Linux
3. Idea of virtual memory: size problem and overlap problem
4. Scheduler, process queues (ready, job, and I/O), process creation and termination
5. fork and exec system calls
[Activity] Write a program with fork and exec calls. Analyse its behaviour.
1. Link to slides on virtual memory
2. fork and exec calls: link
3. Link to the kernel code
January 17th
1. Page tables: single level and multi-level
2. Spatial and temporal locality
3. TLBs
4. Swap space
5. Shared memory based IPC
[Activity] Write a program with shared memory based IPC.
1. Link to slides on virtual memory
2. Shared memory based IPC (Link)
January 19th
1. Shared memory
Advantages: very flexible
Disadvantages: challenges in synchronization, synchronization and data formats
2. Pipes -- named and unnamed (parent <-> child)
Advantages: easy to use, synchronous, OS maintains the queue (accessed with system calls)
3. Sockets -- Can be used to send messages across the internet. The local OS
maintains all the queues (accessible via system calls)
[Activity] Write a program that uses pipes and sockets
Slides from the book
1. Link to code with pipes
2. Link to code with sockets
January 23rd
1. Remote procedure calls -- stubs, skeletons, marshalling, unmarshalling
2. Threads -- spawning, scheduling, and destroying
[Activity] Write a program that uses RPC calls
Slides from Chapter 4
1. Link: tutorial on RPC
2. Link: tutorial on Java RMI
January 24th
More about threads
1. Threads as light-weight processes
2. Sharing the data and heap sections between threads
3. pthread library: create, join, exit
4. OpenMP library (self study)
5. Thread local storage
6. Scheduling processes and threads -- notion of single and multiple ready queues
[Activity] Write a program that adds a large set of numbers using multiple threads
Slides from Chapter 4
1. Tutorial on pthreads (link)
2. Tutorial on OpenMP (link)
January 30th
1. Notion of a critical section
2. Atomic regions
3. Locking and unlocking
1. Slides from the book
January 31st
1. Peterson's lock (algorithm + proof)
2. Atomic operations, mutexes, critical sections
3. Concurrency primitives: Compare and set, swap, fetch-and-increment, test-and-set
[Activity] 1. Implement a Peterson lock in Java (use volatile variables, see link)
                2. Write parallel programs with GCC intrinsics, and java.util.concurrent
1. Locks and CAS (link)
2. Slides from the book

Feb 2nd
1. Semaphores (counting and binary)
2. Conditions for a deadlock --> mutual exclusion, hold and wait, non pre-emptability, and circular wait
3. Deadlock avoidance
4. Dining philosopher's problem
     4.1. Basic Dijkstra's algorithm (based on odd-even numbering)
     4.2. Chandy Misra algorithm
1. Semaphores in Linux (link)
2. Solutions to the dining philosopher's problem with algorithms(link)
3. Solution to the dining philosopher's
    problem with semaphores (link)
Feb 9th
1. Minor 1 solutions
2. Chandy Misra algorithm

Feb 13th
1. Scheduling in CPUs -- Unicore and Multi-core
2. Shortest job first --> minimum average waiting time
3. Tradeoffs of different scheduling policies: round-robin, FCFS
4. Different heuristics for scheduling: maximize throughput, minimize waiting time, minimize response time
5. Bin packing, NP completeness, and their relation to multiprocessor scheduling
1. Link to the code of the Linux scheduler
Feb 17th
(2 classes)
1. Different algorithms for scheduling in uniprocessors and multi-processors.
2. Real time systems -- EDF and RMA algorithms
3. Foreground and background processors
4. Schedule and dispatch latencies
5. Deadlock avoidance, prevention, detection, and recovery
6. Ordered lock algorithm
7. Banker's algorithm
1. Link to Banker's algorithm
Feb 20th
1. Banker's algorithm
2. Buffer overflow attack (stack smashing attack)
1. Code for stack smashing (link)
2. Reference on stack smashing (link)
OS as a Memory Manager
Feb 21st
1. Buffer overflows and stack protection
2. Dynamic linked libraries
3. Page faults and traps
4. FIFO page replacement algorithm.
5. Belady's anomaly
[Activity] 1. Demonstrate a buffer overflow attack using inputs from the command line.
1. Slide set 8 is not there in the syllabus.
Feb 23rd
1. Optimal page replacement algorithm
2. LFU and MFU algorithms
3. Notion of performance in real systems, and methods to develop scheduling and page replacement algorithms for them.
4. Thrashing
[Activity] Formally prove that the optimal algorithm is indeed optimal.

March 6th
1. Buddy and Slab allocation
2. The memory mapping problem -- malloc, kernel data structure allocation in physical memory, systems without virtual memory
1. Slab allocation (link)
OS as a Storage Manager
March 7th
1. Overview of the I/O System
2. Linux read and write calls
3. NRZI encoding
4. Structure of a hard disk
5. Seek time, rotational latency, and transfer time.
1. Link to slides (link)
2. Link to video (link), Chapter 12
 March 9th
2. Solid state drives

March 13th
1. Optical drives: CD, DVD, Blu-ray discs
2. Constant angular velocity vs constant linear velocity
3. Disk scheduling algorithms -- FCFS, SSTF, SCAN, C-SCAN, C-Look
1. YouTube link (slow motion operation of a hard disk)
2. HDD vs SSD (link)
March 14th
1. Master boot records, swap spaces and partitions
2. Notion of file systems
3. File locking -- shared and exclusive
4. Types of devices -- block and character
5. Devices: character, block. /dev directory, and /dev/null
6. proc file system. (/proc/cpuinfo /proc/meminfo)
7. home, usr, var, etc, bin

March 16th
1. Directory Structure
2. Network file systems: NFS, CIFS
3. Mount points, symbolic links
4. File sharing
5. UNIX permissions

March 18th
(2 classes)
1. File system introduction
2. Boot block, super block
3. Difference between contents of a directory and contents of a file
4. Structure of a directory entry (in multiple disk blocks)
5. Structure of a file control block -- owner, permissions, layout on the disk
6. Contiguous, linked-list, and extent-based allocation on the disk
7. FAT file system
8. Concept of inodes