所有提交的电磁系统将被重定向到在线手稿提交系统。作者请直接提交文章在线手稿提交系统各自的杂志。

提出一个新的基于两个处理器的CPU调度算法在不同时间段的实时系统

H.S. Behera1 *,Dipanwita Thakur Jajnaseni熊猫2和Subasini Sahoo3
  1. 计算机科学与工程系,转向苏伦德拉赛科技大学(VSSUT),捉弄Odisha,印度
  2. 计算机科学与工程系,转向苏伦德拉赛科技大学(VSSUT),捉弄Odisha,印度
  3. 计算机科学与工程系,转向苏伦德拉赛科技大学(VSSUT),捉弄Odisha,印度
通讯作者:H.S. Behera,电子邮件:hsbehera_india@yahoo.com, dipanwitathakur31@gmail.com和subasini.vssut@gmail.com
相关文章Pubmed,谷歌学者

访问更多的相关文章全球研究计算机科学杂志》上

文摘

多任务操作系统的性能和效率主要取决于CPU调度算法的使用。及时共享系统、轮循(RR)调度给出了最优解,但可能不适合实时系统因为它给更多数量的上下文切换和更大的等待时间和更大的周转时间。本文基于两个处理器的CPU调度(TPBCS)算法,其中一个处理器是专门为CPU密集型过程和其他处理器是专门为I / o密集型进程。这种方法分派过程适当的处理器根据他们的CPU百分比或I / O的需求。过程后分派到各自的处理器,量子计算的时间和过程是他们的破裂时间递增的顺序执行。实验分析表明,我们的算法执行更好的结果通过减少平均等待时间、平均周转时间。

关键字

调度、轮循调度、上下文切换、等待时间、周转时间。

介绍

CPU调度是一个非常重要的任务在多任务操作系统环境。当有多个进程执行,维护一个就绪队列。在两个处理器系统就绪队列是每个处理器的维护。操作系统是一个预定义的程序选择过程的过程在就绪队列中等待和分配CPU的过程。小心注意必须保证公平和分配CPU的过程中避免饥饿。调度决策总是试图最小化平均等待时间、平均周转时间和数量的上下文切换。
这是一个很好的练习安排CPU密集型过程独立于I / o密集型过程,这意味着一个CPU独家专用CPU密集型过程,另一个CPU独家专用I / o密集型进程。这是由于I / o密集型进程不需要等待轮到它们经过几个cpu密集型过程执行。它可以减少对互动的I / O响应时间显著的过程。
在我们的算法使用百分比值分类cpu密集型的过程分成两组和I / o密集型进程。

调度算法:

等使用CPU调度算法调度(先),先到先得最短工作优先调度(SJF),优先级调度等。上述算法在本质上是没有采用基于优先级的设计,也不适合分时系统。的先到先服务(先),进程就绪队列中的第一个到达首先分配CPU。SJF,当可用的CPU,是分配给流程下CPU的最小破裂。如果两个过程有相同的下一个CPU破裂时间,先安排是用来打破的领带。在优先级调度算法的首要任务是给每一个过程和执行过程有最高优先级等等。轮循调度是类似于先调度,但抢占被添加到流程之间切换。一个小的时间单位,称为时间量或时间片是定义和CPU调度程序就绪队列,分配每个进程的CPU的时间间隔1时间量。轮循(RR)调度是其中最流行的调度算法在今天的计算机系统。此外,它是专门为分时系统和多个处理器系统中找到。

b .相关工作:

在最近的过去,一些CPU调度机制已经发展为预测分配处理器。自动调节时间量子轮循算法[2]是基于一种新方法称为动态时间量子,量子反复调整根据破裂时间的运行过程。量子与动态调整轮循调度算法[1]使用工作混合订单[2]中的算法。根据[1],从一个列表中N的过程,这个过程需要最低CPU时间分配时间量子最高,然后从列表中直到第N个过程等等。在第二轮,量子计算剩余的CPU破裂时间的过程和分配过程等等。[2]和[1]都优于RR调度和克服的局限性RR调度的平均等待时间、平均周转时间和上下文切换。算法[3]使用k - means聚类算法的近似相同的过程分组并将它们分派到合适的处理器。一个新的公平份额与加权时间片调度[4]分配一个体重至少每个流程和流程都有破裂时间分配的最大重量。量子计算动态的时候,使用加权时间切片方法,然后执行的流程。[5]计算原始时间片适合每个流程的破裂时间然后动态(智能时间片)是发现与SRTN算法[7]。 Algorithm in [6] is improved by using dynamic time quantum and multi cyclic time quantum

c .我们的贡献:

我们有两个处理器系统提出了一种新的调度算法,首先将cpu和I / o密集型进程分成两组,分派他们两个不同的处理器。然后在每个处理器执行的过程。我们执行的方法给出更好的结果比循环(RR)和动态量子调整轮循调度算法(DQRRR) [1]。而混合订单我们已经工作两个就绪队列中的进程以升序排序的两个处理器和量子计算的时候用我们的方法改变的每一轮执行。

d .论文的组织:

第二部分展示了背景的工作。第三部分介绍了伪代码和说明我们的算法。在第四部分,讨论了实验分析。最后给出了结论和未来的工作在部分V。

背景预赛

术语:

进程是程序在执行。就绪队列的进程等待执行或分配给制造者。破裂时间(bt)是时间,过程需要的CPU来执行。的时间过程称为到达时间(at)到达。时间量子(tq)或时间片的时间给每个进程的CPU。平均等待时间(awt)之间的时间差距是一个过程的到来及其响应的CPU。平均周转时间(atat)之间的时间差距是即时的到来和即时的完成过程。平均响应时间(艺术)是时间开始响应过程。CPU开关的次数从一个过程到另一个称为上下文切换(cs)。PCCPU和PCI / O是一个过程的需求比例分别为CPU和I / O。

b .动态量子重新调整轮循调度算法[1]

DQRRR调度[1]提高了RR调度通过提高周转时间,等待时间和数量的上下文切换。流程安排就绪队列中的工作混合顺序和时间量子发现使用中值的方法。CPU调度程序在就绪队列,分配每个进程的CPU的时间间隔1时间量。再剩下的时间量子计算破裂时间的过程等等。新工艺被添加到就绪队列的尾部。CPU调度程序选择第一个进程就绪队列和分配的CPU 1次量子过程。

建议的方法

该算法TPBCS发现时间量子以智能的方式使两个处理器环境中更好的结果比量子与动态调整轮循调度算法[1](DQRRR)和RR调度。两个处理器的一个是完全致力于执行CPU密集型过程(CPU1)和其他CPU是完全致力于执行I / o密集型进程(CPU2)。该算法分为第一、二部分。第一部分算法分类过程和分派到一个适当的就绪队列。第二部分算法计算时间量子的cpu以动态的方式在每个周期执行。时间量在每一轮反复调整,根据剩余的破裂时间当前运行的进程。我们采取一种方法得到的最优时间量子,百分比值< PCCPU PCI / O >是分配给每个流程。例如,< 75年,25岁>代表一个过程的时间由75%的CPU活动和25%的I / O活动。例如在数据库系统中,一个过程可以很容易地花70%的时间访问硬盘和30%计算。首先在这里短流程执行,给更好的周转时间和等待时间。
图像

算法:

算法的第一部分
图像
这里p[我]是过程,b[我]的破裂时间过程,rb[我]其余的破裂过程中,我的时间。

b .时间复杂度:

任何新鲜到达任务将插入在就绪队列的末尾。每个任务插入将实现在O(1)或常数时间第二部分在第一部分算法算法,排序的顺序进程就绪队列中的O (n1logn1) CPU1, CPU2 O (n2logn2)。然后tq操作分配给每个进程将实现在O (n1)和O (n2)分别CPU1和CPU2。

c .说明:

我们考虑一个例子来演示上述算法,破裂时间序列是:22日31日,53岁,69年,79年分配给进程P1, P2, P3, P4, P5连同会员值< 80,20 >,< 79年,21 >、< 75 >、< 89 >、< 91 >。流程(P1, P2) PCCPU超过70被送入CPU1就绪队列和流程(P3, P4 P5) PCI / O 70多被送入CPU2就绪队列。就绪队列中的进程按升序排列的破裂时间(bt)。然后在每个CPU使用时间量子计算建议公式。使用上述算法计算tq CPU1 26和5和tq CPU2 68,分别为6和5。

实验分析

答:假设

执行的环境,所有的实验都是一个两个处理器的环境,所有的过程都是独立的。时间量被认为是不要超过最大破裂时间。像破裂时间的所有属性、过程、百分数为每个处理器的过程在提交过程之前。

b .实验框架

我们的实验包括几个输入和输出参数。输入参数包括破裂时间,数量的百分比值,时间量和过程。输出参数包括平均等待时间、平均周转时间。

c .实验完成

评估我们的算法的性能,我们在三种不同情况下的一套流程。该算法可以有效地处理大量的数据。在每种情况下我们算法的实验结果与调度算法相比DQRRR[1]和循环(RR)算法。

增加顺序:

我们考虑六个过程p1, p2, p3, p4, p5和p6到达时间0破裂时间28日,52岁,95年,110年,141年,153年分别表一、表二和表三所示显示DQRRR算法的比较结果,RR算法,我们提出了分别CPU1和CPU2 tpc算法。
图像
图像
图像

减少顺序:

我们考虑六个过程p1, p2, p3, p4, p5, p6和p7抵达时间0破裂时间254年,209年,182年,99年,42岁的58和37分别如表4所示。表V和VI显示DQRRR的比较结果,RR和我们提出了分别CPU1和CPU2 tpc算法。
图像
图像

随机的顺序:

我们考虑六个过程p1, p2, p3, p4, p5, p6和p7抵达时间0破裂时间94,52岁,39岁,155年,113年,238年和167年分别见表六世。第九表7和表显示DQRRR算法的比较结果,RR算法和算法分别为CPU1 tpc和CPU2。
图像
图像
图像
图像

CPU利用率:

CPU繁忙的时间百分比(不空闲),经过一段时间,被称为CPU利用率。实时系统的CPU利用率应该是100%。在我们提出的算法的cpu利用率是100%没有任何两个流程之间的上下文切换时间。CPU繁忙仍在执行的过程。

结论

摘要TPBCS新的调度算法,这是一个修改后的轮询调度算法,用于两个处理器系统。一个处理器指定专门为CPU密集型过程和其他CPU指定专门为I / o密集型进程。上面的比较表明,该TPBCS算法提供了更好的结果比[1]中的算法和循环算法[7]的平均等待时间、平均周转时间。该算法可以进一步调查是有用的在提供越来越多的面向任务的结果。

引用

  1. H.S. Behera, r·莫汉蒂DebashreeNayak”提出一种新的量子与动态调整轮循调度算法及其性能分析”,国际期刊《计算机应用(0975 - 8887)卷5 - 5号,10 - 15,2010年8月。
  2. Rami j . Matarneh。“自动调节时间量子在轮询调度算法根据破裂的时间现在运行的进程”,美国应用科学6 j .(10): 1831 - 1837年,2009年。
  3. SanpawatKantabutra、ParinyaKornpitak ChengchaiNaramittakapong“动态Clustering-Based循环调度算法”。诉讼第三通讯和信息技术国际研讨会(ISCIT2003) 03-05 9月,2003年,Hatyai,泰国宋卡。
  4. H.S. Behera、RakeshMohanty Jajnaseni熊猫Dipanwita Thakur, SubasiniSahoo”实验分析一个新的公平份额与等待时间片调度算法实时系统”。全球研究计算机科学杂志》(issn - 2229 - 371 - x),卷2,54-60,2011年2月2号。
  5. H.S. Behera Simpi Patel, Bijaylaxmi熊猫。“一个新的动态循环和SRTN算法使用变量原始时间片和动态智能软实时系统时间片”。国际期刊《计算机应用(0975 - 8887),第一,卷16日54-60,2011年2月。
  6. H.S. Behera, RakeshMohanty、SabyasachiSahu Sourav Kumar Bhoi”设计和性能评估的多循环轮询调度算法(MCRR)使用动态时间量子”全球研究计算机科学杂志》(issn - 2229 - 371 - x),卷2,2,2011年2月。
  7. P.B.GalvinandG.Gange Silberschatz,, 2004。“操作系统”的概念。第七版。,Johnwiley and Sons, USA. ,ISBN:13:978-0471694663,pp:944.