调度算法

  • 进程调度

    • 总论
      • 当CPU空闲，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU
      • 什么时候会发生 CPU 调度
        • 当进程从运行状态转到等待状态
        • 当进程从运行状态转到就绪状态
        • 当进程从等待状态转到就绪状态
        • 当进程从运行状态转到终止状态
      • 其中发生在 1 和 4 两种情况下的调度称为「非抢占式调度」， 2 和 3 两种情况下发生的调度称为「抢占式调度」
        • 非抢占式：当进程正在运行时，会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把 CPU 让给其他进程
        • 抢占式：进程正在运行的时，可以被打断，使其把 CPU 让给其他进程
    • 先来先服务调度
      • 先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行
      • 对长作业有利，适用 CPU 繁忙型作业的系统，而不适用 I/O 繁忙型作业的系统
    • 最短作业优先调度
      • 会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量
      • 显然对长作业不利，很容易造成一种极端现象
    • 高响应比优先调度
      • 每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行
    • 时间片轮转调度
      • 每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行
    • 最高优先级调度
      • 对多用户计算机系统就有不同的看法，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级调度
      • 优先级可分为：
        • 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化
        • 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，就随着时间的推移增加等待进程的优先级
    • 多级反馈队列调度
      • 「时间片轮转算法」和「最高优先级算法」的综合和发展
      • 「多级」有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
      • 「反馈」如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

  • 内存页面置换

    • 缺页异常（缺页中断）

      • 当 CPU 访问的页面不在物理内存，便产生一个缺页中断，请求操作系统将所缺页调入到物理内存。与一般中断区别在于：
        • 缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号
        • 缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行
      • 页面置换算法：当出现缺页异常，需调入新页面但内存已满，选择被置换的物理页面，也就选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页

    • 最佳页面置换

      • 置换在「未来」最长时间不访问的页面，但无法实现

    • 先进先出置换

      • 选择在内存驻留时间很长的页面进行中置换，就是「先进先出置换」算法的思想

    • 最近最久未使用置换

      • 发生缺页时，选择最长时间没有被访问的页面进行置换，假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用

    • 时钟页面置换

      • 把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面

        缺页中断时，首先检查表针指向的页面：

        • 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
        • 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止

网络

  • I/O多路复用

    • 服务用户数量

      • TCP 连接是由四元组唯一确认的，这个四元组就是：本机IP, 本机端口, 对端IP, 对端端口
      • 服务器作为服务方，会在本地固定监听一个端口，等待客户端的连接。因此服务器的本地 IP 和端口是固定的，于是对于服务端 TCP 连接的四元组只有对端 IP 和端口是会变化的，最大 TCP 连接数 = 客户端 IP 数×客户端端口数
      • 对于 IPv4，客户端的 IP 数最多为 2 的 32 次方，客户端的端口数最多为 2 的 16 次方，也就是服务端单机最大 TCP 连接数约为 2 的 48 次方
        • 两方面限制：
          • 文件描述符，Socket 实际上是一个文件，也就会对应一个文件描述符。在 Linux 下，单个进程打开的文件描述符数是有限制的，没有经过修改的值一般都是 1024
          • 系统内存：每个 TCP 连接在内核中有对应的数据结构，意味着每个连接都是会占用一定内存的

    • 多进程模型

      • 使用多进程模型：就是为每个客户端分配一个进程来处理请求

      • 服务器的主进程负责监听客户的连接，一旦与客户端连接完成，accept() 函数就会返回一个「已连接 Socket」，这时就通过 fork() 函数创建一个子进程，实际上就把父进程所有相关的东西都复制一份，包括文件描述符、内存地址空间、程序计数器、执行的代码等

      • 这两进程刚复制完时，几乎一模一样。根据返回值区分是父进程还是子进程，如果返回值是 0，则是子进程；如果返回值是其他的整数，就是父进程。

        因为子进程会复制父进程的文件描述符，于是可以直接使用「已连接 Socket 」和客户端通信了

      • 当「子进程」退出时，实际上内核里还会保留该进程的一些信息，是会占用内存，如果不做好“回收”工作，就会变成僵尸进程，随着僵尸进程越多，会慢慢耗尽我们的系统资源

    • 多线程模型

      • 进程间上下文切换的“包袱”很重，搞个轻量级的模型来应对多用户的请求 —— 多线程模型
      • 线程是运行在进程中的一个“逻辑流”，单进程中可以运行多个线程，同进程里的线程可以共享进程的部分资源，比如文件描述符列表、进程空间、代码、全局数据、堆、共享库等，这些共享些资源在上下文切换时不需要切换，而只需要切换线程的私有数据、寄存器等不共享的数据，因此同一个进程下的线程上下文切换的开销要比进程小得多
      • 可以使用线程池的方式来避免线程的频繁创建和销毁

    • I/O多路复用

      • 一个进程任一时刻只能处理一个请求，但是处理每个请求的事件时，耗时控制在 1 毫秒以内，这样 1 秒内就可以处理上千个请求，把时间拉长来看，多个请求复用了一个进程，这就是多路复用
      • select/poll/epoll 内核提供给用户态的多路复用系统调用，进程可以通过一个系统调用函数从内核中获取多个事件

    • select/poll

      • select 实现多路复用的方式：将已连接的 Socket 都放到一个文件描述符集合，调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生，通过遍历文件描述符集合的方式，当检查到有事件产生后，将此 Socket 标记为可读或可写， 再把整个文件描述符集合拷贝回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理
        • 进行 2 次「遍历」文件描述符集合，一次在内核态，一个次在用户态
        • 发生 2 次「拷贝」文件描述符集合，先从用户空间传入内核空间，由内核修改后，再传出到用户空间中
        • select 使用固定长度的 BitsMap，在 Linux 系统中，由内核中的 FD_SETSIZE 限制， 默认最大值为 1024
      • poll 不再用 BitsMap 来存储所关注的文件描述符，以链表形式来组织，突破了 select 的文件描述符个数限制
      • poll 和 select 并没有太大的本质区别，都是「线性结构」存储进程关注的 Socket 集合，都需要遍历文件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，也需要在用户态与内核态之间拷贝文件描述符集合

    • epoll

      • epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字，把需要监控的 socket 通过 epoll_ctl() 函数加入内核中的红黑树里，减少了内核和用户空间大量的数据拷贝和内存分配
      • epoll 使用事件驱动的机制，内核里维护了一个链表来记录就绪事件
      • 当某个 socket 有事件发生时，通过回调函数内核会将其加入到就绪事件列表中，当用户调用 epoll_wait() 函数时，只会返回有事件发生的文件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率

    • 边缘触发和水平触发

      • 边缘触发模式：当被监控的 Socket 描述符上有可读事件发生时，服务器端只会从 epoll_wait 中苏醒一次，即使进程没有调用 read 函数从内核读取数据，也依然只苏醒一次，因此我们程序要确保一次性将内核缓冲区的数据读取完；
      • 水平触发模式：当被监控的 Socket 有可读事件发生时，服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束，目的是告诉我们有数据需要读取

  • 一致性哈希

    • 解决负载均衡问题：

      1. 将外界的请求「轮流」的转发给内部的集群。比如集群有 3 个节点，外界请求有 3 个，那么每个节点都会处理 1 个请求，达到了分配请求的目的
      2. 加权轮询算法是建立在每个节点存储的数据都是相同的前提，每次读数据的请求，访问任意一个节点都能得到结果
        • 加权轮询算法是无法应对「分布式系统（数据分片的系统）」的，因为分布式系统中，每个节点存储的数据是不同的
      3. 想提高系统容量，会将数据水平切分到不同的节点来存储，就是将数据分布到不同的节点。比如一个分布式 KV（key-valu） 缓存系统，某个 key 应该到哪个或者哪些节点上获得，应该是确定的

    • 使用哈希算法弊端

      • 哈希算法：对同一个关键字进行哈希计算，每次计算都是相同的值，就可以将某个 key 确定到一个节点了，可以满足分布式系统的负载均衡需求
      • 有一个很致命的问题，如果节点数量发生了变化，也就是在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据

    • 一致性哈希

      • 一致哈希算法也用了取模运算，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值

        1. 计算各服务器节点的哈希值，并映射到哈希环上；

        2. 将服务发来的数据请求使用哈希算法算出对应的哈希值；

        3. 将计算的哈希值映射到哈希环上，同时沿圆环顺时针方向查找，遇到的第一台服务器就是所对应的处理请求服务器。

        4. 当增加或者删除一台服务器时，受影响的数据仅仅是新添加或删除的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响

      • 一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上

      • 不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系

      • 代码实现图解一致性哈希算法，看这一篇就够了！ -阿里云开发者社区

  • I/O模型

    • 详细可看https://wiyi.org/linux-io-model.html
    • IO
      • 所谓I/O，就是计算机内存与外部设备之间拷贝数据的过程
      • 用户线程发起 I/O 操作后，网络数据读取操作会经历两个步骤：
        • 用户线程等待内核将数据从网卡拷贝到内核空间。
        • 内核将数据从内核空间拷贝到用户空间
    • 同步阻塞IO
      • 用户线程发起 read 调用后就阻塞了，让出 CPU。内核等待网卡数据到来，把数据从网卡拷贝到内核空间，接着把数据拷贝到用户空间，再把用户线程叫醒
    • 同步非阻塞IO
      • 用户线程不断发起 read 调用，数据没到内核空间时，每次都返回失败，直到数据到了内核空间，这一次 read 调用后，在等待数据从内核空间拷贝到用户空间这段时间里，线程还是阻塞的，等数据到了用户空间再把线程叫醒
    • IO多路复用
      • 用户线程的读取操作分成两步了，线程先发起 select 调用，目的是问内核数据准备好了吗？等内核把数据准备好了，用户线程再发起 read 调用。在等待数据从内核空间拷贝到用户空间这段时间里，线程还是阻塞的
    • 信号驱动IO
      • 首先开启 Socket 的信号驱动 I/O 功能，并安装一个信号处理函数，进程继续运行并不阻塞。当内核数据准备好时，进程会收到一个 SIGIO 信号，可以在信号处理函数中调用 I/O 操作函数处理数据。信号驱动式 I/O 模型的优点是我们在数据报到达期间进程不会被阻塞，我们只要等待信号处理函数的通知即可
    • 异步IO
      • 用户线程发起 read 调用的同时注册一个回调函数，read 立即返回，等内核将数据准备好后，再调用指定的回调函数完成处理。在这个过程中，用户线程一直没有阻塞