并发控制与竞态:

并发控制与竞态:
 并发是指多个单元同时、并行被执行，而并发执行单元对共享资源的访问
 很容易导致竞态。
 竞态的解释:
  假设有一个设备，执行单元A对其写入3000个字符'a'而另一个执行单元B对
  其写入4000个'b'，第三个执行单元C读取globalmem的所有字符，如果执行单元A
  、B对于设备的写入操作同时发生，此时就会造成竞态
  
  
 竞争状态的分类:
 1.对称多处理器(SMP)的多个CPU
  SMP是一种紧耦合、共享存储的系统类型，因为多个CPU同时共享系统总线，因此可以访问共同的外设和存储器
  SMP结构示意图:
 2.单CPU内进程与抢占它的进程
  Linux2.6支持内核抢占调度,一个进程在内核执行的时候可能被另一个高优先级的进程
  打断，进程与抢占它的进程访问共享资源时会发生竞争
 3.中断(硬中断、软中断、Tasklet、底半部)与进程之间
  中断可以打断重在执行的进程、如果中断处理程序访问进程正在访问的资源、此时静态会发生
  此外中断被更高级的中断打断时也会发生
 
  
  
 竞态的解决方法是:保证对共享资源的互斥访问(即一个执行单元在访问共享资源时，其他的执行
  单元被禁止访问)
  访问共享资源的代码区域被称为临界区(critical sections),临界区需要被以某种
  互斥机制加以保护。
  Linux常见互斥机制:中断屏蔽、原子操作、自旋锁和信号量等是Linux设备驱动中科采用的互斥路径
  

  
  
  
中断屏蔽:
 我们知道，中断会引起竞态。
 为了面这种事情的发生一种简单而有效的事情就是，在进入临界区之前屏蔽系统中断，
 这样就不必在担心在进入临界区后被中断打断。
 
 实质:中断屏蔽将使进程之间的并发不再发生，而且，由于Linux内核的进程调度等操作都依赖于
 中断，所以屏蔽中断后其实就相当于避免了进程之间的并发
 /*中断屏蔽的方法*/
 local_irq_disable()/*屏蔽中断*/
 ...
 critical section /*临界区*/
 ...
 local_irq_enable()/*打开中断*/
 
 需要注意的是上述两个函数都只能禁止和使能本CPU内的中断。
 这也就是说，这种方法不能解决多CPU(SMP)引发的竞态
 
 
 /*另外两个函数*/
 local_irq_save(flags)//屏蔽中断并且保存目前CPU的中断位信息
 ...
 critical section /*临界区*/
 ...
 local_irq_restore(flags)//打开中断，恢复原先CPU中断信息
 
 
 
 /*另外两个函数(只针对中断底半部的禁止和打开)*/
 local_bh_disable()
 
 local_bh_enable()
 
 
   这里简述一下Linux中断的底半部机制:
    Linux系统吧中断处理分为定半部和底半部
    Linux上半部只处理中断框架流程和紧急事件，
    例如对硬件设备的访问、或者修改由设备和处理器同时访问的数据，
    以及修改哪些只有处理器才可以访问的数据结构.
    
    
    
    
 
原子操作:
 性质:原子操作是指在执行过程中不会被代码路径所中断的操作。
 作用:从它的性质上我们就可以推算出它的功能:主要用作内核计数
 分类:位变量原子操作和整型变量原子操作
 
 整型原子操作:
  1.设置原子变量的值
  void atomic_set(atomic_t *v,int i);/*设置原子变量v的值为i*/
  atomic_t_v = ATOMIC_INIT(0);/*定义原子变量v并初始化为0*/
  2.获取原子变量的值
  atomic_read(atomic_t *v);/*返回源自变量的值*/
  3.原子变量的加减
  void atomic_add(int i,atomic_t *v);/*原子变量增加i*/
  void atomic_sub(int i,atomic_t *v);/*原子变量减少i*/
  4.原子变量自增/自减
  void atomic_inc(atomic_t*v);/*原子变量增加一*/
  void atomic_dec(atomic_t*v);/*原子变量减少一*/
  5.操作并测试
  int atomic_inc_and_test(atomic_t *v);
  int atomic_dec_and_test(atomic_t*v);
  int atomic_sub_and_test(atomic_t*v);
  6.操作并返回
  int atomic_add_return(int i.atomic_t *v);
  int atomic_sub_return(int i,atomic_t *v);
  int atomic_inc_return(atomic_t *v);
  int atomic_dec_return(atomic_t *v);
  
  
 位原子操作
  1.设置位
  void set_bit(nr,void *addr);/*设置addr地址的第nr位为1*/
  2.清楚位
  void clear_bit(nr,void *addr);/*设置addr地址的第nr位为0*/
  3.改变位
  void change_bit(nr,void *addr);/*对addr地址的第nr位进行反置*/
  4.测试位
  test_bit(nr,void *addr);/*返回addr地址的第nr位*/
  5.测试并操作位
  int test_and_set_bit(nr,void *addr);
  int test_and_clear_bit(nr,void *addr);
  int test_and_change_bit(nr,void *addr);
  
  
  下面就演示一个实例来利用原子变量实现设备在同一时刻只能由一个进程的打开
  static atomic_t xxx_available = ATOMIC_INIT(1);/*定义并初始化原子变量为1*/
  
  static int xxx_open(struct inode*inode,struct file *filp)
  {
   ...
   if(!atomic_dec_and_test(&xxx_available)){//如果该原子减1后不为0，说明该设备已经被以进程打开
    atomic_inc(&xxx_available);//将刚才减去的一加上
    return -EBUSY;/*已经打开*/
    }
    ...
   return 0;/*成功*/
   
  }
  
  
  static int xxx_release(struct inode*inode,struct file *filp)
  {
   atomic_inc(&xxx_available);/*释放设备*/
   return 0;
  }
 
 
 
自旋锁:
 前面介绍过，要防止静态现象的发生，就要使线程对临界区对象进行互斥访问；
 
 自旋锁定义:自旋锁是一种典型的对临界区对象进行互斥访问的手段。
 机制简介:前面我们已经讲过了原子操作，原子操作时一种不能被别代码路径打断的操作。
 我们在进入临界区之前首先要进行一个原子操作(测试原子变量)，如果测试结果表明
 资源已经没有被占用(即锁锁空闲)，则程序获取这个自旋锁(相当于该程序在进入临界区后将进入该临界区的大门关闭)
 ，否则程序将不停的在原地重复测试，这也就是为什么叫它“自旋锁”。
 
 
 1.自定义自旋锁:
 spinlock_t lock;
 2.初始化自旋锁
 spin_lock_init(lock);
 //该宏用于动态初始化自旋锁lock。
 3.(1)获得自旋锁
 spin_lock(lock)
 //用于获得自旋锁lock，如果能够获得锁，它就马上返回，否则他将自选在那里，
 直到该自旋锁的保持者释放。
   (2)尝试获取自旋锁
 spin_trylock(lock)
 //如果能获得自旋锁Lock就立即获得锁，并返回帧，否则返回假，而并不原地等待
 4.释放自旋锁
 spin_unlock(lock)
 
 
 
 自旋锁的简单使用：
 /*定义一个自旋锁*/
 spinlock_t lock;
 spin_lock_init(&lock);
 
 
 spin_lock(&lock);/*等待直到获取自旋锁，保护临界区*/
 .../*临界区*/
 spin_unlock(&lock); /*解锁*/
 
 
 一般应用范围:主要针对SMP或单CPU(内核抢占)的情况。对于单CPU和内核不支持抢占的系统，自旋锁退化为
 空操作;
 
 
 注意普通的自旋锁只能保证临界区不受别的CPU和本CPU和本CPU内的抢占进程打扰，但是得到锁
 的代码路径在执行临界区的时候还可能受到中断和底半部( BH)的映像。
 为了解决这个问题就需要在spin_lock(&lock)和unspin_lock(&lock)上衍生出新的自选锁机制
 

整套的自旋锁机制:
 spin_lock_irq() = spin_lock()+local_irq_disable()
 spin_unlock_irq() = spin_unlock()+local_irq_enable()
 spin_lock_irqsave() = spin_lock()+local_irq_save()
 spin_unlock_irqrestore() = spin_unlock()+local_irq_restore()
 
 
自旋锁所带来的问题:
 1.自旋锁是忙等待，当锁不可使用的时候,CPU将会不停的测试该自旋锁直到该锁可以使用。而
 CPU在等待自旋锁时不会做任何有用的工作，因此只有在占用所的时间很少的情况下使用它才是合理的
 如果临界区过大，需要长时间占用锁，这样就降低了系统性能
 
 2.可能导致死锁，例如:当某个CPU已经拥有了自旋锁A，但是它又一次的想要获得这个A，这是就导致了死锁
 3.自旋锁锁定期间不能再调用那些可能引起进程调度的函数。
  例如:一进程再获取自旋锁之后，因为调用这些函数copy_xx_user()\kmalloc()\msleep()则可能导致内核崩溃
  
 
 
 /*普通自旋锁使用实例*/
 int xxx_count = 0;
 
 
 static int xxx_open(struct inode*inode,struct file*filp)
 {
  ...
  spinlock(&xxx_lock);
  /************************临界区代码************************/
  if(xxx_count){
   /*已经打开*/
   spin_unlock(&xxx_lock);
   return -EBUSY;
  }
  xxx_count++;/*增加使用计数*/
  /***********************************************************/
  spin_unlock(&xxx_lock);
  
  ...
  return 0 ;/*成功*/
 }
 
 
 static int xxx_release(struct inode*inode,struct file *filp)
 {
  ...
  spinlock(&xxx_lock);
  xxx_count--;/*减少使用计数*/
  spin_unlock(&xxx_lock);
  
  return 0;
 }
 
 
 
 
 
自旋锁衍生----读写自旋锁:
 普通的自旋锁不关心锁定的内核对象，究竟进行怎样的操作，不管是读还是写他都一视同仁。
 然后就衍生出一种新的自旋锁机制--读写自旋锁
 定义:可以允许读的并发，最多只能由一个写
 
 操作:
 1.定义读写自旋锁:
 rwlock_t my_rwlock = PW_LOCK_UNLOCKED;/*静态初始化*/
 
 rwlock_t my_rwlock;
 rwlock_init(&my_rwlock);//动态初始化
 2.读锁定
 void read_lock(rwlock_t *lock);
 void read_lock_irqsave(rwlock_t *lock,unsigned long flags);
 void read_lock_irq(rwlock_t *lock);
 void read_lock_bh(rwlock_t *lock);
 
 3.读解锁:
 void read_unlock(rwlock_t *lock);
 void read_unlock_irqrestore(rwlock_t *lock,unsigned long flags);
 void read_unlock_irq(rwlock_t *lock);
 void read_unlock_bh(rwlock_t *lock);
 在对共享资源进行读取之前，应该先调用读读锁定函数，完成之后调用解锁函数
 4.写锁定函数
 void write_lock(rwlock_t *lock);
 void write_lock_irwqsave(rwlock_t *lock,unsigned long flags);
 void write_lock_irq(rwlock_t *lock);
 void write_lock_bh(rwlock_t *lock);
 int write_trylock(rwlock_t *lock);//尝试获取自旋锁，不管成功与否都立即返回
 5.写解锁
 void write_unlock(rwlock_t *lock);
 void write_unlock_irwqsave(rwlock_t *lock,unsigned long flags);
 void write_unlock_irq(rwlock_t *lock);
 
 
 

 读写自旋锁使用范例:
  rwlock_t lock;/*定义rwlock*/
  rwlcok_init(&lock);/*初始化rwlock*/
  
  /*读时获取锁*/
  read_lock(&lock);
  .../*临界资源*/
  read_unlock(&lock);
  
  /*写时获取锁*/
  write_lock_irqsave(&lock,flags);
  .../*临界资源*/
  write_unlock_irqstore(&lock,flags);
 
 
 
 
 
 
 
自旋锁衍生----顺序锁:
 机制:读时可写或者写时可读，但是不可同时写，并且若果在读执行单元进行读操作时
 有写执行单元写入，那么读执行单元需要重新读取，以确保数据最新
 
 限制:顺序锁要求被保护的资源不包含有指针
 顺序锁操作:
 1.获取顺序锁
 void write_seqlock(seqlock_t sl);
 int write_tryseqlock(seqlock_t *sl);
 write_seqlock_irqsave(lock,flags);//= write_seqlock()+local_irq_save()
 write_seqlock_irq(lock);//spin_unlock()+local_irq_enable()
 write_seqlock_bh(lock);//spin_unlock()+local_bh_enable()
 
 2.释放自旋锁，与获取自选锁相对
 
 
 /*读执行单元涉及的循序操作*/
 1.读开始
 /*读执行单玉环在对被顺序锁sl保护的共享资源进行访问前，需要调用该函数
 ，该函数返回顺序锁sl的当前序号*/
 unsigned read_seqbegin(const seqlock_t *sl);
 read_seqbegin_irqsave(lock,flag);
 2.重读
 /*读执行单元在访问玩被顺序锁sl保护的共享资源后需要调用该函数来检查，
 在读访问期间是否有写操作，如果有写操作，读执行单元就要重新进行读取*/
 int read_seqretry(const seqlock_t *sl,unsigned iv);
 read_seqretry_irqrestore(lock,iv,flags);
 /*读执行单元使用模式*/
 do{
  segnum = read_seqbegin(&seqlock_a,seqnum);
  /*读操作代码*/
  ...
  
 }while(read_seqretry(&seqlock_a,seqnum));
 
 
 
 
自旋锁的衍生----读-拷贝-更新(RCU)
 特点:
 1.对于RCU保护的共享数据，读执行单元不需要任何锁就可以访问它，不实用原子指令
 2.用RCU的写执行单元在访问它前需要首先拷贝一个副本，然后对副本进行修改，最后在时机适当的时候指向原来数据的指针，重新指向新的被
 修改的数据
 
 
 缺点:如果写操作比较多时，对读执行单元的性能的提高不能弥补写执行单元导致的损失。原因在于使用RCU时
 写执行单元之间的同步开销会比较大
 
 
 
 RCU操作:
 1.读锁定
 rcu_read_lock()
 rcu_read_lock_bh()
 2.读解锁
 rcu_read_unlock()
 rcu_read_unlock_bh()
 
 使用模式:
 rcu_read_lock();//获取锁
 .../*读临界区*/
 rcu_read_unlock()
 
 
 3.同步RCU
 synchronize_rcu()
 此操作将阻塞写执行单元，知道所有的读执行单元已经完成读操作，写指定单元才进行下一步操作
 
 synchronize_sched()
 该函数用于等待所有的CPU都处在可抢占的状态，它能保证正在运行的中断处理函数处理完毕，单不能保证正在运行的软中断
 处理完毕
 
 
 
 /*RCU还有许多复杂操作，现在先不谈及，以后用到的时候再说*/
 
 
 
 
 
 
 
 
信号量
 信号量是保护临界区的另一种有效方法
 机制:只有得到信号量的进程才能执行临界区代码，但是与自旋锁不同的是
 ，当获取不到信号量时，进程不会在原地打转而是进入休眠状态，这种休眠可以
 被唤醒
 
 
 
 Linux中与信号量相关的操作
 1.定义信号量
 struct semaphore sem;
 2.初始化信号量
 void sema_init(struct semaphore *sem,int val);
 设置信号量的值为val
 
  相关的宏
  #define init_MUTEX(sem) sem_init(sem,1);//定义并初始化信号量为1
  #define init_MUTEX_LOCKED(sem) sema_init(sem,0);//定义并初始化信号量为0
 
  DECLARE_MUTEX(name);//定义一个名为name的信号量并初始化为1,
  DECLARE_MUTEX_LOCKED(name);//定义一个名为name的信号量并初始化为0
 
 3.获得信号量
 void down(struct semaphore * sem);
 该函数用于获得信号量，如果获取不到会导致睡眠，因此不能在中断上下文中使用
 int down_interruptible(struct semaphore * sem);
 与down类似，不同之处在于，由此函数引起的睡眠可以被信号打断，信号也会导致该函数返回非零值
 int down_trylock(struct semaphore * sem);
 尝试获取信号量，如果能够立即获得，它就获得信号量并返回0，否则返回非零值，不会导致睡眠
 
 注意:使用down_interrupible()获取信号量的时候，对返回值一般会进行检查，如果非零返回-ERESTARTSYS
 if(down_interrupible(&sem))
  return -ERESTARTSYS;
  
 4.释放信号量
 void up(struct semaphore * sem);
 释放信号量唤醒等待者
 
 /*信号量的一般使用步骤*/
 DECLARE_MUTEX(mount_sem);  //定义并初始化信号量为1
 down(&mount_sem);
 ...
 critical section /*临界区*/
 ...
 up(&mount_sem);/*释放信号量*/
 
 
 
 实例:用信号量实现，设备只能被一个进程打开的实例
 static DELCARE_MUTEX(xxx_lock);/*定义互斥量*/
 
 static int xxx_open(struct inode*inode ,struct file*filp)
 {
 ...
 if(down_trylock(&xxx_lock))/*获得信号量,尝试获得*/
  return -EBUSY;/*设备忙*/
 ...
 return 0;
 
 }
 
 
 static int xxx_release(struct inode*inode,struct file*filp)
 {
  up(&xxx_lock);
  return 0;
 }
 
 
 小知识:如果信号量初始化为零，则可以用于同步
 
 

 
完成量
 简介:与信号量类似，但是同步机制更好
 
 完成量的相关操作:
 1.定义完成量
 struct completion my_completion;
 
 
 2.初始化completion
 也有两种途径
 (1),init_completion(&my_completion);
 (2),DECLARE_COMPLETION(my_completion);
 
 3.等待完成量
 void wait_for_completion(struct completion *c);
 4.唤醒完成量
 void complete(struct completion *c);
 void complete_all(struct completion *c);
 
 

 
 
 
 
 
下面我们先暂停一下，来比较一下自选量和信号量的使用原则

(1)自旋锁保护的临界区中不能包含会引起阻塞的代码(可能会引起死锁啦)
(2)如果被保护的共享资源需要在中断上下文中使用则只能使用自旋量或者是down_trylock()

 

自选锁有衍生信号量当然也有衍生啦。而且其使用方法大致相同，只要理解了其中的含义就能一通百通

信号量衍生之读写信号量
(自己看书就行^.^)

 

 

 

现在暂时来盘点一下我们讲到的解决竞态的方法:
1.中断屏蔽
2.自旋锁
3.信号量
4.完全量

 

PS:不知不觉我们已经讲完了这么解决竞态多方法，悲剧的是我们还要继续学习

 

 

 

互斥体
 简介:我们在定义信号量的时候用到了如下宏:
 DECLARE_MUTEX()，从名字中我们可以看出"mutex"互斥的概念，但是这种互斥
 机制在Linux内核中其实已经被实现，从某种意义上来说，信号量有点"模仿"的意思
 
 
 互斥体操作
 1.定义&初始化
 struct mutex my_mutex;
 mutex_init(&my_mutex);
 
 
 
 2.等待(获取)互斥体
 void inline __sched mutex_lock(struct mutex *lock);
 int __sched mutex_lock_interruptible(struct mutex *lock);
 int __sched mutex_trylock(struct mutex *lock);
 其实看到这些函数名字，你就会发现与我们前面学过的信号量其实都是一个东西
 
 
 
 3.释放互斥体
 void __sched mutex_unlock(struct mutex *lock);
 
 /*使用方法与信号量完全一致，真不想在打了，呵呵*/