A. L. N. Reddy
Member of Technical Staff
Netscape Communications Corporation
501 East Middlefield Road
Mountain View, CA 94043
Tel: (408)542-3243
Fax: (408)542-3210
Email:
areddy@netscape.com
Reusable software interface and implementation design must include consideration of storage bounds, efficiency, and other performance issues for them to be widely reused. However, typical components -even those designed to be reused - rarely address performance concerns. For example, most components are designed under the assumption of unbounded storage. When bounds are specified, they usually are placed statically on individual objects, leaving central storage management questions largely unattended. It is important to establish that objects in a software system work within global and communal storage constraints, because ultimately, all practical software systems need to function safely within a fixed storage capacity that is determined by the underlying environment. Storage handling also has tremendous implications on efficiency and predictability of software systems. These observations lead us to the following position:
"For widespread reuse, reusable software interface and implementation design must include storage and other performance considerations. Addressing performance issues in addition to more traditional concerns such as functional flexibility, is what makes component design a technical challenge."
Keywords: reusable components, performance, predictability, specification and verification
Workshop Goals: Engage in a design for reuse discussion, learn other aspects of software reuse, network.
Workshop Groups: "Rigorous Behavioral Specification as an Aid to Reuse" and "Component Certification Tools, Frameworks and Processes."
"The interface must permit multiple implementations, at least one of which provides the optimal performance behavior for each intended functional variation."
Design of such reusable interfaces is the underlying motivation for recasting algorithms as reusable objects [11], where the typical algorithm for finding a minimum spanning forest of a graph is recast as an object to encourage reusability. The difficulty in designing suitable formal interface specification for this problem including storage and duration considerations is illustrated in [9]. This paper highlights the issues in addressing storage aspects in component design. Ability to reason about storage aspects is a fundamental requirement because improper handling of dynamic storage can often lead to devious and difficult-to-detect software errors that can sabotage critical missions. Storage handling also has tremendous implications on the predictability of real-time systems. In addition, for safe and secure use of objects in systems that facilitate easy component sharing (e.g., Java), storage-related issues must be carefully addressed. It is therefore essential to be able to design, use and reason about storage considerations of interfaces with ease, but without compromising efficiency or predictability.
Shown next is an instance of the bounded plastic stack concept:
facility BSF is Bounded_Plastic_Stack_Template(Integer, 1000) realized by Static_Array_With_Top_Index
concept Bounded_Plastic_Stack_Template context global context facility Standard_Integer_Facility parametric context constant Max_Depth: Integer restriction Max_Depth>0 type Entry interface type Stack is modeled by string of Entry exemplar s initialization ensures |s| = 0 constraint |s| <= Max_Depth operation Push(alters s: Stack consumes x: Entry) requires |s| < Max_Depth ensures s = #s * #x operation Pop(alters s: Stack produces x: Entry) requires |s| >0 ensures #s = s * x operation Depth_Of (preserves s: Stack): Integer ensures Depth_Of = |s| operation Max_Depth(): Integer ensures Max_Depth = Max_Depth end Bounded_Plastic_Stack_Template
Fig. 1(a). Bounded Stack specification
The upper bounds of all stack objects of Stack type from this facility are fixed to be 1000. The ceramic version of the specification, while still forces a bound on each object, allows different stack objects to use different upper bounds. This specification is given in Figure 1(b).
Both versions of the specifications where individual objects are bounded are
simple for understanding and reasoning. Typical array-based implementations are
efficient and predictable. However, storage utilization is far from optimal
since sizes of
objects have to fixed a priori.
2.3 Communal Storage Management
Fig. 1(b). Bounded Ceramic Stack specification
A communal storage-based specification remedies the storage under-utilization
problem with individually bounded components to a great extent, without
compromising efficiency or predictability. The basic idea of communal storage
management is simple. Different pools of storage are used for objects from
different facilities. For example, all the objects that belong to stack of
integer facility would use the same pool. Though the pool has an upper bound,
there are no bounds on individual objects. This approach permits faster
allocation and de-allocation of storage because all objects in a pool are of
identical size. Allocation and De-allocation take almost constant time as there
is no need to analyze the storage configuration as would be required in global
best-fit, first-fit, or other schemes.
To express communal storage requirements, additional language constructs have
to be introduced, which make the specifications somewhat more complex. One such
specification for communal Stack_Template, directly based on the one in [6], is
given in Figure 2.
Fig. 2 Communal Stack Specification
In the stack specification in Figure 2 new notations, such as Last_Specimen_Num
and Denoted_By, have been introduced. Conceptually, every stack object from a
facility is assigned a sequence number, where Last_Specimen_Num represents the
sequence number of the most recent stack object. The notation Denoted_By is
used to refer to a specific stack object using its sequence number. This is
essential not to bring in the names of all the stack objects into the
specification. Total_Depth of the facility represents the sum of the depths of
all the stack managed by this facility. And the constraint "Total_Depth <
Max_Upper_Bound" specifies that at any given time the sum of the depths of all
the stacks should not exceed the Max_Upper_Bound set for that
facility.
concept Bounded_Ceramic_Stack_Template
context
global context
facility Standard_Integer_Facility
parametric context
type Entry
interface
type Stack is modeled by (contents: string of
Entry
Max_Depth: integer)
exemplar s
initialization
ensures |s.contents| = 0 and
s.Max_Depth = 0
constraint
|s.contents| <= s.Max_Depth
operation Set_Max_Depth( alters s: Stack preserves
max_depth: Integer)
requires max_depth 0 and s.Max_Depth = 0
ensures s.Max_Depth = max_depth and s.contents = #s.contents
operation Get_Max_Depth( preserves s: Stack ): Integer
ensures Get_Max_Depth = s.Max_Depth
-- specifications of Push, Pop, and Depth_Of are
-- similar to those in Figure 1(a) except that now
-- s.max_depth is used instead of Max_Depth
end Bounded_Ceramic_Stack_Template
concept Communal_Stack_Template
context
global context
facility Standard_Integer_Facility
parametric context
type Entry
constant Total_Max_Depth: Integer
restriction Total_Max_Depth >0
interface
type Stack is modeled by string of Entry
math operation Total_Depth : integer
definition
Total_Depth = SIGMA over i=1 to
i=Stack.Last_Specimen_Num(|Stack.Denoted_By(i)|)
constraint
Total_Depth <= Total_Max_Depth
exemplar s
initialization
ensures |s| = 0
operation Push(alters s: Stack consumes x: Entry)
requires Total_Depth < Total_Max_Depth
ensures s = #x * #s
operation Pop(alters s: Stack produces x: Entry)
requires |s| /= 0
ensures #s = x *s
operation Depth_Of ( preserves s: Stack) : Integer
ensures Depth_Of = |s|
operation Get_Rem_Capacity(): Integer
ensures Get_Rem_Capacity = (Total_Max_Depth - Total_Depth)
end Communal_Stack_Template
enhancement Bounded_Stack_Append_Capability for operation Append(alters s: Stack, consumes t: Stack) requires |s| + |t| < Max_Depth ensures s = #s * #t end enhancement Bounded_Ceramic_Stack_Append_Capability for operation Append(alters s: Stack, consumes t: Stack) requires |s| + |t| < s.Max_Depth ensures s = #s * #t end enhancement Communal_Stack_Append_Capability for operation Append(alters s: Stack, consumes t: Stack) --No requires clause since the storage is already available ensures s = #s * #t endFig. 3: Append secondary operations
As shown above specification models of a concept vary with the storage management. Because of these different models enhancements on components have to be specified in a redundant fashion. The Append enhancement for various stack specifications are given in Fig. 3. Had there been a single specification this multiplicity in the number of specifications could have been avoided.
[2] Fleming, D., Sitaraman, M., and Sreerama, S. "A practical Performance Criterion for Object Interface Design," JOOP, SIGS Publication, 1997, to appear.
[3] Hollingsworth, J. E., and Weide, B. W., "Engineering" UNBOUNDED" Reusable ADA Generics," 10th Annual National Conference on ADA Technology, 1992.
[4] Krone, J., and Sitaraman, M. "Expressive Specification and Modular Verification of Performance of Generic Data Abstractions," 1995.
[5] McManis, C., "Not Using Garbage Collection," JavaWorld, September 1996.
[6] Ogden, W. F., "The Proper Conceptualization of Data Structures," CIS 680 Class Notes, The Ohio State University, 1993.
[7] Ogden, W. F., Sitaraman, M., Weide, B. W., and Zweben, S. H., "The RESOLVE Framework and Discipline," ACM SIGSOFT Software Engineering Notes Vol. 19 No.4, October 1994.
[8] Perkins, C. L., "The Big Picture," Java report, March/April 1996.
[9] Sitaraman, M., "Impact of Performance Considerations on Formal Specification Design," Formal Aspects of Computing, 1997: 000-000.
[10] Wing, J. M., "A Specifier's Introduction to Formal Methods", IEEE Computer, 23(9), 8-24, 1990.
[11] Weide, B. W., Ogden, W. F. and Sitaraman, M. "Recasting Algorithms to Encourage Reuse," IEEE Software, 11(5), 80-88 (1994).
[12] Zhang, Y., "Implementation and Experimentation with a Communal Storage Manager in Java," MS report, West Virginia University, Morgantown, WV26506.
A. L. N. Reddy is currently working at Netscape Communications Corporation, Mtn. View, CA, as a Member of Technical Staff. Prior to joining Netscape, A. L. N. Reddy was a Software Engineer at ManTech, Fairmont, WV. He received a MS in computer science from West Virginia University in 1992, and is currently working on his Ph.D. thesis under the guidance of Dr. Murali Sitaraman at West Virginia University. He is a member of Association for Computing Machinery.