Linda & Concurrency.

There are four classic concurrency problems:

1. Critical Section / Mutual Exclusion,
2. Readers & Writers,
3. Producers & Consumers,
4. Five Dining Philosophers.


Linda - Tuple Space - has uses in Concurrency.

To achieve required results, not only code needs to be written ... tuple space also needs to be filled with initial state.

Critical Section / Mutual Exclusion.	Readers & Writers.
Let's assume that two or more processess want to access critical section of code. Critical section is this program fragment, that can be executed by at most one process at once. We assume that each process which enters critical section, will leave it in finite time. process PCS; begin   repeat     personal_affairs();     Input("ticket");     critical_section();     Output("ticket");   until false end; -- initial state: * ("ticket");	The readers-writers problem relates to an object such as a file that is shared between multiple processes. Some of these processes are readers i.e. they only want to read the data from the object and some of the processes are writers i.e. they want to write into the object. The readers-writers problem is used to manage synchronization so that there are no problems with the object data. For example - If two readers access the object at the same time there is no problem. However if two writers or a reader and writer access the object at the same time, there may be problems. To solve this situation, a writer should get exclusive access to an object i.e. when a writer is accessing the object, no reader or writer may access it. However, multiple readers can access the object at the same time. process Reader; var   r: int32; begin   repeat     personal_affairs();     Input (r: int32, 0);     Output (r+1, 0);     do_read();     Input (r: int32, w: int32);     Output (r-1, w);   until false end; process Writer; begin   repeat     personal_affairs();     Input (r: int32, 0);     Output (r, 1);     Input (0, 1);     do_write();     Output (0, 0);     until false end; -- initial state: * ( 0, 0 );
Producers & Consumers.	Five Dining Philosophers.
There are P > 0 processes in system, which produce certain data, and C > 0 processes which receive data from producers. Between producers and consumers there can be buffer B with capacity BCAPACITY, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data - consumers. Let's notice that a Tuple in Linda - Tuple Space is not a Buffer/FIFO Queue that do_produce() & do_consume() operate on. a Tuple in Tuple Space is only used to store amount of used 'places' in a Buffer/FIFO Queue. BCAPACITY is a constant, total number of 'places' in a Buffer/FIFO Queue. process Producer; const   // B Capacity: 0 ... 107.   int32 BCAPACITY = 107; begin   repeat     personal_affairs();     Input(n: int32);     if (n < BCAPACITY) {       do_produce();       Output(n+1);     } else {       Output(BCAPACITY);     }   until false; end; process Consumer; begin   repeat     personal_affairs();     Input(n: int32);     if (n > 0) {       do_consume();       Output(n-1);     } else {       Output(0);     }   until false; end; -- initial state: * (0);	Five philosophers dine by round table. Before each there's plate. Between plates lie forks. In middle of the table there's serving dish with fish. Each philosopher thinks. When he gets hungry, he reaches for forks laying at his right and left side, then starts eating. When he's done eating, he puts forks away and again devotes himself to thinking. Following conditions have to be met: * Only one philospoher ate with the same fork at the same time. * Each of the philosophers ate only and always with two (and always those which lay near his plate) forks. * No philosopher would die of starvation. * Also we want that each of the philosophers would act the same way. process Philosopher(i); var   int32 i; begin   repeat     think();     Input("room ticket");     Input("fork", i);     Input("fork", (i+1) mod 5);     eat();     Output("fork", i);     Output("fork", (i+1) mod 5);     Output("room ticket");   until false; end; -- initial state: * ("fork", 0); * ("fork", 1); * ("fork", 2); * ("fork", 3); * ("fork", 4); * ("room ticket"); * ("room ticket"); * ("room ticket"); * ("room ticket");

Linda as Database Management System.

Database is data, Database Management System / DBMS / is software that keeps and manipulates database.

There are many Database Management Systems, from Relational Database Management Systems / RDBMS /, to Object Oriented Database Management Systems / OODMBS /, to Hierarchical Database Management Systems, perhaps more.

SQL, language-interface with RDBMS is so holy, as RDBMS have STRONG Roots in Mathematics, Relational Algebra.

... in a way it's powerful, but still complex and unelegant, i think.

... there are Views / pl: Widoki /, PL/SQL, Events - Triggers / pl: Zdarzenia - Wyzwalacze /, Transactions, / pl: Transakcje /, ACID properties, Transaction Isolation Levels / pl: Poziomy Izolacji Transakcji /, Normal Forms at various 'levels' / Pierwsza Postać Normalna, Druga Postać Normalna, ... /, ... Database Tuning / pl: Strojenie Baz Danych / , ... far more.

... i even heard a complaint that someone preferred to store 'XML files in database' instead of proper handling data in relation tables, as a consequence of software-database operations complexity & frustration.

... i am very far from Database Admin expertise levels - it's quite Ambitious & Unappreciated Way ... but still ... it's not my way.

... i don't know anything about Data Warehousing / pl: Hurtownie Danych /, BIG DATA, Data Mining, etc.

... i think Database Tuning is optimization, of either whole Database/DBMS, or it's parts. There are many aspects to optimize - optimizing one/few things at cost of other thing(s).


There are important abstractions over RDBMS, as Java's Hibernate - for example - important bridge between 'Object Oriented Solutions' and RDBMS.

... but i think 'bridge' is not enough, we need simpler ways.


Linda has potential for being new DBMS tool as well, among it's other uses - perhaps many other uses.

Both Linda, as well as Relational Database Management Systems use the idea of a Tuple / pl: Krotka /.

... i think it's important to emphasize that without Transactions Support, any of Database Management Systems is lacking, not good enough to be used commercially ... so Linda also needs Transactions Support if it is to be used as DBMS.

Compared with RDBMS systems, Linda is far simpler, and has very elegant & nice, scientific notation - which can motivate computer programmers, can make their work easier, more enjoyable, quicker.


... in my approach to Linda implementation, Tuples can contain nested / pl: zagnieżdżone / Tuples as well, at theoretically any depth(s) - thanks to that it can store object graphs, with precisely defined state ... and can have many other uses as well.

... but let's not lay / lie so lazily in that 'nest', anyway. ;)

... is including 'lazy evaluation' so lazy?


... i think we should consider both cyclic and acyclic objects graphs if we want this idea to be realized - an idea of using Linda as DBMS.

Perhaps cyclic graphs should have sorted map data structure 'attached', data structure where object names are keys and references to objects are values. That way, as we 'search' through objects graph, we can 'store aside' information about names of objects visited - and avoid proceeding into infinite loop.


Considering Linda-based DBMS requirements - to be able to store object graphs correctly - abstraction, concretization, and inheritance hierarchy issues should be considered as well.


... i think 'read' operation should be fast, it should be one of most important, or perhaps even the most important objective ... then search operation speed can be quite fast.

... is avoiding/defeating data redundancy / pl: redundancja danych, powielanie danych / more important than read/search speed?

... what is more important - addressing 'data redundancy' or addressing 'single point of failure' issues? ... are solutions to these issues mutually exclusive?

... what other needs people require from this 'project'? ... i am open to wishes, suggestions, requests - not only from computer scientists & engineers.

... by serving people that way, i'll try to create market needs - so don't worry about asking, i'll benefit from that as well.

... let's be wary about 'abuses', 'unneccessary intermediaries', 'poisonous people', 'non-symbiotic parasites', etc, ... however.


... see also, if You wish, need, ... : Linda & Tuple Space.

Linda & Tuple Space.

Introduction.

Linda & tuple space are work of Gelernter.

Linda is name derived from porn actress: Linda Lovelace, who later became 'a born again Christian' and a spokeswoman for the anti-pornography movement.




-=- Linda Lovelace. -=-


Linda is a language or notation that is used with tuple spaces, a mechanism that has uses in processes concurrency & synchronization.

There's one big and global tuple space. Processes communicate with each other by putting in the tuple space messages, and by retrieving from tuple space.

Processes are isolated, do not need to know anything about each other, processes do not need to exist at the same time. This helps to decouple objects, increasing software's quality.


'Tuple Space' has uses in the 'Token Game' - for modelling 'places', where tokens are stored, as well. Token Game uses Petri Nets idea, abstracted & concretized different way. Petri Nets are also called P/T Nets or Places / Transition Nets.


Tuple Type, Signature & State.

Tuple's signature is ordered list of data types stored in a tuple.

Tuple has statically determined length.

Tuple's state is it's values written in a binary format, concatenated.

In original work of Gelernter, tuple wasn's a type so a tuple could not contain tuples within. For 'Project Wraithstar's' purposes, tuple is a type.


Simple operations on the tuple space.

* Output(t)

Because of Linda being distributed asynchronous mechanism with the buffer of unlimited size, operation that puts a tuple into space is a nonblocking operation.

Tuple Space should be treated as a Multi-Set, that allows for putting multiple tuples of the same signature and state.

Operation Output(t) puts a tuple into a tuple space. If a tuple t is already present in the tuple space, another copy of t is put in the tuple space.


* Input(s)

A blocking operation that removes a tuple from space. Argument for this method is tuple's signature, for example:

Input(x: int32, c: char) / exact syntax in 'Ola' Programming Language is to be determined still /

If at a given moment there's no tuple with a given signature in the tuple space, then a process performing Input is blocked until requested tuple appears in the tuple space.

In original work of Gelernter, if tuple space contains many tuples with a given signature, then a choice of removed tuple is nondeterministic. There's a rule of fairness in original work as well, but for purpose of 'Project Wraithstar' - we'll assume that tuples with a given signature are put and removed as in a FIFO queue. Similarly processess that attempt to remove a tuple should use a timestamp associated with a request, as a part of UUID / Universally Unique ID /.


* Read(s)

Similar to Input(s), Read(s) retrieves a tuple with it's data from the tuple space - but does not remove it from tuple space.

Read(s) is a blocking operation, and depending on timestamps & UUIDs processess removing or retrieving tuple might be awakened in varying orders & amounts.


* Try_Input(s) and Try_Read(s).

Nonblocking versions of Input(s) and Read(s) methods.


Selective Choice.

There's option of specifying values of tuple's selected elements, of a tuple we wish to remove / retrieve from a tuple space.

For example we can remove a tuple with a signature (int32, char, int32) whose first value is 3. Appropriate instruction looks as follows:

Input(3, c: char, x: int32)


There are differencies between instruction semantics:
- Input (x, c)
- Input (x: int32, c)
- Input (x, c: char)
- Input (x: int32, c: char)


Gaps.

Linda has one more extension. In the tuple space, there can be stored tuples with 'gaps'.

'Gap' is a 'value' of a specified type, that 'matches' to any value of this type.

Gaps are noted as a star with a type.

For example, a tuple:

(3, * : char, 'a', * : int32)

Is a tuple with a signature:

(int32, char, char, int32)

Containing two gaps: on a second and fourth position.


Such tuple can be retrieved or removed from a tuple space, by performing any of given operations:

Input (3, 'c', x: char, 8)
Input (i: int32, x: char, 'a', j: int32)


Let's notice that every 'gap' has a strictly given type.


For putting gapped tuples into space, method Output can be used. In a gap-place we'll just write a type with a variable name, but variable name has no meaning here.

Output (3, c: char)

Will put into tuple space a tuple, that on a second coordinate has a type and is a gap.


Links.
- Linda as Database Management System,
- A written lecture about Linda, in a polish language,
- Linda & Concurrency,
- Tuple Data Type.