进程的定义、组成、组织方式、特征
进程的定义
程序:就是一个指令序列
早期的计算机(只支持单道程序)程序的代码放在程序段内,程序运行过程处理的数据放在数据段内(如变量)
引入多道程序技术之后内存中同时放入多道程序,各个程序的代码、运算数据存放的位置不同。为了方便操作系统管理,完成各程序并发执行,引入了进程、进程实体的概念.系统为每个运行的程序配置一个数据结构,称为进程控制块(PCB),用来描述进程的各种信息(如程序代码存放位置).程序段、数据段、PCB三部分组成了进程实体(进程映像)。一般情况下,我们把进程实体就简称为选程,例如,所谓创建进程,实质上是创建进程实体中的PCB;而撤销进程,实质上是撤销进程实体中的PCB。
PCB是进程存在的唯一标志。
从不同的角度,进程可以有不同的定义,比较传统典型的定义有(强调动态性):
1.进程是程序的一次执行过程。
2.进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
3.进程是具有独立功能的程序在数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位
引入进程实体的概念后,可把进程定义为:
进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。
注:严格来说,进程实体和进程并不一样,**进程实体是静态的,进程则是动态的。**不过,除非题目专门考察二者区别,否则可以认为进程实体就是进程。因此我们也可以说“进程由程序段、数据段、PCB三部分组成”
PCB:操作系统通过PCB来管理进程,因此PCB中应该包含操作系统对其进行管理所需的各种信息。
程序段:程序代码即存放在此
数据段:程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的常量就存放在数据段内
进程的组织
在一个系统中,通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理,应该用适当的方式把这些PCB组织起来。
注:进程的组成讨论的是一个进程内部由哪些部分构成的问题,而进程的组织讨论的是多个进程之间的组织方式问题
进程的特征
进程和程序是两个截然不同的概念,相比于程序,进程拥有以下特征:
- 动态性:进程是程序的一次执行过程,是动态地产生、变化和消亡的。动态性是进程最基本的特征。
- 并发性:内存中有多个进程实体,各进程可并发执行
- 独立性:进程是能独立运行、独立获得资源、独立接受调度的基本单位。进程是资源分配、接受调度的基本单位
- 异步性:各进程按各自独立的、不可预知的速度向前推进,操作系统要提供"进程同步机制"来解决异步问题。异步性会导致并发程序执行结果的不确定性。
- 结构性:每个进程都会配置一个PCB。结构上看,进程由程序段、数据段、PCB组成
进程的状态和转换
进程的状态――三种基本状态
进程是程序的一次执行。在这个执行过程中,有时进程正在被CPU处理,有时又需要等待CPU服务,可见,进程的状态是会有各种变化。为了方便对各个进程的管理,操作系统需要将进程合理地划分为几种状态。
三种基本状态:
- 运行态:占有CPU,并在CPU上运行
- 就绪态:已经具备运行条件,但由于没有空闲CPU,而暂时不能运行。进程已经拥有了除处理机之外所有需要的资源,一旦获得处理机,即可立即进入运行态开始运行。
- 阻塞态:因等待某一事件而暂时不能运行。CPU是计算机中最昂贵的部件,为了提高CPU的利用率,需要先将其他进程需要的资源分配到位,才能得到CPU的服务
注意:单核处理机环境下,每一时刻最多只有一个进程处于运行态。(双核环境下可以同时有两个进程处于运行态)
另外两种状态:
创建态:操作系统需要完成创建进程。操作系统为该进程分配所需的内存空间等系统资源,并为其创建、初始化PCB(如:为进程分配PID)
终止态:进程运行结束(或者由于bug导致进程无法继续执行下去,比如数组越界错误),需要撤销进程。进程正在从系统中撤销,操作系统会回收进程拥有的资源、撤销PCB
进程状态的转换
注意:不能由阻塞态直接转换为运行态,也不能由就绪态直接转换为阻塞态(因为进入阻塞态是进程主动请求的,必然需要讲程在运行时才能发出这种请求)
进程控制
进程控制的主要功能是对系统中的所有进程实施有效的管理,它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
用原语实现进程控制。原语的特点是执行期间不允许中断,只能一气呵成。
这种不可被中断的操作即原子操作。原语采用“关中断指令”和“开中断指令”实现
显然,关/开中断指令的权限非常大,必然是只允许在核心态下执行的特权指令,原语运行在核心态
控制进程相关的原语
学习技巧:进程控制会导致进程状态的转换。无论哪个原语,要做的无非三类事情:
1.更新PCB中的信息(如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
a.所有的进程控制原语一定都会修改进程状态标志
b.剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c.某进程开始运行前必然要恢复期运行环境
2.将PCB插入合适的队列
3.分配/回收资源
进程通信
进程通信就是指进程之间的信息交换。进程是分配系统资源的单位(包括内存地址空间),因此各进程拥有的内存地址空间相互独立。
为了保证安全,**一个进程不能直接访问另一个进程的地址空间。**但是进程之间的信息交换又是必须实现的。为了保证进程尚的安全通信,操作系统提供了一些方法。
共享存储
管道通信
“管道”是指用于连接读写进程的一个共享文件,又名pipe文件。其实就是在内存中开辟一个大小固定的缓冲区
1.管道只能采用半双工通信,某一时间段内只能实现单向的传输。如果要实现双向同时通信,则需要设置两个管道。
2.各进程要互斥地访问管道。
3.数据以字符流的形式写入管道,当管道写满时,写进程的write()系统调用将被阻塞,等待读进程将数据取走。当读进程将数据全部取走后,管道变空,此时读进程的read()系统调用将被阻塞。
4.如果没写满,就不允许读。如果没读空,就不允许写。
5.数据一旦被读出,就从管道中被抛弃,这就意味着读进程最多只能有一个,否则可能会有读错数据的情况。
消息传递
进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
线程概念和多线程模型
线程
有的进程可能需要“同时”做很多事,而传统的进程只能串行地执行一系列程序。为此,引入了“线程”,来增加并发度。引入线程后,线程成为了程序执行流的最小单位。
线程是一个基本的CPU执行单元,也是程序执行流的最小单位。
引入线程之后,不仅是进程之间可以并发,进程内的各线程之间也可以并发,从而进一步提升了系统的并发度,使得一个进程内也可以并发处理各种任务(如QQ视频、文字聊天、传文件)
引入线程后,进程只作为除CPU之外的系统资源的分配单元(如打印机、内存地址空间等都是分配给进程的)。
线程的属性
- 线程是处理机调度的单位
- 多CPU计算机中,各个线程可占用不同的CPU
- 每个线程都有一个线程ID、线程控制块(TCB)
- 线程也有就绪、阻塞、运行三种基本状态
- 线程几乎不拥有系统资源
- 同一进程的不同线程间共享进程的资源
- 由于共享内存地址空间,同一进程中的线程间通信甚至无需系统干预
- 同一进程中的线程切换,不会引起进程切换
- 不同进程中的线程切换,会引起进程切换
- 切换同进程内的线程,系统开销很小
- 切换进程,系统开销较大
线程的实现方式
用户级线程
用户级线程由应用程序通过线程库实现。
所有的线程管理工作都由应用程序负责(包括线程切换)
用户级线程中,线程切换可以在用户态下即可完成,无需操作系统干预。
在用户看来,是有多个线程。但是在操作系统内核看来,并意识不到线程的存在。(用户级线程对用户不透明,对操作系统透明)
可以这样理解,“用户级线程”就是“从用户视角看能看到的线程”
内核级线程
内核级线程(Kernel-Level Thread,KLT,又称“内核支持的线程”)
内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责,因此内核级线程的切换必然需要在核心态下才能完成。
可以这样理解,“内核级线程”就是“从操作系统内核视角看能看到的线程”
在同时支持用户级线程和内核级线程的系统中,可采用二者组合的方式:将n个用户级线程映射到m个内核级线程上( n >= m)
重点重点重点:
操作系统只“看得见”内核级线程,因此只有内核级线程才是处理机分配的单位。
例如:上方这个模型中,该进程由两个内核级线程,三个用户级线程,在用户看来,这个进程中有三个线程。但即使该进程在一个4核处理机的计算机上运行,也最多只能被分配到两个核,最多只能有两个用户线程并行执行。
多线程模型
在同时支持用户级线程和内核级线程的系统中,由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题。
多对一模型
多对一模型:多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。
优点:用户级线程的切换在用户空间即可完成,不需要切换到核心态,线程管理的系统开销小,效率高
缺点:当一个用户级线程被阻塞后,整个进程都会被阻塞,并发度不高。多个线程不可在多核处理机上并行运行
一对一模型
一对一模型:一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
优点:当一个线程被阻塞后,别的线程还可以继续执行,并发能力强。多线程可在多核处理机上并行执行。
缺点:一个用户进程会占用多个内核级线程,线程切换由操作系统内核完成,需要切换到核心态,因此线程管理的成本高,开销大。
多对多模型
多对多模型: n用户及线程映射到m个内核级线程(n >= m))。每个用户进程对应m个内核级线程。
克服了多对一模型并发度不高的缺点,又克服了对一模型中一个用户进程占用太多内核级线程,开销太大的缺点。
处理机调度的概念、层次
调度的基本概念
当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是“调度”研究的问题。
在多道程序系统中,进程的数量往往是多于处理机的个数的,这样不可能同时并行地处理各个进程。
处理机调度,就是从就绪队列中按照一疋的昇法逃作一个进任开付处理小力B有c心,O六n心L的并发执行。
高级调度
由于内存空间有限,有时无法将用户提交的作业全部放入内存,因此就需要确定某种规则来决定将作业调入内存的顺序。
高级调度(作业调度)。按一定的原则从外存上处于后备队列的作业中挑选一个(或多个)作业,给他们分配内存等必要资源,并建立相应的进程(建立PCB),以使它(们)获得竞争处理机的权利。
高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次,调出一次。**作业调入时会建立相应的PCB,作业调出时才撤销PCB。**高级调度主要是指调入的问题,因为只有调入的时机需要操作系统来确定,但调出的时机必然是作业运行结束才调出。
中级调度
引入了虚拟存储技术之后,可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时,再重新调入内存。
这么做的目的是为了提高内存利用率和系统吞吐量。
暂时调到外存等待的进程状态为挂起状态。值得注意的是PCB并不会一起调到外存,而是会常驻内存。
PCB中会记录进程数据在外存中的存放位置,进程状态等信息,操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。
进程的挂起态和七状态模型
暂时调到外存等待的进程状态为挂起状态(挂起态,suspend挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
五状态模型→七状态模型
注意“挂起”和“阻塞”的区别:两种状态都是暂时不能获得CPU的服务,但挂起态是将进程映像调到外存去了,而阻塞态下进程映像还在内存中。
有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列,甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。
低级调度
低级调度(进程调度),其主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它。
进程调度是操作系统中最基本的一种调度,在一般的操作系统中都必须配置进程调度。
进程调度的频率很高,一般几十毫秒一次。
进程调度的时机、切换与过程、方式
进程调度的时机
进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机。
但是进程在普通临界区中是可以进行调度、切换的。
临界资源:一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
临界区:访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的,比如进程的就绪队列(由各就绪进程的PCB组成)
进程调度的方式
非剥夺调度方式,又称非抢占方式。即,只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。
实现简单,系统开销小但是无法及时处理紧急任务,适合于早期的批处理系统
剥夺调度方式,又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的那个进程。可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。
适合于分时操作系统、实时操作系统
进程的切换与过程
“狭义的进程调度”与“进程切换”的区别:
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。
(这个进程可以是刚刚被暂停执行的进程,也可能是另一个进程,后一种情况就需要进程切换)
进程切换是指一个进程让出处理机,由另一个进程占用处理机的过程。广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程切换的过程主要完成了:
1.对原来运行进程各种数据的保存
2.对新的进程各种数据的恢复
(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息,这些信息一般保存在进程控制块)
注意:进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少。
调度算法的评价指标
CPU利用率
由于早期的CPU造价极其昂贵,因此人们会希望让CPU尽可能多地工作
CPU利用率:指CPU“忙碌”的时间占总时间的比例。
Eg:某计算机只支持单道程序,某个作业刚开始需要在CPU上运行5秒,再用打印机打印输出5秒,之后再执行5秒,才能结束。在此过程中,CPU利用率、打印机利用率分别是多少?
CPU利用率=(5+5)/(5+5+5)=66.67%
打印机利用率=5/(5+5+5)=33.33%
通常会考察多道程序并发执行的情况,可以用“甘特图”来辅助计算
系统吞吐量
对于计算机来说,希望能用尽可能少的时间处理完尽可能多的作业
系统吞吐量:单位时间内完成作业的数量
Eg:某计算机系统处理完10道作业,共花费100秒,则系统吞吐量为?
10/100 =0.1道/秒
周转时间
对于计算机的用户来说,他很关心自己的作业从提交到完成花了多少时间。
周转时间,是指从作业被提交给系统开始,到作业完成为止的这段时间间隔。
它包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中,可能发生多次。
对于周转时间相同的两个作业,实际运行时间长的作业在相同时间内被服务的时间更多,带权周转时间更小,用户满意度更高。
对于实际运行时间相同的两个作业,周转时间短的带权周转时间更小,用户满意度更高。
带权周转时间必然≥1
带权周转时间与周转时间都是越小越好
等待时间
计算机的用户希望自己的作业尽可能少的等待处理机
等待时间,指进程/作业处于等待处理机状态时间之和,等待时间越长,用户满意度越低。
对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,在等待I/O完成的期间其实进程也是在被服务的,所以不计入等待时间。
对于作业来说,不仅要考虑建文进程后的等待时间,还要加上作业在外存后备队列中等待的时间。
一个作业总共需要被CPU服务多久,被I/O设备服务多久一般是确定不变的,因此调度算法其实只会影响作业/进程的等待时间。当然,与前面指标类似,也有“平均等待时间”来评价整体性能。
响应时间
对于计算机用户来说,会希望自己的提交的请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应。
响应时间,指从用户提交请求到首次产生响应所用的时间。
FCFS、SJF、HRRN调度算法
注:这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统,当然,FCFS算法也常结合其他的算法使用。
tips:各种调度算法的学习思路
- 算法思想
- 算法规则
- 这种调度算法是作用于作业调度还是进程调度
- 抢占式or非抢占式
- 优点和缺点
- 是否会导致饥饿(某进程/作业长期得不到服务)
先来先服务(FCFS,First Come First Serve)
短作业优先(SJF, Shortest Job First)
严格来说,用于进程调度应该称为短进程优先调度算法(SPF)
短作业/进程优先调度算法:每次调度时选择当前已到达且运行时间最短的作业/进程。
抢占式的短作业优先算法又称“最短剩余时间优先算法(SRTN)“
最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度
注意几个小细节:
-
如果题目中未特别说明,所提到的“短作业/进程优先算法”默认是非抢占式
很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少”
-
严格来说,这个表述是错误的,不严谨的。之前的例子表明,最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少
应该加上一个条件“在所有进程同时可运行时,采用SJF调度算法的平均等待时间、平均周转时间最少”;
或者说“在所有进程都几乎同时到达时,采用SJF调度算法的平均等待时间、平均周转时间最少”;
如果不加上述前提条件,则应该说“抢占式的短作业/进程优先调度算法(最短剩余时间优先, SRNT算法)的平均等待时间、平均周转时间最少”
-
虽然严格来说,SJF的平均等待时间、平均周转时间并不一定最少,但相比于其他算法(如FCFS),SJF依然可以获得较少的平均等待时间、平均周转时间
-
如果选择题中遇到“SIF算法的平均等待时间、平均周转时间最少”的选项,那最好判断其他选项是不是有很明显的错误,如果没有更合适的选项,那也应该选择该选项
对FCFS和SJF两种算法的思考
FCFS 算法是在每次调度的时候选择一个等待时间最长的作业(进程)为其服务。但是没有考虑到作业的运行时间,因此导致了对短作业不友好的问题
SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间,因此导致了对长作业不友好的问题,甚至还会造成饥饿问题
高响应比优先(HRRN,Highest Response Ratio Next)
高响应比优先算法:非抢占式的调度算法,只有当前运行的进程主动放弃CPU时(正常/异常完成,或主动阻塞),才需要进行调度,调度时计算所有就绪进程的响应比,选响应比最高的进程上处理机。
调度算法:时间片轮转、优先级调度、多级反馈队列
注:比起早期的批处理操作系统来说,由于计算机造价大幅降低,因此之后出现的交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIx使用的就是多级反馈队列调度算法)
Tips:各种调度算法的学习思路
1.算法思想
2.算法规则
3.这种调度算法是用于作业调度还是进程调度?
4.抢占式?非抢占式?
时间片轮转(RR, Round-Robin)
常用于分时操作系统,更注重“响应时间”,因而不计算周转时间
如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大。
另一方面,进程调度、切换是有时间代价的(保存、恢复运行环境),因此如果时间片太小,会导致进程切换过于频繁,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。
一般来说,设计时间片时要让切换进程的开销占比不超过1%
优先级调度算法
非抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。
抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外,当就绪队列发生改变时也需要检查是会发生抢占。
补充:
就绪队列未必只有一个,可以按照不同优先级来组织。另外,也可以把优先级高的进程排在更靠近队头的位置
根据优先级是否可以动态改变,可将优先级分为静态优先级和动态优先级两种。
- 静态优先级:创建进程时确定,之后一直不变。
- 动态优先级:创建进程时有一个初始值,之后会根据情况动态地调整优先级。
如何合理地设置各类进程的优先级?
通常:
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好l/O型进程(或称l/O繁忙型进程)
注:与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)。l/O设备和CPU可以并行工作。如果优先让l/O繁忙型进程优先运行的话,则越有可能让l/O设备尽早地投入工作,则资源利用率、系统吞址量都会得到提升
如果采用的是动态优先级,什么时候应该调整?
可以从追求公平、提升资源利用率等角度考虑。如果某进程在就绪队列中等待了很长时间,则可以适当提升其优先级。如果某进程占用处理机运行了很长时间,则可适当降低其优先级。
如果发现一个讲程频繁地进行I/O操作,则可适当提升其优先级
FCFS算法的优点是公平
SJF算法的优点是能尽快处理完短作业,平均等待/周转时间等参数很优秀
时间片轮转调度算法可以让各个进程得到及时的响应
优先级调度算法可以灵活地调整各种进程被服务的机会
能否对其他算法做个折中权衡?得到一个综合表现优秀平衡的算法呢?
多级反馈队列调度算法
进程同步、进程异步
进程具有异步性的特征。异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。
进程同步
同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
进程互斥
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存,又比如打印机、摄像头这样的I/O设备)
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对临界资源的访问,必须互斥地进行。互斥,亦称间接制约关系。进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。
对临界资源的互斥访问,可以在逻辑上分为如下四个部分:
前三部分常考。
注意:
临界区是进程中访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段。
临界区也可称为“临界段”。
为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:
1.空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;
2.忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待;
3.有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿);
4.让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。
进程互斥的软件实现方法
学习提示:
1.理解各个算法的思想、原理
2.结合上小节学习的“实现互斥的四个逻辑部分”,重点理解各算法在进入区、退出区都做了什么
3.分析各算法存在的缺陷(结合“实现互斥要遵循的四个原则”进行分析)
单标志法
算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
turn的初值为0,即刚开始只允许0号进程进入临界区。
若P1先上处理机运行,则会一直卡在⑤。直到P1的时间片用完,发生调度,切换P0上处理机运行。代码①不会卡住P0,P0可以正常访问临界区,在P0访问临界区期间即时切换回P1,P1依然会卡在⑤。只有PO在退出区将turn改为1后,P1才能进入临界区。
因此,该算法可以实现“同一时刻最多只允许一个进程访问临界区”
turn表示当前允许进入临界区的进程号,而只有当前允许进入临界区的进程在访问了临界区之后,才会修改turn的值。也就是说,对于临界区的访问,一定是按P0→P1→P0→P1→…这样轮流访问。
双标志先检查法
算法思想:设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿,比如“flag[0] = ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区,如果没有,则把自身对应的标志flag[i]设为true,之后开始访问临界区。
若按照①⑤②⑥③⑦…的顺序执行,P0和P1将会同时访问临界区。因此,双标志先检查法的主要问题是:违反“忙则等待”原则。
原因在于,进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后,“上锁”前可能发生讲程切换。
双标志后检查法
算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法,来避免上述问题。
若按照①⑤②⑥…的顺序执行,P0和P1将都无法进入临界区
因此,双标志后检查法虽然解决了“忙则等待”的问题,但是又违背了“空闲让进”和“有限等待”原则,会因各进程都长期无法访问临界资源而**产生“饥饿”**现象。
Peterson算法
算法思想:双标志后检查法中,两个进程都争着想进入临界区,但是谁也不让谁,最后谁都无法进入临界区。Gary L. Peterson想到了一种方法,如果双方都争着想进入临界区,那可以让进程尝试“孔融让梨”,主动让对方先使用临界区。
两种双标志法的问题都是由于进入区的几个操作不能一气呵成导致的。
进入区:1.主动争取;2.主动谦让;3.检查对方是否也想使用,且最后一次是不是自己谦让
Peterson算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、有限等待三个原则,但是依然未遵循让权等待的原则。
Peterson算法相较于之前三种软件解决方案来说,是最好的,但依然不够好。
进程互斥的硬件算法
学习提示:
1.理解各方法的原理
2.了解各方法的优缺点
中断屏蔽方法
利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况)
优点:简单、高效
缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)
TestAndSet指令
简称TS指令,也有地方称为TestAndSetLock指令,或TSL指令
TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。以下是用c语言描述的逻辑:
若刚开始lock是false,则TSL返回的old值为false,while循球条件不满足,直接跳过循环,进入临界区。若刚开始lock是true,则执行TLS后old返回的值为true,while循环条件满足,会一直循环,直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法,TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。
Swap指令
有的地方也叫Exchange指令,或简称XCHG指令。
Swap指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。以下是用c语言描述的逻辑
逻辑上来看Swap和TSL并无太大区别,都是先记录下此时临界区是否已经被上锁(记录在 old变量上),再将上锁标记lok设置为true,最后检查old,如果old为 false则说明之前没有别的进程对临界区上锁,则可跳出循环,进入临界区。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。
信号量机制
进程互斥的四种软件实现方式(单标志法、双标志先检查、双标志后检查、Peterson算法)进程互斥的三种硬件实现方式(中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)
1.在双标志先检查法中,进入区的“检查”、“上锁”操作无法一气呵成,从而导致了两个进程有可能同时进入临界区的问题;
2.所有的解决方案都无法实现“让权等待”
1965年,荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法――信号量机制
信号量机制
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作,从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种资源的数量,比如:系统中只有一台打印机,就可以设置一个初值为1的信号量。
原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能“一气呵成”就能避免问题。
一对原语: wait(S)原语和 signal(S)原语,可以把原语理解为我们自己写的函数,函数名分别为wait和 signal,括号里的信号量s其实就是函数调用时传入的一个参数。
wait、signal原语常简称为P、V操作(来自荷兰语proberen和 verhogen)。因此,做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、v(s)
信号量机制――整型信号量
用一个整数型的变量作为信号量,用来表示系统中某种资源的数量。与普通整数变量的区别:对信号量的操作只有三种,即初始化、P操作、V操作。
Eg:某计算机系统中有一台打印机…
“检查”和“上锁”一气呵成,避免了并发、异步导致的问题
存在的问题:不满足“让权等待”原则,会发生“忙等”(常考)
信号量机制――记录型信号量
整型信号量的缺陷是存在“忙等”问题,因此人们又提出了“记录型信号量”,即用记录型数据结构表示的信号量。
在考研题目中wait(S)、signal(S)也可以记为P(S)、v(s),这对原语可用于实现系统资源的“申请”和“释放”。
S.value的初值表示系统中某种资源的数目。
对信号量s的一次Р操作意味着进程请求一个单位的该类资源,因此需要执行S.value–,表示资源数减1,当S.value <0时表示该类资源已分配完毕,因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态→>阻塞态),主动放弃处理机,并插入该类资源的等待队列S.L中。可见,该机制遵循了“让权等待”原则,不会出现“忙等”现象。
对信号量S的一次操作意味着进程释放一个单位的该类资源,因此需要执行S.value++,表示资源数加1,若加1后仍是S.value <=0,表示依然有进程在等待该类资源,因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)。
用信号量机制实现进程互斥、同步、前驱关系
信号量机制实现进程互斥
1.分析并发进程的关键活动,划定临界区(如:对临界资源打印机的访问就应放在临界区)
2.设置互斥信号量mutex,初值为1
3.在临界区之前执行P(mutex)
4.在临界区之后执行V(mutex)
P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放,等待进程永不被唤醒。
信号量机制实现进程同步
进程同步:要让各并发进程按要求有序地推进。
用信号量实现进程同步:
1.分析什么地方需要实现“同步关系”,即必须保证“一前一后”执行的两个操作(或两句代码)
2.设置同步信号量s,初始为0
3.在“前操作”之后执行V(s)
4.在“后操作”之前执行P(S)
若先执行到V(S)操作,则S++后S=1。之后当执行到P(S)操作时,由于S=1,表示有可用资源,会执行S–,S的值变回0,P2进程不会执行block原语,而是继续往下执行代码4。
若先执行到P(S)操作,由于S=0,S–后S=-1,表示此时没有可用资源,因此P操作中会执行block原语,主动请求阻塞。之后当执行完代码2,继而执行v(S)操作,S++,使s变回o,由于此时有进程在该信号量对应的阻塞队列中,因此会在V操作中执行wakeup原语,唤醒P2进程。这样P2就可以继续执行代码4了
信号量机制实现前驱关系
进程P1中有句代码S1,P2中有句代码S2…P3… P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:
其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)因此,
1.要为每一对前驱关系各设置一个同步变量
2.在“前操作”之后对相应的同步变量执行V操作
3.在“后操作”之前对相应的同步变量执行Р操作
生产者——消费者问题
问题描述
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。(同步关系。缓冲区满时,生产者要等待消费者取走产品)
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。(同步关系。缓冲区空时(即没有产品时),消费者要等待生产者放入产品)
缓冲区是临界资源,各进程必须互斥地访问。
生产者每次要消耗(P)一个空闲缓冲区,并生产(V))一个产品。消费者每次要消耗(P)一个产品,并释放一个空闲缓冲区(V)。往缓冲区放入/取走产品需要互斥。
PV操作题目分析步骤:
1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。(互斥信号量初值一般为
1,同步信号量的初始值要看对应资源的初始值是多少)
刚开始空闲缓冲区的数量为n,非空闲缓冲区(产品)的数量为0
实现方式
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。
缓冲区是临界资源,各进程必须互斥地访问。
如果改变相邻P、V操作的顺序
若此时缓冲区内已经放满产品,则empty=0,full=n。
则生产者进程执行①使mutex变为o,再执行②,由于已没有空闲缓冲区,因此生产者被阻塞。由于生产者阻塞,因此切换回消费者进程。消费者进程执行③,由于mutex为o,即生产者还没释放对临界资源的“锁”,因此消费者也被阻塞。
这就造成了生产者等待消费者释放空闲缓冲区,而消费者又等待生产者释放临界区的情况,生产者和消费者循环等待被对方唤醒,出现“死锁”。
同样的,若缓冲区中没有产品,即full=0,empty=n。按③④①的顺序执行就会发生死锁。因此,实现互斥的P操作一定要在实现同步的P操作之后。
v操作不会导致进程阻塞,因此两个v操作顺序可以交换。
多生产者——多消费者问题
问题描述
桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。
1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
互斥关系:
对缓冲区(盘子)的访问要互斥地进行
同步关系(一前一后):
- 1.父亲将苹果放入盘子后,女儿才能取苹果
- 2.母亲将橘子放入盘子后,儿子才能取橘子
- 3.只有盘子为空时,父亲或母亲才能放入水果
“盘子为空”这个事件可以由儿子或女儿触发,事件发生后才允许父亲或母亲放水果
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
互斥:在临界区前后分别PV
同步:前V后P
实现方式
结论:即使不设置专门的互斥变量mutex,也不会出现多个进程同时访问盘子的现象。原因在于:本题中的缓冲区大小为1,在任何时刻,apple、 orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞,并顺利地进入临界区…
如果盘子缓冲容量为2,可能会导致覆盖
父亲P(plate),可以访问盘子→母亲P(plate),可以访问盘子→父亲在往盘子里放苹果,同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况,有可能导致两个进程写入缓冲区的数据相互覆盖的情况。因此,如果缓冲区大小大于1,就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。
吸烟者问题
问题描述
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料,供应者每次将两种材料放桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料再桌上,这个过程一直重复(让三个抽烟者轮流地抽烟)
问题分析
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料,供应者每次将两种材料放桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料再桌上,这个过程一直重复(让三个抽烟者轮流地抽烟)
本质上这题也属于“生产者-消费者”问题,更详细的说应该是“可生产多种产品的单生产者-多消费者”。
1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
桌子可以抽象为容量为1的缓冲区,要互斥访问
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序,PV操作顺序:“前V后P”
3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。(互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少)
实现方式
缓冲区大小为1,同一时刻,四个同步信号量中至多有一个的值为1。
读者——写者问题(读写公平法)
问题描述
有读者和写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前,应让已有的读者和写者全部退出。
1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序
3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。(互斥信号量初值一般为1,
同步信号量的初始值要看对应资源的初始值是多少)
两类进程:写进程、读进程
互斥关系:写进程一写进程、写进程―读进程。读进程与读进程不存在互斥问题。
写者进程和任何进程都互斥,设置一个互斥信号量rw,在写者访问共享文件前后分别执行P、v操作。读者进程和写者进程也要互斥,因此读者访问共享文件前后也要对rw执行P、v操作。
如果所有读者进程在访问共享文件之前都执行P(rw)操作,那么会导致各个读进程之间也无法同时访问文件。
Key:读者写者问题的核心思想――怎么处理该问题呢?
P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问,而读进程与写进程又必须互斥访问,那么我们可以让第一个访问文件的读进程“加锁”,让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量count来记录当前有几个读进程在访问文件。
实现方式
思考:若两个读进程并发执行,则两个读进程有可能先后执行P(rw),从而使第二个读进程阻塞的情况。
如何解决:出现上述问题的原因在于对count变量的检查和赋值无法一气呵成,因此可以设置另一个互斥信号量来保证各读进程对count的访问是互斥的。
潜在的问题:只要有读进程还在读,写进程就要一直阻塞等待,可能“饿死”因此,这种算法中,读进程是优先的
哲学家进餐问题
问题描述
一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。
1.关系分析。系统中有5个哲学家进程,5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2.整理思路。这个问题中只有互斥关系,但与之前遇到的问题不同的事,每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象,是哲学家问题的髓。
3.信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号,哲学家i左边的筷子编号为i,右边的筷子编号为(i+1)%5。
每个哲学家吃饭前依次拿起左、右两支筷子。如果5个哲学家并发地拿起了自己左手边的筷子…每位哲学家循环等待右边的人放下筷子(阻塞)发生“死锁”
如何防止死锁的发生呢?
①可以对哲学家进程施加一些限制条件,比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
②要求奇数号哲学家先拿左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭,那么只会有其中一个可以拿起第一只筷子,另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
因此这种方法并不能保证只有两边的筷子都可用时,才允许哲学家拿起筷子。更准确的说法应该是:各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞,也不会有别的哲学家会继续尝试拿筷子。这样的话,当前正在吃饭的哲学家放下筷子后,被阻塞的哲学家就可以获得等待的筷子了。
管程
1973年,Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分,即一种高级同步机制
管程的定义和基本特征
管程是一种特殊的软件模块,有这些部分组成:
1.局部于管程的共享数据结构说明;
2.对该数据结构进行操作的一组过程;
3.对局部于管程的共享数据设置初始值的语句;
4.管程有一个名字。
跨考Tips:“过程”其实就是“函数”
管程的基本特征:
1.局部于管程的数据只能被局部于管程的过程所访问;
2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
3.每次仅允许一个进程在管程内执行某个内部过程。
用管程解决生产者消费者问题
由编译器负责实现各进程互斥地进入管程中的过程,管程中设置条件变量和等待/唤醒操作,以解决同步问题。
每次仅允许一个进程在管程内执行某个内部过程。
引入管程的目的无非就是要更方便地实现进程互斥和同步。
1.需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2.需要在管程中定义用于访问这些共享数据的“入口”一-其实就是一些函数(如生产者消费者问题中,可以定义一个函数用于将产品放入缓冲区,再定义一个函数用于从缓冲区取出产品)
3.只有通过这些特定的“入口”才能访问共享数据
4.管程中有很多“入口”,但是每次只能开放其中一个“入口”,并且只能让一个进程或线程进入(如生产者消费者问题中,各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的,程序员不用关心)
5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量
上等待(此时,该进程应先释放管程的使用权,也就是让出“入口”)﹔可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
程序员可以用某种特殊的语法定义一个管程(比如: monitor ProducerConsumer …end monitor;),之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。
Java中类似于管程的机制
Java中,如果用关键字synchronized来描述一个函数,那么这个函数同一时间段内只能被一个线程调用
死锁的概念
什么是死锁
每个人都占有一个资源,同时又在等待另一个人手里的资源。发生“死锁”
在并发环境下,各进程因竞争资源而造成的一种互相等待对方手里的资源,导致各进程都阻塞,都无法向前推进的现象,就是“死锁”。发生死锁后若无外力干涉,这些进程都将无法向前推进。
死锁、饥饿、死循环的区别
死锁:各进程互相等待对方手里的资源,导致各进程都阻塞,无法向前推进的现象。
饥饿:由于长期得不到想要的资源,某进程无法向前推进的现象。比如:在短进程优先(SPF)算法中,若有源源不断的短进程到来,则长进程将一直得不到处理机,从而发生长进程“饥饿”。
死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的,有时是程序员故意设计的。
死锁产生的必要条件
产生死锁必须同时满足一下四个条件,只要其中任一条件不成立,死锁就不会发生。
互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
不剥夺条件:进程所获得的资源在未使用完之前,不能由其他进程强行夺走,只能主动释放。
请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞,但又对自己已有的资源保持不放。
循环等待条件:存在一种进程资源的循环等待链,链中的每一个进程己获得的资源同时被下一个进程所请求。
注意! 发生死锁时一定有循环等待,但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)
如果同类资源数大于1,则即使有循环等待,也未必发生死锁。但如果系统中每类资源都只有一个,那循环等待就是死锁的充分必要条件了。
什么时候会发生死锁
1.对系统资源的竞争。各进程对不可剥夺的资源(如打印机)的竞争可能引起死锁,对可剥夺的资源(CPU)的竞争是不会引起死锁的。
2.进程推进顺序非法。请求和释放资源的顺序不当,也同样会导致死锁。例如,并发执行的进程P1、P2分别申请并占有了资源R1、R2,之后进程P1又紧接着申请资源R2,而进程P2又申请资源R1,两者会因为申请的资源被对方占有而阻塞,从而发生死锁。
3.信号量的使用不当也会造成死锁。如生产者-消费者问题中,如果实现互斥的P操作在实现同步的P操作之前,就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)
总之,对不可剥夺资源的不合理分配,可能导致死锁。
死锁的处理策略
1.预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
2.避免死锁。用某种方法防止系统进入不安全状态,从而避免死锁(银行家算法)
3.死锁的检测和解除。允许死锁的发生,不过操作系统会负责检测出死锁的发生,然后采取某种措
施解除死锁。
死锁的处理策略——预防死锁(静态策略)
破坏互斥条件
互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁。
如果把只能互斥使用的资源改造为允许共享使用,则系统不会进入死锁状态。比如: SPOOLing技术。操作系统可以采用SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如,用SPOOLing技术将打印机改造为共享设备…
该策略的缺点:并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全,很多地方还必须保护这种互斥性。因此,很多时候都无法破坏互斥条件。
破坏不剥夺条件
不剥夺条件:进程所获得的资源在未使用完之前,不能由其他进程强行夺走,只能主动释放。
破坏不剥夺条件:
方案一:当某个进程请求新的资源得不到满足时,它必须立即释放保持的所有资源,待以后需要时再重新申请。也就是说,即使某些资源尚未使用完,也需要主动释放,从而破坏了不可剥夺条件。
方案二:当某个进程需要的资源被其他进程所占有的时候,可以由操作系统协助,将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如:剥夺调度方式,就是将处理机资源强行剥夺给优先级更高的进程使用)
该策略的缺点:
1.实现起来比较复杂。
2.释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源,如CPU。
3.反复地申请和释放资源会增加系统开销,降低系统吞吐量。
4.若采用方案一,意味着只要暂时得不到某个资源,之前获得的那些资源就都需要放弃,以后再重新申请。如果一直发生这样的情况,就会导致进程饥饿。
破坏请求和保持条件
请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞,但又对自己已有的资源保持不放。
可以采用静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不让它投入运行。一旦投入运行后,这些资源就一直归它所有,该进程就不会再请求别的任何资源了。
该策略实现起来简单,但也有明显的缺点:
有些资源可能只需要用很短的时间,因此如果进程的整个运行期间都一直保持着所有资源,就会造成严重的资源浪费,资源利用率极低。另外,该策略也有可能导致某些进程饥饿。
破坏循环等待条件
循环等待条件:存在一种进程资源的循环等待链,链中的每一个进程已获得的资源同时被下一个进程所请求。
可采用顺序资源分配法。首先给系统中的资源编号,规定每个进程必须按编号递增的顺序请求资源,同类资源(即编号相同的资源)一次申请完。
原理分析:一个进程只有已占有小编号的资源时,才有资格申请更大编号的资源。按此规则,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象。
假设系统中共有10个资源,编号为1,2,…10
该策略的缺点:
1.不方便增加新的设备,因为可能需要重新分配所有的编号;
2.进程实际使用资源的顺序可能和编号递增顺序不一致,会导致资源浪费;
3.必须按规定次序申请资源,用户编程麻烦。
死锁的处理策略(重要)——避免死锁(动态策略)(银行家算法)
安全序列、不安全状态、死锁的联系
安全序列,就是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要能找出一个安全序列,系统就是安全状态。当然,安全序列可能有多个。
如果分配了资源之后,系统中找不出任何一个安全序列,系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然,如果有进程提前归还了一些资源,那系统也有可能重新回到安全状态,不过我们在分配资源之前总是要考虑到最坏的情况。
如果系统处于安全状态,就一定不会发生死锁。如果系统进入不安全状态,就可能发生死锁(处于不安全状态未必就是发生了死锁,但发生死锁时一定是在不安全状态)
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态,以此决定是否答应资源分配请求。这由是“银行家算法”的核心思想。
银行家算法
银行家算法是荷兰学者Dijkstra为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中,用于避免死锁。
核心思想:在进程提出资源申请时,先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态,就暂时不答应这次请求,让该进程先阻塞等待。
思路:尝试找出一个安全序列…{P1}
依次检查剩余可用资源(3,3,2)是否能满足各进程的需求
可满足P1需求,将P1加入安全序列,并更新剩余可用资源值为(5,3,2)
依次检查剩余可用资源(5,3,2)是否能满足剩余进程(不包括已加入安全序列的进程)的需求
可满足P3需求,将P3加入安全序列,并更新剩余可用资源值为(7,4,3)
依次检查剩余可用资源(7,4,3)是否能满足剩余进程(不包括已加入安全序列的进程)的需求…
………
以此类推,共五次循环检查即可将5个进程都加入安全序列中,最终可得一个安全序列。
该算法称为安全性算法。可以很方便地用代码实现以上流程,每一轮检查都从编号较小的进程开始检查。实际做题时可以更快速的得到安全序列。
安全序列…{P1,P3,P0,P2,P4}
实际做题(手算)时可用更快速的方法找到一个安全序列:
经对比发现,(3,3,2)可满足P1、P3,说明无论如何,这两个进程的资源需求一定是可以依次被满足的,因此P1、P3一定可以顺利的执行完,并归还资源。可把P1、P3先加入安全序列。
(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)
于是,5个进程全部加入安全序列,说明此时系统处于安全状态,暂不可能发生死锁。
如果无法找到任何一个安全序列,说明此时系统处于不安全状态,有可能发生死锁。
假设系统中有n个进程,m种资源
假设系统中有n个进程,m种资源
每个进程在运行前先声明对各种资源的最大需求数,则可用一个nxm的矩阵(可用二维数组实现)表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max,Max[i, j]=K表示进程Pi最多需要K个资源Rj。同理,系统可以用一个nxm的分配矩阵Allocation表示对所有进程的资源分配情况。Max- Allocation =Need矩阵,表示各进程最多还需要多少各类资源。
数据结构:
长度为m的一维数组Available表示还有多少可用资源nm矩阵Max表示各进程对资源的最大需求数
nm矩阵Allocation表示已经给各进程分配了多少资源
Max - Allocation = Need矩阵表示各进程最多还需要多少资源用长度为m的一位数组Request表示进程此次申请的各种资源数
银行家算法步骤:
①检查此次申请是否超过了之前声明的最大需求数
②检查此时系统剩余的可用资源是否还能满足这次请求
③试探着分配,更改各数据结构
④用安全性算法检查此次分配是否会导致系统进入不安全状态
安全性算法步骤:
检查当前的剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并把该进程持有的资源全部回收。
不断重复上述过程,看最终是否能让所有进程都加入安全序列。
死锁的处理策略——检测和解除(允许死锁)
死锁的检测
为了能对系统是否已发生了死锁进行检测,必须:
①用某种数据结构来保存资源的请求和分配信息;
②提供一种算法,利用上述信息来检测系统是否已进入死锁状态。
如果系统中剩余的可用资源数足够满足进程的需求,那么这个进程暂时是不会阻塞的,可以顺利地执行下去。
如果这个进程执行结束了把资源归还系统,就可能使某些正在等待资源的进程被激活,并顺利地执行下去。
相应的,这些被激活的进程执行完了之后又会归还一些资源,这样可能又会激活另外一些阻塞的进程.
如果按上述过程分析,最终能消除所有边,就称这个图是可完全简化的。此时一定没有发生死锁(相当于能找到一个安全序列)
如果最终不能消除所有边,那么此时就是发生了死锁
最终还连着边的那些进程就是处于死锁状态的进程。
检测死锁的算法:
1)在资源分配图中,找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中己有空闲资源数量。如下图中,R1没有空闲资源,R2有一个空闲资源。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配变,使之称为孤立的结点。在下图中,P1是满足这一条件的进程结点,于是将P1的所有边消去。
2)进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在下图中,P2就满足这样的条件。根据1)中的方法进行一系列简化后,若能消去途中所有的边,则称该图是可完全简化的。
死锁定理:如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁
死锁的解除
一旦检测出死锁的发生,就应该立即解除死锁。
补充:并不是系统中所有的进程都是死锁状态,用死锁检测算法化简资源分配图后,还连着边的那些进程就是死锁进程。
解除死锁的主要方法有:
1.资源剥夺法。挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2.撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源。这种方式的优点是实现简单,但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间,已经接近结束了,一旦被终止可谓功亏一篑,以后还得从头再来。
3.进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息,设置还原点。
如何决定“对谁动手”?
1.进程优先级
2.已执行多长时间
3.还要多久能完成
4.进程已经使用了多少资源
5.进程是交互式的还是批处理式的
系统是否已进入死锁状态。
[外链图片转存中…(img-BrycUX7W-1652278801937)]
[外链图片转存中…(img-sFHvEX2M-1652278801938)]
如果系统中剩余的可用资源数足够满足进程的需求,那么这个进程暂时是不会阻塞的,可以顺利地执行下去。
如果这个进程执行结束了把资源归还系统,就可能使某些正在等待资源的进程被激活,并顺利地执行下去。
[外链图片转存中…(img-yzhpyHpC-1652278801938)]
相应的,这些被激活的进程执行完了之后又会归还一些资源,这样可能又会激活另外一些阻塞的进程.
[外链图片转存中…(img-xUA3u5AO-1652278801939)]
如果按上述过程分析,最终能消除所有边,就称这个图是可完全简化的。此时一定没有发生死锁(相当于能找到一个安全序列)
如果最终不能消除所有边,那么此时就是发生了死锁
[外链图片转存中…(img-96jPlPyb-1652278801939)]
[外链图片转存中…(img-9Ey3JGRj-1652278801940)]
最终还连着边的那些进程就是处于死锁状态的进程。
检测死锁的算法:
1)在资源分配图中,找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中己有空闲资源数量。如下图中,R1没有空闲资源,R2有一个空闲资源。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配变,使之称为孤立的结点。在下图中,P1是满足这一条件的进程结点,于是将P1的所有边消去。
2)进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在下图中,P2就满足这样的条件。根据1)中的方法进行一系列简化后,若能消去途中所有的边,则称该图是可完全简化的。
死锁定理:如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁
死锁的解除
一旦检测出死锁的发生,就应该立即解除死锁。
补充:并不是系统中所有的进程都是死锁状态,用死锁检测算法化简资源分配图后,还连着边的那些进程就是死锁进程。
解除死锁的主要方法有:
1.资源剥夺法。挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2.撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源。这种方式的优点是实现简单,但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间,已经接近结束了,一旦被终止可谓功亏一篑,以后还得从头再来。
3.进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息,设置还原点。
如何决定“对谁动手”?
1.进程优先级
2.已执行多长时间
3.还要多久能完成
4.进程已经使用了多少资源
5.进程是交互式的还是批处理式的
更多推荐
二、进程与线程
发布评论