Monday 30 January 2012

Thread and process synchronisation with mutex

In my previous article I described how to use semaphore in order to synchronise threads or processes. Mutex is a semaphore specialisation and can be used in the special case - when only one thread (or process) is allowed to access shared resource.

Mutex is a synchronisation object that controls resource access (critical section execution) by maintaining the knowledge of its current owner (accessor - thread or process). Mutex strictly limits access to a single accessor at a time.

Ownership over the mutex is controlled with following operations:
  • acquire() (or lock()) - passes the ownership of the mutex to the calling thread
  • release() (or unlock()) - calling thread gives up its ownership of mutex. Only thread that acquired the mutex can release it

Mutex has two states:
  • signalled - when no thread owns it; acquire() does not block
  • non-signalled - when owned by some thread; acquire() in other thread blocks till mutex gets signalled

When Thread1 acquires ownership of mutex, it has a exclusive right to access the shared resource (to execute the code in the critical section). Once it's finished, it needs to release mutex so another thread can acquire ownership and access the resource. If thread does not release the mutex, other threads cannot acquire it and application is in a deadlock. It is therefore very important to make sure that mutex is released under any condition, no matter of the outcome of the code in the critical section! RAII-compliant design can prevent program's execution to leave critical section's scope without releasing the mutex.

Semaphore behaves like shared mutex with a count controlled by multiple threads that are allowed to access shared resource. Mutex is stricter, only thread that owns it has the power to release it, and only that thread can access shared resource.

The following example shows how to use mutex in order to synchronise processes that write into the shared file (problem described in this article):

main.cpp:



Links and References:

Mutex Objects (MSDN)
Using Mutex Objects (MSDN)
Mutual exclusion (Wikipedia)

Thread and process synchronisation with semaphores

Semaphore is a synchronisation object that controls resource access (critical section execution) by maintaining the number (count, n) of accessors (threads or processes) (still) allowed to access the resource. While mutex strictly limits access to a single accessor at a time, semaphore allows up to N (N > 0) parallel accessors. N is defined when semaphore is being created and it represents maximum possible value of the semaphore count.

Semaphore count is changed through following operations:
  • wait() - which, on return,  decreases count on successful return (minimum is 0)
  • release() - which increases count (maximum is N)

Semaphore has two states:
  • signalled - when 0 < n <= N; wait() does not block
  • non-signalled - when n == 0; wait() blocks till semaphore gets signalled (or returns on expired timeout)

There are two types of semaphores:
  • counting - based on the count 0 <= n <= N where N > 1
  • binary - (specialisation of counting) where N == 1; when in signalled state we say it is unlocked; when in non-signalled state we say it is locked

Semaphores are signalling accessors the right of way - just as traffic semaphores, but unlike them, accessors themselves are controlling when the light for others will become green - through wait() and release() operations. Accessors are wait()-ing for a semaphore. If semaphore is signalled (n > 0), wait() returns immediately, decreasing semaphore count. When accessor (this one or any other) is finished with the shared resource it calls release() on the semaphore, increasing its count. Accessor will block on wait()-ing if semaphore is non-signalled (when maximum allowed number of accessors are sharing the resource). As soon as some accessor finishes the work and releases the semaphore, accessor's wait() will unblock and it will be allowed to access the resource.

Obviously, if N is set to 1, semaphore (called binary semaphore in this case) logically behaves like a mutex, allowing only one accessor at a time. There is a difference between two of them though: only accessor that locked the mutex can unlock it (mutex is owned by the accessor), but any accessor can release semaphore.

Majority of semaphore examples on the internet are focused on consumer-producer problem. I wanted to show use of semaphore on the example of traffic control - something that resembles the real semaphore. So, let's say we have three single-lane, one way roads joining just before a bridge which is one way but has two lanes. To reduce congestion on the bridge, traffic from only two access roads is allowed at a time. There is a semaphore with the red and green light by the each road and once it turns green, it remains in that state for some time period T. First two opened roads get green light first. As soon as the timeout expires for one of those roads and semaphore shows red, semaphore will show green for traffic that has been waiting at the third road.

Semaphore-example

We can think of roads (traffic on them) as accessors and the bridge as a resource: two roads can lead traffic to the bridge at the same time (two accessors are allowed to access shared resource). Obviously, we will set the maximum value for the semaphore count to 2 in our model. Thread will wait() as long as count is 0 but as soon as it gets increased to 1, wait() returns (decreasing count to 0 again).

This example aims to show how semaphore limits parallel access to the shared resource and how accessors (threads in this case) themselves control semaphore by wait()-ing for the semaphore and release()-ing it.

To stop threads I tend to use event object - not a flag (volatile bool variable). They are thread-safe and thread callbacks don't need to return with delay of one additional wait() cycle in the case when termination has been requested.

I wrapped event and semaphore objects (handles) into RAII-compliant classes - CScopedEvent and CScopedSemaphore.

main.cpp:




Output:

Road 1 opened
0 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
1 road(s) is(are) generating traffic...
Road 2 opened
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...
Road 3 opened
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 3 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 3 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
Road 3 got green light for the next 10 seconds. Generating traffic...
1 road(s) is(are) generating traffic...2 road(s) is(are) generating traffic...


Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
Road 3 got green light for the next 10 seconds. Generating traffic...
1 road(s) is(are) generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...
Closing road 3 ...
Road 3 got request to get closed
Road 3 closed
Closing road 2 ...

Road 1 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got request to get closed
Road 2 closed
Closing road 1 ...

Road 1 got red light. Waiting for a green light...
0 road(s) is(are) generating traffic...
Road 1 got request to get closed
Road 1 closed

The example above shows how semaphore controls access to the resource by multiple threads. But please note that resource was NOT made thread safe! Semaphore was just allowing up to N threads (2 in our case) to be active at a time (and generate the traffic towards the bridge). If we wanted to limit the number of vehicles on the bridge and to control traffic lights depending on the current bridge load, we would have had to limit the number of active threads to 1. In that case only one road would have green light at a time.

In the next example I want to show how to synchronise multiple processes in accessing shared resource. Let's say we have an app which writes some log into the file and does it in a loop. The code could look like this:

main.cpp:



If run with parameter of value e.g. "012345", this app will create text file with the following content:

test.log:

[PID = 4408] Iteration # 1 012345
[PID = 4408] Iteration # 2 012345
[PID = 4408] Iteration # 3 012345
[PID = 4408] Iteration # 4 012345
...

If we run simultaneously two or more instances of this process, they will all write into the same file, increasing its size with each write operation. Manipulator endl inserts new line character ('\n') at the end of the line and flushes the buffer to the disk. Obviously, before writing to the disk, our file stream object needs to know the current size of the file in order to move write pointer to the file end. If Process2 appends a new line to the file after Process1 reads file size but before Process1 writes into it, Process2 will increase file size but Process1 will know only about the previous file size and start writing at the position set accordingly, effectively overwriting Process2's last written line!

The following code is the content of the script (DOS batch file) which runs three instances of our application, providing each with different argument:

run_processes.bat:

@start Process.exe 012345
@start Process.exe ABCDEFHIJKLM
@start Process.exe 987654321

Arguments are of different length so we can easily detect the place of the corruption in the output file, like this one:

test.log:

...
[PID = 8280] Iteration # 214 ABCDEFHIJKLM
[PID = 8120] Iteration # 208 987654321
M
[PID = 8280] Iteration # 216 ABCDEFHIJKLM
...

What happened here? First of all, we need to know that on Windows, \n read from stream buffer is expanded to \r\n (CR-LF) before writing it to the file on disk. Process 8120 has updated its knowledge of file size but before it wrote iteration #208 log, process 8280 had written its log for iteration #215 so basically we had this:

test.log (showing hidden CR-LF characters):

...
[PID = 8280] Iteration # 214 ABCDEFHIJKLM\r\n
[PID = 8280] Iteration # 215 ABCDEFHIJKLM\r\n
...

Then process 8120 wrote its #208 log, but effectively overwriting 8280's #215, after what 8280 wrote its log #216:

test.log (showing hidden CR-LF characters):

...
[PID = 8280] Iteration # 214 ABCDEFHIJKLM\r\n
[PID = 8120] Iteration # 208 987654321\r\nM\r\n
[PID = 8280] Iteration # 216 ABCDEFHIJKLM\r\n
...

Obviosuly, we need to protect file so only one process is accessing it at a time. We can do that with semaphore or mutex which are shared between multiple processes (and therefore must be named).

In this article I will show how to achieve it with semaphore:

main.cpp:



All processes are competing to get semaphore signal. First process whose wait() returns (decreasing semaphore count by 1 - possibly to minimal value of 0 in which case all other processes block on their wait()) gets a exclusive access to a file and updates its content after which it releases semaphore (increasing its count to 1 again). All processes are competing again and the one whose wait() returns first gets its slot of exclusive access. There is no corruption in the file any more:

test.log:

...
[PID = 6036] Iteration # 213 987654321
[PID = 10940] Iteration # 213 012345
[PID = 11644] Iteration # 213 ABCDEFHIJKLM
[PID = 6036] Iteration # 214 987654321
[PID = 10940] Iteration # 214 012345
[PID = 11644] Iteration # 214 ABCDEFHIJKLM
[PID = 6036] Iteration # 215 987654321
[PID = 10940] Iteration # 215 012345
[PID = 11644] Iteration # 215 ABCDEFHIJKLM
...

Note: Although this example uses semaphore for process synchronisation, mutex is here more natural solution - we don't want to limit number of accessors to several (N) but only to 1. Only process that locks the mutex can unlock it and with binary semaphore we are just emulating this behaviour.

Links and References:
Semaphore Objects (MSDN)
Using Semaphore Objects (MSDN)
Semaphore (Wikipedia)
Windows Thread Synchronization - Synchronization Using Semaphores
Joseph M. Newcomer: Semaphores
Mutex or Semaphore for Performance?
Mutex vs Semaphore
Mutex vs Semaphores
Difference between binary semaphore and mutex

Thursday 19 January 2012

UML Class Diagrams and Class Relationships

UML Class Diagrams display relationships between classes in a given model. Here is a list of various types of class relationships and statements that can describe them:
  • generalization ("A is a kind of B")
  • realization ("A implements B")
  • dependency ("A uses B and forgets about it", "A can send message to B")
  • association ("A uses B and keeps it", "A has B")
  • aggregation ("B can be a part of A (whole)", "B can outlive A", "B can be shared between many As")
  • composition ("B is a part of A (whole)", "A owns B", "B cannot outlive A", "B belongs only to one A")
It is usually easy to distinguish generalization from realization, aggregation from composition but the border line between dependency, association and aggregation is a bit blurry. All these relationships are actually some kinds of associations which differ in subtle details and which can be redefined depending on the context. Different books and articles on UML sometimes define these relationships in a very different way ("dependency is a type of association" vs. "association is a type of dependency", "aggregation is meaningless"...) and some are even advising (with a reason!) to give up differentiating them:

"Rule 145. Don't Worry About the Diamonds: When you are deciding whether to use aggregation or composition over association, Craig Larman (2002) says it best: "If in doubt, leave it out." The reality is that many modelers will agonize over when to use aggregation when the reality is that there is very little difference between association, aggregation, and composition at the coding level." [12]

I tried to find an algorithm which goes through a set of questions (based on aforementioned statements) about the relationship between class A and class B and which at the end yields the name of that relationship.

Here is the algorithm I came up with:

ClassRelationshipsAlgorithm

Here are some descriptions of class relationships I found in various UML-related books:

Dependency

The weakest relationship between classes is a dependency relationship. Dependency between classes means that one class uses, or has knowledge of, another class. It is typically a transient relationship, meaning a dependent class briefly interacts with the target class but typically doesn't retain a relationship with it for any real length of time. Dependencies are typically read as "...uses a...". For example, if you have a class named Window that sends out a class named WindowClosingEvent when it is about to be closed, you would say "Window uses a WindowClosingEvent." You show a dependency between classes using a dashed line with an arrow pointing from the dependent class to the class that is used. [1]

A dependency exists between two elements if changes to the definition of one element (the supplier) may cause changes to the other (the client). With classes, dependencies exist for various reasons: One class sends a message to another; one class has another as part of its data; one class mentions another as a parameter to an operation. If a class changes its interface, any message sent to that class may no longer be valid. (...) The UML allows you to depict dependencies between all sorts of elements. You use dependencies whenever you want to show how changes in one element might alter other elements. [2]

(...) Your general rule should be to minimize dependencies [2]

(... ) The most common case I use for dependencies with classes is when illustrating a transient relationship, such as when one object is passed to another as a parameter. [2]

...one class uses another. This is called a dependency. The most common usage of a dependency is to show that the signature of one class' operation uses another class. [3]

Dependency—the relationship between a component and an interface through which it accesses another component. (...) dependency is visualized as a dashed line with an arrowhead. [3]

You model interaction through an interface as a dependency. [3]

Sometimes the relationship between a two classes is very weak. They are not implemented with member variables at all. Rather they might be implemented as member function arguments. (...) This is the dependency relationship. In Booch94 this was called a ‘using’ relationship. This relationship simply means that A somehow depends upon B. In C++ this almost always results in a #include. [5]

A dependency is a "using" relationship within which a change in one thing (such as a class) may affect another thing (for instance, another class). The dependent element is called the client or source; the independent element is called the supplier or target. A dependency involving two classes appears as a dashed line with a feathered arrow pointing at the supplier. [8]

The UML includes a general dependency relationship, which indicates that one element (of any kind, including classes, use cases, and so on) has knowledge of another element. It is illustrated with a dashed arrow line. In class diagrams the dependency relationship is useful to depict non-attribute visibility between classes; in other words, parameter, global, or locally declared visibility. By contrast, plain attribute visibility is shown with a regular association line and a navigability arrow. For example, the Register software object receives a return object of type ProductSpecification from the specification message it sent to a ProductCatalog. Thus Register has a short-term locally declared visibility to ProductSpecifications. And Sale receives a ProductSpecification as a parameter in the makeLineItem message; it has parameter visibility to one. These non-attribute visibilities may be illustrated with the dashed arrow line indicating a dependency relationship. [9]

Dependency relationships are indicating non-attribute visibility. [9]

Association

Associations are stronger than dependencies and typically indicate that one class retains a relationship to another class over an extended period of time. The lifelines of two objects linked by associations are probably not tied together (meaning one can be destroyed without necessarily destroying the other). Associations are typically read as "...has a...". For example, if you have a class named Window that has a reference to the current mouse cursor, you would say "Window has a Cursor". Note that there is a fine line between "...has a..." and "...owns a..." (see "Aggregation" later in this section). In this case, Window doesn't own the Cursor; Cursor is shared between all applications in the system. However, Window has a reference to it so that the Window can hide it, change its shape, etc. You show an association using a solid line between the classes participating in the relationship.[1]

The other way to notate a property is as an association. Much of the same information that you can show on an attribute appears on an association. [2]

An association is a solid line between two classes, directed from the source class to the target class. The name of the property goes at the target end of the association, together with its multiplicity. The target end of the association links to the class that is the type of the property. [2]

As an alternative to labeling an association by a property, many people, particularly if they have a data-modeling background, like to label an association by using a verb phrase so that the relationship can be used in a sentence. This is legal and you can add an arrow to the association to avoid ambiguity. Most object modelers prefer to use a property name, as that corresponds better to responsibilities and operations. [2]

(...) Because you don't need an association to a class to send a message to it, you may also need to add a dependency arrow to show messages between classes that aren't associated. [2]

When classes are connected together conceptually, that connection is called an association. [3]

When one class associates with another, each one usually plays a role within that association. You can show each class’s role by writing it near the line next to the class. In the association between a player and a team, if the team is professional, it’s an employer and the player is an employee [3]

An association declares that there can be links between instances of the associated types. It has at least two ends represented by properties, each of which is connected to the type of the end. An association declares that there can be links between instances of the associated types. [4]

There are other forms of containment that do not have whole / part implications. For example, Each Window refers back to its parent Frame. This is not aggregation since it is not reasonable to consider a parent Frame to be part of a child Window. We use the association relationship to depict this. (...) An association is nothing but a line drawn between the participating classes. (...) Once again note the name on the role. This relationship will almost certainly be implemented with a pointer of some kind. [5]

What is the difference between an aggregation and an association? The difference is one of implication. Aggregation denotes whole/part relationships whereas associations do not. However, there is not likely to be much difference in the way that the two relationships are implemented. That is, it would be very difficult to look at the code and determine whether a particular relationship ought to be aggregation or association. For this reason, it is pretty safe to ignore the aggregation relationship altogether. As the amigos said in the UML 0.8 document: “...if you don’t understand [aggregation] don’t use it.” [5]

Aggregation and Association both correspond to the Has-by-reference relationship from the Booch-94 notation. [5]

There are other types of relationships that do not fit neatly into a generalization (a-kind-of) or aggregation (a-part-of) framework. Technically speaking, these relationships are usually a weaker form of the aggregation relationship. For example, a patient schedules an appointment. It could be argued that a patient is a-part-of an appointment. However, there is a clear semantic difference between this type of relationship and one that models the relationship between doors and cars or even workers and unions. As such, they are simply considered to be associations between instances of classes. [6]

Association: Objects of one class are associated with objects of another class. [7]

Association is a weak form of connection: the objects may be part of a group, or family, of objects but they’re not completely dependent on each other. For example, consider a car, a driver, a passenger and another passenger. When the driver and the two passengers are in the car, they’re associated: they all go in the same direction, they occupy the same volume in space, and so on. But the association is loose: the driver can drop off one of the passengers to go their separate way, so that the passenger is no longer associated with the other objects. [7]

According to the UML standard, all run-time relationships come under the umbrella term association. However, most people use the term ‘association’ to mean ‘an association that isn’t aggregation or composition’. Choosing between relationships can be tricky – you need to use intuition, experience and guesswork. During analysis, you should expect the frequency of these kinds of relationship to be: association > aggregation > inheritance > composition. As far as design and implementation are concerned, the differences between association, aggregation and composition can be difficult to spot. [7]

All relationships, except inheritance, can be given an association label, indicating the nature of the association. If it’s not obvious which way the association name should be read, a black arrowhead can be used. [7]

As well as association names, we can show roles. A role indicates the part played by an object in the association – the role is shown as a label near the object that plays the role. [7]

An association is a relationship between types (or more specifically, instances of those types) that indicates some meaningful and interesting connection. [9]

In the UML associations are defined as "the semantic relationship between two or more classifiers that involve connections among their instances." [9]

Associations worth noting usually imply knowledge of a relationship that needs to be preserved for some duration — it could be milliseconds or years, depending on context. In other words, between what objects do we need to have some memory of a relationship? (...) Associations for which knowledge of the relationship needs to be preserved for some duration ("need-to-know" associations). [9]

Focus on those associations for which knowledge of the relationship needs to be preserved for some duration ("need-to-know" associations). [9]

We should add those associations which the requirements (for example, use cases) suggest or imply a need to remember, or which otherwise are strongly suggested in our perception of the problem domain. [9]

An attribute is related to an association [9]

How to Discover Associations: During system use-case interviews, look out for statements of the form X [verb] Y, where X and Y represent business objects. They often reveal associations. For example, in “A Peace Committee supervises a Case,” Peace Committee is associated with Case; the association name is supervises. [10]

An association represents a relationship that has a precisely defined meaning. The association can be labeled with the name of the association. If you want to assign a direction to the association's name, you can insert a triangle that points to the direction in which the name is supposed to be read. (...) An association indicates that objects of one class have a relationship with objects of another class, in which this connection has a specifically defined meaning (for example, "is flown with"). [11]

 Aggregation

Aggregation is a stronger version of association. Unlike association, aggregation typically implies ownership and may imply a relationship between lifelines. Aggregations are usually read as "...owns a...". For example, if you had a classed named Window that stored its position and size in a Rectangle class, you would say the "Window owns a Rectangle." The rectangle may be shared with other classes, but the Window has an intimate relationship with the Rectangle. This is subtly different from a basic association; it has a stronger connotation. However, it's not the strongest relationship you can have between classes. If the relationship is more of a whole part (class A "...is part of..." class B), you should look at composition. [1]

You show an aggregation with a diamond shape next to the owning class and a solid line pointing to the owned class. [1]

Aggregation is the part-of relationship. It's like saying that a car has an engine and wheels as its parts. This sounds good, but the difficult thing is considering what the difference is between aggregation and association. [2]

(...) Aggregation is strictly meaningless; as a result, I recommend that you ignore it in your own diagrams. If you see it in other people's diagrams, you'll need to dig deeper to find out what they mean by it. Different authors and teams use it for very different purposes. [2]

Sometimes a class consists of a number of component classes. This is a special type of relationship called an aggregation. The components and the class they constitute are in a part-whole association. [3]

Aggregation is a type of association. An aggregate object consists of a set of component objects. [3]

Aggregation is transitive [3]

The weak form of aggregation is denoted with an open diamond. This relationship denotes that the aggregate class (the class with the white diamond touching it) is in some way the “whole”, and the other class in the relationship is somehow “part” of that whole. [5]

Many different types of aggregation or composition relationships have been proposed in data modeling, knowledge representation, and linguistics. For example, a-part-of (logically or physically), a-member-of (as in set membership), containedin, related-to, and associated-with. However, generally speaking, all aggregation relationships relate parts to wholes or parts to assemblies. For our purposes, we use the a-part-of or has-parts semantic relationship to represent the aggregation abstraction. For example, a door is a-partof a car, an employee is a-part-of a department, or a department is a-part-of an organization. [6]

Like the generalization relationship, aggregation relationships can be combined into aggregation hierarchies. For example, a piston is a-part-of an engine, while an engine is a-part-of a car. [6]

Aggregation means putting objects together to make a bigger object. Manufactured items usually form aggregations: for example, a microwave is made up of a cabinet, a door, an indicator panel, buttons, a motor, a glass plate, a magnetron, and so on. Aggregations usually form a part–whole hierarchy. Aggregation implies close dependency, at least of the whole to the part; for example, a magnetron is still a magnetron if you take it out of its microwave, but the microwave would be useless without the magnetron, because it wouldn’t be able to cook anything. [7]

As suggested, the distinction between association and aggregation can be subtle. The ‘What happens if you remove one of the objects?’ test can be helpful, but it doesn’t always solve the problem: hard thinking and experience are often needed. [7]

Aggregation: Strong association – an instance of one class is made up of instances of another class. [7]

An aggregation is a special kind of association — a "whole/part" relationship within which one or more classes are parts of a larger whole. A class can be aggregated to one or more other classes.

Using aggregation is an excellent way to establish a "pecking order" of complexity, with more complex classes aggregating less complex ones. For a system of any size, doing this can only help viewers of your models more easily understand the concepts that are important to them while enabling them to ignore concepts expressed at lower levels of detail.

An aggregation appears as a line with an open diamond at one end. The class next to the diamond is the whole class; the class at the other end of the line is the part class.
[8]

An important property of aggregation is that the aggregated classes are still basically independent of the aggregating class. [8]

Shared aggregation means that the multiplicity at the composite end may be more than one, and is signified with a hollow diamond. It implies that the part may be simultaneously in many composite instances. (...) For instance, a UML package may be considered to aggregate its elements. But an element may be referenced in more than one package (it is owned by one, and referenced in others), which is an example of shared aggregation. [9]

In some cases, the presence of aggregation is obvious—usually in physical assemblies. But sometimes, it is not clear. On aggregation: If in doubt, leave it out. Here are some guidelines that suggest when to show aggregation:

Consider showing aggregation when:

• The lifetime of the part is bound within the lifetime of the composite — there is a create-delete dependency of the part on the whole.
• There is an obvious whole-part physical or logical assembly.
• Some properties of the composite propagate to the parts, such as the location.
• Operations applied to the composite propagate to the parts, such as destruction, movement, recording.

Other than something being an obvious assembly of parts, the next most useful clue is the presence of a create-delete dependency of the part on the whole.
[9]

Composition

Composition represents a very strong relationship between classes, to the point of containment. Composition is used to capture a whole-part relationship. The "part" piece of the relationship can be involved in only one composition relationship at any given time. The lifetime of instances involved in composition relationships is almost always linked; if the larger, owning instance is destroyed, it almost always destroys the part piece. UML does allow the part to be associated with a different owner before destruction, thus preserving its existence, but this is typically an exception rather than the rule. [1]

A composition relationship is usually read as "...is part of...", which means you need to read the composition from the part to the whole. For example, if you say that a window in your system must have a titlebar, you can represent this with a class named Titlebar that "...is part of..." a class named Window. [1]

You show a composition relationship using a filled diamond next to the owning class and a solid line pointing to the owned class. [1]

The general rule is that, although a class may be a component of many other classes, any instance must be a component of only one owner. The class diagram may show multiple classes of potential owners, but any instance has only a single object as its owner. [2]

The "no sharing" rule is the key to composition. Another assumption is that if you delete the "whole", it should automatically ensure that any owned parts also are deleted. [2]

Composition is a good way of showing properties that own by value, properties to value objects, or properties that have a strong and somewhat exclusive ownership of particular other components. [2]

One form of aggregation involves a strong relationship between an aggregate object and its component objects. This is called composition. The key to composition is that the component exists as a component only within the composite object. For example, a shirt is a composite of a body, a collar, sleeves, buttons, buttonholes, and cuffs. Do away with the shirt and the collar becomes useless. Sometimes a component in a composite doesn’t last as long as the composite itself. The leaves on a tree can die out before the tree does. If you destroy the tree, the leaves also die. [3]

A composition is a special kind of aggregation. In a composite object the components exist only as part of the composite. (...) A composite is a strong type of aggregation. Each component in a composite can belong to just one whole. The components of a coffee table—the tabletop and the legs—make up a composite. The symbol for a composite is the same as the symbol for an aggregation except the diamond is filled. [3]

Composition relationships are a strong form of containment or aggregation. Aggregation is a whole/part relationship. In this case, Circle is the whole, and Point is part of Circle. However, composition is more than just aggregation. Composition also indicates that the lifetime of Point is dependent upon Circle. This means that if Circle is destroyed, Point will be destroyed with it. For those of you who are familiar with the Booch-94 notation, this is the Hasby-value relationship. [5]

Composition is a strong aggregation where the composed object is inside a single composite; the composed object is usually created at the same time as the composite and can be deleted at the same time. In UML, in order to emphasize that composition is stronger than aggregation, we use a black diamond instead of a white one. [7]

Composition: Strong aggregation – the composed object can’t be shared by other objects and dies with its composer. [7]

The difference between aggregation and composition is subtle. The differences relate to object sharing and object lifetimes. Recall that a composed object can never be part of more than one composite and dies with the composite, while an aggregated object can be shared and can outlive its aggregator. Although a car trundles out of the factory with a brand new engine inside, the engine may later be replaced, because it’s worn out, so the engine doesn’t necessarily die with the car; in contrast, the body of the car is an intrinsic part of the car – it’s the soul of the car, if you like, you can’t destroy the car without destroying the body (but you could always take the engine out first). The issue of sharing is not important in this example: although the body could never be part of two cars (not legally, anyway), the engine couldn’t either. [7]

Composition is a "strong" form of aggregation. There are two differences between composition and regular aggregation, as follows: Within a composition relationship, the whole and the parts have coincident lifetimes. This means that if a particular instance of the whole is destroyed, so are the instances of the parts. A class can only belong to one composition relationship at a time as a part. [8]

Composite aggregation, or composition, means that the part is a member of only one composite object, and that there is an existence and disposition dependency of the part on the composite. [9]

Composition is signified with a filled diamond. It implies that the composite solely owns the part. [9]

Generalization 

A generalization relationship conveys that the target of the relationship is a general, or less specific, version of the source class or interface. Generalization relationships are often used to pull out commonality between difference classifiers. For example, if you had a class named Cat and a class named Dog, you can create a generalization of both of those classes called Animal. A full discussion of how and when to use generalization (especially versus interface realization) is the subject for an object-oriented analysis and design book and isn't covered here. [1]

Generalizations are usually read as "...is a...", starting from the more specific class and reading toward the general class. Going back to the Cat and Dog example, you would say "a Cat...is a...Animal" (grammar aside).[1]

You show a generalization relationship with a solid line with a closed arrow, pointing from the specific class to the general class. [1]

One class (the child class or subclass) can inherit attributes and operations from another (the parent class or superclass). The parent class is more general than the child class. (...) Object-orientation refers to this as inheritance. The UML also refers to this as generalization. (...) In the UML, you represent inheritance with a line that connects the parent class to the child class. On the part of the line that connects to the parent class, you put an open triangle that points to the parent class. This type of connection stands for the phrase "is a kind of". [3]

The generalization abstraction enables the analyst to create classes that inherit attributes and operations of other classes. The analyst creates a superclass that contains the basic attributes and operations that will be used in several subclasses. The subclasses inherit the attributes and operations of their superclass and can also contain attributes and operations that are unique just to them. For example, a customer class and an employee class can be generalized into a person class by extracting the attributes and operations they have in common and placing them into the new superclass, Person. In this way, the analyst can reduce the redundancy in the class definitions so that the common elements are defined once and then reused in the subclasses. Generalization is represented with the a-kind-of relationship, so that we say that an employee is a-kind-of person. [6]

Inheritance: A subclass inherits all of the attributes and behavior of its superclass(es). [7]

Generalization refers to a relationship between a general class (the superclass or parent) and a more specific version of that class (the subclass or child). You can think of the subclass as being a "kind of" the superclass. A generalization appears as a line with an open triangle at one end. The class next to the triangle is the parent/superclass; the class at the other end of the line is the child/subclass. [8]

Realization 

A realization is an association between a class and an interface, a collection of operations that a number of classes can use. An interface is represented as a class with no attributes. To distinguish it from a class whose attributes have been elided from the diagram, the keyword «interface» appears above the interface’s name or an uppercase “I” precedes the interface’s name. Realization is represented in the UML as a dashed line that connects the class to the interface, with an open triangle adjoining the interface and pointing to it. [3]

References:

[1] Dan Pilone, Neil Pitman, UML 2.0 in a Nutshell, O'Reilly, 2005
[2] Martin Fowler, UML Distilled: A brief guide to the standard object modeling language, 3rd edition, Addison-Wesley Professional, 2004
[3] Joseph Schmuller, Teach Yourself UML in 24 Hours, Sams Publishing, 2004
[4] OMG UML Superstructure Version 2.4.1, OMG, 2011
[5] Robert C. Martin, UML Tutorial
[6] Alan Dennis, Barbara Haley Wixom and David Tegarden, System Analysis and Design with UML Version 2.0 - An Object-Oriented Approach, John Wiley & Sons Ltd, 2005
[7] Mike O’Docherty, Object-Oriented Analysis and Design  - Understanding System Development with UML 2.0, John Wiley & Sons Ltd, 2005
[8] Kendall Scott, Fast Track UML 2.0, Apress, 2004
[9] Craig Larman, Applying UML and Patterns - An Introduction to Object-Oriented Analysis and Design and the Unified Process 2nd ed, Prentice Hall, 2001
[10] Howard Podeswa, UML for the IT Business Analyst: A Practical Guide to Object-Oriented Requirements Gathering, Thomson Course Technology PTR, 2005
[11] Patrick Grässle, Henriette Baumann, Philippe Baumann, UML 2.0 in Action - A Project-Based Tutorial, Packt Publishing Ltd, 2005
[12] Scott W. Ambler, The Elements of UML 2.0 Style, Cambridge University Press, 2005

UML Association vs Aggregation vs Composition

Wednesday 18 January 2012

Circular references in constructors

It is not uncommon to have situation when class A references class B and vice versa. This is known as circular dependency and is resolved by using forward declarations.

It is valid and safe to use mutually referenced classes if we initialize references after fully creating classes' instances. But what happens if references are assigned (and probably used) in constructors? Constructor of first class initializes reference to an instance of the second class that is yet to be created...This sounds silly and we can expect all sorts of things - from compile-time and run-time errors to programs running perfectly fine (well, if we are lucky enough...).

References can be implemented as pointer or reference types.

Let's have a look at pointer-based implementation and let us assume we have structures (or classes) implemented like this:

S1.h:

S1.cpp:

S2.h:

S2.cpp:

main.cpp:

We had to pass 0 to S1 constructor as s2 had not yet been declared nor created. This makes S1 constructor to raise access violation exception when it tries to dereference m_pS2 in order to call S2 methods.

If we used references instead of pointers, we would not even have a chance to write the code that compiles:

S3.h:

S3.cpp:

S4.h:

S4.cpp:

main.cpp:

A simple fact that we cannot have a reference (or address) of the object that hasn't yet been created leads to conclusion that it is impossible to create instances of mutually dependent classes where references must be initialized in constructor.

But there is one case when this is actually possible. Possible but not safe. If these structures are members of another (container) structure, it is possible to initialize references in container's constructor initializer list.


main.cpp:

Output:
S1::S1()
S2::Foo()
S2::PrintVal(): -858993460
S2::S2()
S1::Foo()
S1::PrintVal(): 1
S5::PrintVals()
S2::PrintVal(): 2
S1::PrintVal(): 1
S3::S3()
S4::Foo()
S4::PrintVal(): -858993460
S4::S4()
S3::Foo()
S3::PrintVal(): 1
S6::PrintVals()
S4::PrintVal(): 2
S3::PrintVal(): 1

We can see here that:
  • It is possible to set circular references between two classes during their construction if they are members of some container class
  • It is not safe to use circular references in constructors of their classes: dereferencing (and using) reference of the object that is not fully constructed leads to undefined behaviour. In our examples, the wrong value of the member of the class that had not yet been constructed was printed (-858993460 instead of 2)
  • It is safe to use circular references once objects are fully created S5::PrintVals() and S6::PrintVals() print correct values of members of referenced objects. This is similar to the case when some container class A has a member B that must be initialized with the pointer/reference to A (this or *this): that is safe as long as B's constructor doesn't try to access A's members or call A's methods. B has to wait for A to be completely constructed in order to use A's reference safely
One additional note: it is always a good practice to decouple classes (break dependencies between them) as much as possible. This is usually done by using interfaces or some other patterns (e.g. Observer pattern).

Tuesday 10 January 2012

Prefer compile-time to run-time value range checks: use enumerations

In a perfect world, compiler should be able to detect all errors in the code. If types mismatch or value is out of the valid range - compiler should complain. How can we help compiler to achieve this? One answer is: by defining our custom types.

Enumerations

When we define enumeration, we are introducing a new type. Let's say some integer variable can be assigned only certain values, from a predefined set. Function that assigns value to a variable could look like this:



Ok, what happens if someone writes



This code compiles fine but it sets variable to a value out of the valid range and this can lead to some logical errors.

How can we improve this code? Obviously, we can check whether value is valid. If it is not, we can either throw exception, set variable to some default value or just quietly return from a function:



Each time this function is called it will use CPU resources to perform value check. But is it necessary? Can we make this function more optimal in a run-time? Yes, we can: by moving value check from run-rime to compile time! If we define our custom type - enumeration - which defines valid range, we will be able to use compiler to find all places where invalid value is passed:



SetLevel(2) will cause compiler to report an error.

One example of the real-life usage of this approach could be writing a wrapper around Windows Thread API. E.g. SetThreadPriority has an argument nPriority which is of type int and so can accept any integer value despite the fact that valid values are from a predefined set (THREAD_PRIORITY_ABOVE_NORMAL = 1, THREAD_PRIORITY_BELOW_NORMAL = -1, THREAD_PRIORITY_HIGHEST = 2, ...). Passing invalid integer values can be prevented by introducing our enumeration which enumerates all valid values for thread priority:



NOTE: enum value is implicitly casted to int but int value must be explicitly casted to enum type.