操作系统

《计算机操作系统第四版》西安电子科技大学出版社，读书笔记，每章的思路重点含进程的控制，处理机调度，存储器管理，虚拟存储器等内容。

第一章 操作系统引论

• 1.1 操作系统的目标和作用
  • 1.1.0 什么是操作系统
    • 操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。其主要作用是管理好这些设备，提高他们的利用率和系统的吞吐量，并为用户和应用程序提供一个简单的接口，便于用户使用。
      • 1.什么是操作系统？
  • 1.1.1 操作系统的目标
    • 1.方便性：一个未配置OS的计算机系统是极难使用的。用户如果想在计算机硬件上运行编写的程序，就必须用机器语言书写，但是如果在硬件之上配置了OS，系统便可使用编译命令将用户的高级语言翻译成机器代码，或者直接通过使用OS所提供的各种命令操作计算机系统，极大方便了用户，使得计算机变得易学易用
    • 2.有效性：有效性包含的第一层含义是提高系统资源的利用率，另一层含义是提高系统的吞吐量。OS可以通过合理的组织计算机的工作流程，加速程序的运行，缩短程序的运行周期，从而提高了系统的吞吐量
    • 3.可扩充性：为适应计算机硬件、体系结构和计算机应用发展的要求，OS必须具有很好的可扩充性，近年来OS已广泛采用了微内核结构，能够方便地添加和修改功能和模块，具有良好的可扩充性
    • 4.开放性：所谓开放性，是指系统能遵循世界标准规范，也别是遵循开放系统互连OSI国际标准。凡遵循国际标准所开发的硬件和软件，都能彼此兼容，方便实现互连。
    • 3.OS的主要目标是什么？
  • 1.1.2 操作系统的作用
    • 1.OS作为用户与计算机硬件系统之间的接口：OS处于用户与计算机硬件系统之间。用户可以通过三种方式使用计算机：命令方式、系统调用方式和图标-窗口方式来实现与操作系统的通信
    • 2.OS作为计算机系统资源的管理者：OS的主要功能是对处理机、存储器、I/O设备和文件（数据和程序）这四类（软硬件）资源进行有效的管理。
      • 处理机管理是用于分配和控制处理机
      • 存储器管理主要负责内存的分配和回收
      • I/O设备管理是负责I/O设备的分配（回收）与操纵
      • 文件管理是用于实现对文件的存取、共享和保护
    • 3.OS实现了对计算机资源的抽象：OS首先在裸机上覆盖一层I/O管理设备软件，实现了对计算机硬件操作的第一层次抽象；在第一层软件上再覆盖文件管理软件，实现了对硬件资源操作的第二层次抽象。OS通过在计算机硬件上安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节，由他们共同实现了对计算机资源的抽象。 OS是铺设在计算机硬件上的多层软件的集合，他们不进增强了系统的功能，还隐藏了对硬件操作的具体细节，实现了对计算机硬件操作的多个层次的抽象模型
      • 5.操作系统如何实现对计算机资源的抽象？
      • 虚机器/扩充机器：它向用户提供了一个对硬件（下层）操作的抽象模型。用户可以利用该模型提供的（上层）接口使用计算机，无需了解物理（下层）接口实现的细节，从而使用户更容易地使用计算机硬件（下层）资源
    • 2.OS的作用可表现在哪几个方面？
  • 1.1.3 推动操作系统发展的主要动力
    • 1.不断提高计算机资源的利用率：计算机发展初期，计算机系统特别昂贵，所以必须千方百计提高系统中各个资源的利用率
    • 2.方便用户：资源利用率不高初步解决之后，用户在上机、调试程序时的不方便性便成为了主要矛盾
    • 3.器件的不断更新换代
      • 随着IT技术的飞速发展，尤其是微机芯片的更新换代，使得计算机的性能快速提高，从而推动了OS的功能和性能迅速增强和提高
      • 与此同时，外部设备也在迅速发展 OS所能支持的外部设备也越来越多
    • 4.计算机体系结构的不断发展
      • 当计算机由单处理机系统发展为多处理机系统时，OS也就由单处理机OS发展为多处理机OS
      • 计算机网络出现后，配置在计算机网络上的网络操作系统也就应运而生。它不仅能够有效地管理好网络中的共享资源，而且还向用户提供了许多网络服务
    • 5.不断提出新的应用需求
      • 为了提高产品的质量和数量，需要将计算机应用于工业控制中，此时就需要配置进行时事控制的OS
      • 为了满足娱乐等需求，又在OS中添加了多媒体功能
      • 随着VLSI的发展，计算机芯片的体积越来越小，价格愈发便宜，大型智能设备应运而生，这样嵌入式操作系统的产生和发展也成了一种必然
    • 6.试说明推动多道批处理系统形成和发展的主要动力是什么？
• 1.2 操作系统的发展过程
  • 1.2.0 批处理系统、分时系统和实时系统的目标
    • 批处理系统
      • ①平均周转时间短
      • ②系统吞吐量高
      • ③处理机利用率高
    • 分时系统
      • ①响应时间快
      • ②均衡性
    • 实时系统
      • ①截止时间的保证
      • ②可预测性
    • 4.批处理系统、分时系统、实时系统的目标分别是什么？
  • 1.2.1 未配置操作系统的计算机系统
    • 1.人工操作方式
      • 早期的操作方式是由程序员将实现已穿孔的纸带（卡片），装入纸带（卡片）输入机，再启动它们将纸带（卡片）上的程序和数据输入计算机，然后启动运行。仅当程序运行完毕并取走计算结果后，才允许下一个用户上机
      • 两大缺点
        • 用户独占全机，即一台计算机的全部资源由上机用户所独占
        • CPU等待人工操作。人机速度矛盾导致CPU资源利用率低。当用户进行装带，卸带等人工操作时，CPU及内存等资源是空闲的
    • 2.脱机输入/输出（Off-Line I/O）方式
      • 脱机I/O
        • 脱机I/O 是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机，在外围机的控制下，把纸带或卡片上的数据或程序输入到磁带上。该方式下的输入输出由外围机控制完成，是在脱离主机的情况下进行的。
          • 5.何谓脱机I/O和联机I/O？
        • 两大优点
          • 减少了CPU的空闲时间。装带、卸带，以及将数据从低速I/O设备送到高速磁带上的操作，都是在脱机情况下由外围机完成的，并不占用主机时间，从而有效地减少了CPU的空闲时间
          • 提高了I/O速度。当CPU在运行中需要输入数据时，是直接从高速的磁带将数据输入到内存，这便极大的提高了I/O速度，从而进一步减少了CPU的空闲时间
      • 联机I/O
        • 而联机I/O方式是指程序和数据的输入输出都是在主机的直接控制下进行的。
  • 1.2.2 单道批处理系统
    • 1.单道批处理系统的处理过程
      • 监督程序将磁带上的第一个作业装入内存，并把运行控制权交给该作业
      • 当该作业处理完成时，又把控制权交还给监督程序，再由监督程序把磁带上的第二个作业调入内存
      • 计算机系统就这样自动地一个作业紧接一个作业地进行处理，直至磁带上的所有作业全部完成
    • 3.单道批处理系统的优点
      • 缓解了一定程度的人机速度矛盾，资源利用率有所提升
    • 2.单道批处理系统的缺点
      • 系统中的资源得不到充分的利用（进行I/O操作时CPU处于等待状态）
  • 1.2.3 多道批处理系统 （Multiprogrammed Batch Processing System）
    • 1.多道程序设计的基本概念
      • 多道程序设计技术是指在内存同时放若干道程序，使它们在系统中并发执行，共享系统中的各种资源。当一道程序暂停执行时，CPU立即转去执行另一道程序。
    • 2.多道批处理系统的优缺点
      • (1)资源利用率高。多道程序并发执行，共享资源，以保持CPU处于忙碌状态，可提高内存的利用率和I/O设备的利用率
      • (2)系统吞吐量大。①CPU和其他资源保持忙碌状态 ②仅当作业完成时或运行不下去时才进行切换，系统开销小
      • (3)平均周转时间长。由于作业要排队依次进行处理，因而作业的周转时长较长，通常需要几个小时甚至几天。
      • (4)无交互能力。用户一旦把作业提交给系统后，完成之前用户无法与自己的作业进行交互，修改与调试程序极不方便。
      • 8．多道批处理系统的形成发展的主要动力和优缺点分别是什么？
    • 3.多道批处理系统需要解决的问题
      • (1)处理机争用问题。既要满足各道程序运行的需要，又要能提高处理机的利用率。
      • (2)内存分配和保护问题。系统应能为每道程序分配必要的内存空间，且不会因某道程序出现异常情况而破坏其他程序。
      • (3)I/O设备分配问题。采用适当的策略来分配系统中的I/O设备，以达到既能方便用户对设备的使用，又能提高设备利用率的目的。
      • (4)文件的组织和管理问题。系统应能有效地组织存放在系统中的大量程序和数据，使他们既方便用户使用，又能保证数据的安全性。
      • (5)作业管理问题。系统中存在各种作业（应用程序），系统应能对所有作业进行合理的组织，以满足这些作业用户的不同要求。
      • (6)用户与系统的接口问题。为使用户能方便的使用操作系统，OS还应提供用户与OS的接口
      • 7．多道批处理系统需要解决的问题?
  • 1.2.4 分时系统 （Time Sharing System）
    • 分时系统是指，在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源
    • 1.分时系统的引入
      • 为了满足用户对人—机交互的需求推动了分时系统的形成
        • (1)人—机交互：人—机交互能力使用户能直接控制自己的作业
        • (2)共享主机：多个用户共享主机，CPU 的分时使用缩短了作业的平均周转时间
        • 6.使说明推动分时系统形成和发展的主要动力是什么。
    • 2.分时系统实现中的关键问题
      • (1)及时接收:配置多路卡实现分时多路复用，即主机以很快的速度周期性地扫描各个终端，在每个终端处停留很短的时间用于接收用户发来的指令或数据。
      • (2)及时处理：
        • ①作业直接进入内存。因为作业在磁盘上是不能运行的，所以作业应该直接进入内存。
        • ②采用轮转运行方式。规定每个作业每次只能运行一个时间片（例如30ms）然后暂停，并调度下一个作业运行。如果在不长的时间内能使所有的作业都执行一个时间片的时间，便可以使每一个用户都能及时的与自己的作业进行交互。从而使用户的请求得到及时的响应。
      • 7.实现分时系统的关键问题是什么？应如何解决？
    • 3.分时系统的特征
      • 与多道批处理系统相比
        • (1)多路性。系统允许将多台终端同时连接到一台主机上，并按分时原则为每个用户服务。显著地提高了资源利用率，降低了使用费用。
        • (2)独立性。系统提供了每个用户在各自终端上进行操作，彼此间互不干扰的特点。
        • (3)及时性。用户的请求能在短时间内获得相应，这一时间是根据用户能接受的等待时间确定的（1~3s)
        • (4)交互性。用户可以请求系统提供多方面的服务，如进行文件编辑和数据处理，访问系统中的文件系统和数据库系统，请求提供打印服务等。
    • 4.分时操作系统的优缺点
      • 优点
        • 解决了人机交互问题
        • 多个用户可以共享主机
      • 缺点
        • 不能优先处理紧急任务
  • 1.2.5 实时系统 （Real Time System）
    • 实时系统是指系统能够及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。引入实时OS 是为了满足应用的需求，更好地满足实时控制领域和实时信息处理领域的需要
      • 8.为什么要引入实时操作系统？
    • 1.实时系统的类型
      • 工业(武器)控制系统
        • 火炮的自动控制系统
        • 飞机的自动驾驶系统
        • 导弹的制导系统
      • 信息查询系统
        • 火车飞机订票系统等
      • 多媒体系统
        • 音视频多媒体系统（实时信息处理）
      • 嵌入式系统
        • 智能仪器和设备
    • 2.实时任务的类型
      • (1)周期性实时任务和非周期性实时任务
        • 周期性实时任务是指这样一类任务，外部设备周期性地发出激励信号给计算机，要求它按指定周期循环执行，以便周期性地控制某外部设备
        • 非周期性实时任务并无明显的周期性，但都必须联系着一个截止时间（开始截止时间，完成截止时间），或称最后期限
      • (2)硬实时任务和软实时任务
        • 硬实时任务(Hard Real-time Task, HRT)是指系统必须满足任务对截止时间的要求，否则可能出现难以预测的后果。一般用于工业和武器控制的实时系统
        • 软实时任务(Soft Real-time Task, SRT)也联系着一个截止时间，但并不严格，若偶尔错过任务的截止时间，对系统产生的影响也不会太大。诸如用于信息查询系统和多媒体系统。
        • 9.什么是硬实时任务和软实时任务？试举例说明。
    • 3.实时系统与分时系统特征的比较
      • (1)多路性。都为多用户，实时系统周期性对多路现场信息采集或对多个对象进行控制。而分时系统多路性则与用户情况有关，时多时少。
      • (2)独立性。两者都是互不干扰。分时系统每个终端项分时系统提出服务请求时，彼此独立操作，互不干扰；实时系统中，对信息的采集和对象的控制也是互不干扰。
      • (3)及时性。两者类似，以人所能接受的等待事件来确定。实时系统更具有及时性。
      • (4)交互性。两个都具有，分时系统可以从终端向用户提交复杂的服务；而实时系统的交互仅限定于访问系统中某些特定的服务程序。
      • (5)可靠性。实时系统具有更高的可靠性，实时系统中，往往采用多级容错措施来保障系统的安全及数据的安全。
      • 10.试从交互性、及时性以及可靠性方面将分时系统与实时系统进行比较。
  • 1.2.6 微机操作系统的发展
    • 微机操作系统按运行方式分为
      • 1.单用户单任务操作系统：只允许一个用户上机，且只允许用户程序作为一个任务运行，主要配置在8位和16位微机上
        • CP/M：8位微机操作系统，具有较好的体系结构，可适应性强，可移植性以及易学易用等优点
        • MS-DOS：16位微机操作系统，扩充于CP/M，在功能上有很大的提高，性能优越受到当时用户的广泛欢迎
      • 2.单用户多任务操作系统：只允许一个用户上机，但允许用户把程序分为若干个任务，使它们并发执行，从而有效的改善了系统的性能。目前基本在32位微机上配置
        • Windows
      • 3.多用户多任务操作系统：允许多个用户通过各自的终端，使用同一台机器，共享主机系统的各种资源，而每个用户程序又可进一步分为几个任务，使它们能并发执行，从而可进一步提高资源利用率和系统吞吐量。在大中小型机中所配置的大多是此，在32位微机上也有不少配置。
        • UNIX OS
          • Solaris OS
          • Linux OS
• 1.3 操作系统的基本特性
  • 1.3.1 并发(Concurrence)
    • 10.OS有哪几大特征？
    • 正是系统中的程序能够并发执行这一特征，才使得OS能有效地提高系统中的资源利用率，增加系统吞吐量。
    • 1.并行与并发
      • 并行性：是指两个或多个事件在同一时刻发生
      • 并发性：是指两个或多个事件在同一时间间隔内发生
      • 单处理机系统中，每一时刻仅能有一道程序执行，故微观上这些程序只能是分时交替执行（并发执行），倘若有多个处理机，这些可以并发执行的程序便可被分配到多个处理机上实现并行执行，即利用每个处理机来处理一个可并发执行的程序，这样多个程序便可同时执行
        • 如：在1s内，0~15ms运行A，15~30ms运行B，30~45ms运行C，45~60ms运行D，因此可以说在1s的时间间隔内，有四道程序在同时运行，但微观上，程序A,B,C,D是分时交替执行的
    • 2.引入进程
      • 进程：是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈组成的，是一个能独立运行的活动实体。多个进程之间可以并发执行和交换信息
      • 未引入进程：在属于同一个应用程序的计算程序和I/O程序之间只能是顺序执行，即只有在计算程序执行告一段落后，才允许I/O程序执行
      • 引入进程后：为计算程序和I/O程序分别建立一个进程(Process)后，这两个进程便可并发执行。若对内存中的多个程序都分别建立一个进程，他们就可以并发执行，这样便能极大地提高系统资源的利用率，增加系统吞吐量
  • 1.3.2 共享(Sharing)
    • 在OS环境下的资源共享或称为资源复用，是指系统中的资源可供内存中多个并发执行的进程共同使用。这里宏观上既限定了时间(进程在内存期间),也限制了地点(内存)
      • 12.在多道程序技术的OS环境下的资源共享与一般情况下的资源共享有何不同？
    • 1.互斥共享方式
      • 概念：系统中的某些资源如打印机、磁带机等虽然可以提供给多个进程(线程)使用,但是应该规定在一段时间内，只允许一个进程访问该资源。
      • 资源：把在一段时间内只允许一个进程访问的资源成为临界资源（独占资源）。系统中大多数物理设备，以及栈、变量、表格都属于临界资源，都只能被互斥地共享
        • 12.对独占资源应采取何种共享方式？
    • 2.同时访问方式
      • 概念：系统中还有另一类资源，允许一段时间内由多个进程"同时"对它们进行访问。类似并发性质的同时访问
      • 资源：磁盘设备，一些用重入码编写的文件
  • 并发和共享是多用户(多任务)OS的两个最基本的特征。它们又互为存在的条件
    • 10.其最基本的特征是什么？
    • 一方面资源共享是以进程的并发执行为条件的，若系统不允许并发执行，也就不存在资源共享
    • 另一方面，若系统不能对资源共享实施有效管理，以协调好诸如进程对共享资源的访问，也必然影响到进程间并发执行的程度，甚至根本无法并发执行
  • 1.3.3 虚拟(Virtual)
    • 在OS中，把通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为"虚拟"
    • 1.时分复用技术
      • (1)虚拟处理机技术:利用多道程序设计技术把一台物理上的处理机虚拟为多台逻辑上的处理机，每台逻辑处理机上运行一道程序，我们把用户所感觉到的处理机称为虚拟处理机
        • 13.什么是时分复用技术？举例说明它能提高资源利用率的根本原因是什么。
      • (2)虚拟设备技术:通过时分复用将一台物理I/O设备虚拟为多台逻辑上的I/O设备，并允许每个用户访问的设备(临界资源)，变为共享资源(如供多个用户"同时"打印)
    • 2.空分复用技术
      • 虚拟存储器:空分复用技术是利用存储器的空闲空间分区域存放和运行其它的多道程序，以此来提高内存的利用率
      • 单纯的空分复用存储器只能提高内存的利用率，并不能在逻辑上扩大存储容量的功能，还必须引入虚拟存储技术才能达到此目的。
        • 虚拟存储技术本质上是实现内存的分时复用 例如一个100MB的应用程序之所以可以在30MB的内存空间上运行，实质上就是每次只把用户程序的一部分调入内存运行，运行完成后将该部分换出，再换另一部分到内存中运行，通过这样的置换功能，便实现了用户程序的各个部分分时地进入内存运行
  • 1.3.4 异步(Asynchronism)
    • 在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底。而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。只有系统拥有并发性，才可能导致异步性
      • 14.是什么原因使操作系统具有异步性特征?
• 1.4 操作系统的主要功能
  • 1.4.1 处理机管理功能
    • 传统多道程序中，处理机的分配和运行都是以进程为基本单位，因而多处理机的管理可归结为对进程的管理
    • 1.进程控制
      • 为作业创建进程，撤销（终止）已结束的进程，以及控制进程在运行过程中的状态转换
    • 2.进程同步
      • 为多个进程（含线程）的运行进行协调
        • ①进程互斥方式
          • 进程在对对临界资源的访问时
        • ②进程同步方式
          • 相互合作去完成共同任务的诸进程间，由同步机构对它们的执行次序加以协调（信号量机制）
    • 3.进程通信
      • 实现相互合作进程之间的信息交换
      • 当相互合作的进程处于同一计算机系统时，通常在它们之间采用直接通信的方式，即由源进程利用发送命令直接将消息挂到目标进程的消息队列上，以后由目标进程利用接收命令从其消息队列中取出消息
    • 4.调度
      • （1）作业调度
        • 以作业为单位，为它们分配运行所需的资源，将作业调入内存后，分别为它们建立进程，使他们都成为可能获得处理机的就绪进程，并将他们插入就绪队列中
      • （2）进程调度
        • 以进程为单位，将处理机分配给它，并为它设置运行现场，使其投入执行
  • 1.4.2 存储器管理功能
    • 存储器管理的主要功能，是为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用，并能从逻辑上扩充内存
    • 1.内存分配
      • 内存分配的主要任务
        • 为每道程序分配内存空间，使它们各得其所
        • 提高存储器的利用率，尽量减少不可用的内存空间（碎片）
        • 允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需要
      • 内存分配的两种方式
        • 静态分配方式：每个作业在内存空间是在作业装入时确定的，在作业装入后的运行期间不允许再申请内存空间，也不允许作业在内存中移动
        • 动态分配方式：每个作业所要求的基本内存空间虽然也是在装入时确定，但允许作业在运行过程中继续申请新的附加内存空间，以适应程序和数据的动态增长，也允许作业在内存中移动
    • 2.内存保护
      • 内存保护的主要任务
        • 确保每道用户程序都仅在自己的内存空间内运行，彼此不干扰
        • 绝不允许用户程序访问操作系统的程序和数据，也不允许用户程序转移到非共享的其它用户程序中去执行
      • 内存保护的机制
        • 一种较为简单的机制是设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。在程序运行时，系统需对每条指令所要访问的地址进行检查，若发生越界，便发出越界请求已停止该程序的执行
    • 3.地址映射
      • 地址映射的主要任务
        • 为了保证程序能正确运行，存储器管理必须提供地址映射功能，即能够将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址
      • 地址映射应在硬件的支持下完成
    • 4.内容扩充
      • 内存扩充的主要任务
        • 借助虚拟存储技术，从逻辑上扩充内存容量，使用户所感觉到的内存容量比实际内存容量大的多，以便让更多的用户程序能并发运行
      • 内存扩充必须实现的功能
        • (1)请求调入功能，系统允许在仅装入部分用户程序和数据的情况下，便能启动该程序运行。若要继续执行的程序和数据未装入内存，可向OS发出请求，将所需部分调入内存，以便继续运行
        • (2)置换功能，若发现内存中无足够的空间来装入调入的程序和数据时，系统应能将内存中的一部分暂时不用的程序和数据调入硬盘上，以腾出内存，可以使所需调入的部分装入内存
    • 14. 内存管理有哪些主要功能?他们的主要任务是什么？
  • 1.4.3 设备管理功能
    • 设备管理的主要任务
      • (1)完成用户进程提出的I/O请求，为用户进程分配所需的I/O设备，并完成指定的I/O操作
      • (2)提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备
    • 1.缓冲管理
      • 设置缓冲区的作用：可有效缓和CPU和I/O设备速度不匹配的矛盾，提高CPU利用率，进而提高系统吞吐量
      • 常见的缓冲区机制
        • 单缓冲机制
        • 能实现双向同时传送数据的双缓冲机制
        • 能供多个设备同时使用的公用缓冲池机制
    • 2.设备分配
      • 设备分配的基本任务
        • 是根据用户进程的I/O请求、系统现有资源的情况以及按照某种设备分配策略，为之分配其所需的设备
    • 3.设备处理
      • 设备处理的基本任务
        • 是用于实现CPU和设备控制器之间的通信 ，即由aCPU向设备控制器发出I/O命令，要求它完成指定的I/O操作；反之，由CPU接收从控制器发来的中断请求，并给于迅速的响应和相应的处理
  • 1.4.4 文件管理功能
    • 文件管理的主要任务是对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性
    • 1.文件存储空间的管理
      • 其主要任务是：为每个文件分配必要的外存空间，提高外存的利用率，进而提高文件系统的存取速度
    • 2.目录管理
      • 目录管理的主要任务
        • 为每个文件建立一个目录项，并对众多目录项加以有效地组织，实现方便的按名存取
        • 还应实现文件共享，这样只需在外存上保留一份该共享文件的副本
        • 还应能提供快速的目录查询手段，以提高对文件检索的速度
    • 3.文件的读/写管理和保护
      • 文件的读/写管理
      • 文件保护
        • 防止未经核准的用户存取文件
        • 防止冒名顶替存取文件
        • 防止以不正确的方式使用文件
    • 13. 文件管理有哪些主要功能？其主要任务是什么？
  • 1.4.5 操作系统与用户之间的接口
    • 1.用户接口
      • (1)联机用户接口
      • (2)脱机用户接口
      • (3)图形用户接口
    • 2.程序接口
      • 程序接口是为用户程序在执行中访问系统资源而设计的，是用户程序取得操作系统服务的唯一途径。
  • 1.4.6 现代操作系统的新功能
    • 1.系统安全
      • 认证技术
      • 密码技术
      • 访问控制技术
      • 反病毒技术
    • 2.网络的功能和服务
      • 网络通信
      • 资源管理
      • 应用互操作
    • 3.支持多媒体
      • 接纳控制功能
      • 实时调度
      • 多媒体文件的存储
• 1.5 OS的运行机制和体系结构
  • 1.5.1 运行机制
    • 1.两种指令
      • (1)特权指令
        • 如内存清零指令
      • (2)非特权指令
        • 如普通的运算指令
    • 2.两种处理器状态
      • 用程序状态寄存器PSW来记录当前状态
      • (1)核心态(管态)
        • 特权指令非特权指令都能执行
      • (2)用户态(目态)
        • 此时CPU只能执行非特权指令
      • (3)状态的转换
        • 用户态→核心态：中断是唯一途径
        • 核心态→用户态：执行一个特权指令，更改PSW
    • 3.两种程序
      • (1)内核程序
        • 操作系统的内核程序是系统的管理者，运行在核心态
      • (2)应用程序
        • 运行在用户态
  • 1.5.2 操作系统内核
    • 1.时钟管理
      • 实现计时功能
    • 2.中断处理
      • 负责实现中断机制
    • 3.原语
      • 是一种特殊的程序
      • 处于操作系统的底层，是最接近硬件的部分
      • 这种程序的运行具有原子性——其运行只能一气呵成，不能中断
      • 运行时间较短，调用频繁
    • 4.对系统资源进行管理的功能
      • (1)进程管理
      • (2)存储器管理
      • (3)设备管理
      • 有的操作系统不把这部分归为内核功能
  • 1.5.3 操作系统的体系结构
    • 1.大内核
      • 将操作系统的主要功能模块都作为操作系统的内核，运行在核心态
      • 优点：高性能
      • 缺点：内核代码量庞大，结构混乱，难以维护
    • 2.微内核
      • 只把最基本的功能保留在内核
      • 优点：内核功能少，结构清晰，易于维护
      • 缺点：需要频繁地在用户态和核心态下切换，性能低
• 1.6 OS结构设计
  • 1.6.1 传统操作系统结构
    • 1.无结构操作系统
    • 2.模块化结构OS
      • 1）模块化程序设计技术的基本概念
        • 该技术基于“分解”和“模块化”的原则来控制软件的复杂度，按其功能划分为若干个具有一定独立性和大小的模块，并仔细地规定各模块间的接口使其之间可以交互，再进一步将模块细分为子模块，同样规划好接口，这种设计方法即为模块-接口法
      • 2）模块的独立性
        • 内聚性：指模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越强
        • 耦合度：指模块间相互联系和相互影响的程度。耦合行越低，模块独立性越强
      • 3）模块接口法的优缺点
        • 优点
          • 提高OS设计的正确性、可理解性和可维护性
          • 增强OS的可适应性
          • 加速OS的开发过程
        • 缺点
          • 在OS设计时，对模块间的接口规定很难满足模块设计完成后对接口的实际需求
          • 各模块的设计难以齐头并进，造成各种决定的“无序性”，因此模块接口法又称为“无序模块法”
    • 3.分层式结构OS
      • 1）分层式结构的基本概念
        • 将模块接口法中的无序性变为了有序性，引入了有序分层法，常采用自底向上法来铺设目标系统和裸机系统之间的中间层
      • 2）分层结构的优缺点
        • 优点
          • 易保证系统的正确性。自下而上的设计方式使后续的结构是基于可靠的基础上的。
          • 易扩充和易维护性。在系统中修改一个层次或者模块只需要改变相应的接口，不会影响其他层次。
        • 缺点
          • 主要缺是系统效率较低。由于层次结构是分层单向依赖的，必须在每层之间都建立层次间的通信机制，OS每执行一个功能，通常要自上而下穿越多个层次，会增加系统通信的开销导致系统效率的降低
  • 1.6.2 客户/服务器模式（Client/Server Model）简介
    • 1.客户/服务器模式的组成
      • (1)客户机：每台客户机都是自主计算机，具有一定处理能力，客户进程在其上运行，可以发消息给服务器请求某项服务
      • (2)服务器：通常是大规模的机器，其上存在网络文件系统和数据库系统等，能为网上的所有用户提供一种或多重服务
      • (3)网络系统：用于连接所有的客户机和服务器，实现他们之间通信和资源共享的系统
    • 2.客户/服务器之间的交互
      • 客户发送请求消息→服务器接受消息→服务器回送消息→客户机接受消息
    • 3.客户/服务器模式的优点
      • (1)数据的分布处理和存储。由于客户机也具有相当强的处理和存储能力，可以进行本地处理和数据的分布存储，从而摆脱了由于把一切数据都存放在主机中而造成的既不可靠又容易产生瓶颈现象的困难局面
      • (2)便于集中管理。尽管C/S模式具有分布处理功能，但重要资料等仍可采用集中管理方式
      • (3)灵活性和可扩充性。理论上客户机和服务器的数量不受限制，而且可以配置多种类型的客户机和服务器
      • (4)易于改变应用软件。对于客户机程序的修改和增删比传统集中模式要容易的多，必要时也允许由客户进行修改
  • 1.6.3 面向对象的程序设计（Object-Orientated Programming）技术简介
    • 1.面向对象技术的基本概念
      • OS中的各类实体使用了对象这一概念便有了进程对象，线程对象，消息对象，存储器对象和文件对象等
    • 2.面向对象技术的优点
      • (1)通过“重用”提高产品质量和生产率。
      • (2)使系统具有更好的易修改性和易扩展性。
      • (3)更易于保证系统的“正确性”和“可靠性”
  • 1.6.4 微内核OS结构
    • 1.微内核操作系统的基本概念
      • 1）足够小的内核
        • 微内核是指精心设计的、能实现现代OS最基本核心功能的小型内核，只将操作系统中最基本的部分放入微内核
          • ①与硬件处理紧密相关的部分
          • ②一些较基本的功能
          • ③客户和服务器之间的通信
      • 2）基于客户/服务器模式
        • 将操作系统中最基本的功能放入内核中，而把操作系统的绝大部分功能都放在微内核外面的一组服务器（进程）中实现
      • 3）应用“机制与策略分离”原理
        • 机制：是指实现某一功能的具体执行机构
        • 策略：是在机制的基础上借助于某些参数和算法来实现该功能的优化，或达到不同的功能目标
        • 在微内核操作系统中通常将机制放在OS的微内核中，正因如此，内核才有可能做的很小
      • 4）采用面向对象技术
        • 可以确保操作系统的“正确性”“可靠性”“易修改性”和“易扩展性”
      • 12．微内核操作系统从哪四个方面进行描述。
    • 2.微内核的基本功能
      • 1）进程(线程)管理
        • 为实现进程(线程)的调度功能，需要在进程管理中设置优先级队列，这属于调度功能的机制部分，应将它放入微内核中
        • 由于进程(线程)之间的通信属于微内核OS的最基本功能，被频繁使用，所以进程间的通信功能，进程切换，线程的调度，以及多处理机间的同步等功能也放入微内核中
      • 2）低级存储器管理
        • 通常在微内核中，只配置最基本的低级存储器管理机制，如用于实现将用户的逻辑地址变换为内存空间物理地址的页表机制和地址变换机制，这一部分是依赖硬件的，因此放入微内核
      • 3）中断和陷入处理
        • 大多数微内核操作系统都是将与硬件紧密相关的一小部分放入微内核中处理，此时微内核的主要功能是捕获发生的中断和陷入事件
        • 在微内核OS中是将进程管理，存储器管理以及I/O管理这些功能一分为二，属于机制的很小一部分放入微内核中，另外绝大部分放在微内核外中的各种服务器中来实现
    • 3.微内核操作系统的优点
      • (1)提高了系统的可扩展性。当开发了新的硬件或软件时，微内核OS只需要在相应的服务器中增加新的功能或者添加新的服务器即可。
      • (2)增强了系统的可靠性
        • 微内核是通过精心设计和严格测试的，容易保证其正确性
        • 它提供了规范而精简的API，为微内核外部程序编制高质量代码创造了条件
        • 由于服务器都是运行在用户态，服务器之间采用的是消息传递通信机制，因此当某个服务器出现错误时不会影响内核，也不会影响其他服务器
      • (3)可移植性强。所有与特定CPU和I/O设备硬件有关的代码，均放在内核和内核下面的硬件隐藏层中，而操作系统其他的绝大部分--各种服务器，均与硬件平台无关
      • (4)提供了对分布式系统的支持。微内核OS中，客户和服务器之间、服务器和服务器之间的通信均采用消息传递通信机制，致使微内核OS能够很好的支持分布式系统和网络系统
      • (5)融入了面向对象技术
      • 11．微内核操作系统具有哪些优点？它为何能有这些优点？
    • 4.微内核操作系统存在的问题
      • 较之早期的操作系统，微内核操作系统的运行效率有所降低
        • 在完成一次客户对操作系统提出的服务请求时，需要利用消息实现多次交互和进行用户/内核模式与上下文的多次切换
        • 早期OS：①客户发送请求给系统②系统完成服务返回客户
        • 微内核OS：①客户发送请求给微内核②微内核把客户请求发给服务器③服务器返回响应消息给微内核④微内核响应消息给客户（如果某个服务器尚无能力完成，还需要寻求其他服务器的帮助）
      • 为了改善运行效率，可以重新把一些常用的操作系统基本功能由服务器移入微内核中。但这样又会使微内核容量增大，在小型接口定义和适应性方面的优点也有所下降，并提高了微内核的代价
• 1.7 中断和异常
  • 1.中断机制的诞生
    • 为了实现多道程序并发执行而引入的一种技术
  • 2.中断的概念和作用
    • 发生中断，就意味着需要操作系统介入开展管理工作，CPU会立刻进入核心态
    • 中断是CPU从用户态进入核心态的唯一途径
  • 3.中断的分类
    • 1.内中断(也称为异常、陷入、例外)
      • 信号的来源：CPU内部，与当前执行的指令有关
      • 陷阱、陷入(trap)
        • 如：系统调用时的指令
      • 故障(fault)
        • 如：缺页中断
      • 强迫中断，终止(abort)
        • 硬件故障
          • 如：缺页
        • 软件中断
          • 如：整数除0
    • 2.外中断(狭义的中断)
      • 信号的来源：CPU的外部，与当前执行的指令无关
      • 外设请求
        • 如：I/O系统操作完成发出的中断信号
      • 人工干预
        • 如：用户强制终止进程
  • 4.外中断的处理过程
• 1.8 系统调用
  • 1.什么是系统调用？有何作用？
    • (1)概念
      • 系统调用是操作系统提供给应用程序使用的接口
    • (2)作用
      • 应用程序通过系统调用来获得操作系统的服务
      • 系统调用会使处理器从用户态变为核心态
    • (3)分类
      • 设备管理
      • 文件管理
      • 进程控制
      • 进程通信
      • 内存管理
  • 2.系统调用和库函数的区别
    • 1.系统调用是操作系统向上层提供的接口
    • 2.有的库函数是对系统调用的进一步封装
    • 3.当今编写的绝大多数应用程序大多都是通过高级语言提供的库函数间接地进行系统调用
  • 3.系统调用的过程
    • 1.传递系统调用参数
    • 2.执行陷入指令
    • 3.执行系统调用的相应服务
    • 4.返回用户程序
• 操作系统发展历程
  • 从1945年诞生的第一台计算机，到50年代中期的计算机，都属于第一代计算机。 这时还未出现OS，对计算机的全部操作都是由用户采取人工操作方式进行
  • 为了解决CPU和I/O设备之间的设备不匹配的矛盾，20世纪50年代末出现了脱机I/O技术。该技术是事先将装有用户程序和数据的纸带装入纸带输入机，在一台外围机的控制下，把纸带上的数据输入到磁带上。当CPU需要这些程序和数据时，再从磁带上高速地调入内存。
  • 20世纪50年代中期出现了第二代晶体管计算机，此时计算机虽已具有推广应用的价值，但计算机系统仍然非常昂贵。为了能充分地提高它的利用率，应尽量保持系统的连续运行，即处理完一个作业后，紧接着处理下一个作业，以减少机器的空闲等待时间
  • 20世纪60年代中期，IBM公司生产了第一台小规模集成电路计算机IBM360.由于它较之于晶体管计算机无论在体积、功耗、速度和可靠性上都有了显著的改善，因而获得了极大的成功，IBM的OS/360操作系统是第一个能运行多道程序的批处理系统
  • 随着VLSI(超大规模集成电路，Very Large Scale Integration)和计算机体系结构的发展，以及应用需求的不断扩大，操作系统仍在继续发展。由此先后形成了微机操作系统、网络操作系统等。

第二章 进程的描述与控制

• 2.1 前趋图和程序执行
  • 2.1.1 前趋图
    • 前趋图的概念：所谓前趋图(Precedence Graph)是指一个有向无循环图，可记为DAG(Directed Acyclic Graph),它用于描述进程之间执行的先后顺序
      • 1.什么是前趋图？
    • 进程(或程序)之间的前趋关系可用“→”表示，如果进程pi和pj存在着前趋关系，可以表示为(pi,pj)∈→，也可以写成pi→pj，在表示pj开始执行之前pi必须完成。此时称pi是pj的直接前趋，而称pj是pi的直接后继
    • 前驱图中把没有前趋的结点称为初始结点(Initial Node),把没有后继的结点称为终止节点(Final Node)，此外每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。
    • 可用前趋图来表示进程(程序)的前趋关系
      • 1.为什么要引入前趋图？
  • 2.1.2 程序顺序执行
    • 1.程序的顺序执行
      • 用结点代表各个程序段的操作，如果I代表输入操作，C代表计算操作，P代表打印操作，箭头指示操作的先后次序，前趋关系为I→C→P
      • 包含三个语句的程序段S1:a=x+y,S2:b=a-5,S3:c=b+1，可以做出前趋关系
    • 2.程序顺序执行时的特征
      • ①顺序性：每一个操作必须在下一个操作开始前结束
      • ②封闭性：程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态只有本程序才能改变它，程序一旦执行，其执行结果不受外界因素影响
      • ③可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是间断执行还是不停顿地执行都可获得相同结果
  • 2.1.3 程序并发执行
    • 1.程序的并发执行
      • 若前趋关系同为I→C→P时，由于I2和C1之间不存在前趋关系，所以并发执行结果如图
      • 包含四个语句的程序段S1:a=x+2,S2:b=y+4,S3:c=a+b,S4:d=c+b，可以做出前趋关系
        • 2.试画出下面四条语句的前趋图：
    • 2.程序并发执行时的特征
      • ①间断性：程序并发执行时，由于共享系统资源，致使这些并发执行的程序之间形成了相互制约的关系，导致并发程序具有“执行——暂停——执行”的间断性活动规律
        • 3.为什么程序并发执行会产生间断性特征？
      • ②失去封闭性：当系统中存在着多个可以并发执行的程序时，系统中的资源将为它们共享，而这些资源的状态也会由这些程序来改变，致使其中任一程序在运行时，其环境必然受到其他程序的影响。
        • 4.程序并发执行时为什么会失去封闭性和可再现性？
      • ③不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其失去可再现性
• 2.2 进程的描述
  • 2.2.1 进程的定义和特征
    • 1.进程的定义和特征
      • 进程控制块(Process Control Block, PCB):操作系统中配置的一个专门的数据结构，用于描述进程的基本情况和活动过程，进而控制和管理进程
      • 由程序段、相关的数据段和PCB三部分构成了进程实体(又称进程映像)，进程实体简称进程
        • 所谓创建进程，实质上是创建进程实体中的PCB;而撤销进程，实质上就是撤销进程的PCB
      • 进程的典型定义
        • (1)进程是程序的一次执行
        • (2)进程是一个程序及其数据在处理机上的顺序执行时所发生的活动
        • (3)进程是具有独立功能的程序在一个数据集合上所运行的过程，它是系统进行资源分配和调度的一个独立单位
        • 我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”
      • 为了使程序在多道程序环境下能够并发执行，并能对并发执行的程序加以控制和描述，从而在操作系统中引入了进程的概念。影响：使程序得以并发执行
        • 5.在操作系统中为什么要引入进程的概念？它会产生什么样的影响？
        • 1. 在操作系统中为什么要引入进程概念？它的特征是什么？
    • 2.进程的特征
      • (1)动态性。
        • 进程的实质是进程实体的执行过程(它由创建而产生，由调度而执行，由撤销而消亡)，因此动态性就是进程的最基本的特征
          • 程序则只是一组有序指令的集合，并存放于某种介质上，其本身不具有活动的含义，因而是静态的
      • (2)并发性。
        • 是指多个进程实体同存于内存中，并能在一段时间内同时运行。
          • 而程序(没有建立PCB)是不能参与并发执行的
      • (3)独立性。
        • 是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
          • 对于未建立任何进程的程序，不能作为一个独立的单位而运行
      • 6.试从动态性、并发性和独立性上比较进程和程序。
      • (4)异步性。
        • 是指进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。
  • 2.2.2 进程的基本状态及转换
    • 1.进程的三种基本状态
      • (1)就绪(Ready)状态:指进程已处于准备好运行的状态，即进程已分配到除CPU意外的所有必要资源后，只要再获得CPU，便可立即执行。
      • (2)执行(Running)状态:指进程已获得CPU，其程序正在执行的状态。
      • (3)阻塞(Block)状态:指正在执行的进程由于发生某事件(如I/O请求、申请缓冲区失败等)暂时无法继续执行时的状态，亦即进程的执行受到阻塞。
    • 2.三种基本状态的转换
      • (1)就绪状态→执行状态：进程分配到CPU资源
      • (2)执行状态→就绪状态：时间片用完
      • (3)执行状态→阻塞状态：I/O请求
      • (4)阻塞状态→就绪状态：I/0完成
      • 2.试说明进程在三个基本状态之间转换的典型原因。
    • 3.创建状态和终止状态
      • 为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性，通常在系统中又为进程引入两种常见状态
    • 进行进程切换时，所要保存的处理机状态信息有
      • (1)进程当前暂存地址
      • (2)下一条指令地址
      • (3)进程状态信息
      • (4)过程和系统调用参数及调用地址信息
      • 13.在进行进程切换时，所要保存的处理机状态信息有哪些？
  • 2.2.3 挂起操作和进程状态的转换
    • 进程除了就绪、执行和阻塞三种最基本的状态外，为了系统和用户观察和分析进程的需要，还引入了一个对进程的重要操作——挂起操作。执行状态挂起会暂停执行。就绪状态挂起会使进程此时不接受调度。与挂起操作对应的操作是激活操作
      • 12.挂起状态有哪些性质？
    • 1.挂起操作的引入
      • (1)终端用户的需要。当用户发现程序运行期间有问题希望自己的程序暂停，使之停止下来。
      • (2)父进程请求。有时父进程希望挂起自己的某个自进程以便考察和修改该子进程。
      • (3)负荷调节的需要。当实时系统中的工作负荷较重可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统的正常运行。
      • (4)操作系统的需要。操作系统有时挂起某些进程一遍检查运行中的资源使用情况或进行记账。
      • 12.为什么要引入挂起状态？
    • 2.引入挂起原语操作后三个进程状态的转换
      • 挂起原语Suspend和激活原语Active
      • (1)活动就绪→静止就绪。活动就绪Readya使用挂起原语Suspend后转变为静止就绪Readys，Readys状态的进程不再被调度执行
      • (2)活动阻塞→静止阻塞。活动阻塞Blockeda使用挂起原语Suspend后转变为静止阻塞Blockeds，Blockeds状态的进程在期待事件出现后，将由Blockeds变为Readys状态
      • (3)静止就绪→活动就绪。静止就绪Readys使用激活原语Active激活后转变为活动就绪Readya。
      • (4)静止阻塞→活动阻塞。静止阻塞Blockeds使用激活原语Active激活后转变为活动阻塞Blockeda。
    • 3.引入挂起操作后五个进程状态的转换
      • (1)NULL→创建。一个新进程产生时，该进程处于创建状态
      • (2)创建→活动就绪。在当前系统的性能和内存的容量均允许的情况下，完成对进程创建的必要操作后，相应的系统进程将进程的状态转为活动就绪状态
      • (3)创建→静止就绪。考虑到系统当前资源状况和性能的要求下，不分配给新建进程所需资源，主要是主存，相应的系统将进程状态转为静止就绪状态，被安置在外村，不参与调度，此时进程创建工作尚未完成
      • (4)执行→终止。当一个进程已完成任务时，或是出现了无法克服的错误，或者是被OS或是其他进程所终结，此时将进程的状态转换为终止状态
  • 2.2.4 进程管理中的数据结构
    • 1.操作系统中用于管理控制的数据结构
      • 内存表
      • 设备表
      • 文件表
      • 进程管理的进程表(PCB)
    • 2.进程控制块PCB的作用
      • PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。
      • (1)作为独立运行基本单位的标志。当一个程序(含数据)配置了PCB后，就表示它已是一个能够在多道程序环境下独立运行的、合法的基本单位。PCB已成为进程存在系统中的唯一标志
        • 7.为什么说PCB是进程存在的唯一标志？
      • (2)能实现间断性运行方式。当进程因阻塞而暂停运行时，它必须保留自己运行CPU现场信息，再次被调度运行是恢复其CPU现场信息。
      • (3)提供进程管理所需要的信息。进程的整个生命期中，操作系统总是根据PCB实施对进程的控制和管理
      • (4)提供进程调度所需要的信息。只有处于就绪状态的进程才能被调度执行，而在PCB中就提供了进程处于何种状态的信息。
      • (5)实现与其它进程的同步与通信。进程同步机制是用于实现诸进程的协调运行的，在采用信号量机制时，它要求每个进程中都设置有相应的用于同步的信号量。PCB中还有用于实现进程通信的区域或通信队列指针等。
      • 7.试说明PCB的作用具体表现在哪几个方面？
    • 3.进程控制块中的信息
      • (1)进程标识符
        • 外部标识符:创建者提供，通常有字母与数字组成，往往是由用户(进程)在访问该进程时使用。
        • 内部标识符:操作系统为每一个进程赋予的唯一数字标识符，系统使用
      • (2)处理机状态
        • 通用寄存器
        • 指令计数器
        • 程序状态字PSW
        • 用户栈指针
      • (3)进程调度信息
        • 进程状态
        • 进程优先级
        • 进程调度所需的其他信息
        • 事件
      • 8.PCB提供了进程管理和进程调度所需要的哪些信息？
      • (4)进程控制信息
        • 程序和数据的地址
        • 进程同步和通信机制
        • 资源清单
        • 链接指针
      • 3.进程控制块中的信息包括几个方面，分别是什么?
    • 4.进程控制块的组织方式
      • (1)线性方式:将系统中的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。实现简单，开销小，但每次都需要扫描整张表，因此适合进程数目不多的系统
      • (2)链接方式:把具有相同状态进程的PCB通过PCB中的链接字连成一个队列
      • (3)索引方式:系统根据所有进程状态的不同，建立几张索引表，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址
      • 4.进程控制块的组织方式有哪几种？
• 2.3 进程控制
  • 进程控制一般是由OS的内核中的原语来实现的
  • 2.3.1 操作系统内核
    • 概念：将一些与硬件紧密相关的模块(如中断处理程序等)、各种常用设备的驱动程序以及运行频率较高的模块(如时钟管理、进程调度和许多模块所共用的一些基本操作)都安排在紧靠硬件的软件层次中，使它们常驻内存，即通常被称为的OS内核
      • 10.何谓操作系统内核？
    • 这样安排的目的
      • ①便于对这些软件进行保护，防止遭受到应用程序的有意或无意的破坏
      • ②可以调高OS的运行效率
    • 两大功能
      • 1.支撑功能
        • (1)中断处理：如各种类型的系统调用、键盘命令的输入、进程调度、设备驱动等无不依赖于中断
        • (2)时钟管理：如时间片轮转调度，实时系统中的截止时间控制、批处理系统中的最长运行时间控制等
        • (3)原语操作：如用于链表进行操作的原语、用于实现进程同步的原语等
          • 所谓原语(Primitive)就是由若干条指令组成的，用于完成一定功能的一个过程，它与一般过程的区别为，原语是“原子操作(Action Operation)”，所谓原子操作就是一个操作中的所有动作要么全做，要么不做，不可分割。
      • 2.资源管理功能
        • (1)进程管理：或者由于各个功能模块的运行频率较高，或者由于它们为多种功能模块所需要，通常将它们放在内核中
        • (2)存储器管理：存储器管理软件的运行频率也比较高，通常也将它们放在内核中，以保证存储器管理具有较高的运行速度
        • (3)设备管理：由于设备管理和硬件(设备)紧密相关，因此很大部分也设置在内核中
      • 10.内核的主要功能是什么？
  • 2.3.2 进程的创建
    • 1.进程的层次结构
      • 把创建进程的进程称为父进程，把被创建的进程称为子进程。子进程可以继续创建孙进程由此便形成了一个进程的层次结构，在UNIX中，进程们功能组成了一个进程家族(组)
      • 子进程可以继承父进程的所有资源，例如继承父进程打开的文件，分配到的缓冲区等。子进程被撤销后需要归还资源给父进程。父进程被撤销后，必须同时撤销子进程。PCB中设置了家族关系表项，以表明自己的父进程及所有的子进程。进程不能拒绝其子进程的继承权
      • 在Windows中，不存在任何进程层次结构的概念，所有进程都有相同的地位。进程之间的关系仅仅是获得句柄与否、控制与被控制的简单关系
    • 2.进程图
      • 所谓进程图(Process Graph)就是用于描述进程间关系的一棵有向树，树的根节点被称为进程家族的祖先(Ancestor)
    • 3.引起创建进程的事件
      • (1)用户登录
      • (2)作业调度
      • (3)提供服务
      • (4)应用请求
      • 6.试说明引起进程创建的主要事件
    • 4.进程的创建(Creation of Process)过程
      • (1)出现了创建新进程的请求后，OS便调用进程创建原语Creat按以下步骤创建一个新进程
      • (2)申请空白PCB，为进程获得唯一的数字标识符，并从PCB集合中索取一个空白PCB
      • (3)为新进程分配其运行所需的资源，包括各种物理和逻辑资源
      • (4)初始化进程控制块PCB
        • ①初始化标识信息
        • ②初始化处理机状态信息
        • ③初始化处理机控制信息
      • (5)如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列
      • 5.怎样创建一个新的进程?
  • 2.3.3 进程的终止
    • 1.引起进程终止的事件
      • (1)正常结束
        • 进程任务已经完成，准备退出运行
        • 在批处理系统中，通常在程序的最后安排一条Halt指令表示进程完成
        • 在分时系统中，用户可利用Logs off去表示进程运行完毕
      • (2)异常结束
        • ①越界错
        • ②保护错
        • ③非法指令
        • ④特权指令错
        • ⑤运行超时
        • ⑥等待超时
        • ⑦算术运算错
        • ⑧I/O故障
      • (3)外界干预
        • ①操作员或操作系统干预
        • ②父进程请求
        • ③因父进程终止
      • 6.试说明引起进程被撤销的主要事件
    • 2.进程的终止(Termination of Process)过程
      • 当系统中发生了要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止特定的进程
      • (1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，读出该进程的状态
      • (2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
      • (3)若该进程还有子孙进程，应将其所有的子孙进程都予以终止，以防它们成为不可控的进程
      • (4)将被终止进程所拥有的的全部资源归还给父进程或者是系统
      • (5)将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息
      • 10.在撤销一个进程时所完成的主要工作是什么？
  • 2.3.4 进程的阻塞与唤醒
    • 1.引起阻塞和唤醒的事件
      • (1)向系统请求资源失败：如请求打印机但打印机资源已被占用
      • (2)等待某种操作的完成：如等待I/O操作完成后再由中断处理程序唤醒进程
      • (3)新数据尚未到达：如进程A未收到需要的来自进程B的数据，此时便阻塞A
      • (4)等待新任务的到达：在网络环境下的OS，某些进程完成任务后就将自身阻塞起来等待新任务的到来
      • 8.试说明引起进程阻塞或被唤醒的主要事件是什么？
    • 2.进程阻塞过程
      • (1)进程调用阻塞原语block将自己阻塞
      • (2)把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列
      • (3)转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，即保留被阻塞进程的处理机状态，按新进程的PCB中的处理机状态设置CPU的环境
    • 3.进程唤醒过程
      • (1)有关进程调用唤醒原语wakeup将等待该事件的进程唤醒
      • (2)首先把被阻塞的进程从等待该事件阻塞队列中移出
      • (3)将PCB中的现行状态由阻塞改为就绪
      • (4)然后再将该PCB插入到就绪队列中
  • 2.3.5 进程的挂起与激活
    • 1.进程的挂起过程
      • (1)系统中出现引起进程挂起的事件时，OS利用挂起原语suspend将指定进程或处于阻塞状态的进程挂起
      • (2)首先检查被挂起进程的状态，若处于活动就绪(阻塞)状态便将其改为静止就绪(阻塞)状态
      • (3)为了方便用户或父进程考察该进程的运行情况，把该进程的PCB复制到某指定的内存区域
      • (4)若被挂起的进程正在执行，则转向调度程序重新调度
    • 2.进程的激活过程
      • (1)系统中出现发生激活进程的事件时，OS利用激活原语active将指定进程激活
      • (2)激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪(阻塞)状态便将其修改为活动就绪(阻塞)状态
      • (3)若采用的是抢占调度策略，则每当有静止就绪进程被激活而插入就绪队列时，便应检查是否要进行重新调度
      • (4)即由调度程序将被激活的进程与当前进程两者的优先级进行比较，若被激活进程的优先级低，则不必重新调度，否则，应立即剥夺当前进程的运行，把处理机分配给刚刚被激活的进程
• 2.4 进程同步
  • 2.4.1 进程同步的基本概念
    • 进程同步机制的主要任务：是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性
      • 7. 什么是进程同步？
    • 1.两种形式的制约关系
      • 在多道程序环境下，对于处于同一个系统中的多个进程，由于它们共享系统的资源，或为完成某一任务而相互合作，它们之间可能存在着以下两种形式的制约关系
      • 1）间接相互制约关系：由于临界资源必须保证多个进程对之只能互斥的访问，因此进程间形成了源于对该类资源共享的所谓间接相互制约关系，对于此类资源，进程使用之前必须进行申请后由系统实施统一分配
      • 2）直接相互制约关系：由于某些进程为了完成同一项任务二相互合作，进程间的直接制约关系就是源于它们之间的相互合作。
    • 2.临界资源(critical Resource)
      • 许多硬件资源如打印机、磁带机均为临界资源，诸进程间应采取互斥方式，实现对这种资源的共享
      • 生产者-消费者(Producer-consumer)问题
        • 在并发执行的过程中，为了保证缓冲区中的产品数量counter不为0或满，应将counter作为临时资源去处理，即消费者进程和生产者进程互斥地访问变量counter
    • 3.临界区(critical section)
      • 概念：人们把每个进程中访问临界资源的那段代码称为临界区
        • while(TRUE) { 进入区 临界区 退出区 剩余区 }
          • 进入区：负责检查是否可进入临界区，若可进入，则应该上锁 临界区：访问临界资源的代码 退出区：负责解锁 剩余区：负责实现其他功能
      • 进入区和退出区共同负责实现互斥
    • 4.同步机制应遵循的规则
      • (1)空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源
      • (2)忙则等待。当已有进程处于临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问
      • (3)有限等待。对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死等”状态
      • (4)让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态
      • 11. 同步机构应遵循哪些基本准则？为什么？
        • 为了实现进程互斥访问自己的临界区
  • 实现进程互斥的软件方法
    • 1.单标志法
      • (1)算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
      • (2)算法实现
        • int turn = 0; // turn表示当前允许进入临界区的进程号
        • PO(){ while(turn!=0); 临界区代码; turn=1; 剩余区代码; }
          • P1(){ while(turn!=1); 临界区代码; turn=0; 剩余区代码; }
      • (3)算法特点
        • 对于进入临界区的值，一定是按照P0→P1→PO...这样的轮流顺序，因此如果某时允许进入临界区的进程是P0，而P0一直不访问临界区，那么此时即使临界区空闲，也不允许P1访问
        • 违背“空闲让进”原则
    • 2.双标志先检查法
      • (1)算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=true”意味着0号进程P0现在想要进入临时区，每个进程进入临界区之前都该先检查当前有没有其它进程的flag标志为true，若可以进入后，将自己的表示flag设置为true后，开始访问临界区
      • (2)算法实现
        • bool flag[2]; flag[0]=false; flag[1]=false;
        • P0(){ while(flag[1]); flag[0]=true; 临界区代码; flag[0]=false; 剩余区代码; }
          • P1(){ while(flag[0]);// 检查 flag[1]=true; // 上锁 临界区代码; flag[1]=false; 剩余区代码; }
      • (3)算法特点
        • 若上述实现中的“检查”操作由于进程异步发生进程切换，P0和P1将会同时访问临界区
        • 违背“忙则等待”原则
    • 3.双标志后检查法
      • (1)算法思想：双标志后检查法的改版。前一个算的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述的问题。
      • (2)算法实现
        • bool flag[2]; flag[0]=false; flag[1]=false;
        • PO(){ flag[0]=true; while(flag[1]); 临界区代码; flag[0]=false; 剩余区代码; }
          • P1(){ flag[0]=true; // 上锁 while(flag[1]);// 检查 临界区代码; flag[1]=false; 剩余区代码; }
      • (3)算法特点
        • 若上述的“上锁”操作由于进程异步发生了进程切换，导致所有的标志flag均为true，此时P0和P1都无法访问临界区
        • 解决了“忙则等待”但是又违背了“空闲让进”和“有限等待”
    • 4.Peterson算法
      • (1)算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让进，最后谁都无法进入临界区。Gary L.Peterson想到了一种方法，如果双方都想争着进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。
      • (2)算法实现
        • bool flag[2];int turn=0;
        • PO(){ flag[0]= true; turn=1; while(flag[1] && turn==1); 临界区代码; flag[0]=false; 剩余区代码; }
          • P1(){ flag[1]= true; turn=0; while(flag[0] && turn==0); 临界区代码; flag[1]=false; 剩余区代码; }
      • (3)算法特点
        • Peterson算法用软件解决了进程互斥的问题，遵循了“空闲让进”、“忙则等待”和“有限等待”三个原则，但仍然未遵循“让权等待”的原则
  • 2.4.2 硬件同步机制
    • 1.关中断
      • 在进入锁测试之前关闭中断，直到完成锁测试之后才能打开中断。
        • 锁测试：每个要进入临界区的进程必须先对锁进行测试，锁未开时必须等待，直至锁被打开。反之，当锁是打开的时候，应立即把其锁上，以阻止其他进程进入临界区。
      • 关中断的缺点
        • ①滥用关中断权利可能导致严重后果
        • ②关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力
        • ③关中断方法也不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其他处理器上执行相同的临界段代码
    • 2.利用Test-and-Set指令实现互斥
      • 是一种借助一条硬件指令——“测试并建立”指令TS(Test-and-Set)以实现互斥的方法
        • boolean TS(boolean *lock) { boolean old; old = *lock; *lock = TRUE; return old; }
          • while (TS(&lock)); 临界区代码段 lock = false 剩余区代码段
    • 3.利用Swap指令实现进程互斥
      • 逻辑上看Swap和TS指令并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)
        • bool old = true; while(old == true) swap(&lock,&old); 临界区代码段 lock = false 剩余代码段
    • 特点
      • 该指令可以看作为一个函数过程，其执行过程是不可分割的，即是一条原语
      • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
      • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TS指令，从而导致“忙等”
  • 2.4.3 信号量机制
    • 信号量其实就是一个变量(可以是一个整数，也可以是一个更加复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如系统中只有一台打印机，就可以设置一个初值为1的信号量
    • 1.整型信号量
      • 整型量S用于表示资源数目，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问，二者被分别称作P、V操作
        • wait(S){// wait原语，相当于进入区 while(S<=0);//进入“忙等”状态 S--; // 占用一个资源，此时S少一 }
        • signal(S){ // signal原语，相当于退出区 S++; // 使用完资源后，释放资源 }
      • wait原语和双标志先检查法一样是“检查”，“上锁”。但是wait中的两个操作是一气呵成的。但只要是信号量S<=0，就会不断的测试但是同样不满足“让权等待”原则，而是处于“忙等状态”
    • 2.记录型信号量
      • typedef struct { int va Lue;//剩余资源数 struct process *L; // 等待队列，记录被阻塞的进程 } semaphore;
      • /*某进程需要使用资源时，通过wait原语申请*/ void wait (semaphore S) { S.value--; if (S.value <0 ) { block (S.L); } } //block()函数：如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列(即阻塞队列)中
      • /*进程使用完资源后，通过signal原语释放*/ void signal (semaphore S) { s. value++; if (S.value <= 0) { wakeup(S.L); } } //wakeup()函数：释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
      • S.value表示某种资源数，S.L指向该资源的队列 P操作中，一定是先S.value--，之后可能需要执行block原语 V操作中，一定是先S.value++，之后可能需要执行wakeup原语 可以用记录型信号量实现系统资源的“申请”和“释放” 可以用记录型信号量实现进程互斥、进程同步
      • 注：若考试中出现P(S)和V(S)的操作，除非特别说明，否则默认S位记录型信号量
    • 3.AND型信号量
      • AND型信号量机制针对的是多个并发进程仅共享多个临界资源的情况。
        • wait(S1, S2, …, Sn) { While(TRUE) { if (S1 >=1 and … and Sn>=1 ){ for( i=1 ;i<=n; i++) Si--; break; } else{ Place the process in the waiting queue associated with the first Si found with Si < 1,and set the progress count of this process to the beginning of Swait operation } } }
        • signal(S1, S2, …, Sn){ while(TRUE){ for (i=1; i<=n; i++) { Si++ ; Remove all the process waiting in the queue associated with Si into the ready queue } } }
      • AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。即要不全分配，要不不分配。这样便可避免发生临界资源死锁的问题
    • 4.信号量集
      • 在AND信号量机制下改进的内容
        • ①可以每次对某类临界资源进行N个单位的申请和释放
        • ②为了确保安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予分配
      • 一般信号量集的几种特殊情况
        • (1)Swait(S,d,d)。此时在信号量集中仅有一个信号量S，但允许它每次申请d个资源，当现有资源少于d时，不予分配
        • (2)Swait(S,1,1)。此时信号量集已蜕化成一般的记录型信号量(S>1时)或互斥信号量(S=1时)
        • (3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控的开关
  • 2.4.4 信号量的应用
    • 1.利用信号量实现进程互斥
      • (1)分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应放在临界区)
      • (2)设置互斥信号量mutex，初值为1
      • (3)在临界区之前执行P(mutex)
      • (4)在临界区之后执行V(mutex)
      • semaphore mutex = 1; // 初始化信号量 P1(){ ... P(mutex); // 使用临界资源前需要加锁 临界区代码段 V(mutex); // 使用临界资源后需要解锁 ... }
        • P2(){ ... P(mutex); 临界区代码段 V(mutex); ... }
      • 注意
        • 对不同临界资源需要设置不同的互斥信号量(变量)
        • P、V操作必须成对出现
          • 缺少P(mutex)就不能保证临界资源的互斥访问
          • 缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒
    • 2.用信号量实现进程同步
      • 进程同步：要让各进程按要求有序的推进。让本来异步并发进程相互配合，有序推进
      • (1)分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
      • (2)设置同步信号量S，初值为0
      • (3)在“前操作”之后执行V(S)
      • (4)在“后操作”之前执行P(S)
      • semaphore S = 0; P1(){ 代码1; 代码2; V(S); 代码3; }
        • // 保证代码4在代码2之后执行 P2(){ P(S); 代码4; 代码5; 代码6; }
      • 注意
        • P操作出现在后操作之前 V操作出现在前操作之后
    • 3.利用信号量实现前趋关系
      • (1)分析问题，画出前趋图，把每个前趋关系都看做成一个同步问题
      • (2)每一对前趋关系都是一个进程同步问题
      • (3)在每个“前操作”之后执行V(S)
      • (4)在每个“后操作”之前执行P(S)
      • P1(){ ... S1; V(a); V(b); ... }
        • P2(){ ... P(a); S2; V(c); V(d); ... }
          • P3(){ ... P(b); S3; V(g); ... }
            • P4(){ ... P(c); S4; V(e); ... }
              • P5(){ ... P(d); S5; V(f); ... }
                • P6(){ ... P(e); P(f); P(g); S6; ... }
  • 2.4.5 管程(Monitors)机制
    • 1.管程的定义
      • 管程可以理解为对PV操作的封装
      • 一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能够同步进程和改变管程中的数据
      • 管程的组成部分
        • ①管程的名称
        • ②局部于管程的共享数据结构说明
        • ③对该数据结构进行操作的一组过程
        • ④对局部于管程的共享数据设置初始值的语句
        • 12. 管程是由哪几部分组成的？
      • 管程的主要特征
        • ①模块化，即管程是一个基本程序的单位
        • ②抽象数据类型，指管程中不仅有数据，而且有对数据的操作
        • ③信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见
      • 管程与进程的不同
        • ①虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构，如消息队列
        • ②二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关操作，而管程的设置则是解决共享资源的互斥使用问题
        • ③设置进程的目的是在于实现系统的并发性，而管程的设置主要是解决共享资源的互斥使用问题
        • ④进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序被调用一样，因而管程为被动工作方式，进程则为主动工作方式
        • ⑤进程之间能并发执行，而管程则不能与其调用者并发
        • ⑥进程具有动态性，而管程则是操作系统中的一个资源管理模块，供进程调用
    • 2.条件变量
      • 可在管程中设置条件变量及等待/唤醒操作以解决同步问题
• 2.5 经典进程同步问题
  • 2.5.1 生产者-消费者问题
    • 1.问题描述：系统中由一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品并使用（这里的产品理解为某种数据），生产者和消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区未满的时候，生产者才能把产品放入缓冲区，否则必须等待。
    • 2.解题思路
      • ①关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系
      • ②整理思路。根据各进程的操作流程确定P，V操作的大致顺序
      • ③设置信号量。设置需要的信号量，并根据题目条件设置信号量初值。(互斥信号量初值一般为1，同步信号量的多少看对应初始资源值的多少)
    • 3.解题过程
      • ①关系分析
        • 进程：存在生产者进程和消费者进程
        • 互斥关系：生产者生产产品和消费者消耗产品对缓冲区的访问要实现互斥
        • 同步关系
          • 缓冲区满，生产者进程要等待消费者进程取走产品
          • 缓冲区空，消费者进程要等待生产者进程放入产品
      • ②整理思路
        • 生产者每次要消耗(P操作)一个空闲缓冲区，并放入(V操作)一个产品(非空闲缓冲区)
        • 消费者每次要取走(P操作)一个产品(非空闲缓冲区)，并释放(V操作)一个空闲缓冲区
        • 往缓冲区放入/取走一个产品需要进行一次互斥操作(一对P，V操作)
      • ③设置信号量
        • semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问 semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量 semaphore full = 0; // 同步信号量，表示产品(非空闲缓冲区)的数量
      • ④代码实现
        • producer(){ while(1){ 生产一个产品; P(empty); // 消耗一个空闲缓冲区 P(mutex); // 实现进程互斥 把产品放入缓冲区; V(mutex); // 实现进程互斥 V(full); // 添加一个产品(非空闲缓冲区) } }
          • consumer(){ while(1){ P(full); // 消耗一个产品(非空闲缓冲区) P(mutex); // 实现进程互斥 从缓冲区取出产品; V(mutex); // 实现进程互斥 V(empty); // 增加一个空闲缓冲区 使用一个产品; } }
    • 4.注意
      • 若改变同步信号量P(empty)/P(full)与互斥信号量P(mutex)的顺序，则会发生死锁
      • 可以改变同步信号量V和互斥信号量V的顺序
  • 2.5.2 多生产者-多消费者问题
    • 1.问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专门向盘子中放苹果，妈妈专门向盘子中放橘子，儿子专门等着吃盘子中的橘子，女儿专门等着吃盘子里的苹果。只有盘子空时，爸爸或妈妈才能向盘子中放一个水果。仅当盘子里有自己需要的水果时，儿子或女儿才可以从盘子中取出水果
    • 2.解题过程
      • ①关系分析
        • 进程：父亲进程和母亲进程，儿子进程和女儿进程
        • 互斥关系：所有进程对盘子的的访问都需要实现互斥
        • 同步关系
          • 父亲将苹果放入盘子后，女儿才能取苹果
          • 母亲将橘子放入盘子后，儿子才能取橘子
          • 只有盘子为空时，父亲或母亲才能放入水果
      • ②整理思路
      • ③设置信号量
        • semaphore mutex = 1; // 互斥信号量，实现对盘子的互斥访问 semaphore plate = 1; // 同步信号量，表示盘子资源的数量 semaphore orange = 0;// 同步信号量，表示橘子资源的数量 semaphore apple = 0; // 同步信号量，表示苹果资源的数量
      • ④代码实现
        • dad(){ while(1){ 准备苹果; P(plate); P(mutex); 放入苹果; V(mutex); V(apple); } }
          • mom(){ while(1){ 准备橘子; P(plate); P(mutex); 放入橘子; V(mutex); V(orange); } }
            • daughter(){ while(1){ P(apple); P(mutex); 取出苹果; V(mutex); V(plate); 吃掉苹果; } }
              • son(){ while(1){ P(orange); P(mutex); 取走橘子; V(mutex); V(plate); 吃掉橘子; } }
    • 3.注意
      • 在多生产者-消费者问题时，如果缓冲区大小为1的话，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的问题。
      • 在考试中若来不及分析，可以加上互斥信号量，但是同步的P操作一定要在互斥的P操作之前，否则可能引起死锁
  • 2.5.3 吸烟者问题
    • 1.问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个用友烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下哪种材料的抽烟者会卷一根烟并抽掉它，并给供应者进程一个信号完成了，供应者就会放另外两种材料在桌上，这个过程一直重复
    • 2.解题过程
      • ①关系分析
        • 进程：供应者进程和三个抽烟者进程
        • 互斥关系：桌子上同一时间只能放两种材料的组合
        • 同步关系
          • 桌子上有组合一→第一个抽烟者取走东西
          • 桌子上有组合二→第二个抽烟者取走东西
          • 桌子上有组合三→第三个抽烟者取走东西
          • 发出完成信号→供应者降将下一个组合放在桌子上
      • ②整理思路
      • ③设置信号量
        • semaphore offer1 = 0; // 桌上的组合一的数量 semaphore offer2 = 0; // 桌上的组合二的数量 semaphore offer3 = 0; // 桌上的组合三的数量 semaphore finish = 0; // 抽烟是否完成 int i = 0; // 用于实现抽烟者的抽烟顺序
      • ④代码实现
        • provider(){ while(1){ if(i==0) { 将组合一放桌上; V(offer1); }else if(i==1) { V(offer2); }else if(i==2) { V(offer)3; } i = (i+1)%3; // 实现轮流 P(finish); } }
          • smoker1(){ while(1){ P(offer1); 拿走抽掉; V(finish); } }
            • smoker2(){ while(1){ P(offer2); 拿走抽掉; V(finish); } }
              • smoker3(){ while(1){ P(offer3); 拿走抽掉; V(finish); } }
    • 3.注意
      • 吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路
      • 如果要实现“轮流让多个吸烟者吸烟”必然需要一个整型变量i实现随机的过程
      • 若一个生产者生产多种产品(或者说会引发多种前趋事件)，那么各个V操作应该放在各自对应的事件发生之后
  • 2.5.4 读者-写者问题
    • 1.问题描述：在读者和写者两组并发进程，共享一个文件，当两个或两个以上的进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程同时访问共享数据时则可能导致数据不一致的错误。
    • 2.解题过程
      • ①关系分析
        • 进程：写进程和读进程
        • 互斥关系：写进程-写进程，写进程-读进程
      • ②整理思路：
        • 因为读进程必须与其他任何进程进行互斥访问，所以为了实现读进程与写进程的互斥访问，而不阻断读进程之间的非互斥访问，可以让第一个访问文件的读进程进行“加锁”，让最后一个访问完文件的读进程进行“解锁”，设置一个count变量来记录当前有几个读进程在访问文件
      • ③设置信号量
        • semaphore rw = 1; // 用于实现对文件的互斥访问。 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; // 用于保证对count变量的互斥访问
      • ④代码实现
        • writer(){ while(1){ P(rw); // 写之前加锁 写文件; V(rw); // 写之后解锁 } }
          • reader(){ while(1){ P(mutex); // coun互斥加锁 if(count==0) P(rw); // 第一个读进程进行加锁 count++; V(mutex); // count解锁 读文件... P(mutex); // count互斥锁 count--; if(count==0) V(rw); // 最后一个读进程负责解锁 V(mutex); // count互斥解锁 } }
    • 3.注意
      • 潜在的问题：只要有读进程还在写，写进程就会一直阻塞等待，可能“饿死”。因此这种算法中，读进程是优先的
      • 核心思想：设置计数器count用于记录正在访问共享文件的读进程数，如果实现“一气呵成”就得想到互斥信号量
    • 4.改进为“先来先服务”
      • ①设置信号量
        • semphore rw = 1; // 用于实现读文件的互斥访问 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; // 用于保证对count变量的互斥访问 semaphore w = 1; // 用于实现“先来先服务”
      • ②代码实现
        • writer(){ while(1){ P(w); P(rw); 写文件; V(rw); V(w); } }
          • reader(){ while(1){ P(w); P(mutex); if(count==0) P(rw); count++; V(mutex); V(w); 读文件... P(mutex); count--; if(count==0) V(rw); V(mutex); } }
  • 2.5.5 哲学家进餐问题
    • 1.问题描述：一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，哲学家饥饿时会试图拿起左、右两根筷子(依次)，如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。
    • 2.解题过程
      • ①关系分析
        • 进程：五个哲学家进餐
        • 互斥关系：左右哲学家对其中间筷子的访问是互斥关系
      • ②整理思路：这个问题中只有互斥关系，但每个哲学家需要两个临界资源才能开始吃饭。如何避免临界资源分配不当的死锁问题，是该问题的精髓
      • ③信号量设置
        • semaphore chopstick[5]={1,1,1,1,1} // 每根筷子均为一个互斥信号量
      • ④代码实现
        • 1)要求至多允许四个哲学家同时进餐。这样至少有一个哲学家是可以拿到左右筷子的 semaphore r = 4; 可进餐互斥资源
          • Pi(){ while(1){ P(r); // 可进餐互斥资源 P(chopstick[i]); // 拿左 P(chopstick[(i+1)%5]) // 拿右 吃饭.. V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]) // 放右 V(r); 思考.. } }
        • 2)要求奇数号的哲学家先拿左边的筷子，而偶数号的哲学家先拿右边的筷子。避免了存在哲学家拿到一根筷子却被阻塞
          • Pi(){ while(1){ if(i%2 == 0){ // 偶数先右再左 P(chopstick[(i+1)%5]) // 拿右 P(chopstick[i]); // 拿左 吃饭.. V(chopstick[(i+1)%5]) // 放右 V(chopstick[i]); // 放左 }else{ P(chopstick[i]); // 拿左 P(chopstick[(i+1)%5]) // 拿右 吃饭.. V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]) // 放右 } 思考.. } }
        • 3)仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子 semaphore mutex = 1; //互斥的取筷子
          • Pi(){ while(1){ // 奇数先左再右 P(mutex); // 取筷子互斥资源 P(chopstick[i]); // 拿左 P(chopstick[(i+1)%5]) // 拿右 V(mutex); 吃饭.. V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]) // 放右 思考.. } }
    • 3.注意
      • 哲学家进餐问题关键在于解决进程死锁问题
      • 一个进程需要同时持有多个临界资源时考虑哲学家问题
• 2.6 进程通信
  • 2.6.0 什么是进程通信
    • 进程中需要传送大量数据时，应该利用OS提供的高级通信工具，该工具的主要特点是
      • (1)使用方便。OS隐藏了实现进程通信的具体细节，向用户提供了一组用于实现高级通信的命令(原语)，用户可方便地直接利用它实现进程之间的通信
      • (2)高效地传送大量数据。用户可直接利用高级通信命令(原语)高效地传送大量的数据
    • 进程通信就是指进程之间的信息交换。进程是系统分配资源的单位(包括内存地址空间)，因此各个进程拥有的内存地址空间相互独立，一个进程不能直接访问另一个进程的地址空间
  • 2.6.1 进程通信的类型
    • 1.共享存储器系统(Shared-Memory System)
      • (1)基于共享数据结构的通信方式：只适用于传递相对少量的数据，通信效率低下，属于低级通信。如在生产者-消费者问题中的有界缓冲期
      • (2)基于共享存储区的通信方式：为了传输大量数据，在内存中划出了一块共享存储区域，诸进程可通过对该共享区的读或写交换信息，数据的形式和位置甚至访问控制都是由进程负责，而不是OS。这种通信方式属于高级通信
      • 两个进程对共享空间的访问需要互斥
    • 2.管道(pipe)通信系统
      • 所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件
      • 所谓“管道通信”，向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。它能有效地传送大量数据
      • 特点
        • 管道只能采用半双工通信，如果要实现双向同时通信，则需要设置两个管道
        • 管道机制必须提供的协调能力
          • ①互斥，即当一个进程正在对pipe执行读或写操作时，其他进程必须等待
          • ②同步，即当写(输入)进程把一定数量(如4KB)的数据将pipe写满，写进程的write()系统调用将被阻塞，直到读(输出)进程取走数据后再把它唤醒。当读进程读一空pipe时，读进程的read()系统调用将被阻塞，直至写进程将数据写入管道后才将之唤醒
          • ③确定对方是否存在，只有确定了对方已存在时才能进行通信
        • 数据一旦读出，就从管道中被抛弃，这意味着读进程最多只有一个
    • 3.消息传递系统(Message passing system)
      • 在该机制中，进程不必借助任何共享存储区和数据结构，而是以格式化的消息(message)为单位(消息头+消息体)，将通信的数据封装在消息中，并利用操作系统的一组通信命令(原语)，在进程间进行消息传递，完成进程间的数据交互
      • 基于消息传递系统的通信方式属于高级通信方式
        • (1)直接通信方式，是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程
        • (2)间接通信方式，是指发送和接收进程，都通过共享中间实体(称为邮箱)的方式进行消息的发送和接收，完成进程间的通信
    • 4.客户机-服务器系统(Client-Server system)
      • 1)套接字(Socket)
        • 套接字：是一个通信标识类型的数据结构，包含了通信目的地址、通信使用的端口号、通信网络的传输层协议、进程所在的网络地址，以及针对客户或服务器程序提供的不同系统调用(或API函数)等，是进程通信和网络通信的基本构件
        • 套接字是为客户/服务器模型而设计的，通常包括
          • (1)基于文件型：通信进程都运行在同一台机器的环境中，套接字是基于本地文件系统支持的，一个套接字关联到一个特殊的文件，通信双方通过对这个特殊文件的读写实现通信，类似管道
          • (2)基于网络型：常采用的是非对称方式通信，即发送者需要提供接收者命名
        • 套接字的优势在于
          • 不仅适用于一台计算机内部的进程通信，也适用于网络环境中不同计算机间的进程通信
          • 每个套接字具有唯一的套接字号(套接字标识符)，系统中所有的连接都持有唯一的一对套接字及端口连接，能够方便的区分来自不同程序进程或网络连接的通信
          • 由于确保了通信双方之间逻辑链路的唯一性，便于实现数据传输的并发服务，而且隐藏了通信设施及实现细节，采用统一的接口进行处理
      • 2)远程过程(函数/方法)调用
        • 远程过程(函数)调用RPC(Remote Procedure Call)，是一个通信协议，用于通过网络连接的系统。该协议允许一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程，而对程序员表现为常规的过程调用，无需额外编程。如果设计的软件采用面向对象编程，那么被称作远程方法调用
  • 2.6.2 消息传递通信的实现方式
    • 1.直接消息传递系统
      • 消息直接挂到接收进程的消息缓冲队列上
    • 2.间接消息传递系统(信箱通信)
      • 发送进程通过“发送原语”将消息发送到信箱中，接收进程通过“接收原语”获得对应的消息
    • 15. 消息传递通信的实现方式分别是哪两种？并加以举例。
• 2.7 线程(Threads)的基本概念
  • 2.7.1 线程的引入带来的变化
    • 资源分配、调度
      • 传统的进程机制中，进程是资源分配和调度的基本单位
      • 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
    • 并发性
      • 传统进程机制中，只能进程间并发
      • 引入线程后，各线程间也能并发，提升了并发度
    • 系统开销
      • 传统的进程间并发，需要切换进程的运行环境，系统开销很大
      • 线程间并发，如果是同一进程内的线程切换，则不需要切换线程环境，系统开销小
      • 引入线程后，并发带来的系统开销减小
    • 19.为什么要在OS中引入线程？
  • 线程的属性
    • (1)轻型实体
    • (2)独立调度和独立分派的基本单位
    • (3)可并发执行
    • (4)共享进程资源
    • 20.试说明线程具有哪些属性？
  • 2.7.2 线程与进程的比较
    • 1.调度的基本单位
      • 传统OS中，进程是作为独立调度和分派的基本单位，进程是能独立运行的基本单位
      • 引入线程的OS中，把线程作为调度和分派的基本单位，因而线程是能独立运行的基本单位
      • 同一进程的各线程共享进程拥有的资源
      • 同一进程内的线程切换不会导致进程切换
    • 2.并发性
      • 引入线程的OS中，不仅进程之间可以并发执行，而且在一个进程中的多个甚至所有线程亦可以并发执行。同样，不同进程中的线程也能并发运行
    • 3.拥有资源
      • 进程可以拥有资源，并作为系统中拥有资源的一个基本单位。
      • 线程并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源
      • 线程除了拥有自己的少量资源外，还允许多个线程共享该进程所拥有的资源
    • 4.独立性
      • 同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多
      • 进程都拥有一个独立的地址空间和其他资源，除了共享全局变量外，不允许其它进程的访问
      • 线程之间共享进程的内存地址空间和资源，每个线程都可以访问它们所属进程地址空间中的所有地址
    • 5.系统开销
      • 创建或撤销进程时，系统要为之分配和回收PCB和其他资源，并且进程切换时，涉及到上下文的切换
      • 线程撤销或创建的开销明显小于进程，而线程切换的代价也远远小于进程
    • 21.试从调度性、并发性、拥有资源及系统开销方面对进程和线程进行比较。
    • 6.支持多处理机系统
      • 在多处理机系统中，对于传统的进程(单线程进程)，不管有多少处理机，该进程只能运行在一个处理机上。但对于多线程进程，可以将多个线程分配到多个处理器上，使它们并行执行
  • 2.7.3 线程的状态和线程控制块
    • 1.线程运行的三个状态
      • (1)执行状态
        • 表示线程已经获得了处理机并正在运行
      • (2)就绪状态
        • 表示线程已经具备了执行条件，等待获得CPU就可以运行
      • (3)阻塞状态
        • 指线程在执行中因某事件受阻而处于暂停状态
      • 13. 线程运行的三个状态是什么？
    • 2.线程控制块TCB
      • ①线程标识符：线程的唯一标识符
      • ②一组寄存器：包括程序计数器PC，状态寄存器和通用寄存器的内容
      • ③线程运行状态：描述线程正处于什么状态
      • ④优先级：线程执行的优先程度
      • ⑤线程专有存储区：用于线程切换时存放现场保护信息和与该线程相关的统计信息
      • ⑥信号屏蔽：对某些信号加以屏蔽
      • ⑦堆栈指针：用于保存局部变量和返回地址
      • 22.线程控制块TCB中包含了哪些内容？
    • 3.多线程OS中的进程属性
      • (1)进程是一个可拥有资源的基本单元
      • (2)多个线程可并发执行
      • (3)进程已不是基本可执行实体：对进程施加的状态也对线程起作用，如某个进程挂起时，该进程中的所有线程都将被挂起
• 2.8 线程的实现
  • 2.8.1 线程的实现方式
    • 1.用户级线程ULT(User Level Threads)
      • (1)概念：仅存在于用户空间中的线程，无须内核支持。这种线程的创建、撤销、线程间的同步与通信等功能，都无需利用系统调用实现。用户级线程的切换通常发生在一个应用进程的诸多线程之间，同样无需内核支持。
        • 23.何谓用户级线程？
      • (2)特点
        • 用户级线程是通过线程库实现的
        • 所有线程管理工作都由应用程序负责(包括线程切换)
        • 用户级线程中，线程切换可以在用户态下完成，无需操作系统干预
        • 在用户看来，程序是有多个线程，但操作系统的内核下来看，并不能意识到线程的存在(用户级线程对用于不透明，对操作系统透明)
      • (3)优点
        • 线程切换不需要转换到内核空间
        • 调度算法可以使进程专用的
        • 用户级线程的实现与OS平台无关
      • (4)缺点
        • 系统调用的阻塞问题
        • 在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点，内核每次分配给一个进程的仅有一个CPU，因此，进程仅有一个线程能执行，不能实现并行
          • 26.多对一模型有何优缺点？
    • 2.内核支持线程KST(Kernal Supported Threads)
      • (1)概念：内核支持下运行的线程。无论是用户进程中的线程，还是系统线程中的线程，其创建、撤销和切换等都是依靠内核，在内核空间中实现的。在内核空间里还为每个内核支持线程设置了线程控制块，内核根据该控制块感知某线程的存在并实施控制。
        • 23.何谓内核支持线程？
      • (2)特点
        • 内核级线程是由操作系统内核完成
        • 线程调度、切换等工作都由内核负责
        • 内核级线程中，线程切换必然在核心态下完成
        • 可以理解的是，“内核级线程”就是“从操作系统内核视角看能看到的线程”
      • (3)优点
        • ①在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行
        • ②如果其中一个线程被阻塞了，内核可以调度其他线程占有处理机运行，也可以运行其他进程中的线程
        • ③内核支持线程具有很小的数据结构和堆栈，现成的切换比较快，切换开销小
        • ④内核本身可以采用多线程技术，可以提高系统的执行速度和效率
      • (4)缺点
        • 对于用户的线程切换而言，其模式切换的开销较大，同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态
    • 3.多线程模型
      • 1)多对一模型
        • 概念
          • 多个用户级线程映射到一个内核级线程。每个用户线程只对应一个内核线程
        • 优点、缺点见ULT
      • 2)一对一模型
        • 概念
          • 同于KST，一个用户级线程映射到一个用户级线程。每个用户线程都有同数量的内核线程
        • 优点、缺点见KST
      • 3)多对多模型
        • 在同时支持用户级线程和内核支持线程的系统中，可采用二者的组合方式：将n个用户级线程映射到m个内核级线程上(n>=m)
        • 操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位
        • 如左边这个模型：该进程有两个内核级进程，所以在用户看来三个线程也只能分配到两个内核，因此最多只有两个用户线程能够并行
      • 26.多线程模型有哪几种类型？
  • 2.8.2 线程的实现
    • 1.用户级线程的实现
      • 用户级线程是在用户空间中的实现的，运行在“运行时系统”与“内核控制线程”的中间系统上。运行时系统用于管理和控制线程的函数的集合。内核控制线程或轻型进程LWP可通过系统调用获得内核提供服务，利用LWP进程作为中间系统。
        • 24.试说明用户级线程的实现方法。
    • 2.内核支持线程的实现
      • 系统在创建新进程时，分配一个任务数据区PTDA，其中包括若干个线程控制块TCB空间。创建一个线程分配一个TCB，有关信息写入TCB，为之分配必要的资源。 当PTDA中的TCB用完，而进程又有新线程时，只要所创建的线程数目未超过系统允许值，系统可在为之分配新的TCB；在撤销一个线程时，也应回收线程的所有资源和TCB。
        • 25.试说明内核支持线程的实现方法。
  • 2.8.3 线程的创建和终止
    • 1.线程的创建
      • 应用程序启动时，会生成一个初始化线程用于创建新线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程的创建函数执行完后，将返回一个线程标识符供以后使用
        • 14.如何创建线程？
    • 2.线程的终止
      • 当一个线程完成了自己的任务后，或是线程在运行中出现异常情况而必须被强制终止时，由终止进程通过调用相应的函数(或系统调用)对它执行终止操作
• 进程控制习题
  • 1.若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D只从盘中取梨子。试用：信号量和P、V操作，写出同步算法。
    • 1.关系分析
      • 进程：进程A,B,C,D
      • 互斥关系：每个进程需要互斥访问盘子
      • 同步关系：A,B必须在盘子为空后才能放入一个水果，C必须在盘中有苹果后才能取水果，D必须在盘中有梨子后才能取水果
    • 2.设置信号量
      • semaphore plate = 1; // 盘子可装空间 semaphore apple = 0; // 盘内苹果个数 semaphore peer = 0; // 盘内梨子个数
    • 3.代码实现
      • A(){ while(1){ 准备一个苹果; P(plate); // 查看盘子是否有空余 放入苹果; V(apple); // 苹果个数加一 } }
        • B(){ while(1){ 准备一个梨子; P(plate); // 查看盘子是否有空余 放入梨子; V(peer); } }
          • C(){ while(1){ P(apple); // 查看盘子是否有苹果 取出苹果; V(plate); // 将盘子设为空闲 } }
            • D(){ while(1){ P(peer); // 查看盘子是否有梨子 取出梨子; V(plate); // 将盘子设为空闲 } }
• 信号量练习题
  • 1. 设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作，写出同步算法。
    • 关系分析
      • 进程：工人1,2,3,4
      • 同步关系：A满，要等工人4取走A；A空，要等工人1添加A；B满，要等工人4取走B；B空，要等工人2,3添加B
      • 互斥关系：对A和B的访问要互斥
    • 设置信号量
      • semaphore aEmpty = 8 semaphore bEmpty = 20 semaphore aFull = 0 semaphore bFull = 0 semaphore mutex = 1
    • 代码实现
      • worker1(){ while(1){ 加工一个车架; P(aEmpty); P(mutex); 放入货架A; V(mutex); V(aFull); } }
        • worker2(){ while(1){ 加工一个车轮; P(bEmpty); P(mutex); 放入货架B; V(mutex); V(bFull); } }
          • worker3(){ while(1){ 加工一个车轮; P(bEmpty); P(mutex); 放入货架B; V(mutex); V(bFull); } }
            • worker4(){ while(1){ P(aFull); P(bFull); P(bFull); P(mutex); 取出一个车架和两个车轮; V(mutex); V(bEmpty); V(bEmpty); V(aEmpty); 组装成自行车; } }
  • 2. 假定有一个成品仓库，总共能存放8台成品，生产者进程把生产成品放入仓库，消费者进程从仓库中取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存入和取出只能分别进行，试用P、V操作来实现该方案，写出同步算法。
    • 关系分析
      • 进程：生产者进程，仓库搬运进程
      • 同步关系：仓库满，要等仓库搬运走成品；仓库空，要等生产者进程存入仓库
      • 互斥关系：对A和B的访问要互斥
    • 设置信号量
      • semaphore empty = 8 semaphore full = 0 semaphore mutex = 1
    • 代码实现
      • producer(){ while(1){ 生产一个成品; P(empty); P(mutex); 放入成品仓库; V(mutex); V(full); } }
        • remover(){ while(1){ P(full); P(mutex); 取出成品; V(mutex); P(empty); 搬运成品; } }
  • 3. 进程P1使用缓冲区buffer向进程P2，P3，P4发送消息，要求每当Pl向buffer中发消息时，只有当P2，P3，P4进程都读取这条消息后P1才可向buffer中发送新的消息。试用信号量机制描述各进程的动作过程，写出同步算法。
    • 关系分析
      • 进程：进程P1，进程P2,P3,P4
      • 同步关系：缓冲区存在消息时，需要等P2P3P4读取消息；缓冲区不存在消息时，需要等P1发送入消息
      • 互斥关系：对缓冲区的访问需要互斥
    • 设置信号量
      • semaphore s1 = 3 semaphore s2, s3, s4 = 0
    • 代码实现
      • P1(){ while(1){ 生成一条消息; P(s1); P(s1); P(s1); 放入一条消息; V(s2); V(s3); V(s4); } }
        • Pi(){ // i=2, 3, 4 while(1){ P(si); // i=2, 3, 4 取出消息; V(s1); 处理消息; } }
  • 4. 有P1、P2、P3三个进程共享一个表格F，P1对F只读不写，P2对F只写不读，P3对F先读后写。进程可同时读F，但有进程写时，其他进程不能读和写。请用信号量和P、V操作，编写三个进程能正确工作的算法程序。
    • 关系分析
      • 进程：P1,P2, P3
      • 互斥关系：写进程和读进程互斥
    • 设置信号量
      • semaphore mutex = 1 // 写进程的互斥 int rCount = 0; // 记录读进程的数量 int rMutex = 1; // 对rCount的互斥访问
    • 代码实现
      • P1(){ while(1){ P(mutex); 读表格F; V(mutex); } }
        • P2(){ while(1){ P(rMutex); if (rCount == 0) P(mutex); rCount++; V(rMutex); 写入表格F； P(rMutex); if (rCount > 0) V(mutex); rCount--; V(rMutex); } }
          • P3(){ while(1){ P(rMutex); if (rCount == 0) P(mutex); rCount++; V(rMutex); 写入表格F； P(rMutex); if (rCount > 0) V(mutex); rCount--; V(rMutex); P(mutex); 读表格F; V(mutex); } }
  • 5. 假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。
    • 关系分析
      • 进程：读者进程
      • 互斥关系：50个座位的访问需要互斥；登记和注销需要互斥
    • 设置信号量
      • semaphore mutex = 1; // 登记和注销每次一个人 semaphore seat = 50; // 资源信号量50个座位
    • 代码实现
      • reader(i){ while(1){ 读者来到阅览室; P(mutex); // 查看是否有人登记或注销 在登记表上登记; V(mutex); P(seat); // 互斥访问座位 阅览资料; V(seat); P(mutex); // 查看是否有人登记或注销 在登记表上注销; V(mutex); } }
  • 6. 在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次拣一子；当进程在拣时，不允许另一个进程取拣；当一个进程拣了一子时，必须让另一进程去捡。假设从拣白子开始。试用信号量和P、V操作，写出能正确并发执行的算法程序。
    • 关系分析
      • 进程：P1和P2
      • 互斥关系：拣子必须互斥进行
      • 同步关系：P2拣黑子在P1拣完白子之后，P1拣白子在P2拣黑子之后
    • 设置信号量
      • semaphore mutex = 1; // 互斥拣子 semaphore S1 = 1; // 同步信号量，用于同步P2的拣子，先拣白子初始化为1 semaphore S2 = 0; // 同步信号量，用于同步P1的拣子
    • 代码实现
      • P1(){ while(1){ P(S1); P(mutex); 拣白子; V(mutex); V(S2); // 通知P2可以拣子 } }
        • P2(){ while(1){ P(S2); P(mutex); 拣黑子; V(mutex); V(S1); // 通知P1可以拣子 } }
  • 7. 今有一个文件F供进程共享，现把这些进程分成A、B两组，规定同组的进程可以同时读文件F；但当有A组（或B组）的进程在读文件F时就不允许B组（或A组）的进程读文件F。试用P、V操作来进行管理，写出同步算法。
    • 关系分析
      • 进程：A和B
      • 互斥关系：A类进程和B类进程读文件F必须互斥进行
    • 设置信号量
      • semaphore mutex = 1; // A,B互斥读文件F的互斥信号量 semaphore S1= 0, S2 = 0; // 对A操作和B操作的互斥信号量 int c1 = 0, c2 = 0; // 记录A,B正在读F的进程个数
    • 代码实现
      • PA(i){ while(1){ P(S1); C1 = C1+1; if(C1 == 1) P(mutex); V(S1); 读文件F; P(S1); C1 = C1-1; if(C1 == 0) V(mutex); V(S1); } }
        • PB(i){ while(1){ P(S2); C2 = C2+1; if(C2 == 1) P(mutex); V(S2); 读文件F; P(S2); C2 = C2-1; if(C2 == 0) V(mutex); V(S2); } }
  • 8. 有三个进程，Reader进程读入数据number1，将其放入缓冲器B1，Executor进程将B1中数据取出，处理成数据number2，将其放入缓冲器B2，Printer进程将number2数据取出打印，假设B1 和B2只能存放一个数据，用P、V操作管理这三个进程的执行，写出同步算法。
    • 关系分析
      • 进程：Reader进程，Executor进程，Printer进程
      • 互斥关系：互斥访问缓冲区B1和B2
      • 同步关系：在B1为空后才能放入number1，在B1满时才能取出number1，在B2为空后才能放入number2，在B2为满时才能取出number2
    • 设置信号量
      • semaphore empty1=1, empty2=1; semaphore full1=0, full2 = 0;
    • 代码实现
      • Reader(){ while(1){ Reader进程读取数据 P(empty1); // 查看缓冲区B1是否空闲 放入number1进B1; V(full1); // 缓冲区B1空间加一 } }
        • Executor(){ while(1){ P(full1); // 查看缓冲区B1是否有数据 取出数据并处理成number2; V(empty1); // 缓冲区B1空间减一 P(empty2); // 查看缓冲区P2是否空闲 放入number2进B2; V(full2); // 缓冲区B2空间加一 } }
          • Printer(){ while(1){ P(full2); // 查看缓冲区B2是否有数据 Printer进程取出数据; V(empty2); 打印数据; } }

第三章 处理机调度与死锁

• 3.1 处理机调度的层次和调度算法的目标
  • 3.1.1 处理机调度的层次
    • 1.高级调度(High Level Scheduling)
      • 又称长程调度或作业调度
      • 调度对象是作业
      • 功能是根据某种算法，决定外存上处于后备队列的几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入就绪队列。
        • 1.高级调度的主要任务是什么？
      • 主要用于多道批处理系统
    • 2.低级调度(Low Level Scheduling)
      • 又称短程调度或进程调度
      • 调度对象是进程
      • 功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给选中的进程
        • 1.低级调度的主要任务是什么？
      • 进程调度作为最基本的调度，在多道批处理系统、分时和实时三种系统中
    • 3.中级调度(Intermediate Scheduling)
      • 又称内存调度
      • 中级调度实际上就是存储器管理中的对换功能
      • 功能是把暂时不能运行的进程调至外存等待，此时的进程状态称为挂起状态。当挂起进程具备了运行条件且内存稍有空闲时，重新将其调入内存，使其变为就绪状态。
      • 提高内存利用率和系统吞吐量
        • 1.引入中级调度的目的是什么？
  • 3.1.2 处理机调度算法的目标
    • 1.处理机调度算法的共同目标
      • (1)提高资源利用率
      • (2)公平性
      • (3)平衡性
      • (4)策略强制执行
    • 2.批处理系统的目标
      • (1)平均周转时间短
        • 平均周转时间
          • n为作业总数
          • Ti为第i个作业的周转时间(结束时刻-开始时刻)
        • 平均带权周转时间
          • Ti为第i个作业的周转时间(结束时刻-开始时刻)
          • Ts为第i个作业的运行时间
      • (2)系统吞吐量高
      • (3)处理机利用率高
    • 3.分时系统的目标
      • (1)响应时间快
      • (2)均衡性
    • 4.实时系统的目标
      • (1)截止时间的保证
      • (2)可预测性
• 3.2 作业与作业调度
  • 3.2.1 批处理系统中的作业
    • 1.作业和作业步
      • (1)作业：作业不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制，在批处理系统中是以作业为基本单位从外存调入内存
        • 2.什么是作业？
      • (2)作业步：作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工步骤才能得到结果，其中每一个加工步骤称为一个作业步
        • 2.什么是作业步？
    • 2.作业控制块(Job Control Block, JCB)
      • 作业标识
      • 用户名称
      • 用户账号
      • 作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型)
      • 作业状态
      • 调度信息(优先级、作业运行时间)
      • 资源需求(预计运行时间、要求内存大小等)
      • 资源使用情况等
    • 3.作业运行的三个阶段和三种状态
      • (1)收容阶段：后备状态
      • (2)运行阶段：运行状态
      • (3)完成阶段：完成状态
  • 3.2.2 作业调度的主要任务
    • 1.接纳多少个作业：作业调度每次接纳进入内存的作业数，取决于多道程序度。
    • 2.接纳哪些作业：应将哪些作业从外存调入内存，取决于采用的调度算法。最简单的是先来先服务调度算法，较常用的是短作业优先调度算法和基于作业优先级的调度算法。
    • 3.在作业调度中如何确定接纳多少个作业和接纳哪些作业？
  • 3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法
    • 1.先来先服务(first-come first served, FCFS)调度算法
      • 当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。
    • 2.短作业优先(short job first, SJF)调度算法
      • SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。
      • 缺点
        • ①必须预知作业的运行时间
        • ②对长作业非常不利，长作业的周转时间会明显增长
        • ③采用SJF算法时，人—机无法实现交互
        • ④该调度算法完全未考虑作业的紧迫程度，不能保证紧迫性作业得到及时处理
        • 4.短作业优先算法的缺点是什么？
      • 例题
        • 
  • 3.2.4 优先级调度算法和高响应比优先调度算法
    • 1.优先级调度算法(priority-scheduling algorithm, PSA)
    • 2.高响应比优先调度算法(Highest Response Ratio Next, HRRN)
      • 响应比
      • 特点
        • ①如果作业的等待时间相同，则要求服务的时间愈短，其优先级越高，此时类似于SJF算法
        • ②对于要求服务的时间相同时，作业的优先度取决于其等待时间，此时类似于FCFS算法
        • ③对于长作业的优先级，可以随等待时间的增加而提高，等待时间足够长时也会获得处理机。
        • 综上该算法实现了较好的折中。但是每次进行调度之前都需要先做响应比的计算，显然增加了系统的开销
      • 例题
        • 
• 3.3 进程调度
  • 3.3.1 进程调度的任务、机制和方式
    • 1.进程调度的任务
      • (1)保存处理机的现场信息
      • (2)按某种算法选取进程
      • (3)把处理器分给进程
      • 5.试说明进程调度的任务。
    • 2.进程调度机制
      • 为了实现进程调度，在进程调度进制中，应具有如下三个基本部分
      • (1)排队器。为了提高进程的调度效率，应事先将操作系统中所有就绪进程按照一定策略排成一个或多个队列，以便调度程序能最快找到它。以后每当有一个进程转变为就绪状态时，排队器便将他插入到相应的就绪队列
      • (2)分派器。分派器根据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程
    • 3.进程调度的方式
      • 1)非抢占方式(Nonpreemptive Mode)
        • 引起进程调度的因素
          • ①正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行
          • ②正在执行中的进程因提出I/O请求而暂停执行
          • ③在进程通信或同步过程中，执行了某种原语操作，如block原语
        • 优点
          • 实现简单
          • 系统开销小
          • 适用于大多批处理系统。但是不能用于分时系统和大多数实时系统
      • 2)抢占方式(Preemptive Mode)
        • 主要遵循的原则
          • ①优先权的原则。指允许优先级高的进程抢占当前进程的处理机
          • ②短进程优先原则。指允许新到的短进程可以抢占当前长进程的处理机
          • ③时间片原则。即各个进程按时间片轮转进行，当正在执行的进程一个时间片用完后，便停止该进程的执行并重新调度
          • 6.进程调度方式中的抢占方式遵循的主要原则有哪些？
  • 3.3.2 轮转调度算法
    • 1.轮转法的基本原理
      • 在轮转法(round robin, RR)中，系统根据FCFS策略，将所有的就绪进程排成一个就绪队列，并可设置每隔一定时间间隔(如30ms)的中断，激活系统中的进程调度程序，完成一次调度，将CPU分给队首进程，令其执行。当该进程的时间片耗尽或运行完毕时，系统再次将CPU分给新的队首进程。由此，可保证就绪队列中的所有进程在一个确定的时间段内，都能获得一次CPU执行
    • 2.进程切换时机
      • ①若一个时间片未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中的队首进程运行，并启动一个新的时间片
      • ②在一个时间片用完时，计时器中断处理程序被激活。若该进程未结束，调度程序将该程序送往就绪队列的末尾
    • 3.时间片大小的确定
      • 时间片确定策略：一个较为可取的时间片大小略大于一次典型交互所需的时间，使大多数交互式进程能在一个时间片内完成。
    • 例题
      • 
      • 时间片q=1时
      • 时间片q=4时
        • 
  • 3.3.3 优先级调度算法
    • 1.优先级调度算法的类型
      • (1)非抢占式优先级调度算法：一旦处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发送某事件而放弃处理机时，系统方可将处理器重新分配给另一个优先级最高的进程
      • (2)抢占式优先级调度算法
        • 把处理机分配给优先级最高的进程，使之执行，即使在进程的执行过程中发现了另一进程的优先级更高，应停止当前的执行，进行进程切换。抢占式优先级调度算法常用于对实时性要求较高的系统中
    • 2.优先级的类型
      • 1)静态优先级
        • 静态优先级在进程的创建时就确定了并在进程的整个运行期间保持不变，优先级的大小是利用某一范围内的一个整数来表示的，例如0~255中的某一整数，又把该整数称为优先数
        • 确定优先数的依据
          • (1)进程类型。通常系统进程(如接收进程、对换进程)的优先级高于一般用户进程的优先级
          • (2)进程对资源的需求。对资源要求较少的进程应该赋予较高的优先级
          • (3)用户要求。根据进程的紧迫程度及用户所付费用的多少确定优先级
        • 静态优先级法简单易行，系统开销小，但不够精确，可能出现优先级低的进程长期没有被调度的情况
      • 2)动态优先级
        • 动态优先级是指在创建进程之处，先赋予其一个优先级，然后其值随进程额推进或等待时间的增加而改变，以获得更好的调度性能
  • 3.3.4 多队列调度算法
    • 前所述的各种调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求。
    • 将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列可以采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
  • 3.3.5 多级反馈队列(multileved feedback queue)调度算法
    • 1.调度机制
      • (1)设置多个就绪队列
      • (2)每个队列都采用FCFS算法：每个队列中的各个进程按FCFS进行调度
      • (3)按队列优先级调度：队列之间的调度按照优先级高低顺序进行调度
    • 2.调度算法性能
      • 如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要
      • (1)对于终端型用户：由于终端型用户提交的多为交互型作业，通常较小，系统只要能使这写作业在第一队列规定的时间片内完成，便能使终端型用户感到满意
      • (2)对短批处理作业用户：对于这类作业，如果可在第一队列中执行完成，便获得与终端型作业一样的响应时间。对于较长的作业，也只需在第二和第三队列各执行一时间片完成，其周转时间仍然较短
      • (3)对长批处理作业用户：对于长作业，它将依次在1,2,...,n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理
  • 3.3.6 基于公平原则的调度算法
    • 1.保证调度算法
      • 保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。
    • 2.公平分享调度算法
      • 针对用户而言，使所有用户能获得相同的处理机时间，或要求的时间比例。
• 3.4 实时调度
  • 3.4.1 实现实时调度的基本条件
    • (1)提供必要的信息，如就绪时间，开始截止时间和完成截止时间，处理时间，资源要求，优先级。
    • (2)系统处理能力强
    • (3)采用抢占式调度机制
    • (4)具有快速切换机制
    • 7.实现实时调度的基本条件有哪些？
  • 3.4.2 实时调度算法的分类
    • 实时任务性质
      • 硬实时调度算法
      • 软实时调度算法
    • 调度方式
      • 1.非抢占式调度算法
        • (1)非抢占式轮转调度算法
        • (2)非抢占式优先调度算法
      • 2.抢占式调度算法
        • (1)基于时钟中断的抢占式优先级调度算法
        • (2)立即抢占(Immediate Preemption)的优先级调度算法
  • 3.4.3 最早截止时间优先EDF(Earliest Deadline First)算法
    • 1.非抢占式调度方式用于非周期实时任务
    • 2.抢占式调度方式用于周期性实时任务
  • 3.4.4 最低松弛度优先LLF(Least Laxity First)算法
  • 3.4.5 优先级倒置(priority inversion problem)
    • 1.优先级倒置的形成
    • 2.优先级倒置的解决方法
• 3.5 死锁概述
  • 3.5.1 资源问题
    • 1.可重用性资源和消耗性资源
      • 1)可重用性资源
        • (1)每一个可重用性资源是中的单元只能分配给一个进程使用，不允许多个进程共享
        • (2)进程在使用可重用性资源时，须按照下序
          • ①请求资源。如果请求资源失败，进程将会被阻塞或循环等待
          • ②使用资源
          • ③释放资源
          • 8.进程在使用可重用性资源时，需要遵循何种顺序进行？
      • 2)可消耗性资源
        • ①每一类可消耗性资源的单元数目在进程有运行期间是可以不断变化的，有时它可以有许多，有时可能为0
        • ②进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区，以增加该资源类的单位数目
        • ③进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中
    • 2.可抢占型资源和不可抢占性资源
      • 1)可抢占性资源
        • 指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。CPU和主存均属于可抢占性资源。对于这类资源是不会引起死锁的
      • 2)不可抢占性资源
        • 指系统一旦把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。磁带机、打印机都属于不可抢占性资源
  • 3.5.2 计算机系统中的死锁
    • 1.竞争不可抢占性资源引起死锁
      • 通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。
    • 2.竞争可消耗性资源引起死锁
    • 3.进程推进顺序不当引起死锁
      • 除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。
  • 3.5.3 死锁的定义、必要条件和处理方法
    • 1.死锁的定义
      • 如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件,那么该组进程是死锁的(Deadlock)
    • 2.产生死锁的必要条件
      • (1)互斥条件。进程对所分配到的资源进行排它性使用
      • (2)请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被占有，此时该进程被阻塞，但对自己的资源保持不释放
      • (3)不可抢占条件。进程已获得的资源在未使用完前不能被抢占，只能在进程使用完时由自己释放
      • (4)循环等待条件。发生死锁必然存在一个进程—资源的循环链，即P0等P1所占资源，P1等P2所占资源...
      • 9.产生死锁的必要条件是什么？
    • 3.处理死锁的方法
      • (1)预防死锁：通过破坏产生死锁的必要条件。预防死锁是最容易实现的方法
      • (2)避免死锁：在资源的动态分配过程中运用某种方法防止系统进入“不安全状态”。避免死锁是资源使用率最高的方法
      • (3)检测死锁：无须事先采取任何限制性措施，在运行过程中发生死锁时通过即使检测出死锁的发生然后采取适当的措施，把进程从死锁中解脱出来。
      • (4)解除死锁：当检测到系统中已经发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用方法是撤销一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行
      • 10.处理死锁问题有哪几个几个方法中，其中哪种方法最易于实现？哪种方法使资源利用率最高？
• 3.6 预防死锁
  • 3.6.1 破坏“请求和保持”条件
    • 当一个进程在请求资源时，它不能持有不可抢占资源
    • 1.第一种协议
      • 协议规定，在所有进程开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。从而破坏了“请求”条件。只要有一种资源不满足进程的要求，即使其他所需的各资源都空闲也不分配给该进程，而让进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件
      • 优点：简单易行且安全
      • 缺点
        • 资源被严重浪费，严重地恶化了资源的利用率
        • 使进程经常会发生饥饿现象
    • 2.第二种协议
      • 协议允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中可以逐步释放已分配给自己的、且已用毕的资源，然后再请求新的资源
      • 优点：提高了设备的利用率，还可以减少进程发生饥饿的几率
  • 3.6.2 破坏“不可抢占”条件
    • 协议规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请
    • 缺点
      • 实现起来比较复杂，且需付出很大的代价
      • 延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量
  • 3.6.3 破坏“循环等待”条件
    • 该协议规定每个进程必须按序号递增的顺序请求资源。
    • 优点：资源利用率和系统吞吐量都较前二者有所改善
    • 缺点
      • 首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加
      • 其次，尽管在为资源的类型分配序号事，已经考虑到了大多数作业在实际使用这些资源时的顺序，但也经常会发生作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费
      • 第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而按照这种规定次序申请资源的方法必然会限制用户简单、自主的编程
  • 11.如何预防死锁?
• 3.7 避免死锁
  • 3.7.1 系统安全状态
    • 1.安全状态：所谓安全状态，是指系统能按照某种进程推进顺序为每个进程分配其所需资源，直至每个进程对资源的最大需求，使每个进程都可顺利地完成。此时这个顺序称作安全序列
    • 2.安全状态之例
    • 3.由安全状态向不安全状态的状态
  • 3.7.2 利用银行家算法避免死锁
• 3.8 死锁的检测与解除
  • 3.8.1 死锁的检测
    • 对死锁进行检测，在系统中必须
      • ①保存有关资源的请求和分配信息
      • ②提供一种算法，它利用这些信息来检测系统是否已进入死锁状态
      • 13.检测系统是否发生死锁的前提是什么？
  • 3.8.2 死锁的解除
    • (1)抢占资源。从其他进程中抢占足够数量的资源分配给死锁进程以解除死锁状态
    • (2)终止(或撤销)进程。终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
    • 12.试说明常采用解除死锁的方法。
• 处理机调度习题
  • 1. 有5个批处理作业（A，B，C，D，E）几乎同时到达一个计算中心，估计的运行时间分别为10，6，2，4，8分钟，他们的优先数分别为1，2，3，4，5（1为最低优先数）。对下面的各种调度算法，分别计算作业的开始时间、完成时间、周转时间和平均周期时间。
    • (1)最高优先级优先
      • 平均周转时间=(30+20+14+12+8)/5 = 16.8ms
    • (2)短作业优先
      • 平均周转时间=(30+12+2+6+20)/5=14ms
  • 2. 有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销不考虑）。
    • (1)先来先服务算法
      • 平均周转时间=(10+16+18+22+30)/5 = 19.2min
    • (2)优先级调度算法
      • 平均周转时间=(24+6+26+30+14)/5 = 20min
    • (3)时间片轮转算法(设时间片为1min)
      • 采用时间片轮转算法，5个进程均分CPU时间，每轮的执行情况如下： 第一轮：A,B,C,D,E运行，5min 第二轮：A,B,D,E运行，C第8min完成，5min 第三轮：A,B,D,E运行，4min 第四轮：A,B,E运行，D第17min完成，4min 第五轮：A,B,E运行，3min 第六轮：A,E运行，B第23min完成，3min 第七轮：A,E运行，2min 第八轮：A运行，E第28min完成，2min 第九轮：A运行，1min 第十轮：A第30min完成，1min 平均周转时间=(8+17+23+28+30)/5 = 21.2min
  • 3. 某系统中有3类资源M1, M2, M3，有四个进程P1,P2,P3，P4。其中M1,M2,M3的总数分别是10，8，3。四个进程对资源的需求和资源的已分配情况分别如下图。试问， 按银行家算法能否安全分配?并说明分配过程。
    • ①步骤1：给出当前情况下资源需求即分配的情况分析： 总的可用资源数R=(10,8,3) 当前可用资源数V=(3,1,1) 当前已分配资源A=((3,3,1), (2,3,0), (0,1,1), (2,0,0)) 当前所需资源情况C=((5,2,1), (4,3,3), (5,1,1), (0,1,1))
    • ②步骤2：对资源进行虚拟分配情况： 1.用V和C的每一行进行对比，发现V≥C4；资源满足P4需要，分配给P4后，回收资源A4，此时V=V+A4=(5,1,1)；P4对应的数据则不再使用 2.用V和C的每一行进行对比，发现V≥C3；资源满足P3需要，分配给P3后，回收资源A3，此时V=V+A3=(5,2,2)；P3对应的数据则不再使用 3.用V和C的每一行进行对比，发现V≥C1；资源满足P1需要，分配给P1后，回收资源A1，此时V=V+A1=(8,5,3)；P1对应的数据则不再使用 4.用V和C的每一行进行对比，发现V≥C2；资源满足P2需要，分配给P2后，回收资源A2，此时V=V+A1=(10,8,3)；P2对应的数据则不再使用
    • ③步骤3：下结论： 资源已全部收回，系统无死锁发生，银行家算法能够安全地分配
  • 4.某系统有A、B、C、D这4类资源供5个进程共享，进程对资源的需求和分配情况如下表所示。A、B、C、D类资源分别还剩1、5、2、0个，请按银行家算法回答下列问题：
    • (1)现在系统是否处于安全状态? 为什么？
      • ①当前系统资源分配情况如下： 当前可用资源数V = (1,5,2,0) 当前已分配资源A = ((0,0,1,2), (1,0,0,0), (1,3,5,4), (0,6,3,2), (0,0,1,4)) 当前所需资源情况C=((0,0,0,0), (0,7,5,0), (1,0,0,2), (0,0,2,0), (0,6,4,2))
        • 由已知条件可得Need矩阵如下： 进程 分配矩阵 尚需矩阵(Need) 可用资源数向量(Avaiable) P1 0 0 1 2 0 0 0 0 1 5 2 0 P2 1 0 0 0 0 7 5 0 P3 1 3 5 4 1 0 0 2 P4 0 6 3 2 0 0 2 0 P5 0 0 1 4 0 6 4 2
      • ②对资源进行虚拟内存分配 1.用V和C的每一项进行对比，发现V≥C1；资源满足P1需要，分配给P1后，回收资源A1，此时V=V+A1=(1,5,3,2)；P1对应的数据则不再使用 2.用V和C的每一项进行对比，发现V≥C3；资源满足P3需要，分配给P3后，回收资源A3，此时V=V+A3=(2,8,8,6)；P3对应的数据则不再使用 3.用V和C的每一项进行对比，发现V≥C2；资源满足P2需要，分配给P2后，回收资源A2，此时V=V+A2=(3,8,8,6)；P2对应的数据则不再使用 4.用V和C的每一项进行对比，发现V≥C4；资源满足P4需要，分配给P4后，回收资源A4，此时V=V+A4=(3,8,10,6)；P4对应的数据则不再使用 5.用V和C的每一项进行对比，发现V≥C5；资源满足P4需要，分配给P5后，回收资源A5，此时V=V+A4=(3,8,11,10)；P5对应的数据则不再使用
      • ③全部资源已收回，系统无死锁发生，系统是处于安全状态
    • (2)如果现在进程P2提出需要(0，4，2，0)个资源的请求，系统能否满足它的请求？为什么？
      • 进程 分配矩阵 尚需矩阵(Need) 可用资源数向量(Avaiable) P1 0 0 1 2 0 0 0 0 1 1 0 0 P2 1 4 2 0 0 3 3 0 P3 1 3 5 4 1 0 0 2 P4 0 6 3 2 0 0 2 0 P5 0 0 1 4 0 6 4 2
      • 因此存在安全序列P1, P3, P2, P4, P5，即系统仍然是否安全的，因此系统能满足P2的请求。

第四章 存储器管理

• 4.1 存储器的层次结构
  • 4.1.1 多层结构的存储系统
    • 1.存储器的多层结构
      • (1)对于通用计算机而言，存储器层次至少应具三级：最高层为CPU寄存器，中间为主存，最底层是辅存
      • (2)在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层
        • 其中层次越高(越靠近CPU)，存储介质的访问速度越快，价格也越高，相对所配置的存储容量也越小
        • 其中寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉线后他们将不复存在。而底层的固定硬盘和可移动存储介质则属于设备管理的管辖范畴，它们存储的信息将被长期保存
      • 2.试说明存储器的多层结构
    • 2.可执行存储器
      • (1)寄存器和主存储器又被称为可执行存储器，与辅存中的信息比较而言，采取的访问机制是不同的
  • 4.1.2 主存储器与寄存器
    • 1.主存储器
      • (1)概念
        • 主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。
    • 2.寄存器
      • (1)概念
        • 寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。寄存器具有与处理机相同的速度，故对CPU的访问速度最快，完全能与CPU协调工作，但价格昂贵，因此容量不可能做得很大。
    • 1.试说明主存储器和寄存器
  • 4.1.3 高速缓存和磁盘缓存
    • 1.高速缓存
      • (1)概念
        • 介于寄存器和存储器之间的存储器
      • (2)作用
        • 主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可以大幅度地提高程序的执行速度
    • 2.磁盘缓存
      • (1)概念
        • 本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入的信息)
      • (2)作用
        • 由于磁盘的I/O速度远低于对主存的访问速度，为了缓和二者在速度上的不匹配，而设置了磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息
• 4.2 程序的装入和链接
  • 4.2.0 程序装入的过程
    • (1)编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module)。由高级语言翻译为机器语言
    • (2)链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)，链接后形成完整的逻辑地址
    • (3)装入，由装入程序(Loader)将装入模块装入内存，完成由逻辑地址向物理地址的转换
  • 4.2.1 程序的装入
    • 1.绝对装入方式(Absolute Loading Mode)
      • 编译时产生绝对地址
      • 单道程序阶段，此时还没有产生操作系统
    • 2.可重定位装入方式(Relocation Loading Mode)
      • 又名静态重定位
      • 装入时将逻辑地址转换为物理地址
      • 用于早期的多道批处理操作系统
    • 3.动态运行时的装入方式(Dynamic Run-time Loading)
      • 又名动态重定位
      • 设置重定位寄存器，在运行时把逻辑地址转换为物理地址
      • 现代操作系统
  • 4.2.2 程序的链接
    • 1.静态链接(Static Linking)方式
      • 装入前链接成一个完整模块
    • 2.装入时动态链接(Load-time Dynamic Linking)
      • 运行前一边装入一边链接
    • 3.运行时动态链接(Run-time Dynamic Linking)
      • 运行时需要模块才装入并链接
• 4.3 连续分配存储管理方式
  • 4.3.1 单一连续分配
    • 只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
    • 无外部碎片，有内部碎片
      • 内部碎片：分配给某进程的内存区域中，如果有某些部分没有用上
      • 外部碎片：是指内存中的某些空闲分区由于太小而难以利用
  • 4.3.2 固定分区分配
    • 支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一个作业
    • 无外部碎片，有内部碎片
    • 两种分区方式
      • 分区大小相等
        • 缺乏灵活性，但适用于一台计算机控制多个相同对象的场合
      • 分区大小不相等
        • 增加了灵活性，可以满足不同大小的进程需求
  • 4.3.3 动态分区分配---又称可变分区分配
    • 1.动态分区分配中的数据结构
      • 空闲分区表：每个空闲分区对应一个表项。表项中包含空闲分区号、分区大小、分区起始地址等信息
      • 空闲分区链：每个分区的起始部分和末尾部分分别设置向前指针和向后指针。起始部分处还可记录分区大小等信息
    • 2.动态分区分配算法
    • 3.分区分配操作
      • 相邻的空闲分区要合并
        • 回收区之后有相邻的空闲分区：将后临空闲区的始址修改为回收区始址，大小为二者之和
        • 回收区之前有相邻的空闲分区：两区合并，将前临空闲区的大小修改为两者之和
        • 回收区前后都有相邻的空闲分区：三区合并，将前临空闲区大小修改为三者之和
        • 回收区前后都无相邻的空闲分区：为回收区设置空闲区表项，设置始址和该回收区大小
        • 3.采用首次适应算法回收内存时，会出现哪几种情况？应该如何处理？
    • 4.动态分区分配没有内部碎片，但是有外部碎片
      • 外部碎片可用“紧凑”技术来解决
  • 4.3.4 基于顺序搜索的动态分区分配算法
    • 1.首次适应(first fit, FF)算法
      • (1)算法思想
        • 在分配内存时，每次都从低地址开始查找，找到第一个能满足大小的空闲分区
      • (2)如何实现
        • 空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(空闲分区表)，找到大小能够满足要求的第一个空闲分区
      • (3)优点
        • 综合性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序
    • 2.循环首次适应(next fit, NF)算法
      • 又称临近适应算法
      • (1)算法思想
        • FF算法每次都从链头开始查找的。这可能导致低地址部分出现很多很小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题
      • (2)如何实现
        • 空闲分区以地址递增的次序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(空闲分区表)，找到第一个能满足大小的空闲分区
      • (3)优点
        • 不用每次都从最低地址的小分区开始检索，算法开销小，回收分区后一般不需要对空闲分区队列重新排序
      • (4)缺点
        • 会使高地址的大分区也被用完
    • 3.最佳适应(best fit, BF)算法
      • (1)算法思想
        • 在分配内存时，为了避免“大材小用”，且保证当“大进程”到来时能够有连续的大片空间，可以尽可能地留下大片的空闲区域，即优先使用更小的空闲区
      • (2)如何实现
        • 空闲分区按容量递增的次序排列。每次分配内存时顺序查找空闲分区链(空闲分区表)，找到第一个能满足大小的空闲分区
      • (3)优点
        • 会有更多的大分区被保留下来，更能满足大进程的需求
      • (4)缺点
        • 每次都选择最小的分区进行分配，会留下越来越多的、很小的、难以利用的外部碎片。算法开销大，回收分区后需要对空闲分区队列进行重新排序
    • 4.最坏适应(worst fit, WF)算法
      • 又称最大适应算法
      • (1)算法思想
        • 为了解决最佳适应算法的问题——即留下了太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空间区，这样分配后剩余的空闲区就不会太小更方便使用
      • (2)如何实现
        • 空闲分区按容量递减的次序排列。每次分配内存时顺序查找空闲分区链(空闲分区表)，找到第一个能满足大小的空闲分区
      • (3)优点
        • 可以减少难以利用的小碎片
      • (4)缺点
        • 每次都选择最大的分区进行分配，虽然让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的空闲区被迅速用完。算法开销大，回收分区后需要对空闲分区队列进行重新排序
  • 4.3.5 基于索引搜索的动态分区分配算法
    • 基于顺序搜索的动态分区分配算法，比较适用于不太大的系统。当系统很大时，系统中的内存分区可能会很多，相应的空闲分区链就可能很长，这时采用顺序搜索分区方法可能会很慢。为了提高搜索空闲分区的速度，在大。中型系统中往往会采用基于索引搜索的动态分区匹配算法
    • 1.快速适应(quick fit)算法
    • 2.伙伴系统(buddy system))
    • 3.哈希算法
  • 5.动态分区分配算法有几种。分别是什么？
  • 4.3.6 动态可重定位分区分配
    • 1.紧凑
      • 将内存中的所有作业进行移动，使它们全部相邻接。这样，即可把原来分散的多个空闲小分区拼接成一个大分区，可将一个作业装入该区。这种通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”
        • "紧凑"的时间代价很高
    • 2.动态重定位
      • 由于“紧凑”操作导致了当前作业在内存位置的变化，则需要设置一个重定位寄存器，重新定位程序在内存中的起始地址
• 覆盖技术
  • 一个固定区
    • 存放最活跃的程序段
    • 固定区中的程序段在运行过程中不会调入调出
  • 若干覆盖区
    • 不可能同时被访问程序段共享一个覆盖区
    • 覆盖区中的程序段在运行过程中会根据需要调入调出
  • 必须由程序员声明覆盖结构，操作系统完成自动覆盖
  • 缺点：对用户不透明，增加了用户的编程负担
• 4.4 对换(Swapping)
  • 4.4.1 多道程序环境下的对换技术
    • 1.对换的引入
      • 对换是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或者进程所需要的程序和数据换入内存。 对换是改善内存利用率的有效措施，它可以直接提高处理及的利用率和系统的吞吐量。
        • 6.什么是对换？
    • 2.对换的类型
      • (1)整体对换：以整个进程为单位进行对换，作为处理机的中级调度
      • (2)页面(分段)对换：以进程的一个“页面”或“分段”为单位进行被称为“页面对换”。其目的是为了支持虚拟存储系统。
      • 7.对换有哪些类型？
  • 4.4.2 对换空间的管理
    • 1.对换空间管理的主要目标
      • (1)对文件区管理的主要目标：提高文件存储空间利用率，然后再是提高对文件的访问速度。采取离散分配方式。
      • (2)对对换空间管理的主要目标：体改进程换入换出速度，然后才是提高文件存储空间利用率。采取连续分配方式，较少考虑外存中的碎片问题。
      • 8.对换空间管理的主要目标是什么？
    • 2.对换区空闲盘块管理中对的数据结构
    • 3.对换空间的分配与回收
  • 4.4.3 进程的换入与换出
    • 1.进程的换出
      • 在处理机正常运行时，并不启动对换程序，但如果发现有许多进程在运行时经常发生缺页且显现出内存紧张的情况，才启动对换程序，将一部分进程调至外存。如果发现所有进程的缺页率都已明显减少，而系统的吞吐量已下降时，则可暂停运行对换程序。
        • 9.目前用到的较多的对换方案是什么？
    • 2.进程的换入
      • 磁盘分为文件区和对换区，换出的进程放在对换区
      • ①分页存储管理方式：将用户程序的地址空间分为若干固定大小的区域，称为"页"或"页面"。在进行存储分配时，以页为单位放入内存的任一物理块中实现离散分配
      • ②分段存储管理方式：将用户程序的地址空间分为若干大小不同的区域，称为"段"，在进行存储分配时，以段为单位实现离散分配
      • ③段页式存储管理方式：是分页和分段两种存储管理方式相结合的产物
      • 10. 根据在离散分配时所分配地址空间的基本单位的不同，可分为哪几种方式？
• 4.5 分页存储管理方式
  • 4.5.1 分页存储管理的基本方法
    • 1.页面和物理块
      • (1)物理块：将内存空间分为一个个大小相等的分区，每个分区就是一个"页框"，或称"页帧"、"内存块"、"物理块"。每个页框会有一个编号，即"页框号("内存块号"、"页帧号"、"物理块号")"，页框号从0开始
      • (2)页面：将用户进程的地址空间分为与页框大小相等的一个个区域，称为"页"或者"页面"。每个页面有一个编号，即"页号"，页号也是从0开始的
      • (3)操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。就是说，进程的页面和内存的页框具有一一对应的关系。(注：页框不能太大，不然可能产生过大的内部碎片)
    • 2.地址结构
      • (1)分页地址中的地址结构如下
        • 地址长度为32位，0~11位为页内地址，即每页的大小为
        • 12~31位为页号，地址空间最多有
        • 页面偏移量=位移量W (低12位)
      • (2)分页管理中地址转换的手动步骤
        • ①计算出逻辑地址的对应页号
          • 页号=逻辑地址/页面长度 (整数除法)
        • ②找出该页号对应页面在内存中的起始地址
          • 页面在内存中的起始位置：操作系统需要用某种数据结构记录进程各个页面的起始位置
        • ③计算出逻辑地址在页面内的“页内偏移量”
          • 页内偏移量=逻辑地址%页面长度 (取余)
        • ④物理地址 = 页面起始地址+页内偏移量
    • 3.页表
      • (1)概念：在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。
      • (2)注意
        • ①一个进程对应一个页表
        • ②进程的每一个页都对应一个页表项
        • ③每个页表项由"页号"和"块号"组成
        • ④页表记录进程页面和实际存放的内存块(物理块)之间的对应关系
        • ⑤每个页表项的的长度是相同的，页号是"隐含"的
          • 例如：假设某系统物理内存大小4GB，页面大小为4KB，每个页表项至少应该为多少字节？
          • 答：内存块数=
          • 因此内存块号的范围为0~2^20-1，因此至少需要3个字节的页表项才能表示全部页
          • 各页表项会按顺序连续地存放在内存中，因此只需要知道页表存放的起始地址和页表项长度，即可找到各个页号对应的页表项存放的位置
  • 4.5.2 地址变换机构
    • 1.基本的地址变换机构
      • (1)基本地址变换机构可以借助页表将逻辑地址转化为物理地址
        • 页式管理的地址是一维的
      • (2)通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。
      • (3)进程未执行时，页表的始址和页表长度放在进程控制块PCB中，当进程被调度时，操作系统内核会把他们放到页表寄存器中
      • (4)设页面大小为L，逻辑地址A到物理地址E的变换过程为
        • ①计算页号P和页内偏移量W（计算机中计算看其各占逻辑地址的多少位,页内偏移量的位数根据页面大小而得），手动计算为P=A/L，W=A%L
        • ②比较页号P和页表长度M，若P≥M，则发生越界中断，否则继续执行（页号从0开始的，而页表的长度至少为1，所以P=M时同样发生越界）
        • ③页表中页号P对应的页表项地址=页表起始起始地址F+页号P*页表项长度，在页表中找到对应的内存块号b
          • 第一次访问内存：查页表
        • ④计算E=b*L+W，得到最终的物理地址E去访存(计算机中内存块号b和页内偏移量W的二进制合并起来即为物理地址)
          • 第二次访问内存：访问目标内存单元
        • • 页表寄存器
            • 存放页表起始地址F
            • 存放页表长度M
      • (5)例题
        • 若页面大小L为1K字节，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E （等价描述：某系统按字节寻址，逻辑地址结构中，页内偏移量占10位，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E）
        • 页号P=2500/1024 = 2，页内偏移量W=2500%1024=452，物理地址E=1024*8+452=8644
    • 2.具有快表的地址变换机构
      • (1)概念：增设一个具有并行查询能力的特殊高速缓冲寄存器，又称为“联想寄存器”或者“快表”，在其中存储部分页表
      • (2)局部性原理
        • 时间局部性：如果执行了程序中的某条指令，那么不久之后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据可能再次被访问（因为程序中存在大量的循环）
        • 空间局部性：一旦程序访问了某个存储单元，那么不久之后其附近的存储单元也很有可能被访问（因为很多数据在内存中都是连续存放的）
      • (3)什么是快表(Translation Lookaside Buffer，TLB)
        • 存储在更高速的存储器中，用于存储部分页表
      • (4)引入快表后，地址变换的过程
        • ①CPU给出逻辑地址，由某个硬件算出页号、页面偏移量，将页号与快表中的所有页号进行比较
        • ②如果找出匹配的页号，说明要访问的页表项在快表中有副本，则直接取出该页对应的内存块号，再通过内存块号和页面偏移量拼接得到物理地址，最后再访问物理地址所对应的内存单元，因此，若快表命中，则访问某个逻辑地址，仅需一次访存
        • ③如果没有找出匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页面偏移量拼接得到物理地址，最后再访问物理地址所对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面的再次访问。若快表已满，则必须按照一定的算法对旧的页表项进行替换）
        • 
  • 4.5.3 访问内存的有效时间
    • (1)概念
      • 访问内存的有效时间是指从进程发出指定逻辑地址的访问请求，经过地址变化，到在内存中找到对应的实际物理地址单元并取出数据，所需花费的总时间。
        • 4. 什么是访问内存的有效时间？
    • (2)由于查询快表的速度比查询页表的速度快很多，因此只要快表命中了，就可以节省很多时间，因为局部性原理，一般来说快表的命中率可以达到90%以上
    • (3)例题
      • 某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us，访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？
      • (1+100)*0.9+(1+100+100)*0.1 = 111us
  • 4.5.4 两级和多级页表
    • (1)单级页表存在的问题
      • 所有页表必须连续存放，页表过大时需要很大的连续内存空间
        • 采用二级页表或多级页表技术
      • 在一段时间内并非所有页面都用的到，因此没必要让整个页表常驻内存
        • 可以在需要访问页面时才把页面调入内存(虚拟内存技术)。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存
    • (2)两级页表
      • • 若想要访问的页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存
      • 地址结构
      • 注意几个术语：页目录表/外层页表/顶级页表
    • (3)注意
      • ①若采用多级页表机制，则各级页表的大小不能超过一个页面(内存块)大小
        • 例：若某系统采用字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用()级页表，页面偏移量占()位？
        • 页面大小=4KB=2^12B，按字节编址，因此页面偏移量为12位，页号共占28位，每个页面可以存储的页表项个数=2^12/4 = 2^10，则8位一级页号，10位二级页号，10位三级页号，12位页面偏移量
      • ②多级页表的访存次数(假设没有快表机构)——N级页表访问一个逻辑地址需要访存N+1次
  • 4.5.5 反置页表(Inverted Page Table)
    • 1.反置页表的引入
      • 为了减少页表占用的内存空间，引入了反置页表。一般页表的页表项是按页号进行排序的，页表项中的内容是物理块号。而反置页表则是为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所隶属进程的标识符
    • 2.地址变换
      • 在利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表
• 4.6 分段存储管理方式
  • 4.6.1 分段存储管理方式的引入
    • 1.方便编程
    • 2.信息共享
    • 3.信息保护
    • 4.动态增长
    • 5.动态链接
    • 12. 引入分段存储管理是为了满足用户哪几方面的需要。
  • 4.6.2 分段系统的基本原理
    • 1.分段
      • (1)进程的地址空间：按照程序自身的逻辑关系划分成若干个段，每个段都有一个段名（低级语言中，程序员使用段名来编程），每段从0开始编址
      • (2)内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可不相邻
      • (3)由于是按逻辑功能划分的，用户编程更方便，程序的可读性更高 LOAD 1,[D] | <A>; // 将分段D中A单元内的值读入寄存器1 STORE 1,[X] | <B>; // 将寄存器1的内容存入分段X的B单用中
        • 写程序时用的段名[D][X]会被编译程序翻译成对应的段号 <A>和<B>单元会被编译程序翻译成段内地址
      • (4)逻辑地址结构
        • 分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成的
        • 段号的位数决定了进程最多分多少个段
        • 段内地址位数决定了每个段的最大长度是多少
    • 2.段表
      • (1)概念：程序分为多个段，各段离散的装入内存，为了保证程序能正常的运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需要为每个进程建立一张段映射表，”段表“
      • (2)注意
        • ①每一个段对应一个段表项，其中记录了该段在内存中的起始位置(又称"基址")和段的长度
        • ②记录逻辑段到实际存储地址的映射关系
        • ③各个段表项的长度是相同的，"段号"是隐含的
          • 例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为(段号16位，段内地址16位)，因此16位即可表示最大段长。物理内存大小为4GB(可用32位表示整个物理内存地址空间)。因此，可以让每个段表项占16+32=48位，即6个字节，由于段表项长度相同，因此段号可以隐含，不占存储空间。若段表存放的起始地址为M，则K号段对应的段表项存放的地址应该为M+6K
    • 3.地址变换机构
      • • (1)由逻辑地址得到段号、段内地址
        • (2)段号与段表寄存器中的段长比较，检查是否越界
        • (3)由段表始址、段号找到对应段表项
        • (4)根据段表中的记录的段长、检查段内地址是否越界
        • (5)由短标中的基址+段内地址得到最终的物理地址
        • (6)访问目标单元
    • 4.分段、分页管理的对比
      • (1)相同点
        • 两者都采用离散分配方式，且都是通过地址映射机构实现地址变换
        • 分段系统同于分页系统，也可以引入快表机构，将近期访问过的段表项放入快表中，可以减少一次访存，加快地址变换的速度
      • (2)不同点
        • ①主要目的
          • 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的
          • 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段是对用户可见的，用户编程时需要显示地给出段名
        • ②页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序
        • ③地址空间
          • 分页的用户进程的地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址
          • 分段的用户进程的地址空间是二维的，程序员在标识一个地址时，要给出段名和段内地址
        • ④分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的
      • 11. 试说明分页存储管理和分段存储管理异同点。
  • 4.6.3 信息共享
    • 分段比分页更容易实现信息的共享和保护
      • 由于页面不是按逻辑模块划分的，这样就很难实现共享
    • 不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能被共享的(比如，一段代码中有很多变量，各进程并发地同时访问可能造成数据的不一致)
      • 因此要实现代码的复用，只需让各进程的段表项指向同一个段即可实现共享
  • 4.6.4 段页式存储管理方式
    • 段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分为若干个段，再把每个段分成若干个页，并为每一个段赋一个段名。这种管理方式既具有分段系统的便于实现、分段可共享、易于保护等优点。又能像分页系统那样，很好地解决内存的外部碎片问题。
      • 13. 试说明段页式存储管理方式的基本原理?
    • 1.分页、分段的优缺点
      • 分段管理中的外部碎片也可以用"紧凑"来解决，只是要付出较大的时间代价
    • 2.段页式管理的逻辑地址结构
      • 段页式系统的逻辑地址结构由段号、页号、页内地址(页内偏移量)组成。
        • "分段"对用户是可见的，程序员编程时需要显示的给出段号、段内地址。而将各段"分页"对用户是不可见的。系统会根据段内地址将其自动划分为页号和页内偏移量。因此段页式管理的地址结构是二维的
      • 段号的位数决定了每个进程最多可以分几个段 页号的位数决定了每个段最大有多少页 页面偏移量决定了页面大小、内存块大小是多少
    • 3.段表、页表
      • 每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号(页表起始地址)组成。每个段表项长度相等，段号是隐含的
      • 每个页面对应一个页表项，每个页表项是由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的
    • 4.地址变换机构
      • (1)根据逻辑地址得到段号、页号、页面偏移量
      • (2)判断段号是否越界。若产生越界，中断，否则继续执行
      • (3)查询段表，找到对应的段表项，段表项的存放地址=F+S*段表项长度
      • (4)检查页号是否越界，若产生越界，中断，否则继续执行
      • (5)根据页表存放块号、页号查询页表，找到对应的页表项
      • (6)根据内存块号、页面偏移量得到最终的物理地址
      • (7)访问目标内存单元
    • 5.访问一个逻辑地址需要的访存次数
      • 总共发生三次访存，第一次查段表，第二次查页表，第三次访问目标单元
      • 可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
• 15. 假设某长度为n的存储单元中，存放一长度为m的作业(n>m)，则长度为(n-m)的空间称为该单元的内部碎片；若存储单元长度为n，在该系统采用的调度算法下，无法选出一道作业能放入此存储单元中，则称该存储空间为外部碎片。在固定分区分配、可变分区分配、分页存储系统、分段存储系统中，各会出现何种碎片？为什么？
  • 固定分区分配会产生内部碎片：因为内存分区空间大小是固定的，无论作业长短，存储单元长度不会随之变化，所以如果作业长度小于分区长度，则会产生内部碎片
  • 可变分区分配会产生外部碎片：因为内存分区空间大小是根据作业长短而分配的，而如果剩余内存空间太小不够多余分配，则会产生外部碎片
  • 分页存储系统会产生内部碎片：因为每个物理块的大小是同页面大小一致，但是一个进程的最后一个页面可能会小于一个物理块的大小，所以分配过后会产生内部碎片
  • 分段存储系统会产生外部碎片：因为每个内存分区空间大小是根据进程的段大小进行分配的，而当内存中空间太小时无法进行段的分配，此时会产生外部碎片
• 14.对于下表所示的段表，计算逻辑地址（0,430）、（2,88）、（4,112）所对应的物理地址。
  • 对于逻辑地址(0,430)，430<600，对应的物理地址=430+256=686
  • 对于逻辑地址(2,88)，88<128，对应的物理地址=88+2300=2388
  • 对于逻辑地址(4,112)，112>100，越界，产生越界中断
• 覆盖与对换技术的区别
  • 覆盖是在同一个程序或进程中的
  • 交换是在不同进程(或作业)之间的
• 内存管理的概念
  • 1.内存地址的分配与回收
    • 连续分配管理方式
      • 单一连续分配
      • 固定分区分配
      • 动态分区分配
    • 非连续分配管理方式
      • 基本分页存储管理
      • 基本分段存储管理
      • 段页式存储管理
    • 传统存储管理
  • 2.内存空间的扩充(实现虚拟性)
    • 覆盖技术
    • 交换技术
    • 虚拟存储技术
      • 请求分页存储管理
      • 请求分段存储管理
      • 请求段页式存储管理
  • 3.地址转换(地址映射)
    • 操作系统负责实现逻辑地址到物理地址的转换
    • 三种方式
      • 绝对装入
      • 可重定位装入
      • 动态运行时装入
  • 4.存储保护
    • 保证各个进程在自己的内存空间中运行，不会越界访问
    • 两种方式
      • 设置上下限寄存器
      • 利用重定位寄存器(基址寄存器)、界地址寄存器(限长寄存器)进行判断

第五章 虚拟存储器

• 5.1 虚拟存储器概述
  • 5.1.1 常规存储管理方式的特征和局部性原理
    • 1.常规存储器管理方式的特征
      • (1)一次性，是指作业必须一次性地全部装入内存后方能开始运行，这会造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法运行；②当大作业要求运行时，由于内存无法容纳所有作业，所以只有少量作业能运行，导致多道程序并发度下降
      • (2)驻留性，一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的资源
    • 2.局部性原理
      • 时间局部性：如果执行了程序中的某条指令，那么不久之后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据可能再次被访问（因为程序中存在大量的循环）
      • 空间局部性：一旦程序访问了某个存储单元，那么不久之后其附近的存储单元也很有可能被访问（因为很多数据在内存中都是连续存放的）
      • 高速缓存的技术思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放入更低速存储器中
      • 快表机构就是将近期常访问的页表项副本放到更高速的联想寄存器中
    • 3.虚拟存储器的基本工作情况
      • ①基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅需将那些当前要运行的少数页面或段先装入内存，暂时用不到的部分留在外存便可运行。
      • ②在程序执行的过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
      • ③若内存空间不够，由操作系统负责将内存中暂时不用的信息换出到外存
      • ④在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
  • 5.1.2 虚拟存储器的定义和特征
    • 1.虚拟存储器的定义
      • 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
        • 1. 虚拟存储器的定义是什么?
      • 其实际容量由内存容量和外存容量之和所决定，其最大容量由计算机的地址结构(CPU寻址范围)确定的，其运行速度接近于内存速度
      • 如：某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB。则虚拟内存的最大容量为2^32B=4GB,虚拟内存的实际容量=min(4GB,512MB+2GB)=2.5GB
    • 2.虚拟存储器的特征
      • (1)多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
      • (2)对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入换出
      • (3)虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量
      • 2. 虚拟存储器具有那三个重要特征?
  • 5.1.3 虚拟存储器的实现方法
    • 需要建立在离散分配的内存管理方式之上
    • 3. 虚拟存储器的实现方法有哪些？
      • 请求分页系统，即在分页系统的基础上增加了请求调页功能和页面置换功能说形成的页式虚拟存储系统。
      • 请求分段系统，即在分段系统的基础上增加了请求调段功能和页面置换功能说形成的段式虚拟存储系统。
    • 与传统非连续分配存储管理的区别
      • 在程序执行的过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
        • 操作系统要提供请求调页(或请求调段)功能
      • 若内存空间不够时，由操作系统负责将内存中暂时用不到的信息换出内存
        • 操作系统要提供页面置换(或段置换功能)
        • 6.在何种情况下需要选择页面置换算法？
          • 在进程运行过程中，若其所要访问的页面不存在，而需把它们调入内存，但内存已无空闲空间时，为了保证进程能正常运行，系统必须从内存中调出一个页面送到磁盘的对换区中，此时，应选取页面置换算法。
    • 1.请求分页系统
      • (1)硬件支持
        • ①请求分页的页表机制
        • ②缺页中断机构
        • ③地址变换机构
      • (2)实现请求分页的软件
    • 2.请求分段系统
      • (1)硬件支持
        • ①请求分段的段表机制
        • ②缺段中断机构
        • ③地址变换机构
      • (3)实现请求分段的软件
    • 4.分页请求系统和请求分段系统分别需要什么硬件支持？
    • 3.请求段页式系统
• 5.2 请求分页存储管理方式
  • 5.2.1 请求分页中的硬件支持
    • 1.请求页表机制
      • 4.请求分页系统中的硬件支持
      • 请求分页存储管理机制的页表(请求页表)
        • (1)状态位P：用于指示该页是否已调入内存
        • (2)访问字段A：用于记录本页在一段时间内被访问的次数，或记录上次访问的时间，提供给置换算法(程序)在选择换出页面时参考
        • (3)修改位M：用于标识页面调入内存后是否被修改过
        • (4)外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考
    • 2.缺页中断机构
      • (1)在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后，才检查是否有中断请求到达。若有，便去响应，否则，继续执行下一条指令。然而，缺页中断是在指令执行期间，①若发现所要访问的指令或数据不在内存时，便立即产生和处理缺页中断信号，②缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面。③缺页中断是因为当前指令想要访问的目标页面未调入内存而产生的，因此属于内中断
      • (2)一条指令在执行期间，可能产生多次缺页中断。
    • 3.地址变换机构
      • 相较于基本分页存储新增步骤
        • 请求调页(查到页表项时进行判断)
        • 页面置换(需要调入页面，但没有空闲内存块时进行)
        • 需要修改请求页表中新增的表项
      • • • 补充
            • ①只有"写指令"才需要修改"修改位"，并且，一般来说只需要修改快表中的数据，只有要将快表项数据删除时才需要写回内存中的慢表。这样可以减少访存的次数
            • ②和普通的中断处理一样，缺页中断处理依然需要保留CPU现场
            • ③需要用某种"页面置换算法"来决定换出某个页面
            • ④换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/换出太频繁，会有很大的开销
            • ⑤页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中
  • 5.2.2 请求分页中的内存分配
    • 1.最小物理块数(驻留集大小)的确定
      • 驻留集：指请求分页存储管理中给进程分配的物理块的集合
      • 在采用了虚拟存储技术的系统中，驻留集的大小一般小于进程的总大小
      • 如果驻留集大小为进程的总大小，那么全部放入了内存，不会发生却缺页，但会导致多道程序并发度下降，资源利用率降低。如果驻留集大小远远小于进程的大小，那么必定会频繁的缺页
    • 2.内存分配策略
      • (1)分配策略
        • ①固定分配：操作系统为每一个进程分配一组固定数目的物理块，在进程运行期间不再改变，即驻留集大小不再改变
        • ②可变分配：先为每个进程分配一定数目的物理块，在进程运行期间可根据情况做适当的增加或减少，即驻留集大小可变
      • (2)置换策略
        • ①局部置换：发生缺页时只能选进程自己的物理块进行置换
        • ②全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
      • 具体策略
        • 固定分配局部置换
          • 定义：系统为每个进程分配一定数量的物理块，在整个运行期间不变。若进程在运行过程中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
          • 特点：很难在一开始就确定每个进程需要分配多少个物理块才算合理(采用这种策略的系统可以根据进程大小、优先级、或是程序员给出的参数来决定为一个进程分配的内存块数)
        • 可变分配全局置换
          • 定义：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若无已空闲物理块，则选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。
          • 特点：只要某进程发生缺页，都会获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任意进程的页，因此被选中的进程的物理块会减少，缺页率会增加
        • 可变分配局部置换
          • 定义：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个换出外存
          • 特点：如果进程运行的过程中频繁缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度，反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块
    • 3.物理块分配算法
  • 5.2.3 页面调入策略
    • 1.何时调入页面
      • (1)预调页策略
        • 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入页面中大多数没被访问过，则又是低效的。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪部分
      • (2)请求调页策略
        • 进程在运行期间发生缺页时才将所需页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次都要磁盘I/O操作，因此I/O开销大
    • 2.从何处调入页面
      • (1)系统拥有足够的对换区空间：页面的调入调出都是在内存与对换区之间进行，这样可以保证页面的调入调出速度很快。在进程运行之前，需将进程相关的数据从文件区复制到对换区
      • (2)系统缺少足够的对换区空间：凡是不会被修改的数据都会从文件区直接调入内存，由于这些数据不会被修改，因此换出时不必写回磁盘，下次需要时再从文件去掉调入即可，对于可能需要被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入
      • (3)UNIX方式：运行之前进程的有关数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时再从对换区调入
    • 3.页面调入过程
      • ①每当程序所要访问的页面未在内存时(存在位为"0")，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。该程序通过查找页表得到该页在外存的物理快
      • ②如果此时内存能容纳新页，则启动磁盘I/O，将所缺之页调入内存，然后修改页表。如果内存已满，则需先按照某种置换算法，从内存中选出一页准备换出
      • ③如果换出页未被修改过(修改位为"0")，可不必将该页写回磁盘；但是如果此页已被修改(修改位为"1")，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为"1"，并将此页表项写入快表中。
      • ④在缺页调入内存后，利用修改后的页表形成所要访问数据的物理地址，再去访问内存数据，整个页面的调入过程对用户是透明的。
    • 4.缺页率
      • 1.缺页率的定义：如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率为：
      • 2.缺页率的影响因素
        • ①页面大小：页面越大，缺页率越低；反之越高
        • ②进程所分配到的物理块数：物理块越多，缺页率越低；反之越高
        • ③页面置换算法：算法优劣决定了进程执行过程中缺页中断的次数，所以缺页率也可以反映置换算法的优劣
        • ④程序固有特性：程序的局部性特点越突出，缺页率越低；反之越高
        • 5.什么因素会影响缺页率？
• 5.3 页面置换算法
  • 页面的换入换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
  • 5.3.1 最佳置换算法和先进先出的置换算法
    • 1.最佳(Optimal)置换算法
      • (1)思想
        • 每次淘汰的页面将是以后永不使用，或者在长时间内不再被访问的页面，这样可以保证最低的缺页率
      • (2)例题
        • 假设某系统为某进程分配了三个内存块，并考虑到有下一页面号引用串(会依次访问这些页面)：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
        • • 第四次访问页面，从0,1,7中淘汰一个页面。按最佳置换原则，往后寻找，找到最后一个出现的页面时7，将其替换
        • 整个过程中缺页中断发生了9次，页面置换发生了6次。 注意：缺页发生时未必就发生了页面置换。若还有可用的空闲内存块，就不用进行页面置换 缺页率=9/20 = 45%
      • 最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才知道接下来会访问到的页面是哪个。操作系统无法提前预知访问页面的序列。因此，最佳置换算法是无法实现的
    • 2.先进先出(FIFO)页面置换算法
      • (1)思想
        • 每次淘汰的页面是最早进入内存的页面
      • (2)实现方法
        • 把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块
      • (3)例题
        • 假设系统为某进程分配了三个内存块，并考虑到有下一页面号引用串：3,2,1,0,3,2,4,3,2,1,0,4
        • 
        • 假设设置了四个内存块
        • 分配四个块时缺页10次，分配三个块时缺页9次
          • Belady异常——当为进程分配的物理块数增大时，缺页次数不增反减的现象
          • 只有FIFO算法会产生Belady异常。此外FIFO算法虽然实现简单，但是该算法与进程实际运行时间的规律不适应，因为先进入的页面也有可能最经常被访问。因此该算法性能差
  • 5.3.2 最近最久未使用和最少使用置换算法
    • 1.LRU(Least Recently Used)置换算法的描述
      • (1)思想
        • 每次淘汰的页面是最近最久未使用的页面
      • (2)实现方法
        • 赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用过的页面
      • (3)例题
        • 假设为某进程分配了四个内存块，并考虑到有下一页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
        • 
        • 在手动做题时，若需要淘汰页面，可以逆向检查此时存在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面
      • 该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
    • 2.LRU置换算法的硬件支持
      • (1)寄存器
        • 为了记录某进程在内存中各页的使用情况，需为每个在内存中的页面配置一个移位寄存器
      • (2)栈
        • 可利用一个特殊的栈保存当前使用的各个页面的页面号
    • 3.最少使用(Least Frequently Used, LFU)置换算法
      • (1)思想
        • 每次淘汰的页面是最近最少使用的页面
      • (2)实现方法
        • 在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次选择在最近时期使用最少的页面作为淘汰页
  • 5.3.3 Clock置换算法
    • 1.简单的Clock置换算法
      • 也可以称为最近未用算法(Not Recently Used, NRU)
      • (1)思想和实现方法
        • 赋予每个页面对应的页表项中一个访问字段记录该页面是否被访问，再将内存中的页面通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1，每需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出，如果是1就将其置0，暂不换出，继续扫描队列的下一项，直到访问到访问位为0的页面，将其换出。(简单的clock置换算法选择一个淘汰页面最多会经过两轮扫描)
      • (2)例题
        • 假设为某进程分配了五个内存块，并考虑到有下一页面号引用串：1,3,4,2,5,6,3,4,7
        • 
          • 
    • 2.改进的Clock置换算法
      • 简单时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存
      • (1)思想和实现方法
        • 因此，除了考虑一个页面最近是否被访问过之外，操作系统还应该考虑这个页面是否被修改过。在其他的条件都相同时，应优先淘汰没有被修改过的页面，避免I/O操作。这就是改进时钟置换算法的思想。页表项中的修改位=0，表示页面没有被修改，修改位=1，表示页面被修改过
        • 算法规则：将所有可能被置换的页面排成一个循环队列 （访问字段，修改位）表示各个页面状态
          • 第一轮：从当前位置开始扫描到第一个(0,0)的页面用于替换。本轮扫描不需要修改任何标志位
            • 第一优先级：最近没有被访问，且没有被修改
          • 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0,1)的页面用于替换。本轮将所有的访问字段设为0
            • 第二优先级：最近没有被访问，但是被修改
          • 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0,0)的页面用于替换。本轮扫描不需要修改任何标志位
            • 第三优先级：最近被访问，但是没被修改
          • 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0,1)的页面用于替换
            • 第四优先级：最近被访问，并且被修改
          • 由于第二轮扫描已经将所有页面的访问字段设为0了，因此通过第三轮和第四轮扫描必定会有页面被选中，因此改进的clock置换算法选择淘汰一个页面最多需要四轮扫描
  • 
  • 5.3.4 页面缓冲算法(Page Buffering Algorithm, PBA)
    • 1.影响页面换进换出效率的若干因素
      • (1)页面置换算法
      • (2)写回磁盘的频率
      • (3)读入内存的频率
      • 8.影响页面换进换出效率的因素有哪些？
    • 2.页面缓冲算法PBA
      • 特点
        • ①显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大大减少，因而减少了页面换进换出的开销
        • ②由于换入换出的开销大幅度减小，才能使其采用一种较为简单的置换策略，例如FIFO算法
        • 7.试说明页面缓冲算法的主要特点。
      • 在内存中设置了如下链表
        • ①空闲页面链表：是系统掌握的物理块，用于分配给频繁发生缺页的进程
        • ②修改页面链表：由已修改的页面所形成的的链表，目的是为了减少已修改页面换出的次数
  • 5.3.5 访问内存的有效时间
    • (1)被访问页在内存中，且其对应的页表项在快表中
      • 此时不存在缺页中断的情况，内存的有效访问时间(EAT)分为查找快表的时间(λ)和访问实际物理地址需要的时间(t)：EAT=λ+t
    • (2)被访问页在内存中，且其对应的页表项不在快表中
      • 此时也不存在缺页中断的情况，但是需要两次访问内存，一次读页表，一次读取数据，另外还需要更新快表。所以这种情况的内存有效访问时间可分为查找快表的时间、查找页表的时间、修改快表的时间和访问实际物理地址的时间：EAT=λ+t+λ+t = 2(λ+t)
    • (3)被访问页不在内存中
      • 此时在(2)的基础上增加了缺页中断的时间ε：EAT=ε+2(λ+t)
• 5.4 “抖动”与工作集
  • 5.4.1 多道程序度与“抖动”
    • 1.抖动(颠簸)现象
      • 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存，这种频繁的页面调度行为称为抖动，或颠簸
    • 2.产生抖动的主要原因
      • 进程频繁访问的页面数目高于可用的物理块数。(分配给进程的物理块不够)
        • 为进程分配的物理块太少，会使进程发生抖动现象。 为进程分配的物理块太多，又会降低系统整体的并发度。降低某些资源的利用率。
    • 9.为什么会产生抖动？
      • 发生抖动的根本原因是同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存，会使系统中排队等待页面调进/调出数目增加，造成每个进程的时间大部分都用来换进换出，几乎不再做有效工作，从而导致发生处理机的利用率急剧下降并趋于零的情况。故产生“抖动”。
  • 5.4.2 工作集
    • 1.定义：只在某段时间间隔里，进程实际访问页面的集合。
  • 5.4.3 “抖动”的预防方法
    • 1.采取局部置换策略：即使发生了进程抖动，也不会对其他进程产生影响，可以把进程抖动限制到较小范围内
    • 2.把工作集算法融入到处理机调度中
    • 3.利用"L=S"准则调节缺页率
    • 4.选择暂停的进程：多道程序度偏高时，已影响到处理机的利用率，为了防止抖动，系统必须减少多道程序的数目，此时应基于某种原则选择暂停某些活动的进程
    • 10.“抖动”的预防措施有哪些？
• 5.5 请求分段存储管理方式
  • 5.5.1 请求分段中的硬件支持
    • 1.请求段表机制
    • 2.缺段中断机构
    • 3.地址变换机构
    • 4.请求分段系统的硬件支持
  • 5.5.2 分段的共享与保护
• 11. 某系统采用分页存储管理方式，设计如下：页面大小为4KB，允许用户虚空间最大为16页，允许系统物理内存最多为512个内存块。试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位？
  • ①页面大小为4KB，由于页面大小等于物理块大小，则页内偏移量长度为12位，物理块内偏移量长度也为12位，则物理块大小也占12位 ②物理内存块最多为512个，则物理块号占9位，用户逻辑空间最大为16页，则页号占4位 ③虚地址寄存器长度=页号长度+页内偏移量长度=4+12=16位 物理地址寄存器长度=物理块号长度+物理块大小=9+12=21位

第六章 输入输出系统

• 6.1 I/O系统的功能、模型和接口
  • 6.1.1 I/O系统的基本功能
    • 1. 隐藏物理设备的细节
      • I/O设备的类型非常多，且彼此间在多方面都有差异，诸如接收和产生数据的速度，传输方向、粒度、数据的表示形式及可靠性等方面。
    • 2. 与设备的无关性
      • 隐藏物理设备的细节，在早期的OS中就已实现，它可方便用户对设备的使用。与设备的无关性是在较晚时才实现的，这是在隐藏物理设备细节的基础上实现的。
    • 方便用户使用I/O设备
    • 3.`提高处理机和I/O设备的利用率
      • I/O系统的第三个功能是要尽可能地让处理机和I/O设备并行操作，以提高它们的利用率。为此，一方面要求处理机能快速响应用户的I/O请求，使I/O设备尽快地运行起来；另一方面也应尽量减少在每个I/O设备运行时处理机的干预时间。
    • 4. 对I/O设备进行控制
      • 对I/O设备进行控制是驱动程序的功能。目前对I/O设备有四种控制方式
        • ①采用轮询的可编程I/O方式
        • ②采用中断的可编程I/O方式
        • ③直接存储器访问方式
        • ④I/O通道方式
    • 提高CPU/IO设备利用率
    • 5.确保对设备的正确共享
      • 从设备的共享属性上，可将系统中的设备分为如下两类
        • (1)独占设备，进程应互斥地访问这类设备，即系统一旦把这类设备分配给了某进程后，便由该进程独占，直至用完释放。
        • (2)共享设备，是指在一段时间内允许多个进程同时访问的设备。典型的共享设备是磁盘。
    • 6. 错误处理
      • 大多数的设备都包括了较多的机械和电气部分，运行时容易出现错误和故障。从处理的角度，可将错误分为临时性错误和持久性错误。对于临时性错误，可通过重试操作来纠正，只有在发生了持久性错误时，才需要向上层报告。
    • 保证系统平稳运行
    • 1.I/O系统的基本功能有哪些？
  • 6.1.2 I/O系统的层次结构和模型
    • 1.I/O软件的层次结构
      • 1)用户层 I/O 软件：实现与用户交互的接口，用户可直接调用该层所提供的、与 I/O 操作有关的库函数对设备进行操作。
      • 2)设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
      • 3)设备驱动程序：与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动 I/O 设备工作的驱动程序。
      • 4)中断处理程序：CPU 先保护被中断进程的 CPU 环境，再转入相应的的中断处理程序进行处理，处理完毕后 CPU 再恢复被中断进程的现场，返回到被中断的进程。
      • • 2. I/O软件组织的层次分别是什么，简述其功能。
  • 6.1.3 I/O系统接口
• 6.2 I/O设备和设备控制器
  • 6.2.1 I/O设备
    • 1.I/O设备的类型
      • 1)按使用特性分类
        • 第一类是存储设备，也称外存、辅存，是用以存储信息的主要设备
        • 第二类是I/O设备
          • 输入设备：接受外部信息，如鼠标、键盘、扫描仪、视频摄像等
          • 输出设备：用于将计算机处理后的信息送向处理机外部的设备，如打印机
          • 交互式设备：集成了上述两类的设备，主要是显示器，用于同步显示用户命令及命令执行结果
      • 2)按传输速率分类
        • 第一类是低速设备：其传输速率仅为每秒钟几个字节至数百个字节，如键盘、鼠标等
        • 第二类是中速设备：其传输速率在每秒钟数千字节至数十万字节，如行式打印机、激光打印机等
        • 第三类是高速设备：其传输速率在数十万字节至千兆字节，典型的如磁带机、磁盘机、光盘机等
      • 3. 试说明I/O设备的类型。
    • 2.设备与控制器之间的接口
      • (1)数据信号线：这类信号线用于在设备和设备控制器间传送数据信号
      • (2)控制信号线：这是作为由设备控制器向I/O设发送控制信号时的通路。该信号规定了设备将要执行的操作，如读操作、写操作或执行磁头移动等操作
      • (3)状态信号线：该信号线用于传送指示设备当前状态的信号
  • 6.2.2 设备控制器
    • 1.设备控制器的基本功能
      • (1) 接收和识别命令：接收CPU通过I/O总线发来的命令和参数, 存储在控制器中相应的控制寄存器中, 并对它进行译码识别, 转换成适当的电信号, 通过控制器与设备的接口向设备发送, 指挥设备执行特定的操作。
      • (2) 标识和报告设备的状态：接收从设备发来的电信号, 进行转换和解释, 变为设备的状态信息, 将此结果记录在控制器的状态寄存器上, 供CPU了解。
      • (3) 地址识别：识别I/O端口地址, 使I/O操作与设备对应
      • (4) 数据交换
      • (5) 数据缓冲区
      • (6) 差错控制
      • 实现CPU↔控制器↔设备的数据交换, 从而实现了CPU到设备的数据传递和设备到CPU的数据传递。
  • 6.2.3 内存映像I/O
  • 6.2.4 I/O通道
    • 1.I/O通道设备的引入
      • 虽然在CPU与I/O设备之间增加了设备控制器后，已能大大减少CPU对I/O的干预，但当主机所配置的外设很多时，CPU的负担仍然很重。为此，在CPU和设备控制器之间又增设了I/O通道(I/O Channel)
      • I/O通道是一种特殊的处理机，具有执行I/O命令的能力，并通过执行通道程序来控制I/O操作，指令单一，只能执行I/O操作有关的命令，且通道没有自己内存，与CPU共享内存，其目的是让CPU从繁杂的I/O任务中解脱出来
      • 原理：执行通道程序，向控制器发出命令，并具有向CPU发中断信号的功能。 一旦CPU发出指令，启动通道，则通道独立于CPU工作
    • 2. 通道类型
      • 1) 字节多路通道(Byte Multiplexor Channel)
        • 连接大量慢速外围设备而设置的，它可以分时地执行多个通道程序
        • 当一个通道程序控制某台设备传送一个字节后，通道硬件就控制转去执行另一个通道程序，控制另一台设备传送信息。主要连接以字节为单位的低速I/O设备。如打印机，终端。以字节为单位交叉传输，当一台传送一个字节后，立即转去为另一台传送字节。这些子通道按时间片轮转方式共享主通道。
      • 2) 数组选择通道(Block Selector Channel)
        • 字节多路通道不适于连接高速设备，数组选择通道按数组方式进行数据传送。
        • 以成组方式工作的，即每次传送一批数据，故传送速度很高。在这段时间内只能为一台设备服务。当这台设备数据传输完成后，再选择与通道连接的另一台设备。主要连接磁盘，磁带等高速I/O设备。
      • 3) 数组多路通道(Block Multiplexor Channel)
        • 数组选择通道虽有很高的传输速率，但它却每次只允许一个设备传输数据。数组多路通道是将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作的优点相结合而形成的一种新通道。
        • 它先为一台设备执行一条通道指令，然后自动转接，为另一台设备执行一条通道指令。主要连接高速设备。
        • 数组多路通道实际上是对通道程序采用多道程序设计的硬件实现。
• 6.3 中断机构和中断处理程序
  • 6.3.1 中断简介
    • 1. 中断和陷入
      • 1) 中断：指CPU对I/O设备发来的中断信号的响应。由外部设备引起，故又称为外中断。
      • 2) 陷入：由CPU内部事件引起的中断，如程序出错等等，故又称为内中断。中断和陷入的主要区别是信号的来源，即来自 CPU 外部，还是 CPU 内部。
    • 2. 中断向量表和中断优先级
      • 1) 中断向量表：为每种设备配以相应的中断处理程序，并把该程序的入口地址放在中断向量表中的一个表项，并为每一个设备的中断请求规定一个中断号，它直接对应于中断向量表的一个表项。当 I/O 设备发来中断请求信号时，由中断控制器确定该请求的中断号，并去查找中断向量表取得设备中断处理程序的入口地址，这样便可转入中断处理程序执行。
      • 2) 中断优先级：多个中断信号同时到达时，根据优先级分别先后处理。
    • 3. 对多中断源的处理方式
      • 1) 屏蔽(禁止)中断：类似于关中断，当处理机正在处理一个中断时，将屏蔽掉所有的中断，让它们等待。直到处理机处理完本次中断后，再去检查是否有中断发生。
      • 2) 嵌套中断：CPU 优先响应最高优先级的中断请求。高优先级的中断请求可以抢占正在运行的低优先级中断的处理机。
  • 6.3.2 中断处理程序
    • 中断处理程序是I/O系统中最低的一层，它是整个I/O系统的基础。
    • 中断机构的处理过程：
      • 1. CPU测定是否有未响应的中断信号。执行完当前指令后，处理机都要测试是否有未响应的中断信号。
      • 2. 保护被中断进程的CPU环境。
      • 3. 转入相应的设备处理程序。处理机对各个中断源进行测试，以确定引起本次中断的 I/O 设备，并向提供中断信号的设备发送确认信号。该设备收到确认信号后，立即取消它所发出的中断请求信号。然后将相应的设备中断处理程序的入口地址装入到程序计数器中。处理机运行时便自动地转向中断处理机程序。
      • 4. 中断处理。
      • 5. 恢复CPU现场并退出中断。
      • 5.中断处理程序的处理过程遵循什么步骤？
• 6.4 设备驱动程序
  • 6.4.1 设备驱动程序概述
    • 1. 设备驱动程序的功能
      • (1)接收由与设备无关的软件发来的命令和参数，并将命令中的抽象要求转换为与设备相关的低层操作序列。
      • (2)检查用户I/O请求的合法性，了解I/O设备的工作状态，传递与I/O设备操作有关的参数，设置设备的工作方式。
      • (3)发出I/O命令，如果设备空闲，便立即启动I/O设备，完成指定的I/O操作；如果设备忙碌，则将请求者的请求块挂在设备队列上等待。
      • (4)及时响应由设备控制器发来的中断请求，并根据其中断类型，调用相应的中断处理程序进行处理。
  • 6.4.2 设备驱动程序的处理过程
    • (1)将抽象的要求转化为具体的要求。如:将逻辑盘块号转换为具体的盘面、磁道和扇区
    • (2)检查I/O请求的合法性。如:打印机请求读, 以读方式打开磁盘后请求写
    • (3)读出并检查设备的状态。如:读并查状态是否为就绪, 确定启动控制器或等待
    • (4)传送必要的参数。如:启动磁盘, 先将字节数和内存起始地址送控制器
    • (5)工作方式的设置。如:异步通信, 先设置波特率、校验方式、停止位等
    • (6)启动I/O设备。向控制器发送控制命令, 将自己阻塞进入睡眠状态。由控制器控制下进行指定的I/O操作
    • (7)完成I/O后,设备控制器向CPU发出中断请求;CPU响应转向中断处理程序唤醒相应的设备驱动进程
  • 6.4.3 对I/O设备的控制方式
    • 对设备的控制，早期是使用轮询的可编程I/O方式，后来发展为使用中断的可编程I/O方式。
    • 1.使用轮询的可编程I/O方式
    • 2.使用中断的可编程I/O方式
    • 3.直接存储器访问方式
    • 4. 对I/O设备的控制方式有哪几种，分别是什么？
• 6.5 与设备无关的I/O软件
  • 6.5.1 与设备无关(Device Independence)软件的基本概念
    • 1. 以物理设备名使用设备
      • 在早期OS中，应用程序在使用I/O设备时，都使用设备的物理名称，这使应用程序与系统中的物理设备直接相关
    • 2. 引入了逻辑设备名
      • 为了实现与设备的无关性而引入了逻辑设备和物理设备两个概念。逻辑设备是抽象的设备名
    • 3. 逻辑设备名称到物理设备名称的转换
      • 在应用程序中，用逻辑设备名称使用设备虽然方便了用户，但系统却只识别物理设备名称，在实际执行时，还必须使用物理名称。系统中必须具有将逻辑设备名称转换为某物理设备名称的功能。
      • 同时，为了实现设备的无关性，系统采用了逻辑设备名，通过逻辑设备表LUT来实现逻辑设备名对物理设备名的映射。
  • 6.5.2 与设备无关的软件
    • 1.设备驱动程序的统一接口
    • 2.缓冲管理
    • 3.差错控制
    • 4.对独立设备的分配与回收
    • 5.独立于设备的逻辑数据块
    • 6. 在于设备无关的软件中，包括执行了所有设备公有操作的软件，试说明有哪些？
  • 6.5.3 设备分配
  • 6.5.4 逻辑设备名到物理设备名映射的实现
    • 1. 逻辑设备表LUT(Logical Unit Table)
      • 在逻辑设备表的每个表目中包含了三项：逻辑设备名、物理设备名和设备驱动程序的入口地址，如图所示。
    • 2. 逻辑设备表的设置问题
      • 在系统中可采取两种方式设置逻辑设备表
        • 第一种方式，是在整个系统中只设置一张LUT表。所有进程的设备分配均记录在一张表中，不允许在表中具有相同的逻辑设备名，在多用户环境下难以做到，主要用于单用户系统。
        • 第二种方式，是为每个用户设置一张LUT。此时由于多用户系统中都配置了系统设备表，则 LUT表格式如下。
• 6.6 用户层的I/O软件
  • 6.6.1 系统调用和库函数
    • 1. 系统调用
      • 一方面，为使诸进程能有条不紊地使用I/O设备，且能保护设备的安全性，不允许运行在用户态的应用进程去直接调用运行在核心态(系统态)的OS过程。但另一方面，应用进程在运行时，又必须取得OS所提供的服务，否则，应用程序几乎无法运行。
      • 为了解决此矛盾，OS在用户层中引入了一个中介过程——系统调用，应用程序可以通过它间接调用OS中的I/O过程，对I/O设备进行操作。
    • 2. 库函数
      • 在C语言以及UNIX系统中，系统调用(如read)与各系统调用所使用的库函数(如read)之间几乎是一一对应的。而微软定义了一套过程，称为Win32 API的应用程序接口(Application Program Interface)，程序员利用它们取得OS服务，该接口与实际的系统调用并不一一对应。
      • 用户程序通过调用对应的库函数使用系统调用，这些库函数与调用程序连接在一起，被嵌入在运行时装入内存的二进制程序中。
  • 6.6.2 假脱机(Spooling)系统
    • 将一台物理设备虚拟为多台逻辑设备，支持多个用户共享一台物理设备。
    • 1. 假脱机技术
      • 在20世纪50年代，为了缓和CPU的高速性与I/O设备低速性间的矛盾，而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，先将低速I/O设备上的数据传送到高速磁盘上，或者相反。
      • 系统利用多道程序中的一道程序，模拟脱机输入时的外围控制机功能，把低速 I/O 设备上的数据传送到高速磁盘上；再用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上。这样，便可在主机的直接控制下，实现脱机输入、输出功能。此时的外围操作与 CPU 对数据的处理同时进行，这种联机情况下实现的同时外围操作称为 SPOOLing，或称为假脱机操作。
• 6.7 缓冲区管理
  • 6.7.1 缓冲的引入
    • （1）缓和CPU和I/O设备间速度不匹配的矛盾。
    • （2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
    • （3）解决数据粒度不匹配的问题。
    • （4）提高CPU和I/O设备间的并行性。
    • 7.引入缓冲区的原因有什么？
  • 6.7.2 单缓冲区和双缓冲区
  • 6.7.3 环形缓冲期
  • 6.7.4 缓冲池(Buffer Pool)
• 6.8 磁盘存储器的性能和调度
  • 6.8.1 磁盘性能简述
  • 6.8.2 早期的磁盘调度算法
  • 6.8.3 基于扫描的磁盘调度算法

第七章 文件管理

• 7.1 文件和文件系统
  • 7.1.1 数据项、记录和文件
    • 现代OS计算机系统对系统中软件资源：无论是程序或数据、系统软件或应用软件都以文件方式来管理。
    • 1.数据项
      • ①基本数据项：用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位
      • ②组合数据项：由若干个基本数据项组成的，简称组项
      • 1.什么是数据项？
    • 2.记录
      • 记录是一组相关数据项的集合，用于描述一个对象某方面的属性。
    • 3.文件
      • 文件是指由创建者所定义的，具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件。文件属性包括文件类型、文件长度、文件的物理位置和文件的建立时间。
        • 2. 什么是文件？它的属性有哪些。
      • 文件是具有文件名的一组相关元素的集合
        • 有结构文件(又称记录式文件，文件由一组相似记录组成，如报考某学校的所有考生的报考信息记录)
        • 无结构文件(又称流式文件，被看成是一个字符流。比如一个二进制文件或字符文件)
  • 7.1.2 文件名和类型
    • 1.文件名和扩展名
      • (1)文件名：在不同系统之间，对文件名的规定是不同的，不同系统对文件名的长度、特殊字符、大小写有着不同的要求
      • (2)扩展名：扩展名是添加在文件名后面的若干个附加字符，又称后缀名，用于指示文件的类型
    • 2.文件类型
      • 1)按用途分类
        • (1)系统文件：这是指由系统软件构成的文件。大多数系统文件只允许用户调用，但不允许用户进行读写；有的系统文件不直接对用户开放
        • (2)用户文件：指由用户的源代码、目标文件、可执行文件或数据所构成的文件。用户将这些文件委托给系统保管
        • (3)库文件：由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用，但不允许修改
      • 2)按文件中的数据的形式分类
        • (1)源文件：指由源程序和数据构成的文件。通常，由终端或输入设备输入的源程序和数据形成的文件都属于源文件。它通常是由ASCII码或汉字所组成的
        • (2)目标文件：指把源程序经过编译程序编译过，但尚未经过链接程序链接的目标代码所构成的文件。后缀名为".obj"
        • (3)可执行文件：指把编译后所产生的目标代码经过链接程序链接后所形成的文件。后缀名为".exe"
      • 3)按存取控制属性分类
        • (1)只执行文件：这类文件只允许被核准的用户调用执行，不允许读写
        • (2)只读文件：这类文件只允许文件主及被核准的用户去读，不允许写
        • (3)读写文件：这类文件只允许文件主及被核准的用户去读或写
      • 4)按组织形式和处理方式分类
        • (1)普通文件：由ASCII码或二进制码组成的字符文件，一般用户建立的源程序文件、数据文件以及操作系统自身代码文件、实用程序等都是普通文件
        • (2)目录文件：由文件目录组成的文件，通过目录文件可以对其下属文件的信息进行检索，对其可执行的文件进行操作，与普通文件一样
        • (3)特殊文件：特指系统中的各类I/O设备，为了便于统一管理，系统将所有的I/O设备都视为文件，并按文件方式提供给用户使用
      • 3.试说明文件的几种分类方法。
  • 7.1.3 文件系统的层次结构
  • 7.1.4 文件操作
    • 1.最基本的文件操作
      • (1)创建文件：创建新文件时分配必要的外存空间和建立目录项
      • (2)删除文件：删除对应的目录项并回收所占用的存储空间
      • (3)读文件：根据文件名找到文件在外存的位置并提供一个指针用于文件的读操作
      • (4)写文件：根据文件名找到文件在外存的位置并提供一个指针用于文件的写操作
      • (5)设置文件的读/写位置：通过设置读/写指针的位置实现随机存取
      • 7.简述最基本的文件操作。
• 7.2 文件的逻辑结构
  • 7.2.1 文件逻辑结构的类型
  • 7.2.2 顺序文件(Sequential File)
  • 7.2.3 记录寻址
  • 7.2.4 索引文件(Index File)
  • 7.2.5 索引顺序文件(Index Sequential File)
  • 7.2.6 直接文件和哈希文件
    • 1.直接文件
      • (1)直接文件可根据给定的关键字直接获得指定记录的物理地址。即关键字本身就决定了记录的物理地址。
    • 2.哈希(Hash)文件
      • (2)哈希文件利用Hash函数（或称散列函数）可将关键字转换为相应记录的地址。
    • 5. 试说明直接文件和哈希文件？
• 7.3 文件目录
  • 6.目录管理有什么要求？
    • 实现“按名存取”
    • 提高对目录的检索速度
    • 文件共享：允许多个用户共享一个文件
    • 允许文件重名
  • 7.3.1 文件控制快和索引结点
  • 7.3.2 简单的文件目录
  • 7.3.3 树形结构目录(Tree-Structured Directory)
  • 7.3.4 目录查询技术
• 7.4 文件共享
  • 7.4.1 基于有向无循环图DAG(Directed Acyclic Graph)
  • 7.4.2 利用符号链接实现文件共享
• 7.5 文件保护
  • 4.为了确保文件系统的安全性，可采取什么措施？
    • （1）通过存取控制机制，防止有人为因素所造成的文件不安全性。
    • （2）采取系统容错技术，防止系统部分的故障所造成的文件的不安全性。
    • （3）建立后备系统，防止由自然因素所造成的不安全性。
  • 7.5.1 保护域(Protection Domain)
  • 7.5.2 访问矩阵
  • 7.5.3 访问矩阵的修改
  • 7.5.4 访问矩阵的实现

第八章 磁盘存储器管理

• 8.1 外存的组织方式
• 8.2 文件存储空间的管理
• 8.3 提高磁盘I/O速度的途径
• 8.4 提高磁盘可靠性的技术
• 8.5 数据一致性的控制