进程、线程知识点总结和同步(消费者生产者,读者写者三类问题)、互斥、异步、并发、并行、死锁、活锁的总结

  1. 云栖社区>
  2. 博客>
  3. 正文

进程、线程知识点总结和同步(消费者生产者,读者写者三类问题)、互斥、异步、并发、并行、死锁、活锁的总结

ghost丶桃子 2016-05-19 15:26:48 浏览2660

进程和程序:

进程:是个动态的概念,指的是一个静态的程序对某个数据集的一次运行活动,而程序是静态的概念,是由代码和数据组成的程序块而已。

进程5大特点:动态性,并发性,独立运行性,异步性,和结构化的特性。

在多道程序环境下,程序不能独立运行,操作系统所有的特征都是基于进程而体现的,只有进程可以在系统中运行,程序运行必须有进程才行。进程是操作系统里资源分配的基本单位,也是独立运行的基本单位,具有动态的特点,暂时出现的特点,而且一个进程产生之后,可以再次生成多个进程出来。也可以多个进程并发执行,也可以同步或者异步执行。

进程的结构化特性:指的是说,进程一般由 进程控制块(PCB)+程序段+数据段 组成,其中 PCB 是唯一标识进程存在的标志,当系统或父进程创建一个进程时,实际上就是为其建立一个进程控制块PCB,进程控制块既能标识进程的存在,又能刻画出进程的动态特征,它是一个进程仅有的被操作系统真正感知的部分,对操作系统而言,所有进程控制块将构成并发执行控制和维护系统工作的依据。

进程的三个最基本的状态:(至少是这3个)就绪态,执行态,阻塞态

就绪态:进程已经获得除处理器之外的所有资源

执行态:进程获得了必要的资源,且在 cpu 中执行

阻塞态:进程暂时无法执行(分配了处理器也不行)

运行态—》就绪态:时间片用完 or 优先级调度问题。除了执行态-》阻塞态是主动转换,其他的都是被动转换。

状态的转换具有唯一性

并发和并行

并发与并行是两个既相似而又不相同的概念:并发性,又称共行性,是指能处理多个同时性活动的能力;

并行是指同时发生的两个并发事件,具有并发的含义,而并发则不一定并行,也亦是说并发事件之间不一定要同一时刻发生。

并发的实质:一个物理CPU(也可以多个物理CPU) 在若干道程序之间,在同一时间段里,多路复用,并发性是对有限物理资源强制行使多用户共享以提高效率。

并行性实质:指两个或两个以上事件或活动在同一时刻发生。在多道程序环境下,并行性使多个程序同一时刻可在不同CPU上同时执行

并发,是在同一个cpu上同时(不是真正的同时,而是看来是同时,因为cpu要在多个程序间切换)运行多个程序。

并行,是每个cpu运行一个程序。是真正的同时发生的。

打个比方:并发,就像一个人(cpu)喂2个孩子(程序),轮换着每人喂一口,表面上两个孩子都在吃饭。并行,就是2个人喂2个孩子,两个孩子同时同刻的在吃饭。

有两种并发关系分别是同步和互斥

同步是进程间直接的制约关系,互斥是进程间间接的制约关系。

互斥:进程(同类的)间相互排斥的使用临界资源的现象,就叫进程互斥。

同步:进程(不同类的)之间的关系不是相互排斥临界资源的关系,而是相互依赖的关系。进一步的说明:就是前一个进程的输出作为后一个进程的输入,当第一个进程没有输出时第二个进程必须等待。具有同步关系的一组并发进程相互发送的信息称为消息或事件。简单的说就是不同类的进程相互合作使用临界资源。

线程的概念:引入线程是为了减少程序并发执行时付出的时间和空间的开销,提高并发度!在引入线程的 OS中,线程是独立调度的基本单位(进程是独立运行和拥有资源的基本单位),线程只需要一点儿必需的资源即可。一个线程可以创建和撤销另一个线程,同一个进程中的多个线程之间可以并发执行。

多线程:多线程是程序设计的逻辑层概念,它是进程里的并发运行的一段代码。多线程可以实现线程间的切换执行。

异步和同步是相对的概念

同步是顺序执行,执行完一个再执行下一个,需要等待、协调运行。异步就是彼此独立,在等待某事件的过程中继续做自己的事,不需要等待这一事件完成后再工作。

线程就是实现异步的一个方式。异步是让调用方法的主线程不需要同步等待另一线程的完成,从而可以让主线程干其它的事情。

异步和多线程并不是一个同等关系,异步是最终目的,多线程只是实现异步的一种手段。异步是当一个调用请求发送给被调用者,而调用者不用等待其结果的返回而可以做其它的事情。实现异步可以采用多线程技术或则交给另外的进程来处理。异步和同步的区别,  在io等待的时候,同步不会切走,浪费了时间。

进程调度的目的

记录系统中所有进程的有关情况,确定分配处理机的原则,分配处理机给进程,从进程收回处理机。

进程调度的三个层次:

高级调度(作业调度):频率较低,几分钟一次、中级调度(交换技术)、低级调度(进程调度):频率很高,几十 ms 一次

进程调度算法

1.先来先服务(类似队列FIFO)

按照进程进入就绪队列的先后顺序来调度进程,到达得越早,其优先数越高。获得处理机的进程,未遇到其他情况时,一直运行下去,系统只需具备一个先进先出的队列,在管理优先数的就绪队列时,这种方法是一种最常见策略,并且在没有其他信息时,也是一种最合理的策略。

2.轮转调度(先来先服务的一个重要变形,就是轮转规则)

系统把所有就绪进程按先后次序排队,处理机总是优先分配给就绪队列中的第一个就绪进程,并分配它一个固定的时间片(如100毫秒)。当该运行进程用完规定的时间片时,被迫释放处理机给下一个处于就绪队列中的第一个进程,分给这个进程相同的时间片,每个运行完时间片的进程,当未遇到任何阻塞时,就回到就绪队列的尾部,并等待下次转到它时再投入运行。于是,只要是处于就绪队列中的进程,按此种算法迟早总可以分得处理机投入运行。

3.分级轮转法

将先前的一个就绪队列,根据进程的优先数不同划分两个或两个以上的就绪队列,并赋给每个队列不同的优先数。以两个就绪队列为例,一个具有较高优先数,另一个具有较低优先数,前者称为前台队列,后者称为后台队列。 

4.优先数法

根据已占有处理机的进程是否可被剥夺而分为优先占有法和优先剥夺法两种 。

优先占有法的原理是:一旦某个最高优先数的就绪进程分得处理机之后,只要不是其自身的原因被阻塞(如要求I/O操作)而不能继续运行时,就一直运行下去,直至运行结束。

优先剥夺法的原理是:当一个正在运行的进程即使其时间片未用完,无论什么时候,只要就绪队列中有一个比它的优先数高的进程,优先数高的进程就可以取代以前正在运行的进程,投入运行 。

调度用的进程状态切换图

原语的概念:在操作系统中,某些被进程调用的操作,例如队列操作、对信号灯的操作、检查启动外设操作等,一旦开始执行就不能被中断,否则就会出现操作错误,造成系统混乱。原语就是为实现这些操作而设置的。本质是若干条机器指令构成的一段程序,用来完成特定的功能(执行不可分割,具有原子性)。

信号量:一个同步机构,设置为 S,当s信号量>0表示可用资源数目,当信号量s<0,绝对值为在该信号量上等待的进程个数

P、V 原语

p 申请资源,v 释放资源,可以不再一个进程中,但是必须成对的出现,信号量 s 除去初始化之外,只有 pv 操作可以改变它。

复制代码
    single s;//设置信号量,s>=0
    //p 操作(wait 操作)
    s = s - 1;
    if (s >= 0) {
        //继续运行下去;
    }else{
        //阻塞该进程,把它插入到信号量等待队列中;
    }
    
    //v 操作(single 操作)
    s = s + 1;
    if (s > 0) {
        //继续运行下去;
    }else{
        //从信号量等待队列里,移出第一个进程,进入就绪队列中,再返回原进程执行;
    }
复制代码

进程之间通信

低级通信方式:PV 原语操作,进程互斥和同步。(信息量少,效率低)

高级通信方式:共享存储器系统,消息传递系统,管道通信系统

临界资源、临界区、进入区、退出区、剩余区

临界资源:计算机中有许多资源只允许一个进程使用,如果有多个进程同时去使用这类资源(也叫临界资源)就会产生严重的错误。几个进程若共享同一临界资源,它们必须以互斥的方式使用这个临界资源,即当一个进程正在使用临界资源且尚未使用完毕时,则其他进程必须推迟对该资源的进一步操作,在当前进程的使用完成之前,不能从中插进去使用这个临界资源,否则将会造成信息混乱和操作出错。在临界区之前设立的进入区。之后设立的退出区,最后余下的为剩余区

临界区:进程中用于访问临界资源的代码段

访问临界区的规则

空闲让进,忙则等待,有限等待,让权等待

信号量分类:

整型信号量,整型 s:在 p 操作时,如果没有可用资源,则进程持续对 s 测试,出现了『忙等』现象,不遵循『让权等待』原则。

记录型信号量(资源信号量):为解决整型信号量的问题,用链表链接所有的等待资源的进程,当进程对 s 进行 p 操作,如果没有剩余资源,则进程自我阻塞,并插入等待链表中,v 操作时,如果链表里仍然有等待资源的进程,那么就唤醒第一个等待的进程。有效的解除了忙等现象,无限等待的现象。

经典同步问题

1.生产者与消费者问题

Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”(Producer-consumer-relationship)的抽象模型。

事实上,计算机系统中的许多问题都可归结为生产者与消费者问题,生产者与消费者可以通过一个环形缓冲池联系起来,环形缓冲池由几个大小相等的缓冲块组成,每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品,而每个消费者则可不断地每次从缓冲池中取出一个产品。

下面给出基于环形缓冲区的生产者与消费者关系的形式描述,设:

1、生产者和消费者为同步关系(不同类的进程,顺序的访问资源),缓冲区为资源,需要两个同步信号量生产者私用信号量empty:初值为n,指示空缓冲块数目,也就是缓冲区大小。消费者私用信号量full:初值为0,指示满缓冲块数目,也就是当前产品的数量。

2、因为生产者 或者 消费者是需要使用同一个记录型信号量的进程,故需要一个互斥信号量 mutex,初值为1,用于实现临界区互斥。如果只有一个消费者和一个生产者,那么不需要使用 mutex 信号量。

3、pv 操作里,有多个信号量同时存在,p 操作顺序有讲究,必须先p 操作去申请资源,再占有信号量访问权,防止发生『死锁』!

模块 设计如下:

复制代码
 1     const int N = 10;//空缓冲池的空块的数量是10
 2     
 3     int mutex = 1;//公有信号量 mutex,初值为1,实现临界区互斥访问
 4     int empty = N;//生产者私有信号量empty,初值为 n=10,代表空缓冲池的空快数量
 5     int full = 0;//消费者私有信号量full,初值为0,代表满的缓冲区的满快数量。
 6     //生产者进程
 7     producer(){
 8         while (true) {
 9             //生成一个产品放入临时的缓冲区;
10             creat();
11             //先申请资源,防止死锁发生
12             p(empty);//先占下一个空位置,来防止 creat 的产品
13             //再占据信号量的访问权,进行互斥访问过程
14             p(mutex);
15             //执行产品放入缓冲区的操作
16             add();
17             //释放访问权
18             v(mutex);
19             //产品+1,放入空位置
20             v(full);
21         }
22     }
23     //消费者进程
24     consumer(){
25         while (true) {
26             //必须是先申请资源,然后再占有互斥信号量,实现互斥,不能逆序!
27             p(full);
28             p(mutex);
29             //执行某个产品取出的操作
30             sub();
31             v(mutex);
32             //多了一个空位
33             v(empty);
34             //把取出的产品消费掉
35             eat();
36         }
37     }
复制代码

注意:勿忘循环 while,且先生产了,才能去消费,注意实际的顺序!

2.读者与写者问题(三类情况讨论)

有一块共享的数据区域,然后有读者和写者前来分别读取数据,或者写入数据,要求如下:

1、读者只读出数据,写者只写入数据,不能混淆

2、任意多个读者可以同时读取数据(类似于内存的存取)

3、每次只能有一个写者去写入数据

4、一个写者正在写入数据的同时,其他的任意读者或者写者不能读取或者写入数据

三类情况:读者优先,公平情况,写者优先

一:读者优先算法;

读者先来读取数据(其他的读者也可以来读取数据),此时写者等待,也就是说读者可以插写者的队,这是读者优先的关键点,只有当读者为0,写者才能来写入数据。

1、写者要有一个互斥信号量 writeMutex=1,因为写者一次只能一个来写数据

2、对读者要有一个记录数目的 int 变量,readcount=0,一个互斥信号量readMutex = 1,保证多个读者来的时候,能似的 readcount 互斥的变化,也就是不被混乱的计数。

复制代码
 1     //读者计数用的互斥信号量
 2     int readMutex = 1;
 3     //写者互斥访问临界区的互斥信号量
 4     int writeMutex = 1;
 5     //记录读者数目
 6     int readcount = 0;
 7     //读者进程
 8     reader(){
 9         while (true) {
10             //读者来读,需要记录读者的数量
11             //前提是互斥的访问计数器
12             p(readMutex);
13             //判断当前是否有读者在读取数据,依据此,决定写者是否能进
14             if (0 == readcount) {
15                 //如果当前无读者,那么写者可进写入数据操作,但是这是读者优先算法,那么写者第一次来写不能进,要保证读者优先!
16                 p(writeMutex);
17             }
18             //如果计数器不为0,那么要保证写者不能进,且读者进的时候,要保证优先,也就是可以插读者的队
19             readcount++;
20             //计数器使用完毕,则可以释放使用权
21             v(readMutex);
22             //进行读取数据的操作
23             read();
24             //读取完毕之后,读者离开,再次占据计数器使用权,安全计数
25             p(readMutex);
26             readcount--;
27             //判断是否计数器为0
28             if (0 == readcount) {
29                 //此时,读者再次为0,那么写者可以进入写数据了,因为不是第一次来
30                 v(writeMutex);
31             }
32             //计数器使用完毕,释放使用权
33             v(readMutex);
34         }// end of while
35     }// end of reader
36     //写者进程
37     writer(){
38         while (true) {
39             //保证读者和其他写者不能进入
40             p(writeMutex);
41             //写操作
42             write();
43             //完毕之后,释放使用权
44             v(writeMutex);
45         }
46     }
复制代码

二、公平情况算法(按照先来后到的顺序)

读者想进的时候,有写者正在写(或者正在等待写),读者就不能进(读者等待),只有写者走了,读者才能进。和一相比,需要多一个信号量 wmutex=1,表示是否存在写者正在写或者等待写,如果存在,读者就等待,读者不能插队了。

复制代码
 1     //读者计数用的互斥信号量
 2     int readMutex = 1;
 3     //写者互斥访问临界区的互斥信号量
 4     int writeMutex = 1;
 5     //记录读者数目
 6     int readcount = 0;
 7     //判断写者是否存在的互斥信号量
 8     int wmutex = 1;
 9     //读者进程
10     reader(){
11         while (true) {
12             //不同于读者优先算法,读者来的时候,不能插队了,如果有写者在(或者等待),读者也需要等待,设置标识信号量
13             //占用 wmutex
14             p(wmutex);
15             //读者来读,需要记录读者的数量
16             //前提是互斥的访问计数器
17             p(readMutex);
18             //判断当前是否有读者在读取数据,依据此,决定写者是否能进
19             if (0 == readcount) {
20                 //如果是第一个读者来了,因为是公平算法,那么同样需要阻止其他写者进!
21                 p(writeMutex);
22             }
23             readcount++;
24             //计数器使用完毕,则可以释放使用权
25             v(readMutex);
26             //释放 wmutex,如果不释放,则后续读者无法进入,or 写者无法等
27             v(wmutex);
28             //进行读取数据的操作
29             read();
30             //读取完毕之后,读者离开,再次占据计数器使用权,安全计数
31             p(readMutex);
32             readcount--;
33             //判断是否计数器为0
34             if (0 == readcount) {
35                 //此时,读者为0,那么写者可以不用等待,从而进入写数据了
36                 v(writeMutex);
37             }
38             //计数器使用完毕,释放使用权
39             v(readMutex);
40         }// end of while
41     }// end of reader
42     //写者进程
43     writer(){
44         while (true) {
45             //避免读者优先,如果写者是首个来的,那么同样需要阻止其他读者插队,占用
46             p(wmutex);
47             //已经有一个写者的时候,同样,需保证读者和其他写者不能进入
48             p(writeMutex);
49             //写操作
50             write();
51             //完毕之后,释放使用权
52             v(writeMutex);
53             //释放写者存在标志,说明读者可以进
54             v(wmutex);
55         }
56     }
复制代码

因为有了 wmutex,所以当第一个写者进的时候,占用 p(wmutex),阻止了读者进入,避免了读者优先,v(wmutex)之后,读者才可以进入,控制了进程,可以按照先来后到的顺序来执行。

三、写者优先算法(写者可以插队的算法)

类似读者优先算法,同理,这里是写者可以插队,多用一个 readable 信号量,控制写者可以优先于读者进入临界区,一个整数 writecount 统计写者,而 wmutex 控制写者互质访问 writecount

复制代码
 1     //读者计数用的互斥信号量
 2     int readMutex = 1;
 3     //写者计数用的互斥变量
 4     int writeCountMutex = 1;
 5     //写者互斥访问临界区的互斥信号量
 6     int writeMutex = 1;
 7     //记录读者数目
 8     int readcount = 0;
 9     //记录写者数目
10     int writecount = 0;
11     //判断写者是否存在的互斥信号量
12     int readable = 1;
13     //读者进程
14     reader(){
15         while (true) {
16             //占用 readable,可知道是否存在写者
17             p(readable);
18             //读者来读,需要记录读者的数量
19             //前提是互斥的访问计数器
20             p(readMutex);
21             //判断当前是否有读者在读取数据,依据此,决定写者是否能进
22             if (0 == readcount) {
23                 //如果是第一个读者来了,那么同样需要阻止其他写者进!只不过写者优先说的是写者可以插队
24                 p(writeMutex);
25             }
26             readcount++;
27             //计数器使用完毕,则可以释放使用权
28             v(readMutex);
29             //释放 readable果不释放,则后续读者无法进入,or 写者无法等
30             v(readable);
31             //进行读取数据的操作
32             read();
33             //读取完毕之后,读者离开,再次占据计数器使用权,安全计数
34             p(readMutex);
35             readcount--;
36             //判断是否计数器为0
37             if (0 == readcount) {
38                 //此时,读者为0,那么写者可以不用等待,从而进入写数据了
39                 v(writeMutex);
40             }
41             //计数器使用完毕,释放使用权
42             v(readMutex);
43         }// end of while
44     }// end of reader
45     //写者进程,注意这里是写者优先算法
46     writer(){
47         while (true) {
48             //占用写者计数器
49             p(writeCountMutex);
50             //如果是首个写者,则组织其他读者进入
51             if (0 == writecount) {
52                 p(readable);
53             }
54             writecount++;
55             //停止占用计数器
56             v(writeCountMutex);
57             //写者互斥访问临界区
58             p(writeMutex);
59             //写操作
60             write();
61             //完毕之后,释放使用权
62             v(writeMutex);
63             //再次占用计数器
64             p(writeCountMutex);
65             writecount--;
66             //写者没了,那么读者可以进
67             if (0 == writecount) {
68                 v(readable);
69             }
70             //释放写者存在标志,说明读者可以进
71             v(writeCountMutex);
72         }
73     }
复制代码

注意:当第一个写者来的时候,便占用了 readable,一直占据,后续读者就会等待,而后续写者可以插队!因为 if 语句存在的原因!直到写者再次为0,释放了 readable,那么读者才可以申请进入资源区,然后转而是读者去占用 readable,阻止后续的写者进入。

PV 问题总结:

1、先确定进程是否可以同时执行,不能同时执行,则互斥访问之。

2、在并发进程间分清楚是互斥还是同步问题。同类进程同时只能访问一个资源叫互斥访问,不同类进程按照顺序的访问,叫同步访问。前者是间接的关系,后者是直接的关系。前驱进程加 v(释放资源操作),用来唤醒后继进程。后继进程加 p 操作(申请资源),用来保证在前驱进程之后执行。

3、画流程图,说明变量的含义

4、pv 操作一定成对儿的出现

5、互斥 pv 操作在同一进程内要夹住临界区,同步 pv 操作在不同类进程之间,v 在前驱,p 在后继

6、如果有计数,要给计数变量加信号量mutex,互斥访问。

 

死锁问题

死锁:当某个进程提出申请资源后,使得有关进程在无外力协助下,永远分配不到必需的资源而无法继续运行,这就产生了一种特殊的现象——死锁。在许多实时应用中,比如计算机控制运输和监视系统方面,死锁问题也极为重要。总得来说就是:2个或者2个以上的进程,在系统里无限等待,无法执行,且无外力作用下,他们无法主动去获得各自的资源!死锁进程是系统中当前进程集合的一个子集。

死锁产生的原因 :

1、竞争的资源不足以满足所有的进程使用(死锁产生的根本原因)

2、进程对资源的请求或者释放的顺序不当(死锁产生的重要原因)

比如:假定有两个进程Pl和P2都要修改文件F,修改时都需要一条暂时存放信息的磁带,而只有一台磁带机T可用。又假定由于某种原因,在进行修改之前,P2需要一暂存磁带(例如为了修改,要重新组织输入数据)。设F和T都是可重用资源,它们分别表示允许更新文件和允许使用磁带机。于是Pl和P2。可有如下形式:

分析:从上面的申请-释放过程可以看出,进程Pl和P2有可能“同时”分别到达rl和r2处,例如,P2首先得到T,然后Pl得到F,接着Pl到达r1,最后P2到达r2,此时,若Pl继续运行,则占有F的进程Pl将阻塞在T上,若P2继续运行,则占有T的进程P2将阻塞在F上,如果P2不能前进,则P1也不能继续下去,反之亦然。我们说这两个进程处在死锁状态。 

产生死锁有四个必要条件:互斥条件、不剥夺的条件、请求和保持资源的条件(部分分配资源条件)、环路等待条件。这四个缺一不可。

处理死锁的4种基本方法:

鸵鸟法(不管不顾,任其自由发展,可以使用在死锁很少很少发生的系统里)、预防死锁(从进程调度上入手,去破坏死锁产生的四个必要条件的一个或者多个)、避免死锁(提前防止系统进入死锁状态,不破坏死锁产生的四个必要条件,比如使用银行家算法)、检测和接触死锁(被动方式,发生了死锁再去检测处理)

预防死锁的的四中方法:

1、破坏互斥条件,比如改变受资源本身限制的打印机

2、破坏请求与保持条件:每个进程在运行之前,必须预先提出自己所要使用的全部资源,调度程序在该进程所需要的资源末得到满足之前,不让它们投入运行,并且当资源一旦分配给某个进程之后,那么在该进程的整个运行期间相应资源一直被它占有,这就破坏了产生死锁的请求与保持条件。

3、破坏环路等待条件:对系统提供的每一项资源,由系统设计者将它们按类型进行线性排队,并赋予不同的序号。

例如,设卡片输入机为1,打印机为2,磁带机为3,磁盘机为4,……所有的进程都只能严格地按照编号递增(或递减)的次序去请求资源,亦即,只有低编号的资源要求满足后,才能对高编号资源提出要求;释放资源时,应按编号递减的次序进行。由此可以看出,对资源请求采取了这种限制之后,所形成的进程—资源图不可能再产生环路。

4、破坏不剥夺条件:使其已经分配的资源变为可剥夺的即可,就是说分配了,还可以要回来,重新分配。这样也可以预防死锁。

避免死锁:使用银行家算法

为了避免死锁发生,操作系统必须根据预先掌握的关于资源用法的信息控制资源分配,使得共同进展路径的下一步不致于进入危险区,即只要有产生死锁的可能性,就避免把一种资源分配给一个进程。总得来说就是,把系统分为安全和不安全状态,允许进程动态的去申请资源,提前估计分配资源的安全性,安全则进入,不安全就不进入。

注意:安全序列不唯一,且不一定不安全序列就必然会发生死锁,只是可能发生死锁而已。

死锁避免的算法:银行家算法和安全性算法

解除死锁(一旦发生了死锁的时候,检测到了死锁存在,可以被动的解除死锁)

1.资源剥夺法

(1)还原算法。即恢复计算结果和状态。

(2)建立检查点主要是用来恢复分配前的状态。

2.撤消进程法

 

活锁和死锁的区别

前面已经提到死锁定义

一组进程中的每一个进程,均无限期地等待此组进程中某个其他进程占有的,因而永远无法得到的资源,这种现象称为进程死锁。 

所以可以得到以下结论:

参与死锁的进程至少有二个,每个参与死锁的进程均等待资源 ,参与死锁的进程中至少有两个进程占有资源,死锁进程是系统中当前进程集合的一个子集。 

在一个动态系统中,资源请求与释放是经常性发生的进程行为.对于每类系统资源,操作系统需要确定一个分配策略,当多个进程同时申请某类资源时,由分配策略确定资源分配给进程的次序。

资源分配策略可能是公平的,能保证请求者在有限的时间内获得所需资源;资源分配策略也可能是不公平的,即不能保证等待时间上界的存在。在后一种情况下,即使系统没有发生死锁,某些进程也可能会长时间等待.当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿,当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死。          

考虑一台打印机分配的例子:当有多个进程需要打印文件时,系统按照短文件优先的策略排序,该策略具有平均等待时间短的优点,似乎非常合理,但当短文件打印任务源源不断时,长文件的打印任务将被无限期地推迟,导致饥饿以至饿死。

与饥饿相关的另外一个概念称为活锁(live lock) 在忙式等待条件下发生的饥饿,称为活锁。例如不公平的互斥算法。

不进入等待状态的等待称为忙式等待,另一种等待方式是阻塞式等待,进程得不到共享资源时将进入阻塞状态,让出CPU给其他进程使用。

忙等待和阻塞式等待的相同之处在于进程都不具备继续向前推进的条件,不同之处在于处于忙等待的进程不主动放弃CPU,尽管CPU可能被剥夺,因而是低效的而处于阻塞状态的进程主动放弃CPU ,因而是高效的。

活锁是数据资源分配引起的,而饿死是处理器资源分配引起的。

不同领域中,本质应该是一样的。活锁的进程是在不主动放弃CPU的情况下无法完成工作,就如计算机网络中说的报文围绕目的节点转悠,却不能真正到达目的节点。

而饿死则是放弃CPU让其他进程工作,但这一让就成了无限期的让,从而导致了饿死。

举例子来说明什么是活锁:

如果事务T1封锁了数据R,事务T2又请求封锁数据R,于是T2就等待。之后呢,T3也请求封锁R,当T1释放了R上的封锁之后系统首先批准了T3的请求,T2仍然等待。然后T4又请求封锁R,当T3释放了R上的封锁之后系统又批准了T4的请求,...,T2有可能永远等待,这就是活锁的情形,就是上面说的发生在忙等情景下的饥饿。

避免活锁的简单方法:采用先来先服务的策略。

举例子说明什么是死锁:

如果事务T1封锁了数据R1,T2封锁了数据R2,然后T1又请求封锁R2,因T2已封锁了R2,于是T1等待T2释放R2上的锁。接着T2又申请封锁R1,因T1已封锁了R1,T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2,而T2又在等待T1的局面,T1和T2两个事务永远不能结束,形成死锁。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4355786.html