X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=Kernel%2Fthreads.c;h=b76fe592f220901f9f749b102a538bfc205fb300;hb=314eeb0078d801ddc34718603cad4fa690392496;hp=9fd052b66f914107b91c680552f2100b2daec837;hpb=3b0cee8ca739fc5c564c78467fdc65c4d83d45a1;p=tpg%2Facess2.git diff --git a/Kernel/threads.c b/Kernel/threads.c index 9fd052b6..b76fe592 100644 --- a/Kernel/threads.c +++ b/Kernel/threads.c @@ -7,13 +7,22 @@ #include #include +// Configuration #define DEBUG_TRACE_TICKETS 0 // Trace ticket counts #define DEBUG_TRACE_STATE 0 // Trace state changes (sleep/wake) +// --- Schedulers --- +#define SCHED_UNDEF 0 +#define SCHED_LOTTERY 1 // Lottery scheduler +#define SCHED_RR_SIM 2 // Single Queue Round Robin +#define SCHED_RR_PRI 3 // Multi Queue Round Robin +// Set scheduler type +#define SCHEDULER_TYPE SCHED_LOTTERY + // === CONSTANTS === #define DEFAULT_QUANTUM 10 -#define DEFAULT_TICKETS 5 -#define MAX_TICKETS 10 +#define DEFAULT_PRIORITY 5 +#define MIN_PRIORITY 10 const enum eConfigTypes cCONFIG_TYPES[] = { CFGT_HEAPSTR, // e.g. CFG_VFS_CWD CFGT_INT, // e.g. CFG_VFS_MAXFILES @@ -31,12 +40,12 @@ extern void Proc_CallFaultHandler(tThread *Thread); void Threads_Init(void); int Threads_SetName(char *NewName); char *Threads_GetName(int ID); -void Threads_SetTickets(tThread *Thread, int Num); +void Threads_SetPriority(tThread *Thread, int Pri); tThread *Threads_CloneTCB(Uint *Err, Uint Flags); int Threads_WaitTID(int TID, int *status); tThread *Threads_GetThread(Uint TID); void Threads_AddToDelete(tThread *Thread); -tThread *Threads_int_GetPrev(tThread **List, tThread *Thread); +tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread); void Threads_Exit(int TID, int Status); void Threads_Kill(tThread *Thread, int Status); void Threads_Yield(void); @@ -51,6 +60,7 @@ tUID Threads_GetUID(void); tGID Threads_GetGID(void); int Threads_SetGID(Uint *Errno, tUID ID); void Threads_Dump(void); +void Threads_DumpActive(void); void Mutex_Acquire(tMutex *Mutex); void Mutex_Release(tMutex *Mutex); int Mutex_IsLocked(tMutex *Mutex); @@ -63,21 +73,32 @@ tThread gThreadZero = { ThreadName: "ThreadZero", // Name Quantum: DEFAULT_QUANTUM, // Default Quantum Remaining: DEFAULT_QUANTUM, // Current Quantum - NumTickets: DEFAULT_TICKETS // Number of tickets + Priority: DEFAULT_PRIORITY // Number of tickets }; // -- Processes -- // --- Locks --- tShortSpinlock glThreadListLock; ///\note NEVER use a heap function while locked // --- Current State --- -volatile int giNumActiveThreads = 0; -volatile int giFreeTickets = 0; -volatile Uint giNextTID = 1; +volatile int giNumActiveThreads = 0; // Number of threads on the active queue +volatile Uint giNextTID = 1; // Next TID to allocate // --- Thread Lists --- tThread *gAllThreads = NULL; // All allocated threads -tThread *gActiveThreads = NULL; // Currently Running Threads tThread *gSleepingThreads = NULL; // Sleeping Threads tThread *gDeleteThreads = NULL; // Threads to delete - int giNumCPUs = 1; + int giNumCPUs = 1; // Number of CPUs +BOOL gaThreads_NoTaskSwitch[MAX_CPUS]; // Disables task switches for each core (Pseudo-IF) +// --- Scheduler Types --- +#if SCHEDULER_TYPE == SCHED_LOTTERY +const int caiTICKET_COUNTS[MIN_PRIORITY+1] = {100,81,64,49,36,25,16,9,4,1,0}; +volatile int giFreeTickets = 0; // Number of tickets held by non-scheduled threads +tThread *gActiveThreads = NULL; // Currently Running Threads +#elif SCHEDULER_TYPE == SCHED_RR_SIM +tThread *gActiveThreads = NULL; // Currently Running Threads +#elif SCHEDULER_TYPE == SCHED_RR_PRI +tThread *gaActiveThreads[MIN_PRIORITY+1]; // Active threads for each priority level +#else +# error "Unkown scheduler type" +#endif // === CODE === /** @@ -89,9 +110,13 @@ void Threads_Init(void) ArchThreads_Init(); // Create Initial Task + #if SCHEDULER_TYPE == SCHED_RR_PRI + gaActiveThreads[gThreadZero.Priority] = &gThreadZero; + #else gActiveThreads = &gThreadZero; + #endif + gAllThreads = &gThreadZero; - //giFreeTickets = gThreadZero.NumTickets; giNumActiveThreads = 1; Proc_Start(); @@ -100,12 +125,17 @@ void Threads_Init(void) /** * \fn void Threads_SetName(char *NewName) * \brief Sets the current thread's name + * \param NewName New name for the thread + * \return Boolean Failure */ int Threads_SetName(char *NewName) { tThread *cur = Proc_GetCurThread(); char *oldname = cur->ThreadName; + // NOTE: There is a possibility of non-thread safety here + // A thread could read the current name pointer before it is zeroed + cur->ThreadName = NULL; if( IsHeap(oldname) ) free( oldname ); @@ -117,39 +147,70 @@ int Threads_SetName(char *NewName) /** * \fn char *Threads_GetName(int ID) * \brief Gets a thread's name + * \param ID Thread ID (-1 indicates current thread) + * \return Pointer to name + * \retval NULL Failure */ -char *Threads_GetName(int ID) +char *Threads_GetName(tTID ID) { if(ID == -1) { return Proc_GetCurThread()->ThreadName; } - // TODO: Find a thread and get its name - return NULL; + return Threads_GetThread(ID)->ThreadName; } /** - * \fn void Threads_SetTickets(tThread *Thread, int Num) - * \brief Sets the 'priority' of a task + * \fn void Threads_SetPriority(tThread *Thread, int Pri) + * \brief Sets the priority of a task + * \param Thread Thread to update ticket count (NULL means current thread) + * \param Pri New priority */ -void Threads_SetTickets(tThread *Thread, int Num) +void Threads_SetPriority(tThread *Thread, int Pri) { - if(Thread == NULL) - Thread = Proc_GetCurThread(); - if(Num < 0) return; - if(Num > MAX_TICKETS) Num = MAX_TICKETS; + // Get current thread + if(Thread == NULL) Thread = Proc_GetCurThread(); + // Bounds checking + // - If < 0, set to lowest priority + if(Pri < 0) Pri = MIN_PRIORITY; + if(Pri > MIN_PRIORITY) Pri = MIN_PRIORITY; + + // Do we actually have to do anything? + if( Pri == Thread->Priority ) return; - if( Thread != Proc_GetCurThread() ) { + #if SCHEDULER_TYPE == SCHED_RR_PRI + SHORTLOCK( &glThreadListLock ); + // Remove from old priority + Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread ); + // And add to new + Thread->Next = gaActiveThreads[Pri]; + gaActiveThreads[Pri] = Thread; + Thread->Priority = Pri; + SHORTREL( &glThreadListLock ); + #else + // If this isn't the current thread, we need to lock + if( Thread != Proc_GetCurThread() ) + { SHORTLOCK( &glThreadListLock ); - giFreeTickets -= Thread->NumTickets - Num; - Thread->NumTickets = Num; + + #if SCHEDULER_TYPE == SCHED_LOTTERY + giFreeTickets -= caiTICKET_COUNTS[Thread->Priority] - caiTICKET_COUNTS[Pri]; + # if DEBUG_TRACE_TICKETS + Log("Threads_SetTickets: new giFreeTickets = %i", giFreeTickets); + # endif + #endif + Thread->Priority = Pri; SHORTREL( &glThreadListLock ); } else - Thread->NumTickets = Num; + Thread->Priority = Pri; + #endif } /** * \fn tThread *Threads_CloneTCB(Uint *Err, Uint Flags) + * \brief Clone the TCB of the current thread + * \param Err Error pointer + * \param Flags Flags for something... (What is this for?) */ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) { @@ -157,6 +218,7 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) int i; cur = Proc_GetCurThread(); + // Allocate and duplicate new = malloc(sizeof(tThread)); if(new == NULL) { *Err = -ENOMEM; @@ -167,7 +229,7 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) new->CurCPU = -1; new->Next = NULL; memset( &new->IsLocked, 0, sizeof(new->IsLocked)); - new->Status = THREAD_STAT_ACTIVE; + new->Status = THREAD_STAT_PREINIT; new->RetStatus = 0; // Get Thread ID @@ -189,7 +251,7 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) // Set State new->Remaining = new->Quantum = cur->Quantum; - new->NumTickets = cur->NumTickets; + new->Priority = cur->Priority; // Set Signal Handlers new->CurFaultNum = 0; @@ -222,24 +284,27 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) } /** - * \fn Uint *Threads_GetCfgPtr(int Id) + * \brief Get a configuration pointer from the Per-Thread data area + * \param ID Config slot ID + * \return Pointer at ID */ -Uint *Threads_GetCfgPtr(int Id) +Uint *Threads_GetCfgPtr(int ID) { - if(Id < 0 || Id >= NUM_CFG_ENTRIES) { - Warning("Threads_GetCfgPtr: Index %i is out of bounds", Id); + if(ID < 0 || ID >= NUM_CFG_ENTRIES) { + Warning("Threads_GetCfgPtr: Index %i is out of bounds", ID); return NULL; } - return &Proc_GetCurThread()->Config[Id]; + return &Proc_GetCurThread()->Config[ID]; } /** - * \fn tTID Threads_WaitTID(int TID, int *status) * \brief Wait for a task to change state + * \param TID Thread ID to wait on (-1: Any child thread, 0: Any Child/Sibling, <-1: -PID) + * \param Status Thread return status * \return TID of child that changed state */ -int Threads_WaitTID(int TID, int *status) +tTID Threads_WaitTID(int TID, int *Status) { // Any Child if(TID == -1) { @@ -263,8 +328,9 @@ int Threads_WaitTID(int TID, int *status) if(TID > 0) { tThread *t = Threads_GetThread(TID); int initStatus = t->Status; - int ret; + tTID ret; + // Wait for the thread to die! if(initStatus != THREAD_STAT_ZOMBIE) { // TODO: Handle child also being suspended if wanted while(t->Status != THREAD_STAT_ZOMBIE) { @@ -274,21 +340,22 @@ int Threads_WaitTID(int TID, int *status) } } + // Set return status Log_Debug("Threads", "%i waiting for %i, t->Status = %i", Threads_GetTID(), t->TID, t->Status); - ret = t->RetStatus; + ret = t->TID; switch(t->Status) { case THREAD_STAT_ZOMBIE: // Kill the thread t->Status = THREAD_STAT_DEAD; // TODO: Child return value? - if(status) *status = 0; + if(Status) *Status = t->RetStatus; // add to delete queue Threads_AddToDelete( t ); break; default: - if(status) *status = -1; + if(Status) *Status = -1; break; } return ret; @@ -298,9 +365,9 @@ int Threads_WaitTID(int TID, int *status) } /** - * \fn tThread *Threads_GetThread(Uint TID) * \brief Gets a thread given its TID * \param TID Thread ID + * \return Thread pointer */ tThread *Threads_GetThread(Uint TID) { @@ -321,12 +388,13 @@ tThread *Threads_GetThread(Uint TID) } /** - * \fn void Threads_AddToDelete(tThread *Thread) * \brief Adds a thread to the delete queue + * \param Thread Thread to delete */ void Threads_AddToDelete(tThread *Thread) { // Add to delete queue + // TODO: Is locking needed? if(gDeleteThreads) { Thread->Next = gDeleteThreads; gDeleteThreads = Thread; @@ -337,31 +405,42 @@ void Threads_AddToDelete(tThread *Thread) } /** - * \fn tThread *Threads_int_GetPrev(tThread **List, tThread *Thread) - * \brief Gets the previous entry in a thead linked list + * \brief Deletes an entry from a list + * \param List Pointer to the list head + * \param Thread Thread to find + * \return \a Thread */ -tThread *Threads_int_GetPrev(tThread **List, tThread *Thread) +tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread) { - tThread *ret; - // First Entry - if(*List == Thread) { - return (tThread*)List; - } else { - for(ret = *List; - ret->Next && ret->Next != Thread; - ret = ret->Next - ); - // Error if the thread is not on the list - if(!ret->Next || ret->Next != Thread) { - return NULL; - } + tThread *ret, *prev = NULL; + + for(ret = *List; + ret && ret != Thread; + prev = ret, ret = ret->Next + ); + + // Is the thread on the list + if(!ret) { + //LogF("%p(%s) is not on list %p\n", Thread, Thread->ThreadName, List); + return NULL; } - return ret; + + if( !prev ) { + *List = Thread->Next; + //LogF("%p(%s) removed from head of %p\n", Thread, Thread->ThreadName, List); + } + else { + prev->Next = Thread->Next; + //LogF("%p(%s) removed from %p (prev=%p)\n", Thread, Thread->ThreadName, List, prev); + } + + return Thread; } /** - * \fn void Threads_Exit(int TID, int Status) - * \brief Exit the current process + * \brief Exit the current process (or another?) + * \param TID Thread ID to kill + * \param Status Exit status */ void Threads_Exit(int TID, int Status) { @@ -369,9 +448,9 @@ void Threads_Exit(int TID, int Status) Threads_Kill( Proc_GetCurThread(), (Uint)Status & 0xFF ); else Threads_Kill( Threads_GetThread(TID), (Uint)Status & 0xFF ); + // Halt forever, just in case - for(;;) - HALT(); + for(;;) HALT(); } /** @@ -382,13 +461,13 @@ void Threads_Exit(int TID, int Status) */ void Threads_Kill(tThread *Thread, int Status) { - tThread *prev; tMsg *msg; - // Kill all children + // TODO: Kill all children #if 0 { tThread *child; + // TODO: I should keep a .Parent pointer, and a .Children list for(child = gActiveThreads; child; child = child->Next) @@ -404,18 +483,6 @@ void Threads_Kill(tThread *Thread, int Status) // Lock thread (stop us recieving messages) SHORTLOCK( &Thread->IsLocked ); - // Lock thread list - SHORTLOCK( &glThreadListLock ); - - // Get previous thread on list - prev = Threads_int_GetPrev( &gActiveThreads, Thread ); - if(!prev) { - Warning("Proc_Exit - Current thread is not on the active queue"); - SHORTREL( &Thread->IsLocked ); - SHORTREL( &glThreadListLock ); - return; - } - // Clear Message Queue while( Thread->Messages ) { @@ -424,18 +491,37 @@ void Threads_Kill(tThread *Thread, int Status) Thread->Messages = msg; } + // Lock thread list + SHORTLOCK( &glThreadListLock ); + + // Delete from active list + #if SCHEDULER_TYPE == SCHED_RR_PRI + if( !Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread ) ) + #else + if( !Threads_int_DelFromQueue( &gActiveThreads, Thread ) ) + #endif + { + Warning("Proc_Exit - Current thread is not on the active queue"); + SHORTREL( &glThreadListLock ); + SHORTREL( &Thread->IsLocked ); + return; + } + + // Ensure that we are not rescheduled Thread->Remaining = 0; // Clear Remaining Quantum Thread->Quantum = 0; // Clear Quantum to indicate dead thread - prev->Next = Thread->Next; // Remove from active + // Update bookkeeping giNumActiveThreads --; + #if SCHEDULER_TYPE == SCHED_LOTTERY if( Thread != Proc_GetCurThread() ) - giFreeTickets -= Thread->NumTickets; + giFreeTickets -= caiTICKET_COUNTS[ Thread->Priority ]; + #endif // Save exit status Thread->RetStatus = Status; - // Don't Zombie if we are being killed as part of a tree + // Don't Zombie if we are being killed because our parent is if(Status == -1) { Thread->Status = THREAD_STAT_DEAD; @@ -449,20 +535,25 @@ void Threads_Kill(tThread *Thread, int Status) Log("Thread %i went *hurk* (%i)", Thread->TID, Thread->Status); // Release spinlocks - SHORTREL( &Thread->IsLocked ); SHORTREL( &glThreadListLock ); + SHORTREL( &Thread->IsLocked ); // TODO: We may not actually be released... - if(Status != -1) HALT(); + // And, reschedule + if(Status != -1) { + for( ;; ) + HALT(); + } } /** - * \fn void Threads_Yield(void) - * \brief Yield remainder of timeslice + * \brief Yield remainder of the current thread's timeslice */ void Threads_Yield(void) { - Proc_GetCurThread()->Remaining = 0; - HALT(); + tThread *thread = Proc_GetCurThread(); + thread->Remaining = 0; + //while(thread->Remaining == 0) + HALT(); } /** @@ -473,8 +564,6 @@ void Threads_Sleep(void) { tThread *cur = Proc_GetCurThread(); - //Log_Log("Threads", "%i going to sleep", cur->TID); - // Acquire Spinlock SHORTLOCK( &glThreadListLock ); @@ -486,13 +575,13 @@ void Threads_Sleep(void) // Remove us from running queue Threads_RemActive(); + // Mark thread as sleeping + cur->Status = THREAD_STAT_SLEEPING; // Add to Sleeping List (at the top) cur->Next = gSleepingThreads; gSleepingThreads = cur; - // Mark thread as sleeping - cur->Status = THREAD_STAT_SLEEPING; #if DEBUG_TRACE_STATE Log("Threads_Sleep: %p (%i %s) sleeping", cur, cur->TID, cur->ThreadName); @@ -510,12 +599,10 @@ void Threads_Sleep(void) * \brief Wakes a sleeping/waiting thread up * \param Thread Thread to wake * \return Boolean Failure (Returns ERRNO) - * \note Should be called with the scheduler lock held + * \warning This should ONLY be called with task switches disabled */ int Threads_Wake(tThread *Thread) { - tThread *prev; - if(!Thread) return -EINVAL; @@ -525,24 +612,17 @@ int Threads_Wake(tThread *Thread) Log("Thread_Wake: Waking awake thread (%i)", Thread->TID); return -EALREADY; - case THREAD_STAT_SLEEPING: // TODO: Comment better + case THREAD_STAT_SLEEPING: + SHORTLOCK( &glThreadListLock ); // Remove from sleeping queue - prev = Threads_int_GetPrev(&gSleepingThreads, Thread); - prev->Next = Thread->Next; - // Add to active queue - Thread->Next = gActiveThreads; - gActiveThreads = Thread; - // Update bookkeeping - giNumActiveThreads ++; - giFreeTickets += Thread->NumTickets; - #if DEBUG_TRACE_TICKETS - Log("Threads_Wake: new giFreeTickets = %i", giFreeTickets); - #endif - Thread->CurCPU = -1; - Thread->Status = THREAD_STAT_ACTIVE; + Threads_int_DelFromQueue(&gSleepingThreads, Thread); + + Threads_AddActive( Thread ); + #if DEBUG_TRACE_STATE Log("Threads_Sleep: %p (%i %s) woken", Thread, Thread->TID, Thread->ThreadName); #endif + SHORTREL( &glThreadListLock ); return -EOK; case THREAD_STAT_WAITING: @@ -570,28 +650,41 @@ int Threads_WakeTID(tTID TID) int ret; if(!thread) return -ENOENT; - SHORTLOCK( &glThreadListLock ); ret = Threads_Wake( thread ); - SHORTREL( &glThreadListLock ); + //Log_Debug("Threads", "TID %i woke %i (%p)", Threads_GetTID(), TID, thread); return ret; } /** - * \fn void Threads_AddActive(tThread *Thread) * \brief Adds a thread to the active queue */ void Threads_AddActive(tThread *Thread) { SHORTLOCK( &glThreadListLock ); + + // Set state + Thread->Status = THREAD_STAT_ACTIVE; + Thread->CurCPU = -1; // Add to active list + #if SCHEDULER_TYPE == SCHED_RR_PRI + Thread->Next = gaActiveThreads[Thread->Priority]; + gaActiveThreads[Thread->Priority] = Thread; + #else Thread->Next = gActiveThreads; gActiveThreads = Thread; + #endif + // Update bookkeeping giNumActiveThreads ++; - giFreeTickets += Thread->NumTickets; - #if DEBUG_TRACE_TICKETS - Log("Threads_AddActive: new giFreeTickets = %i", giFreeTickets); + + #if SCHEDULER_TYPE == SCHED_LOTTERY + giFreeTickets += caiTICKET_COUNTS[ Thread->Priority ]; + # if DEBUG_TRACE_TICKETS + Log("Threads_AddActive: %p %i (%s) added, new giFreeTickets = %i", + Thread, Thread->TID, Thread->ThreadName, giFreeTickets); + # endif #endif + SHORTREL( &glThreadListLock ); } @@ -603,12 +696,34 @@ void Threads_AddActive(tThread *Thread) tThread *Threads_RemActive(void) { tThread *ret = Proc_GetCurThread(); - tThread *prev = Threads_int_GetPrev(&gActiveThreads, ret); - if(!prev) return NULL; + + SHORTLOCK( &glThreadListLock ); + + // Delete from active queue + #if SCHEDULER_TYPE == SCHED_RR_PRI + if( !Threads_int_DelFromQueue(&gaActiveThreads[ret->Priority], ret) ) + #else + if( !Threads_int_DelFromQueue(&gActiveThreads, ret) ) + #endif + { + SHORTREL( &glThreadListLock ); + return NULL; + } + + ret->Next = NULL; ret->Remaining = 0; ret->CurCPU = -1; - prev->Next = ret->Next; + giNumActiveThreads --; + // no need to decrement tickets, scheduler did it for us + + #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS + Log("Threads_RemActive: %p %i (%s) removed, giFreeTickets = %i", + ret, ret->TID, ret->ThreadName, giFreeTickets); + #endif + + SHORTREL( &glThreadListLock ); + return ret; } @@ -703,35 +818,70 @@ int Threads_SetGID(Uint *Errno, tGID ID) /** * \fn void Threads_Dump(void) - * \brief Dums a list of currently running threads */ -void Threads_Dump(void) +void Threads_DumpActive(void) { tThread *thread; + #if SCHEDULER_TYPE == SCHED_RR_PRI + int i; + #endif + + Log("Active Threads: (%i reported)", giNumActiveThreads); - Log("Active Threads:"); - for(thread=gActiveThreads;thread;thread=thread->Next) + #if SCHEDULER_TYPE == SCHED_RR_PRI + for( i = 0; i < MIN_PRIORITY+1; i++ ) { - Log(" %i (%i) - %s (CPU %i)", - thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); - Log(" State: %i", thread->Status); - Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum); - Log(" KStack 0x%x", thread->KernelStack); + for(thread=gaActiveThreads[i];thread;thread=thread->Next) + #else + for(thread=gActiveThreads;thread;thread=thread->Next) + #endif + { + Log(" %i (%i) - %s (CPU %i)", + thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); + if(thread->Status != THREAD_STAT_ACTIVE) + Log(" ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE); + Log(" Priority %i, Quantum %i", thread->Priority, thread->Quantum); + Log(" KStack 0x%x", thread->KernelStack); + } + + #if SCHEDULER_TYPE == SCHED_RR_PRI } + #endif +} + +/** + * \fn void Threads_Dump(void) + * \brief Dumps a list of currently running threads + */ +void Threads_Dump(void) +{ + tThread *thread; + + Log("--- Thread Dump ---"); + Threads_DumpActive(); Log("All Threads:"); for(thread=gAllThreads;thread;thread=thread->GlobalNext) { Log(" %i (%i) - %s (CPU %i)", thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); - Log(" State: %i", thread->Status); - Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum); + Log(" State %i (%s)", thread->Status, casTHREAD_STAT[thread->Status]); + switch(thread->Status) + { + case THREAD_STAT_MUTEXSLEEP: + Log(" Mutex Pointer: %p", thread->WaitPointer); + break; + case THREAD_STAT_ZOMBIE: + Log(" Return Status: %i", thread->RetStatus); + break; + default: break; + } + Log(" Priority %i, Quantum %i", thread->Priority, thread->Quantum); Log(" KStack 0x%x", thread->KernelStack); } } /** - * \fn tThread *Threads_GetNextToRun(int CPU, tThread *Last) * \brief Gets the next thread to run * \param CPU Current CPU * \param Last The thread the CPU was running @@ -739,19 +889,27 @@ void Threads_Dump(void) tThread *Threads_GetNextToRun(int CPU, tThread *Last) { tThread *thread; - int ticket; - int number; + // If this CPU has the lock, we must let it complete + if( CPU_HAS_LOCK( &glThreadListLock ) ) + return Last; + + // Don't change threads if the current CPU has switches disabled + if( gaThreads_NoTaskSwitch[CPU] ) + return Last; + + // Lock thread list SHORTLOCK( &glThreadListLock ); // Clear Delete Queue + // - I should probably put this in a worker thread to avoid calling free() in the scheduler while(gDeleteThreads) { thread = gDeleteThreads->Next; if( IS_LOCKED(&gDeleteThreads->IsLocked) ) { // Only free if structure is unused // Set to dead - gDeleteThreads->Status = THREAD_STAT_DEAD; + gDeleteThreads->Status = THREAD_STAT_BURIED; // Free name if( IsHeap(gDeleteThreads->ThreadName) ) free(gDeleteThreads->ThreadName); @@ -774,85 +932,166 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) return NULL; } + #if SCHEDULER_TYPE != SCHED_RR_PRI // Special case: 1 thread if(giNumActiveThreads == 1) { if( gActiveThreads->CurCPU == -1 ) gActiveThreads->CurCPU = CPU; + SHORTREL( &glThreadListLock ); + if( gActiveThreads->CurCPU == CPU ) return gActiveThreads; + return NULL; // CPU has nothing to do } + #endif // Allow the old thread to be scheduled again if( Last ) { if( Last->Status == THREAD_STAT_ACTIVE ) { - giFreeTickets += Last->NumTickets; - #if DEBUG_TRACE_TICKETS + #if SCHEDULER_TYPE == SCHED_LOTTERY + giFreeTickets += caiTICKET_COUNTS[ Last->Priority ]; + # if DEBUG_TRACE_TICKETS LogF(" CPU %i released %p (%i %s) into the pool (%i tickets in pool)\n", CPU, Last, Last->TID, Last->ThreadName, giFreeTickets); + # endif #endif } - #if DEBUG_TRACE_TICKETS + #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS else - LogF(" %p (%s)->Status = %i\n", Last, Last->ThreadName, Last->Status); + LogF(" CPU %i released %p (%i %s)->Status = %i (Released)\n", + CPU, Last, Last->TID, Last->ThreadName, Last->Status); #endif Last->CurCPU = -1; } - #if 1 - number = 0; - for(thread=gActiveThreads;thread;thread=thread->Next) { - if(thread->CurCPU >= 0) continue; - number += thread->NumTickets; - } - if(number != giFreeTickets) { - Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i", - giFreeTickets, number, CPU); - } - #endif - - // No free tickets (all tasks delegated to cores) - if( giFreeTickets == 0 ) { - SHORTREL(&glThreadListLock); - return NULL; + // --- + // Lottery Scheduler + // --- + #if SCHEDULER_TYPE == SCHED_LOTTERY + { + int ticket, number; + # if 1 + number = 0; + for(thread = gActiveThreads; thread; thread = thread->Next) { + if(thread->CurCPU >= 0) continue; + if(thread->Status != THREAD_STAT_ACTIVE) + Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i", + thread, thread->TID, thread->ThreadName, thread->Status); + if(thread->Next == thread) { + Panic("Bookkeeping fail - %p %i(%s) loops back on itself", + thread, thread->TID, thread->ThreadName, thread->Status); + } + number += caiTICKET_COUNTS[ thread->Priority ]; + } + if(number != giFreeTickets) { + Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i", + giFreeTickets, number, CPU); + } + # endif + + // No free tickets (all tasks delegated to cores) + if( giFreeTickets == 0 ) { + SHORTREL(&glThreadListLock); + return NULL; + } + + // Get the ticket number + ticket = number = rand() % giFreeTickets; + + // Find the next thread + for(thread=gActiveThreads;thread;thread=thread->Next) + { + if(thread->CurCPU >= 0) continue; + if( caiTICKET_COUNTS[ thread->Priority ] > number) break; + number -= caiTICKET_COUNTS[ thread->Priority ]; + } + + // If we didn't find a thread, something went wrong + if(thread == NULL) + { + number = 0; + for(thread=gActiveThreads;thread;thread=thread->Next) { + if(thread->CurCPU >= 0) continue; + number += caiTICKET_COUNTS[ thread->Priority ]; + } + Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)", + giFreeTickets, number); + } + # if DEBUG_TRACE_TICKETS + LogF(" CPU%i giFreeTickets = %i, running %p (%i %s CPU=%i)\n", + CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU); + # endif + + giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ]; } - // Get the ticket number - ticket = number = rand() % giFreeTickets; - - // Find the next thread - for(thread=gActiveThreads;thread;thread=thread->Next) + // --- + // Priority based round robin scheduler + // --- + #elif SCHEDULER_TYPE == SCHED_RR_PRI { - if(thread->CurCPU >= 0) continue; - if(thread->NumTickets > number) break; - number -= thread->NumTickets; + int i; + for( i = 0; i < MIN_PRIORITY + 1; i ++ ) + { + for(thread = gaActiveThreads[i]; thread; thread = thread->Next) + { + if( thread->CurCPU == -1 ) break; + } + // If we fall onto the same queue again, special handling is + // needed + if( i == Last->Priority ) { + tThread *savedThread = thread; + + // Find the next unscheduled thread in the list + for( thread = Last->Next; thread; thread = thread->Next ) + { + if( thread->CurCPU == -1 ) break; + } + // If we don't find anything after, just use the one + // found above. + if( !thread ) thread = savedThread; + } + // Found a thread? Schedule it! + if( thread ) break; + } + + // Anything to do? + if( !thread ) { + SHORTREL(&glThreadListLock); + return NULL; + } } - // Error Check - if(thread == NULL) - { - number = 0; - for(thread=gActiveThreads;thread;thread=thread->Next) { - if(thread->CurCPU >= 0) continue; - number += thread->NumTickets; + #elif SCHEDULER_TYPE == SCHED_RR_SIM + { + // Find the next unscheduled thread in the list + for( thread = Last->Next; thread; thread = thread->Next ) + { + if( thread->CurCPU == -1 ) break; + } + // If we don't find anything after, search from the beginning + if( !thread ) + { + for(thread = gActiveThreads; thread; thread = thread->Next) + { + if( thread->CurCPU == -1 ) break; + } + } + + // Anything to do? + if( !thread ) { + SHORTREL(&glThreadListLock); + return NULL; } - Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)", - giFreeTickets, number); } - #if DEBUG_TRACE_TICKETS - LogF(" CPU%i giFreeTickets = %i\n", CPU, giFreeTickets); + #else + # error "Unimplemented scheduling algorithm" #endif // Make the new thread non-schedulable - giFreeTickets -= thread->NumTickets; thread->CurCPU = CPU; - //Threads_Dump(); - #if DEBUG_TRACE_TICKETS - LogF(" CPU%i giFreeTickets = %i, giving %p (%i %s CPU=%i)\n", - CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU); - #endif - SHORTREL( &glThreadListLock ); return thread; @@ -892,9 +1131,11 @@ void Mutex_Acquire(tMutex *Mutex) if( Mutex->Owner ) { SHORTLOCK( &glThreadListLock ); // - Remove from active list - Threads_RemActive(); + us = Threads_RemActive(); + us->Next = NULL; // - Mark as sleeping - us->Status = THREAD_STAT_OFFSLEEP; + us->Status = THREAD_STAT_MUTEXSLEEP; + us->WaitPointer = Mutex; // - Add to waiting if(Mutex->LastWaiting) { @@ -905,10 +1146,21 @@ void Mutex_Acquire(tMutex *Mutex) Mutex->Waiting = us; Mutex->LastWaiting = us; } + #if 0 + { + int i = 0; + tThread *t; + for( t = Mutex->Waiting; t; t = t->Next, i++ ) + Log("[%i] (tMutex)%p->Waiting[%i] = %p (%i %s)", us->TID, Mutex, i, + t, t->TID, t->ThreadName); + } + #endif + SHORTREL( &glThreadListLock ); SHORTREL( &Mutex->Protector ); - while(us->Status == THREAD_STAT_OFFSLEEP) HALT(); + while(us->Status == THREAD_STAT_MUTEXSLEEP) Threads_Yield(); // We're only woken when we get the lock + us->WaitPointer = NULL; } // Ooh, let's take it! else { @@ -928,10 +1180,18 @@ void Mutex_Release(tMutex *Mutex) if( Mutex->Waiting ) { Mutex->Owner = Mutex->Waiting; // Set owner Mutex->Waiting = Mutex->Waiting->Next; // Next! + // Reset ->LastWaiting to NULL if we have just removed the last waiting thread + // 2010-10-02 21:50 - Comemerating the death of the longest single + // blocker in the Acess2 history. REMEMBER TO + // FUCKING MAINTAIN YOUR FUCKING LISTS DIPWIT + if( Mutex->LastWaiting == Mutex->Owner ) + Mutex->LastWaiting = NULL; + // Wake new owner - Mutex->Owner->Status = THREAD_STAT_ACTIVE; - Threads_AddActive(Mutex->Owner); - //Log("Mutex %p Woke %p", Mutex, Mutex->Owner); + SHORTLOCK( &glThreadListLock ); + if( Mutex->Owner->Status != THREAD_STAT_ACTIVE ) + Threads_AddActive(Mutex->Owner); + SHORTREL( &glThreadListLock ); } else { Mutex->Owner = NULL; @@ -950,6 +1210,7 @@ int Mutex_IsLocked(tMutex *Mutex) // === EXPORTS === EXPORT(Threads_GetUID); +EXPORT(Threads_GetGID); EXPORT(Mutex_Acquire); EXPORT(Mutex_Release); EXPORT(Mutex_IsLocked);