首先你要搞明白你学习操作系统的目的是什么？操作系统的重要性如何？学习操作系统会给我带来什么？下面我会从这几个方面为你回答下。
操作系统也是一种软件，但是操作系统是一种非常复杂的软件。操作系统提供了几种抽象模型
学习操作系统我们能够有效的解决并发问题，并发几乎是互联网的重中之重了，这也从侧面说明了学习操作系统的重要性。
学习操作系统的重点不是让你从头制造一个操作系统，而是告诉你操作系统是如何工作的，能够让你对计算机底层有所了解，打实你的基础。
相信你一定清楚什么是编程
Datastructures+Algorithms=Programming
操作系统内部会涉及到众多的数据结构和算法描述，能够让你了解算法的基础上，让你编写更优秀的程序。
我认为可以把计算机比作一栋楼
计算机的底层相当于就是楼的根基，计算机应用相当于就是楼的外形，而操作系统就相当于是告诉你大楼的构造原理，编写高质量的软件就相当于是告诉你构建一个稳定的房子。
在了解操作系统前，你需要先知道一下什么是计算机系统：现代计算机系统由一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成的系统。这些都属于硬件的范畴。我们程序员不会直接和这些硬件打交道，并且每位程序员不可能会掌握所有计算机系统的细节。
所以计算机科学家在硬件的基础之上，安装了一层软件，这层软件能够根据用户输入的指令达到控制硬件的效果，从而满足用户的需求，这样的软件称为操作系统，它的任务就是为用户程序提供一个更好、更简单、更清晰的计算机模型。也就是说，操作系统相当于是一个中间层，为用户层和硬件提供各自的借口，屏蔽了不同应用和硬件之间的差异，达到统一标准的作用。
上面一个操作系统的简化图，最底层是硬件，硬件包括芯片、电路板、磁盘、键盘、显示器等我们上面提到的设备，在硬件之上是软件。大部分计算机有两种运行模式：内核态和用户态，软件中最基础的部分是操作系统，它运行在内核态中。操作系统具有硬件的访问权，可以执行机器能够运行的任何指令。软件的其余部分运行在用户态下。
在大概了解到操作系统之后，我们先来认识一下硬件都有哪些
计算机硬件是计算机的重要组成部分，其中包含了5个重要的组成部分：运算器、控制器、存储器、输入设备、输出设备。
运算器和控制器共同组成了CPU
这五部分也是冯诺伊曼的体系结构，它认为计算机必须具有如下功能：
把需要的程序和数据送至计算机中。必须具有长期记忆程序、数据、中间结果及最终运算结果的能力。能够完成各种算术、逻辑运算和数据传送等数据加工处理的能力。能够根据需要控制程序走向，并能根据指令控制机器的各部件协调操作。能够按照要求将处理结果输出给用户。
下面是一张intel家族产品图，是一个详细的计算机硬件分类，我们在根据图中涉及到硬件进行介绍
下面是CPU可能执行简单操作的几个步骤
算术逻辑单元（ALU）是对数字二进制数执行算术和按位运算的组合数字电子电路。
关于进程和线程，你需要理解下面这张脑图中的重点
操作系统中最核心的概念就是进程，进程是对正在运行中的程序的一个抽象。操作系统的其他所有内容都是围绕着进程展开的。
一个进程就是一个正在执行的程序的实例，进程也包括程序计数器、寄存器和变量的当前值。从概念上来说，每个进程都有各自的虚拟CPU，但是实际情况是CPU会在各个进程之间进行来回切换。
如上图所示，这是一个具有4个程序的多道处理程序，在进程不断切换的过程中，程序计数器也在不同的变化。
在上图中，这4道程序被抽象为4个拥有各自控制流程（即每个自己的程序计数器）的进程，并且每个程序都独立的运行。当然，实际上只有一个物理程序计数器，每个程序要运行时，其逻辑程序计数器会装载到物理程序计数器中。当程序运行结束后，其物理程序计数器就会是真正的程序计数器，然后再把它放回进程的逻辑计数器中。
因此，当我们说一个CPU只能真正一次运行一个进程的时候，即使有2个核（或CPU），每一个核也只能一次运行一个线程。
这里的关键思想是认识到一个进程所需的条件，进程是某一类特定活动的总和，它有程序、输入输出以及状态。
操作系统需要一些方式来创建进程。下面是一些创建进程的方式
从技术上讲，在所有这些情况下，让现有流程执行流程是通过创建系统调用来创建新流程的。该进程可能是正在运行的用户进程，是从键盘或鼠标调用的系统进程或批处理程序。这些就是系统调用创建新进程的过程。该系统调用告诉操作系统创建一个新进程，并直接或间接指示在其中运行哪个程序。
在Windows中，情况正相反，一个简单的Win32功能调用CreateProcess，会处理流程创建并将正确的程序加载到新的进程中。这个调用会有10个参数，包括了需要执行的程序、输入给程序的命令行参数、各种安全属性、有关打开的文件是否继承控制位、优先级信息、进程所需要创建的窗口规格以及指向一个结构的指针，在该结构中新创建进程的信息被返回给调用者。在Windows中，从一开始父进程的地址空间和子进程的地址空间就是不同的。
进程在创建之后，它就开始运行并做完成任务。然而，没有什么事儿是永不停歇的，包括进程也一样。进程早晚会发生终止，但是通常是由于以下情况触发的
在一些系统中，当一个进程创建了其他进程后，父进程和子进程就会以某种方式进行关联。子进程它自己就会创建更多进程，从而形成一个进程层次结构。
相反，Windows中没有进程层次的概念，Windows中所有进程都是平等的，唯一类似于层次结构的是在创建进程的时候，父进程得到一个特别的令牌（称为句柄），该句柄可以用来控制子进程。然而，这个令牌可能也会移交给别的操作系统，这样就不存在层次结构了。而在UNIX中，进程不能剥夺其子进程的进程权。（这样看来，还是Windows比较渣）。
尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态，但是，进程之间仍然需要相互帮助。当一个进程开始运行时，它可能会经历下面这几种状态
图中会涉及三种状态
操作系统为了执行进程间的切换，会维护着一张表，这张表就是进程表(processtable)。每个进程占用一个进程表项。该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时所必须保存的信息。
下面展示了一个典型系统中的关键字段
第一列内容与进程管理有关，第二列内容与存储管理有关，第三列内容与文件管理有关。
当中断结束后，操作系统会调用一个C程序来处理中断剩下的工作。在完成剩下的工作后，会使某些进程就绪，接着调用调度程序，决定随后运行哪个进程。然后将控制权转移给一段汇编语言代码，为当前的进程装入寄存器值以及内存映射并启动该进程运行，下面显示了中断处理和调度的过程。
一个进程在执行过程中可能被中断数千次，但关键每次中断后，被中断的进程都返回到与中断发生前完全相同的状态。
在传统的操作系统中，每个进程都有一个地址空间和一个控制线程。事实上，这是大部分进程的定义。不过，在许多情况下，经常存在同一地址空间中运行多个控制线程的情形，这些线程就像是分离的进程。下面我们就着重探讨一下什么是线程
或许这个疑问也是你的疑问，为什么要在进程的基础上再创建一个线程的概念，准确的说，这其实是进程模型和线程模型的讨论，回答这个问题，可能需要分三步来回答
进程中拥有一个执行的线程，通常简写为线程(thread)。线程会有程序计数器，用来记录接着要执行哪一条指令；线程实际上CPU上调度执行的实体。
下图我们可以看到三个传统的进程，每个进程有自己的地址空间和单个控制线程。每个线程都在不同的地址空间中运行
下图中，我们可以看到有一个进程三个线程的情况。每个线程都在相同的地址空间中运行。
线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址，因此一个线程可以读取、写入甚至擦除另一个线程的堆栈。线程之间除了共享同一内存空间外，还具有如下不同的内容
上图左边的是同一个进程中每个线程共享的内容，上图右边是每个线程中的内容。也就是说左边的列表是进程的属性，右边的列表是线程的属性。
线程之间的状态转换和进程之间的状态转换是一样的。
每个线程都会有自己的堆栈，如下图所示
进程通常会从当前的某个单线程开始，然后这个线程通过调用一个库函数（比如thread_create）创建新的线程。线程创建的函数会要求指定新创建线程的名称。创建的线程通常都返回一个线程标识符，该标识符就是新线程的名字。
当一个线程完成工作后，可以通过调用一个函数（比如thread_exit）来退出。紧接着线程消失，状态变为终止，不能再进行调度。在某些线程的运行过程中，可以通过调用函数例如thread_join，表示一个线程可以等待另一个线程退出。这个过程阻塞调用线程直到等待特定的线程退出。在这种情况下，线程的创建和终止非常类似于进程的创建和终止。
另一个常见的线程是调用thread_yield，它允许线程自动放弃CPU从而让另一个线程运行。这样一个调用还是很重要的，因为不同于进程，线程是无法利用时钟中断强制让线程让出CPU的。
POSIX线程通常称为pthreads是一种独立于语言而存在的执行模型，以及并行执行模型。
POSIXThreads的实现在许多类似且符合POSIX的操作系统上可用，例如FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris，它在现有WindowsAPI之上实现了pthread。
IEEE是世界上最大的技术专业组织，致力于为人类的利益而发展技术。
所有的Pthreads都有特定的属性，每一个都含有标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性。这个属性包括堆栈大小、调度参数以及其他线程需要的项目。
主要有三种实现方式
下面我们分开讨论一下
第一种方法是把整个线程包放在用户空间中，内核对线程一无所知，它不知道线程的存在。所有的这类实现都有同样的通用结构
线程在运行时系统之上运行，运行时系统是管理线程过程的集合，包括前面提到的四个过程：pthread_create,pthread_exit,pthread_join和pthread_yield。
当某个线程希望创建一个新线程或撤销一个已有线程时，它会进行一个系统调用，这个系统调用通过对线程表的更新来完成线程创建或销毁工作。
内核中的线程表持有每个线程的寄存器、状态和其他信息。这些信息和用户空间中的线程信息相同，但是位置却被放在了内核中而不是用户空间中。另外，内核还维护了一张进程表用来跟踪系统状态。
结合用户空间和内核空间的优点，设计人员采用了一种内核级线程的方式，然后将用户级线程与某些或者全部内核线程多路复用起来
在这种模型中，编程人员可以自由控制用户线程和内核线程的数量，具有很大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。
进程是需要频繁的和其他进程进行交流的。下面我们会一起讨论有关进程间通信(InterProcessCommunication,IPC)的问题。大致来说，进程间的通信机制可以分为6种
下面我们分别对其进行概述
信号是UNIX系统最先开始使用的进程间通信机制，因为Linux是继承于UNIX的，所以Linux也支持信号机制，通过向一个或多个进程发送异步事件信号来实现，信号可以从键盘或者访问不存在的位置等地方产生；信号通过shell将任务发送给子进程。
你可以在Linux系统上输入kill-l来列出系统使用的信号，下面是我提供的一些信号
进程可以选择忽略发送过来的信号，但是有两个是不能忽略的：SIGSTOP和SIGKILL信号。SIGSTOP信号会通知当前正在运行的进程执行关闭操作，SIGKILL信号会通知当前进程应该被杀死。除此之外，进程可以选择它想要处理的信号，进程也可以选择阻止信号，如果不阻止，可以选择自行处理，也可以选择进行内核处理。如果选择交给内核进行处理，那么就执行默认处理。
操作系统会中断目标程序的进程来向其发送信号、在任何非原子指令中，执行都可以中断，如果进程已经注册了新号处理程序，那么就执行进程，如果没有注册，将采用默认处理的方式。
Linux系统中的进程可以通过建立管道pipe进行通信
在两个进程之间，可以建立一个通道，一个进程向这个通道里写入字节流，另一个进程从这个管道中读取字节流。管道是同步的，当进程尝试从空管道读取数据时，该进程会被阻塞，直到有可用数据为止。shell中的管线pipelines就是用管道实现的，当shell发现输出
sort 管道实际上就是|，两个应用程序不知道有管道的存在，一切都是由shell管理和控制的。 两个进程之间还可以通过共享内存进行进程间通信，其中两个或者多个进程可以访问公共内存空间。两个进程的共享工作是通过共享内存完成的，一个进程所作的修改可以对另一个进程可见(很像线程间的通信)。 在使用共享内存前，需要经过一系列的调用流程，流程如下 先入先出队列FIFO通常被称为命名管道(NamedPipes)，命名管道的工作方式与常规管道非常相似，但是确实有一些明显的区别。未命名的管道没有备份文件：操作系统负责维护内存中的缓冲区，用来将字节从写入器传输到读取器。一旦写入或者输出终止的话，缓冲区将被回收，传输的数据会丢失。相比之下，命名管道具有支持文件和独特API，命名管道在文件系统中作为设备的专用文件存在。当所有的进程通信完成后，命名管道将保留在文件系统中以备后用。命名管道具有严格的FIFO行为 写入的第一个字节是读取的第一个字节，写入的第二个字节是读取的第二个字节，依此类推。 一听到消息队列这个名词你可能不知道是什么意思，消息队列是用来描述内核寻址空间内的内部链接列表。可以按几种不同的方式将消息按顺序发送到队列并从队列中检索消息。每个消息队列由IPC标识符唯一标识。消息队列有两种模式，一种是严格模式，严格模式就像是FIFO先入先出队列似的，消息顺序发送，顺序读取。还有一种模式是非严格模式，消息的顺序性不是非常重要。 还有一种管理两个进程间通信的是使用socket，socket提供端到端的双相通信。一个套接字可以与一个或多个进程关联。就像管道有命令管道和未命名管道一样，套接字也有两种模式，套接字一般用于两个进程之间的网络通信，网络套接字需要来自诸如TCP（传输控制协议）或较低级别UDP（用户数据报协议）等基础协议的支持。 套接字有以下几种分类 毫无疑问，不同的环境下需要不同的调度算法。之所以出现这种情况，是因为不同的应用程序和不同的操作系统有不同的目标。也就是说，在不同的系统中，调度程序的优化也是不同的。这里有必要划分出三种环境 现在让我们把目光从一般性的调度转换为特定的调度算法。下面我们会探讨在批处理中的调度。 这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。 需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。 交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度 轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priorityscheduling) 它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。  可以看到，在三轮过后，T0在新的估计值中所占比重下降至1/8。 对用户进行承诺并在随后兑现承诺是一件好事，不过很难实现。但是存在着一种简单的方式，有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是彩票调度(lotteryscheduling)算法。 下面我们来了解一下内存管理，你需要知道的知识点如下 如果要使多个应用程序同时运行在内存中，必须要解决两个问题：保护和重定位。第一种解决方式是用保护密钥标记内存块，并将执行过程的密钥与提取的每个存储字的密钥进行比较。这种方式只能解决第一种问题（破坏操作系统），但是不能解决多进程在内存中同时运行的问题。 还有一种更好的方式是创造一个存储器抽象：地址空间(theaddressspace)。就像进程的概念创建了一种抽象的CPU来运行程序，地址空间也创建了一种抽象内存供程序使用。 最简单的办法是使用动态重定位(dynamicrelocation)技术，它就是通过一种简单的方式将每个进程的地址空间映射到物理内存的不同区域。还有一种方式是使用基址寄存器和变址寄存器。 每当进程引用内存以获取指令或读取、写入数据时，CPU都会自动将基址值添加到进程生成的地址中，然后再将其发送到内存总线上。同时，它检查程序提供的地址是否大于或等于变址寄存器中的值。如果程序提供的地址要超过变址寄存器的范围，那么会产生错误并中止访问。 在程序运行过程中，经常会出现内存不足的问题。 下面是一个交换过程 刚开始的时候，只有进程A在内存中，然后从创建进程B和进程C或者从磁盘中把它们换入内存，然后在图d中，A被换出内存到磁盘中，最后A重新进来。因为图g中的进程A现在到了不同的位置，所以在装载过程中需要被重新定位，或者在交换程序时通过软件来执行；或者在程序执行期间通过硬件来重定位。基址寄存器和变址寄存器就适用于这种情况。 在进行内存动态分配时，操作系统必须对其进行管理。大致上说，有两种监控内存使用的方式 使用位图方法时，内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）。一块内存区域和其对应的位图如下 位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况，因为位图的大小取决于内存和分配单元的大小。这种方法有一个问题是，当决定为把具有k个分配单元的进程放入内存时，内容管理器(memorymanager)必须搜索位图，在位图中找出能够运行k个连续0位的串。在位图中找出制定长度的连续0串是一个很耗时的操作，这是位图的缺点。（可以简单理解为在杂乱无章的数组中，找出具有一大长串空闲的数组单元） 另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表，段会包含进程或者是两个进程的空闲区域。可用上面的图c来表示内存的使用情况。链表中的每一项都可以代表一个空闲区(H)或者是进程(P)的起始标志，长度和下一个链表项的位置。 当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存。我们先假设内存管理器知道应该分配多少内存，最简单的算法是使用首次适配(firstfit)。内存管理器会沿着段列表进行扫描，直到找个一个足够大的空闲区为止。除非空闲区大小和要分配的空间大小一样，否则将空闲区分为两部分，一部分供进程使用；一部分生成新的空闲区。首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。 首次适配的一个小的变体是下次适配(nextfit)。它和首次匹配的工作方式相同，只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次匹配算法那样每次都会从头开始搜索。 另外一个著名的并且广泛使用的算法是最佳适配(bestfit)。最佳适配会从头到尾寻找整个链表，找出能够容纳进程的最小空闲区。 尽管基址寄存器和变址寄存器用来创建地址空间的抽象，但是这有一个其他的问题需要解决：管理软件的不断增大(managingbloatware)。虚拟内存的基本思想是，每个程序都有自己的地址空间，这个地址空间被划分为多个称为页面(page)的块。每一页都是连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，硬件会立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。 大部分使用虚拟内存的系统中都会使用一种分页(paging)技术。在任何一台计算机上，程序会引用使用一组内存地址。当程序执行 MOVREG,1000这条指令时，它会把内存地址为1000的内存单元的内容复制到REG中（或者相反，这取决于计算机）。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。 这些程序生成的地址被称为虚拟地址(virtualaddresses)并形成虚拟地址空间(virtualaddressspace)，在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存中线上，读写操作都使用同样地址的物理内存。在使用虚拟内存时，虚拟地址不会直接发送到内存总线上。相反，会使用MMU(MemoryManagementUnit)内存管理单元把虚拟地址映射为物理内存地址，像下图这样 下面这幅图展示了这种映射是如何工作的 页表给出虚拟地址与物理内存地址之间的映射关系。每一页起始于4096的倍数位置，结束于4095的位置，所以4K到8K实际为4096-8191，8K-12K就是8192-12287 在这个例子中，我们可能有一个16位地址的计算机，地址从0-64K-1，这些是虚拟地址。然而只有32KB的物理地址。所以虽然可以编写64KB的程序，但是程序无法全部调入内存运行，在磁盘上必须有一个最多64KB的程序核心映像的完整副本，以保证程序片段在需要时被调入内存。 虚拟页号可作为页表的索引用来找到虚拟页中的内容。由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成物理地址。 因此，页表的目的是把虚拟页映射到页框中。从数学上说，页表是一个函数，它的参数是虚拟页号，结果是物理页框号。 通过这个函数可以把虚拟地址中的虚拟页转换为页框，从而形成物理地址。 下面我们探讨一下页表项的具体结构，上面你知道了页表项的大致构成，是由页框号和在/不在位构成的，现在我们来具体探讨一下页表项的构成 保护位(Protection)告诉我们哪一种访问是允许的，啥意思呢？最简单的表示形式是这个域只有一位，0表示可读可写，1表示的是只读。 修改位(Modified)和访问位(Referenced)会跟踪页面的使用情况。当一个页面被写入时，硬件会自动的设置修改位。修改位在页面重新分配页框时很有用。如果一个页面已经被修改过（即它是脏的），则必须把它写回磁盘。如果一个页面没有被修改过（即它是干净的），那么重新分配时这个页框会被直接丢弃，因为磁盘上的副本仍然是有效的。这个位有时也叫做脏位(dirtybit)，因为它反映了页面的状态。 访问位(Referenced)在页面被访问时被设置，不管是读还是写。这个值能够帮助操作系统在发生缺页中断时选择要淘汰的页。不再使用的页要比正在使用的页更适合被淘汰。这个位在后面要讨论的页面置换算法中作用很大。 最后一位用于禁止该页面被高速缓存，这个功能对于映射到设备寄存器还是内存中起到了关键作用。通过这一位可以禁用高速缓存。具有独立的I/O空间而不是用内存映射I/O的机器来说，并不需要这一位。 下面我们就来探讨一下有哪些页面置换算法。 最优的页面置换算法的工作流程如下：在缺页中断发生时，这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到10、100或者1000条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。 最优化的页面算法表明应该标记最大的页面。如果一个页面在800万条指令内不会被使用，另外一个页面在600万条指令内不会被使用，则置换前一个页面，从而把需要调入这个页面而发生的缺页中断推迟。计算机也像人类一样，会把不愿意做的事情尽可能的往后拖。 这个算法最大的问题时无法实现。当缺页中断发生时，操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用。 为了能够让操作系统收集页面使用信息，大部分使用虚拟地址的计算机都有两个状态位，R和M，来和每个页面进行关联。每当引用页面（读入或写入）时都设置R，写入（即修改）页面时设置M，这些位包含在每个页表项中，就像下面所示 因为每次访问时都会更新这些位，因此由硬件来设置它们非常重要。一旦某个位被设置为1，就会一直保持1直到操作系统下次来修改此位。 如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。当启动一个进程时，将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作系统就可以设置R位(在它的内部表中)，修改页表项使其指向正确的页面，并设置为READONLY模式，然后重新启动引起缺页中断的指令。如果页面随后被修改，就会发生另一个缺页异常。从而允许操作系统设置M位并把页面的模式设置为READ/WRITE。 可以用R位和M位来构造一个简单的页面置换算法：当启动一个进程时，操作系统将其所有页面的两个位都设置为0。R位定期的被清零（在每个时钟中断）。用来将最近未引用的页面和已引用的页面分开。 当出现缺页中断后，操作系统会检查所有的页面，并根据它们的R位和M位将当前值分为四类： 尽管看起来好像无法实现第一类页面，但是当第三类页面的R位被时钟中断清除时，它们就会发生。时钟中断不会清除M位，因为需要这个信息才能知道是否写回磁盘中。清除R但不清除M会导致出现一类页面。 NRU(NotRecentlyUsed)算法从编号最小的非空类中随机删除一个页面。此算法隐含的思想是，在一个时钟内（约20ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，NRU的主要优点是易于理解并且能够有效的实现。 另一种开销较小的方式是使用FIFO(First-In,First-Out)算法，这种类型的数据结构也适用在页面置换算法中。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。 a）按照先进先出的方法排列的页面；b）在时刻20处发生缺页异常中断并且A的R位已经设置时的页面链表。 寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过，该算法就会被简化为单纯的FIFO算法。具体来说，假设图a中所有页面都设置了R位。操作系统将页面依次移到链表末尾，每次都在添加到末尾时清除R位。最后，算法又会回到页面A，此时的R位已经被清除，那么页面A就会被执行出链处理，因此算法能够正常结束。 一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。如下图所示 当缺页错误出现时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入到这个位置，然后把表针向前移动一位；如果R位是1就清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面位置。了解这个算法的工作方式，就明白为什么它被称为时钟(clokc)算法了。 虽然LRU在理论上是可以实现的，但是从长远看来代价比较高。为了完全实现LRU，会在内存中维护一个所有页面的链表，最频繁使用的页位于表头，最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常耗时的操作，即使使用硬件来实现也是一样的费时。 尽管上面的LRU算法在原则上是可以实现的，但是很少有机器能够拥有那些特殊的硬件。上面是硬件的实现方式，那么现在考虑要用软件来实现LRU。一种可以实现的方案是NFU(NotFrequentlyUsed，最不常用)算法。它需要一个软件计数器来和每个页面关联，初始化的时候是0。在每个时钟中断时，操作系统会浏览内存中的所有页，会将每个页面的R位（0或1）加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时，则置换计数器值最小的页面。 只需要对NFU做一个简单的修改就可以让它模拟LRU，这个修改有两个步骤 修改以后的算法称为老化(aging)算法，下图解释了老化算法是如何工作的。 CPU正在以某个频率前进，该频率的周期称为时钟滴答或时钟周期。一个100Mhz的处理器每秒将接收100,000,000个时钟滴答。 当缺页异常出现时，将置换（就是移除）计数器值最小的页面。如果一个页面在前面4个时钟周期内都没有被访问过，那么它的计数器应该会有四个连续的0，因此它的值肯定要比前面3个时钟周期内都没有被访问过的页面的计数器小。 这个算法与LRU算法有两个重要的区别：看一下上图中的e，第三列和第五列 与时钟算法一样，所需的数据结构是一个以页框为元素的循环列表，就像下面这样 工作集时钟页面置换算法的操作：a)和b)给出R=1时所发生的情形；c)和d)给出R=0的例子 与时钟算法一样，在每个缺页异常时，首先检查指针指向的页面。如果R位被是设置为1，该页面在当前时钟周期内就被使用过，那么该页面就不适合被淘汰。然后把该页面的R位置为0，指针指向下一个页面，并重复该算法。该事件序列化后的状态参见图b。 现在考虑指针指向的页面R=0时会发生什么，参见图c，如果页面的使用期限大于t并且页面为被访问过，那么这个页面就不会在工作集中，并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面，并把新的页面放在其中，如图d所示。另一方面，如果页面被修改过，就不能重新申请页面，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个老的，没有被修改过的页面可以立即使用。 原则上来说，所有的页面都有可能因为磁盘I/O在某个时钟周期内被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回n个页面。一旦达到该限制，就不允许调度新的写操作。 那么就有个问题，指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？这里有两种情况： 在第一种情况中，指针仅仅是不停的移动，寻找一个未被修改过的页面。由于已经调度了一个或者多个写操作，最终会有某个写操作完成，它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能会把写操作重排序。 对于第二种情况，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，最简单的方法就是置换一个未被修改的页面来使用，扫描中需要记录未被修改的页面的位置，如果不存在未被修改的页面，就选定当前页面并把它写回磁盘。 我们到现在已经研究了各种页面置换算法，现在我们来一个简单的总结，算法的总结归纳如下 总之，最好的算法是老化算法和WSClock算法。他们分别是基于LRU和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。 下面来聊一聊文件系统，你需要知道下面这些知识点 文件是一种抽象机制，它提供了一种方式用来存储信息以及在后面进行读取。可能任何一种机制最重要的特性就是管理对象的命名方式。在创建一个文件后，它会给文件一个命名。当进程终止时，文件会继续存在，并且其他进程可以使用名称访问该文件。 文件命名规则对于不同的操作系统来说是不一样的，但是所有现代操作系统都允许使用1-8个字母的字符串作为合法文件名。 某些文件区分大小写字母，而大多数则不区分。UNIX属于第一类；历史悠久的MS-DOS属于第二类（顺便说一句，尽管MS-DOS历史悠久，但MS-DOS仍在嵌入式系统中非常广泛地使用，因此它绝不是过时的）；因此，UNIX系统会有三种不同的命名文件：maria、Maria、MARIA。在MS-DOS，所有这些命名都属于相同的文件。 许多操作系统支持两部分的文件名，它们之间用.分隔开，比如文件名prog.c。原点后面的文件称为文件扩展名(fileextension)，文件扩展名通常表示文件的一些信息。一些常用的文件扩展名以及含义如下图所示 在UNIX系统中，文件扩展名只是一种约定，操作系统并不强制采用。 文件的构造有多种方式。下图列出了常用的三种构造方式 三种不同的文件。a)字节序列。b)记录序列。c)树 上图中的a是一种无结构的字节序列，操作系统不关心序列的内容是什么，操作系统能看到的就是字节(bytes)。其文件内容的任何含义只在用户程序中进行解释。UNIX和Windows都采用这种办法。 图b表示在文件结构上的第一部改进。在这个模型中，文件是具有固定长度记录的序列，每个记录都有其内部结构。把文件作为记录序列的核心思想是：读操作返回一个记录，而写操作重写或者追加一个记录。第三种文件结构如上图c所示。在这种组织结构中，文件由一颗记录树构成，记录树的长度不一定相同，每个记录树都在记录中的固定位置包含一个key字段。这棵树按key进行排序，从而可以对特定的key进行快速查找。 很多操作系统支持多种文件类型。例如，UNIX（同样包括OSX）和Windows都具有常规的文件和目录。除此之外，UNIX还具有字符特殊文件(characterspecialfile)和块特殊文件(blockspecialfile)。常规文件(Regularfiles)是包含有用户信息的文件。用户一般使用的文件大都是常规文件，常规文件一般包括可执行文件、文本文件、图像文件，从常规文件读取数据或将数据写入时，内核会根据文件系统的规则执行操作，是写入可能被延迟，记录日志或者接受其他操作。 早期的操作系统只有一种访问方式：序列访问(sequentialaccess)。在这些系统中，进程可以按照顺序读取所有的字节或文件中的记录，但是不能跳过并乱序执行它们。顺序访问文件是可以返回到起点的，需要时可以多次读取该文件。当存储介质是磁带而不是磁盘时，顺序访问文件很方便。 在使用磁盘来存储文件时，可以不按照顺序读取文件中的字节或者记录，或者按照关键字而不是位置来访问记录。这种能够以任意次序进行读取的称为随机访问文件(randomaccessfile)。许多应用程序都需要这种方式。 有两种方法可以指示从何处开始读取文件。第一种方法是直接使用read从头开始读取。另一种是用一个特殊的seek操作设置当前位置，在seek操作后，从这个当前位置顺序地开始读文件。UNIX和Windows使用的是后面一种方式。 使用文件的目的是用来存储信息并方便以后的检索。对于存储和检索，不同的系统提供了不同的操作。以下是与文件有关的最常用的一些系统调用： 文件系统通常提供目录(directories)或者文件夹(folders)用于记录文件的位置，在很多系统中目录本身也是文件，下面我们会讨论关于文件，他们的组织形式、属性和可以对文件进行的操作。 目录系统最简单的形式是有一个能够包含所有文件的目录。这种目录被称为根目录(rootdirectory)，由于根目录的唯一性，所以其名称并不重要。在最早期的个人计算机中，这种系统很常见，部分原因是因为只有一个用户。下面是一个单层目录系统的例子 含有四个文件的单层目录系统 该目录中有四个文件。这种设计的优点在于简单，并且能够快速定位文件，毕竟只有一个地方可以检索。这种目录组织形式现在一般用于简单的嵌入式设备（如数码相机和某些便携式音乐播放器）上使用。 对于简单的应用而言，一般都用单层目录方式，但是这种组织形式并不适合于现代计算机，因为现代计算机含有成千上万个文件和文件夹。如果都放在根目录下，查找起来会非常困难。为了解决这一问题，出现了层次目录系统(HierarchicalDirectorySystems)，也称为目录树。通过这种方式，可以用很多目录把文件进行分组。进而，如果多个用户共享同一个文件服务器，比如公司的网络系统，每个用户可以为自己的目录树拥有自己的私人根目录。这种方式的组织结构如下 根目录含有目录A、B和C，分别属于不同的用户，其中两个用户个字创建了子目录。用户可以创建任意数量的子目录，现代文件系统都是按照这种方式组织的。 当目录树组织文件系统时，需要有某种方法指明文件名。常用的方法有两种，第一种方式是每个文件都会用一个绝对路径名(absolutepathname)，它由根目录到文件的路径组成。 另外一种指定文件名的方法是相对路径名(relativepathname)。它常常和工作目录(workingdirectory)（也称作当前目录(currentdirectory)）一起使用。用户可以指定一个目录作为当前工作目录。例如，如果当前目录是/usr/ast，那么绝对路径/usr/ast/mailbox可以直接使用mailbox来引用。 不同文件中管理目录的系统调用的差别比管理文件的系统调用差别大。为了了解这些系统调用有哪些以及它们怎样工作，下面给出一个例子（取自UNIX）。 文件系统存储在磁盘中。大部分的磁盘能够划分出一到多个分区，叫做磁盘分区(diskpartitioning)或者是磁盘分片(diskslicing)。每个分区都有独立的文件系统，每块分区的文件系统可以不同。磁盘的0号分区称为主引导记录(MasterBootRecord,MBR)，用来引导(boot)计算机。在MBR的结尾是分区表(partitiontable)。每个分区表给出每个分区由开始到结束的地址。 当计算机开始引boot时，BIOS读入并执行MBR。 MBR做的第一件事就是确定活动分区，读入它的第一个块，称为引导块(bootblock)并执行。引导块中的程序将加载分区中的操作系统。为了一致性，每个分区都会从引导块开始，即使引导块不包含操作系统。引导块占据文件系统的前4096个字节，从磁盘上的字节偏移量0开始。引导块可用于启动操作系统。 除了从引导块开始之外，磁盘分区的布局是随着文件系统的不同而变化的。通常文件系统会包含一些属性，如下 文件系统布局 紧跟在引导块后面的是超级块(Superblock)，超级块的大小为4096字节，从磁盘上的字节偏移4096开始。超级块包含文件系统的所有关键参数 在计算机启动或者文件系统首次使用时，超级块会被读入内存。 接着是文件系统中空闲块的信息，例如，可以用位图或者指针列表的形式给出。 BitMap位图或者Bitvector位向量 位图或位向量是一系列位或位的集合，其中每个位对应一个磁盘块，该位可以采用两个值：0和1，0表示已分配该块，而1表示一个空闲块。下图中的磁盘上给定的磁盘块实例（分配了绿色块）可以用16位的位图表示为：0000111000000110。 使用链表进行管理 在这种方法中，空闲磁盘块链接在一起，即一个空闲块包含指向下一个空闲块的指针。第一个磁盘块的块号存储在磁盘上的单独位置，也缓存在内存中。 这里不得不提一个叫做碎片(fragment)的概念，也称为片段。一般零散的单个数据通常称为片段。磁盘块可以进一步分为固定大小的分配单元，片段只是在驱动器上彼此不相邻的文件片段。 然后在后面是一个inode(indexnode)，也称作索引节点。它是一个数组的结构，每个文件有一个inode，inode非常重要，它说明了文件的方方面面。每个索引节点都存储对象数据的属性和磁盘块位置 有一种简单的方法可以找到它们ls-lai命令。让我们看一下根文件系统： inode节点主要包括了以下信息 文件分为两部分，索引节点和块。一旦创建后，每种类型的块数是固定的。你不能增加分区上inode的数量，也不能增加磁盘块的数量。 紧跟在inode后面的是根目录，它存放的是文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。 最重要的问题是记录各个文件分别用到了哪些磁盘块。不同的系统采用了不同的方法。下面我们会探讨一下这些方式。分配背后的主要思想是有效利用文件空间和快速访问文件，主要有三种分配方案 最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。因此，在具有1KB块的磁盘上，将为50KB文件分配50个连续块。 使用连续空间存储文件 上面展示了40个连续的内存块。从最左侧的0块开始。初始状态下，还没有装载文件，因此磁盘是空的。接着，从磁盘开始处（块0）处开始写入占用4块长度的内存A。然后是一个占用6块长度的内存B，会直接在A的末尾开始写。 注意每个文件都会在新的文件块开始写，所以如果文件A只占用了3又1/2个块，那么最后一个块的部分内存会被浪费。在上面这幅图中，总共展示了7个文件，每个文件都会从上个文件的末尾块开始写新的文件块。 连续的磁盘空间分配有两个优点。 因此，连续的空间分配具有实现简单、高性能的特点。 这里有两个文件D和F被删除了。当删除一个文件时，此文件所占用的块也随之释放，就会在磁盘空间中留下一些空闲块。磁盘并不会在这个位置挤压掉空闲块，因为这会复制空闲块之后的所有文件，可能会有上百万的块，这个量级就太大了。 第二种存储文件的方式是为每个文件构造磁盘块链表，每个文件都是磁盘块的链接列表，就像下面所示 以磁盘块的链表形式存储文件 每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。如果上面这张图你看的不是很清楚的话，可以看看整个的链表分配方案 与连续分配方案不同，这一方法可以充分利用每个磁盘块。除了最后一个磁盘块外，不会因为磁盘碎片而浪费存储空间。同样，在目录项中，只要存储了第一个文件块，那么其他文件块也能够被找到。 另一方面，在链表的分配方案中，尽管顺序读取非常方便，但是随机访问却很困难（这也是数组和链表数据结构的一大区别）。 还有一个问题是，由于指针会占用一些字节，每个磁盘块实际存储数据的字节数并不再是2的整数次幂。虽然这个问题并不会很严重，但是这种方式降低了程序运行效率。许多程序都是以长度为2的整数次幂来读写磁盘，由于每个块的前几个字节被指针所使用，所以要读出一个完成的块大小信息，就需要当前块的信息和下一块的信息拼凑而成，因此就引发了查找和拼接的开销。 由于连续分配和链表分配都有其不可忽视的缺点。所以提出了使用内存中的表来解决分配问题。取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决上述链表的两个不足之处。下面是一个例子 上图表示了链表形成的磁盘块的内容。这两个图中都有两个文件，文件A依次使用了磁盘块地址4、7、2、10、12，文件B使用了6、3、11和14。也就是说，文件A从地址4处开始，顺着链表走就能找到文件A的全部磁盘块。同样，从第6块开始，顺着链走到最后，也能够找到文件B的全部磁盘块。你会发现，这两个链表都以不属于有效磁盘编号的特殊标记（-1）结束。内存中的这种表格称为文件分配表(FileApplicationTable,FAT)。 文件只有打开后才能够被读取。在文件打开后，操作系统会使用用户提供的路径名来定位磁盘中的目录。目录项提供了查找文件磁盘块所需要的信息。根据系统的不同，提供的信息也不同，可能提供的信息是整个文件的磁盘地址，或者是第一个块的数量（两个链表方案）或inode的数量。不过不管用那种情况，目录系统的主要功能就是将文件的ASCII码的名称映射到定位数据所需的信息上。 当多个用户在同一个项目中工作时，他们通常需要共享文件。如果这个共享文件同时出现在多个用户目录下，那么他们协同工作起来就很方便。下面的这张图我们在上面提到过，但是有一个更改的地方，就是C的一个文件也出现在了B的目录下。 如果按照如上图的这种组织方式而言，那么B的目录与该共享文件的联系称为链接(link)。那么文件系统现在就是一个有向无环图(DirectedAcyclicGraph,简称DAG)，而不是一棵树了。 为此，Berkeley设计了一种全新的文件系统，试图缓解这个问题，这个文件系统就是日志结构文件系统(Log-structuredFileSystem,LFS)。旨在解决以下问题。 另一方面，当时的文件系统不论是UNIX还是FFS，都有大量的随机读写（在FFS中创建一个新文件至少需要5次随机写），因此成为整个系统的性能瓶颈。同时因为Pagecache的存在，作者认为随机读不是主要问题：随着越来越大的内存，大部分的读操作都能被cache，因此LFS主要要解决的是减少对硬盘的随机写操作。 到目前为止，所有写入最初都缓存在内存中，并且追加在日志末尾，所有缓存的写入都定期在单个段中写入磁盘。所以，现在打开文件也就意味着用映射定位文件的索引节点。一旦inode被定位后，磁盘块的地址就能够被找到。所有这些块本身都将位于日志中某处的分段中。 真实情况下的磁盘容量是有限的，所以最终日志会占满整个磁盘空间，这种情况下就会出现没有新的磁盘块被写入到日志中。幸运的是，许多现有段可能具有不再需要的块。例如，如果一个文件被覆盖了，那么它的inode将被指向新的块，但是旧的磁盘块仍在先前写入的段中占据着空间。 为了处理这个问题，LFS有一个清理(clean)线程，它会循环扫描日志并对日志进行压缩。首先，通过查看日志中第一部分的信息来查看其中存在哪些索引节点和文件。它会检查当前inode的映射来查看inode否在在当前块中，是否仍在被使用。如果不是，该信息将被丢弃。如果仍然在使用，那么inode和块就会进入内存等待写回到下一个段中。然后原来的段被标记为空闲，以便日志可以用来存放新的数据。用这种方法，清理线程遍历日志，从后面移走旧的段，然后将有效的数据放入内存等待写到下一个段中。由此一来整个磁盘会形成一个大的环形缓冲区，写线程将新的段写在前面，而清理线程则清理后面的段。 虽然日志结构系统的设计很优雅，但是由于它们和现有的文件系统不相匹配，因此还没有广泛使用。不过，从日志文件结构系统衍生出来一种新的日志系统，叫做日志文件系统，它会记录系统下一步将要做什么的日志。微软的NTFS文件系统、Linux的ext3就使用了此日志。OSX将日志系统作为可供选项。为了看清它是如何工作的，我们下面讨论一个例子，比如移除文件，这个操作在UNIX中需要三个步骤完成： UNIX操作系统使用一种虚拟文件系统(VirtualFileSystem,VFS)来尝试将多种文件系统构成一个有序的结构。关键的思想是抽象出所有文件系统都共有的部分，并将这部分代码放在一层，这一层再调用具体文件系统来管理数据。下面是一个VFS的系统结构 能够使文件系统工作是一回事，能够使文件系统高效、稳定的工作是另一回事，下面我们就来探讨一下文件系统的管理和优化。 文件通常存在磁盘中，所以如何管理磁盘空间是一个操作系统的设计者需要考虑的问题。在文件上进行存有两种策略：分配n个字节的连续磁盘空间；或者把文件拆分成多个并不一定连续的块。在存储管理系统中，主要有分段管理和分页管理两种方式。 正如我们所看到的，按连续字节序列存储文件有一个明显的问题，当文件扩大时，有可能需要在磁盘上移动文件。内存中分段也有同样的问题。不同的是，相对于把文件从磁盘的一个位置移动到另一个位置，内存中段的移动操作要快很多。因此，几乎所有的文件系统都把文件分割成固定大小的块来存储。 一旦把文件分为固定大小的块来存储，就会出现问题，块的大小是多少？按照磁盘组织方式，扇区、磁道和柱面显然都可以作为分配单位。在分页系统中，分页大小也是主要因素。 一旦指定了块大小，下一个问题就是怎样跟踪空闲块。有两种方法被广泛采用，如下图所示 第一种方法是采用磁盘块链表，链表的每个块中包含极可能多的空闲磁盘块号。对于1KB的块和32位的磁盘块号，空闲表中每个块包含有255个空闲的块号。考虑1TB的硬盘，拥有大概十亿个磁盘块。为了存储全部地址块号，如果每块可以保存255个块号，则需要将近400万个块。通常，空闲块用于保存空闲列表，因此存储基本上是空闲的。 另一种空闲空间管理的技术是位图(bitmap)，n个块的磁盘需要n位位图。在位图中，空闲块用1表示，已分配的块用0表示。对于1TB硬盘的例子，需要10亿位表示，即需要大约130000个1KB块存储。很明显，和32位链表模型相比，位图需要的空间更少，因为每个块使用1位。只有当磁盘快满的时候，链表需要的块才会比位图少。 为了防止一些用户占用太多的磁盘空间，多用户操作通常提供一种磁盘配额(enforcingdiskquotas)的机制。系统管理员为每个用户分配最大的文件和块分配，并且操作系统确保用户不会超过其配额。我们下面会谈到这一机制。 在用户打开一个文件时，操作系统会找到文件属性和磁盘地址，并把它们送入内存中的打开文件表。其中一个属性告诉文件所有者是谁。任何有关文件的增加都会记到所有者的配额中。 配额表中记录了每个用户的配额 第二张表包含了每个用户当前打开文件的配额记录，即使是其他人打开该文件也一样。如上图所示，该表的内容是从被打开文件的所有者的磁盘配额文件中提取出来的。当所有文件关闭时，该记录被写回配额文件。 当在打开文件表中建立一新表项时，会产生一个指向所有者配额记录的指针。每次向文件中添加一个块时，文件所有者所用数据块的总数也随之增加，并会同时增加硬限制和软限制的检查。可以超出软限制，但硬限制不可以超出。当已达到硬限制时，再往文件中添加内容将引发错误。同样，对文件数目也存在类似的检查。 其次，对上次未修改过的文件再进行备份是一种浪费，因而产生了一种增量转储(incrementaldumps)的思想。最简单的增量转储的形式就是周期性的做全面的备份，而每天只对增量转储完成后发生变化的文件做单个备份。 第三，既然待转储的往往是海量数据，那么在将其写入磁带之前对文件进行压缩就很有必要。但是，如果在备份过程中出现了文件损坏的情况，就会导致破坏压缩算法，从而使整个磁带无法读取。所以在备份前是否进行文件压缩需慎重考虑。 磁盘转储到备份磁盘上有两种方案：物理转储和逻辑转储。物理转储(physicaldump)是从磁盘的0块开始，依次将所有磁盘块按照顺序写入到输出磁盘，并在复制最后一个磁盘时停止。这种程序的万无一失性是其他程序所不具备的。 第二个需要考虑的是坏块的转储。制造大型磁盘而没有瑕疵是不可能的，所以也会存在一些坏块(badblocks)。有时进行低级格式化后，坏块会被检测出来并进行标记，这种情况的解决办法是用磁盘末尾的一些空闲块所替换。 然而，一些块在格式化后会变坏，在这种情况下操作系统可以检测到它们。通常情况下，它可以通过创建一个由所有坏块组成的文件来解决问题，确保它们不会出现在空闲池中并且永远不会被分配。那么此文件是完全不可读的。如果磁盘控制器将所有的坏块重新映射，物理转储还是能够正常工作的。 影响可靠性的一个因素是文件系统的一致性。许多文件系统读取磁盘块、修改磁盘块、再把它们写回磁盘。如果系统在所有块写入之前崩溃，文件系统就会处于一种不一致(inconsistent)的状态。如果某些尚未写回的块是索引节点块，目录块或包含空闲列表的块，则此问题是很严重的。 为了处理文件系统一致性问题，大部分计算机都会有应用程序来检查文件系统的一致性。例如，UNIX有fsck；Windows有sfc，每当引导系统时（尤其是在崩溃后），都可以运行该程序。 可以进行两种一致性检查：块的一致性检查和文件的一致性检查。为了检查块的一致性，应用程序会建立两张表，每个包含一个计数器的块，最初设置为0。第一个表中的计数器跟踪该块在文件中出现的次数，第二张表中的计数器记录每个块在空闲列表、空闲位图中出现的频率。 访问磁盘的效率要比内存满的多，是时候又祭出这张图了 最常用的减少磁盘访问次数的技术是使用块高速缓存(blockcache)或者缓冲区高速缓存(buffercache)。高速缓存指的是一系列的块，它们在逻辑上属于磁盘，但实际上基于性能的考虑被保存在内存中。 管理高速缓存有不同的算法，常用的算法是：检查全部的读请求，查看在高速缓存中是否有所需要的块。如果存在，可执行读操作而无须访问磁盘。如果检查块不再高速缓存中，那么首先把它读入高速缓存，再复制到所需的地方。之后，对同一个块的请求都通过高速缓存来完成。 高速缓存的操作如下图所示 由于在高速缓存中有许多块，所以需要某种方法快速确定所需的块是否存在。常用方法是将设备和磁盘地址进行散列操作，然后，在散列表中查找结果。具有相同散列值的块在一个链表中连接在一起（这个数据结构是不是很像HashMap），这样就可以沿着冲突链查找其他块。 如果高速缓存已满，此时需要调入新的块，则要把原来的某一块调出高速缓存，如果要调出的块在上次调入后已经被修改过，则需要把它写回磁盘。 当然，块提前读取策略只适用于实际顺序读取的文件。对随机访问的文件，提前读丝毫不起作用。甚至还会造成阻碍。 高速缓存和块提前读并不是提高文件系统性能的唯一方法。另一种重要的技术是把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘臂的移动次数。当写一个输出文件时，文件系统就必须按照要求一次一次地分配磁盘块。如果用位图来记录空闲块，并且整个位图在内存中，那么选择与前一块最近的空闲块是很容易的。如果用空闲表，并且链表的一部分存在磁盘上，要分配紧邻的空闲块就会困难很多。 在初始安装操作系统后，文件就会被不断的创建和清除，于是磁盘会产生很多的碎片，在创建一个文件时，它使用的块会散布在整个磁盘上，降低性能。删除文件后，回收磁盘块，可能会造成空穴。 磁盘性能可以通过如下方式恢复：移动文件使它们相互挨着，并把所有的至少是大部分的空闲空间放在一个或多个大的连续区域内。Windows有一个程序defrag就是做这个事儿的。Windows用户会经常使用它，SSD除外。 磁盘碎片整理程序会在让文件系统上很好地运行。Linux文件系统（特别是ext2和ext3）由于其选择磁盘块的方式，在磁盘碎片整理上一般不会像Windows一样困难，因此很少需要手动的磁盘碎片整理。而且，固态硬盘并不受磁盘碎片的影响，事实上，在固态硬盘上做磁盘碎片整理反倒是多此一举，不仅没有提高性能，反而磨损了固态硬盘。所以碎片整理只会缩短固态硬盘的寿命。 下面我们来探讨一下I/O流程问题。 什么是I/O设备？I/O设备又叫做输入/输出设备，它是人类用来和计算机进行通信的外部硬件。输入/输出设备能够向计算机发送数据（输出）并从计算机接收数据（输入）。 I/O设备(I/Odevices)可以分成两种：块设备(blockdevices)和字符设备(characterdevices)。 块设备是一个能存储固定大小块信息的设备，它支持以固定大小的块，扇区或群集读取和（可选）写入数据。每个块都有自己的物理地址。通常块的大小在512-65536之间。所有传输的信息都会以连续的块为单位。块设备的基本特征是每个块都较为对立，能够独立的进行读写。常见的块设备有硬盘、蓝光光盘、USB盘 与字符设备相比，块设备通常需要较少的引脚。 基于给定固态存储器的块设备比基于相同类型的存储器的字节寻址要慢一些，因为必须在块的开头开始读取或写入。所以，要读取该块的任何部分，必须寻找到该块的开始，读取整个块，如果不使用该块，则将其丢弃。要写入块的一部分，必须寻找到块的开始，将整个块读入内存，修改数据，再次寻找到块的开头处，然后将整个块写回设备。 另一类I/O设备是字符设备。字符设备以字符为单位发送或接收一个字符流，而不考虑任何块结构。字符设备是不可寻址的，也没有任何寻道操作。常见的字符设备有打印机、网络设备、鼠标、以及大多数与磁盘不同的设备。 设备控制器是处理CPU传入和传出信号的系统。设备通过插头和插座连接到计算机，并且插座连接到设备控制器。设备控制器从连接的设备处接收数据，并将其存储在控制器内部的一些特殊目的寄存器(specialpurposeregisters)也就是本地缓冲区中。 每个设备控制器都会有一个应用程序与之对应，设备控制器通过应用程序的接口通过中断与操作系统进行通信。设备控制器是硬件，而设备驱动程序是软件。 每个控制器都会有几个寄存器用来和CPU进行通信。通过写入这些寄存器，操作系统可以命令设备发送数据，接收数据、开启或者关闭设备等。通过从这些寄存器中读取信息，操作系统能够知道设备的状态，是否准备接受一个新命令等。 为了控制寄存器，许多设备都会有数据缓冲区(databuffer)，来供系统进行读写。 那么问题来了，CPU如何与设备寄存器和设备数据缓冲区进行通信呢？存在两个可选的方式。第一种方法是，每个控制寄存器都被分配一个I/O端口(I/Oport)号，这是一个8位或16位的整数。所有I/O端口的集合形成了受保护的I/O端口空间，以便普通用户程序无法访问它（只有操作系统可以访问）。使用特殊的I/O指令像是 INREG,PORTCPU可以读取控制寄存器PORT的内容并将结果放在CPU寄存器REG中。类似的，使用 OUTPORT,REGCPU可以将REG的内容写到控制寄存器中。大多数早期计算机，包括几乎所有大型主机，如IBM360及其所有后续机型，都是以这种方式工作的。 第二个方法是PDP-11引入的，它将所有控制寄存器映射到内存空间中。 DMA传送操作 现代操作系统实际更为复杂，但是原理是相同的。如果硬件有DMA控制器，那么操作系统只能使用DMA。有时这个控制器会集成到磁盘控制器和其他控制器中，但这种设计需要在每个设备上都装有一个分离的DMA控制器。单个的DMA控制器可用于向多个设备传输，这种传输往往同时进行。 首先CPU通过设置DMA控制器的寄存器对它进行编程，所以DMA控制器知道将什么数据传送到什么地方。DMA控制器还要向磁盘控制器发出一个命令，通知它从磁盘读数据到其内部的缓冲区并检验校验和。当有效数据位于磁盘控制器的缓冲区中时，DMA就可以开始了。 DMA控制器通过在总线上发出一个读请求到磁盘控制器而发起DMA传送，这是第二步。这个读请求就像其他读请求一样，磁盘控制器并不知道或者并不关心它是来自CPU还是来自DMA控制器。通常情况下，要写的内存地址在总线的地址线上，所以当磁盘控制器去匹配下一个字时，它知道将该字写到什么地方。写到内存就是另外一个总线循环了，这是第三步。当写操作完成时，磁盘控制器在总线上发出一个应答信号到DMA控制器，这是第四步。 然后，DMA控制器会增加内存地址并减少字节数量。如果字节数量仍然大于0，就会循环步骤2-步骤4，直到字节计数变为0。此时，DMA控制器会打断CPU并告诉它传输已经完成了。 在一台个人计算机体系结构中，中断结构会如下所示 中断是怎样发生的 使机器处于良好状态的中断称为精确中断(preciseinterrupt)。这样的中断具有四个属性： 不满足以上要求的中断称为不精确中断(impreciseinterrupt)，不精确中断让人很头疼。上图描述了不精确中断的现象。指令的执行时序和完成度具有不确定性，而且恢复起来也非常麻烦。 I/O软件设计一个很重要的目标就是设备独立性(deviceindependence)。这意味着我们能够编写访问任何设备的应用程序，而不用事先指定特定的设备。 除了设备独立性外，I/O软件实现的第二个重要的目标就是错误处理(errorhandling)。通常情况下来说，错误应该交给硬件层面去处理。如果设备控制器发现了读错误的话，它会尽可能的去修复这个错误。如果设备控制器处理不了这个问题，那么设备驱动程序应该进行处理，设备驱动程序会再次尝试读取操作，很多错误都是偶然性的，如果设备驱动程序无法处理这个错误，才会把错误向上抛到硬件层面（上层）进行处理，很多时候，上层并不需要知道下层是如何解决错误的。 I/O软件实现的第三个目标就是同步(synchronous)和异步(asynchronous，即中断驱动)传输。这里先说一下同步和异步是怎么回事吧。 同步传输中数据通常以块或帧的形式发送。发送方和接收方在数据传输之前应该具有同步时钟。而在异步传输中，数据通常以字节或者字符的形式发送，异步传输则不需要同步时钟，但是会在传输之前向数据添加奇偶校验位。大部分物理IO(physicalI/O)是异步的。物理I/O中的CPU是很聪明的，CPU传输完成后会转而做其他事情，它和中断心灵相通，等到中断发生后，CPU才会回到传输这件事情上来。 I/O软件的最后一个问题是缓冲(buffering)。通常情况下，从一个设备发出的数据不会直接到达最后的设备。其间会经过一系列的校验、检查、缓冲等操作才能到达。 I/O软件引起的最后一个问题就是共享设备和独占设备的问题。有些I/O设备能够被许多用户共同使用。一些设备比如磁盘，让多个用户使用一般不会产生什么问题，但是某些设备必须具有独占性，即只允许单个用户使用完成后才能让其他用户使用。 一共有三种控制I/O设备的方法 I/O软件通常组织成四个层次，它们的大致结构如下图所示 下面我们具体的来探讨一下上面的层次结构 在计算机系统中，中断就像女人的脾气一样无时无刻都在产生，中断的出现往往是让人很不爽的。中断处理程序又被称为中断服务程序或者是ISR(InterruptServiceRoutines)，它是最靠近硬件的一层。中断处理程序由硬件中断、软件中断或者是软件异常启动产生的中断，用于实现设备驱动程序或受保护的操作模式（例如系统调用）之间的转换。 中断处理程序负责处理中断发生时的所有操作，操作完成后阻塞，然后启动中断驱动程序来解决阻塞。通常会有三种通知方式，依赖于不同的具体实现 每个连接到计算机的I/O设备都需要有某些特定设备的代码对其进行控制。这些提供I/O设备到设备控制器转换的过程的代码称为设备驱动程序(Devicedriver)。 设备控制器的主要功能有下面这些 在这种情况下，设备控制器会阻塞，直到中断来解除阻塞状态。还有一种情况是操作是可以无延迟的完成，所以驱动程序不需要阻塞。在第一种情况下，操作系统可能被中断唤醒；第二种情况下操作系统不会被休眠。 设备驱动程序必须是可重入的，因为设备驱动程序会阻塞和唤醒然后再次阻塞。驱动程序不允许进行系统调用，但是它们通常需要与内核的其余部分进行交互。 I/O软件有两种，一种是我们上面介绍过的基于特定设备的，还有一种是设备无关性的，设备无关性也就是不需要特定的设备。设备驱动程序与设备无关的软件之间的界限取决于具体的系统。下面显示的功能由设备无关的软件实现 与设备无关的软件的基本功能是对所有设备执行公共的I/O功能，并且向用户层软件提供一个统一的接口。 无论是对于块设备还是字符设备来说，缓冲都是一个非常重要的考量标准。缓冲技术应用广泛，但它也有缺点。如果数据被缓冲次数太多，会影响性能。 在I/O中，出错是一种再正常不过的情况了。当出错发生时，操作系统必须尽可能处理这些错误。有一些错误是只有特定的设备才能处理，有一些是由框架进行处理，这些错误和特定的设备无关。 I/O错误的一类是程序员编程错误，比如还没有打开文件前就读流，或者不关闭流导致内存溢出等等。这类问题由程序员处理；另外一类是实际的I/O错误，例如向一个磁盘坏块写入数据，无论怎么写都写入不了。这类问题由驱动程序处理，驱动程序处理不了交给硬件处理，这个我们上面也说过。 我们在操作系统概述中说到，操作系统一个非常重要的功能就是屏蔽了硬件和软件的差异性，为硬件和软件提供了统一的标准，这个标准还体现在为设备驱动程序提供统一的接口，因为不同的硬件和厂商编写的设备驱动程序不同，所以如果为每个驱动程序都单独提供接口的话，这样没法搞，所以必须统一。 一些设备例如打印机，它只能由一个进程来使用，这就需要操作系统根据实际情况判断是否能够对设备的请求进行检查，判断是否能够接受其他请求，一种比较简单直接的方式是在特殊文件上执行open操作。如果设备不可用，那么直接open会导致失败。还有一种方式是不直接导致失败，而是让其阻塞，等到另外一个进程释放资源后，在进行open打开操作。这种方式就把选择权交给了用户，由用户判断是否应该等待。 不同的磁盘会具有不同的扇区大小，但是软件不会关心扇区大小，只管存储就是了。一些字符设备可以一次一个字节的交付数据，而其他的设备则以较大的单位交付数据，这些差异也可以隐藏起来。 虽然大部分I/O软件都在内核结构中，但是还有一些在用户空间实现的I/O软件，凡事没有绝对。一些I/O软件和库过程在用户空间存在，然后以提供系统调用的方式实现。 盘可以说是硬件里面比较简单的构造了，同时也是最重要的。下面我们从盘谈起，聊聊它的物理构造 盘会有很多种类型。其中最简单的构造就是磁盘(magneticharddisks)，也被称为harddisk,HDD等。磁盘通常与安装在磁臂上的磁头配对，磁头可将数据读取或者将数据写入磁盘，因此磁盘的读写速度都同样快。在磁盘中，数据是随机访问的，这也就说明可以通过任意的顺序来存储和检索单个数据块，所以你可以在任意位置放置磁盘来让磁头读取，磁盘是一种非易失性的设备，即使断电也能永久保留。 为了组织和检索数据，会将磁盘组织成特定的结构，这些特定的结构就是磁道、扇区和柱面 磁盘被组织成柱面形式，每个盘用轴相连，每一个柱面包含若干磁道，每个磁道由若干扇区组成。软盘上大约每个磁道有8-32个扇区，硬盘上每条磁道上扇区的数量可达几百个，磁头大约是1-16个。 对于磁盘驱动程序来说，一个非常重要的特性就是控制器是否能够同时控制两个或者多个驱动器进行磁道寻址，这就是重叠寻道(overlappedseek)。对于控制器来说，它能够控制一个磁盘驱动程序完成寻道操作，同时让其他驱动程序等待寻道结束。控制器也可以在一个驱动程序上进行读写草哦做，与此同时让另外的驱动器进行寻道操作，但是软盘控制器不能在两个驱动器上进行读写操作。 RAID称为磁盘冗余阵列，简称磁盘阵列。利用虚拟化技术把多个硬盘结合在一起，成为一个或多个磁盘阵列组，目的是提升性能或数据冗余。 RAID有不同的级别 磁盘由一堆铝的、合金或玻璃的盘片组成，磁盘刚被创建出来后，没有任何信息。磁盘在使用前必须经过低级格式化(low-levvelformat)，下面是一个扇区的格式 前导码相当于是标示扇区的开始位置，通常以位模式开始，前导码还包括柱面号、扇区号等一些其他信息。紧随前导码后面的是数据区，数据部分的大小由低级格式化程序来确定。大部分磁盘使用512字节的扇区。数据区后面是ECC，ECC的全称是errorcorrectioncode，数据纠错码，它与普通的错误检测不同，ECC还可以用于恢复读错误。ECC阶段的大小由不同的磁盘制造商实现。ECC大小的设计标准取决于设计者愿意牺牲多少磁盘空间来提高可靠性，以及程序可以处理的ECC的复杂程度。通常情况下ECC是16位，除此之外，硬盘一般具有一定数量的备用扇区，用于替换制造缺陷的扇区。 通常情况下，磁盘在进行寻道时，其他进程会产生其他的磁盘请求。磁盘驱动程序会维护一张表，表中会记录着柱面号当作索引，每个柱面未完成的请求会形成链表，链表头存放在表的相应表项中。 一种对先来先服务的算法改良的方案是使用最短路径优先(SSF)算法，下面描述了这个算法。 假如我们在对磁道6号进行寻址时，同时发生了对11,2,4,14,8,15,3的请求，如果采用先来先服务的原则，如下图所示 我们可以计算一下磁盘臂所跨越的磁盘数量为5+9+2+10+6+7+12=51，相当于是跨越了51次盘面，如果使用最短路径优先，我们来计算一下跨越的盘面 但是，最短路径优先的算法也不是完美无缺的，这种算法照样存在问题，那就是优先级问题， 这里有一个原型可以参考就是我们日常生活中的电梯，电梯使用一种电梯算法(elevatoralgorithm)来进行调度，从而满足协调效率和公平性这两个相互冲突的目标。电梯一般会保持向一个方向移动，直到在那个方向上没有请求为止，然后改变方向。 电梯算法需要维护一个二进制位，也就是当前的方向位：UP(向上)或者是DOWN(向下)。当一个请求处理完成后，磁盘或电梯的驱动程序会检查该位，如果此位是UP位，磁盘臂或者电梯仓移到下一个更高跌未完成的请求。如果高位没有未完成的请求，则取相反方向。当方向位是DOWN时，同时存在一个低位的请求，磁盘臂会转向该点。如果不存在的话，那么它只是停止并等待。 我们举个例子来描述一下电梯算法，比如各个柱面得到服务的顺序是4，7，10，14，9，6，3，1，那么它的流程图如下 所以电梯算法需要跨越的盘面数量是3+3+4+5+3+3+1=22 电梯算法通常情况下不如SSF算法。 一般坏块有两种处理办法，一种是在控制器中进行处理；一种是在操作系统层面进行处理。 这两种方法经常替换使用，比如一个具有30个数据扇区和两个备用扇区的磁盘，其中扇区4是有瑕疵的。 控制器能做的事情就是将备用扇区之一重新映射。 还有一种处理方式是将所有的扇区都向上移动一个扇区 上面这这两种情况下控制器都必须知道哪个扇区，可以通过内部的表来跟踪这一信息，或者通过重写前导码来给出重新映射的扇区号。如果是重写前导码，那么涉及移动的方式必须重写后面所有的前导码，但是最终会提供良好的性能。 磁盘经常会出现错误，导致好的扇区会变成坏扇区，驱动程序也有可能挂掉。RAID可以对扇区出错或者是驱动器崩溃提出保护，然而RAID却不能对坏数据中的写错误提供保护，也不能对写操作期间的崩溃提供保护，这样就会破坏原始数据。 我们期望磁盘能够准确无误的工作，但是事实情况是不可能的，但是我们能够知道的是，一个磁盘子系统具有如下特性：当一个写命令发给它时，磁盘要么正确地写数据，要么什么也不做，让现有的数据完整无误的保留。这样的系统称为稳定存储器(stablestorage)。稳定存储器的目标就是不惜一切代价保证磁盘的一致性。 稳定存储器使用两个一对相同的磁盘，对应的块一同工作形成一个无差别的块。稳定存储器为了实现这个目的，定义了下面三种操作： 在计算机中有两种类型的时钟，这些时钟与现实生活中使用的时钟完全不一样。 这种时钟称为可编程时钟，可编程时钟有两种模式，一种是一键式(one-shotmode)，当时钟启动时，会把存储器中的值复制到计数器中，然后，每次晶体的振荡器的脉冲都会使计数器-1。当计数器变为0时，会产生一个中断，并停止工作，直到软件再一次显示启动。还有一种模式时方波(square-wavemode)模式，在这种模式下，当计数器变为0并产生中断后，存储寄存器的值会自动复制到计数器中，这种周期性的中断称为一个时钟周期。 时钟软件也被称为可编程时钟，可以设置它以程序需要的任何速率引发中断。时钟软件触发的中断是一种硬中断，但是某些应用程序对于硬中断来说是不可接受的。 这时候就需要一种软定时器(softtimer)避免了中断，无论何时当内核因为某种原因呢在运行时，它返回用户态之前都会检查时钟来了解软定时器是否到期。如果软定时器到期，则执行被调度的事件也无需切换到内核态，因为本身已经处于内核态中。这种方式避免了频繁的内核态和用户态之前的切换，提高了程序运行效率。 软定时器因为不同的原因切换进入内核态的速率不同，原因主要有 死锁问题也是操作系统非常重要的一类问题 大部分的死锁都和资源有关，在进程对设备、文件具有独占性（排他性）时会产生死锁。我们把这类需要排他性使用的对象称为资源(resource)。资源主要分为可抢占资源和不可抢占资源 资源主要有可抢占资源和不可抢占资源。可抢占资源(preemptableresource)可以从拥有它的进程中抢占而不会造成其他影响，内存就是一种可抢占性资源，任何进程都能够抢先获得内存的使用权。 不可抢占资源(nonpreemtableresource)指的是除非引起错误或者异常，否则进程无法抢占指定资源，这种不可抢占的资源比如有光盘，在进程执行调度的过程中，其他进程是不能得到该资源的。 如果要对死锁进行一个定义的话，下面的定义比较贴切 如果一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，这种情况会导致死锁。 针对我们上面的描述，资源死锁可能出现的情况主要有 发生死锁时，上面的情况必须同时会发生。如果其中任意一个条件不会成立，死锁就不会发生。可以通过破坏其中任意一个条件来破坏死锁，下面这些破坏条件就是我们探讨的重点 Holt在1972年提出对死锁进行建模，建模的标准如下： 从资源节点到进程节点表示资源已经被进程占用，如下图所示 在上图中表示当前资源R正在被A进程所占用 由进程节点到资源节点的有向图表示当前进程正在请求资源，并且该进程已经被阻塞，处于等待这个资源的状态 在上图中，表示的含义是进程B正在请求资源S。Holt认为，死锁的描述应该如下 这是一个死锁的过程，进程C等待资源T的释放，资源T却已经被进程D占用，进程D等待请求占用资源U，资源U却已经被线程C占用，从而形成环。 有四种处理死锁的策略： 下面我们分别介绍一下这四种方法 最简单的解决办法就是使用鸵鸟算法(ostrichalgorithm)，把头埋在沙子里，假装问题根本没有发生。每个人看待这个问题的反应都不同。数学家认为死锁是不可接受的，必须通过有效的策略来防止死锁的产生。工程师想要知道问题发生的频次，系统因为其他原因崩溃的次数和死锁带来的严重后果。如果死锁发生的频次很低，而经常会由于硬件故障、编译器错误等其他操作系统问题导致系统崩溃，那么大多数工程师不会修复死锁。 第二种技术是死锁的检测和恢复。这种解决方式不会尝试去阻止死锁的出现。相反，这种解决方案会希望死锁尽可能的出现，在监测到死锁出现后，对其进行恢复。下面我们就来探讨一下死锁的检测和恢复的几种方式 每种资源类型都有一个资源是什么意思？我们经常提到的打印机就是这样的，资源只有打印机，但是设备都不会超过一个。 可以通过构造一张资源分配表来检测这种错误，比如我们上面提到的 如果这张图包含了一个或一个以上的环，那么死锁就存在，处于这个环中任意一个进程都是死锁的进程。 如果有多种相同的资源存在，就需要采用另一种方法来检测死锁。可以通过构造一个矩阵来检测从P1->Pn这n个进程中的死锁。 现在我们提供一种基于矩阵的算法来检测从P1到Pn这n个进程中的死锁。假设资源类型为m，E1代表资源类型1，E2表示资源类型2，Ei代表资源类型i(1<=i<=m)。E表示的是现有资源向量(existingresourcevector)，代表每种已存在的资源总数。 现在我们就需要构造两个数组：C表示的是当前分配矩阵(currentallocationmatrix)，R表示的是请求矩阵(requestmatrix)。Ci表示的是Pi持有每一种类型资源的资源数。所以，Cij表示Pi持有资源j的数量。Rij表示Pi所需要获得的资源j的数量 一般来说，已分配资源j的数量加起来再和所有可供使用的资源数相加=该类资源的总数。 死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的，算法会开始对进程做标记，进程被标记后说明进程被执行了，不会进入死锁，当算法结束时，任何没有被标记过的进程都会被判定为死锁进程。 上面我们探讨了两种检测死锁的方式，那么现在你知道怎么检测后，你何时去做死锁检测呢？一般来说，有两个考量标准： 上面我们探讨了如何检测进程死锁，我们最终的目的肯定是想让程序能够正常的运行下去，所以针对检测出来的死锁，我们要对其进行恢复，下面我们会探讨几种死锁的恢复方式 在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通知原进程的情况下，将某个资源从进程中强制取走给其他进程使用，使用完后又送回。这种恢复方式一般比较困难而且有些简单粗暴，并不可取。 如果系统设计者和机器操作员知道有可能发生死锁，那么就可以定期检查流程。进程的检测点意味着进程的状态可以被写入到文件以便后面进行恢复。检测点不仅包含存储映像(memoryimage)，还包含资源状态(resourcestate)。一种更有效的解决方式是不要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。 最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通，这时候就需要杀死别的资源进行恢复。 另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。 我们上面讨论的是如何检测出现死锁和如何恢复死锁，下面我们探讨几种规避死锁的方式 银行家算法是Dijkstra在1965年提出的一种调度算法，它本身是一种死锁的调度算法。它的模型是基于一个城镇中的银行家，银行家向城镇中的客户承诺了一定数量的贷款额度。算法要做的就是判断请求是否会进入一种不安全的状态。如果是，就拒绝请求，如果请求后系统是安全的，就接受该请求。 类似的，还有多个资源的银行家算法，读者可以自行了解。 死锁本质上是无法避免的，因为它需要获得未知的资源和请求，但是死锁是满足四个条件后才出现的，它们分别是 我们分别对这四个条件进行讨论，按理说破坏其中的任意一个条件就能够破坏死锁 我们首先考虑的就是破坏互斥使用条件。如果资源不被一个进程独占，那么死锁肯定不会产生。如果两个打印机同时使用一个资源会造成混乱，打印机的解决方式是使用假脱机打印机(spoolingprinter)，这项技术可以允许多个进程同时产生输出，在这种模型中，实际请求打印机的唯一进程是打印机守护进程，也称为后台进程。后台进程不会请求其他资源。我们可以消除打印机的死锁。 后台进程通常被编写为能够输出完整的文件后才能打印，假如两个进程都占用了假脱机空间的一半，而这两个进程都没有完成全部的输出，就会导致死锁。 因此，尽量做到尽可能少的进程可以请求资源。 第二种方式是如果我们能阻止持有资源的进程请求其他资源，我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。如果所需的资源可用，进程会完成资源的分配并运行到结束。如果有任何一个资源处于频繁分配的情况，那么没有分配到资源的进程就会等待。 很多进程无法在执行完成前就知道到底需要多少资源，如果知道的话，就可以使用银行家算法；还有一个问题是这样无法合理有效利用资源。 还有一种方式是进程在请求其他资源时，先释放所占用的资源，然后再尝试一次获取全部的资源。 破坏不可抢占条件也是可以的。可以通过虚拟化的方式来避免这种情况。 现在就剩最后一个条件了，循环等待条件可以通过多种方法来破坏。一种方式是制定一个标准，一个进程在任何时候只能使用一种资源。如果需要另外一种资源，必须释放当前资源。对于需要将大文件从磁带复制到打印机的过程，此限制是不可接受的。 另一种方式是将所有的资源统一编号，如下图所示 尽管通过这种方式来消除死锁，但是编号的顺序不可能让每个进程都会接受。 下面我们来探讨一下其他问题，包括通信死锁、活锁是什么、饥饿问题和两阶段加锁 一种解决方式是使用两阶段提交(two-phaselocking)。顾名思义分为两个阶段，一阶段是进程尝试一次锁定它需要的所有记录。如果成功后，才会开始第二阶段，第二阶段是执行更新并释放锁。第一阶段并不做真正有意义的工作。 如果在第一阶段某个进程所需要的记录已经被加锁，那么该进程会释放所有锁定的记录并重新开始第一阶段。从某种意义上来说，这种方法类似于预先请求所有必需的资源或者是在进行一些不可逆的操作之前请求所有的资源。 不过在一般的应用场景中，两阶段加锁的策略并不通用。如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受的。 我们上面一直讨论的是资源死锁，资源死锁是一种死锁类型，但并不是唯一类型，还有通信死锁，也就是两个或多个进程在发送消息时出现的死锁。进程A给进程B发了一条消息，然后进程A阻塞直到进程B返回响应。假设请求消息丢失了，那么进程A在一直等着回复，进程B也会阻塞等待请求消息到来，这时候就产生死锁。 尽管会产生死锁，但是这并不是一个资源死锁，因为A并没有占据B的资源。事实上，通信死锁并没有完全可见的资源。根据死锁的定义来说：每个进程因为等待其他进程引起的事件而产生阻塞，这就是一种死锁。相较于最常见的通信死锁，我们把上面这种情况称为通信死锁(communicationdeadlock)。 但是并非所有网络通信发生的死锁都是通信死锁，也存在资源死锁，下面就是一个典型的资源死锁。 当一个数据包从主机进入路由器时，会被放入一个缓冲区，然后再传输到另外一个路由器，再到另一个，以此类推直到目的地。缓冲区都是资源并且数量有限。如下图所示，每个路由器都有10个缓冲区（实际上有很多）。 假如路由器A的所有数据需要发送到B，B的所有数据包需要发送到D，然后D的所有数据包需要发送到A。没有数据包可以移动，因为在另一端没有缓冲区可用，这就是一个典型的资源死锁。 现在假想有一对并行的进程用到了两个资源。它们分别尝试获取另一个锁失败后，两个进程都会释放自己持有的锁，再次进行尝试，这个过程会一直进行重复。很明显，这个过程中没有进程阻塞，但是进程仍然不会向下执行，这种状况我们称之为活锁(livelock)。 我们假设打印机的分配方案是每次都会分配给最小文件的进程，那么要打印大文件的进程会永远得不到服务，导致进程饥饿，进程会无限制的推后，虽然它没有阻塞。