YDS-algoritm

YDS är en schemaläggningsalgoritm för dynamiska hastighetsskalningsprocessorer som minimerar den totala energiförbrukningen. Den är uppkallad efter och utvecklad av Yao et al. Det finns både en online- och en offlineversion av algoritmen.

Offline-algoritm

Definitioner:

• Det finns en uppsättning av n jobb $J:=J_{1},...,J_{n}$ , där varje jobb $J_{i}$ har en releasetid $r_{i}$ , deadline $d_{i}$ och en bearbetningsvolym $w_{i}$ .
• $I$ är ett visst tidsintervall.
• Vi har också $\Delta _{I}={\frac {1}{|I|}}\summa _{J_{i}\in S_{I}}w_{i}$ , arbetsdensiteten i $I$ .
• Och slutligen är $S_{I}\in J$ uppsättningen av jobb som måste bearbetas i $I$ , det betyder jobb med $[r_{i},d_{i}]\in I$ .

Algoritmen fungerar då enligt följande:

 Medan $J\neq \{\}$ Bestäm tidsintervallet $I$ för maximal densitet $\Delta _{I}$ . I  $I$ bearbetar jobben för $S_{I}$ med hastighet $\Delta _{I}$ enligt  EDF  Set $J :=J\setminus S_{I}$ . Ta bort  $I$ från tidshorisonten och uppdatera releasetiderna och deadlines för oplanerade jobb därefter. avsluta medan  

Med andra ord är det en rekursiv algoritm som kommer att följa dessa steg tills alla jobb är schemalagda:

1. Beräkna alla intensiteter för alla möjliga kombinationer av intervall. Detta innebär att arbetsintensiteten beräknas för varje kombination av starttid och sluttid. För detta läggs tiderna för alla jobb vars ankomsttid och deadline ligger inom intervallet och divideras med intervalllängden. För att påskynda processen behöver endast kombinationer av ankomsttider och senare deadlines beaktas, eftersom tider utan ankomst av en process eller deadline kan krympas till ett mindre intervall med samma processer, vilket ökar intensiteten, och negativa intervall är ogiltiga. Därefter väljs det maximala intensitetsintervallet. I fallet med flera lika intensiva intervall kan ett väljas efter behag, eftersom intensiteter av icke-överlappande intervall inte påverkar varandra, och att ta bort en del av ett intervall kommer inte att ändra intensiteten på resten, eftersom processer tas bort proportionellt.
2. Processerna inom det här intervallet är schemalagda med hjälp av Earliest Deadline First, vilket innebär att jobbet inom detta intervall vars deadline kommer snarast schemaläggs först, och så vidare. Jobben utförs med ovan beräknade intensitet för att passa alla jobb inom intervallet.
3. Intervallet tas bort från tidslinjen, eftersom inga fler beräkningar kan schemaläggas här. För att förenkla ytterligare beräkningar räknas alla ankomsttider och deadlines för kvarvarande jobb om för att utelämna redan upptagna tider. Antag till exempel ett jobb $A$ med ankomsttid ${\displaystyle a_{A}=0} ,$ deadline $d_{A}=10$ och en arbetsbelastning $w_{A}=5$ och ett jobb $B$ med $a_{B}=5$ , $d_{B}=10$ och $w_{B}=4$ . Antag att föregående intervall var från tid $3$ till $8$ . För att utelämna detta intervall måste tiderna för $A$ och ${\displaystyle B} justeras;$ arbetsbelastningar är opåverkade, eftersom inget arbete har utförts för varken $A$ eller $B$ . $a_{A}$ förblir densamma, eftersom den inte påverkas av senare utelämnanden. $d_{A}$ måste dock ändras till $5$ , eftersom $10-(8-3)=5$ . Detta är den tid som jobb $A$ har kvar innan dess deadline. Ankomsttiden $a_{B}$ blir $3$ , som den skulle ha varit inom det borttagna intervallet. $d_{B}$ blir också $5$ , eftersom tiden kvar efter det borttagna intervallet är $2$ . Det är dock viktigt att komma ihåg de faktiska ankomst- och deadlinetiderna för senare sammansättning av schemat.
4. Upprepa steg 1-3 tills alla jobb har schemalagts.
5. Montera jobb till slutlig schemaläggning enligt deras tilldelade tidsintervall. Kom dock ihåg att ett intervall kan delas i två av ett annat intervall som beräknats tidigare.

För alla Job-instanser beräknar algoritmen ett optimalt schema som minimerar den totala energiförbrukningen.

Se även

• Tidigaste deadline första schemaläggning