CSCE 313 Lecture 13
« previous | Thursday, March 1, 2012 | next »
File System Organization
Highest level: Partition
- Partitions can be made on a single disk or across multiple disks
- Directory and files are then stored in the partitions
Organize directory to find file quickly, group files by properties, naming (same name for multiple files, multiple names for same file)
Directory Structure
Single-Level
Directory is vector of links to files.
- Limited Filename length
- not multi-user friendly.
Two-Level
Master directory for users that points to user directory for each user's file that points to files
- Path names required to identify unique files.
- Where are system files?
Tree-Structured Directories
Almost traditional structure for UNIX and Linux machines.
- current directory
- complete and relative file paths
- search paths for $PATH variable.
Generalized Tree Structure
Same as above, but offers links so same file appears in multiple directories.
- links (referencing affects file to which it is linked)
- consistency, deletion, and privileges to create/access links
char * getcwd(char * buf, size_t size); Gets the current working directory (full path)
Logical View of File Management
- User
- File structure (Accessed by directory management and access control)
- Records (accessed by an access method)
- Physical blocks in memory
- Physical blocks on disk
UNIX Implementation: inodes
An inode stores the following information:
- Size (in bytes)
- Owner UID and GID
- Relevant times (created, accessed, modified)
- link and block counts
- permissions
- "Multilevel allocation table" to actual file content
The Multilevel allocation table is a collection of blocks that point to relevant locations of file pieces on disk.
- Direct: block in MAT to block on disk
- Single indirect: block to another collection of blocks that point to blocks on disk.
- Double inderect, Triple indirect (yada yada)
inode size is fixed, so the MAT is limited in size.
Every system has a block size (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} ) Each index is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} bytes (a pointer is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p=1} bytes) Largest file sizes:
- Direct: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nb}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=\alpha+\beta} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} direct and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} indirect: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha b+\beta \cdot b \cdot b}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=\alpha+\beta+\gamma} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} direct, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} indirect, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} double indirect: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha b + \beta \cdot b \cdot b + \gamma \cdot b^2 \cdot b}
- In general, for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_1}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_2}
, ..., Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_k}
indirection levels (where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0}
is direct), the maximum size is
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^k bn_i \left( \frac{8b}{p} \right)^i}
Note: filenames are not stored in inode. The names are stored in a directory file that contains the file name and the inode number of the associated file. There are two reasons for this:
- Same inode can have multiple links on disk
- Consistent inode block size.
Links
The link counter in inode only counts hard links.
- To delete files, use unlink(char * path);. Once link counter reaches 0, the inode is removed.
Symbolic links do not update inode link counter, but it creates a new inode that stores the path of the actual file that it's referencing.