懒惰计数器 Lazy Counter

现代计算机的多处理器结构催生出一系列并发程序，为了更好地在多处理器上运行，要利用锁的机制，保护临界区，避免race condition导致程序出错。

因此锁的思想在整个并发编程中都比较适用，在更新critical section的时候先请求锁，更新完再释放。并发计数器也是同样的思想，只是为了更好利用多处理器、提高扩展性，并发计数器中以懒惰计数器为著名。

全局计数器维护真正的全局值，但是各个cpu上都运行着一个局部的计数器，局部之间自我通信，速度快到媲美单核性能（单个速度，多个局部加起来那就是单核的许多倍了）。只有当局部计数器达到一定的阈值时才会更新全局计数器。

 代码如下 C语言 Linux下编译:gcc -pthread lazycount.c -o lazycount.out  运行：./lazycount.out

#include <pthread.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h> /*srand && random*/
#include <time.h> /*time()*/
//懒惰计数器 可扩展性强 局部具有自己的锁 全局具有自己的全局锁
#define NUMOFCPU 40

#define COUNTERTIME 1000000

typedef struct counter_t {
    int global;
    pthread_mutex_t glock;
    int local[NUMOFCPU];    //维系局部的统计值
    pthread_mutex_t llock[NUMOFCPU];    //各个局部含有一个锁
    int threshold;  //局部向全局更新阈值
} counter_t ;

counter_t *lazy;//生命一个全局counter 创建多个线程来操作它

void init(counter_t *c, int threshold);

void update(counter_t *c, int tid,int amt);

int get (counter_t *c);

void * mythread(void * arg) ;


int main(int argc, char *argv[]) {
	srand((unsigned int) time(NULL));
    lazy = (counter_t *)malloc(sizeof(counter_t));
    init(lazy, 1000);
    pthread_t p[NUMOFCPU];
    for(int i = 0; i < NUMOFCPU; i++) {
        pthread_create(&p[i], NULL, mythread, &i);
    }
     for(int i = 0; i < NUMOFCPU; i++) {
        pthread_join(p[i], NULL);
    }
    printf("global is %d\n", lazy->global);
}

void * mythread(void * arg) {
    int *tid = (int *) (arg);
    int temp = 0;
    //进行计数
    for(int i = 0; i < COUNTERTIME; i++) {
        temp = random() % 17;
        update(lazy, *tid, temp);
    }
}



//init 为全局和局部都设置自己的锁
void init(counter_t *c, int threshold) {
    c->global = 0;
    assert(pthread_mutex_init(&c->glock, NULL)==0);
    for(int i = 0; i < NUMOFCPU; i++) {
         c->local[i] = 0;
         assert(pthread_mutex_init(&c->llock[i], NULL) == 0);
    }
    c->threshold = threshold;
}


//update 更新指定pid线程局部的值 如果到达阈值则更新全局的值
void update(counter_t *c, int tid,int amt) {
    pthread_mutex_lock(&c->llock[tid]);
    c->local[tid] += amt;
	printf("Local Update : %d \n", amt);
    if(c->local[tid] >= c->threshold) {
        pthread_mutex_lock(&c->glock);
        c->global += c->local[tid];
		printf("Global Update : %d \n", c->local[tid]);
        pthread_mutex_unlock(&c->glock);
        c->local[tid] = 0;//局部置零
    }
    pthread_mutex_unlock(&c->llock[tid]);
}

//get 获取global值
int get (counter_t *c) {
    pthread_mutex_lock(&c->glock);
    int val = c->global;
    pthread_mutex_unlock(&c->glock);
    return val;
}

 运行效果如下：