Chapter 11: File System

Implementation

Operating System Concepts – 8th Edition, Silberschatz, Galvin and Gagne

 Chapter 11: File System Implementation

 Allocation Methods
 Free-Space Management

Operating System Concepts – 8th Edition 11.2 Silberschatz, Galvin and Gagne
 Objectives
 Introduction to file system structure.
 To discuss block allocation and free-block algorithms.

Operating System Concepts – 8th Edition 11.3 Silberschatz, Galvin and Gagne
 File-System Structure
 File structure
 Logical storage unit
 Collection of related information
 The File system is organized into layers (levels).
 File system resides on secondary storage (disks)
 Provides efficient and convenient access to disk by
allowing data to be stored, located, and retrieved easily
 File control block – storage structure consisting of
information about a file , including ownership, permissions,
and location of the file contents
 Device driver controls the physical device

Operating System Concepts – 8th Edition 11.4 Silberschatz, Galvin and Gagne
 Layered file system
Application programs
A layered design abstraction

 I/O control :: device drivers and

interrupt service routines that Logical file system
perform the actual block transfers.

 Basic file system :: issues generic

File organization
low-level commands to device module
drivers.

 File organization :: translates logical

block addresses to physical block Basic file system
addresses.

 Logical file system :: handles

i/o control
metadata that includes file-system
structure (e.g., directory structure
and file control blocks (FCB’s). devices
Operating System Concepts – 8th Edition 11.5 Silberschatz, Galvin and Gagne
 Allocation Methods
 An allocation method refers to how disk blocks are allocated
for files:

 Contiguous allocation

 Linked allocation

 Indexed allocation

 The best allocation method grants:

 Effective utilization of disk space.
 Fast accessing to files.

Operating System Concepts – 8th Edition 11.6 Silberschatz, Galvin and Gagne
 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
 The directory entry for each file indicates the address of the
starting block and the length of the area allocated for this
file .

 Sequential access or Random access (Direct access

capability).

 Wasteful of space (dynamic storage-allocation problem)

 External fragmentation

 Files cannot grow

Operating System Concepts – 8th Edition 11.7 Silberschatz, Galvin and Gagne
 Contiguous Allocation of Disk Space

Operating System Concepts – 8th Edition 11.8 Silberschatz, Galvin and Gagne
 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
 A contiguous chunk of space is allocated initially. Then, if
that amount proves not to be large enough, another chunk of
contiguous space, known as an extent, is added.
 The start location of the file and a block count, plus a link to
the first block of the next extent are saved.
 A file consists of one or more extents

 Internal fragmentation becomes a problem if the extents are too

large
 External fragmentation becomes a problem as extents of
varying sizes are allocated and deallocated

Operating System Concepts – 8th Edition 11.9 Silberschatz, Galvin and Gagne
 Linked Allocation
 Each file is a linked list of disk blocks: blocks may be
scattered anywhere on the disk.
block = pointer Example:
512 bytes / block
= 508 bytes of data
+ 4 bytes of pointer

 Simple – need only starting address

 Free-space management system  There is no external
fragmentation
 A file grows as long as free blocks are availableNo need for
compact disk space.
 Disadvantages:
 A space is required for the pointers.
 Internal fragmentation.
 No random access  slow access to block I
 No reliability (your book p509)
Operating System Concepts – 8th Edition11.10 Silberschatz, Galvin and Gagne
 Linked Allocation

Operating System Concepts – 8th Edition 11.11 Silberschatz, Galvin and Gagne
 Linked Allocation

Operating System Concepts – 8th Edition 11.12 Silberschatz, Galvin and Gagne
 File-Allocation Table
 An important variation on linked allocation is the use of a file-
allocation table (FAT)  disk-space allocation used by MS-DOS
and OS/2
 A section of disk at the beginning of each volume is set aside
to contain the table.
 The table has one entry for each disk block and is indexed by
block number.
 The FAT is used in much the same way as a linked list. The
directory entry contains the block number of the first block of
the file.
 The table entry indexed by that block number contains the
block number of the next block in the file.
 This chain continues until the last block, which has a special
end-of-file value as the table entry.
 Unused blocks are indicated by a 0 table value
 Benefit: random-access time is improved, because the disk
head can find the location of any block by only reading the
information in the FAT

Operating System Concepts – 8th Edition 11.13 Silberschatz, Galvin and Gagne
 File-Allocation Table

300 0

EOF

300 is unused block  its value =0

Operating System Concepts – 8th Edition 11.14 Silberschatz, Galvin and Gagne
 Indexed Allocation
 Brings all pointers together into the index block for each file.
 Each file has its own index block, which is an array of disk-block
addresses.
 The ith entry in the index block points to the ith block of the file.

 Logical view

index table

 When the file is created, all pointers in the index block are set to
null (-1). When the ith block is first written, a block is obtained from
the free-space manager, and its address is put in the ith index-block
entry.

Operating System Concepts – 8th Edition 11.15 Silberschatz, Galvin and Gagne
 Example of Indexed Allocation

Operating System Concepts – 8th Edition 11.16 Silberschatz, Galvin and Gagne
 Indexed Allocation (Cont.)
 Mapping from logical to physical in a file of maximum size of 256K
words and block size of 512 words:
# of blocks allocated for the file= 28*210/29= 218-9 = 29= 512
blocks
 We need only 1 block for index table

 Advantages:
 Random access
 Dynamic access without external fragmentation.
 No size-declaration problem

 Disadvantages:
 Internal fragmentation.
 greater pointer overhead than linked allocation:
 Have overhead of index block  wasted space especially
with small size file(ex. have only 1 or 2 blocks)  an entire
index block must be allocated, even if only one or two
pointers will be non-null.
 Need index table: how large?
11.17  many mechanisms.
Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne
 1) Linked scheme
 An index block is normally one disk block. Thus, it can be
read and written directly by itself. To allow for large files, we
can link together several index blocks.
 For example, an index block might contain a small header
giving the name of the file and a set of the first disk-block
addresses.
 The next address (the last word in the index block) is:
 Nil (for a small file) or
 A pointer to another index block (for a large file).

Operating System Concepts – 8th Edition 11.18 Silberschatz, Galvin and Gagne
 2) Multilevel Index Scheme
 A first-level index block to point to a set of second-level index
blocks
 A second-level Index block point to the file blocks

outer-index

index table file

Operating System Concepts – 8th Edition 11.19 Silberschatz, Galvin and Gagne
 Combined Scheme: UNIX UFS (4K bytes per block)

 keep first 15 pointers of the index

block in the file’s inode
 12 pointers: direct blocks
(no index block)
 3 pointers: indirect block

Operating System Concepts – 8th Edition 11.20 Silberschatz, Galvin and Gagne
 Free-Space Management

 To keep track of free disk space, the system maintains

a free-space list. The free-space list records all free
disk blocks.

 To create a file, we search the free-space list for the

required amount of space and allocate that space to
the new file.

 When a file is deleted, its disk space is added to the

free-space list.

Operating System Concepts – 8th Edition 11.21 Silberschatz, Galvin and Gagne
 Free-Space Management: 1) Bit Vector
 the free-space list is implemented as a bit map or bit
vector.
 Each block is represented by 1 bit.
 If the block is free, the bit is 1;
 If the block is allocated, the bit is 0.

 For example, consider a disk where blocks 2, 3, 4, 5, 8,

9, 10, 11, 12, 13, 17, 18,25,26, and 27 are free and the
rest of the blocks are allocated.

 The free-space bit map would be

001111001111110001100000011100000

 The main advantage of this approach is its relative

simplicity and its efficiency in finding the first free
block
Operating System or –n8 consecutive
Concepts
th
Edition free
11.22 blocks on the disk.
Silberschatz, Galvin and Gagne
 Free-Space Management: 1) Bit Vector

 Implementation: Bit vector (n blocks)

0 1 2 n-1
…

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

Block number calculation

(number of bits per word) *

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

Operating System Concepts – 8th Edition 11.23 Silberschatz, Galvin and Gagne
 Free-Space Management: 1) Bit Vector

 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

Operating System Concepts – 8th Edition 11.24 Silberschatz, Galvin and Gagne
 Free-Space Management: 2) Linked List

 Another approach to free-space management is to link

together all the free disk blocks, keeping a pointer to
the first free block in a special location on the disk and
caching it in memory.

 This first block contains a pointer to the next free disk

block, and so on.

Operating System Concepts – 8th Edition 11.25 Silberschatz, Galvin and Gagne
 Free-Space Management: 2) Linked List

Operating System Concepts – 8th Edition 11.26 Silberschatz, Galvin and Gagne
 Free-Space Management: 3) Grouping

 A modification of the free-list approach is to store the

addresses of n free blocks in the first free block.

 The first n-1 of these blocks are actually free. The last
block contains the addresses of another n free blocks,
and so on.

 The addresses of a large number of free blocks can

now be found quickly, unlike the situation when the
standard linked-list approach is used.

Operating System Concepts – 8th Edition 11.27 Silberschatz, Galvin and Gagne
 Free-Space Management: 4) Counting

 rather than keeping a list of n free disk addresses, we can

keep the address of the first free block and the number (n)
of free contiguous blocks that follow the first block.

 Each entry in the free-space list then consists of a disk

address and a count.

 Although each entry requires more space than would a

simple disk address, the overall list will be shorter, as long
as the count is generally greater than 1.

Operating System Concepts – 8th Edition 11.28 Silberschatz, Galvin and Gagne
 End of Chapter 11

Operating System Concepts – 8th Edition, Silberschatz, Galvin and Gagne