| Related sites for http://www.acm.org/crossroads/xrds4-2/dynac.html |
| Echo_Reality Services include CD authoring, animation, web design and 3D graphics rendering. | | Computer_Performance_Engineering,_Inc Year 2000 software date problem impact analysis and AutoCorrect tools, and the techniques to analyze YEAR 2000-date problem. | | Unigen_Memory Designs and manufactures memory modules and products. | | QPRA_tools A collection of programmer utilities. | | SPFX-UL_Utilities_Light A collection of unusual utilities. | | LNKnet_Pattern_Classification A software package that integrates more than 22 neural network, statistical, and machine learning classification, clustering, and feature selection algorithms into a modular software package. [GPL] | | AxpDataGrid_for_ASP_NET A datagrid with data editing capabilities in form mode. | | Actinic Sells desktop ecommerce software packages that generate a complete online catalogue and shopping cart system. | | SanDriLa Program to make SDL, MSC, TTCN, URN and UML2 diagrams, implemented as a Microsoft Visio add-on. [Commercial, tree trial] | | RFC_0114 File Transfer Protocol. A.K. Bhushan. April 1971. Updated by RFC 0133, RFC 0141, RFC 0171 and RFC 0172. | | WAVE_3_0_Accessibility_Tool Online tool checks page accessibility, displays page with tags to show good and bad points. | | HeadAC3he File converter for several input and output formats including AC-3 and multichannel AAC with a special libfaac.dll. | | WAM Washington Area Midrange. | | YencPowerPost-A&A Open source tool specialized in posting files to binary newsgroups. Uses yEnc encoding format. | | RFC_0970 On Packet Switches with Infinite Storage. J. Nagle. December 1985. | | Philadelphia_Python_Users_Group New user group for the Philadelphia Area. | | AppJet,_Inc_ Users type JavaScript in Web browser box; code can then execute. Programs reside on AppJet servers; source code is public; all start as clones of extant programs. Like Lively Kernel. Descriptions, dem | | Intensedesigns_net Providing web and graphics design, database integration, application development, maintenance, multimedia development, hosting and e-commerce solutions. | | popSmarts_Popup_Killer Software integrates creating an explorer bar inside Internet Explorer. Software descriptions, screenshots, FAQs, download, and contact details. [Windows 98/Me/NT/2000/XP] | | DbNetGrid Database driven grid component based on DHTML behaviours. Grids can be searched, sorted, edited and results saved in HTML, Word or Excel formats. |
|
Extending Java to Support Shared Resource Protection and Deadlock Detection in Threads Programming
Extending Java to Support Shared Resource Protection and Deadlock Detection in Threads Programming
by
Anita J. Van Engen
Michael K. Bradshaw
Nathan Oostendorp
Abstract
Java threads enable programmers to write parallel programs very easily and conveniently. However, the current Java specification does not adequately provide for the protection of shared resources or for deadlock detection, two of the most common problems arising from parallel programs. The ability to solve these problems is crucial for Java concurrent programming. In this paper, we introduce and implement a model that can aid in writing parallel programs by providing shared resource protection and deadlock detection.
Introduction
The increasing use of parallel systems and programs in many different fields has brought new attention to how threads cooperate and share data. Parallel programs are used in such critical and sensitive environments as database operation and manipulation, data collection and system maintenance tasks. With an increasing emphasis being placed on the World Wide Web and on platform-independent tools, Java is positioned to become the language of choice for many applications, including parallel programming. While it provides some solid facilities for basic threads programming, Java does not adequately provide for shared resource protection or have the ability to detect deadlock. Adequate Java support for these features would make Java threads even more effective for parallel programming.
Let us consider two simple applications that illustrate the need for these features. First, consider a bank with 2 ATM machines. Bob and Jane share an account with a current balance of $500, and they each make a different transaction at the exact same time. Bob wants to withdraw $100 and Jane wants to deposit $150. If this scenario proceeds, without provisions for data protection, the resulting balance will be either ($500 - 100) = $400 or ($500 + 150) = $650, both of which are incorrect. This, of course, does not happen, and the correct balance will include both transactions, leaving the final balance at ($500 - 100 + 150) = $550. Second, consider the Dining Philosophers scenario [1] -- a classic resource sharing problem. There are five philosophers sitting at a table. Each has one fork between him and his neighbor on either side, for a total of five forks. Each philosopher needs two forks to eat, and can only pick up one fork at a time. The philosophers need to avoid "starvation," or the unfair sharing of resources. A problem arises if all five philosophers reach for their right forks at the same time. Each philosopher will have only one fork in their hand, and thus cannot eat. However, there are not any other forks on the table to reach for. The result of this situation is deadlock. Resource corruption and deadlock are common problems in parallel programming that are extremely difficult to detect.
These examples illustrate the need for resource protection in parallel programming, especially the need to prevent corrupted data and deadlock. In this paper, we will discuss the current ways in which Java is used for parallel programming and its associated problems. We will then introduce a model for Java resource protection. We will expand on this model by showing our implementation and performing some data analysis to demonstrate the effectiveness of our design. Finally, we will discuss implications of this model.
Background
One strong point of the Java programming language is the inclusion of threads in its basic API [4]. The Thread class allows a programmer to write concurrent code quickly and easily. Currently, the method Java uses for concurrency control is to make a class' critical procedures ``synchronized.'' Only one thread is allowed to run a synchronized procedure at a time, and all other threads are queued. When execution of the current thread completes, or when it calls the wait() method, another thread is allowed to call a synchronized procedure. The wait() method will release the lock on the current synchronized procedure and cause the thread to sleep until the notify() procedure is called. While this ``monitor'' based approach, introduced by Hoare [2], is a workable solution, placement of synchronization within procedures is often a difficult task for programmers trained only in writing serial procedures. Synchronized methods can also cause deadlock when used incorrectly, and the Java virtual machine has no native means of detecting a deadlock situation.
Consider our two previously mentioned examples. The ATM problem could easily be solved by synchronizing the methods that accessed the account. However, in a scenario where many people have access to the same account, this method can be too constrictive, and does not lend itself to more innovative, efficient designs. The dining philosophers problem can also be solved with synchronized methods, by synchronizing parts where the philosophers request and return forks. However, to solve the philosophers' problem one has to write a locking mechanism for the forks, as well as implement some sort of algorithm that will prevent the philosophers from entering a deadlock. These same considerations have to go into almost any resource-locking algorithm and could be more easily handled by built-in software controls.
The only known alternative to synchronized methods is a commercial package by Sealevel Software (http://www.halcyon.com/sealevel) called the Single-Write-Multiple-Read-Guard (SWMRG) [3]. (For information on SWMRG and a threads demo, see http://www.halcyon.com/sealevel/testswmrg.htm) It allows the programmer to protect data conservatively by allowing only one writer or multiple readers to have access to the same SWMRG object. However, it does not protect against a deadlock situation. Also, the programmer is expected to integrate the Singer-Write-Multiple-Read-Guard [3] into their own data structure, rather than having an Object protect itself, which seems more appropriate to the Java object-oriented style. Synchronized methods and Sealevel Software's SWMRG at this time are the only tools available to a parallel programmer who wants to protect data; neither of which handle the deadlock problem.
The DynAC Model
Our model for resource protection is called the DynAC Model, which stands for Dynamic Anomaly Correction. DynAC is composed of five sections, as shown in Figure 1. The interesting features of the model are the interchangeability of components and the ability to monitor activity. This section will step through this model as an introduction to its implementation.
Figure 1: The DynAC Model
The Application is a parallel system that is written by the programmer. It requests permission to read, write, and update logical portions of the shared resources. It is the responsibility of the programmer to catch exceptions which may arise from a poorly designed concurrency control for the application. Because of the modular design of the DynAC Model, the same application may be used with different forms of concurrency control.
Shared data are protected through the use of the ProtectedObject class, an extension of the Java Object Class. Each logically-distinct unit of data is a ProtectedObject. For example, in the ATM problem each account would be a ProtectedObject. All requests to read, write or update the shared data are passed through the ProtectedObjects. Once a request is made, a ProtectedObject makes a call to its associated ConcurrencyControl module in order to determine if the threads are permitted to interact. Then the ProtectedObject determines the correctness of granting a request by using internal algorithms. When the application's request is processed, the thread is allowed to proceed if there are no complications. If an error occurs due to corrupted data or a deadlock of the resources, an exception is thrown for the application to deal with or to allow the program to close without corrupting the data.
DeadLockDetection is an optional feature that allows the ProtectedObject to evaluate the correctness of the ConcurrencyControl's permissions. In several ConcurrencyControls, a set of threads will stall if they are holding resources that other threads need and requesting the resources that the other threads are holding. The DeadLockDetection module creates a graph of all the current locks and requests held by each thread in order to determine if a deadlock will occur. When a deadlock situation arises, an exception is thrown and passed through the ProtectedObject for the application to deal with.
The Thread Viewer is an optional stand-alone program. It serves as a debugging tool for the programmer. The programmer can view the schedules produced by the ConcurrencyControl. Corrupted data is highlighted in red to show where an exception would be thrown.
In order for many threads to safely use the same set of ProtectedObjects at the same time, a method of accessing data must be used. This is the job of the ConcurrencyControl module. The ConcurrencyControl implements a set of rules that allow threads to safely run at the same time. Obviously there are many different ways to allow the threads to interact with each other. The DynAC Model allows various implementations of ConcurrencyControl to be implemented with little difficulty.
These modules work together in the following manner: the Application makes requests (read, write or update) to a ProtectedObject before the data in ProtectedObject can be used. ProtectedObject passes the requests to the assigned ConcurrencyControl, which decides when the threads can access data. Because the DynAC Model does not demand that the ConcurrencyControl always return correct schedules, the ProtectedObject checks for the possibility of corrupted data and uses the DeadLockDetection module to check for deadlock. If no problem is found, the Application is allowed to proceed and use the data in ProtectedObject. If an error occurs, an exception is thrown and it is the responsibility of the Application to correct the problem. Meanwhile, the Thread Viewer collects the state of the system and graphically displays it.
Implementation of the DynAC Model
Application
The Application is a parallel program written using simple guidelines. Because most programmers have been only trained to think serially, making safe, parallel programs can be a difficult and dangerous process for them. Our model would make safe, parallel programming available to proficient serial programmers with only minimal knowledge of Java threads.
The Application is written in a serial manner with some easy rules for creating a safe, parallel environment. The first rule is that all shared data must be in logically separate pieces. These pieces are contained in or are instances of classes which extend ProtectedObject. The programmer could then choose an appropriate ConcurrencyControl for the Application (possibly from a library) to initialize the ProtectedObject. If the chosen ConcurrencyControl has a potential deadlock situation, the programmer will pass a DeadLockDetection instance to the Application's ProtectedObjects.
In order to make a Java parallel program, threads must concurrently run separate operations on shared resources. Whenever a thread needs data that is stored in a ProtectedObject, the thread asks the ProtectedObject if it can safely use it, using four methods: read_Object, write_Object, update_Object and done. Threads performing read, write and update operations call the corresponding methods. When a thread is done with that ProtectedObject, it simply calls done to release it.
If the ProtectedObjects are in a state where the data will become corrupted or deadlock will result, an exception of the proper type will be thrown. These exceptions must be caught by the programmer, who must deal with them in the Application. Each program is different. It is common to catch CorruptedDataExceptions and merely reread the ProtectedObject. This would allow operations to continue by giving the Application the correct version of the ProtectedObject to write to. When DeadLockExceptions are caught, all of the ProtectedObjects that the thread has permission to use must be released, using the done method. This would allow other threads waiting on any of those ProtectedObjects to access them, thus avoiding deadlock. In either case, the data is protected. The following code method demonstrates how to use the DynAC Model.
public boolean Check(ProtectedObject r1,r2)
{
boolean ans;
try
{ r1.read_Object();
r2.read_Object(); }
catch( DeadLockException e)
{ dropAllObjects();
// All Protected Objects must be dropped
restartThread(); }
// Permission has been granted
// Now we can read the Protected Objects
if(r1.getKey() r2.getKey() )
{ try
{ r2.writeObject() }
catch (DeadLockException e)
{ dropAllObjects();
restartThread(); }
catch (CorruptedDataException e)
{ return( Check(r1,r2) ); }
r2.incrementValue();
ans = true; }
else
{ ans = false; }
r1.done();
r2.done();
return(ans);
}
The ProtectedObject class
The ProtectedObject class is a class which extends Java's basic Object class. The ProtectedObject class creates a data object which can be shared between concurrent processes. It does this by adding specific variables and methods which enable the DynAC Model to keep track of the correct version of a data object, thus detecting corrupted data when it occurs.
The ProtectedObject class keeps track of the correct version by using a version-count algorithm, as specified below. Each ProtectedObject has a variable for the version and a hashtable, which stores the versions that each thread is requesting. If the operation is a read, then the entry in the hashtable is set to the version of the ProtectedObject. If the operation is a write and the version requested by the thread is not the current version, an exception is thrown. If the versions match, the ProtectedObject is written to and the version is incremented.
if operation = read
VC[thread] = version;
else if operation = write
if VC[thread] <> version
throw CorruptedDataException;
else
version++;
The ProtectedObject class implements the version count algorithm by using four synchronized methods: read_Object, write_Object, update_Object and done. These methods work with the ConcurrencyControl class to determine when the method may be completed without causing data corruption. They also work with the DeadLockDetection class to check for possible deadlock situations. read_Object determines if the ProtectedObject is safe to be read, by checking the current version. write_Object determines if the ProtectedObject is safe to be written to, by checking the current version. It will only allow a write operation if the version requested matches the current version. When it is finished, it will increment the version for the ProtectedObject. update_Object determines if the ProtectedObject is safe to be updated, implementing the version count algorithm. Like write_Object, the versions must match for an update to be completed. Upon completion, update_Object will also increment the version for the ProtectedObject. done is called in order to release the lock placed on a ProtectedObject by a read_Object, write_Object or update_Object operation.
As an example of how the version-count algorithm and the ProtectedObject methods work, consider an ATM scenario in which Bob is depositing $100 and Jane is requesting the current balance on their account. If the starting balance is $500, the transactions could take place in the following order:
Bob starts his transaction on version 1 of the balance (the ProtectedObject)
Jane starts her transaction on version 1 of the balance (the ProtectedObject)
Bob deposits $100 (writes to ProtectedObject)
and changes the balance to $600 and the version to 2
Jane tries to change the current balance (reads ProtectedObject)
on version 1 and cannot do so because it is not the correct
version.
In our DynAC model, the system would throw a CorruptedDataException here for the programmer to handle. However, in an actual banking system, if this occurred, Jane would probably never know. The system would recognize the new version and give her the new balance (perform a read_Object on ProtectedObject, version 2). The version-count algorithm enables the tracking of the current version of a ProtectedObject and the detection of data corruption by outside methods.
The DeadLockDetection Class
Deadlock is an event where threads hold resources demanded by other threads, resulting in cross dependencies. This leads to a situation where threads wait on each other and suspend actions forever. The DeadLockDetection class is meant to serve as a warning system to detect when these cyclical dependencies occur.
The current module to detect deadlock uses two assumptions about the ConcurrencyControl. The first assumption is that a thread can only be in the act of requesting one ProtectedObject at any time. The threads are not allowed to try to get permission for a ProtectedObject while they are waiting for the use of another ProtectedObject. The current implementation of ProtectedObject ensures this criterion.
The second assumption depends on the ConcurrencyControl class' behavior. When the ConcurrencyControl receives a request, it views the system's current state and returns a boolean depending on whether the thread can continue in that state. For a deadlock to be detected, ConcurrencyControl must turn down thread A only if thread B is using the resources thread A needs. In other words, a thread that is denied the use of a resource is waiting for the resource to be released by another thread. |
|
