晶体管计算机

晶体管

图灵机(假想机器)

• 组成部分: 一条无限长的纸带, 一个读写头, 一个状态标志, 一个规则表格

• 通用性: 如果有足够时间和内存, 可以执行任何计算; 只要有足够的规则, 状态和纸带, 可以创造任何东西, 是很强大的计算模型(图灵完备性, Turing Complete)

• 密码破译机器BOMBE → 可行性剪枝, 大幅减少搜索量, 把精力花在更可能得组合

• 图灵测试 → 如果计算机能欺骗人类相信它是人类, 才算是智能, 成为智能测试的基础

停机问题

• 能不能在不运行程序的情况下就判定程序最终会不会停止, 即出结果? (极具现实意义, 因为有些程序要跑数年才会停止)

• 图灵通过一个巧妙逻辑矛盾证明停机问题是无法解决的 → 哥德尔不完备定理

• 图灵机被证明具有图灵完备性, 而停机问题证明了不是所有问题都能用计算解决(计算机的能力有极限, 无论有多少时间和内存, 有些问题是计算机无法解决的) → 丘奇-图灵论题

二进制, 布尔逻辑和逻辑门

• 二进制数据位数多, 比较冗长, 容易出错, 与十进制间转换比较复杂.

• 十六进制由二进制的位置计数法发展而来, 占位更少, 不易出错, 方便人们手工处理二进制数位. 十六进制数以0x前缀开头, 作为标志

• 二进制与十六进制转换: 将二进制数划分为四位一组, 每组翻译为十六进制( 刚好不越界 )

• 一位八进制数相当于三位二进制数

• 只有在十进制或者已经规定编码方式的二进制下的数据才能讨论正负性, 其他进制并未规定表示正负的标识符

表示整数

表示小数

• IEEE - 754 float number calculating standard

• 单精度浮点型(Float)编码法则
• 符号位独立于其他部分的规则存在, 0正1负
• 对于最通用情形, 1 ≤ exp ≤ 254, 运算时实际指数 = exp-127, 隐藏位设为1(数足够大, 使用隐藏位提高精度)
• 对于极端情形exp = 0, 表示极小数, 此时不适合再将隐藏位设为1(范围不够小). 故隐藏位设为0, 计算实际指数时友情少减一位, 实际指数 = exp - 126
• 对于极端情形exp = 255
• fraction = 0 → ∞ , 正负取决于符号位
• fraction ≠ 0 → NaN , Not a number

• 运算法则
• 使指数相等
• 分数运算
• 结果规格化
• 丢失位舍入
• 判断指数溢出

• 小数转二进制表示: 取小 - 乘二 - 取整, 循环, 直至结果为1.0(高位先出)
• 原理: 对于二进制数, 乘二相当于算数左移1位. 而十进制的第0位为1与二进制的第0位为1等价, 于是当十进制小数乘二后小数点前第零位出现1时也说明左移后二进制数第零位为1, 推出左移前二进制小数点后第一位为1.
• 由该原理可得先得出的数位是高位

• 整数转二进制表示 → 模2 → 除2, 低位先出(与取十进制数的各位原理相同)

表示字符

表示负数

• 原码 –> 只用数字开头符号位表示正负, 其他表示绝对值的部分不变

• 反码 –> 和正整数相比每一位全部取反(与正数相加后得到的数每一位都是1)
• 原码和反码的问题:
• 正0和负0两种表达方式可能出现问题
• 需要额外处理保证运算一致性

• 补码 –> A绝对值的反码+1(绝对值取反加1)

• 正整数的原码, 反码, 补码三码合一

• 不同长度的补码整数作加法运算需要先符号扩展至相同的位数, 正数补0, 负数补1

• 补码体系中, 一个正数与一个负数相加, 结果不可能溢出
• “溢出” 指的是舍去多余进位后, 两正数相加变为负数或两负数相加变为整数, 并不是产生了多余进位就是溢出

• 二进制负数转换成其他进制: 取补码后直接转换
• 特别地, 转换为十进制可以使用算绝对值加负号的方法, 但对其他进制不适用.
• 除了二进制有符号位, 十进制有正负号此两者有专门的符号表示, 其他情况下转换为八进制和十六进制数时不讨论数字的正负(即只在规定编码方式的二进制或十进制下讨论正负).

位组合

• 为了唯一的识别出许多不同的数值(而不只是0和1), 必须对多个位进行组合, 每一种组合都是一个编码,对应着某个特定的值.

• 位组合的子单元 → 字段

• 同一数值的多种表示方法 → 进制

• 同一编码的多种解码方法 → 数据类型

• 最右边是0号, 从右往左编号

• 按位运算: 对两个位组合, 对二者每一个对应位都做特定的逻辑运算(每一位都出一个结果)
• 与0做与运算, 结果是0; 与1做与运算, 结果与原操作数相同
• 位屏蔽 / 掩码 → 原位组合与一个特定位组合 (屏蔽位设置为0, 保留位设置为1) 做与运算
• 判断两数相同 → 两数进行按位异或运算, 若结果每一位都等于0则两数相同

代数运算

• 左 / 右移
• 左移: 把所有数字向相应方向移动一位, 右补0;
• 右移: 移出右边缘的数据舍去, 左补?.
• 对二者而言, 第一个操作数是被移位的数值, 第二个操作数是移动的位数, 即num >> n
• 算数左移 / 逻辑左移 / 逻辑右移 –> 零填充不考虑符号(无论正数负数都无脑补0)
• 算数右移, 符号扩展(区分0填充和1填充, 正数右移左补0, 负数右移左补1)
• 算数右移常用于有符号补码整数, 逻辑右移常用于无符号整数.

数字逻辑电路

MOS晶体管

• 晶体管组成部分: 源极S(Source), 漏极D(Drain), 栅极G(Gate)

• N型MOS晶体管
• 源极(Source)接地, 漏极(Drain)接正极(开关属性为+, 接地属性为-)
• 栅极加3.3V电压, 晶体管相当于导线, 源极和漏极导通, 晶体管中间有电压降输出;
• 反之, 加0V电压即断开

• P型MOS晶体管
• 源极接正极, 漏极接地(开关属性为-, 接地属性为+)
• 栅极提供0V电压, 源极和漏极导通; 源极不能接地(源极只能接电源正极)
• 反之, 加3.3V电压则断开.

• 互补金属氧化物半导体电路(Complementary MOS, CMOS)
• 所有的逻辑门的基本骨架都是在竖列晶体管列之间横向链接输入输出线路.
• NMOS漏极接电源正极, PMOS漏极接地, 二者互补所以漏极可以相连. 所有的输出都产生自NMOS和PMOS相连的漏极处, 当二者一者导通一者断路时输出的电平分别等于电源正极的3.3V和接地的0V, 也即对应1和0.
• 必须一半通一半断, 才能在漏极相接处得到明确的3.3V(P型接通)或0V(N型接通)电压.
• 一半是正常翻译, 另一半是反演律(电路建立准则, 使得N型和P型管恒有且仅有一端导通)
• 即: 一半并联, 一半串联

逻辑门

非门 (NOT Gate)

与门(AND Gate)

或门(OR Gate)

• 逻辑完备性: 其他任何逻辑函数都可以写成与或非三种基本逻辑运算符的逻辑组合

异或(Exclusive OR)

同或(XNOR)

组合逻辑电路

Intro

特点

• 当前的输出与以前的输入无任何关系(没有记忆, 与之相对: 数字逻辑电路), 输出在任何时刻只取决于同一时刻的输入状态, 与电路过去的状态无关

• 输入和输出之间可以用逻辑函数来描述

• 没有记忆功能, 信息不能存储在组合逻辑电路中

• 输入输出之间没有反馈延迟通路

• 主要用于处理信息, 典型元件有译码器, 多路选择器和全加法器等

分析步骤:

• 根据给定的逻辑电路, 从输入端开始逐级推导出输出端的逻辑函数表达式

• 根据输出函数表达式列出真值表(n个输入值对应种输入排列)

• 用文字概括出电路的逻辑功能

• 表达式越简单, 并不等价于工业设计最优
• 器件数量, 种类最少, 连线最简单
• 满足速度要求, 级数尽量少, 以减小延迟
• 功耗小, 工作稳定可靠

译码器(1-of-n decoder)

• 通常n个输入, 个输出

• 将n个输入可能出现的种排列转换成个逻辑门输出形成的位代码, 任意时刻只有1个输出为1, 其余全为0(即根据输入的n位代码精准选中个输出中的一个)

多路选择器(Multiplexer)

• 可以看作是由译码器进化而来, 其中每个与门增加一条连接各自输入的线, 再将输出连接到一个统一的输出端.

• n条选择线(类似n位选择码), 可选择个输入, 1个统一输出

• 功能 → 根据选择信号S, 选择一个输入, 将其连接到一个统一的输出端口(多进一出)

• 一般由n条选择线和个输入组成, 连接到一个统一的输出端口

• n条选择线输入的种位组合恰好可以用于选择任何一个单独的输入, 输出与该输入的值一致.

加法器(Adder)

• 1+1 –> 原位变为0(XOR), 进位加一(AND); 进位到“CARRY”后原“SUM”必为0, 故要做全加器直接将第三个数加到sum中即可.

• Half adder –> add up 2 numbers

• Full adder –> add up 3 numbers

• 8位行波进位加法器 –> 处理两个八位数字二进制相加.(上一位的carry进入下一位继续相加运算, 即为两个数字的相应位与上一步进位三者相加, 需要用到全加器)

可编程逻辑阵列(Programmable Logic Array, PLA)

• 受全加器的设计模式启示, 完全可以通过与阵列和或阵列的组合来根据真值表实现任意的逻辑函数

• 其中, 与阵列中个与门对应n个输入的中情况, 每一种情况都会产生一个独特的与阵列输出; 而或阵列中个或门对应个输出. 只需要在黑箱中将与阵列的输出按照真值表的规定与或阵列的输入连接, 就可以实现该真值表规定的逻辑函数.

• PLA只包含与/或/非三种门电路, 而任意逻辑函数都可以由PLA实现 → 门集合{与, 或, 非}在逻辑上是完备的

• 可以通过布尔代数运算来简化PLA的构成.

基本存储电路

双稳态电路

• 双稳态电路: 有两个稳定状态, 在没有外来触发信号的作用下电路始终处于原来的稳定状态, 在外加输入触发信号作用下, 双稳态电路从一个稳定状态翻转到另一个稳定状态, 两种状态分别代表0和1(稳定状态的来源: 闭合回路循环)
• 双稳态电路是存储器件的基本模块
• 晶体管 - 门电路 - 锁存器 - 时序逻辑电路 - 存储器机票各种数字处理器

S - R锁存器 (S-R Latch)

• 静态存储单元当中最基本, 也是电路结构最简单的一种, 通常由两个或非门或者与非门组成

• 构建方式: 都是用其中一个门电路的输出作为另一个门电路的输入, 从而达到循环效果

• 看起来没通电, 实际上门电路源极/漏极都是有通电的!

• R –> reset S –> set
• 必须满足 即不能同时为0, 否则电路状态不可预知
• R = 1, S = 1 → 可以保持输出为0或1不变, 电路处于稳态
• 瞬间将R或S设置为0 → 设置值发生改变
• 哪条线瞬间置0, 哪条线代表的功能就生效.
• S瞬间置为0, R保持1不变 → 输出Q变为1
• R瞬间置为0, S保持1不变 → 输出Q变为0
• “设置” → 设为0或1; “清空” → 设为0

• 作用
• 缓存
• 完成高速的控制器和慢速的外设不同步问题
• 解决驱动问题
• 解决一个I/O口既能输入也能输出的问题

• 门控D锁存器 → 加上与非门限制写入权限

• 使用与非门的理由
• WE为0时需要保持S和R均为1才能使得输出不变(不能用原始与门)
• WE为1时输入D需要能产生影响(不能用或门)
• 不可以使得两个输入同时为0(其中一个与非门需要取反)

寄存器(Register)

• A group of Latches → A Register! (可以存储多位二进制数)

• 单个锁存器只能实现一位数据存储 → 将多个锁存器捆绑成一个单元即可存储多位数据 →寄存器

• 多个门控D锁存器通过同一条WE控制, 统一进行写入或输出操作, 即组成了一个捆绑单元, 存储多位数据 → 寄存器

存储器(Memory)

• 存储器由一定数量的单元组成, 每个单元具有存储一个数值的能力, 可通过唯一确定的地址被唯一识别.

• 地址空间 → 唯一可被识别的单元总数称为存储器的地址空间.

• 寻址能力 → 存储在每个存储单元中的数据位数, 大多数存储器是字节可寻址的.

存储器构造

• 允许写入线理论上需要连接到所有的锁存器, 统一控制所有的写入权限, 但是只希望改写目标锁存器 → 允许写入线与选择线共同进入与门, 只有两者同时被激活时才开启写入权限

• 选择线与锁存器的输出共同进入与门, 当选择线为0时锁的最终输出恒为0, 不会干扰其他被选择的锁存器的输出. 选择线被激活时最终输出等于锁存器中存储的值.

时序逻辑电路

• 当前输出与以前的输入有关(存储 / 记忆)

• 当前输入 + 记忆 (存储信息) → 当前输出

有限状态机

• 系统的状态 → 系统中所有相关的元素在一个瞬时的瞬态图

• 由于存储元件的容量有限, 状态的数目必须有限, 故通常使用有限状态机来描述系统的行为.

组成元素

• 有限数目的状态

• 有限数目的外部输入

• 有限数目的外部输出

• 明确定义的状态转换函数

• 明确定义的外部输出函数

• 状态的集合表示了系统中所有可能的状态, 每一个状态转换描述了什么使得一个状态转换为另一个状态.

状态图

• 一组圆和线

• 每个圆对应一个状态, 每个带箭头的连接弧线说明状态的转换方向

• 在实现有限状态机的电路中, 从一个状态向另一个状态的转换发生在每一个时钟周期的开始

• 为了控制存储器组织的异步, 需要引入主从触发器(边沿触发的D型锁存器, 与电平触发相对)

• 时钟为0时 → 锁A可写, 锁B不可写, 锁B中保持为上一状态的值, 当前状态的值被写入锁A, 为下一周期开始改变B中的值做好准备

• 时钟变为1时 → 锁B可写, 锁A不可写, 当前状态的值从A中输出被写入B, 为判定下一个状态提供内部输入.

• 设计的目的: 使得组合逻辑的输入在下一个时钟周期而非当前时钟周期输出并发挥作用, 保持当前周期的稳定工作.

寄存器和内存(短期记忆)

• 随机存取存储器( Random Access Memory, RAM )
• 思路: 先做只能存储1bit的电路, 再通过扩大做出内存模块
• RAM + ALU –> CPU !
• (存储状态)
• “门锁”
• 16, 32, 64bits 位宽, 可以用一根线控制所有允许写入线. (一串)



• 明显减少线路条数, 需要用行数列数(地址)定位门锁位置(一行一列锁定一个, 而不需要每一个gate都接一根线).(行与列坐标各用4 bits数据存储)
• 多路选择器 –> 用于处理行列坐标 ( 实际上就是一个n → 2^n译码器 + 与门 )
• 每一个Latch的WE(writing enable wire)上均连接一个与门, 与门和行, 列的多路选择器(Multiplexer)连接, 当且仅当该行该列均被选择, 即确定坐标时, 对应位置的Latch才被激活. 读取同理.



• 封装







• 由于地址线, 允许写入写入线, 允许读取线是共用的, 所以上图操作方式是对每个256位内存的同一个地址进行写入或读取操作, 8个256位内存可以存256个8位数, 每个内存同一地址的GATE分别存储一个八位数的各位.
• 所谓“一个地址”, 本质上是八个256位内存的同一相对位置, 分开来存放一个8位数据, 从而做到一个地址存放一个数据. (把地址拆开来)
• 每个内存地址可以存放8位数值 → 寻址能力为8位, 字节可寻址
• 内存的重要特性: 可以随时访问任何位置 (in a random order), 因此叫“随机存取存储器”, 简称RAM. (与之相对: 磁带等媒介需要从开头一直按顺序转到想要的位置. )



• 每个芯片平行关系不变, 每个芯片依次读取写入一个byte(8bits).
• 计算机CPU一次能并行处理 / 寄存器中能存放的二进制数字位数称为计算机的字长(或位宽).
• 值得注意的是, 内存只能与通用寄存器直接交互, 必须通过将数据加载到通用寄存器中才能将其写入内存

Von Neumann Architecture 冯·诺依曼体系计算机

• 主要思想: 把程序和数据都作为一个二进制的序列存储在计算机的存储器里, 在控制单元的引导下一次执行一条指令.(程序和数据同等存储, 控制单元一次执行一条)

• 程序和数据存储在同一位置(RAM), 在RAM中写入不同的指令即可运行不同的程序, 是为通用电子计算机(在此之前数据和程序分开存放, 要编写程序需要在硬件上改变电路, 为专用电子计算机)
• 处理器(带ALU) + 数据寄存器(通用寄存器) + 指令寄存器(IR) + 指令地址寄存器(程序计数器, PC) + 内存

• 最早期的数据输入输出内存方式: 穿孔纸卡 / 纸带 (想想答题卡)

• 早期编程方式(需要非常了解底层硬件才能编写程序)
• 插线板(直接在硬件层面更改电路)
• 穿孔纸卡纸带(本质上是原始的外存!)
• 面板编程(一大堆开关, 指示灯和按钮), 不太方便但是可行

• 我们需要更简单的编程方式

基本组件

存储器

• 地址空间 → 地址可表示的存储单元的个数(即可用地址的个数)

• 寻址能力 → 单个存储单元中数据的位数

• 总空间 = 地址空间 * 寻址能力

• 4GB → 4G = 个存储单元, Byte字节可寻址

处理单元(ALU)

• ALU → 算数逻辑单元

• 计算机中负责运算的组件, 由一个算数单元和一个逻辑单元构成.

• 用逻辑门等高级抽象构建, 而非晶体管.

• 将ALU抽象为一个“V”形元件, 除了输入输出还有逻辑门元件.

• ALU附件: 0检测器, 当八位全部为0时检测器输出“TRUE”.



OR –> 只要有一位不是0, 传入NOT的数值就为1, NOT取反输出0.

• ALU自身不能做除法, 执行除法的方式是循环做减法, 直到结果小于或等于0, 再经过一步处理得到结果.(早期ALU没有硬件层面的除法, 只能通过软件实现)

• 字长(Word Length) → ALU正常处理的信息量的大小, 每一个元素称为一个字(Word)

• 通常情况下, 计算机会在ALU附近提供少量存储空间(”寄存器堆”), 用于临时存取一些不久就会在计算后读取这个结果并继续计算, 效率远高于从存储器中存取数据.

控制单元

• 指挥信息的处理, 协调系统各个部分的运行

• 主要功能 → 在执行程序的过程中跟踪存储器中的指令(跟踪下一条指令, 使用程序计数器/指令指针PC), 在处理指令的过程中跟踪指令的处理

输入/输出设备

• 属于外围设备(外设), 用于辅助处理.

数据通路

• 数据通路: 计算机内部用于处理信息的所有元件总和

• DLX数据通路采用总线结构, 多时钟周期实现方案

精简版

注解

总线

三态设备(三角形元件)

指令结构

• IR[31:26] → 操作码, 进入有限状态机判定指令类型

• IR[25:21] → 源寄存器, 作为SR1的代码用于取寄存器

• IR[20:16] → 源寄存器或目标寄存器, 作为SR2或DR的代码用于取寄存器, 需要用多路选择器来决定是SR2还是DR

• IR[15:10] → R型指令的DR代码

存储器

• 程序指针PC → 存储下一条指令所在地址的寄存器

• 地址寄存器MAR存放要访问的存储单元的地址, 数据寄存器MDR存放取出的数据, 访问存储单元必须经过二者

• 注意, MAR中只包含一个存储单元的地址, 即一个8位数据的地址, 而MDR有32位. 加载到MDR中的数据可能是以MAR中指向的单元为首的连续四个存储单元, 也可能是MAR指向单元的符号扩展结果.
• 读取存储器需要多个时钟周期, 读取时就绪信号R设为0, 读取结束时R设为1

有限状态机

• 实心箭头为运输的数据, 空心箭头为数据运输的控制信号

• 有限状态机的其中一个输入是时钟信号CLK, 指定每一个时钟周期持续的时间

• 有限状态机的所有输出都是空心箭头, 起控制作用, 是控制单元的核心.

其他结构

• DRMUX → 选择该输入是作为DR还是SR2输入

• AMUX和BMUX选择ALU输入的来源, 因为除了寄存器还有特殊来源如符号扩展和PC和4等.

• SEXT → 完成符号扩展工作, EXT.S控制扩展的模式

• LD实际上表示写使能线, GATE控制数据在合适的时机进入总线运输

• ALUout → 暂时存储ALU的计算结果

• ALUOp → 设定ALU的运算模式(加减乘除逻辑)

• MEM.EN.R.W → 设置存储器的读写权限, 规定访问模式

• LD.X → 加载使能, 使得信息允许加载时为1, 不允许加载时为0

• Gate.X → 使数据与总线相连

处理器(Processor)

中央处理单元(Central Processing Unit, CPU)

• 指令: 计算机程序中规定的可执行的最小工作单位

• 负责执行程序 –> 数学指令 / 内存指令

• 抽象(abstraction): 用一条线连接两个组件时, 这条线代表所有必须线路的一个抽象, 这种高层次视角叫做微体系架构.

• 不只是数据, 程序也可以使用二进制代码存储在RAM和寄存器中( 给CPU支持的所有指令分配一个ID, 用代码代表指令, 类似ASCII码的思路 )
• A possible version: 前四位存操作代码(简称操作码, 规定指令执行的内容) , 后四位代表数据来源, 可以是寄存器或者内存的地址, 可以操作二者中储存的数据.

• 需要额外的两个寄存器:
• 指令地址寄存器(程序计数器, Program Counter, PC): 追踪程序运行到哪里了(存当前指令的内存地址)
• 修改PC就是修改程序的控制流
• 指令寄存器: 存储当前指令

实例: DLX的有限状态机

• 取指令 → 译码 / 取寄存器 → 执行 / 有效地址 / 完成分支 → 访问内存 → 存储结果

取指令阶段

• PC中的指令地址被加载到MAR中, 同时PC的值在ALU中完成自增, 被重新写回PC中

• 通过解引用MAR中的指令地址, 取到指令即RAM[MAR], 将其加载到MDR中, 再从MDR加载到IR中, 完成取指令.
• 注意所有的数据进出RAM都离不开MAR和MDR两个寄存器, 因为需要查找和加载, 只有两个统一的出口

译码阶段 / 取寄存器阶段

• 顾名思义, 该阶段的主要任务就是转译操作码和识别指令中指示的寄存器

• 译码 → 将指令的[31:26]位(Opcode)输入一个6-64译码器, 译码器对应该操作码的输出线就为1, 在根据译码器输出为1的线确定余下26位用法

• IR[25:21]指示R1, IR[20:16]指示R2, IR[15:11]指示R3或为立即数的一部分

• 同时可以在ALU中完成PC(+4)+SEXT(IR[15:0])的运算, 如果后续涉及跳转指令(J指令)就会用到改结果. (与其他任务并行处理, 不做白不做)

处理指令: 执行/有效地址/完成分支

• 具体执行流程由指令本身特性决定.

处理指令: 访问内存

• 获取内存中的数据

处理指令: 存储结果

• 指令执行的结果被写到指定的目标中

时钟和时钟频率

• 电脑中由时钟负责管理CPU的节奏, 时钟以精确的间隔触发电信号, 控制单元使用该信号推进CPU的内部操作, 确保一切按步骤进行, 类似于节拍器. 电信号传播也需要时间, CPU“取指令→解码→执行”的速度叫做“时钟速度”[Clock Speed], 单位是赫兹Hz

• 一个时钟周期是指电压上升到3.3V再回到0V

• 单位时间内能够执行的操作数量取决于时钟周期(时钟触发至少一次, 进行一次操作)

• 现代计算机会按需调整时钟频率以合理利用资源

编程语言

• 硬件层面编程特别麻烦 → 需要一种更通用的编程方式

机器层面 → 二进制指令编码(Machine Language / Code)

• 先在纸上用英文写伪代码(对程序的高层次描述), 再逐层丰富细节, 利用操作码表把程序从伪代码翻译为二进制机器码

• 其他语言被翻译为机器语言的依据 → 该计算机的ISA

汇编语言(Assembly Language)

• 用简明易记的英文标识符 / 关键字 / 十进制数据编写程序

• 0010 1110 → LOAD_A 14

• 利用二进制程序帮忙将汇编语言翻译成对应的二进制机器码 → 汇编器(Assembler)

• 一旦程序的前部发生修改, 后续所有的地址都有可能改变 → 汇编器不适用固定跳转地址, 而是在指令前插入可跳转的标签, 程序被传入汇编器时汇编器会自己搞定跳转地址, 程序员不用管不必要的底层细节, 专心于更复杂的工作.

• 汇编语言从实质上来说虽然向自然语言跨出了第一步, 但实质上只是修饰了一下机器码(汇编指令与机器指令一般仍然一一对应), 故汇编码与底层硬件的链接依然很紧密, 迫使程序员思考用什么寄存器和内存地址.这也导致如果突然需要一个额外的数, 可能需要修改很多代码, 使得程序不易维护.

高级语言(High-level Programming Language)

• 一行高级编程语言可能会转化成数十条二进制指令, 使得编程更简单的

• 为了做到这种复杂转换, Hopper在1952年创造了第一个编译器(Complier), 将高级语言翻译为汇编指令, 再由汇编器将汇编指令翻译为机器指令

• 声明内存区域的特定抽象名称 → 变量

• 实际使用时, 变量可能存入寄存器Rn中, 但是程序员不需要关心这部分细节.

• 所有编译器都含有某几种语言的编译器 → 一次编写, 到处运行, 不必接触汇编码和机器码, 降低使用门槛, 使得计算机从专业学科变成大众工具

• 高级语言独立于ISA, 类似于自然语言, 对所有计算机均通用; 低级语言则是特定计算机上的语言, ISA不同的计算机具有不同的低级语言(即指令集). 故一个用高级语言编写的程序在执行之前,必须先被翻译成适合于预期执行的计算机的ISA的程序. 这个过程称为编译.

指令集结构(Instruction Set Architectures, ISA)

• 指令集结构包括: 存储器的组织, 寄存器集, 指令集(包括操作码, 数据类型和寻址模式)
• DLX的存储顺序为大端优先, 字的高位字节存放在内存的低地址端, 低位字节存在高地址端, 这样按顺序加载就可以得到字段正确排列的一个字.
• DLX只支持基址+偏移量的寻址模式
• DLX中特殊寄存器

• 指令集结构指明在一台机器上编写软件时所要注意的全部信息, 是软件指令和执行命令的硬件之间的接口. 利用指令集结构的定义才能将高于机器语言的其他编程语言翻译成机器语言.

• CISC / RISC ( Complex / Reduced Instruction Set Computer) 复杂指令集 / 精简指令集计算机, 前者便于开发但执行效率低, 后者执行效率高但不易开发

• 拓展可执行指令的两种方案
• 指令长度(Instruction Length) → 用更多位的数字来代表指令
• 可变指令长度(Variable Length Instructions) → 指令可以是任意长度, 看具体指令需要的位数

Example: DLX (Deluxe, created by Stanford University)计算机的指令集

注解

• 后缀加I → 立即数型指令(I型); 不加I一般默认为寄存器型指令(R型)

• I型指令一般设计:

• R型指令一般设计:
• 注意, 机器码中一般Reg.Src在前而Reg.Dst在后, 而汇编指令中一般相反

• 特例: LHI指令 32 =

指令示例

• LHI → Load High 加载高位立即数, 表示将立即数左移16位 (后补0) 后加载到目标操作数中(大端存储 / 高位优先, 先将32位数的高位载入寄存器的高位, 再将低位直接加入寄存器), 属于算数 / 逻辑运算指令一类
• 二进制左移16位, 十六进制左移4位
• 注意机器指令格式, 先空出5位未用, 再是’

• SLL / SRL → Shift Left / Right Logical 逻辑左移右移

• SLA / SRA → Shift Left / Right Arithmetic 算数左移右移
• 注意, 逻辑右移是补0扩展, 右移几位就左补几个0; 算数右移需要考虑符号位, 符号位为1则补1, 为0则补0

• SLTI → Set Less Than 设置是否小于等于条件, 当指令[25:21]表示的寄存器中的值小于等于[15: 0]符号扩展表示的立即数时, 将[20:16]表示的寄存器设置为1

• SEQI → Set Equal 相等时将目标寄存器设为1

• LW / SW → Load / Store Word (32bits)
• 高级语言中同一个变量名分别作为左值和右值出现在赋值表达式两侧时的含义是不同的: 在赋值运算符的右边, 它指的是存储在那个单元中的值; 在左边, 它则指明要进行修改的单元. 处理高级语言的赋值语句时, 对语句左侧指定的存储单元, 编译器会自动生成 一条SW指令. 右侧的计算结果先储存在寄存器中后被SW指令写入内存中.

• LB / SB → Load / Store Byte (8bits)

• BEQZ → Branch if Equal to Zero
• 因为已经硬性规定R0寄存器中只能存放0值, 故当BEQZ待检查寄存器为00000时, 则为无条件跳转指令

• BNEZ → Branch if Not Equal to Zero
• 以上两个指令的统一格式: [31 :26]操作码, [25:21]待检查寄存器编号, [20:16]unused, [15:0]16位立即数
• 取指令阶段, Imm16符号扩展的结果与PC相加, 若检查寄存器的结果符合分支指令则两者相加的结果被写入PC+4, 完成跳转
• 必须注意, 是向已经完成自增的PC中追加, 需要注意跳转量的具体值, 容易出错.

• J → Jump 跳转(只有26位立即数, 跳转有空间限制, 跳转距离过大()则需多次跳转或干脆使用JR指令)

• JR → Jump Register 用寄存器内32bits数据加载PC完成跳转, 无空间限制

• JAL → Jump And Link , 跳转的同时把跳转前指令的下一条指令的地址放入寄存器中, 以便实现函数调用后回到main函数(用于调用子例程, 调用-返回机制)

• TRAP → 自陷子例程, 程序自身暂停, 调用系统服务完成任务(如in & out)
1. 加载PC为系统服务的首地址
2. 将R31设置为修改前的PC(已经+4, 为TRAP指令的下一条指令的地址), 以便在TRAP指令结束时将控制权交还给用户程序

• SUB → Subtract, 做减法运算

• R型(Register), I型(immediate Number), J型(Jump)指令, 均用32位指令通过不同的编码解码方式构建.

• 实例: 条件分支指令(I型, 立即数型, 归属于控制指令)

• 指令的有效部分从两头出发向中间靠, 故中间部分可能留下未用部分; 相对地, 当位数不够用时, 则需要借助特殊的编码方式(例如若要声明一个32位的地址, 则需借助基址+偏移量模式)

实例: DLX汇编语言

指令

基本格式

• (LABEL:) OPCODE OPERANDS (;COMMENTS)

注解

• 其中LABEL标记, 即为指针, 代表某一存储单元的地址, 可以指向数据也可以指向指令. 标记是分支指令或跳转指令的操作数.除非需要在后面的程序中引用, 否则不需要设置标记.

• 标记在后文中出现时等价于被标记对象的地址

• 标记以字母/下划线/$开头, 由字母/数字/下划线组成, 以冒号结束; 指令操作码不可以作为标记名.

• 标记的作用: 分支指令及J指令的目标 / 包含一个准备加载或存储的数据或地址

• COMMENTS是给人看的不是给机器看的, 汇编时会自动删除注释

• 注释和标记都是可选项, 其他二者必须要有

算数逻辑运算指令

• 处理整数

• I类型(立即数型) → OPCODE DR, SR1, Imm16
• 16位立即数可以使用标记来替代
• 使用标记替代立即数有风险(容易设错!), 因为标记地址可能无法使用16位立即数表示. 此时(在汇编时)需要拆分为几步(先设置高位再加上低位). 实例:

• R类型(寄存器型) → OPCODE DR, SR1, SR2
• 注意, DR一般在前, 与机器语言指令相反

• LHI指令(特例) → LHI DR Imm16
• 功能 → 将立即数的高16位赋值给R1
• 立即数可以使用标记替代

数据传送指令

• 在存储器和寄存器, 寄存器和I/O设备之间传送数据

• 加载指令 → LW / LB DR, Imm16(SR1)

• 存储指令 → SW / SB Imm16(SR1), DR(此处DR实际上是SR)

• Imm16可以使用标记代替

• SR1存储基址, Imm16为16位偏移量
• 当SR1为R0或Imm16为0时, Imm16或SR1中的就是绝对地址.

• 注意二者的DR和有效地址相反, 目的地放在前!

• 对于数据传送指令, 机器强制要求字的边界对齐, 由基址+偏移量得到的有效地址必须是4的倍数, 才能以其作为起始地址!(设错)
• 4的倍数地址的特点: 二进制下最低位以00结尾

控制指令

• 改变指令流(即指令的执行顺序)

• 条件分支指令 → OPCODE SR1, LABEL

• J指令 → OPCODE LABEL (注意LABEL指向的数据是否超过J指令中立即数的最大值, 超过则无法一步完成跳转, 常设错)
• J指令立即数有26位而条件分支指令立即数只有16位, J指令跳转范围更大.

• JR指令 → OPCODE SR1 (提供完整32位地址, 可无限制跳转)

• TRAP指令 → TRAP Vector → 根据存储在0x00~0xFF的TRAP向量表找到目标TRAP例程的起始地址, 进入TRAP例程的调用

伪操作

• 类似于预处理指令, 提前规定部分参数. 所有的伪操作都以’.’开头

• .data address → 规定内存中数据区的起始地址(存放数据)

• .text address → 规定内存中代码区的起始地址(存放指令)
• text和data在链接过程中一般会被链接器重新组织, 故存在链接行为时其实没有必要人为规定text和data.

• .align n → 表示在这条伪操作之后被加载的地址末尾有n个0, 强行对齐字段(必须是4的倍数). 不对齐则空出一些单元, 直到与最近的4倍数地址单元对齐

• .word word1, word2, … → 表示将字1, 字2, …存储到数据区连续的内存单元中(”字组”)

• .space size → 表示在数据区中留出size个字节的连续的存储单元(等价于temp变量, 用于为尚未求出的数据分配空间), 需要用标记指示, 否则无法找到并使用

• .ascii “string1”, “string2”, … → 表示将字符串1, 字符串2, …存储到数据区的连续内存单元(”字符串数组”)

• .asciiz “string1”, “string2”, … → 在字符串末尾存储空字符’\0’

• .global LABEL → 当一个汇编程序由多个文件组成时, 规定某一标记为全局作用域, 即对每个文件均可见. 程序默认先执行标记为main并且为全局标记的指令
• 惯用法: .global main

数据

• “#” → 十进制

• “x” → 十六进制

• “b” → 二进制

程序编写约定

• 程序的第一行必须为.data address

• 程序必须具有.global main, 并从main开始执行

• 子例程的主体部分夹在寄存器的保存和恢复之间; 所有的子例程除了中断均由RET(JR R31)完成.

• 多层嵌套需要通过栈来实现.

汇编

• 汇编过程由两趟对汇编码字符串的遍历组成

第一趟遍历

• 构建符号表, 明确每个符号代表的地址, 才能在程序中遇见符号时完成对符号的解析(类似于编写TRAP向量表的过程, 体现子例程与TRAP例程的相通性)
• 遍历程序, 同时使用地址计数器LC(Location Counter)跟踪地址, 遇见标记就在符号表中做相关记录, 将LC中的内容作为它的地址, 直到文件结束.
• 当遍历到.data或.text时, LC的值会做瞬间跳转; LC每次增加量取决于遍历对象的大小.

第二趟遍历

• 生成机器语言程序(期间需要参考第一趟遍历构建的符号表)

• 依旧使用LC跟踪遍历程序

• 需要注意标记替代立即数的风险!

• 对于条件分支指令, 由于必须使用16位立即数来表示跳转量, 故若用标记替代立即数, 则标记所代表的地址必须不大于, 不小于, 否则会发生汇编错误!(设错)
• 对于其他含有立即数的指令, 可能通过LHI+ADDI实现立即数的加载, 把一条汇编指令分解为多条机器语言指令实现.
• 此时添加指令, 会影响后续符号的地址. 故第二趟遍历时还需对符号表进行微调.

链接

• 多个目标文件 (汇编语言翻译成的机器码, 高级语言编译成的机器码, 系统库程序等) 经过链接器链接, 最终形成可执行映像

• 链接器的主要工作: 为多个目标文件重新分配合理且不重叠的内存区域, 并将其整合为一个可执行映像
• 正因此, 在需要链接多个文件时, 对.data和.text的规定是非必须的, 因为会被链接器重新分配

• 全局标记相关
• .global 伪操作可使标记对全部的目标程序可见, 从而允许目标程序在分别汇编时允许包含全局标记的部分暂不进行汇编, 直到链接时最终完成汇编

全局数据区与运行时栈

• 全局数据区: 用于存储全部静态存储类变量

• 运行时栈: 用于存储全部自动存储类变量

• 栈分配内存实例

• 全局数据区存储静态生存期的变量; 运行时栈存储自动生存期的变量(本地变量 / 局部变量)

• 堆从低内存区域向高内存区域增长, 运行时栈从高内存区域向低内存区域增长(即栈顶地址从高向低增长, 将内存限制在固定范围内, 可以防止内存溢出到系统空间, 保证安全)

• DLX使用R28作为全局指针, 包含全局数据区的起始地址

• 栈指针R29指向栈顶, 帧指针R30指向当前栈帧的基址

• 使用基址+偏移量来访问全局数据区或栈帧内的变量. 其中栈指针和帧指针均可以作为基址

• 代码区存放程序本身(PC, Program Counter, 眼不眼熟?)

• 系统空间中存放TRAP向量表或系统例程等(如I/O例程), 一般位于低内存区域, 故低内存区域一般不可写(Read-only)

汇编语言调试

惯用法

顺序结构

• 一个指令流走到底, 无选择和循环结构
• 复制寄存器 → ADDI DR, SR, #0

选择结构

• 首先利用一组指令序列生成条件, 将某个寄存器设置为0或非0

• 再由条件分支指令测试该条件, 决定是否跳转

• 条件分支指令 → 子任务1 → J指令(无条件跳转) → 子任务2
• 条件分支指令的立即数应为[子任务1指令数+1(J指令占空间)]*4, 从而跳转到子任务2的第一条指令
• J指令的立即数应为子任务2的指令数目*4, 从而完全跳过执行指令2
• 乘4是因为一个32位指令需要4个8b存储单元存储

循环结构

• 首先利用一组指令序列生成条件, 将某个寄存器设置为0或非0

• 再由条件分支指令测试该条件, 决定是否跳转

• 条件为真时继续顺序执行, 条件为假时直接跳转到循环体之后的第一条指令

• 循环体的结尾处使用J指令, 无条件跳转回到生成测试条件的指令处, 立即数为 -[循环体指令数+1(J指令)]*4
• 可以指向生成条件指令也可指向条件分支指令

其他

• 输入数字字符时, 保存的是其ASCII码, 必须先转换成整数值再计算. 参考公式 → 整数值 = ASCII - 0x30

• 编写子例程时若涉及其他例程的调用, 应当先保存R31以免被子例程覆写而丢失本例程的返回地址.(设错)

• 子例程占用寄存器时需要保存并恢复

• TRAP例程和子例程使用R31保存PC+4, 使用RET返回, 中断(涉及权限改变)则需要使用EPC保存PC, 用RFE指令返回

I/O 输入输出

I/O设备(以键盘和显示器为例)

基本结构

• 数据寄存器(Data Register, DR) → 存储输入 / 输出的数据, 形式为ASCII编码, 占8bits
• 只需要使用DR[7:0]来(临时)存储一个ASCII编码, 剩余24位均为0

• 状态寄存器(Status Register, SR) → 标志输入 / 输出设备的状态(ready / busy)
• 使用SR[0]来存储一个就绪位, 其他位不一定为0
• 对键盘来说, 就绪位为0表示未输入即就绪, 1表示键盘输入正在处理, 无法进行下一次输入; 对显示器来说, 0表示正在显示即正忙, 1表示显示器空闲可用. 二者正好相互对照. 共同点是就绪位为1时需要服务.
• 输入时KBDR[0]被设为1, DDR[0]被清空.

• DR和SR本身不需要32位, 但是为了与主机结构统一, 仍然采用32位的寄存器.

惯用法

交互方式

• 方法一: 使用专门的 I/O 指令 → CISC计算机的特性, 专门使用一个指令来处理I/O例程

• 方法二: 内存映射的I/O → 从存储器中划出一定数量的地址, 用于表示设备寄存器, 不再表示原来的存储单元. 使用用于在通用寄存器和存储器之间传送数据的数据传送指令.

I/O过程

异步问题

• 处理器处理指令由时钟周期控制, 而用户输入输出一般是随机行为, 与规律的时钟周期不同步 → 异步

实现方式 → 引入设备状态寄存器

• 轮询 → 由处理器控制(最简单方式)
• 处理器不断按照时钟周期检查设备状态寄存器的就绪位, 根据就绪位的值(0 / 1)来判断是否需要进行输入或输出操作(可以由条件分支指令实现)
• 时刻占用处理器资源, 比较低效.

• 中断例程 → 由输入 / 输出设备控制
• 让处理器始终进行自己的任务, 直到被输入 / 输出行为产生的信号打断. “已经输入了一个新字符, 其ASCII码位于输入设备寄存器里, 你需要读取它”

实现轮询

数据通路

• 内存映射尚停留在理论阶段, 需要增加逻辑单元来实现内存映射 → 地址控制逻辑, 选择真实内存或映射内存作为MDR的输入或输出对象

• MAR一方面连接到存储器, 通过译码访问指定的实际存储单元, 另一方面输入地址控制逻辑来访问内存映射的设备

• 地址控制逻辑一方面输出选择码控制INMUX的选择, 一方面决定MAR指定设备寄存器的允许加载信号以及存储器是否可写

• INMUX(Input Multiplexer)依据地址控制逻辑的输出选择来自KBSR/KBDR/DSR/DDR的输入, 连接到存储器

TRAP指令

操作系统

• 具有一定特权级别

• 以I/O为例, 许多用户程序共享同一个输入输出流, 允许用户任意访问输入输出流的硬件寄存器可能不是明智之选(包括C语言也只能使用官方封装好的特权函数来进行输入输出)

• 所以硬件寄存器被设置了一定级别的特权, 没有权限的用户程序是无法访问的

• 操作系统具有恰当的特权级别, 故把I/O例程封装进操作系统, 既方便又安全.

TRAP机制

服务例程

• 服务例程是操作系统的一部分, 是系统代表用户程序去执行的一组程序. DLX总共可以识别256个服务例程.

TRAP向量表

• 一张包含256个服务例程的起始地址的表, 每个起始地址需要占用4个连续存储单元(32bits), 则256个起始地址需要256*4个单元来存储.

• 因此TRAP向量表存储在x0000 0000 ~ x0000 03FF中, 又称系统控制块, 为只读区域

• 每个服务例程都包括数据区和代码区, 而TRAP向量表给出的实际上是代码区的首地址. 在此可以规定每个服务例程的数据区的起始地址均为其代码区起始地址之前x100个单元的位置.

• 每个服务例程所占空间为数据区空间+代码区空间

TRAP指令

• 特点:
• 调用系统例程, 服务于用户程序(使用系统封装好的服务以及操作系统特有的一些特权, 如访问I/O)
• 先调用系统服务(重载PC)再返回原用户程序(所以在跳出原用户程序时需要使用一个寄存器保存原PC的值)

• 一方面根据TRAP向量改编PC的值为相应的服务例程的首地址, 一方面提供一个返回调用者程序的路径, 即”链接”

• 格式: TRAP <Vector>

• 执行阶段的工作
• 将26位的TRAP向量符号扩展到32位, 再左移2位(即乘4)形成一个新地址, 该地址被加载到MAR, 作为相应TRAP指令在TRAP向量表中的地址
• 依据MAR寻址, 取出的值为TRAP例程的首地址, 被加载入MDR中
• 通用寄存器R31被加载为PC中当前内容, 提供一个返回路径(调用TRAP例程后原R31被破坏, 需要保存)
• MDR被载入PC中, 完成TRAP指令跳转
• 执行之后将R31重新写入PC中, 完成返回(若R31未被改变, 则TRAP指令一般以JR R31结束, 否则需要出栈还原R31)
• JR R31助记符RET(与RFE区分)

TRAP例程

• 普通例程改造成为TRAP例程的关键点
• 使用伪操作.text为该TRAP例程规定明确的代码区起始地址, 与TRAP向量表中的记录相符合.
• 使用JR R31或RET结束TRAP指令, 而非J NEXT_TASK
• 注意接口, 如TRAP x07的参数规定储存在R4中

寄存器的保存和恢复

• 在被调用例程进行时, 注意存原PC的寄存器是否会被修改, 如果会被修改则需要声明一个存储单元来保存该PC.

保存的分类

• 调用者保存(caller-save) → 在调用例程的程序中, 调用前保存, 调用后还原

• 调用者保存(callee-save) → 在被调用的程序开头保存, 结尾还原

• 原则: 哪个程序知道哪些寄存器将被接下来的操作破坏, 处理保存 / 恢复问题的就应该是哪一个程序

TRAP指令实例

HALT 停机服务例程 (TRAP x00)

• 运行锁又叫MCR(机器控制寄存器), 与石英振荡器的信号一起进入一个与门后作为时钟信号输入有限状态机, 当MCR[0]为0时等效于时钟停止, 机器停止运行

• MCR既然是一个寄存器(属于存储器组织), 自然也需要分配一个地址. 此处同样使用内存映射地址的策略(映射到xFFFF 00F8).

• 例程分析

• Question: 既然时钟周期已经停止, 那将MCR[0]加载为0之后的指令流有什么意义?
• 至此已经停机, 如果未重置, 以下指令不会被执行

• HALT例程使用了R1, R2, R4, R31, 且停机时数据均被破坏.

中断驱动的I/O

本质

• 让外设打断处理器的运行进程, 而不是让处理器不断去询问外设, 减少浪费资源

上层特性

• 需要处理I/O设备输入时
• 强制程序停止
• 让处理器执行I/O设备的请求
• 让停止的程序继续执行, 好像什么都没发生过

底层机制

• I/O设备有输入要处理或准备接受输出时, 允许I/O设备中断处理器的机制

• 管理I/O数据传送的机制

以上两种机制的实现

• I/O控制器生成中断信号INT(Interrupt)打断处理器进程

• 处理器 → 停止当前的执行过程, 处理由该信号发出的请求

原因寄存器 CAUSE

• 如果某个设备发出IRQ(Interrupt Request)信号, 就会将原因寄存器(CAUSE)的相应位设为1

• 记录哪些设备发出中断信号

• 特殊寄存器, 只有在特权模式(操作系统)下才能访问

• CAUSE[15:8]为中央未决位, 不为0则表示有需要处理的中断, 等待裁决

• CAUSE[15:10]代表6个来自硬件的未决中断, CAUSE[9:8]代表2个来自软件的未决中断

状态寄存器 SR

• 所有设备的IE位的信号可以被状态寄存器 SR[0] 同时改写

• 特殊寄存器, 只有在特权模式(操作系统)下才能访问

• SR[0]表示中断允许位, 决定了谁能中断处理器
• 如果SR[0]为0, 那么所有I/O设备都不能中断处理器, 只能采用轮询方式访问I/O设备
• 如果SR[0]为1, 那么允许所有I/O设备中断

• SR[1]表示正在运行的程序时处于特权模式(sudo)还是非特权(user)模式
• 如果SR[1]为0, 则为特权模式
• 如果SR[1]为1, 则为非特权模式
• 0特权用户; 1普通用户(容易记反)
• 只有在特权模式下, 才可以访问对用户程序不可见的重要资源, 如CAUSE.

• SR[15:8]为中断屏蔽位, 给出中断阻塞方案, 决定系统响应哪些中断, 以及不同I/O设备的中断优先级, 位置越高优先级越高. SR[15:8]是裁决CAUSE[15:8]的依据.
• 显示器优先级为0, 键盘优先级为1

• 裁决标程

• 专门按位与取出CAUSE[15:8]与SR[15:8]进行裁决(同0xFF00按位与, 实际上是位屏蔽, 屏蔽了其他无用位)

• 通过逐位逻辑左移和比较R3与0的大小(补码机制, 测符号位)间接测试哪一级别有待处理中断

• 使用R7存储裁决下一级别中断的指令流, 以便在服务完上一级别后立即开始测试下一级别.

• 完整的中断服务例程: 保存寄存器 → 按优先级依次检查并服务允许中断 → 恢复寄存器 → 完成服务, 清空CAUSE → RFE

中断信号的产生与传送

• 数据通路示意:
• I/O设备经过就绪位与中断允许位逻辑与 → 产生IRQ → IRQ一方面通过或门从一个统一出口产生INT, 另一方面输入原因寄存器CAUSE[15:8]记录产生I/O行为的设备 → CAUSE[15:8]与SR[15:8]按位与, 裁决有效I/O请求 → 中断请求生效或被驳回

• 中断信号INT的产生 → 必须满足两个元素
• I/O设备需要服务
• KBSR或DSR的就绪位[0]必须要为1, 表示需要服务(通性)
• 设备必须有请求服务的权限(系统可能有更重要的进程在执行)
• 中断允许位IE必须为1
• 大多数I/O设备中, 中断允许位(Interrupt Enable, IE)是设备状态寄存器的一部分
• 可以被设置为1 / 0, 取决于是否给I/O设备权限去请求服务
• 所以KBSR和DSR除了就绪位并不是每一位都是0, 与之相对KBDR和DDR除了XXDR[7:0], 其他位均为0

• 中断信号(INT)
• 对于KBSR和DSR, IE位是[1]位
• 中断请求信号IRQ(Interrupt Request) → IE位和就绪位的逻辑与运算结果, 翻译就是两个条件的同时满足
• 各中断设备发出的IRQ信号进过或门, 产生INT信号打断处理器进程(只要有一个IRQ要处理就要产生INT)

测试中断信号 → 增加逻辑

• 原DLX有限状态机的状态图无法完全处理中断例程, 没有规范的步骤检查INT信号

• 将总是”存储结果→返回到取指令”的最后一步更改为存储结果并检测INT信号
• 若INT信号为0则与往常一样返回到取指令阶段
• 若INT信号为1则需要保存及改变程序状态, 控制单元将PC加载为x8000 1000, 执行操作系统的中断服务例程, 处理由该信号发出的中断请求

保存及改变程序状态(特殊)

• 程序状态: 程序影响的所有资源所包含内容的瞬态图, 包括作为程序一部分的所有存储单元和所有通用寄存器的内容. 特别地, 还包括两个重要寄存器 → PC和SR

• 保存PC(记录当前用户程序的指令地址) → 使用专门的寄存器EPC来保存

• 保存SR(记录原用户程序的有无特权, 以及当前是否具有I/O权限): SR[2]←SR[0]; SR[3]←SR[1] (仅限没有嵌套中断时, 否则仍会丢失原SR. 实现嵌套中断需要依赖运行时栈机制.)

中断优先级

• 优先级由SR[15:8](中断屏蔽位)决定, 通过设置SR[15:8]可以控制CAUSE[15:8]与SR[15:8]的按位与结果, 从而改变INT的裁决结果

• 于是可以说SR[15:8]给出了中断阻塞方案, 以决定系统响应哪些中断

• CAUSE[15:8]中的未决中断需要等到相应的中断屏蔽位被设为1之后才能引起处理器的处理

• 如果有多于1个的允许中断发生, 需要优先进行优先级高的中断(寄存器中位置高的优先级高)
• 按照优先级从高到低的顺序裁决中断未决位, 服务完高优先级的例程后再裁决或服务低优先级的例程

• 为了读取特殊寄存器中的值, DLX的数据传送指令中还包括两个在整数寄存器和特殊寄存器之间进行数据传送的指令: MOVI2S(Move integer to special)和MOVS2I(Move special to integer)

• SR的GPR编号为x0C, CAUSE为x0D, EPC为x0E

中断嵌套

• 在低优先级中断过程中出现更高优先级的中断请求, 则会中断低优先级中断例程, 转而处理高优先级中断例程. 高优先级例程处理完毕后再继续低优先级中断

• 一般来讲, 在处理高优先级中断时, 往往会屏蔽部分或全部低优先级中断.

• 根据是否允许中断嵌套, 可以将中断处理分为两种类型 → 串行处理和嵌套处理.
• 串行处理 → 运行一个中断处理例程时, 禁止再响应新的中断(SR[0] = 0), 新的中断只能等待正在运行的中断执行完毕才能获得响应
• 嵌套处理 → 运行中断处理例程时仍可响应中断, 此时需要预先规定优先级.
• 需要保存SR和EPC的值, 因为会被嵌套中断改写
• 修改SR[15:8], 屏蔽比该设备优先级低的其他设备的中断
• 需要将SR[0]改成1以允许当前中断例程被打断
• 结束当前中断例程时需要将SR[0]改为0(接下来恢复SR和EPC的过程不能被中断), 再恢复SR和EPC的值
• 需要用运行时栈来保存寄存器.

从中断返回

• 首先清空CAUSE寄存器, 表明处理完所有的中断(此时所有中断未决位均为0)

• 然后使用RFE指令, 做两件事:
• 将PC恢复为EPC中的值, 即假设程序没有被中断的下一条执行的指令的地址
• 将SR[0]恢复为SR[2]中的值, 将SR[1]恢复为SR[3]中的值, 或执行运行时栈出栈

输入输出流(stream)

• 流的抽象存在的意义: 允许将生产者和消费者分开, 生产者向流中添加数据, 消费者从流中读取数据, 这也不必等谁, 可以以各自的速率处理任务, 有利于异步的实现.
• 使低速的输入输出设备和高速的 CPU 能够协调工作, 避免低速的输入输出设备占用 CPU , 解放出 CPU , 使其能够高效率工作

• 输入和输出均从流的开头读取至流的末尾

• 在大多数的操作系统中, I/O流是被缓冲的, 每个键盘上的输入都被底层的操作系统软件捕获, 并被保存在一个小的数组缓冲区(Buffer)里, 直至用户按下回车键, 缓冲区才被释放到输入 / 输出流里
• 使用缓冲的原因: 按回车键将允许用户确认其输入, 可以在输入进入程序之前编辑输入的内容, 以改正输入中可能存在的错误.

子例程

库(Library)

• 库: 由某个独立的软件供应商提供的程序片段的集合
• 例如: 数学库提供平方根, 正弦等, 用户程序员需要知道的是实现平方根功能的库例程的目标地址, 在哪里(哪个寄存器)输入数值x, 在哪里(哪个寄存器)得到结果

• 接口 → 调用方式; 实现 → 实际代码

子例程运行机制

调用/返回机制

• 使用调用/返回机制, 与TRAP和中断十分类似, 主要考虑两个问题:
• 跳转向目标例程的位置(调用)
• 返回原用户程序(返回)

指令支持

• JAL指令 → Jump and Link, 保存当前PC+4, 计算要跳转的地址后与已经+4的PC相加完成跳转

• 做两件事: ①R31 ← PC+4 ; ②J / JR LABEL
• 格式: JAL LABEL



• PCOffset26 → 26位偏移量, 符号扩展为32位后与+4后的PC相加
• 偏移量来自PCOffset26(26位立即数)的符号扩展, 有范围限制( ~ ).
• 函数名本身也只是一个LABEL, 与其他LABEL地位相同
• 通常该label需要使用.global伪操作定义为全局标记, 以便在汇编时被成功识别

• JALR指令 → 与JAR指令的区别在于跳转范围, 具有完整的32位地址, 可以不限空间完成跳转(类比JR与J指令的区别)

返回过程以及寄存器的保存和恢复

• 子例程以JR R31结尾, 而不需要像中断一样使用RFE指令, 因为不涉及特权级别的转换和SR的清零等过程

• 但是同样需要寄存器的保存, 因为子例程中可能改动寄存器中的值, 引发混乱
• 一般采用被调用者保存(Callee-save)策略, 因为调用者并不明确被调用者需要使用的寄存器
• 应该特别注意R31的保存和修改, 若存在嵌套调用, 则需要借助栈(stack)的数据类型保存寄存器(设错)

调用方式

• 必须知道: 子例程地址(或标记), 功能(不需要知道具体实现), 传给子例程的值(变元)的类型和输入位置, 返回值(的保存位置)

• 低级说法叫文档/手册, 高级说法叫API; 封装 + 接口 → 直接用

• 链接时的注意事项(.global, .extern)
• 对于声明子例程的程序, 需要使用.global Function_name伪操作来声明该子例程对其他程序可见
• 对于调用来自其他文件的子例程的程序, 需要使用.extern Function_name伪操作来说明该子例程来自其他文件, 需要在链接时被处理从而生成可执行映像
• 此时两趟的汇编过程并不能将汇编程序完全转化为机器码, 需要等待链接时对照完整的符号表完成最后的汇编工作.

递归子例程

• 子例程中调用自身, 则称为递归子例程
• 注意: 因为存在嵌套子例程的跳转, 所以在每一次跳转之前都需要使用一个专门的空间来进行寄存器的保存, 特别是R31的保存
• 不仅是子例程, 涉及嵌套的调用-返回机制时均需要在第一次嵌套调用前保存R31, 在最后一次嵌套调用后恢复R31.

• 问题: 如果使用固定的某几个存储单元来保存寄存器, 则这些单元中的值会在层层调用中被多次覆盖, 起不到保存的作用

• 解决方案: 数据结构 —— 栈(Stack)
• 后进先出, 每一次调用都将寄存器保存至栈顶的存储单元(入栈, PUSH), 后续通过依次出栈(POP)逐层还原寄存器(通过栈协议规定出栈 / 入栈操作)
• 存储临时值 / 返回值的寄存器不需要保存

与TRAP例程以及中断的区别

TRAP例程

• 服务例程包括操作系统资源

• 由系统程序员编写

• 通过TRAP指令进行跳转

• 使用R31保存PC

• 通过RET指令返回

中断例程

• 服务例程同样包含系统资源, 调用时具有向操作系统特权(Super User)的转换和向普通用户权限的恢复

• 由INT信号触发, 在当前指令处理周期的末尾跳转到中断例程

• 使用EPC保存PC(不会破坏R31, 只破坏EPC)

• 返回之前需要清空CAUSE

• 通过RFE指令返回, 还原R31和SR

子例程

• 由相同程序员或同事编写, 调用时不具有特权, 不涉及特权级别转换, 无法访问特殊资源

• 或某个库

• 通过JAL / JALR指令进行跳转

• 通过R31保存返回地址

• 运行时栈 → R30保存动态链接(框架指针副本)

• 通过JR R31(RET)指令返回

• 涉及框架指针的保存, 改变与恢复, 以及变元的压栈和出栈

相同点

• 自身或互相存在嵌套调用时均会破坏动态链接和返回地址, 需要调用者保存, 调用后还原

C语言函数

Preamble

• C语言主要是面向函数的, C程序本质上是函数的集合, 每条语句属于且仅属于一个函数

• 所有的程序总是从main函数开始和结束, main函数可能会调用其他的函数, 并且这些函数也可能依次调用更多的函数.

• 控制权最终会返回main函数.

• 某种意义上, 函数扩展了语言提供的原始运算和结构

调用函数步骤

• 调用者的变元传给被调用者(传参), 并且控制权被传给调用者

• 被调用者执行任务

• 返回值被传回给调用者, 并且控制权返回给调用者

• 其他与子例程无明显区别

底层实现

运行时栈

• 栈帧(Stack Frame): 函数在被调用时，所拥有的一块独立的用于存放函数所使用的状态和变量的栈空间. 每个函数都对应有一个栈帧. 同一个函数多次进入, 每次可能会分配到不同的栈帧. 整个栈的内容在同一个时刻可以看作是由许多栈帧依序“堆叠”组成的.

• 栈上的每个栈帧都有相同的结构, 都包含了为函数的局部变量, 保存的寄存器, 动态链接, 返回地址和为参数分配的空间等.

• 每个函数对应一个栈帧 → 不允许递归, 栈帧会在调用中被覆写

• 每次调用函数均分配一个栈帧 → 允许递归
• 在调用函数时分配栈帧, 在函数返回时收回栈帧(于是导致了自动存储期的出现)

• 需要谨记, 栈在内存中的增长方向是从大内存地址到小内存地址

具体调用机制

• 调用前准备(参数传递及压栈)
• 将参数传送到被调用函数可以访问的存储区域中(ADDI dst src #0). 如果参数寄存器(R4~R7)数量不够(参数>4个)则将多出的参数存入运行时栈中调用者栈帧的顶部(SUBI R29, R29, #4; SW 0(R29), R20)

• 寄存器压栈: 被调用函数栈帧分配, 将一些寄存器的值保存到运行时栈中, 使得当控制权交还给调用者时, 调用者的寄存器看起来好像没动过, 具体步骤为:
• 保存调用者的返回地址R31和帧指针R30的值, 将副本压入栈中(防止被嵌套调用修改). 其中帧指针的副本叫做动态链接. 故本步可称为保存返回地址和动态链接, 方式是将其副本压入栈中.
• 保存调用者的R30后就可以调整R30指向被调用者栈帧的最底部, 即调用者栈帧的顶部+1
• 由于参数被保存在调用者栈帧的顶部, 故通过帧指针+偏移量即可方便地访问参数, 如LW R8, 4(R30), 但注意由于栈在内存中由高向低增长, 故偏移量是正数而不是负数
• 被调用者将需要保存的其他寄存器压栈
• 调整R29指向栈顶(R29始终明确指向栈顶, 不需要保存)

• 被调用函数执行任务(JAL FUNC_A)

• 当被调用函数完成工作时, 其栈帧从栈中弹出, 并且控制返回到调用者函数, 具体步骤为:
• 移动栈指针, 将参数从运行时栈中弹出(如果存在变元压栈)
• 恢复先前被保存的寄存器(出栈)
• 恢复动态链接(出栈)
• 恢复返回地址(出栈)
• RET指令(JR R31的助记符)将控制权交还给调用程序

• 一旦控制返回到调用函数, 则执行代码取出被调用函数的返回值(使用或者抛弃)

• 注1: 出栈操作通过移动栈指针实现, 即使实际意义上已经弹出了但是数据仍然留在存储器中

• 注2; 重申重点, 任何调用者的局部变量对于被调用函数都是不可见的, 调用者通过参数传递将数值传入被调用者可返回的存储空间作为副本操作. 因此被调用者访问的往往只是原变量的值而不是原变量本身

具体实现

C中的指针和数组

指针

• 👆🏻注1: 用指针解引用和通过原变量访问虽然在效果上等效, 但是底层的寻址方式是不同的!

• 注2: 内存只能与通用寄存器进行直接交互, 故并不存在SWI指令将立即数直接写入/加载, 只有通过将数值加载进寄存器中才能写入内存.

• 经典的swap函数启示我们: 函数要修改调用者传递给它们的变元, 就必须在调用函数的栈帧中为变元分配空间, 然后令被调用者访问调用者的栈帧, 才能实现变元的值的修改, 否则传参后操作的是不同寄存器中的不同副本

数组

• 数组的寻址模式: 基址(首地址) + 索引 * 单个元素占空间大小
• 该公式成立的前提: 所有元素在内存中按照索引顺序连续排列, 且所有元素大小相同
• 该前提即为数组的存储特性.

高级CPU设计

计算机提速方式

• 早期 –> 减少晶体管的切换时间 (最终会碰到物理瓶颈)

• 现代 → 制作专门的逻辑门电路, 以更高效率实现某些功能(如除法逻辑电路, 可使除法运算在1个而非res + n个时钟周期内完成), 代价是ALU变得更加庞杂(复杂度和速度的平衡)

• CPU时钟速度不断加快, 因此相应地, 需要提高内存(RAM)的速度以持续为CPU提供数据, 才能充分利用算力
• 数据要用线来传递, 称为“总线”(bus), 而RAM需要接收指令, 找到地址, 取出数据, 读写数据, 势必造成延迟, 而CPU速度过快, 小延迟会造成大问题

解决延迟的方法之一: 给CPU加一点RAM, 成为“缓存”(Cache)

• 缓存离CPU(ALU)近, 在一个时钟周期内就可以给ALU提供数据, 显著快于到RAM中寻址, 取数据, 传输数据的过程

• 处理器中空间不大, 所以缓存一般只有KB或MB

• CPU从RAM中拿数据时, 可以直接让RAM传一批, 数据存储在缓存中, 需要时直接从CPU缓存 (离CPU近, 一个时钟周期就可以提供数据) 中调用, 而不用反复到RAM中取数据, 从而提高ALU取数据的速率

• 缓存也可以充当临时空间, 为某些过程冗长的复杂运算存储中间值

• 想要的数据在缓存中 –> cache hit

• 想要的数据不在缓存中 –> cache miss

• 计算后缓存与RAM中的数据不一致, 即发生修改, 则必须记录下来, 在后续操作中同步. –> 缓存里每块空间有一个特殊标记, 称为脏位(Dirty Bit). 同步一般发生在当缓存满了而CPU又要缓存时, 在清理缓存腾出空间之前, 会先检查脏位, 如果是“脏的”, 在加载新内容之前会把数据写回RAM.

解决延迟的方法之二: 指令流水线(Instruction Pipelining)

• double efficiency

• 由于Fetch - Decode - Execute三个阶段由CPU的不同部分执行, 故可以并行, 让CPU三个部分均始终处于运行状态. (类比: 洗衣机, 烘干机, 处理一批床单)

• 也会造成部分问题, 例如:
• 数据依赖性(Data Dependencies): 本来要先改变数值在读写数据, 但是在数值改变完成之前就读写了数据, 导致读取 / 写入的是Outdated Data
• 解决方案: 流水线处理器需要先弄清楚数据依赖性, 必要时停止流水线一步一步来, 避免出现问题.高端CPU会更进一步动态排序有依赖关系的指令, 来最小化流水线的停工时间, 提高效率, 称为“乱序执行”
• 条件跳转(Conditional Jump Instructions): 指令改变程序的执行流, 条件判定前, 高端CPU不会空等而是会推测可能性更大的指令, 然后提前将其放进流水线(“推测执行”, Speculative Execution), 猜对立即执行, 猜错清空流水线(Pipeline Flush), 就像走错路回头重来
• 尽可能减少清空次数 –> 优化猜测分支机制, 即为“分支预测”, Branch Prediction

解决方案之三: 超标量处理器(Superscalar) → 一个时钟周期可以完成多个指令, 成倍提高效率

解决方案之四: 同时运行多个指令流

• 即使用多核处理器(多个独立处理单元, 但是整合紧密, 可以共享包括缓存等在内的某些资源)

• 多核不够时, 甚至可以使用多个CPU (广泛应用于某些高端计算机, 例如服务器), 2个或4个最为常见

• 解决方案之五: 超级计算机(Supercomputer) → 怪兽级运算
• 神威 · 太湖之光 (The Sunway TaihuLight, 江苏无锡) → 40960个CPU, 每个CPU有256个核心, 每个核心频率1.45GHz, 每秒进行9.3亿亿次浮点数运算 (Flops)

软件工程(Software Engineering)

Object 对象

• 虽然有函数的封装模式, 但是对于大项目而言(如Microsoft Office), 可能仍然需要数十万个函数

• 解决方案 → 将函数打包成层级, 将相关代码都放在一起, 打包成对象(objects), 提升一层封装

• 对象内部可能包括子对象, 函数, 或变量, 每当需要一个功能就需要从最外层的对象逐层向下寻找, 最终找到想执行的函数

Object Oriented Programming 面向对象编程

• 将函数打包成对象的思想 → 面向对象编程

• 封装组件, 隐藏复杂度, 选择性地公布功能. another level of abstraction!

• 把大系统 break down 成多个对象 / 子对象, 有利于团队协作开发大型项目

• OO Languages → C++, C#, Object-C, Python, Java

Application Programming Interface(API) 程序编程接口

• 帮助不同程序员编程, 对接, 不用知道具体细节, 只要知道怎么使用即可(整合成一个USB口)

• 让不懂行的程序 / 对象随意访问对象内的函数 / 子对象并不是明智选择(未知细节, 可能引发混乱)

• API → 控制哪些函数和数据可供外部访问, 哪些仅供内部访问

public / private

• 面向对象的编程语言可以指定函数性质为public / private, 从而设置权限

• 如果函数被标记成private则意味着只有同一个对象内的其他函数能调用它; 标记为public则其他对象也可以调用它

Integrated Development Environments(IDE) 集成开发环境

Debug 调试

Readme / Comment 文档 / 注释

• 给人看的

• 帮助开发者和他人理解代码

• 文档还可以提高复用性(Code Reuse), 可以直接用别人写好的代码来解决问题, 而不是重新编写一个差不多功能的模块

• 看怎么用就行, 不需要读代码.

Version Control 版本控制

• 放置(托管)代码的中心服务器 → 代码仓库(Code Repository)

• 想要修改 → Check it out, 一般可以直接在IDE内弯完成, 修改完了再把代码放回去, 称为提交(Commit).

• 如此这般, 多名程序员可以同时写代码, 建立庞大的代码系统

• 代码的主版本(master version)应该总是编译正常且bug很少, 以免对开发工作造成困扰

• 源代码仓库保存有之前的所有版本, 出现bug可以回滚(Roll back)到之前的稳定版本

• 源代码管理同样记录了谁改了什么代码

Quality Assurance Testing(QA) 质量控制

• 写代码和测试代码密不可分, 测试一般由个人或小团队完成, 统称质量保证测试, 模拟各种情况寻找bug

Beta / Alpha

• Beta → 接近完成但不是100%完全测试通过
• 有时会向公众发布以帮助尽快发现问题, 将用户视作免费的QA团队

• Alpha → 产生于Beta版本之前, 一般很粗糙, 错误很多, 经常只在公司内部测试

操作系统(Operating System)

操作系统

• 随着计算机运行速度激增, 人工操作效率很快低于计算机, 故需要计算机自身的操作系统来管理任务

• 操作系统本质也是计算机程序, 但是具有操作硬件的特殊权限, 可以运行和管理其他程序(一般是开机启动的第一个程序, 其他所有程序都由操作系统启动)

批处理

• 操作系统能够控制计算机按序处理多个任务, 而不用不断人工插入穿孔纸卡

外部设备(外设)

• 计算机连着的其他设备统称为外设

设备驱动程序(Device Drivers)

• 和早期的外部设备交互是非常底层的, 程序员需要了解设备的硬件细节, 但是随着设备的廉价化, 设备种类越来越多, 程序员需要考虑兼容问题, 但是又无法做到拿到所有类型的设备测试

• 所以需要操作系统充当软件和硬件之间的媒介

• 操作系统提供API来抽象硬件, 称为设备驱动程序

• 程序员可以用标准化机制和输入输出硬件(I/O设备)交互

多任务处理(Multitasking)

• 通过调度, 让多个程序同时运行, 从而最大限度减少CPU的空闲时间, 充分利用算力)

• 当处理需要很多个时钟周期才能完成的程序时, 暂时跳出本程序, 处理其他程序, 等待任务完成之后再恢复执行该程序的指令流

• 通过调度让不同程序调用不同的算力资源, 充分利用每一个区域

虚拟内存

• 问题: 当切换程序时, 如何保证原程序的数据不丢失?
• 给每个程序分配专属内存块(可能非连续, 分成数个区域, 对程序员来说很难跟踪)

• 为了隐藏这种复杂性, 操作系统会把内存地址进行虚拟化, 程序可以假定始终从0地址开始执行, 简单又一致, 而实际物理位置被操作系统隐藏和抽象了(分配代号)
• Metaphoric Explanation: 相当于给书编页码, 即使书页放置于不同的抽屉(物理上不连续), 页码对书而言仍是连续的

• 这种机制使得程序的内存大小可以灵活增减(Dynamic Memory Allocation). 对程序来说, 内存分配看上去是连续的.

• 这简化了一切, 为操作系统同时运行多个程序提供了极大的灵活性; 另一个好处是可以将程序隔离, 如果一个程序出错也不至于影响其他程序, 这称为内存保护(Memory Protection)

• 对防止恶意软件攻击也有效果, 不允许跨软件修改内存

多用户分时操作系统

• 计算机不仅能同时运行多个程序, 还能让多个用户同时访问, 用户用终端(键盘+屏幕)访问计算机
• 终端只是连接到主计算机的屏幕+键盘, 本身没有处理能力

• 为了确保其中一个人不会占满计算机资源, 开发了分时操作系统(Time Sharing), 意思是每个用户只能用一小部分处理器和内存等资源

Unix

• 操作系统核心功能 → 内存管理, 多任务和输入 / 输出处理 → “内核”(Kernei)

• 一堆非内核部分的有用的工具(例如程序和运行库)

• 内核紧凑 → 功能不全面; 如果有错误发生, 就让内核恐慌(Panic). 调用它时机器会崩溃, 无法恢复, 所以调用一个叫panic的函数

• 这种简单性意味着Unix可以在更便宜更多的硬件上运行

MS-DOS (Microsoft开发的磁盘操作系统)

• 只有160kb, 一张磁盘就能容纳

• 虽然缺少多任务和保护内存的功能, 经常崩溃, 但是可以通过重启解决

• 蓝屏 → 程序崩溃严重, 把系统也带崩溃了

文件系统 (File System)

文件格式 (File Format)

• 随意排列文件数据完全没有问题, 但按格式排会更好

• 可以做成自己的格式, 但是最好使用现成标准, 如JPEG和MP3

• 简单的文件格式举例:
• 不管文件是什么格式, 文件在底层全是一样的: 一长串二进制编码, 区别在于解码的方式
• txt → text 文字, 解码数据的关键是ASCII编码
• wav → wave 波形, 用于存储音频数据, 读取代码之前需要知道一些参数, 比如码率(bit rate), 以及单声道 / 立体声
• 数据的数据叫做 元数据(meta data) , 存储在实际数据之前的文件开头, 因此也叫文件头(Header)



• bmp → 位图(bitmap), 存储图片每个像素由RGB组成; bitmap文件开头也是元数据, 有图片宽度, 图片高度, 颜色深度
• 每个字节可以表示范围0~255的正整数, 颜色数值不同表示RGB三种颜色的强度不同, 255为全强度(RGB强度按顺序三个三个排列, 就像三联密码子)

文件系统

平面文件系统(Flat File System)

• 最简单的格式: 文件一个个在存储设备中连续存储

• 存储器只知道存储, 不知道每个文件起始或终止的位置, 所以需要一个特殊文件, 记录其他文件的位置, 是为目录文件(Directory File), 经常存在于存储器的开头(位置0), 方便寻找

• 目录文件中存储其他所有文件的名字(格式是文件名+’.’+扩展名, 扩展名帮助得知文件类型)以及元数据(如创建时间, 文件所有者, 读写权限等), 文件的起始位置和长度

• 如果要添加 / 删除文件或更改文件名, 就必须更新目录文件

• 问题: 如果给前面的文件添加数据, 就有可能会覆盖后续程序的一部分

• 所以现代文件系统会做两件事:
• 把文件划分成一块块, 导致有一些预留空间, 可以方便改动, 同时方便管理
• 拆分文件, 存在多个块里(Fragmentation). 文件系统会记录多个而非一个块(类似操作系统的虚拟内存), 文件可以轻松增删数据, 但是会产生很多内存碎片, 而对很多存储设备来说碎片化是坏事. 而现实情况是大文件可能被存在数百个块里.
• 答案: 碎片整理 → 计算机会把数据来回移动, 排列成正确的顺序, 各个区块进行重排.

• 如果要删除文件, 只需要在目录中删除该文件的注册信息, 让这一块空间变为可用即可. 在此之后那些区域会被新数据覆盖, 但在此之前, 数据还在原处, 使得文件恢复成为可能.

分层文件系统(Hierarchical File System)

• 最显著的区别: 目录文件不仅要指向文件, 还要指向子目录(Sub-directory), 需要额外的元数据, 来区分开文件和目录.

• 位于存储器最顶层的目录文件叫做根目录(Root Directory); 所有其他文件和文件夹都在根目录下

• 先从根目录读取子目录的位置和元数据, 在跳转至该区域读取子目录的内容, 最后访问子目录中的文件(子目录的书写格式与根目录相同

• 除了能做无限深度的文件夹, 还可以轻松移动文件, 只需要改动根目录和子目录的数据即可

• 拥有相对路径和绝对路径概念

内存和存储介质 Memory & Storage

• 一般来说, 电脑内存(Memory)是非永久性的(Non-permanent), 断电就会丢失当前内存中的全部数据, 所哟内存叫做易失性存储器(volatile memory)

• 存储器(Storage)则相反, 例如硬盘, 数据会一直保存, 直到被覆盖或者删除, 即使断电也不会丢失 → 存储器是非易失性的(non-volatile)

• 以往是易失性存储器远远快于非易失性存储器, 但是随着技术发展, 二者差距显著缩小(以致于apple独门技术swap的出现, SSD必要时临时充当内存)

• 最早的存储介质 → 打孔纸卡 / 纸带, 90年代一张卡能存960位数据. 纸卡以其不用电且便宜耐用的特性一直被沿用十几年. 然而坏处是读取慢, 只能写入一次, 因为打的孔无法轻易补上. 故对于存临时值, 纸卡并不好用.

延迟线存储器(Delay Line Memory)

• 原理: 拿一个管子装满液体, 如水银, 管子一段放扬声器, 另一端放麦克风, 扬声器发出脉冲时会产生压力波, 压力波需要时间才能传播到另一端的麦克风; 麦克风将压力波转化回电信号, 利用压力波的传播延迟来存储数据

• 假设有压力波代表1, 则无压力波代表0.

• 如果加一个电路连接麦克风和扬声器, 再加一个放大器来了弥补信号衰减, 就可以做一个存储数据的循环. 信号沿电线传播几乎是瞬时的, 所以任何时间点只显示1bit的数据

磁芯存储器

• 使用小型磁圈, 如果给磁芯绕上电线, 并施加电流, 可以将其在一个方向上磁化; 如果关掉电流, 磁芯保持磁化; 如果沿相反方向施加电流, 则磁化的方向(极性)会翻转, 这样就可以存1和0.

• 只存1位不够有用, 所以把磁圈排列成网格, 有电线负责选行和列, 也有电线贯穿每个磁芯, 用于读写一位(即用磁芯代替锁存器构建存储器电路, 多路选择器, 字线和写使能线等结构依然保留), 能够随时访问任何一个存储单元.

磁带(magnetic tape)

• 纤薄柔软的一长条磁性带子, 卷在轴上, 可以在磁带驱动器内前后移动.

• 磁带内有一个写头, 绕了电线, 电流通过时会产生磁场, 导致磁带的一小部分被磁化.

• 电流方向决定了极性, 代表1和0

• 还有一个读头, 可以非破坏性地检测极性

• 虽然磁带驱动器很贵, 但是磁带又小又便宜, 因此至今磁带仍用于存档

• 磁带的主要缺点是访问速度, 因为磁带是连续的, 必须倒带或者快进才能到达特定位置. 可能要经过几百英尺才能得到某个字节, 效率很低.

磁鼓存储器

• 有金属圆筒, 盖满了磁性材料以记录数据. 滚筒会持续旋转, 周围有数十个读写头, 等滚筒转到正确的位置, 读写头会读或写1位数据. 为了尽可能缩短延迟, 鼓轮每分钟可达到上千转

硬盘(Hard Disk Drive)

• 硬盘和磁鼓很相似, 只是用的是盘不是圆柱体.原理是一样的(利用磁盘表面的磁性 / 极性表示0 / 1)

• 硬盘的优势是薄, 于是可以将其叠在一起, 提供更多表面积以存储更多数据. 要找到相应的字节, 首先找到正确的磁盘, 再寻找该字节. (寻道时间)

软盘(Floppy Disk)

• 除了磁盘是软的, 其他基本一样. 更轻巧便携, 在1970~1990年代比较流行

光学存储器(光盘Compact Disk, CD)

• 功能和硬盘软盘一样, 都是存数据, 但用的不是磁性, 而是光盘上小坑造成的光的不同反射, 这会被光学传感器捕获到并解码为1和0

固态硬盘(SSD)

• 没有机械存储部件, 里面是集成电路

• 没有活动部件, 故SSD访问时间低于s, 但还是比RAM慢很多倍.

命令行界面(Command Line)

• 命令行 → 在人类和机器之间提供界面的一种方式, 是人机交互的一种

• 交互式 → 人和计算机之间来回沟通

早期设备

• 早期机械计算设备用齿轮, 旋钮和开关等机械结构来输入输出, 也是交互界面的一种. 包括早期计算机ENIAC也是用一大堆机械面板和线来操作, 单单输入数据可能就要耗费数周时间. 运行完毕之后要拿出数据, 一般是打印到纸上

• 1950年代机械输入完全消失, 因为出现了打孔纸卡和磁带等新的存储介质, 但输出仍然是打印到纸上, 同时还有大量指示灯, 在运行中提供实时反馈.

• 时代特点: 尽可能迁就机器, 对人类好不好用是其次. 经典例子是打孔纸带, 完全依照计算机思维设计, 人类程序员要花费额外的时间和精力转成计算机能理解的格式, 一般需要额外人员和设备帮忙才能完成. 的确是人类负责输入程序和数据, 但是计算机不会交互式回应. 程序开始后 会一直运行直到结束, 因为机器太贵, 不能等人类慢慢敲命令给数据, 而要同时放入程序和数据.

现代交互

• 获取用户输入的方式 → 键盘(Keyboard)

• 早期计算机使用了一种特殊打字机, 是专门用来发电报的, 叫电传打字机, 可以用电报线发送和接收文本, 使得两人可以长距离沟通. 因为有电子接口, 所以很容易为计算机改造适配. 人类输入命令按下回车, 计算机就会执行命令并把结果打出来.

• 这种交互就叫命令行界面(Command Line Interfaces)

• 到1970年代, 屏幕代替电传打字机变得可行, 但与其为屏幕制作全新的标准, 工程师宁愿直接用现有的电传打字机协议, 因为屏幕就像无限长度的纸, 除了输入和输出字, 没有任何东西. 正由于协议是一样的, 所以计算机分不清纸和屏幕, 唯一存在的概念是终端(Terminal)