操作系统期末复习文档

1、n什么是操作系统？并分别从功能、软件、什么是操作系统？并分别从功能、软件、管理者及用户观点叙述之管理者及用户观点叙述之 q操作系统是控制和管理计算机软、硬件资源，合理组织计算操作系统是控制和管理计算机软、硬件资源，合理组织计算机工作流程，以及方便用户使用的系统软件。机工作流程，以及方便用户使用的系统软件。q从功能角度看，操作系统是计算机的资源管理系统，由它负从功能角度看，操作系统是计算机的资源管理系统，由它负责对计算机系统的全部软、硬件资源进行分配、控制、调度责对计算机系统的全部软、硬件资源进行分配、控制、调度和回收；和回收；q 从软件的观点看，操作系统是一个大型系统软件，由多个功从软件的观点

2、看，操作系统是一个大型系统软件，由多个功能模块及数据集合组成；能模块及数据集合组成；q从管理者角度看，操作系统是计算机工作流程的组织者。它从管理者角度看，操作系统是计算机工作流程的组织者。它自动、高效、合理的对系统进行管理；自动、高效、合理的对系统进行管理； q从用户观点看，操作系统是一个服务质量高、使用方便的虚从用户观点看，操作系统是一个服务质量高、使用方便的虚拟机。它是用户使用计算机的界面和桥梁。拟机。它是用户使用计算机的界面和桥梁。 第1章 操作系统引论n操作系统的地位操作系统的地位 q操作系统是计算机系统中硬、软件资源的总指挥部。操作系统是计算机系统中硬、软件资源的总指挥部。q操作系统

3、的性能高低决定了整体计算机的潜在硬件操作系统的性能高低决定了整体计算机的潜在硬件性能能否发挥出来。性能能否发挥出来。q操作系统本身的安全可靠程度决定了整个计算机系操作系统本身的安全可靠程度决定了整个计算机系统的安全性和可靠性统的安全性和可靠性q操作系统是软件技术含量最大、附加值最高的部分，操作系统是软件技术含量最大、附加值最高的部分，是软件技术的核心，是软件的基础运行平台。是软件技术的核心，是软件的基础运行平台。 n为什么说操作系统实现了对计算机资源的抽象？为什么说操作系统实现了对计算机资源的抽象？qOS首先在裸机上覆盖一层首先在裸机上覆盖一层I/O设备管理软件，实现设备管理软件，实现了对计算

4、机硬件操作的第一层次抽象；了对计算机硬件操作的第一层次抽象；q在第一层软件上再覆盖文件管理软件，实现了对硬在第一层软件上再覆盖文件管理软件，实现了对硬件资源操作的第二层次抽象。件资源操作的第二层次抽象。qOS 通过在计算机硬件上安装多层系统软件，增强通过在计算机硬件上安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节，由它们共了系统功能，隐藏了对硬件操作的细节，由它们共同实现了对计算机资源的抽象。同实现了对计算机资源的抽象。设计现代设计现代OS 的主要目标是什么的主要目标是什么?.q答：方便性。配置操作系统后可使计算机系统更容易使用。答：方便性。配置操作系统后可使计算机系统更容易使用。q

5、有效性。配置操作系统后可提高系统资源的利用率，提高有效性。配置操作系统后可提高系统资源的利用率，提高系统的吞吐量。系统的吞吐量。q可扩充性。操作系统应采用模块化结构，以便于增加新的可扩充性。操作系统应采用模块化结构，以便于增加新的功能和修改老的功能模块。功能和修改老的功能模块。q开放性。为使出自不同厂家的计算机及其设备能通过网络开放性。为使出自不同厂家的计算机及其设备能通过网络加以集成化并正确、有效地协同工作，实现应用程序的可加以集成化并正确、有效地协同工作，实现应用程序的可移植性和互操作性，要求操作系统必须提供统一的开放环移植性和互操作性，要求操作系统必须提供统一的开放环境，进而要求境，进而

6、要求OS具有开放性。开放性是指系统能遵循世界具有开放性。开放性是指系统能遵循世界标准规范，特别是遵循开放系统互连（标准规范，特别是遵循开放系统互连（OSI）国际标准。）国际标准。n试说明操作系统与硬件、其他系统软件以及用试说明操作系统与硬件、其他系统软件以及用户之间的关系户之间的关系 q操作系统是覆盖在硬件上的第一层软件，它管理计算机的硬件和软件资源，并向用户提供良好的界面。操作系统与硬件紧密相关，它直接管理着硬件资源，为用户完成所有与硬件相关的操作，从而极大地方便了用户对硬件资源的使用并提高了硬件资源的利用率。操作系统是一种特殊的系统软件，其他系统软件运行在操作系统的基础之上，可获得操作系统

7、提供的大量服务，也就是说操作系统是其他系统软件与硬件之间的接口。而一般用户使用计算机除了需要操作系统支持外，还需要用到大量的其他系统软件和应用软件，以使其工作更方便和高效。可见，硬件、操作系统、其他系统软件、应用程序和用户之间存在着右图所示的层次关系。 操作系统具有哪几大特征？它们之间有何关系？操作系统具有哪几大特征？它们之间有何关系？答：操作系统的特征有并发、资源共享、虚拟和异步性。它们的关系答：操作系统的特征有并发、资源共享、虚拟和异步性。它们的关系如下：如下：(1)并发和共享是操作系统最基本的特征。为了提高计算机资源的利并发和共享是操作系统最基本的特征。为了提高计算机资源的利用率，操作系

8、统必然采用多道程序设计技术，使多个程序共享系用率，操作系统必然采用多道程序设计技术，使多个程序共享系统资源，并发地执行。统资源，并发地执行。(2)并发和共享互为存在的条件。一方面，资源的共享是以程序（进并发和共享互为存在的条件。一方面，资源的共享是以程序（进程）的并发执行为条件，若系统不允许程序并发执行，自然不存程）的并发执行为条件，若系统不允许程序并发执行，自然不存在资源共享问题；另一方面，若系统不能对资源共享实施有效的在资源共享问题；另一方面，若系统不能对资源共享实施有效的管理，协调好诸进程对共享资源的访问，也必将影响到程序的并管理，协调好诸进程对共享资源的访问，也必将影响到程序的并发执行

9、，甚至根本无法并发执行。发执行，甚至根本无法并发执行。(3)虚拟技术以并发和资源共享为前提。为了使并发进程能更方便、虚拟技术以并发和资源共享为前提。为了使并发进程能更方便、更有效地共享资源，操作系统常采用多种虚拟技术来逻辑上增加更有效地共享资源，操作系统常采用多种虚拟技术来逻辑上增加CPU和设备的数量以及存储器的容量，从而解决众多并发进程对和设备的数量以及存储器的容量，从而解决众多并发进程对有限的系统资源的争用问题。有限的系统资源的争用问题。(4)异步性是并发和共享的必然结果。操作系统允许多个并发进程共异步性是并发和共享的必然结果。操作系统允许多个并发进程共享资源、相互合作，使得每个进程的运行

10、过程受到其他进程的制享资源、相互合作，使得每个进程的运行过程受到其他进程的制约，不再约，不再“一气呵成一气呵成”，这必然导致异步特性的产生。，这必然导致异步特性的产生。第2章 进程进程引入的原因PCB特征进程同步进程控制概念状态就绪执行阻塞结构特征动态性并发性独立性进程通信临界资源和临界区同步与互斥四个准则同步机制管程信号量程序线程状态概念线程控制引入的原因线程同步属性类别用户级线程内核支持线程类别应用整型记录型特例区别区别组成部分n1.程序顺序执行的特征程序顺序执行的特征n2.前趋图前趋图：描述程序段或进程之间执行的先后顺：描述程序段或进程之间执行的先后顺序序n3.程序并发执行时的特征程序并

11、发执行时的特征q 间断性间断性 失去封闭性失去封闭性 不可再现性不可再现性n4.进程的概念进程的概念q 进程是一个可并发执行的具有独立功能的程进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位（作系统进行资源分配和保护的基本单位（1978年全国操作系统学术会议）年全国操作系统学术会议）n5.进程的特征进程的特征q结构特征：每个进程实体中除了相应的程序段、数结构特征：每个进程实体中除了相应的程序段、数据段外，还必须包含一个数据结构据段外，还必须包含一个数据结构PCB，即进程控，即进程控制块制块q

12、动态性动态性q并发性并发性q独立性独立性q异步性异步性n6.在操作系统中为什么要引入进程概念在操作系统中为什么要引入进程概念?为了为了实现并发进程间的合作和协调工作，以及保证实现并发进程间的合作和协调工作，以及保证系统的安全性，操作系统在进程管理方面应做系统的安全性，操作系统在进程管理方面应做哪些工作？哪些工作？ q在多道程序环境中，程序的执行是并发的，这样就在多道程序环境中，程序的执行是并发的，这样就要失去封闭性，并且间断且不可再现要失去封闭性，并且间断且不可再现 。并发执行。并发执行的三个特点决定通常的程序是不能并发执行的，于的三个特点决定通常的程序是不能并发执行的，于是引进了进程的概念。

13、是引进了进程的概念。q操作系统应该在进程管理方面做以下工作：操作系统应该在进程管理方面做以下工作：n进程控制。进程调度。进程同步。进程进程控制。进程调度。进程同步。进程通信。防止死锁。通信。防止死锁。n7.进程与程序的区别进程与程序的区别l进程更能真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能l进程是由程序和数据两部分组成的进程是由程序和数据两部分组成的l程序是静态的，进程是动态的程序是静态的，进程是动态的l进程有生命周期，有诞生有消亡，短暂的；进程有生命周期，有诞生有消亡，短暂的； 而程序是相对长久的而程序是相对长久的l一个程序可对应多个进程，反之亦然一个程序可对应多个进程，反

14、之亦然l进程具有创建其他进程的功能，而程序没有进程具有创建其他进程的功能，而程序没有n8.什么是进程控制块？试从进程管理、进程通信、中什么是进程控制块？试从进程管理、进程通信、中断处理、文件管理、存储管理、设备管理的角度设计断处理、文件管理、存储管理、设备管理的角度设计进程控制块应包含的项目。进程控制块应包含的项目。q进程控制块（进程控制块（PCB）是为了控制进程在多道程序环境下能）是为了控制进程在多道程序环境下能够独立并发地运行而设计的数据结构，它包含了控制和描述够独立并发地运行而设计的数据结构，它包含了控制和描述该进程所需要的所有信息。该进程所需要的所有信息。q从进程管理的角度：从进程管理

15、的角度：PCB应该包含进程标识符、应该包含进程标识符、CPU状态状态信息、进程状态、进程调度信息。信息、进程状态、进程调度信息。q从进程通信的角度：从进程通信的角度：PCB应该包含指向消息队列的指针，用应该包含指向消息队列的指针，用于互斥访问消息队列的信号量。于互斥访问消息队列的信号量。q从中断处理的角度：从中断处理的角度：PCB应该包含中断前的应该包含中断前的CPU的状态信息。的状态信息。q从文件管理的角度：从文件管理的角度：PCB应该包含用户文件描述符表。应该包含用户文件描述符表。q从存储管理的角度：从存储管理的角度：PCB应该包含程序段、数据段和堆栈段应该包含程序段、数据段和堆栈段的地址

16、和长度。的地址和长度。q从设备管理的角度：从设备管理的角度：PCB应该包含该进程已分配到得设备和应该包含该进程已分配到得设备和运行还需要分配的设备的列表。运行还需要分配的设备的列表。n9. 为什么说为什么说PCB是进程存在的唯一标志？是进程存在的唯一标志？q在创建进程时，系统为他配置一个在创建进程时，系统为他配置一个PCB；在进；在进行进程调度时，系统根据行进程调度时，系统根据PCB中的状态和优先中的状态和优先级等信息来选择新进程，然后将老进程的现场级等信息来选择新进程，然后将老进程的现场信息保存到他的信息保存到他的PCB中，再根据新进程中，再根据新进程PCB中中所保存的处理机状态信息来恢复现

17、场；执行中所保存的处理机状态信息来恢复现场；执行中的进程，如果需要访问文件或者需要与合作进的进程，如果需要访问文件或者需要与合作进程实现同步或通信，也要访问程实现同步或通信，也要访问PCB；当进程因；当进程因某种原因而暂停执行时，也必须将断点的现场某种原因而暂停执行时，也必须将断点的现场信息保存到他的信息保存到他的PCB中；当进程结束时，系统中；当进程结束时，系统将回收他的将回收他的PCB。可见，再进程的整个生命周。可见，再进程的整个生命周期中，系统总是通过其期中，系统总是通过其PCB对进程进行控制和对进程进行控制和管理。管理。n10.某分时系统的进程出现如下图所示的状态变化。某分时系统的进程

18、出现如下图所示的状态变化。等待打等待打印机输印机输出结果出结果运行运行等磁盘读文件等磁盘读文件就绪进程队列就绪进程队列试问：（试问：（1）你认为该系统采用的是何种进程调度算法？）你认为该系统采用的是何种进程调度算法？（2）把图中所示的六个状态变化的原因写出来。）把图中所示的六个状态变化的原因写出来。n【分析】从图中可以看出在、和“就绪进程队列”之间存在一个环路，有的进程在执行过程中被剥夺处理机，排入就绪队列的尾部，等待下一次调度，同时进程调度程序又去调度当前就绪队列中的第一个进程，这样的进程调度算法为时间片轮转法。n解： n（1）该分时系统采用的进程调度算法是时间片轮转法。n（2）进程被选中，

19、变成运行态；时间片到，运行的进程排入就绪队列尾部；运行的进程启动打印机，等待打印；打印工作结束，等待的进程排入就绪队列尾部；等待磁盘读文件工作；磁盘传输信息结束，等待的进程排入就绪队列尾部。n11.进程控制进程控制q所谓进程控制，是指系统使用一些具有特定功能的所谓进程控制，是指系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间转程序段来创建、撤销进程以及完成进程各状态间转换的一系列有效管理。操作系统是通过这些被称为换的一系列有效管理。操作系统是通过这些被称为原语的程序段对进程进行控制的原语的程序段对进程进行控制的n12.原语原语q原语是机器指令的延伸，由若干条机器指令构成，原

20、语是机器指令的延伸，由若干条机器指令构成，用于完成特定功能的一段程序。为了保证需哦的正用于完成特定功能的一段程序。为了保证需哦的正确性，原语在执行的过程中是不可分割的，也即其确性，原语在执行的过程中是不可分割的，也即其执行过程是不允许被中断的执行过程是不允许被中断的n13.进程同步进程同步q进程同步是指对多个相关进程在执行次序上进行协调，进程同步是指对多个相关进程在执行次序上进行协调，目的是使系统中诸进程之间能有效地共享资源和相互合目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。用来实现同步的作，从而使程序的执行具有可再现性。用来实现同步的机制被称为同步机制。

21、机制被称为同步机制。n14.进程的同步与互斥进程的同步与互斥q进程的互斥是指并发进程在竞争共享资源时的相互制约进程的互斥是指并发进程在竞争共享资源时的相互制约关系。关系。q进程的同步是指一个进程是否能使用共享资源依赖与其进程的同步是指一个进程是否能使用共享资源依赖与其他进程的执行情况，一个进程在没有受到其他进程的消他进程的执行情况，一个进程在没有受到其他进程的消息时必须等等待，直至另一进程送来消息后才可继续执息时必须等等待，直至另一进程送来消息后才可继续执行下去。行下去。同步与互斥的区别n同步q进程进程q时间次序上受到某种限制q相互清楚对方的存在及其作用，交换信息q往往指有几个进程共同完成一个

22、任务q举例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间 n互斥q进程资源进程q竞争到某一物理资源时不允许进程工作q不一定清楚其它进程情况q往往指多个任务多个进程间通讯制约q举例：交通十字路口，单轨火车的拨道岔 n15.临界资源和临界区临界资源和临界区q临界资源特点：一次仅允许一个进程使用。临界资源特点：一次仅允许一个进程使用。q临界区：每个进程访问临界资源的那一段必须互斥执行的程临界区：每个进程访问临界资源的那一段必须互斥执行的程序。一个共享变量可以有多个临界区。把使用统一变量的一序。一个共享变量可以有多个临界区。把使用统一变量的一组临界区称为组临界区称为“相关临界区相关临

23、界区”。并发进程不允许同时或交叉。并发进程不允许同时或交叉地在各个相关临界区中执行。地在各个相关临界区中执行。n16.同步机制应遵循的规则同步机制应遵循的规则n17.信号量机制及其应用信号量机制及其应用q信号量的含义：信号量是一个用来实现同步的整型信号量的含义：信号量是一个用来实现同步的整型或记录型变量，除了初始化外，对它只能执行或记录型变量，除了初始化外，对它只能执行wait和和signal两种操作。两种操作。q信号量的物理意义：一个信号量信号量的物理意义：一个信号量S通常对应于一类通常对应于一类临界资源。临界资源。S.wait申请资源，申请资源，S.signal释放资源。释放资源。S.va

24、lue表示当前可用资源数表示当前可用资源数q用信号量实现互斥用信号量实现互斥q用信号量实现前趋关系用信号量实现前趋关系n18.进程通信的类型进程通信的类型q共享存储器系统共享存储器系统q消息传递系统消息传递系统q管道通信管道通信n19.消息缓冲队列通信机制应具有那几方面的功能消息缓冲队列通信机制应具有那几方面的功能q构成消息：发送进程在工作区设置发送区，填信息。构成消息：发送进程在工作区设置发送区，填信息。q发送消息：将消息从发送区复制到消息缓冲区，并把它发送消息：将消息从发送区复制到消息缓冲区，并把它插入到目标进程的消息队列中。插入到目标进程的消息队列中。q接受消息：从消息队列中去消息并拷贝

25、到接收区接受消息：从消息队列中去消息并拷贝到接收区q互斥与同步：互斥与同步：n20.线程的属性线程的属性q轻型实体。线程中的实体基本上不拥有系统资源，轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证独立运行的资源。只是有一点必不可少的、能保证独立运行的资源。q独立调度和分派的基本单位。独立调度和分派的基本单位。q可并发执行。可并发执行。q共享进程资源。共享进程资源。n22.进程与线程的比较进程与线程的比较q调度型：在传统的操作系统中，拥有资源的基本单位和调度型：在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的独立调度、分派的基本单

26、位都是进程。而在引入线程的OS中，则把线程作为调度和分派的基本单位，把进程中，则把线程作为调度和分派的基本单位，把进程作为资源拥有的基本单位。作为资源拥有的基本单位。q并发性。在引入线程的并发性。在引入线程的OS中，不仅进程间可以并发执中，不仅进程间可以并发执行，而且在一个进程的多个线程间也可以并发执行行，而且在一个进程的多个线程间也可以并发执行q拥有资源。在这两种拥有资源。在这两种OS中，拥有资源的基本单位都是中，拥有资源的基本单位都是进程。线程除了一点在运行时必不可少的资源（如线程进程。线程除了一点在运行时必不可少的资源（如线程控制块、程序计数器、一组寄存器值和堆栈）外，本身控制块、程序计

27、数器、一组寄存器值和堆栈）外，本身基本不拥有系统资源，但可访问其隶属进程的资源。基本不拥有系统资源，但可访问其隶属进程的资源。q开销。由于创建或撤销进程时，系统要分配或回收资源；开销。由于创建或撤销进程时，系统要分配或回收资源；进程切换时要保存和设置的现场信息也明显多于线程，进程切换时要保存和设置的现场信息也明显多于线程，因此，因此，OS在创建、撤销和切换进程时所付出的开销明在创建、撤销和切换进程时所付出的开销明显地大于线程。另外，由于隶属于同一个进程的多个线显地大于线程。另外，由于隶属于同一个进程的多个线程共享同一地址空间和该进程的所有已打开文件，从而程共享同一地址空间和该进程的所有已打开文

28、件，从而使它们之间的同步和通信的实现也比进程更方便。使它们之间的同步和通信的实现也比进程更方便。n1.一条小河上有一座独木桥一条小河上有一座独木桥,规定每次只允许规定每次只允许一个人过桥一个人过桥,现在河东河西都有人要过桥现在河东河西都有人要过桥,如如果把每个过桥者看作一个进程果把每个过桥者看作一个进程,为保证安全为保证安全,请用请用PV操作实现正确管理操作实现正确管理.n2.一条小河上有一座独木桥一条小河上有一座独木桥,同一方向的可连同一方向的可连续过桥续过桥;某方向有人过桥时另一方向的人等待某方向有人过桥时另一方向的人等待,现在河东河西都有人要过桥现在河东河西都有人要过桥,如果把每个过桥如

29、果把每个过桥者看作一个进程者看作一个进程,为保证安全为保证安全,请用请用PV操作实操作实现正确管理现正确管理.n3.在一间酒吧里有三个音乐爱好者队列，第一队的在一间酒吧里有三个音乐爱好者队列，第一队的音乐爱好者只有随身听，第二队只有音乐磁带，第音乐爱好者只有随身听，第二队只有音乐磁带，第三队只有电池。而要听音乐就必须随身听、音乐磁三队只有电池。而要听音乐就必须随身听、音乐磁带和电池这三种物品俱全。酒吧老板一次出售这三带和电池这三种物品俱全。酒吧老板一次出售这三种物品中的任意两种。当一名音乐爱好者得到这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出种物

30、品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种。于是第二名音乐爱好售这三种物品中的任意两种。于是第二名音乐爱好者得到这三种物品并开始乐曲。全部买卖就这样进者得到这三种物品并开始乐曲。全部买卖就这样进行下去，试用行下去，试用p、v操作正确解决这一买卖。操作正确解决这一买卖。 n4.某私庙，有小和尚、老和尚若干。一水桶，有一某私庙，有小和尚、老和尚若干。一水桶，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容桶水，水取自同一井中。水井径窄，每次只能容一个水桶取水。水桶总数为一个水桶取水。水桶

31、总数为3。每次入、取缸水仅。每次入、取缸水仅为一桶，且不可同时进行。试给出有关取水、入水为一桶，且不可同时进行。试给出有关取水、入水的算法描述。的算法描述。 第3章 处理及调度调调度度级级别别作作业业调调度度（高高级级调调度度）进进程程对对换换（中中级级调调度度）进进程程调调度度（低低级级调调度度）调调度度队队列列选选择择调调度度方方式式和和算算法法的的准准则则调调度度算算法法先先来来先先服服务务短短作作业业优优先先多多级级反反馈馈队队列列高高优优先先权权优优先先时时间间片片轮轮转转多多级级队队列列实实时时调调度度处处理理机机调调度度死死锁锁概概念念产产生生原原因因处处理理方方法法必必要要条条

32、件件竞竞争争资资源源进进程程推推进进顺顺序序非非法法互互斥斥条条件件请请求求和和保保持持条条件件不不剥剥夺夺条条件件环环路路等等待待条条件件死死锁锁预预防防死死锁锁避避免免死死锁锁检检测测死死锁锁解解除除限限制制条条件件银银行行家家算算法法可可能能引引起起第3章 处理机调度与死锁1. 三级调度三级调度n高级调度（作业调度或长程调度）：决定将后备队列高级调度（作业调度或长程调度）：决定将后备队列中的哪些作业调入内存中的哪些作业调入内存n低级调度（进程调度或短程调度）：决定就需队列中低级调度（进程调度或短程调度）：决定就需队列中哪个进程先获得处理机哪个进程先获得处理机q非抢占式非抢占式q抢占式抢占

33、式 抢占原则：优先权原则、短作业有先、时间片原则抢占原则：优先权原则、短作业有先、时间片原则n中级调度（中程调度）中级调度（中程调度）q目的：解决内存紧张问题，常用在分时系统及具有虚拟存储器目的：解决内存紧张问题，常用在分时系统及具有虚拟存储器的系统中。的系统中。2.选择调度算法的准则选择调度算法的准则（1）面向用户的准则：）面向用户的准则：（a）周转时间短）周转时间短（b）响应时间快）响应时间快（c）截止时间的保证）截止时间的保证（d）优先权准则）优先权准则（2）面向系统的准则：）面向系统的准则：（a）系统吞吐量高）系统吞吐量高（b）处理机利用率好）处理机利用率好（c）各类资源的平衡利用）各

34、类资源的平衡利用第3章 处理机调度与死锁3.调度算法调度算法（1）先来先服务）先来先服务(FCFS)算法算法（2）短作业（进程）优先）短作业（进程）优先(SJF/SPF)算法算法（3）高优先权优先）高优先权优先(HPF)算法算法（4）高响应比优先调度）高响应比优先调度(HRRN)算法算法（5）时间片轮转）时间片轮转(RR)算法算法(常用于交互式系统常用于交互式系统)（6）多级反馈队列调度）多级反馈队列调度(FB)算法算法第3章 处理机调度与死锁n进程调度算法解决以何种次序对各就绪进程进行处理进程调度算法解决以何种次序对各就绪进程进行处理机的分配以及按何种时间比例让进程占用处理机。时机的分配以及

35、按何种时间比例让进程占用处理机。时间片轮转进程调度算法的基本思想是什么？时间片的间片轮转进程调度算法的基本思想是什么？时间片的大小对系统有什么影响？在选取取时间片时应考虑哪大小对系统有什么影响？在选取取时间片时应考虑哪些因素？些因素？q时间片轮转法时间片轮转法(RR)主要是分时系统中使用的一种调度算法。主要是分时系统中使用的一种调度算法。时间片轮转法的基本思想是时间片轮转法的基本思想是:将将CPU 的处理时间划分成一个的处理时间划分成一个个时间片个时间片,就绪队列中的诸进程轮流运行一个时间片。就绪队列中的诸进程轮流运行一个时间片。q在轮转法中在轮转法中,时间片长度的选择将直接影响系统开销和响应

36、时时间片长度的选择将直接影响系统开销和响应时间。如果时间片长度很小间。如果时间片长度很小,则调度程序剥夺处理机的次数频繁则调度程序剥夺处理机的次数频繁,加重系统开销；反之，如果时间片长度选择过长加重系统开销；反之，如果时间片长度选择过长,则轮转法就则轮转法就退化成先进先出算法。退化成先进先出算法。q影响时间片大小设置的主要因素有影响时间片大小设置的主要因素有:系统响应时间，就绪进系统响应时间，就绪进程数目程数目(终端数目终端数目)和计算机处理能力。和计算机处理能力。 n某进程被唤醒后立即投入运行，我们就说这个系统采用的是剥夺调度方法，对吗？q答：不对。因为，芮当前就绪队列为空，这样，被唤醒进程

37、就是就绪队列中惟一的一个进程，于是调度程序会立即将该进程投入运行。n在单处理机的分时系统中，分配给进程P的时间片用完后，系统进行切换，结果调度到的仍然是进程P。有可能出现上述情形吗？如果可能请说明理由。q答：有可能出现上述情况。例如，若在进程P时间片用完后，被迫回到就绪队列时，就绪队列为空，这样进程P就是就绪队列中惟一的一个进程，于是调度程序选中的进程必然是进程P；又如在按优先级调度的系统中，就绪队列按进程优先级排列，在进程P时间片用完之后回到就绪队列时，若其优先级高于当前就绪队列中的其它进程，则它将排在就绪队列之首，从而再次被调度进程选中并投入运行。n现有两道作业同时执行，一道以计算为主，另

38、一道以输入输出为主，你将怎样赋予作业进程占有处理器的优先级？为什么？q解解 如果计算进程的优先级高于或者等于输入输出进程的优先级，系统效率也不会提高。因为计算进程一旦占用了CPU便忙于计算，使输入输出进程得不到运行机会，同样会使设备空闲，不能提高系统效率。q如果输入输出进程的优先级高于计算进程的优先级，系统效率就能够得到提高。因为输入输出操作是一种速度极慢的操作。若该项操作的优先级高，那么，当它完成一项输入输出操作后，便能立即获得CPU，为下一次输入输出作准备工作，并启动外部设备。当设备被启动起来后，它便主动让出CPU，由系统将CPU交给计算机进程使用。从而获得较好的运行效率。4.产生死锁的原

39、因产生死锁的原因（1）竞争资源）竞争资源（2）进程间推进顺序非法）进程间推进顺序非法5.产生死锁的必要条件产生死锁的必要条件（1）互斥条件）互斥条件（2）请求和保持条件）请求和保持条件（3）不剥夺条件）不剥夺条件（4）环路等待条件）环路等待条件第3章 处理机调度与死锁6.处理死锁的基本方法处理死锁的基本方法（1）预防死锁）预防死锁（2）避免死锁）避免死锁（3）检测死锁）检测死锁（4）解除死锁）解除死锁第3章 处理机调度与死锁第3章 处理机调度与死锁7.银行家算法银行家算法用到四个数据结构，执行流程是：用到四个数据结构，执行流程是：（1）某个进程发出资源请求）某个进程发出资源请求（2）判断资源请

40、求是否合法，即：请求量不大于）判断资源请求是否合法，即：请求量不大于最大需求量、不大于可用资源量最大需求量、不大于可用资源量（3）试探性将资源分配给该进程）试探性将资源分配给该进程（4）系统执行）系统执行安全性判定算法安全性判定算法，检查分配后系统，检查分配后系统是否处于安全状态。如果安全，则确认此次分配，是否处于安全状态。如果安全，则确认此次分配，否则撤销此次分配。否则撤销此次分配。n在解决死锁问题的几个方法中，哪种方法最容易实现?哪种方法使资源的利用率最高?q答：a. 解决死锁可归纳为四种方法：q预防死锁。通过一些限制条件的设置来破坏死锁发生的四个必要条件中的一个或多个，以预防死锁的发生。

41、q避免死锁。在资源动态分配过程中用某些算法加以限制，防止系统进入不安全状态从而避免死锁的发生。q检测死锁。采取一定的机制检测系统是否死锁，以配合死锁的解除。q解除死锁。通过撤销一些进程来回收资源把系统从死锁中解脱出来。qb. 其中，预防死锁是最容易实现的；c. 避免死锁使资源的利用率最高.n有3个进程P1、P2和P3并发工作。进程P1需要资源S3和S1，进程P2需要资源S1和S2，进程P3需要资源S2和S3。那么，若对资源分配不加限制，会发生什么情况？为什么？为保证进程正确地工作，应采用怎样的资源分配策略？为什么？n解：若对进程间的资源分配不加限制，可能会发生死锁，因为这样的分配可能导致进程间

42、的“循环等待”，并且这种状态将永远持续下去。进程P1、P2和P3分别获得资源S3、S1和S2，后再继续申请资源时都要等待。n为保证进程正确地工作，系统应该采取一定的资源分配策略来限制死锁发生的必要条件。q限制请求和保持条件的发生。可以要求进程只有一次性申请到了它所需的所有资源后才能得到运行，否则将放弃它申请到的资源。即采用静态分配。q限制不剥夺条件的发生。可以允许系统中的进程在申请了系统中已经没有了的资源后，可以从其他没有在运行的进程中抢夺该资源。q限制环路等待条件的发生。可以要求进程按照资源的编号来顺序地申请资源。即P1进程先申请S1再申请S3，P2进程先申请S1再申请S2，P3进程先申请S

43、2再申请S3。第4章 存储器管理程程序序处处理理步步骤骤内内存存分分配配算算法法优优点点优优点点请求页式请求段式虚虚拟拟存存储储器器需需要要时时装装入入需需要要时时装装入入单单一一固固定定分分区区动动态态分分区区首首次次适适应应循循环环首首次次适适应应最最差差适适应应最最佳佳适适应应页页面面置置换换算算法法存存在在的的问问题题FIFOPBALRUOptimalNRULFUBelady异异常常抖抖动动装装入入到到哪哪里里？编编译译链链接接装装入入静静态态链链接接动动态态链链接接装装入入时时动动态态运运行行时时动动态态绝绝对对装装入入可可重重定定位位装装入入动动态态运运行行装装入入动动态态可可重重

44、定定位位离离散散分分配配方方式式连连续续分分配配方方式式基基本本分分页页段段页页式式基基本本分分段段一、内存管理概念n1.内存管理的功能存储管理的主要任务时为多道程序的运行提供良好的环境，方便用户使用存储器、提高存储器的利用率以及从逻辑上扩充存储器。为此，存储管理应具有如下功能：q内存的分配和回收q地址变换q扩充内存容量q存储保护一、内存管理概念n2.应用程序的处理过程（1）用户先编辑好应用程序（2）通过相关语言的编译程序将其编译成若干个目标模块（3）再通过链接程序将编译后的目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块（4）最后通过装入程序将它们装入内存进行运行。一、内存管

45、理概念q程序的链接方式：n静态链接：在程序运行之前，先把各个目标模块及它们所需要的库函数链接成一个完整的可执行程序，以后不再拆开。n装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接方式。n运行时动态链接：对一些目标模块的链接直到程序运行时才去对它进行链接，其优点是便于修改和更新，便于实现目标模块的共享。一、内存管理概念q程序的装入方式n绝对装入：在编译时就知道程序将要驻留的内存地址，编译程序产生绝对地址目标代码。不适合多道程序设计。n可重定位装入：根据内存当前的使用情况，将装入模块装入到内存的适当位置，地址变换通常是在装入时一次性完成的，之后都不再改变，也称为静

46、态重定位。特点：在一个作业装入内存时必须分配其要求的全部内存空间，此外，不能在内存中移动或增加内存空间。n动态运行装入：允许程序运行时在内存中移动位置，把装入模块装入到内存后所有的地址都是相对地址，只有到程序需要真正执行时才把相对地址转换成绝对地址，也称为动态重定位。特点：可以将程序分配到不连续的存储区中，课装入部分代码。二、连续分配方式1.固定分区分配划分分区的方法：分区大小相等、分区大小不等内存分配：将分区按大小进行排序，建立一张分区使用表优点：可用于多道程序系统最简单的存储分配，无外部碎片缺点：不能实现多进程共享一个主存区，所以存储空间利用率较低，有内部碎片。二、连续分配方式2.可变分区

47、分配q数据结构：空闲分区表、空闲分区链q分配算法：（1）首次适应n优点：优先利用内存低址部分的内存空间，无内部碎片n缺点：低址部分不断划分，有外部碎片；每次查找从低址部分开始，增加了查找的开销。n要求：空闲分区表或空闲分区链按地址从低到高排列n循环首次适应、最佳（差）适应二、连续分配方式2.可变分区分配q数据结构：空闲分区表、空闲分区链q分配算法：（2）循环首次适应n优点：使内存空闲分区分布均匀，减少查找开销，无内部碎片n缺点：会导致缺乏大的空闲分区，有外部碎片n要求：空闲分区表或空闲分区链按地址从低到高排列二、连续分配方式2.可变分区分配q数据结构：空闲分区表、空闲分区链q分配算法：（3）最

48、佳适应算法n优点：产生的外部碎片很小，无内部碎片n缺点：产生许多难以利用的小空闲区，仍有外部碎片n要求：空闲分区表或空闲分区链按其容量从小到大排列（4）最坏适应算法n优点：使得留下来的空闲区较大，便于下次利用，无内部碎片n缺点：大的空闲区不容易保留，有外部碎片n要求：空闲分区表或空闲分区链按其容量从大到小排列二、连续分配方式2.可变分区分配q回收：合并相邻的空闲区q拼接技术q分区的存储保护：上下界寄存器方法、基址限长寄存器方法q动态分区分配的优缺点n优点：实现了多道程序共享主存、管理方案相对简单，不需要更多的软硬件开销，实现存储保护的手段比较简单n缺点：主存利用不够充分，即存在内部碎片，无法实

49、现多进程共享存储器的信息，无法实现主存的扩充采用可变分区方式管理主存空间时，若主存中按地址顺序依次有五个空闲区，空闲区大小分别为15k，28k，10k，226k，110k。现有五个作业Ja、Jb、Jc、Jd和Je，它们需要的主存依次为10k，15k，102k，26k，80k。如果采用最先适应算法能把这五个作业按JaJe的次序全部装入主存吗？用什么分配算法装入这五个作业可使主存的利用率最高？ 1.离散分配方式分类分页、分段2.基本分页存储管理的实现思想作业分页，内存分块，页大小等于块大小3.分页地址结构页号+页内位移4.分页地址变换（1）求页号和页内位移；（2）查页表得块号；（3）计算物理地址：

50、块号*块大小+页内位移5.基本分页存储管理方式的优缺点q优点：存在页内碎片，但碎片相对较小，内存利用率教高；实现了离散分配，消除了程序浮动；便于存储访问控制，有利于代码共享；无外部碎片。q缺点：需要专门的硬件支持，尤其是快表；内存访问的效率下降；不支持动态链接，不能实现真正的共享；有内部碎片6.分页和分段有何异同三、离散分配方式n为满足264地址空间的作业运行，采用多级分页存储管理方式，假设页面大小为4KB，在页表中的每个页表项需要占8个字节，则为了满足系统的分页管理至少应采用多少级页表？n解：页面大小=4KB=212字节，每个页表项为8字节，所以一个页面中可以存放212/23=29个页表项。

51、设有n层分页，则64位逻辑地址形式为： 第1层页号第2层页号第n层页号页内偏移量其中其中,页面大小为页面大小为212字节，所以页内偏移量占字节，所以页内偏移量占12位位.剩下剩下64-12=52位位,由由于每层指向一个物理块于每层指向一个物理块,其中可放下其中可放下29个页表项个页表项,所以所以52/9=6(向上取整向上取整)。四、虚拟内存管理1.虚拟存储器的定义 虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。2.实现虚拟存储技术的硬件支持q要有相当数量的外存：足以存放多个用户的程序q要有一定容量的内存：因为在处理机上运行的程序必须有一部分信息存放在内

52、存中。q地址变换机构：以动态实现虚地址到实地址的地址变换3.常用的虚拟存储技术q请求分页存储管理q请求分段存储管理q请求段页式存储管理4.虚拟存储器的特征多次性、对换性、虚拟性五、请求分页存储管理1.请求分页的硬件支持页表、缺页中断（指令执行期间发生中断）、地址变换机构2.内存分配策略和分配算法（1）最小物理块数的确定：能保证程序运行所需的最小物理块数（2）物理块的分配策略 固定分配局部置换、可变分配全局置换、可变分配局部置换（3）物理块分配算法 平均分配算法、按比例分配算法、考虑优先权分配算法3.调页策略（1）调入页面的时间：请求调页策略、预调页策略（2）从何处调入：兑换区、文件区（未修改的

53、页面）+兑换区、unix方式是文件区（未运行过的页面）+兑换区（运行过又被换出的页面）4.页面置换算法 最佳置换算法、先进先出（FIFO）置换算法、最近最久未使用（LRU）置换算法、Clock置换算法 页面置换时，一定有页面被写到磁盘交换区吗？（no） 5.缺页率 影响缺页的因素：q页面置换算法：其优略影响缺页中断次数q主存物理块数：其数目越多，缺页率越低q页面大小：页面大，缺页率低，反之，缺页率高q程序特性：编程方法对缺页中断次数有影响目前，大多数计算机系统都支持虚拟页式地址转换机制。试回答下列问题：(1)页式存储管理方案中，用户地址空间怎样划分？内存地址空间怎样划分？内存分配过程是怎样的？

54、(2)页表应设计哪些数据项，每个数据项的作用是什么？(3)页式存储管理方案中，地址映射机制需要哪种寄存器的支持？为了加快地址映射速度，需要采取什么措施？该措施的作用是什么？答：(1)系统将用户程序的逻辑空间按照相等大小划分成若干界面，称为逻辑页面。各个逻辑页面从0开始依次编号，每个逻辑页面内也从0开始编址，称为页内地址。用户程序的逻辑地址由逻辑页号和页内地址两部分组成。页式存储管理将内存空间按照逻辑页面大小划分成等长的若干区域，每个区域为一个内存块。内存的所有内存块从0开始编号。内存分配时，以页面（块）为单位，并按用户程序所需页数多少进行分配。逻辑上相邻的页面在内存中不一定相邻，即分配给用户程

55、序的内存块不一定连续。(2)页表表项有：逻辑页面号；物理页面号（或块号）；驻留位（中断位或特征位）：指示该页在内存还是在外存；外存地址：指示该页在外存的地址；修改位：指示该页在内存驻留期间是否被修改过；(3)系统提供一对硬件寄存器：页表始址寄存器和页表长度寄存器。页表始址寄存器，用于保存正在运行进程的页表在内存的首地址。当进程被调度程序选中投入运行时，系统将其页表首地址从进程控制块中取出送入该寄存器。页表长度寄存器，用于保存正在运行进程的页表的长度。当进程被选中运行时，系统将它从进程控制块中取出送入该寄存器。为了加快地址映射速度，可在地址映射机制中增加一个小容量的联想寄存器（相联存储器），它由

56、高速寄存器组成，成为一张快表，快表用来存放当前访问最频繁的少数活动页的页号。 n什么是抖动? 产生抖动的原因是什么?n答a. 抖动(Thrashing)就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调出一页程序或数据送磁盘的对换区中，如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访问，因而又需将它调入，如此频繁更换页面，以致花费大量的时间，我们称这种现象为抖动;nb. 产生抖动的原因是由于CPU 的利用率和多道程序度的对立统一矛盾关系引起的，为了提高CPU 利用率，可提高多道程序度，但单纯提高多道程序度又会造成缺页率的急剧上升，导

57、致CPU 的利用率下降，而系统的调度程序又会为了提高CPU 利用率而继续提高多道程序度，形成恶性循环，我们称这时的进程是处于抖动状态。一个好的调度算法应减少和避免抖动现象。以存储管理中的段式存储管理为例，请叙述操作系统对内存的具体管理方案（包括功能、数据结构和算法）。首先从内存划分、程序逻辑地址划分、内存分配几方面考虑段式存储管理方案的工作原理：内存划分：内存空间被动态地划分为若干个长度不相同的区域，每个区域称作一个物理段、每个物理段在内存中有一个起始地址，称作段首址。将物理段中的所有单元从0 开始依次编址，称为段内地址。逻辑地址空间划分：用户程序按逻辑上有完整意义的段来划分。称为逻辑段。例如

58、主程序、子程序、数据等都可各成一段，每段对应于一个过程，一个程序模块或一个数据集合。将一个用户程序的所有逻辑段从0 开始编号，称为段号。将一个逻辑段中的所有单元从0开始编址，称为段内地址。用户程序的逻辑地址由段号和段内地址两部分组成：段号，段内地址内存分配：系统以段为单位进行内存分配，为每一个逻辑段分配一个连续的内存区(物理段)。逻辑上连续的段在内存不一定连续存放。然后，从实现方法上考虑：建立段表系统为每个用户程序建立一张段表，用于记录用户程序的逻辑段与内存物理段之间的对应关系，包括逻辑段号，物理段首地址和物理段长度三项内容。用户程序有多少逻辑段，该段表里就登记多少行，且按逻辑段的顺序排列。段

59、表存放在内存系统区里。建立空闲区表系统中设立一张内存空闲区表，记录内存中空闲区域情况，用于为段分配和回收内存。系统在寻找空闲区时可采用以下三种分配算法。首先适应算法根据申请，在空闲区表中选取第一个满足申请长度的空闲区。此算法简单，可以快速做出分配决定。最佳适应算法根据申请，在空闲区表中选择能满足申请长度的最小空闲区。此算法最节约空间，因为它尽量不分割大的空闲区。其缺点是可能会形成很多很小的空闲区域，称作碎片。最坏适应算法根据申请，在空闲区表中选择能满足申请要求的最大的空闲区。该算法的出发点是：在大空头区中装人信息后，分割剩下的空闲区相对也大，还能用于装入新的信息。该算法的优点是可以避免形成碎片

60、；缺点是分割大的空闲区后，再遇到较大的申请时，无法满足的可能性较大。 设某计算机的逻辑地址空间和物理地址空间均为设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若，按字节编址。若某进程最多需要某进程最多需要6页数据存储空间，页的大小为页数据存储空间，页的大小为1KB。操作系统采用固定。操作系统采用固定分配局部置换策略为此进程分配分配局部置换策略为此进程分配4个页框，如下个页框，如下：页号页号页框号页框号装入时刻装入时刻访问位访问位071301142301222001391601当该进程执行到当该进程执行到260时刻时，要访问逻辑地址为时刻时，要访问逻辑地址为17CAH的数据，请