File Systems and Virtual Memory Lecture Notes PDF

Agenda November 12 – Lecture 22 Reminders Read 3 EP: Chapters 39, 40: Module: 9 Chapters 20 – 22 Virtual Memory Module 8 Project 4 – Driving Simulation using threads and concurrency Demo Due 11/20 Project 5 – Implementing a Simple File System 1st deliverable 11/13...

Agenda November 12 – Lecture 22 Reminders Read 3 EP: Chapters 39, 40: Module: 9 Chapters 20 – 22 Virtual Memory Module 8 Project 4 – Driving Simulation using threads and concurrency Demo Due 11/20 Project 5 – Implementing a Simple File System 1st deliverable 11/13 Attendance Quiz 11/13 1 Last Time File Systems Introduction Directories Physical vs Logical Directories Disk Structure & Persistent Storage File Allocation Methods Project 5 Today File Systems Project 5 Indexed Allocation Multi-Level Indexing / Linux iNode Demand Paging Page Replacement File System (disk) Layout (Project 5) Boot Sector [reserved sector(s)] Project 5: includes information that describes the ‘volume’ and locations, sizes and organization of directories FATs [File Allocation Table organization] Length of FAT is identified in the boot sector Root Directory (Project 5: this is the only directory/folder) Maximum number of root directory entries identified in the boot sector Each directory entry is 32 bytes Data Area The File Allocation Table File Allocation Table (FAT) on disk is a contiguous number of sectors (blocks) immediately following the area of reserved blocks [a duplicate FAT?] FAT is a list of entries that map to each block on the volume [Physical Directory] Each entry records one of five things: the block number of the next block in a chain a special end of block-chain (EOC) entry that indicates the end of a chain of blocks a special entry to mark a bad block a zero to note that the block is unused File Allocation Table The disk is divided into blocks (Project 5: 8192 blocks) The number of blocks and the size of a block should be identified in the boot block The File Allocation Table has only one entry per disk block For Project 5, this entry uses 16 bits for a simulated FAT16 This would map 65,536 blocks This entry specifies a block number FAT table  FAT Logical Directory Entry Directory Table (Folder) A directory table is a special type of file that represents a directory Each file or directory stored within it is represented by a 32-byte entry in the table. Each entry records the name, extension, attributes (archive, directory, hidden, read-only, system and volume), the date and time of last modification, the address of the first block of the file/directory's data and finally the size of the file/directory All Directory Tables are stored in the Data Region Directories can be extended by adding additional clusters to the directory file. (Project 5: the root directory of 64 entries could be pre-allocated in data blocks.) Project 5 typedef struct { char name; Name Cr Date/time … 1st_blk char attribute; char c_time; // hh:mm:ss Name Cr Date/time … 1st_blk char c_date; // mmddyyyy char last_access_date; char last_modified_time; … char last_modified_date; short cluster_num_in_fat; int f_size; Name Cr Date/time … 1st_blk } directory_entry; Name Cr Date/time … 1st_blk FAT Directory Data Blocks Directory Entries (MS-DOS) A sample HEX dump of a FAT directory with 8 character file name and 3 character file name extension HexFiend – Mac Neo - WIndows Boot Sector (MS-DOS) First disk sector (512 bytes) of a FAT filesystem  Directory Entry points to an Indexed Allocation Index Block Index block lists allocated Indexed Allocation blocks How large should the index block be? Every file must have an index block, so we want the index block to be as small as possible. If the index block is too small, however, it will not be able to hold enough pointers for a large file. Indexed Allocation Allocate fixed-sized blocks for each file Meta-data: Fixed-sized array of block pointers Allocate space for pointers at file creation time D D A A A D B B B B C C C B B D B D Advantages No external fragmentation Files can be easily grown up to max file size Supports random access Disadvantages Large overhead for meta-data: – Wastes space for unneeded pointers (most files are small!) Multi-Level Indexing Variation of Indexed Allocation Dynamically allocate hierarchy of pointers to blocks as needed Meta-data: Small number of pointers allocated statically Additional pointers to blocks of pointers Examples: UNIX FFS-based file systems, ext2, ext3 double indirect indirect indirect triple indirect Comparison to Indexed Allocation Advantage: Does not waste space for unneeded pointers – Still fast access for small files – Can grow to what size?? Disadvantage: Need to read indirect blocks of pointers to calculate addresses (extra disk read) – Keep indirect blocks cached in main memory Unix iNode Inode number Access Control List (ACL) Extended attribute Direct/indirect disk blocks Number of blocks File access, change and modification time File deletion time File generation number File size File type Group Number of links Owner Permissions Status flags Flexible # of ExtentS Modern file systems: Dynamic multiple contiguous regions (extents) per file Organize extents into multi-level tree structure Each leaf node: starting block and contiguous size Minimizes meta-data overhead when have few extents Allows growth beyond fixed number of extents Fragmentation (internal and external)? + Both reasonable Ability to grow file over time? + Can grow Seek cost for sequential accesses? + Still good performance Speed to calculate random accesses? +/- Some calculations depending on size Wasted space for meta-data? + Relatively small overhead Choosing an optimal disk allocation strategy depends on the specific use case, and the trade-offs between fragmentation, file growth flexibility, access performance. Systems with a prevalence of small files benefit from multi-level indexing, while extent-based allocation addresses fragmentation concerns for larger files. Back to Memory Management & Virtual Memory  Demand Paging Demand paging is the principle of loading a page into memory only when the page is needed, rather than at the start of the execution. To Implement Demand Paging A present bit is a binary flag in each page table entry that indicates whether the corresponding page is currently resident in memory. If a page is resident, then the entry points to the frame that holds the page. A page fault is an interrupt that occurs when a program attempts to reference a non- resident page. The interrupt triggers the operating system to find the page on disk, copy the page into a frame, and set the present bit to 1 and then continue executing  Demand Paging (cont.) A process executes the code br m... m: ld R,x where the branch location is on a resident page Initially 3 pages in memory (2, 3, R k) When R is referenced, load another page  If there is a no previous reference to a page, the first reference to that page will trap (interrupt) into the operating system: page fault 1.Operating system looks at page table bits to decide: Truly Invalid reference → abort Just not in memory 2.Get empty frame 3.Read page from disk into frame 4.Update page table with page/frame information 5.Set Present bit = 1 6.Restart the instruction that caused the page fault Page Fault  Following a Page Fault, Restarting an instruction Instruction requires hardware support since some memory areas or registers may have been changed prior to Backup/restart the page fault block move (fault if part of the data are on an out of memory page and some cells already overwritten) auto increment/decrement location or register Could Be and then fault. @R1+ Multiple faults to satisfy per Instruction Page Fault (Cont.) Steps in Handling a Page Fault