Spring2012.CSCI340Homework3 History

Show minor edits - Show changes to output

Changed line 2 from:
'''Due Date''': Wednesday, Mar. 28, 2011\\
to:
'''Due Date''': Friday, Mar. 30, 2012\\
Changed line 2 from:
'''Due Date''': Monday, Mar. 26, 2011\\
to:
'''Due Date''': Wednesday, Mar. 28, 2011\\
Changed line 197 from:
where schedule.h contains common data structure and function prototypes '''and definitions''' shared by all programs.
to:
where @@schedule.h@@ contains common data structure and function prototypes '''and definitions''' shared by all programs.
Changed line 195 from:
% submit csci340 hmwk3 fcfs.c sjf.c rr.c srtf.c schedule.h
to:
@@% submit csci340 hmwk3 fcfs.c sjf.c rr.c srtf.c schedule.h@@
Added lines 1-207:
'''Assigned Date''': Wednesday, Mar. 14, 2012\\
'''Due Date''': Monday, Mar. 26, 2011\\
'''Due Time''': 10:50am

Last modified on {$LastModified} (see [[http://www.cs.cofc.edu/~manaris/?n=Spring2012.CSCI340_Homework3?action=diff&source=n&minor=n | updates]])

[--'''NOTE:''' This homework is an extension of [[Spring2012.CSCI340Homework2 | homework 2]]. Verbiage from homework 2 is included here to make this assignment self-contained. The extension involves adding more scheduling algorithms (Shortest-Job-First, Round Robin, and Shortest-Remaining-Time First). It also slightly changes the format of the input data.--]

This is a '''pair-programming''' assignment (i.e., you may work with '''one''' partner). '''You may discuss the assignment only with your partner or the instructor/grader.'''

!!Purpose

This assignment focuses on Process Management with C, and in particular:

* Learn and apply the C programming language for systems development (on Unix environments).
* Understand the concept of process (vs. thread), as well as key elements of process description and control, states, and scheduling algorithms.
** To gain experience with preemptive scheduling algorithms.
** To gain experience with the simulation of I/O- and CPU-bound processes.

!!Assignment

Create a process management simulation in C that implements a '''First-Come-First-Serve (FCFS)''', '''Shortest-Job First (SJF)''', and '''Round-Robin (RR)''', '''Shortest-Remaining-Time First (SRTF)''' scheduling algorithms.

Read in process information from the standard input.

!!!Input

Input has the following format:

(:source lang=c tabwidth=3 -trim:)
2 # CPU quantum (ignored by non-preemptive schedulers)
3 # number of processes to schedule
0 1 4 # first process has ID=0, arrives at second 1, and needs 4 secs of CPU time
1 3 2 # ...
2 6 7
(:sourcend:)

You should ignore anything past the valid data on each line (e.g., comments). The file may contain an arbitrary number of processes.

You may only assume that processes are sorted by arrival time.

!!!Details

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 or an array.

Below is an example struct for the PBR. Depending on the scheduling algorithm, your struct may require additional fields - be sure to document the rationale for your changes/additions. The same data structure should be used for all algorithms.

(:source lang=c tabwidth=3 -trim:)
struct PBR
{
int processID;
int processArrivalTime;
int remainingRunTime;
};
(:sourcend:)

To allocate space for the C structs use @@malloc()@@. For example:

(:source lang=c tabwidth=3 -trim:)
struct PBR *process = (struct PBR *)malloc(sizeof(struct PBR));
(:sourcend:)

To deallocate the space use @@free()@@. For example:

(:source lang=c tabwidth=3 -trim:)
free(process);
(:sourcend:)

Your program should deallocate all the space it allocated.

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.

Modularize your design using meaningfully named functions.

!!!Scheduling

For this assignment, you will be implementing four separate scheduling algorithms (each in its own file).

Implement the following scheduling algorithms:

* '''First Come First Serve (fcfs.c)''': This is a non-preemptive scheduler, so it ignores the time quantum/slice in the input.

* '''Shortest-Job First (sjf.c)''': This is a non-preemptive scheduler, so it ignores the time quantum/slice in the input.

* '''Round Robin (rr.c)''': This is a preemptive scheduler, so it uses the quantum provided in the input.

* '''Shortest-Remaining-Time First (srtf.c)''': This is a preemptive scheduler, so it uses the quantum provided in the input.

Also submit a '''schedule.h''' file with common data structures and function prototypes and definitions.

No global variables allowed. Everything needed by a function should be passed via its parameter list. Functions that make updates, should '''return''' the modified values (so, aim for functions that modify one array, or one variable, at most).

!!!Output

Your program should output the following for each process:

(:source lang=c tabwidth=3 -trim:)
Process n was allocated the CPU at time p seconds.
Process n completed at time q seconds.
(:sourcend:)

where @@n@@, @@p@@, @@q@@ are int values.

Upon completion of the simulation, i.e., when all processes have finished executing, your program should output the following statistics:

(:source lang=c tabwidth=3 -trim:)
Simulation Statistics:

Average wait time: x seconds
Average turnaround time: y seconds
Average execution time: z seconds
(:sourcend:)

where @@x@@, @@y@@, @@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.

So, for the above input example, the output should be:

(:source lang=c tabwidth=3 -trim:)
Process 0 was allocated the CPU at time 1 seconds.
Process 0 completed at time 5 seconds.
Process 1 was allocated the CPU at time 5 seconds.
Process 1 completed at time 7 seconds.
Process 2 was allocated the CPU at time 7 seconds.
Process 2 completed at time 14 seconds.

Simulation Statistics:

Average wait time: 1.0000 seconds
Average turnaround time: 5.3333 seconds
Average execution time: 4.3333 seconds
(:sourcend:)

!!Documentation

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." [1]

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.,

(:source lang=C tabwidth=3 -trim :)
numStudents += 1; /* we have processed one more student */
(:sourcend:)

as opposed to '''how''' it is done, e.g.,

(:source lang=C tabwidth=3 -trim :)
numStudents += 1; /* increment numStudents by one */
(:sourcend:)

Finally, your code should always include opening comments as follows.

(''NOTE:'' Angle brackets signify information that needs to be filled out. In your final assignment, '''remove the angle brackets and the instructions included in them!''')

(:source lang=C tabwidth=3 -trim :)
/*
Author: <Your Name(s)>
Email: <Your email address(es)>
Class: CSCI 340, Section 1
Assignment: HMWK3
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.>

*/
(:sourcend:)

!!Submissions

You will submit your assignment via the stono @@submit@@ command, as follows:

% submit csci340 hmwk3 fcfs.c sjf.c rr.c srtf.c schedule.h

where schedule.h contains common data structure and function prototypes '''and definitions''' shared by all programs.

No other submission mechanism will be accepted (e.g., email).

!!Grading

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.

!!Reference

# Cooper, D. and Clancy, M. (1985) "Oh! Pascal", 2nd ed., W.W. Norton & Company, New York, p. 42.