爱喝奶茶的波波

操作系统入门-计算机硬件介绍

二、计算机硬件介绍操作系统与运行操作系统的内核硬件关系密切。操作系统扩展了计算机指令集并管理计算机的资源。因此，操作系统因此必须足够了解硬件的运行，这里我们先简要介绍一下现代计算机中的计算机硬件。从概念上来看，一台简单的个人电脑可以被抽象为上面这种相似的模型，CPU、内存、I/O 设备都和总线串联起来并通过总线与其他设备进行通信。现代操作系统有着更为复杂的结构，会设计很多条总线，我们稍后会看到。暂时来讲，这个模型能够满足我们的讨论。2.1CPUCPU 是计算机的大脑，它主要和内存进行交互，从内存中提取指令并执行它。一个 CPU 的执行周期是从内存中提取第一条指令、解码并决定它的类型和操作数，执行，然后再提取、解码执行后续的指令。重复该循环直到程序运行完毕。每个 CPU 都有一组可以执行的特定指令集。因此，x86 的 CPU 不能执行 ARM 的程序并且 ARM 的 CPU 也不能执行 x86 的程序。由于访问内存获取执行或数据要比执行指令花费的时间长，因此所有的 CPU 内部都会包含一些寄存器来保存关键变量和临时结果。因此，在指令集中通常会有一些指令用于把关键字从内存中加载到寄存器中，以及把关键字从寄存器存入到内存中。还有一些其他的指令会把来自寄存器和内存的操作数进行组合，例如 add 操作就会把两个操作数相加并把结果保存到内存中。除了用于保存变量和临时结果的通用寄存器外，大多数计算机还具有几个特殊的寄存器，这些寄存器对于程序员是可见的。其中之一就是 程序计数器(program counter)，程序计数器会指示下一条需要从内存提取指令的地址。提取指令后，程序计数器将更新为下一条需要提取的地址。另一个寄存器是 堆栈指针(stack pointer)，它指向内存中当前栈的顶端。堆栈指针会包含输入过程中的有关参数、局部变量以及没有保存在寄存器中的临时变量。还有一个寄存器是 PSW(Program Status Word) 程序状态字寄存器，这个寄存器是由操作系统维护的8个字节(64位) long 类型的数据集合。它会跟踪当前系统的状态。除非发生系统结束，否则我们可以忽略 PSW 。用户程序通常可以读取整个PSW，但通常只能写入其某些字段。PSW 在系统调用和 I / O 中起着重要作用。操作系统必须了解所有的寄存器。在时间多路复用(time multiplexing) 的 CPU 中，操作系统往往停止运行一个程序转而运行另外一个。每次当操作系统停止运行一个程序时，操作系统会保存所有寄存器的值，以便于后续重新运行该程序。为了提升性能， CPU 设计人员早就放弃了同时去读取、解码和执行一条简单的指令。许多现代的 CPU 都具有同时读取多条指令的机制。例如，一个 CPU 可能会有单独访问、解码和执行单元，所以，当 CPU 执行第 N 条指令时，还可以对 N + 1 条指令解码，还可以读取 N + 2 条指令。像这样的组织形式被称为 流水线(pipeline)，比流水线更先进的设计是 超标量(superscalar) CPU，下面是超标量 CPU 的设计在上面这个设计中，存在多个执行单元，例如，一个用来进行整数运算、一个用来浮点数运算、一个用来布尔运算。两个或者更多的指令被一次性取出、解码并放入缓冲区中，直至它们执行完毕。只要一个执行单元空闲，就会去检查缓冲区是否有可以执行的指令。如果有，就把指令从缓冲区中取出并执行。这种设计的含义是应用程序通常是无序执行的。在大多数情况下，硬件负责保证这种运算的结果与顺序执行指令时的结果相同。除了用在嵌入式系统中非常简单的 CPU 之外，多数 CPU 都有两种模式，即前面已经提到的内核态和用户态。通常情况下，PSW 寄存器中的一个二进制位会控制当前状态是内核态还是用户态。当运行在内核态时，CPU 能够执行任何指令集中的指令并且能够使用硬件的功能。在台式机和服务器上，操作系统通常以内核模式运行，从而可以访问完整的硬件。在大多数嵌入式系统中，一部分运行在内核态下，剩下的一部分运行在用户态下。用户应用程序通常运行在用户态下，在用户态下，CPU 只能执行指令集中的一部分并且只能访问硬件的一部分功能。一般情况下，在用户态下，有关 I/O 和内存保护的所有指令是禁止执行的。当然，设置 PSW 模式的二进制位为内核态也是禁止的。为了获取操作系统的服务，用户程序必须使用 系统调用(system call)，系统调用会转换为内核态并且调用操作系统。TRAP 指令用于把用户态切换为内核态并启用操作系统。当有关工作完成之后，在系统调用后面的指令会把控制权交给用户程序。我们会在后面探讨操作系统的调用细节。需要注意的是操作系统在进行系统调用时会存在陷阱。大部分的陷阱会导致硬件发出警告，比如说试图被零除或浮点下溢等。在所有的情况下，操作系统都能得到控制权并决定如何处理异常情况。有时，由于出错的原因，程序不得不停止。2.2多线程和多核芯片Intel Pentinum 4也就是奔腾处理器引入了被称为多线程(multithreading) 或 超线程(hyperthreading, Intel 公司的命名) 的特性，x86 处理器和其他一些 CPU 芯片就是这样做的。包括 SSPARC、Power5、Intel Xeon 和 Intel Core 系列 。近似地说，多线程允许 CPU 保持两个不同的线程状态并且在纳秒级(nanosecond) 的时间完成切换。线程是一种轻量级的进程，我们会在后面说到。例如，如果一个进程想要从内存中读取指令(这通常会经历几个时钟周期)，多线程 CPU 则可以切换至另一个线程。多线程不会提供真正的并行处理。在一个时刻只有一个进程在运行。对于操作系统来讲，多线程是有意义的，因为每个线程对操作系统来说都像是一个单个的 CPU。比如一个有两个 CPU 的操作系统，并且每个 CPU 运行两个线程，那么这对于操作系统来说就可能是 4 个 CPU。除了多线程之外，现在许多 CPU 芯片上都具有四个、八个或更多完整的处理器或内核。多核芯片在其上有效地承载了四个微型芯片，每个微型芯片都有自己的独立CPU。2.3内存计算机中第二个主要的组件就是内存。理想情况下，内存应该非常快速(比执行一条指令要快，从而不会拖慢 CPU 执行效率)，而且足够大且便宜，但是目前的技术手段无法满足三者的需求。于是采用了不同的处理方式，存储器系统采用一种分层次的结构顶层的存储器速度最高，但是容量最小，成本非常高，层级结构越向下，其访问效率越慢，容量越大，但是造价也就越便宜。寄存器存储器的顶层是 CPU 中的寄存器，它们用和 CPU 一样的材料制成，所以和 CPU 一样快。程序必须在软件中自行管理这些寄存器（即决定如何使用它们）高速缓存位于寄存器下面的是高速缓存，它多数由硬件控制。主存被分割成高速缓存行(cache lines) 为 64 字节，内存地址的 0 - 63 对应高速缓存行 0 ，地址 64 - 127 对应高速缓存行的 1，等等。使用最频繁的高速缓存行保存在位于 CPU 内部或非常靠近 CPU 的高速缓存中。当应用程序需要从内存中读取关键词的时候，高速缓存的硬件会检查所需要的高速缓存行是否在高速缓存中。如果在的话，那么这就是高速缓存命中(cache hit)。高速缓存满足了该请求，并且没有通过总线将内存请求发送到主内存。高速缓存命中通常需要花费两个时钟周期。缓存未命中需要从内存中提取，这会消耗大量的时间。高速缓存行会限制容量的大小因为它的造价非常昂贵。有一些机器会有两个或者三个高速缓存级别，每一级高速缓存比前一级慢且容量更大。缓存在计算机很多领域都扮演了非常重要的角色，不仅仅是 RAM 缓存行。随机存储器（RAM）： 内存中最重要的一种，表示既可以从中读取数据，也可以写入数据。当机器关闭时，内存中的信息会 丢失。大量的可用资源被划分为小的部分，这些可用资源的一部分会获得比其他资源更频繁的使用权，缓存经常用来提升性能。操作系统无时无刻的不在使用缓存。例如，大多数操作系统在主机内存中保留（部分）频繁使用的文件，以避免重复从磁盘重复获取。举个例子，类似于 /home/ast/projects/minix3/src/kernel/clock.c 这样的场路径名转换成的文件所在磁盘地址的结果也可以保存缓存中，以避免重复寻址。另外，当一个 Web 页面(URL) 的地址转换为网络地址(IP地址)后，这个转换结果也可以缓存起来供将来使用。在任何缓存系统中，都会有下面这几个急需解决的问题何时把新的内容放进缓存把新的内容应该放在缓存的哪一行在需要空闲空间时，应该把哪块内容从缓存中移除应该把移除的内容放在某个较大存储器的何处并不是每个问题都与每种缓存情况有关。对于 CPU 缓存中的主存缓存行，当有缓存未命中时，就会调入新的内容。通常通过所引用内存地址的高位计算应该使用的缓存行。缓存是解决问题的一种好的方式，所以现代 CPU 设计了两种缓存。第一级缓存或者说是 L1 cache 总是位于 CPU 内部，用来将已解码的指令调入 CPU 的执行引擎。对于那些频繁使用的关键字，多数芯片有第二个 L1 cache 。典型的 L1 cache 的大小为 16 KB。另外，往往还设有二级缓存，也就是 L2 cache，用来存放最近使用过的关键字，一般是兆字节为单位。L1 cache 和 L2 cache 最大的不同在于是否存在延迟。访问 L1 cache 没有任何的延迟，然而访问 L2 cache 会有 1 - 2 个时钟周期的延迟。什么是时钟周期？计算机处理器或 CPU 的速度由时钟周期来确定，该时钟周期是振荡器两个脉冲之间的时间量。一般而言，每秒脉冲数越高，计算机处理器处理信息的速度就越快。 时钟速度以 Hz 为单位测量，通常为兆赫（MHz）或千兆赫（GHz）。 例如，一个4 GHz处理器每秒执行4,000,000,000个时钟周期。计算机处理器可以在每个时钟周期执行一条或多条指令，这具体取决于处理器的类型。 早期的计算机处理器和较慢的 CPU 在每个时钟周期只能执行一条指令，而现代处理器在每个时钟周期可以执行多条指令。主存在上面的层次结构中再下一层是主存，这是内存系统的主力军，主存通常叫做 RAM(Random Access Memory)，由于 1950 年代和 1960 年代的计算机使用微小的可磁化铁氧体磁芯作为主存储器，因此旧时有时将其称为核心存储器。所有不能在高速缓存中得到满足的内存访问请求都会转往主存中。除了主存之外，许多计算机还具有少量的非易失性随机存取存储器。它们与 RAM 不同，在电源断电后，非易失性随机访问存储器并不会丢失内容。ROM(Read Only Memory) 中的内容一旦存储后就不会再被修改。它非常快而且便宜。（如果有人问你，有没有什么又快又便宜的内存设备，那就是 ROM 了）在计算机中，用于启动计算机的引导加载模块（也就是 bootstrap ）就存放在 ROM 中。另外，一些 I/O 卡也采用 ROM 处理底层设备控制。EEPROM(Electrically Erasable PROM,) 和 闪存(flash memory) 也是非易失性的，但是与 ROM 相反，它们可以擦除和重写。不过重写它们需要比写入 RAM 更多的时间，所以它们的使用方式与 ROM 相同，但是与 ROM 不同的是他们可以通过重写字段来纠正程序中出现的错误。闪存也通常用来作为便携性的存储媒介。闪存是数码相机中的胶卷，是便携式音乐播放器的磁盘。闪存的速度介于 RAM 和磁盘之间。另外，与磁盘存储器不同的是，如果闪存擦除的次数太多，会出现磨损。还有一类是 CMOS，它是易失性的。许多计算机都会使用 CMOS 存储器保持当前时间和日期。磁盘下一个层次是磁盘(硬盘)，磁盘同 RAM 相比，每个二进制位的成本低了两个数量级，而且经常也有两个数量级大的容量。磁盘唯一的问题是随机访问数据时间大约慢了三个数量级。磁盘访问慢的原因是因为磁盘的构造不同磁盘是一种机械装置，在一个磁盘中有一个或多个金属盘片，它们以 5400rpm、7200rpm、10800rpm 或更高的速度旋转。从边缘开始有一个机械臂悬横在盘面上，这类似于老式播放塑料唱片 33 转唱机上的拾音臂。信息会写在磁盘一系列的同心圆上。在任意一个给定臂的位置，每个磁头可以读取一段环形区域，称为磁道(track)。把一个给定臂的位置上的所有磁道合并起来，组成了一个柱面(cylinder)。每个磁道划分若干扇区，扇区的值是 512 字节。在现代磁盘中，较外部的柱面比较内部的柱面有更多的扇区。机械臂从一个柱面移动到相邻的柱面大约需要 1ms。而随机移到一个柱面的典型时间为 5ms 至 10ms，具体情况以驱动器为准。一旦磁臂到达正确的磁道上，驱动器必须等待所需的扇区旋转到磁头之下，就开始读写，低端硬盘的速率是50MB/s，而高速磁盘的速率是 160MB/s。需要注意，固态硬盘(Solid State Disk, SSD)不是磁盘，固态硬盘并没有可以移动的部分，外形也不像唱片，并且数据是存储在存储器（闪存）中，与磁盘唯一的相似之处就是它也存储了大量即使在电源关闭也不会丢失的数据。许多计算机支持一种著名的虚拟内存机制，这种机制使得期望运行的存储空间大于实际的物理存储空间。其方法是将程序放在磁盘上，而将主存作为一部分缓存，用来保存最频繁使用的部分程序，这种机制需要快速映像内存地址，用来把程序生成的地址转换为有关字节在 RAM 中的物理地址。这种映像由 CPU 中的一个称为 存储器管理单元(Memory Management Unit, MMU) 的部件来完成。缓存和 MMU 的出现是对系统的性能有很重要的影响，在多道程序系统中，从一个程序切换到另一个程序的机制称为 上下文切换(context switch)，对来自缓存中的资源进行修改并把其写回磁盘是很有必要的。2.4I/O 设备CPU 和存储器不是操作系统需要管理的全部，I/O 设备也与操作系统关系密切。可以参考上面这个图片，I/O 设备一般包括两个部分：设备控制器和设备本身。控制器本身是一块芯片或者一组芯片，它能够控制物理设备。它能够接收操作系统的指令，例如，从设备中读取数据并完成数据的处理。在许多情况下，实际控制设备的过程是非常复杂而且存在诸多细节。因此控制器的工作就是为操作系统提供一个更简单（但仍然非常复杂）的接口。也就是屏蔽物理细节。任何复杂的东西都可以加一层代理来解决，这是计算机或者人类社会很普世的一个解决方案I/O 设备另一部分是设备本身，设备本身有一个相对简单的接口，这是因为接口既不能做很多工作，而且也已经被标准化了。例如，标准化后任何一个 SATA 磁盘控制器就可以适配任意一种 SATA 磁盘，所以标准化是必要的。ATA 代表 高级技术附件(AT Attachment)，而 SATA 表示串行高级技术附件(Serial ATA)。AT 是啥？它是 IBM 公司的第二代个人计算机的高级技术成果，使用 1984 年推出的 6MHz 80286 处理器，这个处理器是当时最强大的。像是高级这种词汇应该慎用，否则 20 年后再回首很可能会被无情打脸。现在 SATA 是很多计算机的标准硬盘接口。由于实际的设备接口隐藏在控制器中，所以操作系统看到的是对控制器的接口，这个接口和设备接口有很大区别。每种类型的设备控制器都是不同的，所以需要不同的软件进行控制。专门与控制器进行信息交流，发出命令处理指令接收响应的软件，称为 设备驱动程序(device driver)。 每个控制器厂家都应该针对不同的操作系统提供不同的设备驱动程序。为了使设备驱动程序能够工作，必须把它安装在操作系统中，这样能够使它在内核态中运行。要将设备驱动程序装入操作系统，一般有三个途径第一个途径是将内核与设备启动程序重新连接，然后重启系统。这是 UNIX 系统采用的工作方式第二个途径是在一个操作系统文件中设置一个入口，通知该文件需要一个设备驱动程序，然后重新启动系统。在重启系统时，操作系统会寻找有关的设备启动程序并把它装载，这是 Windows 采用的工作方式第三个途径是操作系统能够在运行时接收新的设备驱动程序并立刻安装，无需重启操作系统，这种方式采用的少，但是正变得普及起来。热插拔设备，比如 USB 和 IEEE 1394 都需要动态可装载的设备驱动程序。每个设备控制器都有少量用于通信的寄存器，例如，一个最小的磁盘控制器也会有用于指定磁盘地址、内存地址、扇区计数的寄存器。要激活控制器，设备驱动程序回从操作系统获取一条指令，然后翻译成对应的值，并写入设备寄存器中，所有设备寄存器的结合构成了 I/O 端口空间 。在一些计算机中，设备寄存器会被映射到操作系统的可用地址空间，使他们能够向内存一样完成读写操作。在这种计算机中，不需要专门的 I/O 指令，用户程序可以被硬件阻挡在外，防止其接触这些存储器地址（例如，采用基址寄存器和变址寄存器）。在另一些计算机中，设备寄存器被放入一个专门的 I/O 端口空间，每个寄存器都有一个端口地址。在这些计算机中，特殊的 IN 和 OUT 指令会在内核态下启用，它能够允许设备驱动程序和寄存器进行读写。前面第一种方式会限制特殊的 I/O 指令但是允许一些地址空间；后者不需要地址空间但是需要特殊的指令，这两种应用都很广泛。实现输入和输出的方式有三种。在最简单的方式中，用户程序会发起系统调用，内核会将其转换为相应驱动程序的程序调用，然后设备驱动程序启动 I/O 并循环检查该设备，看该设备是否完成了工作（一般会有一些二进制位用来指示设备仍在忙碌中）。当 I/O 调用完成后，设备驱动程序把数据送到指定的地方并返回。然后操作系统会将控制权交给调用者。这种方式称为 忙等待(busy waiting)，这种方式的缺点是要一直占据 CPU，CPU 会一直轮询 I/O 设备直到 I/O 操作完成。第二种方式是设备驱动程序启动设备并且让该设备在操作完成时发生中断。设备驱动程序在这个时刻返回。操作系统接着在需要时阻塞调用者并安排其他工作进行。当设备驱动程序检测到该设备操作完成时，它发出一个 中断 通知操作完成。在操作系统中，中断是非常重要的，所以这需要更加细致的讨论一下。如上图所示，这是一个三步的 I/O 过程，第一步，设备驱动程序会通过写入设备寄存器告诉控制器应该做什么。然后，控制器启动设备。当控制器完成读取或写入被告知需要传输的字节后，它会在步骤 2 中使用某些总线向中断控制器发送信号。如果中断控制器准备好了接收中断信号（如果正忙于一个优先级较高的中断，则可能不会接收），那么它就会在 CPU 的一个引脚上面声明。这就是步骤3在第四步中，中断控制器把该设备的编号放在总线上，这样 CPU 可以读取总线，并且知道哪个设备完成了操作（可能同时有多个设备同时运行）。一旦 CPU 决定去实施中断后，程序计数器和 PSW 就会被压入到当前堆栈中并且 CPU 会切换到内核态。设备编号可以作为内存的一个引用，用来寻找该设备中断处理程序的地址。这部分内存称作中断向量(interrupt vector)。一旦中断处理程序（中断设备的设备驱动程序的一部分）开始后，它会移除栈中的程序计数器和 PSW 寄存器，并把它们进行保存，然后查询设备的状态。在中断处理程序全部完成后，它会返回到先前用户程序尚未执行的第一条指令，这个过程如下实现 I/O 的第三种方式是使用特殊的硬件：直接存储器访问(Direct Memory Access, DMA) 芯片。它可以控制内存和某些控制器之间的位流，而无需 CPU 的干预。CPU 会对 DMA 芯片进行设置，说明需要传送的字节数，有关的设备和内存地址以及操作方向。当 DMA 芯片完成后，会造成中断，中断过程就像上面描述的那样。我们会在后面具体讨论中断过程当另一个中断处理程序正在运行时，中断可能（并且经常）发生在不合宜的时间。 因此，CPU 可以禁用中断，并且可以在之后重启中断。在 CPU 关闭中断后，任何已经发出中断的设备，可以继续保持其中断信号处理，但是 CPU 不会中断，直至中断再次启用为止。如果在关闭中断时，已经有多个设备发出了中断信号，中断控制器将决定优先处理哪个中断，通常这取决于事先赋予每个设备的优先级，最高优先级的设备优先赢得中断权，其他设备则必须等待。2.5总线上面的结构（简单个人计算机的组件图）在小型计算机已经使用了多年，并用在早期的 IBM PC 中。然而，随着处理器核内存变得越来越快，单个总线处理所有请求的能力也达到了上限，其中也包括 IBM PC 总线。必须放弃使用这种模式。其结果导致了其他总线的出现，它们处理 I/O 设备以及 CPU 到存储器的速度都更快。这种演变的结果导致了下面这种结构的出现。上图中的 x86 系统包含很多总线，高速缓存、内存、PCIe、PCI、USB、SATA 和 DMI，每条总线都有不同的传输速率和功能。操作系统必须了解所有的总线配置和管理。其中最主要的总线是 PCIe(Peripheral Component Interconnect Express) 总线。Intel 发明的 PCIe 总线也是作为之前古老的 PCI 总线的继承者，而古老的 PCI 总线也是为了取代古董级别的 ISA(Industry Standard Architecture) 总线而设立的。数十 Gb/s 的传输能力使得 PCIe 比它的前身快很多，而且它们本质上也十分不同。直到发明 PCIe 的 2004 年，大多数总线都是并行且共享的。共享总线架构(shared bus architeture) 表示多个设备使用一些相同的电线传输数据。因此，当多个设备同时发送数据时，此时你需要一个决策者来决定谁能够使用总线。而 PCIe 则不一样，它使用专门的端到端链路。传统 PCI 中使用的并行总线架构(parallel bus architecture) 表示通过多条电线发送相同的数据字。例如，在传统的 PCI 总线上，一个 32 位数据通过 32 条并行的电线发送。而 PCIe 则不同，它选用了串行总线架构(serial bus architecture) ，并通过单个连接（称为通道）发送消息中的所有比特数据，就像网络数据包一样。这样做会简化很多，因为不再确保所有 32 位数据在同一时刻准确到达相同的目的地。通过将多个数据通路并行起来，并行性仍可以有效利用。例如，可以使用 32 条数据通道并行传输 32 条消息。在上图结构中，CPU 通过 DDR3 总线与内存对话，通过 PCIe 总线与外围图形设备 （GPU）对话，通过 DMI(Direct Media Interface)总线经集成中心与所有其他设备对话。而集成控制中心通过串行总线与 USB 设备对话，通过 SATA 总线与硬盘和 DVD 驱动器对话，通过 PCIe 传输以太网络帧。USB(Universal Serial Bus) 是用来将所有慢速 I/O 设备（比如键盘和鼠标）与计算机相连的设备。USB 1.0 可以处理总计 12 Mb/s 的负载，而 USB 2.0 将总线速度提高到 480Mb/s ，而 USB 3.0 能达到不小于 5Gb/s 的速率。所有的 USB 设备都可以直接连接到计算机并能够立刻开始工作，而不像之前那样要求重启计算机。SCSI(Small Computer System Interface) 总线是一种高速总线，用在高速硬盘，扫描仪和其他需要较大带宽的设备上。现在，它们主要用在服务器和工作站中，速度可以达到 640MB/s 。2.6计算机启动过程那么有了上面一些硬件再加上操作系统的支持，我们的计算机就可以开始工作了，那么计算机的启动过程是怎样的呢？下面只是一个简要版的启动过程在每台计算机上有一块双亲板，也就是母板，母板也就是主板，它是计算机最基本也就是最重要的部件之一。主板一般为矩形电路板，上面安装了组成计算机的主要电路系统，一般有 BIOS 芯片、I/O 控制芯片、键盘和面板控制开关接口、指示灯插接件、扩充插槽、主板及插卡的直流电源供电接插件等元件。在母板上有一个称为 基本输入输出系统(Basic Input Output System, BIOS)的程序。在 BIOS 内有底层 I/O 软件，包括读键盘、写屏幕、磁盘I/O 以及其他过程。如今，它被保存在闪存中，它是非易失性的，但是当BIOS 中发现错误时，可以由操作系统进行更新。在计算机启动(booted)时，BIOS 开启，它会首先检查所安装的 RAM 的数量，键盘和其他基础设备是否已安装并且正常响应。接着，它开始扫描 PCIe 和 PCI 总线并找出连在上面的所有设备。即插即用的设备也会被记录下来。如果现有的设备和系统上一次启动时的设备不同，则新的设备将被重新配置。然后，BIOS 通过尝试存储在 CMOS 存储器中的设备清单尝试启动设备。CMOS是 Complementary Metal Oxide Semiconductor（互补金属氧化物半导体）的缩写。它是指制造大规模集成电路芯片用的一种技术或用这种技术制造出来的芯片，是电脑主板上的一块可读写的 RAM 芯片。因为可读写的特性，所以在电脑主板上用来保存 BIOS 设置完电脑硬件参数后的数据，这个芯片仅仅是用来存放数据的。而对 BIOS 中各项参数的设定要通过专门的程序。BIOS 设置程序一般都被厂商整合在芯片中，在开机时通过特定的按键就可进入 BIOS 设置程序，方便地对系统进行设置。因此 BIOS 设置有时也被叫做 CMOS 设置。用户可以在系统启动后进入一个 BIOS 配置程序，对设备清单进行修改。然后，判断是否能够从外部 CD-ROM 和 USB 驱动程序启动，如果启动失败的话（也就是没有），系统将从硬盘启动，boots 设备中的第一个扇区被读入内存并执行。该扇区包含一个程序，该程序通常在引导扇区末尾检查分区表以确定哪个分区处于活动状态。然后从该分区读入第二个启动加载程序，该加载器从活动分区中读取操作系统并启动它。然后操作系统会询问 BIOS 获取配置信息。对于每个设备来说，会检查是否有设备驱动程序。如果没有，则会向用户询问是否需要插入 CD-ROM 驱动（由设备制造商提供）或者从 Internet 上下载。一旦有了设备驱动程序，操作系统会把它们加载到内核中，然后初始化表，创建所需的后台进程，并启动登录程序或GUI。

爱喝奶茶的波波

死锁-死锁检测和恢复

四、死锁检测和恢复第二种技术是死锁的检测和恢复。这种解决方式不会尝试去阻止死锁的出现。相反，这种解决方案会希望死锁尽可能的出现，在监测到死锁出现后，对其进行恢复。下面我们就来探讨一下死锁的检测和恢复的几种方式4.1每种类型一个资源的死锁检测方式每种资源类型都有一个资源是什么意思？我们经常提到的打印机就是这样的，资源只有打印机，但是设备都不会超过一个。可以通过构造一张资源分配表来检测这种错误，比如我们上面提到的的算法来检测从 P1 到 Pn 这 n 个进程中的死锁。假设资源类型为 m，E1 代表资源类型1，E2 表示资源类型 2 ，Ei 代表资源类型 i (1 <= i <= m)。E 表示的是 现有资源向量(existing resource vector)，代表每种已存在的资源总数。现在我们就需要构造两个数组：C 表示的是当前分配矩阵(current allocation matrix) ，R 表示的是 请求矩阵(request matrix)。Ci 表示的是 Pi 持有每一种类型资源的资源数。所以，Cij 表示 Pi 持有资源 j 的数量。Rij 表示 Pi 所需要获得的资源 j 的数量一般来说，已分配资源 j 的数量加起来再和所有可供使用的资源数相加 = 该类资源的总数。死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的，算法会开始对进程做标记，进程被标记后说明进程被执行了，不会进入死锁，当算法结束时，任何没有被标记过的进程都会被判定为死锁进程。上面我们探讨了两种检测死锁的方式，那么现在你知道怎么检测后，你何时去做死锁检测呢？一般来说，有两个考量标准：每当有资源请求时就去检测，这种方式会占用昂贵的 CPU 时间。每隔 k 分钟检测一次，或者当 CPU 使用率降低到某个标准下去检测。考虑到 CPU 效率的原因，如果死锁进程达到一定数量，就没有多少进程可以运行，所以 CPU 会经常空闲。4.2从死锁中恢复上面我们探讨了如何检测进程死锁，我们最终的目的肯定是想让程序能够正常的运行下去，所以针对检测出来的死锁，我们要对其进行恢复，下面我们会探讨几种死锁的恢复方式通过抢占进行恢复在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通知原进程的情况下，将某个资源从进程中强制取走给其他进程使用，使用完后又送回。这种恢复方式一般比较困难而且有些简单粗暴，并不可取。通过回滚进行恢复如果系统设计者和机器操作员知道有可能发生死锁，那么就可以定期检查流程。进程的检测点意味着进程的状态可以被写入到文件以便后面进行恢复。检测点不仅包含存储映像(memory image)，还包含资源状态(resource state)。一种更有效的解决方式是不要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。为了进行恢复，要从上一个较早的检查点上开始，这样所需要资源的进程会回滚到上一个时间点，在这个时间点上，死锁进程还没有获取所需要的资源，可以在此时对其进行资源分配。杀死进程恢复最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通，这时候就需要杀死别的资源进行恢复。另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。

爱喝奶茶的波波

操作系统入门-操作系统

一、操作系统现代计算机系统由一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成。然而，程序员不会直接和这些硬件打交道，而且每位程序员不可能会掌握所有计算机系统的细节，这样我们就不用再编写代码了，所以在硬件的基础之上，计算机安装了一层软件，这层软件能够通过响应用户输入的指令达到控制硬件的效果，从而满足用户需求，这种软件称之为 操作系统，它的任务就是为用户程序提供一个更好、更简单、更清晰的计算机模型。我们一般常见的操作系统主要有 Windows、Linux、FreeBSD 或 macOS ，这种带有图形界面的操作系统被称为 图形用户界面(Graphical User Interface, GUI)，而基于文本、命令行的通常称为 Shell。下面是我们所要探讨的操作系统的部件这是一个操作系统的简化图，最下面的是硬件，硬件包括芯片、电路板、磁盘、键盘、显示器等我们上面提到的设备，在硬件之上是软件。大部分计算机有两种运行模式：内核态 和 用户态，软件中最基础的部分是操作系统，它运行在 内核态 中，内核态也称为 管态 和 核心态，它们都是操作系统的运行状态，只不过是不同的叫法而已。操作系统具有硬件的访问权，可以执行机器能够运行的任何指令。软件的其余部分运行在 用户态 下。用户接口程序(shell 或者 GUI) 处于用户态中，并且它们位于用户态的最低层，允许用户运行其他程序，例如 Web 浏览器、电子邮件阅读器、音乐播放器等。而且，越靠近用户态的应用程序越容易编写，如果你不喜欢某个电子邮件阅读器你可以重新写一个或者换一个，但你不能自行写一个操作系统或者是中断处理程序。这个程序由硬件保护，防止外部对其进行修改。

爱喝奶茶的波波

文件系统-文件系统的优化

四、文件系统的优化4.1磁盘空间管理文件通常存在磁盘中，所以如何管理磁盘空间是一个操作系统的设计者需要考虑的问题。在文件上进行存有两种策略：分配 n 个字节的连续磁盘空间；或者把文件拆分成多个并不一定连续的块。在存储管理系统中，主要有分段管理和 分页管理 两种方式。正如我们所看到的，按连续字节序列存储文件有一个明显的问题，当文件扩大时，有可能需要在磁盘上移动文件。内存中分段也有同样的问题。不同的是，相对于把文件从磁盘的一个位置移动到另一个位置，内存中段的移动操作要快很多。因此，几乎所有的文件系统都把文件分割成固定大小的块来存储。块大小一旦把文件分为固定大小的块来存储，就会出现问题，块的大小是多少？按照磁盘组织方式，扇区、磁道和柱面显然都可以作为分配单位。在分页系统中，分页大小也是主要因素。拥有大的块尺寸意味着每个文件，甚至 1 字节文件，都要占用一个柱面空间，也就是说小文件浪费了大量的磁盘空间。另一方面，小块意味着大部分文件将会跨越多个块，因此需要多次搜索和旋转延迟才能读取它们，从而降低了性能。因此，如果分配的块太大会浪费空间；分配的块太小会浪费时间。记录空闲块一旦指定了块大小，下一个问题就是怎样跟踪空闲块。有两种方法被广泛采用，如下图所示第一种方法是采用磁盘块链表，链表的每个块中包含极可能多的空闲磁盘块号。对于 1 KB 的块和 32 位的磁盘块号，空闲表中每个块包含有 255 个空闲的块号。考虑 1 TB 的硬盘，拥有大概十亿个磁盘块。为了存储全部地址块号，如果每块可以保存 255 个块号，则需要将近 400 万个块。通常，空闲块用于保存空闲列表，因此存储基本上是空闲的。另一种空闲空间管理的技术是位图(bitmap)，n 个块的磁盘需要 n 位位图。在位图中，空闲块用 1 表示，已分配的块用 0 表示。对于 1 TB 硬盘的例子，需要 10 亿位表示，即需要大约 130 000 个 1 KB 块存储。很明显，和 32 位链表模型相比，位图需要的空间更少，因为每个块使用 1 位。只有当磁盘快满的时候，链表需要的块才会比位图少。如果空闲块是长期连续的话，那么空闲列表可以改成记录连续分块而不是单个的块。每个块都会使用 8位、16位、32 位的计数来与每个块相联，来记录连续空闲块的数量。最好的情况是一个空闲块可以用两个数字来表示：第一个空闲块的地址和空闲块的计数。另一方面，如果磁盘严重碎片化，那么跟踪连续分块要比跟踪单个分块运行效率低，因为不仅要存储地址，还要存储数量。这种情况说明了一个操作系统设计者经常遇到的一个问题。有许多数据结构和算法可以用来解决问题，但是选择一个最好的方案需要数据的支持，而这些数据是设计者无法预先拥有的。只有在系统部署完毕真正使用使用后才会获得。现在，回到空闲链表的方法，只有一个指针块保存在内存中。创建文件时，所需要的块从指针块中取出。当它用完时，将从磁盘中读取一个新的指针块。类似地，删除文件时，文件的块将被释放并添加到主存中的指针块中。当块被填满时，写回磁盘。在某些特定的情况下，这个方法导致了不必要的磁盘 IO，如下图所示上面内存中的指针块仅有两个空闲块，如果释放了一个含有三个磁盘块的文件，那么该指针块就会溢出，必须将其写入磁盘，那么就会产生如下图的这种情况。如果现在写入含有三个块的文件，已满的指针不得不再次读入，这将会回到上图 a 中的情况。如果有三个块的文件只是作为临时文件被写入，在释放它时，需要进行另一次磁盘写操作以将完整的指针块写回到磁盘。简而言之，当指针块几乎为空时，一系列短暂的临时文件可能会导致大量磁盘 I/O。避免大部分磁盘 I/O 的另一种方法是拆分完整的指针块。这样，当释放三个块时，变化不再是从 a - b，而是从 a - c，如下图所示现在，系统可以处理一系列临时文件，而不需要进行任何磁盘 I/O。如果内存中指针块满了，就写入磁盘，半满的指针块从磁盘中读入。这里的思想是：要保持磁盘上的大多数指针块为满的状态（减少磁盘的使用），但是在内存中保留了一个半满的指针块。这样，就可以既处理文件的创建又同时可以处理文件的删除操作，而不会为空闲表进行磁盘 I/O。对于位图，会在内存中只保留一个块，只有在该块满了或空了的情形下，才到磁盘上取另一个块。通过在位图的单一块上进行所有的分配操作，磁盘块会紧密的聚集在一起，从而减少了磁盘臂的移动。由于位图是一种固定大小的数据结构，所以如果内核是分页的，就可以把位图放在虚拟内存中，在需要时将位图的页面调入。4.2磁盘配额为了防止一些用户占用太多的磁盘空间，多用户操作通常提供一种磁盘配额(enforcing disk quotas)的机制。系统管理员为每个用户分配最大的文件和块分配，并且操作系统确保用户不会超过其配额。我们下面会谈到这一机制。在用户打开一个文件时，操作系统会找到文件属性和磁盘地址，并把它们送入内存中的打开文件表。其中一个属性告诉文件所有者是谁。任何有关文件的增加都会记到所有者的配额中。第二张表包含了每个用户当前打开文件的配额记录，即使是其他人打开该文件也一样。如上图所示，该表的内容是从被打开文件的所有者的磁盘配额文件中提取出来的。当所有文件关闭时，该记录被写回配额文件。当在打开文件表中建立一新表项时，会产生一个指向所有者配额记录的指针。每次向文件中添加一个块时，文件所有者所用数据块的总数也随之增加，并会同时增加硬限制和软限制的检查。可以超出软限制，但硬限制不可以超出。当已达到硬限制时，再往文件中添加内容将引发错误。同样，对文件数目也存在类似的检查。什么是硬限制和软限制？硬限制是软限制的上限。软限制是为会话或进程实际执行的限制。这允许管理员（或用户）将硬限制设置为允许它们希望允许的最大使用上限。然后，其他用户和进程可以根据需要使用软限制将其资源使用量自限制到更低的上限。当一个用户尝试登陆，系统将检查配额文件以查看用户是否超出了文件数量或磁盘块数量的软限制。如果违反了任一限制，则会显示警告，保存的警告计数减 1，如果警告计数为 0 ，表示用户多次忽略该警告，因而将不允许该用户登录。要想再得到登录的许可，就必须与系统管理员协商。如果用户在退出系统时消除所超过的部分，他们就可以再一次终端会话期间超过其软限制，但无论什么情况下都不会超过硬限制。4.3文件系统备份文件系统的毁坏要比计算机的损坏严重很多。无论是硬件还是软件的故障，只要计算机文件系统被破坏，要恢复起来都是及其困难的，甚至是不可能的。因为文件系统无法抵御破坏，因而我们要在文件系统在被破坏之前做好数据备份，但是备份也不是那么容易，下面我们就来探讨备份的过程。许多人认为为文件系统做备份是不值得的，并且很浪费时间，直到有一天他们的磁盘坏了，他们才意识到事情的严重性。相对来说，公司在这方面做的就很到位。磁带备份主要要处理好以下两个潜在问题中的一个从意外的灾难中恢复这个问题主要是由于外部条件的原因造成的，比如磁盘破裂，水灾火灾等。从错误的操作中恢复第二个问题通常是由于用户意外的删除了原本需要还原的文件。这种情况发生的很频繁，使得 Windows 的设计者们针对 删除 命令专门设计了特殊目录，这就是 回收站(recycle bin)，也就是说，在删除文件的时候，文件本身并不真正从磁盘上消失，而是被放置到这个特殊目录下，等以后需要的时候可以还原回去。文件备份更主要是指这种情况，能够允许几天之前，几周之前的文件从原来备份的磁盘进行还原。做文件备份很耗费时间而且也很浪费空间，这会引起下面几个问题。首先，是要备份整个文件还是仅备份一部分呢？一般来说，只是备份特定目录及其下的全部文件，而不是备份整个文件系统。其次，对上次未修改过的文件再进行备份是一种浪费，因而产生了一种增量转储(incremental dumps) 的思想。最简单的增量转储的形式就是周期性的做全面的备份，而每天只对增量转储完成后发生变化的文件做单个备份。周期性：比如一周或者一个月稍微好一点的方式是只备份最近一次转储以来更改过的文件。当然，这种做法极大的缩减了转储时间，但恢复起来却更复杂，因为最近的全面转储先要全部恢复，随后按逆序进行增量转储。为了方便恢复，人们往往使用更复杂的转储模式。第三，既然待转储的往往是海量数据，那么在将其写入磁带之前对文件进行压缩就很有必要。但是，如果在备份过程中出现了文件损坏的情况，就会导致破坏压缩算法，从而使整个磁带无法读取。所以在备份前是否进行文件压缩需慎重考虑。第四，对正在使用的文件系统做备份是很难的。如果在转储过程中要添加，删除和修改文件和目录，则转储结果可能不一致。因此，因为转储过程中需要花费数个小时的时间，所以有必要在晚上将系统脱机进行备份，然而这种方式的接受程度并不高。所以，人们修改了转储算法，记下文件系统的瞬时快照，即复制关键的数据结构，然后需要把将来对文件和目录所做的修改复制到块中，而不是到处更新他们。磁盘转储到备份磁盘上有两种方案：物理转储和逻辑转储。物理转储(physical dump) 是从磁盘的 0 块开始，依次将所有磁盘块按照顺序写入到输出磁盘，并在复制最后一个磁盘时停止。这种程序的万无一失性是其他程序所不具备的。第二个需要考虑的是坏块的转储。制造大型磁盘而没有瑕疵是不可能的，所以也会存在一些坏块(bad blocks)。有时进行低级格式化后，坏块会被检测出来并进行标记，这种情况的解决办法是用磁盘末尾的一些空闲块所替换。然而，一些块在格式化后会变坏，在这种情况下操作系统可以检测到它们。通常情况下，它可以通过创建一个由所有坏块组成的文件来解决问题，确保它们不会出现在空闲池中并且永远不会被分配。那么此文件是完全不可读的。如果磁盘控制器将所有的坏块重新映射，物理转储还是能够正常工作的。Windows 系统有分页文件(paging files) 和 休眠文件(hibernation files) 。它们在文件还原时不发挥作用，同时也不应该在第一时间进行备份。物理转储和逻辑转储物理转储的主要优点是简单、极为快速（基本上是以磁盘的速度运行），缺点是全量备份，不能跳过指定目录，也不能增量转储，也不能恢复个人文件的请求。因此句大多数情况下不会使用物理转储，而使用逻辑转储。逻辑转储(logical dump)从一个或几个指定的目录开始，递归转储自指定日期开始后更改的文件和目录。因此，在逻辑转储中，转储磁盘上有一系列经过仔细识别的目录和文件，这使得根据请求轻松还原特定文件或目录。既然逻辑转储是最常用的方式，那么下面就让我们研究一下逻辑转储的通用算法。此算法在 UNIX 系统上广为使用，如下图所示待转储的文件系统，其中方框代表目录，圆圈代表文件。黄色的项目表是自上次转储以来修改过。每个目录和文件都被标上其 inode 号。此算法会转储位于修改文件或目录路径上的所有目录（也包括未修改的目录），原因有两个。第一是能够在不同电脑的文件系统中恢复转储的文件。通过这种方式，转储和重新存储的程序能够用来在两个电脑之间传输整个文件系统。第二个原因是能够对单个文件进行增量恢复。逻辑转储算法需要维持一个 inode 为索引的位图(bitmap)，每个 inode 包含了几位。随着算法的进行，位图中的这些位会被设置或清除。算法的执行分成四个阶段。第一阶段从起始目录（本例为根目录）开始检查其中所有的目录项。对每一个修改过的文件，该算法将在位图中标记其 inode。算法还会标记并递归检查每一个目录（不管是否修改过）。在第一阶段结束时，所有修改过的文件和全部目录都在位图中标记了，如下图所示理论上来说，第二阶段再次递归遍历目录树，并去掉目录树中任何不包含被修改过的文件或目录的标记。本阶段执行的结果如下注意，inode 编号为 10、11、14、27、29 和 30 的目录已经被去掉了标记，因为它们所包含的内容没有修改。它们也不会转储。相反，inode 编号为 5 和 6 的目录本身尽管没有被修改过也要被转储，因为在新的机器上恢复当日的修改时需要这些信息。为了提高算法效率，可以将这两阶段的目录树遍历合二为一。现在已经知道了哪些目录和文件必须被转储了，这就是上图 b 中标记的内容，第三阶段算法将以节点号为序，扫描这些 inode 并转储所有标记为需转储的目录，如下图所示为了进行恢复，每个被转储的目录都用目录的属性（所有者、时间）作为前缀。最后，在第四阶段，上图中被标记的文件也被转储，同样，由其文件属性作为前缀。至此，转储结束。从转储磁盘上还原文件系统非常简单。一开始，需要在磁盘上创建空文件系统。然后恢复最近一次的完整转储。由于磁带上最先出现目录，所以首先恢复目录，给出文件系统的框架(skeleton)，然后恢复文件系统本身。在完整存储之后是第一次增量存储，然后是第二次重复这一过程，以此类推。尽管逻辑存储十分简单，但是也会有一些棘手的问题。首先，既然空闲块列表并不是一个文件，那么在所有被转储的文件恢复完毕之后，就需要从零开始重新构造。另外一个问题是关于链接。如果文件链接了两个或者多个目录，而文件只能还原一次，那么并且所有指向该文件的目录都必须还原。还有一个问题是，UNIX 文件实际上包含了许多 空洞(holes)。打开文件，写几个字节，然后找到文件中偏移了一定距离的地址，又写入更多的字节，这么做是合法的。但两者之间的这些块并不属于文件本身，从而也不应该在其上进行文件转储和恢复。最后，无论属于哪一个目录，特殊文件，命名管道以及类似的文件都不应该被转储。4.4文件系统的一致性影响可靠性的一个因素是文件系统的一致性。许多文件系统读取磁盘块、修改磁盘块、再把它们写回磁盘。如果系统在所有块写入之前崩溃，文件系统就会处于一种不一致(inconsistent)的状态。如果某些尚未写回的块是索引节点块，目录块或包含空闲列表的块，则此问题是很严重的。为了处理文件系统一致性问题，大部分计算机都会有应用程序来检查文件系统的一致性。例如，UNIX 有 fsck；Windows 有 sfc，每当引导系统时（尤其是在崩溃后），都可以运行该程序。可以进行两种一致性检查：块的一致性检查和文件的一致性检查。为了检查块的一致性，应用程序会建立两张表，每个包含一个计数器的块，最初设置为 0 。第一个表中的计数器跟踪该块在文件中出现的次数，第二张表中的计数器记录每个块在空闲列表、空闲位图中出现的频率。然后检验程序使用原始设备读取所有的 inode，忽略文件的结构，只返回从零开始的所有磁盘块。从 inode 开始，很容易找到文件中的块数量。每当读取一个块时，该块在第一个表中的计数器 + 1，应用程序会检查空闲块或者位图来找到没有使用的块。空闲列表中块的每次出现都会导致其在第二表中的计数器增加。如果文件系统一致，则每一个块或者在第一个表计数器为 1，或者在第二个表计数器中为 1，如下图所示但是当系统崩溃后，这两张表可能如下所示其中，磁盘块 2 没有出现在任何一张表中，这称为 块丢失(missing block)。尽管块丢失不会造成实际的损害，但它的确浪费了磁盘空间，减少了磁盘容量。块丢失的问题很容易解决，文件系统检验程序把他们加到空闲表中即可。有可能出现的另外一种情况如下所示其中，块 4 在空闲表中出现了 2 次。这种解决方法也很简单，只要重新建立空闲表即可。最糟糕的情况是在两个或者多个文件中出现同一个数据块，如下所示比如上图的磁盘块 5，如果其中一个文件被删除，块 5 会被添加到空闲表中，导致一个块同时处于使用和空闲的两种状态。如果删除这两个文件，那么在空闲表中这个磁盘块会出现两次。文件系统检验程序采取的处理方法是，先分配一磁盘块，把块 5 中的内容复制到空闲块中，然后把它插入到其中一个文件中。这样文件的内容未改变，虽然这些内容可以肯定是不对的，但至少保证了文件的一致性。这一错误应该报告给用户，由用户检查受检情况。除了检查每个磁盘块计数的正确性之外，文件系统还会检查目录系统。这时候会用到一张计数器表，但这时是一个文件（而不是一个块）对应于一个计数器。程序从根目录开始检验，沿着目录树向下查找，检查文件系统的每个目录。对每个目录中的文件，使其计数 + 1。注意，由于存在硬连接，一个文件可能出现在两个或多个目录中。而遇到符号链接是不计数的，不会对目标文件的计数器 + 1。在检验程序完成后，会得到一张由 inode 索引的表，说明每个文件和目录的包含关系。检验程序会将这些数字与存储在文件 inode 中的链接数目做对比。如果 inode 节点的链接计数大户目录项个数，这时即使所有文件从目录中删除，这个计数仍然不是 0 ，inode 不会被删除。这种错误不严重，却因为存在不属于任何目录的文件而浪费了磁盘空间。另一种错误则是潜在的风险。如果同一个文件链接两个目录项，但是 inode 链接计数只为 1，如果删除了任何一个目录项，对应 inode 链接计数变为 0。当 inode 计数为 0 时，文件系统标志 inode 为 未使用，并释放全部的块。这会导致其中一个目录指向一未使用的 inode，而很有可能其块马上就被分配给其他文件。4.5文件系统性能访问磁盘的效率要比内存满的多，是时候又祭出这张图了从内存读一个 32 位字大概是 10ns，从硬盘上读的速率大概是 100MB/S，对每个 32 位字来说，效率会慢了四倍，另外，还要加上 5 - 10 ms 的寻道时间等其他损耗，如果只访问一个字，内存要比磁盘快百万数量级。所以磁盘优化是很有必要的，下面我们会讨论几种优化方式高速缓存最常用的减少磁盘访问次数的技术是使用 块高速缓存(block cache) 或者 缓冲区高速缓存(buffer cache)。高速缓存指的是一系列的块，它们在逻辑上属于磁盘，但实际上基于性能的考虑被保存在内存中。管理高速缓存有不同的算法，常用的算法是：检查全部的读请求，查看在高速缓存中是否有所需要的块。如果存在，可执行读操作而无须访问磁盘。如果检查块不再高速缓存中，那么首先把它读入高速缓存，再复制到所需的地方。之后，对同一个块的请求都通过高速缓存来完成。高速缓存的操作如下图所示由于在高速缓存中有许多块，所以需要某种方法快速确定所需的块是否存在。常用方法是将设备和磁盘地址进行散列操作，然后，在散列表中查找结果。具有相同散列值的块在一个链表中连接在一起（这个数据结构是不是很像 HashMap?），这样就可以沿着冲突链查找其他块。如果高速缓存已满，此时需要调入新的块，则要把原来的某一块调出高速缓存，如果要调出的块在上次调入后已经被修改过，则需要把它写回磁盘。这种情况与分页非常相似，所有常用的页面置换算法我们之前已经介绍过，如果有不熟悉的小伙伴可以参考 https://mp.weixin.qq.com/s/5-k2BJDgEp9symxcSwoprw。比如 FIFO 算法、第二次机会算法、LRU 算法、时钟算法、老化算法等。它们都适用于高速缓存。块提前读第二个明显提高文件系统的性能是，在需要用到块之前，试图提前将其写入高速缓存，从而提高命中率。许多文件都是顺序读取。如果请求文件系统在某个文件中生成块 k，文件系统执行相关操作并且在完成之后，会检查高速缓存，以便确定块 k + 1 是否已经在高速缓存。如果不在，文件系统会为 k + 1 安排一个预读取，因为文件希望在用到该块的时候能够直接从高速缓存中读取。当然，块提前读取策略只适用于实际顺序读取的文件。对随机访问的文件，提前读丝毫不起作用。甚至还会造成阻碍。减少磁盘臂运动高速缓存和块提前读并不是提高文件系统性能的唯一方法。另一种重要的技术是把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘臂的移动次数。当写一个输出文件时，文件系统就必须按照要求一次一次地分配磁盘块。如果用位图来记录空闲块，并且整个位图在内存中，那么选择与前一块最近的空闲块是很容易的。如果用空闲表，并且链表的一部分存在磁盘上，要分配紧邻的空闲块就会困难很多。不过，即使采用空闲表，也可以使用 块簇 技术。即不用块而用连续块簇来跟踪磁盘存储区。如果一个扇区有 512 个字节，有可能系统采用 1 KB 的块（2 个扇区），但却按每 2 块（4 个扇区）一个单位来分配磁盘存储区。这和 2 KB 的磁盘块并不相同，因为在高速缓存中它仍然使用 1 KB 的块，磁盘与内存数据之间传送也是以 1 KB 进行，但在一个空闲的系统上顺序读取这些文件，寻道的次数可以减少一半，从而使文件系统的性能大大改善。若考虑旋转定位则可以得到这类方法的变体。在分配块时，系统尽量把一个文件中的连续块存放在同一个柱面上。在使用 inode 或任何类似 inode 的系统中，另一个性能瓶颈是，读取一个很短的文件也需要两次磁盘访问：一次是访问 inode，一次是访问块。通常情况下，inode 的放置如下图所示其中，全部 inode 放在靠近磁盘开始位置，所以 inode 和它所指向的块之间的平均距离是柱面组的一半，这将会需要较长时间的寻道时间。一个简单的改进方法是，在磁盘中部而不是开始处存放 inode ，此时，在 inode 和第一个块之间的寻道时间减为原来的一半。另一种做法是：将磁盘分成多个柱面组，每个柱面组有自己的 inode，数据块和空闲表，如上图 b 所示。当然，只有在磁盘中装有磁盘臂的情况下，讨论寻道时间和旋转时间才是有意义的。现在越来越多的电脑使用 固态硬盘(SSD)，对于这些硬盘，由于采用了和闪存同样的制造技术，使得随机访问和顺序访问在传输速度上已经较为相近，传统硬盘的许多问题就消失了。但是也引发了新的问题磁盘碎片整理在初始安装操作系统后，文件就会被不断的创建和清除，于是磁盘会产生很多的碎片，在创建一个文件时，它使用的块会散布在整个磁盘上，降低性能。删除文件后，回收磁盘块，可能会造成空穴。磁盘性能可以通过如下方式恢复：移动文件使它们相互挨着，并把所有的至少是大部分的空闲空间放在一个或多个大的连续区域内。Windows 有一个程序 defrag 就是做这个事儿的。Windows 用户会经常使用它，SSD 除外。磁盘碎片整理程序会在让文件系统上很好地运行。Linux 文件系统（特别是 ext2 和 ext3）由于其选择磁盘块的方式，在磁盘碎片整理上一般不会像 Windows 一样困难，因此很少需要手动的磁盘碎片整理。而且，固态硬盘并不受磁盘碎片的影响，事实上，在固态硬盘上做磁盘碎片整理反倒是多此一举，不仅没有提高性能，反而磨损了固态硬盘。所以碎片整理只会缩短固态硬盘的寿命。

爱喝奶茶的波波

操作系统入门-操作系统博物馆

三、操作系统博物馆操作系统已经存在了大半个世纪，在这段时期内，出现了各种类型的操作系统，但并不是所有的操作系统都很出名，下面就罗列一些比较出名的操作系统。3.1大型机操作系统高端一些的操作系统是大型机操作系统，这些大型操作系统可在大型公司的数据中心找到。这些计算机的 I/O 容量与个人计算机不同。一个大型计算机有 1000 个磁盘和数百万 G 字节的容量是很正常，如果有这样一台个人计算机朋友会很羡慕。大型机也在高端 Web 服务器、大型电子商务服务站点上。3.2服务器操作系统下一个层次是服务器操作系统。它们运行在服务器上，服务器可以是大型个人计算机、工作站甚至是大型机。它们通过网络为若干用户服务，并且允许用户共享硬件和软件资源。服务器可提供打印服务、文件服务或 Web 服务。Internet 服务商运行着许多台服务器机器，为用户提供支持，使 Web 站点保存 Web 页面并处理进来的请求。典型的服务器操作系统有 Solaris、FreeBSD、Linux 和 Windows Server 201x3.3多处理器操作系统获得大型计算能力的一种越来越普遍的方式是将多个 CPU 连接到一个系统中。依据它们连接方式和共享方式的不同，这些系统称为并行计算机，多计算机或多处理器。他们需要专门的操作系统，不过通常采用的操作系统是配有通信、连接和一致性等专门功能的服务器操作系统的变体。个人计算机中近来出现了多核芯片，所以常规的台式机和笔记本电脑操作系统也开始与小规模多处理器打交道，而核的数量正在与时俱进。许多主流操作系统比如 Windows 和 Linux 都可以运行在多核处理器上。3.4个人计算机系统接下来一类是个人计算机操作系统。现代个人计算机操作系统支持多道处理程序。在启动时，通常有几十个程序开始运行，它们的功能是为单个用户提供良好的支持。这类系统广泛用于字处理、电子表格、游戏和 Internet 访问。常见的例子是 Linux、FreeBSD、Windows 7、Windows 8 和苹果公司的 OS X 。3.5掌上计算机操作系统随着硬件越来越小化，我们看到了平板电脑、智能手机和其他掌上计算机系统。掌上计算机或者 PDA(Personal Digital Assistant)，个人数字助理 是一种可以握在手中操作的小型计算机。这部分市场已经被谷歌的 Android 系统和苹果的 IOS 主导。3.6嵌入式操作系统嵌入式操作系统用来控制设备的计算机中运行，这种设备不是一般意义上的计算机，并且不允许用户安装软件。典型的例子有微波炉、汽车、DVD 刻录机、移动电话以及 MP3 播放器一类的设备。所有的软件都运行在 ROM 中，这意味着应用程序之间不存在保护，从而获得某种简化。主要的嵌入式系统有 Linux、QNX 和 VxWorks3.7传感器节点操作系统有许多用途需要配置微小传感器节点网络。这些节点是一种可以彼此通信并且使用无线通信基站的微型计算机。这类传感器网络可以用于建筑物周边保护、国土边界保卫、森林火灾探测、气象预测用的温度和降水测量等。每个传感器节点是一个配有 CPU、RAM、ROM 以及一个或多个环境传感器的实实在在的计算机。节点上运行一个小型但是真是的操作系统，通常这个操作系统是事件驱动的，可以响应外部事件。3.8实时操作系统另一类操作系统是实时操作系统，这些系统的特征是将时间作为关键参数。例如，在工业过程控制系统中，工厂中的实时计算机必须收集生产过程的数据并用有关数据控制机器。如果某个动作必须要在规定的时刻发生，这就是硬实时系统。可以在工业控制、民用航空、军事以及类似应用中看到很多这样的系统。另一类系统是 软实时系统，在这种系统中，虽然不希望偶尔违反最终时限，但仍可以接受，并不会引起任何永久性损害。数字音频或多媒体系统就是这类系统。智能手机也是软实时系统。3.9智能卡操作系统最小的操作系统运行在智能卡上。智能卡是一种包含一块 CPU 芯片的信用卡。它有非常严格的运行能耗和存储空间的限制。有些卡具有单项功能，如电子支付；有些智能卡是面向 Java 的。这意味着在智能卡的 ROM 中有一个 Java 虚拟机（Java Virtual Machine, JVM）解释器。

爱喝奶茶的波波

死锁-破坏死锁

六、破坏死锁死锁本质上是无法避免的，因为它需要获得未知的资源和请求，但是死锁是满足四个条件后才出现的，它们分别是互斥保持和等待不可抢占循环等待我们分别对这四个条件进行讨论，按理说破坏其中的任意一个条件就能够破坏死锁6.1破坏互斥条件我们首先考虑的就是破坏互斥使用条件。如果资源不被一个进程独占，那么死锁肯定不会产生。如果两个打印机同时使用一个资源会造成混乱，打印机的解决方式是使用 假脱机打印机(spooling printer) ，这项技术可以允许多个进程同时产生输出，在这种模型中，实际请求打印机的唯一进程是打印机守护进程，也称为后台进程。后台进程不会请求其他资源。我们可以消除打印机的死锁。后台进程通常被编写为能够输出完整的文件后才能打印，假如两个进程都占用了假脱机空间的一半，而这两个进程都没有完成全部的输出，就会导致死锁。因此，尽量做到尽可能少的进程可以请求资源。6.2破坏保持等待的条件第二种方式是如果我们能阻止持有资源的进程请求其他资源，我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。如果所需的资源可用，进程会完成资源的分配并运行到结束。如果有任何一个资源处于频繁分配的情况，那么没有分配到资源的进程就会等待。很多进程无法在执行完成前就知道到底需要多少资源，如果知道的话，就可以使用银行家算法；还有一个问题是这样无法合理有效利用资源。还有一种方式是进程在请求其他资源时，先释放所占用的资源，然后再尝试一次获取全部的资源。6.3破坏不可抢占条件破坏不可抢占条件也是可以的。可以通过虚拟化的方式来避免这种情况。6.4破坏循环等待条件现在就剩最后一个条件了，循环等待条件可以通过多种方法来破坏。一种方式是制定一个标准，一个进程在任何时候只能使用一种资源。如果需要另外一种资源，必须释放当前资源。对于需要将大文件从磁带复制到打印机的过程，此限制是不可接受的。另一种方式是将所有的资源统一编号，如下图所示进程可以在任何时间提出请求，但是所有的请求都必须按照资源的顺序提出。如果按照此分配规则的话，那么资源分配之间不会出现环。尽管通过这种方式来消除死锁，但是编号的顺序不可能让每个进程都会接受。

爱喝奶茶的波波

死锁-其他问题

七、其他问题下面我们来探讨一下其他问题，包括 通信死锁、活锁是什么、饥饿问题和两阶段加锁7.1两阶段加锁虽然很多情况下死锁的避免和预防都能处理，但是效果并不好。随着时间的推移，提出了很多优秀的算法用来处理死锁。例如在数据库系统中，一个经常发生的操作是请求锁住一些记录，然后更新所有锁定的记录。当同时有多个进程运行时，就会有死锁的风险。一种解决方式是使用 两阶段提交(two-phase locking)。顾名思义分为两个阶段，一阶段是进程尝试一次锁定它需要的所有记录。如果成功后，才会开始第二阶段，第二阶段是执行更新并释放锁。第一阶段并不做真正有意义的工作。如果在第一阶段某个进程所需要的记录已经被加锁，那么该进程会释放所有锁定的记录并重新开始第一阶段。从某种意义上来说，这种方法类似于预先请求所有必需的资源或者是在进行一些不可逆的操作之前请求所有的资源。不过在一般的应用场景中，两阶段加锁的策略并不通用。如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受的。7.2通信死锁我们上面一直讨论的是资源死锁，资源死锁是一种死锁类型，但并不是唯一类型，还有通信死锁，也就是两个或多个进程在发送消息时出现的死锁。进程 A 给进程 B 发了一条消息，然后进程 A 阻塞直到进程 B 返回响应。假设请求消息丢失了，那么进程 A 在一直等着回复，进程 B 也会阻塞等待请求消息到来，这时候就产生死锁。尽管会产生死锁，但是这并不是一个资源死锁，因为 A 并没有占据 B 的资源。事实上，通信死锁并没有完全可见的资源。根据死锁的定义来说：每个进程因为等待其他进程引起的事件而产生阻塞，这就是一种死锁。相较于最常见的通信死锁，我们把上面这种情况称为通信死锁(communication deadlock)。通信死锁不能通过调度的方式来避免，但是可以使用通信中一个非常重要的概念来避免：超时(timeout)。在通信过程中，只要一个信息被发出后，发送者就会启动一个定时器，定时器会记录消息的超时时间，如果超时时间到了但是消息还没有返回，就会认为消息已经丢失并重新发送，通过这种方式，可以避免通信死锁。但是并非所有网络通信发生的死锁都是通信死锁，也存在资源死锁，下面就是一个典型的资源死锁。当一个数据包从主机进入路由器时，会被放入一个缓冲区，然后再传输到另外一个路由器，再到另一个，以此类推直到目的地。缓冲区都是资源并且数量有限。如下图所示，每个路由器都有 10 个缓冲区（实际上有很多）。假如路由器 A 的所有数据需要发送到 B ，B 的所有数据包需要发送到 D，然后 D 的所有数据包需要发送到 A 。没有数据包可以移动，因为在另一端没有缓冲区可用，这就是一个典型的资源死锁。7.3活锁你会发现一个很有意思的事情，死锁就跟榆木脑袋一样，不会转弯。我看过古代的一则故事：如果说死锁很痴情的话，那么活锁用一则成语来表示就是 弄巧成拙。某些情况下，当进程意识到它不能获取所需要的下一个锁时，就会尝试礼貌的释放已经获得的锁，然后等待非常短的时间再次尝试获取。可以想像一下这个场景：当两个人在狭路相逢的时候，都想给对方让路，相同的步调会导致双方都无法前进。现在假想有一对并行的进程用到了两个资源。它们分别尝试获取另一个锁失败后，两个进程都会释放自己持有的锁，再次进行尝试，这个过程会一直进行重复。很明显，这个过程中没有进程阻塞，但是进程仍然不会向下执行，这种状况我们称之为 活锁(livelock)。7.4饥饿与死锁和活锁的一个非常相似的问题是 饥饿(starvvation)。想象一下你什么时候会饿？一段时间不吃东西是不是会饿？对于进程来讲，最重要的就是资源，如果一段时间没有获得资源，那么进程会产生饥饿，这些进程会永远得不到服务。我们假设打印机的分配方案是每次都会分配给最小文件的进程，那么要打印大文件的进程会永远得不到服务，导致进程饥饿，进程会无限制的推后，虽然它没有阻塞。

爱喝奶茶的波波

操作系统面试必知题

1.解释一下什么是操作系统操作系统是运行在计算机上最重要的一种软件，它管理计算机的资源和进程以及所有的硬件和软件。它为计算机硬件和软件提供了一种中间层通常情况下，计算机上会运行着许多应用程序，它们都需要对内存和 CPU 进行交互，操作系统的目的就是为了保证这些访问和交互能够准确无误的进行。2.解释一下操作系统的主要目的是什么操作系统是一种软件，它的主要目的有三种管理计算机资源，这些资源包括 CPU、内存、磁盘驱动器、打印机等。提供一种图形界面，就像我们前面描述的那样，它提供了用户和计算机之间的桥梁。为其他软件提供服务，操作系统与软件进行交互，以便为其分配运行所需的任何必要资源。3.操作系统的种类有哪些操作系统通常预装在你购买计算机之前。大部分用户都会使用默认的操作系统，但是你也可以升级甚至更改操作系统。但是一般常见的操作系统只有三种：Windows、macOS 和 Linux。4.操作系统结构单体系统在大多数系统中，整个系统在内核态以单一程序的方式运行。整个操作系统是以程序集合来编写的，链接在一块形成一个大的二进制可执行程序，这种系统称为单体系统。在单体系统中构造实际目标程序时，会首先编译所有单个过程（或包含这些过程的文件），然后使用系统链接器将它们全部绑定到一个可执行文件中在单体系统中，对于每个系统调用都会有一个服务程序来保障和运行。需要一组实用程序来弥补服务程序需要的功能，例如从用户程序中获取数据。可将各种过程划分为一个三层模型除了在计算机初启动时所装载的核心操作系统外，许多操作系统还支持额外的扩展。比如 I/O 设备驱动和文件系统。这些部件可以按需装载。在 UNIX 中把它们叫做 共享库(shared library)，在 Windows 中则被称为 动态链接库(Dynamic Link Library,DLL)。他们的扩展名为 .dll，在 C:\Windows\system32 目录下存在 1000 多个 DLL 文件，所以不要轻易删除 C 盘文件，否则可能就炸了哦。分层系统分层系统使用层来分隔不同的功能单元。每一层只与该层的上层和下层通信。每一层都使用下面的层来执行其功能。层之间的通信通过预定义的固定接口通信。微内核为了实现高可靠性，将操作系统划分成小的、层级之间能够更好定义的模块是很有必要的，只有一个模块 --- 微内核 --- 运行在内核态，其余模块可以作为普通用户进程运行。由于把每个设备驱动和文件系统分别作为普通用户进程，这些模块中的错误虽然会使这些模块崩溃，但是不会使整个系统死机。MINIX 3 是微内核的代表作，它的具体结构如下在内核的外部，系统的构造有三层，它们都在用户态下运行，最底层是设备驱动器。由于它们都在用户态下运行，所以不能物理的访问 I/O 端口空间，也不能直接发出 I/O 命令。相反，为了能够对 I/O 设备编程，驱动器构建一个结构，指明哪个参数值写到哪个 I/O 端口，并声称一个内核调用，这样就完成了一次调用过程。客户-服务器模式微内核思想的策略是把进程划分为两类：服务器，每个服务器用来提供服务；客户端，使用这些服务。这个模式就是所谓的 客户-服务器模式。客户-服务器模式会有两种载体，一种情况是一台计算机既是客户又是服务器，在这种方式下，操作系统会有某种优化；但是普遍情况下是客户端和服务器在不同的机器上，它们通过局域网或广域网连接。客户通过发送消息与服务器通信，客户端并不需要知道这些消息是在本地机器上处理，还是通过网络被送到远程机器上处理。对于客户端而言，这两种情形是一样的：都是发送请求并得到回应。5.什么是按需分页在操作系统中，进程是以页为单位加载到内存中的，按需分页是一种虚拟内存的管理方式。在使用请求分页的系统中，只有在尝试访问页面所在的磁盘并且该页面尚未在内存中时，也就发生了缺页异常，操作系统才会将磁盘页面复制到内存中。6.多处理系统的优势随着处理器的不断增加，我们的计算机系统由单机系统变为了多处理系统，多处理系统的吞吐量比较高，多处理系统拥有多个并行的处理器，这些处理器共享时钟、内存、总线、外围设备等。多处理系统由于可以共享资源，因此可以开源节流，省钱。整个系统的可靠性也随之提高。7.什么是内核在计算机中，内核是一个计算机程序，它是操作系统的核心，可以控制操作系统中所有的内容。内核通常是在 boot loader 装载程序之前加载的第一个程序。这里还需要了解一下什么是 boot loader。boot loader 又被称为引导加载程序，它是一个程序，能够将计算机的操作系统放入内存中。在电源通电或者计算机重启时，BIOS 会执行一些初始测试，然后将控制权转移到引导加载程序所在的主引导记录(MBR) 。8.什么是实时系统实时操作系统对时间做出了严格的要求，实时操作系统分为两种：硬实时和软实时硬实时操作系统规定某个动作必须在规定的时刻内完成或发生，比如汽车生产车间，焊接机器必须在某一时刻内完成焊接，焊接的太早或者太晚都会对汽车造成永久性伤害。软实时操作系统虽然不希望偶尔违反最终的时限要求，但是仍然可以接受。并且不会引起任何永久性伤害。比如数字音频、多媒体、手机都是属于软实时操作系统。你可以简单理解硬实时和软实时的两个指标：是否在时刻内必须完成以及是否造成严重损害。9.什么是虚拟内存虚拟内存是一种内存分配方案，是一项可以用来辅助内存分配的机制。我们知道，应用程序是按页装载进内存中的。但并不是所有的页都会装载到内存中，计算机中的硬件和软件会将数据从 RAM 临时传输到磁盘中来弥补内存的不足。如果没有虚拟内存的话，一旦你将计算机内存填满后，计算机会对你说：对不起，您无法再加载任何应用程序，请关闭另一个应用程序以加载新的应用程序。对于虚拟内存，计算机可以执行操作是查看内存中最近未使用过的区域，然后将其复制到硬盘上。虚拟内存通过复制技术实现了 妹子，你快来看哥哥能装这么多程序 的资本。复制是自动进行的，你无法感知到它的存在。10.什么是进程和进程表进程就是正在执行程序的实例，比如说 Web 程序就是一个进程，shell 也是一个进程，文章编辑器 typora 也是一个进程。操作系统负责管理所有正在运行的进程，操作系统会为每个进程分配特定的时间来占用 CPU，操作系统还会为每个进程分配特定的资源。操作系统为了跟踪每个进程的活动状态，维护了一个进程表。在进程表的内部，列出了每个进程的状态以及每个进程使用的资源等。http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html 这个网站上面有一个关于进程状态轮转的动画，做的真是太好了。11.什么是线程，线程和进程的区别这又是一道老生常谈的问题了，从操作系统的角度来回答一下吧。我们上面说到进程是正在运行的程序的实例，而线程其实就是进程中的单条流向，因为线程具有进程中的某些属性，所以线程又被称为轻量级的进程。浏览器如果是一个进程的话，那么浏览器下面的每个 tab 页可以看作是一个个的线程。下面是线程和进程持有资源的区别线程不像进程那样具有很强的独立性，线程之间会共享数据创建线程的开销要比进程小很多，因为创建线程仅仅需要堆栈指针和程序计数器就可以了，而创建进程需要操作系统分配新的地址空间，数据资源等，这个开销比较大。12.使用多线程的好处是什么多线程是程序员不得不知的基本素养之一，所以，下面我们给出一些多线程编程的好处能够提高对用户的响应顺序在流程中的资源共享比较经济适用能够对多线程架构有深入的理解13.什么是 RR 调度算法RR(round-robin) 调度算法主要针对分时系统，RR 的调度算法会把时间片以相同的部分并循环的分配给每个进程，RR 调度算法没有优先级的概念。这种算法的实现比较简单，而且每个线程都会占有时间片，并不存在线程饥饿的问题。14.导致系统出现死锁的情况死锁的出现需要同时满足下面四个条件互斥(Mutual Exclusion)：一次只能有一个进程使用资源。如果另一个进程请求该资源，则必须延迟请求进程，直到释放该资源为止。保持并等待(Hold and Wait)：必须存在一个进程，该进程至少持有一个资源，并且正在等待获取其他进程当前所持有的资源。无抢占(No Preemption)：资源不能被抢占，也就是说，在进程完成其任务之后，只能由拥有它的进程自动释放资源。循环等待(Circular Wait) ：必须存在一组 {p0，p1，..... pn} 的等待进程，使 p0 等待 p1 持有的资源，p1 等待由 p2 持有的资源， pn-1 正在等待由 pn 持有的资源，而 pn 正在等待由 p0 持有的资源。15.RAID 的不同级别RAID 称为 磁盘冗余阵列，简称 磁盘阵列。利用虚拟化技术把多个硬盘结合在一起，成为一个或多个磁盘阵列组，目的是提升性能或数据冗余。RAID 有不同的级别RAID 0 - 无容错的条带化磁盘阵列RAID 1 - 镜像和双工RAID 2 - 内存式纠错码RAID 3 - 比特交错奇偶校验RAID 4 - 块交错奇偶校验RAID 5 - 块交错分布式奇偶校验RAID 6 - P + Q冗余16.什么是 DMADMA 的中文名称是直接内存访问，它意味着 CPU 授予 I/O 模块权限在不涉及 CPU 的情况下读取或写入内存。也就是 DMA 可以不需要 CPU 的参与。这个过程由称为 DMA 控制器（DMAC）的芯片管理。由于 DMA 设备可以直接在内存之间传输数据，而不是使用 CPU 作为中介，因此可以缓解总线上的拥塞。DMA 通过允许 CPU 执行任务，同时 DMA 系统通过系统和内存总线传输数据来提高系统并发性。17.什么是设备驱动程序在计算机中，设备驱动程序是一种计算机程序，它能够控制或者操作连接到计算机的特定设备。驱动程序提供了与硬件进行交互的软件接口，使操作系统和其他计算机程序能够访问特定设备，不用需要了解其硬件的具体构造。18.进程间的通信方式通信概念进程间的通信方式比较多，首先你需要理解下面这几个概念竞态条件：即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)。临界区：不仅共享资源会造成竞态条件，事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢？或许一句话可以概括说明：禁止一个或多个进程在同一时刻对共享资源（包括共享内存、共享文件等）进行读写。换句话说，我们需要一种 互斥(mutual exclusion) 条件，这也就是说，如果一个进程在某种方式下使用共享变量和文件的话，除该进程之外的其他进程就禁止做这种事（访问统一资源）。一个好的解决方案，应该包含下面四种条件任何时候两个进程不能同时处于临界区不应对 CPU 的速度和数量做任何假设位于临界区外的进程不得阻塞其他进程不能使任何进程无限等待进入临界区忙等互斥：当一个进程在对资源进行修改时，其他进程必须进行等待，进程之间要具有互斥性，我们讨论的解决方案其实都是基于忙等互斥提出的。解决方案进程间的通信用专业一点的术语来表示就是 Inter Process Communication，IPC，它主要有下面几种通信方式消息传递：消息传递是进程间实现通信和同步等待的机制，使用消息传递，进程间的交流不需要共享变量，直接就可以进行通信；消息传递分为发送方和接收方先进先出队列：先进先出队列指的是两个不相关联进程间的通信，两个进程之间可以彼此相互进程通信，这是一种全双工通信方式管道：管道用于两个相关进程之间的通信，这是一种半双工的通信方式，如果需要全双工，需要另外一个管道。直接通信：在这种进程通信的方式中，进程与进程之间只存在一条链接，进程间要明确通信双方的命名。间接通信：间接通信是通信双方不会直接建立连接，而是找到一个中介者，这个中介者可能是个对象等等，进程可以在其中放置消息，并且可以从中删除消息，以此达到进程间通信的目的。消息队列：消息队列是内核中存储消息的链表，它由消息队列标识符进行标识，这种方式能够在不同的进程之间提供全双工的通信连接。共享内存：共享内存是使用所有进程之间的内存来建立连接，这种类型需要同步进程访问来相互保护。19.进程间状态模型cat chapter1 chapter2 chapter3 | grep tree第一个进程是 cat，将三个文件级联并输出。第二个进程是 grep，它从输入中选择具有包含关键字 tree 的内容，根据这两个进程的相对速度（这取决于两个程序的相对复杂度和各自所分配到的 CPU 时间片），可能会发生下面这种情况，grep 准备就绪开始运行，但是输入进程还没有完成，于是必须阻塞 grep 进程，直到输入完毕。当一个进程开始运行时，它可能会经历下面这几种状态图中会涉及三种状态运行态，运行态指的就是进程实际占用 CPU 时间片运行时就绪态，就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态阻塞态，除非某种外部事件发生，否则进程不能运行逻辑上来说，运行态和就绪态是很相似的。这两种情况下都表示进程可运行，但是第二种情况没有获得 CPU 时间分片。第三种状态与前两种状态不同的原因是这个进程不能运行，CPU 空闲时也不能运行。三种状态会涉及四种状态间的切换，在操作系统发现进程不能继续执行时会发生状态1的轮转，在某些系统中进程执行系统调用，例如 pause，来获取一个阻塞的状态。在其他系统中包括 UNIX，当进程从管道或特殊文件（例如终端）中读取没有可用的输入时，该进程会被自动终止。转换 2 和转换 3 都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换 2 的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行 CPU 时间片了。当所有其他进程都运行过后，这时候该是让第一个进程重新获得 CPU 时间片的时候了，就会发生转换 3。程序调度指的是，决定哪个进程优先被运行和运行多久，这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求。当进程等待的一个外部事件发生时（如从外部输入一些数据后），则发生转换 4。如果此时没有其他进程在运行，则立刻触发转换 3，该进程便开始运行，否则该进程会处于就绪阶段，等待 CPU 空闲后再轮到它运行。20.调度算法都有哪些调度算法分为三大类：批处理中的调度、交互系统中的调度、实时系统中的调度批处理中的调度先来先服务很像是先到先得。。。可能最简单的非抢占式调度算法的设计就是 先来先服务(first-come,first-serverd)。使用此算法，将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。最短作业优先批处理中，第二种调度算法是 最短作业优先(Shortest Job First)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法如上图 a 所示，这里有 4 个作业 A、B、C、D ，运行时间分别为 8、4、4、4 分钟。若按图中的次序运行，则 A 的周转时间为 8 分钟，B 为 12 分钟，C 为 16 分钟，D 为 20 分钟，平均时间内为 14 分钟。现在考虑使用最短作业优先算法运行 4 个作业，如上图 b 所示，目前的周转时间分别为 4、8、12、20，平均为 11 分钟，可以证明最短作业优先是最优的。考虑有 4 个作业的情况，其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束，第二个在时间 a + b 结束，以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大，所以 a 应该是最短优先作业，其次是 b，然后是 c ，最后是 d 它就只能影响自己的周转时间了。需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。最短剩余时间优先最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务。交互式系统中的调度交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度轮询调度一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段，称为时间片(quantum)，在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b。优先级调度事实情况是不是所有的进程都是优先级相等的。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会。最短进程优先对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0，现在假设测量到其下一次运行时间为 T1，可以用两个值的加权来改进估计时间，即aT0+ (1- 1)T1。通过选择 a 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当 a = 1/2 时，可以得到下面这个序列可以看到，在三轮过后，T0 在新的估计值中所占比重下降至 1/8。有时把这种通过当前测量值和先前估计值进行加权平均从而得到下一个估计值的技术称作 老化(aging)。这种方法会使用很多预测值基于当前值的情况。彩票调度有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是 彩票调度(lottery scheduling)算法。他的基本思想为进程提供各种系统资源的彩票。当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得资源。比如在 CPU 进行调度时，系统可以每秒持有 50 次抽奖，每个中奖进程会获得额外运行时间的奖励。可以把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生 速度之靴 的效果。公平分享调度如果用户 1 启动了 9 个进程，而用户 2 启动了一个进程，使用轮转或相同优先级调度算法，那么用户 1 将得到 90 % 的 CPU 时间，而用户 2 将之得到 10 % 的 CPU 时间。为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些CPU 时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证，那么无论一个用户有多少个进程，都将获得相同的 CPU 份额21.页面置换算法都有哪些最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法。FIFO 会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择。第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。时钟 算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法。LRU 算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。NFU 算法是一种近似于 LRU 的算法，它的性能不是非常好。老化 算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock 是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现。最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。22.影响调度程序的指标是什么会有下面几个因素决定调度程序的好坏CPU 使用率：CPU 正在执行任务（即不处于空闲状态）的时间百分比。等待时间这是进程轮流执行的时间，也就是进程切换的时间吞吐量单位时间内完成进程的数量响应时间这是从提交流程到获得有用输出所经过的时间。周转时间从提交流程到完成流程所经过的时间。23.什么是僵尸进程僵尸进程是已完成且处于终止状态，但在进程表中却仍然存在的进程。僵尸进程通常发生在父子关系的进程中，由于父进程仍需要读取其子进程的退出状态所造成的。

爱喝奶茶的波波

内存管理-一种存储器抽象：地址空间

二、一种存储器抽象：地址空间把物理内存暴露给进程会有几个主要的缺点：第一个问题是，如果用户程序可以寻址内存的每个字节，它们就可以很容易的破坏操作系统，从而使系统停止运行（除非使用 IBM 360 那种 lock-and-key 模式或者特殊的硬件进行保护）。即使在只有一个用户进程运行的情况下，这个问题也存在。第二点是，这种模型想要运行多个程序是很困难的（如果只有一个 CPU 那就是顺序执行）。在个人计算机上，一般会打开很多应用程序，比如输入法、电子邮件、浏览器，这些进程在不同时刻会有一个进程正在运行，其他应用程序可以通过鼠标来唤醒。在系统中没有物理内存的情况下很难实现。2.1地址空间的概念如果要使多个应用程序同时运行在内存中，必须要解决两个问题：保护和 重定位。我们来看 IBM 360 是如何解决的：第一种解决方式是用保护密钥标记内存块，并将执行过程的密钥与提取的每个存储字的密钥进行比较。这种方式只能解决第一种问题（破坏操作系统），但是不能解决多进程在内存中同时运行的问题。还有一种更好的方式是创造一个存储器抽象：地址空间(the address space)。就像进程的概念创建了一种抽象的 CPU 来运行程序，地址空间也创建了一种抽象内存供程序使用。地址空间是进程可以用来寻址内存的地址集。每个进程都有它自己的地址空间，独立于其他进程的地址空间，但是某些进程会希望可以共享地址空间。基址寄存器和变址寄存器最简单的办法是使用动态重定位(dynamic relocation)技术，它就是通过一种简单的方式将每个进程的地址空间映射到物理内存的不同区域。从 CDC 6600(世界上最早的超级计算机)到 Intel 8088(原始 IBM PC 的核心)所使用的经典办法是给每个 CPU 配置两个特殊硬件寄存器，通常叫做基址寄存器(basic register)和变址寄存器(limit register)。当使用基址寄存器和变址寄存器时，程序会装载到内存中的连续位置并且在装载期间无需重定位。当一个进程运行时，程序的起始物理地址装载到基址寄存器中，程序的长度则装载到变址寄存器中。在上图 c 中，当一个程序运行时，装载到这些硬件寄存器中的基址和变址寄存器的值分别是 0 和 16384。当第二个程序运行时，这些值分别是 16384 和 32768。如果第三个 16 KB 的程序直接装载到第二个程序的地址之上并且运行，这时基址寄存器和变址寄存器的值会是 32768 和 16384。那么我们可以总结下基址寄存器：存储数据内存的起始位置变址寄存器：存储应用程序的长度。每当进程引用内存以获取指令或读取、写入数据时，CPU 都会自动将基址值添加到进程生成的地址中，然后再将其发送到内存总线上。同时，它检查程序提供的地址是否大于或等于变址寄存器 中的值。如果程序提供的地址要超过变址寄存器的范围，那么会产生错误并中止访问。这样，对上图 c 中执行 JMP 28 这条指令后，硬件会把它解释为 JMP 16412，所以程序能够跳到 CMP 指令，过程如下使用基址寄存器和变址寄存器是给每个进程提供私有地址空间的一种非常好的方法，因为每个内存地址在送到内存之前，都会先加上基址寄存器的内容。在很多实际系统中，对基址寄存器和变址寄存器都会以一定的方式加以保护，使得只有操作系统可以修改它们。在 CDC 6600 中就提供了对这些寄存器的保护，但在 Intel 8088 中则没有，甚至没有变址寄存器。但是，Intel 8088 提供了许多基址寄存器，使程序的代码和数据可以被独立的重定位，但是对于超出范围的内存引用没有提供保护。所以你可以知道使用基址寄存器和变址寄存器的缺点，在每次访问内存时，都会进行 ADD 和 CMP 运算。CMP 指令可以执行的很快，但是加法就会相对慢一些，除非使用特殊的加法电路，否则加法因进位传播时间而变慢。2.2交换技术如果计算机的物理内存足够大来容纳所有的进程，那么之前提及的方案或多或少是可行的。但是实际上，所有进程需要的 RAM 总容量要远远高于内存的容量。在 Windows、OS X、或者 Linux 系统中，在计算机完成启动（Boot）后，大约有 50 - 100 个进程随之启动。例如，当一个 Windows 应用程序被安装后，它通常会发出命令，以便在后续系统启动时，将启动一个进程，这个进程除了检查应用程序的更新外不做任何操作。一个简单的应用程序可能会占用 5 - 10MB 的内存。其他后台进程会检查电子邮件、网络连接以及许多其他诸如此类的任务。这一切都会发生在第一个用户启动之前。如今，像是 Photoshop 这样的重要用户应用程序仅仅需要 500 MB 来启动，但是一旦它们开始处理数据就需要许多 GB 来处理。从结果上来看，将所有进程始终保持在内存中需要大量内存，如果内存不足，则无法完成。所以针对上面内存不足的问题，提出了两种处理方式：最简单的一种方式就是交换(swapping)技术，即把一个进程完整的调入内存，然后再内存中运行一段时间，再把它放回磁盘。空闲进程会存储在磁盘中，所以这些进程在没有运行时不会占用太多内存。另外一种策略叫做虚拟内存(virtual memory)，虚拟内存技术能够允许应用程序部分的运行在内存中。下面我们首先先探讨一下交换过程下面是一个交换过程刚开始的时候，只有进程 A 在内存中，然后从创建进程 B 和进程 C 或者从磁盘中把它们换入内存，然后在图 d 中，A 被换出内存到磁盘中，最后 A 重新进来。因为图 g 中的进程 A 现在到了不同的位置，所以在装载过程中需要被重新定位，或者在交换程序时通过软件来执行；或者在程序执行期间通过硬件来重定位。基址寄存器和变址寄存器就适用于这种情况。交换在内存创建了多个 空闲区(hole)，内存会把所有的空闲区尽可能向下移动合并成为一个大的空闲区。这项技术称为内存紧缩(memory compaction)。但是这项技术通常不会使用，因为这项技术回消耗很多 CPU 时间。例如，在一个 16GB 内存的机器上每 8ns 复制 8 字节，它紧缩全部的内存大约要花费 16s。有一个值得注意的问题是，当进程被创建或者换入内存时应该为它分配多大的内存。如果进程被创建后它的大小是固定的并且不再改变，那么分配策略就比较简单：操作系统会准确的按其需要的大小进行分配。但是如果进程的 data segment 能够自动增长，例如，通过动态分配堆中的内存，肯定会出现问题。这里还是再提一下什么是 data segment 吧。从逻辑层面操作系统把数据分成不同的段(不同的区域)来存储：代码段（codesegment/textsegment）：又称文本段，用来存放指令，运行代码的一块内存空间此空间大小在代码运行前就已经确定内存空间一般属于只读，某些架构的代码也允许可写在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。数据段（datasegment）：可读可写存储初始化的全局变量和初始化的 static 变量数据段中数据的生存期是随程序持续性（随进程持续性）随进程持续性：进程创建就存在，进程死亡就消失bss段（bsssegment）：可读可写存储未初始化的全局变量和未初始化的 static 变量bss 段中数据的生存期随进程持续性bss 段中的数据一般默认为0rodata段：只读数据比如 printf 语句中的格式字符串和开关语句的跳转表。也就是常量区。例如，全局作用域中的 const int ival = 10，ival 存放在 .rodata 段；再如，函数局部作用域中的 printf("Hello world %d\n", c); 语句中的格式字符串 "Hello world %d\n"，也存放在 .rodata 段。栈（stack）：可读可写存储的是函数或代码中的局部变量(非 static 变量)栈的生存期随代码块持续性，代码块运行就给你分配空间，代码块结束，就自动回收空间堆（heap）：可读可写存储的是程序运行期间动态分配的 malloc/realloc 的空间堆的生存期随进程持续性，从 malloc/realloc 到 free 一直存在下面是我们用 Borland C++ 编译过后的结果_TEXT segment dword public use32 'CODE' _TEXT ends _DATA segment dword public use32 'DATA' _DATA ends _BSS segment dword public use32 'BSS' _BSS ends段定义( segment ) 是用来区分或者划分范围区域的意思。汇编语言的 segment 伪指令表示段定义的起始，ends 伪指令表示段定义的结束。段定义是一段连续的内存空间所以内存针对自动增长的区域，会有三种处理方式如果一个进程与空闲区相邻，那么可把该空闲区分配给进程以供其增大。如果进程相邻的是另一个进程，就会有两种处理方式：要么把需要增长的进程移动到一个内存中空闲区足够大的区域，要么把一个或多个进程交换出去，已变成生成一个大的空闲区。如果一个进程在内存中不能增长，而且磁盘上的交换区也满了，那么这个进程只有挂起一些空闲空间（或者可以结束该进程）上面只针对单个或者一小部分需要增长的进程采用的方式，如果大部分进程都要在运行时增长，为了减少因内存区域不够而引起的进程交换和移动所产生的开销，一种可用的方法是，在换入或移动进程时为它分配一些额外的内存。然而，当进程被换出到磁盘上时，应该只交换实际上使用的内存，将额外的内存交换也是一种浪费，下面是一种为两个进程分配了增长空间的内存配置。如果进程有两个可增长的段，例如，供变量动态分配和释放的作为堆(全局变量)使用的一个数据段(data segment)，以及存放局部变量与返回地址的一个堆栈段(stack segment)，就如图 b 所示。在图中可以看到所示进程的堆栈段在进程所占内存的顶端向下增长，紧接着在程序段后的数据段向上增长。当增长预留的内存区域不够了，处理方式就如上面的流程图(data segment 自动增长的三种处理方式)一样了。2.3空闲内存管理在进行内存动态分配时，操作系统必须对其进行管理。大致上说，有两种监控内存使用的方式位图(bitmap)空闲列表(free lists)下面我们就来探讨一下这两种使用方式使用位图的存储管理使用位图方法时，内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0 表示空闲， 1 表示占用（或者相反）。一块内存区域和其对应的位图如下图 a 表示一段有 5 个进程和 3 个空闲区的内存，刻度为内存分配单元，阴影区表示空闲（在位图中用 0 表示）；图 b 表示对应的位图；图 c 表示用链表表示同样的信息分配单元的大小是一个重要的设计因素，分配单位越小，位图越大。然而，即使只有 4 字节的分配单元，32 位的内存也仅仅只需要位图中的 1 位。32n 位的内存需要 n 位的位图，所以1 个位图只占用了 1/32 的内存。如果选择更大的内存单元，位图应该要更小。如果进程的大小不是分配单元的整数倍，那么在最后一个分配单元中会有大量的内存被浪费。位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况，因为位图的大小取决于内存和分配单元的大小。这种方法有一个问题是，当决定为把具有 k 个分配单元的进程放入内存时，内容管理器(memory manager) 必须搜索位图，在位图中找出能够运行 k 个连续 0 位的串。在位图中找出制定长度的连续 0 串是一个很耗时的操作，这是位图的缺点。（可以简单理解为在杂乱无章的数组中，找出具有一大长串空闲的数组单元）使用链表进行管理另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表，段会包含进程或者是两个进程的空闲区域。可用上面的图 c 来表示内存的使用情况。链表中的每一项都可以代表一个 空闲区(H) 或者是进程(P)的起始标志，长度和下一个链表项的位置。在这个例子中，段链表(segment list)是按照地址排序的。这种方式的优点是，当进程终止或被交换时，更新列表很简单。一个终止进程通常有两个邻居（除了内存的顶部和底部外）。相邻的可能是进程也可能是空闲区，它们有四种组合方式。当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存。我们先假设内存管理器知道应该分配多少内存，最简单的算法是使用 首次适配(first fit)。内存管理器会沿着段列表进行扫描，直到找个一个足够大的空闲区为止。除非空闲区大小和要分配的空间大小一样，否则将空闲区分为两部分，一部分供进程使用；一部分生成新的空闲区。首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。首次适配的一个小的变体是 下次适配(next fit)。它和首次匹配的工作方式相同，只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次匹配算法那样每次都会从头开始搜索。Bays(1997) 证明了下次算法的性能略低于首次匹配算法。另外一个著名的并且广泛使用的算法是 最佳适配(best fit)。最佳适配会从头到尾寻找整个链表，找出能够容纳进程的最小空闲区。最佳适配算法会试图找出最接近实际需要的空闲区，以最好的匹配请求和可用空闲区，而不是先一次拆分一个以后可能会用到的大的空闲区。比如现在我们需要一个大小为 2 的块，那么首次匹配算法会把这个块分配在位置 5 的空闲区，而最佳适配算法会把该块分配在位置为 18 的空闲区，如下那么最佳适配算法的性能如何呢？最佳适配会遍历整个链表，所以最佳适配算法的性能要比首次匹配算法差。但是令人想不到的是，最佳适配算法要比首次匹配和下次匹配算法浪费更多的内存，因为它会产生大量无用的小缓冲区，首次匹配算法生成的空闲区会更大一些。最佳适配的空闲区会分裂出很多非常小的缓冲区，为了避免这一问题，可以考虑使用 最差适配(worst fit) 算法。即总是分配最大的内存区域（所以你现在明白为什么最佳适配算法会分裂出很多小缓冲区了吧），使新分配的空闲区比较大从而可以继续使用。仿真程序表明最差适配算法也不是一个好主意。如果为进程和空闲区维护各自独立的链表，那么这四个算法的速度都能得到提高。这样，这四种算法的目标都是为了检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价是增加复杂度和减慢内存释放速度，因为必须将一个回收的段从进程链表中删除并插入空闲链表区。如果进程和空闲区使用不同的链表，那么可以按照大小对空闲区链表排序，以便提高最佳适配算法的速度。在使用最佳适配算法搜索由小到大排列的空闲区链表时，只要找到一个合适的空闲区，则这个空闲区就是能容纳这个作业的最小空闲区，因此是最佳匹配。因为空闲区链表以单链表形式组织，所以不需要进一步搜索。空闲区链表按大小排序时，首次适配算法与最佳适配算法一样快，而下次适配算法在这里毫无意义。另一种分配算法是 快速适配(quick fit) 算法，它为那些常用大小的空闲区维护单独的链表。例如，有一个 n 项的表，该表的第一项是指向大小为 4 KB 的空闲区链表表头指针，第二项是指向大小为 8 KB 的空闲区链表表头指针，第三项是指向大小为 12 KB 的空闲区链表表头指针，以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中，也可以放在一个专门存放大小比较特别的空闲区链表中。快速匹配算法寻找一个指定代销的空闲区也是十分快速的，但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点，即在一个进程终止或被换出时，寻找它的相邻块并查看是否可以合并的过程都是非常耗时的。如果不进行合并，内存将会很快分裂出大量进程无法利用的小空闲区。

爱喝奶茶的波波

操作系统入门-系统调用

五、系统调用我们已经可以看到操作系统提供了两种功能：为用户提供应用程序抽象和管理计算机资源。 对于大部分在应用程序和操作系统之间的交互主要是应用程序的抽象，例如创建、写入、读取和删除文件。 计算机的资源管理对用户来说基本上是透明的。 因此，用户程序和操作系统之间的接口主要是处理抽象。 为了真正理解操作系统的行为，我们必须仔细的分析这个接口。多数现代操作系统都有功能相同但是细节不同的系统调用，引发操作系统的调用依赖于计算机自身的机制，而且必须用汇编代码表达。 任何单 CPU 计算机一次执行执行一条指令。 如果一个进程在用户态下运行用户程序，例如从文件中读取数据。 那么如果想要把控制权交给操作系统控制，那么必须执行一个异常指令或者系统调用指令。 操作系统紧接着进行参数检查找出所需要的调用进程。 然后执行系统调用，把控制权移交给系统调用下面的指令。 大致来说，系统调用就像是执行了一个特殊的过程调用，但是只有系统调用能够进入内核态而过程调用则不能进入内核态。为了能够了解具体的调用过程，下面我们以 方法为例来看一下调用过程。 像上面提到的那样，会有三个参数，第一个参数是指定文件、第二个是指向缓冲区、第三个参数是给定需要读取的字节数。 就像几乎所有系统调用一样，它通过使用与系统调用相同的名称来调用一个函数库，从而从C程序中调用：read。readcount = read(fd,buffer,nbytes);系统调用在 count 中返回实际读出的字节数。 这个值通常与 nbytes 相同，但也可能更小。 比如在读过程中遇到了文件尾的情况。如果系统调用不能执行，不管是因为无效的参数还是磁盘错误，count 的值都会被置成 -1，然后在全局变量 中放入错误信号。 程序应该进场检查系统调用的结果以了解是否出错。errno系统调用是通过一系列的步骤实现的，为了更清楚的说明这个概念，我们还以 read 调用为例，在准备系统调用前，首先会把参数压入堆栈，如下所示C 和 C++ 编译器使用逆序（必须把第一个参数赋值给 printf(格式字符串)，放在堆栈的顶部）。 第一个参数和第三个参数都是值调用，但是第二个参数通过引用传递，即传递的是缓冲区的地址（由 & 指示），而不是缓冲的内容。 然后是 C 调用系统库的 read 函数，这也是第四步。在由汇编语言写成的库过程中，一般把系统调用的编号放在操作系统所期望的地方，如寄存器（第五步）。 然后执行一个 指令，将用户态切换到内核态，并在内核中的一个固定地址开始执行第六步。 TRAP 指令实际上与过程调用指令非常相似，它们后面都跟随一个来自远处位置的指令，以及供以后使用的一个保存在栈中的返回地址。TRAPTRAP 指令与过程调用指令存在两个方面的不同TRAP 指令会改变操作系统的状态，由用户态切换到内核态，而过程调用不改变模式其次，TRAP 指令不能跳转到任意地址上。 根据机器的体系结构，要么跳转到一个单固定地址上，或者指令中有一 8 位长的字段，它给定了内存中一张表格的索引，这张表格中含有跳转地址，然后跳转到指定地址上。跟随在 TRAP 指令后的内核代码开始检查系统调用编号，然后给正确的系统调用处理器，这通常是通过一张由系统调用编号所引用的、指向系统调用处理器的指针表来完成第七步。 此时，系统调用处理器运行第八步，一旦系统调用处理器完成工作，控制权会根据 TRAP 指令后面的指令中返回给函数调用库第九步。 这个过程接着以通常的过程调用返回的方式，返回到客户应用程序，这是第十步。 然后调用完成后，操作系统还必须清除用户堆栈，然后增加，用来清除调用 read 之前压入的参数。 从而完成整个 read 调用过程。dispatch堆栈指针(increment stackpointer)在上面的第九步中我们说道，控制可能返回 TRAP 指令后面的指令，把控制权再移交给调用者这个过程中，系统调用会发生阻塞，从而避免应用程序继续执行。 这么做是有原因的。 例如，如果试图读键盘，此时并没有任何输入，那么调用者就必须被阻塞。 在这种情形下，操作系统会检查是否有其他可以运行的进程。 这样，当有用户输入 时候，进程会提醒操作系统，然后返回第 9 步继续运行。下面，我们会列出一些常用的 系统调用，POSIX 系统调用大概有 100 多个，它们之中最重要的一些调用见下表POSIX进程管理文件管理目录和文件系统管理其他上面的系统调用参数中有一些公共部分，例如 pid 系统进程 id，fd 是文件描述符，n 是字节数，position 是在文件中的偏移量、seconds 是流逝时间。从宏观角度上看，这些系统调所提供的服务确定了多数操作系统应该具有的功能，下面分别来对不同的系统调用进行解释5.1用于进程管理的系统调用在 UNIX 中， 是唯一可以在 POSIX 中创建进程的途径，它创建一个原有进程的副本，包括所有的文件描述符、寄存器等内容。 在 fork 之后，原有进程以及副本（父与子）就分开了。 在 fork 过程中，所有的变量都有相同的值，虽然父进程的数据通过复制给子进程，但是后续对其中任何一个进程的修改不会影响到另外一个。 fork 调用会返回一个值，在子进程中该值为 0 ，并且在父进程中等于子进程的 。 使用返回的 PID，就可以看出来哪个是父进程和子进程。fork进程标识符(Process IDentified,PID)在多数情况下， 在 fork 之后，子进程需要执行和父进程不一样的代码。 从终端读取命令，创建一个子进程，等待子进程执行命令，当子进程结束后再读取下一个输入的指令。 为了等待子进程完成，父进程需要执行 系统调用，父进程会等待直至子进程终止（若有多个子进程的话，则直至任何一个子进程终止）。 waitpid 可以等待一个特定的子进程，或者通过将第一个参数设为 -1 的方式，等待任何一个比较老的子进程。 当 waitpid 完成后，会将第二个参数 所指向的地址设置为子进程的退出状态（正常或异常终止以及退出值）。 有各种可使用的选项，它们由第三个参数确定。 例如，如果没有已经退出的子进程则立刻返回。waitpidstatloc那么 shell 该如何使用 fork 呢？ 在键入一条命令后，shell 会调用 fork 命令创建一个新的进程。 这个子进程会执行用户的指令。 通过使用 系统调用可以实现系统执行，这个系统调用会引起整个核心映像被一个文件所替代，该文件由第一个参数给定。 下面是一个简化版的例子说明 fork、waitpid 和 execve 的使用execve#define TRUE 1 /* 一直循环下去 */ while(TRUE){ /* 在屏幕上显示提示符 */ type_prompt(); /* 从终端读取输入 */ read_command(command,parameters) /* fork 子进程 */ if(fork() != 0){ /* 父代码 */ /* 等待子进程执行完毕 */ waitpid(-1, &status, 0); }else{ /* 执行命令 */ /* 子代码 */ execve(command,parameters,0) } }一般情况下，execve 有三个参数：将要执行的文件名称，一个指向变量数组的指针，以及一个指向环境数组的指针。 这里对这些参数做一个简要的说明。先看一个 shell 指令cp file1 file2此命令把 file1 复制到 file2 文件中，在 shell 执行 fork 之后，子进程定位并执行文件拷贝，并将源文件和目标文件的名称传递给它。cp 的主程序（以及包含其他大多数 C 程序的主程序）包含声明main(argc,argv,envp)其中 argc 是命令行中参数数目的计数，包括程序名称。 对于上面的例子， 是3。 第二个参数 是数组的指针。 该数组的元素 i 是指向该命令行第 i 个字符串的指针。 在上面的例子中，argv[0] 指向字符串 cp，argv[1] 指向字符串 file1，argv[2] 指向字符串 file2。 main 的第三个参数是指向环境的指针，该环境是一个数组，含有 的赋值形式，用以将诸如终端类型以及根目录等信息传送给程序。 这些变量通常用来确定用户希望如何完成特定的任务（例如，使用默认打印机）。 在上面的例子中，没有环境参数传递给 execve ，所以环境变量是 0 ，所以 execve 的第三个参数为 0 。argcargvname = value可能你觉得 execve 过于复杂，这时候我要鼓励一下你，execve 可能是 POSIX 的全部系统调用中最复杂的一个了，其他都比较简单。 作为一个简单的例子，我们再来看一下 ，这是进程在执行完成后应执行的系统调用。 这个系统调用有一个参数，它的退出状态是 0 - 255 之间，它通过 waitpid 系统调用中的 statloc 返回给父级。exitUNIX 中的进程将内存划分成三个部分：，例如程序代码，，例如变量，，栈区域。 数据向上增长而堆栈向下增长，如下图所示text segment,文本区data segment，数据区stack segment上图能说明三个部分的内存分配情况，夹在中间的是空闲区，也就是未分配的区域，堆栈在需要时自动的挤压空闲区域，不过数据段的扩展是显示地通过系统调用 进行的，在数据段扩充后，该系统调用指向一个新地址。 但是，这个调用不是 POSIX 标准中定义的，对于存储器的动态分配，鼓励程序员使用 函数，而 malloc 的内部实现则不是一个适合标准化的主题，因为几乎没有程序员直接使用它。brkmalloc5.2用于文件管理的系统调用许多系统调用都与文件系统有关，要读写一个文件，必须先将其打开。 这个系统调用通过绝对路径名或指向工作目录的相对路径名指定要打开文件的名称，而代码 、 或 的含义分别是只读、只写或者两者都可以，为了创建一个新文件，使用 参数。 然后可使用返回的文件描述符进行读写操作。 接着，可以使用 close 关闭文件，这个调用使得文件描述符在后续的 open 中被再次使用。O_RDONLYO_WRONLYO_RDWRO_CREATE最常用的调用还是 和 ，我们再前面探讨过 read 调用，write 具有与 read 相同的参数。readwrite尽管多数程序频繁的读写文件，但是仍有一些应用程序需要能够随机访问一个文件的任意部分。 与每个文件相关的是一个指向文件当前位置的指针。 在顺序读写时，该指针通常指向要读出（写入）的下一个字节。 调用可以改变该位置指针的值，这样后续的 read 或 write 调用就可以在文件的任何地方开始。IseekIseek 有三个参数，，第一个是文件描述符，第二个是文件位置，第三个是说明该文件位置是相对于文件起始位置，当前位置还是文件的结尾。 在修改了指针之后，Iseek 所返回的值是文件中的绝对位置。position = iseek(fd,offset,whence)UNIX 为每个文件保存了该文件的类型（普通文件、特殊文件、目录等）、大小，最后修改时间以及其他信息，程序可以通过 系统调用查看这些信息。 ，第一个参数指定了被检查的文件； 第二个参数是一个指针，该指针指向存放这些信息的结构。 对于一个打开的文件而言，fstat 调用完成同样的工作。stats = stat(name,&buf)5.3用于目录管理的系统调用下面我们探讨目录和整个文件系统的系统调用，上面探讨的是和某个文件有关的系统调用。 和 分别用于创建 和删除 空目录，下一个调用是 它的作用是允许同一个文件以两个或者多个名称出现，多数情况下是在不同的目录中使用 link ，下面我们探讨一下 link 是如何工作的mkdirrmdirs = mkdir(nname,mode)s = rmdir(name)s = link(name1,name2)图中有两个用户 和 ，每个用户都有他自己的一个目录和一些文件，如果 ast 要执行一个包含下面系统调用的应用程序astjimlink("/usr/jim/memo", "/usr/ast/note");jim 中的 memo 文件现在会进入到 ast 的目录中，在 note 名称下。 此后，和 会有相同的名称。/usr/jim/memo/usr/ast/note用户目录是保存在 /usr，/user，/home 还是其他位置，都是由本地系统管理员决定的。要理解 link 是如何工作的需要清楚 link 做了什么操作。 UNIX 中的每个文件都有一个独一无二的版本，也称作 ，它标示着不同文件的版本。 这个 i - 编号是 表的索引。 每个文件都会表明谁拥有这个文件，这个磁盘块的位置在哪，等等。 目录只是一个包含一组（i编号，ASCII名称）对应的文件。 UNIX 中的第一个版本中，每个目录项都会有 16 个字节，2 个字节对应 i - 编号和 14 个字节对应其名称。 现在需要一个更复杂的结构需要支持长文件名，但是从概念上讲一个目录仍是一系列（i-编号，ASCII 名称）的集合。 在上图中， 的 i-编号为 16，依此类推。 link 只是利用某个已有文件的 i-编号，创建一个新目录项（也许用一个新名称）。 在上图 b 中，你会发现有两个相同的 70 i-编号的文件，因此它们需要有相同的文件。 如果其中一个使用了 系统调用的话，其中一个会被移除，另一个将保留。 如果两个文件都移除了，则 UNIX 会发现该文件不存在任何没有目录项（i-节点中的一个域记录着指向该文件的目录项），就会把该文件从磁盘中移除。i - number，i-编号i-nodes,i-节点mailunlink就像我们上面提到过的那样， 系统 调用会将两个文件系统合并为一个。 通常的情况是将根文件系统分布在硬盘（子）分区上，并将用户文件分布在另一个（子）分区上，该根文件系统包含常用命令的二进制（可执行）版本和其他使用频繁的文件。 然后，用户就会插入可读取的 USB 硬盘。mounts = mount(special,name,flag)通过执行 mount 系统调用，USB 文件系统可以被添加到根文件系统中，如果用 C 语言来执行那就是mount("/dev/sdb0","/mnt",0)这里，第一个参数是 USB 驱动器 0 的块特殊文件名称，第二个参数是被安装在树中的位置，第三个参数说明将要安装的文件系统是可读写的还是只读的。当不再需要一个文件系统时，可以使用 umount 移除之。5.4其他系统调用除了进程、文件、目录系统调用，也存在其他系统调用的情况，下面我们来探讨一下。 我们可以看到上面其他系统调用只有四种，首先来看第一个 chdir，chdir 调用更改当前工作目录，在调用chdir("/usr/ast/test");后，打开 xyz 文件，会打开 文件，工作目录的概念消除了总是需要输入长文件名的需要。/usr/ast/test/xyz在 UNIX 系统中，每个文件都会有保护模式，这个模式会有一个位，它用来区分所有者、组和其他成员。 系统调用提供改变文件模式的操作。 例如，要使一个文件除了对所有者之外的用户可读，你可以执行读-写-执行chmodchmod("file",0644); kill 系统调用是用户和用户进程发送信号的方式，如果一个进程准备好捕捉一个特定的信号，那么在信号捕捉之前，会运行一个信号处理程序。 如果进程没有准备好捕捉特定的信号，那么信号的到来会杀掉该进程（此名字的由来）。POSIX 定义了若干时间处理的进程。 例如， 以秒为单位返回当前时间，0 对应着 1970 年 1月 1日。 在一台 32 位字的计算机中，time 的最大值是 (2^32) - 1秒，这个数字对应 136 年多一点。 所以在 2106 年，32 位的 UNIX 系统会发飙。 如果读者现在有 32 位 UNIX 系统，建议在 2106 年更换位 64 位操作系统（偷笑～）。timeWin 32 API上面我们提到的都是 UNIX 系统调用，现在我们来聊聊 Win 32 中的系统调用。 Windows 和 UNIX 在各自的编程方式上有着根本的不同。 UNIX 程序由执行某些操作或执行其他操作的代码组成，进行系统调用以执行某些服务。 Windows 系统则不同，Windows 应用程序通常是由事件驱动的。 主程序会等待一些事件发生，然后调用程序去处理。 最简单的事件处理是键盘敲击和鼠标滑过，或者是鼠标点击，或者是插入 USB 驱动，然后操作系统调用处理器去处理事件，更新屏幕和更新程序内部状态。 这是与 UNIX 不同的设计风格。当然，Windows 也有系统调用。 在 UNIX 中，系统调用（比如 read）和系统调用所使用的调用库（例如 read）几乎是一对一的关系。 而在 Windows 中，情况则大不相同。 首先，函数库的调用和实际的系统调用几乎是不对应的。 微软定义了一系列过程，称为 ，程序员通过这套标准的接口来实现系统调用。 这个接口支持从 Windows 95 版本以来所有的 Windows 版本。Win32应用编程接口(Application Programming Interface)Win32 API 调用的数量是非常巨大的，有数千个多。 但这些调用并不都是在内核态的模式下运行时，有一些是在用户态的模型下运行。 Win32 API 有大量的调用，用来管理视窗、几何图形、文本、字体、滚动条、对话框、菜单以及 GUI 的其他功能。 为了使图形子系统在内核态下运行，需要系统调用，否则就只有函数库调用。我们把关注点放在和 Win32 系统调用中来，我们可以简单看一下 Win32 API 中的系统调用和 UNIX 中有什么不同（并不是所有的系统调用）上表中是 UNIX 调用大致对应的 Win32 API 系统调用，简述一下上表。 用于创建一个新进程，它把 UNIX 中的 fork 和 execve 两个指令合成一个，一起执行。 它有许多参数用来指定新创建进程的性质。 Windows 中没有类似 UNIX 中的进程层次，所以不存在父进程和子进程的概念。 在进程创建之后，创建者和被创建者是平等的。 用于等待一个事件，等待的事件可以是多种可能的事件。 如果有参数指定了某个进程，那么调用者将等待指定的进程退出，这通过 来完成。CreateProcessWaitForSingleObjectExitProcess然后是6个文件操作，在功能上和 UNIX 的调用类似，然而在参数和细节上是不同的。 和 UNIX 中一样，文件可以打开，读取，写入，关闭。 和 设置文件的位置并取得文件的属性。SetFilePointerGetFileAttributesExWindows 中有目录，目录分别用 以及 API 调用创建和删除。 也有对当前的目录的标记，这可以通过 来设置。 使用 可获得当前时间。CreateDirectoryRemoveDirectorySetCurrentDirectoryGetLocalTimeWin32 接口中没有文件的链接、文件系统的 mount、umount 和 stat ，当然， Win32 中也有大量 UNIX 中没有的系统调用，特别是对 GUI 的管理和调用。