导图社区 《操作系统》第二章-进程与线程
- 416
- 7
- 4
- 举报
《操作系统》第二章-进程与线程
这是一篇关于《操作系统》第二章-进程与线程的思维导图，包括：进程与线程、处理机调度、同步与互斥、死锁。
提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。
- 相似推荐
- 大纲
进程与线程
进程与线程
1. 进程的概念与特征
概念
定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程是动态的，进程映像则是静态的
进程实体（进程映像）
程序段
共享程序段必须是可重入代码（纯代码），即不允许任何修改，因此可以被多个进程同时访问的代码
相关数据段
进程控制块（PCB）
描述进程的基本情况和运行状态，是进程存在的唯一标志
创建进程，本质上就是创建进程实体中的PCB
特征
动态性（基本特征）
进程是程序的一次执行过程，具有动态的生命周期
并发性
多个进程实体同存于内存中，能在一段时间内同时运行
独立性
进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位
异步性
由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进
2. 进程的状态与转换
状态
运行态
并不是每一时刻都有进程处于运行态上，例如发生死锁时；但CPU若处于空闲，则就绪队列必为空
进程正在处理及上运行
单处理机中，每个时刻只有一个进程处于运行态
就绪态
进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行
就绪队列
阻塞态（等待态）
进程正在等待某一事件而暂停运行（如等待输入输出）
阻塞队列
进程的基本状态
创建态
进程正在被创建，尚未转到就绪态
结束态
进程正从系统中消失
转换
就绪态→运行态
处于就绪态的进程被调度后，获得处理机资源
运行态→就绪态
处于运行态的进程在时间片用完或是被剥夺后，让出处理机，转为就绪态
进程时间片用完后，可降低其优先级来让其他进程调度进入执行态
运行态→阻塞态
进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如I/O操作的完成）时，转为阻塞态
阻塞态→就绪态
进程等待的事件到来时，中断处理程序把其状态变为就绪态
3. 进程的组织
进程控制块
进程描述信息
进程标识符（PID）：标志各个进程，每个进程都有一个唯一的标志号
用户标识符：进程归属的用户，主要为共享和保护服务
进程控制和管理信息
进程当前状态：描述进程的状态信息，作为处理机分配调度的依据
进程优先级：描述进程抢占处理机的优先级
资源分配清单
用于说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息
处理机相关信息（处理机上下文）
处理机中各寄存器的值
PCB组织方式
链接方式
队列
索引方式
索引表
程序段
能被进程调度程序调度到CPU执行的程序代码段
程序可被多个进程共享，即多个进程可以运行同一个程序
数据段
4. 进程控制
定义：对系统中的所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能
进程的控制通常都需要操作系统内核的支持
原语：进程控制所用的程序段
执行期间不允许中断，是一个不可分割的基本单位
进程的创建
创建者：父进程
父进程与子进程共享一部分资源，但不能共享虚拟地址空间
被创建进程：子进程
创建过程（创建原语）
分配唯一的进程标志号，申请空白PCB
若PCB申请失败，则创建失败
分配进程所需资源
若资源不足，则处于创建态，等待资源
初始化PCB
插入就绪队列，等待被调度运行
进程的终止
引起进程终止的事件
正常结束
异常结束
如存储区越界，保护错、非法指令、运行超时、I/O故障等
外界干预
如操作系统干预、父进程请求和父进程终止
终止过程（终止原语）
根据被终止进程的标识符，检索PCB，读取状态
若处于执行态，则终止执行，并调度处理及资源
终止子孙进程
归还进程资源给父进程或操作系统
在队列（链表）中删除PCB
阻塞和唤醒
阻塞
正在执行的线程的主动行为
只有运行态线程才可能转为阻塞态
阻塞原语
找到要被阻塞的线程的标志号和PCB
若该进程为运行态，则保护其线程，转为阻塞态，停止运行
把该PCB插入等待队列，调度CPU资源给其他就绪线程
唤醒
当被阻塞进程所期待的事件发生时调用
与阻塞原语成对出现
唤醒原语
在该事件的等待队列中找到对应线程的PCB
将其移出等待队列，置其状态为就绪态
将PCB插入就绪队列，等待调度
5. 进程的通信
低级通信方式
PV操作（两组不可被中断的低级的进程通信原语）
高级通信方式
共享存储（共享内存区）
定义：在通信的进程之间存在一块可以直接访问的共享空间，通过对这片共享进行读/写操作实现进程之间的信息交换
需要使用同步互斥工具（如P/V操作）对共享空间的写/读进行控制
分类
低级方式的共享：基于数据结构的共享
高级方式的共享“基于存储区的共享
消息传递
定义：进程间的数据交换以格式化的消息为单位，通过系统提供的发送信息和接收信息的两个原语进行数据交换
隐藏了通信实现细节，使通信过程对用户透明，是应用最广泛的进程间通信机制；微内核与服务器之间的通信就采用了消息传递机制
分类
直接通信方式
发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上
发生进程把消息发送到某个中间实体（信箱），接收进程从中间实体取得消息
间接通信方式
管道通信
定义
管道：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件
向管道提供输入的发送进程（写进程），以字符流形式将大量的数据写入管道
接受管道输出的接收进程（读进程），则从管道中读数据
遵循先进先出（FIFO）原则
协调机制
互斥
同步
确定对方的存在
半双工通信
从管道读取数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据
管道只能采用半双工通信，即某一时刻只能单向传输；要实现父子进程互动通信，需定义两个管道
共享文件
利用操作系统提供的文件共享功能实现进程之间的通信
需要引入信号量机制来解决文件共享操作中的同步和互斥问题
6. 线程和多线程模型
线程的概念
目的
引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量
引入线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能
进程中的一个实体，是被系统独立调度和分派的基本单位
“轻量级进程”，基本的CPU执行单位，程序执行流的最小单元，有线程ID、程序计数器、寄存器集合和堆栈组成
线程不拥有系统资源，但有唯一标志符和线程控制块（TCB），记录了线程执行的寄存器和栈等现场状态
TCB仅针对内核级线程而言，仅在“一对一”的多线程模型中，才有“每个用户线程对应一个线程控制块”
同一进程中的多个线程共享代码段（代码和常量）、数据段（全局变量和静态变量）、扩展段（堆存储）；但每个线程拥有自己的栈段（运行时段），用于存放所有的局部变量和临时变量，它对其他线程是透明的
线程与进程的比较
调度
线程是独立调度的基本单位，其切换代价远低于进程
并发性
相同/不同进程内的线程可以并发执行，从而使操作系统具有更好的并发性
拥有资源
进程是系统中拥有资源的基本单位，线程不拥有系统资源，但可以访问其隶属进程的资源
独立性
每个进程有着独立的地址空间和资源，其线程共享这些资源，且不能被其他线程访问
系统开销
支持多处理机系统
可以将进程的多个线程分配到多个处理机上执行
线程的状态
执行状态
就绪状态
阻塞状态
线程的基本状态的转换同进程
线程的实现方式
用户级进程（ULT）
在用户级线程中，有关线程管理（创建、撤销和切换等）的所有工作都由应用程序在用户空间中完成，内核意识不到线程的存在，因此，系统调度仍是以进程为单位的
应用程序可以通过使用线程库设计成多线程程序
优点
线程切换不需要转换到内核空间，节省了模式切换的开销
不同进程可以使用不同的调度算法
用户程序自己管理线程
缺点
系统调用的阻塞问题
当线程执行一个系统调用时，该进程的所有线程都会被阻塞
不能发挥多处理机的优势
内核每次分配给进程的仅有一个CPU，因此进程只有一个线程能执行
内核级线程（KLT）
无论是系统进程还是用户进程，都是在操作系统内核的支持下运行的，线程管理的所有工作也是在内核空间实现的
优点
能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行
若进程中的一个线程被阻塞，内核可以调度其他线程占用处理机
线程切换较快
内核本身也可以采用多线程技术，提高效率
缺点
同一进程中的线程切换，需要从用户态转到核心态执行，系统开销较大（因为用户进程的线程在用户态运行，而线程的调度和管理是在内核实现的）
组合方式
内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程
一些内核级线程对应多个用户级线程，这是用户级线程通过时分多路复用内核级线程实现的
同一进程中的多个线程可以同时在多处理机上并行执行，且阻塞一个线程时不需要将整个进程阻塞
线程库
为程序员提供创建和管理线程的API
实现方式
在用户空间中提供一个没有内核支持的库，调用库中的一个函数只导致用户空间中一个本地函数的调用
实现由操作系统直接支持的内核级的一个库，调用库中的一个API通常会导致对内核的系统调用
多线程模型
多对一模型
将多个用户级线程映射到一个内核级线程
线程的调度和管理在用户空间完成，仅当需要访问内核时，才将一个线程映射到内核级线程上
优点
线程管理在用户空间进行，效率较高
缺点
若一个线程阻塞，则整个进程阻塞
在任何时候，只有一个线程能访问内核
一对一模型
将每个用户级线程映射到一个内核级线程
优点
并发能力较强
缺点
创建用户线程开销较大
多对多模型
将n个用户线程映射到m个内核级线程上（n≥m）
处理机调度
调度的概念
基本概念
处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行
调度的层次
高级调度（作业调度）
内存与辅存之间的调度
从外存上处于后备队列的作业中挑选若干个，为其分配内存、设备等资源，并建立相应进程
每个作业只调入、调出一次
作业是从用户角度提交的，以用户任务为单位
中级调度（内存调度）
存储器的对换功能
将暂时不能运行的进程调至外存等待，此时进程的状态变为挂起态
当他们具备运行条件且内存空闲时，将其重新调入内存，变为就绪态
目的是提高内存利用率和系统吞吐量
低级调度（进程调度）
按某种算法从就绪队列中选取一个进程，为其分配处理机
最基本的一种调度
调度的目标
CPU利用率
系统吞吐量
单位时间内CPU完成作业的数量
周转时间
从作业提交到作业完成所经历的时间
是作业等待、在就绪队列中排队、在处理机上运行及输入/输出操作所花费时间的总和
带权周转时间：
等待时间
进程处于等处理机的时间之和
响应时间
从用户提交请求到系统首次产生响应所用的时间
在分时系统中，响应时间与时间片和用户数成正比
调度的实现
调度程序（调度器）
排队器
将系统中所有就绪进程按一定策略排成一个或多个队列，以便于调度程序选择
每当一进程变为就绪态时，排队器便将其插入相应的就绪队列中
分派器
依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程
上下文切换器
将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行
移除分派程序的上下文，将新选进程的CPU现场信息装入处理机的各个相应寄存器
基于硬件实现，通常采用两组寄存器，一组供内核使用，一组供用户使用；上下文切换时，只需改变指针，让其指向当前寄存器组即可
调度的时机、切换与过程
不能进行进程调度与切换的情况
在处理中断的过程中
中断不应被剥夺处理机资源
进程在操作系统内核临界区中
其他需要完全屏蔽中断的原子操作过程中
应该进行进程调度与切换的情况
发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换
若操作系统只在这种情况下进行进程调度，则是非剥夺调度
中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换
剥夺方式的调度
进程调度方式
非抢占式调度方式（非剥夺方式）
仅当程序运行完成或进入阻塞态时，才让出处理机
优点：实现简单，开销小，适用于批处理系统
缺点：不能用于分时和实时系统
抢占调度方式（剥夺方式）
闲逛进程
没有就绪进程时才会运行，优先度最低
不需要CPU以外的资源，不会被阻塞
两种线程的调度
用户级线程调度
内核不知道线程的存在，仅选择一个进程并分配时间，由进程中的调度程序决定线程运行
线程切换在同一进程中进行，仅需少量机器指令
内核级线程调度
内核选择一个特定的线程运行并赋予时间片，不需考虑它属于哪个进程
线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，延迟较大
典型的调度算法
先来先服务（FCFS）调度算法
最简单的调度算法，既可用于作业调度，又可用于进程调度
不可剥夺算法，进程直到运行完成或阻塞时才释放CPU
优点
算法简单，对长作业有利
有利于CPU繁忙型作业
缺点
效率低
对短作业不利，不能作为分时和实时系统的主要调度策略
不利于I/O繁忙型作业
短作业优先（SJF）调度算法
对短作业（进程）优先调度的算法
优点
平均等待时间、平均周转时间最少
缺点
对长作业不利，容易导致”饥饿“现象
未考虑作业的紧迫程度
优先级调度算法
分类
是否抢占
非抢占式优先级调度算法
抢占式优先调度算法
优先级是否可变
静态优先级
动态优先级
优先级原则
系统进程>用户进程
交互型进程>非交互型进程
I/O型进程>计算型进程
高响应比调度算法
用于作业调度，选取后备队列中响应比最高的作业投入运作
公式
作业的等待时间相同时，服务时间越短，响应比越高，故有利于短作业，类似于SJF
服务时间相同时，等待时间越长，响应比越高，类似于FCFS
克服了长作业的”饥饿“现象
时间片轮转调度算法
适用于分时系统
时间片结束后，被剥夺的进程返回就绪队列的末尾重新排队
若时间片足够大，则退化为先来先服务调度算法
若时间片过小，则进程切换的开销增大
多级队列调度算法
设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列
多级反馈队列调度算法
实现思想
设置多个就绪队列，优先级递减
赋予各个队列的进程运行时间片，优先级越高，时间片越小
每个队列采用FCFS算法；当新进程进入内存后，先放入第1级队列的末尾，若它在第一个时间片内未完成，则转入第2级队列的末尾等待调度；在第n级队列中采用时间片轮转方式运行
按队列优先级调度；仅当第1级队列为空时，才调度下一级队列的进程运行
优势
终端型作业用户
短作业优先
短批处理作业用户
周转时间较短
长批处理作业用户
经过前面几个队列得到部分执行，不会长期得不到处理
进程切换
上下文切换
定义：切换CPU到另一个进程时需要保存当前进程状态并恢复另一个进程的状态，上下文是指某一时刻CPU寄存器和程序计数器的内容
过程
挂起一个进程，保存CPU上下文，包括程序计数器的其他寄存器
更新PCB信息
把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列
选择另一个进程执行，并更新其PCB
跳转到新进程PCB中的程序计数器所指向的位置执行
恢复处理机上下文
上下文切换的消耗
上下文切换通常时计算密集型的，需要相当可观的CPU时间
有些处理器提供多个寄存器组，这样，上下文切换只需要简单改变当前寄存器组的指针
上下文切换与模式切换
子主题
模式切换是指用户态与内核态之间的切换，并不改变当前进程
上下文切换是进程的切换，只能发生在内核态
同步与互斥
1. 基本概念
临界资源
定义：临界资源是一次仅允许一个进程使用的资源，在每个进程中，访问临界资源的那段代码称为临界区
临界资源与共享资源的区别在于，在一段时间内能否允许被多个进程访问（并发使用）；例如磁盘属于共享资源，公用队列属于临界资源
临界资源的访问过程
进入区
检查可否进入临界区，若能，则设置正在访问临界区的标志，以阻止其他进程访问
临界区
进程中访问临界资源的那段代码，又称临界段
退出区
将正在访问临界区的标志清除
剩余区
代码中的其余部分
同步
直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作
互斥
间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区，另一个进程才允许访问次临界资源
原则
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待
当已有进程进入临界区，其他试图进入临界区的进程必须等待
有限等待
对请求访问的进程，应保证能在有限时间内进入临界区
必须遵循的原则
让权等待
当进程不能进入临界区时，应立即释放处理器，防止进程忙等待
2. 实现临界区互斥的基本方法
软件实现方法
算法1：单标志法
设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号
可确保每次只允许一个进程进入临界区，但两个进程必须交替进入，若某个进程不再进入临界区，则另一个进程也将无法进入，违背“空闲让进”
算法2：双标志法先检查
在每个进程访问临界区前，先查看临界资源是否正被访问；若是则等待，若否则进入临界区。设置一个数据flag[i]，如第i个元素值为false，表示Pi进程未进入临界区
优点
不用交替进入，可连续使用
缺点
检查和修改的操作不能一次进行，按序列①②③④执行时，Pi和Pj会同时进入临界区，违背“忙则等待”
算法3：双标志法后检查
进程先将自己的标志设置为TRUE，再检测对方的状态标志，若对方标志为TRUE，则进程等待；否则进入临界区
问题
若两个进程同步想要进入临界区，分别将自己的标志值置为TRUE，并同时检测到对方的状态，互相谦让，导致“饥饿”现象
算法4：Peterson's Algorithm
为了防止两个进程为进入临界区而无限期等待，又设置了变量turn
硬件实现方法
提供硬件支持实现临界段的问题方法称为低级方法，又称元方法
中断屏蔽方法
CPU只有在发生中断时才能切换进程，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利执行完，从而保证互斥，然后执行开中断
问题
限制了处理机交替执行程序的能力，执行效率降低；且用户不应具备开关中断的能力
硬件指令方法
TestAndSet指令
原子指令，功能是读出指定标志后把该标志设置为真
功能描述
为每个临界资源设置一个共享布尔变量lock，表示资源状态
Swap指令
交换两个字（字节）的内容
功能描述
为每个临界资源设置一个共享布尔变量lock，表示资源状态；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息
优点
适用于任意数目的进程，而不管是单处理机还是多处理机
简单、容易验证其正确性
支持进程内有多个临界区，只需为每个临界区设立一个布尔变量
缺点
进程等待进入临界区时要耗费处理机时间，不能实现让权等待
可能导致“饥饿”现象
3. 互斥锁
解决临界区最简单的方法。每个互斥锁都有一个布尔变量available，表示锁是否可用；一个进程在进入临界区时提供acquire()函数获得锁，在退出临界区时通过release()函数释放锁
acquire()和release()必须是原子操作，因此互斥锁通常采用硬件机制来实现
缺点
忙等待，当一个进程在临界区时，其他进程在进入临界区时必须连续循环调用acquire()，浪费CPU周期；因此，互斥锁常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程执行
4. 信号量
只能被两个标准原语wait(S)和signal(S)访问，即“P操作”和“V操作”
原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件实现，也可由软件通过屏蔽中断方法实现
分类
整型信号量
定义：一个用于表示资源数目的整型量S
当S≤0时，wait操作将”忙等待“，违背了”让权等待“的准则
记录型信号量
数据结构
操作描述
wait
S.value--表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，进程调用block原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列S.L，遵循了”让权等待“原则
signal
S.value++表示释放一个资源；若释放后仍有S.value≤0，则表示在S.L中仍有等待该资源的进程被阻塞，则调用wakeup原语，将S.L中的第一个等待进程唤醒
利用信号量实现进程同步
设S为实现进程P1，P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。
利用信号量实现进程互斥
设S为实现进程P1，P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1(即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两个进程对临界资源的互斥访问。
利用信号量实现前驱关系
5. 管程
定义
代表共享资源的数据结构，以及由对改共享数据结构实施操作的一组过程所组成的资源管理程序
组成
管程名称
局部于管程内部的共享数据结构说明
对该数据结构进行操作的一组过程（或函数）
对局部于管程内部的共享数据设置初始值的语句
条件变量
当一个进程进入管程后被阻塞时，将阻塞原语定义为条件变量condition；每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程；
操作
x.wait
当x对应的条件不满足时，正在调研管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程
x.signal
x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程
6. 经典同步问题
生产者-消费者问题
问题描述
一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。
信号量设置
信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1
信号量full用于记录当前缓冲池中的“满”缓冲区数，初值为0
信号量empty用于记录当前缓冲池中的“空”缓冲区数，初值为n
注：不可以先P(mutex)再P(empty)，否则将引起死锁
读者-写者问题
问题描述
问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
1||| 允许多个读者可以同时对文件进行读操作
2||| 只允许一个写者往文件中写信息
3||| 任一写者在完成写操作之前不允许其他读者或写者工作
4||| 写者执行写操作前，应让已有的读者和写者全部退出。
信号量设置
设置信号量count为计数器，用于记录当前读者的数量，初值为0
设mutex 为互斥信号量，用于保护更新count变量时的互斥
设mutex 为互斥信号量，用于保护更新count变量时的互斥
读进程优先
可能导致写进程“饿死”
写进程优先（读写公平法）
哲学家进餐问题
问题描述
一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。
信号量设置
定义互斥信号量数组 chopstick[5]= {1,1,1,1,1}，用于对5个筷子的互斥访问。哲学家按顺序编号为0～4，哲学家i左边筷子的编号为i，哲学家右边筷子的编号为（i+1）%5
实现算法
可能引起死锁
设置互斥信号量，每次同时取左右两边的筷子
死锁
死锁的概念
定义
多个进程因竞争资源而造成的一个僵局（互相等待），若无外力作用，这些进程进程都将无法向前推进
产生的原因
系统资源的竞争
只有对不可剥夺资源的竞争才可能产生死锁
进程推进顺序非法
死锁产生的必要条件
互斥条件
一段时间内某资源仅为一个进程所占有
不剥夺条件
资源不能被强行夺走，只能由进程主动释放
请求并保持条件
进程已经保持了至少一个资源，并又提出新的资源请求，进而阻塞
循环等待条件
存在一种进程资源的循环等待链
仅当每种资源都只有一个时，资源分配图含圈才是死锁的充分必要条件
处理策略
死锁预防
避免死锁
事先预防策略
死锁的检测及解除
死锁预防
破坏互斥条件
允许系统资源都能共享使用（较难实现）
破坏不剥夺条件
常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，不能用于打印机之类的资源
破坏请求并保持条件
采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源
实现简单，但浪费系统资源
破坏循环等待条件
采用顺序资源分配法
死锁避免
系统安全状态
允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态（不一定会导致死锁），则允许分配；否则让进程等待。
安全状态，是指系统能按某种进程推进顺序(P, Pz,…,Pn)为每个进程P；分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称P1, P2…，Pn，为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。
银行家算法
思想
把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
数据结构
可利用资源向量Available
含有m个元素的数组，其中每个元素代表一类可用的资源数目
最大需求矩阵Max
n×m矩阵，定义系统中n个进程中的每个进程对m类资源的最大需求
分配矩阵Allocation
n×m矩阵，定义系统中每类资源当前已分配给每个进程的资源数
需求矩阵Need
n×m矩阵，表示每个进程接下来最多还需要多少资源；Need=Max-Allocation
算法过程
安全性算法
死锁检测和解除
资源分配图
请求边：从进程到资源的有向边，表示该进程申请一个单位的该类资源
分配边：从资源到进程的有向边，表示该类资源已有一个资源分配给了该进程
死锁定理
（1） 在资源分配图中，找出既不阻塞又不孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量，如在图2.15中，R1没有空闲资源，R2有一个空闲资源。若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图2.16(a)中，P1是满足这一条件的进程结点，将P的所有边消去，便得到图2.16(b)所示的情况。
（2） 进程Р1所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图2.15中，进程Pz就满足这样的条件。根据(1)中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，如图2.16(c)所示。
（3）
（4） S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的
死锁解除
资源剥夺法
撤销进程法
进程回退法
硬件方法不能实现让权等待
信号量
互斥量
初值为1
当互斥量小于等于0时，其绝对值等于临界区外等待进入的进程数
资源量
初值可以是任意整数，表示可用的资源数