The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 votes

In a computer system where the ‘best-fit’ algorithm is used for allocating ‘jobs’ to ‘memory partitions’, the following situation was encountered:

Partitions size in $KB$ $4K \ 8K \ 20K \ 2K$
Job sizes in $KB$ $2K \ 14K \ 3K \ 6K \ 6K \ 10K \ 20K \ 2K$
Time for execution $4 \ 10 \ 2 \ 1 \ 4 \ 1 \ 8 \ 6$


\begin{array}{|l|l|} \hline  \textbf{Partitions size in $KB$} & \textbf{$4K \ 8K \ 20K \ 2K$} \\\hline \textbf{Job sizes in $KB$} & \text{$2K \ 14K \ 3K \ 6K \ 6K \ 10K \ 20K \ 2K$} \\\hline  \textbf{Time for execution} & \text{$4 \ 10 \ 2 \ 1 \ 4 \ 1 \ 8 \ 6$} \\\hline  \end{array}

When will the $20K$ job complete?

asked in Operating System by Veteran (408k points)
edited by | 2.9k views
Is all the process will run at same time?

I think ,only one process can be assign to CPU at a time.

If we take first come first serve ,3k process will take 0to2 unit of time then ,6k 2-3,14k 4-13,2k 14-17,10k 17-18,20k 19-27.....

Is any thing wrong


answer is 19 units.

Can we schedule J8 before j5.6.7?
i think yes because all the processes are there in the system already and we will schedule J8 from t=2 to t=8.

may be i am wrong. Please correct
I also think yes. Since nothing is mentioned I've taken the order in which it is given J1 to J8 (FCFS). Had it been mentioned we could have ordered the jobs for their respective partitions according to which one takes lesser BT schedule that one first. In this kind of questions we don't consider such things. We simply take the order in FCFS manner. Am I correct?
The important thing to understand here is that this is related to Fixed Partitioning, since the partitions have been initially mentioned explicitly..
Why not to use Fcfs?

@Swapnil Naik because all the job is initial available 


@Tuhin Dutta it is the static allocation so the J8 should go in the 2K slot even though the 4K is empty before 2K slot,

3 Answers

+26 votes
Best answer

Partitons are $4k , 8k, 20k,  2k$, now due to best fit algo,

  1. Size of $2k$ job will fit in $2k$ partition and execute for $4$ unit
  2. Size of $14k$ job will be fit in $20k$ partition and execute for $10$ unit
  3. Size of $3k$ job will be fit in $4k$ partition and execute for $2$ unit
  4. Size of $6k$ job will be fit in $8k$ partition now execute for $1$ unit. All partition are full.

and next job size of $10 k$ $(5)$ wait for the partition of $20k$ and after completion of no. $2$ job, job no. $5$ will be executed for $1$ unit ($10$ to $11$). Now, $20 k$ is also waiting for partition of $20k$, because it is best fit for it. So after completion of job $5$, it will be fit . So, it will execute for $8$ unit which is $11$ to $19$. So, at $19$ unit $20k$ job will be completed .

Answer should be $19$ units.

answered by Boss (16.9k points)
edited by
Can you please explain why would the first 2K job execute for 2 units of time instead of the given 4 units?
Which scheduling algorithm should be considered here? as it is not given in the question. And should this be considered fixed partitioning or dynamic partitioning? @Arjun Sir

There are two 6k requests in the question and you have considered only 1,

the first 6k request will be satisfied by the 20k partition executing 14k request, and from the next 6k request your answer will apply, 

Although answer will be same, at 19s.

Why is the execution time for each partition starting from 0?
CPU can execute each alloted process one-by-one.
Therefore only one process can be asigned to the cpu at atime
for eg: 2k job exectues from 0-4 units
          4k job should execute from 4-14 units

No, don't consider CPU scheduling as it is not mentioned. 

Whenever the context is partitioning or allocation using best fit etc Consider the execution time  as the time for which a process will occupy a partition. These kind of questions should be dealt in this way.

Ohhk... Thankz bro :-)
when will J8 complete execution at 8 time units or 25 units?
8 time units

I have a doubt.

After we put '14K' process into '20K' partition, there'll be '6K' left. The next '6K' can be put into it instead of '8K' partition. This delays the execution of '20K' process by one unit.

So, shouldn't the answer be 20?

Please correct me if I'm missing anything here.

One partition can hold only one job at a time
Why? I mean there's empty space for a whole process, but it can't be used.

Can a partition hold only one process in static partitioning? (consider this question is about static partitioning)
Yes in case of static partitioning one partition can hold only one job at a time. Rest free space is treated as internal fragmentation.
Please explain me . I did not get how to consider the execution [email protected] Shivansh Gupta
try to write 4 partitions and allot the partitions according to availability, within the available partitions choose the best fit. Just do this until 20K process completes. While doing this keep track of the start and end times of each job. Or it will also be clear from the pic above by Tuhin Dutta
But here nothing is mentioned about static partitioning so if we consider that the intermediate contiguous holes created after any allocation are clubbed together to form a bigger hole and then that can be allocated to fit some process...It will lead to answer as 18 time units. Please check
0 votes
T=1   P4 Finishes
T=2   P3 finishes
T=4   P1 Finishes
T=5   P5 Finishes
T=10  P2 Finishes
T=11  P6 Finishes
T=19 P7 (20K job) Finishes
answered by Junior (663 points)
–1 vote

Ans: 19 time unit


First thing we can do is distributes the jobs among partitions as given below:

Now question is asked for 20K job so clearly it depends on 14K and 10K jobs

So it will complete after: 14K Execution time (10) + 10K Execution time (1) + 20K  Execution time (8)

=19 unit.

answered by Active (1.2k points)
Please write comment as well for your down vote!!

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
49,588 questions
54,197 answers
71,152 users