北京大学《计算概论》课件：第五讲-CPU内存基本工作原理.pdf

第五讲：第六章 CPU/内存基本工作原理 北京大学信息科学技术学院 2013年10月 本讲内容  计算机的数学理论模型－图灵机  CPU的内部结构和工作原理  主存储器及其与CPU之间的信息传输  指令系统  计算机程序的基本控制结构 计算机的数学理论模型－图灵机 可计算性 对于一个问题， 如果存在一个机械的过程 ， 当我们给定一个输入，这个过程能 够在有限步内终止并给出正确答案 ， 那么，这个问题就称为是可计算的/具有 可计算性。 计算机理论的发展历史  图灵研究了可计算性  提出了 图灵机 和 图灵机能解决的问题类  证明了 存在着图灵机无法解决的问题类  冯 ·诺伊曼给出了现代计算机的设计蓝图  提出了 数字计算机的组成原理和体系结构  对指令、指令周期、指令系统和存储式程序控制原理都 给出了明确的方案  库克（Stephen A.Cook ）研究了计算复杂性  有一些问题，虽然可计算，但随着问题规模的增加，就 连最快的计算机用几百年也不能结束计算 图灵机 （Turing Machine ）  1936年由英国数学家阿兰 ·图灵提出  一种抽象的计算模型  现代电子计算机的理论基础  基本思想：用机器来模拟人类用纸和笔进行数 学运算的过程  人用纸和笔进行数学运算的两种简单动作：  在纸上写下或擦除某个符号  把注意力从纸的一个位置移动到另一个位置  同时，人的下一步动作依赖于两个因素：  此人当前所关注的纸上某个位置的符号  此人当前的思维状态 图灵机的构成成分（1） 图灵机的  1. 一条无限长的纸带TAPE 符号表  纸带被划分为一个接一个的小方格  每个方格存储一个来自一个有限符号集合的符号  纸带的两端可以无限延伸 TAPE … … … b c d e f g … … u v w x y … … … 图灵机的构成成分（2）  2.一个读写头HEAD  能 读出当前位置的方格里的符号  能 在当前位置的方格里写入一个符号  能 向左、向右移动 HEAD  一次移动一个方格的宽度 向左移动 向右移动 … … … b c d e f g … … u v w x y … … … 图灵机的构成成分（3）  3.一个控制器CONTROL  一个状态寄存器REG 有限状态控制器  记录了图灵机的 当前状态  一个图灵机具有 有限数量的可能状态  一个控制规则表TABLE  规定了图灵机如何在不同的状态之间进行迁移/转换 CONTROL … … … b c d e f g … … u v w x y … … … 图灵机的运作方式 