Elian's blog page

分页、分段连续分配要求进程占用一整段连续物理内存，容易受到外部碎片和连续空间不足的限制。分页和分段都允许进程的逻辑地址空间与物理内存分离，只是划分方式不同： 方式 划分依据 主要目标 分页 按固定大小划分 提高内存利用率，避免外部碎片 分段 按逻辑模块划分 方便共享、保护，符合程序员视角 段页式 先按逻辑模块分段，再把段分页 结合分段和分页的优点 透明性 分页的页号、页内偏移通常由硬件从一维逻辑地址中自动拆出，对所有程序员透明；分段的段名、段号、段内地址更贴近程序逻辑，因此在程序员可见。但无论分页还是分段，最终装入到哪个物理页框或哪段物理内存，仍然对进程透明。 基本分页分页存储把进程的逻辑地址空间划分为大小相等的页，把物理内存划分为同样大小的页框。页可以离散地装入不同页框中。 概念 含义 页 / 页面 进程逻辑地址空间的固定大小块 页框 / 页帧 / 内存块 物理内存中的固定大小块 页号 页面编号，从 0...

存储单元、编址与容量 概念 含义 存储元 存放 1 bit 信息的基本单位 存储单元 具有一个地址的最小可寻址单位 存储字 一次作为整体读写的一组二进制位 存储字长 一个存储字包含的二进制位数 按字节编址 每个地址对应 1 Byte，现代计算机最常见 按字编址 每个地址对应 1 个字，地址加 1 表示移动 1 个字 若地址有 $n$ 位，最多能表示 $2^n$ 个地址。若每个地址对应一个存储单元，则最多可寻址 $2^n$ 个存储单元。 $$\text{存储容量} = \text{存储字数} \times \text{存储字长}$$ 存储芯片接口一片存储芯片对外主要有四类信号：地址线、数据线、片选线、读写控制线。 若芯片有 $n$ 根地址线、$m$ 根数据线： $$\text{芯片容量} = 2^n \times m\ bit$$ 信号 作用 地址线 选择芯片内部的某个存储单元 数据线 传送该存储单元读出或写入的数据 片选线 CS/CE 决定当前芯片是否参与本次访问 读写控制线...

存储系统存储系统是协同工作的一组不同速度、容量、价格的存储器。 现代计算机不会只使用一种存储器，而是形成层次结构：越靠近 CPU，速度越快、容量越小、单位成本越高；越远离 CPU，速度越慢、容量越大、单位成本越低。 存储器分类存储器可以按多个维度分类。 分类维度 类型 关键点 按层次 寄存器、Cache、主存、辅存 越靠近 CPU 越快、越小、越贵 按介质 半导体、磁表面、光介质 主存和 Cache 多为半导体；磁盘是磁表面；光盘是光介质 按存取方式 随机存取RAM、顺序存取、直接存取（随机存取找块+顺序存取读数据）、相联存取 RAM 任意单元访问时间相同；磁带是顺序存取；磁盘是直接存取；TLB/快表体现相联访问思想 按可改写性 读写存储器、只读存储器ROM ROM 名义上只读，但许多 ROM 类器件可擦写 按断电保存性 易失性、非易失性 主存和 Cache 通常易失；磁盘、SSD、ROM 非易失 按读出是否破坏 破坏性读出、非破坏性读出 DRAM 读出后需要重写；SRAM、磁盘、光盘通常非破坏性读出 RAM 和 ROM...

浮点数的基本思想定点数的小数点位置固定，表示范围受位数直接限制。浮点数把一个数拆成三部分： $$(-1)^S \times M \times 2^E$$ 部分 含义 表现形式 $S$ 符号位，决定正负, 取值为0/1 $M$ 尾数或有效数，决定精度 非负的定点小数 $E$ 阶码，决定数量级 定点整数，常用移码表示 IEEE 754 标准IEEE 754 规定了浮点数的编码格式、特殊值、舍入规则和异常状态。 浮点数编码格式如下。 格式 总位数 符号位 阶码位 尾数字段 阶码偏置 单精度 float 32 1 8 23 127 双精度 double 64 1 11 52 1023 规格化数当阶码字段既不全 0，也不全 1 时，表示规格化数： $$(-1)^S \times (1.F) \times 2^{e-bias}$$ 这里的 1.F 表示尾数最高位的 1 不存入字段，称为隐藏位。 非规格化数当阶码字段全 0、尾数字段不全 0 时，表示非规格化数： $$(-1)^S \times (0.F) \times...

运算器与 ALU运算器负责对数据进行处理。ALU（Arithmetic and Logic Unit，算术逻辑单元）是运算器的核心部件。 ALU 可以看成一个受控制信号驱动的数据处理单元： 项目 含义 操作数 A、B 参与运算的两个 n bit 数据 控制信号 指定本次执行加、减、与、或、异或、移位等哪一种操作 Cin 进位输入，常用于加法、减法、带进位运算 结果 F n bit 运算结果 Cout 进位输出 标志位 描述本次结果的特征，如是否为 0、是否溢出 如果 ALU 支持 $k$ 种操作，至少需要： $$m \ge \lceil \log_2 k \rceil$$ 位控制信号，才能区分这些操作。 基本运算ALU 支持的操作可以先分成三类。 类别 常见操作 关注点 算术运算 加、减、乘、除 数值结果、进位、溢出 逻辑运算 与、或、非、异或 按 bit 处理，不关心数值正负 移位运算 逻辑移位、算术移位、循环移位 bit 位置变化，可能影响符号位或进位位 逻辑运算逻辑运算按 bit...

乘法乘法运算常见有三类实现方式： 实现方式 基本思路 迭代式乘法器 复用同一个 ALU 和寄存器，每轮根据乘数位决定加、减或不操作，再移位。若一次ALU加法和一次移位各需要一个时钟周期，则对于$n$位乘法需要$2n$个时钟周期 阵列乘法器 用大量并行硬件同时生成并累加部分积，可在一个时钟周期内完成一次乘法运算。速度最快但硬件开销大。 移位-加减法 从算法层面把乘法转化为移位、加法、减法，硬件成本最低但速度最慢 下面介绍的即迭代式乘法器 无符号乘法乘法过程可以用三个核心寄存器理解： 寄存器 作用 ACC 保存部分积的高位，也参与加法 MQ 初始保存乘数，运算结束后保存乘积低位 X 保存被乘数 ACC 和 MQ 常连在一起看作一个双倍位宽寄存器： 1ACC | MQ 乘法的核心动作是： 看 MQ 的最低位。 若最低位为 1，则 ACC = ACC + X。 若最低位为 0，则 ACC 不变。 将 ACC | MQ 整体右移一位。 重复 n 次后，ACC | MQ 中保存完整乘积。 Note 若 ACC + X...

进位计数制进位计数制用有限个数码和位权表示数值。对于 $r$ 进制数： $$K_nK_{n-1}\cdots K_1K_0.K_{-1}K_{-2}\cdots$$ 其真值为： $$\sum_i K_i r^i$$ 其中每个数码 $K_i$ 必须满足： $$0 \le K_i < r$$ 例如： $$(975.36)_{10}=9\times10^2+7\times10^1+5\times10^0+3\times10^{-1}+6\times10^{-2}$$ 进制转换任意进制转十进制按位权展开后求和。 Example $$(1011.01)_2=1\times2^3+0\times2^2+1\times2^1+1\times2^0+0\times2^{-1}+1\times2^{-2}=11.25$$ 十进制转任意进制整数部分和小数部分分开处理。 部分 方法 读数方向 整数部分 除基取余 余数从下往上读 小数部分 乘基取整 整数部分从上往下读 整数部分：除基取余把十进制整数 $N$ 转为 $r$ 进制： 用...

Computer System Overview这部分回答三个问题： 计算机系统由什么组成。 程序如何在硬件上运行。 如何衡量一台计算机的性能。 Summary 计算机系统 = 硬件 + 软件 硬件按冯诺依曼思想组织 程序以指令序列形式存放并运行 性能由存储器、CPU 和系统整体指标共同描述。 计算机系统计算机系统由 硬件 和 软件...

分治递推组合数学中最常见的思想是分治：把一个规模为 $n$ 的对象，按某个天然位置拆成较小的同类对象。 若一个对象只能落入若干互不重叠的情况，使用加法： $$T(n)=T_1(n)+T_2(n)+\cdots$$ 若一个对象由几个互相独立的部分共同组成，使用乘法： $$T(n)=A(n)\cdot B(n)$$ 很多递推式混合使用两者。 Info 递推式里最容易漏的是空结构。空结构有时表示 0，有时表示 1： 若计数的是“方案数”，空方案通常算 1 种。 若计数的是“结点数”，空树通常有 0...

基本概念散列表也叫哈希表，英文是 Hash Table。它的特点是：可以根据数据元素的关键字直接计算出它在表中的存储地址。 散列函数也叫哈希函数，记作： $$Addr=H(key)$$ 它建立了“关键字 $\rightarrow$ 存储地址”的映射关系。 理想情况下，查找一个关键字只需要： 用散列函数计算地址。 到该地址检查关键字是否匹配。 因此理想时间复杂度可达到 $O(1)$。 冲突与同义词冲突：插入一个数据元素时，根据关键字算出的地址已经存放了其他元素。 同义词：不同关键字通过同一个散列函数映射到同一个地址。 例如表长为 13，散列函数为： $$H(key)=key\bmod 13$$ 则： $$1\bmod 13=1,\quad 14\bmod 13=1$$ 所以 1 和 14 是同义词。若地址 1 已存 14，再插入 1 就发生冲突。 装填因子散列表查找效率不是只由散列函数决定，而主要由三类因素共同决定： 散列函数是否让关键字均匀分布。 处理冲突的方法。 装填因子。 装填因子 $\alpha$...