Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-05-18
2004-09-14
An, Meng-Al T. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C711S205000, C711S206000, C718S101000, C718S103000, C718S104000, C710S200000
Reexamination Certificate
active
06792601
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an object-based computing system including an object locking system having at least two modes for controlling access to an object, and more particularly to controlling transitions between said at least two modes.
BACKGROUND OF THE INVENTION
Programs written in the Java programming language (Java is a trademark of Sun Microsystems Inc) are generally run in a virtual machine environment, rather than directly on hardware. Thus a Java program is typically compiled into byte-code form, and then interpreted by the Java virtual machine (JVM) into hardware commands for the platform on which the JVM is executing. An important advantage of this approach is that Java applications can run on a very wide range of platforms, providing of course that a JVM is available for each platform. In recent years Java has become very popular, and is described in many books, for example “Exploring Java” by Niemeyer and Peck, O'Reilly & Associates, 1996, USA, and “The Java Virtual Machine Specification” by Lindholm and Yellin, Addison-Wedley, 1997, USA.
One of the advantages of the Java language is that creating multi-threaded applications is relatively easy. This is partly because the locking concept within the Java language is simplified for the end-programmer; there is no need at the application level to specifically code lock and unlock operations. Of course locking is important for multi-threaded applications to avoid conflicts between different threads in terms of access to and manipulation of resources (which in the Java environment are referred to as objects). Thus while one thread owns a lock on an object, no other thread may perform any operation upon that object which also requires a lock on the object. This is the principle of mutual exclusion—if a thread attempts to lock an object and discovers that the object is already locked, it may not perform operations on that object until it can acquire ownership of the lock.
Controlling concurrent access to data structures is a fundamental problem in computing, for both uniprocessor and multiprocessor systems (in multiprocessor systems access may be truly concurrent; in uniprocessor systems interrupts and time slicing may occur in the midst of an operation that must be atomic to maintain correctness).
One way to implement efficient locks is to use spin locking. Typically in this approach, each lockable object contains a one-word owner field. When a thread needs to lock an object, it just goes into a loop that repeatedly tests if the object is unlocked (lock=0), and if it is unlocked it attempts to claim the lock by setting the lock field to its own thread identifier (thread).
Spin locking has a number of major advantages: it is simple to implement; it requires only one word of space overhead in the object; and if locks are released quickly it is very efficient. However, spin locking also suffers from some major disadvantages, particularly on a uniprocessor. If locks are not released quickly, or if contention for shared objects is high, then a large amount of computation will be wasted in “spinning”. On a uniprocessor, the spin-lock loop is usually modified so that the processor is yielded every time the lock acquisition fails, in order that the thread does not waste an entire time slice in spinning while other threads are waiting to run.
With spin-locking, the queues for the objects being locked are essentially encoded in the thread scheduler. When there is not much locking, this works very well. When locking is frequent and/or contention is high, then on a uniprocessor a great deal of time is wasted in scheduling threads which immediately yield again because they still can not acquire the desired lock. On a multiprocessor, a lot of excess traffic to main memory is generated by spin-locking, and this also degrades performance. A good summary and investigation of the multiprocessor performance issues is The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors, by T. E. Anderson, IEEE Transactions on Parallel and Distributed Systems, volume 1, number 1, January 1990.
The primary alternative to spin-locking is queued locking. When a thread fails to obtain a lock on an object, it places itself on a queue of threads waiting for that object, and then suspends itself. When the thread that owns the lock releases the lock, it checks if any threads are enqueued on the object. If so, it removes the first thread from the queue, locks the object on behalf of the waiting thread, and resumes the waiting thread.
Unlike spin-locking, queued locking is fair. However, unless a two-level locking scheme is employed (as described below), the time needed to acquire an uncontested queued lock is more expensive than for a spin lock. Performance is especially poor if objects are locked often, typically for short periods of time, and with contention. In this case the overhead of enqueuing and suspending becomes a factor. However, when objects are locked for longer periods of time and contention is low, queued locking is generally more efficient than spin-locking.
A problem with queued locking has to do with the management of the queues. The queues for a shared object are themselves shared objects (even while the object is locked). Therefore, some sort of mechanism is required to assure mutual exclusion on the object queues. Furthermore, there is a race condition inherent in the lock release policy: one thread may attempt to enqueue for the object at the same time that the owning thread is releasing the lock. The simplest way to solve both of these problems is to use a global spin-lock to guard the short critical sections for lock acquisition, release, and enqueuing. Every object now contains not only a lock field but also a queue field. Unfortunately, locking an unlocked object (the most common case) has now become significantly slower and more complex. There is also a global lock for which there could be significant contention as the number of threads increases (that is, the solution does not scale).
Java implementations have generally adopted a queued locking model based on the concept of monitors which can be associated with objects. A monitor can be used for example to exclusively lock a piece of code in an object associated with that monitor, so that only the thread that holds the lock for that object can run that piece of code—other threads will queue waiting for the lock to become free. The monitor can be used to control access to an object representing either a critical section of code or a resource.
Locking in Java is always at the object-level and is achieved by applying a “synchronized” statement to those code segments that must run atomically. The statement can be applied either to a whole method, or to a particular block of code within a method. In the former case, when a thread in a first object invokes a synchronised method in a second object, then the thread obtains a lock on that second object. This lock covers all the methods in that second object (this may or may not be desirable depending on the application). The alternative of including a synchronised block of code within the method allows the lock to be held by taking ownership of the lock of an arbitrary object, which is specified in the synchronised command. If such an arbitrary object is used for the lock, this lock does not prevent execution of any other methods in the second object.
One consequence of the latter approach is that any Java object may be specified for locking, not just those involving synchronised code. This is important because it means that the space available in objects for implementing locking is tightly constricted; otherwise much space is wasted supporting locking in many very small objects that in fact are never likely to be locked.
The monitor structure in Java can also be used as a communication mechanism between separate threads of execution. This is achieved by a first thread including a “wait” command within synchronised code. This suspends execution of this first thread, and effectively
Dimpsey Robert Tod
Hoflich Benjamin Joseph
Peacock Brian David
An Meng-Al T.
Shah Nilesh
VanLeeuwen Leslie A.
LandOfFree
Multiple mode object locking method and system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple mode object locking method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple mode object locking method and system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254756