GATE CSE 1998 | Question: 7-b

Question

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?

Comments

nice explanation thanks

---

Here the partitions we take is static or dynamic, that is if we found similar question with different values, can we put two process in same partition

---

Arrival time is zero for all jobs.
Autumn, yes, I think static partitioning is used here as sizes are pre-determined.

Answer 1

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.

Comments

@Tuhin Dutta

But a 14k process in 20k partition isn't occupying the partition completely and a process of 6k can be fitted in there. How their address-spaces are essentially overlapping?

If the question were about fixed/static-partitioning then you would have been surely correct.

---

See in the question partition sizes are given explicitly which implies fixed partitioning.

---

Yeah silly me.Thanks man.

Answer 2

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.

Comments

Please write comment as well for your down vote!!

---

Last 2k job will be alloted to 4k partition becuase 2k partition is not available till 4 unit of time and at 2 unit 4k partition is available for last job

Answer 3

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

Answer 4

https://gateoverflow.in/?qa=blob&qa_blobid=17049735791133376488

Comments

Can't we just arrange process in any order we want and then allocate them partitions ?

---

No.

---

@ayushsomani

If you are allowed to execute J8 before J7, then you are also allowed to execute J7 at time 0 storing in partition of 20KB. Finally taking 8 units time.

Then 20KB job will finish at time 8.