ICS 计算机系统

发表于 更新于

第一阶段 程序的表示、转换与链接

参考MOOC：NJU-1001625001

1.0 计算机系统概述

1.3 程序开发和执行过程

  1. hello.c程序用ascii文本表示
  2. 首先.c文件预处理为.i文件（把预处理指令翻译过来），然后.i文件编译成.s文件（汇编程序文本）,接着.s文件汇编成.o文件（二进制），与printf等函数的.o文件共同连接成可执行文件（二进制）
  3. 高级语言编写程序所需环境：（1）语言处理程序； （2）语言处理系统； （3）语言运行时的系统； （4）操作系统内核； （5）操作系统； （6）指令集体系结构； （7）人机接口

1.4 计算机系统层次结构

  • 过程式语言：如何做； 非过程化语言：做什么；语言发展是不断抽象的过程
  • 应用->算法->语言->操作系统->(软件)ISA指令集（硬件）->微体系、功能部件、电路和器件
    非预期结果是硬件层次造成的。上层是下层的抽象，下层是上层的实现，底层为上层提供支撑环境
  • 题目：由机器语言编程的早期计算机系统中，没有ISA这一层次（F）；一直都有ISA，因此ISA是计算机体系层次中最重要的层次。
    ISA， Instruction Set Architecture（结构）规定了如何使用硬件，是可以执行的指令的集合，包括指令格式、操作种类及操作数的类型的规定…
    没有ISA，软件无法使用计算机硬件，一台计算机就不能成为“通用”计算机
  • 计算机组成必须能够实现ISA规定的功能；同一种ISA可以由不同的计算机（硬件）组成，如乘法指令用ALU或乘法器都可以实现
  • 题目：有没有乘法指令是ISA考虑的问题，如何实现乘法指令是微体系结构考虑的问题

1.5 计算机系统基础学习目标

  • 编写高效程序必须了解计算机底层结构
  • 必须掌握并行程序设计技术和工具
  • 课程目标：理解计算机如何生成和运行可执行文件
  • 涉及层次：C语言设计层，ISA和汇编层，微体系结构和硬件层
  • 第一部分 程序表示与转换；第二部分 执行控制流

2.0 数据表示和存储

2.0 错题

  1. 负整数转换无符号数。没有把负数转成补码！
    ![[…/Source/Photo/ICS/错题本/2 负有符号转无符号.png]]
  2. 大无符号数转带符号数。理解错误！-1取补码，各位取反再加1，就是全1！
    ![[…/Source/Photo/ICS/错题本/2 大无符号转带符号.png]]
  3. 无符号数和带符号数混合运算。和上题一样的错误，没有补码转换思维！
    ![[…/Source/Photo/ICS/错题本/2 无符号和带符号混合运算.png]]

2.1 编码和数制

  • 数据在计算机中表示的三要素：
    1. 进位计数制（2 8 10 16）
    2. 定、浮点表示（小数）
    3. 如何用二进制编码（正负号：原码、补码、反码、移码）

2.2 定点数的编码表示

2.2.1 定点数的编码表示

  • 定点数：定点整数，定点小数，可以用于表示浮点数
  • 原码：正号为0，负号为1；缺点：加减运算不统一，需要额外符号位，不利于硬件设计，a<b时a-b困难
  • 移码：一个数值加上一个偏置常数；便于浮点数加减运算、比较大小
    例如，补码和移码表示的两个浮点数：

2.2.2 模运算系统和补码表示

  • 8是 -4对模12的补码，10+8 % 12 = 10-4（-4的模12补码为8）8+4=12
  • 负数的补码是 模减去该负数的绝对值
  • 补码 modular运算：+和-的统一
  • 4位十进制数模运算：9828-1928 = 9828+(10^4-1928)=1 7900 = 7900(mod 10^4)；1928的补码8072（和为9999，末尾+1）
  • 0100 0000 的8位二进制补码 1011 1111 + 1 = 1100 0000 （每一位取反，再加1），也可以用2^8 - 0100 0000计算
  • 题目：补码位数为8，-1000b的补码表示是：1111 1000（别忽略前面四位！）
  • 运算器适合使用补码：运算器只有n位，所有运算结果都只能保留低n位，是一个模2^n的计算器
  • 补码的定义：X补 = 2^n + X。X是真值，X补是机器数

2.2.3 补码和真值的对应关系

  • 特殊数的补码
    1. 0的补码：0
    2. -1的补码：n个1（2^n - 01）
    3. -2n-1的补码：10…0（n-1个0，相当于2n - 2^n-1）
  • 题目：32位机器中，int类型-1的机器数是：32位1 32位机器int、short、char分别占32位、16位、8位
  • 变形补码： 4’s comlement两个符号位，用于存放可能溢出的中间结果
    ![[…/Source/Photo/ICS/课程/变形补码.png]]

例如，8的补码为1000，用四位补码则符号位为1（负数）

  • 例如：8位机器123和-123的补码
    123: 0111 1011
    -123: 1000 0101（简便方法，从又到左除第一个1以外全部取反）
  • 快速求补码真值：
    1. 普通求法：-1，除了符号位按位取反，然后B转D
    2. 快速求法：-N2^n-1 + N2^n-2（原来是公式求法，难算，用上面的办法）
      例如：1101 0110
      算法1：1010 1010 = -(32+8+2)
      算法2: -128+64+16 +4+2 = -42（好像不是很快^ ^）

2.3 C语言中的整数

2.3.1 无符号整数与带符号整数

  • 两种位串排序方式
    1. 高位到低位 从左到右
    2. 高位到低位 从右到左
    • 因此用LSB表示最低有效位，MSB为最高有效位
  • 无符号整数：不带符号位，多一个MSB；
    如16位无符号整数最大可以表示的数是2^16=65536
    用于不出现负值的场合，如地址运算、编号表示
  • 补码的好处：
    1. 模运算系统，加减运算统一
    2. 0可以唯一表示，没有正负号
    3. 比原码多表示一个最小负数（-128~127）

2.3.2 C语言程序中的整数举例

(unsigned) int (short / long)

  • 如果同时有无符号和有符号，会把有符号强制转换成无符号数
    如 -1 < 0(unsigned）值为false，因为把-1转成1111了
    如 2147 4836 47 > -2147 4836 37 - 1 值为false，因为后面的有一个符号位，转换后相当于前面+1的真值
    ![[…/Source/Photo/ICS/课程/unsigned.png]]
  • 题目：已知2147483647为2^31-1, C语言中的关系表达式"2147 4836 47U > -2147 4836 47-1"的结果是 假，前后都会转换成unsigned
  • int x = -1
    %u 4294 9672 95，%d -1

2.4 浮点数的编码表示

2.4.1 浮点数的表示范围

  • 规格化形式：小数点前只有一位非0数，小数点后第一位总是为1（所以经常省略，用23个二进制位表示24位尾数）
  • 32位浮点数格式的规格化数表示范围
    0位为符号位S，18位用8位**移码**表示阶码E(偏置常数128)；931位用24位二进制原码表示尾数M
    +/- 0.1xxx(M 23位) * 2^E
    max: (1-2^-24) * 2^127(偏置128+127=255)
    min: (1/2) * 2^-128(128-128=0)
  • 由于原码对称性，浮点数表示范围关于原点对称
  • 题目：若浮点数结果位于上溢区，则说明其值大于最大可表示数 false，大于max或小于min
  • 机器0：尾数为0或落在下溢区的数(下溢区太小取近似为0)
  • 早期，不同体系结构计算机所用的浮点数表示格式是不一样的，在不同计算机之间进行程序移植时，需要考虑浮点数格式之间的转换。

2.4.2 IEEE 754标准的规格化数

  • 阶码没有全0和全1，只有00…01和11…10 (-126~127)
  • S(single)P: (-1)^S * (1+Significand) * 2(Exponent - 127)(用127那么最大254-127=127范围更大，用128就成了最大为126)
  • D(double)P: Exponent - 1023
  • 例子：float变量x机器数为BEE00000H，求x的真值
    1| 011 11101| 110 0000 0000 0000 0000
    = (-1)^S * (1+Significand) * 2^Exponent-127
    • 阶码：0111 1101B = 125
    • 阶码的值：125-127=-2
    • 尾数部分的值：
      1 + 1* 2^-1 + 1* 2^-2 + 0* 2^-3…
      = 1 + 2^-1 + 2^-2
      = 1.75
    • 真值：-1.75 * 2^-2 = -0.4375

2.4.3 IEEE 754特殊数（规格化以外）

  • 0的机器数
    符号 阶码全0 尾数全0
  • 正负无穷+/-inf（浮点数除以0的结果）
    符号 阶码全1（255） 尾数全0
    5.0 / 0 = +inf
  • 非数NaN（如-4.0开根，不存在）
    阶码全1 尾数全0
  • 非规格化数
    最小规格化数：2^-126（0.00…01）
    在 0~最小规格化数 间就是非规格化数
    阶码全0 尾数非0
    当输入数不可表示，机器将其转换成最近的可表示数
  • 题目：从键盘上输入61.420001赋值给一个float型变量x，再打印输出x时，其结果为61.420002。以下描述的是由此推断出的一些结论，其中哪些是正确的？
    由此说明能精确表示的float型数据的有效位数最多为7位。为什么，因为61.42000(7位)是精确的吗？
    由此说明32位IEEE 754单浮点数格式无法精确表示61.420001，可以精确表示61.420002。

2.5 非数值数据的编码表示

  • 非数值数据：逻辑数据、音乐
  • 逻辑数据
    • 表示：用1位表示。n位可以表示n个逻辑数据
    • 运算：按位进行。按位与、或，逻辑左、右移
    • 识别：和数据一样是01序列，计算机靠指令识别
  • 西文字符编码
    • 7位（256个）ASCII码
    • 操作：传送、比较
    • 0~9：48D, 30H~39H
    • A~Z：65D, 41H
    • a~Z：97D, 61H
    • 空格：20H
    • 回车：0DH, 0AH
  • 汉字国际字符编码
    • 输入码：用于输入（输入法，拼音、双拼）
    • 内码：在系统中存储、查找、传送
    • 点阵\轮廓(输出码)：用于输出
    • 西文没有输入码，有内码和点阵、轮廓码
  • GB2312-80字符集
    • 区位码和国标码：
      区号位号各加上32(20H)即为国标码
      行号为区号，列号为位号，各占7位，共14位
    • 必须用两个字节表示，2B = 16bits，2^16 = 65536 > 6万汉字
    • 内码表示：国标码最高位设为1，与ASCII区分
  • 多媒体信息（图形、图像、音频、视频）
    • MIDI：音乐信息

2.6 数据宽度和存储容量的单位

  • bits, Byte, word(字，与字长不同，如IA32字为16b，字长为32b)
  • Byte：存储器按字节编址，需要表示最低、最高有效字节(LSB、MSB)
  • 字长：定点数据通路宽度，等于CPU内部总线宽度、运算器位数、通用寄存器宽度
  • 字： 被处理信息的单位
  • 不同机器表示同一类型的数据可能宽度不同
    如char* 32位4B，64位8B

2.7 数据存储时的字节排列（大小端）

  • int型变量x=-10，存放地址为100，机器数为FF FF FF F6，占4单元
    Q1：变量地址是最大地址还是最小地址？
    • 最小地址，即x存放在100~103中
      Q2：多个字节在存储单元中存放顺序如何？
    • 大端法、小端法
      大端法(顺序）：MSB所在地址是数的地址，100 101 102 103，取100
      小端法：LSB所在地址是数的地址，103 102 101 100，取100
      [photo]
    • 大小端表示的数据内容是一样的，只不过存放顺序不同，读取时会处理成一样的数据

3.0 运算电路基础

3.0 错题

  1. CPU基本运算部件是ALU，不是加法器
    ![[…/Source/Photo/ICS/错题本/3 基本运算部件ALU.png]]
  2. 异号补码运算，真值肯定不会超过可表示范围，不会产生溢出OF信号！
    ![[…/Source/Photo/ICS/错题本/3 异号补码运算.png]]

3.1 数字逻辑电路基础

3.1.1 布尔代数和基本逻辑电路

  • 布尔代数：关于0和1的数学运算体系
  • 真值表：输入、输出之间的关系
  • 与：^/* ，或：v/+
  • n位逻辑运算：按位与、或，用n个门电路实现
  • 门电路分类
    • 组合逻辑电路：没有存储功能，输出仅仅取决于当前输入
    • 时序逻辑电路：有存储功能，不仅依赖当前输入，还依赖存储单元当前状态
    • 组合逻辑部件（功能部件）：译码器、编码器、多路选择器、加法器
  • 如何实现功能部件：
    1. 真值表
    2. 逻辑表达式
    3. 电路
  • 多路选择器（MUX）

3.1.2 无符号数加法器

  • 一位加法器 全加器：
    F = A异或B异或Cin（低位进位）
    Cout = AB + ACin + BCin
  • 题目：关于全加器的叙述，错误的是。全加器只能由与门、或门和异或门实现
  • n位加法器：n个全加器，每个Cout接入高位的Cin
  • 重要认识：加法器由逻辑部件实现，而其他运算部件都基于加法器和逻辑运算实现；因此，所有运算都是基于0和1以及逻辑运算实现的。
  • 题目：关于n位加法器，错误的是。n位加法器的输出包括一个n位的数和一个n位的进位Cout。 只有一个Cout
  • n位带标志加法器
    • n位加法器无法用于两个带符号整数（补码）相加，无法判断溢出
    • 程序经常需要比较大小，通过做减法得到的标志信息来判断
    • OF溢出标志：Cn异或Cn-1
    • SF符号标志：Fn-1
    • ZF零标志：F=0时为1（或非所有F）
    • CF进位、借位标志：Cout异或Cin
  • n位带标志加法器和n位加法器一样可以实现无符号加运算，输入也完全一样，带标志多输出了几个标志信息

3.1.3 整数加/减运算器和ALU

  • n位整数加减运算器：计算机需要电路可以表示x, y的补码以及计算x+/-y的补码
    多路选择器选择原码/各位取反输出（多一路Sub输入决定加法、减法（补码））：实现了带/无符号整数加、减
  • 题目：以下关于整数加/减运算器的叙述中，错误的是：整数加/减运算器不可以实现两个无符号数的加/减运算。
    • 整数加/减运算器的输入为两个运算的操作数和一位控制信号sub。
    • 整数加/减运算器通过输出的标志信息确定运算结果是否正确。
  • ALU
    • 进行基本算术、逻辑运算
    • 核心电路是带标志加法器
    • 输出除了和、差，还有标志信息
    • 有一个操作控制端（分配器）用来决定ALU执行的处理功能
  • 题目：以下关于ALU的叙述中，错误的是：ALU可以实现加、减、乘、除运算。 只有加减运算

3.2 从C表达式到逻辑电路

  • 基本数据类型
    • 整数：无符号、带符号
    • 浮点数
    • 位串、字符串
  • 基本运算类型
    • 关系运算：比较大小，实际上是减法
    • 按位运算 | & ~ ^
    • 逻辑运算
    • 移位运算
    • 扩展和截断
  • 例如：y=(x>>2)+k如何实现
    1. 转换为运算指令序列
      • sarw $2, %ax; x>>2
      • addw %bx, %ax; (x>>2) + k
    2. 计算机直接执行指令完成运算
      • 控制器对指令译码，产生控制信号送运算电路
    3. 操作数在运算电路中运算
      • sarw $2, &ax：将操作数“2”和“R[ax]”送移位器运算
      • addw %bx, %ax：将R[ax]和R[bx]送整数加减器中运算
      • 移位器、整数加减运算器由逻辑门电路构成
    4. 高级语言执行指令进行两次转换：1. 转换成指令；2. 指令在电路上执行
  • 高级语言涉及的运算
    ![[…/Source/Photo/ICS/课程/3.2 数据的运算.png]]
  • 题目：指令系统中有专门的浮点数左移和右移运算指令。（错误） 只有整数有左右移运算

3.3 C语言中的各类运算

  • 算术运算
  • 按位运算
    • 掩码或其他处理
  • 移位运算
    • 提取部分信息
    • 扩大(<<)、缩小(>>)2^n倍
    • 移位操作可能溢出、丢失信息
    • 题目：8位带符号整数的补码表示为1001 0101，右移一位是：1100 1010 最高位的1也要右移，并且保留符号位
  • 移位运算、按位运算举例
    1. x最高有效字节不变，其余全0：右移到只剩下八位，再左移回来
    2. x最低有效字节不变，其余全0：x和0xFF按位与
    3. x最低有效字节变0，其余取反：用1异或x（取反），右移8位再左移回来
    4. x最低有效字节变1，其余不变：x和0xFF按位或
  • 逻辑运算
    • 与按位运算的区别：运算的是整体（而不是按位），结果返回一个逻辑值（而不是位串）
  • 位拓展和位截断运算
    • 拓展：短转长
      • 无符号：补0
      • 有符号：补符号
    • 截断：长转短：
      • 高位丢弃（可能溢出）
    • 例子：
      ![[…/Source/Photo/ICS/课程/3.3 位拓展举例.png]]
      ![[…/Source/Photo/ICS/课程/3.3 位截断溢出举例.png]]
      溢出导致正数32768变成负的(在short类型最高（符号）位上)

3.4 整数加减运算

3.4.1 加减运算生成的标志信息

  • 加减运算部件
    • 所有运算都基于此加法器
    • 加法器不知道运算的数带不带符号
    • 加法器不判定对错，只输出低n位
  • 条件标志位（条件码CC）
    • 被记录到专门的寄存器（程序、状态字寄存器或标志寄存器）中
    • 题目：假定整数加/减运算器的两个输入端分别是A和B，以下关于整数加/减运算器的叙述中，错误的是。不管是带符号整数还是无符号整数，做减运算时，只要借位标志CF=1，就说明有借位，即A小于B。
    • 题目：以下关于n位带标志加法器的叙述中，错误的是。进位标志CF等于加法器的进位输出Cout。 同时也表示借位
      • 正确项：当两个加数的符号相同且不同于和的符号，则溢出标志OF=1。符号标志SF与和的符号位Fn-1相同。在整数加/减运算器中的加法器是n位带标志加法器。
    • 举例
      ![[…/Source/Photo/ICS/课程/3.4 整数加法运算举例.png]]

3.4.2 加减运算溢出公式及举例

  • 判断无符号数相加有没有发生溢出的程序
    • 发生溢出时，一定满足1. result<x && result<y (x+y-2^n>=x, y>=2^n明显错误)
int uadd_ok(unsigned x, unsigned y)
{
    unsigned sum = x+y;
    return sum>=x;
}
  • 判断带符号数相加有没有发生溢出
int tadd_ok(int x, int y)
{
    int sum = x+y;
    int neg_over = x<0 && y<0 && sum>= 0
    int pos_over = x>=0 && y>= 0 && sum<0
    return !neg_over && !pos_over;
}
  • 上面的函数改成判断相减有没有溢出
int tsub_ok(int x, int y)
{
    return tadd_ok(x, -y)
    // 当x=0，y=0x8000 0000时错误,最大负数不能表示
}

4.0 乘除运算及浮点数运算

4.1 整数乘法运算

  • 乘法运算，计算机只取低n位
    • int类型乘法不一定大于0（溢出）
    • float类型乘法一定大于0
  • 如何判断返回值z正确：!x || z/x==y
  • 编译器怎样判断不溢出：−2n−1<=x∗y<2n−1-2^{n-1} <= x*y < 2^{n-1} ，即高n位为全0或全1，并且低于低n位（int类型占用bits）的最高位；乘积高n+1位为全0/1
    • 若为unsigned类型，高n位全0就没有溢出
  • 题目：以下是关于整数乘运算（z=x*y）结果溢出判断规则的描述，其中错误的是。如果是C语言程序员，可以采用"若(y!=0 || x==z/y)，则结果z不溢出"的规则。 !x || z/x==y，题目中y!=0错误
  • 无符号和带符号乘法器的关系
    • 不同的是高n位（因此可以用无符号乘法器实现带符号乘法，但此时不能靠编译器判断了）
  • 硬件不判断溢出，只保留2n位乘积
    • 如果程序和编译器都没有溢出处理，就会出问题
    • 指令：分为无符号、带符号乘指令
  • 例子：malloc(count*sizeof(int))，若count很大，会溢出，堆中大量数据会被破坏（数组大小不够但是程序强行写入）
  • 乘法运算需要多个时钟周期，而移位、加减法只需要一个或更少的时钟周期，因此编译器处理变量与常数相乘时，常常把乘法优化成移位、加减的组合运算
    • 例如x*20，20 = 16+4 = 2^4 + 2^2，可以转化成（x<<4)+(x<<2)（溢出和乘法运算相同）

4.2 整数除法运算

  • 带符号整数，n位整数除以n位整数，只有-2^(n-1)/-1 = 2^(n-1)会溢出（正数表示范围比负数小）
  • 整数除法舍入：整数向下取（floor），负数向上取（ceiling）
  • 整除0：无法表示，发生异常；操作系统异常处理
  • 0x80000000 / -1 和 / b(b=-1)，后者检测到异常（floating point exception），前者不会，因为-1被编译器优化为neg（取负）
  • 除法指令比乘法指令还要长（30+时钟周期），无法用流水线实现，尽量别做除法（编译器优化neg的原因）
    • 可以整除，用>>右移计算
    • 不能整除，右移的位有非0，做相应处理
  • 不能整除，朝零舍入（截断）
    • 无符号、带符号正整数：移出位直接丢弃
    • 带符号负整数：加偏移量（2^k-1），再右移、低位截断（k是右移位数）
  • 举例
    ![[…/Source/Photo/ICS/课程/4.2 整数除法运算.png]]

4.3 浮点数运算

4.3.1 浮点数加减运算

  • 若A=Ma∗2Ea,B=Mb∗2EbA = M_a*2^{E_a}, B = M_b*2^{E_b}, 则A+B=(Ma+Mb∗2−(Ea−Eb))∗2Ea(Ea>=Eb)A+B = (M_a+M_b*2^{-(E_a-E_b)})*2^{E_a}(E_a>=E_b)，阶小的数尾数右移
    ![[…/Source/Photo/ICS/课程/4.3.1 浮点数四则运算原理.png]]
  • 可能情况：
    • 阶码上溢：正指数超过最大允许值，+/-inf/溢出（SP最大指数127）
    • 阶码下溢 ：+/-0（SP最小指数-126）
    • 尾数溢出：最高有效位有进位(1.5+1.5=3(11B))，右规（右移1位，再加1）尾数溢出，结果不一定溢出
    • 非规格化尾数：数值部分高位为0(0.xxx)，左规
    • 右规或对阶（使阶码相等）时，右端有效位丢失：尾数舍入，在运算过程添加保护位（把可能丢弃的位保留，最后再舍入）
  • IEEE 754五种异常情况
    • 无效运算
      • 运算时有一个非有限数
      • 结果无效
    • 除以0，无穷大
    • 数太大，阶上溢
    • 数太小
    • 结果不精确（舍入引起），如1/3,1/10
  • 例子：除0，int类型发生错误，double浮点型有结果（正负无穷大）
  • 例子：1.123*10^5 + 2.560*10^2
    • (1.123+0.00256)*10^5
    • 1.12556舍入56，得1.126*10^5
    • IEEE 754会保留右移尾数的最高位，最后才舍入
  • 基本要点
    1. 求阶差
    2. 对阶（保留附加位，即最高位1）
    3. 尾数加减
    4. 规格化：
      • 尾数高位为0，左规
      • 尾数最高位有进位，右规
      • 阶码溢出异常处理：溢出（上溢）或0（下溢）
    5. 尾数比规定位数长（或有附加位），舍入
    6. 运算结果尾数是0，将阶码设置成0（只有阶码和尾数全为0才是0）
  • 例子：0.5+（-0.4375）
    • 注意机器中用2进制计算，因此0.5=1.0B*2^-1, -0.4375=-1.110B*2^-2(0.25+0.0625)
    • 对阶：0.111*2^-2 -> 1.111*2^-1
    • 加减：(1.000-0.111)*2^-1
    • 左规：1.0*2^-4
    • 判断溢出：无溢出
  • （没懂）问题：为什么IEEE 754加减运算右规最多只需一次 因为最大的尾数相加整数部分最多有两位（和的尾数不超过4）

4.3.2 浮点数运算的精度

"Floating Point numbers are like piles of sand; every time you move one 
 you lose a little sand, but you pick up a little dirt."
  • 如何使得失去的“沙”和捡回的“dirt”少一点？**增加附加位！**多少位合适？没有准确答案；
    IEEE 754规定中间结果需要在右边加两个附加位
  • Guard（保护位）：significand右边的位
  • Round（舍入位）：保护位右边的位
  • 附加位的作用：用来保护对阶时右移的位或运算的中间结果
  • 附加位的处理：1）左规时被移到significand；2）作为舍入的依据
  • 例子：2.3400+0.0253=2.3653，若没有舍入位3，则依据5舍入，结果为2.36；而有3作为依据，则结果为2.37
  • IEEE舍入标准（4种）：
    1. 就近舍入（0舍1入）精度最高
      • 舍入数大于中间数（01）：末位加1
      • 舍入数小于中间数（11）：截断、丢弃
      • 相等（10）：最近偶数
    2. 朝+/-inf舍入；朝0舍入
  • float类型和double类型
    • float范围：3.4∗10383.4 * 10^{38}
    • double范围：1.8∗103081.8 * 10^{308}
    • float类型可表示7个十进制有效位
    • int转float可能舍入丢失精度，转double（52+1位表示）不会；但double转int或float会溢出
  • **浮点数不满足结合律：**大数与小数对阶，小数全部移位移没了

4.3.3 浮点数运算精度举例

  • 96年Ariana5火箭爆炸，5亿美元
    • 原因：64位float转16位int，溢出
  • 91年海湾战争，爱国者导弹定位错误
    • 软件时钟浮点数精度问题，0.1的机器数是无限循环序列，约等于9.54*10^-8；飞毛腿导弹连续工作100小时，误差了0.343秒，2000m/sec，误差为二者相乘687米
  • 用32位定点小数表示0.1，比float精度高64倍
  • 用float相乘比直接把两个二进制数相乘要慢用确定小数常量效率更高

第一阶段拾遗

  1. ISO C90标准下, 在32位系统上以下C表达式的结果是什么?
    -2147483648 < 2147483647, false(与事实不符)!Why?
    • C语言编译器将2147483648==pow（2，31）看成无符号整型，机器数为0x8000 0000，因此表达式是false
      int i = -2147483648;i < 2147483647，true!Why?
    • 这次编译器把两边的数都看做带符号数，负数一定小于正数
  2. 对于任何int型变量x和y, (x>y) == (-x<-y) 总成立吗?
    当x=-2147483648, y任意(除-2147483648外)时不成立, Why?
    • x为最小负数时，表示为100...000，这时-x取补码仍然是最小负数；此时无论y取什么值，等式右边恒成立，左边恒不成立
  3. 下面的代码
    打印结果是什么? d=0, x=1 072 693 248, Why?
// p1.c
double d;
void p1( )
{
    d=1.0;
}

// main.c
int d=100;
int x=200;
int main()
{
    p1( );
    printf (“d=%d, x=%d\n”, d, x );
    return 0;
}
  • 在p1中，d变成了double类型，占8个字节；而在全局变量里d和x各占4字节，在d转成浮点数的过程中发生了溢出，而溢出的值影响到了后面的x。
    (double)1.0D = 0000 0000 0000 F03FH, 1 072 693 248D = 3f f0 00 00H
  1. float类型机器数和真值转换
    • 机器数转真值
      1. 1| 011 11101| 110 0000 0000 0000 0000先划分符号位、阶码和尾数
      2. 阶码转10进制，减去127，127-2-127 = -2
      3. 尾数转10进制，记得加1，0.5+0.25+1 = 1.75
      4. 真值 = 尾数 * 2^阶码，-1.75 * 2^-2 = -0.4375
    • 真值转机器数
      1. 24.678转二进制，并划分整数部分和小数部分
      2. 1 1000.101整数部分用科学计数法表示1.1000 101 * 2^4
      3. 计算阶码，4+127=3+128
      4. 小数部分就是尾数，照抄，0| 100 00011| 100 0101 0000 0000 0000

第二阶段 程序的执行和存储访问

参考MOOC：NJU-1001964032

1.0 程序执行概述

1.0 错题

  1. CPU中控制器的功能是（ ）。
    B. 完成指令译码，并产生操作控制信号

  2. 冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU依据（ ）来区分它们。
    B. 指令和数据的访问时点不同

  3. 下列寄存器中，用户可见的（即：机器级代码程序员能感觉其存在的）寄存器是（ ）。
    D. 程序计数器（PC）
    程序计数器（PC）是用户可见的寄存器。在汇编语言编程中，程序员可以直接操作或引用程序计数器，例如通过跳转（jump）指令来改变程序的执行流程。

  4. 下面是有关CPU中部分部件的描述，其中错误的是（ ）。
    B. IR称为指令寄存器，用来存放当前指令的操作码
    这个描述是错误的。IR（Instruction Register）确实是用来存放当前正在执行的指令，但它不仅包含操作码（opcode），还可能包含操作数（operand）或其他指令信息。

  5. 下列有关程序计数器PC的叙述中，错误的是（ ）。 ‎ ‌ ‎
    A. 指令顺序执行时，PC的值总是自动加1
    程序计数器（PC）的值在指令顺序执行时通常会增加，但增加的量取决于当前执行的指令的长度，而不是固定的1。
    每条指令执行后，PC的值都会被改变，否则会永远执行某一条指令。

  6. 机器主频的倒数（一个节拍）等于（   ）。
    D、时钟周期
    时钟周期是CPU工作的最小时间单位，也称节拍脉冲或T周期，其值等于机器主频的倒数。

  7. 任何指令周期的第一个阶段都是取指令阶段，需要访问存储器。

1.1 程序和指令的关系

  • 程序和指令的关系
    • 程序由一条一条指令组成
  • 程序的执行：周而复始地执行一条一条指令
  • 程序的执行流的控制
    • 可以通过改变PC（程序计数器）的值来控制执行顺序，因为要执行的指令的地址就是PC给的
  • 指令周期：CPU取出并执行一条指令的时间
    • CPI: Cycles Per Instruction

1.2 一条指令的执行过程

  • 取指令->算操作数->取操作数->操作->计算下条指令地址
  • 每一步都会检测异常，若有异常，自动切换操作系统异常处理程序。如越界（第6章）、非法译码、缺页（没取到）、除0/溢出
  • 问题：“取指令”一定在最开始做吗？PC+"1"一定在译码前做吗?“译码”必须在指令执行前做吗？ - 取指令一定在最开始做；
    • PC+1随便在哪里做，在下条取指令之前做就行了；
    • 译码一定在指令执行前做
  • 异常和中断的差别
    • 异常是程序性中断，和指令相关
    • 中断是IO发出的外部中断，如Ctrl^c，打印机缺纸
  • 取指令：从PC所指单元取指令发送到IR（指令寄存器），并增加PC；一般按最长的指令取；或先取一个字节，看看是什么指令，再决定是否继续取
  • 取操作数：如果在寄存器，不用访存；在存储器需要一次或多次访存

1.3 IA-32指令的大致执行过程

  • 四种基本操作
    • 取指令、操作数 LOAD
    • 算术逻辑运算
    • 存储（数字、结果）
    • 寄存器、ALU间传送
  • IA-32体系结构
    • 8个GPR（通用寄存器，标号0~7）
    • 可寻址空间4GB
    • 取指令格式变长、操作码变长
    • 由若干字段（OP、Mod、SIB）组成
  • 寻址方式
    • 基值+有效地址+位移量

1.4 CPU的基本功能与结构

  • 起始EIP（扩展指令指针） = 第一条指令的地址
  • 指令执行结果
    1. 取指令：EIP -> MAR -> 地址线 -> 控制线 -> 数据线 -> MDR -> IR（指令寄存器） -> 控制器译码
    2. 译码，指令执行：ESP-4， EBP送到MDR（EBP是数据）,ESP送到MAR（ESP是地址）（指令内容），写入内存。最后PC+1
  • ALU结构原理：多路选择器选择加减乘除其中一路输入（所有门电路都会运算！）

2.0 主存储器组织

2.0 错题

  1. 假定用若干个16K×8位的存储器芯片组成一个64K×8位的存储器，芯片各单元交叉编址，则地址BFFFH所在的芯片的最小地址为（   ）。
    B、用若干个16K×8位的存储器芯片构成64K×8位的存储器，需要64K×8位/（16K×8位）= 4个芯片。因为采用交叉编址方式，所以，存储单元地址对4取模后，低两位相同的存储单元在同一个芯片中。 BFFFH的最低两位为11，显然，与0003H在同一个芯片中。

  2. 下面有关半导体存储器组织的叙述中，错误的是（   ）。
    B. 同一个存储器中，每个存储单元的宽度可以不同
    这个叙述是错误的。在同一个存储器中，所有存储单元的宽度（即每个存储单元可以存储的数据位数）是相同的。存储单元的宽度决定了存储器的数据总线宽度

  3. 某32位计算机，主存地址为32位，按字节编址，则该计算机的主存地址范围是（  ）。
    B. 0～(4G-1)
    在32位计算机中，主存地址是32位长，这意味着地址空间的大小是2的32次方字节。由于每个字节由8位（1字节）组成，所以地址空间的总大小是：
    2^32 字节 / 8 = 2^30 字节
    这等于4GB（Gigabytes）。因此，主存地址范围是从0到4GB减1（即4,294,967,295），因为地址是从0开始计数的。

  4. 假定主存地址空间大小为1024MB，按字节编址，每次读写操作最多可以一次存取32位。不考虑其它因素，则存储器地址寄存器MAR和存储器数据寄存器MDR的位数至少应分别为（ ）。
    C. 30，32
    存储器地址寄存器（MAR）的位数决定了CPU可以寻址的内存空间大小。由于主存地址空间大小为1024MB，我们需要计算出对应的位数：
    1024MB = 1024 * 1024 * 1024字节 = 2^20 * 1024 * 1024字节 = 2^30字节
    因此，MAR至少需要30位来表示这个地址空间。
    存储器数据寄存器（MDR）的位数决定了每次读写操作可以处理的数据量。题目中提到每次操作最多可以一次存取32位，这意味着MDR至少需要32位来存储这些数据。
    所以，MAR至少需要30位，MDR至少需要32位。

  5. 存储容量为16K×4位的DRAM芯片，其地址引脚和数据引脚数各是（ ）。
    D. 7和4
    存储容量为16K×4位的DRAM芯片意味着它有16K个存储单元，每个存储单元可以存储4位（即半个字节）数据。首先，我们需要计算地址引脚数：
    16K表示16 * 1024，即16384个存储单元。要表示16384个存储单元，我们需要足够的地址引脚来提供唯一的地址。计算所需的地址引脚数：
    2^n = 16384
    解这个方程，我们得到 n ≈ 14。所以，我们需要14个地址引脚来寻址16384个存储单元。又因DRAM行列复用，7个引脚即可
    接下来，数据引脚数由存储单元的数据宽度决定。由于每个存储单元是4位宽，我们只需要4个数据引脚来传输这些数据。
    因此，答案是7个地址引脚和4个数据引脚。

  6. 下面有关ROM和RAM的叙述中，错误的是（   ）。
    计算机系统的主存都用DRAM芯片实现。DRAM的roll buffer是SRAM做的！

  7. 下面有关半导体存储器的叙述中，错误的是（   ）。
    C、有些情况下，可用半导体存储器实现相联存储器，即按内容进行访问，而不是按地址进行随机读写。
    ‏

2.1 存储器基本概念

2.1.1 访存操作与基本术语

  • 许多指令都要访存，是一个非常重要的概念
  • 栈是主存中的一个区域
  • 术语
    1. Cell单元，表示0/1
    2. Addressing Unit
    3. Bank
    4. Addressing Mode
    5. MAR, MBR

2.1.2 存储器分类

  • 分类
    1. RAM，如内存。每个单元读写时间一样，与各单元所在位置无关（不考虑roll buffer）。
    2. SAM（顺序），如磁带。按顺序读写，存储时间长短与信息位置有关。
    3. DAM，如磁盘。直接定位到读写数据块，读写数据时按顺序进行。
    4. ©AM，如快表。按内容检索到存储位置进行读写。不需要根据位置、地址，而是根据内容检索。
  • 内存与外存关系、比较
    1. 外存 -> 内存，程序、数据成批传送
    2. 内存 -> CPU，CPU逐条读取指令、数据
    3. CPU -> 内存，指令处理结果送回内存
    4. 内存 -> 外存，处理结果成批送到外存（回写）

2.2 主存基本结构

  • 8个cell（记忆单元）构成一个存储单元，从全0开始编号，同一个存储单元字线连在一起，同时读整个存储单元
  • 问题：主存中存放的是？指令和数据；CPU何时访问主存？取指令、取数据、存数据的时候

2.3 主存的性能指标

  • 存储时间（Access）： 读取时间和写入时间
  • 存储周期（Memory Cycle）：连续两次访问存储器所需的最小时间间隔，比Access Time更长，有一个预充电（预处理）的时间
    ![[…/Source/Photo/ICS/课程/Part II/2.2 单位.png]]

2.4 半导体存储器组织

  • 六管静态MOS管电路（SRAM，集成度低）
    • 相当于带时钟的RS触发器，无需刷新
  • 动态单管记忆单元电路（DRAM）
    • 对电容充电，所以速度慢。元件少、集成高。破坏性读出，会漏电（但是CPU速度比漏电速度快），需要刷新。
  • 半导体的RAM组织
    • Cell -> Chip -> Memory
    • 相同字的Cell字线连在一起，SRAM与ROM，字片式
    • 二维位片式，DRAM
      -DRAM芯片举例
    • 16Mb = 4Mb*4 = 2048*2048 *4 = 2^11 * 2^11 * 4
    • 问题：为什么每一代DDR都会扩大四倍内存？行列分时复用，每一代DDR都会增加至少一根地址线，即行、列各增一位，所以容量至少提升4倍。用行、列地址选通信号（RAS\CAS）决定传送的是行、列地址

2.5 内存条组织与总线宽度

2.5.1 SPARCstation（工作站） 20的内存条

  • 存储器总线宽度为128，内存条可以一次读取128bits
  • 2Mb = 256K * 8 = 2^9 * 2^9 * 8，即8行8列
  • 行缓存roll buffer是SRAM做的，保持了速度！
  • 各个芯片同一行同时读取到roll buffer

2.5.2 PC中的内存条

  • 主存地址27位，片内地址24位与高24位主存地址相同，低3位用来选片（一般不用，整个读取），确定8个字节中的哪个。片内地址不是连续的，而是交叉编址（如0, 8, 16），可以同时读写
  • Core i7北桥直接做到CPU里
  • 行与列相等，引脚越少；如不能相等，尽量行比列少，这样可以减少刷新次数（按行刷新）

3.0 磁盘存储器

3.0 错题

  1. 以下有关硬磁盘的磁道和扇区的叙述中，错误的是（）。
    C. 一个磁道由若干扇区构成且磁盘各磁道信息位数总相同
    早期的低密度磁盘中每个磁道信息位数总是一样，但是，现在的磁盘，其外道信息量比内道大

  2. 以下有关磁盘驱动器的叙述中，错误的是（）
    C. 送到磁盘驱动器的盘地址由磁头号、盘面号和扇区号组成
    因为每个盘面有一个磁头，所以磁头号就是盘面号。盘地址由柱面号（即磁道号）、盘面号（即磁头号）和扇区号组成。

  3. 假定一个磁盘存储器有10个记录面，用于记录信息的柱面数为5000，每个磁道上记录信息位数相同，磁盘片外径200mm，内径40mm，最内道位密度为200bpm（位/毫米），则该磁盘存储器的容量约为（）
    我们来计算：(10×5000×π×40mm×200bpm)/8bits = 0.157GB

  4. 假定一个磁盘存储器有4个盘片，用于记录信息的柱面数为2000，每个磁道上有3000个扇区，每个扇区512B，则该磁盘存储器的容量约为（）。
    2×4×2000×3000×0.5KB ≈ 24GB

  5. 假定一个磁盘的转速为7200RPM，磁盘的平均寻道时间为10ms，内部数据传输率为1MB/s，不考虑排队等待时间。那么读一个512字节扇区的平均时间大约为 ( )。
    10ms + (1/7200×60×1000)/2 + 0.5KB/1MB×1024≈14.67ms

  6. 以下有关磁盘存储器读写操作的叙述中，错误的是（）。
     C. 磁盘存储器可与CPU交换盘面上的存储信息
     磁盘存储器以成批方式进行数据读写，CPU中没有那么多通用寄存器用于存放交换的数据，所以，磁盘存储器通常直接和主存交换信息

  7. 磁盘存储器进行读写操作之前，CPU需要对磁盘控制器或DMA控制器进行初始化。以下选项中，不包含在初始化信息中的是（）。
    D. 传送信息所在的通用寄存器编号

3.1 硬盘存储器结构

  • 写入：磁头上有线圈，通过电流改变磁性来写入
  • 读入：磁头不同，载体运动。根据感应电压识别0\1
  • 磁盘：最外面是0磁道
  • 扇区：同心圆分割成扇形，近几年变成4KB扇区，而不是512B
  • 磁道：检测到脉冲，一个扇区就开始了。运用CRC校验，有一个同步字节。（512/600有效信息）格式化就是填补512信息字节以外的信息的过程。

3.2 磁盘驱动器及操作过程

  • 所有磁头同进同出，同步寻道
  • 硬盘操作流程
    1. 寻道，控制磁头（平均寻道时间,5ms左右）
    2. 选择1个磁头读写
    3. 磁盘旋转（旋转等待时间）
    4. 读写
  • 平均存储时间T = 平均寻道时间 + 平均旋转等待时间 + 数据传输时间
  • 题目：每个扇区512B，转速5400RPM，寻道时间12ms，数据传输率4MB/s，磁盘控制器开销1ms，则硬盘响应时间为：
    T = 1 + 12 + [0.5(半圈)*60*1000/5400] + 0.5KB/4MB*1000（实际上局部性会让寻道时间减少1/3，旋转等待时间很重要！）

3.3 硬盘存储器的组成

  • 存储介质：用于保存信息
  • 磁盘驱动器：包括读写短路、读写转换开关，磁头定位系统等
  • 磁盘控制器：控制逻辑、时序电路
  • 寄存器：IO端口（第8章）
  • 磁盘地址寄存器：控制磁头定位系统
  • 操作过程：
    1. 盘地址到寄存器，磁头定位系统，开始旋转，计数器数扇区号，扇区符合比较，开始读写

4.0 高速缓存

4.1 存储器层次结构

  • 构造一个存储系统，又大、又快、又便宜：金字塔层次结构
  • 为什么层次化结构有效？局部性。 图书馆相同的书放在一起，搬的次数减少。预借登记，一堆图书送到某个图书馆，比直接去原来的图书馆借书耗费的时间少。
    • 思考：真正重要的是局部性，而不是层次结构。 例如，一直缓存不命中也是很慢的，层次结构什么也没有做，是局部性让我们加速：是局部性让我们不会一直不命中，而是把搬来的一块数据全部用完，再般下一块数据，从而减少了搬数据的世界，把时间用在处理上。
    • 时间局部性：循环。
    • 空间局部性：数组，结构，循环。

4.2 Cache概述

4.2.1 引入cache的出发点

  • 程序具有局部性特征的原因
    • 指令：连续存放，地址连续；循环或子程序重复执行
    • 数据：连续存放，数组元素重复、按顺序访问
  • 为什么引入cache会加快访存速度？
    • 引入cache，访问一次内存，一直到把内存的数据都用完了，才开始下一次访问内存。减少了访问次数和时间开销。

4.2.2 cache与主存的关系

  • cache如何实现？主存是4*n，把其中一行block(4)复制到cache，如果cache中没有找到要找的数据，就到主存中寻找，然后覆写到cache中（整行block）

4.2.3 cache操作过程

  • CPU给出访存要求，送给cache，判断是否在cache，取数据
  • 若不在cache，访问主存并把1block覆盖到cache的空闲行，缺失处理
  • 因为访问cache，所以给出的地址是虚拟地址，不是主存的地址

4.2.4 实现cache需要解决的问题

  • 哪些问题？
  1. 判断是否在cache
  2. 如何在cache中取数据
    • 如何划分块
      • 划分为大小相同的block，cache被分成line/slot槽
    • 主存块和cache如何映射
    • 放到cache什么地方（随便放、一一对应放）
    • cache已满，怎么办？（先进先出？最近不用的？）
    • 写数据如何保证cache和主存的一致性？（修改了cache后，主存的数据怎么办？其他cpu也要用怎么办？锁住，不给其他cpu用一致性问题：计算机体系结构）
    • 如何根据主存地址访问cache数据？
  • cache对程序员透明：程序员感觉不到cache，不需要了解cache的存在、如何设置，但是对cache深入了解有助于写好的程序。

4.3 cache映射方式

4.3.1 直接映射主存地址划分

  • 什么是cache的映射功能？
    • 把访存的局部主存区域取到cache中，该放到cache的何处？
    • cache行比主存块少，多个主存映射到一个cache行中
  • 如何进行映射？
    1. 把主存空间划分成相等的主存块
    2. cache中存放一个主存块的单位是slot/line，但不叫作page!
    3. 三种映射方式：
      1. 直接Direct：每个主存块映射到cache的固定行，取模放（第一行放小说，第二行放专业书）
      2. 全相联：每个主存块映射到cache任一行（只要有空的就放，随便放）
      3. 组相联（折中）：分组，在每个组里随便放
  • 直接
    • 取模放
    • 有效位：当前slot有没有东西
    • tag：当前slot是哪个主存块0(block0),4(block1),8(block2)?
    • 根据tag判断有没有命中
    • 主存地址：7块主存标记+4cache槽号（行数决定）+9块内地址（块大小决定），4+9就是cache地址；拿块号取模得到cache槽号

4.3.2 有效位和访存过程

  • 有效位
    • 开机、复位，所有有效位V=0
    • 被替换、装入，V=1
    • 使V=0来冲刷cache（进程切换、DMA传送，内核用，特权指令）对操作系统程序员不透明（能够感觉到cache）
  • 实现直接映射
    • tag多少位：主存地址 - 块内地址（块内大小B按字节编址，16B用4bits存储）- 数据区地址（Cache容量除以16（16B一块）得到行数4K行用12bits储存）= tag的位数
  • 如何判断命中Hit
    • 拿slot与高16位相比（与门、比较器），若相等且V=1，Hit
  • Hit后怎么办
    • 根据块内地址高2位，在MUX选择哪个数据word
    • 再根据word（32b）再根据MUX取Byte
      ![[…/Source/Photo/ICS/课程/Part II/4.3.2 访存过程.png]]
  • 硬件实现和软件实现：两条指令以上的功能叫软件实现

4.3.4 Cache容量计算

  • 上图的cache容量多大？
    • 4K行 * (1有效位+16tdg) + 64K数据区 * 8 = 580Kbits = 72.5KB， 数据占64/72.5 = 88.3%
  • 问题：64行的cache，块大小16B，地址1200在哪一行？
    1. (1200/16)块号 % 64 = 11
    2. 1200D（居然是10进制）转2进制 = 1024+128+32+16，取6位tag
  • 问题：实现以下cache需要多少位容量？Cache：直接映射、16K行，块大小4B、32位主存地址
    • 16K * 4B = 64KB数据
    • tag = 32主存 - 14行所需b - 2块所需b
    • 块大小 = 214 ×(32block−size(word)+(32−14−2)tag+1validate)=214×49=784Kbits2^{14}\ \times (32_{block-size(word)} + (32-14-2)_{tag}+1_{validate}) = 2^{14} \times 49 = 784Kbits

4.3.4 直接映射的方式特点

  • 特点
    1. 容易实现，命中时间（决定是否命中+取数据的时间）短
    2. 无需考虑淘汰（替换）问题
  • 缺点
    1. 0,4,8不命中，不够灵活，cache空间不能得到充分利用，命中率低，机器很少用

4.3.5 全相联映射方式

  • 特点
    1. 随便哪一槽都可以放（按内容访问）
    2. 地址分为两个字段：tag=主存块号+块内地址
    3. 命中率高
  • 缺点：
    1. 命中时间长
    2. 比较器位数长，成本高，开销大

4.3.5 组相联（Set Associative）映射方式

  • 特点
    1. 将所有组分行，把主存映射到cache固定组的任意一行。（组间模映射，组内随便放）n行称为n-way
    2. 地址 = 组群标记 + 组号 + 块内地址
    3. 把高位和组内几行一起相比

5.0 Cache替换算法

5.1 Cache替换策略

  • 先进先出FIFO
    • 如果每组4个，循环读取1,2,3,4,5，每次都不命中（颠簸现象，或抖动，乒乓现象）
  • 最近最少用LRU
    • 栈算法，命中率随着组的增大而提高
    • 每个槽加一位LRU位（计数值）。如4个槽，两位LRU，每次被访问的槽的LRU位置0，其余槽位+1；每次淘汰LRU值最大的那个

5.2 写策略（cache一致性）

  • cache里的内容是主存块的副本
  • 直写（Write Through）：
    • 直接写入内存，无一致性问题，但是慢
    • 写缓存：增加速度，并行。但是write buffer写满就会饱和，很慢、阻塞。
    • 解决buffer缓冲饱和：加一个二级cache（比buffer大）
  • 写回（Write Back）：
    • block被淘汰替换的时候，一次性写回。
    • 需要锁死内存或cache的数据（修改位 dirty bit）
    • 一定是写分配
  • 写不命中：
    • 写分配：装入cache再写（需要读取主存的block）
    • 非写分配：直接写入主存

5.3 cache实现的几个因素

  • L1 Cache的数据和指令是分开的，可以一边读数据一边取指令 ；L1的命中时间比命中率更重要，因为不命中还有L2也很快
  • L2, L3, L4是联合Cache，指令数据放一起；L2命中率更重要

6.0 虚拟存储器

6.1 分页存储管理

6.1.1 早期虚拟存储器概念

  • 早期：程序员自己管理主存；1961提出overlay，把地址空间和主存容量概念区分开。程序员在地址空间里编写程序，而程序在真正的主存中执行。自动完成映射。
  • 操作系统： 执行到某个页的程序段时，当前主存内容保存到磁盘；找到需要的区间并读入主存；改变地址映射；程序继续执行

6.1.2 分页的基本概念

  • 页表实现逻辑、物理地址的转换
  • 局部化特性时我们不需要把整个程序装入内存；每个程序只用很小一部分内存，为多程序运行提供了便利

6.2 虚拟存储器、虚拟地址空间

6.2.1 虚拟存储器

  • 使程序员可以在比实际主存空间大得多的逻辑地址空间里编写程序
  • 程序执行时，只把局部加载到主存
  • 思考：这就是为什么只有CPU、内存就可以称为计算机。原始的计算机就是这样的，在后面需要保存数据时才引入了外存
  • 理想的页表对每一页都有说明，所以每一个程序都有一个页表

6.2.2 虚拟地址空间

  • 将内核与用户空间隔离开
  • Linux虚拟地址空间
    • Kernel
    • User Stack (Dynamic)
    • Shared Libraries
    • Heap (Dynamic)
    • Read/Write Data
    • Code
  • 按需调页：仅仅建立映射，实际上不会真正从磁盘调入，需要的时候才调入

6.3 分页存储管理的实现

6.3.1 虚拟存储管理需要考虑的问题

  • 问题
    • 块大小（在虚拟存储器中“块”被称为“页／Page”）应多大？
    • 主存与辅存的空间如何分区管理？
    • 程序块存储块之间如何映像？
    • 逻辑地址和物理地址如何转换，转换速度如何提高？
    • 主存与辅存之间如何进行替换（与Cache所用策略相似）？
    • 页表如何实现，页表项中要记录哪些信息？
    • 如何加快访问页表的速度？
    • 如果要找的内容不在主存，怎么办？
    • 如何保护进程各自的存储区不被其他进程访问
  • 缺页开销大：用全相联
  • 页大小比cache的block大得多，因为访问很慢，所以一次取很多
  • 用软件处理“缺页”：缺页时访问磁盘太慢了，所以不用硬件实现

6.3.2 页表结构

  • 装入位、修改位、替换控制位、其他（访问权限）、实际页号
  • 每一个页有一项
  • 页表比页还大
  • 页表存在内核区

6.3.3 页表转换过程

  • 虚拟地址：虚拟页号 + 页内地址
  • 数组访问违例就会Segment Fault

6.3.4 快表 TLB

  • 一次存储器引用需要访问几次主存？3次；把经常要查的页表项放在Cache，就是Translation Lookaside Buffer快表
  • TLB: tag（页表哪一项） + 主存页表项
  • TLB可以直接拿到物理地址，无需访问主存（TLB目的：减少访问主存的次数）

6.4 存储器层次结构

6.4.1 存储器访问过程

  • CPU用VAdrress去TLB，hit则去Cache中取（0次访存）；miss则去页表，再去Cache；最坏情况Page Fault
  • 考研题：在Cache里hit的地址一定会在TLB和页表里

6.5 段式和段页式虚拟存储管理

  • 分段系统的实现
    • 不是等长划分，而是根据程序代码段、按程序逻辑划分（代码段、只读数据段、可读写数据段等）
    • 有段长、段表（段号、装入位、段长、起始位置、访问方式），很好判断缺段、地址出界、保护违例
    • 物理地址 = 段起始地址+段内偏移
    • 缺点：占有空间多，碎片多
  • 段页式
    • 先分段，再分页，仍以页为单位
    • 段号+页号+页内偏移量
    • 缺点：两次访问内存

6.6 存储保护

  • 目的：避免程序相互干扰，每个程序有自己的数据区
  • 模式：
    • 用户模式（目态）：用户的程序
    • 管理模式（内核态）：操作系统的程序
  • 有指令实现内核、用户的转换