[高等教育]自考操作系统概论-第2章

第二章 处理器管理,2.1 多道程序设计,首先描述程序的顺序和并发执行方式2.1.1 程序的顺序执行 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。,2.1.1 程序的顺序执行,例：讨论单道系统的工作情况 对用户作业的处理 首先输入用户的程序和数据 然后进行计算 最后打印计算结果 即有三个顺序执行的操作 I：输入操作 C：计算操作 P：输出操作,2.1 多道程序设计,2.1.2 程序的并发执行程序的并发执行例： 在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi (i=1,2,3,.,n)。 这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。,2.1.2 程序的并发执行,例如: I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2，I3与P1是可以同时执行的。.,2.1.3 多道程序设计,P15,2.2 进程的概念,操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。,要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引入新的概念,2.2.1 进程的定义,行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw)进程是执行中的程序。（Ken Thompson and Dennis Ritchie )进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。,进程的定义：把一个程序在一个数据集上的一次执行 称为一个进程（process)。,2.2.2 为什么要引入进程,提高资源利用率正确描述程序的执行情况,2.2.3 进程的属性,1.进程是动态的，它包含了数据和运行在数据集上的程序2.多个进程可以含有相同的程序3.多个进程可以并发执行4.进程有三种基本状态,2.2.3 进程的属性,4. 进程的三种基本状态(1)就绪状态(Ready) 进程已获得除CPU之外的所有必需的资源，一旦得到CPU控制权，立即可以运行。(2)运行状态(Running) 该进程已获得运行所必需的资源，它的程序正在处理机上执行。 (3)等待（阻塞）状态(Waiting,Blocked) 正在执行的进程由于发生某事件而暂时无法执行时，便放弃处理机而处于暂停状态，则称该进程处于阻塞状态或等待状态。就绪队列与阻塞队列,2.2.3 进程的属性,进程的三种基本状态以及各状态之间的转换关系,2.2.3 进程的属性,进程的特征,进程的特征,动态性-最基本特征,进程：进程实体的一次执行过程，有生命周期。程序：程序是一组有序指令的集合，是静态的概念。,并发性,异步性,多个进程实体同存于内存中，在一段时间内同时运行 程序不能并发执行,进程按各自独立的、不可预知的速度向前推进,2.3 进程控制块,1. 进程控制块的作用 存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。 进程控制块是进程存在的唯一标志。 系统的所有PCB组织成链表或队列，常驻内存的PCB区。,2.3 进程控制块,2. 进程控制块中的信息1) 进程标示符 每个进程都必须有一个唯一的标识符内部标示符外部标示符2) 处理机状态 处理机状态信息主要由处理机的各种寄存器中的内容组成。处理机运行时的信息存放在寄存器中，当被中断时这些信息要存放在PCB中。,通用寄存器 指令计数器程序状态字PSW 用户栈指针,2.3 进程控制块,3) 进程调度信息进程状态进程优先级进程调度所需的其他信息事件4) 进程控制信息程序和数据的地址进程通信和同步机制资源清单链接指针,进程控制（P21）,对系统中的全部进程实施有效的管理，负责进程状态的改变。进程的创建1. 进程图 描述进程的家族关系的有向树 进程Pi创建了进程Pj，则Pi是Pj的父进程， Pj是Pi的子进程，用一条由进程Pi指向进程Pj的有向边来描述。 创建父进程的进程为祖进程，由此形成进程树，树根为进程家族的祖先。,内核完成,进程控制,2. 引起创建进程的事件,3. 进程的创建,在多道程序环境中，只有进程才能在系统中运行。,操作系统发现要求创建新进程的事件后，调用进程创建原语Creat()创建新进程。,创建过程,(1) 申请空白PCB,(2) 为新进程分配资源,(3) 初始化进程控制块,(4) 将新进程插入就绪队列,进程控制,进程的撤销,1. 引起进程终止的事件,正常结束,异常结束,外界干预,越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障,操作员或操作系统干预父进程请求父进程中止,2. 进程的终止过程,(1) 根据被终止进程的标示符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，置调度标志为真，用于指示该进程被终止后应重新进行调度。(3) 若该进程有子孙进程，应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4) 将被终止进程所拥有的全部资源，或归还其父进程，或归还系统。(5) 将被终止进程的PCB从所在队列或链表中移出，等待其他程序搜索信息。,进程控制,进程的阻塞与唤醒,1. 引起进程阻塞和唤醒的事件,2. 进程阻塞过程,调用阻塞原语BLOCK()阻塞自己中止调用进程的执行，将PCB中的状态改为阻塞，并加入到阻塞队列中；最后转进程调度。,3. 进程唤醒过程,阻塞进程等待的事件发生，有关进程调用唤醒原语WAKEUP()把等待该事件的进程唤醒。 唤醒原语的执行：把阻塞进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态改为就绪，将PCB插入到就绪队列中,阻塞原语与唤醒原语作用相反，成对使用,2.4 进程队列,进程控制块的组织方式,1) 链接方式,把具有统一状态的PCB用其中的链接字链接成一个队列。就绪队列 若干个阻塞队列 空白队列,2) 索引方式,系统根据所有进程的状态建立几张索引表，把各表的内存首地址记录在内存的专用单元中。索引表的表目中记录了相应状态的某个PCB在PCB表中的地址。,2.5 中断和中断处理,2.5.1 中断2.5.2 中断类型2.5.3中断响应2.5.4中断处理,2.5.1 中断,由于某些事件的出现，中止现行进程的运行，而由操作系统去处理出现的事件，待适当的时候让被中止的进程继续运行，这个过程称为中断。引起中断的事件称为中断源。对出现的事件进行处理的程序称为中断处理程序。,2.5.2 中断类型,（1）硬件故障中断（2）程序中断（3）外部中断（4）输入/输出中断（5）访管中断,强迫性中断事件,自愿性中断事件,2.5.3中断响应（P24）,当前PSW,旧 PSW,新 PSW,2.5.4中断处理（P25）,（1）硬件故障中断事件的处理-人工干预，输出故障信息。（2）程序中断事件的处理-转交用户自行处理（3）外部中断事件的处理-例行程序（4）输入/输出中断事件的处理-IO正常结束、IO异常结束（5）访管中断事件的处理-系统功能调用,2.6 处理器调度（P26）,在多道程序环境下，进程数目往往多于处理机数目。这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能，在很大程度上取决于处理机调度的性能。因此，处理机调度便成为OS设计的中心问题之一。,高级、中级和低级调度,一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。,高级调度（High Scheduling）,又称为作业调度或长程调度（Long-Term Scheduling），用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。因此有时也称作业调度为接纳调度（Admission Scheduling）。,高级调度（High Scheduling）,作业作业步典型的作业可分成三个作业步：编译-链接装配-运行作业流（后备队列）作业控制块JCB(job control block),高级调度（High Scheduling）,在批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度。在分时系统中为做到及时响应，作业被直接送入内存，故不需作业调度。在实时系统中，通常也不需作业调度。,高级调度（作业调度）,在每次执行作业调度时，都须作出两个决定：接纳多少作业每次接纳多少作业进入内存，取决于多道程序度，即允许多少个作业同时在内存中运行。多道程序度的确定应根据系统的规模和运行速度等情况综合考虑。接纳哪些作业应接纳哪些作业从外存调入内存，取决于所采用的调度算法。如先来先服务，短作业优先等。,低级调度（Low Level Scheduling）,通常也称为进程调度或短程调度（Short-Term Scheduling），用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。进程调度是最基本的一种调度，在三种OS中都有。,低级调度的功能,（1）保存处理机的现场信息。（2）按某种算法选取进程（3）把处理器分配给进程,进程调度的三个基本机制,（1）排队器（2）分派器（分派程序）（3）上下文切换机制,低级调度（Low Level Scheduling）,抢占方式（Preemptive Mode） 这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将以分配给该进程的处理机重新分配给另一进程。抢占的原则有：优先权原则。优先权高的可以抢占优先级低的进程的处理机。短作业（进程）优先原则。短作业（进程）可以抢占长作业（进程）的处理机。时间片原则。各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。,中级调度（Intermediate-Level Scheduling）,中级调度又称中程调度（Medium-Term Scheduling）引入中级调度的目的，是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调之外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能。,具有高级和低级调度的调度队列模型,在批处理系统中，不仅需要进程调度，而且还需要作业调度，由后者按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度算法按照一定的进程调度算法，选择一个进程，把处理机分配给该进程。下图示出具有高、低两级调度的调度队列模型。,具有高级和低级调度的调度队列模型,具有高级和低级调度的调度队列模型,具有高低两级调度的调度模型与仅有进程调度的调度模型的主要区别在于：就绪队列的形式。在批处理系统中，最常用的是最高优先权优先调度算法，因此最常用的就绪队列形式是优先权队列。设置多个阻塞队列。对于小型系统可只设置一个，但对于较大系统要设置多个阻塞队列以保证效率。每个队列对应于某一种进程阻塞事件。,2.6.1 处理器的两级调度（P26）,作业调度进程调度,2.6.2 作业调度算法,设计调度算法的原则：公平性平衡资源使用极大地流量,选择调度方式和调度算法的若干准则,在一个OS的设计中，应如何选择调度方式和算法，很大程度上取决于OS的类型和目标。如在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。选择的准则，有的是面向用户的，有的是面向系统的。,面向用户的准则,周转时间短 周转时间 平均周转时间 带权周转时间 平均带权周转时间响应时间快 响应时间截止时间的保证 截止时间优先权准则,评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。,从作业被提交给系统开始，到作业完成为止的这段时间间隔。,作业的周转时间与系统为他提供服务的时间之比,评价分时系统的性能、选择进程调度算法的重要准则之一。,提交请求到显示结果,评价实时系统的性能、选择实时调度算法的重要准则。,面向系统的准则,系统吞吐量高处理机利用率好各类资源的平衡利用,评价批处理系统的性能的另一个重要指标、选择批处理作业调度的重要准则。,单位时间内系统所完成的作业数,衡量系统性能的十分重要的指标,1、先来先服务算法 FCFS,是一种最简单的调度算法。当在作业调度中采用该算法时，每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。,先来先服务算法例题（P28）,主存空间为100K,先来先服务算法平均周转时间=1.2,2、计算时间短的作业优先算法,短作业优先（SJF）的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。进程调度仍按装入的次序让它们依次占用处理器。,计算时间短作业优先算法平均周转时间=1.16,P30,SJF调度算法的优缺点：优点：有效降低作业的平均等待时间，提高系统吞吐量。缺点：1.对长作业不利。2.该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。3.由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。,3、响应比高者优先算法,响应比=等待时间、计算时间调度在全部作业到达输入井之后开始,4、 优先级调度算法,确定进程优先权的依据有如下三个方面：进程类型：一般来说系统进程高于用户进程。进程对资源的需求：如进程的估计时间及内存需要量的多少，对要求少的进程赋予较高优先权。用户要求：由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。,5、均衡调度算法（P31),2.6 进程调度算法（P31),引起进程切换的原因：（1）一个进程从运行状态变成等待状态（2）一个进程从运行状态变成就绪状态（3）一个进程从等待状态变成就绪状态（4）一个进程完成工作后撤销调度算法： （P31-32）1 先来先服务调度算法2 最高优先级优先调度算法3 时间片轮转调度算法,调度算法例题,在单CPU和两台输入/输出设备（I1,I2)的多道程序设计环境下，同时投入3个作业JOB1,JOB2,JOB3运行。这3个作业对CPU和输入/输出设备的使用顺序和时间如下所示：JOB1:I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms)JOB2:I1(20ms);CPU(20ms);I2(40ms)JOB3:CPU(30ms);I1(20ms);CPU(10ms);I1(10ms)假定CPU，I1，I2都能并行工作，JOB1优先级最高，JOB2次之，JOB3优先级最低，优先级高的作业可以抢占优先级低的作业的CPU但不抢占I1和I2。试求：（1）3个作业从投入到完成分别需要的时间；（2）从投入到完成的CPU的利用率；（3）I/O设备利用率。,调度算法例题,JOB1从投入到运行完成需要110ms, JOB2从投入到运行完成需要90ms, JOB3从投入到运行完成需要110ms.Cpu利用率： （110-30）/110=72.7%I1的利用率： （110-30）/110=72.7%I2的利用率： （110-20）/110=81.8%,2.7 线程的概念（P33）,2.7.1 线程的基本概念1. 线程的引入引入进程的目的： 使多个程序能并发执行，提高资源利用率和系统吞吐量。引入线程的目的： 减少程序在并发执行时所