Official (Closed), Non-Sensitive

ET0023 Operating Systems Chapter 11:

File Systems

In this chapter, you will be learning about File Systems.

1. Learning Objectives
In this lesson, you will learn the following:

• File Systems

• Storing Files & Implementing Directories

• Disk Management

• File System Consistency & Log File System

2. The Big Picture

Storing Information

• Applications can store it in the process

address space

Why is it a bad idea?

• Size is limited to size of virtual address space

• The data is lost when the application

terminates

• Multiple processes might want to access the

same data

There are 3 criteria for long-term information

storage in file systems:
 Official (Closed), Non-Sensitive

1. Should be able to store very large amount of information

2. Information must survive the processes using it

3. Should provide concurrent access to multiple processes

Solution

• Store information on disks in units called files

• Files are persistent, and only the owner can explicitly delete it

• Files are managed by the OS

• File Systems

o How the OS manages files!

3. Properties of a File
3.1 What Does A File Have?
So, what does a file have? A file must have its name, to identify it in the file system.

And inside a file, it has its data. A file also comes with its attributes, including file size, owner,
creation date and so on.

3.2 Properties Of a File

 Official (Closed), Non-Sensitive

• File Operations - What you can do with a file

• File Naming - Uniquely identify the file

• File Structure - How the OS sees the data inside

• File Access Mechanisms - Sequential access, random access

• File Attributes - Information about the file

• File Types - Different types of use

3.3 Example Of File Properties

• Type of file - Text, executable, other binary, etc...

• Location - Where the file is located in the hard drive

• Size - The size of the file

 Official (Closed), Non-Sensitive

• Created - When the file was created

• Modified - When the file was last modified

• Accessed - When the file was last accessed

• Attributes - Whether the file is a Read-only or Hidden

3.3.1. File Operations

• Create - The file is created with no data

• Delete - File is no longer needed, is deleted to free up disk space

• Open - Before using a file, a process must open it

• Close - When a process no longer needs to use the file, the file is closed

• Read - Data is read from the file

• Write - Data is written to the file

• Append - Data is added to the end of the file

• Seek - Positions the file pointer to a specific place in the file

• Get attributes - Read the file attributes

• Set attributes - Change the attributes of the file

• Rename - Change the name of the file

3.3.2. File Naming

• Files abstract information stored on disk

o You do not need to remember block, sector, ...

o We have human readable names

• How does it work?

o Process creates a file, and gives it a name

 Official (Closed), Non-Sensitive

o Other processes can access the file by that name

• Naming conventions are OS dependent

o Usually names as long as 255 characters is allowed

o Digits and special characters are sometimes allowed

o MS-DOS and Windows are not case sensitive

o UNIX/Linux family is case sensitive

3.3.3. File Extensions

• Name divided into 2 parts, second part is the extension

• On UNIX, extensions are not enforced by OS

o However C compiler might insist on its extensions

o These extensions are very useful for C

• Windows attaches meaning to extensions

o Tries to associate applications to file extensions

3.3.4. File Structures

Now lets look at file structures.
We have three types of file
structures. Firstly, we have byte
sequence, in this structure, files
are just an unstructured sequence
of bytes.

Next, we have the record

sequence, in this model, a file is a
sequence of fixed-length records.
This is one record and each record
will have its own internal structure.
 Official (Closed), Non-Sensitive

Lastly, we have a tree of records, in this organization, a file consists of a tree of records, not
necessarily all of the same length.

Byte Sequence

This sequence is just an unstructured sequence of bytes. In effect, the operaing system does not
know or care what is in the file. All it sees are bytes. Any meaning must be imposed by user-level
programs.

Both UNIX and Windows 98 use this approach.

e.g. IBM’s indexed sequenial access method (ISAM)

Record Sequence

In this model, a file is a sequence of fixed-length records, each with some internal structure.
Central to the idea of a file being a sequence of records, is the idea that the read operation
returns one record and the write operation overwrites or appends one record.

As a historical note, when the 80-column punched card was king many (mainframe) operating
systems based their file systems on files consisting of 80-character records, in effect, card images.

Tree

In this organization, a file consists of a tree of records, not necessarily all of the same length, each
containing a key field in a fixed position in the record. The tree is sorted on the key field, to allow
rapid searching for a particular key.

3.3.5. File Access Mechanisms

When a file is used, the stored information in the file must be accessed and read into the memory
of a computer system. Various mechanisms are provided to access a file from the operating
system.

• Sequential access

• Direct/Random access

• Indexed sequential access

Sequential access
 Official (Closed), Non-Sensitive

A sequential access is that in which the records are accessed in some sequence, i.e., the
information in the file is processed in order, one record after the other. This access method is the
most primitive one. Example: Compilers usually access files in this fashion.

Direct/Random access

Random access file organization provides, accessing the records directly.

Each record has its own address on the file with by the help of which it can be directly accessed
for reading or writing.

The records need not be in any sequence within the file and they need not be in adjacent
locations on the storage medium.

Indexed sequential access

This mechanism is built up on base of sequential access.

An index is created for each file which contains pointers to various blocks.

Index is searched sequentially and its pointer is used to access the file directly.

3.3.6. File Attributes

• File-specific info maintained by the OS

o File size, modification date, creation time, etc.

o Varies a lot across different OS's

• Some examples

o Name

o Only information kept in human

o Readable form – Identifier

o Unique tag (number) identifies file within file system

o Type – needed for systems that support different types

 Official (Closed), Non-Sensitive

o Location – pointer to file location on device–Size

o Current file size – Protection

o Controls who can do reading, writing, executing

o Time, date, and user identification

o Data for protection, security, and usage monitoring

4. Users & Access Rights

4.1 File Protection
• File owner/creator should be able to control

o What can be done

o By whom

• Types of access

o Read

o Write

o Execute

o Append

o Delete

o List

4.2 Categories of Users

• Individual user

o Log in establishes a user-id

o Might be just local on the computer or could be through interaction with a network
service
 Official (Closed), Non-Sensitive

• Groups to which the user belongs

o Again could just be automatic or could involve talking to a service that might assign,
say, a temporary cryptographic key

4.3 Linux Access Rights

Basically, when it comes to the Linux Access Rights, we have a read, write, and execute for each
file.

And then, we have three classes of users, owner access, group access, and public access.

Finally, the numbers here indicate the access permission for each class of user.

5. File System & Directories

5.1 File System on Disk
• Could use entire disk space for a FS, but

o A system could have multiple File Systems

o Want to use some disk space for swap space

• Disk divided into partitions, slices or mini- disks

o Chunk of storage that holds a FS is a volume

 Official (Closed), Non-Sensitive

• Directory structure maintains info of all files in the volume (name, location, size, type,
…)

5.2 Directories
• Directories/folders keep track of files

o Is a symbol table that translates file names to directory entries

o Usually are themselves files

• Directory operaions to be supported include:

o Search a file, Create a file, Delete a file, List directory, Rename a file, Traversing
the FS

• 3 types of directory systems

o Single-level directory

o Two-level directory

o Hierarchical directory

5.2.1 Single Level Directory

 Official (Closed), Non-Sensitive

• One directory for all files in the volume (root)

• Used in early PCs (even in first supercomputers)

• Pros

o Simplicity, Able to quickly locate files

• Cons

o Inconvenient naming (uniqueness)

5.2.2 Two-Level Directory

Each user has a separate directory

Solves name collision, but bad if a user(s) has many files

May not allow file sharing or access

File names only need to be unique within a given user's directory.

A master file directory is used to keep track of each users directory, and must be maintained
when users are added to or removed from the system.

A separate directory is generally needed for system (executable) files.

Systems may or may not allow users to access other directories besides their own

• If access to other directories is allowed, then provision must be made to specify the
directory being accessed.

• If access is denied, then special consideration must be made for users to run programs
 Official (Closed), Non-Sensitive

located in system directories. A search path is the list of directories in which to search for
executable programs, and can be set uniquely for each user.

5.2.3 Tree-Structured Directories

• Directory created as a tree of arbitrary height.

o Contains files and sub-directories

o A bit in directory entry differentiates files from sub-directories

• Pros

o Very flexible, allows users to group files

• Cons

o Most complicated of all

An obvious extension to the two-tiered directory structure, and the one with which we are all
most familiar.

Each user/process has the concept of a current directory from which all (relative) searches take
place.
 Official (Closed), Non-Sensitive

Files may be accessed using either absolute pathnames (relative to the root of the tree) or
relative path names (relative to the current directory).

Directories are stored the same as any other file in the system, except there is a bit that identifies
them as directories, and they have some special structure that the OS understands.

One question for consideration is whether or not to allow the removal of directories that are not
empty - Windows requires that directories be emptied first, and UNIX provides an option for
deleting entire sub-trees.

5.2.4 Acyclic Graph Directories

Path Names
• To access a file, the user should either

o Go to the directory where file resides, or

o Specify the path where the file is

• Path names are either absolute or relaive

o Absolute: path of file from the root directory

o Relative: path from the current working directory

• Most OSes have two special entries in each directory

o “.” for current directory, and

o “..” for parent

 Official (Closed), Non-Sensitive

Path Names :

Here are two examples for the path of a file. First, let's look at the absolute path for file 1. The first
/ indicates the root directory.

Therefore, the path of file 1 is / dict for the root directory, / all, then / file 1.

Similarly, you can point out the absolute path for file 3. It is, / spell, / words, / w7 then / file 3.

5.3 Implementing Directories

When a file is opened, OS uses path name to find dir

 Official (Closed), Non-Sensitive

Directory also has attributes of each file

Directory has information about the file’s disk blocks, whole file (contiguous), first block (linked-
list) or I-node

Directory: map ASCII file name to file attributes & location

2 options: entries have all attributes, or point to file I-node

6. File System Layout

6.1 File System Layout
Now lets talk about file system layout. The file system is stored on a disk, the disk is divided to one
or more partitions.

So, you can have as many extended partitions as you like, but you can only have a maximum of 4
partitions for each disk.

This diagram shows the file system layout on the disk.

We have a MBR, we have a partition table, and inside each partition we have, boot block, super
block ,free space management, I-nodes, root directory, files and directories.

6.2 Partition Contents

• What do we find inside every partition
 Official (Closed), Non-Sensitive

o Boot Block

o Superblock

o Information about free blocks

o nodes

o Root directory

o Remainder of disk space

• Boot block

o Instructions to load the operating system are stored inside here

• Superblock

o Contains key parameters about the file system, such as

 A magic number to identify the file system type

 The total number of blocks in the file

• I-nodes

o Is an array of data structures, one per file, telling all about the file

• Root directory

o Contains the top of the file system tree

• Remainder of disk space

o Contains all the other disk directories and files

6.3 Master Boot Record (MBR)

Sector 0 of the disk is called the MBR (Master Boot Record) and it is used to boot the computer

The end of the MBR contains the partition table

This table gives the starting and ending addresses of each partition
 Official (Closed), Non-Sensitive

One of the partitions in the table is marked as active

When the computer is booted, the BIOS reads in and executes the MBR

The first thing the MBR program does is locate the active partition, read in its first block, called
the boot block, and execute it.

The program in the boot block loads the operating system contained in that partition.

6.4 How to implement shared files and sub directories?

When the same files need to be accessed in more than one place in the directory structure (e.g.
because they are being shared by more than one user/process), it can be useful to provide an
acyclic-graph structure.

Hard Link
A hard link (usually just called a link) involves multiple directory entries that both refer to the
same file. Hard links are only valid for ordinary files in the same file system.

Hard links require a reference count, or link count for each file, keeping track of how many
directory entries are currently referring to this file. Whenever one of the references is removed
the link count is reduced, and when it reaches zero, the disk space can be reclaimed.

Symbolic Link (also named as "soft link")

A symbolic link, involves a special file, containing information about where to find the linked file.

Symbolic links may be used to link directories and/or files in other file systems, as well as ordinary
files in the current file system.

For symbolic links there is some question as to what to do with the symbolic links when the
original file is moved or deleted.

One option is to find all the symbolic links and adjust them also.

Another is to leave the symbolic links dangling and discover that they are no longer valid the next
time they are used.

Note: Windows only supports symbolic links, termed shortcuts.

 Official (Closed), Non-Sensitive

Issues?
Two different names (aliasing)

For soft links if the original file is deleted then it becomes a dangling pointer

If dict deletes count --> dangling pointer

• Keep back-pointers of links for each file

• Leave the link, and delete only when accessed later

• Keep reference count of each file

7. File System Hierarchy

7.1 File System Hierarchy

A typical example of a File System Hierarchy is a Linux System. It is a reverse tree.

 Official (Closed), Non-Sensitive

7.2 Mounted File Systems

Let’s look at Mounted File Systems.

We can mount two file systems, the mounting allows two file systems to be merge into one.

Let’s look at diagram (a), before mounting, files are floppy, therefore, files x and y are inaccessible.

Now, let’s mount files x and y under b.

Now see diagram (b), after mounting, files x and y are now a part of the file hierarchy under b, so it
can now be accessed.

8. Storing Files
Files can be allocated in different ways; contiguous allocation, linked structure, indexed structure.

Contiguous Allocation - All bytes together, in order

Linked Structure - Each block points to the next block

Indexed Structure - An index block contains pointer to many other blocks

 Official (Closed), Non-Sensitive

We must also ask - which is the best allocation method? For sequential access? Random access?
Large files? Small files? Mixed?

8.1 Contiguous Allocation

Let’s take a look at this diagram. It illustrates the contiguous allocation of disk space for 7 files,
from File A to File G.

In this allocation, it is required for all blocks of file to be kept together contiguously.

Let’s take file A as an example, since file A needs 4 blocks, the 4 blocks will be contiguously
allocated in the disk.

The performance for this allocation is very fast, because reading successive blocks of the same
file, generally requires no movement of the disk heads.

This contiguous allocation also has many disadvantages, for example if two files has been
removed from the disk, like file D and File F has been removed in this example, then we will have
free blocks.

These free blocks can then be reassigned to other files, however, if the file is larger than the
available free blocks, then a problem could occur in the file system.

Storage allocation involves the same issues discussed earlier for the allocation of contiguous
blocks of memory (first fit, best fit, fragmentation problems, etc)
 Official (Closed), Non-Sensitive

The distinction is that the high time penalty required for moving the disk heads from spot to spot
may now justify the benefits of keeping files contiguously when possible.

Even file systems that do not by default store files contiguously can benefit from certain utilities
that compact the disk and make all files contiguous in the process.

Problems can arise when files grow, or if the exact size of a file is unknown at
creation time
• Over-estimation of the file's final size increases external fragmentation and wastes disk
space.

• Under-estimation may require that a file be moved or a process aborted if the file grows
beyond its originally allocated space.

• If a file grows slowly over a long time period and the total final space must be allocated
initially, then a lot of space becomes unusable before the file fills the space.

A variation is to allocate file space in large contiguous chunks, called extents.

When a file outgrows its original extent, then an additional one is allocated - for example, an
extent may be the size of a complete track or even cylinder, aligned on an appropriate track or
cylinder boundary.

The high-performance files system Veritas uses extents to optimize performance.

Advantages of Contiguous Allocation

• Very simple to implement, only the disk address of the first block and the number of blocks
in the file is needed

• Read performance is excellent

Disadvantages of Contiguous Allocation

• In time, disk becomes fragmented, resulting in files and holes

• To store more files, user needs to know size of files and size of holes
 Official (Closed), Non-Sensitive

8.2 Linked List Allocation

• Each file is stored as linked list of blocks

• First word of each block points to next block

o The rest of the block is for data

• Disk files can be stored as linked lists, with the expense of the storage space consumed by
each link (e.g. a block may be 508 bytes instead of 512)

Linked allocation involves no external fragmentation, does not require pre-known file sizes, and
allows files to grow dynamically at any time.

Unfortunately, linked allocation is only efficient for sequential access files, as random access
requires starting at the beginning of the list for each new location access.

Allocating clusters of blocks reduces the space wasted by pointers, at the cost of internal
fragmentation.

Another big problem with linked allocation is reliability if a pointer is lost or damaged. Doubly
linked lists provide some protection, at the cost of additional overhead and wasted space.

Advantages of Linked List Allocation

1. Every block in the disk can be used by a file
 Official (Closed), Non-Sensitive

2. Directory entry only needs to store the disk address of the first block of the file

Disadvantages of Linked List Allocation

• Random access is extremely slow.

• Overhead of using pointers (file space)

8.3 MS-DOS File System

MS-DOS File System is a typical example of a Linked List Allocation method.

It implements this allocation, using a table called, File Allocation Table, also known as FAT.

A FAT table is a separate table that is stored at the beginning of a disk.

For example, File A, starts from Physical block 4, and it is pointed to physical block 7, so in this
table, physical block 4, is pointed to physical block 7.

Similarly, physical block 7, is pointed to physical block 2, so in this table, physical block 7, is
pointed to physical block 2.

The links for File B can also be found by using this method.

Finally, the -1 in the FAT table indicates that it is the end of the file.
 Official (Closed), Non-Sensitive

8.4 File Allocation Table

The pointer word from each disk block is put into a table instead. This table is called a FAT (File
Allocation Table).

Advantages of File Allocation Table

Entire block is available for data

Random access is faster than linked list

Disadvantage of File Allocation Table

Many file seeks unless entire FAT is in memory

For 20 GB disk, 1 KB block size, FAT has 20 million entries

If 4 bytes used per entry ---> 80 MB of main memory required for FS

8.5 Indexed Allocation

Indexed Allocation combines all the indexes for accessing each file into a common block (for that
file), as opposed to spreading them all over the disk or storing them in a FAT table.

Each file is associated with a data structure called an I-node (index node)

The I-node lists the attributes and disk addresses of the file’s blocks

e.g. Block 19 is an indexed block, inside this block, it contains all the index of the user block for
this file

Advantage of Indexed Allocation

I-node table requires less memory than FAT, depends on total number of files

Disadvantage of Indexed Allocation

I-node may limit file size (solution: use indirect blocks)
 Official (Closed), Non-Sensitive

8.6 Unix File System

The first 12 pointers point to the Direct Blocks, if each block is a 4K bytes, then first 48K bytes
are reachable from the inode table

Pointer 13 points to the Single-Indirect Block, so the next 4MB is available from the Single-
Indirect Block

Pointer 14 points to the Double-Indirect Block, so the next 4GB is available from the Double-
Indirect Block

Pointer 15 points to the Triple-Indirect Block, so the next 4TB is available from the Triple-
Indirect Block

Any block can be found with at most 4 disk accesses

 Official (Closed), Non-Sensitive

Multi-Level Index
The first index block contains a set of pointers to secondary index blocks, which in turn contain
pointers to the actual data blocks.

Combined Scheme
This is the scheme used in UNIX inodes, in which the first 12 or so data block pointers are stored
directly in the inode, and then singly, doubly, and triply indirect pointers provide access to more
data blocks as needed.

The advantage of this scheme is that for small files (which many are), the data blocks are readily
accessible (up to 48K with 4K block sizes); files up to about 4144K (using 4K blocks) are
accessible with only a single indirect block (which can be cached), and huge files are still
accessible using a relatively small number of disk accesses (larger in theory than can be addressed
by a 32-bit address, which is why some systems have moved to 64-bit file pointers)

8.7 Original Unix System File Allocation

 Official (Closed), Non-Sensitive

9. Disk Management
9.1 Managing Free Disk Space
There are 2 approaches to keep track of free disk blocks:

A Bitmap or Bit Vector

is a series or collection of bits where each bit corresponds to a disk block. The bit can take two
values: 0 and 1: 0 indicates that the block is allocated and 1 indicates a free block.

Linked List
In this approach, the free disk blocks are linked together i.e. a free block contains a pointer to the
next free block. The block number of the very first disk block is stored at a separate location on
disk and is also cached in memory.
 Official (Closed), Non-Sensitive

9.2 Managing Disk Quotas

Disk space can be restricted by implementing disk quotas which alert a system administrator
before a user consumes too much disk space or a partition becomes full.

Disk quotas can be configured for individual users as well as user groups. This makes it possible to
manage the space allocated for user-specific files (such as email) separately from the space
allocated to the projects a user works on (assuming the projects are given their own groups).

In addition, quotas can be set not just to control the number of disk blocks consumed but to
control the number of inodes (data structures that contain information about files in UNIX file
systems). Because inodes are used to contain file-related information, this allows control over the
number of files that can be created.
 Official (Closed), Non-Sensitive

• Sys admin gives each user max space

o Open file table has entry to Quota table

o Soft limit violations result in warnings

o Hard limit violations result in errors

o Check limits on login

10. Disk Efficiency & Performance

• Efficiency dependent on

o Disk allocation and directory algorithms

o Types of data kept in file’s directory entry

• Performance

o Disk cache – separate section of main memory for frequently used blocks

o Free-behind and read-ahead – techniques to optimize sequential access

 Official (Closed), Non-Sensitive

o Improve PC performance by dedicating section of memory as virtual disk, or RAM

disk

11. File System Consistency

If there is a System crash before modified files written back

• Leads to inconsistency in FS

• fsck (UNIX) & scandisk (Windows) check FS consistency

Algorithm

• Build 2 tables, each containing counter for all blocks (init to 0)

o 1st table checks how many times a block is in a file

o 2nd table records how often block is present in the free list

 1 not possible if using a bitmap

o Read all i-nodes, and modify table 1

o Read free-list and modify table 2

o Consistent state if block is either in table 1 or 2, but not both

The UFS file system relies on an internal set of tables to keep track of inodes used and available
blocks. When these internal tables are not properly synchronized with data on a disk, inconsistencies
result and file systems need to be repaired.

File systems can be inconsistent because of abrupt termination of the operating system in these
ways:

• Power failure

• Accidental unplugging of the system

• Turning off the system without proper shutdown procedure

• A software error in the kernel

 Official (Closed), Non-Sensitive

File system inconsistencies, while serious, are not common. When a system is booted, a check for
file system consistency is automatically performed (with the fsck command).

Most of the time, this file system checks repairs problems it encounters.

12. Log File System

Log structured (or journaling) file systems record each update to the file system as a transaction

All transactions are written to a log

• A transaction is considered committed once it is written to the log

• However, the file system may not yet be updated

The transactions in the log are asynchronously written to the file system

• When the file system is modified, the transaction is removed from the log

If the file system crashes, all remaining transactions in the log must still be performed

E.g. ReiserFS, XFS, NTFS, ext3, etc

13. Summary & Additional Reading

 File Systems

 Storing Files & Implementing Directories

 Disk Management

 File System Consistency & Log File System

Additional Reading
Click on the links for more information on File Systems.

What Is A File System

Examples Of File System (NTFS, exFAT, FAT32, ext4 & More)