logging in or signing up Input/output System cj.ravikumar Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 2758 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: October 15, 2008 This Presentation is Public Favorites: 1 Presentation Description Input-Output (I/O) is perhaps the hardest practical task of the OS writer I/O devices are very different (mechanically, electronically and in purpose and function) Comments Posting comment... By: jordan007 (21 month(s) ago) ey i like it so much Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Input-Output Systems : Input-Output Systems Input-Output (I/O) is perhaps the hardest practical task of the OS writer I/O devices are very different (mechanically, electronically and in purpose and function) I/O devices have evolved in many different directions and are still evolving rapidly Objectives of I/O Design : Objectives of I/O Design Efficiency and Speed I/O devices are very much slower than processor/memory and can be a bottleneck Very wide range of speeds Generality and Device Independence We wish to minimise the differences between devices to allow a single program to output to a printer, a disk or a tape drive, for example. Minimise the device-dependent driver code Structure of I/O System : Structure of I/O System Application Program Libraries/DLLs O/S Input/Output Control System Shared I/O Routines - eg Buffering Device Driver Device Controller (Hardware/Firmware) Device (Hardware) User Level Operating System Level Device Level Devices : Devices Block Devices Transfer information in ‘lumps’ or blocks eg disks and tapes May allow random-access Character Devices Transfer information one character at a time Inherently serial eg terminal lines, printers Some physical devices can be both Buffering : Buffering Most O/S use ‘buffering’ to improve throughput with I/O devices Data is exchanged between the device and an O/S buffer, and between the buffer and the application Allows overlap between processing and I/O Double buffering allows further gains One buffer fills while another is emptied UNIX I/O System features : UNIX I/O System features UNIX devices appear (by convention) in the ‘/dev’ directory I/O devices appear to be files and can be opened, closed, read, written, etc. Since files in UNIX are streams of bytes, this works, although some operations make little sense on certain devices Device specific features implemented via I/O control (IOCTL) system calls UNIX I/O Implementation : UNIX I/O Implementation UNIX I/O devices are ‘special’ files Two types - ‘b’ (block) and ‘c’ (character) ‘Major’ and ‘minor’ device numbers correspond to device driver and device number (or device type) respectively Five system calls handle most I/O open, close, read, write, lseek Pseudo/Virtual Devices : Pseudo/Virtual Devices UNIX uses various sorts of pseudo/virtual devices Some correspond to resources such as memory (eg /dev/mem, /dev/kmem) Others are convenience features (/dev/null) Pseudo-teletypes (ptys) are network-connected terminals Some devices have multiple virtual devices Device Drivers in DOS : Device Drivers in DOS DOS provided minimal support for devices, which relies on the ‘BIOS’ (Basic I/O System) held in read-only memory Standard devices include con: (keyboard, screen) com1:, com2: (serial ports) lpt1:, lpt2: (parallel ports) A:, B: (floppy disks) C:, D:, E: etc (hard disks or partitions) Windows Device Drivers : Windows Device Drivers Windows device drivers are implemented as DLL files. Advantages include shareable code optional drivers can be written by third parties and installed without modifying Windows Windows 95 onwards supports Plug-and-Play (PnP): an extended device driver which allows the BIOS to initialise/configure a device and for settings to be automatically recognised File Systems : File Systems Storage facilities on magnetic disks etc are normally provided by a file system Many different approaches have been taken: some O/S (eg VMS) support multiple file-types (eg indexed sequential) and are knowledgable about the contents DOS and UNIX assume files are sequences of bytes with no structure Filing System : Filing System Most modern O/S support a hierarchical ‘tree-structured’ filing system Directories can contain sub-directories and/or files. Top-most directory is ‘root’ Path names identify a file in the hierarchy eg /var/adm/syslog/dated/19-Feb-96/mail.log Files also accessable relative to current working directory using . and .. Directories : Directories Directories contain information such as the file name (up to 255 characters in UNIX) the owner (and perhaps group owner) of it file access permissions size creation time, modification time, access time pointer to where the information is held on disk parent directory in hierarchical systems Information known as a ‘link’ in UNIX Volumes : Volumes A ‘volume’ is a physical disk (or partition) In DOS, volumes are ‘drives’ C:, D:, E: etc In UNIX, volumes are known as ‘file systems’ Partitions are made at the device-driver level A volume is prepared by initialising a volume data structure to permit creation of files and directories on it In DOS, this is done with ‘format’ command In UNIX, this is done with ‘mkfs’ command Allocation of File Space : Allocation of File Space File space may be added contiguously. This causes fragmentation and problems in extending files - they can only be extended if free space is available after the end of the file. Rarely used in modern systems. dynamically in ‘allocation units’. Extra file space is available on demand and is handled by the operating system Allocation of Space in DOS : Allocation of Space in DOS DOS allocates file space in ‘clusters’. NB A maximum of 65,536 clusters/volume Cluster size from 512 bytes to 32K Used disk clusters are registered in the FAT - file allocation table FAT is a chain of pointers (null if free) Directories point to the appropriate place in the FAT table to indicate the start of a file FAT structure : FAT structure Disk type ID always FFFF 0003 0004 0006 0008 0007 FFFF 000A 0000 FFFF 0000 0000 0000 0000 0000 0000 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 end of file 1 free end of file 2 free free free free free free dir pointer to file 1 dir pointer to file 2 Volume structure for DOS : Volume structure for DOS Boot sector (Bootstrap loader) FAT table Duplicate FATs Root directory File space Fdisk partition table Windows NT File System NTFS : Windows NT File System NTFS NTFS provides a number of new features advanced security long (unicode) file names (including spaces) improved fault-tolerance through recoverable ‘journalled’ file system ‘hot-fixing’ - bad sectors are transparently remapped disk striping and/or RAID support huge files (up to 264 bytes - 18 x 1012 Mbytes) POSIX compatible UNIX File Systems : UNIX File Systems Directory information is held in ‘inodes’ File blocks are pointed to by ‘inode pointers’ Inode pointers point to 10 blocks directly plus 128 indirect 128*128 double indirect 128*128*128 triple indirect Directory, Inodes and File : Directory, Inodes and File Directory Directory Details about file Pointers File block 1 File block 2 File block 3 UNIX Inode Pointer System : UNIX Inode Pointer System Direct 0 Direct 1 Direct 2 Direct 8 Direct 9 Single Indirect Double Indirect Triple Indirect Data block INODE pointer ptr to 128 ptr to 128 ptr to 128 ptr to 128 UNIX volume structure : UNIX volume structure Separate file systems are incorporated into a single hierarchical directory with the ‘mount’ command A file system can be ‘mounted’ on any directory mount /dev/fd /usr/mnt ‘umount’ unmounts /usr/mnt / /usr original root of floppy disk file system Improving a filing system : Improving a filing system Performance Blocking and Interleaving Cacheing and RAM disks Device independence ‘Logical file systems’ which can span disks Fault tolerance Recoverable file systems Disk striping and RAID Blocking and Interleaving : Blocking and Interleaving Blocking Disk read time is determined by seek time+latency+read/transfer time Typical hardware sector size = 512 bytes Larger block sizes (eg 4K) may improve throughput Interleaving Alters the physical position of data on sectors on the disk to improve access to consecutive data Interleaving : Interleaving 1 2 3 4 5 6 7 8 1 5 2 6 3 7 4 8 No interleaving, sectors are adjacent - no time to transfer sector 1 and set up controller to read sector 2, so takes 9 revolutions to read 8 sectors. Interleaved 1:2 - gives 1 sector ‘gap’ to transfer sector 1 and set up controller to read sector 2. Takes 2 revolutions to read 8 sectors - more than 4 times faster. Caching : Caching Disk caching uses a cache (set of buffers) to hold recently-accessed disk blocks Repeat accesses can be fetched from the cache and not the ‘real’ disk May be ‘write back’ (disk writes delayed) or ‘write through’ (disk updated on writes) Write-back risks data loss on power failure Logical File Systems : Logical File Systems Logical files systems, such as Digitals Advanced File System, allow a single file system to span more than one physical disk Add or remove disks at will Extend file system sizes as they fill up by adding new drives Load balancing - moves files around as disks are added so that all drives get equal use Allow several file systems to share 1 drive Fault Tolerance : Fault Tolerance Fault Tolerance - literally the ability to tolerate (and recover) from hardware or software errors Software techniques include transaction based file systems hot fixing - data on bad sectors is automatically moved to a new location and old one marked Hardware techiques include disk striping, RAID RAID : RAID Redundant Array of Inexpensive Disks expensive RAIDs are R A of Independent Ds! RAID improves performance and/or reliability (fault tolerance RAID systems combine a number of disks into a single file system RAID-0 : RAID-0 RAID-0 is also known as disk striping R-0 can have any number of disks Blocks are assigned to disks in rotation - first block to first disk, 2nd to 2nd, etc Improves performance: a read of a number of consecutive blocks causes several disks to be used - speeds transfers Doesn’t help reliability (makes it worse!) RAID-0 : RAID-0 Block 1 5 9 13 17 21 25 Disk 1 2 6 10 14 18 22 26 Disk 2 3 7 11 15 19 23 27 Disk 3 4 8 12 16 20 24 28 Disk 4 RAID-1 Mirroring : RAID-1 Mirroring Each drive is mirrored so each block is recorded on at least two disks Fault tolerant: One disk can fail Improved performance: choice of drives to read from, so throughput similar to R-0 eg block(b)1/disk(d)1, b2/d3, b3/d2, b4/d4 Main disadvantage is that 1/2 the capacity of the storage array is used in mirroring RAID-1 : RAID-1 Block 1* 3 5* 7 9* 11 13* Disk 1 1 3* 5 7* 9 11* 13 Disk 2 (disk 1 mirror) 2* 4 6* 8 10* 12 14* Disk 3 2 4* 6 8* 10 12* 14 Disk 4 (disk 3 mirror) * = disk from which that block is read ‘round-robin’; all writes go to both mirrored drives RAID-3 Striping with parity : RAID-3 Striping with parity Note: RAID-2 exists but is never used! RAID-3 is similar to RAID-0, but reserves one disk for parity Parity is calculated as the exclusive-OR of the data blocks XOR parity is reversible - given the failure of any disk one can calculate the information that is missing RAID-3 : RAID-3 Block 1 4 7 10 13 16 19 Disk 1 2 5 8 11 14 17 20 Disk 2 3 6 9 12 15 18 21 Disk 3 1 xor 2 xor 3 4 xor 5 xor 6 7 xor 8 xor 9 10 xor 11 xor 12 13 xor 14 xor 15 16 xor 17 xor 18 19 xor 20 xor 21 Disk 4 (Parity disk) RAID-3 : RAID-3 RAID-3 advantages/disadvantages It normally delivers the same read performance as RAID-0 (unless we need to use parity disk) Any one disk can fail without affecting data which can be calculated from the parity (although reads are much slower) The parity disk is overworked, being used on every write operation Storage loss is modest - commercial systems use a single parity disk for up to 7 data disks RAID-5 : RAID-5 NB Raid-3 and Raid-4 are almost identical RAID-5 is similar to RAID-3, but with the parity block rotated around the disks All disks get equal use whether reading or writing Practical RAID-5 systems may allow ‘hot swapping’ or ‘stand-by spare’ arrangements Read about RAID on the web for other issues RAID-5 : RAID-5 Block 1 4 xor 5 xor 6 7 10 13 16 xor 17 xor 18 19 Disk 1 2 4 7 xor 8 xor 9 11 14 16 19 xor 20 xor 21 Disk 2 3 5 8 10 xor 11 xor 12 15 17 20 Disk 3 1 xor 2 xor 3 6 9 12 13 xor 14 xor 15 18 21 Disk 4 You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Input/output System cj.ravikumar Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 2758 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: October 15, 2008 This Presentation is Public Favorites: 1 Presentation Description Input-Output (I/O) is perhaps the hardest practical task of the OS writer I/O devices are very different (mechanically, electronically and in purpose and function) Comments Posting comment... By: jordan007 (21 month(s) ago) ey i like it so much Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Input-Output Systems : Input-Output Systems Input-Output (I/O) is perhaps the hardest practical task of the OS writer I/O devices are very different (mechanically, electronically and in purpose and function) I/O devices have evolved in many different directions and are still evolving rapidly Objectives of I/O Design : Objectives of I/O Design Efficiency and Speed I/O devices are very much slower than processor/memory and can be a bottleneck Very wide range of speeds Generality and Device Independence We wish to minimise the differences between devices to allow a single program to output to a printer, a disk or a tape drive, for example. Minimise the device-dependent driver code Structure of I/O System : Structure of I/O System Application Program Libraries/DLLs O/S Input/Output Control System Shared I/O Routines - eg Buffering Device Driver Device Controller (Hardware/Firmware) Device (Hardware) User Level Operating System Level Device Level Devices : Devices Block Devices Transfer information in ‘lumps’ or blocks eg disks and tapes May allow random-access Character Devices Transfer information one character at a time Inherently serial eg terminal lines, printers Some physical devices can be both Buffering : Buffering Most O/S use ‘buffering’ to improve throughput with I/O devices Data is exchanged between the device and an O/S buffer, and between the buffer and the application Allows overlap between processing and I/O Double buffering allows further gains One buffer fills while another is emptied UNIX I/O System features : UNIX I/O System features UNIX devices appear (by convention) in the ‘/dev’ directory I/O devices appear to be files and can be opened, closed, read, written, etc. Since files in UNIX are streams of bytes, this works, although some operations make little sense on certain devices Device specific features implemented via I/O control (IOCTL) system calls UNIX I/O Implementation : UNIX I/O Implementation UNIX I/O devices are ‘special’ files Two types - ‘b’ (block) and ‘c’ (character) ‘Major’ and ‘minor’ device numbers correspond to device driver and device number (or device type) respectively Five system calls handle most I/O open, close, read, write, lseek Pseudo/Virtual Devices : Pseudo/Virtual Devices UNIX uses various sorts of pseudo/virtual devices Some correspond to resources such as memory (eg /dev/mem, /dev/kmem) Others are convenience features (/dev/null) Pseudo-teletypes (ptys) are network-connected terminals Some devices have multiple virtual devices Device Drivers in DOS : Device Drivers in DOS DOS provided minimal support for devices, which relies on the ‘BIOS’ (Basic I/O System) held in read-only memory Standard devices include con: (keyboard, screen) com1:, com2: (serial ports) lpt1:, lpt2: (parallel ports) A:, B: (floppy disks) C:, D:, E: etc (hard disks or partitions) Windows Device Drivers : Windows Device Drivers Windows device drivers are implemented as DLL files. Advantages include shareable code optional drivers can be written by third parties and installed without modifying Windows Windows 95 onwards supports Plug-and-Play (PnP): an extended device driver which allows the BIOS to initialise/configure a device and for settings to be automatically recognised File Systems : File Systems Storage facilities on magnetic disks etc are normally provided by a file system Many different approaches have been taken: some O/S (eg VMS) support multiple file-types (eg indexed sequential) and are knowledgable about the contents DOS and UNIX assume files are sequences of bytes with no structure Filing System : Filing System Most modern O/S support a hierarchical ‘tree-structured’ filing system Directories can contain sub-directories and/or files. Top-most directory is ‘root’ Path names identify a file in the hierarchy eg /var/adm/syslog/dated/19-Feb-96/mail.log Files also accessable relative to current working directory using . and .. Directories : Directories Directories contain information such as the file name (up to 255 characters in UNIX) the owner (and perhaps group owner) of it file access permissions size creation time, modification time, access time pointer to where the information is held on disk parent directory in hierarchical systems Information known as a ‘link’ in UNIX Volumes : Volumes A ‘volume’ is a physical disk (or partition) In DOS, volumes are ‘drives’ C:, D:, E: etc In UNIX, volumes are known as ‘file systems’ Partitions are made at the device-driver level A volume is prepared by initialising a volume data structure to permit creation of files and directories on it In DOS, this is done with ‘format’ command In UNIX, this is done with ‘mkfs’ command Allocation of File Space : Allocation of File Space File space may be added contiguously. This causes fragmentation and problems in extending files - they can only be extended if free space is available after the end of the file. Rarely used in modern systems. dynamically in ‘allocation units’. Extra file space is available on demand and is handled by the operating system Allocation of Space in DOS : Allocation of Space in DOS DOS allocates file space in ‘clusters’. NB A maximum of 65,536 clusters/volume Cluster size from 512 bytes to 32K Used disk clusters are registered in the FAT - file allocation table FAT is a chain of pointers (null if free) Directories point to the appropriate place in the FAT table to indicate the start of a file FAT structure : FAT structure Disk type ID always FFFF 0003 0004 0006 0008 0007 FFFF 000A 0000 FFFF 0000 0000 0000 0000 0000 0000 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 end of file 1 free end of file 2 free free free free free free dir pointer to file 1 dir pointer to file 2 Volume structure for DOS : Volume structure for DOS Boot sector (Bootstrap loader) FAT table Duplicate FATs Root directory File space Fdisk partition table Windows NT File System NTFS : Windows NT File System NTFS NTFS provides a number of new features advanced security long (unicode) file names (including spaces) improved fault-tolerance through recoverable ‘journalled’ file system ‘hot-fixing’ - bad sectors are transparently remapped disk striping and/or RAID support huge files (up to 264 bytes - 18 x 1012 Mbytes) POSIX compatible UNIX File Systems : UNIX File Systems Directory information is held in ‘inodes’ File blocks are pointed to by ‘inode pointers’ Inode pointers point to 10 blocks directly plus 128 indirect 128*128 double indirect 128*128*128 triple indirect Directory, Inodes and File : Directory, Inodes and File Directory Directory Details about file Pointers File block 1 File block 2 File block 3 UNIX Inode Pointer System : UNIX Inode Pointer System Direct 0 Direct 1 Direct 2 Direct 8 Direct 9 Single Indirect Double Indirect Triple Indirect Data block INODE pointer ptr to 128 ptr to 128 ptr to 128 ptr to 128 UNIX volume structure : UNIX volume structure Separate file systems are incorporated into a single hierarchical directory with the ‘mount’ command A file system can be ‘mounted’ on any directory mount /dev/fd /usr/mnt ‘umount’ unmounts /usr/mnt / /usr original root of floppy disk file system Improving a filing system : Improving a filing system Performance Blocking and Interleaving Cacheing and RAM disks Device independence ‘Logical file systems’ which can span disks Fault tolerance Recoverable file systems Disk striping and RAID Blocking and Interleaving : Blocking and Interleaving Blocking Disk read time is determined by seek time+latency+read/transfer time Typical hardware sector size = 512 bytes Larger block sizes (eg 4K) may improve throughput Interleaving Alters the physical position of data on sectors on the disk to improve access to consecutive data Interleaving : Interleaving 1 2 3 4 5 6 7 8 1 5 2 6 3 7 4 8 No interleaving, sectors are adjacent - no time to transfer sector 1 and set up controller to read sector 2, so takes 9 revolutions to read 8 sectors. Interleaved 1:2 - gives 1 sector ‘gap’ to transfer sector 1 and set up controller to read sector 2. Takes 2 revolutions to read 8 sectors - more than 4 times faster. Caching : Caching Disk caching uses a cache (set of buffers) to hold recently-accessed disk blocks Repeat accesses can be fetched from the cache and not the ‘real’ disk May be ‘write back’ (disk writes delayed) or ‘write through’ (disk updated on writes) Write-back risks data loss on power failure Logical File Systems : Logical File Systems Logical files systems, such as Digitals Advanced File System, allow a single file system to span more than one physical disk Add or remove disks at will Extend file system sizes as they fill up by adding new drives Load balancing - moves files around as disks are added so that all drives get equal use Allow several file systems to share 1 drive Fault Tolerance : Fault Tolerance Fault Tolerance - literally the ability to tolerate (and recover) from hardware or software errors Software techniques include transaction based file systems hot fixing - data on bad sectors is automatically moved to a new location and old one marked Hardware techiques include disk striping, RAID RAID : RAID Redundant Array of Inexpensive Disks expensive RAIDs are R A of Independent Ds! RAID improves performance and/or reliability (fault tolerance RAID systems combine a number of disks into a single file system RAID-0 : RAID-0 RAID-0 is also known as disk striping R-0 can have any number of disks Blocks are assigned to disks in rotation - first block to first disk, 2nd to 2nd, etc Improves performance: a read of a number of consecutive blocks causes several disks to be used - speeds transfers Doesn’t help reliability (makes it worse!) RAID-0 : RAID-0 Block 1 5 9 13 17 21 25 Disk 1 2 6 10 14 18 22 26 Disk 2 3 7 11 15 19 23 27 Disk 3 4 8 12 16 20 24 28 Disk 4 RAID-1 Mirroring : RAID-1 Mirroring Each drive is mirrored so each block is recorded on at least two disks Fault tolerant: One disk can fail Improved performance: choice of drives to read from, so throughput similar to R-0 eg block(b)1/disk(d)1, b2/d3, b3/d2, b4/d4 Main disadvantage is that 1/2 the capacity of the storage array is used in mirroring RAID-1 : RAID-1 Block 1* 3 5* 7 9* 11 13* Disk 1 1 3* 5 7* 9 11* 13 Disk 2 (disk 1 mirror) 2* 4 6* 8 10* 12 14* Disk 3 2 4* 6 8* 10 12* 14 Disk 4 (disk 3 mirror) * = disk from which that block is read ‘round-robin’; all writes go to both mirrored drives RAID-3 Striping with parity : RAID-3 Striping with parity Note: RAID-2 exists but is never used! RAID-3 is similar to RAID-0, but reserves one disk for parity Parity is calculated as the exclusive-OR of the data blocks XOR parity is reversible - given the failure of any disk one can calculate the information that is missing RAID-3 : RAID-3 Block 1 4 7 10 13 16 19 Disk 1 2 5 8 11 14 17 20 Disk 2 3 6 9 12 15 18 21 Disk 3 1 xor 2 xor 3 4 xor 5 xor 6 7 xor 8 xor 9 10 xor 11 xor 12 13 xor 14 xor 15 16 xor 17 xor 18 19 xor 20 xor 21 Disk 4 (Parity disk) RAID-3 : RAID-3 RAID-3 advantages/disadvantages It normally delivers the same read performance as RAID-0 (unless we need to use parity disk) Any one disk can fail without affecting data which can be calculated from the parity (although reads are much slower) The parity disk is overworked, being used on every write operation Storage loss is modest - commercial systems use a single parity disk for up to 7 data disks RAID-5 : RAID-5 NB Raid-3 and Raid-4 are almost identical RAID-5 is similar to RAID-3, but with the parity block rotated around the disks All disks get equal use whether reading or writing Practical RAID-5 systems may allow ‘hot swapping’ or ‘stand-by spare’ arrangements Read about RAID on the web for other issues RAID-5 : RAID-5 Block 1 4 xor 5 xor 6 7 10 13 16 xor 17 xor 18 19 Disk 1 2 4 7 xor 8 xor 9 11 14 16 19 xor 20 xor 21 Disk 2 3 5 8 10 xor 11 xor 12 15 17 20 Disk 3 1 xor 2 xor 3 6 9 12 13 xor 14 xor 15 18 21 Disk 4