AFTER YOU, ALFONSE: A MUTUAL EXCLUSION TOOLKIT*

Concurrency concepts and synchronization techniques are important issues in computer science. Due to the increasing emphasis on parallel and distributed computing, understanding concurrency and synchronization is more necessary than ever. To obtain a thorough understanding of these concepts, practical experience writing concurrent programs is needed. BACI is an option to obtain this desired "hands-on" experience with concurrent programs.

BACI stands for Ben-Ari Concurrent Interpreter. The compiler and interpreter originally were procedures in a program written by M. Ben-Ari, based on the original Pascal compiler by Niklaus Wirth. The original version of the BACI compiler and interpreter was created from that source code and was hosted on a PRIME mainframe. After several modifications and additions, this version was ported to a PC version in Turbo Pascal, to Sun Pascal, and to C. Finally, the compiler and interpreter were split into two separate programs. Recently, a C-- compiler has been added to the BACI suite of programs to compile source programs written in a restricted dialect of C++ into PCODE object code executable by the interpreter. Compared with other concurrent languages, BACI offers a variety of synchronization techniques with a syntax that is usually familiar. Any experienced C or Pascal programmer could use BACI within hours.

We note that BACI is discussed in the following textbook chapter: Bill Bynum and Tracy Camp, BACI: The Ben-Ari Concurrent Programming System, Appendix E in Operating Systems: Internals and Design Principles: Fifth Edition, by William Stallings, pp. 772-784, Prentice Hall, 2005.

BACI's C-- compiler constructs are a subset of C++ compiler constructs. In other words, C-- follows C/C++ syntax. Some restrictions and new types are applied, such as:

1. There are no files other than standard input and output: cout, cin and endl.
2. Only simple C/C++ types are available in C-- BACI: int and char. Constants (const) of simple types are also supported. (All variables must be declared at the beginning of the code block in which they appear.)
3. A string type is supported. BACI also has built-in string handling functions such as: stringCopy, stringCompare, stringConcat, etc.
4. Arrays of simple types and of string type are supported. Array declaration follows the usual C syntax.
5. Procedures and functions are supported. Standard scope rules apply. Recursion is supported. Parameter declarations are pass-by-value or pass-by-reference. Execution begins with a call to main().
6. The executable statements are if-else, switch/case, for, while, do-while, break and continue. The syntax of these statements is as in standard C/C++.

1. cobegin

A list of processes to be run concurrently is enclosed in a cobegin block. Such blocks cannot be nested and must appear in the main program. The PCODE statements belonging to the listed procedures are interleaved by the interpreter in an arbitrary, 'random' order, so that multiple executions of the same program containing a cobegin block will appear to be non-deterministic. The main program is suspended until all of the processes in the cobegin block terminate, at which time execution of the main program resumes at the statement following the ending of the block. Here is an example:

cobegin {
proc1( ... ); proc2( ... ); ... ; procN( ... );
}


2. semaphores

semaphore is a predeclared type in BACI. It is a non-negative valued int variable that can be accessed only in restricted ways. BACI also has binarysem subtype which is a binary semaphore, one that only assumes the values 0 and 1. Semaphore functions includes:
• initialsem ( semaphore, integer_expression ): it is the only method for initializing a semaphore of either type in BACI.
• p ( semaphore) or wait (semaphore): if semaphore > 0 then decrement semaphore by 1 and return, allowing caller to continue. If semaphore = 0, then put p's caller to sleep.
• v ( semaphore) or signal (semaphore): if semaphore = 0 and one or more processes are sleeping on semaphore, then randomly awake one of these processes. If no processes are waiting on semaphore, then increment semaphore by one. In any event, v's caller is allowed to continue.


3. monitors

BACI also supports Hoare's monitor concept with some restrictions. A monitor is a C-- block with some additional properties. All functions in the monitor variables are visible from the outside, but the monitor variables are not accessible outside of the block and can only be accessed by the monitor functions. In BACI, a monitor can be declared only at the outermost, global level. Monitors can not be nested. Only one procedure or function of the monitor block can execute at any one time. This feature makes it possible to use monitors to implement mutual exclusion. Three constructs are used by procedures and functions of a monitor to control concurrency: condition variables, waitc (wait on condition), and signalc (signal a condition).
• condition variables can only be accessed by the monitor's functions. A condition variable never actually 'has' a value; it is somewhere to wait or something to signal.
• void waitc (condition cond, int prio): the monitor process is blocked and assigned the priority prio for being re-awakened. This blocking action allows some other monitor process to execute, if one is ready.
• void waitc (condition cond): has the same semantics as the waitc call, but the wait is assigned a default priority of 10.
• void signalc (condition cond): wake some process waiting on cond with the highest priority; otherwise do nothing.
• void empty (condition cond): returns 1 if there are no processes waiting on condition cond and 0 otherwise.
4. other concurrency constructs
• atomic keyword: if a function is defined as atomic, then the function is non-preemptible. The interpreter will not interrupt an atomic function with a context switch.
• void suspend ( void ): puts the calling thread to sleep.
• void revive ( int process_id ): revives the process with the given id.
• int which_proc( void ): returns the process number of the current thread.
• int random (int range): returns a "randomly chosen" integer between 0 and range -1, inclusive.

A BACI source file using the C-- compiler should use a .cm suffix. To execute a program in BACI, there are two steps:

1. Compile a ".cm" file to obtain a PCODE file (.pco)

Usage: bacc [optional_flags] source_filename
Optional_flags:
-h show this help
-c make a .pob object file for subsequent linking
2. Interpret a PCODE file (.pco) to execute the program

Usage bainterp [optional_flags] pcode_filename
Optional_flags:
-d enter the debugger, single step, set breakpoints
-e show the activation record (AR) on entry to each process
-x show the AR on exit from each process
-t announce process termination
-h show this help
-p show PCODE instructions as they are executed

There is a shell script, baccint, that will call the compiler and then call the interpreter for you. It passes the options that you give it along to the interpreter. If you are using the Pascal compiler syntax, then the source file should be with a .pm suffix, and you compile the program with the bapas compiler.

The following listing was produced by the C-- BACI compiler. The number to the right of the line number is the PCODE offset of the instruction begins that line. The BACI compiler creates this listing from the file "incremen.cm". The listing is placed in the file "increment.lst". An "incremen.pco" file is also created; this file is used by the interpreter.

BACI System: C-- to PCODE Compiler, 10:31 21 Oct 1997
Sourcefile: incremen.cm Fri Sep 8 16:51:00 1995

line   pc
1       0    const int m = 5;
2       0    int n;
3       0
4       0    void incr (char id)
5       0    {
6       0        int i;
7       0
8       0        for (i = 1; i <= m; i = i + 1)
9       14      {
10      14             n = n +1;
11      14             cout Ç id Ç " n =" Ç n Ç "  i =";
12      25             cout Ç i Ç " " Ç id Ç endi;
13      31       }
14      32   }
15      33
16      33   main()
17      34   {
18      34        n = 0;
19      37        cobegin
20      38        {
21      38            incr( 'A' ); incr( 'B' ); incr( 'C');
22      50        }
23      51        cout Ç "The sum is " Ç n Ç endl;
24      55   }

The following listing was produced by the BACI interpreter. The interpreter executes the program that was compiled into the file "incremen.pco".

Source file: incremen.cm Wed Oct 22 21:18:02 1997
Executing PCODE ...
C n =1 i =A n =1 C2 i =
1 A
C n =4 i =2 C
B n =A n =5 i = 24 A
  i =1 B
AC n = n =6 i =3 C6 i =3
A
C n =7 i =4 C
B n =9 i=2 BA n =8
  i =4 A
C n =8 i =5 A n =9C
  i =5 A
B n =10 i =3 B
B n =11 i =4 B
B n =12 i =4 B
The sum is 12

The BACI system can now execute in Java. JavaBACI consists of all BACI applications, including the C and Pascal compilers, disassembler, archiver, linker, and command-line and GUI PCODE interpreters. The input, behavior, and output of programs in JavaBACI are identical to the input, behavior, and output of programs in the original BACI system (our C implementation of BACI). In JavaBACI, one continues to write concurrency programs in C-- or Pascal (not Java). JavaBACI will execute on any computer that has an installation of the Java Virtual Machine. Specifically, users need the Java Runtime Environment (java 1.5.0 or higher).

To use JavaBACI, download the JavaBACI Classes. To extract the JavaBACI system, double click on the file or type java -jar JavaBACIclasses-2007Nov08.jar. To execute, browse into the scripts directory and type javabaci xxx (or javabaci.bat xxx on a CYGWIN or Windows machine), where xxx is one of the original BACI commands (e.g., bacc, bapas, bainterp, etc.).

If you would like to view or modify the JavaBACI source code, download the JavaBACI source code file. Users need the Java Development Kit (javac 1.5.0 or higher) to use the JavaBACI source code. The JavaBACI source code contains all the JavaBACI classes; thus, if you only view the code (not modify it), recompilation of JavaBACI is not required.

Currently, the BACI system can be compiled in Linux, RS/6000 AIX, Sun OS, SGI IRIX, and DOS with minimal modifications to the Makefile file. If you use different hardware platform than these, and if you can give us access to your hardware, we will try to install the BACI system for your machine type. We can be reached at "bynum AT cs DOT wm DOT edu" or "tcamp AT mines DOT edu".

Click on one of the following files to download:

• USER GUIDES:
  BACI C-- Compiler User Guide (in pdf): updated July 14, 2003
  BACI Pascal Compiler User Guide (in pdf): updated July 14, 2003
  BACI GUI User Guide (in pdf): updated November 05, 2002
  All BACI user guide documents (in pdf): updated July 14, 2003
  All BACI user guide documents (in ps): updated July 14, 2003
  All BACI user guide documents (in LaTeX): updated July 14, 2003
  
  
  
  
• SOURCE CODE AND PROJECTS:
  BACI projects (tarfile): updated July 17, 2001
  JavaBACI source code: updated Nov 8, 2007
  BACI source code: updated Nov 25, 2007
  
  
  
  
• OTHER PROJECTS by Florence Appel at Saint Xavier University.
  
  
• EXECUTABLES:
  JavaBACI Classes: updated Nov 8, 2007
  BACI DOS executables: updated November 09, 2005
  Note: The BACI DOS executables run satisfactorily in the MS-DOS Command Prompt Window of any of the Microsoft Windows operating systems (Windows 95, 98, NT, 2000).
  BACI LINUX executables (32 bit): updated Nov 25, 2007
  BACI LINUX executables (64 bit): updated Oct 1, 2012
  BACI RS/6000 AIX executables (old version): updated May 15, 2003
  BACI SGI IRIX executables (old version): updated April 18, 2001
  BACI SUN OS executables (old version): updated May 15, 2003
  

If you decide to use BACI in one of your courses, please let us know!

Past updates to the BACI system are archived.

Moti Ben-Ari announces the release of jBACI, an integrated development environment for learning concurrent programming by simulating concurrency. It was built from the BACI compilers and a modified version of David Strite's BACI GUI. jBACI also implements extensions to the source languages that allow graphics programs to be written.

Moti asks that you send him a message if you use jBACI so that he can keep you informed of updates.