\markboth{Shih}{Shih}
%%%%%% TEMPLATE.TEX for WISR'93, version 1.2, 4/22/93 %%%%%%

\documentstyle[11pt]{article}
\oddsidemargin 0.26in
\evensidemargin 0.26in
\topmargin -1.00in
\headheight .00in
\headsep .75in
\footheight 12.0pt
\footskip 25.0pt
\textheight 9.425in
\textwidth 6.5in

\markboth{Shih}{Shih}
\pagestyle{myheadings}

\parindent=0pt
\parskip=10pt

\def\@maketitle{\vbox to 2.6in{\hsize\textwidth
     \linewidth\hsize \vfil \centering
     {\large \@title \par}
     \vskip 2em
     {\normalsize
     \begin{tabular}[t]{c}\@author
     \end{tabular}\par}
     \vfil}
}

\begin{document}

\bibliographystyle{ieeetr}

\title{Introducing Synchronization into an Object-Oriented Reuse Library}

\author
{Yunyau Shih\\ 
\\
Department of Computer Science\\
Thomas J. Watson School of Engineering and Applied Science\\
Binghamton University, Binghamton NY 13902-6000\\
Phone: (607)777-4802, Fax: (607)777-4822\\
Email: yunyau@bingsuns.cc.binghamton.edu\\
\\
Les Lander \\ 
\\
Department of Computer Science\\
Thomas J. Watson School of Engineering and Applied Science\\
Binghamton University, Binghamton NY 13902-6000\\
Phone: (607)777-2309, Fax: (607)777-4822\\
Email: lander@bingsuns.cc.binghamton.edu
}


\date{}

\maketitle

\begin{abstract}
We discuss how to build an object-oriented software reuse library
emphasizing the inclusion of synchronization constructs and seeking 
to overcome the conflict between synchronization and inheritance. 
Several synchronization primitives and concurrency control policies
which permit automatic synthesis are presented. A preliminary scheme for 
component classification, based on synchronization properties, is 
also proposed.
\end{abstract}

\vspace{0.2in}
\noindent 
{\bf Keywords:} Concurrency, Object-oriented, Reuse library, 
Synchronization.

\vspace{0.2in}
\noindent 
{\bf Workshop Goals:} Discuss approaches to including 
synchronization in object-oriented reusable components.

\vspace{0.2in}
\noindent
{\bf Working Groups:} Reuse and OO Methods and Tools and 
Environments


\newpage

\vspace{0.2in}

\section{Background}

Software reuse has been advocated as a means for overcoming
the software crisis \cite{Krueger92}. Software reuse can be divided
into two categories--horizontal reuse and vertical reuse \cite{Shih93b}: 
horizontal reuse refers to building and using a component so that it 
can itself continue to evolve for other applications, 
by parameterization or otherwise. On the other hand, when reuse is
effected using inheritance and without changing existing classes, 
thereby creating class hierarchies, it is called a vertical reuse.

There are many reuse-based systems available commercially or in 
research environments \cite{Levine93}. However most of them target
code for sequential execution. In this position paper we focus
on vertical reuse, especially for an object-
oriented software reuse library, which emphasizes concurrency. 
We believe that vertical reuse is better
than horizontal reuse because existing components are not
modified and remain validated as the system evolves.

When a reuse library for a concurrent object-oriented
software is established, inheritance has to be considered.
Nevertheless, synchronization is not orthogonal to inheritance
\cite{Wegner87}. In a concurrent object-oriented language,
synchronization mechanisms can be divided into two categories 
\cite{Shih92}: {\em object-level} and {\em in-code}. 
``Object-level'' synchronization
regulates the invocations of methods (operations) based on the
current state of an object. That is, the object-level
synchronization mechanism is like a gatekeeper which is global to
the entire object. ``In-code'' synchronization is the one where the
traditional synchronization mechanisms (semaphore, fork, etc) are
used and the synchronization is scattered in the code of the
methods. In-code synchronization is error prone and we will not
pursue it. Although object-level mechanisms can also be divided
into several approaches, most of them produce some kind of
conflict with inheritance \cite{Kafura89}. Frequently, methods
inherited from a superclass have to be re-coded in the subclass in
order to achieve synchronization between the methods from the
superclass and the new methods of the inherited class. Such
problems are counterproductive in software development.

The basic problem can be described as follows. When a class P
is defined, the synchronization specification is based on the
methods existing in class P. When a subclass, Q, is defined and a
new method {\em m} is added, the synchronization in the superclass P may
not be compatible with the new method {\em m} because the original
relationships may conflict with the new method. An example, which
is used quite often in the literature 
\cite{Decouchant89,Kafura89,Neusius91,Tomlinson89}, is described as
follows. Suppose a direct superclass implements a queue with the
standard operations ``Get'' and ``Put.'' Now, if we wish to use
inheritance to add a new method called ``Get2,'' which fetches two
elements atomically, the synchronization defined in the parent is
not quite right because ``Get2'' is not defined there. Thus, when
``Get2'' is invoked, what is the relationship between ``Get2'' and the
other methods in the direct superclass P? No synchronization
information has been given (or can be given) in the superclass
because ``Get2'' does not exist there. Also, a programmer cannot
simply add synchronization information in the inherited class
because it will have to involve modifications to the
synchronization constructs of the superclass.

We will discuss how to build a concurrent object-oriented
software reuse library systematically from the synchronization
point of view in the remainder of the paper. We will also introduce
a model COORL to illustrate the discussion.

\section{Position}

\subsection{Basic Structure of the COORL Model}

To enhance software reuse we propose that an {\em abstract} component,
i.e. an abstract class, be the basic unit for software reuse. The
reason is twofold. First, it is not easy for people to become familiar
with a great variety of programming languages and a simple specification
language, free of implementation detail should be easy to learn. 
Second, it is intended
to generate the corresponding implementation classes automatically
using a translation tool. This kind of tool for translation is
quite common, e.g. \cite{Luqi89}. A high level structure for the two
classes is shown in Figure 1. Thus, in COORL, there are two kinds
of classes: {\em abstract} and {\em implementation}. 
An abstract class uses a
high level language such as a program design language (PDL) or a
specification language to describe its functionality abstractly
while an implementation class contains the specific programming
language source code for the corresponding abstract class which can
be compiled and executed.

\begin{center}
\begin{picture}(380,265)(0,0)
\put(270,240){\circle{50}}
\put(270,240){\makebox(0,0){Class A}}
\put(190,160){\circle{50}}
\put(190,160){\makebox(0,0){Class B}}
\put(110,80){\circle{50}}
\put(110,80){\makebox(0,0){Class C}}
\put(0,0){\dashbox{1}(100,15){C-Implementation-1}}
\put(0,15){\dashbox{1}(100,15){Option-1}}
\put(120,0){\dashbox{1}(100,15){C-Implementation-2}}
\put(120,15){\dashbox{1}(100,15){Option-2}}
\put(200,80){\dashbox{1}(100,15){B-Implementation}}
\put(200,95){\dashbox{1}(100,15){Option}}
\put(280,160){\dashbox{1}(100,15){A-Implementation}}
\put(280,175){\dashbox{1}(100,15){Option}}
\put(60,30){\vector(1,1){36}}
\put(160,30){\vector(-1,1){36}}
\put(240,110){\vector(-1,1){36}}
\put(320,190){\vector(-1,1){36}}
\put(125,95){\vector(1,1){50}}
\put(205,175){\vector(1,1){50}}
\end{picture}
\\ {\centering  {Figure 1}}
\end{center}


In Figure 1, Class X is an abstract class while X-Implementation-N is its
corresponding implementation class. N is an optional number or
other identifier and is used to enumerate different implementations
of Class X. There is an Option part accompanying each
implementation class. It may be used to store relevant information
such as a data structure. For example, Class A and Class B in
Figure 1 are abstract classes while A-Implementation, and
B-Implementation are their corresponding single implementation
classes. C-Implementation-1 and C-Implementation-2 are two
different implementation classes for Class C, which is an abstract
class. Option-1 and Option-2 could be two different kinds of data
structures for implementing Class C. For instance, Class C might be
a bounded buffer and then C-Implementation-1 might use an array to
implement Class C while C-Implementation-2 might use a linked list.
It is common for a reuse library to have a browser or other query
access system. When the browser or a query language is used to skim
a library built according to COORL, users primarily access abstract
classes. A sophisticated user can also request the different
options used to implement a specific abstract class but that is not
encouraged because such low level information should be shielded
from a user in general to promote encapsulation, not to mention
protecting the implementation code itself.

This paper focuses on a high level view on the synchronization
issue and ignores other aspects. An earlier version of COORL can be
found in \cite{Shih93a}.

\subsection{Synchronization Mechanism for a Reuse Library}

\subsubsection{General Structure}

An ideal, if not the best, synchronization mechanism for a
concurrent software reuse library, based on our experience, is a
declarative mechanism. Synchronization primitives for a
class should be placed in a predefined segment (or section) so
that it is easy to modify them for reuse. Thus, we use an object-level
synchronization mechanism in COORL. For example, see the
Control segments in Figure 2 (ignore the syntax for the time
being). Of course, when a declarative synchronization
mechanism is used, the primitives will inevitably lose some 
flexibility compared with the traditional synchronization
mechanisms, such as semaphore, fork, etc. But overall,
reusability increases, especially in our model when an abstract class
is the basic reuse unit.

There exist many declarative mechanisms for
concurrent object-oriented languages but many of them have the
same basic constructs, i.e. synchronization counters, such as
req(op), wait(op), start(op), exec(op), etc., where ``op'' represents an
invocation of a method. These kinds of primitives can be found in
Guide \cite{Decouchant89}, DRAGOON \cite{Atkinson91}, and Scheduling
Predicates \cite{McHale91}, etc.

In COORL, we can synthesize those synchronization counters
once a subclass has been defined. As long as the counters are
consistent, our primitives can be used to manipulate them and, at the
same time, to avoid the conflict between the synchronization 
and inheritance. In order to enhance the expressive power for
a declarative synchronization mechanism, we merge two other 
constructs, namely the {\em atomic block} and {\em transaction} concepts 
\cite{Kaiser90}, in the current version of COORL.

\subsubsection{Basic Synchronization Primitives}

In the first version of COORL \cite{Shih93a}, there are four
basic synchronization primitives used to construct a 
concurrent object-oriented software reuse library. 

\begin{itemize}

\item \#\{X\} Operator \#\{Y\}: X and Y are methods. \#\{X\} denotes the
number of invocation of X. ``Operator'' represents the relation
between the numbers of invocations of X and Y. ``Operator''
might be $=, >, <, \geq, \leq, $ etc. The symbol ``\#'' is simply
illustrative; finer levels of control can be used,
such as exec (X), term (X), act (X) used in Guide and DRAGOON.

\end{itemize}

The following three synchronization clauses are used to
reflect a new relationship when a new method is defined based on an
existing class.

\begin{itemize}

\item \{X\} = +\{Y\}: the symbol ``+'' means that method X and method
Y have the same effect on the class in terms of the number of
invocations of X and Y. ``+'' is the default and can be omitted,
see Figure 2(b).

\item \{X\} = - \{Y\}: on the other hand, ``-'' (i.e., minus)
indicates that X and Y will have opposite effects.
Conceptually, Get and Put can be denoted as \{Put\} = - \{Get\},
although this is not actually used in the example in Figure 2.

\item \{X\} = {\em n}\{Y\}: ``{\em n}'' is a number representing how many
invocations of method Y equate to the number of invocations of
X. For example, \{Get2\} = 2 \{Get\} indicates that method ``Get2''
has the effect of two invocations of method ``Get.'' 

\end{itemize}

\begin{center}
\begin{tabular}{lll|lll} \hline
\multicolumn{3}{l|}{Class P:} &\multicolumn{3}{l}{Class P:} \\
\multicolumn{3}{l|}{Control:} &\multicolumn{3}{l}{Control:} \\
&&\#Put $>$ \#Get &&&\#Put $>$ \#Get \\
\multicolumn{3}{l|}{Code:} &\multicolumn{3}{l}{Code:} \\ 
&\multicolumn{2}{l|}{Public:} &&\multicolumn{2}{l}{Public:} \\ 
& & Get\{...\}               & & & Get\{...\} \\
& & Put\{...\}               & & & Put\{...\} \\
&&&&& \\
\multicolumn{3}{c|}{(a) Class P} &&&\\
\cline{1-3} 
\multicolumn{3}{l|}{Class Q: Inherit P} &\multicolumn{3}{l}{Class Q: Inherit P} \\
\multicolumn{3}{l|}{Control:} &\multicolumn{3}{l}{Control:} \\ 
&&\{Put\} $=+$ \{Get\} &&&\#Put $>$ \#Get + \#Pop \\
\multicolumn{3}{l|}{Code:} &\multicolumn{3}{l}{Code:} \\ 
&\multicolumn{2}{l|}{Public:} &&\multicolumn{2}{l}{Public:} \\ 
& & Pop\{...\}               & & & Get \\
& &                          & & & Put \\
& &                          & & & Pop\{...\} \\
&&&&& \\
\multicolumn{3}{c|}{(b) Define Class Q} &\multicolumn{3}{c}{(c) Library after Class Q is generated} \\
\hline \\
\multicolumn {6} {c}{Figure 2}
\end{tabular}
\end{center}

The underlying system will generate a set of synchronization
clauses for a new class by interpreting the user's instructions.
The synchronization in Figure 2(c) provides an example; it is a
combination of the synchronization clauses in Figure 2(a) and
Figure 2(b). That is, ``\#\{Put\} $>$ \#\{Get\} + \#\{Pop\}'' 
can be obtained by
merging ``\#\{Put\} $>$ \#\{Get\}'' and ``\{Pop\} = +\{Get\}.''

In COORL the synchronization would be visible to users by
means of a browser or a keyword search (classification issues 
will be addressed in the next section) while the implementation of the
methods will be shielded from users because of encapsulation. It is useful
that the synchronization clauses of a class should be part of its
interface to (or contract with) its users. If only those synchronization
clauses which are added to a subclass Q of P were visible (which
corresponds to the traditional inheritance approach), then it is
possible that the full suite of active synchronization clauses would
become scattered throughout a class hierarchy and be extremely
difficult to understand as a whole.  Therefore, it should not be
considered a redundancy to make all the synchronization explicit in
each subclass. Besides, there is not much burden on the user
because the underlying system will generate the synchronization
clauses automatically as each new subclass is entered into the
library.

In COORL a second level of synchronization construct is
available. It is similar to the guard statement. Thus, apart from
the synchronization clauses described above, which certainly
provide an object level synchronization mechanism and handle the
overall relationships between methods, a guard statement may be
attached to a method, if necessary. Though a guard is somewhat at
the method level, it is not scattered inside the code of a method
and can be managed easily. The most significant difference between
these two mechanisms is that state variables are involved in this
second kind of synchronization mechanism. For instance, method
``Put'' in a class defining a queue should not be invoked unless
there is an empty space left.  This information will be reflected
in the guard statement for method ``Put,'' not in the object-level
synchronization clauses
which are enforced by a Control segment. For a detailed description
and examples for the second level synchronization construct, please
refer to \cite{Shih93a}. This distinction is adopted to enforce the
encapsulation principle for object-orientation.

\subsubsection{Concurrency Policy}

Synchronization and concurrency are different faces of the same coin.
Basically there are two points of view concerning concurrency. 
One point of view is that concurrency should be identified implicitly, 
e.g., a compiler might be used to detect any parallelism available for
a program in a specific hardware environment.  Though it is quite
successful in some specific applications, this approach is a
great challenge for a compiler in general applications. 
The other point of view is that programmer annotations are needed to
exploit possible concurrency in general programs, 
at least the programmer must
be provided with constructs that express concurrency in order to add
optional variants, extensions or improvements to what a 
compiler might provide automatically.

We are investigating what concurrency policies are
appropriate to be indicated explicitly, while we include atomic
block and transaction policies in our current version of COORL. The
keyword {\em Atomic} and {\em Transaction} 
are used in the control segment to
indicate the execution sequence. When no concurrency policy is
indicated, the methods in an object can be executed
concurrently. Of course, that also depends on the underlying hardware
environments. When a method, which is declared to be ``atomic,'' is
executed, other methods in the same object will be suspended.
``Transaction'' is used by one object to inform other objects 
to block other invocations until it returns
the results from a method which is
identified as a transaction method. ``Transaction'' is a very strict
policy. 

We notice that some existing concurrency policies are too rigid. We
would like to merge data flow and atomic concepts to
increase parallelism. Thus, an atomic method might suspend some
methods based on the data flow relationship, but not block all the
others.


\subsection{Classification Scheme for Locating and Retrieving}

Our classification scheme follows Prieto-Diaz's approach
\cite{Prieto-Diaz87} but in COORL we define another ``facet'' for
synchronization. The introduction of the new facet is justified 
as follows. It is possible for a
set of the same methods to be regulated by different synchronization
requirements. Though it is possible to be distinguished by the
Medium facet \cite{Prieto-Diaz87}, it is desirable to add a
synchronization facet because synchronization is an important
characteristic for a concurrent software library. If we could define
a good domain for the facet, search-time in the library would 
be cut down dramatically.

It is possible for the synchronization facet to be activated
by two approaches. One is by some predefined keywords; the other is
by the synchronization primitives described in the previous
section. The latter is not encouraged because it violates
encapsulation. Some predefined keywords could be as follows:
Space, Time, Order, Priority by X (X could be time, length, ...),
FIFO, LIFO, Descending, and Ascending. We are in the process of
studying a more structured keyword representation.


\section{Comparison}

We discussed how to build a concurrent object-oriented
software reuse library and a scheme to classify a reuse component from
the synchronization point of view. We have explored these issues
using the COORL model. We believe the approach is better than only 
developing a new language as in 
\cite{Atkinson91,Decouchant89,Kafura89,Neusius91} 
because of the conflict between
inheritance and synchronization.
With our approach a concurrent object-oriented
software reuse library can be built without the conflict. 

With respect to concurrency policy, 
even though similar concepts are adopted in Meld
\cite{Kaiser90}, reuse is not a concern there. Therefore, code
tracing and code modification are often needed when new methods
are added to an existing class to obtain a subclass. This approach 
violates encapsulation. We argue for putting the 
concurrency policies in the control segment, thus conforming
our placement of synchronization primitives.

Our classification scheme for a reuse library
follows Prieto-Diaz's approach
\cite{Prieto-Diaz87} but we argue for defining another ``facet'' for
synchronization in subsection 2.4.

Our approach will enhance reusability by being 
easy to access, understand, and modify. With synchronization
primitives and concurrency policies expressed in the control segment,
software reuse can be improved.

\bibliography{shih}


\section*{Biography}

{\bf Yunyau Shih} is a Ph.D. student in the Department of Computer
Science at Binghamton University in New York. He graduated from the Tunghai
University in Taiwan and also has an MS from Binghamton. For his Dissertation
he is working on object-oriented reuse libraries with an emphasis
on the inclusion of constructs for synchronization.
 
{\bf Les Lander} is a faculty member of the Department of Computer
Science at Binghamton University. He obtained his BA at the University
of Cambridge and his MS and PhD in mathematics
from the University of Liverpool, U.K. His interests include programming
languages and software engineering and he also works on expert sytems and
system-level fault location. He chairs the ACM SIGAda Local Chapter 
for the Binghamton/Owego area.

\end{document}


