第1章 引论

1.1 什么是操作系统

1. 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
2. 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
3. 操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
4. 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。 内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

1.5 操作系统概念

1.5.1 进程

进程本质上是正在执行的一个程序。

地址空间

第2章 进程与线程

进程是对正在运行程序的一个抽象。

2.1 进程

严格来说，在某一个时刻，CPU只能运行一个进程。但在1秒钟内，它可能运行多个进程，这样就产生并行的错觉。

2.1.1 进程模型

一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。

每个进程执行其运算速度是不确定的，所以，在对进程编程时决不能对时序作任何想当然的假设。

进程和程序有微妙的区别。做蛋糕的食谱就是程序，进程就是厨师阅读食谱、取来各种原料以及烘制蛋糕等一系列操作的总和。

一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。

2.1.2 进程的创建

• 4种主要事件会导致进程的创建：
  • 系统初始化
  • 正在运行的程序执行了创建进程的系统调用
  • 用户请求创建一个新进程
  • 一个批处理作业的初始化
• 守护进程： 停留在后台处理的进程。
• 新进程都是由于一个已存在的进程执行了一个用于创建进程的系统调用而创建的。
• 在UNIX系统中，只有一个系统调用可以用来创建新进程：fork。

2.1.3 进程的终止

通常由下列条件引起进程的终止：

1. 正常退出（自愿的）
2. 出错退出（自愿的）
3. 严重错误（非自愿）
4. 被其他进程杀死（非自愿）

2.1.4 进程的层次结构

• 进程只有一个父进程（但是可以有零个、一个、两个或多个子进程）。
• 在UNIX中，进程和它的所有子进程以及后裔共同组成一个进程组。
• 在UNIX中，所有的进程都属于以 init 为根的一棵树。
• Windows中没有进程层次的概念，所有的进程都是地位相同的。

2.1.5 进程的状态

当一个进程在逻辑上不能继续运行时，它就会被阻塞。

P52 图2-2

2.1.6 进程的实现

• 为了实现进程模型，操作系统维护着一张表格（一个结构数组），即进程表。每个进程占用一个进程表项。
• 与每一I/O类关联的是一个称作中断向量的位置（靠近内存底部的固定区域）。它包含终端服务程序的入口地址。

2.1.7 多道程序设计模型

采用多道程序设计可以提高CPU的利用率，不过也要考虑进程等待I/O操作的时间。

2.2 线程

在传统操作系统中，每个进程有一个地址空间和一个控制线程。

不过，经常存在在同一个地址空间中准并行运行多个控制线程的情形。

2.2.1 线程的使用

引进线程的原因：

• 通过将一些应用程序分解成可以准并行运行的多个顺序线程，程序设计模型会变得更简单。并行实体拥有共享同一个地址空间和所有可用数据的能力。对于进程来讲，它们具有的是不同的地址空间，因此需要引入线程这样的模型和概念。
• 线程比进程更轻量级，所以它们比进程更容易（即更快）创建，也更容易撤销。
• 性能方面。如果存在着大量的计算和大量的I/O处理，拥有多个线程允许这些活动彼此重叠进行，从而会加快应用程序执行的速度。
• 在多CPU系统中，多线程是有益的。

一些典型的例子来理解引入线程的好处：

• 字处理软件
  • 一个线程与用户交互
  • 一个线程在后台重新进行格式处理
  • 第三个线程可以处理磁盘备份
  • 这个例子用三个不同的进程不能做到，因为三个线程会对同一个文件进行操作，多个线程可以共享公共内存。
• 万维网服务器
  • 分派程序
  • 工作线程
  • 高速缓存
  • 线程较好地改善了Web服务器的性能，而且每个线程是按通常方式顺序编程的。
  • 第三种可能的设计：有限状态机
  • 三种方案的比较，见P57 图2-10
• 必须处理极大量数据的应用
  • 一个输入线程
  • 一个处理线程
  • 一个输出线程

2.2.2 经典的线程模型

• 进程模型基于两种独立的概念：资源分组处理与执行。
• 理解进程的一个角度是：用某种方法把相关的资源集中在一起。
• 进程拥有一个执行的线程，通常简写为线程。
• 进程用于把资源集中到一起，而线程则是在CPU上被调度执行的实体。
• 线程给进程模型增加了一项内容，即在同一个进程环境下，允许彼此之间有较大独立性的多个线程执行。
• 在同一个进程中运行多个线程，多个线程共享同一个地址空间和其他资源，而在同一个计算机上运行多个进程，多个进程共享物理内存、磁盘、打印机和其他资源，因此线程也被称为轻量级进程。
• 当多线程进程在单CPU系统中运行时，线程轮流运行。CPU在线程之间的快速切换，制造了线程并行运行的假象。
• 所有的线程都有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于各个线程都可以访问进程地址空间中的每一个内存地址，所以一个线程可以读、写或甚至清楚另一个线程的堆栈。线程之间是没有保护的。
• 线程概念试图实现的是，共享一组资源的多个线程的执行能力，以便这些线程可以为完成某一任务而共同工作。
• 线程可以处于若干状态的任何一个：运行、阻塞、就绪或终止。线程状态之间的转换和进程状态之间的转换似乎一样的。
• 认识到每个线程有自己的堆栈很重要。每个线程的堆栈有一帧，供各个被调用但是还没有从中返回的过程使用。在该栈帧中存放了相应过程的局部变量以及过程调用完之后使用的返回地址。通常每个线程会调用不同的过程，从而有一个各自不同的执行历史。
• 进程通常会从当前的单个线程开始，这个线程有能力通过调用一个库函数（如 thread_create ）创建新的线程。不论线程之间有无层次关系，创建线程通常都返回一个线程标识符，该标识符就是新线程的名字。
• 线程退出：thread_exit
• thread_join：一个线程可以等待一个（特定）线程退出。
• thread_yield：允许线程自动放弃CPU从而让另一个线程运行。这样一个调用是很重要的，因为不同于进程，（线程库）无法利用时钟中断强制线程让出CPU。

2.2.3 POSIX线程

线程包 pthread。

• pthread_create
• pthread_exit
• pthread_join
• pthread_yield
• pthread_attr_init：创建并初始化一个线程的属性结构
• pthread_attr_destroy：删除一个线程的属性结构

2.2.4 在用户空间中实现线程

优点

1. 用户级线程可以在不支持多线程的操作系统上实现。
2. 进行线程切换比陷入内核要快一个数量级（或许更多）。
3. 保存线程状态的过程和调度程序都只是本地过程，所以启动它们比进行内核调用效率更高。另一方面，不需要陷入内核，不需要上下文切换，也不需要对内存高速缓存进行刷新，这就使得线程调度非常快捷。
4. 它运行每个进程有自己定制的调度算法。
5. 用户级线程还有较好的扩展性，这是因为在内核空间中内核线程需要一些固定表格空间和堆栈空间，如果内核线程的数量非常大，就会出现问题。

• 在用户空间实现多线程，线程在一个运行时系统的上层运行，该运行时系统是一个管理线程的过程的集合。
• 在用户空间管理线程时，每个进程需要有其专用的线程表，用来跟踪该进程中的线程。

用户级线程出现的问题

• 如何实现阻塞系统调用。替代方案是提前通知。
• 如果一个线程开始运行，那么在该进程中的其他线程就不能运行。

2.2.5 在内核中实现线程

• 在内核中有用来记录系统中所有线程的线程表。
• 内核的线程表保存了每个线程的寄存器、状态和其他信息。
• 所有能够阻塞线程的调用都以系统调用的形式实现，这与运行时系统过程相比，代价是相当可观的。
• 由于在内核中创建和撤销线程的代价比较大，某些系统采取“环保”的处理方式，回收其线程。
• 内核线程不需要任何新的、非阻塞系统调用。

2.2.6 混合实现

• 一种方法是使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来。在这种模型中，每个内核级线程有一个可以轮流使用的用户级线程集合。

2.2.7 调度程序激活机制

• 调度程序激活工作的目标是模拟内核线程的功能，但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。
• 由于避免了在用户空间和内核空间之间的不必要转换，从而提高了效率。
• 当使用调度程序激活机制时，内核给每个进程安排一定数量的虚拟处理器，并且让（用户空间）运行时系统将线程分配到处理器上。

2.2.8 弹出式线程

一个消息的到达导致系统创建一个处理该消息的线程，这种线程称为弹出式线程。

2.2.9 使单线程代码多线程化

略

2.3 进程间通信

进程间通信：Inter Process Communication, IPC。

进程间通信主要要解决三个问题：

1. 一个进程如何把信息传递给另一个。
2. 确保两个或更多的进程在关键活动中不会出现交叉。
3. 与正确的顺序有关。

2.3.1 竞争条件

竞争条件：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序。例如书中举的脱机打印的例子。

2.3.2 临界区

• 避免竞争条件需要互斥，即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。
• 对共享内存进行访问的程序片段称作临界区域或临界区。如果我们能够适当地安排，使得两个进程不可能同时处于临界区中，就能避免竞争条件。
• 一个好的解决方案，需要满足以下四个条件：
  1. 任何两个进程不能同时处于其临界区。
  2. 不应对CPU的速度和数量做任何假设。
  3. 临界区外运行的进程不得阻塞其他进程。
  4. 不得使进程无限期等待进入临界区。

2.3.3 忙等待的互斥

1.屏蔽中断

• 在单处理器系统中，最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。
• 这个方法并不好。屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。

2.锁变量

• 设想有一个共享（锁）变量，其初始值为0。0就表示临界区内没有进程，1表示已经有某个进程进入临界区。
• 疏漏之处：一个进程读出锁变量的值为0，在将它设为1之前，另一个进程被调度运行，将该锁变量设置为1。第一个进程再次运行，将锁变量设置为1，这样就有两个进程在临界区中。

3.严格轮换法

• 对于编写操作系统而言，C语言是强大、有效、可预知和有特性的语言。
• 连续测试一个变量直到某个值出现为止，称为忙等待。
• 由于这种方式浪费CPU时间，所以通常应该避免。只有在有理由认为等待时间非常短的情形下，才使用忙等待。用于忙等待的锁，称为自旋锁。
• 缺点：在一个进程比另一个慢了很多的情况下，轮流进入临界区并不是一个好办法。这种情况违反了前面叙述的条件3:进程0被一个临界区之外的进程阻塞。

4.Peterson解法

略

5. TSL指令

1

TSL RX,LOCK

这条指令称为测试并加锁（test and set lock），它将一个内存字lock读到寄存器RX中，然后在该内存地址上存一个非零值。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。

• 锁住存储总线不同于屏蔽中断。事实上，在处理器1上屏蔽中断对处理器2根本没有任何影响。让处理器2远离内存直到处理器1完成的唯一方法就是锁住总线，这需要一个特殊的硬件设施。
• 为了使用TSL指令，要使用一个共享变量lock来协调对共享内存的访问。
• 进程在进入临界区之前先调用enter_region，这将导致忙等待，直到锁空闲为止，随后它获得该锁并返回。在进程从临界区返回时它调用leave_region，这将把lock设置为0。进程必须在正确的时间调用enter_region和leave_region，解法才能奏效。
• 一个可替代TSL指令的是XCHG，它原子性地交换了两个位置的内容。

2.3.4 睡眠与唤醒

• Peterson解法和TSL或XCHG解法都是正确的，但是它们都有忙等待的缺点。这些解法的本质：当一个进程想进入临界区，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。考虑优先级反转问题。
• 进程间通信原语：sleep和wakeup。

生产者-消费者问题

• 两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息。
• 问题在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况。其解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样地，当消费者试图从缓冲区中取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。
• 这里有可能会出现竞争条件，其原因是对count的访问未加限制。
• 问题的实质在于发给一个（尚）未睡眠进程的wakeup信号丢失了。快速弥补的方法是修改规则，加上一个唤醒等待位。唤醒等待位实际上就是wakeup信号的一个小仓库。但原则上，这并没有从根本上解决问题。

2.3.5 信号量

• 使用一个整型变量来累计唤醒次数，供以后使用，称作信号量。
• 设立两个操作down (P操作) 和up (V操作)（分别为一般化后的sleep和wakeup）。
• 检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。
• 所谓原子操作，是指一组相关联的操作要么不间断地执行，要么都不执行。
• up操作对信号量的值增1。
• 如果一个或多个进程在该信号量上睡眠，无法完成一个先前的down操作，则由系统选择其中的一个（如随机挑选）并允许该进程完成它的down操作。

用信号量解决生产者-消费者问题

• 为确保信号量能正确工作，最重要的是要采用一种不可分割的方式来实现它。
• 该方案使用了三个信号量：
  • full：用来记录充满的缓冲槽数目；
  • empty：记录空的缓冲槽的数目；
  • mutex：用来确保生产者和消费者不会同时访问缓冲区。如果每个进程在进入临界区前都执行一个down操作，并在刚刚退出时执行一个up操作，就能够实现互斥。该信号量用户互斥，保证任一时刻只有一个进程读写缓冲区和相关变量。
• full和empty用来保证某种事件的顺序发生或不发生。

2.3.6 互斥量

• 互斥量仅仅适用于管理共享资源或一小段代码。
• 互斥量是一个可以处于两态之一的变量：解锁和加锁。
• 常常使用一个整型量，0表示解锁，而其他所有的值则表示加锁。
• 当一个线程（或进程）需要访问临界区时，它调用mutex_lock。如果该互斥量当前是解锁的（即临界区可用），此调用成功，调用线程可以自由进入该临界区。另一方面，如果该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。

2.3.7 管程

• 同步原语：管程。一个管程是一个由过程、变量以及数据结构等组成的集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。
• 管程有一个很重要的特性，即任一时刻管程中只能有一个活跃的进程，这一特性使管程能有效地完成互斥。
• 编译器调用管程时的典型处理方法是，当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进入。
• 进入管程时的互斥由编译器负责，但通常的做法是用一个互斥量或二元信号量。
• 实现阻塞，引入条件变量以及相关的两个操作：wait和signal。当一个管程过程发现它无法继续运行时，它会在某个条件变量上执行wait操作。另一个进程，比如消费者，可以唤醒正在睡眠的伙伴进程，这可以通过对其伙伴正在等待的一个条件变量执行signal完成。
• Brinch Hansen 建议执行signal的进程必须立即退出管程，即signal语句只可能作为一个管程过程的最后一个语句。
• sleep和wakeup之所以失败是因为当一个进程想睡眠时另一个进程试图去唤醒它。使用管程则不会发生这种情况。如果管程过程中的生产者发现缓冲区满，它将能够完成wait操作而不用担心调度程序可能会在wait完成之前切换到消费者。甚至，在wait执行完成而且把生产者标志为不可运行之前，根本不会允许消费者进入管程。

信号量太低级了，而管程在少数几种编程语言之外无法使用，并且，这些原语均未提供机器间的信息交换方法。所以还需要其他的方法，也就是消息传递。

2.3.8 消息传递

消息传递的两条原语send和receive。

如果没有消息可用，则接收者可能被阻塞，直到一条消息的到达，或者，带着一个错误码立即返回。

1. 消息传递系统的设计要点

为了防止消息丢失，一旦接收到信息，接收方马上回送一条特殊的确认消息。如果发送方在一段时间间隔内未收到确认，则重发消息。

对于接收者来说，如何区分新的消息和一条重发的老消息是非常重要的。通常采用在每条原始消息中嵌入一个连续的序号来解决此问题。

消息系统还需要解决进程命名的问题，在send和receive调用中所指定的进程必须是没有二义性的。身份认证也是一个问题。还有性能问题。

2. 用消息传递解决生产者-消费者问题

在该解决方案中共使用N条消息，类似于一个共享内存缓冲区中的N个槽。当生产者向消费者传递一个数据项时，它取走一条空消息并送回一条填充了内容的消息。

如何对消息进行编址。一种方法是为每个进程分配一个唯一的地址，让消息按进程的地址编址。另一种方法是引入信箱，是一个用来对一定数量的消息进行缓冲的地方。

2.3.9 屏障

屏障可用于一组进程同步。执行barrier原语。

2.3.10 避免锁：读-复制-更新

最快的锁是根本没有锁。

然而，在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用它。窍门在于确保每个读操作要么读取旧的数据版本，要么读取新的数据版本，但绝不能是新旧数据的一些奇怪组合。

读-复制-更新，将更新过程中的移除和再分配过程分离开来。

2.4 调度

2.4.1 调度简介

1. 进程行为

当一个进程等待外部设备完成工作而被阻塞时，才是I/O活动。

计算密集型和I/O密集型。随着CPU变得越来越快，更多的进程倾向为I/O密集型。

2. 何时调度

第一，在创建一个新进程之后，需要决定的是运行父进程还是运行子进程。

第二，在一个进程退出时必须做出调度决策。

第三，当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。

第四，在一个I/O中断发生时，必须做出调度决策。

根据如何处理时钟中断，可以把调度算法分为两类：

• 非抢占式
• 抢占式

3. 调度算法分类

三种环境：

• 批处理。非抢占式算法。
• 交互式。抢占是必需的，服务器也归于此类。
• 实时。抢占有时是不需要的。

实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。

4. 调度算法的目标

所有系统

• 公平——给每个进程公平的CPU份额
• 策略强制执行——保证规定的策略被执行
• 平衡——保持系统的所有部分都忙碌

批处理系统

• 吞吐量——每小时最大作业数
• 周转时间——从提交到终止间的最小时间
• CPU利用率——保持CPU始终忙碌，CPU利用率并不是一个好的度量参数。真正有价值的是，系统每小时可完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。

交互式系统

• 响应时间——快速响应请求
• 均衡性——满足用户的期望

实时系统

• 满足截止时间——避免丢失数据
• 可预测性——在多媒体系统中避免品质降低

2.4.2 批处理系统中的调度

1. 先来先服务

最简单的是非抢占式的先来先服务算法。

当在被阻塞的进程变为就绪时，就像一个新来到的作业一样，排到就绪队列的末尾，即排在所有进程最后。

主要优点是易于理解并且便于在程序中运行。缺点很明显。例如一个一次运行1秒钟的计算密集型进程和很少使用CPU但是每个都要进行1000次磁盘读操作才能完成的大量I/O密集型进程存在。

2. 最短作业优先

适用于运行时间可以预知的另一个非抢占式的批处理调度算法。

只有在所有作业都可同时运行的情形下，最短作业优先算法才是最优的。

3. 最短剩余时间优先

最短作业优先的抢占式版本是最短剩余时间优先算法。

调度程序总是选择剩余运行时间最短的那个进程运行。再次提醒，有关的运行时间必须提前掌握。

这种方式可以使新的短作业获得良好的服务。

2.4.3 交互式系统中的调度

1. 轮转调度

一种最古老、最简单、最公平且使用最广的算法是轮转调度。每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。

时间片轮转调度中唯一有趣的一点是时间片的长度。涉及到上下文切换。

时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应时间变长。将时间片设为20ms～50ms通常是一个比较合理的折中。

2. 优先级调度

优先级调度的基本思想是：每个进程被赋予一个优先级，运行优先级最高的可运行进程线运行。

为了防止高优先级进程无休止地运行下去，调度程序可能在每个时钟滴答（即每个时钟中断）降低当前进程的优先级。如果这一行为导致该进程的优先级低于次高优先级的进程，则进行进程切换。另一种方法是，给每个进程赋予一个允许运行的最大时间片，当用完这个时间片时，次高优先级的进程便获得运行机会。

优先级可以静态赋予或动态赋予。

为达到某种目的，优先级可以由系统动态确定。使I/O密集型进程获得较好服务的一种简单算法是，将其优先级设为1/f，f为该进程在上一时间片中所占的部分。

如果不偶尔对优先级进行调整，则低优先级进程很可能会产生饥饿现象。

3. 多级队列

属于最高优先级类的进程运行一个时间片，属于次高优先级类的进程运行2个时间片，再次一级运行4个时间片，以此类推。当一个进程用完分配的时间片后，它被移动到下一类。

随着进程优先级的不断降低，它的运行频度逐渐放慢，从而为短的交互进程让出CPU。

对于那些刚开始运行一段长时间，而后来又需要交互的进程，为了防止其永远处于被惩罚状态，可以采取下面的策略。只要终端上有回车键按下，则属于该终端的所有进程就都被移到最高优先级，这样做的原因是假设此时进程即将需要交互。

4. 最短进程优先

首先运行最短的作业来使响应时间最短。

如何从当前可运行进程中找出最短的那一个进程。一种办法是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。

老化技术，假设某个终端上某条命令的估计运行时间为$T_0$。现在假设测量到其下一次运行时间为$T_1$。可以用这两个值加权和来改进估计时间，即$aT_0+(1-a)T_1$。可以根据需要选择$a$的值。

5. 保证调度

向用户作出明确的性能保证，然后去实现它。若用户工作时有$n$个用户登录，则用户将获得CPU处理能力的$1/n$。

系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间，即自创建以来的时间除以$n$。该算法转向比率最低的进程。

6. 彩票调度

其基本思想是为进程提供各种系统资源（如CPU时间）的彩票。一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得资源。在应用到CPU调度时，系统可以掌握每秒钟50次的一种彩票，作为奖励每个获奖者可以得到20ms的CPU时间。

所有进程是平等的，但是某些进程更平等一些。拥有彩票$f$份额的进程大约得到系统资源的$f$份额。

彩票调度是反应迅速的。

彩票调度可以用来解决其他方法很难解决的问题，例如视频服务器提供视频流，每个视频流的帧速率都不相同。

7. 公平分享调度

考虑谁拥有进程这一因素。

2.4.4 实时系统中的调度

实时系统通常可以分为硬实时和软实时。前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。

实时系统的调度算法可以是静态或动态的。

2.4.5 策略和机制

解决问题的方法是将调度机制与调度策略分离这个一贯的原则。

2.4.6 线程调度

用户级线程：运行时系统使用调度算法可以是上面介绍的算法中的任意一种，常用轮转调度和优先级调度。

内核级线程。

用户级线程和内核级线程之间的差别在于性能。用户级线程的线程切换需要少量的机器指令，而内核级线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这导致了若干数量级的延迟。另一方面，在使用内核级线程时，一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

用户级线程可以使用专为应用程序定制的线程调度程序。而在内核级线程中，内核从来不了解每个线程的作用。一般而言，应用定制的线程调度程序能够比内核更好地满足应用的需要。

2.5 经典的IPC问题

2.5.1 哲学家就餐问题

一种没有死锁，而且对于任意位哲学家的情况都能获得最大的并行度。使用一个数组state跟踪每一个哲学家是在进餐、思考还是饥饿状态（正在试图拿叉子）。一个哲学家只有在两个邻居都没有进餐时才允许进入到进餐状态。

2.5.2 读者-写者问题

为数据库访问建立了一个模型。

第3章 内存管理

• 分层存储器体系
• 操作系统中管理分层存储器体系的部分称为存储管理器。它的任务是有效地管理内存，即记录哪些内存是正在使用的，哪些内存是空闲的；在进程需要时为其分配内存，在进程使用完后释放内存。

3.1 无存储器抽象

• 最简单的存储器抽象就是根本没有抽象，其模型就是简单的物理内存。

在不使用存储器抽象的情况下运行多个程序

• 操作系统只需要把当前内存中所有内容保存到磁盘文件中，然后把下一个程序读入到内存中再运行即可。只要在某一个时间内存中只有一个程序，那么就不会发生冲突。
• 用内存键的方式并发地运行多个程序的缺陷：会出现对内存地址的不正确访问，问题的关键是两个程序都引用了绝对物理地址。

3.2 一种存储器抽象：地址空间

把物理地址暴露给进程的几个问题：

1. 用户程序可以很容易地破坏操作系统，从而使系统慢慢地停止运行。
2. 想要同时运行多个程序是很困难的。

3.2.1 地址空间的概念

• 要使多个应用程序同时处于内存中并且互不影响，需要解决两个问题：保护和重定位。
• 地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间（除了在一些特殊情况下进程需要共享它们的地址空间外）。
• 地址空间概念举例
  • 电话号码的地址空间是从 0 000 000 到 9 999 999
  • x86的I/O端口的地址空间从0到16 383
  • 以“.com”结尾的网络域名的集合也是地址空间

基址寄存器与界限寄存器

• 动态重定位，简单地把每个进程的地址空间映射到物理内存的不同部分。
• 当使用基址寄存器和界限寄存器时，程序装载到内存中连续的空闲位置且装载期间无须重定位。当一个程序运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中。
• 每次一个进程访问内存，取一条指令，读或写一个数据字，CPU硬件会把地址发送到内存总线前，自动把基址值加到进程发出的地址值上。同时，它检查程序提供的地址是否等于或大于界限寄存器里的值，如果访问的地址超出了界限，会产生错误并中止访问。
• 使用基址寄存器和界限寄存器是给每个进程提供私有地址空间的非常容易的方法，因为每个内存地址在送到内存之前，都会自动先加上基址寄存器的内容。
• 使用基址寄存器和界限寄存器重定位的缺点是，每次访问内存都需要进行加法和比较运算。比较运算可以做得很快，但是加法运算由于进位传递时间的问题，在没有特殊电路的情况下会显得很慢。

3.2.2 交换技术

• 所有进程所需要的RAM数量总和通常要远远超出存储器能够支持的范围。
• 有两种处理内存超载的通用方法
  • 交换技术，即把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行时就不会占用内存。
  • 虚拟内存，该策略甚至能使程序在只有一部分被调入内存的情况下运行。
• 交换在内存中产生了多个空闲区，通过把所有放入进程尽可能向下移动，有可能将这些小的空闲区合成一大块。该技术称为内存紧缩。通常不进行这个操作，因为它要耗费大量的CPU时间。
• 如果大部分进程在运行时都要增长，为了减少因内存区域不够而引起的进程交换和移动所产生的开销，一种可用的方法是，当换入或移动进程时为它分配一些额外的内存。然而，当进程被换出到磁盘上时，应该只交换进程实际上使用的内存中的内容，将额外的内存交换出去是一种浪费。
• 如果进程有两个可增长的段，在两者之间的内存可供两个段使用。

3.2.3 空闲内存管理

一般而言，有两种方法跟踪内存使用情况：位图和空闲区链表。

1. 使用位图的存储管理

• 使用位图方法时，内存可能被划分成小到几个字或大到几千字节的分配单位。每个分配单元对应于位图中的一位，0表示空闲，1表示占有（或者相反），
• 分配单元的大小是一个重要的设计因素。分配单元越小，位图越大。若选择比较大的分配单元，则位图更小。但若进程的大小不是分配单元的整数倍，那么在最后一个分配单元中就会有一定数量的内存被浪费了。
• 这种方法的主要问题是，在决定把一个占k个分配单元的进程掉入内存时，存储管理器必须搜索位图，在位图中找出有k个连续0的串。查找位图中指定长度的连续0串是耗时的操作（因为在位图中该串可能跨越字的边界），这是位图的缺点。

2. 使用链表的存储管理

• 维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程，或者是两个进程间的一块空闲区。
• 链表中的每一个结点都包含以下域：空闲区（H）或进程（P）的指示标志、起始地址、长度和指向下一结点的指针。

当按照地址顺序在链表中存放进程和空闲区时，几种算法可以用来为创建的进程分配内存。

• 首次适配算法。存储管理器沿着段链表进行搜索，直到找到一个足够大的空闲区，除非空闲区大小和分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。
• 下次适配算法。它的工作方式和首次适配算法相同，不同点是每次找到合适的空闲区时都记录当时的位置，以便在下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次适配算法那样每次都从头开始。仿真程序表明下次适配算法性能略低于首次适配算法。
• 最佳适配算法。搜索整个链表（从开始到结束），找出能够容纳进程的最小的空闲区。最佳适配算法试图找出最接近实际需要的空闲区，以最好地匹配请求和可用空闲区，而不是拆分一个以后可能会用到的大的空闲区。
• 因为每次调用最佳适配算法时都要搜索整个链表，所以它要比首次适配算法慢。让人感到有点意外的是，它比首次适配算法或下次适配算法浪费更多的内存，因为它会产生大量无用的小空闲区。一般情况下，首次适配算法生成的空闲区更大一些。
• 最差适配算法。总是分配最大的可用空闲区，使新的空闲区比较大从而可以继续使用。仿真程序表明最差适配算法也不是一个好主意。

如果进程和空闲区使用不同的链表，则可以按照大小对空闲区链表排序，以便提高最佳适配算法的速度。空闲区链表按大小排序时，首次适配算法与最佳适配算法一样快，而下次适配算法在这里则毫无意义。

快速适配算法，它为那些常用大小的空闲区维护单独的链表。快速适配算法寻找一个指定大小的空闲区是十分快速的，但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点，即在一个进程终止或被换出时，寻找它的相邻块并查看是否可以合并的过程是非常耗时的。如果不进行合并，内存将会很快分裂出大量的进程无法利用的小空闲区。

3.3 虚拟内存

• 还有另外一个问题需要解决：管理软件的膨胀。
• 程序大于内存，一种解决方法是把程序分割成许多片段，称为覆盖。但是把一个程序分割成小的、模块化的片段是非常费时和枯燥的，并且容易出错。很少程序员擅长使用覆盖技术。
• 虚拟内存技术。其基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页或页面。每一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立即执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
• 从某个角度来讲，虚拟内存是对基址寄存器和界限寄存器的一种综合。

3.3.1 分页

• 由程序产生的这些地址称为虚拟地址，它们构成了一个虚拟地址空间。在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（Memory Management Unit, MMU），MMU把虚拟地址映射为物理内存地址。
• 虚拟地址空间按照固定大小划分成被称为页面的若干单元。在物理内存中对应的单元称为页框。页面和页框的大小通常是一样的。RAM和磁盘之间的交换总是以整个页面为单元进行的。
• 通过恰当地设置MMU，可以把16个虚拟页面映射到8个页框中的任何一个。
• MMU注意到该页面没有被映射，于是使CPU陷入到操作系统，这个陷阱称为缺页中断或缺页错误。操作系统找到一个很少使用的页框且把它的内容写入到磁盘（如果它不在磁盘上）。随后把需要访问的页面读到刚才回收的页框中，修改映射关系，然后重新启动引起陷阱的指令。
• MMU内部结构，了解为什么我们选用的页面大小都是2的整数次幂。输入的16位虚拟地址被分为4位的页号和12位的偏移量。可用页号座位页表的索引，以得出对应于该虚拟页面的页框号。如果“在/不在”位为1，则将在页表中查到的页框号复制到输出寄存器的高3位中，再加上输入虚拟地址中的低12位偏移量，如此就构成了15位的物理地址。输出寄存器的内容随即可被作为物理地址送到内存总线。

3.3.2 页表

• 虚拟地址到物理地址的一种简单实现可以概括为：虚拟地址被分为虚拟页号（高位部分）和偏移量（低位部分）两部分。
• 虚拟页号可用作页表的索引，以找到该虚拟页面对应的页表项。由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成送往内存的物理地址。
• 页表的目的是把虚拟页面映射到页框。从数学角度说，页表是一个函数，它的参数是虚拟页号，结果是物理页框号。通过这个函数可以把虚拟地址中的虚拟页面域替换成页框域，从而形成物理地址。

页表项的结构

• 页框号
• “在/不在”位
• 保护位指出一个页允许什么类型的访问。
• 为了记录页面的使用状况，引入了修改位和访问位。
• 不论是读还是写，系统都会在该页面被访问时设置访问位。它的值被用来帮助操作系统在发生缺页中断时选择要被淘汰的页面。不再使用的页面要比正在使用的页面更适合淘汰。
• 最后一位用于禁止该页面被高速缓存。

应该注意的是，若某个页面不在内存中，用于保护该页面的磁盘地址不是页表的组成部分。

虚拟内存本质上是用来创造一个新的抽象概念——地址空间，这个概念是对物理内存的抽象，类似于进程是对物理处理器（CPU）的抽象。虚拟内存的实现，是将虚拟地址空间分解成页，并将每一页映射到物理内存的某个页框或者（暂时）解除映射。

3.3.3 加速分页过程

在任何分页系统中，都需要考虑两个主要问题：

1. 虚拟地址到物理地址的映射必须非常快。
2. 如果虚拟地址空间很大，页表也会很大。

第一个问题是由于每次访问内存都需要进行虚拟地址到物理地址的映射，所有的指令最终都必须来自内存，并且很多指令也会访问内存中的操作数。

第二个问题来自现代计算机使用至少32位的虚拟地址，而且64位变得越来越普遍。

对大而快速的页映射的需求称为构建计算机的重要约束。一种简单的设计是使用“快速硬件寄存器”，这个方法的优势是简单并且在映射过程中不需要访问内存。而缺点是在页表很大时，代价高昂。而且每一次上下文切换都必须装载整个页表，这样会降低性能。另一种极端的方法是，整个页表都在内存中。这种做法的缺陷是在执行每条指令时，都需要一次或多次内存访问来完成页表项的读入，速度非常慢。

1. 转换检测缓冲区

有了分页机制后，会因为要访问页表而引起更多次的内存访问。

一种解决方案的建立基于这样一种观察：大多数程序总是对少量的页面进行多次的访问，而不是相反。因此，只有很少的页表项会被反复读取，而其他的页表项很少被访问。

为计算机设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再访问页表。这种设备称为转换检测缓冲区（Translation Lookaside Buffer, TLB），有时又称为相联存储器或快表。它通常在MMU中，每个表项记录了一个页面的相关信息，包括虚拟页号、页面的修改位、保护码（读/写/执行权限）和该页所对应的物理页框。

如果发现了一个有效的匹配并且要进行的访问操作并不违反保护位，则将页框号直接从TLB中取出而不必再访问页表。如果虚拟页号确实是在TLB中，但指令试图在一个只读页面上进行写操作，则会产生一个保护错误，就像对页表进行非法访问一样。如果MMU检测到没有有效的匹配项，就会进行正常的页表查询。接着从TLB中淘汰一个表项，然后用新找到的页表项代替它。当一个表项被清除出TLB时，将修改位复制到内存中的页表项，而除了访问位，其他的值不变。当页表项从页表装入TLB中时，所有的值都来自内存。

2. 软件TLB管理

许多现代的RISC机器，几乎所有的页面管理都是在软件中实现的。当发生TLB访问失效时，不再由MMU到页表中查找并取出需要的页表项，而是生成一个TLB失效并将问题交给操作系统解决。

如果TLB大到（如64个表项）可以减少失效率时，TLB的软件管理就会变得足够有效。

无论是用硬件还是软件来处理TLB失效，常见方法都是找到页表并执行索引操作以定位将要访问的页面。可以通过在内存中的固定位置维护一个大的（如4KB）TLB表项的软件高速缓存来减少TLB失效。

当一个页面访问在内存中而不在TLB中时，将产生软失效。当页面本身不在内存中（当然也不在TLB中）时，将产生硬失效。

引发缺页错误的几种情况：

• 次要缺页错误
• 严重缺页错误
• 段错误

3.3.4 针对大内存的页表

1. 多级页表

引入多级页表的原因是避免把全部页表一直保存在内存中。特别是那些从不需要的页表就不应该保留。

多理解书中的例子。

2. 倒排页表

在这种设计中，实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项，但它也有严重的不足：从虚拟地址到物理地址的转换会变得很困难。

可以使用TLB。实现搜索的一个可行的方法是建立一张散列表，用虚拟地址来散列。如果散列表中的槽数与机器中物理页面数一样多，那么散列表的冲突链的平均长度会是一个表项的长度，这将会大大提高映射速度。一旦页框号被找到，新的（虚拟页号，物理页框号）对就会被装载到TLB中。

倒排页表在64位机器中很常见。

3.4 页面置换算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本；如果该页面没有被修改过（如一个包含程序正文的页面），那么它在磁盘上的副本已经是最新的，不需要回写。直接用调入的页面覆盖被淘汰的页面就可以了。

当需要从内存中换出某个页面时，它是否只能是缺页进程自己的页面？这个要换出的页面是否可以属于另外一个进程？在前一种情况下，可以有效地将每一个进程限定在固定的页面数目内；后一种情况则不能。

3.4.1 最优页面置换算法

算法工作原理：在缺页中断发生时，有些页面在内存中，其中有一个页面（包含紧接着的下一条指令的那个页面）将很快被访问，其他页面则可能要到10、100或1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。

最优页面置换算法规定应该置换标记最大的页面。

这个算法唯一的问题就是它是无法实现的。当缺页中断发生时，操作系统无法知道各个页面下一次将在什么时候被访问。用这种方式，可以通过最优页面置换算法对其他可实现算法的性能进行比较。

为了避免混淆，必须清楚以上页面访问情况的记录只针对刚刚被测试过的程序和它的一个特定的输入。

3.4.2 最近未使用页面置换算法

系统为每一页面设置了两个状态位。当页面被访问（读或写）时设置R位；当页面被写入（即修改）时设置M位。一旦设置某位为1，它就一直保持1直到操作系统将它复位。

如果硬件没有这些位，则可以使用操作系统的缺页中断和时钟中断机制进行模拟。

可以用R位和M位来构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置为0，R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。

4类：

• 第0类：没有被访问，没有被修改。
• 第1类：没有被访问，已被修改。
• 第2类：已被访问，没有被修改。
• 第3类：已被访问，已被修改。

NRU算法随即地从类编号最小的非空类中挑选一个页面淘汰。NRU算法的主要优点是易于理解和能够有效地被实现，虽然它的性能不是最好的，但是已经够用了。

3.4.3 先进先出页面置换算法

由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加入到表尾。

3.4.4 第二次机会页面置换算法

第二次机会算法对先进先出页面置换算法做了一个简单的修改：检查最老页面的R位。如果R位为0，那么这个页面既老又没有被使用，可以立刻被置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它像刚装入的一样，然后继续搜索。

第二次机会算法就是寻找一个在最近的时钟间隔内没有被访问过的页面。

3.4.5 时钟页面置换算法

第二次机会算法经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

3.4.6 最近最少使用页面置换算法

对最优算法的一个很好的近似是基于这样的观察：在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。

在缺页中断发生时，置换未使用时间最长的页面。这个策略称为LRU（Least Recently Used, 最近最少使用）页面置换算法。

3.4.7 用软件模拟LRU

NFU（Not Frequently Used，最不常用）算法。该算法将每个页面与一个软件计数器相关联，计数器的初值为0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的R位（它的值是0或1）加到它的计算器上。这个计算器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。这个算法的问题是它从来不忘记任何事情。

老化算法：首先，在R位被加进之前先将计数器右移一位；其次，将R位加到计数器最左端的位而不是最右端的位。

3.4.8 工作集页面置换算法

请求调页，因为页面是在需要时被调入的，而不是预先装入。

局部性访问行为，即在进程运行的任何阶段，它都只访问较少的一部分页面。

一个进程当前正在使用的页面的集合称为它的工作集。若每执行几条指令程序就发生一次缺页中断，那么就称这个程序发生了颠簸。

不少分页系统都会设法跟踪进程的工作集，以确保在让进程运行之前，它的工作集就已在内存中了。该方法称为工作集模型，其目的在于大大减少缺页中断率。在进程运行前预先装入其工作集页面也称为预先调页。

在任一时刻t，都存在一个集合，它包含所有最近k次内存访问所访问过的页面。这个集合w(k,t)就是工作集。

事实上大多数程序会任意访问一小部分页面，但是这个集合会随着时间而缓慢变化，这个事实也解释了为什么一开始曲线快速地上升而k较大时上升会变慢。预先调页就是在程序继续运行之前预先装入推测出的工作集的页面。

页面置换算法：当发生缺页中断时，淘汰一个不在工作集的页面。根据定义，工作集就是最近k次内存访问所使用过的页面的集合。

作为替代，一种能够常见的近似方法就是，不是向后找最近k次的内存访问，而是考虑其执行时间。一个进程从它开始执行到当前实际使用的CPU时间总数通常称作当前实际运行时间。通过这个近似的方法，进程的工作集可以被称为过去的$\tau$秒实际运行时间中它所访问过的页面的集合。

扫描所有页面检查R位：

• 若 (R==1)：设置上次使用时间为当前实际时间
• 若(R == 0 且生存时间 > $\tau$) ：移出这个页面
• 若(R == 0 且生存时间 <= $\tau$) ：记住最小时间

3.4.9 工作集时钟页面置换算法

与时钟算法一样，所需的数据结构是一个以页框为元素的循环表。

如果R位被置为1，该页面在当前时钟滴答中就被使用过，那么该页面就不适合淘汰。然后把该页面的R位置为0，指针指向下一个页面，并重复该算法。

如果R位被置为0。如果页面的生存时间大于$\tau$并且该页面是干净的，申请此页框，并把新页面放在其中。另一方面，如果此页面被修改过，就不能立即申请页框，指针继续向前走。

原则上，所有的页面都有可能因为磁盘I/O在某个时钟周期被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回n个页面。一旦达到该限制，就不允许调度新的写操作。

3.4.10 页面置换算法小结

3.7 分段

编译器的例子。一个直观并且通用的方法是在机器上提供多个互相独立的称为段的地址空间。每个段由一个从0到最大的线性地址序列构成。各个段的长度可以是0到某个允许的最大值之间的任何一个值。不同段的长度可以不同，并且通常情况下也都不相同。段的长度在运行期间可以动态改变。

段当然有可能会被装满，但通常情况下段都很大，因此这种情况发生的可能性很小。程序必须提供两部分地址，一个段号和一个段内地址。

段是一个逻辑实体。一个段可能包括一个过程、一个数组、一个堆栈、一组数组变量，但一般它不会同时包含多种不同类型的内容。

如果每个过程都位于一个独立的段中并且起始地址是0，那么把单独编译好的过程链接起来的操作就可以得到很大的简化。

分段也有助于在几个进程之间共享过程和数据。

因为每个段是一个为程序员所知道的逻辑实体，比如一个过程或一个数组，故不同的段可以有不同种类的保护。

3.7.1 纯分段的实现

分段和分页的实现本质上是不同的：页面是定长的而段不是。

在系统运行一段时间后内存被划分为许多块，一些块包含着段，一些则成了空闲区，这种现象称为棋盘形碎片或外部碎片。空闲区的存在使内存被浪费了，而这可以通过内存紧缩来解决。

3.7.2 分段和分页结合：MULTICS

如果一个段比较大，把它整个保存在内存中可能很不方便甚至是不可能的，因此产生了对它进行分页的想法。这样，只有那些真正需要的页面才会被调入内存。

MULTICS的设计者决定把每个段都看作一个虚拟内存并对它进行分页，以结合分页的优点（统一的页面大小和只在使用段的一部分时不用把它全部调入内存）和分段的优点（易于编程、模块化、保护和共享）。

每个MULTICS程序都有一个段表，每个段对应一个描述符。段表本身也是一个段并被分页。一个段描述符包含了一个段是否在内存中的标记，只要一个段的任何一部分在内存中这个段就被认为是在内存中，并且它的页表也会在内存中。

每个段都是一个普通的虚拟地址空间。

MULTICS中的一个地址由两部分构成：段号和段内地址。段内地址又进一步分为页号和页内的字。算法如下：

1. 根据段号找到段描述符。
2. 检查该段的页表是否在内存中。如果在，则找到它的位置；如果不在，则产生一个段错误。如果访问违反了段的保护要求就发出一个越界错误（陷阱）。
3. 检查所请求的虚拟页面的页表项，如果该页面不在内存中则产生一个缺页中断，如果在内存就从页表项中取出这个页面在内存中的起始地址。
4. 把偏移量加到页面的起始地址上，得到要访问的字在内存中的地址。
5. 最后进行读或写操作。

实际上，MULTICS硬件包含了16个字的高速TLB。

3.7.3 分段和分页结合：Intel x86

x86处理器中虚拟内存的核心是两张表，即LDT（局部描述符表）和GDT（全局描述符表）。LDT描述局部于每个程序的段，包括其代码、数据、堆栈等；GDT描述系统段，包括操作系统本身。

为了访问一个段，一个x86程序必须把这个段的选择子装入机器的6个段寄存器的某一个中。

在选择子被装入段寄存器时，对应的描述符被从LDT或GDT中取出装入微程序寄存器中，以便快速地访问。一个描述符由8个字节构成，包括段的基址、大小和其他信息。

假设段在内存中并且偏移量也在范围内，x86处理器接着把描述符中32位的基址和偏移量相加形成线性地址。

线性地址被分为三个域：目录、页面和偏移量。

x86处理器和MULTICS一样，也有一个小的TLB把最近使用过的“目录-页面”二元组映射为页框的物理地址。

第6章 死锁

软硬件资源都有可能出现死锁。

6.1 资源

需要排他性使用的对象称为资源。

6.1.1 可抢占资源和不可抢占资源

资源分为两类：可抢占的和不可抢占的。

可抢占资源可以从拥有它的进程中抢占而不会产生任何副作用，存储器就是一类可抢占的资源。

不可抢占资源是指在不引起相关的计算失败的情况下，无法把它从占有它的进程抢占过来。

某个资源是否可抢占取决于上下文环境。

总的来说，死锁与不可抢占资源有关，有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。

使用一个资源所需要的事件顺序可以用抽象的形式表示如下：

1. 请求资源
2. 使用资源
3. 释放资源

在后面的讨论中，我们假设：如果某个进程请求资源失败，那么它就进入休眠状态。

6.1.2 资源获取

死锁是非常容易发生的。