信号量

2020-02-05 0 条评论 152 次阅读 0 人点赞

Edsger Dijkstra为解决同步不同执行线程问题提出一种基于信号量的方法。信号量s具有非负整数值的全局变量,只能由联众特殊的操作来处理,这两种操作称为 P(Proberrn测试) 和 V(Verhogen增加) :

  • P(s):如果s是非零的。那么P将s减1,并且立即返回。如果s为0,那么就挂起这个线程,直到s变为非0,而一个V操作会重启这个线程。在重启之后P操作将s减1,并将控制返回给调用者。
  • V(s):V操作将s加1。如果有任何线程阻塞在P操作等待s变成非0,那么V操作会重启这些线程中的一个,然后该线程将s减1,完成它的P操作。

P中的测试和减1操作是不可分割的,也就是说,一旦预测信号量s变为非0,就会将s减1,不能有中断。V中的加1操作也是不可分割的,也就是加载、加1和存储信号量的过程中没有中断。注意,V的定义中没有定义等待线程被重新启动的顺序。唯一的要求是V必须只能重启一个正在等待的线程。因此,当有多个线程在等待同一个信号量的时,你不能预测V操作要重启哪一个线程。

P和V的定义确保了一个正在运行的程序绝不可能进入这样的一种状态:一个正确初始化的信号量有一个负值。这个属性称为信号量不变性,为控制并发程序的轨迹线提供了强有力的工具。

// Posix标准定义了许多操作信号量的函数
#include <semaphore.h>

int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s); // P(s)
int sem_post(sem_t *s); // V(s)

sem_init函数将信号量sem初始化为value。每个信号量在使用前必须初始化。程序分别通过调用sem_wait和sem_post函数来执行P和V操作。

信号量实现互斥

信号量提供了一种很方便的方法来确保对共享变量的互斥访问。基本的思想是将每个共享变量(或一组相关的共享变量)与一个初始化为1的信号量联系起来,然后用P和V操作将相应的临界区包围起来。

以这种方式来保护共享变量的信号量叫做二元信号量,因为它的值总是0或1。以提供互斥为目的的二元信号量常常也叫做互斥锁(mutex)。在一个互斥锁上执行P操作称为对互斥锁加锁。类似地,执行V操作叫做对互斥锁解锁。对一个互斥锁加了所但是还没解锁地线程称为占用这互斥锁。一个被用作 一组可用资源的计数器的信号量称为计数器信号量。

如图所示的进度图展示了我们如何利用二元信号量来正确地同步我们的计数器程序示例。每个状态都标出了该状态中信号量s的值。关键思想是这种P和V操作结合创建了一组状态,叫做禁止区,其中s<0。因为信号量的不变性,没有实际可行的轨迹能够包含禁止区中的状态。而且,因为禁止区完全包括了不安全区,所以没有实际可行的轨迹线能够接触不安全区的任何部分。因此,每条实际可行的轨迹线都是安全的,不管运行时指令顺序是怎样的,程序都会正确地增加计数器的值。

从可操作的意义上来说,由P和V操作创建的禁止区使得在任何时间点上,在被包围的临界区中,不可能由多个线程在执行指令。换句话说,**信号量操作确保了对临界区的互斥访问。

利用信号量来调度共享资源

除提供互斥之外,信号量的另一个重要作用是调度对共享资源的访问。在这种场景中,一个线程用信号量操作来通知另一个线程,程序状态中的某个条件已经为真了。两个经典的例子是生产者消费者问题与读者写者问题。

生产者-消费者问题

生产者和消费者线程共享一个有n个槽的优先缓冲区。生产者线程反复地生成新的项目,并把他们插入到缓冲区中。消费者线程不断地从缓冲区中取出这些项目,然后消费它们。也可能有多个生产者和消费者的变种。

因为插入和取出项目都涉及更新共享变量,所以我们必须保证对缓冲区的访问是互斥的。但是只保证互斥访问是不够的,我们还需要调度对缓冲区的访问。如果缓冲区是满的即没有空的槽位,那么生产者必须等待直到一个槽位变为可用。类似的,如果缓冲区是空的即没有可用的项目,那么消费者必须等待直到有一个项目变为可用。

我们开发一个简单的SBUF包。SBUF操作类型为sbuf_t的有限缓冲区,项目存放一个动态分配的n项整数数组buf中。front和rear索引值记录该数组中的第一项和最后一项。三个信号量同步对缓冲区的访问。mutex信号量提供互斥的缓冲区访问。slots和items信号量分别记录空槽位和可用项目的数量。

接下来我们给出SBUF函数的实现。sbuf_init函数为缓冲区分配堆存储器,设置front和rear表示一个空的缓冲区,并为三个信号量赋初始值。这个函数在调用其他三个函数中任何一个之前调用一次。sbuf_deinit函数是当应用程序使用完缓冲区时,释放缓冲区存储的。sbuf_insert函数等待一个可用的槽位,对互斥锁加锁,添加项目,对互斥锁解锁,然后宣布有一个新项目可用。sbuf_remove函数时与sbuf_insert函数对称的。在等待一个可用的缓冲区项目后,对互斥锁加锁,从缓冲区的前面取出该项目,对互斥锁解锁,然后发信号通知一个新的槽位可用。

typedef struct {
    int *buf; // 存放项目
    int n; // 动态分配
    int front; // 记录数组第一项
    int rear; // 记录数组最后一项
    // 三个信号量同步对缓冲区的访问
    sem_t mutex; // 信号量提供互斥的缓冲区访问
    sem_t slots; // 记录空槽位
    sem_t items; // 记录可用项目的数量
} sbuf_t; // 操作类型为sbuf_t的有限缓冲区

// 在调用其他函数任何一个之前调用一次
void sbuf_init(sbuf_t *sp, int n) { // 函数为缓冲区分配堆存储器
    sp->buf = calloc(n, sizeof(int));
    sp->n = n;
    // 设置空的缓冲区
    sp->front = sp->rear = 0;
    // 为三个信号量赋初始值
    sem_init(&sp->mutex, 0, 1);
    sem_init(&sp->slots, 0, n);
    sem_init(&sp->items, 0, 0);
}

void sbuf_deinit(sbuf_t *sp) { // 当应用程序使用完缓冲区时,释放缓冲区存储的
    free(sp->buf);
}

void sbuf_insert(sbuf_t *sp, int item) { // 等待一个可用的槽位
    P(&sp->slots);
    P(&sp->mutex); // 互斥锁加锁
    sp->buf[(++sp->rear)%(sp->n)] = item; // 添加项目
    V(&sp->mutex); // 互斥锁解锁
    V(&sp->items);
}

void sbuf_remove(sbuf_t *sp) {
    // 等待一个可用的缓冲区项目
    int item;
    P(&sp->items);
    P(&sp->mutex); // 互斥锁加锁
    item = sp->buf[(++sp->rear)%(sp->n)]; // 从缓冲区的前面取出该项目
    V(&sp->mutex); // 对互斥锁解锁
    V(&sp->slots); // 发信号通知一个新的槽位可用
    return item;
}

读者-写者问题

这是互斥问题的一个概括。一组并发的线程要访问一个共享对象,有些线程只读对象,而其他线程只修改对象。修改对象的i安城叫写者,只读对象的线程叫读者。写者必须拥有对对象的独占的访问,而读者可以和无限多个其他的读者共享对象。一般来说可以有无限多个并发的读者和写者。

读者写者问题有几个变种,都是基于读者和写者的优先级的。第一类读者写者问题:读者优先,要求不要让读者等待,除非已经把使用对象的权限赋予了一个写者,换句话说就是读者不会因为有一个写者在等待而等待;第二类读者写者问题:写者优先,要求一旦一个写者准备好可以写,它就会尽可能快地完成它的写操作,也就是说在一个写者后到达的读者必须等待,即使这个写者也是在等待。

我们给出一个对第一类读者写者问题的解答。信号量w控制对访问共享对象的临界区的访问。信号量mutex保护对共享变量readcnt的访问,readcnt统计当前在临界区中的读者数量。每当一个写者进入临界区时,它对互斥锁w加锁,每当它离开临界区时,对w解锁。这就保证了任意时刻临界区中最多只有一个写者。另一方面,只有第一个进入临界区的读者对w加锁,而只有最后一个离开临界区的读者对w解锁。当一个读者进入和离开临界区时,如果还有其他的读者在临界区中,那么这个读者会忽略互斥锁w。这就意味着只要还有一个读者占用互斥锁w,无限多数量的读者可以没有障碍的进入临界区。

// Global variables
int readcnt;
sem_t muyex, w;

void reader(void) {
    while (1) {
        P(&mutex);
        readcnt++;
        if (readcnt == 1)
            P(&w);
        V(&mutex);

        P(&mutex);
        readcnt--;
        if (readcnt == 0)
            V(&W);
        V(&mutex);
    }
}

void write(void) {
    while (1) {
        P(&w);
        V(&w);
    }
}

对这两种读者写者问题的正确解答可能导致饥饿,饥饿就是一个线程无限期地阻塞,无法进展。以上程序中,如果读者不断到达,写者就可能无期限地等待。

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)