一文带你吃透操作系统

痛定思痛。 2024-03-16 17:42 11阅读 0赞

#### 1. 进程、线程管理 ####

1.  进程和线程基础知识
    
    进程：进程是系统进行资源分配和调度的一个独立单位，是系统中的并发执行的单位。
    
    线程：线程是进程的一个实体，也是 CPU 调度和分派的基本单位，它是比进程更小的能独立运行的基本单位，有时又被称为轻权进程或轻量级进程。
    
    1.  **进程**
        
        运行中的程序，就被称为「进程」（Process）。
        
        **在一个进程的活动期间至少具备三种基本状态，即运行状态、就绪状态、阻塞状态。**
        
         *  运行状态（*Running*）：该时刻进程占用 CPU；
         *  就绪状态（*Ready*）：可运行，由于其他进程处于运行状态而暂时停止运行；
         *  阻塞状态（*Blocked*）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；
        
        当然，进程还有另外两个基本状态：
        
         *  创建状态（*new*）：进程正在被创建时的状态；
         *  结束状态（*Exit*）：进程正在从系统中消失时的状态；
        
        挂起状态可以分为两种：
        
         *  阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
         *  就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；
        
        **PCB 进程控制块 是进程存在的唯一标识**
        
        > PCB 具体包含什么信息呢？
        
        **进程描述信息：**
        
         *  进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
         *  用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；
        
        **进程控制和管理信息：**
        
         *  进程当前状态，如 new、ready、running、waiting 或 blocked 等；
         *  进程优先级：进程抢占 CPU 时的优先级；
        
        **资源分配清单：**
        
         *  有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。
        
        **CPU 相关信息：**
        
         *  CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。
    2.  **线程**
        
        **线程是进程当中的一条执行流程。**
        
        同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。
        
        **线程的实现**
        
        主要有三种线程的实现方式：
        
         *  **用户线程（\*User Thread\*）**：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
         *  **内核线程（\*Kernel Thread\*）**：在内核中实现的线程，是由内核管理的线程；
         *  **轻量级进程（\*LightWeight Process\*）**：在内核中来支持用户线程；
        
        第一种关系是**多对一**的关系，也就是多个用户线程对应同一个内核线程
        
        第二种是**一对一**的关系，也就是一个用户线程对应一个内核线程
        
        第三种是**多对多**的关系，也就是多个用户线程对应到多个内核线程
        
        用户线程的整个线程管理和调度，操作系统是不直接参与的，而是由用户级线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等。
        
        **线程的优点：**
        
         *  一个进程中可以同时存在多个线程；
         *  各个线程之间可以并发执行；
         *  各个线程之间可以共享地址空间和文件等资源；
        
        **线程的缺点：**
        
         *  当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java语言中的线程奔溃不会造成进程崩溃
        
        内核线程是由操作系统管理的，线程对应的 TCB 自然是放在操作系统里的，这样线程的创建、终止和管理都是由操作系统负责。
2.  进程/线程上下文切换
    
    1.  进程
        
        **一个进程切换到另一个进程运行，称为进程的上下文切换**。
        
        > 进程的上下文切换到底是切换什么呢？
        
        进程是由内核管理和调度的，所以进程的切换只能发生在内核态。
        
        所以，**进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。**
        
        通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行
        
        > 发生进程上下文切换有哪些场景？
        
         *  为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；
         *  进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
         *  当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
         *  当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
         *  发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；
    2.  线程
        
        1.  > 线程上下文切换的是什么？
            
            这还得看线程是不是属于同一个进程：
            
            1.  当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
            2.  **当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据**；
            
            所以，线程的上下文切换相比进程，开销要小很多。
3.  进程/线程间通信方式
    
    进程间通信（IPC，InterProcess Communication）是指在不同进程之间传播或交换信息。IPC 的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams 等。其中 Socket 和 Streams 支持不同主机上的两个进程 IPC。
    
    **管道**
    
    1.  它是半双工的，具有固定的读端和写端；
    2.  它只能用于父子进程或者兄弟进程之间的进程的通信；
    3.  它可以看成是一种特殊的文件，对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。
    
    **命名管道**
    
    1.  FIFO 可以在无关的进程之间交换数据，与无名管道不同；
    2.  FIFO 有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
    
    **消息队列**
    
    1.  消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符 ID 来标识；
    2.  消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；
    3.  消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除；
    4.  消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。
    
    **信号量**
    
    1.  信号量（semaphore）是一个计数器。用于实现进程间的互斥与同步，而不是用于存储进程间通信数据；
    2.  信号量用于进程间同步，若要在进程间传递数据需要结合共享内存；
    3.  信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作；
    4.  每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数；
    5.  支持信号量组。
    
    **共享内存**
    
    1.  共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区；
    2.  共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
    
    **Socket通信**
    
    前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。
    
    以上，就是进程间通信的主要机制了。你可能会问了，那线程通信间的方式呢？
    
    同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步：
    
     *  互斥的方式，可保证任意时刻只有一个线程访问共享资源；
     *  同步的方式，可保证线程 A 应在线程 B 之前执行；
4.  线程、进程崩溃发生什么
    
    一般来说如果线程是因为非法访问内存引起的崩溃，那么进程肯定会崩溃，为什么系统要让进程崩溃呢，这主要是因为在进程中，**各个线程的地址空间是共享的**，既然是共享，那么某个线程对地址的非法访问就会导致内存的不确定性，进而可能会影响到其他线程，这种操作是危险的，操作系统会认为这很可能导致一系列严重的后果，于是干脆让整个进程崩溃
    
    **崩溃机制**
    
    1.  CPU 执行正常的进程指令
    2.  调用 kill 系统调用向进程发送信号
    3.  进程收到操作系统发的信号，CPU 暂停当前程序运行，并将控制权转交给操作系统
    4.  调用 kill 系统调用向进程发送信号（假设为 11，即 SIGSEGV，一般非法访问内存报的都是这个错误）
    5.  操作系统根据情况执行相应的信号处理程序（函数），一般执行完信号处理程序逻辑后会让进程退出
    
    注意上面的第五步，如果进程没有注册自己的信号处理函数，那么操作系统会执行默认的信号处理程序（一般最后会让进程退出），但如果注册了，则会执行自己的信号处理函数，这样的话就给了进程一个垂死挣扎的机会，它收到 kill 信号后，可以调用 exit() 来退出，**但也可以使用 sigsetjmp，siglongjmp 这两个函数来恢复进程的执行**
5.  守护进程、僵尸进程和孤儿进程
    
    **守护进程**
    
    指在后台运行的，没有控制终端与之相连的进程。它独立于控制终端，周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的，如web服务器进程http等
    
    创建守护进程要点：
    
    （1）让程序在后台执行。方法是调用fork（）产生一个子进程，然后使父进程退出。
    
    （2）调用setsid（）创建一个新对话期。控制终端、登录会话和进程组通常是从父进程继承下来的，守护进程要摆脱它们，不受它们的影响，方法是调用setsid（）使进程成为一个会话组长。setsid（）调用成功后，进程成为新的会话组长和进程组长，并与原来的登录会话、进程组和控制终端脱离。
    
    （3）禁止进程重新打开控制终端。经过以上步骤，进程已经成为一个无终端的会话组长，但是它可以重新申请打开一个终端。为了避免这种情况发生，可以通过使进程不再是会话组长来实现。再一次通过fork（）创建新的子进程，使调用fork的进程退出。
    
    （4）关闭不再需要的文件描述符。子进程从父进程继承打开的文件描述符。如不关闭，将会浪费系统资源，造成进程所在的文件系统无法卸下以及引起无法预料的错误。首先获得最高文件描述符值，然后用一个循环程序，关闭0到最高文件描述符值的所有文件描述符。
    
    （5）将当前目录更改为根目录。
    
    （6）子进程从父进程继承的文件创建屏蔽字可能会拒绝某些许可权。为防止这一点，使用unmask（0）将屏蔽字清零。
    
    （7）处理SIGCHLD信号。对于服务器进程，在请求到来时往往生成子进程处理请求。如果子进程等待父进程捕获状态，则子进程将成为僵尸进程（zombie），从而占用系统资源。如果父进程等待子进程结束，将增加父进程的负担，影响服务器进程的并发性能。在Linux下可以简单地将SIGCHLD信号的操作设为SIG\_IGN。这样，子进程结束时不会产生僵尸进程。
    
    **孤儿进程**
    
    如果父进程先退出，子进程还没退出，那么子进程的父进程将变为init进程。（注：任何一个进程都必须有父进程）。
    
    一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
    
    **僵尸进程**
    
    如果子进程先退出，父进程还没退出，那么子进程必须等到父进程捕获到了子进程的退出状态才真正结束，否则这个时候子进程就成为僵尸进程。
    
    设置**僵尸进程的目**的是维护子进程的信息，以便父进程在以后某个时候获取。这些信息至少包括进程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进程去处理，省去了大量僵尸进程占用系统资源。
6.  进程和线程的比较
    
    **线程是调度的基本单位，而进程则是资源拥有的基本单位**。
    
    线程与进程的比较如下：
    
     *  进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位；
     *  进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
     *  线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
     *  线程能减少并发执行的时间和空间开销；
    
    对于，线程相比进程能减少开销，体现在：
    
     *  线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
     *  线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
     *  同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
     *  由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；
    
    所以，不管是时间效率，还是空间效率线程比进程都要高。
    
    1、线程启动速度快，轻量级
    
    2、线程的系统开销小
    
    3、线程使用有一定难度，需要处理数据一致性问题
    
    4、同一线程共享的有堆、全局变量、静态变量、指针，引用、文件等，而独自占有栈
    
    1.  进程是资源分配的最小单位，而线程是 CPU 调度的最小单位；
    2.  创建进程或撤销进程，系统都要为之分配或回收资源，操作系统开销远大于创建或撤销线程时的开销；
    3.  不同进程地址空间相互独立，同一进程内的线程共享同一地址空间。一个进程的线程在另一个进程内是不可见的；
    4.  进程间不会相互影响，而一个线程挂掉将可能导致整个进程挂掉；

#### 2. 内存管理 ####

1.  物理地址、逻辑地址、虚拟内存的概念
    
    1.  物理地址：它是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取，是内存单元真正的地址。
    2.  逻辑地址：是指计算机用户看到的地址。例如：当创建一个长度为 100 的整型数组时，操作系统返回一个逻辑上的连续空间：指针指向数组第一个元素的内存地址。由于整型元素的大小为 4 个字节，故第二个元素的地址时起始地址加 4，以此类推。事实上，逻辑地址并不一定是元素存储的真实地址，即数组元素的物理地址（在内存条中所处的位置），并非是连续的，只是操作系统通过地址映射，将逻辑地址映射成连续的，这样更符合人们的直观思维。
    3.  虚拟内存：是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。
2.  虚拟内存有什么好处
    
     *  第一，虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
     *  第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
     *  第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。
3.  内存管理
    
    内存管理的概念就是操作系统对内存的划分和动态分配。
    
    **内存管理功能：**
    
    内存空间的分配与回收：由操作系统完成主存储器空间的分配和管理，是程序员摆脱存储分配的麻烦，提高编程效率。  
    地址转换：将逻辑地址转换成相应的物理地址。  
    内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充主存。  
    存储保护：保证各道作业在各自的存储空间内运行，互不干扰。  
    创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下**几个步骤：**
    
    编译：由编译程序将用户源代码编译成若干目标模块（把高级语言翻译成机器语言）  
    链接：由链接程序将编译后形成的一组目标模块及所需的库函数连接在一起，形成一个完整的装入模块（由目标模块生成装入模块，链接后形成完整的逻辑地址）  
    装入：由装入程序将装入模块装入内存运行，装入后形成物理地址  
    **程序的链接有以下三种方式：**
    
    静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。  
    装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。  
    运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。  
    **内存的装入模块**在装入内存时，有以下三种方式：
    
    重定位：根据内存的当前情况，将装入模块装入内存的适当位置，装入时对目标程序中的指令和数据的修改过程称为重定位。
    
    静态重定位：地址的变换通常是在装入时一次完成的。一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。此外，作业一旦装入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。  
    动态重定位：需要重定位寄存器的支持。可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存。  
    内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可采取如下两种方法：
    
    在CPU中设置一对上、下限寄存器，存放用户作业在主存中的上限和下限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。  
    采用重定位寄存器（或基址寄存器）和界地址寄存器（又称限长存储器）来实现这种保护。重定位寄存器包含最小的物理地址值，界地址寄存器含逻辑地址的最大值。每个逻辑地址值必须小于界地址寄存器；内存管理机构动态得将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。
4.  常见的内存分配方式
    
    （1） 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。
    
    （2） 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
    
    （3） 从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。
    
    **常见内存分配内存错误**
    
    （1）内存分配未成功，却使用了它。
    
    （2）内存分配虽然成功，但是尚未初始化就引用它。
    
    （3）内存分配成功并且已经初始化，但操作越过了内存的边界。
    
    （4）忘记了释放内存，造成内存泄露。
    
    （5）释放了内存却继续使用它。常见于以下有三种情况：
    
     *  程序中的对象调用关系过于复杂，实在难以搞清楚某个对象究竟是否已经释放了内存，此时应该重新设计数据结构，从根本上解决对象管理的混乱局面。
     *  函数的return语句写错了，注意不要返回指向“栈内存”的“指针”或者“引用”，因为该内存在函数体结束时被自动销毁。
     *  使用free或delete释放了内存后，没有将指针设置为NULL。导致产生“野指针”。
5.  malloc如何分配内存
    
    从操作系统层面上看，malloc是通过两个系统调用来实现的： brk和mmap
    
     *  brk是将进程数据段(.data)的最高地址指针向高处移动，这一步可以扩大进程在运行时的堆大小
     *  mmap是在进程的虚拟地址空间中寻找一块空闲的虚拟内存，这一步可以获得一块可以操作的堆内存。
    
    通常，分配的内存小于128k时，使用brk调用来获得虚拟内存，大于128k时就使用mmap来获得虚拟内存。
    
    进程先通过这两个系统调用获取或者扩大进程的虚拟内存，获得相应的虚拟地址，在访问这些虚拟地址的时候，通过缺页中断，让内核分配相应的物理内存，这样内存分配才算完成。
6.  如何避免预读失效和缓存污染
    
    **预读失效**
    
    这些被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是**预读失效**。
    
    传统的 LRU 算法法无法避免下面这两个问题：
    
     *  预读失效导致缓存命中率下降；
     *  缓存污染导致缓存命中率下降；
    
    为了避免「预读失效」造成的影响，Linux 和 MySQL 对传统的 LRU 链表做了改进：
    
     *  Linux 操作系统实现两个了 LRU 链表：**活跃 LRU 链表（active list）和非活跃 LRU 链表（inactive list）**。
     *  MySQL Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：**young 区域 和 old 区域**。
    
    **缓存污染**
    
    如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了。
    
    为了避免「缓存污染」造成的影响，Linux 操作系统和 MySQL Innodb 存储引擎分别提高了升级为热点数据的门槛：
    
     *  Linux 操作系统：在内存页被访问**第二次**的时候，才将页从 inactive list 升级到 active list 里。
     *  MySQL Innodb：在内存页被访问
        
        第二次
        
        的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行
        
        停留在 old 区域的时间判断：
        
         *  如果第二次的访问时间与第一次访问的时间**在 1 秒内**（默认值），那么该页就**不会**被从 old 区域升级到 young 区域；
         *  如果第二次的访问时间与第一次访问的时间**超过 1 秒**，那么该页就**会**从 old 区域升级到 young 区域；
    
    通过提高了进入 active list （或者 young 区域）的门槛后，就很好了避免缓存污染带来的影响。
7.  物理内存管理
    
    操作系统物理内存管理主要包括程序装入、交换技术、连续分配管理方式和非连续分配管理方式（分页、分段、段分页）。
    
    **连续分配管理方式**
    
    **连续内存分配**  
    **内存碎片**  
    当给程序分配空间时，可能会出现一些无法被利用的空闲碎片空间。  
    1.外部碎片：分配单元之间无法被利用的内存碎片  
    2.内部碎片：分配给任务内存大小大于任务所需内存大小时，多出来的内存碎片。
    
    **分区的动态分配**  
    连续内存分配情况：将应用程序从硬盘加载到内存中，给内存分配一块内存。应用程序运行访问数据，数据的连续内存空间。
    
    **内存分配算法：**  
    具体问题具体分析适配算法。
    
    1.  首次适配：  
        定义：使用第一块内存大小大于需求大小的可用空闲块  
        实现方法：需要有一个按地址排序的空闲块列表。寻找第一个满足内存需求的空闲块。对于回收，要考虑空闲块与相邻空闲块合并问题。  
        优点：简单，易于产生更大的空闲块，想着地址空间结尾分配  
        缺点：产生外部碎片，具有不确定性
    2.  最优适配：  
        定义：寻找整个空闲块中，最满足分配请求的空闲块，内存差值最小。  
        实现方法：需要有一个按尺寸排序的空闲块列表，寻找最满足分配的内存块。对于回收，要考虑空闲块与相邻空闲块合并问题。  
        优点：避免分割大空闲块，最小化外部碎片的产生，简单  
        缺点：外部碎片很细，有很多微小碎片，不利于后续分配管理。
    3.  最差适配：  
        定义：找到差距最大的内存空闲块。  
        实现：需要有一个按尺寸排序的空闲块列表，寻找差距最大的内存块。对于回收，要考虑空闲块与相邻空闲块合并问题。  
        优点：避免产生微小外部碎片，分配效率高，适用于分配中大快  
        缺点：对于大块请求带来一定影响
    
    **减少内存碎片方法**
    
    1.  紧致：压缩式碎片整理  
        调整运行程序的位置。  
        1.重定位的时机。不能在程序运行时进行，可以在程序等待时拷贝。  
        2.内存拷贝开销很大。
    2.  swaping：交换式碎片整理  
        把硬盘作为一个备份。把等待的程序包括数据（主存）挪到硬盘上。当硬盘上程序需要执行时再拷贝到主存上。  
        1.交换那个程序，减小开销  
        2.交换的时机
    
    **非连续内存分配**
    
    **连续内存分配和非连续内存分配**  
    连续内存分配缺点：1.分配给一个程序的物理内存是连续的，内存利用率较低，由外碎片内碎片的问题。  
    非连续内存分配优点：1.程序物理地址是非连续的 2.更好的内存利用和管理 3.允许共享代码与数据 4.支持动态加载和动态链接  
    非连续内存分配缺点：建立虚拟地址到物理地址的映射，软件开销太大，可以用硬件支持  
    \-》硬件两种管理方案：分段和分页  
    **分段**  
    **分段地址空间**  
    对于一段程序内存可以分为：程序（主程序+子程序+共享库）+变量（栈、堆、共享数据段）  
    分段：更好的分离与共享，将逻辑地址空间分散到多个物理地址空间  
    逻辑地址是连续的，将具有不同功能的映射到物理空间中，这些段大小不一，位置不一
    
    **硬件实现分段寻址机制**  
    一维逻辑地址有不同段组成，首先将逻辑地址分为两段：段寻址（段号）+段偏移寻址（addr）  
    通过段号在段表找到逻辑内存的段起始地址，看段起始地址是否满足段大小限制，不满足返回内存异常，满足将逻辑地址加偏移量是物理地址。
    
    段表：  
    1.存储逻辑地址段段号到物理地址段号之间的映射关系  
    2.存储段大小，起始地址  
    段表的建立：操作系统在寻址前建立。
    
    **分页**  
    **分页地址空间**  
    需要页号和页地址偏移。相比分段，分页页帧大小固定不变。  
    可以划分物理内存至固定大小的帧，将逻辑地址的页也划分至相同内存大小。大小是2的幂。  
    **建立方案**  
    页帧（Frame）：物理内存被分割为大小相等的帧  
    一个内存物理地址是一个二元组（f,o）  
    物理地址 = 2^S\*f+o  
    f是帧号（F位，2F个帧），o是帧内偏移（S位，每帧2S字节）,
    
    页（Page）：逻辑地址空间分割为大小相等的页  
    页内偏移大小 = 帧内偏移大小（页帧大小和页大小一致）  
    页号大小和帧号大小可能不一致
    
    一个逻辑地址是一个二元组（p,o）  
    逻辑地址 = 2^S\*p+o  
    p:页号（P位，2P个页），o：页内偏移（S位，每页2S个字节）
    
    **页寻址机制**  
    CPU寻址（逻辑地址），逻辑地址包含两部分（p，o），首先把p（页号）作为索引，再加上页表基址查页表（pagetable）中对应帧号（物理地址中f），知道帧号加上页内偏移就是物理地址（f，o）。
    
    页表：以页号为索引的对应的帧号（物理地址），为此需要知道页表的基址位置（页号从哪个地址开始查）。  
    页表的建立：操作系统初始化时，enable分页机制前就需要建立好
    
    分页与分段：  
    分页：相比分段，分页页内存固定，导致页内偏移大小范围是固定的。不需要想分段一样考虑分页大小不一致的问题。  
    逻辑地址和物理地址空间  
    1.总逻辑页大小和总物理帧大小不一致，一般逻辑地址空间大于物理地址空间。  
    2.逻辑地址空间连续，物理地址空间不连续。减少内外碎片。  
    **页表**  
    **页表结构**  
    页表是个数组，索引是页号，对应的数组项内容里有帧号。
    
    **分页机制性能问题**  
    1.时间开销：访问一个内存单元需要两次内存访问
    
    页表不能放在CPU里，只能放在内存里，CPU先做内存寻址找页表基址，再进行页表访问，进行两次内存访问，访问速度很慢
    
    2空间代价：页表占用空间
    
    1.64位计算机，每页1KB，页表大小？2^54个数的页表，很大  
    2.多个程序有多个页表
    
    **解决方法**  
    时间上：缓存 ——快表，TLB，Translation Look-aside Buffer  
    TLB：
    
    位于CPU中的一块缓存区域，存放常用的页号-帧号对，采用关联内存的方式实现，具有快速访问功能。  
    \-CPU寻址时会先通过页号在TLB查找，看是否存在页号的Key，对应得到帧号，进而得到物理地址（减少对物理地址的访问）。TLB未命中，把该项更新到TLB中（x86CPU这个过程是硬件完成，对于mps是操作系统完成）。  
    编写程序时，把访问的地址写在一个页号里。  
    空间上：间接访问（多级页表机制），以时间换空间  
    **二级页表：**
    
    对于逻辑地址（p1,p2,o）  
    CPU寻址时先通过p1查找一级页表，一级页表中存放的是二级页表的p2的起始地址，再在二级页表对应起始地址查找偏移p2，对应存放的就是帧号。提高时间开销，但一级页表中不存在页表项就不需要占用二级页表项的内存，节省空间。  
    **多级页表**
    
    页号分为K个部分，建立页表“树”
8.  快表
    
    快表，又称联想寄存器(TLB) ，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。
    
    <table> 
     <thead> 
      <tr> 
       <th>地址变换过程</th> 
       <th>访问一个逻辑地址的访存次数</th> 
       <th></th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>基本地址变换机构</td> 
       <td>①算页号、页内偏移量 ②检查页号合法性 ③查页表，找到页面存放的内存块号 ④根据内存块号与页内偏移量得到物理地址 ⑤访问目标内存单元</td> 
       <td>两次访存</td> 
      </tr> 
      <tr> 
       <td>具有快表的地址变换机构</td> 
       <td>①算页号、页内偏移量 ②检查页号合法性 ③查快表。若命中，即可知道页面存放的内存块号，可直接进行⑤;若未命中则进行④ ④查页表，找到页面存放的内存块号，并且将页表项复制到快表中 ⑤根据内存块号与页内偏移量得到物理地址 ⑥访问目标内存单元</td> 
       <td>快表命中，只需一次访存 快表未命中，需要两次访存</td> 
      </tr> 
     </tbody> 
    </table>
9.  内存交换技术
    
    **交换(对换)技术的设计思想**：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)
    
    换入：把准备好竞争CPU运行的程序从辅存移到内存。 换出：把处于等待状态（或CPU调度原则下被剥夺运行权力）的程序从内存移到辅存，把内存空间腾出来。
    
    **交换时机：**内存交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。
    
    **关键点**
    
    1.  交换需要备份存储，通常是快速磁盘，它必须足够大，并且提供对这些内存映像的直接访问。
    2.  为了有效使用CPU，需要每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间，转移时间与所交换的空间内存成正比。
    3.  如果换出进程，比如确保该进程的内存空间成正比。
    4.  交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用就可能很快。
    5.  交换通常在有许多进程运行且内存空间吃紧时开始启动，而系统负荷降低就暂停。
    6.  普通交换使用不多，但交换的策略的某些变种在许多系统中（如UNIX系统）仍然发挥作用。
10. 分页与分段的区别
    
    1.  段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的；
    2.  段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定；
    3.  段向用户提供二维地址空间；页向用户提供的是一维地址空间；
    4.  段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

#### 3. 进程调度算法 ####

1.  进程调度算法详细介绍
    
    选择一个进程运行这一功能是在操作系统中完成的，通常称为**调度程序**（*scheduler*）。
    
    **调度时机**
    
    在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。
    
    比如，以下状态的变化都会触发操作系统的调度：
    
     *  *从就绪态 -> 运行态*：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
     *  *从运行态 -> 阻塞态*：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行；
     *  *从运行态 -> 结束态*：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；
    
    因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给 CPU 运行，或者是否让当前进程从 CPU 上退出来而换另一个进程运行。
    
    另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：
    
     *  **非抢占式调度算法**挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
     *  **抢占式调度算法**挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生**时钟中断**，以便把 CPU 控制返回给调度程序进行调度，也就是常说的**时间片机制**。
    
    **调度原则**
    
     *  **CPU 利用率**：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
     *  **系统吞吐量**：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
     *  **周转时间**：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
     *  **等待时间**：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
     *  **响应时间**：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。
    
    **调度算法**
    
    调度算法是指：根据系统的资源分配策略所规定的资源分配算法。常用的调度算法有：先来先服务调度算法、时间片轮转调度法、短作业优先调度算法、最短剩余时间优先、高响应比优先调度算法、优先级调度算法等等。
    
     *  **先来先服务调度算法**
    
    先来先服务调度算法是一种最简单的调度算法，也称为先进先出或严格排队方案。当每个进程就绪后，它加入就绪队列。当前正运行的进程停止执行，选择在就绪队列中存在时间最长的进程运行。该算法既可以用于作业调度，也可以用于进程调度。先来先服务比较适合于常作业（进程），而不利于段作业（进程）。
    
     *  **时间片轮转调度算法**
    
    时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片。
    
     *  **短作业优先调度算法**
    
    短作业优先调度算法是指对短作业优先调度的算法，从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短作业优先调度算法是一个非抢占策略，他的原则是下一次选择预计处理时间最短的进程，因此短进程将会越过长作业，跳至队列头。
    
     *  **最短剩余时间优先调度算法**
    
    最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下，进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此只要新进程就绪，调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样，调度程序正在执行选择函数是必须有关于处理时间的估计，并且存在长进程饥饿的危险。
    
     *  **高响应比优先调度算法**
    
    高响应比优先调度算法主要用于作业调度，该算法是对 先来先服务调度算法和短作业优先调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
    
     *  **优先级调度算法**
    
    优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

#### 4. 磁盘调度算法 ####

1.  磁盘调度算法详细介绍
    
    常见的磁盘调度算法有：
    
     *  先来先服务算法
     *  最短寻道时间优先算法
     *  扫描算法
     *  循环扫描算法
     *  LOOK 与 C-LOOK 算法
    
    **先来先服务**
    
    先来先服务（*First-Come，First-Served，FCFS*），顾名思义，先到来的请求，先被服务。
    
    **最短寻道时间优先**
    
    最短寻道时间优先（*Shortest Seek First，SSF*）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求
    
    **扫描算法**
    
    最短寻道时间优先算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。
    
    为了防止这个问题，可以规定：**磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（\*Scan\*）算法**。
    
    这种算法也叫做**电梯算法**，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。
    
    **循环扫描算法**
    
    扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。
    
    循环扫描（*Circular Scan, CSCAN* ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
    
    **LOOK 与 C-LOOK算法**
    
    扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。
    
    那这其实是可以优化的，优化的思路就是**磁头在移动到「最远的请求」位置，然后立即反向移动。**
    
    针对 SCAN 算法的优化叫 LOOK 算法，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，**反向移动的途中会响应请求**。
    
    针对C-SCAN 算法的优化叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，**反向移动的途中不会响应请求**。

#### 5. 页面置换算法 ####

1.  页面置换算法详细介绍
    
    请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入。而内存中给页面留的位置是有限的，在内存中以帧为单位放置页面。为了防止请求调页的过程出现过多的内存页面错误（即需要的页面当前不在内存中，需要从硬盘中读数据，也即需要做页面的替换）而使得程序执行效率下降，我们需要设计一些页面置换算法，页面按照这些算法进行相互替换时，可以尽量达到较低的错误率。常用的页面置换算法如下：
    
     *  **先进先出置换算法（FIFO）**
    
    先进先出，即淘汰最早调入的页面。
    
     *  **最佳置换算法（OPT）**
    
    选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。
    
     *  **最近最久未使用（LRU）算法**
    
    即选择最近最久未使用的页面予以淘汰
    
     *  **时钟（Clock）置换算法**
    
    时钟置换算法也叫最近未用算法 NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。

#### 6. 网络系统 ####

1.  什么是零拷贝
    
    为了提高文件传输的性能，于是就出现了零拷贝技术，它通过一次系统调用（`sendfile` 方法）合并了磁盘读取与网络发送两个操作，降低了上下文切换次数。另外，拷贝数据都是发生在内核中的，天然就降低了数据拷贝的次数。
    
    Kafka 和 Nginx 都有实现零拷贝技术，这将大大提高文件传输的性能。
    
    零拷贝技术是基于 PageCache 的，PageCache 会缓存最近访问的数据，提升了访问缓存数据的性能，同时，为了解决机械硬盘寻址慢的问题，它还协助 I/O 调度算法实现了 IO 合并与预读，这也是顺序读比随机读性能好的原因。这些优势，进一步提升了零拷贝的性能。
2.  I/O多路复用
    
    既然为每个请求分配一个进程/线程的方式不合适，那有没有可能只使用一个进程来维护多个 Socket 呢？答案是有的，那就是 **I/O 多路复用**技术。
    
    一个进程虽然任一时刻只能处理一个请求，但是处理每个请求的事件时，耗时控制在 1 毫秒以内，这样 1 秒内就可以处理上千个请求，把时间拉长来看，多个请求复用了一个进程，这就是多路复用，这种思想很类似一个 CPU 并发多个进程，所以也叫做时分多路复用。
    
    我们熟悉的 select/poll/epoll 内核提供给用户态的多路复用系统调用，**进程可以通过一个系统调用函数从内核中获取多个事件**。
    
    select/poll/epoll 是如何获取网络事件的呢？在获取事件时，先把所有连接（文件描述符）传给内核，再由内核返回产生了事件的连接，然后在用户态中再处理这些连接对应的请求即可。
3.  select/poll/epoll
    
    select 和 poll 并没有本质区别，它们内部都是使用「线性结构」来存储进程关注的 Socket 集合。
    
    在使用的时候，首先需要把关注的 Socket 集合通过 select/poll 系统调用从用户态拷贝到内核态，然后由内核检测事件，当有网络事件产生时，内核需要遍历进程关注 Socket 集合，找到对应的 Socket，并设置其状态为可读/可写，然后把整个 Socket 集合从内核态拷贝到用户态，用户态还要继续遍历整个 Socket 集合找到可读/可写的 Socket，然后对其处理。
    
    很明显发现，select 和 poll 的缺陷在于，当客户端越多，也就是 Socket 集合越大，Socket 集合的遍历和拷贝会带来很大的开销，因此也很难应对 C10K。
    
    epoll 是解决 C10K 问题的利器，通过两个方面解决了 select/poll 的问题。
    
     *  epoll 在内核里使用「红黑树」来关注进程所有待检测的 Socket，红黑树是个高效的数据结构，增删改一般时间复杂度是 O(logn)，通过对这棵黑红树的管理，不需要像 select/poll 在每次操作时都传入整个 Socket 集合，减少了内核和用户空间大量的数据拷贝和内存分配。
     *  epoll 使用事件驱动的机制，内核里维护了一个「链表」来记录就绪事件，只将有事件发生的 Socket 集合传递给应用程序，不需要像 select/poll 那样轮询扫描整个集合（包含有和无事件的 Socket ），大大提高了检测的效率。
    
    而且，epoll 支持边缘触发和水平触发的方式，而 select/poll 只支持水平触发，一般而言，边缘触发的方式会比水平触发的效率高。
4.  高性能网络模式：Reactor和Proactor
    
    常见的 Reactor 实现方案有三种。
    
    第一种方案单 Reactor 单进程 / 线程，不用考虑进程间通信以及数据同步的问题，因此实现起来比较简单，这种方案的缺陷在于无法充分利用多核 CPU，而且处理业务逻辑的时间不能太长，否则会延迟响应，所以不适用于计算机密集型的场景，适用于业务处理快速的场景，比如 Redis（6.0之前 ） 采用的是单 Reactor 单进程的方案。
    
    第二种方案单 Reactor 多线程，通过多线程的方式解决了方案一的缺陷，但它离高并发还差一点距离，差在只有一个 Reactor 对象来承担所有事件的监听和响应，而且只在主线程中运行，在面对瞬间高并发的场景时，容易成为性能的瓶颈的地方。
    
    第三种方案多 Reactor 多进程 / 线程，通过多个 Reactor 来解决了方案二的缺陷，主 Reactor 只负责监听事件，响应事件的工作交给了从 Reactor，Netty 和 Memcache 都采用了「多 Reactor 多线程」的方案，Nginx 则采用了类似于 「多 Reactor 多进程」的方案。
    
    Reactor 可以理解为「来了事件操作系统通知应用进程，让应用进程来处理」，而 Proactor 可以理解为「来了事件操作系统来处理，处理完再通知应用进程」。
    
    因此，真正的大杀器还是 Proactor，它是采用异步 I/O 实现的异步网络模型，感知的是已完成的读写事件，而不需要像 Reactor 感知到事件后，还需要调用 read 来从内核中获取数据。
    
    不过，无论是 Reactor，还是 Proactor，都是一种基于「事件分发」的网络编程模式，区别在于 Reactor 模式是基于「待完成」的 I/O 事件，而 Proactor 模式则是基于「已完成」的 I/O 事件。
5.  一致性哈希介绍
    
    一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。
    
    但是一致性哈希算法不能够均匀的分布节点，会出现大量请求都集中在一个节点的情况，在这种情况下进行容灾与扩容时，容易出现雪崩的连锁反应。
    
    为了解决一致性哈希算法不能够均匀的分布节点的问题，就需要引入虚拟节点，对一个真实节点做多个副本。不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。
    
    引入虚拟节点后，可以会提高节点的均衡度，还会提高系统的稳定性。所以，带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。

#### 7. 锁 ####

1.  什么是死锁和产生死锁原因
    
    **死锁**，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 如下图所示：如果此时有一个线程 A，已经持有了锁 A，但是试图获取锁 B，线程 B 持有锁 B，而试图获取锁 A，这种情况下就会产生死锁。
    
    **产生死锁原因**
    
    由于系统中存在一些不可剥夺资源，而当两个或两个以上进程占有自身资源，并请求对方资源时，会导致每个进程都无法向前推进，这就是死锁。
    
     *  **竞争资源**
    
    例如：系统中只有一台打印机，可供进程 A 使用，假定 A 已占用了打印机，若 B 继续要求打印机打印将被阻塞。
    
    **系统中的资源可以分为两类：**
    
    1.  可剥夺资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU 和主存均属于可剥夺性资源；
    2.  不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。
    
     *  **进程推进顺序不当**
    
    例如：进程 A 和 进程 B 互相等待对方的数据。
    
    **死锁产生的必要条件？**
    
    1.  互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
    2.  请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
    3.  不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
    4.  环路等待条件：在发生死锁时，必然存在一个进程–资源的环形链。
2.  如何避免死锁
    
    预防死锁、避免死锁、检测死锁、解除死锁
    
    **预防死锁**
    
    1.  破坏请求条件：一次性分配所有资源，这样就不会再有请求了；
    2.  破坏请保持条件：只要有一个资源得不到分配，也不给这个进程分配其他的资源：
    3.  破坏不可剥夺条件：当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源；
    4.  破坏环路等待条件：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。
    
    **解除死锁**
    
    1.  资源剥夺：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程（但应该防止被挂起的进程长时间得不到资源）；
    2.  撤销进程：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源（撤销的原则可以按进程优先级和撤销进程代价的高低进行）；
    3.  进程回退：让一个或多个进程回退到足以避免死锁的地步。进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。
3.  什么是悲观锁、乐观锁
    
    悲观锁做事比较悲观，它认为**多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁**。
    
    乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：**先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作**。
    
    可见，乐观锁的心态是，不管三七二十一，先改了资源再说。另外，你会发现**乐观锁全程并没有加锁，所以它也叫无锁编程**。
    
    互斥锁、自旋锁、读写锁，都是属于悲观锁。
4.  哲学家进餐问题
    
    生产者-消费者问题描述：
    
     *  **生产者**在生成数据后，放在一个缓冲区中；
     *  **消费者**从缓冲区取出数据处理；
     *  任何时刻，**只能有一个**生产者或消费者可以访问缓冲区；
    
    我们对问题分析可以得出：
    
     *  任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，**需要互斥**；
     *  缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者**需要同步**。
    
    那么我们需要三个信号量，分别是：
    
     *  互斥信号量 `mutex`：用于互斥访问缓冲区，初始化值为 1；
     *  资源信号量 `fullBuffers`：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；
     *  资源信号量 `emptyBuffers`：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；
    
    如果消费者线程一开始执行 `P(fullBuffers)`，由于信号量 `fullBuffers` 初始值为 0，则此时 `fullBuffers` 的值从 0 变为 -1，说明缓冲区里没有数据，消费者只能等待。
    
    接着，轮到生产者执行 `P(emptyBuffers)`，表示减少 1 个空槽，如果当前没有其他生产者线程在临界区执行代码，那么该生产者线程就可以把数据放到缓冲区，放完后，执行 `V(fullBuffers)` ，信号量 `fullBuffers` 从 -1 变成 0，表明有「消费者」线程正在阻塞等待数据，于是阻塞等待的消费者线程会被唤醒。
    
    消费者线程被唤醒后，如果此时没有其他消费者线程在读数据，那么就可以直接进入临界区，从缓冲区读取数据。最后，离开临界区后，把空槽的个数 + 1。
5.  生产者、消费者问题
    
    哲学家就餐的问题描述：
    
     *  `5` 个老大哥哲学家，闲着没事做，围绕着一张圆桌吃面；
     *  巧就巧在，这个桌子只有 `5` 支叉子，每两个哲学家之间放一支叉子；
     *  哲学家围在一起先思考，思考中途饿了就会想进餐；
     *  这些哲学家要两支叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐；
     *  吃完后，会把两支叉子放回原处，继续思考；
    
    一、让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。
    
    在 P 操作时，根据哲学家的编号不同，拿起左右两边叉子的顺序不同。另外，V 操作是不需要分支的，因为 V 操作是不会阻塞的。
    
    二、用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。
    
    那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。
    
    上面的程序使用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。
6.  读者写者问题
    
    读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。
    
    读者-写者的问题描述：
    
     *  「读-读」允许：同一时刻，允许多个读者同时读
     *  「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
     *  「写-写」互斥：没有其他写者时，写者才能写
    
    使用信号量的方式来尝试解决：
    
     *  信号量 `wMutex`：控制写操作的互斥信号量，初始值为 1 ；
     *  读者计数 `rCount`：正在进行读操作的读者个数，初始化为 0；
     *  信号量 `rCountMutex`：控制对 rCount 读者计数器的互斥修改，初始值为 1；
    
    这种实现，是读者优先的策略，因为只要有读者正在读的状态，后来的读者都可以直接进入，如果读者持续不断进入，则写者会处于饥饿状态。
    
    那既然有读者优先策略，自然也有写者优先策略：
    
     *  只要有写者准备要写入，写者应尽快执行写操作，后来的读者就必须阻塞；
     *  如果有写者持续不断写入，则读者就处于饥饿；
    
    在方案一的基础上新增如下变量：
    
     *  信号量 `rMutex`：控制读者进入的互斥信号量，初始值为 1；
     *  信号量 `wDataMutex`：控制写者写操作的互斥信号量，初始值为 1；
     *  写者计数 `wCount`：记录写者数量，初始值为 0；
     *  信号量 `wCountMutex`：控制 wCount 互斥修改，初始值为 1；
    
    注意，这里 `rMutex` 的作用，开始有多个读者读数据，它们全部进入读者队列，此时来了一个写者，执行了 `P(rMutex)` 之后，后续的读者由于阻塞在 `rMutex` 上，都不能再进入读者队列，而写者到来，则可以全部进入写者队列，因此保证了写者优先。
    
    同时，第一个写者执行了 `P(rMutex)` 之后，也不能马上开始写，必须等到所有进入读者队列的读者都执行完读操作，通过 `V(wDataMutex)` 唤醒写者的写操作。
    
    既然读者优先策略和写者优先策略都会造成饥饿的现象，那么我们就来实现一下公平策略。
    
    公平策略：
    
     *  优先级相同；
     *  写者、读者互斥访问；
     *  只能一个写者访问临界区；
     *  可以有多个读者同时访问临界资源；

#### 8. 操作系统知识点 ####

1.  对并发和并行的理解
    
    1.  并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔发生；
    2.  并行是在不同实体上的多个事件，并发是在同一实体上的多个事件；
2.  什么是用户态和内核态
    
    用户态和内核态是操作系统的两种运行状态。
    
     *  `内核态`：处于内核态的 CPU 可以访问任意的数据，包括外围设备，比如网卡、硬盘等，处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。
     *  `用户态`：处于用户态的 CPU 只能受限的访问内存，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。
3.  两大局部性原理是什么
    
    主要分为**时间局部性和空间局部性**。
    
    **时间局部性:**如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
    
    **空间局部性:**一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)
4.  异常和中断是什么，有什么区别
    
    **中断**
    
    当我们在敲击键盘的同时就会产生中断，当硬盘读写完数据之后也会产生中断，所以，我们需要知道，中断是由硬件设备产生的，而它们从物理上说就是电信号，之后，它们通过中断控制器发送给CPU，接着CPU判断收到的中断来自于哪个硬件设备（这定义在内核中），最后，由CPU发送给内核，有内核处理中断。
    
    **异常**
    
    CPU处理程序的时候一旦程序不在内存中，会产生缺页异常；当运行除法程序时，当除数为0时，又会产生除0异常。所以，大家也需要记住的是，**异常是由CPU产生的，同时，它会发送给内核，要求内核处理这些异常**。
    
    **相同点**
    
     *  最后都是由CPU发送给内核，由内核去处理
     *  处理程序的流程设计上是相似的
    
    **不同点**
    
     *  产生源不相同，异常是由CPU产生的，而中断是由硬件设备产生的
     *  内核需要根据是异常还是中断调用不同的处理程序
     *  中断不是时钟同步的，这意味着中断可能随时到来；异常由于是CPU产生的，所以它是时钟同步的
     *  当处理中断时，处于中断上下文中；处理异常时，处于进程上下文中
5.  原子操作
    
    **处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。**首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存中读取或者写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。Pentium 6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的，但是复杂的内存操作处理器是不能自动保证其原子性的，比如跨总线宽度、跨多个缓存行和跨页表的访问。但是，处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。
    
    （1）使用总线锁保证原子性 第一个机制是通过总线锁保证原子性。
    
    **所谓总线锁就是使用处理器提供的一个LOCK＃信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。**
    
    （2）使用缓存锁保证原子性 第二个机制是通过缓存锁定来保证原子性。
6.  服务器高并发解决方案
    
     *  应用数据与静态资源分离 将静态资源（图片，视频，js，css等）单独保存到专门的静态资源服务器中，在客户端访问的时候从静态资源服务器中返回静态资源，从主服务器中返回应用数据。
     *  客户端缓存 因为效率最高，消耗资源最小的就是纯静态的html页面，所以可以把网站上的页面尽可能用静态的来实现，在页面过期或者有数据更新之后再将页面重新缓存。或者先生成静态页面，然后用ajax异步请求获取动态数据。
     *  集群和分布式 （集群是所有的服务器都有相同的功能，请求哪台都可以，主要起分流作用）  
        （分布式是将不同的业务放到不同的服务器中，处理一个请求可能需要使用到多台服务器，起到加快请求处理的速度。）  
        可以使用服务器集群和分布式架构，使得原本属于一个服务器的计算压力分散到多个服务器上。同时加快请求处理的速度。
     *  反向代理 在访问服务器的时候，服务器通过别的服务器获取资源或结果返回给客户端。
7.  抖动你知道是什么吗？它也叫颠簸现象
    
    刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
    
    为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率 为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程工作集” 的概念