连续分配方式会形成许多“碎片”，如果允许一个进程直接分散地装入到许多不相邻接的分区中，便可充分地利用内存空间。所以产生了离散的分配方式，根据离散时分配地址空间的基本单位不同，可分为三种，这里我们只讲解分页存储管理。
1. 页面和物理块
（1）页面。分页存储管理将进程的逻辑地址空间分成若干个页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存的物理地址空间分成若干个块，同样也为他们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个不相邻的物理块中。由于进程的最后一页经常装不满一块，而形成了不可利用的碎片，称为“页内碎片”。
（2） 页面大小。在分页系统中，若选择过小的页面大小，虽然一方面可以减小内存碎片，起到减少内存碎片总空间的作用，有利于内存利用率的提高，但另一个方面却会造成每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存。此外，还会降低页面换进换出的效率。然而，如果选择的页面过大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应是2的幂，通常为1KB~8KB。
2.地址结构
分页地址中的地址结构如下：
它包含两个部分内容，前一部分为页号P，后一部分为位（偏）移量W，即页内地址。图中的地址长度为32位，其中0~11位为页内地址，即每页大小为4KB，12~31位为页号，地址空间最多允许有1M页。
对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：
P = INT[ A/L] , d = [A] MOD L
其中，INT是整除函数，MOD是取余函数。例如，其系统的页面大小为1KB，设A = 2170B，则由上式可以求得P = 2，d = 122。
3. 页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程依然能够正确运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内所有页（0~n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号，见下图，在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
地址变换机构
为了能将用户地址空间中的逻辑地址转换为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的基本任务是实现从逻辑地址到物理地址的转换。由于页内地址和物理地址是一一对应的（如，对于页面大小是1KB的页内地址是0~1023，其相应的物理块内地址也是0~1023，无需再进行转换），因此，地址变换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。
1. 基本的地址变换机构
进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采用硬件实现。页表功能是由一组专门的寄存器来实现。一个页表项用一个寄存器。由于寄存器具有较高的访问速度，因而有利于提高地址转换速度；但由于寄存器成本高，且大多数现代计算机的页表有可能很大，使业表项的总数达到几千甚至几十万个，显然这些页表项不可能都用寄存器实现。因此，页表大多驻留在内存中。在系统中只设置一个页表寄存器PTR（Page-Table Register），在其中存放页表在内存的始址和页表的长度。平时，程序未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此在单处理机环境下，虽然系统中可以运行多个进程，但只需要一个页表寄存器。
当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间，于是这一错误将被系统发现，并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表长度的乘积想加，便得到该表项在页表中的位置，于是从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，在将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。见下图
2. 具有块表的地址变化机构
由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存，第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是第一次所得地址中获得所需数据（或向此地址写入数据）。因此，采用这种方式将使计算机的处理速度降低1/2。
为了提高地址变换速度，可在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲器，又称为“联想寄存器”或称为“快表”，在IBM系统中又取名为TLB，用以存放当前访问的那些页表项。此时的地址变换过程是：在CPU给出有效地址后，由地址变换机构自动将页号P送入告诉缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在快表中未找到对应的页表项，则还需再访问内存中的页表，找到后，把从页表项中读出的物理块号送往地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则os必须找到一个老的且已被认为是不再需要的页表项将它换出。见下图
由于成本关系，快表不可能做的很大，通常只存放16~512个页表项。
两级和多级页表
由于现在计算机都支持非常大的逻辑地址空间，在这样的环境下，页表变得非常大，占用非常大的内存空间，而且要求是连续的，这显然是不现实的，为了解决这一问题，我们可以采用这两个方法来解决这一问题：1. 对于页表所需的内存空间，可采用离散分配方式，以解决难以找到一块连续的大小内存空间的问题；2. 只需将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
1. 两级页表
针对于难以找到大的连续的内存空间来存放页表的问题，可利用将页表进行分页的方法，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0#页、1#页，····，n#页，然后离散地将各个页面分别存放在不同的物理块中。同样，也要为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号。下面以32位逻辑地址空间为例来说明。当页面大小为4KB时（12位），若采用一级页表结构，应具有20位的页号，即页表项应有1M个；在采用两级页表结构时，再对页表进行分页，使每页中包含2^10（即1024）个页表项，最多允许有2^10个页表项；或者说，外层页表中的外层页内地址P2为10位，外层页号P1为10位。此时的逻辑地址如下图：
由图可以看出，在页表的每个表项中，存放的是进程的某页在内存中的物理块号，如0#页存放在1#物理块中，1#页存放在4#物理块中。而在外层页表项中所存放的是某页表分页的首址，如0#页存放在1011#物理块中。我们可以利用外层页表和页表这两项页表来实现进程从逻辑地址到内存中物理地址的变换。
为了方便地址转换，在地址转换机构中，同样需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号作为外层页表索引，从中找到指定页表分页的始址，再利用P2作为指定页表分页的索引，找到指定的页表实现，其中既含有该页在内存的物理块号，用该块号P和页内地址d即可构成访问的内存物理地址。下图为两级页表时的地址变换机构。
上述对页表实行离散分配的方法，虽然解决了对于大页表无需大片连续存储空间的问题，但未解决用较少的内存空间去存放大页表的问题。能用较少的内存空间存放页表的唯一方法是，仅把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对于页表则只需调入一页或几页。为了表示某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位S，其值若为0，表示该页表分页不在内存中，否则说明其分页已调入内存。进程运行时，地址变换机构根据逻辑地址中的P1去查找外层页表；若找到的页表项中的状态位为0，则产生一个中断信号，请求OS将该页表分页调入内存。
3. 反置页表
（1）. 反置页表的引入
在分页系统中，为每个进程设置了一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。在现代计算机系统中，通常允许一个进程的逻辑地址空间非常大，因此就需要有许多的页表项，而因此也会占用大量的内存空间。为了减少页表占用的内存空间，引入了反置页表。一般页表的页表项是按页号进行排序的，页表项中的内容是物理块号，而反置页表则是为每一个物理块号设置了一个页表项，并将他们按物理块的编号排序，其中的内容则是页号和其所隶属进程的标识符。
（2）. 地址变换
再利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表项中的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项，则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统，此时则表示地址出错。对于具有请求调页功能的存储器管理系统，此时应产生请求调页中断，系统将把此页调入内存。
虽然反置页表可有效地减少页表占用的内存，例如，对于一个具有64MB的机器，如果页面大小为4KB，那么反置页表只占用64KB，然而在该表中只包含已经调入内存的页面，并未包含未调入内存的页面。因此，还必须为每一个进程建立一个外部页表。该页表与传统的页表一样，当所访问的页面在内存时，并不需要访问外部页表，仅当发现所需之页面不在内存时才使用它。在页表中包含了各个页在外存的物理位置，通过它可将所需之页面调入内存。
由于在反置页表中是为一个物理块设置了一个页表项，当内存容量很大时，页表项的数目还是会非常大的。要利用进程标识符和页号去检索这样大的一张线性表是相当费时的。于是可利用Hash算法来进行检索，这样可以很快找到在反置页表中的相应页表项。
页面置换算法
不适当的算法可能会导致进程发生“抖动”，即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，又需要将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上，我们称该进程发生了“抖动”。
1. 最佳（Optimal）置换算法
最佳置换算法是一种理论上的算法，其所选择的被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的
2. 先进先出（FIFO）页面置换算法
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，使他总是指向最老的页面。
3. 最近最久未使用算法（LRU）
LRU置换算法选择最近最久未使用的页面予以淘汰。该算法赋予每一个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当只需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
4. Clock置换算法
（1） 简单的Clock置换算法
当利用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1.置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。如下图，由于该算法是循环地检查各页面的使用情况，故称为Clock算法，但因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时将未使用过的页面换出，故又把该算法称为最近未用算法或NRU（Not Recently Used）算法。
（2） 改进型Clock算法
在将一个页面换出时，如果该页已被修改过便需将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。换言之，对于修改过的页面，在换出时所付出的开销比未修改过的页面大，或者说，置换代价大。在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素——置换代价，这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位A和修改位M可以组合成下面四种类型的页面；
1 类（A = 0，M = 0）：表示该页最近即未被访问，又未被修改，是最佳淘汰页。
2 类（A = 0，M = 1）： 表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
3 类（A = 1，M = 0）：表示最近已被访问，但未被修改，该页有可能再被访问。
4 类（A = 1，M = 1）：表示最近已被访问且被修改，该页可能再被访问。
在内存中的每个页，都必定是这四类页面之一。在进行页面置换时，可采用与简Clock算法相类似的算法，其差别在于该算法必须同时检查访问位与修改位，以确定该页是四类页面中的哪一种。其执行过程分成以下三步：
（1） 从指针所指示的当前位置开始，扫面循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为选中的淘汰页。在第一次扫描期间不改变访问位A。
（2） 如果第一步失败，即查找一轮后未遇到第一类页面，则开始第二轮扫描。寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面访问位都置0。
（3） 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，即寻找A=0且M=0的第一类页面，如果仍失败，必要时再重复第二步，寻找A=0且M=1的第二类页面，此时就一定能找到被淘汰的页。
该算法与简单Clock算法比较，可减少磁盘的I/O操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。
