aikataulullisuus

Aikataulullisuus (schedulability) on käsite, jota käytetään erityisesti reaaliaikaisessa laskennassa sekä tuotanto- ja suunnittelujärjestelmissä. Se kuvaa, voidaanko annetun aikatauluttajan alaisuudessa varmistaa, että kaikki tehtävät valmistuvat määräaikoihinsa. Käytännössä aikataulullisuus tarkoittaa, että tehtävien suoritus voidaan ajoittaa siten, ettei mikään deadline ylity.

Reaaliaikaisissa järjestelmissä tehtävät määritellään usein periodisina, joille annetaan suoritusaika Ci, jakso Ti ja mahdollinen viimeinen määräaika Di (yleensä Di = Ti). Aikatauluttaja pyrkii varmistamaan, että jokainen tehtävä alkaa ja päättyy ennen Di:tä.

Yleisiä aikataulutustestejä ovat Liu ja Laylandin raja-arvo RMS:llä sekä vasteaikaanalyysi. RMS:llä riittävä ehto on ∑ Ui ≤ n(2^(1/n) - 1), missä Ui = Ci/Ti. Tarkempi testaus voidaan tehdä vasteaikaanalyysillä Ri = Ci + sum_{j≠i} ceil(Ri/Tj) * Cj; jos Ri ≤ Di, tehtävä i on aikataulutettavissa. EDF:lla uniprosessorilla aikataulutettavuus on optimaalinen; jos Di = Ti, kokonaistuotto ∑ Ci/Ti ≤ 1 riittää. Moniprosessorijärjestelmissä aikatauluttaminen on yleisesti NP-vaikeaa ja vaatii heuristiikkaa tai conservatiivisia ehtoja.

Käytännön huomioita ovat mahdollinen viive, blokkaus sekä tehtävien riippuvuudet ja itse-suspensaatiot. Aikataulullisuus on keskeinen käsite RTOS-ien suunnittelussa sekä tuotannollisessa aikataulutuksessa.