操作系统高分笔记PV操作

天勤论坛：天勤论坛——专为计算机考研学子打造的专业交流平台期待你的加入！此文档由天勤论坛总结转载请注明出处！天道酬勤，厚德载物！天勤论坛：第二章进程管理····大纲要求一、进程与线程1.进程概念2.进程的状态与转换3.进程控制4.进程组织5.进程通信共享存储系统，消息传递系统，管道通信。6.线程概念与多线程模型二、进程同步1.进程同步的基本概念2.实现临界区互斥的基本方法软件实现方法;硬件实现方法。3.信号量4.管程5.经典同步问题生产者-消费者问题，读者-写者问题，哲学家进餐问题。※注：处理机调度以及死锁将在处理机调度与死锁一章讲解。····本章知识体系框架图天勤论坛：····本章基础要点与核心考点一、核心考点：1、（★★★）进程的定义及特征、进程与程序的异同、进程的状态及引起状态转换的典型原因。2、（★★★★★）临界区的定义及操作原则，进程同步与互斥，用信号量描述进程同步，进程通信。二、基础要点：1、进程的并发执行是指若干进程在执行时间上是重叠的。2、▲进程是一个程序对某个数据集的一次运行活动。3、程序并发执行与顺序执行相比产生了一些新特性：间断性、失去封闭性、不可再现性。4、进程的基本特征是：动态性、并发性、独立性、异步性和结构特征。5、程序的顺序执行通常是在单道程序的工作环境中，具有运行结果可再现的特点。6、▲进程的基本状态有执行、就绪和阻塞。7、进程是动态的概念，而程序是静态的概念。8、▲进程控制块的初始化工作包括初始化标识符信息、初始化处理机状态信息、初始化处理机控制信息。9、▲当进程执行的时间片用完时，进程由执行状态转变为就绪状态。10、进程从结构上讲，包括程序段、数据段和进程控制块（PCB）三部分。11、在操作系统中引入线程概念的主要目的是减少程序并发执行时所需付出的时空开销，提高程序执行的并发程度。12、在进程中，访问临界资源的代码段称为临界区。为保证进程互斥访问临界资源，应在进程的临界区之前设置进入区，在临界区后设置退出区。13、▲访问临界资源应遵循的准则为：空闲让进、忙则等待、有限等待、让权等待。14、信号量的物理意义是当信号量值大于零时表示可用资源的数目：当信号量值小于零时，其绝对值为在该信号量上等待的进程个数。15、用P、V操作管理临界区时，任何一个进程在进入临界区之前应调用P操作，退出临界区时应调用V操作。····知识点扩展与深度总结一、进程同步基本概念1．两种形式的制约关系（课本P38）（1）间接相互制约关系（互斥）：这种制约关系源于多个同种进程需要互斥地共享某种系统资源（比如打印机），互斥是设置在同种进程之间以达到互斥地修改资源数的目的（比如在生产者-消费者问题中，生产者与生产者之间需要互斥地访问缓冲池）。（2）直接相互制约关系（同步）：这种制约主要源于进程间的合作，同步设置在不同进程之间以达到多种进程间的同步（比如在生产者-消费者问题中，只要缓冲池不满，生产者就可以生产，只要缓冲池不空，消费者就可以消费）。注：只要是同类进程即为互斥关系，不同类进程即为同步关系。2．临界资源与临界区（课本P39-40）天勤论坛：【易错点解析】这是两个比较容易混淆的概念，有人可能会理解为临界区就是临界资源所在地址，这样理解显然是错误的。简单点说，临界资源是一种系统资源，需要不同进程互斥访问，而临界区则是每个进程中访问临界资源的一段代码，是属于对应进程的，临界区前后需要设置进入区和退出区以进行检查和恢复。3．同步机制应遵循的规则（课本P41）所有的同步机制都应遵循这四条准则（空闲让进，忙则等待，有限等待，让权等待），后面将在实现临界区互斥基本方法中举例说明。二、实现临界区互斥的基本方法1．软件方法：对临界区互斥访问技术的研究始于20世纪60年代，早期主要从软件方法上进行研究，下面我们介绍这些软件方法。它们有的是正确的，有的是不正确的。之所以介绍这些方法是为了说明用软件方法解决互斥和同步问题的困难和复杂性。例如有两个进程P0和P1，互斥地共享某个资源。P0和P1是循环进程，它们执行一个无限循环程序，每次使用资源一个有限的时间间隔。注：临界区互斥的软件实现方法在历年来各学校的操作系统考题中出现过，通常作为选择题出现，用来考察同步机制的四个准则，统考的两年中在2010年真题第27题以选择题的形式考察过，因此在这里比较详细地介绍一下，帮助大家熟悉和理解四个准则以及同步机制的实现过程。算法1：设置一个公用整形变量turn，用来指示允许进入临界区的进程标识。若turn为0，则允许进程P0进入临界区；否则循环检查该变量，直到turn变为本进程标识；在退出区，修改允许进入进程的标识turn为1。进程P1的算法与此类似。两个进程的程序结构如下：intturn=0；P0:{Do{While(turn!=0);//当turn不为0时循环检查，直到为0进入P0的临界区代码CS0;turn=1;进入P0的其他代码;}While(true)//循环执行这段代码}P1:{Do{While(turn!=1);进入P1的临界区代码CS1;turn=0;进入P1的其他代码;}While(true)}此方法可以保证互斥访问临界资源，但存在的问题是强制两个进程以交替次序进入临界区，很容易造成资源利用不充分。例如，当进程P0退出临界区后将turn置为1，以便允许进程P1进入临界区，但如果进程P1暂时并未要求访问该临界资源，而P0又想再次访问临界资源，则它将无法进入临界区。可见，此算法不能保证实现“空闲让进”准则。算法2：设置标志数组flag[]表示进程是否在临界区中执行，初值均为假。在每个进程访问该临界资源之前，先检查另一个进程是否在临界区中，若不在则修改本进程的临界区标志为真并进入临界区，在退出区修改本进程临界区标志为假。两进程的程序结构如下：enumboolean{false,true};booleanflag[2]={false,false};天勤论坛：{Do{Whileflag[1];//flag[1]为真表示P1在访问临界区，P0等待。flag[0]=true;进程P0的临界区代码CS0;flag[0]=false;进程P0的其他代码;}While(true)}P1:{Do{Whileflag[0];//flag[0]为真表示P0在访问临界区，P1等待。flag[1]=true;进程P1的临界区代码CS1;flag[1]=false;进程P1的其他代码;}While(true)}此算法解决了“空闲让进”的问题，但又出现了新问题。即当两个进程都未进入临界区时，它们各自的访问标志都为false，若此时刚好两个进程同时都想进入临界区，并且都发现对方的标志值为false（当两进程交替执行了检查语句后，都满足flag[]=false的条件），于是两个进程同时进入了各自的临界区，这就违背了临界区的访问规则“忙则等待”。算法3：本算法仍然设置标志数组flag[],但标志用来表示进程是否希望进入临界区，在每个进程访问临界资源之前，先将自己的标志设置为真，表示进程希望进入临界区，然后检查另一个进程的标志。若另一个进程的标志为真，则进程等待；否则进入临界区。两进程的程序结构如下：enumboolean{false,true};booleanflag[2]={false,false};P0:{Do{flag[0]=true;Whileflag[1];//flag[1]为真表示P1希望访问临界区，P0等待。进程P0的临界区代码CS0;flag[0]=false;进程P0的其他代码;}While(true)}P1:{Do{flag[1]=true;Whileflag[0];//flag[0]为真表示P0希望访问临界区，P1等待。进程P1的临界区代码CS1;flag[1]=false;进程P1的其他代码;}While(true)}此算法可以有效地防止两进程同时进入临界区，但存在两个进程都进不了临界区的问题。即当两个进程同时想进入临界区时，它们分别将自己的标志位设置为true，并且同时去检查对方的状态，发现对方也要进入临界区，于是对方互相谦让，结果都无法进入临界区。造成“死等”现象，违背了“有限等待”的准则。算法4：本算法的思想是算法3和算法1的结合。标志数组flag[]表示进程是否希望进入临界区或是否在临界区中执行。此外，还设置了一个turn变量，用于指示允许进入临界区的进程标识。两进程的程序结构如下：天勤论坛：{false,true};booleanflag[2]={false,false};intturn;P0:{Do{flag[0]=true;turn=1;//此时P0未进入临界区，仍然允许P1进入临界区。While(flag[1]&&turn==1);//flag[1]为真表示P1希望访问临界区，turn为1表示P1可以进入临界区，因此P0等待。进程P0的临界区代码CS0;flag[0]=false;//表示P0退出访问临界区。进程P0的其他代码;}While(true)}P1:{Do{flag[1]=true;turn=0;//此时P1未进入临界区，仍然允许P0进入临界区。While(flag[0]&&turn==0);//flag[0]为真表示P0希望访问临界区，turn为0表示P0可以进入临界区，因此P1等待。进程P1的临界区代码CS1;flag[1]=false;//表示P1退出访问临界区。进程P1的其他代码;}While(true)}至此，算法4可以完全正常工作。我们从上面的软件实现方法中可以看出，对于两个进程间的互斥，最主要的问题就是标志的检查和修改不能作为一个整体来执行，因此容易导致无法保证互斥访问的问题。2．硬件方法：注：硬件方法在考题中基本不出现，只需简单了解即可。完全利用软件方法实现进程互斥有很大的局限性，现在已经很少单独采用软件方法。硬件方法的主要思想是用一条指令完成标志的检查和修改两个操作，因而保证了检查操作与修改操作不被打断；或通过中断屏蔽的方式来保证检查和修改作为一个整体执行。硬件方法主要有两种：一种是中断屏蔽，另一种是硬件指令。（在计算机组成原理中会详细讲解中断与指令，操作系统中很少涉及，因此不展开叙述了）三、信号量1．信号量的分类（课本P41）：整型信号量（引入PV操作，存在“忙等”问题）、记录型信号量（引入进程链表）、AND型信号量（引入多种临界资源的“AND分配”）、信号量集（对AND信号量机制的扩充，可以一次分配多种、多个临界资源）2．信号量的应用（课本P42）：实现进程同步与互斥，实现前趋关系。3．注意：信号量的初值不能为负数。信号量的引入与发展课本上讲的比较清楚，从整型信号量发展到记录型、AND型信号量以及之后的信号量集，之前信号量类型存在的问题以及之后信号量类型的引入都有比较详细的介绍，这里就不展开叙述。信号量的应用重点在于进程同步与互斥，这部分将在经典同步问题中详细介绍。四、管程（课本P51）天勤论坛：为了解决大量分散的同步操作导致管理困难和死锁，因此引入管程概念。管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。注：管程在考题基本不涉及，因此不展开叙述，课本上的内容了解即可。五、经典同步问题进程同步问题历来是操作系统考核的重点，基本以三种经典同步问题及其衍生问题为主要考察内容，下面将详细介绍这三种经典同步问题，并在后面的练习中提及一些衍生问题。1、生产者-消费者问题生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投入产品，消费者从中取走产品。这个问题是许多相互合作进程的一种抽象。例如，在输