2 * PROJECT: ReactOS Kernel
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: ntoskrnl/ke/thrdschd.c
5 * PURPOSE: Kernel Thread Scheduler (Affinity, Priority, Scheduling)
6 * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
9 /* INCLUDES ******************************************************************/
16 # define InterlockedOrSetMember(Destination, SetMember) \
17 InterlockedOr64((PLONG64)Destination, SetMember);
19 # define InterlockedOrSetMember(Destination, SetMember) \
20 InterlockedOr((PLONG)Destination, SetMember);
23 /* GLOBALS *******************************************************************/
25 ULONG_PTR KiIdleSummary
;
26 ULONG_PTR KiIdleSMTSummary
;
28 /* FUNCTIONS *****************************************************************/
32 KiIdleSchedule(IN PKPRCB Prcb
)
35 ASSERTMSG("SMP: Not yet implemented\n", FALSE
);
41 KiProcessDeferredReadyList(IN PKPRCB Prcb
)
43 PSINGLE_LIST_ENTRY ListEntry
;
46 /* Make sure there is something on the ready list */
47 ASSERT(Prcb
->DeferredReadyListHead
.Next
!= NULL
);
49 /* Get the first entry and clear the list */
50 ListEntry
= Prcb
->DeferredReadyListHead
.Next
;
51 Prcb
->DeferredReadyListHead
.Next
= NULL
;
53 /* Start processing loop */
56 /* Get the thread and advance to the next entry */
57 Thread
= CONTAINING_RECORD(ListEntry
, KTHREAD
, SwapListEntry
);
58 ListEntry
= ListEntry
->Next
;
60 /* Make the thread ready */
61 KiDeferredReadyThread(Thread
);
62 } while (ListEntry
!= NULL
);
64 /* Make sure the ready list is still empty */
65 ASSERT(Prcb
->DeferredReadyListHead
.Next
== NULL
);
70 KiQueueReadyThread(IN PKTHREAD Thread
,
73 /* Call the macro. We keep the API for compatibility with ASM code */
74 KxQueueReadyThread(Thread
, Prcb
);
79 KiDeferredReadyThread(IN PKTHREAD Thread
)
84 KPRIORITY OldPriority
;
88 ASSERT(Thread
->State
== DeferredReady
);
89 ASSERT((Thread
->Priority
>= 0) && (Thread
->Priority
<= HIGH_PRIORITY
));
91 /* Check if we have any adjusts to do */
92 if (Thread
->AdjustReason
== AdjustBoost
)
95 KiAcquireThreadLock(Thread
);
97 /* Check if the priority is low enough to qualify for boosting */
98 if ((Thread
->Priority
<= Thread
->AdjustIncrement
) &&
99 (Thread
->Priority
< (LOW_REALTIME_PRIORITY
- 3)) &&
100 !(Thread
->DisableBoost
))
102 /* Calculate the new priority based on the adjust increment */
103 OldPriority
= min(Thread
->AdjustIncrement
+ 1,
104 LOW_REALTIME_PRIORITY
- 3);
106 /* Make sure we're not decreasing outside of the priority range */
107 ASSERT((Thread
->PriorityDecrement
>= 0) &&
108 (Thread
->PriorityDecrement
<= Thread
->Priority
));
110 /* Calculate the new priority decrement based on the boost */
111 Thread
->PriorityDecrement
+= ((SCHAR
)OldPriority
- Thread
->Priority
);
113 /* Again verify that this decrement is valid */
114 ASSERT((Thread
->PriorityDecrement
>= 0) &&
115 (Thread
->PriorityDecrement
<= OldPriority
));
117 /* Set the new priority */
118 Thread
->Priority
= (SCHAR
)OldPriority
;
121 /* We need 4 quanta, make sure we have them, then decrease by one */
122 if (Thread
->Quantum
< 4) Thread
->Quantum
= 4;
125 /* Make sure the priority is still valid */
126 ASSERT((Thread
->Priority
>= 0) && (Thread
->Priority
<= HIGH_PRIORITY
));
128 /* Release the lock and clear the adjust reason */
129 KiReleaseThreadLock(Thread
);
130 Thread
->AdjustReason
= AdjustNone
;
132 else if (Thread
->AdjustReason
== AdjustUnwait
)
134 /* Acquire the thread lock and check if this is a real-time thread */
135 KiAcquireThreadLock(Thread
);
136 if (Thread
->Priority
< LOW_REALTIME_PRIORITY
)
138 /* It's not real time, but is it time critical? */
139 if (Thread
->BasePriority
>= (LOW_REALTIME_PRIORITY
- 2))
141 /* It is, so simply reset its quantum */
142 Thread
->Quantum
= Thread
->QuantumReset
;
146 /* Has the priority been adjusted previously? */
147 if (!(Thread
->PriorityDecrement
) && (Thread
->AdjustIncrement
))
149 /* Yes, reset its quantum */
150 Thread
->Quantum
= Thread
->QuantumReset
;
153 /* Wait code already handles quantum adjustment during APCs */
154 if (Thread
->WaitStatus
!= STATUS_KERNEL_APC
)
156 /* Decrease the quantum by one and check if we're out */
157 if (--Thread
->Quantum
<= 0)
159 /* We are, reset the quantum and get a new priority */
160 Thread
->Quantum
= Thread
->QuantumReset
;
161 Thread
->Priority
= KiComputeNewPriority(Thread
, 1);
166 /* Now check if we have no decrement and boosts are enabled */
167 if (!(Thread
->PriorityDecrement
) && !(Thread
->DisableBoost
))
169 /* Make sure we have an increment */
170 ASSERT(Thread
->AdjustIncrement
>= 0);
172 /* Calculate the new priority after the increment */
173 OldPriority
= Thread
->BasePriority
+ Thread
->AdjustIncrement
;
175 /* Check if this new priority is higher */
176 if (OldPriority
> Thread
->Priority
)
178 /* Make sure we don't go into the real time range */
179 if (OldPriority
>= LOW_REALTIME_PRIORITY
)
181 /* Normalize it back down one notch */
182 OldPriority
= LOW_REALTIME_PRIORITY
- 1;
185 /* Check if the priority is higher then the boosted base */
186 if (OldPriority
> (Thread
->BasePriority
+
187 Thread
->AdjustIncrement
))
189 /* Setup a priority decrement to nullify the boost */
190 Thread
->PriorityDecrement
= ((SCHAR
)OldPriority
-
191 Thread
->BasePriority
-
192 Thread
->AdjustIncrement
);
195 /* Make sure that the priority decrement is valid */
196 ASSERT((Thread
->PriorityDecrement
>= 0) &&
197 (Thread
->PriorityDecrement
<= OldPriority
));
199 /* Set this new priority */
200 Thread
->Priority
= (SCHAR
)OldPriority
;
206 /* It's a real-time thread, so just reset its quantum */
207 Thread
->Quantum
= Thread
->QuantumReset
;
210 /* Make sure the priority makes sense */
211 ASSERT((Thread
->Priority
>= 0) && (Thread
->Priority
<= HIGH_PRIORITY
));
213 /* Release the thread lock and reset the adjust reason */
214 KiReleaseThreadLock(Thread
);
215 Thread
->AdjustReason
= AdjustNone
;
218 /* Clear thread preemption status and save current values */
219 Preempted
= Thread
->Preempted
;
220 OldPriority
= Thread
->Priority
;
221 Thread
->Preempted
= FALSE
;
223 /* Queue the thread on CPU 0 and get the PRCB and lock it */
224 Thread
->NextProcessor
= 0;
225 Prcb
= KiProcessorBlock
[0];
226 KiAcquirePrcbLock(Prcb
);
228 /* Check if we have an idle summary */
231 /* Clear it and set this thread as the next one */
233 Thread
->State
= Standby
;
234 Prcb
->NextThread
= Thread
;
236 /* Unlock the PRCB and return */
237 KiReleasePrcbLock(Prcb
);
241 /* Set the CPU number */
242 Thread
->NextProcessor
= (UCHAR
)Processor
;
244 /* Get the next scheduled thread */
245 NextThread
= Prcb
->NextThread
;
249 ASSERT(NextThread
->State
== Standby
);
251 /* Check if priority changed */
252 if (OldPriority
> NextThread
->Priority
)
254 /* Preempt the thread */
255 NextThread
->Preempted
= TRUE
;
257 /* Put this one as the next one */
258 Thread
->State
= Standby
;
259 Prcb
->NextThread
= Thread
;
261 /* Set it in deferred ready mode */
262 NextThread
->State
= DeferredReady
;
263 NextThread
->DeferredProcessor
= Prcb
->Number
;
264 KiReleasePrcbLock(Prcb
);
265 KiDeferredReadyThread(NextThread
);
271 /* Set the next thread as the current thread */
272 NextThread
= Prcb
->CurrentThread
;
273 if (OldPriority
> NextThread
->Priority
)
275 /* Preempt it if it's already running */
276 if (NextThread
->State
== Running
) NextThread
->Preempted
= TRUE
;
278 /* Set the thread on standby and as the next thread */
279 Thread
->State
= Standby
;
280 Prcb
->NextThread
= Thread
;
282 /* Release the lock */
283 KiReleasePrcbLock(Prcb
);
285 /* Check if we're running on another CPU */
286 if (KeGetCurrentProcessorNumber() != Thread
->NextProcessor
)
288 /* We are, send an IPI */
289 KiIpiSend(AFFINITY_MASK(Thread
->NextProcessor
), IPI_DPC
);
296 ASSERT((OldPriority
>= 0) && (OldPriority
<= HIGH_PRIORITY
));
298 /* Set this thread as ready */
299 Thread
->State
= Ready
;
300 Thread
->WaitTime
= KeTickCount
.LowPart
;
302 /* Insert this thread in the appropriate order */
303 Preempted
? InsertHeadList(&Prcb
->DispatcherReadyListHead
[OldPriority
],
304 &Thread
->WaitListEntry
) :
305 InsertTailList(&Prcb
->DispatcherReadyListHead
[OldPriority
],
306 &Thread
->WaitListEntry
);
308 /* Update the ready summary */
309 Prcb
->ReadySummary
|= PRIORITY_MASK(OldPriority
);
312 ASSERT(OldPriority
== Thread
->Priority
);
314 /* Release the lock */
315 KiReleasePrcbLock(Prcb
);
320 KiSelectNextThread(IN PKPRCB Prcb
)
324 /* Select a ready thread */
325 Thread
= KiSelectReadyThread(0, Prcb
);
328 /* Didn't find any, get the current idle thread */
329 Thread
= Prcb
->IdleThread
;
331 /* Enable idle scheduling */
332 InterlockedOrSetMember(&KiIdleSummary
, Prcb
->SetMember
);
333 Prcb
->IdleSchedule
= TRUE
;
335 /* FIXME: SMT support */
336 ASSERTMSG("SMP: Not yet implemented\n", FALSE
);
339 /* Sanity checks and return the thread */
340 ASSERT(Thread
!= NULL
);
341 ASSERT((Thread
->BasePriority
== 0) || (Thread
->Priority
!= 0));
347 KiSwapThread(IN PKTHREAD CurrentThread
,
350 BOOLEAN ApcState
= FALSE
;
354 ASSERT(KeGetCurrentIrql() >= DISPATCH_LEVEL
);
356 /* Acquire the PRCB lock */
357 KiAcquirePrcbLock(Prcb
);
359 /* Get the next thread */
360 NextThread
= Prcb
->NextThread
;
363 /* Already got a thread, set it up */
364 Prcb
->NextThread
= NULL
;
365 Prcb
->CurrentThread
= NextThread
;
366 NextThread
->State
= Running
;
370 /* Try to find a ready thread */
371 NextThread
= KiSelectReadyThread(0, Prcb
);
375 Prcb
->CurrentThread
= NextThread
;
376 NextThread
->State
= Running
;
380 /* Set the idle summary */
381 InterlockedOrSetMember(&KiIdleSummary
, Prcb
->SetMember
);
383 /* Schedule the idle thread */
384 NextThread
= Prcb
->IdleThread
;
385 Prcb
->CurrentThread
= NextThread
;
386 NextThread
->State
= Running
;
390 /* Sanity check and release the PRCB */
391 ASSERT(CurrentThread
!= Prcb
->IdleThread
);
392 KiReleasePrcbLock(Prcb
);
394 /* Save the wait IRQL */
395 WaitIrql
= CurrentThread
->WaitIrql
;
398 ApcState
= KiSwapContext(WaitIrql
, CurrentThread
);
400 /* Get the wait status */
401 WaitStatus
= CurrentThread
->WaitStatus
;
403 /* Check if we need to deliver APCs */
406 /* Lower to APC_LEVEL */
407 KeLowerIrql(APC_LEVEL
);
410 KiDeliverApc(KernelMode
, NULL
, NULL
);
411 ASSERT(WaitIrql
== 0);
414 /* Lower IRQL back to what it was and return the wait status */
415 KeLowerIrql(WaitIrql
);
421 KiReadyThread(IN PKTHREAD Thread
)
423 IN PKPROCESS Process
= Thread
->ApcState
.Process
;
425 /* Check if the process is paged out */
426 if (Process
->State
!= ProcessInMemory
)
428 /* We don't page out processes in ROS */
431 else if (!Thread
->KernelStackResident
)
433 /* Increase the stack count */
434 ASSERT(Process
->StackCount
!= MAXULONG_PTR
);
435 Process
->StackCount
++;
437 /* Set the thread to transition */
438 ASSERT(Thread
->State
!= Transition
);
439 Thread
->State
= Transition
;
441 /* The stack is always resident in ROS */
446 /* Insert the thread on the deferred ready list */
447 KiInsertDeferredReadyList(Thread
);
453 KiAdjustQuantumThread(IN PKTHREAD Thread
)
455 PKPRCB Prcb
= KeGetCurrentPrcb();
458 /* Acquire thread and PRCB lock */
459 KiAcquireThreadLock(Thread
);
460 KiAcquirePrcbLock(Prcb
);
462 /* Don't adjust for RT threads */
463 if ((Thread
->Priority
< LOW_REALTIME_PRIORITY
) &&
464 (Thread
->BasePriority
< (LOW_REALTIME_PRIORITY
- 2)))
466 /* Decrease Quantum by one and see if we've ran out */
467 if (--Thread
->Quantum
<= 0)
470 Thread
->Quantum
= Thread
->QuantumReset
;
472 /* Calculate new Priority */
473 Thread
->Priority
= KiComputeNewPriority(Thread
, 1);
475 /* Check if there's no next thread scheduled */
476 if (!Prcb
->NextThread
)
478 /* Select a ready thread and check if we found one */
479 NextThread
= KiSelectReadyThread(Thread
->Priority
, Prcb
);
482 /* Set it on standby and switch to it */
483 NextThread
->State
= Standby
;
484 Prcb
->NextThread
= NextThread
;
489 /* This thread can be preempted again */
490 Thread
->Preempted
= FALSE
;
496 KiReleasePrcbLock(Prcb
);
497 KiReleaseThreadLock(Thread
);
498 KiExitDispatcher(Thread
->WaitIrql
);
503 KiSetPriorityThread(IN PKTHREAD Thread
,
504 IN KPRIORITY Priority
)
508 BOOLEAN RequestInterrupt
= FALSE
;
509 KPRIORITY OldPriority
;
511 ASSERT((Priority
>= 0) && (Priority
<= HIGH_PRIORITY
));
513 /* Check if priority changed */
514 if (Thread
->Priority
!= Priority
)
516 /* Loop priority setting in case we need to start over */
519 /* Choose action based on thread's state */
520 if (Thread
->State
== Ready
)
522 /* Make sure we're not on the ready queue */
523 if (!Thread
->ProcessReadyQueue
)
525 /* Get the PRCB for the thread and lock it */
526 Processor
= Thread
->NextProcessor
;
527 Prcb
= KiProcessorBlock
[Processor
];
528 KiAcquirePrcbLock(Prcb
);
530 /* Make sure the thread is still ready and on this CPU */
531 if ((Thread
->State
== Ready
) &&
532 (Thread
->NextProcessor
== Prcb
->Number
))
535 ASSERT((Prcb
->ReadySummary
&
536 PRIORITY_MASK(Thread
->Priority
)));
538 /* Remove it from the current queue */
539 if (RemoveEntryList(&Thread
->WaitListEntry
))
541 /* Update the ready summary */
542 Prcb
->ReadySummary
^= PRIORITY_MASK(Thread
->
546 /* Update priority */
547 Thread
->Priority
= (SCHAR
)Priority
;
549 /* Re-insert it at its current priority */
550 KiInsertDeferredReadyList(Thread
);
552 /* Release the PRCB Lock */
553 KiReleasePrcbLock(Prcb
);
557 /* Release the lock and loop again */
558 KiReleasePrcbLock(Prcb
);
564 /* It's already on the ready queue, just update priority */
565 Thread
->Priority
= (SCHAR
)Priority
;
568 else if (Thread
->State
== Standby
)
570 /* Get the PRCB for the thread and lock it */
571 Processor
= Thread
->NextProcessor
;
572 Prcb
= KiProcessorBlock
[Processor
];
573 KiAcquirePrcbLock(Prcb
);
575 /* Check if we're still the next thread to run */
576 if (Thread
== Prcb
->NextThread
)
578 /* Get the old priority and update ours */
579 OldPriority
= Thread
->Priority
;
580 Thread
->Priority
= (SCHAR
)Priority
;
582 /* Check if there was a change */
583 if (Priority
< OldPriority
)
585 /* Find a new thread */
586 NewThread
= KiSelectReadyThread(Priority
+ 1, Prcb
);
589 /* Found a new one, set it on standby */
590 NewThread
->State
= Standby
;
591 Prcb
->NextThread
= NewThread
;
593 /* Dispatch our thread */
594 KiInsertDeferredReadyList(Thread
);
598 /* Release the PRCB lock */
599 KiReleasePrcbLock(Prcb
);
603 /* Release the lock and try again */
604 KiReleasePrcbLock(Prcb
);
608 else if (Thread
->State
== Running
)
610 /* Get the PRCB for the thread and lock it */
611 Processor
= Thread
->NextProcessor
;
612 Prcb
= KiProcessorBlock
[Processor
];
613 KiAcquirePrcbLock(Prcb
);
615 /* Check if we're still the current thread running */
616 if (Thread
== Prcb
->CurrentThread
)
618 /* Get the old priority and update ours */
619 OldPriority
= Thread
->Priority
;
620 Thread
->Priority
= (SCHAR
)Priority
;
622 /* Check if there was a change and there's no new thread */
623 if ((Priority
< OldPriority
) && !(Prcb
->NextThread
))
625 /* Find a new thread */
626 NewThread
= KiSelectReadyThread(Priority
+ 1, Prcb
);
629 /* Found a new one, set it on standby */
630 NewThread
->State
= Standby
;
631 Prcb
->NextThread
= NewThread
;
633 /* Request an interrupt */
634 RequestInterrupt
= TRUE
;
638 /* Release the lock and check if we need an interrupt */
639 KiReleasePrcbLock(Prcb
);
640 if (RequestInterrupt
)
642 /* Check if we're running on another CPU */
643 if (KeGetCurrentProcessorNumber() != Processor
)
645 /* We are, send an IPI */
646 KiIpiSend(AFFINITY_MASK(Processor
), IPI_DPC
);
652 /* Thread changed, release lock and restart */
653 KiReleasePrcbLock(Prcb
);
657 else if (Thread
->State
== DeferredReady
)
660 DPRINT1("Deferred state not yet supported\n");
665 /* Any other state, just change priority */
666 Thread
->Priority
= (SCHAR
)Priority
;
669 /* If we got here, then thread state was consistent, so bail out */
677 KiSetAffinityThread(IN PKTHREAD Thread
,
678 IN KAFFINITY Affinity
)
680 KAFFINITY OldAffinity
;
682 /* Get the current affinity */
683 OldAffinity
= Thread
->UserAffinity
;
685 /* Make sure that the affinity is valid */
686 if (((Affinity
& Thread
->ApcState
.Process
->Affinity
) != (Affinity
)) ||
689 /* Bugcheck the system */
690 KeBugCheck(INVALID_AFFINITY_SET
);
693 /* Update the new affinity */
694 Thread
->UserAffinity
= Affinity
;
696 /* Check if system affinity is disabled */
697 if (!Thread
->SystemAffinityActive
)
700 DPRINT1("Affinity support disabled!\n");
703 /* Return the old affinity */
708 // This macro exists because NtYieldExecution locklessly attempts to read from
709 // the KPRCB's ready summary, and the usual way of going through KeGetCurrentPrcb
710 // would require getting fs:1C first (or gs), and then doing another dereference.
711 // In an attempt to minimize the amount of instructions and potential race/tear
712 // that could happen, Windows seems to define this as a macro that directly acceses
713 // the ready summary through a single fs: read by going through the KPCR's PrcbData.
715 // See http://research.microsoft.com/en-us/collaboration/global/asia-pacific/
716 // programs/trk_case4_process-thread_management.pdf
718 // We need this per-arch because sometimes it's Prcb and sometimes PrcbData, and
719 // because on x86 it's FS, and on x64 it's GS (not sure what it is on ARM/PPC).
722 #define KiGetCurrentReadySummary() __readfsdword(FIELD_OFFSET(KIPCR, PrcbData.ReadySummary))
724 #define KiGetCurrentReadySummary() __readgsdword(FIELD_OFFSET(KIPCR, Prcb.ReadySummary))
734 NtYieldExecution(VOID
)
739 PKTHREAD Thread
, NextThread
;
741 /* NB: No instructions (other than entry code) should preceed this line */
743 /* Fail if there's no ready summary */
744 if (!KiGetCurrentReadySummary()) return STATUS_NO_YIELD_PERFORMED
;
746 /* Now get the current thread, set the status... */
747 Status
= STATUS_NO_YIELD_PERFORMED
;
748 Thread
= KeGetCurrentThread();
750 /* Raise IRQL to synch and get the KPRCB now */
751 OldIrql
= KeRaiseIrqlToSynchLevel();
752 Prcb
= KeGetCurrentPrcb();
754 /* Now check if there's still a ready summary */
755 if (Prcb
->ReadySummary
)
757 /* Acquire thread and PRCB lock */
758 KiAcquireThreadLock(Thread
);
759 KiAcquirePrcbLock(Prcb
);
761 /* Find a new thread to run if none was selected */
762 if (!Prcb
->NextThread
) Prcb
->NextThread
= KiSelectReadyThread(1, Prcb
);
764 /* Make sure we still have a next thread to schedule */
765 NextThread
= Prcb
->NextThread
;
768 /* Reset quantum and recalculate priority */
769 Thread
->Quantum
= Thread
->QuantumReset
;
770 Thread
->Priority
= KiComputeNewPriority(Thread
, 1);
772 /* Release the thread lock */
773 KiReleaseThreadLock(Thread
);
775 /* Set context swap busy */
776 KiSetThreadSwapBusy(Thread
);
778 /* Set the new thread as running */
779 Prcb
->NextThread
= NULL
;
780 Prcb
->CurrentThread
= NextThread
;
781 NextThread
->State
= Running
;
783 /* Setup a yield wait and queue the thread */
784 Thread
->WaitReason
= WrYieldExecution
;
785 KxQueueReadyThread(Thread
, Prcb
);
787 /* Make it wait at APC_LEVEL */
788 Thread
->WaitIrql
= APC_LEVEL
;
791 ASSERT(OldIrql
<= DISPATCH_LEVEL
);
793 /* Swap to new thread */
794 KiSwapContext(APC_LEVEL
, Thread
);
795 Status
= STATUS_SUCCESS
;
799 /* Release the PRCB and thread lock */
800 KiReleasePrcbLock(Prcb
);
801 KiReleaseThreadLock(Thread
);
805 /* Lower IRQL and return */
806 KeLowerIrql(OldIrql
);