操作系统（第3版）罗宇等编著 的学习笔记。

第一章：绪论

1.1 什么是操作系统

• 操作系统是一种系统软件，是软、硬资源的控制中心，它以尽量合理有效的方法组织单个或多个用户以多任务方式共享计算机的各种资源。

• 命令解释器都是必不可少的一个程序，用户通过它来使用计算机系统

• 其他的操作系统内核层之上的程序则是根据计算机的定位（服务器或工作站）而选择安装的。如果将计算机定位成程序开发用的工作站，那么用户必须安装编辑器进行程序编辑，并安装编译器进行程序编译。如果把计算机作为一个网络上的Web服务器，那么必须安装Web服务器程序。

• 它提供一组称为系统调用的接口，供上层程序调用，从而保证操作系统内核在特殊保护状态下运行的需求，并且满足上层程序对系统资源的申请、使用、释放以及进程的创建、结束等诸多功能的需求。

• 系统提供这些库程序是为了方便用户编程，用户不必为了实现一个通用的功能再重写上述库程序代码，而只要引用库程序中的函数即可。

• 系统调用与普通函数调用相似，可以看成是特殊的公共子程序，因为这些程序提供了一些可以被任意用户层程序调用的公共功能，所以用户不需要再编写实现这些功能的程序，只要调用操作系统内核提供的相应“系统调用”即可。

• 文件操作以操作系统内核系统调用形式实现。

• 处理机提供程序执行能力；主存、辅存提供程序和数据的存储能力；终端设备提供人机交互能力；网络设备提供机间通信能力。

• 操作系统要合理调度多用户任务使用处理机。

• 针对不同资源特点，资源管理包含两种资源共享使用的方法：“时分”和“空分”。

  • 时分就是由多个用户进程分时地使用该资源
  • 空分是针对存储资源而言，存储资源的空间可以被多个用户进程共同以分割的方式占用。

• **独占式使用。**独占表示某用户任务占用该资源后，执行对资源的多个操作，使用一个完整的周期。

• **分时式共享使用。**这种共享使用是指用户任务占用该资源无需使用一个逻辑上的完整周期。

• 进程是指运行当中的程序，也就是指程序针对于某一数据集合的执行过程。

• 操作系统为用户提供进程创建和结束等的系统调用功能，使用户能够创建新进程以运行新的程序。

1.2 操作系统的发展历史

• 所谓作业（Job），是用户在一次上机活动中要求计算机系统所做的一系列工作的集合。

• 人们将机器指令分为**“普通指令”和“特权指令”**，并且引入了“模式/态（Mode）”的概念。把有关I/O的指令、对特殊寄存器的访问等列为特权指令，并且规定只有监督程序才有权执行特权指令，用户程序则只能执行普通指令。

• 监督程序所在的存储空间称为**“系统空间”，用户程序所在的存储空间称为“用户空间”**。

• 用户程序执行时若碰到定时器中断，则无条件进入监督程序。监督程序根据当前作业说明（或规定）的“最大运行时间”值来判断该程序是否进入了“死循环”，从而可以有效地防止某个用户程序长期垄断系统处理机的现象。

• 通道是指专门用来控制I/O的硬件装置，可以实现外设与主存直接交换数据，在相当长的时间里不用打扰CPU

• 多道程序设计技术的基本思想是，在主存同时保持多道程序（作业），主机（对于单CPU系统，书中如没有特殊说明则都是单CPU系统）以交替方式同时处理多道程序。多道程序设计系统的出现标志着操作系统的形成。

• 操作系统的最基本特征如下：
  ① 并发（Concurrent）机制，用以支持多道程序设计技术。
  ② 共享（Sharing）机制，控制各种并发活动正确共享系统软、硬资源。

• 将交互式系统与多道程序设计系统相结合便形成了分时系统。

  • 分时系统中，一台计算机与多台终端相连接，用户通过各自的终端和终端命令以交互方式使用计算机系统。
  • 系统规定一个被称为**“时间片”**的时间单位，所有终端用户轮流享用一个时间片的CPU时间

• 分时系统的基本特点如下：
  ① 并发性。系统能协调多个终端用户同时使用计算机系统（即系统内部具有并发机制），能控制多道程序同时运行。
  ② 共享性。对资源而言，系统在宏观上使各终端用户共享计算机系统的各种资源，而在微观上它们则分时使用这些资源。
  ③ 交互性。对系统和用户双方而言，人与计算机系统以对话方式进行工作。
  ④ 独立性。对用户而言，系统能使用户有一种只有他自己在使用计算机的感觉。

• 计算机系统能对用户的服务请求及时做出回答，并能及时修改、处理系统中的数据。这类应用被称为**“实时事务处理”**。实时系统应能及时地响应外部事件的请求并在严格规定的时间内完成对该事件的处理，控制实时设备和实时任务协调一致地运行。

• 实时系统的主要特征和功能如下：
  ① 时钟分辨度高。有更高的时钟中断频度，可实现更精确计时，可以更加频繁地进入操作系统“处理机调度程序”运行，保证实时任务及时占用处理机，以此保证实时任务的快速响应。
  ② 支持可剥夺任务调度。保证实时任务无条件剥夺非实时任务运行，不会让非实时任务耽误实时任务。
  ③ 多级中断机制。保证实时任务对应的事件中断为高级

• 多机操作系统以支持并行多任务为其主要特征，充分发挥计算机中多处理机并行处理的优势，在科学计算及高端事务处理服务器领域占有重要地位。

1.3 主要操作系统介绍

• 自由软件可免费提供给任何用户使用，也包括用于商业目的；并且自由软件的所有源程序代码也是公开的，可免费得到。

• 引入SPOOLing技术的硬件基础是什么？

  通道

第二章：操作系统运行机制与用户界面

• 操作系统的主要功能就是管理CPU、主存、I/O设备及文件，并提供支持程序并发运行的机制。

2.1 中断和异常

• CPU在运行上层程序时唯一能进入内核程序运行的途径就是通过中断或异常。

• 异常表示CPU执行指令时本身出现算术溢出、零做除数、取数时发生奇偶错、访存指令越界，或执行了一条所谓“陷入指令trap”等情况，这时也可以中断当前的执行流程，转到相应的错误处理程序或陷入处理程序。陷入指令（也称自陷指令或访管指令）的出现，是为了使得用户模式下运行的程序可以调用操作系统内核程序。异常只是一种特殊的程序调用，特殊在于处理机状态从“用户模式”变成了“监督模式”。

• **中断（Interruption），也称外中断。**指来自CPU执行指令以外的事件发生。每个不同中断具有不同的中断优先级，表示事件的紧急程度。在处理高级中断时，低级中断可以被临时屏蔽。

• 异常（Exception），也称内中断、例外或陷入（Trap）。指源自CPU执行指令内部的事件。异常不能被屏蔽，一旦出现应立即处理。

• 为了区分和不丢失每个中断信号，通常用一些固定的触发器来寄存它们，并规定其值为1时表示有中断信号，其值为0时表示无中断信号。这些寄存中断的触发器称为**“中断寄存器”**。

• 把中断享有的高、低不同的响应权利称为中断优先级。

• **“中断屏蔽”**通常是指禁止响应中断

• CPU执行指令产生异常，如执行非法指令、自陷指令（Trap指令）时不能被屏蔽，必须马上响应处理。

2.2 中断/异常响应和处理

• 该机构能够在每条机器指令执行周期内的最后时刻扫描中断寄存器，“询问”是否有中断信号。若无中断信号或被屏蔽，CPU继续执行程序的后续指令，否则CPU停止执行当前程序的后续指令，无条件地转入操作系统内核的中断处理程序，这一过程称为中断响应。

• 异常是在执行指令的时候，由指令本身的原因发生的，指令的实现逻辑发现异常发生则转入操作系统内核的异常处理程序。

• 一般情况下，断点应为中断的那一瞬间程序计数器（PC寄存器）所指指令的前一条指令地址，即中断发生时正在执行的那一条指令的地址。中断时程序计数器所指的地址（即断点的逻辑后续指令）称为“恢复点”。

• 现场信息，是指中断那一时刻确保程序继续运行的有关信息，如程序计数器、通用寄存器及一些与程序运行相关的特殊寄存器中的内容。

• 中断和异常的处理程序是操作系统内核程序，都必须在一种特权状态下运行，因为这些程序需要访问外设等操作系统管理的资源或者涉及系统的管理表格。

• 因此，将CPU的运行状态分为核心态和用户态（等同于以前所述的监督模式和用户模式），操作系统内核程序在核心态下运行，允许在核心态下运行的程序执行所有的指令（包括特权指令）；而外层所有程序在用户态下运行，特权指令一般不允许在用户态下执行。

• 当用户程序需要操作系统为之服务时，绝对不能通过通常的程序调用方式来调用操作系统的相应程序，而必须设法通过执行自陷指令（系统调用）引起一次异常而转入操作系统内核的相应程序。

• 也有人把核心态称为管态、系统状态、监督方式，将用户态称为目态、用户状态或用户方式等。

• Intel x86处理机运行状态有0，1，2，3环之分，不过Intel x86上运行的操作系统（如Linux和Windows）只用到0环和3环，0环表示核心态，3环表示用户态。

• 通常将这片存放中断/异常处理程序入口地址的主存单元称为中断/异常向量，或系统控制块。

• PS(process state)寄存器描述CPU的执行状态，主要包含处理机当前运行态、处理机优先级、屏蔽外中断否等标志位。

• 当响应中断/异常时，硬件先把当前PS和PC(process counter)寄存器的内容作为程序现场保存起来，然后从中断/异常向量的相应单元取出新的PS和PC值，并装入到PS和PC寄存器。CPU便根据新装入的PC的内容转去进行中断/异常处理。

• 中断/异常处理中，一般包括保存现场、分析中断/异常原因、进入相应的中断/异常处理程序、重新选择程序（进程）运行、恢复现场等过程

• 中断/异常发生后，硬件机构自动地进入响应中断/异常的过程——交换PS和PC，具体步骤如下：
  ① 硬件机构自动将PS和PC寄存器的内容存入CPU的暂存寄存器中。
  ② 根据发生的中断/异常，硬件从指定的中断/异常向量单元中取出新的PS和PC内容，分别装入PS和PC寄存器。
  ③ 硬件将保留在内部寄存器中的原PS值和PC值的作为现场信息保存到与被中断程序相关的栈中，这里的栈用于保护原来运行程序的现场。

• 对于不同的中断，硬件将转入不同的中断入口程序。对于所有的异常则首先转入公共的入口程序。

• 高级中断能够打断低级中断的处理，待高级中断处理结束后，再返回低级中断处理。为了不丢失低级中断的现场信息，显然应该用栈结构保存现场。

• 用户态程序，则退出中断/异常以前应先考虑进行一次调度选择（运行进程调度程序），以挑选更适合在当前情况下运行的新程序（进程）。这是因为，原来被中断的用户程序在此次中断/异常处理过程中，可能由于其要等待的事件没有发生而不具备继续运行的条件；也可能被降低了运行的优先权；还可能由于此次中断/异常的处理使得其他程序获得了比其更高的运行优先权

2.3 操作系统运行模型

• 操作系统通常都包含进程管理、存储管理、外设管理、文件管理等主要功能模块，还需要提供支持用户使用计算机的命令解释程序。

• 进程管理模块包含有关进程的系统调用处理，如进程创建和结束、进程通信及进程同步等，也包含对处理机的分时使用程序，如进程调度和进程切换。

• 进程空间分配程序也划分到存储管理模块中

• 内核程序作为一个特殊进程运行，它的并发运行实现起来很困难。当一个I/O请求发给外设后，外设进行I/O需要一定的时间，内核因此而阻塞，处理机去运行别的进程，而别的进程就不可再激活内核程序了。

2.4 系统调用

• 系统调用是操作系统内核和用户态运行程序之间的接口。所谓系统调用，可以看成是用户程序（或用户态运行的系统程序）在程序一级请求操作系统为之服务的一种手段

• 大部分的机器都提供一条能产生异常的机器指令，称为**“自陷指令”，或陷入指令，或访管指令**。

• 为了方便高级语言程序使用系统调用，通常提供一个系统调用库，其中包含许多系统调用接口函数，这些函数看上去就是一些普通的子程序，但是这些函数往往是由为数不多的几条汇编指令实现的，而且必须要包含一条trap指令，这样才能保证在执行trap指令时将处理机控制转移至操作系统内核的相应程序。

• 用户只要按子程序调用格式写语句，编译器在编译子程序时，会将用户子程序调用语句中的参数放入约定好的寄存器中，生成指令并从约定好的寄存器或栈中取参数。

第三章：进程与处理机管理

• 用户希望一个作业步中的程序还能够同时在多个处理机上运行，因此进程的机制得到了进一步发展，即让一个进程同时拥有多个线程，让多个线程在不同处理机上同时运行。

• 如何把处理机合理有效地分配给各执行程序使用是处理机管理的主要内容。

• 引入线程的目的是为了支持进程中程序执行的并发。

3.1 进程描述

• 程序以进程方式使用系统资源，包括程序和数据所用的空间、系统外设、文件等程序运行所需的系统资源，并且以分时共享的方式使用处理机资源。

• 把操作系统看成支持进程并且对进程所用系统资源进行管理的系统。

• 进程是支持程序执行的机制。进程可以理解为程序对数据或请求的处理过程。

• 进程由以下4方面组成：
  ① 进程包括至少一个可执行程序，含有代码和初始数据，一般在进程创建时说明。注意，可执行程序可以被多个进程共享，换句话说，多个进程可能运行同一个可执行程序。
  ② 进程包括一个独立的进程用户空间，在进程创建时由操作系统分配。
  ③ 进程包括系统资源。这是指在进程创建及执行过程中，由操作系统分配给进程的系统资源，包括I/O设备、文件等。
  ④ 进程包括一个执行栈区，包含运行现场信息，如子程序调用时所压栈帧，系统调用时所压的栈帧等，这是进程运行及进程调度进行处理机切换时所要涉及的数据结构。

• 在进程运行过程中，操作系统不断地将系统资源以独占方式或者与其他进程共享的方式分配给进程。

• 系统还会为进程在操作系统核心空间分配一个核心栈，用来保存中断/异常点现场，以及在进程运行核态程序后的转子现场。逻辑上，进程的用户栈和核心栈都属于一个执行栈区。

• 同一个程序可以由多个进程分别执行，当然，不同的进程虽然执行的是相同的程序，但是处理不同的数据，这种程序被称为共享程序。

• 任何一个程序，逻辑上都可以将其分为两部分：执行过程中不改变自身的不变部分和工作区、变量等可变部分。

• 我们把程序、数据、栈的集合称作进程映像（Process Image）

• 初始化进程空间是指将辅助存储器中的可执行程序文件中的程序加载到进程空间，并依照可执行程序文件中局部变量、全局变量的数据说明，分配进程的数据区空间并对其初始化，还要分配好栈区。

• 进程控制块（Process Control Block，PCB）。它描述进程标识、空间、运行状态、资源使用等信息。在进程控制块中存放的标识信息主要有本进程的标识、本进程的产生者标识（父进程标识）、进程所属的用户标识。逻辑上说，进程运行栈属于进程控制块。进程控制块一定要有栈的地址。

• 包含中断是否开放、处理机执行态等状态信息的寄存器，通常称为处理机状态字（PSW）

• 进程标识符是一个数字式的系统内码，通过它可以建立其他表格与进程控制块之间的联系。

• 同一用户的所有进程配合完成用户的上机意图。

• 进程控制块中的链接指针可以把有相同特性的进程控制块链接起来，

• 进程控制块是操作系统中最重要的数据结构，每个进程控制块都包含操作系统所需的进程信息。

• 进程控制块的集合定义了操作系统的状态。

• 对所有公共数据结构都存在这样一个问题，用户往往把对该公共数据结构的规范操作集中在一个例程中，这称为管程设计方法。

3.2 进程状态

• 要做到程序的并发执行，操作系统必须能使不同进程中的程序占用处理机运行，所以一个进程在从创建到结束的生命期内会占用处理机，也会从处理机上下来让别的进程去运行。

• 通过改变程序计数器PC的值来改变指令的执行次序。程序计数器可以从一个应用程序的代码段改变到另一个应用程序的代码段，这也是处理机进程切换所要做的事情。

• 一般的进程都要经历创建、断断续续运行、最后结束的过程。

• 在需要时，一个进程可以创建一个新的进程，被创建的进程称为子进程，创建者进程称为父进程。

• 进程结束处理主要是释放进程所占用的系统资源，进行有关信息的统计工作，理顺本进程结束后其他相关进程的关系，最后调用进程调度程序选取高优先级就绪进程来运行。

• 运行状态（Running）：一个进程正在处理机上运行。在单机环境下，每一时刻最多只有一个进程处于运行状态。

• 就绪状态（Ready）：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行，称此进程处于就绪状态。

• 等待状态，又称阻塞状态（Blocked）：一个进程正在等待某一事件而暂停运行，如等待某一资源成为可用或等待I/O完成。

• **系统按进程优先级数设立几个就绪进程队列，同一优先级进程在同一队列中。**系统先取最高优先级的队列队首进程占用处理机，当时间片到时往往重新计算优先级挂回相应就绪队列中。当要等事件时，将其挂到相应的事件等待队列中。如果某个事件发生，系统从相应等待队列中选取队首进程并重新计算优先级挂到就绪队列中。

• 为了能使处于等待状态的进程释放主存空间，系统将其交换到辅存上，这时进程便处在挂起状态。处于挂起状态的进程意味着没有占用任何主存。当等待并挂起的进程等待的事件发生时**，进程状态从等待挂起转化到就绪挂起。**

• 当操作系统选取进程进行交换时，一个高优先级的就绪挂起状态的进程可以被解挂，即将该进程映像从外部存储器调入主存，这时该进程从就绪挂起变成就绪状态。

3.3 进程控制与调度

• 特权态又称核心态、系统态或监督模式，操作系统内核程序在这种模式下运行。

• 如果操作系统提供某种手段能将指定物理空间映射到用户（虚存）空间，那么不但能实现用户态的I/O驱动程序，而且还能用高级语言实现I/O操作，这是因为I/O操作与一般读/写指令格式一致，所不同的只是地址范围不一样。

• 划分特权与非特权态的理由是，保护操作系统和操作系统的数据表格不被可能出错的用户程序破坏。

• 进程既为运行用户程序而创建，又会在用户自陷或外部中断时去运行操作系统内核程序。当进程运行系统内核程序时，系统只是保存了用户程序的运行现场，包括所有处理机状态、现场信息，保留原用户程序使用的栈不被核心态程序使用。当核心程序运行时，系统使用为该进程分配的核心栈空间，这样当核心程序调用子程序或被中断时，可以利用核心栈保存现场。

• 进程切换是指处理机从一个进程的运行转到另一个进程上运行。进程切换与处理机模式切换不同，当模式切换时，处理机逻辑上还在同一进程中运行。而进程切换指处理机转入另一个进程运行。

• 提高处理机的利用率及改善系统响应时间、吞吐率（单位时间完成的作业量），在很大程度上取决于进程调度性能的好坏。

• 调度就是选择。

• 必须按照一定的原则选择进程（或请求）来占用资源，这就是调度。选择进程占用处理机称为进程调度；选择磁盘请求进行磁盘I/O称为磁盘调度

• 作业一旦被高级调度选中，相应的进程及进程组才会产生，其他系统资源才有可能被占用。

• 中级调度可以控制进程对主存的使用。

• 低级调度决定处在就绪状态中的哪个进程将获得处理机。通常所说的进程调度就是指低级调度。

• 非剥夺方式。在这种方式下，一旦分派程序把处理机分配给某进程后，便让它一直运行下去，直到进程完成或发生某事件（如提出I/O请求）而阻塞时，才把处理机分配给另一进程。

• 剥夺方式。在这种方式下，某个进程正在运行时可以被系统以某种原则剥夺已分配给它的处理机，将处理机分配给其他进程。

• 进程调度和切换程序是操作系统内核程序。

• 进程在操作系统内核程序临界区中不应该被切换。在运行用户程序的进程自陷进入操作系统后，如果进入临界区，需要独占式访问共享数据，理论上必须加锁，以防其他并行程序进入。在加锁后到解锁前不应切换到其他进程运行，以加快该共享数据的释放。

• 其他需要完全屏敝中断的原子操作过程，像加锁、解锁、中断现场保护、恢复等原子操作。在原子操作过程中，连中断都要屏蔽，更不应该进行进程调度与切换。

• 进程调度就是选择进程占用处理机。

• 先来先服务调度算法属于不可剥夺算法。

• 按照进程的优先级大小来调度，使高优先级进程优先得到处理机的调度称为优先级调度算法。

• 一个进程的优先级不是固定的，往往随许多因素的变化而变化，尤其随进程的等待时间、已使用的处理机时间或其他资源的使用情况而定。

• 时间片轮转算法也多用于进程调度，采用此算法的系统其进程就绪队列往往按进程到达的时间来排序。

• 按照先来先服务原则调度，但进程占有处理机仅一个时间片，在使用完一个时间片后，进程还没有完成其运行，它也必须释放（被剥夺）处理机给下一个就绪的进程。

• 短进程优先调度算法从进程的就绪队列中挑选那些所需运行时间（估计时间）最短的进程进入主存运行。

• 当后续短进程过多时，大进程可能没有机会运行，导致饿死。

• 让“进程运行到完成时所需的运行时间最短”的进程优先得到处理

• 最短剩余时间优先算法允许被一个新进入系统的且其运行时间少于当前运行进程的剩余运行时间的进程所抢占。

• 按照此算法每个进程都有一个优先数，该优先数不但是要求的服务时间的函数，而且是该进程得到服务所花费的等待时间的函数。

• 可以看出，“等待时间＋要求的服务时间”是系统对作业的响应时间，所以优先数公式中，优先数值实际上也是响应时间与服务时间的比值，称为响应比。响应比高者得到优先调度。

• 优先级最高的第1级队列中的进程的时间片最小，随着队列级别的增加，其进程的优先级降低了，但时间片却增加了。通常下放一级，其时间片增加1倍。各级队列均按先来先服务原则排序。

• 当前面各级队列皆为空时，才调度最后第n级队列中的进程。第n级（最低级）队列中的进程采用时间片轮转算法进行调度。当比运行进程更高级别的队列到来一个新的进程时，它将抢占运行进程的处理机，而被抢占的进程回到原队列的末尾。

3.4 作业与进程的关系

• 进程是系统资源的使用者，系统的资源大部分都是以进程为单位分配的。

• 通常把用户要计算机完成的这一串任务称为作业。

• 作业是用户向计算机提交的相关任务的集合，而进程则是具体完成用户任务的运行实体，分配计算机资源的基本单位。

• 一个作业就动态地转换成了一组运行实体——进程族。

• 对于每一条终端命令，可以创建一个子进程去具体执行。

3.5 线程的引入

• 引入进程后，系统资源，特别是CPU的分配单位变成了进程，原来由一个作业完成的用户任务通过系统中多个进程来实现，一个进程代表了一个作业步，因为进程可以并发地占用CPU运行，因此实现了同一个作业中不同作业步的并发。

• 引入进程是为了实现作业步的并发执行

• 如果要进行进程间数据交换，则需要操作系统中系统调用的支持，操作系统必须提供相应的进程间通信的系统调用来完成进程间数据交换的任务，这样会给编程带来困难。

• 让完成同一作业的进程共享一片存储空间，但是进程独立作为CPU的调度单位占用处理机。

• 在一个进程中可以包含多个可以并发（并行）执行的线程。

• 系统按进程分配所有除CPU以外的系统资源（如主存、外设、文件等），而程序则依赖于线程运行，系统按线程分配CPU资源，引入线程后，进程概念内涵改变了，进程只作为除CPU以外系统资源的分配单位。

• 这些线程共享程序区和数据区，但是它们有各自的运行栈区，可以被独立地调度占用CPU并行或并发地运行。

• 当进程内所有的线程结束时，意味着进程结束，从而释放进程所占用的所有资源。

• 在进程内，每个线程可以运行进程程序区的不同子程序或相同的可再入子程序，它们处理着不同的用户原始数据，或处理着不同的外来请求。

3.6 小结

• 程序、数据、用户栈的集合称为进程映像（Process Image）。

• 为了实现进程间空间共享而引入轻权进程；为了实现进程内的程序并发（并行）运行而引入线程。

• 进程成为资源（除CPU以外）分配单位，线程则是处理机分配单位。

第四章：进程同步与通信、进程死锁

• 并发（分时占用处理机）或并行（同时占用不同处理机）运行的

• 访问共享资源或数据时会引发一种互斥关系，以满足各进程不同时使用共享资源或数据的要求。

• 一个进程需要向另一个进程传递数据，也就是说，后面的进程必须等待前面进程的数据到达才能继续运行，这是一种进程间的次序关系，我们又叫它同步。

• 对资源不加限制地分配可能导致进程间由于竞争资源而相互等待，以至无法继续运行，人们把这种局面称为死锁（Deadlock）

4.1 并发执行的实现

• 没有次序关系的子任务之间可以并发执行。

• 一般情况下，并发程序设计语言可以从顺序程序设计语言增加并发语句成分改造而来，但一些新的语言，在设计的时候就已经考虑了对并发程序设计的支持。

• 如果用户用并行程序设计语言编写并行程序，编译系统在对该程序进行编译时，会将程序中的并发语句转化为对操作系统相关系统调用函数的调用，动态地创建一组进程或线程来执行该程序。

4.2 进程的同步与互斥

• 同步关系（或称直接制约关系）。指为完成用户任务的伙伴进程间，因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

• 互斥关系（或称间接制约关系）。即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系，如进程间因争夺打印机设备而导致一方须待另一方使用结束后方可使用。

• 临界段（Critical Section）问题的实质是进程互斥使用资源问题。

• 因为同一个程序在相同数据上的多次执行可能产生不一样的结果，所以这两个进程的并发执行是不能保证确定性的。

• 让任一个进程在它需要进入的时候进入相应的临界段，而其间排斥另一个进程也进入相应的临界段，这样就可以避免临界段问题。

• 临界资源（Critical Resource，CR）：一次仅允许一个进程使用（必须互斥使用）的资源。如独占型硬件资源，可以由多进程访问的变量、表格、队列、栈、文件等软件资源。

• 临界段（Critical Section，CS）：是指各进程必须互斥执行的那种程序段，该程序段实施对临界资源的操作。

• 在一个多道程序的单处理机系统中，中断会引起多进程并发执行，因为中断处理结束会引起调度程序运行。如果某进程在临界段中发生中断，随着上下文切换，会保存被中断进程寄存器状态，然后调度另外的进程运行，另一个进程如果再进入相关临界段，会修改它们的共享数据，如果再次进行进程切换，原先进程重新执行时，使用了原来保存的寄存器中的不一致的数据，导致错误。如果程序员意识到中断引起的并发能够导致错误的结果，可考虑在程序执行临界段部分的处理时，屏蔽中断。

• 1965年，Dijkstra提出了一种称为信号量（Semaphore）的同步互斥工具，通常称为信号量机制。信号量机制是一种功能较强的机制，可用来解决互斥与同步问题。

• 信号量机制由“信号量”和“P操作、V操作”两部分组成。

• 原语（Primitive）是指完成某种功能且不被分割、不被中断执行的操作序列。有时也称原子操作

• 信号量机制能解决n个进程的临界段问题。n个进程共享一个公共信号量mutex，其初值为1。

• “忙等待”（busy-waiting）现象。即如果某一个进程正在执行其临界段，其他欲进入临界段的进程均须在它们的entry code中连续地循环等待（如执行while(condition);语句等）。

• 某个进程执行P操作过程中，若发现信号量的状态不允许其立即进入临界段，则P操作应使该进程放弃CPU而进入约定的等待队列（调用系统函数block()）。当某个进程执行V操作时，如果在该信号量上有被阻塞的等待进程，则V操作负责将其唤醒（调用系统函数wakeup()）。

• 管程的互斥功能由编译器利用底层同步/互斥机制来实现。

• 把分散的临界段集中起来管理，并把共享资源用数据结构抽象地表示出来，由于临界段是访问共享资源的代码段，所以由一个“秘书”程序管理到来的访问。“秘书”每次只让一个进程来访，这样既便于对共享资源的管理，又能实现互斥访问。在后来的实现中，“秘书”程序更名为管程。

• 任一时刻管程中只能有一个活跃进程

• 对所有生产者和消费者进程来说，把缓冲池看成一个整体，因此缓冲池是临界资源，即任何一个进程在对池中某个缓冲区进行“存”或“取”操作时须和其他进程互斥执行。

• 在对这些计数变量操作时也要保证互斥操作

• 只需保证任何一个Writer进程能与其他进程互斥访问共享数据即可

• “Reader优先”

• “Writer优先”

4.3 消息传递原理

• 进程之间交换信息被称为进程间通信。

• 要想让两个用户进程共享空间必须通过特殊的系统调用来实现，而进程内的线程是自然共享进程空间的。

• 消息传递（Message Passing）方法。消息传递的主要思想是：系统提供发送消息Send()与接收消息Receive()两个原语，进程间通过使用这两个原语进行数据交换。

• 一种方法是设立一个通信参与者共享的逻辑实体，如信箱，发送者只是向信箱发送消息，接收者从信箱取消息。这种方法又称为间接通信方法。

• 另一种方法是直接以接收者进程内部标识为目的地标识发送消息，这种方法又称为直接通信方法。

• 消息传递常常作为进程同步的手段。

• 管道实质上是一种空间有限信息流的缓冲机制，它连接发送进程与接收进程，以实现它们之间的数据通信。

• 管道不同于一般的消息缓冲机制，它以FIFO方式组织字节流数据的传输，并保证进程间同步执行，即当管道中无数据时，接收进程等待；当管道缓冲区满时，发送进程等待。

• 进程对通信机制的使用应该是互斥的。进程正在使用管道写入或读取数据时，另外的进程必须等待，等待锁被释放。

• 叫做write阻塞。反之，当读进程读空管道时，要出现read阻塞，读进程应睡眠，直到写进程唤醒它。

4.4 死锁

• 对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以致无法继续运行，这就是死锁（Deadlock）。

• 进程是因相互竞争资源而导致死锁的

• 死锁定义：在一个进程集合中，若每个进程都在等待某些释放资源事件的发生，而这些事件又必须由这个进程集合中的某些进程来产生，就称该进程集合处于死锁状态。

• 条件1：互斥。在出现死锁的系统中，必须存在需要互斥使用的资源。

• 条件2：占有等待。在出现死锁的系统中，一定有已分配到了某些资源且在等待另外资源的进程。

• 条件3：非剥夺。在出现死锁的系统中，一定有不可剥夺使用的资源。

• 条件4：循环等待。

• 循环等待只是死锁的必要条件。

• 死锁的必要条件4（循环等待）与资源分配图中含有的圈是等价的。系统中出现死锁，则资源分配图中必有圈，但资源分配图中有圈并不一定有死锁。

• 资源分配图含圈而系统又不一定有死锁的原因是，同类资源数大于1，若系统中每类资源都只有1个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。

• 解决死锁问题一般采用两类方法：一类是设计无死锁的系统；另一类是允许系统出现死锁，并在发现死锁后排除。

• 锁主要研究死锁防止、死锁避免、死锁检测及死锁恢复。

• 只要有一个必要条件不成立，系统就能保证不出现死锁，这是死锁防止的理论基础。

• 方法一 使进程申请到了它所需要的所有资源后才能开始运行。在运行过程中进程只需要释放资源，不需要申请资源。这种方法又称资源预分配法。

• 方法二 在进程提出申请资源前，必须释放已占有的一切资源。

• 在进程主动释放占有的资源前允许资源管理者剥夺进程所占有的资源，也能保证系统不出现死锁。

• 采用资源顺序分配法可以破坏循环等待条件。

• 进程只能按序号由小到大顺序申请资源。

• 保证系统杜绝死锁的方法（被称为银行家算法）

• 死锁避免正是通过确保系统随时处于安全状态来防止死锁的。

• 设系统中有n个进程，若存在一个序列（P1，P2，…，Pn），使得Pi（i＝1，2，…，n）以后还需要的资源可以通过系统现有空闲资源加上所有Pj(j＜i)已占有的资源来满足，则称此时这个系统处于安全状态。序列（P1，P2，…，Pn）被称为安全序列。

• 银行家算法是以系统中只有一类资源为背景的死锁避免算法。1969年，Haberman将银行家算法推广到多类资源环境中，形成了现在的死锁避免算法。其数据结构如下所述：

• 可以采用化简资源分配图的方法来检测系统中有无进程处于死锁状态。资源分配图的简化过程如下：

• 系统中有死锁的充分必要条件是，资源分配图不可完全化简。经过化简后，非孤立点的进程处于死锁状态

• 将①，②，③，④类资源编号为1, 2, 3, 4，可按编号递增次序申请资源。对第1, 4两类资源采用预分配法；对第2类采用剥夺法；对第3类采用死锁避免法。而对那些哪种方法也不适合的资源，可用死锁检测程序定期对系统进行检测，发现死锁后再排除死锁。

4.5 小结

• 进程同步关系是指协调完成同一任务的进程之间需要在某些位置上相互等待的直接制约关系；进程互斥关系指进程间共享独占型资源而必须互斥执行的间接制约关系，互斥问题也称临界段问题。

• 信号量机制作为同步互斥工具是理想的，但它难以作为进程通信工具。消息传递是目前广泛采用的理想通信工具，它不仅能方便地用于传输消息，而且也能用于解决各种同步互斥问题。

• 出现死锁时，系统必然满足4个条件：互斥、占有等待、非剥夺和循环等待。

第五章 存储管理

• 当前计算机都是基于冯·偌依曼存储程序式的计算机，程序和数据在运行和使用时都需要存放在主存中。

• “取”是研究该将哪个进程（或进程的某些部分）从辅存调入主存。调入进程占用主存或有资格占用主存是中级调度的工作。

• “放”则是研究将“取”来的某进程（或进程的某部分）按何种方式放在主存的什么地方。

• “替换”是研究将哪个进程（或进程的某部分）暂时从主存移到辅存，以腾出主存空间供其他进程（或进程的某部分）占用。

5.1 连续空间分配

• 应将用户程序的执行严格控制在用户区域中。这种存储保护的控制措施主要是通过硬件提供的界地址寄存器和越界检查机制来实现的。

• 经常活跃的部分放在固定区，其余部分按调用关系分段。首先将那些即将要用的段放在覆盖区，其他段放在辅存，在需要调用前用户安排特定系统调用将其调入覆盖区，替换覆盖区中原有的段。

• 交换的基本思想是，把处于等待状态（或在CPU调度原则下被剥夺运行权利）的作业从主存移到辅存，这一过程叫做换出；把准备好竞争CPU运行的作业从辅存移到主存，这一过程称为换入。

• 一种是上、下界寄存器和地址检查机制；另一种是基址寄存器、长度寄存器和动态地址转换机制。

• 动态地址转换机制指当用户程序运行时，每访问一次主存，该机制将CPU提供的访存地址（相对地址）与长度寄存器中的值进行比较。若越界，则终止该程序；否则，与基地址寄存器中的值相加成为访问主存的绝对物理地址

• 在多道固定分区法下，存储调度（即中级调度）一般分为多队列法和单队列法。

• 这些未得到利用的空间称为存储碎片。
  存储碎片分为内部碎片和外部碎片。

• 若存储块长度为n，该块存储的作业长度为m，则剩下的（长度为n-m）空间称为该块的内部碎片；若存储块长度为n，在该系统所采用的调度算法下，较长时间无法选出一道长度不超过该块的作业，即该块长时间得不到使用，则称该块为外部碎片。

• 分配策略：满足作业要求的可用块可能有很多块，那么应该选哪一块分给该作业呢？有下述三种选择方法：
  ① 首次满足法（First Fit）。搜索F时，选择所碰到的第一个满足作业存储量要求的块分配给用户。
  ② 最佳满足法（Best Fit）。在F中选出所有满足作业要求的存储块中最小的一块分给用户。
  ③ 最大满足法（Largest Fit）。在F中选出满足作业要求的最大块分给用户。

• 紧致空间管理。采用可变分区，没有内部碎片（一般不把小于基本存储分配单位的未利用的空间看成碎片）

• 紧致（Compact）空间的方法予以消除。紧致的基本思想是，通过移动主存中的作业位置，使可用空间连成一片。实现紧致必须要求作业代码是动态重定位的。

5.2 不连续空间分配

• 在页式系统中，将作业和主存都分成较小的块，可将作业的各块非连续地分配到可用块中。

• 用户程序目标代码所设想的空间和所用地址称为逻辑空间和逻辑地址。

• 占主存空间称为物理空间，对应的地址称为物理地址。

• 逻辑空间所划分出的每个区域称为页（Page）；物理空间所划分出的每个区域称为页帧（Page Frame）。

• 逻辑空间若有n页，页表就应该有n项。

• 线性逻辑地址可以分解成页号、页内位移，分别记为P，d。线性物理地址可以分解成页帧号、页帧内位移，记为f，d（例如，页面大小为512字节，地址539属于第1页，页内位移为27）。

• 由于计算机采用二进制编码，所以如果取页面大小为2的正整数次幂，乘、除法就变成了位移运算。例如，取页面大小为29（512）字节，则逻辑地址的低9位便为页内位移，高位为页号。这样，地址转换时所需要的乘、除法则可免去。在页式系统中有此原则：页面大小=2k（k是正整数）。

• 把页表中经常使用的页表项置于快速存储器（如快表，又有联想存储器之称），此矛盾就能得到较好的解决，页式管理法亦才得以付诸实用。

• 首先把页号送到快表中去匹配。若匹配成功，则形成物理地址，否则到主存页表中查找页表项来形成物理地址。如果快表不满，则将新页表项加入快表，否则从快表中淘汰一项后再加入新项

• 在段式系统中，空间不按等长而是根据程序的自然段来划分。

• 逻辑地址则由两部分组成：段号与段内位移，分别记做S，d。

• 首先需要一张逻辑空间与主存空间对照的段表，若作业被划分成n段，段表就应该有n项。段表项中的内容（如图5.23所示）包括本段在主存的起始地址、本段的长度及保护码等。

• 同样，要设置快表，将部分段表项放在快表中以提高转换速度。地址转换的过程是，将段号与快表中的各个关键字进行比较，若匹配成功，则检查段内位移d是否在该说明的长度内，同时检查保护码与本次操作的一致性，若这些比较结果都正常，则输出该段的起始物理地址，并与d相加得到物理地址。若在快表中匹配不成功，则将S与段表长度寄存器的内容进行比较。若没有越界，则将S与段表始地址相加，得到段表项的物理地址，查段表项，检查d是否越界，操作码是否与保护码一致。最后用该段起始地址与d相加得到物理地址，同时更换快表的内容。这一过程如图5.24所示。

• 地址转换的过程是，将段号与快表中的各个关键字进行比较，若匹配成功，则检查段内位移d是否在该说明的长度内，同时检查保护码与本次操作的一致性，若这些比较结果都正常，则输出该段的起始物理地址，并与d相加得到物理地址

• 段页式系统对物理空间的管理、安排与页式系统相同，而对逻辑空间则先进行段的划分，然后在每一段内再进行页的划分。

• 在段页式系统中，作业运行时同样需要动态地将逻辑地址转换成物理地址。地址转换所依赖的数据结构是段表和页表。每个作业均有一个段表，而每一段都有一个页表（都放在系统空间里）。

5.3 虚拟存储管理

• 虚拟存储管理，这种管理方法通过统一管理主、辅存，给用户造成一种仿佛系统内具有巨大主存供用户使用的假象。

• 因为它只把运行程序在最近一段时间里活跃的那一部分放进主存，而这一部分往往只占整个程序空间的少数，于是主存中能同时存在的进程道数明显增多，为提高系统的吞吐量奠定了基础。

• 程序在执行时，当访问的页不在主存时，根据页表项的指引，从辅存将其调入主存。如果这时已无可用的物理空间，则从主存淘汰若干页。

• 修改位是为了在将页面所占用的主存页帧释放回系统时，指明该页是否要回写到辅存块中。

• 专用的交换区（或Swap文件/页文件）用于存放那些可读写的进程页面。

• 若合法位未被置上，则马上产生一个页故障（Page Fault）或称为缺页异常。进入操作系统核心，马上进行页面调入处理。

• 如何选取被淘汰的页是由页面替换策略决定的，进程的合法页集合称为驻留集（或称工作集），是否允许进程驻留集大小可变也是页面替换策略的关键。

• 首先对页表按物理内存页帧大小进行分页，对它们编号并离散地存放于不同的物理页帧中；同时为离散存储的页表再建立一张页表，称为外层页表（Outer Page Table）或页目录表，以记录各页表对应的物理页帧号。

• 多级页表技术，不但突破了页表必须连续存放的限制，同时当有大片虚地址空间未使用时，可以不分配对应页表空间，因此可节省内存。另外，多级页表增加了访存次数，因此外层页表的页表项应该尽可能保持在快表中，以减少访存开销。

• elady奇异是指替换策略不符合随着驻留集大小的增大，页故障数一定减少的规律。例

• 它淘汰下次访问距当前最远的那些页中序号最小的一页。

• LRU策略淘汰上次使用距当前最远的页。

第六章 设备管理

• 管理和控制所有的外部设备（又称I/O设备），是操作系统的主要功能之一。

6.1 I/O硬件概念

• 之所以将设备区分成上述三种类型，主要是因为对它们的管理方法不同。

• 设备管理子系统屏蔽了对各类设备的控制细节，提供一个设备与操作系统其他部分之间的简单易用的接口，并且该接口应对所有设备尽可能地一致，这就是设备无关性。

• 电子部分称为I/O部件或设备控制器。在个人计算机中，它常常是一块可以插入主板扩展槽的印制电路板，机械部分则是设备本身

• 设备本身又发展成了拥有机械部分和部分控制电路的智能设备。

• 之所以区分控制器和设备本身是因为操作系统大多与控制器打交道，而非设备本身。

• 连接CPU、主存、设备控制器和设备的多总线模型

• 每个可编程设备控制器都有一些用来与CPU通信的寄存器。在某些计算机上，这些寄存器占用主存物理地址空间的一部分，这种方案称为主存映射I/O。

• 操作系统通过向控制器的寄存器写命令字来执行I/O功能。

• PCI总线控制器不能算是设备控制器，它在初始化后，只是作为处理机/主存与外部设备之间数据交换的通路，控制总线的使用，没有直接控制设备I/O的逻辑。

• 在程序直接控制I/O时，CPU直接控制I/O操作过程，包括测试设备状态，发送读/写命令与数据。

• CPU向设备控制器发出命令后，继续做其他有用的工作。当设备控制器准备好与CPU交换数据时，设备控制器中断CPU，要求服务。CPU被中断后，执行CPU寄存器与设备控制器之间的数据传输，然后恢复被中断的工作。

• 当大量的数据在外部设备与主存之间移动时，一种有效的技术就是DMA（Direct Memory Access）。

• 发出命令后，CPU继续进行其他的工作。它把这次I/O任务委托给了DMA部件，由它负责完成这次I/O操作。DMA部件每次一个字地将整个数据块直接读取或写入主存，而不需经过CPU的寄存器。当传送过程完成后，DMA部件向CPU发中断信号。因此，仅在数据块传送的开始及结束处涉及到CPU，

• 在DMA传送期间，CPU的执行速度会慢下来。无论如何，对于一次成块的多字节的I/O传送来说，DMA方式比中断驱动I/O要减少许多中断，减少许多CPU的I/O启动操作。

6.2 设备I/O子系统

• 独占式使用设备是指在申请设备时，如果设备空闲，就将其独占，不再允许其他进程申请使用，一直等到该设备被释放，才允许被其他进程申请使用。

• 对磁盘设备进行I/O操作时，也采用了分时式共享使用，就是说，把每一次对磁盘设备的I/O操作的数据都看成是逻辑上完整的，从而无需对设备进行独占式申请，保证设备的高效使用。

• 假脱机I/O技术。把这种技术用于对设备的使用，实质就是对I/O操作进行成批处理。

• 必须避免边生成输出数据边打印，可以将输出数据边生成边写入文件（或写到所谓的磁盘输出井中），文件相当于虚拟打印设备，待到全部输出完成，再独占打印机把文件（或输出井）内容从打印机上打印出来。

• 每个打印机建立一个打印服务（Daemon）进程，和一个打印队列（该队列的每个表项对应一个输出文件副本）。打印服务进程循环地获取打印队列中的表项，顺序地从每个文件副本中读取出数据，再成批地调用写打印机的系统调用将该文件的数据打印在纸上。

• 用户层I/O是提供给用户进程使用I/O设备进行I/O操作的接口，它运行在用户态。系统调用接口，设备无关的操作系统软件、设备驱动及中断处理则在核心态运行，属于操作系统内核程序。

• 这些库函数在用户态运行，它们往往没有做太多的事情，而只转调操作系统的I/O相关的系统调用。

• 块设备和字符设备都需要缓冲技术

• 设备驱动程序包括所有与设备相关的代码。每个设备驱动程序只处理一种设备或者一类紧密相关的设备。

• 笼统地说，设备驱动程序的功能，是从与设备无关的软件中接收抽象的I/O请求并执行。

• 缓冲技术实际上是在计算机各个层次使用的一种通用技术，缓冲区比目标存储访问速度要快，当然缓冲区只能存放目标存储的部分数据，设立缓冲区的目的是减少访问目标存储部件的次数，提高I/O速度。

• 在用户进程从一个系统缓冲区移走（填入）数据的同时，操作系统可往另一系统缓冲区填入（移走）数据。

• 引入缓冲可有效地改善CPU与I/O设备之间速度不匹配的矛盾。

• 无论开辟多少缓冲区，都无法使I/O操作的速度跟上进程的运行。当所有的缓冲区渐渐地被填满后，缓冲区的作用随即减弱，进程将不得不在处理完一批数据后等待I/O。

6.3 存储设备

• 根据磁头的当前位置，首先选择请求队列中距磁头最短的请求，再为之服务。

• 即让磁头固定地从外向内然后从内向外逐柱面运动，如此往复。磁头固定在水平的两个端点来回扫描。

• 这种调度算法使磁头从盘面上的一端（逐柱面地）向另一端移动来服务请求，返回时直接快速移至起始端而不服务任何请求。如此往复单向地扫描并平均地为各种请求服务。

• 一个磁盘的失效不会导致数据丢失。这种磁盘组织技术，统称为冗余廉价磁盘阵列（RAID，Redundant Arrays of Inexpensive Disks），通常用于解决性能和可靠性问题。

• 可靠性问题的解决是引入冗余。除了原始信息以外还存储额外数据，虽然它们不被经常使用，但可以用来在磁盘失效时重建丢失的信息。这样，即使磁盘失效，数据也可以恢复。

• 最简单（但最贵）的冗余方法是复制所有的磁盘，这种技术称为镜像。

6.4 小结

• 设备控制器中常常包含三类寄存器，它们分别用于：① 存放控制命令；② 存放状态信息；③ 存放数据。软件通过读/写这三类寄存器完成相应的I/O操作。

第七章 文件系统

• 早期人们就引入了辅助存储器（也称文件存储器）用于保存大量的永久性信息（如系统库程序、编译程序等实用程序及操作系统自身的部分程序和数据等）和临时性信息（用户的程序、数据、系统临时数据等）。

7.1 文件结构

• 辅助存储器用来存放各种程序和数据，这些存放在辅助存储器中的程序和数据称为文件

• 操作系统抛开存储设备的物理特性，定义了逻辑存储实体，即文件，并负责将文件映射到物理设备上。这是操作系统文件管理所要完成的基本功能之一。

• 文件根据其用途必须有确定的结构

• 若将解释文件结构信息的工作赋予操作系统外层的软件（如文本编辑程序等），那么在操作系统这一级则将文件视为无结构（或只涉及简单的逻辑结构）、无解释的信息集合，如UNIX操作系统只简单地把所有文件看成是一组8位字节的信息流，不对文件的信息项做任何解释。

• 指用户随机地访问文件中的某段信息。

• 文件必须存放于可以支持快速定位的随机访问存储设备中。文件中的记录（或逻辑字节）被顺序编号，文件被允许随机读/写任意的记录（或逻辑字节），无任何限制。

• 光盘设备的特点是定位速度快、可直接访问，但其上的文件往往是一次性写入，不可以删除和重写文件。

• 文件存储器的信息存储、读/写均以块为单位，这种物理块也称为物理记录。

• 解决逻辑记录到物理记录的映射

• 若一个文件在辅存中是散布在辅存非连续的若干物理块中，且用向前指针把每个记录依次链接起来（如用每个记录的最后一个字作为指针，指向下一个记录的物理位置），这种组织形式称为链接结构

• 可将文件的全部逻辑记录都散存在辅存的各物理块中，为文件建立一张索引表，登记相应逻辑记录的长度及其辅存的物理位置

• 文件应包括文件控制块（FCB，File Control Block）和文件体。后者是文件的有效信息部分；前者则是一张用于存放文件标识、定位、说明和控制等信息的表格。

7.2 文件目录结构

• 一级目录结构又叫平面（Flat）文件结构。

• 将记录文件的目录分成主文件目录（主目录）和由其主管的若干子目录，且各子目录的物理位置由主目录中的目录项指出，这种结构即为二级目录结构。

• 二级目录结构可视为根结点是MFD的二级树结构，MFD的子结点是UFD，UFD的孩子结点则是文件树的叶结点。

• 树形目录结构也称为多级目录结构。

• 树中的每个文件具有唯一的路径名。路径名为根结点与经子目录的各级结点直至文件的结点名的顺序组合。

• 用户可指定某级目录作为用户“当前目录”，当前目录的FCB事先已读入并保存在主存。

• 人们因此而引入一种无环图目录结构

• 可建立一个称为链的新目录项，由此链指向共享文件或子目录。

7.3 文件存储器空间布局与管理

• 在系统运行过程中，文件频繁地被创建和删除，文件系统对磁盘空间的分配保持一个称为“自由空间表”的数据结构。

第八章：并行与分布式操作系统

8.1 并行操作系统

• 对称多处理机，这是目前并行处理机中最常见的一种结构，在此结构上的操作系统应该同时调度多进程（或线程）在多处理机上运行，甚至让多个处理机对称地同时响应不同的中断。

• 现代进程概念，将进程控制块中与资源相关的部分和与执行相关的部分部分分离，这种分离引出了线程结构。

• 由多个中央处理机组成，它们共享主存并且每个处理机都可以响应中断，具有完全的对称结构，称为对称多处理机（SMP）

• 共享主存系统。顾名思义，是所有处理机共享同一个物理主存，所有处理机可以平等地访问同一个物理存储器。

• 分布存储系统。每个处理机都有自己的存储器，每个处理机通过互联网络连接起来。当需要时，可以通过网络交换各自存储器中的数据。

• 并行程序段能够在多处理机结构下实现真正并行，而不是单机的分时并发执行，对资源互斥访问有新的要求

• 现代操作系统有意地把这两部分特性分离，并在进程里可以定义多个执行对象，使并行任务能在进程内并行，这种执行对象称为线程。

• 把进程看做除了处理机资源外的其他资源分配单位，但线程总是隶属于进程的，而且进程至少要包含一个线程。

• 进程在创建时一般同时创建第一个线程，其他线程按需要由用户程序发出请求创建。

• 与一个线程关联的私有存储区。每个线程有一个存放与线程相对应的局部变量区。该区与执行栈的区别是，栈区间用于存放调用点现场、函数内局部变量，一般由编译系统安排使用，而该私有存储区空间可由用户程序指定申请，存放长效局部变量，可以在同一个线程中跨函数使用。

• 进程拥有一个虚地址空间，一个用户栈用于执行用户程序，一个核心栈用于执行内核程序。

• 用户栈存放于进程用户虚空间中，核心栈存放于系统空间中。

• 一个进程中的所有线程可共享进程空间及对系统其他资源的使用。

• 对处理机的占用以线程为单位，调度及处理机切换则必须利用线程的数据结构。

• 由于进程用户空间分立，进程间同步、通信必须通过操作系统的系统调用来实现。

• 对于线程间通信与同步，若涉及不同进程的线程，实际就是进程间通信。对于同一进程内的线程间通信与同步，由于线程共享同一片用户进程空间，线程之间的通信与同步就变得很容易，通信完全可以在共享变量间进行。

• 多线库支持的线程称为用户级线程，内核支持的线程称为内核级线程或轻权进程LWP。

• 由于对线程的所有操作都不涉及内核，因此用户级线程的创建、结束、调度、现场保护与切换开销非常少

• 在对多处理机线程调度和处理分配问题的研究中，以下5个方案在现代操作系统线程调度设计中影响很大：
  ① 负载共享。线程不被指定到任何特别的处理机。系统维护一个全局的就绪线程队列，任何处理机在空闲时都可以到该队列上获得一个就绪线程来运行。
  ② 负载绑定。指定运行线程的处理机，线程只能在指定的处理机上运行。
  ③ 组调度。将一组相关的线程同时调度到一组处理机上运行。
  ④ 独占处理机调度。这与负载共享恰恰相反，将一组处理机分配给指定并行程序中的线程运行，等到并行程序运行结束，处理机才被系统收回，以利系统分配给其他并行程序。
  ⑤ 多级动态调度。允许并行程序中的线程数目在运行过程中动态改变，利用多级线程支持实现多级调度。

8.2 分布式系统

• 分布式系统是由独立计算机（又称节点）组成的集合，并给用户一个单一系统的映像。
• 构建分布式系统主要有如下几个好处：实现分布资源位置透明，方式共享；提高系统计算能力；提高系统的可靠性和健壮性。
• 如果能将用户任务分解成可以并行运行的子任务，那么可以将这些能并行运行的子任务分布到分布式系统的各台计算机上并行运行，从而提高系统的计算能力。
• 客户/服务器模型又称工作站/服务器模型（Workstation/Server Model）
• 在对等模型中，系统中的每台计算机具有高度自治性，可以采用工作站或多用户计算机充当节点计算机，每个节点机都运行一组完整的标准软件，既可以作为客户机运行用户应用程序，又可以充当服务器为其他节点机提供服务。
• 集群定义为一组由相同功能的计算机互连而成的系统，它们作为统一的计算资源一起发挥作用，给客户一台机器的感觉。
• IP（网际协议）。IP是面向无连接的报文交换协议，负责寻址和路由的选择。
• ARP负责由IP地址到硬件地址（MAC地址）的转换。
• RARP负责完成由硬件地址到IP地址的转换

第九章：保护与安全

9.1 安全威胁

• 蠕虫是一个独立的程序，利用网络连接寻找攻击目标。蠕虫通常由两部分程序组成：粘连（或钩子）程序和主程序。

• 特洛伊木马是一个独立的程序，表面上在执行合法任务，实际上却具有用户不曾料到的非法功能。

9.2 安全机制

• 数据加密标准（DES，Data Encryption Standard）是使用最广泛的对称加密算法，

• 若以公钥作为加密密钥，以私钥作为解密密钥，则可实现多个用户加密的信息只能由一个用户解读；反之，以私钥作为加密密钥而以公钥作为解密密钥，则可实现一个用户加密的信息能由多个用户解读。前者可用于数据加密，后者可用于数字签名。

• 数字签名是指用户使用自己的私钥对原始数据的数字摘要进行加密所得的数据。