问答题

【案例分析题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？

答案：

需要访问目录文件dir1所在的48号簇，及文件file1的106号簇。

你可能感兴趣的试题

【案例分析题】
图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB（K=1024）的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。

在TCP连接建立过程中，H3收到的S发送过来的第二次握手TCP段的SYN和ACK标志位的值分别是多少？确认序号是多少？

答案：

第二次握手TCP段的SYN=1，ACK=1；确认序号是101。

【案例分析题】
图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB（K=1024）的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。

H3收到的第8个确认段所通告的接收窗口是多少？此时H3的拥塞窗口变为多少？H3的发送窗口变为多少？

答案：

H3收到的第8个确认段所通告的接收窗口是12KB；
此时H3的拥塞窗口变为9KB；
H3的发送窗口变为9KB。

【案例分析题】
图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB（K=1024）的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。

当H3的发送窗口等于0时，下一个待发送的数据段序号是多少？H3从发送第1个数据段到发送窗口等于0时刻为止，平均数据传输速率是多少（忽略段的传输延时）？

答案：当H3的发送窗口等于0时，下一个待发送段的序号是20K+101=20×1024+101=20581；
H3从发...

【案例分析题】
图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB（K=1024）的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。

若H3与S之间通信已经结束，在t时刻H3请求断开该连接，则从t时刻起，S释放该连接的最短时间是多少？

答案：

从t时刻起，S释放该连接的最短时间是：1.5×200ms=300ms。

【案例分析题】如果一棵非空k（k≥2）叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。若T有m个非叶结点，则T中的叶结点有多少个？

答案：根据定义，正则k叉树中仅含有两类结点：叶结点（个数记为n₀）和度为k的分支结点（个数记为n

【案例分析题】如果一棵非空k（k≥2）叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。若T的高度为h（单结点的树h=1），则T的结点数最多为多少个？最少为多少个？

答案：高度为h的正则k叉树T中，含最多结点的树形为：除第h层外，第1到第h-1层的结点都是度为k的分支结点，而第h层均为叶结点...

【案例分析题】已知由n（n≥2）个正整数构成的集合A={a_k}0≤k1和A₂，元素个数分别是n₁和n₂，A₁和A₂中元素之和分别为S₁和S₂。设计一个尽可能高效的划分算法，满足|n₁-n₂|最小且|S₁-S₂|最大。给出算法的基本设计思想。

答案：由题意知，将最小的[n/2]
个元素放在A₁中，其余的元素放在A₂...

【案例分析题】已知由n（n≥2）个正整数构成的集合A={a_k}0≤k1和A₂，元素个数分别是n₁和n₂，A₁和A₂中元素之和分别为S₁和S₂。设计一个尽可能高效的划分算法，满足|n₁-n₂|最小且|S₁-S₂|最大。根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

答案：

【案例分析题】已知由n（n≥2）个正整数构成的集合A={a_k}0≤k1和A₂，元素个数分别是n₁和n₂，A₁和A₂中元素之和分别为S₁和S₂。设计一个尽可能高效的划分算法，满足|n₁-n₂|最小且|S₁-S₂|最大。说明你所设计算法的平均时间复杂度和空间复杂度。

答案：

算法平均时间复杂度是O(n)，空间复杂度是O(1)。

【案例分析题】假定CPU主频为50MHz，CPI为4。设备D采用异步串行通信方式向主机传送7位ASCII字符，通信规程中有1位奇校验位和1位停止位，从D接收启动命令到字符送入I/O端口需要0.5ms。每传送一个字符，在异步串行通信线上共需传输多少位？在设备D持续工作过程中，每秒钟最多可向I/0端口送入多少个字符？

答案：每传送一个ASCⅡ字符，需要传输的位数有1位起始位、7位数据位（ASCⅡ字符占7位）、1位奇校验位和1位停止位，故总位数...

【案例分析题】假定CPU主频为50MHz，CPI为4。设备D采用异步串行通信方式向主机传送7位ASCII字符，通信规程中有1位奇校验位和1位停止位，从D接收启动命令到字符送入I/O端口需要0.5ms。
设备D采用中断方式进行输入/输出，示意图如下：

I/O端口每收到一个字符申请一次中断，中断响应需10个时钟周期，中断服务程序共有20条指令，其中第15条指令启动D工作。若CPU需从D读取1000个字符，则完成这一任务所需时间大约是多少个时钟周期？CPU用于完成这一任务的时间大约是多少个时钟周期？在中断响应阶段CPU进行了哪些操作？

答案：一个字符传送时间包括：设备D将字符送I/0端口的时间、中断响应时间和中断服务程序前15条指令的执行时间。时钟周期为1/（...

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

图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？

答案：页大小为8KB，页内偏移地址为13位，故A=B=32-13=19；D=13；C=24-13=11；主存块大小为64B，故...

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

将块号为4099的主存块装入到Cache中时，所映射的Cache组号是多少？对应的H字段内容是什么？

答案：块号4099=000001000000000011B，因此，所映射的Cache组号为000000011B=3，对应的H字...

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

Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

答案：

Cache缺失带来的开销小，而处理缺页的开销大。因为缺页处理需要访问磁盘，而Cache缺失只要访问主存。

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

为什么Cache可以采用直写（Write Through）策略，而修改页面内容时总是采用回写（Write Back）策略？

答案：因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘比写主存慢得多，所以，在Cache-主存层次，Cache可以...

某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。若调度程序只将nice的值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么？

答案：

由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。

某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。

答案：优先数priority的计算公式为：
priority=nice+k1×cpuTime-k₂

【案例分析题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。

答案：

两个目录文件dir和dir1的内容如下表所示。

【案例分析题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。若FAT的每个表项仅存放簇号，占2个字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？

答案：

FAT的最大长度为2¹⁶×2B=128KB。文件的最大长度是2¹⁶×4KB=256MB。

【案例分析题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。

答案：

file1的簇号106存放在FAT的100号表项中，簇号108存放在FAT的106号表项中。

【【案例分析题】】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？

答案：

需要访问目录文件dir1所在的48号簇，及文件file1的106号簇。