💾 Archived View for thrig.me › blog › 2023 › 12 › 16 › halting-problem.gmi captured on 2024-05-26 at 15:13:34. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Halting Problem

Does the following code halt?

    #include <stdlib.h>

    #include <foo.h>

    int main(void) {
        foo();
        exit(0);
    }

One answer is "maybe" as we do not know what exactly the "foo" call does; it could wedge in various ways, an infinite loop or lock on some resource. Naturally one could look at the code for "foo" and see what it does, or at worst risk a DMCA violation by disassembling the binary blob that "foo" calls into. Be sure to look also for atexit(3) or similar "this code runs at cleanup" object destructors. Any of that code could hang or wedge. This obviously gets more complicated as the code gets more complicated. Maybe you have two libraries that are fighting over some lock you didn't know about, etc.

Another problem is whether a particular instance of the code ever exits. Even less complicated: does an instance of the following code exit?

    /* sleep.c */
    #include <stdlib.h>
    #include <unistd.h>

    int main(void) {
        sleep(5);
        exit(0);
    }

One answer is "maybe" as an instance may hang or wedge for various reasons. Perhaps someone hit control+z by accident, and now the process is stuck. There are various signals that can hang a process (control+z generates one of SIGSTOP, SIGTSTP, SIGTTIN), to say less of a more complicated process hanging due to who knows what reason. Yet another reason is if NFS is involved, which is perhaps less common these days of relatively abundant disk space and software like rsync being available. Or anything else I've forgotten to cover here.

    #!/usr/bin/perl
    use 5.36.0;
    $SIG{STOP} = sub { warn "stop\n" };
    $SIG{TSTP} = sub { warn "tstp\n" };
    $SIG{TTIN} = sub { warn "ttin\n" };
    while (1) {
        say "$ is loopin'";
        sleep 5;
    }

A natural SIGTTIN is unlikely for the above code, though hitting it with control+z or with SIGSTOP and SIGTSTP from elsewhere could be educational. Or you could read signal(3) about the defaults and what can and cannot be caught, but writing and running code is perhaps more educational.

So Does A Process Exit?

Mostly processes will exit most of the time. But there are no guarantees that this will be so, especially if it's the kernel keeping a process alive (the NFS hard mount problem. NFS soft mounts may lack that problem, at the cost of a risk of data corruption) or when there are woeful levels of complexity and you need to write a timeout script because the Java VM sometimes wedges and refuses to exit in a reasonable amount of time (true story, me back in 2002 trying to generate presentations built with XSL-FO).

There is both a Platonic Model Of A Process as to how it behaves, necessary but not sufficient as one must also consider the larger system that process is operating in as to whether that process halts. This is sort of like one of those "Gödel, Escher, Bach" puzzles where one has to step outside the conditions of the puzzle to get a better idea of what could happen.

Meanwhile,

    $ jobs
    [1] + Suspended            ./sleep

eventually this process will go away: the hardware may fail or more likely the system is rebooted due to a software update or power failure. Actually it probably died during one of my routine "excess tmux window" purges, or possibly to the following alias.

    $ grep newshell ~/.kshrc
    alias newshell='exec /bin/ksh -l;: '

P.S. Latency calculations may need to be aware of the control+z problem. How fast were the connections being made if someone hit control+z on the load generating script halfway through the load test, and "fg" just before the end of the test? This sort of temporary interruption might be called the semi-halting problem. The control+z problem generalizes to various other conditions that cause "bytes to get gummed up in the tubes", so it's not just accidental (or malicious) use of control+z as a trigger.

P.P.S. "sleep 3" or whatever is maybe not the most efficient way to make a process do nothing for a while, though it is easy to type out and remember. Another method is to use I/O blocking to halt the process. This however is longer to type out and may not be good if the system or user account is short on file descriptors.

    char buf[1];
    int fds[2];
    if (pipe(fds) != 0) abort();
    while (1) read(fds[0], buf, 1);

P.P.P.S. Someone was asking on chat whether some bit of code would exit or not, hence this post showing all the "maybe" involved.

P.P.P.P.S. I don't think I've done this many post scripts in a post before.