详情
本书首先回顾了与全书其他内容切实相关的UNIX系统内幕，增进读者对UNIX操作系统概念的了解，并且定义随后使用的术语。本书第一部分介绍高速缓存体系结构、术语和概念，详细考察了4种常见的高速缓存实现，第二部分讨论调整单处理机内核的实现，使之适合于紧密耦合、共享存储多处理机上运行时所面临的问题和设计事宜，还研究几种不同的实现，最后一部分介绍多处理机高速缓存一致性，从而将前两个部分的内容结合到一起。
PEARSON
现代体系结构上的UNIX系统 内核程序员的对称多处理和缓存技术（修订版）
[美]Curt Schimmel 著
张辉 译
田春 审校
人民邮电出版社
北京
图书在版编目（CIP）数据
现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术/（美）希梅尔（Schimmel,C.）著；张辉译.--2版（修订本）.--北京：人民邮电出版社，2015.1
ISBN 978-7-115-35758-8
Ⅰ.①现… Ⅱ.①希…②张… Ⅲ.①UNIX操作系统 Ⅳ.①TP316.81
中国版本图书馆CIP数据核字（2014）第238916号
内容提要
本书首先回顾了与全书其他内容切实相关的UNIX系统内幕。回顾的目的是增进读者对UNIX操作系统概念的了解，并且定义随后使用的术语。本书接下来的内容分为3个部分。第一部分介绍了高速缓存体系结构、术语和概念，详细考察了4种常见的高速缓存实现——3种虚拟高速缓存的变体和物理高速缓存。第二部分讨论了调整单处理器内核的实现，使之适合于紧密耦合、共享存储多处理器上运行时所面临的问题和设计事宜，还研究了几种不同的实现。最后一部分介绍多处理器高速缓存一致性，这一部分通过研究高速缓存加入到一个紧密耦合、共享存储器多处理器系统时出现在操作系统和高速缓存体系结构上的问题，从而将前两个部分的内容结合到一起。
本书适合于大学计算机及相关专业高年级本科生或者研究生使用。每一章都包含有一组练习题，问题都需要采用这一章所提供的信息以及一些额外学到的知识来解答，习题大都建立在这一章中所出现的例子的基础之上。在本书的末尾有选择地给出了习题的答案。
◆著 [美]Curt Schimmel
译 张辉
审校 田春
责任编辑 杨海玲
责任印制 彭志环
◆人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
三河市海波印务有限公司印刷
◆开本：787×1092 1/16印张：19
字数：452千字 2015年1月第2版
印数：4001-7000册 2015年1月河北第1次印刷
著作权合同登记号 图字：01-2014-6465号
定价：59.00元
读者服务热线：(010)81055410 印装质量热线：(010)81055316反盗版热线：(010)81055315
广告经营许可证：京崇工商广字第0021号
Authorized translation from the English language edition,entitled UNIX Systems for Modern Architectures:Symmetric Multiprocessing and Caching for Kernel Programmers,First Edition,0201633388 by Curt Schimmel,published by Pearson Education,Inc.,publishing as Addison Wesley,Copyright © 1994 by Curt Schimmel.
All rights reserved.No part of this book may be reproduced or transmitted in any form or by any means,electronic or mechanical,including photocopying,recording or by any information storage retrieval system,without permission from Pearson Education,Inc.
CHINESE SIMPLIFIED language edition published by PEARSON EDUCATION ASIA LTD.and POSTS & TELECOM PRESS Copyright © 2014.
本书中文简体字版由Pearson Education Asia Ltd.授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。
本书封面贴有Pearson Education（培生教育出版集团）激光防伪标签，无标签者不得销售。
版权所有，侵权必究。
本书是对多年前出版时采用的译文参照英文原著进行审校后重新出版的产物。通常，作为一个审校者是不应该留下序的，而且我也不能算是该领域的专家，顶多只能说是在开发并行软件的工作中用到了一些来自本书的知识，然后推动了出版社下决心再版此书的过程。按照国内的出版传统，再版一本已出版十年之久且英文原著并无更新的书是罕见的。我的看法是，这本书的内容既没有过时，也没有被任何后续出版的其他教材所取代，因此为了让广大读者继续得以通过正规渠道学习这些知识，唯一的途径就是再版此书。因此我谨代表广大读者真心感谢人民邮电出版社能够做出这个努力。
当今关于计算机软件和硬件的书本知识正在愈发脱节。关于硬件的知识和汇编语言的教材都还停留在早期的处理器型号上，学完以后对日常编写软件帮助不大（因为编译器的优化能力日益提高，很少需要插入手工的汇编代码），而面向软件和高级语言的知识则越发抽象，层层封装，学来学去，最后只学会了使用各种库而已。计算机的现代体系结构从未改变过，各种语言和虚拟机的内存模型本质上都来源于硬件在性能和可靠性上的权衡。这些权衡就体现在对高速缓存的广泛使用上，可惜关于该领域的知识却很少被提及。
如果读者的最终目标是实现最高性能的多线程程序，那么我认为本书的阅读至少可以起到打基础的良好作用。一旦从硬件层面理解了高速缓存和原子指令的本质，那么接下来就可以从著名的《多处理器编程的艺术》一书中继续汲取营养，或者通过另一本网上可以免费找到的《Is Parallel Programming Hard,And,If So,What Can You Do About It?》进一步了解在某个具体的操作系统（Linux）中，内核和应用程序是如何有效利用对称多处理器和各种高速缓存的了。
所以，本书算是填补了软件和硬件知识之间的空白，把一切都关联起来了。另外，本书是操作系统无关的，并非书名所暗示的仅适用于UNIX。不过类UNIX系统普遍具有一种简单性：极少量的稳定的系统接口用来处理几乎所有的事务，因此以UNIX为蓝本来讲述硬件知识有助于读者迅速地拨云见日，看到真正有用的东西，这是好事。相比之下，即便非常熟悉Windows系统和各种Win32 API的人也未必真正了解Windows内核原理，按照一本极其有趣的书《Rootkit：系统灰色地带的潜伏者》中的说法，微软公司在Windows内核中所设计的虚拟内存模型，其复杂度令英特尔的虚拟内存机制相形见绌。
本书审校过程中的主要改动如下：对于一些计算机术语的译文，参照目前流行的译法以及微软的计算机术语库做了调整。例如，context原本翻译成“现场”，现译成“上下文”；transaction原本翻译成“交易”，现改为“事务”。最明显的改动是几乎所有的“多处理机”全部改为了“多处理器”，因为按照百度百科的解释，“多处理机”是更为广义的概念，相比之下本书只讨论单台传统意义计算机上的对称多处理器系统。此外，一些原本翻译得不准确的句子也有改动。虽然不敢说比原译者理解得更准确，但有了前人的译文再考虑更贴切的译法，总比自己完全重译得到的文字要好一些，所以绝不敢贪功。不过也不排除一些原本翻译不够准确的句子在此次审校过程中竟没能发现，对于这类情况就只能希望读者见谅了。
总而言之，希望所有各方为了再版此书的所作的努力都是值得的，也希望这本书能够真正对广大读者起到帮助作用。
田春
2014年9月21日
于意大利博洛尼亚
本书的目标在于，为了让操作系统能够在采用了高速缓存（cache memory）以及（或者）多处理器（multiprocessor）技术的现代计算机系统上运行，就若干必须要解决的问题提供实用的信息。在撰写本书的时候，已经有一些讲述UNIX系统实现的书籍，但是却没有一本书详细描述应该如何管理高速缓存和多处理器。许多计算机体系结构方面的书籍都是从硬件方面介绍高速缓存和多处理器的，但是却没有一本书能够成功地解决这些现代体系结构给操作系统所带来的问题。本书的意图就是通过建立计算机体系结构和操作系统之间的桥梁来填补这些缺憾。
本书是为操作系统开发人员编写的，它从系统程序员的角度阐述了高速缓存和多处理器的操作。虽然本书的读者对象是UNIX系统程序员，但是本书的编写形式使之能够适用于任何操作系统，其中包括所有的UNIX变体。通过概念层次上阐述的问题和解决方案，并且以使用UNIX系统服务（system service）为例来展示这些问题出现的地方，从而达到了这一效果。所以本书提供的解决方案也可以应用到相应环境下的其他操作系统上。
本书打算采取两种途径向操作系统开发人员提供帮助。首先，读者将学习如何调整现有的操作系统，使之能够在现代体系结构上运行。为了做到这一点，本书从操作系统的角度来详细研究这些体系结构的操作，并且阐述了操作系统要管理这些体系结构必须做什么。其次，读者将学习现代体系结构在不同方法之间进行抉择时所涉及的若干权衡考虑。在投身于采用高速缓存和多处理器的新型计算机系统设计工作时，这会给予操作系统开发人员所需要的背景知识。
本书假定读者熟悉UNIX系统调用接口（system call interface）和UNIX内核原理的高级概念。读者还应该熟悉计算机体系结构（computer architecture）和计算机系统组织（computer system organization），应具备计算机科学系本科生水平的相应课程所教授的知识。
本书扩充了为计算机产业界的UNIX系统专业人员所开发的I级课程（course I）。在过去的4年中，这门课一直在美国的USENIX大会和欧洲的UKUUG大会上讲授。由于它是一门为期一天的辅导课，因而在所含材料的数量上就有所限制。本书更为细致地涵盖了有关高速缓存和多处理器课程的所有材料，并且还包含了其他主题。
本书适合于大学高年级本科生或者研究生使用。每一章都包含有一组练习题。选出的问题都需要采用这一章所提供的信息以及一些额外学到的知识来解答，并不是简单地模仿他人的材料来出题。在许多情况下，习题都建立在这一章中所出现的例子的基础之上。答案往往采取一小段话的形式（大多数情况下有 4~5 句话，有时会长一些）。希望读者能够尝试解答所有的问题，以此增进对所学概念的掌握。在本书的末尾有选择地给出了习题的答案。
我们首先回顾了与本书其他内容切实相关的 UNIX 系统内幕。回顾的目的是增进读者对UNIX操作系统概念的了解，并且定义随后使用的术语。本书接下来分成3个部分：高速缓存存储系统（cache memory system）、多处理器 UNIX 实现以及多处理器高速缓存一致性（cache consistency）。第一部分“高速缓存存储系统”介绍了高速缓存体系结构、术语和概念。接下来详细讲述了 4 种常见的高速缓存实现：3 种虚拟高速缓存（virtual cache）的变体和物理高速缓存（physical cache）。第二部分“多处理器系统”讨论了调整单处理器（uniprocessor）内核的实现，使之适合于在紧密耦合（tightly-coupled）、共享存储多处理器（shared memory multiprocessor）上运行时所面临的问题和设计事宜，还研究了几种不同的实现。最后一部分介绍多处理器高速缓存一致性，这一部分通过研究高速缓存加入到一个紧密耦合、共享存储器多处理器系统时所出现的操作系统和高速缓存体系结构上的问题，从而将前两个部分的内容结合到一起。
本书因地制宜地使用一组经过挑选的现代多处理器体系结构来举例说明相关的概念。其中Motorola 68040和Intel 80X86系列（80386、80486和Pentium）代表了传统的CISC（complex instruction set computer，复杂指令集计算机）处理器。RISC（reduced instruction set computer，精简指令集计算机）方法则以MIPS系列（R2000、R3000和R4000）、Motorola 88000以及来自德州仪器公司（Texas Instruments，TI）的SPARC v8兼容处理器（MicroSPARC和SuperSPARC）为代表。另外还出现了其他几个例子，包括Sun和Apollo工作站和Intel i860。在附录A中可以找到这些处理器特性的一份汇总介绍。
我要向在本书付梓之前耗费时间评审书稿的人士表示我的感激之情。特别要感谢下面这些人：Steve Albert、Paul Borman、Steve Buroff、Clement Cole、Peter Collinson、Geoff Collyer、Bruce Curtis、Mukesh Kacker、Brian Kernighan、Steve Rago、Mike Scheer、Brian Silverio、Rich Stevens、Manu Thapar、Chris Walquist和Erez Zarok。我也要向Addison-Wesley公司的员工们表示感谢，感谢他们在本书出版的过程中所提供的帮助和建议，特别要感谢 Kim Dawley、Kathleen Duff、Tiffany Moore、Simone Payment、Marty Rabinowitz和John Wait。他们的帮助使得这本书比我一个人努力的结果要好得多。我还要感谢许多在上辅导课期间花时间填写课程评语，从而提供其深思熟虑后的反馈意见的人士。
在计算机系统发展历史中的许多时期，构建整体上速度更快的系统的愿望都集中在系统的三大组成部分——CPU、存储子系统和I/O子系统——的速度都更快上面。通过提高时钟速度就可以制造出更快的CPU。通过降低存取时间就可以制造出更快的存储子系统。通过提高数据传输速率就可以制造出更快的I/O子系统。但是，随着时钟速度和传输速率的提高，要提高系统的整体速度就变得越来越困难了，因此要设计和构建这样的系统，成本也变得越来越高。随着速度的提高，传输延迟（propagation delay）、信号上升时间（signal rise time）、时钟同步和分发（clock synchronization and distribution）等都变得越发重要起来。这类高速设计的高成本更难获得有效的性能价格比。
因为受这样和那样的因素影响，系统设计人员扩大了他们的关注范围，以找出提高系统整体性能的其他途径。精简指令集计算机（Reduced Instruction Set Computer，RISC）系统的概念就是其成果之一，在RISC系统中对CPU指令集进行了简化，从而让一个低成本的快速硬件实现就能完成这些指令。另一项成果是高速缓存存储系统的开发。高速缓存通过把程序中引用最频繁的数据和指令保存在一小块高速存储器中，以此降低主存储系统的负载，从而提高系统的性能。通过增加一小块成本划算、高速度的高速缓存（而不是一个成本高、规模大的高速主存储子系统）就能加速存储器整体存取速度。采用高速缓存存储器有可能带来更快的存储器整体存取时间，这对于RISC系统来说尤为重要，因为要完成相同的任务，使用精简的指令集通常要求RISC CPU比传统的CPU体系结构取得和执行更多的指令。一般而言，RISC系统需要更高的带宽来以峰值性能运行。
通过并行运行更多台设备而不是提高任何单台设备的速度就能获得更高的I/O传输速率。这就导致了诸如廉价磁盘冗余阵列（Redundant Arrays of Inexpensive Disks，RAID）之类设备的发展，在 RAID 中，多块磁盘并行运行以提供更高的整体传输率。通过增加一个系统中 CPU 的数量来构建多处理器，这样的技术也可以用于提高 CPU 的速度。多处理器把系统负载分散到多个处理器上来增加整个系统的吞吐率。
多处理器和高速缓存是密切相关的。紧密耦合多处理器系统（tightly coupled multiprocessor system）有一个共享的主存储子系统，随着处理器数量的增加，它需要更高的主存储带宽，因为每个处理器在取得和执行一条独立的指令流的同时，都必须在存储器中访问一组独立的数据。将一块高速缓存和每个处理器进行耦合，从高速缓存而不是共享的主存储器来满足处理器大部分的存储器访问请求，就可以降低主存储器的负载。这是一种颇为划算的提高系统性能的途径。
虽然高速缓存能够在多处理器中增加有效的存储器带宽，但是高速缓存结构对于管理它所需要的操作系统开销有很大的影响，这又反过来影响了系统的整体性能。
总而言之，构建速度更快的计算机系统不仅仅是一件诸如提高 CPU 时钟速度这样的事。虽然这样的技术实际上造就了更快的系统，但是它们不一定就是经济上划算的解决方法。通过集中研究如何利用现有的系统部件来提供更高的系统性能，人们已经发现高速缓存和多处理器是划算的解决方案。因此，我们就从这里开始研究高速缓存和多处理器的体系结构，以及它们给操作系统带来的问题。
本部分举例说明在本书的示例中所采用的符号约定。
常数
十进制、八进制和十六进制常数都以C编程语言的标准记法来表示。十进制常数总是以数字1~9中的一个开头。八进制常数以0开头。十六进制常数以字符序列“0x”开头。这里是一些例子：
12345 十进制常数
07654 八进制常数
0x3af 十六进制常数
字长
存储器中的一个字（word）为4字节（byte）。每字节为8位（bit），因此每一个字是32位。
字节顺序
存储器最容易想成是字的数组（array）。要引用一个字中的单个字节，需要有一种给它们编号的约定。所有展示存储器中字节排列的例子都使用了大端（big-endian）的字节顺序。这意味着每个字的最高有效字节（Most Significant Byte，MSB）拥有最低的地址，而最低有效字节（Least Significant Byte，LSB）拥有最高的地址。在字中的字节是从左到右读取的，首先读取最高有效字节。例如，下面的字节编号方式会运用到字长为4字节的机器上。
Motorola的处理器、Sun SPARC兼容类型的处理器以及IBM的处理器（IBM PC的处理器除外）都使用大端的字节顺序。DEC 和 Intel 处理器使用小端（little-endian）的字节顺序，在这类处理器中，一个字里面的字节是按照逆序编号的。MIPS 处理器可以配置成任何一种字节顺序，在生产基于MIPS处理器的系统的所有厂商中，除了DEC之外，都选择大端的字节顺序。
位顺序
在一个字或者字节内，各个位的顺序遵循低字节结尾的顺序，这意味着最低有效位（least significant bit，LSb）的编号为0位，而4字节长的字中，最高有效位（most significant bit，MSb）是 31 位。最高有效位始终在最左边。在需要用位的编号来说清楚一个例子的时候，就在一个字节或者字的上方给出位的编号来。例如，下面的字显示出了每个字节内的最高和最低有效位，每个字节则按照字内的位顺序进行编号。
位范围
有时需要从一个字或者字节中引用一串连续的位，这就称为位范围（bit range）。位范围可以用尖括号括起范围两端的位号来表示。例如，在上面所示的一个字中，构成字节2的位序列被表示成“位<15..8>”。最高有效位号始终出现在左边，右边跟着最低有效位号。这种记法所表示的范围始终包括这两个位的位置本身。
存储器大小的单位
千字节（kilobyte）被缩写成KB，它包含1024字节。兆字节（megabyte）被缩写成MB，它包含1024 KB。吉字节（gigabyte）被缩写成GB，它包含1024 MB。例如，4 KB是4096字节，而8 MB是8 388 608字节。存储器大小始终是以字节来衡量的。KB、MB和GB等缩写均会在本书中使用。
本章回顾了UNIX内核原理的有关内容，在以后各章中会用到它们。这里没有完整地讨论这个主题，而是作为那些已经熟悉基本概念和术语的人对这些内容进行的一次复习。本章的内容涉及单处理器系统。多处理器UNIX系统的实现是本书第二部分的主题。不熟悉UNIX操作系统或者UNIX内核原理的读者应该首先从本章末尾给出的参考文献中选出一些阅读。
UNIX 系统是一种多用户、多任务操作系统，它提供了高度的程序可移植性以及丰富的开发工具集合。UNIX 系统取得成功的一部分原因在于它提供的可移植的应用程序接口集合。这一接口集合能够轻而易举地处理把应用程序从一家厂商的系统移植到另一家厂商的问题。UNIX 取得成功的另一部分原因在于操作系统、命令和库（library）本身的编写都可以轻松地移植到不同的计算机上，从而促进了市场上UNIX硬件平台的多样性。
UNIX系统在逻辑上具有分层的结构，可以分成两个主要部分：内核（kernel）和用户程序（user program）。图形化的表示如图1-1所示。
内核的用途是与硬件接口并且控制硬件。内核还向用户程序提供一组抽象的系统服务，称为系统调用（system call），使用可移植的接口就能够访问系统调用。内核在内核级（kernel level）上运行，在这个级别上它能够执行特权操作。这能让内核完全控制硬件和用户级程序，并且提供一个让所有的程序协调共享底层硬件的环境。
UNIX系统调用服务的定义在很大程度上能够让它们在所有的UNIX系统上都显得相同，而不管硬件的特殊性如何。这些抽象概念提供了UNIX用户级程序高度的可移植性。文件（file）就是一种内核抽象服务的例子。UNIX文件呈现为一个顺序字节流的形式，其中没有记录（record）或者任何其他类型的边界。用户程序可以从文件的任何部分读取任意数量的字节，而无需考虑对齐任何类型的边界。这就使用户程序在存取一个文件的时候无需考虑磁盘的物理扇区（physical sector）、磁道（track）和柱面（cylinder）的边界。文件抽象如何映射到硬件上的细节问题是由内核来负责处理的。
用户的应用程序、UNIX命令以及库（常用子例程的集合）都共存于用户级（user level）。用户级包含非特权的硬件执行状态。因此，用户级程序是在一个受限的环境中执行的，它受到了内核的控制，防止同时执行的多个程序彼此互相干扰（无论是有意还是无意的）。当用户程序通过执行一次系统调用来请求服务的时候，系统调用会转入内核，在那儿它代表发出请求的用户程序执行一次服务。还可能执行权限检查以确保该程序有权访问被请求的服务。
图1-1描绘出了UNIX系统以及其他大多数操作系统传统上是如何实现的：它们都是作为一个单片的程序（monolithic program）。随着时间的推移，这种实现一直在向结构化的方向发展。在结构化的方式中，内核服务被分割成了独立的一些模块（module）。这就增加了实现的灵活性，更易于添加、改变以及移植系统服务，也有可能将一些服务移到内核之外，然后在特殊的服务器进程中以用户级来运行它们。这就减少了内核自身所必须提供的服务，从而使其缩小到微内核（micro-kernel）。因为本书所介绍的概念和技术并不依靠内核的内部组织，所以也就无需进一步深入考虑其组织的问题。从现在开始，术语“内核”一词将用来指提供UNIX系统服务的东西，而不管它是一个单片程序还是一组模块。
程序（program）被定义为执行某项任务所需的指令和数据集。进程（process）则是程序加上其执行状态的组合，进程最少要包括所有变量的值、硬件状态（如程序计数器（PC）、寄存器、条件码等），以及地址空间的内容说明。简而言之，一个进程就是一个执行中的程序。
当一个用户请求运行某个程序的时候，系统就会创建一个新进程来包含该程序的执行。直到进程终止之前，它都存在于系统中，最后它不是自愿终止就是内核使它终止，要么就是用户请求它终止。进程还可以在一定程度上通过那些影响诸如进程的调度优先级的系统调用进行控制。
通过进程的抽象概念，内核就让程序有了它自己是在硬件上运行的假象。除非用户程序明确想要和系统中的其他程序以某种方式进行通信（有几种服务可以来完成这个任务），否则它们不需要关心自己与那些程序的交互作用。每个进程都获得了各自的虚拟地址空间（virtual address space），并且（在大多数实现上）按时间片来运行，于是多个进程可以共享硬件。系统上其他进程的存在性对于该用户程序是透明的。这使得开发新程序的工作更容易，也有助于确保程序的可移植性。
许多现代的 UNIX 系统提供了一种称为线程（thread）的机制。线程掌握了一个进程内一条执行流的状态。一个线程的状态最少要由硬件状态，往往还有一个栈构成。所有的UNIX进程内部都至少有一个控制线程（control thread），这个控制线程代表了程序的执行。对于所有的UNIX系统，无论是过去的还是现在的系统都是如此。支持线程的系统允许在一个进程内同时有多个控制线程。在这种情况下，每个线程都有其自己的硬件状态，但是所有的线程都在同一个地址空间中执行。在单处理器上，一次只能执行一个线程。在多处理器上，一个进程中的不同线程可以同时在不同的处理器上执行。线程的优点之一就是创建线程的开销要比创建进程的开销小，在一个进程内实现一组协调工作的线程要比实现一组协调工作的独立进程效率更高。一般而言，在进程内部执行的线程数量对于本书所涵盖的主题没有影响。因此，后面章节中只提及进程，它暗含了在进程内部执行的所有线程。
除了几处例外（下面会详细说明），所有的程序，不论是在用户级上还是在内核级上执行的，都出现在某个进程的上下文（context）内（大多数传统的UNIX内核实现都是如此，但是对于专门的实现则可能不同）。所有的用户程序都在它们自己的进程的上下文中运行。当这些用户进程通过系统调用请求内核服务的时候，实现该系统调用的内核代码继续在请求进程的进程上下文内执行。这就能让内核方便地访问进程的所有状态及其地址空间。它还提供了一种代表用户程序记录内核执行的当前状态的方式。例如，如果需要挂起一次系统调用的执行来等待I/O操作完成，那么内核有关系统调用处理的状态就被保存在进程中。
由于所有的系统活动，无论是在用户级的还是在内核级的，都发生在某个进程的上下文中，因此UNIX内核只调度进程的执行。当使用传统的分时调度（time-sharing scheduling）策略的时候，在用户级执行的进程可能被划分成任意数量的时间片，从而让所有的进程公平地共享CPU。在内核级执行的进程则不会被划分时间片。只有在当前的内核进程明确允许的情况下，才能切换到在内核级执行的另一个进程。
“所有的系统活动都发生在进程内部”这一规则的一种例外情况就是中断处理程序（interrupt handler）的执行。中断是由 I/O 设备在它们有状态信息要返回给操作系统的时候产生的。例如，状态信息可能包括一次I/O操作完成的信息。由于中断总是在任意时刻没有警告就发生了，所以它们对于进程的执行来说是异步的。当它们发生的时候，UNIX内核允许它们中断当前进程的执行。接着，系统执行中断处理程序，直到该程序完成，或者它被一次优先级更高的中断所打断为止。内核级进程如果愿意，它们有权屏蔽中断。之所以这样做，仅仅是为了保护进程级代码和中断处理程序代码所共享的数据结构的完整性。
这一规则的第二种例外情况则伴随流（stream）服务过程而出现。来自AT&T的UNIX实现SVR3（System V Release 3）中引入了流机制，它提供了一种网络协议实现的框架。虽然详细讨论流超出了本书的范围，但是这里要说明一点是，出于性能方面的原因，服务过程是在任何进程的上下文之外运行的，就像中断处理程序一样。
内核给每个进程提供了它自己的虚拟地址空间（virtual address space）。在正常情况下，一个进程不能直接访问另一个进程的地址空间；这就提供了一种高度的保护能力，防止来自系统中其他正在执行的进程的干扰。有些实现提供了允许内存的部分区域被多个进程所共享的机制。共享内存（shared memory）和映射文件（mapped file）机制都将在本章后面的内容中进行讨论。其他机制（比如vfork系统调用和线程）都能在进程间共享部分或者全部地址空间。对于本书的目的来说，这类机制都具有和共享内存同样的特点，所以就不再深入讨论了。几乎所有的UNIX系统实现都使用请求调页机制（demand paging）来管理物理内存的分配。
一个进程的地址空间由4个主要部分构成：程序指令、初始化数据、未初始化数据和栈。在UNIX的行话中，指令（instruction）也叫做“正文”段，而初始化数据和栈可以分别简称为“数据”段和“栈”段。未初始化数据则叫做“bss”，它的名字来源于一种叫做“Block Started by Symbol”的古老的汇编程序助记符，这个助记符用于分配未初始化的数据空间。初始化数据和未初始化数据之间的区别在于，初始化数据是在程序编译时已经声明有一个初始值的全局和静态程序变量。未初始化数据是没有明确初始值的全局和静态程序变量。对于这些数据，UNIX系统仅仅依照C程序设计语言（UNIX系统几乎都是用这种语言编写的）的语义在地址空间中分配初始包含 0 的内存。这种方法的优点是未初始化数据不需要在程序文件中占用空间。
大多数使用32位虚拟地址的系统都在用户程序和内核之间划分整个4 GB的地址空间。虽然每个段的实际起始地址是与实现无关的，但是典型的布局则如图1-2所示。通常低2 GB空间供用户使用，被称为用户地址空间（user address space）。高2 GB空间则为内核保留，不准用户级代码读写，这是内核地址空间（kernel address space）。内核地址空间包括内核的正文和数据结构。当内核正在执行的时候，它可以访问整个地址空间。这种安排易于让内核在其代表用户进程执行一次系统调用的时候在用户进程的地址空间中运行。
用户正文和数据段的大小在程序编译时就固定了，它们只能在执行程序的时候从包含程序的文件中复制到地址空间里。bss 段和栈段能够在运行期动态地增长，在它们之间有一段未用的虚拟地址空间来调节增长的空间。在本书中，栈段始终是向较低的内存地址增长的，对于大多数计算机系统来说都是这样。
bss段能够借助sbrk系统调用增长或者缩小。bss段只能向较高的内存地址增长。栈根据需要由内核来动态和透明地增长。当试图访问当前分配的栈段以下的未用区时，就发生了一次缺页错误（page fault）。内核检查栈指针寄存器的内容，如果它包含的地址比栈段顶部当前的地址要小，那么内核就扩大栈段，把栈指针寄存器中的地址包括进来，并且重新执行导致缺页错误的操作。
其他类型的段，比如共享库和共享内存，都可以包含在用户地址空间内。共享库包括附加的正文、数据和bss段，它们用于常用的函数和服务。共享内存则在本章的后面介绍。
内核负责将一个进程的虚拟地址空间映射到计算机的物理地址空间上。大多数计算机允许任何虚拟页面被映射到存储器中的任何物理页面上。例如，一个进程的虚拟地址空间可以按照图1-3所示进行映射。
这幅图中的箭头显示了该进程内的一个虚拟页面被映射到了哪个物理页面上。于是，比如说如果进程访问虚拟页面2，那么对该页面的引用将被映射到物理页面1上。从虚拟地址空间到物理地址空间的映射是由内存管理单元（Memory Management Unit，MMU）来执行的，MMU负责进程所使用的全部地址。
每一个进程都有自己的与其关联的映射关系，并且作为进程上下文的一部分来保存。在进程运行的时候，内核将进程映射关系的描述提供给MMU。
注意，不是所有的虚拟页面都需要映射。例如，图1-3中的虚拟页面1、5和8就没有被映射到任何物理页面上。它们表示进程的地址空间中没有使用的页面，也可以是当前没有驻留在内存中的页面。如果一个进程试图访问后一种类型的页面，那么内核就要把相关的物理页面调入到内存中，并且把虚拟页面映射到新分配的物理页面上。
同样，不是存储器中所有的物理页面都由某个进程来使用。在图1-3中的例子里，物理页面2、4和8没有从这个进程到它们那里的映射关系。当前正在执行的进程将无法访问它们。这些物理页面可以属于系统中的其他进程，或者干脆就没有使用。无论是哪一种情况，肯定都不允许当前正在执行的进程访问它们。
通过把各个进程中的虚拟页面映射到同一个物理页面上，内核可以让多个进程共享特定的物理页面（这将在以后更详细地进行讨论）。
大多数MMU都有给每个映射关系关联一个访问权限（access permission）的能力。最常用的两种权限是读（read）和写（write）。这种功能可以让内核将正文页映射为只读的，同时允许对数据页的读写访问。
内核从执行一个进程转为执行另一个进程的操作称为上下文切换（context switch）。这项操作包括保存当前进程的状态以便在将来可以恢复、选择一个要执行的新进程，以及把所保存的新进程的状态载入到硬件中。进程在上下文切换时必须保存和恢复的最少状态是CPU寄存器的内容、PC（程序计数器）、栈指针、条件码，以及虚拟地址空间的映射关系。
在同一个进程内从一个线程切换到另一个线程的操作称为线程切换（thread switch）。因为进程不变，所以不需要改变地址空间的映射关系。只有上一段话中列出的寄存器和其他项需要保存和恢复。和进程的上下文切换相比，线程切换较少的开销是使用线程的另一个优点。总体而言，本书所介绍的主题都不需要考虑使用线程切换。
如前所述，每个进程都获得了一个独立的虚拟地址空间，这不但给它一个假象，以为它自己独自运行在计算机上，并且把它隔离开来，不受其他进程的干扰。在线程切换期间选择一个要执行的新进程时，必须彻底消除原来进程的地址空间映射，从而让新进程不能访问它。随后，新进程的地址空间被映射进来，从而能够被该进程访问。
根据所用的特定硬件，可能要保存和恢复其他类型的状态。例如，高速缓存可能需要在上下文切换时根据它们的实现进行管理（这是接下来几章讨论的主题）。内核必须确保一个进程的上下文所要求的所有部分都被保存下来，以便在将来的某个时刻可以恢复它，从而可以继续执行，就好像从未发生过上下文切换一样。这是内核保持每个进程都独自在系统上执行的假象这一任务的一个重要方面。
UNIX 系统为创建和消除进程以及改变进程的地址空间提供了几个系统调用。本节简要回顾这些系统调用的内部操作和语义，因为高速缓存和多处理器对UNIX操作系统中处理进程地址空间的部分影响最大。
系统调用fork创建一个新进程。内核通过准确复制调用fork的进程的一个副本来创建一个新进程。调用fork的进程称为父进程（parent），新创建的进程称为子进程（child）。子进程不但获得了父进程的地址空间以及包括程序变量、寄存器、PC等值在内的进程状态，而且获得了访问父进程拥有的全部 UNIX 系统服务的权利，比如父进程打开的文件。子进程是用一个控制线程创建的，这个控制线程和父进程中调用fork的线程是一样的。子进程一旦创建出来，它就独立于父进程而执行。在 fork 调用完成的时候，两个进程是相同的。两个进程上下文的唯一区别在于 fork 系统调用本身的返回值。父进程返回的是子进程的进程 ID （pid），而子进程得到的是0。这就让每个进程能够判断出它是父进程还是子进程。
因为复制一个较大的虚拟地址空间很花时间，所以要进行几种优化。首先，正文段一般由执行同一个程序（和/或共享相同的库）的所有进程只读共享。这意味着正文不需要在物理上复制给子进程。子进程只要共享父进程正在使用的同一个副本就可以了。因为UNIX内核不允许在正文段内擅自修改代码，所以才有可能共享正文（当出于调试的目的需要在正文中插入断点的时候，内核首先要创建一份正文的私用副本，以便执行相同程序的其他进程不会受到影响）。图1-4中父进程将要执行fork调用，其正文段是只读的，而它的其他页面可以进行读写访问。
接下来，几乎所有的实现都使用一种称为写时复制（copy-on-write）的技术来避免复制地址空间中剩余部分的大量内容。大多数UNIX进程在执行fork调用之后会立即调用exec（在下一小节介绍）来执行新程序。这一操作丢弃了父进程的地址空间，所以在fork期间复制父进程空间而很快又丢弃它的做法会很浪费。相反，数据、bss 和栈都不进行物理复制，而是临时在父进程和子进程之间只读共享。如图1-5所示。
注意，两个进程在逻辑上仍然对页面拥有写权限。当父进程或者子进程试图写一个页面的时候就复制单独的页面。这样一来，只有要写入的页面才会按照需要来复制，如果子进程只需要在它执行exec或者exit之前写入其地址空间的一部分的话，那么就有可能节省大量的复制开销。只读、写时复制共享（copy-on-write sharing）只是用作一种高效的实现技术，对于涉及到的进程来说是透明的。
只要两个进程都没有企图修改数据，那么就会继续保持共享关系。当两个进程中的一个要写入一个只读页面的时候，就发生了一次保护陷阱（protection trap），内核会截获到这个陷阱。内核复制出进程正在尝试修改的单个页面的一个副本，用它来替换该页面在那个进程的地址空间中被共享的副本。这种做法只用于执行写操作的进程，其他进程的地址空间不受影响。采用这种方式时，可以在父进程和子进程之间共享尽可能多的地址空间，而仅仅根据需要复制那些进程所修改的单独页面的副本。这种处理对于两个进程都是透明的，从而造成复制了整个地址空间的假象。图1-6给出了图1-5中的子进程修改了它的第3个虚拟页面之后地址空间的状态。内核把这个页面的内容复制到了一个新的物理页面中，并且重新映射子进程的地址空间，指向该物理页面上。
为了避免复制那些仅有一个映射关系的页面，内核要计算每个物理页面上的只读、写时复制的映射关系数量。所以，如果父进程现在要写入它的第3个虚拟页面，那么内核就会知道这个页面上没有其他的映射关系，只要把映射关系改为读写就行了，不需要复制该页。结果如图1-7所示。
从应用的角度来看，系统调用fork是创建新进程的一种很方便的机制，因为它不带任何参数。因为子进程继承了父进程的全部状态，所以不需要像在其他操作系统中创建新进程那样给系统调用传递一组复杂的参数。子进程根据它从父进程那里得到的状态来判断出它应该执行什么任务。在大多数情况下，fork 的目标是创建一个新进程来执行新程序。要做到这一点，子进程通过打开或者关闭文件（例如，可能为了I/O重定向）来准备进程状态，然后用系统调用exec来执行新程序。
系统调用exec可以改变一个进程正在执行的程序。只有调用exec的进程才会受到影响。exec 的参数是一个文件名（该文件包含要执行的新程序）和一组要传递给新程序的参数和环境变量。执行exec系统调用的进程保留它与大多数UNIX系统服务相关的状态信息，如它打开的文件、它的当前目录和主目录等。它的状态中和程序本身有关的部分，比如它的寄存器内容、变量、PC（程序计数器）以及地址空间，都要用新程序的来替换。更具体地说，原来程序的正文、数据、bss 和栈以及诸如共享内存的其他存储对象都会被丢弃，而要为新程序创建新的虚拟地址空间。新程序的正文和初始化数据则从指定的文件中读入，内核将地址空间内的空间分配给 bss和栈。进程内单个线程的PC（程序计数器）被设定在新程序的起始地址。当系统调用执行完毕的时候，原来的程序在进程中就不复存在了，新程序开始执行。新程序可以访问exec系统调用之前进程所打开的文件，因为这些文件都是和进程相关联的，而不是和程序相关联的。
如前所述，系统调用exec往往在fork之后执行。最常见的情形就是UNIX系统的命令解释器，它可以创建新进程来运行每条命令。命令解释器调用fork创建新进程，然后子进程调用exec运行该命令。
系统调用exit会让调用它的进程（以及它的所有线程）终止执行。该系统调用在程序完成它的执行过程之后并希望终止的时候使用。一个进程还有可能采用系统调用kill来终止另一个进程（假定该进程有适当的权限）。如果发生了无法恢复的错误，系统也可以终止一个进程。在所有的情况下，内核终止一个进程以及在事后进行清理工作的步骤都是相同的。
要终止一个进程，内核必须丢弃进程的地址空间，取消进程正在使用的内核服务，例如，关闭进程留下的任何打开的文件。此刻，进程暂时以一种称为僵尸进程（zombie）的形式存在（“僵尸进程”一词来自UNIX的行话）。这就提供了一种便捷的手段，让父进程在有机会采用系统调用wait读取子进程的退出状态之前保持进程之间的父子关系（僵尸进程与本书的讨论无关，不再深入研究）。最后，代表进程本身的内部的内核数据结构被释放。此刻，进程就不复存在了，然后内核执行一次上下文切换，选择另一个要执行的进程。
系统调用sbrk和brk都可以被一个进程用来分配或者收回它的bss段空间。这两个系统调用都以bss段的“BReaK address”（断开地址）而得名。这是在bss段内进程能够访问的最大合法地址。断开地址和栈顶部地址之间的虚拟存储区不会被映射到任何物理存储器上，进程无法访问到它们（眼下忽略共享内存和映射文件）。系统调用sbrk和brk能够让进程改变它的断开地址，从而增长或者缩小bss段的大小。系统调用sbrk接受一个代表断开地址增量变化的有符号值作为参数，而系统调用brk接受一个作为新断开地址的虚拟地址作为参数。
如果进程请求增大bss段，那么内核就正好在原来的断开地址之上分配虚拟内存，从而让进程能够访问到这部分地址空间。新分配的bss内存被定义用0来填充。bss段只能向更大的地址增长，它的起始地址是固定不变的。支持新分配的虚拟内存的物理存储器则根据需要来分配，因为它是由进程来引用的。如果缩小了 bss，那么在新老断开地址之间地址范围内的虚拟和物理内存都将被释放。访问权限也变了，于是进程再也不能访问它了。
有些UNIX系统的实现提供了一种能够让两个或者两个以上的进程共享一个物理内存区域的系统服务。这就是所谓的共享内存（shared memory）段。它是通过将同一个（或者多个）物理页面映射到两个或者更多进程的虚拟地址空间中来实现的。物理内存的共享区域无需在所有的进程中都出现在相同的虚拟地址上，每个共享区域都可以根据需要附着（attach）到不同的虚拟地址上。共享内存通常被附着在进程内bss和栈段之间未用的虚拟内存区中。
共享内存能够充当一种高速的进程间通信（interprocess communication，IPC）机制，因为进程可以通过共享内存传递数据，既不需要执行系统调用，也不需要牵扯到内核。当一个进程把数据写入共享内存中的时候，共享同一共享存储段的其他进程立即就能访问到这些数据，因为它们都共享着相同的物理页面。
在考虑内存操作的时候，I/O（输入/输出）的影响是很重要的。从用户进程请求 I/O 操作的系统调用有两个：read和write。这两个系统调用把数据从进程的地址空间传送到一个文件或者设备（write），或者反过来（read）。有些 UNIX 实现提供了额外的 I/O 系统调用，比如readv、writev、getmsg和putmsg（就本书所介绍的主题而言，这些系统调用的作用同read和 write 是一样的，所以我们只讨论这两个系统调用）。有两种类型的 I/O 操作：有缓冲的（buffered）和无缓冲的（unbuffered）。
在内核中，对特定文件类型的I/O是有缓冲的。内核和用户进程地址空间之间的数据通过一个复制操作来传输。缓冲机制的优点是它允许用户程序不必知道物理I/O设备的特性。程序不需要关心块或者记录的大小，或者任何对齐的限制。例如，磁盘往往以扇区来存取，这意味着 I/O必须从一个扇区的边界开始，并且长度为扇区长度的整数倍。当一个用户程序读取有缓冲的文件时，它只要指定它希望I/O从这个文件内开始的字节偏移量以及它想读取的字节数就可以了。为了保持文件抽象的概念，内核把用户的字节偏移量转换为包含相应数据的扇区。一个或者更多扇区从磁盘读入到内核缓冲区中，然后用户想要读取的数据部分就被复制到用户的缓冲区中。
无缓冲的I/O 则绕过了这种复制操作。用户进程可以使用这种类型的I/O，它在UNIX的行话中称为原始I/O（raw I/O）。术语“原始I/O”来源于这一事实，即通过一个缓冲区进行复制的数据被认为是经过处理的，或者说“被加工过的”。因此，没有复制的数据则被认为是“原始的”。在采用原始I/O的情况下，I/O设备使用DMA（direct memory access，直接内存访问）操作直接把数据传送到用户缓冲区。内核在有缓冲的I/O期间所缓冲的数据最终也使用DMA传送到设备上，或者从设备上传送到缓冲区中。所以，既可以在用户地址空间也可以在内核地址空间执行DMA操作。
许多UNIX系统的实现都提供了将文件映射到一个进程地址空间内的功能。一旦文件被映射到进程地址空间内，这个文件就可以作为地址空间内一段连续的字节区被直接访问。这就让进程可以使用内存的加载和保存操作而不是系统调用read和write来访问文件的内容。映射文件在逻辑上与共享内存类似：映射到同一文件的多个进程可以选择共享映射，从而让一个进程所做的改动也可以出现在其他进程的地址空间内。
本章回顾了UNIX内核的基本原理。UNIX系统是一种多用户、多任务的操作系统，它通过向进程提供与机器无关的抽象服务，从而在UNIX实现之间提供了高度的程序可移植性。程序的执行被限制在保持程序当前状态的进程内，这些状态包括虚拟地址空间、程序的变量值以及硬件状态。内核给每个进程提供了一个环境，让这个环境显得就好像该进程是系统中正在执行的唯一进程那样。这主要是通过赋予每个进程自己的虚拟地址空间来实现的。用户程序通过执行系统调用来请求内核的服务。系统调用可以创建新进程（fork），改变进程正在执行的程序（exec），以及终止进程（exit）。还可以使用许多其他的系统调用，其中包括动态分配未初始化数据的（brk/sbrk）、使用共享内存的以及执行I/O的（read和write）。
有兴趣学习更多有关UNIX系统实现知识的读者可以参考本章末尾提供的参考文献。
1.1 如果一个进程试图把数据保存在它的正文段中，将会发生什么情况？
1.2 UNIX内核会根据需要动态地增加一个进程的栈，但是它绝不会尝试缩小它。考虑这样的情况：一个程序通过调用一个C子程序在栈上分配一个占用10 Kb的局部数组。内核将会扩大栈段来容纳这个数组。当子程序返回的时候，这个空间理论上应由内核释放，但是它将不会被释放。解释为什么此刻有可能缩小栈，以及为什么UNIX内核实际上却没有缩小它。
1.3 如果一个新创建的子进程（进程 C）立即调用 fork 又创建了一个它自己的子进程，那么画出一幅图（采用类似图1-5的方式），显示出所有3个进程怎样共享物理存储器。假定使用了写时复制技术。如果进程C现在退出，那么共享机制会受到什么样的影响？
1.4 假设一个进程有两页正文、一页数据、三页 bss 和三页栈，如果内核使用写时复制技术，那么在 fork 期间将会为子进程分配多少物理页面？如果它不使用写时复制技术的话需要分配多少页？请解释原因。
1.5 如果一个父进程和一个子进程采用写时复制技术共享其栈段的所有页面，子进程调用一个子程序让它的栈扩大到超出所分配的空间，那么内核将动态地扩大子进程的栈。阐述这会给父进程的栈和地址空间造成的影响（如果有的话），以及为什么。
1.6 一个子进程使用写时复制技术与父进程共享它的数据段，如果它执行有缓冲的 read 系统调用，而缓冲区位于子进程的数据区内，这时将会发生什么情况？如果它代之以执行write系统调用，又会发生什么情况？
1.7 代之以使用未缓冲的（原始的）I/O来重做习题1.6。
1.8 假定一个进程正在使用一个共享库（也就是说，进程从映射到它的地址空间中的共享库获得正文和数据）。如果进程调用fork，那么内核应该怎样对待共享库的区域？假定内核支持写时复制技术。
1.9 如果一个使用共享内存的进程执行一次 fork 系统调用，那么内核应该怎样处理共享存储区？假定内核支持写时复制技术。
1.10 如果两个进程采用写时复制技术完全共享它们的地址空间，子进程用系统调用 sbrk 释放了它的部分bss，然后又有另一次sbrk调用将断开地址设定为它原来的值，那么父进程和子进程之间的写时复制关系将会是怎样的？
1.11 考虑一个进程，它执行一次系统调用exec调用了一个程序，该程序的bss段从地址0x10000开始，到地址0x20000结束。进程将值0x1234保存在位于0x15000处的字里。接下来，它执行一次系统调用 brk，将断开地址设定为 0x12000，然后再执行另一次系统调用 brk，将断开地址设定为0x18000。如果该进程现在读取地址0x15000，将会看到什么值？
1.12 如果两个进程采用写时复制技术完全共享它们的地址空间，其中一个进程退出，那么另一个进程的只读映射将会发生什么情况？
1.13 描述带有多个线程的一个进程与使用共享内存的多个进程（其中每个进程都有一个线程）之间的不同之处。
[1] Accetta,M.J.,Baron,R.V.,Bolosky,W.,Goulub,D.B.,Rashid,R.F.,Tevanian,A.,and Young,M.W.,“Mach: A New Kernel Foundation for UNIX Development,”Proceedings of the Summer USENIX Conference,July 1986,pp.93-112.
[2] Andleigh,P.K.,UNIX System Architecture,Englewood Cliffs,NJ: Prentice Hall,1990.
[3] Bach,M.J.,The Design of the UNIX Operating System,Englewood Cliffs,NJ: Prentice Hall,1986.
[4] Bic,L.,and Shaw,A.C.,The Logical Design of Operating Systems,Englewood Cliffs,NJ:Prentice Hall,1982.
[5] Bodenstab,D.E.,Houghton,T.F.,Kelleman,K.A.,Ronkin,G.,and Schan,E.P.,”UNIX Operating System Porting Experiences,”AT&T Bell Laboratories Technical Journal,Vol.63,No.8,October 1984,pp.1769-90.
[6] Bourne,S.R.,The UNIX System V Environment,Reading,MA: Addison-Wesley,1987.
[7] Coffman,E.G.,and Denning,P.J.,Operating Systems Theory,Englewood Cliffs,NJ: Prentice Hall,1973.
[8] Crowley,C.,“The Design and Implementation of a New UNIX Kernel,”Proceedings of AFIPS NCC,Vol.50,1981,pp.1079-86.
[9] Deitel,H.M.,An Introduction to Operating Systems,Reading,MA: AddisonWesley,1990.
[10] Denning,P.J.,“Virtual Memory,”ACM Computing Surverys,Vol.2,No.3,September 1970,pp.153-89.
[11] Feng,L.,ed.,UNIX SVR4.2 Operating System API Reference,Englewood Cliffs,NJ: Prentice Hall,1992.
[12] Gingell,R.A.,Moran,J.P.,and Shannon,W.A.,“Virtual Memory Architecture in SunOS,”Proceedings of the 1987 Summer USENIX Conference,June 1987,pp.81-94.
[13] Kay,J.,and Kummerfeld,B.,C Programming in a UNIX Environment,Reading,MA:Addison-Wesley,1989.
[14] Kernighan,B.W.,and Pike,R.,The UNIX Programming Environment,Englewood Cliffs,NJ:Prentice Hall,1984.
[15] Kernighan,B.W.,and Ritchie,D.M.,The C Programming Language,Second Edition,Englewood Cliffs,NJ: Prentice Hall,1988.
[16] Krakowiak,S.,Principles of Operating Systems,Cambridge,MA: M.I.T.Press,1988.
[17] Leffler,S.J.,McKusick,M.K.,Karels,M.J.,and Quarterman,J.S.,The Design and Implementation of the 4.3BSD UNIX Operating System,Reading,MA: Addison-wesley,1989.
[18] Open Software Foundation,Design of the OSF/1 Operating System,Englewood Cliffs,NJ:Prentice Hall,1993.
[19] Plauger,P.J.,The Standard Clibrary,Englewood Cliffs,NJ: Prentice Hall,1992.
[20] Ritchie,D.M.,and Thompson,K.,“The UNIX Time-sharing System,”The Bell System Technical Journal,Vol.57,No.6,July-August 1978,pp.1905-30.
[21] Ritchie,D.M.,“The Evolution of the UNIX Time-Sharing System,”AT&T Bell Laboratories Technical Journal,Vol.63,No.8,October 1984,pp.1577-94.
[22] Rochkind,M.J.,Advanced UNIX Programming,Englewood Cliffs,NJ: Prentice Hall,1985.
[23] Stevens,W.R.,Advanced Programming in the UNIX Environment,Reading,MA:Addison-Wesley,1992.
[24] Tanenbaum,A.S.,Operating Systems: Design and Implementation,Englewood Cliffs,NJ:Prentice Hall,1987.
[25] Thompson,K.,”UNIX Implementation,”The Bell System Technical Journal,Vol.57,No.6,July-August 1978,pp.1931-46.
高速缓存存储系统（cache memory system）是高速存储器，它能够利用引用的局部性来提高系统性能。本章解释了高速缓存的基本术语、规划和操作，阐述了高速缓存是如何配合主存储器运行的，以及高速缓存中的数据是如何定位的。本章还介绍了散列算法（hashing algorithm）、缺失处理（miss processing）、写策略（write policy）、替换策略（replacement policy）以及组相联（set associativity）。本章主要着眼于单处理器系统的高速缓存，多处理器高速缓存将在第三部分中进行介绍。到本章结束的时候，读者会对高速缓存的操作非常熟悉，可以在后面的章节中开始研究操作系统的问题了。
高速缓存是一种高速存储系统，它保存有主存储器很小的一个子集的内容。它的物理位置介于主存储器和CPU之间。因为它比主存储器速度快，所以如果频繁使用的指令和数据能够保存在高速缓存中供CPU存取，那么就有可能提高系统的性能。图2-1给出了包含高速缓存的一个计算机系统的逻辑框图。
高速缓存利用引用的局部性（locality of reference）来改善系统性能。引用局部性是大多数程序所表现出来的一种属性，在这些程序中，在一个特定的时间段内，程序指令和数据的一个相当小的子集被频繁地重复引用。如果能够把程序当前的局部引用保存在高速缓存中，那么程序就能执行得更快，因为高速缓存可以比主存储器更快地提供指令和数据。
高速缓存只是存储器层次结构（memory hierarchy）中的一个组成部分。这个存储结构的一端是磁盘存储器，它具有非常高的密度，很低的每位成本，而存取速度则（相对）较慢。另一端是CPU内的寄存器，在数量上只有几个，具有很高的每位成本，但是存取速度极快。随着我们从磁盘存储器过渡到寄存器，单位成本逐渐增加，存取速度逐渐加快，而密度却逐渐降低。
虚拟存储器调页系统（paging system）已经显示出只占系统中所有进程所使用的全部虚拟存储空间大小若干分之一的主存储器系统是怎样提供良好的整体性能的。引用的局部性通过只要求一个进程当前的工作集（working set）驻留内存使之成为可能，工作集是那些包含有进程当前局部引用位置的存储页面。进程地址空间的其他部分则可以保存在磁盘上，直到需要的时候再加载。
引用局部性延伸到了比工作集更细的粒度上。在一个进程工作集的页面内，肯定会有一组指令和变量在一段极短的时间内被一个程序频繁地重复引用。例如，考虑图2-2中计算矩阵a和b乘积的C代码小片段。假定a是一个m×r矩阵，而b是一个r×n矩阵，c的全部元素都初始化为0。
在这段代码执行的同时，它重复引用了3个循环内的指令、矩阵的元素以及循环计数器。这就是当这段代码在执行时程序的局部引用。由于矩阵包含的数据比寄存器能保存的数据多，因此如果没有高速缓存，CPU就不得不重复引用主存储器，从而将这部分程序的执行速度限制在了主存储器的存取时间上。
图2-2中有两种类型的局部性：时间的（temporal）和空间的（spatial）。时间局部性是程序有可能重复使用近期引用过的项的属性。例如，在执行最里面的一层循环期间，数组c的同一个元素会被引用两次，循环变量i、j和k也是如此。类似地，在所有三层循环中的指令也会被重复引用。所有这些引用都体现出了时间局部性。空间局部性是程序有可能重复使用前面附近引用过的项的属性。由于C语言中的数组都是按照行的顺序保存的，所以数组a和c都体现出了空间局部性，因为会在后面的迭代中访问到行中的下一个邻接元素。类似地，串行程序的执行表现出了高度的空间局部性。
主存储器系统速度的提高和成本的降低并不能跟上如今高速CPU的发展速度。如果CPU的速度和主存储器的存取时间远远不能平衡，这意味着存储器要比CPU执行指令以及加载和保存数据的能力慢得多，那么CPU就会受到存储器速度的限制。在这样的情况下，提高CPU的速度对于改善系统的整体性能来说几乎没有什么帮助，因为存储系统仍然是限制因素。虽然人们可以制造大规模的高速主存储器系统，它们的存取时间能够同CPU加载和保存数据的能力相媲美，但是这种存储系统对于高端大型机和超级计算机以外的系统来说往往太贵了。当今很多系统设计人员所采取的另一种选择是使用高速缓存。
通过利用细粒度的引用局部性，高速缓存能够弥补速度较慢的主存储系统和快速的 CPU 之间的鸿沟。在存储器层次结构中，每一级引用局部性的应用情况如图2-1所示。正如主存储器只保存了程序的一个子集（工作集）那样，寄存器保存了当前运算的操作数，高速缓存保存了正在工作的指令和变量集，在那之上形成了细粒度的局部引用。由于引用的局部性，高速缓存只需要拥有主存储器的很小一部分就能够发挥效用。由于它的规模相对较小，所以实际上可以使用比主存储器所采用的速度更快的存储设备，因为并不需要太多的高速缓存。于是，高速缓存的高速度与对引用局部性的利用相结合就能大幅提高系统性能，同时在经济上也很划算。
因为几乎所有的程序都体现出了局部引用特性，所以在从 PC（个人计算机）到超级计算机的各种系统上都能找到高速缓存。甚至在现今大多数微处理器芯片和内存管理单元（memory management unit，MMU）芯片上也可以找到集成的高速缓存。如果在微处理器或者MMU芯片上没有包含高速缓存，那么它一般会在主板（称为外部高速缓存）上。靠近CPU降低了CPU和高速缓存之间的存取时间。如果高速缓存位于一块独立的板卡上，从而必须通过总线来访问它，那么就会大幅增加时延（latency），从而带来系统性能上的相应损失。有些系统既使用片上高速缓存，也使用外部高速缓存。
高速缓存的大小从几个字节到数百KB都有，在大规模系统上甚至可能有1 MB以上的高速缓存。例如，今天的片上高速缓存一般介于4 KB到16 KB之间。外部高速缓存要大一些，介于128 KB到4 MB之间。随着时间的推移，高速缓存的规模正在逐步扩大。例如，Intel 80386没有片上高速缓存，80486有8 KB的高速缓存，而Pentium则有两块8 KB的高速缓存。外部高速缓存已经从MIPS R2000的64 KB增加到R4000的4 MB。
一般而言，高速缓存越大，性能提升就越多，因为有更大的一个存储子集被高速缓存起来供高速访问。正如随后的各章中将要看到的那样，高速缓存的规模并不能改变操作系统必须正确管理高速缓存的问题，而只能改变要使用的特定算法。高速缓存的性能将在2.11节里进一步讨论。
一个系统可以使用分离的指令高速缓存和数据高速缓存。这能够进一步提高系统的性能，因为CPU可以同时从指令高速缓存取得指令，而从数据高速缓存加载或者存储数据（参见2.10节）。正如第6章中将要看到的那样，可以使用多级高速缓存给存储器层次结构增加额外的层次（接下来的几章将集中介绍单级高速缓存）。
高速缓存的实现使得它们的存在对于用户程序来说基本上甚至完全地被忽略了。大多数实现的目标是隐藏高速缓存管理的全部细节，不论是硬件的还是操作系统的（在后面的章节中阐述），从而达到用户应用的可移植性。这一思路确保了无需修改程序，应用程序就可以移植到具有不同高速缓存组织、不同高速缓存规模的不同系统上，或者移植到没有高速缓存的系统上。这在当今的市场上是一个重要的好处。如此一来，程序可以像以前那样继续通过地址引用存储器。访问高速缓存不需要特殊的编码技术或者寻址模式。高速缓存可以通过控制高速缓存的硬件自动访问。一种称为物理高速缓存（physical cache）的高速缓存组织方式甚至对操作系统都是透明的。这就有可能给原本在设计上没有高速缓存的体系结构，例如IBM 370和IBM PC，增加高速缓存，同时仍然能够跟现有的系统软件保持兼容性（物理高速缓存将在第6章详细介绍）。
因为高速缓存只保存主存储器的一个子集，所以需要有几种方式来确定存储器的哪些部分当前驻留在高速缓存中。我们称存储器的那些部分被“缓存”了。这一点是通过将高速缓存中的数据用它们对应的主存储器地址进行标记（tagging）来做到的（对于指令高速缓存中的指令来说也是如此）。随后硬件就可以通过检查高速缓存中数据的标记来判断一个特定的内存位置是否被缓存了。这样，比如说当CPU请求一个它想要获取的主存储器地址时，这个地址就被发送给高速缓存，然后硬件就开始搜索高速缓存来寻找相应的数据（参见图 2-3）。如果在高速缓存中找到了它，那么就称为一次缓存命中（cache hit）。如果没有找到相应的数据，那么就称为缓存缺失（cache miss）。缓存命中与缓存缺失的频率之比就称为命中率（hit ratio），它以引用命中的百分比或者命中发生的概率（90%的命中率和 0.9 的命中概率是等价的）来表示。命中率越高，系统的性能就越好。
如果发生了一次命中，那么数据被返回给CPU，就好像它是从主存储器中读取的一样。如果没有命中，那么就把地址传递给主存储系统，在那里访问寻址单元。在这种情况下，数据既返回给CPU也返回给高速缓存。在一次缺失之后数据被保存在高速缓存中，以便利用时间局部性。此时也可以把CPU读取的一段数据周围的数据都载入高速缓存，从而也利用空间局部性（正如后面将要讨论的那样，在高速缓存缺失期间载入的数据量取决于具体实现）。因为大多数程序都表现出了局部性，所以90% 或者更高的命中率并非罕见。
在高速缓存的设计中，要考虑的重要一点是用一个标记确定多少数据。如果独立地标记高速缓存中的每一个字节的话代价太大了。因此，来自主存储器的一个或者更多连续的字被组织到一起形成了一个高速缓存行（line）或者块（block），并且给每一行关联单个标记。所以一个完整的高速缓存行是由一个标记和一段数据组成的，但是高速缓存行的大小是指数据部分的字节数（一般并不包括标记的大小）。片上高速缓存行的典型大小范围是从16字节到32字节。因为行中数据部分的字节是从连续的存储器单元来的，所以标记只需要包括第一个字节的地址即可；其他字节的地址可以用它们在行内的位置来推算。
除了地址之外，一行的标记部分还包括控制信息（control information）。标记部分始终都要加上一位，作为有效位（valid bit），表明相关的高速缓存行是否投入使用以及是否包含有效的数据。仅当有效位被置为ON且标记吻合时，才能发生缓存命中。在系统复位或者启动期间初始化高速缓存的时候，所有的有效位都被清除，因此初始情况下所有的指令和数据都取自主存储器。
在标记中保存的另一个常见的标志是修改位（modified bit）。正如 2.2.5 节所讨论的那样，当CPU把数据保存到使用写回高速缓存机制（write-back caching）的一个高速缓存中的时候就会设置这个位。在标记中也可以出现其他依赖于具体实现的信息，比如键（key），它是第4章的主题。
在发生一次高速缓存缺失的时候，就从主存储器中读取填满整个高速缓存行所需要的字节数，然后加载到高速缓存中。因为反映整行状态的只有一个有效位，所以必须这样做。例如，如果高速缓存行的大小是两个字长，那么在一次高速缓存缺失时不可能只读取CPU所引用的那一个字。如果没有读取两个字，那么高速缓存行的一半就会包含无效的数据。一般说来，从主存储器中读取附加的字并不会影响性能，因为大多数现代的主存储系统的设计都能一次读取或者写入多个字。
有些实现选择使用非常长的高速缓存行（128~256 字节或者更多）。这样做的优点是它减少了标记所需占用的存储器数量，因为一个标记现在能够覆盖更多的缓存行里数据部分的字节数。因此，为保存同等数量的数据，高速缓存所需的标记更少。长高速缓存行的缺点是，将整个行传入和传出主存储器所需要的时间开始明显变长。为了缓解这一问题，有些实现将一个高速缓存行划分成了多个子行（subline），每个子行都有它自己的有效位。于是每个子行都能独立地进行处理，就好像它是一个单独的高速缓存行一样，差别在于只有一个地址标记涵盖一行中所有的子行。这意味着所有的子行包含来自连续主存储器地址中的数据。每个子行的地址由它在整个高速缓存行中的位置和高速缓存行的标记就可以推算得到。幸运的是，子行的使用对于操作系统来说是透明的，所以它不需要成为随后讨论中的一个考虑因素。
高速缓存可以设计成通过数据或者指令的虚拟地址或是物理地址来访问。类似地，缓存标记也可以被设计成连同其他信息一起，要么含有虚拟地址，要么含有物理地址。选择虚拟地址还是物理地址在设计硬件的时候就确定下来了，并且对高速缓存管理技术有很大的影响，而操作系统必须采用这些技术对用户程序隐藏高速缓存的存在。这些复杂的问题将是后续各章的讨论主题。对于本书剩下的内容来说，不需要考虑访问高速缓存时所采用的地址类型。采用其中任何一种地址类型对于下面介绍的主题都有相同的影响。接下来的几小节只是简单地称它们为“地址”。
如果给定 CPU 想要的数据的地址，那么必须快速地搜索高速缓存来查找那个数据，因为高速缓存的全部目的就是要比主存储系统更快地返回数据。搜索技术还必须简单，以便高速硬件的实现既切合实际，又经济划算。比如说，线性搜索技术就不适用于高速缓存，因为除了最小的高速缓存之外，它们对于所有的高速缓存来说都太慢了。它们还难以在硬件上实现，因为它们需要一个状态机（state machine）或者定序器（sequencer）来保存搜索的当前状态。大多数高速缓存代之以使用一种简单的散列表（hash table）技术来进行搜索。
为了搜索一个高速缓存，来自 CPU 的地址经散列处理生成一个索引（index），这个索引指向高速缓存中的一个或者多个位置，如果相应的数据被缓存了，那么就会保存在这些位置上。和许多散列算法一样，不同的地址可能产生相同的索引值。于是必须用这些位置上的标记（它们包含着那些位置上正在高速缓存的数据的地址）和CPU所提供的地址进行比较。如果一个标记与来自CPU的地址相吻合，那么就发生一次命中；否则，就出现一次缺失。对于高速缓存来说，散列是一种很有用的技术，因为它将搜索限定在了包含一个或者多个位置的小集合中（除了在全相联的高速缓存中之外，这将在以后介绍。在全相联的高速缓存中不使用散列技术）。接下来，硬件会快速地并行搜索这些位置。对于大规模的高速缓存来说，这些技术格外重要，因为在这些高速缓存中只有足够的时间去搜索一小部分高速缓存。上述的所有活动都在硬件中执行，无需软件的介入。
因为高速缓存比主存储器小，所以在高速缓存缺失操作期间载入新数据时缓存中的一些已有的数据必须被丢弃。要丢弃的数据是根据高速缓存的替换策略（replacement policy）来进行选择的（该策略与实现有关）。一旦被选中，那么高速缓存中要丢弃的数据就被新数据所替换。和数据相关联的标记也改成新数据的地址，从而在高速缓存中正确地标识它。
高速缓存所采用的替换策略往往相当简单。虽然在存储管理和虚拟存储调页系统中所看到的页面老化（page aging）和替换（replacement）技术从理论上说也可以应用于高速缓存，但是它们在硬件上实现起来过于复杂。它们经常需要大量的状态或者历史信息，而在高速缓存中使用的昂贵的高速存储器数量有限，没有充足的空间来保存这些状态和信息。典型的高速缓存替换策略有LRU（Least Recently Used，最近最少使用）、伪LRU（pseudo-LRU，一种LRU的近似）以及随机替换。这些策略将伴随本章后面讨论的不同高速缓存组织进行介绍。幸运的是，和前面讨论过的那些高速缓存访问的方面一样，替换策略对于软件来说也是透明的。
当 CPU 保存数据的时候，大多数实现都把数据直接保存到高速缓存中。将数据保存在高速缓存中有助于改善系统性能的原因有两个：第一，由于时间局部性，被保存的数据在写入之后会被频繁地重新读取，因此就提高了命中率；第二，在高速缓存中使用的速度更快的存储设备保存数据的速度要比主存储器快，这就解放了CPU，让它能够比其他可能的方式速度更快地开始下一次数据载入或者保存操作。写入高速缓存中的数据也可以同时写入主存储器。高速缓存的写策略（write policy）也叫做更新策略（update policy），表明了数据是怎样保存到高速缓存和主存储器中的。
要把数据保存到高速缓存中，必须搜索高速缓存，看看高速缓存内是否已经包含有和写入的地址相关的数据。此刻使用了与从高速缓存中读取数据时相同的搜索技术。先考虑在保存期间出现一次命中的情况。在这里，CPU写入的数据替换了高速缓存行内的老数据，以便利用时间局部性。
虽然高速缓存是用来自 CPU 的新数据更新的，但是该数据可以写入主存储器，也可以不写入主存储器，这取决于所采用的写入策略。两种可能的写入策略是写直通（write-through）和写回（write-back）（也叫做复制回，copy-back）。如果一个高速缓存正在使用写直通策略，那么来自CPU的数据既会写入高速缓存也会写入主存储器。写直通策略得名于存储器层次结构的组成（参见图2-1），它必须“直通”过高速缓存到达主存储器。MIPS R2000/R3000和Intel用于80486的82495DX外部高速缓存控制器都使用写直通高速缓存机制。写直通策略的效果是存储器始终保持在“最新”状态，这意味着在高速缓存中的数据和存在于主存储器内的数据副本完全相同（也叫做“保持缓存一致”）。这种策略的缺点是每次来自CPU的写入操作都需要有一个主存储器周期，这有可能会降低系统的速度。
另一种策略是写回（write-back）。此时来自CPU的数据还是按照以前那样被写入高速缓存，但是并不写入主存储器，直到在行替换或者操作系统明确要求写回主存储器期间才写入主存储器。这就消除了采用写直通高速缓存机制时，如果在某个地址的数据被高速缓存，同一个地址被写入若干次时所造成的额外的主存储器周期开销。写回策略的缺点是，主存储器中的内容相对于高速缓存而言变成了“过时的”或者说不一致的。为了重获一致性，往往需要操作系统的介入。
例如，考虑采用写回高速缓存的CPU在执行一个程序中i = i + 1这条语句时会发生什么情况（假定 i 的值以前没有被高速缓存过）。如果在执行这条语句之前，i 在主存储器中的值为 1，那么当CPU试图读取i的当前值的时候，它就不会在高速缓存中命中，并且要将值1载入到高速缓存中，然后返回给CPU（图2-4a）。接着，CPU给i的值加1，把i的值2写回。写入操作导致在高速缓存中发生一次命中，并且 i 在高速缓存中的值被更新为 2。此刻写入操作完成时高速缓存中i拥有新值，但主存储器内仍然保持着i的旧值1（图2-4b）。在高速缓存内i的新值被认为相对于主存储器内的值被“修改”过了。
必须确保i在主存储器内的过时值不会被程序访问到，否则将会出现无法预测的结果。类似地，也必须确保多处理器系统上的其他进程不会使用过时的存储器内的值（这将在第三部分进行讨论）。只要 i 的新值保存在高速缓存内，那么程序就不会访问到 i 的过时值，因为程序总是可以在访问主存储器之前在高速缓存中命中。被修改的数据将保持被高速缓存，直到该行被替换为止。
在随后的缺失操作期间内的任何时刻，都可以替换写回高速缓存中的数据。被修改的数据不能被简单地丢弃，因为程序最终会在下一次引用时访问到在主存储器内的原来的过时值。因此，在替换之前，要替换的已被修改过的数据会由高速缓存硬件自动地写回到主存储器中。为了区分高速缓存中需要在替换时写回的已修改数据和不需要写回的未修改数据，在每个标记中加入了一个称为修改位（modified bit）的附加位。CPU写入数据的每一行的标记中都设置了修改位。只要在读缺失（read-miss）操作期间载入了数据，修改位就会被清除，因为数据仍然和主存储器保持同步。通过跟踪每一行的修改状态，高速缓存只需要在必要时写回高速缓存行，而无需像写直通高速缓存机制那样每次保存操作都要这样做。所以说，写回高速缓存机制的优点就是主存储器写入操作可能更少，总线操作可能更少，整体性能也就可能更好。缺点是操作系统需要好多次地把被修改的行写回存储器，以此来保持数据的完整性（在后面的章节中解释）。写回高速缓存机制实现起来也要比写直通高速缓存机制的成本更高。一般而言，写回机制的优点大于缺点，因此这项技术得以广泛使用。例如，Intel 486、Pentium的片上高速缓存和i860 XR、MIPS R4000、Motorola 88200和68040以及TI MicroSPARC和SuperSPARC（如果没有使用外部高速缓存的话）都使用写回高速缓存机制。
前面的讨论只考虑了保存来自 CPU 的数据期间在高速缓存里命中时情况。如果相反没有命中，那么采取的措施则取决于高速缓存是否支持写分配（write-allocate）。在使用写分配机制的时候，CPU保存的数据在发生高速缓存缺失的情况下始终会被写入高速缓存（也就是说，为数据分配高速缓存行），以便利用时间局部性和空间局部性的优点。要做到这一点，要执行与读缺失期间相同类型的处理。首先，替换策略选择一行要丢弃的数据，给保存新数据腾出空间。如果使用写回高速缓存机制，而且所选的要被替代的高速缓存行又被修改过，那么就必须把这一行写入到主存储器中。接着，从主存储器中读取与造成缺失的所有地址相关联的全部高速缓存行。之所以必须读取全部高速缓存行（或者子行），是因为正如2.2.1节所阐述的那样，只有一个有效位涵盖高速缓存行或者子行的状态。一旦读取了一行，那么CPU写入的数据就被插入到这一行中，并且设置这一行的高速缓存标记，以便反映出新数据的地址。如果使用了写回高速缓存机制，那么还要设置这一行的修改位。如果CPU写入数据的大小等于高速缓存行的大小（例如，把一个字保存在每行一个字的高速缓存中），那么就会跳过主存储器的读取操作，因为该行肯定要被CPU的数据所替换。MIPS R2000/R3000就是这种情况，它使用了4字节长的高速缓存行。使用写分配的其他处理器有MIPS R4000、Motorola 68040和88200、TI SuperSPARC以及Intel 80486（82495DX）的外部高速缓存。
有些高速缓存为了在硬件实现上更简单而放弃了写分配策略的局部好处。在不支持写分配策略的高速缓存中出现保存缺失的时候，数据被独自写入主存储器，而保持高速缓存的内容不变。Intel 80486和TI MicroSPARC就使用了这种技术。
在大多数情况下，写回高速缓存都使用写分配策略，但是写直通高速缓存则不然。这是由于硬件的成本问题：写分配会增加低成本的写直通方法的成本，因为在一次保存缺失期间必须读取一行再把这一行写入主存储器。写回高速缓存机制能够很好地配合写分配工作；另一方面，如果被写入的行尚未被CPU读取，那么就不会被高速缓存起来，从而导致所有这样的存储都被送往主存储器。但是，这也有例外。例如，Intel Pentium的外部高速缓存控制器（82434LX）能够配置成使用不带写分配的写回策略，MIPS R2000/R3000使用带有写分配的写直通策略。在MIPS芯片的案例中，硬件执行写分配很容易，因为每一个高速缓存行的大小只有4字节，从而不需要在发生保存缺失的情况下从存储器中读取一行。
其他的变化也是有可能的。例如，Motorola 88200上的高速缓存就使用了写回高速缓存机制，但是只要在高速缓存内发生了保存缺失时，就会更新存储器。这称为写一次（write-once），它允许高速缓存行即使刚发生对它的保存也能保持未修改状态，因为主存储器会被更新。幸运的是，对于操作系统来说，诸如这样的变化都是透明的。
现在由下面的各节探讨几种常见的高速缓存组织，它们将会有助于读者加深对刚介绍过的概念的理解。
最简单的高速缓存组织就是直接映射（direct mapped）或者单路组相联（one-way set associative）高速缓存（短语“单路组相联”的意思在下一节介绍“双路组相联”的时候就清楚了）。TI MicroSPARC的片上数据高速缓存使用的就是这种高速缓存组织。它包含有2 KB的数据高速缓存，组织成128个高速缓存行，每行16字节。在如图2-5所示的这种类型的高速缓存中，在保存数据的部分高速缓存里，以散列算法用地址计算出每行有且仅有的一个索引（也就是说，直接映射关系）。高速缓存可以当作是高速缓存行的线性数组，这些行都以散列算法计算得出的结果作为索引。在搜索期间，索引行中的标记要和地址进行比较以发现是否命中。因此，单有索引还是不够的，因为采用任何类型的散列算法都会有许多不同地址计算出相同的索引结果。在出现一次命中的时候，就从高速缓存行中提取数据，送往CPU。如果标记和地址不匹配，或者有效位没有打开（要记住有效位是和地址一起保存在标记中的控制信息），那么就出现一次缺失，因为在直接映射的高速缓存中，这是能够保存数据的唯一位置。因此没有必要进一步搜索高速缓存。
使用直接映射高速缓存机制的其他处理器有 Intel Pentium，它用于其外部高速缓存，以及MIPS R2000/R3000/R4000所支持的所有高速缓存。
直接映射高速缓存的高速缓存散列算法必须将一个来自 CPU 的给定地址转换为高速缓存中一行的索引值。因为散列算法的计算是在硬件中完成的，所以它必须既简单，速度又快。对于降低成本和获得快速实现来说，简单性是必不可少的。速度非常重要，因为需要索引在适当的高速缓存行上启动读取周期。在比较高速缓存标记，查明是否有一次命中之前，必须完成上面所有的步骤。由于有这些限制因素，所以在高速缓存中使用的散列算法很少会采用算术运算，因为这些操作会花费很长的时间。
最常用的高速缓存散列算法是取模（modulo）函数，这种函数利用了这样的事实，即在直接映射高速缓存中的行数往往是2的幂。这就使得散列算法只要从地址中选出若干位，选出的位数正好等于高速缓存行数以2为底的对数，就能直接用它们来作为索引。例如，考虑TI MicroSPARC上的数据高速缓存，它有128（27）行，每行16字节。这个配置的散列算法应当从地址中选出“位<10..4>”（从第4到第10个位），使用这7个位从高速缓存的128行中选出一行（参见图2-6）。因为每一行高速缓存有16字节，所以该地址的低4位将选择CPU寻址的高速缓存行中的若干字节。因为高速缓存总共有2 KB，所以我们能够看到这种选择索引的方法会让所有模2048的地址都索引到高速缓存中相同的行（所有和“位<10..4>”匹配的地址都生成相同的索引）。这叫做取模散列算法（modulo hashing algorithm）。
此外，产生相同索引的地址被认为有相同的颜色。如果一个高速缓存的大小是页面大小的倍数，则该高速缓存就被认为其颜色和高速缓存中的页数一样多。如果一组存储页面的地址散列到高速缓存内同一组的高速缓存行上，那么称这组存储页面有相同的颜色。高速缓存颜色是一种用来区分页面如何索引高速缓存的概念。它的用途将在7.2.3节中进一步讨论（参见图7-8，该图给出了相对于存储器中页面的高速缓存颜色）。
图2-7描述了程序的地址空间是怎样映射到高速缓存的存储器上的。因为在“位<10..4>”中拥有相同位模式的所有地址都会索引到高速缓存中相同的行，所以地址0、2048（2 KB）、4096 （4 KB）、6144（6 KB）等都将索引或者映射到高速缓存中的第0行，而地址16、2064（2 KB + 16）、4112（4 KB + 16）、6160（6 KB + 16）等都映射到第1行上。正如2.2.1节所阐述的那样，标记将会解决歧义的问题，因为它们指出了被高速缓存的数据的地址。
虽然取模散列算法是最常用的方法，但是用来选择高速缓存行的位可以取自地址中的任何部分。为了看到取模散列方法的优点，下面的例子将使用如图2-8所示的另一种散列算法。这两种散列算法之间的区别在于程序中的地址是如何索引高速缓存的。在第一个例子（图 2-6）中，连续的程序地址映射到高速缓存中的连续位置，而图2-8中的算法则导致那些在“位<18..12>”中有相同值的整个地址范围都映射到相同的高速缓存行上。因此从0x0到0xfff的所有地址都索引到高速缓存中的第0行，而从0x1000到0x1fff的所有地址都索引到第1行，依此类推。效果如图2-9所示。
虽然实现这样的映射关系是可能的，但是我们不使用它，因为它导致了高速缓存利用率的低下（这里只给出举例说明）。例如，完全处于从0x0到0x1fff地址范围内的一个小程序让其所有的引用都映射到了高速缓存的头两行上。当这个程序正在执行的时候，只使用了2 KB高速缓存中的32字节。在这样一种情况下，可能会有很低的命中率，而从高速缓存感觉不出来性能增益。
通过对比，读者可以看到图2-6所示的散列算法提供了一种地址到高速缓存的良好映射关系，能够把空间局部性扩展到最大。出于这个原因，它就是所有使用散列算法的高速缓存存储系统而选择的算法。
现在我们将迄今为止所介绍的所有概念联系起来，以展示一个查找操作如何发生的完整例子。对于这个例子来说，假定我们有一个字长为4字节、带有12位地址的系统。系统包含的直接映射高速缓存每行8字节，共计8行（为了简化示例，选择了12位的地址和一小块高速缓存。注.
对于这个例子来说，我们假定高速缓存的初始内容如图2-11所示。在这个配置中，标记部分的符号“---”表示这一行无效。在高速缓存行中数据部分的两个字被一条竖线分隔开了。在高速缓存行中的字采用高字节结尾的顺序，这意味着地址最小的字位于高速缓存行的左端。
举第一个例子，CPU将发出一次读取地址01234的操作。散列算法选择地址中的“位<5..3>”，它们给该地址一个行索引值3（参见图2-12）。
因为这是一个直接映射高速缓存，所以这个索引只和一行有关，如果这个地址的数据都在高速缓存中，那么数据就保存在这一行里。高速缓存控制硬件获得索引值，并且读取高速缓存行 3的内容。它发现有一个有效标记，并且把这个标记同地址中的标记部分（位<11..6>，即 012）相比较。地址中的标记部分和被索引的高速缓存行中的标记相吻合，因此就出现一次命中。现在，高速缓存控制器必须从高速缓存行中的数据部分选择正确的字。因为地址中的第2个位被设置了，而CPU想要让高端的字保存在高速缓存行的右边，因此想要的字是0777。
这里要理解的一件重要的事情是，对于高速缓存的标记来说没有必要包含完整的地址，因为根据地址在高速缓存中的位置就能推算出地址的一部分。这一点之所以重要是因为它减少了高速缓存行中的总位数，从而也就降低了高速缓存的成本。一般而言，标记只包括地址中散列算法不使用的位。在这个例子中，“位<5..3>”选择出了可以用来保存数据的唯一的高速缓存行。于是，用来构成高速缓存行索引的位可以从标记中省略。类似地，因为该高速缓存行包含8字节，所以地址中的低3位（<2..0>）也不需要保存在标记中。因此，在标记中只需要保存“位<11..6>”。
举第二个例子，考虑当CPU试图从地址0130读取数据时会发生什么情况。散列算法选择“位<5..3>”用于索引，如图2-13所示，这几位又等于3。
读取高速缓存行3，并且将来自地址的标记01同高速缓存中的标记012进行比较。它们并不匹配，所以就发生了一次缺失。现在必须把地址发送到主存储系统来检索数据。接着，主存储器内从地址0130开始的两个字载入到有索引的高速缓存行中。因为第2位是0，所以需要的是双字中低端的那个字，于是高速缓存行左半部分中的字被返回给CPU。
再举最后一个例子，读取地址06540会造成一次缺失，因为被索引的行（高速缓存行4）没有包含有效的标记，这会自动导致一次缺失。
图2-14总结了前面的几个例子，还给出了其他几个例子。
当出现一次高速缓存缺失的时候，必须从主存储器读取数据然后返回给CPU。数据还要载入高速缓存，以便在近期内再次引用它时可以立即得到。如果高速缓存行比一个字大，就要从主存储器中多读几个字，以便在高速缓存中载入完整的一行。此时就会造成邻接字被预取（prefetched），从而充分利用了局部引用特性。要读取完整的一行，高速缓存可能需要额外的存储器周期，也可能不需要，这取决于主存储系统的设计。为了获得最佳性能，主存储系统应该以高速缓存行的大小为单元传送数据，这称为突发模式（burst mode）的传送。这种模式能让完整的高速缓存一行在一次存储器操作中传送。没有突发模式，传送必须以更小的单元来执行，从而增加了开销。
一旦主存储器提供了所需的数据，就必须在高速缓存中找到一个位置保存它。这个位置必须经过挑选，以便散列算法在以后的查找操作期间能正确地定位高速缓存的行。在直接映射高速缓存中，这个位置是通过采用散列算法计算行中首字的地址，从而得到该行将会保存在高速缓存中什么地方的行索引值。最初检查的和发生缺失时找到的结果始终都是同一行。新行必须保存在这个位置，因为如果把它保存在高速缓存中的其他行，以后引用时就不能通过索引找到它。这是直接映射高速缓存唯一可能采用的替换策略。
如果缺失操作期间被替换的高速缓存行以前并不是有效行，那么就可以将新行的数据载入到这一行中，并且设定标记，指出数据的地址。该行的有效位也设为 ON。如果这一行以前保存着不同地址的有效数据，那么这些数据就会被丢弃，并用新行替换它们。如果采用写回高速缓存机制，而且修改了原来的数据（参见2.2.5节），那么在替换它之前必须将它写回存储器，从而不会丢失修改过的数据。
举一个例子，再次考虑2.3.2节里的例子和图2-11描绘的高速缓存。如果CPU试图读取位于00130的字，那么就会发生一次缺失，因为高速缓存内的行3缓存的是从地址01230到地址01237的数据。如果主存储器在地址00130处保存的值为0222，在地址00134处保存的值为0333，那么在处理缺失之后，高速缓存将被更新为图2-15所示的内容。
新标记和新数据替换了原来的标记和数据，高速缓存内其余的行则保持不变。CPU最初请求的数据0222在新行写入高速缓存的同时返回给CPU。
在直接映射高速缓存中，主存储器内数据的地址和高速缓存内可能保存该地址的位置或行之间具有一一对应的关系。数据在高速缓存内是通过散列该地址来定位的，计算得出了高速缓存中可以保存该数据的唯一一行的索引。直接映射高速缓存既可以使用写直通策略，也可以使用写回策略。
直接映射高速缓存是实现起来最简单的高速缓存，因为在读或者写操作期间只可能有一个搜索命中的位置。这就简化了控制逻辑，从而让实现的成本更低。遗憾的是，这也是直接映射高速缓存的缺点，因为许多不同的地址都被散列到了同一行上。对于一个带有病态引用模式的程序，其中局部引用的数据或者指令地址都产生了相同的索引或者总是位于一小组索引的集合中，这样的程序就无法从高速缓存获益，因为命中率将非常低。在这样的情况下，高速缓存行在被再次命中之前总是被替换掉，所以这种情形称为高速缓存颠簸（cache thrashing）（这个名字来源于虚拟存储调页系统中出现的相同现象）。下面一节介绍对直接映射高速缓存所做的一种改进，以此减少颠簸，提高命中率。
双路组相联高速缓存（two-way set associative cache）类似于直接映射高速缓存，不同之处在于散列函数算出的索引指向高速缓存中可能保存数据的一组带有两行的高速缓存。在同一组内，每一行高速缓存都有它自己的标记，这意味着高速缓存可以同时保存经散列算法算出相同索引的两个不同地址的数据。Intel Pentium的片上数据高速缓存就是双路组相联高速缓存。它总共保存有8 KB的数据，每行32字节。这意味着高速缓存中总共有256行（8192字节÷32字节/行），组成128组（256行÷2行/组）。图2-16描绘出了这样的一个高速缓存。
在查找操作期间，散列函数算出的索引指向一组两行可以保存数据的高速缓存。被索引的一组两行高速缓存中的标记和地址同时进行比较，以查看是否命中了两行中的某一行（组内所有行的标记并行比较，从而不会因采用串行比较而降低高速缓存的访问速度）。双路组相联高速缓存的目的是，减少直接映射高速缓存中两个不同地址经散列计算得出相同的索引值时发生的高速缓存颠簸。在双路组相联高速缓存中，这两个不同的地址都保存在高速缓存中。使用这种类型高速缓存的其他处理器还有Intel i860 XR以及80486的外部高速缓存。
现在就很清楚为什么直接映射高速缓存也称为单路组相联高速缓存了。“单路”和“双路”的说法是指每一组中高速缓存行的数量（在高速缓存内所有的组都有相同数量的行）。“相联”一词则是指实际上这一组高速缓存就是以内容编址（content-addressable）的或者说相联（associative）的一个存储器，因为它是通过对照组内高速缓存行的位置（或者地址）来检查标记的内容从而判断出一次命中的。直接映射高速缓存是n路组相联高速缓存的一种退化形式，因为每一个相联组中只有一行高速缓存。
配合双路组相联高速缓存的散列算法和配合直接映射高速缓存的散列算法相同，区别在于前者所需的位数更少，因为对于总量相同的高速缓存存储器来说，双路组相联高速缓存中的组数只有直接映射高速缓存的一半。所以用于图2-16中高速缓存的散列算法就只使用“位<11..5>”来选择组。和以前一样，“位<4..0>”选择高速缓存行内的字节（因为一行有32字节）。
替换策略稍微复杂一些。采用直接映射高速缓存时，在一次缺失操作期间，载入的高速缓存行必须放入将被索引的位置，从而可以在未来的查找操作期间找到。这一行就在散列算法所索引的高速缓存行组内。但是采用双路组相联高速缓存时，现在组内有两行都可以选择用来替换。两行中的任何一行都可以被替换，因为组内的两行在查找操作期间都可以搜索到。在理想情况下，最好替换在最长时间内不会被再次引用的行，因为这能提高高速缓存的整体命中率。遗憾的是，没有办法知道程序未来的引用模式。时间局部性表明，在组内宜采取LRU替换的做法，所以大多数实现（如Intel 80486 外部高速缓存）都利用了这种方法。这种做法不但易于实现，而且效果相当不错。给每个组加上一个额外的位（称为 MRU，代表“最近使用”）就可以实现这种方法。每次在一组内出现一次命中时，MRU 位就被更新，以反映该组内的哪一行产生了命中。当组内的一行必须被替换的时候，高速缓存首先检查其中是否有一行被标记为无效。如果有，那么就替换那一行。如果两行都是有效的，那么 MRU 位就指出上次使用的是那一行，于是就选择替换另一行。然后再更新MRU位来指出被替换的行。
双路组相联高速缓存的总结
双路组相联高速缓存通过索引带有两行的一组可能保存数据的高速缓存行，来尝试获得比直接映射高速缓存更好的高速缓存性能。双路组相联高速缓存实现起来要稍微复杂和昂贵一些，因为必须并行比较一组内两行的标记，而且需要一种更复杂的替换策略。
它相对于直接映射高速缓存的优势在于可以减少高速缓存颠簸的现象。如果在一个进程的局部引用中多个地址得出了同一个索引，那么这两个地址会同时被高速缓存，而直接映射高速缓存却一定要替换该行。注意，双路组相联高速缓存的性能绝对不会低于行数相同的直接映射高速缓存。在最差的情况下，如果程序产生地址的顺序是每个地址索引唯一一行，那么双路组相联高速缓存的性能就和直接映射高速缓存一样。另一方面，如果局部引用是由产生冗余索引的多个地址所构成的，那么双路组相联高速缓存的命中率会更高，因为它能同时缓存着产生相同索引的两个不同地址的数据。
组内的行数并没有理论上的限制；在当今的计算机中，4 路乃至更多路的组相联高速缓存也并非鲜见。例如，Motorola 68040和88200、Intel 80486和i860 XP以及TI SuperSPARC的数据高速缓存都是4路组相联高速缓存。因为在组内并没有索引机制，所以也不要求组的大小一定是2的幂。在这一点上的案例就是TI SuperSPARC的指令高速缓存，它是5路组相联高速缓存。
用于这些高速缓存的散列算法和双路组相联高速缓存所采用的散列算法是相同系列的：使用取模散列函数（modulo hashing function），该函数采用的位数等于组数以2为底的对数值。
每组两行以上的高速缓存往往并不使用严格的LRU替换，因为这样做需要的状态信息太多。常常代之以使用历史信息有限的伪LRU算法。除了68040之外，所有提到过的处理器都采用了这种技术。68040的设计人员选择省略了伪LRU算法所需的额外状态信息，而是采用了一种伪随机替换（pseudorandom replacement）策略。
在高速缓存内，组的大小可以增加到使组内的行数等于高速缓存内的全部行数。此时的高速缓存就称为全相联高速缓存（fully associative cache）。在全相联高速缓存中只有一组，它包含高速缓存中所有的行。不需要散列计算或者索引机制，因为只有一组要检查。采用任何n路组相联高速缓存时，都是并行搜索组内所有的高速缓存行。顾名思义，全相联高速缓存在每次查找的时候都要在全部高速缓存内进行搜索。
之所以需要全相联高速缓存，是因为它能够把高速缓存颠簸（thrashing）的现象减到最少，原因是在高速缓存中的任何位置都可以保存数据的任何部分。于是，从理论上来说，如果一个程序具有局部引用性的地方小于或者等于高速缓存的大小，那么它就会获得 100%的命中率，并从高速缓存得到最大可能的性能提升。
全相联高速缓存构建起来要比同等大小、但每组行数较少的高速缓存成本高，因为必须并行搜索高速缓存中的所有行。这就是全相联高速缓存很少用于指令和数据的主要原因。在使用它们的时候，通常是小规模、有特殊用途且有高度时间局部性的高速缓存，比如转换后备缓冲器（translation lookaside buffer，TLB）。TLB高速缓存最近在MMU内使用过虚拟地址到物理地址的转换。小规模、全相联的TLB比较实用，因为大多数程序都体现出了局部引用特性，这意味着工作集的转换会被多次使用。此外，因为每一次转换都映射了完整的一页数据，所以只需几个转换就能提供良好的性能。例如，TI MicroSPARC使用一个有32项的全相联TLB，而SuperSPARC有64项。Motorola 88200和所有MIPS处理器上的TLB也都是全相联高速缓存。
正如现在所看到的那样，从直接映射到全相联的所有高速缓存组织结构都遵循着相同的组成原则：每一种组织结构都有一种用于选择搜索行的算法，每一种组织结构都有一种替换算法，每一种组织结构都可以使用写直通或者写回策略，而主要的区别则在于每一组内行数的不同。在各种组成结构的一端是直接映射高速缓存，它每组只有一行。对于这种类型的高速缓存来说，以散列算法得到相同索引的所有地址必须在高速缓存中竞争一个可以保存它们的位置。直接映射高速缓存的替换策略相当简单，因为唯一的候选替换行就是散列算法索引的那一行。在各种组成结构的另一端是全相联高速缓存，它只有包括高速缓存内所有行的一个组。这种类型的高速缓存不需要散列计算，因为在每次查找操作期间都必须检查所有的行。在组比较大的高速缓存中使用LRU替换并不实用，这让随机替换成为常见的方法。
随着组的大小从单路组相联或直接映射高速缓存到全相联高速缓存逐渐增大，目标是减少多个地址散列到相同组时出现的高速缓存颠簸现象。增加组的大小可以使那些其地址产生相同索引的更多数据同时保存到高速缓存中。于是，增加组的大小有可能提高命中率和系统性能。组变大的缺点是增加了硬件成本和复杂性，因为必须并行比较被索引组内所有行的标记。实际情况是，除了最小的高速缓存之外，对所有的高速缓存来说，都要避免使用组太大的高速缓存。
所有的高速缓存实现都为操作系统提供了从高速缓存中删除数据的能力，这种功能一般称为高速缓存冲洗（cache flushing）。根据高速缓存组织结构的不同，这对于防止意外引用过时数据、保持高速缓存一致性来说可能是必不可少的功能（高速缓存一致性在多处理器系统上有更广泛的含义，这将在第三部分讨论）。一个高速缓存需要冲洗的准确时机则取决于它的组织结构，这是接下来的几章要讨论的主题。高速缓存冲洗有两种形式：使主存储器有效（validating main memory）和使高速缓存无效（invalidating cache）。
使主存储器有效的形式是指在采用写回策略的高速缓存中将修改过的数据写回到主存储器内的做法。正如2.2.5节所讨论的那样，这是由高速缓存在替换一个修改过的行期间自动完成的，但是它也可以由操作系统明确地进行控制。一次显式的使有效操作（validation operation）将把行内的数据写入主存储器，然后将高速缓存内数据的修改位关闭（因为相对于主存储系统内的副本而言不再是修改过的了）。使主存储器有效的方法还可以让操作系统随时更新主存储器到最新。这可以防止主存储器内数据的过时副本被系统中不使用高速缓存的其他部分所引用。如果操作系统指定将一个高速缓存行写回主存储器，而这一行要么不在高速缓存中，要么当前并没有被修改过，那么这个使有效操作对高速缓存什么也不做。这种类型的缓存冲洗从不需要在采用写直通策略的高速缓存上进行，因为存储器始终和高速缓存中的内容保持同步。
使高速缓存无效的形式是指，如果高速缓存中的数据被修改过，那么无需先将它写回主存储器就把它丢弃的做法。这种功能既可以用于写直通高速缓存，也可以用于写回高速缓存。操作系统使用它来丢弃高速缓存中的过时数据。如果数据在主存储器中的副本的更新与高速缓存无关，从而导致被缓存的数据副本过时，就会需要这种操作。让该数据在高速缓存中无效会造成下一次引用该数据时出现一次缺失，因此要从主存储器中重新读取该数据的正确副本。
一般而言，采用写回策略的高速缓存允许将独立的使主存储器有效和使高速缓存无效操作组合成单个操作，因为它们是一种常用的序列。在这种情况下，如果高速缓存中出现了该行，而且被修改过，那么就首先完成主存储器有效操作，于是该数据就不会丢失。在此之后往往会跟着进行一次使高速缓存无效操作。
两种高速缓存冲洗形式中的任何一种通常都能够以单行为基础来使用。大多数实现允许操作系统指定要被冲洗的数据的地址。随后在高速缓存中查找这个地址，如果命中则被冲洗掉。如果没有命中，则保持高速缓存不变。MIPS 处理器就是以这种方式工作的。有些实现可以允许一次冲洗一组地址，例如一页甚至整个高速缓存。TI MicroSPARC和SuperSPARC就允许后一种方式，它们称之为“洗净”功能。Motorola 68040和88200支持一次按行、按页面或者整个高速缓存的冲洗。
大多数实现都允许CPU绕过高速缓存直接访问主存储器，这称为无缓存的（uncached）操作。例如，如果执行一次无缓存的读取操作，那么即使地址已经在高速缓存中造成一次命中，也还是从主存储器读取数据。在这种情况下，忽略被缓存的数据，返回来自主存储器的值。在本章中提到的所有处理器都支持无缓存的访问，这项功能往往可以通过页表项（page table entry）中的一个标志位来逐页进行选择。
在访问主存储器中其值的改变与CPU写操作无关的单元（用C程序设计语言的话来说就是所谓的易失性单元，volatile location）时，采用无高速缓存操作就很有用。例如，一个映射了某个I/O 设备的状态寄存器的内存将含有根据设备的状态而变化的值。一般采用无缓存的方式来访问这类寄存器，因为一旦设备的状态发生变化，状态寄存器中被缓存的任何值都是过时的。
无缓存的访问通常可被用于任何内存引用。在频繁要求进行高速缓存冲洗以保持缓存一致性的情形中，它们也很有用，这种情形可能会降低系统性能。
将指令高速缓存和数据高速缓存分开的做法目前在计算机系统中相当常见。这种做法能够有效地使高速缓存的带宽加倍，因为它能让CPU从指令高速缓存预取指令的同时把数据载入或者保存到数据高速缓存中。图 2-17 描绘了这样的一种组织结构。本章提到的所有处理器，除了 Intel 80486之外，其片上高速缓存都有独立的指令高速缓存和数据高速缓存。
因为两块高速缓存都可以同时访问主存储器（缺失处理或者写操作），所以要由硬件来仲裁高速缓存对主存储器的访问，这对于软件来说是透明的。注意，没有办法直接把数据保存到指令高速缓存中。因此，指令高速缓存是只读高速缓存。
这种组织结构最重要的方面就是缺乏数据高速缓存和指令高速缓存之间的直接互连。如果在指令高速缓存中没有命中某个指令，那么指令高速缓存就无法到数据高速缓存中查找它。指令高速缓存始终都是从主存储器读取指令来完成缺失操作。类似地，数据高速缓存中的缺失也要从主存储器读取。把数据保存到数据高速缓存中不会影响指令高速缓存的内容。虽然这是一种最简单的实现，但是它可能会产生高速缓存的不一致性，因为主存储器的内容可能会被缓存在一个以上的地方。如果使用单一的、将指令和数据结合在一起的高速缓存，就不会出现这类不一致性。
考虑使用自身能够修改代码的程序时的情形。这类程序包括诸如 LISP 解释器这样的程序，因为对于它们来说，部分编译它们正在解释的程序并非鲜见（编译后的代码通常写入进程的数据区）。如果要执行的指令是在数据区动态生成的，那么有可能出现两种不一致性。第一，如果使用写回高速缓存机制，那么最近写的指令可能尚未写入主存储器。这意味着，如果程序试图执行这些新指令，那么指令高速缓存可能会从内存中取得过时的指令。第二，一旦动态生成的指令被缓存在指令高速缓存中，那么程序的任何写操作（以此用新指令来替换那些在指令高速缓存中的老指令）都不会对指令高速缓存造成影响。新指令将写入数据高速缓存，并且最终写入主存储器，但是指令高速缓存不知道要获取新值。它会继续执行过时的老指令，直到行替换删除这些指令为止。在这种情况下，对那些指令的下一次引用将会造成一次缺失，并且从主存储器读取新指令。
遗憾的是，操作系统不能把高速缓存隐藏起来，从而让这类程序无视高速缓存的存在，因为操作系统没有办法知道程序会在什么时候试图执行其数据空间的某个部分。唯一的解决方法是提供特殊的系统调用，以便在程序已经产生了一组它现在想要执行的指令时就通知操作系统。接着，如果在数据高速缓存中使用了写回高速缓存机制，那么操作系统就使主存储器有效，并且使指令高速缓存的内容无效（在提供特殊指令来冲洗高速缓存的体系结构上，如果应用程序能够直接执行高速缓存冲洗指令，那么就不一定要有特殊的系统调用）。对指令和数据高速缓存的冲洗通常作为分开的硬件操作来实现。
一般而言，只要操作系统需要使被缓存的数据无效来保持一致性，那么它也必须使被缓存的指令无效。各种特定的实例则取决于高速缓存的体系结构，下面的章节将讨论它们。
虽然有可能让构建的系统中的硬件自动保持指令高速缓存和数据高速缓存的同步，但是却很少这样做。这样的系统会要求每次在数据高速缓存上执行写操作的时候都检查指令高速缓存并可能使其无效。这些额外的对指令高速缓存的访问可能会干扰指令的获取操作，并使其变慢。那些能够修改自身的代码实例很少值得为其在硬件上增加复杂性。
虽然全面讨论高速缓存的性能超出了本书的范围，但还是可以做以下一些观察。首先，高速缓存的性能不仅取决于高速缓存的设计，而且取决于应用程序的引用模式。因此，必须谨慎地通过测试基准程序来判定高速缓存的性能以及一般化测试结果。虽然很容易编写一个获得 100%命中率的基准程序，但是把它们运用到实际应用中的时候，这样的结果是毫无意义的。例如，下面的程序会获得100%的高速缓存命中率：
while (1)
;
循环执行一次之后，所有的指令引用都会在高速缓存中命中。相反，下面的代码片段给一个数组中的每个元素都乘以常数 c，因而会得到相当低的高速缓存命中率（假定数组要比高速缓存大）。
for ( j=0; j < YMAX; j++)
for ( i=0; i < XMAX; i++)
matrix[i][j] *= c;
因为在C语言中，数组是按行来保存的，在使用高速缓存的时候，如果数组中一行的大小超过了高速缓存行的长度（假定一开始数组没有被高速缓存），那么每次执行最里面的语句就会出现一次缺失。这样的情形尤其糟糕，因为行很长的高速缓存会读取大量从来都不会用到的数据。互换两层 for 循环会因为空间局部性而提高性能。即使每个元素只读取一次，高速缓存每次都要读取整整一行的事实也意味着引用连续的元素可能会产生一次命中。例外的情况是那些行很小的高速缓存，像MIPS R2000/R3000，它们的每个高速缓存行只有4字节。如果数组matrix的每个元素也是4字节，那么就没有空间局部性的好处了。
即使高速缓存的性能是依赖于应用的，在直觉上还是可以有下面的结论（虽然对于所有应用来说，它们并不一定都对，但是对于包括典型UNIX命令在内的许多应用来说，它们都是正确的）。首先，写回策略比写直通策略更可取，因为程序一般会因为时间局部性而多次修改变量。即使它们没有多次修改变量，写回高速缓存机制也往往不会增加任何性能开销，因为写直通一行或者在以后替换行的时候再写回都要花费一个存储器周期。为每一行维护一个修改位并处理写回虽然增加了复杂性，但这样做是值得的。在最差的情况下，没有时间或者空间局部性可言，有写分配能力的写回策略只会多读一次高速缓存行。完全没有局部性的情形是非常少见的，所以它们不会对性能造成明显的影响。
接下来，增加组的大小一般也会有帮助。对于小规模的高速缓存（1 KB或者更小）来说这样的做法特别有用，因为即便多个地址产生了相同的索引，它也能利用更多的高速缓存。对于非常大的高速缓存（1 MB 或者更多）来说，增加组的大小就没那么重要了，因为随着行数的增加，出现一段数据替换现有的高速缓存数据的可能性也逐渐减小。
由于空间局部性，增加高速缓存行的大小一般也会对高速缓存性能有帮助。高速缓存行太长的缺点是在缺失处理期间读取数据需要开销。在小规模高速缓存的组织结构中找不到很长的高速缓存行，因为这就意味着高速缓存中的行数会更少。因此出现替换的频率就更高了。
高速缓存的性能也会受到操作系统的影响。不同的高速缓存组织结构需要不同情况的冲洗机制。有若干种技术可以用来减少必须发生的冲洗量。这很重要，因为频繁的冲洗很花时间，并且减少了有用的数据被高速缓存的时间。这些技术将在第7章里讨论。
在当今的计算机系统上可找到的各种高速缓存五花八门。它们最明显的区别体现在如下几个领域：
缓存大小；
行大小；
组大小；
写分配的使用；
替换策略；
通过虚拟还是物理地址来查找；
如何标记行（通过虚拟地址、物理地址还是其他信息）；
写直通或者写回策略。
前5项影响高速缓存的性能，而且从保持高速缓存一致性的角度来看，除了一项（组大小）之外，其他的项对操作系统都没有直接影响。偶尔必须考虑一下组的大小，这将在 3.3.2、4.2.2和4.2.6节中介绍。清单中的最后3项也影响性能，但是它们还影响操作系统。这几项决定了操作系统为了对其上运行的程序完全隐藏高速缓存的存在而需要显式执行的高速缓存冲洗操作的数量。
下面的几章介绍了四种不同的高速缓存组织结构，而且描述了在什么样的条件下操作系统必须明确执行冲洗操作。所研究的不同高速缓存组织结构在采用虚拟地址还是物理地址来查找和标记行方面会有些变化。在每种情况下还需要考虑写直通和写回高速缓存机制之间的差异。
2.1 除了I/O控制器上的设备寄存器之外，无缓存的数据还能用在其他什么地方？
2.2 请解释如果高速缓存中的有效位在系统加电复位期间没有清除将会发生什么情况？（在高速缓存中使用的存储设备加电时往往具有随机的内容。）
2.3 为什么高速缓存中的每一行都需要有它自己的标记？
2.4 为什么采用地址的“位<9..2>”来索引一个512行直接映射高速缓存的散列算法是一种不好的选择？如果高速缓存是双路组相联高速缓存又会怎样？
2.5 请解释在使用本章介绍的技术时高速缓存的行数为什么是或可能不是2的整数幂？
.散列算法吗？解释为什么是或者为什么不是。如果高速缓存是16路组相联高速缓存又会怎样？
2.7 考虑一个写回、双路组相联高速缓存，它有4096行，每行16字节。应该将哪几位用于散列算法？为什么？需要行的标记部分中的多少位来保持地址（假定使用32位地址和随机替换策略）？在标记中为地址使用最少的位数同保存全部32位地址相比，高速缓存所需的位数节省了百分之多少？
2.8 有一个7路组相联高速缓存，每行256字节，总共512组，应该使用什么样的散列算法？
2.9 考虑下面对直接映射、写直通高速缓存的组织结构的两种选择。两者都保存 2048 字节（2 KB）的数据（不包括标记和控制位）。一种组织结构是使用 4 字节的行，另一种使用32字节的行。每一种选择中，包括数据、标记和控制位在内，高速缓存总共需要多少位？讨论在两种方案之间进行选择时，应该注意的有关硬件成本和性能的折中考虑。假定系统使用32位的地址。
2.10 考虑这样一种环境，其中经常运行文本处理程序。这些程序的特征是它们经常要把字符串从一个地方复制到另一个地方，并且在缓冲区内产生字符串。在这样的环境中最好是使用写回还是写直通高速缓存机制？应该使用写分配吗？阐述理由。
2.11 描述下面一段代码的高速缓存局部性。系统使用独立的指令和数据高速缓存，两者均为8 KB双路组相联高速缓存，每行16字节。数据高速缓存使用带有写分配功能的写回策略（假定int类型是32位的）。如果行的大小增加到256字节，会发生什么样的情况？
struct {
int rec_id;
char rec_name[16];
int value;
int flags;
} array[1000];
…
int i,sum;
sum = 0;
for ( i=0; i<1000; i++)
sum += array[i].value;
2.12 一个系统采用双路组相联高速缓存，每行8字节，总共16行。高速缓存使用带有写分配功能的写回策略以及LRU替换策略。假定高速缓存内的所有行在初始时都是无效的。主存储器包含以下数据：
地址 数据
01230 33
01234 44
01270 7
01274 8
02270 67
02274 42
03270 43
03274 46
03650 100
03654 200
06730 120
06734 210
08670 10
08674 20
08600 64
08640 76
09830 333
09834 355
接着出现了下面的存储器引用（每次引用一个完整的字）：
从01234载入
把5保存到03650
从08670载入
从08674载入
从01274载入
从08670载入
把99保存到09834
把12保存到02270
从01230载入
从06730载入
从03654载入
把37保存到03654
绘制类似于图2-11的图，显示出上面列出的存储器引用完成后的高速缓存内容。包括每行修改位的状态，此外要显示出主存储器最终的内容。
2.13 一个程序通过每次将一个字保存到存储器连续的地址中来使存储器清零。观察一个系统，它采用带有写分配的写回高速缓存，在一开始被清零的存储器块并没有被高速缓存起来的时候，该系统会发生什么样的情况？假定行的大小比一个字大，第一次把数据保存到每一行中的时候会造成一次缺失，要从主存储器读取该行的内容。随后，程序把零保存到高速缓存行中，替换掉从主存储器读取的老数据。因此，读取高速缓存行是对存储器带宽的一种浪费，因为CPU从来不会读取这些数据。假定要被清零的存储器块的起始地址始终和高速缓存行的起始位置相对应，要被清除的存储量是高速缓存行大小的倍数，那么请推荐一种特殊用途的高速缓存操作，比如一条新指令，从而让存储器的填零操作效率更高。
[1] Agarwal,A.,Hennessy,J.,and Horowita,M.,“Cache Performance of Operating System and Multiprogramming Workloads,”ACM Transactions on Computer System,Vol.6,No.4,November 1988,pp.393-431.
[2] Agarwal,A.,Horowitz,M.,and Hennessy,J.,“An Analytical Cache Model,”ACM Transactions on Computer System,Vol.7,No.2,May 1989.
[3] Alexander,C.,Keshlear,W.,Cooper,F.,and Briggs,F.,“Cache Memory Performance in a UNIX Environment,”SigArch News,Vol.14,No.3,June 1986,pp.41-70.
[4] Alexandridis,N.,Design of Microprocessor Based Systems,Englewood Cliffs,NJ: Prentice Hall,1993.
[5] Alpert,D.,and Flynn,M.,“Performance Tradeoffs for Microprocessor Cache Memories,”IEEE Micro,Vol.8,No.4,August 1988,pp.44-55.
[6] Cohen,E.I.,King,G.M.,and Brady,J.T.,“Storage Hierarchies,”IBM Systems Journal,Vol.28,No.1,1989,pp.62-76.
[7] Cole,C.B.,“Advanced Cache Chips Make the 32-Bit Microprocessors Fly,”Electronics,Vol.60,No.13,June 11,1988,pp.78-9.
[8] Deville,Y.,“A Low-Cost Usage-Based Replacement Algorithm for Cache Memories,”Computer Architecture News,Vol.18,No.4,December 1990,pp.52-8.
[9] Duncombe,R.R.,“The SPUR Instruction Unit: An On-Chip Instruction Cache Memory for a High Performance VLST Multiprocessor,”Technical Report UCB/CSD 87/307,Computer Science Division,University of California,Berkeley,August 1986.
[10] Easton,M.,and Fagin,R.,“Cold Start vs.Warm Start Miss Ratios,”Communications of the ACM,Vol.21,No.10,October 1978,pp.866-72.
[11] Gecsei,J.“Determining Hit Ratios for Multilevel Hierarchies,”IBM Journal of Research and Development,Vol.18,No.4,July 1974,pp.316-27.
[12] Goodman,J.R.,“Using Cache Memory to Reduce Processor-Memory Traffic,”Proceedings of the 10th Annual Symposium on Computer Architecture,June 1983.pp.124-31.
[13] Haikala,I.J.,and Kutvonen,P.H.,“Split Cache Organizations,”Performance '84,1984,pp.459-72.
[14] Handy,J.,The Cache Memory Book,Boston,MA: Academic Press,1993.
[15] Higbie,L.,“Quick and Easy Cache Performance Analysis,”Computer Architecture News,Vol.18,No.2,June 1990,pp.33-44.
[16] Hill,M.D.,“The Case for Direct-Mapped Caches,”IEEE Computer,Vol.21,No.12,December 1988,pp.25-41.
[17] Hill,M.D.,and Smith,A.J.,“Experimental Evaluation of On-Chip Microprocessor Cache Memories,”Proceedings of the 11th Annual International Symposium on Computers Architecture,June 1984,pp.158-66.
[18] Hill,M.D.,and smith,A.J.,“Evaluating Associativity in CPU Caches,”IEEE Transactions on Computers,Vol.38,No.12,December 1989,pp.1612-30.
[19] Jouppi,N.P.,“Cache Write Policies and Performance,”Proceedings of the 20th Annual International Symposium on Computer Architecture,May 1993,pp.191-201.
[20] Laha,S.,Patel,J.H.,and Iyer,R.K.,“Accurate Low-Cost Methods for Performance Evaluation of Cache Memory Systems,”IEEE Transactions on Computers,Vol.37,No.11,November 1988,pp.1325-36.
[21] Lorin,H.,Introduction to Computer Architecture and Organization,Second Edition,New York,NY: John Wiley & Sons,1989.
[22] Mano,M.M.,Computer System Architecture,Third Edition,Englewood Cliffs,NJ: Prentice Hall,1993.
[23] Przybylski,S.A.,Cache and Memory Hierarchy Design: A Performance-Directed Approach,San Mateo,CA: Morgan Kaufmann Publishers,1990.
[24] Rao,G.S.,“Performance Analysis of Cache Memories,”Journal of the ACM,Vol.25,No.3,July 1978,pp.378-95.
[25] Short,R.T.,and Levy,H.M.,“A Simulation Study of Two-Level Caches,”Proceedings of the 15th Annual International Symposium on Computer Architecture,June 1988,pp.81-9.
[26] Smith,A.J.,“A Comparative Study of Set Associative Memory Mapping Algorithms and Their Use for Cache and Main Memory,”IEEE Transactions on Software Engineering,Vol.4,No.2,March 1978,pp.121-30.
[27] Smith,A.J.,“Sequential Program Prefetching in Memory Hierarchies,”IEEE Computer,Vol.11,No.12,December 1978,PP.7-21.
[28] Smith,A.J.,“Cache Memories,”ACM Computing Surveys,Vol.14,No.3,September 1982,pp.473-530.
[29] Smith,A.J.,“Cache Evaluation and the Impact of Workload Choice,”Proceedings of the 12th Annual International Symposium on Computer Architecture,June 1985,pp.64-73.
[30] Smith,A.J.,“Problems,Directions,and Issues in Memory Hierarchies,”Proceedings of the 18th Annual Hawaii Conference on System Sciences,1985,pp.468-76.
[31] Smith,A.J.,“Bibliography and Readings on CPU Cache Memories and Related Topics,”Computer Architecture News,Vol.14,No.1,January 1986,pp.22-42.
[32] Smith,A.J.,“Design of CPU Cache Memories,”Proceedings of the IEEE TENCON,August 1987,pp.30.2.1-30.2.10.
[33] Smith,A.J.,“Line (Block) Size Choice for CPU Cache Memories,”IEEE Transactions on Computers,Vol.36,No.9,September 1987,pp.1063-75.
[34] Stone,H.S.,High Performance Computer Architecture,Third Edition,Reading,MA:Addison-Wesley,1993.
[35] Strecker,W.D.,“Transient Behavior of Cache Memories,”ACM Transactions on Computer Systems,Vol.1,No.4,November 1983,pp.281-93.
[36] Smith,J.E.,and Goodman,J.R.,“A Study of Instruction Cache Organizations and Replacement Policies,”Proceedings of the 10th Annual International Symposium on Computer Architecture,June 1983,pp.64-73.
[37] Thiebaut,D.F.,“On the Fractal Dimension of Computer Programs and Its Application to the Prediction of the Cache Miss Ratio,”IEEE Transactions on Computers,Vol.38,No.7,July 1989,pp.1012-27.
[38] Thompson,J.G.,“Efficient Analysis of Caching Systems,”Technical Report UCB/CSD 87/374,Computer Science Division,University of California,Berkeley,October 1987.
[39] Thompson,J.G.,and Smith,A.J.,“Efficient (Stack) Algorithms for Analysis of Write-Back and Sector Memories,”ACM Transactions on Computer Systems,Vol.7,No.1,February 1989,pp.78-116.
[40] Welch,T.A.,“Memory Hierarchy Configuration Analysis,”IEEE Transactions on Computers,Vol.C-27,No.5,May 1978,pp.408-13.
