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 explanations need not to be that long and complex as people have been doing here. But I always love and appreciate the discussion of GO.

 

First of all do note that partitions in memory are already given. So the partition is of Fixed type. Partitions are fixed and no new partition is going to be generated.

Hence we do not need to worry about the holes which could be created and about merging them or anything as done in Dynamic partitioning.

According to best fit algorithm 20 k job will get the third partition of size 20k. But before 20k job we have 14k job and 10k job which also will get 20k partition according to best fit algorithm and as they are earlier in the list so they get the partition first(generaly this is what we do regarding proesses if nothing is given). 14k and 10k job will complete in 11 unit time then 20k job takes 8 unit time so 20 k job will finish at 19 sec if procedure starts from 0 sec.

Comments

here we have assumed multicore cpu ? bcz even though process get space in mm , it can only pulled out when it  excutes,

---

If the CPU is a multi-core CPU, then considering times of 14k and 10k will be sufficient but if it is a uni-processor machine, then this 20k will be waiting for CPU until it turn comes i.e., it will wait until all processes from 2k until 10k gets completed, then all these process burst times + burst time of 20k should be the actual time taken for job 20k to get completed right ?

Answer 2

Partitions size in KB  4K 8K 20K 2K

                                J1  J2   J3  J4  J5  J6  J7    J8
Job sizes in KB        2K 14K 3K 6K 6K 10K 20K 2K

Time for execution     4  10  2  1  4  1   8   6

TQ = 0

Partition  Job

4K       J3

8K       J4

20K      J2

2K       J1

 

TQ = 1

Partition  Job

4K       J3(2)

8K       J5(2)

20K      J2(10)

2K       J1(4)

 

TQ = 2

Partition  Job

4K       J8(8)

8K

20K      J2(10)

2K       J1(4)

 

TQ = 4

Partition  Job

4K       J8(8)

8K

20K      J2(10)

2K

 

TQ = 10

Partition  Job

4K

8K

20K      J6(11)

2K

 

TQ = 11

Partition  Job

4K

8K

20K      J7(19)

2K