1 The background is currently using multi-threaded processing mechanisms, the following processing is more common: a thread is responsible for placing upstream data into a public queue, and another thread removes data from the public queue. Reading operations need to share a mutex to ensure thread security, so that writing data and data is actually serial, some time, this operation will have a certain impact on software processing performance. If we can implement a queue, the read operation does not require any mutual amount of mutual protection to ensure thread security, then the processing capability of reading and writing thread will be significantly improved. In fact, it is not that there is no concurrent conflict between the reading interface of the queue and the write interface, that is, one thread only calls the read interface, one thread only calls the write interface, the two threads do not need any synchronization action; If multiple threads simultaneously call the read interface or call the write interface, read interfaces and write interfaces can be synchronized with different mutex; eventually achieve our purpose: in multiple threads, reading rate is not The rate of affecting the write, and vice versa. In addition to reading operations, many places may also know the size of the queue, such as internal debugging information, or the maximum capacity of the restriction queue in the implementation, which can be used in reading and writing two threads, but also wants to handle You can take this information without locking in the thread, and this interface and the reading and writing interface do not have concurrently conflict, thereby increasing the execution efficiency.
1 implementation
The operation that needs to be threaded is because you need to modify (some thread modifications, and some thread access) public resources are caused, as long as we guarantee that it is guaranteed to add a node and delete a node, it does not need to modify the same resource. And to ensure that the resources to be accessed are always valid, then the reading operation itself can be the thread.
Below is a simple implementation of a list.
Struct ListNode
{
Int data;
ListNode * Next;
}
Struct List
{
ListNode * Beg;
ListNode * End;
List (): beg (0), End (0) {}
Void Push_Back (int DATA)
{
IF (! End)
Beg = end = new listNode (node);
Else
{
End.next = new listNode (node);
End = end-> next;
}
}
Void pop_front ()
{
ListNode * TOP = Beg;
BEG = Beg-> next;
DELETE TOP;
IF (! beg)
End = beg;
}
int Front ()
{
Return beg-> data;
}
}
The above implementation, because the increase in deletions may modify the internal BEG, END variable, and the thread is unable to do.
If the Push_Back only modifies the END variable, Pop_Front only modifies the beg variable, then the two operations can be threaded. If the list is empty, the end is expressed in an empty pointer, it is impossible to do this. When the list is empty, beg, and End also points to a fixed node, so this can be implemented. As follows:
Struct List
{
ListNode * Beg;
ListNode * End;
List (): Beg (New ListNode (0)), End (BEG) {}
...
}
When the data is inserted, the data is saved with an existing END node, and then generates a new indication end, as follows
Void Push_Back (int DATA)
{
End.data = data;
End.next = new listNode (0);
End = end-> next;}
This does not need to modify the BEG variable when inserting data. Do similar processing when extracting data:
Void pop_front ()
{
IF (! EMPTY ())
{
ListNode * Oldbeg = Beg;
BEG = Beg-> next;
DELETE OLDBEG;
}
}
Consider the actual value operation
int Front ()
{
Return beg-> data;
}
If you call Front () to operate, Beg is just deleted, it may cause a serious problem. If FRONT () and POP_FRONT () are only used in one reading thread, the problem is not large. If these two interfaces are merged, as follows:
INT pop_front ()
{
int R = Beg-> Data
ListNode * Oldbeg = Beg;
BEG = Beg-> next;
DELETE OLDBEG;
Return Ret;
}
It is more convenient to use it. However, considering that our ultimate implementation list should save any type of data, if the customized type is abnormal, the list status cannot be recovered when the function exits the copy constructor. That is to say, this interface is not an unusual interface. Consider this, or divided into two separate interfaces.
Of course, you must make sure that the list is not empty before using POP_FRONT and Front:
Boolean EMPTY ()
{
Return beg == End;
}
If you put non-empty judgment into the Front, what should be returned for empty time? do not know. It is best to understand the risk of this situation yourself.
If there are multiple read threads, front () and pop_front (), EMPTY () require the same mutex to ensure thread synchronization. Push_back should not be called in the same thread with the previous interface above. If it is just such a written specification, it is also very easy in practical applications because it is not obliged to comply with this rule. So we can consider providing two different interfaces to read threads and writing threads, which use Adaptor mode, as follows:
Class Writelist
{
Private:
List & list;
PUBLIC:
WriteList (List & list): this.list (list) {}
Void push_back (int data) {list.push_back (data);}
}
Class readlist
{
Private:
List & list;
PUBLIC:
Readlist (List & List): this.list (list) {}
Void pop_front () {list.pop_front ();
INT front () {return list.front ();
Boolean Empty () {Return List.empty ();
}
Things to read data can only see Readlist, and write data can only see WRITELIST, you can prevent the user from misuse these four interfaces.
Let's consider the interface of the query list:
int size ()
{
INT size = 0;
ListNode * ptmp = beg;
For (ListNode * ptmp = beg; ptmp! = end; ptmp = ptmp.next, size);
Return size;
}
This operation requires access to data saved in memory space points to the memory, but the implementation of POP_FRONT can result in invalid zone, in order to ensure code security, all thread debug information need to output list size Use the same mutex with POP_FRONT, which makes both performance issues and inconveniences. Many times, write threads need to call this interface, such as when you want to limit the number of threads, or debug information. To resolve the lock, you can access the SIZE interface, you need to ensure that the NEXT data of the memory area of the deleted node is available, that is, the delete node only clears the data area saved by the node, and other data is available. If the memory area is not released, it is inevitably caused by memory leaks, and we can consider using these already released nodes to save the data written by PUSH_BACK. A looping list can solve this problem.
Struct ListNode
{
Int data;
ListNode * Next;
ListNode (int V, listNode * pnext = 0): DATA (V), Next (PNEXT) {}
}
Struct List
{
ListNode * Beg;
ListNode * End;
List (): Beg (New ListNode (0)), End (BEG) {end-> next = end;
...
}
First constructed a loop table, when Push_BACK is not previously not released, add the new element to the end, still maintain the structure of the loop table:
Void Push_Back (int DATA)
{
END-> DATA = DATA;
IF (End-> Next == BEG) {
End-> Next = new listNode (0, end-> next);
}
End = end-> next;
}
During this process, the BEG pointer may be moved to the next bit, but there is no impact on the logic implemented here, and final logic is correct.
Void pop_front ()
{
IF (beg! = End) beg = beg-> next;
}
Also in this process, the END pointer may be written to the next bit, but there is no impact on the logic implemented here, and final logic is correct.
There is no change in the implementation of other interfaces:
int Front ()
{
Return beg-> data;
}
Boolean EMPTY ()
{
Return beg == End;
}
int size ()
{
INT size = 0;
ListNode * ptmp = beg;
ListNode * Pend = End;
For (ListNode * ptmp = beg; ptmp! = pend; ptmp = ptmp-> next, size);
Return size;
}
Note that the temporary variable is used during the implementation process to save the END pointer at the time. In order to prevent the other thread from insertion data from the Size execution, this loop cannot be terminated, so the value can be seen as a list. A snapshot data of time, and the list of true size after the Size function is executed, this is determined by the multi-threaded characteristics, which can be considered in this processing mode, which occurs. This error is acceptable.
You can add a SIZE interface for Writelist, Readlist. Multiple threads use WRITELIST (or Readlist) Then there is a need to lock the thread synchronization, but the interface of WriteList and Readlist can be used in multiple threads in multiple threads, and thread synchronization. Attachment is an actual code for reference.
/ ****************************** DEPT: TEST *** Author: htj ******** ******************* /
#ifndef circle_list_h # Define Circle_List_H
#include
template
} while (m_end! = End);} void push_back (const_reference v) {m_end-> assignvalue (v); if (m_beg == m_end-> next) {m_end-> next = allocate (m_end-> next); m_size;} m_end = m_end-> next;} BOOL EMPTY () const {return m_beg == m_end;} const_reference front () const {return m_beg-> value ();} refrest front () {return m_beg-> value (); Void pop_front () {if (m_beg! = M_end) {m_beg-> freevalue (); m_beg = m_beg-> next;}} size_type size () const {int RET = 0; node_pointer pend = m_end; for (Node_Pointer Beg = m_beg; beg! = m_end; RET, BEG = Beg-> Next); Return Ret;} size_type buffer_size () const {return m_size;} private: node_pointer m_end; node_pointer m_beg; size_type m_size; // do not understand the use of the allocator, the following expression is not compiled by // typedef typename allocator_type :: template rebind
struct ListNode {char buffer [sizeof (T)]; ListNode * next; ListNode (): next (this) {} explicit ListNode (ListNode * pnext): next (pnext) {} bool operator == (const ListNode & rhs) const {RETURN next == rhs-> next;} Bool Operator! = (Const listnode & rhs) const {return! (* This == rhs);} void freeValue () {value (). T :: ~ t (); } Void AssignValue (Const T & DATA) {new (data);} t & value () {return * (t *) buffer;} constit t & value () const {return * (t *) buffer;}} ;}; template
template
