Input Output Management in Operating System

Input Output Management in Operating System

1. I/O Management Output Input

2. I/O Devices I/O devices are roughly categorized into three categories: 2 Suitable for communicating with computer user Suitable for communicating with electronic equipment Suitable for communicating with remote devices

3. I/O Devices There are great differences across classes of I/O devices. Key differences are: Data Rate: There may be differences of several orders of magnitude between the data transfers. Application: The use to which a device is put has an influence on the software and policies in the OS and supporting utilities. Complexity of control: E.g. a printer requires a relatively simple control interface while a disk is much more complex. Unit of transfer: Data may be transferred as a stream of bytes or characters or in a large block. 3

4. I/O Devices There are great differences across classes of I/O devices. Key differences are: Data Representation: Different data encoding schemes are used by different devices, including differences in character code and parity conventions. Error conditions: The nature of errors, the way in which they are reported, their consequences and the available range of responses differ widely from one device to another This diversity makes it difficult to achieve a uniform and consistent approach to I/O for both OS as well as for user processes. 4

5. Organization of the I/O Function There are three approaches for performing I/O: 5

6. Organization of the I/O Function Programmed I/O The processor issues an I/O command, on behalf of a process, to an I/O module. The process then busy waits for the operation to be completed before proceeding. Interrupt driven I/O The processor issues an I/O command, on behalf of a process. If the I/O instruction is non-blocking, the processor continues to execute instructions from the process that issued the I/O command. OR If the I/O instruction is blocking , then the next instruction that processor executes is from OS , which will put current process in a blocked state and schedule another process. 6

7. Organization of the I/O Function Direct Memory Access (DMA) Controls the exchange of data between main memory and an I/O module. The processor sends a request for the transfer of a block of data to the DMA module and is interrupted only after the entire block has been transferred. 7 No Interrupts Use of Interrupts I/O-to-Memory transfer through Processor Programmed I/O Interrupt driven I/O Direct I/O-to-Memory transfer Direct Memory Access I/O Techniques

8. Organization of the I/O Function Direct Memory Access (DMA) The DMA is capable of mimicking the processor and, of taking over control of system bus just like a processor. It transfers data to and from memory over the system bus. When the processor wishes to read or write a block of data, it issues a command to a DMA module 8 Data count Data register Address register Control Logic Data lines Address lines Request to DMA Acknowledgement from DMA Interrupt Read Write DMA Block Diagram

9. Organization of the I/O Function Direct Memory Access (DMA) When the processor wishes to read or write a block of data, it issues a command to a DMA module by sending following information: Whether a read or write is requested , using the read or write control line between the processor and the DMA module. The address of the I/O device involved , communicated on the data line . The starting location in memory to read from or write to , communicated on data lines and stored by the DMA module in its address register . The number of words to be read or written , again communicated via the data lines and stored in the data count register . 9

10. Organization of the I/O Function Direct Memory Access (DMA) The processor delegates I/O operation to the DMA module and continues with other work. DMA module transfers the entire block of data, one word at a time, directly to or from memory, without going to a processor. When the transfer is complete, the DMA module sends an interrupt signal to the processor. 10

11. Disk Organization Magnetic disks provide bulk of secondary storage for modern computer systems. 11

12. Disk Organization The two surfaces of a platter are covered with a magnetic material. Information is recorded magnetically on the platters. A read -write head flies just above each surface of every platter. The heads are attached to a disk arm that moves all the heads as a unit. The surface of a platter is logically divided into circular tracks , which are subdivided into sectors . The set of tracks that are at one arm position makes up a cylinder . There may be thousands of concentric cylinders in a disk drive, and each track may contain hundreds of sectors. 12

13. Disk Organization Disk speed has two parts. The transfer rate is the rate at which data flow between the drive and the computer. The positioning time , sometimes called the random-access time , consists of the time necessary to move the disk arm to the desired cylinder, called the seek time and the time necessary for the desired sector to rotate to the disk head, called the rotational latency . The disk head flies on an extremely thin cushion of air. Although the disk platters are coated with a thin protective layer, the head will sometimes damage the magnetic surface. This accident is called a head crash . 13

14. Disk Organization A disk drive is attached to a computer by a set of wires called an I/O bus . Several kinds of buses are available ATA (Advanced Technology Attachment SATA (Serial ATA) eSATA USB (Universal Serial Bus) FC ( Fibre Channel) The data transfers on a bus are carried out by special electronic processors called controller . Host controller is at the computer end of the bus Disk controller is built into each disk drive 14

15. 15

16. Magnetic Tape Magnetic tape was used as an early secondary-storage medium. Information is accessed sequentially. 16

17. Magnetic Tape It can hold large quantities of data, its access time is slow compared with that of main memory and magnetic disk. Random access to magnetic tape is about a thousand times slower than random access to magnetic disk Tapes are used mainly for backup, for storage of infrequently used information, and as a medium for transferring information from one system to another . A tape is kept in a spool and is wound or rewound past a read-write head. Tapes can store from 20GB to 200GB . 17

18. Disk Scheduling The operating system need to use the hardware efficiently. Disk drive is expected to have fast access time and large disk bandwidth. Seek time: The time for the disk arm to move the heads to the cylinder containing the desired sector. Rotational Latency: The additional time for the disk to rotate the desired sector to the disk head. 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. We can improve both the access time and the bandwidth by managing the order in which disk I/O requests are serviced. 18

19. Disk Scheduling Whenever a process needs I/O to or from the disk, it issues a system call to the operating system. The request specifies several pieces of information: Whether this operation is input or output What the disk address for the transfer is What the memory address for the transfer is What the number of sectors to be transferred is If the desired disk drive and controller are available, the request can be serviced immediately. If the drive or controller is busy, any new requests for service will be placed in the queue of pending requests for that drive. 19

20. Disk Scheduling FCFS Disk Scheduling The simplest form of disk scheduling based in first-come, first-served (FCFS) policy. The algorithm is intrinsically fair, but it generally does not provide the fastest service. E.g., a disk queue with requests for I/0 to blocks on cylinders in the following order 98, 183, 37, 122, 14, 124, 65, 67 suppose, currently head starts at 53 20

21. Disk Scheduling FCFS Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 head starts at 53 21 0 14 37 53 65 67 98 122 124 183 199

22. Disk Scheduling FCFS Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 head starts at 53 22 0 14 37 53 65 67 98 122 124 183 199 45 85 146 85 108 110 59 2 A total head movement of 640 cylinders.

23. Disk Scheduling SSTF Disk Scheduling Shortest Seek Time First (SSTF) It selects the request with the least seek time from the current head position. Since seek time increases with the number of cylinders traversed by the head, SSTF chooses the pending request closest to the current head position. Hence, the seek time of every request is calculated in advance in the queue and scheduled according to their seek time. E.g., a disk queue with requests for I/0 to blocks on cylinders in the following order 98, 183, 37, 122, 14, 124, 65, 67 suppose, currently head starts at 53 23

24. Disk Scheduling SSTF Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 head starts at 53 24 0 14 37 53 65 67 98 122 124 183 199 12 2 30 23 84 24 2 59 A total head movement of 236 cylinders.

25. Disk Scheduling SSTF Disk Scheduling Gives a substantial improvement in performance in comparison with FCS. SSTF scheduling is essentially a form of shortest-job-first (SJF) scheduling; and like SJF scheduling, it may cause starvation of some requests. While servicing a current request, if new request arrives which is nearest to current one, new request will be processed after this. Again if new request comes which is closer to the previous request, that incoming request will be served. If this goes on continue… the initial request which are far away will be starved. Although the SSTF algorithm is a substantial improvement over the FCFS algorithm, it is not optimal. 25

26. Disk Scheduling SCAN Disk Scheduling The disk arm starts at one end of the disk moves towards the other end. It services the requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of head movement is reversed, and servicing continues. The head continuously scans back and forth across the disk. The SCAN algorithm is sometimes called the elevator algorithm, since the disk arm behaves just like an elevator in a building. First it services all the requests going up and then reversing to service requests the other way. E.g., a disk queue with requests for I/0 to blocks on cylinders in the following order 98, 183, 37, 122, 14, 124, 65, 67 suppose, currently head starts at 53 and the disk arm is moving toward 0. 26

27. Disk Scheduling SCAN Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 Head starts at 53, the disk arm is moving toward 0. 27 0 14 37 53 65 67 98 122 124 183 199 16 23 14 2 65 31 24 2 59 A total head movement of 236 cylinders.

28. Disk Scheduling SCAN Disk Scheduling If a request arrives in the queue just in front of the head, it will be serviced almost immediately; A request arriving just behind the head will have to wait until the arm moves to the end of the disk, reverses direction, and comes back. Assuming a uniform distribution of requests for cylinders, consider the density of requests when the head reaches one end and reverses direction. At this point, relatively few requests are immediately in front of the head, since these cylinders have recently been serviced. The heaviest density of requests is at the other end of the disk. These requests have also waited the longest so why not go there first? 28

29. Disk Scheduling C-SCAN Disk Scheduling Circular SCAN is a variant of SCAN scheduling designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from one end of the disk to the other, servicing requests along the way. When the head reaches the other end, however, it immediately returns to the beginning of the disk without servicing any requests on the return trip. The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps around from the final cylinder to the first one. 29

30. Disk Scheduling C-SCAN Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 head starts at 53 30 0 14 37 53 65 67 98 122 124 183 199 22 2 31 24 2 59 16 199 14 23

31. Disk Scheduling LOOK and C-LOOK Disk Scheduling Both SCAN and C-SCAN move the disk arm across the full width of the disk. In practice, neither algorithm is often implemented this way. More common, the arm goes only as far as the final request in each direction. Then, it reverses direction immediately without going all the way to the end of the disk Versions of SCAN and C-SCAN that follow this pattern are called LOOK and C-LOOK, because they look for a request before continuing to move in a given direction. 31

32. Disk Scheduling LOOK Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 Head starts at 53, the disk arm is moving toward 0. 32 0 14 37 53 65 67 98 122 124 183 199 16 2 51 31 24 2 59 23

33. Disk Scheduling C-LOOK Disk Scheduling Queue = 98, 183, 37, 122, 14, 124, 65, 67 Head starts at 53, the disk arm is moving toward 199. 33 0 14 37 53 65 67 98 122 124 183 199 1 2 2 31 24 2 59 169 23

34. Disk Scheduling How to select a disk scheduling algorithm? With any scheduling algorithm, the performance depends heavily on the number and types of requests. Requests for disk service can be greatly influenced by the file-allocation method. A program reading a contiguously allocated file will generate several requests that are close together on the disk, resulting in limited head movement. A linked or indexed file in contrast may include blocks that are widely scattered on the disk resulting in greater head movement. The location of directories and index blocks is also important. Because of these complexities, the disk-scheduling algorithm should be written as a separate module of the operating system, so that it can be replaced with a different algorithm if necessary. 34

35. Disk Scheduling Disk Access Time Disk Response Time Average of time spent by a request waiting to perform it’s I/O operation.   35 Disk Queuing Delay Seek Time Rotational Latency Transfer Time Disk Access Time Disk Response Time

36. Disk Scheduling Example Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time, the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests. 1 2 3 4 36

37. Disk Scheduling Example Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution) is _________ tracks. 8 9 10 11 37

38. Disk Scheduling Example Data requests are received by a disk drive for cylinder 5, 25, 18, 3, 39, 8, 35 in that order. A seek takes 5msec per cylinder moved. How much seek time is needed to serve these requests for a SSTF algorithm? Assume that the arm at cylinder 20 when the last of these request is made with none of the requests yet served. 125 295 575 750 38

39. Disk Scheduling Example Consider a disk pack with the following specifications- 16 surfaces, 128 tracks per surface, 256 sectors per track and 512 bytes per sector. What is the capacity of disk pack? What is the number of bits required to address the sector? If the disk is rotating at 3600 RPM, what is the data transfer rate? If the disk system has rotational speed of 3000 RPM, what is the average access time with a seek time of 11.5 msec? 39

40. 40

41. Disk Scheduling Example Consider a disk pack with the following specifications- 16 surfaces, 128 tracks per surface, 256 sectors per track and 512 bytes per sector. What is the capacity of disk pack? 256 MB What is the number of bits required to address the sector? 19 bits If the disk is rotating at 3600 RPM, what is the data transfer rate? 120 MBps If the disk system has rotational speed of 3000 RPM, what is the average access time with a seek time of 11.5 msec? 21.5 msec 41