What is missing from Windows95 is support for multiple users. There is a fundamental lack of protection from one process to another, and the scheduler does not appear to be optimized to deliver reasonable performance in a multiuser environment. However, since multiuser support does not appear to have been a goal of Microsoft, this is understandable.
This document will examine Windows95 scheduling methods, problems, and solutions, and will draw some comparisons between Windows95 and the Unix scheduler to evaluate their respective strategies.
Furthermore, each process contains one or more threads. Each thread can be thought of as a "subprocess" which executes independently of the other threads in the process. Threads are created with the CreateThread() API function call. The scheduler determines which thread is to be executed next by examining each thread's priority.
| Priority Class | Priority Number | Description |
|---|---|---|
| Real Time | 24 | Higher priority than Windows95 internal processes. Should only be used for a short time in highly controlled circumstances. Suitable for processes that demand immediate response from any type of input. |
| High Priority | 13 | Used for processes that need more immediate responses than normal user applications. The Windows Task Manager is a good example of such an application. |
| Normal Priority | 9 or 7 | The normal application priority level. Priority 9 is used for the application which currently holds the user's focus; priority 7 is used for other user processes. |
| Idle Priority | 4 | Idle priority is used for processes that do not demand immediate response time. Examples are the clock application and screen savers. |
Each process can be assigned a priority number between 0-31, where 31 is the highest priority. However, processes are most commonly started in one of four priority classes: Real Time, High Priority, Normal Priority, and Idle Priority. The priority class of a process can be reset during its run using the SetPriorityClass() function.Each priority class is summarized in Table 1.
When a thread is started, it inherits the processes priority. This priority can be adjusted up to 2 points higher or lower than the process priority with a call to the SetThreadPriority() function. In this way, you can cause individual threads in a process to outpace others.
Unfortunately, the functions SetPriorityClass() and SetThreadPriority() can be used to reset the priority of any process or thread in the system! If this were a multiuser situation, one user's process could set other's processes to lower priority giving them a scheduling advantage. Additionally, and process can set its priority so high (to "Real Time" or above) that it can negatively impact the performance and integrity of the operating system.
The "Real Time" priority is something of a misnomer: Windows95 is not a real-time operating system. However, the real time priority will provide very good response time if it is needed. The programmer should beware: since real-time priority processes outrank the internal processes of the operating system, it is possible to cause data loss by running your threads at priority 24 or higher.
High priority processes are the next step down. They will preempt normal priority processes, but will leave the operating system processes alone. Since threads running at high priority usually won't allow normal threads to execute, they should be used only in situations where it is preferable to bring other tasks to a halt. Some sample applications of this would be the Windows Task Manager, or perhaps a source level debugger.
Most user processes will be running at normal priority. When a window is in focus, the threads running within it will have a base priority of 9, while the other threads will be running at priority 7. This gives the currently used application better response time. Applications running above this priority may cause "nicer" applications to lag.
Finally, we there is the idle priority. This is not related to the Unix idler in any respect; it is simply a catchy name for "low priority". When response time is not important, as is the case with the clock application, this is the priority that should be used. It is perfectly acceptable for the clock to remain un-updated for several seconds or more while a high powered program crunches numbers.
Priority levels in Windows95 differ from those on a Unix system in that they remain static unless changed by the user. By comparison, a standard Unix kernel will periodically change the priorities of various processes over time to keep them scheduled evenly. To give more or less CPU time to a process, Unix utilizes a "nice" value which is accounted for in the priority calculations. Positive nice values give processes less CPU time; negative values give them more CPU (this is commonly referred to as "negative nice".)
The aging of processes in the Unix scheduler guarantees that a process will run eventually, no matter how nice it is. (If a process is very nice, it will take a very small chunk of the total CPU time, however.) In comparison, Windows95 allows processes to assign themselves such a high priority that low priority threads will never get a chance to run. This is not such a large problem, however, since the user is not fighting for CPU time with any other individuals, and chances are that no two programs that need a lot of CPU time will be run simultaneously.
To run, a thread in the ready state needs to be selected by the scheduler to be moved to the active state. Once the thread has completed as much processing as it can, it will be moved back to one of the other three states.
Each thread is allowed a certain amount of time in the active state before the operating system interrupts it and gives another thread a chance to run. In Windows95, this time slice is approximately 20ms as compared to the typical 100ms of a non-threaded Unix system. A longer time slice is often preferable because of the overhead involved in a process switch operation. However, in the case of Windows95, it may often be the case that a thread switch happens within the same process, thus reducing the time-overhead involved. For this reason, a 20ms time slice may offer faster performance to the user than a longer slice.
There are other ways a thread my be moved from the active state. If the thread runs out of messages in its message queue or it voluntarily suspends itself, it will be moved into the suspend state until it receives a message or another thread resumes it. Alternatively, if the thread requests an unavailable resource, it is placed in the blocked state until the resource becomes available, at which time it is moved back to the ready state. Finally, the process could be preempted by a higher priority process.
This last method of being removed from the active state is the most interesting. If a normal priority thread had used only 10ms of its time slice, a high priority thread can have it moved to the ready state. The high priority thread then moves into the active state for its time slice. A standard Unix system does not allow this sort of preemption; it will give a process the entire 100ms time slice, no matter how nice the process is.
It is important to remember that the scheduler searches for threads in the ready state only! Many threads in the system will be suspended or blocked and will not run until they've moved back into the ready state. The only threads that compete for CPU time are those that aren't in the blocked or suspended states. Again, since this is a single user system, it is likely that most of the threads will be suspended or blocked. For this reason, competition for the CPU isn't too heavy.
An example of how the scheduler operates is presented in the following diagram (each letter represents a thread, followed immediately by its priority):
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| none | A9 B7 C7 D4 | E7 | F10 |
In the above diagram, there is no process in the active state, and the scheduler is in the middle of selecting a new one. As you can see, the thread with the highest priority is "F" with a priority of 10. However, since it is not in the ready state, it will not be scheduled next. The thread in the ready state with the highest priority is "A" with priority 9. It will be moved into the active state next. If there had been another thread in the ready state with priority 9, the scheduler would have selected the least recently run thread to move to the active state.
In the following example, thread "A" is out of focus at normal priority, and thread "B" is at idle priority. Thread A needs the CPU for an additional, say, 10 time slices.
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| A7 | none | B4 | none |
However, thread B has just encountered an external event and it needs to be handled. Its priority is boosted from idle (4) to normal (7) and it is moved to the ready state. Since the boosted priority is not higher than A's priority, A is not preempted. Once A's time slice expires, it is moved into the ready state for rescheduling.
At this point in time, the threads look like this (the asterisk signifies boosted priority):
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| none | A7 B7* | none | none |
Since there is a tie in priority for the next thread to run, the scheduler chooses the least recently executed thread, B, and moves it to the active state. This temporary priority boost allows lower priority threads to get a chance to run. After B's run is complete, its priority will slowly degrade back to 4 after a certain amount of time has elapsed.
Despite this, it is still possible for a high priority thread to continually outrank a idle priority thread, giving it no runtime whatsoever. A particularly nasty program could call SetPriorityClass() on itself and move from normal priority to high priority, thus preempting all other normal applications. However, in the single user environment of Windows95, this would be pointless. In what situation would a user wish an application to not allow any other applications to run? Such a program would be quite unpopular, indeed.
Examine the following situation:
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| A4 | none | B7 C14 | none |
In the course of process A's execution, it finds that it needs exclusive access to a resource (an exclusive access device or a critical section) and allocates it. Suddenly, thread B comes to life. Since it has a higher priority than A, A is preempted and moved to the ready state (the parenthesis signify that A has exclusive access to the resource):
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| B7 | (A4) | C14 | none |
To make matters worse, C suddenly is activated and thread B is preempted to the ready state. Over the course of C's execution, it finds that it wants to use the same resource that is held by A. Since the resource is unavailable, thread C becomes blocked:
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| none | (A4) B7 | none | C14 |
It is now time to schedule a new thread. Since thread B has the highest priority, it will run next. However, if B wishes to run for a long period of time, A will not run because it has lower priority than B. Since A won't run, the resource will not be freed and C will not continue to run. Because C is the highest priority thread in the system, this should not be the case.
The solution to this problem, called the priority inversion problem, is to boost the priority of the thread that holds a resource to the highest priority of all the threads waiting on that resource. In the above example, C would still be moved to the blocked state, but A's priority would be boosted to that of C until the resource is freed:
| Active | Ready | Suspended | Blocked |
|---|---|---|---|
| none | (A14*) B7 | none | C14 |
Now thread A will run before thread B, hopefully freeing the resource in a timely manner so that C can take it. With this technique, it is easy to see that the only thing that could keep thread C from getting the resource next would be a thread a higher priority than itself. Once A releases the critical section or resource, its priority immediately drops to its previous value, as opposed to the gradual decline it experiences with a dynamic priority boost.
Also, the introduction of preemptive multitasking is a major step above Windows 3.11. A faulty native Windows95 application will be a lot less likely to bring the entire system down and processes will run in a much more timely manner.
Including multi-threading and multi-processing capability to the Windows is a major step ahead for Microsoft (quite possibly the largest step since subdirectories were added to MS-DOS.) How long will we need to wait before they take the next one?
Kipping, David, Migrating to Windows95,