|
Be Newsletter
Issue 26, June 5, 1996
Table of Contents
Be Demo Tour: Michigan
- UNIVERSITY OF MICHIGAN
WHAT: University of Michigan, Advanced Computer
Architecture Lab
WHEN: 10:00 am, Tuesday, June 18
WHERE: 1311 EECS Building (Electrical Engineering and
Computer Science), 1301 Beal Avenue, University of
Michigan North Campus, Ann Arbor
REGISTRATION: E-mail
bedemotour@be.com.
Tell us your name, the names of the people coming with
you, and the meeting name (UM/ACAL Meeting). If you don't
register, admission will be on a first-come, first-served
basis.
PS: A second meeting will probably be held at the
University of Michigan on the evening of Monday, June 17.
The schedule is not totally fixed yet, so keep
posted!
- MICHIGAN STATE UNIVERSITY
WHAT: Michigan State University
WHEN: 3:00 pm, Tuesday, June 18
WHERE: Room 402, Computer Center, Michigan State
University, East Lansing
REGISTRATION: E-mail
bedemotour@be.com.
Tell us your name, the names of the people coming with
you, and the meeting name (MSU Meeting). If you don't
register, admission will be on a first-come, first-served
basis.
BE ENGINEERING INSIGHTS:
Benaphores
By Benoit Schillings
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.
BE DEVELOPER PROFILE: CodeGen,
Inc.
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(TM), a C memory allocator; SmartCollect(TM), a
garbage-collecting memory allocator; and SmartFirmware(TM),
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.
The Cryptography Dilemma
By Jean-Louis Gassée
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.
|
