|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 316-317 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 316
SEC. 4.3
FILE-SYSTEM IMPLEMENTATION
285
File A
Physical
block
Physical
block
4
0
7
2
10
12
File
block
0
File
block
1
File
block
2
File
block
3
File
block
4
File B
0
6
3
11
14
File
block
0
File
block
1
File
block
2
File
block
3
Figure 4-11.
Storing a file as a linked list of disk blocks.
Unlike contiguous allocation, every disk block can be used in this method.
No
space is lost to disk fragmentation (except for internal fragmentation in the last
block). Also, it is sufficient for the directory entry to merely store the disk address
of the first block. The rest can be found starting there.
On the other hand, although reading a file sequentially is straightforward, ran-
dom access is extremely slow. To get to block
n
, the operating system has to start
at the beginning and read the
n
−
1 blocks prior to it, one at a time. Clearly, doing
so many reads will be painfully slow.
Also, the amount of data storage in a block is no longer a power of two be-
cause the pointer takes up a few bytes. While not fatal, having a peculiar size is
less efficient because many programs read and write in blocks whose size is a pow-
er of two. With the first few bytes of each block occupied by a pointer to the next
block, reads of the full block size require acquiring and concatenating information
from two disk blocks, which generates extra overhead due to the copying.
Linked-List Allocation Using a Table in Memory
Both disadvantages of the linked-list allocation can be eliminated by taking the
pointer word from each disk block and putting it in a table in memory.
Figure 4-12
shows what the table looks like for the example of Fig. 4-11. In both figures, we
have two files. File
A
uses disk blocks 4, 7, 2, 10, and 12, in that order, and file
B
uses disk blocks 6, 3, 11, and 14, in that order. Using the table of Fig. 4-12, we can
start with block 4 and follow the chain all the way to the end. The same can be
done starting with block 6.
Both chains are terminated with a special marker (e.g.,
−
1) that is not a valid block number. Such a table in main memory is called a
FAT
(
File Allocation Table
).
Page 317
286
FILE SYSTEMS
CHAP. 4
Physical
block
File A starts here
File B starts here
Unused block
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10
11
7
3
2
12
14
-1
-1
Figure 4-12.
Linked-list allocation using a file-allocation table in main memory.
Using this organization, the entire block is available for data. Furthermore, ran-
dom access is much easier.
Although the chain must still be followed to find a
given offset within the file, the chain is entirely in memory, so it can be followed
without making any disk references. Like the previous method, it is sufficient for
the directory entry to keep a single integer (the starting block number) and still be
able to locate all the blocks, no matter how large the file is.
The primary disadvantage of this method is that the entire table must be in
memory all the time to make it work. With a 1-TB disk and a 1-KB block size, the
table needs 1 billion entries, one for each of the 1 billion disk blocks. Each entry
has to be a minimum of 3 bytes.
For speed in lookup, they should be 4 bytes. Thus
the table will take up 3 GB or 2.4 GB of main memory all the time, depending on
whether the system is optimized for space or time. Not wildly practical. Clearly the
FAT idea does not scale well to large disks.
It was the original MS-DOS file sys-
tem and is still fully supported by all versions of Windows though.
I-nodes
Our last method for keeping track of which blocks belong to which file is to
associate with each file a data structure called an
i-node
(
index-node
), which lists
the attributes and disk addresses of the file’s blocks. A simple example is depicted
in Fig. 4-13. Given the i-node, it is then possible to find all the blocks of the file.
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
