YDS 알고리즘

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2013년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

YDS는 총 에너지 소비량을 최소화하는 동적 속도 스케일링 프로세서의 스케줄링 알고리즘이다.그것은 야오 외 에 의해 이름을 따서 지어졌고 개발되었다.^[1]알고리즘에는 온라인 버전과 오프라인 버전이 있다.

오프라인 알고리즘

정의:

• There is a set of n Jobs ${\displaystyle J:=J_{1},...,J_{n}}$, where each job ${\displaystyle J_{i}}$ has a release time ${\displaystyle r_{i}}$, deadline ${\displaystyle d_{i}}$ and a processing volume ${\displaystyle w_{i}}$.
• ${\displaystyle I}$ ${\displaystyle I}$은(는) 특정 시간 간격이다.
• 또한 $\Delta {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle I_{}}$= ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{I}{}}$ ${\displaystyle \frac{\sum }{}\underset{}{}}$ ${\displaystyle \underset{}{J{}_{}}}$ ${\displaystyle \underset{}{I_{}}}$ ${\displaystyle \underset{}{{}_{}}}$ ${\displaystyle \underset{}{{}_{}}}$ ${\displaystyle \underset{}{I_{}}}$ ${\displaystyle w_{}}$ I ${\$$I}={\frac{1}{{{}}\sum _{J_{i}\in$ S_${I}w_{i}}}},$ $I{\displaystyle }$ ${\displaystyle I}$의 작업 밀도$.$
• 그리고 $마지막$으로 S ${\displaystyle I_{}j}$ J$${\$displaystyle S_{I}\in$ J$}$은(는) $I{\displaystyle }$ ${\displaystyle I}$에서 처리되어야 하는 Jobs 집합이며$,$ 이는 [ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle d_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \in }$ I ${\displaystyle [r_{i},d_{i}]\in}$인 Jobs를 의미한다$.$

알고리즘은 다음과 같이 작동한다.

While ${\displaystyle J\neq \{\}}$   Determine the time interval ${\displaystyle I}$ of maximum density ${\displaystyle \Delta _{I}}$.   In ${\displaystyle I}$ process the jobs of ${\displaystyle S_{I}}$ at speed ${\displaystyle \Delta _{I}}$ according to EDF   Set ${\displaystyle J:=J\setminus }$${\displaystyle S_{}}$ ${\displaystyle I_{}}$ ${\$ $시간{\displaystyle }$ 지평선에서$$ I ${\displaystyle I}$을(를) 제거하고 그에 따라 예정되지 않은 작업의 릴리스 시간과 마감일을 업데이트하십시오.그 동안에 끝나다

다른 말로 하면 모든 작업이 예약될 때까지 다음 단계를 따르는 재귀 알고리즘이다.

1. 가능한 모든 구간 조합에 대한 모든 강도를 계산한다.이는 모든 시작 시간과 종료 시간 조합에 대해 작업 강도가 계산된다는 것을 의미한다.이를 위해 도착 시간과 마감일이 간격 내에 있는 모든 작업의 시간을 구간 길이로 추가하고 나눈다.공정이나 마감일이 도착하지 않은 시간은 동일한 공정으로 더 작은 구간으로 축소할 수 있으므로 공정 속도를 높이기 위해 도착 시간과 이후의 마감 시간의 조합만 고려할 필요가 있다. 따라서 강도가 증가하고 음의 간격은 무효가 된다.그런 다음 최대 강도 간격을 선택한다.균등하게 강도 높은 구간이 여러 개일 경우, 겹치지 않는 구간 강도는 서로 영향을 미치지 않기 때문에 임의로 선택할 수 있으며, 구간 중 일부를 제거해도 공정이 비례적으로 제거되므로 나머지 구간 강도는 변경되지 않는다.
2. 이 간격 내의 프로세스는 가장 빠른 마감일 우선을 사용하여 스케줄링되며, 마감일이 가장 빨리 도착할 이 간격 내의 작업이 먼저 스케줄링되는 등의 작업을 의미한다.해당 간격 내의 모든 작업에 적합하도록 위에서 계산된 강도로 작업이 실행된다.
3. 여기서 더 이상 계산을 예약할 수 없으므로 간격은 타임라인에서 제거된다.추가 계산을 단순화하기 위해 남은 작업의 모든 도착 시간과 마감일을 다시 계산하여 이미 점유된 시간을 생략한다.예를 들어, 도착 ${\displaystyle {시간}_{}}$이${\displaystyle {}_{}}$A = ${\displaystyle \mathrm{0인<img\; alt="A"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3"\; style="vertical-align:\; -0.338ex;\; width:1.743ex;\; height:2.176ex;"\; papago-attr-id="83">}}$ $작업{\displaystyle }$ A ${\$$displaystyle A$$}$을(를) 가정하십시오$.$$A}=0$ 마감 $d{\displaystyle {}_{}}$= ${\displaystyle 10}$ ${\displaystyle d_{$${\displaystyle \mathrm{A}}$$}=10}$ 및$$ ${\displaystyle {워크로드}_{}}$ w${\displaystyle {}_{}}$= 5 ${\displaystyle w_{$$A}=5}$, and a job ${\displaystyle B}$ with ${\displaystyle a_{B}=5}$, ${\displaystyle d_{B}=10}$ and ${\displaystyle w_{B}=4}$. Assume the previous interval was from time ${\displaystyle 3}$ to ${\displaystyle 8}$. To omit this interval the times of ${\displaysty$$Le{\displaystyle }$ A}$및$ $B$ ${\displaystyle$ B}을$($를) 조정해야 하며$$, A$$ ${\displaystyle$ A}$또는$ B ${\displaystyle$ B}에$$대한 작업이 수행되지 않았기 때문에 워크로드는 영향을 받지 않는다.$$${\displaystyle A_{}}$ ${\$$A}}$은(는) 이후의 누락에 영향을 받지 않기 때문에 그대로 유지된다$$.${\displaystyle d_{}}$ A ${\$ 스타일 $d_{$$그러나$ A$}$은$($는) ${\displaystyle 10}$-${\displaystyle }$( ${\displaystyle 8}$- 3${\displaystyle }$)${\displaystyle }$= ${\displaystyle 5}$ ${\디스플레이$ 스타일 $10-(8-3)=5}$으로 5 ${\디스플레이$ 스타일 5$}$로 변경해야 한다$.$ $A{\displaystyle }$ ${\디스플레이$ 스타일 $A}$이(가) 마감일 전에 떠난$$ 시간이다.${\displaystyle {도착}_{}}$ 시간 $B{\displaystyle {}_{}}$ ${\$는 제거된 간격 내에 있었을 $때처럼$3 ${\displaystyle 3}$이 된다. ${\displaystyle d_{}}$ ${\$ 또한$$ 제거된 간격 뒤에 남은 시간이 $2{\displaystyle \mathrm{}}$ ${\displaystyle 2}$이므로$$$5{\displaystyle \mathrm{}}$ ${\displaystystyle 5}$이 된다$.$ 그러나 실제의 실제를 기억하는 것이 중요하다.스케줄링의 이후 조립을 위한 경쟁 및 마감 시간.
4. 모든 작업이 예약될 때까지 1-3단계를 반복하십시오.
5. 할당된 시간 간격에 따라 작업을 최종 스케줄링으로 결합하십시오.그러나 한 구간이 이전에 계산된 다른 구간으로 둘로 분할될 수 있다는 점을 기억하십시오.

잡의 경우 알고리즘은 총 에너지 소비량을 최소화하는 최적의 일정을 계산한다.^[2]

참고 항목

• EDF 알고리즘

참조