CS 414 Review IIAnnouncementsWhat does the disk look like?Disk overheadsDisk SchedulingRAID LevelsStable Storage AlgoFile System LayoutImplementing FilesLinked List AllocationUsing an in-memory tableI-nodesImplementing DirectoriesSlide 14Managing Free Disk SpaceBackup StrategiesFile System ConsistencyFS PerformanceBlock Cache ReplacementLFS Basic IdeaLFS CleaningFS ExamplesNetwork Stack: LayeringEnd-to-End ArgumentPacket vs. Circuit SwitchingLink level IssuesRepeaters and BridgesNetwork LayerTwo connection modelsDNS name serversPurpose of Transport layerUDPUDP FunctionalityTCPTCP SummaryRemote Procedure CallSecurity in Computer SystemsCryptography OverviewSecret-Key CryptographyPublic Key CryptographyDigital SignaturesAuthenticationSalting ExampleOne time passwordsSecurity Attacks & DefensesMobile Code ProtectionEncoding SecurityProtecting CapabilitiesSlide 49Slide 50Capability RevocationDistributed Systems: Event OrderingHappens-beforeTotal ordering?Partial OrderingTotal Ordering?Logical Timestamps w/ tie breakerCategories of failuresDistributed Decision MakingCS 414 Review II2Announcements•Today is the last day of class!!!–You are (almost) done!•Final, Wednesday, May 16th, 7-9:30pm (2½ hour exam)–110 Hollister–Exam will be comprehensive, covers entire semester–Closed book, no calculators/PDAs/…–Bring ID•Sixth and final project due Thursday, May 10th •I will be out of town next week (Monday, May 7th - 10th)–return Friday, May 11th3What does the disk look like?4Disk overheads•To read from disk, we must specify:–cylinder #, surface #, sector #, transfer size, memory address•Transfer time includes: –Seek time: to get to the track –Latency time: to get to the sector and –Transfer time: get bits off the diskTrackSectorSeek TimeRotationDelay5Disk Scheduling •FCFS•SSTF•SCAN•C-SCAN•LOOK•C-LOOK6RAID Levels•0: Striping•1: Mirroring•2: Hamming Codes•3: Parity Bit•4: Block Striping•5: Spread parity blocks across all disks•0+1 and 1+07Stable Storage Algo•Use 2 identical disks–corresponding blocks on both drives are the same•3 operations:–Stable write: retry on 1st until successful, then try 2nd disk–Stable read: read from 1st. If ECC error, then try 2nd –Crash recovery: scan corresponding blocks on both disks•If one block is bad, replace with good one•If both are good, replace block in 2nd with the one in 1st8File System Layout•File System is stored on disks–Disk is divided into 1 or more partitions–Sector 0 of disk called Master Boot Record–End of MBR has partition table (start & end address of partitions)•First block of each partition has boot block–Loaded by MBR and executed on boot9Implementing Files•Contiguous Allocation: allocate files contiguously on disk10Linked List Allocation•Each file is stored as linked list of blocks–First word of each block points to next block–Rest of disk block is file data11Using an in-memory table•Implement a linked list allocation using a table–Called File Allocation Table (FAT)–Take pointer away from blocks, store in this table12I-nodes•Index-node (I-node) is a per-file data structure–Lists attributes and disk addresses of file’s blocks–Pros: Space (max open files * size per I-node)–Cons: what if file expands beyond I-node address space?13Implementing Directories•When a file is opened, OS uses path name to find dir–Directory has information about the file’s disk blocks•Whole file (contiguous), first block (linked-list) or I-node–Directory also has attributes of each file•Directory: map ASCII file name to file attributes & location•2 options: entries have all attributes, or point to file I-node14Implementing Directories•What if files have large, variable-length names?•Solution:–Limit file name length, say 255 chars, and use previous scheme•Pros: Simple Cons: wastes space–Directory entry comprises fixed and variable portion•Fixed part starts with entry size, followed by attributes•Variable part has the file name•Pros: saves space •Cons: holes on removal, page fault on file read, word boundaries–Directory entries are fixed in length, pointer to file name in heap•Pros: easy removal, no space wasted for word boundaries•Cons: manage heap, page faults on file names15Managing Free Disk Space•2 approaches to keep track of free disk blocks–Linked list and bitmap approach16Backup Strategies•Physical Dump–Start from block 0 of disk, write all blocks in order, stop after last–Pros: Simple to implement, speed–Cons: skip directories, incremental dumps, restore some file•No point dumping unused blocks, avoiding it is a big overhead•How to dump bad blocks?•Logical Dump–Start at a directory–dump all directories and files changed since base date–Base date could be of last incremental dump, last full dump, etc.–Also dump all dirs (even unmodified) in path to a modified file17File System Consistency•System crash before modified files written back–Leads to inconsistency in FS–fsck (UNIX) & scandisk (Windows) check FS consistency•Algorithm:–Build 2 tables, each containing counter for all blocks (init to 0)•1st table checks how many times a block is in a file•2nd table records how often block is present in the free list–>1 not possible if using a bitmap–Read all i-nodes, and modify table 1–Read free-list and modify table 2–Consistent state if block is either in table 1 or 2, but not both18FS Performance•Access to disk is much slower than access to memory–Optimizations needed to get best performance•3 possible approaches: caching, prefetching, disk layout•Block or buffer cache:–Read/write from and to the cache.19Block Cache Replacement•Which cache block to replace?–Could use any page replacement algorithm–Possible to implement perfect LRU•Since much lesser frequency of cache access•Move block to front of queue–Perfect LRU is undesirable. We should also answer:•Is the block essential to consistency of system?•Will this block be needed again soon?•When to write back other blocks?–Update daemon in UNIX calls sync system call every 30 s–MS-DOS uses write-through caches20LFS Basic Idea•Structure the disk a log–Periodically, all pending writes buffered in memory are collected in a single segment–The entire segment is written contiguously at end of the log•Segment may contain i-nodes, directory entries, data–Start of each segment has a
View Full Document
Unlocking...