GATE CSE 2022 | Question: 53

Question

Consider two files systems $\text{A}$ and $\text{B}$, that use contiguous allocation and linked allocation, respectively. A file of size $100$ blocks is already stored in $\text{A}$ and also in $\text{B}$. Now, consider inserting a new block in the middle of the file (between $50^{th}$ and $51^{st}$ block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in $\text{A}$ and $\text{B}$ are $n_{A}$ and $n_{B}$, respectively, then the value of $n_{A} + n_{B}$ is__________________.

Comments

Why are you counting 50 read operations?? Because in contiguous we can directly access the 50^th location. Please explain!!

---

Right!! In contiguous memory allocation, we can directly access the given location.

But here we are inserting an element at the $51^{st}$ location, therefore, we have to shift the rest of $50$ elements, and hence we need to read them. So, 50 read operations.

---

Is contiguous allocation means indexd allocation always in file systems in os ?

bcoz i studied both with different names so i have confusion anyone please clarify it ?

Answer 1

$\underline{\underline{\textbf{Answer: 153}}}$
$\underline{\underline{\textbf{Explanation:}}}$

$$\color{blue}{\enclose {circle}{\color{magenta}{\text{ -No Free blocks- }}}}\textbf{1, 2, 3,..,49, 50, } \enclose{circle}{\color{red}{\textbf{New Block}}} \textbf{, 51, 52, …,99, 100, ... }\color{green}{\underline{\underline{\textbf{ Free Blocks ... }}}}$$

$\textbf{Contiguous Allocation:: }$
In case of $\mathbf{Contiguous}$ allocation we can directly go to the $50^{\textbf{th}}$ element. After this, we have to insert a block here, and since the allocation is $\textbf{Contiguous}$, therefore you need to shift all the remaining $50$ blocks $\color {red}{\text{to the right.}}$ [As enough free blocks are available to the right and no free blocks are available in the beginning, so we can only shift the blocks to he right only].

So, $ 50\text{ Read Operations } + {50 \text{ Write Operations}} + \mathbf{1}\;\text{[1 operation to write a newly inserted block]} = 101\; \text{ Operations in Total.}$.

Also, we know from the Contiguous Memory allocation concept that overwriting an element simply means deleting it. Therefore, we don't have to worry about deleting an element specifically. We can just overwrite them, thus saving the cost of operations.

---

$\textbf{Linked Allocation:: }$
In $\textbf{ Linked Allocation }$, $50\text{ operations to read first 50 elements }$, $2\; \text{operations}$ are needed to delete the next pointer of the $50^{\textbf{th}}$ element, connect that link to the block which is to be inserted, and then connect the next pointer of that block to the $51^{\textbf{st}}$ element. This takes $\textbf{2 operations.}$
So, Total $\mathbf{52}$ operations are needed in this case.

$\color{red}{\textbf{Note:}}$

• The statement “The file Control Blocks are already there in memory “ means the information regarding the file structure is already present in the memory. (Eg: index block in the case of indexed allocation is already present in memory.)
• $\text{I/O Operations or Operations or Read & Write Operations or Disk Accesses, }$ all of them simply represent the same thing.

Comments

@`JEET Very Well Explained! 🙌

---

@Atri 50 read and write operations are required to shift 50 blocks,for shifting one block we need to perform 1 read + 1write.

In contiguous allocation we’re not changing links,in linked allocation we’ve to perform 2 write operations,one to change pointer from 50^th  to new block and another write to update pointer from new block to 51^st block.

---

@Abhrajyoti00 @jeet if statement “The file Control Blocks are already there in memory “ is not given then we need to add 2 more memory accesses(one for each A and B) to update information regarding file?

Answer 2

Answer: 153 (Disk Accesses)

File System $A$: uses contiguous allocation

in this system, we can Random Access any block we want but to write a new block and to keep it in a contiguous fashion we need to move every block by one block to the right

so we need 1 read disk access (copy it to memory) and 1 write disk access (write back to disk) to move a block = 50 * 2 disk access to move 50 blocks to the right and finally writing a new block requires 1 more disk write access

hence for $A$, 

        $n_{a} = 50 * 2 + 1 = 101 $ disk accesses 
 
depicted in the image:


File System $B$: uses linked allocation

in this system, we need to maintain pointers to the next block in that order (no random access possible) 

$Todo$ : point the $50 ^{th}$ block to the new block and point the new block to the $51^{st}$ block

so we need 50 disk read accesses to get the address of the $51^{st}$ block (oh, also store the pointer to $50^{th}$ block in memory and also keep the copy of the $50^{th}$ block read in the memory too, we need this in the future)

we have the new block in the main memory so we can just write the pointer to point to the $51^{st}$ block in the main memory without any disk access, but note that the $50 ^{th}$ block has to point to the new disk block, but we can't know what address to point to just now, so we have to write the block into disk first (1 disk write access)


After writing the new block to the disk, we now have a new block already pointing to the $51^{st}$ block, and the only thing to do is to just point the $50 ^{th}$ block to the new disk block written, and remember we stored $50 ^{th}$ block and it's pointer already, so now we can just access that particular block and update it to point to the new block, but it's in main memory. so we have to write it into the disk (we just overwrite it) so 1 more disk access 

and done. 



so we need 50 disk read access to get $51^{st}$ and $50 ^{th}$ block address = 50 disk access and then to write the new block we need 1 disk access and finally update the $50 ^{th}$ block requires 1 more write access 

hence for $B$, 

        $n_{b} = 50 + 1 + 1 = 52 $ disk accesses 

⇒ $ n_{a} + n_{b} = 101 + 52 = 153$