3,681 views
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__________________.

Why are you counting 50 read operations?? Because in contiguous we can directly access the 50th 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.

$\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.
by

1 access is to write the address of new block to the 50th block next pointer.
Tho during exam i missed that one and wrote 152.

Thanks @Pranavpurkar @khushitshah . So it means that writing / updating the next pointers incur 1 more block access although we have already read the block.