|
FALL 2000 Lecture Notes 8: DEVICE MANAGEMENT 2 SEEK STRATEGIES IO device handler uses strategy to allocate a device among many processes. Scheduling algorithms must do the following: Minimize arm movement To look at these algorithms, will imagine a simple disk with the following characteristics:
1. Good old First Come, First Served (FCFS) Easy to program, fair to users. Example: while reading from track 15 the following request arrives (tracks 4,40,11,35,7,14)
TOTAL = 135 ms Average # tracks / request = 22.5 Strategy has many disadvantages:
2. Shortest seek time first(SSFT) 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:
TOTAL = 47 ms Average # tracks/request = 7.83 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. SCAN type algorithms 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: LOOK (also known as elevator algorithm) Looks ahead for a request before going to service it. Assuming that arm is moving inwards (towards higher numbered sectors), the same example is as follows:
TOTAL 61 ms Average # tracks / request 10.16 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. N-Step SCAN 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. C-SCAN (circular scan) 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. C-LOOK 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?
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:
Device Management 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:
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:
IO manager creates a driver object during booting. Creates a driver object for each device to be handled by this driver.
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.
MVS Device Management 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:
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.
|