Programming Assignment V
Due on Friday, November 20, 2009 @ 11pm
70 points
A Fake CPU Scheduler
In this assignment, you are to write a program, using signals
(and "non-local" gotos if you like), to implement a fake scheduler.
You do not and should not use
ThreadMentor.
The major part of this programming assignment is to implement the following:
- Periodically call one of the several given functions
Each function is assigned a time quantum. Once it is called, it
can use the CPU for that amount of time (i.e., real time rather than
CPU time). The call to these
functions is in a round-robin order. Suppose the time quantum is
set to 1 second and there are three functions,
f1(),
f2() and
f3(). Then,
f1() is called and runs
for 1 second (i.e., real time);
f2() is
called and runs for 1 second;
f3() is called and runs
for 1 second; f1() is called
and runs for 1 second; and so on. The default time quantum value
is 1 second.
- A Ctrl-C handler
This Ctrl-C handler should be
activated when the system detects a
Ctrl-C.
- A Shell
The Ctrl-C handler should transfer
the control to this shell for further processing. Once the shell
is entered, it should display the following prompt:
Shell ->
This shell should start accepting commands until it encounters
e,
E,
r or
R. Each
command starts with a single character and possibly followed by
one or more integers.
- e
or E (exit): Exit the
system. Thus, if a user enters
e
or E,
your program should terminate immediately.
- k
or K (kill): Kill a
function. This command requires a non-negative integer
argument, giving the function ID to be killed.
For example,
Shell -> k 2
Function 2 has been killed.
A killed function should not run again.
If the integer argument indicates a function that
does not exist (e.g., killed previously),
you should display a message. For
example, if function 4 was killed sometime ago,
then
Shell -> k 4
Function 4 does not exist.
- r
or R (resume): Exit
the shell and resume the function that was suspended when the
Ctrl-C
handler took over the control by calling
it again.
However, if this function was killed or suspended, the
shell should call the next "runnable" function in the new order.
This function should receive a full, new time quantum.
If no function is runnable, the shell should print a message
and wait for the next command from the user.
- s
or S (suspend):
This command requires a non-negative integer, giving
the function ID to be suspended. For example,
Shell -> s 2
Function 2 has been suspended.
After a function is suspended, it should not be run
until it is activated again (by command
a
or A).
If the ID gives a killed, a
suspended, or even a non-exist function, you should
display a message:
Shell -> s 2
Function 2 does not exist
Shell -> s 2
Function 2 was suspended
- a
or A
(activate a suspended function): This command also
requires a non-negative integer argument,
indicating the function ID that should be activated.
The function to be activated must be a suspended one;
otherwise, you should display a message:
Shell -> a 2
Function 2 has been activated
Shell -> a 2
Function 2 is not a suspended one.
- o
or O
(change execution order):
This command changes the execution order of functions.
It requires a permutation of integers 1, 2, 3, 4 and 5.
For example,
Shell -> o 3 2 4 1 5
The execution order is now changed to 3 2 4 1 5
If all five functions are currently active, then the
execution (or calling) order becomes
f3(),
f2(),
f4(),
f1() and
f5(). However,
if one or more of these functions
were suspended or killed, the new order assigned to them
is simply ignored. More precisely, if function
f3() was
suspended and
f1() was killed,
then the new execution order is
f2(),
f4() and
f5(). In this
case, your Shell should generate the following message to
inform the user:
Shell -> o 3 2 4 1 5
Function 3 was suspended. Assigned order ignored.
Function 1 was killed. Assigned order ignored.
The execution order is changed to 2 4 5
However, after a suspended function is reactivated after
this change, it should be executed in the given order.
For example, if
f3() is
reactivated sometime later before another reordering, then
the order is
f3(),
f2(),
f4() and
f5().
- t
or T
(set time quantum): This command requires a positive
integer argument, giving the new time
quantum. For example,
Shell -> t 2
Time quantum has been set to 2 seconds
The above sets the time quantum to 2 seconds. Note that
the shell should display a message about this change.
This new time quantum also affects the function
that is suspended due to a
Ctrl-C key press.
An Important Note
Your program may or may not encounter a minor problem when running
on Fedora; however, it is easy to fix if you read some
Unix manual pages. This is an exercise!
|
Bonus Points
Here are two options that can help increase the number of points you can get.
Option 2 includes Option 1 as a subset.
Consequently, you have to figure out how to do Option 1 before thinking
about Option 2.
Option 1:
Study the available signals on Fedora, and you should be able to find
that some signals can be used to stop and continue a process.
Next, write a main() that
includes and compiles funct5.c
into your program.
Then, when your prog5 starts,
it creates five processes, say P1 to P5
so that process P1 calls function
f1(),
process P2 calls function
f2(), etc.
Your shell should use signals to suspend and resume these processes
rather than by calling the functions.
Other than the functions being replaced by processes, the shell should work the
same way.
Option 2:
The core of this option is identical to that of Option 1.
The difference is that each process should run in its own window, while the
shell runs in a shell window.
More precisely, when your prog5 starts,
the shell runs in a window and displays the shell prompt.
Each process will create its own window and use this window for output purpose.
Therefore, there are six windows in total.
In this way, the running activity of each process can clearly be
seen as processes are run in separate windows.
Since your shell runs in a separate window, the resume
(r or R)
command has no effect.
Note that creating text windows is not very difficult as long as you know where
to find the document.
Important Notes
- For both options, all processes and their windows must be
removed when they are killed and upon the exit of the shell.
- A successful implementation of Option 1 receives extra
20 points, and a successful implementation of Option 2
receives extra 30 points.
- You should print the following lines once your program is run so
that our grader would know the option you choose, where
the X is
either 1 or 2, depending on your choice.
********************************
*** Option X for Program #5 ***
********************************
- You should make sure all paths and library search paths are
correct, and should not assume the machine for grading would
have the same path and environment setup like your local machine.
- In your README
file, you should explain your implementation in detail.
Therefore, you are allowed to add one extra page for
this purpose.
|
Input and Output
There is no input file. The output has already been defined in the
funct5.c. There are five C
functions,
f1(),
f2(),
f3(),
f4() and
f5(), each of
which produces its own output. The only output and possible input of your
program are the commands to your Shell as shown in the previous section.
Click here to download a copy of
funct5.c.
Note that you should not change anything in this
file, because the original version will be used for grading.
Program Specification
Please note the following specifications. Without observing these rules,
you may risk lower grades.
- You have to use functions in file
funct5.c for scheduling
purpose. You have to link these functions with your program
files.
- You have to implement all
commands. While your shell is processing command input and
output, all other events (e.g.,
Ctrl-C and alarm) must be
masked off so that the shell will not be interfered.
Since the system may not be able to keep
up with your Ctrl-C
key press, you might want to quickly hit
Ctrl-C a few times.
- Use signal.h and
signal() to catch and
handle signals. Other methods are simply
unacceptable
.
- Feel free to use setjmp()
and longjmp() to switch
back and forth between user functions and your scheduler, although
they really are not needed.
- Use alarm() system call to simulate a time quantum.
Submission Guidelines
- All programs must be written in ANSI C.
Use gcc to compile
your program.
- Use the submit command to
submit your work.
You can submit as many times as you want, but only the last one
will be graded. A makefile is required. Name your executable
prog5.
Please do not submit file
funct5.c, because we may
use a different funct5.c
to test your program.
- I will use the following approach to compile and test your
programs:
make <-- make your program
prog5 <-- test your program
I will supply enough number of commands to test your shell and
run it long enough to see if your scheduler handles
Ctrl-C and alarm correctly.
- Your implementation should fulfill the program specification
as stated. Any deviation from the specification will cause you to
receive zero point.
- No late submission will be graded.
- My rule of grading is subtraction based. I assume you always
receive 100%. If you missed something, some points will be
taken off based on the following rules:
- Your programs must contain enough comments.
Programs without comments or with insufficient
comments will cost you 30%.
- For each program, the first piece should be a program
header to identify yourself like this:
// -----------------------------------------------------------
// NAME : John Smith User ID: xxxxxxxx
// DUE DATE : mm/dd/yyyy
// PROGRAM ASSIGNMENT #
// FILE NAME : xxxx.yyyy.zzzz (your unix file name)
// PROGRAM PURPOSE :
// A couple of lines describing your program briefly
// -----------------------------------------------------------
For each function in your program, include a simple description
like this:
// -----------------------------------------------------------
// FUNCTION xxyyzz : (function name)
// the purpose of this function
// PARAMETER USAGE :
// a list of all parameters and their meaning
// FUNCTION CALLED :
// a list of functions that are called by this one
// -----------------------------------------------------------
Bad programming style and missing headers will cost you 30%.
-
Not-compile programs receive 0 point.
By not-compile, I mean any reason that could cause an
unsuccessful compilation, including missing files, syntax
errors, incorrect makefile and so on. Double check your files
before you submit, since I will
not
change your program to make it work.
-
Compile-but-not-run programs receive no more than 50%.
Compile-but-not-run means you have attempted
to solve the problem to certain extent but you failed to
make it work properly. A meaningless or vague program receives
no credit even though it compiles successfully. Another common
problem is that your makefile could successfully process your
source files (i.e., compiled successfully); but, your
makefile does not generate an executable file with the desired
filename (i.e.,
prog5
in this assignment). If this happens, I will consider your
submission as compile-but-not-run.
-
Programs delivering incorrect result, incomplete result,
or incompatible output receive no more than 70%.
-
All deductions mentioned above are cumulative!
This means that even though you have turned in a correct
program, you could get very low grade. For example, if your
submission does not have the necessary program and function
headings (30% off), does not have enough comments (30% off),
and compiles but not runs correctly (30% off),
then you will receive
70×(100-30-30-30)%=7 points.
- Submit a one-page description of your solution, discussing
the following issues:
- The logic of your program
- Why does your program work?
- You have to describe the use of each signal handler
and the purpose of each
setjmp() and
longjmp()
(if you used these two functions). This part is
extremely
important. If I don't understand it, I will
assume your solution is at best partially correct.
- If your program encountered the minor problem mentioned earlier,
how did you overcome this issue? Provide a detailed account
of your solution.
Name this file README
rather than readme or
Readme.
Note also that there is no
filename extension.
Hence, filename such as
README.TXT
is not acceptable.
README must
be a plain text file. We do not accept files produced
by a word processor. Moreover, watch for very long lines.
More precisely, limit the length of each line to no more than
80 characters with the Return key.
Missing
README costs you 50%,
poorly written README costs
you 30%, and submitting a non-text file costs you 30%.
- Your submission should include the following files:
- File prog5.c
contains your main program and all
functions, signal handlers included.
- File Makefile
is a makefile that compiles the above file and
generates the executable files
prog5.
- File README.
-
Programs submitted to wrong class and/or wrong sections
will not be graded.
-
Always start early, because I will not grant any extension if
your home machine, your phone line or the department machine
crashes in the last minute.
- Since the rules are all clearly stated
above, no leniency will be given. So, if you have anything in doubt,
please ask for clarifications.
-
Click here to see how your
program will be graded.