理解操作系统中的移臂调度算法
本章分享操作系统之移臂调度算法,移臂调度算法是驱动调度技术中的算法,目的是减少为若干I/O请求服务所需消耗的总时间,从而提高系统效率。常见的移臂调度算法有先来先服务算法(FCFS)、最短查找时间优先算法、扫描算法、电梯调度算法和循环扫描算法。本章将逐步讲解各个算法的实现方法。
本章同样适用于普通本科院校的学生期末复习和计算机学院老师板书参考。
我们用一道例题来具体讲解下面的各种算法。
假设磁盘机共有200个柱面,编号0至199,考虑依次到达下列柱面访问请求序列:150,30,190,20,100,55,90
同时假如磁头当前处于50号柱面位置,且正在向柱面号大的方向移动。
至此,我们可以得出一张图:
移臂调度算法
- 先来先服务算法
- 最短查找时间优先算法
- 扫描算法
- 电梯调度算法
- 循环扫描算法
先来先服务算法
先来先服务算法中,磁盘臂是随机移动的,不考虑各I/O请求之间的相对次序和移动臂当前所处位置,特点是进程等待I/O请求的时间会很长,寻道性能较差。
简单来说,就按题目中所给的柱面依次进行到达,题目中是150,30,190,20,100,55,90,那就先去150,再绕回去30,再绕去190…等待。如图所示:
故移动臂移动柱面总数=(150-50)+(150-30)+(190-30)+(190-20)+(100-20)+(100-55)+(90-55)=710
注意:移动柱面总数就是把经过都加起来,例如第一步是50到150,经历的柱面书就是100
最短查找时间优先算法
最短查找时间优先算法总是先执行查找时间最短的请求,与FCFS算法相比有较好的寻道性能。简单来说,就是先去距离近的,例如本题中,离50最近的是55,就先去55,离55最近的是30,就先去30,以此类推,如图所示:
故移动臂移动柱面总数=(55-50)+(55-30)+(30-20)+(90-20)+(100-90)+(150-100)+(190-150)=210
相比较FCFS,是不是少了很多柱面!?
扫描算法
扫面柱面就是“撞到南墙才回头”,往一个方向扫柱面后,就一直往那个方向扫,直到那个方向的柱面都扫完了才往反方向扫,例如本题,50往55方向扫,55的下一步就是90,90的下一步就是100…直到190的下一步199,再往回扫。
注意,按照扫描算法规则,即使没有访问请求也须扫描到头,所以到达要求的190后还要扫到199。如图所示:
故移动臂移动柱面总数=(55-50)+(90-55)+(100-90)+(150-100)+(190-150)+(199-190)+(199-30)+(30-20)=328
电梯调度算法
电梯调度算法是扫描算法的一种改进,每次总是选择沿移动臂的移动方向最近的那个柱面,若同一个柱面上有多个请求,还需进行旋转优化。如果当前的移动方向上没有但相反方向有访问请求时,就改变移动臂的移动方向。
本例题中,电梯调度算法的图示情况如下:
相对于扫描算法来说,并没有扫到199,因为到达190后没有要求的柱面,所以就往相反方向扫描,就跟电梯一样,从1楼乘往18楼,如果中间楼层的人想搭电梯下楼,是要先等电梯到达18楼后再往下走。
移动臂移动柱面总数=(55-50)+(90-55)+(100-90)+(150-100)+(190-150)+(190-30)+(30-20)=310
循环扫描算法
循环扫描算法就更简单了,往一个方向扫描后,扫完了,直接重新从反方向的开始方向扫剩下的,不多说,直接上图!:
移动臂移动柱面总数=(55-50)+(90-55)+(100-90)+(150-100)+(190-150)+(150-100)+(190-150)+(199-190)+(199-0)+(20-0)+(30-20)=378
本例题来自书
操作系统教程(第5版)费翔林 骆斌 编著
p270-274
其余操作系统的算法可在博主空间找到!
感谢大家浏览,谢谢!
推荐阅读
-
理解操作系统中的移臂调度算法
-
【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 方法成对出现,以确保计数正确。