[go: up one dir, main page]

CN110879746B - 基于核间迁移的高安全关键任务调度方法 - Google Patents

基于核间迁移的高安全关键任务调度方法 Download PDF

Info

Publication number
CN110879746B
CN110879746B CN201911092362.7A CN201911092362A CN110879746B CN 110879746 B CN110879746 B CN 110879746B CN 201911092362 A CN201911092362 A CN 201911092362A CN 110879746 B CN110879746 B CN 110879746B
Authority
CN
China
Prior art keywords
task
processor
inter
safety
migration
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201911092362.7A
Other languages
English (en)
Other versions
CN110879746A (zh
Inventor
朱怡安
李孟豪
李联
史先琛
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Northwestern Polytechnical University
Original Assignee
Northwestern Polytechnical University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Northwestern Polytechnical University filed Critical Northwestern Polytechnical University
Priority to CN201911092362.7A priority Critical patent/CN110879746B/zh
Publication of CN110879746A publication Critical patent/CN110879746A/zh
Application granted granted Critical
Publication of CN110879746B publication Critical patent/CN110879746B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/485—Task life-cycle, e.g. stopping, restarting, resuming execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/5038—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Debugging And Monitoring (AREA)

Abstract

本发明公开了一种基于核间迁移的高安全关键任务调度方法，用于解决现有高安全关键任务调度方法安全性差的技术问题。技术方案是将任务在高安全关键模式下的处理器映射记为πHI，将任务在低安全关键模式下的处理器映射记为πLO；当系统由低安全关键模式提升为高安全关键模式时，判断在πLO上不可调度的任务w迁移到πHI上后是否可以进行调度，如果满足可调度性，就将其迁移到πHI上进行调度，核间迁移工作完成；如果不存在满足条件的任务ws，则任务w无法进行核间迁移，核间迁移失败。本发明在当前处理器上不可调度的高安全关键任务，充分发挥多核处理器的优势，通过核间迁移来使得不可调度的任务在新的处理器上可调度，增加高安全关键任务的调度成功率，提高了系统的安全性。

Description

基于核间迁移的高安全关键任务调度方法
技术领域
本发明涉及一种高安全关键任务调度方法，特别涉及一种基于核间迁移的高安全关键任务调度方法。
背景技术
发表于IEEE International Symposium on Realtime DistributedComputing2015年版198-207的文章“Multiprocessor Scheduling of Precedenceconstrained Mixed-critical Jobs”提出了一种混合关键任务优先级提升(Mixed-Criticality Priority Improvement，MCPI)的调度方法。该方法利用一个表来存储任务的优先级，每次发生任务调度时，需要先查询优先级表，对优先级最高的任务进行调度。当系统的安全关键等级转换时，会对任务的优先级进行重新分配，提升高安全关键任务的优先级以使其优先得到调度。
该方法虽然能够保证高安全关键任务的调度成功率，但是其在系统安全关键等级每次发生改变时，都要对任务的优先级进行重新划分，严重浪费了系统的资源；也没有充分发挥处理器多核的优势。
发明内容
为了克服现有高安全关键任务调度方法安全性差的不足，本发明提供一种基于核间迁移的高安全关键任务调度方法。该方法在任务的分配阶段即对任务在高安全关键模式和低安全关键模式下的处理器映射进行记录，将任务在高安全关键模式下的处理器映射记为πHI，将任务在低安全关键模式下的处理器映射记为πLO；当系统由低安全关键模式提升为高安全关键模式时，判断在πLO上不可调度的任务w迁移到πHI上后是否可以进行调度，如果满足可调度性，就将其迁移到πHI上进行调度，核间迁移工作完成；如果任务w在迁移到πHI上无法满足可调度性，再查看处理器πHI中是否存在任务ws，满足任务ws在高安全关键模式下的处理器映射
Figure BDA0002267226170000011
与任务w在低安全关键模式下的处理器映射wLO相同，同时满足交换两个任务之后，在新的处理器上任务w与任务ws均可调度，如果存在满足条件的任务ws，那么就将两个任务进行交换，核间迁移工作完成；如果不存在满足条件的任务ws，则任务w无法进行核间迁移，核间迁移失败。
本发明当系统的安全关键等级提升时，对于在当前处理器上不可调度的高安全关键任务，充分发挥多核处理器的优势，通过核间迁移来使得原本不可调度的任务在新的处理器上可调度，增加高安全关键任务的调度成功率，提高了系统的安全性。
本发明解决其技术问题所采用的技术方案：一种基于核间迁移的高安全关键任务调度方法，其特点是包括以下步骤：
步骤一、得到不可调度任务wh当前所在处理器πh(LO)以及其在高安全关键模式HI-cri下的处理器映射πh(HI)。
步骤二、判断任务wh在低安全关键模式LO-cri下的处理器映射πh(LO)和高安全关键模式下的处理器映射πh(HI)是否相同，如果相同，表示该任务无法进行核间迁移，跳转步骤五；如果不相同，表示该任务能够进行核间迁移，跳转步骤三。
步骤三、将任务wh加入处理器πh(HI)的任务队列，通过公式(1)和公式(2)计算πh(HI)的任务集利用率Uh，判断处理器πh(HI)的任务集利用率Uh是否大于1，如果大于1，则表示将任务wh迁移到处理器πh(HI)上不可调度，跳转步骤四；如果不大于1，则表示将任务wh迁移到处理器πh(HI)上可调度，那么就将任务wh迁移到πh(HI)上，跳转步骤六。
Figure BDA0002267226170000021
式中，ui表示任务的利用率因子，ci表示任务的最坏执行时间，pi表示任务周期。
Figure BDA0002267226170000022
式中，U表示处理器πh(HI)的任务集总利用率因子，ui表示任务的利用率因子，n表示处理器πh(HI)上的任务个数。
步骤四、判断任务wh在HI-cri下的处理器映射πh(HI)的任务队列中是否存在任务wj，任务wj在HI-cri下的处理器映射πj(HI)和LO-cri下的处理器映射πj(LO)满足πj(LO)＝πh(HI)且πj(HI)＝πh(LO)，同时在交换任务wh和wj后，处理器πh(HI)和处理器πh(LO)均可调度。如果存在满足上述条件的任务wj，则交换任务wh与wj，跳转步骤六；如果不存在，跳转步骤五。
步骤五、任务迁移失败。
步骤六、任务迁移成功。
本发明的有益效果是：该方法在任务的分配阶段即对任务在高安全关键模式和低安全关键模式下的处理器映射进行记录，将任务在高安全关键模式下的处理器映射记为πHI，将任务在低安全关键模式下的处理器映射记为πLO；当系统由低安全关键模式提升为高安全关键模式时，判断在πLO上不可调度的任务w迁移到πHI上后是否可以进行调度，如果满足可调度性，就将其迁移到πHI上进行调度，核间迁移工作完成；如果任务w在迁移到πHI上无法满足可调度性，再查看处理器πHI中是否存在任务ws，满足任务ws在高安全关键模式下的处理器映射
Figure BDA0002267226170000031
与任务w在低安全关键模式下的处理器映射wLO相同，同时满足交换两个任务之后，在新的处理器上任务w与任务ws均可调度，如果存在满足条件的任务ws，那么就将两个任务进行交换，核间迁移工作完成；如果不存在满足条件的任务ws，则任务w无法进行核间迁移，核间迁移失败。
本发明当系统的安全关键等级提升时，对于在当前处理器上不可调度的高安全关键任务，充分发挥多核处理器的优势，通过核间迁移来使得原本不可调度的任务在新的处理器上可调度，增加高安全关键任务的调度成功率，提高了系统的安全性。
下面结合附图和具体实施方式对本发明作详细说明。
附图说明
图1是本发明基于核间迁移的高安全关键任务调度方法的流程图。
具体实施方式
参照图1。本发明基于核间迁移的高安全关键任务调度方法具体步骤如下：
步骤一、得到不可调度任务wh当前所在处理器πh(LO)以及其在高安全关键模式HI-cri下的处理器映射πh(HI)。
步骤二、判断任务wh在低安全关键模式LO-cri下的处理器映射πh(LO)和高安全关键模式下的处理器映射πh(HI)是否相同，如果相同，表示该任务无法进行核间迁移，跳转步骤五；如果不相同，表示该任务可以迁移，跳转步骤三。
步骤三、将任务wh加入处理器πh(HI)的任务队列，通过公式(1)和(2)计算πh(HI)的任务集利用率Uh，判断处理器πh(HI)的任务集利用率Uh是否大于1，如果大于1则表示将任务wh迁移到处理器πh(HI)上不可调度，跳转步骤四；如果不大于1，则表示将任务wh迁移到处理器πh(HI)上可调度，那么就将任务wh迁移到πh(HI)上，跳转步骤六。
Figure BDA0002267226170000041
式中，ui表示任务的利用率因子，ci表示任务的最坏执行时间，pi表示任务周期。
Figure BDA0002267226170000042
式中，U表示处理器πh(HI)的任务集总利用率因子，ui表示任务的利用率因子，n表示处理器πh(HI)上的任务个数。
步骤四、判断任务wh在HI-cri下的处理器映射πh(HI)的任务队列中是否存在任务wj，任务wj在HI-cri下的处理器映射πj(HI)和LO-cri下的处理器映射πj(LO)满足πj(LO)＝πh(HI)且πj(HI)＝πh(LO)，同时在交换任务wh和wj后，处理器πh(HI)和处理器πh(LO)均可调度。如果存在满足上述条件的任务wj，则交换任务wh与wj，跳转步骤六；如果不存在，跳转步骤五。
步骤五、任务迁移失败。
步骤六、任务迁移成功。

Claims (1)

1.一种基于核间迁移的高安全关键任务调度方法，其特征在于包括以下步骤：
步骤一、得到不可调度任务wh当前所在处理器πh(LO)以及其在高安全关键模式HI-cri下的处理器映射πh(HI)；
步骤二、判断任务wh在低安全关键模式LO-cri下的处理器映射πh(LO)和高安全关键模式下的处理器映射πh(HI)是否相同，如果相同，表示该任务无法进行核间迁移，跳转步骤五；如果不相同，表示该任务能够进行核间迁移，跳转步骤三；
步骤三、将任务wh加入处理器πh(HI)的任务队列，通过公式(1)和公式(2)计算πh(HI)的任务集利用率Uh，判断处理器πh(HI)的任务集利用率Uh是否大于1，如果大于1，则表示将任务wh迁移到处理器πh(HI)上不可调度，跳转步骤四；如果不大于1，则表示将任务wh迁移到处理器πh(HI)上可调度，那么就将任务wh迁移到πh(HI)上，跳转步骤六；
Figure QLYQS_1
式中，ui表示任务的利用率因子，ci表示任务的最坏执行时间，pi表示任务周期；
Figure QLYQS_2
式中，U表示处理器πh(HI)的任务集总利用率因子，ui表示任务的利用率因子，n表示处理器πh(HI)上的任务个数；
步骤四、判断任务wh在HI-cri下映射处理器πh(HI)的任务队列中是否存在任务wj，满足：(1)πj(LO)＝πh(HI)且πj(HI)＝πh(LO)，其中πj(HI)为任务wj在HI-cri下映射的处理器映射，πj(LO)为LO-cri下映射的处理器；(2)将任务wh、wj分别迁移到πh(HI)、πj(HI)，任务wh和wj均可调度；如果存在任务wj满足条件(1)和(2)，则交换任务wh与wj，跳转步骤六；如果不存在，跳转步骤五；
步骤五、任务迁移失败；
步骤六、任务迁移成功。
CN201911092362.7A 2019-11-11 2019-11-11 基于核间迁移的高安全关键任务调度方法 Active CN110879746B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201911092362.7A CN110879746B (zh) 2019-11-11 2019-11-11 基于核间迁移的高安全关键任务调度方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201911092362.7A CN110879746B (zh) 2019-11-11 2019-11-11 基于核间迁移的高安全关键任务调度方法

Publications (2)

Publication Number Publication Date
CN110879746A CN110879746A (zh) 2020-03-13
CN110879746B true CN110879746B (zh) 2023-03-31

Family

ID=69729373

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911092362.7A Active CN110879746B (zh) 2019-11-11 2019-11-11 基于核间迁移的高安全关键任务调度方法

Country Status (1)

Country Link
CN (1) CN110879746B (zh)

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102193826B (zh) * 2011-05-24 2012-12-19 哈尔滨工程大学 一种异构多核处理器高效任务调度方法
US9766931B2 (en) * 2012-04-30 2017-09-19 Massachusetts Institute Of Technology Uniprocessor schedulability testing for non-preemptive task sets
CN105700941B (zh) * 2015-12-18 2019-04-05 西安工业大学 三维调度器模型的调度方法
CN106293919B (zh) * 2016-08-12 2019-06-11 中国航空工业集团公司西安飞行自动控制研究所 一种时间触发的嵌入式任务调度装置与方法
US10620992B2 (en) * 2016-08-29 2020-04-14 TidalScale, Inc. Resource migration negotiation
CN109144691B (zh) * 2018-07-13 2021-08-20 哈尔滨工程大学 一种面向多核处理器的任务调度分配方法
CN109298919B (zh) * 2018-08-27 2021-09-07 西安工业大学 面向高利用率任务集合的软实时系统的多核调度方法
CN109753348A (zh) * 2018-11-21 2019-05-14 惠州Tcl移动通信有限公司 后台应用程序的管控方法和终端

Also Published As

Publication number Publication date
CN110879746A (zh) 2020-03-13

Similar Documents

Publication Publication Date Title
US9875145B2 (en) Load based dynamic resource sets
CN104915407A (zh) 一种基于Hadoop多作业环境下的资源调度方法
CN102193826A (zh) 一种异构多核处理器高效任务调度方法
CN103500119B (zh) 一种基于预调度的任务分配方法
CN101887383B (zh) 一种进程实时调度方法
CN107291550B (zh) 一种针对迭代应用的Spark平台资源动态分配方法及系统
CN101673223B (zh) 基于片上多处理器的线程调度实现方法
CN102521265B (zh) 一种海量数据管理中动态一致性控制方法
WO2017080276A1 (zh) 资源管理方法和系统、计算机存储介质
CN103984595A (zh) 一种异构cmp的静态任务调度方法
CN107122233A (zh) 一种面向tsn业务的多vcpu自适应实时调度方法
CN109101320B (zh) 异构处理器平台融合管理系统
Guo et al. The concurrent consideration of uncertainty in WCETs and processor speeds in mixed-criticality systems
CN110879746B (zh) 基于核间迁移的高安全关键任务调度方法
CN113535356B (zh) 一种能量感知的分层任务调度方法和装置
CN103677959A (zh) 一种基于组播的虚拟机集群迁移方法及系统
CN112463295B (zh) 一种支持可抢占虚拟机实例的云工作流配置和调度方法
CN106293007B (zh) 一种支持非抢占实时任务集的节能调度方法
CN104182280B (zh) 面向混合主存嵌入式系统的低能耗rm实时任务调度方法
CN104182180B (zh) 面向混合主存嵌入式系统的低能耗edf实时任务调度方法
CN114578943B (zh) 一种固定优先级非精确混合关键任务调度方法
CN111045799B (zh) 基于回收再分配的低安全关键任务调度方法
CN113961323B (zh) 一种面向混合云的安全感知任务调度方法和系统
CN104731900A (zh) 一种Hive调度方法及装置
WO2024164369A1 (zh) 混合关键分区实时操作系统的资源感知型任务分配方法

Legal Events

Date Code Title Description
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant