FOR FREE CONTENT

Some related GATE questions 

Q. GATE 1994-1.24

Consider the following heap (figure) in which blank regions are not in use and hatched regions are in use.

The sequence of requests for blocks of sizes 300,25,125,50 can be satisfied if we use

a) Either first fit or best-fit policy (anyone) 

b) First fit but not best-fit policy   

c) Best fit but not first fit policy   

d) None of the above

Answer:

Let’s work with First Fit (FF) first,

# Initially 300K comes and fits at the location with the size 350K and creates a hole of 50K. 

# Now 25K process come and allocates location 150K as the first fit and create a hole of 125K.

# Now process with size 125K come and allocate at immediate free hole 125K.

# Now another process 50K came and allocate at remaining hole 50K.

All the processes allocated properly by First-Fit.

Now working Best fit.

# First process 300K come and allocate the best place at 350K hole and create a hole of 50K.

# Now next process 25K come and allocated at the smallest possible unit of the place of 50K hole, and create a hole of 25K.

# Next process 125K came and allocated at the smallest possible unit of the place of 150K hole, and create a hole of 25K.

# Next process 50K came but there is no place to allocate 50K, here two-hole of 25K available;

So, the Best fit is not appropriate.

So, option b is correct.

Q. Gate 1996

A 1000 Kbyte memory is managed using variable partitions but no compaction. It currently has two partitions of sizes 200 Kbyte and 260 Kbyte respectively. The smallest allocation request in Kbyte that could be denied is for

a) 151             

b) 181           

c) 231           

d) 541

Answer: 

Total 1000 KB and allocated space partition 200 KB and 260 KB. So, the free location right now in 1000kb is 540 KB.

Now how we allocate the said partition 200 KB and 260 KB that we will get the smallest size of partition.

So, the smallest allocation request in Kbyte that could be denied is for b) 181 correct answer.

# But if it asks the largest allocation request in KB which could be denied is for 541 KB.

Q. Gate 1998

In a computer system where the 'best fit' algorithm is used for allocating 'jobs' to 'memory partition', the following situation was encountered.

When will the 20 K job complete?

Answer:

Here we allocated the job as per best fit and also mention the execution time of the process. And we also assume that it FCFS Scheduling.

So, as per table 20 K job complete at time 19.