第四讲：计算机的内部存储与处理北京大学 信息科学技术学院 周明辉 2009年10月序言n前讲问题n将0.6转化成二进制数n存储器的金字塔结构层次？n输入/输出的流程nAbout Think 莱布尼兹的梦想：可以推演 出一切真理的语言nEngines of logic(逻辑的引擎)本讲内容n计算机的数学理论模型图灵机nCPU的内部结构和工作原理n主存储器及其与CPU之间的信息传输n指令系统（略）n计算机程序的基本控制结构nVC 6.0 编程环境n编程网格环境计算机的数学理论模型图灵机可计算性对于一个问题，如果存在一个机械的过程， 当我们给定一个输入，这个过程能 够在有限步内终止并给出正确答案， 那么，这个问题就称为是可计算的/具有 可计算性。计算机理论的发展历史n图灵 研究了 可计算性n提出了 图灵机 和 图灵机能解决的问题类n证明了 存在着图灵机无法解决的问题类n冯诺伊曼 给出了 现代计算机的设计蓝图n提出了 数字计算机的组成原理和体系结构n对指令、指令周期、指令系统和存储式程序控制原理都 给出了明确的方案n库克（Stephen A.Cook ）研究了 计算复杂性n有一些问题，虽然可计算，但随着问题规模的增加，就 连最快的计算机用几百年也不能结束计算图灵机（Turing Machine）n1936年由 英国数学家 阿兰图灵 提出n一种抽象的计算模型n现代电子计算机的理论基础n基本思想：用 机器 来 模拟 人类 用 纸和笔 进行 数 学运算的过程n人用纸和笔进行数学运算的两种简单动作：n在纸上写下或擦除某个符号n把注意力从纸的一个位置移动到另一个位置n同时，人的下一步动作依赖于两个因素：n此人当前所关注的纸上某个位置的符号n此人当前的思维状态图灵机的构成成分（1）n1. 一条无限长的纸带 TAPEn纸带被划分为一个接一个的小方格n每个方格存储一个来自一个有限符号集合的符号n纸带的两端可以无限延伸图灵机的 符号表bcdefguvwxy TAPE图灵机的构成成分（2）n2.一个读写头 HEADn能 读出当前位置的方格里的符号n能 在当前位置的方格里写入一个符号n能 向左、向右移动n一次移动一个方格的宽度bcdefguvwxy HEAD向左移动向右移动图灵机的构成成分（3）n3.一个控制器 CONTROLn一个状态寄存器 REGn记录了图灵机的当前状态n一个图灵机具有 有限数量的可能状态n一个控制规则表 TABLEn规定了图灵机如何在不同的状态之间进行迁移/转换bcdefguvwxy CONTROL有限状态控制器图灵机的运作方式n图灵机的每一步动作取决于四个因素n控制器中的当前状态 qin读写头的当前位置（在哪个方格上）n当前位置的方格内存储的符号 sin控制规则表中的规则控制器 根据 qi、si、以及控制规则，决定：1.向当前方格内写入的符号 2.读写头的移动方向（左移, 右移, 不动） 3.控制器新的当前状态（START, , HALT）停机状态启始状态控制规则表的结构当前状态当前方格 中的符号写入方格 的符号读写头 移动方向新的 当前状态STARTqisisi+1左移qi+1HALT每一行存储了一条控制规则图灵机实例1 CONTROL当前状态STARTn符号表 ： 0, 1, * n状态集合：n START/开始, ADD/相加, CARRY/进位, OVERFLOW/溢出, RETURN/返回, HALT/停机 *101*请同学们观察这 个图灵机的功能 是什么 CONTROL当前状态START*101*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态ADD*101*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态ADD*100*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态CARRY*100*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态CARRY*110*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态RETURN*110*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态RETURN*110*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态RETURN*110*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表 CONTROL当前状态HALT*110*ID当前状态当前符号写入符号移动方 向新的状态01START*左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD*右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW*右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN*不动HALT控制规则表图灵机实例1n这个图灵机的功能是什么？f(x) = x + 1CPU的内部结构和工作原理CPU 中央处理器nCentral Processing Unitn微型/个人计算机的CPU又被称为：nMPU（Micro Processor Unit）微处理器n计算机系统中的核心硬件设备n主要功能：执行程序n与其它部件协同工作CPU内存显卡CPU的内部结构算术逻辑运算器程序控制器寄存器组中断处理器CPU内部总线CPU的内部结构 寄存器组n由 一组寄存器 组成的 高速存储单元n用于 暂时存放 运算数据 或 其它信息n整数类型 的 操作数 或 运算结果n浮点数类型 的 操作数 或 运算结果n指令n指令地址n各种内部标志信息存取速度CPU寄存器CPU的内部结构 程序控制器nProgram Control Unit，CPU的控制中心n分析/解释 指令n根据 分析/解释 结果 向 其它部件 发出命令n控制CPU的工作进度和工作方式n具体而言，当一条指令进入CPU后，程序控制器： 1. 分析/解释该指令的编码内容； 2. 确定为执行该指令应该完成的动作； 3. 确定指令相关的参数；例如：对于一个“加法指令”，需要确定两 个被加数的地址 4. 将 所需的数据 从 主存储器 读取到 CPU的寄存器中； 5. 要求 算术逻辑运算器 进行相关的运算动作； 6. 指示 算术逻辑运算器 将 运算结果 放入 寄存器 或 主存储器 中。CPU的内部结构 算术逻辑运算器nArithmetic Logical Unit (ALU),主要进行算术运算和逻辑运算n加法指令的例子 1.一条加法指令（其中包含了两个被加数/操作数的地址） 进入CPU； 2.程序控制器 分析该指令，判断两个操作数是在寄存器内 ，还是在主存内； 3.如果在主存内，程序控制器 从主存内读入操作数； 4.程序控制器 将 加法运算 提交给 ALU; 5.ALU 进行加法运算； 6.ALU 根据程序控制器 的指示，将运算结果存放到寄存器 或主存中。CPU的内部结构 中断处理器n问题背景：n在CPU执行一般程序运算的过程中，如何处理紧急出现的 事件？比如：鼠标移动事件n发生一个紧急事件 触发一个中断信号n中断信号的处理：n当发现中断信号后，程序控制器 暂停正在运行的程序， 保存该程序的运行现场（CPU内的各种状态信息）；n程序控制器 根据中断信号的编码，从特定位置启动 中断 处理程序（由操作系统提供）；n中断处理程序 运行完毕后，程序控制器 恢复被暂停的程 序。CPU的内部结构 中断处理器n中断信号的产生：n各种软硬件，比如：鼠标、键盘、其它外设n中断信号的接收：n中断处理器 负责 中断信号的接收，并将中断信号的编码 、中断处理程序的起始地址 传给 程序控制器n中断信号的检测n程序控制器 在每条指令执行完毕后，都会检测 是否出现 了新的中断信号CPU的主要性能指标n工作主频