在基于虚拟页面的存储管理中实现页面替换算法 java 虚拟页面存储的三种算法
最编程
2024-04-08 22:48:28
...
文章目录
- 1:页面置换算法的相关概念
- 2:局部置换算法
- 1.最优、先进先出、最近最久未使用算法
- 2.时钟置换算法和最不常用算法
- 3.Belady现象和局部置换算法的比较
- 3:全局置换算法
- 1.工作集置换算法
- 2.缺页率置换算法
- 3.抖动和负载控制
1:页面置换算法的相关概念
- 功能和目标
置换算法并不是针对一个进程,而是一系列进程 - 页面锁定
有些页面是不能把它放到外存里的 - 置换算法的评价方法
通过记录进程访问内存的页面轨迹来模拟页面置换行为,记录产生缺页的次数 - 页面置换算法分类
局部:在内存中,给每个进程分配的页面总数是不会变化的。
全局:置换页面的选择范围是所有可换出的物理界面
2:局部置换算法
1.最优、先进先出、最近最久未使用算法
- 最优算法(OPT optimal):不可实现
基本思路:置换在未来最长时间不访问的页面 - 算法示例:
在1-4时刻,访问都是可以正常访问的,在时刻5,需要访问e页面,这时候根据最优算法调出d页面,产生一次缺页,然后6-9时刻也是可以正常访问的,在时刻10时,也产生一次缺页。
- 先进先出算法(FIFO):最简单
思路:选择在内存驻留时间最长的页面进行置换 - 算法示例:
在时刻5,最先进来的页面是a,所以将e替换a,同时,逻辑链表变成了bcde
- 最近最久未使用算法(LRU Least Recently Used):开销大
思路:选择最长时间没有被引用的页面进行置换 - 算法示例:
在时刻5时,最久未被引用的是c,替换c。
- 可能实现方法:
示例:
在时刻5,置换栈底的页面c,同时将压入栈顶。在时刻6,将栈中的b移到栈顶(开销)
2.时钟置换算法和最不常用算法
这两个算法实际上是对FIFO和LRU的一些简化
- 时钟置换算法(Clock)(LRU和FIFO的折中)
- 思路:仅对页面的访问情况进行大致统计
- 数据结构:
- 算法:
- 示例:
- 先将各页面组成一个环形链表
- 当访问页号1时,将页号1的访问位置1,如果再次访问页号1,则访问为仍是1.
- 当缺页的时候,就从指针出开始顺时针寻找访问位为0的(在这过程中,将访问位为1的清零),在下图就是找到了页号4,将页号4置换出去
- 改进的时钟算法
在上图中,第二行时,修改位为1表示该页被修改过,这时候就修改位置0,同时将修改存入外存。第三行和第4行的处理方式和时钟算法一致。
- 最不常用算法(LFU,Least Frequently Used)
- 思路:缺页时,置换访问次数最少的页面
- 实现:
- 特征:算法开销大,开始时频繁使用,但以后不使用的页面很难置换(可以采用计数定期右移解决)。
- 示例:
3.Belady现象和局部置换算法的比较
- Belady现象:FIFO有,LRU没有,
- 现象解释:局部置换算法给每个进程分配的物理页面数是一定的,当缺页次数过高时,就需要增加分配物理页面数,但此时并不一定会降低缺页次数(主要是置换算法采用的是FIFO算法等)。
- 原因:FIFO算法的置换特征与进程访问内存的动态特征是有矛盾的,被它置换出去的页面并不一定是进程近期不会访问的。
- 示例:
- LRU、FIFO、Clock的比较
3:全局置换算法
1.工作集置换算法
在局部算法里面并没有考虑各个进程之间的访存差异,全局置换算法为进程分配可变数目的物理页面。常驻集是指进程在运行时,当前时刻实际驻留在内存当中的页面集合。而工作集是进行再运行过程所固有的特征。置换算法的工作就是在进程的工作集的前提下,确定常驻集的大小以及相应页面。
- 工作集置换算法相关概念
- 要解决的问题:
- cpu利用率与并发进程数之间的关系
- 工作集
当前时间t到过去一段时间它所访问的逻辑页面的集合。有了工作集,就能知道一个进程在某个时刻所需要的页面数,进而通过操作系统进行合理分配。
如果全局置换算法能近似的按照上面这条曲线来,那么效率就提高了很多。 - 常驻集
常驻集是指进程在运行时,当前时刻实际驻留在内存当中的页面集合。而工作集是进行再运行过程所固有的特征。置换算法的工作就是在工作集的前提下,确定常驻集的大小。
- 工作集置换算法
换成不在工作集中的页面(不一定是在缺页的时候),在实现方法可以看出复杂的是在访存时,怎么换出不在工作集的页面。
示例:
- 在时间0时,假定了t=-1和t=-2时的几个页面,意义在于可以判断在时刻1时,过去的时间里是有几个页面超出了工作集。
- 时刻1,访问第一个页面c,发生缺页,按工作集置换算法,直接把页面c补进来
- 时刻2,c进行访存时,因为窗口大小为4,所以t=-2时所对应的页面e不在工作集,就将e换出。
- 时刻3,正常访问。
- 时刻4,访问b页面时,类似时刻1的将b补进来,同时将t=0时刻对应的a页面移出,后面的类似处理
2.缺页率置换算法
- 缺页率以及影响因素
- 缺页率置换算法(相比工作集算法,降低了开销)
- 算法实现
- 示例
- 时刻1,出现缺页,之间补页面
- 时刻2,正常访问,时刻3也是正常访问
- 时刻4,访问b时出现缺页,把b补进来,此时缺页时间间隔是3,大于窗口大小2,将两个缺页之间没有访问的页面剔除出去,也就是剔除a、e。后面类似,在时刻6时,缺页间隔为2,不进行剔除。
3.抖动和负载控制
- 抖动问题
系统中的进程数目很多 - 负载控制
希望内存的大小恰好是当前所有进程的工作集的总和。同时,当缺页间隔时间大于缺页异常处理时间时,处理器就来得及处理缺页,如果是小于的话,就满负荷运行了,处理不过来了。所以找到一个负载均衡点,使得两者恰好相等。
上一篇: 大多数线程长时间处于发送数据状态
推荐阅读
-
在基于虚拟页面的存储管理中实现页面替换算法 java 虚拟页面存储的三种算法
-
【Netty】「萌新入门」(七)ByteBuf 的性能优化-堆内存的分配和释放都是由 Java 虚拟机自动管理的,这意味着它们可以快速地被分配和释放,但是也会产生一些开销。 直接内存需要手动分配和释放,因为它由操作系统管理,这使得分配和释放的速度更快,但是也需要更多的系统资源。 另外,直接内存可以映射到本地文件中,这对于需要频繁读写文件的应用程序非常有用。 此外,直接内存还可以避免在使用 NIO 进行网络传输时发生数据拷贝的情况。在使用传统的 I/O 时,数据必须先从文件或网络中读取到堆内存中,然后再从堆内存中复制到直接缓冲区中,最后再通过 SocketChannel 发送到网络中。而使用直接缓冲区时,数据可以直接从文件或网络中读取到直接缓冲区中,并且可以直接从直接缓冲区中发送到网络中,避免了不必要的数据拷贝和内存分配。 通过 ByteBufAllocator.DEFAULT.directBuffer 方法来创建基于直接内存的 ByteBuf: ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); 通过 ByteBufAllocator.DEFAULT.heapBuffer 方法来创建基于堆内存的 ByteBuf: ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); 注意: 直接内存是一种特殊的内存分配方式,可以通过在堆外申请内存来避免 JVM 堆内存的限制,从而提高读写性能和降低 GC 压力。但是,直接内存的创建和销毁代价昂贵,因此需要慎重使用。 此外,由于直接内存不受 JVM 垃圾回收的管理,我们需要主动释放这部分内存,否则会造成内存泄漏。通常情况下,可以使用 ByteBuffer.clear 方法来释放直接内存中的数据,或者使用 ByteBuffer.cleaner 方法来手动释放直接内存空间。 测试代码: public static void testCreateByteBuf { ByteBuf buf = ByteBufAllocator.DEFAULT.buffer(16); System.out.println(buf.getClass); ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); System.out.println(heapBuf.getClass); ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); System.out.println(directBuf.getClass); } 运行结果: class io.netty.buffer.PooledUnsafeDirectByteBuf class io.netty.buffer.PooledUnsafeHeapByteBuf class io.netty.buffer.PooledUnsafeDirectByteBuf 池化技术 在 Netty 中,池化技术指的是通过对象池来重用已经创建的对象,从而避免了频繁地创建和销毁对象,这种技术可以提高系统的性能和可伸缩性。 通过设置 VM options,来决定池化功能是否开启: -Dio.netty.allocator.type={unpooled|pooled} 在 Netty 4.1 版本以后,非 Android 平台默认启用池化实现,Android 平台启用非池化实现; 这里我们使用非池化功能进行测试,依旧使用的是上面的测试代码 testCreateByteBuf,运行结果如下所示: class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeHeapByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf 可以看到,ByteBuf 类由 PooledUnsafeDirectByteBuf 变成了 UnpooledUnsafeDirectByteBuf; 在没有池化的情况下,每次使用都需要创建新的 ByteBuf 实例,这个操作会涉及到内存的分配和初始化,如果是直接内存则代价更为昂贵,而且频繁的内存分配也可能导致内存碎片问题,增加 GC 压力。 使用池化技术可以避免频繁内存分配带来的开销,并且重用池中的 ByteBuf 实例,减少了内存占用和内存碎片问题。另外,池化技术还可以采用类似 jemalloc 的内存分配算法,进一步提升分配效率。 在高并发环境下,池化技术的优点更加明显,因为内存的分配和释放都是比较耗时的操作,频繁的内存分配和释放会导致系统性能下降,甚至可能出现内存溢出的风险。使用池化技术可以将内存分配和释放的操作集中到预先分配的池中,从而有效地降低系统的内存开销和风险。 内存释放 当在 Netty 中使用 ByteBuf 来处理数据时,需要特别注意内存回收问题。 Netty 提供了不同类型的 ByteBuf 实现,包括堆内存(JVM 内存)实现 UnpooledHeapByteBuf 和堆外内存(直接内存)实现 UnpooledDirectByteBuf,以及池化技术实现的 PooledByteBuf 及其子类。 UnpooledHeapByteBuf:通过 Java 的垃圾回收机制来自动回收内存; UnpooledDirectByteBuf:由于 JVM 的垃圾回收机制无法管理这些内存,因此需要手动调用 release 方法来释放内存; PooledByteBuf:使用了池化机制,需要更复杂的规则来回收内存; 由于池化技术的特殊性质,释放 PooledByteBuf 对象所使用的内存并不是立即被回收的,而是被放入一个内存池中,待下次分配内存时再次使用。因此,释放 PooledByteBuf 对象的内存可能会延迟到后续的某个时间点。为了避免内存泄漏和占用过多内存,我们需要根据实际情况来设置池化技术的相关参数,以便及时回收内存; Netty 采用了引用计数法来控制 ByteBuf 对象的内存回收,在博文 「源码解析」ByteBuf 的引用计数机制 中将会通过解读源码的形式对 ByteBuf 的引用计数法进行深入理解; 每个 ByteBuf 对象被创建时,都会初始化为1,表示该对象的初始计数为1。 在使用 ByteBuf 对象过程中,如果当前 handler 已经使用完该对象,需要通过调用 release 方法将计数减1,当计数为0时,底层内存会被回收,该对象也就被销毁了。此时即使 ByteBuf 对象还在,其各个方法均无法正常使用。 但是,如果当前 handler 还需要继续使用该对象,可以通过调用 retain 方法将计数加1,这样即使其他 handler 已经调用了 release 方法,该对象的内存仍然不会被回收。这种机制可以有效地避免了内存泄漏和意外访问已经释放的内存的情况。 一般来说,应该尽可能地保证 retain 和 release 方法成对出现,以确保计数正确。