操作系统.md

进程管理

一、进程与线程

线程是处理机调度的单位，进程是资源分配的单位

1、进程有哪些状态及状态转换？

进程一共有5种状态，分别是创建、就绪、运行（执行）、终止、阻塞。

• 运行状态就是进程占有CPU，正在CPU上运行。在单处理机环境下，每一时刻最多只有一个进程处于运行状态。
• 就绪状态就是说进程已处于准备运行的状态，即进程获得了除CPU之外的一切所需资源，一旦得到CPU即可运行。
• 阻塞状态就是进程正在等待某一事件而暂停运行，比如等待某资源为可用或等待I/O完成。即使CPU空闲，该进程也不能运行。
• 创建态：进程正在被创建，操作系统为进程分配资源、初始化PCB
• 终止态：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

运行态→阻塞态：往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。 阻塞态→就绪态：则是等待的条件已满足，只需分配到处理器后就能运行。 运行态→就绪态：不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。 就绪态→运行态：系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态。

补充：进程的挂起态与七状态模型

2、同步与异步的区别是什么？

同步与异步的区别在于调用结果的通知方式上。 同步执行一个方法后，需要等待结果返回，然后继续执行下去。 异步执行一个方法后，不会等待结果的返回，调用方定时主动去轮询调用结果或者被调用方在执行完成后通过回调来通知调用方。

3、阻塞与非阻塞的区别是什么？

阻塞与非阻塞的区别在于进程/线程在等待消息时，进程/线程是否是挂起状态。 阻塞调用在发出去后，消息返回之前，当前进程/线程会被挂起，直到有消息返回，当前进/线程才会被激活。 非阻塞调用在发出去后，不会阻塞当前进/线程，而会立即返回，可以去执行其他任务。

4、孤儿进程,僵尸进程,守护进程？

孤儿进程

• • 根据维基百科的解释，孤儿进程指的是在其父进程执行完成或被终止后仍继续运行的一类进程。孤儿进程与僵尸进程是完全不同。孤儿进程借用了现实中孤儿的概念，也就是父进程不在了，子进程还在运行，这时我们就把子进程的PPID设为1。操作系统会创建进程号为1的init进程，它没有父进程也不会退出，可以收养系统的孤儿进程。在现实中用户可能刻意使进程成为孤儿进程，这样就可以让它与父进程会话脱钩，成为后面会介绍的守护进程。

僵尸进程

• • 当一个进程完成它的工作终止之后,它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态
  • 一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。

僵尸进程

如果子进程先退出，父进程还没退出，那么子进程必须等到父进程捕获到了子进程的退出状态才真正结束，否则这个时候子进程就成为僵尸进程。

设置僵尸进程的目的是维护子进程的信息，以便父进程在以后某个时候获取。这些信息至少包括进程ID，进程的终止状态，以及该进程使用的CPU时间，所以当终止子进程的父进程调用wait或waitpid时就可以得到这些信息。如果一个进程终止，而该进程有子进程处于僵尸状态，那么它的所有僵尸子进程的父进程ID将被重置为1（init进程）。继承这些子进程的init进程将清理它们（也就是说init进程将wait它们，从而去除它们的僵尸状态）。

如何避免僵尸进程？

通过signal(SIGCHLD, SIG_IGN)通知内核对子进程的结束不关心，由内核回收。

如果不想让父进程挂起，可以在父进程中加入一条语句：signal(SIGCHLD,SIG_IGN);表示父进程忽略SIGCHLD信号，该信号是子进程退出的时候向父进程发送的。

父进程调用wait/waitpid等函数等待子进程结束，如果尚无子进程退出wait会导致父进程阻塞。waitpid可以通过传递WNOHANG使父进程不阻塞立即返回。

如果父进程很忙可以用signal注册信号处理函数，在信号处理函数调用wait/waitpid等待子进程退出。

通过两次调用fork。 父进程首先调用fork创建一个子进程然后waitpid等待子进程退出，子进程再fork一个孙进程后退出。这样子进程退出后会被父进程等待回收，而对于孙子进程其父进程已经退出所以孙进程成为一个孤儿进程，孤儿进程由init进程接管，孙进程结束后，init会等待回收。

第一种方法忽略SIGCHLD信号，这常用于并发服务器的性能的一个技巧因为并发服务器常常fork很多子进程，子进程终结之后需要服务器进程去wait清理资源。如果将此信号的处理方式设为忽略，可让内核把僵尸子进程转交给init进程去处理，省去了大量僵尸进程占用系统资源。

守护进程

• • 守护(Daemon)进程我们可以认为守护进程就是后台服务进程，因为它会有一个很长的生命周期提供服务，关闭终端不会影响服务，也就是说可以忽略某些信号。
  • 实现守护进程 首先要保证进程在后台运行，可以在启动程序后面加&，当然更原始的方法是进程自己fork然后结束父进程。

      if (pid=fork()) {
        exit(0); // Parent process
      }

• • 然后是与终端、进程组、会话(Session)分离。每个进程创建时都绑定一个终端，而且属于一个进程组(进程组也有GID不过等同进程组长的PID)，这些进程组在一个会话中，如果是子进程一般会从父进程继承这些信息，想要与环境分离可以使用以下的系统调用。
• • setsid();
• • 同样地我们会从父进程继承文件掩码(mask)，可以手动清理掩码。
• • umask(0);
• • 如果需要我们可以改变当前工作目录，避免运行时必须使用当前所在的文件系统。
  • 使用Nohup nohup命令，是让程序以守护进程运行的方式之一，程序运行后忽略SIGHUP信号，也就说关闭终端不会影响进程的运行。
  • 类似的命令还有disown

5、进程和线程的区别？

调度：进程是资源管理的基本单位，线程是程序执行的基本单位。

并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行 切换：线程上下文切换比进程上下文切换要快得多。 拥有资源： 进程是拥有资源的一个独立单位，线程不拥有系统资源，但是可以访问隶属于进程的资源。 系统开销： 创建或撤销进程时，系统都要为之分配或回收系统资源，如内存空间，I/O设备等，OS所付出的开销显著大于在创建或撤销线程时的开销，进程切换的开销也远大于线程切换的开销。

6、进程和线程的关系：

　 （1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。

​ （2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。

​ （3）处理机分给线程，即真正在处理机上运行的是线程。

​ （4）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。线程是指进程内的一个执行单元,也是进程内的可调度实体.

7、线程的分类？（用户级、内核级）

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

从线程的运行空间来说，分为用户级线程（user-level thread, ULT）和内核级线程（kernel-level, KLT）

内核级线程：这类线程依赖于内核，又称为内核支持的线程或轻量级进程。无论是在用户程序中的线程还是系统进程中的线程，它们的创建、撤销和切换都由内核实现。比如英特尔i5-8250U是4核8线程，这里的线程就是内核级线程

用户级线程：它仅存在于用户级中，这种线程是不依赖于操作系统核心的。应用进程利用线程库来完成其创建和管理，速度比较快，操作系统内核无法感知用户级线程的存在。

8、线程的实现方式

前面我们了解了引入线程的好处和引入线程的变化，以及线程的属性，那么线程如何实现呢？

线程的实现分为两类：用户级线程(User-Level Thread,UTL)和内核级线程(Kernel-Level Thread, KTL)l。内核级线程又称内核支持的线程。

（1）用户级线程

（2）内核级线程

（3）特殊的组合方式及重点注意

9、多线程模型

（1）多对一模型

（2）一对一模型

（3）多对多模型

• 此种模型效率是三种模型中最好的

10、多线程的优缺点

优点：

• 能适当提高程序的执行效率
• 能适当提高资源的利用率(CPU&内存)
• 线程上的任务执行后自动销毁

缺点：

• 开启线程需要占用一定的内存空间
• 如果开启大量的线程,会占用大量的内存空间,降低程序的性能
• 线程越多,cpu在调用线程上的开销就越大
• 程序设计更加复杂,比如线程简的通信,多线程的数据共享

https://www.jianshu.com/p/1556a462be72

总结:

线程和进程的区别在于,子进程和父进程有不同的代码和数据空间,而多个线程则共享数据空间,每个线程有自己的执行堆栈和程序计数器为其执行上下文.多线程主要是为了节约CPU时间,发挥利用,根据具体情况而定. 线程的运行中需要使用计算机的内存资源和CPU。

11、协程与线程的区别？

1. 线程和进程都是同步机制，而协程是异步机制。
2. 线程是抢占式，而协程是非抢占式的。需要用户释放使用权切换到其他协程，因此同一时间其实只有一个协程拥有运行权，相当于单线程的能力。
3. 一个线程可以有多个协程，一个进程也可以有多个协程。
4. 协程不被操作系统内核管理，而完全是由程序控制。线程是被分割的CPU资源，协程是组织好的代码流程，线程是协程的资源。但协程不会直接使用线程，协程直接利用的是执行器关联任意线程或线程池。
5. 协程能保留上一次调用时的状态。

12、并发和并行有什么区别？

并发就是在一段时间内，多个任务都会被处理；但在某一时刻，只有一个任务在执行。单核处理器可以做到并发。比如有两个进程A和B，A运行一个时间片之后，切换到B，B运行一个时间片之后又切换到A。因为切换速度足够快，所以宏观上表现为在一段时间内能同时运行多个程序。

并行就是在同一时刻，有多个任务在执行。这个需要多核处理器才能完成，在微观上就能同时执行多条指令，不同的程序被放到不同的处理器上运行，这个是物理上的多个进程同时进行。

13、进程与线程的切换流程？

进程上下文切换

进程上下文包含了进程执行所需要的所有信息。

用户地址空间：包括程序代码，数据，用户堆栈等；

控制信息：进程描述符，内核栈等；

硬件上下文：进程恢复前，必须装入寄存器的数据统称为硬件上下文。

进程切换分两步：

1、切换页表以使用新的地址空间，一旦去切换上下文，处理器中所有已经缓存的内存地址一瞬间都作废了。

2、切换内核栈和硬件上下文。

3、刷新TLB

4、系统调度器的代码执行

线程上下文切换

对于linux来说，线程和进程的最大区别就在于地址空间。 对于线程切换，第1步是不需要做的，第2和3步是进程和线程切换都要做的。所以明显是进程切换代价大

1. 线程上下文切换和进程上下文切换一个最主要的区别是线程的切换虚拟内存空间依然是相同的， 但是进程切换是不同的。这两种上下文切换的处理都是通过操作系统内核来完成的。 内核的这种切换过程伴随的最显著的性能损耗是将寄存器中的内容切换出。
2. 另外一个隐藏的损耗是上下文的切换会扰乱处理器的缓存机制。 简单的说，一旦去切换上下文，处理器中所有已经缓存的内存地址一瞬间都作废了。 还有一个显著的区别是当你改变虚拟内存空间的时候， 处理的页表缓冲（processor’s Translation Lookaside Buffer (TLB)）或者相当的神马东西会被全部刷新， 这将导致内存的访问在一段时间内相当的低效。但是在线程的切换中，不会出现这个问题。

14、一个进程在fork()的时候会复制什么信息

https://zhuanlan.zhihu.com/p/370705498

https://blog.csdn.net/xy010902100449/article/details/44851453

fork（）会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。在fork之后exec之前两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间，如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。而如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。

fork时子进程获得父进程数据空间、堆和栈的复制，所以变量的地址（当然是虚拟地址）也是一样的。

27. 什么是用户态和内核态？

用户态和系统态是操作系统的两种运行状态：

• 内核态：内核态运行的程序可以访问计算机的任何数据和资源，不受限制，包括外围设备，比如网卡、硬盘等。处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况。
• 用户态：用户态运行的程序只能受限地访问内存，只能直接读取用户程序的数据，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。

将操作系统的运行状态分为用户态和内核态，主要是为了对访问能力进行限制，防止随意进行一些比较危险的操作导致系统的崩溃，比如设置时钟、内存清理，这些都需要在内核态下完成 。

28. 用户态和内核态是如何切换的?

所有的用户进程都是运行在用户态的，但是我们上面也说了，用户程序的访问能力有限，一些比较重要的比如从硬盘读取数据，从键盘获取数据的操作则是内核态才能做的事情，而这些数据却又对用户程序来说非常重要。所以就涉及到两种模式下的转换，即用户态 -> 内核态 -> 用户态，而唯一能够做这些操作的只有 系统调用，而能够执行系统调用的就只有 操作系统。

一般用户态 -> 内核态的转换我们都称之为 trap 进内核，也被称之为 陷阱指令(trap instruction)。

他们的工作流程如下：

• 首先用户程序会调用 glibc 库，glibc 是一个标准库，同时也是一套核心库，库中定义了很多关键 API。
• glibc 库知道针对不同体系结构调用系统调用的正确方法，它会根据体系结构应用程序的二进制接口设置用户进程传递的参数，来准备系统调用。
• 然后，glibc 库调用软件中断指令(SWI) ，这个指令通过更新 CPSR 寄存器将模式改为超级用户模式，然后跳转到地址 0x08 处。
• 到目前为止，整个过程仍处于用户态下，在执行 SWI 指令后，允许进程执行内核代码，MMU 现在允许内核虚拟内存访问
• 从地址 0x08 开始，进程执行加载并跳转到中断处理程序，这个程序就是 ARM 中的 vector_swi()。
• 在 vector_swi() 处，从 SWI 指令中提取系统调用号 SCNO，然后使用 SCNO 作为系统调用表 sys_call_table 的索引，调转到系统调用函数。
• 执行系统调用完成后，将还原用户模式寄存器，然后再以用户模式执行。

25. 中断的处理过程?

1. 保护现场：将当前执行程序的相关数据保存在寄存器中，然后入栈。
2. 开中断：以便执行中断时能响应较高级别的中断请求。
3. 中断处理
4. 关中断：保证恢复现场时不被新中断打扰
5. 恢复现场：从堆栈中按序取出程序数据，恢复中断前的执行状态。

26. 中断和轮询有什么区别？

• 轮询：CPU对特定设备轮流询问。中断：通过特定事件提醒CPU。
• 轮询：效率低等待时间长，CPU利用率不高。中断：容易遗漏问题，CPU利用率不高。

二、处理机的调度

1、处理机调度的三个层次

2、三层调度的联系、对比

3、进程调度的方式

1. 非剥夺调度方式，又称非抢占方式。

2. 1. 即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

3. 剥夺调度方式，又称抢占方式。

4. 1. 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

4、进程调度（算法）策略有哪几种？

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

• 先来先服务调度算法
• 最短作业优先调度算法
• 高响应比优先调度算法
• 时间片轮转调度算法
• 最高优先级调度算法
• 多级反馈队列调度算法

1)、先来先服务（FCFS，First Come First Serve）：

• 非抢占式的调度算法，按照请求的顺序进行调度，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
• 有利于长作业，适用于 CPU 繁忙型作业的系统；但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。另外，对I/O密集型进程也不利，因为这种进程每次进行I/O操作之后又得重新排队。
• 

2)、短作业优先(SJF,Shortest Job First)：

• 非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
• **最短作业优先（Shortest Job First, SJF）**调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

SJF 调度算法

这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

• 

3)、最短剩余时间优先(SRTN)：

• 最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。
• 
• 

4)、高响应比优先调度算法(HRRN):

• 前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。
• 那么，高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：

从上面的公式，可以发现：

• 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行；

• 如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；

• 

先来先服务、短作业优先、高响应比优先调度算法总结

---

注:上述几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，

但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。

因此这三种算法一般适合用于早期的批处理系统，当然，先来先服务算法也常结合其他的算法使用，在现在也扮演着很重要的角色。

而适合用于交互式系统的调度算法将在下面介绍...

---

交互式系统的调度算法

5)、时间片轮转（RR,Round-Robin）：

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

• 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

另外，时间片的长度就是一个很关键的点：

• 因为进程切换都要保存进程的信息并且载入新进程的信息，
• 如果时间片设得太短会导致过多的进程上下文切换，在进程切换上就会花过多时间，降低了 CPU 效率；
• 如果设得太长又可能引起对短作业进程的响应时间变长。

通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。

6)、优先级调度：

前面的「时间片轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。

但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。

为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

进程的优先级可以分为，静态优先级或动态优先级：

• 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
• 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

7)、多级反馈队列调度算法:

1. 先来先服务算法的优点是公平
2. 短作业优先算法的优点是能尽快处理完短作业，平均等待/周转时间等参数很优秀
3. 时间片轮转调度算法可以让各个进程得到及时的响应
4. 优先级调度算法可以灵活地调整各种进程被服务的机会

多级反馈队列调度算法是对其他算法的一个折中权衡

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

顾名思义：

• 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
• 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

多级反馈队列

来看看，它是如何工作的：

• 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，时间片从小到大；
• 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，如果此时已经是在最下级的队列，则重新放回该队列队尾，以此类推，直至完成；
• 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

时间片轮转、优先级调度、多级反馈队列调度算法总结：

三、进程的同步与互斥

1、同步与异步的区别是什么？

同步与异步的区别在于调用结果的通知方式上。

同步执行一个方法后，需要等待结果返回，然后继续执行下去。

异步执行一个方法后，不会等待结果的返回，调用方定时主动去轮询调用结果或者被调用方在执行完成后通过回调来通知调用方。

2、什么是临界区，如何解决冲突？

每个进程中访问临界资源的那段程序称为临界区，一次仅允许一个进程使用的资源称为临界资源**。**许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

解决冲突的办法：

• 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入，如已有进程进入自己的临界区，则其它所 有试图进入临界区的进程必须等待；
• 进入临界区的进程要在有限时间内退出。
• 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

3、同步和互斥的区别：

当有多个线程的时候，经常需要去同步这些线程以访问同一个数据或资源。例如，假设有一个程序，其中一个线程用于把文件读到内存，而另一个线程用于统计文件中的字符数。当然，在把整个文件调入内存之前，统计它的计数是没有意义的。但是，由于每个操作都有自己的线程，操作系统会把两个线程当作是互不相干的任务分别执行，这样就可能在没有把整个文件装入内存时统计字数。为解决此问题，你必须使两个线程同步工作。

​ 所谓同步，是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。如果用对资源的访问来定义的话，同步是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

​ 所谓互斥，是指散布在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。如果用对资源的访问来定义的话，互斥某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

4、进程间通信方式有哪些？

进程间通信又称IPC(Inter-Process Communication),指多个进程之间相互通信，交换信息的方法。根据进程通信时信息量大小的不同,可以将进程通信划分为两大类型:

1. 低级通信,控制信息的通信(主要用于进程之间的同步,互斥,终止和挂起等等控制信息的传递)
2. 高级通信,大批数据信息的通信(主要用于进程间数据块数据的交换和共享,常见的高级通信有管道,消息队列,共享内存等).

• 管道（pipe）：管道这种通讯方式有两种限制，一是半双工的通信，数据只能单向流动，二是只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。 管道可以分为两类：匿名管道和命名管道。匿名管道是单向的，只能在有亲缘关系的进程间通信；命名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信，允许无亲缘关系进程间的通信。
• 信号（signal） ： 信号是一种比较复杂的通信方式，信号可以在任何时候发给某一进程，用于通知接收进程某个事件已经发生，而无需知道该进程的状态。

Linux系统中常用信号： （1）SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。

（2）SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。

（3）SIGQUIT：程序退出信号。程序运行过程中，按Ctrl+\\键将产生该信号。

（4）SIGBUS和SIGSEGV：进程访问非法地址。

（5）SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。

（6）SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。

（7）SIGTERM：结束进程信号。shell下执行kill 进程pid发送该信号。

（8）SIGALRM：定时器信号。

（9）SIGCLD：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。

• 信号量（semaphore）：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列（message queue）：消息队列是消息的链接表，存放在内核中并由消息队列标识符标识。包括Posix消息队列和System V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 共享内存( shared memory )：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
• 套接字（socket）：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

优缺点：

• 管道：速度慢，容量有限；
• Socket：任何进程间都能通讯，但速度慢；
• 消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题；
• 信号量：不能传递复杂消息，只能用来同步；
• 共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存。

5、进程间同步的方式有哪些？

1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

优点：保证在某一时刻只有一个线程能访问数据的简便办法。

缺点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。

2、互斥量：为协调共同对一个共享资源的单独访问而设计的。互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限。

优点：使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

缺点：

• 互斥量是可以命名的，也就是说它可以跨越进程使用，所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。
• 通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号量对象可以说是一种资源计数器。

3、信号量：为控制一个具有有限数量用户资源而设计。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了。

优点：适用于对Socket（套接字）程序中线程的同步。

缺点:

• 信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点；
• 信号量机制功能强大，但使用时对信号量的操作分散， 而且难以控制，读写和维护都很困难，加重了程序员的编码负担；
• 核心操作P-V分散在各用户程序的代码中，不易控制和管理，一旦错误，后果严重，且不易发现和纠正。

4、事件： 用来通知线程有一些事件已发生，从而启动后继任务的开始。

优点：事件对象通过通知操作的方式来保持线程的同步，并且可以实现不同进程中的线程同步操作。

6、线程间的通信方式

• 使用全局变量

• • 主要由于多个线程可能更改全局变量，因此全局变量最好声明为volatile

• 使用消息实现通信

• • 在Windows程序设计中，每一个线程都可以拥有自己的消息队列（UI线程默认自带消息队列和消息循环，工作线程需要手动实现消息循环），因此可以采用消息进行线程间通信sendMessage,postMessage。
  • 1)定义消息#define WM_THREAD_SENDMSG=WM_USER+20;
  • 2)添加消息函数声明afx_msg int OnTSendmsg();
  • 3)添加消息映射ON_MESSAGE(WM_THREAD_SENDMSG,OnTSM)
  • 4)添加OnTSM()的实现函数；
  • 5)在线程函数中添加PostMessage消息Post函数

• 使用事件CEvent类实现线程间通信

• • Event对象有两种状态：有信号和无信号，线程可以监视处于有信号状态的事件，以便在适当的时候执行对事件的操作。
  • 1)创建一个CEvent类的对象：CEvent threadStart;它默认处在未通信状态；
  • 2)threadStart.SetEvent();使其处于通信状态；
  • 3)调用WaitForSingleObject()来监视CEvent对象

7、线程同步的方式有哪些？

各个线程可以访问进程中的公共变量，资源，所以使用多线程的过程中需要注意的问题是如何防止两个或两个以上的线程同时访问同一个数据，以免破坏数据的完整性。数据之间的相互制约包括

1. 直接制约关系，即一个线程的处理结果，为另一个线程的输入，因此线程之间直接制约着，这种关系可以称之为同步关系
2. 间接制约关系，即两个线程需要访问同一资源，该资源在同一时刻只能被一个线程访问，这种关系称之为线程间对资源的互斥访问，某种意义上说互斥是一种制约关系更小的同步

线程间的同步方式有四种

1、临界区：当多个线程访问一个独占性共享资源时，可以使用临界区对象。拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止，以此达到用原子方式操 作共享资源的目的。

2、事件：事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。

3、互斥量：互斥对象和临界区对象非常相似，只是其允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，但是更节省资源，更有效率。

4、信号量：当需要一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。

区别：

• 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说互斥量可以跨越进程使用，但创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量 。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。
• 互斥量，信号量，事件都可以被跨越进程使用来进行同步数据操作。

---

死锁

1、死锁、饥饿、死循环的区别

**死锁：**各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

**饥饿：**由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先（SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

**死循环：**某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

2、什么是死锁？

什么是死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。

3、什么时候会发生死锁？

对不可剥夺资源的不合理分配，可能导致死锁

4、死锁产生的条件？

死锁产生的四个必要条件：（有一个条件不成立，则不会产生死锁）

• 互斥条件：一个资源一次只能被一个进程使用，只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。
• 请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，对已获得资源保持不放。
• 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
• 循环等待条件：存在进程资源的循环等待链。若干进程之间形成一种头尾相接的环形等待资源关系，链中的每一个进程已获得的资源同时被下一个进程所请求。

注意!发生死锁时一定有循环等待，但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)

5、如何处理死锁问题

常用的处理死锁的方法有：死锁预防、死锁避免、死锁检测、死锁解除、鸵鸟策略。

**（1）死锁的预防（静态策略）：**基本思想就是确保死锁发生的四个必要条件中至少有一个不成立：

• ① 破除资源互斥条件：把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。

• • 缺点：可行性不高，很多时候无法破坏互斥条件，并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。

• ② 破除“请求与保持”条件：实行资源预分配策略（静态分配方法），进程在运行之前，一次性申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

• • **缺点：**在很多情况下，无法预知进程执行前所需的全部资源，因为进程是动态执行的，同时也会降低资源利用率，导致降低了进程的并发性。
  • 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

• ③ 破除“不可剥夺”条件：

• • 方案一：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如:剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)
  • 方案二：当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。这意味着进程已经占有的资源会被暂时被释放，或者说被抢占了。
  • 缺点：
• • • 1、实现起来比较复杂
    • 2、释放已获得的资源可能造成前一阶段工作的失效。因此这种方法般只适用于易保存和恢复状态的资源，如CPU
    • 3、反复地申请和释放资源会增加系统开销，降低系统吞吐量。
    • 4、若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

• ④ 破除“循环等待”条件：采用顺序资源分配法：实行资源有序分配策略，对所有资源排序编号，按照顺序获取资源，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。

• • 缺点：
• • • 1、不方便增加新的设备，因为可能需要重新分配所有的编号
    • 2、进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
    • 3、必须按规定次序申请资源，用户编程麻烦

（2）死锁避免（动态策略）：

死锁预防通过约束资源请求，防止4个必要条件中至少一个的发生，可以通过直接或间接预防方法，但是都会导致低效的资源使用和低效的进程执行。

而死锁避免则允许前三个必要条件，但是通过动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。

所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。银行家算法是经典的死锁避免的算法。

（3）死锁检测（允许死锁发生）：

用于检测系统状态，以确定系统中是否发生了死锁

死锁预防策略是非常保守的，他们通过限制访问资源和在进程上强加约束来解决死锁的问题。

死锁检测则是完全相反，它不限制资源访问或约束进程行为，只要有可能，被请求的资源就被授权给进程。但是操作系统会周期性地执行一个算法检测前面的循环等待的条件。死锁检测算法是通过资源分配图来检测是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有存在环，也就是检测到死锁的发生。

• （1）如果进程-资源分配图中无环路，此时系统没有死锁。
• （2）如果进程-资源分配图中有环路，且每个资源类中只有一个资源，则系统发生死锁。
• （3）如果进程-资源分配图中有环路，且所涉及的资源类有多个资源，则不一定会发生死锁。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

（4）死锁解除（允许死锁发生）：

当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

死锁解除的常用方法就是终止进程和资源抢占，回滚。

1. **资源抢占：**就是从一个或者多个死锁进程那里抢占一个或多个资源。

2. 进程终止法（撤销进程法）：

3. 1. 就是简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；
   2. **优缺点：**这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。

4. **进程回退法：**让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

（5）鸵鸟策略：

把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任何措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

6、银行家算法：

数据结构:

1. 长度为m的一维数组Available表示还有多少可用资源
2. n*m矩阵Max表示各进程对资源的最大需求数
3. n*m矩阵Allocation表示已经给各进程分配了多少资源
4. Max- Allocation = Need矩阵表示各进程最多还需要多少资源
5. 用长度为m的一位数组Request表示进程此次申请的各种资源数

银行家算法步骤:

①检查此次申请是否超过了之前声明的最大需求数

②检查此时系统剩余的可用资源是否还能满足这次请求

③试探着分配，更改各数据结构

④用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

1. 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
2. 不断重复上述过程,看最终是否能让所有进程都加入安全序列。

注意：系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

内存管理

1. 物理地址、逻辑地址、有效地址、线性地址、虚拟地址的区别?

物理地址就是内存中真正的地址，它就相当于是你家的门牌号，你家就肯定有这个门牌号，具有唯一性。不管哪种地址，最终都会映射为物理地址。

在实模式下，段基址 + 段内偏移经过地址加法器的处理，经过地址总线传输，最终也会转换为物理地址。

但是在保护模式下，段基址 + 段内偏移被称为线性地址，不过此时的段基址不能称为真正的地址，而是会被称作为一个选择子的东西，选择子就是个索引，相当于数组的下标，通过这个索引能够在 GDT 中找到相应的段描述符，段描述符记录了段的起始、段的大小等信息，这样便得到了基地址。如果此时没有开启内存分页功能，那么这个线性地址可以直接当做物理地址来使用，直接访问内存。如果开启了分页功能，那么这个线性地址又多了一个名字，这个名字就是虚拟地址。

不论在实模式还是保护模式下，段内偏移地址都叫做有效地址。有效抵制也是逻辑地址。

线性地址可以看作是虚拟地址，虚拟地址不是真正的物理地址，但是虚拟地址会最终被映射为物理地址。下面是虚拟地址 -> 物理地址的映射。

2. 内存的分配与回收

2.1 连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间。

1）单一连续分配

只支持单道程序，内存分为系统区和用户区，用户程序放在用户区

无外部碎片，有内部碎片

• 单一连续分配是最简单的内存分配方式
• 只能在单用户、单进程的操作系统中使用
• 内存中只能有一道用户程序，用户程序独占整个用户区空间。

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据;用户区用于存放用户进程相关数据。

优点:实现简单;无外部碎片;可以采用覆盖技术扩充内存;不一定需要采取内存保护（(eg:早期的PC操作系统MS-DoS）。

缺点:只能用于单用户、单任务的操作系统中;有内部碎片:存储器利用率极低。

2）固定分区分配

支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业

无外部碎片，有内部碎片

• 固定分区分配是支持多道程序的最简单存储分配方式
• 内存空间被划分为若干固定大小的区域
• 每一个分区只提供给一个程序所使用，互不干扰

将主存分为若干个分区，每一个分区提供给某一个进程所使用，这就是固定分区的分配方法

分区大小相等:缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如:钢铁广有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序)

分区大小不等:增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如:划分多个小分区、适量中等分区、少量大分区)

3）动态分区分配（可变分区分配）

支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区

无内部碎片，有外部碎片

• 根据进程实际需要，动态分配内存空间
• 涉及到相关数据结构和具体的一些算法

空闲分区表数据结构

假设主存中有若干个分区，有些被使用而有些未被使用，这样就需要一个数据结构去存储某一个分区它是否被使用了，此时就需要空闲表数据结构

在表中有若干个分区，每一个分区都有一个标记，0或1，0表示未被使用，1表示被使用。这就是动态分区空闲表数据结构

空闲分区链数据结构

这个是使用双向链表来保存动态分区中的空闲区域。将所有分散的空闲区域，通过链表进行首尾相连，组成一个空闲链表，但是，会存在像下图中空闲区2和3是连续的，因此可以将节点2和节点3给合并起来，这样就可以减少空闲链表的节点。因此，每个节点的大小不一样，所以需要在每个节点里边存储记录这个节点可存储的容量。这个就是动态分区空闲链数据结构

4）内部碎片与外部碎片

动态分区分配没有内部碎片，但是有外部碎片。

内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。

外部碎片，是指内存中的某些空闲分区由于太小而难以利用。如下：

可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。

2.2 内存回收

内存回收过程，可能有以下几种情况：

• 回收区和一块空闲区相邻，且回收区在空闲区下边
• 回收区和一块空闲区相邻，且空闲区在回收区下边
• 回收区在两块空闲区中间
• 单独的回收区

每种情况的回收过程

回收区在空闲区下边

使用空闲链表的数据结构来保存空闲区，

• 不需要新建空闲链表节点、
• 只需要将空闲区1的容量增大为空闲区即可(也就是将回收区包含进来)
• 两个相邻的空闲区合并为一个

回收区在空闲区上边

• 两个相邻的空闲区合并为一个（将回收区与空闲区合并）
• 新的空闲区使用回收区的地址

回收区位于两个空闲区中间

• 三个相邻的空闲分区合并为一个（将空闲区1、空闲区2和回收区合并）
• 新的空闲区使用空闲区1的地址

单独的回收区

• 为回收区创建新的空闲节点
• 插入到相应的空闲区链表中去

3. 动态分区分配的四种算法（首次适应算法、最佳适应算法、最坏适应算法、临近适应算法）

当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。

• 首次适应算法(FF算法)
• 最佳适应算法(BF算法)
• 快速适应算法(QF算法)

这些算法是实际进行动态内存分配所使用的算法。

1）首次适应算法(First Fit算法)

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

每一次进行内存分配时，从开始顺序查找适合内存区(主要使用空闲链的数据结构)

若没有合适的空闲区，则该次分配失败，如果找到了，就将该空闲区划分给这个进程使用。每次都是从头部开始，使得头部地址空间不断被划分

2）最佳（小）适应算法(Best Fit算法)

算法思想：由于冬天分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

• 最佳适应算法要求空闲区链表按照容量大小排序
• 遍历空闲区链表找到最佳空闲区

如何实现：空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。在需要内存的时候，从节点头部开始遍历，寻找最佳的空闲区节点。这种算法的好处就是可以避免一种大材小用的情况，因为它是从小到大遍历这个空闲链表的，所以它匹配到的第一个合适的空闲区，一定是最佳的。

缺点:每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

3）最坏（大）适应算法（Worst Fit）

算法思想:为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点:每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

4）临近适应算法（Next Fit）

算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）

四种算法的比较

4. 什么是分页存储（页号、页偏移量等）

基本分页存储管理的思想——把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

把内存空间划分为大小相等且固定的块，作为主存的基本单位。因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录映射关系，以实现从页号到物理块号的映射。

1. 一个进程对应一张页表
2. 进程的每一页对应一个页表项
3. 每个页表项由“页号”和“块号”组成
4. 页表****记录进程页面和实际存放的内存块之间的对应关系.
5. 每个页表项的长度是相同的，页号是“隐含”的

访问分页系统中内存数据需要两次的内存访问 (一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；第二次就是根据第一次得到的物理地址访问内存取出数据)。

5. 基本分段存储管理（段表、地址变换、信息共享）

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址。

内存分配规则：以段位单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。

分段内存管理当中，地址是二维的，一维是段号，二维是段内地址；其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。

6. 分页和分段有什区别？

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

• 分页对程序员是透明的，但是分段需要程序员显式划分每个段。

• 页的大小固定且由系统决定；段的长度却不固定，决定于用户编写的程序。

• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址

• 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址

• 分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

• 分段比分页更容易实现信息的共享和保护****。

访问一个逻辑地址需要几次访存?

• 分页（单级页表):第一次访存――查内存中的页表，第二次访存――访问目标内存单元。总共两次访存
• 分段:第一次访存――查内存中的段表，第二次访存――访问目标内存单元。总共两次访存

与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

分段比分页更容易实现信息的共享和保护****。

不能被修改的代码称为纯代码或可重入代码〈不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的

7. 为什么分页不方便实现信息共享和保护？

8. 段页式存储管理（段表、页表）

1）分页、分段的优缺点分析

2）分段+分页=段页式管理

• 将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
• 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
• 逻辑地址结构:(段号，页号，页内偏移量)

3）段页式存储的段表、页表

• 每个段对应一个段表项。各段表项长度相同，由段号（隐含)、页表长度、页表存放地址组成
• 每个页对应一个页表项。各页表项长度相同，由页号（隐含)、页面存放的内存块号组成

4）访问一个逻辑地址所需访存次数

• 第一次——查段表、第二次——查页表、第三次——访问目标单元
• 可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存

9. 什么是交换空间？

操作系统把物理内存(physical RAM)分成一块一块的小内存，每一块内存被称为页(page)。当内存资源不足时，Linux把某些页的内容转移至硬盘上的一块空间上，以释放内存空间。硬盘上的那块空间叫做交换空间(swap space),而这一过程被称为交换(swapping)。物理内存和交换空间的总容量就是虚拟内存的可用容量。

用途：

• 物理内存不足时一些不常用的页可以被交换出去，腾给系统。
• 程序启动时很多内存页被用来初始化，之后便不再需要，可以交换出去。

10. 虚拟内存的基本概念

11. 虚拟内存的定义和特征？

虚拟内存就是说，让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。程序不需要全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需要换出一些数据。

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

虚拟内存有一下三个主要特征:

• 多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性:在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

12. 虚拟内存的实现方式有哪些?

虚拟内存中，允许将一个作业分多次调入内存。釆用连续分配方式时，会使相当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式：

• 请求分页存储管理。
• 请求分段存储管理。
• 请求段页式存储管理。

主要区别：

• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。（操作系统需要提供请求调页（或请求掉段）的功能）
• 若内存空间不够用，由操作系统负责将内存中暂时用不到的信息换出外存。（操作系统需要提供页面置换（或段置换）的功能）

13. 请求分页管理方式（请求页表、缺页中断机构、地址变换机构）

1）页表机制——请求页表与基本页表的区别

2）缺页中断机构

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断

假设此时要访问逻辑地址=(页号，页内偏移量)= (0,1024)

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

3）地址变换机构

14. 页面替换算法有哪些？

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面的换入、换出需要磁盘I/o，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

• 最佳置换算法（OPT）最优算法每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。

• 先进先出置换算法**FIFO** 每次选择淘汰的页面是最早进入内存的页面

• • 实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
  • Belady异常― ― 当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
  • 只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

• 时钟置换算法**CLOCK** **：**是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU,Not Recently Used）

• • **实现方法：**为每个页面设置一个访问位，把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。
  • 当发生缺页中断时，算法首先检查表针指向的页面：
• • • 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
    • 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；
    • 若第一轮扫描中所有页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）

• 最近最久未使用**LRU** ：每次淘汰的页面是最近最久未使用的页面

• • 实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。
  • 是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。性能好，实现困难，开销大。

• **最不常用算法(LFU)：**当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。

• • **实现方法：**对每个页面设置一个「访问计数器」，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。
  • 看起来很简单，每个页面加一个计数器就可以实现了，但是在操作系统中实现的时候，我们需要考虑效率和硬件成本的。
  • 要增加一个计数器来实现，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。
  • LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。
  • 那这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。

最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。

15. 为什么虚拟地址空间切换会比较耗时？

进程都有自己的虚拟地址空间，把虚拟地址转换为物理地址需要查找页表，页表查找是一个很慢的过程，因此通常使用Cache来缓存常用的地址映射，这样可以加速页表查找，这个Cache就是TLB（translation Lookaside Buffer，TLB本质上就是一个Cache，是用来加速页表查找的）。

由于每个进程都有自己的虚拟地址空间，那么显然每个进程都有自己的页表，那么当进程切换后页表也要进行切换，页表切换后TLB就失效了，Cache失效导致命中率降低，那么虚拟地址转换为物理地址就会变慢，表现出来的就是程序运行会变慢，而线程切换则不会导致TLB失效，因为线程无需切换地址空间，因此我们通常说线程切换要比较进程切换块，原因就在这里。

16. 什么是缓冲区溢出？有什么危害？

缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。

危害有以下两点：

• 程序崩溃，导致拒绝额服务
• 跳转并且执行一段恶意代码

造成缓冲区溢出的主要原因是程序中没有仔细检查用户输入。

文件管理

1、磁盘调度算法

我们来看看磁盘的结构，如下图：

磁盘的结构 常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，一般会有多个盘片，每个盘面都有自己的磁头。右边的图就是一个盘片的结构，盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是 512 字节。那么，多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面，如上图里中间的样子。

磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。

寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。

假设有下面一个请求序列，每个数字代表磁道的位置：

98，183，37，122，14，124，65，67

初始磁头当前的位置是在第 53 磁道。

接下来，分别对以上的序列，作为每个调度算法的例子，那常见的磁盘调度算法有：

• 先来先服务算法
• 最短寻道时间优先算法
• 扫描算法算法
• 循环扫描算法
• LOOK 与 C-LOOK 算法

4.1. 先来先服务

先来先服务（First-Come，First-Served，FCFS），顾名思义，先到来的请求，先被服务。

那按照这个序列的话：

98，183，37，122，14，124，65，67

那么，磁盘的写入顺序是从左到右，如下图：

先来先服务

先来先服务算法总共移动了 640 个磁道的距离，这么一看这种算法，比较简单粗暴，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很差，因为寻道时间过长

4.2. 最短寻道时间优先

最短寻道时间优先（Shortest Seek First，SSF）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求，还是以这个序列为例子：

98，183，37，122，14，124，65，67

那么，那么根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的顺序：

65，67，37，14，98，122，124，183

最短寻道时间优先

磁头移动的总距离是 236 磁道，相比先来先服务性能提高了不少。

但这个算法可能存在某些请求的饥饿，因为本次例子我们是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于 183 磁道的，那么 183 磁道可能永远不会被响应，于是就产生了饥饿现象，这里产生饥饿的原因是磁头在一小块区域来回移动。

4.3. 扫描算法

最短寻道时间优先算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。

为了防止这个问题，可以规定：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法。

这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。

还是以这个序列为例子，磁头的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假设扫描调度算先朝磁道号减少的方向移动，具体请求则会是下列从左到右的顺序：

37，14，0，65，67，98，122，124，183

扫描算法

磁头先响应左边的请求，直到到达最左端（ 0 磁道）后，才开始反向移动，响应右边的请求。

扫描调度算法性能较好，不会产生饥饿现象，但是存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异。

4.4. 循环扫描算法

扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。

循环扫描（Circular Scan, CSCAN ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。

还是以这个序列为例子，磁头的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假设循环扫描调度算先朝磁道增加的方向移动，具体请求会是下列从左到右的顺序：

65，67，98，122，124，183，199，0，14，37

循环扫描算法

磁头先响应了右边的请求，直到碰到了最右端的磁道 199，就立即回到磁盘的开始处（磁道 0），但这个返回的途中是不响应任何请求的，直到到达最开始的磁道后，才继续顺序响应右边的请求。

循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。

4.5. LOOK 与 C-LOOK算法

我们前面说到的扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。

那这其实是可以优化的，优化的思路就是磁头在移动到「最远的请求」位置，然后立即反向移动。

那针对 SCAN 算法的优化则叫 LOOK 算法，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。

LOOK 算法

而针 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。

C-LOOK 算法

本文摘自: 调度算法

I/O管理

1. 讲一讲IO多路复用？

IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取，它就通知该进程。IO多路复用适用如下场合：

• 当客户处理多个描述字时（一般是交互式输入和网络套接口），必须使用I/O复用。
• 当一个客户同时处理多个套接口时，而这种情况是可能的，但很少出现。
• 如果一个TCP服务器既要处理监听套接口，又要处理已连接套接口，一般也要用到I/O复用。
• 如果一个服务器即要处理TCP，又要处理UDP，一般要使用I/O复用。
• 如果一个服务器要处理多个服务或多个协议，一般要使用I/O复用。
• 与多进程和多线程技术相比，I/O多路复用技术的最大优势是系统开销小，系统不必创建进程/线程，也不必维护这些进程/线程，从而大大减小了系统的开销。

2. 硬链接和软链接有什么区别？

• 硬链接就是在目录下创建一个条目，记录着文件名与 inode 编号，这个 inode 就是源文件的 inode。删除任意一个条目，文件还是存在，只要引用数量不为 0。但是硬链接有限制，它不能跨越文件系统，也不能对目录进行链接。
• 符号链接文件保存着源文件所在的绝对路径，在读取时会定位到源文件上，可以理解为 Windows 的快捷方式。当源文件被删除了，链接文件就打不开了。因为记录的是路径，所以可以为目录建立符号链接。

3. Unix 常见的IO模型：

对于一次IO访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。所以说，当一个read操作发生时，它会经历两个阶段：

• 等待数据准备就绪 (Waiting for the data to be ready)
• 将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

正式因为这两个阶段，linux系统产生了下面五种网络模式的方案：

• 阻塞式IO模型(blocking IO model)
• 非阻塞式IO模型(noblocking IO model)
• IO复用式IO模型(IO multiplexing model)
• 信号驱动式IO模型(signal-driven IO model)
• 异步IO式IO模型(asynchronous IO model)

对于这几种 IO 模型的详细说明，可以参考这篇文章：https://juejin.cn/post/6942686874301857800#heading-13

其中，IO多路复用模型指的是：使用单个进程同时处理多个网络连接IO，他的原理就是select、poll、epoll 不断轮询所负责的所有 socket，当某个socket有数据到达了，就通知用户进程。该模型的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。

4. select、poll 和 epoll 之间的区别?

（1）select：时间复杂度 O(n)

select 仅仅知道有 I/O 事件发生，但并不知道是哪几个流，所以只能无差别轮询所有流，找出能读出数据或者写入数据的流，并对其进行操作。所以 select 具有 O(n) 的无差别轮询复杂度，同时处理的流越多，无差别轮询时间就越长。

（2）poll：时间复杂度 O(n)

poll 本质上和 select 没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个 fd 对应的设备状态， 但是它没有最大连接数的限制，原因是它是基于链表来存储的。

（3）epoll：时间复杂度 O(1)

epoll 可以理解为 event poll，不同于忙轮询和无差别轮询，epoll 会把哪个流发生了怎样的 I/O 事件通知我们。所以说 epoll 实际上是事件驱动（每个事件关联上 fd）的。

select，poll，epoll 都是 IO 多路复用的机制。I/O 多路复用就是通过一种机制监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），就通知程序进行相应的读写操作。但 select，poll，epoll 本质上都是同步 I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步 I/O 则无需自己负责进行读写，异步 I/O 的实现会负责把数据从内核拷贝到用户空间。

	select	poll	epoll
操作方式	遍历	遍历	回调
底层实现	数组	链表	红黑树
IO效率	每次调用都进行线性遍历,时间复杂度O(n)	每次调用都是线性遍历,时间复杂度O(n)	事件通知方式,每当fd就绪,系统注册的回调函数就会被调用,将就绪fd放到readyList里面,时间复杂度O(1)
最大连接数	1024（x86）或2048（x64）	无上限	无上限
fd拷贝	每次调用select，都需要把fd集合从用户态拷贝到内核态	每次调用poll，都需要把fd集合从用户态拷贝到内核态	调用epoll_ctl时拷贝进内核并保存，之后每次epoll_wait不拷贝(mmap内存映射技术,降低拷贝的资源消耗)

5.select_poll_epoll详解