Control or enable specific properties of the file.
Read-only flag:
0 for read/write, 1 for read-only.
Hidden flag:
Hides a file in listings (set to hide).
System flag:
Designates a file as a system file (set for system file).
Archive flag:
Tracks whether the file has been backed up (OS sets when changed, set to 0 when backed up).
Access flag:
* Conveys how the file is accessed.
* It is set when the file is accessed randomly, otherwise, the file is accessed sequentially.
Time of Last Change and Last Access
Information about when the file was last modified and accessed.
FILE OPERATIONS
Because a file is of an abstract data type, the kind of operations that can be performed on it must be known.
The OS provides system calls for each operation to be implemented on the file.
The following are some operations that are performed on a file:
Create a file:
OS looks for space and sets related attributes.
Write a file:
Needs file name and data.
OS uses a current position pointer.
Increases file size if at the end, overwrites contents if in between.
Close a file:
Frees memory space for attributes and disk addresses.
Updates the file on the disk.
Does not delete the file.
Limits the number of files a process can open.
Read a file:
Needs file name and pointer position.
Updates the pointer after reading data.
Saving a file:
Contents of the file must be saved on the disk.
OS looks for space on the disk, and then save it.
The appropriate entry in the directory, where the file is created, is also done.
Deleting a file:
Frees space and removes the directory entry.
Open a file:
Fetches attributes and disk addresses into main memory for rapid access.
Append a file:
Write operation performed only at the end of the file.
The OS locates the end of the file, using the pointer, and then appends the data to be written in the file.
Repositioning the current position pointer:
The current position pointer used to read and write in the file can be repositioned to any desired position.
The general system call for this operation is seek in some OSs. Therefore, it is also known as seek operation.
Get/Set attributes:
The attributes of a file can be read, or even changed by a user, if necessary. A user may need to look when the file was last changed or created. Similarly, the user might want to change the access permission of a file. The system calls of an OS help to get/set the attributes of a file.
Implementation of File Operations
Basics are discussed.
To perform any operation on a file, the file needs to be opened.
The following data structures are used for opened files:
Open File Table (OFT):
The OS uses a data structure known as open file table (OFT), to keep the information of an opened file, as the open operation fetches the attributes of the file to be opened.
When an operation needs to be performed on the file, it is specified via an index into this table, and therefore, it need not be searched in its directory entry every time.
Maintained per process basis, that is, it maintains the detail of every file opened by a process.
Stores the attributes of the opened file.
Helps in an environment where several processes open files simultaneously.
Maintains an open_count counter that tracks opened files (incremented on open, decremented on close).
System-wide Open File Table (SOFT):
Another data structure, which is used to maintain the status of open files, but on the system basis rather than the process.
An entry in the OFT points to a SOFT, where the process- independent information about the open file is maintained, for example, location of a file on the disk, file size, and so on.
Once a process opens a file, the file gets entry in both OFT and SOFT.
Address of the File on Disk:
The address of the file, where it resides on the disk, may be needed every time the file is opened. Therefore, to avoid reading the address from the disk again and again, its address is kept in the memory.
Sequential File Access
Files stored on disk need to be retrieved.
Access depends on blocking strategy and logical structuring of records.
Sequential File Access:
Information is accessed in the order it is stored.
A simple and commonly-used access method.
Possible only with fixed-length records consisting of a fixed set of fields in a particular order.
A key field, usually the first field in the record, by which the sequential order is maintained.
A file pointer is maintained.
When read/write occurs, the file pointer advances to the next position.
The pointer can be reset to the beginning by assigning zero value to it.
Suited for batch processing, not ideal for interactive applications.
The sequential file is best suited to sequential access devices, like tapes.
Needs proper match of the key field in every record, resulting in considerable processing time and delay, especially when the size of a sequential file is large.
Indexed Sequential File Access
Records are organized in a sequence, based on a key field.
A random access approach is followed by incorporating an index like the sequential file access.
The index stores the key field and a pointer on the main file.
To find a specific field, the index is searched for the highest key value, equal to or less than the desired value.
The search is continued in the main file, after getting the pointer from the index.
The index takes the pointer to the vicinity of a desired record, and reduces the number of lookups in the main file.
The average search length may be reduced from millions to thousands.
The advantage of the indexed sequential access is that the sequential nature of a file is not modified.
The file stored is still sequential, and by this access method, the time to search a record is greatly reduced.
If the index file is too large for the main file, it will be better to have a second-level index file. The second-level index will have pointers to the first level index, and the first level index will have pointers to the actual record in the main file.
File Access Example
File of student records, 16 bytes each, on a disk with 512-byte blocks (32 records per block).
A file of 80,000 records would occupy 2,500 blocks.
Sequential access retrieval requires searching thousands of records.
Index alternative: last name (10 bytes) + logical record number.
Index sorted by last name.
Index search provides the file pointer to the required block, which is then searched sequentially.
Indexed File Access
It is not necessary to store the data in a file sequentially and to search a record by its key field.
There may be other attributes by which a user wants to find a record.
Sequential nature and single key field not required.
Multiple indexes, each for an attribute, are prepared.
No restriction of placing the records in sequence and they can be of variable lengths as well.
Types of Indexes
Exhaustive Index:
One entry for every record in the main file.
Partial Index:
Entries of the records indexed by a particular attribute.
Direct File Access
Meant for random structure of secondary storage, like in disks.
Suitable for disks to access a particular record randomly.
Not necessary to store and access records in sequence.
Records must be of fixed-length.
The key field may also be the block number.
Block can be accessed directly using its number.
Suitable for applications requiring rapid access to data from a large information pool.
DIRECTORIES
Used to maintain the structure of a file system.
A user, if working in a flat file system, may not be able to sort different tasks. One task may have 10 files, but all scattered in the file system; similarly, other tasks may have multiple files, but cannot be grouped together.
Files related to a category or task are grouped.
Tasks are put in related task groups.
These groups are known as directories or folders.
A directory is also a file that lists all the files stored in it.
The listing displays various attributes that may vary from system to system. The general attributes displayed may be name of the file, its location, its access rights, its date and time of creation, and so on.
Provides different groups, according to the tasks, are obtained.
DIRECTORIES
Directories are convenient for users, as they can separate their work into different directories, related to different tasks.
For example, if a student works on two projects, A and B, then he/she can make separate directories for Project A and Project B, such that the files related to a project will only be stored in the related directory.
The directories also give flexibility such that files can have same names in different directories. Thus, the name of every file need not be unique. In a folder, however, every file must have a unique name.
The same name facility in different directories is implemented by having a master directory associated with the file system. The master file directory stores the pointer to every directory the user has made. For example, Project A and Project B are two different directories of a user. He can give same name, say Init, to the files in both directories. In this case, the file system will use master directory, storing the pointers of both directories.
There is no conflict in the name Init, because when the desired file is referred to, the file system will search the pointer in its corresponding directory.
Logical structuring of directories can be done in many ways, according to the requirements of a user.
Single Level Directory Structure
A single level structure under which all the files will be stored.
There is a single directory in the system, known as root director, and all the files are stored only under this directory
Searching a file is easy.
This kind of structure was used in earlier systems when there was no concept of multi-users.
A single- level directory, therefore, is not suitable for multi-user systems, because of duplicate naming of file.
If a user by mistake takes the same name of an existing file, it will be overwritten, and the old contents of the file are lost forever.
If a user writes programs in many languages, it is not possible to have separate directories for each language in a single level directory structure.
This structure is not used in modern systems. It may be applicable in the system where the number of files is less, as in case of an embedded system.
Two Level Directory Structure
The disadvantage of duplicating file names by different users in a single-level directory gives rise to the idea of having separate directories for each user, or for each task.
In the two- level directory, there are two levels: master directory and user directory
The master directory stores the user ID and its address. The user directory is simply a list of files, as seen in a single-level.
When a user starts, the system’s master directory is searched for the entries of this user, through user name or account number.
After searching the appropriate entry, the address of its user directory is retrieved.
When a user refers to a particular file, its own user directory is searched in the master directory.
Different users may have files with the same name in their respective directories.
The addition and deletion of a file also requires searching of the file in the user directory, therefore, a file with the same name in other user directories cannot be deleted.
Hierarchical or Tree Structure Directory
In a two-level directory structure, a user is limited to have a single personal directory.
An extended design of two-level structure allows a user to have sub-directories, so that the work can be divided among these sub-directories.
A directory, where there is no limit on subdirectories of a single user, is known as a tree-structure directory.
A large set of files can be further divided, and then grouped into sub-directories
In the tree-structure directory, there is a root or master directory, consisting of user directories.
Each user directory can be further divided into sub-directories, or it may have files.
A directory has both sub-directories and files.
The primary advantage of this structure is that a user can access another user’s files.
This facility is provided by a pathname.
A pathname is a sequence of one or more path components in the tree structure that uniquely identifies a file.
The pathnames, thus, can be used to access another user’s file and to uniquely identify files with same names in different directories.
Paths
There are two types of paths in a tree structure: absolute path and relative path.
An absolute path is a path that always starts from the root directory, and follows the path descending to the specified file in a particular directory.
To define a relative path, first let us define a term known as current directory or working directory.
A current directory is a directory, where a process or user normally works.
Any file specified by a user is first searched in its current directory.
If the user wishes to access a file, which is not in the current directory, then a path must be provided to access it.
The path provided may be relative to the current directory, that is, the path starts from the current directory, instead of the root. This is known as a relative path.
The relative path does not work every time.
A user may be at his/her current directory, such that the file to be accessed cannot be specified, using a relative path. In this case, the path of the file to be accessed must be specified using an absolute path.
Absolute path always works, because it is an unambiguous way of referring to a file in the tree-hierarchy.
A user, however, may feel inconvenient to specify the absolute path every time, if the number of files to be accessed is more. In this case, the user may change the current directory explicitly and specify the relative path.
Whenever a process or user changes its current directory, it must know its location in the tree structure of the file system.
Example of Paths
The tree-directory structure, shown above, consists of files having identical names. But the files can be easily accessed using pathnames. Both user A and user C consist of a file named ‘Btree’.
The files, however, can be distinguished and accessed using the following path names:
UserA/CPP/G2/Chap1/Btree
UserC/CPP/UnitA/Btree
Since the pathnames are unique to both files, the same name is allowed in the tree structure.
If the working directory of a user is G2 and the user wants to access any file in the hierarchical structure below it, then an absolute path need not be specified. The relative path, Chap1/Btree, is sufficient to access the Btree file.
Acyclic Graph Structure
The tree structure does not allow the sharing of a file or directory among various user directories. It means two users cannot have a same file or sub-directory in their directories.
Consider two programmers who are working on the same project. They may want to share a file or sub-directory required for the project. Thus, the directory structure must allow sharing of files or sub- directories.
Sharing means having the same file or sub-directory in the directory of the concerned user directories. In other words, if there is a change in the contents of a shared file, then it must be visible to all the shared users, because there is only one copy of the shared file. The implementation of this type of sharing in the directory structure violates the tree structure.
This type of structure is not a tree structure, but a graph. It is known as an acyclic graph.
An acyclic graph structure is implemented through a pointer, known as a link. A link is a pointer that points to a file or directory.
If a directory entry is marked as a link, the real file information is in the link.
The link is implemented as a pathname of the shared file. Thus, when a file is needed, the directory entry is searched.
If the directory is found as a link, then the link is resolved to have the access of the real file. This is known as a symbolic link or soft link.
In UNIX, file-sharing is done with the help of link and unlink commands.
The link system call is specified with two parameters: the existing file name and the pathname as a link. It creates a link between the existing file and the file specified in the link.
Similarly, an unlink system call is used to remove the link between two files. However, unlink does not affect the shared file in any way. It just removes the symbolic link between the files.
Symbolic links can also be used to link to files on any machine in the network, by providing the network address and pathname of the machine.
Symbolic Linking Problems
A file may have multiple absolute paths referring to the same file.
Problems when traversing the structure for tasks like backup:
Results in duplicate copies of the same file.
Symbolic links incur extra overhead:
Time and disk space (extra disk accesses and space are required).
Requires reading and parsing the path in link, and following the path step by step.
Hard Link:
Contrary to soft links, a directory entry may have an entry that specifies the location of a file on the storage device. In this case, the file is accessed by directly accessing the physical blocks that are being referenced to. This is known as a hard link.
Needs to be updated whenever there is a change in physical addresses on the disk.
File Sharing Types
Sequential Sharing:
Allows multiple users but one by one in a sequence.
Implemented with a file-locking system restricting access to one user at a time.
Concurrent Sharing:
Allows multiple users to share a file over the same period of time.
FileSystems may prohibit file sharing, allow access to all users, or define access rights for each user. The above represents two extremes of file protection. Instead of having total prohibition or full flexibility of access, access rights must be defined for each user.
Types of Users
Individual user/owner:
An individual user or the owner of a file, who created the file.
User group:
A set of users who share a file and require same type of access.
All:
Any user who has access to the file system.
Access Rights
Reading:
The user can read the file.
Writing:
The user can write, modify, and delete any content of the file.
Appending:
The user is able to write at the end of the file only.
Deleting:
The user can delete the file from the system.
Execution:
The user can load and execute a program, but cannot copy it.
Listing:
The user is able to display the name and attributes of the file.
Security
Different users need different access rights.
An Access Control List (ACL) specifies access rights associated with a file.
When a user requests access, the OS checks the ACL.
Access is allowed if the request and ACL match.
Otherwise, the access is denied.
ACL disadvantage: length of ACL associated with the file.
General access can be given by default with restricted accesses through ACL.
Moreover, access rights can be combined with each type of user, resulting in a standard scheme for access protection. This will result in more restricted protection, having only three fields of protection.
Each field may be of several bits, representing access protection.
For example, in UNIX, there are three fields: owner, group, and all. Each field has three bits, specifying read, write, and execute access permissions. Thus, only 9 bits are required per file.
File Sharing Example
A leader of a group on a project wants all group members to be able to read and write, but not delete data on the project directory. Other users may be allowed only to read the files under the project directory.
Besides this, the project leader should have all access rights.
FILE SYSTEM MOUNTING
There are several types of storage devices like CD-ROMs, hard disks, USB storage and so on. Hard disks may have several partitions as well.
On the other hand, in case of a Linux or UNIX OS, the CD or hard disk partitions cannot be accessed. The reason is that the user needs to mount all the devices or hard disk partitions explicitly, whereas in Windows, the OS does the mounting of all attached devices and partitions of the hard.
Before they can be used, every storage device/partition must be attached to the root directory of the system.
This attaching of the device is known as mounting, and the directory where the device is attached, is known as a mount point.
Similarly, unmounting is done to remove the device from the mount point.
To mount a device, the OS requires the name of the device and the mount point.
The OS then reads the device directory and verifies that the directory has a valid filesystem. After this, it records the entry of a new device directory in its directory structure at the desired mount point.
File System Implementation
The file system accepts the user request for any disk I/O and sends it to the device through various intermediate layers.
Various data structures are used on disk as well as in the memory for implementation of the file system.
The implementation details of various file-related operations and how the files are allocated on the disk are discussed in this chapter.
Besides this, some issues regarding the file system, such as backup and recovery of critical data, file system inconsistencies, and some performance issues have also been discussed.
File System Structure
The file system is structured in various layers to incorporate various operations.
Each layer uses the operation of its lower layer.
Logical File System
The logical file system is concerned with the logical structure of the file.
This module manages all the information about file attributes.
The file structure is maintained in a data structure generally known as a file control block (FCB).
This layer manages the directory structure where a file is located and provides information about the file location to the file organization module.
File Organization Module
This module knows about the logical blocks of the file and translates them to physical blocks so that the basic file system gets the physical blocks and proceeds further.
For this translation, it needs to know the location of the file and its allocation type.
The file is allocated the disk space in some specified manner known as file allocation methods, which will be discussed later in this chapter.
Further, it also must know which blocks are free. This information is provided by the free space manager that tracks unallocated blocks and provides them to the file organization module so that the translation of logical blocks can be performed.
Basic File System/Physical Input–Output Level
The basic file system issues the generic commands to the device drivers of the corresponding devices to read and write physical blocks.
The physical blocks are identified with their disk addresses.
The blocks are first allocated in a buffer.
When there is an I/O request, the blocks are transferred either to the disk or the memory and buffer becomes free.
The buffer management is also done at this level.
Input–Output Control
This is the lowest level in the layered design of the file system.
This module communicates with the actual device (disk or tape drive), starts operation on the device, and processes the I/O request.
It consists of device drivers and interrupt handlers to transfer information between the main memory and the device.
The benefit of layered structure of a file system is that the code of one layer can be used by different file systems.
For example, the basic file system or I/O control module can be reused by various file systems.
The number of layers should be decided wisely. If it is large, then there is a possibility of decreased performance. Thus, the number of layers may affect the performance of an OS.
File System Structure Implementation
The file system implementation involves various data structures to manage its data and meta-data. Since the secondary storage used for the file system implementation is generally a disk, some of these data structures are on-disk or in-memory. The on-disk data structures are organized by dividing the disk into blocks of some size.
Most of the disk space, that is, the blocks are reserved for storing the data. These blocks are known as data blocks. Some of the blocks are reserved for on-disk data structures.
The general on-disk data structures are discussed as follows:
On-Disk Data Structures
Boot block:
Every partition on the disk starts with the boot block.
The program in the boot block loads the OS in that partition.
File control block (FCB):
Required to track information such as which data blocks comprise a file, and the file’s size, owner, access rights, date of creation, access or modification, and so on.
All this information is stored in FCB, which is an array of data structures per file.
It is also known as Inode (Index node). It contains all the accounting information and the information to locate all the disk blocks that hold the file’s data.
Super block/volume control block:
It stores the key information about the file system on every partition (or volume) of the disk, which is read into memory after the system is booted, protecting the integrity of the file