aboutsummaryrefslogtreecommitdiffstats
path: root/litmus
Commit message (Collapse)AuthorAge
* EDF priority tie-breaks.wip-robust-tie-breakGlenn Elliott2012-08-27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Instead of tie-breaking by PID (which is a static priority tie-break), we can tie-break by other job-level-unique parameters. This is desirable because tasks are equaly affected by tardiness since static priority tie-breaks cause tasks with greater PID values to experience the most tardiness. There are four tie-break methods: 1) Lateness. If two jobs, J_{1,i} and J_{2,j} of tasks T_1 and T_2, respectively, have equal deadlines, we favor the job of the task that had the worst lateness for jobs J_{1,i-1} and J_{2,j-1}. Note: Unlike tardiness, lateness may be less than zero. This occurs when a job finishes before its deadline. 2) Normalized Lateness. The same as #1, except lateness is first normalized by each task's relative deadline. This prevents tasks with short relative deadlines and small execution requirements from always losing tie-breaks. 3) Hash. The job tuple (PID, Job#) is used to generate a hash. Hash values are then compared. A job has ~50% chance of winning a tie-break with respect to another job. Note: Emperical testing shows that some jobs can have +/- ~1.5% advantage in tie-breaks. Linux's built-in hash function is not totally a uniform hash. 4) PIDs. PID-based tie-break used in prior versions of Litmus. Conflicts: litmus/edf_common.c
* Improve readability of EDF comparisons.Glenn Elliott2012-08-20
| | | | | | Restructured the EDF task comparison code to improve readability. Recoded chained logical expression embedded in return statement into a series of if/else blocks.
* New Feature: Arbitrary deadlines.2012.2Glenn Elliott2012-08-01
| | | | | | | | | | | | Added support for arbitrary deadlines. Constraint: Relative deadline must be >= exec cost. Use: Set relative deadline in rt_task::rdeadline. Set value to 0 to default to implicit deadlines. Limitations: PFAIR not supported by this patch. PFAIR updated to reject tasks that do not have implicit deadlines.
* control page: avoid "minor" page faultsBjoern Brandenburg2012-07-23
| | | | | | | | | By default, even private writable pages are mapped with the RW bit disabled in the PTE. This causes a "minor" page fault when the page is first written to. To avoid this, make sure that vm_inert_page() uses the proper page protection bits and mark the VMA as VM_IO to keep the rest of the VM code out.
* control page: warn on page faultBjoern Brandenburg2012-07-23
| | | | | Page faults should not happen here. Scream if they do anyway. This is useful when extending the control page.
* control page: use vm_insert_page() instead of remap_pfn_range()Bjoern Brandenburg2012-07-23
| | | | | | vm_insert_page() is the simpler and preferred interface for remapping individual pages and includes additional error checks. It suffices for our purposes, so let's use it instead.
* P-FP: reject tasks with invalid prioritiesBjoern Brandenburg2012-07-23
| | | | | | The existing admission test failed to test for too-low priorities. Use the common macro to accept only valid priorities.
* P-FP: fix build bug if !CONFIG_RELEASE_MASTERBjoern Brandenburg2012-07-23
| | | | | Move declaration of 'cpu' out of #ifdef block, it's also needed for CONFIG_LITMUS_LOCKING.
* P-FP: make PCP available to userspaceSven Dziadek2012-07-23
| | | | Prior to that it was only used internally for DPCP
* P-FP: port P-FP plugin used in B. Brandenburg'sSven Dziadek2012-07-23
| | | | | | | | | | dissertation (branch bbb-diss) to current version of litmus This is needed for ongoing projects I took the unchanged code but removed some leftovers of OMLP which is not implemented
* C-EDF: do not requeue jobs without budgetBjoern Brandenburg2012-05-31
| | | | | | This patch replicates the fix in commit f141d730e91283a9bb5cfcb134fcead55d5da0c6 (which applies to GSN-EDF).
* GSN-EDF: do not requeue jobs without budgetBjoern Brandenburg2012-05-31
| | | | | | | | | | This patch changes how preemptions of jobs without budget work. Instead of requeuing them, they are now only added if they are not subject to budget enforcement or if they have non-zero budget. This allows us to process job completions that race with preemptions. This appears to fix a BUG in budget.c:65 reported by Giovani Gracioli.
* Move budget-related helpers to budget.hBjoern Brandenburg2012-05-31
| | | | | | | | | litmus.h is accumulating too many things. Since we already have budget.h, let's stick all budget-related inline functions there as well. This patch is merely cosmetic; it does not change how budget enforcement works.
* An efficient binary heap implementation.wip-stage-binheapGlenn Elliott2012-05-26
| | | | | | | An efficient binary heap implementation coded in the style of Linux's list. This binary heap should be able to replace any partially sorted priority queue based upon Linux's list.
* Add kernel-style events for sched_trace_XXX() functionsAndrea Bastoni2012-03-30
| | | | | | | | | | | | | | | | | | Enable kernel-style events (tracepoint) for Litmus. Litmus events trace the same functions as the sched_trace_XXX(), but can be enabled independently. So, why another tracing infrastructure then: - Litmus tracepoints can be recorded and analyzed together (single time reference) with all other kernel tracing events (e.g., sched:sched_switch, etc.). It's easier to correlate the effects of kernel events on litmus tasks. - It enables a quick way to visualize and process schedule traces using trace-cmd utility and kernelshark visualizer. Kernelshark lacks unit-trace's schedule-correctness checks, but it enables a fast view of schedule traces and it has several filtering options (for all kernel events, not only Litmus').
* Feather-Trace: keep track of interrupt-related interference.2012.1Bjoern B. Brandenburg2012-01-30
| | | | | | | Increment a processor-local counter whenever an interrupt is handled. This allows Feather-Trace to include a (truncated) counter and a flag to report interference from interrupts. This could be used to filter samples that were disturbed by interrupts.
* Litmus core: simplify np-section protocolwip-2011.2-bbbBjoern B. Brandenburg2011-11-24
| | | | | | User a 32-bit word for all non-preemptive section flags. Set the "please yield soon" flag atomically when accessing it on remotely-scheduled tasks.
* C-EDF: rename lock -> cluster_lockBjoern B. Brandenburg2011-11-24
| | | | The macro lock conflicts with locking protocols...
* locking: use correct timestampBjoern B. Brandenburg2011-11-24
|
* Feather-trace: let userspace add overhead eventsBjoern B. Brandenburg2011-11-24
| | | | | This is useful for measuring locking-related overheads that are partially recorded in userspace.
* ftdev: let bufffer-specific code handle writes from userspaceBjoern B. Brandenburg2011-11-24
| | | | | This allows us to splice in information into logs from events that were recorded in userspace.
* ftdev: remove event activation hackBjoern B. Brandenburg2011-11-24
| | | | | Instead of doing the hackisch 'write commands to device' thing, let's just use a real ioctl() interface.
* Feather-Trace: keep track of release latencyBjoern B. Brandenburg2011-11-24
|
* Feather-Trace: trace locking-related suspensionsBjoern B. Brandenburg2011-11-24
|
* Feather-Trace: start with the largest permissible rangeBjoern B. Brandenburg2011-11-24
| | | | MAX_ORDER is 11, but this is about number of records, not number of pages.
* bugfix: add processors in order of increasing indices to clustersBjoern B. Brandenburg2011-11-24
| | | | | Pfair expects to look at processors in order of increasing index. Without this patch, Pfair could deadlock in certain situations.
* Pfair: improve robustness of suspensionsBjoern B. Brandenburg2011-11-24
| | | | | | | | | | | | | | | This patch fixes two crash or hang bugs related to suspensions in Pfair. 1) When a job was not present at the end of its last subtask, then its linked_on field was not cleared. This confused the scheduler when it later resumed. Fix: clear the field. 2) Just testing for linked_on == NO_CPU is insufficient in the wake_up path to determine whether a task should be added to the ready queue. If the task remained linked and then was "preempted" at a later quantum boundary, then it already is in the ready queue and nothing is required. Fix: encode need to requeue in task_rt(t)->flags.
* Add option to turn off preemption state tracingBjoern B. Brandenburg2011-11-24
| | | | | | Preemption state tracing is only useful when debugging preemption- and IPI-related races. Since it creates a lot of clutter in the logs, this patch turns it off unless explicitly requested.
* Add unlikely() to rel master check (match pfair).Glenn Elliott2011-11-02
|
* bugfix: release master CPU must signal task was pickedBjoern B. Brandenburg2011-11-02
|
* Pfair: various fixes concerning release timersBjoern B. Brandenburg2011-08-27
|
* Pfair: add support for true sporadic releasesBjoern B. Brandenburg2011-08-27
| | | | | | This patch also converts Pfair to implement early releasing such that no timer wheel is required anymore. This removes the need for a maximum period restriction.
* Pfair: add release master support.Bjoern B. Brandenburg2011-08-27
| | | | | Merged in release master support for Pfair. Some merge conflicts had to be resolved.
* C-EDF: Make migration affinity work with Release MasterGlenn Elliott2011-08-27
| | | | | | | | | | Needed to update C-EDF to handle release master. Also updated get_nearest_available_cpu() to take NO_CPU instead of -1 to indicate that there is no release master. While NO_CPU is 0xffffffff (-1 in two's complement), we still translate this value to -1 in case NO_CPU changes. Signed-off-by: Andrea Bastoni <bastoni@cs.unc.edu>
* C-EDF: add release master supportBjoern B. Brandenburg2011-08-27
| | | | As with GSN-EDF, do not insert release master into CPU heap.
* PSN-EDF: add release master supportBjoern B. Brandenburg2011-08-27
| | | | We can give up a processor under partitioning, too.
* Avoid needlessly costly migrations. CONFIG_SCHED_CPU_AFFINITYGlenn Elliott2011-08-27
| | | | | | | | | | | | | Given a choice between several available CPUs (unlinked) on which to schedule a task, let the scheduler select the CPU closest to where that task was previously scheduled. Hopefully, this will reduce cache migration penalties. Notes: SCHED_CPU_AFFINITY is dependent upon x86 (only x86 is supported at this time). Also PFair/PD^2 does not make use of this feature. Signed-off-by: Andrea Bastoni <bastoni@cs.unc.edu>
* Fix prototype mismatching and synch syscall numbersAndrea Bastoni2011-08-27
| | | | | | * Update prototypes for switched_to(), prio_changed(), select_task_rq(). * Fix missing pid field in printk output. * Synchronize syscall numbers for arm and x86.
* Merge 'Linux v3.0' into LitmusAndrea Bastoni2011-08-27
| | | | | | | | | | | | | | | | | | | | | | | Some notes: * Litmus^RT scheduling class is the topmost scheduling class (above stop_sched_class). * scheduler_ipi() function (e.g., in smp_reschedule_interrupt()) may increase IPI latencies. * Added path into schedule() to quickly re-evaluate scheduling decision without becoming preemptive again. This used to be a standard path before the removal of BKL. Conflicts: Makefile arch/arm/kernel/calls.S arch/arm/kernel/smp.c arch/x86/include/asm/unistd_32.h arch/x86/kernel/smp.c arch/x86/kernel/syscall_table_32.S include/linux/hrtimer.h kernel/printk.c kernel/sched.c kernel/sched_fair.c
* LITMUS Core: Check for valid class in RT-param syscall.Christopher Kenna2011-04-20
|
* bugfix: release master CPU must signal task was pickedBjoern B. Brandenburg2011-04-12
| | | | | Otherwise, the release master CPU may try to reschedule in an infinite loop.
* Improve FMLP queue management.wip-fmlp-dequeueGlenn Elliott2011-03-31
| | | | | | | | | | The next owner of a FMLP-protected resource is dequeued from the FMLP FIFO queue by unlock() (when the resource is freed by the previous owner) instead of performing the dequeue by the next owner immediately after it has been woken up. This simplifies the code a little bit and also reduces potential spinlock contention.
* Pfair: remove sporadic_release flagBjoern B. Brandenburg2011-02-01
| | | | | Instead of having an extra flag, Pfair should just infer sporadic release based on deadlines like other plugins, too.
* Pfair: support clustered schedulingBjoern B. Brandenburg2011-02-01
| | | | | | | Just like C-EDF is a global scheduler that is split across several clusters, Pfair can be applied on a per-cluster basis. This patch changes the Pfair implementation to enable clustering based on the recently added generic clustering support.
* Litmus core: add generic clustering supportBjoern B. Brandenburg2011-02-01
| | | | | Inspired by the existing C-EDF code, this generic version will build clusters of CPUs based on a given cache level.
* Litmus core: extract userspace interface from C-EDFBjoern B. Brandenburg2011-02-01
| | | | | Make the cluster size configuration in C-EDF generic so that it can be used by other clustered schedulers.
* Feather-Trace: rename locking trace pointsBjoern B. Brandenburg2011-02-01
| | | | | Since we don't expect to trace more than one lock type at a time, having protocol-specific trace points is not required.
* fdso: pass userpsace config argument to object constructorBjoern B. Brandenburg2011-02-01
| | | | | | | | | | | | As Glenn pointed out, it is useful for some protocols (e.g., k-exclusion protocols) to know the userspace configuration at object creation time. This patch changes the fdso API to pass the parameter to the object constructor, which is then in turn passed to the lock allocater. The return code from the lock allocater is passed to userspace in return. This also fixes some null pointer dereferences in the FDSO code found by the test suite in liblitmus.
* GSN-EDF: re-implement FMLP supportBjoern B. Brandenburg2011-02-01
| | | | This introduces the global FMLP based on the generic locking layer.
* PSN-EDF: re-implement FMLP supportBjoern B. Brandenburg2011-02-01
| | | | | Implement the partitioned FMLP with priority boosting based on the generic lock API.
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-12 10:37:12 -0500