软件技术基础操作系统 处理器管理.doc

《软件技术基础操作系统 处理器管理.doc》由会员分享，可在线阅读，更多相关《软件技术基础操作系统 处理器管理.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.3处理器管理在多道程序运行时，操作系统对处理机的管理就是通过对进程的管理来实现的。代表性的进程定义：1)进程是程序的一次执行；2)进程是可以和别的计算并发执行的计算；3)进程可定义为一个数据结构及能在其上进行操作的一个程序；4)进程是一个程序及其数据在处理机上执行时所发生的活动；5)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。3.3.1基本概念与术语1.作业和进程作业是从事物处理看工作的处理过程。进程是从系统处理看工作的处理过程。例：医生看病，病人看病需要挂号、预约、就诊、验血、做CT，就诊、取药等作业。医生诊断过程就是进程。就诊的环节，病人称为作业，医

2、生称为进程诊疗室就是CPU（1）作业、作业步一个作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。作业由不同的顺序相连的作业步组成。 作业步是在一个作业的处理过程中，计算机所做的相对独立的工作。（2）进程和程序进程与程序的关系程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。进程更能真实地描述并发，而程序不能；进程是由程序和数据两部分组成的。进程具有创建其他进程的功能，而程序没有。同

3、一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程。 特权指令、处理机状态特权指令：只能由操作系统使用非特权指令：供一般用户使用管态（主态、执行状态）：此时处理器执行特权指令。目态（算态、题目状态）：此时处理器处于用户状态。3处理器管理3.4.1 处理机调度的层次 1. 高级调度高级调度又称为作业调度或宏观调度。其主要功能是根据一定的算法，从输入的一批任务（作业）中选出若干个作业，分配必要的资源，如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输入/输出进程），最后把它们的程序和数据调入内存，等待进程调度程序对其执行调度，并在作业完成

4、后作善后处理工作。2. 中级调度中级调度涉及进程在内外存间的交换。为缓解内存紧张问题，在许多系统中设立了中级调度。中级调度的主要功能是在内存使用紧张时，将一些暂时不能运行的进程从内存对换到外存上等待。以后，当内存有足够的空闲空间时，再将合适的进程重新换入内存，等待进程调度。引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。 3. 低级调度低级调度又称进程调度或微观调度，其主要功能是根据一定的算法，将CPU分派给就绪进程队列中的一个进程。执行低级调度功能的程序称为进程调度程序，由它实现CPU在进程间的切换。 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须有进程调度，而且它

5、的策略的优劣直接影响整个系统的性能。3.3.2 作业调度1作业状态转换及作业控制块提交状态：一个作业被提交给机房后或用户通过终端键盘向计算机键入其作业时所处的状态后备状态(收容状态)：作业的全部信息都已通过输入机输入，并由操作系统将其存在磁盘的某些分区（存放作业的输入井）中等待运行。运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行。完成状态：作业完成其全部运行，释放出其所占用的全部资源。准备退出系统时的作业。作业控制块 1）作业标识 2）作业名 3）估计运行时间 4）优先级 5）作业创建时间 6）作业状态 7）作业对其他资源的要求2.作业调度的功能通常作业调度程序要完成以下的工作：（

6、1） 按照某种调度算法，从作业队列中选取作业进入内存。（2） 调用存储管理和设备管理程序，为选中的作业分配内存和外设。（3） 为选中的作业建立相应的进程。（4） 作业运行完毕时回收该作业站用的资源，输出必要的信息，撤消该作业的JCB（进程控制块）与相应的进程。3.作业调度算法调度算法的设计原则1）公平2）提高资源利用率3）对资源的均衡使用4）提高该系统的吞吐量5）响应时间短几种调度算法：（1） 先来先服务算法 小作业可能回等待时间比较长。（2） 基于优先级的调度算法 优先数=（等待时间）2-（要求运行时间）- 输出量（3） 分时和优先级相结合的作业调度3.3.3 进程调度1.进程的状态转换和进

7、程控制块1.进程的三种基本状态进程在运行过程中有3种基本状态。这些状态与系统调度占有处理机密切相关。所以又称它们为进程调度状态。运行状态（Running）当一个进程已分配到处理机，它的程序正由处理机执行时，称此进程处于执行状态。就绪状态（Ready）如果进程已具备执行条件，但是因为处理机已由其他进程占用，暂时不能执行而等待分配处理机，称此为就绪状态。等待状态（Blocked，阻塞状态）进程因等待某一事件（如等待某一输入，输出操作完成）而暂时不能运行的状态称为等待状态，此时即使CPU空闲，它也无法使用。进程控制块的组成：进程名特征信息进程状态信息调度优先权通信信息现场保护区资源需求进程实体信息族

8、系关系其他信息2.进程控制进程控制：系统使用一些具有特定功能的程序段来撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调，实现资源共享的目的。这种控制是通过原语来实现的。原语：是机器指令的延伸，是由若干条机器指令构成的用以完成特定功能的一段程序。原语是操作系统设计的、不可中断的程序，即具有原子性的程序，它用于实现某种独立功能并可以被其他进程调用。为保证操作的正确性，原语在执行期间是不可分割的，在许多机器中为了实现上的方便，规定在执行原语操作时，要屏蔽中断，以保证原语操作的不可分割性。用于进程控制的原语有： 1.进程创建原语 2.进程调度原语 3.进程阻塞原语 （进程等待原语

9、） 4.进程唤醒原语 5.进程撤销原语3.进程调度算法（1） 优先数法（2） 轮转调度法（3） 分级调度法3.3.4 多道程序并发运行出现的问题1.进程的同步和互斥(1) 同步与互斥进程之间的相互制约关系 由于进程是并发执行的，多个进程之间必然存在着各种形式的制约关系。一般来说，并发进程之间存在两种形式的制约关系。 1）资源共享关系，又称为间接相互制约关系，指进程之间本来彼此无关，但因为共享系统资源，如CPU、内存、I/O设备等而产生的相互制约关系。 2）进程合作关系，又称为直接相互制约关系，指多个进程之间具有合作关系，用于完成共同的任务，如同一个作业的输入、计算、输出进程之间必然是相互合作的

10、关系，他们必须按照一定的次序运行。所谓进程同步，是指对多个相关进程在执行次序上的协调，操作系统中用于保证这种协调关系的相应机制称为进程同步机制。对于资源共享关系的进程，应该保证多个并发进程互斥访问临界资源；而对于相互合作的进程，应该保证他们在执行次序上的协调。临界资源 临界资源是依次只能被一个进程访问的资源。独占设备、内存中的公共数据结构、公共变量等都是临界资源。临界区 在并发进程中，对共享变量操作的那段程序叫临界区。进程互斥 一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。 例如：

11、进程p1，p2都需要使用打印机，如果让它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使用。为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须等待。例如：P1:R1count;P2:R2count;P1:R1R1 +1;countR1;P2:R2R2 +1;countR2;虽然P1，P2P都对count作了加1，但count中只增加了1。（2）解决同步与互斥的工具P-V操作对信号量s（整数型）操作的定义为P操作P(s)1 ss-12 If(s0)then3 status(q)”blocked”/将进程q置为“阻塞”

12、/4 Insert(Q,q)/将q插入阻塞队列中/5 ReturnV操作V(s)1ss+12If(s=0)then3remove(Q,R)/将R移出阻塞队列Q/4status(R)”ready”/将R置为“就绪”/5Insert(RL,R)/将R插入就绪队列中RL/6Return(3)用P-V操作实现进程互斥(4)用P-V操作实现进程同步1）非对称制约如果进程P1在执行到L1处从进程P2获取某些信息后才能继续执行，而这些信息却是P2到达L2处后才能提供，为此着两个进程必须采用如下方式进行同步：设置s=0，在进程P2尚未完成V(s)操作之前，进程P1只能处于等待状态。2）双向制约生产者和消费者问

13、题防止生产者将物品放入已满的缓冲区中，同时也禁止消费者从空缓冲区中取物品。一个缓冲区时设置初值s1=1，s2=0。n个缓冲区时设置初值s1=n，s2=0。2.进程通信（1）直接通信方式。发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息，这种通信方式也称为消息缓冲通信。（2）间接通信。发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。这种通信方式也称信箱通信。在网络中称为电子邮件系统。3.死锁(1)死锁的原因和必要条件死锁产生的原因可归结为如下两点：（1）资源有限。当系统中多个进程共享资源，如打印机、公用队列等，其数目不足以满足

14、诸进程的需要，会引起进程对资源的竞争而产生死锁。（2）并发进程间的推进顺序不当。进程在运行过程中，请求和释放资源的顺序不当，也会导致产生进程死锁。 死锁的必要条件：互斥条件：涉及的资源是非共享的。不剥夺条件：不能强行剥夺进程拥有的资源。部分分配条件：进程在等待一新资源时继续占有已分配的资源。环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。（2）死锁的预防通过破坏死锁存在的(4个)必要条件来防止死锁发生。(1) 破坏互斥条件 如果允许系统资源都能共享使用，则系统不会进入死锁状态。但这种方法不是切实可行的。因为有些资源若是共享使用。例如：打印机在多进程打印

15、，不能每个进程打印一行，则无法保证其正确性。又如，对临界资源的访问就必须互斥进行。(2) 破坏占有等待 (二个方法)方法一：进程申请到它所需要的所有资源后，才能开始运行，又称预先静态分配法。例如，一个制表打印进程，需共有打印机，才能运行。此方法虽可保证无死锁，但是a.资源的利用率低 (在程序运行中，打印机空闲)；b. 由于所需资源不能在一次中得到全部满足，而使作业无限期延长。方法二：进程提出申请资源前必须释放已占有的一切资源。这些虽然能提高资源利用率，但要仔细进行程序设计，有时仍需提前申请资源才能保证正确性。这使用户倍感不便。注要考虑无限等待现象 (其实质与死锁一样)。例：P1申请r1, r2

16、, r3，而仅有r3。这时P2申请r3；则把r3给P2，某一进程Pi又释放了r1, r2，而 P1又因无r3，仍需等待直到饿死P1。我们应有相应的防止措施。比如按申请资源的先后次序给进程赋优先级。这种资源预先分配的方法，适于对外存空间的分配。因为作业运行期间所需外存变化不大。(3) 破坏非剥夺性条件在进程主动释放占有的资源前即予以剥夺，也能保证系统不出现死锁。方法一：当进程Pi申请rj类资源时，检查rj中有无可分配的资源，有则分配给Pi；否则将Pi占有的资源全部释放进入等待状态。方法二：当Pi申请rj时，检查rj中有无可分配的资源，有则分配；否则检查占有rj类资源的进程Pk。若Pk处于等待资源

17、状态，则剥夺Pk的rj分给Pi；若Pk处于不等待资源状态，则置Pi于等待资源状态 (此时Pi原占有的资源可能被剥夺。)注剥夺资源时，需保存中间信息。因使用资源的进程尚未主动释放资源，这样开销很大。故只宜在CPU和主存这类重要资源的管理上使用。不宜剥夺临介资源等类型资源。(4) 破坏循环等待条件 采用资源顺序分配法，可以破坏循环等待条件。该方法首先给系统中的资源编号 (唯一)，即寻找一个函数F：RN (R：表资源类集合) 即 r1, r2, ri F(ri) = i 12 i 每个进程只能按序号由小到大的顺序申请资源，而且对它所必须使用的且属于某一类的所有资源，必须一次申请完。 比如：某一进程已

18、占有资源r1, r2, , ri，又申请ri+1，资源分配程序则检查是否有对于任意j1,2,i，有F(rj) F(rj+1)，若不满足则拒绝分配。 采用资源顺序分配法，系统不会出现循环等待。因为在任何时刻，总有一个进程占有较高序号的资源，该进程继续请示的资源必然是空闲的。故该进程可一直向前推进。(换言之，系统中总有进程可以顺序运行完毕，这个进程执行结束后会释放它所占有的全部资源唤醒等待中的进程或满足其它进程的请求。)优点：有序资源分配法提高了资源利用率(比静态法)缺点：顺序号与实际需要资源的顺序不一致，导致资源的浪费。例：输入机1，打印机2，穿孔机3，磁盘机4 某进程使用 32，而23长期搁置

19、。事实上用户使用的资源通常是有一定顺序的。2.避免死锁 死锁四个必要条件 (互斥、占有等待、非剥夺、循环等待) 死锁预防是严格破坏4个必要条件之一，一定不出现死锁；而死锁的避免是不那么严格地限制死锁必要条件的存在 ，其目的是提高系统的资源利用率。万一当死锁有可能出现时，就小心避免这种情况的发生。 每次进行资源分配时，需要通过判断系统状态来决定这次分配后，是否仍存在一条确保系统不会进入死锁状态的路径，否则不予分配。避免死锁的算法：银行家算法假设有三个进程P、Q、R，系统只有某类资源共10个，而三个进程合计申请资源数为20个。目前的分配情况如下：此后P、R再申请资源就不能分配了。因为现在只剩下2个

20、资源，不能满足它们的最大要求 (P:4, R:7)，如果将剩下2个分配给P或R，则会产生死锁。然而将2个资源分给Q (只需一个)则此后可将4个资源分组P 即 Q P R由此可见，按银行家算法来分配资源是不会产生死锁的。因为按该算法分配资源时，每次分配后总存在一个进程，如果让它独立单独运行下去，必然可获得它所需的全部资源，也就是说它能结束。而它结束后可以归还这类资源来满足其它申请者的需要。这也说明了存在一个合理的系统状态序列，可确保系统不会进入死锁状态的路径。单一种类资源引出的银行家算法的基本思想也同样适用于多种类的资源情况：还需(剩余需求)矩阵总共资源数 r = (6, 3, 4, 2)已分资

21、源数 s = (5, 3, 2, 2)余下资源数 t = (1, 0, 2, 0)先做 D 做完后余下资源数：t = (2, 1, 2, 1)再做 A 做完后余下资源数：t = (5, 1, 3, 2)再做 B 做完后余下资源数：t = (5, 2, 3, 2)再做 C 做完后余下资源数：t = (6, 3, 4, 2)再做 E 做完后余下资源数：t = (6, 3, 4, 2) (1) 寻找剩余矩阵的某一未标记的行x，使得它的每一个元素都不大于向量t 的对应元素，如果找不到转(4)。 (2) 对于找到的行x，表示可以满足它，标记此进程，并将它占有的资源加到向量t。 (3) 重复上述步骤，转(

22、1)。(4) 如果所有进程都已标记，则状态是安全的，否则为不安全。（4）死锁的检测和恢复资源简化图矩阵简化法还需(剩余需求)矩阵总共资源数 r = (6, 3, 4, 2)已分资源数 s = (5, 3, 2, 2)余下资源数 t = (1, 0, 2, 0)先做 D t = (2, 1, 2, 1)死锁的恢复一旦发现死锁及时排除，是有关排除死锁的研究。当前系统中使用的死锁恢复办法有两种：(进程撤消，资源剥夺)（1）强制性地从系统中撤消进程，并剥夺它们的资源给剩下的进程使用。(使前面的工作全部损失)(2) 使用一个有效的挂起和解挂机构来挂起一些进程。其实质是从被挂起的进程那里抢占资源以解除死锁

23、。(即可从死锁中恢复，又使进程的损失最小)3.3.5 多道程序设计基础并行程序设计1顺序程序设计（1）顺序性：程序运行时必须严格按照程序所规定的顺序执行。（2）封闭性：（程序在运行时独占全机资源）程序运行结果和它执行的速度无关。（3）可再现性：当对某一程序重复执行时，只要其初始条件相同，必将获得相同的结果。这对程序员检测，校正程序的错误带来很大的方便。2并行程序设计（1） 并行性：多个或程序段可以并行执行，在单处理器系统中即可互相切换。（并发性）（2） 共享性：系统中各程序不但共享硬件资源，而且共享软件资源（程序副本和数据集）。（3） 同步与互斥：这是并行性和共享性带来的必然结果，3并行程序设

24、计语言（1） 同步问题生产者和消费者问题task BUFFER isentry PUT(C:in character); entry GET(C:out character);end BUFFER;task body BUFFER is BUF: character;Beginloopaccept PUT(C:in character) do BUF: =C;/语句体/ End PUT;accept PUT(C:out character) do C: =BUF;/语句体/end GET;end loop;end BUFFER;task PRODUCER;task body PRODUCER

25、isC: character;BeginloopPRODUCER (C:);/生产产品/BUFFER.PUT(C);/放入缓冲区/end loop;end PRODUCER;task CONSUMER;task body CONSUMER isC: character;BeginloopBUFFER.GET(C);/取产品/CONSUMER (C:);/消费产品/end loop;end CONSUMER;(2)互斥问题task CONTROL isentry SECURE;entry RELEASE;end CONTROL;task body CONSUMER isBeginloopaccept SECURE；accept RELEASE；end loop;end CONTROL;task P1； task body P1 isBeginloopCONTROL .SECURE；Count :=count+1; 临界区CONTROL .RELEASE；end loop;end P1;task P1； task body P2 isBeginloopCONTROL .SECURE；Count :=count+1; 临界区CONTROL .RELEASE；end loop;end P2;