Overview
This assignment is related to process scheduling. We will finish
discussing the material you will need to understand this assignment by
the third week of the semester.
Do not wait until then to start this assignment.
The first two parts of the assignment will
be described in abstract terms so you can do these part without understanding
process scheduling.
In each part of the assignment you will be given an input sequence of exactly 7 integers. From this you will produce two output strings consisting of the letters R, w and r. You will also produce two integer values giving the number of times r occurs in the first string and the number of times r occurs in the second string. Lastly you will produce two floating point numbers. The first of these is the average of the two output integers and the second is the total number of R's in the two strings divided by the length of the longer string.
You will write a single C program that takes the 7 input values as
command line parameters. The program should start by checking that there
are exactly 7 parameters and exit with an appropriate
error message otherwise. If the number of command line parameters is
correct, the program will print your name on a line in the form:
Assignment 1 program was written by ...
and then output 7 input values.
For each part you will display 5 additional lines:
a blank line, a heading, the two output strings (the second
directly under the first) and the four numeric values.
Produce a single makefile for compiling all of the programs in this assignment. A sample makefile can be found here.
In writing your programs, following the programming style guidelines here.
Make sure you understand the statement of the each part before writing any code for that part. For each part you will be given information about how to produce the output from the input sequence.
You will run the program with appropriate input of your choosing to test to see of it is working. Save the output generated to be handed in with your assignment.
You will produce two source files, assign1.c and pslibrary.c. The first will contain your main program. The second will contain functions implementing most of the assignment. In each part you will add to the source files keeping the previous capabilities.
Part 0:
This is just to get you started. You do not have to hand in anything for
this part for Assignment 1, but you will be sending me an email with the output
generated as part of Assignment 0.
Create a directory called assign1 for this assignment.
Write a main program called assign1.c.
This program takes exactly 7 integer command line parameters.
It should check for the correct number of command line parameters,
assume that all are integers, print a line containing your name and
a line containing the values of the parameters.
The output should be in the form:
Assignment 1 program was written by S. Robbins
inputs: 0 1 2 3 4 5 6
If the number of parameters is incorrect, print an appropriate message
and exit.
The main program should then create two arrays of characters that will be
large enough to hold the character string you will be creating.
The maximum size of any of the strings will be the sum of the last six
command line parameters. If an error occurs in creating these arrays,
exit the program with an appropriate error message. Otherwise call two
functions, one to create the strings and one to print them out as follows:
void part0(char *s1, char *s2);
void display(char *heading, char *s1, char *s2);
These two functions should be put in the file pslibrary.c. Put prototypes for these in pslibrary.h and have assign1.c include pslibrary.h.
For this part of the assignment use the heading: "Part 0\n". The part0 function will just copy the following strings into the two parameters: RRwwwwwRRRRRRRRR and rrRRRRwwwwwwwwrrRRRRRRR and return. Note that part0 ignores all of the command line parameters.
The display function that you write for this part will be used for all of the rest of the parts of this assignment. The display function prints only to standard out and does the following:
Part 1:
Write a function in pslibrary.c called fcfs that
takes two string parameters and 6 integer parameters.
It fills in the strings for the first two
parameters as described as follows. Suppose the function is called with
fcfs(s1, s2, x1, y1, z1, x2, y2, z2);
The first string, s1, will consist of a x1 R's,
followed by y1 w's, followed by 0 or more r's, followed by
z1 R's.
The number of r's will be described later.
The second string, s2, will be consist of x1 r's, followed by x2 R's, followed by y2 w's, followed by 0 or more r's, followed by z2 R's.
The number of r's in each string will be the minimum value that makes the strings satisfy the following conditions:
Example 2:
With the input sequence: 0 4 11 5 6 3 7
the output generated by display should be:
RRRRwwwwwwwwwwwrrrrrRRRRR
rrrrRRRRRRwwwRRRRRRR
5 4 4.5 0.88000
Example 3:
With the input sequence: 0 4 9 5 6 3 7
the output generated by display should be:
RRRRwwwwwwwwwRRRRR
rrrrRRRRRRwwwrrrrrRRRRRRR
0 9 4.5 0.88000
Problem description in terms of process scheduling
Consider two processes, each with two CPU bursts with one I/O burst in between.
Process 1 has a CPU burst of x1 units followed by an I/O burst of
y1 units followed by a second CPU burst of z1 units.
Process 2 has a CPU burst of x2 units followed by an I/O burst of
y2 units followed by a second CPU burst of z2 units.
Suppose that Process 1 arrives in the ready queue just before Process 2
and just after Process 2 arrives the process that was in the CPU terminates.
No other processes are in the system. For each of the scheduling algorithms
draw a Gantt charts showing the state of each of the two processes.
Use the letter R to represent the running state, the letter w for the
waiting state and the letter r for the ready state.
Calculate the two waiting times, the average waiting time and the CPU
utilization. (Break any ties by having process 1 run first.)
Part 1 describes the FCFS algorithm, where the last 6 input parameters are x1, y1, z1, x2, y2, and z2. The numbers displayed are the waiting times for process 1 and process 2, the average waiting time, and the cpu utilization.
Part 2
Make sure you have read the entire assignment before starting this part.
Implement the SJF algorithm (non-preemptive). Again, ignore the first input
parameter. Do this by putting the function:
sjf(char *s1, char *s2, int x1, int y1, int z1, int x2, int y2, int z2);
in pslibrary.c. Add two lines to assign1.c to call this and
display. Use the heading: "SJF\n".
Part 3
Implement the PSJF algorithm. That is, write the function:
psjf(char *s1, char *s2, int x1, int y1, int z1, int x2, int y2, int z2);
and add two additional lines to assign1.c.
Part 4
Implement the Round Robin algorithm.
Tha is, write the function:
rr(char *s1, char *s2, int q, int x1, int y1, int z1, int x2, int y2, int z2);
In this case the first input parameter is the quantum
and the others will be as before.
Test your program with inputs you have developed. Collect the tests and print them out. Make sure they are labeled so that it is easy to tell what tests were performed and whether or not they worked. Include these with your assignment. Put the starting page number on the cover sheet under Your test output pages.
Then run the program with each of the following three tests. For each, save the output in a file and print the output, each on a single page. Label each one as Test 1, Test 2, or Test 3.
Test 1: 3 8 7 3 6 3 2.
Test 2: 3 8 7 3 6 7 2.
Test 3: 4 8 7 3 6 1 2.
This will be turned in with your assignment. Put the page number of each of
these on the cover sheet under Final test output 1, etc.
Use this cover sheet for handing in your assignment.
Assignments are due at the start of class on the due date.
Note: The first three parts can be implemented in a simple way, but you will have trouble with Part 3 and Part 4 if you do not think in terms of a state machine. If you implement Part 2 as a state machine, one a minor change will be necessary for Part 3. Similarly, if you implement Part 1 as a state machine, Part 4 will require a minor modification. If you do not understand how to program a state machine, be sure to ask someone.