Disks and Disk SchedulingOverviewAnatomy of a Hard DriveSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Disk Scheduling AlgorithmsSlide 31First Come First Served (FCFS)SCANLOOKCSCANC-LOOKSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Shortest Seek Time First (SSTF)Shortest Positioning Time First (SPTF)Weighted Shortest Positioning Time First (WSPTF)ConclusionsDisks and Disk SchedulingOriginal lecture given by Steve Muckle on Monday, March 31st 2003Additional Slides Taken from Eno Thereska’s July Systems TalkBrian RailingFriday, October 31st 200315-410 Fall 2003Carnegie Mellon University 2OverviewAnatomy of a Hard DriveCommon Disk Scheduling AlgorithmsCarnegie Mellon University 5Anatomy of a Hard DriveOn the outside, a hard drive looks like thisTaken from “How Hard Disks Work”http://computer.howstuffworks.com/hard-disk2.htmCarnegie Mellon University 6Anatomy of a Hard DriveIf we take the cover off, we see that there actually is a “hard disk” insideTaken from “How Hard Disks Work”http://computer.howstuffworks.com/hard-disk2.htmCarnegie Mellon University 7Anatomy of a Hard DriveA hard drive usually contains multiple disks, called plattersThese spin at thousands ofRPM (5400,7200, etc)Taken from “How Hard Disks Work”http://computer.howstuffworks.com/hard-disk2.htmCarnegie Mellon University 8Anatomy of a Hard DriveInformation is written to and read from the platters by the read/write heads on the disk armTaken from “How Hard Disks Work”http://computer.howstuffworks.com/hard-disk2.htmCarnegie Mellon University 9Anatomy of a Hard DriveBoth sides of each platter store informationEach side ofa platter iscalled asurfaceEach surfacehas its ownread/write headTaken from “How Hard Disks Work”http://computer.howstuffworks.com/hard-disk2.htmCarnegie Mellon University 10Anatomy of a Hard DriveHow are the surfaces organized?a surfaceCarnegie Mellon University 11Anatomy of a Hard DriveEach surface is divided by concentric circles, creating trackstracksCarnegie Mellon University 12Anatomy of a Hard DriveThe matching tracks on all surfaces are collectively called a cylinderCarnegie Mellon University 13Anatomy of a Hard DriveThese tracks are further divided into sectorsCarnegie Mellon University 14Anatomy of a Hard DriveA sector is the smallestunit of data transfer toor from the diskMost modern harddrives have 512 bytesectorsa sectorCarnegie Mellon University 15Anatomy of a Hard DriveDoes this mean that sectorson the outside of a surfaceare larger than those onthe inside?Modern hard drivesfix this with zoned bit recordingTaken from “Reference Guide – Hard Disk Drives”http://www.storagereview.com/map/lm.cgi/zoneCarnegie Mellon University 16Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headdesired sectordisk rotatescounter-clockwiseCarnegie Mellon University 17Anatomy of a Hard DriveWe need to do two things to transfer a sector1. Move the read/write head to the appropriate track (seek)2. Wait until the desired sector spins aroundCarnegie Mellon University 18Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 19Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 20Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 21Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 22Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 23Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 24Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 25Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 26Anatomy of a Hard DriveWhy don’t we read in a sector from the diskread/write headCarnegie Mellon University 27Anatomy of a Hard DriveOn average, we will have to move the read/write head over half the tracksThe time to do this is the average seek time, and is ~10msWe will also have to wait half a rotationThe time to do this is rotational latency, and on a 5400 rpm drive is ~5.5msCarnegie Mellon University 28Anatomy of a Hard DriveThere are many other things that determine overall disk access time including - settle time, the time to stabilize the read/write head after a seek- command overhead, the time for the disk to process a command and start doing somethingThe things are fairly minor compared to seek time and rotational latencyCarnegie Mellon University 29Anatomy of a Hard DriveTotal drive random access time is on the order of 15 to 20 millisecondsBut wait! Disk transfer rates are tens of MbytesOh man, disks are slowWhat can we, as operating system programmers, do about this?Carnegie Mellon University 30Disk Scheduling AlgorithmsThe goal of a disk scheduling algorithm is to be nice to the diskWe can help the disk by giving it requests that are located close to each other on the diskThis minimizes seek time, and possibly rotational latencyThere exist a variety of ways to do thisCarnegie Mellon University 31Disk Scheduling AlgorithmsWhat the OS knows about the disk?Logical Block NumbersInterface: IDE or SCSIWhat happened to sectors, tracks, etc?They are hidden behind the logical block numbersHow are they used?File systems assign logical blocks to filesCarnegie Mellon University 32First Come First Served (FCFS)Requests are sent to the disk as they are generated by the OSTrivial to implementFair – no request will be starved because of its location on the diskProvides an unacceptably high mean response timeCarnegie Mellon University 33SCANSend requests in ascending cylindersWhen last cylinder is reached, reverse the scanMean response time is worse than SSTF, but better than FCFSBetter response time variance than SSTFUnfair – why?Carnegie Mellon University 34LOOKJust like SCAN – sweep back and forth through cylindersIf
View Full Document
Unlocking...