Description
The Program
Add scheduling for your disk queues, a preemptive history based scheduler for your
ready queue and CPU usage accounting to your OS.
Along with all the information you got in the first program’s SysGen, you should
prompt the installer (me) for the history parameter, α, 0 ≤ α ≤ 1, the initial burst
estimate (the initial value of τ , in milliseconds, for all new processes) and the number
of cylinders each disk has.
This program should do everything your first program did as well as the following:
when an interrupt occurs or a process in the CPU issues a system call the OS (your
program) should query the timer (me) for the amount of time the process has used
the CPU.
The OS should then compute all the appropriate values and implement a
history-based SJF approximation algorithm with τnext = α∗τprevious+(1−α)∗tprevious
(where tprevious is the actual previous CPU burst and τ is the estimated burst). A
call for a disk read or write should prompt for the cylinder to access as well as all the
other information. (Yes, real files on real systems are scattered across many cylinders.
I’m trying to keep this reasonably simple.)
The disk queue should no longer be a FIFO queue, but one ordered so that the
head seek time is minimized while no requests are starved. See “The Paper” for more
details.
An S-{r|c|d|p} should show all the appropriate information well as the total time
each process in the displayed queue has used the CPU, each processes average burst
time and the systems average total CPU time of competed processes. Be sure the
queues are displayed “in order”, that is in the order the processes will be removed
from the queue if no new processes are added. When a process terminates, its PID,
total CPU time, and average burst time are reported to the accounting module (me)
and the system’s average total CPU time is updated.
Email source code and compile instructions before class on the due date. If you
are sending one or two files, there is no need to package them. If you are sending
more than two you should package them. Tar and zip are fine. Please make sure
that the files unpack into the SAME directory the source file is in. Please make sure
you don’t include MACOSX files. If you are sending c++ code, and I can compile it
with g++ -o ~/temp/run.me *cpp then I don’t need a makefile. If you do supply a
makefile, please make sure the output executable is ~/temp/run.me. Also be aware
1
that I will count the readability of your output in the grade.
The Paper
In order to decide on your disk queue scheduling algorithm you will need to do some
research. Your goal is to find a fast algorithm that won’t starve any waiting processes.
Research the known algorithms and write a 500-1000 word paper (2-3 pages, double
spaced, 1 inch margins, 12 point times roman) analyzing the choices and justifying
your choice to implement one of them. I will compare what you choose in the paper to
what you implement in the program, but success in that will only effect your program
grade. This paper will be graded on readability (grammar, sentence and paragraph
structure, understandability) completeness and documentation.
Hand in a printed, stapled document at the beginning of class. No cover or title
pages, but your name should be somewhere. All your work should be documented;
remember that undergraduates may have opinions but are not supposed to know
anything. Fact sources should be referenced. I don’t care if you use foot-notes,
in-notes or end-notes or whether you stick to Chicago, MLA, APA or some other
documentation standard, but all the “right” info has to be in the references and
bibliography. The bibliography does not count to the size of the paper.
2
