https://homeostasis.scs.carleton.ca/wiki/index.php?action=history&feed=atom&title=Operating_Systems_2019F_Lecture_16 2026-05-18T20:02:24Z Revision history for this page on the wiki MediaWiki 1.42.1 https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2019F_Lecture_16&diff=22538&oldid=prev 2020-03-20T02:08:14Z

<p>Created page with &quot;Note that this lecture was given on Monday rather than Wednesday. Please don&#039;t come to class for lecture on Wednesday, Nov. 6, instead watch the video below! ==Video== The...&quot;</p> <p><b>New page</b></p><div>Note that this lecture was given on Monday rather than Wednesday. Please don&#039;t come to class for lecture on Wednesday, Nov. 6, instead watch the video below!<br /> <br /> ==Video==<br /> <br /> The video from the lecture given on November 4th, 2019 (special time) [https://homeostasis.scs.carleton.ca/~soma/os-2019f/lectures/comp3000-2019f-lec16-20191104.m4v is now available].<br /> <br /> ==Notes==<br /> &lt;pre&gt;<br /> Lecture 16<br /> ----------<br /> <br /> Filesystem implementation<br /> <br /> * worth looking at the textbook<br /> <br /> One view of filesystems is as an implementation of open, read, write, close, etc<br /> <br /> But also, with persistent storage, a filesystem is a data structure (on persistent media of some kind)<br /> <br /> With standard in volatile memory data structures (ones in process memory), corrupted data structures aren&#039;t a big deal<br /> - restart the process<br /> <br /> Persistent data structures have to maintain integrity for a long time<br /> - much more likely to see corruption<br /> - can&#039;t &quot;restart&quot; - that would result in lost data<br /> (a restart is a reformat)<br /> <br /> Key design constraints for filesystems<br /> - store it in blocks (not bytes)<br /> - address storage with block numbers and offsets, not addresses<br /> - robust in the face of (accidental) corruption<br /> - random access is high latency (not true for SSDs)<br /> - sequential access is much lower latency<br /> <br /> UNIX filesystems have inodes<br /> - to allow multiple hard links, so filenames refer to inodes, and inodes refer to data<br /> <br /> Many, many UNIX filesystem implementations<br /> - ext4 is most common on Linux systems, but xfs is also used<br /> - bsd systems traditionally used ufs<br /> - btrfs, zfs are also important as next-generation filesystems<br /> <br /> Basic organization of UNIX-like filesystems:<br /> * data blocks<br /> * inode blocks<br /> - metadata (timestamps, length, owner, perms, etc)<br /> - data or references to data blocks<br /> * directory blocks (may be a type of inode block)<br /> * superblock(s) &lt;---<br /> Normally divisions between block types is defined at filesystem creation/formatting (e.g. by mkfs).<br /> <br /> Just like files have metadata, so do filesystems<br /> The superblock stores metadata on the filesystem<br /> - needed for when it is mounted<br /> - says how big it is, what type, other filesystem-specific parameters<br /> <br /> Normally the superblock is cached in RAM<br /> - will be updated periodically as filesystem state changes (e.g., number<br /> of free inodes)<br /> - will be written to disk periodically<br /> - most data is static<br /> <br /> Superblock is normally the first block of a filesystem<br /> - convenient!<br /> - but...what if it gets corrupted? You can&#039;t access the filesystem<br /> - but fortunately we have backups as part of the filesystem, at well-known<br /> offsets (which can vary by filesystem)<br /> <br /> When a filesystem gets corrupted, what do you do? you check it!<br /> - use fsck (file system check)<br /> <br /> If fsck has to repair the filesystem because of errors, it could make things worse.<br /> - error recovery procedures may cause loss of data<br /> <br /> If you really care about the data and don&#039;t have a current backup, do a low level (block level) copy of the filesystem *before* you run fsck.<br /> <br /> You really want backups of your openstack instances!<br /> <br /> The people who really understand filesystem structure are forensic analysts<br /> - helps them find deleted data<br /> <br /> On most UNIX filesystems, delete is just unlink<br /> - so inodes are reclaimed when there are no hard links to it<br /> - but being reclaimed does not mean it is erased, it is just added to the pool of inodes that can be overwritten<br /> - same for data blocks<br /> <br /> fsck on large disks<br /> -------------------<br /> * fsck involves walking the filesystem data structure looking for inconsistencies<br /> - data blocks referred to by multiple inodes<br /> - deleted inodes that still have names<br /> - etc.<br /> * fsck thus involves a lot of random disk access<br /> <br /> Older systems would tell you not to just turn off the computer...why?<br /> - late 1990s<br /> - because filesystem state was cached in RAM and would be lost<br /> - write caching<br /> - so filesystem on disk would be left in an inconsistent state,<br /> would need to run fsck to potentially repair<br /> - fsck times got longer and longer (10+ minutes), hours for RAID arrays<br /> <br /> RAID = redundant array of inexpensive disks originally, ways to combine<br /> multiple disks into one logical disk with higher performance (raid-0,<br /> striping), better reliability (raid-1, mirroring), or a mix of the two<br /> (raid 5 and higher)<br /> <br /> So, how do you avoid long fsck times?<br /> - write everything twice<br /> - write first to a journal: sequential record of activity, changes to fs<br /> - write later to main filesystem data structures (random access)<br /> <br /> With a journal, on fsck you just have to check the journal<br /> - any inconsistencies will be there<br /> - doesn&#039;t handle inconsistencies in &quot;old&quot; data<br /> <br /> next-generation filesystems have integrity protection for all data and metadata<br /> - zfs &amp; btrfs<br /> - will catch silent corruption<br /> <br /> log-structured filesystems<br /> - writing twice seems silly, especially if you are writing a lot<br /> - idea - why not make the journal the entire filesystem?<br /> - log will fill up, so you periodically clean things (write out new entries for up to date data and mark old ones as deleted)<br /> - originally developed for systems with high write load, such as online databases<br /> - but for today, we used them in solid-state disks<br /> <br /> Log-structured &quot;filesystems&quot; aren&#039;t directly accessible in an SSD<br /> - they are below the block interface level<br /> - needed because writes to same portion of SSD will destroy it<br /> - log structure is for wear leveling<br /> <br /> Holes in files in UNIX<br /> - if a file is all zeros, why allocate data blocks for those zeros?<br /> - if you just write a block of zeros, it will be allocated<br /> - but if you lseek past the end of a file and then write, the potions you skipped over will be filled in with virtual zeros (zero data that isn&#039;t stored)<br /> &lt;/pre&gt;</div>

Soma