Safe, Easy Resource Protection using POSIX Threads in C++

Abstract

The design and implementation of a correct threaded system is a difficult task. Novice parallel programmers often find it difficult to implement correct systems in serial languages because of the awkward syntax and the lack of debugging tools. This paper discusses an attempt to help protect beginning parallel programmers against common concurrent system errors. It describes Dynac++, a set of C++ objects that implements protections against two common concurrency anomalies: data corruption and deadlock.

Introduction

Threads are becoming an increasingly important part of software development. Programs that take advantage of threaded operating systems are increasingly important for optimizing use of system resources. POSIX threads implement some very low-level resource protection, but it is up to the programmer to know when to use these methods and how to properly employ them. The process of figuring out how to use this low-level protection can be a complex and tedious task. Figuring out when and how to protect data is difficult because it is necessary to think about programming in an entirely different paradigm. Programmers trained on serial systems can have difficulty visualizing and understanding parallel concepts and must learn how to think of a program in terms of several procedures running at the same time. The premise of the Dynac [1] project is that if a generalized, reliable set of methods were available to insure data correctness, developing threaded applications would be faster and easier, and less intimidating for the beginning threads programmer.

There are several aspects of POSIX threads that make their use difficult. One such aspect is the thread creation and manipulation syntax. Simply creating a simple threaded system with simple locks requires manual initialization and destruction for all components. While this gives the programmer a high degree of control, it can be confusing and tedious for beginners. Another area where POSIX threads is lacking is built-in resource protection. There is no standard method to prevent data corruption and deadlock, two major problems that are encountered in the implementation of parallel systems. When several different threads are dealing with the same set of data, there is potential for two threads to attempt to access the same piece of data at the same time in ways that will corrupt the data. A classic example is the ATM problem. Consider an example: Fred Madison and his wife Renee simultaneously decide that they need some cash. They both go to nearby ATMs. Fred places his card in the machine, and Renee does likewise. They both request a withdrawal, and their respective machines request an account balance from the bank's main computers. Both ATMs are informed that the Madisons have $700 in their checking account. Fred tells his ATM to give him $30, which the teller machine does and writes to the bank that the Madisons now have $670 in their account. Renee simultaneously withdraws $40, and her ATM tells the bank that they have $660 in their account. The net withdraw on their account is $70, but only $40 has been accounted for, due to data corruption. If we abstract Fred and Renee to threads and the bank's computer to a shared set of data, the need for resource protection becomes clear.

Data corruption can potentially go undetected until well after it has occurred. Deadlock, however, tends to become evident immediately. Deadlock occurs when two threads are both waiting for each other to be done with different pieces of data while holding locks on the data that the other thread is waiting for. For example, thread A begins with a lock on object 1. Thread B begins with a lock on object 2. Thread A requests a lock on object 2, and blocks since object 2 is already locked by Thread B. Now if Thread B, while still holding object 2 requested a lock on object 1, deadlock would occur. Neither thread would continue operation, since they would both be waiting for the other to release the lock. This cyclic dependency between threads halts operation and is known as deadlock.

In our paper we wish to outline the need for a system that would allow users to easily write threaded programs in C++, the current options available, and our implementation of the Dynac++ system. We will also discuss our performance testing and what could be done to improve our system.

Current State of the Art

POSIX threads are currently supported on most major operating systems. They contain a set of standardized functions which allows the user to create and destroy threads and locking mechanisms. However, these are not object oriented, and so, in order to stay cleanly within an OOP system, a C++ programmer would write their own class wrappers around the threads.

Many threaded applications are developed in C and C++. However, the languages were designed assuming a serial programming model. Parallel programming requires different methods of program design and implementation. These languages were not developed specifically to be used for parallel programming, so it is often awkward to apply parallel techniques. One solution to this problem has been under development at MIT. The Cilk project [2] focuses on developing a language based on C that is specifically designed for multithreaded parallel programming.

In 1997, a research group at Hope College took a different approach. Based on some algorithms designed by Jipping, this group coded Dynamic Anomaly Correction in Java [3]. This system is set up to make threaded programming less intimidating for beginners by taking care of the resource protection issues that are probably the most difficult aspect of threaded programming to become accustomed to. This system is implemented in Java, which has threads natively implemented in the language. Java has procedure-level protection using the "synchronized" keyword. The Dynac classes allowed for data-level protection, with each "protected object" having it's own internal locking mechanism. Using this package, Java programmers could design their programs to safely use threads with minimal effort.

A Model for Resource Protection

In his paper "Developing a Formal Model for Concurrent System Design", Jipping describes a General Process Model (GPM) system where a central concurrency control defines the behaviour of parallel processes. This control can be designed very abstractly, so that many different systems can use it, or very specifically as to optimize performance. Using this system, a programmer could quickly prototype a parallel system using an abstract concurrency control. Then, if necessary, the programmer could create or alter the concurrency control to work more optimally for his specific system. This type of abstraction can be especially beneficial for beginning parallel programmers, who might be willing to sacrifice a certain degree of control, in order to not have to deal with parallel problems such as deadlock and data corruption.

During the summer of 1997 a research team worked with Dr. Jipping to develop the Dynac System. As with Jipping's original system, Dynac had an abstract concurrency control class that could be used with a variety of concurrency controls. However, the Dynac system was developed with the intention of making Java threads programming easier and safer, rather than being a full parallel design system, as Jipping's GPM was designed to be.

Dynac++

The new Dynac++ system is implemented in C++. It consists of many of the same classes as the old Dynac system, with a few alterations for the transition from Java to C++, as well as some corrections on the DeadLockDetection module. Since C++ does not contain a native threads class, a SafeThread class was created to encapsulate it. A protected object (PObject) class was also designed for use with SafeThread. POSIX Threads were used in the Dynac++ implementation to ensure cross-platform compatibility.

The PObject class is the central class of the Dynac++ system. It contains methods for data/thread interaction, as well as an internal version table to ensure data correctness as threads request access. A user would descend their data object class from PObject, and then use the appropriate methods to communicate thread actions upon it. When the user initializes the PObject, they are required to register the PObject with a concurrency control. The PObject will keep a pointer to this control so that it can communicate with it when requests are made, and it also registers itself with the control to receive a unique ID, for tracking that object's dependencies.

The methods implemented in the PObject are read() for a reader request, write() for a writer request, and done() to release any outstanding requests. When these methods are called, the PObject will return 1 if access has been granted or a 0 if access has been denied due to denial of the request from the concurrency control. In addition to the concurrency control communication, the PObject keeps an internal table of versions for each thread. Any time a write() request is granted, a version counter is incremented, meaning that the PObject's internal data could potentially have been changed. A thread that was granted a read lock on a PObject with version 4, but then asked for a write lock when the version was 6 would receive a corrupted data error, since it would be trying to overwrite a new version of the PObject.

The SafeThread class is the class with which the user/programmer has the most direct interaction, as is seen in figure 1. SafeThread encapsulates a standard POSIX p_thread, providing methods for the object for creation and joining, as well as methods for interaction with Protected Objects. It is modeled after the Java Thread class, and uses a similar style where the user descends their class from the thread class for operation.

When the user initializes a SafeThread, he or she can register it with a concurrency control that they select. The concurrency control will assign a unique ID to that thread which the ConcControl and PObject classes will use to keep track of thread information. The SafeThread also contains the read(), write(), and done() methods, which are the user's primary means of communicating with the PObject. These methods take a PObject as their single parameter, and communicate to that PObject the Thread's unique ID. The PObject, in turn, then communicates this information as well as its own unique ID to the concurrency control, which uses a set of specific algorithms to decide if and when the thread should be granted access to the Object.

Figure 1: Relationships between Dynac++ Objects

The ConcControl class is an abstract class, from which a variety of concurrency controls are descended. The ConcControl class contains the read(), write(), and done() methods as well, but these methods contain specific information for the Thread and PObject involved. The three most important specific instances of the ConcControl class are Dynamic, Conservative, and Single-Writer-Multiple-Reader. Other instances of ConcControl could be created by a programmer to provide fine-grain control of a specific system.

The Dynamic class is descended from ConcControl and implements the simplest form of control: no control. Being purely dynamic, the Dynamic class grants all requests that are made upon it. The logic behind this is that the user is using the PObject's internal algorithm to detect data corruption to ensure data, rather than locking threads to try and protect the data. In this system, the user would be more interested in correcting data when an error occurs than preventing corruption. The potential benefit of using a purely dynamic control is that no locking occurs, which means that performance will be uninhibited by blocking threads.

On the opposite end of the spectrum is the Conservative class. Conservative is a strict conservative implementation of ConcControl where only one thread is allowed to have a read or write lock on a PObject at one time. This is the "safest" of concurrency controls, since each thread has solitary access. However, Conservative is also the most detrimental to performance since even threads that only require reading locks, which could be granted simultaneously, are given exclusive access to the PObject.

Between these two controls is the Single-Writer-Multiple-Reader class. This class allows multiple reader locks to be granted simultaneously, while writer locks must be made exclusive to any other lock. Reader locks are granted if there are no outstanding writer locks or requests, and writer locks are granted if there are no outstanding reader locks, and only one writer lock may be granted at a time. When a writer request is made, all reader requests are blocked, and then the writer lock is granted when there are no outstanding reader locks left. This compromise between dynamic and conservative concurrency controls allows a degree of freedom to enhance performance, without leaving the object unprotected.

Both Conservative and SWMR, which have forms of conservative locking mechanisms, use the DeadlockDetect class. The DeadlockDetect class is called by these concurrency controls whenever a strict conservative lock is granted. The module keeps a chart of Threads and their Object dependencies, to make sure that the requested lock would not cause a deadlock situation. If a deadlock situation would occur, the deadlock module returns an error and the request is not granted.

The idea of deadlock detection is to find cyclic dependencies between threads. The DeadlockDetect module accomplishes this through keeping two tables: a thread request table, and an object lock table. Whenever a request for a conservative lock on an Object is made, the object lock table is checked as to whether any threads already have locks on that object. If the object is unlocked, the thread's ID is inserted into the object lock table, and access is granted. If the object is locked, the thread request table is accessed to see if the thread holding the lock has any outstanding requests. If it does, the object lock table is accessed again for this requested object. This continues until DeadlockDetect traces the dependency to a thread with no outstanding requests, or the object lock table points to the thread itself. In the former case, the threads request is inserted in the thread request table. In the latter, a deadlock situation has occurred and the DeadlockDetect module sends an error back to the concurrency control.

A classic example of a potential deadlock situation is the Dining Philosophers problem. In this problem we have five philosophers sitting around a table, with five forks, one between each philosopher. In order to dig in to the heaping piles of spaghetti on their plates, each philosopher must have two forks. The problem is to let all the philosophers eat (sharing the fork resources), and think. An incorrect solution to this problem would be to have each philosopher grab their right fork, then have each philosopher grab their left fork. If each philosopher were to grab their right fork at the same time, there would be no forks on the table, so no one could eat. This is a cyclic dependency, and a deadlock situation. For an example of a correct solution to the dining philosophers problem see Tannenbaum [4].

However, with the introduction of the DeadlockDetect class, that incorrect answer becomes feasible. Consider this algorithm for the Philosophers:

pick up my right fork
pick up my left fork
if left fork returned deadlock, drop forks and go to beginning
eat
drop forks
think
go to beginning

Since the philosophers' threads can detect deadlock, the programmer can take advantage of it and wait to prevent deadlock until it is about to occur.

Performance Data

Performance improvements have been made from the Dynac++ system over the Dynac system. Many inefficiencies in the code were revised with the translation in to C++ especially in the DeadlockDetect module. Whereas Dynac took a noticeable performance hit with deadlock detection engaged, for Dynac++ the difference in run-time testing was negligible.

There is still a significant decrease in performance when using the Dynac system as opposed to a specifically designed algorithm as is shown in figure 2. For this test we implemented Tannenbaum's solution to the dining philosopher's problem using POSIX threads and locks, and we also implemented it using Tannenbaum's solution, but relying on the Dynac system for conservative locking. These real time tests were made on a Sparc Ultra 1 running Solaris 2.6.

Figure 2: Real Time Comparison of Dining Philosopher Test
(10000 eat/think cycles per Philosopher)

The performance detriment was anticipated, since every resource access (6 per cycle) must call several functions to chart versions, anticipate deadlock, etc. in the Dynac model, whereas in Tannenbaum's model a simple lock/unlock call is made. However, this is considered an acceptable loss since beginning parallel programmers are typically not interested in writing performance-intensive threaded applications, as much as easily learning the concepts of threaded programming.

Conclusions

In our paper we have discussed some concerns and difficulties novice parallel programmers have had using POSIX threads in C++. We addressed how the Dynac++ system deals with these issues, the implementation of Dynac++, as well as the tradeoffs for using an abstracted system.

In the future, Dynac++ could be developed into a more fully-featured set of C++ classes to aid in parallel programming. More specific concurrency controls could be added, as well as mechanisms for developing more complex systems within the Dynac framework.

Bibliography

1. VanEngen, Anita J. Bradshaw, Michael K. Oostendorp, Nathan. "Extending Java to Support Shared Resource Protection and Deadlock Detection in Threads Programming"
2. Leiserson, Charles E. The Cilk Project. http://theory.lcs.mit.edu/~cilk/
3. Jipping, Michael J. "Developing a Formal Model for Concurrent System Design"
4. Tannenbaum, A.S., Operating Systems: Design and Implementation , Prentice-Hall, 1987.

See http://www.cs.hope.edu/dynac++