# 无锁编程(三) - 忙等待

Peterson算法

xchg解法

TSL解法

### Peterson算法

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

```#include <stdio.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);
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[])
{
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)
{
}

for(i=0;i<N;++i)
{
}

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

count = 3999851, usetime = 263132 usecs

### xchg解法

```#include <stdio.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[])
{
int i = 0;

uint64_t usetime;
struct timeval start;
struct timeval end;

gettimeofday(&start,NULL);

for(i=0;i<N;++i)
{
}

for(i=0;i<N;++i)
{
}

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_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  版权声明：本文为博主原创文章，未经博主允许不得转载。

49 篇文章34 人订阅

0 条评论

## 相关文章

3523

3456

1673

1044

1957

800

### 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

712

2216