FIT2100 Operating Systems
Assignment #2
Process scheduling simulator
Daniel Kos
Lecturer, Faculty of IT.
Email: [email protected]
c© 2010-2019, Monash University
September 19, 2019
c© 2019, Faculty of IT, Monash University
1 Introduction 2
1 Introduction
Aim
In this assignment, you will create programs to simulate two different scheduling algorithms.
You will not be doing scheduling of real processes, however your program will determine the
sequence in which a certain number of ‘imaginary’ processes are to be executed.
This document constitutes the requirement specification for this assignment. You will be
assessed on your ability to both comprehend and comply with the requirements as specified
herein.
Due: 14th October 2019 (Monday) 11am.
Late submissions: A late submission penalty of 5% of assignment total per day will apply.
No submissions will be accepted after 25th October 2019 (end of semester 2) except in
exceptional circumstances.
This assignment is worth 15% of the total marks for this unit.
2 About the ‘processes’
We will use a simplified model of a process. Each process has a pre-defined total service time.
Our processes do not use I/O and can never be in a blocked state.
Each process should be represented within your program as a process control block instance
defined as follows:
/∗ S p e c i a l enumerated data t y p e f o r p r o c e s s s t a t e ∗/
t y p e d e f enum {
READY, RUNNING , EXIT
} p r o c e s s s t a t e t ;
/∗ C data s t r u c t u r e used as p r o c e s s c o n t r o l b l o c k . The s c h e d u l e r
∗ s h o u l d c r e a t e one i n s t a n c e p e r r u n n i n g p r o c e s s i n t h e system .
∗/
c© 2019, Faculty of IT, Monash University
3 About the program output 3
t y p e d e f s t r u c t {
c h a r p r o c e s s n a m e [ 1 1 ] ; // a s t r i n g t h a t i d e n t i f i e s t h e p r o c e s s
/∗ Times measured i n s e c o n d s . . . ∗/
i n t ent ryTime ; // t ime p r o c e s s e n t e r e d system
i n t s e r v i c e T i m e ; // t h e t o t a l CPU t ime r e q u i r e d by t h e p r o c e s s
i n t remain ingTime ; // r e m a i n i n g s e r v i c e t ime u n t i l c o m p l e t i o n .
p r o c e s s s t a t e t s t a t e ; // c u r r e n t p r o c e s s s t a t e ( e . g . READY ) .
} p c b t ;
You may modify this struct definition to include additional process information if you wish.
2.0.1 To ‘run’ a process
Our processes have state information, but no program code to be executed! Therefore, to
‘run’ a process for one unit of time, your program should simply sleep for one second (or the
amount of time until the state of the system changes).
(Although we don’t have real processes to run, it makes sense that the scheduler would be
sleeping while the scheduled process is ‘running.’)
3 About the program output
In the lecture on I/O, two types of terminal device (both line-based and form-based) were
mentioned. Up until now, you have been printing to a line-based terminal, but this is not the
only possible target for standard output!
In this assignment, you will use a form-based terminal to display the process scheduling chart
graphically. Your VM environment includes such a system known as ioL.
ioL makes use of markup instructions (similar to HTML1) to interpret how to display content
on the screen. To save you having to learn ioL’s markup language yourself, a small ‘library’
of four functions has been provided for this assignment. These are provided in the files:
process-visualiser.h and process-visualiser.c. You should include these files in
1Unlike HTML which was designed for one-way transmission of a web page to a web browser, ioL is designed
for synchronous communication between the program and the user.
c© 2019, Faculty of IT, Monash University
3 About the program output 4
your submission. You are free to modify these functions if desired, but do not move the
functions out of the files provided.
The functions allow you to plot bar segments on the screen, with one row for each process.
Bars can be dotted (for processes in the ready state/waiting) or solid (for the currently running
process).
Figure: Sample output for a particular data set. (Note: the use of colors, captions, etc. is up
to your own design preference.)
• void initInterface(const char* backgroundColor, const char* foregroundColor)
— call this function first to set up the user interface before you produce other output.
c© 2019, Faculty of IT, Monash University
3 About the program output 5
• int appendRow(const char* processName) — use this to add a row to the chart
representing a process in the system. Returns an index number for the new row.
• int appendBar(int rowIndex, int length, const char* color, const char*
caption, int dotted) — adds a bar of activity to the end of the specified row.
• void appendBlank(int rowIndex, int length) — adds a blank space to the end
of the specified row (e.g. process has not arrived in the system yet).
• void waitExit() — keeps the window open until the user decides to exit.
For instructions on using these functions: read the comments in the process-visualiser.h
header file.
You can also choose what color to make each bar segment, and specify a caption (string of
text) to be displayed when the user moves the mouse over a bar. These design choices are up
to you.
Printing text output in the form-based terminal
During the simulation, you should print information about how the state of the system has
changed (e.g. ”Process A now running.”). To print output, simply use the printf() function
(or write to standard output in whichever way you prefer).
However: note that ioL uses the following characters for markup instructions.2 If you print
them in your output, you may get strange results.
< > { }
Also note that the ioL console produces new-lines in a different way to the regular line-based
terminal. To produce a newline, print the “” character sequence (instead of the regular
\n):
p r i n t f (” H e l l o w o r l d !”);
/∗ This t e r m i n a l r e q u i r e s a d i f f e r e n t n e w l i n e s e q u e n c e . ∗/
2 For more information about ioL’s markup syntax (e.g. for printing text in bold or italics), refer to the
online documentation at: http://doc.iol.science – however this is not required for this assignment.
c© 2019, Faculty of IT, Monash University
3.1 Running the program in the form-based terminal 6
3.1 Running the program in the form-based terminal
When you try to run your program in the normal terminal environment, you may see weird
markup code in the terminal. To run your program in the ioL terminal environment (to see
the output displayed correctly), place ‘iol -- ’ in front of the command.3 For example:
i o l −− . / y o u r p r o g r a m arg1 arg2 . . .
4 If you require extra help
If you are stuck knowing where to begin, refer to the helpful hints in section 8.
This assignment is an independent learning and assessment exercise.
You may utilise the student forums to ask questions and obtain clarification, however you may
not share details or code in your implementation with other students, nor may you show your
code to the teaching team prior to submission. This is an assessment task: tutors and lecturers
are not permitted to help you debug your assignment code directly (you are expected to debug
and test your own code), but can help with more general queries, such as queries related to C
programming syntax, concepts and debugging tips.
You may make use of online references with appropriate citation in accordance with academic
integrity policies, however your work must be your own.
5 Task 1: non-preemptive scheduling
Choose one of these scheduling algorithms to implement.
• FCFS (First come, first served)
• SPN (Shortest process next)
Write a scheduling simulator for your chosen algorithm as described above.
3Due to a known issue in our Virtual Machine environment, ioL may glitch-out the very first time you run
it. In this case, press Ctrl+C in the bash window and try again.
c© 2019, Faculty of IT, Monash University
5 Task 1: non-preemptive scheduling 7
Your main C source file should be named with your student ID as: non-preempt-123456789.c,
where 123456789 is your student ID.4
Your program should take a filename as its only argument. If no argument is specified, use
the default filename process-data.txt.
Each line in the process data file (process-data.txt) should contain space-separated values
for a single process as follows:
[ p r o c e s s name ] [ a r r i v a l t ime ] [ s e r v i c e t ime ]
For example:
P1 0 3
P2 1 6
P3 4 4
P4 6 2
Times are measured in seconds. In the above file, the process named P1 enters the system at
time: 0 seconds, and has a total required service time of 3 seconds, and so on. You cannot
assume that the entries will be listed in order of entry time. You can assume that the maximum
number of processes in the system is limited to 10.
For creating the process-data.txt file, a utility has been provided to assist you. Download
and compile create-data.c to use the utility. Alternatively, you could just enter your process
data using an ordinary text editor.
Note: you can assume that the name of each process is never more than 10 characters in
length and does not contain spaces.
Your scheduler should read the process data from the file.5 It should then begin ‘running’ the
processes according to your chosen algorithm. Each process in the system should be stored in
its own process control block using the pcb t data structure as defined above, which should
be kept updated throughout the lifetime of the process. While a process is ‘running’, your
scheduler should sleep for the appropriate length of time using the sleep function.
When each process completes, print the following information:
• The name of the process that has completed
4 If your completed program contains additional source files, you may name other source and header files
as you wish.
5Hint: You may (if you wish) use high-level functions such as fopen, fclose and fscanf defined in
for reading the file contents. Note that these functions do not work with the low-level open,
close, etc. functions you have used in the previous assignment.
c© 2019, Faculty of IT, Monash University
6 Task 2: Preemptive Round Robin scheduling 8
• The process’s turnaround time
• The process’s total wait time.
You should also print a message whenever a process enters the system, or enters the running
state.
Document the usage of your program in a plain text file and include this with your submission.
Also document any assumptions you have made about your interpretation of the scheduling
algorithm’s implementation.
6 Task 2: Preemptive Round Robin scheduling
Now implement a second scheduling program according to the same requirements as task 1,
except:
• Now Implement Round Robin scheduling on the given process data, with a time-slice
quantum of 2 seconds.
For this task, your main C source file should be named with your student ID as: preempt-123456789.c,
where 123456789 is your student ID.6
Both your Task 1 and Task 2 implementations should be separate programs. User documen-
tation for both tasks may be included in a single file. If you need to make an assumption
about how to interpret the scheduling in a certain circumstance, you should mention any such
assumptions in your documentation.
6.1 Important: commenting is required
Commenting your code is essential as part of the assessment criteria (refer to Section 7).
All program code should include three types of comments: (a) File header comments at the
beginning of your program file, which specify your name, your Student ID, the start date and
the last modified date of the program, as well as with a high-level description of the program.
(b) Function header comments at the beginning of each function should describe the function,
arguments and interpretation of return value. (c) In-line comments within the program are
also part of the required documentation.
6 If your completed program contains additional source files, you may name other source and header files
as you wish.
c© 2019, Faculty of IT, Monash University
7 Marking criteria 9
7 Marking criteria
Tasks 1 and 2 are worth 50% each. The same marking criteria will be applied to both tasks:
• 50% for working functionality according to specification.
• 20% for code architecture (algorithms, use of functions for clarity, appropriate use of
libraries, correct use of pointers, etc. in your implementations of the three tasks.)
• 10% for general coding style (clarity in variable names, function names, blocks of code
clearly indented, etc.)
• 20% for documentation (user documentation describes functionality for the relevant task,
critical assumptions are documented, code is well-commented with file-header-, function-
header-, and inline- comments.)
8 Helpful hints
8.1 If you aren’t sure where to begin...
Try breaking the problem down until you find a starting point that you are comfortable with.
You can extend the functionality later, once you have a small part working, and you can still
pass the assignment without all of the functionality completed.
• A good place to start is simply to try printing some output, adding some rows to the
chart and appending some bars to each row in different lengths and colours.
• If you find that the window appears and disappears quicker than you can read the output,
try using the waitExit() function provided in process-visualiser.h.
• Or, if you aren’t sure where to begin with producing graphical output, start out just
printing text output.
• Use the utility provided (create-data.c), to generate process data files to test with,
and take a look at the resulting files in a text editor.
• If you are having difficulty reading the process values from a file, try hard-coding them
at first, in order to get other parts of your program working first. (Later, adapt your
code to read the values from file instead.)
c© 2019, Faculty of IT, Monash University
8.2 DOs and DON’Ts 10
8.2 DOs and DON’Ts
Do... Don’t... (!)
+ read through the comments in
process-visualiser.h for instructions
– copy and paste the provided visualisation
functions into another file
+ break your program logic into multiple func-
tions to make things easier to handle
– stuff everything into a single main function.
+ follow a clear convention for variable names – use vague names like array or p.
+ copy the specified pcb t data type definition
into your program
– hard-code lots of separate variables.
+ use a sensible data structure for holding up
to 10 process control blocks
– hard-code separate variables for each process.
+ use a loop (and sleep function) to simulate
the passage of time
– try to determine process states in an ad-hoc
way.
+ comment your code as you write it – leave commenting until the last step.
+ check over this specification carefully (e.g.
using a pen or highlighter)
– skip over specified instructions.
9 Submission
There will be NO hard copy submission required for this assignment. You are required to
archive and compress all your deliverables into a single .tar.gz file named with your Student
ID, for submission. For example, if your Student ID is 12345678, you would submit a zipped
file named 12345678 A2.tar.gz.
Your submission is via the assignment submission link on the FIT2100 Moodle site by the due
date specified in Section 1, i.e. 14th October 2019 (Monday) by 11:00am.
Note: You must ensure you complete the entire Moodle submission process (do not sim-
ply leave your assignment in draft status) to signify your acceptance of academic integrity
requirements.
9.1 Deliverables
Your submission should be archived and compressed into a single .tar.gz file containing the
following documents:
• Electronic copies of ALL your files (e.g. C source file(s)) that are needed to compile
c© 2019, Faculty of IT, Monash University
9.2 Academic Integrity: Plagiarism and Collusion 11
and run your program. (Note that your program must run in the Linux Virtual Machine
environment which has been provided for this unit. Any implementation that does not
run at all in this environment will receive no marks.)
• A user documentation file (not more than 2 pages) in plain .txt format with clear and
complete instructions on how to compile and run your program.
Marks will deducted for any of these requirements that are not strictly complied with.
9.2 Academic Integrity: Plagiarism and Collusion
Plagiarism: Plagiarism means to take and use another person’s ideas and or manner of ex-
pressing them and to pass them off as your own by failing to give appropriate acknowledgement.
This includes materials sourced from the Internet, staff, other students, and from published
and unpublished works.
Collusion: Collusion means unauthorised collaboration on assessable work (written, oral, or
practical) with other people. This occurs when you present group work as your own or as
the work of another person. Collusion may be with another Monash student or with people
or students external to the University. This applies to work assessed by Monash or another
university.
It is your responsibility to make yourself familiar with the University’s policies and
procedures in the event of suspected breaches of academic integrity. (Note: Stu-
dents will be asked to attend an interview should such a situation is detected.)
The University’s policies are available at: http://www.monash.edu/students/academic/
policies/academic-integrity
c© 2019, Faculty of IT, Monash University