# Utilization Bound Scheduling Analysis for Nonpreemptive Uniprocessor Architecture Using UML-RT

Authors: S. Ewins Pon Pushpa; Manamalli Devasigamani
Journal: Modelling and Simulation in Engineering
 (2014)

---

## Abstract

The key for adopting the utilization-based schedulability test is to derive the utilization bound. Given the computation times, this paper proposes two utilization bound algorithms to derive interrelease times for nonpreemptive periodic tasks, using a new priority scheme, “Rate Monotonic Algorithm-Shortest Job First.” The obtained task set possesses the advantage of Rate Monotonic Algorithm and Shortest Job First priority scheme. Further, the task set is tested for schedulability, by first deriving a general schedulability condition from “problem window” analysis and, a necessary and sufficient schedulability condition for a task to be scheduled, at any release time are also derived. As a technical contribution, success ratio and effective processor utilization are analyzed for our proposed utilization bound algorithms on a uniprocessor architecture modeled using UML-RT.


---

## Body

## 1. Introduction

Tasks in a real-time system must be executed within its deadline to produce functionally correct results in a timely manner. This implies that the timing requirements of tasks, submitted to the real-time system, are known [1]. Each task in a real-time system is scheduled depending on the characteristic of the scheduling algorithm. One of the most widely used uniprocessor scheduling algorithm for periodic real-time tasks is the Rate Monotonic Algorithm (RMA), proposed by Lehoczky et al. in [2]. Let (
τ
=
τ
1
,
τ
2
,
τ
3
,
…
,
τ
m
) denote the task set of “m” tasks in a periodic system. For each task τ
i, task utilization U
i be the ratio of computation time to its interrelease time:U
i
=
C
i
/
T
i. Then, system load U
(
τ
) of a periodic task system be the sum of all utilization of the tasks inτ
:
U
(
τ
)
=
∑
τ
i
∈
τ
U
i. Rate Monotonic Algorithm (RMA) assigns priority—smaller the period, higher the priority, and each task has its own unique priority [3]. According to [4], set of “m” independent preemptive periodic tasks are schedulable using RMA if and only if the system load U
(
τ
) is given by the following:
(1)
U
(
τ
)
≤
m
(
2
1
/
m
-
1
)
.
Later, a minimum utilization bound of RMA for “m” number of preemptive tasks on single processor was found to be in [5] given by the following:
(2)
U
(
τ
)
≤
(
m
-
1
)
(
2
1
/
(
m
-
1
)
+
2
p
-
1
)
,
where p is ratio between any two periods, which is less than 2.There are two types of scheduling strategies: nonpreemptive scheduling and preemptive scheduling. In nonpreemptive strategy, tasks started to execute, would not preempt in an occurrence of higher priority tasks. A higher priority tasks will preempt any lower priority tasks in preemptive scheduling. However, nonpreemptive scheduling is being preferred because they are easier to implement and have lower run-time overhead than preemptive scheduling [6].There is a growing interest in using the object paradigm for developing real-time software [7]. The dominance of software in real-time embedded systems design caused interest in methodologies with widely accepted notations in the software community, such as the Unified Modeling Language (UML). The Unified Modeling Language (UML) is a modeling language for capturing the specification and the implementation using the graphical notations in software community [4]. This approach describes the specification graphically, promotes correctness of the specification, and generates the test scenarios for the implementation automatically. This paper contributes an object-oriented platform-based design, for uniprocessor architecture using UML-RT to analyze the schedulability for the proposed utilization bound algorithms based on a new priority scheme “Rate Monotonic-Shortest Job First” (RM-SJ).In Section2, related works to the proposed method is discussed. Section 3 describes the system model using UML-RT and notations used. Condition for schedulability of a task and general schedulability test are discussed in Sections 4 and 5, respectively. Proposed priority scheme and utilization bound algorithms are discussed in Section 6. A necessary and sufficient schedulability condition for a task to be scheduled, at any release time, is derived in Section 7. Section 8 deals with performance evaluation for the proposed algorithms. Finally, Section 9 concludes with results analyzed.


## 2. Related Works

For single-processor scheduling, Jeffay et al. [6] presented an exact schedulability test of pseudopolynomial time-complexity for a periodic or sporadic task set under nonpreemptive EDF scheduling on a single-processor. George et al. [8] established exact schedulability tests for both nonpreemptive EDF and nonpreemptive fixed-priority scheduling on a single processor with pseudopolynomial time-complexity and addressed general task models in which relative deadlines and periods are not necessarily related. Baruah et al. [3] addressed schedulability analysis for nonpreemptive recurring tasks, which is the general form of nonpreemptive sporadic tasks, and showed that the nonpreemptive schedulability analysis problem can be reduced to a polynomial number of preemptive schedulability analysis problems.The admission control is an algorithm that depends on the scheduling policy and ensures that only tasks that will meet their deadlines are accepted into the system [9]. Accordingly, general bound is derived and used for admission control of RMS-based systems that only requires information about the number of tasks to be admitted in the system. If more information about the tasks characteristics is analyzed, a better admission control can be obtained. For example, the exact characterization described by Lehoczky et al. in [2] uses computation time (C
i) and interrelease time (T
i) values for admission control. In [10], Burchard et al. used knowledge about the periods of the tasks to obtain better admission control for RMS tasks. Clearly, using more information increases the complexity of the admission control since there are more variables to take into consideration during admission control. In [11], Lu et al. derived a schedulability bound for nonpreemptive Rate Monotonic scheduling by using period ratio of the tasks to provide a guarantee that tasks will meet their deadlines. When uniprocessor priority scheme is considered, Liu and Layland [4] showed that Rate Monotonic priority ordering (RMPO) is optimal for independent synchronous periodic tasks. Leung and Whitehead [12] showed that deadline monotonic priority ordering (DMPO) is optimal for independent synchronous tasks with constrained deadlines. Audsley [13] devised an optimal priority assignment (OPA) algorithm that solved the problem of priority assignment for asynchronous tasksets, and for tasks with arbitrary deadlines.In [1], Guan et al. addresse schedulability test conditions for non-preemptive-fixed priority (NP-FP), building upon the “problem window analysis” for preemptive scheduling for multiprocessors. First, linear-time general schedulability test condition that works not only on NP-FP, but also any other work-conserving nonpreemptive scheduling algorithm is derived; then an analysis is done on a test condition of quadratic time-complexity for NP-FP, which has significant performance improvement comparing to the first one. In [14] Bertogna et al. derived a general method for schedulability conditions for multiprocessor real-time systems in a “problem window” and then it is tightened and analyzed for two algorithms, namely, Earliest Deadline First (EDF) and Fixed Priority (FP).This concept of “problem window” analysis done in multiprocessors is generalized on uniprocessor environment for which task schedulability condition and schedulability at any release time for a periodic task are derived. Further two utilization bound algorithms are proposed using a new priority assignment scheme “Rate Monotonic-Shortest Job” (RM-SJ) and task schedulability is analyzed.


## 3. System Model Using UML-RT and Notations

Consider a work conserving nonpreemptive uniprocessor real-time system. A task set,(
τ
=
τ
1
,
τ
2
,
τ
3
,
…
,
τ
m
) where, there are “m” tasks, each task τ
k
=
(
C
k
,
T
k
) is characterized by two parameters—computation time C
k and interrelease time or period T
k, with an interpretation that tasks are generated in every integer multiples of interrelease time to execute C
k units before the next integer interrelease time T. All tasks generated are independent and are executed on a nonpreemptive uniprocessor architecture modelled using UML-RT. The notations used are described in Table 1.Table 1
Notations and description.
Notations used
Description
τ
A task set
m
Total number of tasks inτ
τ
1
Highest priority task
τ
m
Lowest priority task
τ
k
A task in task set
C
k
Computation time ofτ
k
T
k
Interrelease time or period ofτ
k
φ
k
=
T
k
-
C
k
Problem area of the taskτ
k, analyzed for schedulability. A necessary condition for the deadline miss to occur for τ
k is that the worst-case work load, W
•(k)  in the problem area φ
k by all other tasks in the task set τ except τ
k is no less than φ
k.
C
s
k
Computation time lesser thanC
k
C
Nonzero computation time
U
k
=
C
k
/
T
k
Task utilization ofτ
k
U
(
τ
)
=
∑
τ
i
∈
τ
U
i
System load
hp
(
k
)
Set of all higher priority tasks ofτ
k
lp
(
k
)
Set of all lower priority tasks ofτ
k
C
hp
(
k
)
Set of all computation times of hp(
k
)
C
lp
(
k
)
Set of all computation times of lp(
k
)
C
m
Maximum computation time in the subset ofC
lp
(
k
)
hc
(
k
)
Summation of computation times of all higher priorities ofτ
k
hec
(
k
)
Summation of computation times of all equal and higher priorities ofτ
k
lc
(
k
)
Summation of computation times of lower priorities ofτ
k
lec
(
k
)
Summation of computation times of equal and lower priorities ofτ
k
C
hp
(
k
)
Set of all computation times of hp(
k
)
C
lp
(
k
)
Set of all computation times of lp(
k
)
U
hp
(
k
)
Summation of all the task utilization of hp(
k
)
U
elp
(
k
)
Summation of equal and all task utilization of lp(
k
)
r
n
(
k
)
nth release time of τ
k
r
n
+
1
(
k
)
(n
+
1)th release time of τ
k and deadline for the task released at r
n
(
k
)
l
n
(
k
)
Latest feasible start time forτ
k released at r
n
(
k
), to start execution in order to meet its deadline.
N
τ
i
(
k
)
Number of intermediate tasks inφ
k
w
Work done by initial job, intermediate job or final job inφ
k
W
τ
(
k
)
Worst-case latency ofτ
k. It is the maximum time lapse for a task to start execute.
W
•(k)
Total work done by other tasks in the problem area ofφ
k


### 3.1. UML-RT

UML-RT is a modeling tool for real-time, developed by the Rational Corporation. UML-RT uses Unified Modeling Language (UML) to express the original ROOM (Real-Time Object-Oriented Modelling) concepts and extensions. It includes constructs for modelling both behaviour and structural concepts of event-driven real-time systems. Rational Rose Real time is a software development environment tailored to the demands of real time software. It is used to create models of the software system based on the UML constructs, to generate code, compile, and then run and debug the application. Rational Rose Real time can be used through all phases of the software development lifecycle, through design, implementation, test, and final deployment. UML-RT profile introduces a set of common scheduling annotations which are fairly sufficient to perform schedulability analysis [15]. Using Rational Rose Real time developers can execute, test, and debug models at the modelling language level using visual observation tools.In UML-RT the four principle constructs for modelling structure are capsules, ports, protocols, and connectors [5].


#### 3.1.1. Capsules

The fundamental modelling constructs of UML-RT are capsules. Capsules are distributed architectural active objects that interact with other capsules exclusively through one or more ports. The behavior of a capsule is modelled in the state transition diagram that can process (send and receive) messages via their ports, while its (hierarchical) structure is modelled in the capsule structure diagram. The structure diagram for the proposed model using UML-RT is shown in Figure1.Figure 1
Structure diagram for the model proposed in UML-RT.


#### 3.1.2. Ports

Through ports, messages are sent and received to and from capsule instances. Ports connected to a state machine of a capsule (end port) can handle messages sent to them. Capsules and its associated input and output ports are shown in Table2.Table 2
Capsules and associated ports.
Capsules
Input ports
Output ports
Task generator
—
Gout
Scheduler
Sin
Sout
Processor
Pin1
Pout1


#### 3.1.3. Protocols

Protocols define a set of messages exchanged between a set of capsules. Important timer ports and messages used in capsules are shown in Table3.Table 3
Capsules used timer ports and messages.
Capsules
Timer ports
Protocols
Task generator
initial
trigger
Scheduler
Task A
Pa
Task B
Pb
Task C
Pc
Task D
Pd
Task E
Pe
Task F
Pf
Task G
Pg
Task H
Ph
Task I
Pi
Task J
Pj
Task K
Pk
Task L
Pl
Task M
Pm
Task N
Pn
Processor
exetask1
pfree1


#### 3.1.4. Connectors

Connectors capture the key communication relationships between capsule roles. They interconnect capsule roles that have similar public interfaces through ports.


## 3.1. UML-RT

UML-RT is a modeling tool for real-time, developed by the Rational Corporation. UML-RT uses Unified Modeling Language (UML) to express the original ROOM (Real-Time Object-Oriented Modelling) concepts and extensions. It includes constructs for modelling both behaviour and structural concepts of event-driven real-time systems. Rational Rose Real time is a software development environment tailored to the demands of real time software. It is used to create models of the software system based on the UML constructs, to generate code, compile, and then run and debug the application. Rational Rose Real time can be used through all phases of the software development lifecycle, through design, implementation, test, and final deployment. UML-RT profile introduces a set of common scheduling annotations which are fairly sufficient to perform schedulability analysis [15]. Using Rational Rose Real time developers can execute, test, and debug models at the modelling language level using visual observation tools.In UML-RT the four principle constructs for modelling structure are capsules, ports, protocols, and connectors [5].


### 3.1.1. Capsules

The fundamental modelling constructs of UML-RT are capsules. Capsules are distributed architectural active objects that interact with other capsules exclusively through one or more ports. The behavior of a capsule is modelled in the state transition diagram that can process (send and receive) messages via their ports, while its (hierarchical) structure is modelled in the capsule structure diagram. The structure diagram for the proposed model using UML-RT is shown in Figure1.Figure 1
Structure diagram for the model proposed in UML-RT.


### 3.1.2. Ports

Through ports, messages are sent and received to and from capsule instances. Ports connected to a state machine of a capsule (end port) can handle messages sent to them. Capsules and its associated input and output ports are shown in Table2.Table 2
Capsules and associated ports.
Capsules
Input ports
Output ports
Task generator
—
Gout
Scheduler
Sin
Sout
Processor
Pin1
Pout1


### 3.1.3. Protocols

Protocols define a set of messages exchanged between a set of capsules. Important timer ports and messages used in capsules are shown in Table3.Table 3
Capsules used timer ports and messages.
Capsules
Timer ports
Protocols
Task generator
initial
trigger
Scheduler
Task A
Pa
Task B
Pb
Task C
Pc
Task D
Pd
Task E
Pe
Task F
Pf
Task G
Pg
Task H
Ph
Task I
Pi
Task J
Pj
Task K
Pk
Task L
Pl
Task M
Pm
Task N
Pn
Processor
exetask1
pfree1


### 3.1.4. Connectors

Connectors capture the key communication relationships between capsule roles. They interconnect capsule roles that have similar public interfaces through ports.


## 3.1.1. Capsules

The fundamental modelling constructs of UML-RT are capsules. Capsules are distributed architectural active objects that interact with other capsules exclusively through one or more ports. The behavior of a capsule is modelled in the state transition diagram that can process (send and receive) messages via their ports, while its (hierarchical) structure is modelled in the capsule structure diagram. The structure diagram for the proposed model using UML-RT is shown in Figure1.Figure 1
Structure diagram for the model proposed in UML-RT.


## 3.1.2. Ports

Through ports, messages are sent and received to and from capsule instances. Ports connected to a state machine of a capsule (end port) can handle messages sent to them. Capsules and its associated input and output ports are shown in Table2.Table 2
Capsules and associated ports.
Capsules
Input ports
Output ports
Task generator
—
Gout
Scheduler
Sin
Sout
Processor
Pin1
Pout1


## 3.1.3. Protocols

Protocols define a set of messages exchanged between a set of capsules. Important timer ports and messages used in capsules are shown in Table3.Table 3
Capsules used timer ports and messages.
Capsules
Timer ports
Protocols
Task generator
initial
trigger
Scheduler
Task A
Pa
Task B
Pb
Task C
Pc
Task D
Pd
Task E
Pe
Task F
Pf
Task G
Pg
Task H
Ph
Task I
Pi
Task J
Pj
Task K
Pk
Task L
Pl
Task M
Pm
Task N
Pn
Processor
exetask1
pfree1


## 3.1.4. Connectors

Connectors capture the key communication relationships between capsule roles. They interconnect capsule roles that have similar public interfaces through ports.


## 4. Condition for Schedulability of a Task

A necessary condition for deadline miss to occur forτ
k, is that the worst-case work load, W
•
(
k
) by all other tasks in the task set τ except τ
k is no less than φ
k.l
n
(
k
) is the latest feasible start time for τ
k, to start execution in order to meet its deadline as shown in Figure 2.Figure 2
Problem areaφ
k, for the task τ
k.The aim is to compute the individual contribution of worst-case workload by other tasks, that is,τ
i
∈
τ, in the problem area, φ
k as shown in Figure 2. The work load in φ
k can be categorized into three parts as shown in Figure 3.Figure 3
Work done by other tasks inφ
k.Initial Job. The contribution of task τ
i, in problem area φ
k, is when computation of task τ
i started earlier or at r
n
(
k
) and having deadline in the problem area.Intermediate Job,   N
τ
i
(
k
). The computation of a task τ
i started in φ
k and having deadline in the problem area earlier to l
n
(
k
).Final Job. The contribution of task τ
i in problem area φ
k is when computation of task τ
i started in φ
k and having deadline later or at l
n
(
k
). Assume that all tasks contribute maximum in the problem area. This is a pessimistic but safe approximation to count the workload of a task in the problem area [3].Forτ
(
k
) to be scheduled,
(3)
W
•
(
k
)
≤
φ
k
,
where
(4)
W
•
(
k
)
=
∑
hp
(
k
)
,
lp
(
k
)
w
(
initial
jobs
+
intermediate
jobs
+
final
jobs
)
.


## 5. General Schedulability Test

The entire task set is schedulable only when each task is schedulable. The computation timings of tasks are arranged,C
1
≤
C
2
≤
C
3
≤
⋯
≤
C
k
≤
⋯
≤
C
m.Theorem 1.
Highest priority taskτ
1is schedulable by a work conserving nonpreemptive scheduling algorithm if
(5)
φ
1
≥
C
m
.Proof.
By contradiction if,φ
1
<
C
m, then the highest priority task τ
k may miss its deadline. We recall that C
m is the maximum computation time in the subset of C
lp
(
1
). For a nonpreemptive architecture, any τ
j
∈
hp
⁡
(
1
) will not be preempted, if it starts to execute before the release time of any higher priority task. Consider that j
=
m. From Figure 4, it is shown that τ
j, which started to execute C
m at r
n
-
1
(
j
), is still executing beyond l
n
(
1
) causing the task τ
1 to miss deadline.
Therefore, ifφ
1
≥
C
m, then τ
1will be schedulable.Figure 4
C
m starts to execute before r
n
(
1
) and still executing beyond l
n
(
1
).Theorem 2.
A taskτ
k is schedulable by a work conserving nonpreemptive scheduling algorithm if
(6)
1
-
C
m
φ
k
+
U
e
l
p
(
k
)
≥
U
(
τ
)
.Proof.
In [3], an algorithm is work conserving, if there are no idle processors, when a ready task is waiting. Schedulability condition for a task τ
k is given by (3) and (4). The final job contribution is bounded in the second term RHS of (7). Therefore, from (4) the general schedulability for τ
k will be
(7)
φ
k
≥
C
m
+
∑
hp
(
k
)
w
(
intermediate
jobs
)
,
(8)
φ
k
≥
C
m
+
∑
τ
i
∈
hp
(
k
)
φ
k
T
i
C
i
.
Equation (8) indicates pessimistic and sufficient condition for a task to be schedulable. A task will be scheduled in the task set if (8) is satisfied. Therefore,
(9)
φ
k
≥
C
m
+
φ
k
U
hp
(
k
)
,
(10)
φ
k
≥
C
m
+
φ
k
(
U
(
τ
)
-
U
elp
(
k
)
)
,
φ
k
-
C
m
≥
φ
k
(
U
(
τ
)
-
U
elp
(
k
)
)
,
dividing by φ
k,
(11)
1
-
C
m
φ
k
+
U
elp
(
k
)
≥
U
(
τ
)
.
Equation (11) is the condition for a task τ
k to be schedulable.
Sufficient schedulability condition for least priority task from (9),
(12)
φ
k
≥
φ
k
U
hp
(
k
)
C
m, is neglected in (12), because schedulability condition for τ
m to execute C
m is analyzed.


## 6. Proposed Utilization Bound Algorithms

### 6.1. Rate Monotonic Algorithm-Shortest Job First (RMA-SJF)

In shortest job first (SJF), priority is given to shortest computation time, independent of interrelease time of the tasks, thus minimizing the waiting time and improving the throughput [6]. Rate monotonic algorithm (RMA) is of great practical importance because priority is given to tasks with lesser release time. This paper proposes two utilization bound algorithms to derive a task set which satisfies both RMA-SJF priority scheme; that is, higher priority tasks will have lesser computation time and lesser interrelease time.When a set of computation times are given, our aim is to design a work conserving task system, to utilize the available processing capacity. To achieve maximum processing capacity, system load must be equal to unity for a uniprocessor system [8]. In [3], an algorithm is work conserving, if processor is not idle, when a ready task is waiting. Therefore, behavior of the system developed is strongly dependent upon the periods of the task comprising the task set [16].


### 6.2. Method 1: Work Conserving Utilization Bound

Initially the algorithm aims to schedule “m
-
a” tasks, by deriving the highest priority task release time T
1
=
hec
(
m
-
1
). Schedulability of each task is analyzed using the general schedulability test. Later T
i of tasks are varied to find an optimized utilization bound in 0.9
<
U
(
τ
)
≤
1 to schedule “m” tasks utilizing the processor effectively (see Algorithm 1).Algorithm 1
Step  1. Computation times are randomly generated and arranged according to shortest job first
priority scheme.
C
1
≤
C
2
≤
C
3
≤
⋯
≤
C
k
≤
⋯
≤
C
m
Initializea
=
1;
Step  2. hec
(
m
-
a
)
=
C
(
1
)
+
C
(
2
)
+
⋯
+
C
(
m
-
a
)
hec
(
m
)
=
C
(
1
)
+
C
(
2
)
+
⋯
+
C
(
m
)
Step  3.  l
δ
=
hec
(
m
-
a
)
,
l
δ
<
hec
(
m
)
Step  4. assign T
1
=
l
δ;
fori
=
2  to m
doT
i
=
T
i
-
1
+
C
i
-
1
end for
Step  5. Find U
(
τ
)
=
∑
τ
i
∈
τ
U
i where U
i
=
C
i
/
T
i
Step  6. if 0.9
<
U
(
τ
)
≤
1;
Step  6.1. Vary T
i, such that processor is effectively utilized to schedule “m” tasks in U
(
τ
).
ThereforeU
(
τ
) is work conserving utilization bound.
Step  6.2. exit;
Step  7. if U
(
τ
)
<
0.9; l
δ
-
-; go to Step  4.
Step  8. if U
(
τ
)
>
1; l
δ
+
+; go to Step  4.


### 6.3. Method 2: Worst-Case Utilization Bound

In method 2, the worst-case latency of each task is considered to compute its interrelease time. Worst-case response time (W
τ) of each task is found at critical instant, where all tasks are released instantaneously (see Algorithm 2).Algorithm 2
Step  1. Arrange computation times according to shortest job first,
C
1
≤
C
2
≤
C
3
≤
⋯
≤
C
k
≤
⋯
≤
C
m
Step  2. Worst case response time of tasks analyzed. It is the maximum time lapse for a task to
start to execute.  So it is known that,
W
τ
(
1
)
=
C
m
˚
W
τ
(
k
)
=
hc
(
k
) +  C
m
˚
W
τ
(
m
)
=
hc
(
m
)
Step  3. T
1
=
W
τ
(
1
)
+
C
1;
Step  4. for i
=
2 to m do
T
i
=
W
τ
(
i
)
end for
Step  5. Worst case utilization bound, U
(
τ
)
=
∑
τ
i
∈
τ
U
i where U
i
=
C
i
/
T
i
Step  6. Check schedulability of  “m” tasks by general schedulability test and find success
ratio and effective processor utilization.
Step  7. exit.


## 6.1. Rate Monotonic Algorithm-Shortest Job First (RMA-SJF)

In shortest job first (SJF), priority is given to shortest computation time, independent of interrelease time of the tasks, thus minimizing the waiting time and improving the throughput [6]. Rate monotonic algorithm (RMA) is of great practical importance because priority is given to tasks with lesser release time. This paper proposes two utilization bound algorithms to derive a task set which satisfies both RMA-SJF priority scheme; that is, higher priority tasks will have lesser computation time and lesser interrelease time.When a set of computation times are given, our aim is to design a work conserving task system, to utilize the available processing capacity. To achieve maximum processing capacity, system load must be equal to unity for a uniprocessor system [8]. In [3], an algorithm is work conserving, if processor is not idle, when a ready task is waiting. Therefore, behavior of the system developed is strongly dependent upon the periods of the task comprising the task set [16].


## 6.2. Method 1: Work Conserving Utilization Bound

Initially the algorithm aims to schedule “m
-
a” tasks, by deriving the highest priority task release time T
1
=
hec
(
m
-
1
). Schedulability of each task is analyzed using the general schedulability test. Later T
i of tasks are varied to find an optimized utilization bound in 0.9
<
U
(
τ
)
≤
1 to schedule “m” tasks utilizing the processor effectively (see Algorithm 1).Algorithm 1
Step  1. Computation times are randomly generated and arranged according to shortest job first
priority scheme.
C
1
≤
C
2
≤
C
3
≤
⋯
≤
C
k
≤
⋯
≤
C
m
Initializea
=
1;
Step  2. hec
(
m
-
a
)
=
C
(
1
)
+
C
(
2
)
+
⋯
+
C
(
m
-
a
)
hec
(
m
)
=
C
(
1
)
+
C
(
2
)
+
⋯
+
C
(
m
)
Step  3.  l
δ
=
hec
(
m
-
a
)
,
l
δ
<
hec
(
m
)
Step  4. assign T
1
=
l
δ;
fori
=
2  to m
doT
i
=
T
i
-
1
+
C
i
-
1
end for
Step  5. Find U
(
τ
)
=
∑
τ
i
∈
τ
U
i where U
i
=
C
i
/
T
i
Step  6. if 0.9
<
U
(
τ
)
≤
1;
Step  6.1. Vary T
i, such that processor is effectively utilized to schedule “m” tasks in U
(
τ
).
ThereforeU
(
τ
) is work conserving utilization bound.
Step  6.2. exit;
Step  7. if U
(
τ
)
<
0.9; l
δ
-
-; go to Step  4.
Step  8. if U
(
τ
)
>
1; l
δ
+
+; go to Step  4.


## 6.3. Method 2: Worst-Case Utilization Bound

In method 2, the worst-case latency of each task is considered to compute its interrelease time. Worst-case response time (W
τ) of each task is found at critical instant, where all tasks are released instantaneously (see Algorithm 2).Algorithm 2
Step  1. Arrange computation times according to shortest job first,
C
1
≤
C
2
≤
C
3
≤
⋯
≤
C
k
≤
⋯
≤
C
m
Step  2. Worst case response time of tasks analyzed. It is the maximum time lapse for a task to
start to execute.  So it is known that,
W
τ
(
1
)
=
C
m
˚
W
τ
(
k
)
=
hc
(
k
) +  C
m
˚
W
τ
(
m
)
=
hc
(
m
)
Step  3. T
1
=
W
τ
(
1
)
+
C
1;
Step  4. for i
=
2 to m do
T
i
=
W
τ
(
i
)
end for
Step  5. Worst case utilization bound, U
(
τ
)
=
∑
τ
i
∈
τ
U
i where U
i
=
C
i
/
T
i
Step  6. Check schedulability of  “m” tasks by general schedulability test and find success
ratio and effective processor utilization.
Step  7. exit.


## 7. Sufficient Schedulability Condition at Any Release Time

Sufficient schedulability condition forτ
k
∈
τ in its release time r
n
(
k
) is derived. Let φ
k be the problem area of τ
k shown in Figure 5, and l
n
(
k
) is the latest feasible start time to execute C
k, for τ
k to be schedulable.Figure 5
τ
j
∈
hp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
).Consider the worst-case latency analyzed in Section6.3. The contributions of worst-case work load of other tasks are analyzed under two cases.Case A.
hp
(
k
), lp
(
k
) released before r
n
(
k
).Case B.
hp
(
k
), lp
(
k
) released in [r
n
(
k
), l
n
(
k
)].


### 7.1. Case A:hp
(
k
), lp
(
k
) Released before r
n
(
k
)

#### 7.1.1.hp
(
k
) Released before r
n
(
k
)

Figure5 shows τ
j
∈
hp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
):
(13)
N
τ
i
(
k
)
=
0
;Lemma 3.
Taskτ
j
∈
hp
⁡
(
k
) released before r
n
(
k
), will contribute initial job or intermediate job, if r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
).Proof.
To prove by contradiction, ifr
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
r
n
(
k
), then this task τ
j does not contribute any workload in work area; therefore, for this condition there is no initial or intermediate job. Therefore, r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
) will contribute initial job or intermediate job.(1)
Initial job will be present if,r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
≤
C
j
(i)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
=
C
j, then initial job will be C
j;
(ii)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
<
C
j, thenr
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
=
C
s
j
<
C
j; therefore, the initial job will be C
s
j.
(2)
Intermediate job will be present if,r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j.
For the above condition,(14)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
-
C
j
=
C
>
0
.
Recalling that all tasks contribute maximum in the problem area, τ
i is assumed to start execute in φ
k and has deadline in problem area. So, r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j will contribute intermediate job, N
τ
i
(
k
).


#### 7.1.2.lp
(
k
) Released before r
n
(
k
)

Figure6 shows τ
j
∈
lp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
). Maximum contribution of any lp
(
k
) will be the task having maximum computation time as initial job released at r
n
-
1
(
j
) and started to execute before r
n
(
k
). Therefore, initial job = C
m.Figure 6
τ
j
∈
lp
⁡
(
k
) released in r
n
-
1
(
j
) before r
n
(
k
).


### 7.2. Case B:hp
(
k
), lp
(
k
) Released in [
r
n
(
k
), l
n
(
k
)
]

#### 7.2.1.hp
(
k
) Released [
r
n
(
k
)
,
l
n
(
k
)
]

Lemma 4.
Ifτ
j
∈
hp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will contribute intermediate job, ifr
n
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
), while τ
j is pending.Proof.
Recalling that, contribution of the task started to execute in problem area and finishes beforel
n
(
k
) is intermediate job.
For(15)
(
r
n
(
j
)
+
T
(
j
)
=
r
n
+
1
(
j
)
,
r
n
+
1
(
j
)
<
l
n
(
k
)
,
n
+
+
)
{
N
τ
i
(
k
)
+
+
;
}
.
The above equation shows that there are N
τ
i
(
k
) intermediate jobs contributed by, τ
i
∈
hp
(
k
) in the problem area while τ
k is pending.Lemma 5.
Ifτ
j
∈
hp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will contribute final job, if
(16)
r
n
(
j
)
+
W
τ
(
j
)
+
C
j
≥
l
n
(
k
)
.Proof.
Consider Figure7. By contradiction, if r
n
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
), then by Lemma 4, this condition possesses intermediate job. Therefore, r
n
(
j
)
+
W
τ
(
j
)
+
C
j
≥
l
n
(
k
) will contribute final job (see Algorithm 3).Algorithm 3
(i) According to the definition of final job,
ifr
n
(
j
)
+
W
τ
(
j
)
+
C
j
=
l
n
(
k
), then
r
n
(
j
)
+
W
τ
(
j
)
-
l
n
(
k
)
=
|
C
j
|  therefore the final job will be C
j
elser
n
(
j
)
+
W
τ
(
j
)
+
C
j
>
l
n
(
k
), then
r
n
(
j
)
+
W
τ
(
j
)
+
C
j
-
l
n
(
k
)
=
C
>
0;
ifW
τ
(
j
)
+
C
j
-
C
≥
C
j then, final job will be C
j
else final job isC
s
j
=
W
τ
(
j
)
+
C
j
-
CFigure 7
τ
j
∈
lp
⁡
(
k
) released in [
r
n
(
k
)
,
l
n
(
k
)
].


#### 7.2.2.lp
(
k
) Released in [
r
n
(
k
)
,
l
n
(
k
)
]

Lemma 6.
Ifτ
j
∈
lp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will have no contribution in φ
k for scheduling τ
k.Proof.
Anylp
(
k
) released in [r
n
(
k
)
,
l
n
(
k
)], as shown in Figure 7, will have no contribution in φ
k because anylp
(
k
)is executed. So, lp
(
k
) released in [r
n
(
k
)
,
l
n
(
k
)] will contribute no workload in φ
k.


## 7.1. Case A:hp
(
k
), lp
(
k
) Released before r
n
(
k
)

### 7.1.1.hp
(
k
) Released before r
n
(
k
)

Figure5 shows τ
j
∈
hp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
):
(13)
N
τ
i
(
k
)
=
0
;Lemma 3.
Taskτ
j
∈
hp
⁡
(
k
) released before r
n
(
k
), will contribute initial job or intermediate job, if r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
).Proof.
To prove by contradiction, ifr
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
r
n
(
k
), then this task τ
j does not contribute any workload in work area; therefore, for this condition there is no initial or intermediate job. Therefore, r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
) will contribute initial job or intermediate job.(1)
Initial job will be present if,r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
≤
C
j
(i)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
=
C
j, then initial job will be C
j;
(ii)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
<
C
j, thenr
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
=
C
s
j
<
C
j; therefore, the initial job will be C
s
j.
(2)
Intermediate job will be present if,r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j.
For the above condition,(14)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
-
C
j
=
C
>
0
.
Recalling that all tasks contribute maximum in the problem area, τ
i is assumed to start execute in φ
k and has deadline in problem area. So, r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j will contribute intermediate job, N
τ
i
(
k
).


### 7.1.2.lp
(
k
) Released before r
n
(
k
)

Figure6 shows τ
j
∈
lp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
). Maximum contribution of any lp
(
k
) will be the task having maximum computation time as initial job released at r
n
-
1
(
j
) and started to execute before r
n
(
k
). Therefore, initial job = C
m.Figure 6
τ
j
∈
lp
⁡
(
k
) released in r
n
-
1
(
j
) before r
n
(
k
).


## 7.1.1.hp
(
k
) Released before r
n
(
k
)

Figure5 shows τ
j
∈
hp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
):
(13)
N
τ
i
(
k
)
=
0
;Lemma 3.
Taskτ
j
∈
hp
⁡
(
k
) released before r
n
(
k
), will contribute initial job or intermediate job, if r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
).Proof.
To prove by contradiction, ifr
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
r
n
(
k
), then this task τ
j does not contribute any workload in work area; therefore, for this condition there is no initial or intermediate job. Therefore, r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
) will contribute initial job or intermediate job.(1)
Initial job will be present if,r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
≤
C
j
(i)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
=
C
j, then initial job will be C
j;
(ii)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
<
C
j, thenr
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
=
C
s
j
<
C
j; therefore, the initial job will be C
s
j.
(2)
Intermediate job will be present if,r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j.
For the above condition,(14)
r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
-
C
j
=
C
>
0
.
Recalling that all tasks contribute maximum in the problem area, τ
i is assumed to start execute in φ
k and has deadline in problem area. So, r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j will contribute intermediate job, N
τ
i
(
k
).


## 7.1.2.lp
(
k
) Released before r
n
(
k
)

Figure6 shows τ
j
∈
lp
⁡
(
k
) released at r
n
-
1
(
j
) before r
n
(
k
). Maximum contribution of any lp
(
k
) will be the task having maximum computation time as initial job released at r
n
-
1
(
j
) and started to execute before r
n
(
k
). Therefore, initial job = C
m.Figure 6
τ
j
∈
lp
⁡
(
k
) released in r
n
-
1
(
j
) before r
n
(
k
).


## 7.2. Case B:hp
(
k
), lp
(
k
) Released in [
r
n
(
k
), l
n
(
k
)
]

### 7.2.1.hp
(
k
) Released [
r
n
(
k
)
,
l
n
(
k
)
]

Lemma 4.
Ifτ
j
∈
hp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will contribute intermediate job, ifr
n
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
), while τ
j is pending.Proof.
Recalling that, contribution of the task started to execute in problem area and finishes beforel
n
(
k
) is intermediate job.
For(15)
(
r
n
(
j
)
+
T
(
j
)
=
r
n
+
1
(
j
)
,
r
n
+
1
(
j
)
<
l
n
(
k
)
,
n
+
+
)
{
N
τ
i
(
k
)
+
+
;
}
.
The above equation shows that there are N
τ
i
(
k
) intermediate jobs contributed by, τ
i
∈
hp
(
k
) in the problem area while τ
k is pending.Lemma 5.
Ifτ
j
∈
hp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will contribute final job, if
(16)
r
n
(
j
)
+
W
τ
(
j
)
+
C
j
≥
l
n
(
k
)
.Proof.
Consider Figure7. By contradiction, if r
n
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
), then by Lemma 4, this condition possesses intermediate job. Therefore, r
n
(
j
)
+
W
τ
(
j
)
+
C
j
≥
l
n
(
k
) will contribute final job (see Algorithm 3).Algorithm 3
(i) According to the definition of final job,
ifr
n
(
j
)
+
W
τ
(
j
)
+
C
j
=
l
n
(
k
), then
r
n
(
j
)
+
W
τ
(
j
)
-
l
n
(
k
)
=
|
C
j
|  therefore the final job will be C
j
elser
n
(
j
)
+
W
τ
(
j
)
+
C
j
>
l
n
(
k
), then
r
n
(
j
)
+
W
τ
(
j
)
+
C
j
-
l
n
(
k
)
=
C
>
0;
ifW
τ
(
j
)
+
C
j
-
C
≥
C
j then, final job will be C
j
else final job isC
s
j
=
W
τ
(
j
)
+
C
j
-
CFigure 7
τ
j
∈
lp
⁡
(
k
) released in [
r
n
(
k
)
,
l
n
(
k
)
].


### 7.2.2.lp
(
k
) Released in [
r
n
(
k
)
,
l
n
(
k
)
]

Lemma 6.
Ifτ
j
∈
lp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will have no contribution in φ
k for scheduling τ
k.Proof.
Anylp
(
k
) released in [r
n
(
k
)
,
l
n
(
k
)], as shown in Figure 7, will have no contribution in φ
k because anylp
(
k
)is executed. So, lp
(
k
) released in [r
n
(
k
)
,
l
n
(
k
)] will contribute no workload in φ
k.


## 7.2.1.hp
(
k
) Released [
r
n
(
k
)
,
l
n
(
k
)
]

Lemma 4.
Ifτ
j
∈
hp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will contribute intermediate job, ifr
n
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
), while τ
j is pending.Proof.
Recalling that, contribution of the task started to execute in problem area and finishes beforel
n
(
k
) is intermediate job.
For(15)
(
r
n
(
j
)
+
T
(
j
)
=
r
n
+
1
(
j
)
,
r
n
+
1
(
j
)
<
l
n
(
k
)
,
n
+
+
)
{
N
τ
i
(
k
)
+
+
;
}
.
The above equation shows that there are N
τ
i
(
k
) intermediate jobs contributed by, τ
i
∈
hp
(
k
) in the problem area while τ
k is pending.Lemma 5.
Ifτ
j
∈
hp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will contribute final job, if
(16)
r
n
(
j
)
+
W
τ
(
j
)
+
C
j
≥
l
n
(
k
)
.Proof.
Consider Figure7. By contradiction, if r
n
(
j
)
+
W
τ
(
j
)
+
C
j
<
l
n
(
k
), then by Lemma 4, this condition possesses intermediate job. Therefore, r
n
(
j
)
+
W
τ
(
j
)
+
C
j
≥
l
n
(
k
) will contribute final job (see Algorithm 3).Algorithm 3
(i) According to the definition of final job,
ifr
n
(
j
)
+
W
τ
(
j
)
+
C
j
=
l
n
(
k
), then
r
n
(
j
)
+
W
τ
(
j
)
-
l
n
(
k
)
=
|
C
j
|  therefore the final job will be C
j
elser
n
(
j
)
+
W
τ
(
j
)
+
C
j
>
l
n
(
k
), then
r
n
(
j
)
+
W
τ
(
j
)
+
C
j
-
l
n
(
k
)
=
C
>
0;
ifW
τ
(
j
)
+
C
j
-
C
≥
C
j then, final job will be C
j
else final job isC
s
j
=
W
τ
(
j
)
+
C
j
-
CFigure 7
τ
j
∈
lp
⁡
(
k
) released in [
r
n
(
k
)
,
l
n
(
k
)
].


## 7.2.2.lp
(
k
) Released in [
r
n
(
k
)
,
l
n
(
k
)
]

Lemma 6.
Ifτ
j
∈
lp
⁡
(
k
) released [
r
n
(
k
)
,
l
n
(
k
)
] will have no contribution in φ
k for scheduling τ
k.Proof.
Anylp
(
k
) released in [r
n
(
k
)
,
l
n
(
k
)], as shown in Figure 7, will have no contribution in φ
k because anylp
(
k
)is executed. So, lp
(
k
) released in [r
n
(
k
)
,
l
n
(
k
)] will contribute no workload in φ
k.


## 8. Performance Evaluation

Example 1.
Given the computation timeC
i = (6, 5, 7, 3, 4, 2) the aim is to find optimum interrelease time for each task to achieve 100% success ratio by utilizing the processor effectively by work conserving utilization bound algorithm.
First computation times are arranged in nondecreasing order:(17)
C
i
=
{
2
≤
3
≤
4
≤
5
≤
6
≤
7
}
.
The various system load values by varying T
i are shown in Table 4. All timings are in seconds.Table 4
Analysis of work conserving utilization bound algorithm for various set ofT
i.
C
i
Interrelease time,T
i analyzed by work conserving utilization bound algorithm
2
20
19
18
18
18
18
18
18
18
18
18
3
22
21
21
20
20
20
20
20
20
20
20
4
25
24
24
24
23
23
23
23
23
23
23
5
29
28
28
28
28
27
27
27
27
27
27
6
34
33
33
33
33
33
33
32
32
32
32
7
40
39
39
39
39
40
39
40
39
38
37
U
(
τ
)
0.92024
0.95466
0.96051
0.96766
0.9749
0.97702
0.98152
0.98271
0.9872
0.99192
0.9969Maximum utilization bound was found to be 0.9969 for the task set given below:τ
=
{
2
/
18
,
3
/
20
,
4
/
23
,
5
/
27
,
6
/
33
,
7
/
36
}. When schedulability of τ
(
6
) was analyzed, K
=
6; C
6
=
7; φ
6 = 36 − 7 = 29; U
(
τ
) = 0.9964. Lowest priority task τ
(
6
)will be schedulable if (12) is satisfied:
(18)
φ
k
≥
φ
k
U
hp
(
k
)
,
29
≥
28.898
.
Though the condition is satisfied, τ
(
6
) is unschedulable practically because of runtime of the algorithm. The runtime of the algorithm for six tasks is found to be 0.37599 seconds. In order to compensate the runtime, period is incremented and the problem is analyzed practically.For the task set,U
(
τ
)
=
{
2
/
18
,
3
/
20
,
4
/
23
,
5
/
27
,
6
/
33
,
7
/
40
}, utilization bound U
(
τ
)
=
0.977, the task set τ is found schedulable using processor effectively as shown in Figure 8.(i)
WhenU
(
τ
)
<
0.977, all tasks are schedulable, using less processor capacity.
(ii)
WhenU
(
τ
)
>
0.977 task set is found unschedulable because of runtime of algorithm.When U
(
τ
)
=
0.977 task set is schedulable using processor capacity effectively with 97.5% as showed in Table 5. For the system load U
(
τ
)
=
0.977 the effective processor utilization is found to be 97.5.Table 5
Success ratio and effective processor utilization for various loads analyzed.
Systemload
Successratio
Effectiveprocessorutilization
0.9964
96.02
92.83
0.9919
98.5
96.66
0.9871
98.78
96.66
0.962
97.97
95.27
0.986
98.13
95.85
0.9827
98.35
95.5
0.9784
99.52
97.05
0.977
100
97.5
0.9749
100
96.72
0.9676
100
96.16
0.9605
100
95.83
0.9546
100
94
0.9202
100
91.16Figure 8
Success ratio and effective processor utilization analyzed for example, task set using UML-RT.Extensive simulations are conducted in UML-RT, for the worst-case utilization bound and work conserving unity utilization bound and their performance is compared. The task parameters settings are as follows: for each task computation timings are randomly distributed in{
2,19
}; Ti is calculated according to the two algorithms proposed. Maximum of 14 tasks are generated, to compare the success ratio and effective processor utilization. Figure 9 shows the comparison of utilization bound derived for the two algorithms proposed. From Figure 10, the success ratio for work conserving unity utilization bound is high compared to worst-case utilization bound. Using the worst-case workload of task the utilization bound or the system load derived is heavily loaded for Worst-Case Utilization Bound Algorithm. Effective processor utilized by the proposed algorithm is shown in Figure 11.Figure 9
Comparison of utilization bound of two algorithms proposed.Figure 10
Success ratio versus number of tasks.Figure 11
Comparison of Effective processor utilization of the algorithms proposed.Advantage of Work Conserving Utilization Bound
(i)
Processor can be effectively utilized to schedule task set.Example 2.
To find whetherτ
(
5
) is schedulable for the task set having U
(
τ
)
=
0.9827as shown in Table 4 by general schedulability test.Solution. For τ
(
5
) to be schedulable, (8) is sufficient condition:
(19)
K
=
5
;
C
5
=
6
;
C
m
=
7
;
φ
5
=
32
-
6
=
26
;
U
(
τ
)
=
0.9827
,
φ
k
≥
C
m
+
∑
τ
i
∈
hp
(
k
)
φ
k
T
i
C
i
,
φ
5
≥
C
m
+
∑
τ
i
∈
hp
(
k
)
φ
5
T
i
C
i
,
26
≥
7
+
16.125
,
26
≥
23.125
.
Therefore, τ
(
5
) is schedulable by general schedulability test.When schedulability ofτ
(
6
) was analyzed,K
=
6; C
6
=
7; φ
6
=
40
-
7
=
33; U
(
τ
) = 0.9827. Lowest priority task τ
(
6
) will be schedulable if (12) is satisfied:
(20)
φ
k
≥
φ
k
U
hp
(
k
)
,
33
≥
22.6544
.
Similarly, all the tasks are tested for schedulability and practically found schedulable using UML-RT.(ii) To find whetherτ
(
5
) in the task set τ
=
{
(
2,11
)
,
(
2,13
)
,
(
3,15
)
,
(
3,18
)
,
(
4,21
)
,
(
4,25
)
} is schedulable in its 54th release.Herek
=
5, 5th task W
•
(
k
)
≤
φ
k for τ
n
(
k
) to be scheduled, where
(21)
W
•
(
k
)
=
∑
hp
(
k
)
,
lp
(
k
)
w
(
initial
jobs
+
intermediate
jobs
+
final
jobs
)Case 1.
54th release time of the taskτ
(
5
), r
54
(
5
) = 1134 and r
55
(
5
) = 1155.
C
5 = 4; therefore, l
54
(
5
) = 1155 − 4 = 1151 and φ
5= 17. Figure 12 shows the problem area of ϕ
(
5
).(a)
Finding initial job or intermediate job contribution ofτ
1
(22)
r
54
(
5
)
MOD
T
1
=
1
,
r
n
-
1
(
1
)
=
1134
-
1
=
1133
,
r
n
(
1
)
=
1144
W
τ
(
1
)
=
max
⁡
[
C
lp
(
1
)
]; therefore, W
τ
(
1
)
= 4. By Lemma 3, taskτ
j
∈
hp
⁡
(
k
) released before r
n
(
k
), will contribute initial job or intermediate job, if r
n
(
k
)
<
r
n
-
1
(
j
)
+
W
τ
(
1
)
+
C
j
<
l
n
(
k
)
(23)
r
n
-
1
(
1
)
+
W
τ
(
1
)
+
C
1
=
1133
+
4
+
2
=
1139
here, r
54
(
5
)
<
r
n
-
1
(
1
)
+
W
τ
(
1
)
+
C
1
<
l
54
(
5
)
W
τ
(
j
).
τ
1 will contribute initial job if, r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
≤
C
j, accordingly forr
n
-
1
(
1
)
+
W
τ
(
1
)
+
C
1
-
r
54
(
5
)
≤
C
1, the condition is not satisfied; therefore, it possesses only intermediate job.
τ
1 will contribute intermediate job if r
n
-
1
(
j
)
+
W
τ
(
j
)
+
C
j
-
r
n
(
k
)
>
C
j.
Here,(24)
r
n
-
1
(
1
)
+
W
τ
(
1
)
+
C
1
-
r
54
(
5
)
>
C
1
.
r
n
-
1
(
1
) + W
τ
(
1
) + C
1
-
r
54
(
5
) − C
1 = 3 > 0. Therefore, computation of a task τ
1 started in φ
k and having deadline in the problem area, will contribute an intermediate job.
By Lemma4, taskτ
1
∈
hp
⁡
(
k
) released [
r
54
(
5
)
,
l
54
(
5
)
] will contribute intermediate job, if
(25)
r
n
(
1
)
+
W
τ
(
1
)
+
C
1
<
l
54
(
5
)
l
54
(
5
) = 1151, r
n
(
1
) = 1144, release time is in the problem area.
r
n
(
1
) + W
τ
(
1
) + C
1
<
l
54
(
5
) is satisfied because r
n
(
1
) + W
τ
(
1
) + C
1 = 1150 and l
54
(
5
) = 1151. Therefore τ
1 does contribute one intermediate job in φ
1.
By Lemma4, if τ
1
∈
hp
(
5
)released [
r
54
(
k
)
,
l
54
(
k
)
] will contribute final job, if
(26)
r
n
(
1
)
+
W
τ
(
1
)
+
C
1
≥
l
54
(
5
)
.
r
n
(
1
) = 1144, release time is in the problem area; therefore, τ
1does not contribute final job in φ
1 because r
n
(
1
) + W
τ
(
1
) + C
1
<
l
54
(
5
).
Therefore, the final job = 0.
So, the total worst-case workload contribution ofτ
1 isw
(
1
) = 2(intermediate job) = 4.
Likewise, the other task contribution onϕ
(
1
) is found out similarly. One has
(27)
w
(
2
)
=
2
(
intermediate
job
)
+
1
(
final
job
)
=
3
,
w
(
3
)
=
2
(
initial
job
)
+
3
(
final
job
)
=
5
,
w
(
4
)
=
3
(
intermediate
job
)
=
3
,
w
(
6
)
=
0
,
W
•
(
5
)
=
Σ
w
(
initial
jobs
+
intermediate
jobs
+
final
jobs
)
,
hp
(
k
)
,
lp
(
k
)
W
•
(
5
)
=
4
+
3
+
5
+
3
=
15
.
W
•
(
5
)
<
φ
5; therefore, τ
54
(
5
) will be scheduled. Figure 13 shows the simulation result of τ
54
(
5
) in UML-RT.Figure 12
Problem areaφ
5, for nonpreemptive uniprocessor scheduling.Figure 13
Simulation result in UML-RT.


## 9. Conclusion

Two algorithms with a new priority assignment scheme (RMA-SJF) is proposed which possesses advantages of both rate monotonic and shortest job first, for a nonpreemptive periodic task set, on an uniprocessor architecture modelled using UML-RT. Further, a general schedulability test is derived using “problem window” analysis, to check for task schedulability. A sufficient schedulability condition to verify whether a periodic task is schedulable in any release time is also proposed. Task set generated is analyzed for the above schedulability test and condition with typical examples. The performances of the proposed algorithms are also analyzed with success ratio and effective processor utilization using UML-RT. In future aperiodic dependent nonpreemptive task with the proposed scheme on multiprocessor architecture modelled using UML-RT will be analyzed.



---

*Source: 705929-2014-02-13.xml*