ad majorem Dei gloriam

CPS 356: Operating Systems

Department of Computer Science, University of Dayton

Fall 2018

Table of Contents (TOC)

Course Description

CPS 356 (3 hours) is a course that introduces the theoretical and practical issues underlying an operating system's structure and operation. Topics include process and thread creation and management, scheduling, concurrent, multi-threaded programming and synchronization, deadlock, memory management, virtual memory, and computer security. Concepts are demonstrated using the C, Go, and Elixir programming languages in a Linux environment. This course assumes no prior experience with Linux, C, Go, Lua, or Elixir.

Course Details

Pre-requisite:
CPS 250 (Introduction to Computer Organization) or ECE 314 (Fundamentals of Computer Architecture) & CPS 350 (Data Structures & Algorithms).
Meeting times:
Tue Thu 5:05pm-6:20pm, Miriam Hall Room 203.
Instructor:
Dr. Saverio Perugini, e-mail id: sperugini1, tel: 229-4079, office: AN 145
OHs: Mon Wed 3:00pm-5:00pm; Thu 3:30pm-4:30pm (only when classes are in session); & by appointment.
Graduate Assistant and Student Helper:
Matthew Weiler (e-mail id: weilerm3) and Patrick Marsee (e-mail id: marseep1); Miriam Hall 16
OHs: M 1:15pm-3:20pm; T 11:00am-1:45pm; W 1:15pm-3:20pm; Th 11:00am-1:45pm; (only when class is in session); & by appointment.

TOC

Required Textbooks

    [LP] Linux Programming by S. Perugini. 2018. Draft (Available as a Resource in Isidore).

    [PLCI] Programming Languages: Concepts and Implementation by S. Perugini. 2018. Draft (Available as a Resource in Isidore; only Chapter 14: Concurrency and Synchronization needed for this course.).

    [SCMSW] Seven Concurrency Models in Seven Weeks: When Threads Unravel by P. Butcher. Pragmatic Programmers, Dallas, TX, 2014. ISBN-13:978-1-937785-65-9 (textbook webpage contains links to the source code of all programs in the text). An eBook of [SCMSW] is available free to all UD students in the library's eContent collection. To access it conduct a search for the title in the library's catalog at library.udayton.edu.

Steps to access [SCMSW] off-campus:
  1. Go to https://login.libproxy.udayton.edu/menu.
  2. Login using your standard UD credentials.
  3. Click on the link labeled: EBSCO Ebook Collection (formerly NetLibrary).
  4. This link will will take you to a page were you can perform a search. Search for "Seven concurrency models in seven weeks: When threads unravel" Click on "eBook Full Text".

    Note that there is a limit on how many people can view the book and once someone checks it out, no one else can use it. Also, if you incorrectly break your session (closing the page), the book remains checked out for a period of time and you cannot use the book in until the session ends.
    [SMLSW] Seven More Languages in Seven Weeks: Languages that are Shaping the Future by B.A. Tate, F. Daoud, I. Dees, & J. Moffit. Pragmatic Programmers, Dallas, TX, 2014. ISBN-13:978-1-941222-15-7 (textbook webpage contains links to the source code of all programs in the text). An eBook of [SMLSW] is available free to all UD students in the library's eContent collection. To access it conduct a search for the title in the library's catalog at library.udayton.edu. Steps to access [SMLSW] off-campus: follow same steps above for accessing [SCMSW] (with the title of this book).

TOC

Course Wordle

CPS 356: Operating Systems/Fall 2018

TOC

Learning Outcomes

TOC

Course Outline

Course outline, required reading assignments, lecture notes, & homeworks & projects:
  1. Introduction to operating systems & the UNIX/Linux & C programming environment ([OSCJ8] Ch 1-2; [LP] Ch 1-5; [USP] Ch 1-2, 4)
    1. introduction to operating systems (review of computer organization, C exercises): Aug 23 28
    2. the UNIX philosophy (class UNIX/Linux page, Linux quick reference sheet, vi quick reference sheet, vi editor, UW vi reference): Aug 23
    3. files & directories (manipulation & management): self-study
    4. system libraries & I/O (C quick reference sheet): Aug 23 28 30 Sep 4 6
    5. compiling C in UNIX (static vs. dynamic linking, macros, conditional compilation, error handling, & debugging; RMS's gdb tutorial, valgrind): Sep 11 13

  2. Processes & threads ([OSCJ8] Ch 3-4; [LP] Ch 6-7; [USP] Ch 2-6)
    1. processes (identification; getpid, creation; fork, & termination): Aug 23 28 30 Sep 4 6 11 13
    2. memory allocation/deallocation: Aug 28 30 Sep 4
    3. (shell) job control (through signals) & terminals: Oct .
    4. storage & linkage classes in C: Sep 13
    5. threads & thread-safe functions (strtok): Sep 11 13
    6. process manipulation (wait): Sep 13
    7. process manipulation (exec & building an argument vector): Oct . .
    8. the Linux shell (Learning the Shell) & process environment (variables, configuration, customization; Advanced Linux quick reference sheet): Oct .
    9. low-level I/O (open & close, & read & write): Oct .
    10. context switching: Oct .
    11. files & directories (data structures, inodes, & hard & symbolic links): value added

    12. Exam I (closed book, closed notes) [practice problems]: Oct 2

  3. Scheduling ([OSCJ8] Ch 5)
    1. types, evaluation criteria, & algorithms (FCFS, SJF, SRTF, RR): Oct .
    2. multi-level queues & multi-level feedback queues: Oct . Nov .

  4. Concurrency and Synchronization ([PG] Ch 7, [SCMSW] Ch 5, & [SMLSW] Ch4)
    1. mutual exclusion & the critical section problem (§§ 6.1-6.4): Nov .
    2. classical problems of synchronization (§ 6.6): Nov .
    3. (cooperative time-sharing) Coroutines in Lua (lua.org homepage & Lua quick reference sheet):
    4. introduction to Go programming (Go by example, a tour of Go, command-line programming with Go, effective Go): Nov .
    5. communicating sequential processes (CSP) (Go/CSP quick reference sheet) in Go ([PG] Ch7): Nov . . . . . Dec .

    6. Exam II (closed book, closed notes) [practice problems]: Oct 30

    7. the Actor model of concurrency in Elixir (elixir-lang.org homepage, Elixir quick reference sheet, & 3-page Elixir summary; [SCMSW] Ch5 & [SMLSW] Ch4): Dec . . .

      Exam III (closed book, closed notes) [practice problems]: Nov 27

  5. Deadlock ([OSCJ8] Ch 7)
    1. deadlock prevention (§§ 7.1-7.4): Nov/Dec
    2. deadlock avoidance & Banker's algorithm (§ 7.5) (Banker's examples): Nov/Dec
    3. deadlock detection & recovery (§§ 7.6-7.8): Nov/Dec

  6. Memory Management ([OSCJ8] Ch 8)
    1. fundamentals (overview of hardware, logical vs. physical address space, dynamic loading & linking) (§§ 8.1-8.2): Dec .
    2. contiguous allocation (§ 8.3): Dec .
    3. paging (§§ 8.4-8.5): Dec .
    4. segmentation (§§ 8.6-8.8): Dec .
    5. segmentation faults & buffer overflows (§§ 8.6-8.8): Dec .

  7. Virtual Memory ([OSCJ8] Ch 9)
    1. demand paging (§§ 9.1-9.3):
    2. page replacement algorithms (FIFO, optimal, LRU; § 9.4):
    3. allocation (§ 9.5) & thrashing (§ 9.6):
    4. course reflection (terms): Dec

  8. Appendices ([LP] Appendices)
    1. Vim quick reference sheet
    2. Linux quick reference sheet
    3. C quick reference sheet
    4. Advanced Linux quick reference sheet
    5. Go quick reference sheet
    6. Elixir quick reference sheet

  9. Final Exam (comprehensive, closed book, closed notes) [practice problems]: Tue Dec 11, 4:30pm-6:20pm, Miriam Hall 203.

TOC

Quick Reference Sheets

TOC

Exams

  1. Exam I (closed book, closed notes) [practice problems]: Oct 2

  2. Exam II (closed book, closed notes) [practice problems]: Oct 30

  3. Exam III (closed book, closed notes) [practice problems]: Nov 27

  4. Final Exam (comprehensive, closed book, closed notes) [practice problems]: Tue Dec 11, 4:30pm-6:20pm, Miriam Hall 203

TOC

Homeworks

Coming soon...


Homework Assigned Due Total points
Homework #1 Aug 30 Sep 6 20
Homework #2 Sep 6 Sep 13 30
Homework #3 Sep 13 Sep 20 40
Total Homework Points: 245

TOC

Homework #1

Assigned: August 30
Due: September 6, 5:05pm

Total points: 20 points

Style guide | Academic Integrity | Evaluation Criteria

[LP] Programming Exercise 4.31.31. (Use filename /home/<logname>/homeworks/hw1/countsubsstdin.c)

TOC

Homework #2

Assigned: September 6
Due: September 13, 5:05pm

Total points: 30 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (20 points) [LP] Programming Exercise 4.31.34. (Use filename /home/<logname>/homeworks/hw2/removesubsargs.c)

  2. (10 points) [LP] Programming Exercise 7.3.19. (Use filename /home/<logname>/homeworks/hw2/alternate.c)

  3. (10 points) Setup your Raspberry Pi according to the instructions here. Then, demo the following to one of the TAs in office hours by or before Thursday September 13:
    1. scp'ing a file from your Raspberry Pi to your SUSE account without using the @ symbol in the command line (this means that the account ids must match).
    2. scp'ing a file from your SUSE account to your Raspberry Pi without using the @ symbol in the command line (this means that the account ids must match).
    3. Running firefox on your Raspberry Pi but displaying the window on your laptop.

TOC

Homework #3

Assigned: September 13
Due: September 20, 5:05pm

Total points: 40 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (20 points) [LP] Programming Exercise 4.31.36. (Use filename /home/<logname>/homeworks/hw3/allsubsargs.c)

  2. (20 points) [LP] Programming Exercise 4.31.38. (Use filename /home/<logname>/homeworks/hw3/parsestring.c)

TOC

Evaluation Criteria

(point values below are approximate)
Component Quantity Points per Total points
Homeworks ~10 varies (33 EC) 245
Midterm Project 1 80 80
Labs
Quizzes
Exams 3 125 375
Final exam (comprehensive) 1 300 300
Total:1,000

Homeworks involves analytical, theoretical, and programming exercises. The programming requires a fair amount of critical thought and design, and approximately 500-1000 lines of code. To prepare students for the realities of computer science problems in industry and graduate school (and beyond) this course encourages (and rewards) self-reliance and independent, self-directed work. Handwritten assignments are not accepted. Assignments are due at 3:35pm in class. Late assignments are not accepted. No exceptions. All exams are in-class, closed-book, and closed-notes. Attendance is mandatory at all examinations; make-ups are not given. Any missed examination will result in a zero. Make no assumptions about anything; always consult the instructor first. Final letter grades of A, A-, B+, B, B-, C+, C, C-, and D start approximately at 93, 90, 87, 83, 80, 77, 73, 70, and 60 percent, respectively.

TOC

Workload

CPS 356 is a challenging course and moves at a very fast pace. Spending a minimum of 9 hours outside of class each week reading, studying, and programming is required. I advise you to see me to discuss any problems you may have before you are evaluated. Having said this, CPS 356 is exciting, fun, and essential. The advent of multi-core processors on the desktop makes mastery of core operating system concepts and concurrent programming more necessary than ever for the modern computer scientist.

TOC

Classroom & Course Policies

Students are expected to conduct themselves with respect, integrity, and virtue. Keep phones and similar devices in a silent mode and put away during class (i.e., out of sight). The use of laptop computers and similar devices is not permitted in class. Audio or video recording of any kind in class is strictly prohibited.

TOC

Academic Integrity

To achieve the course objectives, homework assignments must be a sole result of your work, not be shared with other students, and prepared in accordance with the University Honor Pledge (see below). Moreover, you may not plagiarize code from any, cited or uncited, textbooks, online resources, or other authors. There is no team, group-work assignments in this class. Discussions among classmates must never include pending assignments. No exemptions. All questions and comments about a pending assignment must only be directed to the instructor and teaching assistants. Evidence indicating a violation of this policy will be handled according to the University Academic Honor Code and result in a doubly-weighted zero which will not be dropped (e.g., if the assignment is worth 100 points, you receive a 0/200) or a zero on the next exam. Make no assumptions about this policy; always consult the instructor first. No student should ever feel that they must resort to academic dishonesty. You are encouraged to consult the instructor if you are struggling with the course or an assignment. No grade is worth your integrity. Honesty in your academic work will develop into professional integrity. The faculty and students of the University of Dayton will not tolerate any form of academic dishonesty.

The Honor Pledge as listed in the Academic Honor Code section of the Undergraduate Catalog applies in full to this course.

Honor code FAQ

TOC

Other Helpful ...

Programming style guide

Quick Reference Sheets:
  • Vim quick reference sheet
  • Linux quick reference sheet
  • C quick reference sheet
  • Advanced Linux quick reference sheet
  • Go quick reference sheet
  • Elixir quick reference sheet

  • Practice problems:
    see conceptual and programming exercises in [LP] and [PLCI] (Chapter 14); (outdated, but still relevant) practice problems.

    Grades:
    available in Isidore

    Computer accounts:
    Linux account access | UDit | A beginner's guide to effective e-mail

    Helpful links:
    academic calendar (PDF) | student handbook (PDF) | UDit FERPA policies

    Feedback:
    Dr. Perugini welcomes any feedback you may have on the course motif and approach, style of the lectures, the concepts presented in class, the course webpage, homeworks, projects, deadlines, exams, course and grading policies, or your general experience in the course.

    TOC

    This material is based upon work supported by the National Science Foundation under Grant Number (NSF Grant Number 1712406). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

    Last modified:
    ad majorem Dei gloriam