Professor David Arnow (Brooklyn College, City University of New York) has developed a C library for distributed programming on Unix systems called DP. The DP project has three main goals: power, simplicity, and implementability. The DP functions should be powerful enough to implement most distributed applications. They should be a simplified interface to the facilities already present in Unix for process management and communication. Additionally, they should be implementable on most distributed computing platforms. DP provides the C programmer with reliable message passing between processes and simplified non-local process spawning. The C-Linda language is a natural continuation of the above goals. It provides a metaphor for concurrent programming that can serve as an abstraction of the functionality provided by DP.
The Linda shared memory space is called Tuplespace. Tuplespace holds one type of data, called tuples. Tuples are ordered typed lists of items. For example, ("foo", 3, 4.3) is a tuple which contains three items, the first being a character string, the second an integer, and the third a floating point number. Tuples can contain both actual and formal items. An actual item contains a specific value, like 3 or 4.3. A formal item, however, acts like a typed placeholder. For example, the tuple ("formal ex.", ? x), where x is declared as an integer, contains a placeholder for an integer value in the second item. The "?" character denotes that a variable is to be treated as a formal, rather than using the value stored in the variable as an actual.
Tuples can be both active and passive. Active tuples contain at least one value that has not yet been evaluated. Processes are created in Linda by sending active tuples into Tuplespace. For example, ("factorial", 7, fact(7)) is an active tuple. When this tuple arrives in Tuplespace, Linda spawns a concurrent process to evaluate fact(7). When that process returns a value (the return value of the function), the value returned replaces the function call, changing the value of the tuple to ("factorial", 7, 5040) and making the tuple a passive tuple. Thus, a passive tuple is a tuple for which all values have been evaluated.
The Linda function out() sends a passive tuple into Tuplespace. For example, out("foo", 3, 4.3) will result in the tuple ("foo", 3, 4.3) appearing in Tuplespace. The function eval() sends an active tuple into Tuplespace. For example, eval("factorial", 7, fact(7)) will result in the active tuple ("factorial", 7, fact(7)) appearing in Tuplespace, and a process being spawned to evaluate the function call fact(7) concurrently. As described above, when the function returns, the value will replace the function call in the tuple, and the tuple will become passive.
The other four Linda functions are in(), inp(), rd(), and rdp(). These functions are used to retrieve tuples from Tuplespace. The arguments to these functions are items in a tuple template or anti-tuple. Essentially, a tuple template is a query that matches tuples in Tuplespace. Tuple templates contain both formal and actual values, just like regular tuples. Matching occurs as follows:
Additionally, C-Linda programs must call their main procedure real_main() and must include linda.h in each code module. Three sample C-Linda programs can be found in the Appendix below.
The implementation uses the client-server model, where the Tuplespace manager is a server, and the worker processes are clients. Clients send active and passive tuples to the Tuplespace manager, which spawns additional worker processes as necessary and adds the tuple to its memory. When clients query the Tuplespace manager, it performs a search of memory for a matching tuple and sends a reply back to the querying client.
The implementation can be viewed as five separate modules: Linda Library, Tuple Handler, Remote Procedure Call, Preprocessor, and Compiler Interface. Each of these modules will be discussed in detail below.
Also in this module are C versions of the six Linda functions. These functions use the varargs library for variable length argument lists. The first argument of each function is a type string, which describes the types of the following arguments, which are the items in the tuple. One of the main responsibilities of the preprocessor is to transform Linda calls into the format needed by these functions. Each of these functions assembles its arguments into a message and sends the message to the Tuplespace server. When a reply is needed (for rd(), rdp(), in(), and inp()), the function blocks until a reply is received from the Tuplespace server.
The current implementation of the Tuple Handler has two major drawbacks. First, storing Tuplespace as two unordered linked lists makes for very inefficient search (on order O(n)). Storing Tuplespace as a sorted structure (for example, a sorted binary tree) would provide significant speedup to tuple searching. Also, the Tuple Handler has no facilities for supporting multiple Tuplespace servers. Forcing distributed Linda to have only one Tuplespace server makes the server a bottleneck on Linda programs with any decent number of worker processes. There are a number of schemes for multiple Tuplespace servers described in [4]. One scheme is to have a hash function for determining which Tuplespace server will service a specified tuple. Then workers would know which server to send their tuples and queries to. Another scheme is to have Tuplespace servers coordinate amongst themselves and have workers deal only with one server. If the first server does not find the tuple to match a query, it sends the query along to the other servers. Adding a fix for both of these drawbacks would result in significantly better performance from the distributed C-Linda system.
/* hello.clc: a simple C-Linda program */
#include "linda.h"
int worker(int num)
{
int i;
for (i=0; i<num; i++)
out("hello, world");
return 0;
}
int real_main(int argc, char *argv[])
{
int result;
eval("worker", worker(5));
in("hello, world");
in("hello, world");
in("hello, world");
in("hello, world");
in("hello, world");
in("worker", ? result);
return 0;
}
/* philosophers.clc: C-Linda implementation of solution to the dining */
/* philosophers problem using mutex. */
/* Modeled after solution in _Operating Systems_ by Tananbaum. */
#include "linda.h"
#include <stdio.h>
#include <time.h>
#define N 5 /* number of philosophers */
#define LEFT (i+N-1)%N /* number of i's left neighbor */
#define RIGHT (i+1)%N /* number of i's right neighbor */
#define THINKING 0 /* philosopher is thinking */
#define HUNGRY 1 /* philosopher is hungry */
#define EATING 2 /* philosopher is eating */
int philosopher(int i);
void take_forks(int i);
void put_forks(int i);
void test(int i);
void think(int i);
void eat(int i);
void mutex_begin();
void mutex_end();
void P(int i);
void V(int i);
int real_main(int argc, char *argv[])
{
int active_philosophers = N, msg_counter=0, rtnval, i;
char message[50];
out("msg counter", 0);
for (i=0;i<N;i++)
out("state", i, THINKING); /* keep track of everyone's state */
for (i=0;i<N;i++)
out("semaphore", i, 1); /* one semaphore per philosopher */
out("mutex", 1); /* mutex for critical regions */
for (i=0;i<N;i++)
eval("philosopher", philosopher(i)); /* spawn philosophers */
while (active_philosophers > 0) {
rtnval = inp("philosopher", 0);
if (rtnval)
active_philosophers--;
else {
rtnval = inp("message", msg_counter, ? message);
if (rtnval) {
fprintf(fp, "%5d: %s", msg_counter, message);
msg_counter++;
}
}
}
fprintf(fp, "\nThat's all folks!\n");
return 0;
}
void send_message(char *msg)
{
int msg_counter;
in("msg counter", ? msg_counter);
out("message", msg_counter, msg);
out("msg counter", msg_counter+1);
}
void mutex_begin()
{
in("mutex", 1);
out("mutex", 0);
}
void mutex_end()
{
in("mutex", 0);
out("mutex", 1);
}
void P(int i)
{
in("semaphore", i, 0);
out("semaphore", i, 1);
}
void V(int i)
{
in("semaphore", i, 1);
out("semaphore", i, 0);
}
void randomsleep()
{
int sleepval;
sleepval = random() % 10;
dpblock();
while ((sleepval = sleep(sleepval)) != 0) {
}
dpunblock();
}
int philosopher(int i)
{
int j=0;
char message[50];
srandom(getpid()*time(NULL));
while ((j++)<10) {
think(i);
take_forks(i);
eat(i);
put_forks(i);
}
sprintf(message, "Philosopher %d: going home\n", i);
send_message(message);
return 0;
}
void take_forks(int i)
{
char message[50];
int state;
mutex_begin();
in("state", i, ? state);
out("state", i, HUNGRY);
test(i);
mutex_end();
P(i);
sprintf(message, "Philosopher %d: picking up forks\n", i);
send_message(message);
}
void put_forks(int i)
{
char message[50];
int state;
sprintf(message, "Philosopher %d: putting down forks\n", i);
send_message(message);
mutex_begin();
in("state", i, ? state);
out("state", i, THINKING);
test(LEFT);
test(RIGHT);
mutex_end();
}
void test(int i)
{
int state, mystate, leftstate, rightstate;
rd("state", i, ? mystate);
rd("state", LEFT, ? leftstate);
rd("state", RIGHT, ? rightstate);
if (mystate == HUNGRY && leftstate != EATING && rightstate != EATING) {
in("state", i, ? state);
out("state", i, EATING);
V(i);
}
}
void think(int i)
{
char message[50];
sprintf(message, "Philosopher %d: thinking\n", i);
send_message(message);
randomsleep();
}
void eat(int i)
{
char message[50];
sprintf(message, "Philosopher %d: eating\n", i);
send_message(message);
randomsleep();
}
/* isprime.c: a program to test the DP C-Linda library. */
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <math.h>
#include <unistd.h>
#include "linda.h"
/* a simple boolean function to test if a number is prime */
int isprime(int number)
{
int i;
for (i=2;i<(int)(sqrt(number));i++)
if (number%i == 0)
return 0;
return 1;
}
/* The worker checks for any "isprime" tuples marked "unknown" and grabs */
/* one out of tuple space, determines if the number is prime, and returns */
/* a tuple with the answer back to tuplespace. When there are no "unknown" */
/* tuples left, the worker exits. */
int worker()
{
int number;
while (inp("char *, ? int, char *", "isprime", &number, "unknown")) {
if (isprime(number))
out("char *, int, char *", "isprime", number, "true");
else
out("char *, int, char *", "isprime", number, "false");
}
return 0;
}
void handlenum(int num)
{
out("char *, int, char *", "isprime", num, "unknown");
}
void handlerange(int min, int max)
{
int i;
for (i=min;i<=max;i++)
handlenum(i);
}
int handleargs(int argc, char *argv[], int *numworkers)
{
int argnum=1, numtotest=0;
if (argc < 2) {
printf("Usage: %s [-options ...]\n", argv[0]);
printf(" where options include:\n");
printf("\t-r min max\tnumerical range to test\n");
printf("\t-n num\t\tnumber to test\n");
printf("\t-w workers\tnumber of worker processes to use\n");
printf("\n note: r and n options can be specified more than once\n");
return 1;
}
while (argnum<argc) {
if (!strcmp("-r", argv[argnum])) {
int min, max;
min = atoi(argv[++argnum]);
max = atoi(argv[++argnum]);
handlerange(min, max);
numtotest += 1+max-min;
}
else if (!strcmp("-n", argv[argnum])) {
int num;
num = atoi(argv[++argnum]);
handlenum(num);
numtotest++;
}
else if (!strcmp("-w", argv[argnum])) {
*numworkers = atoi(argv[++argnum]);
}
else {
printf("Error: unknown argument %s\n", argv[argnum]);
return 1;
}
argnum++;
}
if (*numworkers == 0) {
printf("Error: the number of workers must be specified\n");
return 1;
}
if (numtotest == 0) {
printf("Error: numbers to test must be specified\n");
return 1;
}
return 0;
}
int real_main(int argc, char *argv[])
{
int i, numworkers = 0, number;
if (handleargs(argc, argv, &numworkers))
return 1;
for (i=0;i<numworkers;i++) /* spawn workers */
eval("char *, fun int ()", "worker", worker);
printf("%d workers spawned\n", numworkers);
for (i=0;i<numworkers;i++) /* wait for workers to finish */
in("char *, int", "worker", 0);
printf("The following numbers are primes:\n");
while (inp("char *, ? int, char *", "isprime", &number, "true"))
printf("%d\n", number);
printf("The following numbers are not primes:\n");
while (inp("char *, ? int, char *", "isprime", &number, "false"))
printf("%d\n", number);
return 0;
}
Jim Basney / Oberlin College / jbasney@cs.oberlin.edu
Last Modified: May 19, 1995