Linux Kernel Synchronization && Mutual Exclusion、Linux Kernel Lock Mechanism Summarize(undone)

1. 同步与互斥
2. 锁定内存总线原子操作
3. 信号量
4. 自旋锁
5. RCU机制
6. PERCPU变量

http://www.cnblogs.com/LittleHann/p/3867214.html

int request_printer()
{
    while (printer == 0)
        wait();
    printer--;
    ...
{

# printer--
movl printer %eax
decl %eax
movl %eax printer

1. 锁定内存总线原子操作
2. 信号量
3. 自旋锁
4. RCU机制
5. PERCPU变量

深入linux内核架构(中文版).pdf 2.3章 同步与互斥
http://blog.csdn.net/lucien_cc/article/details/7440225

# printer--
lock decl printer

1. atomic_add
2. atomic_sub
3. atomic_xchg
4. atomic_inc
5. atomic_dec
6. atomic_cmpxchg
7. atomic_min
8. atomic_max
9. atomic_and
10. atomic_or
11. atomic_xor    
12. atomic_read

static inline void atomic_dec(atomic_t *v)
{
    asm volatile(LOCK_PREFIX "decl %0" : "+m" (v->counter));
}

1. 在多CPU系统中，使用lock前缀保证CPU间的数据一致性
2. 使用由CPU微指令组成的原子操作进行读取、增、减

1. P(Prolagen)操作：对应于内核中的down()
2. V(Verhogen)操作：对应于内核中的up()
//它们统称PV原语

struct semaphore 
{
    //1. 信号量
    raw_spinlock_t          lock;

    //2. 等待该信号量的进程个数
    unsigned int            count;

    //3. 该信号量的等待队列
    struct list_head        wait_list;
};

void down(struct semaphore *sem)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&sem->lock, flags);
    if (likely(sem->count > 0))
        sem->count--;
    else
        __down(sem);
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}

void up(struct semaphore *sem)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&sem->lock, flags);
    if (likely(list_empty(&sem->wait_list)))
        sem->count++;
    else
        __up(sem);
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}

1. 将信号量的值减1
2. 如果信号量的值小于0，则进入等待状态，否则继续执行。访问完资源之后，线程释放信号量，进行如下操作
3. 将信号量的值加1
4. 如果信号量的值小于1，唤醒一个等待中的线程

1. 关闭中断：通过cli指令清除标志寄存器中的中断允许位，即关闭中断
2. 开启中断：通过sti指令开启中断

1. 信号量引起的进程切换消耗相对较大，由于这类"临界"代码的特征是执行时间非常短暂，也就是说CPU执行信号量进程切换的消耗远远大于"临界"代码本身执行的消耗。
所以，在这种情况下，让另一个CPU进入"忙等待"状态，直到临界代码操作完成

2. 由于信号量可能引起进程切换，但是在某些环境下，是不允许进程切换的，例如
    1) 中断环境中是不允许进程切换的，否则会引起panic

1. 设置一个锁变量，用来保护临界区代码
2. 当CPU进入临界区之前，检查锁的状态
3. 如果已经上锁，则当前CPU(或者是单CPU模拟出的多线程)执行一个"空循环"反复检测锁的状态，直到其他的CPU(或者是单CPU模拟出的其他线程)
4. 由于在测试锁的期间，CPU处于忙等待状态的"自旋"状态，因此把这种机制称为自旋锁

typedef struct raw_spinlock 
{
    arch_spinlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
    unsigned int break_lock;
#endif
#ifdef CONFIG_DEBUG_SPINLOCK
    unsigned int magic, owner_cpu;
    void *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map dep_map;
#endif
} raw_spinlock_t;

# define raw_spin_lock_init(lock)                    do { *(lock) = __RAW_SPIN_LOCK_UNLOCKED(lock); } while (0)

static inline void __raw_spin_lock_irq(raw_spinlock_t *lock)
{
    //关闭本地CPU的IRQ中断响应
    local_irq_disable();

    /*
    关闭进程抢占，由于中断或系统调用之后，可能会调度其他的进程运行(例如当前进程的时间片用完，或者有一个拥有更高优先级的进程已经进入就绪状态)，preempt_disable关闭调度器这个功能，从而保证当前进程在执行临界区代码的过程中不会被其他进程干扰
    */
    preempt_disable();
    spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);

    /*
    关闭中断，这是一个宏，经过层层翻译后最终调用一条汇编指令
    /source/arch/x86/include/asm/irqflags.h
    static inline void native_irq_disable(void)
    {
        asm volatile("cli": : :"memory");
    }
    */
    LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
    short inc = 0x0100;

    asm volatile (
        //锁住内存总线
        LOCK_PREFIX "xaddw %w0, %1\n"
        "1:\t"
        
        //如果lock->lock == 0，则说明成功获取到了这个自旋锁，跳转到标号2，成功退出
        "cmpb %h0, %b0\n\t"
        "je 2f\n\t"

        //否则进入"自旋状态"，执行nop指令，并测试lock->slock是否为0
        "rep ; nop\n\t"
        "movb %1, %b0\n\t"
        /* don‘t need lfence here, because loads are in-order */
        "jmp 1b\n"
        "2:"
        : "+Q" (inc), "+m" (lock->slock)
        :
        : "memory", "cc");
}

/*
在单CPU下该函数展开为一个空操作
*/

1. 某段代码在调用spin_lock_irq()之前需要关闭中断，之后获取了某个自旋锁，退出临界区后，再释放自旋锁
2. 在释放自旋锁时，spin_unlock_irq()开启了中断，然而该段代码此时可能根本不允许开启中断
3. 因此我们需要在调用申请自旋锁时保存当时的中断许可状态，在释放自旋锁时恢复之前的状态，而不是盲目地开启中断

/*
由于中断许可位位于CPU的标志寄存器中，因此spin_lock_irqsave()在获取自旋锁之后，把标志寄存器的值保存到flags中，而spin_unlock_irqrestore()在释放自旋锁之后，根据flags恢复标志寄存器
*/
#define spin_lock_irqsave(lock, flags)                          do {                                    raw_spin_lock_irqsave(spinlock_check(lock), flags);        } while (0)

static inline void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags)
{
    raw_spin_unlock_irqrestore(&lock->rlock, flags);
}

spin_lock_irqsave(...);
//some code to do somethings
spin_unlock_irqrestore(...);

http://blog.csdn.net/hustyangju/article/details/40391815
http://www.ibm.com/developerworks/cn/linux/l-cn-spinlock/
http://www.searchtb.com/2011/01/pthreads-mutex-vs-pthread-spinlock.html
http://blog.csdn.net/zhanglei4214/article/details/6837697

深入linux内核架构(中文版).pdf 35 page

深入linux内核架构(中文版).pdf 39 page