Lecture Notes for Operating Systems

Directories, 1 August 2002

1. many files, much space - where is everything?

2. directories impose structure and map file names to storage-device blocks

3. a directory is usually a file - another chicken-egg problem

   1. an indexed sequential file - content or metadata addressable would be nice; name inverted indexing

   2. tagged by metadata

   3. accessed by utility routines - next, last, find

   4. interesting protection and synchronization problems

4. directory structures - the global file organization

   1. flat directory systems - everything's right in front of you.

   2. semi-flat (two-level) systems - cpm (users), dos (devices)

   3. because directories are files, you can build arbitrary structures - graphs

      1. trees - the usual structure supported

         1. simple, convenient, nice properties, easy and simple traversal

         2. roots, paths, current directory, absolute and relative file locations

         3. references over there can get cumbersome - acyclic links make the tree more convenient, but complicate it

      2. arbitrary graphs - the www; google as a content-addressable directory

5. directory operation

   1. directories translate file names to storage blocks, or perhaps metadata

   2. break the file name into pieces

   3. starting at the root directory, look up the first piece to get the next directory

   4. continue to look up the next piece in the current directory until all pieces are processed

   5. a flexible arrangement - mounting, network distribution, multiple file systems

   6. complications - permissions, cycles

   7. inserting and deleting entries - handled via the system routines

6. directory implementation

   1. a two step mapping - file name -> file metadata -> file storage blocks

   2. a single file can hold the first mapping - but name lookup is frequent and metadata can be large; many disk accesses per lookup

   3. separate into two files - a name and a link to the metadata, then the metadata; better performance, greater flexibility

   4. file lookup

      1. break the name into pieces - a syntactic operation

      2. figure out the starting point - absolute (root) or relative (cwd or links)

      3. treat each piece as a directory name and look up the following piece

      4. cashing is important for good performance - cache name and metadata entries

      5. this is a flexible procedure - mounting, remote file systems, virtual file systems

   5. unix example

      1. index-nodes (i-nodes) contain file metadata - permissions, file blocks, dates and times

      2. each file system has a fixed number of i-nodes determined when the file system is created

      3. i-nodes are spread around in disk blocks throughout the file system

      4. a directory record contains a name and an i-node number

      5. several directory entries can point to the same i-node - hard links

      6. the root directory or i-node is in a known location

This page last modified on 1 August 2002.