CALCULATING QUALITY OF SERVICE
Quality of Service for a task is a value that represents the probability that in an
arbitrarily long execution history, a randomly selected job of that task will meet its
deadline. Given a task's requirements, the SRMS service tries to negotiate a time
allowance and a quality of service value for a task that will satisfy the task's
needs. Since allowance and QoS values are totally dependent on one another, the SRMS
service must basically negotiate an allowance that will be sufficient to meet the task's
quality of service, and find a quality of service that can be met within the
allowance. It is a complicated negotiation process that is all performed by the
functions in the calcsrms.c file. All the functions found in this file
are adapted entirely from Atlas' SRMS Simulator code.
Due to the dynamic nature of the SRMS system, quality of service negotiation cannot
just be performed on a single task. The admittance of a new task alters the entire
task set because the new task's higher priority task suddenly has a new super-period.
That means that the QoS for the higher priority task must also be recalculated.
Therefore, in a practical implementation such as this where tasks can enter and
leave the system on the fly, QoS negotiation must consider the entire task set and base
its admissibility decisions on the overall utilization of that system. The specifySystem()
function does just that.
specifySystem() FUNCTION:Once all tasks have registered and are organized, specifySystem()
is called from the QoS admission thread. It takes as
its sole argument a pointer to a qos_task_info_struct, which is a pointer to
the first task in the task set to be tested. For each task in turn, the appropriate
allowance is determined if QoS requirements are given, and the appropriate QoS is
determined from the specified allowance. Once all tasks in the set have both an allowance
and QoS value, the total system utilization is determined. If the system is over-utilized,
then the function decreases the allowance of each task in proportion to its importance. If
that system is still over-utilized, then one unit of allowance is removed from each task
in turn until the system passes. Otherwise, if the system is under-utilized, then the
extra system time gets distributed to all tasks according to their importance. After that,
if the system is remains under-utilized, then the function tries to add an extra unit of
allowance to each task in turn, until it equals the maximum utilization of the system.
SpecifySystem() uses the functions calcQos() and findAllowance()
to do the dirty work of determining quality of service values. findAllowance()
uses a binary search to determine the allowance to give to the task so that its QoS
requirements are met. It looks between 0 and the task's super-period to determine an
appropriate allowance, and once a value is found, it is set in allowance field of the
task's task_struct structure. To arrive at a QoS value, calcQos()
creates an array called probLTArray in which it stores the sum of the
probabilities of all possible execution histories. In doing so, it calls idealCDF()
for each possible execution history and uses the task's sample execution times array that
was supplied during SRMS registration to create a probability of success for that
execution history. Once the function generates the probability of all possible histories,
it then applies that into the formula for determining the QoS of a task, as described in
the Statistical
Rate Monotonic Scheduling, by Atlas and Bestavros.