Recap File Attributes File Operations Directories Naming Paths Absolute Paths Relative Paths Directory Operations File Implementations Contiguous Linked FAT Inode Moran OS Lecture 10 1 Links to Files Tannenbaum calls these shared files Idea is to give a file multiple names Unix supports two ways of doing this hard links soft or symbolic links Windows has these too Hard links create a new directory entry for an existing inode Symbolic links are files that contain the path of another file Moran OS Lecture 10 2 Hard Links Two names for the file foo Both point at the same inode Both share the same meta data because the meta data is stored in the inode A hard link increases the reference count of the inode Deleting a file only deletes the file if the reference count is zero Otherwise it simply deletes the directory entry Hard links can only be made to files Moran OS Lecture 10 3 Soft Links When a soft link is created a new file is created the new file contains the path of the file being linked to the new file has an attribute to let the system know it is a soft link Soft links can point to directories Soft links can point to non existent files Soft links do not increase the reference count so the thing pointed to can be deleted out from under the soft link Moran OS Lecture 10 4 Managing Disk Space Disks are divided into blocks Block sizes are a function of hardware Disks have high latency so very large block sizes make sense Most files are fairly small 5K so very large block sizes result in large fragmentation Almost any block size you can imagine has been tried in the pursuit of performance time and space Current typical disk block sizes are in the 1K 8K range Moran OS Lecture 10 5 Disk Block Sizes File system has one block size Disk has another usually smaller block size File system block size trade off larger blocks mean fewer disk transfers larger blocks mean more fragmentation i e waste Old Statistics for sample Unix FS 512 byte blocks 6 9 waste 1k byte blocks 11 8 waste 2k byte blocks 22 4 waste 4k byte blocks 45 6 waste Moran OS Lecture 10 6 Disk Block Layout We would like to lay blocks out in such a way as to maximize performance Blocks accessed together could be close together Huge amounts of effort were devoted to this at one time Hardware has tended to reduce the need for this kind of cleverness as disk cache sizes have gotten larger Clever layout schemes tend to make allocating blocks somewhat expensive Moran OS Lecture 10 7 Free Space Management At any moment we have some free and some allocated blocks on the disk Ways we can keep track of free blocks In memory bitmap with one bit per free block small block sizes make this get big Paged bitmap with one bit per free block Linked list with each block pointing to the next requires extra I O to handle fixing pointers Linked list with all of the links stored in the same place looks like an array of links to free blocks store the array in free blocks and keep the first one in memory Moran OS Lecture 10 8 File System Consistency 1 OS doesn t write everything to the disk immediately we keep a cache Machine might crash while write is occurring How we check for consistency Scan all blocks to see whether they are in a file or on the free list Problems include blocks on the free list more than once blocks in more than one file or the same file more than once blocks neither in a file nor on the free list Repair the block based problems Moran OS Lecture 10 9 File System Consistency 2 Scan directories and inodes Count how many directories point to every inode and compare this with the inode link counts inode count higher than directory count means that the file doesn t get deleted inode count lower than directory count means that the file gets deleted when it shouldn t Unix fsck and Windows scandisk perform both of these kinds of checks More modern systems tend to have journal file systems file system structure is always consistent Moran OS Lecture 10 10 File System Buffer Cache For performance reasons the OS will keep some blocks in memory reads will simply use the in memory copy writes update the in memory copy and the OS will decide when to write back to disk On a read we scan the cache to see if the block is there If not bring it in and read from the cache Write through means the OS updates the disk block at the same time slower and safer Write back means the OS updates the disk block at a later time faster and riskier Moran OS Lecture 10 11 Buffer Cache Replacement To free the space to bring in a new block we need to pick a block to discard like PRA We can use LRU to decide except we don t want blocks to go too long without getting written back blocks that contain file system structure inodes should be written back immediately partial disk blocks probably still being written shouldn t be thrown away Modified LRU with separate code to write blocks back to the disk before they are discarded Moran OS Lecture 10 12 User write fd buffer cnt buffer cnt logical file system buffers logical file blocks disk blocks Moran OS Lecture 10 13 OS Startup 1 Hardware is turned on Boot Program general purpose standalone pgm to load execute other standalone pgms standalone means it can run without kernel assistance standalone pgms linked with special i o libraries that let them read devices they have standalone device drivers Once boot is loaded it has to figure out what to load usually a hardwired path Moran OS Lecture 10 14 OS Startup 2 Boot loads pgms at addr 0 boot was loaded at 0 so it first relocates itself boot has all addresses as real so it is built with addresses set to where it will relocate Boot loads the kernel at addr 0 and starts it running hardware interrupts are blocked address translation is turned off Moran OS Lecture 10 15 OS Startup 3 Kernel will initialize in 3 phases assembly language pieces machine dependent machine independent Moran OS Lecture 10 16 Assembly Language Init Setup the run time stack Identify the CPU type Calculate physical memory Enable virtual address translation hardware kernel makes sure all real pages map to the correct virtual pages Create the hardware context for process 0 Invoke the initial C based entry point main Moran OS Lecture 10 17 Machine Dependent Init 1 main gets called with the number of the first free page main calls startup startup init error message buffer to display errors and messages on the console allocate memory for system data structs initialize kernel memory allocator autoconfigure