GATE1998-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

Is all the process will run at same time?

I think ,only one process can be assign to CPU at a time.

If we take first come first serve ,3k process will take 0to2 unit of time then ,6k 2-3,14k 4-13,2k 14-17,10k 17-18,20k 19-27.....

Is any thing wrong

,

---

answer is 19 units.

---

Can we schedule J8 before j5.6.7?

---

i think yes because all the processes are there in the system already and we will schedule J8 from t=2 to t=8.

may be i am wrong. Please correct

---

I also think yes. Since nothing is mentioned I've taken the order in which it is given J1 to J8 (FCFS). Had it been mentioned we could have ordered the jobs for their respective partitions according to which one takes lesser BT schedule that one first. In this kind of questions we don't consider such things. We simply take the order in FCFS manner. Am I correct?

---

The important thing to understand here is that this is related to Fixed Partitioning, since the partitions have been initially mentioned explicitly..

---

Why not to use Fcfs?

---

@Swapnil Naik because all the job is initial available 

---

@Tuhin Dutta it is the static allocation so the J8 should go in the 2K slot even though the 4K is empty before 2K slot,

---

Jobs	Job size	Ex. Time
1	2k	4
2	14k	10
3	3k	2
4	6k	1
5	6k	4
6	10k	1
7	20k	8
8	2k	6

 

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
4k	3	3	8	8	8	8	8	8
8k	4	5	5	5	5
20k	2	2	2	2	2	2	2	2	2	2	6	7	7	7	7	7	7	7	7
2k	1	1	1	1

 

---

That was nice and clear explanation..thanks.

---

@Kushagra गुप्ता Here should we assume like it is a multicore CPU?

---

did u get the answer , i have same doubt .

---

Is the cpu considered as multicore?

---

nice explanation thanks

Answer 1

Partitons are $4k , 8k, 20k,  2k$, now due to best fit algo,

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 partition 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$ to $11$). Now, $20 k$ is also waiting for partition of $20k$, because it is 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 .

Answer should be $19$ units.

Comments

Can you please explain why would the first 2K job execute for 2 units of time instead of the given 4 units?

---

Which scheduling algorithm should be considered here? as it is not given in the question. And should this be considered fixed partitioning or dynamic partitioning? @Arjun Sir

---

There are two 6k requests in the question and you have considered only 1,

the first 6k request will be satisfied by the 20k partition executing 14k request, and from the next 6k request your answer will apply, 

Although answer will be same, at 19s.

---

Why is the execution time for each partition starting from 0?
CPU can execute each alloted process one-by-one.
Therefore only one process can be asigned to the cpu at atime
for eg: 2k job exectues from 0-4 units
          4k job should execute from 4-14 units

---

No, don't consider CPU scheduling as it is not mentioned. 

Whenever the context is partitioning or allocation using best fit etc Consider the execution time  as the time for which a process will occupy a partition. These kind of questions should be dealt in this way.

---

Ohhk... Thankz bro :-)

---

when will J8 complete execution at 8 time units or 25 units?

---

8 time units

---

I have a doubt.

After we put '14K' process into '20K' partition, there'll be '6K' left. The next '6K' can be put into it instead of '8K' partition. This delays the execution of '20K' process by one unit.

So, shouldn't the answer be 20?

Please correct me if I'm missing anything here.

---

One partition can hold only one job at a time

---

Why? I mean there's empty space for a whole process, but it can't be used.

Can a partition hold only one process in static partitioning? (consider this question is about static partitioning)

---

Yes in case of static partitioning one partition can hold only one job at a time. Rest free space is treated as internal fragmentation.

---

Please explain me . I did not get how to consider the execution [email protected] Shivansh Gupta

---

try to write 4 partitions and allot the partitions according to availability, within the available partitions choose the best fit. Just do this until 20K process completes. While doing this keep track of the start and end times of each job. Or it will also be clear from the pic above by Tuhin Dutta

---

But here nothing is mentioned about static partitioning so if we consider that the intermediate contiguous holes created after any allocation are clubbed together to form a bigger hole and then that can be allocated to fit some process...It will lead to answer as 18 time units. Please check

---

@Tuhin Dutta

In question it's not specifically mentioned that we gotta consider STATIC-PARTITIONING so why we're allowing only one-process in a partition at a time?

---

How can two processes run in a single partition at a time? Their memory address can't overlap. One process can't access another process memory. There will be permission issues, segmentation fault and both processes would go haywire.

---

@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.

Answer 5

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 ?