Outline for EECS 678 with Professor Kulkarni at KU
Outline for EECS 678 with Professor Kulkarni at KU
Popular in Course
Popular in Department
This 28 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 26 views.
Reviews for Outline for EECS 678 with Professor Kulkarni at KU
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
59 Chapter 12 Outline I Overview of the disk structure I Disk scheduling and management I Swapspace management I RAID Structure l Disk Attachment l StableStorage Implementation l Tertiary Storage Devices l Operating System Issues l Performance Issues EECS 678 Introduction to Operating Systems 7 Sp ng 2009 9 l Over 30 year old storage technology I Very complicated 0 modern drive uses over 250000 lines of micro code Disks track t lt spin La 3 quot sector 5 I I 3 v cylinder 0 gt1 t vquot platter rotation head I readwrite I arm EECS 678 Introduction to Operating Systems 7 Spring 2009 arm assembly g Disks Terms and Definitions l Disk platters 0 both surfaces coated with magnetic material for recording 0 information stored by magnetically recording it on platters Disk platters EECS 678 Introduction to Operating Systems 7 Sp ng 2009 g Disks Terms and Definitions 2 l Disk Arm 0 moves a comb of disk heads 0 only one disk head is active at a time for readingwriting Disk platters Disk heads Disk arm EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 Disks Terms and Definitions 3 l Disk heads 0 aerodynamically designed 0 fly as close to the surface as possible 0 no room for air molecules l Hard drives are filled with special inert gas I If head touches the surface 0 event called a head crash 0 scrapes off magnetic material EECS 678 Introduction to Operating Systems 7 Sp ng 2009 g Disks Terms and Definitions 4 l Each platter surface is divided into concentric tracks Disk heads Disk platters Disk arm Track EECS 678 Introduction to Operating Systems 7 Sp ng 2009 g Disks Terms and Definitions 5 l A track is further divided into sectors l Sector is the smallest unit of disk storage Disk heads Disk platters Sector Disk arm Track EECS 678 Introduction to Operating Systems 7 Sp ng 2009 g Disks Terms and Definitions 6 l A cylinder consists of all tracks with a given disk arm posMon Disk heads Disk platters Sector Disk arm Track EECS 678 Introduction to Operating Systems 7 Sp ng 2009 3 More Hard Drive Details I Track skew 0 starting position of each track is slightly skewed O minimize rotational delay when sequentially transferring bytes across tracks I Thermo calibrations o periodically performed to account for changes of disk radius due to temperature changes I 100 to 1000 bits inserted between sectors to account for minor inaccuracies l Most drives rotate 60200 times per second EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 Disk Access Time I Seek time o the time to position disk heads 8msec on average I Rotational latency 0 time to rotate the track sector under the disk head 0 assume 7200 rotations per minute 7200 RPM 7200 60 120 rotations per second 1 120 8msec per rotation 0 average rotational delay is 4msec l Transfer time o the time to transfer bytes from disk to controller 0 for 58 Mbytessec and 4 Kbyte disk blocks gt time to transfer a block is 007 msec EECS 678 Introduction to Operating Systems 7 Sp ng 2009 10 9 Disk Performance Metrics l Disk access time 0 Seek time Rotational latency Transfer time I Latency 0 Seek Time Rotational latency l Bandwidth 0 bytes transferred disk access time EECS 678 Introduction to Operating Systems 7 Sp ng 2009 11 5 Example of Disk Bandwidth I If disk blocks are randomly accessed 0 average disk access time 12 msec I assume 4 kbyte blocks 0 bandwidth is 4 kbyte 12 msec 340 kbytesec I If disk blocks of the same cylinder are randomly accessed without disk seeks 0 average disk access time 4 msec o bandwidth is 4 kbyte 4 msec 1 Mbytesec I If disk blocks are accessed sequentially 0 without seeks and rotational delays 0 bandwidth is 58 Mbytessec l Key to good disk performance is to minimize seek time and rotational delay EECS 678 Introduction to Operating Systems 7 Sp ng 2009 12 9 Disk Structure l Disk drives are addressed as large onedimensional arrays of logical blocks l Logical block is the smallest unit of transfer I The onedimensional array of logical blocks is mapped into the sectors of the disk sequentially o sector 0 is the first sector of the first track on the outermost cylinder 0 mapping proceeds in order through that track 0 then the rest of the tracks in that cylinder and 0 then through the rest of the cylinders from outermost to innermost EECS 678 Introduction to Operating Systems 7 Sp ng 2009 13 3 Disk Controller l Host and disk controllers facilitate data transfer from disk to computer on an IO bus I Few popular disk controller standards 0 IDE Integrated Device Electronics 0 Parallel and Serial ATA AT Attachment Interface 0 SCSI Small Computer Systems Interface l Differences 0 performance gt IDE lt PATA lt SATA lt SCSI o parallelism gt IDE PATA are parallel interfaces gt SATA is serial gt SCSI can be parallel or serial EECS 678 Introduction to Operating Systems 7 Sp ng 2009 14 it Disk Scheduling l Flashback 0 seek time is the time for the disk to move the readwrite head to the cylinder containing the desired sector 0 rotational latency is the additional time waiting for the disk to rotate the desired sector to the disk head 0 seek time and rotational latency dominate disk access time 0 seek time 2 seek distance I Algorithms to schedule the servicing of disk lO requests I only attempt to minimize seek time 0 schedule a request from a queue of pending disk lO requests 0 consider example disk queue with requests to blocks on cylinders 98 183 37 122 14 124 65 67 0 current location of head pointer cylinder 53 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 15 9 First Come First Serve FCFS l Requests are served in order of arrival 0 fair among requesters 0 poor for accesses to random disk blocks 0 for example total head movement of 640 cylinders queue 98 183 37 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 183199 I l l i I ii I EECS 678 Introduction to Operating Systems 7 Spnng 2009 16 3 Shortest Seek Time First SSTF I Picks request that is closet to the current disk arm position 0 good at reducing seeks 0 may result in starvation e not optimal unlike SJF 0 example requires total head movement of 236 cylinders queue 98 183 37 122 14 124 65 67 head starts at 53 O 14 37 536567 98 122124 183199 EECS 678 Introduction to Operating Systems 7 Spnng 2009 17 3 SCAN I Start disk arm at one end of the disk and move toward the other end 0 servicing closet request in the direction of traversal 0 proceed backwards along same path like elevator o no starvation O a new request can wait for almost two full scans of the disk 0 example requires total head movement of 208 cylinders EECS 678 Introduction to Operating Systems 7 Sp ng 2009 18 SCAN 2 queue 2 98 183 37 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 183199 I I I I II I II I I I I EECS 678 Introduction to Operating Systems 7 Spiing 2009 9 Circular SCAN I Disk arm always serves requests by scanning in one direction 0 once the arm nishes scanning for one direction 0 returns to the 0th track for the next round of scanning 0 provides a more uniform wait time than SCAN queue 98 188 37 122 14 124 65 67 head starts at 53 O 14 37 536567 98 122124 183199 EECS 678 Introduction to Operating Systems 7 Spring 2009 20 t LOOK Scheduling I Modified version of SCAN 0 arm only goes as far as the last request in each direction 0 then reverses direction immediately 0 without first going all the way to the end of the disk queue 98 183 87 122 14 124 65 67 head starts at 53 O 14 87 536567 98 122124 183199 EECS 678 httroduotion to Operating Systems 7 SpIing 2009 21 9 Disk Formatting l Lowlevel or physical formatting o at factory as part of manufacturing process 0 divide disk into sectors with special data structure for each sector 0 data structure contains header data area and trailer 0 header sector number trailer error correcting code E00 0 may also mark bad blocks so that they are not used for data allocation l Logical formatting 0 results in the creation of a file system 0 copy data structures for freespace maps allocated space maps FAT Windows or inode Unix and empty directory EECS 678 Introduction to Operating Systems 7 Sp ng 2009 22 3 Redundant Array of Independent Disks RAID I Used to improve disk lO performance and reliability 0 using additional or redundant disks l Reliability I maintain extra information to allow recovery from disk failures l Performance 0 store information on multiple smaller disks 0 data transfer from disks in parallel l Bitlevel striping 0 split bits of each byte across multiple disks 0 with N disks bit i and Ni are stored on diski l Blocklevel striping 0 blocks are striped across multiple disks EECS 678 Introduction to Operating Systems 7 Sp ng 2009 23 9 RAID Levels l Reliabilityperformance schemes with different cost performance tradeoffs l RAID level 0 o employ bitlevel or blocklevel striping for performance 0 no redundancy for reliability l RAID level 1 disk mirroring o duplicate every disk in RAID array 0 simple 0 expensive 0 can provide better performance as well as reliability EECS 678 Introduction to Operating Systems 7 Sp ng 2009 24 5 RAID Levels 2 l RAID level 2 memorystyle ECC organization 0 redundant disks hold parity information 0 single bit error detection requires 1bit parity single bit error correction needs two or more parity bits 0 uses bitstriping for improved performance 0 less expensive than RAID level 1 l RAID level 3 bitinterleaved parity organization 0 uses single parity bit disk for error correction 0 we can easily figure out which sector on disk is damaged 0 use single parity bit to figure each bit on the damaged disk 0 as good as level 2 but less expensive 0 less storage overhead than level 1 O bitinterleaved so every disk has to participate in each lO request EECS 678 Introduction to Operating Systems 7 Sp ng 2009 25 5 RAID levels 3 l RAID level 4 blockinterleaved parity organization 0 similar to RAID level 3 with blocklevel striping scheme 0 supports more simultaneous IO requests than level 3 0 however data transfer rate for each access is slower O writes smaller than a block needs 2 block reads and 2 writes why 0 how about write of a complete block I RAID level 5 blockinterleaved distributed parity 0 data and parity spread among all N1 disks 0 avoids overuse of the parity disk 0 most commonly adopted RAID scheme l RAID level 6 PQ redundancy scheme 0 uses extra information to guard against multiple disk failures EECS 678 Introduction to Operating Systems 7 Sp ng 2009 26 RAID Levels 4 B a RAID 0 non redundant stripingi 8 b RAID 1 mirrored disks BB E 6 RAID 2 memory style errorcorrecting codes 88 d RAID 3 bitinterleaved parity 88 e RAID 4 Mockinterleaved parity quot quot E I RAID 5 blockInterleaved dISII IbUIed arityi quot 39 quot quot quot 9 RAID 6 P Q redundancy EECS 678 Introduction to Operating Systems 7 Spring 2009 27 if Tertiary Storage Devices l Low cost is the defining characteristic of tertiary storage I Generally tertiary storage is built using removable media I Common examples of removable media are floppy disks and CDROMs other types are available EECS 678 Introduction to Operating Systems 7 Sp ng 2009 28
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'