软件测试-移动应用

读者/写者问题

读者与写者问题（reader-writer problem）（Courtois, 1971）是经典的并发程序设计问题。在这个问题中，我们有两组进程：读者（Readers）和写者（Writers），它们需要共享访问一个文件 F 。

读者优先

semaphore rmutex = 1;  // 控制对 read_count 的互斥访问
semaphore wmutex = 1;  // 控制对文件内容的互斥写
int read_count = 0;

process reader_i() {
    while (true) {
        P(rmutex);  // rmutex 用于互斥访问 read_cout
        if (read_count == 0)
            P(wmutex);  // 如果当前是第一个读者，阻塞写者，以保证读到的数据不被更改
        ++read_count;
        V(rmutex);
        
        read();
        
        P(rmutex);
        if (--read_count == 0)
            V(wmutex);  // 如果当前结束的是最后一个读者，允许开始写
        V(rmutex);
    }
}

process writer_i() {
    while (true) {
        P(wmutex);  // wmutex 用于互斥访问
        write();
        V(wmutex);
    }
}

semaphore rmutex = 1;   // 控制对 read_count 的互斥访问
semaphore wmutex = 1;   // 控制对文件内容的互斥写
semaphore rwmutex = 1;  // 用于阻塞后来者
int read_count = 0;

process reader_i() {
    while (true) {
        P(rmutex);  // rmutex 用于互斥访问 read_cout
        if (read_count == 0)
            P(wmutex);  // 如果当前是第一个读者，阻塞写者，以保证读到的数据不被更改
        ++read_count;
        V(rmutex);
        
        read();
        
        P(rmutex);
        if (--read_count == 0)
            V(wmutex);  // 如果当前结束的是最后一个读者，允许开始写
        V(rmutex);
    }
}

process writer_i() {
    while (true) {
        P(rwmutex);  // 增加了这一互斥信号量
        P(wmutex);   // wmutex 用于互斥访问
        write();
        V(wmutex);
        V(rwmutex);  // 增加了这一互斥信号量
    }
}

在上述算法中引入了新的信号量rwmutex，用于阻塞后来的写者。重新设计的算法可以保证：任何一个读者到来时，没有任何后来者正在对wmutex排队。因此，当前使用wmutex的进程结束之后，该读者可以马上开始工作。即，后来的读者可以对先来的写者插队。

原文：再论“读者优先”

写者优先

int read_count = 0, write_count = 0;
semaphore x = 1, y = 1, z = 1;     // read_count, write_count 互斥
semaphore rmutex = 1, wmutex = 1;  // 读锁，写锁

process reader {
    P(z);
      P(rmutex);
        P(x);
        read_count++;
        if (read_count == 1) P(wmutex);
        V(x);
      V(rmutex);
    V(z);

    // 读操作

    P(x);
      read_count--;
      if (read_count == 0) V(wmutex);
    V(x);
}

process writer {
    P(y);
      write_count++;
      if (write_count == 1) P(rmutex);
    V(y);

    P(wmutex);
      // 写操作
    V(wmutex);

    P(y);
      write_count--;
      if (write_count == 0) V(rmutex);
    V(y);
}

读写公平

semaphore rmutex = 1;  // 控制对 read_count 的互斥访问
semaphore wmutex = 1;  // 控制对文件内容的互斥写
semaphore S = 1;       // 控制读写公平的信号量
int read_count = 0;

process reader_i() {
    while (true) {
        P(S);
        P(rmutex);  // rmutex 用于互斥访问 read_count
        if (read_count == 0)
            P(wmutex);  // 如果当前是第一个读者，阻塞写者，以保证读到的数据不被更改
        ++read_count;
        V(rmutex);
        V(S);
        
        read();
        
        P(rmutex);
        if (--read_count == 0)
        P(wmutex);  // 如果当前没有读者，允许开始写
        V(rmutex);
    }
}

process writer_i() {
    while (true) {
        P(S);
        P(wmutex);  // wmutex 用于互斥访问
        write();
        V(wmutex);
        V(S);
    }
}