IOS面试：操作系统
原创：面试经验型文章
创作不易，请珍惜，之后会持续更新，不断完善
个人比较喜欢做笔记和写总结，毕竟好记性不如烂笔头哈哈，这些文章记录了我的IOS成长历程，希望能与大家一起进步
温馨提示：由于简书不支持目录跳转，大家可通过command + F 输入目录标题后迅速寻找到你所需要的内容
目录
- 1、滴滴二面：进程间通信方式
- 2、什么是缓冲区溢出？危害是什么？原因是什么？
- 3、进程有哪几种状态？
- 4、分页与分段的区别？
- 5、操作系统中进程调度策略？
- 6、页面置换算法
- 7、什么是虚拟内存
- 8、中断的概念
- 9、什么是死锁？死锁产生的必要条件，如果避免？
- 10、进程与线程的区别
- 11、线程同步的方式
- 参考文献
1、滴滴二面：进程间通信方式
IPC原理：Client进程向Server进程通信，是利用进程间可共享的内核内存空间来完成底层通信工作的。
IPC方式：包括管道( pipe )、信号 ( signal ) 、信号量( semophore ) 、消息队列( message queue ) 、共享内存( shared memory ) 、套接字( socket ) 。
管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。缺点是只能承载无格式字节流以及缓冲区大小受限。
信号 ( signal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。除了用于进程间通信外，进程还可以发送信号给进程本身。不适用于信息交换，更适用于进程中断控制，比如非法内存访问，杀死某个进程等。
信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。不适用于交换大批数据，而用于多线程之间的同步。常作为一种锁机制，防止某进程在访问资源时其它进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
消息队列( message queue ) ： 消息队列是消息的链表，存放在内核中并由消息队列标识符标识。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。缺点是信息复制两次，额外的CPU消耗。
共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。无须复制，共享缓冲区直接付附加到进程虚拟地址空间，速度快。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。缺点是进程间的同步问题操作系统无法实现。
套接字( socket ) ： 更为一般的进程间通信机制，可用于不同机器之间进程间或跨网络的通信。缺点是传输效率低。
iOS 的每一个 app 都是一个独立的进程，它没有 Android那种比较开放的多进程通讯能力，甚至 App 与 Extension （如通知中心插件）之间都不能有一种非常直接的通讯方式，当然不是说iOS没有IPC 技术，mach 内核提供了诸如处理器调度、IPC (进程间通信)等非常少量的基础服务。Android 则不太一样，Android apps 基本上都需要各式各样的IPC需求，甚至启动一个Activity也需要用到IPC。
2、什么是缓冲区溢出？危害是什么？原因是什么？
缓冲区溢出是指计算机向缓冲区填充数据时超出缓冲区本身的容量，溢出的数据覆盖在合法数据上。
危害：程序崩溃，导致拒绝服务。跳转并且执行一段恶意代码。
原因：未检出用户非法输入
3、进程有哪几种状态？
就绪状态：进程已获得除处理器以外的所需资源，等待分配处理机资源
运行状态：占用处理机资源正在执行，处于此状态的进程小于等于处理器个数
阻塞状态：进程等待某种条件，在条件满足之前无法执行
4、分页与分段的区别？
相似之处：都采用离散分配方式，且都要通过地址映射机制来实现地址转换
不同之处：
- 段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的
- 段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定
- 段向用户提供二维地址空间；页向用户提供的是一维地址空间
- 段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。
5、操作系统中进程调度策略？
FCFS（先来先服务）
优先级
时间片轮转
多级反馈
6、页面置换算法
作用
缓冲池是数据库最终的概念，数据库可以将一部分数据页放在内存中形成缓冲池，当需要一个数据页时，首先检查内存中的缓冲池是否有这个页面，如果有则直接命中返回，没有则从磁盘中读取这一页，然后缓存到内存并返回。
但是内存的价值较高，一般来说服务器的内存总是小于磁盘大小的，而且内存不能完全分配给数据库作为缓冲池。这就意味着数据库基本上无法将所有的数据都缓冲到内存中。
当缓冲池满后，如果还有新的页面要被缓冲到池中，就要设计一种页面置换的算法，将一个旧的页面替换成新的页面。
最佳置换算法（OPT(MIN)算法）
选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。可惜，需要知道将来发生的事，只能在理论中存在，实际不可应用。
先进先出算法（FIFO算法）
一种很简单的算法，其基本思想是形成一个队列，最先入队的页面最先被逐出。我们用示意图来模拟一下FIFO算法：
先进先出算法（FIFO算法）
我们的内存假设只能保存4个页面，此时的访问请求按照时间顺序是1->2->3->4->5，那么按照时间顺序，当访问到4号页面时队列正好填满，当要访问5号页面时，会将最先入队的1号页面逐出。
这种算法实现起来很简单，但是从实现上来看，性能和OPT算法差距最大。因为被替换出去的页面很有可能是最常使用的页面，因此这个算法很少见出现在数据库缓冲池管理中的。
FIFO算法会出现一个叫做Belay异常的现象，就这个现象我们解释如下。
我们首先定义一个4个页面长度的队列作为缓冲池，然后按照下面的顺序访问：1->2->3->4->5->3->9->1->4->2->7->4->7。那么我们按照刚才描述的FIFO来看看访问的过程：
| 访问顺序 | 访问页 | 内存队列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1,2 | 否 |
| 3 | 3 | 1,2,3 | 否 |
| 4 | 4 | 1,2,3,4 | 否 |
| 5 | 5 | 2,3,4,5 | 否 |
| 6 | 3 | 2,3,4,5 | 是 |
| 7 | 9 | 3,4,5,9 | 否 |
| 8 | 1 | 4,5,9,1 | 否 |
| 9 | 4 | 4,5,9,1 | 是 |
| 10 | 2 | 5,9,1,2 | 否 |
| 11 | 7 | 9,1,2,7 | 是 |
| 12 | 4 | 1,2,7,4 | 否 |
| 13 | 7 | 1,2,7,4 | 是 |
从这个表格上看到，非命中次数有9次，那么我们将这个队列的容量增加到5，然后再次重复这个访问序列，看看效果：
| 访问顺序 | 访问页 | 内存队列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1,2 | 否 |
| 3 | 3 | 1,2,3 | 否 |
| 4 | 4 | 1,2,3,4 | 否 |
| 5 | 5 | 1,2,3,4,5 | 否 |
| 6 | 3 | 1,2,3,4,5 | 是 |
| 7 | 9 | 2,3,4,5,9 | 否 |
| 8 | 1 | 3,4,5,9,1 | 是 |
| 9 | 4 | 3,4,5,9,1 | 是 |
| 10 | 2 | 4,5,9,1,2 | 否 |
| 11 | 7 | 5,9,1,2,7 | 否 |
| 12 | 4 | 9,1,2,7,4 | 否 |
| 13 | 7 | 9,1,2,7,4 | 否 |
这样的话，非命中的次数是10次，奇怪的是增加了缓冲池的容量，非命中缓冲的数量还增加了，这种现象就叫做Belay异常。这种算法不应该被考虑。
最近最少使用算法 LRU(Least-Recently-Used)算法
用过去的历史预测将来，选最近最长时间没有使用的页淘汰(也称最近最少使用)。性能最接近OPT。与页面使用时间有关。LRU算法的思想也很简单，实现一个链表（双向链表），每次要缓冲新的页面时，遍历链表，选择最近最少使用的页面进行逐出操作。
这种算法要求每个页面上记录一个上次使用时间t，程序决定逐出时，以这个时间t为准，t距离当前时间最大的，就是要被逐出的页面。下图中按照1->5->2->2->6->5->4的顺序访问，内存和访问示意图如下
最近最少使用算法 LRU(Least-Recently-Used)算法
其中最接近顶端的页面我们认为其t最小，最接近底部，我们认为其t最大。访问6号页面的时候，内存被填满，下一次访问5号页面的时候，会将5号页面提升到顶部，也就是t最小，之后访问4号页面，因为原先内存中没有4号页面，因此会选择逐出一个页面。此时1号页面在底部，其t最大，因此被逐出。
那么LRU算法是否解决了Belay异常呢？还是按照上一节的实验顺序，测试容量为4和5的内存，左侧到右侧，t逐渐增大：
| 访问顺序 | 访问页 | 内存队列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1，2 | 否 |
| 3 | 3 | 1，2，3 | 否 |
| 4 | 4 | 1，2，3，4 | 否 |
| 5 | 5 | 2，3，4，5 | 否 |
| 6 | 3 | 2，4，5，3 | 是 |
| 7 | 9 | 4，5，3，9 | 否 |
| 8 | 1 | 5，3，9，1 | 否 |
| 9 | 4 | 3，9，1，4 | 否 |
| 10 | 2 | 9，1，4，2 | 否 |
| 11 | 7 | 1，4，2，7 | 否 |
| 12 | 4 | 1，2，7，4 | 是 |
| 13 | 7 | 1，2，4，7 | 是 |
一共有10次未命中。增加容量到5，看一下新的情况：
| 访问顺序 | 访问页 | 内存队列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1，2 | 否 |
| 3 | 3 | 1，2，3 | 否 |
| 4 | 4 | 1，2，3，4 | 否 |
| 5 | 5 | 1，2，3，4，5 | 否 |
| 6 | 3 | 1，2，4，5，3 | 是 |
| 7 | 9 | 2，4，5，3，9 | 否 |
| 8 | 1 | 4，5，3，9，1 | 否 |
| 9 | 4 | 5，3，9，1，4 | 是 |
| 10 | 2 | 3，9，1，4，2 | 否 |
| 11 | 7 | 9，1，4，2，7 | 否 |
| 12 | 4 | 9，1，2，7，4 | 是 |
| 13 | 7 | 9，1，2，4，7 | 是 |
未命中的次数已经变成了9次，减少了一次，如果我设计的队列中有大量的重复，那么这个改进应该更加明显。LRU算法在系统的实现中是被改进的，每次新添加进去的页面会被放在队列的3/8处。无论如何，LRU算法都被认为是最接近OPT的算法。
LRU简单实现：采用链式结构，越早加入到链中数据，顺序越靠近尾部，后来加入的数据添加到头部。当开始需要访问数据时，先遍历链表，分两种情况。
（1）存在数据：数据在头部，则直接返回，不需要做操作。数据不在头部，将数据移动到头部（注意在尾部的情况）
（2）不存在数据：达到达到最大容量，删除尾部的一个元素，然后添加新元素到头部。未达到最大容量，直接添加到新元素到头部。
LRU简单实现
时钟置换算法 CLOCK(NRU)算法
时钟置换算法可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。我们给每一个页面设置一个标记位u，u=1表示最近有使用u=0则表示该页面最近没有被使用，应该被逐出。
按照1-2-3-4的顺序访问页面，则缓冲池会以这样的一种顺序被填满：
1-2-3-4
注意中间的指针，就像是时钟的指针一样在移动，这样的访问结束后，缓冲池里现在已经被填满了，此时如果要按照1-5的顺序访问，那么在访问1的时候是可以直接命中缓存返回的，但是访问5的时候，因为缓冲池已经满了，所以要进行一次逐出操作，其操作示意图如下：
1-5
最初要经过一轮遍历，每次遍历到一个节点发现u=1的，将该标记位置为0，然后遍历下一个页面，一轮遍历完后，发现没有可以被逐出的页面，则进行下一轮遍历，这次遍历之后发现原先1号页面的标记位u=0，则将该页面逐出，置换为页面5，并将指针指向下一个页面。
假设我们接下来会访问2号页面，那么可以直接命中指针指向的页面，并将这个页面的标记为u置为1。<br />
但是考虑一个问题，数据库里逐出的页面是要写回磁盘的，这是一个很昂贵的操作，因此我们应该优先考虑逐出那些没有被修改的页面，这样可以降低IO。
因此在时钟置换算法的基础上可以做一个改进，就是增加一个标记为m，修改过标记为1，没有修改过则标记为0。那么u和m组成了一个元组，有四种可能，其被逐出的优先顺序也不一样：
- (u=0, m=0) 没有使用也没有修改，被逐出的优先级最高；
- (u=1, m=0) 使用过，但是没有修改过，优先级第二；
- (u=0, m=1) 没有使用过，但是修改过，优先级第三；
- (u=1, m=1) 使用过也修改过，优先级第四。
7、什么是虚拟内存
虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。目前，大多数操作系统都使用了虚拟内存。
8、中断的概念
处理器接收到来自硬件或软件的信号，提示发生了某个事件，应该被注意，这种情况就称为中断。
9、什么是死锁？死锁产生的必要条件，如果避免？
死锁是指多个进程因循环等待资源而造成无法执行的现象。死锁会造成进程无法执行，同时会造成系统资源的极大浪费(资源无法释放)。
主要原因：系统资源不足、进程运行推进顺序不合适、资源分配不当
四个必要条件(都成立，才会发生死锁)：
- 互斥条件：一个资源每次只能被一个进程使用
- 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放
- 不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺
- 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系
死锁避免：（银行家算法）判断此次请求是否造成死锁若会造成死锁，则拒绝该请求
10、进程与线程的区别
进程是系统进行资源调度和分配的一个独立单位
线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位
进程拥有独立的地址空间，而线程间共享地址空间
11、线程同步的方式
互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问
信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
事件（信号）：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。
