搜索
操作系统原理教程第2章处理器管理本章教学目标了解线程的基本概念熟悉进程描述、进程通信和进程死锁掌握进程控制、进程同步与互斥、进程调度本章主要内容处理器管理概述进程描述进程控制线程的基本概念进程同步与互斥进程通信进程调度进程死锁处理器管理概述处理器管理的功能程序的执行处理器管理的功能处理器管理的主要任务–是对处理器进行分配，并对其运行进行有效地控制和管理。处理器管理的主要功能–进程控制–进程同步–进程通信–进程调度程序的执行程序执行的描述–前趋图程序的顺序执行程序的并发执行前趋图概念：–前趋图是一个有向无循环图。要求–每个结点可用于表示一条语句、一个程序段等–结点间的有向边表示在两个结点之间存在的前趋关系例如：–图2-1所示程序的顺序执行概念：–程序在执行时，必须按某种先后次序逐个执行操作，只有当前一个操作执行完后，才能执行后一个操作。特征：–顺序性–封闭性–可再现性程序的并发执行概念：–是指在一个时间段内执行多个程序。特征：–间断性–失去封闭性–不可再现性程序并发执行的判断方法：–Bernstein条件–利用前趋图Bernstein条件原理：–不同运算（或程序）的读集与写集的交集和写集与写集的交集的并集为空集时，这几个运算（或程序）可以并发执行。解释：–运算的读集是指在运算执行期间引用的所有变量的集合；–运算的写集是指在运算执行期间要改变的所有变量的集合。例子：–例2-2利用前趋图原理：–画出程序执行的前趋图，根据该程序或运算在前趋图中的位置关系，可以判断其能否并发执行。解释：–在程序或运算的先后顺序上，只有前后相邻的的程序或运算不能并发执行，其余程序和运算都可以并发执行。例子：–例2-3进程描述进程的概念进程的状态进程的挂起状态进程的概念进程的定义–一个程序在一个数据集合上的一次运行过程。所以一个程序在不同数据集合上运行，乃至一个程序在同样数据集合上的多次运行都是不同的进程。进程的特征–动态性–并发性–独立性–异步性–结构性进程的状态进程的三种基本状态进程的其它两种状态进程状态间的转换进程的三种基本状态就绪状态–当进程以分配到除处理器（CPU）以外的所有必要资源后，只要再获得处理器就可以立即执行，这时进程的状态称为就绪状态。执行状态–处于就绪状态的进程一旦获得了处理器，就可以运行，进程状态也就处于执行状态。阻塞状态–正在执行的进程因为发生某些事件（如请求输入/输出、申请额外空间等）而暂停运行，这种受阻暂停的状态称为阻塞状态，也可以称为等待状态。进程的其它两种状态新状态–当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为新状态。终止状态–当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。进程状态间的转换新状态→就绪状态就绪状态→执行状态执行状态→阻塞状态执行状态→就绪状态阻塞状态→就绪状态执行状态→终止状态如图2-5所示进程的挂起状态引入挂起状态主要原因：–用户的需求–父进程的需求–操作系统的需求–对换的需求引入挂起状态后的进程状态转换–执行状态→静止就绪–活动就绪→静止就绪–静止就绪→活动就绪–活动阻塞→静止阻塞–静止阻塞→活动阻塞–静止阻塞→静止就绪进程控制进程控制块PCB进程的创建与撤消进程的阻塞与唤醒进程控制块PCB进程控制块的作用进程控制块的内容进程控制块的组织方式进程控制原语进程控制块的作用概念–进程控制块是进程实体的重要组成部分，是操作系统中最重要的记录型数据，在进程控制块PCB（ProgramContralBlock）中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息作用–通过PCB，使得原来不能独立运行的程序（数据），成为一个可以独立运行的基本单位，一个能够并发执行的进程。进程控制块是进程存在的唯一标志。进程控制块的内容进程标识信息–进程标识符用于标识一个进程，一个进程通有外部标识符和内部标识符两种说明信息–说明信息是有关进程状态等一些与进程调度有关的信息。现场信息–现场信息是用于保留进程存放在处理器中的各种信息，主要由处理器内的各个寄存器的内容组成。管理信息–管理信息包括进程资源、控制机制等一些进程执行所需要的信息。进程控制块的组织方式链接方式–把具有相同状态的PCB，用其中的链接指针链接成队列。如图2-7所示。索引方式–系统根据所有进程的状态，建立几张索引表。在每个索引表的表目中，记录着具有相同状态的各个PCB在表中的地址。如图2-8所示。进程控制原语原语的概念–原语是指具有特定功能的不可被中断的过程。它主要用于实现操作系统的一些专门控制操作。原语的分类–创建原语：用于为一个进程分配工作区和建立PCB，置该进程为就绪状态。–撤消原语：用于一个进程工作完后，收回它的工作区和PCB。–阻塞原语：用于进程在运行过程中发生等待事件时，把进程的状态改为等待态。–唤醒原语：用于当进程等待的事件结束时，把进程的状态改为就绪态。进程的创建引起进程创建的事件–用户登录–作业调度–提供服务–应用请求进程创建的过程–为新进程分配唯一的进程标识符，并从PCB队列中申请一个空闲PCB。–为新进程的程序和数据，以及用户栈分配相应的主存空间及其它必要分配资源。–初始化PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。–如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。进程的撤消引起进程撤消的事件–进程正常结束–在进程运行期间，由于出现某些错误和故障而使得进程被迫中止–进程应外界的请求而中止运行进程撤消的过程–根据被终止进程的标识符，从PCB集合中检索该进程的PCB，读出进程状态。–若该进程处于执行状态，则立即终止该进程的执行。–若该进程有子孙进程，还要将其子孙进程终止。–将该进程所占用的资源回收，归还给其父进程或操作系统。–将被终止进程的PCB从所在队列中移出，并撤消该进程的PCB。进程的阻塞引起进程阻塞的事件–请求系统服务–启动某种操作–新数据尚未到达–无新工作可做进程阻塞的过程–立即停止执行该进程。–修改进程控制块中的相关信息。把进程控制块中的运行状态由“执行”状态改为“阻塞”状态，并填入等待的原因，以及进程的各种状态信息。–把进程控制块插入到阻塞队列。根据阻塞队列的组织方式，把阻塞进程的进程控制块插入到阻塞队列中。–转调度程序重新调度，运行就绪队列中的其他进程。进程的唤醒引起进程唤醒的事件–请求系统服务得到满足–启动某种操作完成–新数据已经到达–有新工作可做进程唤醒的过程–从阻塞队列中找到该进程。–修改该进程控制块的相关内容。把阻塞状态改为就绪状态，删除等待原因等等。–把进程控制块插入到就绪队列。按照就绪队列的组织方式，把被唤醒的进程的进程控制块插入到就绪队列中。线程的基本概念1线程的概念–线程是进程中的一个实体，是被系统独立调度和执行的基本单位。线程与进程的比较–调度单位不同–并发形式不同–拥有资源不同线程的基本概念2线程的类型–系统级线程：是依赖于系统控制的，即无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤消、切换都是由系统控制实现的。–用户级线程：是由用户控制，对于用户级线程的创建、撤消、切换，都与系统控制无关，完全由用户自己管理。超线程超线程的概念–超线程技术就是利用特殊的硬件指令，在一颗实体处理器中放入两个逻辑处理单元，从而模拟成两个工作环境，让单个处理器都能使用线程级并行计算，同时处理多项任务，提升处理器资源的使用率。超线程的工作–超线程处理器被视为两个分离的逻辑处理器，应用程序不须修正就可使用这两个逻辑处理器。–每个逻辑处理器都可独立响应中断。第一个逻辑处理器可追踪一个软件线程，而第二个逻辑处理器则可同时追踪另一个软件线程。–由于两个线程共同使用同样的执行资源，因此不会产生一个线程执行的同时，另一个线程闲置的状况。进程同步与互斥进程的并发性进程的同步与互斥利用PV操作实现互斥与同步管程的基本概念进程的并发性概念–在并发执行的系统中，若干个作业可以同时执行，而每个作业又需要有多个进程协作完成。在这些同时存在的进程间具有并发性并发进程之间的关系–无关关系：这些进程间彼此毫无关系，互不影响–相关关系：这些进程间彼此往往相关，互相影响，要进行合理的控制和协调才能正确执行资源共享关系相互合作关系进程的同步与互斥进程同步与互斥的概念进程同步机制应遵循的原则利用锁机制实现同步进程同步与互斥的概念临界资源–在系统中有许多硬件或软件资源，在一段时间内只允许一个进程访问或使用，这种资源称为临界资源。临界区–每个进程中访问临界资源的那段代码称为临界区进程同步–进程同步是指多个相关进程在执行次序上的协调，这些进程相互合作，在一些关键点上需要相互等待或相互通信。进程互斥–进程互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才被允许使用临界资源。进程同步机制应遵循的原则空闲让进忙则等待有限等待让权等待利用锁机制实现同步锁的概念–在同步机构中，常用一个变量来代表临界资源的状态，并称它为锁。通常用“0”表示资源可用，用“1”表示资源已被占用。锁的操作–关锁操作–解锁操作利用PV操作实现互斥与同步整型信号量的概念信号量的操作利用PV操作实现互斥利用PV操作实现同步利用PV操作实现进程的同步加互斥整型信号量的概念概念–信号量就是一种特殊变量，它用来表示系统中资源的使用情况。而整型信号量就是一个整型变量。说明：–当其值大于“0”时，表示系统中对应可用资源的数目；–当其值小于“0”时，其绝对值表示因该类资源而被阻塞的进程的数目；–当其值等于“0”时，表示系统中对应资源已经都被占用，并且没有因该类资源而被阻塞的进程。信号量的操作（1）P操作：记为P（S），描述为：–P（S）–{S=S-1；–if（S0）W（S）；–}（2）V操作：记为V（S），描述为：–V（S）–{S=S+1；–if（S=0）R（S）；–}利用PV操作实现互斥概念：–互斥信号量是根据临界资源的类型设置的。有几种类型的临界资源就设置几个互斥信号量。它代表该类临界资源的数量，或表示是否可用，其初值一般为“1”。例题–【例2-4】在一个只允许单向行驶的十字路口，分别有若干由东向西，由南向北的车辆在等待通过十字路口。为了安全，每次只允许一辆车通过。当有车辆通过时其它车辆必须等候，当无车辆在路口行驶时则允许一辆车通过。请用PV操作实现保证十字路口安全行驶的自动管理系统。–【例2-5】有4位哲学家围着一个圆桌在思考和进餐，每人思考时手中什么都不拿，当需要进餐时，每人需要用刀和叉各一把，餐桌上的布置如图2-12所示，共有2把刀和2把叉，每把刀或叉供相邻的两个人使用。请用信号量及PV操作说明4位哲学家的同步过程。–【例2-6】在南开大学和天津大学之间有一条弯曲的小路，其中从S到T有一段路每次只允许一辆自行车通过，但其中有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车错车时使用，如图2-14所示。试设计一个算法使来往自行车可以顺利通过。利用PV操作实现同步概念–同步信号量是根据进程的数量设置的。一般情况下，有几个进程就设置几个同步信号量，表示该进程是否可以执行，或表示该进程是否执行结束。其初值一般为“0”。例子–【例2-7】图2-16给出了4个进程合作完成某一任务的前趋图，试说明这4个进程间的同步关系，并用PV操作描述它们。方法一：同步信号量用来表示该进程是否可以开始。方法二：同步信号量用来表示该进程是否已经结束。例子【例2-8】桌上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一只水果，请用PV操作实现爸爸、儿子、女儿3个并发进程的同步。【例2-9】有3个进程PA、PB、PC合