返回学习路线

内存够不够：六种不同问题，一份可复算记录 ​

“明明还有空闲内存，为什么失败？”“页面全驻留，为什么仍然慢？”两句话都没有给出足够条件。这份终结任务要求把数量、连续性、区域资格、活跃驻留、翻译覆盖和节点位置分别核算，再识别哪项措施真正针对当前限制。

阅读入口与交付物 ​

入口是物理页分配与安全回收理路物理页分配与安全回收Physical page allocator · Page frame free list把页框所有权、空闲链、发布前清零和最后使用者释放串成分配协议，解释它与用户堆对象分配的不同粒度。和页表转换理路页表地址转换与访问权限Page table address translation · VPN PFN offset · 虚实地址转换由虚页号、页内偏移与PTE计算物理地址，分别检查驻留、访问类型和用户权限，并建立可检查的隔离不变量。。先用伙伴分配理路伙伴页分配与连续块合并Binary buddy allocation · Buddy system · 伙伴系统用对齐的幂二块分裂与合并管理连续页框，复算异或伙伴、内部碎片，以及空闲总数足够却无法满足大块请求的边界。与分区预算理路分区页分配与保留预算Page allocation zones · Zone watermarks · 分区水位将页框分配拆成区域资格、形状可用性与保留预算三个检查，追踪普通请求和受限设备请求，并区分教学阈值与实际系统水位。判断能否交付，再读工作集理路工作集窗口与驻留需求Working-set model · Working set window · 工作集模型用每进程引用窗口定义工作集并逐步更新，区分历史需求、实际驻留与未来预测，处理暂停、窗口选择和共享物理页去重。、替换范围理路局部与全局页面替换Local page replacement · Global page replacement · 局部全局替换在固定交错访问轨迹上比较全局LRU与局部配额，逐步复算缺页和淘汰对象，并用反向例子说明隔离与容量共享的取舍。和抖动控制理路抖动与内存负载控制Memory thrashing · Admission control for paging · 页面抖动把工作集容量压力与缺页阻塞连成可复算模型，说明CPU低利用率下继续加负载的反馈风险，以及准入、暂停和恢复的成本边界。。翻译与位置分支是大页覆盖理路大页与TLB覆盖范围Huge pages · Superpages · TLB reach在数据全部驻留的模型中复算大页减少TLB未命中的条件，分开翻译覆盖、物理连续性、内部碎片与权限变更粒度。、NUMA放置理路NUMA内存位置与迁移成本NUMA memory placement · First-touch allocation · NUMA page migration把页框所有权与节点距离分开，计算首次实际触页的放置、优先和绑定策略，以及线程位置变化下迁移页内容的回本门槛。；进入大页前需要旧TLB页理路TLB与地址翻译失效Translation lookaside buffer · TLB miss · TLB invalidation将翻译缓存键、权限和映射生命周期一起核对，区别TLB未命中与缺页，构造改PTE后仍越权的最短反例。的命中与缺页区分。

最终交付七份结果：空闲块集合，分区请求日志，工作集表，逐步替换轨迹，串行时间账本，TLB标签序列，迁移回本不等式。另写出每份结果的一项失败边界，证明你知道什么时候需要重建模型。

MEM-16是16个编号0至15的256字节教学页框。以下实验是独立重置的快照，不把上题剩余状态自动带入下题。参数只用于教学，不对应一台真实机器配置。

任务一：空闲数量与对齐形状 ​

把16帧全部分配成四个4帧块。先释放起点0与8，再请求8帧；之后释放起点4，再请求8帧。

请列每一步的非空 $F_k$，写出失败请求是否改变状态，并检查空闲页数加已分配页数等于16。另从全空池请求3帧，交出真实块大小、内部碎片和释放所需元数据。

核对。 四块交付后空闲0；释放0与8后 $F_2=\{0,8\}$，空闲8，但8帧请求失败且状态不变。再释放4，与0合成 $F_3=\{0\}$，另有 $F_2=\{8\}$；交付8后只剩 $F_2=\{8\}$，空闲4、占用12。请求3要order 2，取得起点0的4帧块，内部碎片1帧；释放时使用起点0和真实order 2，而不是“大小3”。

迁移。 若释放的改为4与8，空闲区间虽连续为 $[4,12)$，仍不是允许的对齐8帧伙伴块。指出为什么“两个相邻4帧块”不一定是伙伴。

任务二：有4页空闲，却拒绝普通请求 ​

D区有4帧，G区有12帧，初始空闲数 $(F_D,F_G)=(4,6)$。普通请求按G、D尝试，完成后所在区至少剩2页。受限设备只允许D，可动用这2页预算。请求均为独立单页或单页批量，暂不要求批内物理连续。

依次执行：普通4页、普通1页、普通1页、普通1页、设备2页、设备1页。对失败写出区域、预算或数量原因。

核对。 成功区依次为G、D、D、无、D、无；空闲对依次为 $(4,2),(3,2),(2,2),(2,2),(0,2),(0,2)$。第四项两区都不能突破普通预算。末项D已空，G虽有2页却不在设备允许集合。不能通过远端或不同区域回退悄悄改变硬资格。

迁移。 若再要求连续2页，只有计数表足以判断吗？不够，还必须提供该区符合order与对齐的可用块。若逻辑请求3页、伙伴分配实际取4页块，预算也必须扣4；空闲5、保留2时应拒绝，不能按3页需求误判通过。

任务三：窗口不是配额 ​

P引用 a b a c b d d d e，最近4次引用为窗口。在每步完成后列窗口、不同页集合与大小。P暂停一分钟期间没有引用，判断窗口是否自动变空。

核对。 大小为 1,2,2,3,3,4,3,2,2；第6、8、9步集合分别为 {a,b,c,d}、{b,d}、{d,e}。按进程引用次数计时，暂停不推进窗口。大小随窗口宽度非递减，但随时间可以减小。

若P工作集为 {Pa,Pb,S}，Q为 {Qc,Qd,S}，S是真实共享只读底层页，则联合需求5帧。若两进程只是碰巧都把各自私有页叫S，需求就是6帧。必须给页身份，不能只对虚拟页号字符串去重。

迁移。 改窗口为3，第6步大小为3；它描述历史，不保证第7步不会突然访问新页。

任务四：把跨进程干扰定位到两次淘汰 ​

独立重放 Pa Pb Qx Qy Pa Pb Qz Qw Qu Qv Pa Pb。对照全局4帧LRU与局部P2+Q2，每次列命中、缺页和牺牲页。

核对。 前4步均缺页，5、6均命中。全局7至12步分别淘汰 Qx,Qy,Pa,Pb,Qz,Qw，总缺页10。局部7至10步只淘汰Q的 Qx,Qy,Qz,Qw；最后两次P访问命中，总缺页8。按进程分解，全局P4/Q6，局部P2/Q6。

反向检验。 Q空闲，P访问 a b c 四轮：全局缺页3，固定局部P2缺页12。说明哪份未被使用的配额没有借给P，避免把第一条轨迹的优势夸成普遍支配。

任务五：从缺页数到历时 ​

单进程访问 a b c 四轮，每次引用带来1毫秒有用CPU工作，缺页额外串行等待5毫秒。没有I/O重叠和其他开销。比较2帧与3帧LRU。

核对。 缺页12与3，历时 $12+5\times 12=72$ 与 $12+5\times 3=27$；有用CPU比例 $1/6$ 与 $4/9$。若有别的进程可以在I/O期间运行，整机历时不能继续直接照抄这两项和。

再给8帧驻留预算，三个不共享的稳定工作集各3帧。三者全活跃时联合9帧装不下；暂留两个则需求6帧。但暂停第三者不自动释放其帧，还需保存内容并安全撤销旧访问。说明恢复成本与长期等待公平为什么不由容量不等式自动解决。

任务六：只有翻译发生未命中 ​

数据全部驻留，TLB初始空、全相联LRU、只有2项。基本页号0至7每轮依次访问，重复3轮。比较256字节基本页与对齐1024字节大页。

核对。 基本页翻译标签每轮为 0 1 2 3 4 5 6 7，24次miss；大页标签为 0 0 0 0 1 1 1 1，共2次miss。两者缺页均为0，名义覆盖512与2048字节。地址 0x1A5F 在大页下分为页号6与偏移 0x25F；映射到物理基址 0x6000 后得到 0x625F。

迁移。 改成基本页0至11循环3轮，大页标签每轮包含0、1、2三种，各一组连续4次。2项TLB每轮各有3次miss，总计9；“采用大页”不保证全部翻译永远留住。

任务七：回本条件必须说明未来在哪访问 ​

一页初始N0，本地访问100、远端180，迁到N1一次成本8000。

1. 此后全从N1访问，求严格获益的最小整数次数
2. 此后恰有3/4访问从N1发出，求一条真实有限轨迹可实现的最小获益次数
3. 若3/4是每次独立访问位置的概率，而非有限轨迹精确比例，求期望获益门槛
4. 若两节点各一半访问，是否有足够大的访问次数使此次迁移回本

核对。 第一问 $80m>8000$，最小101。第二问每次平均省40且m须被4整除，200打平、204首次严格获益。第三问201次的期望净收益40。第四问迁移前后平均访问成本相同，固定多付8000，不能靠增加次数偿还。

预测未来访问者位置、页迁移成本或可用目标帧发生变化时，结论必须重算。把线程移走与把页移走合并成一个没有成本的动作，会破坏上述账本。

运行核验器 ​

下载MEM-16标准库核验器，用普通Python 3运行：

python3 foundation-memory-capacity-check.py

脚本只做内存中的教学模拟，输出JSON，不读取机器内存设置，也不调整任何内核参数。它拒绝python -O，防止断言被禁用后仍误报通过。

除主例外，它检查65536种空闲页子集的327680个对齐形状判定，用49205个短串窗口对照计数实现与直接集合定义，并用29523个LRU案例对照独立的重用距离判据。有限穷举不是一般证明；它与正文块覆盖、窗口计数和替换状态不变量相互补充。