 Unit4

 File concept, FileAttributes, File

operations, File types, File Structure;
Access methods: SequentialAccess,
Direct Access, Directory Structure: Single
level directory, Two leveldirectory

Operating System Concepts – 8th Edition 10.1 Silberschatz, Galvin and Gagne ©2009
 File-System Interface

 File Concept  File System Implementation-

 Access Methods  File system structure
 Directory Structure  File system implementation
 File-System Mounting  Directory implementation
 File Sharing  Allocation methods
 Protection  Free-space management
 Efficiency and performance

Operating System Concepts – 8th Edition 10.2 Silberschatz, Galvin and Gagne ©2009
 File concept
 Common terms:
 Field
 Basic element of data (student regd no, name, date, etc.)
 Record
 Collection of related fields that we treat as a unit (employee record)
 May be of a fixed or variable size
 File
 Collection of similar records ( ex: time table file, notifications , bills file
 Treated as an entity by applications
 Usually referenced by a name
 Access controls usually at file level
 Database ( example : student database, Employee database)
 Collection of related data files
 Relationships are explicit
 Used by a number of applications

Operating System Concepts – 7th Edition, Jan 1, 2005 10.3 Silberschatz, Galvin and Gagne ©2005
 File types
 File structurer refers to how the files and directories are
organized and stored on the physical storage deviceA file has a
certain defined structure, which depends on its type
 A text file is a sequence of characters organized into lines.
 Example: notepad
 A source code file is a sequence of declarations, statements, and
subroutine definitions
 An object code file and an executable file each contain a
sequence of bytes organized into headers and tables of data and
code understandable by a system linker and loader
 A file is named for the convenience of its human users, and is
referred to by its name
 After a file is created, it becomes independent of the process that
created it; other processes may read it or edit it

Operating System Concepts – 7th Edition, Jan 1, 2005 10.4 Silberschatz, Galvin and Gagne ©2005
 File Attributes
 Name – the only information kept in human-readable form
 Identifier – unique tag (a number) that identifies file within the file system
 Type – used by systems that support different types of files
 Location – pointer to file location on a device
 Size – current file size in bytes, words, or blocks
 Protection – access controls for who can read, write, and execute
 Time, date, and user identification – used for documenting file
creation, last modification, and last use
 Information about all files is kept in the directory structure, which also is
located on secondary storage

Operating System Concepts – 7th Edition, Jan 1, 2005 10.5 Silberschatz, Galvin and Gagne ©2005
 File Operations
 A file is an abstract data type with operations to
 Create
 Write ( By using write pointer)
 Read ( by using read pointer)
 Reposition within file
 Delete
 Truncate (i.e., erase the contents but keep the file)
Examle : Retrieve All,• Retrieve One ,• Retrieve Next
• Retrieve Previous, Insert_One, • Delete_On,Update_One
 Reposition within file:
 Repositioning within a file need not involve any actual I/O.
 Deleting a file:
 We will release all file space , so that it can be reused by other
files. And erase the directory entry.
 Truncating file:
 The user want to erase the contents of a file but keep its attributes
Operating System Concepts – 7th Edition, Jan 1, 2005 10.6 Silberschatz, Galvin and Gagne ©2005
  File Types:
 Used to indicate the internal structure of the file.
 It refers to the ability of the operating system to differentiate various types of files like
text files, binary, and source files.
 Operating systems like MS_DOS and UNIX has the following type of files:
 Character Special File
 It is a hardware file that reads or writes data character by character, like mouse,
printer, and more.
 Ordinary files
 These types of files stores user information.
 It may be text, executable programs, and databases.
 It allows the user to perform operations like add, delete, and modify.
 Directory Files
 Directory contains files and other related information about those files
 . Its basically a folder to hold and organize multiple files.
 Special Files
 These files are also called device files.
 It represents physical devices like printers, disks, networks, flash drive, etc.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.7 Silberschatz, Galvin and Gagne ©2005
 The name of the file split into 2 parts. One is name and second is
Extension. The file type is depending on extension of the file.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.8 Silberschatz, Galvin and Gagne ©2005
  Device Drivers
Lowest level
Communicates directly with peripheral devices
Responsible for starting I/O operations on a device
 Basic File System
 • Physical I/O
 • Deals with exchanging blocks of data
 Basic I/O Supervisor :
 • Responsible for file I/O initiation and termination
 Logical I/O
 • Enables users and applications to access records

Operating System Concepts – 7th Edition, Jan 1, 2005 10.9 Silberschatz, Galvin and Gagne ©2005
  FILE STRUCTURE
 File types also can be used to indicate the internal structure of the
file.
 The operating system requires that an executable file have a
specific structure so that it can determine where in memory to load
the file and what the location of the first instruct ion is.
 If OS supports multiple file structures, the resulting size of OS is
large.
 If the OS defines 5 different file structures, it needs to contain the
code to support these file structures.
 All OS must support at least one structure that of an executable file
so that the system is able to load and run programs.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.10 Silberschatz, Galvin and Gagne ©2005
  FILE ACCESS METHODS
 Files stores information, this information must be accessed and
read into computer memory.
 There are so many ways that the information
in the file can be accessed.
 1. Sequential file access:
 Fixed record format
 Information in the file is processed in order i.e. one record after the
other. Magnetic tapes are supporting this type of file accessing.
 Eg : A file consisting of 100 records, the current position of
read/write head is 45th record, suppose we want to read the 75th
record then, it access sequentially from 45,
 46, 47
 …….. 74, 75. So the read/write head traverse all the records
between 45 to 75.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.11 Silberschatz, Galvin and Gagne ©2005
  Direct access:
 Direct access is also called relative access.
 Here records can read/write randomly without any order.
 The direct access method is based on a disk model of a file,
because disks allow random access to any file block.
 Eg : A disk containing of 256 blocks, the position of read/write head
is at 95th block.
 The block is to be read or write is 250th block. Then we can access
the 250th block directly without any restrictions.
 Eg : CD consists of 10 songs, at present we are listening song 3, If
we want to list en song 10, we can shift to 10.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.12 Silberschatz, Galvin and Gagne ©2005
  Indexed Sequential File access
 The main disadvantage in the sequential file is, it takes more time to
access a Record.
 .Records are organized in sequence based on a key field.
 Eg :
 A file consisting of 60000 records,the master index divide the total
records into 6 blocks, each block consisiting of a pointer to secondary
index.
 The secondary index divide
the records into 10 indexes.
 Each index consisting of a pointer
to its original location.
 Each record in the index file consisting
of 2 field,
 A key field and a pointer field.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.13 Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7th Edition, Jan 1, 2005 10.14 Silberschatz, Galvin and Gagne ©2005
 file common organizations

 Pile
 Sequential file
 Indexed sequential file
 Indexed file
 Direct (Hashed) file

Operating System Concepts – 7th Edition, Jan 1, 2005 10.15 Silberschatz, Galvin and Gagne ©2005
 File Organization
 Indexed Sequential File
 Adds an index to speed lookup
 Index file is a sequential file
 May have multiple levels of indexes
 Overflow area to handle new records
 Link from main records to overflow, back
 Indexed File
 May have multiple indexes
 One for each field we may search
 Records accessed only through the indexes
 Each index may be exhaustive or partial

Operating System Concepts – 7th Edition, Jan 1, 2005 10.16 Silberschatz, Galvin and Gagne ©2005
 Access Methods
1. Sequential Access
read next
write next
reset
no read after last write
(rewrite)
Ex: editors, compilers
2. Direct Access (file operations  include block no. as parameter ‘n’)
read n
write n
position to n
read next
write next
rewrite n
Operating System Concepts – 8th Edition 10.17 Silberschatz, Galvin and Gagne ©2009
 Access
Methods

SEQUENTIAL ACCESS

 Implemented by the file system.

 Data is accessed one record right after the last.

 Reads cause a pointer to be moved ahead by one.

 Editors and compilers usually access files in this fashion.

 Such a method is reasonable for tape

10: File Systems 18

Operating System Concepts – 7 Edition, Jan 1, 2005
th
10.18 Silberschatz, Galvin and Gagne ©2005
 Access
Methods
DIRECT ACCESS
Direct access allows random access to any file block.
 It allows programs to read and write records rapidly in no particular order.
 Method useful for disks.

 The file is viewed as a numbered sequence of blocks or records.

 There are no restrictions on which blocks are read/written in any order.

 User now says "read n" rather than "read next".

 .

10: File Systems 19

Operating System Concepts – 7 Edition, Jan 1, 2005
th
10.19 Silberschatz, Galvin and Gagne ©2005
 Access
Methods
OTHER ACCESS METHODS

Built on top of direct access and often implemented by a user utility.

Indexed ID plus pointer.

An index block says what's in each remaining block or contains pointers to blocks
containing particular items. Suppose a file contains many blocks of data arranged by
name alphabetically.

Example 1: Index contains the name appearing as the first record in each block. There
are as many index entries as there are blocks.

Example 2: Index contains the block number where "A" begins, where "B" begins, etc.
Here there are only 26 index entries.

10: File Systems 20

Operating System Concepts – 7 Edition, Jan 1, 2005
th
10.20 Silberschatz, Galvin and Gagne ©2005
 Access
Methods
Adams
Example 1: Index contains the
Arthur
name appearing as the first
record in each block. There are Asher
Smith, John | data
as many index entries as there
are blocks.
Smith

Adams Adams | Data

Example 2: Index contains the block Baker Arthur | Data

number where "A" begins, where Charles Asher | Data
"B" begins, etc. Here there are Baker | Data
only 26 index entries.
Saarnin Saarnin | data

Smith, John | data

10: File Systems 21

Operating System Concepts – 7 Edition, Jan 1, 2005
th
10.21 Silberschatz, Galvin and Gagne ©2005
 Sequential-access File

Operating System Concepts – 7th Edition, Jan 1, 2005 10.22 Silberschatz, Galvin and Gagne ©2005
 Simulation of Sequential Access on a Direct-access File

cp = current position

Operating System Concepts – 7th Edition, Jan 1, 2005 10.23 Silberschatz, Galvin and Gagne ©2005
 Example of Index and Relative Files

Operating System Concepts – 7th Edition, Jan 1, 2005 10.24 Silberschatz, Galvin and Gagne ©2005
Directory Structure
 Directory Structure
 A directory contains information about the files, including
attributes , location and ownership

Directory

Files
F1 F2 F4
F3
Fn

Both the directory structure and the files reside on disk. Backups of these two structures may be kept on tapes.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.26 Silberschatz, Galvin and Gagne ©2005
 A Typical File-system Organization

Operating System Concepts – 7th Edition, Jan 1, 2005 10.27 Silberschatz, Galvin and Gagne ©2005
 Operations Performed on Directory

 Search for a file

 Create a file
 Delete a file
 List a directory
 Rename a file
 Traverse the file system

Operating System Concepts – 7th Edition, Jan 1, 2005 10.28 Silberschatz, Galvin and Gagne ©2005
 Goal: Organize a directory (logically) based
on the following criteria:

 Efficiency – locating a file quickly

 Naming – convenient to users
 Two users can have same name for different files
 The same file can have several different names
 Grouping – logical grouping of files by properties, (e.g., all
Java programs, all games, …)

Operating System Concepts – 7th Edition, Jan 1, 2005 10.29 Silberschatz, Galvin and Gagne ©2005
 Directory Structures

 Types of Directory Structure

 There are various types of directory structure:
 Single-Level Directory
 Two-Level Directory
 Tree-Structured Directory
 Acyclic Graph Directory
 General-Graph Directory

Operating System Concepts – 7th Edition, Jan 1, 2005 10.30 Silberschatz, Galvin and Gagne ©2005
  single-Level Directory: – Single-Level Directory is the easiest
directory structure. There is only one directory and that directory is
called a root directory.
 All the files are present in one directory that makes it easy to
understand. In this, the user cannot create the subdirectories
 Disadvantages
 If the size of the directory is large , then the searching will be tough.
we cannot group the similar type of files.
 there is a possibility
of collision because the two
files cannot have the same
name.
 The task of choosing
the unique file name is a
little bit complex.
 .

Operating System Concepts – 7th Edition, Jan 1, 2005 10.31 Silberschatz, Galvin and Gagne ©2005
 Two-Level Directory
 In this, it is possible to create an individual directory for each of the users.
 There is one master node in the two-level directory that include an individual
directory for every user.
 At the second level of the directory, there is a different directory present for each
of the users.
 Without permission, no user can enter into the other user’s directory.
 Disadvantage :
 one user cannot share the file with another user.
 it is not scalable.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.32 Silberschatz, Galvin and Gagne ©2005
  In a tree-structured directory, there is an own directory of each
user, and any user is not allowed to enter into the directory of
another user.
 Although the user can read the data of root, the user cannot modify
or write it.
 The system administrator only has full access to the root directory.
 advantages of the tree-structured directory are:
 The tree-structured directory is very scalable.
 the chances of collision are less.
 the searching is quite easy because, in this, we can use both types
of paths, which are the absolute path and relative path.
 Disavantage::
 In the tree-structure directory, the files cannot be shared.
 Tree-structure directory is not efficient because, in this, if we want
to access a file, then it may go under multiple directories.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.33 Silberschatz, Galvin and Gagne ©2005
  Absolute'' describes something as being independent.
 while the word ''relative'' refers to something being
dependent.
 Absolute paths always start with the root directory and
provide the full path to the file or directory.
 For example, the absolute path to the home directory of a user
named “sri" would be "/home/sri".
 On the other hand, a relative path is a path to a file or directory that
is relative to the current directory

Operating System Concepts – 7th Edition, Jan 1, 2005 10.34 Silberschatz, Galvin and Gagne ©2005
 Tree-Structured/ hierarchical Directories

Operating System Concepts – 7th Edition, Jan 1, 2005 10.35 Silberschatz, Galvin and Gagne ©2005
 Acyclic-Graph Directories
 It allows directories to have shared subdirectories and files.
 Shared files and subdirectories can be implemented by using links.
 A link is a pointer to another file or subdirectory.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.36 Silberschatz, Galvin and Gagne ©2005
 Acyclic-Graph Directories (Cont.)
 Same advantages as tree-structured directory
 In addition, the same file or directory may have a reference that
appears in two or more directories
 Disadvantage is that its structure is more complex
 The same file or directory may be referred to by many names
 Need to be cautious of dangling pointers when files are deleted
 Solutions to deletion
 Just delete the link
 Preserve the file until all links (i.e., references) are deleted
 This requires a new directory entry type called a link
 Keep a count of the number of references

Operating System Concepts – 7th Edition, Jan 1, 2005 10.37 Silberschatz, Galvin and Gagne ©2005
  the General-Graph directory is another vital type of directory
structure.
 In this type of directory, within a directory we can create cycle of the
directory where we can derive the various directory with the help of
more than one parent directory.
 the General-Graph directory is more flexible than the other
directory structure.
 Cycles are allowed in the general-graph directory.
 Disadvantage :
 General-graph directory
is more costly, among other
directory structures.
Traversing is easy.
Easy sharing is possible

Operating System Concepts – 7th Edition, Jan 1, 2005 10.38 Silberschatz, Galvin and Gagne ©2005
 File System Mounting

Mounting is a process in which the operating system adds ( attaching) the directories
and files from a storage device to the user’s computer file system.
The file system is attached to an empty directory, by adding so the system user can
access the data that is available inside the storage device through the system file
manager.
 Storage systems can be internal hard disks, external hard disks, USB flash drivers,
SSD cards, memory cards, network-attached storage devices, CDs and DVDs, remote
file systems, or anything
Attaching the files to the file system,

A file system must be mounted before it can be accessed

A unmounted file system (i.e.(b)) is mounted at a mount point
Mount point: location within file structure where the file system is to be attached.
Or mount point specifies the location at which the file system is attached

Operating System Concepts – 8th Edition 10.39 Silberschatz, Galvin and Gagne ©2009
  Mounting Indifferent Operating Systems
 Linux-Unix based OS
 We want to mount /dev/sdb1 to an existing directory /mnt.
 sudo mount /dev/sdb1 /mnt/mydisk
 After mounting, we have to unmount after use
 sudo umount /mnt/mydisk
 Sudo is a command-line utility for Unix and Unix-based operating systems such as Linux
and macOS.
 The utility provides an efficient way to temporarily grant users or user groups privileged access to
system resources .
 so that they can run commands.

Operating System Concepts – 8th Edition 10.40 Silberschatz, Galvin and Gagne ©2009
  Windows OS
 In windows mounting is very easy for a user.
 When we connect the external storage devices, windows automatically
detect the file system and mount it to the drive letter.
 Drive letter may be D: or E:.
 Steps:
 Connect an external storage device to your PC.
 Windows detects the file system on the drive (e.g., FAT32 or NTFS) and
assigns it a drive letter, such as “E:”.
 You can access the derive by going through, THIS PC –> FILE EXPLORER
–>”E:” drive
 Access the data.

Operating System Concepts – 8th Edition 10.41 Silberschatz, Galvin and Gagne ©2009
  Mac OS
 In Mac OS when we connect an external storage it will automatically mount,
and it will be accessible via Finder. As an advanced mounting method user
can also use the command diskutil in Terminal.
 Method 1:
 Steps:
 Connect an external storage device to your MAC.
 MS OS detects the file system and automatically mount it.
 You can access the drive by opening Finder, and it will appear in the
sidebar.

Operating System Concepts – 8th Edition 10.42 Silberschatz, Galvin and Gagne ©2009
 (a) Existing. (b) Unmounted Partition

Operating System Concepts – 8th Edition 10.43 Silberschatz, Galvin and Gagne ©2009
 Mount Point

Operating System Concepts – 8th Edition 10.44 Silberschatz, Galvin and Gagne ©2009
 Common Mount Points
 Unix or Linux – any directory
 / - root directory
 /floppy – floppy drive
 /cdrom – cdrom drive
 /dev – device “drivers”
 /home – user directories
 Windows XP – drive letters (examples only)
 A:, B: - floppy drive
 C: - hard drive
 D: - CD-ROM drive
 E: - USB drive
 F: - network drive

Operating System Concepts – 7th Edition, Jan 1, 2005 10.45 Silberschatz, Galvin and Gagne ©2005
 File Sharing – Remote File Systems
 Two types of file systems.
 Local file system: Files are available with in the system.
 Global File system: Files are available globally.
 Files sharing in Remote file systems through one of the following procedure
1)Manually via programs like FTP
2)Files is distributed among systems by using distributed file systems
Network File System (NFS) is a common distributed file-sharing method
3) Semi automatically via the world wide web ( by using URL in browser)
 Client-server model is used to implement remote file systems, allows clients to mount
remote file systems from servers
Server can serve multiple clients

In order to implement client server model in Unix/Linux

NFS (Network file system)protocol is used for file sharing
In order to implement client server model in Windows

CIFS (common internet file system ) protocol is used to share files in remote file
systems.
 Distributed Information Systems (distributed naming services) such as LDAP, DNS,
NIS, Active Directory implement unified10.46
Operating System Concepts – 8th Edition access to information needed forGalvin
Silberschatz, remote
and Gagne ©2009
 File Sharing – Failure Modes

 Remote file systems add new failure modes, due

to network failure, server failure
 Recovery from failure can involve state
information about status of each remote
request
 Stateless protocols such as NFS include all
information in each request, allowing easy
recovery but less security

Operating System Concepts – 8th Edition 10.47 Silberschatz, Galvin and Gagne ©2009
 File Sharing – Consistency Semantics
 Consistency semantics specify how multiple users are to access a
shared file simultaneously
 Similar to process synchronization algorithms
 Tend to be less complex due to disk I/O and network latency
(for remote file systems
 Andrew File System (AFS) implemented complex remote file
sharing semantics
 Unix file system (UFS) implements:
 Writes to an open file visible immediately to other users of
the same open file
 Sharing file pointer to allow multiple users to read and write
concurrently
 AFS has session semantics
 Writes only visible to sessions starting after the file is closed
Operating System Concepts – 8th Edition 10.48 Silberschatz, Galvin and Gagne ©2009
 Protection
 Protection : always used to protect internal threads / processes
from unauthorized threads/ processes.
 Security: provide security to the system from external
unauthorized access from external users.
 Example: firewall
 File owner/creator should be able to control:
 what can be done to a file
 by whom
 Types of access
 Read
 Write
 Execute
 Append
 Delete
 List
Operating System Concepts – 7th Edition, Jan 1, 2005 10.49 Silberschatz, Galvin and Gagne ©2005
 Access rights that can be assigned to a particular user for a
particular file.

None : the user may not even learn of the existence of the file.
Knowledge : the user can pass the information regarding the file
such as existence of file, owner, date of creation etc..
Execution : the user can load and execute a program without
copying it.
Reading :The user for any can read the file, .
Appending :the user can add data to a file only at the end but can
not modify or delete any of the file contents.
Updating : the user can add, delete and modify the data .
Changing protection : user can alter the access rights .
Deletion : the user has full authority to delete a file.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.50 Silberschatz, Galvin and Gagne ©2005
 File permission & Access modes in Unix

 File ownership is an important component of Unix that provides a

secure method for storing files.
 Three classes of users

a) owner access (7 -111)

b) group access (6- 110)
c) others (1)

 Every file in Unix has the following attributes

 Owner permissions − The owner's permissions determine what
actions the owner of the file can perform on the file.
 Group permissions − The group's permissions determine what
actions a user, who is a member of the group that a file belongs to,
can perform on the file.
 Other (world) permissions − The permissions for others indicate
what action all other users can perform on the file.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.51 Silberschatz, Galvin and Gagne ©2005
  The first three characters (2-4) represent the permissions for the
file's owner.
 For example, -rwxr-xr-- represents that the owner has read (r),
write (w) and execute (x) permission.

 The second group of three characters (5-7) consists of the

permissions for the group to which the file belongs.
 For example, -rwxr-xr-- represents that the group has read (r) and
execute (x) permission, but no write permission.

 The last group of three characters (8-10) represents the

permissions for everyone else.
 For example, -rwxr-xr-- represents that there is read (r) only
permission.

Operating System Concepts – 7th Edition, Jan 1, 2005 10.52 Silberschatz, Galvin and Gagne ©2005
  Changing Permissions
 To change the file or the directory permissions, you use the chmod (change mode)
command.
 There are two ways to use chmod —
 the symbolic mode and the absolute mode.
 With symbolic permissions you can add, delete, or specify the permission set you
want by using the operators in the following table
 + Adds the designated permission(s) to a file or directory.
 - Removes the designated permission(s) from a file or directory.
 = Sets the designated permission(s).
 Example using testfile.
 Running ls -1 on the testfile shows that the file's permissions are as follows −
 $ ls -l testfile
 -rwxrwxr-- 1 amrood users 1024 Nov 2 00:10 testfile
 Example : Add permission
 $chmod o+wx testfile
 $ ls -l testfile
 -rwxrwxrwx 1 amrood users 1024 Nov 2 00:10 testfile
 Remove Permission :
 chmod u-x test file
 $ ls -l testfile
 -rw-rwxrwx 1 amrood users 1024 Nov 2 00:10 testfile

Operating System Concepts – 7th Edition, Jan 1, 2005 10.53 Silberschatz, Galvin and Gagne ©2005
 Using chmod with Absolute Permissions
 The second way to modify permissions with the chmod command is to use a number
to specify each set of permissions for the file.
0 No permission ---
1 Execute permission --x
2 Write permission -w-

Execute and write

3 permission: 1 (execute) + 2 -wx
(write) = 3

4 Read permission r--

Read and execute

5 permission: 4 (read) + 1 r-x
(execute) = 5

Read and write permission:

6 rw-
4 (read) + 2 (write) = 6

All permissions: 4 (read) + rwx

7
2 (write) + 1 (execute) = 7

Operating System Concepts – 7th Edition, Jan 1, 2005 10.54 Silberschatz, Galvin and Gagne ©2005
  Example :

 $chmod 743 testfile

 $ls -l testfile
 -rwxr---wx 1 amrood users 1024 Nov 2 00:10 testfile

Operating System Concepts – 7th Edition, Jan 1, 2005 10.55 Silberschatz, Galvin and Gagne ©2005
 File System Implementation

Operating System Concepts – 8th Edition, Silberschatz, Galvin and Gagne ©2009
 File-System Structure
 Disks are usually accessed in physical blocks, rather than a byte at
a time.
 Block sizes may range from 512 bytes to 4K or larger.
 File structure
 Logical storage unit
 Collection of related information
 File system resides on secondary storage (disks)
 File system organized into layers

Operating System Concepts – 8th Edition 10.57 Silberschatz, Galvin and Gagne ©2009
 Layered File System

Operating System Concepts – 8th Edition 10.58 Silberschatz, Galvin and Gagne ©2009
  Logical file system : maintains directure structure , methods for
protection and security.
 accepts file name as the input and checks that whether the file is present
in directory structure or not.
 If the file is present in the directory structure then it finds the location of
the file as well logical block number of the file.
 It finds the logical block number.
 That logical block number will give input to the File organization module.
 File organization module. accepts the logical block (file) number as
the input it performs a mapping in order to find the physical block
number in which the file is stored in the hard disk.
 i.e the task of file organization module is it finds the physical block
number for the corresponding logical block number.
 Physical block number means the exact location of file in hard disk.

Operating System Concepts – 8th Edition 10.59 Silberschatz, Galvin and Gagne ©2009
  The basic file system level works directly with the device drivers in terms of
retrieving and storing raw blocks of data, without any consideration for what is in
each block
 It issues generic commands to the underline layer.( i.e I/O control)
 i.e issues generic commands to the device driver
 Example : Read 123, Write 123 ( block number = 123)
 Many file systems are in use today like UNIX file system, FAT, FAT32,NTFS , GOOGLE FILE
SYSTEM etc..
 I/O Control consists of device drivers and Interrupt handles, special software
programs which communicate with the devices by reading and writing special
codes directly to and from memory addresses corresponding to the controller
card's registers.

Operating System Concepts – 8th Edition 10.60 Silberschatz, Galvin and Gagne ©2009
 File system implementation
 In order to implement file system we are using two types of structures.
 On disk structurers (All the structures maintained in secondary storage)
 In- Memory structures ( all the structures maintained in side the main
memory.)
 On-Disk structures : contains information about

Boot control block- contains information needed to boot an OS

Volume control block- contains information about volume( partition) details .
Directory structure : to organize files. It has list of files in that directory
File control block : information about file, including owner of file,
permissions, and location of file contents
 Boot control block: contains information Needed to boot an OS.
 if the disk has no OS , this block is empty.
usually first block of volume in UNIX it is called boot block & in NTFS it called
boot sector.

Operating System Concepts – 8th Edition 10.61 Silberschatz, Galvin and Gagne ©2009
 Volume control block: contains information about volume( partition) details
i.e no. of blocks, size of blocks, free block count etc.
In UNIX it is called superblock.
Directory structure: to organize files.
It has list of files in that directory.

File control block: information about file, including owner of file,

permissions, and location of file contents.

Operating System Concepts – 8th Edition 10.62 Silberschatz, Galvin and Gagne ©2009
 File system implementation
 In-memory:

1. In-memory mount table: information about each mounted volume ( partition)

and mount point etc
2. In-memory directory structure cache: information of recently accessed
directories
3. System-wide open-file table: copy of FCB( file control block) of each open file
i.e information about how many files opened by processes.
4 .Per-process open-file table: points to appropriate entry in system-wide open-
file table.
Each process how many files opened .
Example : process A – 2files , Process B – 3 files

Operating System Concepts – 8th Edition 10.63 Silberschatz, Galvin and Gagne ©2009
 In-Memory File System Structures
 Fig. illustrates the necessary file system structures provided by the OS
 Figure (a) refers to opening a file.
 In order to open a file specify the file name,
 i.e file name as the input, when ever if u want to open a file, first OS
checks whether that file is present in secondary storage directory
structurer or not.
 Then from that directory structure , the file name identified , that files
information will get from FCB of secondary memory.
 If it is there that file information will be transferred to Directory structure
in kernel memory.
 For next time if the same file will try to open then no need to check in
secondary memory , u can retrieve from kernel memory.
 Figure (b) refers to reading a file.

Operating System Concepts – 8th Edition 10.64 Silberschatz, Galvin and Gagne ©2009
 In-Memory File System Structures

Operating System Concepts – 8th Edition 10.65 Silberschatz, Galvin and Gagne ©2009
 Partitions and mounting

 Disk– can be sliced into multiple partitions

 Raw disk – containing no file system
 Boot information: sequential series of blocks, loaded
as an image into memory
 Systems can be dual-booted.
 Root partition: contains OS kernel & other system
files is mounted at boot time

Operating System Concepts – 8th Edition 10.66 Silberschatz, Galvin and Gagne ©2009
 Virtual File Systems (VFS)
 VFS 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.

 The API is to the VFS interface, rather than any specific type
of file system.

Operating System Concepts – 8th Edition 10.67 Silberschatz, Galvin and Gagne ©2009
  Directory Implementation
 There are various types of algorithm which we use for directory
implementation.
 The selection of a suitable algorithm for directory implementation is
an essential task because it directly affects system performance.
 We can classify the directory implementation algorithm based on the
data structure.
 Mostly, we use two types of algorithms:
 Linear List
 Hash Table

Operating System Concepts – 8th Edition 10.68 Silberschatz, Galvin and Gagne ©2009
  Linear List: – The linear list is the most straightforward algorithm
which is used for directory implementation.
 In this algorithm, we keep all the files in a directory like a singly
linked list.
 Every file comprises of a pointer to the data blocks that are
allocated to it and the next file in the directory.

Operating System Concepts – 8th Edition 10.69 Silberschatz, Galvin and Gagne ©2009
  Simple to program.
 Time consuming to execute.
 TO create a new file
 Search directory to ensure that no existing file has same name.
 Add new entry at the end of directory.
 To delete a file:
 Search a directory for named file and release space allocated to it.
 To reuse directory entry:
 For example one file is removed from linear list , that space should be
reused.
 For that we have two approaches
 i) mark entry as unused by specifying bit = 0 in each
 Ii) attach it to a list of free directory entries.
 Disadvantages
 Finding a file requires a linear search.
 It maintains a software cache to improve file access.
Operating System Concepts – 8th Edition 10.70 Silberschatz, Galvin and Gagne ©2009
  Hash table :
 A linear list stores the directory entries, but hash data structure is also used.
 In a directory, for every file, there is a key & value pair that is generated,
and when the key& value pair is generated, then we store it into the hash
table.
 What ever is the file name it is hashed to index into hash table key and
Value is generated .
 What ever the value against key that is pointer to the file name and then get
data block.
 With the help of the key, we only have to check the entries of the hash
table,
 i.e Hash table takes a value computed from file name and returns a pointer
to file name in the linear list.
 i.e Whole list does not need to be searched to get required to get required
file name.

Operating System Concepts – 8th Edition 10.71 Silberschatz, Galvin and Gagne ©2009
  A linear list stores the directory entries, but
hash data structure is also used.
 In a directory, for every file, there is a key &
value pair that is generated, and when the
key& value pair is generated, then we store
it into the hash table.
 What ever is the file name it is hashed to
index into hash table key and Value is
generated .
 What ever the value against key that is
pointer to the file name and then get data
block.
 i.e Hash table takes a value computed from
file name and returns a pointer to file name
in the linear list.
 i.e Whole list does not need to be searched
to get required to get required file name.
 Adv:
 Decrease search [Link] and deletion
are straight forward.
 Dis:Hash table fixed in size.
 Dependence
System Conceptsof
– 8hash Silberschatz, Galvin and Gagne ©2009
Operating th
function
Edition on size. 10.72
 Allocation Methods
 File Allocation Methods
 There are different kinds of methods that are used to allocate disk space.
 Allocate space to the files so that disk space is utilized in an efficient
manner and that will effect the system performance
 There are different types of file allocation methods,
 Contiguous allocation
 Linked list allocation
 Indexed allocation
 Factors to consider:
 Processing speed should be good for sequential & random access.
 Disk space utilization ( i.e while allocation wastage of memory space
should minimal)
 Main memory requirement. ( main memory usage should be less)

Operating System Concepts – 8th Edition 10.73 Silberschatz, Galvin and Gagne ©2009
 1. Contiguous Allocation
 Each file occupies a set of contiguous blocks on the disk
 Disk addresses define a linear ordering on the disk.
 When head movement is needed , the head need only move from one
track to the next.
 Contiguous allocation of a file is defined by the disk address and length of
the first block.
 The directory entry for each file indicates the address of the starting block
and then length.

Operating System Concepts – 8th Edition 10.74 Silberschatz, Galvin and Gagne ©2009
  Advantages :
 The contiguous allocation method gives excellent read performance.
 Contiguous allocation is easy to implement.
 The contiguous allocation method supports both types of file access
methods that are sequential access and direct access.
 The Contiguous allocation method is fast because, in this method
number of seeks is less due to the contiguous allocation of file blocks.

drawbacks :
[Link] storage-allocation problem
[Link] fragmentation
[Link] cannot grow

Operating System Concepts – 8th Edition 10.75 Silberschatz, Galvin and Gagne ©2009
 Linked Allocation
 Allocation is on an individual block basis.
Each block contains a pointer to the next block in the chain.
 Again the file table needs just a single entry for each file, showing the starting
block and the end of the file.
 Any free block can be added to the chain.
 Adv:
 The blocks need not be continuous. Block
may be scattered anywhere on the disk.
 Simple
 There is no need to declare the size of a file
when that file is created.
 File can continue to grow as long as there are
free blocks.
 No external fragmentation.
Disadvantages:
 No random access, Can be used only for sequential access files,
If the pointer in the linked list break in linked list allocation, then the file gets corrupted.
Operating In the Concepts
System disk block
– 8th for the
Edition pointer, it needs some
10.76 extra space. Silberschatz, Galvin and Gagne ©2009
 Indexed Allocation
In the index allocation method, we have an additional block, and
that block is known as the index block.
For each file, there is an individual index block.
In the index block, the ith entry holds the disk address of the ith file
block.
-1 indicates end of the file.

Operating System Concepts – 8th Edition 10.77 Silberschatz, Galvin and Gagne ©2009
 File allocation table

 Variation on linked allocation

 Simple, but efficient

 Section of disk beginning – set aside for table

 One entry for each disk block

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

Operating System Concepts – 8th Edition 10.79 Silberschatz, Galvin and Gagne ©2009
 Indexed Allocation
 Brings all pointers together into the index block.
 Logical view.

index table

Operating System Concepts – 8th Edition 10.80 Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition 10.81 Silberschatz, Galvin and Gagne ©2009
 Indexed Allocation (Cont.)
 Need index table
 Random access
 Dynamic access without external fragmentation, but have overhead of index block.
1. Linked scheme: normally one disk block
Large files: link together several index blocks
2. Multilevel index:
 E.g. Two Level Index - first level index block points to a set of second level
index blocks, which in turn point to file blocks.
 Increase number of levels based on maximum file size desired.
Maximum size of file is bounded.

Disadvantages of Index Allocation
The disadvantages of index allocation are:
1. In index allocation, pointer overhead is more.
2. We can lose the entire file if an index block is not correct.
3. It is totally a wastage to create an index for a small file

Operating System Concepts – 8th Edition 10.82 Silberschatz, Galvin and Gagne ©2009
 Free-Space Management
Disk space is limited, it is necessary to reuse the space from deleted files for
new files.
Free space management is a critical aspect of operating systems as it
involves managing the available storage space on the hard disk or
other secondary storage devices.
The operating system uses various techniques to manage free space
and optimize the use of storage devices.
The free space list can be implemented mainly as:
1. Bit vector /Bit Map
2. Linked list
3. Grouping
4. Counting

Operating System Concepts – 8th Edition 10.83 Silberschatz, Galvin and Gagne ©2009
  A Bitmap 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.
Example:
(where green blocks are
allocated) can be represented by a bitmap
of 16 bits as: 0000111000000110.
2.
Consider a disk block where blocks 2,3,4,5,8,9,10,11,12,13, are free
Then the bit map would be
00111100111111
Adv Simple to understand. Finding the first free block is efficient.
Dis:The efficiency of this method reduces as the disk size increases.
Operating System Concepts – 8th Edition 10.84 Silberschatz, Galvin and Gagne ©2009
 Free-Space Management (Cont.)
2. Linked list (free 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.
Block 2 as the first free block.
It contain a pointer to next free block 3.
Adv: No waste of space
 Disadvantage:
 Not efficient.
 To traverse the list ,
we must read each block.

Operating System Concepts – 8th Edition 10.85 Silberschatz, Galvin and Gagne ©2009
 Free-Space Management (Cont.)
3. Grouping:
A modification of the free list approach stores the address of n free blocks in
the first free block.
• The first n-1 of these blocks are actually free.
• Last block contains addresses of another n free blocks and so on.
• An advantage of this approach is that the addresses of a group of free disk
blocks can be found easily.
 Finding free blocks in massive amount can be done easily using this
method.
• Example: for example free are 10.
• Out of 10 free ,One block exclusively to maintain all 9 remaining free blocks.
• Total 10 free blocks
 Disadvantage:
 we need to alter the entire list, if any of the block of the list is occupied.

Operating System Concepts – 8th Edition 10.86 Silberschatz, Galvin and Gagne ©2009
  4. Counting –
 This approach stores the address of the first free disk block and a
number n of free contiguous disk blocks that follow the first block.
 Every entry in the free space list would contains
 Address of first free disk block.
 A number n.. (count)

 For example, in Figure-1, the first entry of the free space list would
be: ([Address of Block 5], 2), because 2 contiguous free blocks
follow block 5.

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