The Gateway to Computer Science Excellence
+31 votes
6.4k views

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
edited by | 6.4k views
0
J5 finishes at 12
0
Hi there! Shouldn't the completion time for J5 be 12?
0
ood question
0
@Debashish

J5 will be finish at 12 .Am i right ? pls help
0
Yes, I think so.
0
@ujjwal so according to that answer should be 20 for j7.
+1
@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
+1

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

0

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.

0
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
+29

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

0
got it
0

 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

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

Hi @Tuhin Dutta ji,

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

+1
@tuhin

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

@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.

0
ans B or C?
0
Ans is 19 which is option B)
+3
Why J7 is placed in 20 K partition instead of 8 K partition ( Best fit statergy ) ?
0
simple method .. Thanks
0

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

+3
  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                              

 

+1

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.

5 Answers

+50 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}\\
\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$

by
edited by
+4
sir cannot one block contain two request if it has enough free space.????

since here not mention  that one block service at a time for only one request???
+20
J5 finishes at 12..
+1
Yes  you are right, they haven't mentioned fixed size partition
0
Can someone confirm this?
0
sir everything is ok but i have one question the link you provided or in the given question you are execution every job at every time cycle means from t = 0 to t = 8 job J1, J3, J4 are finished but we have only one cpu how can we execute more than one job at the same time in the same cpu..? means at a time only one process can execute na.?
+6
@Arjun sir: As this is asking to use Best Fit strategy, it implies that it is variable partitioning method.

In variable partitioning method each process is allocated only as much space as it requires. So if a partition has space left after being occupied by a process, say p1,  and is adequate for some other process,say p2, then that free space can be allocated to p2 (Reference: Stallings. I even have a solution pdf by stallings where he mentions this).

Even in Galvin it is mentioned that if the hole is too large it is split into two parts. Galvin doesn't go into much details in this topic, but Stallings does.

Tanenbaum says: The hole is then broken up into two pieces, one for the process and one for the unused
memory...
+1


The allocation requests are stored in a queue as shown below.

does it mean that schuduling should be in fcfs order  ?

+1

@Arjun. The question is asking :

At what time the request would be completed?

and not:

At what time the job would be completed?

Answer to first question is 11 sec.

Answer to second question = 19 sec.

0
Arjun sir plzz explain this concept how you have taken timings i.e a t=0,t=8..a not getting this tried allot.
0
how j5 finish at 14. i think it should be [email protected] Sir plz explain
+1
Best fit for J4 should be block C(remaining left is 6KB) and then J5 could be alloted Block B at t=0.At t=4 J5 relinquishes Block B and then J7 completes at t=12.Why is the answer not 12?
0
Hi Arjun Sir,

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

@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.

0

@flash12

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 )

+5

@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  

0
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.
0

order FCFS is followed.

0

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

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

0
J4 should occupy block C it has 6k left J5 should occupy block C rite?
0
how is j7=1
+4 votes
B 19
by
0
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
0
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
0 votes

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

by
Answer:

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
52,315 questions
60,432 answers
201,766 comments
95,245 users