home *** CD-ROM | disk | FTP | other *** search
/ ftp.umcs.maine.edu / 2015-02-07.ftp.umcs.maine.edu.tar / ftp.umcs.maine.edu / pub / WISR / wisr6 / proceedings / ascii / shih.ascii < prev    next >
Text File  |  1993-10-19  |  26KB  |  518 lines
  1.  
  2.  
  3.  
  4.  
  5. Introducing  Synchronization  into  an Ob ject-Oriented Reuse  Library
  6.  
  7.  
  8.  
  9.                                                       Yunyau Shih
  10.  
  11.  
  12.  
  13.                                         Department of Computer Science
  14.  
  15.                     Thomas J. Watson School of Engineering andApplied Science
  16.  
  17.                            Binghamton University, Binghamton NY 13902-6000
  18.  
  19.                                   Phone:  (607)777-4802, Fax:  (607)777-4822
  20.  
  21.                                 Email:  yunyau@bingsuns.cc.binghamton.edu
  22.  
  23.  
  24.  
  25.                                                        Les Lander
  26.  
  27.  
  28.  
  29.                                         Department of Computer Science
  30.  
  31.                     Thomas J. Watson School of Engineering andApplied Science
  32.  
  33.                            Binghamton University, Binghamton NY 13902-6000
  34.  
  35.                                   Phone:  (607)777-2309, Fax:  (607)777-4822
  36.  
  37.                                  Email: lander@bingsuns.cc.binghamton.edu
  38.  
  39.  
  40.  
  41.                                                          Abstract
  42.  
  43.  
  44.            We discuss how to build an object-oriented software reuse library emphasizing the inclusion
  45.        of synchronization constructs and seeking to overcome the conflict between synchronization and
  46.        inheritance.  Several synchronization primitives and concurrency control policies which permit
  47.        automatic synthesis are presented. A preliminary scheme for component classification, based on
  48.        synchronization properties, is also proposed.
  49.  
  50.  
  51.  
  52. Keywords: Concurrency, Object-oriented, Reuse library, Synchronization.
  53.  
  54.  
  55.  
  56. Workshop Goals:  Discuss approaches to including synchronization in object-oriented reusable
  57. components.
  58.  
  59.  
  60.  
  61. Working Groups: Reuse and OO Methods and Tools and Environments
  62.  
  63.  
  64.  
  65.                                                           Shih- 1
  66.  
  67.  
  68. 1      Background
  69.  
  70.  
  71.  
  72. Software reuse has been advocated as a means for overcoming the software crisis [1].  Software reuse
  73. can be divided into two categories-horizontal reuse and vertical reuse [2 ]: horizontal reuse refers
  74. to building and using a component so that it can itself continue to evolve for other applications,
  75. by parameterization or otherwise. On the other hand, when reuse is effected using inheritance and
  76. without changing existing classes, thereby creating class hierarchies, it is called a vertical reuse.
  77.  
  78.  
  79. There are many reuse-based systems available commercially or in research environments [3].  How-
  80. ever most of them target code for sequential execution. In this position paper we focus on vertical
  81. reuse, especially for an object- oriented software reuse library, which emphasizes concurrency. We
  82. believe  that  vertical  reuse  is  better  than  horizontal reuse  b ecause  existing  components  are  not
  83. modified and remain validated as the system evolves.
  84.  
  85.  
  86. When a reuse library for a concurrent object-oriented software is established,  inheritance has to
  87. be considered.  Nevertheless, synchronization is not orthogonal to inheritance [4].  In a concurrent
  88. object-oriented language, synchronization mechanisms can be divided into two categories [5]: object-
  89. level and in-code. "Object-level" synchronization regulates the invocations of methods (operations)
  90. based on the current state of an object. That is, the object-level synchronization mechanism islike
  91. a gatekeeper which is global to the entire object. "In-code" synchronization is the one where the
  92. traditional synchronization mechanisms (semaphore,fork, etc) are used and the synchronization is
  93. scattered in the code of the methods. In-code synchronization is error prone and we will not pursue
  94. it.  Although object-level mechanisms can also be divided into several approaches, most of them
  95. produce some kind of conflict with inheritance [6]. Frequently, methods inherited from a superclass
  96. have to be re-coded in the subclass in order to achieve synchronization between the methods from
  97. the superclass and the new methods of the inherited class. Such problems are counterproductive
  98. in software development.
  99.  
  100.  
  101. The basic problem can be described as follows.  When a class P is defined, the synchronization
  102. specification  is  based  on  the  methods  existing  in  class  P.  When  a  subclass,  Q,  is  defined  and  a
  103. new  method  m  is  added, the  synchronization  in  the  superclass  P may  not  be  compatible  with
  104. the  new  method  m  because  the  original  relationships  may  conflict  with  the  new  method.   An
  105. example, which is used quite often in the literature [7, 6 , 8 , 9 ], is described as follows.  Suppose
  106. a  direct  superclass  implements  a  queue  with  the  standard  operations  "Get"  and  "Put."   Now,
  107. if  we  wish  to  use  inheritance  to  add  a  new  method  called  "Get2,"  which  fetches  two  elements
  108. atomically, the  synchronization  defined  in  the  parent  is  not  quite  right  b ecause  "Get2"  is  not
  109. defined there.  Thus, when "Get2" is invoked, what is the relationship between "Get2" and the
  110. other methods in the direct superclass P? No synchronization information has been given (or can
  111. be given) in the superclass because "Get2" does not exist there. Also, a programmer cannot simply
  112. add synchronization information in the inherited class because it will have to involve modifications
  113. to the synchronization constructs of the superclass.
  114.  
  115.  
  116. We will discuss how to builda concurrent object-oriented software reuse library systematically from
  117. the synchronization point of view in the remainder of the paper. We will also introduce a model
  118. COORL to illustrate the discussion.
  119.  
  120.  
  121.  
  122.                                                           Shih- 2
  123.  
  124.  
  125. 2      Position
  126.  
  127.  
  128.  
  129. 2.1     Basic Structure of the COORL Model
  130.  
  131.  
  132.  
  133. To enhance software reuse we propose that an abstract component, i.e.  an abstract class, be the
  134. basic  unit  for  software  reuse.  The  reason  is  twofold.  First, it  is  not  easy  for  people  to  become
  135. familiar with a great variety of programming languages and a simple specification language, free of
  136. implementation detail should be easy to learn. Second, it is intended to generate the corresponding
  137. implementation classes automatically using a translation tool. This kind of tool for translation is
  138. quite common, e.g.  [10 ].  A high level structure for the two classes is shown in Figure 1.  Thus, in
  139. COORL, there are two kinds of classes: abstract and implementation.  An abstract class uses a high
  140. level language such as a program design language (PDL) or a specification language to describe its
  141. functionality abstractly while an implementation class contains the specific programming language
  142. source code for the corresponding abstract class which can be compiled and executed.
  143.  
  144.  
  145.  
  146.                                                             '         $
  147.  
  148.  
  149.                                                                                 Class A
  150.  
  151.                                                                                &%
  152.                                                                                         @I@
  153.                                                                                              @
  154.                                                                                        ____________________________________________*
  155.  *_______________@
  156.                                       '          $                                     ____________________________________________*
  157.  *_______________@
  158.                                                                                        ____                       ____
  159.                                                                                        ___A-Implementation        ___
  160.                                                           Class B                      ____________________________________________*
  161.  *_______
  162.  
  163.                                                           &%
  164.                                                                    @@I
  165.                                                                        @
  166.                                                                   ___________________________________________________________@
  167.                  '         $                                      _________________________________________________________________*
  168.  *_______________@
  169.                                                                   ____                      ____
  170.                                                                   ___B-Implementation       ___
  171.                                      Class C                      ___________________________________________________
  172.  
  173.                                     &%
  174.                                              @I@
  175.                                                   @
  176.             ______________________________________________________________________________________________________________________@
  177.  
  178.             ______________________________________________________________________________________________________________________O*
  179.  *ption-1________@
  180.  
  181.             ___________________________________________________________C-Implementation-1__________________________________________*
  182.  *_______________@
  183.                                                           Figure 1
  184.  
  185.  
  186.  
  187. In  Figure  1, Class  X  is  an  abstract  class  while  X-Implementation-N  is  its  corresponding  imple-
  188. mentation class.  N is an optional number or other identifier and is used to enumerate different
  189. implementations of Class X. There is an Option part accompanying each implementation class. It
  190. may  be  used  to  store  relevant  information  such  as  a  data  structure.  For  example, Class  A and
  191. Class B in Figure 1 are abstract classes while A-Implementation, and B-Implementation are their
  192. corresponding single implementation classes. C-Implementation-1 and C-Implementation-2 are two
  193. different implementation classes for Class C, which is an abstract class.  Option-1 and Option-2
  194. could be two different kinds of data structures for implementing Class C. For instance, Class C
  195. might be a bounded buffer and then C-Implementation-1 might use an array to implement Class
  196. C while C-Implementation-2 might use a linked list.  It is common for a reuse library to have a
  197. browser or other query access system.  Whenthe browser or a query language is used to skim a
  198. library built according to COORL, users primarily access abstract classes.  A  sophisticated user
  199.  
  200.  
  201.                                                           Shih- 3
  202.  
  203.  
  204. can also request the different options used to implement a specific abstract class but that is not
  205. encouraged because such low level information should b e shielded from a user in general to promote
  206. encapsulation, not to mention protecting the implementation code itself.
  207.  
  208.  
  209. This paper focuses on a high level view on the synchronization issue andignores other aspects.  An
  210. earlier version of COORL can be found in [11 ].
  211.  
  212.  
  213.  
  214. 2.2     Synchronization Mechanism for a Reuse Library
  215.  
  216.  
  217.  
  218. 2.2.1     General Structure
  219.  
  220.  
  221.  
  222. An ideal, if not the best, synchronization mechanism for a concurrent software reuse library, based
  223. on our experience, is a declarative mechanism.  Synchronization primitives fora class should be
  224. placed in a predefined segment (or section) so that it is easy to mo dify them for reuse.  Thus, we
  225. use an object-level synchronization mechanism in COORL. For example, see the Control segments
  226. in Figure 2 (ignore the syntax for the time being). Of course, when a declarative synchronization
  227. mechanism  is  used, the  primitives  will  inevitably  lose  some  flexibility  compared  with  the  tradi-
  228. tional synchronization mechanisms,such as semaphore, fork, etc. But overall, reusability increases,
  229. especially in our model when an abstract class is the basic reuse unit.
  230.  
  231.  
  232. There  exist  many  declarative  mechanisms  for  concurrent  object-oriented  languages  but  many  of
  233. them  have  the  same  basic  constructs, i.e.  synchronization  counters, such  as  req(op),  wait(op),
  234. start(op), exec(op), etc., where "op" represents an invocation of a method.  These kindsof primitives
  235. can be found in Guide [7], DRAGOON [12 ], and Scheduling Predicates [13 ], etc.
  236.  
  237.  
  238. In COORL, we can synthesize those synchronization counters once a subclass has been defined.
  239. As long as the counters are consistent, our primitives can be used to manipulate them and, at the
  240. same time, to avoid the conflict between the synchronization and inheritance. In order to enhance
  241. the expressive power for a declarativesynchronization mechanism, we merge two other constructs,
  242. namely the atomic block and transactionconcepts [14 ], in the current version of COORL.
  243.  
  244.  
  245.  
  246. 2.2.2     Basic Synchronization Primitives
  247.  
  248.  
  249.  
  250. In the first version of COORL [11], there are four basic synchronization primitives used to construct
  251. a concurrent object-oriented software reuse library.
  252.  
  253.  
  254.  
  255.     ffl#fXg  Operator  #fYg:  X  and  Y  are  methods.   #fXg  denotes  the  number  of  invocation
  256.        of  X.  "Operator"  represents  the  relation  between  the  numbers  of  invo cations  of  X  and  Y.
  257.        "Operator" might be =; >; <; ; ; etc. The symbol "#" is simply illustrative; finer levels of
  258.        control can be used, such as exec (X), term (X), act (X) used in Guide and DRAGOON.
  259.  
  260.  
  261.  
  262. The  following  three  synchronization  clauses  are  used  to  reflect  a  new  relationship  when  a  new
  263. method is defined based on an existing class.
  264.  
  265.  
  266.  
  267.     fflfXg = +fYg:  the symb ol"+" means that method X and method Y have the same effect on
  268.        the class in terms of the number of invocations of X and Y. "+" is the default and can be
  269.        omitted, see Figure 2(b).
  270.  
  271.  
  272.                                                           Shih- 4
  273.  
  274.  
  275.     fflfXg = - fYg:  on the other hand, "-" (i.e., minus) indicates that X and Y will have opposite
  276.        effects.  Conceptually, Get and Put can be denoted as fPutg = - fGetg, although this is not
  277.        actually used in the example in Figure 2.
  278.  
  279.  
  280.     fflfXg = nfYg:  "n" isa number representing how many invocations of method Y equate to the
  281.        number of invocations of X. For example, fGet2g = 2 fGetg indicates that metho d "Get2"
  282.        has the effect of two invocations of method "Get."
  283.  
  284.  
  285.                        _________________________________________________________________________________
  286.                         Class P:                 _   Class P:
  287.                         Control:                 _   Control:
  288.                            #Put > #Get      _            #Put > #Get
  289.                         Code:                    _   Code:
  290.                           Public:                 _    Public:
  291.                            Getf...g               _      Getf...g
  292.                            Putf...g               _      Putf...g
  293.  
  294.                                                     _
  295.                        _______(a)_Class_P___________
  296.                         Class Q: Inherit P    _      Class Q: Inherit P
  297.                         Control:                 _   Control:
  298.                            fPutg = + fGetg  _            #Put > #Get + #Pop
  299.                         Code:                    _   Code:
  300.                           Public:                 _    Public:
  301.                            Popf...g              _       Get
  302.  
  303.                                                     _    Put
  304.                                                     _    Popf...g
  305.                                                     _
  306.                        __(b)_Define_Class_Q__________(c)_Library_after_Class_Q_is_generated_____________
  307.  
  308.  
  309.  
  310.                                                           Figure 2
  311.  
  312.  
  313.  
  314. The underlying system will generate a set of synchronizationclauses for a new class by interpreting
  315. the user's instructions. The synchronization in Figure 2(c) provides an example;it is a combination
  316. of  the  synchronization  clauses  in  Figure  2(a)  and  Figure  2(b).   That  is, "#fPutg  >  #fGetg  +
  317. #fPopg" can be obtained by merging "#fPutg > #fGetg" and "fPopg = +fGetg."
  318.  
  319.  
  320. In COORL the synchronization would be visible to users by means of a browser or a keyword search
  321. (classification issues will be addressed in the next section) while the implementation of the methods
  322. will be shielded from users because of encapsulation. It is useful that the synchronization clauses of
  323. a class should be part of its interface to (or contract with)its users.  If only those synchronization
  324. clauses which are added to a subclass Q of P were visible (which corresponds to the traditional
  325. inheritance approach), then it is possible that the full suite of active synchronization clauses would
  326. become scattered throughout a class hierarchy and be extremely difficultto understand as a whole.
  327. Therefore, it should not be considered a redundancy to make all the synchronization explicit in
  328. each subclass.  Besides, there is not much burden on the user because the underlying system will
  329. generate the synchronization clauses automatically as each new subclass is entered into the library.
  330.  
  331.  
  332. In  COORL a  second  level  of  synchronization  construct  is  available.   It  is  similar  to  the  guard
  333. statement. Thus, apart from the synchronization clauses described above, which certainly provide
  334. an object level synchronization mechanism and handle the overall relationships between methods,
  335. a guard statement may be attached to a method, if necessary. Though a guard is somewhat at the
  336.  
  337.  
  338.  
  339.                                                           Shih- 5
  340.  
  341.  
  342. method level, it is not scattered inside the code of a method and can be managed easily.  The most
  343. significant difference between these two mechanisms is that state variables are involved in this second
  344. kind of synchronization mechanism. For instance,method "Put" in a class defining a queue should
  345. not be invoked unless there is an emptyspace left.  This information will be reflected in the guard
  346. statement for method "Put," not in the object-level synchronization clauses which are enforced by
  347. a Control segment.  For a detailed description and examples for the second level synchronization
  348. construct, please refer to [11 ].  This distinction is adopted to enforce the encapsulation principle
  349. for object-orientation.
  350.  
  351.  
  352.  
  353. 2.2.3     Concurrency Policy
  354.  
  355.  
  356.  
  357. Synchronization  and  concurrency  are  different faces  of  the  same  coin.   Basically  there  are  two
  358. points of view concerning concurrency. One point of view is that concurrency should be identified
  359. implicitly,  e.g.,  a compiler might be used to detect any parallelism available for a program in a
  360. specific  hardware  environment.  Though  it  is  quite  successful  in  some  specific  applications,  this
  361. approach is a great challenge for a compiler in general applications.  The other point of view is
  362. that programmer annotations are needed to exploit possible concurrency in generalprograms,  at
  363. least the programmer must be provided with constructs that express concurrency in order to add
  364. optional variants, extensions or improvements to what a compiler might provide automatically.
  365.  
  366.  
  367. We  are  investigating  what  concurrency  policies  are  appropriate  to  be  indicated  explicitly, while
  368. we include atomic block and transaction policies in our current version of COORL. The keyword
  369. Atomic and Transaction are used in the control segment to indicate the execution sequence. When
  370. no  concurrency  policy  is  indicated, the  methods  in  an  object  can  be  executed  concurrently.  Of
  371. course,  that  also  dep ends  on  the  underlying  hardware  environments.   When  a  method, which
  372. is  declared  to  be  "atomic,"  is  executed,  other  methods  in  the  same  object  will  be  suspended.
  373. "Transaction"  is  used  by one  ob ject  to  inform  other  ob jects  to  blo ck  other  invocations  until  it
  374. returns the results from a method which is identified as a transaction method.  "Transaction" is a
  375. very strict policy.
  376.  
  377.  
  378. We notice that some existing concurrency p oliciesare to o rigid.  Wewould like to merge data flow
  379. and atomic concepts to increase parallelism. Thus, an atomic method might susp end some methods
  380. based on the data flow relationship, but not block all the others.
  381.  
  382.  
  383.  
  384. 2.3     Classification Scheme for Locating and Retrieving
  385.  
  386.  
  387.  
  388. Our  classification  scheme  follows  Prieto-Diaz's  approach  [15 ]  but  in  COORL we  define  another
  389. "facet" for synchronization. The introduction of the new facet is justified as follows. It is possible
  390. for a set of the same methods to be regulated by different synchronization requirements.  Though
  391. it is possible to be distinguished by the Medium facet [15 ], it is desirable to add a synchronization
  392. facet because synchronization is an important characteristicfor a concurrent software library. If we
  393. could define a good domain for the facet, search-time inthe library would be cut down dramatically.
  394.  
  395.  
  396. It is possible for the synchronization facet to be activatedby two approaches. One is by some prede-
  397. fined keywords; the other is by the synchronization primitives described in the previous section. The
  398. latter is not encouraged because it violates encapsulation. Some predefined keywords could be as
  399. follows: Space, Time, Order, Priority by X (X could be time, length, ...), FIFO, LIFO, Descending,
  400. and Ascending. We are in the process of studying a more structured keyword representation.
  401.  
  402.  
  403.  
  404.                                                           Shih- 6
  405.  
  406.  
  407. 3      Comparison
  408.  
  409.  
  410.  
  411. We  discussed  how  to  build  a  concurrent  object-oriented  software  reuse  library  and  a  scheme  to
  412. classify a reuse component from the synchronization point ofview.  We have explored these issues
  413. using the COORL model. We believe the approach is better than only developing a new language as
  414. in [12 , 7 , 6 , 8 ] because of the conflict between inheritance and synchronization.  With our approach
  415. a concurrent object-oriented software reuse library can b e built without the conflict.
  416.  
  417.  
  418. With respect to concurrency policy, even though similar concepts are adopted in Meld [14 ], reuse
  419. is not a concern there. Therefore, code tracing and code modification are often needed when new
  420. methods are added to an existing class to obtain a subclass. This approach violates encapsulation.
  421. We argue for putting the concurrency policies in the control segment, thus conforming our placement
  422. of synchronization primitives.
  423.  
  424.  
  425. Our classification scheme for a reuse library follows Prieto-Diaz's approach [15 ] but we argue for
  426. defining another "facet" for synchronization in subsection 2.4.
  427.  
  428.  
  429. Our  approach  will  enhance  reusability  by  b eing  easy  to  access,  understand,  and  mo dify.   With
  430. synchronization  primitives  and  concurrency  policies  expressed  in  the  control  segment,  software
  431. reuse can be improved.
  432.  
  433.  
  434.  
  435. References
  436.  
  437.  
  438.  
  439.   [1] C. Krueger, "Software reuse," ACM Computing Surveys, vol. 24, no. 2, pp. 131-183, 1992.
  440.  
  441.  
  442.   [2] Y. Shih, "Synchronization in a reusable concurrent object-oriented software library,"tech. rep.,
  443.       Department of Computer Science, Binghamton University, 1993.  In preparation.
  444.  
  445.  
  446.   [3] T. Levine, "Reusable software components," ACM Ada Letters, pp. 62-73, May/Jun 1993.
  447.  
  448.  
  449.   [4] P. Wegner, "Dimensions of ob ject-based language design," OOPSLA'87, pp. 168-182, 1987.
  450.  
  451.  
  452.   [5] Y.  Shih,  "Survey  of  the  synchronization  in  concurrent  object-oriented  programming  lan-
  453.       guages," tech. rep., Department of Computer Science, Binghamton University, 1992.
  454.  
  455.  
  456.   [6] D.  Kafura  and  K.  Lee, "Inheritance  in  actor  based  concurrent  object-oriented  languages,"
  457.       ECOOP'89, pp. 131-145, 1989.
  458.  
  459.  
  460.   [7] D. Decouchant et al.,"A synchronization mechanism for typed ob jects in a distributed system,"
  461.       SIGPLAN Notices, vol. 24, pp. 105-107, April 1989.
  462.  
  463.  
  464.   [8] C.  Neusius,  "Synchronization  actions,"  ECOOP'91,  pp.  118-132,  1991.   Also  appeared  in
  465.       Lecture Notes in Computer Science, Vol. 512.
  466.  
  467.  
  468.   [9] C. Tomlinson and V. Singh, "Inheritance andsynchronization with enabled-sets," OOPSLA'89,
  469.       pp. 103-112, 1989.
  470.  
  471.  
  472. [10]  Luqi, "Software evolution through rapid prototyping," IEEE Computer, pp. 13-25, May 1989.
  473.  
  474.  
  475. [11]  Y. Shih and L. Lander, "RCOOL: a model for reusable concurrent object-oriented software
  476.       library," 1993. Submitted to Software Engineering Research Forum 1993.
  477.  
  478.  
  479. [12]  C. Atkinson, Object-Oriented Reuse, Concurrency and Distribution. Addison-Wesley, 1991.
  480.  
  481.  
  482.                                                           Shih- 7
  483.  
  484.  
  485. [13]  C. McHale et al., "Scheduling predicates,"tech. rep., Department of Computer Science, Trinity
  486.       College, University of Dublin, 1991.
  487.  
  488.  
  489. [14]  G.  Kaiser  et al.,  "Multiple  concurrency  control  policies  in  an  object-oriented  programming
  490.       system,"  in Proceedings,  Second  IEEE  Symposium  on  Parallel  and  Distributed  Processing,
  491.       pp. 623-626, 1990.
  492.  
  493.  
  494. [15]  R. Prieto-Diaz and P. Freeman, "Classifying software for reusability," IEEE Software, vol. 4,
  495.       no. 1, pp. 6-16, 1987.
  496.  
  497.  
  498.  
  499. Biography
  500.  
  501.  
  502.  
  503. YunyauShih is a Ph.D. student in the Department of Computer Science at Binghamton University
  504. in  New  York.  He  graduated  from  the  Tunghai  University  in  Taiwan  and  also  has  an  MS from
  505. Binghamton. For his Dissertation he is working on object-oriented reuse libraries with an emphasis
  506. on the inclusion of constructs for synchronization.
  507.  
  508.  
  509. Les Lander is a faculty memb er ofthe Department of Computer Science at Binghamton University.
  510. He obtained his BA at the University of Cambridge and his MS and PhD in mathematics from the
  511. University of Liverpool, U.K. His interests include programming languages and software engineering
  512. and he also works on expert sytems and system-level fault location. He chairs the ACM SIGAda
  513. Local Chapter for the Binghamton/Owego area.
  514.  
  515.  
  516.  
  517.                                                           Shih- 8
  518.