ANNOUNCEMENT OF THE MATERIAL FOR OPERATING SYSTEMS SECTION OF THE COMPUTER SYSTEMS EXAM for 1997 -------------------------------------------------------- The OS Portion of the Computer Systems Exam is a SYLLABUS BASED EXAM. It is NOT a course based exam. Student's are expected to have a mastery of the material presented in the first 12 chapters of Silbershatz and Galvin's text as prerequisite knowledge. A good portion of the exam will cover these first chapters of Galvin so you must know the material in that text well. The syllabus below follows the outline of material covered in select portions of Professor Singhal's texbook. This serves as a guide in your literature review. You may wish to refer to the original papers in your studies. Some of the material below also overlaps with later chapters found in Silbershatz and Galvin. As mentioned above, the exam will cover a range of material from basic issues in operating systems from SilberShatz and Galvin to more advanced material listed below. SYLLABUS for the OS Portion of the Computer Systems Exam (material beyond Silbershatz and Galvin) -------------------------------------------------------- Overview Introduction Functions of the OS Design Approaches: Layered, Kernel, VM Approach Types of Advanced OSs Synchronization Concept of a Process Concurrent Processes Threads: user-level, kernel-level, lightweight processes ( Vahalia's book has good coverage and definition of threads) Critical Section Problem Early Mechanisms Semaphores Other Synchronization Problems Dining Philosophers Producer-Consumer Readers Writer Semaphore Solution to Readers Writers Language Mechansisms for Synchronization Monitors Ada Rendezvous Process Deadlocks Model of Deadlocks Single-unit request model AND Request Model Or Request Model AND-OR Request Model The P-out-of-Q Request Model Model of Resources Types of Resources Types of Resource Accesses A Graph Theoretic Model of System State General Resource Systems General Resource Graph Operations on the General Resource Graph Necessary and Sufficient Conditions for a Deadlock Graph Reduction Method Systems with Single-Unit Request Systems with Consumable Resources Systems with Reusable Resrouces Systems with Single-Unit Resources Deadlock Detection Deadlock Prevention Deadlock Avoidance Advantages/Disadvantages Architecture of Distributed Systems A basic knowledge of issues is assumed A variety of texts could be used to overview these issues (these issues also covered in CS263) Issues in Distributed Operating Systems pg 74-78 Singhal networks - general knowledge local wide area Communication Primitives Message Passing RPC Design issues in RPC Theoretical Foundations Inherent Limitations of a Distributed System Absence of a Global Clock Absence of Shared Memory Lamport Logical Clocks Vector Clocks Causal Ordering of Messages Global State Chandy-Lamport Gobal State Recording Algorithm Cuts of a Distributed System Termination Detection Distributed Mutual Exclusion Preliminaries Requirements How to Measure Performance Simple Solutions Non-Token Based Algorithms Lamports Algorithm Ricart-Agrawala Algorithm Raymond's Algorithm Performance Analysis/Comparison Distributed Deadlock Preliminaries: Model, Resource vs. Communication Deadlocks, Graph Model Deadlock Handling: Prevention, Avoidance, Detection Issues Control Organizations: Centralized, Distributed, Hierarchical Centralized Algorithms Completely Centralized Algorithms Distributed Deadlock Detection (assumes a general knowledge of one algorithm from each class i.e. should be able to differentiate the techniques) Path Pushing Edge Chasing Diffusion Computation Global State Detection Based Algorithm Agreement Protocols Classification of Agreement Problem Byzantine Agreement Consensus Problem Interactive Consistency Relationship between them Solutions to Byzantine Agreement Upper bound on number of Faulty Processors Impossibility Result (familiar) Applications of Agreement Algorithms Fault tolerant Clock Synchronization Atomic Commit in DDBS Distributed File Systems Architecture (understanding) Mechanisms for Building: mounting, caching, hints, bulk data transfer, encryption Design Issues Naming Caches: Main Memory or Disk Write Policy Cache Consistency Availability Scalability Semantics Case Studies: Sun NFS Sprite Apollo Domain AFS Coda x-Kernel Logical File system Locus Mach Log Structured File systems Disk space management Distributed Shared Memory (Virginia Lo's Computer Paper has a good overview) Architecture and Motivation Algorithms for Implementing DSM Central Server Migration Read Replication Full Replication Memory Coherence Semantics Coherence Protocols Design Issues Case Studies: Ivy Mirage Clouds Fault Tolerance Introduction Issues Atomic Actions and Committing Commit Protocols: Two Phase Commit Voting: Static Voting, Majority Based Dynamic Voting Reliable Communication: Atomic Broadcast Multiprocessor OSs (some basic knowledge) Structures of Multiprocessor OSs OS Design Issues Threads: User level, kernel, level, others Process Synchronization Test and Set Swap Fetch and Add Instruction Resource Security and Protection Preliminaries Potential Security Violations External vs Internal Security Policies and Mechanisms Protection Domain Design Principles for Secure Systems Access Matrix Model Implementations of the Access Matrix Capabilities ACLs Lock and Key Advanced Models of Protection Bell-LaPadula Model Cryptography Terms and Definitions Private Key Cryptography: DES Public Key Cryptography Implementation RSA Method Signing Messages Concurrency Control Algorithms (covered in CS160, as well) Basic Synchronization Primitives Locks Timestamps Lock Based Algorithms Static Locking Two Phase Locking Problems with 2PL Timestamp-based Locking