Scheduling of Individual Jobs

개별적인 job들이 스케줄링의 대상이 될 수도 있고, 

이러한 개별적인 job들이 반복되는 task들이 스케줄링의 대상이 될 수도 있다.

 

이번에는 개별적인 job들에 대한 스케줄링에 대해 다뤄볼것이다.

 

스케줄링은 다양한 조건에 따라 사용할 알고리즘이 달라진다.

일단 베이직한 조건에서부터 시작해보자.

 

기본 조건 :

- 싱글프로세서를 사용하며, {J1, , , Jm}까지의 잡을 스케줄링 한다.

- 또한 각각의 잡 Ji는 ri의 release time을 가지며 ei의 execution time, di의 absolute deadline을 가진다 하자.

- Hard real - time constraints를 가진다고 가정할 것이다.

 

위 조건에 대한 optimal한 알고리즘이 있느냐는 것을 확인해 보자.

 

아래의 순서대로 점점 일반화 해가면서 진행해보겠다.

1. 리소스 X, independent, synchronized(모든 job에 대하여 ri = 0일 때. 즉 모두 동시에 릴리즈 될 때)

2. 리소스 X, independent, but not synchronized

3. 리소스 X, but dependent

4. 일반적인 모든 케이스

 

---

No resources, Independent, Synchronized

표와 같은 ei와 di를 같는 잡들을 주어진 조건에 맞게 스케줄링 해야한다.

 

Theorem - 리소스에 대한 고려가 없다면, 데드라인의 오름차순 정렬순으로 독립적인 잡들을 실행하면 언제나 feasible한 스케줄이 된다. (EDD 알고리즘)

 

증명 :

s를 스케줄이라 두자. Ja가 Jb보다 먼저 실행되지만, db < da인 잡의 쌍 (Ja, Jb)이 inversion이다.

만약 s가 이 inversion을 포함하지 않고 있다면, 그건 EDD일 것이다.

 

k(k>0)개의 inversion이 s에 있다 가정하자.

(Ja, Jb)를 Ja가 Jb 바로 직전에 스케줄된 Inversion이라고 두고,

ta < tb 를 Ja와 Jb가 실행을 시작할 때의 시간이라 두자.

이때 Ca <= da이며 Cb <= db < da임을 기억해두자.

 

다음과 같은 조건으로 새로운 스케줄 s'를 정의하자.

1) Ja와 Jb를 제외한 모든 잡들은 s에서와 똑같이 스케줄 되어있다.

2) ta에 Jb를 시작한다.

3) ta + eb에 Ja를 시작한다.

 

이렇게 스케줄링한다면,

Jb가 완료되는 시간은 : ta + eb이고,

ta + eb < ta + eb + ea = tb + eb = Cb <= db

이므로 Jb는 데드라인을 맞출 수 있다.

Ja가 완료되는 시간은 : ta + eb + ea이고,

ta + eb + ea = Cb <= db < da

이므로 Ja도 데드라인을 맞출 수 있다.

 

s'가 k-1개의 inversion을 갖고 있다면, 위의 절차를 k번 반복하므로써 EDD 스케줄을 얻을 수 있다.

 

번역 실력이 부족해서, 한글로 서술했을 때 모호하게 느껴지는 사람도 있을것 같아 원문도 준비했다.

---

No resources, Independent (No Synchro)

방금 살펴본 조건에서 Synchro의 조건만 바뀌었다.

잡들의 release time이 서로 다른 경우인 것이다.

 

이러한 경우 사용할 수 있는 알고리즘으로, 

Earliest Deadline First 알고리즘이 있다. (EDF)

가장 빠른 absolute deadline을 가진 잡들을 먼저 실행하는 것이다.

이 알고리즘의 경우 synchro가 아닌 상황에서는, preemtion의 여부를 고려해야한다.

아래의 예시를 보자.

위와 같은 경우, preemtion이 허용 된다면 J1을 1초 실행한 뒤 J2가 1초에 release 되면 J2를 2초 실행하고 다시 J1으로 넘어와 3초를 마저 실행할 수 있다. 하지만 preemption이 혀용되지 않는다면, J1을 실행한 뒤 중간에 끊을 수 가 없어서, J2의 데드라인을 맞추지 못하게 된다. 따라서, EDF는 preemption이 허용될 때 사용할 수 있는 알고리즘이다.

 

 

Theorem - 리소스에 대한 고려가 없고, 독립적인 잡들에 preemption이 허용된다면, EDF 알고리즘은 피저블한 스케줄을 찾는다.

 

증명 : 

feasible 하지만 EDF는 아닌 스케줄 s가 있다고 가정하자.

또 최대 한 개의 잡이 [k, k+1) interval 사이에 실행된다 가정하자. (k는 자연수)

 

만약 다음 조건 중 하나라도 해당된다면, 스케줄 s는 EDF가 아닌 것이다.

1. [k, k+1) 사이에 실행 가능한 잡이 있지만, 이 기간동안 아무 잡도 실행되지 않는다.

2. 두 개의 잡 Ja와 Jb에 대해, 다음 조건을 만족한다.

 - Ja와 Jb는 k에 실행 가능 상태가 된다.

 - Ja는 [k, k+1)에 실행된다.

 - db < da이다.

 

k를 스케줄 s가 EDF에 위반하게 되는 가장 작은 값으로 설정하자.

Jb을 k에 실행 가능 상태가 되는 모든 잡들 중 가장 deadline이 작은 잡이라 가정하자.

 

1번 조건에 대해서 :

  기존 s와 똑같지만, Jb를 [k, k+1)에서 실행하는 새로운 스케줄 s'를 정의한다.

2번 조건에 대해서 : 

  Jb가 s에서 [l, l+1)에 실행된다 할 때, k < l < db이 l의 범위일 것이다.

  기존 s와 똑같지만, Jb를 [k,k+1)에 실행하고, Ja를 [l, l+1)에 실행하는 새로운 스케줄 s'를 정의한다.

 

s' 스케줄은 위 두 조건(EDF가 아니게 되는 조건)에 해당사항이 없으므로, (k보다 작은 time instant에 대해서)

어떠한 feasible한 스케줄이든 위의 과정을 거치면 EDF로 변환할 수 있다.

 

 

-Preemption이 허용되지 않을 때

non - preemptive 캐이스는 NP-hard문제이다.

Heuristic이 필요하다. (휴리스틱이란 직관적으로 접근하기, 혹은 어림잡아 접근하기를 의미한다.)

잡들의 subset들을 스케줄해나가는 방식의 부분 스케줄링 개념을 사용한다.

매 단계마다,

-> 아직 partial schedule에서 시도하지 않은 잡들 중 H(휴리스틱 펑션)을 극대화 하는 잡을 추가한다.

-> 그런 잡이 없으면 백트래킹 한다.

실패한다면, 이전의 partial schedule로 백트래킹 한다.

 

---

No resources, Dependent (No Synchro)

 

이제는 각각의 독립적인 잡들이 아닌 경우에 대한 스케줄링이다.

서로에 대해 Dependent 하다는 것은, 위 그림과 같은 경우 J1이 실행 된 후에야 나머지 잡이 실행 될 수 있다는 것을 뜻한다.

즉 위와 같이 트리 구조로 표현하였을 때, 부모 노드가 실행되지 않으면 자식 노드를 실행할 수 없다.

 

Theorem - 리소스에 대한 고려가 없고, 잡들이 preemptable이라 가정한다면,

실행 가능한 일정이 존재하는지 여부를 결정한뒤, 있다면 그 스케줄을 계산하는 Polynomial time의 알고리즘이 존재한다.

 

아이디어 : 비독립적인 잡들에 대하여, release time과 deadline을 다시 적용하여 독립적인 잡으로 만든 후, EDF를 실행한다. 서로 의존 관계에 있는 잡들을 독립적인 잡으로 바꿀 수 있다면, EDF를 사용할 수 있다.

 

Ji가 Jk보다 먼저 실행되어야 하는 경우를 생각해보자.rk -> max{rk, ri + ei}  로 바꾼다. (Ji가 ri + ei 이전에는 실행완료가 될 수 없기 때문에, Jk도 그 이전에는 실행될 수 없다)di -> min(di, dk - ek}   로 바꾼다. (Ji가 dk - ek 이전에 실행완료 되어 주어야 Jk가 그 데드라인을 맞출 수 있다)

 

위의 내용을 일반화 하면 아래와 같이 정리할 수 있다.

위의 정리를 이용하여 모든 잡들에 대하여 r*과 d*을 새롭게 정의하여 J*들의 잡을 정의하였다면, 이 J*의 feasiblity를 그대로 J에 적용할 수 있다.