一、内存页面置换算法
当内存中没有空闲页面，而又有程序和数据需要从外存中装入内存运行时，就需要从内存中选出一个或者多个页面淘汰出去，以便新的程序和数据装入运行，置换算法有以下这些：
1、随机淘汰算法。无法确认哪些页面被访问的概率较低时，随机的选择某个页面将其换出。
2、轮转算法。按照内存页面的编号，循环的换出内存中一个可以被换出的页面，无论该页面是刚换进来的还是已经驻留页面很久的。
3、先进新出（First In First Out）。FIFO算法总是选择在内存驻留时间最长的一页将其淘汰，它忽略了一种现象，那就是在内存停留时间最长的页往往也是经常要访问的页面。将这些页面淘汰，很可能刚置换出去，有请求调用该页，致使缺页中断台频繁，严重降低内存的利用率。FIFO算法的另一个缺点是它可能会产生一种异常的现象：一般来说，对于任一作业或者进程，如果给它分配的内存页数越是接近它所要求的页面数，则发生缺页的次数会减少。但是使用FIFO算法时，有时会出现分配的页数增多，缺页次数反而增加的现象，称为belady现象。
看个例题：考虑一个仅460个字节的程序的内存访问序列（10,11,104,170,73,309,185,245,246,434,458,364），页面的大小为100个字节，则460个字节应该占5页，编号为0到4，第0页的字节为0到99，第二页为100到199，第三页为200到299，第四页为300到399，第5页为400到460。因此页面（10,11,104,170,73,309,185,245,246,434,458,364）这些程序在内存中的页数为（0,0,1,1,0,3,1,2,2,4,4,3），可简化为0,1,0,3,1,2,4,3）。如果内存中有200个字节可供使用，则200个字节可以提供2个页帧供使用。按照FIFO算法，结合下图我们演示一些FIFO算法的淘汰过程。
缺页说明1：此时内存是空的，要载入程序的0号页进入内存的第0页，肯定会易产生缺页中断。
缺页说明2：此时内存第0页已经载入了程序0号页，内存第1页还是空的，会易产生缺页中断，要载入程序1号页。
不缺页说明a：此时内存第0页已经载入了程序0号页，内存第1页载入了程序1号页。由于程序0号页面已经在内存中，再次载入内存不需要淘汰页面，没有产生缺页中断。
缺页说明3：此时内存第0页已经载入了程序0号页，内存第1页载入了程序1号页。程序3号页要载入内存，就需要淘汰一个页面，0号和1号，淘汰哪一个？由于FIFO算法总是选择在内存驻留时间最长的一页将其淘汰，程序0号页比程序1号页早载入内存，驻留内存更久，那么就该淘汰0号页，把程序0号的位置让出来给程序3号页。
不缺页说明b：此时内存第0页已经载入了程序3号页，内存第1页载入了程序1号页。由于程序1号页面已经在内存中，再次载入内存不需要淘汰页面，没有产生缺页中断。
缺页说明4：此时内存第0页已经载入了程序3号页，内存第1页载入了程序1号页。程序2号页要载入内存，就需要淘汰一个页面，3号和1号，淘汰哪一个？由于FIFO算法总是选择在内存驻留时间最长的一页将其淘汰，程序1号页比程序3号页早载入内存，驻留内存更久，那么就该淘汰1号页，把程序1号的位置让出来给程序2号页。
缺页说明5：此时内存第0页已经载入了程序3号页，内存第1页载入了程序2号页。程序4号页要载入内存，就需要淘汰一个页面，3号和2号，淘汰哪一个？由于FIFO算法总是选择在内存驻留时间最长的一页将其淘汰，程序3号页比程序2号页早载入内存，驻留内存更久，那么就该淘汰3号页，把程序3号的位置让出来给程序4号页。
缺页说明6：此时内存第0页已经载入了程序4号页，内存第1页载入了程序2号页。程序3号页要载入内存，就需要淘汰一个页面，4号和2号，淘汰哪一个？由于FIFO算法总是选择在内存驻留时间最长的一页将其淘汰，程序2号页比程序4号页早载入内存，驻留内存更久，那么就该淘汰2号页，把程序2号的位置让出来给程序3号页。
共计产生6次缺页中断。
4、最近最久未使用算法（Least Recently Used LUR）。当需要淘汰某一页时，选择离当前最近时间最久没有使用的页先淘汰。依然是上面例子里面的程序页面，用LUR算法来推演一遍。
缺页说明1：此时内存是空的，要载入程序的0号页进入内存的第0页，肯定会易产生缺页中断。
缺页说明2：此时内存第0页已经载入了程序0号页，内存第1页还是空的，会易产生缺页中断，要载入程序1号页。
不缺页说明a：此时内存第0页已经载入了程序0号页，内存第1页载入了程序1号页。由于程序0号页面已经在内存中，再次载入内存不需要淘汰页面，没有产生缺页中断。
缺页说明3：此时内存第0页已经载入了程序0号页，内存第1页载入了程序1号页。程序3号页要载入内存，就需要淘汰一个页面，0号和1号，淘汰哪一个？由于LUR算法选择离当前最近时间最久没有使用的页先淘汰，上此次载入的是程序0号页，刚刚用过，那么程序1号页没有使用的时间更久一些，就应该淘汰程序1号页，把程序1号的位置让出来给程序3号页。
缺页说明4：此时内存第0页已经载入了程序0号页，内存第1页载入了程序3号页。程序1号页要载入内存，就需要淘汰一个页面，0号和3号，淘汰哪一个？由于LUR算法选择离当前最近时间最久没有使用的页先淘汰，上此次载入的是程序3号页，刚刚用过，那么程序0号页没有使用的时间更久一些，就应该淘汰程序0号页，把程序0号的位置让出来给程序1号页。
缺页说明5：此时内存第0页已经载入了程序1号页，内存第1页载入了程序3号页。程序2号页要载入内存，就需要淘汰一个页面，1号和3号，淘汰哪一个？由于LUR算法选择离当前最近时间最久没有使用的页先淘汰，上此次载入的是程序1号页，刚刚用过，那么程序3号页没有使用的时间更久一些，就应该淘汰程序3号页，把程序3号的位置让出来给程序2号页。
缺页说明6：此时内存第0页已经载入了程序1号页，内存第1页载入了程序2号页。程序4号页要载入内存，就需要淘汰一个页面，1号和2号，淘汰哪一个？由于LUR算法选择离当前最近时间最久没有使用的页先淘汰，上此次载入的是程序2号页，刚刚用过，那么程序1号页没有使用的时间更久一些，就应该淘汰程序1号页，把程序1号的位置让出来给程序4号页。
缺页说明7：此时内存第0页已经载入了程序4号页，内存第1页载入了程序2号页。程序3号页要载入内存，就需要淘汰一个页面，4号和2号，淘汰哪一个？由于LUR算法选择离当前最近时间最久没有使用的页先淘汰，上此次载入的是程序4号页，刚刚用过，那么程序2号页没有使用的时间更久一些，就应该淘汰程序2号页，把程序2号的位置让出来给程序3号页。
共计产生7次缺页中断。
5、最近没有使用页面置换算法（No Used Recently NUR）。在需要置换某一页时，从那些最近的一个时期内未被访问的页任选一页置换。
6、最优置换算法。选择那些永久不使用，或者最长时间不被访问的页面置换出去。因为要确定哪个页面时未来最长时间内不被访问的，目前来说很难估计，所以，改算法统筹用来评价其它算法。
7、时钟页面替换算法（Clock）。使用页表中的引用位，将作业已调入内存的页面链成循环队列，用一个指针指向循环队列中的下一个将被替换的页面。
二、Cache替换算法
当Cache产生了一次未命中之后，相应的数据应同时读入CPU和Cache，但是Cache数据已满，新数据必须替换（淘汰）Cache中的某些旧数据，最常见的替换算法有三种：随机算法、先进新出（First In First Out FIFO）算法、最近最久未使用算法（Least Recently Used LUR）。思想和上面讲述的内存页面置换算法相同，补充说明一些：FIFO要求为每块做一记录，记下它们进入cache的先后顺序，这种方法容易实现，而且系统开销小，缺点是可能会把一些需要经常使用的程序块替换出去。LUR算法相对合理，但是实现起来比较负责，系统开销大，通常需要对每一块设置一个称为“年龄计数器”的硬件或者软件计数器，以记录其被使用的情况。
