信号量

信号量

题目:图书馆有100个座位,每位进入图书馆的读者要在登记表上登记,退出时要在登记表上注销。
(1) 当图书馆中没有座位时,后到的读者在图书馆为等待(阻塞)。
(2) 当图书馆中没有座位时,后到的读者不等待,立即回家。

分析:应用操作系统并发性中的信号量解决线程的互斥与同步问题。

定义:

信号量包括一个称为信号量的变量及对它进行的两个原语操作。每个信号量至少须记录两个信息:信号量的值等待该信号量的进程队列

它的类型定义如下:(用类PASCAL语言表述)

  1.     semaphore = record
  2. /*
  3. s.value>=0时,s.queue为空;
  4. s.value<0时,s.value的绝对值为s.queue中等待进程的个数;
  5. */
  6.          value: integer;
  7. /*
  8. 其中PCB是进程控制块,是操作系统为每个进程建立的数据结构。
  9. */
  10.          queue: ^PCB;
  11.        end;

操作:

对一个信号量变量可以进行两种原语操作:p操作和v操作,定义如下:

  1. procedure p(var s:samephore);
  2.      {
  3.        s.value=s.value-1;
  4.        if (s.value<0) asleep(s.queue);
  5.      }
  6. procedure v(var s:samephore);
  7.      {
  8.        s.value=s.value+1;
  9.        if (s.value<=0) wakeup(s.queue);
  10.      }

其中用到两个标准过程:

  • asleep(s.queue);执行此操作的进程的PCB进入s.queue尾部,进程变成等待状态。
  • wakeup(s.queue);将s.queue头进程唤醒插入就绪队列。

几个结论:

  • s.value初值为1时,可以用来实现进程的互斥(Mutex)。
  • p操作和v操作是不可中断的程序段,称为原语。如果将信号量看作共享变量,则pv操作为其临界区,多个进程不能同时执行,一般用硬件方法保证。一个信号量只能置一次初值,以后只能对之进行p操作或v操作。
  • 由此也可以看到,信号量机制必须有公共内存,不能用于分布式操作系统,这是它最大的弱点。

解答

(1)这里需要两层控制,一则控制人数上限为100,多的人在队列等候,二则,登记簿只能由一人登记(同一时刻),其他人需要再队列等候。

  1. 设信号量:S=100;  /*控制图书馆人数*/
  2. 设信号量:MUTEX=1;/*用于互斥访问登记簿*/
  3. P(S);
  4. P(MUTEX);
  5. 登记;
  6. V(MUTEX);
  7. 阅读;
  8. P(MUTEX);
  9. 注销;
  10. V(MUTEX);
  11. V(S);

(2)与第一题不同的是,第一层控制没有必要,不需要排队队列,因此仅用一个变量COUNT存储可以进去的人的数量即可,然后通过一个mutex实现对COUNT和登记簿的互斥访问。

  1. 整型变量:COUNT=100;
  2. 信号量:MUTEX=1;
  3. P(MUTEX);
  4. IF (COUNT==0)
  5. {
  6. V(MUTEX);
  7. RETURN;
  8. }
  9. COUNT=COUNT-1;
  10. 登记;
  11. V(MUTEX);
  12. 阅读;
  13. P(MUTEX);
  14. COUNT=COUNT+1;
  15. V(MUTEX);
  16. RETURN;

网络转载请注明:转载自程序员面试之家

并注明本文链接地址: 信号量

发表评论

电子邮件地址不会被公开。 必填项已用*标注