[大数据]进程管理笔记

目录

1程序的执行方式

1.1程序的顺序执行

1.2程序的并发执行

1.3关于并发执行条件的理论探讨

2 进程的定义和描述

2.1进程process的定义

2.2进程的描述

2.3进程与程序的关系

2.4进程的特征

2.5进程的状态转换

2.6进程的控制***

原语及分类

进程的创建

进程退出

进程阻塞

进程唤醒

3进程间的关系

3.1进程间关系

间接制约关系

直接制约关系

3.2基本概念和原则

3.2互斥算法(基于进程间平等协商的办法)

3.2.1进程互斥的软件方法

3.2.2进程互斥的硬件方法

3.3信号量机制

3.3.1基本概念

3.3.3信号量机制的推广

4经典同步问题

生产者－消费者问题

读者－写者问题

3.4进程间通信(Inter-Process Communication.IPC)

1按通信量的大小

2按通信过程中是否有第三方作为中转

4死锁问题

4.1死锁deadlock的概念

4.2死锁的原因和条件

4.3死锁的预防

4.4死锁的避免

4.5死锁的检测

4.6死锁发生的概率

5 线程

5.1进程开头问题及进程特性

5.2线程的概念

1程序的执行方式

1.1程序的顺序执行

????????指操作系统依次执行各程序，在一个程序的整个执行过程中该程序执行占用所有系统资源，不会中途暂停。其原因在于冯诺依曼经典体系结构的特点(由单一程序计数器控制，顺序执行单一指令流，处理单一数据流)，程序的顺序性基于硬件的顺序性。

????????指一个具有独立功能的程序独占处理机直至得到最终结果的过程。

其特性：

1. 顺序性：程序的执行是按照程序结构所指定的次序进行的，可能的次序有分支、循环或跳转等；
2. 封闭性：程序在执行过程中独占全部资源，计算机的状态完全由该程序的控制逻辑所决定；
3. 可再现性：只要程序的初始条件相同，执行的结果就完全相同。

顺序执行方式易于检测和校正程序中的错误。

1.2程序的并发执行

????????指多个程序在一个处理器上的交替执行，这种交替执行在宏观上表现为同时执行。

????????一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序(或程序段)的执行尚未结束，另一个程序(或程序段)的执行已经开始的执行方式。

????????并发执行之所以引入是基于主存容量增大，出现大容量辅存-磁盘，特别是代替CPU管理设备的通道，使得I/O操作与CPU操作得以并行执行的这一硬件并行处理能力。并发执行引入的目的是为了提高计算机资源的利用率。

其特性(并行执行对程序执行环境的影响)：

1. 间断(异步)性：处理器交替执行多个程序，每个程序都以“走走停停”的方式执行，可能中途停下来，而且程序无法预知每次执行和暂停的时间长度，从而失去原有的时序关系；
2. 失去封闭性：多个程序共享一个计算机系统的多种资源，每个程序的执行都会受到其它程序的控制逻辑的影响，例如一个程序写入存储器的数据可能被另一个程序修改而失去原有的数据不变性；
3. 失去可再现性：由于程序执行环境的封闭性不再成立，程序每次执行的环境可能不同，执行环境在程序的两次执行期间发生变化可能导致执行结果的不同，程序执行结果失去原有的可重复特征。

并发程序执行中出现的程序错误难于检测和校正。

1.3关于并发执行条件的理论探讨

程序执行必须保持封闭性和可再现性，并发执行失去封闭性(失去封闭性可能导致失去可再现性)的原因在于共享资源带来的影响，应消除这种影响。

1966年Bernstein给出了程序并发执行的条件。假设程序P所访问的共享变量的读集和写集分别为R和W，则任两个程序P(i)和P(j)可以并发执行的条件有三条：

R(i)∩W(j)=Ф，W(i)∩R(j)=Ф，W(i)∩W(j)=Ф。

其中：前两个条件保证一个程序在两次读操作之间存储器中的数据不会发生变化，最后一个条件保证程序的写操作的结果不会丢失。

Bernstein条件的两个不足：没有考虑执行速度的影响；在实际程序执行过程中很难对这三个条件进行检查。

2 进程的定义和描述

为了更好的描述程序执行过程及系统中的状况，引入进程。(解决异步执行带来的问题,瞎写 瞎读 )

2.1进程process的定义

一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。进程与处理器、存储器和外设等资源的分配和回收相对应，是计算机系统资源的使用主体。

进程的并发执行是指多个进程在同一计算机操作系统中的并发执行。

2.2进程的描述

进程控制块PCB

由操作系统维护的用来记录进程相关信息的数据结构。操作系统依据进程控制块对进程进行控制和管理，其内容会随进程推进而动态改变。进程控制块处于操作系统核心，通常不能由应用程序自身的代码来直接访问，而要通过系统调用进行访问。

进程控制块的组成

1. 进程描述信息，包括进程标识符(processID)、进程名(通常是可执行文件名)、用户标识符(userID)和进程组(process group)等。
2. 进程控制信息，包括当前状态、优先级、代码执行入口地址、程序的外存地址、运行统计信息(执行时间、页面调度)、进程阻塞原因等。
3. 资源占用信息，指进程占用的系统资源列表。
4. 处理器现场保护结构，用于保存寄存器值，如通用寄存器、程序计数器PC、状态字PSW、地址包括栈指针等。

进程控制块的组织方式

操作系统对于同一状态的进程的进程控制块的组织方式有：

1. 链表方式：将同一状态的进程控制块组成一个链表，多个状态对应多个不同的链表，如就绪链表和阻塞链表等。
2. 索引表方式：将同一状态的进程归入一个索引表，再由索引指向相应的进程控制块，多个状态对应多个不同的索引表，如就绪索引表和阻塞索引表等。

进程上下文

对进程执行活动全过程的静态描述(或进程的映象与进程运行环境两部分信息的集合)，包括进程的用户地址空间内容、处理器中寄存器内容及与该进程相关的核心数据结构等。

1 用户级上下文，指进程的用户地址空间，包括用户级正文段、用户数据段和用户栈；

2 寄存器级上下文，指程序寄存器、处理器状态寄存器、栈指针、通用寄存器的值等；

3 系统级上下文，包括进程的静态部分(PCB和资源表格)和由核心栈等构成的动态部分。

说明：

程序寄存器PC给出CPU将要执行的下条指令的(虚)地址；

处理器状态寄存器PS给出机器与该进程相关联时的硬件状态，如当前执行模式，能否执行特权指令等；栈指针指向下一项的当前地址；

通用寄存器用于不同执行模式之间的参数传递等；

核心栈用来装载进程中所使用系统调用的调用序列(或进程执行在内核模式时使用的堆栈)；

区表项(区表、页表或域表)定义了进程从虚地址到物理地址的映射，或虚地址与实地址映射表(含进程访问权限)。

2.3进程与程序的关系

1. 进程是动态的，程序是静态的。程序是有序代码的集合，进程是程序的执行，进程通常不可以在计算机之间迁移，程序通常对应着文件、静态和可以复制。
2. 进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可长期保存。
3. 组成不同。进程的组成包括程序、数据和进程控制块(即进程状态信息)
4. 进程与程序密切相关。通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个过程；进程可创建其它进程，而程序并不能形成新的程序。
5. 进程是程序代码的执行过程，但并非所有代码执行过程都从属于某个进程。例如处理器调度器是操作系统中的一段代码，其功能为：将处理器从一个进程切换到另一个进程；防止某进程独占处理器。处理器调度器的执行过程就不与进程相对应。

(感觉进程就是为了让程序不会瞎吉儿并发执行，设置了一堆限制和规则，来控制他们的并发)

2.4进程的特征

1. 动态性，指进程具有动态的地址空间，地址空间的大小和内容都是动态变化的。地址空间的内容包括代码(指令执行和处理器状态的变化)，数据(变量的生成和赋值)，和系统控制信息(进程控制块的生成和删除)。
2. 独立性，指各进程的地位空间相互独立，除非采用进程间通信手段，否则不能相互影响。
3. 并发性，亦称异步性，指从宏观上看，各进程是同时独立运行的。
4. 结构化，指进程地址空间的结构划分，如代码段、数据段和核心段划分。

2.5进程的状态转换

为刻画进程不断变化的过程，所有操作系统都把进程分成若干种状态并约定各状态间的转换条件。

五状态进程模式

进程在运行过程中主要是在就绪、运行和阻塞三种状态间进行转换，创建状态和退出状态描述进程创建的过程和进程退出的过程。

1. 运行状态Running，进程占用处理器资源，处于此状态的进程的数目小于等于处理器的数目，在没有其它进程可以执行时，通常会执行系统的空闲进程。
2. 就绪状态Ready，进程已获得除处理器外的所需资源，等待分配处理器资源，只要分配了处理器进程就可以执行。就绪进程可按多个优先级来划分队列。例如当一个进程由于超时而进入就绪状态，排入低优先级队列；当进程由于I/O操作完成而进入就绪态时，排入高优先级队列。
3. 阻塞状态Blocked，由于等待I/O操作或进程同步条件而暂停运行时的状态。
4. 创建状态New，进程正在创建过程中，还不能运行。创建工作包括分配和建立进程控制表项，建立资源表格(如打开文件表)并分配资源，加载程序并建立地址空间表等。
5. 退出状态Exit，进程已结束运行、回收除进程控制块之外的其他资源，并让其他进程控制块收集有关信息(如记帐和将退出代码传递给父进程)。

状态转换

操作系统中多个进程的并发执行是通过调度与超时两种转换间的循环或调度、等待事件和事件出现三种转换间的循环来描述的。

1. 创建新进程，创建一个新进程以运行程序。可能的原因包括用户登录，操作系统创建以提供某项服务，批处理作业等。
2. 提交(Admit或收容)，收容一个新进程进入就绪态。由于性能、内存、进程总数等原因，系统会限制并发进程总数。
3. 调度运行Dispatch，从就绪进程表中选择一个进程进入运行态。
4. 释放Release，由于进程完成或失败而终止进程运行、进入结束或退出状态。运行到结束的转换分为正常退出Exit和异常退出Abort，其中异常退出指进程执行超时、内存不足，非法指令或地址访问、I/O操作失败，被其他进程所终止等原因而退出；从就绪态或阻塞态到结束或退出状态的释放转换可能由于多种原因引发，如父进程可在任何时间终止子进程。
5. 超时Timeout，由于用完时间片或高优先级进程就绪等原因导致进程暂停运行。
6. 事件等待EventWait，进程要求的事件未出现而进入阻塞，可能原因为：申请系统服务或资源、通信、I/O操作等。
7. 事件出现EventOccurs，进程等待的事件出现。如IO操作完成、申请成功等。(操作系统要解决的一个重要问题是当一个事件出现时如何检查阻塞进程表中的进程状态，单队列结构时对系统性能影响很大，可能的做法是按等待事件类型的多队列结构)。

挂起进程模型

五状态进程模型没有区分进程地址空间位于内存还是外存，在操作系统中引入虚拟存储管理技术后，需进一步区分进程的地址空间状态。这个问题的出现是由于进程优先级的引入，一些低优先级进程可能等待较长时间，从而被对换至外存。

挂起suspend，把一个进程从内存转到外存；激活active，把一个进程从外存转到内存。其好处是：

1提高处理器效率：就绪进程表为空时，有空闲内存空间用于提交新进程；

2可为运行进程提供足够内存：资源紧张时，可把某些进程对换至外存；

3有利于调试：在调试时挂起被调试进程，可方便地对其地址空间进行读写。

2.6进程的控制***

进程控制就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到进程高效率并发执行和协调、实现资源共享的目的。

操作系统对进程的控制是依据用户命令和系统状态来决定的。用户可在一定程序上对进程的状态进行控制，其主要体现在进程的创建与退出及进程的挂起与激活。

原语及分类

把系统态下运行的某些具有特定功能的程序段称为原语。其分类有：①机器指令级的，执行期间不允许中断，是一个不可分割的基本单位；②功能级的，作为原语的程序段不允许并发执行。

进程的创建

创建方式：

1. 由系统程序模块统一创建。例如在批处理系统中，由操作系统的作业调度程序为用户作业创建相应进程。由系统统一创建的进程之间的关系是平等的，一般不存在资源继承关系。
2. 由父进程创建。例如在层次结构的系统中，父进程创建子进程以完成并行工作。由父进程创建的子进程之间存在隶属关系、互相构成树型结构的家庭关系，属于某个家庭的子进程可以继承其父进程的某些属性(或所拥有的资源)。按子进程是否覆盖父进程和是否加载新程序分类：fork复制现有进程上下文，但系统上下文会不同，产生新进程；spawn加载程序，创建新进程并加载新程序，产生新进程；exec加载新程序并覆盖自身，不产生新进程。
3. 在系统生成时，创建承担系统资源分配和管理工作的系统进程。

主要工作：进行进程控制块等相关数据结构的维护。

参数说明：进程名(外部标识符)n，处理器初始状态(或进程进行运行现场初始值，主要指各寄存器和程序状态字初始值)S0，优先数K0，父进程分给子进程的初始主存区M0及其他资源清单(多种资源表)R0。

进程退出

亦称进程终止，操作系统要删除系统维护的相关数据结构并回收进程占用的系统资源，如释放进程占用的内外存空间，关闭所打开文件，释放共享内存段和解除各种锁定等。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

进程阻塞

在一个进程期待某一事件(例如键盘输入数据、写盘、其他进程发来的数据等)发生而发生条件尚不具备时，该进程自己通过相应系统调用来阻塞自己。(或进程在执行过程中会因为等待I/O操作完成或等待某个事件出现而进入阻塞状态。)

进程唤醒

当等待队列中进程所等待的事件发生时(事件出现或I/O操作完成)，阻塞进程将被唤醒而进入就绪状态。唤醒方式：

1. 由系统进程唤醒，系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程；
2. 由事件发生进程唤醒，事件发生进程与被唤醒进程之间是合作关系。

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3进程间的关系

3.1进程间关系

间接制约关系

众多进程共同使用系统资源称为共享性。实际上许多资源的使用性质决定了共享往往是宏观上的，如cpu、打印机等要求排它性地轮流使用，A进程使用时，B进程就不能使用，即互斥使用。此类资源一般为重大资源，如cpu、主存空间、外设、文件等，由操作系统统一分配与调度。由此而造成的进程间的互斥制约关系称为间接制约关系。

直接制约关系

多道系统中某作业完成先对两n阶矩阵求逆而后相加，则可建立两个进程分别负责两矩阵的求逆，另建一进程负责两矩阵的相加工作。尽管由于进程并发性而带来的各进程进展的随机和不可预知即异步性，但该任务中各进程的工作进展应有先后次序，即存在时序关系：相加工作应在求逆工作后进行，这就是同步，并且求逆进程应将求逆工作完成和求逆后的结果都通知相加进程，表现为进程间的通信及交换数据。由此二者造成的进程间的相互制约关系称为直接制约关系，一般由进程间自行协调。

进程互斥是指由于共享资源所要求的排他性，进程间要相互竞争以使用这些互斥资源。

进程同步是指多个进程中发生的事件存在某种时序关系，必须协同动作、相互配合以共同完成一个任务。(异步事件能按照要求的时序进行，以达到合作进程间协调一致地工作。)

在诸多并行性问题中最重要和最根本的是进程间互斥，它是解决同步的基础，实际上互斥亦是一种同步。

3.2基本概念和原则

进程之前可能出现的问题：

示例1 SPOOL系统的假脱机输出技术。

操作系统提供外部设备联机同时操作的功能设备spool系统，又称为假脱机系统。

spool系统在应用程序执行前将应用程序的信息通过独占设备预先输入到辅存上的一个特定的存储区域存放好。称为预输入。

在应用程序执行中，也不必直接启动独占设备输出数据，而只要将其输出数据写入磁盘中存取，在应用程序执行完毕后，由操作系统来组织信息输出，称为缓输出。

转载于:https://www.cnblogs.com/luo841997665/p/4669781.html

对于进程要打印输出的文件必须在输出队列中排队，其输出队列为名为SPOOLER的专用的打印输出的文件名录。它有N个目录项，依次编号0，1，2……，用以保存等待打印输出的文件名。系统中专设进程printer负责打印，其周期性检查是否有要打印的文件，若有则负责打印输出，并将已完成输出的文件名从名录中清除。为此，系统设置两个变量out和in。out指示下一个要打印的文件，in指示名录中下一空目录项。图为某时刻目录状况。

假设进程A和B要将各打印输出的文件放入输出队列SPOOLER。若A运行(……；读in；将in 存入局部变量nextfreeitem中)，此时恰好时钟中断，进程A的时间片到，调度转至B运行(……；读in；将in中值(仍为‘6’)存入其局部变量，检测其值为“6”并将B的输出文件存入第6个目录项中；然后将in值增1；其他工作……)。若进程A再次调度运行时，继续从断点处运行，(检测局部变量nextfreeitem值为“6”，将A的输出文件名存入第6个目录项中；nextfreeitem增1存入in中；……)，其结果是导致进程B的文件丢失而没有打印。

示例2 两进程共享变量count，其描述为

①按P1，P2的顺序，count变量值增2；

②按P1(1)，P2(1)，……，count变量值增１。(若P1，P2分时使用同一处理器，当P1(1)执行完发生时间片中断，而后P2得到执行。)

结果①是正确的，结果②是错误的。若P1，P2是航空定票系统中的两个订票进程，count代表某班机售出的座位数，情况②会给旅客及航空公司造成不愉快的后果。

分析：原因在于变量in及count是互斥性使用的共享变量，进程必须互斥地对其进行访问。

临界资源?指计算机系统中的需要互斥使用的硬件或软件资源，如外设共享代码段、共享数据结构等。

临界区critical section进程中访问临界资源一段代码。

进入区entry section检查可否进入临界区的代码段。如果可以进入临界区，设置“正在访问临界区”标志，以阻止其他进程同时进入临界区。

退出区exit section清除“正在访问临界区”标志的代码段。

剩余区 remainder section代码中的其余部分。

进程同步机制遵循的原则

• 空闲则入：当无进程处于临界区时，必须让一个要求进入临界区的进程立即进入临界区，以有效使用临界资源。
• 忙则等待：当已有进程处于其临界区时，后到达的进程只能在进入区等待。
• 有限等待：等待进入临界区的进程不能无限制地“死等”。
• 让权等待：在进入区等待而不能进入临界区的进程应释放处理器，转至阻塞状态，以使其他进程有机会得到处理器的使用权。

3.2互斥算法(基于进程间平等协商的办法)

3.2.1进程互斥的软件方法

(基本思路)在进入区检查和设置一些标志，如果有进程在临界区，则在进入区通过循环检查等待，在退出区修改标志。

(1)双标志-先检查算法　设一标志数组Flag[]，描述各进程是否在临界区，初值均为FALSE；进入区操作为先检查，后修改。设进程Pi与Pj，其中Pi代码描述为：

While(Flag[j]；

Flag[i]=TRUE；

临界区

Flag[i]=FALSE

剩余区

缺点：进程Pi和Pj可能同时进入临界区，原因在于检查和修改不能连续进行。

这里是检查完才修改，所以存在两个进程同时检查，同时进入的情况

(2)双标志-先修改后检查算法　标志Flag[i]表示进程Pi想进入临界区，而不再表示进程i在临界区。设进程Pi与Pj，其中Pi代码描述为：

Flag[i]=TRUE；

While(Flag[j]；

临界区

Flag[i]=FALSE

剩余区

缺点：进程Pi和Pj可能都进不了临界区，原因在于修改和检查不能连续进行。

(如果没有进程可以修改flag，则开始设置为true后，所有进程都是true，无可进入)

说明：完全利用软件方法实现进程互斥有很大局限性，如不适用于数目很多的进程间的互斥，其原因在于修改与检查不能作为一个整体被执行。

3.2.2进程互斥的硬件方法

(基本思想)用一条指令完成读和写两个操作去保证读操作与写操作不被打断。

TS(Test and Set)指令　读出指定标志后把该标志设置为TRUE，其函数描述为：

Boolean TS(Boolean *lock)
{
    Boolean old；
    old=*lock；*lock=TRUE；
    return old；
}

每个临界资源设一公共布尔变量lock表示资源的两种状态，TRUE表示正被占用，FALSE表示空闲，初值为FALSE。所有访问该临界资源的进程，其进入区和退出区代码均相同。

While TS(&lock)；
临界区
lock=FALSE；
剩余区

优点：

①适用范围广：任意数目进程，单处理器与多处理器环境中完全相同。

②简单：标志设置简单，含义明确，易验证其正确性。

③支持多个临界区：每个临界区可定义一个布尔变量。

缺点：

①不能实现“让权等待”。

当判断为true时，就会一直while循环，占用cou资源，在进入区等待而不能进入临界区的进程应释放处理器，转至阻塞状态，以使其他进程有机会得到处理器的使用权

②由于进入临界区的进程是从等待进程中随即选择，有些进程可能一直选不上，导致“饥饿“。

说明：基于进程间平等协商来解决公有资源的使用问题，其存在的问题有：没有获得执行机会的进程就无法判断而导致不公平现象，获得测试机会的进程又为测付出一定的cpu时间。其软件方法复杂，不直观且效率低，硬件办法存在忙等、饥饿的缺点，原因在于每个进程能否进入临界区必须依靠自己的测试判断。故需引入地位高于进程的管理者来解决公有资源的使用问题，这个管理者就是操作系统。

3.3信号量机制

3.3.1基本概念

信号量semaphore机制是由操作系统提供的管理公有资源的有效手段。

基本原则：在多个相互合作的进程之间使用简单的信号来同步，进程可被强制地停止在一个特定的地方直至收到一个专门的信号。

信号量说明

1. 包括一个整数值(用于计数count)及一个进程等待队列queue，其中是阻塞在该信号量的各个进程标识。
2. 信号量只能通过初始化和P、V两个标准原语来访问。P、V原语作为操作系统核心代码的一部分，其执行不受进程调度和执行的打断，具有很好的操作整体性。
3. 信号量可初始化为一非负整数，表示空闲资源总数；信号量为非负整数值，表示当前空闲资源数；若为负值，其绝对值表示当前等待进入临界区的进程数。

关于P、V原语

p原语(或操作)相当于进入区操作，v原语(或操作)相当于退出区操作。

type semaphore= record
value：integer；
L：pointer to Pcb；
end；

设s为某资源上的信号量，p原语描述为：

procedure p(s)
var s: semaphore；
begin
s.value :=s.value-1；
if s.value<0 then block(s.L)；
end

或

wait(s)

{
--s.value；
if(s.value<0) {
insert(CALLER，s.L)；
block(CALLER)；
}
}

其中各项说明为：表示申请一个资源；若无空闲资源；调用进程进入等待队列；阻塞调用进程。

v原语描述为：

procedure v(s)
var s:semaphore；
begin
s.value:=s.value+1；
if s.value<=0 then wakeup(s.L)；
end

或

signal(s)

{
++s.value；
if(s.value<=0) {    //原来是-1 表示有进程在等待序列
remove(s.L， id)；
wakeup(id)；
}
}

其中各项说明为：表示释放一个资源；若有进程处于阻塞状态；从等待队列中取头一个进程P；进程P进入就绪队列。

②对共享资源访问控制时，必须成对使用P、V原语。丢失P则不能保证互斥访问；丢失V则不能在使用临界资源之后将其释放给其他等待的进程。二者使用不能次序颠倒、重复或遗漏。

3.3.2信号量机制的应用

实现进程互斥

对于示例２，两进程共享临界资源count的同步算法为：

var mutex : semaphore=1；
cobegin
P1: begin
    repeat
        p(mutex)；
        R1:=count；
        R1:=R1+1；
        count:=R1；
        v(mutex)；
        remainder of P1；   
    until false；
    end；

P2: begin
    repeat
        p(mutex)；
        R2:=count；
        R1:=R2+1；
        count:=R2；
        v(mutex)；
        remainder of P2；
    until false；  
    end；
coend；

分析：两个进程共享临界资源时，信号量取值范围为[1，0，-1]；n个进程共享临界资源时，信号量取值范围为[1，0，-1，…，-(n-1)]。

实现进程同步

如图示三合作进程中? ?计算进程与打印进程间的同步算法。

? ? ? ? ? ? ? 输入进程Pi? ? ? ? ? ? 计算进程Pc? ? ? ? ? ? ? 打印进程Pp

输入设备—————→buffer—————→buffer—————→打印设备

分析：进程互斥时各进程的执行顺序是任意的。在异步(并发)环境下，进程Pc与Pp的执行不同于互斥，各自的执行结果互为对方的执行条件，Pc的输出结果是Pp的执行条件，Pp的执行结果也是Pc的执行条件，表示为Pc与Pp间的直接制约，即同步关系问题。对于同步问题，P原语可视为查看进程前进的信号有无，则计算进程Pc应先查看有无空的缓冲区，打印进程Pp应先查看有无数据。设置两个信号量，Sa初值为０，表示缓冲区内无数据；Sb初值为１，表示缓冲区空闲可用。(V原语可视为向合作进程发出信号)

var Sa，Sb:semaphore；
Sa:=0，Sb:=1；
cobegin
    Pc: begin
        repeat
            p(Sb)；
            计算下一数据并送入缓冲区；
            v(Sa)；
        until false；
        end

    Pp: begin
        repeat
            p(Sa)；
            从缓冲区中取数据；
            v(Sb)
            打印数据；
        until false；
        end；
coend；

为什么不可以用一个信号量？比如buffer容量为n 一个信号量为Sa? 一个为n-Sa

P（s）中的s表示资源 它的算法里有一个value 进行加减操作时是对s.value操作的

因为信号量是用于表示资源使用情况的一个数据结构。因此，只有同一类资源才能使用一个信号量。在生产者消费者问题的同步中，生产者需要的资源是仓库中空位置，只有当有空位置时，生产者才能将产品放入仓库，而消费者从仓库中取走一个产品后就会释放仓库中的一个空位置。另外，消费者需要的资源是产品，只有仓库中有产品，消费者才能去取。

描述前趋关系

就是进程间的同步关系。示例，前趋关系如图：

var a，b，c，d，e，f，g，semaphore=0，0，0，0，0，0，0；
begin
cobegin
begin S1:v(a)；v(b)；end；
begin P(a)；S2；v(c)；v(d)；end；
begin P(b)；S3；V(e)；end；
begin P(c)；S4；V(f)；end；
begin P(d)；S5；V(g)；end；
begin P(f)；P(g)；P(e)；S6；end；
coend；
end

3.3.3信号量机制的推广

解决同时需要多种资源的互斥访问问题，信号量集是指同时需要多种资源的信号量操作。

AND型信号量集是指同时需要多种资源且每种占用一个资源的信号量操作。

问题示例

当一段代码需要同时获得两种或多种临界资源时，可能出现由于各进程分别获得部分临界资源并等待其余临界资源的局面，各进程都会各不相让，导致死锁发生。　

某进程P1在申请一台输入设备后，又继续申请一台打印设备，然后使用之，过后陆续释放，进程P2在申请一台打印设备后又继续申请一台输入设备，使用后陆续释放。这里mutex1=1表示输入设备，mutex2=1表示打印设备，则同步描述如下：

var mutex1.mutex2:semaphore；
mutex1:=mutex2:=1；
cobegin
    P1:begin
        p(mutex1)；
        p(mutex2)；
        陆续使用输入设备和打印设备；
        v(mutex1)；
        v(mutex2)；
    end；

    P2:begin
        p(mutex2)；
        p(mutex1)；
        陆续使用打印设备和输入设备；
        v(mutex2)；
        v(mutex1)；
    end；
coend；

该同步过程中使用的P操作是嵌套的，可能出现死锁。

基本思想：在一个原语中申请整段代码所需要的多个临界资源，要么全部分配给它，要么一个都不分配给它。

AND型信号量集P原语称为SP或swait(simultaneous)，其描述为：

sp(S1，S2，……Sn)
if (S1>=1 and …… and Sn>=1)
    then    for i=1 to n do Si:=Si-1；
else
    将该进程置于找到的第一个与Si<1相关的等待队列中；
    置该进程的程序计数器为sp操作的起始处；
Endif

//进入等待队列后进程执行：
swait(S1，S2，……Sn)
{ 
    while(TRUE)
    {            //不断判断s1-sn什么时候全部可用，否则一直循环
        if(S1>=1&&……&&Sn>=1)
        {
            for (i=1；i<=n；++i) 
            --Si；
            break；
        }
        else
        {
            调用进程进入第一个小于１信号量的等待队列Si；
            阻塞调用进程；
        }
    }
}

AND型信号量集V原语称为SV或Ssignal，其描述为：

sv(S1，S2，……Sn)
for i=1 to n do
    Si=Si+1；
    摘下等待Si队列中所有进程；
    并插入就绪队列；

//对所有Sn执行唤醒操作
ssignal(S1，S2……Sn)
{
    for (i=1；i<=n；i++)
    {
        ++Si；
        for(each process P waiting in Si queue)
        {
            从等待队列Si　queue中取出进程P；
            if((判断进程P是否通过Swait中的测试)     //现在i是有了 j可能没了...可怜....
            {
                进程P进入就绪队列；
            }
            else 
            {
                进程P进入某等待队列；
            }
    　  }
   }
}

“一般信号量集“指同时需要多种资源，每种占用的数目不同，且可分配的资源还存在一个临界值时的信号量处理。

4经典同步问题

评价同步工具优劣的参考标准：

1. 同步能力强，适合于多种同步类型；
2. 安全、可靠、合理且易证明其正确性；
3. 实现方便且使用效率高；
4. 清晰、易懂、易于使用。

同步工具的使用：

1. 如何选择信号量；
2. 如何安排P、V原语的使用顺序。

信号量分类：

1. 私有信号量指只与制约进程和被制约进程有关的信号量；
2. 公用信号量指与一组并发进程有关的信号量。

生产者－消费者问题

指若干进程通过有限(个)的共享缓冲区交换数据时的缓冲区资源使用问题。

问题描述

生产者进程不断向共享缓冲区写入数据(生产数据)，消费者进程不断从共享缓冲区读出数据(消费数据)；共享缓冲区共有n个，任何时刻只能有一个进程可对共享缓冲区进行操作。

问题分析

1)共享缓冲区中的n个缓冲块为共享资源；生产者写入数据的缓冲块为消费者的可用资源；消费者读出数据后的(空白)缓冲块为生产者的可用资源。

2)设置信号量　full表示有数据的缓冲块数目，初值为０；empty表示空白的缓冲块数目，初值为n；mutex用于访问缓冲区时的互斥，初值是１，其中存在关系full＋empty=n。

3)确定P、V原语的次序　各进程必须先检查自己对应的资源数目，在确信有可用资源后再申请对整个缓冲区的互斥操作；否则就可能死锁。(如先申请互斥操作)　

算法描述

type B=shared record
buffer: array 0……n-1 of datas；
p，c:0……n-1；
end；
var mutex，full，empty:semaphore:=1，0，n；    //互斥  已占用量  空余量
cobegin
producer:
begin
    repeat
        produce next product；
        p(empty)；
        p(mutex)；
        send product to buffer(p)；
        p:=(p+1) mod n；                    //生产指针移动 mod是为了循环到开始
        v(mutex)；
        v(full)；
    until false；
end；
consumer: 
begin
    repeat
        p(full)；
        p(mutex)；
        get product from buffer(c)；
        c:=(c+1) mod n；
        v(mutex)；
        v(empty)；
        consume product；
    until false；
end；
coend；

这里，公用信号量mutex保证各进程之间的互斥，empty为生产者进程的私有信号量，full为消费者进程的私有信号量。

读者－写者问题

示例 文件系统、数据库中普通存在的一个数据集(文件或记录)如果被几个并发进程所共享，一些进程只是要求读数据集的内容，而另一些进程要求修改数据集的内容。通常读进程称为阅读者或读者，要求修改数据的进程称为写入者或写者。①若干阅读者可以同时读数据集，不加互斥也不会产生任何问题，即不存在破坏数据集中数据完整性、正确性的问题；②一个写入者不能与其他进程(无论阅读者或写入者)同时访问数据集，必须互斥，否则将破坏数据集数据的完整性。此类问题即是读者－写者问题。

问题描述

读者－写者问题是指多个进程对一个共享资源进行读写操作问题。设读者进程只对共享资源进行读操作，写者进程可对共享资源进行写操作，任一时刻写者最多只允许一个，读者则允许多个。这里共享资源的读写操作限制关系有“读－写”互斥，“写－写”互斥和“读一读”允许。　　

问题分析

读者－写者问题解决的目的是保证共享资源(或数据集)的数据完整性，数据完整性是内部逻辑性的体现。

①读一读　尽管存在与并发性并存的异步性，各读者进程经读操作所得到的数据完整性是不变的，即不会影响正确性，各读者进程之间彼此不会有任何影响。

②读－写　由于与并发性并存的异步性，写者进程的写操作会造成读者进程读取数据的不完整，即破坏读者进程经读操作得到的数据完整性，从而影响到读进程内部的控制逻辑，这是并发进程不允许的。

③写－写　由于与并发性并存的异步性，各写者进程的写操作会造成某些写进程写的结果的丢失(对同一写入点)或破坏数据完整性，这也是并发进程所不允许的。

关于选择信号量

1)据上分析　由于存在读写互斥与写写互斥，则对于共享资源(或数据集)而言是必须互斥使用的，故应首先为该共享资源设立一个互斥信号量，记为m，初值为1。

2)当没有任何进程使用共享资源时，对读者进程或写者进程，谁先到达谁先获得使用权，即应执行P(m)操作，因此每个进程都应首先申请共享资源的使用。

根据2)，读写进程的描述为：

写者 读者

………… …………

P(m)? ? ? ? ? P(m)

writing? ? ? ?reading

V(m)? ? ? ? ? ?V(m)

………… …………

3)若当前使用者是写者进程时(此时m<=0)，后到进程将因无法申请到共享资源的使用权而阻塞。

4)若当前使用者是读者进程时，后到写者进程将因无法申请到共享资源的使用权而受阻；但因读-读是允许的，也就是说后到的读者进程将可以立即得到共享资源的使用权，即不必去申请使用权(即免去P(m))，也即是表明当前有使用权的读者进程与后到的读者进程应有区别，即第一个读者进程要申请使用权并在获得使用权后应与后续读者进程要进行标志，这里采用读者计数rc(readcount)，初值为０。

根据4)修改读者进程：

读者

…………

if rc=0 then P(m)
rc=rc+1；
reading
rc=rc-1；
if rc=0 then V(m)；

…………

5)为保证计数rc的正确性，各读者进程之间必须互斥使用，故对rc应设立使用权信号量，记为rcm(readcountmutrx)，初值为１。

算法描述

var m.rcm: semaphore； rc: integer；
m:=1；rcm:=1；rc:=0；
cobegin
READER: 
begin
    repeat
        P(rcm)；
        if rc=0 then P(m)；
        rc:=rc+1；
        V(rcm)；
        reading；
        P(rcm)；
        rc:=rc-1；
        if rc=0 then V(m)；
        V(rcm)；
    until false；
end；

WRITER: 
begin
    repeat
        P(m)；
        writing；
        V(m)；
    until false；
end；
coend；

问题及其算法描述的再分析

1)若当前使用者是写者，则后到的写进程将被阻止在信号量m上，第一个读者将被阻止在信号量m上，后续读者将被阻止在信号量rcm(即第一个读者不仅无法得使用权被阻塞，同时连带锁定rc的使用权，阻止即剥夺后续读者的rc使用权)。

2)若当前使用者是读者，则后到的写者进程将被阻止在信号量m上，而后到的读者(无论在写前或写后)都不会阻止而得到共享资源的使用权，也即是即使有写者被阻塞而等待在先，后来的读者将会源源不断地得到各自的使用权(即越过写者而先得到使用权)。

3)根据上述两点，读者使用权时阻止写者，并使写者后面的读者越过写者而先得到使用权；写者使用权阻止的各进程，一旦第一个受阻读者被调用(唤醒)，则会使后等待的读者也会越过先等待的写者而得到使用权。故本算法实际是一个读者优先的描述。

4)数据及时性的考虑　设有进程序列……读１，写１，读２……，该序列无论是否为等待序列，都会出现读２越过写１而先得到使用权(按前面的算法)。如果仅仅考虑数据的完整性，上面的处理无疑是正确的，但若要及时知道或反应数据的修改情况，上述序列若为等待序列，则应按谁先等待谁先使用的原则进行，以保证数据及时性(每个读者应读到最新数据)。

无优先的读者写者问题

要求实现

1读者使用权时：紧接着到来的若干读者不会等待(读读允许)；到来的所有写者必须等待(读写互斥)；晚于写者到来的读者必须等待(无优先)。

2写者使用权时：所有到来的读者必须等待(读写互斥)；所有到来的写者必须等待(写写互斥)。

算法描述

数据集使用权m=1， 读者计数rc=0及使用权rcm=1，写信号w=1。

w谁拿谁运行? 用完释放

读者进程：

p(w)；
p(rcm)；
if rc=0 then p(m)；
rc:=rc+1;
v(rcm)；
v(w)；
reading
p(rcm)；
rc:=rc-1；
if rc=0 then v(m)；
v(rcm)；

写者进程：

p(w)；
p(m)；
writing
v(m)；
v(w)；

写优先的读者写者问题

要求实现

1读者使用权时：紧接着到来的若干读者不会等待(读读允许)；到来的所有写者必须等待(读写互斥)；晚于写者到来的读者必须等待(无优先或写者优先)。

2写者使用权时：所有到来的读者必须等待(读写互斥)；所有到来的写者必须等待(写写互斥)；写者等待优先于读者等待(写者优先)。

算法描述

设数据集使用权m=1，读者计数rc=0及使用权rcm=1，写者计数wc=0及使用权wcm=1，写信号w=1。

还是加入了一个w写信号，读写进程写夺取w信号，当写得到后，进行写进程，如果后面新来写进程，则加入计数，有计数则不放w，直到没有写进程加进来且之前的运行完成，释放w后r进程得到w

读者进程：

p(w)；
p(rcm)；
if rc=0 then p(m)；
rc + 1；
v(rcm)；
v(w)；
reading；
p(rcm)；
rc – 1；
if rc =0 then v(m)；
v(rcm)；

写者进程：? ? ? ? 如果wc不为0 则前边有写进程 已经对w加着锁

p(wcm)；
if wc = 0 then p(w)；
wc + 1；
v(wcm)；
p(m)；
writing；
v(m)；
p(wcm)；
wc – 1；
if wc = 0 then v(w)；
v(wcm)；

嗜睡的理发师问题(由图灵奖获得者Dijkstra教授提出)

理发店里有一位理发师、一把理发椅和N把供等候理发的顾客坐的椅子。

如果没有顾客，理发师便在理发椅上睡觉，当一个顾客到来时，他必须先叫醒理发师；

如果理发师正在理发时又有顾客到来，如果有空椅子可坐，顾客就坐下来等候；如果没有空椅子，顾客就离开。

请设计理发师和顾客的同步算法。

分析：

对于互斥同步，主要解决两个问题：1正确设置信号量，2恰当安排PV原语的使用顺序。

1信号量设置

等待理发的顾客customer=0；

顾客竞争的理发权barber=0；

空座椅计数count=N及其使用权m=1。

2同步算法描述

方案1 barber=0(这个方案应该是合理的)

顾客：

p(m)；
if count = 0 then {v(m)； exit；} 若无空椅子，则退出理发店；
count –1； 坐在一张空椅子上；
v(m)；
v(customer)； 有要理发的顾客；
p(barber)； 等待理发，直至被理发师叫到；
p(m)；
count + 1； 腾出一张空椅子；
v(m)；
get_cuthair()； (被)理发；

理发师：

p(customer)； 查看有无顾客等待理发，若没有，则睡觉；
v(barber)； 叫起一位顾客；
cuthair()； 理发；

方案2 barber=1(这个方案是有问题的，因为顾客对理发权实际没有竞争没有先后，而是一起直接闯入理发室理发，没有和理发师形成同步)

顾客：

p(m)；
if count = 0 then {v(m)； exit；} 若无空椅子，则退出理发店；
count –1； 坐在一张空椅子上；
v(m)；
v(customer)； 有要理发的顾客；
p(barber)； 等待理发，直至被理发师叫到；
v(barber)；
p(m)；
count + 1； 腾出一张空椅子；
v(m)；
get_cuthair()； (被)理发；

理发师：

p(customer)； 查看有无顾客等待理发，若没有，则睡觉；否则，叫起一位顾客；
cuthair()； 理发；

方案3

barber=0

顾客：

p(m)； 查看有无空座椅
if count > 0 then 有空座椅
{
    count – 1；
    v(customer)； 找到一把空座椅坐下，若理发师在睡眠，则唤醒理发师；
    v(m)；
    p(barber)； 等待理发
    get_cuthair()； 理发
}
else
{ 
    v(m)；
    exit；
} 若无空座椅，则退出理发店。

理发师：(存在不尽合理之处，理发师在叫入一位等待理发的顾客时，是不允许新顾客进入等候室的，因为锁定的m的使用权)

p(customer)； 查看有无顾客，若无，则睡眠；
p(m)；
count + 1；
v(barber)； 叫入一位等待的顾客(给予理发权)
v(m)；
cuthair()； 理发

3竞争合作关系

互斥竞争关系：

1)顾客之间要竞争N把空椅子count，同时要竞争计数检查时的使用权m；

2)表面看是竞争N把空椅子，其实count也起到了同步作用，即限制可以等待的顾客的数量，最多N个；

3)进入理发店的顾客要竞争理发权barber，起到了先来后到的作用。

合作同步关系：

1)顾客向理发师发出一个新的理发请求，理发师要查看有无等待理发的顾客，customer；

2)每叫入一位顾客到理发室，也表示将理发权传递给下一位等待的顾客。

哲学家就餐问题(由图灵奖获得者Dijkstra教授提出)

五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。由于通心粉很滑，所以需要两把叉子才能夹住。相邻两个盘子之间放有一把叉子，餐桌如图。

哲学家的生活中有两种交替活动时间段，即吃饭和思考(这只是一种抽象，即对哲学家而言其他活动都无关紧要)。当一个哲学家觉得饿了时，他就试图分两次去取左边和右边的叉子，每次拿一把，但不分次序。如果成功地得到两把叉子，就开始吃饭，吃完后放下叉子继续思考。请描述哲学家之间的同步算法。

分析：

设哲学家逆时针依次编序0-4，叉子依次编序0-4，哲学家i左手叉子i、右手叉子(i+1)%5。

方案1

设信号量fork[0..4]表示叉子的使用权，初值均为1；

philosopher[i]
{
    while (TRUE)
    {
        think()；
        p(fork[i])；
        p(fork[(i+1)%5])；
        eat()；
        v(fork[i])；
        v(fork[(i+1)%5])；
    }
}

这个方案有错误，错误在哪儿？由于并发性或者不确定性，恰好每个哲学家都拿起他们左边的叉子，则进入无限制等待右边的叉子，谁也无法用餐。

方案2

设信号量fork[0..4]表示叉子的使用权，初值均为1；

信号量m加强保护(不恰当的认为是餐桌的使用权或者用餐权)，初值为1；

philosopher[i]
{
    while (TRUE)
    {
        think()；
        p(m)；
        p(fork[i])；
        p(fork[(i+1)%5])；
        eat()；
        v(fork[i])；
        v(fork[(i+1)%5])；
        v(m)；
    }
}

这个方案有错误，错误在哪儿？

任何时刻只能有一个哲学家用餐。

方案3

设信号量fork[0..4]表示叉子的使用权，初值均为1；

信号量m加强保护(不恰当的认为是餐桌的使用权或者用餐权)，初值为2；

philosopher[i]
{
    while (TRUE)
    {
        think()；
        p(m)；
        p(fork[i])；
        p(fork[(i+1)%5])；
        eat()；
        v(fork[i])；
        v(fork[(i+1)%5])；
        v(m)；
    }
}

这个方案是否可行？

任何时刻至多允许两个哲学家用餐。

方案4

设状态数组state[0..4]，分别表示各哲学家的状态thinking/hungry/eating，初值均为thinking；

信号量m，表示状态数组的使用权，初值为1；

信号量数组s[0..4]，表示各哲学家的用餐权，初值均为0；

philosopher[i]
{
    while (TRUE)
    {
        think()； 哲学家在思考
        p(m)；            m保证相邻两个人不会同时eating
        state[i]=hungry； 哲学家饿了
        test(i)； 尝试获取用餐权，即尝试取得2把叉子
        v(m)；
        p(s[i])； 若未取得用餐权，则等待，直到邻位通知再进行test使他的si改变
        eat()； 哲学家在用餐
        p(m)；            m同理
        state[i]=thinking； 哲学家用餐已经结束
        test( (i+5-1)%5)； 尝试向相邻哲学家归还用餐权
        test( (i+1)%5)；
        v(m)；
    }
}
test(i) 尝试取得或归还哲学家i的用餐权
(如果相邻哲学家均不在用餐状态且自己饿了，则应获得用餐权)
{
    if (state[i] == hungry && state[(i+5-1)%5] != eating && state[(i+1)%5] != eating)
    如果哲学家饿了并且相邻两位哲学家均不在用餐状态
    {
        state[i] = eating； 哲学家进入用餐状态
        v(s[i])； 获得用餐权
    }
}

这个方案能否达到要求？

面包店问题。(由图灵奖获得者Lamport提出)(此问题描述及解决不完全，暂不作为授课内容)

面包店销售面包和蛋糕，店内有n个销售员。每个顾客进店后先取一个号，并等待叫号；若有销售员空闲下来，则叫下一个号并为该号顾客提供销售服务。请描述顾客、销售员之间的同步算法。

分析

1顾客之间应竞争服务号count=1并排队queue及其使用权qm=1；

2顾客取到服务号后，应向销售员表明要求服务的请求wait=0，并等待叫号m=0；

3若销售员空闲，则应查看有无顾客要求服务；

(方案1)

顾客：

p(qm)；
取服务号n=count并排队queue；
count + 1；
v(qm)；
v(wait)； 有顾客请求服务；
p(m)； 等待叫号；
销售服务；

销售员i：

p(wait)； 查看有无顾客要求服务
p(qm)；
从排队中取号n并叫号；
v(qm)；
v(m)；
为n号顾客提供销售服务；

注：1这里似乎存在漏洞，若后来的先p(t)，则打乱顺序；2叫起顾客应按顺序，可能要设计队列。

(方案2)

顾客：

p(qm)；
取号n=count并排入队列queue；
count+1；
v(qm)；
v(wait)； 向销售员发出服务请求
销售服务；

销售员i：

p(wait)；
p(qm)；
从排队队列queue中取出服务号n；
v(qm)；
为n号顾客提供服务；

注：这里也存在不足吗，请考虑。

这些同步问题中需要处理的是竞争和合作关系，既有竞争又有合作，竞争的一般是公有资源，合作的一般是同步信号，即时序关系，有的简单一些，有的复杂一些，我们这里提供的是使用一般信号量机制来解决，也有需要信号量集机制进行解决的问题，比如哲学家就餐问题，请考虑。

上下楼梯问题

学生的宿舍楼梯很窄，不能同时上下，但可以同时上或同时下，并且下楼梯优先，即如果此时有人正在上楼梯并且有一个人等待下楼梯时，则不再有新的上楼梯者进入楼梯。请用PV操作写出进程间的同步算法。

分析：

设上梯进程和下梯进程，则竞争合作关系如下：

1上下互斥；2上上允许；3下下允许；4下梯优先。

令楼梯使用权lm = 1，则满足1：

上梯者：? 下梯者：

P(lm)；? ? ?P(lm)；

上楼梯；? 下楼梯；

V(lm)；? ? ?V(lm)；

(谁先到达谁先使用)

令上梯者计数uc = 0及其使用权ucm = 1，下梯者计数dc = 0及其使用权dcm = 1，则满足1、2、3：

上梯者：? ? ? ? ? ? ? ? ? ? 下梯者：

P(ucm)；? ? ? ? ? ? ? ? ? ? P(dcm)；

if uc = 0 then P(lm)； if dc = 0 then P(lm)；

uc = uc + 1； ?????????????dc = dc + 1；

V(ucm)；? ? ? ? ? ? ? ? ? ? ?V(dcm)；

上楼梯； ????????????????????下楼梯；

P(ucm)；? ? ? ? ? ? ? ? ? ? ?P(dcm)；

uc = uc – 1；? ? ? ? ? ? ? ?dc = dc – 1；

if uc = 0 then V(lm)；? ? if dc = 0 then V(lm)；

V(ucm)； ?????????????????????V(dcm)；

(上上允许、下下允许)

令下梯使用权dm = 1，由第一个下梯者发出，每个上梯者必须检测，则满足1、2、3、4：

上梯者： ????????????????下梯者：

P(dm)；

P(ucm)； ????????????????P(dcm)；

if uc = 0 then P(lm)； if dc = 0 then {P(dm)； P(lm)；}

uc = uc + 1；? ? ? ? ? dc = dc + 1；

V(ucm)； ????????????????V(dcm)；

V(dm)；

上楼梯； ????????????????下楼梯；

P(ucm)； ????????????????P(dcm)；

uc = uc – 1；? ? ? ? ?? dc = dc – 1；

if uc = 0 then V(lm)； if dc = 0 then {V(dm)； V(lm)；}

V(ucm)； ????????????????V(dcm)；

(下梯者优先)

测试用例，用于考察是否满足那四个关系：

上1，上2，下1，下2，上3，下3，上4，下4

下1，下2，上1，上2，下3，上3，下4，上4

请同学们也考虑有无其他方案，说明理由。

5信号量机制存在的问题

• 逻辑正确性：操作系统或并发程序通常会使用很多信号量，它们的关系错综复杂，难以保证整个系统的逻辑正确性。
• 使用正确性：同步操作分散在各进程中，使用不当即可导致死锁。
• 程序可读性：要了解一组共享变量及信号量的操作是否正确，必须通读整个系统或并发执行的多个程序。
• 可维护性：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局。

问题的主要原因

在于对共享资源的P、V同步操作分散于各进程中，故一个改进的办法是将同步操作相对集中起来，交由操作系统来完成。将抽象共享资源的数据(信号量)及其操作对封装为一体，这就是面向对象思想出现的由来。

3.4进程间通信(Inter-Process Communication.IPC)

基本概念

目的 解决进程间的信息交流问题。

分类

1按通信量的大小

• 低级通信 进程间只能传递状态和整数值(控制信息)，包括进程互斥和同步采用的信号量机制。速度快而传送信息量小，通信效率低，编程复杂。
• 高级通信 进程间可传递任意量的数据，高效率传送大批数据，包括共享存储区、管道及消息等机制。

2按通信过程中是否有第三方作为中转

• 直接通信 指发送方把信息直接传递给接受方，常用于相互关系紧密的进程间。
• 间接通信 指通信过程要借助于收发双方进程之外的共享数据结构(如消息队列)作为通信中转。接收方和发送方的数据可以是任意的。

典型方式介绍

• 共享存储区shared memory 可用于进程间的大数据量通信。进行通信的各进程可任意读写共享存储区，也可在共享存储区上使用任意数据结构。在使用共享存储区时，需要进程互斥和同步机制的辅助来确保数据一致性。
• 消息系统Message System 进程间的信息交换以消息或报文为单位，利用操作系统提供的一组通信命令(原语)来实现通信。
• 管道Pipe 一条在进程间以字节流方式传送的通信通道，利用操作系统核心的缓冲区(通常是几十个KB)来实现的一种单向通道。

实例分析——消息缓冲通信

消息缓冲区的结构描述

type message buffer = record
sender: 消息发送者；
size: 消息长度；
text: 消息正文；
next: 指向下一个消息缓冲区的指针；
end；

发送与send原语 向系统申请一个消息缓冲区，将发送区中的信件内容复制在消息缓冲区；将该消息缓冲区插入接收进程的消息链中，并通知其有信件。

procedure send(receiver，a)
begin
    getbuf(a size，v)；
    v.sender:= a.sender；
    v.size: = a.size；
    v.text:=a.text；
    v.next:=0；
    get id(PCBset.receiver，j)；
    p(j.mutex)；
    insert(j.mq，i)；
    v(j.mutex)；
    v(j.sm)；
end；

其中：mq进程消息链首指针：mutex消息链本身的互斥信号量；sm消息链的同步记数信号量。

接收与receive原语 接收进程查看sm计数信号量获知是否有待处理的信件，若无则此位置即为接收进程的等信口并阻塞等待；若有(被发送进程唤醒)，则从消息链上摘下一个消息缓冲区，将信件内容复制到自己的接收区并释放消息缓冲区。

procedure receive(b)
begin
    p(j.sm)；
    p(j.mutex)；
    remove(j.mq，I)；
    v(j.mutex)；
    b.sender:=i.sender；
    b.size:=v.size；
    b.text:=i.text；
    put buf(i)；
end；

图示略见教材 P56 2-18。

4死锁问题

4.1死锁deadlock的概念

指多个进程由于竞争资源(或等待对方消息)而造成的彼此无休止地互相等待，在无外力作用下，永远不能向前推进的这种僵持局面。

指计算机系统和进程所处的一种状态：在系统中的一组进程由于竞争系统资源或由于彼此通信而永远阻塞。

指系统中多个进程无限制地等待永远不会发生的条件。(W2000)

4.2死锁的原因和条件

产生死锁的根本原因?对互斥资源的共享，并发执行进程的同步关系不当。

死锁形成过程的分析?按进程使用的资源分为两类。

①可重用资源reuseable resource每个时刻只有一个进程使用，在宏观上各个进程轮流使用，如处理器，主存和辅存，I/O通道，外设，数据结构(文件，数据库和信号量等)。

示例 假设系统中的资源A和B都只有一个(如输入设备和输出设备)，则申请次序P1<a>，P2<a>，P1<b>，P2<b>就会出现死锁。

P1 ???????????????????????? ? ?P2

…… ????????????????????????……

request(A)；<a> request(B)；<a>

request(B)；<b> request(A)；<b>

…… ????????????????????????……

(use)???????????????????????? (use)

…… ????????????????????????……

release(B)； ????????release(A)；

release(A)；???????? release(B)；

…… ????????????????????????……

其原因在于各进程都拥有部分资源，同时在请求其他进程已占有的资源，从而造成永远等待。

编码风格上的细微差别(哪一个资源先获得)造成了可以执行的程序和不能执行而且无法检测错误的程序之间的差别，因此死锁是非常容易发生的。

②可消耗资源consumable resourse指可以动态生成和消耗的资源，一般不限制数量，如硬件中断，信号，消息，缓冲区的数据等。

示例 假设两进程的执行次序P1<a>，P2<a>，则会由于对方还未生成资源而形成永远等待。

P1? ? ? ? ? ? ? ? ? ? ? ? ??????????P2

……???????????????????????????????? ……

receive(P2，M)；<a> receive(P1，Q)；<a>

send(P2，N)；? ? ?<b> send(P1，R)； <b>

其原因在于可消耗资源的生成和消耗存在依赖关系，其使用上可能因为双方都等待对方生成资源而形成死锁，即同步关系不当。

③关于资源的再认识 一个逻辑资源(简称为资源)是指可以引起一个进程进入等待状态的事物。

死锁发生的条件

产生死锁的4个充分必要条件，由Coffman.et.al总结。

1)互斥条件 任一时刻只允许一个进程使用资源(或资源是独占的且排它使用)。

比如两个进程同时使用打印机会引起混乱打印的结果，同时使用同一文件系统表的表项会引起文件系统的瘫痪，因此所有操作系统都具有授权一个进程(临时)排他访问某一种资源的能力。

2)请求和保持(保持与再请求，部分分配)条件 进程在请求其余资源时，不主动释放已经占用的资源(已获得的资源未释放，还要有新的申请要求)。

3)非剥夺(不剥夺，不可抢占)条件 进程已经占用的资源，不会被强制剥夺(进程已获得的资源只能由它自己释放，不允许剥夺；一个资源仅能被占有进程释放，不能被别的进程强行抢占)。

可抢占资源是指可以从拥有它的进程中抢占而不会产生任何副作用，存储器就是一类可抢占资源。例如某系统拥有32K用户内存和一台打印机，若两个32K内存的进程都想进行打印，进程A请求并获得打印机，然后开始计算要打印的值，在未完成计算任务之前，它的时间片用完并被换出；进程B开始运行并请求打印机，但没有成功，此时有潜在的死锁危险。因为A拥有打印机而B占有内存，没有另一个进程的资源，两进程中的任何一个都不能继续执行。幸运的是，通过将B换出内存、A换入内存就可以实现抢占B的内存，A继续运行并执行打印任务。然后释放打印机，在这个过程中不会产生死锁。

不可抢占资源是指在不引起相关计算失败的情况下，无法把它从占有它的进程处抢占过来。如果一个进程已开始刻盘，突然将CD刻录机分配给另一个进程，那么将划坏CD盘。在任何时刻CD刻录机都是不可能抢占的。

4)环路等待(循环等待)条件 环路中的每一条边都是一个进程在请求另一进程已经占有的资源。

由于条件1)是资源的固有特性而无法改变，只能从其它三个条件入手来解决死锁问题。

4.3死锁的预防

死锁预防是指通过某种策略来限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。

1)破坏请求和保持条件 采用预先静态分配法，即一个进程开始执行前就申请所需的全部资源并由系统在调度时为之分配所需全部资源(动态分配是指进程临近使用时才提出申请，系统再进行分配)。

缺点：降低资源利用率，降低进程的并发程度(即进程延迟运行)，适用于预先知道所需资源，但实际的进程运行有可能无法预知所需的资源。

2)破坏环路等待条件 采用有序资源使用法，将资源分类按序排列，赋予不同的序号，其一般原则是较为紧张，稀少的资源排以较大的序号，对资源的申请按递增的次序，以保证资源的申请不形成环路。

缺点：限制进程对资源的请求顺序，资源排序占用系统开销。

死锁预防施加了较强的限制条件，其实现虽较简单，但严重损害系统性能。

4.4死锁的避免

死锁避免?在分配资源时判断是否会出现死锁，只在确信不会导致死锁时才分配资源。死锁避免允许进程动态申请资源。

安全状态?指系统能按某种进程顺序如P1，P2，……Pn(称为安全序列)来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺利完成。若系统不存在这样一个序列，则称系统处于不安全状态。

银行家问题?指银行家在向顾客贷款时如何保证资金安全的问题。假设一个银行家把他的固定资金贷给若干顾客时，只要不出现一个顾客借走所有资金后还不够，银行家的资金就是安全的，银行家应实施某种策略保证借出去的资金在有限时间内可收回。

1)假定条件 每个顾客分成若干次进行贷款，并在第一次借款时能说明其最大借款额。

2)具体操作 各个顾客的借款依次顺序进行，直至全部借款操作完成。

3)贷款判断 银行能否支持顾客借款，直至全部归还。如果能，本次贷款是安全的并执行贷款；否则就是不安全的，暂不贷款。

示例1 设银行家固定资金为10个现金单位(即为顾客共享)，3个顾客：P最大借款8，已借4，仍需4，即P(8，4，4)；Q最大借款3，已借2，仍需1，即Q (3，2，1)；R为(9，2，7)。此时银行家剩余10-4-2-2=2。如图示：

若按Q，P，R次序贷款，则三顾客均完成各自的交易并归还贷款，故银行家的资金是安全的。

若银行家向R贷款一个现金单位，如图示，尽管可以保证Q完成其交易，但顾客P.R均不能完成各自交易而无法归还贷款，则银行家的资金是不安全的。

示例2 假定系统有三进程P1，P2和P3，系统共有12台磁带机，某时刻系统状态如图：

最大需求 已分配 尚需 空闲可用

分析： 若系统按P2，P1，P3分配磁带机，每个进程都可顺利完成，即存在一个安全序列<P2，P1，P3>。此时系统处于安全状态。若此刻只有P3申请一台，系统分配一台空闲给P3，则会造成同示例1相同的结果，即P2可完成但P1，P3彼此等待对方释放资源而都不能进行下去。

银行家算法描述

(多资源的银行家算法)某企业无偿还能力时就不要贷款给他。

1)设定数据结构

• a.可利用资源向量Available 一个具有m个元素的数组，表示系统中拥有的m类资源的数量，其值随该类资源的分配和回收而动态变化，Available[j]=k表示当前系统中有第j类资源k个。
• b.最大需求矩阵Max　一个n*m的矩阵，定义n个进程对m类资源的最大需求。M[i，j]=k表示进程i需第j类资源k个。
• c.分配矩阵Allocation 一个n*m矩阵，定义了各类资源当前的分配情况。Allocation［i，j］=k表示进程i已分得(占有)第j类资源的数目为k。
• d.需求矩阵Need 一个n*m矩阵，表示各进程尚需的各资源数。Need[i，j]=k表示进程i需第j类资源k个才能完成其任务。
• e.工作向量Work 表示系统可提供给进程继续运行所需的各类资源数目，用于执行安全性检查，初值Work=Available。
• f.状态标志Finish(i) 表示进程i获得足够的资源可以执行完毕，并能释放全部获得资源的状态，初值为false，达到上述情况时为true。

2)算法描述　设进程i的资源请求为Request(i)，系统要对这个申请(即顾客的借款)加以检查，以决定是否满足该申请，过程如下：

待修改

申请
N
    申请量超过宣布的Max，出错
Y
    N
        资源不够无法分配，出错
　　Y
　　　　 试探性分配修改Available
         Allocation[i].Need[i]

        安全检查。置所有进程状态标志false
        Work=Available

        查找Finish[j]=false且 置Finish[j]=true并假定进程
　　　　Need[j]≤Work的进程 j能归还全部资源
　　　　Work＝Work+Allocation[j]　　　　　　　　　　　　
Y
N

N
系统为不安全状态，不予分配
Y　　　　　　　　　　　　　　
系统为安全状态，可正式分配

3)示例 假定系统中五进程｛P0，P1，P2，P3，P4}及三种资源A，B，C，每种资源量分别为１０，５，７。当前时刻资源分配情况为：

• a.判定此刻系统的安全性(对安全性的检查可用于死锁的检测)。
• b.判定Request1(1，0，2)的可分配性。
• c.判定Request2(0，2，0)的可分配性。

银行家算法的评价?由于该算法允许资源的部分分配和不需要抢占，可提高资源利用率。其缺点是前提太严格，要求事先说明最大资源需求量并且进程数目固定，实际实现很困难，只能用于一些特定的应用。

4.5死锁的检测

死锁检测

(基本思路)在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。

资源分配图算法?主要是检查是否有循环等待。即把进程和资源间的申请和分配关系描述成一个有向图，通过检查有向图中是否有循环来判断死锁的存在。

资源分配图说明：

有向图G=(V，E)，其中顶点集V分为两部分：P={P1，……Pn}是系中进程集，R={r1，……，rm}是系统中不同资源集；边集E分两类：〈Pi，rj〉表示进程Pi申请一个单位的rj资源并处于等待状态，称为申请边；<rj，Pi>表示有一个单位的rj资源已分配给进程Pi，称为赋给边。圆圈表示进程，方框表示每种资源的类型，框中圆点表示各单位(即同类资源数目)。

单资源死锁检测算法

设资源图为G=(V， E)。令S为顶点栈，flag[e]表示边e是否已经搜索过，基本思路就是对每一个顶点进行深度优先搜索，若发现环路，则有死锁。

(1)for v 属于V do
{
    for e 属于 E do flag[e] = false；
    令S为空；
    push(v)，且v表示S栈顶的顶点；
    (2)若v出度为0 或者 所有e=<v,u>都有flag[e]=true，则
    {
        pop(v)；
        若S为空，则转(1)；否则v=top(S)，转(2)；
    }
    否则
    {
        选择一条边e=<v， u>；
        若u不属于S，则flag[e]=true， push(u)，转(2)；
        否则，发现回路，死锁，退出。
    }
}
没有回路。

例图? ? ? ? ?(x)

r1 → p1? ?p2

↓???????? ↓

p2 → r2 ← p4 → r3 → p5

↑???????? ↑???????? ↓

p6? ? ? r4????????r5

↑ ????????↑ ????????↓

r6 ???????p7???????? ←←←

多资源等价变换简化

①寻找非阻塞，非孤立进程顶点，修改其申请为赋给边，该进程顶点成为出度为0的顶点，删除其所有边(即在有限时间该进程执行完毕后释放其全部资源)，成立孤立顶点。

②重复①直至所有进程都成为孤立顶点，则表示不存在死锁；否则仍存在边的不可简化的资源分配存在死锁，其中有边进程为死锁进程。

示例(x)

r1 r2

T1 r2

r3

多资源检测算法?类似于银行家算法(略)。

死锁解除

通常是选择撤消或挂起代价最小的死锁进程，并抢占其资源以解除死锁。代价最小的判断原则可为进程优先级或系统会计过程给出的运行代价。解除死锁会造成进程中止而成为“牺牲者”，既“前功尽弃”，进而发生“饿死”现象。

总而言之，解决死锁问题的最合理做法应该是死锁的避免策略。

4.6死锁发生的概率

数学家认为无论代价有多大，都要彻底防止死锁的产生，而工程师则需要了解死锁发生的频度、死锁的严重性，如果死锁平均每5年一次，而每个月系统都会因为硬件故障、编译错误或操作系统故障而崩溃一次，那么工程师们就不会以性能损失、可用性的代价去防止死锁。

实际上，大多数操作系统都潜在地受到死锁的威胁，而这些死锁从来没有被检测到过，便自动解除了。比如系统中进程表数量受到进程表表项数量的限制。假设一个系统中进程表有100项，有10个进程在运行，每一个进程都要创建12个子进程。在每个进程创建9个进程后，原来的10个进程和新创建的90个进程将用完进程表的所有表项，那么这10个进程都将进入一个无休止的fork循环，并导致失败，实际上死锁发生了。产生这类事件的概率是很小的，但确实可能出现！

由于解决死锁的代价通常很大，并常常给进程带来不便的限制。所以大多数操作系统处理这一问题的办法就是忽略它，即把头埋到沙子里，假装根本没有问题发生，鸵鸟算法。

也就是在便利性和正确性之间进行权衡。

5 线程

5.1进程开头问题及进程特性

假定一个用户正打算用编辑程序编辑一个文件，但在编辑前，想先审查分析一下该文件，并且要复制一个该文件的副本。为了加快以上工作，提高效率，有效的方法是并行运行以上各子任务。在只有进程机制的操作系统中，可以用并行程序设计语言来写此程序：为整个应用任务设置一个进程，而后该进程再为n个子任务生成n个子进程，以实现迸发的结果。这些进程在运行中提出访管要求(系统调用)，如提出I/O请示、或由于超时而打断当前进程运行，调度其他就绪进程运行。进程切换带来的系统开销有：与进程运行有关的表格均要改(包括PCB表，各种队列，阻塞队列，运行队列或指针，就绪队列。存储管理有关的地址映射及表格、I/O文件的表格等。)；可观的进程的地址空间转换为新调度进程的地址空间；两次模式转换(用户模式→内核模式→用户模式)。这些大量系统开销的总和在一定程度上降低了并发所带来的利益。这就是进程开关问题。(同时进程间通信的效率也受到限制)

进程的特性

①进程是拥有自己资源的单元体，即存储器、外设等资源的分配单位；

②进程是被调度分派在处理器上运行的单元体，即是处理器高度的对象。

这里，①是关于拥有资源的主权，②是关于应用程序的执行。二者的统一体即传统的进程概念。

严重的局限性

①对于想并发执行彼此独立任务且又共享一个公共的地址空间和其他资源的应用，这些进程本质上是并行的，但传统进程不能支持这些要求，而将应用中的独立的任务串行化，效率很低。

②不能很好地利用多处理器系统。因为传统进程在某个时刻只能使用一个处理器。(尽管可为一个应用创建多个进程并分到多个处理器上执行，但问题是保证使用相同的地址空间和资源。)

5.2线程的概念

引入的目的?提高进程内的并发程度。(简化进程间通信，以小的开销)

线程的定义Thread

①一个动态的对象，是处理器调度的基本单位，表示进程中的一个控制点，执行一系列的指令。

②一个进程内的基本调度单位。

③运行的最小单位。

④进程内一个相对独立的、可高度的执行单元

线程的性质

1. 进程内一个相对独立的可执行单元，即为应用的一个子任务的执行；
2. 调度的基本单元，每个进程至少一个线程；
3. 进程是资源分配单位，线程只是使用者，同一进程内的多个线程共享该进程的资源及相应通信与同步机制的支持；
4. 具有生命期。

传统的进程概念可视为只有一个主线程的进程。

线程的优点

1. 线程的创建时间短；
2. 线程的终止时间短；
3. 同进程内线程的时间短；
4. 由于同进程内线程间共享内存及文件资源，可直接进行不通过内核的通信。

进程与线程的关系

单进程线程 单进程多线程

多进程单线程 多进程多线程

进程与线程的不同

①地址空间资源

不同进程的地址空间是相互独立的，同一进程的各线程共享同一地址空间。一个进程中的线程在另一进程中是不可见的。

②通信关系

进程间通信必须使用操作系统提供的进程间通信机制，同一进程的各线程间通信可通过直接读写进程数据段(如全局变量)来进行通信，即在同步和互斥手段的辅助下以保证数据的一致性。

③进程切换

同一进程线程切换比进程切换快得多。

第二章作业

1程序执行时的两种方式及特点是什么？

顺序执行：

1. 顺序性：指处理机严格格地按照程序所规定的顺序执行
2. 封闭性：指程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响
3. 可再现性:指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果。

并发执行：

1. 间断性。程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。
2. 失去封闭性。当系统中存在着多个可以并发执行的程序时，系统中的各种资源将为它们所共享，而这些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其环境都必然会受到其它程序的影响。
3. 不可再现性。程序在并发执行时，由于失去了封闭性，也将导致其又失去可再现性。

2讨论Bernstein条件。

两个过程如果有数据冲突,那么就没法并行执行。

比如过程A生成数据d,而过程B需要输入数据d,那么B就需要A的输入，他们就没法并行执行(写后读问题，RAW)。如果二者会影响后续过程需要的数据，尤其是该数据和他们执行的顺序很有关系，那么他们同样也不能并行执行(写后写问题, WAW)。

3进程与程序的区别是什么？

1、程序是指令的有序集合，是一个静态概念，其本事没有任何运行的含义。而进程是程序在处理机上的一次执行过程，是一动态的概念。

2、程序可以作为一种软件资料长期保存，而进程则是有一定生命周期的，它能够动态的产生和消亡。

3、进程是一个能独立运行的单位，能与其他进程并行活动。

4、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。程序无此该概念。

5、进程与程序之间无一一对应关系。不同的进程可以包含同一程序，同一程序在执行中也可以产生多个进程。

6、程序是记录在介质上指令的有序集合，而进程则由程序、数据和进程控制块3部分组成。

4为什么说各进程在单机时并发执行与多机时并行执行在本质上是一样的？

1. 宏观上各进程都是在同时进行

5说明制约关系： a)若干同学去图书馆借书b)两队进行篮球比赛c)流水线生产中的各道工序

间接制约 ?间接制约 直接制约 直接制约

6解释临界资源、临界区及互斥同步机制的原则。

（1）临界资源：指每次只允许一个进程访问的资源，分为硬件、软件临界资源。

（2）临界区：每个进程中访问临界资源的那段程序，进程对临界区的访问必然相反，每次仅允许一个进程进入临界区，其它进程等待。

（3）互斥同步原则：

1、空闲等待：当没有进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区；

2、忙则等待：当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必然等待，以保证进程互斥地访问临界资源；

3、有限等待：对要求访问临界资源的进程，应当保证进程能够在有限时间进入临界区，以免陷入“死等”状态；

4、让权等待：当进程不能进入自己的临界区时应当释放处理机，以免进程陷入“忙等”状态。

7设有K个进程共享一临界区，对于下述情况，说明信号量的初值，含义并用P、V原语写出互斥算法。

a)一次只允许一个进程进入临界区

b)一次允许L(L﹤K)个进程进入临界区

(1)一次只允许一个进程进入临界区:

设s为互斥信号量，初值为1，表示有1个空闲且可用的共享临界资源

对任一进程Pi (1≤i≤k):

P(s)

<进入临界区>

V(s)

信号量s的变化围为[-(k-1) ..,-1,0,1]。 其中，s=1表示有1个空闲且可用的临界资源，且没有进程进入类名为s的临界区; s=0表示有1个进程在临界区中(该临界资源已被某进程占用)，无等待使用该临界资源的进程; s=-n(1≤n≤k-1， n为整数)表示有1个进程在临界区中，且有n个进程等待使用该临界资源。

(2)一次允许L?(L<k)个进程进入临界区:

设s为互斥信号量，初值为m,表示有m个空闲且可用的共享临界资源，即可允许m个

进程同时进入该临界区.

对任一进程Pi (1≤i≤k):

P(s)

<进入临界区>

V(s)

信号量s的变化围为[-(k-m) ...-1,0.1...m]。 其中，s= m表示有m个空闲且可用的临界资源，且没有进程进入类名为s的临界区; s=j(1≤j<m, j为整数)表示有m-j个进程正在该临界区中，且仍有j个空闲且可用的临界资源，且无等待使用该临界资源的进程;s=0表示有m个进程在临界区中，目前无空闲且可用的临界资源，且无等待使用该临界资源的进程; s=-n(1≤n≤k-m， n为整数)表示有m个进程在临界区中，目前无空闲且可用的临界资源，且有n个进程等待使用该临界资源

8进程A的工作流程如图，若系统中进程只有三种状态，转化如图。被调度选中后可投入运行，时间片q=200ms，用序号列出其生命过程，并注明原因。

开始 ????????计算????????? 盘I/O ????????带I/O? ? ? ? ? ? ?打印机I/O ????????结束

? ? ? ? ? ? ? ? ? ? ? ? ?250ms ????????50 ms ????????200 ms ????????150 ms

就绪A ?运行B 阻塞C

A->B 进程被调度程序选中立即投入运行，运行200ms

B->A 时间片到时，进程由运行态转变成就绪态，发生进程切换

A->B 某时刻，该进程.重新被调度程序调度投入运行，进程从就绪态变成运行态 运行50ms

B->C进程请求磁盘I/0，由运行态变为阻塞态

C->A 磁盘I/O完成后，进程由阻塞态变为就绪态

A->B 在某时刻被调度程序调度得到CPU运行，从就绪态变成运行态运行50ms

B->C 进程因请求磁带I/O而阻塞

C->A 进程磁带I/O请求完成后，从阻塞态变成就绪态

A->B 某一时刻被调度程序选中执行，从就绪态变成运行态，运行200ms

B->A 时间片用完，进程从运行态变为就绪态

A->C 某一时刻，调度程序选中进程执行，但进程要执行打印请求，此时进程从就绪态变成阻塞态

C->A 打印请求结束后，进程由阻塞态变为就绪态

A->B 某一时刻进程又被重新调度执行，进程从就绪态变成运行态,运行150ms后进程结束。

9设有n个单元的环形缓冲区及一个无穷信息序列。甲进程按信息序列逐个地把信息写入环形缓冲区，乙进程则逐个地把缓冲区信息读出。试问：

a)叙述甲、乙进程间的制约关系。

b)下面同步算法有无错误，若有，请纠错，其中S1 初值为0，S2初值为n﹣1。

进程甲 进程乙

V(S1) P(S1)

写入缓冲区 取出信息

P(S2) V(S2)

c)若缓冲区有无穷多个，则两进程间制约关系如何？请写出相应的同步算法。

10设有64个存储区域其编号为0、…、63，存储区使用与否用一个64位的标志字表示，每一位对应一个存储区域，当某位置1时，表示该区已分配，置0表示该区空闲。get进程负责存储区的分配，每次分配一个区域，其分配动作为：找出标志字的某个为0位，将其置1；put进程负责存储区的回收，其回收动作为：把回收区域对应的标志字的相应位置0。试问：

a)分析get，put进程的同步关系。

b)用P、V原语写出两个进程间的同步算法。

分析：

get进程可以被连续调用执行，每次分配一个存储区直至64个存储区全部分配，若再调用get进程分配，则必须等待put进程对存储区的释放回收；put进程被调用执行，则不会受到限制；由于两个进程共同使用标志64个存储区的64位标志字，因此需要互斥。

设置信号量，m=1表示标志字的使用权，free=64表示可供分配的存储区，同步如下

var flagword=bit[0..63] ={0,…0};
m:semaphore = 1, free:semaphore = 64;
getprocess(user):
p(free);
p(m);
搜索flagword中的第一个0位，置为1，对应存储区为memoryarea;
v(m);
将memoryarea返回给调用用户user；

putprocess(memoryarea):
p(m);
搜索flagword，找到存储区memoryarea对应的标志位，置为0；
v(m);
v(free);

11某超级市场，可容纳100人同时购物。入口处备有篮子，每个购物者可持一只篮子入口购物，出口处结帐，并归还篮子(出入口仅容一个人通过)，请用P、V原语写出购物同步算法。

分析：

由题可知出入口为一个，所有购物者共同使用，因此需要竞争使用权，超级市场允许至多100个人同时购物，因此需要购物权100个。

var
m:semaphore = 1, shopticket:semaphore = 100;
shopper:
p(shopticket);
p(m);
在出入口取得一只购物用的篮子，进入超级市场；
v(m);
shopping…;
p(m);
在出入口处结账并归还购物用的篮子，离开超级市场；
v(m);
v(shopticket);

12设某批处理系统中，有三个进程：卡片输入进程、作业调度进程、作业控制进程，它们之间的合作关系是：

a)只要卡片机上有作业信息，输入进程就把作业逐个地输入到输入井，并为每个作业建立一个JCB块，并把它插入后备作业(JCB链表)中。

b)当内存中无作业运行时，作业调度进程从JCB链中挑选出一个作业，并把该作业装入内存。

c)作业控制进程负责处理已调入内存的作业。

试问：

a)用P、V原语写出三进程间的同步算法。

b)用消息缓冲通信写出三进程间的同步算法。

分析：

a)设信号量，卡片机准备好卡片card=0，后备作业计数jobs=0，内存无作业empty=1，内存有待处理作业full=0，JCB链的使用权，则各进程为

inputprocess:
p(card);
启动卡片机，读入卡片，建立一个新的后备作业JCB；
p(m);
将新作业的JCB插入JCB链；
v(m);
v(jobs);

scheduleprocess:
p(empty);
p(jobs);
p(m);
从JCB链中取下一个作业并读入内存；
v(m);
v(full);

handleprocess:
p(full);
处理内存中的作业；
v(empty);
b)使用消息缓冲机制
需要设置JCB链使用权信号量m=1；

inputprocess:
receive(cardmachine, readysignal);
启动卡片机，读入作业，建立一个新的后备作业JCB；
p(m);
将新作业的JCB插入JCB链；
v(m);
send(scheduleprocess, jobssignal);
scheduleprocess:
receive(inputprocess, jobssignal);
p(m);
从JCB链中取下一个作业并读入内存；
v(m);
send(handleprocess, waitforhandlesignal);
receive(handleprocess, handleoversignal);

handleprocess:
receive(scheduleprocess, waitforhandlesignal);
处理内存中的作业；
send(scheduleprocess, handleoversignal);

13、如图表示一条带闸门的运河，其上有两座吊桥，吊桥坐落在一条公路上，为使公路避开一块沼泽地令其横跨运河两次。运河及公路的交通都是单方向的。运河上的运输由驳船承担。当驳船接近吊桥A 100米时就鸣笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾部通过桥为止。吊桥B也同样次序处理。典型驳船长度为200米。

?

试问：

汽车和驳船在前进中是否会发生死锁？

提出防止死锁的办法。