Scribd
Upload
8 views16 pages

Lecture6_FileOrganization

The document discusses linked allocation in file system implementation, where each file is represented as a linked list of disk blocks, allowing for efficient use of disk space without external fragmentation. It highlights the advantages, such as the ability to grow files dynamically, as well as disadvantages, including inefficiencies in direct access and reliability concerns due to pointer management. Additionally, it introduces the File Allocation Table (FAT) as a variation of linked allocation, explaining its structure and limitations across different volume sizes.

Uploaded by

abdonasr1998
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views16 pages

Lecture6_FileOrganization

The document discusses linked allocation in file system implementation, where each file is represented as a linked list of disk blocks, allowing for efficient use of disk space without external fragmentation. It highlights the advantages, such as the ability to grow files dynamically, as well as disadvantages, including inefficiencies in direct access and reliability concerns due to pointer management. Additionally, it introduces the File Allocation Table (FAT) as a variation of linked allocation, explaining its structure and limitations across different volume sizes.

Uploaded by

abdonasr1998
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

File Organization and Processing

Lecture 6

File System Implementation

Mohamed Mead
Linked Allocation
Each file is a linked list of disk blocks: blocks may be
scattered anywhere on the disk
Linked Allocation
 Linked allocation solves all problems of contiguous allocation.

 The directory contains a pointer to the first and last blocks of the
file. For example, a file of five blocks might start at block 9 and
continue at block 16, then block 1, then block 10, and finally block 25
Linked Allocation
Each block contains a pointer to the next block.

These pointers are not made available to the user.

Thus, if each block is 512 bytes in size, and a disk address


(the pointer) requires 4 bytes, then the user sees blocks
of 508 bytes.
Linked Allocation
To create a new file, we simply create a new entry in the
directory.

With linked allocation, each directory entry has a pointer


to the first disk block of the file.

This pointer is initialized to null to signify an empty file.

The size field is also set to 0.


Linked Allocation
A write to the file causes the free-space
management system to find a free block, and this
new block is written to and is linked to the end of
the file.

To read a file, we simply read blocks by following


the pointers from block to block.
Linked Allocation
There is no external fragmentation with linked allocation,
and any free block on the free-space list can be used to
satisfy a request.
The size of a file need not be declared when the file is
created.
A file can continue to grow as long as free blocks are
available.
Consequently, it is never necessary to compact disk space.
Linked Allocation
 The major problem is that it can be used effectively only for
sequential-access files.

 To find the ith block of a file, we must start at the beginning of


that file and follow the pointers until we get to the ith block.

 Each access to a pointer requires a disk read, and some require


a disk seek.

 Consequently, it is inefficient to support a direct-access


capability for linked-allocation files.
Linked Allocation
Another disadvantage is the space required for the
pointers.

If a pointer requires 4 bytes out of a 512-byte block, then


0.78 percent of the disk is being used for pointers, rather
than for information.
Linked Allocation
another problem of linked allocation is reliability.
Recall that the files are linked together by pointers
scattered all over the disk, and consider what would happen
if a pointer were lost or damaged.
A bug in the operating-system software or a disk hardware
failure might result in picking up the wrong pointer.
This error could in turn result in linking into the free-space
list or into another file.
Linked Allocation
One solution is to use doubly linked lists, and another is to
store the file name and relative block number in each block.

However, these schemes require even more overhead for


each file.
Linked Allocation
An important variation on linked allocation is the use of a
file-allocation table (FAT).
This simple but efficient method of disk-space allocation
was used by the MS-DOS operating system.
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.
Linked Allocation
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 it reaches the last block,
which has a special end-of-file value.
Linked Allocation
An unused block is indicated by a table value of 0.

Allocating a new block to a file is a simple

finding the first 0-valued table entry and replacing the


previous end-of-file value with the address of the new
block.
Linked Allocation
for a file consisting of disk blocks 217, 618, and 339.
FAT Limitations
FAT12 - used on volumes smaller than 16MB (Floppies)

FAT16 - used on volumes 16MB to 2GB (Hard Drives)

FAT32 - used on volumes 512MB to 8TB (Hard Drives)

You might also like