一、页式存储基本原理

（一）内存划分

       页式存储首先将内存物理空间划分成大小相等的存储块，这些块通常被称为“页帧”或“物理页”。每个页帧的大小是固定的，例如常见的页帧大小有4KB、8KB等，这个大小由操作系统决定。同时，操作系统会为每个页帧分配一个唯一的编号，即页帧号。

（二）程序划分

       与内存物理空间的划分相对应，页式存储也将要运行的程序的逻辑地址空间划分成大小与页帧相同的“页”。这些页在逻辑上连续，但在物理内存中可以不连续存放。每个页也被分配一个唯一的编号，即页号。

（三）页表管理

       页式存储通过页表来管理逻辑页与物理页帧之间的映射关系。页表是一个数据结构，它记录了每个逻辑页对应的物理页帧号。当程序访问某个逻辑地址时，操作系统会首先查找页表，找到该逻辑地址对应的物理页帧号，然后结合页内偏移量（即逻辑地址中除去页号的部分）来确定最终的物理地址。

（四）内存分配与访问

1. 内存分配：当程序被装入内存时，操作系统会根据程序的逻辑页大小，将程序的页逐一装入到内存中的空闲页帧中。这个过程可以是静态的（即程序执行前全部装入），也可以是动态的（即程序执行过程中根据需要装入）。
2. 内存访问：当程序运行时，它会产生对内存的逻辑地址访问请求。操作系统会利用页表将这些逻辑地址转换为物理地址，然后访问相应的内存位置。

（五）页式存储的优点

1. 提高内存利用率：由于页的大小是固定的，且页在内存中可以不连续存放，因此页式存储能够更有效地利用内存空间，减少内存碎片。
2. 支持虚拟内存：页式存储是虚拟内存技术的基础之一。通过页表，操作系统可以实现逻辑地址与物理地址的分离，从而支持比物理内存更大的虚拟内存空间。
3. 便于内存保护：页式存储可以为每个页设置访问权限，从而实现对内存的保护。例如，可以防止某个进程访问不属于它的内存区域。

（六）页式存储的缺点

1. 页表开销：页表需要占用一定的内存空间来存储映射关系。对于大型程序或需要支持大量进程的操作系统来说，页表的开销可能会比较大。
2. 缺页中断：在动态内存分配的情况下，当程序访问一个尚未装入内存的页时，会产生缺页中断。操作系统需要处理这个中断，将所需的页从磁盘调入内存，这会增加程序的执行时间。

二、页式置换算法

1.先进先出（FIFO）页面置换算法

       FIFO算法选择最早进入内存的页面进行置换。它维护一个页面队列，新页面进入队列尾部，缺页时从队列头部移除页面。该算法实现简单，开销小，但可能导致贝拉迪异常，即当增加分配给进程的物理块数时，缺页中断的次数反而增加。这是因为FIFO算法没有考虑页面的访问频率或重要性，只是简单地按照页面进入内存的顺序进行置换。

2.最近最少使用（LRU）页面置换算法

       LRU算法选择最长时间未被访问的页面进行置换。它基于页面的使用历史进行决策，能够减少页面错误和磁盘I/O操作的数量。LRU算法通常使用链表或栈数据结构来维护页面访问顺序，每次访问页面时，将该页面移到链表头部或栈顶，缺页时从链表尾部或栈底移除页面。虽然LRU算法性能较好，但实现复杂，需要维护链表或栈，并在每次内存访问时更新数据结构。此外，LRU算法还需要较高的硬件辅助，如使用硬件计数器来跟踪页面的访问时间。

3.最优页面置换算法（OPT）

       OPT算法选择未来最长时间内不会被访问的页面进行置换。然而，由于操作系统无法预知未来的页面请求，因此OPT算法主要用于理论分析，而不是实际操作系统中。OPT算法可以作为衡量其他页面置换算法性能的基准。尽管OPT算法无法实现，但它提供了一种理想化的页面置换策略，即选择未来最长时间内不会被访问的页面进行置换，以最小化页面故障次数并最大化命中次数。

4.第二次机会页面置换算法

       第二次机会算法是FIFO算法的一个变种。在淘汰一个页面之前，它会检查该页面是否已经被修改过（或检查其访问位R）。如果页面未被修改（或访问位为0），则直接淘汰；如果已被修改（或访问位为1），则将其访问位清零，并将其重新插入到队列尾部，给予它第二次机会。这样，第二次机会算法避免了贝拉迪异常，因为它允许页面在未被访问时获得第二次机会。该算法实现相对简单，性能优于FIFO。

5.时钟页面置换算法（CLOCK）

       CLOCK算法是第二次机会算法的一个高效实现。它将所有页面保存在一个类似钟面的环形链表中，一个指针指向最老的页面。缺页时，从指针指向的页面开始检查，如果其访问位为0，则淘汰该页面；如果为1，则清零访问位并将指针前移一位，继续检查直到找到访问位为0的页面。CLOCK算法实现简单且高效，避免了在链表中频繁移动页面的开销。它适用于需要快速响应的场景，如实时操作系统。

6.最不经常使用（LFU）页面置换算法

       LFU算法选择访问次数最少的页面进行置换。它为每个页面关联一个计数器，记录该页面的访问次数。缺页时，置换计数器值最小的页面。LFU算法能够反映页面的使用情况，但可能受到初始阶段大量使用但随后不再使用的页面的影响。此外，LFU算法实现相对复杂，需要维护计数器并更新其值。在实际应用中，LFU算法可能不如LRU算法有效，因为LRU算法能够更好地利用页面的时间局部性。

7.工作集页面置换算法

       工作集算法基于进程的工作集进行页面置换。工作集是指进程在过去一段时间内实际访问过的页面的集合。缺页时，找出一个不在工作集中的页面并淘汰它。工作集算法能够适应进程的内存访问模式变化，提高内存利用率和程序性能。然而，它需要维护一个工作集数据结构，并动态更新其内容。这增加了算法的复杂性和开销。

 结语  

保持谦逊的态度

有助于不断学习和成长

！！！