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

haejoo·2021년 3월 11일
1

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 τi\tau_iN times 실행된 후에 τj\tau_j가 같이 실행되어야 하는 경우까지 배제하는 것은 아님
    4. 특정 task의 run-time은 항상 동일하며, 여기에서의 run-time은 interruption없이 processor의 execution time을 측정한 것이다.
      • 한 task의 maximum processing time으로 해석할 수 있음 - 충분한 resource 예약할 수 있게끔 - kinds of upper bound?
      • 정확하진 않더라도 appproximation할 수 있게 해주며, task τi\tau_i(request period TiT_i, run-time CiC_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 ] T1<T2T_1 < T_2인 두 task τ1\tau_1τ2\tau_2에 대해서

  • τ1\tau_1이 더 높은 priority를 가진다면 T2/T1C1+C2T2\lfloor T_2/T_1 \rfloor C_1 + C_2 \le T_2 가 반드시 성립해야 한다. - (1)
  • τ1\tau_1이 더 낮은 priority를 가진다면 C1+C2T1C_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
  • Ci/TiC_i/T_i is fraction of processor time spent for task τi\tau_i
    • for mm tasks, utilization factor : U=i=1m(Ci/Ti)U = \sum_{i=1}^{m} (C_i/T_i)
  • 물론 CiC_i를 늘리거나 TiT_i를 줄이면 utilization을 높일 수 있겠으나, 모든 critical instant의 task들이 deadline안에 수행되어야하는 constraint는 여전함
  • fixed priority algorithm에서, utilization factor의 least upper bound는 processor을 fully utilize하는 task들의 가장 작은 값에 바운드 됨
    • 위의 식에서 Uleast upper bound=min(Ci/Ti) for [1,m]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(2121)U=2(2^{\frac12}-1)

Theorem 4. For a set of mm 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(21m1)U=2(2^{\frac1m}-1)

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

Relaxing the Utilization Bound

  • 앞서 구했던 bound에서는 실제로 switching하는 데에 드는 cost는 고려되지 않음
  • utilization bound를 1로 만드는 가장 쉬운 방법은 {Tm/Ti}=0 for i=1,2,3,,m1\{T_m/T_i\}=0\ for\ i=1,2,3,\ldots,m-1 이나 불가능함
    • 여기에서 {Tm/Ti}\{T_m/T_i\}Tm/TiT_m/T_i의 fractional part를 의미
  • 대신 낮은 priority의 buffer task τm\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 mm tasks, the deadline driven scheduling algorithm is feasible iff (C1/T1) + (C2/T2) +  + (Cm/Tm)  1(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 00 to tt 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.


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

profile
대학원생 전해주의 우당탕탕 공부일상

0개의 댓글