AFTER YOU, ALFONSE: A MUTUAL EXCLUSION TOOLKIT*
-- An Introduction to BACI
Bill Bynum (bynum@cs.wm.edu)
Tracy Camp (tcamp@mines.edu)
If neurotic is wanting two mutually exclusive
things at one and the same time, then I'm neurotic as hell.
-- Sylvia Plath, 1963
* This material is based upon work supported by
the National Science Foundation under Grant No. 9996156. Any
opinions, findings, and conclusions or recommendations expressed in
this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation.
Introduction: What is BACI?
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.
C--Compiler Syntax
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:
-
There are no files other than standard input and
output: cout, cin and endl.
-
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.)
-
A string type is supported. BACI also
has built-in string handling functions such as: stringCopy,
stringCompare, stringConcat, etc.
-
Arrays of simple types and of string type
are supported. Array declaration follows the usual C syntax.
-
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().
-
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++.
Concurrency Constructs
- 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( ... );
}
- 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.
- 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.
- 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.
Using BACI
A BACI source file using the C-- compiler should use a .cm suffix. To
execute a program in BACI, there are two steps:
-
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
- 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.
Examples
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
JavaBACI
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.
Obtain a Copy
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:
- SOURCE CODE AND PROJECTS:
- 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.
An Integrated Development Environment
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.