7.4.3 Runlevels, part two

Let’s look again at the table at the end of part two:

If from this table it is so obvious for us what we should do, then it should also be possible to calculate it for a computer, given such a table as input. Ok, we have to take into account conflicts that are not visible in this table, but the general idea is usable. But how do we find which combination works? I found only one way yet: Kind of a brute force attack: Try combinations until we find one that works.

This alone would be too slow. With 20 services we would have 2^20 possible combinations, that is a bit more than a million. Fortunatly, we can optimize this. First I thought we could remove all services from the list that do not provide any symbol we need, but that is obviously a stupid idea, as we might need them for dependencies, in which case we need to take into account their conflicts. But the following method would work:

Very often a symbol that is required will be a canonical name already, i.e. be provided only by a single service. Using our example above, let’s suppose we also need the symbol V, which is provided only by D. The first step we do is to look which (required) symbols are provided only by a single service, as we will need this service for sure. In this case, we would need D. But by using it, we would also get the other symbols it provides, W in this case. This means that we don’t need to bother looking at other services that provide W, as we cannot use them because they conflict with a service that we definitely need. In this case, we can remove A and B from the list this way. Note that we can remove them entirely, as all their conflicts become irrelevant to us now. In this simple case we would not even have to do much else, C is the only remaining service.

After this first step, there remain the symbols that are provided by two or more services. In every combination we try, exactly one of them must be used (and somehow we should take into account which services are running already). This also reduces the amount of possible combinations a lot. So what remains after that are the services we might need for fulfilling dependencies. For them, we could try all combinations (2^n), making sure that we always try subsets before any of their supersets to avoid starting unneeded services. We should take into account which services are already running as well.

The remaining question is, what to do if starting a service fails. A simple solution would be to recursively remove all services that depend on it directly or indirectly. That might cause undesired side-effects, if a service was running but it had to be stopped because one of the services that provides something it depends on gets exchanged for another service that provides the same symbol, but fails to start. The fact that we would have to stop the (first) service is a problem on its own, though.