Mutual exclusion at the record level with priority inheritance for embedded systems using one semaphore

• US 7,334,229 B1
• Filed: 12/20/2002
• Issued: 02/19/2008
• Est. Priority Date: 01/28/1999
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: McDonald, Michael F., Chu, Mark, Arora, Sumeet
• Primary Examiner(s): BULLOCK JR, LEWIS ALEXANDER
• Assistant Examiner(s): To; Jennifer N.
• Application Number:
  US10/327,487
• Time in Patent Office: 1,887 Days
• Field of Search: 718100-108, 710/200, 710/244
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/4831 with variable priority
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for providing mutual exclusion at a single data element level for use in embedded systems. Entries for tasks that are currently holding a resource are stored in a hold list. Entries for tasks that are not currently executing and are waiting to be freed are stored in a wait list. A single mutual exclusion semaphore flags any request to access a resource.

Claims

1. A computer readable medium having stored thereon sequences of instructions which, when executed by a processor, cause said processor to perform a method, said method comprised of a plurality of a tasks that may desire to lock or unlock any of a plurality of resources, said method comprising:

maintaining a first list, said first list listing a first group of said tasks, wherein, each task listed within said first group of tasks is waiting in a suspended state for at least one of said resources to be freed;

maintaining a second list, said second list listing a second group of said tasks, wherein, each task listed within said second group of tasks is holding at least one of said resources;

suspending a first task and expanding said first list to include said first task upon said first task desiring to lock a resource that is being held by a second task, said second task being listed on said second list, said first task having a priority, said resource having any one of a plurality of different levels;

setting a flag to a first state as a consequence of said first task said desiring to lock said resource;

comparing said priority of said first task with the priority of said second task; and

increasing the priority level of said second task to that of said first task if said second task has a lower priority than said first task.

2. The machine readable medium of claim 1 wherein said second list further comprises a task name, an original priority level, and a current priority level for said each task within said second group.

3. The machine readable medium of claim 2 wherein said flag is a mutual exclusion semaphore.

4. The machine readable medium of claim 3 wherein said resource is a single data element represented as a record.

5. The machine readable medium of claim 3 wherein said method further comprises allowing each single task of said plurality of tasks to access only one of said plurality of resources at a given time.

6. The machine readable medium of claim 3 wherein said method further comprises:

allowing each single task of said plurality of tasks to access a plurality of resources of said one or more resources at a given time; and

assigning a priority level to each accessed resource held by a single task if said single task accesses more than one resource of said plurality of resources at said given time.

7. The machine readable medium of claim 1 wherein said method further comprises:

determining whether a first resource of said plurality of resources contains a reference to a second resource of said plurality of references; and

deriving said second resource from said reference if said first resource contains said reference.

8. The machine readable medium of claim 7 wherein said method further comprises:

storing, in a third list, an entry for each resource of said plurality of resources for which an explicit reference is available; and

storing, in a fourth list, an entry for each resource of said plurality of resources which is derived from a reference that is contained in another resource of said plurality of resources.

9. The machine readable medium of claim 8 wherein said method further comprises:

identifying a highest priority unaccessed resource of said plurality of resources;

locking said highest priority unaccessed resource;

identifying additional resources of said plurality of resources referenced by said highest priority resource; and

locking said additional resources.

10. The machine readable medium of claim 9 wherein said method further comprises:

determining whether a locked resource of said additional resources cannot be locked; and

unlocking all locked resources having an entry in said third list that have a priority level lower than said locked resource.

11. The machine readable medium of claim 1 wherein said method further comprises waiving mutual exclusion policy if deadlock occurs between a third task and a fourth task of said plurality of tasks.

12. The machine readable medium of claim 11 wherein said method further comprises reporting a system error.

13. An apparatus, comprising:

a processor and memory operable to execute a plurality of a tasks that may desire to lock or unlock any of a plurality of resources;

said processor and memory operable to maintain;

1) a first list, said first list listing a first group of said tasks, wherein, each task listed within said first group of tasks is waiting in a suspended state for at least one of said resources to be freed;

2) a second list, said second list listing a second group of said tasks, wherein, each task listed within said second group of tasks is holding at least one of said resources;

said processor and memory operable to;

suspend a first task and to expand said first list to include said first task upon said first task desiring to lock a resource that is being held by a second task, said second task being listed on said second list, said first task having a priority, said resource having any one of a plurality of different levels;

set a flag to a first state as a consequence of said first task said desiring to lock said resource;

compare said priority of said first task with the priority of said second task; and

increase the priority level of said second task to that of said first task if said second task has a lower priority than said first task.

14. The apparatus of claim 13 wherein said second list further comprises a task name, an original priority level, and a current priority level for said each task within said second group.

15. The apparatus of claim 14 wherein said flag is a mutual exclusion semaphore.

16. The apparatus of claim 15 wherein said resource is a single data element represented as a record.

17. The apparatus of claim 15 wherein said processor and memory are also operable to allow each single task of said plurality of tasks to access only one of said plurality of resources at a given time.

18. The apparatus of claim 15 wherein said processor and memory are also operable to:

allow each single task of said plurality of tasks to access a plurality of resources of said one or more resources at a given time; and

assign a priority level to each accessed resource held by a single task if said single task accesses more than one resource of said plurality of resources at said given time.

19. The apparatus of claim 13 wherein said processor and memory are also operable to:

determine whether a first resource of said plurality of resources contains a reference to a second resource of said plurality of references; and

derive said second resource from said reference if said first resource contains said reference.

20. The apparatus of claim 19 wherein said processor and memory are also operable to:

store, in a third list, an entry for each resource of said plurality of resources for which an explicit reference is available; and

store, in a fourth list, an entry for each resource of said plurality of resources which is derived from a reference that is contained in another resource of said plurality of resources.

21. The apparatus of claim 20 wherein said processor and memory are also operable to:

identify a highest priority unaccessed resource of said plurality of resources;

lock said highest priority unaccessed resource;

identify additional resources of said plurality of resources referenced by said highest priority resource; and

lock said additional resources.

22. The apparatus of claim 21 wherein said processor and memory are also operable to:

determine whether a locked resource of said additional resources cannot be locked; and

unlock all locked resources having an entry in said third list that have a priority level lower than said locked resource.

23. The apparatus of claim 13 wherein said processor and memory are also operable to waive mutual exclusion policy if deadlock occurs between a third task and a fourth task of said plurality of tasks.

24. The apparatus of claim 23 wherein said processor and memory are also operable to report a system error.