✝ JMJ ✝

ad majorem Dei gloriam

CPS 356: Operating Systems

Department of Computer Science, University of Dayton

Fall 2019

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. Perugini, e-mail id: sperugini1, tel: 229-4079, office: AN 145
OHs: M 11:00am-noon & 1:15pm-2:15pm; W 11:00am-noon & 1:15pm-2:15pm; Th 3:30pm-4:30pm (only when classes are in session); & by appointment.
Student Helpers:
Anna Duricy (e-mail id: duricya1) and Kyle Mielke (e-mail id: mielkek1); Miriam Hall 16
OHs: M 5:00pm-7:00pm; T 12:30pm-2:00pm & 3:30pm-5:00pm; W 5:00pm-6:00pm & 7:00pm-8:00pm; Th 12:30pm-2:00pm & 3:30pm-5:00pm (only when class is in session); & by appointment.

TOC

Required Textbooks

    [LCP] Linux and C Programming by S. Perugini. 2019. Draft (Available as a Resource in Isidore).

    [PLCI] Programming Languages: Concepts and Implementation by S. Perugini. 2019. 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 2019

TOC

Learning Outcomes

TOC

Course Outline

(required reading assignments and course notes)
  1. Introduction to operating systems & the UNIX/Linux & C programming environment ([OSC10] Ch 1-2; [LCP] Ch 1-5; [USP] Ch 1-2, 4)
    1. introduction to operating systems (review of computer organization, C exercises): Aug 22 27 29
    2. the UNIX philosophy (class UNIX/Linux page, Linux quick reference sheet, vi quick reference sheet, vi editor, UW vi reference): Aug 22 27 29
    3. files & directories (manipulation & management): self-study
    4. system libraries & I/O (C quick reference sheet): Aug 27 29 Sep 3 5
    5. compiling C in UNIX (static vs. dynamic linking, macros, conditional compilation, error handling, & debugging; RMS's gdb tutorial, valgrind): Aug 27 29 Sep 19

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

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

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

  4. Concurrency and Synchronization ([PLCI] Ch 14; [PG] Ch 7, [SCMSW] Ch 5, & [SMLSW] Ch 4)
    1. mutual exclusion & the critical section problem (§§ 6.1-6.4): Oct 15 17
    2. classical problems of synchronization (§ 6.6): Oct 29 31 Nov 7
    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): Oct 29 31 Nov 7
    5. communicating sequential processes (CSP) (Go/CSP quick reference sheet) in Go ([PG] Ch 7): Oct 29 31 Nov 7 12 14 19 21

    6. Exam II (closed book, closed notes): Nov 5

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

  6. Memory Management ([OSC10] Ch 9)
    1. fundamentals (overview of hardware, logical vs. physical address space, dynamic loading & linking) (§§ 9.1): Nov 26
    2. contiguous allocation (§ 9.2): Nov 26
    3. paging (§§ 9.3-9.5): Nov 26 Dec 3 5
    4. segmentation ([OSC] §§ 8.6-8.8): Dec 3 5
    5. segmentation faults & buffer overflows ([OSC] §§ 8.6-8.8): Dec 5

  7. Virtual Memory ([OSC10] Ch 10)
    1. demand paging (§§ 10.1-10.3):
    2. page replacement algorithms (FIFO, optimal, LRU; § 10.4):
    3. allocation (§ 10.5) & thrashing (§ 10.6):
    4. course reflection (terms): Dec 5

  8. Appendices ([LCP] 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

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

TOC

Evaluation Criteria

(all figures below are approximate, and subject to change within the first few weeks of the course)
Component Quantity Points per Total points
Labs ~10 varies 245 (+33 EC)
Midterm Project 1 80 80
Exams (& Quizzes) 2 ~125 250
Final exam (comprehensive) 1 300 300
Total:875

Labs 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 5:05pm 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 nine 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/lab 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 course. 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

Labs

Lab Assigned Due Total points
Lab #1 Aug 29 Sep 5 20
Lab #2 Sep 5 Sep 12 30
Lab #3 Sep 12 Sep 19 45
Lab #4 Sep 19 Sep 26 20
Lab #5 Sep 26 Oct 1 15
Lab #6 Oct 1 Oct 8 20
Lab #7 Oct 31 Oct 31 15
Lab #8 Oct 31 Nov 5 20
Lab #9 Oct 29 Nov 11 15
Lab #10 Nov 7 Nov 12 10
Lab #11 Nov 12 Nov 14 10
Lab #12 Nov 14 Nov 21 24
Lab #13 Nov 26 Dec 5 34
Total Lab Points (including 33 extra credit points): 245 (+33 EC)

TOC

Lab #1

Assigned: August 29
Due: September 5, 5:05pm

Total points: 20 points

Style guide | Academic Integrity | Evaluation Criteria

[LCP] Programming Exercise 4.31.32. (Use filename /home/<logname>/labs/lab1/countsubsstdin.c)

TOC

Lab #2

Assigned: September 5
Due: September 12, 5:05pm

Total points: 30 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (20 points) [LCP] Programming Exercise 4.31.35. (Use filename /home/<logname>/labs/lab2/removesubsargs.c)

  2. (10 points) [LCP] Programming Exercise 7.3.18. (Use filename /home/<logname>/labs/lab2/alternate.c)

TOC

Lab #3

Assigned: September 12
Due: September 19, 5:05pm

Total points: 45 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (20 points) [LCP] Programming Exercise 4.31.37. (Use filename /home/<logname>/labs/lab3/allsubsargs.c.)

  2. (15 points) [LCP] Programming Exercise 7.5.5. (Use filename /home/<logname>/labs/lab3/mathfib.c.)

  3. (10 points) Setup your Raspberry Pi according to the instructions here (or see the Lab #2 in the Lab Manual posted in Isidore). Then, demo the following to one of the TAs in office hours by or before the deadline:
    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

Lab #4

Assigned: September 19
Due: September 26, 5:05pm

Total points: 20 points

Style guide | Academic Integrity | Evaluation Criteria

(20 points) [LCP] Programming Exercise 4.31.39. (Use filename /home/<logname>/labs/lab4/parsestring.c)

TOC

Lab #5

Assigned: September 26
Due: October 1, 5:05pm

Total points: 15 points

Style guide | Academic Integrity | Evaluation Criteria

(15 points) [LCP] Programming Exercise 7.5.7. (Use filename /home/<logname>/labs/lab5/interface.c.)

TOC

Lab #6

Assigned: October 1
Due: October 8, 5:05pm

Total points: 20 points

Style guide | Academic Integrity | Evaluation Criteria

Complete Lab 13 in the course Lab Manual in Isidore first before starting this lab.

(5+6+6+3=20 points) [OSCJ8] Exercise 5.12 (parts a, b, c, and d) on pp. 235-236, or exercise 5.4 (parts a, b, c, and d) on p. 205 of the 7th ed. Consider the following set of processes, with the length of the CPU burst given in milliseconds:

Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

The processes are assumed to have arrived in the order: P1, P2, P3, P4, P5, all at time 0.

  1. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: First-come, first serve (FCFS), Shortest Job First (SJF), non-preemptive priority (a smaller priority number implies a higher priority), and Round Robin (RR) (with quantum = 1).

  2. Give the turnaround time of each process for each of the scheduling algorithms in part a.

  3. Give the waiting time of each process for each of these scheduling algorithms.

  4. Which of these scheduling algorithms results in the minimum average waiting time (over all processes)?

TOC

Lab #7

Assigned: October 31
Due: October 31, 5:55pm

Total points: 15 points

Style guide | Academic Integrity | Evaluation Criteria

(15 points) Complete Lab 24: Learning Channels & Communicating Sequential Processes (in Go) in the OS Lab Manual posted in Isidore. It is repeated here for convenience.
  1. (7 points) [PLCI] Programming Exercise 14.4.25 as /home/<logname>/labs/lab7/PingPongChain.go. In this exercise, you do not need a channel to synchronize the processes, so do not use one. This exercise is more about learning how to spawn threads than it is about synchronization. However, you must use a channel to keep the main thread alive.

  2. (8 points) [PLCI] Programming Exercise 14.4.21 as /home/<logname>/labs/lab7/PingPongFan.go. This time you must use a wait group to keep the main thread alive.

  3. (10 points extra credit) [PLCI] Programming Exercise 14.4.23 as /home/<logname>/labs/lab7/PingPongFanInOrder.go. Rewrite your program from [PLCI] Programming Exercise 14.3.21 above so that this time the goroutines run in the order they were created.

TOC

Lab #8

Assigned: October 31
Due: November 5, 5:05pm

Total points: 20 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (5 points) [PLCI] Programming Exercise 14.4.30 as /home/<logname>/labs/lab8/HardwareData.go.

  2. (6 points) Complete only activities 1 and 2 in Lab 25: More Channels & Communicating Sequential Processes in the OS Lab Manual posted in Isidore, as /home/<logname>/labs/lab8/producer_n_consumer_m.go.

  3. (9 points) [PLCI] Programming Exercise 14.4.34 as /home/<logname>/labs/lab8/Bakery.go.

TOC

(IoT) Lab #9

Assigned: October 29
Due: November 11, 5:05pm

Total points: 15 points

Style guide | Academic Integrity | Evaluation Criteria

(15 points) Complete the Internet-of-Things Lab 20 (camera sensors; pp. 122-134) in the OS Lab Manual posted in Isidore.

TOC

Lab #10

Assigned: November 7
Due: November 12, 5:05pm

Total points: 10 points

Style guide | Academic Integrity | Evaluation Criteria

(10 points) [PLCI] Programming Exercise 14.4.20 as /home/<logname>/labs/lab10/pingpongonlytwo.go.

TOC

Lab #11

Assigned: November 12
Due: November 14, 11:59pm

Total points: 10 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (5 points from quiz in class on November 14) Read and study [PLCI] §§ 14.4.3-14.4.4 (pp. 797-801). Type out and study the program in Listing 14.9 on p. 801. You task is simply to understand the structure of the program and the data structure being built in main (not the synchronization part of the program) so to be able to answer quiz questions about the structure built in this program in class on November 14. For instance, what is the purpose of the assignment statement on line 50? No need to examine Listing 14.10 on p. 802.

  2. (5 points) [PLCI] Programming Exercise 14.4.29 as /home/<logname>/labs/lab11/FairDiningPhilosophers.go.

TOC

Lab #12

Assigned: November 14
Due: November 21, 5:05pm

Total points: 24 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (12 points) [PLCI] Programming Exercise 14.4.32 as /home/<logname>/labs/lab12/AirTrafficControl.go.

  2. (12 points) [PLCI] Programming Exercise 14.4.36 as /home/<logname>/labs/lab12/H2O.go.

  3. (12 points extra credit) [PLCI] Programming Exercise 14.5.23 (in CSP/Go not Actor/Elixir) as /home/<logname>/labs/lab12/SleepingBarber.go.

TOC

Lab #13

Assigned: November 26
Due: December 5, 5:05pm

Total points: 34 points

Style guide | Academic Integrity | Evaluation Criteria

  1. (3+1=4 points) [OSCJ8] 8.11 on p. 388 (or exercise 8.3 on p. 342 of the 7th ed). Given five fixed memory partitions of 100k, 500k, 200k, 300k, and 600k (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of (p1) 212k, (p2) 417k, (p3) 112k, and (p4) 426k (in order)? Which algorithm makes the most efficient use of memory?

  2. (2+2+2=6 points) [OSCJ8] exercise 8.13 on pp. 388-389 (or exercise 8.5 on p. 343 of the 7th ed). Compare the main memory organization schemes of contiguous-memory allocation, pure paging, pure segmentation, and paged segmentation with respect to the following issues:

    • external fragmentation
    • internal fragmentation
    • ability to share code across processes

    Specifically, complete the following table:
    external fragmentation internal fragmentation sharing code
    contiguous-memory allocation
    pure paging
    pure segmentation
    paged segmentation
  3. (3+3=6 points) [OSCJ8] exercise 8.20 on pp. 389-390 (or exercise 8.9 on p. 343 of the 7th ed). Consider a paging system with the page table stored in main memory.

    1. If a memory reference takes 200 ns, how long does a paged memory reference take?
    2. If we add a TLB, and 75% of all page-table references are found in the TLB, what is the effective memory reference time? You may assume that finding a page-table entry in the TLB takes zero time if the entry is present (an unrealistic assumption).

  4. (2 points) How much total memory is required to store the page table on a computer with a 64-bit logical address space, a page size of 8kB, where each page table entry occupies 8 bytes?

  5. (2+2=4 points) [OSCJ8] Exercise 8.19 on p. 389. Consider a computer system with a 32-bit logical address space and a 4kB page size. The system has 512MB of physical memory. How many entries are there in each of the following?
    1. (2 points) a conventional single-level page table.
    2. (2 points) an inverted page table.

  6. (2+2=4 points) Consider a computer system with a 4-bit logical address space, a page size of 4 bytes, and 32 bytes of physical memory. Translate the following relative addresses (in binary) to physical addresses (in binary). The page table follows.
    1. (2 points) 00011
    2. (2 points) 00110
    0 5
    1 6
    2 1
    3 2

  7. (1+1+1=3 points) Consider a computer system with a 32-bit logical address space, and a page size of 4kB, where each entry in the page table occupies 4 bytes. Since the entire page table will not fit into one page (i.e., 232212 × 22 = 222 > 212 page size), we must page the page table into a two-level page table scheme. So instead of logical addresses being (p, d) pairs, they will be (s, p, d) triples. If we want the inner page table to fit exactly into one page, how many bits of the 32 bits available for a logical address must be allocated for each of the three components to the logical address. To provide your answer fill in the table below.
    section page offset (displacement)
                  bits               bits               bits

  8. (1+1+1+1+1=5 points) [OSCJ8] exercise 8.23 on p. 390 (or exercise 8.12 on p. 344 of the 7th ed). Consider the following segment table:

    segment base length
    0 219 600
    1 2300 14
    2 90 100
    3 1327 580
    4 1952 96

    What are the physical addresses for the following logical addresses?

    1. 0,430
    2. 1,10
    3. 2,500
    4. 3,400
    5. 4,112

TOC

Midterm Project

Assigned: September 26
+20 points Extra Credit Due: October 17, 5:05pm
Due: October 29, 5:05pm

Total points: 80 points

Isidore | Style guide | Academic Integrity | Evaluation Criteria

Problem

Design and implement a program (in any language) that simulates some of the job and CPU scheduling of a time-shared operating system.

Detailed Description and Requirements

When jobs initially arrive in the system, they are put on the job scheduling queue which is maintained in FIFO order. The job scheduling algorithm is run when a job arrives or terminates. Job scheduling allows as many jobs to enter the ready state as possible given the following restriction: a job cannot enter the ready state if there is not enough free memory to accommodate that job's memory requirement. Do not start a job unless it is the first job on the job scheduling queue. When a job terminates, its memory is released, which may allow one or more waiting jobs to enter the ready state.

A job can only run if it requires less than or equal to the system's main memory capacity. The system has a total of 512 blocks of usable memory. If a new job arrives needing more than 512 blocks, it is rejected by the system with an appropriate error message. Rejected jobs do not factor into the final statistics (described below).

Note that all jobs in the ready state must fit into available main memory.

Process scheduling is managed as a multilevel feedback queue. The queue has two levels, each queue is organized as a FIFO, and both use a round robin scheduling technique. New jobs are put on the first level when arriving in the ready state. When a job from the first level is given access to the CPU, it is allowed a quantum of 100 time units. If it exceeds that time quantum, it is preempted and moves to the second level.

The jobs on the second level may only be allocated the CPU if there are no jobs on the first level. When a job on the second level is given access to the CPU, it is allowed a quantum of 300 time units. If it exceeds that, it is preempted and put back on the second level of the ready queue.

Process scheduling decisions are made whenever any process leaves the CPU for any reason (e.g., expiration of a quantum or job termination). When a job terminates, do job scheduling first, then process scheduling. Also, give preference to first level jobs (i.e., if a job from the second level of the ready queue is running, and a new job enters the first level, the running job is preempted to the second level in favor of the first level job).

While executing on the CPU, a job may require I/O, which preempts it to the I/O wait queue for the duration of its I/O burst.

When a job completes, put it on a finished list for later processing.

The simulator is driven by the events read from standard input. Examples of possible events are given below. The first field will be the first character of the line, and subsequent fields will be separated by one of more spaces or tabs. The header of each field in the following examples does not appear in the input stream.

A new job arrives:

Event Time Job Memory Run Time
A     140  12  24     2720

Interpretation: job 12 arrives at time 140, requires 24 blocks of memory and uses the CPU for a total of 2720 time units.

A job needs to perform I/O:

Event Time I/O Burst Time
I     214  85

Interpretation: the job currently running on the CPU will not finish its quantum because at time 214 it needs to perform I/O for a duration of 85 time units.

Display the status of the simulator:

Event Time
D     214

Interpretation: display the status of the simulator at time 214.

You may assume that events appear on the input stream in ascending time order. However, realize that the events given in the input stream are not only events which your simulator must handle. For instance, a time quantum expiration is not an event given in the input stream, but it is an event which your simulator must handle. Furthermore, an internal event, such as a time quantum expiration, not in the input stream, may occur at the same time as an event in the input stream (e.g., a new job arrival). Events in the input stream are external events.

The following is a list of internal events (i.e., not given on the input stream) which your simulator must handle:

Assume that context switching and displays take no simulator time (an unrealistic assumption in a real operating system).

When a display is requested, print the contents of all queues as well as the job currently running on the CPU to standard output using only the format used in the sample output given below.

After processing all jobs, write the following to standard output (in this order, as shown on the sample output given below):

  1. completion time for each job (in order of completion),
  2. average turnaround time (where turnaround time is defined as completion time minus arrival time), and
  3. average job scheduling wait time (where wait time is defined as the number of time units spent in the job scheduling queue).

Event Collisions

Often more than one event happen at the same time. Use the following rules to determine which events to process first:

Architectural View of the Simulator

Additional Requirements

  1. Your system must be developed and run on your Raspberry Pi. Multiple programming languages are available on the Pi (C, C++, Java, Python, Perl, Go, etc.) through sudo apt-get install.
  2. Your implementation must be distributed across more than one source code file, in some sensible manner which reflects the logical purpose of the various components of your design, to encourage problem decomposition and modular design.
  3. Include a README file in your submission which describes (i) the language you used to develop your program and (ii) the name of the compiler or interpreter which you used to compile or interpret your program.

Hints and notes

Test data: sample input and output streams

  1. (only events A & D, & E & T) p2stdin_a and p2stdout_a [image]
  2. (all events A, I, & D, & E, C, & T) p2stdin_b and p2stdout_b [image]

This test data is available at /home/perugini_cps356/share/project/. At first, simply try to get only one job through your system; see the test file /home/perugini_cps356/share/project/testdata/one.txt. Once you are confident that your system processes only one job properly, try to get two jobs through the system; see the test file /home/perugini_cps356/share/project/testdata/two.txt

While developing your simulator, you are encouraged to get it to work on the simple test input first (p2d.dat) and progressively enhance and refine your system to the point where it works on the most complex test input (p2a.dat).

Use the Linux diff utility to compare your output to the correct output. For full credit, the output produced by your program must have zero differences, as defined by diff, with the output posted here.

There is also a reference executable of a solution for this project available at /home/perugini_cps356/share/project/OSsim

.

How to submit

Note: All directory and filenames below are case-sensitive. You must use the directory and filenames exactly as shown below, (i.e., all lower case).

Prepare your submission file as /home/<logname>/project/project.tar. This archive must contain only the most minimal set of files necessary to build your simulator from scratch. Only the file /home/<logname>/project/project.tar will be electronically collected from your account on the deadline.

Failure to follow these submission requirements will result in a 10% penalty.

FAQ

  1. How do a create my tar file?
      The requirements require you to make a .tar and place it in /home//project/project.tar. A tar file is a single file that contains a packaged up files and/or directories. The command to make a tar file on UNIX systems (Mac OS X and Linux) is as follows:
      tar cvf project.tar <directory_with_code>
      
      or
      tar cvf project.tar <list of source code files>
      
      Be very careful to ensure the file name after the cvf is the name of the tar file. If you run the command as follows, you will overwrite one of your source files!
      tar cvf Main.java Scheduler.java Types.java
      
      The command to untar a tar file is as follows:
      tar xvf project.tar 
      
      This will create the directory structure with all the files indicated by project.tar.

  2. I developed my project on Windows using and IDE. What should I do?

      Some of you may work locally on your personal computer in some IDE. To upload your code from your computer to the suse server you can either copy and paste the contents of a file into a file on the server or you can use a secure copy program.

      To transfer files to and from your account, use a secure file transfer program such as FileZilla. You can also use PSCP or PSFTP available for free download from the PuTTY Download Page. You can use pscp.exe or psfpt.exe.

      For Windows users you will need to download pscp or psfpt.exe. You will need to have the pscp.exe or psftp.exe in your CMD path (system environment variable PATH) or in your current working directory for this command to work or you will have to specify the path to pscp in the command (C:\putty\pscp.exe for example). Below is an example of the command:

       
      pscp.exe -r <path_to_local_directory_with_code> <logname>@cpssuse04.cps.udayton.edu:/home/<logname>/project/
      

      For Mac OS X and Linux users, there is a command built into your terminal called scp (for secure copy. The format of this command is:

      scp -r <path_to_local_directory_with_code> 
      <logname>@cpssuse04.cps.udayton.edu:/home/<logname>/project/
      

      Lastly, it is strongly recommended that you make multiple copies of your project. This will allow you to revert changes if something accidentally gets overwritten.

Evaluation

Ninety percent of your score will come from correctness and 10% of your score will come from following our programming style guide. Applicable submission penalties will then be applied.

In an effort to award partial credit to students who are unable to complete certain parts of this project, students earn up to two different portions of the 70 possible points for correctness:

Note: Depending on how you order the jobs on your I/O wait queue, your dump of the jobs waiting for I/O may not match our output exactly, and for just that queue, that is acceptable. For instance, you might organize your I/O wait queue as a priority queue where the job which comes off first is at the head, or you might maintain jobs on the I/O wait queue in the order in which they are put on and then search for the job to take off when the I/O is complete.

TOC

Exams

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

  2. Exam II (closed book, closed notes): Nov 5

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

TOC

Quick Reference Sheets

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
  • Lua quick reference sheet

  • Practice problems:
    see conceptual and programming exercises in [LCP] 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 | 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, labs, 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

    ✝ JMJ ✝