↻
❮
❯
⬆︎
×
分类 系统架构设计  2869字  10分钟📤 🖨 

系统架构设计强化教程（1）：计算题

作者

计算题历年真题/教材经典例题汇总

1 计算机组成与体系结构

1.1 流水线

流水线执行时间（设有n条k级操作的指令，操作执行时间分别为t_1,t_2,\cdots,t_k）：

  • 流水线周期：t=\max(t_1,t_2,\cdots,t_k)
  • 理论公式：(t_1+t_2+\cdots+t_k)+(n-1) t
  • 实践公式：kt+(n-1)t=(k+n-1)t

吞吐率（设有n条k级操作的指令，流水线周期为t，使用实践公式）：

  • 基本公式：TP=\frac{n}{流水线执行时间}
  • 最大吞吐率：TP_{\max}=\lim\limits_{n\rightarrow \infty}\frac{n}{(k+n-1)t}=\frac1t

加速比：

  • 基本公式：S=\frac{不使用流水线执行时间}{使用流水线执行时间}

【例1】（2017下半年）某计算机系统采用5级流水线结构执行指令，设每条指令的执行由取指令（2\Delta t）、分析指令（1\Delta t）、取操作数（3\Delta t）、运算（1\Delta t）和写回结果（2\Delta t）组成， 并分别用5个子部件完成，该流水线的最大吞吐率为（ ）；若连续向流水线输入10条指令，则该流水线的加速比为（ ）。

流水线周期：\max(2\Delta t,1\Delta t,3\Delta t,1\Delta t,2\Delta t)=3\Delta t

理论流水线执行时间：(2\Delta t+1\Delta t+3\Delta t+1\Delta t+2\Delta t)+\times (n-1)=9\Delta t+ (n-1)\times 3\Delta t

【第1问】
最大吞吐率：\lim\limits_{n\rightarrow \infty}\frac{n}{9\Delta t+(n-1)\times 3\Delta t}=\frac{n}{3n\Delta t+6\Delta t}=\frac{1}{3\Delta t}

【第2问】
10条指令使用流水线的执行时间：9\Delta t+ (10-1)\times 3\Delta t=36\Delta t
10条指令不使用流水线的执行时间：9\Delta t\times 10=90\Delta t
加速比：\frac{不使用流水线执行时间}{使用流水线执行时间}=\frac{90\Delta t}{36\Delta t}=5:2

【例2】（教材例题1.3.1）某计算机系统一条指令的执行需要经历取指（2ms）、分析（4ms）、执行（1ms）三个阶段，现要执行100条指令，利用流水线技术需要多长时间?

流水线周期：\max(2,4,1)=4\text{ (ms)}

理论流水线执行时间：2+4+1+(100-1)\times 4=403\text{ (ms)}

实际流水线执行时间：3\times 4+(100-1)\times 4=408\text{ (ms)}

1.2 主存编址、进制转换

主存容量、芯片数计算：

  • 存储单元个数 = 最大地址 - 最小地址 + 1
  • 总容量 = 存储单元个数 × 编址内容，其中编址内容为1个字（4B或8B）或1B（8bit）
  • 芯片总数 = 总容量 / 每片的容量

进制转换：

  • R进制转十进制（按权展开法）：数码 × 位权的和
  • 十进制转R进制（除基取余法）：短除法，余数即为从低位到高位上的数码
  • 二进制转八进制与十六进制：从低位起，3位（八进制）或4位（十六进制）一组，每组根据421（八进制）或8421（十六进制）计算“1”所在位的加和，最后排列即得。

【例】内存按字节编址，地址从90000H到CFFFFH，若用存储容量为16K × 8bit器芯片构成该内存，至少需要（ ）片。

CFFFFH - 90000H + 1 = 3FFFFH + 1 = 40000H

法1——十六进制转十进制：40000H转成十进制为256K，由于内存按字节编址（8bit），故存储容量为256K / 16K = 16

法2——十进制转十六进制：16K转成十六进制为4000H，则有40000H / 4000H = 10，转成十进制为16。

1.3 磁盘管理

数据读取时间：

  • 存取时间（Access Time，不含读取）：寻道时间（磁头移动到磁道所需的时间） + 等待时间（等待读写的扇区转到磁头下⽅所⽤的时间）
  • 读取磁盘数据的时间：寻道时间、旋转延迟时间（找块/扇区的时间）、传输时间

磁盘调度算法：

  • 先来先服务（FCFS）：访问序号即为申请序号
  • 最短寻道时间优先（SSTF）：被访问的下一个磁道为距离当前磁道最近（柱面号 → 磁道号(非磁头号) → 扇区号）的待访问磁道

缓冲区：略///

2 操作系统

2.1 PV操作

前P后V，易解。

2.2 ⻚式存储管理

页号查表 + 页内地址：

  • 逻辑/物理页地址：页号/页帧号 页内地址
  • 技巧：将页面大小化为2^n，可得页内地址的二进制位数为n，对应十六进制的后n/4位

页面淘汰算法：

  1. 淘汰状态位为1（在内存中）的页面
  2. 淘汰访问位为0（未访问过）的页面
  3. 淘汰修改位为0（未修改过）的页面

【例1】（2013下半年）某操作系统采用分页存储管理方式，下图给出了进程A和进程B的页表结构。如果物理页的大小为512字节，那么进程A逻辑地址为1111（十进制）的变量存放在（ ）号物理内存页中。假设进程A的逻辑页4与进程B的逻辑页5要共享物理页8，那么应该在进程A页表的逻辑页4和进程B页表的逻辑页5对应的物理页处分别填（ ）。

页式存储1

【第1问】
十进制数1111转成二进制为10001010111_2。物理页的大小为512字节，2^9 = 512，则页内地址为9个二进制位。故该变量的页号为10_2，即十进制数2，对应的物理页为4。

【第2问】
共享物理页8说明均对应物理页8，故均应填8

【例2】（2012下半年）进程P有6个页面，页号分别为0～5，页面大小为4K，页面变换表如下所示。表中状态位等于1和0分别表示页面在内存和不在内存。假设系统给进程P分配了4个存储块，进程P要访问的逻辑地址为十六进制1165H，那么该地址经过变换后，其物理地址应为十六进制（ ）；如果进程P要访问的页面4不在内存，那么应淘汰页号为（ ）的页面。

页式存储2

【第1问】
页面大小为4K，4\times 1024=2^{12}，则页内地址的位数为12位，对应十六进制的后3位165H。查表可得页号1对应的物理块号（页帧号）为3，故物理地址为3165H。

【第2问】
根据页面淘汰算法易知，应淘汰5。

2.2 文件系统

索引⽂件结构：

  • 直接索引范围：索引块数量 * 索引块大小
  • n级间接索引范围：物理块数量^n * 索引块大小
    • 物理块数量 = 数据块大小 / 地址项大小
    • 一般情况下，索引块大小 = 数据块大小

位示图：

  • 物理块数 = 磁盘容量 / 物理块大小
  • 位示图的大小 = 物理块数 / 机器字长 = 磁盘容量 / 物理块大小 / 机器字长

3 数据库系统

数据库关系模式、函数依赖

4 项目管理

成本计算、进度管理相关计算题型：

5 数学与经济管理

简单运筹学、数学建模：

图论：

发表评论