COS 318: Operating Systems File Layout and DirectoriesTopicsFile System ComponentsSteps to Open A FileFile Read and WriteDisk LayoutData Structures for Disk AllocationContiguous AllocationLinked Files (Alto)File Allocation Table (FAT)Single-Level Indexed FilesDEMOS (Cray-1)Multi-Level Indexed Files (Unix)What’s in Original Unix i-node?ExtentsNamingDirectory Organization ExamplesLinear ListTree Data StructureHashingDisk I/Os to Read/Write A FileLinksOriginal Unix File SystemBSD FFS (Fast File System)FFS Disk LayoutWhat Has FFS Achieved?SummaryCOS 318: Operating SystemsFile Layout and Directories2TopicsFile system structureDisk allocation and i-nodesDirectory and link implementationsPhysical layout for performance3File System ComponentsNamingFile and directory namingLocal and remote operationsFile accessImplement read/write and other functionalitiesBuffer cacheReduce client/server disk I/OsDisk allocationFile data layoutMapping files to disk blocksManagementTools for system administrators to manage file systemsFile namingFile accessBuffer cacheDisk allocationManagementVolume manager4Steps to Open A FileFile name lookup and authenticateCopy the file descriptors into the in-memory data structure, if it is not in yetCreate an entry in the open file table (system wide) if there isn’t oneCreate an entry in PCBLink up the data structuresReturn a pointer to userProcesscontrolblock...OpenfilepointerarrayOpen filetable(system-wide)Filedescriptors(Metadata)FiledescriptorsFile systeminfoDirectoriesFile data5File Read and Write Read 10 bytes from a file starting at byte 2?seek byte 2fetch the blockread 10 bytesWrite 10 bytes to a file starting at byte 2?seek byte 2fetch the blockwrite 10 bytes in memorywrite out the block6Disk LayoutBoot blockCode to bootstrap the operating systemSuper-block defines a file systemSize of the file systemSize of the file descriptor areaFree list pointer, or pointer to bitmapLocation of the file descriptor of the root directoryOther meta-data such as permission and various timesKernel keeps in main memory, and is replicated on disk tooFile descriptorsEach describes a fileFile data blocksData for the files, the largest portion on diskSuperblockFile descriptors(i-node in Unix)File data blocksBootblock7Data Structures for Disk AllocationThe goal is to manage the allocation of a volumeA file header for each fileDisk blocks associated with each fileA data structure to represent free space on diskBit map that uses 1 bit per block (sector)Linked list that chains free blocks together…11111111111111111000000000000000…0000011111111000000000011111111111000001111000111100000000000000linkaddrsizelinkaddrsize…Free8Contiguous AllocationRequest in advance for the size of the fileSearch bit map or linked list to locate a spaceFile headerFirst block in fileNumber of blocksProsFast sequential accessEasy random accessConsExternal fragmentation (what if file C needs 3 blocks)Hard to grow files: may have to move (large) files on diskMay need compactionFile A File B File C9Linked Files (Alto)File header points to 1st block on diskA block points to the nextProsCan grow files dynamicallyFree list is similar to a fileNo external fragmentation or need to move filesConsRandom access: horribleEven sequential access needs one seek per blockUnreliable: losing a block means losing the restFile headernull. . .10217File Allocation Table (FAT)ApproachTable of “next pointers”, indexed by block•Instead of pointer stored with blockDirectory entry points to 1st block of fileProsNo need to traverse list to find a blockCache FAT table and traverse in memoryConsFAT table takes lots of space for large disk•Hard to fit in memory; so may need seeksPointers for all files on whole disk are interspersed in FAT table•Need full table in memory, even for one file•Solution: indexed files•Keep block lists for different files together, and in different parts of disk619399foo217EOFFAT039961911Single-Level Indexed FilesA user declares max sizeA file header holds an array of pointers to point to disk blocksProsCan grow up to a limitRandom access is fastConsClumsy to grow beyond the limitStill lots of seeksFile headerDiskblocks12DEMOS (Cray-1)IdeaUsing contiguous allocationAllow non-contiguousApproach10 (base,size) pointersIndirect for big filesPros & consCan grow (max 10GB)fragmentationfind free blocksdata... (base,size)... (base,size)data...13Multi-Level Indexed Files (Unix)13 Pointers in a header10 direct pointers11: 1-level indirect12: 2-level indirect13: 3-level indirectPros & ConsIn favor of small filesCan growLimit is 16G and lots of seek1 2 datadata...11 12 13 data... ... data... ... data... ...14What’s in Original Unix i-node?Mode: file type, protection bits, setuid, setgid bitsLink count: number of directory entries pointing to thisUid: uid of the file ownerGid: gid of the file ownerFile sizeTimes (access, modify, change)No filename??10 pointers to data blocksSingle indirect pointerDouble indirect pointerTriple indirect pointer15ExtentsInstead of using a fix-sized block, use a number of blocksXFS uses 8Kbyte blockMax extent size is 2M blocksIndex nodes need to haveBlock offsetLengthStarting blockIs this approach better than the Unix i-node approach?Block offsetlengthStarting block . . .16NamingText nameNeed to map it to indexIndex (i-node number)Ask users to specify i-node numberIconNeed to map it to index or map it to text then to index17Directory Organization ExamplesFlat (CP/M)All files are in one directoryHierarchical (Unix)/u/cos318/fooDirectory is stored in a file containing (name, i-node) pairsThe name can be either a file or a directoryHierarchical (Windows)C:\windows\temp\fooUse the extension to indicate whether the entry is a directory19Linear ListMethod<FileName, i-node> pairs are linearly stored in a fileCreate a file•Append <FileName, i-node>Delete a file•Search for FileName•Remove its pair from the directory•Compact by moving the restProsSpace efficientConsLinear