第五讲-cpu内存基本工作原理

《第五讲-cpu内存基本工作原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五讲：第六章CPU/内存基本工作原理北京大学信息科学技术学院2013年10月本讲内容计算机的数学理论模型－图灵机CPU的内部结构和工作原理主存储器及其与CPU之间的信息传输指令系统计算机程序的基本控制结构计算机的数学理论模型－图灵机可计算性对于一个问题，如果存在一个机械的过程，当我们给定一个输入，这个过程能够在有限步内终止并给出正确答案，那么，这个问题就称为是可计算的/具有可计算性。计算机理论的发展历史图灵研究了可计算性提出了图灵机和图灵机能解决的问题类证明了存在着图灵机无法解决的问题类冯·诺伊曼给出了现代计算机的设计蓝图提出了数

2、字计算机的组成原理和体系结构对指令、指令周期、指令系统和存储式程序控制原理都给出了明确的方案库克（StephenA.Cook）研究了计算复杂性有一些问题，虽然可计算，但随着问题规模的增加，就连最快的计算机用几百年也不能结束计算图灵机（TuringMachine）1936年由英国数学家阿兰·图灵提出一种抽象的计算模型现代电子计算机的理论基础基本思想：用机器来模拟人类用纸和笔进行数学运算的过程人用纸和笔进行数学运算的两种简单动作：在纸上写下或擦除某个符号把注意力从纸的一个位置移动到另一个位置同时，人的下一步动作依赖于两个因素：此人当前所

3、关注的纸上某个位置的符号此人当前的思维状态图灵机的构成成分（1）1.一条无限长的纸带TAPE纸带被划分为一个接一个的小方格每个方格存储一个来自一个有限符号集合的符号纸带的两端可以无限延伸图灵机的符号表…bcdefg……uvwxy……………TAPE图灵机的构成成分（2）2.一个读写头HEAD能读出当前位置的方格里的符号能在当前位置的方格里写入一个符号能向左、向右移动一次移动一个方格的宽度…bcdefg……uvwxy……………HEAD向左移动向右移动图灵机的构成成分（3）3.一个控制器CONTROL一个状态寄存器REG记录了图灵机的当前

4、状态一个图灵机具有有限数量的可能状态一个控制规则表TABLE规定了图灵机如何在不同的状态之间进行迁移/转换…bcdefg……uvwxy……………CONTROL有限状态控制器图灵机的运作方式图灵机的每一步动作取决于四个因素控制器中的当前状态qi读写头的当前位置（在哪个方格上）当前位置的方格内存储的符号si控制规则表中的规则控制器根据qi、si、以及控制规则，决定：1.向当前方格内写入的符号2.读写头的移动方向（左移,右移,不动）3.控制器新的当前状态（START,……,HALT）停机状态启始状态控制规则表的结构当前状态当前方格中的符号

5、写入方格的符号读写头移动方向新的当前状态START………………………qisisi+1左移qi+1………………………HALT每一行存储了一条控制规则图灵机—实例1…………CONTROL当前状态＝START符号表：{0,1,*}状态集合：{START/开始,ADD/相加,CARRY/进位,OVERFLOW/溢出,RETURN/返回,HALT/停机}**101**请同学们观察这个图灵机的功能是什么…………CONTROL当前状态＝START**101**ID当前状态当前符号写入符号移动方向新的状态01START**左移ADD02ADD01

6、右移RETURN03ADD10左移CARRY04ADD**右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW**右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN**不动HALT控制规则表…………CONTROL当前状态＝ADD**101**ID当前状态当前符号写入符号移动方向新的状态01START**左移ADD02ADD01右移RETURN03ADD10左移CARRY0

7、4ADD**右移HALT05CARRY01右移RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW**右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN**不动HALT控制规则表…………CONTROL当前状态＝ADD**100**ID当前状态当前符号写入符号移动方向新的状态01START**左移ADD02ADD01右移RETURN03ADD10左移CARRY04ADD**右移HALT05CARRY01右移

8、RETURN06CARRY10左移CARRY07CARRY*1左移OVERFLOW08OVERFLOW**右移RETURN09RETURN00右移RETURN10RETURN11右移RETURN11RETURN**不动HA