操作系统第2章进程与线程

1、第2章 进程与线程进程是资源分配的基本单位，也是独立运行的基本单位。2.1 进程的引入 为了描述并发程序执行时的特征，引入了进程。 2.1.1 前趋图前趋图是一个有向无循环图，用于描述程序、程序段或语句执行的先后次序。图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存在的前趋关系“”：=(Pi，Pj)Pi必须在Pj开始执行之前完成前趋图中的各类结点如果(Pi，Pj)，可以写成PiPj，则称Pi是Pj的直接前趋，Pj是Pi的直接后继。若存在一个序列PiPjPk，则称Pi是Pk的前趋。在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。 前趋图例

2、S1S2S3S6S4S52.1.2 程序的顺序执行 一个程序通常由若干个程序段所组成，它们必须按照某种先后次序来执行，仅当前一个操作执行完后才能执行后继操作，这类计算过程就是程序的顺序执行过程。例如：先输入再计算最后输出，即：IC P。程序顺序执行时的特征 顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一个操作必须在下一个操作开始之前结束。封闭性：程序一旦开始运行，其执行结果不受外界因素影响。可再现性：只要程序执行时的初始条件和执行环境相同，当程序重复执行时，都将获得相同的结果。 2.1.3 程序的并发执行及特点程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序

3、段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。程序并发执行例进程1、2、3并发执行。对每个进程而言，其输入、计算和输出这三个操作必须顺序执行。它们之间存在如下先后关系：I1先于C1和I2 ， C1先于P1和C2 ， P1先于P2I2和C1 ， I3、 C2和P1可以并发。I1I2I3C1C3C2P1P2程序并发执行时的特征 间断性：并发程序具有“执行-暂停-执行”这种间断性的活动规律。失去封闭性：多个程序共享系统中的资源，这些资源的状态将由多个程序来改变，致使程序之间相互影响。不可再现性：在初始条件相同的情况下，程序的执行结果依赖于执行的

4、次序。与时间有关的错误例程序并发执行时可能出现与时间有关的错误。例 进程1：r1=x； 进程2：r2=x； r1+； r2+； x=r1； x=r2；设在两进程运行之前，x的值为0。则两进程运行结束后，x值可为：1 22.1.4程序并发执行的条件读集：语句执行期间要引用的变量集合，记为R（Si）=a1，am写集：语句执行期间要改变的变量集合，记为W（Si）=b1，bnBernstein条件Bernstein条件能保证两个程序段并发执行而不会产生与时间有关的错误：R（Si） W（Sj）= 这两条保证R（Sj） W（Si）= 两次读之间数据不变W（Si） W（Sj）= 本条保证写操作结果不丢例考虑

5、下面是条语句： S1：a=x+y S2：b=z+1 S3：c=a-b S4：d=c+1R(S1)=x,y R(S2)=z R(S3)=a,b W(S1)=a W(S2)=b W(S3)=c因R(S1) W(S2)R(S2) W(S1)W(S1)W(S2)= ，故S1和S2可以并发执行 。 因R(S2) W(S3)R(S3) W(S2)W(S3)W(S2)=b，故S2和S3不能并发执行 。 并发语句的描述方式cobegin S1；S2；Sn； coend对应的前趋图如右，其中S0和Sn+1分别是cobegin和coend语句前后的两条语句。S0S1S2SnSn+12.2 进程的定义及描述为了描述

6、并发执行程序的动态特性，人们引入了一个新的概念进程。2.2.1 进程的定义进程有多种定义，下面列举一些有代表性的定义：进程是程序在处理器上的一次执行过程。进程是可以和别的计算并行执行的计算。进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。 2.2.2 进程的特征动态性：进程是程序的一次执行过程。动态性还表现为它因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡。而程序是静态实体。并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。独立性：在传统OS中，进程是独立运行的基本单位，也是系统分配

7、资源和调度的基本单位。异步性：也叫制约性，进程以各自独立的不可预知的速度向前推进。结构性：进程实体由程序段、数据段及进程控制块组成，又称为进程映像。2.2.3 进程与程序的关系进程是动态概念，程序是静态概念；进程是程序在处理机上的一次执行过程，而程序是指令的集合。进程是暂时的，程序是永久的。进程是一个状态变化的过程；程序可以长久保存。进程与程序的组成不同。进程的组成包括程序、数据和进程控制块。进程与程序是密切相关的。一个程序可以对应多个进程；一个进程可以包括多个程序。进程可以创建新进程，而程序不能形成新程序。2.2.4 进程控制块PCB是描述和管理进程的数据结构。它是进程实体的一部分，操作系统

8、通过PCB感知进程的存在，PCB是进程存在的唯一标志。不同操作系统中进程控制块的结构不同，但通常包括下面所列出的内容：PCB包含的内容1进程标识符：惟一标识进程的一个标识符或整数。进程当前状态：说明进程当前所处状态。进程队列指针：用于记录PCB队列中下一个PCB的地址。程序和数据地址：进程的程序和数据在内存或外存中的存放地址。进程优先级：反映进程获得CPU的优先级别。PCB包含的内容2CPU现场保护区：CPU现场信息的存放区域，包括：通用寄存器、程序计数器、程序状态字等。通信信息：进程与其他进程所发生的信息交换。家族关系：指明本进程与家族的关系，如父子进程标识。资源清单：列出进程所需资源及当前

9、已分配资源。2.3 进程的状态及转换为了刻画进程的动态特征，可以将进程的生命期划分为一组状态，用这些状态来描述进程的活动过程。通常，一个进程至少应有以下三种基本状态：就绪状态执行状态阻塞状态2.3.1 进程的三种基本状态就绪状态：进程已获得除处理机以外的所有资源，一旦分配了处理机就可以立即执行。执行状态：又称运行状态。一个进程获得必要的资源并正在处理机上执行。阻塞状态：又称等待状态、睡眠状态。正在执行的进程，由于发生某事件而暂时无法执行下去（如等待输入/输出完成）。这时即使把处理机分配给该进程，它也无法运行。 进程状态转换图执行就绪阻塞进程调度时间片用完等待事件事件发生2.3.2 新建状态和终

10、止状态在许多系统中又增加了两种状态：新建状态：进程刚刚建立，但还未进入就绪队列。又称创建状态。终止状态：当一个进程正常或异常结束，操作系统已释放它所占用的资源，但尚未将它撤消时的状态，又称退出状态。五状态的进程状态转换图运行就绪等待进程调度时间片用完等待事件事件发生新建终止接纳完成状态转换的有关说明大多数状态不可逆转，如等待不能转换为运行。状态转换大多为被动进行，但运行等待是主动的。一个进程在一个时刻只能处于上述状态之一。2.3.3 进程的挂起状态 在某些系统中，希望人为将进程挂起使之处于静止状态。进程挂起的原因有：系统故障或功能受到破坏：先挂起，故障消除后再恢复。检查中间结果：挂起进程以便检

11、查。资源不足：挂起进程以腾出资源。内存不足：在外存挂起。有挂起状态的进程状态转换图基于上述原因，需引入一个新的状态：挂起状态。执行进程调度时间片完活动就绪等待事件挂起事件发生挂起激活活动阻塞挂起就绪挂起阻塞挂起激活事件发生创建退出接纳接纳完成2.4 进程控制和管理进程控制的职能是对系统中的所有进程实施有效的管理。常见的进程控制功能有进程创建、撤消、阻塞与唤醒等。这些功能一般由操作系统内核原语来实现。操作系统内核在操作系统设计中，往往把一些与硬件紧密相关的模块、运行频率较高的模块及公用的一些基本操作安排在靠近硬件的软件层次中，使它们常驻内存，以提高操作系统的运行效率，通常把这部分软件称为操作系统

12、内核。内核主要包括：中断时钟管理进程管理存储器管理设备管理原语原语是由若干条机器指令构成的，用以完成特定功能的一段程序，这段程序在执行期间不可分割。计算机系统的两种运行状态核心态：又称管态、系统态，是操作系统管理程序执行时机器所处的状态。这种状态具有较高的特权，能执行一切指令，访问所有的寄存器和存储区。用户态：又称目态，是用户程序执行时机器所处的状态。这种状态具有较低特权，只能执行规定的指令，访问指定的寄存器和存储区。2.4.1 进程创建为描述进程之间的创建关系，引入了进程图。进程图又称进程树或进程家族树，是描述进程家族关系的一棵有向树。图中的结点表示进程，若进程A创建了进程B，则从结点A有一

13、条边指向结点B，说明进程A是进程B的父进程，进程B是进程A的子进程。 进程图例ABCDEF进程创建原语导致进程创建的原因有：用户登录：用户登录后，若合法则为用户创建一个进程。作业调度：为调度到的作业分配资源并创建进程。OS服务：创建服务进程。应用需要：应用程序根据需要创建子进程。创建原语的主要功能进程创建原语的功能是创建一个新进程，其主要操作过程如下：向系统申请一个空闲PCB。为新进程分配资源。如分配内存空间。初始化新进程的PCB。在其PCB中填入进程名、家族信息、程序和数据地址、进程优先级、资源清单及进程状态等。将新进程的PCB插入就绪队列。2.4.2 进程撤销引起进程撤销的原因有：正常结束

14、异常结束：超时、内存不足、地址越界、算术错、I/O故障、非法指令等。外界干预：包括操作员或系统干预，父进程请求。撤消原语采用的两种策略撤消原语采用的两种策略：撤消指定标识符的进程撤消指定进程及其所有子孙进程下面给出后一种撤消策略的功能描述。 撤消原语的主要功能撤消原语的功能是撤消一个进程，其主要操作过程如下：从系统的PCB表中找到被撤消进程的PCB。检查被撤消进程的状态是否为执行状态，若是则立即停止该进程的执行，设置重新调度标志。检查被撤消进程是否有子孙进程，若有子孙进程还应撤消该进程的子孙进程。回收该进程占有的全部资源并回收其PCB。2.4.3 进程阻塞与唤醒引起进程阻塞及唤醒的事件：请求系

15、统服务。如请求分配打印机，但无空闲打印机则进程阻塞；当打印机重又空闲时应唤醒进程。启动某种操作并等待操作完成。如启动I/O操作，进程阻塞；I/O完成则唤醒进程。等待合作进程的协同配合。如计算进程尚未将数据送到缓冲区，则打印进程阻塞；当缓冲区中有数据时应唤醒进程。系统进程无新工作可做。如没有信息可供发送，则发送请求阻塞；当收到新的发送请求时，应将阻塞进程唤醒。 阻塞原语的主要功能阻塞原语的主要功能是将进程由执行状态转为阻塞状态。其主要操作过程如下：停止当前进程的执行；保存该进程的CPU现场信息；将进程状态改为阻塞，并插入到相应事件的等待队列中；转进程调度程序，从就绪队列中选择一个新的进程投入运行

16、。唤醒原语的主要功能当进程等待的事件发生时，由发现者进程将其唤醒。唤醒原语的主要功能是将进程唤醒，其主要操作过程如下：将被唤醒进程从相应的等待队列中移出；将进程状态改为就绪，并将该进程插入就绪队列；转进程调度或返回。阻塞与唤醒的关系一个进程由执行状态转变为阻塞状态，是这个进程自己调用阻塞原语去完成的。进程由阻塞状态转变为就绪状态，是另一个发现者进程调用唤醒原语实现的。一般发现者进程与被唤醒进程是合作的并发进程。2.4.4 进程的挂起与激活挂起原语和激活原语都有多种实现方式如：把发出挂起原语的进程自身挂起挂起具有指定标识符的进程把某进程及其子孙进程挂起激活一个具有指定标识名的进程激活某进程及其子

17、孙进程下面以挂起或激活具有指定标识符的进程为例，说明这两种原语的主要功能。 挂起原语的主要功能 挂起原语的主要功能是将指定进程挂起，算法思想如下：到PCB表中查找该进程的PCB；检查该进程的状态，若为执行则停止执行并保护CPU现场信息，将该进程状态改为挂起就绪；若为活动阻塞，则将该进程状态改为挂起阻塞；若为活动就绪，则将该进程状态改为挂起就绪；若进程挂起前为执行状态，则转进程调度，从就绪队列中选择一个进程投入运行。激活原语的主要功能 激活原语的主要功能是将指定进程激活。其算法思想如下：到PCB表中查找该进程的PCB。检查该进程的状态。若状态为挂起阻塞，则将该进程状态改为活动阻塞。若状态为挂起就

18、绪，则将该进程状态改为活动就绪。若进程激活后为活动就绪状态，可能需要转进程调度。2.5 进程的组织系统中有许多进程，为了能对它们进行有效的管理，应将PCB组织起来。常用的组织方式有：线性方式链表方式索引方式线性方式线性方式：将PCB顺序存放在一片连续内存中。PCB1PCB2PCB3PCBnPCBn-1PCBn-2链接方式链接方式：将同一状态的PCB组成一个链表。 运行指针 就绪队列指针 阻塞队列指针PCBPCBPCBPCBPCBPCBPCB索引方式索引方式：将同一状态的进程归入一个索引表，再由索引指向相应的PCB 运行指针 就绪表指针 阻塞表指针PCB表就绪索引表阻塞索引表PCB1PCB2PC

19、B3PCB4PCB5PCB6PCB7PCB8PCB92.6 线程在操作系统中引入进程的目的是使多道程序能并发执行，以改善资源利用率及提高系统吞吐量；在操作系统中再引入线程，则是为了减少程序并发执行所付出的时空开销，使操作系统具有更好的并发性。2.6.1 线程的概念进程具有两个属性：拥有资源的独立单位调度和分派的基本单位为使进程并发执行，则必须进行诸如创建、撤消、切换等一系列操作，这些操作涉及到资源管理，所花费的时空开销较大，为此引入了线程。线程定义线程的定义情况与进程类似，存在多种不同的提法。下面列出一些较权威的定义：线程是进程内的一个执行单元。线程是进程内的一个可调度实体。线程是程序（或进程

20、）中相对独立的一个控制流序列。线程是执行的上下文，其含义是执行的现场数据和其他调度所需的信息（这种观点来自Linux系统）。线程本书定义线程是进程内一个相对独立的、可调度的执行单元。线程自己基本上不拥有资源，只拥有一点在运行时必不可少的资源（如程序计数器、一组寄存器和栈），但它可以与同属一个进程的其他线程共享进程拥有的全部资源。线程的控制和进程类似，线程也有运行、就绪、阻塞等状态。创建：当创建一个新进程时，也为该进程创建了一个线程。线程还可以创建新线程。就绪：线程已获得除处理机外的所有资源。运行：线程正在处理机上执行。阻塞：线程因等待某事件而暂停运行。终止：一个线程已完成。线程的同步与通信与进

21、程类似。进程的挂起及终止将影响到其中的所有线程。线程的控制（续）进程中的线程具有执行状态线程上下文执行栈线程静态存储局部变量寄存器及对所属进程资源的访问多线程多线程是指一个进程中有多个线程，这些线程共享该进程的状态和资源，它们驻留在同一地址空间，并且可以访问到相同的数据。线程的实现操作系统中有多种方式实现对线程的支持：内核级线程用户级线程上述两种方法的组合实现内核级线程内核级线程是指依赖于内核，由操作系统内核完成创建和撤消工作的线程。在支持内核级线程的OS中，内核维护进程和线程的上下文信息并完成线程切换。一个内核级线程阻塞时不会影响其他线程的运行。处理机时间分配的对象是线程，所以有多个线程的进

22、程将获得更多处理机时间。用户级线程用户级线程是指不依赖于操作系统核心，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制的线程。用户级线程的维护由应用进程完成，可以用于不支持内核级线程的操作系统当一个线程阻塞时，整个进程都必须等待，处理机时间是分配给进程的，进程内有多个线程时，每个线程的执行时间相对少一些。 两种方法的组合在有些系统中，提供了上述两种方法的组合实现。在这种系统中，内核支持多线程的建立、调度与管理；同时，系统中又提供使用线程库的便利，允许用户应用程序建立、调度和管理用户级的线程。因此可以很好地将内核级线程和用户级线程的优点结合起来。由此产生了不同的多线程模型。一对一模

23、型每个用户级线程映射到一个内核级线程上多对一模型多个用户级线程映射到一个内核级线程上多对多模型多个用户级线程映射到较少或相等个数的内核级线程上。2.6.2 线程与进程的比较调度：在传统OS中，进程是调度和分配资源的基本单位；引入线程后，线程是调度和分派的基本单位，进程是拥有资源的基本单位。拥有资源：进程是拥有资源的基本单位，由一个或多个线程及相关资源构成。并发性：进程之间可以并发执行，同一进程中的各线程之间也可以并发执行。系统开销：进程创建、撤销级切换的开销大于线程。而同一进程的线程间同步与通信开销小。习题P41 3（1）、3（3）、3（5）补充题：设单处理机系统中有n（n2）个进程，问：是否

24、总有进程运行？为什么？是否会出现等待队列为空的情况？为什么？是否会出现等待队列为空且无进程运行的情况？为什么？是否会出现就绪队列为空的情况？为什么？UNIX的进程描述在UNIX系统中，采用了段页式存储管理方式（在UNIX中将段称为区），因此一个进程实体由若干个区组成，包括程序区、数据区、栈区等。每个区又可分为若干页。进程描述的数据结构在UNIX System 中，将PCB分成进程表项和U区（又称proc结构和user结构）两部分。除进程表项和U区外，管理进程的数据结构还有本进程区表和系统区表。进程表项状态字段用于标识进程的状态。若干用户标识号，简称UID或用户ID。若干进程标识号，简称PID或

25、进程ID。存储区位置和长度。调度参数，包括优先数等。软中断信号域。各种计时域，给出进程执行时间和系统资源的利用情况。指向U区的指针，指向与进程表项对应的U区。事件描述域，记录使进程进入睡眠状态的事件。U区指向进程表项的指针，指出对应于该U区的进程表项。真正用户标识符及有效用户标识符。用户文件描述符表，记录进程已打开的文件。当前目录和当前根，描述进程的文件系统环境。计时器域，记录进程及其后代运行所用的时间。一些输入/输出参数。描述要传输的数据量，源或目的数据地址等。限制域，指出进程的大小及它能“写”的文件大小限制。出错域，记录系统调用执行期间所发生的错误。返回值域，指出系统调用的返回结果。信号处

26、理数组，指出进程接收到软中断信号时的处理方式。系统区表UNIX System 把一个进程的虚地址空间划分为正文区、数据区、栈区等。系统设置区表对区进行管理，区表主要包含以下信息：区的类型和大小。指明区的类型为正文、数据或栈。区的状态。一个区具有状态：锁住、在请求中、在装入过程中、有效（区已装入内存）。区在物理存储器中的位置。引用计数。共享该区的进程数。指向文件索引节点的指针。 本进程区表系统为每个进程配置了一张本进程区表，表中每一项记录一个区的起始虚地址及指向系统区表中对应区表项的指针。核心通过查找本进程区表和系统区表，将区的逻辑地址变换为物理地址。进程的数据结构 a b本进程区表系统区表进程

27、表abU区内存进程状态及其转换在UNIX System 中，为进程设置了9种状态。用户态执行核心态执行内存中就绪内存中睡眠就绪且换出睡眠且换出被剥夺状态创建状态僵死状态UNIX系统的状态转换图 fork唤醒退出48就绪且换出睡眠且换出唤醒内存中睡眠换出换入内存足够内存中就绪内存不足创建9核心态执行睡眠僵死调度被剥夺状态返回系统 调用用户态执行返回用户态17换出剥夺6523中断、中断返回进程上下文进程上下文又称进程映像，它由三部分组成：用户级上下文寄存器上下文系统级上下文用户级上下文用户级上下文由进程虚地址空间中的正文、数据、用户栈和共享存储区组成。寄存器上下文寄存器上下文主要由CPU中的一些寄

28、存器内容构成。主要的寄存器有：程序计数器。其中存放的是CPU要执行的下条指令的虚地址。处理机状态寄存器。其中包括运行方式(用户态、核心态)，处理机当前的运行级，以及记录处理机与该进程有关的硬件状态信息。栈指针。指向栈的下一个可用单元或栈中最后使用的单元（因机器而异）。通用寄存器。用于存放进程在运行过程中所产生的数据，通用寄存器的数目因机器而异。系统级上下文系统级上下文可分为静态和动态两部分：静态部分：系统级上下文的静态部分由进程表项、U区、本进程区表项、系统区表项和页表组成。动态部分：系统级上下文动态部分的数目是可变的。它包括：核心栈、若干层寄存器上下文。进程控制在UNIX系统中，用于对进程实

29、施控制的主要系统调用有：fork，创建进程；exec，执行文件；exit，进程终止；wait，等待子进程终止。系统调用fork系统调用fork用于创建一个新进程。fork系统调用的语法格式如下：int fork( )fork系统调用没有参数，如果执行成功，则创建一个子进程，子进程继承父进程的许多特性，并具有与父进程完全相同的用户级上下文。fork的算法描述算法 fork，无输入参数，父进程返回子进程PID，子进程返回0 检查可用的内核资源； 取一个空闲的进程表项和惟一的PID号； 检查用户没有过多运行进程； 将子进程的状态设置为“创建”状态； 将父进程进程表项的数据拷贝到子进程进程表项中； 当

30、前目录和根目录的索引节点引用计数加1； 文件表中打开文件的引用计数加1； 在内存中作父进程上下文的拷贝；fork的算法描述（续）在子进程的系统级上下文中压入虚设系统级上下文层；if （正在执行的进程是父进程） 将子进程的状态设置为“就绪”状态； return（子进程的PID）； else 初始化U区的计时域； return（0）； 系统调用execexec系列中的系统调用都完成同样的功能，它们把一个新的程序装入调用进程的内存空间，以改变调用进程的执行代码，从而使调用进程执行新引入的程序功能。这一组系统调用的主要差别在于给出参数的数目和形式不同。系统调用exec续下面给出两种基本的exec调用格式说明：int execl(path , arg0 ，arg1，argn，0)； char *path，*arg0，*arg1, ，*argn ；int execv(path，argv)； char *path，*argv ； exec算法描述算法 exec，输入参数有文件名、参数表、环境变量，无输出。 取文件的索引节点（算法namei）；