pop up description layer
Last modified: 20080918:092523/initial version for 2008

FIT2022 AJH-2008-39

FIT2022 Computer Systems II

Laboratory Session 6

Objectives and Outcomes | Introduction | I/O Device Models | Generating the Block Requests | A Shortest Seek Time First Scheduler

Simulated Disk Scheduling System

1. Objectives and Outcomes

1.1 Objectives

  1. to model the dynamic behaviour of I/O subsystems
  2. to model some performance parameters of disk scheduling
  3. to explore the multiprogramming features of the Python library

1.2 Outcomes

At the end of this lab session, you should:

  1. understand the factors affecting disk controller design
  2. understand some of the factors affecting file system performance
  3. be aware of how Python can be used to support simulation of operating system components

Your demonstrator may ask you questions about these points, and will only give you a "satisfactory" for the lab if you can respond correctly.

2. Introduction

We develop a model of I/O device access characteristics, and use this to build a simulation of disk accessing, using a variety of disk scheduling algorithms.

You can download all files generated by this document in the tarfile lab6.tar to use in the following exercises.

3. I/O Device Models

I/O devices are typically orders of magnitude slower than CPU and memory components, and hence require careful management if their performance is not to unduly affect overall system performance. What we strive to do in I/O subsystem design is to balance the performance of the I/O components against that of the CPU and memory, so that neither unduly delays the other.

A major factor affecting I/O device performance is that they generally are not true random access devices. Access times to data stored in an I/O device (either reading or writing) comprise two basic factors: latency, which is the time taken to start a data transfer, and data transfer rate, which is the raw speed at which data can be moved into or out of the device.

For reading, the generic process consists of supplying an address to the device, starting the read operation, and then transferring the data from the device as it becomes available. For example, a scanner may take some time to warm up the lamp and move the carriage to the start of the original before it can start delivering data. This is the latency time. Once the data starts being delivered by the device, it may be constrained by the bandwidth of the data channel, or, more usually, by the intrinsic delivery rate of the device. For a scanner, this will be limited by the physical speed of the scanner head.

For writing, the generic process requires the initial supply of both address and data to the device, although the data may be delayed until the latency time has elapsed. For example, a printer may have to pick a sheet of paper from the stock hopper, and transport it until it is under the print head before the data to print actually needs to be available.

For both read and writing, a single user level request ("scan a print") may be broken into a number of address/data requests at the device level. (We have already seen this with file reads and writes in Lab 5 requiring multiple disk block accesses.)

We shall in this lab gloss over the differences between reading and writing, as they tend to be dominated by the other factors.

"iodev.py" 3.1 =
import timefrom threading import *from Queue import *Scale = 1e+2<class IODevice definitions 3.2><class Tape definitions 3.5><class Disk definitions 3.8>

The iodev module defines 3 classes of IO devices:

IODevice
This is the generic IO device. It has random access characteristics.
Tape
The generic sequential device. To get to block n, you must scan through all blocks in the range k..n, where k is the starting position.
Disk
The generic magnetic rotating memory. Its access comprises two components: a seek time, and a rotational latency. (See below for explanation.)

The Scale factor determines the simulation slow down factor. Devices run a hundred times slower than their actual speed, so that they can be observed in real time.

3.1 The Generic IODevice

The generic device is straightforward. Its seek time or latency is constant, and the data transfer rate is effectively instantaneous.

<class IODevice definitions 3.2> =
class IODevice: SeekTime = 0.01e-6 <class IODevice initialization 3.3> <class IODevice seek 3.4>
Chunk referenced in 3.1
<class IODevice initialization 3.3> =
def __init__(self, size=100000): self.current_block = 0; self.previous_block = 0; self.size = size self.str="generic"
Chunk referenced in 3.2

Initialize the generic IO device with a default size of 100,000 blocks. The current_block and previous_block variables are used in computing the latency. Call this class in the form

    d = IODevice(20000)
to create an instance d of a generic IO device with size 20,000 blocks (the block size is not specified).

<class IODevice seek 3.4> =
def seek(self, block_num): global Scale if (block_num 8 0) | (block_num >= self.size): return None; self.current_block = block_num seek_time = self.SeekTime*Scale time.sleep(seek_time); self.previous_block = self.current_block return seek_time
Chunk referenced in 3.2

This routine simulates a generic IO device seek, takingIODevice.SeekTime seconds for all accesses (the calculation is independent of the actual block sought).

Note that we first check that the block address is within range, and then record the current block address, before simulating a response time of SeekTime for all accesses, regardless of address or current position.

3.2 The Tape Device

The Tape device is characterized by a seek time that is proportional to the distance between the current block, and the desired block.

<class Tape definitions 3.5> =
class Tape(IODevice): SeekTime = 0.1e-3 <class Tape initialization 3.6> <class Tape seek 3.7>
Chunk referenced in 3.1

The Tape device inherits from the class IODevice, indicated by the use of the IODevice class name in the "parameter list" of the class.

Here we use inheritance to say "a Tape device is an example of an IO device. It has slightly different characteristics in terms of its seek time, but it can be used in a similar fashion to the class IODevice. Everything that you can do with an IODevice, you can do with a Tape device." In computer-speak, it "isa" IODevice.

<class Tape initialization 3.6> =
def __init__(self, size=100000000): IODevice.__init__(self, size) self.str="tape"
Chunk referenced in 3.5

Define the default size of a tape device to be somewhat larger (100,000,000 blocks) than the generic device. Otherwise the initialization is exactly the same as for the generic device, indicated by the superclass call on the parent class initialization method.

<class Tape seek 3.7> =
def seek(self, block_num): global Scale if (block_num 8 0) | (block_num >= self.size): return None; self.current_block = block_num distance = abs(self.current_block - self.previous_block) seek_time = distance * self.SeekTime * Scale; time.sleep(seek_time); self.previous_block = self.current_block return seek_time
Chunk referenced in 3.5

Check that the requested block is in range. The seek time is assumed to be directly proportional to the distance between the new target block (current_block) and the previous block accessed (previous_block). Simulate this seek time with a sleep operation.

3.3 The Disk Device

The Disk device is characterized by a latency that has two parts: moving the read/write head to the appropriate cylinder, called the head seek time (typically 10's of mS, depending upon the distance travelled); and the time taken for the required sector to rotate under the read head, called the rotational latency. For a disk rotating at 3600 rpm, this means an average rotational latency of 1/2 of the time for one revolution, or 0.00833 seconds. (We are using old technology here!)

<class Disk definitions 3.8> =
class Disk(IODevice): SeekTimeCyl = 0.005 SeekTimeSect = 0.0000167 <class Disk initialization 3.9> <class Disk seek 3.10,3.11,3.12,3.13>
Chunk referenced in 3.1

We assume that there are 1000 sectors to a cylinder, making the rotational latency 0.01667/1000 = 0.0000167 seconds per sector.

<class Disk initialization 3.9> =
def __init__(self, size = 1000000, cylinder = 1000): IODevice.__init__(self, size) self.cylinder_size = cylinder self.str="disk"
Chunk referenced in 3.8

As before, the initialization of the disk calls the parent class initialization, augmented by the additional parameter setting of the number of cylinders on the disk.

<class Disk seek 3.10> =
def seek(self, block_num): global Scale if (block_num 8 0) | (block_num >= self.size): return None; self.current_block = block_num
Chunk referenced in 3.8
Chunk defined in 3.10,3.11,3.12,3.13

check for address in range and determine the new current block address, as given by the actual parameter

<class Disk seek 3.11> =
current_cylinder = self.current_block / self.cylinder_size current_sector = self.current_block % self.cylinder_size previous_cylinder = self.previous_block / self.cylinder_size previous_sector = self.previous_block % self.cylinder_size
Chunk referenced in 3.8
Chunk defined in 3.10,3.11,3.12,3.13

compute the new cylinder and sector information, as well as (re)compute the old values of the same. These are given by splitting an address into two parts, using a divide and remainder algorithm. (In practice, if the cylinder size is a power of two, shift and mask can be used.)

<class Disk seek 3.12> =
cylinders = abs(current_cylinder - previous_cylinder); sectors = current_sector - previous_sector if(sectors 8 0): # we have to go around the disk once sectors = sectors + self.cylinder_size
Chunk referenced in 3.8
Chunk defined in 3.10,3.11,3.12,3.13

Compute the seek distances across the tracks (cylinders to cylinders) and around the track (sector to sector).

<class Disk seek 3.13> =
total = cylinders * self.SeekTimeCyl + sectors * self.SeekTimeSect; seek_time = total * Scale time.sleep(seek_time); self.previous_block = self.current_block return seek_time
Chunk referenced in 3.8
Chunk defined in 3.10,3.11,3.12,3.13

Compute the total seek time and simulate it.

Exercise 1

OK, let's try these out. To do this, create a little test file that creates instances of each of these things, and then calls them with a variety of short and long seek times for each type.

"test-dev.py" 3.14 =
from iodev import *print "testing generic IODevice"def testseek(typ,pos): typename=typ.str val=typ.seek(pos) if val!=None: print " %s seek(%8d)=%10.6f" % (typename,pos,val) else: print " Bad seek"g = IODevice(1000000)testseek(g, 0) # should be fasttestseek(g, 1000) # should also be fasttestseek(g, 1001) # should also be fasttestseek(g, 1000) # should also be fasttestseek(g, 999999) # should be fasttestseek(g, 1000000) # should failprint "testing Tape device"t = Tape() # use default sizetestseek(t, 0) # should be fasttestseek(t, 100) # perhaps not quite as fasttestseek(t, 1000) # slower stilltestseek(t, 1001) # fast!testseek(t, 1000) # fast or slow?# dare you try testseek(t, 10000) ?print "testing Disk device"d = Disk()testseek(d, 0)testseek(d, 100)testseek(d, 1000)testseek(d, 1001)testseek(d, 1000)
  1. Are the last three calls on the tape drive realistic? Explain why they might be, and why they might not be. Predict the time for testseek(t, 10000). If you have a video tape recorder at home, does this time sound familiar?
  2. Older tape drives required a rewind and then forward seeks if the desired position was less than the current position (recall your video recorder again). Make a new class OldTape, where the seek method requires rewinding and advancing for any request that is backwards of the current position. Assume a rewind time of 1 seconds per 1000000 blocks (actually non-linear). Add your OldTape class to test-dev.py and explore.
  3. Explain the behaviour of the last three calls for the disk device. Explore what happens with the disk device when a) you seek back to sector 0 after every seek, and b) you go backwards and forwards the same amount, varying from say 10 sectors through to 1010 sectors.

4. Generating the Block Requests

We need some things to drive the IO devices. We will model three different styles of address generation: random, as generated by a binary chop algorithm, and as generated by a column major array access. A practical example of the last one is an image that is accessed in vertical strips, rather than in horizontal strips. This means the array of pixels is accessed down the columns, rather than across the rows (which would be called Row Major order access).

"simprocess.py" 4.1 =
from threading import *import randomimport time<class Proc 4.2><class RandomSeeker 4.11><class BisectionSeeker 4.13><class ColumnMajor 4.15>

We define three processes that simulate the generation of a sequence of block requests. Each of these processes is modelled by a thread, which is a quasi-parallel sequence of execution, as per the lecture discussion for slides 4.16-18. The plan is to run each of these processes in parallel, so that their sequence of disk requests is interleaved with each other, exactly as occurs in real life.

4.1 The Proc parent class

<class Proc 4.2> =
procs_running = 0procs_running_mutex = Lock()class Proc(Thread): <class Proc run 4.4> <class Proc finish 4.5> <class Proc start 4.3> <class Proc initialize 4.6>
Chunk referenced in 4.1

The first class defined here is the parent class of the block request generation, and serves to define common features of the process invocation and sequencing mechanisms.

<class Proc start 4.3> =
def start(self): global procs_running_mutex,procs_running print self.getName(),"starting" procs_running_mutex.acquire() # critical section entry procs_running = procs_running + 1; procs_running_mutex.release() # critical section exit Thread.start(self)
Chunk referenced in 4.2

A process thread is started by this call. Note that the actual starting is done by the parent, which also invokes the run method for this object (see following). Here we keep track of the number of active block address generators, by incrementing a shared variable. Note the critical section surrounding it.

<class Proc run 4.4> =
def run(self): it = self.start_block; end = self.end_block; name = self.getName() for i in range(self.iterations): self.request_block(name,it); it = it + 100; self.finish()
Chunk referenced in 4.2

The run method actually runs the process within the currently active thread. It is invoked automagically by the start method. The run method is actually going to be overridden by later definitions, but it serves to define a default mechanism, viz. (L. videre licet, it is permitted to see, see also, namely), scan through from start to finish and read every 100th block.

<class Proc finish 4.5> =
def finish(self): global procs_running_mutex,procs_running procs_running_mutex.acquire() # critical section entry procs_running = procs_running - 1; procs_running_mutex.release() # critical section exit print self.getName(),"finished"
Chunk referenced in 4.2

Here we terminate the process and its thread, and decrement the number of processes, again in a critical section.

<class Proc initialize 4.6> =
def __init__(self, n, r, k, s, e): self.request_block = r; self.iterations = k self.start_block = s; self.end_block = e Thread.__init__(self, group=None, target=None, name=n, args=(self)) self.setDaemon(1)
Chunk referenced in 4.2

Some initialization stuff. Not worth explaining here, but interested readers are referred to the library documentation.

Exercise 2

Test this process. We could try it with both Tape and Disk devices, using a simple sequential scan through the data:"test-proc1.py" 4.7 =
from iodev import *from simprocess import *<test tape request 4.8><test disk request 4.9>print "\ntesting Sequential Access of Tape Device"p1 = Proc("proc+tape",req_tape,20,0,10000)p1.run()print "\ntesting Sequential Access of Disk Device"p2 = Proc("proc+disk",req_disk,20,0,10000)p2.run()
<test tape request 4.8> =
t = Tape()def req_tape(n,b): global t print n,b,t.seek(b)
Chunk referenced in 4.7 4.10 4.12 4.14 4.16 4.17
<test disk request 4.9> =
d = Disk()def req_disk(n,b): global d print n,b,d.seek(b)
Chunk referenced in 4.7 4.10 4.12 4.14 4.16 4.17

Exercise 3

Now for something more subtle: interleaved seeks!

"test-proc2.py" 4.10 =
from iodev import *from simprocess import *<test tape request 4.8><test disk request 4.9>print "\ntesting Parallel Operation of both Tape and Disk"p1 = Proc("proc+tape",req_tape,20,0,10000)p2 = Proc("proc+disk",req_disk,20,0,10000)p1.start(); p2.start() p1.join(); p2.join()

The start methods fire up each of the respective threads: the corresponding join methods wait for each thread to terminate. Note that you could change the c.run in Exercise 3 to a c.start(); c.join() for exactly the same effect. What is the difference between these two forms?

4.2 The Random Access Pattern Generator

<class RandomSeeker 4.11> =
class RandomSeeker(Proc): def run(self): s = self.start_block; e = self.end_block; name = self.getName() for i in range(self.iterations): self.request_block(name,random.randint(s, e)) self.finish() def __init__(self, n, r, k, s, e): self.request_block = r; self.iterations = k Proc.__init__(self, n, r, k, s, e)
Chunk referenced in 4.1

The random access pattern is handled by repeated calls on the random method that returns an integer in the specified range (s..e). Initialization is handled through the parent, and the start and finish methods are inherited from the parent.

Exercise 4

Now to test the Random Pattern, again across both Tape and Disk:"test-rand.py" 4.12 =
from iodev import *from simprocess import *<test tape request 4.8><test disk request 4.9>print "\ntesting Random Access of Tape Device"p1 = RandomSeeker("rand+tape",req_tape,20,0,1000)p1.start(); p1.join();print "\ntesting Random Access of Disk Device"p2 = RandomSeeker("rand+disk",req_disk,20,0,1000)p2.start(); p2.join();

4.3 The Binary Chop Simulation

<class BisectionSeeker 4.13> =
class BisectionSeeker(Proc): def run(self): s = self.start_block; e = self.end_block; name = self.getName() for i in range(self.iterations): m = int((s + e) / 2) if (m == s): break self.request_block(name,m) (s, e) = random.choice([(s, m), (m, e)]); self.finish() def __init__(self, n, r, k, s, e): self.request_block = r; self.iterations = k Proc.__init__(self, n, r, k, s, e)
Chunk referenced in 4.1

Exercise 5

OK, run this and see what you get. Is the pattern what you would expect? What can you say about it? Try changing the limit from 1000 to 10,000 or even 1,000,000.

"test-chop.py" 4.14 =
from iodev import *from simprocess import *<test tape request 4.8><test disk request 4.9>print "\ntesting Binary Chop on Tape Device"p1 = BisectionSeeker("chop+tape",req_tape,20,0,1000)p1.start(); p1.join()print "\ntesting Binary Chop on Disk Device"p2 = BisectionSeeker("chop+disk",req_disk,20,0,1000)p2.start(); p2.join()

4.4 Column Major Order

<class ColumnMajor 4.15> =
class ColumnMajor(Proc): def run(self): s = self.start_block; e = self.end_block; name = self.getName() for i in range(self.iterations): self.request_block(name,(s / 100) + (s % 100) * 100) s = s + 1; self.finish() def __init__(self, n, r, k, s, e): self.request_block = r; self.iterations = k Proc.__init__(self, n, r, k, s, e)
Chunk referenced in 4.1

Exercise 6

OK, run this and see what you get. Is the pattern what you would expect? What can you say about it? Try changing the number of iterations.

"test-col.py" 4.16 =
from iodev import *from simprocess import *<test tape request 4.8><test disk request 4.9>print "\ntesting Column Access on Tape Device"p1 = ColumnMajor("col+tape",req_tape,20,0,1000)p1.start(); p1.join()print "\ntesting Column Access on Disk Device"p2 = ColumnMajor("col+disk",req_disk,20,0,1000)p2.start(); p2.join()
Bit tedious huh?

Exercise 7

Now for the real crunch: running all these methods in parallel!

"test-par1.py" 4.17 =
from iodev import *from simprocess import *<test tape request 4.8><test disk request 4.9>r = RandomSeeker("rand+disk",req_disk,20,0,1000)b = BisectionSeeker("chop+disk",req_disk,20,0,1000)c = ColumnMajor("col+disk",req_disk,20,0,1000)b.start(); c.start(); r.start(); b.join(); c.join(); r.join();

Exercise 8

Time the program to see how long it takes. Now reorder the calls so that each runs to completion before the next, and retime it. Explain the differences. How does the random access process affect things? You should by now have a good "feeling" for how process I/O behaviour can affect system performance.

5. A Shortest Seek Time First Scheduler

The requests generated so far have simply been fed straight to the IO device. Particularly for disks, there is an advantage on ordering the requests so that extreme movements of the head are avoided. To do this, we interpose a scheduler between the source of disk addresses and the disk device itself.

"sstf.py" 5.1 =
from iodev import *from simprocess import *running = 1; finished = 0disktime = 0.0<class SSTF 5.4>d = Disk(); scheduler = SSTF(d); scheduler.start()<sstf disk request 5.5><sstf start a range of block request processes 5.2><sstf wait for all processes to complete 5.3>print "\nTotal Disk Seek Time = ",disktime

Our new design introduces a scheduler class, SSTF, described below. In order to see how the scheduler can improve matters, this time we run a number of chop processes, started en masse.

<sstf start a range of block request processes 5.2> =
b = []; NumB = 10for i in range(NumB): name = "chop+disk%d" % i newb = BisectionSeeker(name,disk_req,20,0,1000) b.append(newb) newb.start()
Chunk referenced in 5.1

Here's how we fire off 10 instances of our chopper processes ...

<sstf wait for all processes to complete 5.3> =
for i in range(NumB): b[i].join()running = 0scheduler.join()
Chunk referenced in 5.1

... and then wait for them all to finish.

5.1 The Scheduler Class

<class SSTF 5.4> =
class SSTF(Thread): def __init__(self,dev): self.device = dev; self.queue = [] self.mutex = Lock() Thread.__init__(self,group=None, target=None, name=None, args=None) self.setDaemon(1) <class SSTF run method 5.6> def start(self): Thread.start(self) def accept_req(self,n,b,lk): self.mutex.acquire() self.queue.append((b,lk)) self.mutex.release() print "accepted request from %s for block %d, queue=" % (n,b),\ self.str_q(self.queue) return def str_q(self,q): r = [] for x in q: (b,e) = x r.append(b) return r
Chunk referenced in 5.1

The shortest seek time first scheduler swallows up block requests and returns immediately, through its accept_req interface. However, to make sure that a process requesting a block does not continue on until the request is completed, we pass in a synchronization lock lk as part of the request. The tuple of block number and lock (b,lk) is then appended to a queue for servicing by the disk when it is next free.

The scheduler itself runs as a separate process, and hence the additional housekeeping activities to initialize and start the process. str_q is used to return a string representing the block requests in the queue, for tracing purposes.

<sstf disk request 5.5> =
def disk_req(n,b): global scheduler complete = Event(); complete.clear() scheduler.accept_req(n,b,complete) complete.wait() return
Chunk referenced in 5.1

Here is the other side of synchronizing with the scheduler. Each process requesting a block calls this routine, which creates an event lock, initially cleared. We then pass the request on to the scheduler, along with this lock. Since the accept_req interface routine returns immediately, we must then wait for the event to be signalled, through the complete event flag.

<class SSTF run method 5.6> =
def run(self): global running, disktime dev = self.device while running: if (len(self.queue) > 0): self.mutex.acquire() <class SSTF run method find closest block 5.7> self.mutex.release() t = self.device.seek(block) disktime = disktime + t print "completed request for block %d in time %f" % (block,t) complete.set() else: pass time.sleep(0)
Chunk referenced in 5.4

The guts of the SSTF scheduler. We run an outer loop, that remains whilever there are still address generating processes in the system. Since within this loop we update shared variables (can you identify them?), we whack a mutual exclusion around it, pausing only to issue a sleep(0) call which has the effect of allowing any other ready process to run.

<class SSTF run method find closest block 5.7> =
dist = 2*dev.size; closest = 0; cur = dev.current_blockfor i in range(len(self.queue)): (b,l) = self.queue[i] if (abs(b-cur) 8 dist): closest = i; dist = abs(b-cur)(block,complete) = self.queue[closest]print "%d is closest to %d in" % (block,cur), self.str_q(self.queue)del self.queue[closest]
Chunk referenced in 5.6

And the real guts: we scan through the current queue of block requests, looking for the closest block to the current block, since that will have the shortest seek time.

Exercise 9

Run the program sstf.py and enjoy the results! Can you see any evidence of starvation? Find a sequence where the scheduling makes an obvious difference. To get a more accurate comparison between the two algorithms, download the program both.py (it's also in the tarfile) and run that. It runs both algorithms over the same sequence of address traces.

Exercise 10

There is a significant bug in the algorithm to compute the shortest seek time first block. Can you identify it? A bonus mark for those who can, and a chocolate frog for a fix for the bug!

Document History

20080918:092523 2.0.0 ajh initial version for 2008
This page maintained by John Hurst.
Copyright Monash University Copyright Policy
626 accesses since
14 Aug 2008
My PhotoTrain Photo

Generated at 20090705:1404 from an XML file modified on 20080918:0927
Maintainer use only; not generally accessible: Local ServerWork ServerCSSE Server

176 accesses since 09 Jul 2009, HTML cache rendered at 20120216:0802