EECS 2101 Fall 2023 Assignment 2: System for Determining the Average Waiting Times When Three Different CPU Scheduling Algorithms Are Used
EECS 2101 Section E Fall 2023 Assignment 2
System for Determining the Average Waiting Times When Three Different CPU Scheduling Algorithms Are Used
Due Date: Monday November 13, 2023, 23:59. 1. Description of the Assignment
1.1. System for Determining the Average Waiting Times When Three Different CPU Scheduling Algorithms Are Used
You are required to apply the concepts of data structures and algorithms that you have learned in this course to design, analyze, implement, test, and document a system for determining the average waiting times for any given set of processes when each of the following three different CPU scheduling algorithms are used, as described in the material in the textbook by Silberschatz, Galvin, and Gagne mentioned further below:
(1) Preemptive Shortest-Job-First (SJF) Scheduling Algorithm, when the Arrival Time, and Burst Time are given for each process;
(2) Round Robin (RR) Scheduling Algorithm. when the Arrival Time, Burst Time, and Time Quantum are given for each process;
(3) Combined Round-Robin and Priority Scheduling Algorithm, when the Arrival Time, Burst Time, Time Quantum, and Process Priority are given for each process.
1.2. Required Readings
To understand the basic concepts related to CPU scheduling algorithms, you are required to read the material in the book authored by Silberschatz, Galvin, and Gagne, “Operating System Concepts,” Tenth Edition, Wiley, 2018, specified below. (A copy of the specified material in Silberschatz, Galvin, and Gagne’s book can be found in the 2101E F23 eClass file: Operating_System_Concepts_CPU_Scheduling.pdf)
(a) To understand the basic concept of CPU scheduling:
Read Silberschatz, Galvin, and Gagne page 200, first two paragraphs.
(b) To understand the basic concept of Waiting time:
Read Silberschatz, Galvin, and Gagne page 205, 3rd paragraph.
(c) To understand the basic concepts of the Preemptive Shortest-Job-First (SJF) Scheduling Algorithm:
Read Silberschatz, Galvin, and Gagne page 207, 1st paragraph under subsection 5.3.2
“Shortest-Job-First Scheduling” and
page 209, starting from 3rd paragraph, and example of preemptive SJF scheduling.
(d) To understand the basic concepts of the Round-Robin (RR) Scheduling Algorithm: Read Silberschatz, Galvin, and Gagne page 209, the paragraphs under subsection 5.3.3 “Round-Robin Scheduling” and all the material on page 210, including the example of the RR scheduling algorithm.
(e) To understand the basic concepts of the Combined Round-Robin and Priority Scheduling Algorithm:
Read Silberschatz, Galvin, and Gagne pages 211-214, all the material under subsection 5.3.4 “Priority Scheduling”, including the example of the combined round-robin and priority scheduling algorithm starting from the last paragraph of page
213 until the end of the subsection 5.3.4.
(f) You may also take a look at Slide DS.6.33 “Application: Round Robin Schedulers” in the file “DS.6.pdf” posted on 2101E F23 eClass.
1.3. Requirements regarding the design, analysis, implementation, testing, and documentation of the system:
(a) When designing the software to implement the System for Deterministic Modeling of CPU Scheduling Algorithms, you must apply best practice software engineering principles and carefully choose appropriate data structures and methods. Furthermore, in your report/documentation you must justify and explain why you chose each particular data structure and method.
(b) You must analyze the asymptotic run times and space usage of your methods in the report.
(c) You must describe in detail any problems or difficulties that you had encountered, and how you solved or were able to overcome those problems or difficulties in the report.
(d) Additional Requirements:
(d1) You must make sure that your code has very detailed comments.
(d2) You must make sure that your code compiles correctly.
(d3) You must make sure that your code does not generate non-recoverable exceptions.
(d4) You must make sure that your code is able to handle incorrect input.
Failure to satisfy all the requirements above will result in a low mark for the assignment.
2. Platform on Which The System for Deterministic Modeling of CPU Scheduling Algorithms is to be Implemented
The programs should to be implemented using the Java programming language and you should make sure that the TAs/markers will be able to run them on the Red server at York.
3. What to Hand In
3.1. Each group is required to submit an electronic copy of the following to the 2101E
F23
eClass folder titled “2101E F23 Assignment 2”:
1. A written report that identifies and addresses all the important aspects and issues in the design, analysis, implementation, testing, and documentation of the software for the problem described above. The required format of the submitted written report is PDF.
2. The Java source programs.
3. A “Test_output” file containing the output of any testing your group has done.
4. A “README” file explaining how to compile and run your group’s program.
3.2. Each group is also required to use the utility "submit" to submit the electronic
version of the above 3 files to the course directory /cs/course/2101E/submit/a2
on the Red server.
(Please direct all inquiries about how to login to the Red server to the Helpdesk at York University Information Technologies (UIT). Once you have logged into the Red server, in order to learn how to use any command such as “submit” on the Red server, type “man submit”.)
Important Warning:
Only submitting an electronic copy of your group’s assignment to eClass is not enough! If your group fails to use the utility "submit" to submit the electronic version of the above 3 files to the course directory /cs/course/2101E/submit/a2 on or before the due date, your group’s assignment will receive a grade of ‘F’.
4. Evaluation of the Assignment
4.1. The report part of your assignment (60%) will be evaluated according to:
(a) How well you have satisfied the requirements specified in Section 2 above.
(b) How well you have explained the design and implementation of your system and how well you have justified your design decisions.
(c) The quality of your design.
(d) How well you have designed and explained the testing.
(e) The clarity, and readability of the report.
4.2. The program and testing part of your assignment (40%) will be evaluated according to:
(a) The quality of the design and implementation of your programs. (b) The quality of the testing of your programs.
(c) Whether your programs satisfy the Additional Requirements in Section 1.3 (d), (d1)- (d4) above.
5. Resources
5.1. A copy of the material in Silberschatz, Galvin, and Gagne’s book mentioned above can be found in the file on 2101E F23 eClass titled: “Operating_System_Concepts_CPU_Scheduling.pdf”
5.2. A primitive sample java program template, is posted in the file “EECS_2101E_F23_a2_primitive_sample_template.java” on 2101E F23 eClass,
Please note that the ONLY PURPOSE of providing this primitive sample java program template is to provide some hints of what kinds of input data and output data could be involved in the assignment. Your program is NOT required to be the same, or in any way similar to, any elements or parts of this primitive sample java program template, including either the style, or format, or syntax, or code, or data structures, or program organization, etc., of any parts of this primitive sample java program template. Please note that no further explanation regarding this primitive sample java program template will be provided.
5.3. A copy of a set of slides related to the material in Silberschatz, Galvin, and Gagne’s book mentioned above can be found in the file on 2101E F23 eClass titled: “OS-ch5_part_1.pdf”
5.4. A copy of video recordings related to the set of slides in item 5.3 can be found in the files on 2101E F23 eClass titled:
“OS-ch5_part_1.1.mp4,” and “OS-ch5_part_1.2.mp4”
Please note that it is completely up to each individual student to determine whether the items in 5.3 and 5.4 may be useful or not for doing this assignment. Please note that no further explanation regarding the items in 5.3 and 5.4, will be provided.
6. Notes
Please note that the requirements specified in Section 1. Description of the Assignment above, are the minimum requirements that must be satisfied by your assignment. Obviously, there are many other possible details of the System for Deterministic Modeling CPU Scheduling Algorithms that have been left unspecified. It is your responsibility to make appropriate design, analysis, implementation, testing, and documentation choices concerning the unspecified details of the System for Deterministic Modeling of CPU Scheduling Algorithms, and justify those decisions in your group’s report.
Note that although the material in the textbook by Silberschatz, Galvin, and Gagne do not include examples of the Round Robin (RR) Scheduling Algorithm; and Combined Round-Robin and Priority Scheduling Algorithm when Arrival Times are NOT all equal to zero, you should still try to figure out how to correctly handle cases where Arrival Times are not all equal to zero, based on the concepts explained in the material in Silberschatz, Galvin, and Gagne’s textbook (you should first try to get your program to work correctly for the cases where Arrival Times are all equal to zero, before attempting to get your program to work correctly for the cases where Arrival Times are not all equal to zero.)
You need to very carefully read and try your best to fully understand the explanation in the textbook by Silberschatz, Galvin, and Gagne regarding how the various CPU scheduling algorithms work, as no further explanation beyond Silberschatz, Galvin, and Gagne’s textbook will be provided.
In general it is up to each individual student to make his/her individual judgment regarding details that are not explicitly specified above, such as what design, analysis, implementation, testing, and documentation choices should be made; what specific material to include in the report, the length of writing for each specific material/topic in the report, the total length of the report, how to organize and structure the material in the report, ..., etc., and any other possible details about the report.
