How does Windows know if a program is not responding?
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.
Source About Messages and Message Queues
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.