File-System Implementation

In this lecture, we will discuss the following:

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

 To describe the details of implementing local

file systems and directory structures

 To discuss block allocation and free-block

algorithms and trade-offs

 The implementation must

Keep track of the files and directories stored in the file



system, i.e. which disk blocks/sectors store the file data.

Keep track of the free blocks/sectors in the disk.



 Structures used for implementing FS:

on-disk structure – fast,

1.

2.

in-memory structure

 There are various on disk data structures

that are used

to implement a file system. This structure may vary depending upon the OS. The FS may contain info about

 Boot control block (Boot Sector) contains info

needed by system to boot OS from that volume



Needed if volume contains OS, usually first block of volume

 Volume control block (superblock, master file

table) contains volume (partitions) details

Total # of blocks, # of free blocks, block size, free block



pointers or array

 Directory structure

is used to organize the files -

all

starting with the root directory



In UNIX, it includes inode numbers associated to file names.



A mount table – contains information about each mounted volume- list of all the devices which are being mounted to the system.



A directory structure cache – info about recently accessed directories by the CPU.

A system-wide open file table contains a copy of the



FCB of all open file in the system and other info.

process file info)



A per-process open-file table (1 contains a pointer to the appropriate entry in the system-wide open-file table and other info.

Buffers that hold file-system blocks as they are being



read and written to the disk.

2. Linked allocation – solves all problems of contiguous allocation.



No external fragmentation



No compaction, external fragmentation



Each block contains pointer to next block



File ends at nil pointer (the end-of-list pointer value)



Free space management system called when new block needed



Locating a block can take many I/Os and disk seeks



can be used only for sequential access file (to find the ith block of a file, we must start at the begining of that file & follow the pointers until we get to the ith block).

The space required for the pointers. i.e. Each file requires more space that it would



otherwise Improve efficiency by clustering blocks into groups but increases internal



fragmentation ( More space is wasted when a cluster is partially full than when the block is partially full.)



Reliability can be a problem

Mapping Algorithm

Q

Logical Address (LA) / (BlockSize -PointerSize)

R

Block to be accessed = the Qth disk block in the linked chain of disk blocks representing the file.

Displacement into disk block = R + PointerSize

 FAT (File Allocation Table) variation on linked allocation – disk-space

allocation used by MS-DOS and OS/2.



Simple but efficient method of disk space allocation A section of disk at the Beginning of volume has table, which has 1 entry



for each disk block & indexed by block no Much like a linked list, but faster on disk and cacheable

 

Pointers (i.e. disk data blocks numbers) are kept in a table (FAT)



Data Block does not hold a pointer; hence data size in a disk block is a power of 2.

Disadvantages:  Linked allocation cannot support efficient direct access since the pointers to

the blocks are scattered with the block themselves all over the disk.

 Solution: bringing all the pointers together into 1 location: the index

block

 File system maintains free-space list to track available blocks/clusters

(Using term

“ block for simplicity)

”



 How can we keep track of free blocks of the disk?

Which blocks are free?



 We need this info when we want to allocate a new block to a file.



Allocate a block that is free.

 There are several methods to keep track of free blocks:



Bit vector (bitmap) method



Linked list method Grouping



Counting



 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 or n consecutive free blocks on the disk.

 Easy to get contiguous files  Inefficient unless the entire vector is kept in memory

(possible for smaller disks but not for larger ones)

 Bit map requires extra space



Example:

To manage a disk with a bitmap:

1. Calculate the number of blocks on the disk:

Number of Blocks=Block Size/Disk Size

=1,099,511,627,776 / 4096 = 268,435,456 blocks

1. Each block requires 1 bit in the bitmap to indicate whether it is free or used.
2. Convert the number of bits required for the bitmap into bytes:

Bitmap Size (in bytes)= Number of Blocks / 8 =268,435,456 / 8

= 33,554,432bytes = 32MB

The space required for the bitmap to manage a 1 TB disk

with a 4 KB block size is 32 MB.

 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.

 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.

End of Chapter 11