计算思维导论2.ppt

《计算思维导论2.ppt》由会员分享，可在线阅读，更多相关《计算思维导论2.ppt（83页珍藏版）》请在麦多课文档分享上搜索。

1、第二章 计算系统的基本思维,内容提要： 2.1 理解0和1的思维 2.2 图灵机与冯诺依曼计算机 2.3 现代计算机,2.1 理解0和1的思维,用机器实现自动化计算要解决的几个问题： “数据”和“计算规则”的机器表示。 数据与计算规则的“自动存储” 计算规则的“自动执行” “数据”和“计算规则”的符号化 现实世界的任何事物，若要由计算系统进行计算，首先要将其语义符号化，进而进行基于符号的计算。 将符号赋予不同语义，则能计算不同的问题。,2.1 理解0和1的思维,为什么选择二进制符号体系 简单：二进制只有2个符号0、1，对应着自然界截然相反的两种状态。真、假，黑、白，正、负，高、低，通、断，。

2、最重要的是二进制运算系统容易实现。数字电路，触发器，运算器等。,2.1 理解0和1的思维,1、二进制与算术运算：数值信息的0、1表示二进制数制 逢2进1，借1当2，第 i 位的权值为2i。29282726252423222120 . 2-12-22-32-42-5 - 数位的权(1011110001 . 01011)2 - 二进制数= 1x29+0x28+1x27+1x26+1x25+1x24+0x23+0x22+0x21+1x20 +0x2-1+1x2-2+0x2-3+1x2-4+1x2-5= (753.37)10,2.1 理解0和1的思维,十进制数转换成二进制数：整数部分：除2取余小数部分

3、：乘2取整 八进制、十六进制与二进制间的转换。 二进制数的符号 二进制数的符号用0、1表示，0正，1负。 机器数的概念，由于位数的限制，机器数只能表示一定范围的数，超出此范围会“溢出”。,2.1 理解0和1的思维,2.1 理解0和1的思维,逻辑运算：0 假，1 真。 基本的逻辑运算：“或”、“与”、“非”、“异或” 或运算(OR)：双目运算符，全假时为假，其它为真。 与运算(AND)：双目运算符，全真时为真，其它为假。 非运算(NOT)：单目运算符，真变假，假变真。 异或运算(XOR)：双目运算符，不同为真，相同为假。,2.1 理解0和1的思维,数值运算 二进制加法运算规则二进制减法运算规则,

4、0 1 0 1- 0 - 0 - 1 - 10 1 1 0,2.1 理解0和1的思维,二进制乘、除法运算规则用加法规则构造减法、乘法和除法减去一个数等于加上该数的补码。乘法可理解为左移相加，除法则为右移相减。 结论：加法是计算机内的基本运算，有对应硬件实体。,2.1 理解0和1的思维,小数点表示：定点数与浮点数,2.1 理解0和1的思维,信息的度量单位 信息的度量单位是什么？ 信息的基本度量单位 bit 比特，1位二进制位，Byte 字节, 8位二进制位。1KB = 210字节 1MB = 210KB1GB = 210MB1TB = 210GB = 220MB1PB = 210TB = 230

5、MB1EB = 210PB = 240MB,2.1 理解0和1的思维,2、编码与符号运算：0/1与非数值信息编码的概念 1位二进制位有两种取值，0或1，可用来表示两种信息，如男、女，真、假，黑、白等。 当信息种类多于两种怎么办？ 使用多位二进制表示有限信息集合。如3位二进制包含如下编码：000、001、010、011、100、101、110、111。,2.1 理解0和1的思维,可以为这些编码指派不同的含义000 001 010 011 100 101 110 111专业1 专业2 专业3 专业4 专业5 专业6 专业7 专业8单位1 单位2 单位3 单位4 单位5 单位6 单位7 单位8 编码

6、：编码是以若干位数码或符号的不同组合来表示非数值性信息的方法，它是人为地将若干位数码或符号的每一种组合指定一种唯一的含义。,2.1 理解0和1的思维,编码的三个主要特征唯一性：每一种组合都有确定的唯一性的含义公共性：所有相关者都认同、遵守、使用这种编码易于记忆/便于识认性：有一定规律,2.1 理解0和1的思维,ASCII码-英文字母符号的编码 ASCII码是英文字母与符号的0/1型编码方法，是用7位二进制位0和1的不同组合表示10个数字、52个英文字母及一些特殊符号的编码方法，是信息交换标准编码。 ASCII码：American Standard Code for Information In

7、terchange,B7B6B5B4B3B2B1B00 x x x x x x x,0 0 1 1 0 0 0 1,0 1 0 0 1 1 1 0,“1”,“N”,2.1 理解0和1的思维,完整的ASCII码表,2.1 理解0和1的思维,ASCII编码的规律：每8位为一个字符，最高位为0 30H 39H: “0” “9” 41H 5AH: “A” “Z” 61H 7AH: “a” “z” 0AH: 换行符号LF 0DH: 回车符号CR,2.1 理解0和1的思维,汉字的编码 英文是拼写文字，只需要对基本字母编码。 汉字是图形文字，必须对每个汉字编码。 汉字有近50000个，8位二进制位不够，用1

8、6位。 汉字机内码：汉字在计算机内部采用汉字内码存储，汉字内码为两字节，且最高位均为1，区别于ASCII码。以汉字“大”为例：其机内码为：B4F3H二进制：1011 0100 1111 0011,2.1 理解0和1的思维,“大”,b7 b6 b5 b4 b3 b2 b1 b0,b7 b6 b5 b4 b3 b2 b1 b0,用0和1编码汉字,每个汉字在计算机内部由 2个字节表示,0 0 1 1 0 1 0 0,0 1 1 1 0 1 1 1,国标码,1 0 1 1 0 1 0 0,1 1 1 1 0 1 1 1,机内码,2.1 理解0和1的思维,汉字输入码：是用键盘上的字母符号编码每一汉字的编

9、码，它使人们通过键入字母符号代替键入汉字。,输入码有若干： 拼音码、字型码、区位码 ,“型”,拼音码： xing,双拼码： x；,其中,x表声母x,而；表韵母ing,五笔字型码： gajf,其中,g表字根“-”,a表开下的草字头,j表右侧立刀,f表下面土字,2.1 理解0和1的思维,汉字字形码：是用0和1编码无亮点和有亮点像素,形成汉字字形的一种编码。依据字形码通过显示器或打印机输出汉字。,2.1 理解0和1的思维,汉字处理过程：通过汉字外码输入，以汉字内码存储和处理，以汉字字形码输出。,“大”,oooooo11oooooooo oooooo11oooooooo oooooo11ooooooo

10、o oooooo11ooooo1oo 1111111111111111 oooooo11oooooooo oooooo11oooooooo oooooo11oooooooo oooooo11oooooooo oooooo111ooooooo ooooo11oo1oooooo oooo11oooo1ooooo ooo11ooooo11oooo ooo1ooooooo11ooo oo1ooooooooo111o 11ooooooooooo1oo,大,da,2.1 理解0和1的思维,还有哪些标准编码？ 扩展ASCII码：8位0,1型编码，最高位为0时为标准ASCII码；最高位为1时为扩展ASCII码

11、。 Unicode：是国际组织制定的可以容纳世界上所有文字和符号的字符编码方案。采用数字0-0x10FFFF来映射所有的字符(最多可以容纳1114112个字符)。具体实现时，再将前述唯一确定的码位按照不同的编码方案映射为相应的编码，有UTF-8、UTF-16、UTF-32等几种编码方案。,2.2 图灵机与冯诺依曼计算机,用机器实现自动化计算要解决的几个问题： “数据”和“计算规则”的机器表示。 数据与计算规则的“自动存储” 计算规则的“自动执行” 本节讨论后2个问题 数据与计算规则的“自动存储” 计算规则的“自动执行” 即计算机器的基本原理,2.2 图灵机与冯诺依曼计算机,1、图灵机模型英国人

12、图灵于上世纪30年代提出了图灵机模型，直观形象地说明了通用计算机器的工作原理，建立了指令、程序及通用机器执行程序的理论模型。 计算机界于1966年设立了最高荣誉奖：图灵奖。 后来，冯诺依曼根据这个模型设计出第一台实用的电子计算机器。,2.2 图灵机与冯诺依曼计算机,图灵机的基本思想 数据、指令、程序及程序/指令自动执行的基本思想。 输入数据被制成一串0和1的纸带，送入机器中。如00010000100011 机器可对输入纸带执行的基本动作包括：“翻转0为1”，或 “翻转1为0”, “前移一位”, “停止”等。 对基本动作的控制-指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表

13、示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变), 11表示“前移一位”, 00表示“停止”。,2.2 图灵机与冯诺依曼计算机,输入如何变为输出的控制可以用指令编写一个程序来完成, 如: 011110110111011100 .。 机器能够读取程序并按程序中指令的顺序读取指令。 读一条指令执行一条指令。由此实现自动计算。,2.2 图灵机与冯诺依曼计算机,2、冯诺依曼计算机 冯.诺伊曼计算机的基本思想：存储程序与程序控制 存储程序：将指令和数据以同等地位预先存于存储器中，可按地址寻访。 程序控制：机器从存储器中读取指令和数据，实现连续、自动执行。 注意：指

14、令和数据均采用二进制表示。,2.2 图灵机与冯诺依曼计算机,冯.诺伊曼计算机的基本构成 分为五大部件：运算器、控制器、存储器、输入设备和输出设备。 运算器：负责进行逻辑运算和算术运算。 控制器：负责读取、分析和执行指令。 存储器：存储指令和数据。 输入设备：负责将指令和数据输入计算机。 输出设备：将计算结果显示或打印出来。,2.2 图灵机与冯诺依曼计算机,以运算器为中心的结构：早期结构，大家都争夺控制权，各部件之间不能实现并行工作。,2.2 图灵机与冯诺依曼计算机,以存储器为中心的结构：目前结构，各部件之间可实现并行工作。,2.2 图灵机与冯诺依曼计算机,以运算器为中心结构工作举例：,2.2

15、图灵机与冯诺依曼计算机,过程描述：,(1)启动控制器工作,(2)发送第1条指令地址,(3)取出指令并分析指令,(4)执行指令：发送操作数x所在地址,(5)执行指令：取出操作数x,(10)执行指令：通知运算器计算a乘x,(11)继续后续指令的取指、执行,(6)发送下一条指令地址,(7)取出指令并分析指令,(8)执行指令：发送操作数a所在地址,(9)执行指令：取出操作数a,2.2 图灵机与冯诺依曼计算机,计算机的基本部件 CPU：中央处理单元(Central Process Unit)，将运算器和控制器集成在一块芯片上，形成微处理器。 CPU、主存储器、I/O设备及总线成为现代计算机的四大核心部件

16、。 在现代计算机中，一个微处理器(芯片)可能包含多个CPU，即多核。,2.2 图灵机与冯诺依曼计算机,3、存储器：可按地址自动存取信息的部件 存储器的概念结构图,2.2 图灵机与冯诺依曼计算机,存储器由存储矩阵、地址译码器、输入/出缓冲器组成。 存储矩阵：由若干存储单元构成，每个存储单元通常可存储8位二进制数据，即每个存储单元为一个字节。 地址译码器：每个存储单元由一条地址线( Wi )控制其读写，当其有效时，对应存储单元的内容可读出或写入，否则不可访问。每个存储单元的地址编码：由地址编码线An-1 A0决定，每个地址编码An-1 A0译出其对应的地址线Wi 。n 位地址编码可控制2n个存储单

17、元，即存储容量为2n 。,2.2 图灵机与冯诺依曼计算机,输入/输出缓冲器：暂存将要写入或已经读出的数据，并决定是进行写入还是读出操作。三态控制线：读、写、高阻,2.2 图灵机与冯诺依曼计算机,4、机器指令与机器级程序与算法 若要由计算系统自动求解问题，就要用计算系统所具有的设施及可理解和执行的规则来编写算法和程序。 算法：求解问题的操作规则及步骤。 机器级算法必须精炼，哪怕节省一步都是重要改进。,2.2 图灵机与冯诺依曼计算机,2.2 图灵机与冯诺依曼计算机,机器指令：算法需要用CPU可理解和执行的指令来编写。机器指令是CPU可直接分析并执行的指令，一般由0、1编码表示。 机器指令通常分为操

18、作码和地址码。 机器级程序：832+23+6,2.2 图灵机与冯诺依曼计算机,2.2 图灵机与冯诺依曼计算机,5、机器级程序的存储与执行 机器如何理解和执行程序？ 运算器和控制器 运算器：运算部件和寄存器。基本的运算部件只能进行简单的二进制算术、逻辑运算和移位操作。 控制器：指令寄存器IR、程序计数器PC、时钟与节拍发生器、信号发生器。,2.2 图灵机与冯诺依曼计算机,指令的执行 运算器和控制器 不同的指令，对应着一组不同的电信号。 这些电信号在时钟与节拍的控制下按次序产生与传输。 一条指令占用一个或多个机器周期，一个机器周期又分为多个节拍。 最小的时间间隔单位：时钟周期 计算机的主频：时钟周

19、期,2.2 图灵机与冯诺依曼计算机,时钟周期、节拍与机器周期,第一节拍： 将PC中的地址发往存储器。 由信号发生器发出一信号通知存储器工作,第二节拍： 存储器进行译码，找到对应存储单元，通 过输出缓冲器输出内容。 信号发生器发出一信号IR接收该内容。,第三节拍： 指令码000001控制产生信号，PC加1指向 下一条指令地址，同时将指令中的地址码 发往存储器。,第四节拍： 存储器进行译码，找到对应存储单元，通 过输出缓冲器输出内容。 同时指令码发出控制信号使寄存器R0接收。,程序中指令的逐条执行,2.3 现代计算机,1、现代计算机的构成 现代计算机系统由硬件、软件、数据和网络构成。,2.3 现代

20、计算机,计算机硬件由主机和外部设备两大部分构成 主机 核心部件：CPU、存储器。 主电路板与接口电路板。 外部设备：输入/输出设备 输入设备：鼠标、键盘、麦克风等。 输出设备：显示器、打印机、音箱等。 输入/输出设备：触摸屏。 外部存储器：硬盘、光盘、U盘。,2.3 现代计算机,计算机软件 各种软件研制的目的：扩大计算机的功能，方便使用或专为解决某类问题。系统软件、应用软件。 系统软件：管理、控制、维护计算机，编辑、制作程序，维护计算机的工具软件。 操作系统、编程环境、数据库系统等。 应用软件：用于解决各类实际问题。,2.3 现代计算机,2、存储体系：不同性能资源的组合优化思维 重要概念：程序

21、必须装载进内存，才能被CPU执行。 数据自动存储能力是衡量计算机的重要指标。 存储容量越大越好。 存取速度越快越好。 保存时间越长越好。 价格越低越好。,2.3 现代计算机,现代计算机的存储体系中包含了各种性能的存储器。 寄存器：存取速度最快，与CPU同步。 RAM：随机存储器，可按地址访问，内存。 ROM：只读存储器，用来保存机器级程序。 硬盘：采用磁性材料制作的大容量存储器。 光盘(CD、DVD)，U盘等。,2.3 现代计算机,内存：采用半导体材料制作,内存：RAM/ROM 地址：存储单元 1、2、4或8个字节,2.3 现代计算机,外存,外存：硬盘/软盘 盘面:磁道:扇区 一个扇区存放51

22、2个字节。,2.3 现代计算机,存储体系：不同性能资源的组合优化,内存与外存的区别？,2.3 现代计算机,3、为什么要有操作系统：硬件功能扩展的基本思维 存储体系环境下，程序怎样被执行?,2.3 现代计算机,操作系统：控制和管理计算机系统各种资源(硬件资源、软件资源和信息资源)、合理组织计算机系统工作流程、提供用户与计算机之间接口以解释用户对机器的各种操作需求并完成这些操作的一组程序集合，是最基本、最重要的系统软件。 操作系统的作用： 操作系统是用户与计算机硬件之间的接口。 操作系统为用户提供了虚拟机(Virtual Machine)。 操作系统是计算机系统的资源管理者,2.3 现代计算机,操

23、作系统是一组“管理各种资源以便执行应用程序”的程序。,磁盘管理-管理磁盘信息的读写,内存管理-管理内存空间的分配与回收,CPU管理-调度CPU去执行哪一个程序,2.3 现代计算机,4、化整为零的基本思维：磁盘与文件系统 磁盘与文件管理是存储体系的重要内容，是操作系统对硬件功能的重要扩展。 文件与信息： 信息被操作系统组织成文件。 文件是操作系统管理信息的基本单位。 使用者只需关心文件名和内容，其它交给操作系统。,2.3 现代计算机,用户,信息/程序,文件A,文件A,文件B,文件C,外存(硬盘/软盘/光盘),2.3 现代计算机,磁盘信息的组织：磁盘簇块与扇区 磁盘物理结构：盘面、磁道、扇区。 簇

24、块：操作系统将磁盘组织成簇块 (若干连续的扇区)，以簇块为单位与内存交换信息。 文件中的信息按簇块大小被分割，然后写入磁盘中的簇块。,2.3 现代计算机,文件分配表（FAT） 磁盘上记录文件存储的簇块之间衔接关系的信息区域，二维表格。 磁盘上有多少簇块，文件分配表就有多少项。 FAT表项的内容指出了该簇块的下一簇块的编号。,2.3 现代计算机,目录与文件夹 是磁盘上记录文件名、文件大小、文件更新时间等文件属性的信息区域。 相当于文件清单，对应每个文件名，目录中都会记录它在磁盘上存储的第一个磁盘簇块编号。,2.3 现代计算机,磁盘上的重要信息区域 保留扇区区域、文件分配表区域、根目录区域、数据区

25、域。 上述信息区域的建立通过磁盘格式化完成。 磁盘的第一个扇区被称为引导扇区。 磁盘与文件管理体现的是一种化整为零的基本思维。,2.3 现代计算机,5、内存管理与处理机管理问题：在现代计算机及存储体系中，程序如何执行？ 情况1：单CPU运行单一程序。 情况2：单CPU同时运行多个程序。 情况3：多CPU运行单个程序。 原则：程序必须装入内存，才能被CPU执行。,2.3 现代计算机,内存管理： 内存空间管理 内存空间分配 内存与外存信息的自动交换 内存空间回收,内存被分成不同的块(或页)，一般而言，内存的一页和磁盘的一块相等或为其倍数。,2.3 现代计算机,程序与进程： 以文件形式存储在磁盘上的

26、程序文件称为“程序”。 可运行程序文件在操作系统的管理下被装入内存，形成“进程”。 进程除程序外，还包含描述信息，便于操作系统管理。,内存储器,分工：操作系统对内存的管理与控制-使用哪一段内存,内存空间分配,内存回收,内存与外存信息的自动交换,内存空间管理,进程1,000001段内存,运算器,控制器,CPU,状态与管控,2.3 现代计算机,处理机管理 内存中待执行程序段落的地址送控制器的PC(程序计数器) 内存中的多个程序，执行哪一个程序? 程序执行切换中的状态/环境保护问题,单CPU分时调度-进程多CPU并行调度-线程,2.3 现代计算机,任务与作业： 任务：大粒度工作，一个应用程序的完整的

27、执行，一个任务由多个进程来完成。 作业：小粒度工作，不同作业由不同的进程来完成。,2.3 现代计算机,程序,进程,作业,2.3 现代计算机,操作系统进程和应用程序进程 操作系统的进程：为使应用程序顺利执行而做的辅助性管理性工作的进程。操作系统的进程也存储在内存中，也需要调度CPU来执行；CPU在操作系统进程和多个应用程序进程之间来回切换。 应用程序的进程：应用程序本身的进程。,2.3 现代计算机,进程管理,2.3 现代计算机,6、现代计算机工作过程 计算机是怎样装载操作系统的?,引导程序,基本输入输出部分,磁盘文件管理部分,命令解释器,ROM BIOS,用户键入命令,内部命令 直接执行,外部命

28、令需要找到程序并装载入内存,外部命令 执行,2.3 现代计算机,操作系统的启动和关闭,2.3 现代计算机,7、现代计算机的发展CPU管理-分时：一台主机一个CPU执行多个程序。,t,t,CPU,作业1,作业2,作业3,作业4,操作系统管理着一时间轮盘；按照时间轮盘的时间分区，轮流让CPU执行若干个程序。由于时间分区足够小，所以每个作业的用户都认为自己独占着CPU,执行,执行,时间分区,2.3 现代计算机,CPU管理-并行：一台主机多个CPU执行一个程序,作业的第1部分,作业的第2部分,作业的第3部分,作业的拆分与合并,CPU1,CPU2,CPU3,CPU4,作业,操作系统将一个作业分解成若干个

29、可并行执行的小作业，由不同的CPU予以执行。其中一个CPU负责作业的拆分与合并工作，如CPU1, 如此多CPU并行完成一个作业。,2.3 现代计算机,CPU管理-分布：网络中多台主机多个CPU执行一个任务。,作业的拆分与合并,CPU,作业,一个作业被一台机器的操作系统拆分成若干可分布与并行执行的小作业，通过网络传送到不同的机器，由不同机器的操作系统控制其CPU予以执行。如此网络上，多台计算机可并行完成一个作业。,作业的第1部分,作业的第2部分,作业的第3部分,网络传输,网络传输,网络传输,网络传输,通用计算环境的进化,计算系统发展之重要功劳在于“软件”,软件促进环境发展, 软件也在随环境的变化而发展,云计算(Cloud),云操作系统(Cloud Operating System): 跨物理机管理,OS:进程,Operation,Prog1 Progn,OS,Operation,Prog1 Progn,OS,Operation,Prog,OS,Operation,Prog1 Progn,不同性能的虚拟机：(1)CPU数目 (2)内存容量 (3)外存容量 (4)网络带宽,物理机：CPU(h个);内存(p*qGB);外存(n*mGB),