2 wdq92500 wdq92500 于 2016.03.01 14:22 提问

应用优先队列实现作业的优先调度
  问题描述 
  优先队列priority queue是一种可以用于很多场合的数据结构,应用 堆结构设计并实现一个优先队列。应用该优先队列实现作业的优先调度:
        一个作业ti =(si,ei),si为作业的开始时间(进入时间),ei为 作业的结束时间(离开时间)。作业调度的基本任务是从当前在系统中的 作业中选取一个来执行,如果没有作业则执行nop操作。本题目要求的作 业调度是基于优先级的调度,每次选取优先级最高的作业来调度,优先级 用优先数(每个作业一个优先数pi)表征,优先数越小,优先级越高。作 业ti进入系统时,即si时刻,系统给该作业指定其初始优先数pi = ei - si, 从而使越短的作业优先级越高。该优先数在作业等待调度执行的过程中会 不断减小,调整公式为:pi = pi - wi,其中的wi为作业ti的等待时间: wi = 当前时间-si。一旦作业被调度,该作业就一直执行,不能被抢占, 只有当前执行作业指向完成时,才产生下一轮调度。所以可以在每次调度 前动态调整各作业的优先数。
        编程实现这样一个作业调度系统。
        基本要求
        (1)分别以堆、左高树实现优先队列。
        (2)作业集合中的各作业随机生成,根据作业的s属性和e属性动态调整 作业队列,不断加入作业,作业结束删除作业。
        (3)要对作业调度的结果给出清晰的输出信息,包括:何时作业进入,何 时调度哪个作业,何时离开,每个作业等待多长时间,优先数的动态变化 情况等。

1个回答

caozhy
caozhy   Ds   Rxr 2016.03.07 05:40
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
数据结构: 优先队列的应用
这里介绍一种重要的略为复杂的数据结构“优先队列”.我所提供的不是教学,而是希望提供一个解决类似问题的思路.因此以学习为目的,而不是以实用, 而且涉及到较多的名词概念或术语,对于不懂的建议查找数据结构的书籍,这里考虑到文章的篇幅就不多做介绍. ^^   优先队列(priority queue)是一个以集合为基础的抽象数据类型,每个元素都有一个优先级,对优先队列执行的操作有1) 查找;2) 插
【算法设计-优先队列】优先队列的实现与操作
优先队列是堆排序的一个具体应用。 优先队列分为如下几个操作: 1.INSERT(S,x)把元素x插入到优先队列中。 2.MAXIMUM(S):返回s中具有最大关键字的元素。 3.EXTRACT_MAX(S):去掉S中最大关键字的元素 4.INCREASE_KEY(S,x,k):将元素x的关键字值增加到k,k是不小于x的元素。 优先队列的应用: 1.共享计算机系统的作业调度。最大优先队
任务调度(Schedule)-(优先队列->建堆)
描述 某高性能计算集群(HPC cluster)采用的任务调度器与众不同。为简化起见,假定该集群不支持多任务同时执行,故同一时刻只有单个任务处于执行状态。初始状态下,每个任务都由称作优先级数的一个整数指定优先级,该数值越小优先级越高;若优先级数相等,则任务名ASCII字典顺序低者优先。此后,CPU等资源总是被优先级数最小的任务占用;每一任务计算完毕,再选取优先级数最小下一任务。不过,这里的任务在
作业调度算法总结
在典型的设计中,一个任务有以下三种状态: 正在运行(Running,正在CPU中执行)、待命(Ready,等待执行)、阻塞(Blocked,任务暂停,等待一个事件的发生,例如接收一组数据) 由于CPU在某个时间只能执行一个任务,大部分任务,在大部分时间,处于阻塞或待命状态。可能会有大量项目在待命列表里等待执行,这取决于系统所需的任务数量以及调度器的类型。 一、作业(job)的概念
【每日算法】堆排序&优先队列
堆排序(heapsort)的运行时间为O(n logn),是一种原地排序算法,是不稳定的排序算法。堆基本介绍先直观感受一下,下面就是一个堆:16 7 3 20 17 8什么??上面不就一个数组吗……?!没错,(二叉)堆数据结构是一种数组对象。不过,让我们用另外一种方式来看这个数组:对于表示堆的数组arr[1…n],我们以arr[1]为根,给定某个节点下标i,令其父节点和左右后代节点的下标为:pare
最短作业优先调度算法(SJF算法)的C++实现
题目要求: 在作业调度中,该算法每次从后备作业队列中挑选估计服务时间最短的一个或几个作业,将他们调入内存,分配必要的资源,创建进程并放入就绪队列。与在进程调度中的原理类似。假设有n项作业位于就绪队列中,这些作业的提交时间用数组requestTimes按照提交时间的先后顺序存储,对应的作业服务时间(持续时间)用数组durations存储。采用SJF算法,计算n项作业的平均等待时间。当存在多个相同长
处理机调度算法代码(包括先来先服务,优先级调度,短作业优先,响应比高优先)
处理及调度算法代码 nt counter; /*实际进程个数*/ int fcfs(); /*先来先服务*/ int ps(); /*优先级调度*/ int sjf(); /*短作业优先*/ int hrrn(); /*响应比高优先*/ int pinput(); /*进程参数输入*/ int poutput(); /*调度结果输出*/
先来先服务调度算法和短作业优先算法
操作系统中的先来先服务调度算法和短作业优先调度算法的模拟
调度算法的介绍及优缺点
调度算法是根据系统的资源分配策略所规定的资源分配算法。有的调度算法适用于作业调度,有的适用于进程调度,有的两者都适用。 先了解几个术语 到达时间、服务时间、开始时间 完成时间、等待时间 周转时间:完成时间-到达时间 带权周转时间:周转时间/服务时间一、先来先服务(FCFS)/先进先出(FIFO)调度算法 (1)概念:按照作业/进程进入系统的先后次序进行调度,先进入系统者先调度;即启动等待时
用C语言写的一个最短作业优先调度算法
#include <stdio.h> //定义一个结构体 struct sjf{ char name[10]; //进程名 float arrivetime; //到达时间 float servicetime;//服务时间 float starttime; //开始时间 float finishtime;//完成时间 float zztime;//周转时间 float dqzztime...