@guoxs 2015-10-02T23:06:01.000000Z 字数 7339 阅读 9012

计算机思维与系统

计算机导论

计算机思维与系统

1、0与1的思维

语义符号化 → 符号计算化 → 计算0(和)1化 → 0(和) 1自动化 → 分层构造化 → 构造集成化；

1.2 进位制

数值性信息可以用进位制表示。
进位制：用数码和带有权值的数位来表示有大小关系的数值性信息的表示方法。

非数值性信息可以用编码表示。
编码：编码是以若干位数码或符号的不同组合来表示非数值性信息的方法，它是人为地将若干位数码或符号的每一种组合指定一种唯一的含义。

ASCII码----英文字母符号的编码
ASCII码是英文字母与符号的0,1型编码方法，是用7位0和１的不同组合来表示10个数字、26个英文大写字母、26个英文小写字母及其一些特殊符号的编码方法，是信息交换的标准编码。

ASCII码: American Standard Code for Information Interchange

信息	存储	解析规则
We are students	01010111 01100101 00100000 01100001 01110010 01100101 00100000 01110011 01110100 01110101 01100100 01100101 01101110 01110100 01110011	0/1串按8位分隔一个字符，查找ASCII码表映射成相应符号

ACSII码

汉字的编码
汉字内码：汉字在计算机内部采用汉字内码存储，汉字内码是一两字节且最高位均为1的0,1型编码。

用0和1编码汉字,每个汉字在计算机内部由2个字节表示
b7 b6 b5 b4 b3 b2 b1 b0 b7 b6 b5 b4 b3 b2 b1 b0

汉字输入码是用键盘上的字母符号编码每一汉字的编码,它使人们通过键入字母符号代替键入汉字。

输入码有若干：拼音码、字型码、区位码……
汉字字形码是用0和1编码无亮点和有亮点像素,形成汉字字形的一种编码。依据字形码通过显示器或打印机输出汉字。
用0和1编码无亮点和有亮点形成字形信息,便于显示。汉字字形码是一种字模点阵码。也有不同的处理汉字点阵信息的编码，如向量编码等。

oooooo11oooooooo
oooooo11oooooooo
oooooo11oooooooo
oooooo11ooooo1oo
1111111111111111
oooooo11oooooooo
oooooo11oooooooo
oooooo11oooooooo
oooooo11oooooooo
oooooo111ooooooo
ooooo11oo1oooooo
oooo11oooo1ooooo
ooo11ooooo11oooo
ooo1ooooooo11ooo
oo1ooooooooo111o
11ooooooooooo1oo

汉字处理过程: 通过汉字外码输入,以汉字内码存储,以汉字字形码输出

2、基本逻辑运算

“与”运算(AND): 当X和Y都为真时, X AND Y也为真; 其他情况, X AND Y均为假。有0为0 ，全1为1
“或”运算(OR): 当X和Y都为假时, X OR Y也为假; 其他情况, X OR Y均为真。有1为1，全0为0
“非”运算(NOT): 当X为真时, NOT X为假;当X为假时, NOT X为真。非0则1，非1则0
“异或”运算(XOR): 当X和Y都为真或都为假时, X XOR Y为假; 否则, X XOR Y为真。相同为0，不同为1

2.1 机器数的原码、反码和补码表示规则

原码、反码和补码

基于二进制的算术计算
对于 $A_i + B_i = C_{i+1}S_i$

不 考 虑 进 位 {S i = A i X O R B i C i + 1 = A i A N D B i

$不考虑进位 \begin{cases} S_i = A_i \mathtt{XOR} B_i \\ C_{i+1}= A_i \mathtt{AND} B_i \end{cases}$

考 虑 进 位 {S i = (A i X O R B i) X O R C i C i + 1 = ((A i X O R B i) A N D C i) O R (A i A N D B i)

$考虑进位 \begin{cases} S_i = (A_i \mathtt{XOR} B_i) \mathtt{XOR} C_i \\ C_{i+1}= ((A_i \mathtt{XOR} B_i) \mathtt{AND} C_i) \mathtt{OR} (A_i \mathtt{AND} B_i) \end{cases}$

实现0和1的基本元器件: 电信号和继电器开关
数字信号：高电平为1, 低电平为0

用二极管、三极管可实现基本的集成电路: 与门、或门和非门

基本门电路的符号表示及其特性
与门电路：是实现逻辑与运算的集成电路，即：只有当两个输入端为高电平(1)时，则输出端为高电平(1)；否则，输出端为低电平(0)。

或门电路：是实现逻辑或运算的集成电路，即：只有当两个输入端为低电平(0)时，则输出端为低电平(0)；否则，输出端为高电平(1)。

非门电路：是实现逻辑非运算的集成电路，即：当输入端为高电平(1)时，则输出端为低电平(0)；输入端为低电平(0)时，则输出端为高电平(1)。

异或门电路：是实现逻辑异或运算的集成电路，即：当两个输入端同为高电平(1)或同为低电平(0)时，则输出端为低电平(0)；否则，输出端为高电平(1)。

基于门电路的复杂组合逻辑电路
一位加法器

多位加法器：
算术式
电路组成：

复杂部件的硬件实现(芯片、主板)
微处理器芯片即是复杂组合逻辑集成在一块板上并封装而成的电路:

从Intel4004在12平方毫米的芯片上集成了2250颗晶体管 -> 到Pentium 4处理器内建了4200万颗晶体管，以及采用0.18微米的电路 -> 再到英特尔的45纳米Core 2至尊/至强四核处理器上装载了8.2亿颗晶体管。

总结

3、电子自动计算与器件发展

3.1 电子自动计算

3.1.1 计算分类：

简单计算I：数据计算，计算规则，应用计算规则进行计算并获得计算结果
复杂计算II：**f(x)，函数，计算规则及其简化计算方法，便于人应用规则进行计算，获得计算结果
**复杂计算III：如丢番图方程，判定，计算规则，人可能无法完成但却可由机器自动完成，借助于机器获得计算结果

3.1.2 自动计算要解决的问题

“数据”的表示
“计算规则”的表示：程序
数据与计算规则的“自动存储”
计算规则的“自动执行”

3.1.3 计算机发展史

① 帕斯卡与帕斯卡机----(准)第一台机械计算机

Blaise Pascal (1623～1662)
1642年研制成功一种齿轮式计算机器

帕斯卡机的意义：它告诉人们“用纯机械装置可代替人的思维和记忆”。开辟了自动计算的道路。

② 莱布尼茨

Gottfried Wilhelm Leibniz (1646～1716)，德国数学家。
莱布尼茨机的意义：连续重复自动执行。
提出了二进制数及其计算规则；
数理逻辑的创始人

③ 其他重要工作
1834年：巴贝奇(Charles Babbage)，分析机的概念----可执行程序的机器。
1805 年：杰卡德(J.Jacquard)，打孔卡，实践了输入手段问题。
1854年：布尔创立布尔代数，为数字计算机的电路设计提供了理论基础。
.....

3.1.4 电子自动计算-元器件

① 电子管时代的计算机器

冯.诺伊曼(Von Neumann)电子计算机EDVAC问世
将运算和存储分离，运算速度却比拥有18000个电子管的“ENIAC”提高了10倍
结构上的创新：“冯.诺伊曼计算机”。

② 晶体管时代的计算机器

③ 集成电路时代的计算机器

④ 超大规模集成电路(VLSI)时代的计算机器

发展趋势

体积越来越小；
可靠性越来越高；
电路规模越来越大；
速度越来越快；
功能越来越强大；

3.2 计算机硬件发展

计算机系统要解决的几个问题：

控制与计算 —— 微处理器
输入
输出
永久储存与临时储存

3.2.1 微处理器的发展

字长： 8位 → 16位 → 32位 → 64位
主频：几MHz → 几百MHz → 几GHz
晶体管数量：几万 → 几百万 → 几亿颗
功能/规模：微处理器微处理器+协处理器(浮点运算) → 微处理器+图形处理单元GPU → 微处理器+3D处理器+多媒体处理器 → 多核微处理器

微处理器发展

3.2.2 储存设备的发展

汞延迟线
磁带、磁芯、磁鼓存储
半导体存储（ROM/RAM）
磁盘存储（硬盘和软盘）
光盘存储（CD-ROM,CD,R/W,DVD）
FlashRAM
USB Removable disk
固态硬盘
纳米存储/量子存储

发展趋势：

体积越来越小
容量越来越大
访问速度越来越快
可靠性越来越高
功耗越来越低
持久性越来越好

3.2.3 输入设备的发展

穿孔纸带（0/1输入）
键盘输入（符号输入）
鼠标输入（点输入）
感知输入（接触性感知输入、非接触性感知输入）

3.2.4 输出设备的发展

输出设备(显示器)
CRT：阴极射线管(模拟显示器：黑白与彩色)
CRT: 字符发生器(向量式模拟显示器: 输出字符)
CRT: 数字光栅扫描显示器(基于内存的显示: 输出图形)
数字显示器：高清图形(液晶、等离子技术)
D显示器：3维图形

发展趋势：

分辨率越来越高
颜色越来越逼真
显示速度越来越快(屏幕刷新速度和图形处理速度)
越来越薄，越清晰
可视角度越来越接近平角

4、图灵机

图灵机认为的计算：

所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的变换过程。

图灵机的计算

图灵机的思想：
是关于数据、指令、程序及程序/指令自动执行的基本思想。

输入被制成一串0和1的纸带，送入机器中----数据。如00010000100011…
机器可对输入纸带执行的基本动作包括：“翻转0为1”，或“翻转1为0”, “前移一位”, “停止”。
对基本动作的控制----指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变), 11表示“前移一位”, 00表示“停止”。
输入如何变为输出的控制可以用指令编写一个程序来完成, 如: 011110110111011100…
机器能够读取程序，按程序中的指令顺序读取指令，读一条指令执行一条指令。由此实现自动计算。

图灵机模型

图灵机模型

几点结论：
(1) 图灵机是一种思想模型，它由一个控制器(有限状态转换器)，一条可无限延伸的带子和一个在带子上左右移动的读写头构成。
(2) 程序是五元组形式的指令集。其定义了机器在一个特定状态q下从方格中读入一个特定字符X时所采取的动作为在该方格中写入符号Y, 然后向右移一格R(或向左移一格L或不移动N),同时将机器状态设为p供下一条指令使用。
(3)图灵机模型被认为是计算机的基本理论模型----计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种离散的、有穷的、构造性的问题求解思路，一个问题的求解可以通过构造其图灵机(即程序)来解决。
(4)图灵认为：凡是能用算法方法解决的问题也一定能用图灵机解决;凡是图灵机解决不了的问题任何算法也解决不了----图灵可计算性问题。

图灵机模型示例(注:(q,X,Y,R(或L或N),p), 状态图中圆圈内的是状态，箭线上的是）

图灵机模型示例

5、机器级程序及其执行

一台简单的计算机

程序被执行的过程：

基本思维：机器级算法与程序 → 机器指令与指令系统 → 存储器 → 存储程序 → 运算器与控制器 → 机器级程序的执行；
算法程序化 → 程序指令化 → 指令存储化 → 执行信号化

5.3 冯.诺依曼(Von.Neumann)计算机

1944~1945年间，冯.诺伊曼提出“存储程序”的计算机设计思想，并进行了实践，现代计算机普遍来讲属于冯.诺伊曼机体系。

冯.诺伊曼机的基本思想：

运算和存储分离
存储程序：指令和数据以同等地位事先存于存储器,可按地址寻访, 连续自动执行。
五大部件构成：运算器、控制器、存储器、输入设备和输出设备
指令和数据用二进制表示，指令由操作码和地址码组成
以运算器为中心，控制器负责解释指令，运算器负责执行指令

以运算器为中心的冯.诺依曼计算机构成图:

以存储器为中心的现代计算机构成图:

同样是五个部件，以不同的结构来连接，便体现了不同的性能----这就是“系统”：强调“结构”，强调部件连接后的整体性、协同性。

冯.诺依曼计算机的工作原理：

计算机基本部件
CPU：中央处理单元(Central Process Unit)，将运算器和控制器集成在一块芯片上，形成微处理器。
CPU、主存储器、I/O设备及总线成为现代计算机的四大核心部件。
现代计算机里面，一个微处理器(芯片)可能包含多个CPU，即多核.

5.4 存储器的工作原理

存储器的基本结构：

存储器内部的实现示例
存储矩阵
① 当地址线和数据线间连接有二极管时，则存储的是1，否则，存储的是0
② 当地址线和数据线间连接有二极管时，由地址线决定其是输出1或0，即：当地址线为高电平时，则输出1，而当地址线为低电平时，则输出0；
③ 没有连接的，则不受地址线影响，始终输出低电平0；
存储矩阵
用多个存储器芯片可搭建容量更大的存储器：
半导体存储器芯片示例
不过，存储器扩展要解决的问题是：地址编码空间，储存字长

5.5 机器指令与机器级程序

计算机的构成
算法---从冯.诺依曼计算机的角度
可在机器上执行的求解问题的操作规则及步骤,被称为可执行的算法。
计算的步骤
计算过程
机器指令：

用机器指令表达算法：

将机器级程序和数据装载进存储器中?

高级语言程序的示例
计算ax2+bx+c，其中a,x,b,c是变量。
变量的地址是由编译程序在编译过程中自动分配的，也即是说编译器根据当时编译的情况，分配a,x,b,c为8号，9号，10号，11号存储单元，并产生上述的机器指令程序
C示例

5.6 机器级程序的执行机制

运算器构造：

控制器构造：

存储器构造：

指令的执行机制
指令执行

不同的指令，由一组不同的电信号构成
同一指令的电信号在时钟与节拍的控制下按次序产生与传输
一条指令占用一个或多个机器周期，一个机器周期又分为多个节拍
最小的时间区隔单位--时钟周期

时针周期
机器的“主频”：

计算机各部件内部的简单构成关系
组成关系

5.7 机器级程序的执行过程模拟

(1)程序和数据已经装入存储器中如何执行呢?
程序执行1
(2)第1条指令的读取
程序执行2
(3)第一条指令的执行
程序执行3
(4)第2条指令的读取
程序执行4
(5)第2条指令的执行
程序执行5
程序执行6
(4)其他指令的执行
程序执行7

小结

6、操作系统

现代计算机系统的工作思维：
存储体系 → 磁盘存取 → 操作系统 → 作业与进程 → 程序执行的管理与控制；
资源组合利用体系化、管理分工合作协同化、外存程序内存进程化、硬件不足功能软件化
现代计算机1

6.1 现代计算机的存储体系

冯.诺依曼计算机解决了“程序装载在内存，便可被CPU执行”的问题，但是，对于永久存储、存储容量、存储速度、存储器价格问题却没有很好的解决。
现代计算机将存储体系分离，高速内存，大容量的外存。

不同性能资源的组合优化：

存储体系需要一个资源管理者，那就是操作系统。
存储体系2

6.2 操作系统对计算机资源的分工-合作与协同管理思想

操作系统(Operating System:OS)是控制和管理计算机系统各种资源(硬件资源、软件资源和信息资源)、合理组织计算机系统工作流程、提供用户与计算机之间接口以解释用户对机器的各种操作需求并完成这些操作的一组程序集合，是最基本、最重要的系统软件。
操作系统的作用：

操作系统是用户与计算机硬件之间的接口。
操作系统为用户提供了虚拟机(Virtual Machine)。
操作系统是计算机系统的资源管理者。

操作系统是一组“管理各种资源以便执行应用程序”的程序：
(1)分工。独立管理复杂环境中的每个部件。

(2)合作。以任务为驱动，中心任务就是“让计算机或者说CPU执行存储在外存上的程序”,各部件合作完成该任务。
(3)协同。当基本解决后，关键就是协同，“合作”和“同步”,“自动化”及“最优化”。

$\color{red}{分工-合作-协同：是化简复杂问题，进行复杂问题求解的重要思维}$

6.3 操作系统对几种资源的分工管理

操作系统是如何管理磁盘的?
化整为零，还零为整

磁盘空间的管理：
文件的第一部分位置写在文件夹（目录）中，而之后的部分都写着下一部分的地址。这些地址组成文件分配表（FAT）。
存储管理

磁盘的四个主要区域：保留扇区、文件分配表区域、根目录区域、数据区域

计算机病毒攻击目标

内存管理
主要内容：
- 内存空间管理
- 内存空间分配
- 内存与外存信息的自动交换
- 内存空间的回收

CPU管理/处理机管理

内存中待执行程序段落的地址送控制器的PC(程序计数器)
内存中的多个程序，执行哪一个程序?
程序执行切换中的状态/环境保护问题

6.4 操作系统对资源的合作与协同管理

程序与进程
程序(文件)：存储在磁盘上的程序文件
进程：装入内存中的程序

任务与作业
任务：大粒度的工作，一个应用程序的完整的执行。一个任务由多个进程来完成
作业：小粒度的工作，不同的作业由不同的进程来完成

操作系统的进程：为使应用程序顺利执行而做的辅助性管理性工作的进程。操作系统的进程也存储在内存中，也需要调度CPU来执行；CPU在操作系统进程和多个应用程序进程之间来回切换。
应用程序的进程：应用程序本身的进程

作业与进程管理

应用程序执行
① 进程相关的准备工作
② 为进程分配相关的内存空间
③ 将程序由外存装载到内存中
④ 让CPU执行已经准备就绪的进程
应用程序的执行
外存中的程序中如何被载入内存如何被CPU执行？
程序载入内存

6.5 CPU管理

6.5.1 分时

一台主机一个CPU执行多个程序(来自于多个用户的多个终端)

6.5.2 并行

一台主机多个CPU执行一个程序

6.5.3 分布

网络中多台主机多个CPU执行一个任务

7、计算机的发展

通用计算环境的进化思维：
计算机的演变

云

SASS
SASS