导图社区 进程管理思维导图
- 101
- 4
- 2
- 举报
进程管理思维导图
计算机操作系统第二章进程管理讲述了进程与线程的基本概念、进程与线程的状态与转换、线程的实现、进程与线程的组织与控制、进程间通信。
编辑于2021-10-04 16:45:52- 计算机统考
- 相似推荐
- 大纲
（一）进程与线程
1、进程与线程的基本概念
1.进程的定义
进程控制块(Process Control Block, PCB):操作系统中配置的一个专门的数据结构，用于描述进程的基本情况和活动过程，进而控制和管理进程，是进程存在的唯一标志
由程序段、相关的数据段和PCB三部分构成了进程实体(又称进程映像)，进程实体简称进程
所谓创建进程，实质上是创建进程实体中的PCB;而撤销进程，实质上就是撤销进程的PCB
进程的典型定义
(1)进程是程序的一次执行
(2)进程是一个程序及其数据在处理机上的顺序执行时所发生的活动
(3)进程是具有独立功能的程序在一个数据集合上所运行的过程，它是系统进行资源分配和调度的一个独立单位
我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”
进程是一个具有独立功能的程序关于某个数据集合的一次运行活动
为了使程序在多道程序环境下能够并发执行，并能对并发执行的程序加以控制和描述，从而在操作系统中引入了进程的概念。影响：使程序得以并发执行
5.在操作系统中为什么要引入进程的概念？它会产生什么样的影响？
2.进程的特征
(1)动态性。
进程的实质是进程实体的执行过程(它由创建而产生，由调度而执行，由撤销而消亡)，因此动态性就是进程的最基本的特征
程序则只是一组有序指令的集合，并存放于某种介质上，其本身不具有活动的含义，因而是静态的
(2)并发性。
是指多个进程实体同存于内存中，并能在一段时间内同时运行。
而程序(没有建立PCB)是不能参与并发执行的
(3)独立性。
是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
对于未建立任何进程的程序，不能作为一个独立的单位而运行
(4)异步性。
是指进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。
3.线程的引入带来的变化
线程的基本概念
是一个基本的CPU执行单元，也是程序执行流的最小单位，可以理解为轻量级进程
资源分配、调度
传统的进程机制中，进程是资源分配和调度的基本单位
引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
并发性
传统进程机制中，只能进程间并发
引入线程后，各线程间也能并发，提升了并发度
系统开销
传统的进程间并发，需要切换进程的运行环境，系统开销很大
线程间并发，如果是同一进程内的线程切换，则不需要切换线程环境，系统开销小
引入线程后，并发带来的系统开销减小
4.线程的属性
(1)轻型实体
(2)独立调度和独立分派的基本单位
(3)可并发执行
(4)共享进程资源
5.线程与进程的比较
1.调度的基本单位
传统OS中，进程是作为独立调度和资源分配的基本单位
引入线程的OS中，进程是作为资源分配的基本单位，而线程是能独立调度的基本单位
同一进程的各线程共享进程拥有的资源
同一进程内的线程切换不会导致进程切换
2.并发性
引入线程的OS中，不仅进程之间可以并发执行，而且在一个进程中的多个甚至所有线程亦可以并发执行。同样，不同进程中的线程也能并发运行，增大了系统的吞吐量
3.拥有资源
进程可以拥有资源，并作为系统中拥有资源的一个基本单位。
线程并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源
线程除了拥有自己的少量资源外，还允许多个线程共享该进程所拥有的资源
4.地址空间和其他资源
某进程内的线程对于其他进程不可见
进程都拥有一个独立的地址空间和其他资源，除了共享全局变量外，不允许其它进程的访问
线程之间共享进程的内存地址空间和资源，每个线程都可以访问它们所属进程地址空间中的所有地址
5.系统开销
创建或撤销进程时，系统要为之分配和回收PCB和其他资源，并且进程切换时，涉及到上下文的切换
线程撤销或创建的开销明显小于进程，而线程切换的代价也远远小于进程
6.支持多处理机系统
在多处理机系统中，对于传统的进程(单线程进程)，不管有多少处理机，该进程只能运行在一个处理机上。但对于多线程进程，可以将多个线程分配到多个处理器上，使它们并行执行
2、进程/线程的状态与转换
1.进程的状态
1.进程的三种基本状态
(1)就绪(Ready)状态:指进程已处于准备好运行的状态，即进程已分配到除CPU意外的所有必要资源后，只要再获得CPU，便可立即执行。
CPU×其他所需资源√
(2)执行(Running)状态:指进程已获得CPU，其程序正在执行的状态。
CPU√其他所需资源√
(3)阻塞(Block)状态:指正在执行的进程由于发生某事件(如I/O请求、申请缓冲区失败等)暂时无法继续执行时的状态，亦即进程的执行受到阻塞。
CPU×其他所需资源×
2.创建状态和终止状态
为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性，通常在系统中又为进程引入两种常见状态
创建状态：操作系统为新进程分配资源、创建PCB
终止状态：操作系统回收进程的资源、撤销PCB
2.进程的转换
三种基本状态的转换
(1)就绪状态→执行状态：进程分配到CPU资源，被调度
(2)执行状态→就绪状态：时间片用完，或者CPU被更高优先级的进程抢占
(3)执行状态→阻塞状态：I/O请求，等待系统资源分配（主动完成）
(4)阻塞状态→就绪状态：I/O完成，资源分配到位，等待CPU分配（被动完成）
创建状态→就绪状态：系统完成创建进程的相关工作
运行状态→终止状态：进行运行结束或者遇到不可修复的错误
3、线程的实现
线程库支持的线程 (用户级线程User-Level Thread，ULT)
(1)概念：仅存在于用户空间中的线程，无须内核支持。这种线程的创建、撤销、线程间的同步与通信等功能，都无需利用系统调用实现。用户级线程的切换通常发生在一个应用进程的诸多线程之间，同样无需内核支持。
何谓用户级线程？
(2)特点
用户级线程是通过线程库实现的
所有线程管理工作都由应用程序负责(包括线程切换)
用户级线程中，线程切换可以在用户态下完成，无需操作系统干预
在用户看来，程序是有多个线程，但操作系统的内核下来看，并不能意识到线程的存在(用户级线程对用于不透明，对操作系统透明)
(3)优点
线程切换不需要转换到内核空间
调度算法可以使进程专用的
用户级线程的实现与OS平台无关
(4)缺点
系统调用的阻塞问题
在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点，内核每次分配给一个进程的仅有一个CPU，因此，进程仅有一个线程能执行，不能实现并行
多对一模型有何优缺点？
(5)实现
用户级线程是在用户空间中的实现的，运行在“运行时系统”与“内核控制线程”的中间系统上。运行时系统用于管理和控制线程的函数的集合。内核控制线程或轻型进程(Light Weight Process, LWP)可通过系统调用获得内核提供服务，利用LWP进程作为中间系统。
试说明用户级线程的实现方法。
内核支持的线程 (内核级线程Kernal Supported Thread, KST)
(1)概念：内核支持下运行的线程。无论是用户进程中的线程，还是系统线程中的线程，其创建、撤销和切换等都是依靠内核，在内核空间中实现的。在内核空间里还为每个内核支持线程设置了线程控制块，内核根据该控制块感知某线程的存在并实施控制。
何谓内核支持线程？
(2)特点
内核级线程是由操作系统内核完成
线程调度、切换等工作都由内核负责
内核级线程中，线程切换必然在核心态下完成
可以理解的是，“内核级线程”就是“从操作系统内核视角看能看到的线程”
(3)优点
①在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行
②如果其中一个线程被阻塞了，内核可以调度其他线程占有处理机运行，也可以运行其他进程中的线程
③内核支持线程具有很小的数据结构和堆栈，现成的切换比较快，切换开销小
④内核本身可以采用多线程技术，可以提高系统的执行速度和效率
(4)缺点
对于用户的线程切换而言，其模式切换的开销较大，同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态
多线程模型
1)多对一模型
概念
多个用户级线程映射到一个内核级线程。每个用户线程只对应一个内核线程
优点、缺点见ULT
2)一对一模型
概念
同于KST，一个用户级线程映射到一个用户级线程。每个用户线程都有同数量的内核线程
优点、缺点见KST
3)多对多模型
在同时支持用户级线程和内核支持线程的系统中，可采用二者的组合方式：将n个用户级线程映射到m个内核级线程上(n>=m)
操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位
如左边这个模型：该进程有两个内核级进程，所以在用户看来三个线程也只能分配到两个内核，因此最多只有两个用户线程能够并行，即一个线程和两个并发的线程并行
用户级线程是“代码逻辑的载体”
内核级线程是“运行机会的载体”
要点
内核级线程才是处理机分配的单位，只有映射到了内核级线程的用户级线程才能被执行
内核级线程可以运行任意一个有映射关系的用户级线程，只有一个进程所对应的多个内核级线程都被阻塞时，进程才被阻塞
4、进程与线程的组织与控制
1.进程的控制
进程的创建
进程的层次结构
把创建进程的进程称为父进程，把被创建的进程称为子进程。子进程可以继续创建孙进程由此便形成了一个进程的层次结构，在UNIX中，进程们功能组成了一个进程家族(组)
子进程可以继承父进程的所有资源，例如继承父进程打开的文件，分配到的缓冲区等。子进程被撤销后需要归还资源给父进程。父进程被撤销后，必须同时撤销子进程。PCB中设置了家族关系表项，以表明自己的父进程及所有的子进程。进程不能拒绝其子进程的继承权
在Windows中，不存在任何进程层次结构的概念，所有进程都有相同的地位。进程之间的关系仅仅是获得句柄与否、控制与被控制的简单关系
引起创建进程的事件
(1)用户登录
(2)作业调度
(3)提供服务
(4)应用请求
进程的创建(Creation of Process)过程
出现了创建新进程的请求后，OS便调用进程创建原语Creat按以下步骤创建一个新进程
(1)申请空白PCB，为进程获得唯一的数字标识符，并从PCB集合中索取一个空白PCB，若申请PCB失败则创建失败
(2)为新进程分配其运行所需的资源，包括各种物理和逻辑资源，若申请资源失败，则进入阻塞状态
(3)初始化进程控制块PCB
①初始化标志信息
②初始化处理机状态信息
③初始化处理机控制信息
④初始化进程的优先级
(4)如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列
进程的终止
引起进程终止的事件
(1)正常结束
进程任务已经完成，准备退出运行
在批处理系统中，通常在程序的最后安排一条Halt指令表示进程完成
在分时系统中，用户可利用Logs off去表示进程运行完毕
(2)异常结束
①越界错
②保护错
③非法指令
④特权指令错
⑤运行超时
⑥等待超时
⑦算术运算错
⑧I/O故障
(3)外界干预
①操作员或操作系统终止进程
②父进程请求终止进程
③因父进程终止
2.进程的终止(Termination of Process)过程
当系统中发生了要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止特定的进程
(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，读出该进程的状态
(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
(3)若该进程还有子孙进程，应将其所有的子孙进程都予以终止，以防它们成为不可控的进程
(4)将被终止进程所拥有的的全部资源归还给父进程或者是系统
(5)将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息
进程的阻塞与唤醒
1.引起阻塞和唤醒的事件
(1)向系统请求资源失败：如请求打印机但打印机资源已被占用
(2)等待CPU操作的完成：如等待I/O操作完成后再由中断处理程序唤醒进程
(3)新数据尚未到达：如进程A未收到需要的来自进程B的数据，此时便阻塞A
(4)等待新任务的到达：在网络环境下的OS，某些进程完成任务后就将自身阻塞起来等待新任务的到来
2.进程阻塞过程
进程调用阻塞原语block将自己阻塞
(1)根据进程标识符找到被阻塞进程对应的PCB
(2)若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行
(3)把该PCB插入相应事件的等待队列，将处理机资源调度给其他就绪进程
3.进程唤醒过程
有关进程调用唤醒原语wakeup将等待该事件的进程唤醒
(1)根据进程标识符从等待队列中找到相应的PCB
(2)将其从等待队列中溢出，并设置其状态为就绪态
(3)把该PCB插入就绪队列中，等待调度程序调度
Block原语和wakeup原语是一对作用刚好相反的原语，必须成对使用
进程切换
进程切换过程
(1)保存处理机上下文，包括程序计数器和其他寄存器
(2)更新PCB信息
(3)将进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列
(4)选择另一个进程执行，并更新其PCB
(5)更新内存管理的数据结构
(6)恢复处理机的上下文
2.进程的组织
进程控制块PCB
PCB的作用
PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。
(1)作为独立运行基本单位的标志。当一个程序(含数据)配置了PCB后，就表示它已是一个能够在多道程序环境下独立运行的、合法的基本单位。PCB已成为进程存在系统中的唯一标志
7.为什么说PCB是进程存在的唯一标志？
(2)能实现间断性运行方式。当进程因阻塞而暂停运行时，它必须保留自己运行CPU现场信息，再次被调度运行是恢复其CPU现场信息。
(3)提供进程管理所需要的信息。进程的整个生命期中，操作系统总是根据PCB实施对进程的控制和管理
(4)提供进程调度所需要的信息。只有处于就绪状态的进程才能被调度执行，而在PCB中就提供了进程处于何种状态的信息。
(5)实现与其它进程的同步与通信。进程同步机制是用于实现诸进程的协调运行的，在采用信号量机制时，它要求每个进程中都设置有相应的用于同步的信号量。PCB中还有用于实现进程通信的区域或通信队列指针等。
PCB中的信息
(1)进程标识符
外部标识符UID:创建者提供，通常有字母与数字组成，往往是由用户(进程)在访问该进程时使用。
内部标识符PID:操作系统为每一个进程赋予的唯一数字标识符，系统使用
(2)处理机状态相关信息
通用寄存器
指令计数器
程序状态字PSW
用户栈指针
(3)进程控制和管理信息
进程状态
进程优先级
进程调度所需的其他信息
事件
程序和数据的地址
进程同步和通信机制
资源清单
链接指针
PCB提供了进程管理和进程调度所需要的哪些信息？
(4)资源分配清单
代码段指针
数据段指针
文件描述符
堆栈段指针
PCB的组织方式
(1)线性方式:将系统中的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。实现简单，开销小，但每次都需要扫描整张表，因此适合进程数目不多的系统
(2)链接方式:把具有相同状态进程的PCB通过PCB中的链接字连成一个队列
(3)索引方式:系统根据所有进程状态的不同，建立几张索引表，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址
程序段
程序段就是能被进程调度程序调度到CPU执行的程序代码段
注意：程序可被多个进程共享，即多个进程可以运行同一个程序
数据段
一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行产生的中间或最终结果
3.线程的控制
线程的创建
应用程序启动时，会生成一个初始化线程用于创建新线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程的创建函数执行完后，将返回一个线程标识符供以后使用
线程的终止
当一个线程完成了自己的任务后，或是线程在运行中出现异常情况而必须被强制终止时，由终止进程通过调用相应的函数(或系统调用)对它执行终止操作
5、进程间通信
1.共享内存 Shared-Memory System
(1)基于共享数据结构的通信方式：只适用于传递相对少量的数据，通信效率低下，属于低级通信。如在生产者-消费者问题中的有界缓冲期
(2)基于共享存储区的通信方式：为了传输大量数据，在内存中划出了一块共享存储区域，对该共享区的读或写交换信息，数据的形式和位置甚至访问控制都是由进程负责，而不是OS。这种通信方式属于高级通信
两个进程对共享空间的访问需要互斥
2.消息传递系统 Message passing system
在该机制中，进程不必借助任何共享存储区和数据结构，而是以格式化的消息(message)为单位(消息头+消息体)，将通信的数据封装在消息中，并利用操作系统的一组通信命令(原语)，在进程间进行消息传递，完成进程间的数据交互
基于消息传递系统的通信方式属于高级通信方式
(1)直接通信方式，是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程
(2)间接通信方式，是指发送和接收进程，都通过共享中间实体(称为信箱)的方式进行消息的发送和接收，完成进程间的通信
3.管道(Pipe)通信方式
所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，即一片固定大小的缓冲区，又名pipe文件
所谓“管道通信”，向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。它能有效地传送大量数据
特点
管道只能采用半双工通信，如果要实现双向同时通信，则需要设置两个管道
管道机制必须提供的协调能力
①互斥，即当一个进程正在对pipe执行读或写操作时，其他进程必须等待
②同步，即当写(输入)进程把一定数量(如4KB)的数据将pipe写满，写进程的write()系统调用将被阻塞，直到读(输出)进程取走数据后再把它唤醒。当读进程读一空pipe时，读进程的read()系统调用将被阻塞，直至写进程将数据写入管道后才将之唤醒
③确定对方是否存在，只有确定了对方已存在时才能进行通信
数据一旦读出，就从管道中被抛弃，这意味着读进程最多只有一个，但可有多个写进程
（二）CPU调度与上下文切换
1、调度的基本概念
1.调度的基本概念
在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度就是对处理机分配，即从就绪队列中按照一定的算法，选择一个进程给它运行，以实现进程的并发地执行
2.处理机调度的层次
1.高级调度 (High Level Scheduling)
又称长程调度或作业调度
调度对象是作业
功能是根据某种算法，决定外存上处于后备队列的几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入就绪队列。
高级调度的主要任务是什么？
主要用于多道批处理系统
2.低级调度 (Low Level Scheduling)
又称短程调度或进程调度
调度对象是进程
功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给选中的进程
低级调度的主要任务是什么？
进程调度作为最基本的调度，在多道批处理系统、分时和实时三种系统中
3.中级调度 (Intermediate Scheduling)
又称内存调度
中级调度实际上就是存储器管理中的对换功能
功能是把暂时不能运行的进程调至外存等待，此时的进程状态称为挂起状态。当挂起进程具备了运行条件且内存稍有空闲时，重新将其调入内存，使其变为就绪状态。
提高内存利用率和系统吞吐量
引入中级调度的目的是什么？
3.三层调度的联系
作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列
进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它
中级调度是为了提高内存利用率，系统将那些暂时不能运行的进程挂起来。当内存宽松时，通过中级调度选择具备运行条件的进程将其唤醒
要点
作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间
作业调度次数少，中级调度次数略多，进程调度频率最高
进程调度是最基本的，不可或缺
2、调度的目标
1.处理机调度算法的共同目标
(1)提高资源利用率
(2)公平性
(3)平衡性
(4)策略强制执行
2.批处理系统的目标
(1)平均周转时间短
平均周转时间
n为作业总数
Ti为第i个作业的周转时间(结束时刻-开始时刻)
平均带权周转时间
Ti为第i个作业的周转时间(结束时刻-开始时刻)
Ts为第i个作业的运行时间
(2)系统吞吐量高
(3)处理机利用率高
FCFS算法、SJF/SPF算法、HRRN算法更注重平均等待时间、平均周转时间、平均带权周转时间等指标，适合批处理系统
3.分时系统的目标
(1)响应时间快
(2)均衡性
4.实时系统的目标
(1)截止时间的保证
(2)可预测性
调度算法
RR、优先级调度算法、MFQ更加注重响应时间、公平性、平衡性等指标，适合用于分时系统和实时系统这类交互式系统
3、调度的实现
1.调度器/调度程序(Scheduler)
进程调度机制有三个基本组成部分：排队器、分派器和上下文切换器。他们组成了调度程序，专门用于处理进程调度
(1)排队器
为了提高进程的调度效率，应事先将操作系统中所有就绪进程按照一定策略排成一个或多个队列，以便调度程序能最快找到它。以后每当有一个进程转变为就绪状态时，排队器便将他插入到相应的就绪队列
(2)分派器
分派器根据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程
(3)上下文切换器
正在运行的进程和分派器程序之间的切换。当保存了处理机的现场信息后，正在运行的进程就会被移出，然后处理机装入分派程序运行
分派程序和新选出的进程之间的切换，把分派程序的上下文移出来，然后再装入新进程，恢复其 CPU 的现场信息，使它能够执行
2.调度的时机与调度方式
调度时机
不能进行进程调度与切换的情况
在处理中断的过程中
进程在操作系统内核程序临界区中
其他需要完全屏蔽中断的原子操作过程中
能进行进程调度和切换的情况
发生引起调度条件且当前进程无法继续进行下去时，可以马上进行调度和切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度
中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度
调度方式
抢占式
主要遵循的原则
①优先权的原则。指允许优先级高的进程抢占当前进程的处理机
②短进程优先原则。指允许新到的短进程可以抢占当前长进程的处理机
③时间片原则。即各个进程按时间片轮转进行，当正在执行的进程一个时间片用完后，便停止该进程的执行并重新调度
非抢占式
引起进程调度的因素
①正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行
②正在执行中的进程因提出I/O请求而暂停执行
③在进程通信或同步过程中，执行了某种原语操作，如block原语
优点
实现简单
系统开销小
适用于大多批处理系统。但是不能用于分时系统和大多数实时系统
3.闲逛进程
4.内核级线程与用户级线程调度
4、典型调度算法
1.先来先服务调度算法 (first-come first served, FCFS)
当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。
算法思想
从公平的角度考虑
算法规则
按照到来的先后次序进行调度(等待时间最长的作业/进程得到服务)
用于作业/进程调度
用于作业调度时，考虑的是哪个作业先到达后备队列
用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占
非抢占式的算法
优缺点
优点：公平、算法实现简单
缺点：排在长作业之后的短作业需要等待很长时间，带权周转时间很大，FCFS算法对长作业有利，对短作业不利
是否会导致饥饿
不会
2.短作业优先调度算法 (short job first, SJF)
SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。
算法思想
追求最少的平均等待时间，最少的平均周转时间和最少的平均带权周转时间
算法规则
运行时间最短的作业/进程优先得到服务
用于作业/进程调度
用于作业调度时，称作SJF最短作业调度算法
用于进程调度时，称作SPF最短进程调度算法
是否可抢占
非抢占式的算法
但是也有抢占式的短作业优先算法，称作最短剩余时间优先算法(Shortest Remaining Time Next, SRTN)
优缺点
优点：具有较短的平均等待时间、平均周转时间(SRTN算法更短)
缺点
①必须预知作业的运行时间
②对长作业非常不利，长作业的周转时间会明显增长
③采用SJF算法时，人—机无法实现交互
④该调度算法完全未考虑作业的紧迫程度，不能保证紧迫性作业得到及时处理
是否会导致饥饿
会导致长作业饥饿的现象
3.高响应比优先调度算法 (Highest Response Ratio Next, HRRN)
响应比
算法思想
综合考虑作业/进程的等待时间和要求服务时间
算法规则
每次调度时先计算各个作业的响应比，选择响应比最高的作业/进程为其服务
用于作业/进程调度
是否可抢占
非抢占式的算法
优缺点
①如果作业的等待时间相同，则要求服务的时间愈短，其优先级越高，此时类似于SJF算法
②对于要求服务的时间相同时，作业的优先度取决于其等待时间，此时类似于FCFS算法
③对于长作业的优先级，可以随等待时间的增加而提高，等待时间足够长时也会获得处理机。
综上该算法实现了较好的折中。但是每次进行调度之前都需要先做响应比的计算，显然增加了系统的开销
是否会导致饥饿
不会
4.时间片轮转 (Round-Robin, RR)
算法思想
公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
用于进程调度
只有作业放入内存建立了相应的进程后，才能被分配处理机时间片
是否可抢占
抢占式的算法，由时钟装置发出时钟中断来通知CPU时间片已到
优缺点
优点：公平，响应快，适用于分时操作系统
缺点
由于高频率的进程切换，因此有一定的开销
当时间片过长时，会退化成FCFS算法
当时间片过短时，经常进行时间片切换，开销过大会失去调度的初心
是否会导致饥饿
不会
5.优先级调度算法
优先级的类型
1)静态优先级
静态优先级在进程的创建时就确定了并在进程的整个运行期间保持不变，优先级的大小是利用某一范围内的一个整数来表示的，例如0~255中的某一整数，又把该整数称为优先数
确定优先数的依据
(1)进程类型。通常系统进程(如接收进程、对换进程)的优先级高于一般用户进程的优先级
(2)进程对资源的需求。对资源要求较少的进程应该赋予较高的优先级
(3)用户要求。根据进程的紧迫程度及用户所付费用的多少确定优先级
静态优先级法简单易行，系统开销小，但不够精确，可能出现优先级低的进程长期没有被调度的情况
2)动态优先级
动态优先级是指在创建进程之处，先赋予其一个优先级，然后其值随进程额推进或等待时间的增加而改变，以获得更好的调度性能
3)通常有
系统进程优先级＞用户进程优先级
前台进程优先级＞后台进程优先级
I/O型进程优先级＞CPU型进程优先级
让I/O设备更早的投入工作，提高资源的利用率
算法思想
随着实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
调度时选择优先级最高的作业/进程
用于作业/进程/I/O调度
是否可抢占
非抢占式优先级调度算法只需在进程主动放弃处理机时进行调度
抢占式优先级调度算法需要在就绪队列发生变化时，检查是否发生抢占
优缺点
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，可以灵活地调整对各个作业/进程的偏好程度
缺点：若源源不断的有高优先级进程到来，则可能导致饥饿
是否会导致饥饿
可能会导致低优先级的进程饥饿
6.多级反馈队列调度算法 (Multilevel Feedback Queue, MFQ)
算法思想
对其他调度算法的折中权衡
算法规则
(1)设置多个就绪队列
(2)每个队列都采用FCFS算法：每个队列中的各个进程按FCFS进行调度
(3)按队列优先级调度：队列之间的调度按照优先级高低顺序进行调度
用于进程调度
是否可抢占
抢占式的算法。在k级队列的进程运行过程中，若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列的队尾
优点
对各类型的进程相对公平(FCFS的优点)
每个新到达的进程都可以很快就得到相应(RR的优点)
短进程只用较少的时间就可以完成(SJF的优点)
不必实现估计进程的运行时间(克服SJF的缺点)
可灵活地对各类进程的偏好程度进行调整(优先级调度算法的优点)
补充：可以将因I/O而阻塞的进程重新放回队列，这样就可以保持I/O型进程的高优先级了
是否会导致饥饿
长进程执行多次之后到了较为低级的队列中，后续可能会持续到来优先级更高的进程，导致长进程产生饥饿
5、上下文及其切换机制
（三）同步与互斥
1、同步与互斥的基本概念
进程同步的基本概念
1.进程同步的概念
并发性带来了异步性，有时则需要通过进程同步解决这种异步问题，有的进程之间需要相互配合的完成工作，各个进程的工作推进需要遵循一定的先后顺序
2.进程同步的主要任务
是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性
3.进程互斥的概念
对临界资源的访问，需要互斥的进行。同一时间段里只能允许一个进程访问该资源
4.两种形式的制约关系
在多道程序环境下，对于处于同一个系统中的多个进程，由于它们共享系统的资源，或为完成某一任务而相互合作，它们之间可能存在着以下两种形式的制约关系
1）间接相互制约关系：由于临界资源必须保证多个进程对之只能互斥的访问，因此进程间形成了源于对该类资源共享的所谓间接相互制约关系，对于此类资源，进程使用之前必须进行申请后由系统实施统一分配
2）直接相互制约关系：由于某些进程为了完成同一项任务而相互合作，进程间的直接制约关系就是源于它们之间的相互合作。
5.临界资源 (critical Resource)
许多硬件资源如打印机、磁带机均为临界资源，诸进程间应采取互斥方式，实现对这种资源的共享
生产者-消费者问题 (Producer-consumer)
在并发执行的过程中，为了保证缓冲区中的产品数量counter不为0或满，应将counter作为临时资源去处理，即消费者进程和生产者进程互斥地访问变量counter
6.临界区 (critical section)
概念：人们把每个进程中访问临界资源的那段代码称为临界区
while(TRUE) { 进入区 临界区 退出区 剩余区 }
进入区：负责检查是否可进入临界区，若可进入，则应该上锁 临界区：访问临界资源的代码 退出区：负责解锁 剩余区：负责实现其他功能
进入区和退出区共同负责实现互斥
4.同步机制应遵循的规则
(1)空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源
(2)忙则等待。当已有进程处于临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问
(3)有限等待。对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死等”状态
(4)让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态
为了实现进程互斥访问自己的临界区
2、基本实现方法
进程互斥软件方法
1.单标志法
(1)算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
(2)算法实现
int turn = 0; // turn表示当前允许进入临界区的进程号
P0(){ while(turn!=0); 临界区代码; turn=1; 剩余区代码; }
P1(){ while(turn!=1); 临界区代码; turn=0; 剩余区代码; }
(3)算法特点
对于进入临界区的值，一定是按照P0→P1→P0...这样的轮流顺序，因此如果某时允许进入临界区的进程是P0，而P0一直不访问临界区，那么此时即使临界区空闲，也不允许P1访问
违背“空闲让进”原则
2.双标志先检查法
(1)算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=true”意味着0号进程P0现在想要进入临时区，每个进程进入临界区之前都该先检查当前有没有其它进程的flag标志为true，若可以进入后，将自己的表示flag设置为true后，开始访问临界区
(2)算法实现
bool flag[2]; flag[0]=false; flag[1]=false;
P0(){ while(flag[1]); flag[0]=true; 临界区代码; flag[0]=false; 剩余区代码; }
P1(){ while(flag[0]);// 检查 flag[1]=true; // 上锁 临界区代码; flag[1]=false; 剩余区代码; }
(3)算法特点
若上述实现中的“检查”操作由于进程异步发生进程切换，P0和P1将会同时访问临界区
违背“忙则等待”原则
3.双标志后检查法
(1)算法思想：双标志后检查法的改版。前一个算的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述的问题。
(2)算法实现
bool flag[2]; flag[0]=false; flag[1]=false;
PO(){ flag[0]=true; while(flag[1]); 临界区代码; flag[0]=false; 剩余区代码; }
P1(){ flag[0]=true; // 上锁 while(flag[1]);// 检查 临界区代码; flag[1]=false; 剩余区代码; }
(3)算法特点
若上述的“上锁”操作由于进程异步发生了进程切换，导致所有的标志flag均为true，此时P0和P1都无法访问临界区
解决了“忙则等待”但是又违背了“空闲让进”和“有限等待”
4.Peterson算法
(1)算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让进，最后谁都无法进入临界区。Gary L.Peterson想到了一种方法，如果双方都想争着进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。
(2)算法实现
bool flag[2];int turn=0;
P0(){ flag[0]= true; turn=1; while(flag[1] && turn==1); 临界区代码; flag[0]=false; 剩余区代码; }
P1(){ flag[1]= true; turn=0; while(flag[0] && turn==0); 临界区代码; flag[1]=false; 剩余区代码; }
(3)算法特点
Peterson算法用软件解决了进程互斥的问题，遵循了“空闲让进”、“忙则等待”和“有限等待”三个原则，但仍然未遵循“让权等待”的原则
进程互斥硬件方法
1.关中断
在进入锁测试之前关闭中断，直到完成锁测试之后才能打开中断。
锁测试：每个要进入临界区的进程必须先对锁进行测试，锁未开时必须等待，直至锁被打开。反之，当锁是打开的时候，应立即把其锁上，以阻止其他进程进入临界区。
关中断的缺点
①滥用关中断权利可能导致严重后果
②关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力
③关中断方法也不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其他处理器上执行相同的临界段代码
④只能运行在内核态的内核程序，不能适用于用户程序，因为用户程序没办法使用中断指令
2.利用Test-and-Set指令实现互斥
是一种借助一条硬件指令——“测试并建立”指令TS(Test-and-Set)以实现互斥的方法
boolean TS(boolean *lock) { boolean old; old = *lock; *lock = TRUE; return old; }
while (TS(&lock)); 临界区代码段 lock = false 剩余区代码段
3.利用Swap指令实现进程互斥 (又称Exchange指令或XCHG指令)
逻辑上看Swap和TS指令并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)
bool old = true; while(old == true) swap(&lock,&old); 临界区代码段 lock = false 剩余代码段
特点
该指令可以看作为一个函数过程，其执行过程是不可分割的，即是一条原语
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TS指令，从而导致“忙等”
3、锁
4、信号量
信号量其实就是一个变量(可以是一个整数，也可以是一个更加复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如系统中只有一台打印机，就可以设置一个初值为1的信号量
1.整型信号量
整型量S用于表示资源数目，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问，二者被分别称作P、V操作
wait(S){// wait原语，相当于进入区 while(S<=0);//进入“忙等”状态 S--; // 占用一个资源，此时S少一 }
signal(S){ // signal原语，相当于退出区 S++; // 使用完资源后，释放资源 }
wait原语和双标志先检查法一样是“检查”，“上锁”。但是wait中的两个操作是一气呵成的。但只要是信号量S<=0，就会不断的测试但是同样不满足“让权等待”原则，而是处于“忙等状态”
2.记录型信号量
typedef struct { int value; //剩余资源数 struct process *L; // 等待队列，记录被阻塞的进程 } semaphore;
/*某进程需要使用资源时，通过wait原语申请*/ void wait (semaphore S) { S.value--; if (S.value <0 ) { block (S.L); } } //block()函数：如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列(即阻塞队列)中
/*进程使用完资源后，通过signal原语释放*/ void signal (semaphore S) { S. value++; if (S.value <= 0) { wakeup(S.L); } } //wakeup()函数：释放资源后，若还有别的进程在等待这种资源，则有S.value <=0，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
S.value表示某种资源数，S.L指向该资源的队列 P操作中，一定是先S.value--，之后可能需要执行block原语 V操作中，一定是先S.value++，之后可能需要执行wakeup原语 可以用记录型信号量实现系统资源的“申请”和“释放” 可以用记录型信号量实现进程互斥、进程同步 记录型信号量遵循了“让权等待”的原则
注：若考试中出现P(S)和V(S)的操作，除非特别说明，否则默认S位记录型信号量
3.信号量的应用
1.利用信号量实现进程互斥
(1)分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应放在临界区)
(2)设置互斥信号量mutex，初值为1
(3)在临界区之前执行P(mutex)
(4)在临界区之后执行V(mutex)
semaphore mutex = 1; // 初始化信号量 P1(){ ... P(mutex); // 使用临界资源前需要加锁 临界区代码段 V(mutex); // 使用临界资源后需要解锁 ... }
P2(){ ... P(mutex); 临界区代码段 V(mutex); ... }
注意
对不同临界资源需要设置不同的互斥信号量(变量)
P、V操作必须成对出现
缺少P(mutex)就不能保证临界资源的互斥访问
缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒
2.用信号量实现进程同步
进程同步：要让各进程按要求有序的推进。让本来异步并发进程相互配合，有序推进
(1)分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
(2)设置同步信号量S，初值为0
(3)在“前操作”之后执行V(S)
(4)在“后操作”之前执行P(S)
semaphore S = 0; P1(){ 代码1; 代码2; V(S); 代码3; }
// 保证代码4在代码2之后执行 P2(){ P(S); 代码4; 代码5; 代码6; }
注意
P操作出现在后操作之前 V操作出现在前操作之后
3.利用信号量实现前趋关系
(1)分析问题，画出前趋图，把每个前趋关系都看做成一个同步问题
(2)每一对前趋关系都是一个进程同步问题
(3)在每个“前操作”之后执行V(S)
(4)在每个“后操作”之前执行P(S)
P1(){ ... S1; V(a); V(b); ... }
P2(){ ... P(a); S2; V(c); V(d); ... }
P3(){ ... P(b); S3; V(g); ... }
P4(){ ... P(c); S4; V(e); ... }
P5(){ ... P(d); S5; V(f); ... }
P6(){ ... P(e); P(f); P(g); S6; ... }
5、条件变量
1.管程的定义
管程可以理解为对PV操作的封装
一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能够同步进程和改变管程中的数据
管程的组成部分
①管程的名称
②局部于管程的共享数据结构说明
③对该数据结构进行操作的一组过程
④对局部于管程的共享数据设置初始值的语句
12. 管程是由哪几部分组成的？
管程的主要特征
①模块化，即管程是一个基本程序的单位
②抽象数据类型，指管程中不仅有数据，而且有对数据的操作
③信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见
概要
1.各外部进程/线程只能通过管程提供的特定"入口"才能访问共享数据
2.每次仅允许一个进程在管程内执行某个内部过程
管程与进程的不同
①虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构，如消息队列
②二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关操作，而管程的设置则是解决共享资源的互斥使用问题
③设置进程的目的是在于实现系统的并发性，而管程的设置主要是解决共享资源的互斥使用问题
④进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序被调用一样，因而管程为被动工作方式，进程则为主动工作方式
⑤进程之间能并发执行，而管程则不能与其调用者并发
⑥进程具有动态性，而管程则是操作系统中的一个资源管理模块，供进程调用
2.条件变量
可在管程中设置条件变量及等待/唤醒操作以解决同步问题
经典同步问题
生产者-消费者问题
1.问题描述：系统中由一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品并使用（这里的产品理解为某种数据），生产者和消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区未满的时候，生产者才能把产品放入缓冲区，否则必须等待。
2.解题思路
①关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系
②整理思路。根据各进程的操作流程确定P，V操作的大致顺序
③设置信号量。设置需要的信号量，并根据题目条件设置信号量初值。(互斥信号量初值一般为1，同步信号量的多少看对应初始资源值的多少)
3.解题过程
①关系分析
进程：存在生产者进程和消费者进程
互斥关系：生产者生产产品和消费者消耗产品对缓冲区的访问要实现互斥
同步关系
缓冲区满，生产者进程要等待消费者进程取走产品
缓冲区空，消费者进程要等待生产者进程放入产品
②整理思路
生产者每次要消耗(P操作)一个空闲缓冲区，并放入(V操作)一个产品(非空闲缓冲区)
消费者每次要取走(P操作)一个产品(非空闲缓冲区)，并释放(V操作)一个空闲缓冲区
往缓冲区放入/取走一个产品需要进行一次互斥操作(一对P，V操作)
③设置信号量
semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问 semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量 semaphore full = 0; // 同步信号量，表示产品(非空闲缓冲区)的数量
④代码实现
producer(){ while(1){ 生产一个产品; P(empty); // 消耗一个空闲缓冲区 P(mutex); // 实现进程互斥 把产品放入缓冲区; V(mutex); // 实现进程互斥 V(full); // 添加一个产品(非空闲缓冲区) } }
consumer(){ while(1){ P(full); // 消耗一个产品(非空闲缓冲区) P(mutex); // 实现进程互斥 从缓冲区取出产品; V(mutex); // 实现进程互斥 V(empty); // 增加一个空闲缓冲区 使用一个产品; } }
4.注意
若改变同步信号量P(empty)/P(full)与互斥信号量P(mutex)的顺序，则会发生死锁
可以改变同步信号量V和互斥信号量V的顺序
多生产者-多消费者问题
1.问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专门向盘子中放苹果，妈妈专门向盘子中放橘子，儿子专门等着吃盘子中的橘子，女儿专门等着吃盘子里的苹果。只有盘子空时，爸爸或妈妈才能向盘子中放一个水果。仅当盘子里有自己需要的水果时，儿子或女儿才可以从盘子中取出水果
2.解题过程
①关系分析
进程：父亲进程和母亲进程，儿子进程和女儿进程
互斥关系：所有进程对盘子的的访问都需要实现互斥
同步关系
父亲将苹果放入盘子后，女儿才能取苹果
母亲将橘子放入盘子后，儿子才能取橘子
只有盘子为空时，父亲或母亲才能放入水果
②整理思路
③设置信号量
semaphore mutex = 1; // 互斥信号量，实现对盘子的互斥访问 semaphore plate = 1; // 同步信号量，表示盘子资源的数量 semaphore orange = 0;// 同步信号量，表示橘子资源的数量 semaphore apple = 0; // 同步信号量，表示苹果资源的数量
④代码实现
dad(){ while(1){ 准备苹果; P(plate); P(mutex); 放入苹果; V(mutex); V(apple); } }
mom(){ while(1){ 准备橘子; P(plate); P(mutex); 放入橘子; V(mutex); V(orange); } }
daughter(){ while(1){ P(apple); P(mutex); 取出苹果; V(mutex); V(plate); 吃掉苹果; } }
son(){ while(1){ P(orange); P(mutex); 取走橘子; V(mutex); V(plate); 吃掉橘子; } }
3.注意
在多生产者-消费者问题时，如果缓冲区大小为1的话，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的问题。
在考试中若来不及分析，可以加上互斥信号量，但是同步的P操作一定要在互斥的P操作之前，否则可能引起死锁
吸烟者问题
1.问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个用友烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下哪种材料的抽烟者会卷一根烟并抽掉它，并给供应者进程一个信号完成了，供应者就会放另外两种材料在桌上，这个过程一直重复
2.解题过程
①关系分析
进程：供应者进程和三个抽烟者进程
互斥关系：桌子上同一时间只能放两种材料的组合
同步关系
桌子上有组合一→第一个抽烟者取走东西
桌子上有组合二→第二个抽烟者取走东西
桌子上有组合三→第三个抽烟者取走东西
发出完成信号→供应者降将下一个组合放在桌子上
②整理思路
③设置信号量
semaphore offer1 = 0; // 桌上的组合一的数量 semaphore offer2 = 0; // 桌上的组合二的数量 semaphore offer3 = 0; // 桌上的组合三的数量 semaphore finish = 0; // 抽烟是否完成 int i = 0; // 用于实现抽烟者的抽烟顺序
④代码实现
provider(){ while(1){ if(i==0) { 将组合一放桌上; V(offer1); }else if(i==1) { V(offer2); }else if(i==2) { V(offer3); } i = (i+1)%3; // 实现轮流 P(finish); } }
smoker1(){ while(1){ P(offer1); 拿走抽掉; V(finish); } }
smoker2(){ while(1){ P(offer2); 拿走抽掉; V(finish); } }
smoker3(){ while(1){ P(offer3); 拿走抽掉; V(finish); } }
3.注意
吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路
如果要实现“轮流让多个吸烟者吸烟”必然需要一个整型变量i实现随机的过程
若一个生产者生产多种产品(或者说会引发多种前趋事件)，那么各个V操作应该放在各自对应的事件发生之后
读者-写者问题
1.问题描述：在读者和写者两组并发进程，共享一个文件，当两个或两个以上的进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程同时访问共享数据时则可能导致数据不一致的错误。
2.解题过程
①关系分析
进程：写进程和读进程
互斥关系：写进程-写进程，写进程-读进程
②整理思路：
因为读进程必须与其他任何进程进行互斥访问，所以为了实现读进程与写进程的互斥访问，而不阻断读进程之间的非互斥访问，可以让第一个访问文件的读进程进行“加锁”，让最后一个访问完文件的读进程进行“解锁”，设置一个count变量来记录当前有几个读进程在访问文件
③设置信号量
semaphore rw = 1; // 用于实现对文件的互斥访问。 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; // 用于保证对count变量的互斥访问
④代码实现
writer(){ while(1){ P(rw); // 写之前加锁 写文件; V(rw); // 写之后解锁 } }
reader(){ while(1){ P(mutex); // coun互斥加锁 if(count==0) P(rw); // 第一个读进程进行加锁 count++; V(mutex); // count解锁 读文件... P(mutex); // count互斥锁 count--; if(count==0) V(rw); // 最后一个读进程负责解锁 V(mutex); // count互斥解锁 } }
3.注意
潜在的问题：只要有读进程还在写，写进程就会一直阻塞等待，可能“饿死”。因此这种算法中，读进程是优先的
核心思想：设置计数器count用于记录正在访问共享文件的读进程数，如果实现“一气呵成”就得想到互斥信号量
4.改进为“先来先服务”
①设置信号量
semphore rw = 1; // 用于实现读文件的互斥访问 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; // 用于保证对count变量的互斥访问 semaphore w = 1; // 用于实现“先来先服务”
②代码实现
writer(){ while(1){ P(w); P(rw); 写文件; V(rw); V(w); } }
reader(){ while(1){ P(w); P(mutex); if(count==0) P(rw); count++; V(mutex); V(w); 读文件... P(mutex); count--; if(count==0) V(rw); V(mutex); } }
哲学家进餐问题
1.问题描述：一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，哲学家饥饿时会试图拿起左、右两根筷子(依次)，如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。
2.解题过程
①关系分析
进程：五个哲学家进餐
互斥关系：左右哲学家对其中间筷子的访问是互斥关系
②整理思路：这个问题中只有互斥关系，但每个哲学家需要两个临界资源才能开始吃饭。如何避免临界资源分配不当的死锁问题，是该问题的精髓
③信号量设置
semaphore chopstick[5]={1,1,1,1,1} // 每根筷子均为一个互斥信号量
④代码实现
1)要求至多允许四个哲学家同时进餐。这样至少有一个哲学家是可以拿到左右筷子的 semaphore r = 4; 可进餐互斥资源
Pi(){ while(1){ P(r); // 可进餐互斥资源 P(chopstick[i]); // 拿左 P(chopstick[(i+1)%5]) // 拿右 吃饭.. V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]) // 放右 V(r); 思考.. } }
2)要求奇数号的哲学家先拿左边的筷子，而偶数号的哲学家先拿右边的筷子。避免了存在哲学家拿到一根筷子却被阻塞
Pi(){ while(1){ if(i%2 == 0){ // 偶数先右再左 P(chopstick[(i+1)%5]) // 拿右 P(chopstick[i]); // 拿左 吃饭.. V(chopstick[(i+1)%5]) // 放右 V(chopstick[i]); // 放左 }else{ P(chopstick[i]); // 拿左 P(chopstick[(i+1)%5]) // 拿右 吃饭.. V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]) // 放右 } 思考.. } }
3)仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子 semaphore mutex = 1; //互斥的取筷子
Pi(){ while(1){ // 奇数先左再右 P(mutex); // 取筷子互斥资源 P(chopstick[i]); // 拿左 P(chopstick[(i+1)%5]) // 拿右 V(mutex); 吃饭.. V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]) // 放右 思考.. } }
3.注意
哲学家进餐问题关键在于解决进程死锁问题
一个进程需要同时持有多个临界资源时考虑哲学家问题
（四）死锁
1、死锁的基本概念
1.资源问题
1.可重用性资源和消耗性资源
1)可重用性资源
(1)每一个可重用性资源是中的单元只能分配给一个进程使用，不允许多个进程共享
(2)进程在使用可重用性资源时，须按照下序
①请求资源。如果请求资源失败，进程将会被阻塞或循环等待
②使用资源
③释放资源
8.进程在使用可重用性资源时，需要遵循何种顺序进行？
2)可消耗性资源
①每一类可消耗性资源的单元数目在进程有运行期间是可以不断变化的，有时它可以有许多，有时可能为0
②进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区，以增加该资源类的单位数目
③进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中
2.可抢占型资源和不可抢占性资源
1)可抢占性资源
指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。CPU和主存均属于可抢占性资源。对于这类资源是不会引起死锁的
2)不可抢占性资源
指系统一旦把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。磁带机、打印机都属于不可抢占性资源
2.计算机系统中的死锁
1.竞争不可抢占性资源引起死锁
通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。
2.竞争可消耗性资源引起死锁
3.进程推进顺序不当引起死锁
除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。
3.死锁的定义、必要条件和处理方法
1.死锁的定义
如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件,那么该组进程是死锁的(Deadlock)
2.产生死锁的必要条件
(1)互斥条件。进程对所分配到的资源进行排它性使用
(2)请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被占有，此时该进程被阻塞，但对自己的资源保持不释放
(3)不可抢占条件。进程已获得的资源在未使用完前不能被抢占，只能在进程使用完时由自己释放
(4)循环等待条件。发生死锁必然存在一个进程—资源的循环链，即P0等P1所占资源，P1等P2所占资源...
但循环等待不一定产生死锁
3.处理死锁的方法
(1)预防死锁：通过破坏产生死锁的必要条件。预防死锁是最容易实现的方法
(2)避免死锁：在资源的动态分配过程中运用某种方法防止系统进入“不安全状态”。避免死锁是资源使用率最高的方法
(3)检测死锁：无须事先采取任何限制性措施，在运行过程中发生死锁时通过即使检测出死锁的发生然后采取适当的措施，把进程从死锁中解脱出来。
(4)解除死锁：当检测到系统中已经发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用方法是撤销一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行
4.死锁、饥饿和死循环的区别
死锁
死锁一定是循环等待对方手里的资源导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态
饥饿
可能只有一个进程发生饥饿，发生饥饿的进程既可能是阻塞态(如长期得不到I/O设备)，也可能是就绪态(长期得不到处理机)
死循环
可能只有一个进程发生死循环。死循环的进程可以在处理机上运行，只不过无法像期待的那样顺利推进。死锁和饥饿的问题是由于操作系统分配资源的策略不合理导致的，而死循环是由用户程序的代码逻辑而导致的
2、死锁预防
0.破坏“互斥”条件
采用SPOOling技术将互斥资源改造成共享资源
不常用
1.破坏“请求和保持”条件
当一个进程在请求资源时，它不能持有不可抢占资源
1.第一种协议 (静态分配方法)
协议规定，在所有进程开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。从而破坏了“请求”条件。只要有一种资源不满足进程的要求，即使其他所需的各资源都空闲也不分配给该进程，而让进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件
优点：简单易行且安全
缺点
资源被严重浪费，严重地恶化了资源的利用率
使进程经常会发生饥饿现象
2.第二种协议
协议允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中可以逐步释放已分配给自己的、且已用毕的资源，然后再请求新的资源
优点：提高了设备的利用率，还可以减少进程发生饥饿的几率
2.破坏“不可抢占”条件
协议规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请
缺点
实现起来比较复杂，且需付出很大的代价
延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量
3.破坏“循环等待”条件
顺序资源分配法：该方法规定每个进程必须按序号递增的顺序请求资源。
优点：资源利用率和系统吞吐量都较前二者有所改善
缺点
首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加
其次，尽管在为资源的类型分配序号事，已经考虑到了大多数作业在实际使用这些资源时的顺序，但也经常会发生作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费
第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而按照这种规定次序申请资源的方法必然会限制用户简单、自主的编程
3、死锁避免
1.系统安全状态
1.安全状态：所谓安全状态，是指系统能按照某种进程推进顺序为每个进程分配其所需资源，直至每个进程对资源的最大需求，使每个进程都可顺利地完成。此时这个顺序称作安全序列
2.系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁
3.安全性算法步骤
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收
不断重复上述过程，看最终是否能让所有进程都加入安全序列
2.利用银行家算法避免死锁
银行家算法步骤
①检查此次申请是否超过了之前声明的最大需求数
②检查此时系统剩余的可用资源是否还能满足这次请求
③试探着分配，更改各个数据结构
④用安全性算法检查此次分配是否会导致系统进入不安全状态
4、死锁的检测和解除
1.死锁的检测
对死锁进行检测，在系统中必须
①提供一种数据结构 保存有关资源的请求和分配信息
资源分配图
两种结点
进程结点：对应一个进程
资源结点：对应一类资源，一类资源可能有多个
两种边
进程结点→资源节点：表示进程想申请几个资源(一条边代表一个)
资源节点→进程结点：表示已经为进程分配了几个资源(一条边代表一个)
②提供一种算法 它利用这些信息来检测系统是否已进入死锁状态
①在资源分配图中，找出既不阻塞又不是孤点的进程结点P(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源的数量)
②消去该进程结点P的所有请求边和分配边，使之成为孤立的结点
③进程结点P所释放的资源，可以唤醒因等待着这些资源而阻塞的其他进程结点，原来的阻塞进程可能变为非阻塞进程，按照①中的方法找到此类结点并按照②中的方法进行一系列简化过后，资源分配图消去了所有的边，则称该图是可完全简化的
概要
依次消除与不阻塞进程相连的边，直到无边可消
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁
2.死锁的解除
方法
(1)资源剥夺法。挂起某些死锁进程，并抢占足够数量的资源分配给死锁进程以解除死锁状态。但是应防止被挂起的进程长时间得不到资源饥饿
(2)终止(或撤销)进程。终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。这种方法的优点是实现简单，但所付出的代价可能会很大，因为有些进程可能已经运行了很长时间，接近结束了，一旦被终止可谓功亏一篑，还得重新再来
(3)进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点
对象
进程的优先级
已执行多长时间
还需要多久完成
进程已经使用了多少资源
进程是交互式的还是批处理式的