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

So,  j7 finishes at t=19

time

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

4k

J3

J3

8k

J4

J4

J4

J4

J4

J4

J4

J4

J5

J5

J5

J5

J8

J8

J8

J8

J8

J8

20k

J2

J2

J2

J2

J2

J2

J2

J2

J2

J2

J6

J7

J7

J7

J7

J7

J7

J7

J7

2k

J1

J1

J1

J1

---

Very good analysis

---

Shortcut trick

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

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