Processes and threads
A thread is a flow of execution, and a process is a collection of threads. In the BlackBerry 10 OS, the schedulable entity is a thread, not a process.
Process and thread fundamentals
Before we start talking about processes, threads, time slices, and all the other wonderful scheduling concepts, let's establish an analogy. What you want to do first is illustrate how processes and threads work. The best way (short of digging into the design of a realtime system) is to imagine our processes and threads in some kind of situation.
A process as a house
Let's base our analogy for processes and threads using a regular, everyday object — a house. A house is really a container, with certain attributes (such as the amount of floor space, the number of bedrooms, and so on).
If you look at it that way, the house really doesn't actively do anything on its own — it's a passive object. This is effectively what a process is. We'll explore this shortly.
The occupants as threads
The people living in the house are the active objects—they're the ones using the various rooms, watching TV, cooking, taking showers, and so on.
- Single threaded
- If you've ever lived on your own, then you know what this is like—you know that you can do anything you want in the house at any time, because there's nobody else in the house. If you want to turn on the stereo, use the washroom, have dinner—whatever—you just go ahead and do it.
- Multi threaded
- Things change dramatically when you add another person into the
house. Let's say you get married, so now you have a spouse living there too. You
can't just march into the washroom at any given point; you need to check first to
make sure your spouse isn't in there!
If you have two responsible adults living in a house, generally you can be reasonably lax about security — you know that the other adult will respect your space, won't try to set the kitchen on fire, and so on.
Now, throw a few kids into the mix and suddenly things get a lot more interesting.
Back to processes and threads
Just as a house occupies an area of real estate, a process occupies memory. And just as a house's occupants are free to go into any room they want, a processes' threads all have common access to that memory. If a thread allocates something (mom goes out and buys a game), all the other threads immediately have access to it (because it's present in the common address space—it's in the house). Likewise, if the process allocates memory, this new memory is available to all the threads as well. The trick here is to recognize whether the memory should be available to all the threads in the process. If it is, then you need to have all the threads synchronize their access to it. If it isn't, then we assume that it's specific to a particular thread. In that case, since only that thread has access to it, we can assume that no synchronization is required—the thread isn't going to trip itself up!
As we know from everyday life, things aren't quite that simple. Now that we've seen the basic characteristics (summary: everything is shared), let's take a look at where things get a little more interesting, and why.
The following diagram shows the way that we represent threads and processes. The process is the circle, representing the container concept (the address space), and the three squiggly lines are the threads.
If you want to take a shower, and there's someone already using the bathroom, you have to wait. How does a thread handle this? It's done with something called mutual exclusion. It means pretty much what you think — a number of threads are mutually exclusive when it comes to a particular resource.
If you're taking a shower, you want to have exclusive access to the bathroom. To do this, you typically go into the bathroom and lock the door from the inside. Anyone else trying to use the bathroom gets stopped by the lock. When you're done, you unlock the door, allowing someone else access.
This is just what a thread does. A thread uses an object called a mutex (an acronym for MUTual EXclusion). This object is like the lock on a door — once a thread has the mutex locked, no other thread can get the mutex, until the owning thread releases (unlocks) it. Just like the door lock, threads waiting to obtain the mutex are barred.
Another interesting parallel that occurs with mutexes and door locks is that the mutex is really an advisory lock. If a thread doesn't obey the convention of using the mutex, then the protection is useless. In our house analogy, this would be like someone breaking into the washroom through one of the walls ignoring the convention of the door and lock.
What if the bathroom is currently locked and a number of people are waiting to use it? Obviously, all the people are sitting around outside, waiting for whoever is in the bathroom to get out. The real question is, What happens when the door unlocks? Who gets to go next? It would be fair to allow whoever is waiting the longest to go next. Or it might be fair to let whoever is the oldest go next. Or tallest. Or most important. There are any number of ways to determine what's fair.
We solve this with threads via two factors: priority and length of wait.
Suppose two people show up at the (locked) bathroom door at the same time. One of them has a pressing deadline (they're already late for a meeting) whereas the other doesn't. Wouldn't it make sense to allow the person with the pressing deadline to go next? Well, of course it would. The only question is how you decide who's more important. This can be done by assigning a priority (let's just use a number like BlackBerry 10 OS does—one is the lowest usable priority, and 255 is the highest as of this version). The people in the house that have pressing deadlines would be given a higher priority, and those that don't would be given a lower priority.
Same thing with threads. A thread inherits its scheduling policy from its parent thread, but can (if it has the authority to do so) call pthread_setschedparam() to change its scheduling policy and priority, or pthread_setschedprio() to change just its priority.
If a number of threads are waiting, and the mutex becomes unlocked, we would give the mutex to the waiting thread with the highest priority. Suppose, however, that both people have the same priority. Now what do you do? Well, in that case, it would be fair to allow the person who's been waiting the longest to go next. This is not only fair, but it's also what the QNX Neutrino microkernel does. In the case of a bunch of threads waiting, we go primarily by priority, and secondarily by length of wait.
The mutex is certainly not the only synchronization object that we'll encounter. Let's look at some others.
Let's move from the bathroom into the kitchen, since that's a socially acceptable location to have more than one person at the same time. In the kitchen, you may not want to have everyone in there at once. In fact, you probably want to limit the number of people you can have in the kitchen (too many cooks, and all that). Let's say you don't ever want to have more than two people in there simultaneously. Can you do it with a mutex? Not as we've defined it. Why not? This is actually a very interesting problem for our analogy. Let's break it down into a few steps.
A semaphore with a count of 1
The bathroom can have one of two situations, with two states that go hand-in-hand with each other:
- The door is unlocked and nobody is in the room
- The door is locked and one person is in the room
No other combination is possible — the door can't be locked with nobody in the room (how would we unlock it?), and the door can't be unlocked with someone in the room (how would they ensure their privacy?). This is an example of a semaphore with a count of one — there can be at most only one person in that room, or one thread using the semaphore.
The key here (pardon the pun) is the way we characterize the lock. In your typical bathroom lock, you can lock and unlock it only from the inside — there's no outside-accessible key. Effectively, this means that ownership of the mutex is an atomic operation — there's no chance that while you're in the process of getting the mutex some other thread gets it, with the result that you both own the mutex. In our house analogy this is less apparent, because humans are just so much smarter than ones and zeros.
What we need for the kitchen is a different type of lock.
A semaphore with a count greater than 1
Suppose we install the traditional key-based lock in the kitchen. The way this lock works is that if you have a key, you can unlock the door and go in. Anyone who uses this lock agrees that when they get inside, they immediately lock the door from the inside so that anyone on the outside always requires a key. Well, now it becomes a simple matter to control how many people we want in the kitchen — hang two keys outside the door! The kitchen is always locked. When someone wants to go into the kitchen, they see if there's a key hanging outside the door. If so, they take it with them, unlock the kitchen door, go inside, and use the key to lock the door.
Since the person going into the kitchen must have the key with them when they're in the kitchen, we're directly controlling the number of people allowed into the kitchen at any given point by limiting the number of keys available on the hook outside the door.
With threads, this is accomplished via a semaphore. A plain semaphore works just like a mutex — you either own the mutex, in which case you have access to the resource, or you don't, in which case you don't have access. The semaphore we just described with the kitchen is a counting semaphore — it keeps track of the count (by the number of keys available to the threads).
A semaphore as a mutex
We just asked the question, could you do it with a mutex, in relation to implementing a lock with a count, and the answer was no. How about the other way around? Could we use a semaphore as a mutex? Yes. In some operating systems, that's exactly what they do—they don't have mutexes, only semaphores! So why bother with mutexes at all?
To answer that question, look at your washroom. How did the builder of your house implement the mutex? You probably don't have a key hanging on the wall!
Mutexes are a special purpose semaphore. If you want one thread running in a particular section of code, a mutex is by far the most efficient implementation.
Later on, we'll look at other synchronization schemes — things called condvars, barriers, and sleepons.
Just so there's no confusion, realize that a mutex has other properties, such as priority inheritance, that differentiate it from a semaphore.
Last modified: 2014-11-17