|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 990-991 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 990
SEC. 11.8
THE WINDOWS NT FILE SYSTEM
959
Standard
info header
File name
header
Data
header
Info about data blocks
Run #1
Run #2
Run #3
Standard
info
File name
0
9
20
4
64
2
80
3
Unused
Disk blocks
Blocks numbers
20-23
64-65
80-82
MTF
record
Record
header
Header
Figure 11-41.
An MFT record for a three-run, nine-block stream.
In this figure we have an MFT record for a short stream of nine blocks (header
0–8). It consists of the three runs of consecutive blocks on the disk.
The first run
is blocks 20–23, the second is blocks 64–65, and the third is blocks 80–82.
Each
of these runs is recorded in the MFT record as a (disk address, block count) pair.
How many runs there are depends on how well the disk block allocator did in find-
ing runs of consecutive blocks when the stream was created.
For an
n
-block
stream, the number of runs can be anything from 1 through
n
.
Several comments are worth making here.
First, there is no upper limit to the
size of streams that can be represented this way.
In the absence of address com-
pression, each pair requires two 64-bit numbers in the pair for a total of 16 bytes.
However, a pair could represent 1 million or more consecutive disk blocks.
In fact,
a 20-MB stream consisting of 20 separate runs of 1 million 1-KB blocks each fits
easily in one MFT record, whereas a 60-KB stream scattered into 60 isolated
blocks does not.
Second, while the straightforward way of representing each pair takes 2
×
8
bytes, a compression method is available to reduce the size of the pairs below 16.
Many disk addresses have multiple high-order zero-bytes.
These can be omitted.
The data header tells how many are omitted, that is, how many bytes are actually
used per address.
Other kinds of compression are also used.
In practice, the pairs
are often only 4 bytes.
Our first example was easy: all the file information fit in one MFT record.
What happens if the file is so large or highly fragmented that the block information
does not fit in one MFT record?
The answer is simple: use two or more MFT
records. In Fig. 11-42 we see a file whose base record is in MFT record 102.
It
has too many runs for one MFT record, so it computes how many extension
records it needs, say, two, and puts their indices in the base record.
The rest of the
record is used for the first
k
data runs.
Page 991
960
CASE STUDY 2: WINDOWS 8
CHAP. 11
109
108
106
105
103
102
100
Run #m+1
Run n
Run #k+1
Run m
MFT 105
Run #1
MFT 108
Run #k
Second extension record
First extension record
Base record
101
104
107
Figure 11-42.
A file that requires three MFT records to store all its runs.
Note that Fig. 11-42 contains some redundancy. In theory, it should not be
necessary to specify the end of a sequence of runs because this information can be
calculated from the run pairs.
The reason for ‘‘overspecifying’’ this information is
to make seeking more efficient: to find the block at a given file offset, it is neces-
sary to examine only the record headers, not the run pairs.
When all the space in record 102 has been used up, storage of the runs con-
tinues with MFT record 105.
As many runs are packed in this record as fit. When
this record is also full, the rest of the runs go in MFT record 108.
In this way,
many MFT records can be used to handle large fragmented files.
A problem arises if so many MFT records are needed that there is no room in
the base MFT to list all their indices.
There is also a solution to this problem: the
list of extension MFT records is made nonresident (i.e., stored in other disk blocks
instead of in the base MFT record).
Then it can grow as large as needed.
An MFT entry for a small directory is shown in Fig. 11-43. The record con-
tains a number of directory entries, each of which describes one file or directory.
Each entry has a fixed-length structure followed by a variable-length file name.
The fixed part contains the index of the MFT entry for the file, the length of the file
name, and a variety of other fields and flags.
Looking for an entry in a directory
consists of examining all the file names in turn.
Large directories use a different format.
Instead, of listing the files linearly, a
B+ tree is used to make alphabetical lookup possible and to make it easy to insert
new names in the directory in the proper place.
The NTFS parsing of the path
\ foo \ bar
begins at the root directory for
C:
,
whose blocks can be found from entry 5 in the MFT (see Fig. 11-39). The string
‘‘foo’’ is looked up in the root directory, which returns the index into the MFT for
the directory
foo
.
This directory is then searched for the string ‘‘bar’’, which refers
to the MFT record for this file. NTFS performs access checks by calling back into
the security reference monitor, and if everything is cool it searches the MFT record
for the attribute
::$DATA
, which is the default data stream.
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
