File system

Unit – 6
Chapter 1

File System - OS by JJ @CSE, HKBKCE 1

 File-System Interface

• File Concept
• Access Methods
• Directory Structure
• File-System Mounting
• File Sharing
• Protection

File System - OS by JJ @CSE, HKBKCE 2

 Objectives
• To explain the function of file systems
• To describe the interfaces to file systems
• To discuss file-system design tradeoffs,
including access methods, file sharing,
file locking, and directory structures
• To explore file-system protection

File System - OS by JJ @CSE, HKBKCE 3

 File Concept
• The OS abstracts from the physical properties
of its storage devices to define a logical
storage unit, the file.
• Types:
– Data
• numeric
• character
• binary
– Program

File System - OS by JJ @CSE, HKBKCE 4

• Text file – seq of characters organized into
lines
• Source file – seq of subroutines & functions
each of which is further organized as
declarations followed by executable
statements
• Object file – seq of bytes organized into blocks
understandable by the system’s linker
• Executable file – series of code sections that
the loader can bring into memory and execute

File System - OS by JJ @CSE, HKBKCE 5

File Attributes
• Name – only information kept in human-readable form
• Identifier – unique tag (number) identifies file within file
system
• Type – needed for systems that support different types
• Location – pointer to file location on device
• Size – current file size
• Protection – controls who can do reading, writing, executing
• Time, date, and user identification – data for protection,
security, and usage monitoring
• Information about files are kept in the directory structure,
which is maintained on the disk

File System - OS by JJ @CSE, HKBKCE 6

File Operations
File is an abstract data type and has the following Sys
Calls
• Create (2step: space in, entry to directory structure)
• Write (write pointer to location of the file)
• Read (read & current file position pointers)
• Reposition within file (file seek)
• Delete (releasing the file space from directory)
• Truncate (file space released but attributes are kept)
• Open(Fi) – search the directory structure on disk for
entry Fi, and move the content of entry to memory
• Close (Fi) – move the content of entry Fi in memory
to directory structure on disk

File System - OS by JJ @CSE, HKBKCE 7

Open Files (of open file table)
• Several pieces of data are needed to
manage open files:
– File pointer: pointer to last read/write
location, per process that has the file open
– File-open count: counter of number of times a
file is open – to allow removal of data from
open-file table when last processes closes it
– Disk location of the file: cache of data access
information
– Access rights: per-process access mode
information
File System - OS by JJ @CSE, HKBKCE 8
Open File Locking
• Provided by some operating systems and file
systems
• Mediates access to a file
• Mandatory or advisory:
– Mandatory – access is denied depending on locks
held and requested
– Advisory – processes can find status of locks and
decide what to do

File System - OS by JJ @CSE, HKBKCE 9

File Types – Name, Extension

File System - OS by JJ @CSE, HKBKCE 10

 Access Methods
• Sequential Access
read next
write next
reset
no read after last write
(rewrite)
• Direct Access
read n
write n
position to n
read next
write next
rewrite n
n = relative block number
File System - OS by JJ @CSE, HKBKCE 11
Sequential-access File

File System - OS by JJ @CSE, HKBKCE 12

Simulation of Sequential Access on a Direct-access File

File System - OS by JJ @CSE, HKBKCE 13

Example of Index and Relative Files

File System - OS by JJ @CSE, HKBKCE 14

 Directory Structure
• A collection of nodes containing information about all files

Directory

Files
F1 F2 F4
F3
Fn

Both the directory structure and the files reside on disk

Backups of these two structures are kept on tapes

File System - OS by JJ @CSE, HKBKCE 15

A Typical File-system Organization

File System - OS by JJ @CSE, HKBKCE 16

Operations Performed on Directory
• Search for a file
• Create a file
• Delete a file
• List a directory
• Rename a file
• Traverse the file system

File System - OS by JJ @CSE, HKBKCE 17

Organize the Directory (Logically) to Obtain

• Efficiency – locating a file quickly

• Naming – convenient to users
– Two users can have same name for
different files
– The same file can have several different
names
• Grouping – logical grouping of files by
properties, (e.g., all Java programs, all
games, …)

File System - OS by JJ @CSE, HKBKCE 18

 Single-Level Directory
• A single directory for all users

Naming problem

Grouping problem

File System - OS by JJ @CSE, HKBKCE 19

 Two-Level Directory
• Separate directory for each user

n Path name using User File Directory (UFD) thru Master FD

n Can have the same file name for different user
n No grouping capability
n For searching a file – User name & file name (search path)

File System - OS by JJ @CSE, HKBKCE 20

Tree-Structured Directories

File System - OS by JJ @CSE, HKBKCE 21

Tree-Structured Directories (Cont)
• Efficient searching
• Grouping Capability
• Current directory (working directory)
– cd /spell/mail/prog
– type list

File System - OS by JJ @CSE, HKBKCE 22

Tree-Structured Directories (Cont)
• Absolute or relative path name
• Creating a new file is done in current directory
• Delete a file
rm <file-name>
• Creating a new subdirectory is done in current directory
mkdir <dir-name>
Example: if in current directory /mail
mkdir count

mail

prog copy prt exp count

Deleting “mail” deleting the entire subtree rooted by “mail”

File System - OS by JJ @CSE, HKBKCE 23

 Acyclic-Graph Directories
• Have shared subdirectories and files

File System - OS by JJ @CSE, HKBKCE 24

Acyclic-Graph Directories (Cont.)
• Two different names (aliasing)
• If dict deletes list dangling pointer
Solutions:
– Backpointers, so we can delete all pointers
Variable size records a problem
– Backpointers using a daisy chain organization
– Entry-hold-count solution
• New directory entry type
– Link – another name (pointer) to an existing file
– Resolve the link – follow pointer to locate the file

File System - OS by JJ @CSE, HKBKCE 25

General Graph Directory

File System - OS by JJ @CSE, HKBKCE 26

General Graph Directory (Cont.)
• How do we guarantee no cycles?
– Allow only links to file not subdirectories
– Garbage collection
– Every time a new link is added use a cycle
detection
algorithm to determine whether it is OK

File System - OS by JJ @CSE, HKBKCE 27

 File System Mounting
• A file system must be mounted
before it can be accessed
• Mount procedure is straight forward
– OS is given a name of the device and
mount point (the location within the file
structure where the file system is to be
attached)
• Mount point is an empty directory

File System - OS by JJ @CSE, HKBKCE 28

(a) Existing. (b) Unmounted Partition

File System - OS by JJ @CSE, HKBKCE 29

Mount Point

File System - OS by JJ @CSE, HKBKCE 30

 File Sharing
• Sharing of files on multi-user systems is desirable
• Sharing may be done through a protection scheme
• On distributed systems, files may be shared across a
network
• Network File System (NFS) is a common distributed
file-sharing method
Multiple Users
• User IDs identify users, allowing permissions and
protections to be per-user
• Group IDs allow users to be in groups, permitting
group access rights
File System - OS by JJ @CSE, HKBKCE 31
Remote File Systems
• Uses networking to allow file system access between
systems
– Manually via programs like FTP
– Automatically, seamlessly using distributed file
systems
– Semi automatically via the world wide web
Client-server: model allows clients to mount remote file
systems from servers
– Client and user-on-client identification is insecure or
complicated (ip Spoofing)
– NFS is standard UNIX client-server file sharing protocol
– CIFS is standard Windows protocol
– Standard operating system file calls are translated into
remote calls
File System - OS by JJ @CSE, HKBKCE 32
Distributed Information Systems:
• distributed naming services such as LDAP, DNS, NIS,
Active Directory implement unified access to
information needed for remote computing
Failure Modes :
• Remote file systems add new failure modes, due to
network failure, server failure
• Recovery from failure can involve state information
about status of each remote request
• Stateless protocols such as NFS include all
information in each request, allowing easy recovery
but less security
File System - OS by JJ @CSE, HKBKCE 33
Consistency semantics: specify how multiple users are to
access a shared file simultaneously
• Similar to process synchronization algorithms
• Tend to be less complex due to disk I/O and network
latency (for remote file systems
– Andrew File System (AFS) implemented complex
remote file sharing semantics
– Unix file system (UFS) implements:
• Writes to an open file visible immediately to other
users of the same open file
• Sharing file pointer to allow multiple users to read
and write concurrently
– AFS has session semantics
• Writes only visible to sessions starting after the file
is closed
File System - OS by JJ @CSE, HKBKCE 34
 Protection
• File owner/creator should be able to control:
– what can be done (physical damage)
– by whom (protection)
• Types of access
– Read
– Write
– Execute
– Append
– Delete
– List – the name & attributes of the file

File System - OS by JJ @CSE, HKBKCE 35

Access Control
• Mode of access: read, write, execute
• Three classes of users RWX
a) owner access 7 111
b) group access 6 110
c) public access 1 001
• Ask manager to create a group (unique name), say G, and
add some users to the group.
• For a particular file (say game) or subdirectory, define an
appropriate access.
• Access control list (ACL) specifies user name and type of
access allowed for each user

File System - OS by JJ @CSE, HKBKCE 36

Windows XP Access-control List Management

File System - OS by JJ @CSE, HKBKCE 37

File System Implementation
Chapter 2

File System - OS by JJ @CSE, HKBKCE 38

File System Implementation
• File-System Structure
• File-System Implementation
• Directory Implementation
• Allocation Methods
• Free-Space Management

File System - OS by JJ @CSE, HKBKCE 39

File-System Structure
To improve I/O efficiency, I/O transfers b/w memory & disk
are performed in units of blocks.
block has one or more sector
sectors vary from 32 to 4096 bytes(default 512)
• File structure
– Logical storage unit
– Collection of related information
• File system resides on secondary storage (disks)
• File system organized into layers
• File control block – storage structure consisting of
information about a file

File System - OS by JJ @CSE, HKBKCE 40

Layered File System

File System - OS by JJ @CSE, HKBKCE 41

A Typical File Control Block

File System - OS by JJ @CSE, HKBKCE 42

File System Implementation
Overview
• On disk the file system may contain info of
– Boot control block
– Volume control block (no. of blocks /partition, size
of the block, free block counter & pointers)
– Master file table (file names and associated inode nos)
Created file -> it must be opened first -> open () call
passes file name into file system -> open() system
call searches system wide open file table -> if it is
used by other ->per process open file table entry

File System - OS by JJ @CSE, HKBKCE 43

• System wide open file table
– Contains a copy of the FCB of each open file
• Per process open file table
– Contains pointer to the appropriate entry in the
system wide open file table
– When a process closes the file the entry is
removed

File System - OS by JJ @CSE, HKBKCE 44

In-Memory File System Structures

File System - OS by JJ @CSE, HKBKCE 45

Virtual File Systems
• Virtual File Systems (VFS) provide an object-
oriented way of implementing file systems.
• VFS allows the same system call interface (the API)
to be used for different types of file systems.
• The API is to the VFS interface, rather than any
specific type of file system.
• VFS functions
– Abstraction on interfaces
– Vnode: vfs based file representation structure which
contains a numerical designator for network wide file.

File System - OS by JJ @CSE, HKBKCE 46

Schematic View of Virtual File System

File System - OS by JJ @CSE, HKBKCE 47

Directory Implementation
• Linear list of file names with pointer to
the data blocks.
– simple to program
– time-consuming to execute

• Hash Table – linear list with hash data

structure.
– decreases directory search time
– collisions – situations where two file names
hash to the same location
– fixed size

File System - OS by JJ @CSE, HKBKCE 48

Allocation Methods
• An allocation method refers to how disk
blocks are allocated for files:

• Contiguous allocation

• Linked allocation

• Indexed allocation

File System - OS by JJ @CSE, HKBKCE 49

Contiguous Allocation
• Each file occupies a set of contiguous blocks
on the disk
• Simple – only starting location (block #) and
length (number of blocks) are required
• Random access
• Files cannot grow(no dynamic allocation)
• External fragmentation problem solved thru
file compaction

File System - OS by JJ @CSE, HKBKCE 50

Contiguous Allocation of Disk Space

File System - OS by JJ @CSE, HKBKCE 51

• Extent-Based Systems
– Many newer file systems (I.e. Veritas File System)
use a modified contiguous allocation scheme
– Extent-based file systems allocate disk blocks in
extents
– An extent is a contiguous block of disks
– Extents are allocated for file allocation
– A file consists of one or more extents.

File System - OS by JJ @CSE, HKBKCE 52

Linked Allocation
• Each file is a linked list of disk blocks: blocks may be
scattered anywhere on the disk.
• Simple – need only starting address
• Free-space management system – no waste of space
• No random access
• File-allocation table (FAT)
• Space required for pointers. To solve use clusters
• Solves external fragmentation

File System - OS by JJ @CSE, HKBKCE 53

Linked Allocation

File System - OS by JJ @CSE, HKBKCE 54

File-Allocation Table

File System - OS by JJ @CSE, HKBKCE 55

Indexed Allocation
• Brings all pointers together into the index
block.
• Random access
• Dynamic access without external
fragmentation, but have overhead
index table
of index block.
• Mapping from logical to physical in a file of
maximum size of 256K words and block size
of 512 words. We need only 1 block for index
table
File System - OS by JJ @CSE, HKBKCE 56
Example of Indexed Allocation

File System - OS by JJ @CSE, HKBKCE 57

Indexed Allocation – Mapping (Cont.)

outer-index

index table file

File System - OS by JJ @CSE, HKBKCE 58

Combined Scheme: UNIX (4K bytes per block)

File System - OS by JJ @CSE, HKBKCE 59

Free-Space Management
• Bit vector (n blocks)
0 1 2 n-1
…


0 block[i] free
bit[i] =
1 block[i] occupied

Block number calculation

(number of bits per word) *

(number of 0-value words) +
offset of first 1 bit

File System - OS by JJ @CSE, HKBKCE 60

• Bit map requires extra space
– Example:
block size = 212 bytes
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K bytes)
• Easy to get contiguous files
• Linked list (free list)
– Cannot get contiguous space easily
– No waste of space
• Grouping - collect free addresses
• Counting –
File System - OS by JJ @CSE, HKBKCE 61
• Need to protect:
– Pointer to free list
– Bit map
• Must be kept on disk
• Copy in memory and disk may differ
• Cannot allow for block[i] to have a situation where
bit[i] = 1 in memory and bit[i] = 0 on disk
– Solution:
• Set bit[i] = 1 in disk
• Allocate block[i]
• Set bit[i] = 1 in memory

File System - OS by JJ @CSE, HKBKCE 62