操作系统课件：进程与线程

进程与线程进程（process）是资源分配的基本单位，也是独立运行的基本单位。2.1进程的引入

为了描述并发程序执行时的特征，引入了进程。

2.1.1前趋图前趋图是一个有向无循环图，用于描述程序、程序段或语句执行的先后次序。图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存在的前趋关系“→”：→={(Pi，Pj)│Pi必须在Pj开始执行之前完成}前趋图中的各类结点如果(Pi，Pj)∈→，可以写成Pi→Pj，则称Pi是Pj的直接前趋，Pj是Pi的直接后继。若存在一个序列Pi→Pj→…→Pk，则称Pi是Pk的前趋。在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。

前趋图例S1S2S3S6S4S52.1.2程序的顺序执行

一个程序通常由若干个程序段所组成，它们必须按照某种先后次序来执行，仅当前一个操作执行完后才能执行后继操作，这类计算过程就是程序的顺序执行过程。例如：先输入→再计算→最后输出，即：I→C→P。程序顺序执行时的特征

顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一个操作必须在下一个操作开始之前结束。封闭性：程序一旦开始运行，其执行结果不受外界因素影响。可再现性：只要程序执行时的初始条件和执行环境相同，当程序重复执行时，都将获得相同的结果。2.1.3程序的并发执行及特点程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。程序并发执行例进程1、2、3并发执行。对每个进程而言，其输入、计算和输出这三个操作必须顺序执行。它们之间存在如下先后关系：I1先于C1和I2，C1先于P1和C2，P1先于P2I2和C1，I3、C2和P1可以并发。I1I2I3C1C3C2P1P2程序并发执行时的特征

间断性：并发程序具有“执行---暂停----执行”这种间断性的活动规律。失去封闭性：多个程序共享系统中的资源，这些资源的状态将由多个程序来改变，致使程序之间相互影响。不可再现性：在初始条件相同的情况下，程序的执行结果依赖于执行的次序。与时间有关的错误例程序并发执行时可能出现与时间有关的错误。例进程1：r1=x；进程2：r2=x；r1++；r2++；x=r1；x=r2；设在两进程运行之前，x的值为0。则两进程运行结束后，x值可为：122.1.4．程序并发执行的条件读集：语句执行期间要引用的变量集合，记为R（Si）={a1，…，am}写集：语句执行期间要改变的变量集合，记为W（Si）={b1，…，bn}Bernstein条件Bernstein条件能保证两个程序段并发执行而不会产生与时间有关的错误：R(Si)∩W(Sj)={}这两条保证R(Sj)∩W(Si)={}两次读之间数据不变W(Si)∩W(Sj)={}本条保证写操作结果不丢失例考虑下面4条语句：S1：a=x+yS2：b=z+1S3：c=a-bS4：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不能并发执行。并发语句的描述方式cobeginS1；S2；…Sn；coend对应的前趋图如右，其中S0和Sn+1分别是cobegin和coend语句前后的两条语句。S0S1S2…SnSn+12.2进程的定义及描述为了描述并发执行程序的动态特性，人们引入了一个新的概念——进程（process）。2.2.1进程的定义进程有多种定义，下面列举一些有代表性的定义：进程是程序在处理器上的一次执行过程。进程是可以和别的计算并行执行的计算。进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。2.2.2进程的特征动态性：进程是程序的一次执行过程。动态性还表现为它因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡。而程序是静态实体。并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。独立性：在传统OS中，进程是独立运行的基本单位，也是系统分配资源和调度的基本单位。异步性：也叫制约性，进程以各自独立的不可预知的速度向前推进。结构性：进程实体由程序段、数据段及进程控制块组成，又称为进程映像。2.2.3进程与程序的关系进程是动态概念，程序是静态概念；进程是程序在处理机上的一次执行过程，而程序是指令的集合。进程是暂时的，程序是永久的。进程是一个状态变化的过程；程序可以长久保存。进程与程序的组成不同。进程的组成包括程序、数据和进程控制块。进程与程序是密切相关的。一个程序可以对应多个进程；一个进程可以包括多个程序。进程可以创建新进程，而程序不能形成新程序。2.2.4进程控制块PCB（Processcontrolblock）是描述和管理进程的数据结构。它是进程实体的一部分，操作系统通过PCB感知进程的存在，PCB是进程存在的唯一标志。不同操作系统中进程控制块的结构不同，但通常包括下面所列出的内容：PCB包含的内容1进程标识符：惟一标识进程的一个标识符或整数。进程当前状态：说明进程当前所处状态。进程队列指针：用于记录PCB队列中下一个PCB的地址。程序和数据地址：进程的程序和数据在内存或外存中的存放地址。进程优先级：反映进程获得CPU的优先级别。PCB包含的内容2CPU现场保护区：CPU现场信息的存放区域，包括：通用寄存器、程序计数器、程序状态字等。通信信息：进程与其他进程所发生的信息交换。家族关系：指明本进程与家族的关系，如父子进程标识。资源清单：列出进程所需资源及当前已分配资源。2.3进程的状态及转换为了刻画进程的动态特征，可以将进程的生命期划分为一组状态，用这些状态来描述进程的活动过程。Processstate通常，一个进程至少应有以下三种基本状态：就绪状态ready执行状态running阻塞状态blocking2.3.1进程的三种基本状态就绪状态：进程已获得除处理机以外的所有资源，一旦分配了处理机就可以立即执行。执行状态：又称运行状态。一个进程获得必要的资源并正在处理机上执行。阻塞状态：又称等待状态、睡眠状态。正在执行的进程，由于发生某事件而暂时无法执行下去（如等待输入/输出完成）。这时即使把处理机分配给该进程，它也无法运行。进程状态转换图执行就绪阻塞进程调度时间片用完等待事件事件发生2.3.2新建状态和终止状态在许多系统中又增加了两种状态：新建状态（new）：进程刚刚建立，但还未进入就绪队列。又称创建状态。终止状态（terminated）

：当一个进程正常或异常结束，操作系统已释放它所占用的资源，但尚未将它撤消时的状态，又称退出状态。五状态的进程状态转换图运行就绪等待进程调度时间片用完等待事件事件发生新建终止接纳完成状态转换的有关说明大多数状态不可逆转，如等待不能转换为运行。状态转换大多为被动进行，但运行→等待是主动的。一个进程在一个时刻只能处于上述状态之一。2.3.3进程的挂起状态

在某些系统中，希望人为将进程挂起使之处于静止状态。进程挂起的原因有：系统故障或功能受到破坏：先挂起，故障消除后再恢复。检查中间结果：挂起进程以便检查。资源不足：挂起进程以腾出资源。内存不足：在外存挂起。有挂起状态的进程状态转换图基于上述原因，需引入一个新的状态：挂起状态。执行进程调度时间片完活动就绪等待事件挂起事件发生挂起激活活动阻塞挂起就绪挂起阻塞挂起激活事件发生创建退出接纳接纳完成因果变迁如果一个状态变化A的发生，会引起另一个状态变化B的发生，则称A、B之间是因果变迁。执行就绪阻塞4312下述哪些变迁是因果变迁a）3->4b）2->4c）1->22.4进程控制进程控制的职能是对系统中的所有进程实施有效的管理。常见的进程控制功能有进程创建、撤消、阻塞与唤醒等。这些功能一般由操作系统内核原语来实现。操作系统内核在操作系统设计中，往往把一些与硬件紧密相关的模块、运行频率较高的模块及公用的一些基本操作安排在靠近硬件的软件层次中，使它们常驻内存，以提高操作系统的运行效率，通常把这部分软件称为操作系统内核。内核（kernel）主要包括：中断时钟管理进程管理存储器管理设备管理原语primitive原语是由若干条机器指令构成的，用以完成特定功能的一段程序，这段程序在执行期间不可分割。计算机系统的两种运行状态核心态（kernelmode）：又称管态、系统态，是操作系统管理程序执行时机器所处的状态。这种状态具有较高的特权，能执行一切指令，访问所有的寄存器和存储区。用户态（Usermode）

：又称目态，是用户程序执行时机器所处的状态。这种状态具有较低特权，只能执行规定的指令，访问指定的寄存器和存储区。2.4.1进程创建为描述进程之间的创建关系，引入了进程图。进程图又称进程树（treeofprocess）或进程家族树，是描述进程家族关系的一棵有向树。图中的结点表示进程，若进程A创建了进程B，则从结点A有一条边指向结点B，说明进程A是进程B的父进程，进程B是进程A的子进程。

进程图例ABCDEF进程创建原语导致进程创建的原因有：用户登录：用户登录后，若合法则为用户创建一个进程。作业调度：为调度到的作业分配资源并创建进程。OS服务：创建服务进程。应用需要：应用程序根据需要创建子进程。创建原语的主要功能进程创建原语的功能是创建一个新进程，其主要操作过程如下：向系统申请一个空闲PCB。为新进程分配资源。如分配内存空间。初始化新进程的PCB。在其PCB中填入进程名、家族信息、程序和数据地址、进程优先级、资源清单及进程状态等。将新进程的PCB插入就绪队列。2.4.2进程撤销引起进程撤销的原因有：正常结束异常结束：超时、内存不足、地址越界、算术错、I/O故障、非法指令等。外界干预：包括操作员或系统干预，父进程请求。撤消原语采用的两种策略撤消原语采用的两种策略：撤消指定标识符的进程撤消指定进程及其所有子孙进程下面给出后一种撤消策略的功能描述。

撤消原语的主要功能撤消原语的功能是撤消一个进程，其主要操作过程如下：从系统的PCB表中找到被撤消进程的PCB。检查被撤消进程的状态是否为执行状态，若是则立即停止该进程的执行，设置重新调度标志。检查被撤消进程是否有子孙进程，若有子孙进程还应撤消该进程的子孙进程。回收该进程占有的全部资源并回收其PCB。2.4.3进程阻塞与唤醒引起进程阻塞及唤醒的事件：请求系统服务。如请求分配打印机，但无空闲打印机则进程阻塞；当打印机重又空闲时应唤醒进程。启动某种操作并等待操作完成。如启动I/O操作，进程阻塞；I/O完成则唤醒进程。等待合作进程的协同配合。如计算进程尚未将数据送到缓冲区，则打印进程阻塞；当缓冲区中有数据时应唤醒进程。系统进程无新工作可做。如没有信息可供发送，则发送请求阻塞；当收到新的发送请求时，应将阻塞进程唤醒。

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

挂起原语的主要功能

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

激活原语的主要功能是将指定进程激活。其算法思想如下：到PCB表中查找该进程的PCB。检查该进程的状态。若状态为挂起阻塞，则将该进程状态改为活动阻塞。若状态为挂起就绪，则将该进程状态改为活动就绪。若进程激活后为活动就绪状态，可能需要转进程调度。2.5进程的组织系统中有许多进程，为了能对它们进行有效的管理，应将PCB组织起来。常用的组织方式有：线性方式链表方式索引方式线性方式线性方式：将PCB顺序存放在一片连续内存中。PCB1PCB2PCB3PCBnPCBn-1PCBn-2…链接方式链接方式：将同一状态的PCB组成一个链表。

运行指针

就绪队列指针

阻塞队列指针PCBPCBPCBPCB^PCB^PCBPCB^索引方式索引方式：将同一状态的进程归入一个索引表，再由索引指向相应的PCB

运行指针

就绪表指针

阻塞表指针PCB表就绪索引表阻塞索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9………2.6线程thread在操作系统中引入进程的目的是使多道程序能并发执行，以改善资源利用率及提高系统吞吐量；在操作系统中再引入线程，则是为了减少程序并发执行所付出的时空开销，使操作系统具有更好的并发性。2.6.1线程的概念进程具有两个属性：拥有资源的独立单位调度和分派的基本单位为使进程并发执行，则必须进行诸如创建、撤消、切换等一系列操作，这些操作涉及到资源管理，所花费的时空开销较大，为此引入了线程。线程定义线程的定义情况与进程类似，存在多种不同的提法。下面列出一些较权威的定义：线程是进程内的一个执行单元。线程是进程内的一个可调度实体。线程是程序（或进程）中相对独立的一个控制流序列。线程是执行的上下文，其含义是执行的现场数据和其他调度所需的信息（这种观点来自Linux系统）。线程本书定义线程是进程内一个相对独立的、可调度的执行单元。线程自己基本上不拥有资源，只拥有一点在运行时必不可少的资源（如程序计数器、一组寄存器和栈），但它可以与同属一个进程的其他线程共享进程拥有的全部资源。线程的控制和进程类似，线程也有运行、就绪、阻塞等状态。创建：当创建一个新进程时，也为该进程创建了一个线程。线程还可以创建新线程。就绪：线程已获得除处理机外的所有资源。运行：线程正在处理机上执行。阻塞：线程因等待某事件而暂停运行。终止：一个线程已完成。线程的同步与通信与进程类似。进程的挂起及终止将影响到其中的所有线程。线程的控制（续）进程中的线程具有执行状态线程上下文执行栈线程静态存储局部变量寄存器及对所属进程资源的访问多线程多线程是指一个进程中有多个线程，这些线程共享该进程的状态和资源，它们驻留在同一地址空间，并且可以访问到相同的数据。线程的实现操作系统中有多种方式实现对线程的支持：内核级线程kernel-levelthread用户级线程user-levelthread上述两种方法的组合实现内核级线程内核级线程是指依赖于内核，由操作系统内核完成创建和撤消工作的线程。在支持内核级线程的OS中，内核维护进程和线程的上下文信息并完成线程切换。一个内核级线程阻塞时不会影响其他线程的运行。处理机时间分配的对象是线程，所以有多个线程的进程将获得更多处理机时间。用户级线程用户级线程是指不依赖于操作系统核心，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制的线程。用户级线程的维护由应用进程完成，可以用于不支持内核级线程的操作系统当一个线程阻塞时，整个进程都必须等待，处理机时间是分配给进程的，进程内有多个线程时，每个线程的执行时间相对少一些。

两种方法的组合在有些系统中，提供了上述两种方法的组合实现。在这种系统中，内核支持多线程的建立、调度与管理；同时，系统中又提供使用线程库的便利，允许用户应用程序建立、调度和管理用户级的线程。因此可以很好地将内核级线程和用户级线程的优点结合起来。由此产生了不同的多线程模型。一对一模型每个用户级线程映射到一个内核级线程上多对一模型多个用户级线程映射到一个内核级线程上多对多模型多个用户级线程映射到较少或相等个数的内核级线程上。2.6.2线程与进程的比较调度：在传统OS中，进程是调度和分配资源的基本单位；引入线程后，线程是调度和分派的基本单位，进程是拥有资源的基本单位。拥有资源：进程是拥有资源的基本单位，由一个或多个线程及相关资源构成。并发性：进程之间可以并发执行，同一进程中的各线程之间也可以并发执行。系统开销：进程创建、撤销及切换的开销大于线程。而同一进程的线程间同步与通信开销小。习题P423（1）、3（3）、3（5）补充题：设单处理机系统中有n（n>2）个进程，问：是否总有进程运行？为什么？是否会出现等待队列为空的情况？为什么？是否会出现等待队列为空且无进程运行的情况？为什么？是否会出现就绪队列为空的情况？为什么？选择题1对进程的管理和控制使用_____。A.指令

B.信号量C.原语

D.信箱分配到必要的资源并获得处理机时的进程状态是_____。A.就绪状态

B.撤消状态C.执行状态D.阻塞状态选择题2程序的顺序执行通常在

①

的工作环境中，具有以下特征

②

；程序的并发执行在

③

的工作环境中，具有如下特征

④

。A.资源共享B.程序的可再现性

C.多道程序D.单道程序下列进程状态变化中，_____变化是不可能发生的。A.等待→就绪B.等待→运行

C.运行→等待D.运行→就绪选择题3当_____时，进程从执行状态转变为就绪状态。A.等待的事件发生B.时间片到C.等待某一事件D.进程被调度程序选中下面对进程的描述中，错误的是_____。A.进程是有生命期的B.进程执行需要处理机C.进程是指令的集合D.进程是动态的概念选择题4操作系统通过_____对进程进行管理。A.JCBB.PCBC.DCTD.CHCT下面所述步骤中，_____不是创建进程所必需的。A.建立一个进程控制块B.为进程分配内存C.将进程控制块链入就绪队列D.由调度程序为进程分配CPU选择题5多道程序环境下，操作系统分配资源以_____为基本单位。A.作业

B.进程C.指令D.程序如果系统中有n个进程，则就绪队列中进程的个数最多为_____。A.nB.1C.n-1D.n+1选择题6下述哪一个选项，体现了原语的主要特点_____。A.并发性

B.异步性C.不可分割性D.共享性下面对父进程和子进程的叙述不正确的是_____。A.撤消父进程之时，可以同时撤消其子进程B.父进程和子进程之间可以并发C.父进程可以等待所有子进程结束后再执行D.父进程创建了子进程，因此父进程执行完了子进程才能运行选择题7并发进程失去了封闭性是指_____。A．并发进程的执行结果与速度无关B．多个相对独立的进程以各自的速度向前推进C．并发进程执行时，在不同时刻发生的错误D．并发进程共享变量，其执行结果与速度有关下列几种关于进程的叙述中，最不符合操作系统对进程理解的是_____。A．进程是在多程序并行环境中的完整的程序B．进程可以由程序，数据和进程控制块描述C．线程(Thread)是一种特殊的进程D．进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位选择题8当一个进程处于_____的状态时，称其为等待状态A．它正等待调度

B．它正等着协作进程的一个消息C．它正等分给它一个时间片

D．它正等进入内存进程从执行状态到阻塞状态可能是由于_____。A．进程调度程序的调度

B．现运行进程的时间片用完C．现运行进程执行了P操作

D．现运行进程执行了V操作选择题9一个进程被唤醒意味着_____。A．该进程重新占有了CPUB．进程状态变为就绪C．它的优先权变为最大

D．其PCB移至就绪队列的队首一个进程基本状态可以从其他两种基本状态转变过来

，这个基本状态是_____。A．执行状态B．阻塞状态

C．就绪状态D．撤销状态选择题10关于线程和进程，下列说法中正确的是____。A．线程一定是分配处理机时间的基本单位B．进程一定是分配处理机时间的基本单位C．一个线程可以属于多个进程

D．一个进程可以拥有多个线程填空题1进程的基本特征是

①

、

②

、

③

、

④

及

⑤

。进程的基本状态有执行、

①

和

②

。进程是一个程序对某个数据集的_____。进程由

①

、

②

、

③

三部分组成，其中

④

是进程存在的惟一标志。而

⑤

部分也可以为其他进程共享。程序并发