Spring2012.CSCI340Homework2 History

Hide minor edits - Show changes to output

Deleted line 84:
Deleted line 95:
Deleted line 96:
Added lines 107-123:

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:)
Changed line 45 from:
0 1 4 # first process has ID=0, arrives at second 1, and requires 4 seconds of CPU time to finish
to:
0 1 4 # first process has ID=0, arrives at second 1, and needs 4 secs of CPU time
Changed line 45 from:
0 1 4 # first process has ID=0, arrives at second 1, and will execute in 4 seconds
to:
0 1 4 # first process has ID=0, arrives at second 1, and requires 4 seconds of CPU time to finish
Changed line 2 from:
'''Due Date''': Friday, Feb. 17, 2012\\
to:
'''Due Date''': Monday, Feb. 20, 2012\\
Added lines 163-166:

or as follows (if you include a C header file):

% submit csci340 hmwk2 fcfs.c fcfs.h
Changed line 2 from:
'''Due Date''': Monday, Feb. 20, 2012\\
to:
'''Due Date''': Friday, Feb. 17, 2012\\
Deleted lines 11-13:

* To gain experience using C file I/O, linked lists
* To gain experience with process management
Changed lines 40-42 from:
Each line of the input file will contain 3 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, and the third integer is the required execution time of the process (remember, we are simulating execution). You should ignore anything past the third integer on each line (e.g., we may use this feature to implement input-file comments). The file may contain an arbitrary number of processes.
to:
The first line of the input file contains the number of processes that will be used in the simulation.

Each subsequent line of the input file will contain 3 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, and the third integer is the required execution time of the process (remember, we are simulating execution). You should ignore anything past the third integer on each line (e.g., we may use this feature to implement input-file comments). The file may contain an arbitrary number of processes.
Added line 47:
3 # number of processes to schedule
Changed lines 58-59 from:
queue in order of their arrival time. The PBRs should be represented as C structs, and the queue as a linked list.
to:
queue in order of their arrival time. The PBRs should be represented as C structs, and the queue as a dynamic array.
Deleted line 65:
struct PBR *next; // a pointer to the next PBR in the queue (i.e. linked list)
Deleted lines 67-80:

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

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

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

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

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.
Changed line 102 from:
Process n completed at q seconds.
to:
Process n completed at time q seconds.
Changed line 100 from:
Process n was allocated the CPU at p seconds.
to:
Process n was allocated the CPU at time p seconds.
Added lines 1-190:
'''Assigned Date''': Wednesday, Feb. 8, 2012\\
'''Due Date''': Monday, Feb. 20, 2012\\
'''Due Time''': 10:50am

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

This is a '''solo''' assignment. You '''must''' work alone.

!!Purpose

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

* To gain experience using C file I/O, linked lists
* To gain experience with process management

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

!!Assignment

Create a process management simulation in C that implements a First Come First Serve (FCFS)
scheduler.

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.

(:source lang=c tabwidth=3 -trim:)
int main(int argc, char *argv[])
(
// argc equals the number of arguments received
// argv is an array containing all command line arguments
// argv[0] is set to the name of the program
}
(:sourcend:)

For example, see [1].

!!!Input

Each line of the input file will contain 3 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, and the third integer is the required execution time of the process (remember, we are simulating execution). You should ignore anything past the third integer on each line (e.g., we may use this feature to implement input-file comments). The file may contain an arbitrary number of processes.

Example file contents:

(:source lang=c tabwidth=3 -trim:)
0 1 4 # first process has ID=0, arrives at second 1, and will execute in 4 seconds
1 3 2 # ...
2 6 7
(:sourcend:)

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.

(:source lang=c tabwidth=3 -trim:)
struct PBR
{
int processID;
int processArrivalTime;
int remainingRunTime;
struct PBR *next; // a pointer to the next PBR in the queue (i.e. linked list)
};
(:sourcend:)

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

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

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

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

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.

Simulation time starts at 0 seconds.

In a real system, each process would perform some sort of work while executing, but, for simplicity,
this simulation will omit this.

!!!Scheduling

For now, implement ''First Come First Serve (FCFS)'' to allocate the CPU to the processes. There will be no time
quantum/slice, therefore the implemented algorithm will be non-preemptive.

!!!Output

Your program should output the following for each process:

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

Process n completed at 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.

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

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. '''Remove''' the angle brackets!)

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

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

# Cprogramming.com, [[http://www.cprogramming.com/tutorial/c/lesson14.html | 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.