OSDev.org

Posted: **Wed Jan 25, 2006 7:54 am**

EDIT: The problem is now fixed, and it turns out that it was nothing to do with the linked lists...

Hi, I am having a problem with the runqueues in my scheduler. I add one null thread to the runqueue, it runs once, and once only. I know it is a problem with the linked lists, but I can't see it anywhere. Here is the relevant code:

Code: Select all

void kTimer(tRegs *r)
{
#ifdef _DYKNL_SMP
    IDENTIFIER thiscpu = kaGetCurrentCPU();
#else
    IDENTIFIER thiscpu = 0;
#endif
    
    tTimerEvent *ev;
    tLinkedListHead *list;
    
    SMP(kaLockSpinlock(&gTimerLock));
    
    gSystemTime++;
    
    LIST_FOREACH_NOPTR(list, gTimerEvent)
    {
        ev = LIST_ENTRY(list, tTimerEvent, List);
        if(ev->Time <= gSystemTime)
            kDoEvent(ev->Event);
    };
    
    SMP(kaReleaseSpinlock(&gTimerLock));
    
    if(gCurrent[thiscpu]->Time)
        gCurrent[thiscpu]->Time--;

    if(gCurrent[thiscpu]->Time <= 0)
    {
        kQueueThread(gCurrent[thiscpu], SCHED_QPREMPT);
        kaDoSchedule(thiscpu);
    }
    else if(gCurrent[thiscpu]->Status > STATUS_RUNNING)
        kaDoSchedule(thiscpu);
};

tThread *kDoSchedule(IDENTIFIER thiscpu)
{
    tThread   *current,*previous;
    tLinkedListHead *list;
   tLong q;
 
    SMP(kaLockSpinlock(&gWaitQueueLock));
    
    LIST_FOREACH(list, &gWaitQueue)
    {
        current = LIST_ENTRY(list, tThread, Queue);
        
        //
        // Wake any threads which have an event pending
        //
        
        if(current->Event)
        {
            if(kGetEvent(current->Event) != NULL)
            {
                current->Status = STATUS_ACTIVE;
                current->Event = NULL;
                // Maintain integrity of 'list'
                list = list->Previous;
                LIST_REM(list->Next);
                kQueueThread(current, SCHED_QWAIT);
            };
        };
    };
    
    SMP(kaReleaseSpinlock(&gWaitQueueLock));
    
    //
    // Now find a thread to run
    //
    
    for(q=0;q<THREAD_QUEUES;q++)
   {
        SMP(kaLockSpinlock(&(gQueueLock[q])));
        
        LIST_FOREACH(list, &(gQueue[q]))
      {
            current = LIST_ENTRY(list, tThread, Queue);
            
            if(current->Status == STATUS_ACTIVE)
         {
                //
                // This thread is active - prepare it for running
                //
                
                if((current->Parent != NULL) && (gCurrent[thiscpu]->Parent != current->Parent))
            {
               MemSwitchAddressSpace(current->Parent);
            };
                
            gCurrent[thiscpu] = current;
                current->Status = thiscpu;
                
                LIST_REM(list);
                
                // Calculate execution time
                current->Time = (PRIORITY_TIME(gCurrent[thiscpu]->Priority) +
                    PRIORITY_EXTRATIME(gCurrent[thiscpu]->Priority));
                
                SMP(kaReleaseSpinlock(&gQueueLock[q]));
                return gCurrent[thiscpu];
            };
      }
        SMP(kaReleaseSpinlock(&gQueueLock[q]));
   }
   
    kDie("kDoSchedule: no threads to run");
};

/*
 * Adds a thread to a runqueue
 * tThread *t   - thread to queue
 * tSignedLong f   - favorability 
 */
void    kQueueThread(tThread*   t, tSignedLong  f)
{
    tLinkedListHead *pos;
    tThread *qt;
    IDENTIFIER  q = t->LastQueue;
    
    t->Favorability = CALC_FAVOR(f, t->Priority, t->Time);
    
    //
    // Does the thread need to switch queues?
    //
    
    if((q < (THREAD_QUEUES - 1)) && (t->Favorability < SCHED_DEMOTE))
        q++;
    else if((q > 0) && (t->Favorability > SCHED_PROMOTE))
        q--;
    
    //
    // Calculate the thread's new position
    //
    
    kaAtomic(1);
    SMP(kaLockSpinlock(&gQueueLock[q]));
    
    
    LIST_FOREACH(pos, &(gQueue[q]))
    {
        qt = LIST_ENTRY(pos, tThread, Queue);
        if(qt->Favorability < t->Favorability)
            break;
    };

    t->Queue.Next = pos;
    t->Queue.Previous = pos->Previous;
    pos->Previous->Next = &(t->Queue);
    pos->Previous = &(t->Queue);
    
    SMP(kaReleaseSpinlock(&gQueueLock[q]));
    kaAtomic(0);
};

Linked list code:

Code: Select all

#define LIST_ENTRY(ptr, type, member) \
    ((type *)( (u8 *)(ptr) - (tAdr)(& (((type *)NULL)->member) ) ))

#define LIST_FOREACH(ptr, head) \
    for(ptr = (head)->Next; ptr != (head); ptr = ptr->Next)

#define LIST_FOREACH_NOPTR(ptr, head) \
    for(ptr = (head).Next; ptr != &(head); ptr = ptr->Next)

#define LIST_NULL(head)  ((head)->Next == (head))

#define LIST_ADD(ptr, pos) if(1){ \
    (pos)->Next->Previous = (ptr);    \
    (ptr)->Next = (pos)->Next;  \
    (ptr)->Previous = (pos);    \
    (pos)->Next = (ptr);    \
    }

#define LIST_REM(ptr)   if(1){  \
    (ptr)->Previous->Next = (ptr)->Next;    \
    (ptr)->Next->Previous = (ptr)->Previous;    \
    }

Thanks

OSDev.org

Scheduler linked list problem

Scheduler linked list problem