The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 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$
in Operating System by Boss (16.3k points)
edited by | 4.8k views
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.


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: 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                              


4 Answers

+38 votes
Best answer

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}\\
\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$. 


Correct Answer: $B$

by Veteran (420k points)
edited by
Hi Arjun Sir,

Why J5 is taking 14 time units to complete. Why it doesn't get completed by 12 time units?
J5 should finish at 12
yes J5 at 12
Why 7k block allocated at 20k block not at 8k block????????????????????

@Quest Curious

 need to beg others calling them Sir 

Note that

Arjun sir, doesn't mention anywhere that " CALL ME SIR ", We ourselves gave the respect to him for his knowledge and thanking him for establishing this site.



Note that request processes one by one.... means until J1 request accepted we can't look for J2 or J3

So J7 processed first compared to J8.

At time t=11,  only 4K,20K and 2K are free but 8K is fill with J5, note that 8K will be free at t=14

but at t=11 we can process the request of J7 with the help of 20K ( Best Fit means with in available, you have to choose best, here you have only 20K available with you, therefore choose that )


@Pratyush Madhukar

Block Allocation policies are not only for Variable partitions but also for Fixed Partitions.

But here they didn't mention it is Fixed or Variable Partitions

But my choice ( not standard ) is Fixed Partitions due to in the question

 memory have four free blocks of sizes 

if they really uses Variable partitions, then they give information like

  memory have four holes of sizes  

For J5 how, it will free the 8K partition at t=14 units, it should be t=12 right?as because J5 takes 4 time units. Please clarify the doubt.
order FCFS is followed.

@shashank I too have same doubt

+9 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.
by Junior (983 points)
edited by
J4 size is 6k. As per best fit it should go to C which has exactly 6k left.
Ok..You are right....Sorry For Mistake ....But Not Change in Answer....I Will Correct it..

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
+4 votes
B 19
by Active (1k points)
how explain
0 votes

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. 


by (17 points)
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,288 questions
55,716 answers
90,102 users