Minimize arm movement
Minimize mean response time(for job completion)
Minimize variance in response time.

To look at these algorithms, will imagine a simple disk with the following characteristics:

• One side only
• 50 tracks labeled 0 through 49
• takes 1 millisecond to travel from one track to another

Strategy has many disadvantages:

• Doesn’t meet the three goals
• Extreme arm movements

Like shortest job next for processor allocation. In this algorithm, the request with the track closest to the one being served is selected. Using the same example as above:

Considerable improvement over FCFS. However, has disadvantages. Tendency to favour short jobs, postpones out-of-the-way jobs. In a real situation, job requests come in all the time – arm will tend to stay in centre of disk where most requests can be met. May cause starvation of some requests.

These algorithms involve using a directional bit to indicate which way the arm is moving and involve the arm moving methodically in one direction, then the other. The classic SCAN algorithm involves moving from the outermost to the innermost tracks, servicing every request in its track. There are several variations of this approach:

For this example, LOOK seems worse than SSTF. However, jobs cannot be indefinitely postponed under this algorithm.

Another rule for this algorithm - incoming requests incorporated into correct place in queue, and serviced when arm reaches track. If track 11 is being serviced when a request for 13 arrives, will carry on and do track 7 and track 4 as arm must continue in same direction. Track 13 must wait till the arm is on its way back. SCAN meets all three goals of seek strategies. Only disadvantages are that it needs an extra bit and the programming is rather complex.

Requests are not incorporated into the arm’s path as it travels. All added when it gets to the point at which it will change direction.

Picks up requests during its inward sweep. When innermost track has been reached, immediately returns to outermost track and starts servicing requests that had arrived during last inward sweep. This algorithm can provide quicker service to requests accumulated for low numbered tracks while arm was moving inward. Idea is that when arm reaches high-numbered tracks, few requests immediately behind it. Ones at far end of the disk have been waiting longest. Provides a more uniform wait time.

Optimization of C-SCAN. Sweep inward stops at high numbered track request – arm doesn’t move to last track unless requested to do so. Only returns to lowest numbered track requested. Very complex algorithm

Which strategy is best?

• FCFS works well with light loads, but as load grows, service becomes unacceptably long.
• SSTF is appealing, but risk of starvation is problem
• SCAN/LOOK avoids starvation and works well with light loads.
• CSCAN/LOOK works well even with heavy loads and has a very small variance.

What about rotation?

So far, only looked at seek times. Need to optimize search times once read/write head has been positioned. This is called "rotational ordering"

Have to also consider which sector on the track needs to be read. Imagine a disk with only 5 tracks 0 though 4 and each track contains 5 sectors. Supposing the it takes 1 ms to move from 1 track to another and 5 ms to rotate from sector through sector 4 and 1 ms to transfer one sector from the drum.

With this request list:

Seek time between tracks is a function of the hardware and cannot be modified. However, amount of time due to rotational delay can be reduced. Requests ordered within each track would help. As below:

Tracks are processed from low numbered to high numbered then from high numbered to low numbered in a sweeping motion like that used in SCAN.

There are two levels of ordering of requests on a hard drive. One to handle the position of the read/write heads and another to handle the processing of each track.

Worked example data:

NT IO system protects applications from differences among physical devices. Shields rest of OS from details of device manipulation and isolates hardware dependent code. The NT IO was designed to provide the following:

• Multiple installable file systems (FAT, HPFS,CD, NTFS)
• Ability to add and remove devices from the system
• Fast IO processing while allowing drivers to be written in high level language.

IO system is packet driven. Every IO request represented by IO request packet (IRP) as it moves from one IO component to another. An IRP is a data structure that controls how IO operation is controlled at each step. As well as creating and disposing of IRP packets, IO manager supplies code, common to different drivers, that they call to carry out their IO processing. IO manager also allows device drivers and file systems (also perceived as device drivers) to be loaded dynamically based on the needs of the user. Different file systems can call the same disk driver to access files.

The device driver in an NT system cannot make assumptions about underlying file system. NT IO manager communicates at the intermediate levels between the application and the device driver, and creates a unique NT driver for each device.

Each NT driver must include the following:

• Initialization routines, performed during booting, that create system objects used by IO manager to recognize and access drivers.
• A dispatch routine used by IO manager to communicate with the driver when it generates an IRP after an IO request.
• A start IO routine used by the driver to initiate transfer to or from a device.
• A completion routine used to notify a driver that a lower level driver has finished processing an IRP.
• Unload routine that frees up system resources from memory
• Error logging routine that passes unexpected events to IO manager to be logged in an error file (e.g. bad sectors on a disk)

IO manager creates a driver object during booting. Creates a driver object for each device to be handled by this driver.

• When a process needs to access a file it uses a file name which includes the device object where the file is stored (absolute address).
• When the file is opened, IO manger creates a file object and returns the file handle to the process. Whenever the process uses the file handle, the IO manager can immediately find the device object which points to the driver object representing the driver that services the device.
• A driver object may have multiple device objects pointing to it. The list of device objects represents all the physical, logical and virtual devices that are controlled by the driver. Each sector on a hard disk has a separate object with sector specific information.

Using objects to keep track of information about drivers free IO manager from knowing about individual drivers. It just follows a pointer to locate a driver. Provides portability and allows new drivers to be easily loaded.

NT IO manager needs to know nothing about the file system to do these tasks, IO is multilayered.

• In NT low level IO is asynchronous – an application that issues an IO request doesn’t have to wait for data to be transferred – can continue to process while transfer is taking place. Asynchronous IO must be specified as a property of the file device object. However process must not make another request of same device object. This could cause contention. (As well, in a multiprocessing environment, two processors could try to access the same devices.) To avoid this, NT uses spin locks, which reside in global memory. The spin lock is a locking mechanism associated with a global data structure called the DPC (deferred procedure call) queue. Before accessing a shared device, the kernel must get the spin lock – if it can’t, it waits.
• Unique feature of NT device drivers is provision for power failure recovery. NT is equipped with uninterruptible power supply (UPS) that gives user ample warning of impending power failures and shuts everything down in a systematic way. If the computer has a battery back-up for memory, NT provides a warm-boot that allows IO manager to recover IO operations that were in progress when failure happened.

Handled mostly by IO supervisor. Channel command allows for intelligent use of commands – if one channel to do a write leads to a DASD that requires a rotation to put the R/W head in the right place then another channel will be selected. Channels are equipped with microprocessors that allow for sophisticated data management functions. Can do:

• Error detection and correction
• Command re-try
• Multiple track operation
• Channel switching

Virtual IO is a module in MVS used to handle temporary files by using virtual storage. Application isn’t aware it is not using DASD because VIO simulates a virtual track for the DASD and writes to storage only when virtual track is full.

Advantage of VIO is elimination of device allocation and data management overhead.