Mutual exclusion at the record level with priority...

Details Mutual exclusion at the record level with priority... Mutual exclusion at the record level with priority...

1999-01-28

2003-05-06

Banankhah, Majid (Department: 2156)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000, C709S241000

Reexamination Certificate

active

06560627

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to computer software, and more specifically to providing efficient mutual exclusion of multiple tasks in an embedded system.
BACKGROUND OF THE INVENTION
Real time embedded software applications are often divided into individual tasks that execute independently. In typical applications, these tasks operate on data that is global to the application, or to more than one of the application's tasks. Global data is often organized into groupings of like records. Each record is a data structure that represents a collection of fields or elements. Global data may consist of thousands of records, each representing an instance of something the application must manage. To ensure data integrity and proper operation of the application, access to one record must not interfere in any way with access to any other record. In systems in which one task is preempted in order to allow another task to run, the probability of data corruption and/or race conditions occurring is often unacceptably high. To prevent these conditions from arising, some form of mutual exclusion is required.
In distributed processing and other multi-user or multi-task applications, record locking is used to control reading data from or writing data to a record. A mutual exclusion record locking mechanism helps to ensure that only one program or routine at a time can access a record. In general, multiple read locks on a record are allowed simultaneously, while only one write lock per record is permitted at any one time. A read lock must be refused if another task has a write lock on a record, and vice versa. Thus, both read locks and write locks are record accesses.
Because of performance considerations, real time embedded software applications impose strict requirements on mutual exclusion mechanisms. For example, a mutual exclusion mechanism cannot consume significant memory, nor can it impose a significant amount of processing overhead. Although actual requirements vary in terms of the available memory and processing power of the system, the mechanism must in general not be wasteful.
Furthermore, in most applications, the mutual exclusion mechanism must support priority inheritance. If a low priority task holds a resource, and a higher priority task requests that resource, the priority of the low priority task should be elevated to that of the high priority task until it task releases the resource. Once the resource is released, priorities should revert to their original levels. In general, it is also desirable for the mutual exclusion mechanism to be able to detect and/or prevent deadlock. In a multi-tasking environment several tasks may compete for a finite number of resources. A task requests resources; if the resources are not available at that time the tasks enters the wait state. It may happen that waiting tasks will never again change state, because the resources they have requested are held by other waiting tasks. This situation is called deadlock. For example, deadlock occurs when a first task requests a record held by a second task while the second task is simultaneously requesting a record held by the first task. The result is neither task has its request answered. Such an occurrence could cause the application program or system software to crash.
Present operating systems typically employ mutual exclusion schemes that include one or more of the following mechanisms: semaphores, mutexes, or preemption locks. Each of these mechanisms possess disadvantages that limit their utility in real-time embedded system applications.
Basic mutual exclusion systems use semaphores, which are flags used in programs to coordinate the activities of more than one program or routine. Since one semaphore is required for each routine or resource that is to be protected, the use of semaphores may require significant memory usage. In certain applications, the number of semaphores may be limited in number by the operating system. For example, some operating systems provide a limited number of semaphores, and may not be designed to work well in an environment where many thousands would be required for record-level locking.
Mutexes are similar to semaphores but are related to the use of operating system threads. Therefore implementation of mutual exclusion through mutexes requires the application to use threads rather than tasks. Since threads, and therefore mutexes, are not universally supported by all operating systems, applicability of this approach is limited. Moreover, mutexes generally exhibit the same memory usage disadvantages as semaphores.
Preemption locks are used to prevent a current task from being preempted during a critical region. This mechanism basically elevates the task with a lock to the highest possible priority. In a real time environment, this is generally unacceptable, as a very low priority task can prevent a high priority task from running for a significant amount of time, and embedded systems typically require that critical system events be processed with as little delay as possible.
SUMMARY AND OBJECTS OF THE INVENTION
One of the objects of the present invention is to provide a mutual exclusion mechanism that allows read/write locking at the record level.
Another of the objects of the present invention is to provide a mutual exclusion mechanism that provides record locking with minimal memory and processor bandwidth requirements.
A further object of the present invention is to provide a record locking mechanism that both detects and prevents deadlock.
In one embodiment of the present invention, a method of providing mutual exclusion at a single data element level for use in embedded systems is described. 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 for resources to be freed are stored in a wait list. A single mutual exclusion semaphore synchronize any request to access a resource.


REFERENCES:
patent: 5530903 (1996-06-01), Calvignac
patent: 5991845 (1999-11-01), Bohannon et al.
patent: 6237019 (2001-05-01), Ault et al.

Affiliated with

Also associated with

Rating

Mutual exclusion at the record level with priority... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mutual exclusion at the record level with priority..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mutual exclusion at the record level with priority... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3005072