Verification of STM on relaxed memory models

Guerraoui R, Henzinger TA, Singh V. 2011. Verification of STM on relaxed memory models. Formal Methods in System Design. 39(3), 297–331.


Journal Article | Published | English

Scopus indexed
Author
Abstract
Software transactional memories (STM) are described in the literature with assumptions of sequentially consistent program execution and atomicity of high level operations like read, write, and abort. However, in a realistic setting, processors use relaxed memory models to optimize hardware performance. Moreover, the atomicity of operations depends on the underlying hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We describe RML, a simple language for expressing concurrent programs. We develop a semantics of RML parametrized by a relaxed memory model. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm restricted to two threads and two variables, and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the restricted STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order for two threads and two variables. Finally, we extend the verification results for DSTM and TL2 to an arbitrary number of threads and variables by manually proving that the structural properties of STMs are satisfied at the hardware level of atomicity under the considered relaxed memory models.
Publishing Year
Date Published
2011-12-01
Journal Title
Formal Methods in System Design
Volume
39
Issue
3
Page
297 - 331
IST-REx-ID
531

Cite this

Guerraoui R, Henzinger TA, Singh V. Verification of STM on relaxed memory models. Formal Methods in System Design. 2011;39(3):297-331. doi:10.1007/s10703-011-0131-3
Guerraoui, R., Henzinger, T. A., & Singh, V. (2011). Verification of STM on relaxed memory models. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-011-0131-3
Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Verification of STM on Relaxed Memory Models.” Formal Methods in System Design. Springer, 2011. https://doi.org/10.1007/s10703-011-0131-3.
R. Guerraoui, T. A. Henzinger, and V. Singh, “Verification of STM on relaxed memory models,” Formal Methods in System Design, vol. 39, no. 3. Springer, pp. 297–331, 2011.
Guerraoui R, Henzinger TA, Singh V. 2011. Verification of STM on relaxed memory models. Formal Methods in System Design. 39(3), 297–331.
Guerraoui, Rachid, et al. “Verification of STM on Relaxed Memory Models.” Formal Methods in System Design, vol. 39, no. 3, Springer, 2011, pp. 297–331, doi:10.1007/s10703-011-0131-3.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar