Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Queue CAS atomic operation control method

A control method and atomic operation technology, applied in the field of queue CAS atomic operation control, can solve problems such as difficult to guarantee, low efficiency, unattainable, etc., and achieve the effect of improving efficiency, reducing failure rate, and reducing high

Active Publication Date: 2018-09-07
NANJING UNIV OF POSTS & TELECOMM
View PDF4 Cites 3 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0007] However, the existing technology has the following problems: in the concurrent lock-free data structure, taking the FIFO queue as an example, it is difficult to ensure that the producer does not move when the consumer is operating
The existing range-based atomic operation solution is extremely inefficient in actual use, which will cause consumers to retry continuously, failing to achieve the original intention of range-based atomic operations, and even lead to livelocks in severe cases

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Queue CAS atomic operation control method
  • Queue CAS atomic operation control method
  • Queue CAS atomic operation control method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0029] The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings.

[0030] The present invention designs a queue CAS atomic operation control method, aiming at the transmission length of k·2 from the sending end to the receiving end n The lock-free single-producer single-consumer queue realizes the CAS atomic operation of the receiving end on the data in the queue, where k and n are both integers not less than 1.

[0031] Such as figure 1 The schematic diagram of the 16-bit head pointer module of the lock-free queue producer is shown. First, you need to declare the pointer head of the queue producer, whose type is 16-bits long integer. This pointer is declared as a global variable to record where the producer is currently located. The upper 8 bits of the Head pointer represent the first address of the block where the element is located, which is the key address value (key address valu...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a queue CAS atomic operation control method, which, based on a queue slicing thought, is used for solving the problem of failure of indirectly judging CAS under the conditionof range-based atomic operation maximum because a CAS loop statement is used for judging a single pointer position of a producer in the prior art. Through the design method, queue elements are sliced,a single element position pointed by a head of the producer is no longer purely judged, and instead, slice number values pointed by the pointer of the producer before and after CAS judgment are judged, so that the efficiency of a queue algorithm is greatly improved.

Description

technical field [0001] The invention relates to a queue CAS atomic operation control method, which belongs to the technical field of lock-free concurrent algorithms. Background technique [0002] In recent years, the lock-free data structure design method based on Compare and Swap (CAS) atomic operation provides a more efficient and convenient data access method for upper-level algorithms, and has become a research hotspot in academia and industry. [0003] CAS is an atomic primitive widely used in today's computers, thus enabling the correctness of today's lock-free concurrent algorithms to be guaranteed. However, the main idea of ​​CAS operation is compare-exchange. Specifically, the target value is first compared with the old value, and if they are equal, the new value is assigned to the target variable; otherwise, the target value is not modified. CAS can perform this operation atomically and guarantee that the comparison-modification process will not be interrupted by...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06F8/30
CPCG06F8/31
Inventor 王俊昌田杨锋付雄
Owner NANJING UNIV OF POSTS & TELECOMM
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com