Presentation-4 Group-A1DISK SCHEDULING IN AN OPERATING SYSTEMAgendaDisk StructureDisk structure contd, Advantages of Mapping:Why Disk Scheduling ?ExampleScheduling AlgorithmsFCFS SchedulingScheduling Algorithms cont,SSTFSlide 12SCANSlide 14C-SCANSlide 16C-LOOKComparisonSelection of right AlgorithmReferencesQuestions?Presentation-4 Group-A1Professor Mohamed KhalilAnita KanugantiHemanth RaoDISK SCHEDULING IN AN OPERATING SYSTEMAgendaDisk StructureWhy Disk Scheduling?ExampleScheduling Algorithms1.1.FCFSFCFS2.2.SSTFSSTF3.3.SCANSCAN4.4.C-SCANC-SCAN5.5.LOOKLOOK6.6.C-LOOKC-LOOKComparison of different AlgorithmsComparison of different AlgorithmsSelection of right scheduling AlgorithmSelection of right scheduling AlgorithmReferencesReferencesDisk StructureA hard disk drive(usually called “drive”) records data on the surface of metal plates called platters that are coated with a substance containing ground-up iron, or other substances that allow zeros and ones to be recorded as tiny spots of magnetism.Modern disk drives are addressed as large one-dimensional arrays of logical blocks (smallest unit of transfer) which are mapped onto the sectors of the disk sequentially.Mapping converts a logical block number into an old-style disk address that consists of a cylinder number, a track,number within that cylinder and a sector number within that track.Disk structure contd, Advantages of Mapping:Advantages of Mapping:1. Mapping hides defective sectors by substituting them with spare sectors from elsewhere in the disk.2. Number of sectors per track is not constant. This is solved in modern disks by organizing into “zones”.Why Disk Scheduling ?To use hardware efficiently.To increase disk bandwidth:1.1.Disk bandwidth—The total number of bytes Disk bandwidth—The total number of bytes transferred, divided by the total time between the transferred, divided by the total time between the first request for service and the completion of the first request for service and the completion of the last transfer.last transfer.To reduce the Access time which is caused by:1.1.Seek time -- The time for the disk arm to move the Seek time -- The time for the disk arm to move the heads to the cylinder containing the desired sector.heads to the cylinder containing the desired sector.2.2.Rotational Latency – The additional time waiting for Rotational Latency – The additional time waiting for the disk to rotate the desired sector to the disk the disk to rotate the desired sector to the disk head.head.Example Consider, a disk queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67 in that order.Scheduling AlgorithmsFCFS—First Come First Served1.1.It is Fair– no starvationIt is Fair– no starvation2.2.Disadvantage– Low performance due to Disadvantage– Low performance due to long swings from one part of the disk to long swings from one part of the disk to anotheranotherFCFS SchedulingHead is at 5398, 183, 37, 122, 14, 124, 65, 67 050100150200Scheduling Algorithms cont,SSTF Scheduling– Shortest-seek-time first1.1.Selects minimum seek time from the Selects minimum seek time from the current positioncurrent position2.2.Better PerformanceBetter Performance3.3.Disadvantage: Causes starvation of Disadvantage: Causes starvation of some requests i.e., A request for a some requests i.e., A request for a remote part of the disk may never get remote part of the disk may never get servicedservicedSSTFHead is at 53. 98, 183, 37, 122, 14, 124, 65, 67 050100150200Scheduling Algorithms cont,SCAN Scheduling—Scans from the start of the disk to end servicing all requests and reverses back servicing the remainder of requests just like an Elevator(also called Elevator Algorithm)Disadvantage: If 2 requests is in front of it and it has to scan the whole disk and return back serve the rest of it.SCANHead is at 53. 98, 183, 37, 122, 14, 124, 65, 67 050100150200Scheduling Algorithms cont,C-SCAN– Similar to SCAN but with a difference that when head reaches at the end of the disk, it immediately returns to the beginning of the disk,without servicing any requests on the return trip.More Uniform wait timeC-SCANHead is at 53. 98, 183, 37, 122, 14, 124, 65, 67 050100150200250Scheduling Algorithms cont,LOOK & C-LOOK—Similar to SCAN but reverses direction when hits the last request in the current direction1.1.C-LOOK only moves similar to C-SCAN C-LOOK only moves similar to C-SCAN 1.1.Much better performanceMuch better performance2.2.Advantage since it does not has to go all Advantage since it does not has to go all the way to the end of the diskthe way to the end of the disk3.3.Most widely used and optimizedMost widely used and optimizedC-LOOKHead is at 53. 98, 183, 37, 122, 14, 124, 65, 67 050100150200ComparisonFCFS is not mostly used because of its low speed and delaySSTF is common and has a natural appealSCAN & C-SCAN perform better for systems that place a heavy load on the disk, because they are less likely to have the starvation problemLOOK & C-LOOK perform much betterSelection of right AlgorithmThe criteria of selecting algorithm is based on:1.1.Number of requestsNumber of requests2.2.Type of requestsType of requests3.3.File Allocation MethodFile Allocation MethodReferences“Applied Operating System Concepts” by Abraham Silberschatz, Peter Galvin, Greg