发信人: bigapple (红富士), 信区: NTM
标  题: NT for Soft Real-time Control(Dispatch Algorithm)
发信站: 哈工大紫丁香 (Tue Jul 25 11:01:56 2000) , 转信


 Dispatch Algorithms of the Windows NT Operating System
 Before discussing the soft real-time performance tests of the Windows NT oper
ating system, we need to review its basic dispatching algorithms.  Essentially
, the Windows NT operating system dispatches three types of objects: 
刋 Interrupt service routines (ISRs)  ISRs are driver routines primarily dispatched in response to device interrupts.
刋 Deferred procedure calls (DPCs)  DPCs are driver routines queued by ISRs to perform less time-critical processing.
刋 Dispatched threads of execution (threads) Threads are the primary execution unit supported by the scheduler in the Windows NT operating system.  The kernel, device drivers, and processes can own threads.   
         
   Figure 1: Simplified view of dispatch algorithms in the Windows NT operatin
g system. Running Soft Control in the Real-time (RT) Class prevents other appl
ications from severely affecting determinism. However, lower priority applicat
ions do affect determinism when they cause Ring 0 device drivers to perform op
erations such as reading and writing to disk.

Interrupt Service Routines
 An ISR has an associated interrupt priority level called the IRQL and is rela
ted to hardware interrupt request levels.  The Windows NT operating system use
s 32 interrupt levels, numbered 0-31. The operating systemˇs  Hardware Abstra
ction Layer (HAL) usually maps the 16 PC hardware interrupt request levels to 
IRQLs 12 through 27 (see Table 1).  When hardware interrupt requests occur, th
e virtual programmable interrupt controller (VPIC) located in the HAL delays t
heir dispatch if the IRQL assigned to the interrupt is less than the IRQL of t
he currently executing object.  
 When interrupts are dispatched, the IRQL is raised to the value associated wi
th the interrupt. However, an ISR can raise and lower the IRQL while the ISR r
uns.  When the ISR returns, the IRQL is restored to its original value.  If in
terrupts are pending when the IRQL is lowered beneath the ISRˇs assigned IRQL
 level, then the highest priority pending interrupt is dispatched immediately.
  
 ISRs can prevent pre-emption during their execution by raising the IRQL to a 
high level (KeRaiseIrql), and later lowering it (KeLowerIrql).  Though it is c
onsidered a violation of the device driver rules of the Windows NT operating s
ystem, any privileged (ring 0) routine can also disable interrupts (the x86 CL
I instruction) and perform time critical operations rather than raising and lo
wering the IRQL.  Interrupt processing resumes when the task re-enables the in
terrupts (the x86 STI instruction).  This is considered an acceptable practice
 for extremely short code path lengths if there is no other solution available
 to the driver writer (e.g., dealing with problem hardware, which requires ver
y tight timing, and IRQL manipulation is ineffective.)  

 Table 1: Level Assignments of the Windows NT Operating System
 Interrupt Level (IRQL)  Assignment
 Level 31  Hardware error interrupt (NM)
 Level 30  Power failure interrupt
 Level 29  Inter-processor doorbell
 Level 28  Clock interrupt
 Levels 12-27  Mapped to PC hardware IRQLs 0-15
 Levels 4-11  Unassigned
 Level 3  Software debugger interrupt
 Levels 0-2  System synchronization soft interrupts
 
  
Deferred Procedure Calls
 While the ISR is running, it may post a request for a DPC to run later on its
 behalf. Drivers may also ask for deferred procedure calls to be queued using 
kernel or I/O timers.  The kernel API supports timer resolutions in 0.10 micro
second increments, however, this only guarantees that the DPC gets queued to e
xecute, and actual kernel timer services are not guaranteed to function at tha
t high a resolution.  
 Microsoft recommends that drivers should be designed to have as short an ISR 
as possible, and they should be able to tolerate significant delays in the dis
patch of their DPCs.  Keeping ISRs as short as possible and tolerating delays 
before DPC processing are the two key factors in making drivers able to be use
d in the same machine without interfering with each other.  Drivers that mask 
interrupt processing for prolonged periods of time can interfere with the oper
ation of other drivers.  
 The DPC is normally added to a first-in, first-out (FIFO) queue of pending DP
Cs.  If DPCs are present in the queue, they are dispatched when the ISR activi
ty has ceased.  The DPCs are not prioritized and execute to completion in thei
r queued order.  In multiprocessor systems, multiple DPCs can be active on dif
ferent processors at the same time.  Also, in multiprocessor systems, the DPC 
can become immediately active upon queuing if the other processor is not at an
 elevated IRQL level.

 Figure 2: Process Classes and Thread Priorities of the Windows NT Operating S
ystem
  
 Threads are dispatched on a processor when there are no ISRs dispatched and n
o DPCs pending.  Internally, the Windows NT operating system maintains 32 thre
ad priority levels, numbered 0-31, and dispatches the highest priority thread.
 The Windows NT operating system  has different policies for treating threads 
with priorities between 0 and 15 than it has for threads with priorities betwe
en 16 and 31.  The higher priority threads have static priorities; they run un
til they block, yield, or complete. If multiple threads are of the same priori
ty, they run in a round-robin fashion.  In Win32 APIs, these priorities are ex
posed as the Real-time Priority Class.
 The policy for threads with priorities between 0 and 15 is to dispatch the hi
ghest- priority thread, but rather than simply letting the thread run until it
 blocks, yields, or completes, it also will round-robin time-slice multitask w
ith other threads at its priority using a 10 millisecond quantum.  In addition
, the Windows NT operating system applies several unique heuristic rules that 
automatically boost and decay thread priorities in this priority range.  This 
range is exposed in Win32 application programming interfaces (APIs) as normal 
priority class, high priority class and idle priority class (see Figure 2).  D
esktop applications normally operate in normal priority class.

Privilege Levels
 ISRs and DPCs always execute at a privileged level (ring 0).  Threads may run
 at a privileged level or at the application level (ring 3).  Any code executi
ng at ring 0 can execute privileged instructions, which on the x86 include CLI
, STI, and HLT.  Code running at ring 3 can try to run privileged instructions
, but it will generate a privileged instruction violation exception. When this
 happens, the exception handler of the Windows NT operating system either stop
s the thread or performs the instruction on its behalf.

Symmetrical Multiprocessing
 When the Windows NT operating system is running with multiple processors, it 
has a symmetrical dispatch policy. The Windows NT operating system verifies th
at the N highest-priority objects are running at all times (where N is the num
ber of processors).  If a thread can be run and multiple processors are equall
y available, the Windows NT operating system attempts to schedule the thread o
n the same processor that it ran on last, to improve processor cache performan
ce.  Some early SMP HALs only dispatched ISRs on one processor, to simplify bu
s access synchronization. Most current system HALs support dual ISR dispatch. 
 Dual-processor systems have become fairly common, and quad- processor systems
 are now available.  Further increases in SMP processing power are expected in
 1998.

Summary
 To summarize, the Windows NT operating system dispatches three types of objec
ts: ISRs, DPCs and threads.  All ISRs are higher priority than all DPCs.  DPCs
 execute in first-in-first-out (FIFO) order.  Threads are present in four clas
ses and are scheduled by priority.  The highest priority class does not have d
ynamic priority boosting and threads run until they block, yield or complete. 
 The three lower priority classes use a dynamic priority-boosting algorithm de
veloped to enhance desktop operations, and also have a 10-millisecond quantum 
that is used for 

--
※ 来源:．哈工大紫丁香WWW bbs.hit.edu.cn. [FROM: 203.123.2.2]