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

A device io queue method based on atomic operation

An atomic operation and queue technology, applied in the field of computer system software programming, can solve problems such as excessive overhead, complex and impractical implementation of atomic queues, saving computing resources and speeding up data input and output.

Active Publication Date: 2017-09-26
CHANGSHA XINHONG SOFTWARE
View PDF4 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

This kind of general atomic queue is too complicated to implement, and the overhead is too large in actual specific applications, which is not practical

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
  • A device io queue method based on atomic operation
  • A device io queue method based on atomic operation
  • A device io queue method based on atomic operation

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0021] as attached figure 1 Shown: When performing enqueue operation, first use atomic swap to replace the tail pointer with a pointer to the new node, and take out the pointer of the original tail node at the same time. Then point the link pointer of the original end node to the new end node. If the original tail pointer is empty, directly point the first pointer to the new node, indicating that the new node is the first node in the queue, and it also means that the producer who submitted the new node has obtained control of the queue, that is, the producer It can be transformed into a consumer to take out nodes from the queue. Because the atomic operation guarantees the order of submission, when there are multiple producers enqueuing at the same time, only one producer can gain control.

[0022] as attached figure 2 Shown: Use the atomic swap operation to replace the tail pointer pointing to the 4th node with the pointer pointing to the 5th node, and take out the pointer...

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

A device IO queue method based on atomic operations. The queue is composed of head pointers, tail pointers, data nodes and temporary nodes. Enqueue operations can be performed by multiple producers at the same time; dequeue operations can only be performed by one consumer proceed; the dequeue operation requires a temporary node to participate, replace the first data node in the queue and take out the first data node, and use the atomic compare and exchange (CAS) operation to determine whether the tail pointer is also Point to the first data node, if so, point the tail pointer to the temporary node; the queue also includes the operation of releasing the control right, which is to remove the first node, and atomic compare and exchange (CAS) is required The operation judges whether the tail pointer also points to the first node, and if so, changes the tail pointer to a null pointer, and if the queue is cleared by removing the first node, it means that the control right is released.

Description

technical field [0001] The invention relates to the field of computer system software programming, in particular to an atomic operation-based device IO queue method. Background technique [0002] In the computer system, the access to the device IO is exclusive. Even in a symmetric multiprocessor system, even if it seems that multiple tasks are accessing a certain hardware device at the same time from the user's point of view, in the actual operation process of the bottom layer, it is By submitting the requests in the queue to the hardware device one by one to complete the deserialization. Although some hardware supports command queues inside the hardware, software queues are still required to manage other requests. This involves the mutual exclusion problem of multiple tasks accessing the IO queue at the same time. Generally, locks are used in the design to control the problem of multiple tasks accessing the queue at the same time, that is, only one task can successfully ob...

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 Patents(China)
IPC IPC(8): G06F9/44
Inventor 龙恢管志坚
Owner CHANGSHA XINHONG SOFTWARE
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