How does Windows know if a program is not responding? Does it constantly keep polling all running applications?
An application gets the events from a queue provided by Windows.
If the application doesn't poll the eventqueue for a while (5 seconds), for example when doing a long calculation, then Windows assumes that the application is hung and alerts the user.
To avoid that applications should push expensive calculations to worker threads or split up processing and make sure the queue gets polled regularly.
How does Windows know if a program is not responding?
Without the source code to Windows we cannot be sure what it is doing internally.
There is an SDK Windows function
IsHungAppWindow that can be used.
An application is considered to be not responding if it is not waiting for input, is not in startup processing, and has not called PeekMessage within the internal timeout period of 5 seconds.
Source IsHungAppWindow function
If a top-level window stops responding to messages for more than several seconds, the system considers the window to be not responding. In this case, the system hides the window and replaces it with a ghost window that has the same Z order, location, size, and visual attributes. This allows the user to move it, resize it, or even close the application. However, these are the only actions available because the application is actually not responding.
Does it constantly keep polling all running applications?
No. Applications are not polled but given processor time.
Windows has a scheduling system that gives processor time to application threads.
The scheduling algorithm is complex, and is fully described in Windows Internals, Part 1 (6th Edition) (Developer Reference).
Actually, Windows doesn't always know that an application is not responding. The application has to be an interactive application with a window, and the window must be receiving messages that the application fails to process, before Windows concludes that the application is not responding.
For instance, Windows has no way of knowing if a number-crunching application with no user interface that is run from the command line is doing its thing, or perhaps stuck in an infinite loop.
Interactive graphical applications in Windows receive events by continuously polling a message queue. Windows populates this message queue with keyboard, mouse, timer, etc. events. If an application fails to poll the message queue for some time (5 seconds is the timeout mentioned in the IsHungAppWindow() function documentation), Windows considers the application "hung", which it may indicate by changing the window title (adding the text "(Not Responding)" or equivalent text in localized versions) and greying out the window contents if the user tries to interact with the window.
Applications can hang in ways that Windows does not recognize. For instance, an application may continue polling for messages in its message queue without properly acting on them, so for all practical intents and purposes it would appear "hung" without Windows recognizing that it is non-responsive.
Windows is an operating system, it's supervising all running programs.
Windows communicates with window-based applications using events. Every program has a thread that constantly listens for incoming events and processes them. For example when you click a button or a notification area icon, Windows generates an event and feeds it into appropriate process. The process can then decide how to handle it.
All interactions with programs are event-based in Windows, so when program doesn't process incoming events for too long, it means it doesn't respond. As @DavidPostill has found and noted in his answer, the timeout is 5 seconds.
PeekMessage is the function that gets an event from event queue.
The answer to your question is yes/NO.
While the Windows OS can and does poll applications with events in the Windows Messaging Queue, programs are under absolutely zero obligation to link to the WinAPI or handle/answer the Windows Queue. Even answering a message in the Queue does not tell Windows whether the program has "locked up" or not. It's an indicator, but that's all it is. The real answer is quite a bit more complicated.
The real Answer
People are hedging around the actual answer here. Determining whether a program is "not responding" is a variant of the "halting problem", which is formally undecidable in computer science. The short explanation is that the processor cannot act as a third party observing itself to determine whether a subroutine is stuck in an infinite loop, doing nothing vs incrementing a counter which will terminate at some fixed, normal number. Both of these can be considered to be tightly closed loops. One halts, the other will never terminate. Even you, as a person, don't know whether a program is actually responding or not, especially if it is in a tightly closed loop -- you only know if think it should (respond).
From Windows' perspective, both of these loops are "not responding". That's why windows gives you the choice to wait or terminate, because it cannot tell.
So the corollary is "why does windows know that a process is responding?" The answer is rather clever. When a process is compiled in a multi-threaded & multi-process OS, sometimes even in tightly closed loops, the compiler may add in a yield() command, which provides a convenient notification to the processor that it can switch to other running processes. It "gives up" the processor and a "context switch" (as it is called) happens that allows the OS (Windows included) to answer other events in the stack, some of which include tracking that the process has responded.
**This does not mean that a responding process will terminate. ** A process inside an infinite loop can yield the processor, allowing Windows to process other events.
In some windows programs, the program will handle Windows OS signals, which can tell the OS it is "responding", but no program is under any obligation to do so. You can write quite simple CPU hogging, non-terminating programs even inside higher level languages on Windows such as perl, php, python, and Windows may not detect that it is not terminating and not responding. At that point, Windows depends upon heuristics -- CPU load, memory, how many interrupts the processor handled while the program was running to "guess". Again, at that point, Windows has to ask you to terminate, because it really does not know if it should.
See also Viktor's (correct) answer. Ignore the comments about whether "not responding" is not the same as an infinite loop. There are all kinds of messages, interrupts, loops that an application may or may not handle without informing the Windows message queue. Handling the message queue is only one of many kinds of events that the OS keeps counters on to try to guess whether a process is hung.