How is responsibility divided in thread scheduling?

[smwikipedia]

Hi friends,

I came across a question about Windows messaging and GetMessage() method, and thus leads to the thought of who is the responsible for changing threads' state? Or how is a thread's state changed?

Below is my detailed version:

According to < Windows via C/C++ 5th Edition > Chapter 7 Section: Thread Priorities

...For example, if your process' primary thread calls GetMessage() and the system sees that no messages are pending, the system suspends your porcess' thread, relinquishes the remainder of the thread's time slice, and immediately assigns the CPU to another waiting thread.

If no messages show up for GetMessage to retrieve, the process' primary thread stays suspended and is never assigned to a CPU. However, when a message is placed in the thread's queue, the system knows that the thread should no longer be suspended and assigns the thread to a CPU if no higher-priority threads need to execute.

My current understanding is:

In order for the system to know when a message is placed in a thread's queue, there could be 2 possible approaches:

1 - Centralized approach: It is the system who is responsible to always check EVERY thread's queue. Even that thread is blocked for the lacking of messages. If any message is availabe, the system will change the state of that thread to schedulable. But this checking could be a real burden to the system in my opinion.

2 - Distributed approach: The system doesn't check every thread's queue. When a thread calls GetMessage and find that no message is available, the system will just change the thread's state to blocked, thus not schedulable any more. And in the future no matter who places a message into a blocked thread's queue, it is this "who"(not the system) that is responsible to change the the thread's state from blocked to ready (or whatever state). So this thread is dis-qualified for scheduling by the system and re-qualified by someone else in the regard of GetMessage. What the system cares is just to schedule the runable threads. The system doesn't care where these schedulable threads come from. This approach will avoid the burden in approach 1, and thus avoid the possible bottleneck.

In fact, the key point here is, how are the states of the threads changed? Is it really a distributed paradigm as shown in appraoch 2?

And here is my original post on this topic with more info.
http://stackoverflow.com/questions/4151 ... ssage-loop

Many thanks for your insights.

[pcmattman]

I can't really comment on how Windows works, but I've always looked at this kind of message passing like so:

1. Process A calls GetMessage. There is nothing in the message queue so the process/thread is put to sleep.
2. Process B calls SendMessage to send a message to Process A. Process B might be the window manager, or some other program.
3. The message is added to the message queue for Process A. When this happens a semaphore or some other lock mechanism (perhaps a condition variable) might be signalled to announce the presence of data on the queue.
4. Process A is woken up now that it has content on the message queue. In the scheduler this is essentially as simple as moving a thread from the sleep queue to the run queue.
5. Process A gets the message off the queue and does whatever it needs to with it.

I have greatly simplified this in order to get the basic idea across without specific knowledge about the internals of any specific operating system.

[smwikipedia]

Many thanks, pcmattman.

Here is my comment.

1 - Process A calls GetMessage. There is nothing in the message queue so the process/thread is put to sleep. (Who is responsible to put A to sleep? I think it could be implemented in GetMessage() function.)

2 - Process B calls SendMessage to send a message to Process A. Process B might be the window manager, or some other program.

3 - The message is added to the message queue for Process A. When this happens a semaphore or some other lock mechanism (perhaps a condition variable) might be signalled to announce the presence of data on the queue. (I think this notification mechanism could be implemented in the SendMessage() function. Thus it is B who trigs the whole reaction chain, thus the distributed approach.)

4 - Process A is woken up now that it has content on the message queue. In the scheduler this is essentially as simple as moving a thread from the sleep queue to the run queue. (Who wakes up A? Who moves a thread from sleep queue to the run queue? This is essentially what I am asking.)


5 - Process A gets the message off the queue and does whatever it needs to with it.

[Colonel Kernel]

The answer is sort of both "centralized" and "distributed": The thread's state is changed by code that runs in response to some kind of event (GetMessage/SendMessage), but that code runs in the context of the system. How that works in detail depends on your kernel architecture. Windows generally maintains a kernel-mode thread for each user-mode thread, so for your example, the thread calling GetMessage() will switch to the kernel, and its corresponding kernel-mode thread will invoke the scheduler to suspend itself. The thread calling SendMessage() will switch to the kernel, and its corresponding kernel-mode thread will make the suspended thread runnable again. So you can see it is sort of "distributed" in the sense that the kernel-mode threads running on behalf of GetMessage()/SendMessage() do the actual work, but since they are running kernel code, they are still part of the "centralized" system.

[smwikipedia]

The answer is sort of both "centralized" and "distributed": The thread's state is changed by code that runs in response to some kind of event (GetMessage/SendMessage), but that code runs in the context of the system. How that works in detail depends on your kernel architecture. Windows generally maintains a kernel-mode thread for each user-mode thread, so for your example, the thread calling GetMessage() will switch to the kernel, and its corresponding kernel-mode thread will invoke the scheduler to suspend itself. The thread calling SendMessage() will switch to the kernel, and its corresponding kernel-mode thread will make the suspended thread runnable again. So you can see it is sort of "distributed" in the sense that the kernel-mode threads running on behalf of GetMessage()/SendMessage() do the actual work, but since they are running kernel code, they are still part of the "centralized" system.

Thanks Colonel. I appreaciate your answer very much. It's concise and right-on-target. I'll update this thread when I got more thoughts on this.