操作系统，揭开钢琴的盖子-6

C++软件与嵌入式软件面经解析大全（蒋豆芽的秋招打怪之旅）

本章讲解点

• 1.1 操作系统的来历
• 1.2 操作系统的功能
• 1.3 操作系统的硬件知识
• 1.4 linux下编译程序
• 1.5 Makefile
• 1.6 linux的常用指令
• 1.7 进程的概念
• 1.8 进程的状态转换
• 1.9 进程的创建
• 1.10 守护进程
• 1.11 僵尸进程与孤儿进程
• 1.12 wait()或waitpid()系统调用
• 1.13 进程通信——管道
• 1.14 进程通信——系统IPC
• 1.15 进程通信——socket套接字
• 1.16 线程
• 1.17 线程的创建
• 1.18 线程通信——互斥锁
• 1.19 线程通信——信号量
• 1.20 线程通信——条件变量
• 1.21 线程通信——读写锁
• 1.22 线程池
• 1.23 协程
• 1.24 虚拟内存
• 1.25 页表
• 1.26 缺页中断
• 1.27 缺页置换算法
• 1.28 锁
• 1.29 操作系统资源调度方法
• 1.30 IO模型类型

受众：本教程适合于C/C++已经入门的学生或人士，有一定的编程基础。

本教程适合于互联网、嵌入式软件求职的学生或人士。

故事背景

蒋 豆 芽：小名豆芽，芳龄十八，蜀中人氏。卑微小硕一枚，科研领域苟延残喘，研究的是如何炒好一盘豆芽。与大多数人一样，学习道路永无止境，间歇性踌躇满志，持续性混吃等死。会点编程，对了，是面对对象的那种。不知不觉研二到找工作的时候了，同时还在忙论文，豆芽都秃了，不过豆芽也没头发啊。

隔壁老李：大名老李，蒋豆芽的好朋友，技术高手，代码女神。给了蒋豆芽不少的人生指导意见。

导 师：蒋豆芽的老板，研究的课题是每天对豆芽嘘寒问暖。

故事引入

蒋 豆 芽：老李，最近实在太忙了啊，又要搞论文，又要找工作，简直分身乏术，我也有点想请教一下罗志凶如何进行时间管理了。（笑容邪魅）

隔壁老李：（敲脑袋）豆芽，你可不能搞那些花里胡哨的，瓜要吃，学习还要继续搞。今天我们就要来讲讲操作系统的知识。接下来我们讲虚拟内存。

1.24 虚拟内存

隔壁老李：是的，接下来我们讲新的知识点：操作系统的虚拟内存机制。

虚拟内存是一种内存管理技术。虚拟内存技术使得不同的进程在运行过程中，它所看到的是自己独占的4G内存空间。所有进程共享同一物理内存，每个进程只把自己的虚拟内存空间映射并存储到物理内存上。如图可以直观看到：

两个进程P1和P2都有自己的虚拟内存空间，但是最后都会映射到物理内存空间，只是P1和P2自己不知道而已，它们以为自己就是拥有独立内存空间。

蒋 豆 芽：哦？看样子操作系统偷偷给进程们画大饼啊！（捂嘴）那这有什么好处呢？

隔壁老李：虚拟内存的好处：

（1）扩大地址空间。每个进程独占一个4G空间，虽然真实物理内存没那么多。

（2）内存保护：防止不同进程对物理内存的争夺和践踏，可以对特定内存地址提供写保护，防止恶意篡改。

（3）可以实现内存共享，方便进程通信。

（4）可以避免内存碎片，虽然物理内存可能不连续，但映射到虚拟内存上可以连续。

虚拟内存的代价：

（1）虚拟内存需要额外构建数据结构，占用空间。

（2）虚拟地址到物理地址的转换，增加了执行时间。

（3）页面换入换出耗时。

（4）一页如果只有一部分数据，浪费内存。

蒋 豆 芽：凡事有利就有弊，好像又有点哲学的味道了，哈哈！那虚拟内存怎么实现呢？

1.25 页表

隔壁老李：豆芽，先别急，我们来理清一些概念。

（1）分页和页表：虚拟内存是操作系统里的概念，对操作系统来说，虚拟内存就是一张张的对照表，P1 获取 A 内存里的数据时应该去物理内存的 A 地址找，而找 B 内存里的数据应该去物理内存的 C 地址。

我们知道系统里的基本单位都是 Byte 字节，如果将每一个虚拟内存的 Byte 都对应到物理内存的地址，每个条目最少需要 4字节（32位虚拟地址->32位物理地址），在 4G 内存的情况下，就需要 16GB 的空间来存放对照表，那么这张表就大得真正的物理地址也放不下了，于是操作系统引入了页（Page）的概念。

在系统启动时，操作系统将整个物理内存以 4K 为单位，划分为各个页。之后进行内存分配时，都以页为单位，那么虚拟内存页对应物理内存页的映射表就大大减小了，4G 内存，32位操作系统虚拟地址空间是2^32，假设每页分为4k，需要 (2^32/(4*2^10))*4 = 4M的空间，只需要 4M 的映射表即可，一些进程没有使用到的虚拟内存，也并不需要保存映射关系，而且Linux 还为大内存设计了多级页表，可以进一页减少了内存消耗。操作系统虚拟内存到物理内存的映射表，就被称为页表。

隔壁老李：我们举个形象的例子，就如同一本书，如果把整个书给摊开，那占地面积太大了，所以书才要分页，节约空间。

（2）内存寻址和分配：我们知道通过虚拟内存机制，每个进程都以为自己占用了全部内存，进程访问内存时，操作系统都会把进程提供的虚拟内存地址转换为物理地址，再去对应的物理地址上获取数据。

CPU 中有一种硬件，内存管理单元 MMU（Memory Management Unit）专门用来将翻译虚拟内存地址。CPU 还为页表寻址设置了缓存策略，由于程序的局部性，其缓存命中率能达到 98%。

以上情况是页表内存在虚拟地址到物理地址的映射，而如果进程访问的物理地址还没有被分配，系统则会产生一个缺页中断，在中断处理时，系统切到内核态为进程虚拟地址分配物理地址。

蒋 豆 芽：老李，讲了这么多，虚拟内存到底是如何寻址呢？

隔壁老李：我们以三级页表机制介绍，对于大内存需求，操作系统甚至可以四、五级页表寻址，但是原理和三级页表寻址机制是一样的，接下来我们具体介绍。

隔壁老李：操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，叫页表。页表的内容就是该进程的虚拟地址到物理地址的一个映射。页表中的每一项都记录了这个页的基地址。

三级页表转换方法：（两步）

（1）逻辑地址转线性地址：段起始地址+段内偏移地址=线性地址

（2）线性地址转物理地址：

每一个32位的线性地址被划分为三部分：页目录索引（10位）、页表索引（10位）、页内偏移（12位）

• 从cr3中取出进程的页目录地址（操作系统调用进程时，这个地址被装入寄存器中）
• 页目录地址 + 页目录索引 = 页表地址
• 页表地址 + 页表索引 = 页地址
• 页地址 + 页内偏移 = 物理地址

转换如图所示：

隔壁老李：怎么样？豆芽，上面应该讲得很清楚了吧？

1.26 缺页中断

蒋 豆 芽：嗯嗯，是的！对了，老李，刚才提到了缺页中断又是怎么回事？

隔壁老李：首先我们先弄清缺页异常：malloc和mmap函数在分配内存时只是建立了进程虚拟地址空间，并没有分配虚拟内存对应的物理内存。当进程访问这些没有建立映射关系的虚拟内存时，处理器自动触发一个缺页异常。

缺页中断：缺页异常后将产生一个缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

蒋 豆 芽：那缺页中断和一般中断有什么区别？面试肯定也会问，我拿小笔记本记好。

隔壁老李：缺页中断与一般中断一样，需要经历四个步骤：保护CPU现场、分析中断原因、转入缺页中断处理程序、恢复CPU现场，继续执行。

缺页中断与一般中断区别：

（1）在指令执行期间产生和处理缺页中断信号

（2）一条指令在执行期间，可能产生多次缺页中断

（3）缺页中断返回的是执行产生中断的一条指令，而一般中断返回的是执行下一条指令。

1.27 缺页置换算法

隔壁老李：再多说几句，缺页当然涉及到缺页置换算法，缺页异常发生后将产生一个缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。但是，此时内存已没有空闲空间，就需要从内存中调出一页程序或数据，送入到磁盘的对换区。这个选择调出页面的方法就叫缺页置换算法：

先进先出（First In First Out, FIFO）算法：队列，删除队首的页即可

最近最久未使用置换（Least Recently Used，LRU）算法：置换最近一段时间以来最长时间未访问的页面。

最近最少使用（Least Frequently Used，LFU）算法：置换最近一段时间以来访问频率最低的页面。

蒋 豆 芽：大名鼎鼎的LRU啊，面试太容易考了，老李，你给我讲讲吧。

隔壁老李：行，那我们重点讲讲这个算法吧。LRU算法用于缓存淘汰。

思路是将缓存中最近最少使用的对象删除掉。

实现方式是利用链表和哈希表。

具体的做法是：当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。

在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

我们给出C++的具体实现，代码一看就懂了。

class LRUCache {  
    list<pair<int, int>> cache;//创建双向链表  
    unordered_map<int, list<pair<int, int>>::iterator> map;//创建哈希表  
    int cap;  
public:  
    LRUCache(int capacity) {  
        cap = capacity;  
    }  

    int get(int key) {  
        if (map.count(key) > 0){  
            auto temp = *map[key];  
            cache.erase(map[key]);  
            map.erase(key);  
            cache.push_front(temp);//把该节点移到链表头部  
            map[key] = cache.begin();//映射头部  
            return temp.second;  
        }  
        return -1;  
    }  

    void put(int key, int value) {  
        if (map.count(key) > 0){  
            cache.erase(map[key]);  
            map.erase(key);  
        }  
        else if (cap == cache.size()){//若缓存满了，则把链表最后一个节点删除  
            auto temp = cache.back();  
            map.erase(temp.first);  
            cache.pop_back();  
        }  
        cache.push_front(pair<int, int>(key, value));//新建一个节点，放到链表头部 
        map[key] = cache.begin();//映射头部  
    }  
};  
/** 
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); 
*/ 

蒋 豆 芽：太棒了！

隔壁老李：然后我们开始讲锁。

1.28 锁

隔壁老李：在前面几章中，锁被用于进程线程的同步问题，我们已经初步感受到了锁的魅力。

蒋 豆 芽：那老李，锁在操作系统里实现机制是什么呢？

隔壁老李：所谓的锁，其实就是一个变量，拥有两种状态：1表示空闲状态，0表示上锁状态。加锁时，判断锁是否空闲，如果空闲，修改为上锁状态，返回成功；如果已经上锁，则返回失败。解锁时，则把锁状态修改为空闲状态。

加锁过程可以表示为：（1）读锁。（2）判断锁状态。（3）如果已加锁，失败返回。（4）把锁设置为加锁状态。（5）返回成功。

虽然每一步是原子性的，但是每一步之间却是可以中断的。比如进程A在执行完2后发生中断，中断中进程B也执行了加锁过程，返回中断后就会发生两个进程都会加锁。

对于这个问题，计算机已经解决，方法是采用原子级汇编指令test and set 和swap。两个指令为原子操作。

蒋 豆 芽：你看我这样理解对不对。我们采用互斥锁保护临界区，从而防止竞争条件。也就是说，一个线程在进入临界区时应得到锁；它在退出临界区时释放锁。函数 acquire() 获取锁，而函数 release() 释放锁，如图 ：

每个互斥锁有一个布尔变量 available，它的值表示锁是否可用。如果锁是可用的，那么调用 acquire() 会成功，并且锁不再可用。当一个线程试图获取不可用的锁时，它会阻塞，直到锁被释放。

按如下定义 acquire()：

acquire() {  
    while (!available);  
    /* busy wait */  
    available = false;  
}  

按如下定义release()：

release() {  
    available = true;  
}  

隔壁老李：没错，豆芽。互斥锁其实就是一个bool型变量，为true时表示锁可获取，为false时表示已上锁。这里说的是互斥锁，其实是泛指linux中所有的锁机制。

隔壁老李：我们总结一下锁的种类。因为我们之前都讲过了，如果忘了再复习下前面的内容，这里就简单总结一下：

（1）互斥锁：mutex，保证在任何时刻，都只有一个线程访问该资源，当获取锁操作失败时，线程进入阻塞，等待锁释放。

（2）读写锁：rwlock，分为读锁和写锁，处于读操作时，可以运行多个线程同时读。但写时同一时刻只能有一个线程获得写锁。

互斥锁和读写锁的区别：

（a）读写锁区分读锁和写锁，而互斥锁不