Computer-implemented lock-free data structure and related methods and apparatuses_WO2020200477A1.pdf
免费下载
)
(
(51) International Patent Classification: KR, KW, KZ, LA, LC, LK, LR, LS, LU, LY,MA, MD, ME,
G06F 9/52 (2006.01) G06F 12/02 (2006.01) MG, MK, MN, MW, MX, MY, MZ, NA, NG, NI, NO, NZ,
OM, PA, PE, PG, PH, PL, PT, QA, RO, RS, RU, RW, SA,
(21) International Application Number:
SC, SD, SE, SG, SK, SL, SM, ST, SV, SY, TH, TJ, TM, TN,
PCT/EP20 19/058668
TR, TT, TZ, UA, UG, US, UZ, VC, VN, ZA, ZM, ZW.
(22) International Filing Date:
(84) Designated States (unless otherwise indicated, for every
05 April 2019 (05.04.2019)
kind of regional protection available) . ARIPO (BW, GH,
(25) Filing Language: English
GM, KE, LR, LS, MW, MZ, NA, RW, SD, SL, ST, SZ, TZ,
UG, ZM, ZW), Eurasian (AM, AZ, BY, KG, KZ, RU, TJ,
(26) Publication Language: English
TM), European (AL, AT, BE, BG, CH, CY, CZ, DE, DK,
(71) Applicant: HUAWEI TECHNOLOGIES CO., LTD.
EE, ES, FI, FR, GB, GR, HR, HU, IE, IS, IT, LT, LU, LV,
[CN/CN]; Huawei Administration Building Bantian Long-
MC, MK, MT, NL, NO, PL, PT, RO, RS, SE, SI, SK, SM,
gang District, Shenzhen, Guangdong 518129 (CN).
TR), OAPI (BF, BJ, CF, CG, Cl, CM, GA, GN, GQ, GW,
KM, ML, MR, NE, SN, TD, TG).
(72) Inventor; and
(71) Applicant (for US only): ALVAREZ, Victor [DE/DE];
Published:
Huawei Technologies Duesseldorf GmbH Riesstr. 25,
— with international search report (Art. 21(3))
80992 Munich (DE).
(74) Agent: KREUZ, Georg: Huawei Technologies Duessel¬
dorf GmbH, Riesstr. 25, 80992 Munich (DE).
(81) Designated States (unless otherwise indicated, for every
kind of national protection available) : AE, AG, AL, AM,
AO, AT, AU, AZ, BA, BB, BG, BH, BN, BR, BW, BY, BZ,
CA, CH, CL, CN, CO, CR, CU, CZ, DE, DJ, DK, DM, DO,
DZ, EC, EE, EG, ES, FI, GB, GD, GE, GH, GM, GT, HN,
HR, HU, ID, IL, IN, IR, IS, JO, JP, KE, KG, KH, KN, KP,
(54) Title: COMPUTER-IMPLEMENTED LOCK-FREE DATA STRUCTURE AND RELATED METHODS AND APPARATUSES
(57) Abstract: A computer-implemented lock-free data structure and related
st
er
ta
at
st
COMPUTER-IMPLEMENTED LOCK-FREE DATA STRUCTURE AND RELATED
METHODS AND APPARATUSES
TECHNICAL FIELD
The present disclosure relates to the field of data processing, and more particularly to
a computer-implemented lock-free data structure and related methods and
apparatuses.
BACKGROUND
In computer science, a data structure is a format for organizing, managing and storing
data. A data structure is designed to organize data to suit a specific purpose so that it
can be accessed and worked with in appropriate ways.
At least for some data structures, strong consistency reads and safe memory
reclamation may be desirable. In strong consistency reads, all reads see the latest
previously written values. Memory-constrained concurrent data structures are an
example of a data structure that may require safe memory reclamation.
Strong consistency reads and safe memory reclamation have been traditionally
provided e.g. via techniques including reference counting, latches or spinlocks, hazard
pointers, and copy-read-update (RCU).
However, reference counting may produce a memory overhead on each data type or
node found in a data structure for realizing a counter. E.g. on highly memory-
constrained data structures this may not be desirable. Latches or spinlocks may be
realized with a single bit of space per data type found in the data structure but they
may strongly limit scalability of the data structure due to false sharing between threads.
Hazard pointers and RCUs may require a whole infrastructure to be realized, and thus
they may be very intricate and therefore difficult to implement.
SUMMARY
This summary is provided to introduce a selection of concepts in a simplified form that
are further described below in the detailed description. This summary is not intended
to identify key features or essential features of the claimed subject matter, nor is it
intended to be used to limit the scope of the claimed subject matter.
of 45
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论