//----------------------------------------------------------------------------// // OS on Kaleid // // // // Desc: Process scheduler // // // // // // Copyright © 2018-2021 The OS/K Team // // // // This file is part of OS/K. // // // // OS/K is free software: you can redistribute it and/or modify // // it under the terms of the GNU General Public License as published by // // the Free Software Foundation, either version 3 of the License, or // // any later version. // // // // OS/K is distributed in the hope that it will be useful, // // but WITHOUT ANY WARRANTY//without even the implied warranty of // // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // // GNU General Public License for more details. // // // // You should have received a copy of the GNU General Public License // // along with OS/K. If not, see . // //----------------------------------------------------------------------------// #include #include #include #include #include bool PsInitialized = false; // // For test purpose only // int procslen = 10; Process_t procs[] = { { {0}, 0, 0, 0, 12, 12, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 1, 2, 2, 16, 16, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 2, 3, 3, 31, 31, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 3, 2, 2, 1, 1, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 4, 3, 3, 5, 5, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 5, 0, 0, 12, 12, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 6, 1, 1, 19, 19, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 7, 1, 1, 0, 0, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 8, 3, 3, 12, 12, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, { {0}, 9, 2, 2, 21, 21, STATE_RUNNABLE, DEF_PROC_TSLICE, DEF_PROC_TSLICE }, }; //------------------------------------------// #define ReSchedFlag (KeCurCPU->needReSched) #define PreemptCount (KeCurCPU->preemptCount) #define IdlePrioProcs (KeCurCPU->idlePrioProcs) #define ReglPrioProcs (KeCurCPU->reglPrioProcs) #define ServPrioProcs (KeCurCPU->servPrioProcs) #define TimeCritProcs (KeCurCPU->timeCritProcs) //------------------------------------------// // // Set current process // static void SetCurProc(Process_t *proc) { KeCurProc = proc; if (KeCurProc) KeCurProc->procState = STATE_RUNNING; } // // (Un)Lock priority class list heads // static inline void PsLockSched(void) { KeDisableIRQs(); } static inline void PsUnlockSched(void) { KeEnableIRQs(); } // // The four priority classes of OS/2 // const char *PsPrioClassesNames[] = { "Time-critical class", "Server priority class", "Regular priority class", "Idle priority class", }; // // Get priority class list head // static ListHead_t *GetPrioClassHead(int prioClass) { switch (prioClass) { case TIME_CRIT_PROC: return TimeCritProcs; case SERV_PRIO_PROC: return ServPrioProcs; case REGL_PRIO_PROC: return ReglPrioProcs; case IDLE_PRIO_PROC: return IdlePrioProcs; default: assert(!"Unknown priority class"); } return NULL; } // // Determine which process is going to run first // Return NULL for "equal" processes // static Process_t *CompareProcs(Process_t *proc1, Process_t *proc2) { assert(proc1 && proc2); if (proc1->prioClass < proc2->prioClass) return proc1; if (proc1->prioClass > proc2->prioClass) return proc2; if (proc1->prioLevel > proc2->prioLevel) return proc1; if (proc1->prioLevel < proc2->prioLevel) return proc2; return NULL; // same class and level } // // Add process to schedule lists (unlocked) // static void SchedThisProcUnlocked(Process_t *proc) { assert(proc && proc->procState == STATE_RUNNABLE); bool found = 0; ListNode_t *iterNode = NULL; ListHead_t *head = GetPrioClassHead(proc->prioClass); assert(head); // Find a process with lesser priority for (iterNode = head->first; iterNode; iterNode = iterNode->next) { if (proc->prioLevel > ExGetNodeData(iterNode, Process_t *)->prioLevel) { // Detect double insertions assert(proc->pid != ExGetNodeData(iterNode, Process_t *)->pid); // Add process to schedule ExAddNodeBefore(head, iterNode, &proc->schedNode); found = true; break; } } // Didn't find any process with lesser priority if (found == false) { ExAppendNode(head, &proc->schedNode); } } // // Add process to schedule lists // void PsSchedThisProc(Process_t *proc) { PsLockSched(); SchedThisProcUnlocked(proc); PsUnlockSched(); } // // Selects process to schedule next // static Process_t *SelectSchedNext(void) { if (TimeCritProcs->length > 0) return ExGetNodeData(TimeCritProcs->first, Process_t *); if (ServPrioProcs->length > 0) return ExGetNodeData(ServPrioProcs->first, Process_t *); if (ReglPrioProcs->length > 0) return ExGetNodeData(ReglPrioProcs->first, Process_t *); if (IdlePrioProcs->length > 0) return ExGetNodeData(IdlePrioProcs->first, Process_t *); return NULL; } // // Remove running process from schedule lists // and schedule next runnable process // void PsBlockCurProc(void) { assert(KeCurProc && KeCurProc->procState == STATE_RUNNING); KeCurProc->procState = STATE_BLOCKED; ExRemoveNode(KeCurProc->schedNode.head, &KeCurProc->schedNode); SetCurProc(SelectSchedNext()); } static void ReSchedCurProc(void) { assert(KeCurProc && KeCurProc->procState == STATE_RUNNING); // Restore default attributes, cancelling boosts KeCurProc->prioClass = KeCurProc->defPrioClass; KeCurProc->prioLevel = KeCurProc->defPrioLevel; KeCurProc->timeSlice = KeCurProc->defTimeSlice; KeCurProc->procState = STATE_RUNNABLE; // Remove from list ExRemoveNode(KeCurProc->schedNode.head, &KeCurProc->schedNode); // Schedule again, with default attributes now SchedThisProcUnlocked(KeCurProc); } // // Should we schedule another process? // Called at each tick // void PsSchedOnTick(void) { PsLockSched(); Process_t *procNext, *winner, *previous = KeCurProc; // We're either idle or running something assert(KeCurProc == NULL || KeCurProc->procState == STATE_RUNNING); // Has the current process spent its timeslice? // (To be handled in CPU decisions function) if (KeCurProc != NULL) { if (KeCurProc->timeSlice <= 1) { // Re-schedule ReSchedCurProc(); // See next 'if' statement KeCurProc = NULL; } // Otherwise, make it lose a tick else { KeCurProc->timeSlice--; } } // Are we idle, or scheduling next process? if (KeCurProc == NULL) { SetCurProc(SelectSchedNext()); goto leave; } // Is preemption on and a re-schedule is needed? if (PreemptCount == PREEMPT_ON && ReSchedFlag) { // Is there a higher priority process that is runnable? procNext = SelectSchedNext(); winner = CompareProcs(KeCurProc, procNext); // Yes, procNext should preempt current process if (winner == procNext) { // Re-schedule ReSchedCurProc(); // Switch to procNext SetCurProc(procNext); } } // Current process won't be preempted and has time remaining leave: PsUnlockSched(); if (KeCurProc != NULL && KeCurProc != previous) { // dispatch & context switch } } // // Initialize scheduler // void PsInitSched(void) { int pid; PsLockSched(); TimeCritProcs = ExCreateListHead(); ServPrioProcs = ExCreateListHead(); ReglPrioProcs = ExCreateListHead(); IdlePrioProcs = ExCreateListHead(); assert(IdlePrioProcs && ReglPrioProcs && ServPrioProcs && TimeCritProcs); for (pid = 0; pid < procslen; pid++) { if (procs[pid].procState == STATE_RUNNABLE) { SchedThisProcUnlocked(&procs[pid]); } } PsUnlockSched(); PsInitialized = true; DebugLog("Scheduler initialized\n"); } #define PrintProc(proc) KernLog("{ %d, '%s', %d , %lu}\n", (proc)->pid, \ PsPrioClassesNames[(proc)->prioClass], (proc)->prioLevel, (proc)->timeSlice); // // Print out process list // void PrintList(ListHead_t *head) { assert(head); Process_t *proc; ListNode_t *node = head->first; KernLog("len %lu\n", head->length); while (node) { proc = ExGetNodeData(node, Process_t *); PrintProc(proc); node = node->next; } KernLog(""); } void pstest(void) { KernLog("\nTime Critical: "); PrintList(TimeCritProcs); KernLog("\nServer: "); PrintList(ServPrioProcs); KernLog("\nRegular: "); PrintList(ReglPrioProcs); KernLog("\nIdle: "); PrintList(IdlePrioProcs); KernLog("\n"); KernLog("Tick %d - Running: ", KeGetTicks()); if (KeCurProc == NULL) { KernLog("IDLE\n"); } else { PrintProc(KeCurProc); } }