A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Technique

Most scheduling applications have been demonstrated as NP-complete problems. A variety of schemes are introduced in solving those scheduling applications, such as linear programming, neural networks, and fuzzy logic. In this paper, a new approach of first analogising a scheduling problem to a clustering problem and then using a fuzzy Hopfield neural network clustering technique to solve the scheduling problem is proposed. This fuzzy Hopfield neural network algorithm integrates fuzzy c-means clustering strategies into a Hopfield neural network. This investigation utilises this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration and constrained times (execution time and deadline). Each process is regarded as a data sample, and every processor is taken as a cluster. Simulation results illustrate that imposing the fuzzy Hopfield neural network onto the proposed energy function provides an appropriate approach to solving this class of scheduling problem.       

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

一种新颖的带模糊截止时限的磁盘调度算法

设计了一种新的基于截止时限的磁盘调度算法，该算法支持带多优先级的请求。对于某些实时要求，其截止时限是不确定的或者不精确的，该算法采用模糊集来描述这类不确定性，模糊截止时限的隶属度函数表示对请求完成时间的满意程度。调度的目的是最优的指定优先级，使得截止时限的满意程度最大化。根据请求截止时限的不同，把满意程度划分为若干连续的区间。在每个不同的区间内，每个请求都对应有修正的截止时限，把请求按照其修正的截止时限非减的顺序分配优先级，才能实现请求优先级的最优配置。仿真结果表明该算法能有效的分配请求的优先级，降低请求的丢失率，保证了更多的请求得到满足。     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

基于模糊神经网络的ATM网络业务量智能预测

文章尝试将模糊神经网络方法引入ATM网络的业务量预测中。ATM网络业务源一般是随机产生的时变信号,其模型一般很难描述。文章充分考虑了模糊神经网络的学习功能,通过对相关模型的仿真,能够很好地描述ATM网络中的业务流特性,对多媒体的业务量做出了准确的预测。与传统的神经网络方法比较,具有更好的逼近效果。     

Cost-aware reliability task scheduling of automotive cyber-physical systems

New generation of automotives has become a typical Cyber-Physical System, including various sensors, complex communication networks and distributed computing devices. Manufacturers pay great attention to functional safety and cost control of automotive. High-end computing devices such as electronic control units (ECU) that can perform multiple tasks bring higher reliability and also lead to soaring costs. In this paper, we propose an efficient scheduling algorithm that satisfies cost and functional reliability constraints under multifunctional mixed-criticality task replication execution scenarios. Using the proposed fault-tolerant hardware cost-aware multifunctional safety assurance (FT_HCMSA) algorithm can reduce the deadline miss ratio (DMR) of high-criticality function significantly while meeting the autumotive functional safety and hardware cost constraints. FT_HCMSA uses a fine-grained ECU replacement strategy to optimize task allocation. Our experiments validate that FT_HCMSA can reduce the DMR of high-criticality level functions while meet the requirements of safety and cost.     

基于CloudSim的分类负载均衡调度模型

针对传统的集群调度模型效率低下不足以满足用户需求的问题,本文提出一种基于模糊聚类的分类负载均衡调度模型。首先,构建任务请求的指标体系以完成数学模型的建立;接着,采用基于模糊C均值聚类算法的改进算法对请求分类,即用改进的最小支撑树算法获取初始中心,有效性测度获取其分类个数,BP神经网络算法提高其学习能力;然后,采用两次分类的方法对服务器分类,预聚类对服务器进行功能预聚类,模糊关联聚类按处理负载能力对其分类;最后将分类调度模型在CloudSim下仿真实验,通过对比其他调度算法得到分类调度模型更具适应性和高效性,具有工程指导意义。     

模糊反馈控制实时调度算法

为了解决模糊不确定任务集在不可预测环境下的动态抢占调度问题,应用模糊规则和模糊调度理论,提出一个基于模糊反馈控制的调度算法,并建立相应的调度架构.该架构由基本调度器和模糊反馈控制两部分组成.用模糊调度算法作为基本调度器的调度算法,将任务集按不同优先级等级进行划分,优先级等级高的任务优先调度,从而使得更多的重要任务得到调度;模糊控制器与任务流调节策略一起构成模糊反馈控制部分.仿真结果表明,模糊反     

Globally optimal fuzzy decision trees for classification andregression

A fuzzy decision tree is constructed by allowing the possibility of partial membership of a point in the nodes that make up the tree structure. This extension of its expressive capabilities transforms the decision tree into a powerful functional approximant that incorporates features of connectionist methods, while remaining easily interpretable. Fuzzification is achieved by superimposing a fuzzy structure over the skeleton of a CART decision tree. A training rule for fuzzy trees, similar to backpropagation in neural networks, is designed. This rule corresponds to a global optimization algorithm that fixes the parameters of the fuzzy splits. The method developed for the automatic generation of fuzzy decision trees is applied to both classification and regression problems. In regression problems, it is seen that the continuity constraint imposed by the function representation of the fuzzy tree leads to substantial improvements in the quality of the regression and limits the tendency to overfitting. In classification, fuzzification provides a means of uncovering the structure of the probability distribution for the classification errors in attribute space. This allows the identification of regions for which the error rate of the tree is significantly lower than the average error rate, sometimes even below the Bayes misclassification rate     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

A maximum spanning tree-based dynamic fuzzy supervised neural network architecture for classification of murder cases

In this paper, a hybrid algorithm based on maximum spanning tree and dynamic fuzzy neural network is proposed for classification of murder cases. The proposed classification model of criminal law is useful for judges, lawyers or other people who want to determine the guilt and deliver judgment in their cases. The model is trained and tested for sufficient number of court decisions. The experimental results show that the proposed maximum spanning tree-based dynamic fuzzy supervised neural network algorithm overcomes the problem of slow convergence and large computation caused by artificial neural network and fuzzy neural network algorithms. Comparative studies were carried out for a number of different networks and configurations and reported. Simulations are presented to illustrate the performance of the proposed algorithm.     

基于优先级分类的工业无线网络确定性调度算法

确定性调度技术对于工业无线网络数据的实时性和确定性传输有着重要意义.本文针对工业无线网络数据流本身存在优先级分类属性的情况,基于多信道时分多址接入(TDMA)技术,在分析高优先级数据流对低优先级数据流造成的链路冲突延时和信道竞争延时基础上,对网络进行调度预处理,进而排除参数不合理的网络,并向网络管理者反馈.对于通过预处理的网络,调度算法优先为高优先级数据流的链路分配时隙和信道资源,而对属于同一类优先级的数据流,提出一种基于比例冲突空余时间的调度方案,在满足可调度性条件的前提下,根据各链路的比例冲突空余时间值从小到大依次分配时隙和信道资源.实验结果表明,所提出的调度算法可以取得较高的网络调度成功率.     

ATM网络的一种实时传输调度和信元丢失控制的综合方案

本文提出了ＡＴＭ网络的一种实时传输调度和信元丢失控制的综合方案。     

Bandwidth-aware energy efficient flow scheduling with SDN in data center networks

Nowadays the energy consumption has become one of the most urgent issues for Data center networks. For general network devices, the power is constant and independent from the actual transfer rate. Therefore the network devices are energy efficient when they are in full workload. The flow scheduling methods based on the exclusive routing can reduce the network energy consumption, as the exclusive routing paths can fully utilize all their links. However, these methods will no longer guarantee the energy efficiency of switches, as they handle flows in priority order by greedily choosing the path of available links instantaneously. In a previous work we proposed an extreme case of flow scheduling based on both link and switch utilization. Herein we consider general scenarios in data center networks and propose a novel energy efficient flow scheduling and routing algorithm in SDN. This method minimizes the overall energy for data center traffic in time dimension, and increases the utilization of switches and meet the flow requirements such as deadline. We did a series of simulation studies in the INET framework of OMNet++. The experiment results show that our algorithm can reduce the overall energy with respect to the traffic volume and reduce the flow completion time on average.     

Scheduling parameter sweep applications on global Grids: a deadline and budget constrained cost–time optimization algorithm

Computational Grids and peer‐to‐peer (P2P) networks enable the sharing, selection, and aggregation of geographically distributed resources for solving large‐scale problems in science, engineering, and commerce. The management and composition of resources and services for scheduling applications, however, becomes a complex undertaking. We have proposed a computational economy framework for regulating the supply of and demand for resources and allocating them for applications based on the users' quality‐of‐service requirements. The framework requires economy‐driven deadline‐ and budget‐constrained (DBC) scheduling algorithms for allocating resources to application jobs in such a way that the users' requirements are met. In this paper, we propose a new scheduling algorithm, called the DBC cost–time optimization scheduling algorithm, that aims not only to optimize cost, but also time when possible. The performance of the cost–time optimization scheduling algorithm has been evaluated through extensive simulation and empirical studies for deploying parameter sweep applications on global Grids. Copyright © 2005 John Wiley & Sons, Ltd.     

Reverse Engineering the Neural Networks for Rule Extraction in Classification Problems

Artificial neural networks often achieve high classification accuracy rates, but they are considered as black boxes due to their lack of explanation capability. This paper proposes the new rule extraction algorithm RxREN to overcome this drawback. In pedagogical approach the proposed algorithm extracts the rules from trained neural networks for datasets with mixed mode attributes. The algorithm relies on reverse engineering technique to prune the insignificant input neurons and to discover the technological principles of each significant input neuron of neural network in classification. The novelty of this algorithm lies in the simplicity of the extracted rules and conditions in rule are involving both discrete and continuous mode of attributes. Experimentation using six different real datasets namely iris, wbc, hepatitis, pid, ionosphere and creditg show that the proposed algorithm is quite efficient in extracting smallest set of rules with high classification accuracy than those generated by other neural network rule extraction methods.     

基于模糊策略的ATM网络路由选择

文章综合考虑了用户需求和网络状态,制定出相应的模糊规则,采用模糊逻辑方法完成ATM网络的路由选择。仿真结果表明,该方法具有运算简单,实时性强,硬件实现方便的优点。     

单调时限调度算法的可调度分析

单调时限调度通过定义Di≤Ti放宽了单调比率调度对被调度任务集的限制,使之更加近似于工程实际,但现有的单调时限调度的可调度分析的充分条件十分复杂。文章提出并证明了基于最小处理器利用率上限的单调时限调度的充分可调度条件,大大简化了单调时限调度的调度分析。