FIT2100 Assignment Part B:
Process Scheduling Simulation
Semester 2 2022
Dr Charith Jayasekara
Lecturer, Faculty of IT
Email: charith.jayasekara@monash.edu
© 2022, Monash University
September 13, 2022
Revision Status
version 4: September 2022 by Charith Jayaseakra
© 2022, Faculty of IT, Monash University
1 Introduction 2
1 Introduction
Simulating scheduling algorithms is an excellent way to test and compare different algorithms
in various scenarios. It helps in choosing an appropriate algorithm both for an OS or large
scale systems. On such systems, the access patterns of resources (e.g, CPU, memory) by
users/processes, and the necessary system metrics (e.g., process turnaround time, CPU/mem-
ory usage) can be recorded for later analysis. Also, data from a real system can be used
as an input to simulate the processes/applications from a real system, and to test how the
system would perform with different scheduling algorithms. In this assignment, you will
create three different scheduler programs that each implement a different process
scheduling algorithm to simulate the scheduling of processes in a system.
You will not be doing scheduling of real processes, however your programs 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: 7th October 2022 (Friday) 11.55PM AEDT
Late submissions: A late submission penalty of 10% of the total assignment marks per day
will apply.
This assignment is worth 15% of the total marks for this unit.
2 If you require extra help
If you are stuck and/or not knowing where to begin, refer to the helpful hints in section 6.
This assignment is an independent learning and assessment exercise.
You may utilise the Ed Discussion Forum 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 should not be helping you debug your assignment code directly (you are expected
© 2022, Faculty of IT, Monash University
3 About the ‘processes’ 3
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.
3 About the ‘processes’
In this assignment, we will use a simplified model of a process, where each process:
1. has a pre-defined total service time, and
2. does not use I/O and can never be in a blocked state, and
3. will eventually run to completion and does not encounter any errors (e.g. segmentation
faults).
Each process should be represented within your program as a process control block (PCB)
instance defined as follows:
1 /∗ Sp e c i a l enumerated data type f o r p r o c e s s s t a t e ∗/
2 t y p ed e f enum {
3 READY, RUNNING, EXIT
4 } p r o c e s s s t a t e t ;
5
6 /∗ 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 ck . The s c h e d u l e r
7 ∗ shou l d c r e a t e one i n s t a n c e pe r runn ing p r o c e s s i n the system .
8 ∗/
9 t y p ed e f s t r u c t {
10 char p roces s name [ 1 1 ] ; // A s t r i n g tha t i d e n t i f i e s the p r o c e s s
11
12 /∗ Times a r e measured i n seconds . ∗/
13 i n t entryTime ; // The t ime p r o c e s s e n t e r e d system
14 i n t s e r v i c eT ime ; // The t o t a l CPU t ime r e q u i r e d by the p r o c e s s
15 i n t remain ingTime ; // Remaining s e r v i c e t ime u n t i l c omp l e t i on .
16
17 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) .
18 } pcb t ;
As a PCB is essentially a container containing information about a process, using a struct
keeps all the information about a process neatly encapsulated and makes it easier to manage
from a coding perspective1.
1A real operating system needs to manage far more information about a process, and we are only looking
at a simplified model for this assignment. For example, the process control block structure in Linux is called
task struct, and if you are curious, you can see its very complicated definition here: https://elixir.
bootlin.com/linux/latest/source/include/linux/sched.h
© 2022, Faculty of IT, Monash University
3.1 Important notes 4
3.1 Important notes
PCBs should be used to hold the information about the current processes of the system
only. You MUST NOT:
• store the information of a process which has not yet arrived (i.e. has an arrival time in
the future), or
• has been terminated.
You may:
• modify the above struct definition to include additional process information, and
• also include additional states in the process state t enumerated type if it is useful for
your implementation of the tasks in Section 5.
3.2 How to ‘run’ a process
Our processes have state information, but no program code to be executed! Times are mea-
sured in seconds and represented as integers. Your scheduler should progress through each
second during the simulation and update the process states accordingly. The scheduling pro-
gram should instantly move and start working on the next second without any delay/wait after
it finishes updating the process states for the current second.
4 About the scheduler programs you will write
4.1 Receiving process data
Each of these programs should take a filepath as its only argument, and should read pro-
cess data from this file2. If no argument is specified, use the default file with the name
processes.txt in the same directory as your programs instead.
2Hint: Unlike the previous assignment which was focused on low level system calls, you are ALLOWED
(if you wish) to use the high-level functions found in such as fopen, fclose and fscanf for
reading the file contents. Note that these high-level functions do not work with the low-level open, close,
etc. functions you have used in the previous assignment.
© 2022, Faculty of IT, Monash University
4.2 Format of process data 5
4.2 Format of process data
Each line in the process data file (processes.txt) should contain space-separated values for
a single process as follows:
[Process Name] [Arrival Time] [Service Time] [Deadline]
For example, the lines of the process data file processes.txt can be as follows:
P1 0 3 5
P2 1 6 7
P3 4 4 6
P4 6 2 2
Based on the above, the process named P1:
• arrives (see Section 4.2.2) into the system at time: 0 seconds, and
• has a total required service time (see Section 4.2.2) of 3 seconds, and
• has a deadline (see Section 4.2.3) of 5 seconds.
Each process in the system should be stored in its own process control block using the pcb t
data structure as defined in Section 3, which should be kept updated throughout the lifetime
of the process.
For all tasks in Section 5, you can assume that the processes.txt file will have:
• processes listed in order of arrival time, and
• at most 100 processes.
4.2.1 Process names
For all tasks in Section 5, you can assume that the name of each process:
• is never more than 10 characters in length, and
• does not contain spaces.
© 2022, Faculty of IT, Monash University
4.3 Outputting simulation results 6
4.2.2 Arrival and service times
Arrival and service times are measured in seconds, and represented as integers.
For all tasks in Section 5, you MUST NOT assume that:
• there will be no processes with the same arrival time.
4.2.3 Deadlines
The deadline for a process is the expected maximum time (in seconds) from the arrival to
completion of that process. When a process finishes execution, it may either successfully meet
or fail to meet its deadline (see Section 4.3.3).
For all tasks in Section 5, you can assume that:
• the given deadline for a process will be always greater or equal to the service time of
that process.
4.3 Outputting simulation results
4.3.1 During the simulation
During the scheduling simulation conducted for each of the tasks in Section 5, each of your
scheduler programs should progress through time starting from 0.
Additionally, each of your scheduler programs should print to standard output a message,
along with the current integer time, as soon as these scheduling events happen for any process:
• a process enters the system (i.e. arrives), or
• a process enters the running state, or
• a process finishes execution.
© 2022, Faculty of IT, Monash University
4.3 Outputting simulation results 7
Some example messages are shown below:
Time 0: P1 has entered the system.
Time 0: P1 is in the running state.
Time 1: P2 has entered the system.
Time 3: P1 has finished execution.
Time 3: P2 is in the running state.
......
4.3.2 After the simulation finishes
After the scheduling simulation has finished, the scheduler program for each task in Section 5
should write their respective results to a results output file named results-tasknum.txt,
where tasknum is the task number (i.e. 1, 2, or 3).
Each line in the results output file (results-tasknum.txt) should contain space-separated
values for a single process as follows:
[Process Name] [Wait Time] [Turnaround Time] [Deadline Met]
For example, the lines of the results output file results-tasknum.txt can be as follows:
P1 0 3 1
P2 2 8 0
P3 5 9 0
P4 7 9 0
Based on the above, the process named P2 has:
• a wait time of 2 seconds, and
• a turnaround time of 8 seconds, and
• failed to finish execution within the given deadline.
© 2022, Faculty of IT, Monash University
5 Programming tasks 8
4.3.3 The ’Deadline Met’ value
The Deadline Met value indicates whether the corresponding process was able to finish its
execution within the given deadline (see Section 4.2.3). For example:
• a process with a service time of 2 seconds, a deadline of 5 seconds, and waited for a
total of 3 seconds will have met its deadline, and
• a process with a service time of 5 seconds, a deadline of 10 seconds, and waited for a
total of 6 seconds will have failed to meet its deadline.
Whether a process will meet its deadline or not, is dependent on its turnaround time:
• if its turnaround time is lesser or equal to its given deadline, then that process has
successfully met its deadline, and
• if its turnaround time is greater than its given deadline, then that process did not
meet its deadline.
When interpreting the Deadline Met value of a process:
• a value of 1 means its deadline was met, and
• a value of 0 means its deadline was not met.
5 Programming tasks
Each of the assignment tasks in Section 5 must be implemented as a separate program.
Your main C source file for a particular task should be named with your student ID. For example,
your program for Task 1 should be named as task1-123456789.c, where 123456789 is your
student ID.3
Your user documentation for all the tasks must be included in a single .txt file.
3If any of your completed programs contain additional source files, you may name other source and header
files as you wish.
© 2022, Faculty of IT, Monash University
5.1 Task 1: Non-preemptive scheduling 9
5.1 Task 1: Non-preemptive scheduling
Write a scheduling program that implements the following scheduling algorithm:
• FCFS (First Come, First Served)
For this task, a process should still continue to run to completion even if it does not manage
to meet its deadline.
In your user documentation for this task (Task 1), you must:
• document the usage of your program in a plain text file and include this with your
submission, and
• document any assumptions you have made about your interpretation of the scheduling
algorithm’s implementation.
5.2 Task 2: Preemptive scheduling
Now, implement a second scheduling program according to the following preemptive algorithm:
• RR (Round Robin) scheduling algorithm, with a time quantum of 2.
• Please assume that newly arriving process gets higher priority (stays ahead) in the ready
queue if a process gets preempted at the same time.
For this task, a process should still continue to run to completion even if it does not manage
to meet its deadline.
In your user documentation for this task (Task 2), you must:
• document the usage of your program in a plain text file and include this with your
submission, and
• document any assumptions you have made about your interpretation of the scheduling
algorithm’s implementation.
© 2022, Faculty of IT, Monash University
5.3 Task 3: Deadline-based scheduling 10
5.3 Task 3: Deadline-based scheduling
Now, implement a third scheduling program, which has the primary objective of maximising
the number of processes that meet their specified deadlines.
For this particular task, you should come up with your own algorithm, or implement any existing
deadline-based scheduling algorithm you can find. Your algorithm can be either preemptive or
non-preemptive.
You have complete independence to innovate/design/find the algorithm you will use for this
task. However, your algorithm must utilise the deadline values in the decision-making
process.
Any reasonable approach which has the ability to maximise the number of deadlines met for
one or more scenarios will be acceptable.
In your user documentation for this task (Task 3), you must:
• document any assumptions you have made for your chosen (or invented) algorithm, and
• discuss how and why your algorithm works, and
• provide an example scenario/use-case/test-case where your chosen (or invented) al-
gorithm will be able to maximise the number of processes that meet their specified
deadlines.
5.4 Important: commenting is required
Commenting your code is essential as part of the assessment criteria (refer to Section 5.5).
All program code should include three types of comments:
• 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, and
• function header comments at the beginning of each function which describe the function,
arguments and interpretation of return value, and
• in-line comments within the program which clearly and concisely explains your code.
© 2022, Faculty of IT, Monash University
5.5 Marking criteria 11
5.5 Marking criteria
Task 1 is worth 40%, and both Task 2 and 3 are worth 30% each. The same marking criteria
will be applied to all the 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 professionalism (compliance with the assignment specifications and good coding
style). Good coding style includes clarity in variable names, function names, blocks of
code clearly indented, etc.
• 20% for documentation (user documentation describes functionality for the relevant task,
documents how to use the programs, documents critical assumptions, provides expla-
nations where required, etc., whereas source code is well-commented with file header
comments, function header comments, and inline comments, etc.)
6 Helpful hints
6.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.
• Once you have a small part working, you can extend the functionality later. You can
still pass the assignment without all of the functionality completed.
• 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.)
• Similarly, if you are having difficulty writing the program output values to a file, try
printing them at first, in order to get other parts of your program working. (Later,
adapt your code to write the values to the output file instead.)
• Make and keep frequent backups of your code! You may want to use a version control
system such as Git to ensure that you minimise the loss of your work, should you
encounter any unexpected mishaps such as your virtual machine suddenly breaking due
to OS updates, hardware issues, power outages, etc.
© 2022, Faculty of IT, Monash University
6.2 DOs and DON’Ts 12
6.2 DOs and DON’Ts
Do... Don’t... (!)
+ 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 100 process control blocks
– hard-code separate variables for each process.
+ 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.
+ follow the format of the specified file
naming convention in your submission
– disregard specified instructions for an arbi-
trary reason.
7 Submission
There will be NO hard copy submission required for this assignment. You are required to submit
all your deliverables (see Section 7.1) as individual files. Do ensure that your submission
complies with the requirements set out in this specifications document.
Your submission will be done via the assignment submission link on the FIT2100 Moodle site,
and should be submitted by the deadline specified in Section 1, i.e. 7th October 2021
(Friday) 11:55pm AEDT.
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.
Additionally, your program must be able to 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.
© 2022, Faculty of IT, Monash University
7.1 Deliverables 13
7.1 Deliverables
Your submission should include the following files:
• all C source files (.c format) required to compile and run your programs, where each
task in Section 5 is implemented as a separate program, and where the main
C source file for a particular task is appropriately named, and
• a single user documentation file (.txt format) of not more than 300 lines which provides
clear and complete instructions on how to compile your programs, and and how to run
all of the requested features.
Your submission may optionally include the following files, if you require them for your
implementation:
• C header files (.h format)
• A makefile
Do not submit compiled executable programs. Marks will be deducted for any of these re-
quirements that are not strictly complied with.
7.2 Academic Integrity: Plagiarism and Collusion
Plagiarism Plagiarism means to take and use another person’s ideas and or manner of express-
ing 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
© 2022, Faculty of IT, Monash University