System and method for implementing distributed priority inheritance

• US 20060282836A1
• Filed: 06/09/2005
• Published: 12/14/2006
• Est. Priority Date: 06/09/2005
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Barker, Thomas N.
• Granted Patent: US 7,788,668 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Priority inheritance is implemented across a distributed system, preferably by use of a mutual exclusion object, referred to as a pseudo-mutex, which provides operations for communicating priority of a task which is held to a different connected processor or node of a network and generating a dummy local command of priority at least equal to that of the held task at the remote processor or node in collaboration with a real-time operating system and middleware. The remote real time operating system then carries out priority inheritance in the normal manner to raise the priority of a blocked task, thus reversing any preemption of that task at the remote processor or node. The increase in priority avoids preemption of lower priority processes and thus increases the execution speed of the executing thread to release the existing lock at an earlier time; allowing a lock to be obtained by the higher priority thread. The middleware serves as an intermediary, communicating messages that include pseudo-mutex arguments or similar communications and requests for enabling priority inheritance across nodes.

Claims

1. A mutual exclusion arrangement for operation at a first processor for providing only sequential access to a sequentially reusable resource, said mutual exclusion arrangement including

means for storing an identification of said mutual exclusion arrangement,

means for storing state information including whether said mutual exclusion arrangement is locked or unlocked and, if locked, an identification of a task causing that lock,

a queue of tasks seeking a lock of said mutual exclusion arrangement,

means for executing seize and lock operations,

means for storing a forward pointer to a second processor which may be set in response to a task having a higher priority than said task causing said lock on said mutual exclusion arrangement being placed in said queue, and

means for causing an operation to be started locally on said second processor at a priority at least equal to said task being queued.

2. A mutual exclusion arrangement as recited in claim 1, wherein said mutual exclusion arrangement is a software mutual exclusion object.

3. A mutual exclusion arrangement as recited in claim 1, wherein said operation to be started locally on said second processor is a Raise_Priority operation.

4. A mutual exclusion arrangement as recited in claim 1, wherein said operation to be started locally on said second processor is a dummy operation.

5. A mutual exclusion arrangement as recited in claim 4. wherein said dummy operation is a No-Op operation.

6. A real-time computing system having first and second processors, said real-time computing system including

a mutual exclusion arrangement for operation at a first processor for providing only sequential access to a sequentially reusable resource, said mutual exclusion arrangement including

means for storing an identification of said mutual exclusion arrangement,

means for storing state information including whether said mutual exclusion arrangement is locked or unlocked and, if locked, an identification of a task causing that lock,

a queue of tasks seeking a lock on said mutual exclusion arrangement,

means for executing seize and lock operations,

means for storing a forward pointer to a second processor which may be set in response to a task having a higher priority than said task causing said lock on said mutual exclusion arrangement being placed in a queue, and

means for causing an operation to be started locally on said second processor at a priority at least equal to said task being placed in a queue, and

a remote mutual exclusion arrangement including means for causing execution of said task being placed in a queue as a local operation on said second processor.

7. A system as recited in claim 6, wherein said operation to be started locally on said second processor is a Raise_Priority operation.

8. A system as recited in claim 6, wherein said operation to be started locally on said second processor is a dummy operation.

9. A system as recited in claim 8, wherein said dummy operation is a No-Op operation.

10. A method of providing priority inheritance across nodes of an open-ended data processing system, said method including steps of

detecting priority inversion between a lower priority task and a higher priority task at a first processor of said data processing system,

setting a forward pointer to a remote priority inheritance mutex, and

initiating a task having priority at least equal to said high priority task from said remote priority inheritance mutex to be performed at a second processor,

whereby a low priority task at said second processor is executed to completion at said higher priority.

11. A method as recited in claim 10, wherein said operation to be started locally on said second processor is a Raise_Priority operation.

12. A method as recited in claim 10, wherein said operation to be started locally on said second processor is a dummy operation.

13. A method as recited in claim 12, wherein said dummy operation is a No-Op operation.

14. A method as recited in claim 10, wherein said low priority task at said second processor is executed to completion at said higher priority without preemption.

15. A method as recited in claim 10, wherein said step of setting a forward pointer is implemented in an application as a target address.

16. A method as recited in claim 10, wherein said step of setting a forward pointer is implemented in middleware as a channel descriptor.

17. A method as recited in claim 10, wherein said step of setting a forward pointer is implemented in an operating system as a retained address for the write server start message.