[OS]File System

Disk System

• Disk pack
  • Sector
  • Track
  • Cylinder
  • Platter
  • Surface
• Disk drive
  • Head
  • Arm
  • Positioner (boom)
  • Spindle

    Disk Address

• Physical disk address
• Logical disk address: relative address

  Data Access in Disk System

  1. Seek time
  2. Rotational delay
  3. Data transmission time

File System

• Files
• Directory structure
• Partitions

File Concetp

• File attributes
  • Name
  • Identifier
  • Type
  • Location
  • Size
  • Protection
    • access control information
  • User identification (owner)
  • Time, date
    • creation, late reference, last modificatio
• File operations
  • Create
  • Write
  • Read
  • Reposition
  • Delete
  • Etc.

File Access Methods

• Sequential access
  • E.g., fgetc()
• Directed access
  • E.g., lseek(), seek()
• Indexed access

File System Organization

• Partitions(minidisk, volumes)
  • Virtual disk
• Directory
  • Poerations on directory
    • Search for a file
    • Create a file
    • Delete a file
    • List a directory
    • Rename a file
    • Traverse the file system

Directory Structure

• Logical directory structure
  • Flat (single-level) directory structure
  • 2-level directory structure
  • Hierarchical (tree-structure) directory structure
  • Acyclic graph directory structure
  • General graph directory structure

Flat Directory Structure

• Single-level directory structure
• Issues
  • File naming
  • File protection
  • File management

2-Level Directory Structure

• Strcture
  • MFD(Master File Directory)
  • UFE(User File Directory)
• Problems
  • Unable to create sub-dirctory
    • File nameing issue

Hierarchical Directory Structure

• Tree form
• Terminologies
  • Home directory, Current directory
  • Absolute pathname, Relative pathname

Acyclic Graph Directory Structure

• Hierarchical directory structure extension
• Directory can contain Shared directory, Shared file
• Link
  • E.g., Symbolick link in Unix

General Graph Directory Sturcture

• Problem
  • Infinite loop

File Protection

• Read(R)
• Write(W)
• Execute(X)
• Append(A)

File Protection Mechanism

1. Password
2. Access Matrix

Access Matrix

• Specify access between domain and object
• Terminologies
  • Object
    • file, device(HW/SW objects)
  • Domain(protection domain)
    • User, Process
  • Access right
    • <object-name, rights-set>
• Implementation
  • Global table
  • Access list
  • Capabilty list
  • Lock-key mechanism

Global Table

• Simple
• Problem
  • Lage table size

Access List

• Express the columns of the access matrix as a list
• UNIX
  • rwx(Owner) rwx(Group) rwx(Universe)

Capability List

• Express the row of the access matrix as a list

Lock-key Mechanism

• Access list + Capability list
• Object has Lock, Domain has Key
  • Lock/key: unique bit patterns

File System Implementation

• Allocation methods
• Free space management

Allocation Methods

• Continuous allocation
• Discontinuous allocation
  • Linked allocation
  • Indexed allocation

Free Space Management

• Bit vector
• Linked list
• Grouping
• Counting

---

Reference

File System