|
Alan Kaminsky
|
|
•
|
|
Department of Computer Science
|
|
•
|
|
Rochester Institute of Technology
|
|
•
|
|
4486 +
2220 =
6706
|
|
Home Page
|
|
Operating Systems I
|
|
•
|
|
4003-440-02
|
|
•
|
|
Winter Quarter 2012
|
|
Course Page
|
4003-440-02 Operating Systems I
Programming Project 3
Prof. Alan Kaminsky -- Winter Quarter 2012
Rochester Institute of Technology -- Department of Computer Science
Overview
CPU Scheduling Algorithms
Software Requirements
Questions
Submission Requirements
Grading Criteria
Late Projects
Plagiarism
Resubmission
Overview
Write a Java program that simulates different CPU scheduling algorithms.
Use the simulator to discover
which CPU scheduling algorithm
gives the best performance
for different kinds of jobs.
CPU Scheduling Algorithms
You will investigate three CPU scheduling algorithms:
round robin (RR),
highest priority first (HPF),
and multilevel feedback (MLF).
These algorithms are described
on pages 194, 192, and 198, respectively
of the Silberschatz textbook.
The Computer Science Course Library
already has classes for a RR ready queue
(class FifoReadyQueue)
and a HPF ready queue
(class PriorityReadyQueue).
You will write a class for a MLF ready queue.
Your class will be a subclass of class
ReadyQueue.
You will investigate three types of jobs:
Type A, Type B, and Type C.
Each job enters the system at time 0.
Each job, if run all alone, executes for 10,000 seconds.
The jobs differ in their patterns of CPU bursts and blocking times:
-
Type A -- Each job step is 1 second of computation time
followed by 99 seconds of blocking time.
-
Type B -- Each job step is 50 seconds of computation time
followed by 50 seconds of blocking time.
-
Type C -- For the first nine job steps,
each job step is 1 second of computation time
followed by 99 seconds of blocking time.
For the next five job steps,
each job step is 19 seconds of computation time
followed by 1 second of blocking time.
This pattern then repeats until the end of the job.
For HPF scheduling,
all type A jobs have the same priority;
all type B jobs have the same priority;
all type C jobs have the same priority;
all type A jobs have a higher priority than all type B and C jobs;
and all type C jobs have a higher priority than all type B jobs.
You will write a class for each type of job.
Each of your classes will be a subclass of class
Job.
You will write three simulation main programs.
Each main program will simulate a different CPU scheduling algorithm
(RR, HPF, or MLF).
Each main program will run certain numbers of type A, B, and C jobs,
specified on the command line
(possibly a different number of each type of job).
Each main program will print the following statistics:
-
CPU utilization.
-
Mean response time for all the type A jobs.
-
Mean turnaround time for all the type B jobs.
-
Mean response time for all the type C jobs.
You will use your simulation main programs
to answer several questions
about the CPU scheduling algorithms.
To turn in your project,
you will submit your answers to the questions,
and you will submit the source code for four and only four classes:
the MLF ready queue, type A job, type B job, and type C job classes.
These classes must extend the proper base classes
from the Computer Science Course Library,
otherwise they will not compile
and I will not accept your submission.
I will grade your project using my own simulation main programs.
Software Requirements
MLF Scheduling Algorithm
-
The MLF ready queue class must be named MultiLevelFeedbackReadyQueue,
and this class must not be in a package.
Note: Take care to get the capitalization right in the class name,
otherwise your project will not compile when you submit it.
-
The MLF ready queue class must extend class
edu.rit.os1.cpu.ReadyQueue
from the Computer Science Course Library.
-
The MLF ready queue class's constructor must have no arguments.
-
The MLF ready queue class must implement three ready queues
as described in the Silberschatz textbook, page 198.
-
Ready queue 0 must use RR scheduling with a time quantum of 8 seconds.
-
Ready queue 1 must use RR scheduling with a time quantum of 24 seconds.
Note: This differs from the Silberschatz textbook.
-
Ready queue 2 must use FCFS scheduling.
-
If the job running on the CPU came from ready queue 0
and the running job is preempted because its time quantum expired,
the running job must go to the back of ready queue 1.
-
If the job running on the CPU came from ready queue 1
and the running job is preempted because its time quantum expired,
the running job must go to the back of ready queue 2.
-
If the job running on the CPU came from ready queue 1
and a job goes into ready queue 0,
the running job must be preempted,
and the running job must go to the back of ready queue 1.
-
If the job running on the CPU came from ready queue 2
and a job goes into ready queue 0 or 1,
the running job must be preempted,
and the running job must go to the back of ready queue 2.
-
Preemption due to time quantum expiration
must take precedence over
preemption due to another job becoming ready to run.
-
When a job is created,
and when a job that had been blocked becomes ready to run again,
the job must go to the back of ready queue 0.
Type A Jobs
-
The Type A job class must be named TypeAJob,
and this class must not be in a package.
Note: Take care to get the capitalization right in the class name,
otherwise your project will not compile when you submit it.
-
The Type A job class must extend class
edu.rit.os1.cpu.Job
from the Computer Science Course Library.
-
The Type A job class's constructor must have no arguments.
-
A type A job, if run all alone, executes for 10,000 seconds.
-
In a type A job,
each job step is 1 second of computation time
followed by 99 seconds of blocking time.
-
For HPF scheduling,
all type A jobs have the same priority.
-
For HPF scheduling,
all type A jobs have a higher priority
than all type B and C jobs.
Type B Jobs
-
The Type B job class must be named TypeBJob,
and this class must not be in a package.
Note: Take care to get the capitalization right in the class name,
otherwise your project will not compile when you submit it.
-
The Type B job class must extend class
edu.rit.os1.cpu.Job
from the Computer Science Course Library.
-
The Type B job class's constructor must have no arguments.
-
A type B job, if run all alone, executes for 10,000 seconds.
-
In a type B job,
each job step is 50 seconds of computation time
followed by 50 seconds of blocking time.
-
For HPF scheduling,
all type B jobs have the same priority.
Type C Jobs
-
The Type C job class must be named TypeCJob,
and this class must not be in a package.
Note: Take care to get the capitalization right in the class name,
otherwise your project will not compile when you submit it.
-
The Type C job class must extend class
edu.rit.os1.cpu.Job
from the Computer Science Course Library.
-
The Type C job class's constructor must have no arguments.
-
A type C job, if run all alone, executes for 10,000 seconds.
-
In a type C job,
for the first nine job steps,
each job step is 1 second of computation time
followed by 99 seconds of blocking time;
for the next five job steps,
each job step is 19 seconds of computation time
followed by 1 second of blocking time;
and this pattern repeats until the end of the job.
-
For HPF scheduling,
all type C jobs have the same priority.
-
For HPF scheduling,
all type C jobs have a higher priority
than all type B jobs.
RR Simulation Main Program
Note: Since you will not be submitting the source code
for the RR simulation main program,
the main program class name is not specified.
-
The RR simulation main program
must perform a CPU scheduling simulation
using class
edu.rit.os1.cpu.CpuScheduler
and class
edu.rit.os1.cpu.FifoReadyQueue
from the Computer Science Course Library
for the simulator and the ready queue, respectively.
-
The RR simulation main program
must have three command line arguments:
the number of type A jobs,
the number of type B jobs,
and the number of type C jobs.
-
The jobs must be added to the simulation in the following order:
First all type A jobs,
then all type B jobs,
then all type C jobs.
-
The RR simulation main program
must perform a simulation run and print the following statistics:
-
CPU utilization.
-
Mean response time for all the type A jobs.
-
Mean turnaround time for all the type B jobs.
-
Mean response time for all the type C jobs.
-
The RR simulation main program
must use a time quantum of 8 seconds
for the ready queue.
HPF Simulation Main Program
Note: Since you will not be submitting the source code
for the HPF simulation main program,
the main program class name is not specified.
-
The HPF simulation main program
must perform a CPU scheduling simulation
using class
edu.rit.os1.cpu.CpuScheduler
and class
edu.rit.os1.cpu.PriorityReadyQueue
from the Computer Science Course Library
for the simulator and the ready queue, respectively.
-
The HPF simulation main program
must have three command line arguments:
the number of type A jobs,
the number of type B jobs,
and the number of type C jobs.
-
The jobs must be added to the simulation in the following order:
First all type A jobs,
then all type B jobs,
then all type C jobs.
-
The HPF simulation main program
must perform a simulation run and print the following statistics:
-
CPU utilization.
-
Mean response time for all the type A jobs.
-
Mean turnaround time for all the type B jobs.
-
Mean response time for all the type C jobs.
MLF Simulation Main Program
Note: Since you will not be submitting the source code
for the MLF simulation main program,
the main program class name is not specified.
-
The MLF simulation main program
must perform a CPU scheduling simulation
using class
edu.rit.os1.cpu.CpuScheduler
from the Computer Science Course Library
and your class MultiLevelFeedbackReadyQueue
for the simulator and the ready queue, respectively.
-
The MLF simulation main program
must have three command line arguments:
the number of type A jobs,
the number of type B jobs,
and the number of type C jobs.
-
The jobs must be added to the simulation in the following order:
First all type A jobs,
then all type B jobs,
then all type C jobs.
-
The MLF simulation main program
must perform a simulation run and print the following statistics:
-
CPU utilization.
-
Mean response time for all the type A jobs.
-
Mean turnaround time for all the type B jobs.
-
Mean response time for all the type C jobs.
Questions
Answer the following questions.
Put your answers in a plain text file named "questions.txt".
-
(3 points)
If one type A job is executed, what is the CPU utilization?
Give an expression and calculate the answer.
-
(3 points)
If one type B job is executed, what is the CPU utilization?
Give an expression and calculate the answer.
-
(3 points)
If one type C job is executed, what is the CPU utilization?
Give an expression and calculate the answer.
-
(3 points)
Run your three simulation programs with the following job mix:
1 type A job, 1 type B job, and 0 type C jobs.
Give your simulation results in a table like this.
Each number must have two digits after the decimal point.
RR HPF MLF
CPU utilization 0.00 0.00 0.00
Type A mean response time 0.00 0.00 0.00
Type B mean turnaround time 0.00 0.00 0.00
Type C mean response time 0.00 0.00 0.00
-
(3 points)
Run your three simulation programs with the following job mix:
5 type A jobs, 1 type B job, and 0 type C jobs.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
10 type A jobs, 1 type B job, and 0 type C jobs.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
1 type A job, 1 type B job, and 1 type C job.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
5 type A jobs, 1 type B job, and 1 type C job.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
10 type A jobs, 1 type B job, and 1 type C job.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
1 type A job, 1 type B job, and 2 type C jobs.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
5 type A jobs, 1 type B job, and 2 type C jobs.
Give your simulation results in a table as above.
-
(3 points)
Run your three simulation programs with the following job mix:
10 type A jobs, 1 type B job, and 2 type C jobs.
Give your simulation results in a table as above.
-
(3 points)
Based on your simulation results,
which CPU scheduling algorithm results in the smallest response time
for type A jobs?
Explain why.
-
(3 points)
Based on your simulation results,
which CPU scheduling algorithm results in the smallest turnaround time
for type B jobs?
Explain why.
-
(3 points)
Based on your simulation results,
which CPU scheduling algorithm results in the smallest response time
for type C jobs?
Explain why.
Submission Requirements
Your project submission will consist of
a Java archive (JAR) file containing
the "questions.txt" plain text file
plus four and only four Java source files:
-
MultiLevelFeedbackReadyQueue.java
-
TypeAJob.java
-
TypeBJob.java
-
TypeCJob.java
-
Each class must include a Javadoc comment
describing the overall class.
-
Each method within each class
must include a Javadoc comment
describing the overall method,
the arguments if any,
the return value if any,
and the exceptions thrown if any.
See my Java source files which we studied in class
for the style of Javadoc comments I'm looking for.
Put the above listed files into a JAR file
named "<username>.jar",
replacing <username> with the user name
from your Computer Science Department account.
The command is:
jar cvf <username>.jar questions.txt MultiLevelFeedbackReadyQueue.java TypeAJob.java TypeBJob.java TypeCJob.java
Send your JAR file to me by email at
ark@cs.rit.edu.
Include your full name and your computer account name
in the email message,
and include the JAR file as an attachment.
When I get your email message, I will:
-
Extract the contents of your JAR file
into a directory.
-
Delete any files other than the five files listed above.
-
Copy my simulation main program Java source files
into the directory.
-
Set my Java class path
to include the directory where I extracted your files
and the directory where the
Computer Science Course Library
is installed.
-
Compile all the Java source files in the directory
using the JDK 1.6.0 compiler.
I will then send you a reply message
acknowledging I received your project
and stating whether I was able to compile all the source files.
If you have not received a reply
within one business day (i.e., not counting weekends),
please contact me.
Your project is not successfully submitted
until I have sent you an acknowledgment
stating I was able to compile all the source files.
For this project, you are not allowed
to change any files in the Computer Science Course Library.
If your Java classes do not extend and use
the proper Computer Science Course Library classes,
your project will not compile,
and I will not accept your submission.
The submission deadline is Wednesday, February 6
Monday, February 11, 2013 at 11:59pm.
The date/time at which your email message arrives in my inbox
(not when you sent the message)
will determine whether your project meets the deadline.
You may submit your project multiple times before the deadline.
I will keep and grade only your most recent submission
that arrived before the deadline.
There is no penalty for multiple submissions.
If you submit your project before the deadline,
but I do not accept it
(e.g. I can't compile all the source files),
and you cannot or do not submit your project again before the deadline,
the project will be late (see below).
I strongly advise you to submit the project
several days before the deadline,
so there will be time to deal with any problems
that may arise in the submission process.
Grading Criteria
I will grade your project based on the answers
contained in your "questions.txt" file,
45 points total.
For questions 4 through 12,
I will run my simulation main programs,
compiled with your classes,
using the stated job mix for each question.
If my simulation main programs
produce the same output as recorded in your "questions.txt" file,
and if this is the correct output,
the question will get full credit,
otherwise the question will lose credit.
Note that because there are no random numbers in this project,
each simulation run is completely deterministic,
and there is one and only one correct output
for each simulation run.
After grading your project
I will put your grade and any comments I have
in your encrypted grade file.
For further information,
see the Course Grading and Policies
and the Encrypted Grades.
Late Projects
If I have not received a successful submission of your project
by the deadline,
your project will be late
and will receive a grade of 0.
You may request an extension
for the project.
There is no penalty for an extension.
See the Course Policies for my
policy on extensions.
Plagiarism
Programming Project 3 must be entirely your own individual work.
I will not tolerate plagiarism.
If in my judgment
the project is not entirely your own work,
you will automatically receive, as a minimum,
a grade of zero for the assignment.
See the Course Policies for my
policy on plagiarism.
Resubmission
If you so choose,
you may submit a revised version of your project
after you have received the grade for the original version.
You are allowed to make one and only one resubmission of the project.
However, if the original project was not successfully submitted
by the (possibly extended) deadline
or was not entirely your own work (i.e., plagiarized),
you are not allowed to submit a revised version.
Submit the revised version via email
in the same way as the original version.
I will accept a resubmission
up until 11:59pm Friday 22-Feb-2013.
I will grade the revised version
using the same criteria as the original version,
then I will subtract 4 points
as a resubmission penalty.
The revised grade will replace the original grade,
even if the revised grade is less than the original grade.
|
Operating Systems I
|
|
•
|
|
4003-440-02
|
|
•
|
|
Winter Quarter 2012
|
|
Course Page
|
|
Alan Kaminsky
|
|
•
|
|
Department of Computer Science
|
|
•
|
|
Rochester Institute of Technology
|
|
•
|
|
4486 +
2220 =
6706
|
|
Home Page
|
Copyright © 2013 Alan Kaminsky.
All rights reserved.
Last updated 15-Feb-2013.
Please send comments to ark@cs.rit.edu.