diff options
Diffstat (limited to 'src/core/hle/kernel/scheduler.h')
| -rw-r--r-- | src/core/hle/kernel/scheduler.h | 247 |
1 files changed, 146 insertions, 101 deletions
diff --git a/src/core/hle/kernel/scheduler.h b/src/core/hle/kernel/scheduler.h index b29bf7be8..fcae28e0a 100644 --- a/src/core/hle/kernel/scheduler.h +++ b/src/core/hle/kernel/scheduler.h @@ -20,124 +20,172 @@ namespace Kernel { class Process; -class Scheduler final { +class GlobalScheduler final { public: - explicit Scheduler(Core::System& system, Core::ARM_Interface& cpu_core); - ~Scheduler(); + static constexpr u32 NUM_CPU_CORES = 4; - /// Returns whether there are any threads that are ready to run. - bool HaveReadyThreads() const; + explicit GlobalScheduler(Core::System& system); + ~GlobalScheduler(); + /// Adds a new thread to the scheduler + void AddThread(SharedPtr<Thread> thread); - /// Reschedules to the next available thread (call after current thread is suspended) - void Reschedule(); + /// Removes a thread from the scheduler + void RemoveThread(const Thread* thread); - /// Gets the current running thread - Thread* GetCurrentThread() const; + /// Returns a list of all threads managed by the scheduler + const std::vector<SharedPtr<Thread>>& GetThreadList() const { + return thread_list; + } - /// Gets the timestamp for the last context switch in ticks. - u64 GetLastContextSwitchTicks() const; + // Add a thread to the suggested queue of a cpu core. Suggested threads may be + // picked if no thread is scheduled to run on the core. + void Suggest(u32 priority, u32 core, Thread* thread); - /// Adds a new thread to the scheduler - void AddThread(SharedPtr<Thread> thread); + // Remove a thread to the suggested queue of a cpu core. Suggested threads may be + // picked if no thread is scheduled to run on the core. + void Unsuggest(u32 priority, u32 core, Thread* thread); - /// Removes a thread from the scheduler - void RemoveThread(Thread* thread); + // Add a thread to the scheduling queue of a cpu core. The thread is added at the + // back the queue in its priority level + void Schedule(u32 priority, u32 core, Thread* thread); - /// Schedules a thread that has become "ready" - void ScheduleThread(Thread* thread, u32 priority); + // Add a thread to the scheduling queue of a cpu core. The thread is added at the + // front the queue in its priority level + void SchedulePrepend(u32 priority, u32 core, Thread* thread); - /// Unschedules a thread that was already scheduled - void UnscheduleThread(Thread* thread, u32 priority); + // Reschedule an already scheduled thread based on a new priority + void Reschedule(u32 priority, u32 core, Thread* thread); - /// Sets the priority of a thread in the scheduler - void SetThreadPriority(Thread* thread, u32 priority); + // Unschedule a thread. + void Unschedule(u32 priority, u32 core, Thread* thread); - /// Gets the next suggested thread for load balancing - Thread* GetNextSuggestedThread(u32 core, u32 minimum_priority) const; + // Transfers a thread into an specific core. If the destination_core is -1 + // it will be unscheduled from its source code and added into its suggested + // queue. + void TransferToCore(u32 priority, s32 destination_core, Thread* thread); - /** - * YieldWithoutLoadBalancing -- analogous to normal yield on a system - * Moves the thread to the end of the ready queue for its priority, and then reschedules the - * system to the new head of the queue. - * - * Example (Single Core -- but can be extrapolated to multi): - * ready_queue[prio=0]: ThreadA, ThreadB, ThreadC (->exec order->) - * Currently Running: ThreadR - * - * ThreadR calls YieldWithoutLoadBalancing - * - * ThreadR is moved to the end of ready_queue[prio=0]: - * ready_queue[prio=0]: ThreadA, ThreadB, ThreadC, ThreadR (->exec order->) - * Currently Running: Nothing - * - * System is rescheduled (ThreadA is popped off of queue): - * ready_queue[prio=0]: ThreadB, ThreadC, ThreadR (->exec order->) - * Currently Running: ThreadA - * - * If the queue is empty at time of call, no yielding occurs. This does not cross between cores - * or priorities at all. + /* + * UnloadThread selects a core and forces it to unload its current thread's context */ - void YieldWithoutLoadBalancing(Thread* thread); + void UnloadThread(s32 core); + + /* + * SelectThread takes care of selecting the new scheduled thread. + * It does it in 3 steps: + * - First a thread is selected from the top of the priority queue. If no thread + * is obtained then we move to step two, else we are done. + * - Second we try to get a suggested thread that's not assigned to any core or + * that is not the top thread in that core. + * - Third is no suggested thread is found, we do a second pass and pick a running + * thread in another core and swap it with its current thread. + */ + void SelectThread(u32 core); - /** - * YieldWithLoadBalancing -- yield but with better selection of the new running thread - * Moves the current thread to the end of the ready queue for its priority, then selects a - * 'suggested thread' (a thread on a different core that could run on this core) from the - * scheduler, changes its core, and reschedules the current core to that thread. - * - * Example (Dual Core -- can be extrapolated to Quad Core, this is just normal yield if it were - * single core): - * ready_queue[core=0][prio=0]: ThreadA, ThreadB (affinities not pictured as irrelevant - * ready_queue[core=1][prio=0]: ThreadC[affinity=both], ThreadD[affinity=core1only] - * Currently Running: ThreadQ on Core 0 || ThreadP on Core 1 - * - * ThreadQ calls YieldWithLoadBalancing - * - * ThreadQ is moved to the end of ready_queue[core=0][prio=0]: - * ready_queue[core=0][prio=0]: ThreadA, ThreadB - * ready_queue[core=1][prio=0]: ThreadC[affinity=both], ThreadD[affinity=core1only] - * Currently Running: ThreadQ on Core 0 || ThreadP on Core 1 - * - * A list of suggested threads for each core is compiled - * Suggested Threads: {ThreadC on Core 1} - * If this were quad core (as the switch is), there could be between 0 and 3 threads in this - * list. If there are more than one, the thread is selected by highest prio. - * - * ThreadC is core changed to Core 0: - * ready_queue[core=0][prio=0]: ThreadC, ThreadA, ThreadB, ThreadQ - * ready_queue[core=1][prio=0]: ThreadD - * Currently Running: None on Core 0 || ThreadP on Core 1 - * - * System is rescheduled (ThreadC is popped off of queue): - * ready_queue[core=0][prio=0]: ThreadA, ThreadB, ThreadQ - * ready_queue[core=1][prio=0]: ThreadD - * Currently Running: ThreadC on Core 0 || ThreadP on Core 1 - * - * If no suggested threads can be found this will behave just as normal yield. If there are - * multiple candidates for the suggested thread on a core, the highest prio is taken. + bool HaveReadyThreads(u32 core_id) const { + return !scheduled_queue[core_id].empty(); + } + + /* + * YieldThread takes a thread and moves it to the back of the it's priority list + * This operation can be redundant and no scheduling is changed if marked as so. */ - void YieldWithLoadBalancing(Thread* thread); + bool YieldThread(Thread* thread); - /// Currently unknown -- asserts as unimplemented on call - void YieldAndWaitForLoadBalancing(Thread* thread); + /* + * YieldThreadAndBalanceLoad takes a thread and moves it to the back of the it's priority list. + * Afterwards, tries to pick a suggested thread from the suggested queue that has worse time or + * a better priority than the next thread in the core. + * This operation can be redundant and no scheduling is changed if marked as so. + */ + bool YieldThreadAndBalanceLoad(Thread* thread); - /// Returns a list of all threads managed by the scheduler - const std::vector<SharedPtr<Thread>>& GetThreadList() const { - return thread_list; + /* + * YieldThreadAndWaitForLoadBalancing takes a thread and moves it out of the scheduling queue + * and into the suggested queue. If no thread can be squeduled afterwards in that core, + * a suggested thread is obtained instead. + * This operation can be redundant and no scheduling is changed if marked as so. + */ + bool YieldThreadAndWaitForLoadBalancing(Thread* thread); + + /* + * PreemptThreads this operation rotates the scheduling queues of threads at + * a preemption priority and then does some core rebalancing. Preemption priorities + * can be found in the array 'preemption_priorities'. This operation happens + * every 10ms. + */ + void PreemptThreads(); + + u32 CpuCoresCount() const { + return NUM_CPU_CORES; + } + + void SetReselectionPending() { + is_reselection_pending.store(true, std::memory_order_release); } + bool IsReselectionPending() const { + return is_reselection_pending.load(std::memory_order_acquire); + } + + void Shutdown(); + private: - /** - * Pops and returns the next thread from the thread queue - * @return A pointer to the next ready thread - */ - Thread* PopNextReadyThread(); + bool AskForReselectionOrMarkRedundant(Thread* current_thread, Thread* winner); + + static constexpr u32 min_regular_priority = 2; + std::array<Common::MultiLevelQueue<Thread*, THREADPRIO_COUNT>, NUM_CPU_CORES> scheduled_queue; + std::array<Common::MultiLevelQueue<Thread*, THREADPRIO_COUNT>, NUM_CPU_CORES> suggested_queue; + std::atomic<bool> is_reselection_pending; + + // `preemption_priorities` are the priority levels at which the global scheduler + // preempts threads every 10 ms. They are ordered from Core 0 to Core 3 + std::array<u32, NUM_CPU_CORES> preemption_priorities = {59, 59, 59, 62}; + + /// Lists all thread ids that aren't deleted/etc. + std::vector<SharedPtr<Thread>> thread_list; + Core::System& system; +}; + +class Scheduler final { +public: + explicit Scheduler(Core::System& system, Core::ARM_Interface& cpu_core, u32 core_id); + ~Scheduler(); + + /// Returns whether there are any threads that are ready to run. + bool HaveReadyThreads() const; + /// Reschedules to the next available thread (call after current thread is suspended) + void TryDoContextSwitch(); + + /// Unloads currently running thread + void UnloadThread(); + + /// Select the threads in top of the scheduling multilist. + void SelectThreads(); + + /// Gets the current running thread + Thread* GetCurrentThread() const; + + /// Gets the currently selected thread from the top of the multilevel queue + Thread* GetSelectedThread() const; + + /// Gets the timestamp for the last context switch in ticks. + u64 GetLastContextSwitchTicks() const; + + bool ContextSwitchPending() const { + return is_context_switch_pending; + } + + /// Shutdowns the scheduler. + void Shutdown(); + +private: + friend class GlobalScheduler; /** * Switches the CPU's active thread context to that of the specified thread * @param new_thread The thread to switch to */ - void SwitchContext(Thread* new_thread); + void SwitchContext(); /** * Called on every context switch to update the internal timestamp @@ -152,19 +200,16 @@ private: */ void UpdateLastContextSwitchTime(Thread* thread, Process* process); - /// Lists all thread ids that aren't deleted/etc. - std::vector<SharedPtr<Thread>> thread_list; - - /// Lists only ready thread ids. - Common::MultiLevelQueue<Thread*, THREADPRIO_LOWEST + 1> ready_queue; - SharedPtr<Thread> current_thread = nullptr; + SharedPtr<Thread> selected_thread = nullptr; + Core::System& system; Core::ARM_Interface& cpu_core; u64 last_context_switch_time = 0; + u64 idle_selection_count = 0; + const u32 core_id; - Core::System& system; - static std::mutex scheduler_mutex; + bool is_context_switch_pending = false; }; } // namespace Kernel |