CSE 380 Computer Operating SystemsI/O DevicesPentium Bus ArchitectureDevice ControllersAccessing the deviceMemory Mapped I/OI/O ProgrammingI/O Code with Busy WaitingI/O Code with InterruptsI/O with Direct Memory AccessMechanism of DMA TransferSecondary Storage ManagementDisk DrivesTypical Disk ParametersDisk FormattingDisk Formatting (1)Disk Formatting (2)Disk Formatting (3)Disk AccessDisk-Head SchedulingDisk-Arm Scheduling: FCFSDisk-Arm Scheduling:SSFDisk-Arm Scheduling AlgorithmsFault Tolerance for DisksError Correction Code in SectorsHamming Codes (1950’s)Error Correction in Hamming CodesError Correction ContinuedBad SectorsRead ErrorsReliability by RedundancyRAID Redundant Array of Independent DisksRAID Level 0Slide 35RAID Level 1RAID Level 2RAID Levels 3-51CSE 380Computer Operating SystemsInstructor: Insup LeeUniversity of PennsylvaniaFall 2003Lecture Note on Disk I/O2I/O DevicesStorage devicesFloppy, Magnetic disk, Magnetic tape, CD-ROM, DVD…User interactionKeyboard, mouse, monitor, sound card, printer, modem ….Significant part of OS code deals with I/O devicesCommunication with device driversError handlingInterrupt managementConvenient interfaces3Pentium Bus Architecture4Device ControllersI/O devices have components:mechanical component electronic componentThe electronic component is the device controllermay be able to handle multiple devicesShould have a standardized interfaceController's tasksconvert serial bit stream to block of bytesperform error correction as necessaryController interfaceDevice registersData buffers for reading/writing data (separate from main memory, or not?)5Accessing the device Basically, two choices: I/O instructions that read/write I/O ports, or memory mapped I/OI/O instructions can be of the formIN R, P R is a register, P is a port numberIn memory mapped I/O, no special instructions, but some addresses in virtual memory correspond to portsMOV R, L L can be an address which is reserved for a specific devicePentium provides both schemesI/O ports numbered 0 to 64K used for control informationMemory addresses from 64K to 1M used for device buffers6Memory Mapped I/OIn an instruction such as MOV R, L, L can beA location in main memory, orA control register, or address in data buffer, of a specific I/O deviceI/O space viewed as an extension of main memory, and addressed in the same wayOf course, no overlap between the two address spacesAdvantagesDevice drivers are written in CProtection managed by pages accessible in each user spaceSavings in number of instructionsIssuesCaching must be disabled for I/O pages (why?)How to separate real memory references from I/O ones7I/O Programming Uniform naming of devicesIn Unix, special directories such as /dev/lp, /dev/ttyDevice IndependenceBuffering of data user-space or kernel-space or double bufferingDriver routinesBusy waiting vs. Interrupt driven vs. DMA8I/O Code with Busy WaitingGoal: user wants to send N bytes from Buffer to an I/O device (e.g. printer or floppy)Device controller has registers for status and for putting dataBasic approach (too wasteful for CPU):Copy data into kernel buffer B;for (i=0; i< N; i++) { /* wait for device to be free */ while (*DeviceStatusReg != READY);*DeviceDataReg = B[i]; }9I/O Code with InterruptsGoal: To let CPU schedule other processes while device is busy processing dataCode for driver:Copy data into kernel buffer B while (*DeviceStatusReg != ready);*DeviceDataReg = B[0]; /* Do only the first step */ InvokeScheduler();Code for interrupt handler:if (N == 0) Wakeup(); /* unblock the process */else {DeviceDataReg = B[i];N--; i++;};ResetInterrupt(); /*Notify device as an ack */10I/O with Direct Memory AccessGoal: Device should interrupt CPU only after the entire transferSolution: Provide direct access between memory and device so that data can be copied into memoryDMA Controller: separate unit that manages thisDriver routineCopy data into kernel spaceSet up DMA controller registersSchedule another processInterrupt handlerAck the interruptWakeup User11Mechanism of DMA TransferA program running on CPU sets up the registers in DMA controller (e.g. write N bytes into memory starting at location XYZ)Is the address XYZ virtual or physical ?DMA controller sets up the registers in device controller to request the transferOriginal request may be divided into chunksDisk controller transfers the data directly into memoryBus architecture should resolve contention for memoryDisk controller notifies DMA controllerWhen the original request is entirely processed, DMA controller interrupts the CPU12Secondary Storage ManagementWhy secondary storage?1main memory too small2main memory volatileDevices: Disks, Tapes, DrumsDisks are critical components For virtual memory managementStoring filesDisk technology hasn’t changed much compared to processor technology (esp., speed)13Disk DrivesTracks and Cylinders14Typical Disk ParametersCompare Seek time, rotation time, transfer time15Disk FormattingTypical sector is 512 bytesPreamble identifying start code and sector addressDataError correction code (16 bits). At least detecting errors possible with probability almost 1Cylinder skew:After reading an entire track, as head is moved across a cylinder, seeking next sector shouldn’t cause waiting for full rotationInterleaving sectors:As a sector is copied into controller buffer, it needs to be copied into main memory. So next sector should not be adjacent if we wish to avoid waiting for one full rotation16Disk Formatting (1)A disk sector17Disk Formatting (2)An illustration of cylinder skew18Disk Formatting (3)No interleavingSingle interleavingDouble interleaving19Disk AccessPhysical address on a disk(cylinder number, head number, sector number)Sectors can be given logical numbers that get decoded by Disk ControllerDesign considerationsSeek time (moving head to correct cylinder) and rotational latency time (waiting for correct sector) are greater than data transfer time (time to read)Lots of errors possible (bad sectors, bad bits)Caching blocks that happen to pass under disk head commonly used20Disk-Head SchedulingTime required to read or write a disk block determined by 3 factors1. Seek time2. Rotational