课程新增内容0516.docx
《课程新增内容0516.docx》由会员分享，可在线阅读，更多相关《课程新增内容0516.docx（36页珍藏版）》请在冰点文库上搜索。
课程新增内容0516
第二章新增内容
2.6计算机网络中协议的设计问题
20世纪90年代，计算机网络，特别是因特网（Internet）得到飞速的发展，新思想、新技术、新产品和新的应用层出不穷，并开始渗透到人们生活的各个方面，若再将它列为操作系统中的一个研究主题就不合适了。
为此，CC2001任务组在CC1991（ComputingCurricula1991）报告的基础上，将它提取出来，作为计算学科一个新的主要领域，命名为网络计算。
本小节从两军问题入手介绍计算机网络。
2.6.1两军问题
AndrewS.Tanenbaum在《计算机网络》（ComputerNetworks，潘爱民等译，清华大学出版社2004年8月第4版）一书中介绍了一个与网络协议有关的著名问题两军问题（twoarmyproblem，图2.9），用来说明协议设计的微妙性和复杂性。
两军问题可以这样描述：
一支白军被围困在一个山谷中，山谷的两侧是蓝军。
困在山谷中的白军人数多于山谷两侧的任一支蓝军，而少于两支蓝军的总和。
若一支蓝军对白军单独发起进攻，则必败无疑；但若两支蓝军同时发起进攻，则可取胜。
两支蓝军希望同时发起进攻，这样他们就要传递信息，以确定发起攻击的具体时间。
假设他们只能派谴士兵穿越白军所在的山谷（惟一的通信信道）来传递信息，那么在穿越山谷时，士兵有可能被俘，从而造成消息的丢失。
现在的问题是：
如何通信，以便蓝军必胜。
下面我们进行设计：
图2.9两军问题
假设一支蓝军指挥官发出消息：
“我建议在明天拂晓发起进攻，请确认”，如果消息到达了另一支蓝军，其指挥官同意这一建议，并且他的回信也安全送到，那么能否进攻呢？
不能。
这是一个两步握手协议，因为该指挥官无法知道他的回信是否安全送到了，所以，他不能发起进攻。
改进协议，将两步握手协议改为三步握手协议，这样，最初提出建议的指挥官必须确认对该建议的应答信息。
假如信息没有丢失，并收到确认消息，则他须将收到的确认信息告诉对方，从而完成三步握手协议。
然而，这样他就无法知道消息是否被对方收到，因此，他不能发起进攻。
那么现在采用四步握手协议会如何呢？
结果仍是于事无补。
结论是：
不存在使蓝军必胜的通信约定（协议）。
该结论可以用反证法证明，证明如下：
假如存在某种协议的话，那么，协议中最后一条信息要么是必要的，要么不是。
如果不是，可以删除它，直到剩下的每条消息都是至关重要的。
若最后一条消息没有安全到达目的地，则会怎样呢？
刚才说过每条信息都是必要的，因此，若它丢了，则进攻不会如期进行。
由于最后发出信息的指挥官永远无法确定该信息能否安全到达，所以，他不会冒险发动攻击。
同样，另一支蓝军也明白这个道理，所以也不会发动进攻。
Andrew用“两军问题”来阐述网络传输层中“释放连接”问题的要点。
而在实际中，当两台通过网络互连的计算机释放连接（相对应“两军问题”的发起进攻）时，通常一方收到对方确认的应答信息后，不再回复，就释放连接（用的是一个三步握手协议）。
这样处理，协议并非完全没有错，但通常情况下已经足够了。
本书不再讨论这个问题，但是，正如Andrew给出的结论那样，现在你应该很清楚，释放一个可能有数据丢失的网络连接并不像人们初看起来那样简单。
2.6.2互联网软件的分层结构
网络协议（简称协议），它是为网络中的数据交换而建立的规则、标准或约定的集合。
实现计算机之间自动、可靠数据通信的网络协议，一般都极其复杂。
借鉴复杂系统的研究方法，就是要进行集合的划分，于是人们将它划分为若干个子集（层次），各层各司其责，从而降低协议设计的复杂性，进而讨论和研究它们。
在Internet上，就是通过一个分层的具有不同功能的软件来实现数据交换的。
这就像邮寄一个包裹的过程（图2.10），首先将礼物打包，然后送到当地邮局，邮局通过货运公司的交通工具（可能经过若干中转站）将包裹送往目的地，目的地邮局将包裹取出，按照地址送给接收方，接收方打开包裹，取出礼物。
这个礼物的运送可以有三个层次来完成：
（1）用户层；
（2）邮局；（3）货运公司。
每一层将下一个较低层当作一种抽象工具使用（不用关心该层的细节）。
在这个层次结构中的每一级在源地和目的地都有代表，在目的地的代表会与其在源地的对应代表进行相反的操作。
图2.10包裹邮寄的层次结构
与此相似的，是控制Internet上通信的软件，其不同之处在于，Internet软件有四个层次（图2.11），即应用层，传输层，网络层和链路层，每层均有相应的协议进行支撑，每台Internet上的机器都具有这样的软件及层次结构。
一条信息在应用层产生，向下通过传输层和网络层的处理，然后通过链路层被传递。
这个信息由目的地的链路层接收，通过网络层和传输层的逆操作，最后将信息送到应用层。
图2.11Internet软件的层次结构
应用层包括所有的网络应用，如电子邮件、FTP、WWW等等。
这些应用要支持该层相应的协议，如DNS（DomainNameSystem，域名系统），电子邮件协议（SMTP），文件传输协议（FTP），超文本传输协议（HTTP）等。
从应用层产生的信息首先发送到传输层。
传输层从应用层接收信息，并将信息分成小的片断，这些片断被当作单独的单元在Internet上传送。
传输层为这些小的片断加上序号以便它们在目的地被重组，然后加上目的地地址。
网络层从传输层接收加上序号的片断（也被称为包），通过处理Internet的拓扑结构，在确定一个包的中间目的地后，将这个地址附加其上再送到链路层。
链路层负责处理通信的细节，每次传送包时，包都由接收机器的链路层负责接收，并将包传给接收机器的网络层处理。
若包不为最终目的地的网络层，则接收机器的网络层就在包上附加一个新的中转站地址，再将包返回链路层继续传送，直到网络层确定到达的包已经送到了最后的目的地，它便将包送到传输层。
当传输层从网络层接收包以后，就将包打开，并通过序号将这些信息恢复成原来的样子，最后送到应用层。
本书不对以上过程作详细的描述，以后同学们将在“计算机网络”等课程学到更多的知识。
这里需要指出的是，将“两军问题”一般化，即参与网络协议的是N个实体，所用的信道是不安全的（可以被任何实体截获），那么即使发送方发送的加密信息不被破解，要设计满足特定要求（如不可否认性，公平性等）的网络协议（如各种电子商务协议）也是一件不容易的事，更不用说其他如安全协议的组合问题、复杂数据结构的协商问题等更为困难的问题。
为了确保网络协议的安全，研究人员提出了一系列新的理论（如BAN类逻辑，Kailar逻辑，串空间理论等），研制了不少用于形式化验证的工具（如SMV，SPIN，Athena等）,开辟了一个新的研究领域：
安全协议工程。
第三章新增内容
基于冯·诺依曼计算机体系结构的程序执行
在早期计算机设计中，人们认为，程序与数据是两种完全不同的实体。
于是，自然将程序与数据分离，数据存放在存储器中，程序则作为控制器的一个组成部分（如外插型的程序）。
这样，每执行一个程序，都要对控制器进行设置（如在ENIAC中，编制一个解决小规模问题的程序，就要在40多块几英尺长的插接板上,插上几千个带导线的插头）。
显然，这样的机器效率不仅低，且灵活性也很差。
冯·诺依曼计算机的体系结构，也即存储程序式计算机的体系结构，则是将程序与数据一样看待，对程序像数据那样进行适当的编码，然后与数据一起共同存放在存储器中。
这样，计算机就可以通过改变存储器中的内容，对数据进行操作。
从原来对程序和数据的严格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变化。
下面，介绍Brookshear在其著作《计算机科学概论》中，给出的一个基于冯·诺依曼计算机体系结构的程序执行实例，以加深对存储程序式计算机体系结构的理解。
（1）机器的结构和指令
该机器有256个主存单元（分别用十六进制0FF表示），16个通用寄存器（0F），一个程序计数器和一个指令寄存器。
机器的指令有12条，每条指令的长度均为2个字节，指令的前4位为操作码，后12位为操作数，如表3.1所示。
表3.1执行程序的机器指令集
操作码
操作数
描述
1
RXY
将内存XY单元中的数据取出，存入寄存器R中，如1A43，将43单元中的数据取出，存入寄存器A中
2
RXY
将数XY存放到寄存器R中
3
RXY
将寄存器R中的数据存入主存地址为XY的单元中
4
0RS
将寄存器R中的数存入寄存器S中
5
RST
将寄存器S与T中的用二进制补码表示的数相加，将结果存入寄存器R中
6
RST
将寄存器S与T中的用浮点数表示的数相加，将结果存入寄存器R中
7
RST
将寄存器S与T中的数进行或运算，将结果存入寄存器R中
8
RST
将寄存器S与T中的数进行与运算，将结果存入寄存器R中
9
RST
将寄存器S与T中的数进行异或运算，将结果存入寄存器R中
A
R0X
将寄存器R中的数右移X次，每次将最低位移出的数字放在最高位的空缺中
B
RXY
若寄存器R中的数与寄存器0中的数相同，就将内存XY单元中的数据（跳转指令）存入程序计数器中；否则，按原来的顺序继续执行
C
000
停机,C000
（2）程序执行的一个例子
图3.5一个在主存中即将执行的程序
图3.5表示的是一个在主存中即将执行的程序。
该程序在内存中的起始地址为A0。
下面，分析程序的执行。
⑴从A0开始，将A0放入程序计数器中，开始运行程序；
⑵提取地址为A0的指令（2个字节），并把指令（11AA）存放到指令寄存器中，程序计数器+2；
⑶执行指令11AA，通过总线，将AA地址中的值2取出来，放到1号寄存器中；
⑷提取地址为A2的指令，并把指令（12AB）存放到指令寄存器中，程序计数器+2；
⑸执行指令12AB，将AB地址中的值6取出来，存放到2号寄存器中；
⑹提取地址为A4的指令，并把指令（7012）存放到指令寄存器中，程序计数器+2；
⑺执行指令7012，将1号寄存器中的数据与2号寄存器中的数据相加，将结果存放到0号寄存器中；
⑻提取地址为A6的指令，并把指令（30AC）存放到指令寄存器中，程序计数器+2；
⑼执行指令30AC，将0号寄存器中的数据存放到内存地址为AC的存储单元中；
⑽提取地址为A8的指令，并把指令（C000）存放到指令寄存器中，程序计数器+2；
⑾执行指令C000，停机。
第四章新增内容
4.7数据存储和表示
计算机用位的形式来表示数据。
位（binarydigit，二进制数字，缩写为bit）是存储在计算机中的最小数据单位，位表示二进制数字的0或1，8位表示1个字节（byte）。
存储一个位需要用一个有两种状态的设备。
例如，电子开关就能表示并存储位，通常用“开”（合上）状态表示“1”，用“关”（断开）表示“0”。
现代计算机使用各种各祥的两态设备来存储数据。
在计算机中，数据和指令都是用二进制代码来表示的。
二进制数的每一位只能是数字0或1，它只有形式的意义，对于不同的应用，可以附给它不同的含义。
因此，可以用它来表示数值、字符、图像甚至声音，对这些数据，需要进行相应的编码。
在需要呈现给用户时，再对它们进行解码。
下面分别介绍进位制数及其相互转换，原码、反码和补码及其转换，以及字符、字符串和汉字，图像和声音等数据的表示。
4.7.1进位制数及其相互转换
在计算机中，只能存二进制数，因此，要保存一个十进制（Decimal）的数，也就是要保存一个对应的二进制数。
由于计算机很难确定在内存中一个值的结束位置和另一个值的起始位置，因此，大多数计算机和程序都采用固定的宽度来避免这个问题，即每一个数都用相同的位数来表示。
常用的有16位、32位和64位。
在一个16位的计算机中，若一个十进制数转换为二进制数后，不够16位，则在这个二进制数前加0，直到满16位为止。
比如，十进制数2，其二进制数为10，在10前加14个0，即为：
0000000000000010。
在实际的程序中，由于二进制数不直观。
因此，在程序的输入和输出中，一般仍采用十进制数，而在分析计算机内部工作时，常用十六进制（Hexadecimal）数，这样，就要进行相应的转换。
下面，分别介绍十进制与二进制，以及二进制与八进制（Octal），二进制与十六进制等几种常用的进位制数的表示及其相互转换。
1.十进制数与二进制数之间的转换
我们知道在表示十进制数的时候，从右边起的第1个数字是1（100=1），第2个数字是10（101=10），第3个数字是100（102=100），第4个数字是1000（103=1000），以此类推。
如果我们要把十进制整数3254展开，我们很容易知道存在如下的关系，3254=3*103+2*102+5*101+4*100。
这样的关系同样存在二进制数中，只是这里的基数不是10，而变成了2。
这时，从右边起的第1个数字就是1（20=1），第2个数字就是2（21=2），第3个数字是4（22=4），第4个数字就是8（23=8）了。
从这一点出发，我们很容易找到十进制和二进制转换的方法。
（1）十进制数转换为二进制数
若R表示十进制整数，Kn-1，Kn-2，Kn-3…K1，K0表示二进制数的各位数，最低（右）端一位为K0，最高（左）端一位为Kn-1。
为了区分十进制数和二进制数，我们分别给十进制数和二进制数加上下标10和2，即有如下形式
（R）10=（Kn-1Kn-2Kn-3…K1K0）２ ①
与上文提到的十进制的展开类似，我们可以将上式写为
（Kn-1Kn-2Kn-3…K1K0）２=Kn-1*2n-1+Kn-2*2n-2+Kn-3*2n-3+…+K1*21+K0*20②
显然，从等式右边看，除最后一项K0以外，其余每项都包含有２的因子，它们都能２除尽。
故R除以2，它们的余数即为K0，商变为Kn-1*2n-2+Kn-2*2n-3+Kn-3*2n-4+K1*20，将得到的商再除以2，余数即为K1，商变为Kn-1*2n-3+Kn-2*2n-4+Kn-3*2n-5+…+K2*20，这样依次下去，分别得到K2，K3，K4…Kn，便得到了二进制数的各位数。
比如十进制数126。
所以十进制数126的二进制数为1111110（这里只讨论数之间的转换，没有涉及标准格式的存储，为了方便，如无特殊说明，不用0去补足计算机的实际位数）。
（126）10=（1111110）2
（2）二进制数转换为十进制数
二进制数转换为十进制数比较简单，由①式和②式我们很容易得到（R）10=Kn-1*2n-1+Kn-2*2n-2+Kn-3*2n-3+…+K1*21+K0*20
我们只要简单地将每一位与其对应为的2的幂次方相乘，然后求和。
比如（1111110）2=1*26+1*25+1*24+1*23+1*22+1*21+0*20=64+32+16+8+4+2+0=（126）10。
这样，就完成了从二进制数向十进制数的转换。
以下是几个计算机中常用的二进制数和十进制数转换的例子。
2.八进制数与二进制数之间的转换
因为23=8，所以1位八进制数相当于3位二进制数。
利用这一点，我们可以将每位八进制数用3位对应的二进制数来表示，完成八进制数向二进制数的转换；将二进制数每3位表示成1位八进制数，完成二进制数向八进制数的转换。
下面，通过两个例子说明八进制和二进制之间的转换。
（1）八进制数转换为二进制数
例如，八进制数（254）8要转换为二进制数，则将2，5，4分别用3位二进制表示。
即：
（245）8=（010100101）2
（2）二进制数转换为八进制数
例如，二进制数（11010010110）2要转换为八进制数，则将11010010110从最低端开始每3位写成一组，最高端不足3位的用0补足。
再将每一组3位二进制数表示成八进制
即：
（11010010110）2=（3226）8
3.十六进制数与二进制数之间的转换
根据八进制数与二进制数转换的原理，由于24=16，所以1位十六进制数相当于4位二进制数。
（1）十六进制数转换为二进制数
例如，（5AC8）16可转换为
即（5AC8）16=（010*********）2
（2）二进制数转换为十六进制数
同样的道理，例如（100101000111001）2可转换为
即（100101000111001）2=（4A39）16
计算机中的数据是以二进制数表示的，二进制数的每1位只能为0或1，而人要处理一长串的0和1是非常乏味且容易出错的。
而采用十六进制可以有效的帮助我们，借助这种方法，一个16位的二进制数0100101000111001可以用更简单的十六进制数4A39来表示。
4.7.2原码、反码、补码及其转换
前面，介绍了进制数及其转换。
现在，介绍带符号的编码表示方法。
带符号的编码与数字计算机最基本的一个运算，即“加法”有关。
而数字计算机中的“减法”，则是通过下面的“补数”法，简化为“加法”实现的。
1.原码
原码是一种最简单而又直观的编码方法。
数的符号用一位数码表示，0表示正号，1表示负号，其余的数位与数值本身相同。
例如
N1=+1001101N2=-1001101
其原码为：
[N1]原=01001101[N2]原=11001101
需要指出的是数值0如何表示。
由于机器数受位数的限制，当计算中出现太小的数时（即下溢出），机器作为0处理，于是有正0与负0之分，即+0.00…0，-0.00…0。
若要表示为原码，则有：
[+0]原=0.00…0[-0]原=1.00…0
原码表示简单，与真值间的转换很容易。
但是由于只是简单地将符号数值化，而没有与数值统一编码，作加减运算时很不方便。
例如两符号相反的数相加：
1011+0010，（-3+2），表面上是做加法，事实上由于两数异号，故做减法，即原码表示的数在做加法运算时，不仅要根据指令规定的操作性质（加或减），还要根据两数的符号，才能决定实际操作是加还是减。
这些操作使控制线路复杂化，运算速度降低。
2.反码
反码是机器数的另一种编码表示法。
它是一种正数与原码相同，负数将原码除符号位外其余各位求反的表示法。
求反就是0变1，1变0的操作。
例如
[2]原=00000010[2]反=00000010
[-2]原=10000010[-2]原=11111101
由于0的原码存在两个，且反码由原码得到，所以0的反码也存在两个
[+0]原=0.00…0[-0]原=1.11…1
计算机中得到反码非常方便，因为计算机中将一个二进制数变反是很容易的。
通常只需要完成一个按位加的操作便可。
比如0110101求反
但是反码和原码一样，计算比较麻烦，因此实际使用不多，通常只是将反码作为求补码过程的中间形式。
3.补码
为了弥补原码和反码计算能力的不足，在计算机中引入了补码的概念。
我们先来看两个例子。
第一个例子是两个十进制数之间的运算
8-3=5
8+7=15=10+5
如果运算器只能计算1位十进制数，那么在做加法8+7时，结果中的10超出该运算器的表示范围时，将会被自动舍去。
运算器只能表示出结果为5。
在做减法8-3时，若用加法8+7代替，同样可以得到结果5。
在介绍补码中，另一个经典的例子就是调整时钟。
如果现在时钟的时间是9点，要把时钟调到2点，我们很容易想到两种方法。
一种方法是从9点开始逆时针回拨7小时到2点，即减去7；另一种方法是从9点开始顺时针前拨5小时到2点，即加上5。
两种方法都能将时钟调到4点。
上面的两个例子，10是第一个例子的模，12是第二个例子的模。
我们称7是以10为模的-3的补数，5是以12为模的-7的补数。
通过模和补数的概念，我们就可以将减法变成加法，将负数变成正数，这正是引入补码的目的所在。
由上面两个例子，我们可以归纳出求补数的方法
[-3]补=（-3+10）=7
[-7]补=（-7+12）=5
即[-X]补=（-X+MOD）
补数的概念来自数学的“同余”概念。
为免叙述上的混淆，采用“补码”这个名称。
所谓补码，是指在计算机中用补数码表示数值。
对于正数，补码即原码本身；而对于负数，补码是原码对模数的补数。
换句话说，对负数而言，可以用负数加模的方法得到其补码。
在计算机中二进制数的补码是如何表示的？
我们知道，计算机中数的表示受计算机字长的限制，其运算都是有模运算。
模在机器中是表示不出来的，各运算结果超出能表示的数值范围，则会自动舍去溢出量（模），只保留小于模的部分。
设字长为n+1位，对定点小数x0.x1x2…xn，其溢出量为
，即2，则以2为模。
对定点整数x0x1x2…xn，其溢出量为
，即2n+1，则以2n+1为模。
在知道了二进制数的模后，根据我们上面的公式[-X]补=（-X+MOD），我们可以求出二进制数的补码了。
以定点小数说明。
设有如下两个数
[+0.1011]原=0.1011[-0.1011]原=1.1011
正数的补码就是它本身．即正数的补码与原码相同
[+0.1011]原=0.1011
[+0.1011]补=0.1011
下面，我们求负数的补码
[-0.1011]原=1.1011
[-0.1011]补=-0.1011+10=1.0101
4.原码、反码和补码的转换
这里介绍一种二进制负数求补码的更简单的方法：
对于一个机器数原码来说，如果为正数，则其补码与原码相同，如果为负数，则除符号为不变外，其余各位按位求反，并在最低位上加１即得其补码。
还是用刚才的二进制数-0.1011，它的原码为1.1011，我们对其除符号位外求反得1.0100，再加上1就得到了-0.1011的补码1.0101。
一个补码又如何变回原码以得到真值呢?
对于正数，补码就是原码，不必变换。
而对于负数，则是再次“取反加1”，我们求上例补码的原码，只需
我们看到，得到的原码与上例中的原码是相同的。
我们做如下归纳，对正数而言，原码、反码和补码的表示形式是相同的；对负数而言，原码与反码的互换，只需“除符号位不变外，按位求反”，原码与补码的互换，只需“除符号位不变外，按位求反再加1”。
4.7.3字符、字符串和汉字
在计算机中，除了能处理数值数据信息外，还能处理大量的如字符、图像及汉字等的信息，这些信息在计算机中也必须用二进制代码形式表示。
要想用计算机对这些信息进行处理，首先遇到的一个问题是如何用二进制数表示字符，即如何对字符编码。
1.字符
目前被广泛采用的字符编码是由美国国家标准局（AmericanNationalStandards）制定的美国标准信息交换码——（AmericaStandardCodeforInformationInterchange，ASCII），该编码被国际标准化组织（ISO）定为国际标准，称为ISO646标准。
ASCII码用8位二进制码来表示英文中的大小写字母、标点符号、数字0到9以及一些控制数据（如换行、回车和制表符等），最高位为0。
若将最高位设为1，还可以将标准的ASCII进行适当的扩展（可增加128个字符）。
下面，给出常用的ASCII码对照表（表4.1）。
表4.1常用的的ASCII码对照表
查ASCII码对照表，可知A的ASCII码是01000001，a的ASCII码是01100001，字符就是用这样的二进制数表示的
升级会员 