Operating Systems Design & Construction
Operating Systems Design & Construction CMPSC 473
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 0 page Class Notes was uploaded by Isabel Eichmann on Sunday November 1, 2015. The Class Notes belongs to CMPSC 473 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/233061/cmpsc-473-pennsylvania-state-university in ComputerScienence at Pennsylvania State University.
Reviews for Operating Systems Design & Construction
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/01/15
Operating Systems CMPSC 473 Storage April 3 2008 Lecture 20 W M Outline Disk structure physical and logical Disk addressing Disk scheduling Management Need for Storage Memory is volatile persistence is required insuf cient large capacity is required not portable how can we take information with us Long lasting backup data is needed scientific applications industry and finance Example of Mass Storage Application 331335 3i MBevenv IV 50000 dnru hannc s Ej quot 200 GB buncrmg I quot39J 1TBs mwmm SOOGbs evem inhenng 1 CPUevenr O SGBs davusmmgn 39 39 W 5PBvear CERN Particle Collider Past amp Present in Storage 1956 IBM 305 RAMAC 5 MB capacity 50 disks each 24 in diameter 1 2008 Seagate Savvio 15K 734 GB capacity 25 diameter 1 can readwrite quot complete works of Shakespeare 15 times persecond Storage Hierarchy cheap and slow tertiary storage secondary storage main memory L2 cache L1 cache A 4 E9 registers expensive and fast Secondary Storage Generally magnetic disks provide the bulk of secondary storage in systems future alternative solid state drives 39 eg MacBook Air MEMS and NEMSnanotech holographic storage 39 data read from intersecting laser beams track I rotation arm assembly Aluminum sometimes glass platters Deep Inside a Hard Disk Biticell composed of about 507100 magnetic grains 0 has uniform polarity 1 has a boundary between magnetizations magnetized in direction of disk head longitudinal or perpendicular more complex but more density in development HAMR mas heatiassisted Ecmd with lasers m quotm potentially 50 Tbin2 am Disk Operation Platters start moving from rest Jpz39 up time lots of mass to start moving 39 Heads nd the right track Jae time arm powered by actuator motor accelerates and coasts slows down and settles on correct track servo guided Disk rotates until correct sector found mfm z om dream contingent on platter diameter and RPM Savvio 15K rotates 300 times second Addressing Disks 39 Old days CHS cylinder head sector supply physical characteristics of the disk to the operating system it specifies exactly Where on the physical disk to read and write data 39 Nowadays cylinders not uniform can store more data on outer tracks than inner tracks zoned bit recording Why function of constant angular velocity CAV vs constant linear velocity CLV found in CD ROM Logical Block Addressing LEA 39 OS sees drive as an array of blocks rst block LBA I 0 next block LBA I 1 etc disk rmware takes care of managing the physical location of data Block smallest unit of data accessible through the OS can be the size of a sector 512 bytes up to the size of a page often 4 KB de ned by kernel Disk Scheduling 39 Why does the 08 need to schedule Improves access time seek time amp rotational latency even with LBA assumption is that blocks are written in essentially contiguous order maximizes bandwidth transferred bytes service transfer time Disk Scheduling Algorithms Consider the following request queue min cylinder I O max cylinder I 199 requests at the following cylinders 98 183 37 122 14 124 65 67 drive head is at cylinder 53 First come First served F CFS Service the requests in order of arrival 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 Shortest Seek Time First SSTF Mm seek time from head position like SJF 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 SCAN Elevator Algorithm Arm moves from one end of disk to the other then reverses like an elevator Head movement of 208 cylinders queue 98 183 87 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 183199 C SCAN Algorithm More uniform wait time than SCAN Head services requests in one direction then returns to beginning of disk like circular list queue 98 18337 122 14 124 65 67 head starts at 58 O 14 37 536567 98 122124 183199 C LO OK Algorithm Like C SCAN but only seeks to farthest request in queue Returns to lowest request not start of disk queue 98 183 37 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 183199 Choosing a Disk Scheduling Algorithm SSTF increased performance over FCFS SCAN C SCAN good for heavy loads less chance of starvation C LOOK good overall File allocation plays a role contiguous allocation limits head movement 39 Note only considering seek time rotational latency also important but hard for OS to know doesn t have physical drive L characteristics drive controllers implement some queueing and request coalescing 20 Why not have drive controller do all the scheduling 39 Would be more ef cient but 39 OS knows about constraints that the disk doesn t demand paging gt application lO write gt read if cache is almost full guaranteeing write ordering eg journaling data ushing 21 Aside Linux I O Schedulers 39 Linus Elevator default in 24 kernel merges adjacent requests and sorts request queue can lead to starvation in some cases though big push to change for 26 kernel 39 Deadline lO Scheduler merges amp sorts request expiration timer multiple queues to minimize seeks while ensuring request don t starve Anticipatory lO Scheduler waits a few ms after a read request to see if another one is made high probability acts like deadline scheduler otherwise loses time if wrong but big win if right 22 22 LinuX Schedulers ctd 39 Complete Fair Queueing lO Scheduler different than the others assigns queues based on originating process queues are serviced round robin usually picking 4 requests from each queue at a time good for multimedia eg ensuring audio buffers are full 39 When to use which Linus Elevator obsolete 7 Deadline good for lots of seeks critical workloads Anticipatory good for servers CFQ desktops 23 23 Disk Management 39 Low level formatting 39 Logical formatting 39 Booting Bad block recovery 39 Swap space 24 Low Level Physical Formatting 39 divide disk into sectors for disk controller to read and write sector numbers error correcting codes ECC other identifying information eg servo control data written to each sector 39 usually only done at factory can restore factory configuration reinitialize 25 High Level Logical Formatting Before formatting OS needs to partition the disk into 1 or more cylinder groups why more than 1 root vs swap partitions dual boot etc 39 write a le system onto the disk structures such as file allocation table FAT DOS or inodes UNIX 39 write the boot block boot sector 26 Boot Process 39 Bootstrapping starts from a process in ROM 39 Boot loader reads a bootstrap program from the bootblock on PCs Master boot record MBR rst sector on disk 446 bytes then 64 byte partition table 39 Second stage boot loader program Whose location is pointed to from MBR NTLDR on Windows LILO GRUB on Linux choose the partition to boot from to start to OS 27 Bad Block Recovery 39 Most disks have some bad blocks even from the factory 39 ECC used Reed Solomon encoding on modern disks to try and recover Savior Spd g drive marks bad block and maps to a spare block the OS doesn t see Savior Szj39szz39 g drive remaps blocks in order on disk skipping over bad one Disk does lots of background tasks H 7 Still Avoid head crashes 28 Swap Space Management 39 Swap space used for Virtual memory extension of main memory 39 Often given its own disk partition Can hold process images or memory pages Linux and Solaris page slots within swap les or partitions only allocate swap page slot when page forced out of memory swap map indicates how many processes using 29 Linux Swap Structures swap area page 39 slot swap partition or swap file swap map 1 Attaching Disks to Networks 39 NAS network attached storage RPCs between host and storage eg NFS what we use iSCSI 39 SAN storage area network multiple connected storage arrays servers connect directly to SAN 39 Becoming more like each other eg Open Storage Networking proposal from 5 NetApp combines elements of each 31 SCSI vs IDEATA Originally speed but with serial ATA SATA 39 interface speeds have caught up 39 SCSI supports more drives on a bus but SATA can be bene cial for small numbers Why pay more for SCSI Disks manufactured differently assumed to be server enterprise vs personal often faster eg 15K disks usually only SCSI SCSI drives better constructed O ring sealing air r flow more rigidity stronger actuator motors more reliable ATA cheap though 1 TB SATA lt 73 GB scs132 32 Summary 39 Storage is critical and getting more so physical characteristics cylinders tracks heads sectors 39 seek rotation time 39 Scheduling algorithms affect system performance Storage management boot process swap space On your own look over NAS and SAN gs quot Recommended RAID 015 most common 33 33 39 Next time File Systems 34