Tidsfristen för en begäran är den tidpunkt då verkställigheten måste slutföras. Tidsfristen för begäran under en period av ett arbete med uppskjuten tidsfrist är en viss tid omedelbart efter periodens slut. Detta dokument beskriver en semistatisk, prioriterad algoritm för schemaläggning av periodiska jobb med uppskjutna tidsfrister: varje jobb tilldelas två prioriteringar, den högre för gamla förfrågningar och den lägre för den aktuella begäran. Denna algoritm kallas den modifierade hastighetsmonotoniska algoritmen och är baserad på den välkända hastighetsmonotoniska algoritmen. Vi visar att den modifierade hastighetsmonotoniska algoritmen är optimal när tidsfristen för varje jobb skjuts upp med max (1, γ - 1) perioder eller mer, där γ är förhållandet mellan den längsta perioden och den kortaste perioden. När deadline för varje jobb skjuts upp av en period av jobbet, kan varje uppsättning av n oberoende jobb vars totala utnyttjande är lika med eller mindre än [1 + n (2 1/n − 1)] / 2 möjligen schemaläggas av denna algoritm. Denna gräns närmar sig 0.845 när n närmar sig oändligheten.
En nyare förlängning av RM-algoritmen föreslås av Shih et al. REF för schemaläggning av ansökningar med uppskjutna tidsfrister.
Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines
{'venue': 'IEEE Trans. Software Eng.', 'journal': None, 'mag_field_of_study': ['Computer Science']}