CS 4375: Theory of Operating Systems

Course Description

Most students enjoy this course because it exposes so much of the "magic" of how programs are managed on modern computer systems. For example, a student enrolled in Theory of Operating Systems will learn

• the mechanisms that permit multiple programs to effectively share a single computer
• how programs are started, and how they communicate with each other
• how input/output (such as sound/video/mice/files/windows/networks) are implemented

These functions of a modern operating system are all based on the application of a few fundamental concepts. This course teaches these key concepts and "makes them real" by engaging students in the creation of small programs that implement their key functionalities.

Operating systems design is an exciting area of computer systems that ties together architecture, language, and real-world constraints. Many solutions to the problem of managing a systems explored in this course involve interesting trade-offs between flexibility, performance, and reliability. In order that students gain a mature appreciation of these trade-offs, this course is conducted in a very interactive manner. Students are encouraged to dialog with each other and the professor to discuss the implications of design options. An email list facilitates student/instructor interaction outside of class.

Since the design of operating systems requires a very practical understanding of computer architecture, algorithms, and software design, most students are not prepared for this course before their senior year.

Few programming languages are as well suited to the implementation of operating systems as "C". For this reason, most labs for this course must be written in C. Students with little experience in C are strongly encouraged to review it (some resource links are listed below).

Course Objectives

Text & Email list

• Text: Tannenbaum's "Modern Operating Systems", 2^nd Ed.
• Course meets Tuesdays & Thursdays 4:30-5:50 in CS308.
• Much communication is via email: JOIN THE CLASS MAILING LIST: http://listserv.utep.edu/mailman/listinfo/cs-os
• Official course outcomes (last updated in 2000)

Instructor: Dr. Eric Freudenthal

• email: efreudenthal at utep.edu
• phone: 915 747 6954
• Office Hours: See my homepage

Teaching assistant: Maria Ruiz (PhD Candidate)

Course Objectives

Course Content

• Class notes
• Coarse-grained topic outline
  1. Introduction
     • What is an operating system?
     • History
     • Operating systems for various devices
     • Review of computer architecture
     • Summary of OS concepts
     • System Calls
     • Operating System Structure
  2. Processes and Threads
     • Processes
     • Threads
     • Inter-process communication
     • Classical problems
     • Scheduling
  3. Synchronization (mostly deadlock prevention)
     • Resources
     • Deadlock (another reason why ostriches do not dominate the planet)
     • Detection of deadlock
     • Stopping systems from entering deadlock (avoidance)
     • Designing systems that can not deadlock (prevention)
  4. Memory Management
     • Single address space (both mono- and multiprogramming)
     • better nomenclature than book
       • virtual memory
       • demand v. voluntary systems
       • paged v. segmented systems
     • Managing paged systems
       • exposes a eviction (replacement) problem
       • program behavior (locality)
       • algorithms
       • implementation
       • simulation
     • Managing segmented systems
     • exposes both a placement & eviction problem
  5. Input/Output
     • characteristics of i/o devices
     • how to structure drivers
     • disks
     • terminals, graphical devices
     • networked terminals
     • power mgmt
  6. File Systems
     • files
     • directories
     • implementation
     • special files (/dev, links, /proc)
     • example filesystems
  7. Multimedia
     • File encoding
     • processor scheduling issues
     • disk scheduling issues
     • storage, caching, and transmission issues
     • Multiprocessor Systems
     • Security

Examinations (in class, closed book, no notes permitted)

Labs

Labs must represent individual work and will contribute heavily to your final grade. Our TAs are very effective at detecting plagiarism, which will be reported to the Dean of Students (see section on academic honesty below).

Students are encouraged to discuss requirements of lab assignments, and are encouraged to share evaluation test sets. However, students should prepare their implementations without detailed knowledge of each others' implementations.

Under normal circumstances, labs must be submitted as tarballs (see "man tar") and mailed to the TA (Ryan Spring: rcspring@utep.edu).

• Assignments (exact due dates announced in class and subsequently updated here)
  • C essentials: Lab 0 due: Wed, 3 Sept at 11:59 PM
  • Tthreads: lab 3 Due Monday, 6 October at 11:59 PM
  • Memory allocator:
    • Lab 4a and
    • Lab 4b (grad students only).
  • Scheduler Simulation:
  • Posix shell: lab 1
• Submitting lab assignments
  • Assignments are to be submitted using subversion. Instructions are posted here.
  • The course assignment repository's URL (for subversion, DO NOT USE WITH YOUR WEB BROWSER) is https://robust.cs.utep.edu/svn/classes/tos.
  • Your submission should only include human-readable files (no object or executables!).
• Reference material:
  • A short demo of make (must be "untarred")
  • Review of C & Unix :
    • Preliminary review of C & command-line systems Note that this web page contains some C++-isms related to memory management.
    • Vince Fonseca (OS S05) found this wonderful website of C tutorials
    • Cesar Alaniz found this review of the C libraries: http://www-ccs.ucsd.edu/c/lib_over.html
    • Ryan Knotts suggests "Pointers on C" (isbn 0673999866) as a good review of C pointers.
• Lab grades: Your labs must satisfy assignment guidelines and produce output as specified in the assignment. Programming assignments are graded on the following criteria
  • Correctness: Your submission should include a test suite to demonstrate that it functions correctly. Furthermore, the TA may test your lab using other input.
  • Documentation and programming style: Your code should be documented and written in a professional, consistent, understandable style. Every assignment should include a "README" document or web hierarchy that the TA can easily use to determine
    • How to compile & run your program
    • The general structure and any non-obvious aspects of your program.
    • The testing strategy utilized for your program
    • Any deficits in your program (you will lose less credit if a problem is documented than if it is discovered by a TA.
• Late policy:
  • Labs submitted within 1 week of their deadline will suffer a reduction of one letter grade. (e.g A lab that would otherwise be graded as a "B" will instead earn a "C".
  • Labs may be re-submitted for re-grading one week after grades are released. Up to one half of credit lost on previous submission can be recovered.
  • Re-submissions should be made as changes committed to the same directory in subversion as the initial submission.
  • Students are not required to ever resubmit.
  • Students must explicitly request re-grading after re-submission by sending email to the TA prior to the due date corresponding to their submission. If a student does not notify the TA, they are at risk of it not being graded.
  • Late assignments will be considered to be re-submissions.
  • No re-submissions are accepted more than one week after initial announcement of grades.
• Grading rubric (general):
  • 4 point scale:
    • 0: irrelevant work
    • 1: a tiny bit of understanding demonstrated
    • 2: good try, shows some understanding, but result is weak
    • 3: mostly right
    • 4: perfect
    • 5: spectacular, extraordinary, shows professionalism well beyond what is expected. (demonstration of strong performance harms nobody else's grade)
  • separate scores for
    • following instructions properly (submitted properly, solved correct problem, used proper tools)
    • functions correctly (programmed correctly)
    • appropriate algorithm
    • well documented, readable, easy to use

Be sure to schedule sufficient time for cleaning up your code, testing, and the writing of documentation. Assignments written in an unprofessional style or lacking clear and useful documentation will suffer severe grading penalties. Students with weak written communication skills may wish to contact the UTEP Teaching & Learning center.

Accommodations for Students with Disabilities and Exceptional Circumstances

Individuals with disabilities have the right to equal access and opportunity. Please contact Dr. Freudenthal or the UTEP Office of Disabled Student Services (DSSO) if you have a special circumstance such that an accommodation would be helpful in permitting you to excel or demonstrate mastery of the material covered in this course.

Standards of Conduct and Academic Honesty

• Standards of Conduct: Students are expected to conduct themselves in a professional and courteous manner, as prescribed by the Standards of Conduct: http://hoop.utep.edu/Student_Affairs_Chapter_One-HOP.htm Graded work should be unmistakably your own. You may not transcribe or copy a solution taken from another person, book, or other source ( e.g., a web page). Copying other's work will not be tolerated. Professors are required to report academic dishonesty and any other violation of the Standards of Conduct to the Dean of Students.
• Permitted collaboration: Students may discuss requirements, background information, test sets, and the output of their programs. However, implementations and documentation must be prepared individually.
• If academic dishonesty is suspected: You will receive an incomplete for the lab, and your case will be referred to the Dean of Students for adjudication. The Dean of Students has published a website with complete details concerning the UTEP Academic Honesty policy at the following arcane URL: http://studentaffairs.utep.edu/Default.aspx?tabid=4386.

Course Grading Policy