Operating Systems Lecture Notes

2014 November 18 • Directories

---

Outline

• Directories and file naming.
• Directory structures.
• Implementing directories.

The Story So Far

• Files are named, persistent, garguantian item sequences.
• Files are implemented as a file-block sequence defined by a linked-organized superstructure.
• The superstructure deals with files, but what deals with the superstructure?
• And were are the names?

Disk Layout Illustrated

File Naming

• Naming files seems straightforward, but can be subtle.
• Files are associated with character strings: cs520.html.
• Files can also be “named” by their contents.
  • That html file with the CS 520 outcomes assessment for last year.
  • Google's rise and search-based access, but also databases.

File Names

• A file name is a character sequence with syntax and semantics.
• Syntax includes character set and name structure.
  • Character sets: phishing, Unicode, collating sequences.
  • Name structure: name.ext or unstructured (mostly; there may be size limits and the like).
• Semantics raises more interesting questions.

File Name Semantics

• Should file names have a semantics?
  • Yes: understanding what it's working with makes operating systems smarter.
  • No: the semantics scope is huge and constantly changing.
• The general answer ranges from “no” (*nix) to “maybe a little” (Microsoft 8.3 names).
• Applications are free to impose whatever file-name semantics they want.

Content-Based Naming

• Content-based naming identifies files by their content.

  That e-mail from a student who failed 305 two years ago.

• Databases provide a similar, more structured, facility.
  • Combining databases and operating systems is an old and seductive idea (IBM's QuickSilver operating system).
• Search-based naming is a hybrid technique.

Names and Files

• A directory is a set of (name, file) pairs.
• A dictionary should provide efficient look-up and enumeration operations.
  • Look-up for name (and sometimes file) translation.
  • Enumeration for search and presentation.
• Sets don't support directories well.
  • Ordered lists or search trees are better.
  • But: unique names.

File Grouping and Structure

• Directories create structure by grouping file names.
• The structure so far is flat (or one-level).
• An undifferentiated flat structure is generally not helpful.
  • File names can provide some structure: rvc3bp.ftn .
• Flat directories can be huge, making efficient operations difficult.

One-Level Example

Fixed Multilevel Structure

• The file system (OS) can define a more structured, partitioned organization.
• Each file belongs to exactly one partition.
• Conceptually, each partition corresponds to a directory for files in that partition.
• File names reflect the partition structure.
  • partition-name/file-name
• The current partition (or working set or current directory) determines available files.

Implementing Partitions

• Partitions can be implemented with a single directory and file-name control.
  • A half-complete solution at best.
• Alternatively, devote a directory per partition
  • Simpler, more uniform implementation.
  • Smaller directories for better performance.
  • But global operations are more complex.
• How are the partition directories organized?

Directory Directory

• Bake the partition directories into the disk.
  • Fast and simple, but inflexible.
• When in doubt, recurse: use a directory to keep track of partition directories.
  • A set of (name, directory) pairs.
  • The root directory.
  • A FAT-ish approach.
• Files are organized in a simple, uniform, and dynamic depth-1 n-way tree.

Two-Level Illustrated

Hierarchical Structures

• Letting directories reference directories opens the gate.
• Directories can be organized into graphs.
  • Links are directories referencing directories.
• General graphs are possible (a.k.a. the WWW), but can cause problems.
  • Global traversal in the presence of cycles.
• Trees and dags are usually better structures.
  • There's usually no structural enforcement.

Graph Navigation

• Assuming a tree, each file has a unique path from the root.
• The sequence of names along the path is the absolute path name for the file.
• Graphically, adjacent names are delimited by the path separator (‘/’, ‘\’, ‘>’).
• An absolute path name starts with a path separator.
  • /etc/fstab
• Traversals go from parent to child.

Relative Paths

• Absolute path names can get long and repetitive.
• Establish an arbitrary directory as the working (or current) directory.
• The working directory becomes a pseudo-root for paths.
  • These relative paths, relative to the working directory.
  • Relative paths don't start with a separator character.

Directory Operations

• Create and delete for directories.
• Opendir, readdir, closedir for scanning and searching directory entries.
• Link (create), rename, and unlink (delete) entries in a directory.

Implementing Directories

• A directory is a file of (name, file) pairs.
  • A file is a reference the file superstructure.
• The directory entry may also contain file metadata.
  • The metadata can be split, or shared, with the file superstructure.

Summary

• Directories maintain (name, file) pairs.
  • And may contain file metadata.
• Directories can refer to other directories.
  • From this files can be organized in graph-like structures.
• Directories, being files, are implemented similarly.
  • Although not nearly as involved.

---

This page last modified on 2014 November 21.