什么是死锁、
在多道程序环境中，多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态，这种情况叫做死锁。死锁是指两个或两个以上的进程（线程）在运行过程中因争夺临界资源而造成的一种僵局。
例如，某计算机系统中只有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2 所占用，而P2在未释放打印机之前，又提出请求使用正被P1占用着的输入设备。当这两个设备都在被使用时，请求的进程将会被阻塞，这样两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。
关于死锁的一些结论：
- 参与死锁的进程数至少为两个。
- 参与死锁的所有进程均等待资源。
- 参与死锁的进程至少有两个已经占有资源。
- 死锁会浪费大量系统资源，甚至导致系统崩溃，但是死锁一般不会导致cpu占用率提升，因为发生死锁时进程会被阻塞，cpu会执行其他进程。
产生死锁的四个必要条件、
- 1、 互斥条件：至少有一个资源处于非共享模式，即一次仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待直到该资源被其他进程释放为止。
- 2、不可抢占资源：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。
- 3、 占有并等待：进程已经占有了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程等待该资源并且被阻塞，但对自己已获得的资源保持不放。
- 4、循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被 链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, …, pn}，其中Pi等 待的资源被P(i+1)占有（i=0, 1, …, n-1)，Pn等待的资源被P0占有。
以上这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。
死锁处理方法、
一般来说，处理死锁问题有三种方法：
- 通过协议来预防或者避免死锁，确保系统不会进入状态
- 可用允许系统进入死锁状态，然后检测它并加以恢复
- 可以忽略这个问题，认为死锁不会出现在系统中
第三种方案为大多数系统所采用，包括windows和linux。因此程序员应该保证编写的程序不会出现死锁或者编写相应的死锁处理程序。
预防死锁、
发生死锁有四个必要条件，只要破坏其中一个就可以避免发生。
破坏“互斥”条件：就是在系统里取消互斥。也就是说至少有一个资源是非共享的，相反，可共享资源不要求互斥访问。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说在所列的四个条件中，“互斥”条件是无法破坏的。不过系统中也有这个类似的例子，例如只读的文件是共享资源，无论多少个进程来读取都不会出问题。
破坏“占有并等待”条件：破坏“占有并等待”条件，就是在系统中不允许进程在已获得某种资源的情况下，申请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。
- 方法一：进程一次申请所需的全部资源，即 “ 一次性分配”。
- 方法二：要求每个进程提出新的资源申请前，释放它所占有的资源。即“先释放后申请”。
这两种方法效率都较差，原因是会浪费大量的时间占有资源但是却不使用资源，真正使用资源也许就一会，但是却占据了大量的时间。而且可能会发生饥饿，如果一个进程需要多个常用的资源，可能必须永久等待，因为在它所需要的资源中至少有一个已分配给其他进程。
破坏“不可抢占”条件：破坏“不可抢占”条件就是允许进程对其他进程的资源实行抢夺。
- 方法一：占有某些资源的进程申请其他资源的请求被拒绝时，则该进程必须释放已占有的资源，如果有必要，可再次请求这些资源和另外的资源。
- 方法二：设置进程优先级，优先级高的进程可以抢占其他进程的资源。
破坏“循环等待”条件：将系统中的所有资源统一编号，所有进程必须按照资源编号顺序提出申请。
避免死锁的一些常用方法、
- 加锁顺序：线程按照一定的顺序加锁。例如使用std::lock()，std::lock() 函数可接受任意数量的互斥量， 该函数要么对所有参数互斥量都成功上锁，要么一个也不上锁。 比如， 已经对 ma 和 mb 上锁，但对 mc 上锁失败时， 会自动的 释放 ma 和 mb 的锁。解锁顺序不影响死锁的发生。
- 加锁时限：线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁。例如try_lock()函数会尝试加锁，还有其他的函数可以在一定的时间内尝试加锁。
- 死锁检测：每当一个线程获得了锁，会在线程和锁相关的数据结构中（map、graph等等）将其记下。除此之外，每当有线程请求锁，也需要记录在这个数据结构中。
死锁恢复、
当检测算法检测到系统存在死锁时，有多种解决方法。一种是通知系统管理员来处理死锁；另一种可能是让系统自行从死锁中恢复过来。打破死锁有两种选择，一个是简单的终止一个或多个进程来打破循环等待；另一个是从一个或多个死锁进程那里抢占一个或多个资源。
（1）进程终止：通过终止进程来消除死锁有两种方法，这两种方法都允许系统收回终止进程的所有分配资源。
- 终止所有死锁进程。这种方法显然会打破死锁环，但是代价太大。
- 一次终止一个进程，直到消除死锁循环为止。这种方法的开销会相当大，因为每次终止一个进程都要调用死锁检测算法来确认是否仍然有进程处于死锁。
终止一个进程并不简单，如果进程正在执行某种如活动如更新文件，那么终止它回会使得文件处于不稳定的状态。
如果采用了部分终止，那么我们应该确认哪些进程应该被终止。这个类似于CPU调度决策，是策略决策。这个基本上是最小代价的问题，我们应该终止最小代价的进程，然而最小代价并不精确，许多因素都可以影响，如进程优先级，进程执行了多久等等。。。
（2）资源抢占：通过抢占资源来消除死锁，我们不断抢占一些进程的资源以便给其他进程使用，直到死锁循环被打破为止。
这个方案需要处理三个问题：
- 选择牺牲进程：抢占哪些资源和哪些进程？与进程终止一样，要确认抢占的顺序，使得代价最小。
- 回滚：如果从一个进程那里抢占了一个资源，那么应该对该进程做些什么安排？显然，该进程不能够正常执行，它缺少了某些资源。我们应该将该进程回滚到某个安全状态，以便从该状态重启进程。但是很难确定什么是安全状态，最简单是方法是重新执行该进程，但是代价又很大。
- 饥饿：如何确保不会发生饥饿？即如何保证资源不会总是从同一个进程中被抢占。如果一个进程总是被选为牺牲进程，那么该进程很可能永远都完成不了任务。
经典资源分配算法--银行家算法、
#include<iostream>
#include<thread>
#include<unistd.h>
#include<sys/types.h>
#include<sys/wait.h>
#include<mutex>
#include<sys/ipc.h>
#include<vector>
#include<sys/shm.h>
#include<errno.h>
#include<cstring>
#include<vector>
using std::mutex,std::cout,std::cin,std::endl,std::lock_guard,std::vector;
//共享内存块
struct sm_memory
{
mutex sm_mutex;
};
//判断系统是否安全函数
bool safe(sm_memory* pt) noexcept;
//初始化函数
void init(sm_memory* pt) noexcept;
//银行家算法函数
void bank_algorithm(sm_memory* pt) noexcept;
//进程数
size_t process_count = 0;
//资源数量
size_t resource_count = 0;
//最大进程数
const size_t max_process = 50;
//最大资源数
const size_t max_resource = 100;
//可用资源数组
vector<int> avaliable(max_resource,0);
//最大需求矩阵
vector<vector<int>> max(max_process,vector<int>(max_resource,0));
//分配矩阵
vector<vector<int>> allocation(max_process,vector<int>(max_resource,0));
//需求矩阵
vector<vector<int>> need(max_process,vector<int>(max_resource,0));
//进程需要资源数量
vector<vector<int>> request(max_process,vector<int>(max_resource,0));
//系统是否有足够的资源分配
vector<bool> finish(max_process,false);
//记录序列
vector<int> record(max_process,0);
//进程线程同步输出函数
template<class...Args>
void print(sm_memory* pt,const Args&...args) noexcept
{
lock_guard<mutex> m{pt->sm_mutex};
((cout << args),...);
fflush(stdout);
}
//进程线程同步输入函数
template<class T>
void input(sm_memory* pt,T& val) noexcept
{
lock_guard<mutex> m {pt->sm_mutex};
cin >> val;
}
//出现错误函数
void unix_error(const char* msg) noexcept
{
cout << msg;
exit(0);
}
//创建共享内存
static int shmid = 0;
static key_t key = 0;
sm_memory* create_shared_memory() noexcept
{
key = ftok("./makefile",114514);
if(key < 0)
{
unix_error("create key error\n");
}
shmid = shmget(key,sizeof(sm_memory),IPC_CREAT | IPC_EXCL | 0666);
if(shmid < 0)
{
if(errno == EEXIST)
{
shmid = shmget(key,sizeof(sm_memory),0666);
}
else
{
unix_error("create shared memory error\n");
}
}
sm_memory* sm = static_cast<sm_memory*>(shmat(shmid,nullptr,0));
if(reinterpret_cast<int64_t>(sm) == -1)
{
shmctl(shmid,IPC_RMID,nullptr);
unix_error("map shared memory error\n");
}
memset(sm,0,sizeof(sm_memory));
new(sm)sm_memory;
return sm;
}
//删除共享内存
void delete_shared_memory(sm_memory* sm,int id) noexcept
{
if(shmdt(sm) < 0)
{
cout << "disconnect shared memory error" << endl;
}
if(shmctl(id,IPC_RMID,nullptr) < 0)
{
cout << "delete shared memory error" << endl;
}
}
//初始化函数
void init(sm_memory* pt)noexcept
{
print(pt,"请输入进程的数目: ");
input(pt,process_count);
print(pt,"请输入资源的种类: ");
input(pt,resource_count);
print(pt,"请输入每个进程最多所需的各资源数量,按照矩阵输入: ");
for(int i = 0;i < process_count;++i)
{
for(int j = 0;j < resource_count;++j)
{
input(pt,max[i][j]);
}
}
print(pt,"请输入每个进程已分配的个资源数量，按照矩阵输入：");
for(int i = 0;i < process_count;++i)
{
for(int j = 0;j < resource_count;++j)
{
input(pt,allocation[i][j]);
need[i][j] = max[i][j] - allocation[i][j];
if(need[i][j] < 0)
{
print(pt,"您输入的第",i+1,"个进程所拥有的第",j+1,"个资源数错误，请重新输入：\n");
--j;
continue;
}
}
}
print(pt,"请输入各资源现有的数目：");
for(int i = 0;i < resource_count;++i)
{
input(pt,avaliable[i]);
}
}
//银行家算法
void bank_algorithm(sm_memory* pt) noexcept
{
int i = 0,pid = 0;
char str = '\0';
while(1)
{
flag :
print(pt,"请输入要申请资源的进程号(第一个进程号为0,以此类推)：");
input(pt,pid);
if(pid < 0 || pid > process_count - 1)
{
print(pt,"输入进程号错误，请重新输入！\n");
goto flag;
}
print(pt,"请输入该进程所请求的各资源的数量：");
for(i = 0;i < resource_count;++i)
{
input(pt,request[pid][i]);
}
for(i = 0;i < resource_count;++i)
{
if(request[pid][i] > need[pid][i])
{
print(pt,"输入的请求数超过进程的最大需求量，请重新输入。\n");
goto flag;
}
if(request[pid][i] > avaliable[i])
{
print(pt, "您输入的请求数超过系统有的资源数，请重新输入!\n");
goto flag;
}
}
for(i = 0;i < resource_count;++i)
{
avaliable[i] -= request[pid][i];
allocation[pid][i] += request[pid][i];
need[pid][i] -= request[pid][i];
}
if(safe(pt))
{
print(pt,"同意分配请求!\n");
}
else
{
print(pt,"请求被拒绝！\n");
for(i = 0;i < resource_count;++i)
{
avaliable[i] += request[pid][i];
allocation[pid][i] -= request[pid][i];
need[pid][i] += request[pid][i];
}
}
for(i = 0;i < process_count;++i)
{
finish[i] = false;
}
print(pt,"各进程当前的资源量：");
for(int m = 0;m < process_count;++m)
{
for(int n = 0;n < resource_count;++n)
{
print(pt,allocation[m][n]," ");
}
}
print(pt,"\n");
print(pt,"当前剩余的资源量：");
for(int m = 0;m < resource_count;++m)
{
print(pt,avaliable[m]," ");
}
print(pt,"\n");
print(pt,"还需要再次分配吗? Y/N : ");
input(pt,str);
if(str == 'Y' || str == 'y')
{
continue;
}
else
{
break;
}
}
}
//判断系统是否安全
bool safe(sm_memory* pt) noexcept
{
int i = 0,j = 0,l = 0,k = 0;
vector<int> work(max_resource,0);
for(i = 0;i < resource_count;++i)
{
work[i] = avaliable[i];
}
for(i = 0;i < process_count;++i)
{
finish[i] = false;
}
for(i = 0;i < process_count;++i)
{
if(finish[i])
{
continue;
}
else
{
for(j = 0;j < resource_count;++j)
{
if(need[i][j] > work[j])
{
break;
}
}
if(j == resource_count)
{
finish[i] = true;
for(k = 0;k < resource_count;++k)
{
work[k] += allocation[i][k];
}
record[l++] = i;
i = -1;
}
else
{
continue;
}
}
if(l == process_count)
{
print(pt,"系统是安全的!\n");
print(pt,"安全序列: ");
for(i = 0;i < l;++i)
{
print(pt,record[i]);
if(i != l - 1)
{
print(pt,"-->");
}
}
print(pt,"\n");
return true;
}
}
print(pt,"系统是不安全的！\n");
return false;
}
int main()
{
sm_memory* sm = create_shared_memory();
init(sm);
bank_algorithm(sm);
delete_shared_memory(sm,shmid);
return 0;
}
Comments NOTHING