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

• US 6,560,627 B1
• Filed: 01/28/1999
• Issued: 05/06/2003
• Est. Priority Date: 01/28/1999
• Status: Expired due to Term

• 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): BANANKHAH, MAJID A
• Application Number:
  US09/239,499
• Time in Patent Office: 1,559 Days
• Field of Search: 704/100, 704/101, 704/102, 704/103, 704/104, 704/108, 710/200, 710/41
• US Class Current: 718/103
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

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 method to be performed by a software routine that is comprised of a plurality of tasks that may desire to lock or unlock any of 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 method 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 method of claim 2 wherein said flag is a mutual exclusion semaphore.

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

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

6. The method of claim 3 further comprising:

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 method of claim 1 further comprising:

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 method of claim 7 further comprising:

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 method of claim 8 further comprising:

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 method of claim 9 further comprising:

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 method of claim 1 further comprsing waving mutual exclusion policy if deadlock occurs between a third task and a fourth task of said plurality of tasks.

12. The method of claim 11 further comprising reporting a system error.

13. A method to be performed by a software routine that is comprised of a plurality of tasks that may desire to lock or unlock any of 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.

14. The method 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 method of claim 14 wherein said flag is a mutual exclusion semaphore.

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

17. The method of claim 15 further comprising allowing each single task of said plurality of tasks to access only one of said plurality of resources at a given time.

18. The method of claim 15, further comprising:

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.

19. The method of claim 13 further comprising:

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.

20. The method of claim 19 further comprising:

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.

21. The method of claim 20 further comprising:

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.

22. The method of claim 21 further comprising:

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.

23. The method of claim 13 further comprising waiving mutual exclusion policy if deadlock occurs between a third task and a fourth task of said plurality of tasks.

24. The method of claim 23 further comprising reporting a system error.