2017年东北师范大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。
（1）画出可利用空间表的初始状态。
（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3）画出在回收3个占用块之后可利用空间表的状态。
【答案】（1）因为可利用空间表的初始状态图如图1所示：
图1 可利用空间表的初始状态
（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，
故将
的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个
大小为
的块。又将其中大小为的一块挂到可利用空间表上，另一块再分裂成两个大小为的
块。其中一块的块挂到可利用空间表上，
另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。
图2 每个用户得到的存储空间的起始地址
]
图3 可利用空间表的状态
（3）在回收时，因为给申请45的用户分配了大小为的块，其伙伴地址是0，在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192，也在占用。回收大小为11的占用块时，其伙伴地址是48，可以合并为大小的块，挂到可利用空间表上。所以回收3个占用块之后可利用空间表的状态如图4所示：
图4
2． 假定某计算机的CPU 主频为80MHz , CPI为4, 并且平均每条指令访存1.5次，主存与Cache 之间交换的块大小为168, Cache的命中率为存储器总线宽度为32位。请回答下列问题。
（1）该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下，主存带宽至少达到多少才能满足CPU 的访存要求？
（2）假定在Cache 缺失的情况下访问主存时，存在
期挪用方式，磁盘接口的数据缓冲寄存器为32位，则磁盘的缺页率，则CPU 平均每秒产接口平均每秒发出的DMA 生多少次缺页异常? 若页面大小为4KB ，每次缺页都需要访问磁盘，访问磁盘时DMA 传送采用周请求次数至少是多少？
（3）CPU 和DMA 控制器同时要求使用存储器总线时，哪个优先级更高? 为什么？ （4）为了提高性能，主存采用4体交叉存储模式，工作时每
每个体的存储周期为50ns ，则该主存能提供的最大带宽是多少？
【答案】
（1）平均每秒CPU 执行的指令数为：
平均每秒Cache 缺失的次数为：
为
：
足CPU 的访存要求。
（2）平均每秒钟“缺页”异常次数为：
故平均每秒磁盘DMA 请求的次数至少为：
请求得不到及时响应，传输数据可能会丢失。
因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA 请求，CPU 和DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为若DMA （3）（4）4体交叉存储模式能提供的最大带宽为：故MIPS 数为20; =300000; 才能满个存储周期启动一个体。若当Cache 缺失时，CPU 访问主存，主存与Cache 之间以块为单位传送数据，此时，主存带宽在不考虑DMA 传输的情况下，主存带宽至少达到
3． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的
LSI
相关内容
相关标签