操作系统——进程的描述与控制

1 前趋图和程序执行

1.1 前趋图

• 前趋图（Precedence Graph）：是一个有向无循环的图，记为DAG（Directed Acyclic Graph），描述进程之间的先后顺序。

• 目的：更好的描述程序的顺序和并发执行的情况

• 表示为P={p1,p2,p3,p4,p5,p6,p7,p8,p9}={(p1,p2),(p1,p3),(p1,p4),(p2,p5),(p3,p5),(p4,p6),(p4,p7),(p5,p8),(p6,p8),(p7,p9),(p8,p9)}

**attention：**前趋图中不允许有循环的，所以下图不成立。
在这里插入图片描述

1.2 程序顺序执行

• 程序顺序执行

一个应用程序分成若干个程序段；

每一个程序段完成特定的功能；

各程序段之间必须按照某种先后次序顺序执行；

仅当前一段程序段执行完成后，才运行后一程序段；

• Ii→Ci→Pi

• example

S1: a:=x+y；
S2: b:=a-5；
S3: c:=b+1；

语句S2必须在语句S1之后(即a被赋值)才能执行；同样，语句S3也只能在b被赋值后才能执行。

因此，这三条语句应按图示顺序执行S1→S2→S3

• 程序顺序执行的特征

（1）顺序性：处理机的操作严格按照程序规定的顺序执行，即每一操作必须在上一个操作结束之后开始

（2）封闭性：程序是在封闭的环境下执行的，即程序运行的时候独占全机资源，资源的状态（除初始状态外）只有程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。

（3）可再现性：只要程序执行时的环境和初始条件相同，当程序当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。

1.3 程序并发执行

• 只有不存在前趋关系的程序才能并发执行

由上图可知，Pi-1，Ci，Ii+1之间不存在前趋关系，可以并发执行

• example

S1:a = x + 2;
S2:b = y + 4;
S3:c = a + b;
S4:d = c + b;

画图：

• 程序并发执行的特征

（1）间断性:程序并发执行，由于它们共享资源系统，以及为完成同一项任务相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。相互制约将导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。

（2）失去封闭性:程序并发执行时，多个程序共享资源，资源的状态将由多个程序来改变，致使程序的运行失去了封闭性（单个程序独占资源时，资源状态由程序自己决定）

（3）不可再现性:程序在并发执行时，失去了封闭性，计算结果与并发程序的执行速度有关，从而使程序的执行失去了可再现性

2 进程的描述

2.1 进程的定义

具有一定独立功能的程序关于一个数据集合的一次运行活动

进程的其他定义

（1）进程是程序的一次执行
（2）进程是程序及其数据在处理机上顺序执行时所发生的活动
（3）进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
//传统os进程定义，在引入进程实体概念后：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

2.2 进程控制块

为了使参与并发执行的每个程序都能独立运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block，PCB）

作用：描述进程的基本情况和活动过程，进而控制和管理进程

创建进程：实质上是创建进程中的PCB

撤销进程：实质上是撤销进程的PCB

2.3 一个进程

进程包含了正在运行的一个程序的所有状态信息

（1）程序的代码
（2）程序的数据
（3）CPU寄存器的值，如用来指示下一条将运行的指令、通用寄存器等
（4）一组系统资源（如地址空间、打开的文件）
（5）堆和栈

2.4 进程的特征

（1）动态性：基本特征。进程的实质是进程实体的执行过程。表现在"它由创建而产生，由调度而而执行，由撤销而消亡"。

（2）并发性：另一重要特征。多个进程实体同存于内存之中，且能在一段时间内同时运行。

（3）独立性：进程实体是一个能独立运行、独立获得资源、独立接受调度的基本单位。attention：凡是为建立PCB的程序都不能作为一个独立的单位参与运行。

（4）异步性：进程按各自独立地、不可预知的速度向前推进

2.5 进程的基本状态及转换

• 三种状态

（1）就绪状态（Ready）

进程已经具备运行条件，但由于CPU忙暂时不能运行，只要分得CPU即可执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。

（2）执行状态（Running）

进程已获得CPU，其程序正在执行的状态。对任何一个时刻而言，在单处理机系统中，只有一个进程处于执行状态； 在多处理机系统中，则可以有多个进程处于执行状态。

（3）阻塞状态（Block）

正在执行的进程由于发生某事件（如请求I/O或进程同步）而暂时无法继续执行时，便放弃处理机而转至阻塞状态。通常将这种处于阻塞状态的进程也排成一个队列。有些较大的系统会根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列，以减少操作开销，提高效率。

• 转换关系

attention：阻塞结束后不能直接转换到执行状态，而是转到就绪状态

• 创建状态和终止状态

（1）创建状态

步骤：

• 申请一个空白的PCB，并向PCB填写用于控制和管理进程的信息
• 为该进程分配运行时必须的资源
• 把该进程转入就绪状态并插入就绪队列中

attention：资源分配不满足，比如系统无足够的内存将内存装入，无法完成，进程不能被调度，于是把此时进程所处的状态称为创建状态。获得资源后转为就绪状态。

目的：保证进程调度必须在创建工作完成后进行，确保对进程控制块操作的完整性，增加管理的灵活性。

（2）终止状态

步骤：

• 等待操作系统进行善后处理
• PCB清零，并将PCB内存空间返回

什么情况下会终止：

• 进程达到自然结束点
• 出现无法克服的错误
• 被操作系统终止
• 被其他有终止权的进程所终结

进入终止状态的进程以后不再执行，但在操作系统中依然会保留一个记录，保存其状态码和一些计时统计数据，供其他进程收集。一旦完成信息提取，操作系统删除该进程，清零PCB，返回空白PCB。、

五种状态及其转换关系图：

• 挂起操作和进程状态的转换

（1）挂起

该操作作用于某个进程时，该进程将被挂起，意味着此时进程处于静止状态。如果进程正在执行，它将暂停执行，若原本就处于就绪状态，则该进程暂不接受调度。与挂起操作对应的是激活操作。

（2）为什么需要挂起—基于系统和用户的需要

• 终端用户需要：终端用户在自己程序运行期间发现可以问题，希望暂停自己的程序的运行。
• 父进程请求：父进程有时希望挂起自己的某个子进程，以便考察和修改该子进程或者协调各个子进程间的活动。
• 负荷调节的需要：把不重要的进程挂起，以保证系统能正常运行
• 操作系统的需要：操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账

（3）引入挂起原语（Suspend）操作之后三个进程状态的转换

• 活动就绪（Readya）—静止就绪(Readys)

当进程处于未被挂起的就绪状态，称为活动就绪，此进程可以接受调度。当用挂起原语（Suspend）将该进程挂起后，便处于静止就绪状态（Readys），不再被调度执行。

• 活动阻塞（Blockeda）—静止阻塞（Blockeds）

• 静止就绪（Readys）—活动就绪（Readya）

• 静止阻塞（Blockeds）—活动阻塞（Blockeda）

（4）引入挂起操作后五个进程状态的转换

• NULL→创建：一个新进程产生时，该进程处于创建状态
• 创建—活动就绪
• 创建—静止就绪：系统不分配给新建进程所需资源，主要是主存，相应的系统将进程状态转为静止就绪状态，被安置在外存
• 执行—终止

2.6 进程管理中的数据结构

• 操作系统中用于管理控制的数据结构

为描述和管理进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB(Process Control Block)，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。PCB记录了进程当前情况以及控制进程运行的全部信息。由于PCB访问频繁，所以PCB应常驻内存。PCB是进程存在的唯一标志。

• 进程控制块PCB的作用

(1) 独立运行基本单位的标志： PCB是进程存在的唯一标志。 
(2）实现间断性运行：进程阻塞而暂停运行时，需要保留运行时的CPU现场信息在PCB中，以恢复时使用。
(3）提供进程管理调度、同步和通信所需要的信息。

• 进程控制块PCB中的信息

（1）进程标识符

作用：进程标识符用于惟一地标识一个进程

• 内部标识符：操作系统为每一个进程赋予了一个惟一的数字标识符，它是一个进程的序号。设置内部标识符主要是为了方便系统使用。
• 外部标识符：由创建者提供，通常由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。

（2）处理机状态

组成：由处理机中的各种寄存器中的内容组成

• 通用寄存器：用户程序可以访问，用于暂存信息，在大多数处理机中，有 8～32个通用寄存器，在RISC结构的计算机中可超过100个
• 指令计数器：存放了要访问的下一条指令的地址
• 程序状态字PSW：含有状态信息：条件码、执行方式、中断屏蔽标志等
• 用户栈指针：指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址，栈指针指向该栈的栈顶。

（3）进程调度信息

PCB中还存放一些进程调度和进程对换的信息，包括

• 进程状态:指明进程的当前状态，作为进程调度和对换时的依据
• 进程优先级：用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机
• 进程调度所需的其它信息:与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等
• 事件:指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因

（4）进程控制信息

• 进程的程序和数据所在的内存或外存地(首)址:以便再调度到该进程执行时，能从PCB中找到其程序和数据
• 实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等:它们可能全部或部分地放在PCB中
• 资源清单:列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单
• 链接指针:它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址

3 进程控制

进程控制一般通过OS内核中的原语来实现

3.1 操作系统内核

OS内核——将与硬件紧密相关的模块（如中断处理程序等），常用设备驱动程序，运行频率较高的模块（如时钟管理、进程调度等），都安排在紧靠硬件的软件层次中，并将它们常驻于内存中（开机后），通常称为OS内核

• os内核功能

（1）支撑功能

• 中断处理——OS中很多重要活动，如系统调用、键盘命令输入、进程调度、设备驱动等，都依赖于中断

• 时钟管理——OS的许多活动都需要用到时钟管理，如时间片轮转调度中，每当时间片用完，便由时钟管理产生一个中断信号，促使调度程序进行调度。还有实时系统的截止时间控制等，也需要用到时钟管理

• 原语操作——原语(Primitive)是由若干条指令组成的，用于完成一定功能的一个过程。与一般过程的区别在于：原子操作(Action Operation)

原子操作：指一个操作的所有动作要么全做，要么全不做。换言之，它是一个不可分割的基本单位，因此，在执行过程中不允许被中断。原子操作在管态下执行，常驻内存。

attentiion：内核中提供了许多原语操作，例如用于进程同步的原语。

（2）资源管理功能

• 进程管理——进程调度、创建、撤销，进程同步、通信，等等这些通常都放在内核中。
• 存储器管理——例如内存的分配与回收、保护、对换等，用于实现将用户空间的逻辑地址转换为内存空间的物理地址的地址转换机构，通常存放在内核中
• 设备管理——与硬件密切相关，大部分设置在内核中。如各类设备的驱动程序、缓和CPU和I/O速度不匹配的缓冲管理、设备分配等

3.2 进程的创建

（1）进程的层次结构

操作系统中，允许一个进程创建另一个进程——父进程、子进程。子进程还可以创建孙进程。由此形成层次结构。如在Unix系统中，进程与其子孙进程共同组成一个进程家族。

（2）进程图(Process Graph)

树的根节点称为进程家族的祖先

（3）引起创建进程的事件

• 用户登录：在分时系统中，用户在终端键入登录命令后，如果登陆成功，系统将为该终端建立一个进程，并插入就绪队列中

• 作业调度：在多道批处理系统中，当作业调度程序按一定的算法调度到某作业时，便将该作业装入内存，为它分配必要的资源，并立即为它创建进程，再插入就绪队列中

• 提供服务：运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务。例如用户程序要求进行文件打印，操作系统将为它创建一个打印进程

• 应用请求：上述三种情况下都是由系统内核创建一个新进程；应用请求则是由应用进程根据需要自己创建新进程，以便使新进程以并发运行方式完成特定任务

（4）进程的创建

一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语Creat( )按下述步骤创建一个新进程

• 申请空白PCB。为新进程申请获得惟一的数字标识符，并从PCB集合中索取一个空白PCB。
• 为新进程分配其运行所需的资源，包括内存、I/O设备、CPU时间、文件等。
• 初始化进程控制块：① 初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中；② 初始化处理机状态信息，如程序计数器、栈指针等；③ 初始化处理机控制信息，将进程状态设置为就绪或静止就绪，并设置为最低优先级（除非用户以显式方式提出高优先级要求）。
• 将新进程插入就绪队列。

3.3 进程的终止

引起进程终止的事件(正常结束、异常结束、外界干预）

• 正常结束

表示进程的任务已经完成，准备退出运行

• 异常结束

(1)越界错误，程序访问的存储区越出该进程的区域。
(2)保护错误。进程试图访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如试图去写只读文件。
(3)非法指令。进程试图去执行一条不存在的指令。如程序错误地转移到数据区，把数据当成了指令。 
(4)其他错误，如特权指令错、运行超时、等待超时、算术运算错、 I/O故障等。

• 外界干预

(1) 操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程。
(2) 父进程请求。父进程具有终止自己的任何子孙进程的权力，因而当父进程提出请求时，系统将终止该进程。
(3) 父进程终止。当父进程终止时，OS也将它的所有子孙进程终止。 

进程的终止过程

(1) 从PCB集合中检索进程的PCB，读出进程状态。
(2) 若进程处于执行状态，应立即终止；若还有子孙进程，也应全部终止。
(3) 进程资源归还系统或父进程。
(4) 将进程的PCB从所在队列(或链表)中移出。

3.4 进程的阻塞与唤醒

（1）引起进程阻塞和唤醒的事件

(1)正在执行的进程请求共享资源，而操作系统无法立即满足其要求时，进程转变为阻塞状态来等待。
(2) 启动某种操作
　　当进程启动某种操作后，若进程必须等待该操作完成后才能继续执行，则必须先使该进程阻塞。
(3) 新数据尚未到达
　　对于相互合作的进程，如果其中一个进程需要先获得另一(合作)进程提供的数据后才能对数据进行处理，则只要其所需数据尚未到达，该进程只有(等待)阻塞。
(4) 等待新任务的到达（无新工作可做）
　　操作系统（尤其是网络环境下的OS）往往设置一些具有某特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。

(2) 进程唤醒过程

当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒

wakeup执行过程

• 把阻塞的进程从等待该事件的阻塞队列中移除
• 将PCB改为就绪状态
• PCB插入就绪队列

4 进程同步

4.1 基本概念

（1）两种形式的制约关系

(1) 间接相互制约关系：源于某种系统资源的共享，如共享CPU、共享I/O设备等。
(2) 直接相互制约关系：源于进程间的合作，如输入进程A通过单缓冲向进程B提供数据，当进程A把数据输入缓冲区后，将进程B唤醒。

（2）临界资源（Critical Resouce）：规定在一段时间内只允许一个进程(线程)访问（即需要互斥访问）的资源称为临界资源

（3）竞争状态（race condition）：两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况

解决办法：在同一时刻，只允许一个进程访问该共享数据，如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问

（4）临界区

每个进程中访问临界资源的那段代码称为临界区(critical section)

进程在进入临界区之前，先检查临界资源，看是否正被访问：若未被访问，进程便可进入临界区，并设置临界资源正被访问的标志；若正被其他进程访问，则本进程不能进入临界区

访问临界资源的循环进程描述如下：
while(TRUE){
    entry section            //进入区
    critical section；     //临界区
    exit section              //退出区
    remainder section；//剩余区
    }

（5）同步机制应遵循的规则

(1) 空闲让进。任何两个进程都不能同时进入临界区。当没有任何进程处于临界区时（即临界资源处于空闲状态），才能允许一个请求进入临界区的进程立即进入自己的临界区。
(2) 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，其它试图进入临界区的进程必须等待。
(3) 有限等待。任何一个进程进入临界区的要求应该在有限时间内得到满足，以免陷入“死等”状态。
(4) 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

4.2 硬件同步机制

（1）关中断

关中断是实现互斥的最简单的方法之一。在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。这样在临界区执行时就不会响应中断，引发调度。

（2）利用Test-and-Set指令实现互斥

这是一种借助一条硬件指令——测试并建立的指令来实现互斥的方法。

进程在进入临界区之前，首先用TS指令测试lock，如果为FALSE则表示可进入，并将TRUE值赋值给lock

该指令的一般性描述

boolean TS(boolean *lock){
boolean old;
old=*lock;
*lock=TRUE;//true表示资源正在被占用，false表示空闲
return old;
}
//该指令是原语，不可被分割

（3）利用Swap指令实现进程互斥

该指令称为对换指令

一般性描述

void swap(boolean *a,boolean *b)
{
	boolean temp;
	temp=*a;
	*a=*b;
	*b=temp
}

总结：利用上述硬件指令能有效的实现进程的互斥，但当临界资源忙碌时，其他访问进程必须不断地进行测试，处于一种忙等状态，不符合让权等待的原则，同时很难将它们用于解决复杂难度的进程同步问题。

4.3 信号量机制（P、V操作）

（1)整型信号量

把整型信号量定义为一个用于表示资源数目的整型量S

信号量S与一般整型量不同，由操作系统维护，用户进程只能通过初始化和标准的原子操作wait(S)和signal(S)访问它。
初始化S即指定S等于空闲资源的总数。

原子操作wait(S)和signal(S)被分别称为P操作和V操作。

缺陷：若信号量S<=0，就会不断地进行测试。因此，该机制并未遵循让权等待的原则。会使进程处于忙等的状态。

void wait（S）
{     
      while(S<=0);         //当S<=0时，会不断测试。未处理好
       S--;  
} 
void signal（S）
{     
       S++;  
} 

（2）记录型信号量

记录型信号量机制的提出是为了解决整型信号量机制 不遵循“**让权等待”**准则的问题。

在记录型型号量中，采用了一种新的数据结构，信号S就是这种新的数据结构类型

struct semaphore{
	int value;                   //表示资源数目的整型变量
	struct semaphore *list;        //进程链表指针
}

//wait(S)和signal(S)操作可描述为
//wait(S) 即P(S):表示申请一个资源
//signal(S) 即V(S):表示释放一个资源
void wait(semaphore *S)
    {
      S->value --;               //申请资源
                if(S->value<0)         //资源数不够
                        block(S->list);
    }
    void signal(semaphore *S)
    {
      S->value++;         //释放资源
      if (S->value<=0)    //有可用资源
      wakeup(S->list)；
    }

操作的优点：简单，表达能力强，可以解决任何进程同步互斥问题

操作的缺点：不够安全，操作不当会造成死锁

（3）AND信号量

前面的问题针对的是多个并发进程共享一个临界资源的情况，有些场合，一个进程往往需要获得两个或更多的共享资源后方能完成任务。

基本思想：将进程在整个运行过程中需要的所有资源，一次性、全部地分配给进程，待进程使用完后再一起释放。只要尚有 一个资源未能分配给进程，其它所有可能为之分配的资源， 也不分配给它

假定现有两个进程A和B，都要求访问共享数据D和E。此时共享数据应看作临界资源。为D和E分别设置用于互斥的信号量Dmutex和Emutex，初值均为1。对Dmutex和Emutex的操作

Process A:            Process B:
wait(Dmutex);    signal(Emutex)　
wait(Emutex);     signal(Dmutex)　

（4）信号量集

在有些情况下，为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配

几种特殊的情况

(1) Swait(S，t，d)：只有一个信号量S，每次分配d个资源，当现有资源数少于t时，不予分配。
(2) Swait(S，1，1)： 蜕化为记录型信号量。
(3) Swait(S，1，0)：下限值t=1，资源分配数量d=0
d=0：进入临界区的进程并不申请资源；
t=1：只要S≥1时，就允许多个进程进入某特定区；当S=0后，则阻止任何进程进入特定区。S相当于一个是否允许进程进入的可控开关，后续会用到这个信号量操作。

利用信号量机制需要注意的问题

（1）互斥信号量的初始值为1

（2）wait(mutex)和signal(mutex)须在同一进程中成对出现

缺少wait(mutex)会导致系统混乱，不能保证对临界资源的互斥访问

缺少signal(mutex)将会使临界资源永远不被释放，从而使等待该资源而阻塞的进程不能被唤醒

例题：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OOFDIEeU-1639932290429)(C:\Users\Gabrielle\AppData\Roaming\Typora\typora-user-images\image-20211219233400918.png)]

这7个前驱关系分别设置信号量

a（S1→S2） ，b（S1→S3），c（S2→S4） ，d（S2→S5） ，e （S3→S6） ，f （S4→S6） ，g （S5→S6）

p1() {s1 ；  signal(a)； signal(b)}
p2() { wait(a)； S2； signal(c)； signal(d)； }
p3() { wait(b)； S3； signal(e)； }
p4() { wait(c)； S4； signal(f)； }
p5() { wait(d)； S5； signal(g)； }
p6() { wait(e)； wait(f)； wait(g)； S6； }

main(){
Semaphore a,b,c,d,e,f,g;
   a.value = b.value = c.value = d.value = e.value = 0;
   f.value = g.vaule = 0;
   cobegin:
   p1();      p2();         p3();       p4();         p5();         p6();
}

5 进程的经典问题

5.1 生产者—消费者问题

• 问题描述

A版：一类进程作为生产者，生产产品，生产的产品放入一个缓冲区，消费者从缓冲区中取出产品，需要保证生产者不可以向满的缓冲区中添加产品，消费者不可以从空的缓冲区中取出产品。同一时刻只可以有一个生产者生产产品或者消费者消费产品。

Aplus版：可以实现同一个时刻既有生产者生产产品，又有消费者消费产品。但是绝对不可以同一时刻多个生产者生产产品或者多个消费者消费产品。同时使用count记录缓冲区中产品的数量。

• 问题产生

1）生产者进程和消费者进程都以异步方式运行， 但它们之间必须保持同步。

2）可利用互斥信号量实现诸进程对缓冲池的互斥使用（不可以同时既向缓冲区中放入数据，又从缓冲区中拿出数据）；利用资源信号量empty和full分别表示缓冲池中空缓冲池和满缓冲池的数量。 假定这些生产者和消费者相互等效。

• 问题解决

思路：

引入一个整型变量counter，表示缓冲池中的产品数量，初值为0：
每当生产者进程向缓冲池中投放一个产品后，使counter加1；
每当消费者进程从缓冲池中取走一个产品后，使counter减1。
生产者和消费者两进程共享下面的变量：
int n;          // 缓冲区数量
int buffer[n];  //编号是0,1,2，……，n-1的缓冲区
int in，out; //指针指向生产和消费产品的位置
int counter;         //产品数量取值范围为0,1,2，……，n
生产者进程使用一个局部变量nextp：暂时存放每次刚生产出来的产品；消费者进程使用一个局部变量nextc，用于存放每次要消费的产品。 

• 利用记录型信号量解决生产者—消费者问题

生产者与生产者之间、消费者与消费者之间一定是互斥访问缓冲池的！

int in =0, out =0;　   //in是初始生产位置，out是初始消费位置　　　　　　　　　　　　
int buffer[n]；       //缓冲区　
semaphore mutex = 1, empty = n, full = 0;
void producer()
{
    do
 {  
     生产一个产品nextp;
   wait(empty)； //空缓冲区数目≤0，则进入阻塞状态
   wait(mutex)；//测试mutex ≤0，互斥使用缓冲池       
   buffer(in):=nextp；
   in = (in+1) mod n；
   signal(mutex)；//释放缓冲池资源mutex+1
   signal(full)；//满缓冲区数目full+1
    }while(TRUE);
 }

void consumer()
{
    do
   {  
    wait(full)； //满缓冲区数目≤0，则进入阻塞状态
    wait(mutex)；/测试mutex ≤0，互斥使用缓冲池
    nextc = buffer[out];   //取得消费产品的编号
    out = (out+1) % n；
    signal(mutex)；/释放缓冲池资源mutex+1
    signal(full)；/满缓冲区数目full+1
    消费产品nextc；
   }while(TRUE);
}

• 使用AND信号量解决此问题综合代码

思路：

用Swait(empty，mutex)代替wait(empty)和wait(mutex)
用Ssignal(mutex，full)代替signal(mutex)和signal(full)
用Swait(full，mutex)代替wait(full)和wait(mutex)
用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)

void producer()
{
   do
   {  
     生产一个产品nextp;
    Swait(empty,mutex)； //同时申请两个信号量
    buffer(in):=nextp；
    in = (in+1) mod n；
    Ssignal (empty,mutex) ;
    }while(TRUE);
}

void consumer()
{
    do
   {  
    Swait(full,mutex)； //同时申请两个信号量
    nextc = buffer[out];   //取得消费产品的编号
    out = (out+1) % n；
    Ssignal(mutex,full)；// 同时释放两个信号量
    消费产品nextc；
    }while(TRUE);
}

attention：

1）每个程序的互斥操作wait（）和signal（）必须成对的出现。

2）输入进程不可以向满的缓冲池中输入数据，计算进程不可以从空的缓冲池中取数据

3）在每个程序中的多个wait操作顺序不能颠倒，必须先执行对资源信号量的wait操作，在进行对互斥信号量的wait操作，否则可能引起进程死锁。

4）可以使用三个互斥信号量mutex、mutex1、mutex2实现同一时刻既有生产者生产，又有消费者消费。

5.2 哲学家就餐问题

• 问题描述

五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

• 问题

假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限等待。进入死锁状态。

• 解决

至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐

• 利用记录型信号量解决哲学家进餐问题

semaphore chopstick[5] = {1,1,1,1,1}； 

第i位哲学家的活动可描述为：
do
wait(chopstick[i])；/左边的筷子是否可拿  
wait(chopstick[(i+1)mod 5])；/右边的筷子是否可拿
eat；
signal(chopstick[i])；/放下左边的筷子 
signal(chopstick[(i+1)mod 5])；/放下右边的筷子
think；
while(TRUE);

• 使用AND信号量机制解决此问题

要求每个哲学家同时获得两个临界资源(左右筷子)后方能进餐，本质上就是前面所介绍的AND同步问题：

semaphore chopstick= {1,1,1,1,1}；
void philosopher() {
        do{
          think；
          Sswait(chopstick[(i+1)mod 5]，chopstick[i])；
          eat；
          Ssignal(chopstick[(i+1)mod 5]，chopstick[i])；
          }while(TRUE);
      }

5.3 读者—写者问题

• 问题描述

该问题涉计两类进程，第一类进程是读进程Reader，另一类进程是写进程Writer，多个读进程可以同时读一个文件（共享资源），多个写的进程不可以同时写一个文件（对写互斥），并且读的时候不能写，写的时候不能读（对读互斥）

• 问题核心

保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。

只要求读文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。

允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象（共享对象并不是临界资源，因为他允许多个进程对其访问）

• 使用记录型信号量

semaphore  rmutex=1，wmutex = 1；
int Readcount = 0；/正在读的进程数目为0

void Reader(){
        do{
             wait(rmutex)；//读进程对Readcount的互斥访问
             if Readcount=0 then wait(wmutex)；
             Readcount:=Readcount+1；
             signal(rmutex)； 

             perform read operation；//执行读操作

             wait(rmutex)；//读完后再对Readcount互斥访问
             Readcount=Readcount-1；
             if(Readcount=0) signal(wmutex)；//若无进程在读，则允许写
             signal(rmutex)；
          }while(TRUE);
               }

 void writer(){
           do{
  　　            wait(wmutex)；/是否有进程在读或者写
  　　            perform write operation； 
  　　            signal(wmutex)；
  　　        }while(TRUE);
  　　           }

• 使用信号量集机制

int RN;
semaphore  L = RN，mx = 1；/ /mx是写进程的信号

void reader()
{
 do{
         Swait(L,1,1)；//判断读进程个数是否满L
         Swait(mx,1,0)；//开关: 无写进程，就可进入读

         perform read operation；

         Ssignal(L,1)；//退出读
   } while(TRUE);
}

void writer(){　　　　　　　　　
    do{
            Swait(mx,1,1；L,RN,0)；//既无写又无读
            perform write operation；
            Ssignal(mx,1)；
      }while(TRUE);　　　　　
             }

6 进程通信

6.1 进程通信概念

进程通信是指进程之间的信息交换

6.2 低级通信和高级通信

低级通信——进程互斥和同步中，仅通过信号量传递临界资源是否可用的信息

低级通信：只能传递状态和整数值

关键词：信号量

高级通信——用户可直接利用操作系统提供的一组通信命令高效地传送大量数据的通信方式

高级通信：能够传送任意数量的数据

分为四大类：

共享存储器（shared memory）
消息传递（message passing）
管道（pipe）
客户机-服务器系统

6.3 进程通信的类型

（1）共享存储器系统Shared—Memory System

• 基于共享数据结构的通信方式

要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。如：生产者—消费者问题中，就是用有界缓冲区这种数据结构来实现通信。
公用数据结构的设置及对进程间同步的处理，都是程序员的职责,操作系统只提供共享存储器。这增加了程序员的负担，并且只能传递相对少量的数据，较低效。

• 基于共享存储区的通信方式

为了传输大量数据，在存储器中划出了一块共享存储区，诸进程通过对共享存储区中数据的读或写来实现通信。这种通信方式属于高级通信。
进程在通信前，先向系统申请获得共享存储区中的一个分区，并指定该分区的关键字；申请者把获得的共享存储分区连接到本进程上；此后便可像读、写普通存储器一样地读、写该公用存储分区。

（2）管道通信

管道机制必须提供三方面的协调能力：

（1）互斥
（2）同步
（3）确定对方是否存在

管道是指用于连接一个读进程和一个写进程以实现它们之间通信的一个打开的共享文件（pipe文件）。向管道提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；接受管道输出的接收进程(即读进程)，则从管道中按先进先出的顺序接收(读)数据。
管道的读写操作即为文件操作fwrite/fread，数据流的长度和格式没有限制

（3）消息传递系统

消息传递系统的通信方式属于高级通信方式

消息传递系统(Message passing system)是当前应用最为广泛的一种进程间的通信机制。该机制中，进程间的数据交换是以格式化的消息为单位的。程序员直接利用操作系统提供的一组通信命令(原语)，不仅能实现大量数据的传递，而且还隐藏了通信的实现细节，使通信过程对用户是透明的，从而大大减化了通信程序编制的复杂性，因而获得广泛的应用

（4）客户机-服务器系统

已经成为主流通信机制，实现方法三类

(1) 嵌套字(Socket)
(2) 远程过程调用
(3) 远程方法调用

6.4 消息传递通信的实现方法

在进程之间通信时，源进程可以直接或者间接将消息送给目标进程，因此可以将进程通信分为直接和间接两种通信方式

直接通信方式：直接消息传递系统
间接通信方式：信箱通信

（1）直接消息传递系统

发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。

（1)直接通信原语:系统提供发送消息原语send和接收消息原语receive;对称寻址方式和非对称寻址方式
（2）消息格式：所传递的消息，必须具有一定的格式
（3）进程的同步方式：需要有进程同步机制，以使进程之间能协调通信
（4）通信链路：发送进程和接收进程能进行通信，它们之间必须存在一条通信链路

（2）信箱通信

进程之间的通信，需要通过某个中间实体(如某个共享数据结构等）来完成。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体称为信箱

通信机制包括：

* 信箱的结构
* 信箱通信原语
*  信箱的类型

• 私用信箱

用户进程可为自己建立一个新信箱，作为进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。当拥有该信箱的进程结束时，信箱也随之消失

• 公用信箱

由操作系统创建，提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。公用信箱在系统运行期间始终存在

• 共享信箱

由某进程创建，但创建时指明该信箱是共享型的，并指出共享进程的名字

7 线程的基本概念

7.1进程 两个基本属性

① 进程是一个可拥有资源的独立单位；
② 进程是一个可独立调度和分派的基本单位

7.2 线程和进程的比较

（1）调度的基本单位

进程 ＝ 线程 ＋ 资源平台

进程把一组相关的资源组合起来，构成了一个资源平台（环境），包括地址空间（代码段、数据段）、打开的文件等各种资源
线程是在这个资源平台上的一条执行流程（线程）

进程作为资源拥有的基本单位，线程作为调度和分派的基本单位。线程基本上不拥有资源，显著提高系统的并发程度。

同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换

（2）并发性

引入线程的操作系统中，不仅进程之间可以并发执行，一个进程中的多个线程之间亦可并发执行。

（3）拥有资源

线程基本不拥有系统资源（只有一点必不可少的资源如线程控制块）但可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O设备等，可以供该进程中的所有线程所共享

（4）独立性

在同一进程中的不同线程之间的独立性要比不同进程之间的独立性地

（5）系统开销

线程创建、切换或撤消时的开销远小于进程。

（6）支持多处理机系统

传统的进程，即单线程进程，不管有多少个处理器，该进程也只能在一个处理器上工作。对于多线程进程，可以将一个进程中的多个线程分配到多个处理器上，使它们并行工作，加速进程的完成

7.3 线程的实现

（1）内核支持线程

内核支持线程在内核的支持下运行，它们的创建，阻塞，撤销和切换等，都是在内核空间实现的

优点：

(1)在多处理器系统中，可以同时调度同一进程的多个线程并行执行；
(2)如果某个线程被阻塞，内核可以调度该进程中其他线程占用处理器运行，也可以运行其他进程的线程
(3)切换快，开销小
(4)内核本身可采用多线程技术，提高系统的执行速度和效率

实现方式：

系统在创建一个新进程时，便为它分配一个任务数据区PTDA (Per Task Data Area)——包括若干个线程控制块TCB空间。每一个TCB中可存放线程标识符、优先级、线程运行状态等信息，这些信息被保存在内核空间中

PTDA 进程资源
TCB #1
TCB #2
TCB #3

(3)用户级线程ULT(User Level Threads)

用户级线程ULT(User Level Threads)仅存在于用户空间，线程的调度与管理（如创建、撤消、同步、通信等）无须利用系统调用实现，与内核无关（内核完全不知道ULT的存在） 。用户级线程的切换由进程完成，不需要转换到内核空间，速度特别快。不同进程可以根据自身需要，选择不同的调度算法对自己的线程进行管理和调度，与操作系统的调度算法无关

优点：

(1)线程切换不需要转换到内核空间。节约了模式切换的开销。
(2)线程之间调度算法可以是进程专用，与操作系统的低级调度算法无关。
(3)用户级线程的实现与OS无关。所以用户级线程可以在不支持线程的操作系统平台上实现。

（3）组合

有些操作系统把用户级线程和内核支持线程两种方式进行组合，提供了组合方式ULT/KST 线程。内核既支持KST线程的建立、调度和管理，也允许用户应用程序建立、调度和管理用户级线程

独立性

在同一进程中的不同线程之间的独立性要比不同进程之间的独立性地

（5）系统开销

线程创建、切换或撤消时的开销远小于进程。

（6）支持多处理机系统

传统的进程，即单线程进程，不管有多少个处理器，该进程也只能在一个处理器上工作。对于多线程进程，可以将一个进程中的多个线程分配到多个处理器上，使它们并行工作，加速进程的完成

7.3 线程的实现

（1）内核支持线程

内核支持线程在内核的支持下运行，它们的创建，阻塞，撤销和切换等，都是在内核空间实现的

优点：

(1)在多处理器系统中，可以同时调度同一进程的多个线程并行执行；
(2)如果某个线程被阻塞，内核可以调度该进程中其他线程占用处理器运行，也可以运行其他进程的线程
(3)切换快，开销小
(4)内核本身可采用多线程技术，提高系统的执行速度和效率

实现方式：

系统在创建一个新进程时，便为它分配一个任务数据区PTDA (Per Task Data Area)——包括若干个线程控制块TCB空间。每一个TCB中可存放线程标识符、优先级、线程运行状态等信息，这些信息被保存在内核空间中

PTDA 进程资源
TCB #1
TCB #2
TCB #3

(3)用户级线程ULT(User Level Threads)

用户级线程ULT(User Level Threads)仅存在于用户空间，线程的调度与管理（如创建、撤消、同步、通信等）无须利用系统调用实现，与内核无关（内核完全不知道ULT的存在） 。用户级线程的切换由进程完成，不需要转换到内核空间，速度特别快。不同进程可以根据自身需要，选择不同的调度算法对自己的线程进行管理和调度，与操作系统的调度算法无关

优点：

(1)线程切换不需要转换到内核空间。节约了模式切换的开销。
(2)线程之间调度算法可以是进程专用，与操作系统的低级调度算法无关。
(3)用户级线程的实现与OS无关。所以用户级线程可以在不支持线程的操作系统平台上实现。

（3）组合

有些操作系统把用户级线程和内核支持线程两种方式进行组合，提供了组合方式ULT/KST 线程。内核既支持KST线程的建立、调度和管理，也允许用户应用程序建立、调度和管理用户级线程