计算机概论

计算机硬件组成

• 中央处理器CPU(运算器&控制器&寄存器组&内部总线)

  • 寄存器
    • cpu内部用来暂时存放参与运算的数据跟结果的小单元
    • 本质为常见的时序逻辑电路，只包含存储电路
  • 运算器
    • 算数逻辑单元(Arithmetic and Logic Unit, ALU)
      • 负责数据处理，对数据的算数与逻辑运算
    • 累加寄存器(Accumulator, AC)
      • 通用寄存器，为ALU执行算数或逻辑运算时，提供工作区
    • 数据缓冲寄存器(Data Register, DR)
      • 在内存进行读/写操作时，暂时存放指令或数据，分离不同时间读/写的数据
    • 状态条件寄存器 (Program Status Word, PSW)
      • 保存算数和逻辑指令的结果所产生的条件码，包括状态标志和控制标志
  • 控制器
    • 程序计数器(Program Counter Register, PC)
      • 寄存信息跟计数，保存指令地址并自动保存下一条指令地址
    • 地址寄存器 (Address Register, AR)
      • 保存当前CPU访问的内存单元的地址
    • 指令寄存器 (Instruction Register, IR)
      • 暂存指令
    • 指令译码器(Instruction Decoder, ID)
      • 分析解释指令中的操作码字段，识别该指令的操作，向控制器发出控制信号，控制各部件完成工作
  • 寄存器组
    • 通用寄存器 ：作用可变
    • 专用寄存器： 运算器和控制器中的寄存器是专用寄存器，作用固定
  • 内部总线是一种内部结构，是 cpu 内存 输入 输出设备传递信息的公用通道

  

• 存储器(内部存储&外部存储)

  • cpu 内部的通用寄存器组，cpu内的Cache(高速缓存)，
  • cpu外部的Cache、主板上的主存储器，主板外的联机磁盘存储器（在线），U盘存储（离线）
  • ** Cache 和主存之间的交互功能全部由硬件实现 ** 主存与辅存之间的交互可由软硬件结合实现
  • 分类方式
    • 位置 ： 内存与外存
    • 工作方式: 读/写存储器（Random Access Memory RAM），只读存储器(Read Only Memory ROM)
    • 访问方式：按地址访问、按内存访问
    • 寻址方式：随机存储器、顺序存储器、直接存储器
  • Cache 高速缓存
    • 从内存中去取数据映射到Cache 中，cpu 会先从 Cache 中寻址，取不到才会去主存中获取，然后替换掉，Cache 中的一块，Cache 与主存中的地址映射是由硬件自动完成的
    • 映射关系分类
      • 直接映像：固定的
      • 全相联映像：主存与Cache存储器均分成大小相同的块，相互映射
      • 组相联映像：将组内的块再分组
    • 替换的算法
      • 随机替换
      • 先进先出
      • LRU 近期最少使用算法
      • 优化替换算法，先统计Cache的替换情况，下次根据替换情况来替换
  • 虚拟存储器（用磁盘来 扩大 内存 swap）

• 输入与输出

  • 内存与接口地址的编址 方式
  • 外设
    • 直接程序控制
      • 无条件传送
      • 程序查询 需要先查询外设状态，再去执行
    • 中断处理
      • 在接受中断请求信号后，会保存程序现场，先去执行中断，再去执行目前的程序
      • 中断优先级控制 多个中断源服务，CPU 会优先响应级最高的中断源
    • 直接内存存取 （Direct Memory Access, DMA）
      • 内存在I/O 设备间的传送一个数据块的过程中，不需要CPU的任何干涉 实际操作是由DMA硬件直接执行完成的。但此时总线是被占用的
    • 输入输出处理机 （Input/Output Processor, IOP ) 分担了CPU的一部分功能，实现对外围设备的统一管理，完成外围设备与主存之间的数据传送

• 总线结构

  • 总线（bus ）数据总线、地址总线、控制总线3类。
    • 数据总线 (Data bus, DB) 信息传输，双向的，宽度决定一次性交换数据的位数
    • 地址总线 (Address bus, AB)传送CPU发出的地址信息， 单向的，最大寻址能力
    • 控制总线(Controller bus, CB)，双向的。

计算机安全

• 三大分类 技术安全，管理安全，政策法律安全
• 数据安全（内部安全，外部安全）
• 可靠性 （不稳定期，正常工作期，老化期）
  • 串联系统的可靠性 = 各个子系统可靠性相乘
  • 并联系统的可靠性 = 1- (1-r1)* (1-r2)* (1-r3) 1 减去 不可靠性
  • N模冗余系统 N=2n+1 只要 n+1 或 n+1以上的系统正常工作就是正常工作

计算机性能

计算机体系结构

• 处理系统
  • 单处理系统
  • 并行处理与多处理系统
  • 分布式处理系统
• 指令系统 (Instruction Set Architecture ISA )

  • 1.操作数在cpu上的存储方式 2. 显示操作数的数量 3. 操作数的位置，能放入主存，如何定位 4.指令支持那些操作 5. 操作数的类型与大小

  • 暂存机制

    • 堆栈（stack）, 累加器 (Accumulator), 寄存器组 (a set of register)

  • CISC (Complex Instruction Set Computer) 复杂指令集计算机

  • RISC (Reduced Instruction Set Computer) 精简指令集计算机

    • 关键技术
    • 重叠寄存器窗口
    • 优化编译技术
    • 超流水及超标量技术
    • 硬布线逻辑与微程序的结合

  • 指令的流水

    • 顺序方式 先分析再执行
    • 重叠方式 （分析与执行指令 同时执行）
    • 流水方式 把重复的顺序处理过程分解为若干子过程，每个子过程可以
      • 解决局部相关性，解决
      • 超流水线
      • 超标量
      • 超长指令字
      • 吞吐量 为最长子过程耗费时间的导数

软件（程序&数据&文档）

• 系统软件
• 应用软件

数据表示

• 机器数 二进制数
• 无符号数
• 带符号数（机器数的最高位代表正负符号，其他标识数值）

码制 （原码，反码，补码，移码）

• 原码 由符号位和真值的绝对值组成（原码不能直接拿来计算）
• 反码：正数不变，负数的反码是其原码的基础上，符号位不变，其他的 按位取反
• 补码：正数不变，负数的补码是其反码加一 （计算时一般使用补码）
• 正数的 原码，反码，补码 一致
• -0 与 +0 是不一致的，其符号位不同
• 反码与补码 为了减法的计算问题
  • 将减法变成 加法去计算，减法电路比 加法电路 复杂

字长 就是一次性读取二进制位的个数
定点整数-根据字长求范围，
原码 =`-(2^(n-1) - 1) ~ +(2^(n-1) - 1)`  = 反码
补码 中 人为 规定 `-0 = -2^n` 所以补码范围为 `-2^(n-1) ~ +(2^(n-1) - 1)`  = 移码

小数的表示

• 定点小数（纯小数，如0.8）

  • 正负号|1|0|0|0|

• 定点小数 (规定所有数值数据的小数点后隐含在某一个固定位置上)，小数点本身不占用位置

  定点小数-根据字长求范围，
  原码 =`-(1- 2^-(n-1)) ~ +(1- 2^-(n-1))`  = 反码
  补码 中 人为 规定 `-0 = -2^n` 所以补码范围为 `-1~ +(1-2^-(n-1))`  = 移码

浮点数表示 （小数点位置不固定）

• N = 尾数*基数^指数|阶码
• 尾数 = 定点小数 （补码）， 阶码=定点整数（移码）
• N = M * 2^E (E 阶码 M 尾数)
• 符号位，指数，尾数
• 阶符（阶码的符号位）|阶码|数符（尾数的符号位）|尾数 构成了浮点数
  • 基数在计算机中默认为2
  • 阶码影响数值的范围
  • 尾数可以表示有效精度，尾数越多
  • 结果格式化
• 计算过程
  • 阶码对齐，小数向大数对齐，小数的尾数右移实现的，高位补零
  • 对尾数进行计算
  • 结果格式化
• IEEE754 为浮点数事实标准

逻辑运算

• 与 两者都为真才真
• 或 两者有一个为真就真
• 非 取反
• 异或 两者相同为真 不相同为假

校验码

• 奇偶校验码 1位
  • 只能检测错误，不能纠错
• 海明码 把第N位的校验码放在 2n 位上
  • 在数据位之间 加入 K 个校验位，能检错跟纠错
  • 设数据有n位，校验码为x位，校验码一共有2^x 种取值方式
    • 2^x - 1 > x+n （能表示的出错的总数，要大于任一位出错的数值）
• CRC
  • 采用 mod 2 的方式去计算

程序设计语言

程序设计语言基本概念

• 机器指令是最基本的计算机语言（可读性差，难以修改和维护）
• 汇编语言（特定计算机）&机器语言为低级语言
• 源程序 通过 汇编、解释和编译 进行翻译
• 解释程序（解释器）
  • 执行源程序 翻译成中间代码加以执行
• 编译程序（编译器）
  • 编译器将源代码翻译成目标程序
• 语法，语义，语用，语境
• 语言
  • Fortran(Formula translation) 第一个广泛应用的高级语言
  • c 直接访问操作系统和底层硬件
  • c++ 面向对象，封装继承多态
  • c#
  • java 删除了c++指针相关特征
  • Python 面向对象，解释性（解释器=>中间码）语言（脚本语言）
  • JavaScript 脚本语言，解释性
• 语言分类
  • 命令式&结构化 Fortran c
  • 面向对象 c++ java
  • 函数式（LISP）1958年为人工智能应用而设计的语言
  • 逻辑型程序设计语言 ProLog

程序设计语言基本成分

• 基本成分包括 数据，运算，控制和传输
• 数据
  • 有存储类别 ，类型，名称，作用域，生存周期… 属性
  • 常量&变量
    • 数据对象可以拥有左值（存储单元|地址|容器）和右值（内容）
  • 全局量和局部量
  • 数据类型
    • 基本类型
    • 特殊类型
• 控制
  • 顺序，选择，循环（初始化，循环体，循环条件）
• 传输（赋值处理，数据的输入和输出）
  • 包括函数（定义，声明，调用）

汇编程序基本原理

• 面向特定计算机设计的符号化的程序设计语言，编写的源程序需要汇编翻译程序进行翻译。
• 语句
  • 指令语句-汇编后能被CPU直接识别与执行的操作 如 ADD,SUB和AND
    • 传送指令，算术运算指令，逻辑运算指令，移位指令，转移指令和处理机控制指令
  • 伪指令语句，在汇编源程序时完成一些工作 汇编后不产生机器代码
    • 所指示的操作是在源程序被汇编时完成的，指令语句的操作必须在运行时完成
  • 宏指令语句 多次重复使用的程序段定义为宏
• 工作原理 （将源程序翻译成对饮固定机器指令）
  • 经过两次扫描 ，第一次扫描创建一个符号表（初始化），第二次产生目标程序

编译程序基本原理

• 编译的过程6个部分
• 源程序
  • 1. 词法分析
  • 2. 语法分析
  • 3. 语义分析
  • 4. 中间码生成
  • 5. 代码优化
  • 6. 目标代码生成
• 生成目标代码

解释程序基本原理

• 解释程序的处理主要分为两个部分
  • 分析
    • 词法，语法，语义 生成中间代码**（语法树，后缀式[逆波兰式]，三地址代码）**
  • 解释
    • 对分析生成的中间代码进行解释执行

解释与编译程序的比较

• 效率低，灵活性强，可移植性强

数据结构

• 数据结构是存储，组织数据的方式
• 算法是操作数据结构的行为

线性结构

• 数组
  • 一维数组
  • 多维数组
• 链表
  • 线性表
  • 顺序表（数组）
  • 双向链表
  • 循环链表
  • 双向循环链表
• 栈（堆栈）后进先出（Last In First Out, LIFO）(受限表)
  • 顺序存储（空间优先）
  • 链式存储
• 队列 先进先出（First In First Out , FIFO）(受限表)
  • 顺序队列 链表（无限空间）
  • 循环队列 （有限空间）

矩阵和广义表

矩阵

• 科学与工程计算领域研究的数学对象，（应用点 二维数组）
• 特殊矩阵，会对相同元素进行压缩
• 稀疏矩阵，不进行压缩的矩阵

广义表（线性表的推广）

• 线性表的元素是结构上不可分的单元素，广义表的元素既可以是单元素，也可以是有结构的表
• 重要运算
  • 取表头
  • 取表尾 非空广义表的表尾必定是一个表
• 特点
  • 多层次结构
  • 元素可以是其他广义表
  • 可以为递归表