CS 537 - Introduction to Operating Systems CS 537 Introduction to Operating Systems Note: This web page describes aspects of cs537 that remain relatively constant from semester to semester. Another web page describes the course as it is being taught this semester. Instructor Marvin Solomon Contents Summary Lecture Information Text Projects Grading Course Schedule Lecture Notes Summary CS 537 is intended as a general introduction to the techniques used to implement operating systems and related kinds of systems software. Among the topics covered will be process management (creation, synchronization, and communication); processor scheduling; deadlock prevention, avoidance, and recovery; main-memory management; virtual memory management (swapping, paging, segmentation and page-replacement algorithms); control of disks and other input/output devices; file-system structure and implementation; and protection and security. Lecture Information Lecture: Two sessions per week, each 1 hour and 15 minutes. Discussion: One session per week, 50 minutes. The discussion section is not ``optional'': it is at least as important as the lectures. The primary focus of the discussion meetings will be topics related to the projects (including introduction to the Java programming language), but time will also be available for answering any questions you have regarding points raised in the the lectures or the text. Text Required Operating Systems Concepts (Fourth Edition) by Abraham Silberschatz and Peter Galvin Addison-Wesley, 1994. Strongly Recommended The Java Programming Language by Ken Arnold and James Gosling, Addison-Wesley, 1996. Online References I have written a tutorial, Java for C++ Programmers as well as a set of online lecture notes. In addition, lots of additional helpful materials about Java are available on the WEB. The following references have been collected locally for fast access. The Java Tutorial The Java Language Specification Java Core API Documentation Projects There will be five programming projects, all in the Java programming language. Sun SparcStation workstations running the Solaris dialect of the Unix operating system are provided for your use, but you may use any computer to which you have access that implements the Java programming language. However, if you do not use the Computer Sciences Department's computers, you will be responsible for transferring any required data sets or software packages to your computer. The first assignment will be an easy ``get acquainted'' exercise designed to help you become familiar with the computing environment and the Java language. Subsequent projects will involve process synchronization, processor scheduling, disk scheduling, and file-system implementation. On all but the first project, students will be required to work in pairs. Both members of a pair will receive the same grade on a project. Feel free to discuss projects with anyone, but you must not share code with anyone but your partner. Note: Programming assignments are changed from semester to semester. A master list of projects assigned in the past is available. Cheating will be vigorously punished. See the student handbook for more details. Enough said! Assignments are due at the beginning of class (9:30 a.m.) on the date indicated. Over the entire semester, you have three late days of credit. You can use these late days on different assignments (e.g., one day on each of three assignments) or all three days on one assignment. Late days may not be used for the last assignment. Why Java? Most students taking this course will be familiar with C++ but not Java. Why, then, did we choose Java? There are several arguments in favor of it. Java is a more congenial programming environment. Runtime errors such as bad subscripts, null pointers, and uninitialized variables cause exceptions caught by the language runtime rather than mysterious crashes or random behavior. Java Strings are much easier to use than char * arrays. Garbage collected storage management is extremely handy. There's more. Try it, you'll like it! Java is very trendy. Java had caught on faster than any other new language in history. Many of the reasons for Java's growing popularity have little to do with the way we will use it in this course (we will discuss these issues in class), but a byproduct of this course will be knowledge of Java, which is becoming quite a marketable commodity. Java has ``operating system'' features built in. In particular, it is the first widely-used programming language with language-level support for concurrency (threads) and synchronization (monitors). On the other hand, switching to a new programming language is always a bit dislocating. Fortunately, there are excellent resources are available to ease the transition. The Java Programming Language by Arnold and Gosling is amazingly good. It is neither an introductory programming primer (the authors assume you already know how to program) nor a reference manual (although a reference manual is available online), but a readable introduction to the language, which takes you all to the way from getting started to everything you need to write quite sophisticated programs in Java. This book is available at the University Bookstore. You are strongly encouraged to buy it. I have also gathered a variety of other resources together, including a online tutorial that is far more extensive than the short tutorial I wrote, and a reference manual for the standard class libraries you will be using. Grading There will be a midterm and a final exam, each of which will count for 25% of your grade. The first programming project (getting started) will count for 2% of your grade. The remaining four projects will count for 12% each. Course Schedule The following schedule is tentative; it may be updated later in the semester, so check back here frequently. Week 1 Introduction Chapter 1 Weeks 2 - 6 Processes, Synchronization, Processor Scheduling Chapters 4 - 7 Week 3, first lecture Project 1 Due Learning Java Week 6, second lecture Project 2 Due Synchronization Weeks 6 - 11 Memory Management and Virtual Memory Chapters 8 - 9 Week 8, first lecture Project 3 Due CPU Scheduling Week 8 Midterm Exam 7:25 - 9:25 pm, Room to be announced. Weeks 11 - 14 File Systems and Disks Chapters 10 - 12 Week 11, second lecture Project 4 Due Disk Scheduling Week 15 Protection and Security Chapters 13 - 14 Week 15, second lecture Project 5 Due File Systems Finals Week Final Exam Two hours, date and time to be announced. Lecture Notes Note: These notes are updated each semester. The first few installments were most recently updated Fall 1997. The remainder are as they were Fall 1996 (when a different text was used). ./foo cs537-old/foo cs537-old/last/foo Introduction History What is an OS For? Bottom-up View Top-Down View Course Outline Java for C++ Programmers Processes and Synchronization Using Processes What is a Process? Why Use Processes Creating Processes Process States Synchronization Race Conditions Semaphores The Bounded Buffer Problem The Dining Philosophers Monitors Messages Deadlock Terminology Deadlock Detection Deadlock Recovery Deadlock Prevention Deadlock Avoidance Implementing Processes Implementing Monitors Implementing Semaphores Implementing Critical Sections Short-term Scheduling Memory Management Allocating Main Memory Algorithms for Memory Management Compaction and Garbage Collection Swapping Paging Page Tables Page Replacement Frame Allocation for a Single Process Frame Allocation for Multiple Processes Paging Details Segmentation Multics Intel x86 Disks File Systems The User Interface to Files Naming File Structure File Types Access Modes File Attributes Operations The User Interface to Directories Implementing File Systems Files Directories Symbolic Links Mounting Special Files Long File Names Space Management Block Size and Extents Free Space Reliability Bad-block Forwarding Back-up Dumps Consistency Checking Transactions Performance Protection and Security Security Threats The Trojan Horse Design Principles Authentication Protection Mechanisms Access Control Lists Capabilities That's all folks! solomon@cs.wisc.edu Wed Oct 1 11:16:56 CDT 1997 Copyright © 1996 by Marvin Solomon. All rights reserved.
