# Schedulability tests based on utilization

## RM Scheduling

Schedulability tests for RM based on task utilization.

* Valid with preemption, **n independent tasks**, D=T.
* Liu\&Layland’s (1973), **Least Upper Bound (LUB)**.
  * ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FjxdlNUZlAL8xCpBaFJMv%2Fa.png?alt=media\&token=e073ce80-28b1-4011-9a2b-790b81cb5fbb) => One execution per period guaranteed.
* Bini\&Buttazzo\&Buttazzo’s (2001), **Hyperbolic Bound**.
  * ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FvCiFu6vlMkaAJIWiSWs3%2Fa.png?alt=media\&token=f6b26eea-1ca9-4daa-b2bf-c144496c53b6) => One execution per period guaranteed.

### Interpretation of the Liu\&Layland test

![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2F4OK7jJNqg7Z2fbszG125%2Fa.png?alt=media\&token=72757466-fa0e-43c0-b563-61b70d1bea71) => task set not schedulable (overload) – **necessary condition**.

![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FAPqWq1vyZmfiLRw5ngKs%2Fa.png?alt=media\&token=a012e593-c47d-4520-9577-76ae81e98cc9) => task set is schedulable – **sufficient condition**.

![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FQSTB1vs18dOvhk9ZigDl%2Fa.png?alt=media\&token=b9db4b4a-e460-4b66-a232-c0e79d759679) => the test is **indeterminate**.

#### Some values

<figure><img src="https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2F8IRd5Unbq0U256dEBO63%2Fa.png?alt=media&#x26;token=0ceb0d57-6401-45bc-9713-ead5d7e11699" alt=""><figcaption></figcaption></figure>

### Example 1

Task properties.

<figure><img src="https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2F293QUzsOiY0yLDG1Sqvs%2Fa.png?alt=media&#x26;token=4164f3a0-133c-4042-b9d6-6dcbbd9da6a9" alt=""><figcaption></figcaption></figure>

* ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FHRMv7cwK2vf4E6YEy1qy%2Fa.png?alt=media\&token=e71f625c-a0fe-4773-a218-b12b29647dd1)
* ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FMjHOBT9VL9IuMR0d2Ah4%2Fa.png?alt=media\&token=9abe3e8c-057b-44fb-bc69-9dff02fc7f67) one execution per period is guaranteed.

### Example 2

Task properties.

<figure><img src="https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FNv67AcbaZz3Evfu4EDXT%2Fa.png?alt=media&#x26;token=651d83cc-2468-495d-815b-3f927fc162e1" alt=""><figcaption></figcaption></figure>

* ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FKwIbVkQAzKfgeD4aKoEc%2Fa.png?alt=media\&token=509f4ffe-e0e3-400b-a6c9-4684d3832200)
* ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FP9OuXOqqb8LVaRVB50hx%2Fa.png?alt=media\&token=69130274-d9a3-4619-a8c0-7594c2619942) one execution per period is **NOT guaranteed**.
* But the task set is schedulable (see Gantt chart).

### Example 3

Task set properties.

<figure><img src="https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FkuZnfeohlllPOZQU3Ujb%2Fa.png?alt=media&#x26;token=f53748ee-0b48-4b4a-a0ce-66dea10db8a8" alt=""><figcaption></figcaption></figure>

* ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FDVh4kEXksc0ieVwzmIx2%2Fa.png?alt=media\&token=8ef3a909-49ac-4862-a585-11b9f3a919b5)
* ![](https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FeKAcEupXKyPJHJ7Yhh0o%2Fa.png?alt=media\&token=ec9b0879-463e-49e1-b4c2-3a7cecb6a155) one execution per period is **NOT guaranteed**.
* And the task set indeed is **not schedulable** (see Gantt chart).

## Harmonic Periods

Particular case: if the task **periods are harmonic** then the task set is schedulable iif _U(n) ≤ 1_.

* E.g. _Γ = {(1, 2); (2, 4)}_

<figure><img src="https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FuNVmNsnxsBzh5A4baPh7%2Fa.png?alt=media&#x26;token=4e1905e3-755c-42a3-ae95-842ab0cddc17" alt=""><figcaption></figcaption></figure>
