schedule.c

可用于嵌入式编程学习

/*
 *              NK Kernel scheduler code
 *
 *              Copyright (c) 1995-2000 Microsoft Corporation.  All rights reserved.
 *
 * Module Name:
 *
 *              schedule.c
 *
 * Abstract:
 *
 *              This file implements the scheduler for the NK kernel
 *
 *
 */

/* @doc EXTERNAL KERNEL */
/* @topic Kernel Entrypoints | Kernel Entrypoints */

#include "kernel.h"
#ifdef ARM
#include "nkarm.h"
#endif

BOOL PageOutForced, bLastIdle;

DWORD dwDefaultThreadQuantum;

typedef void (* LogThreadCreate_t)(DWORD, DWORD);
typedef void (* LogThreadDelete_t)(DWORD, DWORD);
typedef void (* LogProcessCreate_t)(DWORD);
typedef void (* LogProcessDelete_t)(DWORD);
typedef void (* LogThreadSwitch_t)(DWORD, DWORD);

LogThreadCreate_t pLogThreadCreate;
LogThreadDelete_t pLogThreadDelete;
LogProcessCreate_t pLogProcessCreate;
LogProcessDelete_t pLogProcessDelete;
LogThreadSwitch_t pLogThreadSwitch;

extern void (* pEdbgInitializeInterrupt)(void);

/* General design: 
	There are many queues in the system, for all categories of processes.  All
	processes are on exactly one queue, with the exception of the currently
	running process (if any) which is on the NULL queue.  Runnable processes are
	on one of the run queues (there are several, one for each priority).  Examples
	of other queues are for sleeping, blocked on a critical section (one per
	critical section), etc.  Preemption grabs the current thread (if any) and puts
	it at the end of the queue for that thread's priority, and then grabs the
	highest priority thread (which should, by definition, always be at the same
	priority as the preempted thread, else the other thread would have been
	running [in the case of a higher prio], or we would have continued running
	the preempted thread [in the case of a lower prio].  Kernel routines take
	threads off of queues and put them on other queues.  NextThread finds the
	next thread to run, or returns 0 if there are no runnable threads.  We preempt
	with a fixed timeslice (probably 10ms).
*/

CRITICAL_SECTION csDbg, DbgApiCS, NameCS, CompCS, LLcs, ModListcs, WriterCS, MapCS, PagerCS;
CRITICAL_SECTION MapNameCS, PhysCS, ppfscs, ODScs, RFBcs, VAcs, rtccs, PageOutCS;

#ifdef DEBUG
CRITICAL_SECTION EdbgODScs, TimerListCS;
#endif

THREADTIME *TTList;

#if defined(x86)
extern PTHREAD g_CurFPUOwner;
#endif

RunList_t RunList;
PTHREAD SleepList;
HANDLE hEventList;
HANDLE hMutexList;
HANDLE hSemList;
DWORD dwSleepMin;
DWORD dwPreempt;
DWORD dwPartialDiffMSec = 0;
BOOL bPreempt;
DWORD ticksleft;

DWORD currmaxprio = MAX_PRIORITY_LEVELS - 1;
DWORD CurrTime;
PTHREAD pOOMThread;

SYSTEMTIME CurAlarmTime;

HANDLE hAlarmEvent, hAlarmThreadWakeup; 
PTHREAD pCleanupThread;

PROCESS ProcArray[MAX_PROCESSES];
PROCESS *kdProcArray = ProcArray;
struct KDataStruct *kdpKData = &KData;

HANDLE hCoreDll;
void (*TBFf)(LPVOID, ulong);
void (*MTBFf)(LPVOID, ulong, ulong, ulong, ulong);
void (*CTBFf)(LPVOID, ulong, ulong, ulong, ulong);
BOOL (*KSystemTimeToFileTime)(LPSYSTEMTIME, LPFILETIME);
LONG (*KCompareFileTime)(LPFILETIME, LPFILETIME);
BOOL (*KLocalFileTimeToFileTime)(const FILETIME *, LPFILETIME);
BOOL (*KFileTimeToSystemTime)(const FILETIME *, LPSYSTEMTIME);
void (*pPSLNotify)(DWORD, DWORD, DWORD);
BOOL (*pGetHeapSnapshot)(THSNAP *pSnap, BOOL bMainOnly, LPVOID *pDataPtr);
HANDLE (*pGetProcessHeap)(void);

LPVOID pExitThread;
LPDWORD pIsExiting;
extern Name *pDebugger;

void DoPageOut(void);
extern DWORD PageOutNeeded;
BYTE GetHighPos(DWORD);

typedef struct RTs {
	PTHREAD pHelper;	// must be first
	DWORD dwBase, dwLen;// if we're freeing the stack
	PPROCESS pProc;		// if we're freeing the proc
	LPTHRDDBG pThrdDbg; // if we're freeing a debug structure
	HANDLE hThread; 	// if we're freeing a handle / threadtime
	PTHREAD pThread;	// if we're freeing a thread structure
	CLEANEVENT *lpce1;
	CLEANEVENT *lpce2;
	CLEANEVENT *lpce3;
	LPDWORD pdwDying;
} RTs;

const PFNVOID ThrdMthds[] = {
	(PFNVOID)SC_ThreadCloseHandle,
	(PFNVOID)0,
	(PFNVOID)UB_ThreadSuspend,
	(PFNVOID)SC_ThreadResume,
	(PFNVOID)SC_ThreadSetPrio,
	(PFNVOID)SC_ThreadGetPrio,
	(PFNVOID)SC_ThreadGetCode,
	(PFNVOID)SC_ThreadGetContext,
	(PFNVOID)SC_ThreadSetContext,
	(PFNVOID)SC_ThreadTerminate,
	(PFNVOID)SC_CeGetThreadPriority,
	(PFNVOID)SC_CeSetThreadPriority,
	(PFNVOID)SC_CeGetThreadQuantum,
	(PFNVOID)SC_CeSetThreadQuantum,
};

const PFNVOID ProcMthds[] = {
	(PFNVOID)SC_ProcCloseHandle,
	(PFNVOID)0,
	(PFNVOID)SC_ProcTerminate,
	(PFNVOID)SC_ProcGetCode,
	(PFNVOID)0,
	(PFNVOID)SC_ProcFlushICache,
	(PFNVOID)SC_ProcReadMemory,
	(PFNVOID)SC_ProcWriteMemory,
	(PFNVOID)SC_ProcDebug,
};

const PFNVOID EvntMthds[] = {
	(PFNVOID)SC_EventCloseHandle,
	(PFNVOID)0,
	(PFNVOID)SC_EventModify,
	(PFNVOID)SC_EventAddAccess,
};

const PFNVOID MutxMthds[] = {
	(PFNVOID)SC_MutexCloseHandle,
	(PFNVOID)0,
	(PFNVOID)SC_ReleaseMutex,
};

const PFNVOID SemMthds[] = {
	(PFNVOID)SC_SemCloseHandle,
	(PFNVOID)0,
	(PFNVOID)SC_ReleaseSemaphore,
};

const CINFO cinfThread = {
	"THRD",
	DISPATCH_KERNEL_PSL,
	SH_CURTHREAD,
	sizeof(ThrdMthds)/sizeof(ThrdMthds[0]),
	ThrdMthds
};

const CINFO cinfProc = {
	"PROC",
	DISPATCH_KERNEL_PSL,
	SH_CURPROC,
	sizeof(ProcMthds)/sizeof(ProcMthds[0]),
	ProcMthds
};

const CINFO cinfEvent = {
	"EVNT",
	DISPATCH_KERNEL_PSL,
	HT_EVENT,
	sizeof(EvntMthds)/sizeof(EvntMthds[0]),
	EvntMthds
};

const CINFO cinfMutex = {
	"MUTX",
	DISPATCH_KERNEL_PSL,
	HT_MUTEX,
	sizeof(MutxMthds)/sizeof(MutxMthds[0]),
	MutxMthds
};

const CINFO cinfSem = {
	"SEMP",
	DISPATCH_KERNEL_PSL,
	HT_SEMAPHORE,
	sizeof(SemMthds)/sizeof(SemMthds[0]),
	SemMthds
};

ERRFALSE(offsetof(EVENT, pProxList) == offsetof(PROCESS, pProxList));
ERRFALSE(offsetof(EVENT, pProxList) == offsetof(THREAD, pProxList));
ERRFALSE(offsetof(EVENT, pProxList) == offsetof(STUBEVENT, pProxList));

ERRFALSE(offsetof(CRIT, pProxList) == offsetof(SEMAPHORE, pProxList));
ERRFALSE(offsetof(CRIT, pProxList) == offsetof(MUTEX, pProxList));
ERRFALSE(offsetof(CRIT, pProxList) == offsetof(EVENT, pProxList));
ERRFALSE(offsetof(CRIT, pProxHash) == offsetof(SEMAPHORE, pProxHash));
ERRFALSE(offsetof(CRIT, pProxHash) == offsetof(MUTEX, pProxHash));
ERRFALSE(offsetof(CRIT, pProxHash) == offsetof(EVENT, pProxHash));

ERRFALSE(offsetof(CRIT, bListed) == offsetof(MUTEX, bListed));
ERRFALSE(offsetof(CRIT, bListedPrio) == offsetof(MUTEX, bListedPrio));
ERRFALSE(offsetof(CRIT, pPrevOwned) == offsetof(MUTEX, pPrevOwned));
ERRFALSE(offsetof(CRIT, pNextOwned) == offsetof(MUTEX, pNextOwned));
ERRFALSE(offsetof(CRIT, pUpOwned) == offsetof(MUTEX, pUpOwned));
ERRFALSE(offsetof(CRIT, pDownOwned) == offsetof(MUTEX, pDownOwned));

void GCFT(LPFILETIME lpFileTime) {
	SYSTEMTIME st;
	OEMGetRealTime(&st);
	KSystemTimeToFileTime(&st,lpFileTime);
	KLocalFileTimeToFileTime(lpFileTime,lpFileTime);
}

void DoLinkCritMut(LPCRIT lpcrit, PTHREAD pth, BYTE prio) {
	LPCRIT lpcrit2, lpcrit3;
	BYTE prio2;
	prio2 = prio/PRIORITY_LEVELS_HASHSCALE;
	DEBUGCHK(prio2 < PRIORITY_LEVELS_HASHSIZE);
	DEBUGCHK((DWORD)lpcrit & 0x80000000);
	if (!pth->pOwnedList) {
		lpcrit->pPrevOwned = lpcrit->pNextOwned = 0;
		lpcrit->pUpOwned = lpcrit->pDownOwned = pth->pOwnedHash[prio2] = pth->pOwnedList = lpcrit;
	} else if (prio < pth->pOwnedList->bListedPrio) {
		lpcrit->pPrevOwned = 0;
		lpcrit->pUpOwned = lpcrit->pDownOwned = pth->pOwnedHash[prio2] = pth->pOwnedList->pPrevOwned = lpcrit;
		lpcrit->pNextOwned = pth->pOwnedList;
		pth->pOwnedList = lpcrit;
	} else if (lpcrit2 = pth->pOwnedHash[prio2]) {
		if (prio < lpcrit2->bListedPrio) {
			lpcrit->pPrevOwned = lpcrit2->pPrevOwned;
			lpcrit->pNextOwned = lpcrit2;
			lpcrit->pUpOwned = lpcrit->pDownOwned = pth->pOwnedHash[prio2] = lpcrit->pPrevOwned->pNextOwned = lpcrit2->pPrevOwned = lpcrit;
		} else {
FinishLinkCrit:
			// bounded by MAX_PRIORITY_HASHSCALE
			while ((lpcrit3 = lpcrit2->pNextOwned) && (prio > lpcrit3->bListedPrio))
				lpcrit2 = lpcrit3;
			if (prio == lpcrit2->bListedPrio) {
				lpcrit->pUpOwned = lpcrit2->pUpOwned;
				lpcrit->pUpOwned->pDownOwned = lpcrit2->pUpOwned = lpcrit;
				lpcrit->pDownOwned = lpcrit2;
				lpcrit->pPrevOwned = lpcrit->pNextOwned = 0;
			} else if (!lpcrit3) {
				lpcrit->pNextOwned = 0;
				lpcrit->pPrevOwned = lpcrit2;
				lpcrit->pUpOwned = lpcrit->pDownOwned = lpcrit2->pNextOwned = lpcrit;
			} else {
				 if (prio == lpcrit3->bListedPrio) {
					lpcrit->pUpOwned = lpcrit3->pUpOwned;
					lpcrit->pUpOwned->pDownOwned = lpcrit3->pUpOwned = lpcrit;
					lpcrit->pDownOwned = lpcrit3;
					lpcrit->pPrevOwned = lpcrit->pNextOwned = 0;
				 } else {
					lpcrit->pUpOwned = lpcrit->pDownOwned = lpcrit2->pNextOwned = lpcrit3->pPrevOwned = lpcrit;
					lpcrit->pPrevOwned = lpcrit2;
					lpcrit->pNextOwned = lpcrit3;
				 }
			}
		}
	} else {
		pth->pOwnedHash[prio2] = lpcrit;
		// bounded by PRIORITY_LEVELS_HASHSIZE
		while (!(lpcrit2 = pth->pOwnedHash[--prio2]))
			;
		goto FinishLinkCrit;
	}
	lpcrit->bListed = 1;
}

void LinkCritMut(LPCRIT lpcrit, PTHREAD pth, BOOL bIsCrit) { 
	BYTE prio;
	DEBUGCHK((DWORD)lpcrit & 0x80000000);
	DEBUGCHK(lpcrit->bListed != 1);
	if (!bIsCrit || (lpcrit->lpcs->needtrap && !GET_BURIED(pth))) {
		prio = lpcrit->bListedPrio = (lpcrit->pProxList ? lpcrit->pProxList->prio : MAX_PRIORITY_LEVELS-1);
		DoLinkCritMut(lpcrit,pth,prio);
	}
}

void LaterLinkCritMut(LPCRIT lpcrit, BOOL bIsCrit) { 
	BYTE prio;
	KCALLPROFON(50);
	if (!lpcrit->bListed && (!bIsCrit || (lpcrit->lpcs->needtrap && !GET_BURIED(pCurThread)))) {
		prio = lpcrit->bListedPrio = (lpcrit->pProxList ? lpcrit->pProxList->prio : MAX_PRIORITY_LEVELS-1);
		DoLinkCritMut(lpcrit,pCurThread,prio);
	}
	KCALLPROFOFF(50);
}

void LaterLinkMutOwner(LPMUTEX lpm) { 
	BYTE prio;
	KCALLPROFON(55);
	if (!lpm->bListed) {
		prio = lpm->bListedPrio = (lpm->pProxList ? lpm->pProxList->prio : MAX_PRIORITY_LEVELS-1);
		DoLinkCritMut((LPCRIT)lpm,lpm->pOwner,prio);
	}
	KCALLPROFOFF(55);
}

void UnlinkCritMut(LPCRIT lpcrit, PTHREAD pth) { 
	LPCRIT pDown, pNext;
	WORD prio;
	if (lpcrit->bListed == 1) {
		prio = lpcrit->bListedPrio/PRIORITY_LEVELS_HASHSCALE;
		DEBUGCHK(prio < PRIORITY_LEVELS_HASHSIZE);
		pDown = lpcrit->pDownOwned;
		pNext = lpcrit->pNextOwned;
		if (pth->pOwnedHash[prio] == lpcrit) {
			pth->pOwnedHash[prio] = ((pDown != lpcrit) ? pDown :
				(pNext && (pNext->bListedPrio/PRIORITY_LEVELS_HASHSCALE == prio)) ? pNext : 0);
		}
		if (pDown == lpcrit) {
			if (!lpcrit->pPrevOwned) {
				DEBUGCHK(pth->pOwnedList == lpcrit);
				if (pth->pOwnedList = pNext)
					pNext->pPrevOwned = 0;
			} else {
				if (lpcrit->pPrevOwned->pNextOwned = pNext)
					pNext->pPrevOwned = lpcrit->pPrevOwned;
			}
		} else {
			pDown->pUpOwned = lpcrit->pUpOwned;
			lpcrit->pUpOwned->pDownOwned = pDown;
			if (lpcrit->pPrevOwned) {
				lpcrit->pPrevOwned->pNextOwned = pDown;
				pDown->pPrevOwned = lpcrit->pPrevOwned;
				goto FinishDequeue;
			} else if (lpcrit == pth->pOwnedList) {
				pth->pOwnedList = pDown;
				DEBUGCHK(!pDown->pPrevOwned);
	FinishDequeue:			
				if (pNext) {
					pNext->pPrevOwned = pDown;
					pDown->pNextOwned = pNext;
				}
			}
		}
		lpcrit->bListed = 0;
	}
}

void PreUnlinkCritMut(LPCRIT lpcrit) {
	KCALLPROFON(51);
	UnlinkCritMut(lpcrit,pCurThread);
	SET_NOPRIOCALC(pCurThread);
	KCALLPROFOFF(51);
}

void PostUnlinkCritMut(void) {
	WORD prio, prio2;
	KCALLPROFON(52);
	CLEAR_NOPRIOCALC(pCurThread);
	prio = GET_BPRIO(pCurThread);
	if (pCurThread->pOwnedList && (prio > (prio2 = pCurThread->pOwnedList->bListedPrio)))
		prio = prio2;
	if (prio != GET_CPRIO(pCurThread)) {
		SET_CPRIO(pCurThread,prio);
		CELOG_SystemInvert(pCurThread->hTh, prio);
      if (RunList.pRunnable && (prio > GET_CPRIO(RunList.pRunnable)))
			SetReschedule();
	}
	KCALLPROFOFF(52);
}

void ReprioCritMut(LPCRIT lpcrit, PTHREAD pth) {
	BYTE prio;
	if (lpcrit->bListed == 1) {
		UnlinkCritMut(lpcrit,pth);
		prio = lpcrit->bListedPrio = (lpcrit->pProxList ? lpcrit->pProxList->prio : MAX_PRIORITY_LEVELS-1);
		DoLinkCritMut(lpcrit,pth,prio);
	}
}

void RunqDequeue(PTHREAD pth, DWORD prio) {
	PTHREAD pDown, pNext;
	prio = prio/PRIORITY_LEVELS_HASHSCALE;
	pDown = pth->pDownRun;
	pNext = pth->pNextSleepRun;
	if (RunList.pHashThread[prio] == pth) {
		RunList.pHashThread[prio] = ((pDown != pth) ? pDown :
			(pNext && (GET_CPRIO(pNext)/PRIORITY_LEVELS_HASHSCALE == (WORD)prio)) ? pNext : 0);
	}
	if (pDown == pth) {
		if (!pth->pPrevSleepRun) {
			DEBUGCHK(RunList.pRunnable == pth);
			if (RunList.pRunnable = pNext)
				pNext->pPrevSleepRun = 0;
		} else {
			if (pth->pPrevSleepRun->pNextSleepRun = pNext)
				pNext->pPrevSleepRun = pth->pPrevSleepRun;
		}
	} else {
		pDown->pUpRun = pth->pUpRun;
		pth->pUpRun->pDownRun = pDown;
		if (pth->pPrevSleepRun) {
			pth->pPrevSleepRun->pNextSleepRun = pDown;
			pDown->pPrevSleepRun = pth->pPrevSleepRun;
			goto FinishDequeue;
		} else if (pth == RunList.pRunnable) {
			RunList.pRunnable = pDown;
			DEBUGCHK(!pDown->pPrevSleepRun);
FinishDequeue:			
			if (pNext) {
				pNext->pPrevSleepRun = pDown;
				pDown->pNextSleepRun = pNext;
			}