《现代操作系统》学习笔记

《现代操作系统》看了两个多月才看了前面200页，很多都似懂非懂，权且将自己认为重要的概念抄下来，以备后续查看。

0. 概述

（1）操作系统的概念

对操作系统的定义，有两种说法，一种声称操作系统是计算机的扩展器，一种声称操作系统是计算机资源集的抽象。

所谓操作系统是计算机的扩展，是将操作系统当做计算机对外的接口。对外包括对应用程序，对程序员，对用户。操作系统对计算机进行“化妆”，将计算机“丑陋晦涩”的硬件对外隐藏，而向外呈现界面友好清晰，更易理解的操作系统。如下图所示：

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

所谓操作系统是计算机资源集的抽象，是指操作系统将计算机资源（处理器，存储器以及I/O设备等）进行抽象以及管理。将CPU处理抽象为进程，将内存抽象为地址空间，磁盘抽象成文件。而这一切抽象都是为了实现多道程序设计，即可以在一个计算机上同时运行多个互不干扰程序。

（2）操作系统的作用

操作系统的主要任务是在相互竞争的程序之间有序地控制对处理器、存储器以及其他I/O接口设备的分配。其主要任务包括管理资源分配，评估使用代价和调节资源分配的冲突，记录哪个程序在用什么资源，用多少，用多久。资源管理包括用以下两种不同方式实现多路复用：在时间上复用（进程调度： CPU 时间片轮转）和在空间上复用（内存管理：虚拟内存，页面置换；磁盘管理：文件系统）。在时间上分配CPU资源需要考虑该进程在上面运行多久，下一次切换到哪一个进程。在空间上分配存储空间需要考虑给每个进程分配多少内存，如果内存不足的时候，将哪个页面置换到磁盘以腾出空间。

操作系统的主要功能：为用户程序提供抽象和管理计算机资源。用户程序和操作系统之间的交互处理是前者。用户程序和操作系统之间的交互主要是处理抽象。对于管理计算机资源系统（进程调度，内存置换等）一般自动完成。所以主要是用户程序与操作系统的交互。用户程序通过操作系统提供的接口来访问底层的系统。操作系统提供一种特殊的过程调用——系统调用，该种过程调用可以由用户态陷入

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

内核态对底层进行操作。比如可以创建和退出进程，打开和读写文件等。目前主要由以下几种系统调用函数——进程管理，文件管理，目录和文件系统管理以及其他。常用的系统调用可以参见下表：

（3）为什么要了解操作系统

之前跟同事说我没有修过操作系统，想补补操作系统，同事说操作系统工作中很少用，我当时想学习操作系统也跟我学习数据结构后

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

一个感觉——很难很有趣但是工作中用不着。而老大却一再跟我说，让我打好基础，好好补补操作系统，计算机网络等基础课程。而我自己看了操作系统之后，突然恍然大悟，oh，原来学习数据结构就是为了学习操作系统呀呀呀~~(*^__^*) 嘻嘻……

瞎扯完，言归正传。我当时学习操作系统源于工作中遇到一个父子进程共享文件描述符的坑。这个坑坑得我好惨啊，因为其具有偶发性，而且完全没有日志迹象查询，只知道在入口处数据就莫名其妙丢了。之前同事也遇到过这种情况，只是定位怀疑有一段代码存在问题，总是觉得那段fork子进程的代码有问题，后来因为这个bug复现少，所以也不了了之。后来因为系统用得越来越多，这个问题复现概率大大提高，于是开始打日志，每一个操作都打日志，最后在老大的英明神武下，发现了原来是在fork子进程之前没有关闭父进程使用的队列连接。如果没有老大，估计打死我也不知道如何解决这个问题。因为我完全不知道这个基础知识。虽然后来老大跟我说了父子进程共享文件描述符的知识，也说了数据可能被子进程的队列连接socket的handle读走了。但是我还是似懂非懂，于是乎，我决定好好补补操作系统。除了因为这个坑，还因为每次老大跟我说内存，cpu，进程，线程我都没概念，所以我决定脑补下，^_^。

吐槽完总结下，了解操作系统就是为了理解计算机是如何工作的，以及程序如何运行的，从而优化程序更好地实现需求，达到预期目的。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

（a）程序在运行的时候需要哪些资源，会受到哪些资源（如磁盘，内存，cpu等）。

比如日常程序每天导库的时候需要例行将历史记录清除，以防磁盘空间不足。

比如redis中的缓存过期数据也要定时清除，以防止redis内存不足而导致其他redis操作失败。在设置redis的max_memory的时候，也要考虑随着业务增长，对redis内存空间要求会越来越大。

比如写程序的时候也要考虑程序可能要用到的最大内存，如果使用内存超过系统默认分配内存，将导致程序出错退出。

比如使用sort命令或awk联合数组对大文件排序的时候可能导致内存使用率100%。

比如使用fork子进程的，要考虑cpu的，不能fork很多子进程，最好使用taskset设置空出一两个核以使机器负载不至于过高，还有fork子进程要记得exit，否则资源不释放，会导致cpu飙到100%。

比如访问同一个资源（db或者redis）的时候要考虑qps，否则会使得资源cpu使用率过高，从而使得有些资源操作失败。影响业务qps主要是用户的访问频率，除此之外在异步处理（用队列存储数据，用daemon处理数据）中，daemon数，队列数都会影响qps。

（b）分析系统的资源评价，从而使得系统优化。

考虑程序运行慢是受哪一部分的：CPU，内存，磁盘等。耗费这些资源过多的是磁盘IO还是网络IO。比如考虑优化网络IO，使

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

用pipeline将数据push到队列，比一个个push要快很多，使用hashMSet比hashSet要快，比如redis的qps过高，会引起cpu占用太高，从而引起程序太慢。

（c）为防止各个程序同时访问一个资源而引起冲突，会引进互斥的概念。

比如多个任务并行处理，如何分配唯一任务id。或许有人说采用时间戳，可是当系统并行处理多个任务的时候，他们处理时差远少于1秒，1秒的间隔已经无法区分他们的时序。有人可能说采用一个共享变量，每次自增来分配task_id。但是如何保证并行处理的时候这个共享task_id唯一，不会出现冲突，这就要理解互斥。在工作之前没有任何什么锁住表，锁住redis，互斥的概念，这些对我来说都是天书。所以当工作遇到redis为了实现互斥，采用单线程。并且redis在执行一个操作的时候，会锁住redis。于是问题来了，当redis删除大数据(如6kw+长度的hash列表或者大的set，长的list)的时候，redis会被锁住很久（高达十几秒），此时对该redis的其他操作就无法执行。在工作中也遇到这个坑，很多泪就不飙了...除了这个坑，当多个程序同时访问同一个redis的时候，发生了冲突，即竞争条件，从而使得redis操作失败，并且使得下面的程序无法执行。这个时候可以考虑模拟假脱机打印机处理打印机资源冲突的方式。将对redis操作请求入队列，单独使用一个daemon来消耗队列中redis操作请求一一处理之。采用队列的方式，可以使得各redis的操作请求具有一定的时序。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

（d）采用多进程，以及父子进程共享文件描述符，多线程共享地址空间都是为了充分利用系统资源，并行处理以更快速度解决问题。并行就必须考虑各个进程之间是否保有性，各个同时处理的数据是否具有依赖性，若有依赖性就牵涉时序问题，资源共享也往往引起冲突。

可能你的程序看起来很符合逻辑，但是在处理大文件和大量数据的时候，还符合逻辑吗？在多个相关任务并行处理的时候，还符合逻辑吗？在机器出现资源不足的时候，还符合逻辑吗？在多个程序竞争资源的时候，还符合逻辑吗？在需求变更的时候，还符合逻辑吗？

要解答这些问题，就是你要学习操作系统的原因。

要理解操作系统，就必须要理解每一个资源抽象的概念和实现，以及如何使用这些抽象来解决问题。所以下面会从cpu的抽象——进程（进程调度），内存的抽象——地址空间（内存管理），磁盘的抽象——文件（文件系统），互斥和锁这几个方面来记录学习操作系统的一些笔记和感受。

1. cpu --> 进程 （1）进程的概念

就像人类对这个世界的认识一样，首先是感性认识，之后才上升到理性认识。所以我们首先通过《现代操作系统》上对进程的一段比喻来理解进程。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

想象一位有一手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需要的原料：面粉、鸡蛋、糖和香草汁等。在这个过程中：

做蛋糕的食就是程序。

计算机科学家就是处理器 cpu。 做蛋糕的各种原料就是输入数据。

科学家阅读食谱、取来各种原料按照食谱的步骤烘培蛋糕的一系列动作的总和就是进程。

进程切换的比喻：现在科学家的儿子哭着跑进来，说他的头被蜜蜂蛰了，科学家记录下其食谱做到哪儿了（保存进程的当前状态），然后拿出一本急救手册，按照其中的只是处理蛰伤。这里，我们看到处理机（科学家）从一个进程（做蛋糕）切换到一个更高优先级的进程（实施医疗救治），每个进程拥有各自的程序（食谱和急救手册）。蜜蜂蛰伤处理完成之后，这位计算机科学家又回来做蛋糕，从他离开时的那一步继续往下做。

所谓进程，就是容许运行一个程序所需要所有信息的容器。这些信息包括与进程相关的有地址空间和资源集。地址空间包括可执行程序，程序的数据以及程序的堆栈；资源集包括寄存器，打开文件清单，突出的报警，有关进程清单，以及运行该进程所需要的所有其他信息。

知道进程的概念，就知道系统会给每个进程分配一个PID，通过这个PID可以查看各个进程使用cpu，内存，code资源情况，同时

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

可以将PID传给kill命令杀死这个进程。非常赞同在比较unix和windows的，windows隐藏了太多操作系统的细节，而unix的命令行界面可以更多程序操作系统的相关细节。所以可以使用top命令查看当前系统运行了哪些进程，每个进程占用多少CPU和进程，磁盘，机器负载是否过高等。虽然windows资源管理器一定程度也可以，但是还是没有unix的直观和详细。我想对有经验程序员来说，windows简直弱爆了，费时而且不方便。虽然我还是一个菜鸟级程序员，也还一直使用着windows，也无法抛弃windows，但还是被unix深深滴吸引。

（2）进程模型——进程如何实现的

（如何创建和终止进程，进程的层次，进程的状态，进程表）

创建一个进程，其实是启动一个程序。一般在以下四种情况下创建进程：

1). 系统初始化（比如启动计算机）

2). 执行了正在运行的进程所调用的进程创建系统调用（fork）

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

3). 用户请求创建一个进程（比如用户打开一个程序） 4). 一个批处理作业的初始化

进程也是有生命周期的，当它完成它的任务之后，就要释放计算机的相关资源并退出。一般通过以下条件来终止进程。

1). 正常退出；

2). 出错退出；（异常处理）

3). 严重错误；（非法指令，引用错误内存，除零错误） 4). 被杀死

从上面创建进程的第二种方法可以看到进程可以fork进程，则说明进程存在父子关系，有其层次结构。

父进程和子进程共享文件描述符（file_handle，网络连接socket）和相同的存储映像，相同的环境字符串。

父进程和子进程拥有不同的地址空间（拥有不同的内存页面）。 ps：windows的进程没有父子关系，但是“父进程”可以控制“子进程”，并且可以转交监控权，也可以剥夺“子进程”的继承权。而unix中父进程不能剥夺子进程的继承权。——不太懂这个。

进程具有三种状态：

阻塞(有cpu资源，但是等待输入) 就绪（无cpu资源，即可运行） 运行（正在占用cpu执行程序）

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

因为进程调度的原因阻塞不能直接转到运行，就绪也不能直接阻塞。

为了实现进程模型，os维护着一张表——进程表：储存进程状态（程序计数器，堆栈指针，内存分配状况，打开的文件状态。账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的东西，从而保证该进程随后能再次启动，就像从未被中断过一样等）（具体参见《现代操作系统》P52图2-4）

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

一般通过中断来实现进程切换，有硬件中断，时钟中断等。通过操作系统通过中断来完成进程切换的具体步骤参见图2-5

线程是我的薄弱，之后好好补补，还有进程和线程的区别。

进程的创建需要分配资源。而退出进程需要释放资源。而进程的切换也意味着进程状态的变换，以及资源的变更。当进程无CPU的资源的时候，等待切换的时候，就处于就绪状态，而当进程占用CPU资源执行程序的时候处于运行状态，如果系统给进程分配CPU资源，而进程等待输入，则处于阻塞状态而被挂起。此时会发生进程切换。当创建和退出进程时，进程阻塞，发生中断的时候都会进行进程切换。

（3）进程间的通信

进程间通信包括三个基础问题：

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

a. 进程如何把信息传递给另一个

b. 确保两个或多个进程在关键活动中不会交叉（保持互斥） c. 进程执行的正确顺序（进程A产生数据，进程B打印数据，则应该先执行进程A，再B）

关于第二个问题，就会牵涉到竞争条件——互斥

两个或多个进程读写某些共享数据。而最后的结果取决于进程运行的精确时序，称为竞争条件。比如并发的时候，如何保证互斥。redis中的hashSetNx和hashIncrBy可以确保互斥吗？

A和B共享out，A读取到一个共享变量，在A读取到A修改这个变量之间，该共享变量被其他进程修改。此时A修改该变量覆盖了原有的值。

临界区——保证互斥

凡是涉及共享内存，共享文件以及共享任何资源的情况都会引发与前面类似的错误。关键是要找到某种途径来阻止多个进程同时读写共享的数据。有人提出临界区的概念防止多个进程同时读写共享数据，也就是通过临界区来保证互斥。

临界区应该满足的以下条件： 1). 任何两个进程不能同时处于临界区 2). 不应对CPU的数量和速度有任何的假设 3). 临界区外的程序不应阻塞其他程序 4). 不能使程序无限期等待进入临界区 实现互斥的几种方法：

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

（a） 屏蔽中断——每个进程在刚刚进入临界区后屏蔽所有中

断，从而无法进行进程切换。

这样就只有一个进程处于临界区，也就避免了竞争条件。但是这种操作很危险。如果屏蔽不再打开，整个系统就终止了。 （b）锁——初始值为0，若有一个进程进入临界区为1. 但是当一个进程读取锁为0到设置其为1的整个过程中，又有一个进程也读取锁值为0，也设置为1，此时将有两个进程进入临界区。

即该种方法无法真正达到互斥。

（c）严格轮换法——用turn记录轮到哪个进程进入临界区。需要进入临界区的进程不断的轮询看其是否轮到自己。

这种情况可以实现互斥，但是如果轮到某个进程进入临界区，它又在做其他事情，迟迟不进入临界区，就是占着茅坑不拉屎，导致其他人不能上厕所。也就是临界区外的进程阻塞了其他进程进入临界区。违反了上面的第三个条件。

（d）Peterson解法为了防止出现临界区外的进程阻塞其他进程进入临界区，设置了一个数组来记录某个进程是否有兴趣进入临界区，如果其没有兴趣进入临界区，则让给其他进程进入临界区。

采用enter_region和leave_region设置turn和interest数组。turn用来记录哪个进程希望进入临界区，或者轮到哪个进程进入到临界区。

信号量和互斥（重点 ）

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

Murphy法则：任何可能出多的地方出错的概率会大大增加。

（4）进程调度

——（时间上多路复用）实现多道程序设计，也就是通过进程切换让各个进程轮流占用CPU执行程序，从而实现多程序分时系统。

调度程序的主要工作就是决定应当运行哪个进程、何时运行及它应该运行多长时间。进程调度的算法力图在整体效率和进程的竞争公平性之间取得平衡。

进程分为CPU密集型进程和IO密集型进程。所谓CPU密集型进程就是占用大量cpu来运行程序，而所谓IO密集型进程就是需要进行大量的IO操作。几乎所有进程的（磁盘）I/O请求或计算都是交替突发的。

有关调度处理的一个关键问题是何时进行调度决策： 1. 创建新进程时，应该先调度父进程还是子进程 2. 进程退出时

3. 进程阻塞时（IO，信号量等） 4. I O中断发生时

调度目标：保证公平；系统的策略强制执行；保持系统的所有部分尽可能忙碌。

调度算法：先来先服务，最短作业优先，最短剩余时间优先 关键调度算法：时间片轮转和优先级调度。

时间片过长——导致较短请求较长相应时间，cPU资源浪费

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

时间片过短——更多的进程切换，导致占用更多的CPU，CPU利用率降低

为了防止高优先级无休止运行下去，导致低优先级的处于饥饿状态。调度程序可以在每个时钟中断降低当前进程优先级，或者设置每个进程运行运行的最大时间片。

对IO密集型进程，若其在时间片占用时间f越短，其优先级1/f越高。

多级队列采用对进程的优先级进行分类的算法。

彩票调度：给各个进程发放一些资源彩票，抽中谁，就给谁分配资源。对于新来的程序也发放彩票，它也将拥有同等的概率获得资源，这样对新的程序可以及时响应。同时可以通过发放彩票的额度来量化各个进程的优先级。

策略和机制：将调度策略和调度机制分离。将调度算法（机制）形式化，调度参数（策略）由用户进程填写。

线程调度

线程调度和进程调度基本一致。只是因为同一个进程中的各个线程之间都共享相关的资源，所以线程切换效率要高于进程切换。

2. 内存 --> 地址空间

帕金森定律声称不管存储器有多大，程序都可以把它填满。所以对于程序来说，内存是远远不够。一方面希望能尽可能多的活跃用户程序装入内存，另一方面系统内存资源有限。所以需要对内存资源进

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

行协调分配和管理，最大限度的充分使用各个存储资源。接下来主要讨论操作系统是怎样对内存创建抽象模型以及怎样管理内存的。

由于每个存储介质的特性不尽相同。一般存取速度快的存储介质其成本也会更高，存储空间小，易失性也高（比如高速缓存）。而相对低成本的存储介质如磁盘容量大，不易丢失，但是存取速度比内存慢几个数量级。所以具体问题具体分析，依据各个存储介质的特点建立了分层存储体系。如下图金字塔所示：

操作系统是将这个存储体系抽象为一个有用的模型并管理这个抽象模型。操作系统中管理分层存储体系的部分称为存储管理器。它的任务是有效地管理内存，即记录哪些内存是正在使用的，哪些内存是空闲的，在进程需要时为其分配内存，在进程使用完后释放内存。并

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

且负责内存与磁盘之间交换。存储管理器（MMU）的主要作用参见下面截图：

（1）地址空间的概念

地址空间：是一个进程可用于寻址内存的一套地址集合。 使用地址空间对存储器进行抽象，主要是为了实现多道程序设计，即实现多个程序可以装入内存且互不干扰。每个进程都有自己的地址空间。

为了实现多道程序设计，曾有采用交换技术，基址寄存器与界限寄存器，虚拟内存等来实现。目前主要采用的是虚拟内存的方法。

（2）虚拟内存

虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分隔成多个块，每一块称作一页或页面。每一页有连续的地址范

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

围。这些页被映射到物理内存，但并不是所有的页面都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间，这个空间被分割成多个块，每一块称作一页或页面。每一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

（3）页面置换——（空间上多路复用）实现多道程序设计

多个程序被装载如进内存，而内存资源有限。所以并不是当前运行的程序的所有的页面都载入内存。这也将导致程序引用到的一些页面不在物理内存中，则可能引起缺页中断。这个时候就需要进行页面

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

置换。由于页面大小固定，所以不需要考虑分配多大内存。关键在于选哪一个页面换出内存。如果是干净页面，不需要写回磁盘，但如果是脏数据，则需要将其写回磁盘。

页面置换的算法基于这样的思想：已经很久没有使用的页面很有可能在未来较长时间的一段时间内仍然不会被使用。这个思想意味着在缺页中断发生时，置换未使用时间最长的页面。这个策略称作：LRU（Least Recently Used 最久最少使用）页面置换算法。

LRU算法理论上可以实现，但是代价太高，所以用软件模拟LRU。NFU（Not Frequently Used最不常用）简单的就是记录每个页面的访问频次以及最近一次的访问时间，将访问频次最少的置换出来。对于访问频次相同的，选择最久没有被访问的那个页面置换。

老化算法(Aging)也是模拟LRU算法，就是说在用一个01序列记录每个时钟页面是否被访问，如果第i个时刻该页面被访问，那么该序列第n-i+1位为1，否则为0。n为时钟个数。选择计数器值最小的页面进行置换。采用此种置换方法会使得访问频次相同，越久没被访问的页面计数器值偏小。因为越早的时刻被访问访问值处在低位，越早的处于高位。

（自己语言表述没表达清楚，copy书上的一段看看）

首先在R位被加入之前先将计数器右移一位；其次，将R位加到计数器最左端的位。这样保证页面的最早的访问位处于计数器值低位，最近访问位处于计数器值高位。（觉得这个计数器很nice，不但款可以衡量访问频次，还可以衡量最新访问时间）。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

这个方法的缺陷在于计数器只有有限位，计数器只记录9个时刻，假如一个页面上次访问是在10个时钟前，另一个页面上次方位是在1000个时钟前。这个时候计数器就无法衡量这两个页面哪一个最久没被访问。此时很有可能将第一个页面（连续10个时钟没有访问）给置换掉，而不是将最久没被访问的页面（连续1000个时钟没有访问）置换掉。

除了老化算法，还有类似队列先进先出（FIFO）的算法，该算法最新访问的页面放在队列尾，这样最久没被访问的处于队列头部，选择头部的页面置换掉。这样的方式会将最新的放在队列尾部，但是最常用的最老的页面将会被淘汰掉，因为它没有考虑页面访问频繁程度。

为了防止FIFO算法将常用的老页面置换掉，提出了第二次机会算法，就是从队头寻找没有被访问的页面(R为0)。如果该页面的R为0，则将其置换掉。如果队头的页面被访问过（R为1），则将其R置为0，并且从队头装入到队尾。直至从队头找到没有被访问过的页面（R为0）。

按照这本书一贯的惯例，一个算法在解决一个问题后，又会在其他情况下存在缺陷，也就是说没有尽善尽美的算法。第二次机会算法虽看起来很赞，但由于需要在链表中频繁移动页面，从而降低效率。还好是用链表来实现队列，用数组实现第二次算法的队列，会搞死你滴。比第二次算法稍微好点（不需要频繁移动页面）就是时钟页面置换算法。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

时钟页面置换算法是将所有的页面都保存在一个类似钟面的环形链表中，用表钟的时针来指向最老的页面。时钟按照某一个方向转动寻找未被访问过（R为0）的页面，如果当前时针指向的页面没被访问过，则置换掉，并且将新的页面插入这个位置，然后将表针前移一位。如果R位是1就清除R位并把表针前移一个位置，重复这个过程直至找到R位为0的页面。

在多道程序设计系统中，经常会把进程转移到磁盘上（即从内存中移走所有的页面），这样可以让其他的进程有机会占用CPU。当进程再次被调用回来后，该进程会一直产生缺页中断直到它所需要的页面全部被装入内存。这样就导致每次装入进程，都要发生多次缺页中断，大大的降低了效率，并且cpu也要花时间处理缺页中断，浪费cpu的宝贵时间。所以内存的分页系统（paging system）会设法跟踪进程的工作集，在进程运行前将其装入内存。这种方法叫做预调页，大大的减少了缺页中断的时间。人们很早就发现大多数程序都不是均匀地访问他们的地址空间的，而访问往往是集中于一小部分页面。

如何确定进程的工作集合以及工作集合大小，这是一个让人头疼的问题。

由于基本的工作集算法，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较费时的。

与时钟算法一样，所需的数据结构是一个以页框为元素的循环表，起初表是空的，之后逐渐将页面加入到表中，形成一个环。每个

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

表项包含来自基本工作集算法的上次使用时间，R位（访问位）和M位（修改位）。如下图所示：

先选择没有被访问的页面，访问的页面跳过，并且其R位重置为0。如果找到了没被访问过的页面，再看其上次使用时间距离现在的时间（即生存时间）是否大于某个值。如果大于生存时间，则看其是否是干净页面，如果是干净页面，则将其置换掉换入新的页面。如果其不是干净页面，则跳过（为了减少写入磁盘的时间）。如果转了一圈还没有干净的未访问页面，则将某个页面写入磁盘，置为干净页面，并将该页面置换出来。

工作集时钟页面转换算法中，页面置换的优先级：未访问页面>未修改的干净页面>老页面。

工作集时钟页面转换算法图解见下图：

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

各个页面置换算法比较：

3. 磁盘-->文件系统

本着以下三个基本需求： a） 能够存储大量信息

b） 使用信息的进程终止时，信息仍存在 c） 必须能使多个进程并发存取有关信息

磁盘诞生了，相对内存，磁盘具有大容量，不易丢失，成本低廉的优点，但是在存取速度要比内存慢几个数量级。

虽然对磁盘进行读写操作比较容易，但是对于以下情况不一定能很好的解决：

1) 如何找到信息？——查找

2) 如何防止一个用户读取另一个用户的数据？——权限 3) 如何知道哪些块是空闲的？——磁盘空间分配和回收

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

于是类同进程之于CPU，地址空间之于内存。同样磁盘也需要一个抽象来解决这些问题。于是文件的概念就出现了。通过进程调度来进程切换，通过内存管理单元来管理内存的分配，释放和置换等。同样操作系统需要一个系统来处理文件——文件系统。

（1）文件和目录的概念

——从用户角度来看文件和目录有哪些操作，文件如何命名，目录树的层次，文件的相关权限修改等

文雅点说文件是数据集合，粗糙点说文件就是磁盘块集合。文件具有权限（读写执行），创建时间，访问时间文件所有者等属性，可以进行创建打开读写关闭删除等操作。文件具有不同的类型。除了普通文件和目录外，UNIX还有字符特殊文件和块特殊文件。字符特殊文件和输入/输出有关，用于串行I/O类设备，如终端，打印机和网络等。块特殊文件用于磁盘类设备。普通文件一般分为ASCII和二进制文件。ASCII文件最大优势是在于可以显示和打印，还可以用各种编辑器进行编辑。目录其实也是一种文件。所以也有权限等属性，有创建打开关闭删除等操作。

通过ll命令可以看到文件和目录的详细信息，

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

（2）i节点

——实现者角度来看文件和目录是怎样存储的，磁盘空间是怎样管理的以及怎样使系统有效而可靠地工作。

文件存储的实现的关键问题是记录各个文件分别使用哪些磁盘块。这样操作系统就知道哪些磁盘块被使用，哪些是空闲的。要读写一个文件要访问哪些磁盘块，创建和删除文件可以进行磁盘块的分配和回收。

有四种算法来给一个文件分配磁盘块。给文件分配磁盘块要本着方便进行文件创建时分配空间，删除时回收空间，读写的时候能快速查找到相应的磁盘块，并且最大限度减少磁盘块空间的浪费。

（a） 连续分配

算法：每个文件作为一连串连续数据块存储在磁盘上。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

优点：实现简单，只需要知道第一个磁盘块地址和磁盘块块数即可。读操作性能好，因为磁盘块都挨在一块，减少了磁盘寻道和旋转延迟。

缺点：引起磁盘碎片，从而导致磁盘空间浪费。而且不利于动态分配文件存储空间。 （b）链表分配

算法：每个文件构造磁盘块链表

优点：最大限度使用磁盘空间，很少有磁盘碎片，除了最后一个磁盘的内部碎片。而且可以动态扩展文件的存储空间。 缺点：读操作性能下降，由于磁盘块之间不是连续的，所以需要寻道和旋转。而且随机存取性能也会下降。磁盘块之前有两个字节存储了下一个磁盘块的地址，导致每一个磁盘块存储的内容不是2的整数次幂。如果需要完整读取2的整数次幂，会导致获取和拼接两个磁盘块。

（c） 在内存中采用表的链表分配

这种方法类似于上面的方法，针对上面采用磁盘空间存储磁盘地址不能读取2的整数次幂，所以使用内存来存储磁盘块地址链表。这种方法主要缺点由于其存放在内存中，当磁盘比较大的时候，非常占用内存空间。 （d）i节点

针对上面占用内存空间的缺点，提出i节点的概念。就是使用i节点来存储每个文件包含的磁盘块的地址和文件属性。但是只有当文件

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

打开的时候，该文件对应的i节点才会写入到内存。因为一般情况下，打开的文件个数有限，所以极大的减少了占用的内存空间。

i节点存在的一个问题是，如果每个i节点只能存储固定数量的磁盘地址，那么当一个文件所含的磁盘块数量超出一个i节点的所容纳的数目，解决方案是：可以有两个或更多个包含磁盘地址的块，或者指向其他存放地址的磁盘块的地址。

（e） 目录的实现

操作系统利用用户给出的路径名找到相应目录项。目录项中提供了查找文件磁盘块所需要的信息。目录系统的主要功能是把ASCII文件名映射成定位文件数据所需的信息。也就是说根据ASCII文件名可以找到文件所包含的磁盘块信息。每个目录项包含一些目录项以及文件i节点（或者顺序存储的文件磁盘地址，链表分配的第一个块的编号等）。

（3）虚拟文件系统（文件创建打开读写关闭删除等操作）

因为不同操作系统的文件系统不同，所以会采用虚拟文件系统（Vitrual File System）概念尝试将多种文件系统统一成一个有序的框架。关键的思想就是抽象出所有文件系统共有的部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来具体管理数据。虚拟文件系统不需要管这个数据是来自磁盘，还是来自网络，只需要拿到文件描述符，进行读取操作。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

书中描述所有的IO都可以看做文件读写。包括网络IO，磁盘IO等。

（4）文件系统管理和优化

磁盘块划分多大来平衡磁盘空间利用率和磁盘访问时间效率，使用和空闲磁盘块采用何种数据结构进行记录以方便磁盘空间的分配和释放， 磁盘对不同用户开放权限和实用配额的设置。这些都是磁盘空间管理需要解决的问题。

另一方面为了应对人为的或者天灾的意外的文件系统的破坏，需要对文件系统进行备份。由于在数据全部写回磁盘之前存在系统崩溃的可能，从而导致文件系统的不一致。所以会考虑采用日志文件系统记录相关的操作历史记录以方便恢复。一般采用高速缓存，提取预读数据，以及顺序存取减少磁盘臂的移动等方法来优化文件系统的性能。

4. 互斥和锁 （1）什么是死锁

由于计算机系统中有很多独占性的资源，比如打印机，系统内部表项等。当两个进程同时使用一个独占资源，就有可能引起死锁。死锁的规范定义如下：

如果一个进程集合中的每一个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

由于所有的进程都需要其他进程促发才能执行，所以导致所有的进程都处于等待和休眠的状态。

可以采用资源分配图来分析该进程集合是否会发生死锁。如果资源分配图中有环路，则该环路的进程集合会发生死锁。

资源死锁发生的四个必要条件： a） 互斥条件 b） 占有和等待条件 c） 不可抢占条件 d） 环路等待条件

只有同时满足以上四个条件，才会引起死锁。换句话说，我们可以通过破坏其中的任一条件来避免死锁。也就是我们接下来要探讨的如何检测死锁，从而避免死锁并修复死锁。

（2）如何避免死锁并修复死锁

一种方法就是无视它（画外音，没想到无视也是一种解决棘手的计算机问题的算法…）

第二种方法就是死锁的检测和恢复。针对每种类型一个资源的一种算法就是检测资源图中是否有环路。若资源图中有环路，则说明存在死锁。检测环路的方法是每次选择资源图中的某一个节点作为起点，采用深度优先遍历看其最后是否回到遍历途径的点。如果资源图所有节点都被用作起点进行深度优先仍然没有检测到环路，则说明该进程集不存在死锁。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

针对每种类型资源多个资源的死锁检测，采用矩阵来标识各种类型资源现有资源数，可用资源数以及进程n分配。每次给一个可以满足其资源需求的进程分配资源，进行执行完毕之后，释放资源。如果所有的进程都能执行完毕，则说明该资源集合不会发生死锁，否则说明可能发生死锁。

恢复死锁则可以通过破坏死锁产生的四个必要条件来进行，首先破坏第三个条件，利用抢占来恢复，比如cpu资源是独占资源，一个cpu只能执行一个进程。如果某个进程想使用cpu资源，则可以采用进程切换来抢占cpu资源。

通过杀死进程恢复，破坏第四个条件，这样就等于是解开环路，因为环路中一个进程消失。当然杀死环路外的进程不一定能避免死锁。

通过回滚恢复，就倒退到进程执行的某个时间点，可能在这个时间点，该进程某些资源暂时不需要。

如何避免死锁，Dijkstra提出了一种能够避免死锁的调度算法，称为银行家算法。该银行家算法采用的是空闲的资源数能否满足某一进城的最大需求，如果能满足某一进程的最大需求，就称该状态是暂时安全的，然后满足该进程，执行该进程完毕后释放资源，直至所有进程执行完毕。如果整个过程都无法满足某一进程其资源需求，则说明状态是不安全的，也就是可能存在死锁。

如何预防死锁，就是破坏死锁的四个必要条件。比如打印机资源，采用假脱机打印机资源，所有需要打印的进程都可以访问假脱机

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

打印资源，该资源可以同时输出。打印机资源只有一个后台的daemon可以访问，这样确保打印机只有一个进程可以使用。整个文件完整的输出之后，该daemon使用打印机打印出资源。

防止独占资源引起死锁的一个小思路是：避免分配那些不是绝对必须的资源，尽量做到尽可能少的进程可以真正请求资源。

另一种破坏占有和等待条件的方法是，要求当一个进程请求资源时，先暂时释放当前占用的所有资源，然后再尝试一次获得所需的全部资源。

5. linux操作系统

先八卦下，在看关于linux操作系统这一章的时候，我很想知道Andrew S.Tanenbaum是怎么评价linux操作系统滴，(*^__^*) 嘻嘻……，在Linus的自传《Just For Fun》中有叙述其与Andrew的一段邮件掐架。于是我怀着这样滴小心情看这一章。总的来说还是挺客观的，分析了minix没有流行，而linux操作系统迅速发展的原因，并且讲述了minix和linux的设计差别。

还是说说主角Linux操作系统。Unix系统的设计原则：  能够同时处理多进程和多用户的交互式系统。

 让系统尽量简单，优雅，并且具有一致性（最少学习成本）  系统有较强的功能型和灵活性  每个程序应该只做一件事并且把它做好  尽量减少冗余

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

Linux操作系统其需要的是一个佣人，而不是保姆。（换句话说其只需要一个执行者，不需要一个协作者）

Linux系统中的层次结构：

Shell——非常强大的命令行界面（多用户多程序，管道，正则表达式）

Linux命令行用户界面包含大量的标准应用程序： -文件和目录操作命令 -过滤器

-程序设计工具，如编辑器和编译器 -文档处理 -系统管理 -其他

参见P415的Linux内核结构，理解Linux操作系统。I/O部件，内存管理部件和进程管理部件。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

I/O部件——对一个文件进行读操作，不论是在内存还是在磁盘中，都和终端输入中读取一个字符是一样的。从底层来看，所有的I/O操作都要通过某一个设备驱动器。所有的Linux驱动程序都可以被分类为字符驱动程序或块驱动程序。两者之间的主要区别是块设备允许查找和随机访问而字符设备不允许。

进程和线程 内存管理 文件系统

6. 与工作相关的内容

一个家庭作业——如何优化你的电脑速度，以及如何优化你的手机速度（腾出空间，卸载程序，减少开机启动，磁盘碎片整理）

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

（1） coding

——考虑系统资源的（磁盘，cpu，内存）

比如写导库或导日志脚本的时候要考虑数据库过大可能引起磁盘爆满。

比如对大文件使用awk或者sort等命令的时候，考虑机器内存。可能引起内存使用率过高。

比如fork子进程的时候，要考虑cpu的。为了避免所有核都占用，可以使用taskset来空出一两个核，同事fork子进程个数不要太多。

以上是考虑的是程序占用的系统资源，还要考虑redis所需要的资源，比如考虑业务增长和机器成本，redis要开多大内存，还要考虑qps，从而考虑同时使用多少个redis。

这些都需要在工作和实践中慢慢摸索，目前我还只是旁观者。

（2） 系统优化

——分析系统性能瓶颈（哪个资源不足导致性能下降，cpu，内存，磁盘，网络io等）

有的情况系统需要满足一定业务性能需求，需要满足一定的qps。这时候除了从硬件上考虑（扩展机器，扩展进程数，扩展redis，db资源等），也可以从程序逻辑上考虑，如何优化程序逻辑，让其查本地，不进行网络通信，减少网络io，或者在程序上考

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

虑，通过查缓存减少查询db的次数，或者优化程序本身逻辑，让其更少的运算次数，更少的资源操作。

（3）多进程并发——时序

曾经看到一篇文章叫做《程序员的修禅之道》，里面说单线程优于多线程。我当时只是单纯的以为单线程优于多线程是因为其“专注”。后来工作发现很多业务为了能够提高性能，多是采用多进程并行处理的模式。这个时候我并不认为单线程优于多线程。以至于每次老大要我处理数据，我都想着采用多进程处理。其实老大交给我的事情多半不是很紧急的事情，所以其实对时效性没什么要求，我只是为了臭摆，认为多进程比单进程高级，到后来写到一半发现进程之间不能通信，知道自己被自己坑了。

在后来填坑的过程中，发现很多问题都是因为多进程并发处理引起的。因为一个资源同时被多个程序操作，他们之间可能相互影响。比如之前说过当删除redis的一个中存了几千万数据的key，redis会被锁住几秒到十几秒，此时redis不能进行任何其他操作，其他程序操作该redis失败。比如父子进程共享文件描述符，如果各自职责没划分清楚的话，可能导致越界从而出错。比如多个进程共享一个变量，如果你写程序的时候，单纯的以为就一个程序（或者任务）在操作它，然后用完就删除或者重置这个变量，最后结果导致另外一个程序（或者任务）操作这个变量失败。比如多个程序操作一个变量，在一个程序获取这个变量，并且正准备修改这个变量的状态时候，这个变

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

量已经被其他程序读走，而且读取了没有更新的状态从而导致其他程序出错。

（4）fall in love with computer

——know how to work about computer

code和debug就像你在跟程序谈恋爱，你要抱着bug虐我千百遍，我待bug如初恋的心态，要非常耐心，静下心来站在他的角度理解他，一遍遍的试探和探寻，从而逐步摸清他的心性，用他所擅长的方式跟他沟通，他自然也会给你相应的惊喜。

7. 后记

其实操作系统主要就是进行各个资源（CPU，内存，磁盘，输入输出等）的管理。而为了实现多道程序设计，则需要对资源进行时间上或者空间上的多路复用。时间上，各个进程个执行多长时间，执行的顺序是怎样的？各个进程占用多少内存？出现缺页中断，将哪个进程内存置换出来？所以CPU的进程调度就涉及时间片轮转，每个进程运行一个时间片。对于有些优待的进程，可能会设置优先级，优先级别高的进程先占用cpu。对于运行时间长的进程可以给与更多时间片，但随着时间片给予更多，其优先级也随之下降。而内存分配，是将内存进行分页，将进程各个部分分别装入各个虚拟内存页面。虚拟内存和物理内存相互映射，如果虚拟内存无法映射到物理内存，将引起缺页中断。此时需要将最久很少使用的页面中的内容换出，如果该

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通

抽象的概念，实现以及如何使用它解决问题

页面中存储的是脏数据，则需要将该数据写回到磁盘。如果是干净页面，则无需重新写回磁盘。在这个过程中之所以要进行资源的协调，是因为多个进程争抢资源。为了充分利用资源，就需要兼顾效率与公平。

本书基本上都是本着提出问题->解决问题->方法的适用场景及其优缺点->针对上一方法的缺点提出更好的方法。看了整本书让我深深明白了坑是填不完滴，因为需求会变化。根据具体业务需求而变更相应滴系统设计和实现。

记得附上《现代操作系统》读书笔记网上版本。这样方便查看。

想象其对你工作的意义，能不能打什么比方更好理解，能不能融会贯通