品读《现代操作系统》

本人浅读前六章，目的是把握操作系统知识体系，而不深究硬件实现，仅整理了能理解的一部分与君分享，才疏学浅，欢迎指正和补充，不胜感激

引论

什么是操作系统？

现代计算机系统由一个或多个处理器、主存、磁盘、打印机、键盘、鼠标、显示器、网络接口以及其他各种I/O设备组成，一般而言，现代计算机系统是一个复杂的系统，如果每位应用程序员都不得不掌握系统的所有细节，那就不可能再编写代码了，而且，管理这些部件并加以优化使用，是一件挑战性极强的工作。所以计算机安装了一层软件，称为操作系统。它的任务是为用户程序提供一个更好、更简单、更清晰的计算机模型，并管理刚才提到的所有设备。

计算机的两种运行模式

多数计算机有两种运行模式：内核态和用户态（目态）。软件中最基础的部分是操作系统，它运行在内核态（也称为管态、核心态）。在这个模式中，操作系统具有对所有硬件的完全访问权，可以执行及其能够运行的任何指令，软件的其余部分运行在用户态下。在用户态下，只使用了机器指令的一个子集，特别的，那些会影响机器的控制或可进行I/O操作的指令（特权指令），在用户态的程序中是禁止的。
用户接口程序（shell或GUI）处于用户态程序中的最低层次，允许用户运行其他程序，诸如web浏览器、阅读器或音乐播放器等。

中断：

中断是用户态到核心态转换的唯一途径。核心态到用户态的切换是通过执行一个特权指令，将PSW的标志位设置为用户态。

中断处理程序处理中断，一个进程被挂起后，在随后的某个时刻里，该进程再次启动时的状态必须与先前暂停时完全相同，这就意味着在挂起时该进程的所有信息都要保存下来。一个挂起的进程包括：进程的地址空间，以及对应的进程表项。
.
地址空间：通常，每个进程有一些可以使用的地址集合，典型值从0开始直到某个最大值。最简单的情形下，一个进程可拥有的最大地址空间小于主存，在这种方式下，进程可以用满其地址空间，而且内存中也有足够的空间通纳该进程。如果一个进程有比计算机主存还大的地址空间，有一种称为虚拟内存的技术，操作系统可以把部分地址空间转入主存，部分留在磁盘上，并来回交换它们。
.
系统调用：
记住下列事项是有益的。任何单CPU计算机一次只能执行一条指令。如果一个进程正在用户态运行一个用户程序，并且需要一个系统服务，比如从一个文件读数据，那么它就必须执行一个陷阱或系统调用指令，将控制转到操作系统。操作系统接着通过参数检查出所需要的调用进程。然后，它执行系统调用，并把控制返回给在系统调用后面跟随者的指令。

作为扩展机器的操作系统

操作系统的一个主要任务是隐藏硬件，呈现给程序良好、清晰、优雅、一致的抽象。
用户与用户接口所提供的抽象打交道，或者是命令行shell或者是GUI图形接口
请考虑普通的Windows桌面以及面向行的命令提示符。两者都是运行在windows操作系统上的程序，并使用了操作系统提供的抽象（比如文件），但是它们提供了非常不同的接口。

作为资源管理者的操作系统

全书章节根据这个功能展开讲解。

从这个角度看，操作系统的任务是在相互竞争的程序之间有序的控制对处理器、存储器以及其他I/O设备的分配。

操作系统历史

第一代：真空管和穿孔卡片
第二次世界大战刺激了有关计算机研究工作的爆炸性开展
在那个年代里，所有的程序设计是用纯粹的机器语言编写（甚至连汇编语言都没有），需要通过上千根电缆接到插线板上连接成电路，以便控制机器的基本功能，操作系统则从来没有听说过。

第二代：晶体管和批处理系统
晶体管的发明极大改变了整个状况
程序员首先将程序写在纸上（用fortran或者汇编语言）然后穿孔成卡片，再将卡片带到输入室，交给操作员，等待操作完成。如果需要fortran编译器，操作员还需要从文件柜中取出来读入计算机，当操作员在机房走来走去时许多时间被浪费掉了。
批处理系统出现，其思想是在输入室收集全部作业，用一台相对便宜的计算机将它们读到磁带上，然后用一台比较昂贵的计算机来完成真正的运算。在收集了大约一个小时的批量作业后，这些卡片被读进磁带，然后磁带被送到机房里并装到磁带机上。随后，操作员装入一个特殊的程序（操作系统前身），它从磁带上读入第一个作业并运行，其输出写到第二盘磁带上，而不打印。每个作业结束后，操作系统自动地从磁带上读入下一个作业并运行。当一批作业完全结束后，操作员取下输入和输出磁带，将输入磁带换成下一批作业，并把输出磁带拿到一台机器上进行脱机打印（联机打印表示给一条打印一次，脱机打印表示给多条打印一次）。
第二代计算机主要用于科学与工程计算。

第三代：集成电路和多道程序设计
使用集成电路的计算机与采用分立晶体管制造的第二代计算机相比，其性能/价格比有很大提高。
多道程序设计得到广泛应用，解决方案是内存分为几个部分，每部分存放不同的作业。可以一次读入多个作业，系统利用率大幅提升。本质上是多道批处理系统
后面出现分时操作系统：计算机以时间片为单位轮流为多个用户/作业服务，解决了人机交互问题。

第四代：个人计算机
大规模集成电路的发展导致了计算机的小型化，个人计算机时代到来
DOS操作系统出现
GUI诞生
windows诞生
个人计算机世界中另一个主要竞争者是UIX，UIX衍生Mac和Linux，Linux又衍生了Android
另一个有趣发展是，那些运行在网络操作系统和分布式操作系统的个人计算机网络的增长
在网络操作系统中，用户知道多台计算机的存在，能够登录到一台远程机器上并将文件从一台机器复制到另一台机器，每台机器都有自己本地操作系统，并有自己本地用户。网络操作系统与单处理器的操作系统没有本质区别。很明显它们需要一个网络接口控制器以及一些底层软件来驱动，同时需要一些程序来进行远程登录和远程文件访问，但这些附加成分并未改变操作系统的本质结构。目前很难到没有网络功能的操作系统了。
相反，分布式操作系统是以一种传统单处理器操作系统的形式出现在用户面前的，尽管它实际上是由多处理器组成的，用户应该不知晓自己的程序或者自己的文件处于何处，这些应该由操作系统自动和有效的处理。分布式系统通常运行一个应用在多台处理机上同时运行，因此，需要更复杂的处理器调度算法来获得最大的并行度优化。目前还停留在实验室阶段。（要注意分布式操作系统和分布式应用架构的区别）

第五代：移动计算机
在编写这本书时，谷歌公司的Android 是最主流的操作系统，而苹果公司的iOS也牢牢占据次席，然而这并不会是常态，在接下来的几年可能会发生很大变化。在智能手机领域唯一可以确定的是，长期保持在巅峰并不容易。

计算机硬件简介

这一部分相当于是对计算机组成的一个软件层面的介绍了，这里省略掉一些细节，引入了《程序是怎样跑起来》一书中内容（这本书对于不想深入组成原理的同志是很好的选择），引入了《数据库系统概念》一书中内容（对于存储器的层次结构我觉得这本书中写的更好）。

CPU：

CPU的内部由寄存器、控制器、运算器和时钟四个部分构成，各部分之间由电流信号相互连通，寄存器可以用来暂存指令、数据等处理对象；控制器负责把内存上的指令、数据读入寄存器，并根据指令的执行结果来控制整个计算机；运算器负责运算从内存读入寄存器的数据；时钟负责发出CPU开始计时的时钟信号。

对程序员来说，程序员用java等高级语言编写程序，将程序编译后转换成机器语言的文件，程序运行时，在内存中生成exe文件的副本，CPU解释并执行程序内容。

CPU中的八种寄存器（其中，程序计数器、累加计数器、标志寄存器和栈寄存器都只有一个）：
累加寄存器：存储执行运算的数据和运算后的数据
标志寄存器：条件分支和循环中使用的跳转指令，会参照当前执行的运算结果来判断是否跳转。无论运算结果是什么，标志寄存器都会将其保存。
程序计数器：若地址0100是程序运行的开始位置，windows等操作系统把程序从硬盘复制到内存后会将程序计数器设定为0100，然后程序开始运行，CPU每执行一个指令后，程序计数器的值就会自动加1。函数调用处理也是通过把程序计数器的值设定成函数的存储地址来实现的，函数调用cal指令会把调用处下一条指令的地址存储到内存中的栈中，函数调用完毕，将该地址从栈中取出，更改计数器的值。
基址寄存器：CPU会吧基址寄存器变址寄存器的值解释为实际查看的内存地址
变址寄存器：变址寄存器就相当于高级语言中的索引
通用寄存器：存储任意数据，比如在做加法的时候可以一个数存在累加寄存器中，另外一个数暂存在通用寄存器中
指令寄存器：存储指令，CPU内部使用，程序员无法通过程序对该寄存器进行读写操作。
栈寄存器：存储栈区域的起始地址。

存储器：

虽然寄存器也算存储器的一种 ，不过我们不把它划分到存储器层次中。

高速缓冲存储器：

高速缓冲存储器是最快最昂贵的存储介质。高速缓冲存储器一般很小，由计算机系统硬件来管理它的使用。它多数由硬件控制，部分主存被分隔成高速缓冲行，其典型大小为64字节，地址0-6对应高速缓冲行0，以此类推。最常用的高速缓冲行放置在CPU内部或者非常接近CPU的高速缓冲中。如果是，则称高速缓存命中，缓存满足了请求，就不需要通过总线把访问请求送往主存

主存储器（内存）：

主存储器是用于存放可处理的数据的存储介质。通用机器指令在主存储器上执行。通常所说的内存指的是计算机的主存储器，简称主存，通常指的是Random Access Memory，RAM。主存通过控制芯片等与CPU相连，主要负责存储指令和数据。主存中存储的指令和数据会随着计算机的关机而自动清除。除了主存之外，还有Read Only Memory,ROM.在工厂中就被编程完毕，然后再也不能被修改。

快闪存储器：

快闪存储器不同于主存储器的地方是在电源关闭时数据可以保存下来，闪存目前用于U盘、照相机、MP、手机，同时越来越多用于笔记本电脑（快闪存储器在作为磁盘存储器的替代品越来越多地使用，这种替代品就是所谓的固态硬盘）。

磁盘存储器：

用于长期联机存储的主要介质是磁盘。磁盘分为硬盘和软盘（已经被淘汰），所以目前讲的磁盘一般就是指硬盘，从市场角度来讲分为普通机械硬盘和固态硬盘（其实是一种闪存）。
在一个磁盘中有一个或多个金属盘片，每个盘面的两个表面都覆盖着磁性物质，信息就记录在表面上。盘片由硬金属或玻璃制成。通过反转磁性物质磁化的方向，读写头将信息磁化存储到扇区中。
当磁盘被使用时，驱动马达使磁盘以很高的恒定速度旋转（通常为每秒60/90/120/250），有一个读写头恰好位于盘片表面的上方，盘片的表面从逻辑上划分为磁道，磁道又划分为扇区。扇区是从磁盘读出和写入信息的最小单位。对于现在的磁盘，扇区大小一般为512字节。外侧的磁道比内侧的磁道拥有更多的扇区。磁盘的每个盘面的每一面都有一个读写头，读写头通过在盘面上移动来访问不同的磁道，所有的读写头都安装在一个称为磁盘臂的装置上，并且一起移动。因为所有盘片上的读写头一起移动，所以当某一个盘片的读写头在第i条磁道上时，所有其他盘片的读写头也都在格子盘片的第i条磁道上。所有盘片的第i条磁道合在一起称为第i个柱面。
磁盘控制器作为计算机系统和实际的磁盘驱动器硬件之间的接口。

光盘：

在发布软件、多媒体数据（如声音和图像）和其他电子出版物方面，光盘已经成为一种流行的介质。CD和DVD的数据传输率比磁盘的数据传输率要慢一些。目前的CD驱动器的读取速度大约是每秒-6MB，而DVD是每秒8-20MB

磁带：

尽管相对而言磁带的保存时间更长久些，并且能够存储大量的数据，但是它与磁盘和光盘相比速度较慢。更重要的是，磁带只能进行顺序存取。因此磁带不能提供辅助存储所需的随机访问，虽然在历史上，磁带是先于磁盘被作为辅助存储介质使用的。
磁带主要用于备份，存储不经常使用的数据，以及作为将数据从一个系统转到另一个系统的脱机介质。磁带还应用于存储大量数据，例如视频和图像数据，它们不需要迅速的访问，或者因为数据量太大以至于磁盘存储太昂贵。尽管磁带很便宜，磁带驱动器和磁带库的成本明显高于一张磁盘的成本，现在对于大量应用而言，较之于磁带备份，备份数据到磁盘驱动器已经成为一种划算的选择。

I/O设备

存储器也算I/O设备的一部分

I/O设备一般包括两个部分：设备控制器和设备本身。控制器是插在电路板上的一块芯片或者一组芯片，这块电路板物理的控制设备。在许多情形下，对这些设备的控制是非常复杂和具体的，所以，控制器的任务是为操作系统提供一个简单的接口。

例如，磁盘控制器可以接受一个命令从磁盘2读出11206号扇区，然后控制器把这个线性扇区号转化为柱面、扇区和磁头。磁盘控制器必须确定磁头臂应该在哪个柱面上，并对磁头臂发出指令以使其前后移动到所要求的柱面号上，接着必须等待对应的扇区转动到磁头下面并开始读出数据，随着数据从驱动器读出，要消去引导块并计算校验和。最后，还得把输入的二进制位组成字并存放到存储器中。

每类设备控制器都是不同的，所以需要不同的软件进行控制。专门与控制器对话，发出命令并接受响应的软件，称为设备驱动程序（device driver）。每个控制器厂家必须为所支持的操作系统提供相应的设备驱动程序。比如windows操作系统中有各种各样的驱动，声卡、蓝牙等等。为了能够使用设备驱动程序，必须把设备驱动程序装入操作系统中，这样它可以在核心态运行。

实现输入和输出的方式有三种。
在最简单的方式中，用户程序发出一个系统调用，内核将其翻译成一个对应设备驱动程序的过程调用。然后设备驱动程序启动I/O并在一个连续不断的循环中检查该设备，看该设备是否完成了工作。当I/O结束后，设备驱动程序把数据送到指定的地方，并返回。然后操作系统将控制返回给调用者。这种方式称为忙等待，其缺点是要占据CPU一直等到对应的I/O操作完成。
第二种方式是设备驱动程序启动设备并且让该设备在操作完成时发出一个中断。操作系统接着在需要时阻塞调用者并安排其他工作进行。当设备驱动程序检测到该设备的操作完毕时，它发出一个中断通知操作完成。
第三种方式是，为I/O使用DMA（Direct Memory Access）芯片，它可以控制在内存和某些控制器之间的位流，而无须持续的CPU干预。CPU对DMA芯片进行设置，说明要传送的字节数、有关的设备和内存地址以及操作方向，接着启动DMA。当DMA芯片完成时，它引发一个中断，其处理方式如前所述。有关DMA和I/O硬件会在第5章中具体讨论。

总线

单总线结构在小型计算机中使用了很多年，但是随着处理器和存储器速度越来越快，到了某个转折点时，单总线就很难处理总线的交通流量了，其结果是导致其他的总线出现。

启动计算机

简要启动过程如下。每台计算机上有一块双亲板（母板），在双亲板上有BIOS程序（Basic Input Output System）,在BIOS内有底层I/O软件，包括读键盘，写屏幕、进行磁盘I/O以及其他过程。现在这个程序存放在RAM中，它是非易失性的。
在计算机启动时，BIOS开始运行。它首先检查所安装的RAM数量，键盘和其他基本设备是否已经安装并正常响应。接着，它开始扫描PCIe和PCI总线并出连在上面的所有设备。即插即用设备也被记录下来。然后BIOS通过尝试存储在CMOS存储器中的设备清单决定启动设备。用户可以在系统刚启动之初后进入一个BIOS配置程序，对设备清单进行修改。典型的，如果存在CD-ROM（光盘或者USB）则系统试图从中启动，如果失败，系统将从硬盘启动。内存读入操作系统，并启动之。
然后，操作系统询问BIOS，以获得配置信息。对于每种设备，系统检查对应的设备驱动程序是否存在，如果没有，系统要求用户插入含有该设备驱动程序的CD-ROM，或者从网络上下载驱动程序。一旦有了全部的设备驱动程序，操作系统就将它们调入内核。然后初始化有关表格，创建需要的任何背景进程，并在终端上启动登录程序或GUI

操作系统大观园

大型机操作系统：
在操作系统的高端是用于大型机的操作系统，这些房间般大小的计算机仍然可以在一些大型公司的数据中心见到。这些计算机与个人计算机的主要差别是其I/O处理能力。用于大型机的操作系统主要面向多个作业的同时处理，系统主要提供三类服务：批处理、事务处理和分时。批处理系统处理不需要交互，保险公司的索赔通常是以批处理方式完成的。事务处理系统负责大量小的请求，每个业务量都很小，但是系统必须每秒处理亿级数据；分时系统允许多个远程用户同时在计算机上运行作业。

服务器操作系统：
服务器可以是大型的个人计算机，工作站，甚至是大型机。他们通过网络同时为若干用户服务，并允许用户共享硬件和软件资源。典型的服务器操作系统有Linux等。

多处理器操作系统：
windows和Linux都可以运行在多核处理器上。

个人计算机操作系统： 常见的例子是Linux、Windows、OS X，个人计算机操作系统是如此的广为人知，所以不需要再做介绍了。

掌上计算机操作系统： 这部分市场已经被google的Android系统和苹果的ios主导。

嵌入式操作系统：
嵌入式系统在用来控制设备的计算机中运行，这种设备不是一般意义上的计算机，并且不允许用户安装软件。典型的例子有微波炉、电视机、汽车、mp等。主要的嵌入式操作系统有嵌入式Linux、QX和VxWorks等。

传感器节点操作系统：
这些节点是一种可以彼此通信并且使用无线通信的微型计算机。这类传感网络可以用于建筑物周边保护、国土边界保卫、森林火灾探测、气象预测用的温度和降水测量等。

实时操作系统：
实时操作系统的特征是将时间作为关键参数。例如，在工业过程控制系统中，工厂中的实时计算机必须收集生产过程的数据并用有关数据控制机器。通常，系统必须满足严格的最终实现。分为硬实时系统和软实时系统。硬实时系统比如工业过程控制、军事等，某个动作必须在某个时刻绝对完成。软实时系统中，虽然不希望偶尔违反最终实现，但勉强可以接受，比如多媒体。

智能卡操作系统： 最小的操作系统运行在智能卡上。智能卡是一种包含一块CPU芯片的信用卡。它有非常严格的运行能耗和存储空间的限制。

操作系统体系结构

书上分的比较细，这里是一般简单的分类。

分为单内核和微内核，单内核将操作系统的主要功能模块都作为系统内核，运行在核心态，优点是高性能，缺点是内核代码庞大，结构混乱，难以维护；微内核只把基本的功能保留在内核，优点是内核功能少，结构清晰，方便维护，缺点是需要频繁在核心态和用户态之间切换，性能低。

单内核（宏内核）：windows　9x（windows95／98／ME）
微内核：AIX、MAch等
混合内核：让原本运行在用户空间的服务程序运行在内核空间。目的：提高运行效率，本质还是微内核。通用计算机上使用的大多数现代操作系统都采用这种结构，例如：Windows　T／XP／2000、Vista和WIndows7

进程与线程

由于死锁与进程线程密切相关，所以死锁一章的内容与该章放在了一起。

在任何多道程序设计中，（单）CPU由一个进程快速切换至另外一个进程，使每个进程各运行几十或几百毫秒。严格的说，在某一个瞬间，CPU只能运行一个进程，但在1秒钟内，它可能运行多个进程，这样就产生并行的错觉。有时人们说的伪并行就是指这种情形，以此来区分多处理器系统的真正硬件并行。

进程的状态

在操作系统发现进程不能继续运行下去时，发生转化1（需要I/O）。系统认为一个运行进程占用处理器的时间已经过长，决定让其他进程使用CPU时间片时，发生转换2。在系统已经让所有其他进程享有了他们应有的公平待遇而重新轮到第一个进程再次占用CPU时，会发生转换。调度程序的主要工作就是决定应当运行哪个进程、何时运行及它应该运行多长时间，这一点我们将在本章的后面部分进行讨论。当进程等待的一个外部事件发生时（比如输入到达），发生转换4。如果此时没有其他进程运行则立即出发转换，该进程便开始运行。否则该进程将处于就绪态，等待CPU轮到它运行。

进程的创建

4种主要时间会导致进程的创建
1.系统初始化
2.正在运行的程序执行了创建进程的系统调用
.用户请求创建一个新进程
.一个批处理作业的初始化

每个被启动的进程都有一个启动该进程的用户UID（User IDentification）

进程的终止

通常由下列条件引起：
1.正常退出（自愿的）
2.出错退出（自愿的）进程发现了严重错误。比如编译命令的文件不存在
.严重错误（非自愿）进程中的错误，通常由程序中的错误所致 比如1/0
4.被其他进程杀死（非自愿）某个进程执行一个系统调用通知操作系统杀死某个进程

进程的实现

为了实现进程模型，操作系统维护着一张表格，即进程表。每个进程占用一个进程表项。即进程表（PCB：process
table）。PCB表中包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程中由运行态转换到就绪态或阻塞态时必须保存的信息。从而保证该进程随后能再次启动，就像从未被中断过一样。

进程组织：
就绪队列指针：指向当前出于就绪态的进程
阻塞队列指针：指向当前阻塞态的进程，很多操作系统还会根据阻塞原因的不同，再分为多个阻塞队列。

原语：为了在进程控制状态转换时，PCB的修改、阻塞队列修改等操作执行期间不发生中断（如果中断是很危险的），使用原语进行进程控制。原语采用关中断指令和开中断指令实现。原语的执行在核心态。原语一般做三类工作：更新PCB中的信息；将PCB插入合适队列；分配/回收资源

线程

为什么要引入线程（相比进程有什么优势）？

试想一下我们要在QQ中同时视频聊天和传送文件，在没有引入线程的概念之前，CPU只能进行进程间的切换，在程序中的代码还是只能顺序执行的，引入线程的概念后，线程相当于是轻量级的进程，也是并发而不是并行执行，使得我们能够在QQ这个程序内，不停地在视频和传送文件之间切换，实现并发。同一进程内的线程切换，不需要切换进程环境，系统开销小得多。

• 进程是资源分配的基本单位，引入线程后，线程是调度的基本单位。
• 和传统进程一样，线程可以处于若干状态的任何一个：运行、阻塞、就绪或终止。
• 每个线程都有一个线程ID、线程控制块TCB
• 统一进程的线程间共享进程的资源，由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

用户级线程：由应用程序通过线程库实现，所有的线程管理工作由应用程序负责，比如你可以用java编写多线程程序，运行之由jvm虚拟机实现线程切换，操作系统内核意识不到线程的存在。
内核级线程：内核级线程的管理工作由操作系统内核完成，线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

混合实现：在同时支持用户级线程和内核级线程的系统中，可以采用两者组合的方式，将n个用户级线程映射到m个内核级线程上，此时只有内核级线程才是处理机分配的单位。

进程通信

我们来讨论一下关于进程间通信（Inter Process
Communication,IPC）的问题。第一个问题，即一个进程如何把信息传递给另一个。第二个问题，确保两个或更多的进程在关键活动中不会出现交叉，例如，在飞机订票系统中的两个进程为不同的客户试图争夺飞机上的最后一个座位。第三个问题，正确的顺序，比如如果进程A产生数据而进程B打印数据，那么B在打印之前必须等待，直到A已经产生一些数据。

在上述三个问题中，可以将三个问题要解决的问题归纳为：1.消息的传递 2.进程互斥 .进程同步

有必要说明，进程考虑的问题对于线程来说同样是适用的。第一个问题对线程而言比较容易，因为线程共享一个地址空间。另外两个问题和解决方法和进程一致。

共享存储

共享存储分为同时共享和互斥共享，许多物理设备都属于临界资源（摄像头、打印机）。此外还有许多变量、数据；内存缓冲区等都属于临界资源。

竞争条件：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race
condition），比如银行存款的更新，同一个账户同时用zfb取和ATM取钱，如果不避免竞争条件，就存在这种情况：zfb和ATM都读取到原存款，然后分别用原存款数额减取钱的数额进行更新数据库，这显然是有问题的。

怎样避免竞争条件？互斥，即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。

临界区：我们把对共享内存进行访问的程序判断称为临界区。

进程互斥的四个条件
(1) 任何两个进程的不能同时处于临界区
(2) 不应对CPU的速度和数量做任何假设
() 临界区外运行的进程不能阻塞其他进程
(4) 不能时进程无限期等待进入临界区
.

忙等待的互斥软件实现：
1.锁变量：设想有一个锁变量，其初始值为0。当一个进程想进入其临界区时，它首先测试这把锁。如果该锁的值为0，则该进程将其 设置为1并进入临界区，这把锁的值已经为1，则该进程将等待直到其值变为0。（违反条件1）
2.严格轮换法：变量turn，初始值为0，用于记录哪个进程进入临界区。开始时，进程0检查turn，发现其值为0，进入临界区。进程1也发现其值为0，进入不了。当进程0很快退出临界区并且把turn设置为1，此时两个进程都在临界区外，进程0结束了非临界区的操作回到循环开始，但是，这时进程1还在忙非临界区的操作，进程0只有等待进程把turn置为1（违反条件）

.Peterson解法：一开始，没有任何进程处于临界区中，现在进程0调用enter_region.它通过设置其数组元素和将turn置为0来标识它希望进入临界区。由于进程1并不想进入临界区，所以enter_region很快就返回。如果进程1现在调用enter_region，进程1将在此处挂起直到interested[0]成false，该事件只有进程0调用leave_region退出临界区时才会发生。

忙等待的互斥硬件实现：
1.屏蔽中断：即使用开中断和关中断指令实现，对多核处理器无效。
2.TSL
.XCHG

前面都介绍的是忙等待的互斥解法，现在来考察几条通信原语，它们在无法进入临界区时将阻塞，而不是忙等待。最简单的sleep和wakeup。sleep是一个将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒。wakeup有一个参数，即要被唤醒的进程。这两个原语称为P、V操作。

注：生产者消费者等问题一并放在了信号量之后，信号量这部分本书感觉写的很晦涩，尤其是一些表示方法和国内课本都不同 ，这里我们还是参照国内的，我在这以我的操作系统老师讲的为主。

信号量：可以分为互斥信号量和同步信号量，互斥信号量一般取值0/1，同步信号量表示剩余资源数量。原语保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。

生产者、消费者问题（有界缓冲区问题）：

两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，把信息放入缓冲区。另一个是消费者，从缓冲区中取信息。

//empty和full是同步信号量，分别表示对生产者而言有多少空位，对消费者而言可以消费的数量
//mutex是互斥量
//buffer数组表示有界缓冲区
empty= full=0 mutex=1
//生产者
i=0
while(1){	
	生产产品
	P(empty)
	P(mutex)
	往Buffer[i]放数据
	i=(i1)%n
	V(mutex)
	V(full)
}
//消费者
j=0
while(1){
	P(full)
	P(mutex)
	从Buffer[j]取数据
	j=(j1)%n
	V(mutex)
	V(empty)
	消费产品
}

//如果是缓冲区，将i=i1  j=j1即可

哲学家就餐问题：

五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。由于通心粉很滑，需要两把叉子才能夹住，相邻两个盘子之间有一把叉子。当一个哲学家觉得饿了时，他就试图分别取其左边和右边的叉子，如果成功得到了两把叉子，就开始吃饭，吃完饭后放下叉子。
.
哲学家就餐问题对于互斥访问有限资源的竞争问题一类的建模过程十分有用。

Semaphore chopstick[5]={1,1,1,1,1}
Semaphore mutex=1
while(1){
	思考；
	P(mutex)
	P(chopstick[i])
	P(chopstick[(i1)%5])
	V(mutex)
	进食
	V(chopstick[i])
	V(chopstick[(i1)%5])
}

读者/写者问题：

读者写者问题为数据库访问建立了一个模型
.
读者写者共享一组数据区，允许多个读者同时执行读操作，不允许读者、写者同时操作，不允许多个写者同时操作

读者优先
分析：mutex是读写和写写之间的互斥信号量，mr是多个读保护readcount的计数。第一次读，readcount,P(mutex),此时进入多个读，readcount,对于写P(mutex)进不去，只有在readcount==0,时 V(mutex)才能进行写操作
反过来，如果已经有进程在写，那么P(mutex)，读和写P(mutex)都进不去

//互斥信号量mutex：读写、写写
//全局变量readcount：计数器，读者个数
//互斥信号量mr：保护readcount
Semaphore mutex=1,mr=1
int readcount=0
读者
while(){
	P(mr)
	readcount
	if(readcount==1)P(mutex)
	V(mr)
	readcount--
	if(readcount==0)V(mutex)
	V(mr)
}

写者
while(1){
	P(mutex)
	写
	V(mutex)
}

写者优先
分析：第一个读者，P(wr)P(mr)，readcount，P(mutex)，V(mr)V(wr)，读，第二个读者进来P(wr)P(mr)，readcount，V(mr)V(wr)，读，第三个写者进来P(wr)，P(mutex) 写

Semaphore mutex=1,mr=1,wr=1
int readcount=0

读者
while(1){
	P(wr)
	P(mr)
	readcount
	if(readcount==1)P(mutex)
	V(mr)
	V(wr)
	读
	P(mr)
	readcount--
	if(readcount==0)V(mutex)
	V(mr)
}


写者
while(1){
	P(wr)
	P(mutex)
	写
	V(mutex)
	V(wr)
}

管道

在有了信号量和互斥量之后，进程间通信看起来就很容易了，实际是这样的吗？答案是否定的。使用信号量时要非常小心。一处很小的错误将导致很大的麻烦。这就像用汇编语言编程一样，甚至更糟，因为这里出现的错误都是竞争条件、死锁以及其他一些不可预测和不可再现的行为。
.
管程是一个编程语言概念，编译器必须要识别管程并用某种方式对其互斥做出安排。C/Pascal 以及多数其他语言都没有管程（Java有），所以指望这些编译器遵守互斥规则是不合理的。
.
与管程和信号量有关的另一个问题是，这些机制都是设计用来解决访问公共内存的一个或多个CPU上的互斥问题的。通过将信号量放在共享内存中并用TSL或XCHG来保护它们，可以避免竞争。但是：信号量太低级了，而管程在少数几种编程语言之外又无法使用，并且，这些原语均为提供机器间的信息交换方法，所以还需要其他方法。

本书对于管道讲解也比较复杂，这里内容简化为国内书籍的说法。
管道只能采用半双工通信。各个进程要互斥的访问管道，数据以字符流的形式写入管道，当管道写满时，写进程的write系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read系统调用被阻塞。如果没写满，就不允许读。如果没读空，就不允许写。

消息传递

消息传递可以分为直接通信方式和间接通信方式：
直接通信方式将消息直接挂到接收进程的消息缓冲队列上。
间接通信方式，消息要先发送到信箱中。

上面提到的其他方法就是消息传递（message passing）。这种进程间通信的方法使用两条原语send和service，它们像信号量而不像管程，是系统调用而不是语言成分。
.
消息传递系统面临着许多信号量和管程所未涉及的问题和设计难点，特别是位于网络中不同机器上的通信进程的情况。不可靠的消息传递中的成功通信问题是计算机网络中的主要研究内容。

死锁

本书死锁一章内容。

什么是死锁？

有两个进程准备分别将扫描的文档记录到蓝光光盘上。进程A请求使用扫描仪，并被授权使用。但进程B首先请求蓝光光盘刻录机，也被授权使用。现在，A请求使用蓝光光盘刻录机，但该请求在B释放蓝光光盘刻录机前会被拒绝。但是，进程B非但不放弃蓝光光盘刻录机，而且去请求扫描仪。这时两个进程都被阻塞，并且一直处于这样的状态，这种状况就是死锁。
.
除了请求独占性的I/O设备外。别的情况也可能引起死锁。例如，在一个数据库系统中，为了避免竞争，可对若干记录加锁。如果进程A对记录R1加了锁，进程B对R2加了锁，接着，这两个进程试图把对方的记录也加锁，这时也会产生死锁。
.
所以软硬件都可能出现死锁。

资源

大部分死锁都和资源有关，资源可以是硬件设备或是一组信息。
资源分为两类：可抢占的和不可抢占的。可抢占资源可以从拥有它的进程中抢占而不会有任何副作用。不可抢占资源是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢过来。总的来说，有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解，通俗点讲就是不会一直在那占着，有破坏一直占有资源的行为（主存中虚拟内存、CPU进程切换）。所以我们的重点放在不可抢占资源上。

死锁条件

互斥条件。每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待条件。已经得到了某个资源的进程可以请求新的进程。
不可抢占条件。已经分配给一个进程的资源不能强制性的被抢占，它只能被占有它的进程显式的释放。
环路等待条件。死锁发生时，系统中一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。（死锁一定有环）

死锁策略

死锁检测与恢复

死锁检测

1.如果资源分配图中没有环路，则没有死锁。
2.有环路不一定有死锁。但是如果每个资源只有一个实例（一类资源指向一个进程），则有环路一定有死锁。

注：下面检测方法来自我们老师的课件，释放只有分配边的节点，然后将释放的资源分配给其申请边，直到没有 仅有分配边的非孤立点，如果全部为孤立点，则无死锁，否则有死锁

分配边：资源R–>进程P的边

有环有死锁：图中没有 仅有分配边的非孤立进程节点，无法简化

有环无死锁：
P2为仅有分配边的非孤立进程节点，去掉R1->P2分配边(P2变成孤立节点)，多出来R1资源，给P1，P1->R1反转为R1->P1，P1变成仅有分配边的非孤立进程节点，去掉R1->P1，R2->P1（P1变成孤立节点）；去掉R2->P4（P4变为孤立节点），将P->R2反转R2->P，P变成仅有分配边的非孤立进程节点，去掉R1->P，R2->P（p变为孤立节点）。

死锁恢复

1.利用抢占恢复：在某些情况下，可能会临时将某个资源从它当前所有者那里转移给另外一个进程。用这种方法恢复通常比较困难或者说不太可能。
2.利用回滚恢复：周期性的对进程进行检查点检查。进程检查点检查就是将进程的状态写入一个文件以备以后重启。该检查点中不仅包括存储映像，还包括了资源状态，即哪些资源分配给了该进程。为了使这一过程更有效，新的检查点应该写到新文件中。
.直接杀死进程恢复

死锁避免

问题是：是否存在一种算法总能做出正确的选择从而避免死锁？答案是肯定的，但条件是必须实现获得一些特定的信息。

安全状态和不安全状态的区别是：从安全状态出发，系统能够保证所有进程都能完成，从不安全状态出发，就没有这样的保证。

死锁避免的重点是银行家算法。

银行家算法的核心思想：算法要做的是判断对请求的满足是否会导致进入不安全状态。如果是，就拒绝请求；如果满足请求后系统仍然是安全的，就予以分配。

单个资源的银行家算法：

一个小城镇的银行家，他向一客户分别承诺了一定的贷款额度。在图a中我们看到4个客户ABCD，每个客户都被授予一定数量的贷款单位，银行家知道不肯所有客户同时都需要最大贷款款额，所以只保留10个单位而不是22个单位的资金来为客户服务。这里将客户比作进程，贷款单位比作资源，银行家比作操作系统。

在某一时刻，分配如图b，银行家能够拖延除了C以外的其他请求，因而可以让C先完成，然后释放C的4个单位资源。有了这四个单位资源，银行家就可以给D或B分配所需的贷款单位，以此类推。

在某一时刻，分配如图c，空闲只剩1个单位，不能满足ABCD任何一个的全部请求，所以该状态是不安全的。不安全状态不一定引起死锁，由于客户不一定需要其最大贷款额度，但银行家不敢抱侥幸心理。

多个资源的银行家算法：

现有资源E、已分配资源P、可用资源A
1）检查一个状态是否安全的算法如下，检查右边矩阵中是否有一行，其没有满足的资源数均小于等于A，如果不存在这样的行，那么系统将会死锁，因为任何进程都无法运行结束
2）假若到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上。
）重复以上两步，或者直到所有的进程都标记为终止，其初始状态是安全的；或者所有进程的资源需求都得不到满足，此时就是发生了死锁

银行家算法几乎每本操作系统的专著都详细的描述它，很多论文的内容也围绕该算法讨论了它的不同方面。但很少有作者指出该算法虽然很有意义但缺乏使用价值，因为很少有进程能够在运行前就知道其所需资源的最大值。因此在实际中，如果有，也只有极少的系统使用银行家算法来避免死锁。关于死锁避免的研究在实际系统中的应用非常少，似乎只是为了让一些图论家有事可做罢了。

死锁预防

破坏互斥条件：如果资源不被一个进程所独占，那么死锁肯定不会产生。当然允许多个进程同时使用打印机会造成混乱，通过采用spooling技术可以允许若干个进程同时产生输出。spooling中唯一真正请求物理打印机的进程是打印机守护进程，由于守护进程绝不会请求别的资源，所以不会银打印机而产生死锁。
.
假设守护进程被设计为在所有输出进入假脱机之前就开始打印，那么如果一个输出进程在头一轮打印之后决定等待几个小时，打印机就可能空置。为了避免这种现象，一般将守护进程设计成在完整的输出文件就绪后才开始打印。
若两个进程分别占用了可用的假脱机磁盘空间的一半用于输出，而任何一个也没有完成输出，会怎么样？这种情况下，就会有两个进程，其中每一个都完成了部分的输出，但不是它们的全部输出，于是无法继续进行下去。没有一个进程能够完成，结果在磁盘上出现了死锁。尽量避免那些不是绝对必须的资源，尽量做到尽可能少的进程可以真正请求资源。
.
破坏占有并等待条件：规定所有进程在开始执行前请求所需的全部资源。
.
破坏不可抢占条件：占有资源、申请新资源无法立即得到满足，释放占有资源。
.
破坏环路等待条件：一个进程可以在任何时刻提出资源请求，但是所有请求必须按照资源编号的顺序提出。
如果两个进程AB，假设A请求i，B请求j，如果i>j,i不会请求j，如果i<j
，j不会请求i
如果多个进程，在任何时候，总有一个已分配的资源是编号最高的。占用该资源的进程不可能请求其他已经分配的各种资源。编号最高的资源始终是可用的，最终结束释放所有资源。

进程调度

当计算机系统是多道程序设计系统时，通常就会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序（scheduler）,该程序使用的算法称为调度程序。
.
尽管有一些不同，但许多适用于进程调度的处理方法也同样适用于线程调度。下面我们将首先关注适用于进程与线程两者的调度问题，然后会明确地介绍线程调度以及它所产生的独特问题。

进程行为

a为CPU密集型进程，b为I/O密集型进程

典型的计算密集型进程具有较长时间的CPU集中使用和较小频度的I/O等待。I/O密集型进程具有较短时间的CPU集中使用和频繁的I/O等待。在I/O开始后它们都花费同样的时间提出硬件请求读出磁盘块。

非抢占式调度算法在让进程运行至阻塞时，或者直到该进程自动释放。即使该进程运行数个小时，该进程也不会挂起。在处理完时钟中断后，如果没有更高优先级的进程等待到时，则被中断的进程会继续执行。
.
.
抢占式调度算法挑选一个进程，并且让该进程运行某个固定时段的最大值。如果在该时段结束时，该进程仍在运行，它就被挂起，而调度程序挑选另一个进程运行。

调度算法

调度算法共同的目标
公平： 给每个进程公平的CPU份额，相似进程应该得到相似服务，当然，不同类型的进程可以采用不同方式处理
策略强制执行： 保证规定的策略被执行
平衡： 保持系统的所有部分都忙碌，如果CPU和所有I/O设备都能够始终运行，那么相对于让某些部件空转而言，每秒钟可以完成更多的工作。

在不同的系统中，调度程序的优化是不同的。

批处理

批处理系统在商业领域仍在广泛应用，用来处理薪水册、存货清单、账目收入、账目支出、利息计算、索赔处理和其他的周期性的作业。在批处理系统中，不会有用户等待快捷响应。因此，非抢占式算法，或对每个进程都有长时间周期的抢占式算法，都是可接受的。这种处理方式减少了进程的切换从而改善了性能。

三个指标：
吞吐量：每小时最大作业数
周转时间：等待时间运行时间 平均周转时间T=（T1T2…）/n 带权周转时间Wi=(Ti/作业i运行时间)
CPU利用率：保持CPU始终忙碌

1.先来先服务（FCFS ，first com first served）
非抢占式，进程按照它们请求CPU的顺序使用CPU，因为是非抢占式，该作业不会因为运行太长时间而中断。当该进程阻塞时，就绪队列中的第一个接着运行。当在被阻塞的进程变为就绪时，排到就绪队列最后

有利于长作业，不利于短作业

2.最短作业优先（SJF，shortest job first）
非抢占式

利于短作业，不利于长作业，长作业长时间等不到调度

.最短剩余时间优先（shortest remaining time next）
抢占式 ，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新的作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要较少的时间，当前进程就被挂起，而运行新的进程。
利于短作业，不利于长作业

交互式

这里只选取书中的前三种。

在交互式用户环境中，为了避免一个进程霸占CPU拒绝为其他进程服务，抢占是必须的。服务器归于此类

两个指标：
响应时间：最小响应时间
均衡性：用户对做一件事情需要多长时间总是有一种固有的看法，当认为一个请求很复杂需要较多时间时，用户会接受这个看法，但是当认为一个请求很简单，但也需要较多的时间时，用户会急躁。

1.轮转调度（round robin）
每个进程一个时间片，允许该进程在该时间段中运行。如果时间片结束时该进程还在运行，剥夺CPU并分配给另一个进程。如果该进程在时间片结束之前阻塞或结束，则CPU立即进行切换。当一个进程用完它的时间片后，就被移到就绪队列末尾。

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

轮转调度中做了一个隐含的假设，即所有的进程 同等重要，而拥有和操作
多用户计算机系统的人对此常有不同的看法。这种将外部因素考虑在内的需要就导致了优先级调度。其基本思想很清楚：每个进程赋予一个优先级，允许优先级最高的可运行进程先运行。

分为静态优先级和动态优先级

只要存在优先级为第四类的可运行进程，按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第四类进程为空，则按照轮转法运行第三类进程。若第四类和第三类均为空，则按轮转法运行第二类进程。

.多级队列
为CPU密集型进程设置较长的时间片比频繁分给它们很少的时间片要高效（减少交换次数）。设计优先级类，属于最高优先级类的进程运行一个时间片，属于次高优先级类的进程运行2个时间片，再次一级运行4个时间片，以此类推。当一个进程用完分配的时间片后，它被移到下一类。

实时

实时限制的系统中，抢占有时是不需要的，因为进程了解它们可能会长时间得不到运行，所以通常很快的完成各自的工作并阻塞，实时系统和交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的。

两个指标：
截止时间：如果计算机正在控制一个以正常速率产生数据的设备，若一个按实时运行的数据收集进程出现失败，会导致数据丢失。
均衡性：用户对做一件事情需要多长时间总是有一种固有的看法，当认为一个请求很复杂需要较多时间时，用户会接受这个看法，但是当认为一个请求很简单，但也需要较多的时间时，用户会急躁。

实时系统通常分为硬实时和软实时，前者的含义是绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。
实时系统中的时间按照响应方式进一步分类为周期性（以规则时间间隔发生）和非周期性（发生时间不可预知）。考虑一个有三个周期性事件的软实时系统，其周期分别是100ms，200ms和500ms。如果这些事件分别需要50ms、0ms和100ms的CPU时间，那么该系统是可调度的，因为0.50.150.2<1
本书中没有讨论实时系统的算法。实时系统的调度算法可以是静态或动态的，前者在系统开始运行之前作出调度决策，后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作，而动态调度算法不需要这些限制。

线程调度

当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。在这样的系统中调度处理有本质差别，这取决于所支持的是用户级线程还是内核级线程（或混合级线程）
内核级线程只会在所在进程A所拥有的时间片内进行调度，线程间并不存在时钟中断，所以这个线程可以按其意愿任意运行多长时间。

用户级线程和内核级线程之间的差别在于性能。用户级线程的线程切换需要少量的机器指令，而内核级线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这导致了若干数量级的延迟。另一方面，在使用内核级线程时，一旦线程阻塞在I/O上就不需要想在用户级线程中那样将整个进程挂起。从进程A切换到进程 B，其代价高于运行进程 A的第二个线程（因为必须修改内存映像，清除内存高速缓存的内容），内核对此是了解的，并可运用这些信息做出决定。例如，两个在其他方面同等重要的线程，其中一个进程与刚好阻塞的线程属于同一个进程，而另一个线程处于其他的线程，那么应该倾向于前者。
另一个重要因素是用户及县城可以使用专为应用程序定制的线程调度程序。一般而言，应用定制的线程调度程序能够比内核更好的满足应用的需要。

内存管理

操作系统中管理分层存储器体系的部分称为存储管理器，它的任务是管理内存，即记录哪些内存是正在使用的，哪些内存是空闲的；在进程需要时为其分配内存，在进程使用完后释放内存
本章我们将研究几个不同的存储管理方案，涵盖非常简单的方案到非常复杂的方案。高速缓存的管理由硬件来完成，本章将介绍针对编程人员的内存模型，以及怎样优化管理内存。至于磁盘的抽象和管理，则是磁盘一章的主体。

无存储器抽象

早期的计算机都没有存储器抽象，每个程序都直接访问物理内存。在这种情况下，想在内存中同时运行两个程序是不可能的。如果一个程序在地址2000位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的。
.
计算机世界的发展总是倾向于重复历史。对染直接引用地址对于大型计算机、小型计算机、台式计算机和笔记本电脑已经成为很久远的记忆了，但是缺少存储器抽象的情况在嵌入式系统和智能卡系统中还是很常见的。现在，像洗衣机和微波炉这样的设备都已经完全被（ROM形式的）软件控制，在这些情况下，软件都采用绝对内存地址的寻址方式。在这些设备中这样能够工作是因为，所有运行的程序都是实现确定好的，用户不可能在烤面包机上自由地运行他们自己的软件。

地址空间

总之，（无存储器抽象）把物理地址暴露给进程会带来下面几个严重问题。第一，如果用户程序可以寻址内存，那么它们就可以很容易地破坏操作系统，从而使操作系统慢慢地停止运行。即使在只有一个用户进程运行的情况下，这种情况也是存在的。第二，使用这种模型，想要运行多个程序是很困难的。在个人计算机上，同时打开几个程序是很常见的，因此我们需要其他办法。

要使多个应用程序同时处于内存中并且不互相影响，需要解决两个问题：保护和重定位。一个好的办法是创造一个新的存储器抽象：地址空间。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于 其他进程的地址空间。

一个简单的解决办法是重定位（地址映射）。分为静态重定位（静态地址映射）和动态重定位（动态地址映射）。

静态地址映射，在程序进入内存时，代码中的逻辑地址全部转换成物理地址，缺点是占用连续内存空间，程序装入后不能移动。多见于早期多道批处理系统。

动态地址映射，所使用的经典办法是给每个CPU配置基址寄存器和界限寄存器。当使用基址寄存器和界限寄存器时，程序装载到内存中连续的空闲位置且装载期间无须重定位。当一个程序运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中。每次一个进程访问内存，取一条指令，读或写一个数据字，CPU硬件会在把内存发送到内存总线之前，被送到MMU中，MMU作为CPU的一部分，MMU自动把基址加到进程发送出的地址值上，把逻辑地址映射为物理内存地址。同时，它检查程序提供的地址是否等于或大于界限寄存器里的值，如果访问的地址超过了界限，就会产生错误并终止访问。
使用基址寄存器和界限寄存器重定位的缺点是，每次访问内存都需要进行加法和比较运算。

交换技术

所有进程一直保存在内存中需要巨大的内存，如果内存不够，就做不到这一点。有两种处理内存超载的通用方法。最简单的策略是 交换（swapping） 技术，即把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行就不会占用内存（尽管其中的一些进程会周期性地被唤醒以完成相关工作，然后就又进入睡眠或叫做挂起）。另一种策略是虚拟内存，该策略甚至能使程序在只有一部分被调入内存的情况下运行。本节先讨论交换技术，虚拟内存技术将在后面单独讨论。

交换技术的操作如下图，开始时内存中只有进程A，之后创建进程B和C或者从磁盘将它们调入内存。图d显示A被交换到磁盘。。然后D被调入，B被调出，最后A再次被调入。由于A位置变化，所以在它换入的时候再程序运行期间通过硬件对其地址进行定位。例如，基址寄存器和界限寄存器就适用于这种情况。

交换在内存中产生了多个空闲区，通过把所有的进程尽可能向下移动，有可能将这些小的空闲区合成一大块。该技术称为内存紧缩（memory compaction）。通常不进行这个操作，因为它要耗费大量的CPU时间。

分区存储管理

注：本书中没有写分区存储管理，我想可能这种技术太老了，但是国内的书籍中都有这部分内容。

把整个内存划分为若干大小不等的区域，操作系统占用一个区域，其它区域供系统中的多个进程共享，这种方法称为分区存储管理。

动态分区时也需要用到内存分配算法。固定分区因为分区都一样大，不需要内存分配算法。

空闲内存管理

1.使用位图的存储管理
分配内存的大小是一个重要的设计因素。分配单元越小，位图越大。但若进程的大小不是分配单元的整数倍，那么在最后一个分配单元中就有一定数量的内存被浪费了。这种方法主要的问题是，在决定把一个占k个分配单元的进程调入内存时，存储管理器必须搜索位图，在位图中出有k个连续0的串。查位图中指定长度的0串是耗时的操作，这是位图的缺点。

2.使用链表的存储管理
另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表（我们这里讨论的链表是按照地址排序的）。其中链表中的一个节点或者包含一个进程，或者是两个进程间的一块空闲区。链表的每个节点都包含以下域：空闲区或进程的指示标志，起始地址，长度和指向下一节点的指针。一个终止的进程一般有两个邻居，它们可能是进程也可能是空闲区，这就导致了图-7所示的四种组合。

内存分配算法

内存分配算法: 当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以用来为创建的进程分配内存。这里，假设存储管理器知道要为进程分配多少内存。
.
1.最简单是算法是首次适配（first fit）算法。存储器沿着链表进行搜索，直到到一个足够大的空闲区，除非空闲区，除非空闲区和要分配的空间大小正好一样，否则将空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。首次适配算法是一种速度很快的算法，因为它尽可能少的搜索链表节点。
.
2.对首次适配算法进行很小的修改就可以得到下次适配算法（next fit）。它的工作方式和首次适配算法相同，不同点是每次到合适的空闲区时都记录当时的位置，以便在下次寻空闲区时从上次结束的地方开始搜索，而不是像first fit那样每次都从头开始。
.
.另一著名的算法是最佳适配算法（best fit）。最佳适配算法搜索整个链表（从开始到结束），出能够容纳进程的最小的空闲区。最佳适配会产生大量无用的小空闲区，它比first fit和next fit浪费更多内存。
.
4.最差适配算法（worst fit），即总是分配最大的可用空闲区，使新的空闲区比较大从而可以继续使用。
.
如果为进程和空闲区维护各自独立的链表，那么这四个算法的速度都能得到提高。这样就能集中精力只检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价就是增加复杂度和内存释放速度变慢因为必须将回收的段从进程链表中删除并插入空闲区链表。
如果进程和空闲区使用不同的链表，则可以按照大小对空闲区链表排序，以提高最佳（最差）适配算法的速度，在使用最佳（最差）适配算法搜所由从小到大（由大到小）排列的空闲区链表时，则这个空闲区就是能容纳这个作业的最小的空闲区，因此是最佳（最差）适配。空闲区链表按大小排序时，首次适配算法与最佳适配算法一样快，而下次适配算法在这里则毫无意义。
.
5.另一种分配算法是快速适配算法（quick fit），它为那些常用大小的空闲区维护单独的链表。例如有一个n项的表，该表的第一项是指向大小为4KB的空闲区链表表头的指针，第二项是指向大小为8KB的空闲区链表表头的指针，第三项是指向大小为12KB的空闲区链表表头的指针，以此类推。快速适配方法寻一个指定大小的空闲区是十分迅速的，但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点，即在一个进程终止或被换出时，寻它的相邻块并查看是否可以合并的过程是非常费时的。如果不进行合并，内存将会很快分裂出大量的进程无法利用的小空闲区。

在分区存储管理中解决碎片的办法：
规定门限值：分割空闲区时，若剩余部分小于门限值，则不再分割此空闲区。
定期压缩存储空间：将所有空闲区集中到内存的一端，但这种方法的系统开销太大。

虚拟内存

程序大于内存的问题早在计算时代开始就产生了，虽然只是有限的应用领域；像科学和工程计算。在20世纪60年代所采取的解决方法是：把程序分割成许多片段，称为覆盖（overlay）。程序开始执行时，将覆盖管理模块装入内存，该管理模块立即装入并运行覆盖0。执行完成后，覆盖0通知管理模块装入覆盖1，或者占用覆盖0的上方位置（如果有空间），或者占用覆盖0（如果没有空间）。一些覆盖系统非常复杂，允许多个覆盖快同时在内存中。覆盖块存放在磁盘上，在需要时由操作系统动态换入换出。
虽然由系统完成实际的覆盖块换入换出工作，但是程序员必须把程序分割成多个片段。把一个大程序分割成小的、模块化的片段是非常枯燥的，而且非常容易出错。而且没多少程序员会这种覆盖技术。因此，没过多久，就有人到一个办法，把全部的工作交给计算机做。采用的这个办法称为虚拟内存。
虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块被称作一页或页面（page）。每一页有连续的地址空间，这些也被映射到物理内存，但并不是所有的页都必须在内存中程序才能运行。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用的一部分不再物理内存中的地址空间时（缺页中断），由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

分页存储管理

关于分页存储，书上介绍的比较复杂，这里我结合了国内比较普遍的简单说法。另外国内课本将分页分成非虚拟内存和虚拟内存，其实显然分页技术就是为了虚拟内存而服务的。这里按照本书只讨论虚拟内存的分页、分段、段页式。

页

每页从0开始编号，页内地址是相对0编址。一般，一页的大小为2的整数次幂，地址的高位部分为页号，低位部分为页内地址

在内存中按页的大小划分为大小相等的区域，称为块，本书中称为页框（page frame）。以页为单位进行分配，逻辑上相邻的页，物理上不一定相邻。（相比于分区是连续存储，分页显然并不是连续存储的）

页表

页表：登记页号和块的对应关系。每个进程建立一个页表，页表的长度和首地址存放在PCB中。运行进程的页表必须驻留在外存。

完整的页表项如下图。

在/不在位表示该页在不在内存中，这一位为1时表示该表项是有效的，可以直接使用；如果是0，则表示该表项对应的虚拟页面现在不在内存中，访问该页面会引起一个缺页中断。
.
保护（protection）位指出允许什么类型访问。最简单的形式是这个域只有一位，0表示读/写，1表示只读。一个更先进的方法是使用三位，各位分别对应是否启用读、写、执行该页面。
.
为了记录页面的使用情况（页面置换相关），引入了修改（modified）位和访问（referenced）位。在写入一页时由硬件自动设置修改位。该位在操作系统重新分配块时是分厂有用的。如果一个页面已经被修改过，则必须把它写回磁盘、如果一个页面没有被修改过，则只简单的丢弃就可以了。
.
不论读还是写，系统都会在页面被访问时设置访问位，它的值被用来帮助操作系统在发生缺页中断时选择要被淘汰的页面。不再使用的页面要比正在使用的页面更适合淘汰。这一位在即将讨论的很多页面置换算法中都会起到重要的作用。
.
最后一位用于禁止该页面被高速缓存。对于某些命令而言，保证硬件是不断地从设备中读取数据而不是访问一个旧的被高速缓存的副本。通过这一位可以禁止高速缓存。

这里由简单到复杂呈现一个页表的结构。

页地址映射：MMU中完成，是动态地址映射。映射图解如下（实际上后边需要考虑信息保护的问题，这里先只讨论怎样计算的问题）。

有了分页机制后，会因为要访问页表而引起更多次的内存访问。由于执行速度通常被CPU从内存中取指令和数据的速度所限制，所以两次访问内存才能实现一次内存访问会使性能下降一半。在这种情况下，没人会采用分页机制。解决方案是为计算机设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不再访问页表。这种设备称为转换检测缓冲区（Translation Lookaside Buffer，TLB），有时称为相联存储器或块表。它通常在MMU中，包含少量的表项，在实际中很少会超过256个数据。
现在看一下TLB是如何工作的。将一个虚拟地址放入MMU中进行转换时，硬件首先通过将该虚拟页号与TLB中所有表项同时（即并行）进行匹配，判断虚拟页面是否在其中。如果发现了一个有效的匹配并且要进行的访问操作并不违反保护位，则将页框号直接从TLB中取出而不必再访问页表。如果虚拟页号确实是在TLB中，但指令试图在一个只读页面上进行写操作，则会产生一个保护错误，就像对页表进行非法访问一样。
当虚拟页号不在TLB中，如果MMU检测到没有有效的匹配项，就会进行正常的页表查询，接着从TLB中淘汰一个表项，然后用新到的页表项代替它。这样，如果这一页面很快被再次访问，第二次访问TLB时自然将会命中而不是未命中。当一个表项被清除出TLB时，将修改位赋值到内存中的页表项，而除了访问位，其他的值不变。

更进一步的需要信息保护处理（这里的页表地址寄存器和页表长度寄存器实际上就是动态映射中的基址寄存器和界限（变址）寄存器）：

完整的请求分页流程。

两级/多级页表

页面置换算法

当发生缺页中断时，虽然可以随机地选择一个页面来置换，但是如果每次都选择不常使用的页面会提升系统的性能。如果一个被频繁使用的页面被置换出内存，很可能它在短时间内又要被调入内存，这会带来不必要的开销。人们已经从理论和实践两个方面对页面置换算法进行了深入的研究。下面我们介绍几个最重要的算法。

最优页面置换算法

有些页面在内存中，其中有一个页面将很快被访问，其他页面则可能要到10/100/1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前要执行的指令数作为标记。最优页面置换算法规定应该置换标记最大的页面。如果一个页面在800万条指令内不会被使用，另外一个页面在600万条指令内不会被使用，则置换前一个页面。这个算法是无法实现的，操作系统无法知道各个页面下一次将在什么时候被访问。
虽然无法实现，我们可以在仿真程序上运行程序，跟踪所有页面的访问情况，然后在第二次运行时利用第一次运行时收集的信息是可以实现最优页面置换算法的。用这种方式，可以通过最优页面置换算法对其他可实现算法的性能进行比较。如果操作系统达到的页面置换性能只比最优算法差1%，那么即使花费大量的精力来寻更好的算法最多也只能换来1%的性能提高。

最近未使用页面置换算法（RU，ot Recently Used）

书上的说法很含糊，这里使用国内一般说法。

使用访问位和修改位，当启动一个进程时，它的所有页面的两个位都由操作系统设置为0，访问位被定期清零，以区别最近没有被访问的页面和被访问的页面。
时钟中断不清除修改位是因为在决定一个页面是否需要写回磁盘时将用到这个信息。

eg，内存中只为用户进程分配个页框，当前即对应页号1，2，。

在T1时钟滴答中，访问页号2和页号，页号1没有被访问，访问位置为0

在T2时钟滴答中，访问页号4，由于进程无空闲页框，便产生缺页中断。系统调用RU页面置换算法，页号2和页号访问位都由1置为0，页号1访问位本身为0，所以置换页号1。调入页号4，并将页号4访问位置为1，修改页号1和页号4的状态位。

先进先出页面置换算法（FIFO，First-In First-Out）

另一种开销较小的算法是FIFO算法。由操作系统维护一个当前在内存中的页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。

第二次机会页面置换算法

FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：如图a所示（页面上的数字是装入时间），检查最老页面的访问位，如果访问位是0，name这个页面既老又没有被使用，可以立即置换掉；如果是1，就将访问位清0，并把该页面放到链表的尾端。这也算法称为第二次机会算法。如图b所示。

时钟页面置换算法（clock）

尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。
当发生缺页中断时，算法首先检查表针指向的页面，如果它的访问位就是0淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除访问位并把表针前移一个位置，知道到一个访问位为0的位置为止。

最近最少使用页面置换算法（LRU，Least Recently Used）

对最优算法的一个很好的近似是基于这样的观察：在前面一条指令中频繁使用的页面很可能在后面的几条指令中被使用。这个思想提示了一个可实现的算法：在缺页中断发生时，置换未使用时间最长的页面，这个策略称为LRU页面置换算法。

虽然LRU在理论上是可以实现的，但代价很高。为了完全实现LRU，需要在内存中维护一个页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是每次访问内存时都必须要更新整个链表。在链表中到一个页面，删除它，然后把它移动到表头是一个费时的操作，即使使用硬件实现也一样费时。

用软件模拟的FU和老化算法这里省略。

工作集页面置换算法

在单纯的分页系统里，刚启动进程时，在内存中并没有页面。在CPU试图取第一条指令时就会产生一次缺页中断，使操作系统装入后含有第一条指令的页面。一段时间后，进程需要的大部分页面都已经在内存了，进程开始在较少缺页中断的情况下运行。这个策略称为请求调页。

大部分进程都表现为一种局部性访问行为，即在进程运行的任何阶段，它都只访问较少的一部分页面。一个进程当前正在使用的页面的集合称为工作集。如果内存无法装入整个工作集，那么进程的运行过程中会产生大量的缺页中断，导致运行速度变得很缓慢，因为通常只需要几个纳秒就能完后一条指令，而从磁盘读入一个页面通常需要10毫秒。若每执行几条指令就发生一次缺页中断，那么就成这个程序发生了颠簸。
不少分页系统都设法跟踪进程的工作集，确保进程在运行以前，它的工作集就已在内存中。该方法称为工作集模型。其目的在于大大减少缺页中断率。在进程运行之前装入其工作集页面也称为预先调页（preparing）。

对该算法的描述：当发生缺页中断时，淘汰一个不在工作集中的页面。为了实现该算法，就需要一种精确的方法来确定哪些页面在工作集中。根据定义，工作集就是最近k次内存访问所使用过的集合。一种常见近似的方法是用时间代替次数。

在下图中同样有一个时钟中断会定期清除访问位。需要扫描整个页表记录仍在工作集中的生存时间最长的页面。如果扫描完整个页表没有适合淘汰的二面，在这种情况下，就淘汰生存时间最长的页面，因此这种算法是需要扫描整个页表的。

工作集时钟页面置换算法（WSClock）

当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较费时的。

每次缺页中断时，首先检查指针指向的页面。如果R位被置为1，该页面在当前时钟滴答中就被使用过，那么该页面就不适合淘汰。然后把该页面的R置为0，指针指向下一个页面。并重复该算法。如图a->b.
现在考虑指针指向R=0的页面会发生什么，参见图c。另一方面，如果此页面被修改过，将会被写。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个旧的且干净的页面可以立即使用。

如果指针经过一圈返回它的起始点会发生什么呢？这里由两种情况：
1）至少调度了一次写操作
2）没有调度过写操作
对于第一种情况，指针仅仅是不停移动，寻一个干净页面，且最终写操作会完成，它的页面会标记为干净。
对于第二种情况 ，一个简单的方法就是随便置换一个干净的页面来使用。

总结

总之，最好的两种算法是老化算法和工作集时钟算法，它们分别基于LRU和工作集。它们都具有良好的页面调度性能，可以有效地实现。也存在其他一些算法，但在实际应用中，这两种算法可能是最重要的
。

注：关于分页的设计问题书上还介绍了其它内容，这里只介绍分配策略。

全局分配和局部分配

关于这么多置换算法的一个主要问题（到目前为止我们一直在小心地回避这个问题）是，怎样在相互竞争的可运行进程之间分配内存。
.
假设发生了缺页中断，页面置换算法是在本进程内寻页面？还是考虑所有在内存中的页面？ 全局算法通常情况下工作得比局部算法好
。一些页面置换算法既适用于局部置换算法，又适用于全局置换算法。例如FIFO能将所有内存中最老的替换掉（全局），也能将当前继承的页面中最老的替换掉（局部）。相似的，LRU或是一些类似算法能够将所有内存或是当前进程中最近最少使用的页面替换掉。
另一方面，对于其他的页面置换算法，只有采用局部策略才有意义。特别是工作集和WSClock算法是针对某些特定进程的并且必须应用在这些进程的上下文中。

注：有关分页实现的问题，只选了两个重要的出来。

与分页有关的工作

操作系统要在下面的四段时间里做与分页相关的工作：进程创建时，进程执行时，缺页中断时和进程终止时。

在分页系统中创建一个新进程时，操作系统要确定程序和数据在初始时有多大，并为它们创建一个页表。操作系统还要在内存中为页表分配空间并对其初始化。当进程被换出时，页表不需要驻留在内存中，但当程序运行时，它必须在内存中。另外，操作系统要在磁盘交换区中分配空间，以便在一个进程换出时在磁盘中有放置此进程的空间。操作系统还要用程序正文和数据对交换区进行初始化，这样当新进程发生缺页中断时，可以调入需要的页面。最后，操作系统必须把有关页表和磁盘交换区的信息存储在进程表（PCB）中。

当调度一个新进程执行时，必须为新进程重置MMU，刷新TLB（块表），以清除以前的进程遗留的痕迹。进程的页表必须成为当前页表，通常可以通过复制该页表或者把一个指向它的指针放进某个硬件寄存器来完成。

当缺页中断发生时，操作系统必须通过读硬件寄存器来确定是哪个虚拟地址造成了缺页中断。通过该信息，计算出需要哪个压面，并在磁盘上定位对应的块。必须到合适的页框存放新页面，必要时需要置换老的页面。最后，还要回退程序计数器，使程序计数器指向引起缺页中断的指令，并重新执行该指令。

当进程退出的时候，操作系统必须释放进程的页表、页面和页面在硬盘上所占用的空间。如果某些页面是与其他进程共享的（涉及页面共享，这里不深入），当最后一个使用它们的进程终止的时候，才释放内存和磁盘上的页面。

缺页中断处理

现在终于可以讨论缺页中断发生的细节了。缺页中断发生时的时间顺序如下：
1）硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
2）启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统当做一个函数来调用。
）当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这个信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
4）一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻一个页面来淘汰。
5）如果选择的页框脏了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
6）一旦页框干净后（无论是立刻还是在写回磁盘后），操作系统查所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面正在被装入时，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
7）当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
8）恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
9）调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
10）该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页从来没有发生过。

注：分段和段页式内容来自我老师的PPT

分段

分段存储管理方式已成为当今所有存储管理方式的基础。

分段相比分页优点（为何引入分段）：

在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行，亦即，能从物理内存中出每个逻辑段所对应的位置，应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度，如右图所示。段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但更常见的是将段表放在内存中。分段与分页一样需要置换。

简化的段表（还有一些复杂位和分页一样的功能，这里不描述）

分段存储的逻辑地址映射如下：

请求分段处理

段页式

文件系统

就像操作系统提取处理器的概念来建立进程的抽象，以及提取物理存储器的概念来建立进程地址空间的抽象那样，我们可以用一个新的抽象—文件来解决这个问题。进程、地址空间和文件，这些抽象概念均是操作系统中最重要的概念。如果真正深入理解了这三个概念，那么读者就迈上了成为一个操作系统专家的道路。

一个磁盘一般含有几千甚至几百万个文件，每个文件是独立于其他文件的，唯一不同的是文件是对磁盘的建模。事实上如果能把每个文件看成一个地址空间，那么读者就能够理解文件的本质了。

文件是受操作系统管理的。有关文件的构造、命名、访问、使用、保护、实现和管理方法都是操作系统设计的主要内容。从总体上看，操作系统中处理文件的部分称为文件系统（file system），这就是本章的论题。

前面分别介绍文件和目录的用户接口，随后详细讨论文件系统的实现，最后介绍一些文件系统的实例。

文件

文件命名

在进程创建文件时，它给文件命名。在进程终止时，该文件依旧存在，并且其他进程可以通过这个文件名对它进行访问。
文件的具体命名规则在各个系统中是不同的。有些文件系统区分大小写字母，有些则不区分。Unix属于前一类，老的文件系统MS-DOS则属于后一类（顺便提一下，尽管MS-DOS很古老了，但它仍然非常广泛地应用于嵌入式系统，所以MS-DOS绝对没有过时）（注：我的电脑win10也不区分大小写）

win95和win98用的都是MS-DOS的文件系统，FAT-16，win98对FAT-16进行一些修改，从而称为FAT-2，但这两者是很相似的。在本章中，当提到MS_DOS或FAT文件系统的时候，除非特别指明，否则所指的就是FAT-16或FAT-2。

许多操作系统支持文件名用圆点隔开分为两部分，如。圆点后面的部分称为文件扩展名（file extension）。
在MS-DOS中，文件名由1-8个字符以及1-个字符的可选扩展名组成。
在UIX中，如果有扩展名，则扩展名长度完全由用户决定，一个文件甚至可以包含两个或更多的扩展名。如homepage.html.zip。这里html表名html格式的一个web页面，zip表示该文件已经采用zip程序压缩过。对于UIX，文件扩展名只是一种约定，更多的是提醒所有者，而不是表示传送什么信息给计算机。
与UIX相反，Windows关注扩展名且对其赋予了含义，用户可以在操作系统中注册扩展名并且规定哪个程序拥有该扩展名（设置文件打开方式）。当用户双击某个文件名时，拥有该文件扩展名的程序就启动并运行该文件。

文件结构

文件可以有多种构造方式，下图中列出了常用的三种方式。

a：无结构的字节序列，事实上操作系统并不知道也不关心文件内容是什么，操作系统看到的就是字节，其文件内容的任何含义只在用户程序中解释。UIX和Windows都采用这种方法。

b：文件是具有固定长度记录的序列，每个记录都有内部结构，把文件作为记录序列的中心思想是：读操作返回一个记录，而写操作重写或追加一个记录。现在已经没有使用这种文件系统的通用系统了。

c：文件在这种结构中由一颗记录树构成，每个记录不必具有相同的长度，记录的固定位置有一个键字段。这颗树按键排序，从而可以对特定键进行快速查。基本操作是获得具有特定键的记录。用户可以要求读取键为pony的记录，而不必关系在文件中的确切位置。用户可以在文件中添加新记录。但是用户不能决定把它添加在文件的什么位置，这是由操作系统决定的。它在一些处理商业数据的大型计算机中获得广泛应用。

文件类型

文件类型可以分为普通文件、目录文件、特殊文件。

1.普通文件（regular file）是包含有用户信息的文件

普通文件分为ASCII文件和二进制文件，ASCII文件最大的优势是可以显示和打印，还可以用任何文本编辑器进行编辑。
二进制文件打印出来是无法理解的，充满混乱字符的一张表。通常，二进制文件有一定的内部结构，使用该文件的程序才了解这种结构。

2目录文件（directory）是管理文件系统结构的系统文件。

.特殊文件，特指系统中的各类I/O设备。为了便于统一管理，系统将设备都视为文件，并按文件方式提供给用户使用，这是对这些文件的操作将由设备驱动程序来完成。

文件访问

顺序访问：进程在这些系统中可从头按顺序读取文件的全部字节或记录，但不能跳过某一些内容，也不能不按顺序读取。在存储介质是磁带而不是磁盘时，顺序访问文件是很方便的。

随机访问：当用磁盘来存储文件时，可以不按顺序读取文件中的字节或记录，或者按照关键字而不是位置来访问记录。这种能够以任何次序读取其中字节或记录的文件称作随机访问文件。如数据库系统。如果乘客打电话预定某航班机票，订票程序必须能直接访问该航班记录，而不必先读出其他航班的成千上万个记录。

有两种方法可以指示从何处开始读取文件。一种是每次read操作都给出开始读文件的位置，另一种是用一个特殊的seek操作把当前位置指针指向文件中的特定位置。UIX和Windows用的是后一种方法。

文件属性

文件都有文件名和数据，另外所有的操作系统还会保存其他与文件相关的信息。这些附加信息称为文件属性。

下图是常见的文件属性，没有一个系统拥有所有这些属性，但每个属性都在某个系统中使用。

保护、口令、创建者、所有者四个属性与文件保护相关，它们指出谁可以访问这个文件、在一些系统中，用户必须给出口令才能访问文件、文件的创建者ID、文件当前所有者

标志用于控制或启用某些属性。

记录长度、键的位置和键的长度等字段只能出现在用关键字查记录的文件里，它们提供了查关键字相关的信息。

不同的时间字段记录了文件的创建时间、最近一次访问时间以及最后一次修改时间，它们的作用不同。

当前大小字段指出了当前的文件大小。在一些老式大型机操作系统中创建文件时，要给出文件的最大长度，以便操作系统事先先按最大长度留出存储空间。工作站和个人计算机中的操作系统不需要这一个属性提示。

文件操作

以下是与文件有关的最常用的一些系统调用
create:创建不包含任何数据的文件。该调用的目的是表明文件即将建立，并设置文件的一些属性
delete：当不再需要某个文件时，必须删除该文件以释放磁盘空间。任何文件系统总有一个系统调用来删除文件。
open：在使用文件之前，必须先打开文件。open调用的目的是：把文件属性和磁盘地址表装入内存，以便后续调用的快速访问。
close：访问结束后，不再需要文件属性和磁盘地址，这时应该关闭文件以释放内部表空间。很多系统限制进程打开文件的个数，以鼓励用户关闭不再使用的文件。磁盘以块为单位写入。关闭文件时，写入该文件的最后一块，即使这个块还没有满。
read：在文件中读取数据。一般地，读取的数据来自文件的当前位置。调用者必须指明需要读取多少数据，并且提供存放这些数据的缓冲区。
write：向文件中写数据，写操作一般也是从文件当前位置开始。如果当前位置是文件末尾，文件长度增加。如果当前位置在文件中间，则现有数据被覆盖，并且永远丢失。
append：此调用是write的限制形式，它只能在文件末尾添加数据。若系统只提供最小系统调用集合，则通常没有append。很多系统对同一操作提供了多种实现方法，这些系统中有时有append调用。
seek：对于随机访问文件，要指定从何处开始获取数据，通常的方法是用seek系统调用把当前位置指针指向文件定位置。seek调用结束后，就可以从该位置开始读写数据了。
get attributes：进程运行通常需要读取文件属性。
set attributes：某些属性是可由用户设置的，甚至是在文件创建之后，实现该功能的是set attributes系统调用。大多数标志属于此类属性。
rename：用户尝尝要改变已有文件的名字，rename系统调用用于这一目的。

目录

一级目录系统

目录系统的最简单形式是在一个目录中包含所有的文件。这有时称为根目录，但是由于只有一个目录，所以其名称并不重要。这一设计的优点在于简单，并且能够快速定位文件，这种目录系统经常用于简单的嵌入式装置中，诸如电话、数码相机以及一些便携式音乐播放器等。

层次目录系统

对于简单的特殊应用而言，单层目录是合适的，但是现在的用户有着数以千计的文件，如果所有的文件都在一个目录中，寻文件就很困难。这样，就需要有一种方式将相关的文件组合在一起。这里所需要的的是层次结构（即一个目录树）。通过这种方式，可以用很多目录把文件以自然的方式分组。如果多个用户共享一个文件服务器，如公司内部网络系统（下图），每个用户可以为自己的目录树拥有自己的私人根目录。

用户可以创建任意数量的子目录，这为用户组织其工作提供了强大的结构化工具。因此，几乎所有现代文件系统都是用这个方式组织的。

路径名

路径名分为绝对路径名和相对路径名

绝对路径名由从根目录到文件的路径组成。
windows中 cd D:\MyeclipseWorkspace\MyEclipse Professional 2014\Client\src
UIX or Linux cd /usr/local

相对路径名常和工作目录（即当前目录）一起使用。
Windows中 如果当前工作目录是 D:\MyeclipseWorkspace\MyEclipse Professional 2014，那么可以通过cd Client\src来表示。
Unix or Linux 如果当前工作目录是/usr，那么可以通过cd local来表示

支持层次目录结构的大多数操作系统在每个目录中有两个特殊的目录项 . 和 ..
常读作dot和dotdot。dot指当前目录，dotdot指父目录，可以使用 .. 来调用当前工作目录的父目录目录下的其他目录。

目录操作

不同系统中管理目录的系统调用的差别比管理文件的系统调用的差别大。下面给出UIX的例子

create：创建目录除了目录项 . 和 .. 外，目录内容为空。目录项 . 和 .. 是由操作系统创建的（有时通过mkdir完成）。
delete：删除目录。只有空目录可以删除。只包含目录项 . 和 .. 的被认为是空目录。
opendir：目录系统可被读取。为列出目录中全部文件，程序必须先打开该目录，然后读取全部文件的文件名。与打开和读文件相同，在读目录之前，必须打开目录。
closedir：系统调用readdir返回打开目录的下一个目录项。
rename：同文件一样，给目录换名
link：链接技术在允许在多个目录中出现同一个文件。这个系统调用指定一个存在的文件和一个路径名，并建立从该文件到路径所指名字的链接。这样，可以在多个目录中出现同一个文件。
unlink：删除目录项。unlink就是UIX系统中文件系统的删除操作。

实现

现在从用户角度转到实现者角度来考察文件系统。用户关心的是文件是怎样命名的 、可以进行哪些操作、目录树是什么样的以及类似的表面问题。而实现者感兴趣的是文件和目录是怎样存储的、磁盘空间是怎样管理的以及怎样使系统有效而可靠的工作的（注：管理优化后面单独讨论）。

文件系统布局

文件系统存放在磁盘上。多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。 磁盘的0号扇区称为主引导记录（Master Boot Record，MBR），用来引导计算机。在MBR的结尾是分区表。该表给出了每个分区的起始和结束地址。
在计算机被引导时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入它的第一个块，称为引导块（boot block）并执行之。引导块中的程序将装载该分区中的操作系统（如果操作系统在该分区中）。
在每个磁盘分区中，文件系统经常包含有如图所列的一些项目。第一个是超级块（superblock），超级块包含文件系统的所有关键参数，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。超级块中的典型信息包括：确定文件系统类型用的魔数、文件系统中块的数量以及其他重要的管理信息。接着是文件系统中空闲块的信息，可以用位图或指针列表的形式给出。后面也许跟随的是一组i节点，这是一个数组，每个文件一个，i节点说明了该文件的方方面面。接着可能是根目录，它存放文件系统目录树的根部。最后，该分区的其他部分存放了其他所有的目录和文件。

文件实现

简单分配

把每个文件作为一连串连续数据块存储在磁盘上。所以，在块大小为1KB的磁盘上，50KB的文件需要分配50个连续的块。对于块大小为2KB的磁盘，将分配25个连续的块。每个文件都从一个新的块开始，如果文件A实际上只有1/2块，那么最后一块的结尾会浪费一些空间。

连续磁盘空间分配方案有两大优势：首先，实现简单，记录每个文件用到的磁盘块简化为记住两个数字即可：第一块的磁盘地址和文件的块数。给定了第一块的编号，一个简单的加法就可以到任何其他块的编号
其次，读操作性能好，只需要一次寻（到第一个块），之后不再需要寻道和旋转延迟，数据以磁盘全带宽。

连续分配方案同样有相当明显的不足之处：当删除一个文件时，会在磁盘上留下空闲块。磁盘不会在这个位置挤压掉这个空洞，因为这样或设计复制空洞之后的所有文件，可能有上百万的块。
开始时，碎片并不是问题，因为每个新的文件都在先前文件的结尾部分之后的磁盘空间里写入。但是磁盘最终会被磁盘，所以要么压缩磁盘（代价高，不可行），要么重新使用空洞使用空洞所在的空闲空间。后者是可行的，但是当创建一个新文件时，为了挑选合适大小的空洞存入文件，就有必要知道该文件的最终大小。（但对于一般计算机程序是不合理的）

在计算机科学中，随着新一代技术的出现，历史往往重复着自己。多年前，连续分配由于其简单和高性能被设实际用在磁盘文件系统中。后来由于用户不希望在文件创建时必须指定最终文件的大小，于是放弃了这个想法。但是随着CD-ROM、DVD、蓝光光盘以及其他一次性写光学介质的出现，突然连续分配又称为一个好主意。

链表分配

存储文件的第二种方法是为每个文件构造磁盘块链表，每一个块的第一个字作为指向下一块的指针，块的其他部分存放数据。这一方法可以充分利用每个磁盘块。同样，在目录项中，只需要存放第一块的磁盘地址，文件的其他块就可以从这个首块地址查到。尽管顺序读文件非常方便，但随机访问却相当缓慢。要获得块n，操作系统必须读前面的n-1块。由于每个块的前几个字节被指向下一个块的指针所占据，所以要读出完整的一个块大小的信息，需要从两个块中获得并拼接信息，这就因复制引发了额外的开销。

采用内存中的表进行链表分配

如果取出每个磁盘块的指针字，把它们维护在内存的一张表中，就可以解决上述链表方法的不足。内存中的这样一个表格称为文件分配表（File Allocation Table，FAT）。按这类方式组织，整个块都可以存放数据。进而随机访问也容易地多。虽然仍要顺着链在文件中查给定的偏移量，但是整个链都存放在内存中，所以不需要任何磁盘引用。所以不管文件多大，在目录项中只需记录一个整数（起始块号），按照它就可以到文件的全部块。

缺点是必须把整个表都存放在内存中。显而易见，FAT的管理方式不能较好的扩展并应用于大型磁盘中，但在最初的MS-DOS文件系统比较使用，并仍被各个windows版本所完全支持。

i节点

每个文件赋予一个数组的数据结构（称为i节点），其中列出文件属性和文件块的磁盘地址。文件只有打开时，其i节点才在内存中，那么为了打开文件而保留i节点的数组所占据的全部内存仅仅是kn个字节，只需要提前保留这么多空间即可。

一个问题是如果一个文件所含的磁盘块的数目超出了i节点所容纳的数目怎么办？

方案1：可以将多个索引块链接起来存放，一个解决方案是最后一个元素指向另一个包含磁盘块地址的数组。

方案2：方案1要想访问文件的最后一个块，就必须顺序到最后一个块。这显然是很低效的。为此人们提出了多层索引模型。若采用多层索引，则各层索引表大小不能超过一个磁盘块大小。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K1此读磁盘操作。

方案：前两种方案的结合，一个文件的顶级索引表中，既包含直接地址索引，也包一级简介索引、二级间接索引。

目录的实现

目录里中有一个固定大小的目录项列表，每个文件或目录对应一项，其中包含一个文件名、一个文件属性的结构体以及用以说明磁盘块位置的地址，说明磁盘块位置的地址的信息可能是整个文件的磁盘地址（对于连续分配），第一块的编号（两种链表分配），或者是i节点号。

到目前为止，在需要查文件名时，所有的方案都是线性地从头到尾对目录进行搜索。对于非常长的目录，线性查就太慢了。加快查速度的一个方法是在每个目录中使用散列表。设表的大小为n，在输入文件名时，文件名被散列到1和n-1之间的一个值。
添加一个文件时，不论散列表使用哪种方法都要对与散列值相对应的散列表表项进行检查。如果该表项没有被使用，就将一个指向文件目录项的指针放入，文件目录项紧连在散列表后面。如果该表项被使用了，就构造一个链表，该链表的表头指针存放在该表项中，并廉洁所有具有相同散列值的文件目录项。
查文件按相同的过程进行。散列处理文件名，以便选择一个散列表项。检查链表头在该位置上的链表的所有表项，查看要的文件名是否存在。如果名字不再该链上，该文件就不在这个目录中。

使用散列表的优点是查非常迅速。其缺点是需要复杂的管理。只有在预计系统中的目录经常会有成百上千个文件时，才把散列方案真正作为备选方案考虑。

注：在一些书籍上给出了另外一种方法来提高效率，即添加索引节点，基本原理是另外维护一张表，只存放文件名、物理地址、指向其他属性的指针。显然这张表要比目录项列表要小很多。

共享文件

当几个用户在同一个项目里工作时，他们常常需要共享文件。其结果是，如果一个共享文件同时出现在不同用户的不同目录下，工作起来就很方便。

C的一个文件现在也出现在B的目录下。B的目录与该共享文件的联系称为一个链接（link）。这样，文件系统本身是一个有向无环图（Directed Acyclic Graph，DAG）而不是一棵树。将文件系统组织成有向无环图使得维护复杂化，但也是必须付出的代价。

有两种方法实现这种结构。

在第一种解决方案中（硬链接），磁盘块列入一个与文件本身关联的小型数据结构中（即i节点）。这是UIX系统中采用的方法。让B的目录中的一个目录项指向该文件i节点。

缺点及改进：如果以后试图删除这个文件。如果系统删除文件并清除i节点，B则有一个目录项指向一个无效的i节点。如果该i节点分配给其他文件，则B的链接指向一个错误的文件。系统通过i节点中的计数可以知道该文件仍然被引用，但没办法到指向该文件的全部目录项并删除它们。唯一能做的就是只删除C的目录项而不删除对应的i节点，并将计数置为1（当前计数-1），如果系统进行记账或有配额，那么C将继续为该文件付账直到B决定删除它，只有到计数变为0的时刻，才会删除该i节点。

在第二种解决方案中（软链接），通过让系统建立一个类型为LIK的新文件（新的文件中只包含了它所链接的文件的路径名），并且把该文件放在B的目录下，使得B与C的一个文件存在链接。当B读该链接文件时，操作系统查看读到的文件类型是LIK类型，则到该文件所链接的文件的名字，并且去读那个文件。这一方法称为符号链接（软链接）。
符号链接有一个优势，即只要简单地提供一个机器的网络地址以及文件在该机器上驻留的路径，就可以链接全球任何地方的机器上的文件。

缺点及改进：对于符号链接，删除问题不会发生，当文件所有者删除文件时，该文件被销毁。若以后视图通过符号链接访问该文件将导致失败，因为根据路径不到该文件。
符号链接的问题是需要额外的开销。必须读取包含路径的文件，然后要一个部分一个部分扫描路径，直到到i节点。这些操作也许需要很多次磁盘访问。此外，每个符号链接都需要额外的i节点，以及额外的一个磁盘块存储路径，如果路径名很短，最为一种优化，可以将路径就存储在i节点中。
还有另外一个问题，如果转储一指定目录下的文件，有可能多次复制一个被链接的文件。

其他文件系统

日志结构文件系统（LFS，Log-structured File System）：基本思想是将整个磁盘结构化为一个日志，每隔一段时间，或是有特殊需要时，被缓冲在内存中的所有未决的操作都被放到一个段中作为在日志末尾的一个邻接段写入磁盘。这个单独的段可能包括i节点、目录块，数据块或者都有。在处理大量的零碎的写操作时性能上比UIX好上一个数量级，而在读和大块写操作的性能方面并不必UIX文件系统差，甚至更好。虽然基于日志结构的文件系统是一个很吸引人的想法，但是由于它们和现有文件系统不相匹配，所以还没有被广泛应用

日志文件系统：保存一个用于记录系统将要做什么的日志，这样当系统在完成它们即将完成的任务前崩溃时，重新启动后，可以通过查看日志，获取崩溃前计划完成的任务，并完成它们。TFS文件系统（win7
win8 win10）使用日志。

虚拟文件系统（Virtual FIle System，VFS）：即使在同一台计算机上或在同一个操作系统下，都会使用很多不同的文件系统。windows有一个主要的TFS文件系统，但是也有一个包含老的但仍然使用的FAT2或者FAT16驱动器或分区。windows驱动指定不同的盘符来处理这些不同的文件系统。
虚拟文件系统尝试将多种文件系统整合到一统一的结构中。绝大多数UIX操作系统都使用虚拟文件系统。关键的思想是抽象出所有文件系统都共有的部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来管理数据。如下图。

管理和优化

要使文件系统工作是一件事，使真实世界中的文件系统有效的工作是另一回事。在本节中，将讨论有关磁盘的一些问题。

磁盘空间管理

块大小

一旦决定把文件按固定大小的块来存储，就会出现一个问题：块的大小应该是多少？

拥有大的块意味着小的文件浪费了大量的磁盘空间。另一方面，小的块尺寸意味着大多数文件都会跨越多个块，因此需要多次寻道与旋转延迟才能读出它们，从而降低了性能。

这些曲线显示出性能与空间利用率天生就是矛盾的。小的块会导致低的性能（寻道次数多）但是高的空间利用率（内部碎片少）。从历史观点上来说，文件系统将大小设在1-4KB之间，但现在随着磁盘超过了1TB，还是将块的大小提升到64KB并且接受浪费的磁盘空间，这样也许更好。

记录空闲块

第一种方法是采用磁盘块链表，链表的每个块中包含尽可能多的空闲磁盘块号。通常情况下，采用空闲块存放空闲表。
只需要在内存中保存一个指针块（磁盘中保存全部的指针块）。当文件创建时，所需要的块从指针块中取出。现有的指针块用完时，从磁盘中读入一个新的指针块。类似地，当删除文件时，其磁盘块被释放，并添加到内存的指针块中。
当指针块几乎为空时，一系列短期的临时文件会引起大量的I/O操作。一个避免过多I/O操作的策略是保持磁盘上的大多数指针块为满，但是在内存中保留一个半满的指针块。这样，它既可以处理文件的创建又同时处理文件的删除操作，而不会为空闲表进行磁盘I/O。
a->b经过策略改进之后变成a->c

另一种空闲磁盘空间管理的方法是采用位图。在位图中，空闲块用1表示，已分配块用0表示（或者反之）。
在内存中只保留一个块是有可能的，只有在该块满或空的情形下，才到磁盘上取另一块。这样处理的附加好处是，通过在位图的单一块上进行所有的分配操作，磁盘块会较为紧密的聚集在一起，从而减少了磁盘臂移动次数。

很明显，位图方法所需空间较少，因为每个块只用一个二进制位标识，而在链表方法中，每一块要用到2位。只有在磁盘块满时（几乎没有空闲块时）链表方案需要的块才比位图少

磁盘配额

为了防止人们贪心而占用太多的磁盘空间，多用户操作系统提供一种强制性磁盘配额机制。

当用户打开一个文件，系统到文件属性和磁盘地址，并把它们送入内存中的打开文件表。其中一个属性告诉文件所有者是谁。任何有关该文件大小的增长都记录到所有者的配额上。
在配额表中，记录了用户的配额记录。配额表的内容是从被打开文件所有者的磁盘配额文件中提取出来的
在打开文件表中建立一个新表项时，会产生一个指向所有者配额记录的指针，以便很容易到不同的限制。

每次往文件添加一块，文件所有者所用数据块的总数增加，引发对配额应硬限制和软限制的检查。可以超出软限制，不能超出硬限制。当已经达到硬限制时，再继续添加内容会引发错误。同样，对文件数目也有类似的检查。

当用户试图登录时，查看该用户文件数目或磁盘块数目是否超过软限制。如果超过了任意限制，则显示警告，保存的警告计数减1,。如果该计数为0，不允许该用户登录。

文件系统备份

比起计算机的损坏，文件系统的破坏往往要糟糕的多（其他损坏可以用钱解决）。如果计算机的文件系统被破坏了，恢复全部信息是一件困难又费时的工作，在很多情况下，是不可能的。

最简单的解决办法是制作备份。
做磁带备份主要是要处理好两个潜在问题中的一个：

从意外的灾难中恢复：主要是由于磁盘破裂、火灾等原因引起的。事实上这种情形并不多见。（即使发生了，人们也不觉得因此丢失数据是一件不可思议的事情）

从错误的操作中恢复：主要是用户意外删除了原本还需要的文件。这种情况发生的很频繁。使得windows的设计者专门特殊了特殊目录—回收站，文件并不真正从磁盘上消失，而是被放置到这个特殊目录下，待以后需要的时候可以还原回去。

怎样让备份做的又快又好，有下面几个方面：
首先，合理的做法是只备份特定目录及其下的全部文件，而不是备份整个文件系统。
其次，周期性的做全面的备份，而每天对上一次全面备份发生的变化的数据做备份，即增量存储。
第三，可以在备份之前对数据进行压缩，但是，备份磁带上的单个坏点就能破坏压缩算法。
第四，既然转储一次需要几个小时，可以把将来对文件和目录所做的修改复制到块中，而不是处处更新它们，留待以后空闲的时候做备份。
第五，非技术性问题，备份磁带的安全风险，备份磁带应该远离现场存放。

磁盘存储到磁带上有两种方案：物理转储和逻辑转储。物理转储是完全复制磁盘，可以确保万无一失。缺点是无法增量转储，不能满足恢复个人文件的请求。逻辑转储从一个或几个指定的目录开始，递归转储其自给定基准日期后有所更改的全部文件和目录。所以，在逻辑存储中，转储磁带上会有一连串精心标识的目录和文件，这样就很容易满足恢复特定文件或目录的请求。

文件系统的一致性

影响文件系统可靠性的另一个问题是文件系统是一致性。很多文件系统读取磁盘块，进行修改后，再写回磁盘。如果在修改过的磁盘块全部写回之前系统崩溃，则文件系统有可能处于不一致状态。
为了解决文件系统的不一致问题，很多计算机都带有一个实用程序以检验文件系统的一致性。例如UIX有fsck，windows用scandisk。

文件系统性能

许多文件系统采用了各种优化措施以改善性能。我们将介绍三种方法。

高速缓存

最常用的减少磁盘访问次数技术是块高速缓存（block cache）或者缓冲区高速缓存（buffer cache）。高速缓存指的是一系列的块，在逻辑上属于磁盘，实际上被保存在内存中。通常的算法是：检查全部读请求，查看在告诉缓存中是否有需要的块。如果有，执行读操作无需访问磁盘；如果没有，首先把它读到高速缓存中，再复制到所需地方。

快速确定所需要的块是否在高速缓存中可以使用散列。

如果高速缓存满，可以和采用分页系统中的置换算法。例如FIFO算法、第二次机会算法、LRU算法等，它们都适用于高速缓存。

块提前读

第二个明显提高文件系统性能的技术是：在需要用到块之前，试图提前将其写入高速缓存，从而提高命中率，当然，这种技术只适用于实际顺序读取的文件。对随机访问文件，提前读丝毫不起作用。文件系统通过跟踪每一个打开文件的访问方式来确定是否要使用这种策略。
对于顺序读文件，如果请求 文件系统在某个文件中生成块k，文件系统执行相关操作且在完成之后，会在用户不察觉的情形下检查高速缓存，以便确定块k1是否已经在高速缓存，如果还不在，文件系统就会预读k1块，英文文件系统希望在需要用到该块时，它已经在高速缓存或者至少马上就要在高速缓存中了。

减少磁盘臂运动

另一种重要技术是把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘臂的移动次数。越来越多的电脑开始装配不带移动部件的固态硬盘（SSD）。对于这些硬盘，寻道时间和旋转时间没有意义，使得随机访问和顺序访问在传输速度上较为详尽，许多传统硬盘的许多问题就消失了。

磁盘碎片整理

磁盘性能可以通过如下方式恢复：移动文件使它们相邻，并把所有的（至少是大部分的）空闲空间放在一个或多个大的连续空间内。window有一个程序defrag就是从事这个工作的。
磁盘碎片整理程序会在一个分区末端的连续区域内有大量空闲空间的文件系统上很好地运行。选择在分区开始端的碎片文件，复制它所有的块放到空闲空间内，这样磁盘开始处释放出一个连续的空间，这样原始或其他的文件可以在其中相邻的存放。这个过程可以在下一块的磁盘空间上重复，并继续下去。

输入/输出

本章略过了后面的时钟、鼠标键盘显示器、瘦客户机、电源管理内容，添加了一些国内课本内容

除了提供抽象（进程、地址空间、文件）以外，操作系统还要控制计算机的所有I/O（输入输出）设备。操作系统必须向设备发送命令，捕捉中断，并处理设备的各种错误。它还应该在设备和系统的其他部分之间提供易于使用的接口。如果有可能，这个接口对于所有设备都应该是相同的，这就是所谓的设备无关性。

I/O硬件原理

I/O设备

I/O设备分为两类：块设备（block device）和字符设备（character device）。

块设备把信息存储在固定大小的块中，每个块都有自己的地址。所有的传输都以一个或者多个完整的块为单位。块设备的基本特征是每个块都能独立于其他块而读写。硬盘、蓝光光盘和U盘是最常见的块设备。

另一类I/O设备是字符设备。字符设备以字符为单位发送或接收一个字符流，而不考虑任何块结构。字符设备是不可寻址的，而且没有任何寻道操作。打印机、网络接口、鼠标、以及大多数与磁盘不同的设备都可以看做字符设备。

这种分类方法并不完美，有些设备没有包括进去。例如，时钟既不是块可寻址的，也不产生字符流。它所做的工作就是按照预先规定好的时间间隔产生中断。内存映射的显示器也不适用于此模型。但是，块设备和字符设备的模型有足够的一般性，可以用作使处理I/O设备的某些操作系统具有设备无关性的基础。

设备控制器

I/O设备一般由机械部件和电子部件两部分组成。电子部件称为设备控制器（device controller）或适配器（adapter），在个人计算机上经常以主板上芯片的形式出现，或者以插入（PCI）扩展槽的印刷电路板的形式出现，机械部分则是设备本身。
、
控制器卡上有一个连接器，通向设备本身的电缆可以插入到这个连接器中。很多控制器可以操作2、4甚至8个相同的设备。如果控制器和设备之间采用的是标准接口，无论是官方的ASI、IEEE或ISO标准还是事实上的标准，各个公司都可以制造各种适合这个接口的控制器或设备。
、
控制器的任务是把串行的位流转换成字节块，并进行必要的错误校正工作。字节块通常首先在控制器内部的一个缓冲区中按位进行组装，然后再对校验和进行校验并证明字节块没有错误后，再将它复制到主存。

内存映射I/O

每个控制器有几个寄存器来与CPU进行通信。通过写入这些寄存器，操作系统可以命令设备发送数据，接受数据、开启或关闭，或者执行某些其他操作。通过读取这些寄存器，操作系统可以了解设备的状态，是否准备好接收一个新的命令等。除了控制寄存器，还有一个数据缓冲区。例如，在屏幕上展示像素的常规方法是使用一个数据缓冲区，可供程序或操作系统写入数据。

CPU如何与设备的控制寄存器和数据缓冲区通信？
第一个方法：每个控制寄存器分配一个I/O端口号，这是一个8位或16位的整数，所有I/O端口形成I/O端口空间（I/O port space），并且受到保护使得普通的用户程序不能对其进行访问（只有操作系统可以访问）。使用特殊的I/O指令CPU可以读取控制寄存器的内容并将结果存入到CPU寄存器中。
第二个方法：将所有控制寄存器映射到内存空间中。每个控制寄存器被分配唯一的内存地址，并且不会有内存会被分配这一地址。这样的系统称为内存映射I/O。在大多数系统中，分配给控制寄存器的地址位于或者靠近地址空间的顶端。
第三种：前两种混合

直接存储器读取

无论一个CPU是否具有内存映射I/O，它都需要寻址设备控制器以便与它们交换数据。CPU可以从I/O控制器每次请求一个字节的数据，但是这样做浪费CPU的时间，所以经常用到一种称为直接存储器存取（Direct Memory Access，DMA）的不同方案。

只有硬件具有DMA控制器时操作系统才能使用DMA，而大多数系统都有DMA控制器。有时DMA控制器集成到磁盘控制器和其他控制器之中，但是这样的设计要求每个设备有一个单独的DMA控制器。更加普遍的是，只有一个DMA控制器可利用。

DMA控制器包含一个内存地址控制器、一个字节计数寄存器和一个或多个控制寄存器。控制寄存器指定要使用的I/O端口、传送方向（从I/O设备读或写到I/O设备）、传送单位（每次一个字节或每次一个字）以及在一次突发传送中要传送的字节数。

DMA的工作原理，首先CPU通过设置DMA控制器的寄存器对它进行编程，所有DMA控制器知道将什么数据传送到什么地方（第1步）。DMA控制器还要向磁盘控制器发出一个命令，通知它从磁盘读数据到其内部缓冲区，并对校验和进行检验。如果缓冲区中的数据是有效的，那么DMA就可以开始了。DMA控制器通过在总线上发出一个读请求到磁盘控制器而发起DMA传送（第2步）。这一读请求看起来与任何其他读请求是一样的，并且磁盘控制器不知道或者并不关心它是来自CPU还是来自DMA控制器。一般情况下，要写的内存地址在总线的地址线上，所以当磁盘控制器从其内部缓冲区中读取下一个字的时候，数据写入内存（第步）。当写操作完成时，磁盘控制器在总线上发出一个应答信号到DMA控制器（第4步）。于是，DMA控制器步增要使用的内存地址，并且步减字节计数。如果字节计数仍然大于0，则重复第2步到第4步，知道字节计数到达0.此时，DMA控制器将中断CPU以便让CPU知道传送现在已经完成了。当操作系统开始工作时，用不着将磁盘块复制到内存中，因为它已经在内存中了。

重温中断

在一台典型的个人计算机系统中，中断结构如图所示。在硬件层面，中断的工作如下所述。当一个I/O设备完成交给它的工作时，它就产生一个中断，它是通过在分配给它的一条总线信号线上置起信号而产生中断的。该信号被主板上的中断控制器芯片检测到，由中断控制器芯片决定做什么。

如果没有其他中断，中断控制器立即对中断进行处理。如果另外中断在处理，或者有更高优先级中断请求，该设备暂时不被理睬。在这种情况下，该设备继续在总线上置起中断信号，直到得到CPU的服务。

I/O软件原理

I/O软件目标

设备独立性：读取一个文件作为输入的程序能够在硬盘、DVD或者U盘上读取文件，无需为每一种不同的设备修改程序。
统一命名：一个文件的名字不应该依赖于设备。设备可以看做特殊文件。所有文件和设备都采用路径名进行寻址。
错误处理：错误应尽可能在接近硬件的层次得到处理，许多情况下，错误恢复可以在低层透明的得到解决。
同步和异步：大多数物理I/O是异步的，CPU启动传输后便去做其他工作，直到中断发生。如果I/O操作是阻塞的，那么用户程序将自动被挂起，直到控制器缓冲区的数据准备好。
缓冲（缓冲区管理）：数据离开一个设备后通常并不能直接存放到最终的目的地，所以数据必须预先放置到内存中的输出缓冲区中，从而消除缓冲区填满速率和缓冲区清空速率之间的相互影响。
共享设备和独占设备（设备的分配回收问题）：有些I/O设备能够同时多个用户使用（磁盘），其他设备必须由单个用户使用，直到该用户使用完（磁带机）。spooling技术。

程序直接控制方式

用户进程通过发出打印机一类的系统调用来获得打印机进行写操作。如果打印机被占用，返回错误代码或阻塞。一旦拥有打印机，用户进程发出系统调用通知操作系统在打印机上打印字符串。
操作系统将字符串缓冲区复制到内核中的一个数组（缓冲区）中，然后操作系统复制第一个字符到打印机（控制器）数据寄存器中，字符也许不会立即出现在打印机上，因为打印机在打印东西之前可能先缓冲一行或一页。将字符写到数据寄存器的操作将导致（控制器）状态寄存器变为非就绪态。当打印机处理完当前字符，变为就绪态。就绪事件发生，操作系统打印下一个字符。
特点：CPU要不断地查询设备以了解它是否就绪准备接收另一个字符。这一行为经常称为轮询（polling）或忙等待（busy waiting）

读操作

中断驱动方式

引入了中断机制，由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成曾后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。接着，CPU恢复等待I/O继续执行或者将其放入就绪队列等待下一次CPU调用。

把每个字符写到打印机（控制器）的数据寄存器之后，CPU将有10ms在无价值的循环中，等待允许输出下一个字符。这10ms足以进行一次进程上下文切换并且运行其他进程。使用中断解决。
打印机接收第一个字符将第一个字符复制到打印机中。这时，CPU要调用调度程序，阻塞该进程，切换其他进程。
当打印机将字符打印完并且准备好接收下一个字符时，它将产生一个中断。这一中断将停止当前进程并保存其状态。然后，打印机中断程序将运行。如果没有更多的字符要打印，中断处理程序将采取某个操作将用户进程解除阻塞（或者进入就绪队列）。否则，它将输出下一个字符，应答中断，并且返回到中断之前正在运行的进程，该进程将从其停止的地方继续运行。

读操作
和打印机类似，从I/O模块中读取字每次只能读取一个，产生中断。

中断方式明显缺点是中断发生在每个字符上，浪费一定CPU时间。

DMA方式

中断方式缺点的解决方法是使用DMA，思路是让DMA控制器一次给打印机提供一个字符，而不必打扰CPU。
DMA重大的成功是将中断的次数从打印每个字符减少到每个缓冲区一次。

读操作，读写单位从字变成块，数据流向不再经过CPU，直接进入内存

I/O软件层次

书上内容比较晦涩，仅了解

spooling技术

批处理阶段的脱机技术：在外围控制机的控制下，慢速输入设备的数据先被输入到更快速的磁带上，之后主机可以从快速的磁带上读入数据，输出时类似，先输出到快速的磁带上，然后磁带输出给外围控制机，然后数据慢速输出给输出设备。

spooling技术又叫假脱机技术，是用软件的方式模拟脱机技术，输入井和输出井模拟脱机技术中的磁带，输入进程和输出进程用软件模拟外围控制机，内存中的输入缓冲区和输出缓冲区是进入输入井和输出井的中转站。

独占式设备：只允许进程串行使用的设备
共享设备：允许多个进程同时使用的设备

共享打印机原理：多个用户进程提出输出打印请求，系统会答应它们的请求，但是并不是真正把打印机给它们。先将要打印的数据放入输出井申请的一个空闲缓冲区中，为用户进程申请一张打印请求表，将该表挂到打印任务队列上。根据这个打印任务队列一次打印全部的打印任务。将输出井中的数据给输出缓冲区，再从输出缓冲区中进行真正的打印。

盘

关于盘的基础内容大部分在第一章中已经介绍过了，这里跳过了书中比较晦涩部分，主要写一下磁盘管理和磁盘臂调度算法。

磁盘初始化

在磁盘能够使用之前，每个盘片必须经受由软件完成的低级格式化（low level format）。将磁盘的各个磁道划分为扇区，一个扇区可以分为头、数据区域、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码，校验码用于校验扇区中的数据是否发生错误。
在低级格式化之后，需要对磁盘进行分区，每个分区由若干个柱面组成（即一般的C、D、E盘）

在准备一块磁盘以便于使用的最后一步是对每个分区分别执行一次高级格式化（high-level
format）。这一操作要设置一个引导块、空闲存储管理、根目录和一个空文件系。当电源打开时，BIOS最先运行，它读入主引导记录并跳转到主引导记录（主引导记录在0扇区中，它包含某些引导代码以及处在扇区末尾的分区表），然后这一引导程序进行检查以了解哪个分区是活动的。引导扇区包含一个小的程序，它一般会装入一个较大的引导程序装载器，该引导程序装载器将搜索文件系统以到操作系统内核，该程序被装入内存并执行。

坏块处理（错误处理）

制造时的瑕疵会引入坏扇区。对于坏块存在两种一般的处理方法：在控制器中对它们进行处理或者在操作系统中对它们进行处理。在前一种方法中，磁盘在从工厂出厂之前要进行测试，并且将一个坏扇区列表写在磁盘上。对于每一个坏扇区，用一个备用扇区替换它。如果控制器没有透明重映射扇区的能力，那么操作系统就必须在软件中做同样的事情。这意味着操作系统必须首先获得一个坏扇区列表，或者是通过从磁盘中读出该列表，或者只是由它自己测试整个磁盘，一旦操作系统知道哪些扇区是坏的，就可以建立重映射表。

磁盘臂调度算法

先来先服务（FCFS，First-Come FIrst-Served）：很难优化寻道时间

最短寻道优先（SSF，Shortest Seek First）：下一次总是处理与磁头最近的请求以使最短寻道时间最小化，如果磁盘负载很重，磁盘臂将停留在磁盘的中部区域，而两端极端区域的请求将不得不等待。

电梯算法（elevator algorithm）：当一个请求处理完后，如果更高的位置没有未完成的请求，则反向。
对电梯算法稍加改进，方法是如果更高位置没有未完成的请求，不是反向，而是回到具有未完成请求的最低编号的柱面，然后继续沿向上的方向移动。

《程序是怎样跑起来的》

《程序是怎样跑起来的》中的一部分内容并入了上面的章节中作为补充，还有一些内容比较独立，所以放在本篇的最后。

二进制数

想必大家都知道计算机内部是由IC（集成电路）这种电子部件构成的。CPU和内存也是IC的一种。IC在其两侧有数个至数百个引脚。IC的所有引脚，只有直流电压0V或5V两个状态。IC这个特性，决定了计算机中的信息数据只能用二进制数来表示，由于1位（一个引脚）只能表示两个状态，所以二进制的计数方式就变成了二进制的形式。

二进制转10进制，二进制数00100111用10进制数表示的话是（0*128）（0*64）（1*2）（0*16）（0*8）（1*4）（1*2）（1*1）=9

补数：二进制数表示负数时，一般把最高位作为符号位，计算机中表示负数是通过补数的形式来表示的。-1用8位表示为11111111，为了获得补数我们需要将二进制数的各数位取反1。例如-1，只需求1，00000001，取反11111110，加1,就得到结果。

移位运算，移位分为左移（<<）和右移(>>)。左侧表示被移位的值，右侧表示要移位的位数。移位操作使最高位或者最低位溢出的数字，直接丢弃就好了。左移空出来的低位要补0。右移稍微复杂一点，当二进制数的值表示图形模式而并非数值时，移位后需要在高位补0，这称为逻辑右移。当二进制数作为带符号的数值进行运算时，移位后要在最高位填充移位前符号位的值，这就是算数右移。如果数值是用补数表示的负数值，那么右移后再空出来的最高位补1，就可以正确的实现运算。如果是正数，只需在最高位补0即可。

逻辑运算：逻辑运算是指对二进制数各数字位的0和1分别进行处理的运算，包括逻辑非（OT）、逻辑与（AD）、逻辑或（OR）、和逻辑异或（XOR）四种。
逻辑非：真值 1
逻辑与：真值 11
逻辑或：真值11 10 01
逻辑异或：真值01 10

二进制小数：把1011.0011二进制数转换成10进制数。（1*8）（0*4）（1*2）（1*1）（0*0.5）（0*0.25）（1*0.125）（1*0.0625）=11.1875
计算机二进制小数运算出错的原因：有一些二进制数的小数无法转换成二进制数。例如十进制数0.1，就无法用二进制数正确表示，只能表示它的近似值。
浮点数：双精度浮点类型64位、单精度浮点2位表示小数。浮点数是指用符号、尾数、基数和指数四部分来表示的小数。m×n^e（m是尾数，n是基数）二进制基数自然是2。符号位为1时表示正数，为0时表示负数。尾数部分是将小数点前面的值固定为1的正则表达式，指数部分用的是EXCESS系统，使用这种方法是为了表示负数时不使用符号位。具体表示如下面第三张图。

内存IC

内存IC的引脚配置示例。VCC和GD是电源，A0~A9是地址信号的引脚，D0 ~D7是数据信号的引脚，RD和WR是控制信号的引脚。将电源链接到VCC和GD后，就可以给其他引脚传递比如0或1这样的信号。大多数情况下，5V直流电压表示1，0V表示0。数据信号引脚有8个，表示一次可以输入输出8位数据。地址信号引脚有10个，1024个地址。因此我们可以得出这个内存IC中可以存储1024个1字节的数据。1024=1k，所以该IC容量就是1KB。

我们假设要往该内存IC中写入1字节的数据。为了实现该目的，就可以给VCC接入5V，给GD接入0V的电源，并使用A0 ~A9的地址信号来指定数据的存储场所，然后再把数据的值输入给D0 ~D7的数据信号，并把WR设置为1，执行完这些操作，就可以在内存IC内部写入数据了。
读出数据时，只需通过A0 ~A9的地址信号指定数据的存储场所，然后再将ED（read=读出的简写）信号设成1即可。执行完这些操作，指定地址中存储的数据就会被输出到D0 ~D7的数据引脚中。

从源文件到可执行文件

计算机只能运行本地代码（即机器代码）。用某种编程语言编写的程序就称为源代码，保存源代码的文件称为源文件，java中源文件就是.java后缀。因为源文件是简单的文本文件，所以用windows自带的记事本等文本编辑器就可以编写。

能够把java等高级语言编写的源代码转换成本地代码的程序称为编译器。每个编写源代码的编程语言都需要专用的编译器。编译器首先读入代码的内容，然后再把源代码转换成本地代码。编译的过程要有一个同本地代码的对应表，还要进行语法解析、句法解析、语义解析等，才能生成本地代码。仅仅靠编译无法得到可执行文件，java源文件编译后生成.class文件。然而.class并不是本地代码。需要用JDK中的java解释器翻译成本地代码。将多个目标文件结合，生成1个exe文件的处理就是链接，运行连接的程序称为链接器。库文件指的是把多个目标文件集成保存到一个文件中的形式。之所以使用库文件，收尾了简化为链接器的参数指定多个目标文件这一过程。windows中，API的目标文件，并不是存储在通常的库文件中，而是存储在名为DLL文件的特殊库文件中，是程序运行时动态结合的文件。与此相反，存储这目标文件实体的库叫做静态链接库。

汇编语言

现在已经没有人用汇编语言来编写程序了，因为java等高级语言用1行就可以完成的处理，使用汇编语言的话有时就需要很多行，效率很低。不过，汇编语言的经验还是很重要的。因为借助汇编语言，我们可以更好的了解计算机的机制。没有汇编语言经验的程序员，就相当于只知道汽车的驾驶方法而不了解汽车结构的驾驶员。

使用助记符的编程语言称为汇编语言。这样，通过查看汇编语言编写的源代码，就可以了解程序的本质。因为这和查看本地代码的源代码是同一级别的。用汇编语言写的源代码，需要转换成本地代码才能运行。负责转换工作的程序称为汇编器（类似编译器）。本地代码也可以反过来转换成汇编语言的源代码，称为反汇编。对于一些高级语言，可以用工具转换成汇编语言代码。

汇编语言的代码，是由转换成本地代码的指令和针对汇编器的伪指令构成的。伪指令负责把程序的构造及汇编的方法指示给汇编器。但伪指令本身无法汇编成本地代码。

函数调用

（）和（4）表示的4将两个参数push入栈，（5）的call指令，将程序流程跳转到了操作数中指定的Addum函数所在的内存地址处。Addum处理完后，程序流程回到编号（6）这一行。call指令运行后，call指令的下一行的内存地址会自动入栈。该值会在函数处理的最后通过ret指令pop出栈，然后程序流程就会到（6）这一行。（6）部分会把两个参数销毁（esp寄存器8）。
对于（1）和（7），是C编译器的规定，确保函数调用前后ebp寄存器的值不发生变化。（2）在下面函数内部处理中解释。

addum函数内部

（2），在mov指令中方括号内的参数，是不允许指定esp寄存器的，所以不直接通过esp，而是用ebp来读栈内容。
（）（4），分别从栈中取12和456，eax是累加寄存器

局部和全局变量

初始化的全局变量，会被汇总到_DATA的段定义中，没有初始化的全局变量，会被汇总到_BSS的段定义中。（5）中的dd_1指的是申请分配了4字节的内存空间，存储这1这个初始值。dd表示双字（每个字的长度是2个字节）（6）中的db 4 dup(?)表示的是申请分配4字节的领域，但值未确定。db表示有长度是1字节的内存空间。

为确保c0~c10所需的领域，寄存器空闲时就用寄存器，空间不足就用栈。
（8）表示用eax寄存器给c1-c5这5个局部变量赋值。
（10）函数入口对栈数据存储位置的esp寄存器的值做减20的处理。剩下的c6-c10就被分配了栈的内存空间。

循环和条件判断

cmp ebx,10就相当于是吧exb寄存器的数值同10进行比较。汇编语言中比较指令的结果，会存储在CPU的标志寄存器中。根据跳转指令的种类和寄存器的值来判定是否跳转。最后一行的jl short @4意思就是前面运行的比较指令如果小就跳转到@4这个标签。

条件判断和循环本质上一样，不是调到开始处，而是跳到别的地方。