Programming in a multithreaded environment can be tricky. The key is to synchronize your threads' access to the data structures that you define. The classical way to synchronize threads is to wrap a mutex around each critical section through the use of a semaphore. In other words:

acquire_sem(a_protection_semaphore)
/*
  Critical Section:
  Manipulate the Data Structure Here.
*/
release_sem(a_protection_semaphore).

This is a perfectly valid use of a semaphore—but at a cost. Typically, acquiring and releasing a semaphore takes about 35 microseconds. This overhead can add significantly to the cost of manipulating the data structure. It's not unusual for the semaphore calls to take more time than the critical section itself.

There is a better way. In the app server, we use a slight variation on the semaphore idea which some of us called the "benaphore." A benaphore is a combination of an "atomic" variable (a variable that's used in atomic_add() calls) and a semaphore. You use the atomic variable to test whether the current invasion of the critical section needs the mutex, and then you acquire the semaphore only if the mutex is called for. On the way out of the critical section, the variable is once again checked to see if some other thread is waiting to enter the section; if there is such a thread, the semaphore is released. This is easier to express in code.

First, we declare and initialize our variables.

long benaphore_atom;
sem_id benaphore_sem;

long init_benaphore()
{
   benaphore_lock = 0;
   benaphore_sem = create_sem("benaphore", 0);

   if (benaphore_sem < B_NO_ERROR)
      return B_ERROR;
   else
      return B_NO_ERROR;
}

Next, we define two new functions, acquire_benaphore() and release_benaphore().

void acquire_benaphore()
{
   long previous_value;
   previous_value = atomic_add (&benaphore_atom, 1);

   if (previous_value > 0)
      acquire_sem(benaphore_sem);
}

void release_benaphore()
{
   long previous_value;
   previous_value = atomic_add (&benaphore_atom, -1);

   if (previous_value > 1)
      release_sem(benaphore_sem);
}

Finally, we replace the acquire_sem() and release_sem() calls with calls to acquire_benaphore() and release_benaphore().

acquire_benaphore();
/* Critical Section */
release_benaphore();

Before each trip into the critical section, the visiting thread checks the value of the atomic variable and, at the same time, increments the variable's value (this retrieve-and-increment simultaneity is the function's atomicity). If the pre-incremented value isn't 0, then some other thread is currently in the critical section and so our access must be controlled by the semaphore. Conversely, if the pre-incremented atomic value is 0, then our thread can charge on in without waiting to acquire the semaphore.

Now consider what happens on the way out of the critical section. Again the atomic variable's value is retrieved and set (decremented, in this case) at the same time. A pre-decrement value that's greater than 1 indicates that one or more threads is waiting to enter the critical section: We give the next thread the go-ahead by releasing the semaphore. On the other hand, if the atomic value is 1, no other thread is waiting (remember, our thread incremented the atomic value to 1 itself). So we move on without releasing the semaphore.

Why is the benaphore better than the plain semaphore? Because checking the value of an atomic variable is a *lot* faster than acquiring a semaphore. In the case where the critical section is rarely contested (in other words, where the section is usually visited by only one thread at a time), the time saved can be enormous: An uncontested trip through the critical section that's protected by a benaphore has an overhead of under 1.5 microseconds. That's twenty times faster than using a semaphore.

Of course, the benaphore imposes an overhead of its own (the atomic variable check); this overhead is unnecessary if there's a lot of contention for the critical section. But even in the worst case, the atomic variable overhead gets lost in the noise of the context switch.

As its name implies, CodeGen, Inc. is in the business of generating code. The three-person company, located in San Francisco, serves the computer industry with products such as SmartAlloc™, a C memory allocator; SmartCollect™, a garbage-collecting memory allocator; and SmartFirmware™, an OpenFirmware implementation for embedded systems. They also do contract programming.

Chairman Parag Patel says the BeBox is the only system that's fun and easy to program and use. “The Mac ceased being fun quite some time ago, and PCs have never been fun under any operating system—it really beats programming for Windows NT (shiver!). As for UNIX, see 'The UNIX-HATERS Handbook' for more comments.”

“In many ways, the BeBox is what I wish the Mac could be. It's a way cool box with a nice lightweight OS and class library, it has multithreading that doesn't suck, reliable memory-protection, enough POSIX stuff to port things easily, and a database for a file system. Tons of I/O is nice too.”

Thomas J. Merritt, president of CodeGen, isn't sure what business Be will end up in, but says, “It's clear with the interest it's generating and the coolness of the box, it's going to find a niche somewhere.”

“I think it would make a terrific networking server. The only other thing that comes close in price/performance is a generic PC loaded with FreeBSD, but that's a pain to configure. Windows NT and pay-for UNIX cost more, and other desktop OS's don't offer memory protection or other niceties the BeBox has.” Parag adds, “With the GeekPort, the BeBox could also be nice as a user-friendly factory floor controller.”

Parag and Thomas plan to do contract programming (such as device driver ports) for the BeBox in addition to developing their own products. So far, they've ported SmartAlloc to the BeBox, and plan to port their host implementation of SmartFirmware later this summer.

“We'd like to create something for the BeBox. Maybe a decent HTML WYSIWYG editor, of which none exist as yet on any platform. Heck, something as simple as WriteNow for the Be would be nice, too.”

For more information on CodeGen, Inc., visit their web site at http://www.cgt.com or send e-mail to Parag or Thomas at parag@cgt.com or tjm@cgt.com.

We all agree we need good cryptography. It's good for privacy, it's good for business. The only remaining obstacles are governments, bureaucrats, politicians, individuals, and groups who use national security and the fear of crime to further their quest for power, budgets, and votes. The argument is this: Criminals and enemies can't be allowed to communicate under the cloak of impenetrable cryptography, the consequences would be too dire for the nation's security, the safety of our families and possessions. As a result, our government has banned export of hard encryption technology and has promoted various soft encoding schemes for domestic purposes. Both are failing and there is hope that fearful and brutish common sense will give way to facts and the calculus of consequences. Or, it might just be a dollop of good old greed lubricating the wheels of commerce.

Domestically, the talk of putting our keys in escrow isn't going down very well. For all the reassuring talk of judicial oversight and due process in allowing government agencies access to our encrypted data, we harbor a healthy distrust of the police, bureaucrats, and intelligence agencies. Perhaps this is nothing but a projection of our low self-esteem. Or just a reaction to the enduring spectacle of corruption and incompetence in various guardian agencies. We don't trust the trustees. Furthermore, an escrow scheme might violate principles of good design: The keys have to be stored under lock and key. That lock could be broken by negligence or malice. A single point of failure might expose a large number of keys. The problems don't stop here. More generally, any encryption soft enough to be penetrated by bureaucrats is also vulnerable to sophisticated hackers and criminals, or an alliance of both. Consider the vintage air traffic control systems. Government might not enjoy a monopoly on the best computers and programmers. As a result, billions of electronic messages and transactions might be vulnerable to sophisticated crooks. In the name of fighting crime, we might abet it.

Internationally, the situation is worse. Hard cryptography is considered a munition and its export is illegal. As a result, US cryptography companies are losing export business and software publishers have to forbid export of US products containing "dangerous" encoding; they must create weaker versions for overseas markets. This in a world where software travels in a pocket, on a laptop, or in files over the Net. Besides losses and inconvenience, these ineffectual restrictions engender scorn and ridicule on the international scene. There is hope, though. For years, Phil Zimmerman, the inventor of PGP (Pretty Good Privacy), was harassed by the Feds. He was suspected of violating the law restricting the export of his public-key encryption software, as if, for the reasons stated above, anyone could prevent his code from traveling abroad. With a reluctant bow to reality, charges have been dropped—for now, they said. And, once again, Japan, Inc. is coming to the rescue, providing helpful disruption. NTT, the big and powerful Japanese telephone company, helped by a constitution much more protective of privacy than ours, is preparing to market hard encryption chips. Now our politicians have the fig leaf they need. Instead of using the fear of crime to get votes, they can use the fear of losing jobs. We can't let foreign companies dominate the encryption market and take jobs from US workers: Let's update our legislation. It's nice to see business interests aligned with our privacy needs.

As one of our investors says, Be was born on the web. So more than established businesses, we need the web to gain critical mass, to reach and support developers and customers all over the world. Soon we'll sell the BeBox on the web. We'll help developers market their applications and deliver software on the web. Micro transactions, the delivery of intellectual property, even the availability of play-only content, all depend on the worldwide availability of unencumbered hard cryptography. Call it what you will: Greed, commerce, or the need for privacy, governments (not just ours) will have to bow to reality and stay out of the way.