Presentation 4 Group A1 Professor Mohamed Khalil Anita Kanuganti Hemanth Rao DISK SCHEDULING IN AN OPERATING SYSTEM Agenda Disk Structure Why Disk Scheduling Example Scheduling Algorithms 1 2 3 4 5 6 FCFS SSTF SCAN C SCAN LOOK C LOOK Comparison of different Algorithms Selection of right scheduling Algorithm References Disk Structure A 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 onedimensional 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 2 Mapping hides defective sectors by substituting them with spare sectors from elsewhere in the disk 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 Disk bandwidth The total number of bytes transferred divided by the total time between the first request for service and the completion of the last transfer To reduce the Access time which is caused by 1 2 Seek time The time for the disk arm to move the heads to the cylinder containing the desired sector Rotational Latency The additional time waiting for the disk to rotate the desired sector to the disk 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 Algorithms FCFS First Come First Served 1 2 It is Fair no starvation Disadvantage Low performance due to long swings from one part of the disk to another FCFS Scheduling Head is at 53 98 183 37 122 14 124 65 67 200 150 100 50 0 Scheduling Algorithms cont SSTF Scheduling Shortest seek time first 1 2 3 Selects minimum seek time from the current position Better Performance Disadvantage Causes starvation of some requests i e A request for a remote part of the disk may never get serviced SSTF Head is at 53 98 183 37 122 14 124 65 67 200 150 100 50 0 Scheduling 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 SCAN Head is at 53 98 183 37 122 14 124 65 67 200 150 100 50 0 Scheduling 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 time C SCAN Head is at 53 98 183 37 122 14 124 65 67 250 200 150 100 50 0 Scheduling Algorithms cont LOOK C LOOK Similar to SCAN but reverses direction when hits the last request in the current direction 1 C LOOK only moves similar to C SCAN 1 2 3 Much better performance Advantage since it does not has to go all the way to the end of the disk Most widely used and optimized C LOOK Head is at 53 98 183 37 122 14 124 65 67 200 150 100 50 0 Comparison FCFS is not mostly used because of its low speed and delay SSTF is common and has a natural appeal SCAN C SCAN perform better for systems that place a heavy load on the disk because they are less likely to have the starvation problem LOOK C LOOK perform much better Selection of right Algorithm The criteria of selecting algorithm is based on 1 2 3 Number of requests Type of requests File Allocation Method References Applied Operating System Concepts by Abraham Silberschatz Peter Galvin Greg Gagne Questions