CHAPTER11: I/O MANAGEMENT AND DISK SCHEDULINGSUBTOPIC: 11.5 DISK SHCHEDULINGNAZIRAH BINTI MOHAMMED ANWAR B031210271NUR HUDA ATHIRAH BINTI ABDUL LATIB B031210358NUR ATIQAH BINTI ABD RASHID B031210185LIM ZHEW SHENG B031210379WONG POH LING B031210033
Disk Scheduling Over the last 40 years, the increase in the speed ofprocessors and main memory has far outstripped thatfor disk access. Disk are currently at least four orders of magnitudeslower than main memory. The performance of disk storage subsystem is of vitalconcern, much research has focus on improving thatperformance.INTRODUCTION
• The actual details of disk I/O operationdepend on the computer system, theoperation system, and the nature of theI/O channel and disk controller hardware.• The figure below shows a general timingdiagram of disk I/O transfer:
When the disk drive is operating, the disk isrotating at constant speed.To read or write, the head must be positioned atthe desired track and at the beginning of thedesired sector of that track.Track selection involves moving the head in amoveable-head system or electronicallyselecting one head on a fixed-system.
Seek Time -Seek timeis for the disk arm to move the heads to the cylindercontaining the desired sector. -It is also measures the amount of time required for theread/write heads to move between tracks over the surface of theplatters. -It turns out that this is a difficult quantity to pin down. -Consists of two key components: access arm is up to spend.The time taken totraverse the tracksthat have to becrossed once thea) Theinitialstartuptime
Average Seek Time = sum of the time of all possible seekall possible seek.- The time waiting for the disk to rotate the desiredsector to the disk head.-Time taken to transfer the data.-The time it takes to transfer a block ofbits, typically a sector, under the read/write head.EQUATIONRotational Delay(r)Transfer Time(T
Two different I/O operations that illustrate the danger of relying onaverage values. Consider a disk with an advertised average seek time of 4 ms, rotationspeed of 7500 rpm, and 512-byte sectors with 500 sectors per track.Suppose that we wish to read a file consisting of 2500 sectors for a totalof 1.28 Mbytes. (Estimate the total time for the transfer). 1) Assume that the file is stored as compactly as possible on thedisk, (the file occupies all of the sectors on 5 adjacent tracks, 5 tracks x500 sectors/track = 2500 sectors). Also known as sequentialorganization. So, the time to read the first track is as follows :Average seek 4msRotational delay 4 msRead 500 sectors 8 ms16 ms
Suppose that the remaining tracks can now be read with essentiallyno seek time. (I/O operation can keep up with the flow from thedisk). Then, deal with rotational delay for each succeeding track. Thus, each successive track is read in 4 + 8 = 12 rmms.To read theentire file : Total time = 16 + (4 x 12) = 64 ms = 0.064 seconds 2) Calculate the time required to read the same data usingrandom access rather than sequential access, (accesses to thesectors are distributed randomly over the disk). Average seek 4 msRotational delay 4 msRead 1 sectors 0.016 ms8.016 ms For each sector we have : Total time = 2500 x 8.016 = 20040 ms = 20.04 secondsAverage seek 4 msRotational delay 4 msRead 500 sectors 8 ms16 ms
If the sector requests involve selection of tracks atrandom, then the performance of the disk I/O systemwill be as poor as possible. To improve matters, need toreduce average time spent on seeks. is useful as a benchmark against which to evaluateother techniques.RANDOM SCHEDULING
The simplest form of scheduling, which processesitems from the queue in sequential order. The advantage of being fair, because everyrequest is honored and the requests are honoredin the order received. Normally in FIFO disk accesses are in the sameorder as the request were originally received. With FIFO, only a few processes that requireaccess and if many of the request are to clusteredfile sector, then we can hope for goodperformance. But, if many processes competing the disk, it maybe profitable to consider a more sophisticatedscheduling policy.
SHORTEST SERVICE TIME FIRST Is to select the disk I/O request that require the least movement of thedisk arm from its current position. Always choose to incur the minimum seek time. But still cannot make sure the average seek time will be minimum too. However, this should provide better performance than FIFO. Arm move in two directions. Random tie-breaking algorithm maybe used to resolve cases of equaldistances.System based on priority (PRI), the control of thescheduling is outside the control of disk managementsoftware.Often short batch jobs and interactive jobs are givenhigher priority than longer jobs that require longercomputation.However, longer jobs may have to wait excessivelylong times.So that, this type of policy tends to be poor forDatabase Systems.PRIORITY
a.k.a elevator algorithm because it operates like the elevator able to prevent starvation the arm move in one direction only satisfying request en route until there are no more requests available the service direction reversed, the scan proceed in opposite direction SCAN policy is biased against the area most recently traversed Thus, does not exploit locality as well as SSTF SCAN policy favours jobs whose request are for tracks nearest to bothinnermost and outermost track Also, favours the latest-arriving jobs a.k.a circular SCAN restrict scanning to one direction only when the last track has been visited in one direction, the arm is returnedto the opposite end of the disk and the scan begins again reduces delay experienced by new requestsC-SCAN
to avoid ‘arm stickiness’ where the arm does not move for a considerableamount period of time happens due to a process repeatedly request for a track, thus monopolizingthe entire device in N-step-SCAN, the disk request queue is segmented into subqueue oflength N subqueues are processed one at a time, using SCAN new requests must be added to some other queue for FSCAN uses two subqueues all requests are in one queue while scan begins the second subqueue is empty all new request are put into the second subqueue thus, new requests will be proceed only when the old requests are done