## 摘录 共计：356个摘录 ## 第2章 操作系统历史 - 第一阶段：状态机操作系统（1940年以前） - 所谓状态机操作系统实际上算不上是我们现在通常所定义的操作系统，而是一种简单的状态转换程序：根据特定输入和现在的特定状态进行状态转换而已。这个时候的计算机也不是现代意义上的计算机，而是所谓的自动机 - 第二阶段：单一操作员单一控制端操作系统（20世纪40年代） - SOSC操作系统的设计目的是满足基本功能，并提供人机交互。在这种操作系统下，任何时候只能做一件事，即不支持并发和多道程序运行。操作系统本身只是一组标准库函数而已。操作系统本身并不自我运行，而是等待操作员输入命令再运行。用户想使用什么服务，就直接在命令行键入代表该服务的对应操作系统的库函数名（文件名）即可。 - 第三阶段：批处理操作系统（20世纪50年代） - 仔细考察了SOSC后，人们发现，SOSC效率之所以低下，是因为计算机总是在等待人的下一步动作，而人的动作总是很慢。因此，人们觉得，如果去掉等待人的时间，即让所有的人先想好自己要运行的命令，列成一个清单，打印在纸带上，然后交给一个工作人员来一批一批地处理，效率不就提高了吗？这样就形成了批处理操作系统。 - 批处理的过程是：用户将自己的程序编在卡片或纸带上，交给计算机管理员处理。管理员在收到一定数量的用户程序后，将卡片和纸带上的程序和数据通过IBM 1401机器读入，并写到磁带上。这样每盘磁带通常会含有多个用户的程序。然后，计算机操作员将这盘磁带加载到IBM 7094上，一个一个地运行用户的程序，运行的结果写在另一个磁盘上。所有用户程序运行结束后，将存有结果的磁盘取下来，连到IBM 1401机器上打印结果，然后就可以将打印结果交给各个用户了。 - 磁带上的多个用户程序必须以某种方式进行隔离，这需要一个抽象的东西来区分。这个抽象的东西不是别的，就是文件。 - 驱动这个阶段操作系统发展的动力是改善效率。因为机器的昂贵，我们不能容忍机器在操作员思考或I/O设备工作期间闲置起来。 - 第四代：多道批处理操作系统（20世纪60年代） - CPU和I/O设备的运行是串行的，即在程序进行输入输出时，CPU只能等待。CPU需要不断地探询I/O是否完成，因而不能执行别的程序。 - 第五代之一：分时操作系统（20世纪70年代） - 分时操作系统里面最著名的应该是MulticS和UNIX。 - 分时引入的多道程序设计，又造成操作系统的空前复杂，我们需要应对竞争、通信、死锁、保护等一系列的新功能。因此，操作系统在本阶段变得相当复杂。 - 第五代之二：实时操作系统 - 实时操作系统是指所有任务都在规定时间内完成的操作系统，即必须满足时序可预测性（Timing pre-dictability）。 - 实时系统通常又分为软实时系统和硬实时系统。软实时系统在规定时间得不到响应所产生的后果是可以承受的，如流水装配线。即使装配线瘫痪，也只是损失了资金；而硬实时系统在得不到实时响应后则可能产生不能承受的灾难，如导弹防卫系统。如果反应迟钝，结果就可能是严重损失。 - 商用实时操作系统的代表有VxWorks和EMC的DART系统。 - 第六代：现代操作系统（1980年以后） - 网络促进了网络操作系统和分布式操作系统的出现。对于网络操作系统来说，其任务是将多个计算机虚拟成一个计算机。传统的网络操作系统是在现有操作系统的基础上增加网络功能，而分布式操作系统则是从一开始就把对多计算机的支持考虑进来，是重新设计的操作系统，所以比网络操作系统效率高。分布式操作系统除了提供传统操作系统的功能外，还提供多计算机协作的功能。 - 服务器操作系统的演变从UMES开始，经CTSS演变为IBM的MVS和VM操作系统，经MulticS演变为UNIX系统。在20世纪80年代初，UNIX一分为二：由AT＆T（美国电话电报公司）提供的System系列和由UCB提供的BSD系列。XENIX为微软公司为PC机而移植的AT＆T版的UNIX操作系统。AT＆T是UNIX的鼻祖，UCB则在美国国防部的支持下开发了BSD（伯克利软件分配）系列。 - IBM和斯坦福大学看到AT＆T和UCB的UNIX软件后，也不甘示弱，分别研发了AIX和SUN OS（SUN是Stanford University Networks（斯坦福大学网络）的缩写）。这样UNIX就形成了4个系列：AT＆T的System系列、IBM的AIX系列、SUN的SUN OS系列以及UCB的BSD系列。 - 20世纪90年代中期，在美国国防部停止对BSD的支持后，UCB亦停止了BSD系列的研发，而AT＆T也在与BSD焦头烂额的较量中放弃了System系列。Linux则趁AT＆T和UCB忙于与对方较量的时候发展起来。卡内基梅隆大学（Car-negie Mellon University）在看到UCB和斯坦福大学都研发了UNIX后，慌忙开发了个MACH操作系统。MACH为微内核操作系统，在学术界得到了一定的使用，但由于其运行效率低下而没有获得商业上的广泛应用。 - 这样UNIX的商业使用版本就剩下AIX、Solaris系列（SUN OS的后续版本）和Linux系列。后来由于惠普公司（HP）加入到服务器行列使得UNIX家族又增加了一个版本：HP-UX。在UNIX家族中，SUN公司濒临灭亡的命运令Solaris的前途堪忧。 - 从UNIX的1400行代码到Windows XP的4000万行代码，这完全是一种爆炸式增长。而爆炸式增长的后果就是，操作系统设计已经变得极为复杂和困难。以致商用操作系统在关键机制的实现上都或多或少地进行了偷工减料，从而严重影响了操作系统的稳定性。 - 规模的庞大使得没有什么人能够完全理解一个完整的操作系统，而这种状况同样将限制操作系统的可靠性、可用性和安全性。这迫使我们不得不思考：操作系统能在复杂性和规模不断增加的情况下保持正确性和可靠性吗？它能在今天的云计算时代取得突破，而达到我们所祈望的“操作系统奇异点”（OS singularity）吗？ ## 第3章 操作系统基本概念 - 数学是一门严谨的学科，一切都以精确为追求（这里是指纯数学，不包括那些不被认为是数学的应用数学）。而软件却没有任何精确可言，是十足的“差不多”学科。因为软件是一门人造学科，它没有对与错（这里指的是同一功能的不同实现，而不是说程序不可能出现错误），只有好或坏。我们设计软件的时候，也是觉得差不多就可以了，而没有什么精确的追求。 - 计算机的结构非常简单：首先布置一根总线，然后将各种硬件设备挂在总线上。所有的这些设备都有一个控制设备，外部设备都由这些控制器与CPU通信。而所有设备之间的通信均需通过总线， - 内核态就是拥有资源多的状态，或者说访问资源多的状态，称为特权态。相对来说，用户态就是非特权态，在此种状态下访问的资源将受到限制 - 内核态和用户态各有优势：运行在内核态的程序可以访问的资源多，但可靠性、安全性要求高，维护管理都较复杂；用户态程序程序访问的资源有限，但可靠性、安全性要求低，自然编写维护起来比较简单。一个程序到底应该运行在内核态还是用户态则取决于其对资源和效率的需求。 - 为了赋予内核态程序访问所有资源的权限，当系统处于内核态时，内核程序可以绕过内存地址翻译而直接执行特权指令，如停机指令。这种绕过翻译的做法突破了系统对资源的控制。 - 微内核结构，即只将操作系统核心中的核心放在内核态运行，其他功能都移到用户态运行。 - 卡内基梅隆大学开发的MACH操作系统的内核非常小，而微软公司的Windows XP的内核就大多了。 - 在任何时候，进程所占有的全部资源，包括分配给该进程的内存、内核数据结构和软资源形成一个进程核（core）。核快照（core image）代表的是进程在某一特定时刻的状态。 - 如果在Linux或UNIX操作系统下编写程序，在出现分段错误（segmentation fault）时，操作系统会自动进行核倒出（core dump）。“核倒出”把所有计算机的状态保存在一个文件中，通过阅读这个文件的内容可以得知溢出时的进程状况，从而帮助调试程序。 - 操作系统的服务是通过什么方式提供的呢？答案是系统调用（system call） - 为了向这些不编程的用户提供服务，操作系统提供了一个壳（shell）来与用户交互。每个操作系统都提供某种壳，以便与用户进行交互。这个壳是覆盖在操作系统服务上面的一个用户界面，既可以是图形界面，也可以是文本界面。用户在这个界面上输入命令，操作系统则执行这些命令。 ## 第4章 进程 - 进程在Multics操作系统出现前叫做工作（job）。工作是IBM用于多道批处理程序设计中的概念。由于历史的原因，Multics操作系统的研发人员不愿意承用IBM发明的术语，而将工作改为了进程（process）。 - 进程是其提供的一种抽象，目的是通过并发来提高系统利用率，同时还能缩短系统响应时间。 - 子进程又可以再创建子进程，这样子子孙孙创建下去就形成了所谓的进程树。UNIX称这个进程树里面的所有进程为一个进程组，进程组里面的进程分布在不同的层次上，从而形成一个层次架构。Windows没有进程组的概念，而是所有进程均地位平等。 - 那么进程挂起有哪些原因呢？首先是一个进程在运行过程中执行了某种阻塞操作，如读写磁盘。由于阻塞操作需要等待结果后才能继续执行，因此操作系统将把这个进程挂起，让其他进程运转。另外一种情况是一个进程执行的时间太长了，为了公平，操作系统将其挂起，让其他进程也有机会执行。 - 进程分为3种状态：执行、阻塞和就绪， - 一个进程只能在执行时才可能阻塞，没有执行的进程无法直接转换到阻塞状态。 - 许多商业操作系统的进程状态不止3个，例如，Windows的进程有7个状态，Solaris的进程则有6个状态。 - 操作系统用于维护进程记录的结构就是进程表或进程控制块（Process Control Block,PCB）。 - 维护的资料信息应当包括寄存器、程序计数器、状态字、栈指针、优先级、进程ID、信号、创建时间、所耗CPU时间、当前持有的各种句柄等。 - UNIX将进程创建分为两个步骤：第1步是fork，创建一个与自己完全一样的新进程；第2步是exec，将新的进程的地址空间用另一个程序的内容覆盖，然后跳转到新程序的起始地址，从而完成新程序的启动。而Windows使用一个系统调用就可以完成进程创建。这个系统调用就是CreateProcess。在调用该函数时我们把欲执行的程序名称作为参数传过来，创建新的页表，而不需要复制别的进程。 - Web服务器在每收到一个用户请求后，就创建一个新的一模一样的进程来服务用户请求。而在Windows下，复制自我就要复杂一些了。而且，共享数据只能通过参数传递来实现。 ## 第5章 进程调度 - 程序使用CPU的模式有3种：一种是程序大部分时间在CPU上执行；另一种是程序大部分时间在进行输入输出；还有一种是程序介于前两种模式之间。 - 第1种程序运行的模式是在CPU上执行较长时间，接着进行短暂的输入，然后又在CPU上进行较长的运算，之后又进行短暂的输入输出操作，就这样循环往复。这种程序由于使用CPU的时间远远长于其用于输入输出上的时间，因此称为CPU导向（CPU-bound）或计算密集型程序。 - 第2种程序则与第1种相反，这种程序的大部分时间用来I/O，每次I/O后进行短暂的CPU执行，因此称为I/O导向（I/O-bound）或输入输出密集型程序。 - 第3种程序自然介乎二者之间，既有长时间的CPU执行部分，又有长时间的I/O部分。或者说，这种程序使用CPU和I/O的时间相差不大。这种程序称为平衡型程序。 - 对于I/O导向的程序来说，响应时间非常重要；而对于CPU导向的程序来说，周转时间（turnaround）就比较重要；对于平衡型程序来说，进行某种响应和周转之间的平衡就显得重要。 - CPU调度就是要达到极小化平均响应时间、极大化系统吞吐率、保持系统各个功能部件均处于繁忙状态和提供某种貌似公平的机制。 - 极小化平均响应时间就是要极小化用户发出命令和看到某种结果之间所花费的时间，即减少做一件工作平均等待的时间；极大化系统吞吐率就是要在单位时间内完成尽可能多的程序，就是单位时间内能完成的工作数量，即整个系统运行效率高；保持系统各个功能部件繁忙就是要让CPU和输入输出设备均处于忙碌状态。 - 先来先服务调度算法缩写为FCFS（First Come First Serve）。 - 时间片轮转算法是对FCFS算法的一种改进，其主要目的是改善短程序的响应时间。其方法就是周期性地进行进程切换。 - 系统响应时间依赖于时间片的选择。 - 如果选择的时间片过大，时间片轮转将越来越像FCFS，当选择的时间片超过任何一个程序所需要的执行时间长度时，则完全退化为FCFS。而如果选择的时间片过小，则进程切换所用的系统消耗将太多，使得系统的大部分时间花在进程的上下文切换上，而用来真正执行程序的有用时间很少，从而降低系统效率，并造成浪费。 - 我们需要知道进行一次进程切换所用系统消耗和我们能够承受的整个系统消耗，就可以得出合适的时间片。例如，如果每次进程切换需要消耗0.1毫秒的CPU时间，则选择10毫秒的时间片将浪费约1%的CPU时间在上下文切换上；如果选择5毫秒的时间片，则浪费约为2%；20毫秒的时间片，则浪费约为0.5%。如果我们能够承受的CPU浪费为1%，则选择10毫秒的时间片就很合理。 - 时间片选择还需考虑的一个因素是，有多少进程在系统里运行？如果运行的进程多，时间片就需要短一些，不然，用户的交互体验会很差。进程数量少，时间片就可以适当长一些。 - 改善短任务排在长任务后面轮转而造成响应时间和交互体验下降的办法就是短任务优先（Shorted time to Completion First,STCF）算法。 - 短任务优先算法有两个变种：一种是非抢占，一种是抢占。 - 非抢占短任务优先算法的原理是让已经在CPU上运行的程序执行到结束或阻塞，然后在所有候选的程序中选择需要执行时间最短的进程来执行。抢占式短任务优先算法则是每增加一个新的进程就需要对所有进程（包括正在CPU上运行的进程）进行检查，谁的时间短，就运行谁。 - 在所有非抢占调度算法中，STCF算法的响应时间最优。而在所有抢占调度算法中，抢占式STCF算法的响应时间最优。 - STCF算法有一个缺点是可能造成长进程“饥饿”。 - 优先级调度算法的原理是给每个进程赋予一个优先级，每次需要进程切换时，找一个优先级最高的进程进行调度。这样，如果赋予长进程一个高优先级，则该进程就不会再“饥饿”。 - STCF算法本身就是一种优先级调度，只不过它给予短进程高优先级而已。 - 在一个进程执行特定CPU时间后将其优先级降低一个级别，或者将处于等待进程的优先级提高一个级别。这样，一个进程如果等待时间很长，其优先级将因持续提升而超越其他进程的优先级，从而得到CPU时间。这样，“饥饿”现象就可以防止。 - 混合调度算法。该算法的原理是将所有进程分成不同的大类，每个大类为一个优先级。如果两个进程处于不同的大类，则处于高优先级大类的进程优先执行；如果两个进程处于同一个大类，则采用时间片轮转来执行。 - 实时系统是一种必须提供时序可预测性的系统。 - 最经典的两种算法：动态优先调度和静态优先级调度。动态优先级调度又称为最早截止任务优先（Earliest Deadline First,EDF）算法，而静态优先级调度又称为最短周期优先（Rate Monotonic Scheduling,RMS）算法。 - EDF调度算法就是最早截止的任务先做。如果新的工作来了，比正在运行的程序的截止时间更靠前，那么就抢占当前进程。EDF调度算法是实时调度里面的最优算法。如果一组任务可以被调度的话（指所有任务的截止时间在理论上能够满足），则EDF可以满足。一批任务如果不能全部满足，那么EDF能满足的任务数最多。这就是它最优的体现。 - EDF调算算法就是STCF算法变化来的。如果将STCF算法的任务所需执行时间变为截止时间，则抢占式STCF算法就是EDF调度算法。 - EDF算法在理论上是最优的，但动态计算截止时间和动态抢占CPU均要消耗系统资源，因此EDF算法实际效果比其理论效果要差一截。 - RMS调度算法。该算法在进行调度前先计算出所有任务的优先级，然后按照计算出来的优先级进行调度，任务执行中间既不接收新的进程，也不进行优先级的调整或进行CPU抢占。因此这种算法的优点是系统消耗小，缺点是不灵活。一旦该系统的任务决定了，就不能再接收新的任务。 - 如果一个系统里所有任务的CPU的利用率低于ln 2，则这些任务的截止时间均可以得到满足。 - RMS算法为静态最优算法。即如果任何静态优先级算法可以满足一组任务的截止时间，则RMS算法也必能满足。 - 调度进程时操作系统所执行的操作概览：因时序或外部中断或进程挂起而导致操作系统获得CPU控制权。操作系统在所有就绪的进程中按照某种算法遴选进程。如果选中的是非当前进程，则操作系统将当前进程（中断或挂起的进程）状态予以保护。将选中的进程的环境布置好（设置寄存器、栈指针、状态字等）。跳转到选中的进程。 - 优先级倒挂则可能引起严重后果。如果一个高优先级进程一直不能获得资源，有可能造成系统故障，或激发事先定义的纠正措施，如系统复位。例如，美国的火星探测器Mars Path-finder就是因为优先级倒挂而出现故障。 - 如果高优先级进程在等待资源时不是阻塞等待，而是循环（繁忙）等待，则它将永远无法获得所需资源。 - 使用中断禁止 - 通过禁止中断来保护临界区。在采用此种策略的系统中只有两个优先级：可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区进程的优先级。 - 在多CPU环境下，由于不能使用中断禁止，因此使用一个简单的变种：单一共享标志锁。该方法在共享内存里面提供一个单一标志。所有CPU在进入跨CPU临界区时都必须先获得该标志。这个标志在有的操作系统里面称为旋锁。 - 优先级上限（priority ceiling） - 让共享的临界区有自己的优先级，并让访问临界区的进程获得临界区的优先级。这样，只要临界区的优先级设置得足够高，就可以避免优先级倒挂。（因为获得资源的进程具有的将是高优先级！） - 优先级继承（priority inheritance） - 当一个高优先级进程等待一个低优先进程所持有的资源时，这个低优先级进程将暂时获得高优先级进程的优先级别。这样就能防止一个中间优先级的进程抢占低优先级进程而延长资源占用时间，同时也防止了因高优先级进程自身进行繁忙等待可能导致的死锁。 ## 第6章 进程通信 - 管道是一个线性字节数组，类似文件，可以使用文件读写的方式进行访问。但却不是文件。因为通过文件系统看不到管道的存在。 - 管道可以设在内存里 - 记名管道与文件系统共享一个名字空间，即我们可以从文件系统中看到记名管道。也就是说，记名管道的名字不能与文件系统里的任何文件名重名。 - 允许有多个同一命名管道的实例并且可以由不同的进程打开，但是不同的管道都有属于自己的管道缓冲区而且有自己的通信环境，互不影响。 - 信号就是一个内核对象，或者说是一个内核数据结构。发送方将该数据结构的内容填好，并指明该信号的目标进程后，发出特定的软件中断。操作系统接收到特定的中断请求后，知道是有进程要发送信号，于是到特定的内核数据结构里查找信号接收方，并进行通知。接到通知的进程则对信号进行相应处理。 - 在计算机里，信号量实际上就是一个简单整数。一个进程在信号变为0或者1的情况下推进，并且将信号变为1或0来防止别的进程推进。当进程完成任务后，则将信号再改变为0或1，从而允许其他进程执行。需要注意的是，信号量不只是一种通信机制，更是一种同步机制。 - 信号量实际上就是一个简单整数。一个进程在信号变为0或者1的情况下推进，并且将信号变为1或0来防止别的进程推进。当进程完成任务后，则将信号再改变为0或1，从而允许其他进程执行。 - 信号量不只是一种通信机制，更是一种同步机制。 - 共享内存的缺点是管理复杂，且两个进程必须在同一台物理机器上才能使用这种通信方式。共享内存的另外一个缺点是安全性脆弱。因为两个进程存在一片共享的内存，如果一个进程染有病毒，很容易就会传给另外一个进程。 - 使用全局变量在同一个进程的进程间实现通信不称为共享内存。 ## 第7章 线程 - 于线程是在进程的基础上产生的概念（进程里面的一个执行序列），其调度可以由进程负责。当然，我们也可以将线程的调度交给操作系统。而这两种不同的调度推手就形成了线程的两种实现：用户态实现和内核态实现。 - 进程是在CPU上实现并发（多道编程），而CPU是由操作系统管理的，因此，进程的实现只能由操作系统内核来进行，而不存在用户态实现的情况 - 线程是进程内部的东西，当然存在由进程直接管理线程的可能性。因此，线程存在着内核态与用户态两种实现可能。 - 那么在用户态如何进行线程调度呢？那就是用户自己写一个执行系统（runtime system）作调度器，即除了正常执行任务的线程外，还有一个专门负责线程调度的线程。由于大家都在用户态下运行，谁也不比谁占优势，要想取得CPU控制权只能靠大家的自愿合作。一个线程在执行完一段时间后主动把资源释放给别人使用，而在内核态下则无须如此。因为操作系统可通过周期性的时钟中断把控制权夺过来。在用户态实现情况下，执行系统的调度器（runtime scheduler）也是线程，没有能力强行夺走控制权，所以必须合作。 - 如果在执行过程中一个线程受阻，它将无法将控制权交出来（因为受阻后无法执行交出CPU的指令了），这样整个进程都无法推进。操作系统随即把CPU控制权交给另外一个进程。这样，一个线程受阻造成整个进程都受阻，我们期望通过线程对进程实施分身的计划就失败了。这是用户态线程的致命弱点。 - 线程阻塞造成整个进程阻塞，解决的办法只有两种：一是不让线程阻塞；二是阻塞后想办法激活同一进程的另外线程。 - 进程阻塞后想办法激活受阻进程的其他线程。这种办法的实现必须依赖操作系统。因为线程阻塞后，CPU控制权已经回到操作系统手里。而要激活受阻进程的其他线程，唯一的办法是让操作系统在进行进程切换时先不切换，而是通知受阻的进程执行系统（即调用执行系统），并问其是否还有别的线程可以执行。如果有，将CPU控制权交给该受阻进程的执行系统线程，从而调度另一个可以执行的线程到CPU上。这种做法被称为调度器激活（scheduler activation）。 - 我们将这种做法称为“第二机会”。因为在一个进程挂起后，操作系统并不立即切换到别的进程，而是给该进程第二次机会，让其继续执行。如果该进程只有一个线程，或者其所有线程都已经阻塞，则控制权将再次返回给操作系统。而这次，操作系统就会切换到别的进程了。 - 做法还存在一个更为严重的缺陷：这种操作系统调用用户态执行系统的做法违反了我们所遵循的层次架构原则。因为这种调用属于所谓的up-call，即下层功能调用了上层功能（操作系统在下，执行系统在上）。 - 鉴于用户态和内核态的线程模型都存在缺陷，因此现代操作系统将二者结合起来使用。用户态的执行系统负责进程内部线程在非阻塞时的切换；内核态的操作系统负责阻塞线程的切换。即我们同时实现内核态和用户态线程管理。其中内核态线程数量较少，而用户态线程数量较多。每个内核态线程可以服务一个或多个用户态线程。 - 用户态线程被多路复用到内核态线程上。例如，某个进程有5个线程，我们可以将5个线程分成两组，一组3个线程，另一组2个线程。每一组线程使用一个内核线程。这样，该进程将使用两个内核线程。如果一个线程阻塞，则与其同属于一组的线程皆阻塞，但另外一组线程却可以继续执行。 - 可将需要执行阻塞操作的线程设为内核态线程，而不会执行阻塞操作的线程设为用户态线程。 - 线程的机制非常类似于硬件的流水线机制。流水线也是提供并发，不过是指令级的（而不是程序级的）。并发当然提高了计算机的吞吐率，改善了用户响应时间。但问题是，在多流水线多梯级情况下，由于有许多指令同时在不同的流水线和梯级上执行，其之间存在的数据和指令依赖关系十分复杂。如果万一再发生异常，如何保存一个一致性的状态都成了问题。 - 线程与流水线分别是软件层和硬件层不确定性的根源。流水线使得我们可以在硬件指令执行上并发，线程则使我们在软件指令执行上并发。但其带来的操作系统、编译系统和指令集结构的高度复杂是否值得，也许并不容易回答。 ## 第8章 线程同步 - 一般情况下，在任何计算机体系结构中，x=1对应的不是一条微指令，即一条高级指令对应的是多条微指令，因此一条高级指令需要多个时钟周期（通常为6个时钟周期以上）才能完成。 - 任何时刻都只能有一个人在临界区里，这称为互斥（mutual exclusion）。 - 正确互斥需要满足4个条件：不能有两个进程同时在临界区里面。进程能够在任何数量和速度的CPU上正确执行。在互斥区域外不能阻止另一个进程的运行。进程不能无限制地等待进入临界区。 - 一把正常锁所应该具备的特性：锁的初始状态是打开状态。进临界区前必须获得锁。出临界区时必须打开锁。如果别人持有锁则必须等待。 - sleep和wakeup就是操作系统里的睡觉和叫醒操作原语。 - 消费者先来，这个时候count=0，于是去睡觉，但是在判断count等于0后并且在执行sleep语句前CPU发生切换，生产者开始运行，它生产一件商品后，给count加1，发现count结果为1，因此发出叫醒消费者信号。但这个时候消费者还没有睡觉（正准备要睡），所以该信号没有任何效果，浪费了。而生产者一直运行直到缓冲区满了后也去睡觉。这个时候CPU切换到消费者，而消费者执行的第1个操作就是sleep，即睡觉。至此，生产者和消费者都进入睡觉状态，从而无法相互叫醒而继续往前推进。系统死锁发生。 - 造成二者同时睡觉的原因是生产者发出的叫醒信号丢失（因为消费者此时还没睡觉）。 - 在消费者获得CPU并执行sleep语句后，生产者在这之前发送的叫醒信号还保留，因此消费者将马上获得这个信号而醒过来。而能够将信号累积起来的操作系统原语就是信号量。 - 信号量（semphore）可以说是所有原语里面功能最强大的。它不仅是一个同步原语，还是一个通信原语。而且，它还能作为锁来使用！ - 信号量就是一个计数器，其取值为当前累积的信号数量。它支持两个操作：加法操作up和减法操作down - down和up操作在历史上被称为P和V操作。P和V指的是荷兰语里prob-eren和verhogen两个单词，分别表示减少和增加的意思。 - 如果将信号量的取值限制为0和1两种情况，则获得的就是一把锁，也称为二元信号量（binary semaphore） - 由于二元信号量的取值只有0和1，因此上述程序防止任何两个程序同时进入临界区。二元信号量还可以用来管理线程的执行顺序， - 二元信号量从某种意义上说就是锁和睡觉与叫醒两种原语操作的合成。 - 管程的英文单词是monitor，即监视器的意思。它监视的就是进程或线程的同步操作。 - 即将需要保护的代码置于begin monitor和end monitor之间，即可获得同步保护。在任何时候只能有一个线程活跃在管程里面。那谁来保证这一点呢？编译器。 - 管程就是锁加上条件变量。 - 条件变量就是线程可以在上面等待的东西，而另外一个线程则可以通过发送信号将在条件变量上的线程叫醒。 - 管程的中心思想是运行一个在管程里面睡觉的线程。但是在睡觉前需要把进入管程的锁或信号量释放，否则在其睡觉后别的线程将无法进入管程，就会造成死锁。 - 管程里面的两个操作wait和signal的语义分别如下：wait（x）以原子操作完成下述3个步骤：1）释放锁。2）将本线程挂在条件变量x的等待队列上。3）睡觉，等待被叫醒。 - signal则与我们前面讲过的一样，将等在指定条件变量上面的第1个线程叫醒。在叫醒方面，管程还提供另外一个所谓的广播（broadcast）原语，其语义是将指定条件变量上面的所有等待线程全部叫醒。 - 进入管程需要获得该管程的锁（由编译器提供），因此，在一个准备等待的线程真正进入等待之前，由于其持有的管程锁尚未释放，另外的线程是无法执行管程里面的任何代码的。而在锁释放之时，相关线程已经进入等待状态。此时如果一个线程发送信号，自然将接收到，而不会丢失。 - 管程只有一把锁。如果两个线程同时活跃，那谁将持有管程的锁呢？ - 叫醒者继续持有锁，并在离开管程时将锁释放，此时被叫醒者将获得管程的锁，从而可以继续执行。 - 第2种办法是赋予被叫醒者优先级，即在发送signal时同时释放锁，让被叫醒者获得锁。从而在signal后，第1个运行的线程将是被叫醒的线程。叫醒者只能在被叫醒者运行完毕或由于其他原因释放锁之后才能继续运行。由于这种方式是HOARE提出的，因此这种给予被叫醒者优先的管程称为HOARE管程。 - 两种方法都是在管程设计时就确定了谁将有优先权：前者将优先权赋予叫醒者，后者则将优先级赋予被叫醒者。这两种方法因为都是在管程设计时就确定了，十分不灵活，它们限制了操作系统的作用。 - 我们希望下一步执行哪个线程由操作系统决定。即让两个线程竞争这把锁。这样，操作系统就可以在竞争中发挥作用，使用各种机制动态地调整每个线程获取锁的优先级。这种管程就称为MESA管程。 - MESA管程的signal处理方式如下：叫醒者在发出signal后释放锁；被叫醒者与叫醒者同时竞争这把锁。谁先获得锁，谁先执行。 - 管程只能在单台计算机上发挥作用。如果想在多计算机环境下（或者网络环境下）进行同步，那就需要其他机制了。这种其他机制就是消息传递。 - 消息传递是通过同步双方经过互相收发消息来实现。它有两个基本操作，发送send和接收receive。它们均是操作系统的系统调用，而且既可以是阻塞调用，也可以是非阻塞调用。 - 生产者和消费者就这样通过消息的传送进行同步，既不会死锁，也不会繁忙等待。而且，无须使用临界区等机制。更为重要的是，它可以跨计算机进行同步，即可以对处于不同计算机上的线程实现同步。由于这些优点，消息传递是当前使用非常普遍的线程同步机制。（当然，它更是一种通信机制，记得前面讲过的消息队列吗？）。 - 栅栏就是一个障碍。到达栅栏的线程必须停止下来，直到除去栅栏后才能往前推进。 ## 第9章 死锁应对之哲学原理 - 如果有一组线程，每个线程都在等待一个事件的发生，而这个事件只能由该组线程里面的另一线程发出，则称这组线程发生了死锁。 - 锁的发生必须满足4个条件 - 条件1：死锁发生的必要条件是资源有限。即一个系统里面的资源数量有限，以致无法同时满足所有线程的资源需求。 - 条件2：死锁的另外一个必要条件是持有等待。即一个线程在请求新的资源时，其已经获得的资源并不释放，而是继续持有。 - 条件3：死锁的另外一个条件是不能抢占。如果可以抢占一个资源，则也不会发生死锁。 - 条件4：就是我们已经提过的循环等待条件。这是死锁的最后一个条件。如果你等我、我等你，大家都这样等着对方，就产生了死锁。这时如果画出系统里线程的资源占用和请 - 从哲学角度来说，世界上本没有问题，是你认为有问题，才有问题。学生考试不及格，要补考；补考也不及格，毕不了业。毕不了业是问题吗？当然不是。只有你认为是问题时它才是问题。 - 防止死锁的代价很高，防止死锁比重启100次代价还高，因此不如直接重启。如果死锁发生，重启即可。这就是为什么Windows、Linux和其他商业操作系统都没有采取死锁防止措施 - 一种效率较高的算法是利用矩阵。这种算法用到两个矩阵：一个叫资源分配矩阵，另一个叫资源等待矩阵。矩阵的每一行代表一个线程，每一列代表一种资源。在资源分配矩阵中，行列交叉的数值代表该线程已经拥有该资源的数量；在资源等待矩阵中，行列交叉的数值代表特定行还需要特定资源的数量。 - 除此之外，我们还维持两个矢量：一个系统资源总量矢量，表示系统中所有资源的总数是多少；另一个是系统当前可用资源矢量，代表系统现在还有多少可用的资源， - 先考虑什么时候发生死锁？每个线程都不能推进。什么时候不能推进？就是要求的资源不能满足。你把可用的资源拿来与资源等待矩阵的每一行进行比较，你就知道谁不能满足。如果减出来，每一个线程都有负数，那就是发生了死锁。 - 死锁的检测已经实现了，那怎么从死锁状态恢复呢？ - 首先可以抢占。即将某个线程所占的资源强行拿走，分配给别的线程。当然了，被抢占的线程很有可能不能正确运行。不过这就是纠正死锁的代价。这种策略的一个重要考虑是选择哪个线程作为牺牲品，而这往往不是容易做出的决策。 - 另外一个选择是更进一步，不只是抢占某个线程的资源，而是将整个线程“杀掉”。 - 最后一个办法是上翻（rollback），即将整个系统翻转到过去的某个状态，大家从那个状态重新来过。那么这就要定期记录系统。这是一件很麻烦的事情。对于一个负责的系统来说，上翻到一个可靠的状态十分困难。而且，更为重要的是，系统并不是在任何时候都可以上翻的。 - 检测与恢复两个部分都存在巨大困难。 - 使用资源分配与等待矩阵来判断死锁是否可靠？如果减运算后每一项都有负数，死锁是不是就真的发生了？答案是否定的。这种判断只能说是死锁有可能发生，但并不能肯定死锁会发生。因为也许某个线程因某种原因突然退出，从而不会发生死锁。 - 有n个线程，有可能你有几个线程已经死锁了，但是有的线程还能推进。 - 第2个问题是，这个矩阵可能是一个巨大的矩阵。如果是多用户的话，线程数可能不计其数。因此，这个矩阵有可能非常大。 - 这种策略最致命的问题是，检查死锁的线程自己发生了死锁。 - 检查死锁的线程自己发生了死锁。此时，死锁检查程序已经无法推进，自然无法检查死锁是否发生。 - 既然这种策略存在诸多弊端，那只能走另一条路，即不让死锁发生！ - 死锁防治的第3种策略：动态避免。 - 进行动态避免的原则也很简单：在每次进行资源分配时，必须经过仔细计算，确保该资源请求批准后系统不会进入死锁或潜在的死锁状态。潜在的死锁状态指的是尚未发生死锁的状态，但接下来的执行将一定产生死锁，因此这种状态又称为“不安全状态”，与之相对的状态称为安全状态。 - 安全状态是指从该状态开始，我们能够找到一种资源分配方法和顺序，使得所有线程都能获得其需要的资源，从而不会产生死锁。而不安全状态则是从该状态开始，无论我们怎样，也不能找到一种资源分配方法和顺序来满足所有线程的资源需求。 - 死锁动态避免的策略就很简单了，就是要防止系统进入不安全状态。手段就是每次需要进行资源分配时，就计算一下该分配是否会将系统带入不安全状态。如果是，就否决相关资源请求；否则，就批准。 - 死锁的静态防止。这个策略的中心思想是清除死锁发生的土壤，而死锁发生的土壤就是死锁的4个必要条件。如果消除死锁发生的4个必要条件中的任何一个，则死锁将无法发生。 - 消除资源独占条件 - 消除这个条件有两个办法，将资源无限增加或把所有资源变为共享。 - 有的资源看上去是独占资源，但却可以通过间接来实现共享，例如磁盘和打印机。对于打印机来说，我们不允许任何线程直接占有，而是设计一个“精灵”程序daemon来管理。 - 消除保持和请求条件 - 一个线程必须一次请求其所需要的所有资源，而不是一般情况下的请求一点资源，做一点事情； - 一次将所有资源拿齐，太过浪费。 - 就是在一开始就需要知道一个线程所需要的所有资源，这是很困难的。 - 消除非抢占条件 - 允许抢占资源。也就是说可以从一个线程手上将资源抢夺过来。典型的例子有CPU和内存空间。一个线程可以将CPU或内存空间从另一个线程手上抢过来，从而避免了因CPU和内存空间的竞争而造成死锁。而这恰恰是操作系统里面CPU调度和内存管理的一个重要功能。 - 策略也有局限性。因为不是所有的资源都可以被抢占而不产生不良后果。例如，锁就不能抢占。 - 消除循环等待条件 - 出现循环等待是因为线程请求资源的顺序是随机的 - 按顺序请求资源 - 银行家算法是一个动态避免死锁算法，通过对资源的仔细分配以避免死锁。其特点是可以超额批准客户的信用额度，即所有客户的信用额度之和可以超过银行的全部资本，这就是杠杆（leverage）。 - 在应对死锁的策略上，我们讲解了4种策略：静态防止、动态避免、不予理睬和检测修复。用人口控制来作比喻，就是不控制婴儿的出生；允许生育，但想办法处理出生的婴儿；不准结婚来静态防止生育和可以结婚但不许生育来进行动态避免。 - 死锁实际上就是饥饿。对于处于饥饿状态的线程来说，它因为无法往前推进， - 饥饿还有另外一种特例：活锁。在活锁状态下，处于活锁线程组里的线程状态可以改变，但是整个活锁组的线程无法推进。 ## 第10章 锁的实现 - 实际上，闭锁操作在编程微指令后，根本不止两个步骤，而是十几个甚至更多步骤。事实上，所有同步原语在微指令级都是由多个步骤构成。那操作系统是如何保证这些同步原语的原子性呢？即在执行同步原语的中途是怎么防止别的进程或线程插入执行呢？ - 操作系统之所以能够构建锁之类的同步原语，原因就是硬件已经为我们提供了一些原子操作：中断禁止和启用（inter-rupt enable/disable）、内存加载和存入（load/store）和测试与设置（test＆set）指令。禁止中断这个操作是一个硬件步骤，中间无法插入别的操作。 - 在这些硬件原子操作之上，我们便可以构建软件原子操作：锁、睡觉与叫醒、信号量等。 - 要切换进程，必须发生上下文切换，而发生上下文切换只能有两种可能：一是一个线程自愿放弃CPU而将控制权交给操作系统调度器，从而发生上下文切换；二是一个线程被强制放弃CPU而失去控制权。自愿放弃通过调用yield之类的操作系统系统调用来实现；而强制放弃则需通过中断来实现，操作系统主要是通过周期性的时钟中断来获得CPU控制权的。 - 闭锁的第一个操作是禁止中断，记住，这是一个硬件原子操作。如果成功禁止了中断，接下来就检查value是否等于FREE，如果是，就表明这个资源没有被其他进程占用，我们就将其设置为忙，然后启用中断（记住，这也是一个硬件原子操作）。这样就完成了闭锁操作。 - unlock的操作就是首先禁止中断，将value设为FREE，再启用中断， - 现代处理器基本上都提供一条所谓的“读-修改-写入”的原子指令，该操作以不可分割的方式执行如下两个操作：1）将内存指定位置的存储单元的内容读到一个寄存器。2）将新的值写入刚才的内存单元。 - 改善的思路是不进行繁忙等待，而是在拿不到锁的时候去睡觉，等待别人的叫醒。这样，锁的实现思路如下：1）使用中断禁止，但不进行繁忙等待。2）如果拿不到锁，等待进程放弃CPU并进入睡觉状态，以便持有锁的进程可以更好地运行。3）当锁释放的时候将睡觉进程叫醒。 - 问题是，切换到别的进程的语句在启用中断指令前执行，由于切换到另一个进程后，该程序就无法再执行，那么后面的中断启用指令自然就不能执行了。 - 我们要求所有线程遵守下列约定：所有线程承诺在调用线程切换时将中断留在禁止状态。所有线程承诺在从切换返回时将中断重新启用。 - 显然，这是一个危险的系统。因为所有操作系统的系统调用都必须遵守一个约定，即在进入系统调用前必须禁止中断，而在返回到用户代码前则必须启用中断。而这将依赖于各个系统调用之间的自愿配合。这里无法强制。因此，这个机制对系统调用设计者的技术水平和信用都有很大的依赖。 - 在单处理器上，如果禁止了中断，自然别的线程就无法获得CPU控制权。但在多CPU情况下，即使禁止了某个CPU的中断，另一个CPU却可以继续执行， - test＆set是针对内存单元的，多CPU有全局内存，所以能够工作。 ## 第11章 基本内存管理 - Windows NT里面的"NT"不是新技术New Technology的缩写，而是《新约》New Testament的缩写。因为对于微软来说，这是它与世人定的“新约”，而世人都将不得不按照这个“新约”行事 - 内存管理要达到如下两个目标：地址保护：一个程序不能访问另一个程序地址空间。地址独立：程序发出的地址应与物理主存地址无关。 - 虚拟内存要提供的就是一个空间像磁盘那样大、速度像缓存那样高的主存储系统。 - 在运行前即将物理地址计算好的方式叫做静态地址翻译。 - 在程序运行时进行地址翻译，这种翻译称为动态地址翻译 - 多道编程下的内存管理策略有两种：固定分区和非固定分区。 - 非固定分区的思想很简单：除了划分给操作系统的空间外，其余的内存空间是作为一个整体存在的。当一个程序需要占用内存空间时，就在该片空间里面分出一个大小刚刚满足程序所需的空间； - 最简单的方式是数据和栈往一个方向增长。这种模式下，我们事先给数据部分和栈部分分别留下增长空间。 - 那还有没有别的办法呢？有，给该程序换一个空间。就是当一个程序所占空间不够时，我们将其倒到磁盘上，再加载到一片更大的内存空间。这种将程序倒到磁盘上，再加载进内存的管理方式称为交换（swap）。 - 交换就是将一个进程从内存倒到磁盘上，再将其从磁盘上加载到内存中的过程。这种交换的主要目的是为程序找到一片更大的空间，从而防止一个程序因空间不够而崩溃。交换的另一目的，是实现进程切换，也就是将一个程序暂停一会儿，让另一个程序运行。不过使用交换进行进程切换的成本颇高，一般不这样做。 - 如果一个程序超过了物理内存，还能运行吗？答案也许出乎意料。能。这个办法就是所谓重叠（overlay）。重叠就是将程序按照功能分成一段一段功能相对完整的单元。一个单元执行完后，再执行下一个单元，而一旦执行到下一个单元，就不会再执行前面的单元。所以我们可以把后面的程序单元覆盖到当前程序单元上。这样就可以执行一个比物理内存还要大的程序。 - 在管理内存的时候，操作系统需要知道内存空间有多少空闲。 - 第1种办法是给每个分配单元赋予一个字位，用来记录该分配单元是否闲置。 - 另外一种办法是将分配单元按是否闲置链接起来，这种办法称为链表表示法。 - 从可靠性上看，位图表示法没有容错能力。如果一个分配单元为1，你并不能肯定它应该为1，还是因为错误变成1的。因为链表有被占空间和闲置空间的表项，可以相互验证，具有一定的容错能力。 ## 第12章 页式内存管理 - 分页似乎就是我们解决交换缺陷的“不二法门”。 - 分页系统要能够工作的前提是：对于任何一个虚拟页面，系统知道该页面是否在物理内存中，如果在的话，其对应的物理页面是哪个；如果不在的话，则产生一个系统中断（缺页中断），并将该虚页从磁盘转到内存，然后将分配给它的物理页面号返回。 - 分页系统的核心是页面的翻译，即从虚拟页面到物理页面的映射。而这个翻译过程由内存管理单元（MMU）完成。 - 内存管理单元对虚拟地址的翻译只是对页面号的翻译，即将虚拟页面号翻译成物理页面号。 - 对于每个程序，内存管理单元都为其保存一个页表，该页表中存放的是虚拟页面到物理页面的映射。 - 对于32位寻址的虚拟地址，如果页面大小为4KB，则虚拟页面数最多可以达到220，即1048576个虚拟页面。那么页表的记录条数就为1048576条。 - 页表除了提供虚拟页面到物理页面的映射外，还记录这些相关信息。页表的一个记录所包括的内容如图12-6所示。[插图]图12-6 页表记录内容举例 - 缺页中断服务程序将负责在磁盘上找到需要的虚拟页面，并在物理内存里面寻找一个闲置的页面来存放该虚拟页面，然后更新页表。 - 分页系统也存在缺点。第一个缺点就是页表很大，占用了大量的内存空间。 - 既然一个程序可以分解为一个个页面，并将部分页面存放在磁盘上而降低其内存占用空间，页表也可以采用同样的方式处理，即将页表分为一个个页面，不需要的页面也放在磁盘上。 - 在多级页表结构下，页表根据存放的内容可分为：顶级页表、一级页表、二级页表、三级页表等。顶级页表里面存放的是一级页表的信息，一级页表里面存放的是二级页表的信息，以此类推，到最后一级页表存放的才是虚拟页面到物理页面的映射。 - 多级页表有什么缺点呢？它降低了系统的速度。因此每次内存访问都变成多次内存访问。对于二级页表，一次内存访问变成了三次内存访问。如果次级页表不在内存，还需要加上一次磁盘访问。 - 反转页表存放的是物理页面到虚拟页面的映射。这样，由于物理内存比虚拟内存小很多，页表的尺寸将大为减少。 - 由于反转页表存放的是物理地址到虚拟地址的映射，而CPU发出的地址却是虚拟地址，这就造成页表查找困难。不过，这个问题可以通过散列来解决，即将虚拟页号散列到物理页号，然后以这个散列出来的物理页号作为索引在反转页表里面查找。 - 即在一段时间内，程序所要访问的地址空间有一定的空间局域性。如果一个页面被访问，则该页面的其他地址可能也将被随后访问。这样，我们可以将该页面的翻译结果存放在缓存里，而无须在访问该页面的每个地址时再翻译一次。 - 这种存放翻译结果的缓存称为翻译快表（Translation Look-Aside Buffer,TLB）。 - 由于TLB里面不能按虚拟页面号进行索引，唯一的办法是一个记录一个记录地按顺序查找 - 搜索TLB所花费的时间可能已经远远超过查找多级页表所花的时间了。 - 哲学原理：软件没有办法构建原子操作，只能把硬件请出来。在这里，我们看到，软件没有办法在以一次内存访问完成TLB查找，到这里卡住了。解决方案就是使用硬件。 - 解决方案就是使用硬件。我们在TLB里面进行的比较不是一个个地顺序比较，而是同时比较，即将所有的TLB记录与目的虚拟地址同时比较，因此只需要一次查找就能确定一个虚拟页面号是否在TLB里。这种设计需要同时配备多套比较电路，比较电路的套数需与TLB的大小一样。这也就是为什么TLB非常昂贵。 - 有时我们需要把页面锁在内存，不想被交换出去。 - 在更换页面时，如果更换的页面是一个很快就会被再次访问的页面，则在此次缺页中断后很快又会发生新的缺页中断。在最坏情况下，每次新的访问都是对一个不在内存的页面进行访问，即每次内存访问都产生一次缺页中断，这样每次内存访问皆变成一次磁盘访问，而由于磁盘访问速度比内存可以慢一百万倍，因此整个系统的效率急剧下降。这种现象就称为内存抖动， - 发生内存抖动时，系统的效率将与停滞差不多，几乎看不到任何进展的迹象。 - 如果页面不断地换出去调进来，CPU的资源将完全耗费在缺页中断上，无法进行任何有效工作。用户体验到的就是计算机停止了工作，而硬盘灯一直亮着。 - 通过减少同时运行的程序个数而使得每个程序都有足够的资源来运行而不产生抖动。例如，我们可以把其中一些进程全部交换到磁盘上，把空出来的空间给其他尚在内存的进程使用。这种降低多道编程度数的做法也称为负载平衡。 ## 第13章 页面更换算法 - 页面更换时挑选替换页面的目标是什么呢？当然是降低随后发生缺页中断的次数或者概率。因此，我们选择的页面应当是在随后相当长时间内不会被访问的页面。最好是再也不会被访问的页面。同时，如果可能，我们应该选择一个没有修改过的页面。这样，替换时就无须将被替换页面的内容写回磁盘，从而进一步加快缺页中断的响应速度。 - 有的算法都归结为两个大类的一类：公平算法非公平算法 - 平算法主要包括下面4种：随机算法先来先出（FIFO）算法第二次机会算法时钟算法非公平算法则包括如下5种：最优算法NRU算法LRU算法工作集算法 - FIFO只考虑进入内存的时间，不关心一个页面被访问的频率，从而有可能造成替换掉一个被经常访问的页面而造成效率低下。 - 在使用FIFO更换一个页面时，需要看一下该页面是否在最近被访问过。如果没有被访问过，则替换该页面。如果该页面在最近被访问过（通过检查其访问位的取值），则不替换该页面，而是将该页面挂到链表末端，并将该页面进入内存的时间设置为当前时间，并将其访问位清零。 - 在时钟算法里，我们把页面排成一个时钟的形状。该时钟有一个针臂。每次需要更换页面时，我们从针臂所指的页面开始检查。如果当前页面的访问位为0，即从上次检查到这次，该页面没有被访问过，将该页面替换。如果当前页面被访问过，那就将其访问位清零，并顺时针移动指针到下一个页面。我们重复这些步骤直到找到一个访问位为0的页面。 - 既然时钟算法的精髓就是第二次机会算法，其缺点就和第二次机会算法一样：过于公平，没有考虑到不同页面调用频率的不同，有可能换出不应该或不能换出的页面，还有可能造成无限循环。 - 在非公平的算法里面，最理想的页面替换算法是选择一个再也不会被访问的页面进行替换。如果不存在这样的页面，那至少选择一个在随后最长时间内不会被访问的页面进行替换。 - 第二次机会算法选择的是最先进入内存且访问位为0的页面进行替换。改进的办法就是选择一个最近没有被访问的页面来替换，但在所有的最近没有使用的页面里，不是按照最先进入来划分，而是按照各个页面的修改位和访问位的组合来进行划分。这种算法称为最近未使用算法（Not Recently Used,NRU）。 - 对NRU算法的改进就是LRU算法。LRU算法是最近使用最少算法（LeastRecently Used）。 - 它不一定保证是最近最少使用的页面被选中。最少被使用可以肯定，但“最近”则不一定。因为计数器记录的时间段不一定是最近。 - LRU算法的另一种简单实现方式是用一个链表将所有页面链接起来，最近被使用的页面在链表头，最近未被使用的放在链表尾。 - 这两种简单的LRU算法实现方法都存在明显的缺点。每次内存访问都对链表进行更新效率十分低下 - 比起链表或页表来实现，使用矩阵实现LRU算法就要好不少。 - 该矩阵为n×n维，n是相关程序当前驻内存的页面数。在一开始矩阵的初值为0。每次一个页面被访问时，例如第k个虚拟页面被访问时，我们进行如下操作：1）将第k行的值全部设置为1。2）将第k列的值全部设置为0。在每次需要更换一个页面时，选择矩阵里对应行值最小的页面更换即可。此处的行值是指把该行所有的0和1连起来看做一个二进制数时的取值。 - 给每个存放在内存的页面配备一个移位寄存器。该寄存器用来记录该页面被访问频率和最近的属性。 - 在每个规定长度的周期内，将移位寄存器的值往右移动一位，并将对应页面的访问位的值加到该移位寄存器的最左位。 - 矩阵法需要n×n维的空间，而这里是n×L维。这里的L是移位寄存器的长度。因此，只要移位寄存器的长度少于进程在内存的页面数，这种实现方式就有空间上的优势。 - 至于溢出的位，都属于超时的信息，不再纳入考虑。 - 在矩阵法里，每次页面访问均需要更新矩阵，而移位寄存器法却不需要每次访问都进行更新。我们只在规定长度的时间内统计更新一次。 - 更新周期灵活所付出的代价就是记录的精确性不如矩阵法。在某些特定情况下，这样选出的页面有可能不是最近最少使用的页面。 - 这是一个常见的“衰老算法”的思想，越是发生时间久远的事件，它对决策的影响越小。 - 由于不可能精确地确定哪个页面是最近最少使用的，那就干脆不用花费这个力气，只维持少量的信息使得我们选出的替换页面不太可能是马上又会使用的页面即可。这种少量的信息就是工作集信息。 - 工作集算法的实现如下：为页表的每个记录增加一项信息用来记录该页面最后一次被访问的时间。这个时间不必是真实时间，只要是按规律递增的一个虚拟时间即可。同时我们设置一个时间值t，如果一个页面的最后一次访问在当前时间减去t之前，则视为在工作集外，否则视为在工作集内。 - 扫描所有的页面记录，并进行如下操作：1）如果一个页面的访问位是1，则将该页面的最后一次访问时间设为当前时间，并将访问位清零。2）如果页面的访问位为0，则查看其访问时间是否在当前时间减去t之前。a）如果在，则该页面将是被替换页面，算法结束。b）如果不在，记录当前所有被扫描过页面的最后访问时间里面的最小值。扫描下一个页面并重复1、2两个步骤。 - 该算法只扫描页表一次。如果所有页面的访问位都为1的话，则表示分配给该程序的内存不够。最好的解决办法不是替换页面，而是给该程序增加一个物理页面。 - 设计出工作集时钟算法，即使用工作集算法的原理，但是将页面的扫描顺序按照时钟的形式组织起来。这样每次需要替换页面时，从指针指向的页面开始扫描，从而达到更加公平的状态。而且，按时钟组织的页面只是在内存里的页面，在内存外的页面不放在时钟圈里，从而提高实现效率。 - 工作集时钟算法被大多数商业操作系统所采纳。 - 在页面替换算法的考虑中，算法应用的对象可以分为全局和本局两类，从而形成两类替换策略：全局策略和局部策略。 - 在全局策略下，算法应用的对象是物理内存里面的所有页面 - 在局部策略下，算法应用的对象是当前进程的所有页面， - 全局策略的优点是系统的总页面缺失率低，但程序运行不稳定。因为程序无法控制自己的缺页率。一个进程在内存中的页面使用不仅取决于该进程的页面走向，也取决于其他进程的页面走向。因此，相同程序由于外界环境不同会造成执行上的很大差别。 - 局部替换策略的优点是更加公平，程序运行更加稳定。因为一个进程的内存使用情况不会干扰其他进程的内存使用，但缺点是不能充分利用系统的整体资源，可能造成不同进程之间在页面使用上的不平衡：即有的进程有页面富余，而有的进程却频繁缺页。 - 使用何种页面替换策略决定了一个进程在内存所占页面的数量是否固定。 - 为每个进程分配内存块的算法主要有3种：均分法、比例法、优先权法。 ## 第14章 段式内存管理 - 我们把基本内存管理的一段式管理称为纯粹分段，而一个程序分为多个段的分段管理称为逻辑分段。 - 每个逻辑单元可单独占一个虚拟地址空间，这样使得编写程序的空间大为增长，几乎可以编写出没有尺寸限制的程序来。 - 段是按逻辑关系而分，共享起来就非常方便。不会出现分页系统下一个页面里面可能同时包含数据和代码而造成共享不便的问题。 - 对于空间稀疏的程序来说，分段管理将节省大量的空间。因为空余的部分不用分配任何虚拟空间；而在分页下，空余的空间仍然需要分配虚拟页面，只不过该页面非法而已。 - 段页式管理就是将程序分为多个逻辑段，在每个段里面又进行分页，即将分段和分页组合起来使用 ## 第15章 磁盘操作 - 读写磁头可以在6毫秒到17毫秒的时间内遍历磁盘的整个活动区域。这个时间与磁盘旋转一圈的时间一样。不管一个磁盘驱动系统有多少个读写磁头、多少磁道或多少盘面，在任何时候只能有一个磁头处于活动状态 - 磁道（磁柱）、扇面、和盘面（磁头）3个参数。以这种方式给出的地址称为逻辑块地址（Logical Block Address,LBA）。 - 从磁盘上读取一个扇面的过程：1）操作系统将要读取的LBA传送给磁盘驱动器并启动读取命令。2）磁盘驱动器通过将磁头移动到正确的位置，并启动处于指定盘面上的磁头来搜索指定的磁道。在磁头的移动过程中，读取磁头将不断地检查下面的扇面号直到找到所要求的扇面为止。3）磁盘控制器将扇面数据和ECC信息传送到一个处于磁盘界面里的缓冲区。这里的ECC信息是在数据流动的动态过程中进行计算而得出的。4）磁盘驱动器向操作系统发出“数据就绪”信号。5）操作系统从磁盘界面里的缓冲区读取数据，既可以按一个字节一个字节的方式来读取，又可以启动DMA命令来读取。 - 磁盘调度的算法主要有以下几种：先来先服务FCFS（First Come,First Serve）短任务优先STF（Shortest Task First）短寻道优先SSF（Shortest Seek First）电梯调度ES（Elevator Scheduling）提前查看电梯调度ESLA（Elevator Scheduling with Look Ahead）单向电梯调度OWES（One Way Elevator Scheduling） - 短寻道优先则考虑当前磁头离谁的数据最近，谁就优先。 - 电梯调度策略很简单，先满足一个方向的所有请求，再满足所有反方向的请求，这样循环往复。 ## 第16章 文件系统 - 与内存管理系统类似，文件系统也需要达到两个目的：地址独立和地址保护。 - 解决读写文件效率低的中心思想就是把磁盘访问变成内存访问。实现这种访问转变的手段就是内存映射的文件访问。 - 内存映射的文件访问不是为了文件拷贝而提出的，而是为了文件的共享。具体来说，我们可以将同一个文件映射到两个或多个进程的虚地址空间。这样每个进程对相应的虚地址空间进行访问时就是对同一个文件进行访问。 ## 第17章 文件系统实现 - 一个磁盘包括一个个扇面，编号从0递增，整数计数。第0个扇面在整个文件系统中占有重要意义。该扇面存放的是主引导记录（Master Boot Record,MBR）。该记录的内容是一个小小的程序，用来启动计算机。如果该扇面损坏，则整个磁盘就无法使用。这时唯一的办法就是将磁盘拿到硬件制造商那里对磁盘扇面重新编号。 - 在MBR后面紧接着的是磁盘分区表。磁盘分区表里给出的是磁盘的所有分区及其开始和终结地址，其中一个分区为主分区。操作系统就装载在这个分区中。主分区里面最前面的是引导记录（Boot Record）。 - MBR程序接下来找到系统主分区，并将主分区里面的Boot Record加载并运行。Boot Record里面的内容是一个小程序，该程序将负责找到操作系统映像，并加载到内存，从而启动操作系统。所有的文件系统都必须按照这种格式存放，操作系统才能正常启动。 - 在链表存放方式下，文件的映射就是给出文件第一个磁盘快的位置。这种存放方式比起连续存放方式的优点是可以利用碎片。但缺点呢？访问速度慢。尤其是随机访问，访问任何一个数据块均需要从头数据块开始一个指针一个指针地找下去。如果有任何一个指针损坏，则将无法重构整个文件 - 存放文件数据块指针的表称为文件分配表（File Allocation Table,FAT） - 在使用符号链接后，一个文件可以从多个路径进行访问。即一个文件有多个路径名，从多个路径都可以找到该文件在磁盘上存放的地址，也就是说，该文件的映射情况保存在多个文件夹里。 - 有了链接后，文件删除的操作需要进行修改。删除文件时不是马上将文件删除（不管是逻辑上还是物理上），而是将该文件对应I-NODE里面的链接计数减1。如果结果为0，就删除该文件（逻辑删除）； - 上面讲到的链接方式将文件的地址映射直接加到链接目录下，这种链接也称为硬链接。 - 软链接从严格意义上说不是链接，因为它并没有直接连到文件上，而是保存了文件的原始访问路径而已。正因为此，Windows的快捷方式不是链接。因为快捷方式保存的就是路径名。 - Windows上经常使用FAT文件系统，没有地方存放文件的链接计数，硬链接无法实现。当然，如果是NTFS，则可以使用链接。 - 链接虽然方便共享，但也存在诸多问题。最主要的问题是造成备份困难。 - 对容量配额的实现，不同的操作系统使用的方法不一定相同。在UNIX环境下，通常存在所谓的软配额和硬配额。软配额就是你可以临时超过，但必须在下次登录前解决这个问题，否则超出配额的文件将被删除。硬配额就是在任何情况下都不能超过，一旦超过，当前写入的数据都无法完成。 ## 第18章 文件系统性能 - 保护域就是将访问控制权限一样的文件和对象组织成同一个域。而访问控制权限与每个域直接相关。每个域的控制独立于其他域。每个进程都运行在一定的域里，从而具有访问该域里面文件和对象的权限。 - 一种较为新颖的数据保护方法是隐写文件或隐写文件系统（crypt file sys-tems）。隐写就是将要保护的数据嵌入到其他文件中而达到隐身的目的。例如，我们可以将一个文件甚至整个文件系统隐写在一系列音频文件中。另外一种更有意思的技术是数据隐藏，即将数据隐藏起来，使得病毒或者试图进行非法访问的人无法看到数据，甚至无法得知数据的存在。 - 物理备份不经过文件系统，因此需要裸读磁盘，即绕过文件系统对磁盘数据进行读写。 - 逻辑备份使用文件系统进行读写，备份软件无须与磁盘驱动器的许多底层细节打交道。 - 逻辑备份的时候你知道一部分语意；在物理备份的时候你不知道它的语意。在这种情况下，如果备份中途出现错误，你将很难侦测到它的错误。即使侦测到，进行恢复也不容易。而逻辑备份则可以文件为单位进行正确性确认。如果出现错误文件，只需要重新备份有问题的文件即可。 - 物理备份由于是拷贝磁盘上的一切数据，将造成物理磁盘的卷标也被拷贝。这样将造成物理备份的备份磁盘和源磁盘卷标相同。 - 根据备份方式的不同，备份可以分为很多种类。例如，备份方式有下列几种：主动和被动备份：以谁提要求来区分。在线和离线备份：以是否停止服务区分。实时和延时备份：以主备数据时差区分。等分和差分备份：以主备数据量差区分。增量和差分增量：以备份量和差分标来区分。分裂和并列备份：以备份是否减少来区分。近程与远程备份：以主备中心距离区分。 - 如果在将I-NODE写入磁盘后，但把I-NODE的磁盘地址和文件名写入该文件所属文件夹之前发生系统故障，则将出现“孤儿文件”，即文件不在文件系统里出现（目录里没有），但却在磁盘上。如果将上述两个操作步骤顺序颠倒，则有可能出现“魅影文件”，即文件在文件系统里出现（在目录里有），却没有在磁盘上。 - 不管是幻影文件、魅影文件还是孤儿文件，都表明文件的一致性遭到破坏。那么如何保证文件系统的一致性呢？答案是使用日志（logging）、事务（transac-tion）和随影（shadowing）。 - 当这些新数据全部写完后，在日志最后写上“完毕”（commit）。在这之后，我们就可以将日志里面的数据往源文件里写。这样就能确保文件数据的一致性。 - 一个事务是一组操作。事务机制可以确保这一组操作要么全部发生，要么一个都不发生。 - 那么事务是如何实现的呢？答案很显然，与日志一样。即将所有的磁盘写操作记录在与源数据分开的地方。在“完毕”（commit）后，即可以将这些数据往源数据上拷贝。 - 锁的实现需要硬件支持，事务的实现也不例外，也需要硬件的支持。而这里的硬件支持就是一个扇面的读写。磁盘系统读写一个扇面的操作是一个原子操作 - 文件系统一致性包括如下几个方面：没有魅影文件。没有孤儿文件。文件I-NODE里面的链接计数与其出现在文件系统中不同位置的次数一致。没有消失的空间。没有额外的空间。 - 日志结构的文件系统。在这种系统中，整个磁盘被看做一个巨大的日志。所有的磁盘写操作从日志的尾端开始，这样就避免了寻道操作。 - 每次写从上次写毕的位置直接开始。当写到磁盘末尾时，我们再从磁盘头接着写下去。即将磁盘看做一个循环日志。 - 由于每次文件修改后的内容都写入日志的末尾，即为该文件创建了一个新的版本，将造成一个文件在磁盘上存在多个版本。 - LFS使用一个垃圾清理程序来清理已经废弃的文件。当然，这个垃圾清理程序只在磁盘空闲时或者磁盘空间已满时才运行。 ## 第19章 输入输出 - 在专有通道I/O模式下，I/O与内存是完全脱离的。每个控制寄存器被赋予一个I/O端口。 - 内存映射的I/O，顾名思义，就是将I/O映射到内存里面。从而使得I/O和内存管理得到统一。具体来说，就是将I/O设备的每个控制寄存器和设备缓冲区寄存器赋予一个唯一的内存地址。对这些地址的访问就是对I/O设备的访问。对这些地址的访问从逻辑上看，就是内存访问。 - 对于一般的数据来说，缓存提供的是优势。但对于控制寄存器来说，则是一个大缺点。因为操作系统在读控制寄存器时需要的是最新的内容，而不是缓存的内容。 - 如果要传输的数据是一片连续的内存空间，则我们就可以把CPU从I/O中解脱出来。解脱出来的办法就是直接内存访问（即Direct Memory Access,DMA）。 - DMA的工作原理是，如果按数据块进行I/O，即需要传输大量数据时，就无须CPU的介入。在这种情况下，我们可以让I/O设备与计算机内存进行直接数据交换。而CPU则可以去忙别的事情。这种将CPU的介入减少的I/O模式称为直接内存访问。 - 由另外一个CPU来负责数据传输。这个另外的CPU就是DMA控制器。 - 由于DMA需要与CPU竞争内存总线，其效率的提高不如理论上的期望。 - 在下述情况下，应该选择使用主CPU：设备I/O速度非常高。主CPU没有其他事情可做。成本考虑。 ## 第20章 多核结构与内存 - 在多CPU的情况下，以CPU之间的关系不同又可以分为对称和非对称多处理器结构。 - 对称结构下，多个CPU的角色功能平等，没有主从之分，这种多CPU结构称为对称多处理器结构（Symmetric Multi-Processor Architecture,SMP）。 - 非对称多处理器结构中，则不同CPU的角色地位不同，有主从CPU之分。这种多CPU结构称为非对称多处理器结构（Asymmetric Multi-Processor Architecture,AMP）。 - SMP结构远比AMP结构普遍 - 超线程技术可在同一时间里让应用程序使用芯片的不同部分。而为了支持这种技术，需要在处理器上多加入一个逻辑处理单元指针（Logical CPU Pointer）。 - 最简单的内存共享方式就是将内存作为与执行核独立的单元构建在核之外，所有的核通过同一总线对内存进行访问。由于每个核使用相同的方式访问内存，其到内存的延迟也相同，这种访问模式称为均匀内存访问（Uniform Memory Ac-cess,UMA）。 - 随着执行核数量的增加，对共享内存的竞争将变得白热化，从而造成系统效率急剧下降。 - 多个分开的独立共享内存。每个执行核或CPU到达不同共享内存的距离不同，访问延迟也不一样。这种访问延迟不一致的内存共享模式称为非均匀内存访问（Non-Uniform Memory Access,NUMA） - 在每个执行核里面配置缓存，其执行需要的数据均缓存在该缓存里面。所有访问由缓存得到满足。这样，不论数据原来是处于哪个内存单元，其对效率的影响均将不复存在。 - 这种完全由缓存满足数据访问的模式称为全缓存内存访问（Cache Only Memory Access,COMA）。在这种模式下，每个执行核配备的缓存共同组成全局地址空间。 - 我们不能让两个CPU同时执行BIOS（或EFI）里面的指令（BIOS不支持多线程）。因此，除一个CPU外，必须让其他CPU均处于中断屏蔽状态。也就是说CPU的启动是有次序的。 - 所有的CPU里面有一个被定为启动处理器（Bootstrap Processor,BSP），而其他的处理器则作为应用处理器（Application Processor,AP）。到底哪个CPU是BSP则由某一特定寄存器的值来决定。 - 多CPU之间通信，自然也可以发送信号。不过这个信号不是内存的一个对象，因为这样的话，无法及时引起另外一个CPU的注意。而要引起其注意，需要发送的是中断。 - 用来协调这些CPU之间中断的机制就是高级可编程中断控制器（APIC）。这是实现SMP功能必不可少的，且是英特尔多处理规范的核心。 - 除了每个CPU自己本地的APIC外，所有CPU通常还共享一个I/O APIC来处理由I/O设备引起的中断，这个I/O APIC是安装在主板上的。 - 除了处理处理器间及输入输出的中断外，APIC也负责处理本地中断源发出的中断，如本地连接的I/O设备、时序中断、性能监视计数器中断、高温中断、内部错误中断等。 ## 第21章 多核环境下的进程同步与调度 - 在多核环境下，还有一种硬件原子操作称为总线锁。总线锁就是将总线锁住，只有持有该锁的CPU才能使用总线。这样，由于所有CPU均需要使用共享总线来访问共享内存，而总线的锁住将使得其他CPU没有办法执行任何与共享内存有关的指令，从而使得数据的访问是排他的。 - 硬件提供的另外一种同步原语是交换指令，即xchg（exchange）。该指令可以以原子操作完成在寄存器和内存单元之间的内容置换。 - 旋锁上的繁忙等待时间通常较短。因此持有旋锁的CPU肯定在往前推进（而不像线程持有锁的情况，线程有可能没有推进），会很快释放旋锁。切换到别的线程再回来，反而慢了。 - 因为旋锁由CPU持有，不是线程持有，因线程具有优先级关系而可能出现的优先级倒挂现象在旋锁上自然也不会出现。 - 旋锁的问题是对总线的竞争，而这是一个严重的问题。 - 每个CPU在检查旋锁的状态时均需要使用系统总线来访问旋锁所在的共享全局内存单元。如果它要测试并设置这个全局内存单元，就需要使用内存总线。那么它不停地发信号到总线上，会造成对内存总线的竞争。这是效率非常低下的一种机制。这就是旋锁的缺点。 - 队列旋锁的中心思想就是，需要旋锁的CPU不要到全局内存去SPIN，而是到自己的局部内存去SPIN。这样就可以排除对总线的竞争。在旋锁上排一个队，就表示哪些CPU要这个旋锁。释放的时候就去检查这个队列，交给队列里的第一个CPU。 - 由于不同CPU的功能并不相同，而一个进程可能需要某个特定CPU的功能才能执行。即使这个CPU非常繁忙，我们也不愿意将某个进程移动到另一个CPU上。这时我们就将一个进程钉（pined）在一个CPU上。一个被钉住的进程是不能移动的。 - 如果一个应用被分解为多个线程，由于多个线程需要共享许多资源，这时需要将这些线程尽量分配到同一个处理器核上执行，以提升缓存命中率。 - 如果一个CPU没有任务可执行，我们可以令其执行一条所谓的终结（halt）指令，使其进入到C状态（一个耗能很低的状态）；如果一个CPU的工作量很少，我们可以降低其主频频率，使其运行在较低的速度上，从而降低能耗。这个低频率状态就是所谓的P状态。 - 对于超线程结构来说，C状态是独立的。即一个逻辑CPU可以变为C状态，而不影响其他逻辑CPU的运行。 - P状态是不独立的。因为一个物理CPU里面的逻辑CPU共享同一个时钟，它们的P状态控制寄存器也是共享的。