.png){kind=icon}
.png){kind=icon}
Return
Formal modelling of list based dynamic memory allocators
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-017-9280-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Existing implementations of dynamic memory allocators (DMA) employ a large spectrum of policies and techniques. The formal specifications of these techniques are quite complicated in isolation and very complex when combined. Therefore, the formal reasoning on a specific DMA implementation is difficult for automatic tools and mostly single-use. This paper proposes a solution to this problem by providing formal models for a full class of DMA, the class using various kinds of lists to manage the memory blocks controlled by the DMA. To obtain reusable formal models and tractable formal reasoning, we organise these models in a hierarchy ranked by refinement relations. We prove the soundness of models and the refinement relations using the modeling framework Event-B and the theorem prover Rodin. We demonstrate that our hierarchy is a basis for an algorithm theory for list based DMA: it abstracts various existing implementations of DMA and leads to new DMA implementations. The applications of this formalisation include model-based code generation, testing, and static analysis.
Keywords:
dynamic memory allocators
formal methods
refinement
Event-B
Rodin
model-based design
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K
View more organizations