Scheduling Algorithm for Multiprogramming in a Hard-Real-Time Environment

realtime system 쪽으로 분야를 바꿔서 읽어보는 첫 논문이다. 지금까지 내가 공부해왔던 분야와 사용하는 terminology나 문제해결을 위해 접근하는 방식이 좀 많이 다르다는 걸 느꼈다. 그래도 theorem을 증명하기 위해서 케이스를 나누고 증명하고 하면서 이산수학 공부할 때가 생각났다.

---

Introduction

• 보통 컴퓨터는 time-critical한 job과 non-time-critical한 job들을 동시에 수행
• 이들 사이를 잘 스케줄링하면 컴퓨터의 리소스를 효율적으로 사용할 수 있음
• 앞으로 진행될 담론에서 두가지 scheduling 특성을 고려할 예정 - priority driven and preemptive
  • fixed priority assignment는 up to 70% processor utilization 가능 - RM
  • dynamic priority assignment도 가능하며 fully utilization 가능 - EDF

Environments

• 모두가 필요하지는 않지만 몇가지 assumption을 두고 시작할 필요가 있음

  1. Hard deadline을 가진 task들은 모두 periodic하며, 이는 request 사이에 일정한 interval - period - 을 가진다는 의미이다.
  2. Deadline은 run-ability의 제한만을 가진다. (모든 task는 다음 request가 들어오기 전에 수행이 끝나야 한다.)
     • 개별 task의 queuing problem을 무시할 수 있게됨
  3. task들끼리는 서로 독립적이다. (특정 task의 실행/요청은 다른 task의 시작이나 수행과 관련이 없다.)
     • 이렇게 가정한다고 해서 특정 task $\tau_i$ 가 N times 실행된 후에 $\tau_j$가 같이 실행되어야 하는 경우까지 배제하는 것은 아님
  4. 특정 task의 run-time은 항상 동일하며, 여기에서의 run-time은 interruption없이 processor의 execution time을 측정한 것이다.
     • 한 task의 maximum processing time으로 해석할 수 있음 - 충분한 resource 예약할 수 있게끔 - kinds of upper bound?
     • 정확하진 않더라도 appproximation할 수 있게 해주며, task $\tau_i$를 (request period $T_i$, run-time $C_i$) 으로 characterization할 수 있게 해줌
     • request rate → request period의 역수
  5. 모든 nonperiodic task는 일반적이지 않은 특별한 경우(initialization이나 failure-recovery routines)로 상정한다. 이들은 평범하지 않은 경우니까 들어오게 되면 periodic task를 대체하며, hard critical deadline을 가지지 않는다.

• Scheduling algorithm → 특정 순간에 어떤 task를 실행할지를 결정하는 a set of rules

  • 본 페이퍼에서 다루는 scheduling algorithm들은 모두 preemptive and priority driven

• static if priorities are assigned to tasks once and for all. (=fixed)

• dynamic if priorities of tasks might change from request to request.

• mixed scheduling algorithm when some of the tasks are fixed yet the priorities of the remaining tasks vary from request to request

A Fixed Priority Scheduling Algorithm

✔️ Notations? Definitions?

• deadline for a task → the time of the next request for the same task
• time t에 t가 deadline인 task가 아직 완료되지 않았다면 overflow가 일어났다고 표현한다.
• 주어진 모든 task들이 overflow가 나지 않고 scheduling될 수 있다면 그 scheduling algorithm이 feasible하다고 표현한다.
  • 만약 critical instant에 할당된 모든 task들이 각각의 respective deadline안에 수행된다면? → scheduling algorithm is feasible
• response time → time span between the request and the end of response to that request
• critical instant → instant that request for certain task will have the largest response time
• critical time zone → time interval between a critical instant and the end of the response to the request.

Theorem 1. A critical instant for any task occurs whenever the task is requested simultaneously with requests for all higher priority tasks.

[ Proof ] $T_1 < T_2$인 두 task $\tau_1$ 과 $\tau_2$에 대해서

• $\tau_1$이 더 높은 priority를 가진다면 $\lfloor T_2/T_1 \rfloor C_1 + C_2 \le T_2$ 가 반드시 성립해야 한다. - (1)
• $\tau_1$이 더 낮은 priority를 가진다면 $C_1 + C_2 \le T_1$이 반드시 성립해야 한다. - (2)
• (2)를 만족하면 (1)도 만족하게 되므로 period의 역수에 따라 priority를 부여하는 것이 가장 reasonable한 방법임

Theorem 2. If a feasible priority assignment exists for some task set, the rate-monotonic priority assignment is feasible for that task set.

Achievable Processor Utilizations

• utilization factor → 1 - the fraction of idle processor time
• $C_i/T_i$ is fraction of processor time spent for task $\tau_i$
  • for $m$ tasks, utilization factor : $U = \sum_{i=1}^{m} (C_i/T_i)$
• 물론 $C_i$를 늘리거나 $T_i$를 줄이면 utilization을 높일 수 있겠으나, 모든 critical instant의 task들이 deadline안에 수행되어야하는 constraint는 여전함
• fixed priority algorithm에서, utilization factor의 least upper bound는 processor을 fully utilize하는 task들의 가장 작은 값에 바운드 됨
  • 위의 식에서 $U_{least\ upper\ bound} = \min(C_i/T_i)\ for\ [1, m]$ ?
• RM assignment는 optimum이기 때문에, 이로 인해 얻은 utilization factor는 다른 방식으로 얻은 utilization factor보다 같거나 크다. → upper bound

Theorem 3. For a set of two tasks with fixed priority assignment, the least upper bound to the processor utilization factor is $U=2(2^{\frac12}-1)$

Theorem 4. For a set of $m$ tasks with fixed priority order, and the restriction that the ratio between any two request periods is less than 2, the least upper bound to the processor utilization factor is $U=2(2^{\frac1m}-1)$

Theorem 5. For a set of $m$ tasks with fixed priority order, the least upper bound to the processor utilization factor is $U=2(2^{\frac1m}-1)$

Relaxing the Utilization Bound

• 앞서 구했던 bound에서는 실제로 switching하는 데에 드는 cost는 고려되지 않음
• utilization bound를 1로 만드는 가장 쉬운 방법은 $\{T_m/T_i\}=0\ for\ i=1,2,3,\ldots,m-1$ 이나 불가능함
  • 여기에서 $\{T_m/T_i\}$은 $T_m/T_i$의 fractional part를 의미
• 대신 낮은 priority의 buffer task $\tau_m$ 을 만드는거? switching하는 것을 또 다른 task로 간주하는건가?

The Deadline Driven Scheduling Algorithm

• deadline driven scheduling algorithm → priorities are assigned to tasks according to their deadline of current task
• 가장 deadline이 가깝고 아직 완료되지 않은 task부터 처리

Theorem 6. When the deadline driven scheduling algorithm is used to schedule a set of tasks on a processor, there is no processor idle time prior to an overflow.

Theorem 7. For a given set of $m$ tasks, the deadline driven scheduling algorithm is feasible iff $(C_1/T_1)\ +\ (C_2/T_2)\ +\ \ldots\ +\ (C_m/T_m)\ \le\ 1$

• optimum algorithm → if a set of tasks can be scheduled by any algorithm, it can be scheduled by the deadline driven scheduling algorithm

A Mixed Scheduling Algorithm

• RM algorithm과 EDF를 결합한 방식의 알고리즘도 있음
• availability function of a processor → accumulated processor time for $0$ to $t$ available to this set of tasks

Theorem 8. If a set of tasks are scheduled by the deadline driven scheduling algorithm on a processor whose availability function is sublinear, then there is no processor idle period to an overflow.

---

사실 아직 모든 증명의 과정을 다 이해한건 아니지만 .. 다 이해하고 올리면 언제 올릴지 보장할 수 없기 때문에 일단 올려두고 이해가 더해지만 내용을 추가하려고 한다..