《计算机科学导论 第三版》读书笔记

Posted by

花了不到一个月的时间粗读完了这本经典计算机专业入门教材,此书涉及范围很广,并且深度很浅,有助于简单了解计算机发展的各个方面,借梳理读书笔记再精读一遍。

目录

第1章 绪论

1.1 图灵模型

Alan Turing(阿兰·图灵)在1937年首次提出了一个通用计算设备的设想。他设想所有的计算都可能在一种特殊的机器上执行,这就是现在所说的图灵机。

可编程数据处理器

程序是用来告诉计算机对数据进行处理的指令集合。

在这个图灵模型中,输出数据是依赖两方面因素的结合作用:输入数据和程序。

如果输入数据和程序保持不变,输出结果也将不变。

1.2 冯·诺依曼模型

4个子系统

基于冯·诺依曼模型建造的计算机分为4个子系统:存储器、算术逻辑单元、控制单元和输入/输出单元。

存储器

存储器是用来存储的区域,在计算机的处理过程中存储器用来存储数据和程序

算术逻辑单元

算术逻辑单元(ALU)是用来进行计算和逻辑运算的地方。

控制单元

控制单元是对存储器、算术逻辑单元、输入/输出等子系统进行控制操作的单元。

输入/输出

输入子系统负责从计算机外部接收输入数据和程序;输出子系统负责将计算机的处理结果输出到计算机外部。

指令的顺序执行

冯·诺依曼模型中的一段程序是由一组数量有限的指令组成。

1.3 计算机组成部分

我们可以认为计算机由三大部分组成:计算机硬件、数据和计算机软件。

计算机软件

程序必须是存储的

在冯·诺依曼模型中,这些程序被存储在计算机的存储器中,存储器中不仅要存储数据,还要存储程序

1.4 历史

计算机的诞生(1950年至今)

第一代计算机

第一代计算机(大约1950~1959年)以商用计算机的出现为主要特征。

第二代计算机

第二代计算机(大约1959~1965年)使用晶体管代替真空管。

第三代计算机

集成电路(晶体管、导线以及其他部件做在一块单芯片上)的发明更加减少了计算机的成本和大小。小型计算机出现在市场上。

第四代计算机

第四代计算机(大约1975~1985年)出现了微型计算机。

第五代计算机

这个还未终止的时代始于1985年。

1.6 计算机科学作为一门学科

系统领域涵盖那些与硬件和软件构成直接有关的领域,例如计算机体系结构、计算机网络、安全问题、操作系统、算法、程序设计语言以及软件工程。应用领域涵盖了与计算机使用有关的领域,例如数据库和人工智能。

第2章 数字系统

2.1 引言

数字系统

数字系统(或数码系统)定义了如何用独特的符号来表示一个数字。

2.2 位置化数字系统

在位置化数宇系统中,数字中符号所占据的位置决定了其表示的值。

在该系统中,数字这样表示:

$$\pm(S_{k-1}\cdots S_2S_1S_0.S_{-1}S_{-2}\cdots S_{-l})_b$$

它的值是:

$$n\pm S_{k-1}\times b^{k-1}+\cdots S_1\times b^1+S_0\times b^0+S_{-1}\times b^{-1}+S_{-2}\times b^{-2}+\cdots S_{-l}\times b^{-l}$$

其中,$S$是一套符号集;$b$是底(或基数),它等于$S$符号集中的符号总数,其中$S_1$和$S_k$是代表分数部分或整个数字的符号

转换

十进制到其他进制的转换

数码的数量

通过$k=\lceil log_bN\rceil$数字系统的关系,我们总可以找到一个整数的数码的数量

通常,假设在以$b_1$为底的系统中使用$k$个数码,在源系统中显示的最大数是$b_1^k-1$。我们可在目标系统中拥有的最大数是$b_2^x-1$。因此$b_2^x-1\geq b_1^k-1$这意味着$b_2^x\geq b_1^k$,也就是:

$$x\geq k\times (log \ b_1/log\ b_2)\quad x=\lceil k\times (log \ b_1/log\ b_2)\rceil$$

2.3 非位置化数字系统

非位置化数字系统仍然使用有限的数字符号,每个符号有一个值。但是符号所占用的位置通常与其值无关——每个符号的值是固定的。为求出该数字的值,我们把所有符号表示的值相加。

第3章 数据存储

3.1 数据类型

计算机行业中使用术语“多媒体”来定义包含数字、文本、图像、音频和视频的信息。

位(bit, binary digit 的缩写)是存储在计算机中的最小单位;它是0或1。

位模式

为了表示数据的不同类型,应该使用位模式,它是一个序列,有时也被称为位流。

通常长度为8的位模式被称为1字节。有时用字这个术语指代更长的位模式。

3.2 存储数字

存储整数

整数通常使用定点表示法存储在内存中。

符号加绝对值表示法

在这种方法中,用于无符号整数的有效范围(0到$2^n-1$)被分成两个相等的子范围。前半个表示正整数,后半个表示负整数

该系统中有两个0:正0 (0000)和负0 (1000)。

在符号加绝对值表示法中,最左位用于定义整数的符号。0表示正整数,1表示负整数。

二进制补码表示法

几乎所有的计算机都使用二进制补码表示法来存储位于n位存储单元中的有符号整数。

在二进制补码表示法中,最左位决定符号。如果它是0,该整数为正;如果是1,该整数为负。

两种运算

反码

该运算简单反转各个位,即把0位变为1位,把1位变为0位。

补码

该运算分为两步:首先,从右边复制位,直到有1被复制;接着,反转其余的位。

另一种将一个整数进行补码运算的方法是先对它进行1次反码运算再加上1得到结果

以二进制补码格式存储整数

  • 将整数变成n位的二进制数。
  • 如果整数是正数或零,以其原样存储;如果是负数,计算机取其补码存储。

从二进制补码格式还原整数

  • 如果最左位是1,计算机取其补码。如果最左位是0,计算机不进行操作。
  • 计算机将该整数转换为十进制。

二进制补码表示法仅有一个0

实数

带有很大的整数部分或很小的小数部分的实数不应该用定点表示法存储。

浮点表示法

在浮点表示法中,无论十进制还是二进制,一个数字都由3部分组成。 第一部分是符号,可正可负。第二部分显示小数点应该左右移动构成实际数字的位移量。第三部分是小数点位置固定的定点表示法。

规范化

为了使表示法的固定部分统一,科学计数法(用于十进制)和浮点表示法(用于二进制)都在小数点左边使用了唯一的非零数码,这称为规范化。十进制系统中的数码可能是1~9,而二进制系统中该数码是1。

符号,指数和尾数

在一个二进制数规范化之后,我们只存储了一个数的三部分信息:符号、指数和尾数(小数点右边的位)。

符号

一个数的符号可以用一个二进制位来存储(0或1)。

指数

指数(2的幂)定义为小数点移动的位数。注意幂可以为正也可以为负。

尾数

尾数是指小数点右边的二进制数。它定义了该数的精度。

尾数是带符号的小数部分,像以符号加绝对值表示法存储的整数那样对待。

余码系统

在该余码系统中,正的和负的整数都可以作为无符号数存储。为了表示正的或负的整数,一个正整数(称为一个偏移量)加到每个数字中,将它们统一移到非负的一边。这个偏移量的值是$2^{m-1}-1$,$m$是内存单元存储指数的大小。

IEEE标准

单精度数格式采用总共32位来存储一个浮点表示法的实数。符号占用1位(0为正,1为负),指数占用8位(使用偏移量127),尾数使用23位(无符号数)。该标准有时称为余127码(Excess_127),因为偏移量是127。

双精度数格式采用总共64位来存储一个浮点表示法的实数。符号占用1位(0为正,1为负),指数占用11位(使用偏移量1023), 尾数使用52位。该标准有时称为余1023码(Excess_1023),因为偏移量是1023。

IEEE标准浮点数的存储

使用以下步骤,一个实数可以存储为IEEE标准浮点数格式:

  • 在S中存储符号(0或1)。
  • 将数字转换为二进制。
  • 规范化。
  • 找到E和M的值。
  • 连接S、E和M。

将存储为IEEE标准浮点数的数字还原

一个以IEEE浮点格式之一存储的数字可以用以下步骤方法还原:

  • 找到S、E和M的值。
  • 如果S=0,将符号设为正号,否则设为负号。
  • 找到位移量(E-127)。
  • 对尾数去规范化。
  • 将去规范化的数字变为二进制以求出绝对值。
  • 加上符号。

上溢和下溢

对于浮点数,有上溢和下溢两种情况。

该表示法不能存储很小或很大的绝对值。试图存储绝对值很小的数导致下溢的情况,而试图存储绝对值很大的数导致上溢的情况。

存储零

约定在这种情况下符号、指数和尾数都设为零

截断错误

原始数字与还原后数字的差异称为截断错误。

3.3 存储文本

代码

不同的位模式集合被设计用于表示文本符号。其中每一个集合我们称之为代码。表示符号的过程被称为编码。

ASCII

美国国家标准协会(ANSI)开发了一个被称为美国信息交换标准码(ASCII)的代码。该代码使用7位表示每个符号。即该代码可以定义$2^7=128$种不同的符号。

Unicode

硬件和软件制造商联合起来共同设计了一种名为Unicode的代码,这种代码使用32位并能表示最大达$2^{32}=4294967296$个符号。代码的不同部分被分配用于表示来自世界上不同语言的符号。其中还有些部分被用于表示图形和特殊符号。

如今ASCII是Unicode的一部分。

3.4 存储音频

音频是随时间变化的实体,我们只能在每一时刻度量声音的密度。当我们讨论用计算机内存存储声音时,我们的意思是存储一个音频信号的密度,例如,每隔一段时间(一秒钟,一小时)来自麦克风的信号。

音频是模拟数据的例子。即使我们能够在一段时间度量所有的值,也不能把它全部存在计算机内存中,因为可能需要无限数量的内存单元。

采样

采样意味着我们在模拟信号上选择数量有限的点来度量它们的值并记录下来。

采样率

每秒40000个样本的采样率对音频信号来说是足够好的。

畳化

量化指的是将样本的值截取为最接近的整数值的一种过程。

编码

量化的样本值需要被编码成位模式。

毎样本位

对于每个样本系统需要决定分配多少位。

毎样本位的数量有时称为位深度。

位率

如果我们称位深度或每样本位的数量为$B$,每秒样本数为$S$,我们需要为每秒的音频存储$S\times B$位。该乘积有时称为位率$R$。

声音编码标准

当今音频编码的主流标准是MP3(MPEG Layer3的简写)。该标准是用于视频压缩方法的MPEG(动态图像专家组)标准的一个修改版。它采用每秒44100个样本以及每样本16位。结果信号达到705600b/s的位率,再用去掉那些人耳无法识别的信息的压缩方法进行压缩。

3.5 存储图像

光栅图

当我们需要存储摸拟图像(如照片)时,就用到了光栅图(或位图)。一张照片由模拟数据组成,类似于音频信息。不同的是数据密度(色彩)因空间变化,而不是因时间变化。这意味着数据需要采样。然而,这种情况下采样通常被称作扫描。样本称为像素(代表图像元素)。换言之,整个图像被分成小的像素,每个像素假定有单独的密度值。

解析度

在图像处理中的扫描率称为解析度。

色彩深度

用于表现像素的位的数量,即色彩深度,依赖于像素的颜色是如何由不同的编码技术来处理的。

真彩色

用于像素编码的技术之一称为真彩色,它使用24位来编码一个像素。在该技术中,每个三原色(RGB)都表示为8位。因为该技术中8位模式可以表示0~255之间的一个数,所以每种色彩都由0~255之间的三维数字表示。

索引色

真彩色模式使用了超过1600万种的颜色。许多应用程序不需要如此大的颜色范围。索引色(或调色板色)模式仅使用其中的一部分。在该模式中,每个应用程序从大的色彩集中选择一些颜色(通常是256种)并对其建立索引。对选中的颜色赋一个0~255之间的值。

矢量图

矢量图图像编码方法并不存储每个像素的位模式。一个图像被分解成几何图形的组合,例如,线段、矩形或圆形。

矢量图也称为几何模型或面向对象图形。

3.6 存储视频

视频

视频是图像(称为帧)在时间上的表示。

换言之,视频是随空间(单个图像)和时间(一系列图像)变化的信息表现。

第4章 数据运算

4.1 逻辑运算

位层次上的逻辑進算

真值表定义了对于每一种可能的输入的输出值。

异或(XOR)

$$x\ XOR\ y\leftrightarrow[x\ AND\ (NOT\ y)]\ OR\ [(NOT\ x)\ AND\ y]$$

模式层次上的逻辑运算

应用

使指定的位复位

AND运算的一个应用就是把一个位模式的指定位复位(置0)。这种情况下的第二个输入称为掩码。掩码中的0位对第一个输入中相应的位进行复位。掩码中的1位使得第一个输入中相应的位保持不变。

对指定的位置位

OR运算的一个应用是把一个位模式的指定位置位(置1)。我们再次使用掩码,但是一个不同的掩码。掩码中的1位对第一个输入中的相应的位进行置位,而掩码中的0位使第一个输入中相应的位保持不变。

使指定的位反转

XOR运算的一个应用是使指定的位反转,我们再次使用掩码,但是一个不同的掩码。掩码中的1位对第一个输入中的相应的位进行反转,而掩码中的0位使第一个输入中相应的位保持不变。

4.2 移位运算

逻辑移位运算

逻辑移位

逻辑右移运算把毎一位向右移动一个位置。

循环移位运算(旋转运算)对位进行移位,但没有位被丢弃或增加。

算术移位运算

算术右移保留符号位,但同时也把它复制,放入相邻的右边的位中,因此符号被保存。

算术左移丢弃符号位,接受它的左边的位作为符号位。如果新的符号位与原先的相同,那么运算成功,否则发生上溢或下溢,结果是非法的。

4.3 算术运算

整数的算术运算

二进制补码中的加减法

二进制补码表示法的一个优点是加法和减法间没有区别。当遇到减法时,计算机只简单地把它转变为加法,但要为第二个数求二进制的补。

过程如下:

  • 如果运算是减法,我们取第二个整数的二进制补码,否则,转下一步。
  • 两个整数相加。

当我们进行计算机中数字上的算术运算时,要记住每个数字和结果应该在分配的二进制位的定义范围之内。

符号加绝对值整数的加减法

实数的算术运算

实数的加减法

第5章 计算机组成

5.1 引言

计算机的组成部件可以分为三大类(或子系统):中央处理单元(CPU)、主存储器和输入/输出子系统。

5.2 中央处理单元

中央处理单元(CPU)用于数据的运算。在大多数体系结构中,它有三个组成部分:算术逻辑单元(ALU)、控制单元、寄存器组、快速存储定位。

算术逻辑单元

算术逻辑单元(ALU)对数据进行逻辑、移位和算术运算。

寄存器

寄存器是用来存放临时数据的高速独立的存储单元。

指令寄存器

CPU的主要职责是:从内存中逐条地取出指令,并将取出的指令存储在指令寄存器(寄存器IR)中,解释并执行指令。

程序计数器

程序计数器中保存着当前正在执行的指令。当前的指令执行完后,计数器将自动加1,指向下一条指令的内存地址。

控制单元

控制单元控制各个子系统的操作。控制是通过从控制单元到其他子系统的信号来进行。

5.3 主存储器

主存储器是计算机内的第二个子系统。它是存储单元的集合,每一个存储单元都有唯一的标识,称为地址。数据以称为字的位组的形式在内存中传入和传出。

地址空间

所有在存储器中标识的独立的地址单元的总数称为地址空间。

作为位模式的地址

由于计算机都是以位模式存储数并进行运算,因此地址本身也是用位模式表示的。

内存地址用无符号二进制整数定义。

存储器的类型

主要有两种类型的存储器:RAM和ROM。

RAM

随机存取存储器(RAM)是计算机中主存的主要组成部分。在随机存取设备中,可以使用存储单元地址来随机存取一个数据项,而不需要存取位于它前面的所有数据项。

RAM和ROM的区别在于,用户可读写RAM,即用户可以在RAM中写信息,之后可以方便地通过覆盖来擦除原有信息。

当计算机断电后,存储在RAM中的信息将被删除。

ROM

只读存储器(ROM)的内容是由制造商写进去的。用户只能读但不能写

当切断电源后,数据也不会丢失。

存储器的层次结构

高速缓冲存储器

高速缓冲存储器的存取速度要比主存快,但是比CPU及其内部的寄存器要慢。

高速缓冲存储器在任何时间都含有主存中一部分内容的副本。当CPU要存取主存中的一个字的时候,将按以下步骤进行:

  • CPU首先检查高速缓冲存储器。
  • 如果要存取的字存在,CPU就将它复制;如果不存在,CPU将从主存中复制一份从需要读取的字开始的数据块。该数据块将覆盖高速缓冲存储器中的内容。
  • CPU存取高速缓冲存储器并复制该字。

如果字在高速缓冲存储器中,就立即存取它。如果宇不在高速缓冲存储器中,字和整个数据块就会被复制到高速缓冲存储器中。因为很有可能CPU在下次存取中需要存取上次存取的第一个字的后续宇,所以高速缓冲存储器可以大大提高处理的速度。

5.4 输入/输出子系统

这个子系统可以使计算机与外界通信,并在断电的情况下存储程序和数据。

存储设备

有时称它们为辅助存储设备,通常分为磁介质和光介质两种。

磁介质存储设备

磁介质存储设备使用磁性来存储位数据。如果一点有磁性则表示1,如果没有磁性则表示0。

磁盘

磁盘是由一张一张的磁片叠加而成的。这些磁片由薄磁膜封装起来。信息是通过盘上每个磁片的读/写磁头读写磁介质表面来进行读取和存储的。

为了将数据存储在磁盘的表面,每个盘面都被划分成磁道,每个磁道又分成若干个扇区。磁道间通过磁道内部间隔隔开,扇区之间通过扇区内部间隔隔开。

数据项可以被随机存取,而不需要存取放置在其前的所有其他数据。但是,在某一时间可以读取的最小的存储区域只能是一个扇区。数据块可以存储在一个或多个扇区上,而且该信息的获取不需要通过读取磁盘上的其他信息。

磁盘的性能取决于几个因素:最重要的因素是角速度、寻道时间和传送时间。角速度定义了磁盘的旋转速度。寻道时闻定义了读/写磁头寻找数据所在磁道的时间。传送时间定义了将数据从磁盘移到CPU/内存所需要的时间。

磁带

磁带的宽度可以分为9个磁道:磁道上的每个点可以存储1位的信息。垂直切面的9个点可以存储8位(即1字节)的信息,还有1位用作错误检测。

磁带是顺序存取设备。尽管磁带的表面可能会分成若干块,但是却没有寻址装置来读取每个块。要想读取指定的块就需要按照顺序通过其前面所有的块。

光存储设备

光存储设备是一种新技术,它使用光(激光)技术来存储和读取数据。

CD-ROM

激光束使位模式变成一系列的坑(有洞)和纹间表面(没有洞)。坑通常表示0,纹间表面则通常表示1。但这也只是一种规则,也可以反过来表示。另一种方法是将过渡部分(坑到洞或者洞到坑)表示1,而非过渡部分表示0。

CD-ROM依靠来自计算机光驱的低能激光束读信息,激光束经过有纹间表面时会被铝质的表射层反射回来。经过坑处时会被反射两次,一次是被坑的边缘反射,另外一次是被铝质表射层的边界反射,这两次反射有破坏性的影响。因为坑的深度是精确选定的,为激光束波长的1/4。换言之,装在驱动器上的感应器对于某个点是纹间表面时,应该探测到多一些的光信号,反之是坑时就少一点;这样它才可以读出记录在原始主盘上的信息。

CD-R
CD-RW

5.5 子系统的互连

CPU和存储器的连接

CPU和存储器之间通常由称为总线的三组线路连接在一起,它们分别是:数据总线、地址总线和控制总线。

数据总线

数据总线是由多根线组成,每一根线上每次传送1位的数据。线的数量取决于计算机的字的大小。

地址总线

地址总线允许访问存储器中的某个字,地址总线的线数取决于存储空间的大小。如果存储器容量为$2^n$个字,那么地址总线一次需要传送$n$位的地址数据。因此它需要$n$根线。

控制总线

控制总线负责在中央处理器和内存之间传送信息。例如,必须有一个代码从CPU发往内存,用于指定进行的是读操作还是写操作。控制总线的线数取决于计算机所需要的控制命令的总数。如果计算机有$2^m$条控制命令,那么控制总线就需要有$m$根,因为$m$位可以定义$2^m$个不同的操作。

I/O设备的连接

输入/输出设备是通过一种被称为输入/输出控制器或接口的器件连接到总线上的。每一个输入/输出设备都有一个特定的控制器。

控制器

控制器,或者说接口,清除了输入/输出设备与CPU及内存在本质上的障碍。

串行控制器则只有一根数据线连接到设备上,而并行控制器则有数根数据线连接到设备上,使得一次能同时传送多个位。

SCSI(小型计算机系统接口)

它是一个8、16或32线的并行接口。

它提供了菊花链连接,连接链的两端都必须有终结器,并且每个设备都必须要有唯一的地址(目标ID)。

火线

它可以在一条菊花链或树形连接(只用一根线)上连接多达63个设备。

它不需要终结器。

USB

通用串行总线(USB)控制器是一种可以和火线控制器相媲美的控制器。

多个设备可以被连接到一个USB控制器上,这个控制器也称为根集线器。USB-2(USB 版本2.0)允许多达127个设备组成树状拓扑结构连接到一个USB控制器上,其中控制器作为树的根,集线器作为中间节点,设备作为末端节点。控制器(根集线器)与其他集线器的不同之处在于控制器能感知到树中其他集线器的存在,而其他集线器是被动的设备,它们只是简单地传送数据。

设备可以不需要关闭计算机很容易地被移除或连接到树中。这称为热交换。当集线器被从系统中移除时,与此集线器相连的所有设备和其他集线器也被移除。

USB使用4根线的电缆。两根线(+5V和地)被用来为像键盘和鼠标这样的低压设备提供电压。高压设备需要被连接到电源上。集线器从总线取得电压,能为低压设备提供电压。其他两根线(缠绕在一起,以减小噪声)用来传送数据、地址和控制信号。

通过USB的数据是以包的形式传输的。每个包含有:地址部分(设备标识)、控制部分、要被传送到其他设备的数据部分。所有设备将接收到相同的包,但只有具有数据包中所定义的地址的那些设备将接受它。

HDMI

高清晰度多媒体接口(HDMI)是现有视频模拟标准的数字化替代品。它可以用来从个资源向另一个兼容的计算机显示器、视频投影仪、数字电视或数字音像设备传输视频数据和数字音像数据。

输入/输出设备的寻址

通常CPU使用相同的总线在主存和输入/输出设备之间读写数据。

I/O独立寻址

在I/O独立寻址中,用来读/写内存的指令与用来读/写输入/输出设备的指令是完全不同的。有专门的指令完成对输入/输出设备的测试、控制以及读写操作。每个输入/输出设备有自己的地址。因为指令的不同,所以输入/输出地址可以和内存地址重叠而不会产生混淆

I/O存储器映射寻址

在I/O存储器映射寻址方式中,CPU将输入/输出控制器中的每一个寄存器都看作内存中的某个存储字。换言之,CPU没有不同的指令用来表示是从内存或是从输入/输出设备传送数据。

存储器映射的输入/输出的配置优点在于有一个较小的指令集,所有对内存的操作指令都同样适合于输入/输出设备,其缺点是输入/输出控制器占用了一部分内存地址。

5.6 程序执行

机器周期

CPU利用重复的机器周期来执行程序中的指令,一步一条,从开始到结東。一个简化的周期包括3步:取指令、译码和执行。

取指令

在取指令阶段,控制单元命令系统将下一条将要执行的指令复制到CPU的指令寄存器中。被复制的指令地址保存在程序计数器中。复制完成后,程序计数器自动加1指向内存中的下一条指令。

译码

机器周期的第二阶段是译码阶段。当指令置于指令寄存器后,该指令将由控制单元负责译码。指令译码的结果是产生一系列系统可以执行的二进制代码。

执行

指令译码完毕后,控制单元发送任务命令到CPU的某个部件

输入/输出操作

计算机需要通过命令把数据从I/O设备传输到CPU和内存。因为输入/输出设备的运行速度比CPU慢得多,因此CPU的操作在某种程度上必须和输入/输出设备同步。

程序控制输入/输出

在程序控制输入/输出中,采用最简单的一种同步:CPU等待I/O设备。

这种方法存在的最大问题就是,当每一个单元数据被传输时, CPU都要浪费时间去查询I/O的状态。

中断控制输入/输出

在中断控制输入/输出中,首先CPU告知I/O设备即将开始传输,但是CPU并不需要不停地査询I/O设备的状态。当I/O设备准备好时,它通知(中断)CPU。在这过程中,CPU还可以做其他工作。

在这种方法中,CPU时间没有被浪费。当慢速的I/O设备正在完成一项任务时,CPU可以做其他工作。

直接存储器存取(DMA)

第三种传输数据的方法是直接存储器存取(DMA)。这种方法用于在高速I/O设备间传输大量的数据块

这种方法需要一个DMA控制器来承担CPU的一些功能。DMA控制器中有寄存器,可以在内存传输前后保存数据块。

需要注意的是,在这种方法中,CPU只是在一小段时间内是空闲的。CPU仅当在DMA和内存间传输数据时才空闲,而不是在设备为传输数据做准备时。

5.7 不同的体系结构

CISC

CISC(读作[sisk])是复杂指令集计算机(complex instruction set computer)的缩写。CISC体系结构的设计策略是使用大量的指令,包括复杂指令。

指令集的复杂性使得CPU和控制单元的电路非常复杂。CISC体系结构的设计者已经提出减少这种复杂性的解决方案:程序在两个层面上运行。CPU不直接执行机器语言指令。CPU只执行被称为微操作的简单操作。复杂指令被转化为一系列简单操作然后由CPU执行。这种执行机制需要一个被称为微内存的特殊内存,它负责保存指令集中的每个复杂指令的一系列操作。使用微操作的程序设计被称为微程序说计。

RISC

RISC(读作[risk])是精简指令集计算机(reduce instruction set computer)的缩写。RISC体系结构的设计策略是使用少量的指令完成最少的简单操作。复杂指令用简单指令子集模拟。

流水线

现代计算机使用称为流水线的技术来改善吞吐量(在单位时间内完成的指令总数)。这个理念是如果控制单元能同时执行两个或三个阶段,那么下一条指令就可以在前一条指令完成前开始。

并行处理

随着技术的进步和计算机硬件成本的下降,如今可以拥有具有多个控制单元、多个算术逻辑单元和多个内存单元的计算机。这个思想称为并行处理。像流水线一样,并行处理能改善吞吐量。

SISD组织

单指令流,单数据流(SISD)组织表示计算机有一个控制单元、一个算术逻辑单元和一个内存单元。指令被顺序执行,每条指令可以存取数据流中的一个或多个数据项。

SIMD组织

单指令流,多数据流(SIMD)组织表示计算机有一个控制单元、多个处理单元和一个内存单元。所有处理器单元从控制单元接收相同的指令,但在不同的数据项上操作。

MISD组织

多指令流,单数据流(MISD)体系结构是属于多个指令流的多个指令作用于相同的数据项的体系结构。

MIMD组织

多指令流,多数据流(MIMD)体系结构是属于多个指令流的多个指令作用于多个数据流(每条指令作用于一个数据项)。

5.8 简单计算机

CPU

CPU本身被分成三部分:数据寄存器、算术逻辑单元(ALU)和控制单元。

数据寄存器

计算机中有16个16位的数据寄存器,它们的十六进制地址为$(0,1,2,\cdots,F)_ {16}$但我们称它们为$R_0$到$R_ {15}$

控制单元

控制单元具有电路,控制ALU的操作、对内存的存取和对I/O子系统的存取。它有两个专用的寄存器:程序计数器和指令寄存器。程序计数器(PC)(只含有8位)保存的是下条将被执行的指令的踪迹。PC的内容指向含有下一条程序指令的主存的存储单元的地址。在每个机器周期后,程序计数器将加1,指向下一条程序指令。指令寄存器(IR)含有16位值,它是当前周期译码的指令。

主存

主存有256个16位的存储单元,二进制的地址为$(00000000$到$11111101)_ 2$,或者是十六进制的$(00$到$FD)_ {16}$。主存中既有数据,又有程序指令。前64个存储单元$(00$到$3F)_ {16}$被专用于程序指令。任何程序的程序指令存储在连续的内存单元中,内存单元$(40$到$FD)_ {16}$被用来存储数据。

输入/输出子系统

假定键盘(作为输入设备)和监视器(只作为输出设备)像内存单元一样,它们的地址分别为$(FE)_ {16}$和$(FF)_ {16}$

指令集

每条计算机指令由两部分构成:操作码(opcode)和操作数(operand)。操作码指明了在操作数上执行的操作的类型。每条指令由16位组成,被分成4个4位的域。最左边的域含有操作码,其他3个域含有操作数或操作数的地址,如图5-31所示。

注意,并不是每条指令都需要3个操作数。任何不需要的操作数域被填以$(0)_ {16}$。

还要注意,寄存器地址是用单个十六进制数来表示的,所以只用一个域,而内存单元是用两个十六进制数来表示,所以用两个域。

如果使用地址$(FE)_ {16}$作为LOAD指令的第二个操作数,简单计算机就可以从键盘取得输入。同样,如果使用地址$(FF)_ {16}$作为STORE指令的第二个操作数,计算机就可以发送输出到监视器。如果ROTATE指令的第三个操作数是0,那么指令就把R中的二进制位模式向右循环移位n个位置;如果第三个操作数是1,则向左循环移位。

处理指令

一个周期有三个阶段:取指令、译码和执行。在取指令阶段,其地址由PC决定的指令从内存中得到,被装入IR中。然后PC加1,指向下一条指令。在译码阶段,IR中的指令被译码,所需的操作数从寄存器或内存中取到。在执行阶段,指令被执行,结果被放入合适的内存单元或寄存器中。一旦第三阶段结束,控制单元又开始新的周期,现在PC是指向下一条指令的。处理过程一直继续,直到CPU遇到HALT指令。

一个例子

完成这个简单加法的简单程序需要5条指令,显示如下:

  • 把内存$M_ {40}$的内容装入寄存器$R_ 0(R_ 0\leftarrow M_ {40})$。
  • 把内存$M_ {41}$的内容装入寄存器$R_ 1(R_ 1\leftarrow M_ {41})$
  • 相加$R_ 0$和$R_ 1$的内容,结果放入$R_ 2$中$(R_ 2\leftarrow R_ 0+R_ 1)$。
  • 把$R_ 2$的内容存入$M_ {42}$中$(M_ {42}\leftarrow R_ 2)$。
  • 停机。

存储程序和数据

为了遵循冯·诺依曼模型,我们需要把程序和数据存储在内存中,可以从内存单元$(00)_ {16}$到$(04)_ {16}$存储5行程序。

指令周期

第6章 计算机网络和因特网

6.1 引言

网络

网络是一系列可用于通信的设备相互连接构成的。在这个定义里面,一个设备可以是一台主机(或用另一种称呼,端系统),

设备也可以是一个连接设备,比如用来将一个网络与另一个网络相连接的路由器,一个将不同设备连接在一起的交换机,或者一个用于改变数据形式的调制解调器,等等。在一个网络中,这些设备都通过有线或无线传输媒介(比如电缆或无线信号)互相连接。

局域网

局域网(LAN)通常是与单个办公室、建筑或校园内的几个主机相连的私有网络。

在一个局域网中的每一台主机都有作为这台主机在局域网中唯一定义的一个标识符和一个地址。一台主机向另一台主机发送的数据包中包括源主机和目标主机的地址。

广域网

广域网(WAN)也是通信设备互连构成的。

局域网将主机互连,广域网则将交换机、路由器或调制解调器之类的连接设备互连。通常,局域网为机构私有,广域网则由通信公司创建并运营,并且租给使用它的机构。

点对点广域网是通过传输媒介(电缆或无线)连接两个通信设备的网络。

交换广域网是一个有至少两个端的网络。就像我们很快就会看到的那样,交换广域网用于当今全球通信的骨干网。我们也可以这么说,交换广域网是几个点对点广域网通过开关连接产生的结合体。

互联两络

当两个或多个网络互相连接时,它们构成一个互联网络,或者说网际网。

因特网

最值得注意的网际网是因特网,它由成千上万个互连的网络组成。

在顶层,骨干网为通信公司所拥有,这些骨干网通过一些复杂的交换系统相互连接。我们把这些交换系统称为网络对等交汇点(peering point)。在第二层,有一些规摸较小的网络,这些网络称为供应商网络,它们付费使用骨干网上的一些服务。这些供应商网络与骨干网相连接,有时也连接其他供应商网络。在因特网的边缘有一些真正使用基于因特网的服务的网络,这些网络是客户网络,他们向供应商网络付费来得到服务。

骨干网和供应商网络也被称为因特网服务供应商(ISP),骨干网通常被称为国际因特网服务供应商,供应商网络则被称为国内或地域性因特网服务供应商。

协议分层

协议定义了发送器、接收器以及所有中间设备必须遵守以保证有效地通信的规则。简单的通信可能只需要一条简单的协议,当通信变得复杂时,可能需要将任务分配到不同的协议层中,在这种情况下,我们在每一个协议层都需要一个协议,或者协议分层。

情景

一个协议层(模块)可以定义为一个具有输入和输出而不需要考虑输入是如何变成输出的黑匣子。

协议分层的一个优势就是可以将服务和其实施分开来。每层使用更低层的服务,并向较高一层提供服务;并且我们不需要考虑该层是如何实施的。

协议分层的原则

我们讨论一下协议分层的原则。第一条原则规定,如果我们想达到双向通信,我们需要保证每一个协议层都可以进行两个对立且方向相反的工作。

在协议分层中,我们需要遵守的第二条重要原则是在两个站点中每一层的两个对象必须完全相同。例如,在两个站点中第三层的对象都应该是明文信件,而在两个站点中第二层的对象都应该是密文信件,在第一层则都是一封信。

TCP/IP协议族

传输控制协议/网际协议(TCP/IP)。如今因特网中使用的协议集(一组通过不同分层进行组织的协议)被称为TCP/IP协议族。TCP/IP协议族是一个分层协议,它由提供特定功能的交互式模块组成。分层这个术语说明每一个高层协议都基于一个或多个低层协议提供的服务。TCP/IP协议族被定义成图6-7所示布局的软件层。

分层架构

两台主机都涉及5个协议层,同时源主机需要在应用层中创建消息并将其通过协议层向下发送,这样这条消息才能物理地发送至目标主机。目标主机需要在物理层接收通信并通过其他协议层将其发送至应用层。

路由器只涉及三个层,由于路由器仅用来路由,所以在路由器中没有传输层或应用层。虽然路由器总是包括在网络分层中,但是它仅仅被包括在n个链接和物理层的组合中,这里的n指与路由器相连的链接数。因为每个链接都可能使用它自已的数据链接协议或物理协议。

然而,链接中的链路层开关只涉及两个协议层:数据链路层和物理层。虽然图6-7中的每个开关都有两个不同的连接,但是这些连接都在同一个链接中,这些链接仅使用一组协议。这一点说明与路由器不同的是,链路层开关只涉及一个数据链路层和j物理层。

地址和数据包名称

在这个模型中,我们有层组之间的逻辑通信。任何涉及两步校验的通信需要两个地址:源地址和目标地址。虽然看上去我们需要5组地址,每个协议层一组,但是正常情况下我们只有4组,因为物理层不需要地址。这是由于物理层数据交换的单位是位,这使它无法得到地址。图6-9展示了每一层的数据包名称和地址。

在应用层,我们通常使用名称来定义提供服务的站点,比如someorg.com,或者邮箱地址,比如somebody@coldmail.com。在传输层,地址被称为端口号,这些端口号的作用是在源和目的之间定义应用层程序。端口号的作用是通过各程序的本地地址来辨别多个同时运行的本地程序。在网络层,这些地址在整个因特网范围下是全球化的,网络层的地址独一无二地定义了该设备与因特网的连接。链路层地址,有时称为MAC地址,是在本地定义的地址,每一个链路层地址在计算机网络(局域网(LAN)或广域网(WAN))中定义一个特定的主机或者路由器。

6.2 应用层

TCP/IP协议族的第5层叫做应用层。应用层向用户提供服务。通信由逻辑连接提供,也就是说,假设两个应用层通过之间假想的直接连接发送和接收消息。

提供服务

应用层与其他层不同的地方在于,它是协议族中的最高层。在这层中的协议不向其他协议提供服务,它们只接收在传输层的协议提供的服务。这意味着该层的协议可以轻易去除。只要新的协议可以使用传输层中任意一个协议提供的服务,这个新的协议就可以添加到应用层上。

因为应用层是唯一向因特网用户提供服务的层,应用层的灵活性使得新的协议可以很容易地添加到网络上,如前所述,这个情况在因特网的生命周期内常常出现。

应用层模式

两个应用程序都应能够请求和提供服务,或者这些应用程序只需要其中的一个或另外一个功能?在网络的生命周期中,应用程序发展出了两种模式来解答这个问题:客户机-服务器模式和端到端模式。

传统模式:客户机-服务器模式

在这种模式中,服务提供者是一个应用程序,叫做服务器进程,这个进程一直持续运转,等待另一个叫做客户端进程的应用程序通过因特网连接要求服务。通常一些服务器进程可以提供某特定种类的服务,但是向这些服务器进程请求服务的用户会很多,因此很多服务器进程需要一直运行,而客户端进程只在需要时运行。

虽然在客户机-服务器模式中的通信是在两个应用程序之进行的,但每个应用程序的角色完全不同

这种模式的一个问题是通信负荷集中由服务器承担,这说明服务器必须是一台极为强大的计算机。

一些传统服务仍然在使用这种模式,包括万维网(WWW)和它的超文本传输协议(HTTP),文件传输协议(FTP)、安全外壳协议(SSH)、邮件服务,等等。

新模式:端到端模式

端到端模式(通常缩写为P2P模式)是一个新的模式,这种模式为了响应一些新应用的需求而形成。在这种模式中,不需要一个一直运行并等待客户端进程连接的服务器进程。这个责任是在端与端之间共享的。一台与网络相连接的计算机可以在一个时间段提供服务又在另一个时间段接收服务。一台计算机甚至可以在同一时间提供和接收服务。

最主要的挑战是安全性。

另一个挑战则是适应性

标准化客户机-服务器应用

在网络的生命周期中,发展出了几种客户机-服务器应用程序。

万维网和超文本传输协议

万维网

Web是具有连接分布在世界各地的文档中信息的存储库。这个存储库中叫做网页的文档分布在全世界并且相关的文档都链接在一起。

分布促进了Web的发展,世界上的每一个Web服务器都可以往这个存储库上添加一个新网页并且告知所有网络用户而不用担心导致个别服务器过载。链接使一个网页可以参考存储在世界上另外一个地方的服务器中的另一个网页。网页之间的链接是通过一个叫做超文本的概念达到的

当用户点击链接时,就会检索到被链接的文档。

在这个服务中,客户可以通过浏览器来访问使用服务器的服务。但是,提供的服务分布在许多地方,称为站点。每个站点存储的一个或多个文档称为网页。然而,每个网页都包含到相同站点或不同站点的其他网页相连的链接。换句话说,一个网页可以很简单也可以很复杂。一个简单的网页不包含到其他网页的链接,一个复杂的网页则拥有一个或多个到其他网页的链接。每个网页都是一个具有名称和地址的文件。

客户端(浏览器)

每个浏览器通常由三部分构成:控制器、客户端协议和解释器。

控制器接收来自键盘或鼠标的输入,使用客户端程序存取文档。在文档被存取之后,控制器使用一个解释器在屏幕上显示文档。客户端协议可以是稍后要描述的协议中的一种,如HTTP或FTP。根据文档类型,解释器可以是HTML、Java或Javascript。

服务器

服务器存储网页。每当请求到达时,相应的文档会发送至客户端。

统一资源定位器(URL)

作为文件,网页需要唯一地标识符来将它和其他网页区分开来。

这意味着我们需要4个标识符来定义网页,第一个是用来得到网页的工具种类,剩下三个的组合定义目标对象(网页)。

  • 协议:为了访问网页需要的第一个标识符是客户机-服务器程序的缩写。
  • 主机:主机标识符可以是服务器的IP地址或服务器的特定名称。
  • 端口:端口号通常是为客户机-服务器应用程序预定义的16位整数。
  • 路径:路径标识该文件在基本的操作系统中的名字和位置。这种格式的标识符通常由操作系统决定。

统一资源定位器(URL)是为了把这4个部分结合起来而设计的,如下所示,它用3种不同的分隔符将4个部分分开:

protocol://host/path 大多数时间用

protocol://host:port/path 当需要端口号时使用

超文本传输协议

超文本传输协议(HTTP)是一个用来定义如何编写客户机-服务器程序以便于从网络中检索网页的协议。HTTP客户端发送请求,服务器返回响应。服务器使用的端口号为80,而客户机使用临时端口号。

文件传输协议

文件传输协议(FTP)是TCP/IP提供的标准协议,用于从一台计算机复制文件到另一台计算机。

命令和数据的分开传输使得FTP效率更高。

两个连接的生命周期

FTP中的两个连接有着不同的生命周期。控制连接在整个交互式FTP会话中都是保持打开的,而数据连接为每个文件传输活动打开和关闭。每次涉及使用文件传输命令时,它就打开,文件传输结束后,它就关闭。

电子邮件

电子邮件被认为是一个单向事务。

休系结构

管理员已经为每个用户创建了一个邮箱,用来存储收到的信息。邮箱是服务器硬盘的一部分,一个有权限限制的特殊文件。只有邮箱的主人可以进入它。

三个不同的代理程序:用户代理(UA)、信息传送代理(MTA)和信息访问代理(MAA)。

这里用到了两个信息传送代理:一个客户机和一个服务器。就像网络上的其他客户机-服务器程序一样,服务器需要一直运行,因为它不知道何时会有客户要求连接。另一方面,当队列中有一个邮件将要发送时,客户机可以被系统触发。

Bob需要另一组客户机-服务器程序:信息访问程序。这是因为MTA客户机-服务器程序是推入程序:客户机将消息推入(上载)服务器。Bob需要一个拉出程序,客户机需要从服务器拉出(下载)信息。

TELNET

为一系列常用场景设置一个特定的客户机/服务器程序,但是使用一些一般性的客户机/服务端程序,这样的程序可以允许用户在客户端站点登录服务器端计算机,并且可以使用该计算机上可用的服务。

我们把这些一般性的客户机/服务器对称为远程登录应用。

TELNET是终端网络(Terminal NETwork)的缩写,是最早的远程登录协议之一。虽然TELNET要求登录名和密码,但是面对黑客行为时它是很脆弱的,因为它以明文形式(不是密文)发送所有数据,包括密码。黑客可以窃听并且得到登录名和密码。由于这个安全问题,TELNET的使用已经由于另一个协议(安全外壳协议)的使用而减少。

安全外売

虽然现今安全外壳(SSH)是一个可以用作多个目的(如远程登录和文件传输)的安全应用程序,但是它在最初是为了代替TELNET而设计的。

域名系统

网络需要有一个可以将名称映射到地址的目录系统。

命名空间

命名空间可以把每一个地址映射到一个唯一的名称上,这些名称通常按照分层进行组织。在一个分层的命名空间内,每个名字由几部分组成。第一部分定义组织的本质,第二部分定义组织的名称,第三部分定义组织中的部门,等等。在这里,命名空间的分配和控制权可以是分散的。

组织可以通过向名称添加后缀(或前缀)来定义它的主机或资源。

网络中的域名系统

网络中,域名空间(树)最初分为三个不同部分:一般域、国家域和反相域。然而,由于网络的快速发展,跟踪反相域变得极为困难,这里反相域的作用是在设置IP地址时找到该主机的名称。

一般域

一般域根据注册主机的一般行为对它们进行定义。树上的每一个节点定义一个域,这些节点是域名空间数据库的索引。

国家域

国家域部分使用两个字符组成的国家缩写(例如,us作为United States的缩写)。第二个标签可以是编制的,也可以是更特定的国别称号。

端到端模式

准备好共享他们资源的网络用户成为同位体并逐渐构成网络。当网络中的一个同位体有可共享的文件(例如,一个音频或视频文件)时,这个文件对于其他同位体而言是可获得的。感兴趣的同位体可以与存储该文件的计算机连接并下载这个文件。在一个同位体下载这个文件之后,这个文件可用于其他同位体的下载。随着更多同位体加入和下载该文件,这个文件的更多副本就会提供到组中。由于同位体列表可能增长也可能收缩,因此问题是该模式应当如何跟踪忠实的同位体和文件位置。

集中网络

在一个集中的端到端网络中,目录系统列出同位体和它们提供了什么以使用客户机-服务器模式,但是文件的存储和下载都使用端到端模式完成。由于这个原因,集中P2P网络有时也被称为混合P2P网络。

为了寻找一个特定文件,同位体向主服务器发送一个查询要求。服务器在它的目录中搜索并给出存有该文件副本的节点的IP地址。同位体连接这些节点之一并下载文件。随着节点加入和离开同位体,这个目录一直在更新。

分散网络

在这个模型中,同位体组织形成一个在物理网络之上的逻辑网络,称为重叠网络。

在一个未结构化的P2P网络中,节点随机地连在一起。在未结构化的P2P中进行搜索不是很有效,因为寻找一个文件的查询涌入网络并造成巨大的流量,即使这样这个查询请求也不一定得到解决。

结构化的网络使用一组预设的规则来链接节点,这样一个查询就可以有效且高效地解决。为了达到这个目的,最常用的技术是分布式散列表(DHT)。很多应用都使用了DHT,包括分布式数据结构(DDS)、内容分布式系统(CDS)、域名系统(DNS)和P2P文件共享。一个使用DHT的常用P2P文件共享协议是BT下载。

6.3 传输层

TCP/IP协议族中的传输层位于应用层和网络层之间,它从网络层接收服务并且为应用层提供服务。传输层作为一个客户程序和服务器程序之间的联络,是一个过程间连接。传输层是TCP/IP协议族的核心部分,它是一个在网络中从一点向另一点进行数据传输的端与端之间逻辑媒介。

传输层服务

进程间通信

传输层的第一个义务是提供进程间通信。一个进程是使用传输层服务的应用层实体(运行中的程序)。

网络层负责在计算机层面的通信(主机间通信)。网络层协议只能将信息传输到目的计算机。然而,这是一个不完整的传递,这个消息仍然需要被传递给正确的进程。这就是传输层协议的工作,它的责任是将消息送抵相应的进程。

地址:端口号

在主机上的进程叫做客户程序,客户程序需要来自通常运行在远程主机上的进程提供的服务,这个运行在远程主机上的进程叫做服务器程序。这两个进程(客户和服务器程序)有着相同的名称。

本地主机和远程主机用IP地址进行定义。为了定义这些进程,我们需要第二个标识符,称为端口号。在TCP/IP协议族中,端口号是0和65535(16位)之间的整数。

用来定义客户程序的端口号叫做临时端口号。临时这个词的意思是短命的,用在这里是因为客户程序的使用寿命通常很短。临时端口号建议使用大于1023的数,这样一些客户/服务器程序才能正常运行。服务器程序也必须定义一个端口号。然而,这个端口号不可以随机选择。TCP/IP协议族已经决定给服务器使用通用端口号,这些端口号被称为知名端口号。每一个客户进程知道相应服务器进程的知名端口号。

传输层协议

用户数据报协议

用户数据报协议(UDP)是不可靠的无连接传输协议。它除了提供进程间通信而不是主机间通信以外,没有向网络层服务添加任何东西。

UDP是一个极简单同时开销最少的协议。如果一个进程想要发送一条短的消息且不关心可靠性,那么就可以使用UDP。

用户数据报

UDP数据包,也叫做用户数据报,有一个固定大小为8字节的头。图6-22展示了用户数据报的格式。然而,由于UDP用户数据报是存储在总长度为65535字节的IP数据报中的,所以其整体长度会比较短。

传输控制协议

传输控制协议(TCP)是一个面向连接的可靠协议。它明确地定义了连接设施、数据传输和连接拆卸段以提供面向连接的服务。这里面向连接的服务指的是在(来自应用层的)同一消息中的所有数据包(段)之间有连接(关联)。TCP使用序列号来定义段的顺序。序列号与每一段的字节数有关

在传输层,TCP将一些字节组合成一个叫做段的数据包。TCP在每一段之前加上一个头(目的是方便控制),并且将这些段发送至网络层进行传输。这些段都封装在IP数据报里并如图6-23所示进行传输。

6.4 网络层

TCP/P协议族中的网络层负责源到目的地(计算机到计算机或主机到主机)的消息发送

源主机、目标主机和路径中的所有路由器(R2、R4、RS和R7)都涉及网络层。在源主机(Alice)处,网络层从传输层接收了一个数据包,它将数据包封装在一个数据报中,并且发送至数据链路层。在目标主机(Bob)处,这个数据报就被解除封装取出数据包并发送至相应的传输层。

路径中的路由器通常与两个数据链路层和两个物理层同时展示,因为它从一个网络接收数据包,然后将该数据包传递至另一网络。

网络层提供的服务

网路层在传输层的下面,这就意味着网络层要向传输层提供服务。

打包

网络层的第一个义务就是定义打包:在源主机的网络层数据包中封装有效负荷(从上层接收的数据),并且从来自目的主机网络层的数据包中解封装有效负荷。

网络层的服务就是一个邮局式的传递者,它负责将数据包从发送者送至接收者,同时保证数据包的内容不被改变或使用。

如果在源主机或在路径中的路由器处时数据包为碎片状,网络层有责任等待直到所有碎片到达,对它们重新组合并发送至上层协议。

传输层的有效负荷可以封装在几个网络层数据包中。

数据包传递

不可靠传递

在网络层传递的数据包是不可靠的,这意味着这些数据包可能毁损、丢失或者重复。换句话说,网络层提供的是尽力而为的传输,但是它不能保证这个数据包如我们所期待的那样到达目的地。

我们要通过使用传输层协议中的TCP协议才能保证消息没有毁损。如果在传输层的一个有效负荷(由于数据链路层的不可靠传递)毁损了,TCP会丢弃这个数据包并且要求重新发送。

无连接传递

网络层对每个数据包的处理是单独的

属于相同传输层有效负荷的数据包之间是没有联系的。如果一个传输层数据包由4个网络层数据包构成,那么无法保证这4个数据包到达的顺序与它们发送的顺序相同;这是由于每个数据包都可能依照不同的路径到达目的地。

路由

网络层为将数据包从它的源传送到目的地而负责。物理网络是网络(LAN和WAN)和连接这些网络的路由器的集合,这意味着从源到目的地有不止一条路线。网络层的责任是在这些可能的路线中找到最优路线,它需要有一些特定的策略来定义最优路线。在现在的网络中,这个得通过在数据包到达时运行一些路由协议来帮助多个路由器协调它们对于周边的知识并且提出一致的路由表来实现。

网络農协议

最主要的协议叫做网际协议(IP)

第4版网际协议(IPv4)

现在大多数系统都使用第4版网际协议(IPv4),但是这将在未来改变,因为该协议的地址空间和数据包格式较小(以及其他原因)。

IPv4地址

在TCP/IP协议族的IPv4层中用来标记每个设备和互联网之间的连接的标识符叫做网络地址或IP地址。IPv4地址是一种32位的地址,这种地址唯一但又通用地定义了主机或路由器与网络之间的连接。IP地址是连接的地址而非主机或路由器的地址,因为如果这个设备移动到了另外一个网络中,它的IP地址可能会改变。IPv4地址是独一无二的,因为每个地址定义一个且只有一个与网络之间的连接。如果一个设备(例如路由器)有多个网络连接,那么它就有多个IPv4地址。IPv4地址也是通用的,因为这个地址系统必须被所有想要连接到网络的主机接收。

在二进制表示法中,IPV4地址展示为32位。为了使地址更便于阅读,毎8位之间会添加一个到两个空格。每8位一般被看作一个字节。为了使IPV4地址更紧湊易读,它通常写成十进制的形式,不同字节利用小数点分开。这个格式被称为带点的十进制表示法。注意,由于每个字节(8位)只有8位,因此在带点的十进制表示法中每个数字都在0~255之间。我们有时候把IPv4地址用十六进制表示。每个十六进制数字与二进制表示法中的4位等同,这意昧着一个32位的地址由8个十六进制数字构成。这种十六进制表示方法通常用于网络编程。

地址的第一部分叫做前缀,定义网络;地址的第二部分叫做后缀,定义节点(设备和网络的连接)。前缀的长度是n位,后缀的长度就是(32-n)位。前缀和后缀的长度取决于网络(组织)的站点。

IPv4数据报

IP使用的数据包叫做数据报。数据报是一种长度不一的数据包,这种数据包包括两部分:头和有效负荷(数据)。头的长度是20~60字节,并且他包含路由和传递时必要的信息。

第6版网际协议(IPv6)

新版本叫做第6版网际协议(IPv6)或新一代IP的版本是一个在扩大IPv4的地址空间的同时重新设计IP数据包的格式并修改一些辅助性协议的计划。

IPv6地址

为了防止地址耗尽,IPV6使用128位来定义任何连接到网络的设备。地址显示为二进制的或冒号十六进制的格式。第一个格式用来在计算机中存储地址,第二个格式是供人们便用的。

IPv6数据报/IPv4数据报

在这个版本下的数据报也是包括头和有效负荷(数据)两部分的长度可变的数据包。

6.5 数据链路层

TCP/IP协议族没有定义数据链路层中的任何协议。这层是网络中连接起来后可以构成因特网的区域。这些网络,有线或者无线,都接收服务并将服务提供给网络层。

在源和目标处只包括一个数据链路层,但在每个路由器处都有两个数据链路层。

节点和链接

虽然应用层、传输层和网络层的通信都是端到端的,但数据链路层的通信是节点对节点的。网络中一点的数据单元需要穿过很多网络(LAN和WAN)才能到达另外一点。这些LAN和WAN都是通过路由器连在一起的。传统上会将两个端主机和路由器看作节点,它们之间的网络看作链接。

连接节点的链接不是LAN就是WAN。

局域网

有线LAN:以太网

它的发展经历了四代:标准以太网(10Mbps)、快速以太网(100Mbps)、千兆以太网(1Gbps)和万兆以太网(10Gbps)。

标准以太网

数据可以从工作站传输至LAN的速度被定义为数据速率。在以太网中,速度是每秒一千万位。然而,这些位不是一个接着一个发送的,每组数据都被打包起来并称为帧。帧中不仅包括从发送者到目标的数据,还带有一些诸如源地址(48位)、目的地地址(48位)、数据类型、实际数据的信息和一些其他作为守卫来帮助检査传输中数据完整性的控制位。如果我们把一帧看作是一个装着发信人寄给收信人的信的信封,数据在信封内,而其他这些诸如地址之类的信息都在信封上。

快速以太网(100Mbps)

快速以太网的设计者需要使快速以太网能够与标准以太网竞争,所以大部分的协议像地址、帧格式都没有变。

千兆以太网

万兆以太网的目标是将数据速率升级至1Gbps,但是保持地址长度、帧格式以及最大和最小数据帧长度不变。

万兆以太网

设计万兆以太网的目标可以总结为升级数据速率至10Gbps,保持数据帧大小和格式不变,同时允许LAN、MAN和WAN可能的互连。这个数据速率只有此时的光纤技术可以达到。

无线LAN

在无线LAN中,传输媒介是空气,信号通常是在空气中传播的。当无线LAN中的主机互相通信时,它们在共享同样的媒介(多发访问)。

无线以太网

电气和电子工程师协会(IEEE)为无线LAN定义的规格,有时也被称为无线以太网或者WiFi(wireless fidelity的缩写)。然而,WiFi其实是一个由WiFi联盟(一个拥有超过300个成员公司的国际非盈利行业协会)认证的无线LAN。这个标准定义了两种服务:基本服务集(BSS)和扩展服务集(ESS)。第二个服务使用额外设备(接人点或AP)作为连接其他LAN或WAN的开关

蓝牙

蓝牙是一种无线LAN技术,它用于连接不同功能的设备,如电话、笔记本电脑、计算机(台式机以及笔记本电脑)、照相机、打印机,甚至是咖啡机之类的设备,只要这些设备之间的距离比较短。蓝牙LAN是一个临时网络,这也就意味这这个网络是自发的,这些有时候称为小配件的设备互相连接之后可以形成一个叫做蓝牙微网的网络。如果其中一个小设备有连入因特网的功能,则蓝牙LAN就可以连入因特网。

广域网

有线WAN

拨号上网服务

拨号网络或连接使用电话网络提供的服务来传输数据

调制解调器这个词是一个组合词,它指构成这个设备的两个功能性实体:信号调制器和信号解调器。调制器通过数据制造信号,解调器从调制信号中恢复数据。

数字用户线路(DSL)

数据用户线路(DSL)技术是现有的电话上支持高速通信中最有前途的一种。

这个系列中的第一个技术是非对称数字用户线路(ASDL)。ASDL在下游方向(从网络到居民)比在上游方向(从居民到网络)提供更快的速度(比特率)。这也是为什么它被称为非对称的。

ADSL允许用户同时使用语音频道和数据频道。上游速率可以达到1.44Mbps。

很有意思的一点是,这种情况下电话公司充当ISP,所以电子邮件或网络连接之类的服务都由电话公司自身提供。

交换式有线WAN

当今的网络不能只通过提供网络末端连接的点对点有线WAN进行操作。我们需要交换式有线WAN来连接网络的骨干网。

无线WAN

WiMax

全球互联接入(Wimax)是DSL或通过电缆连接因特网的无线版,它提供两种服务(固定 Wimax)将主要工作站与固定工作站或移动电话之类的移动工作站相连接。

手机网络

现今的另一种无线WAN是最初为语音通信而设计的手机电话,现在它也可以用于网络通信。如我们所知的那样,蜂窝式网络将地球划分成单元。移动工作站与它们该时刻所在的单元内的固定天线通信。当用户移动到另一个单元时,通信存在于移动设备和新的天线之间。

卫星网络

卫星网络是由节点组合而成的,这些节点一部分是卫星,它们提供地球上一点到另一点的通信。网络中的一个节点可以是一个卫星、一个地球工作站或者一个最终用户终端或电话。

卫星可以提供往返于地球上无论多远的任意地点处的传输功能。

6.6 物理层

物理层的角色是将从数据链路层接收的位转换成用于传输的电磁信号。

数据和信号

在物理层的通信是节点对节点的,但是节点交换的是电磁信号。

物理层的一个主要功能就是为位确定在节点间传输的路线。但是就像它代表的是节点(主机、路由器或交换机)内存中储存的两个可能的值一样,位不能直接发送到传输媒介(有线或无线);这些位在传输之前需要先转换成信号。所以物理层的主要责任是高效地将这些位转换成电磁信号。

模拟的和数字的

模拟数据这个词指连续的信息。

数字数据呈现的是离散的值。

信号也可以是模拟的或数字的。模拟信号在一个时间段中有无限种不同的等级强度,就像当波从A值移动到B值的时候,它的路径经过并包括无限个值。与之不同的是,数字信号可以只拥有有限个定义的值。

数字化传输

计算机网络是为将信息从一点发送到另一点而设计的。这个信息需要转换成数字信号或模拟信号来进行传输。如果这个数据是数据化的,需要用数数转换技术,一种将数字数据转换成数字信号的方法。如果数据是模拟的,需要使用模数转换技术,一个将模拟信号转换成数字信号的方法。

模数转换

有时候我们通过麦克风或照相机得到一个模拟信号,现在的趋向是将模拟信号转换成数字数据,因为数字信号受到噪音干扰的影响更小。

模拟传输

摸拟传输是当我们没有专用通道时的唯一选择。

数模转换

数模转换是基于数字数据的信息改变模拟信号的某个特征的过程。

模模转换

模模转换是基于模拟数据的信息改变模拟信号的某个特征的过程。

6.7 传输介质

在物理层产生的电子信号需要传输介质来从一端传输到另一端。传输介质通常在物理层之下,并且受到物理层的直接控制。我们可以说传输介质属于第0层。

在电信中,传输介质可以分为两大类:导向介质和无导向介质。

导向介质

导向介质就是那些用来提供从一个设备到另一个设备的通道的,包括双绞线、同辅电缆和光纤电缆。

非导向介质:无线

非导向介质不通过物理上的导体来传播电磁波。这种通信通常归为无线通信。信号通常在自由空间中传播,这样任何有能够接收信号的设备的人都可以使用它。

无线电波

频率在3kHz~1GHZ之间的电磁波通常叫做无线电波。它们通常用于无线电通信。

微波

频率在1~300GHz的电磁波叫做微波。微波是没有方向性的。当天线传输微波时,它们可以集中得很窄,也就是说发送和接收微波的天线需要对齐。微波没有方向性的一个最明显的优势就是一对天线可以在不和另一对天线相互千扰的情况下对齐。

红外波

红外波,频率在300GHz~400THz之间(波长在770mm~1mm之间),它可以用于短程通信。红外波的频率较高,无法穿透墙壁,这个有着明显优势的特点防止了不同系统之间的干扰,一个房间内的短程通信系统不会受到下一个房间内的另一个系统的影响。

第7章 操作系统

7.1 引言

计算机软件分成两大类:操作系统和应用程序。应用程序使用计算机硬件来解决用户的问题。另一方面,操作系统则控制计算机系统用户对硬件的访问

操作系统

操作系统是计算机硬件和用户(程序和人)的一个接口,它使得其他程序更加方便有效地运行,并能方便地对计算机硬件和软件资源进行访问。

自举过程

很小一部分内存用ROM构成,其中存有称为自举程序的小程序。当计算机被加电时,CPU计数器被设置为自举程序的第一条指令,并执行程序中的指令。这个程序唯一的职责就是把操作系统本身(需要启动计算机的那部分)装入RAM内存。当装入完成后,CPU中的程序计数器就被设置为RAM中操作系统的第一条指令,操作系统就被执行。

7.2 演化

批处理系统

批处理操作系统设计于20世纪50年代,目的是控制大型计算机。当时计算机十分庞大。用穿孔卡片进行输入数据,用行式打印机输出结果,用磁带设备作为辅助存储介质

每个运行的程序叫做一个作业。想要运行程序的程序员通过穿孔卡片将程序和数据输入计算机,并向控制器发出作业请求。

这个时代的操作系统非常简单:它们只保证计算机所有资源被从一个作业转换到另一个作业。

分时系统

为了有效使用计算机资源,多道程序的概念被引入。它可以将多个作业同时装入内存,并且仅当该资源可用时分配给需要它的作业。

多道程序带来了分时的概念:资源可以被不同的作业分享。每个作业可以分到一段时间来使用资源。

调度:给不同的程序分配资源并决定哪一个程序什么时候使用哪一种资源。

一个作业是一个要运行的程序,一个进程则是在内存中等待分配资源的程序。

个人系统

当个人计算机产生后,需要有一类适合这类计算机的操作系统。于是,单用户操作系统就应运动而生了,如DOS(磁盘操作系统)。

并行系统

人们对更快和更有效的需求导致了并行系统的设计:在同一计算机中安装了多个CPU,每个CPU可以处理一个程序或者一个程序的一部分。意味着很多任务可以并行地处理而不再是串行处理。

分布式系统

分布式系统结合了以往系统的特点和新的功能,例如安全控制。

实时系统

实时系统是指在特定时间限制内完成任务。它们被用在实时应用程序中,这些应用程序监控、响应或控制外部过程或环境。

7.3 组成部分

现代操作系统至少具有以下4种功能:存储管理、进程管理、设备管理、文件管理。就像很多组织有一个部门不归任何经理管理一样,操作系统也有这样一个部分,称为用户界面或命令解释程序,它负责操作系统与外界通信。

用户界面

每个操作系统都有用户界面,即指用来接收用户(进程)的输入并向操作系统解释这些请求的程序。一些操作系统(比如UNIX)的用户界面,被称作命令解释程序(shell)。在其他操作系统中,则被称为窗口,以指明它是一个由菜单驱动的并有着GUI(图形用户接口)的部件。

内存管理器

内存分配必须进行管理以避免“内存溢出”的错误

单道程序

在单道程序中,大多数内存用来装载单一的程序(我们考虑数据作为程序的一个部分被程序处理),仅仅一小部分用来装载操作系统。

这里内存管理器的工作是简单明了的,即将程序载入内存、运行它、再装入新程序。

程序必须能够载入内存。如果内存容量比程序小,程序将无法运行。

当一个程序正在运行时,其他程序不能运行。一个程序在执行过程中经常需要从输入设备得到数据,并且把数据发送至输出设备。但输入/输出设备的速度远远小于CPU,所以当输入/输出设备运行时,CPU处于空闲状态。而此时由于其他程序不在内存中,CPU不能其服务。这种情况下CPU和内存的使用效率很低。

多道程序

在多道程序下,同一时刻可以装入多个程序并且能够同时被执行。CPU轮流为其服务。

非交换范畴,这意味着程序在运行期间始终驻留在内存中。

交换范畴。也就是说,在运行过程中,程序可以在内存和硬盘之间多次交换数据。

分区调度

在这种模式中,内存被分为不定长的几个分区。每个部分或分区保存一个程序。CPU在各个程序之间交替服务。它由一个程序开始,执行一些指令,直到有输入/输出操作或者分配给程序的时限到达为止。CPU保存最近使用的指令所分配的内存地址后转入下ー个程序。对下一个程序采用同样的步骤反复执行下去。当所有程序服务完毕后,再转回第一个程序。当然,CPU可以进行优先级管理,用于控制分配给每个程序的CPU时间。

在这种技术下,每个程序完全载入内存,并占用连续的地址。

分区的大小必须由内存管理器预先决定。如果分区小了,有的程序就不能载入内存。如果分区大了,就会出现空闲区。

即使分区在刚开始时比较合适,但随着新程序的交换载入内存后有可能出现空闲区。

当空闲区过多时,内存管理器能够紧缩分区并删除空闲区和创建新区,但这将增加系统额外开销。

分页调度

在分页调度下,内存被分成大小相等的若干个部分,称为帧。程序则被分为大小相等的部分,称为页。页和帧的大小通常是一样的,并且与系统用于从存储设备中提取信息的块大小相等。

在这种技术下,程序在内存中不必是连续的:两个连续的页可以占用内存中不连续的两个帧。

分页调度在一定程度上提高了效率,但整个程序仍需要在运行前全部载入内存。

请求分页调度

在请求分页调度中,程序被分成页,但是页可以依次载入内存、运行,然后被另一个页代替。换句话说,内存可以同时载入多个程序的页。此外,来自同一个程序的连续页可以不必载入同一个帧,一个页可以载入任何一个空闲帧。

请求分段调度

在请求分段调度中,程序将按程序员的角度划分成段,它们载入内存中、执行,然后被来自同一程序或其他程序的模块所代替。

因为在内存中的段是等长的,所以段的一部分可能是空的。

请求分页和分段调度

请求分页和分段调度结合了两者的优点以提高系统效率。一个段也许太大而不能载入内存中的空闲区。内存可以分成很多帧,一个模块可以分成很多页,依次装入内存运行。

虚拟内存

请求分页调度和请求分段调度意味着当程序运行时,一部分程序驻留在内存中,一部分则放在硬盘上。这就意味着,例如,10MB内存可以运行10个程序。每个程序3MB,共30MB。任一时候10个程序中10MB在内存中,还有20MB在磁盘上。这里实际上只有10MB内存但却有30MB的虚拟内存。

虚拟内存意味着请求分页调度、请求分段调度,或两种都有,如今几乎所有的操作系统都使用了该技术。

进程管理器

程序、作业和进程

程序

程序是由程序员编写的一组稳定的指令,存在磁盘(或磁带)上,它可能会也可能不会成为作业。

作业

从一个程序被选中执行,到其运行结束并再次成为一个程序的这段过程中,该程序称为作业。在整个过程中,作业可能会或不会被执行,或者驻留在磁盘上等待调入内存,或者在内存中等待CPU执行,或者驻留在硬盘或内存中等待一个输入/输出事件,或者在内存中等待直到被CPU运行。

当一个作业执行完毕(正常或不正常),它又变成程序代码并再次驻留于硬盘中,操作系统不再支配该程序。需要注意的是,毎个作业都是程序,但并不是所有的程序都是作业。

进程

进程是一个运行中的程序。该程序开始运行但还未结束。换句话说,进程是一个驻留在内存中运行的作业,它是从众多等待作业中选取出来并装入内存中的作业。一个进程可以处于运行状态或者等待CPU调用。只要作业装入内存就成为一个进程。需要注意的是,每个进程都是作业,而作业未必是进程。

状态图

调度器

作业调度器

作业调度器将一个作业从保持状态转入就绪状态,或是从运行状态转入终止状态。

进程调度器

进程调度器将一个进程从一个状态转入另一个状态。

队列

为处理多个进程和作业,进程管理器使用队列(等待列表)。与每一作业或进程相关的是存有这些作业和进程信息的作业控制块或进程控制块。进程管理在队列中存储的不是作业或进程,而是作业或进程控制块。作业和进程仍保存在内存或硬盘中;它们因为太大而无法被复制到队列中。这些作业控制块或进程控制块就是等待中的作业和进程的代表。

作业队列用来保存那些等待内存的作业。就绪队列用来保存那些已经在内存中准备好运行但在等待CPU的进程。I/O队列用来保存那些正在等待I/O设备的进程。

进程管理器可以用多种策略从队列中选择下一个作业或进程;可以是先入先出(FIFO)、最短长度优先、最高优先级等。

进程同步

只要资源可以被多个用户(进程)同时使用,那么它就可能有两种有问题的状态:死锁和饿死。

死锁

死锁发生在操作系统允许一个进程运行,而不用首先检査它所必需的资源是否准备好,是否允许这个进程占有资源直到它不需要为止。

当操作系统没有对进程的资源进行限制时将会发生死锁。

死锁不是经常发生,死锁发生需要4个必要条件:

  • 互斥。一个资源只能被一个进程占有;
  • 资源占有。一个进程占有一个资源,即使在获取其他资源之前无法使用它;
  • 抢先。操作系统不能临时对资源重新分配;
  • 循环等待。所有的进程和资源包含在一个循环里,如图7-16所示。
饿死

饿死是一种与死锁相反的情况。它发生在当操作系统对进程分配资源有太多限制的时候。例如,假使一个操作系统中规定一个进程只有在所需的所有资源都为其占有时才能执行。

设备管理器

设备管理器(或者是输入/输出管理器)负责访问输入/输出设备。

  • 设备管理器不停地监视所有的输入/输出设备,以保证它们能够正常运行。管理器同样也雷要知道何时设备已经完成一个进程的服务,而且能够为队列中下一个进程服务。
  • 设备管理器为每一个输入/输出设备维护一个队列,或是为类似的输入/输出设备维护一个或多个队列。
  • 设备管理器控制用于访问输入/输出设备的不同策略。

文件管理器

现今的操作系统使用文件管理器来控制对文件的访问。

  • 文件管理器控制文件的访问。只有那些获得允许的应用程序才能够访问,访问方式也可以不同。
  • 文件管理器管理文件的创建、删除和修改。
  • 文件管理器可以给文件命名。
  • 文件管理器管理文件的存储:怎样存储,存在哪里等。
  • 文件管理器负责归档和备份。

7.4 主流操作系统

UNIX

第一,UNIX是个可移植的操作系统,它可以不经过较大的改动而方便地从一个平台移植到另一个平台。原因是它主要是由C语言编写的(而不是特定于某种计算机系统的机器语言)。第二,UNIX拥有一套功能强大的工具(命令),它们能够组合起来(在可执行文件中被称为脚本)去解决许多问题,而这一工作在其他操作系统中则需要通过编程来完成。第三,它具有设备无关性,因为操作系统本身就包含了设备驱动程序,这意味着它可以方便地配置来运行任何设备。

UNIX是多用户、多道程序、可移植的操作系统,它被设计来方便编程、文本处理、通信。

UNIX结构

内核

内核是UNIX系统的心脏。它包含操作系统最基本的部分:内存管理、进程管理、设备管理和文件管理。系统所有其他部分均调用内核来执行这些服务。

命令解释器

命令解释器是UNIX中用户最可见的部分。它接收和解释用户输入的命令。

工具

工具是UNIX标准程序,它为用户提供支持过程。常用的三个工具是:文本编辑器、捜索程序和排序程序。

应用

UNIX的应用是指一些程序,它们不是操作系统发布中的标准部分。它们是由系统管理员、专职程序员或用户编写的,提供了对系统的扩展能力。

Linux

组成

系统库

系统库含有一组被应用程序使用的函数(包括命令解释器),用于与内核交互。

系统工具

系统工具是使用系统库提供的服务,执行管理任务的各个程序。

Windows

设计目标

可扩展性

Windows被设计成具有多层的模块化体系结构。意图是允许高层随时间而改变,而不影响底层。

可移植性

像UNIX一样,Windows是用C或C++编写的

可靠性

Windows被设计成能处理包括防止恶意软件的错误条件。

兼容性

Windows被设计成能运行为其他操作系统编写的程序,或Windows早期版本。

性能

Windows被设计成对运行在操作系统顶部的应用程序,具有快速响应时间。

体系结构

HAL

硬件抽象层(HAL)为上层隐藏了硬件的差异。

内核

内核是操作系统的心脏。它是面向对象软件的一个片段。该面向对象的软件把任何实体都看成对象。

执行者

它由6个子系统构成:对象管理器、安全引用监控器、进程管理器、虚拟内存管理器、本地过程调用工具和I/O管理。

环境子系统

这些子系统被设计用来允许Windows运行那些为Windows、其他操作系统或Windows早期版本设计的应用程序。

第8章 算法

8.1 概念

非正式定义

算法是一种逐步解决问题或完成任务的方法。

8.2 三种结构

程序必定是由顺序、判断(选择)和循环这三种结构组成。已经证实其他结构都是不必要的。仅仅使用这三种结构就可以使程序或算法容易理解、调试或修改。

8.4 更正式的定义

算法是一组明确步骤的有序集合,它产生结果并在有限的时间内终止。

定义良好

算法必须是一组定义良好且有序的指令集合。

明确步骤

算法的每一步都必须有清晰、明白的定义。

产生结果

算法必须产生结果,否则该算法就没有意义。

在有限的时间内终止

算法必须能够终止(停机)。如果不能(例如,无限循环),说明不是算法。

第9章 程序设计语言

9.1 演化

计算机语言是指编写程序时,根据事先定义的规则(语法)而写出的预定语句集合。

机器语言

计算机唯一识别的语言是机器语言。

汇编语言

编程语言中接下来的演化是伴随着用带符号或助记符的指令和地址代替二进制码而发生的。因为它们使用符号,所以这些语言首先被称为符号语言。这些助记符语言后来就被称为汇编语言。

称为汇编程序的特殊程序用于将汇编语言代码翻译成机器语言。

高级语言

高级语言同汇编语言有一个共性:它们必须被转化为机器语言,这个转化过程称为解释或编译

9.2 翻译

高级语言程序被称为源程序。被翻译成的机器语言程序称为目标程序。有两种方法用于翻译:编译和解释。

解择

有些计算机语言使用解释器把源程序翻译成目标程序。解释是指把源程序中的每一行翻译成目标程序中相应的行,并执行它的过程。

解释的第一种方法

在Java语言之前的有些解释式语言(如BASIC和APL)使用一种称为解释的第一种方法的解释过程

在这种解释中,源程序的每一行被翻译成被其使用的计算机上的机器语言,该行机器语言被立即执行。如果在翻译和执行中有任何错误,过程就显示消息,其余的过程就被中止。程序需要被改正,再次从头解释和执行。

解释程序的第二种方法

源程序到目标程序的翻译分成两步进行:编译和解释。Java源程序首先被编译,创建Java的字节代码,字节代码看起来像机器语言中的代码,但不是任何特定计算机的目标代码,它是一种虚拟机的目标代码,该虚拟机称为Java虚拟机或JVM。字节代码然后能被任何运行JVM模拟器的计算机编译或解释,也就是运行字节代码的计算机只需要JVM模拟器,而不是Java编译器。

翻译过程

词法分析器

词法分析器一个符号接一个符号地读源代码,创建源语言中的助记符表。

语法分析器

词法分析器分析一组助记符,找出指令。

语义分析器

语义分析器检查语法分析器创建的句子,确保它们不含有二义性。计算机语义通常是无二义性的,这意味着这一步骤或者是在翻译器中被省略,或者是其责任被最小化。

代码生成器

在无二义性指令被语义分析器创建之后,每条指令将转化为一组程序将要在其上运行的计算机的机器语言。

9.3 编程模式

模式是计算机语言看待要解决问题的一种方式。计算机语言可分成4种模式:过程性(强制性)、面向对象、函数式和声说式。

过程式模式

在过程式模式(或强制性模式)中,我们把程序看成是操纵被动对象的主动主体。

过程式模式下的程序就是主动主体,该主体使用称为数据或数据项的被动对象。作为被动对象的数据项存储在计算机的内存中,程序操纵它们。为了操纵数据,主动主体(程序)发出动作,称之为过程。

在过程式模式中,对象(文件)和过程(print)是完全分开的实体。对象(文件)是一个能接收print动作或其他一些动作(如删除、复制等)的独立实体。为了对文件应用这些动作中的任何一个,我们需要一个作用于文件的过程。过程print(或复制或删除)是编写的一个独立实体,程序只是触发它。

为了避免每次需要打印文件时都编写一个新过程,我们可以编写一个能打印任何文件的通用过程。

我们需要把过程与程序触发区分开。程序不定义过程(后面解释),它只触发或调用过程。过程必须已经存在。

即使使用像加法运算符(+)这样的简单数学运算符时,我们也是正在使用一个过程调用一个已经编写的过程。

一些过程式语言

FORTRAN

FORTRAN是第一代高级语言。

FORTRAN所具备的一些特征使得40年后它仍然是科学或工程应用中的理想语言。

  • 高精度算法。
  • 处理复杂数据的能力。
  • 指数运算。
Pascal

Pascal设计时有一个特定目标:通过强调结构化编程方法来教初学者编程。

C
  • C有一个结构化的高级编程语言应有的所有高级指令,使程序员无需知道硬件细节。
  • C也具有一些低级指令,使得程序员能够直接、快速地访问硬件。相对于其他高级语言,C更接近于汇编语言,这使得它对系统程序设计员来说是一种好语言。
  • C是非常有效的语言,指令短。这种简洁吸引了想编写短程序的程序员。

面向对象模式

面向对象模式处理活动对象,而不是被动对象。

在面向对象模式中的文件能把所有的被文件执行的过程(在面向对象模式中称为方法)打包在一起,这些过程有打印、复制、删除等。在这种模式中的程序仅仅向对象发送相应请求(打印、复制、删除等),文件就会被打印、复制或删除。

这些方法被相同类型的所有对象共享。也被从这些对象继承的其他对象共享。

过程式模式中的过程是独立的实体,但面向对象模式中的方法是属于对象领地的。

相同类型的对象(如文件)需要一组方法,这些方法显示了这类对象对来自对象“领地”外的刺激的反应。为了创建这些方法,面向对象语言,如C++、Java和C#使用称为类的单元

方法

方法的格式与有些过程式语言中用的函数非常相似。每个方法有它的头、局部变量和语句。

面向对象语言实际上是带有新的理念和新的特性的过程式语言的扩展。

继承性

在面向对象模式中,作为本质,一个对象能从另一个对象继承。这个概念被称为继承性。当一般类被定义后,我们可以定义继承了一般类中一些特性的更具体的类,同时这些类具有一些新特性。

多态性

多态性意思是“许多形状”。在面向对象模式中的多态性是指我们可以定义一些具有相同名字的操作,而这些操作在相关类中做不同的事情。

一些面向对象语言

C++

它使用类来定义相似对象的通用属性以及可以应用于它们本身的各种操作。

Java

Java中的程序可以是一个应用程序也可以是一个小程序。应用程序是指一个可以完全独立运行的程序。小程序则是嵌入在超文本标记语言中的程序,存储在服务器上并由浏览器运行

在Java中,应用程序(或小程序)是类以及类实例的集合。Java自带的丰富类库是它的有趣特征之一。

Java的另一大有趣的特点是多线程。线程是指按顺序执行的动作序列。C++只允许单线程执行(整个程序作为单线程),但是Java允许多线程执行(几行代码同时执行)。

函数式模式

函数式语言主要实现下面的功能:

  • 函数式语言预定义一系列可供任何程序员调用的原始(原子)函数
  • 函数式语言允许程序员通过若干原始函数的组合创建新的函数。

说明式模式

说明式模式依据逻辑推理的原则响应査询。

逻辑推理以推导为基础。逻辑学家根据已知正确的一些论断(事实),运用逻辑推理的可靠的准则推导出新的论断(事实)。

程序员需要学习有关主题领域的知识(知道该领域内的所有已知的事实)或是向该领域的专家获取事实。程序员还应该精通如何逻辑上严谨地定义准则。这样程序才能推导并产生新的事实。

说明性语言也有自身的缺憾,那就是有关特殊领域的程序由于要收集大量的事实信息而变得非常庞大。这也是说明性程序迄今为止只局限于人工智能等领域的原因。

9.4 共同概念

标识符

所有计算机语言的共同特点之一就是都具有标识符,即对象的名称。标识符允许给程序中对象命名。

数据类型

数据类型定义了一系列值及应用于这些值的一系列操作。每种数据类型值的集合称为数据类型的域。大多数语言都定义了两类数据类型:简单数据类型和复合数据类型。

简单数据类型

筒单数据类型(有时称为原子类型、基本类型、标量类型或内建类型)是不能分解成更小数据类型的数据类型。

复合数据类型

复合数据类型是一组元素,其中每个元素都是简单数据类型或复合数据类型(这是递归定义)。大多数语言定义了如下的复合数据类型:

  • 数组是一组元素,其中每个元素具有相同类型。
  • 记录是一组元素,其中的元素可以具有不同的类型。

变量

变量是存储单元的名字。

变量声明

声明是对象创建的一部分。

字面值

字面值是程序中使用的预定义的值。

语句

子程序

参数

在主程序中称为实际参数,在子程序中称为形式参数。

传值

主程序和子程序的通信是单方向的,从主程序到子程序。主程序传递实际参数的值,存储到子程序中相应的形式参数中。从子程序到主程序没有参数的通信。

传弓旧

传引用被设计来允许子程序改变主程序中变量的值。在传引用中,变量(实际上它是内存的地址)被主程序和子程序共享。相同的变量可能在主程序和子程序中有不同的名字,但两个名字是指向同一个变量。

第10章 软件工程

10.1 软件生命周期

开发过程模型

瀑布模型

在这种模型中,开发过程只有一个方向的流动。这意味着前一个阶段不结束,后一个阶段不能开始。

瀑布模型的缺点是难以定位问题:如果过程的一部分有问题,必须检查整个过程。

增量模型

10.2 分析阶段

整个开发过程始于分析阶段,这个阶段生成规格说明文档;这个文档说明了软件要做什么,而没有说明如何去做。

面向过程分析

如果实现阶段使用过程式语言,那么面向过程分析(也称为结构化分析或经典分析)就是分析阶段使用的方法。

数据流图

数据流图显示了系统中数据的流动。它们使用4种符号:方形盒表示数据源或数据目的,带圆角的矩形表示过程(数据上的动作)。末端开口的矩形表示数据存储的地方,箭头表示数据流。

状态图

状态图提供了另外一种有用的工具,它通常用于当系统中的实体状态在响应事件时将会改变的情况下。

面向对象分析

如果实现使用面向对象语言,那么面向对象分析就是分析过程使用的。

用例图

用例图给出了系统的用户视图:它显示了用户与系统间的交互。用例图使用4种组件系统、用例、动作者和关系。系统(用矩形表示)执行功能。系统中的行动由用例显示,它用圆角的矩形表示。动作者是使用系统的某人或某事。虽然动作者用线条人物来表示,但它们并不需要表示人类。

10.3 设计阶段

设计阶段定义系统如何完成在分析阶段所定义的需求。在设计阶段,系统所有的组成部分都被定义。

在面向过程设计中,整个系统被分解成一组过程或模块。

面向过程设计

在面向过程设计中,我们既要设计过程,也要设计数据。

结构图

在面向过程设计中,说明模块间关系的常用工具是结构图

模块化

模块化意味着将大项目分解成较小的部分,以便能够容易理解和处理

耦合

耦合是对两个模块互相绑定紧密程度的度量。越紧耦合的模块,它们的独立性越差。既然目标是为了让模块尽可能地独立,你需要让它们松散耦合。至少有三条理由说明松散耦合是希望的:

  • 松散耦合的模块更可能被重用;
  • 松散耦合的模块不容易在相关模块中产生错误
  • 当系统需要修改时,松散耦合的模块允许我们只修改需要改变的模块,而不会影响到不需要改变的模块。

软件系统中模块间的耦合必须最小化。

内聚

内聚是程序中处理过程相关紧密程度的度量。我们需要尽可能最大化软件系统模块间的内聚。

软件系统模块间的内聚必须最大化。

10.4 实现阶段

程序员为面向过程设计中的模块编写程序或者编写程序单元,实现面向对象设计中的类。

软件质量

软件质量因素

可操作性

可操作性涉及系统的基本操作。

准确性

准确性能够通过诸如故障平均时间、每千行代码错误数以及用户请求变更数这样的测量指标来度量。

可靠性

一些度量直接说明了系统的可靠性,最显著的是故障平均时间。

安全性

一个系统的安全性是以未经授权的人得到系统数据的难易程度为参照的。

可维护性

可维护性以保持系统正常运行并及时更新为参照。很多系统需要经常修改,这不是因为它们不能很好地运行而是因为外部因素的改变。

可修正性

可修正性的一种度量是恢复正常的平均时间,也就是当程序发生故障后使程序恢复运行所花费的时间。

适应性

用户经常要求在系统中进行变动。适应性是个定性的属性,试图度量进行这些变动的难易程度。

可迁移性

可迁移性是指把数据和(或)系统从一个平台移动到另一个平台并重用代码的能力。在

重用性

如果编写的函数可以在不同的程序和不同的项目中使用,那么它具有很好的重用性。

互用性

互用性是发送数据给其他系统的能力。

可移植性

可移植性是一种把软件从一个硬件平台转移到另一个硬件平台的能力。

10.5 测试阶段

测试阶段的目标就是发现错误,这就意味着良好的测试策略能发现最多的错误。

白盒測试

白盒测试(或玻璃盒测试)是基于知道软件内部构的。测试的目标是检査软件所有的部分是否全部设计出来。白盒测试假定测试者知道有关软件的一切。在这种情况下,程序就像玻璃盒子,其中的每件事都是可见的

使用软件结构的白盒测试需要保证至少满足下面4条标准:

  • 每个模块中的所有独立的路径至少被测试过一次。
  • 所有的判断结构(两路的或多路的)每个分支都被测试。
  • 每个循环被测试。
  • 所有数据结构都被测试。

基本路径测试

基本路径测试是一种软件中每条语句至少被执行一次的方法。

控制结构测试

控制结构测试比基本路径测试更容易理解并且包含基本路径测试,这种方法使用下面将要简要讨论的不同类的测试。

条件测试

条件测试应用于模块中的条件表达式,简单条件是关系表达式,而复合条件是简单条件和逻辑运算符的组合。条件测试用来检査是否所有的条件都被正确设置。

数据流测试

数据流測试是基于通过模块的数据流的。这种测试选择测试用例,这些用例涉及检査被用在赋值语句左边的变量的值。

循环测试

循环测试使用测试用例检査循环的正确性。

黑盒测试

黑盒测试在不知道程序的内部也不知道程序是怎样工作的情况下测试程序。

10.6 文档

软件的正确使用和有效维护离不开文档。

文档是一个持续的过程。

用户文档

为了软件包正常运行,传统上称为用户手册的文档对用户是必不可少的。它告诉用户如何一步步地使用软件包。它通常包含一个教程指导用户熟悉软件包的各项特性。

系统文档

系统文档定义软件本身。撰写系统文档的目的是为了让原始开发人员之外的人能够维护和修改软件包。系统文档在系统开发的所有4个阶段都应该存在。

在分析阶段,收集的信息应该仔细地用文档记录。另外,系统分析员应该定义信息的来源。需求和选用的方法必须用基于它们的推论来清楚表述。

在设计阶段,最终版本中用到的工具必须记录在文档中。例如,如果结构图修改了多次,那么最终的版本要用完整的注释记录在案。

在实现阶段,代码的每个模块都应记录在文档中。另外,代码应该使用注释和描述头尽可能详细地形成自文档。

最后,开发人员必须仔细地形成测试阶段的文档。对最终产品使用的每种测试,连同它的结果都要记录在文档中。甚至令人不快的结果和产生它们的数据也要记录在案。

技术文档

技术文档描述了软件系统的安装和服务。安装文档描述了软件如何安装在每台计算机上,如服务器和客户端。服务文档描述了如果需要,系统应该如何维护和更新。

第11章 数据结构

数据结构利用了有关的变量的集合,而这些集合能够单独或作为一个整体被访问。

11.1 数组

二维数组

大多数计算机使用行主序存储,其中数组的一个整行在内存上存储在下一个行之前。但是计算机也可以使用列主序存储,其中一个整列在内存上存储在下一个列之前。

11.2 记录

记录是一组相关元素的集合,它们可能是不同的类型,但整个记录有一个名称。记录中的每个元素称为域。域是具有含义的最小命名数据。它有类型且存在于内存中。它能被赋值,反之也能够被选择和操纵。域不同于变量主要在于它是记录的一部分。

在记录中的元素可以是相同类型或不同类型,但记录中的所有元素必须是关联的

记录名与域名

记录的名字是整个结构的名字,而每个域的名字允许我们存取这些域。

第12章 抽象数据类型

12.1 背景

复杂抽象数据类型

抽象概念意味着:

  1. 知道一个数据类型能做什么。
  2. 如何去做是隐藏的。

定义

抽象数据类型就是与对该数据类型有意义的操作封装在一起的数据类型。然后,用它封装数据和操作并对用户隐藏。

抽象数据类型的模型

图中不规则轮廓中的浅阴影区域部分表示模型。在这个抽象区域内部是该模型的两个部分:数据结构和操作(公有的和私有的)。应用程序只能通过接口访问公有操作。接口是公有操作和传给或从这些操作返回的数据的列表。私有操作是抽象数据类型内部用户使用的。数据结构(如数组、链表)在抽象数据类型里面,被公有和私有操作使用。

实现

计算机语言不提供抽象数据类型包。要使用抽象数据类型,首先要实现它们,把它们存储在库中。

12.4 广义线性表

  • 元素具有相同的类型;
  • 元素顺序排列,这意味着有第一个元素和最后一个元素;
  • 除第一个元素外每个元素都有唯一的前驱;除最后一个元素外每个元素都有唯一的后继;
  • 每个元素是一个带有关键字段的记录;
  • 元素按关键字值排序。

12.5 树

树包括一组有限的元素,称为节点(或顶点),同时包括一组有限的有向线段,用来连接节点,称为弧。如果树是非空的,其中有一个节点没有进入的弧,该节点称为根。树中的其他节点都可以沿着从根开始的唯一路径到达,该路径是指一系列相邻连接的节点序列。

从一给定节点可以直接到达(通过一个弧)的节点称为子节点;从其出发子节点可以直接到达的节点称为双亲。具有相同双亲的节点称为兄弟节点。节点的子孙是指从该节点出发可以到达的所有节点,而从其出发所有的子孙都可以到达的节点称为祖先。树中每个节点都有可能有子树。

二叉树的递归定义

二叉树是一棵空树或由一个根节点和两棵子树构成,而每棵子树也是二又树。

第13章 文件结构

13.1 引言

文件存储在辅助存储设备或二级存储设备中。两种最常见的二级存储设备是磁盘和磁带。文件在二级存储设备中是可读写的。文件也可以以计算机只能写不能读的形式存在。

文件是数据记录的集合,每一个记录都由一个或多个域组成。

存取方法决定了怎样检索记录

随机存取

如果想存取某一特定记录而不用检索其之前的所有记录,则使用允许随机存取的文件结构。

13.2 顺序文件

顺序文件是指记录只能按照顺序从头到尾一个接一个地进行存取。

更新顺序文件

需要更新的文件

和更新程序有关的一共有4个文件:新主文件、旧主文件、事务文件和错误报告文件。所有这些文件根据关键字值被分类。

更新完成之后,新主文件要被送到脱机存储器中去,直到再次需要为止。当文件被更新时,主文件将从脱机存储器中检索返回,成为旧主文件。

  • 新主文件。新的永久数据文件通常称为新主文件。
  • 旧主文件。它是需要更新的永久文件。即使在更新后,旧主文件作为参考将继续保留。
  • 事务文件。第三种文件是事务文件。它包含将要对主文件作的改变。在所有的文件更新中,一共有三种基本类型的改变。添加事务包含将要追加到主文件中的新数据。删除事务把将要从文件中删除的记录标识出来。而更改事务则包含对文件中特定记录的修改。要处理这些事务就需要键。键就是文件中一个或多个能唯一标识数据的字段。
  • 错误报告文件。错误报告包括在数据更新时所发现的错误的清单,并且提供给用户以进行纠错操作。

文件更新过程

更新过程要求比较事务文件和主文件中的键,假定在没有错误发生的情况下,更新过程遵循以下步骤

1)如果事务文件的键小于主文件的键,事务就是一个增加事务文件(A),则将事务追加到新主文件中。

2)如果事务文件的键与主文件的相同,则

a.如果事务是修改(C),则修改主文件数据。

b.如果事务是删除(D),则将数据从主文件中删除。

3)如果事务文件的键大于主文件的键,将旧主文件记录写人新主文件。

4)有几种情况可能产生一个错误,错误被记录在错误报告文件中

a.如果事务定义追加一个旧主文件中已经存在的记录(相同键值)。

b.如果事务定义删除或修改一个旧主文件中不存在的记录。

13.3 索引文件

索引文件可以把账号和记录地址关联起来

索引文件由数据文件组成,它是带索引的顺序文件

存取文件中的记录需按以下步骤:

1)整个索引文件都载入内存中(文件很小,只占用很小的内存空间)。

2)搜索项目,用高效的算法(如折半査找法)査找目标键

3)检索记录的地址。

4)按照地址,检索数据记录并返回给用户。

倒排文件

索引文件的好处之一就是可以有多个索引,每个索引有不同的键。

这种索引文件被称为倒排文件。

13.4 散列文件

散列文件用一个数学函数来完成映射。用户给出键,函数将键映射成地址,再传送给操作系统,这样就可检索记录了(图13-7)。

散列文件无需额外的文件(索引)。

散列文件中,用函数来寻找地址。这里不需要索引和随之而来的所有开销。

散列方法

直接散列法

在直接散列法中,键是未经算法处理的数据文件地址。文件因此必须对每个可能的键都包含一个记录。

求模法

求模法也称为除余散列法,求模方法用文件大小去除键后,将余数加1作为地址。

一个为素数的列表大小要比其他的列表大小产生更少的冲突。因此只要可能,尽量用素数作为文件的大小。

数宇析取法

如果用数字析取散列法,则选择从键中析取的数字作为地址。

冲突

有可能多于一个的键将被散列为文件中的同一个地址。我们把列表中一些映射为同一地址的键称为同义词。

冲突的产生是在散列算法为插入键产生地址时,发现该地址已被占用。由散列算法产生的地址称为内部地址。包含所有内部地址的区域称为主区。当两个键在内部地址上冲突时,必须将其中一个键和数据存放到主区外的另一个地址单元中来解决冲突。

冲突解决法

开放寻址

当一个冲突发生时,主区地址将査找开放的或空闲的记录来用于存放新数据。对于不能在内部地址中存放的数据, 一种简单的策略就是把该数据存储在内部地址的下一个地址中去(内部地址+1)。

开放寻址的一个主要缺点是每个冲突的解决增加了将来冲突的可能性。

链表第决法

在这种方法中,第一条记录存储在内部地址,但它包含了一个指向下一条记录的指针

桶散列法

另一种处理冲突的方法是散列到桶。

桶是一能接纳多个记录的节点。这种方法的缺点是可能有很多浪费的(未占用的)存储单元。

组合方法

复袭的实现方法通常是组合使用多种方法,

13.5 目录

目录是大多数操作系统提供的,用来组织文件。

在大多数操作系统中,目录被表示为含有其他文件信息的一种特殊文件类型。目录的作用不仅仅像一种索引文件,该索引文件告诉系统文件在辅助存储设备上的位置,目录还包含了关于它所包含的文件的其他信息,如:谁有访问文件的权限,文件被创建、存取和修改的日期。

UNIX操作系统中的目录

在目录结构的顶部是一个称为根的目录。虽然它的名字是根,但在与目录有关的命令中,它被输入为正斜杠(/)。

特殊目录

根目录

根目录是文件系统层次结构的最高层。它是整个文件结构的根,因此它没有父目录。在UNIX的环境中,根目录总是有几层子目录。根目录属于系统管理员,只有系统管理员能修改它。

主目录

这个目录包含我们在其中创建的任何文件,还可能包含个人系统文件。主目录也是个人目录结构的开始。每个用户都有一个主目录。

工作目录

工作目录(或当前目录)是在用户会话中在任意点我们所“在”的目录。

父目录

父目录是工作目录的直接上层目录。

路径和路径名

为了唯一地标识一个文件,我们需要指明从根目录到文件的文件路径。文件路径由它的绝对路径名来指明,它是斜线字符(/)分隔的所有目录的列表。

13.6 文本文件和二进制文件

存储在存储设备上的文件是一个位的序列,可被应用程序翻译成一个文本文件或是二进制文件

文本文件

文本文件是一个字符文件。在它们的内存储器格式中不能包含整数、浮点数或其他数据结构。要存储这些类型的数据,必须把它们转换成对应的字符格式。

一些文件只能用字符数据格式。值得注意的是用于键盘、监视器和打印机的文件流(像C++面向对象语言中的输入/输出对象)。这也是为什么需要特殊的函数来格式化丄述设备的输入或输出数据。

二进制文件

二进制文件是计算机的内部格式存储的数据集合,在这种定义中,数据可以是整型(包括其他表示成无符号整数的数据类型,例如图像、音频或视频)、浮点型或其他数据结构(除了文件)。

二进制文件中的数据只有当被程序正确地解释时才有意义。

第14章 数据库

14.1 引言

数据的存储传统上是使用单独的没有关联的文件,有时称为平面文件。

定义

数据库是一个组织内被应用程序使用的逻辑相一致的相关数据的集合。

数据库的优点

  1. 冗余较少
  2. 避免不一致性
  3. 效率
  4. 数据完整性
  5. 机密性

数据库管理系统

数据库管理系统(DBMS)是定义、创建、维护数据库的一种工具。DBMS也允许用户来控制数据库中数据的存取。

硬件

硬件是指允许物理上存取数据的计算机硬件系统。

软件

软件是指允许用户存取、维护和更新物理数据的实际程序。另外,软件工具还可以控制哪些用户可以对数据库中的哪部分数据进行存取。

数据

数据是独立于软件的一个实体。这种独立使得组织可以在不改变物理数据及其存取方式的情况下,更换所应用的软件。

用户

最终用户

最终用户指直接从数据库中获取信息的用户。最终用户又可分为两类:数据库管理员(DBA)和普通用户。数据库管理员拥有最大的权限,可以控制其他用户以及他们对数据库的存取。数据库管理员可以将他的一些特权授予其他用户并保留随时收回特权的能力。而另一方面,普通用户只能使用部分数据库和有限的存取。

应用程序

数据库中数据的其他使用者就是应用程序。应用程序需要存取和处理数据。

规程

必须被明确定义并为数据库用户所遵循的规程或规则的集合。

14.2 数据库体系结构

内层

内层决定了数据在存储设备中的实际位置。这个层次处理低层次的数据存取方法和如何在存储设备间传输字节。换句话说,内层直接与硬件交互。

概念层

概念层定义数据的逻辑视图。在该层中定义了数据模式。数据库管理系统的主要功能(如查询)都在该层。数据库管理系统把数据内部视图转化为用户所看到的外部视图。概念层是中介层,它使得用户不必与内层打交道。

外层

外层直接与用户(最终用户或应用程序)交互。它将来自概念层的数据转化为用户所熟悉的格式和视图。

14.3 数据库模型

数据库模型定义了数据的逻辑设计,它也描述了不同数据之间的联系。

层次模型

层次模型中,数据被组织成一棵倒置的树。每一个实体可以有不同的子节点,但只能有一个双亲。层次的最顶端有一个实体,称为根。

网状模型

网状模型中,实体通过图来组织,图中的部分实体可通过多条路径来访问。这里没有层次关系。

关系模型

关系模型中,数据组织成称为关系的二维表,这里没有任何层次或网络结构强加于数据上,但表或关系相互关联

14.4 关系数据库模型

关系

从表面上看,关系就是二维表。在关系数据库管理系统中,数据的外部视图就是关系或表的集合,但这并不代表数据以表的形式存储。数据的物理存储与数据的逻辑组织的方式毫无关系。

关系数据库管理系统中的关系有下列特征:

  • 名称:在关系数据库管理系统中,每一种关系具有唯一的名称。
  • 属性:关系中的每一列都称为属性,属性在表中是列的头。每一个属性表示了存储在该列下的数据的含义。表中的每一列在关系范围内有唯一的名称。关系中属性的总数称为关系的度。注意属性名并不存储在数据库中,概念层中使用属性给每一列赋予一定的意义。
  • 元组:关系中的行叫做元组。元组定义了一组属性值,关系中元组的个数叫关系的基数。

14.5 关系的操作

结构化查询语言

结构化查询语言(SQL)是美国国标协会(ANSI)和国际标准组织(ISO)用于关系数据库上的标准化语言。这是一种描述性(不是过程化)的语言,这意味着使用者不需要一步步地编写详细的程序而只需声明它。

插入

插入是一元操作,它应用于一个关系。其作用是在表中插入新的元组。插人操作使用如下的格式:

value子句定义了要插入的相应元组的所有属性。

删除

删除也是一元操作。根据要求删除表中相应的元组。删除操作使用如下格式:

删除的条件是由where子句定义的。

更新

更新也是一元操作,它应用于一个关系。用来更新元组中的部分属性值。更新操作使用如下格式

要改变的属性定义在set子句中,更新的条件定义在where子句中。

选择

选择也是一元操作。它应用于一个关系并产生另外一个新关系。新关系中的元组(行)是原关系元组的子集。选择操作根据要求从原表中选择部分元组。选择操作使用如下格式

星号(*)表示所有的属性都被选择。

投影

投影也是一元操作。它应用于一个关系并产生另外一个新关系。新表中的属性(列)是原表中属性的子集。投影操作所得到的新关系中的元组属性减少,但元组(行)的数量保持不变。投影操作使用如下的格式:

连接

连接是二元操作。它基于共有的属性把两个关系组合起来。连接操作使用如下格式:

属性表是两个输入关系的属性组合。条件明确地定义了作为相同属性的属性。

并也是二元操作。它将两个关系合并成一个新的关系。不过这里对两个关系有一个限制,即它们必须有相同的属性。并操作,类似于集合论中的定义,新关系中的每一个元组或者在第一个关系、第二个关系,或者在两个关系中皆有。并操作使用如下格式:

这里星号仍然是代表所有属性都被选择。

交也是二元操作。它对两个关系操作,创建一个新关系。和并操作一样,进行交操作的两个关系必须有相同的属性。交操作,类似于集合论中的定义,新关系中的每一个元组必须是两个原关系中共有的成员。交操作使用如下格式:

差也是二元操作。它应用于具有相同属性的两个关系。生成的关系中的元组是那些存于第一个关系中而不在第二个关系中的元组。差操作使用如下格式:

14.6 数据库设计

实体关系模型(ERM),这种模型定义了其一些信息需要维护的实体、这些实体的属性和实体间的关系。

实体关系模型

在这一步,数据库设计者建立了实体关系(E-R)图来表示那些其信息需要保存的实体和实体间的关系。

  • 矩形表示实体集。
  • 椭圆形表示属性。
  • 菱形表示关系集。
  • 线连接属性和实体以及连接实体集和关系集。

关系(用菱形表示的)可以是一对一,一对多、多对一和多对多。

从E-R图到关系

实体集上的关系

对于E-R图中的每个实体集,我们都创建一个关系(表),这些关系具有n个列,对应于这个集合所定义的n个属性。

关系集上的关系

对于E-R图中的每个关系集,我们都创建一个关系(表),这个关系中有一个列对应于这个关系所涉及的实体集的关键字,如果关系有属性(本例中没有),这个关系还可以有关系本身的属性对应的列。

规范化

规范化是一个处理过程,通过此过程给定的一组关系转化成一组具有更坚固结构的新关系。规范化要允许数据库中表示的任何关系,要允许像SQL这样的语言去使用由原子操作组成的恢复操作,要移除插入、删除和更新操作中的不规则,要减少当新的数据类型被加入时对数据库重建的需要。

规范化过程定义了一组层次范式(NF)。

第一范式(1NF)

当我们把实体或关系转换成表格式的关系时,可能有些关系的行或列的交集有多个值。

第二范式(2NF)

在每个关系中,我们需要有一个关键字(称为主键),所有其他的属性(列值)都依赖于它。

但是,当关系是根据E-R图建立时,我们可能有一些复合的关键字(两个或两个以上关键字的组合)。在这种情况下,如果每一个非关键字属性都依赖于整个复合关键字,那么这个关系就是第二范式的。

如果有些属性只依赖于复合关键字的一部分,那这个关系就不是第二范式的。

14.7 其他数据库模型

分布式数据库

数据库中的数据存储在一些通过因特网(或一些私有的广域网)通信的计算机上。每台计算机(或者站点)拥有部分或全部数据库。

不完全的分布式数据库

在不完全的分布式数振库中,数据是本地化的。本地使用的数据存储在相应的站点上。但是,这并不意味着一个站点不能访问存储在其他站点的数据。访问大部分情况下是本地的,但偶尔又是全局的。虽然站点对存储的本地数据具有完全控制权,但是通过因特网或广域网,还存在一个全局的控制。

复制式的分布式数据库

在复制式的分布式数据库中,每个站点都有其他站点的一个完全副本。对一个站点数据的修改将会在其他站点的副本数据上重复。

面向对象数据库

面向对象数据库在试图保留关系模型优点的同时允许应用存取结构化数据。在面向对象数据库中,定义了对象和它们的关系。另外,每一个对象可以具有属性并以域的形式表达

XML

通常用作面向对象数据的查询语言是XML(Extensible Markup Language)。

第15章 数据压缩

15.1 引言

15.2 无损压缩

在无损数据压缩中,数据的完整性是受到保护的。原始数据与压缩和解压后的数据完全一样。因为在这种压缩方法中,压缩和解压算法是完全互反的两个过程,在处理过程中没有数据丢失。冗余的数据在压缩时被移走,在解压时再被加回去。

游程长度编码

这种算法的大致思想是将数据中连续重复出现的符号用一个字符和这个字符重复的次数来代替。

赫夫曼编码

在赫夫曼编码中,对于出现更为频繁的字符分配较短的编码,而对于出现较少的字符分配较长的编码。

首先,出现频率高的字符的编码要比出现频率低的宇符的编码短。这点可以通过比较分配给各个字符的编码适当的位长度看出。其次,在这个编码系统中,没有一个编码是其他编码的前缀。

编码

赫夫曼编码的好处就是没有一个编码是其他编码的前缀,这样在编码过程中没有二义性,接收方接收到数据解压缩时也不会产生二义性。

译码

译码器可以即时明确地翻译出编码(在最小位数下)。

Lempel Ziv编码

Lempel Ziv(LZ)编码是称为基于字典的编码的那一类算法的一个例子,它是用其发明者的名字(Abraham Lempel和Jacob Ziv)命名的。在通信会话的时候它将产生一个字符串字典(一个表)。如果接收和发送双方都有这样的字典,那么字符串可以由字典中的索引代替,以减少通信的数据传输量。

压缩

算法从未压缩的字符串中选取最小的子字符串,这些子字符串在字典中不存在。然后将这个子字符串复制到字典(作为一个新的记录)并为它分配一个索引值。压缩时,除了最后一个字母之外,其他所有字符被字典中的索引代替。然后将索引和最后一个字母插入压缩字符串。

解压

15.3 有损压缩方法

联合图像专家组(JPEG)用来压缩图片和图像,运动图像专家组(MPEG)用来压缩视频,MPEG第三代音频压缩格式(MP3)则用来压缩声音。

图像压缩:JPEG

JPEG的整体思想是将图像变换成一个数的线性(矢量)集合来揭示冗余。这些冗余(缺乏变化的)可以通过使用前面学过的无损压缩的方法来除去。

离散余弦变换

在此步骤中,每个64像素块都要用离散余弦变换(DCT)进行变换。这种变换改变了64个值以使相邻像素之间的关系得以保持,但同时又能够揭示冗余。

$P(x,y)$定义了每个块上的值;$T(m,n)$则定义了变换后的块的值。

  • 转换从$P$表生成$T$表。
  • DC值是像素的平均值
  • AC值显示变化。

量化

生成$T$表后,这些值将被量化以减少需要编码的位数。量化过程用一个常量来除位数,然后舍弃小数部分。这样可以更加减少需要编码的位数。在大多数实现方法中,通过一张量化表$(8\times 8)$定义了如何量化每个值,其中除数取决于表位置上的值。这样做可以对每一个特殊的应用程序优化位数和0的个数。

注意在整个过程中只有量化阶段是不可逆的。在这里所失去的一些信息是不能恢复的。

压缩

量化后,将表中的值读出并去掉多余的0。但是,为了把0聚集起来,整个压缩过程以Z字形按对角线读取表,而不是按行或列。原因是如果图像没有很好的变化,$T$表底部的右下角将全为0。

JPEG在压缩阶段通常使用游程长度编码来压缩从Z字形线性化读取的位模式。

视频压缩:MPEG

时间压缩

在时间压缩中,多余的帧将被丢弃。

  • I-帧:即内部编码帧(I-帧),是一个独立帧,该帧与任何其他帧(即在其前发送的帧或者在其后发送的帧)无关。它们以周期性间隔出现。I-帧独立于其他帧之外,而且不能由其他帧构造,
  • P-帧:即预帧(P-帧),与前面的-帧或P-帧有关联。换句话说,每个P-帧都从前面帧变化而来。
  • B-帧:即双向帧(B-帧),与前面和后续的I-帧或P-帧有关系。换句话说,每个B帧都与过去和将来有关系。

版本

MPEG的最近的一个版本称为MPEG-7,它叫作“多媒体内容描述接口”。MPEG-7大部分是使用XML描述元数据(关于数据的数据)和对视频中所含内容的描述的标准。

音频压缩

预测编码

在预测编码中,样本间的差别被编码,而不是对所有的样本值进行编码。

感知编码:MP3

用来创建CD质量音频最常用的压缩技术是基于感知编码技术的。

感知编码是基于心理声学的,心理声学是一门研究人类是如何感知声音的科学。想法是基于我们听觉系统的瑕疵,有些声音能够掩盖其他声音。掩盖可以发生在频率上和时间上。在频率掩盖中,一个频率范围的高的声音可以部分或完全掩盖另一个频率范围的低的声音。在时间掩盖中,一个高音可以短时间内降低我们听觉的灵敏度,甚至在声音停止之后。

MP3使用这两种现象(频率掩盖和时间掩盖)来压缩音频信号。该技术分析音谱并把音谱分成几个组。0位被赋给了那些频率范围被完全掩盖的,小数值的位被赋给了那些频率范围部分被掩盖的。大数值的位被赋给了那些不被掩盖的。

第16章 安全

16.1 引言

安全目标

我们将首先讨论三个安全目标:机密性、完整性和可用性。

完整性

完整性的意思是变化只应该由授权的实体通过授权的机制来完成。完整性冲突不一定是由于恶意行为造成的,它也可能是系统中断(例如短路)造成的对信息的一些不希望的改动。

可用性

一个组织创建和存储的信息对授权实体来说应该是可用的。如果信息是不可用的,那它就是无用的。信息需要时常改变,这就意味着它必须对那些被授予访问权限的实体是可以访问的。

攻击

威胁机密性的攻击

嗅探

嗅探是指对数据的非授权访问或侦听。

流量分析

通过在线流量监控收集其他类型的信息

威胁完整性的攻击

篡改

侦听或访问信息后,攻击者篡改信息,使得信息有利于他们。

假冒

当攻击者冒充其他人时,假冒或“哄骗”就发生了。

重放

攻击者得到用户发送的消息的副本,过后设法重放它。

抵赖

抵赖是一种不同于其他类型的攻击,因为它是由通信双方中的一个来进行的:发送者或接收者。消息的发送者后来可能抵赖他发送了消息;消息的接收者后来也可能抵赖他接收到消息。

威胁可用性的攻击

拒绝服务(DoS)攻击是很常见的,它可能减慢或完全中断系统的服务。攻击者能使用几种策略取得这样的效果。他们可能通过发送大量虚假请求使系统变得非常忙碌而崩溃,或他们可能侦听并删除服务器对客户端的响应,使客户端相信服务器未响应。攻击者也通过侦听客户端的请求,使得客户端多次发送请求导致系统变得非常忙碌。

服务和技术

密码术

虽然在过去密码术只是指使用密钥进行消息的加密和解密,但如今它被定义成三种不同的机制:对称密钥密码、非对称密钥密码和散列。

隐写术

密码术就是通过加密把消息中的内容隐藏起来;而隐写术是通过在消息上覆盖其他内容而隐藏消息。

16.2 机密性

对称密钥密码术

对称密钥密码术使用了同一个密钥进行加密和解密,并且这个密钥可以用来进行双向通信,这就是为什么它被称为对称的。

对称密钥密码术也称为保密密钥密码术。

传统对称密钥密码

替换密码

替换密码用一个符号替换另一个符号。如果在明文中的符号是字母表的字符,我们用另一个字符来代替。

单字母密码

在单字母密码中,明文中相同的字符(或符号)在密文中用相同的字符(或符号)替换,与该字符在明文中的位置无关。

在加法密码中,明文、密文和密钥都是模26中的整数

多字母密码

在多字母密码中,字符的每一次出现都使用不同的替换码。明文中字符和密文中字符的关系是一对多,

多字母密码具有可以隐藏原有语言的字母频率的作用,即使通过单字母频率统计都无法破解密文。

为了创造一个多字母密码,我们对每一个密文字符的确定都不仅取决于相对应的明文字符,还与该明文字符在原来文本中的位置有关。这意味着我们的密钥应该是子密钥流,这个子密钥流中的每一个子密钥都在某种程度上取决于使用该子密钥进行加密的明文字符的位置。

在这个密码中,密钥是一个密钥流,在这个子密钥流中的每一个子密钥都用来对明文文本中的对应字符进行加密。

这种密码的名字”自动密钥密码”说明了这些子密钥都是在加密过程中通过明文密码字符自动创造的。

移位密码

移位密码就是符号重新排序。

流密码

在流密码中,加密和解密都是一次只对一个符号(例如一个字符或位)进行。我们有个明文流、一个密文流和一个密钥流。将明文流称为P,密文流称为C,密钥流称为K。

分组密码

在分组密码中,一组大小为m(m>1)的明文符号被加密在一起,创造一组同样大小的密文。基于定义,在一个分组密码中,整个分组是由一个单独的密钥进行加密,即使这个密钥由多个值构成。在分组密码中,密文的分组取决于整个明文分组。

组合

在实际操作中,每个明文分组是分别加密的,但是同时密钥流被用来对整个消息按照分组依次加密。

每个分组都使用一个不同的密钥进行加密,这些密钥是在加密进行之前或进行过程中产生的。

现代对称密钥密玛

传统对称密钥密码都是面向字符的密码。由于计算机的进步,我们需要面向位的密码。

现代分组密码

对称密钥现代分组密码对大小为n位的明文分组进行加密或对同样大小的密文分组进行解密。加密或解密算法使用k位的密钥。

现代流密码

在现代流密码中,加密和解密都是每次对r位进行。

流密码比分组密码更快,它的硬件实现也更简单一些。当我们需要对二进制流加密并将加密后的流匀速传输时,流密码是一个更好的选择。流密码对于传输中发生的损毁也有更好的免疫能力。

最简单也最安全的同步流密码是吉尔伯特·弗纳姆发明并取得专利的一次一密乱码。一次一密乱码每次加密时使用随机选择的密钥流。加密和解密都使用单一的异或操作。

非对称密钥密码术

在对称密钥密码术中,密码必须在双方之间共享。在非对称密钥密码术中,秘密是个人独有的(非共享的),每个人创造并保守个人的秘密。

对称密钥密码术基于共享保密;非对称密钥密码术基于个人保密。

在非对称密钥密码术中,明文和密文都是数字,加密和解密的过程是对数字应用数学函数并创造其他数字的过程。

在非对称密钥密码术中使用两个分开的密钥:私钥和公钥。如果把加密和解密想象成是带有钥匙的挂锁的锁上和打开,那么用公钥锁上的挂锁只能被相应的私钥打开。

非对称密钥密码有时也称为公钥密码。

主要思想

首先,它强调了密码系统的非对称本性。提供安全的重担落在接收者的肩上

其次,非对称密钥密码术意味着Bob和Alice在双向通信中不能使用同一组密钥。在通信中的毎个个体应该创建自己的私钥和公钥。

明文/密文

在非对称密钥密码术中,明文和密文被当作整数来对待。在加密之前,消息必须被编码成一个整数(或一组整数),在解密之后整数(或一组整数)必须译码成消息。

非对称性密钥密码术通常起到辅助目标而不是加密消息的作用。

加密/解密

在非对称密钥密码术中的加密和解密是作用在表示明文和密文的数字上的数学函数。密文可以被看成$C=f(K _ {public} \cdot P)$,而明文可以看成$P=g(K _ {private} \cdot C)$,其中加密函数$f$只用来加密, 而解密函数$g$只用来解密。

两个系统都需要

需要通过数学函数进行加密和解密的非对称密钥密码术比对称密钥密码术慢得多。

身份验证、数字签名和秘密密钥交换仍然需要用到非对称密钥密码术。这就意味着,我们需要将对称密钥密码术和非对称密钥密码术相互配合使用才能使用到当今安全性的每一个领域。

RSA密码系统

RSA使用两个指数$e$和$d$,其中$e$是公钥,$d$是私钥。假设$P$代表明文而$C$代表密文,那么Alice使用$C=P^e\ \mod n$的算法从明文$P$中得到密文$C$;Bob通过$P=C^d\mod n$来检索Alice发送的明文。在密钥生成的过程中创造了一个很大的数作为模数$n$。

Bob选择了两个素数$p$和$q$,计算$n=p\times q$和$\varphi =(p-1)\times (q-1)$。然后Bob选择$e$和$d$这样$(e\times d)\mod \varphi =1$。Bob的公钥是$n$和$e$,他的私钥是$d$。任何人,包括Alice,都可以通过$C=P^e\mod n$加密一条消息并发送给Bob,而Bob则通过$P=C^d\mod n$来解密消息。

应用

RSA特定用于数字签名以及其他不需要使用对称密钥来对较短信息进行加密的密码。

16.3 其他安全服务

消息完整性

消息和消息摘要

保证文档完整性的一种方法是通过使用指纹。

两对(文档/指纹和消息/消息摘要)是相似的,但有一些区别。文档和指纹在物理上链接在一起。消息和消息摘要可以不链接(或单独发送),最重要的是消息摘要需要保证安全,免受篡改。

散列函数

散列函数将任意长度的消息加密成为固定长度的消息摘要。所有的散列函数加密都需要从长度不一的消息中创造出长度固定的消息摘要。建造这样一个功能最好由迭代完成,创造一个有着固定输入值并且可以使用必需的次数的函数,而不是使用输入值大小可变的散列函数。这里的固定输入值函数指的是压缩函数,它将n位的一串字符压缩并创造成m位的字符串,这里的n通常大于m。该方案被称为迭代加密散列函数。

罗思·李维斯设计的几个散列算法被称为MD2、MD4和MD5,这里的MD代表消息摘要。

然而,事实证明大小为128位的消息摘要太小了以至于不能阻挡攻击。

安全散列算法(SHA)是由国家标准与技术研究所(NIST)研制的一个标准。

消息验证

为了确保消息的完整性以及数据源的身份验证——这消息是真的来自于Alice而不是任何其他的人,我们需要在过程中包括一个Alice和Bob共享的秘密(没有经过Eve);我们需要创造一个消息验证码(message authentication code,MAC)

MAC通过散列函数和密钥的组合来保证消息的完整性和消息验证。

数字签名

数字签名使用一组公私钥。

一个电子签名能证明Alice作为消息发送者的身份。我们把这种签名称为数字签名。

对比

验证手段

对于数字签名,接收者接收到消息和签名,签名的副本不再保存,接收者需要应用验证技术来组合消息和签名,从而验证发送者的身份。

关系

对于数字签名来说,签名和消息之间是一对一的关系。每条消息有它自己的签名。一条消息的数字签名不能用在另一条消息上。

过程

签署者使用他(或她)的私钥(应用于一个签名算法)去签署文档。另方面,验证者使用签署者的公钥(应用于一验证算法)验证文档。

密码系统使用接收者的私钥和公钥;数字签名使用发送者的私钥和公钥。

签署摘要

解决方法是签署消息的摘要,该摘要比消息本身要短得多。一个仔细选择的消息摘要与消息具有一对一的关系。发送者可以签署消息摘要,接收者可以验证消息摘要,两者的效果是相同的。

服务

消息验证

一个安全的数字签名模式就像一个安全的普通签名(也就是说一个人不容易复制)一样能提供消息验证,也称为数据源验证。

消息完整性

如果我们签署消息或消息的摘要,消息的完整性就能被保护,因为如果消息改变了,我们就不能得到相同的摘要。

不可抵赖性

实体验证

实体验证用来使得一方证明另ー方标识的一种技术。一个实体可以是一个人、一个过程、一个客户端或一个服务器。身份需要证明的实体称为要求者。试图证明要求者身份的一方称为证明者。

验证分类

在实体验证中,要求者必须向证明者标识自己。

  • 所知道的。这是一种只有要求者知道的秘密,证明者可以通过它来检査要求者。
  • 所拥有的。这种东西能证明要求者的身份。
  • 所固有的。这是要求者内在固有的特性。

挑战-回应

在挑战-回应身份验证中,要求者能证明他知道秘密而不需要暴露它。换言之,要求者没有把秘密发送给证明者,但证明者或者有它,或者能找到它。

使用对称密钥密码
使用非对称密钥密码
使用数字签名

密钥管理

对称密钥分发

密钥分发中心:KDC

为了减少密钥的数量,每个人与KDC建立一个共享的密钥。一个密钥建立在KDC和每个成员间。现在的问题是Alice如何向Bob发送机密消息。过程如下:

1) Alice向KDC发送一个请求,说明她需要一个和Bob之间的会话(临时的)密钥。

2)KDC告诉Bob关于Alice的请求。

3)如果Bob同意,一个会话密钥就在二者之间建立了。密钥的作用是为了使Alice和Bob在KDC得到验证通过,并且防止Eve冒充他们中的任何一个,这里的密钥是通过KDC建立的。

多个密钥分发中心
会话密钥

KDC为每个成员建立一个密钥,这个密钥只可以在成员和KDC之间使用,而不是两个成员之间。如果Alice需要和Bob秘密通信,她需要一个在她和Bob之间的秘密密钥。KDC可以建立Alice和Bob之间的会话密钥,通过密钥和中心会话。Aice和Bob的密钥是在会话密钥建立前用来授权Alice和Bob与中心通信和互相通信的。当通信终止后,会话密钥就不再有效。

公钥分发

在公钥密码术中,每个人有权访问每个人的公钥。公钥对公众可用。

认证机构

最常用的分发公钥的方法是建立公钥认证。Bob想要两件事情:他想要人们知道他的公钥,他想要没有人接受假冒他的公钥。Bob可以去认证机构(CA),它是一个把公钥和实体捆绑在一起并处理认证的政府机构。

X.509

X.509是一个结构化描述证书的方式。

16.4 防火墙

防火墙是一个安装在一个组织的内部网络和因特网其他部分之间的设备(通常是一个路由器或计算机)。防火墙是为了推进一些数据包而过滤其他数据包而设计的。

包过滤防火墙

站点防火墙可以用做数据包过滤器。它可以基于网络层的信息和传输层的头部:源和目标IP地址,源和目标端口地址以及协议的种类(TCP或UDP)来推进或阻拦数据包。包过滤防火墙是一个使用过滤表单决定哪些数据包应该丢弃(不推进)的路由器。

代理防火墙

代理计算机(有时也称为应用网关),代理计算机位于客户计算机和公司计算机之间。当用户客户进程发送消息时,应用网关运行服务器进程来接收请求。服务器在应用层打开数据包并且查找这个请求是否合法。如果是,那么服务器运行客户端进程并将消息发给公司中真正的服务器,否则这个消息会被丢弃并且错误消息会发给外部用户。

第17章 计算理论

17.2 简单语言

我们可以仅用三条语句来定义一种语言,它们是:递增语句、递减语句和循环语句。在该语言中,只能使用非负整数数据类型。这里不需要其他类型数据,因为本章的目标仅仅是说明计算理论中的一些思想。该语言只使用少数的几个符号,如“{”和“}”。

递增语句

递减语旬

循坏语旬

筒单语言的戚力

简单语言中的宏

一个宏(macro,macroinstruction的简称)是高级语言中的一条指令,它等价于相同语言中的一条或多条指令的特定集合。

17.3 图灵机

图灵机组成部件

磁带

磁带任何时候只能保存一系列顺序字符,该字符来自计算机所能接收的字符集中。为了我们的目的,假设图灵机只能接收两个符号:空白(b)和数字1

在一元算术中,正整数仅由1组成。例如,整数4表示为1111(4个1),7表示为1111111(7个1),没有1的地方表示0。

读/写头

读/写头任何时刻总是指向磁带上的一个符号,我们称这个符号为当前符号,读/写头每次在磁带上读写一个符号。每读写完一次后,它向左移、向右移。读、写和移动都是在控制器指令下进行的。

控制器

控制器是理论上功能作用类似于现代计算机中央处理单元(CPU)的一个部件,它是一个有限状态自动机,即该机器有顶定的有限个状态并能根据输入从一个状态转移到另一个状态,但任何时候它只能处于这些状态中的一种。

对简单语言的模拟

递增语句

控制器有4个状态,从$S _ 1$到$S _ 4$,状态$S _ 1$是开始状态,状态$S _ 2$是右移的状态,状态$S _ 3$是左移的状态,状态$S _ 4$是停机状态。

递减语甸

控制器有三个状态:$S _ 1$、$S _ 2$和$S _ 3$。状态$S _ 1$是开始状态,状态$S _ 2$是检査语句,它检査当前符号是还是b。如果是b,语句进入停机状态;如果下一个符号是1,第二条语句把它改成b,然后再进入停机状态。

循坏语句

邱奇-图灵论题

如果存在一个能完成一个符号操纵任务的算法,那么也存在一台完成这个任务的图灵机。

定理可以在数学上得到证明,但论题却不能。虽然这个论题可能永远得不到证明,但有些强有力的论断在支持它。首先,尚未发现有图灵机不能模拟的算法;其次,所有在数学上己经得到证明的计算机模型都与圉灵机模型等价,这个论断是得到证明的。

17.4 歌德尔数

在计算机科学理论中,一个无符号数能被分配给任何用特定语言编写的程序,通常称为歌德尔数

首先,程序可以作为单一数据项输入给其他程序。第二,程序可以通过它的整数表示来引用。第三,该编号方式可以用来证明有一些问题计算机并不能解决,从而说明世界上问题的数量远远比曾经编写的程序数量要多得多。

各种各样的方法被设计用来给程序编号。我们用一个简单的变换给用简单语言编写的程序编号。假定简单语言仅使用15个标志符(表17-2)。

表示一个程序

运用这个表,我们可以通过唯一的正整数表示用简单语言编写的任何程序。按照以下步骤进行:

1)将每一个符号用表中所给的对应十六进制代码替代。

2)将最后的结果(十六进制)转化为无符号整数。

翻译一个数字

为了证明编号方式是唯一的,用以下步骤来解释歌德尔数:

1)将数字转换成十六进制数。

2)用表17-2将每个十六进制数翻译成对应的符号(忽略0) 注意,虽然用简单语言编写的一切程序都能用数字表述,但是,并不是所有的数字都能解释为合法程序。转换之后,如果符号不符合语法规则,这个数字就不是有效的程序。

17.5 停机问题

我们能编写一个程序来测试任何可以用歌德尔数表示的程序是否会终止吗?

该程序的存在将会节省编程人员的大量时间,运行一个程序而不知道它是否可以终止是一项枯燥乏味的工作。不幸的是,现在已经证明这样的程序不可能存在(编程人员的最大失望)。

停机问题是不可解决的

证明

17.6 问题的复杂度

不可解问题

证明一个问题能否解决等同于证明停机问题能否解决。

可解问题

可解问題的复杂度

衡量可解问题复杂度的一个方法是找出计算机运行该程序时要执行的运算数量。这样,复杂度问题不是依赖于运行程序的计算机速度,而是依赖于输入的数目。

多项式问题

以当今计算机的处理速度,对于一个有合理输入数量的(如从1000到1000000)的多项式问题我们都能解决。

第18章 人工智能

18.1 引言

什么是人工智能

人工智能是对程序系统的研究,该程序系统在一定程度上能模仿人类的活动,如感知、思考、学习和反应。

图灵测试

在1950年,阿兰·图灵提出了图灵测试,这个测试提出了机器具有智能的一个定义。该测试的方法是,简单地比较人类的智能行为和计算机的智能行为。一个询问者对计算机和人类都提出一组问题,然后,询问者得到两组答案,但他不知道哪一组是来自人类,哪一组来自计算机。在仔细检査两组答案后,如果询问者不能肯定地说出哪一组来自人类,哪一组来自计算机,那么,计算机就通过了具有智能行为的图灵测试。

智能体

智能体是一个能智能地感知环境、从环境中学习并与环境进行交互的系统。

软件智能体

软件智能体是一组用来完成特殊任务的程序。

物理智能体

物理智能体(机器人)是一个用来完成各项任务的可编程系统。

编程语言

LISP

LISP把数据和程序都当成表,这就意味着LISP程序能改变它自身。这个特性与智能体的理念相吻合,智能体能从环境中学习并改善自身行为。

PROLOG

PROLOG(Programing in LOGIC)是一种能建立事实数据库和规则知识库的编程语言。使用PROLOG编程能使用逻辑推理来回答那些可以从知识库中推导出来的问题。

18.2 知识表示

事实被表示成数据结构后就能被存储在计算机中的程序操纵。

语义网

语义网使用有向图表示知识。有向图由顶点(nodes)和边(arcs)构成。语义网用顶点代表概念,用边(用箭头表示)表示两个概念间的关系

概念

概念被看成一个集合或一个子集。

关系

一条边可以定义一个“子类”——关系这条边从子类指向超类。一条边可以定义一个“实例”关系——这条边从实例指向它所属的集合。一条边也可以定义一个对象的属性(颜色、大小…)。最后,一条边可以定义一个对象的所有权,例如拥有另外一个对象。语义网能很好定义的最重要的关系是“继承”。继承关系定义明了这样一个事实: 一个类的所有属性将出现在继承的类中。

框架

在框架中,数据结构(记录)用来表示相同的知识。

对象

语义网中的一个节点变成了一组框架中的一个对象,所以一个对象可以定义个类、一个子类或类的一个实例。

语义两中的边被翻译成”槽”(数据结构中的域)。槽的名字定义了关系的类型和构成关系的槽的值。

谓词逻辑

谓词逻辑使用了命题逻辑。

命题逻辑

命题逻辑是由对世界进行逻辑推理的一组句子组成的一种语言。

推演

给定两个假定为真的句子,我们能推演出新的为真的句子,前面两个句子称为前提,推演出的句子称为结论,而整个称为论断。

一个合法的论断是指它的结论是前提的必然延续。

验证论断合法性的一种方法是为前提和结论建立真值表。如果我们在其中发现了反例,那么结论就是非法的,

当找不到反例时,论断就是合法的。

谓词逻辑

在谓词逻辑中,句子被分成谓词和参数。

上面句子中的母亲关系是由谓词”母亲”来定义的,如果在两个句子中的玛丽是指同一个人,我们可以推导出琳达和安妮间的新的关系:祖母(琳达,安妮)。

句子

1)一个带有n个参数的谓词,像predicate_name(argument,…,argument)是一个句子,predicate_name把各个参数关联起来。每个参数可以是:

a.一个常数,像人类、动物、约翰、玛丽。

b.一个变量,像x、y和z

c.一个函数,像母亲(安妮)。注意,函数是谓词,可以用作参数,函数的返回对象能替代参数。

2)两个常数值(真和假)中的任一个都是句子。

3)如果P是句子,则P也是句子。

4)如果P和Q是句子,则$P\vee Q$、$P\wedge Q$、$P\rightarrow Q$和$P\leftrightarrow Q$都是句子。

量词

谓词逻辑允许使用量词。在谓词逻辑中两个常用的量词是$\forall$和$\exists$。

超谓词逻辑

  • 高阶逻辑
  • 模态逻辑
  • 时态逻辑
  • 默认逻辑

基于规则的系统

基于规则的系统使用一组规则来表示知识,这些规则能用来从已知的事实中推导出新的事实。规则表示当指定条件满足时什么为真。基于规则的数据库是一组if…then…语句,它们的形式为:

其中A称为前提,B为结论。注意在基于规则的系统中,每条规则都是独立处理的,与其他规则没有关联。

组成

知识库

基于规则系统中的知识库部分就是规则的数据库(仓库)。它包含一组预先建立的规则,这些规则能从给定事实中得出结论。

事实库

事实库中包含了知识库中的规则要使用的一组条件。

解释器

解释器(推理机)是一个处理器或控制器(如一段程序),它把规则和事实组合在一起。解释器有两种类型:正向推理和反向推理。

正向惟理

反向推理

18.3 专家系统

专家系统使用前面所讨论的知识表示语言,来执行通常需要人类专家才能完成的任务。它们被用在需要人类专家,而人类专家却缺少、昂贵或不可用等场合。

抽取知识

一个专家系统是建立在预先定义的关于领域专家经验的知识的基础上的。

建立专家系统的第一步就是从人类专家身上抽取知识。

知识抽取过程通常是由知识工程师来完成。

抽取事实

为了能推导新的事实或采取动作,除了需要用知识表示语言表示的知识库外,还需要事实库。专家系统中的事实库是基于事例的,在事例中事实被收集或度量,然后进入系统,被推理机使用。

体系结构

推理机

推理机是专家系统的心脏,它使用知识库和事实库推导出要采取的动作。

事实库

事实库在专家系统中是基于事例的。对于每个事例,用户输入可用的或度量的数据进入事实库,推理机为这特殊的事例使用这些数据。

解释系统

并不是所有的专家系统都有解释系统,它用来解释推理机得出的结论的合理性。

知识编辑器

并不是所有的专家系统都有知识编辑器,当从领域专家那里获得新的经验时,用知识库编辑器来更新知识库。

18.4 感知

图像处理

图像处理或计算机视觉是人工智能的一个研究领域,它处理通过像摄像机这样的智能体的人工眼睛而获得的对对象的感知。一个图像处理器从外部世界获得二维图像,然后创建在场景中的这个对象的三维描述。

边缘探測

图像处理的第一步是边缘探测,去查找图像中的边缘在哪里。

分段

分段是图像分析接下来的一步。分段把图像分成同构的段或区域。同构的定义随着方法的不同而不同。

查找深度

图像分析接下来的一步是査找对象的深度或是图像中的对象。深度的査找可以帮助智能体去测量对象距它多远。

立体视觉

立体视觉(有时称为立体影像)使用人类眼睛的技术来发现对象的深度。

两台摄像机创建的图像能帮助智能体去判定对象是近还是远。

运动

另外一种对发现图像中的对象距离有帮助的方法是:当图中一个或多个对象移动时建立多幅图像。在场景中移动对象与其他对象间的相对位置能给出对象距离的提示。

査找方向

光照

光从物体表面反射的总量由多个因素来决定。如何一个对象的不同表面的光学特性是相同的,那么反射光线的总量将取决于反射光源的物体表面(它的相对位置)的方向

纹理

纹理(有规律重复的图案)也能对査找方向或表面的曲率有所帮助。如果智能体能识别图案,这将帮助它査找对象的方向或曲率。

对象识别

图像处理的最后一步是对象识别。要识别对象,智能体需要在它的记忆里有可进行比较的对象模型。

一个解决方案是假定要识别的对象是一个复合的对象,它由一组简单的几何形状体组成。这些原始的形状能在智能体的记忆中创建并存储。

当智能体”看”到对象,它就进行对象的分解,把对象分解成原始形状的组合。如果组合的对象对智能体来说是已知的,那对象就被识别了。

语言理解

语音识别

自然语言处理的第一步是语音识别。在这一步中,语音信号被分析,其中所含的单词序列被抽取出来。语音识别子系统的输入是连续(模拟)的信号,输出是单词的序列。

语法分析

语法分析这一步用来定义单词在句子中是如何组织的

文法

正确分析句子的第一工具是良好定义的文法。

词法分析器

一台判定个句子是否符合文法(语法)的机器在判定一个句子是否合法之前,并不需要检査所有可能的选项。这个任务是由词法分析器来完成的。词法分析器基于文法规则建立一棵词法分析树来判断一个句子的合法性。

语义分析

语义分析就是在句子被语法分析之后抽取出句子的意思。这种分析建立了句子中所涉及的对象的表示方法、它们的关系以及它们的属性。

语用分析

前面的三个步骤(语音识别、语法分析和语义分析)能创建口语句子的知识表示。在大多数情况下,另外一步,语用分析是用来进一步明确句子的意图和消除歧义。

18.5 搜索

搜索可以描述成用状态(情形)集合求解问题。搜索过程开始于一个起始状态,经过中间状态,最后到达目标状态。
搜索过程所使用的全部状态的集合称为搜索空闻。

搜索方法

启发式搜索

使用启发式搜索,我们给每个节点赋一个称为启发值(h值)的定量值。这个定量值显示了该节点与目标节点间的相对远近。

开始搜索时,我们考虑下一层所有可能的状态和它们的启发值。

接下来,我们从具有较小h值的节点开始,画出下一层次可能的状态。我们继续这种方法,直至到达一个h值为0(目标状态)的状态

18.6 神经网络

神经网络试图使用神经元网络去模仿人脑的学习过程。

感知器

感知器是一个类似于单个生物神经元的人工神经元。它带有一组具有权重的输入,对输入求和,把结果与阈值进行比较。如果结果大于阈值,感知器触发;否则,不触发。当感知器触发时,输出为1;不触发,输出为0。

多层网络

几个层次的感知器可以组合起来,形成多层神经网络。每一层的输出变成下一层的输入。第一层称为输入层,中间层称为隐藏层,最后一层称为输出层。输入层中的节点不是神经元,它们是分配器。隐藏的节点通常用来给上一层的输出加上权重的。

应用

当有足够的预先定义的输入和输出时,就可以使用神经网络。

One comment

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注