**Problem Description: **The real-time system consists **m** resources and
**n** periodic tasks, **G
= {T**_{1}, …, T_{n} },
in which each task **T**_{i} = (c_{i},
p_{i}) is characterized
by its execution requirement **c**_{i}
and its period **p**_{i}. The deadline for each task
instance is the task's next period. **c**_{i}
and **p**_{i} are integer
multiples of a system unit time. The weight (or utilization) for
task **T**_{i} is defined as **w**_{i}**
= c**_{i}/p_{i}, and
the system utilization is the summation of all tasks' utilizations
**U = ****
S****w**_{i}
(**U ****
£
m**). The problem is to
design a scheduling algorithm with the following constraints: (C1).
A resource can only be allocated to one task at any time,
that is, resources can not be shared concurrently; (C2) A task can
only be allocated at most one resource at any time, that is, tasks
are not parallel and thus cannot occupy more than one resource at
any time.

**Current Solutions: **An optimal scheduling algorithm (**Pfair**)
[1] has been proposed. But, the Pfair
algorithm incurs a very high scheduling overhead by making
scheduling decision for *every* time unit to enforce **
strict proportional progress** for each task at any time unit,
which prevents it from being employed in practice, as many of its
variants. To reduce the scheduling overhead, notice that deadline
misses happen *only* at the end of tasks’ periods, we
proposed a novel idea of *boundary-fair (Bfair)*
scheduling [2], which makes scheduling decision at a period boundary
to ensure that all tasks with deadline as next period boundary will
finish on time, and to *properly* allocate resources to
the rest tasks such that they can meet their deadlines in the
future. A schedule *Bfair*
iff any task *T*_{i}
is either allocated **ë***w*_{i}**t*_{b}û
or **é***w*_{i}**t*_{b}ù
units at any period boundary time *t*_{b.
}

Bfair algorithm is also
optimal in the sense that it can achieve full system utilization.
And by making scheduling decisions at periodic boundaries, it
effectively reduces the number of scheduling points as well as
context switches. We showed that Bfair
algorithm has the same complexity as that of
Pfair algorithm for each scheduling point, but with fewer
scheduling points. Thus, it will reduce the overall scheduling
overhead compared to Pfair algorithm,
which is especially important when they are used on-line. We believe
it will attract researchers' attention from
Pfair to boundary-fairness.

Consider an example task set that has 6 tasks *
T*_{1}=(2, 5),
T_{2}=(3, 15),
T_{3}=(3, 15),
T_{4}=(2, 6),
T_{5}=(20, 30),
T_{6}=(6, 30).*
*Here, *LCM = 30, S**w*_{i}*
= 2. *The proportional-fair schedule generated by
*Pfair** *scheduling
algorithm in [1] is shown in Fig. 1 (the dotted bold lines are
period boundaries) with *30* scheduling points and **
***60* context switches. The boundary-fair schedule generated
by *Bfair** *scheduling algorithm in [2] is shown
in Fig. 2 with only *11* scheduling points and *46*
context switches.

Can we do better than the schedule above? **Yes**.
If tasks are in the order of *T*_{1}, T_{2}, T_{3},
*T*_{6}, *T*_{4}, T_{5},
the first four tasks could be scheduled on one resource while the
last two task were scheduled on another resource. We can get the **
BETTER** scheduling as shown in Fig. 3 where there are only *
29** *context switches (considering scheduling points
effect). However the ordering of tasks is *NP-hard. *

**Future work:** Exploring ideas to further
reduce the scheduling overhead and incorporating other issues in
parallel scheduling (such as synchronization and migration) would be
the next step in this direction. Also, a real implementation of the
algorithm and the performance comparison with previous efficient Pfair variants will also be pursued. A comprehensive list of
publication on the fairness scheduling algorithms can be found from
the website of
Prof. James H. Anderson (University of North Carolina at Chapel Hill).

[1]
S. K.
Baruah, N. K. Cohen, C. G. Plaxton,
and D. A. Varel. **Proportionate
progress: A notion of fairness in resource allocation**.
*Algorithmic*a, 15(6):600–625, 1996

[2]
D. Zhu, D. Mosse and R.
Melhem, **Periodic Scheduling Problem
for Multi-Processor Real-Time Systems: how much fairness is
necessary?** IEEE Real-Time System Symposium 2003