计算机基本结构为 5 部分：运算器(ALU)、控制器、存储器、输入设备、输出设备，这 5 个部分也被称为冯诺依曼模型。

        

【tips】运算器、控制器是在中央处理器(CPU)里的，存储器就是我们常见的内存，输入输出设备则是计算机外接的设备，比如键盘就是输入设备，显示器就是输出设备。

        存储单元和输入输出设备要与CPU打交道的话，离不开总线。所以，它们之间的关系如下图：

        

        存储器分为内部存储器和外部存储器。 

• 内部存储器：又叫内存、主存。存取速度快、容量小、价格高。用来存放即将执行的程序和数据，可供 CPU 直接读取。
  • 随机存储器（RAM，Random Access Memory）：可以被 CPU 随机读取（读取任何一个地址数据的速度是一样的，写入任何一个地址数据的速度也是一样的），一般存放 CPU 将要执行的程序、数据，断电丢失数据。
  • 只读存储器（ROM，Read-only Memory）：只能被 CPU 读，不能轻易被 CPU 写，用来存放永久性的程序和数据，比如：系统引导程序、监控程序等。具有掉电非易失性。
  • 高速缓存存储器（Cache）：Cache 是计算机中的一个高速、小容量存储器，其中存放的是 CPU 近期要执行的指令和数据，其存取速度可以和 CPU 的速度匹配，一般采用静态 RAM 充当 Cache。
          程序和数据都存储在内存中，存储的区域是线性的。
          在计算机数据存储中，存储数据的基本单位是字节（byte），1 字节等于 8 位（8 bit）。每一个字节都对应一个内存地址。内存的地址是从 0 开始编号的，然后自增排列，最后一个地址为内存总字节数 - 1，这种结构好似、程序里的数组，所以内存的读写任何一个数据的速度都是一样的。内存的存取速度会直接影响计算机的运算速度。由于 CPU 是高速器件，所以 CPU 的速度是受制于内存的存取速度的。为了解决 CPU 和内存速度不匹配的问题，在 CPU 和内存之间设置了一种高速缓冲存储器Cache。
  
• 外部存储器：存取速度慢。用来存放暂时用不着的程序和数据，可以和内存交换数据，不需要依靠电来存储数据。如硬盘、磁盘、光盘、U盘等。

        中央处理器也就是我们常说的 CPU，32 位和 64 位 CPU 最主要区别在于一次能计算多少字节的数据：

• 32 位 CPU 一次可以计算 4 个字节；
• 64 位 CPU 一次可以计算 8 个字节；

（3）总线

        总线用于 CPU 和存储器及和其他设备之间的通信。

        总线可分为 3 种：地址总线、数据总线、控制总线。

• 地址总线：用于指定 CPU 将要操作的内存地址；
• 数据总线：用于读写内存的数据；
• 控制总线：用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后进行响应，也需要控制总线。

        当 CPU 要读写内存数据的时候，一般需要通过下面这三个总线：

• 首先要通过「地址总线」来指定内存的地址；
• 然后通过「控制总线」控制是读还是写命令；
• 最后通过「数据总线」来传输数据；

        程序实际上是一条一条指令，所以程序的运行过程就是把每一条指令一步一步的执行起来，负责执行指令的就是 CPU 了。

        

        CPU 执行程序的过程如下：

• 第一步：CPU 读取「程序计数器」的值，这个值是指令的内存地址，然后 CPU 的「控制单元」操作「地址总线」指定需要访问的内存地址，通知内存准备数据，准备好后通过「数据总线」将指令数据传给 CPU，CPU 收到内存传来的数据后，将这个指令数据存入到「指令寄存器」。
• 第二步：「程序计数器」的值自增，表示指向下一条指令。（自增的大小取决于 CPU 的位宽，比如 32 位的 CPU，指令是 4 个字节，需要 4 个内存地址存放，因此「程序计数器」的值会自增 4）
• 第三步：CPU 分析「指令寄存器」中的指令，确定指令的类型和参数，如果是计算类型的指令，就把指令交给「逻辑运算单元」运算；如果是存储类型的指令，则交由「控制单元」执行。

★【总结】一个程序执行的时候，CPU 会根据程序计数器里的内存地址，从内存里面把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，顺序读取下一条指令。CPU 从程序计数器读取指令、到执行、再到下一条指令，这个过程会不断循环，直到程序执行结束。(这个不断循环的过程被称为 CPU 的指令周期)

        我们编写的代码只是一个存储在硬盘的静态文件，通过编译后就会生成二进制可执行文件，当我们运行这个可执行文件后，它会被装载到内存中，接着 CPU 会执行程序中的每一条指令，那么这个运行中的程序，就被称为「进程」。

        进程是对运行中程序的封装，是操作系统进行资源调度和分配的基本单位。

        进程和程序的关系？

        ——进程存在的目的就是执行某个程序。进程与程序的区别是：

• 进程是动态的概念，程序是静态的概念。程序是指令代码的有序集合，而进程是程序的一次执行过程，它能动态的被创建、执行和消亡。
• 进程是暂时的，程序是永久的。进程是一个程序执行状态变化的过程，程序是可长久保存。
• 进程是由程序、数据和进程控制块组成。程序是由若干行代码组成。
• 通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
• 进程能够独立运行，可以为其独立分配资源，独立接受调度的单位，而程序不能在多道程序设计环境下运行。

        并发：一个处理器核在很短的时间内分别执行多个进程。

        并行：多个处理器核同时执行多个进程。

        

        对于并发来说，CPU需要从⼀个进程切换到另⼀个进程，这个过程需要保存进程的状态信息，方便切换回来时可以继续执行。因此一个进程至少具备三种基本状态：运行状态、就绪状态、阻塞状态。

• 运行状态（Running）：该时刻进程占用了 CPU；
• 就绪状态（Ready）：可运行，但由于其他进程处于运行状态而暂时停止运行，得到CPU的控制权就可以运行；
• 阻塞状态（Blocked）：该进程正在等待某一事件(资源)发生（如等待输入/输出操作的完成）而暂时停止运行。此时即使给它CPU控制权，它也无法运行。
   

        进程还有另外两个常见状态：创建状态和结束状态。

• 创建状态（new）：进程正在被创建时的状态；
• 结束状态（Exit）：进程正在从系统中消失时的状态。
  

        上图中各进程间的转换过程：

• NULL -> 创建状态：一个新进程被创建时的第一个状态；
• 创建状态 -> 就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；
• 就绪态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运行该进程；
• 运行状态 -> 结束状态：当进程已经运行完成或出错时，会被操作系统作结束状态处理；
• 运行状态 -> 就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行；
• 运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；
• 阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态。

        处于阻塞状态的进程可能会占用物理内存空间，造成了内存资源浪费。所以通常会把阻塞进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。因此这就需要一个新的状态来描述进程没有占用实际物理内存空间的情况，这个状态就是挂起状态。

        导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

• 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
• 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程。

        挂起状态可以分为两种：

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

        

        在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。PCB 是进程存在的唯一标识：一个进程的存在必然会有一个 PCB；进程消失 PCB 也会随之消失。

【PCB 具体包含什么信息呢？】

• 进程描述信息：
  • 进程标识符：标识各个进程，每个进程都有一个唯一的进程标识符；
  • 用户标识符：表示进程归属哪个用户，用户标识符主要为共享和保护服务。
• 进程控制管理信息：
  • 进程当前状态：如 new、ready、running、waiting 或 blocked 等；
  • 进程优先级：进程抢占 CPU 时的优先级。
• 资源分配清单：有关内存地址空间或虚拟地址空间的信息、所打开文件的列表和所使用的 I/O 设备信息。
• CPU 相关信息：CPU 中各个寄存器的值。（当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，方便进程重新执行时，能从断点处继续执行）

【PCB 是一个什么样的数据结构？是如何组织的？】

        PCB 通常是通过链表的方式进行组织的，把具有相同状态的进程链在一起，组成各种队列，方便增删和进程管理。比如就绪队列和阻塞队列等。

• 就绪队列：将所有处于就绪状态的进程链在一起；
• 阻塞队列：把所有处于阻塞状态的进程链在一起。

（5）进程切换为何比线程慢？

        涉及到虚拟内存的问题，进程切换涉及虚拟地址空间的切换⽽线程不会。 因为每个进程都有⾃⼰的虚拟地址空间，⽽线程是共享所在进程的虚拟地址空间的，所以同⼀个进程中的线程进⾏ 线程切换时不涉及虚拟地址空间的转换。 把虚拟地址转换为物理地址需要查找⻚表，⻚表查找是⼀个很慢的过程（⾄少访问2次内存），因此通常使⽤ Cache来缓存常⽤的地址映射，这样可以加速⻚表查找，这个cache就是TLB（快表）。 由于每个进程都有⾃⼰的虚拟地址空间，那么显然每个进程都有⾃⼰的⻚表，那么当进程切换后⻚表也要进⾏切 换，⻚表切换后TLB就失效了，cache失效导致命中率降低，那么虚拟地址转换为物理地址就会变慢，表现出来的 就是程序运⾏会变慢，⽽线程切换则不会导致TLB失效，因为线程线程⽆需切换地址空间，这也就是进程切换要比同进程下线程切换慢的原因。

• 什么是守护进程？
  守护进程是指在后台运行的，没有控制终端与它相连的进程。它独立于控制终端，周期性地执行某种任务。
  （Linux的大多数服务器就是用守护进程的方式实现的，比如web服务器进程http等。）
• 守护进程的创建过程？https://www.bilibili.com/video/BV1z5411K7XY/?spm_id_from=333.337.search-card.all.click&vd_source=fb6dff5e4de754c2b530b6cdd9a61812
  • ①创建子进程，终止父进程，让程序在后台执行：
    • 方法是调⽤fork()产⽣⼀个⼦进程，然后使⽗进程退出。
  • ②在子进程中创建新对话：
    • 守护进程需要摆脱⽗进程的影响，⽅法是调⽤setsid()使进程成为⼀个会话组⻓。setsid()调⽤成功后，进程成为新的会话组⻓和进程组⻓，并与原来的登录会话、进程组和控制终端脱离。
      在调用fork函数时，子进程全盘拷贝父进程的会话期(session，是一个或多个进程组的集合)、进程组、控制终端等，虽然父进程退出了，但原先的会话期、进程组、控制终端等并没有改变，因此，那还不是真正意义上使两者独立开来。setsid函数能够使进程完全独立出来，从而脱离所有其他进程的控制。
      
  • ③禁⽌进程重新打开控制终端：
    • 经过①和②，子进程已经成为⼀个⽆终端的会话组⻓，但是它可以重新申请打开⼀个终端。为了避免这种情况发⽣，可以通过使进程不再是会话组⻓来实现。再⼀次通过fork()创建新的⼦进程，使调⽤fork的进程退出。
  • ④关闭不再需要的⽂件描述符：
    • 子进程从⽗进程继承打开的⽂件描述符。如果不关闭将会浪费系统资源，造成进程所在的⽂件系统⽆法卸下以及引起⽆法预料的错误。⾸先获得最⾼⽂件描述符值，然后⽤⼀个循环程序，关闭0到最⾼⽂件描述符值的所有⽂件描 述符。
  • ⑤将当前⽬录更改为根⽬录。
  • ⑥⼦进程从⽗进程继承的⽂件创建屏蔽字可能会拒绝某些许可权：
    • 为防⽌这⼀点，使⽤unmask(0)将屏蔽字清零
  • ⑦处理SIGCHLD信号：
    • 对于服务器进程，在请求到来时往往⽣成⼦进程处理请求。如果⼦进程等待⽗进程捕获状态，则⼦进程将成为僵⼫进程（zombie），从⽽占⽤系统资源。如果⽗进程等待⼦进程结束，将增加⽗进程的负担，影响服务器进程的并发性能。在Linux下可以简单地将SIGCHLD信号的操作设为SIG_IGN。这样，⼦进程结束时不会产⽣僵⼫进程。
• 什么是僵尸进程？
  多进程程序中父进程⼀般需要跟踪子进程的退出状态。当⼦进程退出，⽗进程在运⾏，⼦进程必须等到⽗进程捕获到了子进程的退出状态才算真正结束。在子进程结束后父进程读取状态前，此时的子进程为僵尸进程。
  设置僵⼫进程的⽬的是维护⼦进程的信息，以便⽗进程在以后某个时候获取。这些信息⾄少包括进程ID，进程的终 ⽌状态，以及该进程使⽤的CPU时间。所以当终⽌⼦进程的⽗进程调⽤wait或waitpid时就可以得到这些信息。

（1）抢占式/非抢占式调度算法

• 非抢占式调度算法：当把CPU分配给某个进程后，就一直让该进程运行下去，不会因为时钟中断或其他原因去抢占他的CPU，直到该进程进入阻塞态或者执行结束，才会把CPU分配给另一个进程。
• 抢占式调度算法：允许暂停某个正在运行的进程，将已分配给它的CPU重新分配给其他进程。

• 先来先服务(First Come First Serve, FCFS)算法：每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
      特点：有利于长作业，不利于短作业。当一个长作业先运行了，那么后面的短作业等待的时间就会很长。适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。
• 最短作业优先(Shortest Job First, SJF)调度：优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。
      特点：有利于短作业，不利于长作业。长作业有可能会饿死，处于⼀直等待短作业执行完毕的状态，如果⼀直有短作业到来，那么长作业永远得不到调度。
• 高响应比优先(Highest Response Ratio Next, HRRN)调度算法：每次进行进程调度时，先计算响应比优先级，然后让响应比优先级最高的进程先运行。
      
      特点：一个进程的要求服务时间是不可预估的。所以高响应比优先调度算法是理想型的调度算法，现实中是实现不了的。
• 时间片轮转(Round Robin, RR)调度算法：每个进程被分配一个时间段，称为时间片（Quantum），只允许该进程在该时间段中运行。
          如果时间片用完进程还在运行，就把该进程从 CPU 释放出来，并把 CPU 分配给另外一个进程；
          如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。
          
• 最高优先级(Highest Priority First，HPF)调度算法：为每个进程分配⼀个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
      进程的优先级可以分为静态优先级和动态优先级：
          -- 静态优先级：创建进程时候就已经确定了优先级，整个运行时优先级都不会变化；
          -- 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级；如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
      该算法也有两种处理优先级高的方法——非抢占式和抢占式。
• 多级反馈队列(Multilevel Feedback Queue)调度算法：是时间片轮转算法和最高优先级算法的结合。
      「多级」：表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
      「反馈」：表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列。
          
  -- 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
  -- 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
  -- 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行。
          对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

3.进程的通信方式(IPC:Inter-Process Communication)

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

• 匿名管道（pipe）
  • 半双工数据传输，数据可以双向传输，但在同⼀时刻只能单方向流动；
  • 数据只能从管道的⼀端写入，从另⼀端读出；
  • 数据遵循先入先出的规则；
  • 传输的数据是无格式的，要求管道通信双方必须事先约定好数据的格式(如多少字节算⼀个消息等)；
  • 管道不是普通的文件，不属于某个文件系统，其只存在于内存中。管道在内存中对应⼀个缓冲区。对于不同的系统大小不⼀定相同；
  • 从管道读数据是⼀次性操作，数据⼀旦被读走，就从管道中被抛弃，释放空间以便写更多的数据；
  • 匿名管道没有名字，只能在具有公共祖先的进程（具有亲缘关系的进程，如父进程与子进程、兄弟进程）之间使用；
  • 存在阻塞方式。
• 匿名管道的创建
  • 匿名管道的创建，需要调用pipe函数，表示创建一个匿名管道，并建立两个文件描述符(file descriptor) fd[0] 和 fd[1]，fd[0]用于读管道，fd[1]用于写管道。

    /**
     * 创建匿名管道。注意，这个匿名管道是特殊的文件，只存在于内存，不存于文件系统中。 
      * @param fd 为int型数组的⾸地址，其存放了管道的⽂件描述符 
     * @return 创建成功返回0，创建失败返回-1.
     */
    int pipe(int fd[2])

    
• 读写管道的四种情况
  • ①读端没被关闭：如果管道被写满了，写进程想写管道会被阻塞；
  • ②读端被关闭：写进程写管道会收到⼀个信号，然后退出；
  • ③写端没被关闭：
    • 管道中没有数据：读进程读管道会被阻塞(因为不久的将来可能有数据写入管道，就可以读了)；
    • 管道中有数据：读进程会将数据读出来；
  • ④写端被关闭：读进程读管道会读取全部内容，最后返回0。
• 命名管道（FIFO）
  • 命名管道提前创建了一个类型为管道的设备文件(FIFO)，在进程里只要使用这个设备文件，就可以相互通信。因此，不相关的进程间也能通过命名管道相互通信。
• ★命名管道与匿名管道的区别？
  • ①匿名管道基于文件描述符进行通信，命名管道是个特殊的文件，借助文件系统实现通信；
  • ②匿名管道用于有亲缘关系的进程间的通信，命名管道可以在没有亲缘关系的进程间通信。
• 命名管道的创建
  • 通过命令创建：
    • mkfifo  fifo；
    • eg创建 fifo 文件
  • 通过mkfifo函数创建

（2）消息队列

        A 进程要通过消息队列给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。

• 特点：
  • 消息队列是保存在内核中的消息链表，每个消息体都是固定大小的存储块(不像管道是无格式的字节流数据)。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。
  • 如果没有释放消息队列或者没有关闭操作系统，消息队列会⼀直存在。（匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁。）
• 缺点：
  • 消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销。(进程写数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程；同理另一进程读内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。)
    
  • 消息队列不适合比较大数据的传输。因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。

（3）共享内存(共享存储映射)

        对于现在操作系统的内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间(外存)，不同进程的虚拟内存映射到不同的物理内存(即存储映射)中。所以，即使进程 A 和 进程 B 的虚拟地址是一样的，其实访问的是不同的物理内存地址，对于数据的增删查改互不影响。

        共享内存的机制，就是相互通信的进程共享一块内存存储区，进程可以直接通过读写内存来实现通信。进程写入的东西，另外一个进程马上就能看到了。

        共享内存可以说是最有用的进程间通信方式，也是最快的IPC形式，因为进程可以直接读写内存，而不需要任何数据的拷贝。

        

        以上进程通信方式都是常规状态下的进程通信。对于异常情况下的进程通信，就需要用信号的方式来通知进程。

        在 Linux 中， 提供了几十种代表不同意义的信号，我们可以通过 kill -l 命令查看所有的信号：

        

        信号是软件中断，它是在软件层次上对中断机制的⼀种模拟 。信号是进程通信中唯一的异步通信机制。信号可以使一个正在运行的进程被另一个正在运行的异步进程中断，去处理某⼀个突发事件。 
        信号可以直接进行用户空间进程和内核空间进程的交互，内核进程可以利用信号来通知用户空间进程发生了哪些系统事件。

• 特点：
  • 信号简单；
  • 不能携带大量信息；
  • 满足某个特定条件才能发送。
• 信号一个的完整生命周期
  • 信号的产生
  • 信号在进程中注册
  • 信号在进程中注销
  • 执行信号处理函数
• 信号的编号
  • 信号编号从1开始，到64结束，没有编号为0的信号；
  • 1~31号称为常规信号(普通信号、标准信号)，32~64号称为实时信号，驱动编程与硬件相关。
• 常见的信号
  • 2）SIGINT：按下<Ctrl+C>组合键时产生的信号，表示终止进程；
    
  • 3）SIGQUIT：按下<Ctrl+\>组合键时产生的信号，和SIGINT类似，也是表示终止进程。但是进程收到SIGQUIT退出时会产生core文件，从这个意义讲上SIGQUIT类似于一个程序错误信号；
  • 11）SIGSEGV： 表示进程进行了无效的内存访问(段错误)， 终止进程并产生core⽂件；
  • 13）SIGPIPE：向一个没有读端的管道写数据时，会发出SIGPIPE信号，即会生成BROKEN PIPE错误，终止进程；
  • 17）SIGCHLD：子进程结束时，父进程会收到这个信号，默认忽略这个信号。
• 信号的状态
  • 产生
    • 当⽤户按某些终端键时，将产生信号；
    • 硬件异常将产⽣信号；
    • 软件异常将产⽣信号；
    • 调用系统函数(如：kill、raise、abort)将发送信号；
    • 运行 kill/killall 命令将发送信号。
  • 未决状态：信号没有被处理
  • 递达状态：信号被处理了
• 信号的四要素
  • 编号（使用 man 7 signal 命令可以查看信号的帮助文档）
  • 名称
  • 事件
  • 默认处理动作：  
    • Term：终止进程
    • Ign： 忽略信号 (默认即时对该种信号忽略操作)
    • Core：终止进程，⽣成Core⽂件。(查验死亡原因，⽤于gdb调试)
    • Stop：暂停进程
    • Cont：继续运行进程
      
  • 【tips】9) SIGKILL 和19) SIGSTOP 信号不允许忽略和捕捉，只能执⾏默认动作。甚⾄不能将其设置为阻塞。

（5）Socket

        前面提到的管道、消息队列、共享内存、信号都是在同一台主机上的进程间通信，要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了，当然它也可以在同一主机上通信。

• 针对 TCP 协议通信的 socket 编程模型
  
  • 服务端和客户端初始化 socket，得到文件描述符；
  • 服务端调用 bind，将绑定在 IP 地址和端口;
  • 服务端调用 listen，进行监听；
  • 服务端调用 accept，等待客户端连接；
  • 客户端调用 connect，向服务器端的地址和端口发起连接请求；
  • 服务端 accept 返回用于传输的 socket 的文件描述符；
  • 客户端调用 write 写入数据；服务端调用 read 读取数据；
  • 客户端断开连接时，会调用 close，那么服务端 read 读取数据的时候，就会读取到了 EOF，待处理完数据后，服务端调用 close，表示连接关闭。

        可以看到，服务端调用 accept 时，连接成功了会返回一个已完成连接的 socket，后续用来传输数据。因此监听的 socket 和真正用来传送数据的 socket，是「两个」 socket，一个叫作监听 socket，一个叫作已完成连接 socket。

        线程是进程中的一条执行流程。

        同一个进程内多个线程之间可以共享资源(代码段、数据段、打开的文件等)，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。
        线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。因此，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。所以前面讲的进程调度算法，实际应该叫线程调度算法。

        对于线程和进程，我们可以这么理解：

• 当进程只有一个线程时，可以认为进程就等于线程；
• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的。

• 优点：
  • 一个进程中可以同时存在多个线程；
  • 各个线程之间可以并发执行，提⾼程序的并发性；
  • 各个线程之间可以共享地址空间和文件等资源，方便进行数据通信。
• 缺点：
  • 增加了项目的复杂度：在编写多线程代码的过程中，时刻要关注死锁、多并发等问题。虽然进程的子线程通常具有独立的局部变量，但是他们却共享同一块全局内存，这个共享地址空间的竞争和临界区管理非常困难，很容易增加整体的系统复杂度；
  • 时序依赖：多线程的执行在时序上可能存在依赖，因此在编写多线程代码的时候，不仅要面对多并发的问题，还要面对时序依赖的问题；
  • 性能问题：虽然线程没有快速转换进程上下文的开销，但是锁定共享数据结构以防止互相干涉的开销也很大，有时这些性能成本超过了进程分解为多线程所带来的优势。

（3）线程的资源

        

        一个进程中可以有多个线程，多个线程共享进程的堆和方法区 (JDK1.8 之后的元空间)资源，但是每个线程有自己的程序计数器、虚拟机栈 和 本地方法栈。

        程序计数器私有主要是为了线程切换后能恢复到正确的执行位置。

        虚拟机栈和本地方法栈私有是为了保证线程中的局部变量不被别的线程访问到。

• 共享资源：同一进程的多个线程共享该进程的堆和方法区资源，主要有：
  • 文件描述符表
  • 每种信号的处理方式
  •  当前工作目录
  • 用户ID和组ID
• 非共享资源：每个线程还有保证自己独立运行的私有资源——程序计数器、虚拟机栈和本地方法栈：
  • 线程id
  • 处理器现场和栈指针(内核栈)
  • 独立的栈空间(用户空间栈)
  • errno变量
  • 信号屏蔽字
  • 调度优先级

（4）线程的上下文切换

• ①进程是程序的⼀次执行过程，是资源分配的基本单位；⼀个进程在执行时可以产生多个线程，线程是CPU调度的基本单位；
• ②进程可以拥有资源，同⼀进程的多个线程可以共享进程的资源，而线程本身并不拥有系统资源，只有一点能保证独立运行的必不可少的资源(如线程控制块TCB、程序计数器、寄存器和堆栈)；
• ③线程相较于进程来说能减少开销：
  • 首先进程在创建和销毁时需要分配和销毁PCB和所需要的资源，而线程在创建时不涉及这些资源管理信息，而是共享它们；终止线程的时间也比进程快，因为线程释放的资源相比进程少很多；
  • 其次进程进行上下文切换时需要保留当前的CPU环境以及设置新进程的CPU环境，而同一线程由于资源共享，在进行上下文切换时只需要切换线程的私有数据、寄存器等这些不共享的数据。所以线程的切换开销比进程也少很多。

• ①用户线程（User Thread）：在用户空间实现的线程，由用户态的线程库来完成线程的管理。
      用户线程是基于用户态的线程管理库来实现的，包括线程的创建、终止、同步和调度等。那么TCB也是在库里面来实现的，对于操作系统而言是看不到这个 TCB 的，OS只能看到整个进程的 PCB。 所以，操作系统不直接参与用户线程的线程管理和调度。
  • 优点：
    • 线程的管理不需要内核直接参与，因此可用于不支持线程技术的操作系统；
    • 用户线程切换由线程库调度，不需要用户态与内核态之间的转换，速度特别快。
  • 缺点：
    • 因为操作系统不参与线程的调度，所以如果一个用户线程发起了系统调用而阻塞，那么进程所包含的用户线程就都不能执行了。
    • 某个线程开始运行后，只有它主动交出 CPU 执行权，其他用户线程才能运行，无法被打断。因为只有操作系统才有权限打断线程运行，但是用户线程不是由操作系统管理的。
    • 因为时间片(时间片是资源)是分配给进程的，所以对于多线程进程，分到每个用户线程的时间片就短了，执行起来会比较慢。
• ②内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程。
      内核线程由操作系统管理和调度，TCB 存放在内核中，⼀般由操作系统事先创建内核线程集(类似于线程池)，数量有限。
  • 优点：
    • 当⼀个内核线程发起系统调用阻塞时不会影响其它内核线程的执行；
    • 操作系统将CPU资源直接分配给内核线程，对于多线程线程就有更多的CPU运行时间。
  • 缺点：
    • 需要由内核来维护内核线程的上下文信息和运行状态等，会占用内核资源；
    • 内核线程的创建、终止、切换都是在内核中进行的，开销比较大。
• ③轻量级进程（LWP，Light-Weight Process）：二者的结合，在内核中来支持用户线程。
      LWP是在内核中支持的用户线程，每个LWP与内核线程是一对一映射的(即每个LWP都需要⼀个内核线程的支持)，也就是说它由内核管理，可以像普通进程⼀样被调度。
      一个进程可有一个或多个 LWP，类似于进程中的执行线程(一个进程可以有一个或多个线程)。
  

• 线程的创建快。进程的创建需要分配PCB以及所需要的各种资源，而线程创建后是共享所属进程的资源；
• 线程的终止快。进程的终止需要回收PCB以及其他资源，而线程的终止只需要回收少量寄存器和私有的栈空间；
• 线程的切换快。进程的上下文切换包括CPU寄存器和程序计数器(二者是CPU上下文切换)、虚拟内存空间、页表切换等；而线程的切换只涉及到少量的寄存器和栈。
• 线程的通信效率高。线程在创建时共享了所属进程的绝大多数资源，因此具有较高的线程间通信交互效率。

        进程创建线程时，OS需要为线程分配一个栈空间。创建的线程越多，分配的栈空间越多，需要的虚拟内存(堆内存)就越大。因此一个进程能创建多少个线程取决于进程的虚拟内存大小以及创建一个线程需要分配的栈空间大小。

 （1）32位 Windows
        对于32位Windows OS，默认情况下，进程空间(虚拟内存大小)是4G(2^32bit)，其中高位2G分给内核，低位2G分给用户，所以进程堆内存小于2G。而创建一个线程要分配1M左右的栈空间，所以在32位 Windows OS下，一个进程最多可以创建2048个线程(2G/1M=2048个)。

（2）32位 Linux

        对于32位Linux OS，默认情况下，进程空间4G，其中高位1G留给内核，低位3G留给用户，所以进程堆大小小于3G。而创建一个线程默认分配8M栈空间(ulimit -a查看)，所以在32位 Linux OS下，一个进程最多可以创建380个左右线程(3G/8M=384个)。

（3）64 位OS

        对于64位Linux OS，一个进程用户态的虚拟空间大到有 128T，所以一个进程能创建的最大线程数理论上不会受虚拟内存大小的限制，而会受系统的参数或性能限制。比如下面这三个内核参数的大小，都会影响创建线程的上限：

• /proc/sys/kernel/threads-max：表示系统支持的最大线程数，默认值是 14553；
• /proc/sys/kernel/pid_max：表示系统全局的 PID 号数值的限制，每一个进程或线程都有 ID，ID 的值超过这个数，进程或线程就会创建失败，默认值是 32768；
• /proc/sys/vm/max_map_count：表示限制一个进程可以拥有的VMA(虚拟内存区域)的数量，具体什么意思我也没搞清楚，反正如果它的值很小，也会导致创建线程失败，默认值是 65530。

        多个线程可以共享进程的资源。多个线程竞争共享资源时，如果不采取有效的措施，就会造成共享数据的混乱。

• 互斥(mutualexclusion)
  • 由于多线程执行时操作共享变量的代码可能会导致竞争状态，因此我们将这段代码称为临界区（critical section）。临界区是访问共享资源的代码片段，一定不能让多线程同时执行这部分代码。
  • 互斥指的是一个线程在临界区执行时，其他线程应该被阻止进入临界区。
  
  
• 同步(synchronization)
  • 并发进程/线程需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。也就是说线程A必须等待线程B执行完才能执行。

2.实现和使用

        在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系。为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种：

• 锁：加锁、解锁操作——实现互斥；
• 信号量：P、V 操作——实现互斥或同步。

        这两种方法都可以实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以实现进程/线程同步。

        使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。加锁的目的就是保证共享资源在任意时间里只有一个线程访问，当已经有一个线程加锁后，其他线程加锁则就会失败。

        任何想进入临界区的线程，必须先执行加锁操作。若成功加锁，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

• ★死锁(DeadLock)
  • 当两个线程都在等待对方释放锁，在没有外力的作用下，这两个线程会一直相互等待，都没办法继续运行，这种情况就是发生了死锁。
    
  • 死锁产生的必要条件——死锁只有同时满足以下四个条件才会发生：
    • 互斥：资源只能被一个进程占用，其他请求该资源的进程必须等待释放资源。
    • 占有并等待：已经占有某个资源的进程可以再请求新的资源，而新资源被占有时只能等待，等待时又不释放已占有的资源。
    • 不可抢占：进程获得的资源在用完前不能被抢占，只能主动释放。
    • 环路等待：死锁发生时，系统中⼀定有由两个或两个以上的进程组成的⼀条环路，该环路中的每个进程都在等待着下⼀个进程所占有的资源。A等B，B等C，C等A。
  • 处理死锁的方法？

    • ①预防死锁：通过破坏产生死锁的四个条件之一或几个来预防死锁。
      • 破坏互斥条件：允许多个进程同时访问资源。但是由于绝大多数资源必须互斥访问这一固有特性不能改变，因此破坏互斥条件预防死锁不太现实。
      • 破坏占有等待条件：规定所有进程在执行前一次性请求所需要的全部资源，同时只要有一种资源不满足进程要求，即使其他资源空闲系统也不会分配给进程，这样在运行时进程就不会提出资源请求，等待时也不会占有资源。
      • 破坏不可抢占条件：保证每一个进程在任何时刻只能占用一个资源，如果想请求另⼀个资源必须先释放第⼀个资源。
      • 破坏环路等待：使用资源的有序分配，即多个线程获取资源的顺序要一样。举个例子：当线程 A 先尝试获取资源 A，然后尝试获取资源 B 的时候，线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。也就是说，线程 A 和 线程 B 总是以相同的顺序申请自己想要的资源。
    • ②避免死锁：也是一种事先预防的策略，但不是通过破坏死锁产生的条件，而是在资源分配过程中，不让系统进入不安全状态以避免发生死锁。安全状态是指没有死锁发生时，即使所有进程突然请求对资源的最大需求，系统也能能够使得每个进程运行完毕，此时就说系统状态是安全的。
      • 银行家算法
        银行家算法要求进程必须声明自己请求的最大资源量，当进程请求资源时系统必须先确认自己是否有足够的资源分配给该进程，如果有足够的资源，还需要计算将这些资源分配给该进程后，会不会导致系统处于不安全状态，如果不会，才会将资源分配给进程。
    • ③检测死锁：
      • 如果进程资源分配图中无环路，则此时系统没有发生死锁；
      • 如果进程资源分配图中有环路，且每个资源类仅有一个资源，则系统中已经发生了死锁；
      • 如果进程资源分配图中有环路，且涉及到的资源类有多个资源，此时系统未必会发生死锁。如果能在进程资源分配图中找出一个不阻塞且能够在有限的时间内归还占有资源的进程，则不会发生死锁，否则会发生死锁。
    • ④解除死锁：
      • 抢占资源：将进程挂起，强行取⾛资源给另⼀个进程使用，用完再放回；
      • 回滚回复：复位到还没有取得所需的资源的状态；
      • 杀死进程：杀死环中的⼀个或多个进程，破坏循环环路。

        信号量是操作系统提供的一种协调共享资源访问的方法。通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。

        有两个原子操作的系统调用函数来控制信号量的，分别是：

• P 操作：将 sem 减 1，表示请求一个共享资源；相减后，如果 sem < 0，说明原来共享资源就用光了，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
• V 操作：将 sem 加 1，表示释放了一个共享资源；★相加后，如果 sem <= 0，说明仍有等待该资源的进程/线程被阻塞，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

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

        信号量既可以实现临界区的互斥访问，也可以实现线程同步。

• 实现临界区的互斥访问
  • 为每一类共享资源设置一个信号量 s，其初始值为 1，表示该临界资源未被占用。只要把进入临界区的操作置于 P(s) 和 V(s) 之间，就可实现进程/线程互斥。此时，任何想进入临界区的线程，必先在互斥信号量上执行 P 操作，在完成对临界资源的访问后再执行 V 操作。
    
    

    ①由于互斥信号量的初始值为 1，假设线程A先执行 P 操作， s 值变为 0，表示临界资源为空闲，可分配给线程A，然后A就进入临界区。
    ②若此时线程B想进入临界区，也应先执行 P 操作，结果使 s 变为 -1 了，这就意味着临界资源已被占用，所以线程B被阻塞。
    ③线程A从临界区出来后执行 V 操作，释放临界资源而恢复 s 值为 0 后，才唤醒线程B，使B进入临界区，等B完成临界资源的访问后，又执行 V 操作，使 s 恢复到初始值 1。
    对于两个并发线程，互斥信号量的值仅取 1、0 和 -1 三个值，分别表示：
        -- 如果互斥信号量为 1，表示没有线程进入临界区；
        -- 如果互斥信号量为 0，表示有一个线程进入临界区；
        -- 如果互斥信号量为 -1，表示线程正在临界区，另一个线程等待进入。

    通过互斥信号量的方式，就能保证临界区任何时刻只有一个线程在执行，就达到了互斥的效果。
• 实现线程同步
  • 同步的方式是设置一个信号量，其初值为 0。我们以线程“mom”给线程“son”做饭的同步问题为例，规定mom必须等son饿了才能做饭，son必须等mom做完饭才能吃饭。
    
    ①这个问题涉及两个同步，因此需要两个初始值为0的信号量。
    ②mom必须等son饿了才能做饭：mom执行 P(s1) ，相当于询问son需不需要吃饭，此时 s1 变成 -1 < 0，表明son还没饿不需要吃饭，所以mom就阻塞等待状态；
    ③当son饿了时，执行了 V(s1)，使得 s1 信号量从 -1 变成 0 <= 0，于是就唤醒了阻塞中的mom，mom就开始做饭；(②③一个同步)
    ④紧接着son执行了 P(s2)，相当于询问mom饭做完了吗，此时 s2 变成 -1 < 0，说明mom还没做完饭，所以son就阻塞等待状态；
    ⑤当mom做完饭了后，执行了V(s2)，使得s2从 -1 变成了 0 <= 0，于是就唤醒了阻塞中的son，son 就开始吃饭。(④⑤一个同步)
• 生产者与消费者问题——互斥与同步问题
  
  生产者和消费者共用一块缓冲区(共享资源)，生产者在生产出一个产品后，放进缓冲区；消费者从缓冲区取出一个产品进行消费；规定任何时刻，只能有一个生产者或消费者可以访问缓冲区(二者互斥访问缓冲区)。
  很明显：操作缓冲区是临界代码，需要互斥；缓冲区空时，消费者必须等待生产者生产产品；缓冲区满时，生产者必须等待消费者取出产品。说明生产者和消费者需要同步。
  因此我们需要三个信号量，分别是：
  
  • 互斥信号量 mutex：用于互斥访问缓冲区，初始值为 1；
  • 资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始值为 0（表明缓冲区一开始为空）；
  • 资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始值为 n（缓冲区大小）。
  
  ①如果消费者线程一开始执行 P(fullBuffers)，由于信号量 fullBuffers 初始值为 0，则此时 fullBuffers 的值从 0 变为 -1，说明缓冲区里没有数据，消费者只能等待。
  ②当生产者执行 P(emptyBuffers)，表示减少 1 个空槽，如果当前没有其他生产者线程在临界区执行代码，那么该生产者线程就可以把数据放到缓冲区，放完后，执行 V(fullBuffers) ，信号量 fullBuffers 从 -1 变成 0，表明有「消费者」线程正在阻塞等待数据，于是阻塞等待的消费者线程会被唤醒。
  ③消费者线程被唤醒后，如果此时没有其他消费者线程在读数据，那么就可以直接进入临界区，从缓冲区读取数据。最后，离开临界区后，把空槽的个数 + 1。
• 哲学家就餐问题——经典同步问题
  
  • 问题描述：5 个哲学家围绕着一张圆桌吃面，这个桌子只有 5 个叉子，每两个哲学家之间放一支叉子，每个哲学家需要左右两个叉子才能吃面；哲学家围在一起先思考，思考中途饿了就会想进餐；吃完后，会把两支叉子放回原处，继续思考。
  • 方案一（错误）：如果所有哲学家同时拿起左手边的叉子，那么所有哲学家都在等待右手的叉子，导致死锁。
    
  • 方案二（解决）：为了防止死锁的发生，可以设置两个条件：
            1. 必须同时拿起左右两个叉子
            2. 只有在两个邻居都没有进餐的情况下才允许进餐
• 读者写者问题——经典同步问题
  • 问题描述：读者只会读取数据，不会修改数据，而写者既可以读也可以修改数据。
    「读-读」允许：同一时刻，允许多个读者同时读
    「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
    「写-写」互斥：没有其他写者时，写者才能写
  • 读者优先策略：
    只要有读者正在读的状态，后来的读者都可以直接进入，如果读者持续不断进入，则写者会处于饥饿状态。
    
  • 写者优先策略：
    
  • 公平方案：
    读者优先策略和写者优先策略都会造成饥饿的现象，那么我们就来实现一下公平策略：
    
    • 读、写者优先级相同；
    • 写者、读者互斥访问；
    • 只能一个写者访问临界区；
    • 可以有多个读者同时访问临界资源；
    
• 管程
  管程可以看做一个软件模块，将共享的变量(共享资源)和对共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制。

        1）互斥锁与自旋锁

        很多高级锁都是基于互斥锁和自旋锁实现的。当已经有一个线程加锁后，其他线程加锁则就会失败。互斥锁和自旋锁对于加锁失败后的处理方式是不一样的：

• 互斥锁加锁失败(即获取不到锁)后，线程会释放 CPU 给其他线程(需要进行线程切换)；
      比如线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放锁，线程 B 加锁就会失败，于是线程 B 就会释放 CPU 让给其他线程，既然线程 B 释放掉了 CPU，自然线程 B 加锁的代码就会被阻塞。
      对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。当加锁失败时，内核会将线程置为睡眠状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，就可以继续执行了。
      ★因此，互斥锁加锁失败时，会从用户态切换到内核态，让内核帮我们切换线程，虽然简化了使用锁的难度，但是存在一定的性能开销成本(即线程上下文切换的成本)。
  
• 自旋锁加锁失败后，线程会忙等待，直到它拿到锁(不需要进行线程切换，只忙等待)。
      自旋锁是通过 CPU 提供的 CAS 函数（Compare And Swap），在用户态完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。但是如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源。
      自旋锁加锁失败的线程会忙等待，直到它拿到锁。这里的忙等待可以用 while 循环等待实现，不过最好是使用 CPU 提供的 PAUSE 指令来实现，可以减少循环等待时的耗电量。
      在单核 CPU 上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。其他线程就无法执行了。

        综上所述，如果被锁住的代码执行时间很短，就应该使用自旋锁；如果执行时间很长，就应该使用互斥锁。因为如果代码执行时间很短，选用了互斥锁，那么线程切换所花费的时间可能都比代码执行时间长。

        2）读写锁

        读写锁由「读锁」和「写锁」两部分构成，如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。所以，读写锁适用于能明确区分读操作和写操作的读多写少的场景。

• 读写锁工作原理
      只要没有线程持有写锁，那么其他线程就可以并发持有读锁，来读取共享资源。这样可以提高共享资源的访问效率；
      一旦有一个线程持有了写锁，那么其他线程无论是获取读锁还是获取写锁都会被阻塞。因此，任何时刻只能有一个线程持有写锁。
• 读写锁的分类
  • 读优先锁：优先服务读线程。如果有线程持有了读锁，获取写锁的进程会被阻塞，但是后续读进程仍然可以获取读锁，这样可以保证读锁被更多线程持有，提高读线程的并发能力。
                      如果一直有读线程获取读锁，那么写线程将永远获取不到写锁，这就造成了写线程饥饿的现象。
  • 写优先锁：优先服务写线程。如果有线程持有了读锁，获取写锁的进程会被阻塞，同时后续读进程获取读锁也会被阻塞，等到读锁释放，写进程就可以获取写锁了。
                      读进程可能饿死。
  • 公平读写锁：用队列把获取锁的线程进行排队，不管是写线程还是读线程都按照先进先出的原则加锁，这样读线程仍然可以并发，也不会出现「饥饿」的现象。

        3）乐观锁与悲观锁

• 什么是乐观锁与悲观锁？
      乐观锁是不管三七二十一，先改了资源再说。它全程没有加锁，所以也叫无锁编程，比如在线编辑文档、Git。
      悲观锁访问共享资源前要先上锁，比如上面提到的互斥锁、自旋锁、读写锁都是悲观锁。
• 二者的适用场景？
      乐观锁适用于多线程同时修改共享资源的概率较低，且加锁成本太高的场景。
• 乐观锁的工作方式？
      先让多线程修改完共享资源，再验证这段时间内有没有发生冲突。如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。
  • 如何验证冲突？
    一般线程在修改完共享资源后提交一个版本号，通过判断这个版本号与当前版本号是否相同，来验证有没有发生冲突。
  • 放弃后如何重试？
    放弃后如何重试，这跟业务场景息息相关，虽然重试的成本很高，但是冲突的概率足够低的话，还是可以接受的。

        主要负责内存的分配和回收，以及将逻辑地址转换成物理地址。

        简单可以分为连续分配管理方式和非连续分配管理方式这两种。

• 连续分配管理方式是指为一个用户程序分配一个连续的内存空间，比如 块式管理。
  （1）内存分块管理
          分块管理是早期操作系统的内存管理方式。将内存分为几个固定大小的块，每个块只能包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块。如果程序运行只需要很小的内存空间的话，分配的这块内存很大一部分就被浪费了，所以内存分块管理会产生内部碎片。
  
• 非连续分配管理方式允许程序使用的内存分布在离散或者不连续的内存中，比如分页管理 和 分段管理。
  （2）内存分页管理
          把用户程序的地址空间分为大小相等且固定的页，相应地，内存也按相等大小的页划分(在 Linux 下，每一页的大小为 4KB)，然后将虚拟地址与物理地址通过页表进行映射，实现内存的离散分配。
          分页管理有内部碎片(内存分页分配内存的最小单位是一页，也就是说即使进程不足一页，我们最少也只能分配它一页)无外部碎片。
  （3）内存分段管理
          内存分段是从程序的逻辑角度，分成了栈段、堆段、数据段、代码段等。每一段的大小不是固定的。 段式管理通过段表对应逻辑地址和物理地址。
          分段管理有外部碎片无内部碎片。
  （4）段页式管理
          段页式管理是分页和分段的结合，它是先将程序分段，再将每个段分页，这样段与段之间以及段的内部的内存空间都是离散的。
          段页式管理利用段表和页表实现虚拟地址和物理地址的映射。
  

        为了提高虚拟地址到物理地址的转换速度，操作系统引入了 快表。可以把快表理解为一种特殊的Cache(高速缓冲存储器)，其中的内容是页表的一部分或者全部内容。

        由于页表储存在内存中，所以采用页表做地址转换读写内存数据时 CPU 要两次访问内存。有了快表，如果能在快表中命中，就只需要访问一次cache和一次主存，这样可加速查找并提高指令执行速度。

        使用快表之后的地址转换流程：

• 根据虚拟地址中的页号查快表；
• 如果该页在快表中，直接从快表中读取相应的物理地址；
• 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
• 当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

【两次访问主存】第一次是访问内存中的页表，将虚拟地址转换成物理地址；第二次才是真正根据所得地址读写数据。

（2）多级页表

        以32位OS为例，进程的虚拟地址空间就为2^32bit(即4GB)，如果一个页面是4KB，那么一个进程就有1M(4G/4K)个页面，即页表需要1M个页表项，假设一个页表项大小是4B，那么一个页表就是4MB。这意味着每创建一个进程就需要在内存中维护4MB大小的页表，显然难以在内存中找到这么多连续的空间来存放页表。这个问题可以用多级页表来解决。

        多级页表其实就是实现页表在内存中的离散存储。以二级页表为例，第一级页表的页表项存放的是所有第二级页表的目录，第二级页表就相当于以前的一级页表。
        

        多级页表属于以时间换取空间。

（1）共同点

• 二者都属于内存的离散分配，页与页之间以及段与段之间都是离散存储的，但是页中和段中的内存是连续的。
• 二者都需要虚拟地址到物理地址的转换。

（2）区别

• 分页是为了满足OS内存管理的需求，而分段是从程序逻辑角度，分为代码段，数据段等，能够更好满足用户的需求；
• 页大小固定，由OS决定；段大小不固定，取决于当前运行的进程；
• 分页会产生内部碎片，分段会产生外部碎片。

        虚拟内存是OS内存管理的一种技术，虚拟内存是通过硬盘从逻辑上对内存空间进行扩充，让每个进程产生一种在独享主存的错觉。

        现在的CPU寻址都是虚拟寻址，也就是说需要将虚拟地址转换成物理地址才能访问内存。实现地址转换功能的是CPU中的一个硬件——内存管理单元(Memory Management Unit, MMU)。

        没有虚拟地址空间的时候，程序直接访问和操作的都是物理内存 。这意味着用户程序可以访问任意内存，寻址内存的每个字节，这样就很容易破坏操作系统，造成操作系统崩溃。同时如果想要同时运行多个程序也十分困难，因为程序A可能覆盖程序B在内存中的数据。

        在多进程环境下，为了让进程之间的内存地址相互隔离，互不影响，于是操作系统就为每个进程独立分配一套虚拟地址空间，每个进程只关心自己的虚拟地址即可。

        操作系统会将进程的虚拟地址和内存的物理地址映射起来。如果程序要访问虚拟地址的时候，由操作系统转换成对应的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

• 虚拟内存地址：程序、进程使用的地址就叫虚拟内存地址。
• 物理内存地址：真实存在于硬件里的地址空间就叫物理内存地址。

        进程的虚拟地址会通过 CPU 中的内存管理单元（MMU）的映射关系，将虚拟地址转换成物理地址，然后再通过物理地址访问内存。

        那么OS如何管理虚拟地址与物理地址之间的映射关系？

        ——主要有两种方式，分别是内存分段和内存分页。

        虚拟内存的实现建立在内存的离散分配管理的基础上。
        虚拟内存的实现有以下三种方式：

• 请求分页存储管理：基于内存的分页存储管理，增加了请求调页和页面置换功能。
          在请求分页存储管理系统中，允许用户程序只装入执行所需要的部分页面即可运行，在运行时需要哪些页面，再通过请求调页和页面置换将相应的页面调入到主存，同时也可以将暂时不用的页面置换到外存中。
• 请求分段存储管理：基于内存的分段存储管理，增加了请求调段和分段置换功能。
          请求分段储存管理方式和请求分页一样，允许程序只装入执行所需的部分段即可运行，在运行时需要哪些段，再通过请求调段和分段置换将相应的段调入到主存，同时也可以将暂时不用的段置换到外存中。
• 请求段页式存储管理：基于内存的段页式存储管理。

（6）很多人容易搞混请求分页与分页存储管理，两者有何不同呢？

        请求分页存储管理是建立在分页管理之上的。二者的根本区别是是否将程序全部所需的全部地址空间都装入主存，这也是请求分页存储管理可以提供虚拟内存的原因。请求分页存储管理不要求将作业全部地址空间同时装入主存。基于这一点，请求分页存储管理可以提供虚存，而分页存储管理却不能提供虚存。

        当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。页面置换算法就是当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。

• 最佳页面置换算法（OPT）
  置换在「未来」最长时间不被访问的页面。
  这种算法虽然很理想，但是实际上无法实现，因为我们是无法预知每个页面在「下一次」访问前的等待时间。所以最佳页面置换算法一般用来衡量算法的效率。
• 先进先出置换算法（FIFO）
  选择在内存中驻留时间很长的页面进行置换。
  
• 最近最久未使用的置换算法（LRU）
  选择最长时间没有被访问的页面进行置换，该算法认为已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
  虽然 LRU 在理论上是可以实现的，但代价很高，需要在内存中维护一个所有页面的链表，在每次访问内存时都必须要更新「整个链表」。所以 LRU 由于开销比较大，实际应用中比较少使用。
  
• 时钟页面置换算法（Lock）
  把所有的页面都保存在一个环形链表中，一个指针指向最老的页面，页面包含一个访问位，页面被访问，访问位就置为1。当发生缺页时，顺时针遍历页面，如果访问位为1，将访问位置为0，继续遍历；直到访问到访问位为0的页面，将该页面置换。
  
• 最不常用置换算法（LFU）
  记录每个页面的访问次数，选择访问次数最少的页面将其淘汰。
  实现时，既增加了硬件成本(需要一个计数器记录访问次数)，又增大了时间开销。