免费智能真题库 > 历年试卷 > 软件设计师 > 2015年下半年 软件设计师 上午试卷 综合知识
  第23题      
  知识点:   信号量与P、V操作   检验   信号   信号量
  关键词:   PV   流水线   信号量   信号        章/节:   计算机软件知识       

 
某企业的生产流水线上有2名工人P1和P2,1名检验员P3。P1将初步加工的半成品放入半成品箱B1;P2从半成品箱B1取出继续加工,加工好的产品放入成品箱B2;P3从成品箱B2去除产品校验。假设B1可存放n件半成品,B2可存放m件产品,并设置6个信号量S1、S2、S3、S4、S5和S6,且S3和S6的初值都为0。采用PV操作实现P1、P2和P3的同步模型如下图所示,则信号量S1和S5(23);S2、S4的初值分别为(24)。
 
 
  A.  分别为同步信号量和互斥信号量,初值分别为0和1
 
  B.  都是同步信号量,其初值分别为0和0
 
  C.  都是互斥信号量,其初值分别为1和1
 
  D.  都是互斥信号量,其初值分别为0和1
 
 
 

 
  第27题    2016年下半年  
   37%
假设系统中有n个进程共享3台扫描仪,并采用PV操怍实现进程同步与互斥。若系统信号量S的当前值为-1,进程P1、P2又分别执行了1次P(..
  第28题    2017年上半年  
   23%
进程P1、P2 、P3、P4 和P5的前趋图如下所示:

  第25题    2018年上半年  
   39%
假设铁路自动售票系统有n个售票终端,该系统为每个售票终端创建一个进程Pii=..
   知识点讲解    
   · 信号量与P、V操作    · 检验    · 信号    · 信号量
 
       信号量与P、V操作
        信号量机制主要有整型信号量、记录性信号量、信号量集机制。
        1)整型信号量与P、V操作
        信号量是一个整型变量,根据控制对象的不同赋予不同的值。信号量可分为以下两类。
        (1)公用信号量。实现进程间的互斥,初值为1或资源的数目。
        (2)私用信号量。实现进程间的同步,初值为0或某个正整数。
        信号量S的物理意义为:S≥0,表示某资源的可用数;S<0,其绝对值表示阻塞队列中等待该资源的进程数。P、V操作是实现进程同步与互斥的常用方法。
        P操作定义:S:=S-1,若S≥0,则执行P操作的进程继续执行;否则,若S<0,则置该进程为阻塞状态,并将其插入阻塞队列。
        V操作定义:S:=S+1,若S>0,则执行V操作的进程继续执行;否则,若S≤0,则从阻塞状态唤醒一个进程,并将其插入就绪队列,执行V操作的进程继续执行。
        2)利用P、V操作实现进程的互斥
        令信号量的初值为1,当进程进入临界区时执行P操作,退出临界区时执行V操作。则进入临界区的代码段如下。
        
        3)利用P、V操作实现进程的同步
        进程的同步是由于进程间合作而引起的相互制约问题。要实现进程的同步,可用一个信号量与消息联系起来。当信号量的值为0时表示消息未产生,当信号量的值为非0时表示希望的消息已经存在。假定用信号量S表示某条消息,进程可以通过调用P操作测试消息是否达到,调用V操作通知消息已经准备好。
 
       检验
        检验(检查)包括测量、检查和测试等活动,目的是确定项目成果是否与要求相一致。检验可以在任何管理层次中开展,例如,一个单项活动的结果和整个项目的最后成果都可以检验。检验有各种名称,如复查、产品复查、审查及评审等。
        检查表(核对表)是常用的检验技术,检查表通常是由详细的条目组成的,用于检查和核对一系列必须采取的步骤是否已经实施的结构化工具,其具体内容因应用的不同而不同。检查表是一种有条理的工具,可简单可烦琐,语言表达形式可以是命令式,也可以是询问式。
        例如,下表是一个确认测试工具属性的检查表例子。
        
        一个确认测试工具属性的检查表例子
 
       信号
        任务间同步的另一种方式是异步信号。在两个任务之间,可以通过相互发送信号的方式,来协调它们之间的运行步调。
        所谓的信号,指的是系统给任务的一个指示,表明某个异步事件已经发生了。该事件可能来自于外部(如其他的任务、硬件或定时器),也可能来自于内部(如执行指令出错)。异步信号管理允许任务定义一个异步信号服务例程ASR(Asynchronous Signal Routine),与中断服务程序不同的是,ASR是与特定的任务相对应的。当一个任务正在运行的时候,如果它收到了一个信号,将暂停执行当前的指令,转而切换到相应的信号服务例程去运行。不过这种切换不是任务之间的切换,因为信号服务例程通常还是在当前任务的上下文环境中运行的。
        信号机制与中断处理机制非常相似,但又各有不同。它们的相同点是:
        .都具有中断性:在处理中断和异步信号时,都要暂时地中断当前任务的运行;
        .都有相应的服务程序;
        .都可以屏蔽响应:外部硬件中断可以通过相应的寄存器操作来屏蔽,任务也能够选择不对异步信号进行响应。
        信号机制与中断机制的不同点是:
        .中断是由硬件或特定的指令产生,而信号是由系统调用产生;
        .中断触发后,硬件会根据中断向量找到相应的处理程序去执行;而信号则通过发送信号的系统调用来触发,但系统不一定马上对它进行处理;
        .中断处理程序是在系统内核的上下文中运行,是全局的;而信号处理程序是在相关任务的上下文中运行,是任务的一个组成部分。
        实时系统中不同的任务经常需要互斥地访问共享资源。当任务试图访问资源时被正使用该资源的其他任务阻塞,可能出现优先级反转的现象,即当高优先级任务企图访问已被某低优先级任务占有的共享资源时,高优先级任务必须等待直到低优先级任务释放它占有的资源。如果该低优先级任务又被一个或多个中等优先级任务阻塞,问题就更加严重。由于低优先级任务得不到执行就不能访问资源、释放资源。于是低优先级任务就以一个不确定的时间阻塞高优先级的任务,导致系统的实时性没有保障。下图为是一个优先级反转的示例。
        
        一个优先级反转的示例
        如上图所示,系统存在任务1、任务2、任务3(优先级从高到低排列)和资源R。某时,任务1和任务2都被阻塞,任务3运行且占用资源R。一段时间后,任务1和任务2相继就绪,任务1抢占任务3运行,由于申请资源R失败任务1被挂起。由于任务2的优先级高于任务3,任务2运行。由于任务3不能运行和释放资源R,因此任务1一直被阻塞。极端情况下,任务1永远无法运行,处于饿死状态。
        解决优先级反转问题的常用算法有优先级继承和优先级天花板。
               优先级继承协议
               L. Sha、R. Rajkumar和J. P. Lehoczky针对资源访问控制提出了优先级继承协议(Priority Inheritance Protocol,PIP)。
               PIP协议能与任何优先级驱动的抢占式调度算法配合使用,而且不需要有关任务访问资源情况的先验知识。优先级继承协议的执行方式是:当低优先级任务正在使用资源,高优先级任务抢占执行后也要访问该资源时,低优先级任务将提升自身的优先级到高优先级任务的级别,保证低优先级任务继续使用当前资源,以尽快完成访问,尽快释放占用的资源。这样就使高优先级任务得以执行,从而减少高优先级任务被多个低优先级任务阻塞的时间。低优先级任务在运行中,继承了高优先级任务的优先级,所以该协议被称作优先级继承协议。
               由于只有高优先级任务访问正被低优先级任务使用的资源时,优先级继承才会发生,在此之前,高优先级任务能够抢占低优先级任务并执行,所以优先级继承协议不能防止死锁,而且阻塞是可以传递的,会形成链式阻塞。另外,优先级继承协议不能将任务所经历的阻塞时间减少到尽可能小的某个范围内。最坏情况下,一个需要μ个资源,并且与v个低优先级任务冲突的任务可能被阻塞min(μ,v)次。
               优先级冲顶协议
               J. B. Goodenough和L. Sha针对资源访问控制提出了优先级冲顶协议(Priority Ceiling Protocol,PCP)。
               PCP协议扩展了PIP协议,能防止死锁和减少高优先级任务经历的阻塞时间。该协议假设所有任务分配的优先级都是固定的,每个任务需要的资源在执行前就已确定。每个资源都具有优先级冲顶值,等于所有访问该资源的任务中具有的最高优先级。任一时刻,当前系统冲顶值(current priority ceiling)等于所有正被使用资源具有的最高冲顶值。如果当前没有资源被访问,则当前系统冲顶值等于一个不存在的最小优先级。当任务试图访问一个资源时,只有其优先级高于当前系统冲顶值,或其未释放资源的冲顶值等于当前系统冲顶值才能获得资源,否则会被阻塞。而造成阻塞的低优先级任务将继承该高优先级任务的优先级。
               已经证明,PCP协议的执行规则能防止死锁,但其代价是高优先级任务可能会经历优先级冲顶阻塞(Priority ceiling blocking)。即高优先级任务可能被一个正使用某资源的低优先级任务阻塞,而该资源并不是高优先级任务请求的。这种阻塞又被称作回避阻塞(avoidance blocking),意思是因为回避死锁而引起的阻塞。即使如此,在PCP协议下,每个高优先级任务至多被低优先级任务阻塞一次。使用PCP协议后,能静态分析和确定任务之间的资源竞争,计算出任务可能经历的最大阻塞时间,从而能分析任务集合的可调度性。在PCP协议下,高优先级任务被阻塞时会放弃处理器,因此,访问共享资源的任务可能会产生4次现场切换。
 
       信号量
        信号量是1965年由著名的荷兰计算机科学家Dijkstra提出的,其基本思路是使用一种新的变量类型,即信号量来记录当前可用资源的数量。
        在信号量的具体实现上,有两种不同的方式。
        (1)方式一:要求信号量的取值必须大于或等于0。如果信号量的值等于0,表示当前已没有可用的空闲资源;如果信号量的值大于0,则该值就代表了当前可用的空闲资源数量;
        (2)方式二:信号量的取值可正可负。如果是正数或0,其含义与方式一是相同的;如果是负数,则它的绝对值就代表正在等待进入临界区的任务个数。
        信号量是由操作系统来维护的,任务不能直接去修改它的值,只能通过初始化和两个标准原语(即P、V原语)来对它进行访问。在初始化时,可以指定一个非负整数,即空闲资源的总数。所谓的原语,通常由若干条语句组成,用来实现某个特定的操作,并通过一段不可分割或不可中断的程序来实现其功能。原语是操作系统内核的一个组成部分,必须在内核态下执行。原语的不可中断性是通过在其执行过程中关闭中断来实现的。
        P、V原语作为操作系统内核代码的一部分,是一种不可分割的原子操作。它们在运行时,不会被时钟中断所打断。另外,在P、V原语中包含有任务的阻塞和唤醒机制,因此,当任务在等待进入临界区的时候,会被阻塞起来,而不会去浪费CPU时间。
        P原语中的字母P,是荷兰语单词测试的首字母。它的主要功能是申请一个空闲的资源,把信号量的值减1。如果成功的话,就退出原语;如果失败的话,这个任务就会被阻塞起来。V原语当中的字母V,是荷兰语单词增加的首字母。它的主要功能是释放一个被占用的资源,把信号量的值加1,如果发现有被阻塞的任务,就从中选择一个把它唤醒。
        采用信号量来实现任务之间的互斥,优点有两个:一是可以设置信号量的计数值,从而允许多个任务同时进入临界区;二是当一个任务暂时无法进入临界区时,它会被阻塞起来,从而让出CPU给其他的任务。
        大多数嵌入式操作系统都提供了信号量的机制,用户可以通过函数调用的方式去使用。
   题号导航      2015年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第23题    在手机中做本题