CS446 [CS646] Software Design and Architecture Fall 1998

Prof Ric Holt, Department of Computer Science, Waterloo University

MIDTERM: CS446 [CS646] Software Design and Architecture

5 Nov 1998
                                                Q1 [30] _______
                                                Q2 [10] _______
                                                Q3 [25] _______

                                                Q4 [25] _______
                                                Q5 [10] _______
                                             TOTAL[100] _______
Answers should be clear and brief. Please use good grammar and spelling.

1. A software architecture can be characterized in terms of a "vocabulary", a set of "constraints", "structural patterns", a "computational model", "invariants", along with "advantages/disadvantages" and "specializations". (These terms come from Garlan/Shaw and Mancoridis.) Using these terms, characterize the following two architectural styles, giving an example of each, with appropriate diagrams:

1A. [15 points] Repository style

1B. [15 points] Layered style

2. [10 points] Explain what is meant by a standard (or reference) architecture. Give an example of a standard architecture, using a diagram.

3. Consider a system S, which contains 2 modules (M1 and M2), 5 resources (r1 to r5), which you can consider to be procedures, and 4 secrets (s1 to s4), which you can consider to be design decisions. These are interconnected by these relations:

	C	Contain (modules contain resources)
	H	Has secret (resources have secrets --- or know about secrets)
	U	Use (resources use resources, eg, they call each other)
The interconnecting edges in system S are:
	M1 C r1, M1 C r2, M2 C r3, M2 C r4,
	M2 C r5, r1 H s1, r1 H s2, r2 H s1, r3 H s3, r4 H s4, r1 U r2,
	r2 U r5, r3 U r2 and r5 U r4.

[5 points] Draw a clear diagram that represents system S; draw C (containment) as explicit edges, not as box nesting.

[5 points] Give, both on your diagram as arrows, and as a list of pairs, the relation h = C * H, where * means relational composition.

[5 points] Define "ideal modularization" according to Parnas, as given in class (for any system T that has a structure like that of S). Give the definition both in English and mathematically.

[5 points] Explain in detail why system S has (or does not have) an ideal modularization.

[5 points] Give an example system, containing 3 resources (r1 to r3) and three secrets (s1 to s3), with the property that it has no ideal modularization (other than putting all resources into a single module). Give your example system by drawing it (with a legend explaining your notation). Explain why there is no ideal modularization.

4. A system designer has specified a convention for what interactions are allowed in the system he/she is designing. The system is to consist of subsystems SS, and resources R, which are procedures and variables. In this model, the designer does not distinguish between procedures and variables; in other words, the entity class R consists of both procedures and variables. The lowest level subsystems can be considered to be modules.

The "scheme" (or schema) W for the system is as follows. There are use (U) edges from procedures to procedures (representing calls) and from procedures to variables (representing fetches and stores). Subsystems (SS) contain (C) other subsystems as well as procedures and variables (R). (The system itself is considered to be a subsystem). Relation C is a tree.

A small system called SYS has these edges:

	S1 C S2, S1 C S3, S2 C x, S3 C y, S1 C z, x U y, x U z.
[5 points] Draw a clear diagram of SYS, with the convention that C is shown by nesting. Give an appropriate legend for your drawing. Give the value of the relation L = inv U * U (the composition of the inverse of U with U) as a set of pairs. Give the value of the relation Ao = (inv C)* (the reflexive transitive closure of the inverse of C), as a set of pairs.

[8 points] Draw scheme W as an E/R diagram (using TA style is your wish). Does SYS satisfy scheme W? Explain why or why not in detail.

There are two kinds of permission edges that will appear in the system:
	E	Export edges
	B	Buy edges
[2 points] Add these E and B edges to your diagram for SYS.
	x B S2, x B S1, S2 B S1, S1 E z.

Intuitively, the only way to get inside a subsystem is by following Export edges and the only way to get out of a subsystem is by following Buy edges. (Strictly speaking, the E and B edges should be included in the scheme, but we will not worry about this here). These permission constraints are given by Rules RULE1 and RULE2:

RULE1: A parent can Export (E) its child as well as the things transitively Exported from its child.

RULE2: A child N1 can Buy its parent, and as well, N1 can Buy N3, by following Buy edges transitively from N1 to node N2 and on to N2's parent N3.

Note that RULE2 is essentially the reverse of RULE1. RULE2 can be stated mathematically as

	B <= B* * inv C
i.e., B is constrained to be a subset of the reflexive transitive closure of B composed with the inverse of C.

[5 points] Explain clearly whether RULE1 is satisfied by SYS, with its B and E edges. Do the same for RULE2. Give RULE1 mathematically (using Tarski operators).

The designer decided to use this rule (RULE3) to constrain usage (U):

RULE3. A procedure R1 can use a procedure or variable R2 only if R1 and R2 are siblings or if R1 Buys an ancestor A1 that is the sibling of node A2 that in turn Exports R2.

[5 points] Add edges as necessary to SYS so RULE3 is satisfied. You may need to copy the diagram to make this clear.

5. [10 points] Compare and contrast the concept of an "architectural style" versus the concept of a "design pattern". Use examples in your discussion.