Information Technology Reference
In-Depth Information
classResourceMgr{
private:
Locklock;
Condcv;
intr; //Numberofresources
intt; //Numberofthreads
intavail[]; //avail[i]isnumberofinstancesofresourceiavailable
intmax[][]; //max[i][j]ismaxofresourceineededbythreadj
intalloc[][]; //alloc[i][j]iscurrentallocationofresourcei
//to threadj
...
}
Figure6.9: State maintained by banker algorithm's resource manager.
Re-
source manager code is in Figures 6.10 and 6.11.
//
//Invariant:thesystemisinasafestate
//
ResourceMgr::Request(intresourceID,intthreadID){
lock.Acquire();
assert(isSafe());
while(!wouldBeSafe(resourceID,threadID)){
cv.Wait(&lock);
}
alloc[resourceID][threadID]++;
avail[resourceID]--;
assert(isSafe());
lock.Release();
}
Figure6.10: High level pseudo-code for banker's algorithm. The state main-
tained by the algorithm is defined in Figure 6.9 and the method isSafe() is
defined in Figure 6.11.
high-level approach by tracking the current allocation of each resource to each
thread, the maximum allocation possible for each thread, and the current set of
available, unallocated resources.
Figure 6.11 shows how we can test whether a state is safe. Recall that a state
is safe if there is some sequence of thread executions that will allow each thread
to gain its maximum resource need, finish its work, and release its resources.
So, we first see if the currently free resources would allow any thread to finish;
if so, then the resources held by that thread would eventually be released to the
system. Next, we see if the currently free resources plus the resources held by
the thread identified in the first step would allow any other thread to finish; if
so, both the first and second threads resources would eventually be released to
the system. We continue this process until we have identified all threads that
can be guaranteed to finish. If that set includes all of the threads, the state is
safe.
Example: Page allocation with the Bankers Algorithm. Suppose we have
a system with 8 pages of memory and three processes: A, B, and C, which
 
Search WWH ::




Custom Search