A. 【我的笔记】内存管理（二）分区方法（静态、动态、伙伴、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所属队列。
这是我在一个论坛里看到的，你也参考参考吧。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的算法启动数据发送。
一次发送可能是你提交数据的一部分，一定要当心，否则出问题没处找去。
C. 伙伴算法和slab算法
内存碎片太小和管理内存碎片的效率问题
原因：分配内存时，不能将相邻内存合并
解决办法：
如果申请的内存大小为n，则向上取整为2的幂次数，定位到响应组，到组中(链表上)找空闲块分配出去；若没有空闲块，则到上一组找，直到找到为止，并将剩余的内存放到下面适当的组中。
用完内存需要归还，根据实际内存块大小向上取整为2的幂次数，归入链表。
注：伙伴算法使用位图标记内存块的使用情况
slab以内存池为思想，解决内部碎片问题，专门解决小内存问题。
D. 外碎片与内碎片
内部碎片
是处于操作系统分配的用于装载某一进程的内存区域内部的存储块。占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。
外部碎片
外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
外部碎片是处于任何两个已分配区域或页面之间的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。
内部碎片的产生 ：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。
外部碎片的产生 ： 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是0 99。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为0 9区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为10 14区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0 9空闲，10 14被占用，15 24被占用，25 99空闲。其中0 9就是一个内存碎片了。如果10 14一直被占用，而以后申请的空间都大于10个单位，那么0 9就永远用不上了，变成外部碎片。
伙伴算法(buddy)用来解决外碎片
slab算法用来解决内碎片
E. 操作系统第四章【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按对换单位分类：
Ø整体对换(或进程对换)：以整个进程为单位（连续分配）
Ø页面对换或分段对换：以页或段为单位（离散分配）