Operating system chapter 11

صفحه 1:
I/O Management and Disk Scheduling Chapter 11 

صفحه 2:
Categories of I/O Devices ° Human readable ~ Used to communicate with the user ~ Printers ~ Video display terminals * Display * Keyboard * Mouse 

صفحه 3:
Categories of I/O Devices ° Machine readable ~ Used to communicate with electronic equipment ~ Disk and tape drives ~ Sensors ~ Controllers ~ Actuators 

صفحه 4:
Categories of I/O Devices * Communication ~ Used to communicate with remote devices ~ Digital line drivers ~ Modems 

صفحه 5:
Differences in I/O Devices ° Data rate ~ May be differences of several orders of magnitude between the data transfer rates 

صفحه 6:
oat ethernet Grapes dopey ard : ‏تست سس سس تست تا‎ TT ۳ ‏سس سس سس سس سس سس‎ ١٠٠٠:٠1٠٠ ‏سس سس سس سس سس‎ ‏رم‎ as ‏سس سس سس سس و‎ ‏د‎ ‎- Mouse Keyboard 17 we ‏را اک‎ ##« Figure 11.1 ‘Typical 1/0 Device Data Rates 

صفحه 7:
Differences in I/O Devices ° Application ~ Disk used to store files requires file management software ~ Disk used to store virtual memory pages needs special hardware and software to support it ~ Terminal used by system administrator may have a higher priority 

صفحه 8:
Differences in I/O Devices ° Complexity of control ° Unit of transfer ~ Data may be transferred as a stream of bytes for a terminal or in larger blocks for a disk ° Data representation ~ Encoding schemes ° Error conditions ~ Devices respond to errors differently 8 

صفحه 9:
Performing I/O ° Programmed I/O ~ Process is busy-waiting for the operation to complete ° Interrupt-driven 0 ~ 1/O command is issued ~ Processor continues executing instructions - 1/0 module sends an interrupt when done 

صفحه 10:
Performing I/O ۰ Direct Memory Access (DMA) - DMA module controls exchange of data between main memory and the I/O device ~ Processor interrupted only after entire block has been transferred 

صفحه 11:
Relationship Among Techniques Table 11.1. VO Techniques [No Interrupts Programmed TO 

صفحه 12:
Evolution of the I/O Function ° Processor directly controls a peripheral device ° Controller or I/O module is added ~ Processor uses programmed I/O without interrupts ~ Processor does not need to handle details of external devices 

صفحه 13:
Evolution of the I/O Function * Controller or I/O module with interrupts ~ Processor does not spend time waiting for an I/O operation to be performed ° Direct Memory Access ~ Blocks of data are moved into memory without involving the processor ~ Processor involved at beginning and end only 13 

صفحه 14:
Evolution of the I/O Function * 1/0 module is a separate processor ° I/O processor ~ I/O module has its own local memory ~ Its a computer in its own right 

صفحه 15:
Direct Memory Access ° Processor delegates I/O operation to the DMA module ° DMA module transfers data directly to or form memory ° When complete DMA module sends an interrupt signal to the processor 

صفحه 16:
16 gure 11.2 Typical DMA Block Diagram Data Lines ‘Address Lines ¢——} DMA Request « DMA Acknowledge Interrupt « 

صفحه 17:
DMA Configurations 

صفحه 18:
DMA Configurations هه Figure 11.3 Alternative DMA Configurations 

صفحه 19:
Operating System Design Issues ° Efficiency - Most I/O devices extremely slow compared to main memory ~ Use of multiprogramming allows for some processes to be waiting on I/O while another process executes ~ I/O cannot keep up with processor speed ~ Swapping is used to bring in additional Ready processes which is an I/O operation 19 

صفحه 20:
Operating System Design Issues ° Generality ~ Desirable to handle all I/O devices in a uniform manner ~ Hide most of the details of device 7/0 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 Ge) ‏لیا‎ مسر ۳-3 مس موس را تسام ‎A Model of /O Organization‏ ۱۱4 مینز 

صفحه 22:
1/O Buffering ° Reasons for buffering ~ Processes must wait for I/O to complete before proceeding - Certain pages must remain in main memory during I/O 

صفحه 23:
1/O Buffering ° Block-oriented ~ Information is stored in fixed sized blocks ~ Transfers are made a block at a time ~ Used for disks and tapes ° Stream-oriented ~ Transfer information as a stream of bytes ~ Used for terminals, printers, communication ports, mouse and other pointing devices, and most other devices that are not secondary storage 23 

صفحه 24:
Single Buffer ° Operating system assigns a buffer in main memory for an I/O request ۰ Block-oriented ~ Input transfers made to buffer ~ Block moved to user space when needed ~ Another block is moved into the buffer * Read ahead 24 

صفحه 25:
Single Buffer ° Block-oriented ~ User process can process one block of data while next block is read in ~ Swapping can occur since input is taking place in system memory, not user memory ~ Operating system keeps track of assignment of system buffers to user processes 

صفحه 26:
Single Buffer ° Stream-oriented - Used a line at time ~ User input from a terminal is one line at a time with carriage return signaling the end of the line ~ Output to the terminal is one line at a time 26 

صفحه 27:
1/O Buffering Operating System 

صفحه 28:
28 Double Buffer ° Use two system buffers instead of one ۰ A process can transfer data to or from one buffer while the operating system empties or fills the other buffer ‘Operating System User Process 

صفحه 29:
Circular Buffer * More than two buffers are used ° Each individual buffer is one unit ina circular buffer * Used when I/O operation must keep up with process (4) Chea battering 29 

صفحه 30:
Disk Performance Parameters ° To read or write, the disk head must be positioned at the desired track and at the beginning of the desired sector ° Seek time ~ Time it takes to position the head at the desired track ° Rotational delay or rotational latency ~ Time its takes for the beginning of the sector to reach the head 30 

صفحه 31:
Timing of a Disk I/O Transfer ‎Vit tr‏ لسر ‎Dee Channel‏ ۲۴ ۱ ۱۱۱ ۱ ۱۱ ‎rice sp >‏ ‎Figure 11.6 Timing of'a Disk VO Transfer 

صفحه 32:
Disk Performance Parameters ° Access time ~ Sum of seek time and rotational delay ~ The time it takes to get in position to read or write ° Data transfer occurs as the sector moves under the head 

صفحه 33:
Disk Scheduling Policies ° Seek time is the reason for differences in performance ° For a single disk there will be a number of I/O requests ° If requests are selected randomly, we will poor performance 

صفحه 34:
Disk Scheduling Policies ° First-in, first-out (FIFO) ~ Process request sequentially ~ Fair to all processes ~ Approaches random scheduling in performance if there are many processes 7 و Fro, Time 34 

صفحه 35:
Disk Scheduling Policies ° Priority ~ Goal is not to optimize disk use but to meet other objectives ~ Short batch jobs may have higher priority ~ Provide good interactive response time 

صفحه 36:
Disk Scheduling Policies ° Last-in, first-out ~ Good for transaction processing systems * The device is given to the most recent user so there should be little arm movement ~ Possibility of starvation since a job may never regain the head of the line 36 

صفحه 37:
Disk Scheduling Policies * Shortest Service Time First ~ Select the disk I/O request that requires the least movement of the disk arm from its current position ~ Always choose the minimum Seek time us 19 ‏وه‎ Time 37 

صفحه 38:
Disk Scheduling Policies ۰ SCAN ~ Arm moves in one direction only, satisfying all outstanding requests until it reaches the last track in that direction Direction is reversed each: (SCAN Time 38 

صفحه 39:
Disk Scheduling Policies ° C-SCAN ~ Restricts scanning to one direction only ~ When 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 (@) CSCAN Time 39 

صفحه 40:
Disk Scheduling Policies ° N-step-SCAN ~ Segments the disk request queue into subqueues of length N ~ Subqueues are processed one at a time, using SCAN ~ New requests added to other queue when queue is processed ° FSCAN ~ Two queues ~ One queue is empty for new requests 40 

صفحه 41:
Disk Scheduling Alanrithms ‘Table 11.2 Comparison of Disk Scheduling Algorithms ‎SSTF (scan @C-scAN‏ © مج ‎(earting at wack 100) (ranting at wack 100) (Gtarting attack 100, in the | (tarting at wack 100, inthe‏ ‎rection of increasing wack | direction of meveasing wack‏ كلسم ‎subst)‏ ‎track [Nextwack Namberof [Next wacky‏ 0 ‎aecessed tracks accessed accessed tracks accessed‏ ‎traversed sraversed‏ 150 50 150 0 30 55 160 10 160 2 5 58 186 24 14 3 39 18 4و 90 16 38 18 38 2 58 1 38 90 0 3 3 2 18 160 ‎ss‏ 16 3 132 150 150 ‎i ۳‏ 38 10 160 12 38 ‎Ist 2+ 18 20 9‏ ۳3 18 ‎Average sock JAveragesook 275 [Average seek 278 | Average seok‏ اوه ‎length length‏ قوس ‎41 ‎ ‎ 

صفحه 42:
RAID ° Redundant Array of Independent Disks ° Set of physical disk drives viewed by the operating system as a single logical drive ° Data are distributed across the physical drives of an array ° Redundant disk capacity is used to store parity information 

صفحه 43:
RAID 0 (non-redundant) 

صفحه 44:
RAID 1 (mirrored) 

صفحه 45:
۷ حم لالخلا ‎through Hamming‏ ‎code)‏ SEEEEEE اسمن عسي د ا 

صفحه 46:
RAID 3 (bit-interleaved parity) 

صفحه 47:
RAID 4 (block-level parity) as a os i 

صفحه 48:
RAID 5 (block-level distributed parity) 

صفحه 49:
RAID 6 (dual redundancy) [esr] [rio] leis] [ess] (Seen) [Sea] 

صفحه 50:
Disk Cache ° Buffer in main memory for disk sectors ° Contains a copy of some of the sectors on the disk 

صفحه 51:
Least Recently Used ۰ The block that has been in the cache the longest with no reference to it is replaced ¢ The cache consists of a stack of blocks ° Most recently referenced block is on the top of the stack e When a block is referenced or brought into the cache, it is placed on the top of the stack 

صفحه 52:
Least Recently Used ° The block on the bottom of the stack is removed when a new block is brought in ° Blocks don’t actually move around in main memory ° A stack of pointers is used 

صفحه 53:
Least Frequently Used The block that has experienced the fewest references is replaced A counter is associated with each block Counter is incremented each time block accessed Block with smallest count is selected for replacement Some blocks may be referenced many times in a short period of time and the reference count is misleading 

صفحه 54:
91555555 count = coun +1 lock brought ‘oul = 1 (a) FIFO New Section Middle Section OW Section 5 تم معا ۵ 7 Figure 11.9 Frequency-Based Replacement 54 

صفحه 55:
۳ Figure 11.10 Some Disk Cache Performance Results Using LRU 

صفحه 56:
Caste mega) Figure 11.11 Disk Cache Performance Using Frequency-Based Replacement [ROBI90] 

صفحه 57:
UNIX SCR4 I/O * Each individual [me] device is associated with a special file ‏اج‎ ‎۰ 1۷۵ ‏86و7۵‎ I/O ‏أ‎ ‎~ Buffered Character [Block ‏ع‎ ‎~ Unbuffered Figure 11.12, UNIX V/O Structure 

صفحه 58:
Figure 1.13 UNIX Rafer Cache Organization 58 

صفحه 59:
Linux 0 ° Elevator scheduler ~ Maintains a single queue for disk read and write requests ~ Keeps list of requests sorted by block number ~ Drive moves in a single direction to satisy each request 

صفحه 60:
Linux 0 ° Deadline scheduler ~ Uses three queues * Incoming requests ۰ Read requests go to the tail of a FIFO queue * Write requests go to the tail of a FIFO queue ~ Each request has an expiration time 60 

صفحه 61:
Linux 0 Sorted (elevator) queue ea FIFO ane ITT TTt 1 Write FIFO quewe Figure 11.14 The Linux Deadline /O Scheduler 61 

صفحه 62:
Linux 0 ° Anticipatory I/O scheduler ~ Delay a short period of time after satisfying a read request to see if a new nearby request can be made 

صفحه 63:
Windows I/O ° Basic I/O modules ~ Cache manager ~ File system drivers ~ Network drivers ~ Hardware device drivers 

صفحه 64:
64 Windows I/O 1/۵ Manager| Cache Manager File System Drivers ‘Network Drivers Hardware Device Drivers Figure 11.15. Windows I/O Manager 

I/O Management and Disk Scheduling Chapter 11 1 Categories of I/O Devices • Human readable – Used to communicate with the user – Printers – Video display terminals • Display • Keyboard • Mouse 2 Categories of I/O Devices • Machine readable – Used to communicate with electronic equipment – Disk and tape drives – Sensors – Controllers – Actuators 3 Categories of I/O Devices • Communication – Used to communicate with remote devices – Digital line drivers – Modems 4 Differences in I/O Devices • Data rate – May be differences of several orders of magnitude between the data transfer rates 5 6 Differences in I/O Devices • Application – Disk used to store files requires file management software – Disk used to store virtual memory pages needs special hardware and software to support it – Terminal used by system administrator may have a higher priority 7 Differences in I/O Devices • Complexity of control • Unit of transfer – Data may be transferred as a stream of bytes for a terminal or in larger blocks for a disk • Data representation – Encoding schemes • Error conditions – Devices respond to errors differently 8 Performing I/O • Programmed I/O – Process is busy-waiting for the operation to complete • Interrupt-driven I/O – I/O command is issued – Processor continues executing instructions – I/O module sends an interrupt when done 9 Performing I/O • Direct Memory Access (DMA) – DMA module controls exchange of data between main memory and the I/O device – Processor interrupted only after entire block has been transferred 10 Relationship Among Techniques 11 Evolution of the I/O Function • Processor directly controls a peripheral device • Controller or I/O module is added – Processor uses programmed I/O without interrupts – Processor does not need to handle details of external devices 12 Evolution of the I/O Function • Controller or I/O module with interrupts – Processor does not spend time waiting for an I/O operation to be performed • Direct Memory Access – Blocks of data are moved into memory without involving the processor – Processor involved at beginning and end only 13 Evolution of the I/O Function • I/O module is a separate processor • I/O processor – I/O module has its own local memory – Its a computer in its own right 14 Direct Memory Access • Processor delegates I/O operation to the DMA module • DMA module transfers data directly to or form memory • When complete DMA module sends an interrupt signal to the processor 15 DMA 16 DMA Configurations 17 DMA Configurations 18 Operating System Design Issues • Efficiency – Most I/O devices extremely slow compared to main memory – Use of multiprogramming allows for some processes to be waiting on I/O while another process executes – I/O cannot keep up with processor speed – Swapping is used to bring in additional Ready processes which is an I/O operation 19 Operating System Design Issues • Generality – Desirable to handle all I/O devices in a uniform manner – Hide 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 20 21 I/O Buffering • Reasons for buffering – Processes must wait for I/O to complete before proceeding – Certain pages must remain in main memory during I/O 22 I/O Buffering • Block-oriented – Information is stored in fixed sized blocks – Transfers are made a block at a time – Used for disks and tapes • Stream-oriented – Transfer information as a stream of bytes – Used for terminals, printers, communication ports, mouse and other pointing devices, and most other devices that are not secondary storage 23 Single Buffer • Operating system assigns a buffer in main memory for an I/O request • Block-oriented – Input transfers made to buffer – Block moved to user space when needed – Another block is moved into the buffer • Read ahead 24 Single Buffer • Block-oriented – User process can process one block of data while next block is read in – Swapping can occur since input is taking place in system memory, not user memory – Operating system keeps track of assignment of system buffers to user processes 25 Single Buffer • Stream-oriented – Used a line at time – User input from a terminal is one line at a time with carriage return signaling the end of the line – Output to the terminal is one line at a time 26 I/O Buffering 27 Double Buffer • Use two system buffers instead of one • A process can transfer data to or from one buffer while the operating system empties or fills the other buffer 28 Circular Buffer • More than two buffers are used • Each individual buffer is one unit in a circular buffer • Used when I/O operation must keep up with process 29 Disk Performance Parameters • To read or write, the disk head must be positioned at the desired track and at the beginning of the desired sector • Seek time – Time it takes to position the head at the desired track • Rotational delay or rotational latency – Time its takes for the beginning of the sector to reach the head 30 Timing of a Disk I/O Transfer 31 Disk Performance Parameters • Access time – Sum of seek time and rotational delay – The time it takes to get in position to read or write • Data transfer occurs as the sector moves under the head 32 Disk Scheduling Policies • Seek time is the reason for differences in performance • For a single disk there will be a number of I/O requests • If requests are selected randomly, we will poor performance 33 Disk Scheduling Policies • First-in, first-out (FIFO) – Process request sequentially – Fair to all processes – Approaches random scheduling in performance if there are many processes 34 Disk Scheduling Policies • Priority – Goal is not to optimize disk use but to meet other objectives – Short batch jobs may have higher priority – Provide good interactive response time 35 Disk Scheduling Policies • Last-in, first-out – Good for transaction processing systems • The device is given to the most recent user so there should be little arm movement – Possibility of starvation since a job may never regain the head of the line 36 Disk Scheduling Policies • Shortest Service Time First – Select the disk I/O request that requires the least movement of the disk arm from its current position – Always choose the minimum Seek time 37 Disk Scheduling Policies • SCAN – Arm moves in one direction only, satisfying all outstanding requests until it reaches the last track in that direction – Direction is reversed 38 Disk Scheduling Policies • C-SCAN – Restricts scanning to one direction only – When 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 39 Disk Scheduling Policies • N-step-SCAN – Segments the disk request queue into subqueues of length N – Subqueues are processed one at a time, using SCAN – New requests added to other queue when queue is processed • FSCAN – Two queues – One queue is empty for new requests 40 Disk Scheduling Algorithms 41 RAID • Redundant Array of Independent Disks • Set of physical disk drives viewed by the operating system as a single logical drive • Data are distributed across the physical drives of an array • Redundant disk capacity is used to store parity information 42 RAID 0 (non-redundant) 43 RAID 1 (mirrored) 44 RAID 2 (redundancy through Hamming code) 45 RAID 3 (bit-interleaved parity) 46 RAID 4 (block-level parity) 47 RAID 5 (block-level distributed parity) 48 RAID 6 (dual redundancy) 49 Disk Cache • Buffer in main memory for disk sectors • Contains a copy of some of the sectors on the disk 50 Least Recently Used • The block that has been in the cache the longest with no reference to it is replaced • The cache consists of a stack of blocks • Most recently referenced block is on the top of the stack • When a block is referenced or brought into the cache, it is placed on the top of the stack 51 Least Recently Used • The block on the bottom of the stack is removed when a new block is brought in • Blocks don’t actually move around in main memory • A stack of pointers is used 52 Least Frequently Used • The block that has experienced the fewest references is replaced • A counter is associated with each block • Counter is incremented each time block accessed • Block with smallest count is selected for replacement • Some blocks may be referenced many times in a short period of time and the reference count is misleading 53 54 55 56 UNIX SCR4 I/O • Each individual device is associated with a special file • Two types of I/O – Buffered – Unbuffered 57 58 Linux I/O • Elevator scheduler – Maintains a single queue for disk read and write requests – Keeps list of requests sorted by block number – Drive moves in a single direction to satisy each request 59 Linux I/O • Deadline scheduler – Uses three queues • Incoming requests • Read requests go to the tail of a FIFO queue • Write requests go to the tail of a FIFO queue – Each request has an expiration time 60 Linux I/O 61 Linux I/O • Anticipatory I/O scheduler – Delay a short period of time after satisfying a read request to see if a new nearby request can be made 62 Windows I/O • Basic I/O modules – – – – Cache manager File system drivers Network drivers Hardware device drivers 63 Windows I/O 64