System and method for implementing distributed priority inheritance

• US 7,788,668 B2
• Filed: 06/09/2005
• Issued: 08/31/2010
• 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.
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US11/148,329
• Publication Number:
  US 20060282836A1
• Time in Patent Office: 1,909 Days
• Field of Search: 718/103, 718/102
• 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 in a computer system for operation at a first processor for providing only sequential access to a sequentially-reusable resource available at a second processor, said first and second processors communicating through a network including a plurality of processors which provide priority inheritance among locally originating tasks, said mutual exclusion arrangement including

a mutual exclusion lock for said resource, said mutual exclusion lock comprising

means for storing an identification of said mutual exclusion arrangement,

means for storing state information including whether said mutual exclusion lock 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 lock, and

means for executing seize, lock, and release operations, said mutual exclusion arrangement further comprising

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

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

whereby priority of said task causing said lock is raised or priority inheritance is triggered at said second processor from said first processor, such that said task at said second processor is executed to completion at said higher priority.

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

3. The 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. The mutual exclusion arrangement as recited in claim 1, wherein said operation to be started locally on said second processor is a dummy operation.

5. The 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 available at a second processor, said first and second processors communicating through a network including a plurality of processors which provide priority inheritance among locally originating tasks, said mutual exclusion arrangement including

a mutual exclusion lock for said resource, said mutual exclusion lock comprising

means for storing an identification of said mutual exclusion lock,

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 lock, and

means for executing seize, lock, and release operations, said mutual exclusion arrangement further comprising

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

means for causing an operation to be started locally on said second processor, in accordance with said pointer at a priority at least equal to said task being placed in said 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 and raising priority or triggering priority inheritance of a task of said second processor from said first processor, such that said task at said second processor is executed to completion at said higher priority.

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

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

9. The 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 including first and second processors communicating through a network including a plurality of processors which provide priority inheritance among locally originating tasks, said method including steps of

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

setting a forward pointer to a remote priority inheritance mutex at said second processor, and

initiating, from said remote priority inheritance mutex, an operation having priority at least equal to said high priority task to be locally performed at said second processor, in accordance with said pointer,

whereby priority inheritance is performed such that priority of said lower priority task is raised or priority inheritance is triggered and a low priority task at said second processor is executed to completion at said priority at least equal to said high priority task.

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

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

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

14. The 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. The method as recited in claim 10, wherein said step of setting a forward pointer is implemented in an application as a target address.

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

17. The 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.