操作系统原理 第2章 处理器管理.ppt

《操作系统原理 第2章 处理器管理.ppt》由会员分享，可在线阅读，更多相关《操作系统原理 第2章 处理器管理.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统原理教程第2章 处理器管理本章教学目标l了解线程的基本概念l熟悉进程描述、进程通信和进程死锁l掌握进程控制、进程同步与互斥、进程调度 本章主要内容l处理器管理概述l进程描述l进程控制l线程的基本概念l进程同步与互斥l进程通信l进程调度l进程死锁处理器管理概述l处理器管理的功能l程序的执行处理器管理的功能l处理器管理的主要任务是对处理器进行分配，并对其运行进行有效地控制和管理。l处理器管理的主要功能进程控制 进程同步 进程通信 进程调度 程序的执行l程序执行的描述前趋图l程序的顺序执行l程序的并发执行前趋图l概念：前趋图是一个有向无循环图。l要求每个结点可用于表示一条语句、一个程序段等

2、结点间的有向边表示在两个结点之间存在的前趋关系 l例如：图2-1所示程序的顺序执行l概念：程序在执行时，必须按某种先后次序逐个执行操作，只有当前一个操作执行完后，才能执行后一个操作。l特征：顺序性封闭性可再现性程序的并发执行l概念：是指在一个时间段内执行多个程序。l特征：间断性 失去封闭性不可再现性l程序并发执行的判断方法：Bernstein条件利用前趋图Bernstein条件l原理：不同运算（或程序）的读集与写集的交集和写集与写集的交集的并集为空集时，这几个运算（或程序）可以并发执行。l解释：运算的读集是指在运算执行期间引用的所有变量的集合；运算的写集是指在运算执行期间要改变的所有变量的集合

3、。l例子：例2-2 利用前趋图l原理：画出程序执行的前趋图，根据该程序或运算在前趋图中的位置关系，可以判断其能否并发执行。l解释：在程序或运算的先后顺序上，只有前后相邻的的程序或运算不能并发执行，其余程序和运算都可以并发执行。l例子：例2-3进程描述l进程的概念l进程的状态l进程的挂起状态 进程的概念l进程的定义一个程序在一个数据集合上的一次运行过程。所以一个程序在不同数据集合上运行，乃至一个程序在同样数据集合上的多次运行都是不同的进程。l进程的特征动态性 并发性 独立性 异步性 结构性 进程的状态l进程的三种基本状态 l进程的其它两种状态 l进程状态间的转换 进程的三种基本状态 l就绪状态

4、当进程以分配到除处理器（CPU）以外的所有必要资源后，只要再获得处理器就可以立即执行，这时进程的状态称为就绪状态。l执行状态 处于就绪状态的进程一旦获得了处理器，就可以运行，进程状态也就处于执行状态。l阻塞状态 正在执行的进程因为发生某些事件（如请求输入/输出、申请额外空间等）而暂停运行，这种受阻暂停的状态称为阻塞状态，也可以称为等待状态。进程的其它两种状态 l新状态 当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为新状态。l终止状态当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。进程状态间的转换l新状态就绪状态 l就绪状态执行状态 l执

5、行状态阻塞状态 l执行状态就绪状态 l阻塞状态就绪状态 l执行状态终止状态 l如图2-5所示进程的挂起状态 l引入挂起状态主要 原因：用户的需求 父进程的需求 操作系统的需求 对换的需求 l引入挂起状态后的进程状态转换 执行状态静止就绪 活动就绪静止就绪 静止就绪活动就绪 活动阻塞静止阻塞 静止阻塞活动阻塞 静止阻塞静止就绪进程控制l进程控制块PCB l进程的创建与撤消 l进程的阻塞与唤醒 进程控制块PCB l进程控制块的作用l进程控制块的内容l进程控制块的组织方式l进程控制原语进程控制块的作用l概念进程控制块是进程实体的重要组成部分，是操作系统中最重要的记录型数据，在进程控制块PCB（Pro

6、gram Contral Block）中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息 l作用通过PCB，使得原来不能独立运行的程序（数据），成为一个可以独立运行的基本单位，一个能够并发执行的进程。进程控制块是进程存在的唯一标志。进程控制块的内容l进程标识信息 进程标识符用于标识一个进程，一个进程通有外部标识符和内部标识符两种 l说明信息 说明信息是有关进程状态等一些与进程调度有关的信息。l现场信息 现场信息是用于保留进程存放在处理器中的各种信息，主要由处理器内的各个寄存器的内容组成。l管理信息 管理信息包括进程资源、控制机制等一些进程执行所需要的信息。进程控制块的组织

7、方式l链接方式把具有相同状态的PCB，用其中的链接指针链接成队列。如图2-7所示。l索引方式 系统根据所有进程的状态，建立几张索引表。在每个索引表的表目中，记录着具有相同状态的各个PCB在表中的地址。如图2-8所示。进程控制原语l原语的概念原语是指具有特定功能的不可被中断的过程。它主要用于实现操作系统的一些专门控制操作。l原语的分类创建原语：用于为一个进程分配工作区和建立PCB，置该进程为就绪状态。撤消原语：用于一个进程工作完后，收回它的工作区和PCB。阻塞原语：用于进程在运行过程中发生等待事件时，把进程的状态改为等待态。唤醒原语：用于当进程等待的事件结束时，把进程的状态改为就绪态。进程的创建

8、 l引起进程创建的事件 用户登录 作业调度 提供服务 应用请求 l进程创建的过程 为新进程分配唯一的进程标识符，并从PCB队列中申请一个空闲PCB。为新进程的程序和数据，以及用户栈分配相应的主存空间及其它必要分配资源。初始化PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。进程的撤消l引起进程撤消的事件 进程正常结束 在进程运行期间，由于出现某些错误和故障而使得进程被迫中止 进程应外界的请求而中止运行 l进程撤消的过程 根据被终止进程的标识符，从PCB集合中检索该进程的PCB，读出进程状态。若该进程处于执行状态，则立即终止该进程

9、的执行。若该进程有子孙进程，还要将其子孙进程终止。将该进程所占用的资源回收，归还给其父进程或操作系统。将被终止进程的PCB从所在队列中移出，并撤消该进程的PCB。进程的阻塞l引起进程阻塞的事件 请求系统服务 启动某种操作 新数据尚未到达 无新工作可做 l进程阻塞的过程 立即停止执行该进程。修改进程控制块中的相关信息。把进程控制块中的运行状态由“执行”状态改为“阻塞”状态，并填入等待的原因，以及进程的各种状态信息。把进程控制块插入到阻塞队列。根据阻塞队列的组织方式，把阻塞进程的进程控制块插入到阻塞队列中。转调度程序重新调度，运行就绪队列中的其他进程。进程的唤醒l引起进程唤醒的事件 请求系统服务得

10、到满足 启动某种操作完成 新数据已经到达 有新工作可做 l进程唤醒的过程 从阻塞队列中找到该进程。修改该进程控制块的相关内容。把阻塞状态改为就绪状态，删除等待原因等等。把进程控制块插入到就绪队列。按照就绪队列的组织方式，把被唤醒的进程的进程控制块插入到就绪队列中。线程的基本概念1l线程的概念线程是进程中的一个实体，是被系统独立调度和执行的基本单位。l线程与进程的比较 调度单位不同 并发形式不同拥有资源 不同线程的基本概念2l线程的类型 系统级线程：是依赖于系统控制的，即无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤消、切换都是由系统控制实现的。用户级线程：是由用户控制，对于用户级

11、线程的创建、撤消、切换，都与系统控制无关，完全由用户自己管理。超线程 l超线程的概念 超线程技术就是利用特殊的硬件指令，在一颗实体处理器中放入两个逻辑处理单元，从而模拟成两个工作环境，让单个处理器都能使用线程级并行计算，同时处理多项任务，提升处理器资源的使用率。l超线程的工作 超线程处理器被视为两个分离的逻辑处理器，应用程序不须修正就可使用这两个逻辑处理器。每个逻辑处理器都可独立响应中断。第一个逻辑处理器可追踪一个软件线程，而第二个逻辑处理器则可同时追踪另一个软件线程。由于两个线程共同使用同样的执行资源，因此不会产生一个线程执行的同时，另一个线程闲置的状况。进程同步与互斥l进程的并发性 l进程

12、的同步与互斥 l利用PV操作实现互斥与同步 l管程的基本概念 进程的并发性l概念在并发执行的系统中，若干个作业可以同时执行，而每个作业又需要有多个进程协作完成。在这些同时存在的进程间具有并发性 l并发进程之间的关系无关关系：这些进程间彼此毫无关系，互不影响 相关关系：这些进程间彼此往往相关，互相影响，要进行合理的控制和协调才能正确执行 l资源共享关系 l相互合作关系 进程的同步与互斥 l进程同步与互斥的概念l进程同步机制应遵循的原则 l利用锁机制实现同步 进程同步与互斥的概念l临界资源 在系统中有许多硬件或软件资源，在一段时间内只允许一个进程访问或使用，这种资源称为临界资源。l临界区 每个进程

13、中访问临界资源的那段代码称为临界区 l进程同步进程同步是指多个相关进程在执行次序上的协调，这些进程相互合作，在一些关键点上需要相互等待或相互通信。l进程互斥进程互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才被允许使用临界资源。进程同步机制应遵循的原则 l空闲让进 l忙则等待 l有限等待 l让权等待 利用锁机制实现同步l锁的概念 在同步机构中，常用一个变量来代表临界资源的状态，并称它为锁。通常用“0”表示资源可用，用“1”表示资源已被占用。l锁的操作 关锁操作 解锁操作 利用PV操作实现互斥与同步 l整型信号量的概念 l信号量的操作

14、 l利用PV操作实现互斥l利用PV操作实现同步l利用PV操作实现进程的同步加互斥 整型信号量的概念l概念信号量就是一种特殊变量，它用来表示系统中资源的使用情况。而整型信号量就是一个整型变量。l说明：当其值大于“0”时，表示系统中对应可用资源的数目；当其值小于“0”时，其绝对值表示因该类资源而被阻塞的进程的数目；当其值等于“0”时，表示系统中对应资源已经都被占用，并且没有因该类资源而被阻塞的进程。信号量的操作l（1）P操作：记为P（S），描述为：P（S）S=S-1；if （S0）W（S）；l（2）V操作：记为V（S），描述为：V（S）S=S+1；if （S=0）R（S）；利用PV操作实现互斥l概

15、念：互斥信号量是根据临界资源的类型设置的。有几种类型的临界资源就设置几个互斥信号量。它代表该类临界资源的数量，或表示是否可用，其初值一般为“1”。l例题【例2-4】在一个只允许单向行驶的十字路口，分别有若干由东向西，由南向北的车辆在等待通过十字路口。为了安全，每次只允许一辆车通过。当有车辆通过时其它车辆必须等候，当无车辆在路口行驶时则允许一辆车通过。请用PV操作实现保证十字路口安全行驶的自动管理系统。【例2-5】有4位哲学家围着一个圆桌在思考和进餐，每人思考时手中什么都不拿，当需要进餐时，每人需要用刀和叉各一把，餐桌上的布置如图2-12所示，共有2把刀和2把叉，每把刀或叉供相邻的两个人使用。请

16、用信号量及PV操作说明4位哲学家的同步过程。【例2-6】在南开大学和天津大学之间有一条弯曲的小路，其中从S到T有一段路每次只允许一辆自行车通过，但其中有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车错车时使用，如图2-14所示。试设计一个算法使来往自行车可以顺利通过。利用PV操作实现同步l概念同步信号量是根据进程的数量设置的。一般情况下，有几个进程就设置几个同步信号量，表示该进程是否可以执行，或表示该进程是否执行结束。其初值一般为“0”。l例子【例2-7】图2-16给出了4个进程合作完成某一任务的前趋图，试说明这4个进程间的同步关系，并用PV操作描述它们。l方法一：同步信号量用来表

17、示该进程是否可以开始。l方法二：同步信号量用来表示该进程是否已经结束。例子l【例2-8】桌上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一只水果，请用PV操作实现爸爸、儿子、女儿3个并发进程的同步。l【例2-9】有3个进程PA、PB、PC合作解决记录打印问题：PA将记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的记录复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的记录打印出来，每执行一次打印一个记录；缓冲区的大小等于一个记录的PA、PB、PC大小。请用PV操作来保证记录

18、的正确打印。使用PV操作实现进程的同步加互斥 l概念l例子【例2-10】某数据库有一个写进程，多个读进程，它们之间读、写操作的互斥要求是：写进程运行时，其它读、写进程不能对数据库操作，读进程之间不互斥，可以同时读数据库。请用信号量及PV操作描述这一组进程的工作过程。例题l【例2-11】设有一个具有N个信息元素的环形缓冲区，A进程顺序地把信息写进缓冲区，B进程依次地从缓冲区中读出信息，用PV操作表示A、B进程的同步算法。l【例2-12】理发师理发问题。有一个理发师，一把理发椅和n把等候理发顾客坐的椅子。如果没有顾客，则理发师在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师，进行理发；如果理发师正

19、在理发，又有顾客来到时，如果有空椅子可坐，他就坐下来等候，如果没有空椅子，他就离开。请为理发师和顾客各编一个程序表述他们的行为。同步与互斥的解题思路l分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。l对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。l对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。l在每个进程中用于实现互斥的PV操作必须成对出现；用

20、于实现同步的PV操作也必须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒，必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作，但V操作的顺序没有严格要求。同步与互斥的解题步骤l（1）确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。l（2）确定同步互斥关系。根据是否使用的是临界资源，还是处理的前后关系，确定同步与互斥，然后确定信号量的个数、含义，以及对信号量的P、V操作。l（3）用类C语言描述同步或互斥算法。管程的基本概念l概念管程实际上是定义了一个数据结构和在该数据结构上的能为并发进程所执行的一组操作，这组操作能同步进程

21、和改变管程中的数据。l说明：管程由3部分组成：局部于管程的共享变量说明、对该数据结构进行操作的一组过程、对局部于管程的数据设置初始值的语句。每个管程都应该有唯一的名字来标识。进程通信l概念进程通信是指进程间的信息交换。l类型共享存储器系统消息传递系统管道通信系统 共享存储器系统l概念在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过它们进行通信。l方式共享数据结构方式 l相互通信的诸进程公用某些数据结构，并通过这些数据交换信息。共享存储区方式 l是在存储器中划出一块共享存储区，相互通信的诸进程可以通过对共享存储区中的数据进行读或写来实现通信。消息传递系统l概念进程

22、间的数据交换以消息为单位，用户直接利用系统中提供的一组通信命令（原语）进行通信。l方式直接通信方式l发送进程使用发送原语直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程使用接收原语从消息缓冲队列中取出消息。间接通信方式 l发送进程使用发送原语直接将消息发送到某种中间实体中，接收进程使用接收原语从该中间实体中取出消息。管道通信系统l管道管道是指连接读进程和写进程，以实现它们之间通信的共享文件。l管道通信系统向管道提供输入的发送进程（写进程），以字符流形式将大量的数据送入管道，而接受管道输出的接收进程（读进程），可以从管道中接收数据。进程调度l进程调度的类型l选择进程调度算法

23、的原则 l常用的进程调度算法 进程调度的类型l高级调度 l低级调度 l中级调度 高级调度l基本原理高级调度又称为作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入主存，并为它们创建进程、分配必要的资源，然后将新创建的进程排入就绪队列，准备执行。l需要解决的问题 一是接纳多少个作业。二是接纳哪些作业。低级调度l基本原理低级调度通常又称为进程调度或短程调度。它决定主存中的就绪队列上的哪个进程（单处理器系统）将获得处理器，然后把处理器分配给该进程，使其执行。l方式非抢占方式 l在某个进程正在占用处理器执行时，不允许其它任何进程抢占处理器。抢占方式 l把处理器分配给某个进程后，在该进程尚

24、未终止或阻塞时，允许系统调度程序根据某种原则，暂停正在执行的进程，回收已经分配的处理器，并将处理器重新分配给其它更为紧急的进程。中级调度l基本原理系统将那些暂时不能运行的进程从主存调到外存（仍然保持进程状态）上的特定区域，这些在外存存放的进程所处的状态称为就绪驻外状态或挂起状态。当这些进程的运行条件具备，且主存又有空闲时，在中级调度的控制下，再将处于外存上的那些重新具备运行条件的就绪驻外进程调入主存，并将其状态修改为就绪状态，放入就绪队列，等待进程调度。l目的是为了进一步提高主存的利用率和系统的吞吐量。选择进程调度算法的原则 l面向用户的原则 周转时间短 响应时间快 截止时间有保证 优先权原则

25、 l面向系统的原则 系统吞吐量高 处理器利用率好 各类资源的平衡利用 常用的进程调度算法l先来先服务调度算法 l短进程优先调度算法 l时间片轮转调度算法 l优先数调度算法 l响应比高者优先调度算法 l多级队列调度算法 先来先服务调度算法 l原理每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。l特点利于长进程，而不利于短进程。短进程优先调度算法 l原理它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生

26、事件而阻塞，然后退出处理器，再重新调度。l特点照顾到了系统中占大部分的短进程，有效地降低了进程的平均等待时间，提高了系统的吞吐量，但对长进程不利。时间片轮转调度算法 l原理系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。l特点为了保证人机交互的及时性，系统使每个进程依次按时间片方式轮流地执行。优先数调度算法 l原理它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。l方式非抢占式优先数调度算法 l系统一

27、旦把处理器分配给就绪队列中优先权最高的进程后，该进程就占有处理器一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。抢占式优先数调度算法 l系统同样把处理器分配给当前就绪队列中优先权最高的进程，使之执行。但在其执行期间，仍然会不断的有新的就绪进程进入就绪队列，如果出现某个进程，其优先权比当前正在执行的进程的优先权还高时，进程调度程序就会立即暂停当前进程的执行，而将处理器收回，并将处理器分配给新出现的优先权更高的进程，让其执行。响应比高者优先调度算法 l原理它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。l特点既照顾了短进程，又

28、考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。多级队列调度算法 l原理是根据进程的类型或性质的不同，将就绪进程分为若干个独立队列，不同类型或性质的进程固定地分属于一个队列，每个队列可以采用适合的调度算法，不同的队列可使用不同的调度算法。l特点同时具有多种操作方式 的进程调度进程死锁l死锁的基本概念 l死锁的预防 l死锁的避免 l死锁的检测与解除 死锁的基本概念 l死锁的概念是指多个进程因竞争资源而造成的一种僵局，若无外力的作用，这些进程将都不能再继续执行。l产生死锁的原因 竞争资源

29、 进程推进顺序非法 l产生死锁的必要条件 互斥条件 请求和保持条件 不剥夺条件 环路等待条件 死锁的预防 l原理该方法是通过对资源分配的原则进行限制，从而使产生死锁的四个必要条件中的第2、3、4个条件之一不能成立，来预防产生死锁。l方法破坏“不剥夺”条件 破坏“请求和保持”条件 破坏“环路等待”条件 死锁的避免 l原理在死锁的避免中，所施加的限制较弱，将获得较好一些的系统性能。该方法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免发生死锁。l安全状态是指系统能按某种顺序为每个进程分配所需资源，直到最大需求，使每一个进程都可以顺利完成。l利用银行家算法避免死锁银行家算

30、法的处理步骤l银行家算法的处理步骤为：（1）列出某一时刻资源分配表，格式如表2-4所示。（2）拿可用资源量与每一个进程所需资源量进行比较，可用资源量不少于所需资源量时，把资源分配给该进程。新的可用资源量为原有可用资源量加上该进程已分配资源量。（3）重复（2），直到所有进程都执行完，即可判断能否获得一个安全资源分配序列。l例题【例2-18】死锁的检测与解除l死锁的检测 利用死锁定理l死锁的解除 剥夺资源法 撤消进程法 本章小结 l处理器管理的主要任务是分配处理器，l主要目的是提高处理器的使用效率。l它的主要功能有：进程控制、进程同步、进程通信和进程调度。l熟悉和掌握以下基本概念：熟悉和掌握以下基本概念：进程、临界资源、同步、互斥、原语、线程、管程、管道、死锁 l熟悉和掌握以下基本知识：熟悉和掌握以下基本知识：1并发与并行。2进程描述与控制。3同步控制机制。4进程调度。5进程通信。6进程死锁。习 题 l一、单项选择题 1-22题l二、判断题 1-10题l三、填空题 1-15题l四、区分下列概念 1-8题l五、简答题 1-7题l六、应用题 1-19题