| 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> |
| Date |
Lecture |
References |
| January 3rd |
Introduction and Course Policies |
|
| Background | ||
| 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 packages |
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 |
1. RAID 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 |
|
| Apr 3 |
1. Minor 2 Solutions 2. Revision of FAT and inode file systems |
|
| Apr 4 |
1. Bit vectors vs optimized bit vectors vs
linked lists (for managing free lists) 2. Block cache and page cache 3. Synchronous vs asynchronous writes 4. Log based file systems. Transactional writes. 5. Snapshots 6. NFS (stateful vs stateless servers) |
1. NFS tutorial (link) 2. Log structured file system (link) |
| OS
as an I/O Manager |
||
| Apr 6 |
1. I/O system design 2. I/O system stack (network and protocol layers) 3. I/O mapped I/O (I/O ports and addressing) 4. Memory mapped I/O 5. Interrupts, polling, and DMA |
1. Additional slides: link |
| OS
as a Security Provider |
||
| Apr 10 |
[Guest Lecture
by Prof. Ragesh Jaiswal] Cryptography Primitives |
1. Slides: link |
| Apr 13 |
[Guest Lecture
by Prof. Subodh Sharma] |
1. Slides: link |
| Apr 17 |
1. Access control matrix 2. Access control list 3. Capability matrix 4. Encryption and access permissions in Linux and Windows |
|
| Apr 18 |
1. Viruses and worms 2. Trojan horses, trapdoors, and keyloggers 3. Buffer overflow attacks 4. Phishing, and social engineering 5. Methods to prevent buffer overflows. 6. Logic bomb, denial of service 7. Ethical issues concerning security |
1. Stuxnet Links: article,
video 2. 10 worst viruses of all time: link |
| Apr 20 |
1. Power analysis and EM attacks 2. nmap and port scanning 3. Virtual Machines overview 4. Type 0, 1, and 2 hypervisors 5. Advantages of hypervisors: security, mobility 6. Technical challenges: system calls, interrupts, and paging |
|
| Virtual Machines |
||
| Apr 24 |
1. Type 0, 1, and 2 hypervisors 2. Advantages of virtual machines 3. Trap and emulate method 4. Handling system calls, interrupts, and privileged instructions in VMs |
|
| Apr 25 |
1. Binary translation and para-virtualization 2. Type 2 Hypervisors 3. Shadow and nested page tables 4. JVMs and application level hypervisors 5. Resource allocation in virtual machines 6. VM migration 7. Containers 8. Storage virtualization |
|
| Self Study |
Last two chapters on the internals of Linux
and Windows 7. |
|