| Commit message (Collapse) | Author | Age |
|---|
| | |
|
| |
|
|
|
|
|
| |
a very ugly kludge. wake ups are queued in
a per-cpu buffer. lock, unlock, and budget
operations that affect priority then have to
flush the wake queue.
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
| |
New budget drain policy drains while task is executing
or suspends for a non-litmus-lock (non-real-time, such
as for I/O) reason.
|
| |
|
|
|
|
| |
Also added logic for real-time tasks to prevent
worker threads (klmirqd and aux tasks) from inheriting
from tasks waiting for release.
|
| |\
| |
| |
| |
| |
| |
| | |
Conflicts:
include/litmus/budget.h
litmus/sched_cedf.c
litmus/sync.c
|
| | | |
|
| | | |
|
| | |
| |
| |
| |
| |
| |
| |
| | |
Fixed a major bug where a scheduled task with
and exhausted budget does not recheck its priority
inheritance upon deadline postponement. Postponment
may enable priority inheritance relations, as the
priority of the lock holder decreases.
|
| | |
| |
| |
| |
| |
| |
| | |
Added support to IKGLP to handle budget exhaustion
of blocked waiter.
NOTE: CODE IS UNTESTED...
|
| | | |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Fixed bug whereby the budget timer could fire and be handled
on a remote CPU while a task is waking up. Thus, the handler
runs the 'is-running' branch of logic and triggers a remote
resched. In the meantime, the target task runs and blocks.
Thus, the budget is not refreshed in the resched routine
because the task is both out of budget AND blocked.
The fix: In the on_blocked routine, re-arm the timer. This will
re-run the exhaustion logic.
|
| | |
| |
| |
| |
| |
| |
| | |
Adds a configuration option to allow the ready queue
to be a recursive (raw) spinlock. This is useful
in implementing inheritance from nested locking
and budget enforcement actions.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
This adds an implementation of recursive spinlocks.
These allow a lock to be taken repetitively in a nested
fastion by the same CPU, provided that every lock call
is matched with an unlock call.
In general, the use of recursive locks IS TO BE
DISCOURAGED. However, it can make some implementation
easier. Try to only use recursive spinlocks as a
stop-gap measure in software development.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Proper sobliv draining: Always and only drain budget
from a task if its BASE priority is among the top
m processors in the cluster. This required some
work with timers and tracking of consumed budget
while a task is suspended (since the Linux rq won't
track this for us).
Had to introduce a number of hacks and kludges to
make this work in the required timeframe:
1) C-EDF's ready queue lock becomes recursive (yuck!)
2) Extend bheap with a for_each visitor function.
This is needed to set a timer for each newly released
job.
3) Dual-binary heap structure in C-EDF to divide
jobs into top-m and not-top-m tasks.
4) Restructured the budget plugin API. Unfortunatly,
there is not a lot of overlap between SIMPLE and
SOBLIV draining policies.
|
| | |
| |
| |
| | |
Also fixed numerous bugs...
|
| | | |
|
| | | |
|
| | | |
|
| | | |
|
| | |
| |
| |
| |
| |
| |
| | |
Adds support for suspension-oblivous budget draining
to C-EDF. Also changes how jobs with exhausted budget
in C-EDF are treated: jobs are early released until
they catch up.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
As a step towards implementing more complex budget tracking
method (ex. BWI, VXR, etc.), we need per-task budget trackers
because we may be required to drain budget from a task, even
while it is suspended or blocked.
This patch does:
1) Replaces the per-CPU hrtimers with per-task hrtimers.
2) Plugin architecture for different budget policies.
This patch creates three budget draining policies:
SIMPLE, SAWARE (suspension-aware), and SOBLIV (suspension-oblivious).
However, only SIMPLE is supported by this patch.
SIMPLE (default):
Budget drains while the task is scheduled. Budget is preserved
across self-suspensions (but not job completions, of course).
Only SIMPLE is supported in this patch. (Maintaining current Litmus
functionality.)
SAWARE:
Draining according to suspension-aware analysis. Budget should drain
whenever a task is among the top-m tasks in its cluster, where
m is the number of processors in said cluster. This draining should
happen whether or not the task is actually scheduled.
SOBLIV:
Draining according to suspension-oblivious analysis. Budget should
drain whenever the task is scheduled or suspended (but not due to
preemption). Exception: Draining should halt when we can prove that
the task is not among the top-m tasks blocked on the same lock (i.e.,
on the PQ in the OMLP-family locking protocols).
|
| | | |
|
| |\|
| |
| |
| |
| |
| |
| |
| |
| | |
Conflicts:
include/litmus/litmus.h
include/litmus/rt_param.h
litmus/Makefile
litmus/sched_cedf.c
litmus/sched_gsn_edf.c
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Tasks can now be PERIODIC or SPORADIC.
PERIODIC tasks do not have their job number incremented
when they wake up and are tardy. PERIODIC jobs must
end with a call to sys_complete_job() to set up their next
release. (Not currently supported by pfair.)
SPORADIC tasks _do_ have their job number incremented when
they wake up and are tardy. SPORADIC is the default task
behavior, carrying forward Litmus's current behavior.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
This patch allows a task to request early releasing
via rt_task parameters to sys_set_task_rt_param().
Note that early releasing can easily peg your CPUs
since early-releasing tasks never suspend to wait for
their next job. As such, early releasing is really
only useful in the context of implementing bandwidth
servers, interrupt handling threads (or any thread that
spends most of its time waiting for an event), or
short-lived computations. If early releasing pegs your
CPUs, then you probably shouldn't be using it.
|
| | | |
|
| |\| |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Nesting of locks was never supported in LITMUS^RT since
the required analysis does not exist anyway. That is, as
defined in the literature, the protocols implemented
in LITMUS^RT have not been studied in conjunction with
nested critical sections.
In LITMUS^RT, attempting to nest locks could lead to
silent or not-so-silent bugs. This patch makes this
restriction explicit and returns EBUSY when a process
attempts to nest resources.
This is enforced on a protocol-by-protocol basis,
which means that adding protocols with support for
nesting in future versions is not affected by this
change.
Exception: PCP and SRP resources may be nested,
but not within global critical sections.
|
| | | |
|
| | | |
|
| | | |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Generalized the IKGLP implementation to support non-optimal
configurations. Parameters allow the IKGLP to be configured
as FIFO queues (aka KFMLP), a single priority queue, or
a hybrid (optimal IKGLP). The maximum number of users within
the FIFO queues is also parameterized, allowing more than 'm'
replica holders to hold replicas concurrently (this breaks
optimality though).
Also fixed a bug in locking.c where DGL prority inheritance
is determined.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
First 'working' implementation of DGLs with PRIOQ_MUTEX.
(All other code prior was work-in-progress.)
General approach:
Because of priority queue order, PRIOQ_MUTEX DGLs must be
*acquired* atomically. This means that a task cannot
acquire an available PRIOQ_MUTEX if another PRIOQ_MUTEX
is not available at the same time. Requests are buffered
in PRIOQ_MUTEX and the resource 'idles'-- that is, the
mutex owner is NULL, but there are waiting tasks for the
resource.
Several notes/side-effects:
1) A high-priority task that idles a resource can
effectively block lower-priority tasks from acquiring
that resource. This is because the low-prio task
cannot skip ahead of the high-prio task in the priority
queue.
2) Priority inheritance from nesting can cause the
low-prioity task in #1 to jump over the high-priority
task and acquire the resource. This means that
any task blocked on a DGL that receives an increase
in priority while blocked on the DGL must trigger
a re-eval of the locks it can take. If the resources
can be acquired, then the task needs to be woken
up! <<<<< Lock acquisition via inheritance is entirely
new and weird! >>>>>
3) A similar case for #2 exists for priorty decreases
(example: this can happen when a task loses a donor)
while it is blocked on a PRIOQ_MUTEX. The high-priority
task described in #1 can change and become a lower-
priority task. Every idle lock (mutex owner is NULL)
on which the task losing priority must be revaluated---
it is possible that the (possible) new head on the
priority queue can take the lock. Note: This affects
BOTH singular and DGL resource requests, while
the case described in #2 only affects DGL requests
(because a singular request at the head of the priority
queue will never idle a resource).
|
| | | |
|
| | | |
|
| | | |
|
| | | |
|
| | | |
|
| | | |
|
| |\| |
|
| | |
| |
| |
| | |
Allow tracing of NULL tasks. Makes debugging a bit easier.
|
| | |
| |
| |
| |
| |
| | |
IKGLP wasn't being passed the right value for
'm' in C-EDF. It went undected for so long
since m < k in our GPUSync experiments.
|
| | |
| |
| |
| |
| | |
fixed minor bugs and cleaned up
ikglp affinity logic
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Bug: Inheritance not propagated to klmirqd and aux
tasks when the task these threads inherit from
has a change in its own priority.
(Also removed per-task NV interrupt tracking since
we cannnot identify exact interrupt ownership under
GPUSync.)
|
| | | |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Fixed bug where AUX tasks were being added to the
ready queue while those AUX tasks were actually blocked.
Bug stems from the fact that the AUX tasks do not
make themselves realtime, but another thread does this
instead. Also fixed minor bugs elsewhere.
NOTE: ONLY FIXES C-EDF. OTHER PLUGINS REMAIN TO BE FIXED.
|
