Changes between Initial Version and Version 1 of Ticket #2556


Ignore:
Timestamp:
01/27/16 08:46:27 (8 years ago)
Author:
Sebastian Huber
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #2556 – Description

    initial v1  
    33The O(m) Independence-Preserving Protocol ([http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf OMIP]) is a generalization of the priority inheritance protocol to clustered scheduling which avoids the non-preemptive sections present with priority boosting.  The m denotes the number of processors in the system.  Its implementation requires an extension of the scheduler helping protocol already used for the [http://www-users.cs.york.ac.uk/~burns/MRSPpaper.pdf MrsP] semaphores.  However, the current implementation of the scheduler helping protocol has two major issues, see Catellani, Sebastiano, Luca Bonato, Sebastian Huber, and Enrico Mezzetti: Challenges in the Imple- mentation of MrsP. In Reliable Software Technologies - Ada-Europe 2015, pages 179–195, 2015.  Firstly, the run-time of some scheduler operations depend on the size of the resource dependency tree.  Secondly, the scheduler operations of threads which don't use shared resources must deal with the scheduler helping protocol in case an owner of a shared resource is somehow involved.
    44
    5 To illustrate the second issue, let us look at the following example.  We have a system with eight processors and two L2 caches.  We assign processor 0 to a partition P for latency sensitive real-time tasks (e.g. sensor and actuator handling), processors 1, 2 and 3 are assigned to a cluster C,,A,, and the remaining processors are assigned to a cluster C,,_B,, for soft real-time worker tasks.  The worker tasks use a shared resource, e.g. a file system for data storage.  Let us suppose a task R of partition P sends a message to the workers.  This may make a waiting worker ready, which in turn pre-empts the owner of a shared resource.  In this case the scheduler helping protocol takes action and is carried out by the task R.  This contradicts the intended isolation of scheduler instances.
     5To illustrate the second issue, let us look at the following example.  We have a system with eight processors and two L2 caches.  We assign processor 0 to a partition P for latency sensitive real-time tasks (e.g. sensor and actuator handling), processors 1, 2 and 3 are assigned to a cluster C,,A,, and the remaining processors are assigned to a cluster C,,B,, for soft real-time worker tasks.  The worker tasks use a shared resource, e.g. a file system for data storage.  Let us suppose a task R of partition P sends a message to the workers.  This may make a waiting worker ready, which in turn pre-empts the owner of a shared resource.  In this case the scheduler helping protocol takes action and is carried out by the task R.  This contradicts the intended isolation of scheduler instances.
    66
    77The reason for this unfortunate coupling is a design issue of the scheduler helping protocol implementation.  Some scheduler operations may return a thread in need of help.  For example, if a thread is unblocked which pre-empts an owner of a shared resource, then the pre-empted thread is returned.  Once a thread in need of help is returned, the ask for help operation of the scheduler is executed.  An alternative to this return value based approach is the introduction of a pre-emption intervention during thread dispatching.  Threads taking part in the scheduler helping protocol indicate this with a positive resource count value.  In case a thread dispatch occurs and pre-empts an owner of a shared resource, the scheduler ask for help operation is invoked.  So, the work is carried out on behalf of the thread which takes part in the scheduler helping protocol.