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

J5 finishes at 12

---

Hi there! Shouldn't the completion time for J5 be 12?

---

ood question

---

@Debashish

J5 will be finish at 12 .Am i right ? pls help

---

Yes, I think so.

---

@ujjwal so according to that answer should be 20 for j7.

---

@set2018 Can you tell me why it will be 20 for j7 even if J5 finishes at 12?

J6 finishes at 11, so that time we can schedule j7

---

@rahul sharma 5

Again now i have a doubt question is about best fit 

According to that After allocating J2 to 20k remaining space will be (20-14=6) according to best fit  process J4 will go into 20k remaining space (which is 6)for this it shoulf be fininsh into 18 

confused :(

---

Can you elaborate more on

J4 will go into 20k remaining space (which is 6)for this it shoulf be fininsh into 18 

I am not able to understand.

---

J4 will go into 20 k block becoz after completion of J2 (which is 14 kb) remaining space is 6kb .in this free space according to best fit j4 can enter

---

When a partition is already having a job it shouldn't be taking any more jobs. That 6K space will be treated as internal fragmentation. Block sizes are given as fixed. J4 should go in 8K partition.

the answer should be B) 19

---

got it

---

 Tuhin Dutta see this question 

When a partition is already having a job it shouldn't be taking any more jobs

why we allocate other sizes in one block?

https://gateoverflow.in/2467/gate1994_1-24

---

There we have variable partitioning but here we have fixed size partitions. Here internal fragmentation occurs whereas in that case, external fragmentation occurs.

---

Hi @Tuhin Dutta ji,

Thank You. Please convert your comment to answer. Use table if possible.

---

@tuhin

but how did you know that the question in the link given by @set2018 uses variable partitioning ?

---

@Aish, Do you see any internal fragmentation here: https://gateoverflow.in/2467/gate1994_1-24? Since no internal fragmentation thus variable partitioning but later external fragmentation can occur when the job completes and leave holes.

---

ans B or C?

---

Ans is 19 which is option B)

---

Why J7 is placed in 20 K partition instead of 8 K partition ( Best fit statergy ) ?

---

simple method .. Thanks

---

Requests will be fulfilled in Fcfs manner only. and size is given (2k,4k...) means it is fixed size partition means you can not allocate free space to another process while one process is using this space..

---

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

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

 

---

A better way of understanding would be:

 

One example rests you can do: J7 can only under 8k and 20k but 20k is taking less time (11 clock cycle) than 8k (12 clock cycle). Hence, J7 comes under 20k.

I hope this makes everything clear.

---

even if we consider that a block can hold more than one process simultaneously

then the answer do not match the options, this is clear indication.

@Shaik Masthan sir has an intuitive point in the best answer comment to distinguish between fixed/variable partitioning scheme, check it out.

---

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

PS: Since the block sizes are given, we cannot assume further splitting of them. 

Also, the question implies a multiprocessing environment and we can assume the execution of a process is not affecting other process' runtime. $$\overset{\large{\text{At }t=0}}{\small{\begin{array}{|c|l|l|} \hline \textbf{Memory} & \textbf{Size} & \textbf{Job}\\
\textbf{Block}&&\\
\hline \text{A} & \text{4k} & \text{J3 (finishes at t = 2)} \\\hline \text{B} & \text{8k} & \text{J4 (finishes at t = 8)} \\\hline \text{C} & \text{20k} & \text{J2 (finishes at t = 10)} \\\hline \text{D} & \text{2k} & \text{J1 (finishes at t=4)} \\\hline  \end{array}}} \quad
\overset{\large{\text{At }t=8}}{\small{\begin{array}{|c|l|l|} \hline \textbf{Memory} & \textbf{Size} & \textbf{Job}\\
\textbf{Block}&&\\ \hline \text{A} & \text{4k} & \text{}
\\\hline \text{B} & \text{8k} & \text{J5 (finishes at t=12)} \\\hline \text{C} & \text{20k} & \text{J2 (finishes at t = 10)} \\\hline \text{D} & \text{2k} & \text{} \\\hline  \end{array}}}$$ $$\overset{\large{\text{At }t=10}}{\small{\begin{array}{|c|l|l|} \hline \textbf{Memory} & \textbf{Size} & \textbf{Job}\\
\textbf{Block}&&\\ \hline \text{A} & \text{4k} & \text{} \\\hline \text{B} & \text{8k} & \text{J5 (finishes at t=12)} \\\hline \text{C} & \text{20k} & \text{J6 (finishes at t = 11)} \\\hline \text{D} & \text{2k} & \text{} \\\hline  \end{array}}}\quad \overset{\large{\text{At }t=11}}{\small{\begin{array}{|c|l|l|} \hline \textbf{Memory} & \textbf{Size} & \textbf{Job}\\
\textbf{Block}&&\\ \hline \text{A} & \text{4k} & \text{} \\\hline \text{B} & \text{8k} & \text{J5 (finishes at t=12)} \\\hline \text{C} & \text{20k} & \text{J7 (finishes at t = 19)} \\\hline \text{D} & \text{2k} & \text{} \\\hline  \end{array}}}$$

So, $J7$ finishes at $t = 19$. 

Reference: http://thumbsup2life.blogspot.fr/2011/02/best-fit-first-fit-and-worst-fit-memory.html

Correct Answer: $B$

Comments

order FCFS is followed.

---

@shashank I too have same doubt

---

that is best available fit ,which you are talking about ,here best fit given so answer C)

Answer 2

In Best Fit Policy Process Seek for Best Size for opted by someone. but only when, there is no t space available.

A=4k, B=8k, C=20k, D=2k

So J1=2k_D, J2=14k_C(free 6k), J3=3k_A(free 1k), J4=6k_Space between C&D, J5=6k_B(free 2k)..  

now J6 wait for best block= (J2)C block, and J7 wait for = (J4) Space between C&D block

So add the time of J2+J6+J7= 10+8+1=19 Ans.

Comments

After allocating a job in one partition can we allocate next job in that same partition ? 

---

J4 should occupy block C it has 6k left J5 should occupy block C rite?

---

how is j7=1

Answer 3

B 19

Comments

how explain

Answer 4

Best fit is actually an algorithm for finding holes and we know it simply does O(n) search to find it . By that logic , the following allocations happen immediately :

1) J1 goes to 2k partition (Completely filled)

2) J2 goes to 20k partition (6k space still left , i.e hole of size 6k)

3) J3 goes to 4K partition (1k space left , i.e hole of size 1k )

4) J4 goes to 8k partition (2k space left , i.e hole of size 2k)

When assigning J5 which is of size 6k , the holes are checked linearly . Refer to step 2 above , it has a 6k sized hole to be filled . So J5 is allocated to the remaining 6k space. Therefore following are the vacant spaces/holes in each partition.

1) partition (2k): 0 k

2) partition (20k) : 0 k

3) partition (4k) : 1 k

4) partition (8k) : 2k

Since J6 is 10k and there's no space left , it has no option but to wait till J2 (sized 14k) to finish it's execution. So by the end of 10 units of time partition (20k) has a hole sized 20k (14k from J2 and 6k from J5 , as both were allocated instantly) and J6 is fit into it. Note : by the end of 10 units all other partitions other than partition (20k) are empty as all it's processes are complete. Therefore following are the vacant spaces/holes in each partition.

1) partition (2k): 2 k

2) partition (20k) : 10 k

3) partition (4k) :  4k

4) partition (8k) : 8k

When assigning J7 which is of size 7k , the holes are checked linearly . Refer to step 4 above , it has a 8k sized hole/partition to be filled . So J5 is allocated to partition (8k).

 

Total time taken to complete J7 = 10(total wait) + 8(time taken by J7) = 18 .

At the end of 18th unit or beginning of 19th unit J7 is complete.