Transcript 09-File System Implementation-stud-UPDATED - pnu-cs-os

Princess Nora University
Faculty of Computer & Information Systems
Computer science Department
Operating Systems
(CS 340 D)
File System
Implementation
Chapter 12: File System Implementation
1. Allocation Methods
2. Free Space Management
3
OBJECTIVES:
 Introduction to file system structure.
 To discuss block allocation and free-block algorithms
4
File-System Structure
5
File systems
Disks:






A disk can access directly any block of information it contains. Thus, it is
simple to access any file either sequentially or randomly,
It can switch from one file to another requires only moving the read–
write heads and waiting for the disk to rotate.
To improve I/O efficiency, I/O transfers between memory and disk are
performed in units of blocks.
Each block has one or more sectors.
sector size varies from (32 -4,096) bytes; the usual block size is 512
bytes.
File systems



6
file system provides the mechanism for efficient and convenient storage
and access to file contents, including data and programs.
file system resides permanently on secondary storage,
File systems
A file system poses two different design problems:

The first problem is defining how the file system
should look to the user.
1.

2.
7
This task involves defining a file and its attributes, the
operations allowed on a file, and the directory structure for
organizing files.
The second problem is creating algorithms and data
structures to map the logical file system onto the
physical secondary-storage devices
File-System Structure
File structure
 Logical storage unit
 Collection of related information
File system resides on secondary storage (disks)
 Provided user interface to storage,
 mapping logical file system to physical
 Provides efficient and convenient access to disk by
allowing data to be stored, located retrieved easily
File control block–storage structure consisting of information
about a file
Device driver controls the physical device
8
File-System Structure (Cont.)
File system organized into layers (/levels)

Each level in the design
uses the features of
lower levels to create
new features for use by
higher levels.

9
Layered File-System







Logical File System Level:
Metadata is
data that
Input: a symbolic file name
describes other
data.
Output: file information
It manages metadata information (i.e. data about files)
It manages the directory structure
It maintains file-control blocks (FCB).
It is also responsible for protection and security.
FCB: contains information
about the file, including
ownership, permissions,
location …etc.
10
Layered File-System (cont.)





The file-organization module level
Input: file information (logical blocks)
Output: physical block addresses.
It knows about files and their logical blocks, as well as physical
blocks.
It translate logical block addresses to physical block addresses.



Each file’s logical blocks are numbered from 0 through N.
Each physical block is identified by its numeric disk address (e.g.
drive 1,cylinder 73, track 2, sector 10).
It includes the free-space manager, which tracks
unallocated blocks .
11
Layered File-System (cont.)





The basic file system level:
Input: physical block addresses
Output: generic commands to device driver
It needs only to issue generic commands to the
appropriate device driver to read and write physical
blocks on the disk.
This layer also manages the memory buffers and
caches that hold various file-system, directory, and data
blocks.
12
Layered File-System (cont.)

The I/O control level:

It consists of device drivers and interrupt handlers to
transfer information between the RAM and the disk system

A device driver can be thought of as a translator.


13
Device driver input consists of high-level commands such as
“retrieve block 123.”
Device driver output consists of low level, hardware-specific
instructions that are used by the hardware controller, which interfaces
the I/O device to the rest of the system.
File-System Structure (cont.)

layered structure Pros. (++):


layered structure Cons. (--):


useful for reducing duplication of code. The “I/O control level” and
sometimes “the basic file-system code” can be used by multiple file
systems.
Layering can introduce more operating-system overhead, which may
result in decreased performance.
Many file systems are in use today. Most operating
systems support more than one:


14
UNIX uses the UNIX file system (UFS),
Windows NT ,2000 and XP support disk file-system formats of FAT,
FAT32, and NTFS (or Windows NT File System), as well as CDROM, DVD, and floppy-disk file-system formats.
File-System Implementation
15
File-System Implementation


Several on-disk and in-memory structures are used to implement a file
system.
On-disk structures :

Boot control block: (per volume) - contains info. needed by system to boot
OS from that volume

If the disk does not contain an OS, this block can be empty.

Volume control block (superblock /master file table): (per volume)contains volume details such as total # of blocks, # of free blocks, block size,
free block pointers .

Directory structure: (per file system) - is used to organize the files.

File Control Block (FCB): (per file)- contains many details about the file
16
Virtual File Systems


Virtual File Systems (VFS) on Unix provide an
object-oriented way of implementing file systems
VFS allows the same system call interface (the API) to be
used for different types of file systems
o
o
o
17
Separates file-system generic operations from implementation details
Implementation can be one of many file systems types, or network
file system
Schematic View of Virtual File System
18
Directory Implementation
How to implement the directory?

Using Linear list of file names with pointer to the data blocks





Simple to program (++)
Time-consuming to execute (--)
Linear search time (--) >>>>(long time)
Sorted list can be use to decrease search time but maintaining a sorted list is complex .
Hash Table
 a linear list stores the directory entries, but a hash data structure is also used.
 The hash table takes a value computed from the file name and returns a
pointer to the file name in the linear list.
 It Decreases directory search time (++)


19
Some provision must be made for Collisions (--)
The major difficulties with a hash table are its
fixed size (--)
Collisions–situations
where two file names
hash to the same
location
Allocation Methods
20
Allocation Methods
 An allocation method refers to how disk blocks are
allocated for files:
1. Contiguous allocation
2. Linked allocation
3. Indexed allocation
21
1-Contiguous Allocation
22
Contiguous Allocation

Basic Idea:


Each file occupies a set
of contiguous blocks
on the disk
The directory entry for
each file indicates :


23
address of the starting
block
length of the area
allocated for this file
Contiguous Allocation (cont.)

Pros. (++):




Simple
Good performance-the number of disk head seeks required for
accessing contiguously allocated files is minimal
It support sequential and direct access efficiently
Cons. (--):

Dynamic storage-allocation problem (how to satisfy a request of size n
from a list of free holes).


External fragmentation



24
First fit and best fit are the most common strategies used
One solution is compaction (/defragmentation) which is time consuming
File is difficult to grow
Size declaration problem :How does the creator know the size of the
file to be created?
Contiguous Allocation (cont.)

Many newer file systems use a modified contiguousallocation scheme:

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 (i.e. A file
consists of one or more extents)

The location of a file’s blocks is then recorded as:




25
a location
a block count
a link to the first block of the next extent
This scheme is used to improve performance
2-Linked Allocation
26
Linked Allocation

Basic Idea:


Each file is a linked list
of disk blocks: blocks
may be scattered
anywhere on the disk
The directory contains
a pointer to the first and
last blocks of the file.
block
27
=
pointer
Linked Allocation

Pros. (++):






Simple – need only starting address
No external fragmentation
A file can grow - no need for disk compaction
no size declaration problem
It is efficient for sequential access
Cons. (--):




28
It is inefficient for direct access
low performance-It may required multiple disk head seeks to
access single file’s blocks because the block is scattered
A space is required for the pointers.
Low reliability: what happen if a pointer damaged or
lost??
File-allocation table (FAT)

An important variation on linked allocation is the use of a file-allocation table
(FAT).
 It used in the MS-DOS and OS/2 operating systems.

Basic Idea:
 A section of disk at the beginning of each volume is used to store the table
(FAT).
 The FAT is used in much the same way as a linked list.
 The table has one entry for each disk block and is indexed by block number.
 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 as the table entry.
 An unused block is indicated by a table value of 0.
29
File-allocation table (FAT)

Pros. (++):
 Simple
 If the FAT is cached, FAT is
efficient for direct access
30
3-Indexed Allocation
31
Indexed Allocation Method

Basic Idea:



32
Each file has its own
index block which is an
array of disk-block
addresses
The directory contains
the address of the
index block.
To find and read the ith
block, we use the
pointer in the ith indexblock entry.
Indexed Allocation (cont.)

Pros. (++):



wasted space is
more than pointers’
space used in linked
allocation method
Efficient for direct access
No external fragmentation
Cons. (--):


It needs index table….(wasted space)
low performance-It may required multiple disk head seeks to
access single file’s blocks because the block is scattered
Same as performance
problem of linked
allocation method
33
Free-Space Management
34
Free-Space Management


File system maintains free-space list to track available blocks
Different methods to implement free-space list:

Bit vector (/bit map):

35
Blocks that are
not allocated for
any file
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.
Efficiency and Performance

Disks tend to represent a major bottleneck in system
performance, since they are the slowest main computer
component

Efficiency depends on:


36
The disk allocation and directory algorithms in use
The types of data kept in file’s directory entry (e.g. “ last access
date” field need the directory to be updated for every file
access)
Efficiency and Performance

Performance :

Improve performance by dedicating section of memory as disk cache
to store frequently used blocks

Some systems optimize their cache by using different replacement
algorithms such as free-behind and read-ahead techniques
>>>>>>(( For sequential access files ))

Free-behind techniques: removes a page from the buffer as soon as
the next page is requested.


Read-ahead techniques :a requested page and several subsequent
pages are read and cached.

37
The previous pages are not likely to be used again .
These pages are likely to be requested after the current page is processed.
Retrieving these data from the disk in one transfer and caching them saves a
considerable amount of time.
Thank you
The End
38