c3第三章 进程管理

1、1第三章 进程管理3.1 进程(PROCESS)概念3.2 进程控制3.3 线程(THREAD)3.4 进程互斥和同步3.5 进程间通信(IPC, INTER-PROCESS COMMUNICATION)3.6 死锁问题(DEADLOCK)3.7 进程其他方面的举例 为了描述程序在并发执行时对系统资源的共享，需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制、进程间同步和互斥、进程的通信和死锁等问题。23.1 进程(PROCESS)概念3.1.1 程序的顺序执行和并发执行3.1.2 进程的定义和描述3.1.3 进程的状态转换返回33.1.1 程序的顺序执行

2、和并发执行(P37)程序的执行有两种方式：顺序执行和并发执行。n顺序执行是单道程序系统的执行方式；n并发执行是指多个程序在同一时间段内执行，多个程序交替得到处理机的执行。4顺序执行的特征n顺序性：按照程序结构所指定的次序（可能有分支或循环）执行；n封闭性：独占计算机的全部资源，计算机的状态只由该程序的控制逻辑所决定；n可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。同一个程序反复执行，其结果应该一样。5并发执行的特征n间断(异步)性：“走走停停”，一个程序可能走到中途停下来，由其他程序执行；n失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被

3、另一个程序修改，失去原有的不变特征。n失去可再现性：失去封闭性 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。6并发执行的条件：达到封闭性和可再现性并发执行的条件：达到封闭性和可再现性将程序中任一语句将程序中任一语句 Si Si 划分为两个变量的集划分为两个变量的集合（读集和写集合（读集和写集 R(Si)R(Si)和和W(SiW(Si) )，分别是要进，分别是要进行读和写操作的变量集合）行读和写操作的变量集合）条件：任意两个语句条件：任意两个语句S1,S2S1,S2，若有：，若有：nR(i)R(i)W(j)=W(j)=; ;nW(i)W(i)R(j)=R(j)=;

4、;nW(i)W(i)W(j)=W(j)=; ; 则这两条语句可并发执行。则这两条语句可并发执行。并发执行失去封闭性的原因是共享资源的影响，去掉这种影响并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。就行了。19661966年，由年，由BernsteinBernstein给出并发执行的条件。（在这里给出并发执行的条件。（在这里没有考虑语句执行速度的影响。）没有考虑语句执行速度的影响。）前两条保证一个程序的两次读之间数据不变化；最后一条前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。保证写的结果不丢掉。7程序的并发执行所带来的影响并发执行的优点并发执行的优点:n

5、提供资源的利用率；提供资源的利用率；n提供系统的吞吐率。提供系统的吞吐率。并发执行的缺点并发执行的缺点:n加剧系统资源竞争；加剧系统资源竞争；n管理开销增加。管理开销增加。83.1.2 进程的定义和描述进程：一个具有独立功能的程序对某个数据集在处理机上的一次执行过程和分配资源的基本单位。为解决并发环境下的问题，操作系统引入了进程概念9进程的特征动态性：进程是（程序）动态的执行过程；独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性：进程可以并发执行；异步性：进程之间的执行速度是不确定的；进程间可以相互作用。10进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程

6、是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序的永久的：进程是一个状态变化的过程，动态地被创建，执行后消亡。程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程具有并发特征（独立性和异步性），而程序没有。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。11作业与进程的区别作业是用户向计算机提交任务的实体，被提交后进入外存的作业等待队列。而进程是完成用户任务的执行实体，被创建后，总有相应部分常驻内存；一个作业至少由一个进程来执行完成，反之不然；作业

7、的概念主要用于批处理操作系统；而进程的概念几乎用于所有的多道操作系统中。12进程的组成程序：描述进程要完成的功能，规定指令的执行顺序。数据：程序执行时需要的数据，操作对象。进程控制块（PCB）：存储有关进程的各种信息，操作系统根据它来控制和管理进程。13进程控制块 (PCB, process control block)每个进程在OS中的登记表项（可能有总数目限制），OS据此对进程进行控制和管理；处于核心段（管态或核心态），通常不能由应用程序自身的代码来直接访问，而要通过系统调用等方式访问。进程控制块是由OS维护的用来记录进程相关信息的一块内存。14进程控制块的内容进程描述信息：n进程标识符(

8、process ID)，唯一，通常是一个整数；n进程名，通常基于可执行文件名（不唯一）；n用户标识符(user ID)；进程家族关系进程控制信息：n当前状态；n优先级(priority)；n代码执行入口地址；n程序的外存地址；n运行统计信息（执行时间、页面调度）；n进程间同步和通信信息；阻塞原因资源管理信息：虚拟地址空间的使用状况、打开文件列表CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）15进程上下文 一个进程的执行是在该进程的上下文中执行的，当系统调度新进程占用处理机时，新老进程的上下文将进行切换。进程上下文是对进程执行活动全过程的静态描述。进程上下文由进

9、程的用户地址空间内容（正文段、数据集等）、硬件寄存器内容及与该进程相关的核心数据结构组成。16进程空间任一进程都有自己的地址空间，称为进程空间，由用户空间和系统空间组成。用户程序在用户空间执行，只能执行普通指令，称处于用户态；操作系统内核在系统空间执行，可执行所有指令，称处于系统态（核心态、管理态）。计算机系统通过设置程序状态寄存器等设置不同的状态。173.1.3 进程的状态转换在进程的生命期内，一个进程至少具有三种基本状态：执行状态、等待状态、就绪状态。n处于执行状态(Running)的进程正在处理机上执行，在单CPU系统中任意时刻处于执行状态的进程只能有一个；n处于就绪状态(Ready)的

10、进程已获得除处理机外的所需资源，等待分配处理机资源，只要分配CPU就可执行；n等待状态(Blocked)：处于执行状态的进程因为等待某个I/O设备或是等待某个事件的发生而进入等待状态。18进程状态转换就绪等待执行因为等待某个事件的发生而睡眠 时间片到（分时系统）调度因为等待的事件已经发生而唤醒进程的状态转换193.2 进程控制3.2.1 进程控制的功能3.2.2 进程的创建、退出、 阻塞和唤醒返回203.2.1 进程控制的功能进程控制的功能进程控制：系统使用一些具有特殊功能的程序段进程控制：系统使用一些具有特殊功能的程序段来创建、撤销进程以及完成进程各状态的转换，来创建、撤销进程以及完成进程各

11、状态的转换，从而达到多进程高效率并发执行和协调、实现资从而达到多进程高效率并发执行和协调、实现资源共享的目的，通常使用原语实现。源共享的目的，通常使用原语实现。原语原语(primitive)(primitive)：一类是机器指令级的，其特：一类是机器指令级的，其特点是执行期间不允许中断，正如在物理学的原子点是执行期间不允许中断，正如在物理学的原子一样，在操作系统中，是一个不可分割的执行单一样，在操作系统中，是一个不可分割的执行单位；另一类是功能级的，其特点是作为原语的程位；另一类是功能级的，其特点是作为原语的程序段不允许并发执行。这两类原语都在系统态下序段不允许并发执行。这两类原语都在系统态下

12、运行，并且都是为了完成某个系统管理所需要的运行，并且都是为了完成某个系统管理所需要的功能和被高层软件所调用。功能和被高层软件所调用。213.2.2 进程的控制1.进程创建（创建原语）进程创建的方式： 由系统程序模块统一创建； 由父进程创建，例如在层次结构的系统中，父进程创建子进程以完成并行工作。入口查PCB链表有空PCB?取空表PCB（i）将有关参数填入PCB（i）相应项PCB（i）入就绪队列PCB（i）入进程家族或进程链返回创建失败222. 进程撤销入口返回查进程链表或进程家族有此PCB吗？该PCB有子进程吗？释放该进程所占有的资源释放该PCB结构本身出错处理进程撤销的时机：该进程已经完成所

13、要求的功能而正常终止；由于某种错误导致非正常终止；祖先进程要求撤销某个子进程；233.进程的阻塞（阻塞原语）入口保存当前进程的CPU现场置该进程的状态被阻塞进程入等待队列转进程调度阻塞原语在一个处于执行状态的进程期待某一事件（例如键盘输入数据、写盘、等待其它进程发来的数据或是申请打印机等）的发生，但发生条件尚不具备时，被该进程自己调用来阻塞自己。244.进程的唤醒（唤醒原语）入口从等待队列中摘下被唤醒进程将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列转进程调度或返回当等待队列中的进程所等待的事情发生时，等待该事件的所有进程都将被唤醒。思考一下：为什么一个处于阻塞状态的进程不可能自己唤醒自己？

14、唤醒一个进程的两种方法：由系统进程唤醒；由事件发生进程唤醒。253.3 线程(THREAD) P743.3.1 线程的引入3.3.2 进程和线程的比较3.3.3 线程举例引入线程的目的是提高系统的执行效率，减少处理机的空转时间和调度切换时间，以及便于管理。263.3.1 线程的引入关于线程的理解 线程通常被定义为一个进程中代码的不同执行路线。也就是说，一个进程中，可以有多个不同的代码路线在同时执行。例如，常见的字处理程序中，主线程处理用户输入，而其他并行运行的线程在必要时可在后台保存用户的文档。我们也可以说线程是“轻量级进程”。在 Linux 中，每个进程由五个基本的部分组成：代码、数据、栈、

15、文件I/O 和信号表。因此，系统对进程的处理要花费更多的开销，尤其在进行进程调度和任务切换时。从这个意义上，我们可以将一般的进程理解为重量级进程。在重量级进程之间，如果需要共享信息，一般只能采用管道或者共享内存的方式实现。如果重量级进程通过 fork() 派生了子进程，则父子进程之间只有代码是共享的。 而我们这里提到的线程，则通过共享一些基本部分而减轻了部分系统开支。通过共享这些基本组成部分，可以大大提高任务切换效率。27线程的概念一个进程内的基本调度单位成为线程或称为轻权进程，这个调度单位既可以由操作系统内核控制的，也可以由用户程序控制的。28未引入线程前的进程：进程是资源分配单位（存储器、

16、文件）和CPU调度（分派）单位。又称为任务(task)“。引入线程之后：线程作为CPU调度单位，而进程只作为其他资源分配单位。n线程只拥有必不可少的资源，如：线程状态、寄存器上下文和栈n同样具有就绪、阻塞和执行三种基本状态线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。n线程的创建时间比进程短；n线程的终止时间比进程短；n同进程内的线程切换时间比进程短；n由于同进程内的线程间共享内存和文件资源，可直接进行不通过内核的通信。29one processone threadmultiple processesone thread pe

17、r processone processmultiple threadsmultiple processesmultiple threads per process进程与线程的关系3.3.2 进程和线程的比较30地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的线程在其他进程不可见通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性调度：线程上下文切换比进程上下文切换要快得多。3.3.3 线程举例时间用户程序服务器1服务器2RPC请求1RPC请求2结果1结果2用户程序服务器1服务器2RPC请

18、求1RPC请求2结果1结果2323.4 进程互斥和同步(P49)3.4.1 临界资源3.4.2 信号量(semaphore)3.4.3 经典进程同步问题3.4.4 管程(monitor)3.4.5 进程互斥和同步举例333.4.1 临界资源3.4.1.1临界资源3.4.1.2临界区的访问过程3.4.1.3互斥的问题343.4.1.1临界资源由临界资源产生进程间的制约关系-间接制约：由于某些临界资源的存在，导致进程只能互斥地访问这些资源。另一种进程间的制约关系-直接制约：某些进程之间存在协作关系,一个进程等待来自其他进程（合作进程）的信息，比如“同步”关系。如计算进程和打印进程的关系。多道程序环

19、境下进程之间存在资源共享，进程的运行时间受影响。临界资源-硬件或软件（如外设、共享代码段、共享数据结构），多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行有些共享资源可以同时访问，如只读数据，但有些资源必须互斥进行，如对打印机设备的申请。35一个火车售票系统，如N个终端，售票时可能出现如下情况：T1READ(X);IF X=1 THEN X:=X-1;WRITE(X);T2READ(X);IF X=1 THEN X:=X-1;WRITE(X);直到N终端产生售票冲突，出现一张票（同一车次、同一座位）卖给多个旅客的现象。在这里车票就属于临界资源。36多个进程申请打印机，但作为打印

20、机只能为一个进程提供服务，其他的进程只能在打印机等待队列里等待，待打印机空闲时，进入打印机。打印机就是一个临界资源。P1P2P3占用等待等待373.4.2 临界区的表示方法entry sectionexit section critical section remainder section临界区38临界区(critical section)：进程中访问临界资源的一段代码。进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志退出区(exit section)：用于将正在访问临界区标志清除。剩余区(remaind

21、er section)：代码中的其余部分。393.4.1.3 互斥的问题互斥：一组并发进程中的一个或多个程序段，因共享某一共享资源而导致它们必须以一个不允许交叉执行的单位执行，也就是说不允许两个以上的共享资源的并发进程同时进入临界区称为互斥。互斥执行应遵循的准则：n空闲则入：其他进程均不处于临界区；n忙则等待：已有一进程处于其临界区；n有限等待：等待进入临界区的进程不能无限等待；n让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态），不阻止其它进程进入。403.4.2 信号量信号量(semaphore)3.4.2.1 信号量和信号量和P、V原语原语 多道程序并发执行需要一个地位高于

22、进程的管理者来解决多道程序并发执行需要一个地位高于进程的管理者来解决公有资源的使用问题。公有资源的使用问题。OS可从进程管理者的角度来处理互斥的可从进程管理者的角度来处理互斥的问题，信号量就是问题，信号量就是OS提供的管理公有资源的有效手段。提供的管理公有资源的有效手段。413.4.2.1 信号量和信号量和P、V原语原语1965年，由荷兰学者年，由荷兰学者Dijkstra提出（所以提出（所以P、V分别分别是荷兰语的是荷兰语的test(proberen)和和increment(verhogen)），是一种卓有成效的进程），是一种卓有成效的进程同步机制。同步机制。每个信号量每个信号量s除一个整数值

23、除一个整数值s.count（计数）外，还（计数）外，还有一个进程等待队列有一个进程等待队列s.queue，队列中是阻塞在该，队列中是阻塞在该信号量的各个进程的标识信号量的各个进程的标识n信号量只能通过初始化和两个标准的原语来访问信号量只能通过初始化和两个标准的原语来访问n初始化指定一个非负整数值，表示空闲资源总数（又称为初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量资源信号量）若为非负值表示当前的空闲资源数，）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数若为负值其绝对值表示当前等待临界区的进程数二进制信号量二进制信号量(binary semaphor

24、e)：只允许信：只允许信号量取号量取0或或1值值421. P原语原语wait(s)-s.count;/表示申请一个资源表示申请一个资源;if (s.count =0调用进程入等待队列调用进程入等待队列转进程调度转进程调度返回返回sem0是是452. V原语原语signal(s)+s.count;/表示释放一个资源；表示释放一个资源；if (s.count = 0)/表示有进程处于阻塞状态；表示有进程处于阻塞状态； 从等待队列从等待队列s.queue中取出一个进程中取出一个进程P; 进程进程P进入就绪队列进入就绪队列;V原语通常唤醒进程等待队列中的头一个进程原语通常唤醒进程等待队列中的头一个进程

25、46V原语操作的主要动作原语操作的主要动作:1.Sem加加1；2.若若sem加加1后大于零，则进程继续执行；后大于零，则进程继续执行；3.若若sem加加1后小于等于零，则从该信号后小于等于零，则从该信号的等待队列中唤醒以等待进程，然后再的等待队列中唤醒以等待进程，然后再返回原进程继续执行或转进程调度。返回原进程继续执行或转进程调度。V原语操作的功能框图见下页原语操作的功能框图见下页入口sem=sem1Sem buffer;V(mutex);V(full);/退出区P(full);P(mutex);/进入区 one unit - buffer;V(mutex);V(empty);/退出区522.

26、 读者写者问题读者写者问题(the readers-writers problem)问题描述：对共享资源的读写操作，任问题描述：对共享资源的读写操作，任一时刻一时刻“写者写者”最多只允许一个，而最多只允许一个，而“读者读者”则允许多个则允许多个n“读写读写”互斥，互斥，n“写写写写”互斥，互斥，n读读读读允许允许53采用信号量机制：采用信号量机制：nWmutex表示表示允许写允许写，初值是，初值是1。n公共变量公共变量Rcount表示表示“正在读正在读”的进程数，初值是的进程数，初值是0；nRmutex表示对表示对Rcount的互斥操作，初值是的互斥操作，初值是1。P(Rmutex); if

27、(Rcount = 0)P(Wmutex); +Rcount;V(Rmutex); read;P(Rmutex); -Rcount; if (Rcount = 0)V(Wmutex);V(Rmutex);ReaderP(Wmutex); write;V(Wmutex);Writer543、哲学家进餐问题、哲学家进餐问题哲学家进餐问题是典型的同步问题，是由哲学家进餐问题是典型的同步问题，是由Dijkstra提出并解提出并解决的。决的。5个哲学家，他们的生活方式是交替的思考和进餐。哲学家们个哲学家，他们的生活方式是交替的思考和进餐。哲学家们公用一张圆桌，分别坐在周围的公用一张圆桌，分别坐在周围的5

28、张椅子上，圆桌上有张椅子上，圆桌上有5个碗个碗和和5支筷子，平时哲学家进行思考，饥饿时便坐在桌前自己的支筷子，平时哲学家进行思考，饥饿时便坐在桌前自己的位子上试图取用其左、右最靠近他的筷子，只有他拿到两只位子上试图取用其左、右最靠近他的筷子，只有他拿到两只筷子时才能进餐，放下筷子又继续思考。筷子时才能进餐，放下筷子又继续思考。问题：如何保证哲学家们的动作有序进行？问题：如何保证哲学家们的动作有序进行？n不出现有人永远拿不到筷子。不出现有人永远拿不到筷子。55哲学家的状态哲学家的状态Repeat 思考；思考； 取取chopsticki;取取chopstick (i+1) mod 5； /*先取左

29、手的筷子，再取右手的筷子先取左手的筷子，再取右手的筷子 进食；进食； 放放chopstick i;/*先放左手筷子先放左手筷子 放放chopstick (i+1) mod 5； /*再放右手再放右手Until false;56是否出现死锁？是否出现死锁？五个人都拿起一只筷子。五个人都拿起一只筷子。假如五位哲学家同时饥饿而各自拿起左假如五位哲学家同时饥饿而各自拿起左边的筷子时，当他们再试图去拿右边的边的筷子时，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限等待。筷子时，都将因无筷子可拿而无限等待。57如何打破死锁？如何打破死锁？最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在

30、桌子周围仅当一个哲学家左右两边的筷子都可用时，仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（才允许他拿筷子（ ）给所有哲学家编号，奇数号的哲学家必须给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反首先拿左边的筷子，偶数号的哲学家则反之之为了避免死锁，把哲学家分为三种状态，为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。子，否则不拿。58具体算法具体算法Program diningphilosophers;Semaphore chopstick 5 = 1;（5支筷子的状态）支筷子的状态）S

31、emaphore seat = 4;（桌上最多允许四个人）（桌上最多允许四个人）int i;Void philospher (int i) while (true) thinking(); P( seat ); P(chopsticki); P(chopstick(i+1) mod 5) eating(); V(chopsticki); V(chopstick(i+1) mod 5) V(seat); 594 理发师问题理发师问题一个理发店由一个有一个理发店由一个有n（n1）张椅子）张椅子的等候室和一个放有一张理发椅的理发的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发室组

32、成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待；若理发顾客就找一张空椅子坐下等待；若理发师在睡觉，则顾客就唤醒他，设计一个师在睡觉，则顾客就唤醒他，设计一个协调理发师和顾客的程序。协调理发师和顾客的程序。 60问题分析问题分析理发师的状态（理发、睡觉）理发师的状态（理发、睡觉）顾客的状态（等待、理发、离开）顾客的状态（等待、理发、离开）顾客的数量顾客的数量61信号量设计信号量设计cu

33、stomers：顾客数，初始值为：顾客数，初始值为0；baber：理发师，初始值为：理发师，初始值为0，只有，只有0，1两种状态；两种状态；waiting：等待理发的顾客数，初始值为：等待理发的顾客数，初始值为0；mutex，对顾客数的互斥访问信号量，初始值为，对顾客数的互斥访问信号量，初始值为1，只有只有0，1两种状态。两种状态。62理发师进程理发师进程 Process baberbeginLoop: P(Customers);/*等待顾客到来等待顾客到来 ; V(baber)；/通知顾客理发完成通知顾客理发完成 goto loop;end;63顾客进程顾客进程i Process Custo

34、mer(i)begin P(mutex); /测试是否有其他顾客对测试是否有其他顾客对waiting进行访问。进行访问。 if waitingn then /测试等待人数是否大于测试等待人数是否大于n， begin waiting=waiting+1； V(customers); V(mutex); P(baber);/,测试理发师是否空闲测试理发师是否空闲,如空闲就唤醒理发师如空闲就唤醒理发师 P(mutex); waiting=waiting-1; V(mutex); end else begin V(mutex); end;end; 64司机售票员问题司机售票员问题问题描述：问题描述：在

35、公共汽车上，司机和售票员各司其职，在公共汽车上，司机和售票员各司其职，司机负责开车和到站停车；售票员负责司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好门之后，售票和开、关门，当售票员关好门之后，驾驶员才能开车行驶。试用驾驶员才能开车行驶。试用P、V操作实操作实现司机与售票员的同步操作。现司机与售票员的同步操作。65司机与售票员的同步关系司机与售票员的同步关系这里分别用这里分别用S1和和S2表示司机和售票员的私用信号量，其初始值表示司机和售票员的私用信号量，其初始值为为0，正常行驶正常行驶到站停车到站停车开车开车售票售票开车门开车门关车门关车门司机司机乘务员乘务员一个完一个完整的

36、动整的动作顺序。作顺序。66司机和售票员的同步关系描述司机和售票员的同步关系描述S1，S2：Semaphore;S1:=0；S2:=0；Process Driver /司机进程司机进程BeginLoop: ； ； V(S2)； P(S1); Goto Loop;End;Process TicketCollector /售票员进程售票员进程BeginLoop: ； P(S2)； ； ； V(S1); Goto Loop;End;673.4.4 管程管程 由于信号量不是很容易使用，使用不当会造成由于信号量不是很容易使用，使用不当会造成死锁，死锁，Hoare和和Hansen在在1975年提出一种高年

37、提出一种高级同步原语级同步原语-管程，以方便对于共享变量的管程，以方便对于共享变量的访问。访问。管程：管程：monitor，是管理进程间同步的一种机，是管理进程间同步的一种机制，它保证进程互斥地访问共享变量，并且提制，它保证进程互斥地访问共享变量，并且提供了一个方便的阻塞和唤醒进程的机制。一个供了一个方便的阻塞和唤醒进程的机制。一个管程是一个由过程、变量及数据结构等组成的管程是一个由过程、变量及数据结构等组成的一个集合，它们组成了一个特殊的模块和软件一个集合，它们组成了一个特殊的模块和软件包。包。683.5 进程间通信进程间通信(IPC, INTER-PROCESS COMMUNICATION

38、)3.5.1 进程间通信的类型进程间通信的类型3.5.2 信号信号(signal)3.5.3 共享存储区共享存储区(shared memory)3.5.4 管道管道(pipe)3.5.5 消息消息(message)3.5.6 套接字套接字(socket)693.5.1 进程间通信的类型进程间通信的类型低级通信：只能传递状态和整数值（控制信低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和息），包括进程互斥和同步所采用的信号量和管程机制。优点的速度快。缺点是：管程机制。优点的速度快。缺点是：n传送信息量小：效率低，每次通信传递的信息量固传送信息量小：效率低，每次通信传

39、递的信息量固定，若传递较多信息则需要进行多次通信。定，若传递较多信息则需要进行多次通信。n编程复杂：用户直接实现通信的细节，编程复杂，编程复杂：用户直接实现通信的细节，编程复杂，容易出错。容易出错。高级通信：能够传送任意数量的数据，包括三高级通信：能够传送任意数量的数据，包括三类：共享存储区、管道、消息。类：共享存储区、管道、消息。返回返回1. 低级通信和高级通信低级通信和高级通信702. 直接通信和间接通信直接通信和间接通信直接通信：信息直接传递给接收方，如管道。直接通信：信息直接传递给接收方，如管道。n在发送时，指定接收方的地址或标识，也可以指在发送时，指定接收方的地址或标识，也可以指定多

40、个接收方或广播式地址；定多个接收方或广播式地址；n在接收时，允许接收来自任意发送方的消息，并在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址。在读出消息的同时获取发送方的地址。间接通信：借助于收发双方进程之外的共享间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。通常数据结构作为通信中转，如消息队列。通常收方和发方的数目可以是任意的。收方和发方的数目可以是任意的。713. 高级通信的特征高级通信的特征通信链路通信链路(communication link)：n点对点点对点/多点多点/广播广播n单向单向/双向双向n有容量（链路带缓冲区）有容量（链路

41、带缓冲区）/无容量（发送方和接收方需自备缓冲区）无容量（发送方和接收方需自备缓冲区）数据格式：数据格式：n字节流字节流(byte stream)：各次发送之间的分界，在接收时不被保留，：各次发送之间的分界，在接收时不被保留，没有格式；没有格式；n报文报文(datagram/message)：各次发送之间的分界，在接收时被保：各次发送之间的分界，在接收时被保留，通常有格式（如表示类型），定长留，通常有格式（如表示类型），定长/不定长报文，可靠报文不定长报文，可靠报文/不可不可靠报文。靠报文。收发操作的同步方式收发操作的同步方式n发送阻塞（直到被链路容量或接收方所接受）和不阻塞（失败时立即发送阻塞

42、（直到被链路容量或接收方所接受）和不阻塞（失败时立即返回）返回）n接收阻塞（直到有数据可读）和不阻塞（无数据时立即返回）接收阻塞（直到有数据可读）和不阻塞（无数据时立即返回）n由事件驱动收发：在允许发送或有数据可读时，才做发送和接收操作由事件驱动收发：在允许发送或有数据可读时，才做发送和接收操作723.5.2 信号信号(signal)3.5.2.1 UNIX信号信号3.5.2.2 Windows NT信号信号返回返回信号相当于给进程的信号相当于给进程的“软件软件”中断；进程可发送信号，中断；进程可发送信号，指定信号处理例程；它是单向和异步的。指定信号处理例程；它是单向和异步的。733.5.2.

43、1 UNIX信号信号一个进程向另一个进程或进程组（或自己）发送一个进程向另一个进程或进程组（或自己）发送（kill系统调用）：发送者必须具有接收者同样的系统调用）：发送者必须具有接收者同样的有效用户有效用户ID，或者发送者是超级用户身份，或者发送者是超级用户身份某些键盘按键，如：中断字符（通常是某些键盘按键，如：中断字符（通常是Ctrl+C或或Del）、暂停字符（）、暂停字符（如如Ctrl+Z）硬件条件，如：除数为零、浮点运算错、访问非法硬件条件，如：除数为零、浮点运算错、访问非法地址等异常条件地址等异常条件软件条件，如：软件条件，如：Socket中有加急数据到达。中有加急数据到达。1. 信号

44、类型信号类型742. 对信号的处理对信号的处理进程可以设置信号处理例程（进程可以设置信号处理例程（signal系统调用），系统调用），在接收到信号时就被调用，称为在接收到信号时就被调用，称为捕获捕获该信号。信该信号。信号处理例程的参数是接收到信号的编号。号处理例程的参数是接收到信号的编号。进程也可以忽略指定的信号进程也可以忽略指定的信号(SIG_IGN)。n只有只有SIGKILL信号（无条件终止进程）和信号（无条件终止进程）和SIGSTOP（使（使进程暂停）不能被忽略。进程暂停）不能被忽略。n在库函数在库函数system()的实现中，通过的实现中，通过fork和和exec加载新程加载新程序之后

45、，在父进程中对序之后，在父进程中对SIGINT和和SIGQUIT都要忽略，都要忽略，然后然后wait直到子进程终止，才恢复对直到子进程终止，才恢复对SIGINT和和SIGQUIT的原有处理例程。的原有处理例程。进程创建后为信号设立了默认处理例程进程创建后为信号设立了默认处理例程(SIG_DFL)，如：终止并留映象文件如：终止并留映象文件(core)753.5.3 共享存储区共享存储区(shared memory)创建或打开共享存储区创建或打开共享存储区(shmget)：依据用户给出的整数值：依据用户给出的整数值key，创，创建新区或打开现有区，返回一个共享存储区建新区或打开现有区，返回一个共享

46、存储区ID。连接共享存储区连接共享存储区(shmat)：连接共享存储区到本进程的地址空间，：连接共享存储区到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享存储区首地址。父进程可以指定虚拟地址或由系统分配，返回共享存储区首地址。父进程已连接的共享存储区可被已连接的共享存储区可被fork创建的子进程继承。创建的子进程继承。拆除共享存储区连接拆除共享存储区连接(shmdt)：拆除共享存储区与本进程地址空间：拆除共享存储区与本进程地址空间的连接。的连接。共享存储区控制共享存储区控制(shmctl)：对共享存储区进行控制。如：共享存储：对共享存储区进行控制。如：共享存储区的删除需要显式调用区的

47、删除需要显式调用shmctl(shmid, IPC_RMID, 0)；相当于内存，可以任意读写和使用任意数据结构（当然，对相当于内存，可以任意读写和使用任意数据结构（当然，对指针要注意），需要进程互斥和同步的辅助来确保数据一致指针要注意），需要进程互斥和同步的辅助来确保数据一致性性1. UNIX的共享存储区的共享存储区763.5.4 管道管道(pipe)管道是一条在进程间以字节流方式传送的管道是一条在进程间以字节流方式传送的通信通道。它由通信通道。它由OS核心的缓冲区（通常几核心的缓冲区（通常几十十KB）来实现，是单向的；常用于命令）来实现，是单向的；常用于命令行所指定的输入输出重定向和管道命

48、令。行所指定的输入输出重定向和管道命令。在使用管道前要建立相应的管道，然后才在使用管道前要建立相应的管道，然后才可使用。可使用。771. UNIX管道管道通过通过pipe系统调用创建无名管道，得到两个文件描系统调用创建无名管道，得到两个文件描述符，分别用于写和读。述符，分别用于写和读。nint pipe(int fildes2);n文件描述符文件描述符fildes0为读端，为读端，fildes1为写端；为写端；n通过系统调用通过系统调用write和和read进行管道的写进行管道的写和读；和读；n进程间双向通信，通常需要两个管道；进程间双向通信，通常需要两个管道；n只适用于父子进程之间或父进程安

49、排的各个子进程之间；只适用于父子进程之间或父进程安排的各个子进程之间；UNIX中的命名管道，可通过中的命名管道，可通过mknod系统调用建立：系统调用建立：指定指定mode为为S_IFIFOnint mknod(const char *path, mode_t mode, dev_t dev);78 写端写端：fd1Write(fd1,buf,size) 读端读端： fd0read(fd0,buf,size)nint pipe(int fd2);n文件描述符文件描述符fd0为读端，为读端，fd1为写为写端；端；管道工作原理如下：管道工作原理如下：79管道通信实例用C语言编写一个程序，建立一个p

50、ipe，同时父进程生成一个子进程，子进程向pipe中写入一字符串，父进程从pipe中读出该字符串。程序如下：include int x,fd2; char buf30,s30; pipe(fd); /*创建管道*/ while(x=fork()=-1);/*创建子进程失败，反复循环*/ if(x=0) sprintf(buf,”This is an examplen”); write(fd1,buf,30);/*把buf中的字符写入管道*/ exit(0); /*续左面*/ else/*父进程返回*/ wait(0); read(fd0,s,30); /*父进程读管道字符*/ printf(“

51、%s”,s); 803.5.5 消息消息(message)与窗口系统中的与窗口系统中的“消息消息”不同。通常是不同。通常是不定长数据块。消息的发送不需要接收不定长数据块。消息的发送不需要接收方准备好，随时可发送。方准备好，随时可发送。81 UNIX消息消息消息队列消息队列(message queue)(message queue)：每个：每个messagemessage不定长，由类型不定长，由类型(type)(type)和正文和正文(text)(text)组成组成UNIXUNIX消息队列消息队列APIAPI：nmsggetmsgget依据用户给出的整数值依据用户给出的整数值keykey，创建新

52、消息队列或打开现有消息，创建新消息队列或打开现有消息队列，返回一个消息队列队列，返回一个消息队列IDID；nmsgsndmsgsnd发送消息；发送消息；nmsgrcvmsgrcv接收消息，可以指定消息类型；没有消息时，返回接收消息，可以指定消息类型；没有消息时，返回-1-1；nmsgctlmsgctl对消息队列进行控制，如删除消息队列；对消息队列进行控制，如删除消息队列；通过指定多种消息类型，可以在一个消息队列中建立多个虚通过指定多种消息类型，可以在一个消息队列中建立多个虚拟信道拟信道注意：消息队列不随创建它的进程的终止而自动撤销，必须注意：消息队列不随创建它的进程的终止而自动撤销，必须用用m

53、sgctl(msgqidmsgctl(msgqid, IPC_RMID, 0), IPC_RMID, 0)。另外，。另外，msggetmsgget获得消息队获得消息队列列IDID之后，之后，forkfork创建子进程，在子进程中能否继承该消息队创建子进程，在子进程中能否继承该消息队列列IDID而不必再一次而不必再一次msggetmsgget。823.5.6 套接套接字字(socket)双向的，数据格式为字节流（一对一）或报文（多双向的，数据格式为字节流（一对一）或报文（多对一，一对多）；主要用于网络通信；对一，一对多）；主要用于网络通信；支持支持client-server模式和模式和peer-

54、to-peer模式，本模式，本机或网络中的两个或多个进程进行交互。提供机或网络中的两个或多个进程进行交互。提供TCP/IP协议支持协议支持UNIX套接字套接字(基于基于TCP/IP)：send, sendto, recv, recvfrom;在在Windows NT中的规范称为中的规范称为Winsock(与协议与协议独立，或支持多种协议独立，或支持多种协议)：WSASend, WSASendto, WSARecv, WSARecvfrom;833.6 死锁问题(DEADLOCK) P723.6.1 概述3.6.2 死锁的预防3.6.3 死锁的检测3.6.4 解决死锁问题的综合方法843.6.1

55、 概述死锁是指系统中多个进程无限制地等待永远不会发生的条件；1. 死锁发生原因并发进程对互斥资源的共享，并发执行的顺序不当85. Request(B); Request(A); Release(A); Release(B);P2. Request(A); Request(B); Release(B); Release(A);P1死锁举例死锁发生：双方都拥有部分资源，同时在请求对方已占有的资源。如次序：P1 P2 P1 P2862. 死锁发生的必要条件只有4个条件都满足时，才会出现死锁。n互斥：任一时刻只允许一个进程使用资源n请求和保持：进程在请求其余资源时，不主动释放已经占用的资源n非剥夺：进

56、程已经占用的资源，不会被强制剥夺n环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。873. 处理死锁的基本方法方法 资源分配策略 各种可能模式 主要优点 主要缺点 一次请求所有资源 适用于作突发式处理的进程；不必剥夺 资源剥夺 适用于状态可以保存和恢复的资源 预防 Prevention 保守的； 宁可资源闲置 （从机制上使死锁条件不成立） 资源按序申请 可以在编译时（而不必在运行时）就进行检查 效率低；进程初始化时间延长 剥夺次数过多；多次对资源重新起动 不便灵活申请新资源 避免 Avoidance 是 “预防” 和 “检测” 的折衷 （在运行时判断是否可能死锁） 寻找可能的安全的运行顺序 不必进行剥夺 使用条件：必须知道将来的资源需求；进程可能会长时间阻塞 检测 Detection 宽松的；只要允许，就分配资源 定期检查死锁是否已经发生 不延长进程