Argthtjtr

If a program is not allowed to handle or ignore SIGKILL and SIGSTOP, and must immediately terminate, why does the kernel even send the signal to the program? Can't the kernel simply evict the program from the CPU and memory? I assume the kernel would have the ability do directly do this.

This answer is partly correct, there is more to do to terminate a process than to free the memory. However a SIGKILL is not a tap on the shoulder and a request to do something, it is one of the few signals that a process can't ignore or handle. That means that a SIGKILL is always handled by the kernel's default handler, and this default action, as with most of the signals, is to terminate the process receiving the signal. The user space part of the program won't even see the signal, so there is no request to do something, no cooperation required, and therefor a program can't misbehave upon receiving SIGKILL, whether by malicious intent or by some programming error. Instead the kernel side of the process will handle the signal and terminate the process. So in a way the kernel is directly terminating the process, by telling another part of the kernel that the process shall be terminated.

From a programming point of view, when the kernel wants to kill a program (which mostly happens because of missing resources, especially not enough free RAM), there are two possibilities, to duplicate the code that does this when a process has to be terminated, or just call a single function to deliver the signal and know that everything necessary to terminate the process will be handled. The second approach is not only less initial work, it means much less work in the long run because the duplicate code doesn't have to be maintained.

The user-space part of a process terminated by SIGKILL never gets to know about it; the kernel deals with everything. (This does mean that some resources can leak: temporary files, shared memory allocations, resources held on behalf of the killed process by another process such as an X server…)

However the signal still needs to be delivered, so that other processes can find out how the killed process was terminated. A parent, using wait, will get the information that the killed process was terminated by SIGKILL.

An overview of how signals work, in order to complete the other answers which are very good:

The execution of a process can happen in two modes: in userspace or in kernelspace. When in userspace, the process executes the code of its program whereas in kernelspace, it executes the code of the kernel. Processes run in userspace as much as possible to do their work but enter kernelspace from time to time during their execution when they make a system call (which is necessary for any privileged operation on the hardware or shared resources of the system itself, like reading a file) or when they are interrupted in their execution.

They are two cases in which a signal is handled: when a process returns into userspace after having finished a system call, or when it wakes up from an interruptible sleep and resumes its execution. In both cases, the process is in kernelspace. Before anything else, the kernel checks if some signal is pending for the process and acts upon it. If a handler is defined for the signal for example, it makes the process execute it upon its return into userspace. As you've said yourself, the case of KILL is special because it cannot be captured. So, it's actually a simple case for the kernel: the return to userspace is cancelled and the process is killed right away, which means that it won't execute any code in userspace anymore, its memory is freed, its parent process is notified of its death, etc.

Processes on exit perform several cleanup actions like freeing memory, releasing semaphores, closing files, mayhap some statistics, within their process context / environment. Although the kernel could replicate that, it's easier to tap the process on its shoulder and ask it to commit suicide.