Operating system: banker algorithm

Report Download
Code download

1. Problem description

1.1 banker algorithm

The applicant shall state in advance the maximum demand for various resources. When dynamically applying for a certain type of resources during process activities, the system reviews whether the number of existing resources in the system can meet the maximum demand of the current process. If it can, it will be allocated, otherwise it will be rejected.

1.2 pseudo code

#Define N 5 / / number of processes
#Define m 3 / / resource type
int   Available[m],Alloc[n][m],Need[n][m];
main() {
   int request[m];
   input( );
   while (1) {
      read_req( ); 
      if (End of request) break;
 	  (1) if (!(requesti <= Needi))   Indicates an illegal request;
 	  (2) if (!(requesti <= Available)) be Pi Obstruction; 
	  (3)Tentative distribution
		Available=Available - Requesti;
      	Alloci=Alloci + Requesti;
      	Needi=Needi - Requesti;
 	  (4)If the new state is safe, resources are actually allocated to Pi,Otherwise, cancel the exploratory allocation.

1.3 safety state discrimination algorithm

(1) Set Finish=(false,..., false), work = available
(2) Cycle to find the process pi that meets the following conditions, and cycle up to n times: Finish[i]=false and needI < = work
(3) If found, Finish[i]=true;work=work+Alloci; Turn (2)
(4) If Finish=(true,..., true), it is safe, otherwise it is not safe.

1.4 test data

Three types of resources m=3
Number of processes n=5

The request sequence is as follows:
a) Process P2 requests resources (0, 3, 4)
b) Process P4 requests resources (1, 0, 1)
c) Process P1 requests resources (2, 0, 1)
d) Process P3 requests resources (0, 0, 2)

2. Implementation ideas

2.1 file reading

First, write the currently requested resources, maximum resource requirements and allocated resources into files. The program will read these files and process resource requests. The first number of each line of each file represents the thread, and the remaining value of each line represents the size of each resource.

2.2 tentative allocation

For each request sequence, it is first tentatively allocated to determine whether the resource request sequence can be satisfied. If yes, resources can be allocated, otherwise they cannot be allocated.
The user can input the number of sequences to be obtained, and the program will output all the request sequences that can be allocated. The process is as follows: first, an permutation is generated to represent the current resource request order. Two functions are designed to judge whether the current request is legal isLegal(int numOfReq) and whether it can meet notBlocked(int numOfReq). The parameter numOfReq represents the thread. For one of the sequences whose return value is false, resources cannot be allocated. Therefore, terminate the program, try the next request sequence and re allocate tentatively.

3. Core code

int detectiveAlloc(int permutation[]) {
	for (int i = 0; i < RESOURCE; ++i) {
		Work[i] = Available[i];
	for (int i = 0; i < PROCESS; ++i) {
		for (int j = 0; j < RESOURCE; ++j) {
			Alloc_[i][j] = Alloc[i][j];
			Need_[i][j] = Need[i][j];
	for (int i = 0; i < PROCESS; ++i) {
		// Is the request legal
		if (!isLegal(permutation[i])) {
			printf("\n %d is illegal \n", permutation[i]);
		// Is it assignable to this process
		if (!notBlocked(permutation[i])) {
			//if (i == 0);
		for (int j = 0; j < RESOURCE; ++j) {		
			// Work reduction
			Work[j] -= Request[permutation[i]][j];
			// Need reduction
			Need_[permutation[i]][j] -= Request[permutation[i]][j];
			// Alloc increase
			Alloc_[permutation[i]][j] += Request[permutation[i]][j];
		for (int k = 0; k < PROCESS; ++k) {
			bool flag = true;
			for (int j = 0; j < RESOURCE; ++j) {
				// Whether resources are released
				if (Need_[k][j] > Work[j]) {
					flag = false;
			if (flag == true && std::count(AllocOrder.begin(), AllocOrder.end(), k) == 0) {
				for (int j = 0; j < RESOURCE; ++j) {
					Work[j] += Alloc_[k][j];
	return AllocOrder.size() == PROCESS ? 1 : 0;

4. Operation results

Read the file and enter the number of request sequences:

Output the qualified request sequence and the sequence of allocating resources to the sequence:

Keywords: C C++ Operating System

Added by ryanbutler on Fri, 11 Feb 2022 09:48:15 +0200