Lesson 4 - Multitasking and Multiprocessing

On This Page

What You Will Learn
Thinking Ahead
What To Do
Before Going On
Speaking The Language
To Learn More

What You Will Learn

By the end of this lesson, you should be able to do the following:

• Explain how Windows NT implements preemptive multitasking on single and multiple processor systems and how preemptive multitasking improves system operation.

• Tell the difference between a process and a thread and describe the basic attributes of each. Explain the advantages and problems of multi-threaded operation.

• Explain what scheduling is and describe how threads are scheduled and prioritized under Windows NT.

• Explain why synchronization is necessary and show how to protect a critical section.

• Using material learned in this module, you'll be able to explain the following:

• Why the RPC server dies in Windows NT when PowerPoint is doing a full-screen display--and how to correct the problem.

• Why programs running under Windows NT can always be switched away from or killed--even in situation that would crash 16-bit Windows 3.1.

Thinking Ahead

What To Do

Review: What Is Multitasking?

Multitasking is the ability of a computer to run more than one program, or task , at the same time. Multitasking contrasts with single-tasking, where one process must entirely finish before another can begin. MS-DOS is primarily a single-tasking environment, while Windows 3.1 and Windows NT are both multi-tasking environments.

On a single-processor multitasking system, multiple processes don't actually run at the same time since there's only one processor. Instead, the processor switches among the processes that are active at any given time. Because computers are so fast compared with people, however, it appears to the user as though the computer is executing all of the tasks at once. Multitasking also allows the computer to make good use of the time it would otherwise spend waiting for I/O devices and user input--that time can be used for some other task that doesn't need I/O at the moment.

Multitasking on a multiple-processor system still involves the processors switching between tasks because there are almost always more tasks to run than there are processors. Note, however, that there can be as many tasks running simultaneously as there are processors in the system. For the moment, we'll discuss multitasking on a single-processor system.

Review: Preemptive and Non-Preemptive Multitasking

Within the category of multitasking, there are two major sub-categories: preemptive and non-preemptive (or cooperative). In non-preemptive multitasking , use of the processor is never taken from a task; rather, a task must voluntarily yield control of the processor before any other task can run. Windows 3.1 uses non-preemptive multitasking for Windows applications.

Programs running under a non-preemptive operating system must be specially written to cooperate in multitasking by yielding control of the processor at frequent intervals. Programs that do not yield sufficiently often cause non-preemptive systems to stay "locked" in that program until it does yield. An example of failed non-preemptive multitasking is the inability to do anything else while printing a document in Microsoft Word for Windows 2.0a. This happens because Word does not give up control of the processor often enough while printing your document. The worst case of a program not yielding is when a program crashes. Sometimes, programs which crash in Windows 3.1 will crash the whole system simply because no other tasks can run until the crashed program yields.

Preemptive multitasking differs from non-preemptive multitasking in that the operating system can take control of the processor without the task's cooperation. (A task can also give it up voluntarily, as in non-preemptive multitasking.) The process of a task having control taken from it is called preemption. Windows NT uses preemptive multitasking for all processes except 16-bit Windows 3.1 programs. As a result, a Window NT application cannot take over the processor in the same way that a Windows 3.1 application can.

A preemptive operating system takes control of the processor from a task in two ways:

• When a task's time quantum (or time slice) runs out. Any given task is only given control for a set amount of time before the operating system interrupts it and schedules another task to run.

• When a task that has higher priority becomes ready to run. The currently running task loses control of the processor when a task with higher priority is ready to run regardless of whether it has time left in its quantum or not.

Switching Among Tasks

At any given time, a processor (CPU) is executing in a specific context. This context is made up of the contents of its registers and the memory (including stack, data, and code) that it is addressing. When the processor needs to switch to a different task, it must save its current context (so it can later restore the context and continue execution where it left off) and switch to the context of the new task. This process is called context switching .

When Windows NT switches tasks, it saves all of the registers of the task it's leaving and re-loads the registers of the task to which it's switching. This process also enables the proper address space for the task to which Windows NT is switching.

Processes and Threads

In addition to being a preemptive multitasking operating system, Windows NT is also multithreaded, meaning that more than one thread of execution (or thread ) can execute in a single task at once.

A process comprises:

• A private memory address space in which the process's code and data are stored.

• An access token against which Windows NT makes security checks.

• System resources such as files and windows (represented as object handles).

• At least one thread to execute the code.

A thread comprises:

• A processor state including the current instruction pointer.

• A stack for use when running in user mode.

• A stack for use when running in kernel mode.

Since processes (not threads) own the access token, system resource handles, and address space, threads do NOT have their own address spaces nor do they have their own access token or system resource handles. Therefore, all of the threads in a process SHARE the same memory, access token, and system resources (including quota limits) on a "per-process" rather than a "per-thread" basis. In a multithreaded program, the programmer is responsible for making sure that the different threads don't interfere with each other by using these shared resources in a way that conflicts with another thread's use of the same resource. (As you might suspect, this can get a little tricky.)

Why Use Multithreading?

Multithreading provides a way to have more than one thread executing in the same process while allowing every thread access to the same memory address space. This allows very fast communication among threads. Threads are also easier to create than processes since they don't require a separate address space.

Inside Windows NT, processes and threads are represented as objects that are created, maintained, and destroyed by the Process Manager. These Process Manager process and thread objects contain simpler kernel process and thread objects.

Some typical examples of the use of multiple threads are using a background thread to print a document in a word processor and to recalculate a spreadsheet. When a new thread is created to do these tasks, the main thread can continue responding to user input. A single-threaded application can't respond to user input until it's done printing or recalculating or whatever.

On a uniprocessor platform, the use of multiple threads allows a user to continue using a program even while another thread is doing some lengthy procedure. But only one thread executes at a time.

On a multiprocessor platform, more than one processor may be running different threads in the same process. This has the potential for very significantly speeding up the execution of your program.

Sharing A Single Address Space--Synchronizing Access To Data

Running each process in its own address space had the advantage of reliability since no process can modify another process's memory. However, all of a process's threads run in the same address space and have unrestricted access to all of the same resources, including memory. While this makes it easy to share data among threads, it also makes it easy for threads to step on each other. As mentioned before, multithreaded programs must be specially programmed to ensure that threads don't step on each other.

A section of code that modifies data structures shared by multiple threads is called a critical section . It is important than when a critical section is running in one thread that no other thread be able to access that data structure. Synchronization is necessary to ensure that only one thread can execute in a critical section at a time. This synchronization is accomplished through the use of some type of Windows NT synchronization object. Programs use Windows NT synchronization objects rather than writing their own synchronization both to save coding effort and for efficiency: when you wait on a Windows NT synchronization object, you do NOT use any CPU time testing the object to see when it's ready.

Windows NT provides a variety of different types of synchronization objects that programs can use to coordinate threads' access to shared data structures. Synchronization objects remember their states and can be set and tested in one uninterruptable step. They also cause the thread to be suspended while waiting on an object and to automatically restart when the other thread signals that it's done.

During the initialization of a program, the program creates a synchronization object for each data structure or object that will be shared among threads.

EVERY critical section will have the following structure:

1. Wait on the synchronization object before accessing the data structure. The Windows NT waiting API insures that your thread is suspended until the synchronization object becomes unlocked. As soon as the synchronization object becomes unlocked, Windows NT sets the synchronization object to "locked" and restarts your thread.

2. Access the data structure. (This is the critical section.)

3. Unlock the synchronization object so that the data can be accessed by other threads.

The first step is critical because if it's omitted then any thread can access the data structure while you're accessing. The last step is also critical--it it's omitted, then no thread will be able to access the data even after you're done.

Using this technique on every critical section insures that only one thread can access the data at a time.

The Life Cycle Of A Thread

Each thread has a dispatcher state that changes throughout its lifetime.

The most important dispatcher states are:

• Running: only one thread per processor can be running at any time.

• Ready: threads that are in the Ready state may be scheduled for execution the next time the kernel dispatches a thread. Which Ready thread executes is determined by their priorities.

• Waiting: threads that are waiting for some event to occur before they become Ready are said to be waiting. Examples of events include waiting for I/O, waiting for a message, and waiting for a synchronization object to become unlocked.

The Kernel's Dispatcher

The kernel's dispatcher performs scheduling and context switching.

Thread scheduling is the act of determining which thread runs on each processor at a given time.

Context switching is the act of saving one thread's volatile state (CPU register contents) and restoring another thread's state so it can continue running where it previously left off.

How Thread Priorities Affect Scheduling

The kernel's dispatcher schedules threads to run based a 32-level priority scheme. Windows NT guarantees that the threads that are ready that have the highest priority will be running at any given time. (That's one thread on a single-processor system.) Threads with a priority of 31 will be run before any others, while threads with a priority of 0 will run only if no other threads are ready. The range of priorities is divided in half with the upper 16 reserved for real-time threads and the lower 16 reserved for variable priority threads.

Real-time threads run at the same priority for their entire lifetime. They are commonly used to monitor or control systems that require action to be taken at very precise intervals. These threads run at higher priorities than all variable priority threads, which means that they must be used sparingly.

Variable priority threads are assigned a base priority when they are created. (A thread's base priority is determined by the process to which the thread belongs.) The priority of such threads can be adjusted dynamically by the kernel's dispatcher. A thread's dynamic priority can vary up to two priority levels above or below its base priority.

The dispatcher maintains a priority queue of ready tasks. When prompted to reschedule, it changes the state of the highest priority task to Standby. When the conditions are right, a context switch is performed to begin the thread's execution and the thread goes into the Ready state.

Lower priority threads will always be preempted when a higher priory thread enters the ready state. This is true even if the lower priority thread has time remaining in its quantum, or if the lower priority thread is running on a different processor.

Performance Tuning

In order to get the computer system to perform as users expect, Windows NT changes the priorities of threads over time.

Each process has a base priority. Threads in a process can alter their base priority by up to two levels up or down.

Depending on the type of work the thread is doing, Windows NT may also adjust the thread's dynamic priority upwards from its base priority. For instance:

• Threads that are waiting for input get a priority boost, as do threads in the foreground process. This makes the system responsive to the user.

• Threads get a priority boost after completing a voluntary wait.

• All threads periodically get a priority boost to prevent lower priority threads from holding locks on shared resources that are needed by higher priority threads.

• Compute-bound threads get their priorities lowered.

Scheduling On Multiprocessor Systems

A multiprocessing operating system is one that can run on computer systems that contain more than one processor. Windows NT is a symmetric multiprocessing (SMP) system, meaning that it assumes that all of the processors are equal and that they all have access to the same physical memory. Therefore, Windows NT can run any thread on any available processor regardless of what process, user or Executive, owns the thread.

There are also asymmetric multiprocessing (ASMP) systems in which processors are different from each other--they may address different physical memory spaces, or they may have other differences. These operating systems only run certain processes on certain processors--for instance, the kernel might always execute on a particular processor.

The design of Windows NT supports processor affinity , whereby a process or thread can specify that it is to run on a particular set of processors, but this facility isn't supported in the first release.

Windows NT uses the same rules for scheduling on a multiprocessor system as it does on a single processor system, so at any given time the threads that are ready and have the highest priorities are actually running.

Before Going On

Before you go on, make sure you can answer the following questions:

1. What is the difference between preemptive and non-preemptive multitasking? In preemptive multitasking, what is a time quantum?

2. What are processes and threads in Windows NT? Are objects owned by processes or threads? How can an application benefit from having multiple threads of execution?

3. Why will a multithreaded Windows NT application execute faster on a multiprocessor workstation than on a uniprocessor system, while a single-threaded application executes at roughly the same speed on both systems?

4. What is meant by the terms thread scheduling and context switching? What type of information makes up a thread's context?

5. What are the relative priorities of real-time- and variable-priority threads? What are each used for? What can cause the priority of a variable-priority thread to change?

6. What event(s) cause a thread to make the following dispatcher state transitions: Running to Waiting, Running to Ready, Waiting to Ready, Ready to Running?

7. If a lower priority thread is running, will it be preempted when a higher priory thread enters the ready state, even if the lower priority thread has time remaining in its quantum?

8. Why is synchronization of threads sometimes necessary? How does this relate to critical sections?

9. What is multiprocessing? What is the difference between symmetric multiprocessing (SMP) and asymmetric multiprocessing (ASMP)? What is processor affinity? How are multiple processors scheduled under Windows NT?

Speaking The Language

This lesson introduced terms that it is important for you to understand. Please look through the list and verify that you understand the meaning of each term:

• Task

• Multitasking

• Non-preemptive multitasking

• Preemptive multitasking

• Time quantum

• Thread

• Thread Scheduling

• Context switching

• Critical section

• Dispatcher state

• Real-time priority

• Variable priority

• Priority queue

• Multiprocessing

• Symmetric multiprocessing (SMP)

• Processor affinity

To Learn More

If you're interested in learning more about this topic, you may find the following resources useful:

• Chapters 4 and 7 of Inside NT.