【内核&驱动】并发和竞态【1】

1.导致并发执行的原因
    硬件中断服务
    SMP(对称多处理)
    内核抢占
    schedule()

2.scull的缺陷

if (!dptr->data[s_pos]) {
        dptr->data[s_pos] = kmalloc(quantum, GFP_KERNEL);
        if (!dptr->data[s_pos])
            goto out;
    }

    假定有两个进程，正在独立尝试向一个scull设备的相同偏移量写入数据，
    而且两个进程在同一时刻达到上述代码阿中的第一个if判断语句。如果代码
    涉及的指针是NULL，则这两个进程会同时分配空间，而每个进程会同时将结束
    指针赋值给dptr->data[s_pos],然而，只有一个进程会赋值成功。而另一个
    进程分配的空间则永远也不会返回到系统中。

    以上事件描述的就是竞态，竞态会导致对共享数据的非控制访问，产生非预期结果。

3.并发及其管理
    内核代码是可抢占的，所以我们的驱动程序代码会在任何时候丢失对处理器的独占
    而拥有处理器的进程可能正在调用我们的驱动程序代码
    设备中断是异步事件，也会导致代码的并发执行。
    内核中提供了许多可以延迟代码执行的机制。
        workqueue    工作队列
        tasklet        小任务
        timer        定时器
    这些机制可以使得代码在任何时刻执行，而不管当前进程在作什么

    对竞态的避免也是一种胁迫性的任务，大部分竞态可以通过使用内核的并发控制原语，
    并应用几个基本原理来控制

    竞态通常作为对资源的共享访问结果而产生。
    当两个执行线程需要访问相同数据结构时，混合的可能性就永远存在
    因此，应该避免资源的共享。但是这种类型的共享通常是必须的。硬件资源在
    本质上就是共享的资源，软件资源经常需要对其他执行线程可用。全局变量并不是
    共享数据的唯一途径，只要我们将代码的一个指针传递给内核的其他部分，一个
    新的共享就可能建立。共享是现实的生活

    资源个共享的硬规则：
        在单个执行线程之外共享硬件或软件资源的任何时候，因为另一个线程可能
        产生对该资源不一致的观察，因此必须显示的管理对该资源的访问。

        访问管理的常见技术称为“锁定”或者“互斥”————确保一次只有一个执行线程
        可操作其共享资源
        当内核代码创建了一个可能和其他内核部分共享的对象时，该对象必须在
        还有其他组件引用自己时保持存在，也就是说，在对象尚不能工作时，不能
        将其对内核引用
4.信号量和互斥体
    我们的目的是对scull数据结构的操作是原子的，这就意味着在涉及到其他执行线程之前，
    整个操作就已经结束了。为此，我们需要建立临界区(在任意给定的时刻，代码只能被
    一个线程执行)
    并不是所有的临界区都是一样的，因此内核为不同的需求提供了不同的原语
    在之前的scull程序，每个发生在进程的上下文的对scull数据结构的访问都被认为是一个
    直接的用户请求，这就意味着，当scull驱动程序在等待访问数据结构而进入休眠时，不
    需要考虑其他内核组件

    在这个上下文中“进入休眠”是一个具有明确定义的术语。
    当一个Linux进程达到某个时间点，此时它不能进行任何处理，将进入休眠(或阻塞)状态
    这将把处理器让给其他执行线程直到将来它能够继续完成自己的处理为止。
    因此，我们可以使用一种锁定机制，当进程在等待对临界区访问时，此机制可让进程进入
    休眠状态

    在可能出现休眠的情况下，并不是所有的锁机制都可用(还有一些不能休眠的锁机制)。
    而目前，对于我们来说最适合的机制是信号量(semaphore)

    信号量：
    一个信号量本质上是一个整数值，它和一对函数联合使用，这一对函数通常成为P和V。希望
    进入临界区的进程将在相关信号量上调用P；如果信号量大于零，则该值会减小一，而进程
    可以继续。相反，如果信号量的值为零，进程必须等待直到其他人释放该信号量。对信号量的
    解锁通过调用V完成；该函数增加信号量的值，并在必要时唤醒等待的进程。

    当信号量用于互斥时，信号量的值应初始化为2，这种信号量在给定的时候只能由单个进程或者
    线程使用,在这种模式下，一个信号量有时也称为一个互斥体(mutex),它是互斥的简称。
    Linux内核中几乎所有的信号量均用于互斥

5.Linux信号量的实现
    要使用信号量，内核代码必须包括
    相关类型是struct semaphore
    直接创建信号量
      

void sema_init(struct semaphore *sem, int val);

            val是赋予一个信号量的初始值
    内核提供了一组辅助的函数和宏
     

DECLARE_MUTEX(name);
/*一个称为name的信号量被初始化为1*/
DECLARE_MYTEX_LOCKED(name);
/*一个称为name的信号量被初始化为0,互斥体的初始状态是锁定的*/

    如果互斥体必须在运行时被初始化：

void init_MUTEX(struct semaphore *sem);
void init_MUTEX_LOCKED(struct semaphore *sem);

    在linux世界里，P操作称之为down，down指的是减小信号量，它也许会将调用者置于休眠状态
    ，然后等信号量变得可用，之后授予调用者对被保护资源的访问:
       

void down(struct semaphore *sem);
/*减小信号量的值，并在必要时一直等待*/
int down_interruptible(struct semaphore *sem);
/*减小信号量的值，并在必要时一直等待，但是可被中断打断*/
int down_trylock(struct semaphore *sem);
/*永远不会休眠，当信号量在调用的时候不可获得，down_trylock会立即返回一个非零值*/

    当一个线程成功调用上述操作时，就称为该线程“拥有”（“拿到”，“获得”）了该信号量。这样，
    该线程就被赋予访问该信号量保护的临界区的权力。当互斥操作完成后，必须返回该信号量。
    linux中等价于V的操作是up：

void up(struct semaphore *sem);
/*调用up后，调用者不再拥有该信号量*/

6.在scull中使用信号量
    信号量机制可以避免在访问scull_dev结构时产生竞态
    正确使用锁的关键是：明确指定需要保护的资源，并确保每一个对这些资源的访问使用正确的锁定。

    该结构体定义如下：
      

struct scull_dev {
            strucy scull_qset *data;    /* 指向第一个量子集的指针 */
            int quantum;            /* 当前量子的大小 */
            int qset;            /* 当前数组的大小 */
            unsigned long size;        /* 保存在其中的数据的总量 */
            unsigned int access_key;    /* 由sculluid和scullpriv使用 */
            struct semaphore sem;        /* 互斥信号量 */
            struct cdev cdev;        /* 字符设备结构 */
        };

    初始化信号量：
      

for (i = 0; i < scull_nr_devs; i++) {
            scull_devices[i].quantum = scull_quantum;
            scull_devices[i].qset = scull_qset;
            init_MUTEX(&scull_devices[i].sem);
            scull_setup_cdev(&scull_devices[i], i);
        }

        信号量必须在scull设备对系统其他部分可用前被初始化，所以在
        scull_setup_cdev()之前调用了init_MUTEX()
    在scull_write的开始处包含以下代码：
       

if (down_interruptible(&dev->sem)) {
            return -ERESTARTSYS;
        }

        down_interruptible()返回非0值说明操作被中断
    不管scull_write能否成功，都需要释放信号量:
       

out:
            up(&dev->sem);
            return retval;

            
7.读取者/写入者信号量
许多任务可以划分两种不同的工作类型
    一些任务只需要读取受保护的数据结构
    其他的则必须做出修改
为了提高性能，并发执行读操作是可行的
linux内核为这种情形提供了一种特殊的信号量类型,称为“rwsem”
(或者“reader/writer semaphore, 读取者/写入者信号量”)


struct rw_semaphore;
初始化：

void init_rwsem(struct rw_semaphore *sem);

对于只读访问，可用的接口如下：
  

void down_read(struct rw_semaphore *sem);
/* 提供了对受保护资源的只读访问，可与其他的读取者并发访问
 * 可能会将调用进程置于不可中断的休眠 */
int down_read_trylock(struct rw_semaphore *sem);
/* 不会在读取访问不可获得时等待，他在授予访问时返回非零，其他情况下返回零 */
void up_read(struct rw_semaphore *sem);

针对写入者的接口类似于读取者接口
 

void down_write(struct rw_semaphore *sem);
void down_read_trylock(struct rw_semaphore *sem);
void up_write(struct rw_semaphore *sem);
void downgrade_write(struct rw_semaphore *sem);
/* 当某个快速改变获得了一个写者锁，而其后是更长时间的只读访问的话，
 * 我们可以在结束修改之后调用downgrade_write来允许其他读取者访问*/

     一个rwsem可允许一个写入者和无限的读取者拥有该信号量， 写入者具有更高的优先级，
     当某个给定的写入者试图进入临界区时，在所有写入者完成其工作之前，不会允许读取者
     获得访问。如果有大量的写入者竞争该信号量，则这种实现会导致读取者“饿死”，即可能会
     长期拒绝读取者的访问。为此，最好在很少需要写访问且写入者只会短期拥有信号量时使用rwsem
8.completion
内核中常见一种模式，在当前线程之外初始化某个活动，然后等待活动的结束。在这种情况下，我们可以
使用该信号量来同步这两个任务：
  

struct semaphore sem;
init_MUTEX_LOCKED(&sem);
start_external_task(&sem);
down(&sem);

当外部任务完成其工作的时候调用：
   

up(&sem);

completion(完成)接口，是一种轻量级的机制，它允许一个线程告诉另外一个线程某个工作已经完成。

创建接口：
 

DECLARE_COMPLETION(my_completion);

动态的创建和初始化copletion：

struct completion my_completion;
    ...
init_completion(&my_completion);

要等待completion,可进行如下调用
  

void wait_for_completion(struct completion *c);
/* 该函数执行一个不可杀的进程，如果调用了wait_for_completion且
 * 没有人会完成该任务，则将产生一个不可杀的进程*/

出发completion事件：
   

void complete(struct completion *c);
void complete_all(struct completion *c);

一个completiion通常是一个单次设备，如果没有使用complete_all，则我们可以重复使用一个completion结构
但是如果使用了complete_all，则在重复使用的时候重新初始化它：

INIT_COMPLETION(struct completion c)；

实例程序：
    任何试图从该设备读取的进程都将等待，直到其他进程写入该设备为止
   

DECLARE_COMPLETION(comp);
ssize_t complete_read(struct file * filp, char __user *buf,
                       size_t count, loff_t *pos)
{
    printk(KERN_DEBUG "process %i (%s) going to sleep\n",
           current->pid, current->comm);
    wait_for_completion(&comp);
    printk(KERN_DEBUG "awoken %i (%s)\n", current->pid, current->comm);
    return 0;
}
ssize_t complete_write(struct file * filp, const char __user *buf,
            size_t count, loff_t *pos)
{
    printk(KERN_DEBUG "process %i (%s) awakening the readers...\n",
            current->pid, current->comm);
    complete(&comp);
    return count;
}

completion机制的典型使用是模块退出时的内核线程终止，在这种原型中，某些驱动程序的内部工作由一个内核线程在
while(1)循环中完成，当内核准备清除该模块时，exit函数会告诉该线程退出并等待completion。为了实现这个目的，内核
包含了可用于这种线程的一个特殊函数：

void complete_and_exit(struct completion *c, long retval);