Linux with Operating System Concepts

fragment
.
The operating system must be able to manage this distribution of files to blocks in three 
ways. First, given a file and block, the operating system must map that block number into a 
physical location on some disk surface. Second, the operating system must be able to direct 
the disk drive to access that particular block through a movement of both the disk and 
the drive’s read/write head. Third, the operating system must be able to maintain free file 
space (available blocks), including the return of file blocks once a file has been deleted. All 
of these operations are hidden from the user and system administrator.
3018
3020
3022
Block
0
File
Disk
block
locations
Block
1
Block
2
Block
3
Block
4
Block
5
5813
5815
683
FIGURE 10.1 
File decomposed into blocks. (Adapted from Fox, R. 
Information Technology: An 
Introduction for Today’s Digital World
,
 
FL: CRC Press, 2013.)

---

The Linux File System
◾
393
Let us consider how a disk file might be broken into blocks. We might assume that our file 
system already has hundreds or thousands of files stored in it. The files are distributed across 
all of the disk’s surfaces (recall from Chapter 3 that a hard disk drive will contain multiple 
disk platters and each platter has two surfaces, a top and bottom). Given a new file to store, 
the file is broken into blocks. The first block is placed at the first available free block on disk.
Where should the next disk block be placed? If the next block after the first is available, 
we could place the block there, giving us two blocks of contiguous storage. This may or 
may not be desirable. The disk drive spins the disks very rapidly. If we want to read two 
blocks, we read the first block and transfer it into a buffer in the disk drive. Then, that 
data are transferred to memory. However, during that transfer, the disk continues to spin. 
When we are ready to read the second disk block, it is likely that this block has spun past 
the read/write head and now the disk drive must wait to finish a full disk revolution before 
reading again. Distributing disk blocks so that they are not contiguous will get around this 
problem. If you examine Figure 10.1, you will see that the first three disk blocks are located 
near each other but not in a contiguous block. Instead, the first block lies at location 3018, 
the second at 3020, and the third at 3022.
Whether initial blocks are contiguous or distributed, we will find that further disk 
blocks may have to be placed elsewhere because we have reached the end of the available 
disk blocks in this locality. With the deletion of files and saving of other files, we will even-
tually find disk blocks of one file scattered around the disk surfaces. This may lead to some 
inefficiency in access in that we have to move from one location of the disk to another to 
read consecutive blocks and so the seek time and rotational latency are lengthened.
Again, referring back to Figure 10.1, we might assume that the next available block after 
3022 is at 5813 and so as the file continues to grow, its next block lies at 5813 followed by 
5815. As the next block, according to the figure, lies at 683, we might surmise that 683 was 
picked up as free space because a file was deleted.
10.2.2 Block Indexing Using a File Allocation Table
How do we locate a particular block of a disk? File systems use an 
indexing
scheme. MS 
DOS and earlier Windows systems used a 
file allocation table
(FAT). For every disk block 
in the file system, the next block’s location is stored in the table under the current block 
number. That is, block i’s successor location is stored at location i.
The FAT is loaded from disk into memory at the time the file system is mounted (e.g., at 
system initialization time). Now, a search of memory would track down a particular disk 
block’s location. For instance, if the file started at block 1500, we would look at FAT loca-
tion 1500 to find the file’s second block location. If it were 1505, we would look at 1505 to 
find the file’s third location, and so forth.
In Figure 10.2, a partial listing of a FAT is provided. Here, assume a file starts at block 
151. Its next block is 153 followed by 156, which is the end of the file (denoted by “EOF”). 
To find the file’s third block, the operating system will examine the FAT starting at loca-
tion 151 to find 153 (the file’s second block) and then look at location 153 to find 156, the 
file’s third block. Another file might start at block 154. Its third block is at location 732. The 
entry “Bad” indicates a bad sector that should not be used.

---

394
◾
Linux with Operating System Concepts
More recent versions of Windows operating systems use the NTFS file system (new 
technology file system), which utilizes a data structure called a B
+
tree for indexing. In 
Linux, indexing is handled through the inode data structure. We explore this in Section 
10.3 where you will see that every inode contains pointers to disk blocks that either store 
data or additional pointers.
10.2.3 Other Disk File Details
Aside from determining the indexing strategy and the use/reuse of blocks, the file system 
must also specify a number of other details. These will include naming schemes for file 
entries (files, directories, links). It is common today for names to permit just about any 
character, including blank spaces; however, older file systems had limitations such as eight-
character names and names consisting only of letters and digits (and perhaps a few types 
of punctuation marks such as the hyphen, underscore, and period). Some file systems do 
not differentiate between uppercase and lowercase characters while others do. Most file 
systems permit but do not require file name extensions.
File systems will also maintain information about the entries, often called metadata. 
This will include the creation date/time, last modification date/time and last access date/
time, owner (and group in many cases), and permissions or access control list. The access 
control list enumerates for each user of the system the permissions granted to that user so 
that there can be several levels of permissions over the Linux user/group/other approach.
Many different file system types have been developed over the years. Many early main-
frames had their own, unique file systems. Today, operating systems tend to share file sys-
tems or provide compatibility so that a different file system can still be accessed by many 
different types of operating systems. Aside from the previously mentioned FAT and NTFS 
file systems, some of the more common file systems are the extended file system family 
(ext, ext2, ext3, ext4, derived originally from the Minix OS file system) used in Linux. NFS 
(the network file system) is also available in Linux. Files-11, which is a descendant of the 
file system developed for DEC PDP mainframes, and the Vax VMS operating system (and 
itself a precursor of NTFS) are also available. While these multitudes of file systems are 
available, most Linux systems primarily use the ext family as the default file system type.
10.3 FILES
In the Linux operating system, everything is treated as a file except for the process. 
What does this mean? Among other things, Linux file commands can be issued on enti-
ties that are not traditional files. The entities treated like files include directories, physi-
cal devices, named pipes, and file system links. Aside from physical devices, there are also 
150
381
153
Bad
156
155
732
EOF
Block
Next location
151
File allocation table (portion)
152
153
154
155
156
FIGURE 10.2 
Excerpt of a file allocation table. (Adapted from Fox, R.