On Multithreading

Hans-Dieter.Dreier@materna.de Hans-Dieter.Dreier@materna.de
Thu, 20 May 1999 11:48:28 +0200

Content-type: text/plain; charset="ISO-8859-1"
Content-transfer-encoding: quoted-printable

On Multithreading

I'd like to discuss the pros and cons and possible implementations of multi=
threading for our environment,
especially their impact on memory management (short: MM) and object access.

What is multithreading and what is it good for?

Multithreading is the ability to run more than one execution thread on the =
same memory data set.
Each thread has its own virtual machine (or if compiled to machine language=
, its own execution context).
Data are shared, although some data structures (usually the stack) may effe=
ctively be private to a specific thread,
simply because other threads do not have references pointing to them.

Multithreading allows implementation of server applications that may serve =
multiple clients
without having to maintain the execution context switches manually.
Examples are web servers, database servers, print servers, terminal servers=
, process monitors and debuggers.

What are the problems?

1. Object may have moved due to reallocation or compacting

We're assuming that MM (more specifically, GC) is the only instance that ma=
y move objects.
If addresses of objects are stored in places where they are not accessible =
by MM,
it cannot fix up such addresses. This applies to local variables inside the=
 Ultra C++ runtime system.
It can happen even in a single-threaded environment if objects can be moved=
, so we need to address this problem anyway.

2. Concurrent changes to the same object

More than one thread may change an object at the same time, thus creating a=
n inconsistent state.
To make the situation even more complicated, multiple updates to multiple r=
elated objects (eg data records and indexes)
may form a "transaction" that requires the affected objects not to be chang=
ed by other threads
until the transaction is completed.
Depending on the "isolation level", a thread trying to read access an objec=
t that is part of an ongoing write transaction may...

 - be suspended until the transaction is committed (or some timeout expires=
 - see the old (unaltered) state until the transaction is committed,
 - see the current (inconsistent) state.

What can be done to solve these problems?

1. Object movement issue

a) Pointers can be made accessible to MM, thus allowing them to be fixed up=

 - No optimisations possible for these pointers since they may change any t=
ime. They must be declared "volatile".
 - Overhead when creating or deleting these pointers since MM's access mech=
anism must be maintained.

b) Objects for which addresses are held will be locked against movement.
This would require a semaphore for each such object.

 - Memory overhead for each object (semaphore).
 - Potential overflow problem for these semaphores.
 - Creating, deleting such a pointer and changing such a pointer's value (b=
y assignment)
   is slow because the referenced object must be determined and the semapho=
re(s) must be maintained.
   Performing pointer arithmetic is fast, however, because it can be assume=
d that the same object keeps to be referenced.
 - May pose a problem to MM if it needs to move an object that is locked.

IMO approach a) is better.

2. Transaction management

This issue is well known from databases and it is one of the most important=
 factors that limit their performance.
Because all the solutions I can think of carry a heavy performance penalty,
and because we do not primarily want to create a database management system=
I'd suggest to leave this to be implemented at a higher level eventually.

Do you have any ideas concerning these subjects?



Hans-Dieter Dreier

Content-type: text/plain; charset="ISO-8859-1"
Content-transfer-encoding: quoted-printable

a16106a.txt IA5 DX-MAIL X.400 User Agent=