This is the mail archive of the ecos-discuss@sources.redhat.com mailing list for the eCos project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Is this a bug


TomChen <chenqy_79@163.com> writes:

> Nick Garnett wrote:
> 
> >TomChen <chenqy_79@163.com> writes:
> >
> >
> >>Hi All,
> >>
> >>Kernel package src/sched/mlqueue.cxx
> >>in function Cyg_ThreadQueue_Implementation::enqueue(Cyg_Thread *thread) ,
> >>
> >>When there is more than one thread in the queue and the priority is
> >>neither higer than the head nor lower than the tail, we have to search
> >>the queue to find the place. The code for this is:
> >>
> >>Cyg_Thread *qtmp = get_tail();
> >>while ( thread->priority > qtmp->priority)
> >>    qtmp = qtmp->get_prev();
> >>qtmp->append( thread );
> >>
> >>I think this should be:
> >>
> >>Cyg_Thread *qtmp = get_tail();
> >>while ( thread->priority *<* qtmp->priority)
> >>    qtmp = qtmp->get_prev();
> >>qtmp->append( thread );
> >>
> >
> >I believe the original code it correct.
> >
> >Remember that the priorities go from 0=highest to 31=lowest. So the
> >loop spins while the thread priorities are numerically greater than
> >the one we want to insert. Once we find one that is less than or equal
> >we break out and install the new thread just after it.
> >
> >
> Consider such a scenario, we enqueue three threads with priority 3, 5,
> 4 respectively into an empty queue in the order as shown. According to
> the originall code, we will get the result:
> 
>                                       ------next----->
> ------next----->       ------next----->  T3
>                                   T3                            T5
> T4
>    T4 <-----prev-----      <-----prev-----         <-----prev------
>                                    |
> |
>                                 head
> tail
> 
> Now, when we try get_tail() to get the tail who has the lower pirority
> then the thread with priority 4 will be returned.
> 
> In the queue the head has higher priority (numerically less) and the
> tail has lower priority (numerically greater). In the code, the search
> begins from the tail , here the condition thread->priority >
> qtmp->priority will never be true since before the loop we have checked
> 
>         if( thread->priority > get_tail()->priority )
>         {
>             // We are lower priority than any thread in the queue,
>             // go in at the end.
>             add_tail( thread );
>         }
> So, I think this is a bug.

Yes. I think you are right. It took a while and a couple of diagrams to
convince myself, though. Good catch, that bug has probably been there
for several years.

I'll check in a fix.

We haven't been bitten by this in the past because we seldom enable
sorted queues, few thread queues ever have more than two threads on
them, and few programs depend on the order of threads in these lists
anyway.

-- 
Nick Garnett                    eCos Kernel Architect
http://www.ecoscentric.com/     The eCos and RedBoot experts


-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]