4.8k 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$

edited | 4.8k views
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,

+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)
+2
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..
0
 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

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

Correct Answer: $B$

by Veteran (420k points)
edited
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

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

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 )

+3

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

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

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

1
2