Page 235 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
Figure 6.12: Linked Free-Space List on Disk

Free-space list head
0 1 2 3
4 5 6 7

8 9 1 0 1 1
12 13 14 15
16 17 18 19
20 21 22 23

24 25 26 27
28 29 30 31

6.11.3 Grouping
A modification of the free-list approach is to store the addresses of n free blocks in the first free
block. The first n-1 of these blocks are actually free. The last block contains the addresses of
another n free blocks, and so on. The importance of this implementation is that the addresses of
a large number of free blocks can be found quickly, unlike in the standard linked-list approach.

6.11.4 Counting
Another approach is to take advantage of the fact that, generally, several contiguous blocks may
be allocated or freed simultaneously, particularly when space is allocated with the contiguous-
allocation algorithm or through clustering. Thus, rather than keeping a list of n free disk
addresses, we can keep the address of the first free block and the number n of free contiguous
blocks that follow the first block. Each entry in the free-space list then consists of a disk address
and a count. Although each entry requires more space than would a simple disk address, the
overall list will be shorter, as long as the count is generally greater than

6.12 Directory Implementation

To keep track of files, file systems normally have directories or folders, which, in many systems,
are themselves files. In this section, we will discuss directories, their organization, their properties,
and the operations that can be performed on them.

6.12.1 Simple Directories
A directory typically contains a number of entries, one per file. One possibility is shown in Fig.
6.13(a), in which each entry contains the file name, the file attributes, and the disk addresses
where the data are stored. Another possibility is shown in Fig. 6.13(b). Here a directory entry
holds the file name and a pointer to another data structure where the attributes and disk addresses
are found. Both of these systems are commonly used.

228 LOVELY PROFESSIONAL UNIVERSITY