GATE IT 2007 | Question: 11

Question

Let a memory have four free blocks of sizes $4k$, $8k$, $20k$, $2k$. These blocks are allocated following the best-fit strategy. The allocation requests are stored in a queue as shown below.$$\small \begin{array}{|l|l|l|l|l|l|l|l|}\hline \textbf{Request No} & \text{J1} & \text{J2} & \text{J3} & \text{J4} & \text{J5} & \text{J6} & \text{J7} & \text{J8}   \\ \hline \textbf{Request Sizes} & \text{2k}& \text{14k}& \text{3k}& \text{6k}& \text{6k}& \text{10k}& \text{7k}& \text{20k} \\\hline \textbf{Usage Time} & \text{4} & \text{10}& \text{2}& \text{8}& \text{4}& \text{1}& \text{8}& \text{6} \\ \hline\end{array}$$The time at which the request for $J7$ will be completed will be

• A. $16$
• B. $19$
• C. $20$
• D. $37$

Comments

Very good analysis

---

Shortcut trick

https://gateoverflow.in/3444/gate-it-2007-question-11?show=413827#a413827

---

Thankyou for the analysis!

Answer 1

 Short Trick to solve this question .

 

Answer 2

I think, the answer should be 18. The main difference, between my answer and the one provided by Arjun sir, is that I allocated J4 to the remaining space available in the 20K block. So, the 8K block can immediately be assigned to J5. Recall that, in variable-size partitioning, the degree of multiprogramming is NOT restricted by the number of partitions. Thus, we can simultaneously (of course in order as they are in a queue) allocate processes J1 to J5, without any waiting. See Galvin article 8.3.3. 

 

Comments

Can two (or more) processes can be allocated to a single memory block?? I don't think so. It(the extra space available in the 20K memory block) will be treated as internal fragmentation

Answer 3

Answer: (B)

Explanation: Initially when a process arrives and needs memory, it would search for a hole big enough to fit the job and if the hole is larger then the remaining hole is returned to the free storage list.

Memory Block	Size	Job (t=0)	Job(t=8)	Job(t=10)	Job(t=11)
1	4k	J3 – 2 units (1K free left)
2	8k	J4 – 8 units (2K free left)	J5 – 14 units	J5 – 14 units	J5 – 14 units
3	20k	J2 -10 units(6K free left)	J2 -10 units	J6 – 11 units	J7 – 19 units
4	2k	J1 -4 units

Therefore, the process finishes at J7=19 units

Option B

Answer 4

BNo.  RNo.     Free at

4K    J3       2

8K    J4       8

20K   J2       10

2K    J1       4

Time: 0

 

BNo.  RNo.     Free at

4K          

8K    J5       12      

20K   J2       10

2K          

Time: 8

 

BNo.  RNo.     Free at

4K          

8K    J5       12              

20K   J6       11

2K          

Time: 10

 

BNo.  RNo.     Free at

4K          

8K    J5       12              

20K   J7       19

2K          

Time: 11