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

ans should be 153

---

Why??

---

See we just need to change the pointers in linked allocation and the block is already present, therefore there is no need to write something. So I belive just $2$ accessss for two pointers

---

incase of linked allocation when u access 50 ^th block  u find the pointer for  the 51th block in old linked allocation 

access the new block  and pointed to 51th block one disk access after this we can find pointer to the new block  so we access the  50^th block(old  linked  allocation) and change its  next pointer 

50 for finding middle after this 2 disk access  required overall 52

---

Yes, your logic and mine logic is exactly same. The only mistake was in the addition. Kind of typo.

---

Best explanation ,,👌😎

---

In contiguous allocation we can directly access the 50^th element then why we are counting 50 read operations? I am unable to understand the concept of 50 read operations. 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 the $50$ elements, and hence we need to read them. So, $50$ read operations.

---

@`JEET @Pranavpurkar @khushitshah  In case of Linked Allocation:-

After reading the first 50 blocks, we already know what the 50^th block is and what it’s next pointer is, so why are we adding one more operation to read it’s next pointer while inserting the new block? Why is the answer not 152?

Edit: Got it. The reason is this:-

linked allocation

52. I must read 50 blocks to find the middle. Then I must write my new block somewhere with the next block pointing to the block after the 50th block. Then I must write the 50th block to point to this new block.

Ref

---

@Abhrajyoti00

In linked allocation , it is asking for total number of disk accesses required to insert the block between 50^th and  51^st  block, as only sequential search is possible in the linked allocation so at first we have to search the 50^th block (even if we know where the 50^th block is, no random access is possible here , so we have to go sequentially) .

when we reach the 50^th block now here we have to insert the new block which requires updations of two links , the next of 50^th block and the next of new block, so to update the next of 50^th block we have to access the new block (so here till now $50 + 1$ access) now after this to update the next of new block we have to access the 51^st block (so now $50 + 1 + 1$ accesses) total $52$ accesses in case of linked allocation.

and in contiguous allocation total accesses are $101$ as explained above .

so total accesses = $153$.

 

---

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.

---

Thanks

---

I have two enquiries in the question

1.why do we need 50 read operations in contiguous memory allocation. we can just directly go to the disred memory location. without doing such operations

2.you wrote that 2 operation are needed to delete the link between 50 ^th and 51 ^th node and add the new. but I think that we need two  operation to join the node between 50 and 51 st node and one operation to break the connection. so total 

in contiguous 50 write operation +1 write + 50(traverse operation)+3(joining and disconnecting operation) plz correct me if I am wrong

 

---

@`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$