计算机操作系统实验指导第3版总结：深圳大学操作系统实验3内存分配与回收

试验目的

加深对内存分配与使用操作的直观认识；

掌握Linux操作系统的内存分配与使用的编程接口；

了解linux操作系统中进程的逻辑编程地址和物理地址间的映射；

实验内容

可以使用Linux或其它Unix类操作系统；

学习该操作系统提供的分配、释放的函数使用方法；

学习该操作系统提供的进程地址映射情况的工具。

实验环境

硬件：桌面PC

软件：Linux 或其他操作系统

实验步骤及说明

借助google工具查找资料，学习使用Linux进程的内存分配、释放函数，完成以下实验操作

操作部分：

1. 编写一个含1个全局变量和一个自定义函数的程序，运行该程序打印上述变量和函数的地址。展示和解说一个虚地址经过页表逐级转换的过程（20%）。

要求：借助Linux上的crash工具完成展示。记录该进程的页表起始地址；然后将打印出的全局变量地址，用rd、rd -p、pte命令获得的信息手工完成地址的逐级转换形成物理地址。重复上述过程，对函数地址进行变换，对比两者pte的不同。

1. 编写程序，连续申请分配六个128MB空间（记为1~6号），然后释放第2、3、5号的128MB空间。然后再分配1024MB。(30%)

要求：记录该进程的虚存空间变化（/proc/pid/maps），每次操作前后检查/proc/pid/status文件中关于内存的情况，简要说明虚拟内存变化情况。推测此时再分配64M内存将出现在什么位置，实测后是否和你的预测一致？解释说明用户进程空间分配属于课本中的离散还是连续分配算法？首次适应还是最佳适应算法？用户空间存在碎片问题吗？

1. 设计一个程序测试出你的系统单个进程所能分配到的最大虚拟内存空间为多大。(10%)

要求：用/proc/PID/maps展示此时进程空间使用情况，指出所分配空间在什么区域，检查进程剩余可用空间有多少。

1. 编写一个程序，分配256MB内存空间（或其他足够大的空间），检查分配前后/proc/pid/status文件中关于虚拟内存和物理内存的使用情况，然后每隔4KB间隔将相应地址进行读操作，再次检查/proc/pid/status文件中关于内存的情况，对比前后两次内存情况，说明所分配物理内存（物理内存块）的变化。然后重复上面操作，不过此时为读操作，再观察其变化(20%)。
2. 设计并运行第一个进程，使之分配若干物理页帧。然后设计并运行第二个进程，大量分配并使用物理内存。（20%）

要求：展示两个进程的物理页帧竞争的动态变化过程，即第二个进程抢占第一个进程原来所分配的物理页帧。使用/proc/PID/smap展示第一个进程分配和使用物理页帧前后的变化。使用/proc/PID/status记录两个进程的物理内存总量的变化。用/proc/meminfo记录系统整体使用情况的变化。

实验报告要求：

1. 按学校统一格式
2. 需要给出具体命令和自行编写的程序的源代码
3. 程序的设计需要给出设计思路或流程框图
4. 实验操作的截图需要有必要的说明文字

选作部分：

1. 分配足够大的内存空间，其容量超过系统现有的空闲物理内存的大小，1）按4KB的间隔逐个单元进行写操作，重复访问数遍（使得程序运行时间可测量）；2）与前面访问总量和次数不便，但是将访问分成16个连续页为一组，逐组完成访问，记录运行时间。观察系统的状态，比较两者运行时间，给出判断和解释。

实验结果

由于我在ubuntu18.04上多次安装crash不成功，最后决定转到centos中安装crash，首先输入yum install kexec-tools crash安装crash（图1-1），安装完成后，我们键入uname -r 查看当前版本号（图1-2），这里我的版本号为3.10.0-1160.el7.x86_64。

图 1‑1 安装crash

图 1‑2 查看当前版本号

根据当前版本号，进入http://debuginfo.centos.org/7/x86_64/下载内核rpm包（图1-3、1-4）。

图 1‑3 下载内核rpm包

图 1‑4 下载rpm包

使用rpm -ivh 命令安装rpm包（图1-5）。

图 1‑5 安装rpm包

安装完成后，根据题目要求编写代码crashdemo.c（图1-6），代码思路如下图。

图1 程序思路

图 1‑6 crashdemo.c代码

使用gcc编译运行代码（图1-7），我们可以看到var地址为0x60103c，函数地址为0x40057d，然后输入crash /usr/lib/debug/lib/modules/ 3.10.0-1160.el7.x86_64//vmlinux进入crash，然后查询到进程pid后切换到该进程（图1-8），注意到当前task struct地址为 ffff8a97c22f2100。

图 1‑7 运行crashdemo

图 1‑8 crash切换到目的进程

然后我们查看task_struct->mm_struct ->pgd内容，执行px ((struct task_struct *)0xffff99f501f04200)->mm->pgd以此查找页表（图1-9），我们可以看到页表起始地址位于 0xffff99f4e0694000的虚地址处，而内核虚地址和物理地址只相差一个常数（所谓的一致映射，不同于用户空间杂乱的映射），这 个 常 数 为 0xffff880000000000 ， 因 此 其 物 理 地 址 为 0x694000（图1-10） 。

图 1‑9 px指令

图 1‑10 求物理地址

根据64位地址转换原理，一个页 4KB 只能保存 512 项页表项（4096 字节/8 字节=512）， 虚拟地址菜用 4 级分页（9bit 9bit 9bit 9bit 12bit） ——对应于 PGD 索引/偏移、 PUD 索引/偏移、PMD 索引/偏移、PD 索引/偏移和页内偏移,已知var地址为0x60103c，转换为二进制为0000 0000 0000 0000 0000 0000 0110 0000 0001 0000 0011 1100。

根据分析，由于前面计算出虚地址 0x60103c 在 PGD 的偏移量为 0， 我们用 rd 0xffff99f4e0694000 虚地址方式读入0xffff99f4e0694000 单元， 获得的一个数据 0x80000001a069d067（图1-11）；

图 1‑11 rd查看pgd页表首地址

因为包含一些 flag，还要通过 pte 命令得到真正的物理页地址，如图得到的地址为 0x1a069d000（图1-12） ：

图 1‑12 pte求pgd物理地址

得到下一级页表 pud 的首地址 为 0x1a069d000 同样根据 pud 的偏移 0x0，得到下一级页表的首地址，在 pud 数组中存储的位置：0x1a069d000。然后通过rd -p完成（图1-13）。

图 1‑13 rd -p查看pud页表首地址

同样重复上述步骤，将数据 0x0000000178be1067 通过 pte 得到 pmd 的实际的物理地址：0x178be1000（图1-14）。

图 1‑14 查看pud物理地址

pmd 的首地址为 0x178be1000，然后根据 pmd 的偏移计算下一级页表的地址，在 pmd 数组中存放的位置：0x178be1000 0x3 * 8 = 0x178be1018，然后通过 rd -p 查看物理地址为 0x178be1018 处的数据0x00000001c111a067（图1-15）：然后pte查看（图1-16）

图 1‑15 rd-p查看pmd页表首地址

图 1‑16 pte查看pmd物理地址

然后根据 pte 的偏移，找最终的物理页框的地址，在 pte 数组中存储的地址：1c111a000 0x1 * 8 =0x1c111a008, 然后通过 rd -p 查看物理地址为 0x1c111a008 处的数据：最后得到0x80000001716b1867（图1-17）。

图 1‑17 得到pte物理地址

然后我们计算最终物理地址 0x80000001716b1867 0x3c=0x80000001716b18a3,最后pte得出最终物理地址为1716b1000（图1-18）。

图 1‑18 pte计算page页表首地址

我们最后rd -p读取最终物理地址为0x1716b1000 0x3c=0x1716b103c的值，读取结果为0xf423f

图 1‑19 rd-p读取int值

最后我们计算机算出来0xf423f就是999999，也就是我们的全局变量的值（图1-20）！我们通过vtop检查，发现答案正确（图1-21）！

图 1‑20 999999全局变量

图 1‑21 vtop检查

我们接着看函数地址0x40057d，它转化成二进制就是：0000 0000 0000 0000 0000 0000 0100 0000 0000 0101 0111 1101

应为PGD与PUD和前面全局变量var相同，故步骤省去,已知pmd首页地址为0x178be1000，我们直接用0x178be1000 8*0x2=0x178be1010, 然后通过 rd -p 查看物理地址为 0x178be1010 处的数据0x000000017eb9c067（图1-15）：然后pte查看pte首页地址为0x17eb9c000（图1-16）。

图 1‑22 rd-p查看pmd物理地址

图 1‑23 pte查看pte首页地址

已知pte偏移为0，所以我们直接rd -p 查看page地址为0x9e06d25（图1-24）

图 1‑24 rd-p查看page页表首地址

因为偏移是0x57d，所以0x9e06d25 0x57d=0x9e06d5a2，我们使用pte查看物理地址得0x9e06d000（图1-25），我们再按照0x9e06d000 0x57d=0x9e06d57d,即可得到函数物理地址，我们使用vtop查看，发现结果完全一样（图1-26）。

图 1‑25 pte查看page物理地址

图 1‑26 vtop查看结果

根据题目要求，我们写下allocation.c的代码（图2-1），程序流程如下图。

图2程序思路

图 2‑1 allocation.c代码

Gcc编译之后，我们开始运行程序，可以看到，一开始我们执行了pause，所以并未分配任何内存（图2-2）。

图 2‑2 执行allocation

我们对该进程查看maps情况（图2-3），我们可以看到heap区从地址559c2f350000-559c2f371000，这个应该是默认大小，然后我们查看该进程的status（图2-4），我们可以看到当前进程的虚拟内存大小为4512kb。

图 2‑3 maps查看heap区

图 2‑4 status查看虚拟内存

接着我们键入任意键来启动进程继续执行指令，可以看到allocation继续分配了6个128MB的内存（图2-5），我们打印的地址显示我们分配的缓冲区地址十分连续，他们的头尾之间仅仅相差了0x1000也就是4096字节，可能是为了防止越界。

图 2‑5 打印地址与计算

接着我们继续观察maps信息，我们可以看到多出来7f4ee2502000-7f4f12508000的内存（图2-6），换算后我们得到大小大约是768MB也就是6个128MB的内存 6*4096字节，总共也是805330944字节（图2-7）。

图 2‑6 观察maps打印信息

图 2‑7 换算得到内存大小

此时我们查看status中的信息，我们可以看到虚拟内存变成了790968KB（图2-8）。

图 2‑8 status查看内存变化

接着我们再输入任意字符串释放2/3/5缓冲区（图2-9），我们这时再进入status查看发现虚拟内存变成了397740KB（图2-10），也就是减少了393228KB，大概348MB，大约正是3个128MB缓冲区释放的大小。

图 2‑9 释放缓冲区

图 2‑10 status显示虚存变化

这时我们观察maps，发现heap区不再是连续的内存了，它们变成了3块大小为134221824KB的内存块，换算下来大概是128MB（图2-11）。

图 2‑11 maps显示heap区变化

经过之前的maps对比，我们发现heap的排布规律是从上到下分布的缓冲区序号从大到小（图2-12）。

图 2‑12 maps排布规律

接着我们再分配1024MB的空间，可以看到我们的这段空间的地址是0x7f4ea2501010-0x7f4ee2501010（图2-13），接着我们再查看maps，通过与之前对比我们发现1024MB的内存被扩展到了6号内存之后，也就是增加了0x1000的内存（图2-14）。

图 2‑13 分配1024mb空间

图 2‑14 对比maps发现拓展情况

接着我们开始分配64MB内存（图2-15），我们发现新内存地址为0x7f4f06506010-0x7f4f0a506010，然后通过maps观察发现，新分配的64MB内存区占用了之前释放的第二块128MB内存的缓冲区（图2-16）。

图 2‑15 分配64MB内存

图 2‑16 第二块缓冲区内存被重新占用

然后我们对代码稍作修改，将2/4缓冲区大小改为200MB/150MB，然后释放，最后添加140MB内存（图2-17），若为首次适应算法，则140MB内存区应该落在2号缓冲区，若为最佳适应算法，则应该落在4号缓冲区，程序思路如下图。

图3 程序思路

图 2‑17 修改后代码

执行代码后，我们运行到释放内存的哪一步，观察其maps信息（图2-18），然后再分配140MB后，我们发现其内存分配到了缓冲区2中，也就是200MB大小的内存块里，所以说明使用的是首次适应算法而不是最佳适应算法（图2-19）。

图 2‑18 内存信息对应

图 2‑19 140MB映射到了缓冲区2

综上所述，我们根据上面的实验结果，对问题就有了明确的解答：

根据题目要求，我们写下maxmemory.c代码，基本思路就是无限循环生成256MB的缓冲区，直到发生故障自动停止（图3-1），通过运行代码，我们发现生成了23*256=5888MB内存空间（图3-2），大概是6GB不到，符合系统内存大小（图3-3），程序思路如下图。

图4 程序思路

图 3‑1 maxmemory代码

图 3‑2 分配打印情况

图 3‑3 虚拟机内存

接着我们修改代码，将其while的无限循环改成只循环22次，也就是只分配22个256MB的内存区域（图3-4），程序思路如下图。

图5 程序思路

图 3‑4 循环23次分配内存

我们接着运行程序，并且使用free -m来查看剩余可用内存（图3-5），可以看到一共有6091MB内存，我们使用了5841Mb，还剩255MB，接着我们查看maps内容，发现内存被分到的heap区地址是7fc1c625f000-7fc336276000 ，计算后发现一共有5888MB（图3-6）。

图 3‑5 free查看剩余可用内存

图 3‑6 maps查看heap区

接着，我们写下maxmalloc.c代码，其代码基本思路就是仅仅使用malloc在while循环中不断分配1024MB的内存（图3-7），我们在运行后分析输出可以发现，虚拟地址在堆区的起始地址0x7fdfbc59610开始就不断地往外扩张，直到进入10开头的低地址，接着就开始溢出到ff的高地址，最后又回到7f开头的地址也就是和起始地址相近的地址（图3-8），程序框图如下图。

图6 程序思路

图 3‑7 maxmalloc代码

图 3‑8 maxmalloc输出结果分析

综合以上的实验现象，我们可以得到结论：虚拟地址空间是可以几乎无限申请的，但是前提是不写入数据，因为物理地址空间是有限的，如果写入内存中，那么我们能分配的虚拟地址空间也会变得有限。

根据题意，我们写下firstrthenw.c代码，代码思路就与题目类似（图4-1），接着我们运行程序，然后在另一个terminal里面查看status（图4-2），我们发现我们的初始虚拟内存大小为4512KB，物理内存大小为812KB，程序思路如下图。

图7 程序思路

图 4‑1 firstrthenw.c代码

图 4‑2 status查看

紧接着我们继续运行代码，开始分配内存，但是不进行任何读写操作（图4-3），接着我们查看status，发现虚拟内存变成了266660KB，相比之前增加了262148KB，换算下来大概就是256MB，符合代码逻辑（图4-4）。

图 4‑3 分配内存

图 4‑4 status观察变化

接着我们继续运行代码，开始读数据（图4-5），观察status发现虚拟内存使用没变化，物理内存使用变大了大概1.5倍，不算太明显（图4-6）。

图 4‑5 读数据

图 4‑6 status观察变化

接着我们开始写数据（图4-7），再利用status可以发现我们的物理内存大小从一开始的810KB变成了263500KB，增加了262690KB，换算下来就是增加了大约256MB（图4-6）。

图 4‑7 写数据操作

图 4‑8 status显著变化

综上所述，我们参考实验现象可以得出结论，linux的内存操作是只有真正写了之后才会占用物理内存的，否则分配内存，读取内存都是只占用虚拟内存。

我们使用free -m来查看内存和交换区的情况（图5-1），可以看到2GB的物理内存中，可用的只有921MB，而交换区可用的有2047MB，总共2968MB可用内存。

图 5‑1 free查看交换区与内存情况

我们编写exchangememory.c程序，程序思路是根据自己虚拟机的可用物理内存与交换机，然后分配相应空间，在此我先后申请并且写800MB的内存，总共1600MB内存，与总内存相近（图5-2），不申请2968MB内存是因为容易卡死，写得少也没有效果，程序思路如下图。

图8 程序思路

图 5‑2 exchangememory.c代码

我们生成2487与2488进程（图5-3），并且计划让2488抢占2487进程的内存，一开始的时候他们都没有分配申请内存，我们查看meminfo可以看到可用物理内存还有712872KB，大概696MB可用内存（图5-4）。

图 5‑3 2进程ps查看

图 5‑4 meminfo查看可用内存

我们接着让2487号进程使用800MB内存，此时系统中可用内存变成42MB左右大小（图5-5），接着我们使用/proc/2487/smaps 查看进程信息，我们可以看到2487占用了800MB的内存（图5-6），接着status也反映了确实占用了这么多内存（图5-7）。

图 5‑5 meminfo查看可用内存

图 5‑6 2487进程所占内存

图 5‑7 status查看2487进程

接着我们使2488号进程也开始占用内存，然后使用free -m查看内存情况（图5-8），发现现在仅剩1081 48=1129MB，与当初2968MB内存相差大约1600MB，与预想相近，接着我们使用status查看2487号进程，发现近半数内存被换出，并且有437568KB内存被2488进程占用（图5-9），我们再使用status查看2488号进程，发现确实2488号进程占用了2487号进程的物理页帧（图5-10）。

图 5‑8 free-m查看内存

图 5‑9 status查看2487进程

图 5‑10 status查号进程

首先我们使用free -m查看系统空闲物理页（图6-1），我们发现空闲物理页还有1271 1451=2722MB，于是我们编写代码TLBtest.c，代码思路根据题目所述即可（图6-2），程序思路如下图。

图9 程序思路

图 6‑1 free查看空闲页

图 6‑2 TLBtest.c代码

然后我们运行程序（图6-3），我们发现连续访问每页的情况下我们花费的时间只有2.77秒，而16页为一组访问花了3秒，我们分析原因可能是因为有TLB存在，连续访问每页的时候旁边的页会被拉进块表，从而减少了访问时间，而16个页访问时，有时会超出块表的存储大小，可能访问的下一页没有在TLB中而增加了访问时间。

图 6‑3 运行TLBtest

四、实验体会：（根据自己情况填写）

通过本次实验，我受益匪浅：

1. 通过对xv6系统的实验，增加了对进程调度的直观认识，明白了如何添加系统调用与简单程序。
2. 明白了调度在xv6中的重要作用以及运行原理，并且明白了如何简单的实现信号量机制。
3. 明白了slab内核内存管理的实现方法以及运行原理。
4. 掌握了系统里copy_on_write的编码实现。