244766935qqcom • 2020-12-22 14:46:20

<header class="entry-header">
<h1 class="entry-title">2018329621184 边凯昂</h1>
<h1 class="entry-title">File Allocation Methods</h1>
<time title="Monday, September 10th, 2018 1:11:16 PM" datetime="2018-09-10T13:11:16+00:00">Last Updated: 10-09-2018</time></header>
<div class="entry-content">
<div></div>
The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.
<ul>
<li>Contiguous Allocation</li>
<li>Linked Allocation</li>
<li>Indexed Allocation</li>
</ul>
The main idea behind these methods is to provide:
<ul>
<li>Efficient disk space utilization.</li>
<li>Fast access to the file blocks.</li>
</ul>
All the three methods have their own advantages and disadvantages as discussed below:

<strong>1. Contiguous Allocation</strong>

In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be:<em> b, b+1, b+2,……b+n-1.</em> This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
<ul>
<li>Address of starting block</li>
<li>Length of the allocated portion.</li>
</ul>
The<em> file ‘mail’</em> in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies <em>19, 20, 21, 22, 23, 24</em> blocks.

<a href="https://media.geeksforgeeks.org/wp-content/uploads/Contiguous-Allocation.jpg"><img class="alignnone size-medium wp-image-174514" title="Click to enlarge" src="https://media.geeksforgeeks.org/wp-content/uploads/Contiguous-Allocation.jpg" alt="pic" width="450" height="350" /></a>
<strong>Advantages:</strong>
<ul>
<li>Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file which starts at block b can easily be obtained as (b+k).</li>
<li>This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.</li>
</ul>
<div id="AP_G4GR_5">
<div id="c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" class="_ap_apex_ad" data-section="c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" data-xpath="#AP_G4GR_5" data-section-id="" data-render-time="1608619783833" data-ap-network="adpTags" data-refresh-time="1608619828294" data-timeout="1713">
<div id="ADP_40792_728X280_c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" data-google-query-id="CMCNwOz_4O0CFVpAwgUdN0sEwQ">
<div id="google_ads_iframe_/103512698/21930050872_0__container__"><if rame id="google_ads_iframe_/103512698/21930050872_0" title="3rd party ad content" name="google_ads_iframe_/103512698/21930050872_0" width="336" height="280" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" sandbox="allow-forms allow-popups allow-popups-to-escape-sandbox allow-same-origin allow-scr ipts allow-top-navigation-by-user-activation" data-google-container-id="a" data-load-complete="true" data-mce-fragment="1"></iframe></div>
</div>
</div>
</div>
<strong>Disadvantages:</strong>
<ul>
<li>This method suffers from both internal and external fragmentation. This makes it inefficient in terms of memory utilization.</li>
<li>Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.</li>
</ul>
<strong>2. Linked List Allocation</strong>

In this scheme, each file is a linked list of disk blocks which<strong> need not be </strong>contiguous. The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next block occupied by the file.

<em>The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25) contains -1 indicating a null pointer and does not point to any other block.</em>
<a href="https://media.geeksforgeeks.org/wp-content/uploads/linkedListAllocation.jpg"><img class="alignnone size-medium wp-image-174517" title="Click to enlarge" src="https://media.geeksforgeeks.org/wp-content/uploads/linkedListAllocation.jpg" alt="linked" width="450" height="350" /></a>

<strong>Advantages:</strong>
<ul>
<li>This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a contiguous chunk of memory.</li>
<li>This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.</li>
<li>It does not support random or direct access. We can not directly access the blocks of a file. A block k of a file can be accessed by traversing k blocks sequentially (sequential access ) from the starting block of the file via block pointers.</li>
<li>Pointers required in the linked allocation incur some extra overhead.</li>
</ul>
<strong>3. Indexed Allocation</strong>

In this scheme, a special block known as the <strong>Index block</strong> contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block as shown in the image:

<a href="https://media.geeksforgeeks.org/wp-content/uploads/indexedAllocation.jpg"><img class="alignnone size-medium wp-image-174515" title="Click to enlarge" src="https://media.geeksforgeeks.org/wp-content/uploads/indexedAllocation.jpg" alt="indexed" width="450" height="350" /></a>
<strong>Advantages:</strong>
<ul>
<li>This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.</li>
<li>It overcomes the problem of external fragmentation.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>The pointer overhead for indexed allocation is greater than linked allocation.</li>
<li>For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep one entire block (index block) for the pointers which is inefficient in terms of memory utilization. However, in linked allocation we lose the space of only 1 pointer per block.</li>
</ul>
</div> PostVer 0

804824950qqcom • 2020-12-22 15:02:43

There are two methods: linear list and hash table. It should be noted that the realization of the directory is for searching. Therefore, the realization of linear list corresponds to linear search, and the realization of hash table corresponds to hash search.

1. Linear list

The simplest way to implement a directory is to use a linear table that stores file names and data block pointers. When creating a new file, you must first search the directory table to make sure that no file with the same name exists, and then add one to the directory table

Directory item. To delete a file, search the directory table according to the given file name, and then release the space allocated to it. There are many ways to reuse a catalog item: you can mark the catalog item as no longer used, or add it to

On the free directory entry table, the last entry in the directory table can also be copied to a free location, and the length of the directory table can be reduced. Using a linked list structure can reduce the time to delete files. Its advantage lies in simple implementation,

However, due to the particularity of linear tables, it is time-consuming.

2.Hash table

The hash table gets a value based on the file name and returns a pointer to the element in the linear list. The advantage of this method is that the search is very fast, and the insertion and deletion are relatively simple, but some preparatory measures are required to

avoid confict. The biggest difficulty is the fixed degree of the hash table and the dependence of the hash function on the table length.

Directory query is done through repeated searches on the disk, which requires constant I/O operations, which is expensive. So as mentioned earlier, in order to reduce I/O operations, copy the currently used file directory to the memory,

When you want to use the file in the future, you only need to operate in the memory, thereby reducing the number of disk operations and improving the system speed. PostVer 0

2031115154qqcom • 2020-12-22 15:26:52

An allocation method refers to how disk blocks are allocated for files so that disk space is utilized effectively and files can be accessed quickly.There are 3 main allocation methods called Contiguous allocation, Linked allocation and Indexed allocation respectively.

&nbsp;

Contiguous allocation means that each file occupies a set of contiguous blocks on the disk. In generally, it is simple and directory entry only need starting location(block #) and length(number of blocks). Its advantages include that Contiguous allocation support both random and sequential access, and because of short head movement, it has fast access speed. But it will lead to the existence of external fragment(wasteful of space). And the other more serious disvantage is that if using this allocation methos, the files can not extend or file size must be known in advance.

&nbsp;

Linked allocation means that each file is a linked list of disk blocks and the blocks may be scattered anywhere on the disk. The directory entry would record the first block number and last block number. Using this allocation method, there will not have wasteful space. And it is also simple, because only need to know starting address. Its disadvantages are 1)link pointers need disk space and must access files in sequence (no random access).

&nbsp;

Indexed allocation brings all pointers together into the index block. Each file has its own index block, and index block address is stored in directory entry. Advantage:1)can actualize random access; 2)can actualize dynamic access without external fragmentation. Disadvantage:1)as link pointers, index block also need overhead; 2)because one index block can contains limited pointers, the size of file is also limitted. PostVer 0

997371991qqcom • 2020-12-22 15:51:36

There are three main disk space or file allocation methods.
<ul>
<li>Contiguous Allocation</li>
<li>Linked Allocation</li>
<li>Indexed Allocation</li>
</ul>
<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/FF3477CA-A6C7-4A76-B2A1-2D91B704A68C.jpeg"><img class="alignnone size-medium wp-image-9210" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/FF3477CA-A6C7-4A76-B2A1-2D91B704A68C-300x276.jpeg" alt="" width="300" height="276" /></a> <a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/F80BC7EE-52DD-4D95-8A2B-DC108DF5852C.jpeg"><img class="alignnone size-medium wp-image-9211" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/F80BC7EE-52DD-4D95-8A2B-DC108DF5852C-300x140.jpeg" alt="" width="300" height="140" /></a> <a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/B3653462-0426-4349-9F11-9F801C11D991.jpeg"><img class="alignnone size-medium wp-image-9212" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/B3653462-0426-4349-9F11-9F801C11D991-300x140.jpeg" alt="" width="300" height="140" /></a>

<!--more--> PostVer 0

653968106qqcom • 2020-12-23 11:23:24

徐天然2018329621008
There are mainly three methods of file allocation in the disk. Each method has its advantages and disadvantages. Mainly a system uses one method for all files within the system.
1. Contiguous allocation
2. Linked allocation
3. Indexed allocation
The main idea behind contiguous allocation methods is to provide
· Efficient disk space utilization
· Fast access to the file blocks

1. Contiguous allocation
Advantages:
· In the contiguous allocation, sequential and direct access both are supported.
· For the direct access, the starting address of the kth block is given and further blocks are obtained by b+K,
· This is very fast and the number of seeks is minimal in the contiguous allocation method.
Disadvantages:
· Contiguous allocation method suffers internal as well as external fragmentation.
· In terms of memory utilization, this method is inefficient.
· It is difficult to increase the file size because it depends on the availability of contiguous memory.


2. Linked allocation
Advantages:
· In terms of the file size, this scheme is very flexible.
· We can easily increase or decrease the file size and system does not worry about the contiguous chunks of memory.
· This method free from external fragmentation this makes it better in terms of memory utilization.

Disadvantages:
· In this scheme, there is large no of seeks because the file blocks are randomly distributed on disk.
· Linked allocation is comparatively slower than contiguous allocation.
· Random or direct access is not supported by this scheme we cannot access the blocks directly.
· The pointer is extra overhead on the system due to the linked list.

3. Indexed allocation
Advantages:
· This scheme supports random access of the file.
· This scheme provides fast access to the file blocks.
· This scheme is free from the problem of external fragmentation.

Disadvantages:
· The pointer head is relatively greater than the linked allocation of the file.
· Indexed allocation suffers from the wasted space.
· For the large size file, it is very difficult for single index block to hold all the pointers.
· For very small files say files that expend only 2-3 blocks the indexed allocation would keep on the entire block for the pointers which is insufficient in terms of memory utilization. PostVer 0

1720650158qqcom • 2020-12-23 11:39:46

File allocation mode

File allocation corresponds to the physical structure of the file and refers to how disk blocks are allocated to the file. <em><strong>There are three common methods of disk space allocation: continuous allocation, link allocation and index allocation.</strong> </em>Some systems (such as RD0S operating system) support all three methods, but it is more common for a system to support only one method.

<strong>1) Continuous distribution.</strong>

The sequential allocation method requires each file to occupy a contiguous set of blocks on disk, as shown in Figure 4-12. A disk address defines a linear sort on disk. This sort minimizes the number of seek and seek times required for the job to access the disk.

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/d-12-连续分配.png"><img class="alignnone size-medium wp-image-9214" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/d-12-连续分配-300x218.png" alt="" width="300" height="218" /></a>

<strong>2) Link allocation.</strong>

Link allocation<em> is a discrete allocation method, which eliminates external fragmentation and thus significantly improves the utilization of disk space. And because it is based on the current requirements of the file, it is necessary to allocate the disk block, when the file dynamic growth, it can dynamically re-allocate the disk block, so there is no need to know the size of the file in advance.</em> In addition, it is also very convenient to add, delete and change files. Link allocation can be divided into two forms: <strong>implicit link and explicit link.</strong>

The implicit connection is shown in Figure 4-13. Each file corresponds to a linked list of disk blocks; Disk blocks are distributed everywhere on the disk, and each disk block has a pointer to the next disk block except for the last one, which is transparent to the user. The directory contains a pointer to the first block of the file and a pointer to the last block.

When a new file is created, a new entry is added to the directory. Each directory entry has a pointer to the first block of the file. The pointer is initialized to NULL to represent an empty file with a size field of 0. The write file finds the empty block through the free space management system and links the block to the end of the file for writing. A file is read in a block-to-block pointer.

The disadvantage of implicit link allocation is that the blocks cannot be accessed directly, the files can only be accessed sequentially through the pointer, and the pointer consumes some storage space. The stability of implicit link allocation is also a problem. During the operation of the system, the pointer in the linked list is lost or damaged due to software or hardware errors, which will lead to the loss of file data.

The sequential allocation of files can be defined by the disk address of the first block and the number of contiguous blocks. If the file is n blocks long and starts at location B, then the file will occupy blocks B, B +1, B +2... , b + n - 1. The directory entry for a file includes the address of the start block and the length of the area allocated by the file.

Sequential allocation supports sequential and direct access. Its <strong>advantage</strong> is to implement simple, fast access speed. The <strong>disadvantage</strong> is that it is not appropriate to increase the file length dynamically, because the disks at the end of one file may have been allocated to other files, and if they need to be increased, they will need to be moved a lot. In addition, the repeated addition and deletion of files results in external fragmentation (similar to the fragmentation in memory management allocation), and it is difficult to determine the size of space required for a file, so it only applies to files of fixed length.

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/d-12-链式分配.png"><img class="alignnone size-medium wp-image-9215" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/d-12-链式分配-300x231.png" alt="" width="300" height="231" /></a>

<strong>3) Index allocation</strong>

Link allocation solves the problem of contiguous allocation of external fragmentation and file size management. However, link allocation does not effectively support direct access (except FAT). Index allocation solves this problem by putting all the block numbers of each file together to form an index block (table).

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/d-12-索引分配.png"><img class="alignnone size-medium wp-image-9216" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/d-12-索引分配-300x237.png" alt="" width="300" height="237" /></a>

Each file has its index block, which is an array of disk block addresses. The ith entry in the index block points to the ith block of the file. The directory entry includes the address of the index block. To read the ith block, look up and read in the desired block using a pointer to the ith entry in the index block.

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/三种分配方式的比较.png"><img class="alignnone size-medium wp-image-9217" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/三种分配方式的比较-300x86.png" alt="" width="300" height="86" /></a> PostVer 0

1730854984qqcom • 2020-12-23 22:13:43

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/1-5.jpg"><img class="alignnone size-medium wp-image-9222" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/1-5-300x255.jpg" alt="" width="300" height="255" /></a><a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/2-5.jpg"><img class="alignnone size-medium wp-image-9223" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/2-5-300x268.jpg" alt="" width="300" height="268" /></a><a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/3-1.jpg"><img class="alignnone size-medium wp-image-9224" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/3-1-300x282.jpg" alt="" width="300" height="282" /></a> PostVer 0

cfeshete97gmailcom • 2020-12-24 04:16:10

&nbsp;

Name: FESHETE CHARLES DE-GAULLE 2018529627022

&nbsp;

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/1-2.png"><img class="alignnone size-medium wp-image-9232" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/1-2-228x300.png" alt="" width="228" height="300" /></a>

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/2.png"><img class="alignnone size-medium wp-image-9233" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/2-300x161.png" alt="" width="300" height="161" /></a>

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/3.png"><img class="alignnone size-medium wp-image-9234" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/3-223x300.png" alt="" width="223" height="300" /></a>

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/4.png"><img class="alignnone size-medium wp-image-9235" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/4-300x185.png" alt="" width="300" height="185" /></a>

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/5.png"><img class="alignnone size-medium wp-image-9236" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/5-217x300.png" alt="" width="217" height="300" /></a>

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/6.png"><img class="alignnone size-medium wp-image-9237" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/6-300x202.png" alt="" width="300" height="202" /></a> PostVer 0

wx287_oz26ft1wt2_isbggtha4lgepaasa • 2020-12-24 15:19:52

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.
<ul>
<li>Contiguous Allocation</li>
<li>Linked Allocation</li>
<li>Indexed Allocation</li>
</ul>
The main idea behind these methods is to provide:
<ul>
<li>Efficient disk space utilization.</li>
<li>Fast access to the file blocks.</li>
</ul>
All the three methods have their own advantages and disadvantages as discussed below:

<strong>1. Contiguous Allocation</strong>

In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be:<em> b, b+1, b+2,……b+n-1.</em> This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
<ul>
<li>Address of starting block</li>
<li>Length of the allocated portion.</li>
</ul>
<strong>Advantages:</strong>
<ul>
<li>Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file which starts at block b can easily be obtained as (b+k).</li>
<li>This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>This method suffers from both internal and external fragmentation. This makes it inefficient in terms of memory utilization.</li>
<li>Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.</li>
</ul>
<strong>2. Linked List Allocation</strong>

In this scheme, each file is a linked list of disk blocks which<strong> need not be </strong>contiguous. The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next block occupied by the file.

<em>The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25) contains -1 indicating a null pointer and does not point to any other block.</em>

<strong>Advantages:</strong>
<ul>
<li>This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a contiguous chunk of memory.</li>
<li>This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.</li>
<li>It does not support random or direct access. We can not directly access the blocks of a file. A block k of a file can be accessed by traversing k blocks sequentially (sequential access ) from the starting block of the file via block pointers.</li>
<li>Pointers required in the linked allocation incur some extra overhead.</li>
</ul>
<strong>3. Indexed Allocation</strong>

In this scheme, a special block known as the <strong>Index block</strong> contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block.

<strong>Advantages:</strong>
<ul>
<li>This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.</li>
<li>It overcomes the problem of external fragmentation.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>The pointer overhead for indexed allocation is greater than linked allocation.</li>
<li>For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep one entire block (index block) for the pointers which is inefficient in terms of memory utilization. However, in linked allocation we lose the space of only 1 pointer per block.</li>
</ul>
For files that are very large, single index block may not be able to hold all the pointers.
Following mechanisms can be used to resolve this:
<ol>
<li><strong>Linked scheme:</strong> This scheme links two or more index blocks together for holding the pointers. Every index block would then contain a pointer or the address to the next index block.</li>
<li><strong>Multilevel index:</strong> In this policy, a first level index block is used to point to the second level index blocks which inturn points to the disk blocks occupied by the file. This can be extended to 3 or more levels depending on the maximum file size.</li>
<li><strong>Combined Scheme:</strong> In this scheme, a special block called the <strong>Inode (information Node)</strong> contains all the information about the file such as the name, size, authority, etc and the remaining space of Inode is used to store the Disk Block addresses which contain the actual file<em> as shown in the image below.</em> The first few of these pointers in Inode point to the <strong>direct blocks</strong> i.e the pointers contain the addresses of the disk blocks that contain data of the file. The next few pointers point to indirect blocks. Indirect blocks may be single indirect, double indirect or triple indirect. <strong>Single Indirect block</strong> is the disk block that does not contain the file data but the disk address of the blocks that contain the file data. Similarly, <strong>double indirect blocks</strong> do not contain the file data but the disk address of the blocks that contain the address of the blocks containing the file data.</li>
</ol>
&nbsp; PostVer 0

512858048qqcom • 2020-12-25 16:43:13

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/dis12.png"><img class="alignnone size-medium wp-image-9245" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/dis12-300x163.png" alt="" width="300" height="163" /></a> PostVer 0

2470994471qqcom • 2020-12-26 17:45:29

There are mainly three methods of file allocation：
<ul>
<li>Contiguous allocation</li>
<li>Linked allocation</li>
<li>Indexed allocation</li>
</ul>
<h3>Contiguous allocation</h3>
Contiguous allocation requires that each file occupy a set of contiguous blocks on the device.Device addresses define a linear ordering on the device.

<b>Advantages:</b>
<ol>
<li>In the contiguous allocation, sequential and direct access both are supported.</li>
<li>For the direct access, the starting address of the kth block is given and further blocks are obtained by b+K,</li>
<li>This is very fast and the number of seeks is minimal in the contiguous allocation method.</li>
</ol>
<b>Disadvantages:</b>
<ol>
<li>Contiguous allocation method suffers internal as well as external fragmentation.</li>
<li>In terms of memory utilization, this method is inefficient.</li>
<li>It is difficult to increase the file size because it depends on the availability of contiguous memory.</li>
</ol>
<h3>Linked allocation</h3>
Linked allocation solves all problems of contiguous allocation. With linked allocation, each file is a linked list of storage blocks; the blocksmay be scattered anywhere on the device.

<b>Advantages:</b>
<ol>
<li>In terms of the file size, this scheme is very flexible.</li>
<li>We can easily increase or decrease the file size and system does not worry about the contiguous chunks of memory.</li>
<li>This method free from external fragmentation this makes it better in terms of memory utilization.</li>
</ol>
<b>Disadvantages:</b>
<ol>
<li>In this scheme, there is large no of seeks because the file blocks are randomly distributed on disk.</li>
<li>Linked allocation is comparatively slower than contiguous allocation.</li>
<li>Random or direct access is not supported by this scheme we cannot access the blocks directly.</li>
<li>The pointer is extra overhead on the system due to the linked list.</li>
</ol>
<h3>Indexed Allocation</h3>
a special block known as the index block contains the pointer to all the blocks occupied by a file. each file contains its index which is in the form of an array of disk block addresses. The ith entry of index block point to the ith block of the file. The address of the index block is maintained by the directory.

<b>Advantages:</b>
<ol>
<li>This scheme supports random access of the file.</li>
<li>This scheme provides fast access to the file blocks.</li>
<li>This scheme is free from the problem of external fragmentation.</li>
</ol>
<b>Disadvantages:</b>
<ol>
<li>The pointer head is relatively greater than the linked allocation of the file.</li>
<li>Indexed allocation suffers from the wasted space.</li>
<li>For the large size file, it is very difficult for single index block to hold all the pointers.</li>
<li>For very small files say files that expend only 2-3 blocks the indexed allocation would keep on the entire block for the pointers which is insufficient in terms of memory utilization.</li>
</ol> PostVer 0

1210775967qqcom • 2020-12-27 19:01:15

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/online_discussion12.jpg"><img class="alignnone size-medium wp-image-9258" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/online_discussion12-300x210.jpg" alt="" width="300" height="210" /></a> PostVer 0

454234624qqcom • 2020-12-31 13:57:48

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/Online_Disscussion12_1.jpg"><img class="alignnone size-medium wp-image-9264" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/Online_Disscussion12_1-297x300.jpg" alt="" width="297" height="300" /></a> <a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/Online_Disscussion12_2.jpg"><img class="alignnone size-medium wp-image-9265" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/Online_Disscussion12_2-300x202.jpg" alt="" width="300" height="202" /></a> <a href="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/Online_Disscussion12_3.jpg"><img class="alignnone size-medium wp-image-9266" src="http://www.yvsou.com/wp-content/uploads/sites/30/2020/12/Online_Disscussion12_3-300x258.jpg" alt="" width="300" height="258" /></a> PostVer 0

1224532347qqcom • 2021-01-01 14:16:23

You must open the file before reading it. When opening a file, the operating system uses the path name to find the corresponding directory entry, which provides the information needed to find the disk block of the file. There are two basic ways to realize Directory: linear list and hash table.

1) Linear list

The simplest way to implement a directory is to use a linear table that stores file names and block pointers. First, after creating a new directory file, you must make sure that there is no directory entry in the table. To delete a file, search the directory table according to the given file name, and then release the space allocated to it. To reuse a directory item, there are many ways: you can mark the directory item as no longer in use, or add it to the free directory item table, copy the last directory item in the directory table to the free location, and reduce the length of the directory table. Using linked list structure can reduce the time of deleting files. The advantage of this method is that it is easy to implement, but it is time-consuming because of the particularity of linear table.

2) Hash table

The hash table gets a value based on the file name and returns a pointer to the element in the linear list. The advantage of this method is that the search is very fast and the insertion and deletion are relatively simple, but some preparatory measures are needed to avoid conflicts. The biggest difficulty is the fixed length of hash table and the dependence of hash function on table length.

Directory query is completed by repeated search on disk, which needs continuous I / O operation, and the cost is large. Therefore, as mentioned above, in order to reduce I / O operations, copy the currently used file directory to memory, and only operate in memory when using the file in the future, so as to reduce the number of disk operations and improve the system speed. PostVer 0

1079513613qqcom • 2021-01-04 14:15:48

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.
<ul>
<li>Contiguous Allocation</li>
<li>Linked Allocation</li>
<li>Indexed Allocation</li>
</ul>
The main idea behind these methods is to provide:
<ul>
<li>Efficient disk space utilization.</li>
<li>Fast access to the file blocks.</li>
</ul>
All the three methods have their own advantages and disadvantages as discussed below:

<strong>1. Contiguous Allocation</strong>

In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be:<em> b, b+1, b+2,……b+n-1.</em> This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
<ul>
<li>Address of starting block</li>
<li>Length of the allocated portion.</li>
</ul>
The<em> file ‘mail’</em> in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies <em>19, 20, 21, 22, 23, 24</em> blocks.

<a href="https://media.geeksforgeeks.org/wp-content/uploads/Contiguous-Allocation.jpg"><img class="alignnone size-medium wp-image-174514" src="https://media.geeksforgeeks.org/wp-content/uploads/Contiguous-Allocation.jpg" alt="pic" width="450" height="350" /></a>
<strong>Advantages:</strong>
<ul>
<li>Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file which starts at block b can easily be obtained as (b+k).</li>
<li>This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.</li>
</ul>
&nbsp;
<div id="AP_G4GR_5">
<div id="c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" class="_ap_apex_ad" data-section="c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" data-xpath="#AP_G4GR_5" data-section-id="" data-render-time="1609741121870" data-ap-network="adpTags" data-refresh-time="1609741284341" data-timeout="5589">
<div id="ADP_40792_728X280_c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" data-google-query-id="CNX9zM3Rge4CFQwhvAodYL8Fag">
<div id="google_ads_iframe_/103512698/21930050872_0__container__"><if rame id="google_ads_iframe_/103512698/21930050872_0" title="3rd party ad content" name="google_ads_iframe_/103512698/21930050872_0" width="336" height="280" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" sandbox="allow-forms allow-popups allow-popups-to-escape-sandbox allow-same-origin allow-scr ipts allow-top-navigation-by-user-activation" data-google-container-id="6" data-mce-fragment="1"></iframe></div>
</div>
</div>
</div>
&nbsp;

<strong>Disadvantages:</strong>
<ul>
<li>This method suffers from both internal and external fragmentation. This makes it inefficient in terms of memory utilization.</li>
<li>Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.</li>
</ul>
<strong>2. Linked List Allocation</strong>

In this scheme, each file is a linked list of disk blocks which<strong> need not be </strong>contiguous. The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next block occupied by the file.

<em>The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25) contains -1 indicating a null pointer and does not point to any other block.</em>
<a href="https://media.geeksforgeeks.org/wp-content/uploads/linkedListAllocation.jpg"><img class="alignnone size-medium wp-image-174517" src="https://media.geeksforgeeks.org/wp-content/uploads/linkedListAllocation.jpg" alt="linked" width="450" height="350" /></a>

<strong>Advantages:</strong>
<ul>
<li>This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a contiguous chunk of memory.</li>
<li>This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.</li>
<li>It does not support random or direct access. We can not directly access the blocks of a file. A block k of a file can be accessed by traversing k blocks sequentially (sequential access ) from the starting block of the file via block pointers.</li>
<li>Pointers required in the linked allocation incur some extra overhead.</li>
</ul>
<strong>3. Indexed Allocation</strong>

In this scheme, a special block known as the <strong>Index block</strong> contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block as shown in the image:

<a href="https://media.geeksforgeeks.org/wp-content/uploads/indexedAllocation.jpg"><img class="alignnone size-medium wp-image-174515" src="https://media.geeksforgeeks.org/wp-content/uploads/indexedAllocation.jpg" alt="indexed" width="450" height="350" /></a>
<strong>Advantages:</strong>
<ul>
<li>This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.</li>
<li>It overcomes the problem of external fragmentation.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>The pointer overhead for indexed allocation is greater than linked allocation.</li>
<li>For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep one entire block (index block) for the pointers which is inefficient in terms of memory utilization. However, in linked allocation we lose the space of only 1 pointer per block.</li>
</ul>
For files that are very large, single index block may not be able to hold all the pointers.
Following mechanisms can be used to resolve this:
<ol>
<li><strong>Linked scheme:</strong> This scheme links two or more index blocks together for holding the pointers. Every index block would then contain a pointer or the address to the next index block.</li>
<li><strong>Multilevel index:</strong> In this policy, a first level index block is used to point to the second level index blocks which inturn points to the disk blocks occupied by the file. This can be extended to 3 or more levels depending on the maximum file size.</li>
<li><strong>Combined Scheme:</strong> In this scheme, a special block called the <strong>Inode (information Node)</strong> contains all the information about the file such as the name, size, authority, etc and the remaining space of Inode is used to store the Disk Block addresses which contain the actual file<em> as shown in the image below.</em> The first few of these pointers in Inode point to the <strong>direct blocks</strong> i.e the pointers contain the addresses of the disk blocks that contain data of the file. The next few pointers point to indirect blocks. Indirect blocks may be single indirect, double indirect or triple indirect. <strong>Single Indirect block</strong> is the disk block that does not contain the file data but the disk address of the blocks that contain the file data. Similarly, <strong>double indirect blocks</strong> do not contain the file data but the disk address of the blocks that contain the address of the blocks containing the file data.
<a href="https://media.geeksforgeeks.org/wp-content/uploads/Combined-Scheme.jpg"><img class="alignnone size-medium wp-image-174516" src="https://media.geeksforgeeks.org/wp-content/uploads/Combined-Scheme.jpg" alt="inode" width="300" height="225" /></a></li>
</ol>
This article is contributed by <strong>Saloni Baweja</strong>. If you like GeeksforGeeks and would like to contribute, you can also write an article using <a href="http://www.contribute.geeksforgeeks.org/">contribute.geeksforgeeks.org</a> or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don’t stop learning now. Get hold of all the important CS Theory concepts for SDE interviews with the <a href="https://practice.geeksforgeeks.org/courses/SDE-theory?vC=1"><strong>CS Theory Course</strong></a> at a student-friendly price and become industry ready. PostVer 0

1119833189qqcom • 2021-01-05 13:33:03

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2021/01/FZS6Y4DNLLUYY0X9RX06.png"><img class="alignnone size-medium wp-image-9286" src="http://www.yvsou.com/wp-content/uploads/sites/30/2021/01/FZS6Y4DNLLUYY0X9RX06-293x300.png" alt="" width="293" height="300" /></a> PostVer 0

1285795916qqcom • 2021-01-05 16:39:06

邱锐鹏  2018329621199

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2021/01/discussion12.png"><img class="alignnone size-medium wp-image-9293" src="http://www.yvsou.com/wp-content/uploads/sites/30/2021/01/discussion12-300x188.png" alt="" width="300" height="188" /></a> PostVer 0

450766287qqcom • 2021-01-05 16:50:15

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.
Contiguous Allocation
Linked Allocation
Indexed Allocation

The main idea behind these methods is to provide:
Efficient disk space utilization.
Fast access to the file blocks.

1. Contiguous Allocation
In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
Address of starting block
Length of the allocated portion.
The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks.
Advantages:
Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file which starts at block b can easily be obtained as (b+k).
This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.
Disadvantages:
This method suffers from both internal and external fragmentation. This makes it inefficient in terms of memory utilization.
Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.

2. Linked List Allocation
In this scheme, each file is a linked list of disk blocks which need not be contiguous. The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next block occupied by the file.
The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25) contains -1 indicating a null pointer and does not point to any other block.
linked
Advantages:
This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a contiguous chunk of memory.
This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.
Disadvantages:
Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.
It does not support random or direct access. We can not directly access the blocks of a file. A block k of a file can be accessed by traversing k blocks sequentially (sequential access ) from the starting block of the file via block pointers.
Pointers required in the linked allocation incur some extra overhead.

3. Indexed Allocation
In this scheme, a special block known as the Index block contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block.
Advantages:
This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.
It overcomes the problem of external fragmentation.
Disadvantages:
The pointer overhead for indexed allocation is greater than linked allocation.
For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep one entire block (index block) for the pointers which is inefficient in terms of memory utilization. However, in linked allocation we lose the space of only 1 pointer per block. PostVer 0

2736689890qqcom • 2021-01-06 21:23:07

2018329621239-严宇豪
The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.

Contiguous Allocation
Linked Allocation
Indexed Allocation
The main idea behind these methods is to provide:

Efficient disk space utilization.
Fast access to the file blocks.
All the three methods have their own advantages and disadvantages as discussed below:

1. Contiguous Allocation

In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains

Address of starting block
Length of the allocated portion.
The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks. PostVer 0

1403861656qqcom • 2021-01-06 22:12:45

1) Continuous distribution.

The sequential allocation approach requires that each file occupies a contiguous set of blocks on disk, as shown in Figure 4-12. A disk address defines a linear ordering on the disk. This sort minimizes the number of seeks and seek time required for the job to access the disk.



2) Link allocation.

Link allocation is a discrete allocation method to eliminate the external fragmentation, so significantly improve the utilization of disk space; And because it is according to the current needs of the file, it is allocated the necessary disk blocks, when the file dynamic growth, can be dynamically allocated for it again, so there is no need to know the size of the file. In addition, the file is added, deleted, change is also very convenient. Link allocation can be divided into two forms: implicit link and explicit link.

FAT).

3) Index allocation

Link allocation solves the problem of external fragmentation and file size management for sequential allocation. However, link allocation does not effectively support direct access (with the exception of FAT). Index allocation solves this problem by lumping all the block numbers of each file together to form index blocks (tables), as shown in Figure 4-14.

Each file has its index block, which is an array of disk block addresses. The i-th entry of the index block points to the i-th block of the file. The directory entry contains the address of the index block. To read the i-th block, look for and read the required block by indexing the i-th entry pointer to the block. PostVer 0

hokyeejaufoxmailcom • 2021-01-07 09:27:36

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.
<ul>
<li>Contiguous Allocation</li>
<li>Linked Allocation</li>
<li>Indexed Allocation</li>
</ul>
The main idea behind these methods is to provide:
<ul>
<li>Efficient disk space utilization.</li>
<li>Fast access to the file blocks.</li>
</ul>
All the three methods have their own advantages and disadvantages as discussed below:

<strong>1. Contiguous Allocation</strong>

In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be:<em> b, b+1, b+2,……b+n-1.</em> This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
<ul>
<li>Address of starting block</li>
<li>Length of the allocated portion.</li>
</ul>
The<em> file ‘mail’</em> in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies <em>19, 20, 21, 22, 23, 24</em> blocks.

<a href="https://media.geeksforgeeks.org/wp-content/uploads/Contiguous-Allocation.jpg"><img class="alignnone size-medium wp-image-174514" src="https://media.geeksforgeeks.org/wp-content/uploads/Contiguous-Allocation.jpg" alt="pic" width="450" height="350" /></a>
<strong>Advantages:</strong>
<ul>
<li>Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file which starts at block b can easily be obtained as (b+k).</li>
<li>This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.</li>
</ul>
&nbsp;
<div id="AP_G4GR_5">
<div id="c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" class="_ap_apex_ad" data-section="c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" data-xpath="#AP_G4GR_5" data-section-id="" data-render-time="1609983161950" data-ap-network="adpTags" data-refresh-time="1609983196600" data-timeout="527">
<div id="ADP_40792_728X280_c9541d0b-2b1f-47f8-8b8b-63e4e11f2de9" data-google-query-id="CMGWsNTWiO4CFZhbYAodemACLA">
<div id="google_ads_iframe_/103512698/21930050872_0__container__"><if rame id="google_ads_iframe_/103512698/21930050872_0" title="3rd party ad content" src="https://6ac0b67927889439805aac8a443d2a1e.safeframe.googlesyndication.com/safeframe/1-0-37/html/container.html" name="" width="300" height="250" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" sandbox="allow-forms allow-popups allow-popups-to-escape-sandbox allow-same-origin allow-scr ipts allow-top-navigation-by-user-activation" data-is-safeframe="true" data-google-container-id="4" data-load-complete="true" data-mce-fragment="1"></iframe></div>
</div>
</div>
</div>
&nbsp;

<strong>Disadvantages:</strong>
<ul>
<li>This method suffers from both internal and external fragmentation. This makes it inefficient in terms of memory utilization.</li>
<li>Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.</li>
</ul>
<strong>2. Linked List Allocation</strong>

In this scheme, each file is a linked list of disk blocks which<strong> need not be </strong>contiguous. The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next block occupied by the file.

<em>The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25) contains -1 indicating a null pointer and does not point to any other block.</em>
<a href="https://media.geeksforgeeks.org/wp-content/uploads/linkedListAllocation.jpg"><img class="alignnone size-medium wp-image-174517" src="https://media.geeksforgeeks.org/wp-content/uploads/linkedListAllocation.jpg" alt="linked" width="450" height="350" /></a>

<strong>Advantages:</strong>
<ul>
<li>This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a contiguous chunk of memory.</li>
<li>This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.</li>
<li>It does not support random or direct access. We can not directly access the blocks of a file. A block k of a file can be accessed by traversing k blocks sequentially (sequential access ) from the starting block of the file via block pointers.</li>
<li>Pointers required in the linked allocation incur some extra overhead.</li>
</ul>
<strong>3. Indexed Allocation</strong>

In this scheme, a special block known as the <strong>Index block</strong> contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block as shown in the image:

<a href="https://media.geeksforgeeks.org/wp-content/uploads/indexedAllocation.jpg"><img class="alignnone size-medium wp-image-174515" src="https://media.geeksforgeeks.org/wp-content/uploads/indexedAllocation.jpg" alt="indexed" width="450" height="350" /></a>
<strong>Advantages:</strong>
<ul>
<li>This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.</li>
<li>It overcomes the problem of external fragmentation.</li>
</ul>
<strong>Disadvantages:</strong>
<ul>
<li>The pointer overhead for indexed allocation is greater than linked allocation.</li>
<li>For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep one entire block (index block) for the pointers which is inefficient in terms of memory utilization. However, in linked allocation we lose the space of only 1 pointer per block.</li>
</ul>
For files that are very large, single index block may not be able to hold all the pointers.
Following mechanisms can be used to resolve this:
<ol>
<li><strong>Linked scheme:</strong> This scheme links two or more index blocks together for holding the pointers. Every index block would then contain a pointer or the address to the next index block.</li>
<li><strong>Multilevel index:</strong> In this policy, a first level index block is used to point to the second level index blocks which inturn points to the disk blocks occupied by the file. This can be extended to 3 or more levels depending on the maximum file size.</li>
<li><strong>Combined Scheme:</strong> In this scheme, a special block called the <strong>Inode (information Node)</strong> contains all the information about the file such as the name, size, authority, etc and the remaining space of Inode is used to store the Disk Block addresses which contain the actual file<em> as shown in the image below.</em> The first few of these pointers in Inode point to the <strong>direct blocks</strong> i.e the pointers contain the addresses of the disk blocks that contain data of the file. The next few pointers point to indirect blocks. Indirect blocks may be single indirect, double indirect or triple indirect. <strong>Single Indirect block</strong> is the disk block that does not contain the file data but the disk address of the blocks that contain the file data. Similarly, <strong>double indirect blocks</strong> do not contain the file data but the disk address of the blocks that contain the address of the blocks containing the file data.
<a href="https://media.geeksforgeeks.org/wp-content/uploads/Combined-Scheme.jpg"><img class="alignnone size-medium wp-image-174516" src="https://media.geeksforgeeks.org/wp-content/uploads/Combined-Scheme.jpg" alt="inode" width="300" height="225" /></a></li>
</ol>
&nbsp; PostVer 0

962305148qqcom • 2021-01-07 22:13:16

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods. Contiguous Allocation Linked Allocation Indexed Allocation The main idea behind these methods is to provide: Efficient disk space utilization. Fast access to the file blocks. All the three methods have their own advantages and disadvantages as discussed below: 1. Contiguous Allocation In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the length of the file (in terms of blocks required), we can determine the blocks occupied by the file. The directory entry for a file with contiguous allocation contains Address of starting block Length of the allocated portion. The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks. PostVer 0

439731491qqcom • 2021-01-07 22:39:24

<a href="http://www.yvsou.com/wp-content/uploads/sites/30/2021/01/捕获-6.png"><img class="alignnone size-medium wp-image-9336" src="http://www.yvsou.com/wp-content/uploads/sites/30/2021/01/捕获-6-300x276.png" alt="" width="300" height="276" /></a> PostVer 0