对数据结构的并发读取和插入而无需读取器的锁存或等待

摘要

本公开涉及对数据结构的并发读取和插入而无需读取器的锁存或等待。一种方法包括通过数据结构处理器执行对分层数据结构的并发的读取操作和写入操作。写入器获取对写入器修改的分层数据结构元素的锁存。读取器直接访问分层数据结构元素而无需获取锁存。写入器执行针对分层数据结构的一层或多层的修改操作。当分层数据结构的去除部分不再被引用时，通过使用全局状态值和复制的全局状态值的组合进行跟踪。全局状态值变换通过非重复的值序列。分层数据结构中不再被引用的部分利用当前全局状态值进行标记。

主权项

一种方法，包括：通过数据结构处理器执行对分层数据结构的并发的读取操作和写入操作；通过写入器获取对写入器修改的分层数据结构元素的锁存；通过读取器直接访问分层数据结构元素而无需获取锁存；通过写入器执行针对分层数据结构的一层或多层的修改操作；及当分层数据结构的去除部分不再被引用时，通过使用全局状态值和全局状态值的本地副本的组合进行跟踪；其中：全局状态值变换通过非重复的值序列；及分层数据结构中不再被引用的部分利用在最后一个引用被去除之后捕获的全局状态值进行标记。