- many files, much space - where is everything?
- directories impose structure and map file names to storage-device blocks
- a directory is usually a file - another chicken-egg problem
- an indexed sequential file - content or metadata addressable would be
nice; name inverted indexing
- tagged by metadata
- accessed by utility routines - next, last, find
- interesting protection and synchronization problems
- directory structures - the global file organization
- flat directory systems - everything's right in front of you.
- semi-flat (two-level) systems - cpm (users), dos (devices)
- because directories are files, you can build arbitrary structures -
graphs
- trees - the usual structure supported
- simple, convenient, nice properties, easy and simple traversal
- roots, paths, current directory, absolute and relative file
locations
- references over there can get cumbersome - acyclic links make the
tree more convenient, but complicate it
- arbitrary graphs - the www; google as a content-addressable directory
- directory operation
- directories translate file names to storage blocks, or perhaps metadata
- break the file name into pieces
- starting at the root directory, look up the first piece to get the next
directory
- continue to look up the next piece in the current directory until all
pieces are processed
- a flexible arrangement - mounting, network distribution, multiple file
systems
- complications - permissions, cycles
- inserting and deleting entries - handled via the system routines
- directory implementation
- a two step mapping - file name -> file metadata -> file storage blocks
- a single file can hold the first mapping - but name lookup is frequent
and metadata can be large; many disk accesses per lookup
- separate into two files - a name and a link to the metadata, then the
metadata; better performance, greater flexibility
- file lookup
- break the name into pieces - a syntactic operation
- figure out the starting point - absolute (root) or relative (cwd or
links)
- treat each piece as a directory name and look up the following piece
- cashing is important for good performance - cache name and metadata
entries
- this is a flexible procedure - mounting, remote file systems, virtual
file systems
- unix example
- index-nodes (i-nodes) contain file metadata - permissions, file
blocks, dates and times
- each file system has a fixed number of i-nodes determined when the
file system is created
- i-nodes are spread around in disk blocks throughout the file system
- a directory record contains a name and an i-node number
- several directory entries can point to the same i-node - hard links
- the root directory or i-node is in a known location
This page last modified on 1 December 2004.