searchalgorithms.cpp

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

// ==++==
//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// SearchAlgorithms.cpp
//
// Implementation file containing all scheduling algorithms.
//
// **PLEASE NOTE**:
//
//     Any search algorithm in here must be fully reentrant.  On UMS schedulers, the UMS primary will invoke these routines
//     to perform a search for work.
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

#include "concrtinternal.h"

namespace Concurrency
{
namespace details
{
    //*************************************************************************** 
    //
    // General:
    //

    /// <summary>
    ///     Constructs a work item from an internal context.
    /// </summary>
    WorkItem::WorkItem(InternalContextBase *pContext) :
        m_type(WorkItemTypeContext),
        m_pGroup(pContext->GetScheduleGroup()),
        m_pContext(pContext)
    {
    }

    /// <summary>
    ///     Binds the work item to a context and returns the context.  This may or may not allocate a new context.  Note that
    ///     act of binding which performs a context allocation will transfer a single count of work to the counter of the new
    ///     context.
    /// </summary>
    InternalContextBase *WorkItem::Bind()
    {
        switch(m_type)
        {
            case WorkItemTypeUnrealizedChore:
                m_pContext = m_pGroup->GetInternalContext(m_pUnrealizedChore, true);
                m_pContext->SaveDequeuedTask();
                break;
            case WorkItemTypeRealizedChore:
                m_pContext = m_pGroup->GetInternalContext(m_pRealizedChore);
                m_pContext->SaveDequeuedTask();
                break;
            case WorkItemTypeContext:
                break;
        }

        m_type = WorkItemTypeContext;
        return m_pContext;
    }

    /// <summary>
    ///     Invokes the work item.
    /// </summary>
    void WorkItem::Invoke()
    {
        CORE_ASSERT(m_type == WorkItemTypeRealizedChore || m_type == WorkItemTypeUnrealizedChore);
        switch(m_type)
        {
            case WorkItemTypeUnrealizedChore:
                m_pUnrealizedChore->_Invoke();
                break;
            case WorkItemTypeRealizedChore:
                m_pRealizedChore->Invoke();
                m_pGroup->GetScheduler()->ReleaseRealizedChore(m_pRealizedChore);
                break;
        }
    }

    /// <summary>
    ///     Transfers reference counts as necessary to inline the given work item on the given context.  This may
    ///     only be called on a work item that can be inlined (e.g.: an unbound one).
    /// </summary>
    /// <param name="pContext">
    ///     The context that is attempting to inline the work item.
    /// </param>
    void WorkItem::TransferReferences(InternalContextBase *pContext)
    {
        ASSERT(m_type == WorkItemTypeRealizedChore || m_type == WorkItemTypeUnrealizedChore);

        ScheduleGroupBase *pGroup = pContext->GetScheduleGroup();
        if (m_type == WorkItemTypeRealizedChore)
        {
            if (pGroup != m_pGroup)
                pContext->SwapScheduleGroup(m_pGroup, false);
            else
                //
                // If newGroup is the same as the existing group, we need to release a reference since both, the context,
                // and the realized chore, have a reference on the schedule group, and we only need to hold one reference.
                //
                pGroup->InternalRelease();

        }
        else if (pGroup != m_pGroup)
        {
            pContext->SwapScheduleGroup(m_pGroup, true);
        }
    }

    /// <summary>
    ///     Resets the work search context to utilize the specified algorithm at the starting iterator position.
    /// </summary>
    /// <param name="pVirtualProcessor">
    ///     The virtual processor binding the searching.
    /// </param>
    /// <param name="algorithm">
    ///     The algorithm to reset the iterator with.
    /// </param>
    void WorkSearchContext::Reset(VirtualProcessor *pVirtualProcessor, Algorithm algorithm)
    {
        m_pCurrentRing = NULL;
        m_localBias = 0;
        m_ringBias = 0;
        m_fPerformOneTimeLRCScan = false;
        m_fPerformedOneTimeLRCScan = false;
        m_pVirtualProcessor = pVirtualProcessor;
        m_pScheduler = pVirtualProcessor->GetOwningNode()->GetScheduler();

        switch(algorithm)
        {
            case AlgorithmCacheLocal:
                m_pSearchFn = &WorkSearchContext::SearchCacheLocal;
                m_pSearchYieldFn = &WorkSearchContext::SearchCacheLocalYield;
                break;
            case AlgorithmFair:
                m_pSearchFn = &WorkSearchContext::SearchFair;
                m_pSearchYieldFn = &WorkSearchContext::SearchFairYield;
                break;
            default:
                ASSERT(false);
        }
    }

    /// <summary>
    ///     Steals a local runnable from a virtual processor within the specified node.  Note that this allows a given virtual processor
    ///     to be skipped.
    /// </summary>
    bool WorkSearchContext::StealLocalRunnable(WorkItem *pWorkItem, SchedulingNode *pNode, VirtualProcessor *pSkipVirtualProcessor)
    {
        int idx;
        VirtualProcessor *pVProc = pNode->GetFirstVirtualProcessor(&idx);
        while (pVProc != NULL)
        {
            if (pVProc != pSkipVirtualProcessor)
            {
                InternalContextBase *pContext = pVProc->StealLocalRunnableContext();
                if (pContext != NULL)
                {
                    *pWorkItem = WorkItem(pContext);
                    return true;
                }
            }
            
            pVProc = pNode->GetNextVirtualProcessor(&idx);
        }

        return false;
    }

    /// <summary>
    ///     Steals a local runnable from a virtual processor of any scheduling node other than the specified local node.
    /// </summary>
    bool WorkSearchContext::StealForeignLocalRunnable(WorkItem *pWorkItem, SchedulingNode *pLocalNode)
    {
        int idx;
        SchedulingNode *pNode = m_pScheduler->GetFirstSchedulingNode(&idx);
        while (pNode != NULL)
        {
            if (pNode != pLocalNode)
            {
                if (StealLocalRunnable(pWorkItem, pNode, NULL))
                    return true;
            }

            pNode = m_pScheduler->GetNextSchedulingNode(&idx);
        }

        return false;

    }

    /// <summary>
    ///     Performs a pre-search for any "special" contexts (e.g.: the UMS SUT)
    /// </summary>
    bool WorkSearchContext::PreSearch(WorkItem *pWorkItem)
    {
        InternalContextBase *pContext = m_pVirtualProcessor->PreRunnableSearch();
        if (pContext != NULL)
        {
            *pWorkItem = WorkItem(pContext);
            return true;
        }

        return false;
    }

    /// <summary>
    ///     Gets a local runnable context from the specified virtual processor.
    /// </summary>
    bool WorkSearchContext::GetLocalRunnable(WorkItem *pWorkItem, VirtualProcessor *pVirtualProcessor, bool fSteal)
    {
        InternalContextBase *pContext = fSteal ? pVirtualProcessor->StealLocalRunnableContext() : pVirtualProcessor->GetLocalRunnableContext();
        if (pContext != NULL)
        {
            *pWorkItem = WorkItem(pContext);
            return true;
        }

        return false;
    }

    /// <summary>
    ///     Gets a runnable from the specified group.
    /// </summary>
    bool WorkSearchContext::GetRunnableContext(WorkItem *pWorkItem, ScheduleGroupBase *pGroup)
    {
        InternalContextBase *pContext = pGroup->GetRunnableContext();
        if (pContext != NULL)
        {
            *pWorkItem = WorkItem(pContext);
            return true;
        }

        return false;
    }

    //*************************************************************************** 
    //
    // Fair Searches
    //

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

        int idxStart = idx;

        while (pGroup != NULL)
        {
            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 fair search for realized chores in the specified ring.
    /// </summary>
    bool WorkSearchContext::SearchFair_Realized(WorkItem *pWorkItem, SchedulingRing *pRing)
    {
        int idx;
        ScheduleGroupBase *pGroup = pRing->GetPseudoRRScheduleGroup(&idx);

        int idxStart = idx;

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

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

        return false;

    }