分布式并行操作系统中调度的研究和实现

分布式并行操作系统中调度的研究和实现

刘流[1]2002年在《分布式并行操作系统中调度的研究和实现》文中研究表明随着计算机技术的广泛应用,对分布式并行操作系统的需求越来越大。分析当前国内外操作系统的发展趋势,我们迫切需要开发一个分布式并行操作系统。因此,本课题以开放源码的Linux操作系统为基础,对它进行改造,开发出分布式并行调度系统。 本论文首先介绍了分布式并行操作系统的概念和特点,以及设计分布式并行操作系统需要注意的问题。接着专门讨论了分布式并行操作系统中的调度,主要是处理机的分配算法,并对若干种现有的调度算法进行了深入分析。论文的主要部分是关于分布式并行调度的设计与实现,在介绍了分布式并行操作系统的设计结构后,开始主要介绍分布式并行调度的结构组成。对其中的每一个组成部分都分别介绍了设计思想和实现方案。最后,论文从响应时间和负载均衡两个方面的测试数据对分布式并行调度的性能进行了评估。

高新成[2]2016年在《基于云计算的逆时偏移数据处理方法研究》文中认为随着传统一些构造简单的油气藏逐渐减少,油气勘探难度日趋提高,主要表现为地层倾角大、储层埋藏深和介质纵横向速度变化剧烈等,因此,油气勘探对偏移成像方法的计算速度与精度的要求也日益增加。目前,迭前逆时偏移被认为是精确获得复杂构造的内部映像最有效的方法,但在整个偏移成像数据处理过程中存在着计算量和存储量巨大等问题,导致其难以大规模的应用于工业生产。如何降低地震数据存储量和提高计算效率是油气勘探偏移成像中重点研究的问题。目前主要采用集群计算方式实现地震数据的高性能处理,但集群计算受到资源限制,并且建设成本高,很难得到广泛的应用。近年来,随着云计算技术的发展与成熟,为逆时偏移提供了一种新的数据存储与管理的有效方法。本文分析逆时偏移数据处理特点及应用需求,在剖析国内外数据处理与云计算等技术和方法的基础上,提出一种基于云计算的逆时偏移数据处理方法,提供更加广泛的高性能计算应用服务。首先,设计基于云计算的逆时偏移数据处理整体架构模型,并分析模型中待解决问题;其次,针对这些问题,对云环境下地震数据分布式存储方法、云环境下数据并行处理方法和云环境下任务调度算法等内容展开深入研究,寻求解决方法,为整体模型提供技术支撑:最后,根据地震资料偏移成像业务需求,研发逆时偏移成像系统,将其应用到云环境中提供服务。主要研究内容如下:1、提出云环境下逆时偏移数据处理的整体架构模型C-RTMDPM针对逆时偏移数据处理特点和应用需求以及存在问题展开研究,重点研究云计算架构及其数据处理的关键技术,设计云环境下逆时偏移数据处理流程:提出一种适合云环境下逆时偏移数据处理整体架构模型(C-RTMDPM),详细描述模型中各层次的功能和待解决的问题;通过引入云环境下分布式存储、并行计算和任务调度等相关技术,实现对逆时偏移数据高效的存储和处理,为逆时偏移数据处理提供新的方法。2、重点研究C-RTMDPM中数据存储、数据处理和任务调度方法首先,研究云环境下地震数据的分布式存储方法。通过对地震数据的存取特点分析,引入分布式云存储思想,从数据存储结构、数据分配策略和节点选择机制等多方面考虑,设计云环境下地震数据分布式存储结构模型:并在模型基础上对地震数据分布式存储策略展开深入研究,设计基于节点动态选择的数据存储算法,实现云环境下地震数据的高效存取。其次,研究云环境下逆时偏移数据的并行处理方法。通过对逆时偏移数据并行处理特点分析,根出逆时偏移数据分布式式处理流程和基于粒度划分的并行数据处理方法;利用GPU计算优势,设计基于CPU/GPU协同逆时偏移计算和多GPU卡联合计算的工作模式;结合云计算MapReduce编程模型,提出一种云环境下GPU-MapReduce并行计算模型,实现云环境下多GPU节点间协同并行工作的高效数据处理机制。最后,研究云环境下任务调度优化策略。通过分析目前常用任务调度算法的优缺点及其适用范围,重点研究遗传算法和蚁群算法,结合逆时偏移计算中大规模任务调度需求,提出一种适合云环境下的遗传-蚁群混合优化算法的任务调度策略。该策略融合遗传算法和蚁群算法双重优点,实现云计算任务调度的高效执行,同时在系统负载均衡方面也有较好的性能。3、云环境下逆时偏移数据处理方法实证分析基于云计算的逆时偏移数据处理方法,结合数据分布式云存取模型、数据并行处理方法和任务调度优化策略等研究成果,开发迭前逆时偏移成像系统,为逆时偏移数据处理提供可视化界面,并将系统应用到云环境中。通过实验表明,系统利用多节点并行处理,不会影响成像精度,能够提高偏移成像的计算效率。研究结果表明,本文提出的基于云计算的逆时偏移数据处理方法能够较好的解决当前地震数据处理存在的数据存储与计算问题,同时对处理其他地震资料应用提供了高效的数据存储、数据管理和高性能计算服务。

邱元杰[3]2001年在《电网自动化分布并行操作系统中智能化任务调度的设计与实现》文中研究说明电力产业是国家的基础能源产业,随着科技的发展,其自动化系统也在不断的发展。基于对现有应用环境的分析,我们发现具有高可靠性、高性价比、高可扩展性和高性能的分布式并行计算机自动化系统具有极大的应用前景。为了获得这样的系统,我们基于Linux系统开发了具有自主版权的分布式并行操作系统,以便在这个系统上开发电网自动化系统。 本文首先介绍当前的分布并行系统的发展情况和电网自动化系统的发展情况,从而提出了电网自动化系统对分布并行操作系统任务调度的需求;接着讨论分布并行操作系统中任务调度的问题、矛盾和常见算法;然后提出了衡量任务调度算法好坏的几个指标,并以此分析了投标算法的性能,提出了改进的意见。 本文重点描述了在电网自动化分布并行操作系统中使用的智能化任务调度,包括任务调度模型、任务调度算法、节点负载衡量和镜像执行的处理。然后介绍了任务调度的实现情况。 本文最后介绍了系统测试情况。就系统的调度时延、可靠性、有效利用率和负载平衡情况进行了测试,并给出了测试结果和说明。

吴齐跃[4]2016年在《教育部数据中心数据管理优化策略研究》文中提出针对教育数据的快速增长和巨大分析需求,考虑信息安全和基础网络、软硬件资源等因素制约,本文研究教育数据存储的优化管理、任务调度、容错部署等问题,以降低教育数据在管理上的总体成本,提升系统效率和可靠性。论文的主要研究成果有:(1)针对教育数据中心的传统竖井式建设模式成本高、无差别数据存储造成存储空间利用率不高的问题,选取在成本和横向扩展能力上更合适的分布式并行处理方式,提出了基于相关性的列组合聚类及列组合配置策略。在界定搜索查询热度值的基础上构建带有查询热度值的数据列组合,考虑集群中节点负载情况,提出了最小存储成本策略,在降低存储空间成本的同时有效提高教育数据查询分析效率。(2)针对教育数据查询分析面对的巨大压力和响应要求,对教育数据分析任务进行量化和优先级划分,综合考虑服务成本,量化节点分析承载能力,提出了“基于综合效用的教育数据调度模型”。基于系统的整体负载率,提出了优化的任务调度优化策略。(3)针对教育数据的列组合特性,提出数据重要性的界定方法,基于节点负载和数据重要性提出了数据选择性恢复策略,提高了系统的可用性。(4)针对教育分析系统分布式数据节点故障问题,提出了节点故障下资源优化部署模型和部署策略,保证数据的完整性和可用性,并给出了教育数据中心的运维保障策略,以提高系统的服务可靠性。

蒋建春[5]2011年在《异构多核嵌入式软件关键问题研究》文中进行了进一步梳理如何充分利用异构多核处理器的异构特性,将单核的应用软件快速的移植到多核处理器上以及快速地开发基于多核处理器的应用程序是多核处理器应用中面临的主要问题。而解决这些问题的方法要求主要集中在多核软件等关键技术研究上,只有开发出与异构多核硬件相适应的操作系统及其应用软件,才能真正地发挥异构多核处理器的性能。由于异构多核处理器中不同性质程序在不同内核的执行效率存在差异,且应用系统存在功耗、效率、实时性等要求,这就要求操作系统能够对任务进行有效的管理,如分配调度、通信、同步等,以实现多核处理器的最大化利用。而要实现这些功能必须针对异构多核处理器特点研究和设计相应的操作系统架构、调度算法、通信与同步机制等关键技术。传统的多处理器和分布式计算机与异构多核处理器在架构和通信机制上存在巨大差别,相应的分布式操作系统也不适用于异构多核处理器,特别是在嵌入式系统领域。本课题针对嵌入式系统领域,通过研究异构多核处理器的结构特点,分别在操作系统架构、任务划分、异构核间的任务分配以及同构核间动态任务调度等几个关键问题方面进行了大量深入的研究,主要完成了以下工作:1.研究了异构多核的操作系统架构针对多处理器系统的分布式结构以及应用于同构多核系统的主从式结构操作系统不能解决异构多核处理器的实时调度和效率问题,本课题提出一种适用异构多核处理器的多主模式实时操作系统架构。这种架构将通信总线中的多主模式引入多核操作系统架构中,采用对称式结构及组件模式设计操作系统模型,使多核处理器中每个内核都可以作为主核实现对资源、任务的实时管理,提高系统性能,同时可以解决主从式操作系统存在的由于处理器核增多而带来的主内核不能满足系统性能要求存在的瓶颈问题。通过这种单一架构模型可以进行灵活配置适应不同结构及功能要求处理器内核,降低操作系统开发难度。2.研究了异构多核处理器的任务划分问题任务的调度与任务的属性、粒度、任务之间的关系等因素密不可分。异构多核的任务划分是多目标优化问题,怎样针对具体的任务执行环境进行任务分割,使任务在粒度大小、通信调度花费、并行化处理、负载均衡等方面得到一个有效的综合,从而通过调度获得系统的最大执行效率,是任务划分需要解决的关键问题。本课题从任务本身属性和调度两个方面针对异构多核处理器的任务划分中的重要影响因素进行分类分析,提出一种基于聚合性的微粒群分层任务划分方法,通过参数匹配,获得一个较好的划分结果,从而提高任务调度和执行的效率。3.研究了异构多核处理器的任务静态调度问题在异构多核处理器中,任务有最小最大完成时间、负载均衡、最低功耗等要求,异构环境下的任务分配和作业调度问题往往是局部目标和全局目标是相互制约,不能同时满足,任务静态调度被证明是一个NP-Hard的组合优化问题。本课题针对异构并行系统的作业调度和任务分配问题进行研究,提出一种基于Sufferage启发式算法和DPSO(Discrete Particle Swarm Optimization)算法的混合离散微粒群SDPSO (Sufferage Discrete Particle Swarm Optimization)独立任务分配算法,改进DPSO算法效率和搜索精度。由于实际的任务之间存在耦合性,针对独立任务设计的静态调度算法不能很好解决非独立任务的调度问题。因此,本课题在SDPSO算法的基础上,根据任务划分实际存在的耦合性,研究并提出一种基于耦合性的SDPSO静态任务调度改进算法。4.研究了异构多核中同构核间的任务动态调度问题在异构多核处理器中,有可能存在多个同构核,在这些同构核中的任务除了进行任务的静态分配以外,还存在运行过程中的动态调度问题。在动态调度中主要存在基于任务复制和基于表的动态调度算法,而基于任务复制的动态调度算法对存储空间要求较高不适合实时系统。本课题针对嵌入式系统并行同步任务的实时性要求在动态表的基础上提出一种基于任务划分的最小最大关键点执行时间MMKPT(Min-Max Key Point Time)算法,该算法根据同步任务的同步执行时间点和任务之间的耦合性对就绪任务和执行内核进行选择和调度,以满足嵌入式系统的实时性要求。通过这些关键技术的研究工作及成果,可以为异构多核处理器的实时操作系统的研究与开发提供一些帮助和参考,以促进异构多核处理器的应用推广。

伍智锋[6]2003年在《分布式飞行仿真技术研究》文中提出本文以航空航天飞行器(如导弹、运载火箭、空间站等)为研究对象,结合飞行仿真技术、分布计算技术和可视化技术,设计开发了一套通用的、适宜飞行器系统细粒度仿真的分布式软件体系——分布式飞行仿真环境(Distributed Flight Simulation Environment,DFSE),并系统地研究了DFSE系统从应用层子系统设计、分布支撑子系统设计、到交互接口设计的整个过程中所涉及的理论方法和技术原理。 根据飞行器系统细粒度分布仿真的基本要求和特点,DFSE系统采用了当前分布式系统设计中流行的客户/服务器模式、中间件技术和分层设计的思想,并采用面向对象的方法来完成设计与开发。它实现了仿真系统与计算机网络结构的分离、仿真系统内应用子系统和分布式仿真支撑子系统的分离、仿真任务模型与仿真应用平台的分离、以及仿真算法与仿真模型的分离,因此整个仿真系统具有很强的平台独立性、可重用性、可靠性、可移植性以及可扩展性。论文的主要贡献归纳如下: ①对参与设计完成的多个工程应用项目及其研究对象模型的特点进行了深入细致的分析,并在对它们所涉及的分布与飞行仿真技术进行理论深化总结的基础上,阐述了利用共享内存机制来实现仿真节点间数据交互的分布式飞行仿真通用平台的总体解决方案。 ②提出并建立了飞行仿真应用系统的分布式体系结构和软件环境——分布式飞行仿真环境。结合当前仿真领域的先进技术和理论进行了深入系统的研究,通过对飞行仿真的系统需求、任务特点以及技术要求等的仔细分析,考虑系统的通用性和可重用性,详细设计了分布式飞行仿真环境的层次化结构框架体系。 ③进行了DFSE系统分布式支撑核心层的理论方法研究和软件设计开发。通过网络通信中间件的设计,实现了分布式飞行仿真系统跨多种网络平台工作;通过对逻辑共享内存技术的基本思想、构造方法、工作原理以及分类方法等技术理论的深入研究,实现了仿真系统节点间模型数据的透明共享;通过采用事件与时间双重驱动的调度管理机制,实现了对分布式仿真系统运行的有效控制;设计并实现了DFSE系统的多种服务。 ④完成了DFSE系统仿真应用层的设计与开发。系统研究了飞行仿真任务的可分布性、分解原则、任务分配、参数分布以及仿真建模等相关技术理论;设计并实现了DFSE系统应用层的层次化、模块化软件结构体系。 ⑤详细分析了影响分布式飞行仿真系统性能的各种因素,提出了相应的性能改进方法和具体措施,并给出了综合评价系统性能的具体方法和多种性能指标。 ⑥通过对一个典型的工程仿真任务进行分布仿真实验,检验并验证了本文所研制开发的DFSE系统及其技术方法的正确性,实验表明DFSE系统软件操作快捷方便、性能稳定高效、功能强大实用。西北工业大学博士学位论文 作为仿真技术与网络技术相结合的产物,分布式仿真技术己经成为目前实现大型复杂系统仿真的主要技术途径之一。本文研制的DFSE系统是根据飞行器系统细粒度仿真的具体需要来设计完成的一套比较完整的分布式飞行仿真通用平台,它在飞行器系统论证、设计与仿真实验等方面以及相关领域中都有着广阔的应用前景。

景维鹏[7]2016年在《分布式环境下主副版本任务可靠调度方法研究》文中指出随着计算技术和网络技术的发展,以分布式计算、并行计算为基础的分布式计算系统所构建的数据中心和计算中心在工业、商业、科技和军事等领域有着非常广泛的应用。在这些应用中将大量的复杂计算任务分解成为若干个子任务并行处理,最后将计算结果进行有效合并得到最终结果。可以看到在任务的分解和计算过程中,有效的任务调度机制是影响分布式计算系统性能和效率的关键因素,而不合理的任务调度方法会严重影响系统的计算能力,降低并行效率,甚至达不到并行计算应具有的效果。因此任务的调度问题一直是分布式系统、网格系统、云计算系统的核心内容,也是人们一直研究的热点。但是,随着分布式系统规模的不断增加、计算能力不断提高的同时,系统的稳定性和可靠性已成为影响并行应用能否顺利执行的关键。例如在天河二号、Google数据中心等超级计算机或是大规模集群中,由于复杂的上层应用以及系统超高的功耗导致了系统极容易出现故障,因此设计一套完整的可靠性保障机制显得尤为重要,而在系统的调度阶段设计高可靠的调度算法是其中重要的手段之一。本文从“保障性能,提高可靠性”这一目标出发,深入研究如何保障分布式计算系统可靠性与计算资源高效利用问题。论文将任务的类型分为实时周期任务和非实时任务两种任务类型,通过主副版本调度技术,实现了高可靠、高性能的调度策略。具体工作为:(1)针对分布式计算系统的实时任务的可靠调度问题,提出了一种依据计算节点和通信链路可靠性代价的调度算法(DRCAMD)。该方法能通过设置权值的方法来调整系统的目标权重函数,平衡用户在系统的调度性能和可靠性的不同需求,另外,针对具有依赖关系的实时任务的调度问题,本文提出了一种不考虑主版本任务与副版本任务各种重迭状态的可调度分析方法,实验结果表明了在一定的计算节点和通信链路的故障概率条件下,算法的可靠性和性能方面具有一定的优势。(2)针对混合关键任务可靠性调度的问题,基于主副版本调度策略,结合任务关键性等级的处理方法,提出了一种二阶段可靠调度算法(MCRSS)及可调度分析方法。该算法的第一阶段主要是对需要调度的混合关键性任务按照优先级高低进行调度,调度过程中,使用副本重迭的方法减少由于副版本任务的复制所带来的系统开销,第二个阶段是对调度到目标处理机上的任务进行可调度分析,对于不能满足可调度需求的任务进行升级处理,直到能满足任务对截止期的要求。仿真实验表明了MCRSS算法能有效的处理混合关键任务中不同关键等级任务的可靠调度问题,同时保证了分布式计算系统具有良好的灵活性和性能。(3)针对具有优先级依赖关系的DAG任务的调度问题,本文提出了一种基于副版本任务最早完成时间的调度算法(EFTBT),该方法通过分析主版本任务调度的状态以此得到不同情况下副版本任务调度的最早为完成时间以及调度的目标处理机的约束,并证明了该约束的合理性,该方法能够在保障可靠调度前提下获得较好的调度性能,另外,针对科学工作流应用中存在的多个DAG任务同时调度的问题,为了解决不公平导致的多个后续DAG任务无法调度问题,提出了基于分层思想的多DAG调度策略(MDDL),实验结果表明上述两种算法与经典算法相比能有效提高调度的性能。(4)针对大规模分布式计算系统的异构性、动态性的特点,提出基于节点和链路故障特征分析的具有依赖关系DAG任务可靠调度策略,该策略以副版本任务最早完成时间算法EFTBT为基础,给出了更符合实际应用需求的通信模型以及副版本执行策略,建立了分布式计算系统的故障特点分析方法,在此基础上提出了基于通信竞争模型的容错调度算法(RAPA),实验结果表明与HEFT和EFTBT相比,RAPA算法具有较好的性能和可靠性。

王辉[8]2016年在《异构分布计算系统可靠性分析及优化方法研究》文中认为随着大规模科学计算应用的普及以及并行数据处理规模的不断增大,以网格和并行计算为基础的分布计算系统已成为信息技术和通信技术的重要发展方向,尤其是通过互联网络将大量廉价、处理能力和可靠性等都相互异构的计算单元进行连接所构成的数据存储和计算平台受到学术界和工业界的广泛关注。异构分布计算平台也成为中国战略性新兴产业的重要组成部分,其中系统性能和可靠性优化问题已成为国内外研究的热点。但是系统和应用规模逐渐增大的同时,并行应用对系统长期可靠运行的时间需求也越来越高。此外,由于异构系统下计算资源的动态加入和退出,并行应用程序输入参数的变化以及异构系统环境等因素将引起并行应用程序的执行出现不确定性和不可控性等安全威胁。因此,各并行任务能否可靠地运行是评价分布计算系统优劣的关键指标之一。尤其当异构分布计算系统在时间和空间维度存在关联失效背景下,如何分析系统可靠性以及通过任务调度对并行应用程序执行过程的可靠性进行优化等问题。本文首先从系统可靠性分析理论入手,重点解决关联失效模式下异构分布计算系统可靠性度量和优化方法,并在分布计算系统资源管理和任务分配等方面展开深入研究和探索,提出考虑性能和可靠性开销、具有截止时间约束以及计算资源存在关联失效等条件下的任务调度理论和可靠性优化方法,旨在解决异构分布计算系统可靠性领域的部分关键技术问题。本文的主要研究工作和贡献包括:(1)扩展现有分布计算系统可靠性分析方法,提出关联失效模式下异构分布计算系统可靠性评估方法。目前的异构分布计算系统存在大规模资源共享、广域通信以及多资源合作,而很多传统可靠性分析方法都建立在计算资源间的失效是相互独立的假设基础之上,没有考虑计算资源在时间和空间维度上可能存在的关联失效,尤其随着纳米级大规模集成电路的快速发展,高能电磁辐射引起计算节点关联失效的概率越来越大。根据分布计算系统资源的失效特征建立系统失效模型,提出关联失效模式下基于泰勒展开式的计算系统可靠性度量方法,并从系统结构角度分析共因失效对系统可靠性的影响程度,通过仿真实验验证影响系统可靠度和平均无故障时间的主要因素。在此基础上,进一步提出冗余系统和静态失效系统可靠性分析方法,并通过仿真实验验证算法的性能和有效性。(2)针对资源存在异构性、动态性和广域分布性等特点的大规模分布计算系统,提出基于任务期望执行时间和可靠性开销的表调度算法。分析任意架构网络模型(APN)下关联任务之间最可靠通信链路的选择问题,并提出考虑可靠性开销的最优路径选择算法(OCPR)。在此基础上通过添加具有预测功能的分布计算节点选择策略,以及考虑系统异构性和可靠性开销的任务优先级计算方法,设计分布计算系统环境下可靠性驱动的任务调度算法(RDLS)。仿真实验结果表明所提算法在相同时间复杂度条件下,相对于经典的HEFT和RASD算法具有更优的调度性能和可靠性指标。(3)针对实际分布计算系统运行过程中所收集的开源失效数据集FTA,从时间和空间角度对计算资源的关联失效进行建模,其中空间角度又分为物理空间关联失效和逻辑空间关联失效两种失效模型,并利用马尔科夫随机场和Gibbs分布之间存在的等价理论对所提出的关联失效模型进行理论分析和形式化建模。对关联失效进行建模的目的是将分布计算系统内的节点进行关联组划分,每个组内的计算节点具有强关联性,从而为选择冗余节点来提高任务执行可靠性提供依据,避免选择同-关联失效组内的多个计算节点作为同一任务的副本计算节点。通过理论分析和实验验证了所提关联失效模型的有效性和可行性。(4)针对计算资源存在关联失效的分布计算系统和具有截止时间约束的并行DAG应用程序,提出基于任务截止时间划分的关键路径模型和子任务截止时间分配算法(SDA)。在此基础上,进一步提出基于可靠性驱动的贪心任务复制算法(RDGD)和基于费用驱动的任务复制算法(CDD),在选择复本资源进行任务分配以提高应用程序执行可靠性时,避免同一个子任务分配给具有关联失效特性的计算节点集合内的多个节点,以最大化子任务执行结果的可靠性。实验结果显示基于截止时间划分的关键路径和基于不同目标的可靠性优化调度算法不仅能够提高并行应用程序执行的可靠性,同时又能满足并行应用程序调度性能的需求。

毛佳[9]2004年在《嵌入式实时系统中关键技术的研究》文中研究说明近年来,嵌入式实时系统在航空航天、军事、工业控制、仪器仪表、信息家电等行业得到广泛应用。实时系统与非实时系统之间的最大区别就是要满足处理与时间的关系。在实时系统中,系统输出的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间。实时系统最重要的要求就是系统必须在一个事先定义好的时间限制中对外部或内部的事件进行响应和处理,我们称这个事先定义好的时间限制为截止期(Deadline)。实时操作系统在多媒体通信、在线事务处理、生产过程控制、交通控制等各个领域得到广泛的应用,因而越来越引起人们的重视。而进程调度策略是影响系统实时性能的重要因素。因此我在此对实时进程调度进行研究。目前实时系统的进程调度算法主要有先进先出算法(First In and First Out,FIFO)、单调速率算法(Rate Monotonic,RM)、最早截止期优先算法(Earliest Deadline First,EDF)、价值最高优先算法(Highest Value First,HVF)等。本文是在研读Linux源代码,引入其它相关学科的理论和方法,并且参考了大量参考文献的基础上,进行深入研究的。当然本文提出的思想对其他操作系统的实时进程调度算法上有一定的使用价值及参考价值。进程管理是操作系统最关键的部分之一,它的设计和实现直接影响到整个系统的性能。虽然目前对实时进程的调度算法已经有很多,但是大多都存在一定的缺点。本文通过对Linux的进程调度进行分析,发现Linux关于实时进程的优先级没有涉及到实时进程的截止期和进程的紧迫性,为了增强Linux的关于实时进程的处理,本文并提出了一种优化改进调度算法。该算法以进程的重要性为<WP=116>基础,兼顾截止期内实时进程的紧迫性,建立了基于优先级数的可执行进程队列。Linux原有的调度算法(以下称为优化前调度算法)中建立进程优先级的主要依据是进程所拥有的价值(即进程的重要性),然后系统选择优先级最高的进程进入CPU运行。Linux调度算法的实现受到CPU运行速度和负载状况的影响。作为实时系统调度算法应综合考虑进程的权值和截止期两个概念,以防止对CPU能力的不合理使用。因此本文提出新的调度算法,算法中进程的优先级数计算公式为:(1)公式中各参数定义:vi表示进程的优先级数;wi表示该进程的价值(代表进程的重要程度);Pi表示进程的估计执行时间;di表示绝对截止期;Ti表示该进程提交时间;(d-Ti)是相对截止期,即该进程最大容忍的等待时间,在相对截止期内,这个进程就应该被执行,否则这个进程夭折;Pi/(d-Ti)我们称之为紧迫度,即这个值越大,说明从时间上看这个任务越紧迫;k是系数因子。论文的创新主要有以下几个方面:(1)本文在对实时系统的进程调度算法进行研究的基础上,还对优先级逆转问题进行了思考,并且分析了已有的解决方案的弊端,进而提出了自己的解决方案。提出的优先级倒转的解决策略,因为其简单易于实现,而且在考虑临界区中进程优先级的前提下,能解决优先级逆转问题,因此有很高的实用价值。(2)本文所讨论的多处理器实时系统的研究,为在一个系统中同时支持多种实时调度方法提供了可能性。首先阐述了排队论的相关概念、基本理论和研究现状,其次根据其中的调度对象的特征,提出了一种层次性调度对象模型,然后详细分析了几种有代表性的主要调度方法,重点对它们各自的随机特性和适用范围作了评价和比较,在此基础上。找出它们的若干共同之处,,阐述了这些共同点带来的启发:可以通过对随机进程和服务器性能的综合分析,在保<WP=117>证完成进程吞吐率的前提下,减少系统的总开销,从而提高系统的效率,同时明确给出了该方法的数学证明。(3)在许多实际工程问题的计算中,经常遇到一些大型的高阶矩阵的有关计算,尤其是两矩阵相乘和方阵求逆最为常见。当矩阵阶数较高时,通常的计算过程需要占用较多的工作单元和较大的计算机内存,计算效率受到影响.随着大型的具有多处理机的并行计算机系统的发展,一些大型计算可以构造相应的并行计算方法进行并行处理,从而减少机器的工作单元,提高计算效率,节约资源。为此,对于矩阵的乘积和方阵求逆运算本文构造了一种并行算法,并给出了相应的实现步骤。(4)研究了资源共享可能引起的死锁问题,提出了并行资源死锁结构的概念。探讨了信息资源共享时出现处理死锁问题的几种办法,提出了一种按顺序分配信息资源的简单的无死锁方法,给出了对应的任务调度管理算法,并且通过仿真实验验证了算法的有效性。(5)研制了嵌入式超声探伤仪有小型、节能、操作方便、精度高及测量速度快等一系列优点,对嵌入式技术在缺陷检测设备中的应用研究有一定的参考价值。而且,采用状态空间平均法建立了电动机的输出角速度和PWM占空比以及电压等之间的等效模型,并基于DSP设计了嵌入式伺服控制系统,实现实时处理数据优化算法,验证了算法的有效性和可靠性,提高了系统的响应能力,硬件电路设计简单实用。文章中的模型系统具有稳定性好、响应速度快、精度较高等特点,对嵌入式伺服控制系统的研究具有一定的参考价值。嵌入式实时系统是计算机界比较关注的问题,实时

张滨[10]2017年在《基于MapReduce大数据并行处理的若干关键技术研究》文中研究指明关系数据库技术在传统数据科学领域的研究已经比较完善,但是由于当前CPU计算能力与磁盘读写技术发展的不平衡,使I/O成为了传统数据库性能提升的瓶颈。此外,传统数据库也无法胜任非结构化数据类型的数据分析处理任务。随着大数据研究的日益深入,出现了各种新的数据查询处理方法。关系数据库和非关系型数据库技术相融合研究是数据科学、数据工程领域的研究热点,国内外研究学者进行了一些探索,仍然有很多关键问题有待解决。如何实现利用MapReduce分布式并行计算方法解决大数据查询处理,以及针对查询处理系统提出有效的查询优化策略是目前学术界普遍关注的问题。本文正是从利用MapReduce分布式并行计算的思想和方法入手,设计了新的面向大数据的查询分析处理方法,本文的研究工作概括为以下几个方面:一、在传统关系数据库查询代价估计模型基础上,设计了基于MapReduce的大数据并行处理的代价估计模型,并且针对不同的优化策略,分别设计了Hash连接环境,查询物化策略环境以及频繁查询环境下的代价估计优化模型。二、讨论了并行处理系统的查询优化控制问题。提出基于列存储的大数据分析系统物化策略。首先,通过引入MapReduce物化代价估计模型,深入分析影响物化效率的各个因素。在此基础上设计了MapReduce分布式环境下的面向物化策略的存储系统文件格式:MMF,在数据加载过程中采用协同定位策略实现对物化数据的存储优化;其次,分别针对不同的物化时机,构建了mapreduce早期物化策略,mapreduce延迟物化策略和mapreduce混合物化策略;然后,利用自适应物化调整策略对其做了进一步优化。叁、针对传统关系型数据库在对大数据访问操作时,系统性能严重下降,计算效率提升有限以及可扩展性差等问题,引入mapreduce并行计算模型,设计了大数据上基于列存储的mapreduce并行连接算法。首先,设计了面向大数据的分布式计算模型,其次,使用了分片聚集和子连接启发式优化方法实现大数据在mapreduce分布式环境下并行连接算法。四、设计了大数据上基于列存储的支持负载数据偏斜动态探测的mapreduce分布式hash连接算法。首先,建立了面向大数据的分布式计算模型,在此基础上设计了mapreduce环境下的哈希分布式存储系统;其次,在数据加载过程中采用协同定位策略实现对数据分布的优化,减少数据偏斜的出现;然后,在设计的分片聚集并行连接基础上,利用hash连接以及动态探测方法优化了数据连接处理效率。五、通过讨论并行处理系统的调度优化控制问题,设计了面向大数据频繁查询工作负载的优化方法。首先,建立频繁查询模型,分析了mapreduce环境下影响频繁查询效率各种因素。其次,设计了基于mapreduce一致性窗口分片算法,不仅为频繁查询集合创建更多的重用机会,而且通过对输入数据这样的精细粒度调度,可以大大减少冗余数据加载。然后,在数据调度方面,利用mapreduce延迟调度策略,提高数据处理吞吐量,优化mapreduce集群计算资源分配,通过mapreduce频繁查询数据重用策略,构造最佳的数据重用调度执行计划。最后,开发了基于hadoop的算法测试原型系统hcms对所提方法进行逐一验证。实验结果在证明算法有效的同时,也能提供良好的可扩展性。通过分析证明算法在执行时间、在存储空间和负载能力上,都有很好的表现。

参考文献:

[1]. 分布式并行操作系统中调度的研究和实现[D]. 刘流. 电子科技大学. 2002

[2]. 基于云计算的逆时偏移数据处理方法研究[D]. 高新成. 东北石油大学. 2016

[3]. 电网自动化分布并行操作系统中智能化任务调度的设计与实现[D]. 邱元杰. 电子科技大学. 2001

[4]. 教育部数据中心数据管理优化策略研究[D]. 吴齐跃. 北京科技大学. 2016

[5]. 异构多核嵌入式软件关键问题研究[D]. 蒋建春. 重庆大学. 2011

[6]. 分布式飞行仿真技术研究[D]. 伍智锋. 西北工业大学. 2003

[7]. 分布式环境下主副版本任务可靠调度方法研究[D]. 景维鹏. 哈尔滨工业大学. 2016

[8]. 异构分布计算系统可靠性分析及优化方法研究[D]. 王辉. 东南大学. 2016

[9]. 嵌入式实时系统中关键技术的研究[D]. 毛佳. 吉林大学. 2004

[10]. 基于MapReduce大数据并行处理的若干关键技术研究[D]. 张滨. 东华大学. 2017

标签:;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  

分布式并行操作系统中调度的研究和实现
下载Doc文档

猜你喜欢