Assignment 1
(due Monday, October 19, at 11:30 pm)
Your task in this assignment is to implement a simplified Dispatcher for an OS. It will simulate dispatching using one of three dispatching policies, and change states of processes admitted to the system respectfully, as described in lecture notes and the textbook. It will also accumulate statistics about each process and print it at the end of simulation.
Here is generic scenario: there is a mix of processes arriving to the system with each process falling into one of three categories. It is either CPU bound process, short process or I/O bound process.
All CPU bound processes require 1000 milliseconds of CPU time to complete and do not do any I/O.
All short processes require 200 milliseconds of CPU time to complete and do not do any I/O.
All I/O bound processes require 200 milliseconds of CPU time to complete, and do I/O requests
after 50, 100, and 150 of used CPU time.
Processes from the mix start to arrive to the system at time 0, and arrive every 100 milliseconds. Process ID is assigned to the processes in order of arrival, starting with ID =1.
The mix of processes arriving to the system is defined by a single string. For example, the string process.
All short processes require 200 milliseconds of CPU time to complete and do not do any I/O.
All I/O bound processes require 200 milliseconds of CPU time to complete, and do I/O requests after 50, 100, and 150 of used CPU time.
Processes from the mix start to arrive to the system at time 0, and arrive every 100 milliseconds. Process ID is assigned to the processes in order of arrival, starting with ID = 1.
The mix of processes arriving to the system is defined by a single string. For example, the string CCIIS
describes a mix of 5 processes:
process with ID=1 is CPU bound and arrives to the system at time 0;
process with ID=2 is CPU bound and arrives to the system at time 100;
process with ID=3 is I/O bound and arrives to the system at time 200;
process with ID=4 is I/O bound and arrives to the system at time 300;
process with ID=5 is short process and arrives to the system at time 400.
Your Dispatcher will have to keep track of events and changes in the state of the processes, taking into account the following additional conditions:
• There is only one type of I/O requests - request to the hard drive;
• hard drive serves requests using FIFO (first in first out) policy;
• every request to hard drive takes 1000 milliseconds to complete;
• if there are no ready user processes, then process number 0 (system idle process) is running;
• if process 0 is running and new process is created, or as the result of an event one of the blocked processes becomes ready (unblocked), this process will get CPU immediately.
Implement only one of three scheduling algorithms (how to select which one is described below): Round Robin with quantum size 200 milliseconds, Shortest Remaining Time Next, or
First Come First Served, taking into consideration the following
• if some process is unblocked and another one is preempted at the same time, unblocked process will get into the ready queue (or ready list) first;
• if some process is unblocked (preempted), and another one is admitted to the system at the same time, unblocked (preempted) process will get into the ready queue (or ready list) first;
• if a process requests an exchange with the hard drive and CPU quantum expires at the same time, this process will get into blocked (not ready) state.
When all lines of the input are processed, Dispatcher will print the following cumulative information about all processes admitted to the system during simulation:
You can assume that input is consistent, i.e. contains no errors.
For example, if the input is
ISC
The following output is expected
FCFS :
0 2050 1400
1 200 250 3000
2 1000 0 0
3 200 100 0
RR :
0 1850 1400
1 200 50 3000
2 1000 250 0
3 200 50 0
SRTN :
0 1800 1400
1 200 0 3000
2 1000 250 0
3 200 0 0
See additional documents on MLS for explanations.
2
How to decide what is your scheduling policy to implement?
You are assigned the policy to implement based on your ID:
• If your ID is < 171000000 then you will implement Round Robin.
• If your Laurier ID is > 171000000 but < 180111111 then you will implement Shortest Remaining Time Next.
• If you Laurier ID is > 180111111 then you will implement First Come First Served.
Implementation details
You can simulate \global" time using a global counter that starts at 0 and is incremented by 50 on every iteration of simulation.
Your code must have two data structures: queue of blocked processes, and list or queue (depending on scheduling) of ready to run processes.
It is advisable to also have new processes queue data structure. It simplifies programming. You can first process the input by inserting processes into the New_Queue and start simulation after processing the input. Your implementation must have a structure that represents a process. Minimal requirements for the fields in this structure are: process ID, process status (new/running/ready/blocked/exited), process service time, process local time counter, array of requests to the hard drive.
Your implementation must have a process table, that keeps track of all processes admitted to the system during the simulation.
Another recommendations are given in
Your implementation must have a structure that represents a process. Minimal requirements for the fields in this structure are: process ID, process status (new/running/ready/blocked/exited), process service time, process local time counter, array of requests to the hard drive.
Your implementation must have a process table, that keeps track of all processes admitted to the system during the simulation.
Another recommendations are given in A1_DataStructures_and_other.pdf posted on MLS.
If your submission is in C, it should be possible to compile your program with gcc -o Dispatcher Dispatcher.c in command line window.
Your program will read single line describing the mix of processes from the standard input and will print required statistics to the standard output.
2020-10-18