GATE CSE 2022 | Question: 53
Arjun asked in Operating System Feb 15, 2022 retagged Nov 30, 2022 by Lakshman Patel RJIT
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__________________.
gatecse-2022
numerical-answers
2-marks
by ShouvikSVK
commented Feb 19, 2022
https://courses.cs.washington.edu/courses/cse451/98au/Section/ch11/
refer this for practice problems
by Bhaskar_Saini
Why are you counting 50 read operations?? Because in contiguous we can directly access the 50th location. Please explain!!
by `JEET
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.
`JEET answered Feb 18, 2022 edited Dec 28, 2022 by gatecse
by khushitshah
commented 1 day ago
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.
← Previous in categoryNext in category →
Arjun asked in Operating System Feb 15, 2022
Consider a demand paging system with four page frames (initially empty) and $\text{LRU}$ page replacement policy. For the following page reference string $7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1$ the page fault rate, defined as the ratio of number of page faults to the number of memory accesses $\textit{(rounded off to one decimal place)}$ is _____________.
page-replacement
demand-paging
Arjun asked in Databases Feb 15, 2022
Consider the relational database with the following four schemas and their respective instances. Student(sNo, sName, dNo) Dept(dNo, dName) Course(cNo, cName, dNo) Register(sNo, cNo) ... SELECT cNo FROM Register WHERE sNo = S.sNo) The number of rows returned by the above $\text{SQL}$ query is ____________.
Arjun asked in Computer Networks Feb 15, 2022
Consider a network with three routers $\text{P, Q, R}$ shown in the figure below. All the links have cost of unity. The routers exchange distance vector routing information and have converged on the routing tables, after which the link $\text{Q-R}$ ... off to one decimal place) between $\text{P}$ and $\text{Q},$ leading to count-to-infinity problem, is _______________.
computer-networks
distance-vector-routing
Arjun asked in Algorithms Feb 15, 2022
Let $\textit{G(V,E)}$ be a directed graph, where $\textit{V} = \{ 1, 2, 3, 4, 5 \}$ is the set of vertices and $\textit{E}$ is the set of directed edges, as defined by the following adjacency matrix $\textit{A}.$ ... contains a directed path from $r$ to every other vertex in $V.$ The number of such directed spanning trees rooted at vertex $5$ is __________________.
spanning-tree
General Aptitude (2.5k)
Engineering Mathematics (9.3k)
Digital Logic (3.3k)
Programming and DS (5.8k)
Algorithms (4.6k)
Theory of Computation (6.7k)
Compiler Design (2.3k)
Operating System (5.0k)
Databases (4.6k)
CO and Architecture (3.8k)
Computer Networks (4.6k)
Non GATE (1.3k)
Others (2.4k)
Admissions (649)
Exam Queries (842)
Tier 1 Placement Questions (17)
Job Queries (74)
Unknown Category (853)