操作系统期末论文一、处理机简述处理机是计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。

处理机包括中央处理器，主存储器,输入-输出接口。

处理机加接外围设备就构成完整的计算机系统。

处理机的处理能力有多种指标和参数。

通常用每秒最快执行的百万条指令数(MIPS)来度量。

对具有向量处理能力的处理机，则用每秒最多能给出的百万个浮点处理结果数（MFLOPS）来度量。

此外，还常用处理数据率(PDR)来评价处理机的处理能力。

处理数据率(PDR)的定义是执行每条指令传送的平均位数与指令处理平均速率的乘积。

处理机的操作是首先将用户程序和数据通过输入－输出设备输入到主存储器（主存）或辅助存储器。

中央处理器从主存取出指令，完成对指令的解释，执行控制操作；若是运算型指令，还须从主存取出数据，由运算器完成运算。

结果通常暂存在运算器或送回主存。

处理机执行程序过程涉及输入-输出操作、主存-辅存的信息交换，这些都要经过输入、输出接口部件。

处理机与外界的这种信息交换有三种方式。

①中断方式：即程序I／O。

每传送一个位组（如一个字或字节）产生一次中断,由CPU执行相应的中断程序完成。

这种方式主要用于慢速输入-输出设备。

②直接存储器存取(DMA)方式:在硬件线路控制下直接在快速输入-输出设备和主存之间完成一条输入－输出指令规定的信息量交换。

③通道控制方式：各通道各有自己的通道程序,实现输入-输出指令规定的主存和输入-输出设备之间的信息交换。

从系统结构角度，按处理机执行的指令流和与指令流相关的数据流的关系，有单指令流单数据流（SISD）处理机、单指令流多数据流（SIMD）处理机和多指令流多数据流（MIMD）处理机。

SISD处理机的程序是按单一指令序列执行的，操作数据亦按对应的指令确定的单一顺序逐个处理。

大多数处理机都属于这一类。

SIMD和MIMD处理机又称并行处理机。

并行处理机的目的在于提高处理机的数据处理能力。

SIMD处理机以处理向量数据为主，故又称向量处理机。

其中以单个指令执行部件和多个相同的运算处理器构成的处理机称为阵列（式）处理机。

以生产流水线方式组织指令部件(称先行控制)和运算功能部件的SIMD处理机，称为流水线处理机。

联想处理机则是采用按内容检索的联想存储器为主要特征的SIMD处理机。

至于MIMD处理机，实际上是多处理机系统，它是多个相同的处理机通过公共主存储器相互耦合构成有多重处理能力的系统。

二、处理机调度简述在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。

处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

处理机调度的功能一般情况下，当占用处理机的进程因为某种请求得不到满足而不得不放弃CPU进入等待状态时，或者当时间片到，系统不得不将CPU分配给就绪队列中另一进程的时候，都要引起处理机调度。

除此之外，进程正常结束、中断处理等也可能引起处理机的调度。

因此，处理机调度是操作系统核心的重要组成部分，它的主要功能如下：（1）记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息，将这些信息记录在相应的进程控制块中。

（2）根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间。

（3）收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候，保存该进程的现场，并收回处理机。

处理机调度的功能中，很重要的一项就是根据一定算法，从就绪队列中选出一个进程占用CPU运行。

可见，算法是处理机调度的关键。

处理机调度的性能准则处理机调度，有许多不问的调度算法，不同的调度算法具有不同的特性。

因此，在介绍算法之前，先介绍衡量一个算法的基本准则。

衡量和比较调度算法性能优劣主要有一下几个因素：（1）CPU利用率。

CPU是计算机系统中最重要的资源，所以应尽可能使CPU 保持忙，使这一资源利用率最高。

（2）吞吐量。

CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。

（3）周转时间。

指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。

（4）等待时间。

处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。

因此，衡量一个调度算法优劣常常简单的考察等待时间。

（5）响应时间。

指从作业提交到系统作出相应所经过的时间。

在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即响应时间。

从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。

三、单处理机调度相关算法在操作系统中调度的实质是一种资源分配,因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法。

对于不同的系统和系统目标, 通常采用不同的调度算法。

1 常用的几种处理机调度算法1．1先来先服务调度算法:这是一种比较简单的调度算法,是将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列,并按照先来先服务的方式进行调度处理。

2)短进程优先调度算法:是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它建立执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时, 再重新调度。

3 )时间片轮转调度算法:系统将所有的就绪进程按先来先服务原则,排成一个队列,每次调度时把CPU 分配给队首进程, 并令其执行一个时间片。

当执行的时间片用完时, 由一个计时器发出一个时钟中断,调度程序便据此信号来停止该进程的执行,并将它送就绪队列的末尾,等待下一次执行,然后把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。

4)优先权调度算法: 每当进行调度时,选择就绪队列中优先权最高的进程投入运行。

有静态优先权和动态优先权之分。

静态优先权是在创建进程时确定的,且规定它在进程的整个运行期间保持不变;动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进而改变, 以便获得更好的调度性能。

5 )多级反馈队列调度算法:建立多个不同优先权及时间片的就绪队列,新就绪进程进入第一级就绪队列。

CPU 优先选择第一级就绪队列中的进程,若在一个时间片内进程未结束,则进入下级就绪队列的队尾。

在服务的过程中,如出现新的就绪进程,若采用非抢占方式,正在执行的进程完成规定时间片后,再为新进程提供服务; 若采用抢占方式, C P U 完成单位时, 立即为新出现的进程服务。

2 调度算法性能的评价周转时间对于一个进程来说,它的周转时间是从它第1 次进入就绪队列开始,到进程运行完毕所经历的时间。

(1)作业的平均周转时间T,对每个用户而言, 都希望自己作业的周转时间最短。

但作为计算机系统的管理者而言, 总希望使多个作业的平均周转时间最短,因为这不仅会有效地提高系统资源利用率,而且还可使大多数用户满意。

作业平均周转时间可用来衡量不同调度算法对同一作业流的调度性能。

作业平均周转时间T 的公式如下:其中n 是被测定的作业流中的作业数;Ti是该作业流中第i 个作业的周转时间,即该作业的完成时刻Tci与提交作业完毕时刻Tsi之差,也就是第i 个作业执行时间与等待时间之和。

(2)作业平均带权周转时间W,作业i 的带权周转时间Wi是作业i周转时间Wi与作业i实际运行时间TRi 之比,即,而作业平均带权周转时间W 的公式为:作业平均带权周转时间是用来衡量某种调度算法对不同作业流的调度性能,这是因为W 反应了作业对单位执行时间所付出的平均等待时间。

3几种调度算法的优缺点1)先来先服务调度算法比较简单容易实现,但是效率比较低,其平均周转时间和平均带权周转时间都比较长,并且不利于短进程;2)短进程调度算法效率比较高,也充分考虑了短进程,但该算法对长进程非常不利,并且该算法完全未考虑进程的紧迫程度,因而不能保证紧迫型进程会得到及时处理;3)时间片轮转法简单易行,平均响应时间短,但不利于紧急进程的处理;4)静态优先权调度算法简单易行、系统开销小,但是不太灵活,很可能会出现低优先权的进程长期得不到调度而等待的情况;动态优先权调度算法比较灵活、科学, 可以防止有些进程一直得不到调度,也可防止有些进程长期垄断处理机,但是系统动态地确定进程的优先级需要花费相当多的程序执行时间,因而花费的系统开销比较大;5)多级反馈队列调度算法性能比较好,它能较好地满足了终端型、短批处理、长批处理任务的要求, 是目前比较常用的调度算法。

四、单处理机调度相关算法多处理机系统是提高计算机速度、功能、可靠性和性能价格比的一个重要发展方向.多处理机系统与单处理机相比最显著的特点就是任务运行的并发性. 如何将多个任务巧妙地分配到多个处理机上高并行度地运行就是多处理机调度算法所研究的主要课题, 调度算法的优劣是决定多处理机系统效率的关键.在多处理机系统中通常存在多个相同或不同的处理机, 而所处理的作业可能含有多个并发的、数据相关或数据独立的任务. 通常以表示偏序任务集的前趋图作为调度的初始依据。

（1）多处理机的几种相关任务调度算法1）LEVEL 调度算法LEVEL 调度算法的主要依据是任务系统前趋图中各节点任务的位级.定义位级(LEVEL) , 对于偏序任务系统(T , < ) 的前趋图G , 定义位级如一下:1.无后继的节点任务的位级等于其权量2.具有后继的节点任务, 其位级等于本节点的权量加上该节点的直接后继位级的最大值LEVEL 调度算法:在多处理机系统中, 每当一个处理机变为空闲时, 就给它分配一个处于最高位级的等待执行的就绪任务定理假设任务系统( T , < ) 的前趋图G 是一棵树( 或森林) , 各任务具有相等的执行时间, 则LEVE L 算法是最佳的非抢先调度算法LEVEL 调度算法的时间复杂性是0 ( n) 。

LEVEL 调度算法是一个典型的列表调度算法. 图1 的调度实例表明了它的工作原理。

2）LABEL 调度算法COFFMAN 和G RAHAM 提出的L A B E L 调度算法是: 假设(T ,< ) 是含有n 个任务的U E T 系统, 正整数集合{1 , 2 , ⋯, n} 中的标号分配给T 中的每个任务的规则如下:1.分配标号1 到( T , < ) 中的一个出节点( 无后继的节点) 任务。

2. 假设标号1, 2 ,⋯, j-1 已被分配且令R 是尚未分配标号的任务( 但它们的后继节点任务已经全部标号) 的集合.则把标号j 分配给R 中的某一个元素X , 使得L ( X ) <=L ( X’) 。

其中X’是R 中除x 外的任何其它元素之一, L ( X ) 为X 直接后继标号的递减偏序。