接上回:linux编程的108种奇淫巧计-7(Lock-free实验)
本节增加test_and_set的原语和一个spinlock比较完整的实现(参照nginx spin lock),主要的变化在于插入了__asm__ ("pause")指令,且插入次数是尝试锁的次数的2次幂,有助于在减少重试次数,通过这一变化可以对比看出CPU100%占用的问题得到了缓解。test_and_set指令在未来的博客中还会继续提到,cas,tas,fetch_and_add是这一系列中需要使用的仅有的3条原子操作。
test_and_set的语义为传入一个地址将其无条件置1,并返回该地址值的原来值,如果原来是1,返回1,如果原来是非1,返回非1,这提供了一个关门的好处,如果变量是非1,在进入临界区以后,该变量自动关门,后面的尝试全部失败因为是while(tas(V)==1)的操作,在使用完临界区以后,将该值请零(reset),必然有一个会在spin的过程中拿到,但是这种调度是有偶然性的,因此可能会出现饥饿,而且并发数越多的情况下,越容易出现饥饿,spin的次数不易过大,本文指定为4096,该值可以根据实际环境调整,参见nginx源码。
以下是实验代码:
/*************************************************************************
//编译方法
//g++ test.cpp -o test_cas_imp -D CAS_IMP -lpthread
//g++ test.cpp -o test_cas_imp_all -D CAS_IMP_ALL -lpthread
//g++ test.cpp -o test_tas_imp -D TAS_IMP -lpthread
//g++ test.cpp -o test_tas_imp_all -D CAS_IMP_ALL -lpthread
/**************************************************************************
# i
nclude <stdio.h>
#include <pthread.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <syscall.h>
#if defined(__x86_64__)
#define ATOMICOPS_WORD_SUFFIX "q"
#else
#define ATOMICOPS_WORD_SUFFIX "l"
#endif
static inline bool compare_and_swap(volatile size_t *p, size_t val_old, size_t val_new)
{
char ret;
__asm__ __volatile__("lock; cmpxchg" ATOMICOPS_WORD_SUFFIX " %3, %0; setz %1"
: "=m"(*p), "=q"(ret)
: "m"(*p), "r" (val_new), "a"(val_old)
: "memory");
return (bool)ret;
}
static inline size_t fetch_and_add(volatile size_t *p, size_t add)
{
unsigned int ret;
__asm__ __volatile__("lock; xaddl %0, %1"
:"=r" (ret), "=m" (*p)
: "0" (add), "m" (*p)
: "memory");
return ret;
};
static inline int test_and_set(volatile int *s) /* tested */
{ int r;
__asm__ __volatile__(
"xchgl %0, %1 \n\t"
: "=r"(r), "=m"(*s)
: "0"(1), "m"(*s)
: "memory");
return r;
}
static inline int reset(volatile int *s)
{
*s = 0;
}
volatile size_t g_uCount;
pthread_mutex_t g_tLck=PTHREAD_MUTEX_INITIALIZER;
const size_t cnt_num = 10000000;
volatile int tas_lock = 0;
void* sum_with_cas_imp(void*)
{
for(int i=0;i< cnt_num;++i) {
for(;;) {
size_t u = g_uCount;
if(compare_and_swap(&g_uCount,u,u+1)){
break;
}
}
}
}
void* sum_with_tas_imp(void*)
{
for(int i=0;i< cnt_num;++i) {
while((test_and_set(&tas_lock))==1){}
++g_uCount;
reset(&tas_lock);
}
}
void* sum_with_cas_imp_all(void*)
{
for(int i=0;i < cnt_num;) {
for(;;)
{
size_t u = g_uCount;
if(compare_and_swap(&g_uCount,u,u+1)){
goto L1;
}
for(size_t n=1;n<4096;n<<=1){
for(size_t i=0;i<n;i++){
__asm__ ("pause") ;
}
u = g_uCount;
if(compare_and_swap(&g_uCount,u,u+1)){
goto L1;
}
}
syscall(SYS_sched_yield);
}
L1: ++i;
}
}
// reference:http://nginx.sourcearchive.com/documentation/0.7.59-1/ngx__spinlock_8c-source.html
void* sum_with_tas_imp_all(void*)
{
for(int i=0;i < cnt_num;++i) {
for(size_t n = 1;(test_and_set(&tas_lock))==1;n<<=1){
if(n<4096){
for(size_t i=0;i<n;i++){
__asm__ ("pause") ;
}
}
else{
syscall(SYS_sched_yield);
n = 1;
}
}
++g_uCount;
reset(&tas_lock);
}
}
void* sum(void*)
{
#ifdef CAS_IMP
sum_with_cas_imp(NULL);
#endif
#ifdef TAS_IMP
sum_with_tas_imp(NULL);
#endif
#ifdef CAS_IMP_ALL
sum_with_cas_imp_all(NULL);
#endif
#ifdef TAS_IMP_ALL
sum_with_tas_imp_all(NULL);
#endif
};
int main()
{
pthread_t* thread = (pthread_t*) malloc(10*sizeof( pthread_t));
for(int i=0;i<10;++i)
{
pthread_create(&thread[i],NULL,sum,NULL);
}
for(int i=0;i<10;++i)
{
pthread_join(thread[i],NULL);
}
printf("g_uCount:%d\n",g_uCount);
free( thread );
}
我搜了一下也有一些不错的文章供大家参考
(1)http://student.csdn.net/space.php?uid=45153&do=thread&id=7403
(2)http://www.ibm.com/developerworks/cn/linux/l-rwlock_writing/
分享到:
相关推荐
星火考研系列是针对准备研究生入学考试(简称考研)的学生提供的一种学习资源,其中的“巧计速计”方法是针对英语单词记忆的一种技巧性、高效的学习方法。艾宾浩斯记忆曲线则是心理学家赫尔曼·艾宾浩斯提出的理论,...
【巧计英语7000单词】是一种创新的英语词汇学习方法,旨在通过800个有趣且富有挑战性的句子帮助学习者记忆7000个英语单词。这种方法强调趣味性和实用性,使得学习过程不再枯燥乏味。这些句子涵盖了广泛的词汇,包括...
个省级行政区的名称和位置巧计PPT教案.pptx
试听巧计10000单词,杨金明 往年的参考资料,仅共参考
标题“小学数学数学故事小女儿巧计救父”讲述了一个智慧与解决问题能力的故事,通过一个小学数学问题展示了逻辑思维在日常生活中如何应用。这个故事的核心是利用数学知识解决实际问题,特别是涉及到数量、交易和条件...
速查巧计手册是一种便于携带和快速查找的工具书,它将大量的概念、公式、定理等信息进行分类整理,使得使用者能够迅速找到所需信息。在考研数学的复习过程中,这种手册可以大大提高复习效率,帮助考生在短时间内掌握...
标题提到的“英语谚语巧计单词700词汇任你掌握”暗示了一种通过学习英语谚语来记忆单词的方法。这种方法利用了谚语的韵律感和故事性,使单词的记忆过程变得有趣且易于接受。例如,“Anthropologists have discovered...
初中语文文摘历史苏军巧计“忽悠”希特勒
个省级行政区的名称和位置巧计.pptx
个省级行政区的名称和位置巧计学习教案.pptx
15.三数之和----双指针(三指针) 17.电话号码的字母组合----回溯 19.删除链表的倒数第N个节点----双指针 20.有效的括号----栈 21.合并两个有序链表----递归 22.括号生成----回溯 23.(hard)合并K个排序链表----...
9. **动词的过去式和过去分词**:学习并记住常用动词的不规则变化,如 "understand" (understood, understood), "hit" (hit, hit), "break" (broke, broken), "become" (became, become), "begin" (began, begun), ...
自己复习托福 才知道但背单词有多艰难 无论是词根式还是其他方法 这是我见到的最好的方法了 共享给大家
考研英语词汇巧计。20天内记住考研词汇,拥有去的故事记住考研英语单词
9. 应对考试的策略和心态调整: 考试是检验学习成果的一种方式,文件中提到了一些应对考试的策略,比如熟悉考试流程、加强记忆、找到适合自己的复习方法等。同时,保持良好的心态对于考试成功同样重要,包括调节紧张...
9. "32、数一数二数三的区别.pdf":解释了考研数学中数一、数二、数三的不同,这对于考生选择适合自己的考试类型和备考方向至关重要。 这些文档覆盖了考研数学复习的多个重要领域,从积分理论到概率统计,再到具体...
5. 错误的说法是C项,阎典史并未使用巧计,而是通过号召民众并提供武器,成功组织防御。 这份同步练习涵盖了语文学习中的基础知识、文言实词虚词的理解、文言句式分析以及文学常识等内容,旨在通过练习加深学生对...
二、设巧计迁都洛阳 1. 原因: - 政治:加强对中原地区的统治,平城(今山西大同)的地理位置不利于统治全局,保守势力阻碍改革。 - 经济:平城地处边远,粮食供应困难。 - 军事:与北方游牧民族临近,存在安全...
《考研数学概念公式定理手册》是一本为准备参加研究生入学考试的学生提供的数学参考书籍。这本手册主要涵盖了数学中的基本概念、重要的公式和定理,是考研数学复习的重要资料。由于内容都是通过OCR扫描获得,可能...
在描述中,“项目管理44个过程输入输出工具技术忆巧计法--项管考试通关秘笈”透露了项目管理工程师考试涉及的核心知识点。这44个过程是项目管理知识体系的核心组成部分,涵盖了从项目启动到项目结束的整个生命周期。...