硬件框架图

PCI bridge 北桥， ISA bridge 南桥。图片来自《程序员的自我修养--链接、装载与库》。

虚拟化

CPU

CPU是计算单元，针对计算的目标主要有如下：

多线程在CPU上并发执行
线程在CPU上执行的权限可控

针对第一点，通过线程间的切换，达成并发执行；针对第二点，通过不同的运行模式，达到权限可控。

线程切换

为了让多个线程并发执行，给用户很好的交互体验，通过时分共享CPU技术，让每个线程都只运行一个时间片，然后切换到其他线程，达到一种多个线程同时运行的表象。

线程切换的第一个关键问题是让OS在没有执行的情况下，重新获得CPU的控制权，来实现线程之间的切换，有两种可行的思路：

协作的方式（不可取）：通过等待程序进行系统调用（陷阱，非法操作，yield），将CPU的控制权交还给OS
非协作的方式：利用时钟设备发出时钟中断，进入预先设置好的中断处理程序，从而回到OS

时钟中断

时钟中断的处理流程如下

初始化过程
- 操作系统初始化陷阱表
- 硬件记住系统调用处理程序&时钟处理程序
- 操作系统启动中断时钟
- 硬件启动时钟，每隔xms中断CPU
中断过程
- 进程A，runnging
- 硬件发出时钟中断，将寄存器A保存到内核栈A，转向内核模式，跳到陷阱处理程序（因为需要执行陷阱处理程序，所以需要先保存寄存器内容到内核栈）
- 操作系统处理陷阱，调用switch()例程，将寄存器A保存到进程结构（PCB）A中，将进程结构B恢复到寄存器B，从陷阱返回（进入B）
- 硬件从内核栈B恢复寄存器B，转向用户模式，跳到B的程序计数器
- 进程B，running

关于上述寄存器的保存和恢复，有两种处理的方法：

发生时钟中断时，线程的用户寄存器由硬件隐式保存到该进程的内核栈。
当操作系统决定从进程A切换到B时，内核寄存器被操作系统明确地保存，但是存储到了该进程的进程结构的内存中。同时将B的进程结构中保存的数据恢复到内核寄存器，陷阱返回之后就如同刚刚是从B陷入了内核一样。

处理器调度

度量指标

周转时间：任务完成时间-任务到达时间
响应时间：任务首次运行时间-任务到达时间

调度算法

先进先出 First In First Out | Fist Come First Served，先到的任务先执行，但很容易遇到长耗时任务在前，增加平均周转时间，这也被称为护航问题，为了解决长耗时任务在前的问题，引出了SJF。
最短任务优先 Shortest Job First，耗时时间短的任务先执行，但这需要基于所有任务一起到来，同时已知每个任务耗时的假设。SJF可以在周转时间指标上达到最优，同时是不切实际的。
最短完成时间优先 Shortest Time-to-Completion First，为了应对SJF中，所有任务不是同一时间到达的问题，提出了STCF，也被称作是抢占式SJF。每当新的工作进入系统时，会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。STCF相比于FIFO和SJF最大的特点是抢占式，在抢占式的条件下，STCF在周转时间指标上可以达到最优。
时间片轮转 Round-Robin，周期性的遍历每个任务一段时间，响应时间上是最优的，在周转时间上几乎是最差的。
多级反馈队列 Multi-level Feedback Queue，在不知道进程到底需要执行多久的情况下，同时兼顾周转时间和响应时间，该算法思想仍存在于目前主流的操作系统的调度策略中。规则如下：
1. 总是运行优先级高的任务
2. 相同优先级的任务，轮转运行
3. 工作刚进入系统时，放在最高优先级的队列中
4. 工作用完整个时间片，降低一个优先级，工作在其时间片内，主动放弃CPU，优先级不变
5. 经过一段时间S，将系统中所有的工作重新加入最高优先级，避免长工作会饥饿
6. 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），都降低优先级，防止恶意程序在轮转中恶意调用IO，保持优先级。 MLFQ的问题，涉及到了太多需要依据经验来设置的变量，需要长时间的调优。

进程切换与线程切换

进程切换，我更愿意理解是进程间的线程切换；线程切换是指进程内的线程切换。

只要是线程切换就涉及到寄存器的现场保护，但是进程是资源管理的基本单位，还涉及到

逻辑地址和物理地址的映射；
包含当前进程信息的进程表
包含进程已打开文件的信息的文件表

这些在进程切换的时候都需要进行切换，所以开销更大。

权限管理

同时为了限制线程的权力，将线程的执行区分成用户模式和内核模式。不同的模式下的区别主要体现在资源范围不同。

在用户模式下，进程的不能执行特权操作，例如发出I/O请求或者执行受限操作
在内核模式下，运行的代码（即操作系统或内核）可以执行他们想做的任何事情

不同模式在硬件上是体现在某个控制寄存器中的值，在内核模式时，可以执行所有的指令，访问系统中的任意位置；在用户模式时，不允许执行特权指令（例如停止处理器、改变模式位或者发起I/O操作等），也不允许引用内核区域的代码和数据。

运行应用程序代码进程初始时是在用户模式中，进程从用户模式变为内核模式的方式是通过中陷阱（系统调用）或者异常引发的中断等。当在内核模式执行完特定的程序之后，返回用户模式。

陷阱&系统调用

用户程序工作在用户模式下，如果需要系统调用，则通过内核暴露的陷阱指令，跳入内核，并将权限升级到内核模式，从而调用一些特权操作，完成后，操作系统调用一个特殊的从陷阱返回指令（return-from-trap），回到发起调用的用户程序中，同时权限降低到用户模式。

对系统调用的调用，看起来就像是一个过程调用一样，在过程调用中隐藏着著名的陷阱指令，它会将参数放入和内核约定好的位置中（如栈或者寄存器中），将系统调用号也放入其中，执行陷阱指令，之后处理陷阱指令的返回值，并将控制权返回给发出系统调用的程序。那么陷阱如何知道在OS内运行哪些代码呢？（用户程序在执行陷阱指令时不能指定要跳转到的代码地址），由操作系统在启动时设置陷阱表来实现，陷阱表中定义了在发生某些异常事件（如I/O中断、用户程序执行系统调用）时需要运行的代码，从而限制用户程序任意跳转到内核的任意位置。

具体流程如下：

操作系统初始化陷阱表
硬件记住系统调用处理程序的地址
操作系统在进程列表中创建条目，为程序分配内存，将程序加载到内存，根据argv设置程序栈，用寄存器/程序计数器（程序代码的入口位置）填充内核栈，从陷阱返回
硬件从内核栈恢复寄存器，转向用户模式，跳转到用户程序的入口
程序运行main，调用系统调用，陷入操作系统
硬件将寄存器保存到内核栈，转向内核模式，跳到陷阱处理程序
操作系统处理陷阱，做好系统调用工作，从陷阱返回
硬件从内核栈恢复寄存器，转向用户模式，跳转到陷阱之后的程序计数器
程序运行结束，通过exit()陷入
操作系统释放进程的资源，将进程从进程列表中清除

辅助讲解

在《Linux 内核设计与实现》书中关于系统调用的讲解

系统调用的作用

为用户空间提供了一种硬件的抽象接口。用户不需要关心在硬件上具体是怎么实现的

保证了系统的稳定和安全。可以基于权限、用户类型和其他一些规则，对访问进行裁决

进程都是运行在虚拟系统中，系统调用在用户空间和系统的其余部分的提供了一层公共接口（不是很理解）

系统调用的组成

系统调用通过系统调用号、传入参数和返回值三部分组成（注意是没有函数名称的）。

系统调用号是独一无二的，不允许被回收利用的。失效或被删除的系统调用号会执行统一的sys_ni_syscall() 返回一个错误码而不执行任何操作。系统调用号通过寄存器eax传递给内核

传入参数，通过寄存器传入，对于小于等于5个的参数，会依次使用5个寄存器；对于多于5个的参数，会在寄存器中传入参数所在的用户空间地址指针。

返回值也是通过寄存器传递的，x86是放在eax寄存器中的
自己编写一个系统调用程序
在kernel文件夹下的文件（例如kernel/sys.c）中创建一个函数，例如
1
2
3
4
#include <asm/page.h>
asmlinkage long sys_foo(void){
   	return THREAD_SIZE;
}
把函数加入到系统调用表中，例如文件entry.s，形如
1
2
3
4
5
6
ENTRY(sys_call_table)
  .long sys_restart_syscall	/* 0 */
  .long sys_extit
  .long sys_fork
  ...
  .long sys_foo
这些函数会被按照次序分配系统调用号。
接下来把系统调用号加入到<asm/unistd.h>中，形如
1
2
3
4
5
#define __NR_restart_syscall	0
#define __NR_exit							1
#define __NR_fork							2
...
#define __NR_foo							338
在用户代码中进行调用

下面的代码感觉怪怪的，感觉书中有错误

下面介绍直接进行系统调用的方式。通过一组宏直接对系统调用进行访问。

__syscall{n}n取值[0,6)，代表需要的参数，后面跟着\(2+2*n\)个参数，第一个对应系统调用的返回值，第二个是系统调用的名称，再以后是按照系统调用参数排列的每个参数的类型和名称。

例如系统调用
1
long open(const char *filename, int flags, int mode)
不靠库的支持，直接调用此系统调用的宏的形式为
1
2
#define NR_open 5
_syscall3(long, open, const char*, filename, int, flags, int, mode)
调用我们自己编写的系统调用
1
2
3
4
5
6
7
8
9
#define __NR_foo 283
_syscall0(long foo)

int main(void){
  long stack_size;
  stack_size = foo();
  printf("The kernel stack size is %ld", stack_size);
  return 0;
}
系统调用的工作机制

用户空间程序无法直接执行内核代码，不能调用内核空间中的函数，因为内核驻留在受保护的地址空间上。因此应用程序应该以某种方式通知系统，告诉内核需要执行一个系统调用，希望系统切换到内核态，这样内核就可以代表应用程序在内核空间执行系统调用。通知的方式是软中断实现的，通过引发一个异常来促使系统切换到内核态去执行异常处理程序，此时的异常处理程序实际上就是系统调用处理程序。

在x86系统上预定义的软中断号128，触发一个异常导致系统切换到内核态执行第128号异常处理程序，即系统调用处理程序（system_call()），该处理程序会根据在eax中声明的系统调用号执行相关的函数。system_call()异常处理程序会负责切换回用户空间。

系统调用的上下文

内核在执行系统调用的时候处于进程上下文，即引发系统调用的那个进程。在进程上下文中，内核可以休眠（比如在系统调用阻塞（例如缺页）或显示调用schedule()的时候）并且可以被抢占，即系统调用可以使用内核提供的绝大部分的功能。作为对比，中断处理程序不能休眠，使得其能进行的操作受到了极大的限制。

异常

在系统启动时，操作系统分配和初始化一张称为异常表的跳转表，包含每种异常的处理程序入口，当异常发生时，通过异常表跳转到对应的异常处理程序。异常类似于过程调用，但是有一些重要的不同之处：

过程调用时，在跳转到处理程序之前，处理器将返回地址压入栈中；而异常的返回地址要么是当前指令，要么是下一条指令。
处理器也把一些额外的处理器状态压入栈中，然后在处理程序返回时，重新开始执行被中断的程序会需要这些状态。
如果控制从用户程序转移到内核，所有这些项目都被压入到内核栈中，而不是压到用户栈。
异常处理程序运行在内核模式下，这意味着它们对所有的系统资源都有完全访问权限。

一旦硬件触发异常，剩下的工作就是由异常处理程序在软件中完成。在处理程序处理完事件之后，它通过执行一条特殊的“从中断返回”指令，返回到被中断程序的地址，将适当的状态弹回到处理器的控制和数据寄存器中，如果被异常中断的是一个用户程序，就将状态恢复为用户模式，然后将控制返回给被中断的程序。

异常的类别，可参考下表：

类别	原因	异步or同步	返回行为
中断	来自IO设备的同步信号	异步	总是返回到下一条指令
陷阱	有意的异常	同步	总是返回到下一条指令
故障	潜在可恢复的故障	同步	可能返回到当前指令
终止	不可恢复的错误	同步	不会返回

中断

中断是系统在执行过程中因为外界（硬中断）或者CPU（软中断）产生，例如硬中断中的IO设备的中断和软中断中的初0和缺页等。中断还可以分为同步中断和异步中断：

同步中断（异常）——CPU内，控制单元产生

当指令执行时由CPU控制单元产生的中断，只有在一条指令执行后才会发出中断。比如软中断，由内核触发，以内核线程的方式执行，比如除数为0，缺页等。
异步中断（中断）——其他硬件设备发出

由硬件设备依照CPU时钟随机产生的中断，中断能在指令之间发生。比如硬中断，由硬件触发，立即执行中断处理程序，打断 CPU 正在执行的任务

辅助讲解

在《Linux 内核设计与实现》书中关于中断的讲解

中断的目标

内核的核心任务都包括对所有连接到计算机上的硬件设备进行有效的管理，但这些设备和CPU的处理速度通常不在一个数量级。因此中断的目标就是联系这两种不同速度的设备，允许低速设备通过中断，让CPU知晓低速设备的状态，从而避免CPU轮询低速设备。

中断的本质

中断的本质是一种特殊的电信号，由硬件设备发向处理器，不与时钟同步，随时产生。

与之对比的是异常，它的产生必须考虑和处理器时钟同步。（也常常被称为同步中断），在处理器执行到错误的指令（如除0）、或者在执行期间出现特殊情况（如缺页），必须靠内核处理时，就会产生一个异常。

中断处理程序

中断处理程序（中断服务例程）是在响应中断的时候，内核会执行的函数。（中断处理程序和中断对应，不和设备关联，一个设备可以产生多种中断，以执行不同的中断处理程序）。在Linux中，中断处理程序就是普通的C函数，只不过需要按照特定的类型声明，以便内核能够以标准的方式传递处理程序的信息。中断处理程序运行在中断上下文（亦称原子上下文）中，这就要求中断处理程序尽可能快的执行完。中断程序可以分为两个部分：

上半部，会被立即在关中断的情况执行，该过程要求尽可能的快。

下半部，在合适的时机，会被执行，此时会在开中断的情况下执行。

例如网卡的中断，在上半部会将网卡设备中的数据传输到内存中，在下半部进行处理和解析。

内存

概念

内存虚拟化为了实现进程眼中的内存空间到物理内存空间的映射；每个进程看到的是一个连续的、完整的内存空间，但数据具体存放的位置是由OS来决定的。

每个进程的内存空间可以分为如下几个区，从低到高分别是

程序代码和数据。对于所有的进程来说，代码是从同一固定地址开始，紧接着的是和C全局变量相对应的数据位置。
堆。代码和数据区后紧随着的是运行时栈。代码和数据区在进程一开始运行时就被指定了大小，与其不同的是，当调用malloc和free这样的C标准库函数的时候，堆可以在运行时动态地扩展和收缩。
共享库。大约在地址空间中的中间部分存放的是像C标准库和数学库这样的共享库的代码和数据的区域。
栈。位于用户虚拟地址空间顶部的是用户栈，编译器利用它来实现函数调用。和堆一样，栈在程序执行期间可以动态地扩展和收缩。特别的，我们每调用一个函数的时候，栈就会增长；从一个函数返回时，栈就会收缩。
内核虚拟内存。地址空间的顶部区域是为内核保留的。不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数，需要调用内核来执行这些操作。

关于此部分的具体内容参考Memory Manager，主要有分段、分页等方法

缓存算法

在一级和二级存储swap的过程中涉及到如下的算法

LFU，Least Frequently Used，最不经常使用算法。
- 含义：使用一个计数器来记录条目被访问的频率。当缓存满了以后，当前缓存中最低访问次数的条目首先被移除。缺点，无法对一个拥有最初高访问率，但是之后没有被访问的条目缓存负责。假设，某一个条目最初被访问了100次，但是此后，不再需要，那么它会一直占用缓存空间。
- 实现方法：
  - 哈希+双向链表+二叉树，每次操作的复杂度O(logn)
  - 双层哈希，一个哈希存频率和对应的节点id的list，另一个哈希存节点id与其对应的缓存在内存中的位置。每次操作的时间复杂度为O(1)
LRU，Least Recently Used，最近最少使用算法。
- 含义：将最近使用的条目放到靠近缓存顶部的位置。当一个新条目被访问时，LRU将其放到缓存的顶部。当缓存充满时，从底部的较早访问到的条目开始移除。
- 实现方法：哈希+双向链表，时间复杂度为O(1)
FIFO，First In First Out，先进先出算法。
- 顾名思义……

进程与线程

进程

创建

OS先从磁盘中将代码和所有静态数据（如初始化变量）加载到内存中进程的地址空间上，为程序的运行时栈分配一些内存（8M），为堆分配一些内存以及执行与I/O设置相关的工作（如默认每个进程都有3个打开的文件描述符，用于标准输入、输出和错误）之后，跳转在程序的入口处（main函数），OS将CPU的控制权转移到新创建的进程中，该程序开始运行。

PCB

struct context{
int eip, ebx, ecx, edx, esi, edi, esp, ebp;
};
enum proc_state{
	NEW, READY, RUNNING, BLOCKED, ......
};
struct proc{
		pid_t pid;							    			// 进程号
		enum proc_state state;					  // 进程状态
		char * memoy;											// 进程内存开始处
		uint size;												// 进程大小
		struct proc *parent;		 					// 指向父进程的指针
		struct proc *children[CHILD_NUM]; // 子进程指针数组
		struct file *open_file[FILE_NUM];	// 文件指针数组
		struct context ctx;								// CPU中各寄存器值
		uint priority;										// 进程抢占CPU时的优先级
		.......
}

是可以通过系统调用，修改进程调度的优先级，可以和多级调度队列联系起来

状态

在一个进程的活动期间至少具备三种基本状态，即运行状态、就绪状态、阻塞状态。

另外，与阻塞状态等待某个事件的返回不同，挂起状态下的进程被换出到硬盘，不占用内存空间。挂起状态分为两种：

阻塞挂起状态：进程被换出在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程被换出在外存（硬盘），但只要进入内存，就能立刻运行；

通信

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间通信必须要通过内核。

主要的方式有：

管道：匿名管道通信、高级管道通信、有名管道通信
- 匿名管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。父进程可以往管道里写，子进程可以从管道里读。管道由环形队列实现。
- ~~高级管道( popen )：将另一个程序当做一个新的进程在当前程序进程中启动，则它算是当前程序的子进程，这种方式我们成为高级管道方式。~~
- 有名管道 (named pipe) ：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
消息队列

消息队列是由有类型的消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
共享内存+信号量
- 信号量( semophore ) ：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
- 共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
信号：

上面说的进程间通信，都是常规状态下的工作模式，处于异常情况下的进程，就需要用信号的方式来通知。实际上，信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程。信号事件的来源主要有两种：
- 硬件来源
  
  Ctrl+C 产生 SIGINT 信号，表示终止该进程；Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束；
- 软件来源
  
  kill -9 1050 ，表示给 PID 为 1050 的进程发送 SIGKILL 信号，用来立即结束该进程；
Socket

前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要Socket通信。Socket三元组：IP、port、protocol.

根据创建 Socket 的类型不同，分为三种常见的通信方式：
- TCP字节流通信
- UDP数据报通信
- 本地进程间通信

线程

概念

线程是进程中的一条执行流程。在 Linux 内核中，进程和线程都是用 tark_struct 结构体表示的，区别在于线程的 tark_struct 结构体里部分资源是共享了进程已创建的资源，比如内存地址空间、代码段、文件描述符等，所以 Linux 中的线程也被称为轻量级进程，因为线程的 tark_struct 相比进程的 tark_struct 承载的资源比较少，因此以「轻」得名。

一个进程中可以并发执行多个线程，每个线程都有独立一套的寄存器和栈用来保证线程的控制流相互独立，除此之外，各个线程之间共享代码段、数据段、打开文件等资源。多线程的一个特性是，当进程中的一个线程奔溃时，会导致其所属进程的所有线程奔溃（内核线程与用户线程是一对多的情况）。

通信

锁机制：互斥锁、条件变量、读写锁、自旋锁
信号量机制：包括无名线程信号量和命名线程信号量
信号机制：类似进程间的信号机制

线程池

线程池是一个线程阻塞队列，通过预创建的技术，在应用程序启动之后，立即创建一定数量的线程放入阻塞队列中，当任务到来后，线程池唤醒一个线程执行新任务，在任务执行完毕后线程也不退出，而是继续保持在池中等待下一次的任务。

实现方式：线程池主要由2部分组成：任务队列、线程池。粗略做法可以按生产者消费者问题去构建。

代码实现

适用场景

单位时间内需要频繁处理时间短的任务，避免频繁创建、销毁线程带来的系统开销。
需要对请求快速响应的应用，如果接受到任务后再创建线程，满足不了实时要求的话，需要线程池进行预创建。

区别

相同处

二者都具有就绪、阻塞、执行三种基本状态，以及相同的状态转换关系；
二者都可以实现高并发

不同处

进程是 OS 调度的单位，线程是 CPU 调度的单位；
每个进程拥有一个完整的资源平台（内存空间、打开文件列表），而线程只独享必不可少的资源，如寄存器和栈，所以，相较于进程，多线程的创建快，属于同一个进程的不同线程的上下文切换快
线程间不需要经过内核的数据通信效率更高。

协程

协程，也叫做用户空间线程，由程序员自己写程序管理的一种比线程更轻量级的存在。

与线程相比，协程最大的优势就是极高的执行效率，协程占用资源少，由用户管理协程切换，不需要陷入内核态，且切换只需要修改程序计数器、栈等少数的状态值。以及不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态，所以执行效率比多线程高很多。

如，Python对协程的支持是通过generator实现的。传统的生产者-消费者模型是一个线程写消息，一个线程取消息，通过锁机制控制队列和等待，但一不小心就可能死锁。如果改用协程，生产者生产消息后，直接通过yield跳转到消费者开始执行，待消费者执行完毕后，切换回生产者继续生产，效率极高。

个人理解

进程、线程、协称的切换代价，可以从直接和间接两方面来理解。

直接代价体现在切换过程中，需要从用户态切换到内核态，暂存寄存器等等

间接代价体现在切换之后，他们使用的数据范围出现了不同程度的变化，从而造成了各层级缓存的频繁失效

协称不需要模态（用户态/内核态）的切换，所使用的数据变化范围还是比较小，因此轻量高效

线程相比于协程增加了模态的切换，寄存器需要保存的也更多，同时所使用的数据变化范围也稍大

进程的切换在直接代价我理解和线程一样，但是会带来更大范围的缓存失效问题，因此代价也会更高

同步和互斥

在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系。

互斥就是保证一个进程/线程在临界区执行时，其他进程/线程被阻塞，达到避免竞争条件出现的目的。比如「操作 A 和操作 B 不能在同一时刻执行」；
而所谓同步，就是指并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。比如「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都完成之后才能执行」；

OS如何实现进程协作呢

锁：加锁、解锁实现互斥
信号量：P、V操作实现互斥和同步
- P代表减少一个资源，V代表增加一个资源

锁

具体见如何理解互斥锁、条件锁、读写锁以及自旋锁？

锁的分类

悲观锁

悲观锁认为并发访问共享资源时，冲突概率可能非常高，所以任何想进入临界区的线程，必须先执行加锁操作；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

自旋锁

通过CPU提供的CAS原子函数实现，当线程获取不到锁时，一直自旋，利用CPU周期，直到锁可用。在此期间，用户不会主动产生线程上下文切换，适用于明确知道临界区的执行时间很短的情况。在开发过程中，只有特别明确这段竞争期很短才用自旋锁，否则非常浪费 CPU 资源。

spin lock 的锁持有区可以响应中断，除非这个中断处理程序试着去锁这个 spin lock。由于 spin lock 是非递归的，同一个线程在拿到了 spin lock 之后还去获取 spin lock 会导致死锁。

spin_lock_irqsave() 会关所有在本地 CPU 上的中断，如果有某个中断处理程序要获取一个锁，最好声明成 spin_lock_irqsave() 。没必要去关心其他 CPU 上的中断，对这个锁不会有影响。
互斥锁

当没获取到锁时OS就把当前线程放入到锁的等待队列，然后执行调度程序，把CPU让给其他线程执行，当获取到锁时，移出等待队列的队头元素，将该线程的PCB插入到就绪队列，设置该进程为就绪状态，等待被调度。

线程获取不到锁时就及时让出CPU给其他线程，避免无意义的等待，但如果这个过程中发生的两次线程上下文切换占用一定的系统开销。
两阶段锁

先自旋固定的次数，若没有获得锁，则睡眠等待。
读写锁

读锁之间不阻塞，其他情况都阻塞，适用于能明确区分读写操作且读多写少的场景。为避免写优先锁中读线程被饿死/读优先锁中写线程被饿死的情况，引入公平读写锁。让获取锁的线程进入线程队列，不管是写线程还是读线程都按照先进先出的原则加锁，这样读线程仍然可以并发，且不会出现「饥饿」的现象。

乐观锁

乐观锁认为并发访问共享资源的冲突概率很低，它的工作方式是，修改数据之前记录版本号X，修改数据，版本号原子自增1，修改完成之后，查看版本号Y是否等于\(X+1\)，若相等，说明修改过程中，没有其他线程过来修改，否则意味着存在同时修改的情况，则需要重新修改。

数据库中的MVCC，在线文档多人编辑，Git版本管理都是秉承着乐观锁的思想。

产生死锁的条件

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

处理死锁的方法

预防死锁。通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个来预防产生死锁。
1. 破坏互斥条件：例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
2. 破坏请求和保持条件：一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
3. 破坏不抢占条件：
4. 破坏循环等待条件：给资源统一编号，进程只能按编号顺序来请求资源。
避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。
检测死锁。通过检测工具及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。
解除死锁。当检测到系统中已发生死锁时，就采取相应的措施把进程从死锁中解脱出来。常用的方法是撤消一些进程，回收它们的资源，将资源分配给已处于阻塞状态的进程，使其能继续运行。

信号量

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量，通过两个原子操作的系统调用函数来控制信号量，分别是：

P操作

将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
V操作

将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

P操作是用在进入临界区之前，V操作是用在离开临界区之后，这两个操作是必须成对出现的。

信号量如何实现临界区的互斥访问？

为每类共享资源设置一个初值为 1的信号量 s，表示该临界资源未被占用。只要把进入临界区的操作置于 P(s) 和 V(s) 之间，即可实现进程/线程互斥，这种用法也叫做二值信号量。

信号量如何实现事件同步？

设置一个初值为 0的信号量作为条件变量，通常一个线程等待条件成立，另外一个线程修改条件并发信号给等待线程，从而唤醒等待线程

额外提一嘴，C++中只提供了互斥和条件变量，但是没有信号量的开箱即用，可以使用锁加条件变量来实现一个信号量，具体内容可参考，代码如下

#include <mutex>
#include <condition_variable>

class semaphore {
private:
    int count;
    mutex mtk; // 控制count的互斥访问
    condition_variable cv; // 实现主动阻塞和被动唤醒
public:
    semaphore(int val = 1) : count(val) {}

    void wait() { // 可以理解是申请资源
        unique_lock<mutex> lck(mtk); // 上锁
        if (--count < 0) cv.wait(lck); // 在wait的时候就释放掉了锁
    }

    void signal() { // 可以理解是释放资源
        unique_lock<mutex> lck(mtk); // 上锁
        if (++count <= 0) cv.notify_one(); // 此处并没有释放锁
    } //函数退出在执行对象lck的析构的时候，释放掉了锁
};

关于信号量的使用有3个经典问题

生产者/消费者问题

是进程通信、并发队列的一种建模

#define N 100
semaphore mutex = 1;					// 用于互斥访问缓冲区
semaphore emptyBuffers = N;	   // 用于消费者询问缓冲区是否有数据
semaphore fullBuffers = 0;			 // 用于生产者询问缓冲区是否有空位

void producer(){
	while(true){
    	P(emptyBuffers);
        P(mutex);
        //将生成的数据放入缓冲区
        V(mutex);
        V(emptyBuffers);
    }
}

void consumer(){
	while(true){
    	P(fullBuffers);
        P(mutex);
        // 从缓冲区里读取数据
        V(mutex);
        V(emptyBuffers);
    }
}

哲学家就餐问题

是对于互斥访问有限的竞争问题（如 I/O 设备）的建模

#define N 5
semaphore forks[N];				 // 控制对每个叉子的互斥使用，初值为1

void smart_person(int i){
	while(true){
    	think();
        if(i % 2 == 0){
        	P(forks[i]);						// 偶数编号的哲学家先拿左边再拿右边
            P(forks[(i + 1) % N]);
        }else{
        	P(forks[(i + 1) % N]);		// 奇数编号的哲学家先拿右边再拿左边
            P(forks[i]);
        }
        eat();
        V(forks[i]);							  // 统一先放下左边再放下右边 
        V(forks[(i  + 1) % N]);
    }
}

读者—写者锁

下面的介绍仅是通过信号量实现的机制，在Linux内核中，还有基于自旋锁、信号量和RCU实现的版本。见下面的6.8内核并发机制

是对于数据库访问等读多写少问题的建模，这是一个公平读写的模型。此外还有优先读和优先写，依旧参考。

// 公平读写
semaphore rCountMutex;	// 控制对rCount的互斥修改，初值为1
semaphore wDateMutex;	// 控制写者互斥写操作，初值为1
semaphore flag;						// 用于实现读写之间的公平竞争，初值为1
int rCount = 0;							// 正在进行读操作的读者个数

void reader(){
	while(true){
    	P(flag);								// 拿到读权限
        P(rCountMutex);				// 拿到修改rCount的锁
          if(rCount == 0){				// 当第一个读者读的时候，如果有写者则阻塞 
        	  P(wDataMutex);
          }
          rCount ++;
        V(rCountMutex);				 // 对rCount + 1后，可以释放rCount锁给其他读者了
      V(flag);
        
    read();
    
     P(rCountMutex);
        rCount --;
        if(rCount == 0){				 // 当没有读者了，唤醒阻塞中的写者
        	V(wDataMutex);
        }
     V(rCountMutex);
    }
}

void writer(){
	while(true){
    	P(flag);								// 拿到写权限
        P(wDataMutex);				// 拿到作用于写者间的锁
          write();
        V(wDataMutex);
      P(flag);
    }
}

引入flag互斥量的作用是阻止读者只要到达就能进入读者队列造成写饿死的情况，比如：开始来了一些读者读数据，它们全部进入读者队列，此时来了一个写者，执行 P(flag) 操作，使得后续到来的读者都阻塞在 flag 上，不能进入读者队列，这会使得读者队列逐渐为空，即 rCount 减为 0。这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列中的读者全部读取结束后，最后一个读者进程执行 V(wDataMutex)，唤醒刚才的写者，写者则继续开始进行写操作。

文件系统

文件管理

文件组成

Linux文件系统为每个文件分配两个数据结构：

索引节点（inode）

记录文件的元信息，比如 inode 编号、数据在磁盘的位置、文件大小等，索引节点是存储在硬盘上的数据，为了加速文件访问，通常在文件被访问时加载到内存

本人理解的数据块的管理方式使用B+树进行管理的；一个索引节点的数据块可能包含多个
目录项（dentry）

记录文件的名字、索引节点指针、与其他目录项的层级关联关系。其由内核维护，缓存在内存中。

另外，磁盘进行格式化的时候，会被分成三个存储区域，如下：

超级块，用来存储文件系统的详细信息，比如块个数、块大小、空闲块等，当OS刚开始运行时，文件系统会把它挂载进内存。
索引节点区，用来存储索引节点，为了加速文件访问，在文件被访问时会加载到内存。
数据块区，用来存储文件数据或目录数据。其中内核会把已经读过的目录数据用目录项这个数据结构缓存在内存。

文件储存

管理被占用的数据块
- 连续空间存放方式
  
  数组方式，访问磁盘1次，读写速度快，但是会产生外部碎片以及难以动态扩充。
- 非连续空间存放方式
  - 链表方式，访问磁盘n次，无外部碎片以及动态增长方便，但是只能顺序查找，效率低下，且存放指针信息需要消费内存或磁盘空间
  - 索引方式，访问磁盘n + 1次，无外部碎片，支持随机快速访问，但是需要维护索引表的存储开销。
Unix采用多级索引+链表的方式存放文件，小文件直接查找，大文件多级索引查找。
管理空闲数据块
- 空闲表法
  
  仅适用于建立连续文件
- 空闲链表法
  
  无法随机访问，工作效率低
- 位图法
  
  位图是利用二进制来表示磁盘中盘块的使用情况，Linux用位图的方式不仅管理数据空闲块，还有inode空闲块。

文件I/O

I/O的分类

根据「是否利用操作系统的缓存」，可以把文件 I/O 分为直接 I/O 与非直接 I/O

直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
非直接 I/O，读操作时，数据从内核缓存区中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存区，再由内核决定什么时候写入数据到磁盘。

根据「是否等待内核拷贝数据到应用程序缓冲区」，可以把文件 I/O 分为同步 I/O 与异步 I/O

同步I/O
- 阻塞I/O
  
  进程发起阻塞 read 请求，一直等待内核准备数据，并把数据从内核缓冲区拷贝到应用程序的缓冲区中这两件事完成之后，read 才会返回。
- 非阻塞I/O
  
  非阻塞的 read 请求在数据未准备好的情况下立即返回，继续往下执行。此时应用程序不断轮询内核，直到数据准备好，然后等待内核将数据拷贝到应用程序缓冲区，read 才会返回。轮询的过程中，应用程序也无法执行其他指令，只是在循环。
- 非阻塞I/O多路复用
  
  非阻塞I/O多路复用的 read 请求在数据未准备好的情况下立即返回，等待内核以事件分发的形式通知，再来请求数据，此时等待内核将数据拷贝到应用程序缓冲区，read 才会返回。（这个图是select I/O多路复用的过程）
异步I/O

当发起异步I/O的 read 请求之后，就立即返回，内核异步完成数据准备和拷贝到应用缓冲区两件事，全程不用等待。

总的来说，I/O 是分为两个过程的：

数据准备的过程（从磁盘读入内存空间）
数据从内核空间拷贝到用户进程缓冲区的过程

阻塞 I/O 会阻塞在「过程 1」和「过程 2」，而非阻塞 I/O 和非阻塞 I/O 多路复用只会阻塞在「过程 2」，所以这三个都可以认为是同步 I/O。异步 I/O 则不同，「过程 1」和「过程 2」都不会阻塞。

实际上，无论是阻塞 I/O、非阻塞 I/O，还是基于非阻塞 I/O 的多路复用都是同步调用。因为它们在 read调用时，内核将数据从内核空间拷贝到应用程序空间，过程都是需要等待的，也就是说这个过程是同步的，如果内核实现的拷贝效率不高，read调用就会在这个同步过程中等待比较长的时间。

I/O多路复用

最基础的 TCP 的 Socket 编程，它是阻塞 I/O 模型，基本上只能一对一通信，那为了服务更多的客户端，我们需要改进网络 I/O 模型。比较传统的方式是使用多进程/线程模型，每来一个客户端连接，就分配一个进程/线程，然后后续的读写都在对应的进程/线程，这种方式处理 100 个客户端没问题，但是当客户端增大到 10000 个时，10000 个进程/线程的调度、上下文切换以及它们占用的内存，都会成为瓶颈。

为了解决上面这个问题，就出现了 I/O 的多路复用，可以只在一个进程里处理多个文件的 I/O，Linux 下有三种提供 I/O 多路复用的 API，分别是：select、poll、epoll。

select & poll

在使用的时候，首先需要把关注的 Socket集合通过 select/poll 系统调用从用户态拷贝到内核态，然后由内核检测事件，当有网络事件产生时，内核需要遍历进程关注 Socket 集合，找到对应的 Socket，并设置其状态为可读/可写，然后把整个Socket集合从内核态拷贝到用户态，用户态还要继续遍历整个Socket集合找到可读/可写的 Socket，然后对其处理。整个过程2次遍历、2次拷贝文件描述符集合。

select 使用固定长度的 BitsMap 表示文件描述符集合，在 Linux 系统中，由内核中的 FD_SETSIZE 限制，默认最大值为 1024。poll 与select 的区别仅在于用动态数组，以链表形式来组织文件描述符集合，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。
epoll

epoll 通过两个方面，很好解决了 select/poll 的问题。
1. epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述符。把需要监控的一个个 socket 通过 epoll_ctl() 函数加入内核中的红黑树里，这样就不需要像 select/poll 每次操作时都传入整个 socket 集合，减少了内核和用户空间大量的数据拷贝和内存分配。
2. epoll 使用事件驱动的机制，内核里维护一个链表来记录就绪文件描述符。当某个 socket 有事件发生时，通过回调函数内核会将其加入到这个就绪事件列表中，当用户调用 epoll_wait() 函数时，只会返回有事件发生的文件描述符的集合，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。
epoll 支持两种事件触发模式，分别是边缘触发（edge-triggered，ET）和水平触发（level-triggered，LT）。一般来说，边缘触发的效率比水平触发的效率要高，因为边缘触发可以减少 epoll_wait 的系统调用次数，系统调用因为上下文切换占有一定的开销。select/poll 只有水平触发模式，epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。

根据小林文章所言，epoll没有使用mmap共享内存，也就是说还是不可避免的要将数据从内核拷贝到用户空间。

	select	poll	epoll
数据结构	固定长度的数组	链表	红黑树
获取就绪文件描述符时间复杂度	O(n)，主动轮询所有文件描述符	同select	O(1)，注册回调，事件驱动，通过就绪链表获取文件描述符
触发模式	水平触发	同select	水平触发、边缘触发
最大连接数	内核中的 FD_SETSIZE 限制，默认为 `1024`	仅受系统文件描述符限制	每1G内存10W连接

对应的应用场景：

考虑跨平台、连接数少（不超过1000），且都十分活跃（需要实时性），比如一个高速LAN环境，用select；
考虑跨平台、连接数多，用poll；
针对Linux平台，Socket量大但不活跃的情况，选epoll的边缘触发模式，相比于水平触发，它只会通知处理程序一次，直到该文件描述符上出现第二次可读写事件，不管有没有一次性读取完。

文件传输

DMA

设备在 CPU 不参与的情况下，通过直接内存访问（DMA）技术能够自行完成把设备 I/O 数据放入到内存。

在 DMA 技术下，进程是如何从磁盘读取文件？

用户进程借助系统调用 read ，向 OS 发出 I/O 请求，OS 收到后占用 CPU 给 DMA 控制器下发指令，告诉它读取多少数据，放在内存的哪个位置之后，将CPU让给其他进程；
DMA 控制器向磁盘控制器下发指令，通知它从磁盘读数据到磁盘内部的缓冲区中，当磁盘控制器的缓冲区被读满后，向 DMA 发起中断信号，告知自己缓冲区已满；
DMA 收到磁盘的信号，将磁盘控制器缓冲区中的数据拷贝到内核缓冲区（Page Cache）中，当DMA读取足够多的数据之后，向CPU发起中断信号；
CPU 收到 DMA 的信号，知道数据已经准备好，于是将数据从内核拷贝到用户空间，系统调用返回。

用 DMA 控制器代替 CPU ，从磁盘文件拷贝数据到内核缓冲区。

零拷贝

传统 I/O 传输文件

1 2	read(file, tmp_buf, len); write(socket, tmp_buf, len);

从硬盘读取数据，然后再通过网卡向外发送，需要进行 4 次上下文切换和 4 次数据拷贝，其中 2 次 DMA 完成发生在内存里的缓冲区和对应的硬件设备之间的数据拷贝，另外 2 次由 CPU 完成发生在内核态和用户态之间的数据拷贝。

零拷贝传输文件

1	sendfile(socket, file, offset, len);

在网卡支持SG-DMA技术的情况下，没有在内存层面去拷贝数据，所有的数据都是通过 DMA 来进行传输的，只需要 2 次上下文切换和 2 次数据拷贝。实际上，Kafka 和Nginx等已广泛利用零拷贝技术，但需要注意的是，零拷贝技术是不允许进程对文件内容作进一步的加工的，比如压缩数据再发送。

大文件传输用什么方式？

零拷贝技术针对小文件传输有良好的性能，如果用零拷贝来传输大文件，由于内核缓冲区（PageCache）长时间被大文件占据，其他「热点」的小文件可能就无法充分使用到 PageCache，造成磁盘读写的整体性能下降，且如果文件只是用于传输，没有额外的修改，那么缓存没有意义，浪费了 DMA 拷贝到内核缓冲区这次拷贝。

因此，在高并发的场景下，针对大文件传输，应该使用「异步 I/O + 直接 I/O」来替代零拷贝技术。

设备管理

Linux 存储系统的 I/O 由上到下可以分为三个层次，分别是文件系统层、通用块层、设备层。

文件系统层，包括虚拟文件系统和其他文件系统的具体实现，它向上为应用程序统一提供了标准的文件访问接口，向下会通过通用块层来存储和管理磁盘数据。
通用块层，包括块设备的 I/O 队列和 I/O 调度器，它会对文件系统的 I/O 请求进行排队，再通过 I/O 调度器，选择一个 I/O 发给下一层的设备层。
设备层，包括硬件设备、设备控制器和驱动程序，负责最终物理设备的 I/O 操作。

用一个问题来展开OS如何管理设备，键盘敲入字母时，操作系统期间发生了什么？

先来看看 CPU 的硬件架构，CPU 里面的内存接口，直接和系统总线通信，然后系统总线再接入一个 I/O 桥接器，这个 I/O 桥接器，另一边接入了内存总线，使得 CPU 和内存通信。再另一边，又接入了一个 I/O 总线，用来连接 I/O 设备，比如键盘、显示器等。

当用户输入了键盘字符，键盘控制器就会产生扫描码数据，并将其缓冲在键盘控制器的寄存器中，紧接着键盘中断控制器通过总线给 CPU 发送中断请求。

CPU 收到中断请求后，操作系统会保存被中断进程的 CPU 上下文，然后调用键盘的中断处理程序。

键盘的中断处理程序是在键盘驱动程序初始化时注册的，那键盘中断处理函数的功能就是从键盘控制器的寄存器的缓冲区读取扫描码，再根据扫描码找到用户在键盘输入的字符，如果输入的字符是显示字符，那就会把扫描码翻译成对应显示字符的 ASCII 码，比如用户在键盘输入的是字母 A，是显示字符，于是就会把扫描码翻译成 A 字符的 ASCII 码。

得到了显示字符的 ASCII 码后，就会把 ASCII 码放到「读缓冲区队列」，接下来就是要把显示字符显示屏幕了，显示器的驱动程序会定时从「读缓冲区队列」读取数据放到「写缓冲区队列」，最后把「写缓冲区队列」的数据一个一个写入到显示器控制器的寄存器中，最后将这些数据显示在屏幕里。

显示出结果后，恢复被中断进程的上下文。

Linux系统启动的过程

由小及大，每次都利用小规模的程序，启动更大规模的程序。

主板上电，加载BIOS -> BIOS自检 -> BIOS加载硬盘上的引导程序 -> 引导加载程序（例如，grub）可以访问文件系统，加载操作系统内核 -> 操作系统内核程序启动并确定运行级别 -> 操作系统初始化 -> 用户登录

BIOS 自检

BIOS是电脑启动时加载的第一个程序，它是计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序。主机接通电源后，系统将有一个对内部各个设备进行检查的过程，这是由一个通常称之为POST(Power On Self Test，上电自检）的程序来完成的。

如果自检没有问题，会根据BIOS中的引导选项中查找引导设备，然后读取设备的第一扇区，设备的第一个扇区（MBR）主要记录了系统的分区信息。

简单概括为：

主板上电，加载BIOS
BIOS上电自检
BIOS查找引导设备，将其第一扇区加载到内存，并跳转到扇区处的引导程序，将控制权交给引导程序

内核引导

具体的引导加载程序有很多种，grub、syslinux、bootmgr等等。这部分在磁盘上，BIOS或UEFI会把这部分加载到内存中，然后执行这部分程序。这部分的功能是为了加载更大的操作系统内核并传递参数给内核。

以grub(GRand Unified Bootloade)为例，BIOS将权限交给grub，grub在嵌入的映像中包含硬件及文件系统的驱动，因此，一旦嵌入的映像载入内存，grub即可访问文件系统。grub到/boot目录下去读取内核文件。读取成功后，grub完成了其作为操作系统引导加载程序的使命。下面将跳转到加载的内核映像去执行，将控制权交给内核。

运行init

内核启动系统的第一个进程INIT，因此INIT的进程号总是1，init进程是所有进程的发起者和控制者，所有如果init出现问题，系统随之垮掉。init读取配置文件/etc/inittab，决定启动的运行级别（runlevel）。

Linux系统有7个运行级别(runlevel) 运行级别0：系统停机状态，系统默认运行级别不能设为0，否则不能正常启动运行级别1：单用户工作状态，root权限，用于系统维护，禁止远程登陆运行级别2：多用户状态(没有NFS)运行级别3：完全的多用户状态(有NFS)，登陆后进入控制台命令行模式运行级别4：系统未使用，保留运行级别5：X11控制台，登陆后进入图形GUI模式运行级别6：系统正常关闭并重启，默认运行级别不能设为6，否则不能正常启动

系统初始化

系统确定运行级别，根据运行级别/etc/rc*.d执行相应的环境初始化，建立终端。

用户登录系统

输入用户名密码登陆系统。

面试问题汇总

进程管理

为什么要进程内存管理，进程的内存结构、进程间调度算法、进程同步与互斥

为了营造每个进程都能独占一台计算机的所有内存，引入虚拟化机制，让每个进程都有自己的虚拟内存空间，通过操作系统映射到物理内存上。

为了保证在进程间公平高效地分配CPU/内存资源，需要管理进程。

进程的内存结构中有这么几个字段，进程标识符、进程状态、指向父进程、子进程的指针、内存起始位置、寄存器副本等。

进程调度算法主要有先来先用、最短优先、时间片轮转等，以及综合以上各算法优点的多级反馈队列算法。

OS维护不同优先级的队列以及分配不同的时间片大小，当系统产生一个新进程时，放在优先级最高、时间片最小的队列上，一旦这个作业用完了在这个队列中的时间配额，就进入下一个优先级队列，其他进程同理，以及，为避免老进程等待过久，每经过一段时间就将该系统中所有工作重新加入最高优先级队列。

进程互斥指的是不同进程不能同时运行，进程同步指的是不同进程执行要有明确的先后之分，通常我们通过锁来实现进程互斥，通过信号量来实现进程同步。
什么是上下文切换，线程上下文怎么保存怎么恢复的，用户态内核态，进程线程协程，线程和协程比较

上下文切换是系统调度时先保存当前进程的状态值，恢复即将执行的进程的状态值。具体过程
1. 保存处理机上下文，包括程序计数器、栈寄存器等，更新在当前PCB中
2. 把当前进程PCB移入阻塞队列，OS从就绪队列中选出一个即将运行的进程
3. 用新进程PCB中的寄存器值更新当前处理机的上下文。
当两个线程属于同一个进程，因为虚拟内存空间、打开列表是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

为了保留OS对CPU的控制权，引入用户态内核态两种执行模式来保护系统，用户态下的进程如果要发出I/O请求需要通过系统调用切换到内核态。

协程，也叫做用户空间线程，由程序员自己写程序管理的一种比线程更轻量级的存在。

与线程相比，协程最大的优势就是极高的执行效率，协程占用资源少，由用户管理协程切换，不需要陷入内核态，且切换只需要修改程序计数器、栈等少数的状态值。以及不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

Python对协程的支持是通过generator实现的。传统的生产者-消费者模型是一个线程写消息，一个线程取消息，通过锁机制控制队列和等待，但一不小心就可能死锁。如果改用协程，生产者生产消息后，直接通过yield跳转到消费者开始执行，待消费者执行完毕后，切换回生产者继续生产，效率极高。
信号量是什么，互斥量能不能在进程中使用

信号量用来表示共享资源的数量，通过合理使用互斥量可以保持进程互斥和同步。
操作系统中的中断、僵尸进程（如何解决）、孤儿进程、守护进程等概念

我们平时说的中断都是指异步中断，比如硬中断，由硬件触发，CPU立即停下手上的工作去执行中断处理程序。

孤儿进程指的是一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作，孤儿进程不会对系统造成危害。

僵尸进程指的是被一个进程使用fork创建出来的子进程，如果该子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息导致该子进程成为僵尸进程，它的进程描述符仍然保存在系统中，占用进程号。

通过杀死僵尸进程的父进程，让所有的僵死进程变成孤儿进程，从而被init进程释放所占有的资源。

守护进程是运行在后台的一种特殊进程，它不需要用户输入就能运行而且提供某种服务，不是对整个系统就是对某个用户程序提供服务，如系统日志进程syslogd、 web服务器httpd和数据库服务器mysqld等。
进程请求资源死锁，如何在编程上防止死锁？
- 避免在一个同步方法中调用其它对象的耗时方法和同步方法。调用耗时方法会占用长时间的锁，调用其他对象的同步方法一定要注意释放锁。
- 以确定的顺序获得锁，破坏“循环等待条件”。针对多线程需要共同访问的资源进行线性排序，并赋予不同的序号，规定每一个线程必须按照序号递增的顺序请求资源。
- 锁持有的时间加一个时限，超时放弃。
- 使用事务时，尽量缩短事务的逻辑处理过程。
进程通信的方式有哪几种？那种的效率会更好？为什么？

管道、消息队列、共享内存+信号量、Socket。

效率更高的是Socket，不论是匿名管道还是命名管道还是消息队列，速度都很慢；共享内存速度是很快，但是需要手动加信号量来实现同步，如果进程间通信不考虑同步问题的话，适合用共享内存，如交换大数据的场合，比如视频、文件复制之类。而Socket不仅可以在不同主机上的进程通信，而且还支持本地快速通信，提供的API也比较成熟。
消费者生产者问题

IPC的一种经典情况，单生产者+单消费者+有界缓冲区的情况需要维护3个信号量，一个用于互斥访问缓冲区，一个用于消费者询问缓冲区是否有数据，一个用于生产者询问缓冲区是否有空位。
hashmap支持并发，如何上锁来保证锁粒度最小。

哈希表中每个桶（链表）都有一个锁，链表上每个节点都有一个锁，查找哈希表时不需要上锁，修改哈希表时需要先获取每个桶的锁，然后再获取需要修改的节点的锁。
线程与进程区别与联系？为什么进程切换代价比线程高，进程、线程的中断，这个过程是怎么样的？进程和线程相比，为什么慢？

进程是OS调度的基本单位，线程是CPU调度的基本单位，每个进程拥有一个完整的资源平台，比如内存空间、打开文件列表等，而同一个进程的线程是共享同一套内存空间和打开文件列表的，只维护自身的寄存器和栈。

进程切换相比线程切换需要多保存内存空间、打开列表等信息。

线程需要维护的只属于自己的资源少，所以创建销毁快速，执行效率高。
线程通信方式，线程的锁有哪些，互斥锁、读写锁、自旋锁的区别，介绍和应用场景，怎么防止锁的发生？

线程通信方式跟进程通信方式一样，有管道、共享内存+信号量等。

互斥锁是当线程请求不到资源的时候，进入阻塞队列，让出CPU资源给其他线程，当得到锁之后，唤醒进入就绪队列，等待系统调度。一般情况都用这种锁，但如果临界区的执行时间很短，这种方式带来的上下文切换会占用一定的系统开销。

自旋锁是当线程请求不到资源的时候，进入忙等状态，继续持有CPU资源，直到获取锁为止。适用于明确知道临界区的执行时间很短的情况。

读写锁是由互斥锁或者自旋锁发展而来的，针对于读多写少场景的一种锁。

可以通过破坏锁的四个必要条件来防止锁的发生，常见的有让多线程按顺序线性访问共享资源；增加一个线程持有锁的时长，超时主动放弃；避免同步方法的嵌套等。
多线程底层实现，多线程同步，线程池的实现方式，使用线程池的好处，线程池的设计思路，线程池中线程的数量由什么确定

多线程的底层实现是OS维护一个线程就绪队列，CPU通过时间片轮转的方式轮流执行不同的线程。

多线程同步可以通过信号量来实现。

线程池是一个线程阻塞队列，通过预创建的技术，在应用程序启动之后，立即创建一定数量的线程放入阻塞队列中，当任务到来后，线程池唤醒一个线程执行新任务，在任务执行完毕后线程也不退出，而是继续保持在池中等待下一次的任务。

使用线程池的好处在于能够有效应对高并发且请求时间短的场景。

通过维护任务队列、线程池、完成队列三部分来实现。

一个原则就是从更加有效地利用CPU资源角度出发，CPU密集型任务应配置尽可能小的线程，如配置CPU个数+1的线程数；IO密集型任务应配置尽可能多的线程，如配置两倍CPU个数+1。总体而言，线程数要尽可能少，尽量复用线程池中的每一个线程。
线程安全的理解，队列的线程安全如何实现，无锁队列怎么实现

只用两个锁，一个负责队列头、一个负责队列尾，同时添加假节点（解决链表中如果只有一个元素，head 和 tail 都指向同一个结点的问题），待补充
写道题：全局变量count=0，1个主线程打印start后，多个子线程按顺序对count+1，并打印出count值，count==n时，主线程打印end并退出，待补充
银行家问题、生产者消费者问题的扩展

待补充

内存管理

32位系统能访问多大内存？为什么要用虚拟内存？好处？虚拟内存分布，什么时候会由用户态陷入内核态(系统调用，异常)？内核态与用户态的区别？从用户态切换到内核态有哪几种方式？内核分几个部分？

\(2^{32} = 4GB\) 内存。通过虚拟内存可以造成一种进程拥有所有内存地址的假象，且程序员编程的时候可以无需考虑具体存储到哪一个物理地址上。

3种切换方式，当用户发起系统调用主动陷入内核态；当用户进程执行期间发生异常（缺页异常）或硬件中断（Ctrl+z）被动陷入内核态。

在内核态权限高，可以访问用户空间和内核空间的所有数据，可以执行一些与底层设备打交道的命令，比如磁盘读写、网卡读写等

内核分为进程管理系统、内存管理系统、I/O管理系统和文件管理系统四部分
分页与分段
- 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
- 对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段。
- 地址空间的维度：分页是一维地址空间，分段是二维的。
- 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
为什么要有页表，操作系统页面管理是怎样的？页面大小一般多少？过大或过小会怎样？页缓存

为了更好的进行内存虚拟化，引入分页的方式管理内存，即将地址空间分割成固定长度的分页，用页表记录分页情况。OS根据时空局部性原理换入换出页面，代表算法是LRU和LFU，LRU通过维护哈希表+双向链表的结构，优先淘汰最久不使用的页面。

页面大小一般是4KB，过大会导致内存碎片，浪费内存空间；过小会带来较大的页表项，增加寻址时TLB的额外开销。

页缓存是内核缓冲区，有两个优点，一是能够缓存最近被访问的数据，二是预读相邻的数据。
1G的内存可以装入2G的程序么？怎么装？

可以，在磁盘上开辟交换空间，根据时空局限性来选择优先级高的1G装入内存，其余暂时放在磁盘上，等待页面替换。
堆内存和栈内存的区别、什么时候才需要在堆内存分配空间、为什么程序不全部使用堆内存

堆内存由低向高增长，给程序动态申请内存使用，在C++中使用new, delete的时候在堆内存分配空间。

栈内存由高向低增长，给程序递归保存上下文使用，栈内存不需要手动分配，在程序中执行的每一个函数都会用分配栈内存。

一个程序的执行会动态增删大量生命周期短的变量，栈内存按顺序增加删除变量非常方便，但如果用堆内存的话，不仅要手动指定内存分配，还要手动回收，效率低下容易出错。

文件管理

说一下零拷贝

零拷贝是一种网络文件传输时避免CPU拷贝数据的技术，普通I/O传输文件时需要调用read、write一共4次上下文切换，4次数据拷贝，而通过sendfile的零拷贝技术只需要2次上下文切换，2次数据拷贝，加快了文件传输的效率。
同步/异步/阻塞/非阻塞 + Linux I/O，I/O多路复用epoll，是轮询的吗，epoll和select的区别，epoll为什么高效，epoll最大连接数

epoll不是轮询，而是通过epoll_ctl注册fd，一旦该fd就绪，内核就会采用类似callback的回调机制来激活该fd，epoll_wait便可以收到通知，避免轮询带来的低效。

相比于select，由于epoll是事件驱动，所以能够支持更大的文件连接数（每1G内存大约能监听10W个端口），更高效的I/O事件通知，且由于其只需要在用户空间和内核缓冲区之间拷贝有事件响应的文件描述符数据，对系统的开销更小。