Advocacy

  Myths
  Press

Dojo (HowTo)

  General
  Hack
  Hardware
  Interface
  Software

Reference

  Standards
  People
  Forensics

Markets

  Web

Museum

  CodeNames
  Easter Eggs
  History
  Innovation
  Sightings

News

  Opinion

Other

  Martial Arts
  ITIL
  Thought


Reentrant
What is it, why does it matter?

By:David K. Every
©Copyright 1999


A lot of people have wondered why Apple hasn't added things like preemptive multitasking sooner, or why it is difficult to just plop that feature underneath. The answer is that the Mac ToolBox (Mac OS Low-Levels) are not reentrant.

Now of course that begs the question, "What is reentrant code, and why does it matter?"

Reentrancy: the problem

Programs are normally just lots of little routines (pieces of code) that do things (simple algorithms) like test variables and set states based on the results, and so on.

So lets create a little scenario:

Imagine I have an Operating System routine that runs in the background that lets you get the current time. The computer remembers time as some value (like how many seconds have passed since 1904 or some such) but our routine converts this value to a string (text) and returns the time in that format "11:59 a.m.".

So our program is running at it calls our little CheckTime() routine -- and normally it works fine. But this time our routine starts, and it starts building the text for us, it adds the '1' and the '1' and the ':' and right then the Operating System stops (interrupts) this routine (and our program), it is time for another program to get its chance to run.

If you don't understand multitasking read How does Multitasking Work. Multitasking is when the computer just gives chunks of time to many different applications -- it keeps stopping one program, and giving time to another, then stopping that one and returning back to the first one. (Each "turn" is called a time-slice). If it does this very quickly, it feels like both are running smoothly at the same time.

Now the second program runs and just happens to also call the same CheckTime() routine -- it reenters that routine (can you guess where term "reentrant" comes from?). CheckTime() doesn't know it is really half way through processing somewhere else, so it clears out the first text response, and starts over. It completes just fine and it builds the response "11:59 a.m." and goes on. The second program is happy, and it seems like things worked -- but soon this program gets interrupted, and the computer goes back to the first program.

The first program (and our CheckTime() routine) just continues from where it left off... let's see, it had finished '11:', and so it just adds the '5' + '9' + ' a.m." to the end of the string (text). But the string was already ''11:59 a.m." because it had been completed elsewhere. So what does the result look like? "11:59 a.m.59 a.m.". Hmmm... not exactly what we wanted.

Now the problems can be a lot bigger than just a few added characters tacked on to the end of something -- it can easily pollute data, give you invalid results and make the program crash. The whole problem was because the routine CheckTime() was not reentrant -- it could not be "re-entered" from more than one place at a time.

Recursive is somewhat related to Reentrant. Recursive routines are routines that call themselves (part way through) -- so they are not only being "re-entered", they are being reentered by themselves. So recursion and reentrancy are often taught in programming around the same time, and people sometimes confuse them. There are many reasons for recursion -- but that would get us flying off topic and is really best left to another article. For now, just know that it exists and is sometimes neat.

More problems

Multitasking problems are actually more than just having routines that are reentrant -- but this is the most common, and they are all pretty interrelated.

There are a lot of little uglies you can get into. Imagine our CheckTime() routine builds the "11:" and gets interrupted... the second program gets it's time slice. This time there is no reentrancy issue, but just a time issue -- by the time the OS gets back to us the time is "12:00 p.m.". CheckTime() continues and adds the "00 p.m." to the end of "11:" -- and now we have the very confusing (and spectacularly wrong) time of "11:00 p.m.".

So there is much more to the set of problems created by OS controlled multitasking than just reentrancy issues -- but they all get lumped in with the most common problem (and under that name).

Solutions #1 -- Blocking (semaphores)

The most common solution to these problems seems to be blocking -- which is just that, blocking others out. If the first thing I do when I start CheckTime() is to put up a "block", so that no other program can interrupt me until I'm done, and I release that block as the last thing I do in CheckTime(), then the problem is solved. No one can stop me from completing my task and messing up my data.

This is all a game of "red-light / green-light". The computer can't pause me until I give it the green light. So the OS does a lot of little stop-starts. Of course since it can't stop me when it wants (only when I say it can) it isn't as "smooth" (fast/responsive) as it could be -- since the OS is waiting for my routines.

These blocking flags are called semaphores after the real semaphores:

Semaphore: n. A visual signaling apparatus with flags, lights, or mechanically moving arms, as one used on a railroad.

So just like the railroad arms stop traffic from going, our software semaphores block other routines or programs from going.

For what it is worth, Windows95 and Windows98 use a lot of huge semaphores. Whole areas of the OS (most of it) are blocked off, and the other programs can't continue (or use the OS) until that one Application is done. This is multitasking, but they all have one huge shared resource (the OS), and they can't share -- they can only take turns.

Solutions #2 -- relative data

The better solution is to write (or rewrite) all of your routines so they get all their data from a pointer (variable) that is passed to them by the calling routine. If my routine accesses a pointer to get the data, and that pointer is different for each time the routine is called, then the data from one instance/call can't overwrite the other, and things are pretty much fixed (reentrant).

This is how it is usually designed -- if you are designing things to be reentrant in the first place. But it is far easier to do when creating something -- and damn near impossible to fix later. If you try to go back and fix routines to be reentrant, then you learn that one routine's state was dependent on another routine's state -- and you have to fix the other routine too, which is dependent on another, and so on. Usually you just have to rewrite everything from scratch -- but this is harder to do that doing it the first time, because many of the parameters you are passing around have to stay the same (because programers are using those routines and expect a certain parameter count and order) -- and things can't just stay the same, since you need more parameters (to keep all the relative data pointers). This gets very ugly -- and has been the birds nest of code that has kept Apple from just "fixing" the Mac OS a long time ago.

Conclusion

In reality, there are more ways than just the 2 solutions I mentioned -- and most often there is a combination of both. There are some areas where you just need to "block" -- but you want to do it infrequently and as small as possible. Everything that is blocked is a shared resource, that people/programs have take turns with -- it is much better if they can all work with it at once.

Multiprocessing requires reentrancy as well, because multiple processors could be calling the same routine at the same time as well.

Reentrancy is a pretty simple concept (in theory), but many programmers don't fully understand. I once got a programming job because I could explain to the interviewer what reentrancy was (and how to make code reentrant), after many interview'ies before me could not. So if you were able to understand and follow this article, you now know far more than many people (and even many programers) on this subject.


Answers to other questions

Now that you understand reentrancy, you understand a lot more than you might think. Like "what is Carbon"?

Carbon is just a subset / superset of the MacAPI's (Programmer Interfaces) that are reentrant. By programmers only using these subroutines they are fully multitasking (and likely multiprocessing).

Apple has been spending the time to do reentrancy in the toolbox (OS) correctly -- but that takes time (lots of time) to do it right. The problem is that you can't be 99% reentrant -- it is like pregnancy, either you are or aren't. Apple has had many parts of the OS (like almost everything they've added since the early 90's) that are reentrant (to the best of my knowledge, QuickTime, QuickDrawGX, QuickDraw3D, OpenTransport and many other things are reentrant) -- but that still left a whole lot of things to change. Carbon is a way to add the final parts, and eliminate the rest that aren't.

OS X will still have a "transparent" BlueBox (Mac emulator for older Applications) that will run older Mac Applications just like normal -- but there will be big semaphores / shared resources and blocking of the toolbox (OS) itself. So old Apps can run a little better on OS X than on say Mac OS 8, but they are likely to keep "blocking" each other (but not Carbon-based Apps or OS X itself).

The problem with the Mac was never to add Preemptive multitasking so that it would work (barely) like Win95. The problem was to take the time to do it right, and make the entire toolbox reentrant and make it so that it would add value to users (and not just be a check box on some marketing literature).


Created: 02/16/99
Updated: 11/09/02


Top of page

Top of Section

Home