伙伴算法思想
这是我在一个论坛里看到的，你也参考参考吧。C++的虚函数
======================
C++使用虚函数实现了其对象的多态，C++对象的开始四个字节是指向虚函数表的指针，其初始化顺序是先基类后派生类，所以该虚函数表永远指向最后一个派生类，从而实现了相同函数在不同对象中的不同行为，使得对象既有共性，又有其个性。
内存池分配、回收之伙伴算法
=======================
伙伴算法是空闲链表法的一个增强算法，依次建立2^0\2^1\2^2\2^3...2^n大小的 内存块空闲链表，利用相邻内存块的伙伴性质，很容易将互为伙伴的内存块进行合并移到相应的空闲链表或将一块内存拆分成两块伙伴内存，一块分配出去，另一块挂入相应空闲链表，使得内存的分配和回收变得高效。
AVL树
=======================
AVL树是一个平衡二叉树，其中序遍历是从小到大排序的，该结构插入节点和检索非常高效，被广泛应用
快速排序
=======================
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。效率非常高
密码学之非对称加密协议（公钥、私钥加密协议）
======================
非对称加密算法需要两个密钥，用其中一个加密产生的密文，只能通过另外一个密钥解密，密钥持有者A可以将其中一个公开，称为公用密钥，另外一个秘密保存称为私钥，这样当某人B想给A传一封秘信时，只要将密信使用A的公钥加密后，就可以放心使用各种信道将迷信传给A了，因为该密信只有A可以解密，第三者截取因为无法解密而毫无意义。
该算法很好地解决了密钥的安全传递的问题，因为公钥和加密算法都是公开的，私钥不需要传输。
密码学之数字签名协议（身份鉴别、防抵赖）
======================
数字签名也是建立在非对称加密基础之上的，如果A君用它的私钥将文件加密后在发布，A君就无法抵赖该文件是其发布的，因为其他人能通过A君的公钥将文件解密就说明，如果算法可靠，该文件一定是A君用其私钥加密的。
由于非对称加密算法的加密和解密很慢，现在的数字签名并非是将其要发布的信息用其私钥加密，而是先用一个单项散列算法如（MD5）产生一个该信息的比较短的指纹（hash值），对其指纹用其私钥加密后和信息一并发布，同样达到了防抵赖的作用。
无回溯字符串模式匹配-kmp算法
======================
他是根据子串的特征，当匹配失败时，不需要回溯，而是直接将字串向后滑动若干个字节，继续匹配，极大提高了匹配速度。该算法被广泛使用。详细请参考数据结构教程。
最小路径选路-迪杰斯特拉算法、弗洛伊德算法
======================
学习数据结构的时候，印象最深的就要算kmp算法和最小路径算法了，因为理解他们比较费脑子，我是不可能发明这些算法了，发明他们的都是天才，呵呵。
使用最短路径的算法曾经帮人写过一个小东西，还是很有效的，记得是使用的弗洛伊德算法的一个变种，要详细了解的朋友可以查找相关资料，想将他们使用在你的项目中，代码直接从教科书上抄就可以了，不需要理解。
tcp协议之-nagle算法
======================
tcp、ip中令人叫绝的想法很多，印象最深的要算nagle算法了。
tcp出于效率和流量控制的考虑，发送端的数据不是产生多少就马上发送多少，一般是等到数据集聚到发送缓冲区长度的一半或者数据达到最大tcp数据包数据部分长度（好像是65515）才启动发送，而且还要看接受端可用缓冲区的大小，如果接受端产生一个回应报文通知发送端没有接受空间了，发送端哪怕缓冲区已经满了，也不会启动发送，直到接受端通告发送端其已经有了接受数据的空间了。
这样就有一个问题，假如发送端就是要发送一个小报文（比如10个字节），然后等待对方的回应。按照上面的方案，tcp会一直等数据收集到一定量才发送，于是矛盾就产生了。应用层不再发数据，tcp等不到足够的数据不会将10个字的数据发送到网卡，接收端应用层收不到数据就不会回应发送端。
你也可能说，可以让修改发送端发送条件，不一定要等到足够的数据再发送，为了效率考虑，可以考虑延时一定的时间，比如说1秒，如果上层还没有数据到来，就将发送缓冲中的数据发出去。当然这样也是可行的，尽管应用端白白等了1秒钟啥也没干，呵呵。
其实nagle算法很好解决了该问题，它的做发是链接建立后的第一次发送不用等待，直接将数据组装成tcp报文发送出去，以后要么等到数据量足够多、要么是等到接受方的确认报文，算法及其简单，而且很好解决了上面的矛盾。
socket之io模型设计
======================
windows下socket有两种工作方式：
1）同步方式
2）异步方式
同步socket又有两种工作模式：
1）阻塞模式
2）非阻塞模式
阻塞模式是最简单的工作模式，以tcp的发送数据为例，如果发送缓冲区没有空间，send调用就不会返回，一直要等到能够发出一点数据为止，哪怕是一个字节，但是send返回并不表示我要发送的数据已经全部提交给了tcp，所以send返回时要检查这次发送的数量，调整发送缓冲指针，继续发送，直到所有数据都提交给了系统。
由于其阻塞的特性，会阻塞发送线程，所以单线程的程序是不适合使用阻塞模式通信的，一般使用一个连接一个线程的方法，但是这种方式对于要维护多个连接的程序，是个不好的选择，线程越多，开销越大。
同步非阻塞模式的socket不会阻塞通信线程，如果发送缓冲区满，send调用也是立刻返回，接受缓冲区空，recv也不会阻塞，所以通信线程要反复调用send或recv尝试发送或接收数据，对cpu是很大的浪费。
针对非阻塞的尴尬，接口开发人员发明了三种io模型来解决该问题：
1）选择模型（select）
2）异步选择模型（AsyncSelect）
3）事件选择模型（EventSeselect）
其思想是根据io类型，预先查看1个或n个socket是否能读、写等。
其select本身来说，select是阻塞的，可以同时监视多个socket，只要所监视的其中一个socket可以读、写，secect调用才返回
异步选择模型其select是异步的（异步是不会阻塞的），是将监视任务委托给系统，系统在socket可读、写时通过消息通知应用程序。有一点需要说明，假如应用程序已经有很多数据需要发送，当收到可写通知时，一定要尽量多地发送数据，直到发送失败，lasterror提示“将要阻塞”，将来才可能有新的可写通知到来，否则永远也不会有。
事件选择模型也是将监视socket状态的工作委托给系统，系统在适当的时候通过事件通知应用程序socket可以的操作。
除了同步工作方式外，还有一种叫异步工作方式
异步工作方式是不会阻塞的，因为是将io操作本身委托给系统，系统在io操作完成后通过回调例程或事件或完成包通知应用程序
异步工作方式有两种io模型和其对应，其实这两种模型是window是异步io的实现：
1）重叠模型
2）完成端口
重叠模型通过事件或回调例程通知应用程序io已经完成
完成端口模型比较复杂，完成端口本身其实是一个io完成包队列。
应用程序一般创建若干个线程用来监视完成端口，这些线程试图从完成端口移除一个完成包，如果有，移除成功，应用程序处理该完成包，否则应用程序监视完成端口的线程被阻塞。
select模型是从UNIX上的Berkeley Software Distribution(BSD)版本的套接字就实现了的，其它四种io模型windows发明的，在windows中完成端口和异步选择模型是使用比较广泛的，一般分别用于服务端和客户端开发。
这五种io模型设计还是比较巧妙的：三种选择模型很好解决了“同步非阻塞”模式编程的不足；重叠模型和完成端口是windows异步io的经典实现，不局限于网络io，对文件io同样适用。
说点题外话，socket的send完成仅仅是将数据（可能是部分）提交给系统，而不是已经发送到了网卡上，更不是已经发送到了接收端。所以要知道你的数据已经发送到了对方的应用层的唯一方法是，让对方给你发送一个应对包。
发送数据要注意，对应tcp，要防止发送和接收的乱序，对于发送，一般应该为每一个链接建立一个发送队列，采用类似nagle的算法启动数据发送。
一次发送可能是你提交数据的一部分，一定要当心，否则出问题没处找去。
❷ Netty内存管理
ByteBuf底层是一个字节数组，内部维护了两个索引：readerIndex与writerIndex。其中0 --> readerIndex部分为可丢弃字节，表示已被读取过，readerIndex --> writerIndex部分为可读字节，writerIndex --> capacity部分为可写字节。ByteBuf支持动态扩容，在实例化时会传入maxCapacity，当writerIndex达到capacity且capacity小于maxCapacity时会进行自动扩容。
ByteBuf子类可以按照以下三个纬度进行分类：
在进入内存分配核心逻辑前，我们先对Netty内存分配相关概念做下了解。Netty内存管理借鉴jemalloc思想，为了提高内存利用率，根据不同内存规格使用不同的分配策略，并且使用缓存提高内存分配效率。
Netty有四种内存规格，tiny表示16B ~ 512B之间的内存块，samll表示512B ~ 8K之间的内存块，normal表示8K ~ 16M的内存块，Huge表示大于16M的内存块。
Chunk是Netty向操作系统申请内存的单位，默认一次向操作系统申请16M内存，Netty内部将Chunk按照Page大小划分为2048块。我们申请内存时如果大于16M，则Netty会直接向操作系统申请对应大小内存，如果申请内存在8k到16M之间则会分配对应个数Page进行使用。如果申请内存远小于8K，那么直接使用一个Page会造成内存浪费，SubPage就是对Page进行再次分配，减少内存浪费。
如果申请内存小于8K，会对Page进行再次划分为SubPage，SubPage大小为Page大小/申请内存大小。SubPage又划分为tiny与small两种。
负责管理从操作系统中申请到的内存块，Netty为了减少多线程竞争arena，采用多arena设计，arena数量默认为2倍CPU核心数。线程与arena关系如下：
线程本地缓存，负责创建线程缓存PoolThreadCache。PoolThreadCache中会初始化三种类型MemoryRegionCache数组，用以缓存线程中不同规格的内存块，分别为：tiny、small、normal。tiny类型数组缓存的内存块大小为16B ~ 512B之间，samll类型数组缓存的内存块大小为512B ~ 8K之间的内存块，normal类型数组缓存的内存块大小受DEFAULT_MAX_CACHED_BUFFER_CAPACITY配置影响，默认只缓存8K、16K、32K三种类型内存块。
内存块缓存容器，负责缓存tiny、small、normal三种内存块。其内部维护一个队列，用于缓存同种内存大小的内存块。
负责管理从操作系统申请的内存，内部采用伙伴算法以Page为单位进行内存的分配与管理。
负责管理Chunk列表，根据内存使用率，分为：qInit、q000、q025、q050、q075、q100六种。每个PoolChunkList中存储内存使用率相同的Chunk，Chunk以双向链表进行关联，同时不同使用率的PoolChunkList也以双向列表进行关联。这样做的目的是因为随着内存的分配，Chunk使用率会发生变化，以链表形式方便Chunk在不同使用率列表进行移动。
PoolSubpage负责tiny、small类型内存的管理与分配，实现基于SLAB内存分配算法。PoolArena中有两种PoolSubpage类型数组，分别为：tinySubpagePools、smallSubpagePools。tinySubpagePools负责管理tiny类型内存，数组大小为512/16=32种。smallSubpagePools负责管理small类型内存，数组大小为4。
PoolSubpage数组中存储不同内存大小的PoolSubpage节点，相同大小节点以链表进行关联。PoolSubpage内部使用位图数组记录内存分配情况。
Netty通过ByteBufAllocator进行内存分配，ByteBufAllocator有两个实现类：PooledByteBufAllocator与UnpooledByteBufAllocator，其中，是否在堆内存或者直接内存分配与是否使用unsafe进行读写操作都封装在其实现类中。
我们先看下ByteBufAllocator类图：
PooledByteBufAllocator与UnpooledByteBufAllocator内存分配类似，可以通过newHeapBuffer与newDirectBuffer进行分配内存，我们以PooledByteBufAllocator为例分析下内存分配流程：
以PooledByteBufAllocator为例来分析下内存分配器实例化过程。首先调用PooledByteBufAllocator#DEFAULT方法实例化PooledByteBufAllocator
PooledByteBufAllocator实例化时会初始化几个比较重要的属性：
最终会调用PooledByteBufAllocator如下构造方法：
PooledByteBufAllocator构造方法主要做了两件事情，一是：初始化PoolThreadLocalCache属性，二是：初始化堆内存与直接内存类型PoolArena数组，我们进入PoolArena.DirectArena构造方法，来分析下PoolArena初始化时主要做了哪些事情：
DirectArena构造方法会调用其父类PoolArena构造方法，在PoolArena构造方法中会初始化tiny类型与small类型PoolSubpage数组，并初始化六种不同内存使用率的PoolChunkList，每个PoolChunkList以双向链表进行关联。
以分配直接内存为例，分析内存分配的主要流程：
PooledByteBufAllocator#directBuffer方法最终会调用如下构造方法，其中maxCapacity为Integer.MAX_VALUE：
该方法主要分三步，第一步：获取线程缓存，第二步：分配内存，第三步：将ByteBuf转为具有内存泄漏检测功能的ByteBuf，我们来分析下每一步具体做了哪些事情：
1.获取线程缓存，从PoolThreadLocalCache中获取PoolThreadCache，首次调用会先进行进行初始化，并将结果缓存下来：
初始化方法在PoolThreadLocalCache中，首先会循环找到使用最少的PoolArena，然后调用PoolThreadCache构造方法创建PoolThreadCache：
PoolThreadCache构造方法中会初始化tinySubPageDirectCaches、smallSubPageDirectCaches、normalDirectCaches这三种MemoryRegionCache数组：
createSubPageCaches方法中会创建并初始化MemoryRegionCache数组，其中tiny类型数组大小为32，small类型数组大小为4，normal类型数组大小为3：
最终会调用MemoryRegionCache构造方法进行创建，我们看下MemoryRegionCache结构：
2.分配内存，首先会获取PooledByteBuf，然后进行内存分配：
newByteBuf方法会尝试从对象池里面获取pooledByteBuf，如果没有则进行创建。allocate方法为内存分配核心逻辑，主要分为两种分配方式：page级别内存分配（8k 16M）、subPage级别内存分配（0 8K）、huge级别内存分配（>16M）。page与subPage级别内存分配首先会尝试从缓存上进行内存分配，如果分配失败则重新申请内存。huge级别内存分配不会通过缓存进行分配。我们看下allocate方法主要流程：
首先尝试从缓存中进行分配：
cacheForTiney方法先根据分配内存大小定位到对应的tinySubPageDirectCaches数组中MemoryRegionCache，如果没有定位到则不能在缓存中进行分配。如果有则从MemoryRegionCache对应的队列中弹出一个PooledByteBuf对象进行初始化，同时为了复用PooledByteBuf对象，会将其缓存下来。
如果从缓存中分配不成功，则会从对应的PoolSubpage数组上进行分配，如果PoolSubpage数组对应的内存大小下标中有可分配空间则进行分配，并对PooledByteBuf进行初始化。
如果在PoolSubpage数组上分配不成功，则表示没有可以用来分配的SubPage，则会尝试从Page上进行分配。先尝试从不同内存使用率的ChunkList进行分配，如果仍分配不成功，则表示没有可以用来分配的Chunk，此时会创建新的Chunk进行内存分配。
进入PoolChunk#allocate方法看下分配流程：
allocateRun方法用来分配大于等于8K的内存，allocateSubpage用来分配小于8K的内存，进入allocateSubpage方法：
内存分配成功后会调用initBuf方法初始化PoolByteBuf：
Page级别内存分配和SubPage级别类似，同样是先从缓存中进行分配，分配不成功则尝试从不同内存使用率的ChunkList进行分配，如果仍分配不成功，则表示没有可以用来分配的Chunk，此时会创建新的Chunk进行内存分配，不同点在allocate方法中：
因为大于16M的内存分配Netty不会进行缓存，所以Huge级别内存分配会直接申请内存并进行初始化：
调用ByteBuf#release方法会进行内存释放，方法中会判断当前byteBuf 是否被引用，如果没有被引用, 则调用deallocate方法进行释放：
进入deallocate方法看下内存释放流程：
free方法会把释放的内存加入到缓存，如果加入缓存不成功则会标记这段内存为未使用：
recycle方法会将PoolByteBuf对象放入到对象池中：
❸ 使用malloc和free有哪些注意事项
free 不管指针指向多大的空间,均可以正确地进行释放，这一点释放比 delete/delete [] 要方便。不过，必须注意，如果在分配指针时，用的是new或new[]。当在释放内存时，并不能图方便而使用free来释放。反过来，用malloc 分配的内存，也不能用delete/delete[] 来释放。一句话，new/delete、new[]/delete[]、malloc/free 三对均需配套使用，不可混用.
1 分配内存 malloc 函数
需要包含头文件：
and
函数声明(函数原型)
void *malloc(int size);
说明：malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针。
从函数声明上可以看出。malloc 和 new 至少有两个不同: new 返回指定类型的指针，并且可以自动计算所需要大小。比如：
int *p;
p = new int; //返回类型为int* 类型(整数型指针)，分配大小为 sizeof(int);
或：
int* parr;
parr = new int [100]; //返回类型为 int* 类型(整数型指针)，分配大小为 sizeof(int) * 100;
而 malloc 则必须由我们计算要字节数，并且在返回后强行转换为实际类型的指针。
int* p;
p = (int *) malloc (sizeof(int));
第一、malloc 函数返回的是 void * 类型，如果你写成：p = malloc (sizeof(int)); 则程序无法通过编译，报错：“不能将 void* 赋值给 int * 类型变量”。所以必须通过 (int *) 来将强制转换。
第二、函数的实参为 sizeof(int) ，用于指明一个整型数据需要的大小。如果你写成：
int* p = (int *) malloc (1);
代码也能通过编译，但事实上只分配了1个字节大小的内存空间，当你往里头存入一个整数，就会有3个字节无家可归，而直接“住进邻居家”！造成的结果是后面的内存中原有数据内容全部被清空。
malloc 也可以达到 new [] 的效果，申请出一段连续的内存，方法无非是指定你所需要内存大小。
比如想分配100个int类型的空间：
int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100个整数的内存空间。
另外有一点不能直接看出的区别是，malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。
除了分配及最后释放的方法不一样以外，通过malloc或new得到指针，在其它操作上保持一致。
2 释放内存 free 函数
需要包含头文件(和 malloc 一样)：
函数声明：
void free(void *block);
即： void free(指针变量)；
之所以把形参中的指针声明为 void* ，是因为free必须可以释放任意类型的指针，而任意类型的指针都可以转换为void *。
举例：
int* p = (int *) malloc(4);
*p = 100;
free(p); //释放 p 所指的内存空间
或者：
int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100个整数的内存空间。
……
free(p);
❹ C语言编写程序，将一个字符串中的大写字母转换为对应的小写字母，小写字母转换为对应的大写字母，并统计数
在 C 语言中区分字母的大小写，利用 ASCII 码中大写字母和小写字母之间的转换关系（差值为 32），可以将小写字母转换为大写字母。编写程序实现，从键盘上输入一个小写字母，按回车键，程序将该小写字母转换为大写字母，并输出其 ASCII 值。
算法思想
由于大写字母与小写字母之间的差值为 32，因此小写字母转换为大写字母的方法就是将小写字母的 ASCII 码值减去 32，便可得到与之对应的大写字母。
利用 getchar 函数从键盘上输入一个小写字母，并将其赋给一个字符变量 a；然后将 a—32 的值赋给字符变量 b；最后进行输出，输出时先输出字母，再将字母以整数形式输出。其具体步骤如下：
① 定义两个字符变量 a、b；
② a=get char()；
③ b=a—32；
❺ 简述内存管理中buddy算法和slab机制的区别
1、Buddy算法
linux对空闲内存空间管理采取buddy算法，
Buddy算法：
把内存中所有页面按照2^n划分，其中n=0~5，每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成了大小不等的存储块，称为页面块，简称页块，包含一个页面的页块称为1页块，包含2个页面的称为2页块，依次类推。
每种页块按前后顺序两两结合成一对Buddy“伙伴”。系统按照Buddy关系把具有相同大小的空闲页面块组成页块组，即1页块组、2页块组……32页块组。 每个页块组用一个双向循环链表进行管理，共有6个链表，分别为1、2、4、8、16、32页块链表。分别挂到free_area[] 数组上。
位图数组
用于标记内存页面使用情况，第0组每一位表示单个页面使用情况，1表示使用，0表示空闲，第二组每一位表示比邻的两个页面使用情况，一次类推。默认为10个数组，当一对Buddy的两个页面中有一个事空闲的，而另一个全部或部分被占用时，该位置1.两个页面块都是空闲，对应位置0.
内存分配和释放过程
内存分配时，系统按照Buddy算法，根据请求的页面数在free_area[]对应的空闲页块组中搜索。 若请求页面数不是2的整数次幂，则按照稍大于请求数的2的整数次幂的值搜索相应的页面块组。
当相应页块组中没有可使用的空闲页面块时就查询更大一些的页块组，在找到可用的页块后分配所需要的页面。当某一空闲页面被分配后，若仍有剩余的空闲页面，则根据剩余页面的大小把他们加入到相应页面组中。
内存页面释放时，系统将其作为空闲页面看待，检查是否存在与这些页面相邻的其他空闲页块，若存在，则合为一个连续的空闲区按Buddy算法重新分组。
2、Slab算法
采用buddy算法，解决了外碎片问题，这种方法适合大块内存请求，不适合小内存区请求。如：几十个或者几百个字节。Linux2.0采用传统内存分区算法，按几何分布提供内存区大小，内存区以2的幂次方为单位。虽然减少了内碎片，但没有显着提高系统效率。
Linux2.4采用了slab分配器算法，该算法比传统的分配器算法有更好性能和内存利用率，最早在solaris2.4上使用。
Slab分配器思想
1）小对象的申请和释放通过slab分配器来管理。
2）slab分配器有一组高速缓存，每个高速缓存保存同一种对象类型，如i节点缓存、PCB缓存等。
3）内核从它们各自的缓存种分配和释放对象。
4）每种对象的缓存区由一连串slab构成，每个slab由一个或者多个连续的物理页面组成。这些页面种包含了已分配的缓存对象，也包含了空闲对象。
❻ 操作系统第四章【2】内存空间管理---连续
内存分为系统区和用户区两部分：
系统区：仅提供给OS使用，通常放在内存低址部分
用户区：除系统区以外的全部内存空间，提供给用户使用。
最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中。
优点：易于管理。
缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。
把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个分区。操作系统占用其中一个分区。
u提高：支持多个程序并发执行，适用于多道程序系统和分时系统。最早的多道程序存储管理方式。
划分为几个分区，便只允许几道作业并发
1如何划分分区大小：
n分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。缺乏灵活性。
n分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。
2需要的数据结构
建立一记录相关信息的分区表（或分区链表），表项有: 起始位置 大小 状态
分区表中，表项值随着内存的分配和释放而动态改变
3程序分配内存的过程：
也可将分区表分为两个表格：空闲分区表/占用分区表。从而减小每个表格长度。
检索算法：空闲分区表可能按不同分配算法采用不同方式对表项排序(将分区按大小排队或按分区地址高低排序)。
过程：检索空闲分区表；找出一个满足要求且尚未分配的分区，分配给请求程序；若未找到大小足够的分区，则拒绝为该用户程序分配内存。
固定分配的不足：
内碎片（一个分区内的剩余空间）造成浪费
分区总数固定，限制并发执行的程序数目。
（3）动态分区分配
分区的大小不固定：在装入程序时根据进程实际需要，动态分配内存空间，即——需要多少划分多少。
空闲分区表项：从1项到n项：
内存会从初始的一个大分区不断被划分、回收从而形成内存中的多个分区。
动态分区分配
优点：并发进程数没有固定数的限制，不产生内碎片。
缺点：有外碎片（分区间无法利用的空间）
1）数据结构
①空闲分区表：
•记录每个空闲分区的情况。
•每个空闲分区对应一个表目，包括分区序号、分区始址及分区的大小等数据项。
②空闲分区链：
•每个分区的起始部分，设置用于控制分区分配的信息，及用于链接各分区的前向指针；
•分区尾部则设置一后向指针，在分区末尾重复设置状态位和分区大小表目方便检索。
2）分区分配算法
动态分区方式，分区多、大小差异各不相同，此时把一个新作业装入内存，更需选择一个合适的分配算法，从空闲分区表/链中选出一合适分区
①首次适应算法FF
②循环首次适应算法
③最佳适应算法
④最差适应算法
⑤快速适应算法
①首次适应算法FF(first-fit)
1.空闲分区排序：以地址递增的次序链接。
2.检索：分配内存时，从链首开始顺序查找直至找到一个大小能满足要求的空闲分区；
3.分配：从该分区中划出一块作业要求大小的内存空间分配给请求者，余下的空闲分区大小改变仍留在空闲链中。
u若从头到尾检索不到满足要求的分区则分配失败
优点：优先利用内存低址部分，保留了高地址部分的大空闲区；
缺点：但低址部分不断划分，会产生较多小碎片；而且每次查找从低址部分开始，会逐渐增加查找开销。
②循环首次适应算法(next-fit)
1.空闲分区排序：按地址
2.检索：从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。为实现算法，需要：
©设置一个起始查寻指针
©采用循环查找方式
3.分配：分出需要的大小
优点：空闲分区分布均匀，减少查找开销
缺点：缺乏大的空闲分区
③最佳适应算法 (best-fit)
总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。
1.空闲分区排序：所有空闲分区按容量从小到大排序成空闲分区表或链。
2.检索：从表或链的头开始，找到的第一个满足的就分配
3.分配：分出需要的大小
缺点：每次找到最合适大小的分区割下的空闲区也总是最小，会产生许多难以利用的小空闲区（外碎片）
④最差适应算法/最坏匹配法(worst-fit)： 基本不留下小空闲分区，但会出现缺乏较大的空闲分区的情况。
⑤快速适应算法
n根据进程常用空间大小进行划分，相同大小的串成一个链，需管理多个各种不同大小的分区的链表。进程需要时，从最接近大小需求的链中摘一个分区。类似的：伙伴算法
n能快速找到合适分区，但链表信息会很多；实际上是空间换时间。
3）分区分配操作
分配内存
找到满足需要的合适分区，划出进程需要的空间
s<=size，将整个分区分配给请求者
s> size，按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。
回收内存
进程运行完毕释放内存时，系统根据回收区首址a，在空闲分区链(表)中找到相应插入点，根据情况修改空闲分区信息，可能会进行空闲分区的合并：
（4）动态重定位分区分配
——有紧凑功能的动态分区分配
用户程序在内存中移动，将空闲空间紧凑起来提高空间利用率。但必然需要地址变化，增加“重定位”工作。
（5）内存空间管理之对换
当内存空间还是满足不了需求时，引入“对换”思想：
把内存中暂时不能运行、或暂时不用的程序和数据调到外存上，以腾出足够的内存；把已具备运行条件的进程和进程所需要的程序和数据，调入内存。
u按对换单位分类：
Ø整体对换(或进程对换)：以整个进程为单位（连续分配）
Ø页面对换或分段对换：以页或段为单位（离散分配）
❼ 【我的笔记】内存管理（二）分区方法（静态、动态、伙伴、Slab）
由操作系统或系统管理员预先将内存划分成若干个分区。在系统运行过程中，分区的边界不再改变。分配时，找一个空闲且足够大的分区。如没有合适的分区：①让申请者等待。②先换出某分区的内容，再将其分配出去。
为申请者分配指定的分区或任选一个分区。如果没有空闲分区，可将一个分区的内容换出。可能需要重定位。
会出现内部碎片，无法满足大内存的需求。
可减少内部碎片。减少对大内存需求的限制。
①固定分配：只分配某种尺寸的特定分区，如分区已被使用，申请者必须等待。
可能出现不公平等待：虽有更大尺寸的空闲分区，却必须等待。
②最佳适应分配：分配能满足需要的最小尺寸的空闲分区，只有当所有分区都已用完时，申请者才需要等待。灵活，但可能产生较大的内部碎片。
3、静态分区：内存利用率低，产生内部碎片；尺寸和分区数量难以确定。
1、不预先确定分区的大小和数量，将分区工作推迟到实际分配内存时进行。 Lazy
初始情况下，把所有的空闲内存看成一个大分区。分配时，按申请的尺寸，找一块足够大的空闲内存分区，临时从中划出一块构成新分区。新分区的尺寸与申请的大小相等，不会出现内部碎片。回收时，尽可能与邻近的空闲分区合并。在内存紧缺时，可将某个选定的分区换出。
2、会产生外部碎片，如下图（内部碎片是指 eg：要 1M，分了 8M，产生 7M 的碎片）：
移动内存中的进程，将碎片集中起来，重新构成大的内存块。需要运行时的动态重定位，费时。
（1）紧缩方向：向一头紧缩，向两头紧缩。
（2）紧缩时机：①在释放分区时，如果不能与空闲分区合并，则立刻进行紧缩。
好处是不存在外部碎片，坏处是费时。
②在内存分配时，如果剩余的空闲空间总量能满足要求但没有一个独立的空闲块能满足要求，则进行紧缩。
好处是减少紧缩次数。Lazy。
①最先适应算法（First fit）：从头开始，在满足要求的第一个空闲块中分配。
分区集中在内存的前部，大内存留在后面，便于释放后的合并。
②最佳适应算法（Best fit）：遍历空闲块，在满足要求的最小空闲块中分配。
留下的碎片最小，基本无法再用，需要更频繁地紧缩。
③下一个适应算法（Next fit）：从上次分配的位置开始，在满足要求的下一个空闲块中分配。
对内存的使用较平均，不容易留下大的空闲块。
④最差适应算法（Worst Fit）：遍历空闲块，在满足要求的最大空闲块中分配。
留下的碎片较大，但不会剩余大内存。
最先适应算法较优，最佳适应算法较差。
伙伴算法：将动态分区的大小限定为 2^k 字节，分割方式限定为平分，分区就会变得较为规整，分割与合并会更容易，可以减少一些外部碎片。平分后的两块互称伙伴。
1、
分配时可能要多次平分，释放时可能要多次合并。举例：
记录大小不同的空闲页：
示意图：
2、
伙伴算法是静态分区和动态分区法的折中，比静态分区法灵活，不受分区尺寸及个数的限制；比动态分区法规范，不易出现外部碎片。会产生内部碎片，但比静态分区的小。
Linux、Windows、Ucore等都采用伙伴算法管理物理内存。
一般情况下，将最小尺寸定为 2^12 字节（1页，4K=4096B），最大尺寸定为1024页，11个队列。
Linux、Windows、Ucore 等都将伙伴的最小尺寸限定为1页。
ucore 用 page，在内存初始化函数 page_init 中为系统中的每个物理页建立一个 page 结构。
页块（pageblock）是一组连续的物理页。
5、
（1）判断伙伴关系/寻找伙伴
最后两行是指，B1和B2只有第i位相反。
（2）判断伙伴是否空闲：
ucore 用 free_area[ ]数组定义空闲页块队列。
（3）确定伙伴是否在 order 队列中：
7、
（1）解决内部碎片过大问题（eg：申请5页，分配8页，浪费3页）：
ucore 在前部留下需要的页数，释放掉尾部各页。每次释放1页，先划分成页块，再逐个释放。
（2） 解决切分与合并过于频繁的问题：
用得较多的是单个页。位于处理器Cache中页称为热页（hot page），其余页称为冷页（cold page）。处理器对热页的访问速度要快于冷页。
可建一个热页队列（per_cpu_page），暂存刚释放的单个物理页，将合并工作向后推迟 Lazy。总是试图从热页队列中分配单个物理页。分配与释放都在热页队列的队头进行。
（3）解决内存碎化(有足够多的空闲页，但是没有大页块)问题：①将页块从一个物理位置移动到另一个物理位置，并保持移动前后逻辑地址不变（拷贝页块内容）；②逻辑内存管理器。
（4）满足大内存的需求：
（5）物理内存空间都耗尽的情况：
在任何情况下，都应该预留一部分空闲的物理内存以备急需。定义两条基准线low和high，当空闲内存量小于low时，应立刻开始回收物理内存，直到空闲内存量大于high。
（6）回收物理内存：
法一：启动一个守护进程，专门用于回收物理内存。周期性启动，也可被唤醒。
法二：申请者自己去回收内存。实际是由内存分配程序回收。回收的方法很多，如释放缓冲区、页面淘汰等。
1、
伙伴算法最小分配内存为页，对于更小的内存的管理 --> Slab 算法
内和运行过程中经常使用小内存（小于1页）eg：建立数据结构、缓冲区
内核对小内存的使用极为频繁、种类繁多、时机和数量难以预估。所以难以预先分配，只能动态地创建和撤销
2、
Slab 向伙伴算法申请大页块（批发），将其划分成小对象分配出去（零售）；将回收的小对象组合成大页块后还给伙伴算法。
Slab 采用等尺寸静态分区法，将页块预先划分成一组大小相等的小块，称为内存对象。
具有相同属性的多个Slab构成一个Cache，一个Cache管理一种类型（一类应该是指一个大小）的内存对象。当需要小内存时，从预建的Cache中申请内存对象，用完之后再将其还给Cache。当Cache中缺少对象时，追加新的Slab；当物理内存紧缺时，回收完全空闲的Slab。
Slab 算法的管理结构：
① Cache 管理结构：管理Slab，包括Slab的创建和销毁。
② Slab 管理结构：管理内存对象，包括小对象的分配与释放。
（Cache结构和Slab结构合作，共同实现内存对象的管理）
3、
（1）描述各个内存对象的使用情况
可以用位图标识空闲的内存对象。也可以将一个Slab中的空闲内存对象组织成队列，并在slab结构中记录队列的队头。
早期的Linux在每个内存对象的尾部都加入一个指针，用该指针将空闲的内存对象串联成一个真正的队列。（对象变长、不规范，空间浪费）
改进：将指针集中在一个数组中，用数组内部的链表模拟内存对象队列。
再改进：将数组中的指针换成对象序号，利用序号将空闲的内存对象串成队列。序号数组是动态创建的。
序号数组可以位于 Slab 内部，也可以位于 Slab 外部
（2）一个Cache会管理多个Slab，可以将所有Slab放在一个队列中。
Ucore为每个Cache准备了两个slab结构队列：全满的和不满的。Linux为每个Cache准备了三个slab结构队列：部分满的、完全满的和完全空闲的。
Linux允许动态创建Cache，Ucore不许。Ucore预定了对象大小，分别是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。为每一种大小的对象预建了Cache。
（3）Slab是动态创建的，当Cache中没有空闲的内存对象时，即为其创建一个新的Slab。
Slab所需要的内存来自伙伴算法，大小是 2^page_order 个连续页。
4、小对象的尺寸
如按处理器一级缓存中缓存行（Cache Line）的大小（16、32字节）取齐，可使对象的开始位置都位于缓存行的边界处。
在将页块划分成内存对象的过程中，通常会剩余一小部分空间，位于所有内存对象之外，称为外部碎片。
Slab算法选用碎片最小的实现方案。
5、
（1）对象分配 kmalloc
① 根据size确定一个Cache。
② 如果Cache的slabs_notfull为空，则为其创建一个新的Slab。
③ 选中slabs_notfull中第一个Slab，将队头的小对象分配出去，并调整队列。
④ 对象的开始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;
（2）对象释放 kfree
① 算出对象所在的页号，找到它的 Page 结构。
② 根据 Page 找到所属的 Cache 和 Slab。
③ 算出对象序号：objnr = (objp - slabp->s_mem) / cachep->objsize;
④将序号插入Slab的free队列。
⑤整Slab所属队列。
❽ linux中使用了什么内存管理方法,为什么
“事实胜于雄辩”，我们用一个小例子（原形取自《User-Level Memory Management》）来展示上面所讲的各种内存区的差别与位置。
进程的地址空间对应的描述结构是“内存描述符结构”,它表示进程的全部地址空间，——包含了和进程地址空间有关的全部信息，其中当然包含进程的内存区域。
进程内存的分配与回收
创建进程fork()、程序载入execve()、映射文件mmap()、动态内存分配malloc()/brk()等进程相关操作都需要分配内存给进程。不过这时进程申请和获得的还不是实际内存，而是虚拟内存，准确的说是“内存区域”。进程对内存区域的分配最终都会归结到do_mmap（）函数上来（brk调用被单独以系统调用实现，不用do_mmap()），
内核使用do_mmap()函数创建一个新的线性地址区间。但是说该函数创建了一个新VMA并不非常准确，因为如果创建的地址区间和一个已经存在的地址区间相邻，并且它们具有相同的访问权限的话，那么两个区间将合并为一个。如果不能合并，那么就确实需要创建一个新的VMA了。但无论哪种情况，do_mmap()函数都会将一个地址区间加入到进程的地址空间中－－无论是扩展已存在的内存区域还是创建一个新的区域。
同样，释放一个内存区域应使用函数do_ummap()，它会销毁对应的内存区域。
如何由虚变实！
从上面已经看到进程所能直接操作的地址都为虚拟地址。当进程需要内存时，从内核获得的仅仅是虚拟的内存区域，而不是实际的物理地址，进程并没有获得物理内存（物理页面——页的概念请大家参考硬件基础一章），获得的仅仅是对一个新的线性地址区间的使用权。实际的物理内存只有当进程真的去访问新获取的虚拟地址时，才会由“请求页机制”产生“缺页”异常，从而进入分配实际页面的例程。
该异常是虚拟内存机制赖以存在的基本保证——它会告诉内核去真正为进程分配物理页，并建立对应的页表，这之后虚拟地址才实实在在地映射到了系统的物理内存上。（当然，如果页被换出到磁盘，也会产生缺页异常，不过这时不用再建立页表了）
这种请求页机制把页面的分配推迟到不能再推迟为止，并不急于把所有的事情都一次做完（这种思想有点像设计模式中的代理模式（proxy））。之所以能这么做是利用了内存访问的“局部性原理”，请求页带来的好处是节约了空闲内存，提高了系统的吞吐率。要想更清楚地了解请求页机制，可以看看《深入理解linux内核》一书。
这里我们需要说明在内存区域结构上的nopage操作。当访问的进程虚拟内存并未真正分配页面时，该操作便被调用来分配实际的物理页，并为该页建立页表项。在最后的例子中我们会演示如何使用该方法。
系统物理内存管理
虽然应用程序操作的对象是映射到物理内存之上的虚拟内存，但是处理器直接操作的却是物理内存。所以当应用程序访问一个虚拟地址时，首先必须将虚拟地址转化成物理地址，然后处理器才能解析地址访问请求。地址的转换工作需要通过查询页表才能完成，概括地讲，地址转换需要将虚拟地址分段，使每段虚地址都作为一个索引指向页表，而页表项则指向下一级别的页表或者指向最终的物理页面。
每个进程都有自己的页表。进程描述符的pgd域指向的就是进程的页全局目录。下面我们借用《linux设备驱动程序》中的一幅图大致看看进程地址空间到物理页之间的转换关系。
上面的过程说起来简单，做起来难呀。因为在虚拟地址映射到页之前必须先分配物理页——也就是说必须先从内核中获取空闲页，并建立页表。下面我们介绍一下内核管理物理内存的机制。
物理内存管理（页管理）
Linux内核管理物理内存是通过分页机制实现的，它将整个内存划分成无数个4k（在i386体系结构中）大小的页，从而分配和回收内存的基本单位便是内存页了。利用分页管理有助于灵活分配内存地址，因为分配时不必要求必须有大块的连续内存[3]，系统可以东一页、西一页的凑出所需要的内存供进程使用。虽然如此，但是实际上系统使用内存时还是倾向于分配连续的内存块，因为分配连续内存时，页表不需要更改，因此能降低TLB的刷新率（频繁刷新会在很大程度上降低访问速度）。
鉴于上述需求，内核分配物理页面时为了尽量减少不连续情况，采用了“伙伴”关系来管理空闲页面。伙伴关系分配算法大家应该不陌生——几乎所有操作系统方面的书都会提到,我们不去详细说它了，如果不明白可以参看有关资料。这里只需要大家明白Linux中空闲页面的组织和管理利用了伙伴关系，因此空闲页面分配时也需要遵循伙伴关系，最小单位只能是2的幂倍页面大小。内核中分配空闲页面的基本函数是get_free_page/get_free_pages，它们或是分配单页或是分配指定的页面（2、4、8…512页）。
注意：get_free_page是在内核中分配内存，不同于malloc在用户空间中分配，malloc利用堆动态分配，实际上是调用brk()系统调用，该调用的作用是扩大或缩小进程堆空间（它会修改进程的brk域）。如果现有的内存区域不够容纳堆空间，则会以页面大小的倍数为单位，扩张或收缩对应的内存区域，但brk值并非以页面大小为倍数修改，而是按实际请求修改。因此Malloc在用户空间分配内存可以以字节为单位分配,但内核在内部仍然会是以页为单位分配的。
另外,需要提及的是，物理页在系统中由页结构structpage描述，系统中所有的页面都存储在数组mem_map[]中，可以通过该数组找到系统中的每一页（空闲或非空闲）。而其中的空闲页面则可由上述提到的以伙伴关系组织的空闲页链表（free_area[MAX_ORDER]）来索引。
内核内存使用
Slab
所谓尺有所长，寸有所短。以页为最小单位分配内存对于内核管理系统中的物理内存来说的确比较方便，但内核自身最常使用的内存却往往是很小（远远小于一页）的内存块——比如存放文件描述符、进程描述符、虚拟内存区域描述符等行为所需的内存都不足一页。这些用来存放描述符的内存相比页面而言，就好比是面包屑与面包。一个整页中可以聚集多个这些小块内存；而且这些小块内存块也和面包屑一样频繁地生成/销毁。
为了满足内核对这种小内存块的需要，Linux系统采用了一种被称为slab分配器的技术。Slab分配器的实现相当复杂，但原理不难，其核心思想就是“存储池[4]”的运用。内存片段（小块内存）被看作对象，当被使用完后，并不直接释放而是被缓存到“存储池”里，留做下次使用，这无疑避免了频繁创建与销毁对象所带来的额外负载。
Slab技术不但避免了内存内部分片（下文将解释）带来的不便（引入Slab分配器的主要目的是为了减少对伙伴系统分配算法的调用次数——频繁分配和回收必然会导致内存碎片——难以找到大块连续的可用内存），而且可以很好地利用硬件缓存提高访问速度。
Slab并非是脱离伙伴关系而独立存在的一种内存分配方式，slab仍然是建立在页面基础之上，换句话说，Slab将页面（来自于伙伴关系管理的空闲页面链表）撕碎成众多小内存块以供分配，slab中的对象分配和销毁使用kmem_cache_alloc与kmem_cache_free。
Kmalloc
Slab分配器不仅仅只用来存放内核专用的结构体，它还被用来处理内核对小块内存的请求。当然鉴于Slab分配器的特点，一般来说内核程序中对小于一页的小块内存的请求才通过Slab分配器提供的接口Kmalloc来完成（虽然它可分配32到131072字节的内存）。从内核内存分配的角度来讲，kmalloc可被看成是get_free_page（s）的一个有效补充，内存分配粒度更灵活了。
有兴趣的话，可以到/proc/slabinfo中找到内核执行现场使用的各种slab信息统计，其中你会看到系统中所有slab的使用信息。从信息中可以看到系统中除了专用结构体使用的slab外，还存在大量为Kmalloc而准备的Slab（其中有些为dma准备的）。
内核非连续内存分配（Vmalloc）
伙伴关系也好、slab技术也好，从内存管理理论角度而言目的基本是一致的，它们都是为了防止“分片”，不过分片又分为外部分片和内部分片之说，所谓内部分片是说系统为了满足一小段内存区（连续）的需要，不得不分配了一大区域连续内存给它，从而造成了空间浪费；外部分片是指系统虽有足够的内存，但却是分散的碎片，无法满足对大块“连续内存”的需求。无论何种分片都是系统有效利用内存的障碍。slab分配器使得一个页面内包含的众多小块内存可独立被分配使用，避免了内部分片，节约了空闲内存。伙伴关系把内存块按大小分组管理，一定程度上减轻了外部分片的危害，因为页框分配不在盲目，而是按照大小依次有序进行，不过伙伴关系只是减轻了外部分片，但并未彻底消除。你自己比划一下多次分配页面后，空闲内存的剩余情况吧。
所以避免外部分片的最终思路还是落到了如何利用不连续的内存块组合成“看起来很大的内存块”——这里的情况很类似于用户空间分配虚拟内存，内存逻辑上连续，其实映射到并不一定连续的物理内存上。Linux内核借用了这个技术，允许内核程序在内核地址空间中分配虚拟地址，同样也利用页表（内核页表）将虚拟地址映射到分散的内存页上。以此完美地解决了内核内存使用中的外部分片问题。内核提供vmalloc函数分配内核虚拟内存，该函数不同于kmalloc，它可以分配较Kmalloc大得多的内存空间（可远大于128K，但必须是页大小的倍数），但相比Kmalloc来说,Vmalloc需要对内核虚拟地址进行重映射，必须更新内核页表，因此分配效率上要低一些（用空间换时间）
与用户进程相似,内核也有一个名为init_mm的mm_strcut结构来描述内核地址空间，其中页表项pdg=swapper_pg_dir包含了系统内核空间（3G-4G）的映射关系。因此vmalloc分配内核虚拟地址必须更新内核页表，而kmalloc或get_free_page由于分配的连续内存，所以不需要更新内核页表。
vmalloc分配的内核虚拟内存与kmalloc/get_free_page分配的内核虚拟内存位于不同的区间，不会重叠。因为内核虚拟空间被分区管理，各司其职。进程空间地址分布从0到3G(其实是到PAGE_OFFSET,在0x86中它等于0xC0000000)，从3G到vmalloc_start这段地址是物理内存映射区域（该区域中包含了内核镜像、物理页面表mem_map等等）比如我使用的系统内存是64M(可以用free看到)，那么(3G——3G+64M)这片内存就应该映射到物理内存，而vmalloc_start位置应在3G+64M附近（说"附近"因为是在物理内存映射区与vmalloc_start期间还会存在一个8M大小的gap来防止跃界）,vmalloc_end的位置接近4G(说"接近"是因为最后位置系统会保留一片128k大小的区域用于专用页面映射，还有可能会有高端内存映射区，这些都是细节，这里我们不做纠缠)。
上图是内存分布的模糊轮廓
由get_free_page或Kmalloc函数所分配的连续内存都陷于物理映射区域，所以它们返回的内核虚拟地址和实际物理地址仅仅是相差一个偏移量（PAGE_OFFSET），你可以很方便的将其转化为物理内存地址，同时内核也提供了virt_to_phys（）函数将内核虚拟空间中的物理映射区地址转化为物理地址。要知道，物理内存映射区中的地址与内核页表是有序对应的，系统中的每个物理页面都可以找到它对应的内核虚拟地址（在物理内存映射区中的）。
而vmalloc分配的地址则限于vmalloc_start与vmalloc_end之间。每一块vmalloc分配的内核虚拟内存都对应一个vm_struct结构体（可别和vm_area_struct搞混，那可是进程虚拟内存区域的结构），不同的内核虚拟地址被4k大小的空闲区间隔，以防止越界——见下图）。与进程虚拟地址的特性一样，这些虚拟地址与物理内存没有简单的位移关系，必须通过内核页表才可转换为物理地址或物理页。它们有可能尚未被映射，在发生缺页时才真正分配物理页面。
这里给出一个小程序帮助大家认清上面几种分配函数所对应的区域。
#include<linux/mole.h>
#include<linux/slab.h>
#include<linux/vmalloc.h>
unsignedchar*pagemem;
unsignedchar*kmallocmem;
unsignedchar*vmallocmem;
intinit_mole(void)
{
pagemem = get_free_page(0);
printk("<1>pagemem=%s",pagemem);
kmallocmem = kmalloc(100,0);
printk("<1>kmallocmem=%s",kmallocmem);
vmallocmem = vmalloc(1000000);
printk("<1>vmallocmem=%s",vmallocmem);
}
voidcleanup_mole(void)
{
free_page(pagemem);
kfree(kmallocmem);
vfree(vmallocmem);
}
实例
内存映射(mmap)是Linux操作系统的一个很大特色，它可以将系统内存映射到一个文件（设备）上，以便可以通过访问文件内容来达到访问内存的目的。这样做的最大好处是提高了内存访问速度，并且可以利用文件系统的接口编程（设备在Linux中作为特殊文件处理）访问内存，降低了开发难度。许多设备驱动程序便是利用内存映射功能将用户空间的一段地址关联到设备内存上，无论何时，只要内存在分配的地址范围内进行读写，实际上就是对设备内存的访问。同时对设备文件的访问也等同于对内存区域的访问，也就是说，通过文件操作接口可以访问内存。Linux中的X服务器就是一个利用内存映射达到直接高速访问视频卡内存的例子。
熟悉文件操作的朋友一定会知道file_operations结构中有mmap方法，在用户执行mmap系统调用时，便会调用该方法来通过文件访问内存——不过在调用文件系统mmap方法前，内核还需要处理分配内存区域（vma_struct）、建立页表等工作。对于具体映射细节不作介绍了，需要强调的是,建立页表可以采用remap_page_range方法一次建立起所有映射区的页表，或利用vma_struct的nopage方法在缺页时现场一页一页的建立页表。第一种方法相比第二种方法简单方便、速度快，但是灵活性不高。一次调用所有页表便定型了，不适用于那些需要现场建立页表的场合——比如映射区需要扩展或下面我们例子中的情况。
我们这里的实例希望利用内存映射，将系统内核中的一部分虚拟内存映射到用户空间，以供应用程序读取——你可利用它进行内核空间到用户空间的大规模信息传输。因此我们将试图写一个虚拟字符设备驱动程序，通过它将系统内核空间映射到用户空间——将内核虚拟内存映射到用户虚拟地址。从上一节已经看到Linux内核空间中包含两种虚拟地址：一种是物理和逻辑都连续的物理内存映射虚拟地址；另一种是逻辑连续但非物理连续的vmalloc分配的内存虚拟地址。我们的例子程序将演示把vmalloc分配的内核虚拟地址映射到用户地址空间的全过程。
程序里主要应解决两个问题：
第一是如何将vmalloc分配的内核虚拟内存正确地转化成物理地址？
因为内存映射先要获得被映射的物理地址，然后才能将其映射到要求的用户虚拟地址上。我们已经看到内核物理内存映射区域中的地址可以被内核函数virt_to_phys转换成实际的物理内存地址，但对于vmalloc分配的内核虚拟地址无法直接转化成物理地址，所以我们必须对这部分虚拟内存格外“照顾”——先将其转化成内核物理内存映射区域中的地址，然后在用virt_to_phys变为物理地址。
转化工作需要进行如下步骤：
找到vmalloc虚拟内存对应的页表，并寻找到对应的页表项。
获取页表项对应的页面指针
通过页面得到对应的内核物理内存映射区域地址。
如下图所示：
第二是当访问vmalloc分配区时，如果发现虚拟内存尚未被映射到物理页，则需要处理“缺页异常”。因此需要我们实现内存区域中的nopaga操作，以能返回被映射的物理页面指针，在我们的实例中就是返回上面过程中的内核物理内存映射区域中的地址。由于vmalloc分配的虚拟地址与物理地址的对应关系并非分配时就可确定，必须在缺页现场建立页表，因此这里不能使用remap_page_range方法，只能用vma的nopage方法一页一页的建立。
程序组成
map_driver.c，它是以模块形式加载的虚拟字符驱动程序。该驱动负责将一定长的内核虚拟地址(vmalloc分配的)映射到设备文件上。其中主要的函数有——vaddress_to_kaddress（）负责对vmalloc分配的地址进行页表解析,以找到对应的内核物理映射地址（kmalloc分配的地址）；map_nopage()负责在进程访问一个当前并不存在的VMA页时，寻找该地址对应的物理页，并返回该页的指针。
test.c它利用上述驱动模块对应的设备文件在用户空间读取读取内核内存。结果可以看到内核虚拟地址的内容（ok!），被显示在了屏幕上。
执行步骤
编译map_driver.c为map_driver.o模块,具体参数见Makefile
加载模块：insmodmap_driver.o
生成对应的设备文件
1在/proc/devices下找到map_driver对应的设备命和设备号：grepmapdrv/proc/devices
2建立设备文件mknodmapfilec 254 0（在我的系统里设备号为254）
利用maptest读取mapfile文件，将取自内核的信息打印到屏幕上。