总线

栈

理解桟的定义需要注意：首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

参考文章

栈的应用

递归

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

递归过程退回的顺序是它前行顺序的逆序。显然这符合栈的存储方式。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压如栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳就可以了。

例如：

1
2
3
4
5
6
7
8

long f(long m,long n)
{
    long sum;
    if(m==0) sum=n+1;
    else if(n==0) sum=f(m-1,1);
    else k=f(m-1,f(m,n-1));
return sum;
}

非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

long f(long m,long n)
{
  listStack<long> k;    //用链栈来实现
  k.push(m);
  k.push(n);
  long sum;
 while(k.length()!=1)  //栈中只有一个元素时退出循环
  {
      n=k.pop();      //出栈 
       m=k.pop();
      if(m==0) k.push(n+1);
      else if(n==0)
      {
        k.push(m-1);
        n=1;
        k.push(n);
      }
      else
      {
        k.push(m-1);
        k.push(m);
        k.push(n-1);

      }
  }
  sum=k.pop();  
return sum;
}

队列

注意，在大多数的课本中，队尾指向的是队列的最后一个元素的下一个元素。

“假溢出现象”：

在顺序存储结构中，队列的不断出队列会导致这些出去的元素的地址将无法使用（因为后续入队列的元素的地址将往后排）。

循环队列和链队列的优劣势

对于循环队列与链队列的比较，可以从两方面来考虑：

• 从时间上，其实它们的基本操作都是常数时间，即都为0(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。

• 对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

• 总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据，可以有效的利用资源。但是用循环队列有个小麻烦，不好判断数列是为空还是为满；

链队列就不存在上面的问题。“循环队列”最大优点就是节省空间和少分配空间，而链队列多了一点点地址存储开销。

矩阵

矩阵的压缩存储

按照我们正常的矩阵存储，其实对内存的空间开销还是比较大的，所以我们自然就想到了压缩存储。

那么什么是矩阵的压缩存储？其实就是为很多个值相同的元素只分配一个存储空间。对零元素不分配存储空间。那么这个值相同的元素，我们很容易就想到了线性代数的特殊矩阵，比如单位阵，对角阵，对称阵等，我们这里说三个。分别是对称矩阵、上下三角矩阵、和对角矩阵。

对称矩阵：

就是矩阵的行和列对调之后还是和原来的矩阵相等。那么这种矩阵就是对称矩阵。

ok，我们知道了对称矩阵的特性，所以要运用要压缩存储上，因为对称矩阵有这样的特性，所以我们存储的时候就不用将元素全部存储，我们只需要存储这个镜面一半的元素就可以了。比如上面这个，我们只存158234这些元素即可，相同的元素不要重复存储。

稀疏矩阵：

其实就是说矩阵中的元素为0的特别多。

那么我们再存储的时候其实存储分零元素是最能节省空间的。但是稀疏矩阵的位置又没有前面哪些矩阵的规律，所以我们存储的时候就干脆把元素的行列下标也存进去。形成一个三元组。也就是行下标、列下标、元素值。

注意三元组的存储方式牺牲了随机存储的优点。

组成原理-存储系统

基本术语

• 存储器：存放程序和数据的器件。
• 存储位：存放一个二进制数位的存储单元，是存储器最小的存储单位。
• 存储字：计算机可寻址（作为一个整体存入或取出）的最小信息单位。
• 存储单元：存放一个存储字的若干个记忆单元组成一个存储单元。
• 存储体：大量存储单元的集合组成存储体。
• 存储单元地址：存储单元的编号。
• 字编址：对存储单元按字编址。
• 字节编址：对存储单元按字节编址。
• 寻址：通过地址寻找数据，从对应地址的存储单元中访存数据。

存储系统分类

按存储介质分类

半导体存储器：用半导体器件组成的存储器。
磁表面存储器：用磁性材料做成的存储器。（磁盘、磁带）
激光存储器：信息以刻痕的形式保存在盘面上，用激光束照射盘面，靠盘面的不同反射率来读出信息。

按存取方式分类

RAM

随机存储器（RAM，Random Access Memory）：可随机访问任意存储单元，且存取时间与存储单元的物理位置无关。主要充当高速缓冲存储器和主存储器。

半导体随机存储器

动态随机存储器（DRAM）

只能将数据保持很短的时间。为了保持数据，DRAM 使用电容存储，所以必须隔一段时间刷新（Refresh）一次，如果存储单元没有被刷新，存储的信息就会丢失，关机就会丢失数据。常用于主存储器。DRAM 采用地址复用技术，地址线是原来的 1/2，且地址信号分行、列两次传送。相对于 SRAM 来说，DRAM 具有容易集成、价位低、容量大和功耗低等优点，但 DRAM 的存取速度比 SRAM 慢，一般用来组成大容量主存系统。

DRAM 保存的信息会自动消失（易失性存储器），为此，每隔一段时间必须刷新，通常取 2ms，这个时间称为刷新周期。常用的刷新方式有 3 种：集中刷新、分散刷新和异步刷新。

　　（1）集中刷新：指在一个刷新周期内，利用一段固定的时间，依次对存储器的所有行进行逐一再生，在此期间停止对存储器的读写操作，称为“死时间”，又称访存“死区”。集中刷新的优点是读写操作时不受刷新工作的影响，因此系统的存取速度较高；缺点是在集中刷新期间（死区）不能访问存储器。

补充一点：为什么刷新与存取不能并行？
因为内存就一套地址译码和片选装置，刷新与存取有相似的过程，它要选中一行——这期间片选线、地址线、地址译码器全被占用着。同理，刷新操作之间也不能并行——意味着一次只能刷一行。

　　（2）分散刷新：把对每行的刷新分散到各个工作周期中。这样，一个存储器的系统工作周期分为两部分：前半部分用于正常读、写或保持；后半部分用于刷新某一行。这种刷新方式增加了系统的存取周期，如存储芯片的存取周期为 0.5μs，则系统的存取周期为 1μs。分散刷新的优点是没有死区；缺点是加长了系统的存取周期，降低了整机的速度。

即在每个存取操作后绑定一个刷新操作。延长了存取周期，这样存取周期就成了0.5μs + 0.5μs =1μs。但是由于与存取操作绑定，就不需要专门给出一段时间来刷新了。这样，每有128个读取操作，就会把0-127行全部刷新一遍。故每隔128μs 就可将存储芯片全部刷新一遍，即刷新周期是1μs×128=128μs远短于2ms，而且不存在停止读/写的死时间，但是存取周期长了，整个系统速度降低了。（分散刷新的刷新周期128μs ，其实不需要这么频繁，会导致浪费）

　　（3）异步刷新：异步刷新是前两种方法的结合，它既可以缩短“死时间”，又能充分利用最大刷新间隔为 2ms 的特点。具体做法是将刷新周期除以行数，得到两次刷新操作的时间间隔 t，利用逻辑电路每隔时间 t 产生一次刷新请求。这样可以避免使 CPU 连续等待过长的时间，而且减少了刷新次数，从根本上提高了整机速度。

具体操作为：在2ms内对128行各刷新一遍

即每隔15.6μs刷新一行(2000μs/128≈15.6μs)，而每行刷新的时间仍为0.5μs。这样，刷新一行只能停止一个存取周期，但对每行来说，刷新间隔时间仍为2ms，而死时间为0.5μs。（相对每一段来说，是集中式刷新，相对整体来说，是分散式刷新）

如果将DRAM的刷新安排在CPU对指令的译码阶段，由于这个阶段CPU不访问存储器，所以这种方案既克服了分散刷新需独占0.5μs用于刷新，使存取周期加长且降低系统速度的缺点，又不会出现集中刷新的访存“死区”问题，从根本上上提高了整机的工作效率。

DRAM 的刷新需注意以下问题：（1）刷新对 CPU 是透明的，即刷新不依赖外部的访问；（2）动态 RAM 的刷新单位是行，故刷新操作时仅需要行地址；（3）刷新操作类似于读操作，但又有所不同。刷新操作仅给栅极电容补充电荷，不需要信息输出。另外，刷新时不需要选片，即整个存储器中的所有芯片同时被刷新。

　　SRAM 和 DRAM 都满足断电内容消失，但需要刷新的只有 DRAM，而 SRAM 不需要刷新。

静态随机存储器（SRAM）

所谓的 “静态”，指这种存储器只要保持通电，里面储存的数据就可以恒常保持。相对之下，DRAM 里面储存的数据需要周期性地 Refresh。然而，当电力供应停止（关机）时，储存的数据还是会消失，所以也称为 Volatile Memory（易失性存储器），这与在断电后仍能储存数据的 ROM 或闪存不同的。但是 SRAM 也有它的缺点，即它的集成度较低，功耗较 DRAM 大，相同容量的 DRAM 内存可以设计为较小的体积，但是 SRAM 却需要很大的体积。同样面积的硅片可以做出更大容量的 DRAM，因此 SRAM 显得更贵。常用于高速缓存。

静态存储器结构

译码部分：

找到静态存储器中对应的存储单元。

总体：

串行访问存储器（SAS）

对存储单元进行 读/写 操作时，需按其物理地址的先后顺序寻址，包括顺序存取存储器（如磁带，SAM）与直接存取存储器（如磁盘,DAM）。

顺序存取存储器（SAM）

是完全的串行访问，顺序存取存储器的内容只能按照某种顺序存取，存取时间的长短与信息在存储体上的物理位置有关，其特点是存取速度缓慢。如：磁带，读写时要待磁带移动到合适位置之后才能顺序读写。由于价格便宜，主要用于数据备份容灾系统。

直接存取存储器（DAM）

是部分的串行访问，如：HHD 机械硬盘，对信息的存取有两步操作。首先，磁头直接移动到目标区域（磁道），然后再从磁道的合适位置开始读写，它介于顺序存取和随机存取之间。主要用于辅助存储器。

只读存储器（ROM）

存储器的内容只能随机读出而不能写入。信息一旦写入存储器就固定不变，即使断电，内容也不会丢失。因此，通常用它存放固定不变的程序、常数和汉字字库，甚至用于操作系统的固化。它与随机存储器可共同作为主存的一部分，统一构成主存的地址域。

由 ROM 派生出的存储器也包含可反复重写的类型，ROM 与 RAM 的存取方式均为随机存取。广义上的只读存储器已可已可通过电擦除等方式进行写入，其“只读”的概念没有保留，但仍然保留了断电内容保留、随机读取特性，但其写入速度比读取速度慢得多。

掩膜式只读存储器（MROM）

MROM 写入后任何人无法改变其内容

一次可编程只读存储器（PROM）

PROM 允许用户利用专门的设备（编程器）写入自己的程序，一旦写入，内容就无法改变。

可擦除可编程只读存储器（EPROM）

EPROM不仅可以由用户利用编程器写入信息，而且可以对其内容进行多次改写。需要修改 EPROM 内容时，先将其全部内容擦除，然后编程。

闪速存储器（Flash Memory）

固态硬盘（Solid State Drives

按信息的可保存性分类

非永久记忆（易失性）的存储器：掉电后数据消失的存储器，如：半导体读/写存储器 RAM。
永久性记忆（非易失性）的存储器：掉电后仍能保存信息的存储器，如：磁性材料做成的存储器以及半导体 ROM。

若某个存储单元所存储的信息被读出时，原存储信息被破坏，则称为破坏性读出；若读出时，被读单元存储信息不被破坏，则称为非破坏性读出，具有破坏性读出的存储器，每次读出操作后，必须紧接一个再生的操作，以便恢复被破坏的信息。

三层存储结构

几个问题：

1、cpu速度慢：cpu访问的是主存，但是主存的速度慢于cpu的读取速度。导致cpu的速度慢。

2、主存容量不足

解决方法：

1、cache：解决cpu速度慢的问题（一般是集成在cpu上）

2、辅存解决主存容量小的问题

存储系统层次结构主要体现在 “Cache - 主存” 层次和 “主存 - 辅存” 层次。前者主要解决 CPU 和主存速度不匹配的问题，后者主要解决存储系统容量的问题

主存和 Cache 之间的数据调动是由硬件自动完成的，对所有程序员均是透明的；而主存和辅存之间的数据调动则是由硬件和操作系统共同完成的，对应用程序员是透明的。

主存储器：主存（又称内存）

用来存放计算机运行期间所需的大量程序和数据，CPU 可以直接随机地对其进行访问，也可以和告诉缓冲存储器（Cache）及辅助存储器交换数据，其特点是容量较小、存取速度较快、单位价格较高。

• 半导体存储器、DRAM、非永久记忆存储器
• 特性：“可随机访问任意存储单元” 和 “掉电即失去数据”，这些特性均服务于冯诺依曼体系 “存储程序” 的核心理想。

辅助存储器：辅存

又称外存储器（外存），是主存储器的后援存储器，用来存放当前暂时不用的程序和数据，以及一些需要永久性保存的信息，它不能与 CPU 直接交换信息。其特点是容量极大、存取速度较慢、单位成本低。

高速缓冲存储器：cache

位于主存和 CPU 之间，用来存放正在执行的程序段和数据，以便 CPU 能高速地使用它们。Cache 地存取速度可与 CPU 的速度匹配，但存储容量小、价格高。目前的高档计算机通常将它们制作在 CPU 中。

存储器的性能指标

存储器有 3 个主要性能指标，即存储容量、单位成本和存储速度。这 3 个指标相互制约，设计存储器系统所追求的目标就是大容量、低成本和高速度。

具体可见《王道》

主存中的数据组织

主存：随机访问存储器，包含读/写存储空间和只读存储空间

存储字长：主存的一个存储单元所包含的二进制位数。按照字节为单位。

数据存储与边界的关系

按边界对齐，方便访问和读取。但是会浪费空间。

大端和小端存储方式

大端：最高字节地址作为数据地址

小端：最低字节地址作为数据地址

大端模式更符合人的读写习惯，但是小端模式更符合计算机的处理。

CPU和主存储器连接

• 连接由总线来支持：包括数据总线、地址总线和控制总线。

• CPU 通过 AR（地址寄存器）& AB（地址总线）、DR（数码寄存器）& DB（数据总线）和主存进行数据传输。

若 AR 为 K 位字长，表示 CPU 的寻址宽度，即允许主存包含有 2K 个可寻址存储单位；
若 DR 为 n 位字长，则表示在一个存储周期内，CPU 和主存之间通过总线进行 n 位数据传输。
控制总线包括控制数据传输的读（READ）、写（WRITE）和表示存储器功能完成的（READY）的三种控制线。

cpu向内存写数据的时，相当于将数据写入内存地址中。数据的地址经过地址总线送给译码器，译码器的有效输出送给锁存单元的使能端，而cpu中寄存器数据通过数据总线送给锁存单元的输入端，实现数据存入内存。

cpu读内存数据时，相当于将内存地址中的数据读入cpu。数据的地址经过地址总线送给译码器，译码器的有效输出送给锁存单元的使能端，此时锁存单元将输出端数据送入数据总线，再通过数据总线送入cpu。

cpu与内存通过数据总线交换数据，数据总线是双向的。

CPU读取主存数据

当 CPU 从存储器读取一个存储字时，CPU 必须指定该存储字的地址，将该地址送到 AR 再经 AB 送到存储器，同时，CPU 通过控制线发送 READ 信号到存储器。此后，CPU 等到存储器通过控制线发来一个 READY 信号，表示已经完成了数据的读，并将数据经 DB 放到 DR 上了，CPU 再从 DR 取出相应的数据。以此来完成了一个存储器字的读与取。

CPU存放数据到主存

CPU 为了存放一个字到存储器，首先将存储字在存储器中的存放地址通过 AR 经 AB 发送到存储器，并将存储字放到 DR，同时发出一个 WRITE 信号到存储器。此后，CPU 等到接收 READY 信号。存储器会根据 AB 收到的地址来存放 DB 接收到的存储字，然后通过 READY 控制线发送 READY 信号给 CPU 接收。以此完成了一个存储字的存放。

可见，主存和 CPU 之间采用的是异步工作方式，以 READY 信号表示以此访存操作的结束。

存储扩展

CPU 的数据线数与存储芯片数据位数不一定相等，通常进行位扩展，用多个存储芯片对字长进行扩充，使数据位数与 CPU 的数据线数相等。可用的技术方法有位扩展法、子扩展法和字位同时扩展法。

分为字扩展和位扩展以及字位扩展。

位扩展

地址线不变，但是数据线分成了四个部分。因为位表示的是字的深度，字的地址还是和没扩展前一样的。

仅采用位扩展时，各个芯片连接地址线的方式一样，而连接数据线的方式不一样，某一时刻选中所有芯片，所以片选信号线要连接到所有芯片。

字扩展

由于位数没有发生变化，所以数据线是没有发生变化的。但是由于字的数量（厚度）增加了，所以地址线要增加。

片选信号是选择字扩展中的字的厚度中的那一层。

字扩展将存储芯片的地址线、数据线、读写控制线相应并联，而由片选信号来区分芯片的地址范围

仅采用字扩展时，各个芯片连接地址线方式相同，连接数据线的方式也相同，但在某一时刻只需选中部分芯片，所以通过片选信号或采用译码器设计连接到相应的芯片。

字位扩展

字位同时扩展就是既增加存储字的数量，又增加存储字长。

采用字位同时扩展时，各个芯片连接地址线的方式相同，但连接数据线的方式不同，而且需要通过片选信号或采用译码器设计连接到相应的芯片。

双端口 RAM 和多模块存储器

双端口 RAM 是指同一个存储器有左、右两个独立的端口，分别具有两组相互独立的地址线、数据线和控制线，允许两个独立的控制器同时异步地访问存储单元。当两个端口的地址不相同时，在两个端口上进行读写操作一定不会发生冲突。

两个端口同时存取存储器地同一地址单元时，会因数据冲突造成数据存储或读取错误。两个端口对同一主存操作有以下4 种情况：

1. 两个端口不同时对同一地址单元存取数据。
2. 两个端口同时对同一地址单元读出数据。
3. 两个端口同时对同一地址单元写入数据。
4. 两个端口同时对同一地址单元操作，一个写入数据，另一个读出数据。

其中，第 1 种和第 2 种情况不会出现错误；第 3 种情况会出现写入错误；第 4 种情况会出现读出错误。

多体交叉存储器

由多个存储模块构成。基本思想是：在不提高存储器效率、不扩展数据通路位数的前提下，通过存储芯片的交叉组织，提高CPU单位时间内访问的数据量，从而缓解快速的CPU与慢速的主存之间的速度差异。

分为高位和低位两种多体交叉存储器。

高位多体交叉存储器

可以看到的是，用高位段地址经过译码后产生片选信号，选择存储体。低位段地址直接选择一个存储体内的不同存储单元。

特点

• 相邻的地址在同一个存储体中
• 不同存储体的地址不相邻

问题

因为连续的地址在同一个存储体中，无法实现存储体并行工作

低位多体交叉存储器

用低位段地址经过译码后产生片选信号，选择存储体。高位段地址直接选择一个存储体内的不同存储单元。

存储流水线访问

其中：存储周期T=0至W0 时间，表示的是存储体存入数据的时间。

连续并行读取时间是：0至W0 +W0至W1 （此时第一个存储体的数据读出） +W1至W2 （此时第二个存储体的数据读出） +W2至W3

Cache的基本原理

cache，中译名高速缓冲存储器，其作用是为了更好的利用局部性原理，减少CPU访问主存的次数。简单地说，CPU正在访问的指令和数据，其可能会被以后多次访问到，或者是该指令和数据附近的内存区域，也可能会被多次访问。因此，第一次访问这一块区域时，将其复制到cache中，以后访问该区域的指令或者数据时，就不用再从主存中取出。

程序访问的局部性原理包括时间局部性和空间局部性。

• 空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的
• 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息

主要分析的是CPU和主存之间的Cache

cache的工作过程

Cache和主存都被分成若干大小相等的块（Cache块又称为Cache行），每块由若干字节组成，块的长度称为块长（Cache行长）。所以Cache中的块数要远少于主存中的块数，它仅保存主存中最活跃的若干块的副本。

CPU与Cache之间的数据交换以字为单位，而Cache与主存之间的数据交换则以Cahce块为单位。

• 当CPU发出读请求时，若访存地址在Cache中命中，就将此地址转换成Cache地址，直接对Cahce进行读操作，与主存无关；若访存地址在Cache中未命中，则需访问主存，并把此字所在的块一次性地从主存调入Cache，若此时Cache已满，则需根据某种 替换算法，用这个块替换Cache中原来的某块信息。

  • Q：如何判断数据在Cache中？

    ​ A：使用相联存储器（注意，这里是在相联存储器中进行分析的，没有进入到cache块中）

  • Q：Cache中的数据是有效的吗？

    ​ A：使用cache块中的vaild

  

• 当CPU发出写请求时，若Cache命中，有可能会遇到Cache与主存中的内容不一致的问题，此时需要根据某种 写策略 解决这个问题。

  • 在写穿式Cache中，数据更新时，在写入缓存之后，立即也将数据写入内存，如果此时请求指定的地址没有对应的缓存，那么直接写入内存。所以每次操作总会执行：

    ​ 第一步，CPU将数据写入Cache；
    　　 第二步，将Cache数据传送到Memory中相应的位置；

  • 在写回式Cache中，数据更新时，在写入缓存之后，不会立即更新对应的内存，只有当该缓存被用于其他的内存数据（即数据被替换出缓存）时，被修改的缓存中的数据才会被覆盖式地写入到对应的内存中。

    ​ 并不是每次执行步骤1后都执行步骤2操作。

  • Q：写回前，主存的数据是新的吗？（因为没有及时的写回主存中）

    ​ A：使用cache块中的dirty

cache的地址划分

因为cache是以块划分的，所以对主存地址，需要进行二次划分。

为了解决上述的三个问题，cache的结构需要进行相应的改变。

CPU将地址置入相联存储器中，如果数据在cache中，去cache中对应的地址查找，如果不再就直接对主存进行访问。

相联存储器

作用：判断CPU要访问的内容是否在Cache中，在的话，会给出相应内容在cache中的地址。

存放查找表 (独立硬件，不在缓存中)
存储容量 = 查找表容量 = cache块数 * 表项大小
cache中用于存放块表，虚拟存储器中存放段表、页表
（valid, Key， Value ）
( 有效位, 主存块地址 ， Cache块地址） 注：value不一定是必要的

CPU给出的块地址与查找表中某单元相同且有效位为1表示命中

步骤(对应的是系统的读过程)

• CPU给出主存地址（块地址，块内地址）

• 主存块地址为关键字查找相联存储器中的查找表

• 如相符表示副本在cache中，命中，访问cache

• 否则数据缺失，访问主存

  • 将数据所在块副本调入cache（块交换—局部性）

  • 载入副本过程可能引起替换

  • 更新查找表，记录当前数据块地址

  • cache缺失时系统等待数据调入

基本结构如下

检索寄存器从地址中剥离Key

当明确查找的在Cache中时，符合寄存器会记录要查找的地址的位置

此处的存储体就是cache中的标记存储体

由下图可以看到：key包含了tag和offset。

cache地址映射和变换方法

这里的地址映射是指：主存空间映射到cache的地址空间。

在使用相联存储器得知数据在cache中后，接下来需要得知主存数据如何放置到cache行中。此外，cache满后应该如何处理？如何实现保持cache和主存的一致性？

全相联映射

只有一个组，就是全相联。不用hash来确定组，直接挨个比对高位地址，来确定是否命中。可以想见这种方式不适合大的缓存。想想看，如果4M 的大缓存　linesize为32Byte，采用全相联的话，就意味着410241024/32 = 128K 个line挨个比较，来确定是否命中，这是多要命的事情。高速缓存立马成了低速缓存了。

映射算法：主存的数据块可映射到cache任意行同时将该数据块地址对应的标记存储体中保存。

主存地址=块地址（标记）+块内地址（字）

因为只有一组，cache中的所有行标记会全部送入相联存储器中进行比较。如果命中的话，从cache中剥离出具体要访问的那个字。反之，会根据cpu给出的原始地址再次访问主存。

直接映射

每个组只有一个line，选中组之后不需要和组中的每个line比对，因为只有一个line。这样导致了cache的利用率低，块内冲突率高，但是淘汰算法（后来的赶走之前的）简单，适合大容量cache。

映射算法：cache共n行，主存第j快映射到cache行号为i=jmod (n)即映射到特定行

主存调入cache中的位置由行地址决定。

先看索引，取出对应的标识放入相联存储器中比较。命中与否的结果与上述相同。可以很明显的看出比较的内容变少了。

组相联映射

cache分成多个组，每个组分成多个行。所谓8路组相连（ 8-way set associative）的含义是指，每个组里面有8个行。

cache分组（每组包含的行数相同），主存以cache分组标准将块分组（两者数量相同）

映射算法：cache共n组，主存第j块号映射到cache的组号是i=jmod（n）。即主存的数据块映射到cache特定组的任意行

我们知道，cache的容量要远远小于主存，主存和cache肯定不是一一对应的，那么主存中的地址和cache的映射关系是怎样的呢？

拿到一个地址，首先是映射到一个组里面去。如何映射？取内存地址的中间几位来映射。

举例来说，data cache: 32-KB, 8-way set associative, 64-byte line size

Cache总大小为32KB，8路组相连（每组有8个line），每个line的大小linesize为64Byte,OK，我们可以很轻易的算出一共有32K/8/64=64 个组。

对于32位的内存地址，每个line有2^6 = 64Byte，所以地址的【0，5】区分line中的那个字节。一共有64个组。我们取内存地址中间6为来hash查找地址属于那个组。即内存地址的【6，11】位来确定属于64组的哪一个组。组确定了之后，【12，31】的内存地址与组中8个line挨个比对，如果【12，31】为与某个line一致，并且这个line为有效，那么缓存命中。

先看索引，取出索引组的全部行对应的标识放入相联存储器中比较。命中与否的结果与上述相同。

替换算法

cache存储空间被占满后需要替换数据块。

直接映射是不需要替换算法的。全相联映射替换算法适用于全部行。组相联映射替换算法适用组内全部行

① 先进先出算法(FIFO)

基本思想：按照数据块进入Cache的先后决定替换的顺序，即在需要进行替换时，选择最先

​ 被调入Cache中的块作为替换块。这种方法要求为每块记录它们进入Cache的先

​ 后次序。

优点：FIFO算法系统开销较小。

缺点：是不考虑程序访问的局部性，可能会把一些需要经常使用的块（如循环程序块）也作

为最早进入Cache的块而替换掉，因此，可能导致Cache的命中率不高。

② 近期最少使用(LRU)算法

基本思想：将近期内长久未被访问过的行换出。为此，每行设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1，因此它是未访问次数计数器。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。

优点：这种算法显然保护了刚调入Cache的新数据，符合cache工作原理，因而使cache有较高

的命中率。LRU算法硬件实现简单

③ 最不经常使用(LFU)算法

基本思想：将一段时间内被访次数最少的那行数据换出。为此，每行设置一个计数器，新新

​ 调入行的数据从0开始计数，每访问一次被访行的计数器增1。当需要替换时，对

​ 这些特定行的计数值进行比较，将计数值最小的行换出。

缺点：一段期间访问情况不能严格反映近期访问情况。例如特定行中的A、B两行，A行在期间的前期多次被访问而后期未被访问，但累积计数值很大，B行是前期不常用而后期却正被频繁访问，但可能由于累积计数小于A行而被LFU算法换出了。

④ 随机替换算法

基本思想：需要进行替换时，从特定的行位置中随机地选取一行进行替换。

优点：硬件实现最容易，而且速度也比前几种策略快。

缺点：随意换出的数据很可能马上又要用，从而降低命中率和cache工作效率。但这个负面效应随着cache容量增大会减少，模拟研究表明随机替换策略的功效只是稍逊于LFU和LRU。

随机替换法

替换算法的抖动

调出去的那块就是即将访问的那块数据。

要避免抖动，需要在程序行为上避免。

虚拟存储器

解决了程序大小大于内存的限制问题

虚拟存储器处于“主存-辅存”存储层次。

• 辅存—–逻辑地址
• 主存—–物理地址

页式虚拟存储器

采用页表判断cpu访问的内容是否在主存，如果在辅存，则调用其内容到主存中。

转换：

MMU用于指出页表在内存中的位置，通过与VPN结合就能访问到页表中与虚拟页号VPN相对应的物理页号PPN。实现虚拟地址到物理地址的转换。

页表常驻在内存中。保存有虚拟页号和物理页号的对应关系。

进程开始要访问一个地址，它可能会经历下面的过程

1、每次我要访问地址空间上的某一个地址，都需要把地址翻译为实际物理内存地址
2、所有进程共享这整一块物理内存，每个进程只把自己目前需要的虚拟地址空间映射到物理内存上
3、进程需要知道哪些地址空间上的数据在物理内存上，哪些不在（可能这部分存储在磁盘上），还有在物理内存上的哪里，这就需要通过页表来记录
4、页表的每一个表项分两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址（如果在的话）
5、当进程访问某个虚拟地址的时候，就会先去看页表，如果发现对应的数据不在物理内存上，就会发生缺页异常
6、缺页异常的处理过程，操作系统立即阻塞该进程，并将硬盘里对应的页换入内存，然后使该进程就绪，如果内存已经满了，没有空地方了，那就找一个页覆盖，至于具体覆盖的哪个页，就需要看操作系统的页面置换算法是怎么设计的了。

当每个进程创建的时候，内核会为进程分配4G的虚拟内存，当进程还没有开始运行时，这只是一个内存布局。实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射）。这个时候数据和代码还是在磁盘上的。当运行到对应的程序时，进程（拿着虚拟地址）去寻找页表，发现页表中地址没有存放在物理内存上，而是在磁盘上，于是发生缺页异常，于是将磁盘上的数据拷贝到物理内存中。

另外在进程运行过程中，要通过malloc来动态分配内存时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

可以认为虚拟空间都被映射到了磁盘空间中（事实上也是按需要映射到磁盘空间上，通过mmap，mmap是用来建立虚拟空间和磁盘空间的映射关系的）

TLB

虚实地址转换过程中存在的问题：

两次访问主存：第一次拿页表项判断是否在主存中，第二次得到数据。

5，6步骤是为了替换主存中的对应物理地址的内容。

为了减少访问主存的次数。设置TLB，不去主存拿页表。故TLB能节省一次CPU访问主存的次数。

于是TLB设计成页表映像的一部分。

1、CPU拿着虚拟地址访问MMU（为了将虚拟地址中剥离出的虚页号与MMU中的页表基址寄存器结合得到物理内存地址）

2、MMU拿着虚页号VPN访问TLB

首先，先去TLB中根据标志Tag寻找，假如找到了并且有效位是1，说明TLB命中了，那么直接就可以从TLB中获取该虚拟页号对应的物理页号。假如有效位是0，说明该页不在内存中，这时候就发生缺页异常，CPU需要先去外存中将该页调入内存并将页表和TLB更新。

假如在TLB中没有找到，那么就去页表（Page Table）中寻找（以虚拟页号为索引），假如找到了并且有效位是1，那么就可以取出对应的物理页号。假如有效位是0，说明该页不在内存中，这时候就发生缺页异常，CPU需要先去外存中将该页调入内存并将页表和TLB更新。

假如在页表中没有找到，也是缺页。同意会执行上述的缺页处理。

（不管从哪获取到物理页号，都可以根据规则组拼成实际物理地址，然后就可以访存去数据啦）

此处TLB tag是因为TLB只是页表的一个子集，不能全部遍历页表中的每一项。所以要增加tag判断与虚页对应的物理页是否存在。（具体见上面的引用部分）

段式虚拟存储器

以段为单位。一般将主存空间按照实际运行程序中的段来划分。由此 段可大可小。

段的独立性—易于编译、管理、修改和维护，也便于多道程序共享

各段的长度不同，给主存的分配带来麻烦

段式管理容易产生碎块，浪费主存空间

段页式虚拟存储器

程序按模块分段

段再分成长度固定的页。

程序调入调出按页面来进行

程序共享保护按段进行

兼备段式，页式管理的优点

在地址映像中需要多次查表

RAID

核心技术：将数据条带化后的存放在不同磁盘上，通过多磁盘的并行操作提高磁盘系统的读写速率。使用基于异或运算为基础的校验技术恢复损坏的数据

最左边的盘就是冗余盘。是用于备份的。

RAID0

数据以条带方式均匀分散在各磁盘上。

没有冗余，没有校验技术，任一磁盘坏了就GG。

RAID1

数据采用镜像的冗余方式，同一个数据有多份拷贝

RAID3/4

专用校验盘。

RAID5

RAID10

RAID01

一些习题

-万继光 - 百度文库 - wenku.baidu.com.png)

-万继光 - 百度文库 - wenku.baidu.com-1595315230835.png)-万继光 - 百度文库 - wenku.baidu.com.png)

计算机系统概述

计算机发展历程

计算机系统的层次结构

M4
高级语言级，它时面向用户的为方面用户编写应用程序而设置的。这一级由各种高级语言编译程序支持和执行。如C语言,c++等。它们编写的程序会由相应的编译器编写成汇编语言。实现高级语言的语法和语义等的执行过程对该层的程序员是透明的。

M3
汇编语言级，它给程序人员提供一种符号式的程序设计语言，以减少程序编写的复杂性。一个机器都有自己的汇编语言，上层的高级语言首先被翻译成汇编语言，再进一步翻译（翻译过程由机器系统软件中的汇编软件完成）成机器直接识别的机器语言。机器通过执行机器语言程序来最终完成用户所要求的功能。

M2
操作系统级，它由操作系统程序实现。这些操作系统由机器指令和广义指令组成，广义指令是操作系统定义和解释的软件指令，所以这一级也成为混合级，计算机中所有机器指令的集合成为这台计算机的指令系统，指令系统又分为精简指令系统（RISC)和复杂指令系统（CISC)。

操作系统对用户程序使用机器的各种资源（CPU、存储器、输入输出设备等）进行管理和分配。例如，当某一用户程序需要运行时，首先由操作系统将其调入内存中，这其中需要操作系统为其分配内存空间进行存储。再如某程序需要使用某一输出设备进行结果的输出时，需要操作系统为其提供对该设备的控制等。

M1
一般机器级，也称机器语言级，它由微程序解释机器指令系统，这一级也是硬件级，如二进制代码01010100101人真的很难看懂的 。

M0
微程序设计级或逻辑电路级，这是一个实在的硬件级，由硬件直接执行，如果某一个应用程序直接用微指令来编写，那么可再这一级上运行应用程序。

这一层的核心是计算机硬件控制单元。控制单元会逐条接收来自上层的机器指令，然后分析译码，产生一系列的操作控制信号，并由这些控制信号控制下层的逻辑部件按照一定的时间顺序有序地工作。

解释程序由于是翻译一句执行一句，是不会有目标程序生成的

计算机的组成

一个完整的计算机系统，是由硬件系统和软件系统两大部分组成的。

硬件系统

参考文章

主要分为主机（CPU+主存储器）和外设（I/O设备）两部分，是指那些构成计算机系统的物理实体，它们主要由各种各样的电子器件和机电装置组成。
从ENIAC(世界上第一台计算机)到当前最先进的计算机，硬件系统的设计采用的都是冯·诺依曼体系结构。

• 运算器:　负责数据的算术运算和逻辑运算，即数据的加工处理。

• 控制器:　是整个计算机的中枢神经，分析程序规定的控制信息，并根据程序要求进行控制，协调计算机各部分组件工作及内存与外设的访问等。
  运算器和控制器统称中央处理器（即CPU)

  • 处理单元（Processing Unit，PU）：又称数据通路（Datapath）或运算器，包含了算术逻辑单元（Arithmetic Logic Unit，ALU）和处理器寄存器（Processor Register）。用于完成各种算术和逻辑运算。

  • 控制器单元（Control Unit，CU）：包含了指令寄存器（Instruction Register）和程序计数器（Program Counter）。用于控制程序的流程（程序流），通常是条件判断和跳转。

  PU 和 CU 就组成了 CPU（Central Processing Unit，中央处理器）。

• 存储器：包括用于存储数据（Data）和指令（Instruction）的主存储器和容量更大但速度却慢的外部存储器。

• 输入设备:　实现将程序、原始数据、文字、字符、控制命令或现场采集的数据等信息输入到计算机。

• 输出设备:　实现将计算机处理后生成的中间结果或最后结果（各种数据符号及文字或各种控制信号等信息）输出出来。

冯诺依曼体系结构的核心思想是存储程序原理：

将程序指令以代码形式提前输入计算机主存储器，然后按照其在存储器中的首地址执行程序的第一条指令，以后就按该程序的规定顺序执行其他指令，直至程序执行结束

计算机按照此原理应该具有：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能

软件系统

• 主要分为系统软件和应用软件，是指计算机证运行所需的各种各样的计算机程序。
  • 系统软件：OS、DBMS、语言处理程序、分布式软件系统、网络软件系统、标准库程序、服务性程序等
• 系统软件的任务是既要保证计算机硬件的正常工作，又要使计算机硬件的性能得到充分发挥，并且为计算机用户提供一个比较直观、方便和友好的使用界面。

操作系统（Operation System，OS）

没有安装操作系统的计算机，通常被称为裸机
如果想在 裸机 上运行自己所编写的程序，就必须用机器语言书写程序。

操作系统的作用

• 是现代计算机系统中 最基本和最重要 的系统软件
• 主要作用是管理好硬件设备，并为用户和应用程序提供一个简单的接口，以便于使用
• 而其他的诸如驱动程序、编译程序、数据库管理系统，以及大量的应用软件，都直接依赖于操作系统的支持

其他系统程序

• 驱动程序：真正管理和控制硬件的程序，往往操作系统会携带一些默认版本
• 语言处理程序：也称为编译程序，作用是把程序员用某种编程语言(如Python)所编写的程序，翻译成计算机可执行的机器语言。机器语言也被称为机器码，是可以通过CPU进行分析和执行的指令集。

计算机硬件的主要技术指标

• 机器字长：CPU一次能处理数据的位数，一般和CPU的寄存器位数有关

  • 太短了会使得计算机运行的速度变慢
  • 太长了会使得硬件的造价太高，但是可以提高精度和数的表示范围

• 存储容量：存储单元个数X存储字长

-万继光 - 百度文库 - wenku.baidu.com.png)

线性表

线性表的定义

线性表是具有相同特性的数据元素的一个有限序列。线性表属于逻辑结构中的线性结构，它包括顺序表、链表、栈、队列等。

线性表在存储结构上有顺序存储和链式存储两种方式，但不管哪种存储方式，它们的结构都有如下特点：

1. 均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一个线性表来说，数据元素必须具有相同的数据类型和长度。每个数据元素都是单个元素。
2. 有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的”第一个”和”最后一个”数据元素。除了第一个和最后一个外，其他元素前面均只有一个数据元素(直接前驱)，后面均只有一个数据元素(直接后继)。
3. 有限性：表中元素的个数是有限的
4. 抽象性：只讨论表中元素间的关系，不考虑元素究竟表示什么内容

有序表

我们很容易把有序表与顺序表、链表相提并论，其实这是错误的。因为顺序表、链表是根据线性表的存储结构(顺序或链式)来划分概念的，而有序表是根据线性表的数据元素的数值大小来划分概念，故有序表与顺序表、链表不是相互独立的，而是内容互相交错的。

有序表是指表中所有数据元素的数值以递增或递减方式有序排列，是数据元素的数值的有序性。
有序表只描述元素之间的逻辑关系，故为逻辑结构，因此有序表既可以顺序存储也可以链式存储。

例如，数组int array[3]=[1,2,3];是顺序存储结构的有序表。因为是数组，所以是顺序存储结构；因为数据元素[1,2,3]是从小到大排列，故是有序表。而单链表1->2->3则是链式存储结构的有序表。由这个例子可见：有序表与顺序表、链表不是相互独立的，而是内容互相交错的，我们不能把他们相提并论。

线性表的顺序存储（顺序表）

顺序表是顺序存储结构的线性表，是把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中指定位置开始的一块连续的物理地址的空间中。由于顺序表的逻辑地址与其物理地址皆相邻，故称为顺序表。

编程语言中的数组就是顺序表的一个典型实例。

表中的任一元素的地址都可以通过这个公式得到：$LOC(d_i)=LOC(d_1)+(i-1)*L 　1≤i≤n $其中，L是元素占用存储单元的长度。

顺序表的特点

优点：

1.空间利用率高，数据是连续存放，命中率比较高

2.不用为表示结点间的逻辑关系而增加额外的开销

3.顺序表可以按照元素下标**==随机访问==**

缺点：

1.在插入和删除时大约移动平均一半的元素，对比较大的顺序表操作时效率很低

最好情况是：在表尾插入和删除
最坏情况是：在表头插入和删除

2.需要预先分配足够大的空间，估计过大，导致空间浪费；估计过小，会造成溢出

此处需要注意的是：数组的动态分配还是顺序存储结构，并不是链式存储。数组的动态分配是开辟一块更大的存储空间来替换原本的存储空间。

**时间复杂度 :**插入和删除操作为O(n)。

查找操作：
如果是按照元素序号和首地址来查找的话，时间复杂度是O(1)；

如果是按照元素值查找的话，时间复杂度是O(n)。

线性表的链式存储(链表)

链表是链式存储结构的线性表，是用任意一组物理地址来存储数据元素，而数据元素之间的逻辑关系通过指针来表示。所以它的存储结构可以是连续的，也可以不是连续的。
一般我们说的链表都是不连续的。有一种用数组来表示的特殊链表，叫做静态链表，它的存储结构就是连续的。

优点：

1.插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。

2.没有空间限制,存储元素无上限,只与内存空间大小有关.

3.动态分配内存空间，不用事先开辟内存

4.是内存的利用率变高

缺点：

1.占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多)

2.查找速度比较慢，因为在查找时，需要循环链表。

**时间复杂度 :**查找操作为O(n) ,插入和删除操作为O(1)。

线性表

线性表的定义

线性表是具有相同特性的数据元素的一个有限序列。线性表属于逻辑结构中的线性结构，它包括顺序表、链表、栈、队列等。

线性表在存储结构上有顺序存储和链式存储两种方式，但不管哪种存储方式，它们的结构都有如下特点：

1. 均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一个线性表来说，数据元素必须具有相同的数据类型和长度。每个数据元素都是单个元素。
2. 有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的”第一个”和”最后一个”数据元素。除了第一个和最后一个外，其他元素前面均只有一个数据元素(直接前驱)，后面均只有一个数据元素(直接后继)。
3. 有限性：表中元素的个数是有限的
4. 抽象性：只讨论表中元素间的关系，不考虑元素究竟表示什么内容

线性表的顺序存储（顺序表）

顺序表是顺序存储结构的线性表，是把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中指定位置开始的一块连续的物理地址的空间中。由于顺序表的逻辑地址与其物理地址皆相邻，故称为顺序表。

编程语言中的数组就是顺序表的一个典型实例。

表中的任一元素的地址都可以通过这个公式得到：$LOC(d_i)=LOC(d_1)+(i-1)*L 　1≤i≤n $其中，L是元素占用存储单元的长度。

顺序表的特点

优点：

1.空间利用率高，数据是连续存放，命中率比较高

2.不用为表示结点间的逻辑关系而增加额外的开销

3.顺序表可以按照元素下标**==随机访问==**

缺点：

1.在插入和删除时大约移动平均一半的元素，对比较大的顺序表操作时效率很低

最好情况是：在表尾插入和删除
最坏情况是：在表头插入和删除

2.需要预先分配足够大的空间，估计过大，导致空间浪费；估计过小，会造成溢出

此处需要注意的是：数组的动态分配还是顺序存储结构，并不是链式存储。数组的动态分配是开辟一块更大的存储空间来替换原本的存储空间。

**时间复杂度 :**插入和删除操作为O(n)。

查找操作：
如果是按照元素序号和首地址来查找的话，时间复杂度是O(1)；

如果是按照元素值查找的话，时间复杂度是O(n)。

线性表的链式存储(链表)

链表是链式存储结构的线性表，是用任意一组物理地址来存储数据元素，而数据元素之间的逻辑关系通过指针来表示。所以它的存储结构可以是连续的，也可以不是连续的。
一般我们说的链表都是不连续的。有一种用数组来表示的特殊链表，叫做静态链表，它的存储结构就是连续的。

优点：

1.插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。

2.没有空间限制,存储元素无上限,只与内存空间大小有关.

3.动态分配内存空间，不用事先开辟内存

4.是内存的利用率变高

缺点：

1.占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多)

2.查找速度比较慢，因为在查找时，需要循环链表。

**时间复杂度 :**查找操作为O(n) ,插入和删除操作为O(1)。

4.有序表

我们很容易把有序表与顺序表、链表相提并论，其实这是错误的。因为顺序表、链表是根据线性表的存储结构(顺序或链式)来划分概念的，而有序表是根据线性表的数据元素的数值大小来划分概念，故有序表与顺序表、链表不是相互独立的，而是内容互相交错的。

有序表是指表中所有数据元素的数值以递增或递减方式有序排列，是数据元素的数值的有序性。
有序表只描述元素之间的逻辑关系，故为逻辑结构，因此有序表既可以顺序存储也可以链式存储。

例如，数组int array[3]=[1,2,3];是顺序存储结构的有序表。因为是数组，所以是顺序存储结构；因为数据元素[1,2,3]是从小到大排列，故是有序表。而单链表1->2->3则是链式存储结构的有序表。由这个例子可见：有序表与顺序表、链表不是相互独立的，而是内容互相交错的，我们不能把他们相提并论。

基本概念和术语

基本概念

区别和详细解释

1、数据(Data)：描述客观事物属性的数、字符及所有能被输入到计算机中并被计算机程序识别和处理的符号的集合。

数据不仅包括整形、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。 数据必须具备两个前提：
（1）可以输入到计算机中；
（2）能被计算机程序处理。对于整型、实型等数值类型，可以进行数值计算；而对于字符数据类型，就需要非数值的处理；而声音、图像、视频等可以通过编码的手段变成字符数据来处理。

2、数据对象(Data Object)：具有相同性质的数据元素的集合。数据对象是数据的一个子集。

什么叫性质相同呢？是指数据元素具有相同数量和类型的数据项，比如人 这个例子，都有姓名、生日、性别等相同的数据项。 既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们将数据对象简称为数据。

3、数据元素(Data element)：数据的基本单位，也称结点(node)或记录(record)。

比如 畜类 牛、马、羊、鸡、猪、狗等动物当然就是畜类的数据元素。

4、数据项(Data item)：构成数据元素的不可分割、有独立含义的最小单位，也称域(field)。

一个数据元素由若干个数据项组成。

5、数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。

数据元素都不是孤立存在的，它们之间存在某种关系，这些数据元素之间的关系称为结构(structure)。

数据结构三要素

逻辑结构（数据元素之间的关系）+数据结构（数据结构在计算机中的表示）+数据的运算（运算的定义和实现）。

PS:通常需要用（数据对象、数据关系、基本操作集）这样的三元组来定义数据结构

逻辑结构、数据结构的区分方法

逻辑结构与数据结构的区分判定方法：当一个结构(如数组、链表、树、图)，在逻辑结构中只有一种定义，而在存储结构中却有两种或多种定义，那么这个结构就属于逻辑结构；相反，当此结构在原有基础上加上了某种限定词(如二叉树->线索二叉树)，使得其在存储结构中只有一种定义，那么这个结构就称为数据结构。

举例1：栈属于什么结构？
分析：栈在逻辑结构中只能属于线性结构，而在存储结构中它可以使用顺序存储（数组），也可以使用链式存储（链表），所以说栈是一种逻辑结构。

举例2：线索二叉树属于什么结构？
分析：首先因为二叉树既可以顺序存储又可链式存储，故可以得到二叉树是一种逻辑结构。但是线索二叉树是二叉树加上限定词线索后的链表结构（不能用顺序存储），也就是说，线索二叉树在计算机内部的只有一种存储结构，所以线索二叉树是数据结构。

逻辑结构和数据结构的区别点在于：数据的逻辑结构是独立于在计算机中的存储结构的，数据的存储方式有多种不同的选择。例如栈是一种逻辑结构，它可以用顺序存储也可以用链式存储；而数据结构是既可以描述逻辑结构又可以描述存储结构和数据运算，必须包含这三种元素。所以像顺序表、哈希表、单链表都是数据结构。

算法和算法分析

程序 = 数据结构 + 算法

算法（algorithm） 是为了解决某类问题而规定的一个有限长的操作序列。

算法的五个特性：

• 有穷性：指算法在执行完有限步骤之后，自动结束而不会出现死循环，并且每个步骤都在可接受时间内完成。
• 确定性：算法的每一步骤都具有正确的含义，不会出现二义性。
• 可行性：算法的每一步都是可行的，也就是说，每一步都能通过执行有限次数完成。
• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。

算法设计的要求：

• 正确性：没有歧义，能正确反映问题需求、能够得到问题的正确答案。
• 可读性：便于阅读、理解和交流。
• 健壮性：当输入数据不合法时，也能做出相关处理，而不至于出现莫名其妙的结果。
• 高效性和低存储量需求：时间高效、空间高效。

衡量算法效率的度量方法分为时间复杂度和空间复杂度。

时间和空间复杂度

时间复杂度：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）= O（f（n））。它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐进复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。这样用大写 O（） 来体现算法时间复杂度的记法，我们称为大O记法。

推导大O阶的方法

• *用常数1取代运行时间中的所有加法常数。*
• *在修改后的运行次数函数中，只保留最高阶项。*
• *如果最高阶项存在且不是1，则去除与这个项目相乘的常数。*
• *最后得到的结果就是大O阶。*

参考文章

算法的空间复杂度：通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S（n）= O（f（n）），其中，n为问题规模，f（n）为语句关于n所占存储空间的函数。

存储和存取

存取结构：随机存取和顺序存取

随机存取

随机存取（直接存取,Random Access）指的是当存储器中的数据被读取或写入时，所需要的时间与该数据所在的物理地址无关。

随机存取的微观现实例子就是编程语言中的数组。
随机存取的宏观现实例子就是我们的随机存取存储器(RAM:Random Access Memory)，通俗的说也就是我们电脑的内存条。因为RAM利用电容存储电荷的原理保存信息，所以RAM可以高速存取，且与物理地址无关。

顺序存取

顺序存取(Sequential Access)是一种按记录的逻辑顺序进行读、写操作的存取方法，所需要的时间与该数据所在的物理地址有关。顺序存取表现为:在存取第N个数据时，必须先访问前（N-1）个数据。
顺序存取的微观现实例子就是数据结构中的链表。
顺序存取的现实例子就是我们的录音磁带、光盘、机械硬盘里面的磁盘。磁带、光盘、磁盘上的数据分别存储在不同扇区、不同磁道上，磁盘的读写磁头通过切换不同扇区和磁道来读取物理地址不连续的数据时，该过程中要经过不同扇区和不同磁道上的无关数据，磁盘的读写磁头在切换不同扇区和磁道所需时间也不同，故为顺序存取。

顺序存储

顺序存储是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接关系来体现。

顺序存储的主要优点：

• 节省存储空间。因为分配给数据的存储单元全用存放数据元素（不考虑c/c++语言中数组需指定大小的情况），数据元素之间的逻辑关系没有占用额外的存储空间。
• 可实现对数据元素的随机存取(直接存取)。即每一个数据元素对应一个元素下标，由该元素下标可以直接计算出来数据元素的物理存储地址。

顺序存储的主要缺点：

• 不便于数据修改。对数据元素的插入、删除运算时，可能要移动一系列的数据元素。

• 产生磁盘碎片。因为顺序存储只能使用相邻的一整块存储单元，因此会产生较多的磁盘碎片。

  顺序存储的典型实例就是编程语言中的数组。例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如下图所示：

数组中的所有元素存储在一个连续性的内存块中，并通过数组的首地址和元素下标来访问。因此一个数组就是由1个数组首地址和N个数组元素构成，数组不需要像链表一样，链表的每个节点必须存储下一个结点的物理地址，在存储同样多的数据下，数组比链表节省空间。

数组可通过数组的首地址和元素下标来直接存取数组中的没每一个元素，而不需要像链表一样，在存取第N个链表结点的数据时，必须先访问前（N-1）个链表结点。

但对数组的数据元素的插入、删除运算时，可能要移动一系列的数据元素，特别的麻烦，因此顺序存储结构的数组不便于修改。

随机存储

在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。它不要求逻辑上相邻的元素在物理位置上也相邻，而是借助指示元素存储地址的指针来表示元素之间的逻辑关系。

随机存储的主要优点：

• 不会产生磁盘碎片。因为随机存储不要求逻辑上相邻的元素在物理位置上也相邻，而是借助指示元素存储地址的指针来表示元素之间的逻辑关系，因此不会产生磁盘碎片。
• 数据修改方便。对数据元素的插入、删除运算时，随机存储不必移动结点，只要改变结点中的指针。

随机存储的主要缺点：

• 占用空间大。随机存储的每个结点都由数据域和指针域组成，所以相同空间内假设全存满，顺序存储比随机存储可存更多数据。

• 查找结点时链式存储要比顺序存储慢，且只能实现顺序存取。

随机存储——链式存储

链式存储是随机存储最典型的代表，因此链式存储的定义、优点和缺点就是2.2随机存储中的定义、优点和缺点。

随机存储——索引存储

除建立存储结点信息外，还建立附加的索引表来标识结点的地址，索引表由若干索引项组成，索引项的一般形式是(关键字，地址)。

索引存储的主要优点：检索速度快。
索引存储的主要缺点：增加了附加的索引表,会占用较多的存储空间。

随机存储——散列存储

散列存储，又称Hash存储，是一种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术，即根据元素的关键字直接计算出该元素的存储地址。

散列存储的主要优点：检索、增加和删除节点的操作更快。
散列存储的主要缺点：若散列函数不好，则可能出现元素存储单元的冲突。

电脑磁盘碎片的定义、产生原理和清理原因

参考文章

文件碎片的定义

电脑碎片即磁盘碎片，磁盘碎片应称为文件碎片。文件碎片是由于文件被分散保存到整个磁盘的不同地方，而不是连续地保存在磁盘连续的簇中而形成的。

文件碎片产生的原因

百度百科中对文件碎片产生列出了以下三大原因：

当应用程序所需的物理内存不足时，一般操作系统会在硬盘中产生磁盘临时交换文件，用该文件所占用的硬盘空间虚拟成内存。虚拟内存通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上。虚拟内存管理程序会对硬盘频繁读写，产生大量的碎片，这是产生硬盘碎片的主要原因。
还有一种情况就是当中间的一个扇区内容被删除后，新写入一个较小的文件，这样在这个文件两边就会出现一些空间，这时候再写入一个文件，两段空间的任意一部分都不能容纳该文件，这时候就需要将文件分割成两个部分，碎片再次产生了。
最常见的就是下载电影之类的大文件，这期间大家一般都会处理一下其它事情，而下载下来的电影文件被迫分割成若干个碎片存储于硬盘中。因此下载是产生碎片的一个重要源头。还有就是经常删除、添加文件，这时候如果文件空间不够大，就会产生大量的文件碎片，随着文件的删改频繁，这种情况会日益严重。
文件碎片产生的原因：

清理文件碎片的原因(为什么要清理文件碎片?)

知道了文件碎片的产生原因之后，我们还有必要了解一下程序运行时磁盘的读写动作。一般运行一个程序时，磁盘驱动器的磁头所做的工作是先搜索该程序运行必需的文件，然后读取数据，最后做读后处理——将数据传送至磁盘高速缓存(Cache)和内存中。搜索时间在硬盘性能指标中被称为平均寻道时间（Average seek time），单位为毫秒（ms），当下主流硬盘的平均寻道时间小于9.5ms。如果能将应用程序的相关文件放在磁盘的连续空间内，磁头搜索的时间将会减少很多。读取时也是如此，磁盘读取位于磁头下方扇区的数据所需时间仅为将磁头移到另一地点再读取相同数据所需时间的五分之一。读盘时，系统先检查数据是否在高速缓存中，如果有则直接读取；如果没有则访问磁盘，也就是读盘。当需要多次读取同一份数据时，Cache的作用很大，但对于第一次读取某个文件，Cache就无能为力了。于是搜索时间和读取时间在很大程度上影响着程序执行的效率。

而磁盘碎片整理是将电脑使用中产生的碎片和冗杂的文件重新整理，让碎片文件融为一体，从而减少了磁盘的寻道时间，因此整体上使得电脑的运行速度得以提升。

机械硬盘/固态硬盘都需要清理文件碎片吗？

先说结论：机械硬盘需要清理文件碎片，固态硬盘不需要清理文件碎片。

机械硬盘需要清理文件碎片的原因已经在上述的四、清理文件碎片的原因(为什么要清理文件碎片?)解释了，因为磁盘碎片整理是将电脑使用中产生的碎片和冗杂的文件重新整理，让碎片文件融为一体，从而减少了磁盘的寻道时间，因此整体上使得电脑的运行速度得以提升。

而为什么说固态硬盘不需要磁盘碎片整理呢？

固态硬盘的擦写次数是有限的。闪存完全擦写一次叫做1次P/E，25nm的固态硬盘寿命约是3000次P/E。碎片整理会大大减少固态硬盘的使用寿命。其实，固态硬盘的垃圾回收机制就已经是一种很好的“磁盘整理”，再多的整理完全没必要。Windows的“磁盘整理”功能是机械硬盘时代的产物，并不适用于固态硬盘。
固态硬盘电荷寻道耗时几乎为0。固态硬盘不用磁头，又因为固态硬盘的存储单元是基于闪存颗粒的电子存储，所以寻道时间几乎为0。持续写入的速度非常惊人，大部分固态硬盘读写速度在500MB/s。
固态硬盘具有TRIM功能。这一功能充当了SSD的军师，它会发出指令让系统告诉固态硬盘哪些数据块不再使用了，否则SSD控制器不知道可以回收这些闲置的数据块。从某种意义上来说，这个功能已经是承担了磁盘碎片整理的工作了。

符号表

符号表的作用

• 用来存放有关标识符（符号）的属性信息

  • 这些信息会在编译的不同阶段用到
  • 符号表的内容将用于静态语义检查和产生中间代码
  • 在目标代码生成阶段，符号表是对符号名进行地址分配的依据
  • 对一个多遍扫描的编译程序，不同遍所用的符号表也会有所不同，因为每遍所关心的信息或所能得到的信息会有差异

• 用来体现作用域与可见性信息

符号的常见属性

① 符号名

② 符号的类型：常量、变量、过程/函数、类的名称等

③ 符号的存储类别：常量、变量的数据类型，过程函数的返回类型等【决定了其存储格式和允许的操作】

④ 符号的作用域及可视性

⑤ 符号变量的存储类别和存储分配信息
存储类别确定其分配的区域，静态或动态数据区，堆区或栈区，存储分配信息如单元的大小，相对于某个存储区域的偏移位置等等

⑥ 符号的其它属性

• 数组内情向量
• 记录结构的成员信息
• 函数及过程的形参

符号表的实现

针对符号表的常见操作

• 创建符号表：在编译开始，或进入一个作用域
• 插入表项：在遇到新的标识符声明时进行
• 查询表项：在引用标识符时进行
• 修改表项：在获得新的语义值信息时进行
• 删除表项：在标识符成为不可见或不再需要它的任何信息时进行
• 释放符号表空间：在编译结束前或退出一个作用域

实现符号表的常用数据结构

• 一般的线性表
  如：数组，链表，等
• 有序表
  查询较无序表快，如可以采用折半查找
• 二叉搜索树
• Hash表

作用域与符号表组织

• 所有作用域共用一个全局符号表

• 每个作用域都有各自的符号表

作用域与可见性

• 嵌套的作用域（nested scopes）

• 开作用域与闭作用域（相应于程序中特殊点）

  • 该点所在的作用域为当前作用域
  • 当前作用域与包含它的程序单元所构成的作用域称为开作用域（open scopes）,即嵌套重叠的作用域
  • 不属于开作用域的作用域称为闭作用域（close scopes）

• 常用的可见性规则（visibility rules）

  • 在程序的任何一点，只有在该点的开作用域中声明的名字才是可访问的
  • 若一个名字在多个开作用域中被声明，则把离该名字的某个引用最近的声明作为该引用的解释
  • 新的声明只能出现在当前作用域

作用域与符号表组织

• 作用域与多符号表组织
  • 每个作用域都有各自的符号表
  • 维护一个符号表的作用域栈，每个开作用域对应栈中的一个入口，当前的开作用域出现在该栈的栈顶
  • 当一个新的作用域开放时，新符号表将被创建，并将其入栈
  • 在当前作用域成为闭作用域时，从栈顶弹出相应的符号表

静态语义分析

静态语义： 刻画程序在静态一致性或完整性方面的特征；仅当程序通过了静态语义检查，才能完成后续的中间代码生成和目标代码优化。

动态语义： 刻画程序执行时的行为。比如除数为0，数组越界等错误，需要生成相应代码

主要任务

• 类型检查（type checks）
  检查每个操作是否遵守语言类型系统的定义

• 名字的作用域（scope）分析
  建立名字的定义和使用之间联系

• 控制流检查（flow-of-control checks）
  控制流语句必须使控制转移到合法的地方（如break语句必须有合法的语句包围它）

• 唯一性检查（uniqueness checks）
  很多场合要求对象只能被定义一次（如枚举类型的元素不能重复出现）

• 名字的上下文相关性检查（name-related checks）
  某些名字的多次出现之间应该满足一定的上下文相关性

类型检查

类型检查程序（type checker）：负责类型检查

• 验证程序的结构是否匹配上下文所期望的类型
• 为相关阶段搜集及建立必要的类型信息
• 实现某个类型系统（type system）

中间代码生成

源程序的不同表示形式,也称为中间表示。其作用：

• 源语言和目标语言之间的桥梁，避开二者之间较大的语义跨度，使编译程序的逻辑结构更加简单明确
• 有利于编译程序的重定向
• 有利于进行与目标机无关的优化

常见的中间表示的形式

有不同层次不同目的之分。常见中间表示形式：

• AST（Abstract syntax tree，抽象语法树）
  DAG（Directed Acyclic Graph,有向无圈图，通过优化技术得到改进型 AST）
• TAC（Three-address code,三地址码，四元式）
• P-code （特别用于 Pasal 语言实现）
• Bytecode（Java 编译器的输出, Java 虚拟机的输入）
• SSA（Static single assignment form，静态单赋值形式）【静态单赋值形式，程序中的名字只有一次赋值。】

生成抽象语法树

(1) 树的根节点是开始符

(2) 所有的内节点都是非终结符

(3) 所有的叶子节点都是终结符

生成三地址码

通过遍历语法树或在归约时，生成三地址码，后续要用到的四元式：

• 赋值语句 x := y op z （op 代表二元算术/逻辑运算）

• 赋值语句 x := op y （op 代表一元运算）

• 复写语句 x := y （y 的值赋值给 x）

• 无条件跳转语句 goto L （无条件跳转至标号 L）

• 条件跳转语句 if x rop y goto L （rop 代表关系运算）

• 标号语句 L : （定义标号 L）

• 过程调用语句序列 param x1 … param xn call p,n

• 过程返回语句 return y （y 可选，存放返回值）

• 下标赋值语句 x := y[i] 和 x[i] := y （前者表示将地址 y 起第i个存储单元的值赋给 x，后者类似）

• 指针赋值语句 x := *y 和 *x := y

赋值语句及算术表达式的语法制导翻译

中间代码（中间语言）

中间代码也叫中间语言（Intermediate code /language）是：源程序的一种内部表示，不依赖目标机的结构。介于源语言和目标语言的中间语言形式。

中间代码的特点：

1、独立于机器

2、复杂性界于源语言和目标语言之间

中间代码的优点

1、使得编译程序的逻辑结构清楚；

2、利于不同目标机上实现同一种语言；

3、利于进行与机器无关的优化；

中间语言将编译程序分为前端和后端有利于编译程序的移植。例如：保持编译程序的前端不变，替换其后端，就可以将原来的某个语言的编译程序改造成同一个语言，不同目标机器的程序。如果保持后端不变，替换前端，就可以将某个机器上的某个语言的编译程序改造成同一个机器上的另一个语言的编译程序。

常用的中间语言

• 后缀式：逆波兰表示
• 图表示：抽象语法树AST、有向无环图DAG
• 三地址代码：
  • 三元式
  • 四元式
  • 间接三元式

后缀式

逆波兰表示法即为后缀表示法，而默认我们使用的表达式是中缀表示法

逆波兰式的使用：需使用额外的标识符栈。顺序扫描逆波兰表达式的时候，遇到标识符直接入栈。

遇到运算符时：

1. 根据运算符目数，从栈顶取出相应数目的标识符做运算，并把运算结果压栈
2. 运算结束时，标识符栈应该只剩下一个元素，且为运算结果

图表示法

抽象语法树和有向无环图

抽象语法树

在语法树中去掉一些对翻译不必要的信息后，获得的更有效的源程序的中间表示，这种经过变换后的语法树称为抽象语法树。

在抽象语法树中，操作符和关键字都不作为叶子节点出现，而是把它们作为内部节点，即这些叶子节点的父节点。

有向无环图

对表达式中的每个子表达式，DAG都有一个结点，一个内部结点代表一个操作符，他的孩子代表操作数。

在一个DAG中代表公共子表达式的节点具有多个父结点（与抽象语法树中公共子表达式被表示为重复的子树不同）

树形表示

树形表示和三元式表示非常相似，如a:=b∗c+b∗d表示为：

注意赋值表达式中被赋值对象在树的左孩子节点位置

单目运算−T1直接表示成：

三地址代码表示

三地址代码可以看作是抽象语法树或有向无环图的一种线性表示

三地址代码最基本的用法形式:

x:=y op z

​ 其中x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号。每个语句的右边只能有一个运算符。

三地址代码可以看成是抽象语法树一种线性表示

三地址代码可以看成是DAG的一种线性表示

三地址码的各种形式：

1
2
3
4
5
6
7

1.x:=yop z          x := op z                         x:=y
2.Goto L             ifx relopy gotoL         if a goto L
3【传参、转子】.Param x         call p,n                           
4【返回语句】.return y
5【索引赋值】.x:=y[i]             x[i]:=y
6【地址和指针赋值】.x:=&y            x:=*y                  *x:=y     
赋值语句翻译为三地址码的属性文法

三元式

三元式$(op,A_1,A_2)$

op为运算符
A1为第一运算对象
A2为第二运算对象

例如$a:=b∗c+b∗d$表示为：
$(1)(∗,b,c)\
(2)(∗,b,d)\
(3)(+,(1),(2)) 这里用(1)和(2)来表示中间计算结果的显式引用\
(4)(:=,(3),a)( 这里相当于a:=(3)$

而单目运算的−b可以表示成(−,b,/)

四元式

四元式实际上是一种“三地址语句”的等价表示，是一个带有四个域的记录结构。

四元式$(op,A_1,A_2,R)$

op为运算符
A1为第一运算对象
A2为第二运算对象
R为运算结果

例如$a:=b∗c+b∗d$的四元式表示：
$(1)(∗,b,c,t_1)\
(2)(∗,b,d,t_2)\
(3)(+,t_1,t_2,t_3)\
(4)(:=,t_3,−,a)$

和三元式的差别在于，四元式对中间结果的引用必须通过给定的名字(临时变量)

它的三地址码写法为：
$t_1:=b∗c\
t_2:=b∗d\
t_3:=t_1∗t_2\a:=t_3$

三元式和四元式的比较

相同点：

1、无论在一个三元式序列还是四元式序列中，各个三元式或四元式都是按相应表达式的实际运算顺序出现的；

2、对同一表达式而言，所需的三元式或四元式的个数一般都是相同的。

不同点：

1、由于三元式没有result字段，且不需要临时变量，故三元式比四元式占用的存储空间少；

2、在进行代码优化处理时，常常需要挪动一些运算的位置，这对于三元式序列来说是很困难的，但对于四元式来说，由于四元式之间的相互联系是通过临时变量来实现的，所以，更改其中一些四元式给整个系列带来的影响就比较小。

三地址代码-间接三元式

建立两个与三元式有关的表格，一个称为三元式表，用于存放各三元式本身；另一个称为执行表，它按照三元式的执行顺序，依次列出相应各三元式在三元式表中的位置，也就是说我们用一个三元式表连同执行表来表示中间代码。通常我们称这种表示方法为间接三元式。

三元式

$x：=（a+b）c\
b：=a+b\
y：=c（a+b$

（1）（+，a，b） （5） （+，a，b）
（2）（ *，（1），c） （6）（ *，c，（5））
（3）（：=，x，（2）） （7）（：=，y，（6））
（4）（：=，b，（1））

间接三元式

执行表 三元式表

（1） （1）（+，a，b）
（2） （2）（*，（1），c）
（3） （3）（：=，x，（2））
（4） （4）（：=，b，（1））
（1） （5）（：=，y，（2））
（2）
（5）

三元式与间接三元式之间的区别

1、由于间接三元式在执行表中已经依次列出每次要执行的那个三元式，若其中有相同的三元式，则仅需在三元式表中保存其中之一，即三元式的项数一般比执行表的项数少；

2、当进行代码优化需要挪动运算顺序时，则只需对执行表进行相应地调整，而不必再改动三元式本身，这样，就避免了前面讲到的因改变三元式的顺序所引起的麻烦。

赋值语句的翻译

布尔表达式的翻译

布尔表达式在程序设计语言中有两个作用：

1. 计算逻辑值
2. 用于改变控制流语句中的条件表达式

控制流语句包含循环、分支两大类。

通常我们只考虑如下文法生成的布尔表达式：
$E→EandE∣EorE∣notE∣idropid∣id∣true∣falseE→EandE∣EorE∣notE∣idropid∣id∣true∣false$
其中$rop$是关系符，如$<=,<,=,>,>=<=,<,=,>,>=$等
布尔运算符的优先顺序为$not>and>ornot>and>or$
并且$and$和$not$服从左结合

布尔表达式的计算有两种方法：

1. 计算各部分的真假值，最后计算出整个表达式的值
   $(1and0)and(0or1)=0and1=0$
2. 短路法：AandB如果A=0则直接得到0；AorB如果A=1则直接得到1。这种方式若B为一个带返回值的过程调用会引发副作用

布尔表达式翻译成四元式序列，如a or b and not c的翻译结果为：
(1)t1:=not c
(2)t2:=b and t1
(3)t3:=a or t2

条件语句中布尔表达式的翻译

现在有文法：
S→if E then S1∣if E then S1 else S2∣while E do S1

翻译这部分的题目主要是以给定四元式序列，然后填空。

对布尔表达式E=a rop b，可以翻译成：
(1)if a rop b goto E.true
(2)goto E.false

但此时E.true和E.false的值仍不能被确定。例如：
S→if E then S1 else S2

E.true的值为S1的第一条四元式的地址
E.false的值为S2的第一条四元式的地址

例如：

1
2
3
4
5
6
7
8
9
10

//假设要翻译 if a<b or c<d and e>f ...这段程序

//理想的情况是翻译成下面这样
（1）　if a＜b goto E.true //E.true代表该if...else...逻辑的正向逻辑段入口地址，但是翻译当前bool表达式显然是暂且还不能确定E.true的
（2）　goto （3）
（3）　if c＜d　goto （5）
（4）　goto E．false       //E.false代表if...else...的反向逻辑段入口地址
（5）　is e＞f goto E．true
（6）　goto E．false //到bool表达式翻译完成时，才能确定原来逻辑块的正向段入口地址是7
（7） ...

可以看到上面的出现E.true和E.false的地方是需要回填的逻辑地址，这里比较常见的思路可能是额外为每个逻辑地址保存一个数组用来记录需要的所有地址，比如定义一个E.true-speicific-array并将(1）（2）填入该数组中。这种做法显然是很笨的，有没有比较好的方法？这便是”拉链“式解决方案，借鉴自链表的思想，为所有需要回填E.true的指令行首尾串在一起。

……
(p−1)…S1 end
(p) goto q
(p+1) S2 begin…
……
(q−1)… S2 end
(q)…

在产生出S1和S2的状态块后，才能进行地址回填。上面的E.true应填(7)，而E.false应填(p+1)。

为了解决地址回填的问题，需要采用拉链法，把需要回填E.true的所有四元式构造并维护一条真链的链表，把需要回填E.false的所有四元式构造一条假链的链表

对于上面的例子，真链和假链如下图：

其中(5)为真链的链首，(6)为假链的链首。一旦确定S1和S2的地址，就可以沿着链作地址回填

但还有3种情况会使得四元式序列变得十分复杂，这里不讨论：

1. 连续的or或连续的and
2. 连续的if−else if−else if…
3. 嵌套条件语句

循环语句中布尔表达式翻译

现需要翻译语句：while a<b do if c<d then X:=Y+Z

100:if a<b goto E.true
101:goto E.false
102:if c<d goto 104
103:goto 106
104:t1:=Y+Z
105:X:=t1
106:goto 100
107:…

分析到状态块的开始就可以确认E.true=102，而分析完状态块的结束之后就可以确认E.false=107

for循环语句翻译

现需要翻译语句：for I :=1 step 1 until Y do X:=X+1
等价于C语言的：for(I=1;I<=Y;++I) X=X+1;

100:I:=1
101:goto 103
102:I:=I+1
103:if I<=Y goto 105
104:goto 108
105:T:=X+1
106:X:=T
107:goto 102
108:…

数组的翻译

对于一个静态的n维数组，要访问其中一个元素，可以使用下标法：

A[i1,i2,…,in]

由于内存是一维连续空间，对于行主数组，比如一个2×32×3的二维数组，在内存中的布局为:

A[1,1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]

现知道数组A的地址为a，那A[i,j]的地址为：

a+(i−1)×3+(j−1)

设B为n维数组B[l1:u1,l2:u2,…,ln:un]

显然di=ui−li+1。令b是数组首元素地址，那么行主数组下B[i1,i2,…,in]的地址D为：

D=b+(i1−l1)d2d3…dn+(i2−l2)d3…dn+(in−1−ln−1)dn+(in−ln)

对式子展开可以提取出式子中的固定部分和变化部分：
D=constPart+varPart
constPart=b−C
C=l1d2d3…dn+l2d3…dn+…+ln−1dn−1+lndn
varPart=i1d2d3…dn+i2d3…dn+…+in−1dn−1+indn

访问数组元素A[i1,i2,…,in]需要产生两组计算数组的四元式：

1. 一组计算varPart，存放结果到临时单元T中
2. 一组计算constPart，存放结果到另一个临时单元T1中

用T1[T]表示数组元素的地址

变址取数的四元式：(=[],T1[T],−,X),相当于X:=T1[T]
变址存数的四元式：([]=,X1,−,T1[T]),相当于T1[T]:=X

现在有一个10*20的数组A，即d1=10,d2=20。则X:=A[I,J]的四元式序列为：
(∗,I,20,T1)
(+,T1,J,T1)
(−,A,21,T2)
(=[],T2[T1],−,T3)
(:=,T3,−,X)

对应：
varPart=20∗I+J
constPart=A−(1∗20+1)=A−21

符号表

符号表的作用

符号表用来体现作用域与可见性信息

• 登记各类名字的信息
• 编译各阶段都需要使用符号表
  • 一致性检查和作用域分析
  • 辅助代码生成

符号表的作用：
① 收集符号属性；（词法分析）
② 上下文语义的合法性检查的依据；（语法分析）
③ 作为目标代码生成阶段地址分配的依据；（语义分析）

符号表的组织

符号表的每一项（入口）包含两大栏

• 名字栏：主栏、关键字栏
• 信息栏：记录相应的不同属性、分为若干子栏

按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表

符号表中语言符号可分为关键字（保留字）符号，操作符符号及标识符符号

符号表中的标识符一般设置的属性项目有：
① 符号名
② 符号的类型
③ 符号的存储类别
④ 符号的作用域及可视性
⑤ 符号变量的存储分配信息
⑥ 符号的其它属性

符号表操作

针对符号表的常见操作：

• 创建符号表 在编译开始，或进入一个作用域

• 插入表项 在遇到新的标识符声明时进行

• 查询表项 在引用标识符时进行

• 修改表项 在获得新的语义值信息时进行

• 删除表项 在标识符成为不可见或不再需要它的任何信息时进行

释放符号表空间 在编译结束前或退出一个作用域

对符号表进行操作的时机

• 定义性出现：int index
• 使用性出现：if index < 100

实现符号表的常用数据结构

• 一般的线性表：如：数组，链表，等
• 有序表：查询较无序表快，如可以采用折半查找
• 二叉搜索树
• Hash表

作用域和可见性

静态语义分析

静态语义： 刻画程序在静态一致性或完整性方面的特征；仅当程序通过了静态语义检查，才能完成后续的中间代码生成和目标代码优化。

主要任务

• 类型检查（type checks）
  检查每个操作是否遵守语言类型系统的定义

• 名字的作用域（scope）分析
  建立名字的定义和使用之间联系

• 控制流检查（flow-of-control checks）
  控制流语句必须使控制转移到合法的地方（如 break语句必须有合法的语句包围它）

• 唯一性检查（uniqueness checks）
  很多场合要求对象只能被定义一次（如枚举类型的元素不能重复出现）

• 名字的上下文相关性检查（name-related checks）
  某些名字的多次出现之间应该满足一定的上下文相关性

类型检查

类型检查程序（type checker）负责类型检查

• 验证程序的结构是否匹配上下文所期望的类

• 为相关阶段搜集及建立必要的类型信息

• 实现某个类型系统（type system）

并发控制概述

并发的背景：

• DBMS作为系统软件，对外提供数据访问服务
• 多个用户同时访问一个数据库
• 各种任务以事务为逻辑单位运行
• 同一时间并发运行的事务数可达数百个

多个事务的运行过程

串行执行

——事务依次执行，且每个事务必须等待前一个事务结束后方能运行

事务串行执行降低了系统资源利用率

事务执行过程中会占用多种资源：

• CPU——比较、计算、统计等
• 数据
• 网络——收发指令和数据

单个事务执行过程中部分资源可能处于空闲状态

并行执行

• 单处理机——CPU时间片轮转，多道程序交替运行
• 多CPU——并行处理技术，多种共享内存以及硬盘策略

注意，数据是临界资源。在事务执行过程中，它所访问的数据集合应该在事务终止前是一致的、相容的

数据库事务并发带来的问题

操作系统层面的并发控制手段：信号量
——保护对象明确、相对集中
——控制保护时间一般较短
——直接阻塞任务进程——信号量资源有限

数据库事务并发控制：
——事务访问的数据对象及其范围相对灵活，一致性所涉及的范围更广。
——事务的执行一般包括一个读写操作的序列，时间相对比简单的应用程序变量操作要长。
——需要被保护的对象个数可能远多于信号量数目。
——事务的执行可能涉及DBMS的多个进程。

数据库系统中的并发错误

事务是数据库中并发控制的基本单位，事务处理需要保证事务的ACID特性，并发控制要能保证事务的隔离性和一致性。

当多个用户/进程/线程同时对数据库进行操作时，会出现3种冲突情形：

1. 读-读，不存在任何问题
2. 读-写，有隔离性问题，可能遇到脏读（会读到未提交的数据） ，幻影读等。
3. 写-写，可能丢失更新

要解决冲突，一种办法是是锁，即基于锁的并发控制，比如2PL，这种方式开销比较高，而且无法避免死锁。

多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前的数据库的快照。 这样在读操作不用阻塞写操作，写操作不用阻塞读操作的同时，避免了脏读和不可重复读

乐观并发控制（OCC）是一种用来解决写-写冲突的无锁并发控制，认为事务间争用没有那么多，所以先进行修改，在提交事务前，检查一下事务开始后，有没有新提交改变，如果没有就提交，如果有就放弃并重试。乐观并发控制类似自选锁。乐观并发控制适用于低数据争用，写冲突比较少的环境。

多版本并发控制可以结合基于锁的并发控制来解决写-写冲突，即MVCC+2PL，也可以结合乐观并发控制来解决写-写冲突。

基于封锁的并发控制

封锁概述

封锁的基本思想

封锁是数据库管理系统实现并发控制的一种重要技术。

并发控制方法：
① 锁（Locking）——商用数据库典型方法
② 时间戳（timestamping）
③ 乐观（Optimistic）

流程——事务在对某个数据对象（表、记录集合等）进行读写操作之前，先向系统发出封锁请求，系统依据请求对数据对象加锁，事务在获得锁后才能对数据对象进行操作，操作完成后在适当时机释放锁。

约束——系统在事务持有锁期间提供与锁配套的对数据的并发访问保护功能，其他事务不能违反保护规则进行与锁互斥的数据操作。

封锁的基本规则

① 将要存取的数据须先申请加锁；

② 已被加锁的数据不能再加不相容锁；

③ 一旦完成使用应“尽早”释放锁；

④ 未被加锁的数据不可对之解锁。

申请的时机

①针对事务执行确定一个时间点整体申请
一次封锁——无死锁
锁开销少——用少数的锁保护较大范围的数据
并发度低——锁冲突概率增加。

②针对单条SQL语句执行申请
申请频繁——申请时机增多
死锁——部分占有与互斥等待
锁开销大——被保护的数据对象集合增多
并发度高——细粒度的封锁

申请的方式

①显式

应事务的要求直接加到数据对象上。

②隐式

该数据对象没有直接加锁，由于数据对象的多粒度层次结构中的上级结点加了锁，使该数据对象隐含的加了相同类型的锁。

封锁的类型

基本的封锁类型有两种：排它锁（exclusive locks，简称X锁）和共享锁（share locks，简称S锁）。

（1）排它锁（X锁）
若事务T持有数据D的X锁，则T可读、写D，其它任何事务不能再对D加任何锁，直至T释放该X锁。X锁一般用于写保护，可防止丢失更新。

（2）共享锁（S锁）
若事务T持有数据D的S锁，则T仅能够对D进行读操作，其它事务仍可对D加S锁，但不可加X锁，直到T释放该S锁。

S锁一般用于读操作，一旦施加S锁，读可共享，但其它事务不可改。

除了X锁和S锁外，还有：

更新锁（U锁）：

意向锁：对多粒度树中的结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。

注：当出现解锁时，就认定解锁任务开始，在解锁阶段不能再加任何锁

封锁的协议

在运用X锁和S锁时，针对并发操作不正确调度可能产生的丢失修改、不可重复读和读脏问题，可以通过三级封锁协议不同程度上解决这些问题。不同的封锁协议达到的系统一致性级别是不同的。

发生丢失更新的过程

T1读取库存后，T2也读取了同一个库存；T1修改库存，回写更新后的值；T2修改库存，也回写更新后的值。此时库存为T2回写的值，T1对库存的更新丢失。

顺序	任务	操作	库存量
１	T1	读库存量	50
２	T2	读库存量	50
３	T1	库存量=50+100
４	T2	库存量=50-40
５	T1	写库存量	150
６	T2	写库存量	10

T2使用T1的“脏数据”的过程

当T1和T2并发执行时，在T1对数据库更新的结果没有提交之前，T2使用了T1的结果，而在T2操作之后T1又回滚，这时引起的错误是T2读取了T1的“脏数据”。

顺序	任务	操作	库存量
１	T1	读库存量	50
２	T1	库存量=50+100
３	T1	写库存量	150
４	T2	读库存量	150
５	T2	库存量=150-40
６	T1	ROLLBACK	50
７	T2	写库存量	110

T1对数据A“不可重复读”的过程

当T1读取数据A后，T2执行了对A的更新，当T1 再次读取数据A（希望与第一次是相同的值）时，得到的数据与前一次不同，这时引起的错误称为“不可重复读”。

顺序	任务	操作	库存量A	入库量B
１	T1	读A=50	50	100
2	T1	读B=100
3	T1	求和=50+100
４	T2	读B=100	50
５	T2	B←B×4
６	T2	回写B=400	50	400
７	T1	读A=50	50
8	T1	读B=400
9	T1	和=450（验算不对）

（1）1级封锁协议
①策略
事务T在修改数据D之前须先对其加X锁，直到事务T结束（commit/rollback）才释放。
②功能
防止丢失修改；并保证事务T是可恢复的。
③问题
不能防止不可重复读和读“脏”数据。（仅对修改操作申请加锁保护，若读则不加锁）

上述过程发生了脏数据的读取

1级封锁协议为什么不能避免读脏数据？

排它锁X只能防止该数据无法被其他线程写，不能防止该数据被其他线程读。在改数据和回滚的过程有可能会产生脏数据

（2）2级封锁协议
①策略
在1级封锁协议基础上，再加上约束：事务T在读取D之前先对D加S锁，读完后即可释放该S锁。[无需等待事务结束]
②功能
防止丢失修改；防止读脏。
③问题
不能防止读不可重复（读完即释放，重读可能其它事务对之修改）。

为什么二级封锁协议可以解决脏读？

​ 前面我们说过脏读产生的原因：因为B事务读取到了A事务修改过尚未提交的数据，根据二级封锁协议要求：读数据的时候必须加S锁，但因为A事务在修改的时候已经加了X锁，在X锁的基础上是不能加S锁的，所以B事务无法获取S锁，就会导致B事务无法读取A事务中正在操作的数据，从而避免了脏读的发生。

（3）3级封锁协议
①策略
在1级封锁协议的基础上，加上约束：T读D前须先对D加S锁，直至T结束后才释放该S锁。
②功能
防止丢失修改；防止读脏；防止不可重复读。

为什么三级封锁协议可以解决不可重复读？

​ 前面我们也说过了不可重复读产生的原因：是因为B事务读取到了A事务已经修改过的数据，导致前后两次读取的数据不一致。现根据三级封锁协议的要求：读取数据时必须加S锁，在S锁的基础上只能加S锁，不能加X锁，所以在B事务读取数据期间，A事务无法对数据进行修改，从而避免了不可重复读问题的发生。

并行调度的可串行性

正确性标准

（1）单个事务

——若非并发的执行，每个事务都能保证DB的正确性。
（丢失修改、不可重复读、读脏数据，都是因事务并发执行产生）

（2）多个事务

——多个事务以任意串行方式执行都能保证DB的正确性。
给定三个事务：T1，T2，T3。
T1→T2→T3 T1→T3→T2
T2→T1→T3 T2→T3→T1
T3→T1→T2 T3→T2→T1
显然，任何一事务并发执行时禁止其它事务执行，总能保证DB正确性，但不利于数据共享。

（3）可串行化调度（serializable）

——当且仅当多个事务并发执行的结果与这些事务按某一顺序串行执行的结果相同时，则该并发执行是可串行化的。
（可串行化调度是并发事务正确性的唯一准则）

例：有两个事务TA，TB （A=10, B=2, C=0）包含如下操作序列
TA：读B；A:=B+1；写回A；
TB：读C；读A；B:=A+C+1；写回B；
则至少可能有四种不同的调度方式:

1、先执行TA，再执行TB——RA(B) WA(A) RB(C) RB(A) WB(B)；结果：A=3，B=4，C=0。【串行调度】

2、先执行TB，再执行TA——RB(C) RB(A) WB(B) RA(B) WA(A) ；执行结果：A=12，B=11，C=0。【串行调度】

3、两事务TA、TB按ti并发执行——RA(B) RB(C) RB(A) WA(A) WB(B)，结果为A=3，B=11。
按事务并发可串行化的正确性准则，该结果与TA、TB两个串行执行的任何结果（A=3，B=4；A=12，B=11）均不同，调度结果错误。【交错执行（不可串行化）调度】

4、按ti交错执行——RA(B) RB(C)WA(A)RB(A)WB(B)；执行结果：A=3，B=4。该结果正确，因为与串行化调度1结果相同，该调度是可串行化调度【交错执行(可串行化)调度】

冲突可串行化调度

——可串行化调度的充分而非必要条件。

冲突操作：① Ri(x)与Wj(x) ② Wi(x)与Wj(x)

操作顺序的交换（可交换、不可交换）
——不同事务的冲突操作和同一事务的两个操作均是不可交换的。否则可能使操作序列的结果不等价。

在可交换的前提下，若干事务的操作交换顺序的结果是一个串行调度，则称这个调度是冲突可串行化的。

前趋图：事务均为节点，事务之间存在冲突操作（读写、写读、写写）时，则事务之间存在由冲突操作的先执行事务指向后执行事务的有向边。

前驱图中不存在环路等价于调度是冲突可串行化的

冲突可串行化是可串行化的充分条件，不是必要条件。

两段锁协议

参考文章

问题分析

• 并发调度的正确性标准：可串行化调度
  n个事务的可串行化调度结果——n！种
  可串行化的充分而非必要条件：冲突可串行化调度

• 基于封锁的并发控制：一种基于悲观思想的并发控制策略。
  操作之前先查验冲突

• 封锁如何解决并发错误？
  三级封锁协议
  排它锁保护写操作——写之前申请，事务结束时释放。
  在此基础上，共享锁保护读操作——读之前申请，释放时机（读完之后即可释放、事务结束时释放）

三级封锁协议的选择依据

权衡并发调度正确性和并发性能。

三级封锁协议的特点之一：事务对数据的保护时间较为统一，其中比较强的往往保护至事务结束。

能否制定相对灵活的封锁协议?
两阶段封锁（TwoPhase Locking，简称2PL）

基于2PL协议的调度

基本思想：所有事务必须分为两个阶段对数据项加锁和解锁，第一阶段称为扩展阶段（获得锁）；第二阶段称为收缩阶段（释放锁）。

协议内容：
（1）在对任何数据读、写之前，须先获得该数据的锁；
（2）在释放一个封锁之后，该事务不能再申请任何其它锁。【正确的遵守2PL协议，所有获得锁均在释放锁之前。】

两个阶段：事务的第一个释放锁操作成为分界线。
扩张和收缩：事务对数据资源的占有。

两段锁协议的目标：实现并发事务调度的可串行化。

两阶段锁协议的特点

• 定理：若所有事务都遵守2PL协议，则对这些事务的所有并发调度策略都是可串行化的。

证明思路：
前趋图——事务均为节点，事务之间存在冲突操作（读写、写读、写写）时，则事务之间存在由冲突操作的先执行事务指向后执行事务的有向边。

前驱图中不存在环路等价于调度是冲突可串行化的

反证法：假设调度遵循2PL协议但不是可串行化的 → 与2PL有矛盾。冲突可串行化是可串行化的充分而非必要条件。

假如调度不是可串行化的，则该调度也不是冲突可串行化的。
① 假设某个遵守2PL的调度不是可串行化调度；
② 按Lock、UnLock操作中因锁不兼容而等待的关系构造调度的前趋图G；
③ 依据假设，若调度不是可串行化，则G中必存在环路，不妨设为：Ti1→Ti2→……→Tjp→Tin。
④ 其中某个冲突事务获得锁的前提是前面的冲突事务释放锁，则意味着Ti1解锁后Tjp才能获得锁，之后在环路中又出现Tin加锁；
⑤ “④”中Ti违反了两阶段锁协议。

• 2PL协议是可串行化的充分条件，不是必要条件。
• 遵守两阶段锁协议的事务可能发生死锁。

总结

两阶段锁（2PL）：通过事务的扩张和收缩阶段的划分，而不是提交之前与提交之时的这种划分，对锁的申请和释放流程进行的一种约定，从而实现了调度正确性的一个充分而非必要条件。

封锁的粒度

到目前为止我们都没有对不同粒度的锁进行讨论，一直以来我们都讨论的都是数据行锁，但是在有些时候我们希望将多个节点看做一个数据单元，使用锁直接将这个数据单元、表甚至数据库锁定起来。这个目标的实现需要我们在数据库中定义不同粒度的锁

多粒度封锁

封锁的粒度：封锁对象的大小。
（1）逻辑单元：整个数据库、整个关系、整个索引、关系的分区、元组、索引项、属性值集、属性值。
（2）物理单元：数据页（块）、索引页

封锁的粒度与数据库并发性能的两个重要因素相关：

• 并发度
• 并发控制的开销

粒度小——封锁开销大——并发度大

封锁的基本策略

宜采用多粒度封锁：
1）需常存取多个关系的大量元组时宜采用数据库级粒度；
2）需常存取单个关系大量元组时宜采用关系级；
3）需常存取单个关系少量元组时宜采用元组级；
4）一般不采用属性级；
5）物理单元一般不宜采用。

多粒度锁提供了并发度和锁开销的权衡空间。

多粒度封锁

隐式封锁：某个数据对象被显式封锁后，它在多粒度层次结构中的子孙节点被隐含的加了相同类型的锁

多粒度锁的冲突检测

• 显式封锁和隐式封锁的效果是一样的，因此检查封锁冲突时需要对两种封锁的结果都进行检测。

  1）检查数据对象本身有无显式封锁与申请冲突；

  2）检查上级结点有无封锁与本结点冲突；

  3）检查后代结点有无封锁与本结点冲突

意向锁

对任一结点加锁时，必须先对它的上层结点加意向锁。如果对某个结点加意向锁，则表示该结点的某个子孙结点正在或拟施加相应的非意向锁。作用：提高系统并发度，减少加锁和解锁的开销。被商用产品广泛采用。

意向锁的类型：
1）IS锁：表示某个子孙结点拟加S锁
2）IX锁：表示某个子孙结点拟加X锁
3）SIX锁：表示对结点施加S锁的同时，再施加IX锁= S+IX

查询优化概述

查询优化的意义

• SQL语言具有非过程化特性（必要性）
• 查询操作存在多解性（可能性）
  • 同一个查询语句可以用多种关系代数表达式来表达
  • 同一个关系操作可以有多种实现算法或存取路径
    • 选择——全表扫描、索引扫描
    • 自然连接——嵌套循环、排序-合并、索引连接、哈希连接

自然连接算法

自然连接：是一种特殊的等值连接，它要求两个关系进行比较的分量必须是相同的属性组，并且在结果集中将重复属性列去掉。

1）等值连接必须要有等值的条件，当条件不同时连接的结果也不相同，两个关系可以没有相同的属性列
2）自然连接必须要有相同的属性列才能进行，即等值连接之后要去除相同的属性列

嵌套循环算法

1
2
3
4

for each row1 from T1
	for each row2 from T2
	if row2 match row1//如果row2与row1满足连接条件
	join row1 and row2 into result//加入结果集

简单通用，对参与连接的表没有要求。由于对内层循环表需要进行多次扫描。因此性能较差

排序—合并算法

访问次数：两张表都只会访问0次或1次。
驱动表是否有顺序：无。
是否要排序：是。
应用场景：当结果集已经排过序。

如果A表的数据为（2,1,4,5,2）,B表的数据为(2,2,1,3,1) ,首先将A表和B表全扫描后排序，如下：

​ A B

​ 1 1

​ 2 1

​ 2 2

​ 4 2

​ 5 3

因为没有驱动表，所以数据库会随机选择一张表驱动，如果选择了A扫描到1，然后扫描B，当扫描=1的时候则匹配

当扫描到B=2时，再以B=2为驱动扫描A表，不是从1开始扫，而是从2开始扫描，交替的进行扫描、关联。

也就是说：不是从1重新开始扫，而是从2开始扫描

对于左表和右表只需要扫描一遍，性能比较高。但是只适用于参与连接的表已经有序的情况。

索引连接算法

利用索引提高连接过程中的元组查找速度，适用于参加连接的表的连接属性上存在索引的情况。

哈希连接算法

通过对连接属性进行哈希分桶来提高连接阶段的匹配速度，适用于较小的那个连接表在散列后能完全放入内存的情况

简单的对于两个表来讲，hash-join就算讲两表中的小表（称S）作为hash表，然后去扫描另一个表(称M)的每一行数据，用得出来的行数据根据连接条件去映射建立的hash表，hash表是放在内存中的，这样可以很快的得到对应的S表与M表相匹配的行。

对于结果集很大的情况，merge-join需要对其排序效率并不会很高，而nested loop join是一种嵌套循环的查询方式无疑更不适合大数据集的连接，而hash-join正是为处理这种棘手的查询方式而生，尤其是对于一个大表和一个小表的情况，基本上只需要将大小表扫描一遍就可以得出最终的结果集。

　　不过hash-join只适用于等值连接，对于>, <, <=, >=这样的查询连接还是需要nested loop这种通用的连接算法来处理。如果连接key本来就是有序的或者需要排序，那么可能用merge-join的代价会比hash-join更小，此时merge-join会更有优势。

代数优化

是指通过对关系代数表达式的等价变换来提高查询效率

就是查询语法树的等价变形

变换五大核心规则

总结起来就是: “(连接类的)交换律, 结合律; (投影和选择类的)串接律, (这两大类相互之间)分配率”

1. E1 X E2 = E2 X E1, (E1 X E2) X E3 = E1 X (E2 X E3)做笛卡尔积, 多个表做连接是满足交换律和结合律的
2. 投影和选择的串接定律
   多层的投影可以取小的那个
   多层的选择可以取交集(其实也是那个范围比较小的), 这样能够把多次选择 多次表的扫描, 改成一次.
3. 选择与投影交换律: 选择和投影的顺序可以随意改变
4. 选择与笛卡尔积, 并, 自然连接, 差的分配律: 处在后面的选择, 可以与处在前面的二目运算顺序进行调整, 使得对相应的表先实施选择, 再实现连接等二目运算. 这个非常重要, 是先选择后进行二目运算的依据, 又名”选择提前”.
5. 选择与笛卡尔积, 并的分配率: 可以先投影, 也可以先进行二目运算

导致关系数据库查询性能低的主要原因是笛卡尔积运算

投影与交运算不属于关系代数表达式等价规则

经验性优化五大策略

其实就是”选择, 合并, 视图”

1. 选择运算尽可能先做, 这是最最最最重要和基本的, 这样往往使得执行代价减少了几个数量级, 主要的原理就是选择运算能够大大降低参与连接的元组的行数, 使得连接生成的A•B结果也大大被缩小.
2. 把选择和投影运算同时进行, 如果有若干投影和选择运算, 并且他们都是针对同一个表, 那么可以在扫描这个表的时候同时完成这些所有的运算, 以此避免重复扫描这张表.
3. 把投影与其前或者后的双目运算(笛卡尔积, 等值连接, 并集, 差集)结合起来, 也就是说, 没有必要为了选择出几个字段而单独再重新扫描全表.
4. 把某些选择和在它前面要执行的笛卡尔积结合起来成为一个连接运算(比如变成等值连接), 这是因为连接运算要比同样情形下的笛卡尔积节省很多时间.

笛卡尔积先进行了 O(N • M)操作 生成了A•B大小的中间文件, 存盘, 然后读盘, 然后再按照where选择进行筛选得到结果; 对比之下, 等值连接运算也进行了O(N•M)操作, 但是还进行了筛选, 只生成比较小的中间文件, 存盘和读盘的是一个非常小的结果集合. 大大减少了IO开销.

1. 找出公共子表达式(一次计算, 多次使用). 比如很多的查询都基于某个公共部分, 那么可以定义一个公共子表达式, 然后先计算一次公共子表达式, 然后把它存盘, 供其他大量的表达式来使用. 我们定义视图其实就是在实践这种策略.

物理优化

基于经验规则的优化

• 对于小的表, 直接全表扫描, 即使列上有索引.

• 对于大的表：

  • 如果是选择条件涉及主键, 那么使用主键索引(MySQL等主流关系数据库都会对主键建立索引);
  • 如果不是涉及主键：
    • 如果是等值查询, 列上有索引, 就使用索引;
    • 如果非等值查询, 而是范围值查询, 那么范围<=10%用索引, 范围比较大的, 直接全表扫描.

• And 和 OR:

  • AND连接的, 优先考虑使用索引;
  • OR连接的, 优先考虑使用顺序扫描, 毕竟OR可能性非常多.

• 连接操作:

  • 如果两个表都按照连接属性排序, 用sort-merge算法
  • 如果其中一个表在连接属性上有索引,采用索引连接算法;
  • 如果啥都没有, 对小的表建立哈希表, 使用hash join方法; 或者使用基本的嵌套循环, 不过外层循环(i循环)使用小表, 这样能稍微减小代价.

基于代价的优化

基于代价的优化需要依赖数据库表的各种”情报”, 来计算出不同方案的代价, 从中选择最优的.
这些信息(meta info)包括:

1. 对每个表来说:
   表的元组行数 N,
   元组的长度, 即列的维度数目 P,
   表占用的block数目 B,
   表占用的溢出块的块数 BO,
2. 对表中的每个列,
   该列的不同值的个数 k
   列的最大值, 最小值max, min
   列上有什么类型的索引 index: 按照实现方式有B+, Hash, Cluster / 按照类型来说有普通索引, 唯一索引, 主键索引, 聚集索引
   列上的数值分布情况 (直方图)

那么对于不同情况, 我们有如下的代价估算:

1. 全表扫描 cost = B
2. 有索引的扫描
   如果选择条件是key = value, 能适用唯一索引: L + 1
   如果选择条件是attr = value, 能使用普通索引: L + S (可能有S个元组满足)
   如果条件是范围类的, 比如>, <, between A and B, 那么基本上就是接近全表扫描B;
3. 连接算法的代价
   如果用嵌套循环: 读入Capacity-1块B[a], 遍历连接b表所有B[b], 再换下一批B[a], 直到a表结束. 所以, cost = B[a] + ( B[a]/(C-1) ) • B[b] = a表IO次数 + b表IO次数, 假如要生成中间文件的话, 那么还得加上存下所有连接好的元组的磁盘IO开销.

如果用sort-merge: cost = B[a] + B[b], 如果要把中间结果写入外存, 那么还要加上存下所有连接好的元组的磁盘IO开销, 这个开销和上面嵌套循环的是一样的.
假如表本身没有排序, 那么排序的代价是B[a]logB[a] + B[b]logB[b]

参考资料

1. 数据库系统概论（高级篇）
2. 脚本之家: SQL语句的各个关键字的解析过程详细总结