GATE CSE 2017 | Set 2 | Question: 08

Question

In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed?

1. Contiguous
2. Linked
3. Indexed

• A. $1$ and $3$ only
• B. $2$ only
• C. $3$ only
• D. $2$ and $3$ only

Comments

@usher Just my opinion , I think we can prefer Linked FAT as both don't have External fragmentation but we have to consider Internal Fragmentation which can be more in Indexed FAT where index block as well as last file block can have Internal fragmentation , while in Linked FAT only last block of file can have Internal Fragmentation.

---

option D   indexed & linked
 

https://www.geeksforgeeks.org/operating-systems/file-allocation-methods/

---

Contiguous Allocation :                          Internal Fragmentation ✅     External Fragmentation ✅

Linked Allocation :                          Internal Fragmentation ✅     External Fragmentation ❌

Indexed Allocation :                           Internal Fragmentation  ✅    External Fragmentation ❌

Answer 1

Answer: D) Both Linked and Indexed allocation free from external fragmentation

Refer: Galvin

Reference: https://webservices.ignou.ac.in/virtualcampus/adit/course/cst101/block4/unit4/cst101-bl4-u4-06.htm

Comments

The link is marked unsafe by Chrome. Is there any other link where I can get more information about this topic?

---

In galvin, allocation methods in file system chapter 11.

---

@srestha@Bikram plz let me know if i am wrong

Internal Fragmentation

1) It occurs when memory is divided into fixed-sized partitions.

2) it occurs contiguous & non contiguous allocation

3)non contiguous allocation avoid external fragmentation.

External Fragmentation

1)It occurs when memory is divided into variable-sized partitions based on size of process.

2) it does not occur when memory allocated in non contiguous manner.

---

Plz search Wikipedia for it.

---

Internal fragmentation happens when the unusable memory is within an allocated memory area.

external fragmentaion happens when the unusable memory is not within an allocated memory area but its still unusable. 

Source

Answer 2

Option D: Both Indexed and Linked file allocation schemes do not suffer from external fragmentation,  Whereas Contiguous allocation suffer from external fragmentation & Internal fragmentation may exist in the last disk block of a file.

Comments

Internal Fragmentation will be there in all the allocations.

---

in dynamic memory allocation, memory pools drastically cut internal fragmentation by spreading the space overhead over a larger number of objects.

---

@hem chandra joshi @vishalshrm539

IF we have a file of size 1020 B and block size is 512 B

Then every allocation technique will give Internal fragmentation as last block wil  be partially filled 

So all techniques suffer from Internal fragmentation is right ???

---

Yes, all will suffer from internal fragmentation given File size is not a multiple of Block size.

Answer 3

Contiguous: It's possible to have external fragmentation, as to store a file we need continous data blocks which might not be available.

Linked: No ext. fragmentation,as we can link data blocks by using a pointer to next data block in each data block.

Indexed: No ext. fragmentation,as in index table we store a files all data blocks addresses,without requiring to access data block to get to random data block.

Option D

Answer 4

The correct answer is: D. 2 and 3 only

Explanation:

In file allocation systems, external fragmentation occurs when free storage space is broken into small pieces and is scattered throughout the disk, making it difficult to allocate contiguous space to new files.

---

1. Contiguous Allocation

• Description: Allocates a single continuous block of space for a file.
• External Fragmentation: Yes. As files are created and deleted, gaps of free space arise that may be too small for new files.
• Conclusion: Not suitable when no external fragmentation is allowed.

---

2. Linked Allocation

• Description: Each file is a linked list of disk blocks, which can be scattered anywhere on the disk.
• External Fragmentation: No. Any free block can be used; there's no need for contiguous space.
• Conclusion: Suitable.

---

3. Indexed Allocation

• Description: Maintains an index block with pointers to all blocks of the file.
• External Fragmentation: No. Like linked allocation, blocks can be scattered.
• Conclusion: Suitable.

Answer 5

                                                                       About Every Allocation Scheme

Contiguous Allocation :  Internal Fragmentation ✅     External Fragmentation ✅

Linked Allocation :  Internal Fragmentation ✅     External Fragmentation ❌

Indexed Allocation :  Internal Fragmentation  ✅    External Fragmentation ❌

Answer 6

option D   indexed & linked
 

https://www.geeksforgeeks.org/operating-systems/file-allocation-methods/