#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <iostream>
#include <sys/time.h>
#include <pthread.h> using namespace std; #define MAXLEN 200000 #define NUM_THREADS 8 #define CAS __sync_bool_compare_and_swap
#define FAA __sync_fetch_and_add
#define FAS __sync_fetch_and_sub
#define VCAS __sync_val_compare_and_swap struct node{
int num;
node * next;
node(int i, node* n) :
num(i), next(n)
{}
}; struct list{
node *head;
node *tail;
pthread_mutex_t lock;
int count;
}; void init(list *plist)
{
node *tmp = new node(0, NULL);
plist->head = tmp;
plist->tail = tmp;
plist->count = 0;
pthread_mutex_init(&(plist->lock), NULL);
} int enque_lock(list *plist, int num)
{
node *tmp = new node(num, NULL);
pthread_mutex_lock(&(plist->lock)); plist->tail->next = tmp;
plist->tail = tmp;
plist->count++;
pthread_mutex_unlock(&(plist->lock));
return 0;
}
int enque(list *plist, int num)
{
node *p = NULL;
node *tmp = new node(num, NULL);
do
{
p = plist->tail;
} while (CAS(&(p->next), NULL, tmp) == false);
CAS(&(plist->tail), p, tmp); FAA(&(plist->count), 1);
return 0;
} void deque(list *plist)
{
node *tmp = NULL;
do{
tmp = plist->head;
if (plist->head == plist->tail)
{
printf("err\n");
return;
}
} while (CAS(&(plist->head), tmp, tmp->next) == false);
FAS(&(plist->count), 1);
delete tmp;
return;
} void *SendMsg(void* p)
{
struct timeval tv_begin, tv_end;
gettimeofday(&tv_begin, NULL);
int i = 0;
while (i++ < MAXLEN)
{
enque((list*)p, i);
}
gettimeofday(&tv_end, NULL);
long timeinterval = (tv_end.tv_sec - tv_begin.tv_sec) * 1000000 + (tv_end.tv_usec - tv_begin.tv_usec);
printf("cost %llu us\n", timeinterval);
} void *SendMsg2(void* p)
{
struct timeval tv_begin, tv_end;
gettimeofday(&tv_begin, NULL);
int i = 0;
while (i++ < MAXLEN)
{
enque_lock((list*)p, i);
}
gettimeofday(&tv_end, NULL);
long timeinterval = (tv_end.tv_sec - tv_begin.tv_sec) * 1000000 + (tv_end.tv_usec - tv_begin.tv_usec);
printf("cost %llu us\n", timeinterval);
} int main(void)
{
int rc, i;
pthread_t thread[NUM_THREADS];
list ll;
init(&ll);
for (i = 0; i < NUM_THREADS; i++)
{
printf("Creating thread %i\n", i);
rc = pthread_create(&thread[i], NULL, SendMsg, (void*)&ll);
if (rc)
{
printf("ERROR; return code is %d\n", rc);
return -1;
}
} for (i = 0; i < NUM_THREADS; i++)
{
pthread_join(thread[i], NULL);
} while (ll.count > 0)
{
deque(&ll);
} for (i = 0; i < NUM_THREADS; i++)
{
printf("Creating thread %i\n", i);
rc = pthread_create(&thread[i], NULL, SendMsg2, (void*)&ll);
if (rc)
{
printf("ERROR; return code is %d\n", rc);
return -1;
}
} for (i = 0; i < NUM_THREADS; i++)
{
pthread_join(thread[i], NULL);
}
return 0;
}

   The test results are as follows :

Creating thread 0
Creating thread 1
Creating thread 2
Creating thread 3
Creating thread 4
Creating thread 5
Creating thread 6
Creating thread 7
cost 227839 us
cost 228055 us
cost 228034 us
cost 228179 us
cost 228274 us
cost 228328 us
cost 228413 us
cost 228433 us
Creating thread 0
Creating thread 1
Creating thread 2
Creating thread 3
Creating thread 4
Creating thread 5
Creating thread 6
Creating thread 7
cost 486283 us
cost 487499 us
cost 488358 us
cost 488677 us
cost 489118 us
cost 489658 us
cost 489657 us
cost 489735 us

Locked version Time consuming It takes twice as much time as the lockless version

Use CAS Achieve lock free formation - More related articles on linked lists

  1. Use CAS Achieve lock free SkipList

    unlocked The most common synchronization methods in concurrent environment are mutex and read-write lock , for example pthread_mutex and pthread_readwrite_lock, The common paradigm is : void ConcurrencyOperation() ...

  2. CAS Implement lockless mode

    Using multithreading to realize the self growth of a number to 1000000, The code is implemented in lock free mode and lock mode respectively . 1. Use ReentrantLock. package test; import java.util.concurren ...

  3. be based on CAS Implementation of lock free structure

    Yang Qiancheng 2017310500302 One . Subject requirements be based on CAS(Compare and Swap) Implement a lock free structure , Consider queue,stack,hashmap,freelist etc. . Can support multiple threads with ...

  4. CAS And Lockless queue

    http://coolshell.cn/articles/8239.html http://www.tuicool.com/articles/VZ3IBv http://blog.csdn.net/r ...

  5. lock 、CAS Operation and implementation of lock free queue

    https://blog.csdn.net/yishizuofei/article/details/78353722 Lock mechanism Locks are like people , Some people are optimistic , Always think of the good side , So as long as you work harder , The luckier : ...

  6. CAS Atomic operation to achieve no lock and performance analysis

    CAS Atomic operation to achieve no lock and performance analysis Author:Echo Chen( Chen Bin ) Email:chenb19870707@gmail.com Blog:Blog.csdn.net/chen19870707 ...

  7. DPDK Lockless queue Ring Library principle ( Learning notes )

    Reference from DPDK The original official document :http://doc.dpdk.org/guides-20.02/prog_guide/ring_lib.html For their own understanding to do some auxiliary explanation . 1 Pre knowledge 1.1 ...

  8. And asynchronous algorithms CAS(Compare and Swap) No lock algorithm

    lock (lock) The price of Locks are the easiest way to do concurrency , Of course, the cost is also the highest . When locking in kernel mode, the operating system needs a context switch , Lock . Releasing lock will lead to more context switching and scheduling delay , The thread waiting for the lock is suspended until the lock is released . ...

  9. CAS Lock free algorithm and ConcurrentLinkedQueue

    CAS:Compare and Swap Compare and exchange java.util.concurrent The package is built entirely on CAS Above , No, CAS There is no contract . And with the help of CAS Lock free algorithm is different from synchroni ...

Random recommendation

  1. Nodejs express Upload files

    Upload files Let's create a form for uploading files , Use POST Method , Forms enctype Property is set to multipart/form-data. index.htm The file code is modified as follows : <html ...

  2. Hadoop: operation Hadoop Cluster

    start-up Hadoop When all the necessary configuration is complete , take HADOOP_CONF_DIR Copy all configuration files in the directory to all machines , It is suggested that HDFS and YARN The background process runs as a different user , Like running HDFS The users of the processes are hdf ...

  3. [stm32] A simple stm32vet6 drive 2.4 " 240X320 Of 8 Bit parallel port tft screen DEMO

    The book follows : I've been working on low speed . low RAM Single chip microcomputer to drive small LCD or TFT Color screen to achieve animation effect First of all, I use one 16MHz Crystal m0 Kernel 8 Bit MCU nRF51822 Try to drive a 1.77 " 4 Line SPI screen (128X16 ...

  4. HTML Basics -- label 、 form

    <html>    -- The start tag <head> Control information on the web page <title> The page title </title> </head> <body& ...

  5. Appnium Research on mobile automation framework

    author :cryanimal QQ:164166060 This article briefly introduces appnium Architecture of automation framework . Loading process . Support language . Related configuration , And element positioning tools . Official website : http://appium.io Ap ...

  6. Windows Complete the port network model

    GetQueuedCompletionStatus   For example, what is done on the port at this time , What's the data , also , How can the system automatically fill in the above structure , in other words , How does the system know it's in Overlap->OpCode ...

  7. ListCtrl Control coloring

    I'm writing a fake anti-virus software recently , The general function has been realized , There are still some small links that need to be refined . among , In interface programming , It's used to give ListCtrl Control coloring , I checked some articles on the Internet , At last . In fact, it's plain , The principle is simple , Namely Li ...

  8. Error : APP-FND-01926: The custom event WHEN-LOGON-CHANGED raised unhandled exception: ORA-06502: PL

    In this Document   _afrLoop=440418974213449&id=1508865.1&_afrWindowMode=0&_adf.ctrl-stat ...

  9. About MySQL&#160;5.6.24&#160; After the decompressed version reboots the computer , Can't start problem

    Recent projects need to use mysql, Remember that I installed it before , There should be no problem . I don't know if it's a software upgrade problem , Or the copyright issue , Internet search msi Version of mysql It's hard to install , Start by installing .NET, I can not bear it. , And then you have to install Visu ...

  10. canvas-arc.html

    <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...