2017年内蒙古大学计算机学院893数据结构与操作系统(自命题)考研题库
● 摘要
一、应用题
1． 系统盘块大小为S12B （字节），盘块编号长4B , 文件说明中可存放10个盘块编号。关于文件大小有如下统计结果：
试为该系统设计文件的物理结构，使访问文件时具有尽可能小的平均访问磁盘次数，并计算其平均访问磁盘次数。
【答案】此文件系统应采用多级索引。先将文件大小转化为盘块个数，考虑到一个索引块可索引128个盘块。
因此文件说明中可用编号a0〜a5共6个标号索引6个盘块。用编号a6〜a8共3个标号索引3个二级块，共个盘块。用编号a9可索引1个三级块，共
个盘块。 关于文件大小有如下统计结果：
，也就是在索引表所指的物理块中存放的不是文件信息，【解析】采用间接索引（多重索引）
而是装有这些信息的物理块地址。这样，如果一个物理块可装下，n 个物理块地址的话，则经过一级间接索引，可寻址的文件长度将变为块。如果文件长度还大于块的话，还可以进行类似的扩充，即二级间接索引。本题要根据统计结果的边界条件来求出直接索引、一级索引和二级索引的块数。
2． 已知T0时刻系统资源分配情况如下表所示。T0时刻系统资源分配表
（1）判断系统当前状态是否是死锁状态？
（2）P2进程发出请求向量Request2[l, 0，1], 系统能把资源分给它吗？
（3）若在P2进程申请资源后，P3进程发出请求向量Request3[0, 0, 1], 系统能把资源分给它吗？
【答案】（1）①初始化，令Work=Available，Finish 列全为false 。
系统资源初始化分配表
②因为将资源分配给P2进程，同时标记FiniSh[2]为true 。P2进程使用完后将
系统将资源分配给P2进程
它所占用的全部资源释放。此时系统资源分配情况如下表所示。
因为将资源分配给P3进程，同时标记FiniSh[3]为true 。P3进程使用完后将它所
系统将资源分配给P2进程
占用的全部资源释放，此时系统资源分配情况如下表所示。
因为将资源分配给P4进程，同时标记FiniSh[4]为true 。P4进程使用完后将它
系统将资源分配给P4进程
所占用的全部资源释放，此时系统资源分配情况如下表所示。
因为将资源分配给P1进程，同时标记FiniSh[l]为trae^PUt程使用完后将^所占
系统将资源分配给P1进程
用的全部资源释放，此时系统资源分配情况如下表所示。
⑥此时Finish 列的所有项均为true , 故系统没有死锁。
⑵P2进程发出请求向量Request2[l，0, 1]，假定系统先将资源分配给P2进程。由第⑴题的解
，故系统可把资源分配给P2进程。题过程可以看出，此时系统存在一个安全序列（P2, P3, P4，P1）
（3）①在P2进程申请资源后，P3进程发出请求向量ReqUeSt3[0, 0, 1]，假定系统先将资源分配给P3进程。此时Available=（0，1, 0）。初始化，令Work=Available，Finish 列全为false 。
系统将资源分配给P3进程
②此时因为找不到
的进程，故系统处于不安全状态。因此不能将资源分配给P3。
二、综合题
3． 试比较在单处理机0S 和多处理机0S 中的内存管理。
【答案】在多处理机系统中，存储器系统的结构十分复杂，致使对存储器系统的管理也变得非常复杂:除了需要具有单机多道程序系统中的地址变换机构和虚拟存储器功能外，还应增强和增加下面的功能和机制:
（1）地址变换机构。该机构不仅用于将虚拟地址转换成实际物理地址，还应能确定所访问的是本地存储器还是远地存储器。事实上，在目前很多支持多处理机的操作系统中，对整个存储器系统已经采用连续的地址方式进行描述，即一个处理机无需专门去识别所要访问的存储器模块的具体位置。
（2）访问冲突仲栽机构。当多个处理机上的进程同时竞争访问某个存储器模块时，该机构能
够按照一定的规则，决定哪一个处理机上的进程可立即访问，哪个或哪些处理机上的进程应等待。
（3）数据一致性机制。当共享主存中的某个数据在多个处理机的局部（本地）存储器中出现时，操作系统应保证这些数据的一致性。