写本文前严重声明, 这些论文是以前写论文准备的,好象已经是一年前看的了, 在下肯定有错误之处,希望大家见谅.
今天来讨论一下real-time scheduling中的比较基础的一篇论文, 可以说从这篇论文后, sche才有了真正的研究方向, 并且是严格基于数学验证的. 熟悉论文系统的兄弟姐妹现在估计已经知道要说的Rate-Monotonic和EDF算法, 论文是
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
C. L. Liu
Project MAC, MIT
James W. Layland
Jet Propulsion Laboratory, CIT
由于我的中文输入速度太慢了, 下面基本改用英文了. 必要的时候用中文, 下面内容有摘抄,论文原文和自己的解释. 另外论文中很多地方涉及到充分必要条件, 我没有指出,因为早就忘了.
Part 1 Intro.
This paper is the origin of the rate-monotonic (RM) priority assignment theory, which
is the most discussed and developed theory for scheduling single processor systems as
of today. The paper gives proof for RM priority assignment to be the optimal assignment
of priorities for a specific task-set.
It also includes a sufficient condition for such a task set to be schedulable with RM assignment.
A second part of the paper discusses another scheduling algorithm: The deadline-driven scheduling algorithm (or Earliest Deadline First - EDF), which is based on dynamic assignment of priorities (i.e. online
assignment) according to the task deadlines. This method is also proven to be optimal
among dynamic priority schedulers. EDF is shown to have a very simple utilization based necessary and sufficient condition.
Part 2 Definition
Real time Systems
• Guaranteed execution of tasks
• Required to complete tasks in a timely manner
• Examples – digital control, real-time command and control, signal processing
• Often run “under the covers”
Part 3 Hard and Soft
Hard real-time
– Guaranteed response time
– Aircraft safety controls
– Missile systems
Need to work correctly and responsively
• More Important – Need to be able to demonstrate the timeliness of the system using validation techniques
• Need proof that the time constraints are met
Soft real-time
– Execution may not be guaranteed
– Statistical distribution of response time acceptable
– Online transaction systems, telephone switches,electronic games
Part 4 Terminology
• Deadline
– Time at which task should complete execution
• Overflow
– Unfulfilled request
• Response time
– Time to fulfill the request. ( elapsed time )
• Run Time
– time taken without interruption
– vs Response time
• Critical Instant
– Instant at which request will have the largest response time
• Critical time zone
– Time interval between a critical instant and the deadline for the task
• Feasible priority assignment
– All tasks are able to run to completion before their deadlines
• Static
– Schedule determined a priority
• Dynamic
– Schedule determined at run-time
• Priority Driven
– Each task assigned a priority
• Fixed priority assignment
– Priorities assigned statically
• Preemptive
– Higher priority task preempts lower priority task
上面是介绍性质,现在具体设计到论文
1 论文假设:
(A1) The requests for all tasks for which hard deadlines exist are periodic, with constant interval
between requests.
(A2) Deadlines consist of run-ability constraints only { i.e. each task must be completed before the
next requests for it occurs.
(A3) The tasks are independent in that requests for a certain task do not depend on the initialization
or the completion of requests for other tasks.
(A4) Run-time for each task is constant for that task and does not vary with time. Run-time refers
to the time which is taken by a processor to execute the task without interruption.
(A5) Any non-periodic tasks in the system are special; they are initialization or failure-recovery rou-
tines; they displace periodic tasks while they themselves are being run, and do not themselves
have hard, critical deadlines.
不过,大部分假设都是软性的,后续的部分地区论文也主要是针对这些限制条件做了松懈.
2 论文结构: 介绍了以下三方面
• Rate monotonic scheduling
• Deadline driven scheduling
• Mixed scheduling
2.1 首先是RM, 用到的假设如下
1 Requests for all tasks are periodic
– constant interval between requests
2 Deadline consists of run-ability constraints only
– deadline for a task same as end of interval between requests for the task
3. Tasks are independent
– Not dependent on initiation or completion of other tasks
4. Run-time for task is constant
– time taken by a processor to execute the task is a constant
– does not vary over time
RM算法是固定优先级算法,算法思想
RM Priority Assignment
• Rate monotonic priority assignment
– Assign higher priority to tasks with higher request rate
– Optimum assignment
– higher processor utilization
针对这种fixed-prior 有下面成立
A critical instant for a task is defined to be an instant at which a request for that task will have the largest response time. A critical time zone for a task is the time interval between a critical instant and the end of the response to the corresponding request of the task. We have the following theorem.
Theorem 1 A critical instant for any task occurs whenever the task is requested simultaneously
with requests for all higher priority tasks.
Theorem 2 If a feasible priority assignment exists for some task set, the rate-monotonic priority
is feasible for that task set.
就不贴proof了.麻烦,紧接着,考虑效率
Theorem 3 For a set of two tasks with xed priority assignment, the least upper bound to the
processor utilization factor is U = 2(2^1/2-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 = m(2^1/m-1).
把定律4中的ratio 2 times 去掉,得到定律5
Theorem 5 For a set of m tasks with fixed priority order, the least upper bound to processor utilization is U = m(2^1/m-1).
2.2 接着是Deadline Driven
We turn now to study a dynamic scheduling algorithm which we call the deadline driven scheduling algorithm. Using this algorithm, priorities are assigned to tasks according to the deadlines of their current requests. A task will be assigned the highest priority if the deadline of its current request is the nearest, and will be assigned the lowest if the deadline of its current request is the furthest.
Deadline driven scheduling
• Task with earliest deadline given highest priority
• Dynamic priority assignment
• Optimum – if a set of tasks can be scheduled by some priority assignment, it
can be scheduled using deadline driven priority assignment
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 if and only if
(C1/T1) + (C2/T2) + …. + (Cm/Tm) <= 1
Necessity proof
T=T1.T2.T3……Tm
(T/T1)C1 + (T/T2)C2 + ……+ (T/Tm)Cm > T
(C1/T1) + (C2/T2) + …. + (Cm/Tm) > 1
Sufficiency proof
Assume necessity condition is satisfied and yet
the scheduling is not feasible
There exists T | 0 ÿ<=T <= T1.T2.T3….Tm, where
an overflow occurs
floor(T/T1).C1 + floor(T/T2).C2 + …..+
floor(T/Tm).Cm > T
(T/T1).C1 + (T/T2).C2 + …..+ (T/Tm).Cm > T
2.3 最后是Mixed Sche
• Combination of RM and deadline driven scheduling
• Shortest tasks 1..k are scheduled using RM and k+1..m are scheduled using
deadline driven algorithm
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.
Theorem 9 A necessary and suffcient condition for the feasibility of the deadline driven scheduling
algorithm with respect to a processor with availability function ak(t) is 省略...
