412-S12-index

CMSC 412-0201

Operating Systems

Spring 2012

http://www.cs.umd.edu/~shankar/412-S12
Check at least twice weekly. See News for last update

Professor	A. Udaya Shankar (email: shankar@cs.umd.edu). Office hours: TuTh 3:30-4 or by appointment (AVW 4141).
TA	Johnny Wu (email: jywu07@cs.umd.edu). Office hours: On Piazza.
TA	Daozheng Chen (email: dchen@cs.umd.edu). Office hours: On Piazza.
Classes	CSIC 2107. TuTh 2:00-3:15pm

News

[May 12] NEW Exam 3: some typical filesystem/disk questions:
- Given a filesystem (e.g., fat, gosfs, unixfs) and a file, determine the number of disk blocks used to store the data and metadata of the file. (Relevant parameters of the file system will be given, (e.g., number of pointers in an inode, name size, block size.)
- Given a filesystem and a file, determine the number of disk blocks accessed to read a file block.
- Given a sequence of disk read requests and a disk scheduling discipline (e.g., fifo, nearest first, scan), determine the order in which the requests are served and the distance traversed by the disk head.
- Questions related to projects 5 and 6. (Don't ask me for details.)
[May 12] NEW Exam 3:
- All the material for exam 2 plus the following:
  - Lecture slides 7-20 (from 412 Fall 2011 page).
  - Notes 4-15 links on class page.
  - Material covered in class after exam 2.
  - Projects 3-6 (not requiring code details).
  - OSC chapters on file-system interface and file-system implementation (chapters 11 and 12 in OSC edition 6). You can skip parts specific to remote file systems or distributed file systems.
- The structure of the exam is approximately as follows:
  - [30%] Paging, deadlocks, Banker's algorithm (as described for exam 2).
  - [35%] Concurent programming questions (as described for exam 2).
  - [35%] File systems and disks. (Examples questions by Monday, hopefully.)
[May 9] exam 2 solution.
[Apr 12b] Exam 2 typical questions
- Write pseudo-code to solve a concurrency problem, e.g., mutual-exclusion, producer-consumer, readers-writers, counting semaphore using binary semaphore, strong semaphore using weak semaphore, semaphore using atomic reads and writes, semaphore using test-and-set, semaphore using ready/wait queues (in OS).
- Given a resource allocation state, does deadlock exist (deadlock detection). Given a resource allocation state, is it safe to grant a request (deadlock avoidance). Does a resource allocation policy prevent deadlocks.
- Paging. Given virtual address size, physical address size, page size, determine a page table structure (number of entries, fields in each entry, field size, etc.). Which parts are accessed by hardware.
- Same as above but for TLB.
- Paging. Given the number of physical pages, a sequence of addresses, and a replacement policy (LRU, fifo, optimal, LRU-approx), determine the number of page faults and the final state of the page table.
- Same as above but for TLB.
[Apr 12a] Exam 2 topics:
- Lecture slides 7-12 (from 412 Fall 2011 page).
- Notes 4-15 links on class page.
- Material covered in class.
- Projects 3-4 (not requiring code details).
- Following text sections (taken from OSC, edition 6)
  - 7.1 Process synchronization: background; 7.2 The critical section problem; 7.3 Synchronization hardware; 7.4 Semaphores; 7.5 Classic problems of synchronization.
  - 8.1 Deadlocks: system model 8.2 Deadlock characterization 8.3 Methods for handling deadlocks 8.4 Deadlock prevention 8.5 Deadlock avoidance 8.6 Deadlock detection 8.7 Recovery from deadlock
  - 9.1 Memory management: background 9.2 Swapping 9.3 Contiguous memory allocation 9.4 Paging 9.5 Segmentation 9.6 Segmentation with paging
  - 10.1 Virtual memory: background 10.2 Demand paging 10.3 Process creation 10.4 Page replacement 10.5 Allocation of frames 10.6 Thrashing
[Mar 14] Notes from 412-S99.
[Mar 13] exam 1 solution.
[Feb 29] Exam 1: Problems will be in the style of those in the practice exams from Fall 2011 412. The topics covered are text sections (listed below), lecture slides 1-8 (from 412 Fall 2011 page), concepts covered in class, and projects 0-2.
- DMA and scheduling are two areas for quantitative problems (e.g., number of memory-cpu cycles needed for an IO operation, average response time for a queueing discipline given a configuration of jobs).
- Writing pseudo-code to solve a particular concurrency problem (e.g., mutual-exclusion, producer-consumer) using different kinds of hardware support (e.g., atomic reads and writes, test-and-set, semaphores).
- "Descriptive" problems based on projects 0-2 and following text sections (taken from OSC with Java, edition 6):
  - 2.1 Computer system operation; 2.2 IO structure; 2.3 Storage structure; 2.4 Storage hierarchy; 2.5 Hardware protection.
  - 3.1 System components; 3.2 Operating system services; 3.3 System calls.
  - 4.1 Process concept; 4.2 Process scheduling; 4.3 Operations on processes; 4.4 Cooperating processes
  - 5.1 Threads overview; 5.2 Multithreading modles; 5.3 Threading issues;
  - 6.1 CPU scheduling: Basic concepts; 6.2 Scheduling criteria; 6.3 Scheduling algorithms.
  - 7.1 Process synchronization: Background; 7.2 The critical section problem; 7.4 Synchronization hardware; 7.5 Semaphores; 7.6 Classical synchronization problems.
[Feb 4] Project 1 up. Handout same as last year: http://www.cs.umd.edu/class/fall2011/cmsc412/project1/index.html. Due: Fri Feb 17 6pm. Late submission: see Piazza.
[Jan 30] Discussion slides
[Jan 29]
- Discussion section this Monday (jan 30) for just this week.
- Project 0 due on Friday Feb 3.
[Jan 27] Exam dates posted.
[Jan 26] Piazza link: http://piazza.com/umd/spring2012/cmsc412
The sixth edition of the book is adequate.

Overview

There is a significant programming project (GeekOS). It requires you to read and understand provided code and write new modules. Overall it is very intensive and time consuming.

I'll be following Prof Hollingsworth's Fall 2011 412. In particular, the projects are (almost) the same, and the lecture slides and discussion notes should be helpful.

Topics covered (in order approximately):

Introduction to Operating Systems (1 week)
Concurrent Processes (2 weeks)
Kernel implementation techniques (1 week)
CPU scheduling (1 week)
Memory Management (2 weeks)
File and I/O Systems (2 weeks)
Security and Protection (1 week)
Networking and Distributed Systems (2 weeks)
Objects and Naming (1 week)
Window and Display Services (1 week)

Required text:

Operating System Concepts, 6th edition or later

Notes

These notes are old (except for 10x) but useful. (Notes 1-3 are trivial, given GeekOs.)

Programming projects

See Piazza.

Grading

You will get a letter grade for project and a letter grade for the rest. If you get D or F in either, then that is your course grade. If you get C or higher in both, then your course grade will be determined by both as follows.

Midterm 1: approx 15% (Thu Mar 8)
Midterm 2: approx 15% (Thu Apr 19)
Final : approx 25% (Wed May 16 10:30-12:30)
Project: approx 45%
Class participation: approx 5%

"Approx" means +/− 5%. For example, projects can become 50% and class particpation can become 0%.

Missed exams or submission deadlines

Each project has a regular deadline and a late deadline. No submissions after the late deadline.
If you miss an exam or project deadline due to medical or family emergency, please see me. If it's due to illness, please bring documentation signed by a health care professional.
If you miss a midterm exam, the weight of the exam will be moved to the next exam.

Regrades

Any regrade request (for exams, homeworks, projects) must be submitted within a week of the grade being posted.

Academic Integrity

Academic dishonesty.