无锁编程(三) - 忙等待

概念

忙等待可以认为是一种特殊的忙等待

忙等待分类

Peterson算法

xchg解法

TSL解法

自旋锁

Peterson算法

Peterson算法是一个实现互斥锁的并发程序设计算法,可以控制两个线程访问一个共享的单用户资源而不发生访问冲突。GaryL. Peterson于1981年提出此算法。

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/time.h>
#include <stdint.h>

int count = 0;
#define N 2
volatile int turn;   
volatile int interested[N] = {0}; 

void enter_region(int process)
{
	int other = 1 - process; //另一个进程  
	interested[process] = true;
	turn = process;
	while (turn == process && interested[other] == true) NULL; //一直循环,直到other进程退出临界区  
}

void leave_region(int process)
{
	interested[process] = false; 	// leave critical region
}

void *test_func(void *arg)
{
	int process = *((int *)arg);
	printf("thread %d run\n", process);
	int i=0;
	for(i=0;i<2000000;++i)
	{
		enter_region(process);
		//printf("%d enter, count = %d\n", pthread_self(),count);
		++count;
		leave_region(process);
	}
	return NULL;
}

int main(int argc, const char *argv[])
{
	pthread_t id[N];
	int process[N];
	int i = 0;

	uint64_t usetime;
	struct timeval start;
	struct timeval end;
	
	gettimeofday(&start,NULL);
	for(i=0;i<N;++i)
	{
		process[i] = i;
	}	
	
	for(i=0;i<N;++i)
	{
		pthread_create(&id[i],NULL,test_func,&process[i]);
	}

	for(i=0;i<N;++i)
	{
		pthread_join(id[i],NULL);
	}
	
	gettimeofday(&end,NULL);

	usetime = (end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-start.tv_usec);
	printf("count = %d, usetime = %lu usecs\n", count, usetime);
	return 0;
}

结果说明:

[root@rocket lock-free]#./busywait_peterson 

thread 0 run

thread 1 run

count = 3999851, usetime = 263132 usecs

可以看出,虽然是互斥算法,但是实测的结果缺不是十分精确,有少量的count丢失,这点让人感到很差异,这里先不去深究,有经验的同学可以帮忙分析一下原因。

xchg解法

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <sys/types.h>
#include <asm/system.h>
#include <sys/time.h>
#include <stdint.h>

volatile int in_using = 0;
int count = 0;
#define N 2

void enter_region()
{
	while (xchg(&in_using, 1)) NULL;
}

void leave_region()
{
	in_using = 0;	// leave critical region
}

void *test_func(void *arg)
{
	int i=0;
	for(i=0;i<2000000;++i)
	{
		enter_region();
		++count;
		leave_region();
	}
	
	return NULL;
}

int main(int argc, const char *argv[])
{
	pthread_t id[20];
	int i = 0;

	uint64_t usetime;
	struct timeval start;
	struct timeval end;
	
	gettimeofday(&start,NULL);
	
	for(i=0;i<N;++i)
	{
		pthread_create(&id[i],NULL,test_func,NULL);
	}

	for(i=0;i<N;++i)
	{
		pthread_join(id[i],NULL);
	}
	
	gettimeofday(&end,NULL);

	usetime = (end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-start.tv_usec);
	printf("count = %d, usetime = %lu usecs\n", count, usetime);
	return 0;
}

结果说明:这个结果自然是非常精确,感觉比peterson算法靠谱多了,性能倒是差别不大。

[root@rocket lock-free]# ./busywait_xchg

count = 4000000, usetime = 166548 usecs

TSL解法(Test and Set Lock)

enter_region:

tsl register, lock |复制lock到寄存器,并将lock置为1

cmp register, #0 | lock等于0吗?

jne enter_region |如果不等于0,已上锁,再次循环

ret |返回调用程序,进入临界区

leave_region:

move lock, #0 |置lock为0

ret |返回调用程序

自旋锁

自旋锁请参考我的另一篇文章,这里不再赘述。

https://cloud.tencent.com/developer/article/1020651  版权声明:本文为博主原创文章,未经博主允许不得转载。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏佳爷的后花媛

php统计查询,实时更新

在应用中我们经常会用到一些统计数据,例如当前所有(或者满足某些条件)的用户数、所有用户的最大积分、用户的平均成绩,用户的银行卡张数等等,ThinkPHP为这些统...

3523
来自专栏FreeBuf

SQL注入之骚姿势小记

写在前面 小记一下CTF那些日子和DROPS队友学到的SQL注入的骚姿势。 By 010 1、IN之骚 这个我也偶然发现的,也不知前辈们有没有早已总结好的套路了...

3456
来自专栏技术沉淀

命令行工具:awk文本处理

1673
来自专栏Danny的专栏

【SSH快速进阶】——Hibernate继承映射:每个具体类映射一张表

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1044
来自专栏JackieZheng

Nutch源码阅读进程2---Generate

继之前仓促走完nutch的第一个流程Inject后,再次起航,Debug模式走起,进入第二个预热阶段Generate~~~ 上期回顾:Inject主要是将爬取列...

1957
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版6.5节虚函数的coredump例子

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

800
来自专栏Jed的技术阶梯

Hive窗口函数01-SUM、MIN、MAX、AVG

order by : 在同一个组内,先累加完相同createtime的pv,再累加其他createtime的pv, 比如 : 现在在表末尾加一条数据cooki...

2883
来自专栏小樱的经验随笔

BZOJ 1293: [SCOI2009]生日礼物【单调队列】

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2534  Solv...

2605
来自专栏鸿的学习笔记

records包源码解析

核心类有三个 Record, RecordCollection, Database。在做源码分析时,先从入口类Database开始:

712
来自专栏marsggbo

Udacity并行计算课程笔记-The GPU Hardware and Parallel Communication Patterns

本小节笔记大纲: 1.Communication patterns gather,scatter,stencil,transpose 2.GPU hardwa...

2216

扫码关注云+社区