第二章 进程 管理 (1)
第二章 进程管理（ 1）
2.1 进程的概念和 PCB
2.2 进程控制
2.3 线 程第二章 进程管理
2.1 进程的基本概念
2.1.1程序的顺序执行及特征
1,基本概念
程序：一个在时间上按严格次序,顺序执行的操作序列 。
程序的顺序执行：一个具有独立功能的程序独占处理机,直至得到最终结果的过程 。
操作：数据处理的一种规则,一经启动就需要在有限时间内完成 。
计算：若干操作严格顺序执行的集合 。
2.程序的顺序执行
在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。 通常一个程序可分成若干个程序段，它们必须按照某种先后次序执行，
仅当前一操作执行后，才能执行后继操作。
例如：进行计算 。 I:输入操作 C:
计算操作 P:打印操作 。 在进行计算时,
总是先输入用户的程序和数据,然后进行计算,最后将结果打印出来 。
3.语句的顺序执行
S1,a:=x+y
S2,b:=a-5
S3,c:=b+1
如下图,语句 S2必须在 a被赋值后才能执行； S3也只能在 b
被赋值后才能执行 。
4.程序的顺序执行的特征
顺序性：一个程序的各个部分的执行,严格地按照某种先后次序执行；
封闭性：程序在封闭的环境下运行,即程序运行时独占全部系统资源；
可再现性：只要程序执行时的环境和初始条件相同,当程序重复执行时,不论它是从头到尾不停顿地执行,还是,停停走走,
地执行,都将获得相同的结果 。
程序顺序执行的特性,为程序员检测和校正程序的错误带来很大方便 。
2.1.2.前趋图
为了描述一个程序的各部分 (程序段或语句 )间的依赖关系,或者是一个大的计算的各个子任务间的因果关系,我们常常采用前趋图方式 。
图 2-1 九个结点的前趋图前趋图（续）
P1为初始结点,P9为终止结点每个结点还具有一个重量 。
该前趋图,存在下面的前趋关系：
P1→P 2,P1→P 3,P1→P 4,P2→P 5，
P3→P 5,P4→P 6,P4→P 7,P5→P 8，
P6→P 8,P7→P 9,P8→P 9；或表示为：
Ｐ ={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)}
前趋图（续）
前趋图中的每个结点可以表示一条语句,
一个程序段或进程,结点间的有向边表示两个结点之间存在的偏序 (Partial_Order)
或前趋关系 (Precedence_Relation)“→,
＝ {(Pi,Pj)|在 Pj开始前 Pi必须完成 }如果
(Pi,Pj)∈→,可写成 Pi→Pj,Pi是 Pj的直接前趋,Pj是 Pi的直接后继 。 前趋图中必须不存在循环,如下图不是前趋图 。
2.1.3 程序并发执行及特征
1.并发环境：
在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的
2,程序的并发执行
在对一批程序进行处理时,可以并发执行 。
例如,输入,计算,打印三个程序对一批作业进行处理时,存在以下的前趋关系：
Ii→Ci,Ii→Ii+ 1,Ci→Pi,Ci→Ci+ 1，
Pi→Pi +1
图 2-2 并发执行时的前趋图
Ii→C i,Ii→I i+1,Ci→P i,Ci→C i+1,Pi→P i+1
在 Pi-1和 Ci以及 Ii+1之间,可以并发执行 。
S1,a∶ =x+2
S2,b∶ =y+4
S3,c∶ =a+b
S4,d∶ =c+b
图 2-3 四条语句的前趋关系
3.程序的并发执行的特征
不可再现性,由于程序的并发执行,打破了由另一程序独占系统资源的封闭性,
因而破坏了可再现性 。
间断性,程序并发执行时,由于它们共享资源或程序之间相互合作完成一项共同任务,因而使程序之间相互制约 。
通信性,对于相互合作的程序,为了更有效地协调运行,相互之间进行通信 。
独立性,并发程序在运行过程中,既然是作为一个独立的运行实体,它也必然具有作为一个单位去获得资源的独立性 。
4.多道程序设计定义,Multiprogramming
多道程序设计是指允许多个程序同时进入内存并运行 （引入目的是为了提高系统效率）
与并发不完全是一个概念，但效果相似考虑因素：
在多道程序环境下如何向用户提供服务
在并发程序之间如何正确传递消息（通讯）
如何对 CPU进行调度，保证每个用户相对公平地得到 CPU
如何管理其他资源
当各用户对资源使用上发生冲突时，如何处理竞争对 CPU只能通过调度来解决竞争问题，而对于其他资源通过 申请 —分配 —使用 —回收 的办法进行管理，
当且仅当占有 CPU的时候才可以申请，否则要排队等候
2.1.4 进程的特征与状态
1.进程的概念
进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位
进程是可与其他程序并发执行的程序，
在一个数据集合上的运行过程。它是系统进行资源分配和调度的一个独立单位。
2,进程的特征
动态性,进程的实质是程序的一次执行过程,
进程是动态产生，动态消亡的，进程在其生命周期内，在三种基本状态之间转换
并发性,任何进程都可以同其他进程一起向前推进
独立性,进程是一个能独立运行的基本单位,
同时也是系统分配资源和调度的独立单位；
异步性,由于进程间的相互制约,使进程具有执行的间断性,即进程按各自独立的,不可预知的速度向前推进
结构特征,为了控制和管理进程,系统为每个进程设立一个进程控制块－ PCB。
3,进程与程序的区别
程序是静态的，进程是动态的 ;
进程更能真实地描述并发,而程序不能 ;
一个程序可对应多个进程，反之亦然 ;
进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 ;
程序可作为软件资源长期保存,进程只是一次执行过程,是暂时的；
进程是系统分配调度的独立单位,能与其他进程并发执行 ;
进程是由程序和数据两部分组成的
进程具有创建其他进程的功能，而程序没有
4,进程创建与中止
1）进程何时创建
提交一个批处理作业
用户登录
由 OS创建，用以向一用户提供服务 ( 如：打印文件 )
由已存在的一进程创建一个用户程序可创建成多个进程进程何时中止
批处理作业发出暂停（ Halt） 指令
用户退出登录
进程执行一中止服务请求
出错及失败因素
5,进程中止的原因
正常结束
给定时限到
缺少内存
存储器出界
保护性出错：例子,写只读文件
算术错
超出时间：进程等待超过对某事件的最大值
I/O 失败
无效指令：如试图执行数据
特权指令
操作系统干预：如当死锁发生时
父进程请求中止某一子进程
父进程中止，所以子进程也中止运行就绪 等待图 2－ 4 进程的状态及其转换
进程状态（续）
当进程已分配到除 CPU以外的所有必要资源时,
它便处于就绪状态,一旦获得 CPU,便立即执行 。
已获得 CPU的进程进入执行状态 。
正在执行的进程,由于发生某个事件而暂时无法执行时,便放弃处理机而进入阻塞状态 。
由于执行的进程变为阻塞状态后,调度程序立即把处理机分配给另一个就绪进程；因此,阻塞进程的事件消失后,进程不会立即恢复到执行状态,
而转变为就绪状态,重新等待处理机 。
2）进程 状态 转换条件在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：
就绪 --> 运行
– 调度程序选择一个新的进程运行
运行 --> 就绪
– 运行进程用完了时间片
– 运行进程被中断，因为一高优先级进程处于就绪状态进程状态 转换条件 （续）
运行 --> 等待
– 当一进程必须等待时
OS尚未完成服务
对一资源的访问尚不能进行
初始化 I/O 且必须等待结果
等待某一进程提供输入 (IPC)
等待 --> 就绪
– 当所等待的事件发生时
创建状态
终止状态
挂起状态
（调节负载，对换，父进程，
操作系统，终端用户）
3）其他状态创建 ( 新 new)状态
– OS 已完成为创建一进程所必要的工作
已构造了进程标识符
已创建了管理进程所需的表格
– 但还没有允许执行该进程 (尚未同意 )
因为资源有限终止（退出 exit)状态
– 中止后进程移入该状态
– 它不再有执行资格
– 表格和其它信息暂时由辅助程序保留
例子,为处理用户帐单而累计资源使用情况的财务程序
当数据不再需要后，进程 (和它的表格 )
被删除
4）具有挂起操作的进程状态转换图有的系统有时希望能人为地把进程挂起,使之处于静止状态,以便研究其执行情况或对它进行修改 。 下图示出了具有挂起状态的进程状态演变图 。
图 2－ 5 具有挂起状态的进程状态演变图五状态进程模型
准备退出：父进程可中止子进程七状态进程模型活动挂起事件发生事件发生 等待事件挂起调度超时释放活动挂起
5）新状态转换 (中期调度 )
阻塞 -->阻塞挂起
– 当所有进程都阻塞,OS会安排空间让一就绪进程进入内存
阻塞挂起 --> 就绪挂起
– 当等待的事件发生时 (状态信息已在 OS
中 )
就绪挂起 -->就绪
– 当内存中没有就绪进程时
就绪 -->就绪挂起 (较少见 )
– 当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时
7,进程控制块（ PCB）
系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。
系统利用 PCB来控制和管理进程，
所以 PCB是系统感知进程存在的唯一标志
进程与 PCB是一一对应的
1)进程控制块的内容
进程标识符：标识一个进程的编号,也称为进程的内部名；
现性状态：说明进程的当前状态；
现场保留区：保存进程由执行状态变为其它状态时的 CPU现场信息；
程序与数据地址：该进程的程序和数据所在位置信息；
互斥与同步机构：实现进程间互斥与同步时所必须的机构；
进程控制块的内容（续）
进程通信机制：用于实现进程间的通信所需的数据结构；
优先级：表示进程使用 CPU时优先级别的一个整数；
资源清单：列出进程拥有的资源的记录；
连接字：给出本进程所在队列中的下一个进程的 PCB首址；
家族联系：用于说明本进程与其它家族成员间的关系 。
2)进程映象 (进程要素 )
用户程序
用户数据
栈
– 用于过程调用和参数传递
进程控制块 PCB (执行上下文 )
– 控制进程所需的数据 (进程属性 )，
包括,
进程标识符信息
处理器状态信息
进程控制信息
3）进程控制块的组织方式为了有效地对进程控制块进行管理,
应该采用适当的方式把它们组织起来 。
目前常用的组织方式有以下两种：
按链接方式组织 PCB (队列 )
不同状态进程分别组成队列运行队列、就绪队列、等待队列
按索引方式组织 PCB (表 )
对具有相同状态的进程，分别设置各自的 PCB索引表，表明 PCB在 PCB表中的地址
（其他方式：线性表或链表）
按索引方式组织 PCB
按链接方式组织 PCB
PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCBn
......
空 PCB
运行态就绪态等待 1
等待 2
6
7
5
10
15
2.2 进程控制
1.进程控制的主要任务进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。
2.进程图进程图是一棵有向树 (如下图 )，
结点代表进程 。 一棵树表示一个家族,根 结 点 为 该 家 族 的 祖 先
(Ancestor)。
3.进程图和前趋图之间的差异
前趋图描述的是任务 (或进程 )之间的前趋关系；只有在前趋进程完成后,其后继进程才能运行；
在进程图中,创建者和被创建者可以并发执行,也可以父进程等待其所有的子进程结束后再执行,这完全取决于创建原语和创建者的需要 。
4.内核与原语
内核,加在硬件上的第一层软件,通过执行各种原语操作来实现各种控制和管理功能,具有创建,
撤消,进程通信,资源管理的功能 。
内核的基本功能支撑功能：中断处理,时钟管理,原语操作资源管理功能：进程管理,存贮管理,设备管理
原语,是由若干条机器指令所构成,用以完成特定功能的一段程序 。
5.进程控制创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。
进程创建原语进程撤消原语阻塞原语唤醒原语挂起原语激活原语
1)创建原语
功能,创建一个具有指定标识符进程
入口信息,进程标识符,优先级,
进程开始地址,初始 CPU状态,
资源清单等 。
进程创建过程
创建一个 PCB
赋予一个统一进程标识符
为进程映象分配空间
初始化进程控制块
– 许多默认值 (如,状态为 New，无
I/O设备或文件,..)
设置相应的链接
– 如,把新进程加到就绪队列的链表中创建原语的实现过程
2) 进程的撤消原语
功能：撤消一个指定的进程
入口信息：被撤消的进程名
实现,收回进程所占有的资源,
撤消该进程的 PCB
引起撤消的原因
正常结束
异常结束 （ 越界错,保护错,特权指令错,非法指令,运行超时,
I/O故障等 ）
外界干预 （ 操作员干预,父进程请父进程终止 ）
撤消原语的实现过程
3) 进程阻塞处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。
进程的阻塞原语
功能：停止调用进程的执行,变为等待 。
入口信息：可省
阻塞原语的实现过程
4) 进程的唤醒原语
功能,唤醒某一处于等待队列当中的进程 。
入口信息,被唤醒进程的名字
引起唤醒的原因系统服务由不满足到满足
I/O完成新数据到达进程提出新请求 （ 服务 ）
唤醒原语的实现过程
5)进程的挂起与激活
挂起原语的功能：自身挂起,挂起具有指定标识符的进程,将其进程及其全部或部分,子孙,挂起 。
激活原语功能：使处于静止状态的进程变为活动 。
6,系统核心
1)系统核心：
向上提供多个无中断的虚拟机器在核心内不允许中断
2)特点：
为进程运行提供一个舞台
核心常驻内存
设计短小精焊
3)核心的组成中断处理进程管理,
调度 控制 通讯 互斥 同步等原语管理,
在核心中提供一系列原语，同步,
通信，创建，撤消等
4) 队列管理队列数据结构,指向队首的表指针三个队列,运行，就绪，等待队列排队方式,排队首排队尾插 队出队方式,队首出队 /队中出队队列管理,中断之后，进程调度之前
5) 现场管理保存现场 ;注意顺序,中断之后第一步恢复现场,恢复时机，进程调度最后一步时钟管理,
以固定频率 +1 -1
用途,进入绝对时钟间隔时钟进行分析比较
6) 虚时钟每个进程分配给一个虚时钟来记录 CPU时间,这个时钟称为虚时钟。
虚时钟存放在 PCB中，属于现场的一部分，进程运行时，将虚时钟放入内存开辟的专门单元，离开 CPU则放在
PCB中。
核心处理 流程,
7)内核的执行特点由中断驱动的,中断 → 内核 → 退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令思考题
1．如果系统中有 N个进程，运行的进程最多几个，最少几个；就绪进程最多几个,最少几个；等待进程最多几个，最少几个？
2,有没有这样的状态转换，为什么？
等待 —运行； 就绪 —等待
3,一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能
4,举 3个日常生活中类似进程的例子第二章 进程管理
2.3 线 程
2.3 线 程
1.进程的两个基本属性：
资源的拥有者：
给每个进程分配一虚拟地址空间，
保存进程映像，控制一些资源（文件,I/O设备），有状态、优先级、
调度
调度单位：
进程是一个执行轨迹以上两个属性构成进程并发执行的基础
2,线程的引入对进程系统必须完成的操作：
创建进程
撤消进程
进程切换缺点：
时间空间开销大，限制并发度的提高线程的引入（续 1）
在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制
线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度
线程,有时称轻量级进程，进程中的一个运行实体，是一个 CPU调度单位，资源的拥有者还是进程或称任务线程的引入（续 2）
线程：
有执行状态（状态转换）
不运行时保存上下文
有一个执行栈
有一些局部变量的静态存储
可存取所在进程的内存和其他资源
可以创建、撤消另一个线程
3,线程的特点
是进程的一个实体,可作为系统独立调度和分派的基本单位 。
不拥有系统资源 （ 只拥有从属进程的全部资源,资源是分配给进程 ）
一个进程中的多个线程可并发执行 。
（ 进程可创建线程执行同一程序的不同部分 ）
系统开销小,切换快 。 （ 进程的多个线程都在进程的地址空间活动 ）
单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程
4.线程和进程的关系
P C B 用户栈单线程进程模型用户地址空间核心栈线程控制块：
包含了寄存器映像，线程优先数和线程状态信息
P C B
多线程进程模型用户地址空间用户栈核心栈线程控制块用户栈核心栈线程控制块用户栈核心栈线程控制块
5.引入线程的好处
创建一个新线程花费时间少（结束亦如此）
两个线程的切换花费时间少
（如果机器设有,存储 [恢复 ]所有寄存器,指令，则整个切换过程用几条指令即可完成）
因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核
适合多处理机系统例子 1：
LAN中的一个文件服务器，在一段时间内需要处理几个文件请求因此有效的方法是：为每一个请求创建一个线程在一个 SMP机器上：多个线程可以同时在不同的处理器上运行例子 2：
一个线程显示菜单，并读入用户输入；
另一个线程执行用户命令考虑一个应用：由几个独立部分组成，
这几个部分不需要顺序执行，则每个部分可以以线程方式实现当一个线程因 I/O阻塞时，可以切换到同一应用的另一个线程
6.线程与进程的比较
调度：线程作为调度的基本单位,同进程中线程切换不引起进程,当不同进程的线程切换才引起进程切换；进程作为拥有资源的基本单位 。
并发性：一个进程间的多个线程可并发 。
拥有资源：线程仅拥有隶属进程的资源；
进程是拥有资源的独立单位 。
系统开销：进程大；线程小 。
7,线程的实现机制
用户级线程
核心级线程
两者结合方法
1) 用户级线程（ ULT）
由应用程序完成所有线程的管理通过线程库 (用户空间 )
一组管理线程的过程
核心不知道线程的存在
线程切换不需要核心态特权
调度是应用特定的对用户级线程的核心活动
核心不知道线程的活动，但仍然管理线程的进程的活动
当线程调用系统调用时，整个进程阻塞
但对线程库来说，线程仍然是运行状态即线程状态是与进程状态独立的用户级线程的优点和缺点优点：
线程切换不调用核心
调度是应用程序特定的：可以选择最好的算法
ULT可运行在任何操作系统上（只需要线程库）
缺点：
大多数系统调用是阻塞的，因此核心阻塞进程，
故进程中所有线程将被阻塞
核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
2) 核心级线程（ KLT）
所有线程管理由核心完成
没有线程库，但对核心线程工具提供 API
核心维护进程和线程的上下文
线程之间的切换需要核心支持
以线程为基础进行调度
例子,Windows NT,OS/2
核心级线程的优点和缺点优点,
对多处理器，核心可以同时调度同一进程的多个线程
阻塞是在线程一级完成
核心例程是多线程的缺点：
在同一进程内的线程切换调用内核，
导致速度下降两者分析
针对不同的操作系统
开销和性能（ 线程的调度和切换速度 ）
系统调用（ 阻塞 ）
线程执行时间
灵活性
可扩充性
抢占 CPU
共享进程的资源
3) ULT和 KLT结合方法
线程创建在用户空间完成
大量线程调度和同步在用户空间完成
程序员可以调整 KLT的数量
可以取两者中最好的
例子,Solaris
实例,Solaris
进程：
用户地址空间
用户栈
进程控制块分派唤醒继续抢占停止可运行睡眠睡眠停止停止停止用户级线程活跃连接在 LWP上分派 唤醒继续时间片或抢占停止运行阻塞系统调用停止停止轻型进程状态
LWP状态独立于状态 ULT
（受限制 ULT除外）
可运行阻塞唤醒进程 1 进程 2 进程 3 进程 4 进程 5
进程库用户内核硬件用户级线程 内核级线程 轻型线程 处理器
8,线程与进程的关系线程：进程 特点 例子
1,1 每一执行的线程是有自己的地址空间和资源的唯一进程,
各种 UNIX版本
M,1 进程定义了所拥有的地址空间和动态资源。在该进程中多个线程可被创建和执行,
Windows NT,
Solaris,OS/2,
OS/390,MACH
9.用户级线程和内核支持线程
内核支持线程 ——依赖于内核 。
（ 创建,撤消,切换由内核实现 ）
用户级线程 ——与内核无关 （ 切换速度特别快,不利用系统调用 ）
第二章 进程管理（ 1）
2.1 进程的概念和 PCB
2.2 进程控制
2.3 线 程第二章 进程管理
2.1 进程的基本概念
2.1.1程序的顺序执行及特征
1,基本概念
程序：一个在时间上按严格次序,顺序执行的操作序列 。
程序的顺序执行：一个具有独立功能的程序独占处理机,直至得到最终结果的过程 。
操作：数据处理的一种规则,一经启动就需要在有限时间内完成 。
计算：若干操作严格顺序执行的集合 。
2.程序的顺序执行
在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。 通常一个程序可分成若干个程序段，它们必须按照某种先后次序执行，
仅当前一操作执行后，才能执行后继操作。
例如：进行计算 。 I:输入操作 C:
计算操作 P:打印操作 。 在进行计算时,
总是先输入用户的程序和数据,然后进行计算,最后将结果打印出来 。
3.语句的顺序执行
S1,a:=x+y
S2,b:=a-5
S3,c:=b+1
如下图,语句 S2必须在 a被赋值后才能执行； S3也只能在 b
被赋值后才能执行 。
4.程序的顺序执行的特征
顺序性：一个程序的各个部分的执行,严格地按照某种先后次序执行；
封闭性：程序在封闭的环境下运行,即程序运行时独占全部系统资源；
可再现性：只要程序执行时的环境和初始条件相同,当程序重复执行时,不论它是从头到尾不停顿地执行,还是,停停走走,
地执行,都将获得相同的结果 。
程序顺序执行的特性,为程序员检测和校正程序的错误带来很大方便 。
2.1.2.前趋图
为了描述一个程序的各部分 (程序段或语句 )间的依赖关系,或者是一个大的计算的各个子任务间的因果关系,我们常常采用前趋图方式 。
图 2-1 九个结点的前趋图前趋图（续）
P1为初始结点,P9为终止结点每个结点还具有一个重量 。
该前趋图,存在下面的前趋关系：
P1→P 2,P1→P 3,P1→P 4,P2→P 5，
P3→P 5,P4→P 6,P4→P 7,P5→P 8，
P6→P 8,P7→P 9,P8→P 9；或表示为：
Ｐ ={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)}
前趋图（续）
前趋图中的每个结点可以表示一条语句,
一个程序段或进程,结点间的有向边表示两个结点之间存在的偏序 (Partial_Order)
或前趋关系 (Precedence_Relation)“→,
＝ {(Pi,Pj)|在 Pj开始前 Pi必须完成 }如果
(Pi,Pj)∈→,可写成 Pi→Pj,Pi是 Pj的直接前趋,Pj是 Pi的直接后继 。 前趋图中必须不存在循环,如下图不是前趋图 。
2.1.3 程序并发执行及特征
1.并发环境：
在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的
2,程序的并发执行
在对一批程序进行处理时,可以并发执行 。
例如,输入,计算,打印三个程序对一批作业进行处理时,存在以下的前趋关系：
Ii→Ci,Ii→Ii+ 1,Ci→Pi,Ci→Ci+ 1，
Pi→Pi +1
图 2-2 并发执行时的前趋图
Ii→C i,Ii→I i+1,Ci→P i,Ci→C i+1,Pi→P i+1
在 Pi-1和 Ci以及 Ii+1之间,可以并发执行 。
S1,a∶ =x+2
S2,b∶ =y+4
S3,c∶ =a+b
S4,d∶ =c+b
图 2-3 四条语句的前趋关系
3.程序的并发执行的特征
不可再现性,由于程序的并发执行,打破了由另一程序独占系统资源的封闭性,
因而破坏了可再现性 。
间断性,程序并发执行时,由于它们共享资源或程序之间相互合作完成一项共同任务,因而使程序之间相互制约 。
通信性,对于相互合作的程序,为了更有效地协调运行,相互之间进行通信 。
独立性,并发程序在运行过程中,既然是作为一个独立的运行实体,它也必然具有作为一个单位去获得资源的独立性 。
4.多道程序设计定义,Multiprogramming
多道程序设计是指允许多个程序同时进入内存并运行 （引入目的是为了提高系统效率）
与并发不完全是一个概念，但效果相似考虑因素：
在多道程序环境下如何向用户提供服务
在并发程序之间如何正确传递消息（通讯）
如何对 CPU进行调度，保证每个用户相对公平地得到 CPU
如何管理其他资源
当各用户对资源使用上发生冲突时，如何处理竞争对 CPU只能通过调度来解决竞争问题，而对于其他资源通过 申请 —分配 —使用 —回收 的办法进行管理，
当且仅当占有 CPU的时候才可以申请，否则要排队等候
2.1.4 进程的特征与状态
1.进程的概念
进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位
进程是可与其他程序并发执行的程序，
在一个数据集合上的运行过程。它是系统进行资源分配和调度的一个独立单位。
2,进程的特征
动态性,进程的实质是程序的一次执行过程,
进程是动态产生，动态消亡的，进程在其生命周期内，在三种基本状态之间转换
并发性,任何进程都可以同其他进程一起向前推进
独立性,进程是一个能独立运行的基本单位,
同时也是系统分配资源和调度的独立单位；
异步性,由于进程间的相互制约,使进程具有执行的间断性,即进程按各自独立的,不可预知的速度向前推进
结构特征,为了控制和管理进程,系统为每个进程设立一个进程控制块－ PCB。
3,进程与程序的区别
程序是静态的，进程是动态的 ;
进程更能真实地描述并发,而程序不能 ;
一个程序可对应多个进程，反之亦然 ;
进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 ;
程序可作为软件资源长期保存,进程只是一次执行过程,是暂时的；
进程是系统分配调度的独立单位,能与其他进程并发执行 ;
进程是由程序和数据两部分组成的
进程具有创建其他进程的功能，而程序没有
4,进程创建与中止
1）进程何时创建
提交一个批处理作业
用户登录
由 OS创建，用以向一用户提供服务 ( 如：打印文件 )
由已存在的一进程创建一个用户程序可创建成多个进程进程何时中止
批处理作业发出暂停（ Halt） 指令
用户退出登录
进程执行一中止服务请求
出错及失败因素
5,进程中止的原因
正常结束
给定时限到
缺少内存
存储器出界
保护性出错：例子,写只读文件
算术错
超出时间：进程等待超过对某事件的最大值
I/O 失败
无效指令：如试图执行数据
特权指令
操作系统干预：如当死锁发生时
父进程请求中止某一子进程
父进程中止，所以子进程也中止运行就绪 等待图 2－ 4 进程的状态及其转换
进程状态（续）
当进程已分配到除 CPU以外的所有必要资源时,
它便处于就绪状态,一旦获得 CPU,便立即执行 。
已获得 CPU的进程进入执行状态 。
正在执行的进程,由于发生某个事件而暂时无法执行时,便放弃处理机而进入阻塞状态 。
由于执行的进程变为阻塞状态后,调度程序立即把处理机分配给另一个就绪进程；因此,阻塞进程的事件消失后,进程不会立即恢复到执行状态,
而转变为就绪状态,重新等待处理机 。
2）进程 状态 转换条件在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：
就绪 --> 运行
– 调度程序选择一个新的进程运行
运行 --> 就绪
– 运行进程用完了时间片
– 运行进程被中断，因为一高优先级进程处于就绪状态进程状态 转换条件 （续）
运行 --> 等待
– 当一进程必须等待时
OS尚未完成服务
对一资源的访问尚不能进行
初始化 I/O 且必须等待结果
等待某一进程提供输入 (IPC)
等待 --> 就绪
– 当所等待的事件发生时
创建状态
终止状态
挂起状态
（调节负载，对换，父进程，
操作系统，终端用户）
3）其他状态创建 ( 新 new)状态
– OS 已完成为创建一进程所必要的工作
已构造了进程标识符
已创建了管理进程所需的表格
– 但还没有允许执行该进程 (尚未同意 )
因为资源有限终止（退出 exit)状态
– 中止后进程移入该状态
– 它不再有执行资格
– 表格和其它信息暂时由辅助程序保留
例子,为处理用户帐单而累计资源使用情况的财务程序
当数据不再需要后，进程 (和它的表格 )
被删除
4）具有挂起操作的进程状态转换图有的系统有时希望能人为地把进程挂起,使之处于静止状态,以便研究其执行情况或对它进行修改 。 下图示出了具有挂起状态的进程状态演变图 。
图 2－ 5 具有挂起状态的进程状态演变图五状态进程模型
准备退出：父进程可中止子进程七状态进程模型活动挂起事件发生事件发生 等待事件挂起调度超时释放活动挂起
5）新状态转换 (中期调度 )
阻塞 -->阻塞挂起
– 当所有进程都阻塞,OS会安排空间让一就绪进程进入内存
阻塞挂起 --> 就绪挂起
– 当等待的事件发生时 (状态信息已在 OS
中 )
就绪挂起 -->就绪
– 当内存中没有就绪进程时
就绪 -->就绪挂起 (较少见 )
– 当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时
7,进程控制块（ PCB）
系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。
系统利用 PCB来控制和管理进程，
所以 PCB是系统感知进程存在的唯一标志
进程与 PCB是一一对应的
1)进程控制块的内容
进程标识符：标识一个进程的编号,也称为进程的内部名；
现性状态：说明进程的当前状态；
现场保留区：保存进程由执行状态变为其它状态时的 CPU现场信息；
程序与数据地址：该进程的程序和数据所在位置信息；
互斥与同步机构：实现进程间互斥与同步时所必须的机构；
进程控制块的内容（续）
进程通信机制：用于实现进程间的通信所需的数据结构；
优先级：表示进程使用 CPU时优先级别的一个整数；
资源清单：列出进程拥有的资源的记录；
连接字：给出本进程所在队列中的下一个进程的 PCB首址；
家族联系：用于说明本进程与其它家族成员间的关系 。
2)进程映象 (进程要素 )
用户程序
用户数据
栈
– 用于过程调用和参数传递
进程控制块 PCB (执行上下文 )
– 控制进程所需的数据 (进程属性 )，
包括,
进程标识符信息
处理器状态信息
进程控制信息
3）进程控制块的组织方式为了有效地对进程控制块进行管理,
应该采用适当的方式把它们组织起来 。
目前常用的组织方式有以下两种：
按链接方式组织 PCB (队列 )
不同状态进程分别组成队列运行队列、就绪队列、等待队列
按索引方式组织 PCB (表 )
对具有相同状态的进程，分别设置各自的 PCB索引表，表明 PCB在 PCB表中的地址
（其他方式：线性表或链表）
按索引方式组织 PCB
按链接方式组织 PCB
PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCBn
......
空 PCB
运行态就绪态等待 1
等待 2
6
7
5
10
15
2.2 进程控制
1.进程控制的主要任务进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。
2.进程图进程图是一棵有向树 (如下图 )，
结点代表进程 。 一棵树表示一个家族,根 结 点 为 该 家 族 的 祖 先
(Ancestor)。
3.进程图和前趋图之间的差异
前趋图描述的是任务 (或进程 )之间的前趋关系；只有在前趋进程完成后,其后继进程才能运行；
在进程图中,创建者和被创建者可以并发执行,也可以父进程等待其所有的子进程结束后再执行,这完全取决于创建原语和创建者的需要 。
4.内核与原语
内核,加在硬件上的第一层软件,通过执行各种原语操作来实现各种控制和管理功能,具有创建,
撤消,进程通信,资源管理的功能 。
内核的基本功能支撑功能：中断处理,时钟管理,原语操作资源管理功能：进程管理,存贮管理,设备管理
原语,是由若干条机器指令所构成,用以完成特定功能的一段程序 。
5.进程控制创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。
进程创建原语进程撤消原语阻塞原语唤醒原语挂起原语激活原语
1)创建原语
功能,创建一个具有指定标识符进程
入口信息,进程标识符,优先级,
进程开始地址,初始 CPU状态,
资源清单等 。
进程创建过程
创建一个 PCB
赋予一个统一进程标识符
为进程映象分配空间
初始化进程控制块
– 许多默认值 (如,状态为 New，无
I/O设备或文件,..)
设置相应的链接
– 如,把新进程加到就绪队列的链表中创建原语的实现过程
2) 进程的撤消原语
功能：撤消一个指定的进程
入口信息：被撤消的进程名
实现,收回进程所占有的资源,
撤消该进程的 PCB
引起撤消的原因
正常结束
异常结束 （ 越界错,保护错,特权指令错,非法指令,运行超时,
I/O故障等 ）
外界干预 （ 操作员干预,父进程请父进程终止 ）
撤消原语的实现过程
3) 进程阻塞处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。
进程的阻塞原语
功能：停止调用进程的执行,变为等待 。
入口信息：可省
阻塞原语的实现过程
4) 进程的唤醒原语
功能,唤醒某一处于等待队列当中的进程 。
入口信息,被唤醒进程的名字
引起唤醒的原因系统服务由不满足到满足
I/O完成新数据到达进程提出新请求 （ 服务 ）
唤醒原语的实现过程
5)进程的挂起与激活
挂起原语的功能：自身挂起,挂起具有指定标识符的进程,将其进程及其全部或部分,子孙,挂起 。
激活原语功能：使处于静止状态的进程变为活动 。
6,系统核心
1)系统核心：
向上提供多个无中断的虚拟机器在核心内不允许中断
2)特点：
为进程运行提供一个舞台
核心常驻内存
设计短小精焊
3)核心的组成中断处理进程管理,
调度 控制 通讯 互斥 同步等原语管理,
在核心中提供一系列原语，同步,
通信，创建，撤消等
4) 队列管理队列数据结构,指向队首的表指针三个队列,运行，就绪，等待队列排队方式,排队首排队尾插 队出队方式,队首出队 /队中出队队列管理,中断之后，进程调度之前
5) 现场管理保存现场 ;注意顺序,中断之后第一步恢复现场,恢复时机，进程调度最后一步时钟管理,
以固定频率 +1 -1
用途,进入绝对时钟间隔时钟进行分析比较
6) 虚时钟每个进程分配给一个虚时钟来记录 CPU时间,这个时钟称为虚时钟。
虚时钟存放在 PCB中，属于现场的一部分，进程运行时，将虚时钟放入内存开辟的专门单元，离开 CPU则放在
PCB中。
核心处理 流程,
7)内核的执行特点由中断驱动的,中断 → 内核 → 退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令思考题
1．如果系统中有 N个进程，运行的进程最多几个，最少几个；就绪进程最多几个,最少几个；等待进程最多几个，最少几个？
2,有没有这样的状态转换，为什么？
等待 —运行； 就绪 —等待
3,一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能
4,举 3个日常生活中类似进程的例子第二章 进程管理
2.3 线 程
2.3 线 程
1.进程的两个基本属性：
资源的拥有者：
给每个进程分配一虚拟地址空间，
保存进程映像，控制一些资源（文件,I/O设备），有状态、优先级、
调度
调度单位：
进程是一个执行轨迹以上两个属性构成进程并发执行的基础
2,线程的引入对进程系统必须完成的操作：
创建进程
撤消进程
进程切换缺点：
时间空间开销大，限制并发度的提高线程的引入（续 1）
在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制
线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度
线程,有时称轻量级进程，进程中的一个运行实体，是一个 CPU调度单位，资源的拥有者还是进程或称任务线程的引入（续 2）
线程：
有执行状态（状态转换）
不运行时保存上下文
有一个执行栈
有一些局部变量的静态存储
可存取所在进程的内存和其他资源
可以创建、撤消另一个线程
3,线程的特点
是进程的一个实体,可作为系统独立调度和分派的基本单位 。
不拥有系统资源 （ 只拥有从属进程的全部资源,资源是分配给进程 ）
一个进程中的多个线程可并发执行 。
（ 进程可创建线程执行同一程序的不同部分 ）
系统开销小,切换快 。 （ 进程的多个线程都在进程的地址空间活动 ）
单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程
4.线程和进程的关系
P C B 用户栈单线程进程模型用户地址空间核心栈线程控制块：
包含了寄存器映像，线程优先数和线程状态信息
P C B
多线程进程模型用户地址空间用户栈核心栈线程控制块用户栈核心栈线程控制块用户栈核心栈线程控制块
5.引入线程的好处
创建一个新线程花费时间少（结束亦如此）
两个线程的切换花费时间少
（如果机器设有,存储 [恢复 ]所有寄存器,指令，则整个切换过程用几条指令即可完成）
因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核
适合多处理机系统例子 1：
LAN中的一个文件服务器，在一段时间内需要处理几个文件请求因此有效的方法是：为每一个请求创建一个线程在一个 SMP机器上：多个线程可以同时在不同的处理器上运行例子 2：
一个线程显示菜单，并读入用户输入；
另一个线程执行用户命令考虑一个应用：由几个独立部分组成，
这几个部分不需要顺序执行，则每个部分可以以线程方式实现当一个线程因 I/O阻塞时，可以切换到同一应用的另一个线程
6.线程与进程的比较
调度：线程作为调度的基本单位,同进程中线程切换不引起进程,当不同进程的线程切换才引起进程切换；进程作为拥有资源的基本单位 。
并发性：一个进程间的多个线程可并发 。
拥有资源：线程仅拥有隶属进程的资源；
进程是拥有资源的独立单位 。
系统开销：进程大；线程小 。
7,线程的实现机制
用户级线程
核心级线程
两者结合方法
1) 用户级线程（ ULT）
由应用程序完成所有线程的管理通过线程库 (用户空间 )
一组管理线程的过程
核心不知道线程的存在
线程切换不需要核心态特权
调度是应用特定的对用户级线程的核心活动
核心不知道线程的活动，但仍然管理线程的进程的活动
当线程调用系统调用时，整个进程阻塞
但对线程库来说，线程仍然是运行状态即线程状态是与进程状态独立的用户级线程的优点和缺点优点：
线程切换不调用核心
调度是应用程序特定的：可以选择最好的算法
ULT可运行在任何操作系统上（只需要线程库）
缺点：
大多数系统调用是阻塞的，因此核心阻塞进程，
故进程中所有线程将被阻塞
核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
2) 核心级线程（ KLT）
所有线程管理由核心完成
没有线程库，但对核心线程工具提供 API
核心维护进程和线程的上下文
线程之间的切换需要核心支持
以线程为基础进行调度
例子,Windows NT,OS/2
核心级线程的优点和缺点优点,
对多处理器，核心可以同时调度同一进程的多个线程
阻塞是在线程一级完成
核心例程是多线程的缺点：
在同一进程内的线程切换调用内核，
导致速度下降两者分析
针对不同的操作系统
开销和性能（ 线程的调度和切换速度 ）
系统调用（ 阻塞 ）
线程执行时间
灵活性
可扩充性
抢占 CPU
共享进程的资源
3) ULT和 KLT结合方法
线程创建在用户空间完成
大量线程调度和同步在用户空间完成
程序员可以调整 KLT的数量
可以取两者中最好的
例子,Solaris
实例,Solaris
进程：
用户地址空间
用户栈
进程控制块分派唤醒继续抢占停止可运行睡眠睡眠停止停止停止用户级线程活跃连接在 LWP上分派 唤醒继续时间片或抢占停止运行阻塞系统调用停止停止轻型进程状态
LWP状态独立于状态 ULT
（受限制 ULT除外）
可运行阻塞唤醒进程 1 进程 2 进程 3 进程 4 进程 5
进程库用户内核硬件用户级线程 内核级线程 轻型线程 处理器
8,线程与进程的关系线程：进程 特点 例子
1,1 每一执行的线程是有自己的地址空间和资源的唯一进程,
各种 UNIX版本
M,1 进程定义了所拥有的地址空间和动态资源。在该进程中多个线程可被创建和执行,
Windows NT,
Solaris,OS/2,
OS/390,MACH
9.用户级线程和内核支持线程
内核支持线程 ——依赖于内核 。
（ 创建,撤消,切换由内核实现 ）
用户级线程 ——与内核无关 （ 切换速度特别快,不利用系统调用 ）
