COP 4600 - Operating Systems, Summer 2000
Project 3 - Minix Process Scheduling
--------------------------------------------------------------------------
PROJECT DUE DATE: July 21st at 2pm
PLEASE NOTE THAT THIS ASSIGNMENT IS DUE AT THE BEGINNING OF CLASS ON
THE DATE STATED ABOVE. YOU MUST TURN IN YOUR PROJECT REPORT AT THIS
TIME. NO PROJECTS SLID UNDER THE OFFICE DOOR WILL BE ACCEPTED.
--------------------------------------------------------------------------
PROJECT DESCRIPTION
--------------------------------------------------------------------------
The purpose of this programming assignment is to learn the concept and
implementation of process scheduling. We will modify and extend the Minix
round-robin scheduling strategy to include priority.
Before beginning this project, it is recommeded that you:
o Perform a minix_backup to save your old project files
o Perform a minix_DESTROY to remove all old Minix files
o Perform a minix_setup to install a fresh copy of Minix
o Read sections 2.5.4 and 2.6.9 of your textbook and examine the code
in /src/kernel/proc.c to fully understand how Minix currently
implements user process scheduling.
The Minix scheduler maintains three queues: TASK_Q, SERVER_Q and USER_Q.
TASK_Q has the highest priority and USER_Q has the lowest priority
(Section 2.5.4 and lines 7177-7306). Tasks in TASK_Q and servers in
SERVER_Q are non-preemptable, while processes in USER_Q are scheduled
using a round-robin mechanism with a time quantum set to SCHED_RATE
(11054).
In this project, we will replace the round-robin USER_Q with a priority
scheduler. That is, the USER_Q will be partitioned into four logical
queues, each with a different priority class. Each priority class has a
priority value ranging from 0 (highest) to 3 (lowest). When picking a
process from the USER_Q, the scheduler chooses the process at the head of
the highest non-empty priority queue. Within each priority class, round-
robin is used with an effective time quantum as follows:
priority 0: one quantum (Minix default)
priority 1: 2x as long as priority 0
priority 2: 4x as long as priority 0
priority 3: 8x as long as priority 0
TASK_Q and SERVER_Q remain unchanged. You are encouraged to use a single
linked list sorted by the priority class to implement the four logical
queues. The effective time quantum can be simulated by giving extra
quanta to processes without changing the basic SCHED_RATE.
Each process begins with the highest priority. Processes that use up all
time quanta alloted to them are reduced to the next lower priority.
Processes that block, and therefore do not use up all time quanta alloted
to them, are promoted to the next higher priority. Any time a process is
placed on a priority queue, it should be placed at the end of that queue
(to implement round-robin within each of the priority classes).
As you may have noticed in this priority scheme, a computation-bound
process will eventually end up in a low priority queue and perhaps will
starve there. Let us extend the above strategy so that such a process can
be reborn again. If a process has not been scheduled to run for more than
10 turns, its priority should be increased to the highest priority and it
should be placed at the end of the appropriate queue. A turn is defined
as how often pick_proc is called, which chooses the process to execute.
To test your solution, it will be necessary to monitor the activity of the
user queue. To achieve this, you must modify the clock routine to display
the user queue every 60 clock ticks. Your printout of the user queue must
include the process PID, number, priority, quanta remaining, and name, and
it must be displayed in order from highest priority to lowest. When the
user queue is empty, you may either display just the header for the user
queue, or display a message stating that the user queue is empty. Here is
an example of what the format of your user queue printout should be like:
PID P_NR PRTY QUANTA NAME
-------------------------------------------------
40 11 0 1 project3
38 9 0 1 project3
39 10 1 2 project3
41 12 3 6 project3
To help you complete this project, here's the complete list of the files
you will either need to modify or create to complete this project:
/src/tools/project3.c (provided below)
/src/kernel/proc.h
/src/kernel/proc.c
/src/kernel/clock.c
==========================================================================
You must do your project independently. No copying of code will be
tolerated. Copying will result in a grade of zero, and will be reported
to the student honor court.
==========================================================================
TEST PROGRAM (project3.c)
--------------------------------------------------------------------------
#include
#include
#include
#define NUM_CHILDREN 10
void keepSpinning();
int main() {
int count, repeat_count, status;
float first, second, third;
long spin[2];
first = 32892.3929;
second = 239233.2933;
count = 1;
while (count < NUM_CHILDREN) {
if (fork() == 0) break;
count++;
}
if (count < 4) {
printf("P%d (%d) spinning...\n", count, getpid());
for (spin[0] = 0; spin[0] < 10000; spin[0]++)
for (spin[1] = 0; spin[1] < 20000; spin[1]++) {
third = first / second;
}
printf("P%d (%d) finished.\n", count, getpid());
return;
}
srand(time(NULL));
for (repeat_count = 0; repeat_count < 5; repeat_count++) {
printf("P%d (%d) spinning...\n", count, getpid());
for (spin[0] = 0; spin[0] < (rand() % 1000) * 1000; spin[0]++)
for (spin[1] = 0; spin[1] < (rand() % 1000) * 1000; spin[1]++) {
third = first / second;
}
printf("P%d (%d) sleeping...\n", count, getpid());
sleep(rand() % 3);
}
if (count == NUM_CHILDREN)
for (count = 1; count < NUM_CHILDREN; count++)
waitpid(-1, &status, 0);
printf("P%d (%d) finished.\n", count, getpid());
}
PROJECT REPORT REQUIREMENTS
--------------------------------------------------------------------------
The report should consist of three parts:
Part 1: Describe any errors in your program and their locations in the
code. This is very important for partial credit. If the program
does not run, your description of the errors may be the only way
to get partial credit. You MUST use the report in conjunction
with the code printout to describe the location of both logical
and/or semantic errors that are stopping the code from running.
If you are unsure what the error is, please state so. If there is
any part of the assignment that you have not completed, please
note so clearly in the report (even if your program runs). If
your program runs perfectly and is complete, then simply note
that.
If we find an error or incomplete program that was not described,
it will result in additional LOST POINTS (not just for the error,
but also for not mentioning it).
Part 2: Provide a printout of your code. It is suggested that you use
the output generated by minix_diff as your code listing.
Part 3: Provide a printout of a sample execution of your program.
To capture the output, use the "script" command as follows:
o Go to your Minix src/tools directory
o Issue the command "script project.out" and press enter
o Run Minix as usual (sunread, execute your program, etc.)
o Exit Minix
o Issue the command "exit" and press enter
This will generate a file in your src/tools directory named
project.out that contains a log of your Minix session.
ADDITIONAL REQUIREMENTS
--------------------------------------------------------------------------
In order to receive full credit for this assignment, you must do the
following (in addition to getting the program working correctly and
writing the report):
You must put your full name and CISE username on the front page of your
report. If you have a cover page, put it on the cover page. If you do
not have a cover page, put it at the top of your report page. In any
event, your name and username must be clearly visible on the front page.
You must compile Minix and your test program prior to the deadline. Your
compiled program should be named 'project3' and your source code should be
named 'project3.c' and both should be placed in your /src/tools directory.
You must comment your code to the extent that someone who is not familiar
with your code can understand what your program does (in other words,
comment everything, and comment thoroughly). It is important that your
code be distinguishable from code previously existing in Minix. You MUST
encapsulate your changes in comments marking the beginning and end of the
changes, such as:
/* BEGIN PROJECT X MODIFICATIONS */ (replace X with project number)
/* END PROJECT X MODIFICATIONS */
Also note that comments in the Makefiles begin with a "#" and extend to
the end of the line. C style comments (/* and */) do not work in
Makefiles. The same is true for assembly files (.s files).
Be cautious of spaces in Makefiles and .s files. Any line that is
indented from the left margin by any amount must be done so using a tab,
not spaces. Also, you may not have any spaces following any lines in a
Makefile. If you get "unexpected end of line" errors in your Makefile, it
means you've got unwanted spaces.
NOTE: Placing comments in the list of object files within a Makefile tends
to cause problems. For example, the following will compile but will cause
problems:
$(LIBRARY)(_pipe.o) \
$(LIBRARY)(_ptrace.o) \
$(LIBRARY)(_read.o) \
$(LIBRARY)(_readdir.o) \
# BEGIN PROJECT 8 MODIFICATIONS \
$(LIBRARY)(_rename.o) \
# END PROJECT 8 MODIFICATIONS \
$(LIBRARY)(_rewinddir.o) \
$(LIBRARY)(_rmdir.o) \
$(LIBRARY)(_setgid.o) \
To avoid these problems, you are not required to comment the lines
of code you add to the list of object files within the Makefiles.
You are, however, required to comment the actual instructions to
compile the files within the Makefiles, like this:
# BEGIN PROJECT 8 MODIFICATIONS
$(LIBRARY)(_getpid.o): _getpid.c
$(CC1) _getpid.c
# END PROJECT 8 MODIFICATIONS
Remember, you must comment your code IN ADDITION to encapsulating your
code in the BEGIN and END comments.
PROJECT UPDATES AND CHANGES
--------------------------------------------------------------------------
From time to time it is necessary to make updates or changes to project
assignments. If this is deemed necessary, the changes will be mentiond
during the next lecture session, emailed to all students on the cop4600
mailing list, and posted on the class web page.
RUNAWAY MINIX PROCESSES
--------------------------------------------------------------------------
PLEASE NOTE: Sometimes Minix will not exit properly and you will end up
with 'runaway' minix processes. This irritates the system group
immensely, and they will begin banning you from CISE machines if you do
not 'clean up' your runaway minix processes. To do this, follow these
instructions:
1) type "ps -u $user"
This will show you all processes you are running on the machine
you are logged into. If you see some listed as 'minix', follow
the next instruction. If there are no 'minix' processes running,
you may safely log out.
2) type "kill -9 "
Where is the PID of the running minix process. It is the
(usually four digit) number in the first column of the ps output.
For example:
> ps -u $user
PID TTY TIME CMD
3010 pts/15 0:01 tcsh
3855 pts/15 0:04 minix
3922 pts/17 0:01 tcsh
> kill -9 3855
Always do this before you log out.
GRADING GUIDELINES
--------------------------------------------------------------------------
1. Report (10%)
Your report must be clear and concise. Points will be deducted for
errors in your program that were not reported or for failure to
include all three parts of the report.
2. Style (10%)
The programming style must show readability of your program. Thus,
it must be well-organized. We'll look for how well you use comments,
how well you modularize the program, how meaningful the use and
naming of constants and variables are, which variables should be
global or local, etc.
When modifying Minix, style is very important. Make your code look
similar to the original Minix code, but add many more comments.
You should use highly visible comments that separate the code you
add to Minix from the pre-existing code, as well as line-by-line
comments describing the code you add (excluding simple statements).
3. Functionality (80%)
It is very important that Minix and your program compile. If they
do not compile without errors, your program will be considered
non-functional.
NOTE: If your program compiles but you did not make an effort to
implement most of the features required, your program is still
incomplete. In other words, turning in a program that technically
compiles but performs none of the functions requested is not
permitted.
If the program compiles but doesn't run we will use the report to
understand the errors and give partial credit.
If your program compiles and runs, we will test it according to the
project description and give you points based on how well you
implemented all that was required.
GRADING DISTRIBUTION
--------------------------------------------------------------------------
This is an approximation of how grades will be assigned. We reserve the
right to change this grading criteria at any time without prior notice.
Report:
correct bug reporting and inclusion of code and sample output 8 pts
placement of full name and CISE username on front page 2 pts
Style:
meaningful variable names, proper use of global/local scope 5 pts
adequate and thorough commenting 5 pts
Functionality:
incrementing priority on block 5 pts
decrementing priority of CPU-bound process 5 pts
quanta reset when placed on queue 5 pts
priority queues in order (highest to lowest) 10 pts
proper handling of multiple quanta per process 10 pts
round-robin preserved within priority queues 10 pts
user queue displayed correctly 10 pts
user queue appears every 60 clock ticks 10 pts
starvation avoidance works properly 15 pts
Other:
failure to compile Minix by deadline -5 pts
failure to compile test program(s) by deadline -5 pts
improper naming of test program(s) -5 pts
HOW TO SUBMIT YOUR PROJECT
------------------------------------------------------------------------
This project is due at the beginning of class on the date given at the top
of this description. You must compile Minix and your test program(s) by
the deadline. Make certain your test program(s) is/are named correctly
(see above). We will archive your Minix directory soon after the
deadline. You must stop work on your project at the time class begins.
We will use a script to check the timestamps on your files.
Additionally, you must turn in your report (described above) by the
project deadline. You must turn in your report to the instructor during
class. Please do not slide projects under the office door.
IMPORTANT: It is important that you do not access your Minix files or
directories after the project deadline until instructed to do
so by the TAs or instructor. All Minix directories will be
archived after the deadline, and we will check file timestamps
to make certain no files were modified after the deadline.