读者写者问题详解 操作系统

  • Post author:
  • Post category:其他




2.16 读者写者问题



抽象解释
  • 多个进程访问一个共享的数据区
  • 读者(读进程)只能读数据,写者(写进程)只能写数据
  • 适用于数据库、文件、内存、寄存器等数据区的访问模型
  • 如12306购票系统,由于用户量庞大和数据量巨大,不可避免地会出现多个进程同时查询(读)或修改(写)同一条数据的情况


2.16.1 读者写者问题的三个约束条件
  • 读者之间不互斥(

    你和室友可以同时查看元旦那天早上7点的高铁信息

  • 写者之间必须互斥(

    你和室友不能同时申请购买元旦那天早上七点G1234的6D号位置

  • 读者写者之间也互斥(

    假如你正在买G1234的6D座位,你的室友无法读到该位置的售票信息



2.16.2 读者写者问题VS生产者消费者问题


  • 能不能用生产者消费者问题解决读者写者问题?

不能

像生/消问题那样严格互斥读者写者虽然可以保证数据的正确,却无法实现同时读的特点



  • 如何判断一个问题是生产者消费者问题,还是读者写者问题?
  1. 生产者消费者问题:数据消费后就没有了;读者写者问题:数据可多次读
  2. 生产者消费者问题:消费者彼此互斥;读者写者问题:读者可以同时读


2.16.3 解决读者写者问题的三种方案


策略一 读者优先
  • 有读者在读的话,随后的读者可以进入临界区一起读
  • 待临界区全部读者退出后再轮到下一个写者
  • 有越过写者的现象,造成写者饥饿


变量设置
  • wsem:互斥信号量
  • readcount:统计同时读的readers
  • x:对readcount的修改加锁


伪代码
	int readcount=0;
	semaphore x = 1, wsem=1;
	
	void reader() { 
	 while (1) {
	  P(x);
	   readcount++;if (readcount==1) P(wsem); //第一个读者会执行此if语句,随后的会跳过P(wsem)直接进入临界区V(x);
	  READ;
	  P(x);
	   readcount--;if (readcount==0) V(wsem);//最后退出的读者执行此语句,释放临界区权限V(x);
	  }
	}
	
	void writer() {
	 while (1) {
	   P(wsem);
	    WRITE;
	   V(wsem);
	 }
	}



读者优先的相关思考
  1. Ⅰ、Ⅱ语句能否互换?

    答:不能,readcount的判断一定要在锁内,否则会出现读写不互斥:假设此时写者在临界区,第一个读者到来后readcount++,阻塞在P(wsem),第二个读者到来后直接可以修改count++,导致跨过P(wsem)直接进入临界区,读写不互斥。

    这时失去的条件是:先有一个读者进入临界区时等其进入后后面的读者才能修改count。
  2. Ⅲ、Ⅳ语句能否互换?

    答:不能,交换后考虑最后一个进程退出时又到来一个读者进程的情况:交换后readcount=0,尚未判断if时,读者仍会进入临界区,判断后释放临界区权限,写者也进入临界区,这时读写不互斥。

    这时失去的条件是:最后一个读者退出临界区时等其退出后才能修改count
  3. 考虑如下进程序列(设序列中从右到左为进程先后到达顺序),下列哪一种情况下可能存在写者饥饿

    1.R R R

    2.W W W

    3.R W

    4.R R W

    5.R R W R

    6.W W R

    7.W R R W

    答:5.RRWR时有一个R先到临界区,后面的读者进程在等待时会越过P(wsem)直接进入临界区,也就是越过了W,造成写者饥饿


策略二 公平优先
  • 有读者在读的话,下一个写者之前的读者可以进入临界区一起读
  • 写过程中,其他到来的进程按顺序处理
  • 没有越过写者的现象,不会造成写者饥饿


变量设置
  • wsem:互斥信号量
  • readcount:统计同时读的readers
  • x:对readcount的修改加锁
  • wrsem:互斥信号量,reader和writer在这里排队,用处是在读者优先的基础上,不让读者越过写者


伪代码
	int readcount=0, semaphore x=l, wrsem=1, wsem=l;
void reader() {
  while (true) {
    P(wrsem);
    P(x);
      readercount++;
      if (readercount == 1)
        P(wsem);
    V(x);
    V(wrsem);
      READ;
    P(x);
      readercount--;
      if (readercount == 0)
        V(wsem);
    V(x);
  }
}
void writer() {
  while (true) {
    P(wrsem);
    P(wsem);
      WRITE;
    V(wsem);
    V(wrsem);
  }
}



与读者优先相比

在读者优先中,wsem只对第一个读者起阻塞作用,后续读者不受其影响。为了保证按照到达顺序处理,故公平优先方式设置wrsem,读者/写者按到达顺序在wrsem上排队。



策略三 写者优先
  • 有写者声明要写时,不允许读者再进入临界区
  • 降低了并发度
  • 有越过读者的现象,会造成读者饥饿


变量设置
  • rsem:互斥信号量,当至少有一个写者申请写数据时,互斥新的读者进入读数据
  • 第一个写者受rsem影响,一旦有第一个写者,后续写者不受rsem其影响。但是读者需要在rsem上排队
  • writecount:用于控制rsem对写者的控制
  • y:对writecount的修改加锁


伪代码
int readcount = 0, writecount = 0;
semaphore x=l, y= 1, wsem=1, rsem=l;

void reader( ) {
   while (1) {
      P(rsem);
       P(x);
        readcount++;
        if (readcount ==1) P(wsem);
       V(x);
      V(rsem);
     READ;
     P(x);
      readcount--;
      if (readcount ==0) V(wsem);
     V(x);
   }
 }
void writer( ) {
  while (1) {
    P(y);
     writecount++;
     if (writecount ==1) P(rsem);
    V(y);
    P(wsem);
     WRITE;
    V(wsem);
    P(y);
     writecount--;
     if (writecount==0) V(rsem);
    V(y);
  }
}



与公平优先相比

在公平优先中,读者和写者都会受到wrsem的限制,而写者优先中,由于增加了if (writecount ==1) P(rsem)的语句,当写者到来时会比读者优先进入临界区,但WRRRR的情况写者不会优先



策略四 写者优先改进
  • 为了解决WRRRR中W不能优先的问题


变量设置
  • 沿用写者优先的变量
  • 增加z信号量,仅对写者有作用,让读者队列在z上排队,只有一个读者在rsem上排队


伪代码
int readcount=0,writecount=0; 
semaphore x=l, y= 1,z=1,wsem=1,rsem=l;

void reader( ) {
   while (1) {
     P(z);
      P(rsem);
       P(x);
        readcount++;
        if (readcount ==1) P(wsem);
       V(x);
      V(rsem)V(z);
     READ;
     P(x);
      readcount--;
      if (readcount ==0) V(wsem);
     V(x);
   }
 }
void writer( ) {
  while (1) {
    P(y);
     writecount++;
     if (writecount ==1) P(rsem);
    V(y);
    P(wsem);
     WRITE;
    V(wsem);
    P(y);
     writecount--;
     if (writecount==0) V(rsem);
    V(y);
  }
}



写者优先改进方法的思考
  1. z信号量起到了什么作用?
  • 在rsem上不允许建造读进程的长队列,否则写进程将不能跳过这个队列.
  • 允许一个读进程在rsem上排队,其他读进程在信号量z上排队
  1. P(z)和P(rsem)能否互换位置?

    不能, 否则P(z)失去限制作用


2.16.4 读者写者问题示例



示例一


情境描述
  • 东西方向的独木桥,仅容一人过,不允许停留
  • 东西方向都有人在等着过桥

请用P、V操作来实现东西两端行人过桥问题



分析
  • 简单的写者互斥问题
  • 多个写者共享数据
  • 行人都是写者,桥是数据
  • 信号量
  • s:互斥信号量


伪代码
semaphore s = 1;                       //互斥信号量

void east_west( )
{
    while (true) {
         P(s);                                           //互斥其他人过桥
         walk across the bridge from east to west;      //行人从东向西过桥
         V(s);                                          //允许其他人过桥
    }
}

void west_east( )
{
    while (true) {
         P(s);                                         //互斥其他人过桥
         walk across the bridge from west to east;      //行人从西向东过桥
         V(s);                                           //允许其他人过桥
    }
}




示例二


情境描述
  • 东西方向的独木桥,仅容一人过,不允许停留
  • 东西方向都有人在等着过桥
  • 同一方向的行人可以连续过桥,另一方的行人必须等待

请用P、V操作来实现东西两端行人过桥问题



分析
  • 读者优先问题
  • 行人首先上桥的一方为读者,另一方为写者,桥是数据
  • 信号量
  • x:互斥信号量,互斥读者写者
  • countR:统计读者数目(同时在桥上的行人数目)
  • mutexR:对变量countR加锁


伪代码
int countA=0, countB=0;
semaphore x=1, mutexA=1, mutexB=1;

void east_west() { 
    while (1) {
        P(mutexA);
        countA++;
        if (countA==1) P(x); 
        V(mutexA);
        walk across the bridge from east to west;
        P(mutexA);
        countA--;
        if (countA==0) V(x);
        V(mutexA);
    }
}

void west_east() { 
    while (1) {
        P(mutexB);
        countB++;
        if (countB==1) P(x); 
        V(mutexB);
        walk across the bridge from west to east;
        P(mutexB);
        countB--;
        if (countB==0) V(x);
        V(mutexB);
    }
}



示例三


情境描述
  • 东西方向的独木桥,不允许停留
  • 东西方向都有人在等着过桥
  • 同一方向的行人可以连续过桥,另一方的行人必须等待
  • 桥最大可承重四人

请用P、V操作来实现东西两端行人过桥问题



分析
  • 读者优先问题
  • 行人首先上桥的一方为读者,另一方为写者,桥是数据
  • 与示例二不同在于不用一个一个过桥,只要桥没到承重限度就可以进入,这里承重限度就是临界区大小
  • 信号量
  • x:互斥信号量,互斥读者写者
  • countR:统计读者数目(同时在桥上的行人数目)
  • mutexR:对变量countR加锁
  • count: 位于独木桥上的行人数目


伪代码
int countA=0, countB=0;
semaphore x=1, muteA=1, mutexB=1,count=4;


void east_west() { 
    while (1) {
        P(mutexA);
        countA++;
        if (countA==1) P(x); 
        V(mutexA);
        P(count);
        walk across the bridge from east to west;
        V(count);
        P(mutexA);
        countA--;
        if (countA==0) V(x);
        V(mutexA);
    }
}
void west_east() { 
    while (1) {
        P(mutexB);
        countB++;
        if (countB==1) P(x); 
        V(mutexB);
        P(count);
        walk across the bridge from west to east;
        V(count);
        P(mutexB);
        countB--;
        if (countB==0) V(x);
        V(mutexB);
    }
}

在这里插入图片描述



版权声明:本文为qq_44722674原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。