=### 1
假设图中的H3访问Web服务器时S时,S为新建的TCP连接分配了20KB(K=1024)的接收缓存,最大段长MSS=1KB,平均往返时间RTT=200ms。H3建立连接时的初始序号为100,且持续以MSS大小的段向S发送数据,拥塞窗口初始阈值为32KB;S对收到的每个段进行确认,并通告新的接收窗口。假定TCP连接建立完成后,S端的TCP接收缓存仅有数据存入而无数据取出。请回答下列问题。
这一题考的是什么?考的是三报文握手和四报文分手。
(1)在TCP连接建立过程中,H3收到的S发送过来的第二次握手TCP段的SYN和ACK标志位的值分别是多少?确认序号是多少?
TCP连接的建立分以下三个阶段。首先,H3向Web服务器S发出连接请求报文段,这时首部中的同步位SYN=1,ACK=0,同时选择一个初始序号seq=100.TCP规定,SYN报文段(即SYN=1)的报文段不能携带数据,但是要消耗一个序号。接着,S收到连接请求报文段,为自己选择一个初始序号seq=y,向A发送确认。这个报文段SYN=1,ACK=1,seq=y,确认号ack是100+1=101.它不能携带数据,但是也要消耗一个序号。最后,H3收到S的确认报文段后,还要向S给出确认。这份确认报文段SYN=0,ACK=1,确认号ack=y+1,自己的序号seq=101.因此,第二次握手TCP段的SYN=1,ACK=1,确认序号是101。
(2)H3收到的第8个确认帧所通告的接收窗口是多少?此时H3的拥塞窗口变为多少?H3的发送窗口变为多少?
20-8=12,此时H3的拥塞窗口8
H3的发送窗口8
这里我犯的错误是我忽略了拥塞窗口初始就为1,每收到一个确认报文拥塞窗口就加1,H3收到了8个确认帧,那么拥塞窗口就变成8+1=9。
这里既然有拥塞窗口,那么很显然不是数据链路层的流量控制,而是传输层的流量控制。
那么发送窗口就等于min[rwnd,cwnd]

因特网建议标准定义了进行拥塞控制的四种算法:,满开始,拥塞避免,快重传和快恢复。
在TCP刚刚连接好并开始发送TCP报文段时,先令拥塞窗口cwnd=1,即一个最大报文段长度MSS。每收到一个对新报文段的确认后,将cwnd加1,即增大一个MSS。用这样的办法逐步增大发送方的cwnd。

算术移位会失去一定的位数,造成一些误差,为减小误差,要进行舍入操作。
如1000 0000左移一位,0000 0001右移一位。
首先左移一位代表乘2,右移一位代表除2。
其次移位包括算术移位和逻辑移位
其中算术移位针对带符号数,逻辑移位针对无符号数
逻辑移位较为简单,无论左移还是右移都只需要补0.
算术移位因为有符号的原因,所以左移是在右边补0,右移的话要在左边补上符号位,符号位是1就补1,符号位是0就补0。
(3)当H3的发送窗口等于0时,下一个待发送的数据段序号是多少?H3从发送第一个数据段到发送窗口等于0时刻为止,平均数据传输速率是多少?
首先拥塞窗口不可能为0,所以发送窗口为0的原因只能使接收窗口为0,也就是说发了20个MSS,缓存被耗尽了。
平均往返时间RTT=200ms,所以每隔200ms就完成以此满开始的循环。
200ms cwnd =1+1=2 ,rwnd=20-1=19
400ms cwnd=2+2=4,rwnd=19-2=17
600ms cwnd = 4+4=8,rwnd = 17-4=13
800ms cwnd = 8+8 = 16,rwnd=13-8=5
10000ms cwnd=16+16=32,rwnd
所以每秒发送20个MSS,也就是20KB/S
下一个待发送的数据段序号为:101+20K=20581
(4)
若H3与S之间通信已经结束,在t时刻H3请求断开该连接,则从t时刻起,S释放该连接的最短时间是多少?
这个地方有一个小陷阱,那就是服务器在发出确认报文段后,立刻发出连接释放报文段,就相当于有半个RTT重复了,所以最短时间是1.5个RTT,就是300ms。
这里考的应该是四报文分手吧。
第一步,客户机打算关闭连接时,向其TCP发送连接释放报文段,并停止发送数据,主动关闭TCP连接,该报文段的终止位FIN置1,序号seq=u,它等于前面已传送过的数据的最后一个字节的序号加1,FIN报文段即使不携带数据,也消耗掉一个序号。这时,TCP客户进程进入FIN-WAIT-1(终止等待1)状态。TCP是全双工的,既可以想象为一条TCP连接上有两条数据通路,发送FIN的一端不能再发送数据,即关闭了其中一条数据通路。但对方还可以发送数据。
第二步,服务器收到连接释放报文段后即发出确认,确认号ack=u+1,序号seq=v,等于它前面已传送的数据的最后一个字节的序号加1.然后服务器进入CLOSE-WAIT(关闭等待)状态。此时,从客户机到服务器这个方向的连接就释放了,TCP连接处于半关闭状态。但服务器若发送数据,客户机仍要接受,即从服务器到客户机这个方向的连接并未关闭。
第三步,若服务器已没有要向客户机发送的数据,就通知TCP释放连接,此时其发出FIN=1的连接释放报文段。设该报文段的序号为w(在半关闭状态服务器可能又发送了一些数据),
还须重复上次已发送的确认号ack=u+1.这时服务器进入LAST-ACK(最后确认)状态。
第四步。客户机收到连接释放报文段后,必须发出确认。把确认报文段中的确认位ACK置1;确认号ack=w+1,序号seq=u+1.此时TCP连接还未释放,必须经过时间等待计时器设置的时间2MSL(最长报文段寿命后),客户机才进入CLOSE(连接关闭)状态。

2

假定CPU主频为500MHz,CPI为4.设备D采用异步串行通信方式向主机传送七位ASCII字符,通信规程中有1位ji校验位和一位停止位,从D接受启动命令到字符送入I/O端口需要0.5ms。请回答下列问题,要求说明理由。
(1)每传送一个字符,在异步串行通信方式上共需传输多少位?在设备D持续工作过程中,每秒钟最多可向I/O端口送入多少个字符。
首先我需要了解ASCII码,
第一,一个ASCII码占据一个字节,其中首位是校验位,可能是ji校验,也可能是偶校验。
而对于汉字而言,一个汉字对应两个字节。
(2)
我需要了解异步串行通信方式
在这里插入图片描述
因为异步通信方式发送方和接收方要约定时间,因此必须有起始位和校验位,而同步通信方式因为建立了连接,所以就不需要起始位和校验位了。

所以每传送一个字符,就传送包括7位ASCII码,1位校验位,一位起始位和一位停止位,一共包括10位。
(2)设备D采用中断方式进行输入/输出,示意图如下。
在这里插入图片描述
我发现但凡是这种带图的题,如果看不懂图,那么必然抓瞎。
就比如这里,它问CPU需从D读取字符完成的时间是多少?
那我们就需要直到CPU从D读取一个字符需要多少时间?
首先从D接受启动命令到到字符送入I/O端口需要0.5ms,其次,CPU进行中断响应需要10个时钟周期。然后题中说第15条指令启动D工作指的是第15条指令后CPU就要开始读取下一个字符。因此读取一个CPU字符需要
50M*0.0005+10+15 * 4=25000+70=25070
完成1000个字符需要25070000个时钟周期。
中断响应阶段,CPU主要进行以下操作:关中断,保护断点和程序状态,识别中断源。

3

在这里插入图片描述

某计算机采用页式虚拟存储管理方式,按字节编址,虚拟地址为32位,物理地址为24位,页大小为8KB;TLB采用全相联映射;Cache数据区大小为64KB,按2路组相联方式组织,主存块大小为64B。存储访问过程的示意图如下。

(1)页大小为8KB,也就是块内地址有13位。所以虚页号有32-17=15位,物理块号有24-13=11位
Cache数据区大小为64KB,一个块大小为8KB,那么一个Cache就包括8个块,按2路组相联方式,那么就有4个组,所以组号为2位,块内地址还是13位,前面的标记就是24-2-13=9位
虚页号的标记就是32-13=19位。
因此A,B都是19位,C是11位,D是13位,E和H都是9位,F是2位,G是13位
B存放的是标记信息,是用来和虚地址的前一部分比较的。

标准答案

第1题中F和G我回答错了,因为我忽略了主存块大小为64B,我需要记住在虚拟地址到物理地址的映射中,页的大小起作用;在物理地址到Cache的映射中,主存块大小起作用。
因此G为6位,F代表组号,为64KB/64B/2=512,因此F为9位。
TLB标记字段B的内容是虚页号,表示该TLB项对应哪个虚页的页表项。
(2)将块号为4099的主存块装入到Cache中,所映射的Cache组号是多少?对应的H字段内容是什么?
块号从0开始,一个Cache有8个块,用4099去mod8,余1,因为用的是2路组相联,所以4099映射的组号为1,H字段为标记,这个不清楚

标准答案

这里我错的地方是4099mod8居然出错了,正确的余数为1。
由此可见,还是直接取对应的组号比较正确。4099是一个10进制数,其16进制表示为1003,它的二进制表示就是0001 0000 0000 0011
我们发现,这里的二进制一共才18位,可是在本题中cache的标记位+组号一共是9+9=18位,因此要在前面补上两位,之后再取组号就是0 0000 0011
因此Cache组号为3,对应H字段的内容也就是 0 0000 1000B
(3)Cache缺失处理的时间开销大还是缺页处理的时间开销大?
Cache缺失以后需要从主存中调取主存块,缺页以后需要进行的处理比较麻烦,所以应该是却也处理的时间开销大。

标准答案

其实这里我回想缺页处理的时候感觉很麻烦,所以才说缺页处理时间开销大,现在我要重新学习一下缺页处理。
在请求分页系统中,每当所要访问的页面不在内存中时,便产生一个缺页中断,请求操作系统将所缺的页调入内存。(这里有一点没说但很重要,所缺的页是从外存,也可以说磁盘中调入内存的)。此时应将缺页的进程阻塞(调页完成唤醒),若内存中有空闲块,则分配一个块,将要调入的页装入该块,并修改页表的相应页表项,若此时内存中没有空闲块,则要淘汰某页(若被淘汰页在内存期间被修改过,则要将其写回外存)。
缺页中断作为中断,同样要经历诸如保护CPU环境,分析中断原因,转入缺页中断处理程序,恢复CPU环境等几个步骤。但与一般的中断相比,它有以下两个明显的区别:
在指令执行期间而非一条指令执行完后产生和处理中断信号,属于内部中断。
一条指令在执行期间,可能产生多次缺页中断。

用简洁的话语来描述的话就是:缺页中断需要访问磁盘,而Cache缺失只需要访问主存即可。

(4)为什么Cache可以采用直写(write-through)策略,而修改页面内容时总是采用回写(write back)策略?直写的话cache中不会修改对应的内容,根据局部性原理,它有可能在接下来的操作中用到,这时再进行调入等操作比较麻烦。而回写法有助于在接下来的操作中使用到该内容。

标准答案:这里我把write-through,write-back和write-allocate,not-write-allocate弄混了。
因为采用直写策略时需要同时写快速存储器和慢速存储器,而写磁盘比写主存慢很多,所以在Cache-主存层次,Cache可以采用直写策略,而在主存-外存层次,修改页面内容时总是采用回写策略。

4

某进程调度程序采用基于优先数(priority)的调度策略。即选择优先数最小的进程运行,进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数,引入运行时间cpuTime和等待时间waitTime,初值均为0.进程处于执行态时,cpuTime定时加1,且waitTime置0;进程处于就绪态时,cpuTime置0,waitTime定时加1。
(1)若调度程序只将nice的值作为进程的优先数,即priority=nice,则可能会出现饥饿现象,为什么?
如果某些进程的nice值较大,就有可能一直得不到运行,也就进入了饥饿状态。
(2)使用nice,cpuTime和waitTime设计一种动态优先数计算方法,以避免产生饥饿现象,并说明waitTime的作用。
若要避免产生饥饿现象,就必须使那些nice值较大的进程也能得到运行。也就是说随着waitTime的不断增大,优先数应该逐渐变小,所以waitTime应该作为分母,以此来避免nice值较大的进程长期得不到运行。
(nice+cpuTime)/waitTime。
标准答案中给出了另一种计算方法,给了我一种新思路。即为:
priority=nice+k1cpuTime-k2waitTime;其中k1>0,k2>0,用来分别调整cpuTime和waitTime在priority中所占的比例。我以前一直以为可以用除法降低优先数,但这道题给了我一个新思路,减法也可以用来降低优先数。

5

某磁盘文件系统使用链接分配方式组织文件,簇大小为4KB。文件目录的每个目录项包括文件名和文件的第一个簇号,其他簇号存放在文件分配表FAT中。
(1)假定目录树如下图所示,各文件占用的簇号及顺序如下表所示,其中dir,dir1是目录,file1,file2是用户文件。请给出所有目录文件的内容。
dir中的内容是dir1,dir1中的内容是file1和file2。
看图看图还是看图,除了文件名还有簇号我怎么就把簇号给忘了呢?
文件名 簇号 文件名 簇号
dir1 48 file1 100
file2 200
记住一件事情,在有图的题中,不根据图来答题,死路一条
(2)若FAT的每个表项仅存放簇号,占2字节,则FAT的最大长度为多少字节?该文件系统支持的文件长度最大是多少?
这道题我没有思路,因此我翻阅了答案,以后要重点复习。
由于FAT的簇号最多为2个字节,即16比特,因此在FAT表中最多允许2^16(65536)个表项,一个FAT文件最多包含
2^16(65535)个簇,FAT的最大长度为
2^162B=128KB
文件的最大长度是2^16
4B=256MB。
(3)系统通过目录文件和FAT实现对文件的按名存取,说明file1的106,108两个簇号分别存放在FAT的哪个表项中。
什么叫按名存取?所谓的按名存取,就是在FAT的每个表项中存放下一个簇号。file1的簇号106存放在FAT的100号表项中,簇号108存放在FAT的106表项中。
(4)假设仅FAT和dir目录文件已读入内存,若需将文件dir/dir1/file1的第5000个字节读入内存,则要访问哪几个簇?
我们直到一个簇大小为4KB,就是4096字节,所以第5000个字节应该存放在file1的第2个簇中,也就是file1的第106号簇。
先在dir目录文件里找到dir1的簇号,然后读取48号簇,得到dir1目录文件,接着找到file1的第一个簇号,据此在FAT里查找file1的第5000个字节所在的簇号,最后访问磁盘中的该簇。因此,需要访问目录文件dir1所在的48号簇及文件file1的106号簇。