edited by
18,981 views
54 votes
54 votes

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

  1. $16$
  2. $19$
  3. $20$
  4. $37$
edited by

7 Answers

Best answer
65 votes
65 votes

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$

edited by
10 votes
10 votes
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.
edited by
1 votes
1 votes

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.

 

Answer:

Related questions