Operating system chapter 11

Operating system chapter 11

اسلاید 1: 1I/O Management and Disk SchedulingChapter 11

اسلاید 2: 2Categories of I/O DevicesHuman readableUsed to communicate with the userPrintersVideo display terminalsDisplayKeyboardMouse

اسلاید 3: 3Categories of I/O DevicesMachine readableUsed to communicate with electronic equipmentDisk and tape drivesSensorsControllersActuators

اسلاید 4: 4Categories of I/O DevicesCommunicationUsed to communicate with remote devicesDigital line driversModems

اسلاید 5: 5Differences in I/O DevicesData rateMay be differences of several orders of magnitude between the data transfer rates

اسلاید 6: 6

اسلاید 7: 7Differences in I/O DevicesApplicationDisk used to store files requires file management softwareDisk used to store virtual memory pages needs special hardware and software to support itTerminal used by system administrator may have a higher priority

اسلاید 8: 8Differences in I/O DevicesComplexity of controlUnit of transferData may be transferred as a stream of bytes for a terminal or in larger blocks for a diskData representationEncoding schemesError conditionsDevices respond to errors differently

اسلاید 9: 9Performing I/OProgrammed I/OProcess is busy-waiting for the operation to completeInterrupt-driven I/OI/O command is issuedProcessor continues executing instructionsI/O module sends an interrupt when done

اسلاید 10: 10Performing I/ODirect Memory Access (DMA)DMA module controls exchange of data between main memory and the I/O deviceProcessor interrupted only after entire block has been transferred

اسلاید 11: 11Relationship Among Techniques

اسلاید 12: 12Evolution of the I/O FunctionProcessor directly controls a peripheral deviceController or I/O module is addedProcessor uses programmed I/O without interruptsProcessor does not need to handle details of external devices

اسلاید 13: 13Evolution of the I/O FunctionController or I/O module with interruptsProcessor does not spend time waiting for an I/O operation to be performedDirect Memory AccessBlocks of data are moved into memory without involving the processorProcessor involved at beginning and end only

اسلاید 14: 14Evolution of the I/O FunctionI/O module is a separate processorI/O processorI/O module has its own local memoryIts a computer in its own right

اسلاید 15: 15Direct Memory AccessProcessor delegates I/O operation to the DMA moduleDMA module transfers data directly to or form memoryWhen complete DMA module sends an interrupt signal to the processor

اسلاید 16: 16DMA

اسلاید 17: 17DMA Configurations

اسلاید 18: 18DMA Configurations

اسلاید 19: 19Operating System Design IssuesEfficiencyMost I/O devices extremely slow compared to main memoryUse of multiprogramming allows for some processes to be waiting on I/O while another process executesI/O cannot keep up with processor speedSwapping is used to bring in additional Ready processes which is an I/O operation

اسلاید 20: 20Operating System Design IssuesGeneralityDesirable to handle all I/O devices in a uniform mannerHide most of the details of device I/O in lower-level routines so that processes and upper levels see devices in general terms such as read, write, open, close, lock, unlock

اسلاید 21: 21

اسلاید 22: 22I/O BufferingReasons for bufferingProcesses must wait for I/O to complete before proceedingCertain pages must remain in main memory during I/O

اسلاید 23: 23I/O BufferingBlock-orientedInformation is stored in fixed sized blocksTransfers are made a block at a timeUsed for disks and tapesStream-orientedTransfer information as a stream of bytesUsed for terminals, printers, communication ports, mouse and other pointing devices, and most other devices that are not secondary storage

اسلاید 24: 24Single BufferOperating system assigns a buffer in main memory for an I/O requestBlock-orientedInput transfers made to bufferBlock moved to user space when neededAnother block is moved into the bufferRead ahead

اسلاید 25: 25Single BufferBlock-orientedUser process can process one block of data while next block is read inSwapping can occur since input is taking place in system memory, not user memoryOperating system keeps track of assignment of system buffers to user processes

اسلاید 26: 26Single BufferStream-orientedUsed a line at timeUser input from a terminal is one line at a time with carriage return signaling the end of the lineOutput to the terminal is one line at a time

اسلاید 27: 27I/O Buffering

اسلاید 28: 28Double BufferUse two system buffers instead of oneA process can transfer data to or from one buffer while the operating system empties or fills the other buffer

اسلاید 29: 29Circular BufferMore than two buffers are usedEach individual buffer is one unit in a circular bufferUsed when I/O operation must keep up with process

اسلاید 30: 30Disk Performance ParametersTo read or write, the disk head must be positioned at the desired track and at the beginning of the desired sectorSeek timeTime it takes to position the head at the desired trackRotational delay or rotational latencyTime its takes for the beginning of the sector to reach the head

اسلاید 31: 31Timing of a Disk I/O Transfer

اسلاید 32: 32Disk Performance ParametersAccess timeSum of seek time and rotational delayThe time it takes to get in position to read or writeData transfer occurs as the sector moves under the head

اسلاید 33: 33Disk Scheduling PoliciesSeek time is the reason for differences in performanceFor a single disk there will be a number of I/O requestsIf requests are selected randomly, we will poor performance

اسلاید 34: 34Disk Scheduling PoliciesFirst-in, first-out (FIFO)Process request sequentiallyFair to all processesApproaches random scheduling in performance if there are many processes

اسلاید 35: 35Disk Scheduling PoliciesPriorityGoal is not to optimize disk use but to meet other objectivesShort batch jobs may have higher priorityProvide good interactive response time

اسلاید 36: 36Disk Scheduling PoliciesLast-in, first-outGood for transaction processing systemsThe device is given to the most recent user so there should be little arm movementPossibility of starvation since a job may never regain the head of the line

اسلاید 37: 37Disk Scheduling PoliciesShortest Service Time FirstSelect the disk I/O request that requires the least movement of the disk arm from its current positionAlways choose the minimum Seek time

اسلاید 38: 38Disk Scheduling PoliciesSCANArm moves in one direction only, satisfying all outstanding requests until it reaches the last track in that directionDirection is reversed

اسلاید 39: 39Disk Scheduling PoliciesC-SCANRestricts scanning to one direction onlyWhen the last track has been visited in one direction, the arm is returned to the opposite end of the disk and the scan begins again

اسلاید 40: 40Disk Scheduling PoliciesN-step-SCANSegments the disk request queue into subqueues of length NSubqueues are processed one at a time, using SCANNew requests added to other queue when queue is processedFSCANTwo queuesOne queue is empty for new requests

اسلاید 41: 41Disk Scheduling Algorithms

اسلاید 42: 42RAIDRedundant Array of Independent DisksSet of physical disk drives viewed by the operating system as a single logical driveData are distributed across the physical drives of an arrayRedundant disk capacity is used to store parity information

اسلاید 43: 43RAID 0 (non-redundant)

اسلاید 44: 44RAID 1 (mirrored)

اسلاید 45: 45RAID 2 (redundancy through Hamming code)

اسلاید 46: 46RAID 3 (bit-interleaved parity)

اسلاید 47: 47RAID 4 (block-level parity)

اسلاید 48: 48RAID 5 (block-level distributed parity)

اسلاید 49: 49RAID 6 (dual redundancy)

اسلاید 50: 50Disk CacheBuffer in main memory for disk sectorsContains a copy of some of the sectors on the disk

اسلاید 51: 51Least Recently UsedThe block that has been in the cache the longest with no reference to it is replacedThe cache consists of a stack of blocksMost recently referenced block is on the top of the stackWhen a block is referenced or brought into the cache, it is placed on the top of the stack

اسلاید 52: 52Least Recently UsedThe block on the bottom of the stack is removed when a new block is brought inBlocks don’t actually move around in main memoryA stack of pointers is used

اسلاید 53: 53Least Frequently UsedThe block that has experienced the fewest references is replacedA counter is associated with each blockCounter is incremented each time block accessedBlock with smallest count is selected for replacementSome blocks may be referenced many times in a short period of time and the reference count is misleading

اسلاید 54: 54

اسلاید 55: 55

اسلاید 56: 56

اسلاید 57: 57UNIX SCR4 I/OEach individual device is associated with a special fileTwo types of I/OBufferedUnbuffered

اسلاید 58: 58

اسلاید 59: 59Linux I/OElevator schedulerMaintains a single queue for disk read and write requestsKeeps list of requests sorted by block numberDrive moves in a single direction to satisy each request

اسلاید 60: 60Linux I/ODeadline schedulerUses three queuesIncoming requestsRead requests go to the tail of a FIFO queueWrite requests go to the tail of a FIFO queueEach request has an expiration time

اسلاید 61: 61Linux I/O

اسلاید 62: 62Linux I/OAnticipatory I/O schedulerDelay a short period of time after satisfying a read request to see if a new nearby request can be made

اسلاید 63: 63Windows I/OBasic I/O modulesCache managerFile system driversNetwork driversHardware device drivers

اسلاید 64: 64Windows I/O