多线程的应用系统避免死锁

多线程的应用系统避免死锁

应用软件在一个多级的应用系统环境中运行，同步访问共享资源是系统安全性的基本要求。其中对单个资源进行多读单写和对多个资源进行排序锁定是较常见的同步访问控制方式,已经有了很成熟的算法。但软件运行时也经常需要对多个资源进行多读单写的同步访问控制,利用当前已有的算法已无法解决,需要将读者-写者算法和排序锁定模式结合,提供一种既能允许对多个资源分别多读单写,又能避免同时访问一个以上资源时出现死锁状态的算法。1提出问题1.11.1.1读者-作家的算法读者-写者算法是一类经典的同步访问控制算法,它提供了对单个资源进行同时读或者单独写的访问控制方式,并保证无写者死等待。1.1.2免死锁的发生排序锁定模式是为了解决多个线程共享多个资源时如何避免发生死锁的问题。它通过破坏死锁发生的环路等待条件(条件4)来避免死锁的发生。应用该模式时,首先应该对每个共享资源设定全局唯一的优先级,每个客户线程只允许按照指定的顺序对资源进行锁定:一个线程只能锁定比它所持有的所有资源优先级低的新资源,如果所持有资源中有比当前1申请资源的优先级低的资源时,则对新资源加锁的申请不会立即被实施,排序锁定模式将会抛出一个加锁顺序异常,由客户线程捕获该异常,并对之进行处理。1.2熟的算法的求解针对软件经常性并发多读单写操作多个资源而容易造成死锁问题,目前还没有一个成熟的算法可以解决。而读者-写者算法解决了对单个资源的多读单写的同步访问控制问题,排序锁定模式提出了一种对多个资源进行同步访问并避免发生死锁的安全方式,所以将这两个方法结合起来应该是解决对多资源进行多读单写访问控制的良好途径。2资源管理算法排序锁定模式包括三个部分(1)管理资源列表,处理从客户线程发出的资源访问申请,将其转化为对具体资源的加锁请求,并且发现加锁顺序异常,触发处理过程。(2)处理加锁请求,对具体资源进行多读单写方式的加锁操作。(3)处理申请过程中发生的异常情况,即处理加锁顺序异常。资源管理算法应该将客户线程的资源申请对应到资源的实际加锁和解锁操作,所以对于资源的每一种加锁和解锁方式,资源管理算法都应该有对应的处理请求的接口。为了完成对单个资源的多读单写访问方式的控制,我们应该将多读单写算法以多读单写锁的方式实现,包括读加锁、写加锁、读解锁和写解锁四个调用方法。相应的,资源管理算法也应该有四种对应的处理请求方法。算法的结构视图如下图1所示:算法中的ResourceClientPolicy表示资源客户线程,ResourceList表示资源管理器,对于一个客户线程只有一个资源管理器实例,ResourcePolicy是资源的多读单写锁,提供对资源的多读单写方式的同步控制,ResourcePolicyImpl是一个具体的资源类,实现资源的具体业务逻辑,并继承ResourcePolicy获得资源锁。下面我们详细介绍资源管理算法中的三个重要组成部分:多读单写锁,资源管理器和加锁异常处理算法。2.1记录特征应是受锁的同步访问控制多读单写锁算法中加锁和解锁的操作可以封装到单独的方法当中,实际使用中具体的资源类只需自定义对该资源特有的读写操作过程,并且继承该锁以获得对自身的同步访问控制的方法。算法中应该维护一个全局的整数变量,记录当前对该资源进行读操作的线程数量,每调用一次读加锁方法时该变量自增,调用读解锁操作时自减,在写锁加锁时作为判断条件:只有当读者的数量为0的时候,写者线程才能占用该资源,并向其中写入信息。下面给出多读单写锁算法四个锁操作方法的算法描述:2.2加锁资源的存储资源管理器首先需要记录应用程序中当前资源总数和它所管理的所有资源的优先级;同时,因为对加锁顺序异常的处理过程也在资源管理算法内部执行,该过程要求资源管理算法必须知道资源的位置,才能对其进行相应的锁操作,所以资源管理器还应该记录每个资源的地址。在运行过程当中,对这些信息的遍历操作比较频繁,故而采用适当的数据结构存储这些信息,将会提高查询具体资源的效率,从而提高整个算法的执行效率。考虑到每种资源的优先级是全局唯一的,不可能有两种资源有相同的优先级,因此我们可以采用以资源的优先级作为键值的有序数组(以下称之为资源数组)存储以上信息,数组的长度为当前资源总数,资源优先级越高,其资源ID越小,在数组中位置越靠前。当有客户线程向资源管理器发出资源占用请求时,它必须向相应的加锁申请处理方法传递两个参数,一个是该资源的优先级,另一个是该资源指针。加锁方法首先判断对该资源的加锁请求是否满足排序锁定规则:如果满足则对资源进行对应的加锁操作,并将该资源优先级和指针保存到资源数组中其对应的位置;如果请求不满足规则,则转异常处理程序。如果请求解锁则只需给出该资源的优先级,解锁方法遍历资源数组,获得该资源的指针,对于写锁,首先对资源做解除写锁操作,并直接将资源指针释放,表示不再占有该资源;对于读锁,在解锁之后还要判断该资源的当前读者是否为0,是则释放该资源指针,否则不作任何操作。2.3异常处理算法当发现加锁顺序违规时,通常的做法是:解锁所持有资源当中所有比当前申请资源优先级低的资源,然后按照优先级由高到低的顺序从当前申请资源开始重新锁定这些资源。对于读操作和写操作,该算法的逻辑并没有太大区别,因此可以将异常处理过程设计成对读写操作公用的算法,为了判断用户对所持有资源正在进行的是那种操作,以便作出相应的解锁操作,我们用一个有序数组保留了每个所持有资源当前的读者数量,当读者数量大于0时,说明当前客户对该资源正在进行读操作,应该解除读锁,当读者数量为0时,说明当前对该资源应该正在进行写操作,应该解除写锁。当异常处理过程被调用时,首先遍历资源优先级数组,获得当前优先级最低资源的指针,然后判断其读者数量是否为0,根据比较结果作相对应的解锁操作,循环该过程,直到所有优先级低于当前请求资源的资源都已经被释放,然后对当前请求资源进行加锁,最后按照顺序对优先级低于当前请求资源的资源按照排序顺序恢复加锁,在恢复加锁时也应该通过资源的读者数量决定应该进行哪种加锁操作。下面给出异常处理算法描述:以上定义了UnlockHighorderResource()方法,该方法负责对所持有的低优先级资源进行顺序解锁,该方法中getMaxID()方法负责获得资源管理器列表当中当前最低优先级资源(资源ID最大),getResource()方法根据资源ID返回该资源的指针,此后可以通过GetReadCount()方法返回当前该资源的读者数量,以判断应当对该资源解除读锁还是写锁,并调用相应的解锁方法,同时还应该将这个数量记录下来以备恢复加锁时判断应该是加读锁还是写锁。以上定义了RestoreHighorderResource()方法,实现对所持有的低优先级资源进行顺序恢复加锁的过程。上述两个方法共同提供了异常处理算法当中的公有操作,使用时由处理加锁请求的方法调用UnlockHighorderResource()方法对低优先级资源进行解锁,然后对当前申请资源进行加锁(由于加锁请求方法分为读加锁请求和写加锁请求两个,因此它当然知道应该对当前请求资源加哪种锁),之后再调用RestoreHighorderResource()方法恢复对UnlockHighorderResource()方法释放的资源加锁。3基于平台的禁止时间效率算法中用一个ResourcePolicy类来实现多读单写锁,资源类继承ResourcePolicy以获得它定义的StartRead(),EndRead(),StartWrite(),EndWrite()四个多读单写的访问控制方法。ResourceList类实现了资源管理器,其中我们将资源ID和资源指针的信息用vector类型来存储,对比于使用数组的方式,使用vector固然会牺牲一定的空间效率,但是对于遍历操作它比数组的效率要高,因此当资源较多的情况下,算法的时间效率将会获得显著的提高。Semaphore类定义了信号量类的接口,是一个纯虚类,只有两个纯虚函数lock()和unlock()的定义,其子类SemaphoreMFCImpl类使用MFC的semaphore类提供信号量操作的windows平台下的实现方式,从而屏蔽了与平台相关的具体实现信息。ResourcePolicy是通过调用它的lock和unlock操作来实现其StartRead