Computer graphics processing and selective visual display system – Display driving control circuitry – Controlling the condition of display elements
Reexamination Certificate
2000-06-29
2003-12-30
Huynh, Ba (Department: 2173)
Computer graphics processing and selective visual display system
Display driving control circuitry
Controlling the condition of display elements
C345S215000, C707S793000
Reexamination Certificate
active
06670969
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to multi-threaded programming and more specifically to a method of providing thread-safe access to data having a hierarchical structure.
A computer program is a sequence of instructions that can be executed by a computer. Instructions within computer programs can be organized into threads for the purposes of separating functionality. A thread is a process that is part of a larger process or program. Threads may be executed concurrently or in a round-robin scheduling scheme. Threads generally provide a technique for organizing code in computer programs, allowing improved performance and responsiveness to external interfaces.
Data accessed by computer program threads can be organized in a hierarchical fashion. These hierarchies can store data, represented by objects, such that data retrieval and maintenance operations are improved. Web content, including text and graphics, is often organized in hierarchies. Languages exist to define these hierarchies. For example, eXtensible Markup Language (“XML”) is a specification for designing formats for text data that allows for text objects to be organized into hierarchies (i.e., XML documents). XML lets Web developers and designers create customized tags that offer flexibility in organizing and presenting information.
A common way to build object-based systems for use with multiple threads is to associate a lock with each object. Operations that might be performed incorrectly if multiple threads were simultaneously accessing an object are defined as synchronized, that is, the operation will interact with a locking mechanism to insure the proper order of execution. Whenever a synchronized operation is performed on an object, the object's lock is first obtained, preventing any other thread from performing any synchronized operation on the object until the completion of the operation holding the lock. While this method of synchronization is useful for many purposes, it frequently is not suitable for an interconnected set of objects in a hierarchical structure. Problems may arise because an operation on an object frequently cannot be completed without performing operations on its parent or child objects. In a graphical user interface (GUI), for example, a slider control object may be defined as a child of the parent dialog object. Now, consider what happens if a thread A performs an operation on the slider object at about the same time as another thread B performs an operation on the dialog object. Thread A will lock the slider object and thread B will lock the dialog object, but if thread A's operation cannot be completed without first locking all its ancestor objects and thread B's operation cannot be completed without first locking all its descendant objects a classic “deadlock” situation will occur and result in both threads becoming blocked forever, causing portions of the graphical user interface to become inoperative.
A simpler way to support operations on objects in a hierarchy is to allow just one thread at a time to perform operations on objects in the hierarchy. Depending on the nature of the system, such an architecture still offers some scope for multithreading if there are multiple hierarchies or there is a mechanism for transferring control of a specific hierarchy from one thread to another. With multiple hierarchies (e.g., several windows being displayed on the screen, and the objects displayed in each window being contained in a separate hierarchy associated with each window), each hierarchy can be under the control of a different thread. Multithreading can also be provided by using a mechanism for transferring control of a hierarchy from one thread to another. With a transferring mechanism, before a thread A could perform an operation on an object, thread A would first have to gain control of the hierarchy containing the object. If some other thread B controls the hierarchy, thread A would have to wait for thread B to finish its current operation in the hierarchy and relinquish control of it. Implementing either of these cases will provide limited multithreading. An alternative mechanism, representing the simplest possible system, provides that a given thread is the only thread that ever performs any operation on any object in the hierarchy. This approach can prevent locking problems, but only provides multithreading when independent hierarchies are controlled by different threads. In all these cases, deadlock is avoided because at any point in time there is at most one thread that is in the process of performing any operation on any object in a given hierarchy. Thus, no matter what objects in the hierarchy need to be accessed in order to perform an operation, it is guaranteed that no other thread is currently accessing any of those objects.
SUMMARY OF THE INVENTION
An operation within a hierarchy often involves accessing multiple objects. Problems arise when using threaded programming techniques if an operation on an object cannot be completed without performing operations on its parent or child objects. Therefore, these existing methods of providing thread-safe access in a mult-threaded environment are less than adequate or ideal.
In a single-threaded environment the appearance of concurrent access to multiple objects can be achieved by emulating multi-threading using a polling technique. The single thread can thus respond to multiple requests and emulate concurrent access, but such programming is error-prone and often cannot use standard library functions because they are not written to include the requisite polling operations.
Multi-threaded solutions often involve locks to insure proper access to multiple objects. One multi-threading technique involves creating a lock per object. It is extremely difficult to design all operations that can be performed on objects in a way that is free from deadlock when a lock-per-object synchronization strategy is used. In addition, the cost of just obtaining and releasing locks for all of the objects involved in an operation can be very substantial, in many cases dominating all other costs of performing the operation. Alternate multi-threading techniques include: 1) using a separate thread for each separate hierarchy, 2) using one thread that is switched between each separate hierarchy and 3) using a separate, hard-coded, thread for each separate hierarchy.
There are some operations that are not handled very satisfactorily by any of the techniques discussed above. Therefore, a general mechanism allowing multiple threads of control to work together within an application that uses hierarchies is preferable. In these situations, it is often highly desirable to have different threads operating simultaneously in different parts of a hierarchy. One example of such a situation is where a graphical window is defined with several panes, each of which is showing an independently controlled animated sequence of images. Another example is a Web browser application where it is desirable to assign to one thread the responsibility for controlling the content displayed in the browser window, while a different thread controls the menus, buttons, and other user-interface elements that are used to control the browser application. In these cases, it is desirable to have the user-interface elements that control the application remain responsive, even while the content to be displayed is being computed or downloaded.
Accordingly, it would be desirable to provide methods and apparatus for ensuring thread-safe access to a hierarchy of objects. The present invention provides a mechanism allowing different threads the ability to operate simultaneously in different parts of a hierarchy. This satisfies the requirements of speed and safety, without returning to the deadlock-prone model in which every object has its own lock. The present invention utilizes a mechanism for partitioning a hierarchy into subhierarchies, each of which can be controlled by a different thread. Using this mechanism, such subhierarchies have thread interface fram
Halstead, Jr. Robert H.
Kranz David A.
Ward Stephen A.
Curl Corporation
Hamilton Brook Smith & Reynolds P.C.
Huynh Ba
LandOfFree
Interface frames for threads does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interface frames for threads, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interface frames for threads will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3110065