Sufficient Schedulability Condition And Acceptance Test
Sufficient Schedulability Condition and Acceptance Test
Again, the OS scheduler subjects the application to an acceptance test whenever an application Tk requests to execute in the real-time mode. The required capacity of the application is sk ,and in the open system, it is scheduled by its server scheduler according to algorithm Σk . Deng, et al. [DLZS] showed that the following conditions together constitute a sufficient condition for the application Tk to be schedulable when executed in the open system according to algorithm Σk .
1. The size ˜ uk of the server Sk used to execute Tk is equal to sk, if Tk is predictable, or 
if Tk is unpredictable, where δk,min is the shortest relative deadline of all threads in Tk whose release times or resource acquisition times are unknown.
2. The total size of all servers in the open system is no more than 
where the max function is over all real-time applications Tj ’s in the system, Bj is the maximum execution time of nonpreemptable sections of all applications other than Tj , and Dmin, j is the shortest relative deadline of all threads in Tj .
3. In the interval (t, d − q) from any budget replenishment time t of Sk to q time units before the corresponding server deadline d, where q ≥ 0 and d − q > t , there would be no context switch among the threads in Tk if Tk were to execute alone on a slow processor of speed sk .
(c) Acceptance test and choice of server size summarizes the acceptance test that the OS scheduler subjects each application to and the choice of server size that the scheduler makes when admitting a new real-time application. The rationale behind them are conditions 1 and 2 stated above: The OS scheduler makes sure that these conditions are met. Similarly, the replenishment rules in (b) Server maintenance rules are such that condition 3 is satisfied for all types of real-time applications.
(c) Acceptance test and choice of server size
Information provided by requesting application T:
• required capacity s and scheduling algorithm Σ;
• maximum execution time B of all nonpreemptable sections;
• existence of aperiodic/sporadic tasks, if any;
• the shortest relative deadline δ of all threads with release-time jitters;
• the shortest relative deadline Dmin if the application is priority driven or the shortest length of time between consecutive timer events if the application is time driven.
Information maintained by the OS scheduler:
• the total size Ut of all servers in the system, and
• the above parameters provided by existing real-time application.
Step 1: Choose the size u of the server for the new application as follows:
• u = s if T is predictable, or
• u = sδ/(δ − q) if T is unpredictable.
Step 2: Acceptance test and admission:
• If Ut u maxall j (Bj /Dmin, j) > 1, reject T;
• Else, admit T:
– increase Ut by u,
– create a server S of the chosen size for T, and
– set budget and deadline of S to 0.