|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 334-335 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 334
SEC. 4.4
FILE-SYSTEM MANAGEMENT AND OPTIMIZATION
303
Keeping Track of Free Blocks
Once a block size has been chosen, the next issue is how to keep track of free
blocks. Two methods are widely used, as shown in Fig. 4-22. The first one con-
sists of using a linked list of disk blocks, with each block holding as many free
disk block numbers as will fit. With a 1-KB block and a 32-bit disk block number,
each block on the free list holds the numbers of 255 free blocks.
(One slot is re-
quired for the pointer to the next block.)
Consider a 1-TB disk, which has about 1
billion disk blocks.
To store all these addresses at 255 per block requires about 4
million blocks.
Generally, free blocks are used to hold the free list, so the storage
is essentially free.
(a)
(b)
Free disk blocks: 16, 17, 18
A bitmap
A 1-KB disk block can hold 256
32-bit disk block numbers
86
234
897
422
140
223
223
160
126
142
141
1001101101101100
0110110111110111
1010110110110110
0110110110111011
1110111011101111
1101101010001111
0000111011010111
1011101101101111
1100100011101111
0111011101110111
1101111101110111
230
162
612
342
214
160
664
216
320
180
482
42
136
210
97
41
63
21
48
262
310
516
Figure 4-22.
(a) Storing the free list on a linked list. (b) A bitmap.
The other free-space management technique is the bitmap.
A disk with
n
blocks requires a bitmap with
n
bits. Free blocks are represented by 1s in the map,
allocated blocks by 0s (or vice versa). For our example 1-TB disk, we need 1 bil-
lion bits for the map, which requires around 130,000 1-KB blocks to store.
It is
not surprising that the bitmap requires less space, since it uses 1 bit per block, vs.
32 bits in the linked-list model. Only if the disk is nearly full (i.e., has few free
blocks) will the linked-list scheme require fewer blocks than the bitmap.
If free blocks tend to come in long runs of consecutive blocks, the free-list sys-
tem can be modified to keep track of runs of blocks rather than single blocks.
An
8-, 16-, or 32-bit count could be associated with each block giving the number of
Page 335
304
FILE SYSTEMS
CHAP. 4
consecutive free blocks.
In the best case, a basically empty disk could be repres-
ented by two numbers: the address of the first free block followed by the count of
free blocks.
On the other hand, if the disk becomes severely fragmented, keeping
track of runs is less efficient than keeping track of individual blocks because not
only must the address be stored, but also the count.
This issue illustrates a problem operating system designers often have. There
are multiple data structures and algorithms that can be used to solve a problem, but
choosing the best one requires data that the designers do not have and will not have
until the system is deployed and heavily used. And even then, the data may not be
available. For example, our own measurements of file sizes at the VU in 1984 and
1995, the Website data, and the Cornell data are only four samples. While a lot bet-
ter than nothing, we have little idea if they are also representative of home com-
puters, corporate computers, government computers, and others. With some effort
we might have been able to get a couple of samples from other kinds of computers,
but even then it would be foolish to extrapolate to all computers of the kind meas-
ured.
Getting back to the free list method for a moment, only one block of pointers
need be kept in main memory. When a file is created, the needed blocks are taken
from the block of pointers.
When it runs out, a new block of pointers is read in
from the disk. Similarly, when a file is deleted, its blocks are freed and added to
the block of pointers in main memory. When this block fills up, it is written to
disk.
Under certain circumstances, this method leads to unnecessary disk I/O.
Con-
sider the situation of Fig. 4-23(a), in which the block of pointers in memory has
room for only two more entries.
If a three-block file is freed, the pointer block
overflows and has to be written to disk, leading to the situation of Fig. 4-23(b). If
a three-block file is now written, the full block of pointers has to be read in again,
taking us back to Fig. 4-23(a). If the three-block file just written was a temporary
file, when it is freed, another disk write is needed to write the full block of pointers
back to the disk.
In short, when the block of pointers is almost empty, a series of
short-lived temporary files can cause a lot of disk I/O.
An alternative approach that avoids most of this disk I/O is to split the full
block of pointers. Thus instead of going from Fig. 4-23(a) to Fig. 4-23(b), we go
from Fig. 4-23(a) to Fig. 4-23(c) when three blocks are freed. Now the system can
handle a series of temporary files without doing any disk I/O.
If the block in mem-
ory fills up, it is written to the disk, and the half-full block from the disk is read in.
The idea here is to keep most of the pointer blocks on disk full (to minimize disk
usage), but keep the one in memory about half full, so it can handle both file crea-
tion and file removal without disk I/O on the free list.
With a bitmap, it is also possible to keep just one block in memory, going to
disk for another only when it becomes completely full or empty.
An additional
benefit of this approach is that by doing all the allocation from a single block of the
bitmap, the disk blocks will be close together, thus minimizing disk-arm motion.
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
