操作系统

2022-06-17

0. 操作系统笔记

本笔记是基于《操作系统导论》书籍，王道的操作系统考研以及哈工大李治军老师的操作系统课程做的笔记[https://www.bilibili.com/video/BV1d4411v7u7?spm_id_from=333.337.search-card.all.click&vd_source=2c8f06c2de9e2684a8af9b7eb62c75b7]。希望自己能了解点底层的东西。

1. 操作系统简介

操作系统要知道的关键问题就是操作系统如何将资源虚拟化，操作系统主要一种通用的技术，也就是虚拟化。操作系统将物力资源（如处理器、内存或者磁盘）转换为更通用、更强大且更易于使用的虚拟形式。

操作系统就是相当于沟通计算机应用和计算机的桥梁，是软件。管理的硬件包含：CPU管理，内存管理，终端管理，磁盘管理，文件管理，网络管理，电源管理，多核管理。

操作系统的层次如下：

操作系统的层次

<img style="border-radius: 0.3125em;
box-shadow: 0 1px 3px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
src="D:\blog\source\_posts\操作系统\系统调用过程.png">
<br>
<div style="color:orange; border-bottom: 1px solid #d9d9d9;
display: inline-block;
color: #999;
padding: 2px;">系统调用过程</div>

  <img style="border-radius: 0.3125em;
  box-shadow: 0 1px 3px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="D:\blog\source\_posts\操作系统\第一类虚拟机管理程序.png">
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">第一类虚拟机管理程序</div>

第二类虚拟机管理程序：就相当于一个普通的进程。仍然伪装成具有CPU和各种设备的完整计算机。就相当于在VMware中安装虚拟机那样。

2. 进程与线程

2.1 进程的概念与特征

在多道程序的环境下，允许多个程序并发的执行，此时它们将失去封闭性，并具有间断性以及不可再现性的特征。为此引入了进程的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性。

为了使参与并发执行的每个程序和数据都能独立的运行，必须为之配置一个专门的数据结构，称为进程控制块（process control block）PCB。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。相应的，由程序段、相关数据段和PCB三部分构成了进程实体。创建进程，实质上是创建进程实体中的PCB；而撤销进程，实质上是撤销进程中的PCB。PCB是进程存在的唯一标志。

可以简单的理解为：进程是程序的一次执行的过程。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征如下：

动态性：进程是程序的一次执行，它有着创建、活动、暂停、终止等过程，具有一定的生命周期，是动态的产生、变化和消亡的。
并发性：指多个进程实体同存于内存中，能在一段时间内同时进行。
独立性：指进程实体是一个能独立运行，独立获得资源和独立接受调度的基本单位。但凡未建立PCB的程序，都不能作为一个独立的单位参与运行。
异步性：由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进。

2.1.1 进程的状态与转换

进程在生命周期内，由于系统中各进程之间的相互制约及系统的运行环境的变化，使得进程的状态也在不断地发生变化。

运行态：进程正在处理机上运行。
就绪态：进程获得了除处理机外的一切所需资源，一旦得到了处理机，便可以立即运行。系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
阻塞态：进程正在等待某一事件而暂停运行，即使处理机空闲，该进程也不能运行。系统也将处于阻塞态的进程排成阻塞队列。
创建态：进程正在被创建，尚未转到就绪态。创建进程需要多个步骤：首先申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息；然后为该进程分配运行时所需的资源；最后把该进程转入就绪态并插入就绪队列。但是如果进程所需的资源尚不能得到满足，如内存不足，则创建工作尚未完成，进程此时处于创建态。
结束态：进程正从系统中消失，可能是进程正常结束或其他原因退出运行。结束运行时，系统首先将该进程置于结束态，然后进一步处理资源释放和回收等工作。

5种进程状态的切换

2.1.3 进程的组织

进程控制块：进程创建时，操作系统为它新建一个PCB，该结构之后常驻内存，任意时刻都可以存取，并在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。进程执行时，系统通过PCB了解进程的现行状态信息，以便操作系统对其进行控制和管理，进程结束时，系统回收其PCB，该进程随之消亡。在进程的整个生命周期内，系统总是通过PCB对进程进行控制的。

PCB包含的信息

程序段：程序段就是能被进程调度到CPU执行的程序代码段。程序可能被多个进程共享，即多个进程可以运行同一个程序。
数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

2.1.3 进程控制

进程的创建：

允许一个进程创建另一个进程，此时创建者称为父进程，被创建的称为子进程。子进程可以继承父进程所拥有的资源，当子进程被撤销时，应将从父进程那里获得的资源归还给父进程。在撤销父进程时，通常也会撤销其所有子进程。

创建新进程的步骤为：

（1）为新进程分配一个唯一的进程标识号，并申请一个空白的PCB（PCB是有限的）。若PCB申请失败，则创建失败。

（2）为进程分配其运行所需的资源，如内存、文件、I/O设备和CPU时间等。这些资源或从操作系统获得，或仅从父进程获得。若资源不足，则并不是创建失败，而是处于创建态，等待内存资源。

（3）初始化PCB，主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息以及设置进程的优先级等。

（4）若进程就绪队列能够接纳新的进程，则将新进程插入就绪队列，等待被调度运行。
进程的终止：

终止的情况有：正常结束、异常结束或者外界干预结束。

终止进程的过程为：

（1）根据被终止进程的标识符，检索出该进程的PCB，从中读出该进程的状态。

（2）若被终止进程处于执行状态，立即终止该进程的执行，将处理机资源分配给其他进程。

（3）若该进程还有子孙进程，则应该将其子孙进程终止。

（4）将该进程所拥有的全部资源，或归还给父进程，或归还给操作系统。

（5）将该PCB从所在队列（链表）中删除。
进程的阻塞和唤醒

阻塞原语的执行过程如下：

（1）找到将要被阻塞进程的标识号对应的PCB

（2）若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。

（3）把该PCB插入相应时间的等待队列，将处理机资源调度给其他就绪进程。

唤醒原语如下：

（1）在该事件的等待队列中找到相应进程的PCB

（2）将其从等待队列中移除，并设置其状态为就绪态。

（3）把该PCB插入就绪队列，等待调度程序调度。

2.1.4 进程的通信

进程之间交换信息的方式主要有三类：

共享存储

在通信的进程之间存在一块可以直接访问的共享内存，通过对这片共享空间进行读写操作实现进程之间的信息交换。

共享存储

在共享空间进行读写操作时，需要使用同步互斥工具，对共享空间的读写进行控制。共享内存有两种：低级方式的共享是基于数据结构的共享；高级方式的共享则是基于存储区的共享。操作系统只负责为通信进程提供可共享的存储空间和同步的互斥工具，而数据交换则由用户自己安排读写指令完成。

进程空间一般都是独立的，想让两个进程共享空间就必须通过系统调用实现，而进程内的线程是自然共享进程空间的。

消息传递

在消息传递系统中，进程间的数据交换以格式化的信息为单位。这种情况是在进程之间不存在可直接访问的共享空间的时候选择的。这种方式隐藏了通信实现的细节，使通信过程对用户透明，简化了通信程序的设计，是当前应用最广泛的进程间通信机制。这种机制能够很好地支持多处理机系统，分布式系统和计算机网络，所以也成为这些领域最重要的通信工具。

消息传递

（1）直接通信方式。发送进程直接把消息发送给接受进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。

（2）间接通信方式。发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。这个中间实体一般称为信箱。

管道通信

管道就是用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件。向管道提供（共享文件）输入的发送进程（即写进程），以字符流形式将大量的数据送入（写）管道；而接收管道输出的接收进程（即读进程）则从管道中接收（读）数据。管道机制必须提供：互斥、同步和确定对方的存在。

管道可以克服使用文件的两个问题：

（1）限制管道的大小。管道是一个固定大小的缓冲区。在Linux中该缓冲区的大小为4KB，这使得它的大小不像文件那样不加检验的增长。使用单个固定缓冲区也会带来问题，写管道时可能变满，随后对管道的write()调用将默认的被阻塞，等待某些数据被读取，以便腾出足够的空间供write()调用写。

（2）读进程也可能工作的比写进程快。当所有的当前进程数据已被读取时，管道变空。当这种情况发生时，一个随后的read()调用将默认的被阻塞，等待某些数据被写入，这解决了read()调用返回文件结束的问题。

2.2 线程和多线程

引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；而引入线程的目的是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

线程相当于轻量级进程，是一个基本的CPU单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体，是被系统独立调度和分配的基本单位，线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程的所有资源。一个线程可以创建和撤销另一个进程，同一个进程中的多个进程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中出现间断性。线程有就绪、阻塞和运行三种基本状态。

2.2.1 线程与进程的比较

调度。在引入线程的操作系统中，线程是独立调度的基本单位，而线程切换的代价远低于进程。在同一进程中，线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且一个进程中的多个线程之间也可以并发执行，甚至不同进程中的线程也能并发执行。
拥有资源。进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少，能保证独立运行的资源）。但是线程可以访问其隶属进程的系统资源，同一进程的所有线程都具有相同的地址空间。
独立性。每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。某进程中的线程对其他进程不可见。同一进程中的不同线程是为了提高并发性及进行相互间的合作而创建的，它们共享进程的地址空间和资源。
系统开销。在创建或撤销进程时，系统都要为之分配或回收进程控制块PCB及其他资源，操作系统为此付出的开销明显大于创建或撤销线程时的开销。同样在涉及上下文切换的地方，线程的开销也是要小于进程的。
支持多处理机系统。进程只能运行在一个处理机上，对于多线程进程，可以将进程中的多个线程分配到多个处理机上执行。

2.2.2 线程的属性

线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个惟一的标识符和一个线程控制块，PCB记录了线程执行的寄存器状态和栈等现场状态。
不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程。
同一个进程中的各个线程共享该进程所拥有的资源。
线程是处理机的独立调度单位，多个线程是可以并发执行的，在多CPU的计算机系统中，各线程可以同时占用不同的CPU，若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间。

2.2.3 线程的状态与转换

执行状态：线程已获得处理机而正在运行。
就绪状态：线程已具备各种执行条件，只需再获得CPU便可立即执行。
阻塞状态：线程在执行中因某事件受阻而处于暂停状态。

2.2.4 线程的实现方式

用户级线程

在用户级线程中，有关线程管理（创建、撤销和切换等）的所有工作都由程序在用户空间中完成，内核意识不到线程的存在。应用程序可以通过使用线程库设计成多线程程序。通常，应用程序从单线程开始，在该线程中运行开始，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。

线程创建方式

对于设置了用户级线程的系统，其调度仍然是以进程为单位进行的，各个流程轮流执行一个时间片。这种实现方式的优点为：1.线程切换不需要转换到内核空间，节省了模式切换的开销。2.调度算法可以是进程专用的，不同的进程可以根据自身的需要选择不同的调度算法。3.用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分。

缺点为：1.系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内所有线程都被阻塞。2.不能发挥多处理机的优势，内核每次分配给一个进程的仅有一个CPU，因此进程中仅有一个线程能执行。

内核级线程

内核级线程也是在内核的支持下运行的，线程管理的所有工作也是在内核空间内实现的。内核级线程的实现方式的优点为：1.能发挥多处理机的优势，内核能同时调度统一进程的多个线程并执行。2.如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可以运行其他进程中的线程。3.支持线程具有很小的数据结构和堆栈，线程切换比较快，开销小。4.内核本身可以采用多线程技术，可以提高系统的执行速度和效率。

缺点为：同一进程中的线程切换，需要从用户态转到核心态进行，系统开销比较大。因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的。

组合方式

多线程的模型有以下三种：

多线程模型

2.3 同步与互斥

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约的关系。为了协调进程之间的相互制约的关系，引入了进程同步的概念。

临界资源

虽然多个进程可以共享系统中的各种资源，但是其中许多资源一次只能为一个进程所使用，我们将一次允许一个进程使用的资源称为临界资源。对临界资源的访问可以分为四个部分：

进入区：为了进入临界区使用临界资源，需要检查是否能够进入临界区，若能的话就设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
临界区：进程中访问临界资源的那段代码。
退出区：将正在访问临界区的标志清除。
剩余区：代码中的其余部分。

do{
    entry section; //进入区
    critical section; //临界区
    exit section; //退出区
    remainder section; //剩余区
} while ()

同步

同步也是制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作。

互斥

互斥也称为间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

为禁止两个进程同时进入临界区，同步机制应该遵循以下准则：

空闲让进。
忙则等待。
有限等待。（有限时间内进入临界区）
让权等待。（当进程不能进入临界区时，应该立即释放处理器，防止进程忙等待）

2.3.1 互斥锁

解决临界区最简单的工具就是互斥锁。一个进程在进入临界区时应获得锁，在退出临界区的时候释放锁。函数acquire()获得锁，release()释放锁。

每个互斥锁一个布尔变量available，表示锁是否可用，如果可用的话调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

acquire(){
    while (! available)
        ;//忙等待
    available = false;//获得锁
    release(){
        available = true;//释放锁
    }
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一个CPU时，就浪费了CPU周期，因此互斥锁通常用于多处理系统。

2.3.2 信号量

信号量机制可以用来同步与互斥的问题，它只能被两个标准的原语wait(S)和signal(S)访问，也可以记为“P操作”和“V操作”。原语是指完成某种功能而不被分割、不被中断执行的操作序列，通常可由硬件来实现。原语不可中断在于原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。

记录型信号量

是一种不存在忙等现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程。

typedef struct{
    int value;
    struct process *L;
} semaphore;

相应的wait(S)和signal(S)的操作如下：

void wait(semaphore S){//相当于申请资源
    S.value--;//表示进程请求一个该类资源
    if(S.value < 0){
        add this process to S.L;
        block(S.L);
    }
}
void signal(semaphore S){//相当于释放资源
    S.value ++;
    if (S.value <= 0){
        remove a process P from S.L;
        wakeup(P);
    }
}

利用信号量实现同步

设S为实现进程$P_1,P_2$同步的公共信号量，初值为0.进程$P_2$中的语句y要使用进程$P_1$中语句的运行结果，所以只有当语句x执行完成之后语句y才可以执行。

semaphore S=0;//初始化信号量
P1(){
    x;//语句x
    V(S);//告诉进程P2，语句x已经完成
    ...
}
P2(){
    ...
    P(S);//检查语句x是否运行完成
    y;
    ...
}

若$P_2$执行到$P(S)$时，S为0，执行P操作会把进程$P_2$阻塞，并放入阻塞队列；当进程$P_1$中x执行完后，执行V操作，把$P_2$从阻塞队列中放回就绪队列，当$P_2$得到处理机时，就得以继续执行。

2.4 管程

在信号量机制中，每个要访问临界资源的进程都必须自备同步的PV操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当导致系统死锁。管程就是用来保证进程的互斥，无序程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了变量条件，可以让程序员灵活的实现进程同步。

管程由4部分组成：1.管程的名称；2.局部于管程内部的共享数据结构说明；3.对该数据结构进行操作的一组过程或函数；4.对局部于管程内部的共享数据设置初始值的语句。

monitor Demo{//定义一个名称为"Demo"的管程
    //定义共享数据结构，对应系统中的某种共享资源共享数据结构S
    //对共享数据结构初始化的语句
    init_code(){
        S=5;//初始资源数等于5
    }
    //过程1：申请一个资源
    take_away(){
        对共享数据结构x的一系列处理
        S--;//可用资源数-1
        ...
    }
    //过程2：归还一个资源
    give_back(){
        对共享数据结构x的一系列处理
        S++;
        ...
    }
}

管程把对共享资源的操作封装起来，管程内的共享数据只能被管程内的过程所访问。
每次仅允许一个进程进入管程，从而实现进程互斥。

2.5 死锁

在多道程序系统中，由于多个进程的并发执行，带来了死锁的现象。死锁就是指多个进程由于竞争资源而造成的一种僵局，互相等待，若无外力作用，这些进程都将无法向前推进。

2.5.1 死锁产生的原因

系统资源的竞争
进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，同样会造成死锁。例如并发进程$P_1,P_2$分别保持了资源$R_1,R_2$，而进程$P_1$申请资源$R_2$，进程$P_2$申请资源$R_1$时，两者都会因为所需资源被占用而阻塞，于是导致死锁。

2.5.2 死锁产生的必要条件

互斥条件：进程要求对所分配的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。
不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求被进程阻塞，但对自己已获得的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

2.5.3 死锁的处理策略

死锁预防。设置某些限制条件，破坏产生死锁的4个条件中的一个或几个。
避免死锁。在资源启动的动态分配过程中，用某种方法阻止系统进入不安全状态。
死锁的检测及解除。

2.5.4 死锁避免的方法

2.5.4.1 系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应该先计算此分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配，否则让进程等待。

安全状态就是系统能按照某种进程推进顺序($P_1,P_2,...,P_n$)为每个进程$P_i$分配其所需要的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺序完成。此时称$P_1,P_2,...,P_n$为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态。反之，只要系统处于安全状态，系统便可以避免进入死锁状态。

2.5.4.2 银行家算法

来源于：[https://qyliang.blog.csdn.net/article/details/80245715?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-80245715-blog-124103874.pc_relevant_show_downloadRating&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-80245715-blog-124103874.pc_relevant_show_downloadRating&utm_relevant_index=1]:

银行家算法的本质就是：当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探作废，让该进程继续等待。

首先是银行家算法中的进程：包含进程$P_i$的需求资源数量（也是最大需求资源数量，MAX），已分配给该进程的资源A(Allocation)，还需要的资源数量(Need = M - A)
Available为空闲资源数量，即资源池

假设资源$P_1$申请资源，银行家算法首先试探的分配给它，若申请的资源数量小于等于available，然后接着判断分配给$P_1$后剩余的资源，能不能使得进程队列的某个进程执行完毕，若没有进程可以执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随着时间推移，系统将处于死锁状态）。

若有进程可以执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程，若所有的进程都可以执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列。

银行家算法的代码如下：

#include "stdio.h"
#include "iostream"
using namespace std;

int Max[100][100] = {0}; //各进程对资源的最大需求数
int Allocation[100][100] = {0}; //已经给各进程分配了多少资源
int Need[100][100] = {0}; //各进程还需要多少资源
int Available[100] = {0}; //总的可用资源
int Request[100] = {0}; //进程此次申请的各种资源数
int Afford[100] = {0}; //还有多少可用资源
int Security[100] = {0}; //安全序列的进程
char Name[100] = {0}; //各类资源名称
int M, N; //进程数和资源种类

void init(){
    cout << "请输入可分配的资源种类数量：";
    cin >> N;
    cout << endl;
    for (int i = 0; i < N; ++i) {
        cout << "请输入第" << i + 1 << "个资源的名称：";
        cin >> Name[i];
        cout << "请输入" << Name[i] << "资源的可分配数量：";
        cin >> Available[i];
        cout << endl;
    }
    cout << endl << "请输入进程数量：";
    cin >> M;
    cout << endl << "请输入进程的Max矩阵" << endl;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> Max[i][j]; //输入每个进程所需要的各种资源的最大数量
        }
    }
    cout << endl << "请输入进程的Allocation矩阵" << endl;
    int every[100] = {0};
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> Allocation[i][j]; //每个进程已经分配的各种资源的数量
            Need[i][j] = Max[i][j] - Allocation[i][j]; //Need数组通过最大-已经获得
            every[j] += Allocation[i][j]; //统计每一种类已经分配的资源数量
        }
    }
    for (int i = 0; i < N; ++i) {
        Available[i] = Available[i] - every[i]; //总的-已经分配处去的=现在剩余的可分配数量
    }
}

void show_info(){
    cout << endl << endl;
    cout << "              " << "****************" << endl;
    cout << "       " <<"系统当前可用的资源矩阵Available:" << endl;
    cout << "              " << "****************" << endl;
    cout << "               ";
    int i;
    for (int i = 0; i < N; ++i) {
        cout << "  " << Name[i];
    }
    cout << endl << "               ";
    for (int i = 0; i < N; ++i) {
        cout << "    " << Available[i];
    }
    cout << endl << endl;
    cout << "              " << "****************" << endl;
    cout << "         " << "系统当前资源分配情况如下:" << endl;
    cout << "              " << "****************" << endl << endl;
    cout << "    " << "       Max      Allocation     Need      " << endl;
    cout << "进程名  ";

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < N; ++j) {
            cout << Name[j] << "    ";
        }
    }
    cout << endl;
    for (int i = 0; i < M; ++i) { //打印进程的三个矩阵
        cout << "Pro" << i;
        for (int j = 0; j < N; ++j) {
            cout << "    " <<Max[i][j];
        }
        for (int j = 0; j < N; ++j) {
            cout << "    " << Allocation[i][j];
        }
        for (int j = 0; j < N; ++j) {
            cout << "    " << Need[i][j];
        }
        cout << endl;
    }
}

bool is_Safe(){
    int isAfford[100] = {0}; //是否有足够的资源分配给进程，使之完成运行
    for (int i = 0; i < N; ++i) {
        Afford[i] = Available[i]; //在执行安全算法开始时，work=available
    }
    int count = 0, m = 0;//count是用来统计系统足够某个进程所需的某种资源数量
    for (int i = 0; i < M; ++i) {
        count = 0;
        for (int j = 0; j < N; ++j) {
            if (isAfford[i] == 0 && Need[i][j] <= Afford[j]){
                //如果进程没有执行且资源需求条件满足
                count ++;//这种资源是够的
                if (count == N){//表示对i号进程的所有资源都满足
                    isAfford[i] = 1;//记录i号进程为可执行
                    for (int k = 0; k < N; ++k) {
                        Afford[k] = Afford[k] + Allocation[i][k];//进程执行成功，回收各资源
                    }
                    Security[m++] = i;//此进程可以进入安全序列
                    i = -1;//将i设置为-1，通过for循环执行i++后变为0，从第一个进程重新开始找
                }
            }
        }
    }
    for(int i=0;i<M;i++){             //依次检查各进程，如果有一个不满足，就说明不安全
        if(isAfford[i]==0){
            cout << endl << "系统不安全" << endl;
            return false;
        }
    }
    cout << endl << "系统安全" << endl << endl;
    cout << "一个安全序列为:";
    for(int i=0;i<M;i++){
        cout << "P" << Security[i];
        if(i<M-1)
            cout << "-->";
    }
    cout << endl << endl;
    return true;
}

bool bank(){
    cout << "请输入手动分配资源的进程编号:";
    int id;
    bool flag=true;
    while(cin >> id){
        if(id < 0 || id > M-1){
            cout << endl << "进程不存在!请重新输入!" << endl;
            cout << endl << "请重新输入希望手动分配资源的进程的编号:";
        }
        else break;
    }
    cout << endl << "请分别输入各类请求资源数(" << N << "个):";
    for(int i=0;i<N;i++){
        cin >> Request[i];
    }
    cout << endl << "开始为进程Pro" << id << "分配资源,请等待..." << endl;
    for(int i=0;i<N;i++){
        if(Request[i]>Need[id][i]){
            cout << "进程请求资源数大于所需资源数，无法分配!" << endl;
            flag=false;
            break;
        }
        else if(Request[i]>Available[i]){
            cout << "进程请求资源数大于可用资源数，无法分配!" << endl;
            flag=false;
            break;
        }
        else{
            Available[i] -= Request[i];           //可用资源数减少
            Allocation[id][i] += Request[i];      //已分配资源数增加
            Need[id][i] -= Request[i];            //所需资源数减少
        }
    }
    if(flag==true){
        if(is_Safe())
            cout << "分配资源完成!" << endl;
        else{
            for(int i=0;i<N;i++){
                Available[i] += Request[i];           //分配资源回收
                Allocation[id][i] -= Request[i];
                Need[id][i] += Request[i];
            }
            cout << endl <<"此次分配会导致系统不安全，无法分配!" << endl;
        }
    }
    return flag;
}

int main(){

    cout << "              " << "****************" << endl;
    cout << "                 " << "银行家算法" << endl;
    cout << "              " << "****************" << endl << endl;
    init(); //初始化
    show_info();
    is_Safe();

    cout << "              " << "****************" << endl;
    cout << "               " << "手动进行资源请求" << endl;
    cout << "               " << "输入R/r请求资源" << endl;
    cout << "               " << "输入E/e退出程序" << endl;
    cout << "              " << "****************" << endl;

    char choice;
    while(true){
        cout << endl << "请选择资源分配(R/r)还是退出(E/e):";
        cin >> choice;
        cout << endl;
        if(choice=='R'||choice=='r'){
            if(bank()){          //可分配
                show_info();     //展示信息
            }           //这边由于上述bank()算法已经进行了安全性检查，此处无需再次调用
            else{
                show_info();
            }
        }
        else if(choice=='E'||choice=='e'){
            cout << "退出程序成功!" << endl;
            exit(0);
        }
        else
            printf("请正确选择!");
    }
    return 0;
}

2.6 死锁检测和解除

系统死锁可以利用资源分配图来描述。

圆圈表示一个进程，框表示一类资源，一种类型的资源可能有多个，进程到资源的有向边称为请求边，表示该进程中申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。

2.6.1 死锁定理

在资源分配图中，找出既不阻塞又不孤点的进程$P_i$（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源）。判断某种资源是否有空闲，应该用它的资源数量减去它在资源分配图中的出度。
进程$P_i$释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。
死锁解除：1.资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。2.撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。3.进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时资源释放资源而非被剥夺。

3. 内存管理

3.1 内存管理的概念

内存管理的主要功能有：

内存空间的分配与回收
地址转换
内存空间的扩充
内存共享
存储保护

将用户源程序变为可在内存中执行的程序，通常需要以下步骤：编译，链接，装入。

程序的链接方式：

静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。将几个模块装配成一个装入模块时：1、修改相对地址，编译后的所有目标模块都是从0开始的相对地址；2、变换外部调用符号，将每个模块中所用的外部调用符号也都变换成相对地址。
装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。
运行时动态链接：对于某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块，都不会被调入内存和被连接到装入模块上。

装入方式同样有以下三种：

绝对装入：只适用于单道程序环境。在编译时，若知道程序将驻留在内存的某个位置，则编译程序将产生绝对地址的目标代码。绝对装入程序难找装入模块中的地址，将程序和数据装入内存。
可重定位装入：在多道程序环境下，多个目标模块的起始地址通常都是从0开始的，程序中的其他地址都是相对于起始地址的，此时应该采用可重定位装入方式。根据内存的当前情况，将装入模块装入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为重定位。
动态运行时装入：动态重定位，程序在内存中若发生移动，装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。

逻辑地址和物理地址：编译后，每个目标模块都从0号单源开始编址，这称为目标模块的相对地址（逻辑地址）；当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序一次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间（虚拟地址空间）。进程在运行时，看到和使用的地址都是逻辑地址。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换为物理地址，这叫做地址重定位。操作系统通过内存管理部件（MMU）将进程使用的逻辑地址转换为物理地址。

进程的内存映像：当一个程序调入内存运行时，就构成了进程的内存映像。一个内存映像一般有几个要素：1.代码段，即程序的二进制代码，是只读的，可以被多个进程共享；2.数据段，即程序运行时加工处理的对象，包括全局变量和静态变量；3.进程控制块（PCB），存放在系统区，控制和管理进程；4.堆，用来存放动态分配的变量，通过调用malloc函数动态的向高地址分配空间；5.栈，用来实现函数调用，从用户空间的最大地址往低地址方向增长。

代码段和数据段在程序调入内存时就指定了大小，而堆和栈不一样，当调用malloc和free这样的函数时，堆可以在运行时动态地扩展和收缩。用户栈在程序运行期间也可以动态扩展和收缩，每调用一个函数，栈就会增长，从一个函数返回时，栈就会收缩。

内存保护

确保每个进程都有一个单独的内存空间。需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可以采取两种方法：

在CPU中设置一对上下限寄存器，存放用户作业在驻村中的上限和下限地址，每当CPU要访问一个地址时，分别和两个寄存器的值比较，判断有无越界。
采用重定位寄存器和界地址寄存器来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。内存管理机构动态的将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送给内存单元。只有操作系统内核才能加载这两个寄存器，而不允许用户程序修改。

内存共享

只有只读的区域才可以共享。可重入代码又称纯代码，是一种允许多个进程同时访问但不允许任何进程修改的代码。在实际执行时，可以为每个进程配以局部数据区，把在执行中可能改变的部分复制到该数据区，这样程序在执行时只需对该私有数据区中的内存进行修改，不去改变共享的代码。

连续分配管理方式

单一连续分配：内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间由该程序独占。
固定分区分配：是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区。

动态分区分配

是在进程装入内存时，根据进程的实际需要，动态的为之分配内存，并使分区的大小正好适合进程的需要。系统中分区的大小和数目是可变的。

动态分区在开始时是很好的，但是之后内存中可能会出现越来越多的小的内存块，内存的利用率也随之降低。这些小的内存块称为外部碎片，存在于所有分区的外部。克服外部碎片可以通过紧凑技术解决，即操作系统不时地对进程进行移动和整理。

在进程装入或换入主存时，若内存中有多个足够大的空闲块，则操作系统必须确定分配哪个内存块给进程使用，这就是动态分区分配策略。

首次适应算法：空闲分区以地址地址递增的顺序链接。分配内存时，从链首开始顺序查找，找到大小能满足要求的第一个空闲分区分配给作业。
临近适应算法：分配内存时从上次查找结束时的位置开始继续查找。
最佳适应算法：空闲分区按容量递增的次序形成空闲分区链，找到第一个能满足要求且最小的空闲分区分配给作业。
最坏适应算法：空闲分区以容量递减的次序链接，找到第一个能满足要求的，即最大的分区。

3.2 基本分页存储管理

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存利用率都比较低。分页的思想就是为了尽量避免碎片的产生：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页存储中的几个基本概念：

页面和页面大小：进程中的块称为页或者页面，内存中的块称为页框或者页帧。外存直接称为块或者盘块。进程在执行时需要申请主存空间，即要为每个页面分配主存中的可用页框，页和页框一一对应。
地址结构：分页存储管理的逻辑地址结构如下图所示：

地址结构决定了虚拟内存的寻址空间有多大。
页表：为了便于在内存中找到进程的每个页面对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般存在于内存中。表的作用是实现页号到物理块号的地址映射。

基本地址变换机构

设置一个页表寄存器（PTR），存放页表在内存的起始地址F和页表长度M。设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

计算页号P（P=A/L）和页内偏移W（W=A%L）
比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行
页表中页号P对应的页表项地址=页表起始地址F+页号Px页表项长度，取出该页表项内容b，即为物理块号。
计算$E=b\times L + W$

具有快表的地址变换机构

由上面的地址变换可知，若页表全部放在内存中，则存取一个数据或一个指令至少要访问内存

4. 网课笔记

4.0 C语言知识

程序其实也是个状态机。这是从源代码角度来看程序的。

从状态机的视角来看，程序就是$计算\to syscall \to 计算 \to ...$这样的过程。

#include <sys/syscall.h>

.globl _start
_start:
        movq $SYS_write, %rax   #write(
        movq $1,        %rdi    # fd=1,
        movq $st,       %rsi    # buf=st,
        movq $(ed - st),%rdx    # count=ed-st
        syscall                 # );

        movq $SYS_exit, %rax    #exit(
        movq $1,        %rdi    # status=1
        syscall                 # );

st:
        .ascii "\033[01;31mHello, OS World\033[0m\n"
ed:

上面这段代码可以说是最小的hello world的实现，里面提到了几个寄存器。寄存器属于CPU中的一块存储区域，有非常高的读写速度。

rax:
rdi:
rsi:
rdx:

寄存器的结构一般如下：

逆向分析中常见的寄存器有4种：通用寄存器、段寄存器、标志位寄存器和指令指针寄存器。通用寄存器如下。

EAX：(针对操作数和结果数据的)累加器，返回函数结果
EBX：(DS段中的数据指针)基址寄存器
ECX：(字符串和循环操作数)计数器
EDX：(I/O指针)数据寄存器
EBP：(SS段中栈内数据指针)扩展基址指针寄存器
ESI：(字符串操作源指针)源变址寄存器
EDI：(字符串操作目标指针)目的变址寄存器
ESP：(SS段中栈指针)栈指针寄存器

编译器的作用就是将源代码（状态机）转换为二进制代码（状态机）$C=compile(S)$，那么正确的编译就是：S与C的可观测行为严格一致。

现在的编译器会在保证观测一致性的前提下改写代码：

内嵌汇编也可以参与优化
其他优化可能会跨过不带barrier的asm volatile。
eventual memory consistency

4.1 并发

并发的基本单位：线程

并发共享内存的多个执行流：1.执行流拥有独立的堆栈/寄存器 2.共享全部的内存（指针可以互相引用）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdatomic.h>
#include <assert.h>
/**
unistd.h为Linux/Unix系统中内置头文件，包含了许多系统服务的函数原型，
例如read函数、write函数和getpid函数等。
其作用相当于windows操作系统的"windows.h"，
是操作系统为用户提供的统一API接口，方便调用系统提供的一些服务。
**/
#include <unistd.h>
#include <pthread.h>

#define NTHREAD 64
enum { T_FREE = 0, T_LIVE, T_DEAD, };
struct thread {
  int id, status;
  pthread_t thread;
  void (*entry)(int);//指针函数，传参是int类型
};

//创建线程池，并创建指向线程池的指针
struct thread tpool[NTHREAD], *tptr = tpool;

void *wrapper(void *arg) {
    //传参arg是一个指针对象
  struct thread *thread = (struct thread *)arg;
  thread->entry(thread->id);
  return NULL;
}

void create(void *fn) {
  assert(tptr - tpool < NTHREAD);//创建合法的线程
  *tptr = (struct thread) {
    .id = tptr - tpool + 1,
    .status = T_LIVE,
    .entry = fn,
  };
  /**
  pthread_create是Unix下创建线程的函数。
  传参：
  int pthread_create(pthread_t* restrict tidp,const pthread_attr_t* restrict_attr,void* (*start_rtn)(void*),void *restrict arg);
  tidp：事先创建好的pthread_t类型的参数。成功时tidp指向的内存单元被设置为新创建线程的线程ID。
  attr：用于定制各种不同的线程属性。
  start_rtn：新穿件线程从此函数开始运行。
  arg：start_rtn函数的参数。无参数时设置为null即可。
  返回值：成功返回0，否则返回错误码
  **/
  pthread_create(&(tptr->thread), NULL, wrapper, tptr);
  ++tptr;
}

void join() {
  for (int i = 0; i < NTHREAD; i++) {
    struct thread *t = &tpool[i];
    if (t->status == T_LIVE) {
      pthread_join(t->thread, NULL);
      t->status = T_DEAD;
    }
  }
}

__attribute__((destructor)) void cleanup() {
  join();
}

并发有个问题就是：原子性的丧失。所谓的原子性就是一段代码执行独占整个计算机系统。

单处理多线程：线程在运行时可能被中断，切换到另一个线程执行。
多处理器多线程：线程根本就是并行执行的。

比方说下面这个程序，就是因为线程起了冲突才造成最终的错误的。

#include "thread.h"

#define N 100000000

long sum = 0;

void Tsum(){
    for (int i = 0; i < N; ++i) {
//        sum ++;
        //even if assembly, it returns the wrong res
//        asm volatile("add $1, %0": "+m"(sum));
        //true when we add lock to the threads
        //but the time usage increased dramatically
        asm volatile("lock add $1, %0": "+m"(sum));
    }
}

int main(){
    //two simple threads make conflicts
    create(Tsum);
    create(Tsum);
    join();
    printf("sum = %ld\n", sum);
}

互斥和原子性是重点，以下俩API实现是关键：

lock(&lk)
unlock(&lk)
实现临界区之间的绝对串行化
程序的其他部分仍然可以并行执行

这里要注意的重点就是：多处理器编程是不原子、能乱序、不立即可见的。这些都是来自于编译优化，处理器也就是编译器。

并发造成另一个问题就是顺序性问题，比方说下面这个程序：

#include "thread.h"

#define N 100000000

long sum = 0;

void Tsum(){
    for (int i = 0; i < N; ++i) {
//        sum ++;
        //even if assembly, it returns the wrong res
//        asm volatile("add $1, %0": "+m"(sum));
        //true when we add lock to the threads
        //but the time usage increased dramatically
        asm volatile("lock add $1, %0": "+m"(sum));
    }
}

int main(){
    //two simple threads make conflicts
    create(Tsum);
    create(Tsum);
    join();
    printf("sum = %ld\n", sum);
}

如果只是任凭编译器进行优化的话，可能会出现不一样的输出结果。

1	asm volatile("lock add $1, %0": "+m"(sum));

这句话的引入就是为了阻止编译器对内存访问"eventually consistent"的处理导致的共享内存作为线程同步工具的失效。插入上面的内嵌汇编就是为了优化不能穿越，告诉编译器不要去优化这个代码。

最后一个可能产生的问题就是不可见性。

单个处理器用电路把汇编代码编译成更小的$\mu \ ops$，在任何时刻，处理器都维护一个$\mu \ op$的池子。每个周期向池子补充尽可能多的$\mu \ op$，也就是多发射。每一个周期执行尽可能多的$\mu \ op$，也就是乱序执行，按序提交。满足单处理器eventual memory consistency的执行，在多处理器上可能无法序列化。

1
2
3

     # <-----------+
movl $1, (x)   #   |
movl (y), %eax # --+

这段代码如果x发生cache miss，可以让y先执行，在多处理器上的表现就可能是y=0,x=0，产生错误的结果。

互斥

互斥是为了保证两个线程不能同时执行一段代码。

如果只允许内存的读和写的话，如何保证共享内存上的互斥呢？

首先介绍一个Peterson算法：

Peterson算法使用两个控制变量flag和turn，其中flag[n]的值为真表示ID号为n的进程希望进入该临界区。变量turn保存有权访问共享资源的进程的ID号。

假设A和B争用厕所：这里的旗子就是表示的谁想要上厕所，标签表示当两个进程都想上厕所时，谁可以上。

想进入厕所之前，A/B都要先举起自己的旗子
- A确认旗子举好以后，往厕所门上贴上“B正在使用的标签”
- B确认旗子举好以后，往厕所门上贴上“A正在使用”的标签。
然后，如果对方的旗子举起来，且门上的名字不是自己，等待；否则可以进入厕所。
出厕所后，放下自己的旗子。

要注意看到的和下一步决策不能够同时执行，这也就是并发麻烦的所在。

#include "thread.h"
#include "stdatomic.h"
#define A 1
#define B 2

atomic_int nested;//atomic_int保证了线程的安全性
atomic_int count;

void critical_section(){
    long cnt = atomic_fetch_add(&nested, 1);
    //only one thread in the pool?
    assert(atomic_fetch_add(&nested, 1) == 0);
    atomic_fetch_add(&nested, -1);
}

int volatile x = 0, y = 0, turn = A;

void TA(){
    while (1){
        x = 1; //PC=1，把自己的旗子举起来
        turn = B; //PC=2，把对方的标签贴上去
        while (y && turn == B);//只要对面的旗子举起来并且标签还是对面，就一直空等待
        critical_section();//出来进入临界区
        x = 0;//PC=4，旗子放下来
    }
}

void TB(){
    while (1){
        y = 1; //PC=1
        turn = A; //PC=2
        while (x && turn == A);
        critical_section();
        y = 0;//PC=4
    }
}

int main(){
    create(TA);
    create(TB);
}

在进入临界区的时候：

1.如果只有一个人举旗，他就可以直接进入；

2.如果两个人同时举旗，由厕所门上的标签决定谁进（手快有，被另一个人的标签覆盖（太心机了，看似谦让，实则自私），手慢无）

3.A看到B没有举旗，那么B一定不在临界区，或者B想进去但是还没有来得及把A正在使用贴在门上。

4.A看到B举旗子，A一定已经把旗子举起来了。

如何在多处理器上实现线程互斥？

实现互斥的根本困难在于：不能同时读/写共享内存。

自旋锁

这里是假设硬件能为我们提供一条瞬间完成的读+写指令。如果多个人同时请求，由硬件选出一个胜者，败者要等胜者完成后才能继续执行。

用xchg实现互斥，还是用厕所那个例子来说：

1.首先最开始的时候在厕所门口放一个桌子（共享变量），初始时桌子上是钥匙

2.想要上厕所的同学（一条xchg指令）

看一眼桌子上的东西是钥匙还是禁止进入，如果是禁止进入的话就等

3.出厕所的同学要把钥匙归还到桌子上

python下实现这个自旋锁的代码为：

class Spinlock:
    locked = ''

    @thread
    def t1(self):
        while True:
            while True:
                self.locked, seen = '🔒', self.locked
                if seen != '🔒': break
            cs = True
            del cs
            self.locked = ''

    @thread
    def t2(self):
        while True:
            while True:
                self.locked, seen = '🔒', self.locked
                if seen != '🔒': break
            cs = True
            del cs
            self.locked = ''

    @marker
    def mark_t1(self, state):
        if localvar(state, 't1', 'cs'): return 'blue'

    @marker
    def mark_t2(self, state):
        if localvar(state, 't2', 'cs'): return 'green'

    @marker
    def mark_both(self, state):
        if localvar(state, 't1', 'cs') and localvar(state, 't2', 'cs'):
            return 'red'

然而自旋锁存在以下缺陷：

自旋（共享变量）会触发处理器间的缓存同步，延迟增加
除了进入临界区的线程，其他处理器上的线程都在空转，争抢锁的处理器越多，利用率越低。
获得自旋锁的线程可能被操作系统切换出去，实现100%的资源浪费。

所以自旋锁的使用场景有限：1.临界区几乎不拥挤；2.持有自旋锁时禁止执行流切换。

互斥锁

那么我们可以很简单的想到，如何把自己的CPU让渡给其他作业执行。

这个C语言代码并不能做到，应该把锁放在操作系统中：

syscall(SYSCALL_lock, &lk);：试图获取lk，但是如果失败，就切换到其他线程。

syscall(SYSCALL_unlock, &lk);：释放lk，如果有等待锁的线程就唤醒。

实现线程+长临界区的互斥：

操作系统=更衣室管理员。
先到的人（线程）：
    成功获得手环，进入游泳馆
    *lk = locked，系统调用直接返回
后到的人（线程）：
    不能进入游泳馆，等待排队
    线程放入等待队列，执行线程切换(yield)
洗完澡出来的人（线程）：
    交还手环给管理员；管理员把手环再交给排队的人。
    如果等待队列不为空，则等待队列中取出一个线程允许执行。
    如果等待队列为空，*lk = unlocked。
管理员OS使用自旋锁确保自己处理手环的过程是原子的。

下面是互斥锁的实现的过程：

#include <semaphore.h>

// Spinlock
typedef int spinlock_t;
#define SPIN_INIT() 0

static inline int atomic_xchg(volatile int *addr, int newval) {
  int result;
  asm volatile ("lock xchg %0, %1":
    "+m"(*addr), "=a"(result) : "1"(newval) : "memory");
  return result;
}

void spin_lock(spinlock_t *lk) {
  while (1) {
    intptr_t value = atomic_xchg(lk, 1);
    if (value == 0) {
      break;
    }
  }
}
void spin_unlock(spinlock_t *lk) {
  atomic_xchg(lk, 0);
}

// Mutex
typedef pthread_mutex_t mutex_t;
#define MUTEX_INIT() PTHREAD_MUTEX_INITIALIZER
void mutex_lock(mutex_t *lk)   { pthread_mutex_lock(lk); }
void mutex_unlock(mutex_t *lk) { pthread_mutex_unlock(lk); }

// Conditional Variable
typedef pthread_cond_t cond_t;
#define COND_INIT() PTHREAD_COND_INITIALIZER
#define cond_wait pthread_cond_wait
#define cond_broadcast pthread_cond_broadcast
#define cond_signal pthread_cond_signal

// Semaphore
#define P sem_wait
#define V sem_post
#define SEM_INIT(sem, val) sem_init(sem, 0, val)

#include "thread.h"
#include "thread-sync.h"

#define N 1000000000
mutex_t lock = MUTEX_INIT();

long n, sum = 0;

void Tsum(){
    for (int i = 0; i < n; ++i) {
        mutex_lock(&lock);
        sum ++;
        mutex_unlock(&lock);
    }
}

int main(int argc, char *argv[]){
    assert(argc == 2);
    int nthread = atoi(argv[1]);
    n = N / nthread;
    for (int i = 0; i < nthread; ++i) {
        create(Tsum);
    }
    join();
    assert(sum == n * nthread);
}

这个如果我们使用spinlock来看运行的时间的话，开多个线程的时间是要大于开单个线程的时间的；而如果使用mutex_lock的话则不会有显著的变化。

当然也能将spin_lock和mutex_lock结合起来，结合优点。

4.2 同步

这里首先引出一个生产者-消费者问题：

1 2	void Tproduce() {while(1) printf("(");} void Tconsume(){while(1) printf(")");}

如何在printf前后增加代码，使得打印的括号序列满足：

一定是某个合法括号序列的前缀
括号嵌套深度不超过n
同步：等到有空位的时候再打印左括号；等到能配对时再打印右括号。

这里左括号相当于生产资源（任务）、放入队列；右括号相当于从队列中取出资源（任务）执行。

能否用互斥锁来实现括号问题呢？

左括号：嵌套深度（队列）不足n时才能打印
右括号：嵌套深度（队列）>1时才能打印

下面的思路就是用互斥锁来实现这个生产者消费者的思想的：

#include "thread.h"
#include "thread-sync.h"

int n, count = 0;
mutex_t lk = MUTEX_INIT();

void Tproduce() {
  while (1) {
retry:
    mutex_lock(&lk);//首先创建一把互斥锁
    if (count == n) {//如果包里面的东西是满的，那么就一直得等待
      mutex_unlock(&lk);//并且放弃当前的锁
      goto retry;
    }
    count++;//一旦出来了，说明包里面有剩余空间
    printf("(");//可以打印
    mutex_unlock(&lk);//并且释放锁
  }
}

void Tconsume() {
  while (1) {
retry:
    mutex_lock(&lk);
    if (count == 0) {
      mutex_unlock(&lk);
      goto retry;
    }
    count--;
    printf(")");
    mutex_unlock(&lk);
  }
}

int main(int argc, char *argv[]) {
  assert(argc == 2);
  n = atoi(argv[1]);
  setbuf(stdout, NULL);
  for (int i = 0; i < 8; i++) {
    create(Tproduce);
    create(Tconsume);
  }
}

上面的代码可能造成的问题就是所有的进程都要访问一下锁，复杂度很大。这里的做法是将上述代码中的自旋变为睡眠，在完成操作的时候唤醒。

条件变量API：

wait(cv, mutex)：调用时必须保证已经获得mutex，释放mutex、进入睡眠状态
signal/notify(cv)：如果有线程正在等待cv，则唤醒其中一个线程。
broadcast/notifyAll(cv)：唤醒全部正在等待的cv进程。

主要的代码如下：

void Tproduce() {
  mutex_lock(&lk);//进去之前先给一把锁
  if (count == n) cond_wait(&cv, &lk);//如果当前的包是满的，那么得等待一会
  printf("("); count++; cond_signal(&cv);//传递消息给条件变量cv，唤醒正在等待其的变量
  mutex_unlock(&lk);//解开锁的占用
}

void Tconsume() {
  mutex_lock(&lk);
  if (count == 0) cond_wait(&cv, &lk);
  printf(")"); count--; cond_signal(&cv);
  mutex_unlock(&lk);
}

上面这种可能面临的问题如下：

我们需要对代码进行的改变有：

首先要将if改变为while，一直等待不满足的条件过去。

mutex_lock(&mutex);
while (!cond) {
  wait(&cv, &mutex);
}
assert(cond);
// ...
// 互斥锁保证了在此期间条件 cond 总是成立
// ...
mutex_unlock(&mutex);

当其他的线程条件可能被满足的时候，应该广播信号而不是单播：

1	broadcast(&cv);

信号量

回到上面的更衣室管理问题，我们完全没有必要限制手环的数量，可以让更多的人进入更衣室。

管理员可以持有任意数量的手环，更衣室容量的上限。先进入更衣室的同学先得到，手环用完之后才需要等同学出来。

线程可以任意变出一个手环：1.把手环看成是令牌；2.得到令牌的可以进入执行；3、可以随时创建令牌。

这里说的手环=令牌=一个资源=信号量semaphore。

P(&sem) - prolaag = try + decrease; wait; down; in
- 等待一个手环后返回
- 如果此时管理员手上有空闲的手环，立即返回
V(&sem) - verhoog = increase; post; up; out
- 变出一个手环，送给管理员

#include "thread.h"
#include "thread-sync.h"

sem_t fill, empty;

void producer() {
  while (1) {
    P(&empty);
    printf("(");
    V(&fill);
  }
}

void consumer() {
  while (1) {
    P(&fill);
    printf(")");
    V(&empty);
  }
}

int main(int argc, char *argv[]) {
  assert(argc == 2);
  SEM_INIT(&fill, 0);
  SEM_INIT(&empty, atoi(argv[1]));
  for (int i = 0; i < 8; i++) {
    create(producer);
    create(consumer);
  }
}

线程和协程

进程：进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。由于进程比较重量，占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大，但相对比较稳定安全。
线程：线程是指进程内的一个执行单元,也是进程内的可调度实体。线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈)，但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。线程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。
协程是一种用户态的轻量级线程，协程的调度完全由用户控制。从技术的角度来说，“协程就是你可以暂停执行的函数”。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。
协程和线程的区别：

\1) 一个线程可以多个协程，一个进程也可以单独拥有多个协程。

\2) 线程进程都是同步机制，而协程则是异步。

\3) 协程能保留上一次调用时的状态，每次过程重入时，就相当于进入上一次调用的状态。

4）线程是抢占式，而协程是非抢占式的，所以需要用户自己释放使用权来切换到其他协程，因此同一时间其实只有一个协程拥有运行权，相当于单线程的能力。

5）协程并不是取代线程, 而且抽象于线程之上, 线程是被分割的CPU资源, 协程是组织好的代码流程, 协程需要线程来承载运行, 线程是协程的资源, 但协程不会直接使用线程, 协程直接利用的是执行器(Interceptor), 执行器可以关联任意线程或线程池, 可以使当前线程, UI线程, 或新建新程.。

6）线程是协程的资源。协程通过Interceptor来间接使用线程这个资源。

4.1 操作系统的启动

4.1.1 引导扇区

计算机的工作方式就是取址执行，如下图：

计算机的工作方式

计算机上电之后的执行是怎么样的呢？

对于x86PC，开机经过以下步骤：

x86PC刚开机时CPU处于实模式（这个跟保护模式对应，实模式的寻址CS:IP（CS<<4 + IP），和保护模式不一样）
开机时，CS=0xFFFF;IP=0x0000
寻址0xFFFF0（ROM BIOS映射区）
检查RAM，键盘，显示器，软硬磁盘
将磁盘0磁道0扇区读入0x7c00处（0磁道0扇区就是操作系统的引导扇区）
设置cs=0x07c0，ip=0x0000（这个时候cs<<4+ip == ox7c00，也就是说要寻址到0x7c00处继续执行）

引导扇区有512字节，就是启动设备的第一个扇区，开机的时候按住del键就可以进入启动设备设置界面，可以设置为光盘启动。启动设备信息被设置在CMOS中，第一个扇区上存放着开机后执行的第一段我们可以控制的程序。

下面是引导扇区代码：bootsect.s：

这里：BOOTSEG = 0x07c0

INITSEG = 0x9000

SETUPSEG = 0x9020

start:
	mov ax, #BOOTSEG	mov ds, ax //将ds设置为0x7c0
	mov ax, #INITSEG	mov es, ax //将es设置为0x9000
	mov cx, #256
	sub si, si			sub di, di //构成段内偏移来构建地址，ds:di=ds<<4 + di = 0x7c00, es:ei = es<<4 + ei = 0x90000
	rep movw //移动256个字，512个字节，从0x7c00处移动到0x90000，腾出空间给后面用
	jmpi go, INITSEG //当前程序已经在0x9000处，偏移地址是go，是一个地方，也就是跳到go处继续执行

go:
	mov ax, cs //cs = 0x9000
	mov ds, ax	mov es, ax	mov ss, ax	mov sp, #oxff00
load_setup://载入setup模块
	mov dx, #0x0000		mov cx, #0x0002		mov bx,	#0x0200
	mov ax, #0x0200+SETUPLEN	int 0x13 //BIOS中断
	jnc ok_load_setup
	mov dx, #0x0000
	mov ax, #0x0000 //复位
	int 0x13
	j	load_setup //重读

上面的load_setup代码中，0x13是BIOS读磁盘扇区的中断：ah=0x02-读磁盘，al=扇区数量(SETUPLEN=4)，ch=柱面号，cl=开始扇区，dh=磁头号，dl=驱动器号，es:bx=内存地址。

操作系统启动盘

首先int 0x13就是定位到BIOS读磁盘扇区，cx=#0x0002，低八位是从第二个扇区开始读，也就是上图中蓝色的部分。ax=#0x0200+SETUPLEN就是开始读磁盘，读的就是4个，刚好对应于setup的四个扇区。（其实也就是高八位ah，低八位al）。es:bx对应于段基址+段内偏移，bx=#0x0200，cs=0x9000，那么移动到的位置就是#0x90200

ok_load_setup://载入setup模块
	mov dl, #0x00		mov ax, #0x0800 //ah=8获得磁盘参数
	int 0x13		mov ch, #0x00 		mov sectors, cx
	mov ah, #0x03		xor bh, bh		int 0x10 //读光标
	mov cx, #24		mov bx, #0x0007 //7是显示属性
	mov bp, #msg1		mov ax, #1301		int 0x10 //显示字符
	mov ax, #SYSSEG //SYSSEG=0x1000
	mov es, ax
	call read_it //读入system模块
	jmpi 0, SETUPSEG

那么int 0x10处显示的是什么字符呢？它访问的是#msg1处的内容，这部分的数据如下：

sectors: .word 0 //磁道扇区数
msg1: .byte 13, 10
	  .ascii "Loading system..."
	  .byte 13, 10, 13, 10

read_it: mov ax, es		cmp ax, #ENDSEG		jb ok1_read
	ret

ok1_read:
	mov ax, sectors
	sub ax, sread //sread是当前磁道已读取扇区数，ax未读扇区数
	call read_track //读磁道

可以转到setup执行了，jmpi 0, SETUPSEG。

4.1.2 setup模块

setup模块将完成os启动前的设置。

start: mov ax, #INITSEG 	mov ds, ax		mov ah, #0x03
	xor bh, bh 		int 0x10//取光标位置 	mov ah, #0x88 	int 0x15 	mov [2], ax ...//获取0x15扩展内存的大小，后面那句话将9000左移四位加2就是90002，也就是扩展内存数
	cli //不允许中断
	mov ax, #0x0000		cld
do_move: mov es, ax 	add ax, #0x1000
	cmp ax, #0x9000 	jz end_move
	mov ds, ax 	sub di, di//di=0
	sub si, si//si=0
	mov cx, #0x8000//将这段空间留给操作系统用
	rep //将system模块移到0地址
	movsw
	jmp do_move

将setup移到0地址处后，操作系统要让硬件进入保护模式了，保护模式下int n和cs: ip解释不再和实模式一样。用GDT将cs: ip变为物理地址。

GDT：全局描述表，是在保护模式下必不可少的一个数据结构。在实模式下，对一个内存地址的访问是通过segment:offset的方式进行的，也就是段基址左移四位+偏移地址就是我们要寻址的空间。

而到了保护模式时，内存的管理分为两种：段模式和页模式，其中页模式也是基于段模式的。在保护模式下，地址仍然采用的是段地址：偏移地址的寻址方式，只不过段的概念发生了变化。保护模式下段值仍然由原来的16位的cs、ds寄存器表示，但是他们此时只是一个索引，这些索引指向一个数据结构的表项，表项中定义了一个段的起始地址、界限、属性等内容，这个数据结构就是$GDT$，每个表项就是描述符。

切换到保护模式也就是从16位机（1M寻址空间）到32位机（4G寻址空间）。进入保护模式的代码如下：

进入保护模式的代码

最重要的三句代码就是上面的标红的代码，首先将ax设置为最后一位是1，再将ax赋值给cr0，也就是将cr0寄存器的最后一位置为1，启动保护模式，jmpi 0，8将cs=8，用来检查gdt。

保护模式下的地址翻译和中断处理

上面的图片就是保护模式下的地址翻译，首先根据cs找到GDT表中的位置，GDT表中会有个映射，然后加上ip之后就是表示的物理地址。

IDT：中断描述符表，将每个1异常或者中断向量分别与他们的处理过程联系起来。IDT表也是由8字节长描述符组成的一个数组。总之给定一个n，它会帮你找到中断处理函数的入口。

所以我们必须初始化一些映射在GDT表中，初始化的程序如下：

GDT表的初始化

所以上述的jmpi 0,8最终寻址的地方其实是0，

jmpi指令的移动

system模块（目标代码）中的第一部分代码是head.s，head.s是一段在保护模式下运行的代码，setup是进入保护模式，head是进入之后的初始化。下面的代码是32位的汇编，因为进入了保护模式了。

startup_32:
	movl $0x10, %eax 	mov %ax, %ds 	mov %ax, %es
	mov %as, %fs 	mov %as, %gs //指向gdt的0x10项(数据段)
	lss _stack_start, %esp //设置栈（系统栈）
	call setup_idt
	call setup_gdt
	xorl %eax, %eax

1: incl %eax
	movl %eax, 0x000000 	cmpl %eax, 0x100000
	je lb //0地址处和1M地址处相同(A20没有开启),就死循环
	jmp after_page_tables //页表
setup_idt: 	lea ignore_int, %edx
	movl $0x00080000, %eax 	 movw %dx, %ax
	leaa _idt, %edi 	movl %eax, (%edi)

在设置也表之后呢，执行下面的语句：

设置页表之后

main函数

4.2 系统调用的实现

硬件提供了主动进入内核的方法，对于Intel x86来说，就是中断指令int，int指令将使CS中的CPL改成0，进入内核。这是用户程序发起的调用内核代码的唯一方式。

系统调用的核心：

用户程序中包含一段包含int指令的代码
操作系统写中断处理，获取想调程序的编号。
操作系统根据编号执行相应代码。