学习操作系统

tech os
八股
发布日期:   2022-11-18
更新日期:   2023-04-08
文章字数:   16.5k
阅读次数:  

计算机硬件结构

冯诺依曼模型

1945年，冯诺依曼等人在图灵机的基础上，提出使用电子元件构造计算机，并约定了使用二进制进行存储和计算。将计算机的基本结构定义为五个部分，运算器，控制器，存储器，输入设备和输出设备。这种计算机结构被称为冯诺依曼结构。

冯诺依曼结构

运算器和控制器在cpu中，存储器就是我们常说的内存，输入设备和输出设备是计算机外接的设备。

内存

程序和数据都存放在内存中，存储的区域是线性的。在计算机中，存储数据的基本单位是字节(byte)，一个字节由8个二进制位组成。内存的地址是从0开始的，每个字节对应一个内存地址，每个内存地址对应内存中的一个字节。
内存中的地址从0开始编号，自增直到最后一个地址为内存的总字节数-1。

cpu

cpu是计算机的核心，负责执行程序。cpu分为32位和64位。主要区别在于，一次能计算多少字节数据。32位cpu一次能计算4个字节(4x8=32个二进制位)，64位cpu一次能计算8个字节(8x8=64个二进制位)。32位和64位又称为cpu的位宽。将cpu设计成多位的，可以计算大数。32位的cpu能计算的最大数值为$2^{32}-1$，64位的cpu能计算的最大数值为$2^{64}-1$。

cpu的组件主要有，寄存器，控制单元和逻辑运算单元。控制单元负责控制cpu的工作，逻辑运算单元负责运算，寄存器分为多种种类，每种寄存器的功能不尽相同。

  • 通用寄存器：用来储存需要进行运算的数据
  • 程序计数器：用来储存cpu要执行的下一条指令的内存地址
  • 指令寄存器：用来存放现在正在执行的指令

此时，我们已经了解到计算机的三种存储器，寄存器，cpu cache，内存和硬盘。寄存器和cpu cache都是cpu内部的存储器，寄存器的速度比cpu cache快，但是寄存器的容量比cpu cache小。寄存器的容量一般为几十个字节，cpu cache的容量一般为几十兆字节。内存和硬盘是cpu之外的存储器，内存的访问速度比硬盘快10-1000倍。

计算机的存储结构

总线

总线是计算机中连接各个部件的通道。总线的宽度决定了cpu一次能传输多少数据。总线的宽度越大，cpu一次能传输的数据就越多，cpu的性能就越好。

总线可分为三种，数据总线，地址总线和控制总线。

  • 地址总线：用于传输cpu将要操作的内存地址
  • 数据总线：用于读写内存中的数据
  • 控制总线：用于发送和接收信号，比如中断，设备复位等

cpu在读写内存中的数据时，首先会通过地址总线指定内存的地址，然后通过控制总线控制是读还是写，最后通过数据总线来传输数据。

输入输出设备

输入输出设备是计算机和外界进行交互的接口。输入设备是将外界的信息输入到计算机中，输出设备是将计算机中的信息输出到外界。

中断和软中断

中断是cpu在执行指令时，发生了某种事件，cpu会暂停当前的指令，转而去执行中断处理程序。中断的事件有很多种，比如时钟中断，键盘中断，鼠标中断等等。中断的处理程序是由操作系统提供的。
操作系统在处理中断时应该尽可能快的执行完，这样可以减少对正常进程运行调度的影响。中断程序在相应中断时，可能还会临时关闭中断，这就导致，在当前的中断处理程序执行完之前，系统中的其他中断程序无法被响应，导致中断可能会丢失（一种形象的类比是由于电话占线而漏接电话），所以中断程序应该尽可能的短且快。

Linux系统为了解决中断丢失的问题，将中断过程分成了两个阶段，上半部分用来快速处理中断，主要负责处理跟硬件紧密相关或者时间敏感的事情，下半部分延迟处理上半部未完成的工作，一般以内核线程的方式进行运行。
上半部直接处理硬件请求，也就是硬中断，主要负责耗时短的工作。下半部由操作系统自己触发，也就是软中断，用于处理上半部未完成的工作，特点是延时执行。

中断（上半部）是会打断 CPU 正在执行的任务，然后立即执行中断处理程序，而软中断（下半部）是以内核线程的方式执行，并且每一个 CPU 都对应一个软中断内核线程。不过，软中断不只是包括硬件设备中断处理程序的下半部，一些内核自定义事件也属于软中断，比如内核调度等、RCU锁（内核里常用的一种锁）等。

操作系统启动

以linux0.11为例：
操作系统在启动时，首先要将磁盘上的操作系统加载到内存中，即著名的bootsect.s所做的任务。

  • 分段将操作系统的代码读入，setup.s和system
  • 调用1ah=0x13中断将存在es:bp寄存器的字符串打印在串口屏幕，只要在使用中断时，将输入设定好即可
  • 确定根设备号和驱动设备号

在完成这些任务之后，bootsect.s将跳转到setup.s的第一条指令，将控制权交给setup.s，

  • 取出光标位置和其他的硬件参数，放在0x90000处
  • 获取扩展内存的大小，即1M以外的其他内存空间，放在0x90002处
  • 将system模块移到0x10000处

setup.s在完成了上边的任务之后，执行jmpi 0, 8，从实模式进入保护模式。这时，寻址的方式发生了变化。之前实模式下的寻址cs << 4 + ip变成了保护模式下的寻址，根据cs查gdt表(在setup.s中初始化)再加上ip。中断处理也发生了变化，保护模式下，中断处理函数的入口被放在idt表中，而不是之前在实模式下通过中断向量表来寻找中断程序的入口地址。

system模块中的第一部分代码是head.s，这段代码在保护模式下运行。这段代码建立了idt表和gdt表，(虽然在上一步setup.s中已经建立过gdt表，但那是为了执行jmpi 0, 8而设置的，因此在这里还需要再创建一次)并进行了一些其他的初始化(设置页表、填写页表)。在完成自己的任务之后，将跳转到main.c代码中。main.c的工作是初始化各种硬件，以及mem_map(mem_init)等重要的数据结构。完成初始化之后，操作系统开始运转，进入内核态，进入shell。

操作系统启动

#define EXT_MEM_K = (*(unsigned short *)0x90000)

void main(void) {
    // 结束地址是由0x90002 处取出的内容决定
    long memory_end = 1 « 20 + EXT_MEM_K « 10;
    // 而一页的大小操作系统就设为 4K，当不足 1 页的内存就丢弃。
    memory_end &= 0xfffff000;
    // 此处的起始地址为 4M，这是因为 0 - 1M 交给了系统内核 system，1M - 4M 将交给磁盘高速缓存，所以 4M 以后的内存才是让用户应用程序使用的
    long memory_start = 4*1024*1024;
    // mem_init() 的两个参数是要管理的起始内存地址和结束内存地址
    mem_init(memory_start, memory_end); // 初始化mem_map

    hd_init(); // 硬盘初始化 

    ······

    sti()
    move_to_user_mode();
    // init() 会启动一个 shell，就是命令窗口
    if (!fork()) { init();}
    for(;;) { pause();}
}

进程和线程

cpu管理的直观想法

最简单的使用cpu的方法就是给pc设置一个初值，然后让cpu取址执行下去。但是，一些指令比如io指令执行时间长，且并不占用cpu，这时候cpu就会空闲下来，导致cpu的利用率低。
一种直观的改善方法是，设置多道程序交替执行。这样，当一个程序执行io指令时，cpu就会执行另一个程序，这样就能提高cpu的利用率。怎么做到呢？不仅需要在切换程序的时候修改pc的值，还需要保存当前程序的状态，以便下次切换回来时，能够恢复程序的状态。这就引出了pcb(process control block)的概念，pcb是一个数据结构，用来保存程序的状态。
同时，也引出了进程的概念，进程就是一个运行中的程序。

为什么要进行进程的切换？

对于一个支持多进程的系统，单核的cpu会从一个进程快速的切换到另一个进程，这样就产生了一种并行的错觉，但是，事实上单核的cpu只能执行一个进程，实际上这是并发而不是并行。

多进程图像

多进程图像是一个抽象的概念，它是一个进程的集合。

多进程的组织是怎么样的？有一个进程在执行，一些进程在等待执行，有一些进程在等待某事件。为了管理这些进程的状态，引入了就绪态，运行态，阻塞态的概念。除了这三种状态之外，再加上新建态和终止态，这就是进程的五种基本状态，这五种基本状态完整的描述了一个进程的生命周期。

多进程是如何交替的？依赖于schedule函数。schedule函数是一个函数，它的作用是选择一个进程，让cpu执行这个进程。schedule函数的选择过程是怎么样的？有两种选择方式，一种是抢占式，一种是非抢占式。抢占式是指，当一个进程执行的时候，如果有更高优先级的进程需要执行，那么就会抢占当前进程，让更高优先级的进程执行。非抢占式是指，当一个进程执行的时候，如果有更高优先级的进程需要执行，那么就会等待当前进程执行完毕，再执行更高优先级的进程。

多进程如何互相影响？进程之间切换时，可能会导致不同的进程同时修改同一个内存地址，这样就导致进程的执行乱套了，为了避免这种状况，我们对每一个进程都设置一个单独的映射，使相同的虚拟地址对应到不同的物理地址。多进程是怎么合作的？核心的想法在于进程同步，确定一个合理的推进顺序，实现方法是给进程上锁。

进程的基本知识

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

进程的状态

进程的几种状态 意义
运行态 进程此时处于运行态，表示进程此时正占用cpu
就绪态 进程此时可运行，但是由于其他进程处于运行态而暂时的停止运行
阻塞态 进程此时正在等待另一事件的发生，如等待输入输出操作的完成，此时，即使cpu空闲此进程也不能运行
创建状态 进程正在被创建的状态
结束状态 进程正在从系统中消失时的状态

进程的三种主要状态

如果大量的进程都处于阻塞状态，这些在阻塞态的进程将占用大量的物理内存空间，根据我们上文所说的，cpu附近的内存空间寸土寸金，阻塞态占用大量的内存空间显然是一种浪费物理内存的行为。为了避免大量物理内存的浪费，通常会把阻塞状态的进程的物理内存空间换到硬盘中，等进程再次被运行时，再从硬盘换入物理内存中。

当进程没有实际占用物理内存空间时，我们称这种状态为 挂起状态。
挂起状态可以分为两种，阻塞挂起状态和就绪挂起状态。阻塞挂起状态是指，进程在硬盘中等待某个事件的发生。就绪挂起状态是指，进程在硬盘中等待被调度，只要进入内存就能立刻被执行。

进程的状态变迁

进程的控制结构

上文提到过，在操作系统中通过pcb来控制进程。
pcb是进程存在的唯一标识。在pcb中包含了进程的各种信息：

  • 进程描述信息
    • 进程标识符：用于标识各个进程，每个进程都有唯一的标识符
    • 用户标识符：用于标识进程的所有者

  • 进程控制和管理信息

    • 进程当前的状态：创建态，结束态，就绪态，运行态，阻塞态
    • 进程优先级：用于调度进程的优先级

  • 资源分配清单

    • 进程的内存分配情况，打开的文件列表和所使用的I/O设备信息等等

  • cpu相关的信息

    • cpu中各个寄存器的值，当进程被切换时，需要保存进程的cpu相关信息，以便下次切换回来时，能够恢复进程的运行状态

pcb通过链表的方式进行组织，操作系统将状态相同的进程的pcb连在一块组成各种队列。比如，就绪队列，阻塞队列，挂起队列等等。

进程的控制

进程是如何被创建，终止，阻塞和唤醒的？

01 创建进程

操作系统允许一个进程创建另一个进程，且允许子进程继承父进程所拥有的资源。
操作系统创建一个进程的步骤为：

  • 申请一个空白的pcb，并向pcb中填写一些控制和管理进程相关的信息，比如进程的唯一标识等
  • 为该进程分配运行所需的内存资源等
  • 将创建的pcb插入就绪队列中，等待被调度
02 终止进程

进程的终止是指进程的执行结束，进程的pcb被释放，进程所占用的资源被回收。
进程的终止有三种方式，正常终止，异常终止和被动终止(被用户手动的kill掉)。
当子进程被终止时，其继承的父进程的资源应当全部还给父进程，当父进程被终止时，其名下的子进程变成了孤儿进程，由1号进程（init进程）对他们进行状态收集工作（收养）。
终止进程时，操作系统会进行以下步骤：

  • 查找要释放的进程的pcb，
  • 若该进程还处于执行状态，则立刻停止该进程的执行，将cpu资源分配给其他进程，
  • 若该进程还有子进程，则将其子进程交给1号进程进行接管，
  • 将该进程所占用的所有资源交还给操作系统，
  • 将该进程的pcb从所在的队列中删除。

为什么要收养孤儿进程？
任何一个子进程(init除外)在exit()之后，并非马上就消失掉，而是留下一个称为僵尸进程(Zombie)的数据结构，等待父进程处理。这是每个子进程在结束时都要经过的阶段。如果子进程在exit()之后，父进程没有来得及处理，这时用ps命令就能看到子进程的状态是Z。如果父进程能及时处理，可能用ps命令就来不及看到子进程的僵尸状态，但这并不等于子进程不经过僵尸状态。如果父进程在子进程结束之前退出，则子进程将由init接管。init将会以父进程的身份对僵尸状态的子进程进行处理。
孤儿进程的父进程已经被终止，但是，父进程还没有调用wait获取子进程的状态信息，孤儿进程的信息不能被处理，这些孤儿进程的进程标识符等信息将一直被保存在操作系统中，变成了僵尸进程，导致操作系统的空间被浪费，因此，必须对孤儿进程进行收养。init进程会循环地wait它的已经退出的子进程，避免僵尸进程对操作系统的危害。

03 阻塞进程

当进程需要等待另一事件完成时，可以调用阻塞语句将自己置于阻塞状态。一个处于阻塞态的进程只能被另一进程唤醒。
阻塞进程时，操作系统会进行以下步骤：

  • 查找要阻塞的进程标识号对应的pcb，
  • 若该进程处于运行状态，则保护其现场，将其状态转换为阻塞态，停止运行，
  • 将该进程对应的pcb从原队列中删除，加入阻塞队列中。
04 唤醒进程

进程由运行态转变为阻塞态时由于进程必须等待某一事件的完成，因此，进程必须等待另一进程的唤醒。当另一进程完成了事件后，会调用唤醒语句将阻塞进程唤醒。处于阻塞状态的进程绝对不可能自己叫醒自己。
唤醒进程时，操作系统会进行以下步骤：

  • 查找要唤醒的进程标识号对应的pcb，
  • 将其从阻塞队列中移出，并将其状态置为就绪态，
  • 将其插入到就绪队列中，等待调度。

线程的基本知识

在早期的操作系统中，进程就是调度的最基本单元，随着操作系统的发展，提出了更小的能独立运行的基本单位，也就是线程。

为什么要使用线程？

对于一些任务，如果我们使用单进程进行运行，各个函数之间不能并发的执行，导致资源利用效率低下。若使用多进程的方式，可以提高资源的利用效率，但是又带来了新的问题，进程之间如何相互通信？如何共享数据？维护这么多的进程又要消耗大量的资源。
为了解决这些问题，我们设计了一种新的实体供操作系统进行调度，即线程。线程具有以下特点：

  • 线程之间可以并发的运行
  • 线程之间可以共享相同的地址空间

线程的定义

线程是进程中的一条执行流程。
同一进程中的多个线程之间可以共享代码块，数据段和打开的文件等资源，以节省维护很多进程对应的pcb所需要的物理内存空间，但是每个线程都有自己独立的一套寄存器和栈，确保线程的控制流时相对独立的，从而使得线程可以被操作系统调度。

使用线程的优点：

  • 一个进程中可以同时并发多个线程
  • 各个线程之间可以同步执行
  • 各个线程之间可以共享地址空间和文件等资源
    使用线程的缺点：
  • 进程中的一个线程崩溃时，会导致该线程所属的进程的所有线程崩溃。这并非不可避免的，在java编程中，线程的崩溃不会导致进程的崩溃。

线程的实现

线程的实现有三种不同的思路：

  • 用户级线程：在用户空间中实现，由用户态的线程库管理的线程
  • 内核级线程：在内核中实现，由内核管理的线程
  • 轻量级进程：又称混合型线程，在内核中支持用户级线程

目前通常将几种不同的线程实现思路结合起来使用，既提供核心线程供smp系统使用，也提供线程库在用户态中实现另一套线程机制，供用户使用。

内核级线程：内核级线程只运行在内核态，不受用户态的影响，在上下文切换时不涉及到内核态和用户态的切换。唯一使用的资源时内核栈和上下文切换时保存寄存器的空间，资源消耗量小。

内核级线程的模型，一个用户线程对应一个内核线程

  • 内核级线程的优点：
    1. 在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行。
    2. 分配给线程，多线程的进程获得更多的 CPU 运行时间。
  • 内核级线程的缺点：
    1. 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB。
    2. 线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大。

用户级线程：用户级线程完全建立在用户空间的线程库之上，用户线程的创建，调度，同步和结束全都在用户态之下完成，不需要内核的帮助，因此用户级线程是低消耗且高效的。

用户级线程的模型，多个用户线程对应一个内核线程

  • 用户级线程的优点：
    1. 每个进程都需要有它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统。
    2. 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快。
  • 用户级线程的缺点：
    1. 由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了。
    2. 当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的。
    3. 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢。

轻量级进程：轻量级进程是建立在内核之上并由内核支持的 用户线程，是内核线程的高度抽象，每一个轻量级进程都与一个特定的内核级线程关联，内核线程只能由内核管理并像普通的进程一样被调度。轻量级进程的创建通过系统调用完成，与父进程共享进程地址空间和系统资源。像普通的进程一样被调用，但是相比于普通的进程，轻量级进程只有一个最小的执行上下文和调度程序所需的统计信息。而相比于普通的用户线程，轻量级进程与内核线程相关联，可以像独立的进程一样拥有中断。

轻量级进程

  • 使用轻量级进程的优点：
    1. 由于本质是用户线程：故轻量级进程可以共享诸如地址空间，打开的文件等，只要其中一个修改共享资源，另一个就立即查看这种修改。
    2. 由于与内核进程相关联：所以每个LWP都可以作为独立单元由Kernel独立调度，同时由于内核线程位于Kernel，而Kernel正是所有资源的管理者，这也LWP也就可以像独立进程一样享有专门的中断。
  • 使用轻量级进程的缺点：
    1. 大多数LWP的操作，如建立、析构以及同步，都需要进行系统调用。系统调用的代价相对较高：需要在user mode和kernel mode中切换。
    2. 每个LWP都需要有一个内核线程支持，因此LWP要消耗内核资源（内核线程的栈空间）。因此一个系统不能支持大量的LWP。

在linux中，没有真正的线程，linux中所有的线程都是使用轻量级进程和进程模拟实现的。

进程、线程和协程的区别和联系

进程 线程 协程
定义 资源分配和拥有的基本单位 程序执行的基本单位 用户态的轻量级线程，线程内部调度的基本单位
切换情况 进程CPU环境(栈、寄存器、页表和文件句柄等)的保存以及新调度的进程CPU环境的设置 保存和设置程序计数器、少量寄存器和栈的内容 先将寄存器上下文和栈保存，等切换回来的时候再进行恢复
切换者 操作系统 操作系统 用户
切换过程 用户态->内核态->用户态 用户态->内核态->用户态 用户态(没有陷入内核)
调用栈 内核栈 内核栈 用户栈
拥有资源 CPU资源、内存资源、文件资源和句柄等 程序计数器、寄存器、栈和状态字 拥有自己的寄存器上下文和栈
并发性 不同进程之间切换实现并发，各自占有CPU实现并行 一个进程内部的多个线程并发执行 同一时间只能执行一个协程，而其他协程处于休眠状态，适合对任务进行分时处理
系统开销 切换虚拟地址空间，切换内核栈和硬件上下文，CPU高速缓存失效、页表切换，开销很大 切换时只需保存和设置少量寄存器内容，因此开销很小 直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快
通信方面 进程间通信需要借助操作系统 线程间可以直接读写进程数据段(如全局变量)来进行通信 共享内存、消息队列

1、进程是资源调度的基本单位，运行一个可执行程序会创建一个或多个进程，进程就是运行起来的可执行程序

2、线程是程序执行的基本单位，是轻量级的进程。每个进程中都有唯一的主线程，且只能有一个，主线程和进程是相互依存的关系，主线程结束进程也会结束。多提一句：协程是用户态的轻量级线程，线程内部调度的基本单位

cpu调度

直观的想法：FIFO，先来先服务。Piority，优先级，任务短的可以适当优先。RR，时间片轮转。

调度的五个原则

调度有五个原则：

  1. CPU利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
  2. 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
  3. 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
  4. 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
  5. 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

考虑到任务的特点，将任务分为前台任务和后台任务，前台任务使用时间片轮转进行调度，后台任务使用最短作业优先进行调度，前台任务和后台任务之间使用优先级进行调度。

一个实际的schedule()函数

linux0.11中的schedule函数如下所示：

void schedule(void)
{
         int i,next,c;
         struct task_struct ** p;
 
/* check alarm, wake up any interruptible tasks that havegot a signal */
         for(p= &LAST_TASK ; p> &FIRST_TASK ; --p)
                   if (*p) {
                            if ((*p)->alarm &&(*p)->alarm< jiffies) {
                                               (*p)->signal|= (1<<(SIGALRM-1));
                                               (*p)->alarm =0;
                                     }
                            if (((*p)->signal& ~(_BLOCKABLE & (*p)->blocked))&&
                            (*p)->state==TASK_INTERRUPTIBLE)
                                     (*p)->state=TASK_RUNNING;
                   }
/* this is the scheduler proper: */
         while (1) {
                   c = -1;
                   next = 0;
                   i = NR_TASKS;
                   p = &task[NR_TASKS];
                   while (--i) {
                            if (!*--p)
                                     continue;
                            if ((*p)->state ==TASK_RUNNING && (*p)->counter> c) // 找到状态就绪且counter最大的任务，counter同时实现了时间片轮转和优先级调度
                                     c = (*p)->counter, next =i;
                   }
                   if (c) break;
                   for(p = &LAST_TASK; p > &FIRST_TASK; --p)
                            if (*p)
                                     (*p)->counter= ((*p)->counter>> 1) +
                                                        (*p)->priority;
         }
         switch_to(next);
}

counter代表的优先级在不断的动态调整。
counter保证了响应时间的界。$c(t)=\frac{c(t-1)}{2} + p,c(0) = p$是一个几何级数，且一定收敛，这也是为什么降低counter一定是除以一个数而不是减去一个数的原因。
经过IO之后，counter会变大，IO时间越长，counter就越大，变相的照顾了前台的进程。
后台进程一直按照counter的大小进行轮转，近似了sjf调度。

进程间通信机制

每个进程的用户地址空间都是相对独立的，不能互相访问。但是内核空间是每个进程共享的，因此进程之间的通信必须通过内核。
Linux的内核提供了一些进程间通信的机制，管道，消息队列，共享内存，socket，信号量和信号。

管道

linux中提供了匿名管道和命名管道。最常见的管道就是|，他是一个匿名管道：

ps aux | grep python 
# 这是一条很常见的命令，首先使用ps aux命令将所有进程的信息输出到标准输出，
# 然后使用管道将标准输出作为grep python的标准输入，
# grep python命令将标准输入中包含python的行输出到标准输出。

匿名管道在使用完之后就被销毁。在linux中，命名管道是一个文件，可以在不同的进程之间进行通信。

mkfifo mypipe # 创建一个命名管道，命名为mypipe，此时，多了一个名为mypipe的文件，使用ls -l可以看到其类型为p，即pipe，管道。

echo "hello" > mypipe # 将hello写入管道，此时，管道中的内容为hello

cat < mypipe # 从管道中读取内容，此时，管道中的内容为空

# 在mypipe中的内容被读取之前，echo "hello" > mypipe 不会退出。

管道这种通信方式效率低，不适合进程间频繁地交换数据。但是，管道的使用很简单，同时也我们很容易得知管道里的数据已经被另一个进程读取了。

匿名管道的创建使用系统调用int pipe(int fd[2])，fd[0]是读端，fd[1]是写端。命名管道的创建使用系统调用int mkfifo(const char *pathname, mode_t mode)，pathname是管道的名字，mode是管道的权限。匿名管道只存在于内存中，命名管道存在于文件系统中。

所谓的管道，就是操作系统内核中的一串缓存。从管道的一端写入的数据实际上缓存在内核中，另一端读取时，直接从内核中读取这段数据，因此管道的大小是受限的。且管道传输的数据事实上是无格式的流。

  • fd[0]是读端，fd[1]是写端，对于匿名管道，两个描述符都在同一个进程中，那么匿名管道是如何跨过两个进程，实现进程之间的通信的？
    一般的做法是，fork一个子进程，子进程继承父进程的所有文件描述符，因此，子进程也有了管道的读写端。这样，父子进程之间都可以通过各自的fd写入和读取同一个管道文件，实现跨进程通信。
    事实上，父子进程同时读写管道很容易造成混乱，为了避免这种混乱的出现，通常的做法是父进程只写，子进程只读，或者父进程只读，子进程只写。这样只能实现单向通信，如果要实现双向通信，就需要使用两个管道。

匿名管道实现进程间的通信

对于匿名管道，他的通信范围是存在于父子关系之间的进程。由于没有实体，只能通过fork父进程来实现进程之间的通信。
对于命名管道，可以在不相关的进程间相互通信。命名管道提前创建了一个文件，这个文件就是管道，因此，命名管道的通信范围是整个文件系统。

消息队列

使用管道从A进程向B进程发送消息时，只有B进程将管道中的信息读取完之后才能A进程才能正常的退出。因此，使用管道是效率低的，不适合进程间频繁地交换数据。

使用消息队列的通信模式可以解决这个问题。消息队列本质上是一个保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体。消息体是用户自定义的数据类型，消息的接收方和发送方要约定好消息体的数据类型。所以每个消息体都是固定大小的存储块，而不是管道中的无格式的字节流数据。若进程从消息队列中读取了消息体，内核会将这个消息体从消息队列中删除。

消息队列的生命周期由内核决定，若没有主动的释放消息队列或者关闭操作系统，消息队列会一直存在，而匿名管道的生命周期由进程决定，随着进程的创建而建立，当管道中的数据被读取之后就销毁。

使用消息队列的不足之处：

  1. 通信不及时
  2. 消息体的大小有限制，不适合比较大数据的传输。在内核中，每个消息体都会有一个最长长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限的。在linux内核中，有两个宏定义，MSGMAX和MSGMNB，他们以字节为单位，分别表示消息体的最大长度和消息队列的最大长度。
  3. 使用消息队列进行通信时，存在从内核态到用户态之间的数据拷贝开销，因为消息队列存在于内核中，进程写入数据到内核中的消息队列时，会发生用户态拷贝数据到内核态的过程，同样的进程从消息队列中读取数据时，也会发生从内核态拷贝数据到用户态的过程。

共享内存

使用消息队列进行通信时，通信往往是不及时的，且频繁的发生从内核态拷贝到用户态和从用户态拷贝到内核态的过程，导致额外的开销。因此，使用共享内存进行通信是一种更高效的方式。

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

共享内存的实现方式是，将一段物理内存映射到不同进程的虚拟内存中，这样不同进程就可以访问同一段物理内存，从而实现数据的共享。

共享内存

信号量

使用共享内存的通信方式，实现了不同进程对同一物理内存地址的修改。但是若多个进程同时对同一内容进行修改，很可能会发生冲突。为了防止多进程竞争共享资源而造成的数据错乱，需要保护机制，使得共享的资源在任意时刻只能被一个进程访问。这种保护机制可以使用信号量来实现。

信号量是一个整型的计数器，主要用于实现进程间的互斥和同步，实际上并不直接传递数据。信号量的大小表示资源的数量，控制信号量有两种操作：

  1. P操作，这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
  2. V 操作，这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程。

将信号量的值初始化为1，代表互斥信号量，可以保证共享内存在任一时刻只能被一个进程访问。

互斥信号量

具体的过程为：

  1. 进程 A 在访问共享内存前，先执行了 P 操作，由于信号量的初始值为 1，故在进程 A 执行 P 操作后信号量变为 0，表示共享资源可用，于是进程 A 就可以访问共享内存。
  2. 若此时，进程 B 也想访问共享内存，执行了 P 操作，结果信号量变为了 -1，这就意味着临界资源已被占用，因此进程 B 被阻塞。
  3. 直到进程 A 访问完共享内存，才会执行 V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执行 V 操作，使信号量恢复到初始值 1。

信号量不仅可以是互斥信号量，当信号量的值初始化0时，代表同步信号量，确保进程执行的顺序。

同步信号量

具体的过程为：

  1. 如果进程 B 比进程 A 先执行了，那么执行到 P 操作时，由于信号量初始值为 0，故信号量会变为 -1，表示进程 A 还没生产数据，于是进程 B 就阻塞等待；
  2. 接着，当进程 A 生产完数据后，执行了 V 操作，就会使得信号量变为 0，于是就会唤醒阻塞在 P 操作的进程 B；
  3. 最后，进程 B 被唤醒后，意味着进程 A 已经生产了数据，于是进程 B 就可以正常读取数据了。

信号

信号是进程间通信机制中唯一的一种异步通信机制。可以在任何一个时刻发送信号给一个进程，一旦有信号产生，进程就将对信号做出处理。
用户进程对信号的处理方式有：

  1. 执行默认的操作。
  2. 忽略信号，当我们不希望处理某些信号时，可以忽略该信号，不做任何处理。SIGKILL 和 SIGSTOP 信号不能被忽略。
  3. 捕捉信号，将信号定义为一个信号处理函数，在信号发生时，执行相应的信号处理函数

linux中的信号：使用kill -l命令可以查看linux中的信号。

$ kill -l
 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

socket

在同一主机中的进程间通信，可以使用管道、信号量、信号、共享内存等方式，但是在不同主机中的进程间通信，就需要使用网络通信了。网络通信的基础是 socket，socket 是一种通信机制，它可以让不同主机上的进程进行通信。

创建socket的系统调用为：

int socket(int domain, int type, int protocol);
/* domain 为协议族，AF_INET 为 IPv4 协议族, AF_INET6 为 IPv6 协议族, AF_UNIX 为本地通信协议族*/
/* type 为套接字类型，指定通信的类型，SOCK_STREAM 为字节流套接字，对应TCP，SOCK_DGRAM
为数据报套接字，对应UDP*/
/*protocol 为协议，现已被忽略，一般指定为0即可*/

关于socket编程具体的内容在计算机网络中介绍。

线程互斥与同步

在单核的cpu系统中，为了实现多个程序同时运行的假象，操作系统常常以时间片轮转的方式进行调度，让每个线程都执行一个时间片，时间片用完之后就切换到下一个进程进行，由于时间片的时间很短，就会有一种很多线程在并发运行的假象。

多个线程同时操作一个变量时；若此时在执行过程中发生了上下文切换，很可能会使执行的顺序出现问题，这时，我们是有概率得到错误的结果的。

互斥

为什么要有互斥的概念？
在多线程执行操作共享变量的一段代码时，可能会导致竞争状态。这样一个访问共用资源的程序片段，我们称为临界区。共用资源又有无法被多个线程同时访问的特性。这样就引入了互斥的概念，我们希望这段代码是互斥的：当有线程进入临界区时，其他线程必须等待。即，临界区的代码执行时，最多只能出现一个线程。

基于临界区控制的交互作用是比较简单的，只需要一个进程/线程进入了临界区，其他试图进入临界区的进程/线程都会被阻塞着，直到第一个进程/线程离开了临界区。

临界区的代码执行时只能出现一个线程

同步

在多线程中，每个线程不一定是顺序执行的，但是，我们又需要线程之间可以密切合作，以实现一个共同的任务。
为了实现这种需求，提出了同步的概念：并发线程在一些关键点上需要互相等待或者互通消息，这种相互制约的等待与互通消息称为线程同步。

同步操作即，操作A应该在操作B之前执行，操作C必须在操作A和B都执行完成之后再执行，强调执行的先后顺序。
互斥操作即，操作A和操作B不能同时执行，并不要求执行的先后顺序。

互斥与同步的实现和使用

为了实现线程进程之间的正确协作，操作系统提供实现进程协作的措施和方法，主要的方法有两种：

  • 锁：加锁解锁操作
  • 信号量：PV操作

信号量和锁都可以实现线程/进程之间的互斥，但是，信号量可以实现更加复杂的同步操作。

锁

通过加锁和解锁的操作，可以解决并发线程/进程之间的互斥问题。

具体的操作是，对于任意想进入临界区的线程，必须先进行加锁操作，若加锁操作顺利通过，则线程可以进入临界区，在完成对临界资源的访问之后再执行解锁操作，以释放该临界资源。

根据锁的不同实现方式，可以分为 忙等待锁 和 无忙等待锁。

  • 忙等待锁

忙等待锁的实现基于一组特殊原子操作指令——测试和置位指令(test and set)。Test-and-Set指令的伪码如下所示：

int TestAndSet(int *old_ptr, int new) {
  int old = *old_ptr;
  *old_ptr = new;
  return old;
}

原子操作就是要么全部不执行，要么全部执行，执行了之后无法被打断的操作，这组指令完成了这些工作：

  1. 将old_ptr地址内保存的内容更新为new;
  2. 返回old_ptr中的旧值。

这条原子操作指令同时完成了测试旧值和设置新值的工作，所以这条指令叫做 测试并设置。

可以使用Test-and-Set指令实现 忙等待锁：

typedef struct lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    lock->flag = 0; 
    // 初始化锁，将锁置为0，解锁状态。 
}

void lock(lock_t *lock) {
    while(TestAndSet(&(lock->flag), 1) == 1)
    ; // wait and do nothing
  // 当线程想要进入临界区时，对临界区的锁进行检查，并将临界区的锁置为锁定状态，等待，
  // 直到上一个访问临界区的线程退出，将临界区的锁置为0，这时继续向下进行，并再次锁定临界区
}

void unlock(lock_t *lock) {
    lock->flag = 0;
    // 将锁置为0，解锁状态
}

当要访问的临界区被锁时，线程就被困在while循环中，不做任何事情，因此这种锁被称为忙等待锁，也成为自旋锁。

这是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

  • 无忙等待锁

无忙等待锁，顾名思义就是在获取不到锁时，不自旋，而是将获取不到锁的线程放在等待队列中，将cpu资源让给其他的线程。

一种无忙等待锁的伪码如下所示：

typedef struct lock_t {
    int flag;
    queue_t *q;
} lock_t;

void init(lock_t *lock) {
    lock->flag = 0; // 将锁置为可获取状态
    queue_init(lock->q); // 初始化等待队列
}

void lock(lock_t *lock) {
    while(TestAndSet(&(lock->flag), 1) == 1) {
      /*
      1. 保存现在运行进程的tcb，
      2. 将现在运行的进程的tcb插入等待队列中，
      3. 将当前运行的线程设置为等待状态，
      4. 调度其他能使用cpu的线程。
      */
    }
}

void unlock(lock_t *lock) {
    if(lock->q != NULL) {
      /*
      1. 移出队列中的第一个线程，
      2. 将该线程的tcb插入到就绪队列，
      3. 设置该线程为就绪状态。
      */
    }
    lock->flag = 0;
}
信号量

信号量是操作系统提供的一种协调共享资源访问的方法。

信号量就是资源的数量，对应的变量通常是一个整型变量。

在操作系统中，提供了两种原子操作对信号量进行控制：

  • P 操作：对信号量进行减 1 操作，如果sem < 0，那么就阻塞当前线程。
  • V 操作：对信号量进行加 1 操作，如果 sem <= 0 ，那么就唤醒一个线程。

为什么V操作在sem <= 0时唤醒一个线程？
V操作和P操作都是成对出现的，当执行V操作时说明有一个线程已经执行完了临界区的代码，而此时，sem <= 0，说明还有线程在等这个刚刚被释放出来的资源，那么就会唤醒一个线程。

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

下边是信号量和P、V操作的伪码：

typedef struct sem_t {
    int value;  // 资源数量
    queue_t *q; // 等待队列
} sem_t;

void init(sem_t *sem, int value) {
    sem->value = value;
    queue_init(sem->q);
}

void P(sem_t *sem) {
    sem->value--;
    if(sem->value < 0) {
        /*
        1. 保存现在运行进程的tcb，
        2. 将现在运行的进程的tcb插入等待队列中，
        3. 将当前运行的线程设置为等待状态，
        4. 调度其他能使用cpu的线程。
        */
    }
}

void V(sem_t *sem) {
    sem->value++;
    if(sem->value <= 0) {
        /*
        1. 移出队列中的第一个线程，
        2. 将该线程的tcb插入到就绪队列，
        3. 设置该线程为就绪状态。
        */
    }
}

P操作和V操作是怎样使用的？

实现互斥访问控制

将信号量的初值设置为1，并将临界区的代码放在P和V之间时，可以实现临界区的互斥访问控制。

使用信号量实现互斥访问控制

此时，任何想进入临界区的线程，必先在互斥信号量上执行 P 操作，在完成对临界资源的访问后再执行 V 操作。由于互斥信号量的初始值为 1，故在第一个线程执行 P 操作后 s 值变为 0，表示临界资源为空闲，可分配给该线程，使之进入临界区。

若此时又有第二个线程想进入临界区，也应先执行 P 操作，结果使 s 变为负值，这就意味着临界资源已被占用，因此，第二个线程被阻塞。

并且，直到第一个线程执行 V 操作，释放临界资源而恢复 s 值为 0 后，才唤醒第二个线程，使之进入临界区，待它完成临界资源的访问后，又执行 V 操作，使 s 恢复到初始值 1。

实现事件同步控制

为了说明问题，我们假设两个需要进行同步控制的线程。

  • 儿子线程：儿子肚子饿了就要吃饭，叫妈妈早点做饭，妈妈做好饭之后，儿子可以开始吃饭
  • 妈妈线程：儿子肚子饿了就开始做饭，做完饭之后叫儿子吃饭

儿子线程和妈妈线程

当儿子饿了时，妈妈才开始做饭，当妈妈做好饭了，儿子才开始吃饭。

一种使用信号量的方式实现上述事件关系的伪码是：

semaphore s1 = 0; // 表示还不饿
semaphore s2 = 0; // 表示还没做好饭

void son() {
    while(1) {
        V(s1); // 叫妈妈做饭
        P(s2); // 等待妈妈做好饭
        eat(); // 吃饭
    }
}

void mother() {
    while(1) {
        P(s1);  // 等待儿子叫妈妈做饭
        cook(); // 做饭
        V(s2);  // 告诉儿子饭做好了
    }
}

妈妈一开始询问儿子要不要做饭时，执行的是P(s1)，相当于询问儿子需不需要吃饭，由于 s1初始值为 0，此时s1变成 -1，表明儿子不需要吃饭，所以妈妈线程就进入等待状态。

当儿子肚子饿时，执行了V(s1)，使得s1信号量从 -1 变成 0，表明此时儿子需要吃饭了，于是就唤醒了阻塞中的妈妈线程，妈妈线程就开始做饭。

接着，儿子线程执行了P(s2)，相当于询问妈妈饭做完了吗，由于s2初始值是 0，则此时s2变成 -1，说明妈妈还没做完饭，儿子线程就等待状态。

最后，妈妈终于做完饭了，于是执行 V(s2)，s2 信号量从 -1 变回了 0，于是就唤醒等待中的儿子线程，唤醒后，儿子线程就可以进行吃饭了。

生产者和消费者问题

生产者和消费者的问题中既包含了互斥关系，也包含了同步关系，问题描述如下：

  • 生产者在生成数据之后，将数据放在一个缓冲区中
  • 消费者从缓冲区中取出数据进行处理
  • 任何时刻，都只能有一个消费者或者生产者访问缓存区的数据

互斥关系：缓冲区一次只能有一个线程操作，说明缓冲区是临界代码，需要互斥
同步关系：当缓冲区为空时，消费者需要等待生产者生成数据，当缓冲区满时，生产者需要等待消费者消耗数据。

为了实现上述的这种控制关系，我们需要三个信号量：

  1. 互斥信号量mutex：用于互斥访问缓冲区，初始化为1
  2. 资源信号量fullBuffers：用于消费者询问缓冲区是否有数据，初始化为0
  3. 资源信号量emptyBuffers：用于生产者询问缓冲区是否有空间，初始化为n(缓冲区的大小)

伪码：

# define N 1000 // 缓冲区的大小

semaphore mutex = 1;
semaphore emptyBuffers = N;
semaphore fullBuffers = 0;

void producer() {
    while(1) {
		P(emptyBuffers); // 询问是否有空间，将缓冲区的空间 - 1
		P(mutex);        // 询问是否能进入临界区
		produce();       // 将生成的数据放在缓冲区
		V(mutex);        // 离开临界区
		V(fullBuffers);  // 将缓冲区的数据数量 + 1
    }
}

void consumer() {
	while(1) {
		P(fullBuffers);  // 询问缓冲区是否有数据，将缓冲区的数据数量 - 1
		P(mutex);        // 是否可以进入临界区
		consume();       // 将缓冲区中的数据取出1
		V(mutex); 		 // 离开临界区
		V(emptyBuffers); // 将缓冲区的空间数量 + 1
	}
}

死锁

死锁的概念

在多线程编程时，为了防止多线程竞争共享资源导致数据错乱，通常会在共享资源之前加上互斥锁，保证同时只能由有一个线程对共享资源进行操作。两个线程为了保护两个不同的共享资源使用了两个互斥锁，当两个互斥锁应用不当时，就可能会造成两个线程都在等待对方释放锁，在没有外力的情况下，这些线程就会一直互相等待，没有办法继续运行下去，这种情况就是发生了死锁。

死锁的发生需要四个条件：

  1. 互斥条件：多个线程不能同时使用一个资源。

  2. 持有并等待条件：一个线程已经持有了一个资源，但是又申请了一个新的资源，而这个新的资源已经被其他线程持有。
    当线程A拥有资源1，但是线程A又想申请资源2，但是资源2已经被线程C所占有。这种情况下A就会处于等待状态，但是A又不会释放资源1，这样就会造成线程B也无法申请资源1，因为资源1已经被A所占有。

    持有并等待条件

  3. 不可剥夺条件：线程已经获得的资源，在未使用完之前不能被其他线程获取。

  4. 环路等待条件：线程之间形成一个环路，线程A等待线程B，线程B等待线程A。
    线程A已经持有资源2，而想请求资源1，线程B已经获取了资源1，而想请求资源2，这就形成资源请求等待的环形图。

    环路等待条件

模拟死锁

使用C++代码来模拟死锁的产生，首先创建两个线程和两个互斥锁。

// linux
# include <iostream>
# include <thread>
# include <pthread.h>
# include <unistd.h>
using namespace std;

// 声明线程函数A和线程函数B
void* thread_A_func(void* data);
void* thread_B_func(void* data);

// 创建互斥锁

pthread_mutex_t mutex_A = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_B = PTHREAD_MUTEX_INITIALIZER;

int main() {
	pthread_t thread_A, thread_B;
	
	// 创建两个线程
	pthread_create(&thread_A, NULL, thread_A_func, NULL);
	pthread_create(&thread_B, NULL, thread_B_func, NULL);
	
	pthread_join(thread_A, NULL);
	pthread_join(thread_B, NULL);

	cout << "exit" << endl;
	return 0;
}

// 线程函数A

void* thread_A_func(void* data) {
	cout << "thread a is waiting for resource a" << endl;
	pthread_mutex_lock(&mutex_A);
	cout << "thread a is using resource a" << endl;

	sleep(1);

	cout << "thread a is waiting for resource b" << endl;
	pthread_mutex_lock(&mutex_B);
	cout << "thread a is using resource b" << endl;

	pthread_mutex_unlock(&mutex_B);
	pthread_mutex_unlock(&mutex_A);

	return (void*)0;
}

// 线程函数B的实现

void* thread_B_func(void* data) {
	cout << "thread b is waiting for resource b" << endl;
	pthread_mutex_lock(&mutex_B);
	cout << "thread b is using resource b" << endl;

	sleep(1);

	cout << "thread b is waiting for resource a" << endl;
	pthread_mutex_lock(&mutex_A);
	cout << "thread b is using resource a" << endl;

	pthread_mutex_unlock(&mutex_A);
	pthread_mutex_unlock(&mutex_B);

	return (void*)0;
}

运行结果

线程 B 在等待互斥锁 A 的释放，线程 A 在等待互斥锁 B 的释放，双方都在等待对方资源的释放，很明显，产生了死锁问题。

使用gdb调试工具可以对确定死锁死锁的位置。
首先获取可能发生了死锁的进程的pid，使用gdb -p xxxx命令，然后使用info threads命令查看线程的状态，可以看到线程A和线程B都在等待互斥锁，这就是死锁的位置。

避免死锁的出现

死锁的出现需要四个条件，互斥条件，持有并等待条件，不可剥夺条件，环路等待条件。四个条件缺一不可。

为了避免死锁的出现，我们只需要破坏其中任意一个条件即可。最常见的方法是，使用资源有序分配法，来破坏环路等待条件。

什么是资源有序分配法？

为所有的资源编上编号，保证线程A和线程B获取资源的顺序一样。
即，线程A是先尝试获取资源A， 再获取资源B；线程B也是先尝试获取资源A，再获取资源B。

资源有序分配法

// 使用资源有序分配法改进后的代码，只需要修改线程函数B的获取资源顺序即可。
// 线程函数B的实现

void* thread_B_func(void* data) {
	cout << "thread b is waiting for resource a" << endl;
	pthread_mutex_lock(&mutex_A);
	cout << "thread b is using resource a" << endl;
	
	sleep(1);
  	
	cout << "thread b is waiting for resource b" << endl;
	pthread_mutex_lock(&mutex_B);
	cout << "thread b is using resource b" << endl;

	
	pthread_mutex_unlock(&mutex_B);
	pthread_mutex_unlock(&mutex_A);

	return (void*)0;
}

运行结果

很明显，这次并没有发生死锁。

内存管理

虚拟内存

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。大多数操作系统都使用了虚拟内存，如Windows家族的“虚拟内存”；Linux的“交换空间”等。

什么是虚拟内存

cpu的执行，本质上是一个取址执行的过程。在内存中同时运行两个程序是不可能的，因为两个程序的代码和数据都是放在内存中的，如果同时运行两个程序，那么这两个程序的代码和数据就会相互覆盖，这样就会导致程序运行出错。操作系统为了解决这个问题，引入了虚拟内存的技术。

我们可以将两个进程所使用的地址隔离开，操作系统为每个进程分配独立的一套虚拟地址，互不干涉。这样，每个进程都可以独立的使用自己的虚拟地址，而不会相互干扰。

在这个过程中，操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存。

CPU通过虚拟地址访问物理地址

操作系统是怎么管理虚拟地址和物理地址之间的关系的？主要有内存分段和内存分页两种方法。

内存分段

计算机程序是由若干个逻辑分段组成的，包括代码分段，数据分段，栈段，堆段等。不同的段有不同属性，所以，使用分段的形式将这些段分离出来。

分段机制下，虚拟地址和物理地址应该如何映射？

分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。

内存分段

段选择因子和段内偏移量

段选择因子保存在段寄存器中。段选择因子中，最重要的是段号，用于段表的索引。段表中保存的是这个段的基地址，段的界限和特权等级等。

虚拟地址中的段内偏移量应该位于0和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

虚拟地址通过段表与物理地址进行映射，分段机制将程序的虚拟地址分为四个段，每个段在段表中占一个项，在这一项中找到段的基地址。再加上偏移量，就可以找到物理内存中的地址。

这其中的机制如下图所示：

如果要访问栈区偏移量为500的虚拟地址，我们可以计算出物理地址为，栈区的基地址7000+偏移量500 = 7500。
这样，我们就解决了从程序中的虚拟地址到实际物理地址对应的问题。但是，这种分段的解决方式是有一些不足之处的。

  • 会产生内存碎片
  • 内存的交换效率低下

为什么会产生内存碎片？

假设计算机的物理内存空间为1G，此时，我们并发使用游戏，浏览器和音乐，这几个应用占用的物理内存如下图所示：

为什么会产生内存碎片

当浏览器的任务退出时，释放出128MB的内存空间，此时，加上之前剩余128MB内存空间，计算机可分配的物理内存空间共有256MB，但是，此时我们却无法打开一个200MB内存占用的新程序，因为按照之前的做法，一个程序只能使用一段连续的内存空间。

内存分段会出现内存碎片吗？

内存碎片分为，内部内存碎片和外部内存碎片。

内存分段管理可以做到段根据实际需求分配内存，所以有多少需求就分配多大的段，所以不会出现内部内存碎片。
但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。
解决「外部内存碎片」的问题就是内存交换。
可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。
这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。

为什么程序的的虚拟地址有四个段？
c++程序的内存模型分为四个区，代码区，全局区，栈区，堆区。代码区是只读的，全局区是全局变量和静态变量的存储区，栈区是函数调用时的临时变量，由编译器自动分配和释放，堆区是由程序员自己动态分配的内存区域，若在使用后没有释放，则在程序结束后由操作系统进行回收。
c++内存模型

学习资料

文章作者: 李垚
文章链接: https://blog.ylee.cn/2022/11/18/os/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 李垚 !
tech os
评论
  目录