云计算中一种基于休假排队理论.pptx

云计算中一种基于休假排队理论的节能任务调度策略 报告人 王健时间 2015 5 29 目录 一 排队论中常见的概率分布及其数字特征二 一般服务时间M G 1模型三 基于空竭服务的M G 1休假排队系统的任务调度模型四 基于相似任务的调度算法五 实验评价 3 泊松分布及其数字特征设随机变量X所有可能取的值为0 1 2 而取各个值的概率为 k 0 1 2 其中 0是常数 则称X服从参数为 的泊松分布 其均值为 方差为 排队论中常见的概率分布及其数字特征 4 若随机变量t取具有概率密度函数为 其中 0为常数 则称t服从参数为 的指数分布 其分布函数F t 为 其均值为 方差为 指数分布及其数字特征 排队论中常见的概率分布及其数字特征 5 如果随机变量T的概率密度是则称T服从负指数分布 它的分布函数是数学期望为方差为标准差为 负指数分布的定义 排队论中常见的概率分布及其数字特征 6 一般服务时间M G 1模型 顾客到达过程服从泊松分布 M 顾客服务时间服从任意分布 G 7 按下述两种情况讨论 一般服务时间 M G 1 FCFS定长服务时间 M D 1 FCFS 8 标准M G 1 FCFS模型 一般服务时间模型 9 适合下列条件的排队系统到达过程 顾客源无限 顾客单个到来 相互独立 一定时间内到达数服从泊松分布 排队规则 单队 队长没有限制 先到先服务 服务机构 单服务台 顾客服务时间相互独立 分布是一般的 但其期望值E T 和方差Var T 已知 系统容量 没有限制 10 下面来确定当系统达到稳定状态之后 系统的各平稳数量指标 这些指标包括 L 平均队长 Lq 平均排队长 W 平均逗留时间 Wq 平均等待时间 11 Pollaczek Khintchine P K 公式 由P K公式可知 不管服务时间T符合什么样的分布 只要知道 E T 和Var T 就能求出队长 12 由M M 1模型的Little公式可知 13 标准M D 1 FCFS模型 定长服务时间模型 14 适合下列条件的排队系统到达过程 顾客源无限 顾客单个到来 相互独立 一定时间内到达数服从泊松分布 排队规则 单队 队长没有限制 先到先服务 服务机构 单服务台 顾客服务时间为定长分布 系统容量 没有限制 15 下面来确定当系统达到稳定状态之后 系统的各平稳数量指标 这些指标包括 L 平均队长 Lq 平均排队长 W 平均逗留时间 Wq 平均等待时间 16 Pollaczek Khintchine P K 公式 因为服务时间T为间隔D的定长分布 故E T D和Var T 0 由P K公式可知 17 由M M 1模型的Little公式可知 基于空竭服务的M G 1休假排队系统的任务调度模型 独立任务按照泊松流到达云计算系统 第j号任务定义为 任务调度器在全局的调度中心节点运行 它接收动态到达的任务请求 在执行任务调度算法的时候 采用先来先服务的策略 把任务调度到合适的计算节点上 计算节点接收并执行任务 假设正在到达第i号计算节点 的任务服从的泊松分布而且任务到达的时间间隔和每个计算节点的服务时间是独立的 然后 节点的服务时间服从分布函数 它的一阶与二阶矩如下 其中代表节点上任务的平均服务率 因此 平均服务时间为 表示服务时间的方差 每个计算节点表示为一个五元组 基于相似任务的调度算法 TSAST 文献 24 表明一个计算节点的能耗是时间与功率的函数 本文经过分析任务在队列中逗留时间的数学期望和队列系统功率的数学期望 得出 一个计算节点的能耗与空闲时间的阈值和服务时间的方差相关 因此 在云计算系统调度任务时 可以通过减少服务时间的方差和设置合理的空闲时间阈值来节约能耗 在本文中 侧重减小服务时间的方差来优化能耗 并提出了一种基于相似任务的调度算法 TSAST TSAST算法调度任务的思想 对于软实时任务和非实时任务来说 我们把他们调度到具有相似服务时间和较短等待时间的计算节点上 把在一个节点上具有相似服务时间的任务认为相似任务 对于具有严格截止期限的硬实时任务来说 当一个任务调度到一个具有相似服务时间的计算节点上 如果截止期限不满足 则该任务被调度到具有最早完成时间的计算节点上 实验评价 实验环境 使用MATLAB的离散事件模拟工具进行模拟实验 所有的实验在配置为 2 40GHz英特尔酷睿i5CPU 内存4GB 500G硬盘的PC机进行 实验过程 当一个任务到达的时候 记录下它的参数 然后分别根据三种算法把该任务调度到一个计算节点上 任务的到达时间间隔服从的负指数分布 ME3PC算法中 所有计算节点根据他们的负载被分成三个集合 具有较低负载的服务器优先执行任务 具有较高负载的计算机 ME3PC算法采用基于大服务强度的任务调度策略 具有正常负载的计算机 ME3PC算法采用基于较小执行能耗的任务调度策略 当所有计算机过载的时候 ME3PC算法把任务调度到具有最小负载的计算机上 Min min算法中 最小的任务被优先调度 并被调度到的具有最早完成时间的计算机上 TSAST算法 任务被调度到具有相似服务时间和较短等待时间的计算节点上 模拟环境参数 给出了9组模拟实验 每组实验可用一个三元组参数表示 其中m表示任务数 表示任务到达率 k表示计算节点数 实验结果分析 通过四个方面进行评价 系统的平均功率 系统运行任务的平均能耗 总的空闲能耗 任务的平均逗留时间 Min min算法的系统平均功率是最大的 ME3PC算法比Min min算法小 而TSAST算法是最小的 原因是 Min min算法调度任务的主要目的是为了尽可能快的完成任务 而不考虑能耗优化 因此其平均功率高 ME3PC算法考虑能耗优化 但是没有把计算节点的睡眠状态考虑进去 所以 其平均功耗仍然比TSAST算法高 当计算节点的数目少的时候 三种算法的系统运行任务的平均能耗非常接近而且增长缓慢 这是因为所有的计算节点都正在工作而且资源利用率处于偏高的环境 当计算节点的数目增多的时候 平均能耗开始增大 ME3PC算法与Min min算法的曲线比TSAST算法的曲线上升更快 因为TSAST算法在调度任务时 不仅考虑最小的能耗期望 而且使用睡眠状态进一步节约能耗 当云计算系统有相对较少的计算节点时 大部分节点都在运行任务 因此总空闲能耗较少 当计算节点的数目增加时 调度到一个给定计算节点的任务数与计算量降低 空闲能耗增加 结果 总空闲能耗增加 在Min min算法中 计算节点始终保持开机 因此 空闲能耗是最高的 TSAST算法 除了采用类似任务调度策略 计算节点还支持睡眠状态 因此它的总空闲能耗比ME3PC算法的更少 总体来说 每个算法的任务平均逗留时间随着计算节点的增加而有减少趋势 由于Min min算法重点关注任务的完成时间而不考虑