Scheduling Algorithms Are Used
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
EECS 2101
Assignment 2
System for Determining the Average Waiting Times When Three Different CPU
Scheduling Algorithms Are Used
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.