File Structure None

File Structure

• None:

• File can be a sequence of words or bytes

• Simple record structure:

• Lines
• Fixed Length
• Variable Length

• Complex Structure:

• Formatted documents
• Relocatable load files

• Who decides?

File Access Methods

• Sequential Access

• Based on a magnetic tape model
• read next, write next
• reset

• Direct Access

• Based on fixed length logical records
• read n, write n
• position to n
• relative or absolute block numbers

Directory Structure

• Collection of nodes containing information on all files

Information in a Device Directory

• File name:

• File Type:

• Address:

• Current Length

• Maximum Length

• Date Last accessed (for archiving)

• Date Last updated (for dumping)

• Owner ID

• Protection information

Directory Operations

• Search for a file

• Create a file

• Delete a file

• List a directory

• Rename a file

• Traverse the file system

Objectives for a Directory System

• Make it efficient

• It should be easy to locate a file quickly

• Make file (and directory) naming convenient

• Allow 2 users to have the same name for different files
• Allow the same file to have more than 1 name

• Allow logical grouping of files

• All word processing files together
• All c++ files together
• etc.

Alternative Directory Structures

• Single-Level Directory

• Issues:

• Naming
• Grouping

Alternative Directory Structures

• Two-Level Directory

Tree-Structured Directory

File System Structure

• A data structure on a disk that holds files

• Disk Storage attributes:

• Allows direct access to any given block of information
• Supports re-writing in place (copy block, modify, rewrite)

• Organized in Layers:

• Application Programs
• Logical file system
• file-organization module
• basic file system
• I/O control
• devices

File System Organization

• Devices

• Peripheral equipment- disk drives, tapes, etc.

• I/O Control

• device drivers and interrupt handlers
• Communicates directly with peripheral devices
• Starts and closes out I/O request

• Basic File System

• Requires knowledge of physical device (track, cylinder, head, etc.)
• Manages data transfer at block level (buffering, placement)

File System Organization

• File-organization Module

• Maps logical block structure of file to physical block structure of disk
• Includes free space manager

• Logical file system

• Manages file directory information
• Provides security, protection

• Applications

• Maintains basic data about the file
• Allows users to access file information

File System Structure

• Access to File

• file control block (generic)
• file descriptor (UNIX)
• file handle (Windows)

• File System Requirements

• boot mechanism
• file system information
• file information
• file data

Allocation Methods Contiguous Allocation

• Each file occupies a set of contiguous blocks on the disk.

• Number of blocks needed identified at file creation

• May be increased using file extensions

• Advantages:

• Simple to implement
• Good for random access of data

• Disadvantages

• Files cannot grow
• Wastes space

Contiguous Allocation

Allocation Methods Linked Allocation

• Each file consists of a linked list of disk blocks.

• Advantages:

• Simple to use (only need a starting address)
• Good use of free space

• Disadvantages:

• Random Access is difficult

Linked Allocation

Linked Allocation

Allocation Methods Indexed Allocation

• Collect all block pointers into an index block.

• Advantages:

• Random Access is easy
• No external fragmentation

• Disadvantages

• Overhead of index block

Indexed Allocation

Indexed Allocation

UNIX File System File Types

• Regular File

• Directory

• Block-oriented Device

• Character-oriented Device

• Symbolic Link

UNIX File Ownership

File Access Model

• open -- read -- write -- close

• fdesc = open (*filename, r / w / a / +);

• n = read (fdesc, buff, 24);

• n = write (fdesc, buff, 24);

• lseek (fdesc, 100L, L_SET);

• (L_SET, L_CUR, L_END)

• close (fdesc);

Concurrent File Access

• From separate processes

• OPEN generates a new file descriptor.
• Allows independent access to the same file.
• No inherent blocking in access

• From parent / child processes

• fork duplicates all active file descriptors.
• all processes access a common “current” pointer

• File locking

• flock, lockf

UNIX File Sharing - unrelated processes -

UNIX File Sharing - related processes -

UNIX i-node

UNIX i-node

UNIX i-node

I-node File Sizes

Disk Drive Layout (simplified)

Sample filesystem: Creating the directory “testdir”

Sample filesystem: Creating the directory “testdir”

Sample filesystem: Creating the directory “testdir”

Sample filesystem: Creating the directory “testdir”

Sample filesystem: Creating the directory “testdir”

Sample filesystem after creating the directory “testdir”

Viewing directory structure

• ls –ai /

• 2 .
• :
• 1730 home

• ls –ai /home

• 1730 .
• 2 . .
• :
• 199 rcotter

Linux File System Structure

• Linux uses a Virtual File System (VFS)

• Defines a file object
• Provides an interface to manipulate that object

• Designed around OO principles

• File system object
• File object
• Inode object (index node)

• Primary File System - ext2fs

• Supports (or maps) several other systems (MSDOS, NFS (network drives), VFAT (W95), HPFS (OS/2), etc.

Virtual Filesystem

• A kernel software layer that handles all system calls related to a standard UNIX filesystem.

• Supports:

• Disk-based filesystems
• IDE Hard drives (UNIX, LINUX, SMB, etc.)
• SCSI Hard drives
• floppy drives
• Network filesystems
• remotely connected filesystems
• Special filesystems
• /proc

VF Example

• inf = open (“/floppy/test”,

• O_RDONLY, 0);

• outf = open (“/tmp/test”, O_WRONLY|O_CREATE|O_TRUNC, 0600);

• do {

• cnt = read(inf, buf, 4096);

• write (outf, buf, cnt);

• } while (cnt);

• close (outf);

• close (inf);

Virtual file system Model

• Superblock object

• metadata about a mounted filesystem

• inode object

• general information about a specific file

• file object

• information about process and open file interaction

• dentry object

• directory entry information

Virtual Filesystem and Processes

Ext2fs History

• Minux

• extfs

• ext2fs - 1994

Ext2fs Blocks

• 1k default

• 2k, 4k possible

• choice based on file sizes

Ext2fs Disk Data Structures

• Each Block Group contains:

• A copy of the Super Block
• A copy of the group of block group descriptors
• A data block bitmap (for this group)
• An inode bitmap (for this group)
• A group of inodes (for this group)
• Data blocks

Disk Data Structures

• SuperBlock

• Contains metadata about the block group
• # free blocks,
• # free inodes,
• block size,
• times (last mount, last write),
• check status,
• blocks to pre-allocate,
• alignments, etc. (~38 items)

Disk Data Structures

• Block Groups

• Block group limited to 8 * block size by data block bitmap.
• 1k block limited to 8,192 blocks or 8 mbytes per block group. 4k block = 128 mbytes

• Group descriptor - 24 bytes per group

• block numbers for bitmaps, start of tables, etc.

Disk Data Structures

• Inode Table

• Inodes - 128 bytes
• File type and access rights
• owner
• length
• timestamps (last access, last change, etc.)
• hard links counter
• pointers to data blocks,
• etc.

Disk Data Structures

• Items cached in memory on filesystem mount

• Superblock - always cached
• Group descriptor - always cached
• Block bitmap - fixed limit - most recent only
• Inode bitmap - fixed limit - most recent only
• Inode - dynamic
• Data block - dynamic

File Blocks Grouped

• Physically and logically

• Inodes distributed throughout disk

• Data blocks allocated close to inode

• Pre-allocation of free blocks to minimize frag.

Summary Features

• Fast Symbolic Links

• pre-allocation of data blocks

• file-updating strategy

• immutable files or append only files

Journal File Systems

• Designed to speed file system recovery from system crashes.

• Traditional systems use an fs recovery tool (e.g. fsck) to verify system integrity

• As file system grows, recovery time grows.

• Journal File Systems track changes in meta-data to allow rapid recovery from crashes

Journal File System

• Uses a version of a transaction log to track changes to file system directory records.

• If a system crash occurs, the transaction log can be reviewed back to a check point to verify any pending work (either undo or redo).

• For large systems, recovery time goes from hours or days to seconds.

Journal File System - Examples

• XFS

• Commercial port by SGI (IRIX OS)
• Based on 64 bit system (ported to 32 bit)
• Supports large systems 2TB -> 9 million TB
• Uses B+trees for improved performance
• Journals file system meta-data
• Supports Quotas, ACLs.
• Supports filesystem extents (contiguous blocks)

Journal File System - Examples

• JFS

• Commercial Port by IBM. Used in OS/2
• 64 bit system ported to 32 bits.
• Journal support of meta-data.
• System Size 2TB -> 32PB
• Built to scale on SMP architectures
• Uses B+trees for improved performance
• Supports use of extents.

Journal File System - Examples

• ReiserFS

• Designed originally for Linux (32 bit system)
• Supports file systems to 2TB -> 16TB
• Journal support of meta-data
• Btree structure supports large file counts
• Supports block packing for small files
• No fixed inode allocation - more flexible.

Journal File System - Examples

• Ext3fs

• Simple extension of ext2fs that adds journaling
• All virtual file system operations are journaled.
• Other limitations of ext2fs remain.

Journal File System - Examples

• ext4fs

• Next generation of file system development, incorporating improvements and changes to ext3fs.
• Journalling filesystem
• Improvements is journal checksumming
• Larger file systems – 1 MTB (exabyte)
• Larger files – 16 TB
• Delayed block allocation, multi-block allocator
• Allows files to be written as contiguous sequences of blocks: improves read performance of streaming data files.
• Poses the risk of lost data if system crashes before data is written.
• Use of extents
• Large (<= 128 MB) contiguous physical blocks.

Free Space Management

• Bit Vector management

• One bit for each block

• 0 = free; 1 = occupied

• Use bit manipulation commands to find free block

• Bit vector requires space

• block size = 4096 = 2 12
• disk size = 1 gigabyte = 2 30
• bits = 2 (30-12) = 2 18 = 32k bytes

Free Space Management

• Bit vector (advantages):

• Easy to find contiguous blocks

• Bit vector (disadvantages):

• Wastes space (bits allocated to unavailable blocks)

• Issues:

• Must keep bit vector on disk (reliability)
• Must keep bit vector in memory (speed)
• cannot allow memory != disk (memory = 1, disk = 0)

Free Space Management

• Linked List management

• Use linked list to identify free space

• Advantages:

• no wasted space

• Disadvantages:

• harder to identify contiguous space.

• Issues:

• Must protect pointer to free list

Free Space Management

• Grouping of blocks

Example File Systems

• CD-ROM

• ISO 9660
• Rock Ridge
• Joliet

• MS-DOS

Summary

• File Structures

• Directory Structures

• File System Implementation

• File System Management

• Example File Systems

Questions

• Two primary access methods are used to manage files.  Discuss these two methods, including  which types of physical devices each is normally associated with.

• What is the difference between a tree structured file directory and an acyclic graph directory?  Please give an example Operating System used today that uses each.

• Discuss 3 ways in which files might be allocated to file stores (disks). What are the advantages or disadvantages of each?

• How might a file system manage its free space so that it can easily assign space for a new file when needed? Give at least 2 approaches.

• What can an OS designer to improve the efficiency of a file system? What factors should be considered? How do those affect the efficiency of the system?

• Discuss at least 2 mechanisms that might be used to ensure the recovery of information stored in a file system.