锁与原子操作CAS的底层实现

线程

1：线程就是程序的执行路线，即进程内部的控制序列，或者说是进程的子任务。

2：一个进程可以同时拥有多个线程，即同时被系统调度的多条执行路线，但至少要有一个主线程。

3： 一个进程的所有线程都共享进程的代码区、数据段、BSS段、堆、命令行参数和环境变量，唯有栈区是一个线程一个。

4：一个进程的所有线程共享系统内核中与进程有关的部分资源，如文件描述符表、信号处理函数、工作目录、各种ID等。

5：一个进程的每个线程都有一个独立的ID(线程ID)、独立的寄存器上下文、独立的调度策略和优先级、独立的信号掩码、独立的errno以及线程私有数据。

线程调度

系统内核中专门负责线程调度的处理单元被称为调度器。调度器将所有处于就绪状态（没有阻塞于任何系统调用上）的线程拍成一个队列，即所谓就绪队列。调度器从就绪队列中获取队首线程，为其分配一个时间片，并令CPU执行该线程，过了一段时间：

1：该线程的时间片耗尽，调度器立即终止该线程，并将其排列到就绪队列的尾端，接着从队首获取下一个线程。

2：该线程的时间片未耗尽，但需阻塞于某系统调用，比如等待I/O或者睡眠。调度器会被终止该线程，将其从就绪队列移至等待队列，直到其等待的条件满足后，在被移回就绪队列。

3：在低优先级线程执行期间，有高优先级线程就绪，后者会抢占前者的时间片。若就绪队列未空，则系统内核进入空闲状态，直至其非空

时间片

调度器分配给每个线程的时间片长短，对系统的行为和性能影响很大。如果时间片过长，线程必须等待很长时间才能重新获得处理机，这就降低了整个系统的并行性，用户会感觉到明显的响应延时。如果时间片过短，大量时间会浪费在线程切换上，同时降低了虚拟内存的存储命中率，线程的时间局部性无法得到保证。某些UNIX系统倾向于为线程分配较长的时间片，希望通过扩大系统吞吐率来改善其整体表现；而另一些UNIX系统则更倾向于为线程分配较短的时间片，以提升系统的交互性，Linux系统根据线程在不同时间的具体表现，为其动态分配时间片，在吞吐率和交互性之间寻求最佳平衡点。

处理及约束和I/O约束

1：一些线程总是持续地消耗掉分配给它们的全部时间片，比如那些专门负责科学计算、图像处理等任务的线程。这些线程被称为处理机约束型线程。它们通常可以得到较长的时间片，通过提高虚拟内存的存储命中率。保证线程的时间局部性，以尽可能快的速度完成任务。

2：另一些线程则多数时间处于为等待资源而阻塞的状态，比如那些专门负责文件读写、网路通信或者人机交互的线程。这些线程被称为I/O约束型线程。它们通常只能得到较短的时间片，因为它们在发出I/O请求并阻塞于内核资源之前，只会运行很短的时间。

3：另一方面，调度器又会适度降低处理机约束型线程的优先级，同时提高I/O约束型线程的优先级，于期间寻求平衡。

#include<pthread.h>                            POSIX线程库  libpthread.so ---> -lpthread

int pthread_equal(pthread_t tidl , pthread_t tid2); 若相等，返回非0，否则返回0。

pthread_t pthread_self(void);       返回调用线程的ID。

int pthread_create(pthread_t* tid , const pthread_attr_t* attr , void* (*start_rtn)(void*)

                             ,   void* arg);

1：pthread_create本身并不调用线程过程函数，而是在系统内核中开启独立的线程，并立即返回，在该线程中执行线程过程函数。

2：pthread_create函数返回时，所指定的线程过程函数可能尚未执行，也可能正在执行，甚至可能已经执行完毕。

3：如果主线程先于子线程结束，则由于进程的结束，所有的子线程都i会立即被终止。

4：主线程和通过pthread_create函数创建的多个子线程，在时间上“同时”运行，如果不附加任何同步条件，则它们每一个执行步骤的先后顺序是完全无法确定的，这就叫做自由并发。  

5：传递给线程过程函数的参数是一个泛型指针void* 它可以指向任何类型的数据：基本类型的变量，结构体类型的变量或者数组类型的变量等等，但必须保证在线程过程函数执行期间，该指针所指向的内存空间持久有效，直到线程过程函数不再使用它为止。

6：调用pthread_create函数的代码在用户空间，线程过程函数的代码也在用户空间，但偏偏创建线程的动作由系统内核完成。因此传递给线程过程函数的参数也不得经由系统内核传递给线程过程函数。pthread_create函数的arg参数负责将线程过程函数的参数带入系统内核。

#include>sys/syscall.h>

long int syscall(SYS_gettid)；   函数返回一个系统内核产生线程唯一标识。一个进程的PID其实就是它的主线程的TID。

线程终止

1：线程可以简单地从启动例程中返回，返回值是线程的退出码。

2：线程可以被同一进程中的其他线程取消。

3：线程调用pthread_exit。

void pthread_exit(void* rval_ptr)；

线程可以通过调用pthread_cancel函数来请求取消同一进程中的其他线程。

int pthread_cancel(pthread_t tid)；    

线程也可以安排它退出时需要调用的函数

void pthread_cleanup_push(void* (*rtn)(void*) , void* arg)；

void pthread_cleanup_pop(int excute)；

当线程执行以下动作时，清理函数rtn是由pthread_cleanup_pop调度的，调用时只有一个参数arg：

1：调用pthread_exit时。

2：响应取消请求时。

3：用非零execute参数调用pthread_cleanup_pop时。

如果execute参数设置为0，清理函数将不被调用。

汇合线程

int pthread_join(pthread_t tid , void** retval);      成功返回0，失败返回错误码，retval输出线程过程函数的返回值。

等待子线程终止，即其线程过程函数返回，并与之汇合，同时回收该线程的资源。

在父进程中调用pthread_join函数等待子线程的终止，并回收其资源。如果调用该函数时子线程已经终止，该函数会立即返回，如果调用该函数时子线程尚在运行中，该函数会阻塞，直至子线程终止。该函数在返回成功的同时通过其retval参数向调用或者输出子线程线程过程函数的返回值。

分离线程

int pthread_detach(pthread_t tid)；

一个线程在默认情况下都是可汇合线程，这样的线程在终止以后其资源会被保留，其中含有线程过程函数的返回值及线程ID等信息，父线程可以通过pthread_join函数获得线程过程函数的返回值，同时释放这些资源。如果在创建线程以后，对其调用pthread_detach函数并返回成功，该线程即成为分离线程，这样的线程终止以后其资源会被系统自动回收，不需要也无法通过pthread_join函数汇合它。

CPU亲缘性

互斥锁

对互斥量进行加锁以后，任何其他试图再次对互斥量加锁的线程都会被阻塞直到当前线程释放该互斥锁。如果释放互斥量时有一个以上的线程阻塞，那么所有该锁上的阻塞线程都会变成可运行状态，第一个变为运行的线程就可以对互斥量加锁，其他线程就会看到互斥量依然是锁着的，只能回去再次等待它重新变为可用。

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER   // 静态创建互斥锁

int pthread_mutex_init(pthread_mutex_t* mutex ,const pthread_mutexattr_t* attr) //动态创建互斥锁，  成功返回0，失败返回errno   attr:属性 ， 一般不用，填NULL缺省。

int pthread_mutex_destroy(pthread_mutex_t* mutex) // 动态销毁互斥锁 ，成功返回0  ， 失败返回errno

int pthread_mutex_lock(pthread_mutex_t* mutex);// 加锁互斥锁  ， 成功返回0 ，失败返回errno ， 存在锁冲突会阻塞。

int pthread_mutex_unlock(pthread_mutex_t* mutex); //解锁互斥锁，成功返回0，失败返回errno。

int pthread_mutex_trylock(pthread_mutex_t* mutex);// 尝试加锁，如果调用该函数时互斥量处于未锁住的状态，那么将锁住互斥量，不会阻塞直接返回0。否则就是失败，不能锁住互斥量，返回EBUSY。

条件变量

pthread_cond_t cond = PTHREAD_COND_INITIALIZER；//静态创建条件变量

int pthread_cond_init(pthread_cond_t* cond , const pthread_condattr_r* attr);// 动态创建条件变量

int pthread_cond_destory(pthread_cond_t* cond)；// 动态销毁条件变量。

int pthread_cond_wait(pthread_cond_t* cond , pthread_mutex_t* mutex);// 睡入条件变量

int pthread_cond_timedwait(pthread_cond_t* cond , pthread_mutex_t* mutex ,

const struct timespec* tsptr);                                       以上函数成功返回0，失败返回errno

我们使用pthread_cond_wait等待条件变量为真。如果在给定的时间内条件变量不能满足，那么会产生一个返回错误码的变量。传递给pthread_cond_wait的互斥量对条件进行保护。调用者把锁住的互斥量传给函数，函数然后自动把调用线程放到等待条件的线程列表上，对互斥量解锁。这就关闭了条件检查和线程进入休眠状态等待条件改变这两个操作之间的时间通道，这样线程就不会错过条件的任何变化。pthread_cond_wait返回时，互斥量再次被锁住。

pthread_cond_timedwait函数的功能与pthread_cond_wait函数相似，只是多了一个超时，超时值指定了我们愿意等待多长时间，这个时间是一个绝对值而不是相对值。例如，假设我们需要等待3分钟。那么，并不是把三分钟转换成timespec结构，而是需要把当前时间加上3分钟再转换成timespec结构。     可以使用gettimeofday()获取timeval结构表示当前时间，然后把这个时间转换成timespec结构。  如果超时到时期条件还没出现，pthread_cond_timewait将重新获取互斥量，然后返回错误ETIMEOUT。从pthread_cond_wait或者pthread_cond_timedwait调用成功返回时，线程需要重新计算条件，因为另一个线程可能已经在运行并改变了条件。

int pthread_cond_signal(pthread_cond_t* cond)；//   至少唤醒一个

int pthread_cond_broadcast(pthread_cond_t* cond)；//   唤醒全部

一个线程调用pthread_cond_wait函数进入阻塞状态，直到条件变量cond受到信号为止，阻塞期间互斥锁mutex会被释放。另一个线程通过pthread_cond_signal函数向条件变量cond发送信号，唤醒在其中睡眠的一个线程，该线程即从pthread_cond_wait函数返回，同时重新获得互斥锁mutex。

自旋锁

自旋锁与互斥量类似，但它不是通过休眠使进程阻塞，而是在获取锁之前一直处于忙等(自旋)的状态。自旋锁可用于以下情况：锁被持有的时间短，而且线程并不希望在重新调度上花费太多成本。

int pthread_spin_init(pthread_spinlock_t* lock , int pshared);

int pthread_spin_destroy(pthread_spinlock_t* lock);

                                                          成功返回0，否则返回errno。

只有一个属性是自旋锁特有的，这个属性只在支持线程进程共享同步选项的平台上才用得到。pshared参数表示进程共享属性，表明自旋锁是如何获取的。如果它设置为PTHREAD_PROCESS_SHARED，则自旋锁能被可以访问锁底层内存的线程所获取，即便那些线程属于不同的进程，情况也是如此。否则pshared参数设置为PTHREAD_PROCESS_PRIVATE，自旋锁就只能被初始化该锁的进程内部的线程所访问。

pthread_spin_lock(pthread_spinlock_t* lock)；//  在获得锁之前一直自旋。

pthread_spin_trylock(pthread_spinlock_t* lock)；// 如果不能获取锁，就立即返回EBUSY错误号。

pthread_spin_unlock(pthread_spinlock_t* lock)；// 不管一何种方式加锁，都可以调用这个函数解锁。

注意：如果自旋锁当前在解锁状态的话，pthread_spin_lock函数不要自旋就可以对它进行加锁。如果线程已经对它加锁了，结果就是为定义的。调用pthread_spin_lock会返回EDEADLK错误(或其他错误)，或者调用可能会永久自旋。具体行为依赖于实际的实现。试图对没有加锁的自旋锁进行解锁，结果也是未定义的。

不管是pthread_spin_lock还是pthread_spin_trylock，返回值为0的话就表示自旋锁被加锁。需要注意，不要调用在持有自旋锁的情况下可能会进入休眠状态的函数。如果调用了这些函数，会浪费CPU资源，因为其他线程需要获取自旋锁需要等待的时间就延长了。

读写锁

读共享，写独占。

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER；// 静态初始化

pthread_rwlock_init(pthread_rwlock_t* rwlock , const pthread_rwlockattr_t* attr); //

pthread_rwlock_destroy(pthread_rwlock_t* rwlock)；//  销毁

pthread_rwlock_rdlock(pthread_rwlock_t* rwlock)；//  加读锁

pthread_rwlock_wrlock(pthread_rwlock_t* rwlock)；// 加写锁

pthread_rwlock_unlock(pthread_rwlock_t* rwlock)；// 解锁

pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock)；

pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock)；

                                                            成功返回0 ， 失败返回错误码errno

原子操作

由于线程的切换

当cpu加载线程1的时候将线程1的寄存器上下文移动到cpu内然后执行指令，当cpu切换到线程2的时候会把当前的寄存器上下文先移动回原线程，然后加载线程2的寄存器上下文进入cpu进行指令操作。

"原子操作(atomic operation)是不需要synchronized"，这是多线程编程的老生常谈了。所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。

c++11提供的原子操作

共享内存

多进程情况：

#include<sys/mman.h>

建立虚拟内存到物理内存或磁盘文件的映射。

void* mmap(void* start, size_t length , int port , int flags , int fd , off_t offset);

成功返回映射区虚拟内存的起始地址，失败返回MAP_FALIED(-1)

start: 映射区虚拟内存的起始地址，NULL系统自动选定后返回。

length:映射区字节数，自动按页圆整。

port：映射区操作权限，可以取以下值：

               PORT_READ ---- 映射区可读

               PORT_WRITE ---- 映射区可写

               PORT_EXEC ---- 映射区可执行

               PORT_NONE ---- 映射区不可访问

对指定映射存储区的保护要求不能超过文件open的模式访问权限。

flags：映射标志，可以取以下值：

               MAP_ANONYMOUS | MAP_PRIVATE --- 虚拟内存到物理内存的映射。（映射的只是一个副本，对该内存的修改不影响原文件）

               MAP_SHARED --- 虚拟内存到磁盘文件的映射。

fd：文件描述符。（必须先打开该文件）

offset：文件偏移量，自动按页对齐。

解除虚拟内存到物理内存或磁盘文件的映射。

int munmap(void* start , size_t length)；

成功返回0 ，失败返回-1

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/mman.h>
#define THREAD_SIZE     10
int count = 0;
pthread_mutex_t mutex;
pthread_spinlock_t spinlock;
pthread_rwlock_t rwlock;
// MOV dest, src;  at&t
// MOV src, dest;  x86
int inc(int *value, int add) {
    int old;
    __asm__ volatile ( 
        "lock; xaddl %2, %1;" // "lock; xchg %2, %1, %3;" 
        : "=a" (old)
        : "m" (*value), "a" (add)
        : "cc", "memory"
    );
    return old;
}
// 
void *func(void *arg) {
    int *pcount = (int *)arg;
    int i = 0;
    while (i++ < 100000) {
#if 0
        (*pcount) ++;
#elif 0
        pthread_mutex_lock(&mutex);
        (*pcount) ++;
        pthread_mutex_unlock(&mutex);
#elif 0
        if (0 != pthread_mutex_trylock(&mutex)) {
            i --;
            continue;
        }
        (*pcount) ++;
        pthread_mutex_unlock(&mutex);
#elif 0
        pthread_spin_lock(&spinlock);
        (*pcount) ++;
        pthread_spin_unlock(&spinlock);
#elif 0
        pthread_rwlock_wrlock(&rwlock);
        (*pcount) ++;
        pthread_rwlock_unlock(&rwlock);
#else
        inc(pcount, 1);
#endif
        usleep(1);
    }
}
int main() {
#if 0
    pthread_t threadid[THREAD_SIZE] = {0};
    pthread_mutex_init(&mutex, NULL);
    pthread_spin_init(&spinlock, PTHREAD_PROCESS_SHARED);
    pthread_rwlock_init(&rwlock, NULL);
    int i = 0;
    int count = 0;
    for (i = 0;i < THREAD_SIZE;i ++) {
        int ret = pthread_create(&threadid[i], NULL, func, &count);
        if (ret) {
            break;
        }
    }
    for (i = 0;i < 100;i ++) {
        pthread_rwlock_rdlock(&rwlock);
        printf("count --> %d\n", count);
        pthread_rwlock_unlock(&rwlock);
        sleep(1);
    }
#else
    int *pcount = mmap(NULL, sizeof(int), PROT_READ | PROT_WRITE, MAP_ANON|MAP_SHARED, -1, 0);
    int i = 0;
    pid_t pid = 0;
    for (i = 0;i < THREAD_SIZE;i ++) {
        pid = fork();
        if (pid <= 0) {
            usleep(1);
            break;
        }
    }
    if (pid > 0) { // 
        for (i = 0;i < 100;i ++) {
            printf("count --> %d\n",  (*pcount));
            sleep(1);
        }
    } else { 
        int i = 0;
        while (i++ < 100000)  {
#if 0            
            (*pcount) ++;
#else
            inc(pcount, 1);
#endif
            usleep(1);
        }
    }
#endif 
}