1
STUDY MATERIAL
DEPARTMENT : SOFTWARE SYSTEMS
CLASS : II M.Sc
SUBJECT : OPERATING SYSTEMS
UNIT : IVa
Syllabus: I/O management and disk scheduling
Introduction:
I/O devices can be categorized as three different classes:
Ø Human readable
Ø Machine readable
Ø Communication
There are various differences between the various I/O devices. Some of them are:
Ø Data rate
Ø Application
Ø Complexity of controls
Ø Unit of transfer
Ø Data representation
Ø Error conditions
Organization of the I/O function
There are three ways to perform the I/O function
Ø Programmed I/O
Ø Interrupt-driven I/O
Ø DMA (Direct Memory Access)
The evolution of the I/O function: the I/O function evolved through the following steps
Ø The processor directly controls the peripheral device.
Ø A controller or I/O module is added. The processor used programmed I/O without interrupts.
Ø Now interrupts are involved. The processor need not spend waiting for an I/O operation to be performed.
Ø The I/O module is given direct control of the memory through DMA
Ø The I/O module is enhanced to become a separate processor with a specialized instruction set tailored for I/O (I/O channel)
Ø The I/O module has a local memory of its own. (I/O processor)
DMA
The DMA is capable of mimicking the processor and taking over the control from the processor. But to do the data transfer the DMA must make use of the common system bus. To do this it must force the processor to suspend its activities for a short time so as to use the bus. It does this by stealing a bus cycle.
Instruction cycle
Processor cycle
Fetch decode fetch execute store process
Instruction instruction operand instruction result interrupt
DMA breakpoints interrupt breakpoint
DMA block diagram
There are various ways in which the DMA could be configured. The DMA can have a separate I/O bus r itcan share the system bus with the processor.
Operating system design issues
Design objectives
The two main objectives of the I/O function are
Ø Efficiency
Ø Generality
Logical structure of the I/O function
The logical structure of the I/O function for a local peripheral device, a communication port and a file system are given as examples.
Local peripheral device communication port file system
I/O Buffering
If a program wants to read a piece of data from a disk file to its user area then the simple way is to execute an io operation to read the block into the user area. But there are two main problems. First the program is hung up waiting for the io operation to complete and the next problem is that the program cannot be swapped out or be moved about in memory. For this reason buffering is used. There are three types of buffers
Ø Single buffer
Ø Double buffer
Ø Circular buffer
Single buffer
Input transfers are made to the system buffer. When the transfer is complete the block is moved to the user space and another block is bought into the system buffer immediately. This is called as reading ahead or anticipated input. Similarly when a block is to be read out, the block is copied into the system buffer and the program continues. Then the block is copied from the system buffer to the secondary memory device.
Double buffer
Here two system buffers are assigned to an operation. A process now transfers data to or from one buffer while the operating system empties or fills the other. This is known as double buffering or buffer swapping.
Circular buffer
When more than two buffers are used then the collection of buffers is called as a circular buffer. This method is used because double buffer may be inadequate when there are rapid bursts in data. Refer to diagram in book.
Disk Scheduling
Disk performance parameters
Seek time: this is the time required to move the disk arm to the required track.
Rotational delay: rotational delay is delay for the arm to move to the exact point on the track from where the data is to be read.
Transfer time: this is time taken for the actual transfer of data.
T = b/rN
T—transfer time
b—number of bytes to be transferred
N—number of bytes on the track
r—rotational speed
Disk scheduling policies
The io requests for a single disk from various processes will be held in a queue. There are a number of scheduling algorithms that are used to select the next request to be serviced.
Random: here any request from the queue is selected in random manner. This is not a good algorithm, it is only used to compare the performance of other algorithms with it’s performance.
FIFO: here the queue is processed in sequential order, the first request to arrive is processed first and so on.
Priority: here the control of the scheduling is outside the disk management software. Here the requests are processes according to the priority of the processes they come from.
LIFO: here the last request is processed next.
Shortest Service Time Next: this policy selects the request that requires the least amount of disk arm movement.
SCAN: the arm is required to move in one direction only satisfying all requests on the way. When it reaches one end it moves the in other direction satisfying all requests on that side.
C-SCAN: this policy restricts scanning to one direction only. When the arm reaches one end it is returned to the opposite end and the scan begins again.
N-step SCAN and FSCAN
The N-step scan policy segments the disk request queue into sub queues of length N. these sub queues are processed one at a time. When one queue is being processed all the new requests are put in some other sub queue.
The FSCAN policy uses two sub queues. When a scan begins all the requests are in one of the queues, with the other is empty. During the scan all new requests are put in the other queue. This queue will be processed only after the first queue is empty. Refer to example in the book.
Disk Cache
A disk cache is a buffer in main memory for disk sectors. The cache contains a copy of some of the sectors on the disk. When an I/O request is made for a certain sector then a check is made to see if it is in the disk cache. If so then the request is satisfied from the cache itself. Else the sector is read into the cache from the disk.
There are two design considerations involved in disk cache:
Ø The first is to decide on how the sector in the disk cache is given to the user process that requested the sector. One way is to copy the sector from the cache to the user process area. This would involve a memory-memory transfer. The other method is to make the sector sharable and give the user process the pointer to the address of the sector in cache.
Ø The second consideration is replacement policy. When a new sector is bought into the memory an existing sector ahs to be replaced. There are several algorithms to decide which sector has to be replaced next.
ü LRU: in this method the least recently used sector is selected for replacement
ü LFU: in this method the least frequently used sector is selected for replacement. There is a counter associated with each sector in the cache and this counter is incremented every time the sector is referenced.
ü Frequency based replacement: here there are two methods.
· Two sections: here the sectors are in a queue. The queue has two sections, an new section (at the head) and an old section. When a sector is bought the first time into cache it is put in the new section. When there is cache hit (when the requested sector is in the cache) the sector is bought to head of the queue. If the sector was already in the new section then its reference count is not incremented else it is incremented. Whenever a sector has to be replaced a sector with the least reference count from the old section is replaced.
· Three sections: this is similar to the previous algorithm, but the queue has three sections, new, middle and old. Here whenever there is a cache hit the sector is bought to the head of the queue (into the head of new section). If the sector was already in the new section the reference count is not incremented, else (either in middle or old) the count is incremented. When a sector has to be replaced the sector with the least reference count is selected from the old section(not new or middle).