第二章进程的描述与控制

2023年12月3日发(作者：)

第二章进程的描述与控制第二章 进程的描述与控制2.1 前趋图和程序执行2.1.1 前趋图定义定义：所谓前趋图，是指一个有向无循环图，可记为DAG.*进程（或程序）之间的前趋关系可用“ → ”来表示。*每个节点还具有一个重量，用于表示该节点所含有的程序量或程序的执行时间。*前驱图中不允许循环。2.1.2 程序顺序执行程序的顺序执行程序顺序执行时的特征 - I代表输入操作。 C代表计算机操作。 P为打印操作。 - ①顺序性： 每一操作必须在下一操作开始之前结束 ②封闭性： 程序运行时独占全机资源，资源的状态（除出始状态外）只由本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响。 ③可再现性： 只要程序执行时的环境和初始条件相同，都可以获得相同结果。2.1.3 程序并发执行程序的并发执行程序并发执行时的特征 ☞ 多道程序的优点：增加了CPU的利用率和作业吞吐量。 ✦与单道程序相比，多道程序的工作环境变化主要表现在： 1>资源共享 2>程序的并发执行☞并发执行的特性： ①间断性 ②失去封闭性 ③不可再现性：程序执行时的环境和初始条件相同，但结果可能不相同。2.2进程的描述2.2.1 进程的定义和特征进程的定义进程的特征1.进程控制块（PCB）：为了使参与并发执行的每个程序（含数据）都能独立的运行， 在操作系统中必须为之配置一个专门的数据结构。称之为进程控制块。2.进程的定义： （1）进程是程序的一次执行。 （2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 ★（3）进程是具有独立功能的程序在一个数据集合上的运行的过程，它是系统 进行资源调度和分配的一个独立单位。 （4）在引入进程实体之后，我们可以把传统OS中的进程定义为： ※进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 进程 = PCB + 程序段 + 数据段3.进程的特征： （1）动态性 （2）并发性 （3）独立性 （4）异步性4.进程与程序的区别和联系： 进程：是程序的一次执行，是动态概念。一个进程可以同时包括多个程序； 进程是暂时的，是动态的产生和消亡的。 程序：是一组有序的静态指令，是静态概念。一个程序可以是多个进程的 一部分；程序可以作为资料长期保存。2.2.2 进程的基本状态及转换进程的三种基本状态三种基本状态的转换创建和终止状态1.（1）就绪状态：这是指进程已处于准备好运行的状态，即进程已分配到处CPU以外的所有必要资源后，只要在获得CPU，便可立即执行。 （2）执行状态：指进程以获得CPU，其程序正在执行的状态。 （3）阻塞状态：这是指正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行的状态，亦即进程执行受到阻塞。2.进程三种状态/五种状态的基本转换。 - -- -见课本P37详解。

2.2.3挂起操作和进程状态的转换挂起操作的引入引入挂起原语操作后三个进程状态的转换引入挂起操作后五个进程状态的转换1.挂起操作的引入： （1）终端用户的需要 （2）父进程请求 （3）负荷调节的需要 （4）操作系统的需要2.三个状态的转换： （1）活动就绪 → 静止就绪 （2）活动阻塞 → 静止阻塞 （3）静止就绪 → 活动就绪 （4）静止阻塞 → 活动阻塞 ————见P39图2-73.五个状态的转换： （1）NULL → 创建 （2）创建 → 活动就绪 （3）创建 → 静止就绪 （4）执行 → 终止2.2.4 进程管理中的数据结构操作系统中用于管理控制的数据结构进程控制块PCB的作用进程控制块的信息进程控制块的组织方式1.在计算机系统中，对于每个资源和每个进程都设置一个数据结构， 用于表征其实体，我么们称之为（资源信息表）或（进程信息表）。

▶OS管理这些数据结构一般分为四类：内存表、设备表、文件表和进程表。 ▶见P39 图2-9 操作系统控制表的一般结构。作用： （1）作为独立运行基本单位的标志 （2）能实现间断性的运行标志 （3）提供进程管理所需要的信息 （4）提供进程调度所需要的信息 （5）实现与其他进程的同步与通信3.进程控制块中的信息： （1）进程标识符 ①外部标识符。方便用户对进程的访问 ②内部标识符。方便系统对进程的使用 （2）处理及状态 处理机状态信息也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成的。 这些寄存器包括： ①通用寄存器 ②指令计数器 ③程序状态字PSW ④用户栈指针

（3）进程调度信息 ①进程状态，指明进程的当前状态，它是作为进程调度和对换时的依据。 ②进程优先级，是用于描述进程使用处理机的优先级别的一个整数。 ③进程调度所需要的其他信息，它们与所采用的进程调度算法有关。 ④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

（4）进程控制信息 ①程序和数据的地址，进程实体中的程序和数据的内存或外存地址， 以便在调度到改进程时，能从PCB中找到其程序和数据。 ②进程同步和通信机制，这是实现进程同步和进程通信时必需的机制。 ③资源清单，在该清单中列出了进程在运行期间所需要的全部资源，另外 还有一张已分配到该进程的资源的清单。4.进程控制块的组织方式： ④链接指针，他给出本进程（PCB）所在队列的下一个进程的PCB的首地址。 ①线性方式 ②链接方式 ③索引方式 ——见P42中详细介绍。2.3进程控制2.3.1 操作系统内核大多数操作系统内核包括两大方面的内容：支撑功能资源管理功能通常将处理机的执行状态分为系统状态和用户状态两种。 ①系统态：又称为管态，也称为内核态。 ②用户态：又称为目态。1.支撑功能： （1）中断处理 （2）时钟管理 （3）原语操作2.资源管理功能： （1）进程管理 （2）存储器管理 （3）设备管理2.3.2 进程的创建进程的层次结构进程图引起创建进程的事件进程的创建进程的层次结构： 通常，把创建进程的进程成为--父进程；把被创建进程的进程成为子进程。 在UNIX中，进程与其子孙进程共同组成一个进程家族（组）。 但在Windows中不存在任何进程层次结构的概念。引起进程创建的事件： （1）用户登录 （2）作业调度 （3）提供服务 （4）应用请求进程的创建： （1）申请空白PCB为新进程申请获得唯一的数字表示符，并从PCB集合中索取一个空白PCB。 （2）为新进程分配其运行所需的资源。 （3）初始化进程控制块 （4)如果程序就绪队列能够接纳新进程，便将新进程插入就绪队列。2.3.3 进程的终止引起进程终止的事件进程终止的过程引起进程终止的事件： （1）正常结束。 （2）异常结束： ①越界错，这是指程序所访问的存储区，已越出该程序的区域。 ②保护错，指进程试图去访问一个不允许访问的资源或文件。或者以不适当的方式进行访问。 ③非法指令，指程序试图去执行一个不存在的指令。 ④特权指令错，指用户进程试图去执行一条只允许OS执行的指令。 ⑤运行超时，指进程的执行时间超过了指定的最大值。 ⑥等待超时，指进程等待某事件的时间超过了规定的最大值。 ⑦算术运算错，指进程试图去执行一个被禁止的运算。（３）外界干预：① ② ③进程终止的过程：（１）根据被终止进程的标识符，从PCB集合中j检索出该进程的PCB，从中读出该进程的状态。（２）若被终止的进程的处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。（３）若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以方他们成为不可控的进程。（４）将被终止的进程所拥有的全部资源或者归还其父进程，或者归还给系统。（５）将被终止的进程（PCB）从所在的队列（或链表）中移除，等待其它程序来搜集信息。2.3.4 进程的阻塞与唤醒引起进程阻塞和唤醒的事件进程阻塞过程进程唤醒过程有下述几类事件会引起进程阻塞或被唤醒： （1）向系统请求共享资源失败。 （2）等待某种操作的完成 （3）新数据尚未到达 （4）等待新任务的到达2.3.5 进程的挂起与激活进程的挂起进程的激活过程2.4 进程同步2.4.1 进程同步的基本概念两种形式的制约关系临界资源临界区同步机制应遵循寻的规则两种形式的制约关系：（1）间接相互制约关系（2）直接相互制约关系临界资源：临界区：---人们把每个进程中访问临界资源的那段代码成为临界区。可以把一个访问临界资源的循环过程描述如下： while（TRUE）{ 进入区 临界区 退出区 剩余区 }同步机制应遵循的规则

（1）空闲让进（2）忙则等待（3）有限等待（4）让权等待2.4.2 硬件同步机制关中断利用Test-And-Set指令实现互斥利用Swap指令实现进程互斥1.关中断是实现互斥的最简单的方法之一。缺点：①滥用关中断权力会导致严重后果②关中断时间过长，会影响系统效率。限制处理器交叉执行的能力③关中断方法也不适用于多CPU系统2.4.3 信号量机制整形信号量记录型信号量AND型信号量信号量集2.4.4 信号量的应用利用信号量实现进程互斥利用信号量实现前驱关系2.4.5 管程机制管程的定义条件变量1.管程的定义： 代表共享资源的数据结构以及由对该共享数据结构实时操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，我们称之为管程。 - 管程可分为四部分： ①管程的名称 ②局部于管程的共享数据结构说明 ③对该数据结构进行操作的一组进程 ④对局部于管程的共享数据结构设置初始值的语句3.从语言角度看，管程有以下特征： ①模块化，即管程是一个基本程序单位，可以单独编译。 ②抽象数据类型，指管程中不仅有数据，还有对数据的操作。 ③信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程是也是在管程内部定义的供管程外的进程调用，而管程的中的数据结构以及过程（函数）的具体实现外部不可见。4.管程和进程的不同： ①虽然二者都定义了数据结构，但进程定义的是‘私有’的数据结构PCB,管程定义的是‘公共‘数据结构。 ②二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关操作，而管程主要进行同步操作和初始化操作。 ③设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题。 ④进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子进程一样被调用，因而管程为被动工作方式，进程则为主动工作方式。 ⑤进程之间能并发执行,而管程不能与其调用者并发。 ⑥进程具有动态性，由“创建”而诞生，由“撤销”而消亡。而管程则是操作系统中的一个资源管理模块，供进程调用。2.5经典进程的同步问题2.5.1 生产者-消费者问题利用记录型信号量解决生产者-消费者问题利用AND信号量解决生产者-消费者问题利用管程解决生产者-消费者问题2.5.2哲学家进餐问题利用记录型信号量解决哲学家进餐问题利用AND信号量解决哲学家进餐问题2.5.3 读者-写者问题利用记录型信号量解决读者-写者问题利用信号量集机制解决读者-写者问题2.6 进程通信2.6.1 进程通信的类型共享存储器系统管道通信系统消息传递系统客户机-服务器系统进程通信是指进程之间的信息交换。在进程之间要传送大量数据时，应当利用OS提供的高级通信工具，该工具最主要的特点是： （1）使用方便 （2）高效地传送大量数据共享存储器系统： （1）基于共享数据结构的通信方式。 （2）基于共享存储区的通信方式。管道通信系统： 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间的通信的一个共享文件，又名pipe文件。管道机制必须提供三种协调机制 ： ①互斥 ②同步 ③确定对方是否存在，只有确定对方已存在时才能进行通信。消息传递系统： 消息传递系统的通信方式属于高级通信方式： （1）直接通信方式 （2）间接通信方式客户机-服务器系统： （1）套接字 一个套接字就是一个通信标识类型的数据结构 套接字包括两类： ①基于文件型 ②基于网络型 （2）远程过程调用和远程方法调用 远程过程调用是一个通信协议，用于通过网络连接的系统。2.6.2 消息传递通信的实现方式直接消息传递系统信箱通信直接消息传递系统： （1）直接通信原语 ①对称寻址方式 send（receiver，message） 发送一个消息给接收进程 receive（sender，message） 接收Sender发来的消息 ②非对称寻址方式 send（P，message） 发送一个消息给进程P。 receive（id，message） 接收来自任何进程的消息，id变量可设置为进行通信的发送方进程的id或名字。 （2）消息的格式 （3）进程的同步方式 ①发送进程阻塞，接收进程阻塞。 ②发送进程不阻塞，接收进程阻塞。 ③发送进程和接收进程均不阻塞。 （4）通信链路 1.有两种方式建立通信链路： 第一种方式 ---

第二种方式 ---

2.链路可分为两种： ①单向通信链路 ②双向通信链路1.信箱通信属于间接通信方式，即进程之间的通信，需要通过某种中间实体（如共享数据结构等）来完成。 - ✦信箱的结构 （1）信箱头 （2）信箱体 ✦信箱通信原语 （1）邮箱的创建和撤销。 （2）消息的发送和接收。 Send（mailbox，message） 将一个消息发送到指定邮箱 Receive（mailbox,message）从指定邮箱中接收一个消息 ✦信箱的类型 （1）私用邮箱 （2）公用邮箱 （3）共享邮箱 ①一对一关系 ②多对一关系 ③一对多关系 ④多对多关系2.6.3 直接消息传递系统实例消息缓冲队列通信中的数据结构发送原语接收原语1.消息缓冲队列通信中的数据结构 （1）消息缓冲区 （2）PCB中有关通信的数据项2.7 线程的基本概念2.7.1 线程的引入进程的两个基本属性程序并发执行所需要付出的时空开销线程—作为调度和分派的基本单位1.两个基本属性： （1）进程是一个可拥有资源的独立单位。 （2）进程同时又是一个可独立调度和分派的基本单位。2.程序并发执行所需要付出的时空开销： (1) 创建进程 （2）撤销进程 （3）进程切换2.7.2 线程与线程的比较调度的基本单位并发行拥有资源独立性系统开销支持多处理系统2.7.3线程的状态和线程控制块线程运行的三个状态线程控制块TCB多线程OS中的进程属性1.三个状态： 执行状态 就绪状态 阻塞状态: （1）线程控制标识符 （2）一组寄存器 （3）线程运行状态 （4）优先级 （5）线程专有存储区 （6）信号屏蔽 （7）堆栈指针3.进程属性: （1）进程是一个可拥有资源的基本单位。 （2）多个线程可并发执行。 （3）进程已不是可执行的实体。2.8 线程的实现2.8.2 线程的实现方式内核支持线程KST用户级线程ULT组合方式2.8.2 线程的实现内核支持线程的实现用户级线程的实现2.8.3线程的终止和创建线程的创建线程的终止