searchalgorithms.cpp

C语言库函数的原型,有用的拿去

    /// <summary>
    ///     Performs a fair search for unrealized chores in the specified ring.
    /// </summary>
    bool WorkSearchContext::SearchFair_Unrealized(WorkItem *pWorkItem, SchedulingRing *pRing)
    {
        int idx;
        ScheduleGroupBase *pGroup = pRing->GetPseudoRRScheduleGroup(&idx);

        int idxStart = idx;
        
        while (pGroup != NULL)
        {
            _UnrealizedChore *pUnrealizedChore = pGroup->StealUnrealizedChore();
            if (pUnrealizedChore != NULL)
            {
                pRing->SetPseudoRRScheduleGroupNext(idx);
                *pWorkItem = WorkItem(pUnrealizedChore, pGroup);
                return true;
            }

            pGroup = pRing->GetNextScheduleGroup(&idx, idxStart);
        }

        return false;

    }

    /// <summary>
    ///     Performs a fair search for work.
    /// </summary>
    bool WorkSearchContext::SearchFair(WorkItem *pWorkItem, ScheduleGroupBase *pOriginGroup, ULONG allowableTypes)
    {
        bool fFound = false;

        //
        // Do any up-front searching required for special circumstances (e.g.: UMS schedulers)
        //
        if (PreSearch(pWorkItem))
            return true;

        //
        // The fair search essentially round robins among scheduling rings and groups within a ring.
        // If you consider the search space as follows:
        //
        //               SR      SR     SR     SR
        // Contexts      ---------------------->
        // Realized      ---------------------->
        // Unrealized    ---------------------->
        //
        // fair scheduling will make horizontal slices through the search space to find work.
        //
        // Each entry in the above matrix can be viewed as:
        //
        // SG -> SG -> SG -> SG
        //
        // However, after finding work in a particular ring, fair will move onto the next ring in round-robin fashion.
        //

        //
        // At the top of each search, reset to the next ring in the round robin index.  This is simply the starting point for this search.
        //
        SchedulingRing *pCurrentRing;

        pCurrentRing = m_pCurrentRing = m_pScheduler->GetNextSchedulingRing();

        if (allowableTypes & WorkItem::WorkItemTypeContext)
        {
            SchedulingRing *pRing = pCurrentRing;
            while (pRing != NULL)
            {
                fFound = SearchFair_Runnables(pWorkItem, pRing);
                if (fFound)
                    break;
                
                pRing = m_pScheduler->GetNextSchedulingRing(pCurrentRing, pRing);
            }

            if (!fFound)
                fFound = StealForeignLocalRunnable(pWorkItem, m_pVirtualProcessor->GetOwningNode());
        }

        if (!fFound && (allowableTypes & WorkItem::WorkItemTypeRealizedChore))
        {
            SchedulingRing *pRing = pCurrentRing;
            while (pRing != NULL)
            {
                fFound = SearchFair_Realized(pWorkItem, pRing);
                if (fFound)
                    break;

                pRing = m_pScheduler->GetNextSchedulingRing(pCurrentRing, pRing);
            }
        }

        if (!fFound && (allowableTypes & WorkItem::WorkItemTypeUnrealizedChore))
        {
            SchedulingRing *pRing = pCurrentRing;
            while (pRing != NULL)
            {
                fFound = SearchFair_Unrealized(pWorkItem, pRing);
                if (fFound)
                    break;

                pRing = m_pScheduler->GetNextSchedulingRing(pCurrentRing, pRing);
            }
        }

        return fFound;
    }

    /// <summary>
    ///     Performs a fair search for work in the yielding case.
    /// </summary>
    bool WorkSearchContext::SearchFairYield(WorkItem *pWorkItem, ScheduleGroupBase *pOriginGroup, ULONG allowableTypes)
    {
        //
        // The yielding case slices identically to the regular case excepting that the search is done in a pseudo-reverse order
        //
        bool fFound = false;

        //
        // Do any up-front searching required for special circumstances (e.g.: UMS schedulers)
        //
        if (PreSearch(pWorkItem))
            return true;

        //
        // At the top of each search, reset to the next ring in the round robin index.  This is simply the starting point for this search.
        //
        SchedulingRing *pCurrentRing;

        pCurrentRing = m_pCurrentRing = m_pScheduler->GetNextSchedulingRing();

        if (allowableTypes & WorkItem::WorkItemTypeUnrealizedChore)
        {
            SchedulingRing *pRing = pCurrentRing;
            while (pRing != NULL)
            {
                fFound = SearchFair_Unrealized(pWorkItem, pRing);
                if (fFound)
                    break;

                pRing = m_pScheduler->GetNextSchedulingRing(pCurrentRing, pRing);
            }
        }


        if (!fFound && (allowableTypes & WorkItem::WorkItemTypeRealizedChore))
        {
            SchedulingRing *pRing = pCurrentRing;
            while (pRing != NULL)
            {
                fFound = SearchFair_Realized(pWorkItem, pRing);
                if (fFound)
                    break;

                pRing = m_pScheduler->GetNextSchedulingRing(pCurrentRing, pRing);
            }
        }

        if (!fFound && (allowableTypes & WorkItem::WorkItemTypeContext))
        {
            SchedulingRing *pRing = pCurrentRing;
            while (pRing != NULL)
            {
                fFound = SearchFair_Runnables(pWorkItem, pRing);
                if (fFound)
                    break;
                
                pRing = m_pScheduler->GetNextSchedulingRing(pCurrentRing, pRing);
            }

            if (!fFound)
                fFound = StealForeignLocalRunnable(pWorkItem, m_pVirtualProcessor->GetOwningNode());
        }

        return fFound;

    }

    //*************************************************************************** 
    //
    // Cache Local Searches
    //

    /// <summary>
    ///     Performs a cache local search for runnables in the specified ring.
    /// </summary>
    bool WorkSearchContext::SearchCacheLocal_Runnables(WorkItem *pWorkItem, SchedulingRing *pRing, ScheduleGroupBase *pOriginGroup)
    {
        int idx;
        ScheduleGroupBase *pGroup = pRing->GetPseudoRRScheduleGroup(&idx);

        int idxStart = idx;

        while (pGroup != NULL)
        {
            if (pGroup != pOriginGroup)
            {
                InternalContextBase *pContext = pGroup->GetRunnableContext();
                if (pContext != NULL)
                {
                    pRing->SetPseudoRRScheduleGroupNext(idx);
                    *pWorkItem = WorkItem(pContext);
                    return true;
                }
            }

            pGroup = pRing->GetNextScheduleGroup(&idx, idxStart);
        }

        return false;

    }

    /// <summary>
    ///     Performs a cache local search for realized chores in the specified ring.
    /// </summary>
    bool WorkSearchContext::SearchCacheLocal_Realized(WorkItem *pWorkItem, SchedulingRing *pRing, SchedulingRing *pStartingRing, ScheduleGroupBase *pOriginGroup)
    {
        //
        // At the outset of every search, bias to the origin group.
        //
        if (pRing == pStartingRing && pOriginGroup != NULL)
        {
            RealizedChore *pRealizedChore = pOriginGroup->GetRealizedChore();
            if (pRealizedChore != NULL)
            {
                *pWorkItem = WorkItem(pRealizedChore, pOriginGroup);
                return true;
            }
        }

        int idx;
        ScheduleGroupBase *pGroup = pRing->GetPseudoRRScheduleGroup(&idx);

        int idxStart = idx;

        while (pGroup != NULL)
        {
            if (pGroup != pOriginGroup)
            {
                RealizedChore *pRealizedChore = pGroup->GetRealizedChore();
                if (pRealizedChore != NULL)
                {
                    pRing->SetPseudoRRScheduleGroupNext(idx);
                    *pWorkItem = WorkItem(pRealizedChore, pGroup);
                    return true;
                }
            }

            pGroup = pRing->GetNextScheduleGroup(&idx, idxStart);
        }

        return false;

    }

    /// <summary>
    ///     Performs a cache local search for unrealized chores in the specified ring.
    /// </summary>
    bool WorkSearchContext::SearchCacheLocal_Unrealized(WorkItem *pWorkItem, SchedulingRing *pRing, SchedulingRing *pStartingRing, ScheduleGroupBase *pOriginGroup)
    {
        //
        // At the outset of every search, bias to the origin group.
        //
        if (pRing == pStartingRing && pOriginGroup != NULL)
        {
            _UnrealizedChore *pUnrealizedChore = pOriginGroup->StealUnrealizedChore();
            if (pUnrealizedChore != NULL)
            {
                *pWorkItem = WorkItem(pUnrealizedChore, pOriginGroup);
                return true;
            }
        }

        int idx;
        ScheduleGroupBase *pGroup = pRing->GetPseudoRRScheduleGroup(&idx);

        int idxStart = idx;

        while (pGroup != NULL)
        {
            if (pGroup != pOriginGroup)
            {
                _UnrealizedChore *pUnrealizedChore = pGroup->StealUnrealizedChore();
                if (pUnrealizedChore != NULL)
                {
                    pRing->SetPseudoRRScheduleGroupNext(idx);
                    *pWorkItem = WorkItem(pUnrealizedChore, pGroup);
                    return true;
                }
            }

            pGroup = pRing->GetNextScheduleGroup(&idx, idxStart);
        }