CSci 430: Introduction to Operating Systems

Resource Allocation Denial Simulation (Bankers Algorithm)

• How do deadlock avoidance schemes work in practice to keep deadlocks from occurring in a computing system?
• How can we programatically implement an algorithm to test whether a resource request would be safe to grant
or not?
• What information is needed about processes needs and requests in order to define their state and determine if
new resource requests are safe to grant or not?

CSci 430: Introduction to Operating Systems

Resource Allocation Denial Simulation (Bankers Algorithm)

1. You should start by implementing the needsAreMet() member function. This member function takes a process id/index as its first parameter, and an array of integers represent the current number of resources available of each resource type. This function returns a boolean result of true if the process needs are met by the currentAvailable resources, and false if they are not. Basically, in the State object there is a matrix called need, which holds the (C – A) information. Each row of this matrix is the information for a particular process. For the needsAreMet() function, you need to check each of the resource needs for the indicated process, and see if the are all <= to the indicated currentAvailable resource. If all of the needs are less than or equal to the currently available, then the process can have its needs met, and the function should return true. But if any need is greater than a current available resource, then the answer should be false from this function.
2. The next test case tests the findCandidateProcess() member function. This function should use the previous needsAreMet() function to perform its work. This function takes an array of boolean flags as its first parameter,
and an array of currentAvailable resources, the same as used by needsAreMet(). The boolean array are a set of flags that indicate whether a particular process has completed its work yet or not. When determining if a state is safe, we start by assuming all processes are still running, so all process start off with completed as false. When a process can run, we mark its completed as true. For the findCandidateProcess() function, you need to search through all of the processes in the system. The first process you find that is not yet completed, but whose needs can be met by the currentAvailable resources should be returned as the candidate process. As mentioned, you should use the needsAreMet() function to determine whether or not a particular process can have its needs met and is thus a candidate to be run to completion.
3. The next test case tests the releaseAllocatedResources() member function. This funciton will be called after a process is selected to run to completion, to return its currently allocated resources back to the currentAvailable resources. This funciton takes a process id/index as its first parameter, and the same currentAvailable array as its second parameter. The allocation array of the State class contains the current allocations of resources for each process. In this funciton you basically need to add the allocations of the indicated process to the currentAvailable vector of resources, which simulates the resources being released and returned back to the system to be used by other processes. This function is a void function, so it doesn’t return anything explicitly, but of course it does change the currentAvailable vector to update it with the released resources.
4. The final test case is for the main isSafe() member method. This method will implement the actual Banker’s algorithm to determine if the State is a safe or unsafe. This function doesn’t take any input, it uses the current state defined by the matrices and vectors of the State object to perform its task. The function does return a boolean value of true if the state is safe, or false if the state is unsafe.

DETAILED ASSIGNMENT

20201013200026assg03