OS-semaphore

信号量机制

信号量是一种用于控制多进程或多线程并发访问共享资源的同步机制，最早由荷兰计算机科学家Edsger W. Dijkstra在1960年代提出，并被广泛应用于操作系统和并发编程领域。

信号量的基本概念和特征

信号量是一个整数计数器，通常用于表示资源的数量或者许可证的数量。

信号量的两个主要操作：P(wait)和V(signal),

(P和V是荷兰语中“请求“和”释放“的首字母)

信号量的两个成员变量分别表示当前可用的资源数量和指向该资源等待队列的指针

整形信号量

int s=1;

void wait(int s){
  while(s<=0){}；
   s--;
}

void signal(int s){
   s++;
}

由于死循环的存在，程序会一直占用CPU的资源却没有推动进程，这就是”忙等“

记录型信号量

typedef struct{
  int value;
  Struct process *L;
}semaphore

void wait(semaphore S){
   S.value--;
   if(S.value<0){
    block(S.L);//如果请求时已经没有资源了，手动将目前的程序加入到阻塞队列中
    }
}

void signal(semaphore S){
    S.value++;
    if(S.value<=0){//在释放资源后资源的值还是没有大于0,说明这个被释放的资源已被预订了，将等待队列中预定此资源的程序唤醒，使其从阻塞态进入就绪态。
     wakeup(S.L);
     }
}

伪代码中使用整数型信号量即“忙等模型”来理解题目

struct semaphore s,empty,full=1,n,0
 message buffer[n]; int in,out=0,0;
 cobegin void produceri( i=1,2,…k)
     {   message x;
          while(TRUE){
	 produce a new message into x;
	 P(empty);//如果P(empty)在P(S)之后，则可能会出现empty已经<=0但是s已被申请，导致程序死锁
	 P(s);
	 buffer[in]=x; in=(in+1) mod n;
	 V(s);
	 V(full);
          }
     }

void consumerj( j=1,2,…m)
     {   message y;
          while(TRUE){
              P(full);
	P(s);
	y=buffer[out]; 
	out=(out+1) mod n;
	V(s);
	V(empty);
	consume message y;
          }
     }
coend

//读者优先的情况，有读者在阅读时，后来的读者总能进入缓存，写者无法操作直到不再有读者请求进入缓存

Semaphore mutex, wrt=1,1; 
int readcount=0;
void Writer(void)
{   P(wrt); 
    Perform writing;
    V(wrt);
}
void Reader(void)
{  P(mutex);
   readcount=readcount+1;
   if readcount == 1 then P(wrt);//第一个读者设立写者锁
   V(mutex);
   Perform reading;

   P(mutex);
   readcount=readcount-1;
   if readcount == 0 then V(wrt);
   V(mutex);
}

写者优先的请况，只要有写者申请缓存资源，读者就不能进入缓存直到不再有写者请求进入缓存

Semaphore xxx,mutex=1,1;
int Writers = 0;

//写者优先，只要有写者要求进入缓存，读者就无法进入缓存直到不再有写者请求进入缓存
void Writer(void) {
    P(mutex);//申请进入缓存
    Writers++;
    if (Writers == 1) {
        P(xxx);            //第一个写者设立读者锁
    }
    V(mutex);

    Perform writing;

    P(mutex);
    Writers--;//写者离开
    if (Writers == 0) {
        V(xxx);//直到所有已申请的写者离开后，才会释放缓存资源
    }
    V(mutex);
}

void Reader(void) {
    P(mutex);           //申请进入内存
    if (Writers > 0) {//已有写者申请进入内存，等待所有写者离开
        V(mutex);      //允许写者继续申请
        P(xxx);           //等到所有写者离开后进入缓存，申请缓存资源，能申请到说明Writers=0
        Perform reading;
        V(xxx);
    }              //没有写者
    Perform reading;
    V(mutex);      //允许写者继续申请

}