

# 操作系统

## 知识体系

## Questions

### 1.进程和线程的区别

- **进程**是系统进行资源分配和调度的基本单位；
- **线程**是CPU调度和分派的基本单位。
  - 每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器，线程之间切换的开销小；
  - 一个进程至少有一个线程，线程依赖于进程而存在；
  - 每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行；
  - 多线程程序只要有一个线程崩溃，整个程序就崩溃了，但多进程程序中一个进程崩溃并不会对其它进程造成影响，因为进程有自己的独立地址空间，因此多进程更加健壮。

### 2.协程

- **协程**：协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

### 3.进程的状态

#### 三态模型

* **运行**：当一个进程在处理机上运行时，则称该进程处于运行状态。处于此状态的进程的数目小于等于处理器的数目，对于单处理机系统，处于运行状态的进程只有一个。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的空闲进程。
* **就绪**：当一个进程获得了除处理机以外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。就绪进程可以按多个优先级来划分队列。例如，当一个进程由于时间片用完而进入就绪状态时，排入低优先级队列；当进程由I／O操作完成而进入就绪状态时，排入高优先级队列。
* **阻塞**：一个进程正在等待某一事件发生（例如请求I/O而等待I/O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。

![三态模型](https://i.loli.net/2021/03/25/fjOoY642rznWUGE.png)

#### 五态模型

* **新建**：对应于进程被创建时的状态，尚未进入就绪队列。
* **终止**：进程完成任务到达正常结束点，或出现无法克服的错误而异常终止，或被操作系统及有终止权的进程所终止时所处的状态。

![](https://i.loli.net/2021/03/25/B7Ee5j2XCrObMhw.png)

### 4.进程间通信方式

* **匿名管道**：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
* **高级管道**：将另一个程序当做一个新的进程在当前程序进程中启动，则它算是当前程序的子进程。
* **有名管道**：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

* **消息队列**：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

* **信号量**：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

* **信号**： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

* **共享内存**：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。

* **套接字**：套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

### 5.僵尸进程和孤儿进程

* **僵尸进程**：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。
* **孤儿进程**：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。

### 6.死锁

* **死锁**：死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。

#### 死锁产生的必要条件

* **互斥条件**：一个资源每次只能被一个进程使用；
* **请求与保持条件**：一个进程因请求资源而阻塞时，对已获得的资源保持不放；
* **不剥夺条件**：进程已获得的资源，在未使用完之前，不能强行剥夺；
* **循环等待条件**：若干进程之间形成一种头尾相接的循环等待资源关系。

#### 死锁预防

* 破坏互斥条件：允许某些资源同时被多个进程访问，但是有些资源本身并不具有这种属性；
* 破坏请求与保持条件：
  * 实行资源预先分配策略（当一个进程开始运行之前，必须一次性向系统申请它所需要的全部资源，否则不运行）；
  * 只允许进程在没有占用资源的时候才能申请资源（申请资源前先释放占有的资源）；
* 破坏不剥夺条件：允许进程强行抢占被其它进程占有的资源，这样做会降低系统性能；
* 破坏循环等待条件：将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。

#### 死锁避免

> 银行家算法
>
> 参考： [ 银行家算法](https://zh.wikipedia.org/wiki/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95)

### 7.页面置换算法

* **最佳置换算法**（OPT）：选择以后永不使用的或者是在最长时间内不再被访问的页面；
* **先进先出置换算法**（FIFO）：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面；
* **最近最久未使用置换算法**（LRU）：置换出未使用时间最长的页面；
* **第二次机会算法**（SCR）：按FIFO选择某一页面，若其访问位为1，给第二次机会，并将访问位置0；
* **时钟算法**（CLOCK）：SCR中需要将页面在链表中移动（第二次机会的时候要将这个页面从链表头移到链表尾），时钟算法使用环形链表，再使用一个指针指向最老的页面，避免了移动页面的开销。

* 注：[LRU算法题](https://leetcode-cn.com/problems/lru-cache/)

### 8.分页和分段的区别

* 段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的；
* 段的大小不固定，由它所完成的功能决定；页的大小固定，由系统决定；
* 段向用户提供二维地址空间；页向用户提供的是一维地址空间；
* 段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

### 9.硬中断和软中断

​	    **硬中断**是由硬件产生的，比如，像磁盘，网卡，键盘，时钟等。每个设备或设备集都有它自己的IRQ（中断请求）。

​	    处理中断的驱动是需要运行在CPU上的，因此，当中断产生的时候，CPU会中断当前正在运行的任务，来处理中断。在有多核心的系统上，一个中断通常只能中断一颗CPU（也有一种特殊的情况，就是在大型主机上是有硬件通道的，它可以在没有主CPU的支持下，可以同时处理多个中断）。

​		**硬中断**可以直接中断CPU。它会引起内核中相关的代码被触发。对于那些需要花费一些时间去处理的进程，中断代码本身也可以被其他的硬中断中断。

​		**软中断**的处理非常像硬中断。然而，它们仅仅是由当前正在运行的进程所产生的。通常，软中断是一些对I/O的请求。这些请求会调用内核中可以调度I/O发生的程序。对于某些设备，I/O请求需要被立即处理，而磁盘I/O请求通常可以排队并且可以稍后处理。根据I/O模型的不同，进程或许会被挂起直到I/O完成，此时内核调度器就会选择另一个进程去运行。I/O可以在进程之间产生并且调度过程通常和磁盘I/O的方式是相同。

​		**软中断**仅与**内核**相联系。而内核主要负责对需要运行的任何其他的进程进行调度。一些内核允许设备驱动的一些部分存在于用户空间，并且当需要的时候内核也会调度这个进程去运行。

​		**软中断**并不会直接中断CPU。也只有当前正在运行的代码（或进程）才会产生软中断。这种中断是一种需要内核为正在运行的进程去做一些事情（通常为I/O）的请求。有一个特殊的软中断是Yield调用，它的作用是请求内核调度器去查看是否有一些其他的进程可以运行。



### 10.IO模型

* **阻塞式 I/O**：应用进程被阻塞，直到数据从内核缓冲区复制到应用进程缓冲区中才返回；

* **非阻塞式 I/O**：应用进程可以继续执行，但是需要不断地执行系统调用来获知 I/O 是否完成，这种方式称为轮询；

* **I/O 复用**：单个进程具有处理多个 I/O 事件的能力；

  * **select**：将文件描述符放入一个集合中，调用select时，将这个集合从用户空间拷贝到内核空间（缺点1：每次都要复制，**开销大**），由内核根据就绪状态修改该集合的内容。（缺点2）**集合大小有限制**，32位机默认是1024（64位：2048）；采用水平触发机制。select函数返回后，需要通过遍历这个集合，找到就绪的文件描述符（缺点3：**轮询的方式效率较低**），当文件描述符的数量增加时，效率会线性下降；

    默认单个进程打开的FD有限制是1024个，可修改宏定义，但是效率仍然慢。

  * **poll**：基本原理与select一致，也是轮询+遍历；唯一的区别就是**poll**采用链表的方式存储，没有最大文件描述符限制。

  * **epoll**：通过内核和用户空间共享内存，避免了不断复制的问题；支持的同时连接数上限很高（1G左右的内存支持10W左右的连接数）；文件描述符就绪时，采用回调机制，避免了轮询（回调函数将就绪的描述符添加到一个链表中，执行epoll_wait时，返回这个链表）；支持水平触发和边缘触发，采用边缘触发机制时，只有活跃的描述符才会触发回调函数。

* **信号驱动式 I/O**：内核在数据到达时向应用进程发送 SIGIO 信号；

* 异步 I/O：内核完成所有操作后向应用进程发送信号。



## 参考链接

* https://github.com/wolverinn/Waking-Up#2-%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F
* http://www.linuxidc.com/Linux/2014-03/98013.htm
* https://blog.csdn.net/violet_echo_0908/article/details/51201278
* https://www.cnblogs.com/wlwl/p/10293057.html



















