os-k/kaleid/kernel/ps/sched.c

//----------------------------------------------------------------------------//
//                                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 <https://www.gnu.org/licenses/>.            //
//----------------------------------------------------------------------------//

#include <asm.h>
#include <ke/proc.h>
#include <ke/sched.h>
#include <liblist.h>
#include <ke/time.h>

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");
}

//
// Shutdowns scheduler
//
void PsFiniSched(void)
{
    assert(IdlePrioProcs && ReglPrioProcs && ServPrioProcs && TimeCritProcs);

    PsInitialized = false;

    PsLockSched();

    while (IdlePrioProcs->length > 0)
        ExRemoveNode(IdlePrioProcs, IdlePrioProcs->first);

    while (ReglPrioProcs->length > 0)
        ExRemoveNode(ReglPrioProcs, ReglPrioProcs->first);

    while (ServPrioProcs->length > 0)
        ExRemoveNode(ServPrioProcs, ServPrioProcs->first);

    while (TimeCritProcs->length > 0)
        ExRemoveNode(TimeCritProcs, TimeCritProcs->first);

    ExDestroyListHead(IdlePrioProcs); IdlePrioProcs = NULL;
    ExDestroyListHead(ReglPrioProcs); ReglPrioProcs = NULL;
    ExDestroyListHead(ServPrioProcs); ServPrioProcs = NULL;
    ExDestroyListHead(TimeCritProcs); TimeCritProcs = NULL;

    PsUnlockSched();
}

#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);
    }
}