Operating Systems (ELL783)

Course Outline and General Information (PDF)

Course Outline

Link to course outline

General Information

No one shall be permitted to audit the course. People are welcome to sit through it, however. The course is open to all suitably inclined M.Tech, M.S.(R) and Ph.D. students of all disciplines. This course is not open to B.Tech and Dual Degree students. Those who do not fulfil the above criteria, and are found enrolled after the completion of the add-drop period will be forcibly removed from the course.

Credits: 4 (LTP: 3-0-2) [Slot A]

Schedule for Classes:

Monday
08:00 - 09:30
IIA-101 (Bharti Building)
Thursday
08:00 - 09:30
IIA-101 (Bharti Building)

Schedule for Examinations:

Minor I: 03 February 2020 (Monday) 04:00 pm - 05:00 pm, LH-408
{Minor II+Major}: 27 August 2020 (Thursday) 10:00 am - 12:00 noon, scanned scripts to be sent in by 12:15 pm.

Teaching Assistant(s):

Books, Papers and other Documentation

Textbook:

Reference Books:

[Internal Link: IIT Delhi]

The above list is (obviously!) not exhaustive. Other reference material will be announced in the class. The Web has a vast storehouse of tutorial material on Operating Systems, and other related areas.

Lecture Schedule, Links to Material (where applicable)

Please see the link to the II Sem (Spring) 2018-2019 offering of this course, for an idea of the approximate structure of the course.
S.No.
Topics
Lectures
Instructor
References/Notes
0
Introduction
01-01
SDR
The design of a bare-bones OS: a glorified interrupt service routine on a timer interrupt. How to design an OS for a simple microprocessor. Instruction set design, interaction with a von Neumann-type architecture. ROM and RAM. Programs and processes. Instruction and data, types of data. How a computer boots up.
30 Dec (Mon) {lecture#01}
SDR
1
The Process Concept
01-04
SDR
[SGG: Chap.3]
The process concept. The Process Control Block.
30 Dec (Mon) {lecture#01}
SDR
A small sample example for creating processes.
02 Jan (Thu) {lecture#02}
SDR
A small sample example for creating processes (contd). Introduction to two basic actions for a process, the fork and exec family of instructions. Discussion on absolute addresses (and the need for them), and logical addresses.
06 Jan (Mon) {lecture#03}
SDR
Discussion on linux's clone() system call to treat processes and threads alike, and the copy-on-write poilcy.
Discussion on returning more than one parameter, and why is a subroutine also known as a function.
Discussion on `name-mangling' of functions (polymorphism of functions in an OOPS invironment), and having a variable number of parameters.
09 Jan (Thu) {lecture#04}
SDR
2
Threads
04-06
SDR
[SGG: Chap.4]
Introduction to threads. Efficient context-switching, sharing code, data and file pointers.
09 Jan (Thu) {lecture#04}
SDR
Introduction to threads. The hardware perspective and motivation. A programming example. Linux treats threads and processes alike, with different parameters to the same clone() system call.
13 Jan (Mon) {lecture#05}
SDR
Introduction to threads (contd). Shared memory and processes. Assignment 2: Inter-process communication.
16 Jan (Thu) {lecture#06}
SDR
3
CPU Scheduling
07-15
SDR
[SGG: Chap.5]
CPU Scheduling: basic performance criteria, basic scheduling algorithms. The Earlier Linux Scheduler (two queues).
20 Jan (Mon) {lecture#07}
SDR
[Early start: 07:30am] (to make up for the 22 Feb (Sat) scheduled class to be missed)
Thread Scheduling, Multi-Core Processor Scheduling (software: OS, hardware: logical processor). Introduction to hardware logical processor scheduling.
23 Jan (Thu) {lecture#08}
SDR
[Early start: 07:30am] (to make up for the 22 Feb (Sat) scheduled class to be missed)
The processor's scheduling, for each logical processor. Intel's Itanium Dual Core hardware scheduler with 8 priority levels.
Real-Time Scheduling. Hard and Soft Real Time. Physical constraints. Rate-Monotonic Scheduling. Earliest-Deadline First (EDF) Scheduling.
27 Jan (Mon) {lecture#09}
SDR
[Early start: 07:30am] (to make up for the 22 Feb (Sat) scheduled class to be missed)
Linux's Scheduler: Real-Time and Ordinary job scheduling (CFS: Completely Fair Scheduler, the work of Ingo Molnar, based on the work of Con Kolivas).
30 Jan (Thu) {lecture#10}
SDR
---
Minor I
03 Feb (Mon) - 06 Feb (Thu)
---
---
The basic problem of atomicity for a producer-consumer problem.
Basic structure of a synchronisation problem, three basic points.
10 Feb (Mon) {lecture#11}
SDR
Peterson's solution: two process pure software solution.
Synchronisation hardware: the TestAndSet instruction.
An example of an n- process synchronisation problem with TestAndSet.
13 Feb (Thu) {lecture#12}
SDR
An example of an n- process synchronisation problem with TestAndSet (contd.)
The de facto standard for synchronisation primitives: semaphores and mutexes. Definitions. Issues in atomicity on a single core single processor system.
17 Feb (Mon) {lecture#13}
SDR
An alternate representation for semaphores which permits negative integer values and interfaces with the CPU scheduler. The producer-consumer problem.
20 Feb (Thu) {lecture#14}
SDR
--- No class ---
22 Feb (Sat) {lecture#xx}
---
The Readers and Writers problem, Dining Philosophers problem.
Sequentialisation/Serialisation through Semaphores.
24 Feb (Mon) {lecture#15}
SDR
4
Deadlocks
16-xx
SDR
[SGG: Chap.7]
Introduction to Deadlocks: Necessary conditions. Graph representation.
27 Feb (Thu) {lecture#16}
SDR
Resource Allocation Graph (RAG) contd. Introduction to 4 main issues with deadlocks: Deadlock Prevention, Deadlock Avoidance, Deadlock Detection, Deadlock Recovery. Introduction to Deadlock Prevention, and why this is Draconian.
02 Mar (Mon) {lecture#17}
SDR
Deadlock Avoidance: The Banker's Algorithm. The first subroutine of Banker's Algorithm for Deadlock Avoidance: the safety algorithm.
05 Mar (Thu) {lecture#18}
SDR
Deadlock Avoidance: The Banker's Algorithm (contd).
09 Mar (Mon) {lecture#19}
SDR
---
Minor II (postponed)
15 Mar (Sun) - 18 Mar (Wed)
---
---
4. Deadlocks
Deadlock Avoidance (contd): The second subroutine of Banker's Algorithm for Deadlock Avoidance: the resource request algorithm (which in turn, uses the safety algorithm). Illustrations of Banker's Algorithm for Deadlock Avoidance.
Deadlock Detection: Banker's Algorithm for Deadlock Detection.
Deadlock Recovery: Deadlock Recovery Techniques. What do OSs do in cases of deadlocks?
[Study plan for Lockdown period]
SDR
Deadlock Avoidance [SGG: Sections 7.5.1 Safe State, 7.5.2 Resource-Allocation-Graph Algorithm, 7.5.3 Banker's Algorithm (all sub-sections)]
Deadlock Detection [SGG: Section 7.6 Deadlock Detection (all sub-sections)]
Deadlock Recovery [SGG: Section 7.7 Recovery from Deadlock (all sub-sections)]

The textbook's slides web page has a link to all slides in the PPT and PDF formats.
5. Virtual Memory
Virtual Memory and Caches: Similarities and Differences. Review of cache organisations (Direct-Mapped, Fully Associative, Set-Associative). The Write-back policy for cache writes. Why is Write-Through not feasible for Virtual Memory?
Paging: Introduction to Virtual Memory with a simple paging example. Basic concepts. Prominent features of paging. Large page tables.
Segmentation: Basic Concepts. Hybrid strategies in Paging and Segmentation.
Miscellaneous Concepts: Background: Protection, Address Binding, Logical-versus-Physical Address Space, Dynamic Loading, Dyniamic Linking and Shared Libraries. Swapping. Contiguous Memory Allocation: Fragmentation.
Page Replacement: Introduction. Demand Paging. Copy-on-Write. Page Replacement: Introduction. Thrashing. Common page replacement algorithms: FIFO and Belady's Anomaly, Optimal Page Replacement, LRU Page Replacement, LRU Approximations. Others: Frequency-based Page Replacement, LRU Approximations, Kernel Memory Allocation.
[Study plan for Lockdown period]
SDR
Caches: [Please read this from a Computer Architecture textbook such as the one by Hennessy and Patterson, or please read the relevant topics mentioned here, from the Internet. You can also refer to some lecture notes, which the instructor will send over email. Please pick only the relevant parts from either the lecture notes, or the book, or the Internet, as mentioned here!]
Paging: [For an introduction, please refer to some lecture notes, which the instructor will send out over email.]
[SGG: One may skim through the material in Sections 8.5.1 Basic Paging, 8.5.3 Protection and 8.5.4 Shared Pages.] [Large Page Tables: SGG: Section 8.6 Structure of the Page Table. Instead of Section 8.6.1 Hierarchical Paging, please refer to the lecture notes which the instructor will send out over email. SGG: Sections 8.6.2 Hashed Page Tables and 8.6.3 Inverted Page Tables: basic concepts.
Segmentation: [SGG: Section 8.4 Segmentation: basic concepts]
Miscellaneous Concepts: [SGG: Sections 8.1 Background, 8.2 Swapping, 8.3 Contiguous Memory Allocation]
Page Replacement: [SGG: Sections 9.1 (skim through), 9.2 Demand Paging: 9.2.1 Basic Concepts, 9.3 Copy-on-Write, 9.4 Page Replacement, 9.6 Thrashing, 9.6.1 Cause of Thrashing, 9.8 Allocating Kernel Memory]

The textbook's slides web page has a link to all slides in the PPT and PDF formats.
6. Storage Management
File Systems: Organisation, Data Structures, Allocation.
Implementing File-Systems: Free Space Management, Performance, Opening, Closing, Partitions, Mounting. Unified Buffer Cache, Log structure file systems.
Mass-Storage Structure: Secondary structure devices and bus protocols (EIDE, ATA, SATA, USB, FC, SCSI), Disk Structures, Disk Scheduling, Formatting, Boot blocks, bad blocks, RAID.
[Study plan for Lockdown period]
SDR
File Systems: [SGG: Sections 10.1 File Concept, 10.2 Access Methods, 10.3 Directory and Disk Structure, 10.4 File-System Mounting, 10.5 File Sharing, 10.6 Protection]
Implementing File-Systems: [SGG: Sections 11.1 File-System Structure, 11.2 File-System Implementation, 11.3 Directory Implementation, 11.4 Allocation Methods, 11.5 Free-Space Management, 11.6 Efficiency and Performance, 11.7 Recovery, 11.8 NFS, 11.9 Example: The WAFL File System]
Mass-Storage Structure: [SGG: Sections 12.1 Overview of Mass-Storage Structure, 12.2 Disk Structure, 12.3 Disk Attachment, 12.4 Disk Scheduling, 12.5 Disk Management, 12.6 Swap-Space Management, 12.7 RAID Structure]

The textbook's slides web page has a link to all slides in the PPT and PDF formats.
7. Stochastic Modelling for Operating Systems

Measures of performance evaluation. The A/B/n model for client-server systems: an introduction. M/M/1 systems. The Poisson Distribution for the arrival process. The Exponential Distribution for the service time distribution. Steady State situation, Little's Law.
[Study plan for Lockdown period]
SDR
Stochastic Modelling: [Please read this from a Queueing Theory reference, or please read the relevant topics mentioned here, from the Internet. You can also refer to some lecture notes, which the instructor will send over email. Please pick only the relevant parts from either the lecture notes, or the book, or the Internet, as mentioned here!]
Stochastic modelling: A probability primer. Certainty and probability. When is a Binomial distribution apt for modelling phenomena? The mean and variance of a Binomial distribution. The special case when p -> 0 and n -> infinity: The Poisson Distribution. The mean and variance of the Poisson Distribution.
18 Aug (Tue) {lecture#xx}
SDR
Lecture notes: [Internal link: IITD only]
Stochastic Modelling: Modelling the Arrival Process. Starting from first principles, reasonable assumptions, derivation of the fact that the arrival process naturally comes out to be Poisson. Similarly, the service time distribution naturally comes out to be exponential. Answering the first two of five important problems in M/M/1 queueing theory.
20 Aug (Thu) {lecture#xx}
SDR
Lecture notes: [Internal link: IITD only]
Answering three practical questions associated with M/M/1 queueing theory: the probability that more than k buffers will be required, the average queue length and the average waiting time in the system.
24 Aug (Mon) {lecture#xx}
SDR
Lecture notes: [Internal link: IITD only]

Assignments

... A combination of theoretical work as well as programming work.
Both will be scrutinized in detail for original work and thoroughness.
For programming assignments, there will be credit for good coding.
Sphagetti coding will be penalized.
Program correctness or good programming alone will not fetch you full credit ... also required are results of extensive experimentation with varying various program parameters, and explaining the results thus obtained.
Assignments will have to be submitted on or before the due date and time.
Late submissions will not be considered at all.
Unfair means will be result in assigning as marks, the number said to have been discovered by the ancient Indians, to both parties (un)concerned.
Assignment 1
Assignment 2
Assignment 3
Assignment 4

Examinations and Grading Information

The marks distribution is as follows (out of a total of 100):
Minor I
25
Minor II
25
Assignments
25
Major
25
Grand Total
100

ELL783 Evaluation: Programming Assignment Groups, Assignment/Examination-related Information [Internal Link: IIT Delhi]

ELL783 Grades (Anonymised)

Attendance Requirements:

As per Institute rules for IIT Delhi students: a minimum of 75% attendance (i.e., a maximum of 7 absents permitted), else one grade less
Illness policy: illness to be certified by a registered medical practitioner
Attendance in Examinations is Compulsory.

ELL783 Attendance Records (on the moodle page)

Course Feedback

Link to Course Feedback Form
Sumantra Dutta Roy, Department of Electrical Engineering, IIT Delhi, Hauz Khas,
New Delhi - 110 016, INDIA. sumantra@ee.iitd.ac.in