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-101 (Bharti Building)
Thursday
08:00 - 09:30
IIA-101 (Bharti Building)

Schedule for Examinations:

Minor I: 06 February 2018 (Wednesday) 01:00 pm - 02:00 pm, LH-416
Minor II: 27 March 2018 (Wednesday) 01:00 pm - 02:00 pm, LH-416
Major: 30 April 2019 (Sunday) 01:00 pm - 03:00 pm, LH-408

Teaching Assistant(s):

Sakshi Agrawal
Hareesh Kumawat

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) 2017-2018 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.
31 Dec (Mon) {lecture#01}
SDR
1
The Process Concept
02-03
SDR
[SGG: Chap.3]
How a computer boots up (contd). ``A time-sharing multiprogramming OS is a glorified interrupt service routine on the timer interrupt.'' The process concept. The Process Control Block.
03 Jan (Thu) {lecture#02}
SDR
{Early start: 7:30am-9:30am class}
--- No class ---
07 Jan (Mon) {lecture#xx}
SDR
--- No class ---
10 Jan (Thu) {lecture#xx}
SDR
A small sample example for creating processes. 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.
17 Jan (Thu) {lecture#03}
SDR
{Early start: 7:30am-9:30am class}
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.
21 Jan (Mon) {lecture#04}
SDR
{Early start: 7:30am-9:30am class}
Introduction to threads (contd). Shared memory and processes. Assignment 2: Inter-process communication.
24 Jan (Thu) {lecture#05}
SDR
{Early start: 7:30am-9:30am class}
--- No class ---
28 Jan (Mon) {lecture#xx}
SDR
3
CPU Scheduling
06-09
SDR
[SGG: Chap.5]
CPU Scheduling: basic performance criteria, basic scheduling algorithms Assignment 3: Basic Scheduling Algorithms.
31 Jan (Thu) {lecture#06}
SDR
{Early start: 7:30am-9:30am class}
---
Minor I
06 Feb (Wed), LH-416, 1pm-2pm
---
---
Multiple-Processor Scheduling, The Earlier Linux Scheduler (two queues). OS schedulers for multi-processors. Hardware schedulers for multi-processor machines, typically multi-core CPUs. Thread Scheduling, Multi-Core Processor Scheduling (software: OS, hardware: logical processor)
11 Feb (Mon) {lecture#07}
SDR
{Early start: 7:30am-9:30am class}
Real-Time Scheduling: Rate Monotinic Scheduling, Earliest Deadline First
14 Feb (Thu) {lecture#08}
SDR
{Early start: 7:30am-9:30am class}
The current Linux Scheduler: CFS, the Completely Fair Scheduler
18 Feb (Mon) {lecture#09}
SDR
{Early start: 7:30am-9:30am class}
4
Synchronisation
09-12
SDR
[SGG: Chap.6]
The basic problem of atomicity for a producer-consumer problem
18 Feb (Mon) {lecture#09} (contd)
SDR
{Early start: 7:30am-9:30am class}
The general structure of a critical section problem. The three important points with regard to any solution: mutula exclusion, progress, bounded wait.
Peterson's solution: two process pure software solution.
Synchronisation hardware: the TestAndSet instruction.
An example of a n- process critical section problem with the TestAndSet instruction.
21 Feb (Thu) {lecture#10}
SDR
{Early start: 7:30am-9:30am class}
--- No class ---
23 Feb (Sat) {lecture#xx}
---
An example of a n- process critical section problem with the TestAndSet instruction (contd). Illustration of a bounded wait.
Semaphores and Mutexes.
Issues in atomicity on a single core single processor system.
An alternate representation for semaphores which permits negative integer values and interfaces with the CPU scheduler.
25 Feb (Mon) {lecture#11}
SDR
{Early start: 7:30am-9:30am class}
An alternate representation for semaphores which permits negative integer values and interfaces with the CPU scheduler (contd.)
The Producer-Consumer Problem. The Readers and Writers problem. The Dining Philosophers problem.
28 Feb (Thu) {lecture#12}
SDR
{Early start: 7:30am-9:30am class}
4
Deadlocks
13-16
SDR
[SGG: Chap.7]
Introduction to Deadlocks: Necessary conditions. Graph representation. Resource Allocation Graphs (RAG). Deadlock Prevention, Deadlock Avoidance, Deadlock Detection, Deadlock Recovery: An Introduction. Dijkstra: Banker's Algorithm for Deadlock Avoidance: An Introduction.
11 Mar (Mon) {lecture#13}
SDR
{Early start: 7:30am-9:30am class}
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.
14 Mar (Thu) {lecture#14}
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.
16 Mar (Sat) {lecture#15}
SDR
Banker's Algorithm for Deadlock Detection.
Deadlock Recovery. What do OSs do in cases of deadlocks?
Introduction to Virtual Memory
18 Mar (Mon) {lecture#16}
SDR
---
Minor II
27 Mar (Wed), LH-416, 1pm-2pm
---
---
5
Virtual Memory
16-24
SDR
[SGG: Chap.8, 9]
Introduction to Virtual Memory: The memory hierarchy. Caches and Virtual Memory. Paging and Segmentation: an introduction.
01 Apr (Mon) {lecture#17}
SDR
Paging: simple example, basic concepts. Prominent features of paging.
04 Apr (Thu) {lecture#18}
SDR
Paging: (contd). Large page tables. Segmentation. Comparison with Caches.
08 Apr (Mon) {lecture#19}
SDR
Paging: (contd). Large page tables. Protection. Dynamic Loading and Linking.
11 Apr (Thu) {lecture#20}
SDR
Frequency-based Page Replacement, LRU Approximations, Kernel Memory Allocation
15 Apr (Mon) {lecture#21}
SDR
5
Storage Management
25-xx
SDR
[SGG: Chap.10, 11, 12, 13]
File Systems: Organisation, Data Structures, Allocation
18 Apr (Thu) {lecture#22}
SDR
Free Space Management, Performance, Opening, Closing, Partitions, Mounting
22 Apr (Mon) {lecture#23}
SDR
Unified Buffer Cache, Log structure file systems, Secondary structure devices and bus protocols (EIDE, ATA, SATA, USB, FC, SCSI), Disk Structures
25 Apr (Thu) {lecture#24}
SDR
Disk Scheduling, Formatting, Boot blocks, bad blocks, RAID
xx xxx (xxx) {lecture#xx}
SDR
xx xxx (xxx) {lecture#xx}
SDR
xx xxx (xxx) {lecture#xx}
SDR
xx xxx (xxx) {lecture#xx}
SDR
xx xxx (xxx) {lecture#xx}
SDR
---
Major
30 Apr (Sun), LH-408, 1pm-3pm
---
---

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)


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