COMP3300 - Operating Systems Assignment 1 2005

COMP3300 – Assignment 1 2005

Updated on Tuesday, 3 May 2005 at 5:01 PM

COURSE PROFILE

LECTURE NOTES

ASSIGNMENTS
First assignment
Second assignment

TUTORIALS

CONTACT
email to
<comp3300@itee.uq.edu.au>
Lecturer
Philip Machanick
<philip@itee.uq.edu.au>

EXAM
TBA

ITEE

Tutors
Timothy Brown <s4006402@student.uq.edu.au>
Richard Woon <woon@itee.uq.edu.au>

What’s New:

Notes on solving the problem and a solution are available.

Results are available.

The count of contents of the data structure was not decremented everywhere it should have been in the deleteFromSchedule function. This should not affect correctness but you can fetch a new version of scheduletypes.c if you want the correction [31 March 2005].

Assignment 1 in 2005 aims to familarise you with different approaches to scheduling by implementing a simulation of a scheduling algorithm.

The example in the file data3 violated requiredment 6.c.i in that the processes did not arrive in the correct order. This has been fixed, as has the corresponding results3 file. If you already have the tar archive, you can just refetch these files.

Handin deadline: 5 April 11:30pm.

Assignment 1 in 2005 covers different ground but this 2004 assignment could provide a useful starting point for understanding C coding.

You should hand in your files via the Online Assignment Submission Service:

for COMP3300
for COMP7303

Assignment 1

The purpose of this assignment is to show your understanding of scheduling and of C programming.

You are required to use existing code as a base for developing a simple simulator to compare various approaches to scheduling (to be covered in week 4).

The intent is that you should work a bit ahead of lectures and therefore understand the concepts better.

The notion is that while working through examples as in the text book is possible in simple cases, it would be useful to automate the process of evaluating alternative strategies.

The provided code gives an example of a first come first served (FCFS) scheduler. You need to implement a shortest job first scheduler simulation. The approach should follow that described in the book in Chapter 6, except you need to take into account arrival time of each process. If a process hasn’t arrived yet in the queue when a scheduling decision needs to be made, it cannot be a candidate for scheduling.

Note that the code includes a command line option to implement a “true” SJF scheduler which uses the burst time after the process finishes its burst to update the value of alpha as defined for exponential averaging. Read ahead in week 4 notes to find out what that is about. You need not implement this feature (the provided example is an illustration of use of command-line parameters in C).

The files you need to get started are in the Files directory. You can also fetch them as a gzipped tar file; to untar it (cd first to the directory where you want to develop your solution):

tar xfzv comp3300-assign1-1.1-2005-files.tgz

This will unpack the tar archive into a directory called Assign1.

Professional Practice

Please do not forget the importance of ethical conduct. If in doubt about whether something constitutes plagiarism or misconduct, please ask.

We will use a plagiarism checker on handed in solutions. Note the basis for assessment on this course which makes it worthwhile to skip an assignment rather than risk a misconduct hearing which may not only result in loss of marks but other potentially serious consequences.

Learning Objectives

You should aim to

achieve reasonable proficiency in C including memory allocation, function pointers and implementation of non-trivial code
understand differences between common scheduling strategies
be able to extend existing C code by adding a new module, without requiring changes to existing code
be able to build on existing code without exploiting features not meant to be for public use (i.e., not published in a header file)

Detailed Requirements

Your program should use the same files as are supplied, and you should only modify the files you are told to modify.
A command line is supplied to compile the program. Whatever development environment you use, your program must compile with the given command line on the student UNIX machines (Solaris). The provided code has been tested on various platforms, but your solution must run on Solaris. To compile the program on Solaris after unpacking the tar archive
cd Assign1 ./compile
Your program should run with the following command:
./scheduler < data
where the file name data can be replaced by any file name where that file contains arrival times of processes as defined below.
The input data to your program should be any number of lines in the following format
process_number arrival_time burst_time
for example (as in the example file data1):
1 0 42
0 10 24
2 11 15
The output of your program should only consist of the output produced by the printf calls in the supplied code; the output should match the examples below.
Your program should be written as follows (data structure design is up to you but you may not assume that contents of .c files are visible – all interfaces to the rest of the program should be through the given header files):
1. implement the functions in sjf.c (as defined by the header file, sjf.h):
  // take inspiration from copyToScheduleList in scheduletypes.c to implement this void copyToSJF (void* destination, unsigned id, unsigned arrival, unsigned burst); // create a new variable of a type defined in sjf.c and return a pointer to it void* initSJF (unsigned size); // this should use the same variable as was created in initSJF void scheduleSJF (void *schedule); // print out contents of the SJF schedule data structure void printSJFSchedules (void *aList);
2. the functions you implement should have the following functionality:
  1. copyToSJF – create a new schedule in a data structure maintaining schedules in an order which facilitates SJF processing: put the result in destination (which should have been created using initSJF); this function is used in a call to copySchedule in the main program. It should do whatever is necessary to add in a nwe schedule consisting of a process id, start time and burst time into the data structure you are using for SJF schedules (which is also passed to copyToSJF).
  2. initSJF – create a new variable to hold SJF schedules and return a pointer to it. You will need to define the actual variable in the sjf.c file (the code is deliberately designed for generality so you can make this any type – hence the use of void* pointers)
  3. scheduleSJF – find the next process to run, remove it from the list, collect stats, print it out with the given printf, and finally print the statistics in the final given printf
3. you may assume that:
  1. schedules are in a reasonable order, i.e., you will not be given start times in a non-increasing order
  2. process ids need not be checked for duplicates
You are supplied with 4 data files for testing, but your final code will be tested with other files.
1. input files are called data1..4
2. result files are called results1..4
3. to compare your results with that against which the code will be tested, e.g., for data1:
  ./scheduler < data1 > myresults1 diff results1 myresult1
4. don’t worry about output which goes to the screen instead of redirecting to the file (from debugging or error messages which go to stderr instead of stdout) unless this output indicates there is an error in your program
5. if your code is OK, diff should terminate without output
You should only modify the following files; all other files will be used unaltered when we test your code:
sjf.c README
If you modify any other files or submit files with different names to these your assignment will be graded as “doesn’t compile”.
In the README file, you should add any comments at the end in the indicated space which will assist the marker in understanding your approach.
Your program should conform to the following formatting requirements:
1. All code at the same level should be left-aligned; an increase of level by introducing “{” should result in an indentation of 2 - 4 spaces; opening a new “{” block should usually be done at the end of the previous line and the closing “}” should be on a line of its own unless readbility dictates otherwise (for example, it is permissiable to write “} else {”); if in doubt ask
2. Type names should start with an initial capital; all other names with an initial lowercase letter. For readability you may use underscores or capitals within a name. (Violations of these guidelines in the given code should not be altered.)
3. Any types or variables specific to one compilable (“.c”) file should appear at the top of the file after the “#includes”.
If in doubt about any formatting requirements, please ask: these guidelines can be extended.
There will be a bonus for early completion: any assignment handed in 24 hours or more before the due date, which achieves at least 50% of available marks, will receive a 5% bonus. The maximum available for the assignment therefore is 105% of available marks. Recall that if you fail to achieve 50% overall for assignments, your exam alone will be used to determine your final grade, but with a maximum grade of 5.

Mark Scheme

If your program fails to compile, it will receive a maximum mark of 40%.
If your program fails to run to completion or has errors in output, it will receive a maximum mark of 50% (after other aspects of the mark scheme are taken into account).
If your program works for a minimal case of the given files, it will receive a maximum mark of 65%.
If your program works in all cases but with obvious inefficiencies, it will receive a maximum mark of 80%.
Marks will be deducted for each of the following, with the maximum set by each of the above criteria:
1. inadequate documentation: code must be explained at the level of each function, as well as high-level design decisions; you should explain the big picture at the end of the given README file
2. deviation from specification (less than the extreme case of failure to compile)
3. clear approach – over and above the documentation, it must be clear what your solution does
4. poor coding style
5. failure to achieve reasonable efficiency
6. use of information hidden in a compilable (“.c”) file
7. incorrect or inefficient use of C language features (e.g., which may lead to future maintenance problems)
Work of no academic merit may achieve a result of 0.

Example of Output

For the example above in file data1, the output should look like this (green text is typed in, red text goes to stderr, and hence will show on the screen not go to the file with a redirect using “>”):

./scheduler < data1 ./scheduler setting exponential averaging to defaults 0.000000 0.500000 about to read schedules: id startime bursttime read schedules: about to use them Schedules in the list id = 1, arrival = 0, burst = 42 id = 0, arrival = 10, burst = 24 id = 2, arrival = 11, burst = 15 process 1 scheduled at time = 0, burst time = 42; waited time = 0. process 0 scheduled at time = 42, burst time = 24; waited time = 32. process 2 scheduled at time = 66, burst time = 15; waited time = 55. 3 processes scheduled, average wait time = 29.000000; total elapsed time = 81. Schedules in the list id = 1, arrival = 0, burst = 42 id = 0, arrival = 10, burst = 24 id = 2, arrival = 11, burst = 15 process 1 scheduled at time = 0, burst time = 42; waited time = 0. process 2 scheduled at time = 42, burst time = 15; waited time = 31. process 0 scheduled at time = 57, burst time = 24; waited time = 47. 3 processes scheduled, average wait time = 26.000000; total elapsed time = 81. ...all done