操作系统课件：07_Input and Output

1、1Input/OutputChapter 55.1 Principles of I/O hardware5.2 Principles of I/O software5.3 I/O software layers5.4 Disks5.5 Clocks5.6-8 Terminals2Principles of I/O HardwareSome typical device, network, and data base rates3Device ControllersI/O devices have components:mechanical component electronic compon

2、entThe electronic component is the device controllermay be able to handle multiple devicesControllers tasksconvert serial bit stream to block of bytesperform error correction as necessarycommunicate with CPU4Memory-Mapped I/O (1)Separate I/O and memory spaceMemory-mapped I/OHybrid5Memory-Mapped I/O

3、(2)(a) A single-bus architecture(b) A dual-bus memory architecture6Direct Memory Access (DMA)Operation of a DMA transferMulti-channel DMA ControllerFlight Mode: Device Memory, Device Device, Memory MemoryVirtual Address or Physical AddressUncacheable memory section for DMA7Interrupts RevisitedInterr

4、upt ControllerInterrupt VectorPrecise and Imprecise Interrupt8Principles of I/O SoftwareGoals of I/O Software (1)Device independenceprograms can access any I/O device without specifying device in advance (floppy, hard drive, or CD-ROM)Uniform namingname of a file or device a string or an integernot

5、depending on which machineError handlinghandle as close to the hardware as possible9Goals of I/O Software (2)Synchronous vs. asynchronous transfersblocked transfers vs. interrupt-drivenBufferingdata coming off a device cannot be stored in final destinationSharable vs. dedicated devicesdisks are shar

6、abletape drives would not be10Programmed I/O (1)Steps in printing a string11Programmed I/O (2)Writing a string to the printer using programmed I/O - busy waiting12Interrupt-Driven I/OWriting a string to the printer using interrupt-driven I/OCode executed when print system call is madeInterrupt servi

7、ce procedure13I/O Using DMAPrinting a string using DMAcode executed when the print system call is madeinterrupt service procedure14I/O Software LayersLayers of the I/O Software System15Interrupt Handlers (1)Interrupt handlers are best hiddenhave driver starting an I/O operation block until interrupt

8、 notifies of completionInterrupt procedure does its taskthen unblocks driver that started it16Interrupt Handlers (2)Steps must be performed in software after interrupt completedSave registers not already saved by interrupt hardwareSet up context for interrupt service procedureSet up stack for interr

9、upt service procedureAcknowledge interrupt controller, reenable interruptsCopy registers from where savedRun service procedure Set up MMU context for process to run nextLoad new process registersStart running the new process17Device DriversLogical position of device drivers is shown hereCommunicatio

10、ns between drivers and device controllers goes over the busBlock devices and Character devices18Tasks of Device DriversAccept abstract requestsCheck input parametersTranslate from abstract to concreteCheck if device is in useIssue commands to controller(Block)Check errorsReturn (error) to caller19De

11、vice-Independent I/O Software (1)Functions of the device-independent I/O softwareUniform interfacing for device driversBufferingError reportingAllocating and releasing dedicate devicesProviding a device-independent block size20Device-Independent I/O Software (2)(a) Without a standard driver interfac

12、e(b) With a standard driver interfaceFile operations: open(), read(), write(), close()21Device-Independent I/O Software (3)(a) Unbuffered input(b) Buffering in user space(c) Buffering in the kernel followed by copying to user space(d) Double buffering in the kernel22Device-Independent I/O Software (

13、4)Networking may involve many copiesError ReportingProgram ErrorDevice ErrorDevice ManagementBlock Size2324User-Space I/O Software Layers of the I/O system and the main functions of each layerSpooling directory50 Years Old!13th September 1956 The IBM RAMAC 35080000 times more data on the 8GB 1-inch

14、drive in his right hand than on the 24-inch RAMAC one in his leftWhat does the disk look like?Some parameters2-30 heads (platters * 2)diameter 14 to 2.5700-20480 tracks per surface16-1600 sectors per tracksector size: 64-8k bytes512 for most PCsnote: inter-sector gapscapacity: 20M-100Gmain adjective

15、s: BIG, slowDisk overheadsTo read from disk, we must specify:cylinder #, surface #, sector #, transfer size, memory addressTransfer time includes: Seek time: to get to the track Latency time: to get to the sector and Transfer time: get bits off the diskTrackSectorSeek TimeRotationDelayModern disksBa

16、rracuda 180Cheetah X15 36LPCapacity181GB36.7GBDisk/Heads12/244/8Cylinders24,24718,479Sectors/track609485Speed7200RPM15000RPMLatency (ms)4.172.0Avg seek (ms)7.4/8.23.6/4.2Track-2-track(ms)0.8/1.10.3/0.4Disk StructureDisk drives addressed as 1-dim arrays of logical blocksthe logical block is the small

17、est unit of transferThis array mapped sequentially onto disk sectorsAddress 0 is 1st sector of 1st track of the outermost cylinderAddresses incremented within track, then within tracks of the cylinder, then across cylinders, from innermost to outermostTranslation is theoretically possible, but usual

18、ly difficultSome sectors might be defectiveNumber of sectors per track is not a constantNon-uniform #sectors / trackReduce bit density per track for outer layers (Constant Linear Velocity, typically HDDs)Have more sectors per track on the outer layers, and increase rotational speed when reading from

19、 outer tracks (Constant Angular Velcity, typically CDs, DVDs)Disk FormattingAfter manufacturing disk has no informationIs stack of platters coated with magnetizable metal oxideBefore use, each platter receives low-level formatFormat has series of concentric tracksEach track contains some sectorsTher

20、e is a short gap between sectorsPreamble allows h/w to recognize start of sectorAlso contains cylinder and sector numbersData is usually 512 bytesECC field used to detect and recover from read errorsCylinder SkewWhy cylinder skew?How much skew?Example, if10000 rpmDrive rotates in 6 msTrack has 300 s

21、ectorsNew sector every 20 sIf track seek time 800 s40 sectors pass on seekCylinder skew: 40 sectorsFormatting and PerformanceIf 10K rpm, 300 sectors of 512 bytes per track153600 bytes every 6 ms 24.4 MB/sec transfer rateIf disk controller buffer can store only one sectorFor 2 consecutive reads, 2nd

22、sector flies past during memory transfer of 1st trackIdea: Use single/double interleaving Disk PartitioningEach partition is like a separate diskSector 0 is MBR Contains boot code + partition tablePartition table has starting sector and size of each partitionHigh-level formattingDone for each partit

23、ionSpecifies boot block, free list, root directory, empty file systemWhat happens on boot?BIOS loads MBR, boot program checks to see active partitionReads boot sector from that partition that then loads OS kernel, etc.Disk SchedulingThe operating system tries to use hardware efficientlyfor disk driv

24、es having fast access time, disk bandwidthAccess time has two major componentsSeek time is time to move the heads to the cylinder containing the desired sectorRotational latency is additional time waiting to rotate the desired sector to the disk head.Minimize seek timeSeek time seek distanceDisk ban

25、dwidth is total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.Disk Scheduling (Cont.)Several scheduling algos exist service disk I/O requests. We illustrate them with a request queue (0-199).98, 183, 37, 122, 14,

26、124, 65, 67Head pointer 53FCFSIllustration shows total head movement of 640 cylinders.SSTFSelects request with minimum seek time from current head positionSSTF scheduling is a form of SJF scheduling may cause starvation of some requests.Illustration shows total head movement of 236 cylinders.SSTF (C

27、ont.)SCANThe disk arm starts at one end of the disk, moves toward the other end, servicing requests head movement is reversed when it gets to the other end of disk servicing continues.Sometimes called the elevator algorithm.Illustration shows total head movement of 208 cylinders.SCAN (Cont.)C-SCANPr

28、ovides a more uniform wait time than SCAN.The head moves from one end of the disk to the other.servicing requests as it goes. When it reaches the other end it immediately returns to beginning of the diskNo requests serviced on the return trip.Treats the cylinders as a circular list that wraps around

29、 from the last cylinder to the first one.C-SCAN (Cont.)C-LOOKVersion of C-SCANArm only goes as far as last request in each direction,then reverses direction immediately, without first going all the way to the end of the disk. C-LOOK (Cont.)Selecting a Good AlgorithmSSTF is common and has a natural a

30、ppealSCAN and C-SCAN perform better under heavy loadPerformance depends on number and types of requestsRequests for disk service can be influenced by the file-allocation method.Disk-scheduling algorithm should be a separate OS module allowing it to be replaced with a different algorithm if necessary

31、.Either SSTF or LOOK is a reasonable default algorithmHandling ErrorsA disk track with a bad sectorSolutions:Substitute a spare for the bad sector (sector sparing)Shift all sectors to bypass bad one (sector forwarding)RAID MotivationDisks are improving, but not as fast as CPUs1970s seek time: 50-100

32、 ms.2000s seek time: 5 ms.Factor of 20 improvement in 3 decadesWe can use multiple disks for improving performanceBy Striping files across multiple disks (placing parts of each file on a different disk), parallel I/O can improve access timeStriping reduces reliability 100 disks have 1/100th mean tim

33、e between failures of one diskSo, we need Striping for performance, but we need something to help with reliability / availabilityTo improve reliability, we can add redundant data to the disks, in addition to StripingRAIDA RAID is a Redundant Array of Inexpensive DisksIn industry, “I” is for “Indepen

34、dent”The alternative is SLED, single large expensive diskDisks are small and cheap, so its easy to put lots of disks (10s to 100s) in one box for increased storage, performance, and availabilityThe RAID box with a RAID controller looks just like a SLED to the computerData plus some redundant informa

35、tion is Striped across the disks in some wayHow that Striping is done is key to performance and reliability.Some Raid IssuesGranularityfine-grained: Stripe each file over all disks. This gives high throughput for the file, but limits to transfer of 1 file at a time coarse-grained: Stripe each file o

36、ver only a few disks. This limits throughput for 1 file but allows more parallel file accessRedundancyuniformly distribute redundancy info on disks: avoids load-balancing problems concentrate redundancy info on a small number of disks: partition the set into data disks and redundant disksRaid Level

37、0Level 0 is nonredundant disk arrayFiles are Striped across disks, no redundant infoHigh read throughputBest write throughput (no redundant info to write)Any disk failure results in data lossReliability worse than SLEDStripe 0Stripe 4Stripe 3Stripe 1Stripe 2Stripe 8Stripe 10Stripe 11Stripe 7Stripe 6

38、Stripe 5Stripe 9data disksRaid Level 1Mirrored DisksData is written to two places On failure, just use surviving diskOn read, choose fastest to read Write performance is same as single drive, read performance is 2x betterExpensivedata disksmirror copiesStripe 0Stripe 4Stripe 3Stripe 1Stripe 2Stripe

39、8Stripe 10Stripe 11Stripe 7Stripe 6Stripe 5Stripe 9Stripe 0Stripe 4Stripe 3Stripe 1Stripe 2Stripe 8Stripe 10Stripe 11Stripe 7Stripe 6Stripe 5Stripe 9Parity and Hamming CodesWhat do you need to do in order to detect and correct a one-bit error ?Suppose you have a binary number, represented as a colle

40、ction of bits: , e.g. 0110Detection is easyParity:Count the number of bits that are on, see if its odd or evenEVEN parity is 0 if the number of 1 bits is evenParity() = P0 = b0 b1 b2 b3Parity() = 0 if all bits are intactParity(0110) = 0, Parity(01100) = 0Parity(11100) = 1 = ERROR!Parity can detect a

41、 single error, but cant tell you which of the bits got flippedParity and Hamming CodeDetection and correction require more workHamming codes can detect double bit errors and detect & correct single bit errors7/4 Hamming Code h0 = b0 b1 b3h1 = b0 b2 b3h2 = b1 b2 b3H0() = 0H1() = 1H2() = 0Hamming() =

42、= If a bit is flipped, e.g. Hamming() = = compared to , are in error. Error occurred in bit 5.Raid Level 2Bit-level Striping with Hamming (ECC) codes for error correctionAll 7 disk arms are synchronized and move in unisonComplicated controllerSingle access at a timeTolerates only one error, but with

43、 no performance degradation data disksBit 0Bit 3Bit 1Bit 2Bit 4Bit 5Bit 6ECC disksRaid Level 3Use a parity diskEach bit on the parity disk is a parity function of the corresponding bits on all the other disksA read accesses all the data disksA write accesses all data disks plus the parity diskOn dis

44、k failure, read remaining disks plus parity disk to compute the missing datadata disksParity diskBit 0Bit 3Bit 1Bit 2ParitySingle parity disk can be usedto detect and correct errorsRaid Level 4Combines Level 0 and 3 block-level parity with StripesA read accesses all the data disksA write accesses al

45、l data disks plus the parity diskHeavy load on the parity diskdata disksParity diskStripe 0Stripe 3Stripe 1Stripe 2P0-3Stripe 4Stripe 8Stripe 10Stripe 11Stripe 7Stripe 6Stripe 5Stripe 9P4-7P8-11Raid Level 5Block Interleaved Distributed ParityLike parity scheme, but distribute the parity info over all disks (as well as data over all disks)Better read performance, large write performanceReads can outperform SLEDs and RAID-0data and parity disksStripe 0Stripe 3Stripe 1Stripe 2P0-3Stripe 4Stripe 8P8-11Stripe 10P4-7Stripe 6S