search
Log In
0 votes
72 views
The banker’s algorithm is being run in a system with $m$ resource classes and $n$ processes. In the limit of large $m$ and $n,$ the number of operations that must be performed to check a state for safety is proportional to $m^{a} n^{b}.$ What are the values of $a$ and $b?$
in Operating System 72 views

1 Answer

0 votes
Each process has an array(size = m) of resources allocated to it.

Ex: $$P_i = [r_1, r_2, r_3, ...., r_m]$$

To check for a safe state:

In first loop, we may find a process that can be executed with the available resources and this takes O(mn).

In second loop, we have (n-1) processes and time complexity is O((n-1)m).

...

...

In last loop, we need to check for that single process whether it can be executed or not, time complexity = O(m)

So, total time complexity = $$O(m(n+(n-1)+(n-2)+.....+1)) = O(m^1n^2)$$

a = 1, b = 2

Related questions

2 votes
0 answers
1
0 votes
2 answers
2
0 votes
1 answer
4
...