edited by
12,668 views
47 votes
47 votes
In a computer system where the ‘best-fit’ algorithm is used for allocating ‘jobs’ to ‘memory partitions’, the following situation was encountered:$$\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?
edited by

5 Answers

Best answer
38 votes
38 votes

The partitions are $4k, 8k, 20k,  2k$, now due to the best-fit algorithm,

  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 partitions 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\;\text{to}\; 11).$ Now, $20 k$ is also waiting for a partition of $20k$ because it is the 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.

The answer should be $19$ units.

edited by
21 votes
21 votes

Ans: 19 time unit

Explanation:

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.

2 votes
2 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
2 votes
2 votes
Answer:

Related questions

45 votes
45 votes
4 answers
2
26 votes
26 votes
4 answers
4
Kathleen asked Sep 25, 2014
8,219 views
The overlay tree for a program is as shown below:What will be the size of the partition (in physical memory) required to load (and run) this program?$\text{12 KB}$$\text{...