File Allocation Methods and Access Techniques

File System

• A file system is a logical storage unit
• Files are mapped to non-volatile physical devices
• A file is a named collection of related information stored on secondary storage
• For users, a file is the smallest allotment of logical secondary storage
• Files represent programs (source and object code) and data
• Data can be numeric, alphabetic, alphanumeric, or binary
• Files can be free-form (e.g., text files) or rigidly formatted
• Generally, a file is a sequence of bits, bytes, lines, or records whose meaning is defined by the creator and user

File Attributes

• File attributes vary between operating systems, but typically include:
  • Name (human-readable symbolic name)
  • Identifier (unique, non-human-readable name for the file within the file system)
  • Type (needed for systems supporting different file types)
  • Location (pointer to device and file location)
  • Size (current size in bytes, words, or blocks; maximum allowed size)
  • Protection (access control information determining who can read, write, execute, etc.)
  • Time, date, and user identification for creation, modification, and last use (useful for protection, security, and usage monitoring)

File Operations

• Operating systems provide system calls for creating, writing, reading, repositioning, deleting, and truncating files
• Creating a file: File is initially empty
• Writing to a file: System call specifies file name and information to be written; system searches the directory to locate the file; A write pointer marks location in the file for the next write, updating whenever necessary
• Reading a file: System call specifies file name and memory location for the next block; system searches the directory for the associated entry; reads from the file location indicated by the read pointer; updates the read pointer
• Repositioning within a file (file seek): Positioning the current-file-position pointer to a given value; used for random access
• Deleting a file: Searching directory for the file; releasing file space; erasing the directory entry
• Truncating a file: Erases contents but keeps attributes, setting file length to zero, releasing file space

File Operations (Continued)

• Systems typically use open() system calls before file use
• An open-file table keeps information on all open files
• Operating systems usually use internal tables:
  • Per-process table—tracks files open to a process; stores information on how the process is using the file; includes the current file pointer
  • System-wide table—process-independent table, containing file location on disk, access dates, and file size; an open count for each file
• Information associated with an open file:
  • File pointer—The last read/write location in the file
  • File-open count—Tracks the number of opens and closes; zero on the last close, allowing removal of the entry

File Operations (Continued)

• Disk location of the file: Information needed for file location on disk is kept in memory for faster access during file operations
• Access rights: Each process opens a file in an access mode; information is stored in the per-process table for the system to allow or deny further I/O requests

File Types

• Various computer files exist - Examples:
  • executable
  • object
  • source code
  • batch
  • markup
  • word processor
  • library
  • print/view
  • archive
  • multimedia

File Access Methods

• Files store information accessible in several ways

• Sequential Access:

  • Simplest method; processes information in order, one record after the other
  • Commonly used by editors and compilers
  • Read operation (read next()) reads the next portion and automatically advances the file pointer
  • Write operation (write next()) appends to the end and advances to the end of the newly written material

• Direct Access:

  • File is viewed as numbered blocks or records
  • Allows programs to read and write records rapidly in any order (no specific order)
  • Examples: Databases are often direct access—a query computes the block number containing the answer, then reads that block directly to provide the desired information
    • Read operation is read(n), where n is the block number
    • Write operation for direct access is write(n)

• Other Access Methods:

  • Built on top of direct access
  • An index structure is usually used, with the index containing pointers to the various blocks
  • To locate a record, first search the index, then use the pointer to access the file and locate the desired record; secondary index files may be used if the index file is large

Allocation Methods

• Techniques for allocating file data on storage media
• Contiguous Allocation:
  • Allocates contiguous blocks on the disk
  • Defined by disk address and length (in block units) of the first block
  • Directory entry for each file includes the address of the starting block and the length of the allocated area

Allocation Methods (Continued)

• Contiguous Allocation (Problem & Solution):
  • Problem: External fragmentation
  • Solution: Copy entire file system to another disk, then copy files back to the original, allocating free contiguous space for compacting fragmentation

Allocation Methods (Continued)

• Linked Allocation:
  • Solves contiguous allocation problems by arranging file as a chain of disk blocks—blocks may be scattered
  • Directory stores pointers to the first and last blocks of the file

Allocation Methods (Continued)

• Linked Allocation(Disadvantages):

  • Inefficient for random access files—to locate the ith block must start at the first block and follow the pointers
  • Space required for file pointers—example: if a pointer occupies 4 bytes out of a 512-byte block, the wasted space is large

• Linked Allocation (other factors):

  • Not reliable if the operating system software or disk hardware has a bug in the software, and may result in the wrong pointer, leading to linking to free space or another file—solutions:
    • doubly linked lists—file name and relative block number in each block
    • File-allocation table (FAT): a table containing entries for each disk block, indexed by block number. Directory points to the first block of the file; the table entry indicates the next block. Chain continues till the end-of-file value; unused blocks are assigned a value of 0

Allocation Methods (Continued)

• Indexed Allocation:
  • Each file has its own index block—an array of disk block addresses—the ith entry of the index block points to the ith block of the file
  • Directory maintains the index address
  • Direct access—use index-block entry to locate the ith block
  • All pointers are set to null during file initialization
  • To write the ith block, a block is acquired from the free-space manager

Allocation Methods (Continued)

• Indexed Allocation (Disadvantage):
  • Index block pointer overhead is greater than linked allocation pointer overhead
  • Normally, an index block is one disk block; thus, it can be read and written directly; linking several index blocks can support larger files

Allocation Methods (Continued)

• Indexed Allocation (Multilevel Index):
  • First-level index block points to several second-level index blocks, which in turn point to the file blocks—used for accessing a specific block
• Combined Scheme (Indexed Allocation):
  • Inodes (file's inode) contain the first 15 pointers of the index block—the first 12 pointers in this block may be direct block pointers to the blocks containing the file's data; this helps reduce the space required for small files by eliminating need for a separate index block
  • The next three pointers point to indirect blocks, thus accessing data blocks indirectly

Directory Structure

• A collection of nodes containing information about all files
• Both the directory structure and files reside on disk; Examples:
  • Single-level directory—simple structure but has naming and grouping issues
  • Two-level directory—separate directories for each user, efficiently addressing the searching problem but lacking grouping capabilities
  • Tree-structured directories—the most used method, using a tree structure

File System Types

• General-purpose file systems
• Special-purpose file systems: Examples include memory-based volatile file systems (tmpfs) for temporary I/O; the object file system (objfs) for kernel symbols; and contract file system (ctfs) for daemons

Operations Performed on Directory

• Searching for a file
• Creating a file
• Deleting a file
• Listing a directory
• Renaming a file
• Traversing the file system

Directory Organization

• Directory organization is logically created for fast file retrieval
• Efficiency: Quickly locate files
• Naming: Convenient for users (Different users can have files with similar names. Files themselves can also have multiple names.)
• Grouping: Logic grouping of files based on similar properties

Protection

• The role of protection in a computer system is to provide a mechanism for the enforcement of policies governing resource use—these may be a fixed system design or set by the system, and/or individual users
• Goals of protection: -prevent mischievous/intentional violation of access restrictions -Ensure system components use system resources only as per policies -Protect against unauthorized or incompetent user misuse

Protection (Continued)

• Principles of protection: Least privilege—programs, users, and systems are given only the necessary privileges to perform their tasks

Protection (Continued)

• Domain of protection:
  • A computer system is a collection of processes and objects (hardware and software objects)
  • Each object has a unique name allowing it to be distinguished, and each object can be accessed only through defined operations
  • Access to a resource requires the process to have authorization. Access to resources is by domains with assigned permissions for that domain; switching between domains is permissible—domain switching occurs based on various criteria: User login, User logout, Process sending messages to a process
  • A domain can be a user, a process, or a procedure—if a domain is equivalent to a user, then its access rights depend on the identity of the user; or if the domain is equivalent to a process, then its access rights depend on the identity of the process
  • Domain access rights are defined by their rights—using access rights, a domain can access an object if the access right includes that permission
  • Each domain can be realized in ways (user, process or procedure)
  • Access matrix—a matrix containing each domain and object with specified rights; each row/column is an access right
  • Copying access rights—allow access right copying from one domain into another (indicated by an asterisk (*)) only within the column (object)

Protection (Continued)

• Access Matrix (continued):
  • Addition/removal of rights—the owner right controls these; if access(i, j) includes the owner right, then the process executing in domain Di can add/remove rights in Column j
  • Control rights: applicable to domain objects; if access(i, j) includes the control right, then a process executing in domain Di can remove access rights in row j

Explore the various methods of file allocation and the principles of file access. This quiz covers contiguous allocation, indexed allocation, linked allocation, and the principles of protection systems in computing. Test your knowledge on how these concepts apply to databases and security.