searchalgorithms.h

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

        bool Search(WorkItem *pWorkItem, 
                    ScheduleGroupBase *pOriginGroup,
                    ULONG allowableTypes = WorkItem::WorkItemTypeContext | WorkItem::WorkItemTypeRealizedChore | WorkItem::WorkItemTypeUnrealizedChore)
        {
            return (this->*m_pSearchFn)(pWorkItem, pOriginGroup, allowableTypes);
        }


        /// <summary>
        ///     Searches from the last iterator position according to the set algorithm for a yield.  This can return any type of
        ///     work item (context, realized chore, or unrealized chore)
        /// </summary>
        bool YieldingSearch(WorkItem *pWorkItem, 
                                ScheduleGroupBase *pOriginGroup,
                                ULONG allowableTypes = WorkItem::WorkItemTypeContext | WorkItem::WorkItemTypeRealizedChore)
        {
            return (this->*m_pSearchYieldFn)(pWorkItem, pOriginGroup, allowableTypes);
        }
                                
    private:

        // **************************************************
        // Common:
        //

        //
        // NOTE: The m_pCurrentRing and m_pStartingRing are flagged as volatile because it's possible that something blocks inside
        // the search algorithm and the UMS primary invokes a search for runnables during that point.  In that case, the routine must
        // be fully reentrant and the original search may have m_pCurrentRing/m_pStartingRing overwritten by the primary.  This is not a problem
        // if the search code takes care.  It snaps these values at the top of a loop and utilizes them during the search locally.
        //

        // The current scheduling ring.
        SchedulingRing * volatile m_pCurrentRing;

        // The ring at which we started a search
        SchedulingRing * volatile m_pStartingRing;

        // The virtual processor binding the search.
        VirtualProcessor *m_pVirtualProcessor;

        // The scheduler
        SchedulerBase *m_pScheduler;

        // How many times work has been found in the local bias (LRCs, current schedule group) since the last local bias reset
        ULONG m_localBias;

        // How many times work has been found in the local bias OR current scheduling ring since the last ring bias reset.
        ULONG m_ringBias;

        // The search function to utilize.
        bool (WorkSearchContext::*m_pSearchFn)(WorkItem *pWorkItem, 
                                               ScheduleGroupBase *pOriginGroup, 
                                               ULONG allowableTypes);

        // The search function to utilize for yielding.
        bool (WorkSearchContext::*m_pSearchYieldFn)(WorkItem *pWorkItem, 
                                                    ScheduleGroupBase *pOriginGroup, 
                                                    ULONG allowableTypes);

        // An indication of whether we are to perform a one time LRC scan upon a forced ring change.
        bool m_fPerformOneTimeLRCScan;
        bool m_fPerformedOneTimeLRCScan;

        /// <summary>
        ///     Performs a pre-search for any "special" contexts (e.g.: the UMS SUT)
        /// </summary>
        bool PreSearch(WorkItem *pWorkItem);

        /// <summary>
        ///     Steals a local runanble from a virtual processor within the specified node.  Note that this allows a given virtual processor
        ///     to be skipped.
        /// </summary>
        bool StealLocalRunnable(WorkItem *pWorkItem, SchedulingNode *pNode, VirtualProcessor *pSkipVirtualProcessor);

        /// <summary>
        ///     Steals a local runnable from a virtual processor of any scheduling node other than the specified local node.
        /// </summary>
        bool StealForeignLocalRunnable(WorkItem *pWorkItem, SchedulingNode *pLocalNode);

        /// <summary>
        ///     Gets a local runnable context from the specified virtual processor.
        /// </summary>
        bool GetLocalRunnable(WorkItem *pWorkItem, VirtualProcessor *pVirtualProcessor, bool fSteal);

        /// <summary>
        ///     Gets a runnable from the specified group.
        /// </summary>
        bool GetRunnableContext(WorkItem *pWorkItem, ScheduleGroupBase *pGroup);

        /// <summary>
        ///     Called on any biased work.
        /// </summary>
        void Bias()
        {
            m_localBias++;
            m_ringBias++;
        }

        /// <summary>
        ///     Resets the local bias counter but not the ring bias counter.
        /// </summary>
        void ResetLocalBias()
        {
            m_localBias = 0;
        }

        /// <summary>
        ///     Resets all bias counters.
        /// </summary>
        void ResetBias()
        {
            m_localBias = m_ringBias = 0;
            m_fPerformOneTimeLRCScan = false;
            m_fPerformedOneTimeLRCScan = false;
        }

        /// <summary>
        ///     Returns the current stage of local bias.
        /// </summary>
        int LocalBiasStage()
        {
            if (m_localBias < 101)
                return 0; // (fwd) Normal --> LRC LIFO
            else if (m_localBias < 127)
                return 1; // (fwd) Flip LRC --> LRC FIFO
            else if (m_localBias < 151)
                return 2; // (fwd) Skip LRC --> runnables
            else
                return 3; // (fwd) Skip SG --> inject change
        }

        /// <summary>
        ///     Returns whether we drop the bias to the current scheduling ring.  This is the final stage of dropping bias.  After
        ///     this, bias should be reset and we can go back to being fully cache local on another scheduling ring.
        /// </summary>
        bool DropRingBias()
        {
            bool fDrop = (m_ringBias > 307);
            if (fDrop && !m_fPerformedOneTimeLRCScan)
                m_fPerformOneTimeLRCScan = true;

            return fDrop;
        }

        /// <summary>
        ///     Informs us whether we perform a one time LRC scan upon entering a new ring via a forced transition.
        /// </summary>
        bool PerformOneTimeLRCScan()
        {
            if (m_fPerformOneTimeLRCScan)
            {
                m_fPerformOneTimeLRCScan = false;
                m_fPerformedOneTimeLRCScan = true;
                return true;
            }

            return false;
        }


        // **************************************************
        // Cache Local Algorithm:
        //

        /// <summary>
        ///     Performs a cache local search for runnables in the specified ring.
        /// </summary>
        bool SearchCacheLocal_Runnables(WorkItem *pWorkItem, SchedulingRing *pRing, ScheduleGroupBase *pOriginGroup);

        /// <summary>
        ///     Performs a cache local search for realized chores in the specified ring.
        /// </summary>
        bool SearchCacheLocal_Realized(WorkItem *pWorkItem, SchedulingRing *pRing, SchedulingRing *pStartingRing, ScheduleGroupBase *pOriginGroup);

        /// <summary>
        ///     Performs a cache local search for unrealized chores in the specified ring.
        /// </summary>
        bool SearchCacheLocal_Unrealized(WorkItem *pWorkItem, SchedulingRing *pRing, SchedulingRing *pStartingRing, ScheduleGroupBase *pOriginGroup);

        /// <summary>
        ///     Performs a cache local search for work.
        /// </summary>
        bool SearchCacheLocal(WorkItem *pWorkItem, ScheduleGroupBase *pOriginGroup, ULONG allowableTypes);

        /// <summary>
        ///     Performs a cache local search for work in the yielding case.
        /// </summary>
        bool SearchCacheLocalYield(WorkItem *pWorkItem, ScheduleGroupBase *pOriginGroup, ULONG allowableTypes);

        // **************************************************
        // Fair Algorithm:
        //

        /// <summary>
        ///     Performs a fair search for runnables in the specified ring.
        /// </summary>
        bool SearchFair_Runnables(WorkItem *pWorkItem, SchedulingRing *pRing);

        /// <summary>
        ///     Performs a fair search for realized chores in the specified ring.
        /// </summary>
        bool SearchFair_Realized(WorkItem *pWorkItem, SchedulingRing *pRing);

        /// <summary>
        ///     Performs a fair search for unrealized chores in the specified ring.
        /// </summary>
        bool SearchFair_Unrealized(WorkItem *pWorkItem, SchedulingRing *pRing);

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

        /// <summary>
        ///     Performs a fair search for work in the yielding case.
        /// </summary>
        bool SearchFairYield(WorkItem *pWorkItem, ScheduleGroupBase *pOriginGroup, ULONG allowableTypes); 

    };

}
}