操作系统知识点（七）——信号量

信号量

背景

信号量（semaphore）

• 抽象数据类型

  • 一个整形（sem），两个原子操作

  • P()：sem减1，如果sem<0，等待，否则继续

  • V()：sem加1，如果sem<=0，唤醒一个等待的P

信号量使用

特性

• 信号量是被保护的整数变量

  • 初始化完成后，只能通过P()和V()操作修改

  • 由操作系统保证，PV操作是原子操作

• P()可能阻塞，V()不会阻塞

• 通常假定信号量是”公平的“

  • 线程不会被无限期阻塞在P()操作

  • 假定信号量等待按先进先出排队

分类

• 二进制信号量：可以是0或1

• 一般/计数（资源）信号量：可取任何非负值

• 两者等价：基于一个可以实现另一个

使用

• 互斥访问：临界区的互斥访问控制

• 条件同步：线程间的事件等待

生产者-消费者问题

• 生成者->缓冲区->消费者

• 有界缓冲区的生产者-消费者问题描述

  • 一个或多个生产者在生成数据后放在一个缓冲区里

  • 单个消费者从缓冲区取出数据处理

  • 任何时刻只能有一个生产者或消费者可访问缓冲区

• 问题分析

  • 任何时刻只能有一个线程操作缓冲区（互斥访问）

  • 缓冲区空时，消费者必须等待生产者（条件同步）

  • 缓冲区满时，生产者必须等待消费者（条件同步）

• 用信号量描述每个约束

  • 二进制信号量mutex

  • 资源信号量fullBuffers

  • 资源信号量emptyBuffers

class BoundedBuffer{
    mutex =new Semaphore(1);
    fullBuffers =new Semaphore(0);
    emptyBuffers =new Semaphore(n);
}
BoundedBuffer::Producter(c){
    emptyBuffers ->P();
    mutex ->P();
    ADD C TO THE BUFFER;
    mutex ->V();
    fullBuffers ->V();
}
BoundedBuffer::Consumer(c){
    fullBuffers ->P();
    mutex ->P();
    REMOVE C FROM BUFFER;
    mutex ->V();
    emptyBuffers ->V();
}

信号量实现

• 实现

class Semaphore{
    int sem;
    WaitQueue q;
}
Semaphore: P(){
    sem--;
    if(sem<0){
        ADD THIS THREAD t TO q;
        block(q);
    }
}
Semaphore: V(){
    sem++;
    if(sem<=0){
        REMOVE a THREAD t FROM q;
        wakeup(t);
    }
}

• 困难

  • 读/开发代码比较困难

  • 容易出错。使用的信号量已经被另一个线程占用；忘记释放信号量

  • 不能够处理死锁问题

管程（Moniter）

• 管程是一种用于多线程互斥访问共享资源的程序结构

  • 采用面向对象方法，简化了线程间的同步控制

  • 任一时刻最多只有一个线程执行管程代码

  • 正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复

• 使用

  • 在对象/模块中，收集相关共享数据

  • 定义访问共享数据的方法

• 组成

  • 一个锁：控制管程代码的互斥访问

  • 0或者多个条件变量：管理共享数据的并发访问

• 条件变量

  • 条件变量是管程内的等待机制

    • 进入管程的线程因资源被抢占而进入等待状态

    • 每个条件变量表示一种等待原因，对应一个等待队列

  • wait()操作

    • 将自己阻塞在等待队列中

    • 唤醒一个等待者或释放管程的互斥访问

  • signal()操作

    • 将等待队列中的一个线程唤醒

    • 如果等待队列为空，则等同空操作

• 条件变量实现

class Condition{
    int numWaiting =0;
    WaitQueue q;
}
Condition::Wait(lock){
    numWaiting++;
    ADD this thread t to q;
    release(lock);
    schedule();
    require(lock);
}
Condition::Signal(){
    if(numWaiting >0){
        REMOVE a thread t from q;
        wakeup(t);
        numWaiting--;
    }
}

• 管程解决生产者-消费者问题

class BoundedBuffer {
    …
    Lock lock;
    int count = 0;
    Condition notFull, notEmpty;
}
BoundedBuffer::Producter(c) {
    lock->Acquire();
    while (count == n)
        notFull.Wait(&lock);
    Add c to the buffer;
    count++;
    notEmpty.Signal();
    lock->Release();
}
BoundedBuffer::Consumer(c) {
    lock->Acquire();
    while (count == 0)    
      notEmpty.Wait(&lock);
    Remove c from buffer;
    count--;
    notFull.Signal();
    lock->Release();
}

经典同步问题

读者-写者问题

• 共享数据的两类使用者

  • 读者：只读取数据，不修改

  • 写者：读取和修改数据

• 读者-写者问题描述：对共享数据的读写

  • 读-读允许：同一时刻允许有多个读者同时读

  • 读-写互斥：没有写者时读者才能读，没有读者时写者才能写

  • 写-写互斥：没有其它写者时才能写

• 信号量方法

class Writer(){
    P(WriteMutex);
    write;
    V(WriteMutex);
}
class Reader(){
    P(CountMutex);
    if(Rcount ==0)
        P(WriteMutex);
    ++Rcount;
    V(CountMutex);
    
    read;
    
    P(CountMutex);
    --Rcount;
    if(Rcount ==0)
        V(WriteMutex);
    V(CountMutex);
}

• 管程方法

AR = 0;   // # of active readers
AW = 0;   // # of active writers
WR = 0;   // # of waiting readers
WW = 0;   // # of waiting writers
Lock lock;
Condition okToRead;
Condition okToWrite;

//读者
Private Database::StartRead() {
    lock.Acquire();
    while ((AW+WW) > 0) {
        WR++;
        okToRead.wait(&lock);
        WR--;
    }
    AR++;
    lock.Release();
}
Private Database::DoneRead() {
    lock.Acquire();
    AR--;
    if (AR ==0 && WW > 0) {
        okToWrite.signal();
    }
    lock.Release();
}
Public Database::Read() {
  //Wait until no writers;
  StartRead(); 
  read database;
  //check out – wake up waiting writers; 
  DoneRead(); 
}

//写者
Private Database::StartRead() {
    lock.Acquire();
    while ((AW+WW) > 0) {
        WR++;
        okToRead.wait(&lock);
        WR--;
    }
    AR++;
    lock.Release();
}
Private Database::DoneRead() {
    lock.Acquire();
    AR--;
    if (AR ==0 && WW > 0) {
        okToWrite.signal();
    }
    lock.Release();
}
Public Database::Read() {
  //Wait until no writers;
  StartRead(); 
  read database;
  //check out – wake up waiting writers; 
  DoneRead(); 
}

哲学家就餐问题

• 问题描述

  • 5个哲学家围绕一张圆桌而坐

    • 桌子上放着5支叉子

    • 每两个哲学家之间放一支

  • 哲学家的动作包括思考和进餐

    • 进餐时需同时拿到左右两边的叉子

    • 思考时将两只叉子放回原处

更多精彩，关注“咋家”