欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

操作系统——信号量例题

程序员文章站 2022-06-17 20:12:55
有一个仓库,可以存放 A 和 B 两种产品,仓库的存储空间足够大,但要求: (1)一次只能存入一种产品(A 或 B); (2)-N < (A 产品数量-B 产品数量) < M。 其中,N 和 M 是正整数。试用“存放 A”和“存放 B”以及 P、V 操作描述产品 A 与 产品 B 的入库过程。 Se ......

  有一个仓库,可以存放 a 和 b 两种产品,仓库的存储空间足够大,但要求: (1)一次只能存入一种产品(a 或 b); (2)-n < (a 产品数量-b 产品数量) < m。 其中,n 和 m 是正整数。试用“存放 a”和“存放 b”以及 p、v 操作描述产品 a 与 产品 b 的入库过程。

semaphore sa = m - 1;
semaphore sb = n - 1;
//代表还能存入的数量

semaphore mutex = 1;

process_a() {
	while(1){
		p(sa); //取一个a产品准备入库
		p(mutex);
		a产品入库;
		// a产品入库后还能存入a产品数量-1
		v(mutex);
		v(sb); //还能存入b产品数量+1
	}
}

process_b() {
	while(1){
		p(sb); //取一个b产品准备入库
		p(mutex);
		b产品入库;
		// b产品入库后还能存入b产品数量-1
		v(mutex);
		v(sa); //还能存入a产品数量+1
	}
}

  桌子上有一只盘子,最多可容纳两个水果,每次只能放入或取出一个水果。爸爸专向盘子放苹果( apple),妈妈专向盘子中放桔子( orange);两个儿子专等吃盘子中的桔子,两个女儿专等吃盘子中的苹果。请用 p、 v 操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

semaphore mutex = 1;      //互斥信号量, 其初值为1
semaphore empty = 2;       //记录允许向盘子中放入水果的个数,初值为2
semaphore orange = 0;      //盘子中已放入的苹果的个数,初值为0
semaphore apple = 0;      //盘子中已放入的桔子的个数,初值为0
main()
{
cobegin
{
   father                    //父亲进程
    {
    while (true)
       {
           p(empty);           //减少盘中可放入的水果数
                p(mutex);           //申请向盘中取、放水果
                向盘中放苹果;
                v(mutex);           //允许向盘中取、放水果
                v(apple);           //递增盘中的苹果数
        }
     }
    mother                    //母亲进程
    {
    while (true)
       {
          p(empty);           //减少盘中可放入的水果数
                p(mutex);           //申请向盘中取、放水果
                向盘中放桔子;
                v(mutex);           //允许向盘中取、放水果
                v(orange);          //递增盘中的桔子数
        }
    }
    daughteri(i=1,2)      //两女儿进程
    {
    while (true)
       {
            p(apple);           //减少盘中苹果数
                p(mutex);           //申请向盘中取、放水果
                取盘中苹果;
                v(mutex);           //允许向盘中取、放水果
                v(empty);           //递增盘中可放入的水果数
        }
     }
    sonj(j=1,2)           //两儿子进程
    {
    while (true)
       {
          p(orange);          //减少盘中桔子数
                p(mutex);           //申请向盘中取、放水果
                取盘中桔子;
                v(mutex);           //允许向盘中取、放水果
                v(empty);           //递增盘中可放入的水果数
        }
     }
   }
    coend
}

  有一个理发师,一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发师椅子上睡觉;当一个顾客到来时,必须唤醒理发师进行理发;如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和顾客各编一段程序(伪代码)描述他们的行为,要求不能带有竞争条件。

semaphore mutex = 1;    //互斥信号量,初值为1.
semaphore  wait = 0;     //等待服务的顾客数
semaphore  barbers= 0;    //等待顾客的理发师数
int custnum = 0;    //等待的顾客(还没理发的)

costumer()
{
  while(true)
  {
        p(mutex);            //申请理发
        if(custnum>0)
     {
            if(custnum<n)   //若等待人数小于n
       {
                v(mutex);     //释放进程等待
                custnum++;     //增加等待人数
            }
       else            //若等待人数超过n
        {
                v(mutex);   //释放进程等待
                离开;
             }
     }
    else                //若目前无人等待
    {
            v(mutex);        //释放进程等待
            v(barbers);     //如果必要的话,唤醒理发师
            理发;
            离开;
            p(mutex);        //要求进程等待
            custnum--;        //顾客人数减1
            v(mutex);       //释放进程等待
            v(wait);        //等待人数减1
    }
  }
}

barber()
{
  while(true)
  {
        p(mutex);            //要求进程等待
        if(custnum ==0)    //目前无顾客
     {
            v(mutex);        //释放进程等待
            p(barbers);        //理发师睡觉
       }
    else
    {
            v(mutex);        //释放进程等待
            理发;
    }
  }
}

  吸烟者问题。三个吸烟者在一间房间内,还有一个香烟供应者。为了制造并抽掉香烟,每个吸烟者需要三样东西:烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中,第一个有自己的烟草,第二个有自己的纸,第三个有自己的火柴。供应者将两样东西放在桌子上,允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者,供应者再放两样东西(随机地)在桌面上,然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。

semaphore s = 1;                //供应者
semaphore s1,s2,s3;                //三个吸烟者
s1 = s2 = s3 = 0;
bool flag1,flag2,fiag3;            //三种吸烟原料
fiag1=flag2=flag3=true;

apply()                            //供应者
{
  while(true)
  {
          p(s);
        取两样香烟原料放桌上,由flagi标记;
        if (flag2 && flag3) //供纸和火柴
      {
           v(s1);          //唤醒吸烟者一
          }
         else if(flag1 && fiag3) //供烟草和火柴
      {
           v(s2);                //唤醒吸烟者二
          }
       else                      //供烟草和纸
      {
           v(s3);                //唤醒吸烟者三
           }
   }
}

smoker1()                         //吸烟者一
{
   while(true)
   {
       p(s1);
       取原料;
       做香烟;
       v(s);                    //唤醒供应者
       吸香烟;
   }
}

smoker2()                        //吸烟者二
{
   while(true)
   {
       p(s2);
       取原料;
       做香烟;
       v(s);                    //唤醒供应者
       吸香烟;
   }
}

smoker3()                        //吸烟者三
{
   while(true)
{
       p(s3);
       取原料;
       做香烟;
       v(s);                    //唤醒供应者
      吸香烟;
   }
}

   面包师问题。面包师有很多面包和蛋糕,由 n 个销售人员销售。每个顾客进店后先取一个号,并且等着叫号。当一个销售人员空闲下来,就叫下一个号。请分别编写销售人员和顾客进程的程序。

semaphore buyer= 0;                //顾客人数
semaphore seller = n;            //销售人员数
semaphore mutex_s = 1;            //用于销售人员的互斥信号量
semaphore mutex_b = 1;            //用于顾客的互斥信号量
int count_s = 0;                //记录取号的值
int count_b = 0;                //记录叫号的值

void buy()                    //顾客进程
{
    进店;
   p(mutex_b);          //取号
   count_b++;
   v(mutex_b);
   v(buyer);
  p(seller);            //等待叫号
   买面包;
   离开
}

void sell()
{
   while(true)
   {
        p(buyer);
        p(mutex_s);   //叫号
        count_s++;
        叫编号为count_s的顾客;
        v(mutex_s);
        v(seller);
   }
}

   桌上有一空盘,运行存放一只水果,爸爸可向盘中放苹果,也可放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘中空时一次只能放一个水果供吃者取用,用 p,v 原语实现爸爸儿子和女儿 3 个并发进程的同步。

	semaphore s = 1;      //s 表示盘子是否为空;
semaphore sa = 0;        //sa 表示盘中是否有苹果;
semaphore sb = 0;    //sb 表示盘中是否有桔子;

father()            //父亲进程
{
    while(true)
  {
        p(s);
        将水果放入盘中;
        if (放入的是桔子)
            v(sb);
        else
            v(sa);
    }
}

son()                  //儿子进程
{
    while(true)
  {
        p(sb);
        从盘中取出桔子;
        v(s);
      吃桔子;
    }
}

daughter()            //女儿进程
{
    while(true)
  {
        p(sa);
        从盘中取出苹果;
        v(s);
        吃苹果;
    }
}

   写者优先的读者--写者问题。读者-写者问题为数据库访问建立了一个模型。例如,一个系统,其中有许多竞争的进程试图读写其中的数据,多个进程同时读是可以接受的,但如果一个进程正在更新数据库,则所有的其他进程都不能访问数据库,即使读操作也不行。写者优先是指当一个写者到达时,将阻止其后面的读者进入数据库,直到其离开为止。

	semaphore mut1, mut2, wmutex, fmutex;          //互斥信号量
int rcount, wcount;                          //读写者人数
mut1 = mut2 = wmutex = fmutex = 1;
rcount = wcount = 0;

writer()                            //写者进程
{
   while(true)
   {
       p(mut1);
       wcount=wcount+1;
       if (wcount==1)
     {
           p(fmutex);     //如有读者,写者阻塞在此处
       }
       v(mut1);
       p(wmutex);
       写;
       v(wmutex);
       p(mut1);
       wcount=wcount-1;
       if (wcount==0)
      {
           v(fmutex);
       }
       v(mut1);
   }
}

reader()                            //读者进程
{
   while(true)
   {
       p(mut2);
       rcount=rcount+1;
       if (rcount==1)
      {
           p(fmutex);
       }
       v(mut2);
       读;
       p(mut2);
       rcount=rcount-1;
       if (rcount==0)
      {
            v(fmutex);
       }
       v(mut2);
   }
}

   在天津大学与南开大学之间有一条弯曲的小路,这条路上每次每个方向上只允许一辆自行车通过。但其中有一个小的安全岛 m,同时允许两辆自行车停留,可供两辆自行车已从两端进入小路的情况下错车使用。如图所示。
操作系统——信号量例题
下面的算法可以使来往的自行车均可顺利通过。其中使用了 4 个信号量, t 代表天大路口资源, s 代表南开路口资源, l 代表从天大到安全岛一段路的资源, k 代表从南开到安全岛一段路的资源。程序如下,请在空白位置处填写适当的 pv 操作语句,每处空白可能包含若干个 pv 操作语句。

begin
    t:=1;s:=1;l:=1;k:=1;
    cobegin
    从天大到南开的进程
        begin
            ______(1)______
           通过 l 路段;
           进入安全岛 m;
           ______(2)______
           通过 k 路段
           ______(3)______
        end
   从南开到天大的进程
       begin
          略,与“从天大到南开的进程”相反。
       end
    coend
end

  解答:

  (1) p(t); p(l);

  (2) v(l); p(k);

  (3) v(k); v(t);

  三个进程 p1、 p2、 p3 互斥使用一个包含 n(n>0)个单元的缓冲区。 p1 每次用 produce()生成一个正整数并用 put()送入缓冲区某一空单元中;p2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数;p3 每次用 geteven()从该缓冲区中取出一个偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动,并说明所定义信号量的含义。要求用伪代码描述。

p1()
{
   while(true)
   {
       x = produce();      //生成一个数
      p(empty);     //是否有空单元格
       p(mutex);    //进入临界区
       put();
       if(x%2 == 0)
            v(s2);   //如果是偶数,向p3发出信号
       else
             v(s1);   //如果是奇数,向p2发出信号
       v(mutex);         //离开临界区,释放互斥信号量
   }
}

p2()
{
   while(true)
   {
       p(s1);     //收到p1发送来的信号,已产生奇数
      p(mutex);         //进入临界区
       getodd();
       countodd():=countodd()+1;
       v(mutex);
       v(empty);         //离开临界区,释放互斥信号量
   }
}

p3()
{
   while(true)
   {
      p(s2)        //收到p1发送来的信号,已产生偶数
      p(mutex);         //进入临界区
      geteven();
      counteven():=counteven()+1;
      v(mutex);
      v(empty);         //离开临界区,释放互斥信号量
   }
}