## 虚拟内存 **虚拟内存**是逻辑存在的内存，他的主要作用的简化内存管理。 总的来说虚拟内存提供了以下几个功能 1. **隔离进程**：物理内存通过虚拟地址空间访问，虚拟地址空间与进程一一对应。每个进程都认为自己拥有了整个物理内存，进程之间彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。 2. **提升物理内存利用率**：有了虚拟地址空间后，操作系统只需要将进程当前正在使用的部分数据或指令加载入物理内存。 3. **简化内存管理**：进程都有一个一致且私有的虚拟地址空间，程序员不用和真正的物理内存打交道，而是借助虚拟地址空间访问物理内存，从而简化了内存管理。 4. **提供更大的可使用内存空间**：可以让程序拥有超过系统物理内存大小的可用内存空间。这是因为当物理内存不够用时，可以利用磁盘充当，将物理内存页（通常大小为 4 KB）保存到磁盘文件（会影响读写速度），数据或代码页会根据需要在物理内存与磁盘之间移动。 ## 虚拟地址与物理内存地址是如何映射的？ MMU**(Memory Management Unit，内存管理单元)**将虚拟地址翻译为物理地址的主要机制有 3 种: 1. 分段机制 2. 分页机制 3. 段页机制 其中，现代操作系统广泛采用分页机制，需要重点关注！ ### 分段机制 程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。**不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。** ![image-20230508141543630](assets/image-20230508141543630.png) 分段机制容易出现外部内存碎片，即在段与段之间留下碎片空间(不足以映射给虚拟地址空间中的段)。从而造成物理内存资源利用率的降低。解决「外部内存碎片」的问题就是**内存交换**（内存交换空间就是swap空间）。但是**如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。**所以为了解决内存分段的「外部内存碎片和内存交换效率低」的问题，就出现了内存分页。 ### 分页机制 **分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小**。在 Linux 下，每一页的大小为 `4KB`。 ![image-20230508142326378](assets/image-20230508142326378.png) 页表是存储在内存里的，**内存管理单元** （MMU）就做将虚拟内存地址转换成物理地址的工作。 内存分页由于内存空间都是预先划分好的，也就不会像内存分段一样，在段与段之间会产生间隙非常小的内存，这正是分段会产生外部内存碎片的原因。而**采用了分页，页与页之间是紧密排列的，所以不会有外部碎片。**但是，因为内存分页机制分配内存的最小单位是一页，即使程序不足一页大小，我们最少只能分配一个页，所以页内会出现内存浪费，所以针对**内存分页机制会有内部内存碎片**的现象。 #### 多级页表 为了解决一级页表过大，导致占用内存过多的问题。所以就产生了多级页表 #### TLB 多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。 TLB即为页表缓存、转址旁路缓存、快表等。有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。 ![image-20230508143024494](assets/image-20230508143024494.png) ### 段页机制 内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为**段页式内存管理**。 虚拟内存地址结构就由**段号、段内页号和页内位移**三部分组成。 ![image-20230508143143138](assets/image-20230508143143138.png) ## 缺页中断 进程访问的虚拟地址在页表中查不到时，系统会产生一个**缺页异常**，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。 缺页中断主要分为一下两种： * **硬性页缺失（Hard Page Fault）**：物理内存中没有对应的物理页。此时MMU就会建立相应的虚拟页和物理页的映射关系。 如果发生硬性页缺失，CPU会看是否有空闲的物理内存，如果有，就直接分配物理内存，并建立虚拟内存与物理内存之间的映射关系。 如果物理内存中没有空闲的物理页面（有虚拟内存可以用，不会发生OOM）可用的话。操作系统就必须将物理内存中的一个物理页淘汰出去，这样就可以腾出空间来加载新的页面了。更新页表主要有一下几种算法 1. **最佳页面置换算法（OPT，Optimal）**：优先选择淘汰的页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，只是理论最优的页面置换算法，可以作为衡量其他置换算法优劣的标准。 2. **先进先出页面置换算法（FIFO，First In First Out）** : 最简单的一种页面置换算法，总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。该算法易于实现和理解，一般只需要通过一个 FIFO 队列即可需求。不过，它的性能并不是很好。 3. **最近最久未使用页面置换算法（LRU ，Least Recently Used）**：LRU 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。LRU 算法是根据各页之前的访问情况来实现，因此是易于实现的。OPT 算法是根据各页未来的访问情况来实现，因此是不可实现的。 4. **最少使用页面置换算法（LFU，Least Frequently Used）** : 和 LRU 算法比较像，不过该置换算法选择的是之前一段时间内使用最少的页面作为淘汰页。 * **软性页缺失（Soft Page Fault）**：物理内存中有对应的物理页，但虚拟页还未和物理页建立映射。此时MMU就会建立相应的虚拟页和物理页的映射关系。 ## 在 4GB 物理内存的机器上，申请 8G 内存会怎么样？ 32 位操作系统和 64 位操作系统的虚拟地址空间大小是不同的，在 Linux 操作系统中，虚拟地址空间的内部又被分为**内核空间和用户空间**两部分，如下所示： ![img](assets/3a6cb4e3f27241d3b09b4766bb0b1124.png) - 在 32 位操作系统，因为进程理论上最大能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。 - 在 64 位操作系统，因为进程理论上最大能申请 128 TB 大小的虚拟内存（没有被访问的前提下），即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。如果这块虚拟内存被访问了，要看系统有没有 Swap 分区 - 如果没有 Swap 分区，因为物理空间不够，进程会被操作系统杀掉，原因是 OOM（内存溢出）； - 如果有 Swap 分区，即使物理内存只有 4GB，程序也能正常使用 8GB 的内存，进程可以正常运行； ## swap 这种，将内存数据换出磁盘，又从磁盘中恢复数据到内存的过程，就是 Swap 机制负责的。 Swap 就是把一块磁盘空间或者本地文件，当成内存来使用，它包含换出和换入两个过程 ## 进程和线程 * **进程（Process）** 是指计算机中正在运行的一个程序实例。操作系统的资源分配单位，进程是资源（包括内存、打开的文件等）分配的单位， * **线程（Thread）** 也被称为轻量级进程，更加轻量。多个线程可以在同一个进程中同时执行，并且共享进程的资源比如内存空间、文件句柄、网络连接等。CPU资源的最小分配单位。线程是 CPU 调度的单位； ### PCB 是什么？包含哪些信息？ **PCB（Process Control Block）** 即进程控制块，是操作系统中用来管理和跟踪进程的数据结构，每个进程都对应着一个独立的 PCB。你可以将 PCB 视为进程的大脑。 当操作系统创建一个新进程时，会为该进程分配一个唯一的进程 ID，并且为该进程创建一个对应的进程控制块。当进程执行时，PCB 中的信息会不断变化，操作系统会根据这些信息来管理和调度进程。 **进程描述信息：** - 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符； - 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务； **进程控制和管理信息：** - 进程当前状态，如 new、ready、running、waiting 或 blocked 等； - 进程优先级：进程抢占 CPU 时的优先级； **资源分配清单：** - 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。 **CPU 相关信息：** - CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。 ### 进程间的通信方式有哪些？ 1. **管道/匿名管道(Pipes)**：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。 2. **信号(Signal)**：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生； 3. **消息队列(Message Queuing)**：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显式地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。**消息队列克服了信号承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺点。** 4. **信号量(Semaphores)**：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。 5. **共享内存(Shared memory)**：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。 6. **套接字(Sockets)** : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。 ### 进程和线程的区别 - 线程是进程划分成的更小的运行单位,一个进程在其执行的过程中可以产生多个线程。 - 线程和进程最大的不同在于基本上各进程是独立的，而各线程则不一定，因为同一进程中的线程极有可能会相互影响。 - 线程执行开销小，但不利于资源的管理和保护；而进程正相反。 ### 线程的通信方式 * 互斥量 * 信号量 ### 线程间的同步的方式有哪些？ 下面是几种常见的线程同步的方式： 1. **互斥锁**：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。 2. **读写锁**：允许多个线程同时读取共享资源，但只有一个线程可以对共享资源进行写操作。 3. **信号量**：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。 4. **屏障**：屏障是一种同步原语，用于等待多个线程到达某个点再一起继续执行。当一个线程到达屏障时，它会停止执行并等待其他线程到达屏障，直到所有线程都到达屏障后，它们才会一起继续执行。 5. **事件** :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。 ## 进程与线程的上下文切换 ### 进程 **一个进程切换到另一个进程运行，称为进程的上下文切换** **进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。** > 发生进程上下文切换有哪些场景？ - 为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行； - 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行； - 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度； - 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；软件中断 - 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；硬件中断 ### 线程 **线程是调度的基本单位，而进程则是资源拥有的基本单位**。 对于线程和进程，我们可以这么理解： - 当进程只有一个线程时，可以认为进程就等于线程； - 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的； > 线程上下文切换的是什么？ - 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样； - **当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据**； ## 进程生命周期 我们一般把进程大致分为 5 种状态，这一点和线程很像！ - **创建状态(new)**：进程正在被创建，尚未到就绪状态。 - **就绪状态(ready)**：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。 - **运行状态(running)**：进程正在处理器上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。 - **阻塞状态(waiting)**：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。 - **结束状态(terminated)**：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。 ![image-20230508161218693](assets/image-20230508161218693.png) ## 死锁 死锁（Deadlock）描述的是这样一种情况：多个进程/线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于进程/线程被无限期地阻塞，因此程序不可能正常终止。 产生死锁的四个必要条件 1. **互斥**：资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。 2. **占有等待**：一个进程至少应该占有一个资源，并等待另一资源，而该资源被其他进程所占有。 3. **非抢占**：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放。 4. **循环等待**：有一组等待进程 `{P0, P1,..., Pn}`， `P0` 等待的资源被 `P1` 占有，`P1` 等待的资源被 `P2` 占有，......，`Pn-1` 等待的资源被 `Pn` 占有，`Pn` 等待的资源被 `P0` 占有。 ## 如何预防死锁 破坏第一个条件 **互斥条件**：使得资源是可以同时访问的，这是种简单的方法，磁盘就可以用这种方法管理，但是我们要知道，有很多资源 **往往是不能同时访问的** ，所以这种做法在大多数的场合是行不通的。 破坏第三个条件 **非抢占**：也就是说可以采用 **剥夺式调度算法**，但剥夺式调度方法目前一般仅适用于 **主存资源** 和 **处理器资源** 的分配，并不适用于所有的资源，会导致 **资源利用率下降**。 所以一般比较实用的 **预防死锁的方法**，是通过考虑破坏第二个条件和第四个条件。 1. **静态分配策略**：一个进程必须在执行前就申请到它所需要的全部资源 2. **层次分配策略**：一个进程得到某一次的一个资源后，它只能再申请较高一层的资源 ## 零拷贝 **传统的拷贝** ![image-20230524103611405](assets/image-20230524103611405.png) **一共需要2次CPU拷贝，很消耗时间。** 零拷贝（Zero-Copy）是一种 `I/O` 操作优化技术，可以快速高效地将数据从文件系统移动到网络接口，而不需要将其从内核空间复制到用户空间。 技术的核心就要是减少CPU占用和上下文切换 它主要由以下4点技术结合实现： ### 1. DMA技术 DMA（Direct Memory Access）是一种硬件实现的技术，能够直接将数据从设备传输到内存中，而无需CPU参与其中。 ### 2. 缓冲区技术 在实现零拷贝时，需要使用多个缓冲区来存储数据。通过缓冲区技术可以实现不同层级的内存之间的数据传输。 ### 3. 文件映射技术 文件映射技术可以将文件或磁盘块映射到内存空间中，使得应用程序可以直接访问这些文件或磁盘块，从而实现零拷贝。 **mmap + write** ![image-20230524101601923](assets/image-20230524101601923.png) `mmap()` 系统调用函数会直接把内核缓冲区里的数据「**映射**」到用户空间，这样，操作系统内核与用户空间就不需要再进行任何的数据拷贝操作。 具体过程如下： - 应用进程调用了 `mmap()` 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区； - 应用进程再调用 `write()`，操作系统直接将内核缓冲区的数据拷贝到 socket 缓冲区中，这一切都发生在内核态，由 CPU 来搬运数据； - 最后，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程是由 DMA 搬运的。 但这还不是最理想的零拷贝，因为仍然需要通过 CPU 把内核缓冲区的数据拷贝到 socket 缓冲区里，而且仍然需要 4 次上下文切换，因为系统调用还是 2 次 ### 4. 网络协议技术 网络协议技术可以帮助实现在网络上进行零拷贝传输，例如在TCP/IP协议栈中使用sendfile系统调用。 **sendfile** ![image-20230524101812043](assets/image-20230524101812043.png) - 第一步，通过 DMA 将磁盘上的数据拷贝到内核缓冲区里； - 第二步，缓冲区描述符和数据长度传到 socket 缓冲区，这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中，这样就减少了一次数据拷贝； 如果系统支持SG-DMA ![img](assets/senfile-零拷贝.png) ## PageCache 有什么作用？ **零拷贝使用了 PageCache 技术**，**PageCache其实本质上就是一种磁盘高速缓存**，通过 DMA 把磁盘里的数据搬运到内存里，这样就可以用读内存替换读磁盘。 **PageCache 来缓存最近被访问的数据**，当空间不足时淘汰最久未被访问的缓存。所以，读磁盘数据的时候，优先在 PageCache 找，如果数据存在则可以直接返回；如果没有，则从磁盘中读取，然后缓存 PageCache 中。 还有一点，读取磁盘数据的时候，需要找到数据所在的位置，但是对于机械磁盘来说，就是通过磁头旋转到数据所在的扇区，再开始「顺序」读取数据，但是旋转磁头这个物理动作是非常耗时的，为了降低它的影响，**PageCache 使用了「预读功能」**。 比如，假设 read 方法每次只会读 `32 KB` 的字节，虽然 read 刚开始只会读 0 ～ 32 KB 的字节，但内核会把其后面的 32～64 KB 也读取到 PageCache，这样后面读取 32～64 KB 的成本就很低，如果在 32～64 KB 淘汰出 PageCache 前，进程读取到它了，收益就非常大。 所以，PageCache 的优点主要是两个： - 缓存最近被访问的数据； - 预读功能； 这两个做法，将大大提高读写磁盘的性能。 ## 大文件传输用什么方式实现？ **在传输大文件（GB 级别的文件）的时候，PageCache 会不起作用，那就白白浪费 DMA 多做的一次数据拷贝，造成性能的降低，即使使用了 PageCache 的零拷贝也会损失性能** **在高并发的场景下，针对大文件的传输的方式，应该使用「异步 I/O + 直接 I/O」来替代零拷贝技术**。 异步I/O： 它把读操作分为两部分： - 前半部分，内核向磁盘发起读请求，但是可以**不等待数据就位就可以返回**，于是进程此时可以处理其他任务； - 后半部分，当内核将磁盘中的数据拷贝到进程缓冲区后，进程将接收到内核的**通知**，再去处理数据； 直接 I/O 应用场景常见的两种： - 应用程序已经实现了磁盘数据的缓存，那么可以不需要 PageCache 再次缓存，减少额外的性能损耗。在 MySQL 数据库中，可以通过参数设置开启直接 I/O，默认是不开启； - 传输大文件的时候，由于大文件难以命中 PageCache 缓存，而且会占满 PageCache 导致「热点」文件无法充分利用缓存，从而增大了性能开销，因此，这时应该使用直接 I/O。 另外，由于直接 I/O 绕过了 PageCache，就无法享受内核的这两点的优化： - 内核的 I/O 调度算法会缓存尽可能多的 I/O 请求在 PageCache 中，最后「**合并**」成一个更大的 I/O 请求再发给磁盘，这样做是为了减少磁盘的寻址操作； - 内核也会「**预读**」后续的 I/O 请求放在 PageCache 中，一样是为了减少对磁盘的操作； ## 什么是一致性哈希？ ### 如何处理分配请求？ 直接使用Kafka的轮询分配策略，使用权重对其进行轮询。但是加权轮询算法是无法应对「分布式系统（数据分片的系统）」的，因为分布式系统中，每个节点存储的数据是不同的。 当我们想提高系统的容量，就会将数据水平切分到不同的节点来存储，也就是将数据分布到了不同的节点。比如**一个分布式 KV（key-valu） 缓存系统，某个 key 应该到哪个或者哪些节点上获得，应该是确定的**，不是说任意访问一个节点都可以得到缓存结果的。 ### 使用哈希算法有什么问题？ 主要有两个问题？ 1. 数据分布不均匀，高频词的点，该节点数据可能过大 2. 扩容时会发生再哈希，导致数据迁移问题 ### 一致性哈希 ![img](assets/30c2c70721c12f9c140358fbdc5f2282.png) - 首先，对 key 进行哈希计算，确定此 key 在环上的位置； - 然后，从这个位置沿着顺时针方向走，遇到的第一节点就是存储 key 的节点。 > 缺点： > > **一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题**。 ![img](assets/d528bae6fcec2357ba2eb8f324ad9fd5.png) ### 如何通过虚拟节点提高均衡度？ 想要解决上述问题，就需要采用虚拟节点 具体做法是，**不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。** 比如对每个节点分别设置 3 个虚拟节点： - 对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03 - 对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03 - 对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03 引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。 ![img](assets/dbb57b8d6071d011d05eeadd93269e13.png) ## 内核优化 * **文件描述符**，默认是1024，改到最大值65535 ## I/O多路复用 ### select/poll select 实现多路复用的方式是，将已连接的 Socket 都放到一个**文件描述符集合**，然后调用 select 函数将文件描述符集合**拷贝**到内核里，让内核来检查是否有网络事件产生，检查的方式很粗暴，就是通过**遍历**文件描述符集合的方式，当检查到有事件产生后，将此 Socket 标记为可读或可写， 接着再把整个文件描述符集合**拷贝**回用户态里，然后用户态还需要再通过**遍历**的方法找到可读或可写的 Socket，然后再对其处理。 所以，对于 select 这种方式，需要进行 **2 次「遍历」文件描述符集合**，一次是在内核态里，一个次是在用户态里 ，而且还会发生 **2 次「拷贝」文件描述符集合**，先从用户空间传入内核空间，由内核修改后，再传出到用户空间中。 select 使用固定长度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的个数是有限制的，在 Linux 系统中，由内核中的 FD_SETSIZE 限制， 默认最大值为 `1024`，只能监听 0~1023 的文件描述符。 poll 不再用 BitsMap 来存储所关注的文件描述符，取而代之用动态数组，以链表形式来组织，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。 但是 poll 和 select 并没有太大的本质区别，**都是使用「线性结构」存储进程关注的 Socket 集合，因此都需要遍历文件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，而且也需要在用户态与内核态之间拷贝文件描述符集合**，这种方式随着并发数上来，性能的损耗会呈指数级增长。 ### epoll epoll 通过两个方面，很好解决了 select/poll 的问题。 *第一点*，epoll 在内核里使用**红黑树来跟踪进程所有待检测的文件描述字**，把需要监控的 socket 通过 `epoll_ctl()` 函数加入内核中的红黑树里，红黑树是个高效的数据结构，增删改一般时间复杂度是 `O(logn)`。而 select/poll 内核里没有类似 epoll 红黑树这种保存所有待检测的 socket 的数据结构，所以 select/poll 每次操作时都传入整个 socket 集合给内核，而 epoll 因为在内核维护了红黑树，可以保存所有待检测的 socket ，所以只需要传入一个待检测的 socket，减少了内核和用户空间大量的数据拷贝和内存分配。 *第二点*， epoll 使用**事件驱动**的机制，内核里**维护了一个链表来记录就绪事件**，当某个 socket 有事件发生时，通过**回调函数**内核会将其加入到这个就绪事件列表中，当用户调用 `epoll_wait()` 函数时，只会返回有事件发生的文件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。 epoll 支持两种事件触发模式，分别是**边缘触发（\*edge-triggered，ET\*）\**和\**水平触发（\*level-triggered，LT\*）**。 这两个术语还挺抽象的，其实它们的区别还是很好理解的。 - 使用边缘触发模式时，当被监控的 Socket 描述符上有可读事件发生时，**服务器端只会从 epoll_wait 中苏醒一次**，即使进程没有调用 read 函数从内核读取数据，也依然只苏醒一次，因此我们程序要保证一次性将内核缓冲区的数据读取完； - 使用水平触发模式时，当被监控的 Socket 上有可读事件发生时，**服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束**，目的是告诉我们有数据需要读取； > **select/poll 只有水平触发模式，epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。** ## 进程调度算法 ### 先来先服务调度算法 最简单的一个调度算法，就是非抢占式的**先来先服务（\*First Come First Severd, FCFS\*）算法**了。 ![FCFS 调度算法](assets/24-先来先服务.jpg) ### 最短作业优先调度算法 **最短作业优先（\*Shortest Job First, SJF\*）调度算法**同样也是顾名思义，它会**优先选择运行时间最短的进程来运行**，这有助于提高系统的吞吐量。 ![SJF 调度算法](assets/25-最短作业优先算法.jpg) ### 高响应比优先调度算法 前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。 那么，**高响应比优先 （Highest Response Ratio Next, HRRN）调度算法**主要是权衡了短作业和长作业。 **每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行**，「响应比优先级」的计算公式： ![img](assets/26-响应比公式.jpg) 从上面的公式，可以发现： - 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行； - 如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会； ### 时间片轮转调度算法 最古老、最简单、最公平且使用最广的算法就是**时间片轮转（\*Round Robin, RR\*）调度算法**。 ![RR 调度算法](assets/27-时间片轮询.jpg) **每个进程被分配一个时间段，称为时间片（\*Quantum\*），即允许该进程在该时间段中运行。** - 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程； - 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换； 另外，时间片的长度就是一个很关键的点： - 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率； - 如果设得太长又可能引起对短作业进程的响应时间变长。将 通常时间片设为 `20ms~50ms` 通常是一个比较合理的折中值。 ### 最高优先级调度算法 前面的「时间片轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。 但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能**从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法**。 进程的优先级可以分为，静态优先级或动态优先级： - 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化； - 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是**随着时间的推移增加等待进程的优先级**。 该算法也有两种处理优先级高的方法，非抢占式和抢占式： - 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。 - 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。 但是依然有缺点，可能会导致低优先级的进程永远不会运行。 ### 多级反馈队列调度算法 **多级反馈队列（Multilevel Feedback Queue）调度算法**是「时间片轮转算法」和「最高优先级算法」的综合和发展。 顾名思义： - 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。 - 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列； ![多级反馈队列](assets/28-多级队列.jpg) 来看看，它是如何工作的： - 设置了多个队列，赋予每个队列不同的优先级，每个**队列优先级从高到低**，同时**优先级越高时间片越短**； - 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成； - 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行； 可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的**兼顾了长短作业，同时有较好的响应时间。** ## 磁盘调度算法 ### 先来先服务 先来先服务（*First-Come，First-Served，FCFS*），顾名思义，先到来的请求，先被服务。 那按照这个序列的话： 98，183，37，122，14，124，65，67 那么，磁盘的写入顺序是从左到右，如下图： ![先来先服务](assets/磁盘调度-先来先服务.png) 先来先服务算法总共移动了 `640` 个磁道的距离，这么一看这种算法，比较简单粗暴，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很差，因为寻道时间过长。 ### 最短寻道时间优先 最短寻道时间优先（*Shortest Seek First，SSF*）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求，还是以这个序列为例子： 98，183，37，122，14，124，65，67 那么，那么根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的顺序： 65，67，37，14，98，122，124，183 ![最短寻道时间优先](assets/磁盘调度-最短寻道时间优先.png) 磁头移动的总距离是 `236` 磁道，相比先来先服务性能提高了不少。 但这个算法可能存在某些请求的**饥饿**，因为本次例子我们是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于 183 磁道的，那么 183 磁道可能永远不会被响应，于是就产生了饥饿现象，这里**产生饥饿的原因是磁头在一小块区域来回移动**。 ### 扫描算法 最短寻道时间优先算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。 为了防止这个问题，可以规定：**磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（\*Scan\*）算法**。 这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。 还是以这个序列为例子，磁头的初始位置是 53： 98，183，37，122，14，124，65，67 那么，假设扫描调度算先朝磁道号减少的方向移动，具体请求则会是下列从左到右的顺序： 37，14，`0`，65，67，98，122，124，183 ![扫描算法](assets/磁盘调度-扫描算法.png) 磁头先响应左边的请求，直到到达最左端（ 0 磁道）后，才开始反向移动，响应右边的请求。 扫描调度算法性能较好，不会产生饥饿现象，但是存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异。 ### 循环扫描算法 扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。 循环扫描（*Circular Scan, CSCAN* ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且**返回中途不处理任何请求**，该算法的特点，就是**磁道只响应一个方向上的请求**。 还是以这个序列为例子，磁头的初始位置是 53： 98，183，37，122，14，124，65，67 那么，假设循环扫描调度算先朝磁道增加的方向移动，具体请求会是下列从左到右的顺序： 65，67，98，122，124，183，`199`，`0`，14，37 ![循环扫描算法](assets/磁盘调度-C-SCAN算法.png) 磁头先响应了右边的请求，直到碰到了最右端的磁道 199，就立即回到磁盘的开始处（磁道 0），但这个返回的途中是不响应任何请求的，直到到达最开始的磁道后，才继续顺序响应右边的请求。 循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。 ### LOOK 与 C-LOOK算法 我们前面说到的扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。 那这其实是可以优化的，优化的思路就是**磁头在移动到「最远的请求」位置，然后立即反向移动。** 那针对 SCAN 算法的优化则叫 LOOK 算法，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，**反向移动的途中会响应请求**。 ![LOOK 算法](assets/磁盘调度-LOOK算法.png) 而针 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，**反向移动的途中不会响应请求**。 ![C-LOOK 算法](assets/磁盘调度-C-LOOK算法.png)