Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (3): 372-380.doi: 10.1007/s12204-019-2073-7

• • 上一篇    下一篇

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

XIE Ying *(谢盈), WU Jinzhao (吴尽昭), CHEN Jianying (陈建英), CUI Mengtian (崔梦天)   

  1. (1. School of Computer Science and Technology, Southwest Minzu University, Chengdu 610041, China; 2. Guangxi Key Laboratory of Hybrid Computational and IC Design Analysis, Guangxi University for Nationalities, Nanning 530006, China; 3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China; 4. University of Chinese Academy of Sciences, Beijing 100049, China)
  • 出版日期:2019-06-01 发布日期:2019-05-29
  • 通讯作者: XIE Ying *(谢盈) E-mail:xieying33@163.com

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

XIE Ying *(谢盈), WU Jinzhao (吴尽昭), CHEN Jianying (陈建英), CUI Mengtian (崔梦天)   

  1. (1. School of Computer Science and Technology, Southwest Minzu University, Chengdu 610041, China; 2. Guangxi Key Laboratory of Hybrid Computational and IC Design Analysis, Guangxi University for Nationalities, Nanning 530006, China; 3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China; 4. University of Chinese Academy of Sciences, Beijing 100049, China)
  • Online:2019-06-01 Published:2019-05-29
  • Contact: XIE Ying *(谢盈) E-mail:xieying33@163.com

摘要: It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system. A novel dynamic measurement method (DMM) was proposed to measure the task scheduling algorithm’s correctness and dependability. In a multi-processor system, task scheduling problem is represented by a combinatorial evaluation model, interactive Markov chain (IMC), and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic (aCSL). DMM derives a path by logging runtime scheduling actions and corresponding times. Through judging whether the derived path can be received by task scheduling IMC model, DMM analyses the correctness of algorithm. Through judging whether the actual values satisfy label function of the initial state, DMM analyses the dependability of algorithm. The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.

关键词: multi-processor, task scheduling algorithm, IMC, aCSL, dynamic measurement

Abstract: It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system. A novel dynamic measurement method (DMM) was proposed to measure the task scheduling algorithm’s correctness and dependability. In a multi-processor system, task scheduling problem is represented by a combinatorial evaluation model, interactive Markov chain (IMC), and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic (aCSL). DMM derives a path by logging runtime scheduling actions and corresponding times. Through judging whether the derived path can be received by task scheduling IMC model, DMM analyses the correctness of algorithm. Through judging whether the actual values satisfy label function of the initial state, DMM analyses the dependability of algorithm. The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.

Key words: multi-processor, task scheduling algorithm, IMC, aCSL, dynamic measurement

中图分类号: