retagged by
9,545 views
29 votes
29 votes
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__________________.
retagged by

2 Answers

40 votes
40 votes

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

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)


image2

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$

Answer:

Related questions

25 votes
25 votes
5 answers
2