Assigned Date: Wednesday, Mar. 30, 2011
Due Date: Wednesday, Apr. 13, 2011
Due Time: 11:50am
Last modified on April 08, 2011, at 03:17 PM (see updates)
NOTE: This homework is an extension of homework 3. Verbiage from homework 3 is included here to make this assignment self-contained. The extension involves adding two more scheduling algorithms (Priority and Round Robin). It also slightly changes the format of the input data.
This is a solo assignment. You must work alone.
This assignment focuses on Process Management with C, and in particular:
- To gain experience with preemptive scheduling algorithms.
- To gain experience with the simulation of I/O- and CPU-bound processes.
Create a process management simulation in C that implements a First-Come-First-Serve (FCFS), Priority, and Round-Robin (RR) scheduling algorithms.
Read in process information from an ASCII file. The name of the file will be provided as input to your
program, using C command-line arguments.
int main(int argc, char *argv)
/* argc equals the number of arguments received
argv is an array containing all command line arguments
argv is set to the name of the program */
For example, see .
The first line of the input file will contain 1 integer, 1 character, and 1 integer values:
- The first value will be used as a seed to the random number generator
srand() (so results can be reproduced),
- the second value will define which scheduling algorithm should be used (FCFS =
'f', Priority =
'p', RR =
- the third will be the quantum (time-slice) value to use for the preemptive algorithms.
You may assume that the first and second values are separated by a single space character.
On each additional line, the input file will contain 4 integers describing a single process to be run:
- The first integer is the process ID,
- the second integer is the arrival time of the process,
- the third integer is the required execution time of the process (remember, we are simulating execution), and
- the forth integer is the probability the process will block for IO.
You should ignore anything past the forth integer on each line. The file may contain an arbitrary number of processes.
Example file contents:
12345 r 5 # seed the random number generator with 12345, and run the RR scheduler with a 5-sec quantum
0 1 4 30 # process ID is 0, arrives at sec 1, will execute in 4 secs, has 30% chance to block for IO
1 3 2 5 # ...
2 6 7 80
You may only assume that processes are sorted by arrival time.
Processes and their related information should be stored in ProcessBlockRecords (PBR) organized as a
queue in order of their arrival time. The PBRs should be represented as C structs, and the queue as a linked list.
Below is an example struct for the PBR. Depending on the scheduling algorithm, your struct may require additional fields (e.g. priority) - be sure to document the rationale for your changes/additions. The same data structure should be used for all three algorithms.
struct PBR *next; /* a pointer to the next PBR in the queue (i.e. linked list) */
To allocate space for the C structs use
malloc(). For example:
struct PBR *head = (struct PBR *)malloc(sizeof(struct PBR));
To deallocate the space use
free(). For example:
Your program should deallocate all the space it allocated. A good strategy is to deallocate the PBR of any process that has completed. Also, depending on how you implement your linked list, you may also use a function called
cleanUp(), which takes as argument(s) the program's dynamic data structure(s). It should be called before the program exits.
Instead of maintaining actual time in your program, you should use a counter and treat every increment
made as the passing of 1 second.
In a real system, each process would perform some sort of work while executing, but, for simplicity,
this simulation will omit this detail.
To simulate IO- and CPU-bound processes, every process is provided with a probability of blocking for IO in the input file. For each unit of time a process is running, a check must be made to see if the process should block.
Again, in a real system, a process that blocks for IO would normally be blocked for some duration while the IO occurs. However, for this assignment, we are concerned only with simulating the blocking of each process. So, for this assignment, you can assume that once a process blocks it can be immediately rescheduled.
To check if a process will block, use the C
rand() function for every unit time that the process is running. For example:
/* map random range to 0 through 99 */
int result = rand() % 100;
/* assuming an IO chance of 30% */
if (result < 30)
/* process blocks and is rescheduled */
/* process keeps running */
/* time is advanced by 1 */
/* ... */
To make sure all executions of your code can be reproduced, make a call to the @srand(seed)@ function near the beginning of your program, where
seed is provided in the input file.
Lastly, you have two options on how to handle arriving processes:
- Either read and schedule processes from the input file one line at a time. That is, once your code has read the first process from the input, do not read in the next process until the current process is ready to be scheduled (i.e., its arrival time <= current time).
- Or, read all the processes from the input file and place them in a temporary queue (ordered by time of arrival). Move processes from the temporary to the ready queue when they are ready to be scheduled (i.e., their arrival time <= current time).
Modularize your design using meaningfully named functions.
For this assignment, you will be implementing three separate scheduling algorithms. The algorithm to be used is indicated by the second integer on the first line of the input file.
Implement the following scheduling algorithms:
- First Come First Serve (FCFS): There will be no time quantum/slice, therefore the implemented algorithm will be non-preemptive.
- Priority Scheduling: The priority for each process will be defined as @1/f@, where @f@ is the fraction of the previous quantum used by that process. For example, assuming a time quantum of @50@, if a process runs for @25@ time units, then its fraction of used time is @25/50 = 1/2@. Hence, the priority of that process becomes @1/(1/2) = 2@ (Note: You should initialize all incoming processes to the highest possible priority, so that every process will run at least once initially.)
- Round Robin: Using the quantum value provided via the input file, implement the Round Robin algorithm.
Upon completion of the simulation, i.e., when all processes have finished executing, your program should output the following statistics:
average wait time: x
average turnaround time: y
average execution time: z
z are float values.
Average wait time: Average (across all processes) of elapsed time between a process' arrival time and the moment it is allocated the CPU.
Average turnaround time: Average (across all processes) of elapsed time between a process' arrival time and its completion.
Average execution time: Average of all the processes' run times.
Follow the Golden Rule of Style: "A program should be as easy for a human being to read and understand as it is for a computer to execute." 
In general, you should comment any variable, obscure statement, block of code, etc. you create.
Also, you should comment why something is being done, e.g.,
numStudents += 1; /* we have processed one more student */
as opposed to how it is done, e.g.,
numStudents += 1; /* increment numStudents by one */
Finally, your code should always include opening comments as follows.
(NOTE: Angle brackets signify information that needs to be filled out. Remove the angle brackets!)
Author: <Your Name(s)>
Email: <Your email address(es)>
Class: CSCI 340, Section 1
Due Date: <The assignment's due date>
Certification of Authenticity <remove one of the following>:
I certify that this lab is entirely my own work.
I certify that this lab is my own work, but I received
some assistance from: <Name(s)>
TASK: <Provide a simple, yet complete description of the task being
performed by this program. It may be several sentences long.>
INPUT: <Describe the input to this program. Be thorough.>
OUTPUT: <Describe the output to this program. Be thorough.>
You will submit your assignment via the stono
submit command, as follows:
% submit csci340 hmwk4 processScheduler.c
No other submission mechanism will be accepted (e.g., email).
Your assignment will be graded based on the documentation, formatting, and correctness of your source code. Also the completeness / thoroughness of your work, and how well you followed the homework instructions.
- Cprogramming.com, Accepting command line arguments, accessed on-line, March 20, 2011.
- Cooper, D. and Clancy, M. (1985) "Oh! Pascal", 2nd ed., W.W. Norton & Company, New York, p. 42.