CS 441 Advanced Operating Systems

Total Credits: 3 cr

Course Coordinator: Robert Rinker

URL: http://www2.cs.uidaho.edu/~rinker/cs541/index.html

Current Catalog Description: Principles of contemporary operating systems for network and distributed computer systems; sequential processes, scheduling, process synchronization, device management, file systems, memory management and protection and security.

Textbook: Tanenbaum and Van Steen, Distributed Systems: Principles and Paradigms, Prentice Hall

References: Chow and Johnson, Distributed Operating Systems and Algorithms, Addison Wesley.

Course Goals: This is a second course in operating systems, focusing primarily on distributed systems, including networked systems. Many of the problems and concepts studied in CS 240 are revisited, with an emphasis on distributed system solutions.

Prerequisites by Topic:

• Process management
• Memory management
• Synchronization
• Files and files systems

Major Topics Covered in the Course:

• Distributed systems: definitions and concepts. (2 hours)
• Communication concepts: protocols, RPC, message and stream communication. (6 hours)
• Processes: threads, client-server model, code migration, and scheduling. (6 hours)
• Naming: methods for naming, name resolution, and name spaces. Mobile entities. (4 hours)
• Synchronization : Real clocks, logical clocks, centralized vs distributed mutual exclusion, election algorithms, and transaction-oriented operations (6 hours)
• Consistency and replication: consistency models, distribution protocols, and consistency protocols. (6 hours)
• Fault tolerance: basic concepts – the Byzantine Generals problem and extensions, agreement algorithms, reliable communication concepts, transaction-oriented commit, and recovery schemes. (6 hours)
• Distributed Files systems: NFS, Coda, and object-based systems. (4 hours)

Laboratory projects (specify number of weeks on each): None.

• Write an MPI implementation of the Row-Column-Oriented Matrix Multiply Algorithm. (3 weeks)
• Write a Threads implementation of the Matrix Multiply Algorithm. (3 weeks)
• Write a simulator for vector logical clocks, and compare the accuracy of clocks at each node, given varying amounts of communication. (3 weeks)

Estimated Curriculum Category Content:

Area	Core	Advanced	Area	Core	Advanced
Algorithms		1	Data Structures
Software Design		0.5	Prog. Languages
Computer Arch			Other		1.5

Oral and Written Communications: None.

Social and Ethical Issues: None.

Theoretical Content:

• Logical clocks (3 hours)
• Mutual exclusion / election algorithms (6 hours)
• Consistency models (3 hours)
• Fault tolerance (3 hours)

Problem Analysis: None.

Solution Design: Students are required to design a distributed algorithm, using two different distributed models – MPI and threads. Students must design a network simulator that requires several processes, each sending a different number of messages.

Course Outcomes: The following list documents the course outcomes and crossreferences them to the BSCS program outcomes. The letter at the beginning of each reference identifies the program outcome supported. The numbers sequentially identify the course outcome for this course. After completing CS 441 a student should know or be able to: