一种基于消息槽的K资源互斥算法

时间:2022-05-02 04:08:36

一种基于消息槽的K资源互斥算法

摘要:在分布式操作系统等一些有多个进程同时活跃的应用中,必须妥善解决不同进程对资源的需求,即同步与互斥问题。文章提出了一种基于消息槽的K资源互斥算法,介绍了该算法的原理,详细描述了该算法的运作过程,并进行了深入的分析。分析结果表明,该算法能够有效地满足K资源分布式环境下同步与互斥的要求。

关键词:K资源互斥;进程;消息槽;算法

引言

关于资源互斥以及K资源互斥的问题,有很多算法已经被提出来了,其中有一些还是相当不错的,比如基于令牌的K资源互斥算法和基于仲裁集的K资源互斥算法等。本文在分析吸取他人成果的基础上,提出了基于消息槽的K资源互斥算法,下文将对该算法进行描述并进行讨论。

1 K资源互斥算法

所谓消息槽,就像一个大卡车,卡车上分成了很多部分,每一部分可以容纳―个货物;当有人要把自己的货物给别人时,他就等着这个大卡车的到来,然后在车上找到一个空闲的货位,把货物放上去;大卡车继续往前,到了收货人那里,收货人把货物卸下来,原来的这个货位也就再次成为可用的了。

这里所说的消息槽,就像这个大卡车,槽中共分出K槽位,每个槽位代表对一个资源的操作情况,即该资源目前是否被使用。当一个节点要使用资源时,就等着消息槽的到来,然后在其中找出若干空闲的槽位,并声明,这些资源已被占用。使用完之后,再将这些槽位释放。

1.1 前提与假设

(1)系统中的所有节点组织成一个环形结构,消息槽,就像一个令牌,沿着这个逻辑环在系统中循环往复地传送。

(2)消息槽中共有K槽位,相应的,系统中有K资源,每个槽位代表对一个资源的使用情况。初始时,每个槽位的内容都为空。

(3)在消息槽的末尾,另设一项数据,记录当前别的某个节点所需要的资源数。平常该项数据固定为0,当某个节点发现消息槽中空闲的资源数不能满足自己的要求时,就把这一位填上自己所需要的资源数,等到释放资源时,再将这项数据重新清0。

(4)为防止某些节点长期占用资源,导致另一些节点被饿死,并为提高资源的利用率,采用时间片(比如消息槽转了n圈)的方法,当一个节点使用资源持续一定时间后,必须将资源释放,若还要使用,则需重新申请。

1.2 算法的运作过程描述

(1)请求资源

若节点i申请使用a个资源,当i等到消息槽到达时,如果消息槽中空闲的槽位数能满足自己的要求,即空闲槽位数f>=a,并且消息槽的末尾数据项为0,或者消息槽末尾数据项为b,但f>=a+b,则节点i从这f个资源中任选a个,并在他们对应的消息槽槽位中填上自己的进程号,表明这些资源已经被占用了。同时,如果节点i曾经将消息槽的末尾项数据填上的话,那么,将这项数据清0;否则直接使用资源,不必考虑消息槽的末尾项数据。

如果f

若f

(2)释放资源

如果节点i完成了对资源的使用,那么等到消息槽到达后,将自己所申请资源所对应的消息槽中的槽位清空,表明这些资源又成为可用的了。当一个节点连续使用某些资源达一定时间后,该节点必须进行资源释放过程,若还需使用,需要再次进行资源申请过程。

(3)不中请,也不释放资源

消息槽到达后,节点不作申请,并释放操作,槽往下一个逻辑节点传送。2算法运作实例

上面给出了该算法的形式化描述,为便于理解,下边将结合一个例子具体说明。 在一个系统中,共有7个进程节点,6个共享资源。这7个进程通过上边的算法,来对这3个资源进行互斥访问。

以后,这个系统就按照上面的算法,不断地运作下去,直到断电或者人为的切断。

3 分析与总结

该算法满足了互斥的要求。因为只有拿到资源的节点才能进入临界段,当系统剩余资源不能满足新的请求时,节点将申请不到资源,即同时处于临界段的节点所占用的资源总数不会大于K,所以算法可以满足互斥的要求。 这个算法是不存在死锁的情况的。因为节点要么一次拿到所需的所有的资源,要么一个资源也拿不到,不会出现占有了一些资源,却还在等待另一些资源的情况,也就是说,不可能发生死锁的条件。

另外,这个算法也不存在节点饿死的情况。因为如果一个进程需要的资源数较多而无法立即得到满足的话,那么它可以在消息槽中加以声明,这样别的节点就会“让路”,等保证了它的请求得到满足后,别的节点才会去申请资源。所以,任何需要较多资源的进程,都会在一定的时间后得到所需要的资源,不会出现一个需要较多资源的进程一直处于等待别的进程释放资源的状态。

此外,该算法的资源利用率也还比较高,虽然存在一点资源浪费,但由于有时间片限制,不会出现长时间内有大量空闲资源不能使用的情况。而且,与几种较成功的K资源互斥算法相比,资源利用率相差不大。

4 结束语

综上所述,该算法实现了K资源的互斥,不存在死锁与饿死情况,并且资源利用率较高,是一个满足了各方面要求的算法。

上一篇:农村劳动力技能培训系统的UML分析和设计 下一篇:《VFP语言及程序设计》课程建设