《csapp》第一部分—程序结构和执行

admin管理员组

文章数量:1565357

文章目录

• 第一章 计算机系统漫游
• • 信息就是位+上下文
  • 代码的翻译过程
  • 程序的执行
  • 存储设备的层次结构
  • 操作系统、网络
  • 重要主题
• 第六章 存储器层次结构
• • 6.1 存储技术
  • 6.2 局部性
  • 6.3 存储器层次结构
  • 6.4 高速缓存存储器
  • 6.5 编写高速缓存友好的代码
  • 6.6 综合：高速缓存对程序性能的影响
  • 6.7 小结

第一章 计算机系统漫游

信息就是位+上下文

• 文本文件与二进制文件
• 由ASCII或者Unicode字符构成的文件是文本文件；所有其他文件都是二进制文件(不过文本文件本质上还是二进制数据)

代码的翻译过程

助记：几个中间格式的后缀 => iso

程序的执行

• 硬件组成
  
  注意：
  1主要由总线、IO设备、处理器、存储器组成
  2.每个IO设备都通过控制器或者适配器与IO总线相连
  3.高速缓存(cache)通常也在cpu内部
• 补充—控制器、适配器、驱动器的关系
  1.控制器与适配器都是IO设备的直接控制单元，两者的区别在于：控制器是设备本身或者主板上的芯片组； 适配器则是插在主板上的卡
  2.驱动器是操作系统用于间接控制IO设备的软件，驱动程序根据需要对设备控制器进行操作，设备控制器再去控制设备本身！
• 执行程序的过程—以hello程序为例
  1.shell将hello命令读取到内存，数据流向如图(需经过cpu!)
  
  2.shell从磁盘加载hello程序到内存(DMA，不经过内存)
  
  3.CPU执行程序，将字符串输出到显示设备(经过cpu!)
  

存储设备的层次结构

操作系统、网络

这两节后面章节有详细介绍，此处没有重要笔记

重要主题

• Amdal定律
  T n e w = ( 1 − α ) T o l d + ( α T o l d ) / k T_{new}=(1-\alpha)T_{old}+(\alpha T_{old})/k Tnew​=(1−α)Told​+(αTold​)/k
• 并行与并发
  …
• 计算机中的抽象
  
  文件是对IO设备的抽象；虚拟内存是对存储器的抽象；进程是对正在运行的程序的抽象；虚拟机是对整个计算机的抽象

第六章 存储器层次结构

• 概述
  访问寄存器：0个周期
  访问告诉缓存：4~75个周期
  访问主存：上百个周期
  访问磁盘：几千万个周期！！！！！
  重点是高速缓存：它作为cpu和主存之间的缓存区域，对程序性能的影响最大

6.1 存储技术

• RAM
  分为SRAM和DRAM

  • 1.SRAM
    常用作cache，不需要刷新
  • 2.DRAM
    常用作主存，通过电容来存储，需要刷新
    注：DDR是一种增强的DRAM，即双倍数据速率同步DRAM
    DRAM存储器单元对干扰非常敏感，数码相机和摄像机中的传感器 本质上就是DRAM单元阵列
    DRAM芯片示意图
    
    每个超单元存储w(通常是8)位信息，一个DRAM芯片是有d个超单元组成的阵列
    读取DRAM芯片上的内容
    
    先收到行地址，缓存整行到缓冲区=>然后收到列地址，从缓冲区取出对应列；行列共享地址线，先取行地址，再去列地址，从而节约芯片引脚数量
    DRAM芯片组成内存模块
    
    CPU访问RAM(主存)
    总线按作用可分为：地址线、数据线、信号线
    总线按照位置可分为：系统总线、内存总线、IO总线
    对数据的访问通过总线进行，读取数据过程如图：
    
    注：IO桥内部包括内存控制器(区别于驱动器程序)，它直接控制对内存的读写

• ROM
  PROM：只能被编程一次的ROM
  EPROM：可擦写可编程的ROM
  闪存：基于EEPROM这类ROM，U盘就是闪存制作的
  固态硬盘：基于闪存
  存储在ROM中的程序通常被称为固件，比如BIOS

• 磁盘
  磁盘结构
  
  磁盘容量
  1.扇区的数量由最靠内的磁道能记录的扇区数决定！
  2.磁盘容量的计算(较简单，理解即可)：
  
  3.对于DRAM、SRAM的容量，常以二进制算(即K=1024…)；对于磁盘、网络这样的IO设备容量，常以十进制算(K=1000…)
  磁盘操作
  磁盘以扇区大小的块来读写数据，扇区大小通常是512B
  三个操作：寻道+旋转+传送
  寻道时间 ≈ 旋转时间 >> 传送时间
  逻辑磁盘块
  1.磁盘中的(固件/硬件设备)磁盘控制器 维护着逻辑磁盘块号和实际物理磁盘扇区之间的关系 => 类似于虚拟内存地址通过页表实现到物理内存地址的转换
  2.操作系统读取磁盘时给出的是逻辑磁盘块号，磁盘控制器通过一个快速查找表将其转换成(盘面,磁道,扇区)的三元组
  访问磁盘
  内存映射I/O技术：虚拟内存的地址空间中保留一块地址用于和IO设备通信，这样的地址称为IO端口(区别于网络协议的端口)；这个保留地址(IO端口)对应磁盘控制器中的少量寄存器，CPU实际上是通过读写这些寄存器完成对磁盘的访问，而不是直接读写扇区!!!
  以读磁盘为例，过程如下：
  a.CPU将读取磁盘的指令存放到IO端口 => b.CPU将要读扇区的逻辑块号放到IO端口 => c.CPU把内容将被存放的主存地址放到IO端口 => d.控制器完成地址翻译 => e.控制器将磁盘内容通过DMA直接放到主存

6.2 局部性

• 对程序数据引用的局部性
  
  如图，sum多次被访问，时间局部性良好，无空间局部性;
  数组v的元素逐个被访问，空间局部性良好，但是对于单个元素而言时间局部性较差
  步长为k的引用模式：一个连续向量中，每隔k个元素进行访问，就称为步长为k的引用模式 => 步长为1的引用模式是空间局部性的重要来源，然而随着步长增加，空间局部性下降
• 取指令的局部性
  如上图sumvec函数所示：
  1.for循环内的指令按照连续的内存顺序执行，因此循环具有良好的空间局部性
  2.for循环内的指令会被多次执行，因此它也具有很好的时间局部性

6.3 存储器层次结构

• 层次结构示意图
  
• 缓存的基本原理
  
  1.两级存储中，数据总是以块为大小在第k层和第k+1层来回复制数据(不相邻的层次中，块的大小不一定相等)
  2.任何时刻，第k层的缓存包含第k+1层块的一个子集的副本!!
• 缓存不命中的种类
  1.冷不命中 ：访问时缓存是空的
  2.冲突不命中：缓存足够大，但是由于总是读取映射到同一个缓存块的数据，导致总是不命中
  3.容量不命中：工作集大小超过缓存大小时，发生容量不命中，即缓存太小!
• 缓存管理
  在存储器层次结构的每一层，必须有某个东西将缓存划分成块，在不同层之间传送块，判断命中还是不命中，并处理它们 => 软件、硬件等都可以实现，比如：
  *1.寄存器文件由编译器管理
  2.L1、L2、L3缓存由cache中的硬件逻辑管理
  3.DRAM由操作系统和CPU上的地址翻译硬件以及页表共同管理(这里的管理包括：判断DRAM是否命中，若命中找到存放在DRAM中的数据，若不命中则从磁盘中复制数据到DRAM…)
  …

6.4 高速缓存存储器

• 通用的高速缓存组织结构
  高速缓存由 ( S , E , B , m ) (S,E,B,m) (S,E,B,m)四元组来描述；S是组数，占s位；E是组内行数，占t位，但是E的范围并非[0,2^t-1]；B是行内字节数，占b位；m是地址总位数，对应物理内存大小，满足 m = s + t + b m=s+t+b m=s+t+b。如下：
  
  注：1.缓存容量的计算： C = S ∗ E ∗ B C=S*E*B C=S∗E∗B，容量不包括图示中的有效位和标记位
  2. S = 2 t S=2^t S=2t、 B = 2 b B=2^b B=2b，但是 E ! = 2 t E!=2^t E!=2t；E应该小于 2 t 2^t 2t，若E等于 2 t 2^t 2t，说明内存地址空间大小等于缓存地址空间大小，则内存没有意义了!!
  3.t个标记为并非用于直接计算行的索引(地址)，而是用于逐行比较判断是否要查找的行，这一点上与s、b有区别!!!
  4.CPU从缓存读取字节时，发送给缓存的是物理内存地址，而不是虚拟内存地址(见第九章)！
  注意：为什么使用中间位来做组索引
  如果使用高位做索引，那么一些连续的内存块容易映射到相同的高速缓存组/行；
  而以中间位做索引，相邻的块总是映射到不同的高速缓存组/行；
  

• 直接映射高速缓存(E=1)
  访存过程
  a.组索引(使用地址中抽出的s位) => b.行匹配(只有一行，直接看有效位和标记位即可，对比数据中的标记位是否与地址中的一致) => c.字选择(根据地址中的b位提取字节)
  缓存不命中
  如果缓存不命中，则从存储层次的下一层取出请求的块，然后将新的块存储在组索引位对应的组中的一个高速缓存行中(不过每组只有一行；当然也可能涉及替换…)。向下一层取数据块使用同一个物理内存地址，只是下一级缓存对这个物理地址的理解方式不同
  直接映射高速缓存的冲突不命中
  当程序访问大小为2的幂的数组时，直接映射高速缓存中通常会发生冲突不命中；比如，
  
  x[i]与y[i]映射到相同的组，从而导致访问缓存时产生抖动(高速缓存反复地加载和驱逐相同的高速缓存块的组)

• 组相联高速缓存(1<E<C/B)
  访存过程
  a.组索引(使用地址中抽出的s位) => b.行匹配(逐行检查标记位和有效位，对比数据中的标记位是否与地址中的一致) => c.字选择(根据地址中的b位提取字节)
  相联存储器
  1.相联/关联存储器是一个(key,val)对的数组；
  2.写入信息时按顺序写入，不需要地址。
  3.读出时，要求中央处理单元给出一个相联关键字，用它和存储器中所有单元中的一部分信息进行比较，若它们相等，则将此单元中余下的信息读出(所以读取数据时给存储器传递的应该看做key而不是地址)
  4.可以将组相联存储器的每个组看做一个小的相联系存储器
  5.所以对于组相联存储，组中的任何一行都可以包含任何映射到这个组的内存块
  组相联缓存不命中时的行替换
  …略 => 设置替换策略

• 全相联高速缓存(E=C/B)
  结构及特点
  1.由于S=1，所以地址结构中没有s位的组索引；
  2.由于构造一个又大又快的相联高速缓存很困难且昂贵(因为需要并行地搜索许多相配的标记)，所以全相联只适合用作小的高速缓存，比如TLB
  访存过程
  a.组索引(由于只有一组，不必组索引) => b.行匹配(逐行检查标记位和有效位，对比数据中的标记位是否与地址中的一致) => c.字选择(根据地址中的b位提取字节)
  缓存不命中
  …略

• 有关写的问题
  写命中(缓存中有要写的数据时)
  直写：最简单的方式，直接将更新后的缓存内容写到低一级中
  写回：尽可能推迟写到低一级存储，直到需要替换该缓存块时
  写不命中(要写的数据不再缓存中时)
  写分配：加载低一级的内容到高速缓存块，然后更新高速缓存块
  非写分配：避开高速缓存，直接将要写的内容写到低一级存储
  注：直写高速缓存通常是非写分配的；写回高速缓存通常是写分配的； 高速缓存越往下层，越有可能写回而不是直写
  注注：这里讨论的写问题，主要适用于寄存器、cache、内存之间，并不适用于内存与磁盘之间；
  因为寄存器、cache上的数据都能在更低一级的存储器中找到，因此可以讨论将不需要的数据放回的低一级的存储中，而这个放回的过程并不需要程序员介入；
  而在内存和磁盘之间，虽然内存也是作为磁盘的缓存，由于程序运行是将内存看做真正的物理存储的，在程序运行过程中，可能产生许多临时的数据，这部分数据只能存储在内存，而在磁盘上并没有对应的空间=>所以并不能将这部分临时数据放回磁盘(当物理内存存放不下时，可以把多余的数据放入交换区间(详见9.8)，虽然交换区间也在磁盘上，但它区别于磁盘上的其他部分，因为电脑刚启动时，交换区间并没有数据，所以交换区间最好不要直接看做磁盘，而应该看做内存的补充)；与更高层次的写回相比，内存中的数据想要写回磁盘，就必须程序要介入，显式地写到磁盘

• 一个真实的高速缓存示例
  

6.5 编写高速缓存友好的代码

• 1.将注意力集中在核心函数的循环上
• 2.尽量减少循环内部的缓存不命中数量
• 一些注意事项
  a.对局部变量的反复引用是好的，因为编译器能将他们缓存在寄存器文件中(时间局部性)
  b.步长为1的引用模式是好的，因为缓存都是将数据存储为连续的块(空间局部性)
  c.在对多为数组进行操作的程序中，空间局部性尤其重要

6.6 综合：高速缓存对程序性能的影响

• 存储器山
  
• 重新排列循环以提高空间局部性
  
  这是一个矩阵乘法(C=AB)，判断哪个版本效率更高？ => 详见P448

6.7 小结

• 较大收获/易忘易混
  1.DRAM芯片的结构、读写
  2.系统如何通过逻辑磁盘块号读取磁盘扇区的内容
  3.DDR、SATA两个常用词的含义(前者描述DRAM、后者描述总线/接口)
  4.内存映射I/O
  5.高速缓存的通用结构+三类缓存
  6.什么是相联存储器
• 疑惑

本文标签： 第一部分结构程序CSAPP