CS 361 -- Operating Systems --- Spring 2014


The final exam will be given on 4/30 at 8am in MK 524.

The questions for Midterms #1 and Midterm #2 are linked here.


    Final Exam Study Questions (answers)
    1. Define swapping and paging, and explain why paging can enable a greater number of processes to run without incurring undue disk overhead.
    2. Explain how page protection hardware is used to implement fork using copy-on-write, and how it enables the common fork-then-exec sequence of operations.
    3. Describe a scenario in which FIFO page replacement results in high paging overhead.
    4. Explain the problem with using a conventional directory mechanism to efficiently store a large number of objects, and one way to work around the issue.

    Midterm #2 Study Questions (answers)
    1. If an operating system implements preemption of an executing process, it can still use a non-preemptive scheduling policy. Explain the difference between low level preemption and preemptive scheduling policy.
    2. Explain why the straightforward implementation of the Critical Section problem (Figure 6.7 in Section 6.4 of Silberschatz Ed. 8) does not guarantee non-starvation.
    3. Define the reader/writer problem and explain how it can be solved using only mutexes.
    4. Write pseudocode for a solution to the Bounded Buffer problem that using semaphores.
    5. Given the resource allocation graph of a system with a simple instance of each resource, how can we determine whether the system is in deadlock?

    Midterm #1 Study Questions (answers)
    1. Name three ways in which a program executing in user mode can enter kernel mode.
    2. If a process writes continuously to a pipe but no data is read, where does the data reside and what action does the kernel eventually take?
    3. Why is user level thread creation a more "lightweight" (efficient) operation than forking a child process?
    4. A program is structured using three threads: one reads input from an input file, one processes it and one writes the result to an output file. Is many-to-one or one-to-one a better thread management scheme for this program, and why?

Instructor: Micah Beck
Office: Min Kao 433
Office Hours: Wednesday 2:30-3:30pm
Email: mbeck@eecs.utk.edu

    Class Time: 10:10 am - 11:00 am MWF
    Classroom: Min Kao Engineering 524

TA: Rui Ma (homework)

    TA Office Hours: 1-3pm Thurs or by appointment
    TA Office: 349 Min Kao
    TA email: rma@utk.edu

Textbook

    Operating System Concepts
    Authors: Abraham Silberschatz, Peter B. Galvin, Greg Gagne
    Edition: 7 or higher

    Editions 7, 8 and 9 are available at a variety of prices, in hardback, paperback and for the Kindle e-book reader.

Reading Assignments

All reading assignments refer to the eigth edition of Silberschatz (ISBN 978-0-470-12872-5), but the corresponding sections in the seveth or nineth editions are equivalent and may be substituted.

    Reading Assignment for 1/13/2014 Chapters 1 & 2
    Reading for 1/15/2013 Chapter 3
    Reading for 1/27/2014 Chapter 4.1-4.3
    Reading for 2/7/2014 Chapter 5.1-5.3
    Reading for 2/24/2014 Chapter 6
    Reading for 3/10/2014 Chapter 7
    Reading for 3/24/2014 Chapter 8
    Reading for 4/7/2014 Chapter 9
    Reading for 4/21/2013 Chapters 10 & 11

Homework Assignments

All reading assignments refer to the eigth edition of Silberschatz. Students using other editions may obtain the homework problems from Dr. Beck.

    #1Homework due 1/27/2013 2.13, 2.14, 2.16, 2.17, 2.18, 3.2, 3.3, 3.4, 3.7 
    #2Homework due 2/10/2014 4.8, 4.10, 4.11, 4.13, 4.14 
    #3Homework due 2/28/2014 5.9, 5.10, 5.11, 5.13, 5.14, 5.17 
    #4Homework due 3/14/2014 6.8, 6.12, 6.16, 6.17, 6.32pdf
    #5Homework due 3/25/2014 7.10, 7.11, 7.15, 7.17pdf
    #6Homework due 4/9/2014 8.9, 8.11, 8.12, 8.15, 8.17, 8.18, 8.24pdf
    #7Homework due 4/21/2013 9.14 - 16, 9.18 - 9.20, 9.22, 9.23, 9.25, 9.30, 9.33, 9.35 pdf

Annotated Course Syllabus

The couse syllabus and reading will mirror the first 13 chapters of the book. Chapters 11, 12 and 13 may be combined or abbreviated depending on the class schedule.
  • Chapter 1: Introduction
  • Chapter 2: Operating-System Structures
    • What are the reasons for using libraries?
    • What is a protected resource?
    • What is a manager?
    • How is virtualization used to manage resources?
  • Chapter 3: Processes
    • What is a process? How does it differ from a task or a thread?
    • What are the elements of process context?
    • How is the process/task control block used in operating systems?
    • What are the steps in kernel/user and user/user context switches?
    • How are runnable processes managed, and how is the next to run chosen?
    • How are processes created?
  • Chapter 4: Threads
    • What are the major reasons for programming with threads?
    • What is the difference between a thread and a (heavyweight) process?
    • What are the different modes of support that an OS kernel may provide for threads?
    • What are the strengths of preemptive vs. non-preemptive threads?
    • How are threads used in the programming of multicore architectures?
  • Chapter 5: CPU Scheduling
    • What is the CPU-I/O burst cycle?
    • What is the function of a CPU scheduler? When are scheduling decisions made?
    • What are the usual criteria used in making scheduling decisions?
    • What are the criteria used in making preemptive scheduling decisions?
    • What is the ideal or optimal scheduler? Why can't it be implemented?
    • What is the definition and important attributes of these CPU scheduling algorithms: FCFS, SJF, priority, RR and multilevel?
  • Chapter 6: Process Synchronization
    • Why is mutual exclusion important in preemptive and parallel systems?
    • What are the requirements for a solution to the critical section problem?
    • How does Peterson's Solution to the Critical Section problem work?
    • How can Test & Set and Swap hardware be used to solve the Critical Section problem?
    • What are Semaphores and Monitors and how are they used for process synchronization?
    • What are Deadlock and Priority Inversion?
    • Explain the Bounded Buffer and Dining Philosophers' problems and their solutions.
  • Chapter 7: Deadlocks
    • What are the requirements for deadlock to be possible in a system?
    • What are the techniques for handling deadlocks?
    • How can deadlock be prevented/avoided/detected?
    • How is recovery from deadlock possible?
  • Chapter 8: Main Memory
    • What are the definitions and uses for swapping, paging and segmentation?
    • Describe a straightforward hardware implementation of paging.
    • What is a Translation Look Aside Buffer, and why is it important in paging?
    • How does a multi-level page table work? A hashed page table? An inverted page page table?
  • Chapter 9: Virtual Memory
    • How is page management hardware used to support demand paging? copy-on-write?
    • Define and explain one strength and one weakness of random, FIFO, optimal, LRU and LRU approximation page replacement algorithms.
    • Explain one explain one LRU algorithm and the second chance LRU approximation algorithms, and compare their use of resources.
    • What are the causes of thrashing and what can be done to avoid it?
    • Explain three advantages of memory-mapped files.
  • Chapter 10: File-System Interface
  • Chapter 11: File-System Implementation

Course Requirements and Grading

  • There will be two midterm exams and a final exam.
  • Homework will be assigned on a regular basis.
The final exam will have three sections:
  1. section 1 focuses on the material covered in midterm 1,
  2. section 2 focuses on the material covered in midterm 2,
  3. section 3 focuses on the rest of the course.

The final course grade will be calculated as

    10%(H) + 25%(M1') + 25%(M2') + 40%(F)

where
  • H = homework grade
  • M1' = MAX(final exam grade, midterm 1 grade)
  • M2' = MAX(final exam grade, midterm 2 grade)
  • F = final exam grade

For example, a student who scores 70 on midterm 1, 85 on midterm 2, 84 on the final, and 75 on the homework will have an overall score of

    10%(75) + 25%(MAX(84, 70)) + 25%(MAX(84, 85)) + 40%(84) = 83.35

The intention of this grading scheme is that students have two chances to show their mastery of the material covered in the two midterms: on the midterm and on the cummulative final. The 90% of the course grade that is awarded on the basis of exams is available to every student at the time they take the final.

While it is possible for a student to skip the midterm exams and rely solely on the homework and final for their course grade, students are strongly advised against this approach. Taking the midterm exams is a no-risk proposition: it can only improve a student's final course grade. Taking the midterms is also the best preparation for the final exam.


For students doing the the course as Honors By Contract

  • The operating system you will be using for this project is XinuPi, a port of the Embedded Xinu operating system to the Raspberry Pi.
  • A variety of tools and notes about working with the Raspberry Pi can be found on this page.
The steps to your honors project are:
  1. Arrange for a Pi execution platform, either hardware or virtual machine.
  2. Put a Xinu image on the Raspberry Pi. You can start with a prebuild image if that is easier, but you will have to create your own image to do the next step. (see this link for more information about installing Xinu on a Virtual Box virtual machine)
  3. Implement Shortest Burst First process scheduling in Xinu.
  4. Perform an experiment to show a difference in performance between standzard Xinu process scheduling and your implementation of SBF.