前记

这本书的英文名字是《Operating Systems：Three Easy Pieces》(吐槽下中文翻译，很不搭的感觉)，作者是Remzi H.Arpaci-Dusseau.英文起名还有一个梗：Remzi期望这本书能够像理查德费曼写过一些物理学的讲义，他把一些基本内容汇集成一本书，叫做《Six Easy Pieces》。这本书探讨的又正好是操作体系的3个简略部分，所以取名很适宜，由于操作体系的难度差不多是物理学的一半。这本书的英文电子版是免费的，Remzi说这本书之所以免费，是由于从前他有一个学生由于买不起书而向他求助，这让他很受触动，从此他决议揭露此书资源，Remzi人真的很好！

概述和理念

整本书环绕虚拟化、并发和耐久性这三个首要概念打开，介绍了一切操作体系的首要组件。这本书并不是一股脑的把一些结论性质的东西放出来，而是从引出问题动身，一步步引导读者去思考操作体系是怎么开展到现在这样的。

这本书的每一个章节都配套了习题，都是完全开源免费的，咱们只需求跟着readme照葫芦画瓢就好，链接我放在这儿： github.com/remzi-arpac… 代码需求在Linux环境下运转，Windows电脑的朋友能够下个虚拟机，我是用Oracle VM VirtualBox装的Ubuntu。

我在看书之前听了一遍清华的操作体系原理课程，课程的许多内容和这本书是很像的，b站就能够看到课程，这儿也引荐给读者：www.bilibili.com/video/BV1uW…

书中作者写给读者的话让我深受触动：

叶芝有一句名言：“教育不是注满一桶水，而是点着一把火。”他说的既对也错。你必须“给桶注一点水”，这本书当然能够协助你完结这部分的教育。毕竟，当你去Google面试时，他们会问你一个关于怎么运用信号量的技巧问题，切当地知道信号量是什么感觉真好，对吧？

可是叶芝的首要观念显而易见：教育的真实关键是让你对某些事情感兴趣，能够独立学习更多关于这个主题的东西，而不仅仅是你需求消化什么才干在某些课程上取得好成绩。正如咱们的父亲（Remzi的父亲Vedat Arpaci）从前说过的，“在讲堂以外学习。”

今日想要写一篇小结，大致总结下自己学到的常识而且同享一些常见的笔试面试题，也顺便同享这个理念。

正文小结

虚拟化

咱们为什么要进行虚拟化呢？其实很简略，由于核算机的硬件资源是有限的，而经过操作体系，咱们能够愈加有效的运用物理资源。本书中的虚拟化过程，便是在竭尽所能的达到这个意图。前几章是在引进进程的概念，简略的介绍了几个常用API：fork()、exec()、wait()，读者能够依据自己兴趣或许课后习题，写一些简略的程序了解它们。然后就来到了虚拟化部分的第一个大件：CPU。

为了虚拟化CPU，操作体系需求以某种方法让许多使命同享物理CPU，让它们看起来像是同时运转。基本思维很简略，运转一个进程一段时刻，然后运转另一个进程，如此轮换。经过这种方法时分同享CPU，就完结了虚拟化。

想象一下，运转程序最快的方法是不是直接把程序放到CPU傍边运转？当然是！但问题是，假如这个程序做了一些很离谱的事情，咱们该怎么让它停下来？以及出于虚拟化CPU的意图，现已运转的程序（也便是进程），操作体系怎么让它停下来，切换到另一个进程？为此，便引申了出来一些底层机制，读者可依据关键词做进一步了解（用户形式和内核形式、协作方法和非协作方法、时钟中止），这部分是比较概念性的东西，逻辑难度并不大，首要是为了适应专业词汇。

了解了底层机制，咱们便开始学习操作体系的上层战略了，接下来这本书介绍了一系列的调度战略，这部分也是面试傍边常被问到的：先进先出（FIFO）、最短使命优先（SJF）、最短完结时刻优先（STCF），多级反馈行列（MLFQ）、单行列多处理器调度和多行列多处理器调度（当然也是有单行列单处理器调度和多行列单处理器调度的哈哈）。调度战略并非只要这几种，规划人员能够依据不同的指标去规划不同的战略。这本书还引进了比例比例调度的概念，简略评论了两种完结：彩票调度和步长调度，简略来说，前者是随机的，后者是确认的。

其中单行列的方法（SQMS）比较容易构建，负载均衡较好，但在扩展性和缓存亲和度方面有着固有的缺陷。多行列的方法（MQMS）有很好的扩展性和缓存亲和度，但完结负载均衡却很困难，也更复杂。

这部分的话，了解它们的机理今后是能够很天然的用自己的方法表述出来的。然后由于我上学期喜爱刷力扣学习，所以这儿也引荐读者结合一些详细场景的代码，问题导向的话，许多笼统的概念就显得简略了一些。比方下面这个是力扣的621题，我暂时也只写了这个，同理还有力扣的1834题、636题，还有些其他场景，也很类似，比方第10题和第993题。下面这个是我第621题的解法：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        if(n == 0){
            return tasks.size();
        }
        vector<int> freq(26,0);
        for(char task:tasks){
            freq[task - 'A']  ;
        }
        sort(freq.begin(),freq.end());
        int max_freq = freq[25];
        int idle_slots = (max_freq-1)*n;
        for(int i= 24; i>=0 && idle_slots>0;--i){
            idle_slots -= min(max_freq - 1, freq[i]);
        }
        idle_slots = max(0,idle_slots);
        return tasks.size()   idle_slots;
    }
};

CPU虚拟化的部分到这儿就完毕了，接下来是另一个大件：内存虚拟化。

如上所说，咱们的物理资源是有限的，物理内存天然也是有限的，咱们经过虚拟内存技能，能够愈加有效的运用实际物理内存，构成一种“内存”（地址空间）比物理内存大许多的现象，这个过程需求操作体系和硬件合作完结。

实际上，作为用户级的程序员，能够看到的任何地址都是虚拟地址。

本书简略介绍了一些内存操作的API，malloc1()、free()等等，而后开始介绍地址转换机制的开展历程。从简略的思维动身，基址和界限开始，然后渐渐添加复杂性，分段、分页，TLB、混合分段和分页、多级页表、反向页表等等。这一部分的关键之处是规划适宜的映射方法，多个进程或许同一进程的不同虚拟页面能够映射到同一块物理内存，然后完结了一种形式的内存同享。这种映射关系是动态的，能够依据应用程序的需求进行调整。

在了解基本机制后，这本书介绍了几种常见的缓存战略：最优替换战略、先入先出战略、随机、运用历史数据（LRU）。相同缓存战略也能够在力扣里找到练习题，第146题的LRU和第460题的LFU，LRU要简略些，我暂时只写了LRU：

class LRUCache {
public:
    struct Node{
        int key, value;
        Node * prev;
        Node * next;
        Node(int k, int v){
            this->key = k;
            this->value = v;
        }
    };
    int cap;
    Node* head = new Node(-1,-1);
    Node* tail = new Node(-1,-1);
    unordered_map<int,Node*> map;
    LRUCache(int capacity) {
        cap = capacity;
        head->next = tail;
        tail -> prev = head;
    }
    void addNode(Node* newnode){
        Node* temp = head -> next;
        newnode -> next = temp;
        newnode -> prev = head;
        head -> next = newnode;
        temp -> prev = newnode;
    }
    void deltNode(Node* delnode){
        Node* prevv = delnode -> prev;
        Node* nextt = delnode -> next;
        prevv -> next = nextt;
        nextt -> prev = prevv;    
    }
    int get(int key) {
       if(map.find(key)!=map.end()){
           Node* resultNode = map[key];
           int result = resultNode->value;
           deltNode(resultNode);
           addNode(resultNode);
           map[key] = head->next;
           return result;
       }
       return -1;
    }
    void put(int key, int value) {
        if(map.find(key)!= map.end()){
            Node* current = map[key];
            map.erase(key);
            deltNode(current);
        }
        if(map.size()==cap){
            map.erase(tail->prev->key);
            deltNode(tail->prev);
        }
        addNode(new Node(key,value));
        map[key] = head ->next;
    }
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

这是我习惯用的方法，可是时刻复杂度不能打败100％，欢迎看到这篇文章的朋友同享更好的方法。

最终这本书在简略介绍了VAX/VMS虚拟内存体系之后，虚拟化部分就完毕了。当然，在本书的最终还做了一部分弥补常识，简略介绍了虚拟机管理程序，咱们能够将其了解成操作体系之下的操作体系，它是介于操作体系和硬件之间的。

并发

接下来是第二部分：并发，这部分从外表的问题来看，和数据库的进程事务管理很像。当然，虽然在外表上看起来类似，可是操作体系和数据库体系的方针和重视点不一样，处理并发问题的详细机制和战略或许会有所不同。

之前咱们现已知道，进程便是一个正在运转的程序，在这儿咱们需求引进一个新的概念，叫做线程。这儿也有一个常见的面试题，进程和线程的差异？ 这儿直接引用原文：

经典观念是一个程序只要一个履行点（一个程序计数器，用来存放要履行的指令），但多线程（multi-threaded）程序会有多个履行点（多个程序计数器，每个都用于取指令和履行）。换一个角度来看，每个线 程类似于独立的进程，只要一点差异：它们同享地址空间，然后能够拜访相同的数据。

因而，单个线程的状况与进程状况十分类似。线程有一个程序计数器，记载程序从哪里获取指令。每个线程有自己的一组用于核算的寄存器。所以，假如有两个线程运转在一个处理器上，从运转一个线程（T1）切换到另一个线程（T2）时，必定产生上下文切换。线程之间的上下文切换类似于进程间的上下文切换。关于进程，咱们将状况保存到进程操控块。现在，咱们需求一个或多个线程操控，保存每个线程的状况。可是，与进程相比，线程之间的上下文切换有一首要差异：地址空间保持不变（即不需求切换当前运用的页表）。线程和进程之间的另一个首要差异在于栈。在简略的传统进程地址空间模型【咱们现在能够称之为单线程（single-threaded）进程】中，只要一个栈，通常坐落地址空间的底部（见图 26.1 左图）。

然而，在多线程的进程中，每个线程独立运转，当然能够调用各种例程来完结正在履行的任何作业。不是地址空间中只要一个栈，而是每个线程都有一个栈。假设有一个多线程的进程，它有两个线程，成果地址空间看起来不同（见图26.1右图）。

或许在不同的当地会给这些问题不同的定义，但其实本质都类似这样的场景：有一个变量a = 1，进程T1履行a=a 1, 进程T2也履行a=a 1，进程T1履行这个操作的时候a=1，履行a 1后a等于2，这时候a=2的成果还没有回来，进程T2忽然抢断了进程T1，这个时候a依然是等于1的，履行a=a 1,回来成果a=2。T1继续履行操作，回来a=2。问题就呈现了，经历了T1和T2，按理说a应该等于3的，成果等于2。

这一整个章节都是在结合详细的场景，给出相应的处理方案，关键之处在于规划合理的数据结构和函数，以及在正确的当地调用相应函数，这也是这一章最难的当地。

本书一开始还是介绍了一些线程的API，然后介绍了锁、临界区、互斥、条件变量，然后引进信号量的概念。咱们能够看一个经典的出产者-顾客比如：

sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i  ) {
sem_wait(&mutex); // line p0 (NEW LINE)
sem_wait(&empty); // line p1
put(i); // line p2
sem_post(&full); // line p3
sem_post(&mutex); // line p4 (NEW LINE)
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i  ) {
sem_wait(&mutex); // line c0 (NEW LINE)
sem_wait(&full); // line c1
int tmp = get(); // line c2
sem_post(&empty); // line c3
sem_post(&mutex); // line c4 (NEW LINE)
printf("%dn", tmp);
}
}
int main(int argc, char *argv[]) {
// ...
sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
sem_init(&full, 0, 0); // ... and 0 are full
sem_init(&mutex, 0, 1); // mutex=1 because it is a lock (NEW LINE)
// ...
} 

整个场景是这样的：出产者只要在某个区域“空了”（empty）的状况下才干继续履行，然后它会在这个区域“出产”（put），直到出产“满了”（full），添加这个条件（sem_post(&full)），然后不再占用锁（sem_post(&mutex)）。

顾客只要在某个区域“满了”（full）的状况下才干继续履行，然后它会把这个区域“消费”（get），直到消费“空了”（empty），添加这个条件（sem_post(&empty)），然后不再占用锁（sem_post(&mutex)）。

这儿就呈现了典型的死锁状况：

假设有两个线程，一个出产者和一个顾客。顾客首要运转，获得锁（c0 行），然后对 full 信号量履行 sem_wait() （c1 行）。由于还没有数据，所以顾客堵塞，让出 CPU。可是，重要的是，此刻顾客依然持有锁。

然后出产者运转。假如出产者能够运转，它就能出产数据并唤醒顾客线程。惋惜的是，它首要对二值互斥信号量调用 sem_wait()（p0 行）。锁现已被持有，因而出产者也被卡住。

这儿呈现了一个循环等候。顾客持有互斥量，等候在 full 信号量上。出产者能够发送full 信号，却在等候互斥量。因而，出产者和顾客相互等候对方——典型的死锁。

正确做法是这样的：

sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i  ) {
sem_wait(&empty); // line p1
sem_wait(&mutex); // line p1.5 (MOVED MUTEX HERE...)
put(i); // line p2
sem_post(&mutex); // line p2.5 (... AND HERE)
sem_post(&full); // line p3 
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i  ) {
sem_wait(&full); // line c1
sem_wait(&mutex); // line c1.5 (MOVED MUTEX HERE...)
int tmp = get(); // line c2
sem_post(&mutex); // line c2.5 (... AND HERE)
sem_post(&empty); // line c3
printf("%dn", tmp);
}
}
int main(int argc, char *argv[]) {
// ...
sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
sem_init(&full, 0, 0); // ... and 0 are full
sem_init(&mutex, 0, 1); // mutex=1 because it is a lock (NEW LINE)
// ...
} 

还有一个经典的哲学家就餐问题，读者能够参阅力扣1226题。简略来说，好的做法是隔一个哲学家同时进餐，怎么规划呢？然后本书介绍了一些常见的并发问题，这个死锁依赖图给我感觉也很nice哈哈：

接着总结了产生死锁的四个条件，这部分也是常呈现的面试题。最终是进阶课程：根据事情的并发。并发性这一章节也就完毕了。

其实读下来能够也能够感觉到，这一章节重要的是了解各种概念，然后怎么规划数据结构和函数去处理相应的问题，这才是真实不断发挥创造力的当地。

耐久性

最终一个章节是耐久性的问题，核心问题是怎么耐久保存数据。这一部分咱们能够学到一些硬件常识，能够了解相应过程中，操作体系是怎么同硬件打交道的，再往后能够看到操作体系是怎么同网络进行交互的。我个人期望在对组成和网络了解更多的时候再回过头来看，这儿也只是对其有个开始知道，细节的完结才是真实棘手的当地。

这一章节和核算机组成原理是有许多堆叠部分的，这儿也让我开始了解了一个困扰了我很久的问题：操作体系是怎么与设备进行交互的。

这个问题能够经过古老的笼统技能来处理。在最底层，操作体系的一部分软件清楚地知道设备怎么作业，咱们将这部分软件称为设备驱动程序。

书中这个图粗略展示了Linux软件的安排方法：

在学习这部分常识的时候，要重视一些硬件的完结，这部分能够在核算机组成原理傍边补齐。

寄存器的完结，懂得运用中止削减CPU开销，当然这也是需求就详细问题而定的：

留意，运用中止并非总是最佳方案。假如有一个十分高性能的设备，它处理恳求很快：通常在CPU第一次轮询时就能够回来成果。此刻假如运用中止，反而会让体系变慢：切换到其它进程，处理中止，再切换回之前的进程价值不小。因而，假如设备十分快，那么最好的办法反而是轮询。假如设备比较慢，那么选用允许产生堆叠的中止更好。假如设备的速度不知道，或许时快时慢，能够考虑运用混合战略，先尝试轮询一段时刻，假如设备没有完结操作，此刻再运用中止。这种两阶段的办法能够完结两种方法的优点。

另一个最好不要运用中止的场景是网络。网络端收到许多数据包，假如每一个包都产生一次中止，那么有或许导致操作体系产生活锁，即不断处理中止而无法处理用户层 恳求。例如，假设一个Web服务器由于“电杆效应”而忽然接受很重的负载。这种状况下，偶尔运用轮询的方法能够更好的操控体系的行为，并允许Web服务器先服务一些用户恳求，再回去查看网卡设备是否有更多数据包到达。

另一个根据中止的优化是兼并。设备在抛出中止之前往往会等候一小段时刻，在此期间，其它恳求或许很快完结，因而多次中止能够兼并为一次中止抛出，然后降低处理中止的价值。当然，等候太长会添加恳求的延迟，这是体系中常见的折中。

磁盘驱动器，这需求一点数学常识，可是很简略，不超过高中难度。

I/O的本钱很高，所以操作体系专门有个磁盘调度程序来查看恳求并决议下一个要调度的恳求。和使命调度不一样的当地在于，每个使命的长度是不知道的。书里介绍了一些方法：最短寻道时刻优先（SSTF）、电梯（又称SCAN或C-SCAN）、最短定位时刻优先（SPTF）。

廉价冗余磁盘阵列（RAID），为了处理下面这个问题引进的一种存储虚拟化技能：假如磁盘呈现故障，而数据没有备份，那么一切有价值的数据都没了。

本书插叙了一章文件和目录，介绍了一些常用的指令。而后简略介绍了文件体系的完结思路，以及呈现断电或许体系崩溃的状况时，更新耐久数据结构的方法。还有网络文件体系、分布式体系、Andrew文件体系等等。

经过阅览，能够大致了解操作体系是怎么与网络进行交互的，也能够引出来通讯原理的常识。到这儿，这本书就大致完毕了。

写在最终

我读这本书首要带着这个意图：在了解操作体系大致怎么运转基础上，应对学校考试和笔试面试题，以及了解操作体系作为核算机组成和核算机网络的中间件是怎么完结接口的。书里还有许多细节没有呈现在这篇文章里，我写下来的，首要是我需求的和我感兴趣的。

对待常识，我总是期望在构成开始认知后，找到自己真实感兴趣的点，让自己有足够的热情去研讨细节。若是横跨整个人生时刻区间，我期望余生都能够做自己喜爱的事。也期望在前进的路上，能够遇到更多志同道合的人。

感谢阅览。