Anonymous user menu

‘best-fit’ algorithm

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 5K
Time for execution 4 10 2 1 4 1 8 6

When will the 5K job complete?


Sourav Mishra @sourav
13 Jul 2016 03:25 pm

By Best Fit algorithm we put the incoming jobs in best possible size slots. Hence, 5K job will be allocated to 8K slot but in the meantime it has to wait for the 6K jobs to complete their execution.

Now, consider the snapshot of the system with slots, incoming jobs and execution times.


                  4K                         8K                        20K                         2K

                  3K (2units)          6K (1unit)            14K (10units)         2K (4units)

                                               6K (4units)

                                               5K (6units)


Total completion time for 5K job = (1+4+6) = 11 units.

Lovely @cse23
13 Jul 2016 12:35 pm

why we are not taking time of 3K???

can u plz explain...

Sourav Mishra @sourav
13 Jul 2016 03:52 pm

3K will be allocated to 4K slot where 5K will never fit into so we are not bothering about 3K.

Here we are mainly looking for those jobs that will be allocated to 8K slot before 5K comes into picture and adding their execution times.

Lovely @cse23
15 Jul 2016 10:47 am