A Distributed Implementation of the C-Linda Programming Language

Jim Basney
Computer Science Program
Oberlin College
May 1995


Introduction

As the cost of networks of workstations has decreased relative to the cost of mainframes and parallel machines, there has been increased interest in distributed systems. Conceptually, a distributed system is a parallel machine where the processors are connected by a network rather than a local bus. Users log on to a workstation and are presented with the illusion of a single user, single processor system. However, their files may be on a file server somewhere on the network, and their processes may be running on many different remote machines. The motivation behind distributed systems is the realization that allocating a processor to each user is inefficient. Often, many of the processors will be idle (while the users talk on the phone or grab a pizza), while a few users will be starving for CPU time. Distributed systems solve this problem by allocating the processors on the network to the users who need them. This provides a more efficient use of resources, and allows for parallelism across the network, which can result in a significant speedup for problems with good parallel solutions. Distributed systems can have significant processing overhead, however. Managing non-local processes causes network traffic and computation (for load balancing) that would not otherwise be needed in non-distributed operating systems or programs. Additionally, passing data over a network is considerably slower than passing it over a local bus. This makes a distributed machine slower than a shared-memory parallel machine. However, if implemented well, I believe the benefits of distributed systems outweigh the costs.

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 C-Linda Language

The C-Linda programming language is the combination of the C and the Linda languages. Linda, developed by Professor David Gelernter (Yale University), is a coordination language. It provides six functions for concurrent process coordination that can be added to any sequential programming language, conforming to that language's function call syntax. Thus, unlike with many other modern parallel languages, the Linda programmer does not need to learn an entirely new computational language, but rather only needs to learn the Linda primitives for adding concurrency to the language that the programmer is most familiar with.

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:

For example, the tuple template ("data", ? x), where x is declared as an integer, will match the tuple ("data", 5). When a match occurs, data is returned to a formal template item when it matches an actual tuple item. So, in the example above, x will get the value 5 when the match occurs. Thus, the value is retrieved from Tuplespace. The in() call will remove the matched tuple from Tuplespace, whereas the rd() call will not (i.e., essentially returning a copy of the tuple to the querying process). The inp() and rdp() calls are predicate versions of in() and rd(). The predicate versions will return 1 if a match is found and 0 otherwise. The non-predicate versions will block until a match is found. Thus, the above example can be thought of as follows. One process makes the call out("data", 5), and a second process makes the call in("data", ? x). The out() call places in the tuple ("data", 5) into Tuplespace. When the in() call returns, x will have the value 5, and the tuple ("data", 5) will have been removed from Tuplespace.

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.

Project Overview

I chose to implement a "compiler" for the C-Linda language as a preprocessor and a C library that prepares C-Linda code for compilation by the C compiler. This scheme has a number of benefits over writing a C-Linda compiler by hand. First, it required less work, making this a project which I could complete in the time allotted. Second, it made the implementation more portable, i.e., where ever there is a C compiler and an installation of DP, the C-Linda "compiler" should work. This did, however, provide a number of implementation challenges, because the information available to the compiler (for example, the parse tree) needed to be constructed by the C-Linda layer when necessary. This will be discussed further in later sections. Thus, the C-Linda layer provides an interface to the DP layer, which in turn provides an interface to the C (with system calls) layer.

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.

Linda Library

The Linda Library is a C module in the C-Linda library, which is linked with any compiled C-Linda programs. The C main() function is defined in this module. When a C-Linda process starts, the main() function reads the DP "semantic packet," which is a structure which contains the instructions for the new process. If this packet is empty, then the process is the first Linda process. In this case, main() initializes the DP system, spawns the Tuplespace manager, and calls the user-defined real_main(). The Tuplespace manager process has a semantic packet message signifying that it should run the Tuple Handler routine. Thus, the main() function calls tuplehandler() in this case. Otherwise, the process is a Linda worker process, and the semantic packet contains instructions for that process, namely, which function to call and what arguments to call it with. Thus, in this case the main() function calls the Remote Procedure Call module (described later), passing it the instructions from the semantic packet.

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.

Tuple Handler

The Tuple Handler is a C module in the C-Linda library which contains the code for the Tuplespace server. When executed, the tuplehandler() function waits for messages from Linda worker processes. When a message arrives, it handles the tuple or query as appropriate. The Tuple Handler keeps two linked lists of tuples: an active list and a passive list. When an active tuple arrives, it spawns a process for each function call in the tuple, to evaluate the calls concurrently. Then, it puts the active tuple on the active list. When a reply is received from all of the processes for that active tuple, it moves the tuple from the active list to the passive list. When a passive tuple arrives, it adds it to the passive list. When a query arrives, it searches the passive list for a match, and returns tuple data in reply if a tuple is found. Otherwise, it returns a "tuple not found" message for predicate queries, and enqueues non-predicate queries. These queued queries are checked for each new tuple added to the passive list, to see if the new tuple satisfies any of the queries.

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.

Remote Procedure Call

The Remote Procedure Call module is also a C module in the C-Linda library. This module contains the function rpc(), which is executed by each worker process spawned by the Tuple Handler. The rpc() function uses the instructions given in the DP semantic packet to assemble a function call with the specified parameters. To do this, the semantic packet (sent by the Tuple Handler) contains a type string, a function pointer, and the actual values of each of the parameters. The rpc() function puts each of these values into a variable, and dereferences the function pointer, giving the parameter variables as parameters to the function call. One result of this scheme is that rpc() will not work across multiple architectures, where it can not be guaranteed that function pointer values are uniform across binaries. Another result is that there needs to be a separate case in the C code for each possible argument type in the dereferenced function. This makes it impossible to generalize the implementation to accept functions with an arbitrary number of arguments. In this implementation, I have limited the user to function with up to 5 arguments. The question of how to solve this generally is still open.

Preprocessor

The Preprocessor is a C program generated by the Unix lex program that converts C-Linda programs to the syntax needed by the C-Linda library. The Preprocessor adds format strings containing type information to all Linda calls. To do this, it keeps track of the types of all variables and functions in the current context while scanning through the C-Linda program. Additionally, it changes the Linda '?' operator to '&' for all parameters in Linda calls, except for variables of character pointer type (i.e., string), for which it just removes the '?'. Thus, any formal parameters are passed by address, enabling the Linda functions to return the found value in the parameter. The Preprocessor also converts the active tuples in eval() calls so that they are not evaluated before the call. To do this, it breaks up function calls into a function pointer and argument list. For example, the call eval("worker", worker(5)), where worker is a function which returns an integer value, will be converted by the Preprocessor to eval("char *, fun int (int)", "worker", worker, 5). As described above, the function pointer is dereferenced in the Remote Procedure Call module.

Compiler Interface

The Compiler Interface is a C program that presents the distributed C-Linda system to the programmer in the form of a compiler. When the user types "clc -o [exename] [sourcename] ...", the Compiler Interface calls the Preprocessor for each source file, then calls the C compiler to produce the executable, linking with the C-Linda library. Additional arguments to clc are passed directly on to the C compiler.

Conclusions

I have completed a distributed implementation of a subset of the C-Linda programming language using the DP library. This subset is large enough to provide a powerful, high-level interface for distributed programming. As discussed above, there are open questions to be answered and improvements to be made to this implementation. For example, adding the ability to have multiple Tuplespace servers would significantly improve the performance and usefulness of the system. Additionally, the current implementation does not support a number of the types specified in [6]. It is my hope that work will continue on this project, by Professor Arnow, myself, and others, and that many of these questions will be answered and improvements will be made.


Bibliography

  1. Shakil Ahmed, Nicholas Carriero, and David Gelernter. A Program Building Tool for Parallel Applications. DIMACS Workshop on Specifications of Parallel Algorithms, Princeton University, May 1994.

  2. Sudhir Ahuja, Nicholas Carriero, and David Gelernter. Linda and Friends. IEEE Computer, Aug. 1986, Vol. 19, No. 8, pp. 26-34.

  3. David Arnow and Haibin Jiu. Notes on Using the DP Library. Brooklyn College, Brooklyn, NY. October 1993.

  4. Robert Bjornson. Linda on Distributed Memory Multiprocessors. Ph.D. Dissertation, Technical Report 931, Yale University Department of Computer Science, Nov. 1992.

  5. Nicholas Carriero and David Gelernter. Coordination languages and their significance. Communications of the ACM, Feb. 1992, Vol. 35, No. 2, pp. 97-107.

  6. Nicholas Carriero and David Gelernter. How to Write Parallel Programs: A First Course. Cambridge, Massachusetts: The MIT Press, 1990. Chapter 3: Basic Data Structures, Appendix: C-Linda Reference Manual.

  7. Nicholas Carriero and David Gelernter. Tuple analysis and partial evaluation strategies in the Linda pre-compiler. Languages and Compilers for Parallel Computing, edited by D. Gelernter, A. Nicolau and D. Padua, Research Monographs in Parallel and Distributed Computing, MIT Press, 1990, pp. 114-125.

  8. Nicholas Carriero and David Gelernter. Technical Correspondence on Linda in Context. Communications of the ACM, Oct. 1989, Vol. 32, No. 10, pp. 1255-1258.

  9. Nicholas Carriero and David Gelernter. Coordination Languages and Their Significance. Technical Report 716, Yale University Department of Computer Science, July 1989.

  10. Nicholas Carriero and David Gelernter. Linda in Context. Communications of the ACM, April 1989, Vol. 32, No. 4, pp. 444-458.

  11. David Gelernter. Mirror Worlds: or The Day Software Puts the Universe in a Shoebox... How it Will Happen and What it Will Mean. Oxford University Press, 1991.

  12. David Gelernter and Suresh Jagannathan. Programming Linguistics. Cambridge, Massachusetts: The MIT Press, 1990. Chapter 9: Parallel Languages.

  13. K. Kahn and M. Miller. Technical Correspondence on Linda in Context. Communications of the ACM, Vol. 32, No. 10, Oct. 1989, pp. 1253-1255.

  14. L. Kale. Technical Correspondence on Linda in Context. Communications of the ACM, Vol. 32, No. 10, Oct. 1989, pp. 1252-1253.

  15. Wm Leler. Linda meets Unix. IEEE Computer, Vol. 23, No. 2, Feb. 1990, pp. 43--55.
  16. James Narem. An Informal Operational Semantics of C-Linda V2.3.5. Technical Report 839, Yale University Department of Computer Science, Dec. 1990.

  17. G. Schoinas. Issues on the Implementation of POSYBL: A free Linda implementation for Unix Networks. Department of Computer Science, University of Crete. 1991.

  18. E. Shapiro. Technical Correspondence on Linda in Context. Communications of the ACM, Vol. 32, No. 10, Oct. 1989, pp. 1244-1249.


Appendix

Example 1

/* 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;
}

Example 2

/* 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();
}

Example 3

/* 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;
}

Return to Jim Basney's Home Page
Jim Basney / Oberlin College / jbasney@cs.oberlin.edu
Last Modified: May 19, 1995