CMPS 111: Introduction to Operating Systems
 
Catalog copy
CMPS 111. Introduction to Operating Systems. F,W,S Fundamental
principles of operating systems: process synchronization, deadlocks,
memory management, resource allocation, scheduling, storage systems,
and study of several operating systems. A major programming project
will be required. Prerequisite(s): course 101 and Computer
Engineering 12C and 12L. C. McDowell, D. Long, S. Brandt, E. Miller

Explanation of prerequisites
CMPS-101: 
 Students need to have an advanced understanding of basic
 programming concepts including pointers, linked lists, hashing, queues,
 stacks, and trees and an ability to implement with
 appropriate algorithmic efficiency the data structures
 required in an operating system.
CMPE-012C/L:
 An understanding of assembly language and low-level machine
 concepts is essential to the code generation part of an
 operating system. Of particular importance are basics of computer
 architecture including ALU, cache, MMU and interrupts.
 
Required skills to pass the course.

Understanding and facility with the following concepts: Processes
and threads; Scheduling; Deadlocks; Memory management; I/O systems,
and File systems.

Core topics (must be taught)

1. What Is an Operating System? (a) Mainframe Systems, (b) Desktop
Systems, (c) Multiprocessor Systems, and (d) Distributed Systems

2. Computer-System Operation: (a) I/O Structure, (b) Storage
Structure, (c) Storage Hierarchy, (d) Hardware Protection, and (e)
Network Structure

3. Operating-System Structures: (a) System Components, (b)
Operating-System Services, (c) System Calls, (d) System Programs,
(e) System Structure, (f) Virtual Machines and (g) System Design
and Implementation

4. Processes: (a) Process Concept, (b) Process Scheduling,
(c) Operations on Processes (d) Cooperating Processes, and (e)
Interprocess Communication

5. Threads: (a) Multithreading Models and (b) Threading Issues

6. CPU Scheduling: (a) Basic Concepts, (b) Scheduling Criteria,
(c) Scheduling Algorithms, (d) Multiple-Processor Scheduling,
(e) Real-Time Scheduling, and (f) Process Scheduling Models

7. Process Synchronization: (a) The Critical-Section Problem, (b)
Synchronization Hardware, (c) Semaphores, (d) Classic Problems
of Synchronization, (e) Critical Regions, (f) Monitors, and (g)
OS Synchronization

8. Deadlocks: (a) System Model, (b) Deadlock Characterization, (c)
Methods for Handling Deadlocks, (d) Deadlock Prevention, (e) Deadlock
Avoidance, (f) Deadlock Detection, and (g) Recovery from Deadlock

9. Memory Management: (a) Swapping, (b) Contiguous Memory Allocation,
(c) Paging, and (d) Segmentation

10. Virtual Memory: (a) Demand Paging, (b) Process Creation, (c)
Page Replacement, (d) Allocation of Frames, (e) Thrashing, and (f)
Operating-System Examples

11. File-System Interface: (a) File Concept, (b) Access Methods,
(c) Directory Structure, (d) File-System Mounting, (e) File Sharing,
and (f) Protection

12. File-System Implementation: (a) File-System Structure, (b)
File-System Implementation, (c) Directory Implementation, (d)
Allocation Methods, and (e) Free-Space Management

13. I/O Systems: (a) I/O Hardware, (b) Application I/O Interface, (c)
Kernel I/O Subsystem, (d) Transforming I/O to Hardware Operations,
(e) Disk Structure, (f) Disk Scheduling, (g) Disk Management,
(h) RAID Structure, and (i) Tertiary-Storage Structure

14. Protection: (a) Goals of Protection, (b) Domain of Protection, (c)
Access Matrix, (d) Implementation of Access Matrix, (e) Revocation
of Access Rights, and (f) Capability-Based Systems

Core lab exercises

There are normally 4 to 5 programming assignments. The first is
for familiarization:

1. Implement a shell. The goal of this is to familiarize student
with the notions of processes and system calls.

The second through fourth are modifications or additions to a simple
operating system (Nachos or DLX/OS).

2. Implement a process scheduler such as lottery scheduling. 
3. Implement a synchronization method such as monitors or semaphores. 
4. Implement a simple file system such as FAT.

Optional lab exercises 
1. Implement a virtual memory page replacement policy 
2. Implement an interprocess communication method such as a FIFO

Text "Modern Operating Systems," by Andrew Tanenbaum Prentice Hall;
ISBN: 0130313580; 2nd edition

Possible Alternative Texts "Operating System Concepts," by Abraham
Silberschatz, Peter Baer Galvin, Greg Gagne, John Wiley & Sons;
ISBN: 0471417432; 6th edition

Prepared by Darrell Long, 10/02; revised 5/03