Operating System Study 3: Process Scheduling and Deadlock-and Avoiding Deadlock with the Banker's Algorithm--NetCore Implementation

Preface

This is the third article in the operating system study series. There's a lot of content about process scheduling. The problem operating systems most easily run into when scheduling processes is deadlock, and the Banker's Algorithm is a typical deadlock-avoidance algorithm.

The Concept of Deadlock

First, let's understand the basic concept of deadlock: A set of processes competing for system resources or communicating with each other become mutually "permanently" blocked. Without external intervention, this set of processes will never be able to continue execution.

Look at the two pictures below. The left one is a state that may produce deadlock: four cars (processes) competing for the same resource (passing through an intersection). If the system schedules improperly, they will fall into a deadlock state, as shown in the right figure (each car occupies one lane (resource), and the needed lane (resource) is occupied by another car.).

Causes of Deadlock

There are mainly two reasons deadlock occurs:

• Number of resources < number of processes requesting that kind of resource (resource competition)

• Inappropriate process advancement order

  As shown in the figure below: A and B each represent a certain resource, assuming there is only one of each. Process P first occupies resource A, then process Q occupies resource B. After that, when process P wants resource B it cannot get it, and when process Q wants resource A it cannot get it either, so the system falls into a deadlock state.

Look at the figure below as well; it similarly illustrates the result of an inappropriate process advancement order:

• (1), (2), (4), (5) run normally
• (3), (6) deadlock occurs

After modifying the process advancement order, deadlock will not occur and it can run normally, as shown in the figure below:

Conditions for Deadlock

1. Mutual exclusion condition: The resources that processes compete for must be used mutually exclusively.

Mutual exclusion is an inherent property of the resource and cannot be forbidden.

2. Hold-and-wait condition: A process that currently already owns resources can still request new resources, and when blocked, it holds onto the resources it has already obtained without releasing them.

3. No-preemption condition: Resources a process has already obtained can only be released by itself after use, and cannot be preempted.

4. Circular wait condition: There exists a circular waiting chain containing at least two processes, in which each process is waiting for a resource occupied by the next process.

• The first three conditions are necessary conditions, and the circular wait condition is a necessary condition.

• The first, mutual exclusion, is an inherent property of the resource and there is no way to forbid it.

• As long as any one of the latter 3 conditions is broken, deadlock can be prevented or avoided.

Banker's Algorithm

This is a deadlock-avoidance algorithm designed by imitating the control method banks use when issuing loans. Its characteristic is that the credit limits of all customers can exceed the bank's total capital.

The goal of the Banker's Algorithm: **The sum of all customers' credit limits can exceed the bank's total capital; this is leverage. **

Main Ideas

The main ideas of the Banker's Algorithm are as follows:

1. When a user's maximum demand for funds (i.e., credit limit) does not exceed the banker's currently available funds, that user can be accepted.
2. Users can take out loans in installments, but the total of the loans cannot exceed the maximum demand.
3. When the banker's currently available funds cannot satisfy a user's remaining loan need, payment of the user's loan can be postponed, but the user can always get the loan within a finite time.
4. After a user obtains all the needed funds, they will definitely repay all funds within a finite time. (Customers have good credit and can all repay on schedule)

Example

Assume a bank's total working capital is 10000 yuan. Customer A applies for a credit limit of 4000 yuan, customer B applies for a credit limit of 6000 yuan, customer C applies for a credit limit of 10000 yuan. Since none of them exceed the bank's working capital, they are approved. Customer D applies for a credit limit of 12000 yuan, and the bank refuses. Assume A, B, and C come to the bank with the following loan applications:

• A requests a loan of 2000 yuan
• B wants a loan of 4000 yuan
• C wants a loan of 3000 yuan

The bank's strategies are as follows:

1. As long as the bank still has money, issue the loan

   If this strategy is adopted, after issuing the loans the bank has 1000 yuan left, which will be unable to satisfy any customer's credit limit, thus causing the bank to have bad debts.

2. Need to consider the risk the bank faces after issuing loans (if the bank cannot satisfy all customers' credit limits, it will be unable to recover the loans)

   If this strategy is adopted, after first issuing A's and B's loans the bank has 4000 yuan left, postpones paying C's loan, and the remaining 4000 yuan can satisfy customer A's or B's credit limit.

Further Understanding

We regard the operating system as the banker, and the resources managed by the operating system as equivalent to the funds managed by the banker. When a process makes a resource request, the system checks:

• Number of available resources Available: the bank's working capital
• Process maximum resource demand Max: credit limit
• Number of resources already allocated to the process Allocation: loans
• Number of resources the process will still need Need: credit limit - loans

The flow of the Banker's Algorithm is as follows:

• Perform resource pre-allocation
• Carry out a safety check
  • Safe: actually allocate the resources
  • Unsafe: return to the state before pre-allocation

Algorithm Implementation

Below is a flowchart of the entire Banker's Algorithm implementation process:

Explanation of the data structures involved in the implementation:

1． Available resource vector Available, which is an array containing m elements, where each element represents the number of available resources of one type. Its initial value is the total number of available resources of that type configured in the system. Its value changes dynamically with the allocation and reclamation of that type of resource. If Available[j]=k, it means there are currently k resources of type j in the system.

2． Maximum demand matrix Max, which is an n×m matrix that defines the maximum demand of each of the n processes in the system for m types of resources. If Max[i][j]=k, it means process i needs a maximum of k resources of type j.

3． Allocation matrix Allocation, which is an n×m matrix that defines the number of resources of each type currently allocated to each process in the system. If Allocation[i][j]=k, it means process i currently has already been allocated k resources of type j. Allocation[i] represents the allocation vector of process i.

4． Need matrix Need, which is an n×m matrix used to represent the number of each type of resource that each process still needs. If Need[i][j]=k, it means process i still needs k resources of type j to complete its task. Need[i] represents the need vector of process i.

The three matrices above have the relationship: Need[i][j]=Max[i][j]-Allocation[i][j]；

Algorithm process description

Request is the request vector of process i. Request[j]=k means process i requests allocation of k resources of type j. After process i issues a resource request, the system checks according to the following steps:

1． If Request ≤Need[i], go to step 2; otherwise, consider it an error, because the number of resources it requested has already exceeded its current maximum demand.

2． If Request ≤Available, go to step 3; otherwise, it means there are not yet enough resources in the system to satisfy process i's request, and process i must wait.

3． The system tentatively allocates the resources to process i, and modifies the values in the following data structures:

Available = Available - Request 

Allocation[i]= Allocation[i]+ Request

Need[i]= Need[i] - Request 

4． The system executes the safety algorithm to check whether, after this resource allocation, the system is in a safe state. If it is safe, the resources are formally allocated to process i to complete this allocation; otherwise, the tentative allocation is discarded, the original resource allocation state is restored, and process i is made to wait.

Safety Test Algorithm

1． Set two vectors.

Work: It represents the number of each type of resource the system can provide for processes to continue running. It contains m elements. When starting to execute the safety algorithm, Work = Available

Finish: It indicates whether the system has enough resources to allocate to a process so that it can run to completion. Initially Finish[i]=false; when there are enough resources to allocate to process i, set Finish[i]=true

2． Find a process from the process set that can satisfy the following conditions.

• Finish[i]= = false
• Need[i]≤work

If found, execute step 3; otherwise, execute step 4;

3． After process i obtains the resources, it can execute smoothly until completion and release the resources allocated to it, so the following should be executed

• Work = work + Allocation[i]
• Finish[i]=true
• 转向步骤2

4． If Finish[i] of all processes is true, it means the system is in a safe state; otherwise, the system is in an unsafe state.

Implementation Code

Alright, the concepts and principles have all been explained clearly. Next, I'll paste the code.

The code already has detailed comments. Although it's written in a procedural style, the structure is also quite clear.

First, define the process class

namespace OperatingSystemExperiment.Exp3 {
    public class ProcessExp3 {
        public int Id;

        /// <summary>
        /// 进程最大（各类）资源需求数：信用额度
        /// </summary>
        public int[] Max;

        /// <summary>
        /// 已分配给进程的资源：贷款
        /// </summary>
        public int[] Allocation;

        /// <summary>
        /// 进程还需要的资源：信用额度 - 贷款
        /// </summary>
        public int[] Need;

        public ProcessExp3(int id) => this.Id = id;


        public void EvaluateNeedResource()
        {
            Need = new int[Max.Length];
            for (var i = 0; i < Max.Length; i++) {
                Need[i] = Max[i] - Allocation[i];
            }
        }
    }
}

Algorithm implementation code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace OperatingSystemExperiment.Exp3 {
    public class Main {
        private int _resourceClassesCount = 0;
        private int _processCount = 0;

        private List<ProcessExp3> _processes = new List<ProcessExp3>();

        /// <summary>
        /// 系统全部可分配资源：银行流动资金
        /// </summary>
        private List<int> _resource = new List<int>();

        /// <summary>
        /// 系统剩余可分配资源
        /// </summary>
        private List<int> _available = new List<int>();

        private Main()
        {
            // 获取当前系统资源分配状态
            LoadAllAvailableResource();
            LoadProcessMaxResource();

            var continueFlag = true;
            while (continueFlag) {
                mainLoop:
                // 获取各进程已分配资源
                LoadAllocationResource();
                // 评估每个进程还需要的资源
                EvaluateNeedResource();

                // 打印各数据结构当前值
                PrintStatus();
                Console.Write("请输入要操作的进程号：");
                if (!int.TryParse(Console.ReadLine(), out var procId)) {
                    Console.WriteLine("\n请输入数字！");
                    if (QueryExit()) Environment.Exit(0);
                    else goto mainLoop;
                }

                if (procId < 0 || procId >= _processes.Count) {
                    Console.WriteLine("\n不存在进程号为 {0} 的进程！", procId);
                    if (QueryExit()) Environment.Exit(0);
                    else goto mainLoop;
                }

                Console.Write("请输入资源请求向量：");
                var request = Console.ReadLine();
                var requestVector = Array.ConvertAll(request?.Split(' '), int.Parse);

                // 检查资源请求是否合理
                var proc = _processes[procId];
                Console.WriteLine("银行家算法检验中...");
                for (var i = 0; i < requestVector.Length; i++) {
                    if (requestVector[i] > proc.Need[i]) {
                        Console.WriteLine("分配失败！资源类型 {0}，请求数量 {1}，超过进程所需数量 {2}",
                            i, requestVector[i], proc.Need[i]);
                        if (QueryExit()) Environment.Exit(0);
                        else goto mainLoop;
                    }

                    if (requestVector[i] > proc.Max[i]) {
                        Console.WriteLine("分配失败！资源类型 {0}，请求数量 {1}，超过进程最大资源数量 {2}",
                            i, requestVector[i], proc.Need[i]);
                        if (QueryExit()) Environment.Exit(0);
                        else goto mainLoop;
                    }
                }

                // 保存当前状态
                var tempAvailable = new List<int>(_available);
                var tempAllocation = (int[]) proc.Allocation.Clone();
                var tempNeed = (int[]) proc.Need.Clone();
                // 资源预分配
                for (var i = 0; i < _resourceClassesCount; i++) {
                    proc.Allocation[i] += requestVector[i];
                    proc.Need[i] -= requestVector[i];
                }

                if (SecurityEvaluate()) {
                    Console.WriteLine("正在为进程 {0} 分配资源", proc.Id);
                    // 写入资源分配文件
                    var writer = new StreamWriter(Path.Combine(
                        Environment.CurrentDirectory, "Exp3", "input", "Allocation_list.txt"), false);
                    foreach (var p in _processes) {
                        // 使用LinQ语句，构造输出行
                        var line = p.Allocation.Aggregate("", (current, allocation) => current + (allocation + " "));

                        writer.WriteLine(line.Trim());
                    }

                    Console.WriteLine("已经保存新的分配状态！");
                    writer.Close();
                }
                else {
                    Console.WriteLine("恢复试分配前的状态。");
                    // 恢复预分配之前的状态
                    _available = tempAvailable;
                    proc.Allocation = tempAllocation;
                    proc.Need = tempNeed;
                }

                continueFlag = !QueryExit();
            }
        }

        /// <summary>
        /// 安全性算法
        /// </summary>
        private bool SecurityEvaluate()
        {
            var work = _available;
            var finish = new bool[_processCount];
            var found = false; // 判断标志
            var finishCount = 0; // 满足条件的进程数目
            var safeQueue = new List<int>();

            while (finishCount < _processCount) {
                for (var procId = 0; procId < _processCount; procId++) {
                    var proc = _processes[procId];

                    if (!finish[procId]) {
                        for (var resId = 0; resId < work.Count; resId++) {
                            Debug.WriteLine("安全性测试，procId={0} resId=(1)", procId, resId);
                            if (proc.Need[resId] > work[resId]) {
                                Debug.WriteLine("NotFound! procId={0} resId={1}", procId, resId);
                                found = false;
                            }
                            else {
                                Debug.WriteLine("Found! procId={0} resId={1}", procId, resId);
                                found = true;
                            }
                        }
                    }

                    if (found) {
                        // 模拟释放资源
                        for (var t = 0; t < work.Count; t++) {
                            work[t] += proc.Allocation[t];
                        }

                        // 保存进程号
                        finish[procId] = true;
                        finishCount++;
                        // 加入安全队列
                        safeQueue.Add(procId);
                        // 重置状态
                        found = false;
                    }
                }
            }

            Console.WriteLine("安全序列如下：");
            // 打印安全序列
            var output = "";
            foreach (var procId in safeQueue) {
                output += "P" + procId + ",";
            }

            Console.WriteLine(output.TrimEnd(','));


            if (finish.Any(flag => !flag)) {
                Console.WriteLine("未通过安全性测试！");
                return false;
            }

            Console.WriteLine("已经通过安全性测试！");

            return true;
        }

        private bool QueryExit()
        {
            Console.Write("是否退出(y/n)？");
            var option = Console.ReadLine()?.ToLower();
            return option == "y";
        }

        /// <summary>
        /// 评估进程所需资源
        /// </summary>
        private void EvaluateNeedResource()
        {
            foreach (var p in _processes) {
                p.EvaluateNeedResource();
                // 计算系统还剩下多少资源
                for (var i = 0; i < _resourceClassesCount; i++) {
                    _available[i] -= p.Allocation[i];
                }
            }
        }

        /// <summary>
        /// 打印出当前状态
        /// </summary>
        private void PrintStatus()
        {
            Console.WriteLine("-------------------------银行家算法-------------------------");
            Console.WriteLine("系统进程数量：{0}；资源种类数量：{1}", _processCount, _resourceClassesCount);
            Console.WriteLine("可用资源向量 Available：");
            foreach (var i in _resource) {
                Console.Write("{0} ", i);
            }

            Console.WriteLine("\n最大需求矩阵 Max：");
            foreach (var p in _processes) {
                foreach (var t in p.Max) {
                    Console.Write("{0} ", t);
                }

                Console.WriteLine("");
            }

            Console.WriteLine("已分配矩阵 Allocation：");
            foreach (var p in _processes) {
                foreach (var t in p.Allocation) {
                    Console.Write("{0} ", t);
                }

                Console.WriteLine("");
            }

            Console.WriteLine("需求矩阵 Need：");
            foreach (var p in _processes) {
                foreach (var t in p.Need) {
                    Console.Write("{0} ", t);
                }

                Console.WriteLine("");
            }
        }

        /// <summary>
        /// 加载系统所有可用的资源数量
        /// </summary>
        private void LoadAllAvailableResource()
        {
            var reader =
                new StreamReader(Path.Combine(Environment.CurrentDirectory, "Exp3", "input", "Available_list.txt"));
            var line = reader.ReadLine();
            // 获取各类型资源数量
            _resourceClassesCount = int.Parse(line?.Trim());
            line = reader.ReadLine();
            _resource.AddRange(Array.ConvertAll(line?.Split(' '), int.Parse));
            _available.AddRange(Array.ConvertAll(line?.Split(' '), int.Parse));
            reader.Close();
        }

        /// <summary>
        /// 加载所有进程以及他们需要的最大资源
        /// </summary>
        private void LoadProcessMaxResource()
        {
            var reader =
                new StreamReader(Path.Combine(Environment.CurrentDirectory, "Exp3", "input", "Max_list.txt"));
            var line = reader.ReadLine();
            var index = 0;
            _processCount = int.Parse(line?.Trim());
            while (!reader.EndOfStream) {
                line = reader.ReadLine();
                var tempProc = new ProcessExp3(index++) {
                    Max = Array.ConvertAll(line?.Split(' '), int.Parse)
                };
                _processes.Add(tempProc);
            }

            reader.Close();
        }

        /// <summary>
        /// 获取所有进程已经分配的资源
        /// </summary>
        private void LoadAllocationResource()
        {
            var reader = new StreamReader(Path.Combine(
                Environment.CurrentDirectory, "Exp3", "input", "Allocation_list.txt"));
            var index = 0;
            do {
                var line = reader.ReadLine()?.Trim();
                _processes[index++].Allocation = Array.ConvertAll(line?.Split(' '), int.Parse);
            } while (!reader.EndOfStream);

            reader.Close();
        }

        private void EvaluateProcessNeedResource() { }

        public static void Run()
        {
            new Main();
        }
    }
}

PS: This code does not include the Program class. To run the code, you need to add a Program class and call Exp3.Main.Run(); in the Main method.

Run Results

## 

系统进程数量：5；资源种类数量：3
可用资源向量 Available：
10 5 7 
最大需求矩阵 Max：
7 5 3 
3 2 2 
9 0 2 
2 2 2 
4 3 3 
已分配矩阵 Allocation：
2 3 2 
2 0 0 
3 0 2 
2 1 1 
0 0 2 
需求矩阵 Need：
5 2 1 
1 2 2 
6 0 0 
0 1 1 
4 3 1 
请输入要操作的进程号：0
请输入资源请求向量：1 1 1
银行家算法检验中...
安全序列如下：
P0,P1,P2,P3,P4
已经通过安全性测试！
正在为进程 0 分配资源
已经保存新的分配状态！

State after reallocation:

-------------------------银行家算法-------------------------
系统进程数量：5；资源种类数量：3
可用资源向量 Available：
10 5 7 
最大需求矩阵 Max：
7 5 3 
3 2 2 
9 0 2 
2 2 2 
4 3 3 
已分配矩阵 Allocation：
3 4 3 
2 0 0 
3 0 2 
2 1 1 
0 0 2 
需求矩阵 Need：
4 1 0 
1 2 2 
6 0 0 
0 1 1 
4 3 1 

Welcome to Discuss

For questions, please leave a message on the WeChat official account backend. I will reply to every message~

• WeChat Official Account: 画星星高手
• Coding livestream: https://live.bilibili.com/11883038
• Zhihu: https://www.zhihu.com/people/dealiaxy
• Column: https://zhuanlan.zhihu.com/deali
• Jianshu: https://www.jianshu.com/u/965b95853b9f