Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1995-12-04
2003-03-11
Banankhah, Majid (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S241000, C712S203000
Reexamination Certificate
active
06532487
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for data processing in general, and in particular to a method for processing semaphores within a computer system. Still more particularly, the present invention relates to a method for managing semaphores in an object-oriented multi-tasking computer system.
2. Description of the Prior Art
A typical multi-tasking computer system has the capability of performing several processes in parallel. However, despite all its advantages, a multi-tasking computing environment also presents its own set of problems, primarily centered around the scheme of data protection from concurrent processes (or threads) that attempt to modify data that is shared by these processes. The traditional method for data protection within a multi-tasking environment is by utilizing a semaphore.
A semaphore is a flag variable commonly employed for maintaining the executing order among several concurrent processes that are competing for the utilization of critical resources, such as shared data or processor time. For example, a process executing within a processor can exclude all other processes from accessing some shared data by utilizing a process interlocking semaphore. The process interlocking semaphore should be set only before any access to the shared data and should be released only after all accesses to the shared data are complete. Otherwise, the exclusive access to the shared data may not be guaranteed. The traditional semaphore and its usage are described in more detail in Section 5.33 of
Structured Computer Organization
by Andrew Tanenbaum, which is incorporated herein by reference.
In order to take advantage of the multi-tasking capabilities, many object-oriented systems that were designed to run as a single execution unit today will soon be migrated towards a multi-tasking computing environment. Within an object-oriented computing environment, there are at least five different schemes of allocating semaphores to classes and objects: (1) one global semaphore, (2) one semaphore per group of classes, (3) one semaphore per class, (4) one semaphore per group of objects, and (5) one semaphore per object. Each of the five different semaphore allocation schemes is depicted in FIG.
7
. In the example shown in
FIG. 7
, there are three classes—Class A
71
, Class B
72
and Class C
73
. Each class is denoted by box
70
; and within each class there are four objects, each denoted by circle
79
. Within circle
79
is a number, ranging from 1 to 12, which corresponds to a physical semaphore.
Under the one global semaphore method, as shown in
FIG. 7
, all classes and objects share a common semaphore
1
. Under the one semaphore per group of classes method, certain classes are grouped together to share a common semaphore. For example, both Class A
71
and Class C
73
share semaphore
1
. Under the one semaphore per class method, each class has a unique semaphore. For example, Class A
71
utilizes semaphore
1
, Class B
72
utilizes semaphore
2
and Class C
73
utilizes semaphore
3
. The one semaphore per group of objects method is similar to the one semaphore per group of classes method except that the grouping is by objects instead of classes. Finally, under the one semaphore per object method, each object has a semaphore of its own. For example, each of the twelve objects has a unique semaphore represented by a number ranging from 1 to 12.
These different semaphore allocation schemes can be viewed in terms of a granularity scale, with the single global semaphore method as the least granular and the one semaphore per object method as the most granular. The rest of the allocation schemes lie somewhere in the middle of the granularity scale. Incidentally, the most desirable allocation scheme would consist of not too many semaphores such that deadlock may become a problem and not too few semaphores such that concurrency may be limited (or no concurrency at all as in the case of the single global semaphore method).
In an object-oriented system, because data has already been nicely encapsulated within an object, it is only natural to simply add a semaphore to each object to protect its instance data accordingly. However, under this allocation scheme of one semaphore per object, the number of semaphores may grow so fast that it can become unmanageable quite rapidly. For example, in a reasonably sized object-oriented computer system, the number of objects can be in the range of thousands such that thousands of semaphores would be required. This large amount of semaphores would no doubt increase the chance for deadlock tremendously.
Consequently, it would be desirable to provide a flexible method for managing semaphores in a multi-tasking computer system. This invention can be utilized in any object-oriented multi-tasking computing environment to provide a flexible scheme for allocating semaphores to balance multi-tasking concurrency performance and deadlock potential.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide a method and system for data processing.
It is another object of the present invention to provide a method and system for processing semaphores within a computer system.
It is yet another object of the present invention to provide a method and system for managing semaphores in an object-oriented multi-tasking computer system.
In accordance with the method and system of the present invention, management of semaphores may be implemented in the form of a semaphore manager data structure. The data structure comprises a multiple of indices corresponding to each class, a multiple of semaphore numbers corresponding to each semaphore, and a mapping table defining an assignment of the semaphores to each of the classes by utilizing the class indices and semaphore numbers. The assignment criteria is such that a class can only be assigned to one semaphore but a semaphore can be assigned to more than one class. The advantages of the data structure include the number of actual semaphores that can be controlled so that the computer system would not be overwhelmed, the semaphore mapping can be performed statically at time of compilation or dynamically during time of execution, potential deadlock situations can be reduced due to the assurance that only one class can request one semaphore at a time, and the semaphore tracing or debugging capabilities can be enhanced because all semaphores are managed centrally.
All objects, features and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4318182 (1982-03-01), Bachman et al.
patent: 4320451 (1982-03-01), Bachman et al.
patent: 4925311 (1990-05-01), Neches et al.
patent: 4928222 (1990-05-01), Vriezen et al.
patent: 4965718 (1990-10-01), George et al.
patent: 5050070 (1991-09-01), Chastain et al.
patent: 5057996 (1991-10-01), Cutler et al.
patent: 5159686 (1992-10-01), Chastain et al.
patent: 5230047 (1993-07-01), Frey, Jr. et al.
patent: 5369766 (1994-11-01), Nakano et al.
patent: 5379432 (1995-01-01), Orton et al.
patent: 5394551 (1995-02-01), Holt et al.
patent: 5404529 (1995-04-01), Chernikoff et al.
patent: 5430850 (1995-07-01), Papadopoulos et al.
patent: 5434975 (1995-07-01), Allen
Decouchant et al., A Synchronization Mechanism for an Object-Oriented Distributed System, Dist. Comp. Systems 1991 Int. Conf., 1991.*
Booch, Grady, Object Oriented Analysis and Design, 1994 pp. 88-89, 360-365.
Banankhah Majid
LaBaw Jeffrey S.
LandOfFree
Method and system for managing semaphores in an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for managing semaphores in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for managing semaphores in an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3066239