COURIER:基于非抢占式优先排队和优先经验重放DRL的边缘计算任务调度与卸载方法

边缘计算(Edge Computing,EC)将计算、存储等资源部署在网络边缘,以满足业务对时延和能耗的要求。计算卸载是EC中的关键技术之一。现有的计算卸载方法在估计任务排队时延时使用M/M/1/∞/∞/FCFS或M/M/n/∞/∞/FCFS排队模型,未考虑高时延敏感型任务的优先执行问题,使得一些对时延要求不敏感的计算任务长期占用计算资源,导致系统的时延开销过大。此外,现有的经验重放方法大多采用随机采样方式,该方式不能区分经验的优劣,造成经验利用率低,神经网络收敛速度慢。基于确定性策略深度强化学习(Deep Reinforcement Learning,DRL)的计算卸载方法存在智能体对环境的探索能力弱和鲁棒性低等问题,降低了求解计算卸载问题的精度。为解决以上问题,考虑边缘计算中多任务移动设备、多边缘服务器的计算卸载场景,以最小化系统时延和能耗联合开销为目标,研究任务调度与卸载决策问题,并提出了基于非抢占式优先排队和优先经验重放DRL的计算卸载方法(Computation Offloading qUeuing pRioritIzed Experience Replay DRL,COURIER)。COURIER针对任务调度问题,设计了非抢占式优先排队模型(M/M/n/∞/∞/NPR)以优化任务的排队时延;针对卸载决策问题,基于软演员-评论家(Soft Actor Critic,SAC)提出了优先经验重放SAC的卸载决策机制,该机制在目标函数中加入信息熵,使智能体采取随机策略,同时优化机制中的经验采样方式以加快网络的收敛速度。仿真实验结果表明,COURIER能有效降低EC系统时延和能耗联合开销。

一类非抢占式非严格周期任务单通道调度问题研究

针对一种特殊的非抢占式非严格周期任务集的单通道调度问题,提出一种启发式搜索的方法,全局遍历来搜索所有的可行解。同时对于某些需要快速反应的应用场景,提出一种快速求解法,其算法复杂度要远低于全局搜索,能在更快的时间内求得可行方案,但可能会忽略大部分的可行解。实验结果表明两算法在任务集调度方面都有其各自的优缺点,可适用于不同的应用场景。

基于关键链的非抢占式多项目调度多属性优化

针对多项目调度中难以实现动态调度和高效调度的问题,从多项目调度整体效用最大化角度,提出基于关键链的非抢占式多项目调度操作模式,构建多项目调度模型.利用正态云模型中云滴的随机性与稳定性的特征改进遗传算法中交叉算子与变异算子的设置方式,并对模型进行数据模拟和算例分析.结果表明,采用非抢占式操作模式,不仅可实现多项目调度的整体效用最大化,而且可实现多项目调度的帕累托改善并提高资源的利用率.

非抢占式EDF算法下周期性任务的最小相对截止期计算

现有的求解周期性任务最小相对截止期的方法均假定任务集是采取抢占式EDF调度算法,并不适用于当任务为基于非抢占式EDF调度算法的场合,如实时通信领域。在分析了非抢占式EDF调度算法的可调度性判定条件基础上,提出了基于非抢占式EDF调度算法下周期性任务最小相对截止期的计算算法。算法通过逐渐增加任务的相对截止期直到使任务集变为可调度的方式,实现某个任务相对截止期的最小化。仿真实验表明该算法具有较好的计算复杂度。

非抢占式实时容错调度

面向嵌入式实时系统中,任务非抢占式实时容错调度问题,得出了任务能够容忍一次故障的条件,以及能够容忍的故障间隔条件;其次,为了减少任务的等待时间,分别在EDF、RM算法中增加了任务可重复次数的判断条件,在相同等待时间或最终期限下,可重复次数少的任务具有较高的优先级。仿真结果显示,基于RM改进的容错算法NP-PBOR-FT性能较好,平均任务失效率比NP-EDF-FT算法降低了44.19%,比NP-RM-FT算法降低了45.87%,比NP-DBOR-FT算法降低了4.43%,任务等待时间比NP-EDF-FT算法降低了60.54%,比NP-RM-FT算法降低了48.09%,比NP-DBOR-FT算法降低了4.09%;最后,利用设计的NP-PBOR-FT算法,完成实际系统中非抢占式任务的容错调度,采用故障注入的方法,对系统进行了验证,结果表明系统满足实时性以及容错要求。

非对称的多队列非抢占优先权排队系统分析

该文对非对称情形下多队列非抢占优先权排队系统的精确解析方法进行了探讨。利用嵌入马尔可夫链理论,以服务员到达队列的时刻为参考点构造出了系统的概率母函数,从而解析出非对称情形下系统的平均周期时间以及一般队列和中心队列的平均排队队长表达式。计算机仿真实验验证了分析的有效性。

带非抢占优先权和可变服务率的离散工作休假排队

主要研究带非抢占优先权和可变服务率的离散工作休假排队系统模型.建立关于两类顾客数及系统和服务台状态的四维离散马尔科夫链,并得到了转移概率矩阵.利用拟生灭过程和高斯-赛德尔迭代法,给出了系统的平稳分布和一些重要的性能指标.通过数值例子分析系统参数对性能指标的影响.构造两类顾客的利益函数分析顾客的均衡行为,根据对社会利益的算例分析,得到了在一定范围内的最优到达率.

对M/M/1非抢占优先权排队平稳指标的分析

讨论M/M/1非抢占优先权排队模型.该模型可以用一个具有可数位相的拟生灭(QBD)过程来描述.对该过程采用生成函数法得到平稳状态时低优先权顾客数分布的概率母函数,以及其逗留时间分布的LaplaceStieltjes变换.所得结论同时也说明了这两个分布都不是PH分布.

非抢占维修优先权下的多级备件库存优化

针对装备保障组织中维修站点维修能力有限的问题,在经典VARI-METRIC理论基础上,首先基于稳态排队理论,考虑非抢占维修优先权对故障件维修过程的影响,建立了非抢占维修优先权下的装备可用度评估模型和多级备件初始库存优化模型;然后,构造了多级保障系统非抢占优先权分配方案的优化目标函数,并利用遗传算法对优先权分配方案进行优化;最后,随后利用边际优化算法对备件库存进行优化。算例分析表明:考虑非抢占维修优先权备件购置费用相比于传统先到先修的降低了37.14%,说明了当维修站点维修能力有限时,合理设置故障件的非抢占维修优先权会降低备件购置费用,提高保障效果。

带有转换时间和阈值的非抢占优先权排队模型

在[3]中,我们研究了在抢占规则下带有转换时间和阈值的两类顾客优先权排队系统.本文就非抢占情形对这样的系统作进一步的研究,同样求出两类顾客队长的稳态联合概率母函数.籍助这些母函数可求出诸如平均队长这样一些重要的系统性能指标.

一种基于非抢占RM算法的可行性判决算法及应用

为中断服务例程建立了任务模型,在该模型的基础上给出了中断服务例程集使用非抢占RM调度的可行性的充分必要条件,并且基于该条件提出了一种新的非抢占RM算法的可行性判决算法。进一步地,给出了如何改进不可调度例程集的方法,并且将该方法应用到一个具体工程项目中,取得较好的效果。

一种基于时间片的非抢占式实时内核在温室控制系统中应用

温室控制系统对多任务处理能力和实时处理能力有较高的要求。介绍了一种基于时间片的非抢占式实时内核的原理和设计要点,指出了其相对于前后台系统和RTOS的优点,并开发出基于该内核的应用于温室控制系统的控制器。

T型非抢占优先权M/M/1排队系统

为了进一步优化认知无线网频谱的接入,在将T作为时间参数引入排队系统的基础上,提出了一种新的T型非抢占优先权排队策略,并将其引入M/M/1排队模型中,系统分析并推导出顾客在系统内的平均等待时间、平均逗留时间以及系统的平均队长.最后通过Matlab软件对顾客平均等待时间进行了仿真模拟.

Symbian OS环境中用活动对象处理非抢占式多任务的安全性分析

分析了当前流行手机操作系统(Symbian OS)中用活动对象处理非抢占式多任务的独特设计思想,讨论了平台安全性相关问题,并阐述了能力、权限、授权、安全标识符和数据锁定等5个安全因素,剖析了异步函数、活动对象和非抢占式多任务等3个基本概念,重点从安全性的角度对活动对象的实现过程进行了比较分析,有助于解决当前手机操作系统中内存小和安全性两方面问题.

反馈后优先非抢占的M/M/1排队系统的等待队长分析

考虑反馈后优先排队非抢占的M/M/1排队系统,固定每位顾客的反馈次数为1次,即每位顾客的服务要求数为2,利用相关文献中系统总服务要求数的分布,推出了系统中等待服务的服务要求数的分布.同时研究了等待服务要求数与等待队长的关系,得出了系统模型的等待队长的分布及平均等待队长.

一类特殊的非抢占式周期任务的调度方法

现实世界中针对许多任务的资源调度分配和使用具有时效性,对该类任务的调度问题目前的研究还较少。针对此类调度问题,分析其特点,明确其与已有调度模型研究问题的区别,提出新的非抢占式周期任务调度模型,并证明了该类问题为NP完全问题。在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种求解近似解的快速求解算法。相关实验表明,提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。

具有共有寿命和取消订货的非抢占优先权排队库存系统

本文研究了具有取消订货和共有寿命的非抢占优先权排队库存系统,其中顾客到达服从泊松过程,服务时间服从指数分布.我们构建了一个水平相依的拟生灭过程(LDQBD过程),并利用Neuts-Rao截断法得到了系统的平稳条件和稳态概率向量,同时给出了一些性能指标和期望成本函数.通过数值模拟,我们得到了最优库存容量和最小成本.最后,我们通过对系统参数的敏感性分析,给管理者提供了一些有益的建议.

非抢占优先权轮询系统特性分析

本文讨论的是一种多站点通信系统的优先权链路调度算法，调度模型采用具有非抢占优先权的轮询机制，队列服务采用完全服务方式。文章利用嵌入马尔可夫链和概率母函数方法，解析出了非对称情形下系统的平均周期时间以及一般队列和中心队列的平均排队队长表达式，并利用计算机仿真实验验证了结果的正确性。

带非抢占优先权和多重休假的M/M/c排队

主要对非抢占优先权和多重休假的M/M/c排队模型进行分析.首先通过描述系统服务流程来研究系统的状态,从而给出三维马尔科夫链.其次求解系统的状态转移率矩阵,并利用矩阵几何解的方法得到稳态平均队长、服务台休假的概率等重要性能指标.再次依据数值算例刻画出重要的性能指标随参数的变化趋势.最后分别构造个人及社会效益函数,并通过分析得到使社会效益最大化的最优参数值.

带启动时间和多重休假的非抢占优先权M/M/c排队

以M/M/c排队模型为依据,主要分析研究带有启动时间和多重休假的非抢占优先权M/M/c排队模型.首先,依据模型描述构造三维马尔科夫过程,并求得转移率矩阵.其次,利用拟生灭过程和矩阵几何解的方法,得到系统的平稳分布,进而求解出一些关键的性能指标.然后,运用数值例子刻画出参数变化对系统性能指标的影响.最后,通过建立个人效益函数和社会效益函数,得到使系统状态达到最优的参数值,从而为系统的资源分配提出合理化的建议.