File Systems and Disk LayoutI/O: The Big PictureRotational MediaDisks and DriversUsing Disk StorageUnix File SyscallsNachos File Syscalls/OperationsPreview of Issues for File SystemsRepresenting a File On-Disk in NachosFile MetadataRepresenting Large FilesRepresenting Small FilesBasics of DirectoriesA Nachos Filesystem On DiskUnix File Naming (Hard Links)Unix Symbolic (Soft) LinksThe Problem of Disk LayoutFFS and LFSFFS Cylinder GroupsSequential File WriteSequential Writes: A Closer LookSmall-File Create StormSmall-File Create: A Closer LookAlternative Structure: DOS FATFile Systems and Disk LayoutFile Systems and Disk LayoutI/O: The Big PictureI/O: The Big PictureI/O BusMemory BusProcessorCacheMainMemoryDiskControllerDisk DiskGraphicsControllerNetworkInterfaceGraphicsNetworkinterruptsI/O BridgeRotational MediaRotational MediaSectorTrackCylinderHeadPlatterArmAccess time = seek time + rotational delay + transfer timeseek time = 5-15 milliseconds to move the disk arm and settle on a cylinderrotational delay = 8 milliseconds for full rotation at 7200 RPM: average delay = 4 mstransfer time = 1 millisecond for an 8KB block at 8 MB/sBandwidth utilization is less than 50% for any noncontiguous access at a block grain.Disks and DriversDisks and DriversDisk hardware and driver software provide basic facilities for nonvolatile secondary storage (block devices).1. OS views the block devices as a collection of volumes.A logical volume may be a partition of a single disk or a concatenation of multiple physical disks (e.g., RAID).2. OS accesses each volume as an array of fixed-size sectors.Identify sector (or block) by unique (volumeID, sector ID).Read/write operations DMA data to/from physical memory.3. Device interrupts OS on I/O completion.ISR wakes up process, updates internal records, etc.Using Disk StorageUsing Disk StorageTypical operating systems use disks in three different ways:1. System calls allow user programs to access a “raw” disk. Unix: special device file identifies volume directly.Any process that can open the device file can read or write any specific sector in the disk volume.2. OS uses disk as backing storage for virtual memory.OS manages volume transparently as an “overflow area” for VM contents that do not “fit” in physical memory.3. OS provides syscalls to create/access files residing on disk.OS file system modules virtualize physical disk storage as a collection of logical files.Unix File SyscallsUnix File Syscallsint fd; /* file descriptor */fd = open(“/bin/sh”, O_RDONLY, 0);fd = creat(“/tmp/zot”, 0777);unlink(“/tmp/zot”);char data[bufsize];bytes = read(fd, data, count);bytes = write(fd, data, count);lseek(fd, 50, SEEK_SET);mkdir(“/tmp/dir”, 0777);rmdir(“/tmp/dir”);process file descriptor tablesystem openfile table/etc tmpbinNachos File Syscalls/OperationsNachos File Syscalls/OperationsCreate(“zot”);OpenFileId fd;fd = Open(“zot”);Close(fd);char data[bufsize];Write(data, count, fd);Read(data, count, fd);Limitations:1. small, fixed-size files and directories2. single disk with a single directory3. stream files only: no seek syscall4. file size is specified at creation time5. no access control, etc. BitMapFileSystem DirectoryFileSystem class internal methods:Create(name, size)OpenFile = Open(name)Remove(name)List()A single 10-entry directory storesnames and disk locations for allcurrently existing files.Bitmap indicates whether each disk block is in-use or free.FileSystem data structures resideon-disk, but file system code alwaysoperates on a cached copy in memory(read/modify/write).Preview of Issues for File SystemsPreview of Issues for File Systems1. Buffering disk data for access from the processor.block I/O (DMA) must use aligned, physically resident buffersblock update is a read-modify-write2. Creating/representing/destroying independent files.disk block allocation, file block map structuresdirectories and symbolic naming3. Masking the high seek/rotational latency of disk access.smart block allocation on diskblock caching, read-ahead (prefetching), and write-behind4. Reliability and the handling of updates.Representing a File On-Disk in NachosRepresenting a File On-Disk in NachosFileHdr Allocate(...,filesize)length = FileLength()sector = ByteToSector(offset)A file header describes an on-diskfile as an ordered sequence ofsectors with a length, mapped bya logical-to-physical block map.OpenFile(sector)Seek(offset)Read(char* data, bytes)Write(char* data, bytes)OpenFile An OpenFile represents a file inactive use, with a seek pointer and read/write primitives for arbitrarybyte ranges.once upon a time/nin a land far far away,/nlived the wise and sagewizard.logicalblock 0logicalblock 1logicalblock 2OpenFile* ofd = filesys->Open(“tale”);ofd->Read(data, 10) gives ‘once upon ‘ofd->Read(data, 10) gives ‘a time/nin ‘bytessectorsFile MetadataFile MetadataOn disk, each file is represented by a FileHdr structure.The FileHdr object is an in-memory copy of this structure.bytessectorsetc.file attributes: may include owner, access control, time of create/modify/access, etc.logical-physical block map (like a translation table)physical block pointers in the block map are sector IDsFileHdr* hdr = new FileHdr();hdr->FetchFrom(sector)hdr->WriteBack(sector)The FileHdr is a file system “bookeeping” structurethat supplements the file data itself: these kinds ofstructures are called filesystem metadata.A Nachos FileHdr occupiesexactly one disk sector.To operate on the file (e.g.,to open it), the FileHdr mustbe read into memory.Any changes to the attributesor block map must be writtenback to the disk to make thempermanent.Representing Large FilesRepresenting Large FilesThe Nachos FileHdr occupies exactly onedisk sector, limiting the maximum file size.inodedirectblockmap(12 entries)indirectblockdoubleindirectblocksector size = 128 bytes120 bytes of block map = 30 entrieseach entry maps a 128-byte sectormax file size = 3840 bytesIn Unix, the FileHdr (called an index-node or inode) represents large files using a hierarchical block map.Each file system block is a clump of sectors (4KB, 8KB, 16KB).Inodes are 128 bytes, packed into blocks.Each inode has 68 bytes of attributes and 15 block map entries.suppose block size = 8KB12 direct block map entries in the inode can map 96KB of data.One indirect block (referenced by the inode) can map 16MB of data.One double indirect block pointer in inode maps 2K indirect blocks.maximum file size is 96KB +