2018 408
1
拟建设一个光通信骨干网络连通BJ，CS，XA，QD，JN，NJ，TL和WH等8个城市，题中无向边上的权值表示两个城市间备选光纤的铺设费用。
关于TTL,我之前的理解有一些误差。TTL意为Time To Life ，即为生存时间。
它的作用是确保分组不会永远在网络中循环，路由器在转发分组前，先把TTL减1，若TTL被减为0，则该分组必须丢弃。
2
假定计算机的主频为500MHz，CPI为4.现有设备A和B，其数据传输率分别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。
（1）若设备A采用定时查询方式，每次输入/输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百分比至少是多少？
500MHz意为每秒有500M个时钟周期
CPI为4意为每条指令需要4个时钟周期。
设备A采用定时查询方式，每次输入/输出都至少执行10条指令。
数据A的数据传输速率为2MB/s，数据缓冲寄存器里有4B，
4B/（2MB/s）=210^-6s=2us
因此每秒的查询次数至少是1s/2us=510^5，每秒CPU用于设备A输入/输出的时间至少为
510^5104=210的七次方个时钟周期，占整个CPU时间的百分比至少是210的七次方/500M=4%。
（2）在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？为什么？
中断响应和中断处理的时间为400/500M=0.8us，这时只需判断设备B准备32位数据要多少，如果准备数据的时间小于中断响应和中断处理的时间，那么数据就会被刷新，造成丢失。经过计算，设备B准备32位数据所用的时间小于中断响应和中断处理的时间，那么数据就会被刷新，造成丢失。经过计算，设备B准备32位数据所用的时间为4B/40MB=0.1us，因此设备B不适合采用中断I/O方式。
（3）若设备B采用DMA方式，每次DMA传送的数据块大小为1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输入/输出的时间占CPU总时间的百分比最多是多少？
1000B/40MB/s=0.2510^-4s，即为25us
CPU每秒有500M个时钟周期，每次传送一个DMA数据块需要500个时钟周期，那么一共传送了多少个数据块呢？数据缓冲寄存器为4B
那么1000B岂不是要填满250个数据缓冲寄存器。
那么就需要500250=125000个时钟周期
125000/500M=0.2510^-5=0.0002510的负二次方。
那就死百分之0.00025？
我犯了一个错误，DMA方式不需要I/O接口。它只需要申请总线即可。
所以在DMA方式中，只有预处理和后处理需要CPU处理，数据的传送过程是由DMA控制的。设备B每秒的DMA次数最多只有40MB/1000B=40000，
CPU用于设备B输入/输出的时间最多为40000500=210^7个时钟周期，占CPU总时间的百分比最多为210的七次方/500M=4%。
3
某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题所示。
我对于页式虚拟存储管理方式的理解不是很够，需要再加深以下了解。
另外我发现我对快表的了解还不够。
第一就是物理地址是什么？
因为是请求分页存储管理方式，所以物理地址包括页号和块内地址。在本题中，就是TLB中的实页号和CPU的块内地址相加。
那么这里的20+3+5又是什么呢？，这里的20是tag，是同有效位配合在一起用来在cache里取块的时候确认用的。3则是组号，其实这里的3很有迷惑性，因为此处的cache用的是二路组相联映射，按照道理来说本应该用1位组号的，很容易让人产生误解，需要多加注意。
5则是块内地址。
那么快表TLB（Translation Look-aside Buffer的运行机制是？
1：CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓冲寄存器，并将此页号与快表中的所有页号进行比较。
2：若找到匹配的页号，说明要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样存取数据仅一次访存便可实现。
3：若未找到匹配的页号，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。
（2）TLB采用什么映射方式？TLB是用SRAM还是DRAM实现？
仔细观察TLB，我们会发现只有一组TLB，所以为全相联映射。
TLB采用全相联映射，可以把页表内容调入任一块空TLB项中，TLB每项都有一个比较器，没有映射规则，只要空闲就行。
TLB用SRAM实现，读写速度快，但成本高，多用于容量较小的高速缓冲寄存器。
（3）cache采用什么映射方式？若cache采用LRU替换算法和回写（write back）策略，则cache每行中除数据（data），Tag和有效位外，还应有哪些附加位？cache的总容量是多少？
从图中可以看到，cache中每组有两行，故采用2路组相联映射方式。
因为是2路组相联并采用LRU替换算法，所以每行需要1位LRU位；因为采用回写策略，所以每行有1位修改位，根据脏位判断数据是否被更新，若脏位为1则需要写回内存。
cache总容量等于数据项总容量+标记项总容量。
数据项总容量=822^5=512B
标记项总容量=16*23=368bit
所以cache的总容量为4464bit。
（4）若CPU给出的虚拟地址为0008 C040H，则对应的物理地址是多少？是否在cache中命中，说明理由。若CPU给出的虚拟地址为0007 C260，则该地址所在主存块映射到的cache组号是多少？
虚拟地址分为两部分：虚页号，页内地址；物理地址分为两部分：实页号，页内地址。利用虚拟地址的虚页号部分去查找TLB表（缺失时从页表调入），将实页号取出后和虚拟地址内的页内地址拼接，就形成了物理地址。虚页号008C恰好在TLB表中对应实页号0040H（有效位为1，说明存在），虚拟地址的后三位为页内地址040H，则对应的物理地址是0040040H。
物理地址为0040040H，其中高20位00400H为标志字段，低5位00000B为块内偏移量，中间3位101B为组号2，因此将00400H与cache中的第二组两行中的标志字段进行比较，可以看出，虽然有1个cache行中的标志字段与00400H相等，但对应的有效位为0，而另一cache行中的标志字段与00400H不相等，故访问cache不命中。
0007C这是标志位 260H就是0010 0110 0000B，它就是页内地址
所以组号为011B，映射的组号为3。
4
请根据上图给出的虚拟存储管理方式，回答下列问题。
（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？
有一点需要注意到，为什么虚页号的20位在TLB缺失的情况下变成了两部分？很简单，这是一个二级页表结构，包括页目录号和页号。
虚拟地址包括虚页号和页内地址，虚页号为
0000000110 0000000110
页内地址为000000001000
则该虚拟地址的16进制表示为01806008H
（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会发生变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。
虚拟地址
会，进程切换时要打开不同的页，页目录起始地址自然随之改变。
不会，线程不占据资源，因此不会改变页。
PDBR为页目录基址寄存器（Page-Directory Base Register），其存储页目录表物理内存基地址。
增加修改位和访问位。
5
某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级，二级，三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。
（1）该文件系统能支持的最大文件长度是多少？
每个文件索引节点应该有的地址项个数为64/4=16
直接地址项：864
一级地址项：1664
二级地址项：161664
三级地址项：16161664
（2）
文件系统用1M个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像的大小为5600B，则该文件系统最多能存放多少个图像文件。
说起最多的话，那就看文件索引节点最多能存放多少个文件节点了。也就是
1M4KB/64B=1M64=64M
64M个文件索引节点。
那接下来该怎么写呢？
一个簇是4KB=41024=4096B，那么一个图像就占两个簇。
512M个簇可存放的文件总个数为512M/2=256M。可表示的文件总个数受限于文件索引节点总个数，故能存放64M个大小为5600B的图像文件。
（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？
一个簇大小为4KB，则F1最后一个簇号为1，文件F2最后一个簇号为9。
我忘了这题考的是地址项了。
不相同，因为F1只需要直接地址项，F2则需要一级间接地址项。
6
某公司的网络如图所示，IP地址空间192.168.1.0/24被均匀分配给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。
（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？
主机位全为0即为广播地址。
192.168.1.1----192.168.1.20
0000 0001----0001 0100
主机位为？
192.168.1.129----192.168.1.208
1000 0001----1101 0000
广播地址：192.168.1.0/32
子网地址192.168.1.128/25
7位128-2-（208-129+1）=126-80=46
第一道题我犯的错误是将广播地址记错了，广播地址即为主机位全为1的地址，主机位全为0则代表网络本身。
第二个错误就是我忘记了路由器的端口（192.168.1.254）同样需要一个IP，所以可以连接的主机数为45.
（2）假设主机192.168.1.1向主机192.168.1.208发送以一个总长度为1500的IP分片，IP分组的首部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？
780B，1480/780=1.----
两个片，片偏移量 1480/80=19 0001 0011
1480-780=700
700/8偏移量9 0000 1001
第二题我犯的错误是对片偏移的理解不到位。
片偏移与标志共同占据两个字节。
其中片偏移占13位，它指出较长的分组在分片后，某片在原分组中的相对位置。片偏移以8个字节为偏移单位，即每个分片的长度一定是8B（64bit）的整数倍。
比如在本题中，本来最大分片应该是800-20=780B，但是780不是8B的整数倍，所以就要选一个既是8的整数倍，又比780小，还要最接近780的数，那就是776B，所以最大片就是776B。既然是片偏移，那第一个片当然就不会偏移了，就是0.第二个片就是776/8=97
