Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Probabilistic real-time task scheduling method based on pWCET shaping

A technology of real-time tasks and scheduling methods, applied in the direction of program startup/switching, resource allocation, program control design, etc., can solve the problem of high computational complexity of schedulability analysis

Active Publication Date: 2018-11-20
DALIAN UNIV OF TECH
View PDF6 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the complexity of response time analysis of probabilistic real-time systems is exponential with respect to the number of tasks and the number of values ​​estimated by pWCET, while pWCET estimation in practical applications may involve thousands of values, which makes the computational complexity of schedulability analysis very high

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Probabilistic real-time task scheduling method based on pWCET shaping
  • Probabilistic real-time task scheduling method based on pWCET shaping
  • Probabilistic real-time task scheduling method based on pWCET shaping

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0044] An embodiment of the present invention will be further described below in conjunction with the accompanying drawings.

[0045] For example, there is a task set that contains two tasks: task τ 1 The period is T 1 = 5, the deadline is D 1 = 5, the probabilistic requirement of the task missing the deadline is pWCET is Task τ 2 The period is T 2 = 10, the deadline is D 2 = 10, the probability that the task misses the deadline is required to be pWCET is

[0046] Before introducing the embodiment of the present invention, we first use the Audsley algorithm for scheduling analysis to analyze whether the task set is schedulable.

[0047] First, because the task τ 2 The minimum WCET of 7 is greater than the task τ 1 deadline 5, and the task τ 1 The probabilistic demand for missing the deadline for is Known task τ 1 Priority is higher than τ 2 , and the task τ 1 The probabilistic response time of Such as figure 1 As shown, the task τ 1 Worst case executio...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a probabilistic real-time task scheduling method based on pWCET (probabilistic worst case execution time) shaping, and belongs to the technical field of real-time systems. A probabilistic real-time task scheduling scheme based on the pWCET shaping is proposed, so that the goals of properly isolating the influence between probabilistic real-time tasks and lowering the calculation complexity of system schedulability analysis are achieved. According to the method, the pWCET of the probabilistic real-time tasks is shaped, and budget allocation is performed on the basis of the shaped pWCET, so that while the probabilistic real-time requirements of the tasks are met, the influence between the probabilistic real-time tasks can be properly isolated, and the schedulability ofthe whole task set is remarkably improved. In addition, the value of the shaped pWCET is obviously reduced compared with that of original pWCET; the calculation complexity of the schedulability analysis can be lowered; and the efficiency is remarkably improved.

Description

technical field [0001] The invention belongs to the technical field of real-time systems, and in particular relates to a probabilistic real-time task scheduling method based on probabilistic Worst Case Execution Time (pWCET) shaping. Background technique [0002] With the rapid development of chip technology, high-performance microprocessors are more and more widely used in safety-critical fields (such as avionics, automobiles, industrial control, etc.) . Although high-performance microprocessors can reduce the average execution time of tasks, due to the complexity of the processor architecture, the worst-case execution time (Worst Case Execution Time, WCET) of some tasks is relatively large, so a higher Over-provisioning to meet the real-time requirements of the system. In order to alleviate the problem of over-allocation, improve the utilization rate of resources, and meet the real-time requirements, a probabilistic method can be used to solve the uncertainty problem of ...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06F9/48G06F9/50
CPCG06F9/4881G06F9/5038G06F2209/484G06F2209/5021
Inventor 任健康宿晓燕
Owner DALIAN UNIV OF TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com