嵌入式操作系统MQX内存管理机制分析与改进

针对嵌入式实时操作系统MQX(Message Queue e Xecutive)中内存管理不够灵活等问题,提出一种基于哈希索引表和最先匹配策略相结合的自适应内存管理算法,针对不同大小的内存采用不同的内存管理策略。对于小块内存采用哈希索引表组织,实现内存分区池的常数级定位,并且通过双向链表将分区池紧密联系提高内存申请的鲁棒性;对于大块内存采用最先适应策略,减少内部碎片的产生,提高内存的利用率。实验结果表明,改进后的算法在保证MQX原有内存管理算法较高实时性的同时,提高了内存申请的命中率以及内存管理的可靠性。     

FreeRTOS内存管理方案的分析与改进

针对FreeRTOS内存管理方案分配时间不确定,切割次数较多,利用率低及合并机制不足等缺点,采用一种“精确切割”和“延时合并”相结合的策略以最大限度减少内存碎片,提高内存利用率。具体实现方法是在FreeRTOS中引入TLSF（Two-level Segregated Fit）算法数据结构,采用二级位图索引对动态内存进行管理,并改进TLSF算法的内存分配和释放过程;最后将改进的算法以及FreeRTOS移植到STM32开发平台上进行实验测试。测试结果表明该方法提高了FreeRTOS的内存分配速度,减少了内存碎片率。     

基于预测原理的嵌入式内存分配算法设计

针对嵌入式系统中内存管理存在的实时性与碎片率较大等问题,分别从时间和空间角度对其进行分析,采用基于预测分配和合并分配原理的预测合并分配机制.从时间上,利用预测线程预测下一次申请内存的大小,提前分配以减少系统等待内存创建的时间;将2次申请的内存块合并成一大块,以大块为申请单位申请内存块,以降低内存块被多次分割导致的内部碎片.μC/OS-Ⅱ平台对比实验结果表明,改进后的预测合并内存分配算法能有效从时间和内存碎片率方面提高系统的整体性能.     

一种适用嵌入式系统的自适应动态内存管理方案

实时性、可靠性、高效性的要求,使得许多嵌入式应用使用自己的内存管理方案。任何内存碎片的产生无疑都是对大块内存频繁分割造成的,适当减少对大块内存的分割,就会减少内存碎片的产生,但在减少分割内存块的同时又如何才能满足系统对内存的需求呢?文中在对当今最常用的两种内存分配算法分析的基础上提出一种新的适用于嵌入式系统的内存管理算法——自适应动态内存分配算法,重点就如何减少内存碎片,提高内存利用率,提出了新的构想与实现。望其成为嵌入式系统中内存管理算法的模板。     

一种适用嵌入式系统的自适应动态内存管理方案

实时性、可靠性、高效性的要求，使得许多嵌入式应用使用自己的内存管理方案。任何内存碎片的产生无疑都是对大块内存频繁分割造成的，适当减少对大块内存的分割，就会减少内存碎片的产生，但在减少分割内存块的同时又如何才能满足系统对内存的需求呢？文中在对当今最常用的两种内存分配算法分析的基础上提出一种新的适用于嵌入式系统的内存管理算法——自适应动态内存分配算法，重点就如何减少内存碎片，提高内存利用率，提出了新的构想与实现。望其成为嵌入式系统中内存管理算法的模板。     

实时系统中的动态内存分配算法

针对实时系统中的内存分配问题,分析实时系统应用程序的行为特点,提出一种使用双级离散表和双级索引位图相结合的动态内存分配方法。对于较小的内存分配请求,使用位图索引来加快速度并且降低内存分割的次数。对于较大内存块,使用双级离散表的方法降低内存碎片。实验表明,该方法具有很低的内存碎片率和确定的响应时间,适合实时性要求较高的系统。     

基于内存云的大块数据对象并行存取策略

由于内存云(RAMCloud)只支持最大1 MB的小块数据对象存储,因此当大于1 MB的对象需要存储在内存云集群中就会受到对象大小的限制,无法在集群中进行存储。为了解决内存云存储限制的问题,提出了基于内存云的大块数据对象并行存取策略。该存储策略首先将大块数据对象分割成若干个1 MB的小块数据对象,然后在客户端生成数据摘要,最后使用并行存储算法将客户端分割成的小块数据对象存储在内存云集群中。读取时首先读取数据摘要,然后根据数据摘要从内存云集群中并行读取小块数据对象,并将小块数据对象合并生成大块数据对象。实验结果表明:大块数据对象的并行存取策略在不破坏内存云集群体系结构的前提下存储时间为16~18 μs,读取时间为6~7 μs。在InfiniBand网络架构下,所提并行算法的加速比呈现类似线性的增长,它使大块数据对象也能够像小块数据对象一样在微秒级别下快速、高效地进行存取。     

可持久化CSB+-树索引技术研究

现有主存索引方案为实现重用功能仅将更新操作存储到硬盘中,根据操作序列进行索引恢复,实时性和重用性均较差。为进一步提升重用性和实时性,提出了一种可持久化的CSB+-树(cache sensitive B+-tree)索引方案。该方案基于内存映射技术,完整而高效地将索引结构保存到外存中,导入时无需重复创建索引,可节省大量计算资源。针对索引更新过程中出现大量内存碎片问题,采用一种分类内存管理机制进行管理和监视,当内存碎片过多而无法利用时,基于有序键值对进行索引重构以完全消除内存碎片。实验结果表明,所提方案与现有方案相比具有更好的实时性和重用性,同时具有高效的查询处理能力。     

Linux内核伙伴系统分析

本文针对Linux内核实现的伙伴系统进行了抽象分析,并通过实例演示了算法的执行过程. 分析了用于物理地址空间管理的三级数据结构及其关系. 在此基础上,详细描述了用于分配和回收页框的伙伴算法. 对于待回收的内存块而言,计算其伙伴的索引及合并内存块的索引是回收操作的关键,讨论了相关计算方法的几条结论并予以证明.     

大型3D场景漫游系统内存管理

在大型3D场景漫游系统中,单个资源(如模型、纹理)所需内存较大且分配和释放频繁,为了防止内存碎片的产生并提高内存分配速度,提出了一种新型内存管理方法.根据程序需求首先划分出一块或多块大的虚拟内存区域,然后基于所划分的内存区域进行内存分配和回收管理.在该管理方法中,对于程序中的小资源,使用内存池;对于大的资源,则使用伙伴系统内存管理方法.实验结果表明,该内存管理方法高效且稳定.     

部分延迟放宽合并算法

本文针对Buddy算法再多核系统内存管理中缺点,提出部分延迟放宽合并算法,,增加合并连续内存块,降低内存访问时间,提高系统整体性能;仿真实验结果证明算法有效性.     

对伙伴算法内存管理的讨论

伙伴算法是用于内存管理的经典算法之一，本文以linux内存管理为模型，分析了内存管理中伙伴算法的特点，并指出算法中的不足之处，针对具体的情况和应用讨论了几点改进的方法，一定程度上使该算法更具有适应具体环境的能力。     

Linux内存管理实现的分析与研究

存储管理子系统作为操作系统中最重要的组成部分之一,对整个系统的运行起着举足轻重的作用。Linux继承了UNIX系统的优秀设计思想,并采用了许多先进算法来保持系统的高效性和稳定性。文中先概述了Linux2.4物理内存的管理,然后介绍了解决内存中碎片问题的伙伴系统算法和Slab分配器,并讨论了它们实现的要点,着重对Slab分配器中的几个数据结构进行了分析。     

面向通信领域通用内存管理单元的算法和实现

由于快速性、实时性、可靠性的要求，使得许多嵌入式应用使用自己的内存管理程序，该文概要地分析了嵌入式操作内存管理的实现原理以及它们的内存分配与回收、内存保护算法。在此基础上详细阐述面向通信领域的一种内存管理方法——UB(内存分块管理)内存管理算法，并描述了它的实现方法。     

A Geometry-Based Point Cloud Reduction Method for Mobile Augmented Reality System

In this paper, a geometry-based point cloud reduction method is proposed, and a real-time mobile augmented reality system is explored for applications in urban environments. We formulate a new objective function which combines the point reconstruction errors and constraints on spatial point distribution. Based on this formulation, a mixed integer programming scheme is utilized to solve the points reduction problem. The mobile augmented reality system explored in this paper is composed of the offline and online stages. At the offline stage, we build up the localization database using structure from motion and compress the point cloud by the proposed point cloud reduction method. While at the online stage, we compute the camera pose in real time by combining an image-based localization algorithm and a continuous pose tracking algorithm. Experimental results on benchmark and real data show that compared with the existing methods, this geometry-based point cloud reduction method selects a point cloud subset which helps the image-based localization method to achieve higher success rate. Also, the experiments conducted on a mobile platform show that the reduced point cloud not only reduces the time consuming for initialization and re-initialization, but also makes the memory footprint small, resulting a scalable and real-time mobile augmented reality system.     

Implementation of a constant‐time dynamic storage allocator

This paper describes the design criteria and implementation details of a dynamic storage allocator for real‐time systems. The main requirements that have to be considered when designing a new allocator are concerned with temporal and spatial constraints. The proposed algorithm, called TLSF (two‐level segregated fit), has an asymptotic constant cost, O(1), maintaining a fast response time (less than 200 processor instructions on a x86 processor) and a low level of memory usage (low fragmentation). TLSF uses two levels of segregated lists to arrange free memory blocks and an incomplete search policy. This policy is implemented with word‐size bitmaps and logical processor instructions. Therefore, TLSF can be categorized as a good‐fit allocator. The incomplete search policy is shown also to be a good policy in terms of fragmentation. The fragmentation caused by TLSF is slightly smaller (better) than that caused by best fit (which is one of the best allocators regarding memory fragmentation). In order to evaluate the proposed allocator, three analyses are presented in this paper. The first one is based on worst‐case scenarios. The second one provides a detailed consideration of the execution cost of the internal operations of the allocator and its fragmentation. The third analysis is a comparison with other well‐known allocators from the temporal (number of cycles and processor instructions) and spatial (fragmentation) points of view. In order to compare them, a task model has been presented. Copyright © 2007 John Wiley & Sons, Ltd.     

An improved direct labeling method for the max–flow min–cut computation in large hypergraphs and applications

Algorithms described so far to solve the maximum flow problem on hypergraphs first necessitate the transformation of these hypergraphs into directed graphs. The resulting maximum flow problem is then solved by standard algorithms. This paper describes a new method that solves the maximum flow problem directly on hypergraphs, leading to both reduced run time and lower memory requirements. We compare our approach with a state–of–the–art algorithm that uses a transformation of the hypergraph into a directed graph and an augmenting path algorithm to compute the maximum flow on this directed graph: the run–time complexity as well as the memory space complexity are reduced by a constant factor. Experimental results on large hypergraphs from VLSI applications show that the run time is reduced, on average, by a factor approximately 2, while memory occupation is reduced, on average, by a factor of 10. This improvement is particularly interesting for very large instances, to be solved in practical applications.