全部科目 > 嵌入式系统设计师 >
2014年下半年 上午试卷 综合知识
第 21 题
知识点 进程   信号   信号量   打印机   同步与互斥  
关键词 PV   打印机   范围   进程同步与互斥   信号量   进程   信号  
章/节 嵌入式操作系统基础知识  
 
 
假设系统采用PV操作实现进程同步与互斥。若n个进程共享两台打印机,那么信号量S的取值范围为(21)。
 
  A.  -2?n
 
  B.  -(n-1)?1
 
  C.  -(n-1)?2
 
  D.  -(n-2)?2
 
 




 
 
相关试题     任务间的同步与互斥 

  第35题    2009年下半年  
RS~422有(35)根数据信号线:而RS~485最少有(36)根数据信号线。

  第12题    2015年下半年  
声音(音频)信号的一个基本参数是频率,它是指声波每秒钟变化的次数,用Hz表示。人耳能听到的音频信号的频率范围是(12)。

  第50题    2014年下半年  
以下关于死锁的叙述中,不正确的是(50)。

相关试题     进程、线程和任务 

  第35题    2011年下半年  
对于两个并发进程,设互斥信号量为mutex,若mutex=1,则(35)。

  第21题    2019年下半年  
进程P1、P2、P3、P4和P5的前趋图如下所示。

PV操作控制这5..

  第12题    2020年下半年  
线程可以在(12)空间实现。
①内核 ②用户 ③虚拟  ④物理

 
知识点讲解
· 进程
· 信号
· 信号量
· 打印机
· 同步与互斥
 
        进程
        简单而言,一个进程就是一个正在运行的程序。一般来说,一个进程至少应该包括以下几个方面的内容。
        .相应的程序:进程既然是一个正在运行的程序,当然需要有相应程序的代码和数据。
        .CPU上下文:指程序在运行时,CPU中各种寄存器的当前值,包括:程序计数器,用于记录将要取出的指令的地址;程序状态字,用于记录处理器的运行状态信息;通用寄存器,用于存放数据或地址;段寄存器,用于存放程序中各个段的地址;栈指针寄存器,用于记录栈顶的当前位置。
        .一组系统资源:包括操作系统用来管理进程的数据结构、进程的内存地址空间、进程正在使用的文件等。
        进程有动态性、独立性和并发行三个特性。
        (1)动态性。进程是一个正在运行的程序,而程序的运行状态是在不断地变化的。例如,当一个程序在运行的时候,每执行完一条指令,PC寄存器的值就会增加,指向下一条即将执行的指令。而CPU中用来存放数据和地址的那些通用寄存器,它们的值肯定也不断地变化。另外,堆和栈的内容也在不断地变化,每当发生一次函数调用时,就会在栈中分配一块空间,用来存放此次函数调用的参数和局部变量。而当函数调用结束后,这块栈空间就会被释放掉。
        (2)独立性。一个进程是一个独立的实体,是计算机系统资源的使用单位。每个进程都有自己的运行上下文和内部状态,在它运行的时候独立于其他的进程。
        (3)并发性。从宏观上来看,在系统中同时有多个进程存在,它们相互独立地运行。
        下图表示四个进程A、B、C、D在系统中并发地运行。从中可以看出,虽然从宏观上来说,这四个进程都是在系统中运行,但从微观上来看,在任何一个特定的时刻,只有一个进程在CPU上运行。从时间上来看,开始是进程A在运行,然后是进程B在运行,然后是进程C和进程D。接下来又轮到了进程A去运行。因此,在单CPU的情形下,所谓的并发性,指的是宏观上并发运行,而微观上还是顺序运行,各个进程轮流去使用CPU资源。
        
        四个进程在并发运行
        在具体实现上,以CPU中的程序计数器PC为例,真正物理上的PC寄存器只有一个。当四个进程在轮流执行时,PC取值的运动轨迹是先在进程A内部流动,然后再到进程B的内部流动,再到进程C和D。从进程的独立性角度来说,每个进程都有“自己”独立的PC寄存器,即逻辑上的PC寄存器,它们的取值相互独立、互不影响。所谓的逻辑PC,其实就是一个内存变量。例如,在上图中,当进程A要执行的时候,就把A的逻辑PC的值拷贝到物理PC中,然后开始运行。当轮到B运行的时候,先把物理PC的当前值保存到A的逻辑PC中,然后再把B的逻辑PC的值装入到物理PC中,即可运行。这样就实现了各个进程的轮流运行。
 
        信号
        任务间同步的另一种方式是异步信号。在两个任务之间,可以通过相互发送信号的方式,来协调它们之间的运行步调。
        所谓的信号,指的是系统给任务的一个指示,表明某个异步事件已经发生了。该事件可能来自于外部(如其他的任务、硬件或定时器),也可能来自于内部(如执行指令出错)。异步信号管理允许任务定义一个异步信号服务例程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给其他的任务。
        大多数嵌入式操作系统都提供了信号量的机制,用户可以通过函数调用的方式去使用。
 
        打印机
        打印机是计算机系统中常用的设备之一。打印机在计算机系统中是可选件。利用打印机可以打印出各种资料、文书、图形和图像等。根据打印机的工作原理,可以将打印机分为激光打印机、喷墨打印机和针式打印机三类,如下图所示。
        
        常见打印机
        激光打印机是一种高速度、高精度、低噪音的非击打式打印机,它是激光扫描技术与电子照相技术相结合的产物。激光打印机具有最高的打印质量和最快的打印速度,可以输出漂亮的文稿,也可以输出直接用于印刷制版的透明胶片。
        喷墨打印机的打印头由几百个细小的喷墨口组成,当打印头横向移动时,喷墨口可以按一定的方式喷射出墨水,打到打印纸上,形成字符、图形等。其主要优点是打印精度高、噪声较低、价格较便宜。主要缺点是打印速度慢、墨水消耗较大、日常费用较高。
        针式打印机利用打印头内的点阵撞针撞击打印色带,在打印纸上产生打印效果,常用的点阵打印机为24针行式打印机。该打印机的主要优点是价格便宜、轻便实用、维护费用低,适合于打印宽幅纸,且便于多份拷贝,还可以打印多联的超长度打印纸。主要缺点是打印速度慢、噪声大,打印质量也差。
 
        同步与互斥
        同步是合作进程间的直接制约问题,互斥是申请临界资源进程间的间接制约问题。
               进程间的同步
               在计算机系统中,多个进程可以并发执行,每个进程都以各自独立的、不可预知的速度向前推进,但是需要在某些确定点上协调相互合作进程间的工作。例如,进程A向缓冲区送数据,进程B从缓冲区取数据加工,当进程B要取数据加工时,必须是进程A完成了向缓冲区送数据的操作,否则进程B必须停下来等待进程A的操作结束。
               可见,所谓进程间的同步是指在系统中一些需要相互合作,协同工作的进程,这样的相互联系称为进程的同步。
               进程间的互斥
               进程的互斥是指系统中多个进程因争用临界资源而互斥执行。在多道程序系统环境中,各进程可以共享各类资源,但有些资源一次只能供一个进程使用,称为临界资源(Critical Resource,CR),如打印机、共享变量和表格等。
               临界区管理的原则
               临界区(Critical Section,CS)是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下:
               (1)有空即进。当无进程处于临界区时,允许进程进入临界区,并且只能在临界区运行有限的时间。
               (2)无空则等。当有一个进程在临界区时,其他欲进入临界区的进程必须等待,以保证进程互斥地访问临界资源。
               (3)有限等待。对于要求访问临界资源的进程,应保证进程能在有限的时间进入临界区,以免陷入“饥饿”状态。
               (4)让权等待。当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入忙等状态。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2023 All Rights Reserved
软考在线版权所有