|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 处理器管理 > 同步与互斥（竞争条件、临界区、互斥、信号量、思锁等） >
|
被考次数：31次
被考频率：高频率
总体答错率：51%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：掌握
相关知识点：30个
|
|
|
|
|
|
|
在一个嵌入式应用系统中往往包含有多个任务，它们在系统的硬件平台和操作系统提供的软件平台上运行。这些任务之间主要有以下几种关系：
|
|
|
|
.相互独立：任务之间没有任何的关联关系，互不干预、互不往来。唯一的相关性就是它们都需要去竞争CPU资源。
|
|
|
|
.任务互斥：除了CPU之外，这些任务还需要共享其他的一些硬件和软件资源，而这些资源由于种种原因，在某一时刻只允许一个或几个任务去访问。因此当这些任务在访问共享资源的时候可能会相互妨碍。
|
|
|
|
.任务同步：任务之间存在着某种依存关系，需要协调彼此的运行步调。
|
|
|
|
.任务通信：任务之间存在着协作与分工，需要相互传递各种数据和信息，才能完成各自的功能。
|
|
|
|
在嵌入式操作系统当中，对于任务间的第一种关系，主要是靠调度器来进行协调。而对于其他的几种关系，操作系统必须提供一些机制，让各个任务能够相互通信、协调各自的行为，以确保系统能够顺利、和谐地运行。
|
|
|
|
|
|
在多道程序操作系统当中，两个或多个任务对同一个共享数据进行读写操作，最后的结果是不可预测，它取决于各个任务的具体运行情况。人们把这种现象叫着竞争条件。那么如何来解决竞争条件的问题呢？既然问题产生的根源在于两个或者多个任务对某一个共享数据同时进行读写操作，那么解决的方法就是在同一个时刻，只允许一个任务来访问这个共享数据。也就是说，如果当前已经有一个任务正在访问这个共享数据，那么其他的任务暂时都不能访问，只能等它先用完。这就是任务之间的互斥。
|
|
|
|
可以用一种抽象的形式来表示这个问题。把一个任务在运行过程中所做的各种事情分为两类，第一类是任务内部的计算或其他的一些事情，这些事情肯定不会导致竞争条件的出现；第二类是对共享资源进行访问，这些访问可能会导致竞争条件的出现。人们将相应的那一部分程序称为是临界区，把需要互斥访问的共享资源称为是临界资源。这样，如果能够设计出某种方法，使得任何两个任务都不会同时进入到它们的临界区当中，那么就可以避免竞争条件的出现。不过，这只是一个最基本的要求。在具体实现的时候，还必须考虑其他的一些问题。为此，人们提出了实现互斥访问的四个条件：
|
|
|
|
.在任何时候最多只能有一个任务位于它的临界区当中；
|
|
|
|
|
|
.如果某一个任务没有位于它的临界区当中，它不能妨碍其他的任务去访问临界资源；
|
|
|
|
.任何一个任务进入临界区的请求必须在有限的时间内得到满足，不能无限期地等待。
|
|
|
|
|
|
|
|
为了实现任务之间的互斥，最简单的办法就是把中断关掉。具体来说，当一个任务进入它的临界区之后，首先把中断关闭掉，然后就可以去访问共享资源。当它从临界区退出时，再把中断打开。
|
|
|
|
关闭中断可以有效地实现任务之间的互斥。对于操作系统而言，它可以认为是由中断来驱动的，只有当发生中断的时候，包括时钟中断、I/O中断、系统调用等，操作系统才能得到控制权，才能进行任务切换。如果当前任务把中断关闭了，除非它主动让出CPU，否则将不会发生任务的切换，别的任务将无法运行。在这种情形下，当前任务就可以很方便地去访问共享资源，不用担心别的任务来跟它竞争。
|
|
|
|
关闭中断法虽然简单有效，但也有它的缺点。首先，这种方法具有一定的风险。当任务把中断关闭后，如果由于种种原因不能及时地打开中断，那么整个系统就可能陷入崩溃的状态。其次，这种方法的效率不高。因为我们的初衷，只是想阻止那些试图访问共享资源的任务，以实现对该资源的互斥访问。但是关闭中断后，所有的任务都被阻止了，不论是竞争对手，还是毫不相关的任务，都被拒之门外，无法运行。因此，关闭中断法不能作为一种普遍适用的互斥实现方法，它主要用在操作系统的内核当中，使内核在处理一些关键性的敏感数据时，不会受到其他任务的干扰。
|
|
|
|
|
|
实现任务间互斥，也可以采用繁忙等待（busy waiting）的策略。其基本思路是：当一个任务想要进入它的临界区时，首先检查一下是否允许它进入，若允许，就直接进入；若不允许，就在循环地等待。
|
|
|
|
在具体实现上，有多种基于繁忙等待的实现方案。如加锁标志位法、强制轮流法、Peterson算法、TSL指令等等。这些方法可以抽象为下图所示的伪代码形式。当一个任务需要进入临界区时，不断地用while语句来测试一个标志位，看能否进入。如果不能的话，就循环等待，直到允许进入。在退出临界区的时候，还要把标志位清除掉。这类方法的共同点就是在测试能否进入临界区的时候，使用的是while循环语句，不断地执行测试指令，这样就浪费了大量的CPU时间。另外，这种方法还有一个问题，它只能处理单一共享资源的情形。如果在系统中，某种类型的共享资源有N份实例，则在任何时刻，最多应该允许N个任务同时进入临界区，去访问这种资源。但繁忙等待法无法处理此类问题。
|
|
|
|
|
|
|
|
|
|
信号量是1965年由著名的荷兰计算机科学家Dijkstra提出的，其基本思路是使用一种新的变量类型，即信号量来记录当前可用资源的数量。
|
|
|
|
|
|
（1）方式一：要求信号量的取值必须大于或等于0。如果信号量的值等于0，表示当前已没有可用的空闲资源；如果信号量的值大于0，则该值就代表了当前可用的空闲资源数量；
|
|
|
|
（2）方式二：信号量的取值可正可负。如果是正数或0，其含义与方式一是相同的；如果是负数，则它的绝对值就代表正在等待进入临界区的任务个数。
|
|
|
|
信号量是由操作系统来维护的，任务不能直接去修改它的值，只能通过初始化和两个标准原语（即P、V原语）来对它进行访问。在初始化时，可以指定一个非负整数，即空闲资源的总数。所谓的原语，通常由若干条语句组成，用来实现某个特定的操作，并通过一段不可分割或不可中断的程序来实现其功能。原语是操作系统内核的一个组成部分，必须在内核态下执行。原语的不可中断性是通过在其执行过程中关闭中断来实现的。
|
|
|
|
P、V原语作为操作系统内核代码的一部分，是一种不可分割的原子操作。它们在运行时，不会被时钟中断所打断。另外，在P、V原语中包含有任务的阻塞和唤醒机制，因此，当任务在等待进入临界区的时候，会被阻塞起来，而不会去浪费CPU时间。
|
|
|
|
P原语中的字母P，是荷兰语单词测试的首字母。它的主要功能是申请一个空闲的资源，把信号量的值减1。如果成功的话，就退出原语；如果失败的话，这个任务就会被阻塞起来。V原语当中的字母V，是荷兰语单词增加的首字母。它的主要功能是释放一个被占用的资源，把信号量的值加1，如果发现有被阻塞的任务，就从中选择一个把它唤醒。
|
|
|
|
采用信号量来实现任务之间的互斥，优点有两个：一是可以设置信号量的计数值，从而允许多个任务同时进入临界区；二是当一个任务暂时无法进入临界区时，它会被阻塞起来，从而让出CPU给其他的任务。
|
|
|
|
大多数嵌入式操作系统都提供了信号量的机制，用户可以通过函数调用的方式去使用。
|
|
|
|
|
|
一般来说，一个任务相对于另一个任务的运行速度是不确定的，也就是说，任务是在异步环境下运行的。每个任务都以各自独立的、不可预知的速度向前推进。但是在有些时候，在两个或多个任务中执行的某些代码片断之间，可能存在着某种时序关系或先后关系，因此这些任务必须协同合作、相互配合，使各个任务按一定的速度运行，以共同完成某一项工作，这就是任务间的同步。
|
|
|
|
要实现任务之间的同步，可以使用信号量机制，通过引入P、V操作来设定两个任务在运行时的先后顺序。例如，可以把信号量视为某个共享资源的当前个数，然后由一个任务负责生成这种资源，而另一个任务则负责消费这种资源，这样，就构成了这两个任务之间的先后顺序。在具体实现上，一般把信号量的初始值设为N，N大于或等于0。然后在一个任务的内部使用V原语，增加资源的个数；而在另一个任务的内部使用P原语，减少资源的个数，从而实现这两个任务之间的同步关系。
|
|
|
|
例如，假设有两个任务T1和T2。T1做的事情主要是代码片断A，T2做的事情主要是代码片断B。任务T1和T2同时位于系统当中，相互独立地运行。但由于这两个任务之间存在某种同步关系，要求代码A必须先执行，然后代码B才能执行。例如说，A负责采集信号，B负责对这些信号进行处理，显然，只有当A把信号采集进来之后，B才能去处理。由于在多道程序的操作系统当中，各个任务的执行是相互独立的，系统可能先调度任务T1去运行，也可能先调度任务T2去运行，这是由调度算法来决定的。因此无法保证任务T1肯定比任务T2先执行。但是为了实现任务之间的同步，必须保证，无论是任务T1先执行还是任务T2先执行，从最后的结果来看，代码片断A必须先执行，然后代码片断B才能执行。
|
|
|
|
|
|
在一组任务当中，每个任务都占用着若干个资源，同时又在等待其他任务所占用的资源，从而造成所有任务都无法进展下去的现象，这种现象称为死锁，这一组相关的任务称为死锁任务。在死锁状态下，每个任务都动弹不得，既无法运行，也无法释放所占用的资源，它们互为因果、相互等待。
|
|
|
|
死锁的产生有四个必要条件，只有当这四个条件同时成立时，才会出现死锁。
|
|
|
|
.互斥条件：在任何时刻，每一个资源最多只能被一个任务所使用；
|
|
|
|
.请求和保持条件：任务在占用若干个资源的同时又可以请求新的资源；
|
|
|
|
.不可抢占条件：任务已经占用的资源不会被强制性拿走，而必须由该任务主动释放；
|
|
|
|
.环路等待条件：存在一条由两个或多个任务所组成的环路链，其中每一个任务都在等待环路链中下一个任务所占用的资源。
|
|
|
|
除了资源的竞争之外，PV操作使用不当也会引起死锁，下图是一个例子。
|
|
|
|
|
|
|
|
在系统中，定义了两个信号量S和Q，它们的初始值都是1。两个任务T1和T2，假设T1先被调度执行，它顺利地通过了P（S）操作，并使S的值变为0。假设这时发生了一次时钟中断，任务T2被调度执行。它顺利地通过了P（Q）操作，并将Q的值变为0。接着在执行P（S）操作时，由于S的值已经是0，因此T2在这里被阻塞起来，并让出CPU。然后任务T1重新开始运行，但是当它执行到P（Q）时，由于Q的值已经为0，因此T1也被阻塞起来。这样一来，任务T1和T2都处于阻塞状态，都在等待对方释放信号量，这就是一种死锁的状态。
|
|
|
|
|
|
任务间同步的另一种方式是异步信号。在两个任务之间，可以通过相互发送信号的方式，来协调它们之间的运行步调。
|
|
|
|
所谓的信号，指的是系统给任务的一个指示，表明某个异步事件已经发生了。该事件可能来自于外部（如其他的任务、硬件或定时器），也可能来自于内部（如执行指令出错）。异步信号管理允许任务定义一个异步信号服务例程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次现场切换。
|
|
|
