Operating Systems (211) (09/10)

Lecturer: Dr Peter Pietzuch
Email: prp@doc (you know the rest)
Office: Huxley 442

Format: 2 hours of lectures + 1 tutorial per week (weeks 2 - 10)
Location: Lecture LT 145 (Tue 11am-12pm) + Lecture LT 308 (Thurs 9am-10am) + Tutorial 344 (Thurs 10am-11am)

The first half of the Operating Systems course looks at I/O devices, disk management, file systems, memory management and security issues. (The second half of the course is taught by Dr Cristian Cadar.)

Please send me email if you have any questions. 

News 

• 12/02/10 - There were problems with the email alias for course questions <doc-os211-questions (A T) imperial.ac.uk>. This has been fixed now - please resend your question if you emailed about the coursework yesterday.
• 16/02/10 - The deadline for the first coursework has been extended until March 1st.

Syllabus

1. Introduction and Overview

• OS functions and characteristics
• Kernel organisation (monolithic, microkernel, hybrid)
• Types of operating systems
• Case studies: Linux and Windows

2. Device Management

• I/O layers: device independence
• Character devices, block devices
• Unbuffered vs buffered I/O
• Shared vs dedicated devices: spooling
• Device drivers
  
  • Microkernel vs. monolithic device model
  • Linux: loadable kernel modules
• Linux I/O Management
• Linux devices and classes, unified device model
  
• Linux I/O API
• System call interface
• Synchronous vs asynchronous I/O

3. Disk Management

• Disk storage devices
  • Hardware layout
  • Disk performance
  • Disk scheduling: FCFS, SSTF, SCAN, N-Step SCAN, C-SCAN, Linux disk scheduling
    
  • Disk formatting
    
• RAID Levels 0, 1, 2, 3, 4, 5
• Disk caching: LRU, LFU

4. File Systems

• Files: naming, structure, types, file system calls, access methods, attributes
  
• File system organisation: contiguous file, block linkage, file allocation table, index blocks
  
• Free space management: free list, bitmap
• Directory organisation
  
  • Directory structures: flat, multi-level
  • Directory operations: Linux directories, directory system calls
    
  • Hard and soft links
  • Mounting
• Linux ext2: characteristics, inodes, block groups, file security, structure
• File system correctness: consistency semantics, checking, locks, archiving, recovery
  

5. Memory Management

• Memory hierarchy
• Logical vs physical address space: address binding, relocation, memory management unit, swapping
  
• Memory allocation
  • Contiguous allocation, multiple partition allocation, dynamic allocaiton
  • Memory protection, fragmentation
• Virtual memory
  • Paging
    • Address translation, paging hardware: TLBs
    • Page tables: hierarchical, hashed, inverted
  • Segmentation: hybrid segmentation/paging
  • Linux memory layout
• Demand paging
  • Page faults
  • Copy-on-write, memory-mapped files
  • Page replacement: FIFO, optimal, LRU, reference bit, second chance, clock, LFU, MFU
    
    • Belady's anomaly
    • Locality of reference
      • Memory map, working set model
      • WSClock algorithm, global vs local page replacement
    • Linux page replacement

6. Advanced Topic: OS Virtualisation (Guest lecture)

• Virtual machines and hypervisors
• Type 1 and Type 2 virtualisation
• Paravirtualization
• Virtual machine interface
• Memory virtualization: shadow page tables
• I/O virtualisation

Handouts

Note: I will make solution notes for tutorial questions available one week after the corresponding tutorial.

Week 2

Part 1 - Introduction and Overview
Part 2 - Device Management (answers)
Tutorial 1 - Introduction and Device Management (answers)

Week 3

Part 3 - Disk Management (answers)
Tutorial 2 - Disk Management (answers)

Week 4

Week 5

Part 5 - Memory Management
Tutorial 4 - Memory Management (answers)

Week 6

Part 6 - OS Virtualization

Recommended Books

• Modern Operating Systems, Tanenbaum, 3rd edition, Prentice Hall, 2008
• Operating Systems, Design and Implementation, Tanenbaum & Woodhull, 2nd edition, Prentice Hall, 1997
• Operating Systems, Deitel, Deitel, Choffnes, 3rd edition, Pearson/Prentice-Hall, 2004
• Operating System Concepts, Silberschatz, Galvin, Gagne, 7th Edition, John Wiley & Sons, 2005
• Operating Systems – Internals and Design Principles, W. Stallings, 5th Edition, Prentice­ Hall, 2005