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.

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

Schedule for Classes:

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

Schedule for Examinations:

Minor I: 06 February 2018 (Tuesday) 01:00 pm - 02:00 pm, LH-512
Minor II: 26 March 2018 (Monday) 01:00 pm - 02:00 pm, LH-512
Major: 05 May 2018 (Saturday) 10:30 am - 12:30 pm, LH-517

Teaching Assistant(s):

Akash Nayak
Hemant Goyal

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)

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.
04 Jan (Thu) {lecture#01}
SDR
1
The Process Concept
02-05
SDR
[SGG: Chap.3]
The process concept. The Process Control Block. A small sample example for creating processes.
08 Jan (Mon) {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. Linux's copy-on-write policy, and the clone() system call. A fork bomb. Assignment 1: implementation of a simple shell, using the above theory.
11 Jan (Thu) {lecture#03}
SDR
2
Threads
04-05
SDR
[SGG: Chap.4]
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 (Sat) {lecture#04}
SDR
Introduction to threads (contd). Shared memory and processes. Assignment 2: Inter-process communication.
15 Jan (Mon) {lecture#05}
SDR
3
CPU Scheduling
06-11
SDR
[SGG: Chap.5]
CPU Scheduling: basic performance criteria, basic scheduling algorithms
18 Jan (Thu) {lecture#06}
SDR
Multiple-Processor Scheduling, The Earlier Linux Scheduler (two queues)
25 Jan (Thu) {lecture#07}
SDR
Thread Scheduling, Multi-Core Processor Scheduling (software: OS, hardware: logical processor)
29 Jan (Mon) {lecture#08}
SDR
Real-Time Scheduling
01 Feb (Thu) {lecture#09}
SDR
---
Minor I
06 Feb (Tue)
---
---
Real-Time Scheduling
12 Feb (Mon) {lecture#10}
SDR
4
Synchronisation
11-15
SDR
[SGG: Chap.6]
The basic problem of atomicity for a producer-consumer problem
15 Feb (Thu) {lecture#11}
SDR
--- No class ---
19 Feb (Mon) {lecture#xx}
SDR
The general structure of a critical section problem
Peterson's solution: two process pure software solution
22 Feb (Thu) {lecture#12}
SDR
Synchronisation hardware: the TestAndSet instruction.
Issues in atomicity on a single core single processor system.
05 Mar (Mon) {lecture#13}
SDR
An alternate representation for semaphores which permits negative integer values and interfaces with the CPU scheduler.
The producer-consumer problem
08 Mar (Thu) {lecture#14}
SDR
The Readers and Writers problem, Dining Philosophers problem. Introduction to Deadlocks: Necessary conditions. Graph representation.
10 Mar (Sat) {lecture#15}
SDR
4
Deadlocks
15-19
SDR
[SGG: Chap.7]
--- Make-up class in lieu of 19 Feb, 15 Mar classes ---

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. Deadlock Avoidance: The Banker's Algorithm. The first subroutine of Banker's Algorithm for Deadlock Avoidance: the safety algorithm.
11 Mar (Sun) {lectures#16,#17}
SDR
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.
12 Mar (Mon) {lecture#18}
SDR
--- No class ---
15 Mar (Thu) {lecture#xx}
SDR
Banker's Algorithm for Deadlock Detection.
Deadlock Recovery. What do OSs do in cases of deadlocks?
Introduction to Virtual Memory
19 Mar (Mon) {lecture#19}
SDR
5
Virtual Memory
19-24
SDR
[SGG: Chap.8, 9]
Paging: simple example, basic concepts. Prominent features of paging.
22 Mar (Thu) {lecture#20}
SDR
---
Minor II
06 Feb (Tue)
---
---
Paging: (contd). Large page tables. Segmentation. Comparison with Caches.
02 Apr (Mon) {lecture#21}
SDR
Paging: (contd). Large page tables. Protection. Dynamic Loading and Linking.
05 Apr (Mon) {lecture#22}
SDR
09 Apr (Mon) {lecture#23}
SDR
Frequency-based Page Replacement, LRU Approximations, Kernel Memory Allocation
12 Apr (Thu) {lecture#24}
SDR
5
Storage Management
25-xx
SDR
[SGG: Chap.10, 11, 12, 13]
File Systems: Organisation, Data Structures, Allocation
16 Apr (Mon) {lecture#25}
SDR
Free Space Management, Performance, Opening, Closing, Partitions, Mounting
19 Apr (Thu) {lecture#26}
SDR
23 Apr (Mon) {lecture#27}
SDR
26 Apr (Thu) {lecture#28}
SDR
30 Apr (Mon) {lecture#29}
SDR
---
Major
05 May (Sat)
---
---

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]

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) (04.01.2018-01.02.2018; 12.02.2018-22.03.2018)


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