CN105260497B

CN105260497B - Semi-direct simulation method for real-time task schedulability test based on linear linked list

Info

Publication number: CN105260497B
Application number: CN201510481348.1A
Authority: CN
Inventors: 姜誉
Original assignee: Heilongjiang University
Current assignee: Heilongjiang University
Priority date: 2015-08-07
Filing date: 2015-08-07
Publication date: 2019-04-30
Anticipated expiration: 2035-08-07
Also published as: CN105260497A

Abstract

Real-time task schedulability based on linear linked list tests semi-direct analogy method.The method of the present invention includes: to remember task τ to each i, 1≤i≤n_iRelease time of first task instances for being no earlier than scheduling stable point S release be that new release deviates, also use Φ_iIt indicates；According to given scheduling model, using the simulation of linear linked list recording dispatching and test process, first to task τ₁,τ₂,...,τ_n‑1, in time range Φ_min ^(n‑1)To Φ_min ^(n‑1)+LCM_n‑1Each task τ is inside according to priority simulated in descending order_iScheduling execute, then to task τ on current chained list_nIt is tested.The present invention is used for it needs to be determined that whether one group of given real-time task is in schedulable simulation or real application systems.

Description

Real-time task schedulability based on linear linked list tests semi-direct analogy method

Technical field:

The present invention relates to a kind of, and the real-time task schedulability based on linear linked list tests semi-direct analogy method.

Background technique:

In real-time system design and application process, appoint in real time for what n given periodicity or not timing occurred Business determines whether this group of real-time task schedulable in real scheduling and before executing, i.e., each task be released later whether Can be at it with respect to being finished in the deadline date, this is a particularly significant problem, for guaranteeing real-time system safe operation With particularly important meaning.

Classical preferentially seizes scheduling model, referred to as CP model, wherein CP, that is, classic preemptive, CP model Scheduling mode are as follows: when low priority task has high-priority task arrival in the process of running, low priority task will Right of execution is deprived of and high-priority task starts to execute, when high-priority task is finished and appoints without other high priorities When business etc. is pending, which continues to execute from bereft position；Transactional manner preferentially seizes tune Model, referred to as TP model are spent, wherein TP, that is, transactional preemptive, for example, TP model has based on priority Functional response formula programming model, referred to as P-FRP model, wherein P-FRP bepriority-based functional reactive programming；Or stop and restart model, and referred to as AR model, wherein AR, that is, abort-and- restart；Or software transactional memory model, referred to as STM model, STM, that is, software transactional Memory, STM model include thirsting for collision detection strategy and lazy collision detection strategy, thirst for collision detection strategy and are referred to as ECD strategy, wherein ECD, that is, eager conflict detection, lazy collision detection strategy are referred to as LCD strategy, wherein LCD, that is, lazy conflict detection；The scheduling mode of TP model are as follows: whenever low priority task in the process of running When having high-priority task arrival, low priority task will be deprived of right of execution and high-priority task starts to execute, this is low excellent The result that first grade task has executed all is discarded, when high-priority task is finished and waits without other high-priority tasks When execution, from it, most starting position re-executes the low priority task；Symbol string r ← s indicates the value of variable s being assigned to change Measure r；Min (a, b) takes the minimum value in a and b, and max (a, b) takes the maximum value in a and b；After mod (a, b) i.e. a mould b Remainder；The least common multiple of lcm (a, b) i.e. a and b；Task it is primary release be known as the task a task instances (job) or Person calls (invoke) or task instances (instance)；[and] between, between "and", between "and", [and], between "and" Respectively indicate a statement body；Task instances, which execute, to be stopped to include executing to interrupt and execute completion by high-priority task.

Given scheduling model is CP model or TP model；In the schedulability (or feasibility) of one group of n real-time task The schedulability of section test (or examine or check or detect) this group task.If the group task be it is schedulable, After one time point S, every time span LCM_n, the dispatch situation of this group task occurs as soon as repetition, i.e., subsequent scheduling process Actually one section is LCM in length_nTime interval [S, S+LCM_n) in scheduling repetition.

System Startup time is the time 0, when actual test schedulability, due to this group task section [0, S) in tune Degree includes first arrival situation and does not often have repeatability, therefore, traditionally by [0, S+LCM_n) as actual schedulable Property test section.This section of schedulability test siding-to-siding block length is smaller, and efficiency is higher in actual test.It, can from the point of view of common situation Scheduling property test siding-to-siding block length is typically no less than LCM_n.Before this without using linear linked list recording dispatching process to task-set can The method that scheduling property is tested.

Summary of the invention:

The object of the present invention is to provide a kind of, and the real-time task schedulability based on linear linked list tests semi-direct simulation side Method indicates that the scheduling of task (or event) executes the stage by using chained list node, using the scheduling of linear linked list record test Process simultaneously achievees the purpose that determining real-time task (or event) schedulability is tested using the method for semi-direct simulation；It is suitable for The situation that real-time task or Event Priority are fixed.

Above-mentioned purpose is realized by following technical scheme:

A kind of semi-direct analogy method of real-time task schedulability test based on linear linked list, this method comprises: to every A i, 1iN remembers task τ_iRelease time of first task instances for being no earlier than scheduling stable point S release be new release Offset is put, Φ is also used_iIt indicates, according to given scheduling model, using the simulation of linear linked list recording dispatching and test process, first To task τ₁,τ₂,...,τ_n-1, in time range Φ_min ^(n-1)To Φ_min ^(n-1)+ LCM_n-1Inside according to priority mould in descending order Intend each task τ_iScheduling execute, then to task τ on current chained list_nIt is tested.

The real-time task schedulability based on linear linked list tests semi-direct analogy method, and the use is linear The simulation of chained list recording dispatching and test process, first to task τ₁,τ₂,...,τ_n-1, in time range Φ_min ^(n-1)To Φ_min ^(n-1) + LCM_n-1Each task τ is inside according to priority simulated in descending order_iScheduling execute, then to task τ on current chained list_n It carries out test to refer to, is executed using the dispatching simulation of a linear linked list logger task and test process, task instances start to hold The start field of chained list node is recorded in row time point, and task instances execute the end word that chained list node is recorded in intermission point Section, each chained list node indicate the time provided from the time point that node start field value provides to node end field value The continuous scheduling of one or more task instances executes between point；Φ_min ⁽¹⁾←Φ₁, LRT₁← C₁；To each i, 2iN, Φ_min ⁽ⁱ⁾←min(Φ_min ^(i-1), Φ_i), LRT_i←C_i；MAX_inter←Φ_min ^(n-1)+ LCM_n-1；One is assigned to indexed variable flag Initial value；[first in time range Φ_min ^(n-1)To Φ_min ^(n-1)+ LCM_n-1Interior simulation task τ₁From the 1st to LCM_n-1/T₁ The execution of a task instances, that is, establish LCM_n-1/T₁A chained list node, from small to large to each j, 1jLCM_n-1/T₁, " jth The start field of a chained list node is assigned a value of task instances τ_1,jRelease time r_1,j, the end field tax of j-th of chained list node Value is r_1,j+C₁；〗；Then to task τ₂,τ₃,...,τ_n-1, in time range Φ_min ^(n-1)To Φ_min ^(n-1)+LCM_n-1It is interior to press preferentially Grade simulates each task τ in descending order_iFrom the 1st to LCM_n-1/T_iThe scheduling of a task instances executes, that is, " to every A i, 2iN -1, each j, 1jLCM_n-1/T_i, j successively calls to execute from small to large simulates individual task example function F1 To task τ_iJ-th of task instances τ_i,jIt is simulated；〗；]；I ← n calls test simulation individual task function F2 to task τ_i It is tested；Providing task-set is schedulable information.

The real-time task schedulability based on linear linked list tests semi-direct analogy method, and described executes simulation Individual task example function F1 is to task τ_iJ-th of task instances τ_i,jIt carries out simulation to refer to, [according to r_i,jPass through in chained list Compared with start field value and end field value in node search and since relative position of the current work j in chained list, By when CP module scheduling by runing time C_iCorrespond to 1 or continuous multiple tasks τ_iIdle section chained list node, these nodes The sum of siding-to-siding block length of expression is equal to C_i；By when TP module scheduling by runing time C_iCorrespond to task τ_iA permission section The siding-to-siding block length that node PINode, node PINode are indicated is equal to C_i, and in the task instances release time to node PINode Between whole task τs_iVery big idle section be all merged into its adjacent interval；Chronologically successively chain enters the phase in chained list Position is answered, chain merges the chained list node that scheduling executes interval time point overlapping margins, the nothing in simulation process while entering chained list Method completes runing time C on chained list_iTo it is corresponding when variable flag value be different from its initial value；Postscript is completed in simulation Record task τ_iCurrent maximum response time LRT_i；If indexed variable flag value is different from its initial value or LRT_i>D_i, then return It returns non-scheduling information and stops to test the schedulability of the task-set；].

The real-time task schedulability based on linear linked list tests semi-direct analogy method, the test simulation Individual task function F2 is to task τ_iIt carries out test to refer to, [when pressing TP module scheduling: " successively from the release of each task instances Time point starts at most elapsed-time standards length LCM_i-1, it is determined whether there is task τ_iPermission section, if it is not, return not Schedulable information simultaneously stops to test the schedulability of the task-set；Logger task τ after the completion of each task instances simulation_iCurrently Maximum response time LRT_i；If LRT_i>D_i, then return to non-scheduling information and stop to survey the schedulability of the task-set Examination；〗；

When by CP module scheduling: " from time point Φ_min ⁽ⁱ⁾Start to time point Φ_min ⁽ⁱ⁾+LCM_i, successively to task τ_iIt is every A task instances determine whether that the sum of siding-to-siding block length is more than or equal to C_i1 or continuous multiple very big idle sections, if do not had Have, then return to non-scheduling information and stops to test the schedulability of the task-set；Postscript is completed in each task instances simulation Record task τ_iCurrent maximum response time LRT_i；If LRT_i>D_i, then return to non-scheduling information and stop to the task-set Schedulability test；〗；].

The real-time task schedulability based on linear linked list tests semi-direct analogy method, the TP model Task τ_iPermission section refer to: task τ_iA free time section EI refer to, for task τ₁,τ₂,...,τ_n-1Scheduling knot A no occupied continuous time range section [t in fruit₁, t₂), t₂>t₁, without task-set { τ in the section₁, τ₂,...,τ_n-1In task release, and in moment t₁And task-set { the τ discharged all before₁,τ₂,...,τ_n-1In Task be all finished；

Task τ_iA free time section [t₁, t₂) it is known as a task τ_iVery big free time section maxEI refer to, moment t₁ For task τ_iRelease time or task-set { τ₁,τ₂,...,τ_n-1In job end time, and from moment t₂It begins with Task-set { τ₁,τ₂,...,τ_n-1In task release or t₂Equal to Φ_min ^(i-1)+k×LCM_i-1, k1；For TP model, such as One task τ of fruit_iIdle section [t₁, t₂) or very big free time section [t₁, t₂) meet t₂-t₁ C_i, then section [t₁, t₂) claim For task τ_iA permission section PI.

The real-time task schedulability based on linear linked list tests semi-direct analogy method, and described provides this Business collects schedulable or non-scheduling information and provides max when providing the information that task-set is schedulable₁ _i _n(LRT_i), table Show whole task τs_iMaximum response time in current priority setting and task release offset.

The real-time task schedulability based on linear linked list tests semi-direct analogy method, the merging scheduling The chained list node for executing interval time point overlapping margins refers to, if can generate in chained list or there are two adjacent node Node1 and Node2 makes the end field value of Node1 be equal to the start field value of Node2, then the two nodes is merged into one A node Node3 chain enters the position of Node1 in chained list, instead of the two nodes of Node1 and Node2, the wherein start of Node3 Field value is assigned a value of the start field value of Node1, and the end field value of Node3 is assigned a value of the end field value of Node2, Node3's Next field value is assigned a value of the next field value of Node2.

The utility model has the advantages that

1. method of the invention is different from existing real-time task (or event) schedulability test method, side of the invention Method by indicated with linear linked list node task (or event) scheduling execute the stage, using linear linked list recording dispatching simulation and Test process, existing real-time task (or event) schedulability test method do not use the simulation of linear linked list record test And scheduling process.

Method of the invention makes the time of method of the invention using the simulation of linear linked list recording dispatching and test process Complexity is to test the polynomial time of task instances quantity total in section, therefore, with existing real-time task (or event) The exponential time of schedulability test method is compared, and from the point of view of common situation, improves efficiency；It is especially higher at preceding n-1 The minimum least common multiple LCM for reaching the period of priority tasks_n-1When much larger than number of tasks, efficiency can be significantly improved.

In existing real-time task (or event) schedulability test method, it should consider to test total in section appoint Pragmatic number of cases amount, meanwhile, test siding-to-siding block length is also greater than equal to LCM_n；In method of the invention, due to LCM_n/T_n LCM_n-1, It need to only consider to test task instances quantity total in section, even if being equal to LCM in test siding-to-siding block length_n-1Or it is equal to LCM_n, adjustable The degree property test of length no more than LCM in section_n；And LCM is equal to for TP model schedulability test siding-to-siding block length_n-1 LCM_n.This The method of invention is in section [Φ_min ^(n-1), Φ_min ^(n-1)+LCM_n-1) the interior preceding n-1 task τ of simulation₁,τ₂,...,τ_n-1, not firm The n-th task is simulated on border, works as LCM_n-1Less than LCM_nWhen method ratio of the invention in section [S, S+LCM_n) in directly simulation whole n it is a The method of task is high-efficient.Method of the invention is to task τ_nOnly check that its schedulability reduces pair without operation simulation The operation for adjusting chained list, improves efficiency.

The adjacent chain list node merging for the condition that meets is advantageously reduced chained list knot in simulation process by method of the invention Point quantity, that is, chained list length, improves the efficiency of test.For example, chained list node quantity used is up to 5 in embodiment 10 and 11, I.e. scan chain table length is up to 5 in simulation process, is siding-to-siding block length LCM than conventional method simulation step number_n-1=LCM_n=24 want small Much.

In the method for the present invention, for distribute n >=1 real-time task on a processor or CPU or Core or Task-set { the τ of person's event₁,τ₂, ...,τ_n, these tasks are periodic or not timing occurs, it is thus necessary to determine that this The schedulability of business collection, each task τ_i, 1iN is endowed a unique fixed priority i, and 1 represents highest priority, N represents lowest priority.

Each task τ_iWith following parameter: max calculation time or maximum runing time C_i ', copy time 0C_i ^copy 1, the load time 0C_i ^restore 1, C_i←C_i ^copy+C_i '+C_i ^restore, scheduling CP mould is preferentially seized for classical Type, C_i ^copy=C_i ^restore=0, i.e. C_i←C_i '；The two neighboring task instances or calling of each task or being most short to for operation It is T up to the time_i；The opposite deadline date that each task instances execute completion is D_i；0<C_i min(D_i, T_i)；When system starts Between t be the moment 0；First task instances of each task are Φ relative to the release offset at moment time 0_i, i.e. task τ_i? One task instances begins to pass through time Φ from the time 0_iIt is released, later at least every time span T_iIt is released, i.e. task τ_i Release time of j-th of task instances be no earlier than as Φ_i+(j–1)×T_i, j is greater than the integer equal to 1 here；Variables L RT_i Logger task τ_iMaximum response time in current priority setting and task release offset, to each k, 2kN, LRT₁ ←C₁, LRT_k←C_k；LCM₁←T₁, LCM_k←lcm(LCM_k–1, T_k)；I, j, k, n take positive integer.To each i, 1iN, note Task τ_iRelease time of first task instances for being no earlier than scheduling stable point S release be that new release deviates, also use Φ_i It indicates, at this moment Φ_min ⁽ⁿ⁾It is equal with S.

Detailed description of the invention:

Attached drawing 1 be 10 the method for the embodiment of the present invention time interval [11,11+24) between schedulability test Figure.

In figure: LCM1=6, LCM2=24, LCM3=24, LCM4=24, CP model.

As i=4, task τ₄Test section [11,11+24) share 2 task instances.

To task instances τ_4,1, C₄=3, from r_4,1=14 start, successively have greatly idle section [15,16), [19,20), [22,23) it meets the requirements, τ_4,1It is schedulable, at this moment LRT₄=9;To task instances τ_4,2, C₄=3, from r_4,2=26 start, and successively have pole Large space section [26,28), [33,35) it meets the requirements, τ_4,2

It is schedulable, at this moment LRT4=9.

LRT₁=2, LRT₂=4, LRT₃=2, LRT₄=9, max_1≤i≤n(LRT_i)=9。

Attached drawing 2 be method described in the embodiment of the present invention 11 time interval [16,16+24) between schedulability test Figure.

In figure: LCM1=6, LCM2=24, LCM3=24, LCM4=24, TP model.

As i=4, task τ₄Test section [16,16+24) share 2 task instances.

To task instances τ_4,1, C₄=3, from r_4,1=16 start, successively have permission section [21,24) meet the requirements, τ_4,1It is adjustable It spends, at this moment LRT₄=8;To task instances τ_4,2, C₄=3, from r_4,2=28 start, successively have Maximum Space section [29,30), [31, 32), then have permission space [37,40) meet the requirements, τ_4,2

It is schedulable, at this moment LRT4=12.

LRT₁=1, LRT₂=3, LRT₃=3, LRT₄=12, max_1≤i≤n(LRT_i)=12。

Specific embodiment:

Embodiment 1:

Specific embodiment:

Embodiment 1:

Embodiment 2:

Semi-direct analogy method, institute are tested according to the real-time task schedulability described in embodiment 1 based on linear linked list That states uses the simulation of linear linked list recording dispatching and test process, first to task τ₁,τ₂,...,τ_n-1, in time range Φ_min ^(n-1)To Φ_min ^(n-1)+ LCM_n-1Each task τ is inside according to priority simulated in descending order_iScheduling execute, then exist To task τ on current chained list_nIt carries out test to refer to, executes and tested using the dispatching simulation of a linear linked list logger task The start field of chained list node is recorded in journey, task instances Starting Executing Time point, and task instances execute intermission point record To the end field of chained list node, each chained list node was indicated from the time point that node start field value provides to the node The continuous scheduling of one or more task instances executes between the time point that end field value provides；Φ_min ⁽¹⁾←Φ₁, LRT₁← C₁；To each i, 2iN, Φ_min ⁽ⁱ⁾←min(Φ_min ^(i-1), Φ_i), LRT_i←C_i；MAX_inter←Φ_min ^(n-1)+ LCM_n-1；It gives Indexed variable flag assigns an initial value；[first in time range Φ_min ^(n-1)To Φ_min ^(n-1)+ LCM_n-1Interior simulation task τ₁From 1st to LCM_n-1/T₁The execution of a task instances, that is, establish LCM_n-1/T₁A chained list node, from small to large to each j, 1 jLCM_n-1/T₁, " the start field of j-th of chained list node is assigned a value of task instances τ_1,jRelease time r_1,j, j-th of chained list The end field of node is assigned a value of r_1,j+C₁；〗；Then to task τ₂,τ₃,...,τ_n-1, in time range Φ_min ^(n-1)It arrives Φ_min ^(n-1)+LCM_n-1Each task τ is inside according to priority simulated in descending order_iFrom the 1st to LCM_n-1/T_iA task The scheduling of example executes, that is, " to each i, 2iN -1, each j, 1jLCM_n-1/T_i, j from small to large successively hold by calling Individual task example function F1 is to task τ for row simulation_iJ-th of task instances τ_i,jIt is simulated；〗；]；I ← n calls test Individual task function F2 is simulated to task τ_iIt is tested；Providing task-set is schedulable information.

Embodiment 3:

Real-time task schedulability according to embodiment 1 or 2 based on linear linked list tests semi-direct analogy method, The execution simulation individual task example function F1 is to task τ_iJ-th of task instances τ_i,jSimulation is carried out to refer to, [according to r_i,jBy being searched and from current work j in chained list compared with start field value and end field value in node in chained list Relative position start, by when CP module scheduling by runing time C_iCorrespond to 1 or continuous multiple tasks τ_iIdle interval chain Table node, the sum of siding-to-siding block length that these nodes indicate are equal to C_i；By when TP module scheduling by runing time C_iCorrespond to task τ_i A permission section node PINode, the siding-to-siding block length that node PINode is indicated is equal to C_i, and in task instances release Between to whole task τs between node PINode_iVery big idle section be all merged into its adjacent interval；Chronologically successively Chain enters the corresponding position in chained list, and chain merges the chained list node that scheduling executes interval time point overlapping margins while entering chained list, Runing time C can not be completed on chained list in simulation process_iTo it is corresponding when variable flag value be different from its initial value； Logger task τ after the completion of simulation_iCurrent maximum response time LRT_i；If indexed variable flag value be different from its initial value or Person LRT_i>D_i, then return to non-scheduling information and stop to test the schedulability of the task-set；].

Embodiment 4:

Real-time task schedulability according to embodiment 1 or 2 or 3 based on linear linked list tests semi-direct simulation side Method, the test simulation individual task function F2 is to task τ_iIt carries out test to refer to, [when pressing TP module scheduling: " successively from every The release time point of a task instances starts at most elapsed-time standards length LCM_i-1, it is determined whether there is task τ_iPermission section, such as Fruit does not have, then returns to non-scheduling information and stop to test the schedulability of the task-set；Each task instances simulation is completed After record task τ_iCurrent maximum response time LRT_i；If LRT_i>D_i, then return to non-scheduling information and stop to this The schedulability test of business collection；〗；

Embodiment 5:

Real-time task schedulability according to embodiment 1 or 2 or 3 or 4 based on linear linked list tests semi-direct mould Quasi- method, the task τ of the TP model_iPermission section refer to: task τ_iA free time section EI refer to, for task τ₁,τ₂,...,τ_n-1Scheduling result in one without occupied continuous time range section [t₁, t₂), t₂>t₁, in the area It is interior there is no task-set { τ₁,τ₂,...,τ_n-1In task release, and in moment t₁And the task-sets discharged all before {τ₁,τ₂,...,τ_n-1In task be all finished；

Embodiment 6:

Real-time task schedulability test according to embodiment 1 or 2 or 3 or 4 or 5 based on linear linked list is semi-direct Analogy method, it is described to provide that the task-set is schedulable or non-scheduling information, it is schedulable information providing task-set When, provide max₁ _i _n(LRT_i), indicate whole task τs_iPeak response in current priority setting and task release offset Time.

Embodiment 7:

Real-time task schedulability test half according to embodiment 1 or 2 or 3 or 4 or 5 or 6 based on linear linked list Direct analogy method, the chained list node that the merging scheduling executes interval time point overlapping margins refers to, if in chained list It can generate or there are two adjacent node Node1 and Node2, and the end field value of Node1 to be made to be equal to the start word of Node2 The two nodes are then merged into the position that a node Node3 chain enters Node1 in chained list, instead of Node1 and Node2 by segment value The two nodes, wherein the start field value of Node3 is assigned a value of the start field value of Node1, and the end field value of Node3 is assigned Value is the end field value of Node2, and the next field value of Node3 is assigned a value of the next field value of Node2.

Embodiment 8:

Real-time task schedulability test according to embodiment 1 or 2 or 3 or 4 or 5 or 6 or 7 based on linear linked list Semi-direct analogy method executes simulation individual task example function F1 to task τ_iJ-th of task instances τ_i,jIt is simulated, That is, [tempC_i←C_i；According to r_i,jIt is current by being searched compared with start field value and end field value in node in chained list Relative position of the operation j in chained list, point or less 5 kinds of situations, and in simulation process as far as possible merge scheduling occupied section when Between put overlapping margins node: (one) is if r_i,jGreater than the end field value of the last one node, then " inter ← MAX_inter– r_i,j；Increase a new node to enter as the last node chain in chained list, the start field value of new node is assigned a value of r_i,j, new to tie The end field value of point is assigned a value of min (r_i,j+tempC_i, MAX_inter)；If inter < tempC_i, then modified logo variable flag Value is different from its initial value；〗；(2) if r_i,jEqual to the end field value of the last one node, then " inter ← MAX is enabled_inter– r_i,j；By min (MAX_inter, r_i,j+tempC_i) it is assigned to the end field of the last one node；If inter < tempC_i, then repair Change indexed variable flag value different from its initial value；〗；(3) if r_i,jLess than the start field value of first node, then " note the One node is Node1, enables the start field value-r of inter ← Node1_i,j；If inter < tempC_i, then " by Node1 Start field value be assigned a value of r_i,j；If it is pressing CP module scheduling, then tempC_i←tempC_i–inter；If it is by TP mould Type is dispatched, then tempC_i←C_i；Then continue to dispatch current j-th of task instances by following situation (five)；』；If inter > tempC_i, then increase a new node and enter as first node chain in chained list, wherein the start field value of new node is assigned Value is r_i,j, the end field value of new node is assigned a value of r_i,j+tempC_i；If inter is equal to tempC_i, then by first node Start field value is assigned a value of r_i,j；〗；(4) make r if there is node Node1 and Node2_i,jEnd field value greater than Node1 And r_i,jStart field value less than Node2, the then " start field value-r of inter ← Node2_i,j；If inter > tempC_i, then in chained list between Node1 and Node2 increase a new node chain enter, wherein newly node start field value It is assigned a value of r_i,j, the end field value of new node is assigned a value of r_i,j+tempC_i；If inter is equal to tempC_i, then by Node2's Start field value is assigned a value of r_i,j；If inter < tempC_i, then " the start field value of Node2 is assigned a value of r_i,j；If it is By CP module scheduling, then tempC_i← tempC_i–inter；If it is pressing TP module scheduling, then tempC_i←C_i；At this time will Node2 is denoted as Node1, then continues to dispatch current j-th of task instances by following situation (five)；』；〗；(5) if there is Node Node1 makes r_i,jStart field value more than or equal to Node1 and the end field value less than or equal to Node1, then continue Current j-th of task instances are dispatched, until the remaining time tempC of current j-th of task instances_iIt is zero, that is, executes loop body H, loop control condition are as follows: work as tempC_i>0；Loop body H specifically: " if " enabled after Node1 without other nodes inter ← MAX_interThe end field value of-Node1；If intertempC_i, then [the end field value of Node1 is added tempC_iIt is assigned to the end field of Node1；LRT_i← max (end field value-the r of Node1_i,j, LRT_i)；tempC_i←0；];Such as Fruit inter < tempC_i, then [the end field value of Node1 is assigned a value of MAX_inter, modified logo variable flag value is different from it Initial value, tempC_i←0；]；』；If having other nodes after Node1: the next field meaning node for remembering Node1 is The end field value of the start field value-Node1 of Node2, inter ← Node2；If inter > tempC_i, then " will End field value+the tempC of Node1_iIt is assigned to the end field of Node1, LRT_i← max (end field value-the r of Node1_i,j, LRT_i)；tempC_i←0；』；If inter is equal to tempC_i, then " LRT_i← max (end field value-the r of Node1_i,j, LRT_i)； The end field value of Node1 is assigned a value of to the end field value of Node2, the next field value of Node1 is assigned a value of to the next of Node2 Field value；tempC_i←0；』；If inter < tempC_i, then " the end field value of Node1 is assigned a value of to the end field of Node2 The next field value of Node1, is assigned a value of the next field value of Node2 by value；If it is pressing CP module scheduling, then tempC_i← tempC_i–inter；If it is pressing TP module scheduling, then tempC_i←C_i；』；〗；At the beginning of if indexed variable flag value is different from it Value or LRT_i>D_i, then return to non-scheduling information and stop to test the schedulability of the task-set；].

Embodiment 9:

Real-time task schedulability according to embodiment 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 based on linear linked list Semi-direct analogy method is tested, test simulation individual task function F2 is to task τ_iIt is tested, that is, [press TP module scheduling When: " on current chained list, from time point Φ_min ⁽ⁱ⁾To time point Φ_min ^(i-1)+LCM_i-1Search whole permission section iPI, note The number for allowing section iPI is k, if k is equal to 0, returns to non-scheduling information and stops the schedulability to the task-set Test；If k > 0, " tempC_i←C_i；Remember from Φ_min ^(i-1)To Φ_min ^(i-1)+LCM_i-1Interior first permission section is [ts₁, ts₂)；To each j, 1jLCM_i/T_i, " mod_j← mod(r_i,j- S, LCM_i-1)+S, if mod_j<Φ_min ^(i-1)And j > 1, then mod_j←mod_j+ LCM_i-1；Remember mod_jFirst permission section later is [t_j1, t_j2), if mod_jTo Φ_min ^(i-1)+LCM_i-1 Between without allow section, then by [ts₁+LCM_i-1, ts₂+LCM_i-1) it is used as mod_jFirst permission section later, is still denoted as [t_j1, t_j2)；If mod_j<t_j1, then, if t_j1≠t₁, then LRT_i←max(t_j1–mod_j+ tempC_i, LRT_i)；"；』；If LRT_i>D_i, then return to non-scheduling information and stop to test the schedulability of the task-set；〗；

When by CP module scheduling: " to each j, 1jLCM_i/T_i, " tempC_i←C_i；mod_j← mod(r_i,j- S, LCM_i-1)+S, if mod_j<Φ_min ^(i-1)And j > 1, then mod_j←mod_j+ LCM_i-1；tempLRT_i← LRT_i, LRT_i←0；Loc ←mod_j；cycle←0；Execute loop body Loop1, loop control condition are as follows: work as tempC_i> 0, loop body Loop1 is specific Are as follows: it " executes and finds task τ_iVery big free time interval function SearchmaxEI (i)；If LRT_i>D_i, then non-scheduling is returned Information simultaneously stops to test the schedulability of the task-set；If indexed variable flag value is different from its initial value, [cycle value Increase by 1；Loc←Φ_min ^(i-1)；Its initial value is assigned to indexed variable flag value；]；』；LRT_i← max(LRT_i, tempLRT_i)；If Indexed variable flag value is different from its initial value or LRT_i>D_i, then return to non-scheduling information and stop to the adjustable of the task-set The test of degree property；〗；Wherein, task τ is found_iVery big free time interval function SearchmaxEI (i) refer to, " in task τ₁, τ₂,...,τ_n-1Scheduling result since time point Loc be no more than time point Φ_min ^(i-1)+LCM_i-1In the range of find task τ_iFirst greatly idle section；If not finding task τ_iVery big free time section maxEI, then [if cycle > 1, return It returns non-scheduling information and stops to test the schedulability of the task-set；Otherwise, modified logo variable flag value is different from it Initial value；]；If finding a task τ_iVery big free time section maxEI, be denoted as [t_j1, t_j2), then " if t_j2–t_j1 tempC_i, then [LRT_i←t_j1+cycle×LCM_i-1–Loc+ tempC_i+ LRT_i；tempC_i←0；]；If t_j2–t_j1< tempC_i, then [LRT_i←t_j2+cycle×LCM_i-1–Loc+LRT_i；tempC_i←tempC_i–(t_j2–t_j1)；Loc← t_j2；]；』；〗；].

Embodiment 10:

It is schedulable according to the real-time task based on linear linked list described in embodiment 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 Property the semi-direct analogy method of test, be scheduled by CP model, the priority of each task instances is as corresponding in the present embodiment The priority of the priority of task, i.e., each task instances is fixed.

Given set of tasks { the τ being made of n=4 periodic task (or event)₁,τ₂,τ₃,τ₄, related parameter such as table 1 It is shown.

1 task parameters of table

2 are shown in Table after stable point S=11 and adjustment release offset have been determined using existing method, by given CP model, Using linear linked list recording dispatching process, an initial value is assigned to indexed variable flag value and uses semi-direct simulation since point S Method carries out task-set { τ₁,τ₂,τ₃,τ₄Schedulability test；Wherein, LCM₁=6, LCM₂=24, LCM₃=24, LCM₄=24。 Φ_min ⁽¹⁾=Φ_min ⁽²⁾=Φ_min ⁽³⁾=Φ_min ⁽⁴⁾=11.Task τ₁,τ₂,τ₃Section [11,11+24) task schedule and task τ₄ Test case is as shown in Fig. 1, all schedulable；Task τ₄Also schedulable after tested.Simulation complete when the task-set it is schedulable and Maximum response time is 9.

The task parameters that table 2 gives stable point S=11 and is adjusted after release offset

Embodiment 11:

It can according to the real-time task based on linear linked list described in embodiment 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 or 10 The semi-direct analogy method of scheduling property test, the present embodiment it is given be to be scheduled by TP model, each task instances it is preferential Grade is the priority of corresponding task, i.e., the priority of each task instances is fixed.

Given set of tasks { the τ being made of n=4 periodic task (or event)₁,τ₂,τ₃,τ₄, related parameter such as table 3 It is shown.

3 task parameters of table

4 are shown in Table after stable point S=16 and adjustment release offset have been determined using existing method, by given TP model, Using linear linked list recording dispatching process, an initial value is assigned to indexed variable flag value；Since point S, semi-direct simulation is used Method carries out task-set { τ₁,τ₂,τ₃,τ₄Schedulability test；Wherein, LCM₁=6, LCM₂=24, LCM₃=24, LCM₄=24。 Task τ₁,τ₂,τ₃Section [16,16+24) task schedule and task τ₄Test case is as shown in Fig. 2, all schedulable；Task τ₄ Also schedulable after tested.The task-set is schedulable when simulation is completed and maximum response time is 12.

Table 4 gives the task parameters for determining stable point S=16 and being adjusted after release offset

Claims

1. a semi-direct simulation method for real-time task schedulability testing based on linear linked list, it is characterized in that: the method comprises: for each i, 1≤i≤n, record task τ _i no earlier than scheduling stable point S The release time of the first task instance released is the new release offset, also denoted by Φ _i , Φ _min ⁽¹⁾ ←Φ ₁ , LRT ₁ ← C ₁ ; for each i, 2≤i≤n, Φ _min ⁽ⁱ⁾ ← min(Φ _min ^(i-1) , Φ _i ), LRT _i ←C _i , according to the given scheduling model, a linear linked list is used to record the scheduling simulation and testing process. First, the tasks τ ₁ , τ ₂ ,...,τ _n-1 , simulate the scheduling of each task τ _i in order of priority from high to low in the time range Φ _min ^(n-1) to Φ _min ^(n-1) + LCM _n-1 Execute, and then test the task τ _n on the current linked list;

LRT _i represents the current maximum response time of task τ _i ; C _i represents the maximum computation or running time of task τ _i ; LCM _n-1 represents the least common multiple of the minimum arrival period of the first n-1 higher priority tasks;

The described scheduling simulation and testing process is recorded using a linear linked list. First, for tasks τ ₁ , τ ₂ ,...,τ _n-1 , in the time range Φ _min ^(n-1) to Φ _min ^(n-1) + In LCM _n-1 , the scheduling execution of each task τ _i is simulated according to the priority from high to low, and then the task τ _n is tested on the current linked list, which means that a linear linked list is used to record the scheduling simulation execution and testing process of the task. , the task instance execution time point is recorded in the start field of the linked list node, the task instance execution termination time point is recorded in the end field of the linked list node, each linked list node represents the time from the start field value of the node to the Continuously scheduled execution of one or more task instances between the time points given by the end field value of the node; Φ _min ⁽¹⁾ ←Φ ₁ , LRT ₁ ←C ₁ ; for each i, 2≤i≤n, Φ _min ⁽ⁱ⁾ ← min(Φ _min ^(i-1) , Φ _i ), LRT _i ←C _i ; MAX _inter ← Φ _min ^(n-1) +LCM _n-1 ; assign an initial value to the flag variable flag ; [First simulate the execution of task τ ₁ from the 1st to the LCM _n-1 /T ₁ task instance in the time range Φ _min ^(n-1) to Φ _min ^(n-1) + LCM _n-1 , that is, to establish LCM _n-1 /T ₁ linked list nodes, for each j from small to large, 1≤j≤LCM _n-1 /T ₁ , the start field of the jth linked list node is assigned as the task instance τ The release time r _1,j _of ₁ ,j, the end field of the jth linked list node is assigned as r ₁ _,j + _C ₁ ; Simulate each task τ _i from _1st to _1st _LCM _n ^- ¹ / Scheduled execution of T _i task instances, that is, 〖for each i, 2≤i≤n-1, for each j, 1≤j≤LCM _n-1 /T _i , j is called sequentially from small to large to simulate a single The task instance function F1 simulates the jth task instance τ _i _,j of the task τ i;〗;]; i←n, call the test to simulate a single task function F2 to test the task τ _i ; the given task set is schedulable Information;

Ti represents the arrival period constant of two adjacent jobs or task instances or calls of task τi.

2. the semi-direct simulation method of real-time task schedulability test based on linear linked list according to claim 1, is characterized in that: described execution simulates single task instance function F1 to the j-th task instance τ _i of task τ _{i ,j} to simulate means, [according to r _i,j in the linked list by comparing with the start field value and end field value in the node to find and start from the relative position of the current job j in the linked list, when scheduling according to the CP model, the The running time C _i corresponds to the free interval linked list nodes of one or more consecutive tasks τ _i , and the sum of the interval lengths represented by these nodes is equal to C _i ; when scheduling according to the TP model, the running time C _i corresponds to the task τ _i An allowable interval node PINode, the interval length represented by the node PINode is equal to C _i , and the maximum idle interval of all tasks τ _i between the release time of the task instance to the node PINode is merged into its adjacent interval; The corresponding positions in the linked list are linked in sequence in time order, and the linked list nodes whose time point boundaries coincide with the execution interval are merged while linked into the linked list, and the flag variable flag cannot be modified on the linked list when the corresponding running time C _i cannot be completed on the linked list during the simulation process. The value is different from its initial value; after the simulation is completed, record the current maximum response time LRT _i of the task τ _i ; if the value of the flag variable flag is different from its initial value or LRT _i >D _i , return unschedulable information and abort the task Set schedulability test;].

3. the semi-direct simulation method of real-time task schedulability test based on linear linked list according to claim 2, it is characterized in that: described test simulation single task function F2 is to test task τ _i and refers to, [by TP model. When scheduling: 〖Sequentially from the release time point of each task instance at most LCM _i-1 , determine whether there is an allowable interval for task τ _i , if not, return the unschedulable information and suspend the availability of the task set. Scheduling test; record the current maximum response time LRT _i of task τ _i after the simulation of each task instance is completed; if LRT _i >D _i , return unschedulable information and abort the schedulability test for the task set; ];

When scheduling according to the CP model: 〖From the time point Φ _min ⁽ⁱ⁾ to the time point Φ _min ⁽ⁱ⁾ +LCM _i , for each task instance of task τ _i in turn, determine whether the sum of the interval lengths is greater than or equal to C _i 1 or more consecutive maximum idle intervals, if not, return unschedulable information and stop the schedulability test of the task set; record the current maximum response time LRT _i of the task τ _i after the simulation of each task instance is completed; If LRT _i > D _i , return unschedulable information and abort the schedulability test for this task set; ];].

4. the semi-direct simulation method of real-time task schedulability test based on linear linked list according to claim 3, it is characterized in that: the allowable interval of the task τ _i of described TP model refers to: an idle interval of task τ _i EI refers to a continuous time range interval [t ₁ , t ₂ ) that is not occupied in the scheduling results of tasks τ ₁ , τ ₂ ,...,τ _n-1 , t ₂ >t ₁ , in this There is no task release in the task set {τ ₁ ,τ ₂ ,...,τ _n-1 } in the interval, and at time t ₁ and before all released task sets {τ ₁ ,τ ₂ ,..., The tasks in τ _n-1 } have been executed;

An idle interval [t ₁ , t ₂ ) of a task τ _i is called a maximum idle interval maxEI of a task τ _i , which means that the time t ₁ is the release time of the task τ _i or the task set {τ ₁ ,τ ₂ ,. ..,τ _n-1 }, and there are tasks in the task set {τ ₁ ,τ ₂ ,...,τ _n-1 } released from time t ₂ or t ₂ is equal to Φ _min ^{( i-1)} +k×LCM _i-1 , k≥1; for the TP model, if the idle interval [t ₁ , t ₂ ) or the maximum idle interval [t ₁ , t ₂ ) of a task τ _i satisfies t ₂ -t ₁ ≥C _i , then the interval [t ₁ , t ₂ ) is called an allowable interval PI of task τ _i .

5. The semi-direct simulation method of real-time task schedulability test based on linear linked list according to claim 4, it is characterized in that: the described task set is given schedulable or unschedulable information, when the task set is given, it is schedulable. When scheduling information, max ₁ ≤ _i ≤ _n (LRT _i ) is given, indicating the maximum response time of all tasks τ _i at the current priority setting and task release offset.

6. the semi-direct simulation method of real-time task schedulability test based on linear linked list according to claim 5, it is characterized in that: the linked list node that described merge scheduling execution interval time point boundary coincides refers to, if in linked list There will be or have two adjacent nodes Node1 and Node2 so that the value of the end field of Node1 is equal to the value of the start field of Node2, then these two nodes will be merged into one node Node3 will be linked to the position of Node1 in the linked list instead of Node1 and Node2, where the start field value of Node3 is assigned the start field value of Node1, the end field value of Node3 is assigned the end field value of Node2, and the next field value of Node3 is assigned the next field value of Node2.