江南大学操作系统复习提纲.pdf

江南大学计算机考研辅导操作系统 操作系统考研复习提纲操作系统考研复习提纲 一、一、操作系统概述操作系统概述（一）操作系统的概念、特征、功能和提供的服务(1)牢固掌握操作系统的定义：计算机操作系统是方便用户、管理和控制计算机软、硬件资源的系统（或程序集合）；清楚地了解操作系统所处的地位：是裸机之上的第一层软件，是建立其他所有软件的基础。(2)记住操作系统的基本特征：并发、共享和异步性。理解模拟：并发“大家一起前进了”；共享“一件东西大家用”；异步性“你走我停”。(3)牢固掌握操作系统的五大主要功能：存储器管理、处理机管理、设备管理、文件管理、用户接口管理。(4)操作系统的服务：1 公共服务类型。程序执行、I/O 操作、文件系统操作、通信和差错检测。2 系统调用。(5)研究操作系统面对用户的服务观点和系统内部的管理观点。即为用户提供方便而安全的工作环境，体现“用户至上”、“服务至上”的原则；内部管理采用中断、通道、串行、并发、并行和本地远地通信等分设的各种管理部门机构；里外协作分工组织，力争达到“多快好省”。(6)了解现代操作系统为用户提供的三种使用界面：命令界面、系统调用界面和图形界面。一般用户通过命令、图形方式控制，编程人员通过系统调用方式控制计算机。（二）操作系统的发展与分类(1)操作系统的形成和五大类型（批处理操作系统、分时操作系统、实时操作系统、网络操作系和分布式操作系统）(2)计算机操作系统的 4 个发展阶段 手工操作阶段（对应第一代计算机），早期批处理和执行系统（对应第二代计算机），批量操作系统、分时操作系统（对应第三代计算机），个人计算机操作系统、网络操作系统、分布式操作系统（对应现在的第四代计算机）批量操作系统的主要特征和优缺点:批量操作系统的的主要特征是“批量”，优点是系统吞吐率高，缺点是对用户的响应时间较长，用户不能及时了解和控制自己的程序的运行 分时系统的主要特点:1 多路性 2 独占性 3 交互性 实时操作系统的特点以及与分时系统的区别:1 系统对外部实时信号必须能及时响应，响应的时间间隔要足以能够控制发出实时信号的那个环境 2 系统要求有高可靠性和安全性，效率则放在第二位 3 系统整体性强，要求所管理的联机设备和资源，必须按一定的时间关系和逻辑关系协调工作 4 实时操作系统没有分时操作系统那样强的交互会话能力，通常不允许用户通过实时终端设备去编写新的程序或修改已有的程序，终端设备只作为执行装置或询问装置。计算机网络和网络操作系统:1江南大学计算机考研辅导操作系统 网络的组成：若干主机、一个通信子网和一系列协议 网络操作系统除了具备一般操作系统赢具有的功能模块外，还要增加网络通信模块。提供以下能力：1 允许用户访问网络主机中各种资源 2 对用户访问进行控制仅允许授权用户访问特定的资源3对远程资源的利用如同本地资源一样4提供全网统一的记帐方法5联机提供最近网络说明资料 6 提供比单机更可靠的操作 （三）操作系统的运行环境(1)处理机的状态和特权指令 简单的系统可只分为管态和用户态，特权指令是指计算机中不允许用户直接使用的指令。特权指令包括下面功能：1 允许和禁止中断 2 在进程之间切换处理机 3 存取用于主存保护的寄存器 4 执行 I/O 操作 5 停止一个处理机的工作(2)存储器和存储器的组织 两种类型：ROM 和 RAM，三级组织体系：主存储器、辅助存储器和高速缓冲存储器(3)中断和中断系统。中断的概念是指某个事件发生时，系统中止现行程序的运行，引出处理事件程序对该事件进行处理，处理完毕后返回断点处继续执行。中断系统是指发现中断源而产生中断过程的设备，又称中断装置。(4)向量中断和中断向量 当中断发生时，由中断源自己引导处理机进入中断服务程序的中断过程称为向量中断。在向量中断中，系统为每个中断类型都设置一个中断向量，用来存放该类型中断的中断服务例行服务程序的入口地址和程序状态字。习题 1、教材中介绍了学习“操作系统”要记住最精髓的两句话，是什么？答：计算机操作系统使方便用户、管理和控制计算机软硬件资源的系统软件（或程序集合）；操作系统目前有五大类型（批处理、分时、实时、网络和分布式）和五大功能（作业管理、文件管理、存储管理、设备管理和进程管理）。2、分时系统和实时系统有什么不同？答：分时系统通用性强，交互性强，及时响应性要求一般（通常数量级为秒）；实时系统往往是专用的，系统与应用很难分离，常常紧密结合在一起，实时系统并不强调资源利用率，而更关心及时响应性（通常数量级为毫秒或微秒）、可靠性等。3、多用户操作系统和网络操作系统有什么区别？答：以单机多用户系统为例，说明它与网络操作系统的比较。单机多用户系统 网络操作系统 CPU 共用一个或几个 多个处理机 共享资源 共享主存 共享服务器 终端工作 分时方式 网址通信链接 2江南大学计算机考研辅导操作系统 客户端工作 不能独立工作 客户机能独立工作 操作系统 集中管理 客户机有独立的操作系统 4、操作系统负责管理计算机系统的（），其中包括处理机、存储器、设备和文件。A.程序 B.文件 C.资源资源 D.进程 5、没有下列（）设备计算机无法工作。A.硬盘 B.软盘 C.内存内存 D.打印机 6、操作系统是计算机系统的核心软件。按功能特征的不同，可把操作系统分为1、2、3、网络操作系统和分布式操作系统基本类型。其中1的主要目标是提高系统的吞吐率和效率，而2是一旦有处理请求和要求处理的数据时，CPU 就应该立即处理该数据并将结果及时送回，例如4等。供选择的答案：123 A、单用户系统 B、批处理系统B、批处理系统 C、分时系统 C、分时系统 D、微机操作系统 E、实时系统 E、实时系统 4 A、计算机激光照排系统 B、办公自动化系统 C、计算机辅助设计系统 D、航空订票系统 D、航空订票系统 7、操作系统是一种（）。A.应用软件 B.系统软件 B.系统软件 C.通用软件 D.工具软件 8、在下列性质中，哪一个不是分时系统的特征。（）A.交互性 B.多路性 C.成批性C.成批性 D.独占性 9、实时操作系统追求的目标是（）。A.高吞吐率 B.充分利用内存 C.快速响应快速响应 D.减少系统开销 10、操作系统是为了提高计算机的1和方便用户使用计算机而配置的基本软件。它负责管理计算机系统中的2，其中包括3，4，外部设备和系统中的数据。操作系统中的3管理部分负责对进程进行管理。操作系统对系统中的数据进行管理的部分通常叫做5。供选择的答案：1 A、速度 B、利用率B、利用率 C、灵活性 D、兼容性 2 A、程序 B、功能 C、资源 C、资源 D、进程 34 A、主存储器 A、主存储器 B、虚拟存储器 C、运算器 D、控制器 E、微处理器 F、处理机 F、处理机 5 A、数据库系统 B、文件系统 B、文件系统 C、检索系统 D、数据库 E、数据存储系统 F、数据结构 G、数据库管理系统 11、现代操作系统的两个基本特征是（）和资源共享。A.多道程序设计 B.中断处理 C.程序的并发执行 C.程序的并发执行 D.实现分时与实时处理 12、以下（）项功能不是操作系统具备的主要功能。A内存管理 B中断处理 C文档编辑文档编辑 DCPU 调度 13、批处理系统的主要缺点是（）。3江南大学计算机考研辅导操作系统 A.CPU 的利用率不高 B.失去了交互性 失去了交互性 C.不具备并行性 D.以上都不是 14、引入多道程序的目的在于（）。A、充分利用 CPU，减少 CPU 等待时间 A、充分利用 CPU，减少 CPU 等待时间 B、提高实时响应速度 C、有利于代码共享，减少主、辅存信息交换量 D、充分利用存储器 15、（）没有多道程序设计的特点。A.DOSDOS B.UNIX C.Windows D.OS/2 16、DOS 是磁盘操作系统磁盘操作系统的缩写。17、下列四个操作系统中，是分时系统的为（）。A.CP/M B.MS-DOS C.UNIXUNIX D.WINDOWS NT 18、在分时系统中，时间片一定，（），响应时间越长。A.内存越多 B.用户数越多 用户数越多 C.后备队列 D.用户数越少 19、操作系统是一组（）。A.文件管理程序 B.中断处理程序 C.资源管理程序资源管理程序 D.设备管理程序 20、（）不是操作系统关心的主要问题。A、管理计算机裸机 B、设计、提供用户程序与计算机硬件系统的界面 C、管理计算机系统资源 D、高级程序设计语言的编译器 D、高级程序设计语言的编译器 二、二、进程管理进程管理（一）进程与线程 1.进程概念 2.进程的状态与转换 3.进程控制 4.进程组织 5.进程通信 共享存储系统；消息传递系统；管道通信。6.线程概念与多线程模型 (1)程序顺序执行的特点 1 顺序性 2 封闭性 3 可再现性(2)程序并发执行的特点 1 失去程序的封闭性 2 程序与计算不再一一对应 3 程序并发执行的相互制约(3)进程的定义、进程与程序的区别 进程即是一个具有独立功能的程序在某个数据集合的一次运行活动。4江南大学计算机考研辅导操作系统 进程的基本特征：动态性，并发性，独立性，异步性，结构性。(4)进程和程序是既有联系又有区别的两个概念：1 程序是指令的有序集合，本身没有任何运行的含义是一个静态的概念。而进程是程序在处理机上的一次执行过程，是个动态的概念。2 进程是一个能独立运行的单位，能与其他进程并行活动3进程是竞争计算机系统有限资源的基本单位4同一程序同时运行若干不同的数据集合上将属于不同的进程。(5)进程的基本状态及其变迁 三种基本状态：就绪、运行、等待，状态变迁是有方向的。(6)进程的描述 用进程控制块（PCB）来描述一个进程。从结构上来说，进程由一个程序段和一个进程控制块组成。(7)进程控制 所谓进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。进程创建、进程撤消、进程等待和进程唤醒等。由操作系统内核来实现。把系统态下执行的某些具有特定功能的程序段称为原语。原语可分为两类：一类是机器指令级的，其特点是执行期间不允许中断，正如在物理学中的原子一样，在操作系统中，它是一个不可分割的基本单位。另一类是功能级的，其特点是作为原语的程序段不允许并发执行。（8）进程组织 常用的组织方式有两种：链接方式、索引方式。（9）进程通信：指进程间的信息交换。按通信内容可以划分为 2 种：低级通信，高级通信 高级通讯机制类型：1 共享存储器系统(Shared-Memory System)：相互通讯的进程通过共享数据结构和存储区进行通讯 2 消息传递系统(Message passing System)：在消息传递系统中，进程间的数据交换是以消息(message，在计算机网络中又称报文)为单位。程序员直接利用系统提供的一组通讯命令（原语）来实现通讯。消息缓冲机制，信箱通信方式 3 管道(pipe)通信系统 管道（pipe）通讯由 UNIX 首创的一种借助文件和文件系统形成的一种通信方式，。由于其有效性，一些系统继 UNIX 之后相继引入了管道技术，如 pc-dos，管道通信将成为进程通讯的一种重要方式。消息缓冲通信机构是以内存缓冲区为基础。管道是以文件系统为基础。有名管道，无名管道（10）线程概念与多线程模型 5江南大学计算机考研辅导操作系统 线程是进程中的一个实体，是被系统独立调度和分配的基本单位，故又称为轻权（轻型）进程(Light Weight Process)，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。传统的进程称为重型进程(Heavy Weight Process)。习题 习题 1、什么是进程？答：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。（在 Windows NT 等采用微内核结构的现代操作系统中，进程的功能发生了变化：它只是资源分配的单位，而不再是调度运行的单位，其调度运行的基本单位是线程。）2、什么是线程？它与进程有什么关系？答：线程是进程中执行运算的最小单位，即处理机调度的基本单位。它与进程的关系是：一个线程只能属于一个进程，而一个进程可以有多个线程；资源分配给进程，同一进程的所有线程共享该进程的所有资源；处理机分给线程，即真正在处理机上运行的是线程；线程在运行过程中，需要协作同步，不同进程的线程间要利用消息通信的办法实现同步。特别注意的是：传统操作系统中的进程概念与现代操作系统中的进程概念不同简单说，传统操作系统中进程具有分配资源、调度运行两大功能，而现代操作系统中进程只作为分配资源单位，线程才作为调度运行单位。3、一个进程入睡时其断点落在何处？它被唤醒后从何处继续原来的执行？答：一个进程入睡是指该进程由于缺乏资源不能占用 CPU，进入等待状态。一个进程由程序、数据集合和进程控制块（PCB）组成。PCB 是进程存在的唯一标志。PCB 中包括如下内容：进程标志号、进程状态（执行/就绪/等待）、进程标志、进程优先数、程序地址、现场保护区（通常被保护的信息有程序计数器、程序状态字、各个工作寄存器等）、通信机构、其他信息等。处于睡眠状态的进程，它的断点在它的 PCB 中的现场保护区中保护起来。保存程序运行的 CPU 现场，以便在将来的某一时刻恢复并继续原来的运行。它被唤醒后，把它从等待进程队列中摘下，将进程状态改为就绪，然后将它插入到就绪队列中；等它占用 CPU 进入执行状态时，从断点处继续执行。4、进程之间有哪些基本的通信方式？它们分别有什么特点？适用于哪些场合？答：进程通信根据交换信息量的多少分为高级通信和低级通信。低级通信一般只传送一个或几个字节的信息，以达到控制进程执行速度的作用（如 PV 操作）；高级通信则要传送大量数据，目的不是为了控制进程的执行速度，而是为了交换信息。高级进程通信方式有很多种，大致可归并为三类：共享存储器、管道文件和消息传递。6江南大学计算机考研辅导操作系统 共享存储器：在内存种分配一片空间作为共享存储区。需要进行通信的进程把它附加到自己的地址空间中，不需要时则把它取消。管道文件：它是连接两个命令的一个打开文件。一个命令向该文件中写入数据，为写者；另一个命令从该文件中读出数据，为读者。消息传递：它以消息为单位在进程间进行数据交换。具体说明见教材“消息缓冲”。5、程序的并发并发执行是现代操作系统的基本特征之一，为了更好地描述这一特征而引入了进程进程这一概念。6、进程存在的标志是进程控制块 PCB进程控制块 PCB。7、进程的静态实体由程序，数据集合程序，数据集合和进程控制块 PCB进程控制块 PCB三部分组成。8、用于进程控制的原语主要有建立原语、撤消原语，挂起原语建立原语、撤消原语，挂起原语和激活原语激活原语。9、进程被创建后，最初处于就绪就绪状态，然后经进程调度程序进程调度程序选中后进入执行执行 状态。10、进程创建工作主要完成的是创建进程控制块（PCB），并把它挂到就绪就绪队列中。11、如果系统中有 n 个进程，则在就绪队列中进程的个数最多为n-1n-1。12、通常，线程的定义是是进程中执行运算的最小单位是进程中执行运算的最小单位。在现代操作系统中，资源的分配单位是进程进程，而处理机的调度单位是线程线程，一个进程可以有多个多个线程。13、计算机系统一般都设计有两种运行状态：用户态用户态和核心态核心态。14、操作系统中，可以并行工作的基本单位是1，1也是系统核心调度及资源分配的基本单位，它是由2组成的，它与程序的主要区别是3。供选择的答案：1：A.作业 B.函数 C.进程 进程 D.过程 2：A.程序、数据和 PCB程序、数据和 PCB B.程序、数据和标识符 C.程序、标识符和 PCB D.数据、标识符和 PCB 3：A.程序有状态，而它没有 B.它有状态，而程序没有 它有状态，而程序没有 C.程序可占用资源，而它不可 D.它可占用资源，而程序不可 15、下列进程状态的转换中，哪一个是不正确的（）。A.就绪执行 B.执行就绪 C.就绪等待就绪等待 D.等待就绪 16、下列各项步骤中，哪一个不是创建进程所必须的步骤（）。A.建立一个进程控制块 PCB B.由 CPU 调度程序为进程调度 CPU 由 CPU 调度程序为进程调度 CPU C.为进程分配内存等必要的资源 D.将 PCB 链入进程就绪队列 17、在下列特性中，哪一个不是进程的特性（）。A.异步性 B.并发性 C.静态性静态性 D.动态性 18、进程就是可与其他程序共行执行的程序段的一次执行过程，它是系统进行资源分配和调度的一个基本单位。进程具有1、2、调度性、异步性和结构性 5 个基本特征。进程是一次执行过程，具有生命期体现了进程的1特征。进程由程序段、3、4组成，其中4是进程在系统中存在的唯一标识。供选择的答案：12 A、动态性动态性 B、静态性 C、共行性 D、并发性并发性 E、可执行性 F、易用性 3 A、过程 B、数据数据 C、进程标识符 D、函数 4 A、FCB B、FIFO C、PCBPCB D、JCB 19、进程执行时的间断性，决定了进程可能具有多种状态。进程的基本状态有三种，在分时系统中，当一个进程拥有的时间片到时，则该进程即由1进入2。7江南大学计算机考研辅导操作系统 如果出现因某种原因使得处理机空闲时，则需要从就绪队列中选择一进程，并将处理机分配给它，此时该进程进入3，这个过程是由4来完成。供选择的答案：123 A、就绪状态就绪状态 B、静止状态 C、等待状态 D、执行状态执行状态 4 A、进程控制程序 B、资源分配程序 C、进程调度程序进程调度程序 D、处理机分配程序 20、为了描述进程的动态变化过程，采用了一个与进程相联系的（）系统，根据它而感知进程的存在。A.进程状态字 B.进程优先数 C.进程控制块 进程控制块 D.进程起始地址 21、已经获得除（）以外的所有运行所需资源的进程处于就绪状态。A.存储器 B.打印机 C.CPUCPU D.磁盘空间 22、进程是（）。A.与程序等效的概念 B.并发环境中程序的执行过程并发环境中程序的执行过程 C.一个系统软件 D.存放在内存中的程序 23、进程具有并发性和（）两大重要属性。A.动态性动态性 B.静态性 C.易用性 D.封闭性 24、操作系统在控制和管理进程过程中，涉及到（）这一重要数据结构，这是进程存在的唯一标 103、志。A.FCB B.FIFO C.FDT D.PCBPCB 25、并发性是指若干事件在（）发生。A.同一时刻 B.同一时间间隔内 同一时间间隔内 C.不同时刻 D.不同时间间隔内 26、顺序程序和并发程序的执行相比，（）。A.基本相同 B.有点不同 C.并发程序执行总体上执行时间快并发程序执行总体上执行时间快 D.顺序程序执行总体上执行时间快 27、在单一处理机上，将执行时间有重叠的几个程序称为（）。A.顺序程序 B.多道程序 C.并发程序并发程序 D.并行程序 28、引入多道程序技术后，处理机的利用率（）。A.降低了 B.有所改善 C.大大提高大大提高 D.没有变化，只是程序的执行方便了 29、在单一处理机上执行程序，多道程序的执行是在（）进行的。A.同一时刻 B.同一时间间隔内同一时间间隔内 C.某一固定时刻 D.某一固定时间间隔内 30、在单处理机系统中，处于运行状态的进程（）。A.只有一个只有一个 B.可以有多个 C.不能被挂起 D.必须在执行完后才能被撤下 31、如果某一进程获得除 CPU 外的所有所需运行资源，经调度，分配给它 CPU，该进程将进入（）。A.就绪状态 B.运行状态运行状态 8江南大学计算机考研辅导操作系统 C.等待状态 D.活动状态 32、如果某一进程在运行时，因某种原因暂停，此时将脱离运行状态，而进入（）。A.自由状态 B.停止状态 C.等待状态等待状态 D.静止状态 33、一个进程被唤醒意味着（）。A.该进程重新占有了 CPU B.进程状态变为就绪进程状态变为就绪 C.它的优先权变为最大 D.其 PCB 移至就绪队列的队首 34、进程从运行状态变为等待状态的原因是（）。A.输入或输出事件发生输入或输出事件发生 B.时间片到 C.输入或输出事件完成 D.某个进程被唤醒 35、在操作系统中同时存在多个进程，它们（）。A.不能共享系统资源 B.不能调用同一段程序代码 C.可以共享允许共享的系统资源 可以共享允许共享的系统资源 D.可以共享所有的系统资源 36、操作系统中有一组常称为特殊系统调用，它不能被系统中断，在操作系统中称为（）。A.初始化程序 B.原语 原语 C.子程序 D.控制模块 47、进程和程序的本质区别是（）。A.存储在内存和外存 B.顺序和非顺序执行机器指令 C.分时使用和独占使用计算机资源 D.动态和静态特征动态和静态特征 （二）处理机调度 1.调度的基本概念 2.调度时机、切换与过程 3.调度的基本准则 4.调度方式 5.典型调度算法 先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。1 一般来说，计算机中的调度可分为 4 级 作业调度：又称为“宏观调度”、“高级调度”。按一定的原则对外存输入井上的大量后备作业进行选择，给选定的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，使得该作业的进程获得竞争处理机的权利。交换调度：又称为“中级调度”。按照给定的原则和策略，将处于外存交换区中的就绪状态或就绪准等待状态的进程调入内存，或把处于内存就绪或内存等待状态的进程交换到外存交换区。进程调度：又称为“微观调度”、“低级调度”。按照某种策略和方法选取一个处于就绪状态的进程占用处理机。线程调度：类似进程调度 2 进程调度的时机 9江南大学计算机考研辅导操作系统(1)正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费处理机资源。(2)执行中进程自己调用阻塞原语将白己阻塞起来进入睡眠等状态。(3)执行中进程调用了 P 原语操作，从而因资源不足而被阻塞；或调用了 v 原语操作激活了等待资源的进程队列。(4)执行中进程提出 I/O 请求后被阻塞。(5)在分时系统中时间片已经用完。(6)在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。以上都是在可剥夺方式下的引起进程调度的原因。在 CPU 执行方式是可剥夺时还有(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。3 进程的上下文切换过程：用户态执行进程 A 代码进入 OS 核心（通过时钟中断或系统调用）保存进程 A 的上下文，恢复进程 B 的上下文（CPU 寄存器和一些表格的当前指针）用户态执行进程 B 代码 注：上下文切换之后，指令和数据快速缓存 cache 通常需要更新，执行速度降低 4 调度的基本准则 1）面向用户的准则：为了满足用户的需求所应遵循的一些准则（1）周转时间短（从提交到完成的时间间隔）Ti=Tei-Tsi 作业平均周转时间为（有 n 个作业，n=1)n T=1/n Ti i=1 一个作业的周转时间说明了该作业在系统内停留的时间 包含两部分：一是等待时间；二为执行时间 Ti(停留时间)=Twi +Tri 带权周转时间 Wi：Wi=Ti/Tri 平均带权周转时间为：n W=1/n Wi i=1（2）响应时间快 分时系统，用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。（3）截止时间的保证 实时系统（4）优先权准则 2）面向系统的准则（1）系统的吞吐量高（2）处理机利用率好（3）各类资源的平衡利用 5 调度方式 10江南大学计算机考研辅导操作系统 是指当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要进行处理，此时如何分配处理机。通常有剥夺调度和非剥夺调度。6 调度算法（1）先来先服务（FCFS）调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。（2）最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业(3)最高响应比作业优先算法（HRN）最高响应比作业优先算法是对 FCFS 方式和 SJF 方式的一种综合平衡响应比 R 定义为系统对作业的响应时间与作业要求运行时间的比值 R响应时间/要求运行时间(作业等待时间需运行时间)/需运行时间 1已等待时间/需运行时间 1W/T(4)轮转法（Round Robin）采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先服务原则调度，但一旦进程占用处理机则仅使用一个时间片。在使用先一个时间片后，进程还没又完成其运行，它必须释放出处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队等待在次运行。（5）优先级调度算法 一种常用的进程调度算法是把处理机分配给具有最高优先数的进程（用于实时系统）在这种算法中，首先考虑的问题是如何确定进程的优先数。一种是静态优先数，另一种是动态优先数。（6）多级反馈队列 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列 1 的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍 新进程进入内存后，先投入队列 1 的末尾，按 FCFS 算法调度；若按队列 1 一个时间片未能执行完，则降低投入到队列 2 的末尾，同样按 FCFS 算法调度；如此下去，降低到最后的队列，则按时间片轮转算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。11江南大学计算机考研辅导操作系统 习题 习题 1、单道批处理系统，采用短作业优先调度算法。当第一个作业进入后开始调度，现有 3 个作业，进入和计算时间如图所示，求：（1）完成下表；（2）计算平均周转时间。序号 进入时间需计算时间 开始执行时间完成时间周转时间 1 9：00 60 分钟 2 9：10 45 分钟 3 9：15 25 分钟 答：平均周转时间 83 分钟 20 秒。（3 分）序号 进入时间 需计算时间 开始执行时间 完成时间 周转时间 1 9：00 60 分钟 9：00 10：00 60 分钟 2 9：10 45 分钟 10：25 11：10 120 分钟 3 9：15 25 分钟 10：00 10：25 70 分钟 2、某多道程序设计系统配有一台处理器和两台输入输出设备IO1和IO2。现有优先数从高到低 3 个进程P1、P2 和P3 同时存在，他们使用资源的先后顺序和占用时间分别是：进程P1：IO2(30ms),CPU(10ms),IO1(30ms),CPU(10ms),IO2(10ms)进程P2:IO1(20ms),CPU(20ms),IO2(40ms)进程P3：CPU（30ms）,IO1(20ms)忽略调度等所需时间，回答下列问题：（1）进程调度采用非抢占式的优先数算法时 3 个进程从开始到完成所用的时间分别是多少？CPU的利用率为多少？（2）进程调度采用可抢占的优先数算法时，3 个进程从开始到全部完成总共用了多少时间？CPU的利用率为多少？答：（1）三个进程从开始到完成所用的时间分别为：进程 P1 110ms；进程 P2 100ms；进程 P3 50ms。处理器的利用率为（30+20+10+10）/110=63.6%；（2）3 个进程从开始到全部完成总共用了 100ms 时间，此时 CPU 的利用率为（20+10+10+10+10+10）/100=70%。12江南大学计算机考研辅导操作系统 3、某分时系统中的进程可能出现如图所示状态变化，回答下列问题：（1）根据图示，该系统采用的是什么进程调度策略？（2）写出图示中每一个状态变化的原因。运行 答：（1）分析图可知，图中 2 变化是时间片到的时候才会发生，又考虑到是分时系统，所以进程调度采用的是时间片轮转算法。（3 分）（2）变化原因如下表所示：变化 原因 1 进程被选中运行 2 运行满一个时间片（时间片到）（1 分）3 启动打印机工作后等待 （1 分）4 等待磁盘工作结束 （1 分）5 打印机工作结束 （1 分）6 磁盘传输信息结束 （1 分）4、5 个进程 P1、P2、P3、P4、P5 同时依次进入就绪队列，它们的优先数和需要的处理器时间如图所示：忽略进程调度所花费时间，回答下列问题：（1）写出分别采用先来先服务和非抢占式的优先数调度算法选中进程执行的顺序 进程 所需处理器时间 优先数 P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2 6 5 2 3 1 就绪进程队列 4 等待打印机输出结果 等磁盘读文件 13江南大学计算机考研辅导操作系统（2）分别计算上述两种算法使各进程在就绪队列中的等待时间以及两种算法下的平均等待时间。答：（1）先来先服务次序：P1、P2、P3、P4、P5；（2 分）非抢占式优先数:P1、P4、P3、P5、P2；（2 分）（2）各进程在就绪队列中的等待时间如下表：先来先服务算法的平均等待时间：9.6；（2 分）非抢占式优先数算法的平均等待时间：10.4。（2 分）进程 处理器时间 优先数 等待时间（先来先服务）等待时间（非抢占式优先数）P1 10 3 0 0 P2 1 1 10 18 P3 2 3 11 11 P4 1 4 13 10 P5 5 2 14 13 5、一个具有两道作业的批处理系统中，作业调度采用先来先服务的调度算法，作业一旦被调度运行就不再退出，作业对应的进程调度采用内存中的就绪进程平分 CPU 时间，不计作业对换及其他系统开销。如下表的作业序列。计算平均周转时间和平均带权周转时间 作业号 进入时刻 估计运行时间 JOB1 8：00 25 分钟 JOB2 8：20 30 分钟 JOB3 8：25 25 分钟 JOB4 8：30 15 分钟 答：提交时刻 运行时间 结束时刻周转时间 带权周转时间 1 10 15 14 1.4 2 2 4 2 1 3 2 6 3 1.5 4 1 21 17 17 5 5 20 15 3 (1)周转时间1423171551；平均周转时间=51/5=10.2 （4 分）14江南大学计算机考研辅导操作系统 (2)带权周转时间1.411.517323.9；平均带权周转时间=23.9/5=4.78（4 分）6、某系统采用不能移动正在主存中作业的可变分区方式管理主存，现有供用户使用的主存空间 100K，系统配有 4 台磁带机（静态分配），采用多道程序设计技术，忽略设备工作时间和系统进行调度所花时间，若对计算时间短的作业进程赋予高优先数，作业调度采用“可抢占的优先数”调度算法，则平均周转时间为多少。作业如下：序号 入井时间 要求计算时间 需要主存量申请磁带机数 1 10：00 25 分钟 15 K 2 台 2 10：20 30 分钟 60 K 1 台 3 10：30 10 分钟 50 K 3 台 4 10：35 20 分钟 10 K 2 台 5 10：40 15 分钟 30 K 2 台 答：平均周转时间为 43 分钟（4 分）。列表如下：（4 分）序号 选中次序 选中时间 开始执行时间 完成时间 周转时间1 1 10：00 10：00 10：25 25 分钟 2 2 10：20 10：25 11：15(10:35 暂停 20 分)55 分钟 3 4 11：15 11：15 11：25 55 分钟 4 3 10：35 10：35（抢占）10：55 20 分钟 5 5 11：25 11：25 11：40 60 分钟 请分别写出采用“先来先服务调度算法”和“计算时间最短优先算法”选中作业执行顺序以及它们的平均周转时间。答：两种调度算法相同，平均周转时间为 44 分钟（4分）。列表如下：（4分）作业序号 选中次序 选中时间 开始执行时间 完成时间 周转时间 1 1 10：00 10：00 10：25 25 分钟 2 2 10：20 10：25 10：55 35 分钟 3 5 10：30 11：30 11：40 75 分钟 15江南大学计算机考研辅导操作系统 4 3 10：35 10：55 11：15 40 分钟 5 4 10：55 11：15 11：30 50 分钟 7、某单道系统中有 3 个作业正在输入井中等待处理，每个作业估计的计算时间均为 2 小时，那么这 3 个作业的平均周转时间至少为()小时。A2 B4 C6 D8 8、某分时系统采用时间片轮转调度算法分配处理器，对每个用户的请求需花费 200 毫秒可给出应答。那么，要保证响应时间不超过 4 秒，该系统最多可同时接收（）个终端用户。A5 B20 C50 D200 9、（）算法综合考虑了作业的等待时间和计算时间。A先来先服务 B计算时间短的优先 C均衡调度 D响应比最高者优先 10、为了对紧急进程或重要进程进行调度，调度算法应采用（）。A.先进先出调度算法 B.优先数法 B.优先数法 C.最短作业优先调度 D.定时轮转法 11、进程调度的关键问题是选择合理的（），并恰当地进行代码转换。A.时间片间隔 B.调度算法调度算法 C.CPU 速度 D.内存空间 12、采用时间片轮转法进行进程调度是为了（）。A.多个终端都能得到系统的及时响应 多个终端都能得到系统的及时响应 B.先来先服务 C.优先级较高的进程得到及时响应 D.需要 CPU 最短的进程先做 （三）进程同步 1.进程同步的基本概念 2.实现临界区互斥的基本方法 软件实现方法；硬件实现方法。3.信号量 4.管程 5.经典同步问题 生产者-消费者问题；读者-写者问题；哲学家进餐问题。1、进程同步的基本概念 进程同步：它主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。16江南大学计算机考研辅导操作系统 进程互斥：它主要源于资源共享，是进程之间的间接制约关系。在多道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个进程使用临界资源。2、临界区 每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。临界资源:一次仅允许一个进程使用的资源。软件方法教材中提到四种算法。（西电的教程）硬件法采用硬件指令的方式：（1）Test-and-Set（测试并设置指令）（2）Swap（交换指令）3、信号量用于表示资源数目或请求使用某一资源的进程个数的整型量.S 是与临界区内所使用的公用资源有关的信号量。S0 可供并发进程使用的资源数 S buffer;V(mutex);V(full);Consumer：P(full);P(mutex);one unit-buffer;V(mutex);V(empty);5、读者写者问题(the readers-writers problem)一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。为了解决读者和写者问题，需设置两个信号量：为了解决读者和写者问题，需设置两个信号量：（1）读互斥信号量 rmutex,用于使读者互斥地访问共享变量 readcount,这里readcount 是记录有多少读者正在读;（1）读互斥信号量 rmut