01一次缺页怎样跨过计组与操作系统
- 地址翻译发现存在位为 0
- 缺页故障:原指令尚未完成
- OS 选框,必要时写回脏页并调入
- 设备完成中断,等待者变就绪
- 调度恢复,更新映射后重做原指令
TLB 未命中先查页表,只有页面未驻留才进入这条调页路径。Cache 未命中通常向主存取块,代价与这条外存路径不同。
02局部性怎样把数组、缓存与工作集接起来
- 数组按存储顺序连续访问
- 相邻元素复用同一 Cache 块、同一页
- 空间局部性减少重复搬入
- 热点反复使用形成时间局部性
- 近期活跃页形成工作集,驻留集要能承接
固定总容量时,块或页增大虽能多带相邻数据,也会减少块数或页框数、增加一次搬入量;空间收益与占用代价一起判断。
03一份 TCP 数据从封装到确认,哪些边界不同
- 应用字节进入 TCP 数据区
- TCP 整段成为 IP 数据区
- IP 整包成为 MAC 数据的一部分
- 链路 FCS 随每跳重新封装生成
- 目的端重组、TCP 校验并推进字节确认
IP 首部校验不保护 TCP 首部;MAC 填充不计入 IP 总长;IP 分片不复制 TCP 首部;TCP 重传解决端到端未确认,和链路上的重新封装不是一个动作。
04“最小”必须连同目标记:图算法到路由
- Prim 比较树内外的一条连接边
- Kruskal 比较候选边且用并查集防环
- Dijkstra 比较源点到顶点的累计距离
- OSPF 传播链路状态后本地计算路径
MST 让连通全图的总边权最小,最短路径让源到目的累计路程最小。OSPF 使用最短路径思想,不是把整网最小生成树直接当作所有路由。
05磁盘 I/O 昂贵,三类数据组织怎样减次数
- B+ 树提高扇出,降低树高
- 范围查找先定位叶,再沿叶链继续
- 多路归并减少完整读写轮次
- 败者树减少每次选下一记录的比较
减少比较与减少读盘是不同收益。B+ 树非叶纯索引提高块内装载量;外部排序把归并趟数、每趟读写量和挑选开销分开。
06FIFO 与 LRU:同一规则,两个存储层次
- FIFO 记录装入次序
- 命中不改变 FIFO 的先后
- LRU 记录最后访问次序
- 命中把对象更新为最近使用
- 页或 Cache 块换出时,脏位再决定是否写回
淘汰依据与写回代价是两条轴。页面置换还受进程页框配额限制;Cache 替换受映射给出的候选行或候选组限制。
07共享、可见与互斥:不是同一项保证
- 线程共享进程地址空间
- 共享内存让不同进程看见同一数据
- 读旧值—计算—写回仍可交错
- 互斥或原子更新保护复合修改
- 信号量还可规定前驱—后继顺序
能够访问同一个对象,只解决通信或共享条件;操作是否被拆开、顺序是否满足、是否会饥饿,需由相应机制另外建立。
08容量、占用与可新增量:别把一个数字当成全部
- 工作集给需求,驻留集给供给
- TCP 窗口给允许在途上限
- 已发未确认量占据发送额度
- 剩余可发 = 上限 − 已占用
- 容量足够还要检查对象与位置是否正确
TCP 的上限还受接收窗口与拥塞窗口共同约束;驻留集则要留住工作集对应的页。共同的数量思路可以迁移,各自具体含义仍分层保留。
09一道原始报文题:从十六进制走到序号、填充与跳数
- 先用版本与 IHL 划出 IP 头
- 协议字段决定怎样读上层
- TCP 标志 + seq/ack 还原建连及数据进度
- IP 长度决定是否需要 MAC 填充
- 确认同一报文后,用 TTL 差数路由跳
同一题中的 4 B 首部单位、8 B 分片单位、字节序号与 46 B 最小载荷分别属于不同约束。数值串到一张报文里,仍要按层拆解。
10一种地址,四次计数:数组—页—TLB—Cache
- 逻辑下标按元素大小转成字节地址
- 按页内偏移判断是否跨页
- 虚页号去查 TLB,未命中查页表
- 物理地址按组索引与标记查 Cache
- 按真正的读写次数统计缺失率
一轮循环不一定只有一次访存;一个页也不是一个 Cache 块。地址在每一层按各自粒度拆分,低位重合不代表高位标记相同。
11同一个文件:名字、打开、映射、数据块
- 目录把名字连到文件身份
- open 建立打开引用和读写状态
- read 按位置通过文件索引定位块
- mmap 把文件页接入虚拟地址空间
- close、unlink 与解除映射各解除自己的关系
一个名字不等于一次打开,一个打开引用不等于文件全部数据已读入;映射同一文件还需要正确同步共享访问。
12从命令到异常:程序的五种“位置”
- 代码所在区不等于局部变量所在区
- 指针自身位置不等于所指对象位置
- 用户程序请求服务不等于用户态执行服务
- 进入内核不等于一定切换进程
- 故障修复后可能重新执行原指令
每次先明确所问是存放区域、权限模式、执行者身份、运行状态还是返回地址,再使用对应规则。
N26路由器查表把一个数据报转发出去,属于控制平面还是数据平面?
数据平面;计算、更新转发表或下发规则属于控制平面工作。
N01TCP 首部属于控制信息,为什么 IPv4 首部校验和不检查它?
它只是在 TCP 层属于首部;到了 IP 层,整个 TCP 段已是 IP 的数据部分。IPv4 的校验边界停在自己的首部。
N02IPv4 IHL=6,是否表示首部长 6 B,或选项长 6 B?
表示全部 IPv4 首部长 6×4=24 B;基本首部为 20 B,所以选项与填充合计 4 B。
N22以太网 MTU=1500,能否把 MAC 帧总长也写成 1500?
不能。1500 是装在 MAC 中的上层分组上限;普通未标记帧还要加 14 B 首部与 4 B FCS,合计 1518 B。
N20IP 标识和 TCP 序号都是编号,能否用同一含义理解?
IP 标识把同一原始数据报的片归为一组;TCP 序号定位字节流中的每个字节。一个认数据报归属,一个认流内位置。
N23UDP 长度是 21 B,计算校验时临时补了 1 B 零,长度应改成 22 吗?
不改,仍为 21。临时补零只是为了按 16 bit 分组求和,接收方同样在计算时补足。
N21一个 TCP 段 ACK=1、PSH=1 且携带 200 B 数据,消耗多少序号?
这 200 B 数据消耗 200 个序号。ACK 与 PSH 本身不额外占号;只有 SYN、FIN 等明确的控制语义按规则占用。
关联推演标志 02H、12H、10H 为什么能串成三次握手?
它们分别是 SYN、SYN+ACK、ACK。再核验前两份 seq 被下一份 ack 加 1 确认;仅看标志还要与编号和方向合读。
N03未分片 IPv4 总长度 1000,IHL=6,TCP 数据偏移=8,TCP 数据有多少?
1000−6×4−8×4=944 B。先分别换算两种首部长度,再从 IP 总长度扣除。
N04正常经过路由器,TTL 减了 1,为什么重算 IP 校验但不因此重算 TCP 校验?
TTL 属 IPv4 首部校验范围,却不在 TCP 首部、数据或伪首部中;TCP 的参与校验内容没有因这个 TTL 改动而改变。
关联推演40 B 的纯确认 IP 包装进最短以太网帧,哪些字节进各层校验?
MAC 另补 6 B;FCS 保护 MAC 头、40 B IP 包和 6 B 填充。IPv4 只校验自己的 20 B 首部;TCP 校验其 20 B 首部及伪首部,MAC 填充不进入 TCP 校验。
N05无数据的 TCP 纯 ACK,IPv4 与 TCP 都无选项,普通以太网需要多少填充?
IP 总长 20+20=40 B;MAC 数据至少 46 B,所以补 6 B。MAC 帧长 14+40+6+4=64 B,IP 总长度仍为 40。
N18IPv6 有 8 B 扩展首部和 100 B UDP 数据报,有效载荷长度写多少?总分组长多少?
有效载荷长度 108 B,整个分组长 40+108=148 B。UDP 自己的长度仍为 100 B。
N06跨网发送时 ARP 查到了网关 MAC,IP 目的字段应填谁?
仍填最终目标主机的 IP。网关只是本跳接收者,放在 MAC 目的地址,不替换端到端 IP 目的地址。
N07192.168.0.255/23 是广播地址吗?
不是。/23 的主机部分有 9 位,其中最高一位为 0;该子网广播地址是 192.168.1.255。判断主机位全 1,要看完整掩码,不能只看最后一个字节。
N08ARP 请求是广播,所以 ARP 使用 UDP 吗?
不使用。广播是链路发送范围,UDP 是传输层协议;ARP 直接装在以太网帧中,类型字段为 0x0806。
关联推演NAPT 同时改源 IP 与 UDP 源端口,报文长度会增加吗?
不会。字段值变化不改变位数;IP 首部校验及启用的 UDP 校验随参与计算的内容调整,UDP 长度仍是原首部加原数据。
N25终端通过 AP 向外网服务器发 IP 包,地址 1 与地址 3 都填外网服务器 MAC 吗?
地址 1 是 AP;地址 3 通常是本局域网网关的 MAC。远端服务器 IP 写在 IP 目的字段,远端 MAC 不跨路由传来作本地寻址。
N09UDP 面向报文,是否因此规定它在下层绝不能被分片?
不是。UDP 保留的是端到端交付的报文边界;承载它的 IPv4 数据报仍可分片,先重组后才交给 UDP。
N24A→B:seq=1000、ack=500、窗口 300、数据 100 B。A 的下一个数据序号是多少?窗口限制谁?
A 下一个数据序号是 1100;窗口限制 B→A 的发送范围,从 500 起的 300 B。
N10A 发 FIN 后,B 还有数据要发,此时谁还能发数据?
A→B 的发送方向已经结束,B→A 仍可继续。A 仍能接收 B 的数据并发送确认。
N113 bit 序号,GBN 发送窗最多多少?SR 两窗相等时最多各多少?
GBN 最多 7;SR 最多各 4。序号共有 8 种;SR 需给新旧接收窗口留出不混淆的范围。
N12ACK 号未变,但接收窗口从 0 变成 4000 B,可能发生了什么?
接收应用取走了已在缓冲区的数据,空出空间;虽然没有新字节到达,接收方仍可通告更大的窗口。
N14浏览器从 50000 端口访问服务器 HTTP 80,回复报文的源、目的端口是多少?
源端口 80,目的端口 50000。服务端口描述服务角色,不意味着请求和响应里都作目的端口。
N15HTTP 使用持久 TCP 连接,是否就与“HTTP 无状态”冲突?
不冲突。连接复用回答通道是否重建,会话状态回答服务器是否把前后请求识别为同一个用户过程。
N16OSPF 使用最短路径算法,能否用最小生成树替代?
不能。最短路径要分别缩短源点到各目的的路程;最小生成树优化连接全网的总边权,目标不同。
N13“以太网不提供 MAC 层确认重传”与“碰撞后重发”矛盾吗?
不矛盾。后者是发送端检测到介质竞争失败而退避;前者说接收端不对收到的帧建立 ACK、超时重传的可靠交付机制。
N17同一路径带宽变为原来的 2 倍、RTT 不变,填满链路需要的窗口怎样变?
按带宽时延积模型,在途窗口需求也约增为 2 倍;原小窗口可能变成吞吐瓶颈。
关联推演1 个大文件拆为 N 个等长分组,经过 H 条同速链路,为什么不是 NH 次串行时间?
不同分组可在不同链路重叠。第一组经历 H 次发送,后续 N−1 组各再加一个发送节拍,所以忽略传播等时为 (N+H−1)L/R。
N19生成多项式是 x⁴+x+1,应追加几位 CRC?二进制除数几位?
追加 4 位校验;除数 10011 共 5 位。最高次数决定余数宽度,不是把除数的位数当 CRC 长度。
D01给出单链表第 k 个元素的序号,删除总时间一定 O(1) 吗?
先沿链找到它及必要前驱通常 O(n),再改链接 O(1);总成本仍由定位主导。
D13同一个模式串,分别在两个不同主串里匹配,需要因为主串不同重算 next 吗?
不需要。next 来自模式串内部的前后缀关系。
D15行优先 A[4][8],int 为 4 B,A[2][3] 相对 A[0][0] 偏移多少?
(2×8+3)×4=76 B。先得元素下标 19,再换成字节。
关联推演结构体字段长度相加是 7 B,数组元素步长就一定是 7 B 吗?
不一定。先处理字段对齐和尾部对齐;该题按边界对齐后一个结构体占 8 B,数组按 8 B 前进。
D02先序 AB、后序 BA 能确定 B 是 A 的左孩子还是右孩子吗?
两种树都产生这些序列,因此不能确定;加入中序即可区分 BA 与 AB。
D03一个二叉树有 10 个度为 2 的结点,叶子数是多少?需要知道度为 1 的结点数吗?
叶子数是 11。n₀=n₂+1 中度为 1 的结点已在两种计数中抵消,不需要知道它的个数。
D14右指针有值,就一定能把它作为右子树根继续递归吗?
线索树还要检查标志位。若它是后继线索,就表示遍历邻居,不是右孩子。
D04数组按层构成大根堆,能否直接对这个数组做折半查找?
不能把堆序当成全局线性有序。堆只保证父子关系,不保证数组整体递增或递减。
D05AVL 的 LL 情形为什么是右旋,而不是名字里的“左旋”?
LL 描述从失衡结点出发的增长方向:左孩子的左侧过重。右旋把这部分提升,才会抵消失衡。
D06同样需要返回一个关键字区间内的大量记录,B+ 树的结构优势在哪里?
先自根找到区间起点所在叶,再沿有序叶链连续取后续记录,无需为每个关键字重新从根开始查找。
D07把同一稀疏图从邻接矩阵改成邻接表,BFS 的搜索规则变了吗?
没有,仍是队列逐层扩展。变化的是枚举邻接点的成本,因此时间与空间复杂度随表示改变。
D08Prim 与 Dijkstra 都“选最近的顶点”,为什么不能交换使用?
Prim 的近是接到已选树的一条边便宜;Dijkstra 的近是从指定源点累计路程短。候选值的语义不同。
D09两个并行分支都需 10 天,只把其中一支缩到 8 天,工程能提前吗?
另一支仍需 10 天,总工期仍是 10 天。这体现多条关键路径对工期的共同制约。
D11开放定址中,为什么“已删除”与“从未用过的空位”不能同样处理?
从未用过的空位可作为查找失败的边界;已删除位置后面仍可能存着沿原探测链插入的目标。
D10一趟直接插入后,前 5 个元素有序。它们都已到最终位置了吗?
没有。后续可能读到更小元素,插到前缀前方,使这些元素整体右移。局部有序不等于全局归位。
关联推演“最坏时间平方级”能推出“最坏移动也平方级”吗?
不能。简单选择排序做平方量级比较,但每趟最多交换一次,移动量是线性的;比较量与搬移量要拆开。
D12败者树与置换选择都“选最小”,能否认为作用相同?
败者树降低 k 路当前候选中选最小的比较开销;置换选择决定怎样产生较长的初始有序段,影响段数和后续趟数。
C0132 位 CPU 的 MAR 一定是 32 位吗?
机器字长与地址位宽描述不同对象。MAR 取决于寻址范围;不能仅凭“32 位 CPU”推出。
C02主频提高一倍,但同一程序的 IC 不变、CPI 也提高一倍,CPU 时间怎样变?
IC×CPI/f 不变,CPU 时间不变。主频收益被每条指令拍数增加抵消。
C03结果最高位是 1,就能断定这次有符号运算溢出吗?
不能。最高位反映补码结果的符号;溢出要看操作数符号与结果符号关系,或等价的进位判据。
C04单精度小数字段只有 23 位,为何能精确表示连续的 24 位二进制有效数字?
规格化数另有隐藏的前导 1;23 个显式小数位加 1 个隐含位,共 24 位有效精度。
C05“这个整数在 float 范围内,所以转换必然精确”少检查了什么?
有效精度。即使数量级在范围内,若需要的有效二进制位多于 24 位,转换仍可能舍入。
关联推演1122334455667788H 按小端从 8040H 存放,8046H 为什么是 22H?
从低地址到高地址依次放 88、77、66、55、44、33、22、11。8046H 比首址高 6 B,取到 22H;不能照着位串从左向右分配地址。
C06SRAM 不需要刷新,是否表示断电也能保存?
不是。SRAM 与 DRAM 都是易失存储器;是否刷新与是否非易失是不同属性。
C154 片 1K×8 位芯片组成 1K×32 位,与组成 4K×8 位有何不同?
前者位扩展,四片同址并行输出;后者字扩展,高位地址选择其中一片,地址深度扩大。
C07TLB 未命中、Cache 未命中,目标页仍可能在主存吗?
可以。页表可指出页已驻留;随后直接从主存取块即可,既无需磁盘调页,也不代表地址非法。
关联推演两路组相联 TLB 共 4 项,虚页号 12 位,标记几位?
共有 2 组,组索引 1 位,TLB 标记为虚页号余下 11 位;不是从物理地址中扣减。
C08全写法配非写分配法,CPU 写一个已经在 Cache 的地址,写哪里?
这是写命中:更新 Cache,并把写操作送往下层。只有写不命中时,非写分配才表示不调入。
关联推演题目给 Cache 数据区 128 KB,还问总容量,为什么不直接写 128 KB?
数据区以外,每行还要有标记、有效位和题目要求的控制位。先算每行附加位数,再乘行数,最后与数据区相加。
C17把乘法器换成更快的实现,是否必然改变 ISA?
不必。只要可见指令语义、编码和约定保持,可以只改实现与性能。
C09寄存器寻址与寄存器间接寻址,同样给出寄存器编号,差别在哪里?
前者寄存器内容就是操作数,后者寄存器内容是操作数的内存地址,还要按这个地址访存。
C10RISC 是否就是“采用硬布线控制器”的另一种名称?
不是。RISC 是 ISA 设计风格,硬布线是控制实现方式;它们有典型搭配,但不是一个分类维度。
C11为什么“有转发”仍不能让紧邻 Load 的使用者总是零停顿?
因为使用者需要数据的时刻可能早于 Load 读回数据的时刻。转发能缩短传递路径,不能提前产生尚不存在的数据。
C16处理器有多个核,多对一模型中的多个用户线程能否自然分到各核并行?
不能。内核只见到一个可调度实体,用户线程映射模型限制了可分派的执行通路。
C12缺页发生时,把返回地址设为下一条指令,会丢掉什么?
故障指令本来尚未完成。直接跳过会丢掉这次取数或写数,所以修复后应重执行原指令。
C13DMA 工作时,CPU 是否完全不再参与这次 I/O?
仍负责发起配置和结束处理,也可能受主存总线竞争影响;省去的是逐字执行搬运指令。
C14一个地址处于统一编址的地址空间,是否一定对应 DRAM 单元?
不一定。这个地址也可以映射到设备接口寄存器,由读写动作访问设备。
O01一次系统调用没有阻塞,处理完就返回原程序。发生了什么切换?
发生用户态与内核态之间的模式切换;可以始终是同一个进程,没有进程切换。
O19VFS 是否意味着文件只在内存、不在外存?
不是。VFS 提供统一文件操作接口,具体存储仍由相应文件系统和设备实现。
O20全局指针 p 指向 malloc 得到的对象,p 与 *p 必须在同一区域吗?
不必。p 自身是全局数据,所指动态对象位于堆。
O02两个线程共享堆,为什么还要各有一个栈?
堆是进程共享的动态数据区;栈记录各线程自身的调用链、局部变量和返回位置,执行进度不同就需要各自保存。
O03磁盘中断到来后,被唤醒的进程是否立刻运行?
先进入就绪态。CPU 是否立刻改执行它,由调度和抢占规则决定。
O04周转时间很长,是否一定说明就绪等待时间很长?
不一定;大量 I/O 阻塞也会拉长周转。周转统计全程,就绪等待只统计等待处理器。
O05长任务总被新到的短任务挤下去,是死锁还是饥饿?
饥饿。系统仍在推进,只是选择规则长期不照顾它;没有必然形成资源循环等待。
O17共享内存没有消息复制开销,是否就不需要同步?
仍需要。双方可能同时读写;共享映射只保证访问同一内容,不保证复合操作不可分割或执行次序正确。
O06空缓冲区中,消费者先 P(mutex) 再 P(full),问题在哪里?
消费者拿锁后因 full 不足而阻塞;生产者需要同一把锁才能放产品,结果谁也无法创造推进条件。
关联推演三个人连续作业,共用工具,还限制未完成任务数,为什么不能只设 mutex?
mutex 只管工具独占;工序先后要事件信号量,数量上限要容量信号量。先满足数量条件,再进入共享工具的临界区。
O07剩余资源足够满足这一次申请,为什么银行家仍可能拒绝?
这次分出资源后可能破坏安全序列,使所有进程的剩余最大需求无法找到可依次满足的完成顺序。
O08空闲空间合计足够,动态分区仍装不进进程;分页为什么可能装得进?
动态分区需要一整段连续空间;分页只要求足够数量的空闲页框,页框可以不相邻。
O15TLB 有 64 项,页从 4 KiB 增到 8 KiB,其覆盖范围怎样变?
从 256 KiB 增到 512 KiB。项数未变,每项映射的页面扩大一倍。
O143 个页 A、B、C 循环访问,只给 2 个页框。最该先解决什么?
先补足驻留容量或减少同时竞争内存的进程。活跃页总有一个放不下,仅更换淘汰算法难消除这种反复换页。
关联推演保证一条指令能执行与避免工作集反复换出,是同一条页框条件吗?
不是。前者沿该指令取指和寻址路径列同时需要的页;后者由近期活跃页需求估计容量,要让驻留集能承接工作集。
O16一个进程大量缺页后夺走别人的页框,为什么其他进程也开始大量缺页?
它们的驻留集被压小,原本能留住的工作集被破坏,缺页压力随全局置换传播。
O09页面 A 最早调入,但刚被再次访问。FIFO 与 LRU 会怎样看它?
FIFO 仍把 A 看作最早调入者;LRU 已把 A 视为最近使用者。后续淘汰顺序可能因此不同。
关联推演访问前已经驻留 3 页,LRU 计数从空内存开始会错在哪?
初始驻留页可以直接命中,且命中更新最近次序;把它们当空会多算缺页,也会改变下一次淘汰对象。
O18目录和空闲位图通常由哪一步建立:物理格式化还是逻辑格式化?
逻辑格式化。物理格式化解决扇区等底层记录结构。
关联推演分区、逻辑格式化、物理格式化如何按依赖排列?
先建立物理扇区结构,再划分区范围,再在分区上建立文件系统管理结构;格式化的层次不同。
O10把每块的链接指针集中进 FAT,是否就变成每文件的直接索引表?
没有。FAT 项仍给“下一块”,仍要追链;每文件索引表直接按逻辑块次序给对应物理块号。
O11两个进程分别打开同一文件后,一个已读到第 100 B,另一个是否也必须从第 100 B 继续?
不必。共享的是文件对象,分别打开的当前读写位置可以不同;题目应分别维护各自的打开状态。
关联推演新建文件时,目录项为什么不把所有权限信息也再存一遍?
目录主要把文件名连接到索引结点,权限等属性由索引结点管理;两种结构各负责一环。
O12给打印机增加 SPOOLing 后,打印机是否真的能同时打印两份?
物理设备仍顺序工作。多个进程可以先把任务提交到磁盘队列,因此不必独占打印机直到整份输出结束。
O13一次回卷没有处理请求,计算磁头总移动距离时能否省掉?
若题目统计实际移动距离,回卷仍移动,仍应计入;是否服务请求不改变磁头确实移动这一事实。