Invention Grant
- Patent Title: Lock-free work-stealing thread scheduler
-
Application No.: US17008549Application Date: 2020-08-31
-
Publication No.: US11698816B2Publication Date: 2023-07-11
- Inventor: Matthew S. Gates , Joel E. Lilienkamp , Alex Veprinsky , Susan Agten
- Applicant: HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP
- Applicant Address: US TX Houston
- Assignee: Hewlett Packard Enterprise Development LP
- Current Assignee: Hewlett Packard Enterprise Development LP
- Current Assignee Address: US TX Spring
- Agency: Yao Legal Services, Inc.
- Main IPC: G06F9/50
- IPC: G06F9/50 ; G06F9/48 ; G06F9/54 ; G06F12/0811 ; G06F12/0817

Abstract:
Systems and methods are provided for lock-free thread scheduling. Threads may be placed in a ring buffer shared by all computer processing units (CPUs), e.g., in a node. A thread assigned to a CPU may be placed in the CPU's local run queue. However, when a CPU's local run queue is cleared, that CPU checks the shared ring buffer to determine if any threads are waiting to run on that CPU, and if so, the CPU pulls a batch of threads related to that ready-to-run thread to execute. If not, an idle CPU randomly selects another CPU to steal threads from, and the idle CPU attempts to dequeue a thread batch associated with the CPU from the shared ring buffer. Polling may be handled through the use of a shared poller array to dynamically distribute polling across multiple CPUs.
Public/Granted literature
- US20220066831A1 LOCK-FREE WORK-STEALING THREAD SCHEDULER Public/Granted day:2022-03-03
Information query