Operating System

File-System Interface
Primary Roles of the OS (file system)

2
 Files
● A file is a collection of data with some
properties
● contents, size, owner, last read/write time,
protection …
● Files may also have types
● understood by file system
4 device, directory, symbolic link
● understood by other parts of OS or by
runtime libraries
4 executable, dll, source code, object code,
text file, …
 Files
● Type can be encoded in the file’s name
or contents
● windows encodes type in name
4 .com, .exe, .bat, .dll, .jpg, .mov,
.mp3, …
● old Mac OS stored the name of the
creating program along with the file
● unix has a smattering of both
4 in content via magic numbers or
initial characters (e.g., #!)
 File Structure
● Simple record structure
● Lines
● Fixed length
● Variable length
● Complex Structures
● Formatted document
● Re-locatable load file
● Can simulate last two with first method by inserting
appropriate control characters
● Who decides:
● Operating system
● Program
 User vs. System View of a File

● User level: individual files

● System call level: collection of bytes
● Operating system level:
● A block is a logical transfer unit
4 Even for getc() and putc()
4 4 Kbytes under UNIX
● A sector is a physical transfer unit
4 4-Kbyte sectors on disks
● File: a named collection of blocks
 Path Name Translation
● Let’s say you want to open “/one/two/three”
● What does the file system do?
● Open directory “/” (well known, can always find)
● Search for the entry “one”, get location of “one” (in dir entry)
● Open directory “one”, search for “two”, get location of “two”
● Open directory “two”, search for “three”, get location of “three”
● Open file “three”
● Systems spend a lot of time walking directory paths
● This is why open is separate from read/write
● OS will cache prefix lookups for performance
4 /a/b, /a/bb, /a/bbb, etc., all share “/a” prefix
 File System Components

● Storage management organizes storage

blocks into files
● Naming provides file names and
directories to users, instead of tracks and
sector numbers (e.g. Takashita)
● Protection keeps information secure from
other users
● Reliability protects information loss due
to system crashes
 File System Layout
How do file systems use the disk to store files?
● File systems define a block size (e.g., 4KB)
● Disk space is allocated in granularity of blocks
● A “Master Block” determines location of root directory
● Always at a well-known disk location
● Often replicated across disk for reliability
● A free map determines which blocks are free, allocated
● Usually a bitmap, one bit per block on the disk
● Also stored on disk, cached in memory for performance
● Remaining disk blocks used to store files (and dirs)
● There are many ways to do this
 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 Operations

● File is an abstract data type

● Create
● Write
● Read
● Reposition within file
● Delete
● Truncate
● 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
 Basic operations

Unix Windows
● create(name) ● CreateFile(name, CREATE)

● open(name, mode) ● CreateFile(name, OPEN)

● read(fd, buf, len) ● ReadFile(handle, …)

● write(fd, buf, len) ● WriteFile(handle, …)

● sync(fd) ● FlushFileBuffers(handle, …)

● seek(fd, pos) ● SetFilePointer(handle, …)

● close(fd) ● CloseHandle(handle, …)

● unlink(name) ● DeleteFile(name)

● rename(old, new) ● CopyFile(name)

● MoveFile(name)
 Open Files

● 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 Types – Name, Extension
 File access methods
● Some file systems provide different access methods that specify ways
the application will access data
● sequential access
4 read bytes one at a time, in order
● direct access
4 random access given a block/byte #
● record access
4 file is array of fixed- or variable-sized records
● indexed access
4 FS contains an index to a particular field of each record in a file
4 apps can find a file based on value in that record (similar to DB)
● Why do we care about distinguishing sequential from direct access?
● what might the FS do differently in these cases?
 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
 Directories

● Directories provide:
● a way for users to organize their files
● a convenient file name space for both users and FS’s
● Most file systems support multi-level directories
● naming hierarchies (/, /usr, /usr/local, /usr/local/bin, …)
● Most file systems support the notion of current directory
● absolute names: fully-qualified starting from root of FS
bash$ cd /usr/local
● relative names: specified with respect to current directory
bash$ cd /usr/local (absolute)
bash$ cd bin (relative, equivalent to cd /usr/local/bin)
 Directory internals

● A directory is typically just a file that happens to

contain special metadata
● directory = list of (name of file, file attributes)
● attributes include such things as:
4 size, protection, location on disk, creation time,
access time, …
● the directory list is usually unordered (effectively
random)
4 when you type “ls”, the “ls” command sorts the
results for you
 Directory Structure
● A collection of nodes containing information about all files

Directory

Files F F F
F 4
1 2
3 F
n

Both the directory structure and the files reside on disk

Backups of these two structures are kept on tapes
 Operations Performed on Directory

● Search for a file

● Create a file
● Delete a file
● List a directory
● Rename a file
● Traverse the file system
 Disk Structure
● Disk can be subdivided into partitions
● Entity containing file system known as a
volume
● Each volume containing file system also
tracks that file system’s info in device
directory or volume table of contents
● As well as general-purpose file systems there
are many special-purpose file systems,
frequently all within the same operating
system or computer
Tree-Structured Directories
 Acyclic-Graph Directories
● Have shared subdirectories and files
General Graph Directory
 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
 File Sharing – 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
 Process 1 Process 2 (child) Process 3
channel channel channel
table table table

open file file offset file offset

table

memory-resident
i-node table
disk

file buffer cache

 File Sharing – 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
● Server can serve multiple clients
● Client and user-on-client identification is insecure or
complicated
● NFS is standard UNIX client-server file sharing protocol
● CIFS is standard Windows protocol
● Standard operating system file calls are translated into
remote calls
 Protection

● File owner/creator should be able to control:

● what can be done
● by whom

● Types of access
● Read
● Write
● Execute
● Append
● Delete
● List
 Access Lists and Groups

● Mode of access: read, write, execute

● Three classes of users
RWX
a) owner access 7 ⇒ 1 1 1
RWX
b) group access 6 ⇒ 110
RWX
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.
 ACLs vs. Capabilities
● Capabilities are easy to transfer
● they are like keys: can hand them off
● they make sharing easy
● ACLs are easier to manage
● object-centric, easy to grant and revoke
4 to revoke capability, need to keep track of principals that have it
4 hard to do, given that principals can hand off capabilities
● ACLs grow large when object is heavily shared
● can simplify by using “groups”
4 put users in groups, put groups in ACLs
4 you are all in the “VMware powerusers” group on Win2K
● additional benefit
4 change group membership, affects ALL objects that have this group
in its ACL
A Typical File Control Block
 Disk Allocation Policies

● Contiguous allocation
● Link-list allocation
● Segment-based allocation
● Indexed allocation
● Multi-level indexed allocation
● Hashed allocation
 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.

● Wasteful of space (dynamic storage-allocation problem).

● Files cannot grow.

 Contiguous Allocation of Disk Space

Operating
System
Concepts
 Linked Allocation
● Each file is a linked list of disk blocks: blocks may be
scattered anywhere on the disk.

block
pointer
=

File-allocation table (FAT) –

disk-space allocation used by
MS-DOS and OS/2.
Linked Allocation
 Indexed Allocation

● Brings all pointers together into the index block.

● Logical view.

index
table
Example of Indexed Allocation
 Indexed Allocation (Cont.)

● Need index table

● Random access
● Dynamic access without external
fragmentation, but have overhead 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.
 The original Unix file system

● Dennis Ritchie and Ken Thompson, Bell Labs, 1969

● “UNIX rose from the ashes of a multi-organizational
effort in the early 1960s to develop a dependable
timesharing operating system” – Multics
● Designed for a “workgroup” sharing a single system
● Did its job exceedingly well
● Although it has been stretched in many directions
and made ugly in the process
● A wonderful study in engineering tradeoffs
(Old) Unix disks are divided into five parts
…
● Boot block
● can boot the system by loading from this block
● Superblock
● specifies boundaries of next 3 areas, and contains head of freelists of
inodes and file blocks
● i-node area
● contains descriptors (i-nodes) for each file on the disk; all i-nodes are
the same size; head of freelist is in the superblock
● File contents area
● fixed-size blocks; head of freelist is in the superblock
● Swap area
● holds processes that have been swapped out of memory
 i-node format
● User number
● Group number
● Protection bits
● Times (file last read, file last written, inode last written)
● File code: specifies if the i-node represents a directory, an ordinary user
file, or a “special file” (typically an I/O device)
● Size: length of file in bytes
● Block list: locates contents of file (in the file contents area)
● more on this soon!
● Link count: number of directories referencing this i-node
 The tree (directory, hierarchical) file
system
● A directory is a flat file of fixed-size entries
● Each entry consists of an i-node number and a file name

i-node number File name

152 .
18 ..
216 my_file
4 another_file
93 oh_my_god
144 a_directory

• It’s as simple as that!

44
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition 10.44