Linux死锁现象及分析
1. 什么是死锁?
死锁(DeadLock)是指两个或者两个以上的进程(线程)在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程(线程)称为死锁进程(线程)。由于资源占用是互斥的,当某个进程提出申请后,使得有关进程(线程)在无外力协助下,永远分配不到必需的资源而无法继续进行,这就产生了一种特殊现象——死锁。
一种交叉持锁死锁的情形,此时执行程序中两个或多个线程发生永久堵塞(等待),每个线程都在等待被其他线程占用并堵塞了的资源。例如,如果线程1锁住了记录A并等待记录B,而线程2锁住了记录B并等待记录A,这样两个线程就发生了死锁现象。在计算机系统中,如果系统的资源分配策略不当,更常见的可能是程序员写的程序有错误等,则会导致进程因竞争资源不当而产生死锁的现象。
2. 产生死锁的四个必要条件
1)对临界资源的互斥使用(资源独占)
一个资源每次只能给一个进程(线程)使用。比如写操作
2) 占有且等待
进程在申请新的资源的同时,保持对原有资源的占有。
3) 不可抢占
资源申请者不能强行从资源占有者手中夺取资源,资源只能由占有者自愿释放。
4)循环等待
P1等待P2占有的资源,P2等待P3占有的资源, …, Pn等待P1占有的资源,形成一个进程等待回路。
3. 死锁避免、银行家算法
4. 实战
1.运行第三步中的代码实例,验证不同情况下的资源请求,系统是否安全。对程序进行修改,要求在判断到系统处于安全状态后,还需输出安全序列。
2.在进程同步的实验中,关于生产者和消费者问题,编写可以产生死锁的程序,运行后对结果加以分析。
银行家算法【源程序】
代码
banker.c
#include<stdio.h> #include<stdlib.h> int main() { int n ,m,t,w,flag1=1,flag2=1,flag4=1,flag5=1; int*Available,*Request,*Finish; int **Allocation,**Max,**Need,**Work; FILE*fp; fp=fopen("/root/os/jsss-12/data.txt","r"); //打开.txt文件 fscanf(fp,"%d",&n),fscanf(fp,"%d",&m); //赋值.txt文件的数值,n*m二维数组 Available = (int*)malloc(sizeof(int)*m); //开动态一维数组 for(int i=0;i<m;i++) //给一维数组赋值 fscanf(fp,"%d",&Available[i]); Allocation= (int**)malloc(sizeof(int*)*n); //开动态二维数组 Max= (int**)malloc(sizeof(int*)*n); Need= (int**)malloc(sizeof(int*)*n); for (int i = 0; i < n; i++) { Allocation[i] = (int*)malloc(sizeof(int)*m); Max[i] = (int*)malloc(sizeof(int)*m); Need[i] = (int*)malloc(sizeof(int)*m); } for(int i=0;i<n;i++) //给二维数组赋值 { fscanf(fp,"%d",&t); //t为进程编号 for(int j=0;j<m;j++) fscanf(fp,"%d",&Allocation[t][j]); for(int j=0;j<m;j++) fscanf(fp,"%d",&Max[t][j]); for(int j=0;j<m;j++) Need[i][j]=Max[i][j]-Allocation[i][j]; } for(int i=0;i<m;i++) for(int j=0;j<n;j++) Available[i]-=Allocation[j][i]; fscanf(fp,"%d",&w); //w为发出请求的进程的编号 Request = (int*)malloc(sizeof(int)*m); for(int i=0;i<m;i++) fscanf(fp,"%d",&Request[i]); for(int i=0;i<m;i++) if(Request[i]>Need[w][i]) flag1=0; if(!flag1) //flag1用来判断Request是否小于等于Need printf("Flase\n"); else { for(int i=0;i<m;i++) if(Request[i]>Available[i]) flag2=0; if(!flag2) //flag2用来判断Request是否小于等于Available printf("p %d 等待\n",w); else { for(int i=0;i<m;i++) //假设系统把申请的资源分给进程 { Available[i]-=Request[i]; Allocation[w][i]+=Request[i]; Need[w][i]-=Request[i]; } Work= (int**)malloc(sizeof(int*)*n); for (int i = 0; i < n; i++) Work[i] = (int*)malloc(sizeof(int)*m); Finish = (int*)malloc(sizeof(int)*n); for(int i=0;i<n;i++) Finish[i]=0; //fnish[i]=0代表fnish[i]=flase,fnish[i]=1代表fnish[i]=true for(int i=0;i<n;i++) for(int j=0;j<m;j++) Work[i][j]=Available[j]; while(flag5) //安全性算法,flag5用来判断系统是否已经完成安全性判断 { for(int i=0;i<n;i++) //每次从0号进程开始搜索是否有满足条件的进程 { int flag3=1; //flag3用来判断Need是否小于等于Work for(int j=0;j<m;j++) if(Need[i][j]>Work[i][j]) flag3=0; if(!Finish[i]&&flag3) //找到满足Finish[i]=false且Need小于等于Work { Finish[i]=1; //置Finish[i]=true for(int j=0;j<n;j++) //释放进程所占全部资源 for(int k=0;k<m;k++) if(j!=i&&!Finish[j]) Work[j][k]=Work[i][k]+Allocation[i][k]; break; } else if(i==n-1) //没有找到满足条件的并且是最后一个进程 { for(int j=0;j<n;j++) if(!Finish[j]) flag4=0; if(flag4) //flag4用来判断是否所有进程都是Finish[i]=true { printf("系统处于安全状态\n"); printf("Work:\n"); for(int j=0;j<n;j++) //输出安全状态下,系统把申请的资源分配给进程资源的情况 { for(int k=0;k<m;k++) printf("%4d",Work[j][k]); printf("\n"); } printf("Alllcation:\n"); for(int j=0;j<n;j++) { for(int k=0;k<m;k++) printf("%4d",Allocation[j][k]); printf("\n"); } printf("Need:\n"); for(int j=0;j<n;j++) { for(int k=0;k<m;k++) printf("%4d",Need[j][k]); printf("\n"); } printf("Available:\n"); for(int j=0;j<m;j++) printf("%4d",Work[n-1][j]+Allocation[n-1][j]); printf("\n"); flag5=0; } else{ printf("系统处于不安全状态\n"); for(int j=0;j<m;j++) //系统不安全,还原资源分配给进程前的情况 { Available[j]+=Request[j]; Allocation[w][j]-=Request[j]; Need[w][j]+=Request[j]; } flag5=0; } } } } } } }
运行结果
data.txt 说明
验证数据:建立在程序目录下建立data文件,文件内容是:
5 3
10 5 7
0 0 1 0 7 5 3
1 2 0 0 3 2 2
2 3 0 2 9 0 2
3 2 1 1 2 2 2
4 0 0 2 4 3 3
1 1 0 2
4 3 3 0
0 0 2 0
第一行:5个进程,3种资源。
第二行:每种资源系统拥有的最大数量。
3-7行:第一列是进程号(按顺序排),2-4列是Allocation(已有资源)向量,5-7列是Max(最大资源需求量)向量。
8-10行:第一列是进程号,2-4列是Request(资源请求)向量。
运行程序,通过命令行参数指定文件,如: ./banker ./data运行。
fp=fopen("/home/student/data.txt","r"); //打开.txt文件 //改成自己data.txt所在的绝对路径 fp=fopen("/root/os/jsss-12/data.txt","r"); //打开.txt文件
[root@centos-7 jsss-12]# ls banker banker.c data.txt [root@centos-7 jsss-12]# pwd /root/os/jsss-12
开始验证
1.验证第一个资源请求
//data.txt.文件
5 3 10 5 7 0 0 1 0 7 5 3 1 2 0 0 3 2 2 2 3 0 2 9 0 2 3 2 1 1 2 2 2 4 0 0 2 4 3 3 1 1 0 2
输出结果:
2.验证第二个资源请求
/data.txt文件/
5 3 10 5 7 0 0 1 0 7 5 3 1 2 0 0 3 2 2 2 3 0 2 9 0 2 3 2 1 1 2 2 2 4 0 0 2 4 3 3 4 3 3 0
输出结果:
3.验证第三个资源请求
/data.txt文件/
5 3 10 5 7 0 0 1 0 7 5 3 1 2 0 0 3 2 2 2 3 0 2 9 0 2 3 2 1 1 2 2 2 4 0 0 2 4 3 3 0 0 2 0
输出结果:
4.验证资源请求出错(即Request i>Need i)
/data.txt文件/
5 3 10 5 7 0 0 1 0 7 5 3 1 2 0 0 3 2 2 2 3 0 2 9 0 2 3 2 1 1 2 2 2 4 0 0 2 4 3 3 3 0 2 1
输出结果:
5.验证进程资源请求等待(即Request i>Available)
/data.txt文件/
5 3 10 5 7 0 0 1 0 7 5 3 1 2 0 0 3 2 2 2 3 0 2 9 0 2 3 2 1 1 2 2 2 4 0 0 2 4 3 3 0 4 4 3
输出结果:
输出安全序列【改进程序 】
代码
新增变量
//list数组用来存放安全序列 int *list;//安全序列 list=(int*)malloc(sizeof(int)*n); for(int i=0;i<n;i++) //给安全序列赋值 list[i]=0; //l变量来移动赋值list int l=0;//用来移动 list
新增语句
在if(!Finish[i]&&flag3)
添加赋值语句list[l++]=i;
在if(flag4)
中添加输出语句
printf("安全序列\n"); for(int i=0;i<n;i++) printf("%4d",list[i]); printf("\n");
banker2.c
#include<stdio.h> #include<stdlib.h> int main() { int n ,m,t,w,flag1=1,flag2=1,flag4=1,flag5=1; int*Available,*Request,*Finish; int **Allocation,**Max,**Need,**Work; int *list;//安全序列 FILE*fp; fp=fopen("/root/os/jsss-12/data.txt","r"); //打开.txt文件 fscanf(fp,"%d",&n),fscanf(fp,"%d",&m); //赋值.txt文件的数值,n*m二维数组 Available = (int*)malloc(sizeof(int)*m); //开动态一维数组 for(int i=0;i<m;i++) //给一维数组赋值 fscanf(fp,"%d",&Available[i]); Allocation= (int**)malloc(sizeof(int*)*n); //开动态二维数组 Max= (int**)malloc(sizeof(int*)*n); Need= (int**)malloc(sizeof(int*)*n); list=(int*)malloc(sizeof(int)*n); for(int i=0;i<n;i++) //给安全序列赋值 list[i]=0; int l=0;//用来移动 list for (int i = 0; i < n; i++) { Allocation[i] = (int*)malloc(sizeof(int)*m); Max[i] = (int*)malloc(sizeof(int)*m); Need[i] = (int*)malloc(sizeof(int)*m); } for(int i=0;i<n;i++) //给二维数组赋值 { fscanf(fp,"%d",&t); //t为进程编号 for(int j=0;j<m;j++) fscanf(fp,"%d",&Allocation[t][j]); for(int j=0;j<m;j++) fscanf(fp,"%d",&Max[t][j]); for(int j=0;j<m;j++) Need[i][j]=Max[i][j]-Allocation[i][j]; } for(int i=0;i<m;i++) for(int j=0;j<n;j++) Available[i]-=Allocation[j][i]; fscanf(fp,"%d",&w); //w为发出请求的进程的编号 Request = (int*)malloc(sizeof(int)*m); for(int i=0;i<m;i++) fscanf(fp,"%d",&Request[i]); for(int i=0;i<m;i++) if(Request[i]>Need[w][i]) flag1=0; if(!flag1) //flag1用来判断Request是否小于等于Need printf("Flase\n"); else { for(int i=0;i<m;i++) if(Request[i]>Available[i]) flag2=0; if(!flag2) //flag2用来判断Request是否小于等于Available printf("p %d 等待\n",w); else { for(int i=0;i<m;i++) //假设系统把申请的资源分给进程 { Available[i]-=Request[i]; Allocation[w][i]+=Request[i]; Need[w][i]-=Request[i]; } Work= (int**)malloc(sizeof(int*)*n); for (int i = 0; i < n; i++) Work[i] = (int*)malloc(sizeof(int)*m); Finish = (int*)malloc(sizeof(int)*n); for(int i=0;i<n;i++) Finish[i]=0; //fnish[i]=0代表fnish[i]=flase,fnish[i]=1代表fnish[i]=true for(int i=0;i<n;i++) for(int j=0;j<m;j++) Work[i][j]=Available[j]; while(flag5) //安全性算法,flag5用来判断系统是否已经完成安全性判断 { for(int i=0;i<n;i++) //每次从0号进程开始搜索是否有满足条件的进程 { int flag3=1; //flag3用来判断Need是否小于等于Work for(int j=0;j<m;j++) if(Need[i][j]>Work[i][j]) flag3=0; if(!Finish[i]&&flag3) //找到满足Finish[i]=false且Need小于等于Work { list[l++]=i; Finish[i]=1; //置Finish[i]=true for(int j=0;j<n;j++) //释放进程所占全部资源 for(int k=0;k<m;k++) if(j!=i&&!Finish[j]) Work[j][k]=Work[i][k]+Allocation[i][k]; break; } else if(i==n-1) //没有找到满足条件的并且是最后一个进程 { for(int j=0;j<n;j++) if(!Finish[j]) flag4=0; if(flag4) //flag4用来判断是否所有进程都是Finish[i]=true { printf("系统处于安全状态\n"); printf("Work:\n"); for(int j=0;j<n;j++) //输出安全状态下,系统把申请的资源分配给进程资源的情况 { for(int k=0;k<m;k++) printf("%4d",Work[j][k]); printf("\n"); } printf("Alllcation:\n"); for(int j=0;j<n;j++) { for(int k=0;k<m;k++) printf("%4d",Allocation[j][k]); printf("\n"); } printf("Need:\n"); for(int j=0;j<n;j++) { for(int k=0;k<m;k++) printf("%4d",Need[j][k]); printf("\n"); } printf("Available:\n"); for(int j=0;j<m;j++) printf("%4d",Work[n-1][j]+Allocation[n-1][j]); printf("\n"); printf("安全序列\n"); for(int i=0;i<n;i++) printf("%4d",list[i]); printf("\n"); flag5=0; } else{ printf("系统处于不安全状态\n"); for(int j=0;j<m;j++) //系统不安全,还原资源分配给进程前的情况 { Available[j]+=Request[j]; Allocation[w][j]-=Request[j]; Need[w][j]+=Request[j]; } flag5=0; } } } } } } }
运行结果
3