文摘
基于模糊的CPU调度程序的操作系统已经成为极大的兴趣,因为其处理不精确的信息与任务相关的能力。介绍了基于模糊的轮循调度程序的扩展基于模糊逻辑的轮循(VBRR)调度器。VBRR调度程序适用于双层框架。在第一层,调度程序有一个模糊推理系统,有能力处理任务的impreciseness使用模糊逻辑。在第二层,基于模糊逻辑的轮循调度算法(VBRR)安排的任务工作。VBRR调度器的学习能力基于调度程序适应智能时间量的最佳长度。一个最佳的时间量减少调度器通过减少不必要的上下文切换的开销,提高系统的整体性能。工作是使用MATLAB模拟,相比传统的轮循调度程序和其他两个CPU调度程序为基础的模糊方法。仿真分析,结果证明VBRR调度程序的有效性和效率。
1。介绍
计算机系统的多任务环境定义了CPU调度程序的作用。调度器使用调度算法来决定何时安排任务和多长时间。系统设计的目标是设计CPU调度程序以这样一种方式,它给用户更有效和高效的吞吐量(1- - - - - -3]。在本文中,作者讨论了轮循(RR) CPU调度程序。
传统的RR CPU调度程序不能足以知道任务像破裂时间的具体属性,量子的时间长度,到达时间等影响系统的性能。最近的研究工作处理的不确定性属性使用模糊逻辑(4]。这些发展无疑提高系统的性能。拟议的工作扩展了基于模糊RR调度程序模糊逻辑RR调度程序。作者称之为VBRR CPU调度程序。模糊集理论对模糊集理论提高了现实世界的造型,成为一个有前途的工具来处理impreciseness [5]。
VBRR调度程序功能是四倍。首先,它使用模糊逻辑地址impreciseness和不确定性。第二,它动态地提供了一个最佳的时间量子。第三,它减少了不必要的进一步减少调度程序上下文切换开销。第四,最后,它可以提高系统的整体性能的平均响应时间、平均等待时间、平均周转时间和平均周转时间正常化。
VBRR调度程序适用于双层框架。第一层的模糊推理系统本身包含四个单元:模糊逻辑单位,年级的功能单元,数据基本单位,模糊逻辑单元。前两个函数VBRR只表现在这一层。第二层运行调度算法调度的任务。后者两个函数执行在这个特殊的层。
剩下的纸是组织如下。部分2概述了RR调度程序的相关工作。部分3简要描述了模糊集合理论,以及它是如何在模糊集合理论更好的工具。部分4介绍了双层框架RR CPU调度程序。部分5介绍了模拟和结果分析VBRR调度程序的性能与传统的RR调度程序和另外两个CPU调度程序为基础的模糊。最后,部分6总结提出的工作。
2。国家的艺术
轮循(RR)调度是专门设计的多任务系统,用户得到一个印象,多个任务同时运行。这是最简单,最美丽,最广泛使用的CPU调度算法的调度程序(6]。分配一个固定大小的时间量子就绪队列中的每一个任务,每个任务是平等,如图1。固定大小的时间量是CPU时间的一小部分。轮循调度是根据先到先得(先)调度。但先调度是无优先类型的调度而循环赛是先发制人的调度。因此,任务完成后由系统中断时间量子和系统任务分配给暂停执行。后,继续执行任务时量子。
RR调度算法提高了任务的响应时间比其他的调度算法。Racu等人分析了RR调度算法对响应时间在2007年。他们获得最佳情况下的响应时间算法在最坏情况下的响应时间算法(7]。
RR调度算法提供了一个有效的响应时间,但增加等待时间和周转时间由于固定大小的时间量。2008年,公园等人给出了一个基于量子的方法固定优先级调度(8]。他们把量子的概念与优先级的任务(9]2009年;他们进一步集成基于抢占阈值与量子的概念。每次任务分派到CPU,上下文切换,增加了任务执行的开销,提高了执行时间。然而,上下文切换是任何多任务系统的基本特征;加载的过程是一个任务在主内存和存储的另一个任务。在RR调度,上下文切换是重要的关注后,每个任务是抢占时间量子。在计算密集型以及可以增加系统的货币价值的处理器时间。此外,它可以在一个操作系统(昂贵的操作10]。因此,应该有一个专注于设计的调度算法,以避免不必要的上下文切换可能的程度。
上下文切换的数量取决于使用的时间量的大小。小尺寸量子增加了上下文切换,会降低系统的性能6]。Matarneh在2009年提出了一个解决方案的固定大小的时间量。建议的解决方案(萨尔)调整时间量的大小,根据每个任务的CPU破裂值(11]。操作系统无法马上适应这个解决方案是系统需要一些时间观察用户的行为,作为用户的需要破裂时间分析最初由操作系统。Behera等人讨论的问题高等待时间和周转时间与RR调度算法由于使用静态的时间量(12]。2010年,他们提出了一个新版本的RR调度和给它的名称动态时间和调整量子RR (DQRRR)调度算法。Mostafa等人也看着里面的问题时间量的大小。同年,他们引入了一个基于整数规划的方法来决定量子,这样每个任务的时间得到公平的响应时间和也会增加系统的吞吐量,减少不必要的上下文切换(13]。2011年,中午固定时间量子等人提供了一个解决方案,这个新算法。一个算法的思想是相同的;操作系统本身的调整时间量的大小取决于所有任务就绪队列中等待的破裂时间(14]。
因此,系统设计师有一个选项来决定时间量的大小,使其不太长也不太短。例如,考虑一个进程的CPU破裂时间是6.2毫秒,固定的时间量是2 ms。执行3周期后,这个任务将被抢占,分配到就绪队列。任务更需要0.2毫秒,如果抢占0.2毫秒的过程之前,它将完成其执行。因此,其等待时间可能减少,另一个进程的机会是在队列中(15]。时间量的大小随不同的参数,即破裂时间,数量的任务就绪队列中,等等。这些参数可以有不精确或不确定的值。为了让智慧在现实世界中,事情并不完全正确,我们需要一个不同的逻辑。请排队,陈守煜教授给了模糊逻辑(16在上世纪下半叶)。Raheja等人在2012年探索与RR调度的模糊方法。作者提供了一个基于模糊解生成时间量的最佳值。作者称这种方法FBRR调度算法(15]。阿拉姆在2013年还探讨了选择使用模糊逻辑与轮循调度算法来处理不精确的值。他设计了一个模糊推理系统(FIS)决定的时间量子系统的最优,所以每个任务接收到一个公平的系统的响应时间和吞吐量。否则,与固定时间量子系统的吞吐量降低由于不必要的上下文切换。作者称这种方法BFRR调度算法(10]。
模糊逻辑使用一个单一的概念加入价值不能同时考虑用户的证据:证据支持和反对的证据。模糊逻辑有效处理impreciseness使用模糊逻辑不能处理的证据(5,17]。本文提出了一种新的RR调度程序使用模糊集理论。我叫此调度器“基于模糊逻辑的轮循调度程序”或VBRR调度器。VBRR调度器适应动态时间量子的大小根据就绪队列的当前状态;因此它是一种智能调度程序,进一步提高了更大的等待时间,周转时间和规范化的周转时间的任务。VBRR调度器也降低了调度开销减少上下文切换的次数。最后,这个工作比较的性能与传统的RR VBRR, FBRR, BFRR方法。
3所示。模糊集理论
许多数学家和研究人员提供一个解决方案来处理模糊性和impreciseness知识。陈守煜教授(16)引入了一个新颖的方法,即模糊逻辑。在模糊逻辑中,每个元素都有一个单级加入间隔(18]。有许多的广义形式的模糊集理论由不同的作者在文献中讨论。Atanassov [19]介绍了直觉模糊集理论。他扩展模糊成员分为两个功能:会员和nonmembership在相同的时间间隔19,20.]。pswlak [21)描述另一个impreciseness称为粗糙集方法。在此方法中,impreciseness不是表达的单身会员但表示为一双集提供的上下近似集。上下近似给出的信息元素无疑属于集合的元素可能属于集合,分别。高斯教授和Buehrer [5)介绍另一种方法在模糊集合理论,称之为模糊集理论。他们分区的概念单一成员值为两个值:一个代表值和另一个代表值。他们指出,模糊集理论不能单独考虑反对和支持值甚至不能同时使用它们。模糊集理论与模糊集理论,让我们考虑论域。
定义1(模糊集)。一个模糊集在被定义为一对在哪里在哪里。为每一个对象,该值代表对象的隶属程度在如图2。如果该值的更对1,对象更多的属于一组(16]。
定义2(模糊集)。一个模糊集在特点是两个隶属度函数:真理隶属函数和一个false-membership函数,在那里是一个年级的下界的会员吗来自“证据”,是一个下界的反对源自于“证据反对”,如图3,总这两个独立的成员值不能超过1;也就是说,。
定义3(模糊值)。会员的等级在模糊集是有界的子区间的的时间间隔代表的“模糊的价值”在(5]。
3.1。都是集理论不同吗?
让宇宙的话语,破裂时间的收集活动任务的操作系统。让是一个模糊的所有宇宙的“高破裂时间任务”,让是一个模糊集的“高破裂时间任务”。假设一个智能代理显示会员的价值的元素在模糊集他的专家知识潜力。相反,另一个智能代理建议独立两个成员值和相同的元素在模糊集通过自己的专家知识潜力。的学位的true-membership价值吗和的false-membership价值吗在模糊集。人类代理和有知觉的限制,评估,和工作能力与现实生活的情况。在模糊集的情况下,没有进一步检查会员的价值。在第二种情况下,代理建议独立成员的值和并进一步检查通过保持约束,。如果不满意,代理可以思考和改组评估。
4所示。VBRR CPU调度程序
VBRR CPU调度程序适用于双层框架如图4。在第一层,调度器模糊推理系统(22- - - - - -25)进一步四个模块。这一层基本上处理impreciseness和不确定性活动任务的系统。此外,它提供了一个最优值时间量子第二层调度器的调度算法。VBRR调度算法调度的任务对于一个给定的时间量,并使用这一次量子来改善系统的性能。
接下来的小节描述了层的细节。
4.1。模糊推理系统(VIS)
我们的VIS包含四个单元,如图5如下:(我)模糊逻辑单元。(2)级功能单元。(3)数据的基本单位。(iv) 模糊逻辑单元。
以下4.4.1。模糊逻辑单元(VLU)
VLU需要输入破裂时间()从数据库和执行vaguification过程22]。Vaguification流程映射的输入参数模糊值:true-membership ()和false-membership ()。它认为目前的就绪队列处理不确定性和impreciseness的任务。当任务到系统中,系统不能完全知道任务的实际属性;因此,VLU认为最大和最小破裂时间的值出现在就绪队列来处理具体的当前值的偏差。此外,VLU也在考虑静态时间量子(),最初是由系统分配。基于我们所有这些值,模糊逻辑单元计算使用(1),使用(2): 这两个和必须满足以下公理:公理1:。公理2:。公理3:。公理4:。
4.1.2。级功能单元(GFU)
GFU评估模糊值的精确度。级函数应用于成员的值和从VLU接收,在吗 在这里代表了品位价值。以来,在模糊集合理论,这两个函数之和不能大于1,分数值也应该满足以下axiom如图6:Axiom 5:。
4.1.3。数据的基本单位
它存储的所有相关信息的任务像破裂时间,到达时间,当前活动任务,最大和最小值的破裂时间,平均破裂时间,等等。所有其他单位从数据库中提取所需的当前信息。
4.1.4。模糊逻辑单元
模糊逻辑单元最后分数值映射到输出值,也就是说,时间量子的最佳值。时间量的大小可以使用计算 这种动态时间量取决于品位值,静态时间量子,活跃任务就绪队列中。它从数据库中提取数据。在下一节中,作者讨论了2层如何使用这个动态的时间量。
4.2。VBRR调度算法
在我们的提议VBRR调度算法,任务分类根据其破裂,这任务用最短的时间将早从就绪队列中删除。最佳时间量子计算使用前一节中定义的活力和所有活动任务直到完成执行。作者讨论了算法在算法4算法的伪代码和相应的伪代码1和盒子1,2,3。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
算法4。
初始化变量,,平均破裂时间、最大破裂时间和最小破裂时间出现在就绪队列。
初始化变量和。
递增的顺序排序就绪队列破裂时间。
量子计算时间VIS(部分4.1)。
根据轮循调度和执行的任务调度算法使用计算直到就绪队列是空的。
如果一个新任务到达时,重复步骤来。
计算的等待时间、响应时间、周转时间,规范化的周转时间为每个任务。
最后计算的平均等待时间(AWT),平均响应时间(艺术)、平均周转时间(ATT),归一化平均周转时间(ATT)和总上下文切换(nc)。
5。仿真和结果
作者分析了提出的性能与RR, FBRR, BFRR调度算法。对于每一个比较,选择集的任务被认为是,计算每种情况下的性能指标。结果证明VBRR具有更好的性能比其他三种算法。她展示了一个示例任务将显示所有的调度算法的详细的性能分析的帮助下甘特图。
5.1。样本任务设置
假设一组五项任务破裂时间(,,,,)。为了简单起见,所有任务的到达时间被认为是0。
5.1.1。使用RR调度
假设静态时间量由系统分配2 ms。任务的调度顺序使用如图7(一)。
(一)
(b)
(c)
5.1.2中。使用FBRR调度算法
同样,时间量子示例任务集的大小后应用FBRR调度方法= 2.6 ms。任务的调度顺序FBRR算法如图7 (b)。
5.1.3。使用BFRR调度算法
应用BFRR调度算法后,时间量子示例任务集的大小= 2.5 ms。任务的调度顺序BFRR算法如图7 (c)。
5.1.4。使用VBRR调度算法
VBRR算法首先初始化以下变量: 然后,VIS返回真正的-和false-membership函数如下考虑: 在那之后,它计算如图8通过使用和: 然后,量子的时间是计算 任务计划。调度任务顺序如图9。
5.2。性能指标
评估VBRR调度程序的性能,作者选择了所有主要的性能指标如下讨论。
定义5(平均等待时间)。等待时间是任务的总时间在就绪队列中等待执行。让我们考虑,当任务已经抵达系统到达时间和任务有CPU时开始时间。等待时间可以计算的 RR调度,任务抢占和恢复执行多次,直到任务完成执行。为进一步转变,开始时间作为下一个开始时间和到达时间时最后一次执行的任务。计算出的总等待时间是添加一个任务使用的所有等待时间(9): 平均等待时间的等待时间计算就绪队列中的所有活动任务使用(10)。这是计算的 在这里,活动任务的数量。CPU调度程序的性能取决于平均等待时间。减少AWT被认为是调度程序的性能改进。
定义6(平均响应时间)。响应时间是第一个任务的开始时间从系统它的到来。它代表了第一次任务的时候有CPU。这是计算的 无优先的调度算法,等待时间和响应时间返回相同的结果。平均响应时间计算所有活动任务的响应时间使用(12)。这是计算的
定义7(平均周转时间)。周转时间是任务的总寿命这意味着一个任务的总时间需要完成其执行。它可以计算的
这里,CPU破裂时间表示任务所需要的时间和等待时间计算使用(9)。
平均周转时间计算的周转时间就绪队列中的所有活动任务使用(14)。这是计算的
定义8(归一化平均周转时间)。规范化的周转时间表示的相对延迟任务。它只是一个周转时间比破裂时间。这是计算的 归一化平均周转时间计算的标准化的周转时间就绪队列中的所有活动任务使用(16)。这是计算的
定义9(上下文切换)。上下文切换是一种机制,紧随其后的是CPU从一个任务切换到另一个任务在多任务系统。保存和加载计算机寄存器。它允许多个任务运行;基本上它在多个任务共享CPU。上下文切换是计算密集型和不执行任何有用的任务,所以设计的重点是优化上下文切换的次数。
甘特图如图7和9,每个调度算法的性能指标计算使用(11),(13),(15)和(17)。
所有的图表示例任务设置如图10说明性能指标的降低值从RR VBRR调度。在图10 (f),在轴的图表,“1”代表RR调度程序,“2”代表BFRR调度器,“3”代表FBRR调度器,“4”表示VBRR调度器。从图,我们可以比较这四种算法的性能。有一个减少性能值在“4”,证明了改进VBRR比其他三种算法的性能。因此,VBRR调度程序具有更好的性能。
(一)
(b)
(c)
(d)
(e)
(f)
本文认为多个任务集,以更好地评估VBRR调度程序比其他三种方法的性能。在这部作品中,作者说明的性能结果的帮助下15任务集。
数据11,12,13,14,15显示平均等待时间、平均响应时间、平均周转时间、平均周转时间正常化,分别和上下文切换的数量。VBRR algorihm有值最低的所有性能矩阵。从这些图表中,我们可以得出这样的结论:VBRR算法具有更好的性能在其他三个算法:RR, FBRR, BFRR算法。
VBRR调度器提高CPU调度程序的性能主要由三个原因。首先,它涉及相关impreciseness uncertainity和任务。其次,它提供了一个动态的环境中执行任务的分配动态时间量。第三,它可以提高系统的性能,减少平均等待时间,平均周转时间,平均归一化把aroound时间和数量的上下文切换。
6。结论
正如上面所讨论的,轮循调度算法提高了任务的响应时间,但增加等待时间和周转时间。此外,时间量子扮演关键角色的大小RR算法的性能。规模较小的数量可以增加上下文切换,使调度器的表现更糟。必须有一个技术内部CPU调度程序,它允许它动态地计算时间量的大小,而不是一个固定大小的时间量。这项工作提供了一种解决上述所有问题RR调度。作者介绍了一个基于模糊逻辑的轮循CPU调度程序。VBRR第一层,一个模糊推理系统设计任务的处理不精确的参数如破裂一次,静态时间量子考虑活动任务的当前状态。基于当前的情况,这个模糊推理系统最终生成的时间量的最佳值使得调度器在动态环境下工作。在第二层,介绍了一个基于模糊逻辑的轮循调度算法调度的任务。作者评估VBRR算法的性能在多个任务集和RR的性能相比,BFRR, FBRR调度算法。 Simulation results illustrate that the VBRR scheduler improves the performance in terms of average waiting time, average turnaround time, and average normalized turnaround time by maintaining the average response time. It consequently improves the performance of the system by reducing the number of context switches.
相互竞争的利益
作者宣称没有利益冲突。