|
|
Project 1 2016 - simulate OS process scheduling and disk I/O
|
The goal of this project
is to develop and test a C99 program,
named osevents,
that reports three basic integral statistics about the 'mix' of events
in a scenario file.
The name of the scenario file is provided as the only command-line argument
to your osevents program.
Your program should terminate when all events have been "performed" -
after the last process has exited.
This project will assess your understanding of
introductory C99 programming language features,
including its control-structures,
simple data-structures,
and its standard library support for handling strings and text files.
The project can be successfully completed using the information presented
in CITS2002's lectures, laboratories, and tutorials,
to the end of week-5.
|
Consider an operating system's
5-State Model of Process Execution.
New processes are admitted to the system
and are immediately marked as Ready to run.
Each process executes, in turn, until it
- completes its execution
(at which time the process Exits),
- executes for a finite time-quantum
(after which the process is marked as Ready
and is queued until it can again Run), or
- requests some input or output (I/O)
(at which time the process is marked as Blocked
and queued until its I/O request is be satisfied).
For this project we'll consider a simplified embedded operating system
in which only a single process occupies the single CPU at any one time,
and all I/O is performed using a single disk-drive.
Our operating system executes on a low-powered 1MHz processor,
with its internal clock advancing every one microsecond,
and all instructions taking one microsecond to execute.
Requests to perform I/O on the disk-drive suffer rotational latency,
as the required disk sector may not be under the single read/write head at
the time of the request.
Thus, disk I/O requests result in the requesting process being
Blocked until the required sector is available.
As our operating system is typically used in remote data-logging environments,
the integrity of the disk I/O is crucial,
and so every write request is implicitly followed by a read
request from the same sector to verify the data just written.
Between the execution of any two instructions,
the operating system determines which disk sector is currently
available for I/O (under the disk's read/write head).
All of the Blocked processes that have previously requested I/O
from the currently available sector are marked as Ready to execute,
and are queued until they can again Run.
Switching between states,
such as 'New → Ready', 'Ready → Running',
incurs no cost -
the global/absolute time does not advance,
and the processes involved do not accumulate any additional runtime.
Scenario files
Consider the following text file, which we'll call a scenario file.
Each line of the file contains a number of fields,
separated by one or more spaces or tabs,
and provides either a named constant, defining characteristics of the system,
or the description of a single event.
We may assume that the format of each scenario file is correct,
and its data consistent,
so we do not need to check for errors in the scenario file.
timequantum 20000
diskrpm 5400
disksectors 64
1100000 0 admit
40000 0 read 18
45000 0 read 20
1600000 1 admit
60000 0 read 12
100000 0 exit
30000 1 read 20
80000 1 write 0
1000000 1 exit
Each event line (which begins with an integer) has a number of fields,
separated by one or more spaces or tabs.
- the first field provides a (non-negative) time,
measured in microseconds.
- the second field provides a (small, non-negative) process-identifier (PID).
Events of type admit will always have a previously unused
(and strictly monotonically increasing) PID;
all other events provide an existing PID.
There will be at most 50 processes (with PIDs 0..49) in existence at once.
- the third field provides an event type -
it will always be one of
admit, read, write, or exit.
- the fourth field provides a (non-negative) integer
which represents the required disk sector number for an
I/O event.
Only read and write events have this field.
Individual processes will have at most 100 I/O events
over their lifetime.
The time field for admit events represent an absolute time,
since the operating system rebooted.
In the above example,
processes 0 and 1 are admitted at time 1.1 and 1.6 seconds, respectively.
The time field for all other events represents a relative time -
a number of microseconds that the process has spent executing
(i.e. the total time it has spent on the CPU).
In the above example,
process 0 makes I/O requests after/when it has executed for
40000μs, 45000μs, and 60000μs,
and then Exits after a total execution time of 100000μs.
Disk operation
The characteristics of the simple single-platter,
fixed-multi-head, disk drive
are defined in the scenario file.
The disk spins at a constant rate,
measured in revolutions-per-minute.
The disk has a number of sectors which can be considered as
arcs radiating from the disk centre
[see Wikipedia].
Sectors are numbered from 0 and,
when the machine reboots,
sector 0 is positioned under the head.
Each sector contains an identical number of data blocks and (pedantically)
a disk I/O request requires both a sector number and a block number to
identify the required disk location.
However,
because the disk head under which the disk spins is fixed,
our scenario files only need to provide the sector number.
For example,
a 20 sector disk spinning at 5400RPM,
would 'see' sectors 0,1,...19,0,1... in order
and would 'see' a total of
(5400 / 60 * 20) = 1800 sectors per second.
The disk spins constantly,
and can only perform read or write operations when the required sector
first becomes available
(as it must read/write the whole sector).
For example,
if sector 28 has been under the head for a few microseconds already,
and a process now requests I/O using sector 28,
then that process will have to block and wait for
the disk to spin around until sector 28 again becomes available.
Program requirements
The statistics are all printed on a single output line,
separated by tab characters.
- the first statistic is the total process turnaround time,
reported in microseconds.
Each individual process's turnaround time is the difference between
the (absolute) time at which the process is Admitted
and
the (absolute) time at which the process Exits.
There is no need to additionally account for the time
spent in the Ready or Blocked queues -
these will be "automatically" adding to the turnaround time as they simply
delay each process's (absolute) Exit time.
- the second statistic is the total blocked reading time,
reported in microseconds.
This is the sum of all the time that all processes spend in the Blocked queue
waiting for their read requests to be serviced.
- the third statistic is the total blocked writing time,
reported in microseconds.
This is the sum of all the time that all processes spend in the Blocked queue
waiting for their write requests to be serviced
(both the writing and read/verification times).
Your program can print out any additional information (debugging?) that you
want - just ensure that the three statistics appear on the very last line.
Good luck!
Chris McDonald.
|
