操作系统复习

参考：github.com/wolverinn/W…

1 进程和线程

• 进程是分配资源的基本单位。有独立的地址空间。
• 线程作为CPU独立运行和独立调度的基本单位。共享地址空间。
• 线程之间的通信更方便，同一进程下的线程共享全局变量等数据，而进程之间的通信需要以进程间通信(IPC)的方式进行。
• 线程切换只需保存少量的独占资源（寄存器，栈，错误返回码）
• 多进程程序中一个进程崩溃并不会对其它进程造成影响，因为进程有自己的独立地址空间，因此多进程更加健壮

2 进程间通信

进程间通信IPC (InterProcess Communication)

Pipe无名管道

• 实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据
• 是一个文件，但独立于文件系统（磁盘上看不到）
• 管道所传送的是无格式字节流，这就要求事先约定好数据的格式
• Pipe需要通信的进程具有亲缘关系
• 缓冲区大小受限

FIFO有名管道

• Pipe不在磁盘上建立管道文件，FIFO在磁盘上建立管道文件
• Pipe 和 FIFO 的管道数据都存在内核内存的缓冲区中
• 在不相关的进程之间也能交换数据

信号Signal

• 信号是软件层次上对中断机制的一种模拟，是一种异步通信方式。主要有硬件来源和软件来源。
• SIGHUP：用户从终端注销，所有已启动进程都将收到该信号。默认终止进程。
• SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。
• SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。

消息(Message)队列

• 与管道(Pipe/FIFO)不同的是，消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除时才会被真正的删除。
• 消息队列在某个进程写入消息之前，并不需要另外某个进程等待消息的到达。
• 消息队列是消息的链表，允许一个或多个进程向它写入与读取消息，可以实现消息的随机查询
• 克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

共享内存

• 内核专门留出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间，无需拷贝数据同时读写。
• 是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。
• 需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。

信号量(semaphore)

• 信号量是一个计数器，用于多进程对共享数据的访问。
• 信号量是非负整型变量，除了初始化之外，它只能通过PV原语操作
• P来源于荷兰语proberen"测试"：尝试获取
• V来源于荷兰语verhogen"增加"：释放资源

Socket套接字

• 套接字是一种通信机制，允许进行通信的进程跨网络进行。
• 套接字的特性由3个属性确定，它们分别是：域、端口号、协议类型。
• 域：AF_INET，它指的是Internet网络；AF_UNIX，表示UNIX文件系统。
• 协议类型：流套接字（TCP字节流）；数据报套接字（UDP）；原始套接字(允许对较低层次的协议直接访问，比如IP、 ICMP协议)

3 进程调度

批处理系统

• 先来先服务 first-come first-serverd（FCFS）
• 最短作业优先 shortest job first（SJF）
• 最高响应比优先 Highest Response Ratio Next（HRRN）
  • 响应比 = 1+ 等待时间/处理时间。
  • 同时考虑了等待时间的长短和估计需要的执行时间长短
  • 很好的平衡了长短进程。非抢占（开始运行就不被打断），吞吐量高，开销可能较大，提供好的响应时间，无饥饿问题。

交互式系统

• 时间片轮转 Round Robin
• 优先级调度算法
  • 按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级
• 多级反馈队列调度算法 Multilevel Feedback Queue
  • 设置多个就绪队列1、2、3...，优先级递减，时间片递增。
  • 只有等到优先级更高的队列为空时才会调度当前队列中的进程。
  • 如果进程用完了当前队列的时间片还未执行完，则会被移到下一队列。
  • 抢占式（时间片用完时），开销可能较大，对IO型进程有利，可能会出现饥饿问题。

4 协程

• 协程就是用户级线程。对于操作系统是并不可见的.
• 协程与（核心级）线程主要区别是它将不再被内核调度，而是交给了程序自己。切换更加高效。
• 整个流程无锁，由一个线程执行，所以称为“协程”，而非线程的抢占式多任务。
• python可以通过 yield/send 的方式实现协程。在python 3.5以后，async/await 成为了更好的替代方案
• Golang中大量使用协程, “Go出去的”都是协程。

Yield和Resume

一般的协程实现都会提供两个重要的操作Yield和Resume。其中：

• Yield：是让出cpu的意思，它会中断当前的执行，回到上一次Resume的地方
• Resume：继续协程的运行。执行Resume后，回到上一次协程Yield的地方。

内核级线程与用户级线程

• 用户态线程是协程的一种实现
• 所谓「用户态线程」就是把内核态的线程在用户态实现了一遍而已
• 操作系统层面的线程就是所谓的「内核态线程」； 「用户态线程」则多种多样，只要能满足在同一个内核线程上执行多个任务的都算，例如 coroutine、golang 的 goroutine、C# 的 Task。
• 到底什么是用户态线程，内核态线程？ - Martin Chloride的回答 - 知乎

5 并发、并行、异步的区别？

• 并行（和串行相比）：在多CPU系统中，多个程序无论宏观还是微观上都是同时执行的。
• 并发：在一个时间段中同时有多个程序在运行，但其实任一时刻，只有一个程序在CPU上运行，宏观上的并发是通过不断的切换实现的；
• 多线程：并发运行的一段代码。是实现异步的手段
• 异步（和同步相比）：即不是顺序执行。在等待某个资源的时候继续做自己的事。

7 死锁

发生的必要条件

• 互斥条件。独占性的资源。
• 保持和等待条件。进程因请求资源而阻塞时，对已经获得的资源保持不放。
• 不剥夺条件。已分配给进程的资源不能被剥夺，只能由进程自己释放。
• 循环等待条件。存在一个进程循环链，链中每个进程都在等待链中的下一个进程所占用的资源。

8 死锁的避免：银行家算法

银行家算法总结 - 日常被禁言的文章 - 知乎

• 最大需求矩阵Max：一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
• 分配矩阵Allocation：一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
• 需求矩阵Need：一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。（Need=Max-Allocation）
• 可利用资源向量Available：一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。
• 工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，安全算法开始时，Work:=Available

安全性算法

• 建立向量Finish：表示系统是否有足够的资源分配给进程使之运行完成。开始时先令Finish[i]=false，
• 找到一个Finish[i]:=false的进程，假设用当前的Work向量瞬间满足它的所有需求（如果可以），设置Finish[i]:=true并收回它的资源。得到一个新的Work向量。
• 如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态

运行过程

• 如果一个进程请求资源数 Requesti ≤ Need 或 Requesti ≤ Available，直接拒绝。
• 否则就试探着分配，然后执行安全性算法，安全就分配。

9 内存管理

• 分区分配: 固定式分区,可变式分区
  • 首次适应法(first fit)，查找开销大，但高地址大概率有大空闲
  • 最佳适应法(best fit)，有碎片问题，但大空闲可用
  • 最坏适应法(worst fit)，无碎片问题，但又大空闲不可用问题
• 页式存储器管理
• 段式存储器管理
• 段页式存储器管理

分段和分页的区别

• 目的不同：分页的目的是管理内存，用于虚拟内存以获得更大的地址空间；分段的目的是满足用户的需要，使程序和数据可以被划分为逻辑上独立的地址空间；
• 分段便于信息的保护和共享；分页的共享收到限制；
• 大小不同：段的大小不固定（连续），由其所完成的功能决定；页的大小固定，由系统决定；
• 地址空间维度不同：分段是二维地址空间（段号+段内偏移），分页是一维地址空间（每个进程一个页表/多级页表，通过一个逻辑地址就能找到对应的物理地址）；
• 碎片：分段没有内碎片，但会产生外碎片；分页没有外碎片，但会产生内碎片（一个页填不满）

虚拟内存

CPU使用虚拟地址向内存寻址，通过专用的内存管理单元（MMU）硬件把虚拟地址转换为真实的物理地址，操作系统负责把虚拟地址和物理地址的映射关系维护在页表之中。

出现要访问的页面不在内存中，那么就通过页面调入功能将其调入，同时还可以将暂时不用的页面换出到辅存，以腾出空间。因为页是根据请求调入的，故称为请求页式存储管理。

当CPU寻址的时候，这个映射会有三种可能。

• 未分配：虚拟地址所在的那一页并未被分配。
• 未缓存：虚拟地址所在的那一页被分配了，但并不在内存中。
• 已缓存：虚拟地址所在的那一页就在内存中。

程序的运行

创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

• 编译：由编译程序将用户源代码编译成若干个目标模块。
• 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。
• 装入：由装入程序将装入模块装入内存运行。

链接

• 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。
• 装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，釆用边装入边链接的链接方式。
• 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。

装入

• 绝对装入

  • 按照装入模块中的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际内存物理地址完全相同，故不需对程序和数据的地址进行修改。

• 静态重定位

  • 物理地址=首地址+逻辑地址（偏移）。
  • 静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间
  • 且在整个运行期间不能在内存中移动或再申请内存空间。

• 动态重定位

  • 并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。
  • 这种方式需要重定位寄存器（段寄存器）的支持。 当程序运行的时候，CPU每取一条访存指令，硬件地址变换机构会自动将指令中的相对地址与重定位寄存器的地址相加，所得的值为绝对地址，然后根据绝对地址访问。
  • 特点是可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，可以根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

10 页面置换算法

• 最佳页面置换算法OPT（Optimal replacement algorithm）：置换以后不需要或者最远的将来才需要的页面，是一种理论上的算法，是最优策略；
• 先进先出FIFO：置换在内存中驻留时间最长的页面。缺点：有可能将那些经常被访问的页面也被换出，从而使缺页率升高；造成抖动现象。
• 最近最少使用算法LRU（Least Recently Used）：置换出未使用时间最长的一页；实现方式：维护时间戳，或者维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。没有抖动现象。

局部性原理

时间上：最近被访问的页在不久的将来还会被访问。源自程序中的循环。 空间上：内存中被访问的页周围的页也很可能被访问。程序的顺序执行。

抖动（颠簸）现象

被置换的页，立刻被再次需要，不断产生缺页中断，导致整个系统的效率急剧下降。内存颠簸的解决策略包括：

• 修改页面置换算法；如不要使用FIFO
• 降低同时运行的程序的数量 & 或增加物理内存容量：开源节流降低并发

11 磁盘调度

• 先来先服务
• 最短寻道时间优先
• 电梯算法：电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

12 IO多路复用

IO 多路复用是什么意思？ - levin的回答 - 知乎

1. select/poll 老李去火车站买票，委托黄牛，然后每隔6小时电话黄牛询问，黄牛三天内买到票，然后老李去火车站交钱领票。
2. epoll 老李去火车站买票，委托黄牛，黄牛买到后即通知老李去领，然后老李去火车站交钱领票。

• 多路是啥意思？:黄牛说，我还可以代买飞机票，客车票，啥都能买，你要定还是这个电话奥亲
• 复用体现在哪？:多个人复用一个黄牛（一个黄牛为多个人服务）

常见的IO模型

• 同步阻塞IO（Blocking IO，BIO）
  • In order to handle two clients with this approach, we need to have several threads, i.e. to allocate a new thread for each client connection.
  • 一个socket监视一个进程：Apache
  • 一个socket监视一个线程：比进程切换效率高，但是一个线程crash整个进程crash。
• 同步非阻塞IO（Non-blocking IO, NIO）
  • 非阻塞+忙轮询。
  • 默认创建的socket都是阻塞的，非阻塞IO要求socket被设置为NONBLOCK。
  • We would have to ask each socket with the same question and essentially spin in an infinite loop.
• IO多路复用（IO Multiplexing）
  • To get rid of this inefficient loop, we need polling readiness mechanism.
  • When any of the sockets is ready, we will perform operations in the queue and then be able to return to the blocking state, waiting for the sockets to be ready for the next I/O operation.
  • IO多路复用把忙轮询变成了select/poll这种查找可用性的算法。外层代码阻塞等待select/poll发现下一个可用的结果，内层socket肯定必须使用非阻塞的socket。
  • IO Multiplexing的分类具有争议。它的确一直在blocking所以肯定是阻塞。但有人说算异步有人说不算异步。
  • 个人感觉不算异步。下面图里的Signal Driven和AIO是异步（有process continues executing）
• 异步IO（Asynchronous IO, AIO）

参考

• IO复用,AIO,BIO,NIO,同步，异步，阻塞和非阻塞 区别(百度)
• 一个关于异步的文章系列，还探讨了协程的问题
• 多大关于Select的PPT

epoll

一棵红黑树，一条准备就绪句柄链表，少量的内核cache，就帮我们解决了大并发下的socket处理问题。select poll epoll的区别(转） - 海茶依依岛的文章 - 知乎

• 执行epoll_create时，创建了红黑树和就绪链表
• 执行epoll_ctl时，如果增加socket句柄，则检查在红黑树中是否存在，存在立即返回，不存在则添加到树干上
• 然后向内核注册回调函数，用于当中断事件来临时向就绪链表中插入数据。
• 执行epoll_wait时立刻返回准备就绪链表里的数据即可。
• 最后看看epoll独有的两种模式LT和ET。无论是LT和ET模式，都适用于以上所说的流程。区别是，LT模式下，只要一个句柄上的事件一次没有处理完，会在以后调用epoll_wait时次次返回这个句柄，而ET模式仅在第一次返回。