Patent Publication Number: US-11048562-B2

Title: Multi-thread synchronization primitive

Description:
This application claims the benefit of U.S. Prov. Appl. No. 62/514,914 filed on Jun. 4, 2017, which is incorporated by reference herein in its entirety. 
    
    
     BACKGROUND 
     Technical Field 
     This disclosure relates generally to computer systems, and, more specifically, to operating systems that support execution of multi-threaded applications. 
     Description of the Related Art 
     Modern computer systems typically include one or more processors having multiple execution cores, which may also have multiple execution pipelines. The inclusion of multiple pipelines in a processor may allow a computer system to execute multiple instruction sequences in parallel in order to perform multiple tasks concurrently. To allow application developers to use this functionality, a modern operating system may provide an application programming interface (API) that allows an application to make various system calls to the operating system to request the use of this functionality. For example, in Linux and Berkeley Software Distribution (BSD) operating systems, an application may include a “fork” system call to request that an operating system kernel spawn an additional thread to perform one or more tasks concurrently with tasks being performed by a main thread of the application. 
     To facilitate communication between applications (as well as threads within an application), modern operating systems may implement an inter-process communication system in which threads may send and receive messages with other threads. In sending a message, a first thread may issue a request to an operating system kernel to cause it to route a message through the operating system kernel to a second recipient thread. If the second thread wants to respond, it may make a similar request to route a response back to the first read. This system may also be used to notify a thread when particular events occur within the computer system, so that the thread can take appropriate action. For example, if a thread is wanting to open a particular file being accessed by some other thread, the thread may request that the operating system kernel notify it when the other thread has closed the file making it available for access. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram illustrating an example of a multi-threaded computer system that uses queues to pass work items to an operating system kernel and to receive notifications of events from the operating system kernel. 
         FIG. 2  is a block diagram illustrating an exemplary arrangement for a collection of queues used by the computer system. 
         FIG. 3  is a block diagram illustrating an example of a user-space synchronization primitive that controls access to a collection of queues and its corresponding kernel-space synchronization primitive. 
         FIGS. 4A and 4B  are block diagrams illustrating an example of a synchronization-primitive manager within a kernel space of the computer system. 
         FIGS. 5A and 5B  are block diagrams illustrating exemplary finite state machines (FSMs) associated with user-space and kernel-space synchronization primitives. 
         FIG. 6A-6C  are flow diagrams illustrating exemplary methods performed by elements of the computer system. 
         FIG. 7  is a block diagram illustrating one embodiment of an exemplary computer system. 
     
    
    
     This disclosure includes references to “one embodiment” or “an embodiment.” The appearances of the phrases “in one embodiment” or “in an embodiment” do not necessarily refer to the same embodiment. Particular features, structures, or characteristics may be combined in any suitable manner consistent with this disclosure. 
     Within this disclosure, different entities (which may variously be referred to as “units,” “circuits,” other components, etc.) may be described or claimed as “configured” to perform one or more tasks or operations. This formulation—[entity] configured to [perform one or more tasks]—is used herein to refer to structure (i.e., something physical, such as an electronic circuit). More specifically, this formulation is used to indicate that this structure is arranged to perform the one or more tasks during operation. A structure can be said to be “configured to” perform some task even if the structure is not currently being operated. A “processor configured to execute program instructions of an application” is intended to cover, for example, an integrated circuit that has circuitry that performs this function during operation, even if the integrated circuit in question is not currently being used (e.g., a power supply is not connected to it). Thus, an entity described or recited as “configured to” perform some task refers to something physical, such as a device, circuit, memory storing program instructions executable to implement the task, etc. This phrase is not used herein to refer to something intangible. Thus, the “configured to” construct is not used herein to refer to a software entity such as an application programming interface (API). 
     The term “configured to” is not intended to mean “configurable to.” An unprogrammed FPGA, for example, would not be considered to be “configured to” perform some specific function, although it may be “configurable to” perform that function and may be “configured to” perform the function after programming. 
     Reciting in the appended claims that a structure is “configured to” perform one or more tasks is expressly intended not to invoke 35 U.S.C. § 112(f) for that claim element. Accordingly, none of the claims in this application as filed are intended to be interpreted as having means-plus-function elements. Should Applicant wish to invoke Section 112(f) during prosecution, it will recite claim elements using the “means for” [performing a function] construct. 
     As used herein, the terms “first,” “second,” etc. are used as labels for nouns that they precede, and do not imply any type of ordering (e.g., spatial, temporal, logical, etc.) unless specifically stated. For example, in a processor having eight processing cores, the terms “first” and “second” processing cores can be used to refer to any two of the eight processing cores. In other words, the “first” and “second” processing cores are not limited to logical processing cores 0 and 1, for example. 
     As used herein, the term “based on” is used to describe one or more factors that affect a determination. This term does not foreclose the possibility that additional factors may affect a determination. That is, a determination may be solely based on specified factors or based on the specified factors as well as other, unspecified factors. Consider the phrase “determine A based on B.” This phrase specifies that B is a factor is used to determine A or that affects the determination of A. This phrase does not foreclose that the determination of A may also be based on some other factor, such as C. This phrase is also intended to cover an embodiment in which A is determined based solely on B. As used herein, the phrase “based on” is thus synonymous with the phrase “based at least in part on.” 
     DETAILED DESCRIPTION 
     While using multiple threads can provide significant performance improvements for an application, traditional multi-threading techniques do have some potential downsides. Spawning threads (e.g., using a fork system call) can have enough overhead to easy mitigate any benefits if the tasks being performed by the new threads are small ones. In order to correctly use threads, application developers may need to understand system calls and understand proper thread management such as remembering to kill threads after they are no longer being used. Still further, using multiple threads may further complicate delivery of messages (e.g., regarding inter-process communications or occurrences of other events) to an application as messages may need to be routed to the appropriate application threads executable to process them. One approach involved an application maintaining a dedicated thread for receiving messages and delivering messages to the appropriate application threads; however, maintaining a thread solely for this purpose is an inefficient use of system resources—particularly when each application on a computer system may have such a thread. 
     The present disclosure describes techniques for improving usage of multiple threads by, for example, reducing the overhead associated with using multiple threads as well as reducing the overhead associated with delivering notifications to an application. As will be described in greater detail below, in various embodiments, an operating system kernel can maintain a collection of already spawned threads (referred to below as a “thread pool”) that can be dispatched to executing applications to assist in the performance of various work items. Notably, once a dispatched thread has assisted an application with performance of a requested work item, the thread can return to the thread pool, so that it can later be dispatched. An advantage of dispatching threads in this manner is that a thread does not have to be recreated for every work item, and thus incur the overhead of recreation. Dispatched threads may also handle delivery of notifications/messages (referred to below as “kernel events”) regarding the occurrences of various events such as the arrival of an inter-process communication. 
     In order to facilitate delivery of work items and kernel events, in various embodiments, an application instantiates a collection of queues to receive work items and kernel events for processing. Accordingly, if a thread of an application wants to have a work item processed, the thread can enqueue the work item in the collection of queues and have the kernel dispatch a thread from the thread pool (as opposed to spawning a child thread to handle the item, which, again, would involve additional overhead). The dispatched thread may then dequeue the work item and process it. Similarly, a dispatched thread delivering a kernel event may enqueue it in the collection of queues, and an application thread may subsequently dequeue the kernel event for processing. Such a delivery scheme may be advantageous over the prior delivery approach noted above as a dedicated kernel-event processing thread does not need to be maintained, freeing up additional resources. 
     As application threads and dispatched threads may simultaneously compete to enqueue and/or dequeue work items and kernel events, in various embodiments, a synchronization primitive is instantiated to control access to the collection of queues. As used herein, the term “synchronization primitive” is to be interpreted according to its understood meaning in the art, and includes a data structure that controls access to a resource in a manner that ensures mutual exclusion such as a semaphore, mutex, lock, etc. In various embodiments, the synchronization primitive is operable to, not only control access to a collection of queues, but also store various metadata about enqueue items, which is useful to the kernel as well as dispatched threads. For example, in some embodiments, the synchronization primitive may store an execution priority associated with an enqueued item to indicate that the kernel is supposed to dispatch a thread at that execution priority to perform the work item. In some embodiments, the kernel is unable to directly access the synchronization primitive; however, information stored in the synchronization primitive may be exposed via one or more system calls to the kernel, which may instantiate a data structure corresponding to the synchronization primitive for storing this conveyed information. For example, this data structure may include the priority of an enqueued item. In various embodiments, the kernel stores additional information in this structure that may be helpful for dispatching threads. For example, in some embodiments, this additional information may include an identifier for any dispatched thread, which is associated with the synchronization primitive (or more generally the collection of queues). If the kernel receives a system call from an application requesting a thread to handle a newly enqueued work item, the kernel may determine from this identifier that a thread has already been dispatched to operate on an earlier enqueued item in the collection of queues and can operate on this newly enqueued item (or may determine to delay dispatching another thread until the previously dispatched thread returns to the thread pool). As a result, the number of times a thread gets dispatched and/or the frequency of dispatching threads may be reduced. 
     Turning now to  FIG. 1 , a block diagram of a computer system  10  configured to execute multiple threads is depicted. In the illustrated embodiment, system  10  includes an application  110 , queue manager  120 , and thread pool  130 . Application  110  includes one or more application threads  112 , queues  114 , and a synchronization primitive  118 A. Queue manager  120  includes a synchronization primitive  118 B and kernel queues  124 . Thread pool  130  includes worker threads  132 . In some embodiments, system  10  may be implemented different than shown. For example, system  10  may include multiple applications  110 , each application  110  may include multiple collections of queues  114 , each controlled by a primitive  118 A, etc. System  10  may also include multiple thread pools  130 . 
     As shown, in various embodiments, application  110  resides in user space  102  while queue manager  120  and thread pool  130  reside in kernel space  104 . As used herein, a “user space” (or application space) refers to a classification of applications (i.e., processes) that execute with restricted privileges (e.g., restricted access to files, addresses, hardware, etc.) and typically includes applications that are not responsible for management of the computer system. Examples of user-space applications may include, for example, word processing applications, web browsers, mail clients, etc. For security reasons, most applications typically run as user-space applications. The term “user space” can also refer to a region (or regions) of memory allocated to a user-space application for storage of its program instructions and application data. In many instances, a user-space application  110  may be restricted to accessing only data within a user-space region of memory. In contrast, “kernel space” (or system space) refers to a classification of applications that execute with unrestricted privileges and typically includes applications responsible for system management. Examples of kernel-space applications may include an operating system kernel, drivers, a hypervisor, etc. “Kernel space” can also refer to restricted regions of memory that can only be accessed by kernel-space applications. In some embodiments, kernel-space applications may also be restricted from accessing user-space regions of memory. Restricting applications  110  in this manner may provide additional security as it can prevent a malicious (or malfunctioning) application from executing with the full set of privileges given to, for example, the operating system kernel. It can also prevent kernel-space applications from being compromised by causing them to run user-space program instructions. 
     Application  110 , in various embodiments, is a multi-threaded application and may correspond to any suitable application such as those mentioned above. Being a multi-threaded application, application  110  may spawn multiple threads  112  to perform multiple actions concurrently. For example, if application  110  is a mail client, application  110  may have a main thread  112  for managing the user interface and spawn another thread  112  for retrieving email from a mail server concurrently. As an alternative to spawning an additional thread  112  to perform some action, in various embodiments, an application  110  may offload the work (shown as a work item  116 ) to a worker thread  132  for performance. As used herein, the term “work item” refers generally to a set of instructions for performing some action. For example, a mail client may present multiple panels, each showing a respective portion of a received email in a user&#39;s inbox. Rather than spawn multiple threads  112  to read each email portion, the mail client may provide a work item  116  for each panel to cause one or more worker threads  132  to perform reading the email portions from memory. Application  110  may also want to receive notifications (shown as kernel events  126 ) from the kernel when particular events occur. For example, a mail application may want to know when a push notification has been received from a mail server indicating that new mail is available for retrieval. As will be discussed below, in various embodiments, a worker thread  132  may be dispatched to deliver such a kernel event  126  in response to, for example, a network interface card of system  10  receiving traffic via a particular TCP/IP port associated with the push notification. Kernel events  126  may also be used to deliver inter-process communications such as a request from another application to open a window for a user to compose an email because the user clicked an email address in the other application. 
     Queues  114  may be instantiated by an application  110  to facilitate the exchange of work items  116  and kernel events  126  between threads  112  and  132 . Accordingly, if an application thread  112  wants to offload a work item to a worker thread  132 , the thread  112  may enqueue it in a queue  114 , and a work thread  132  may subsequently retrieve the work item  116  from a queue  114  to perform the work item  116 . In some embodiments, work items  116  may be enqueued asynchronously or synchronously. In asynchronous enqueuing, a thread  112  delivers a work item  116  and continues to execute while the work item  116  is being performed. In synchronous enqueuing, a thread  112  delivers a work item  116  and blocks (i.e., suspends execution) while the work item  116  is being performed. Similarly, if the kernel wants to deliver a kernel event  126  via a worker thread  132 , the thread  132  may enqueue the event  126  in a queue  114  until the appropriate thread  112  can dequeue it and use it. In some embodiments, work items  116  and events  126  are assigned one of multiple execution priorities in order to ensure that a particular quality of service (QoS) is achieved when processing the item  116  or event  126 . For example, a time-sensitive work item  116  associated with rendering a user interface may be assigned a higher execution priority than an execution priority of a kernel event  126  indicating that new email is available for retrieval. In such an embodiment, queues  114  may be priority queues that select items  116  and events  126  based on their assigned priorities—giving favoritism to higher priorities. In some embodiments, an application  110  may instantiate a single queue  114 , a collection of queues  114 , or (as discussed below with respect to  FIG. 2 ) a collection of queues  114  arranged in a manner that collectively implement a queue. In some embodiments, queues  114  are operable such that only a single item  116  or event  126  can be enqueued or dequeued at a given time by a thread  112  or  132 . In another embodiment, queues  114  may permit multiple items  116  and events  126  to be enqueued at a given time, but not multiple items  116  and events  126  to be dequeued at a given time. 
     Synchronization primitive  118 A, in various embodiments, is a data structure operable to control access to queues  114  by threads  112  and  132 . In some embodiments, this access control includes ensuring mutual exclusion for threads  112  and  132  dequeuing and potentially executing content of queues  114 . Accordingly, if a worker thread  132  wants to dequeue a work item  116 , it may acquire primitive  118 A in order to ensure that no other thread dequeues the work item  116  and also executes that item  116 . As will be discussed below, if another thread  112  or  132  wants to acquire primitive  118 A, but it is already held by another thread (i.e., primitive  118 A is contented), the other thread may wait if it has a lower execution priority and cause the original holder to be overridden. As used herein, the term “override” refers to elevating the execution priority of the thread holding a primitive in order to expedite its serving of a queue and releasing of a primitive. In some embodiments, however, primitive  118 A does not control access for enqueuing work items  116  or kernel events  126 . In such an embodiment, queues  114  may be operable to support simultaneous enqueuing of work items and/or kernel events  126 . For example, in one embodiment, queues  114  may implement an atomic FIFO queue as discussed in U.S. application Ser. No. 12/477,767. (In other embodiments, however, primitive  118 A may be acquired to enqueue items  116  and/or events  126 .) In some embodiments, primitive  118 A may also be acquired to ensure mutual exclusion of queues  114  when no enqueuing or dequeuing is performed. In some embodiments, instantiation of queues  114  and/or primitive  118 A may be performed by application  110  via an application programming interface (API) accessible to application  110 . 
     As noted above, in various embodiments, synchronization primitive  118 A also stores useful metadata pertaining to the work items  116  and kernel events  126  enqueued in queues  114 —thus primitive  118 A may be said to provide uses other than merely controlling access to queues  114 . As will be discussed below and in greater detail with  FIG. 3 , this metadata may include priority information associated with enqueued items, information about an owner thread or threads waiting to acquire primitive  118 A, etc. As noted above, in some embodiments, at least a portion of this useful metadata may be conveyed to the kernel via one or more system calls  122  as primitive  118 A may not be directly accessible by processes in kernel space  104 . These system calls  122  may be made by an application thread  112  when items  116  are enqueued (e.g., to request a worker thread  132 ) or when events  126  are dequeued. Calls  122  may then be handled, in the illustrated embodiment, by queue manager  120 . 
     Queue manager  120 , in various embodiments, is a set of program instructions that are included in an operating system kernel and are executable to manage queues  114 . (Thus, while various operations may be described herein as being performed by manager  120 , these operations may also be described more generally as being performed by an operating system kernel.) As part of this management, queue manager  120  may receive system calls  122  requesting performance of newly enqueued work items  116  and dispatch threads  132  from thread pool  130  to service those requests. Queue manager  120  may also receive systems calls  122  from an application  110  to register for the reception of particular kernel events  126 . Manager  120  may then dispatch threads  132  from thread pool  130  to deliver those events  126  as events occur in system  10 . In the illustrated embodiment, manager  120  maintains kernel queues  124  to store kernel events  126  for an application  110  until the events  126  can be delivered by dispatched worker threads  132 . For example, if an application  110  has registered to receive a kernel event  126  indicating when a particular file has become available for access, manager  120  may enqueue a kernel event  126  in a queue  124  in response to the kernel determining that the file has become available. Manager  120  may then instruct thread pool  130  to dispatch a worker thread  132  to deliver the event  126 . In some embodiments, kernel queues  124  and kernel events  126  correspond to BSD kqueues and kevents, respectively. 
     Thread pool  130 , in various embodiments, is a collection of worker threads  132  that can be dispatched from kernel space  104  to user space  102  to assist application  110  by performing enqueued work items  116  and delivering kernel events  126  from kernel queues  124 . In some embodiments, thread pool  130  is shared among multiple applications  110 —i.e., a thread  132  may assist one application  110  and later assist another  110 . In other embodiments, thread pool  130  assist only one application  110  and may be one of multiples pools  130 . Threads  132  may be described as “ephemeral threads” as they may move up to user space  102  temporarily before returning to kernel space  104  to prepare for subsequent dispatches. In some embodiments, a thread  132  may be dispatched for some initial purpose (e.g., delivery of an event  126  or performance of an item  116 ), but determine after being dispatched that queues  124  have additional events  126  received in the interim or that queues  114  have received additional work items  116 . In response to making such a determination, a worker thread  132  may remain in user space  102  to deliver these additional events  126  and/or process these additional work items  116 . In various embodiments, threads  132  may be dispatched at higher or lower execution priorities depending on the execution priorities associated work items  116  or kernel events  126 . In some embodiments, queue manager  120  may cause a thread  132  to be dispatched a first execution priority associated with an element  116  or  126  and then cause the execution priority to be changed to a second execution priority if the thread is going process some other element  116  or  126  associated with a different execution priority. 
     As noted above, in various embodiments, queue manager  120  may not be able to directly access primitive  118 A, but may receive information included in primitive  118 A via system calls  122 . To maintain this received information, queue manager  120  may instantiate a data structure (show as synchronization primitive  118 B) corresponding to primitive  118 A and may store the received information in this structure. In some embodiments, primitive  118 B has a one-to-one correspondence to primitive  118 A—accordingly, manager  120  may have multiple primitives  118 B if an application  110  has multiple primitives  118 A. In the illustrated embodiment, primitive  118 B is shown with a dotted line to indicate that primitive  118 B may be maintained temporarily. For example, in some embodiment, manager  120  may delete primitive  118 B if there are no work items  116  currently enqueue in queues  114  and the application  110  has not requested that the kernel detect occurrences of any events. 
     As will be described in greater detail below with respect to  FIG. 3 , synchronization primitive  118 B may store various useful information to facilitate queue manager  120 &#39;s dispatch of threads  132 . Most basically, primitive  118  may indicate, in various embodiments, whether an item is enqueued in a queue  114 . This information may be beneficial as 1) manager  120  does not need to dispatch a thread  132  to read the contents of queues  114  to determine whether something is enqueued and 2) manager  120  is not dispatching a thread  132  when nothing is enqueued in a queue  114 . In some embodiments, primitive  118 B includes an identifier of primitive  118 A, which manager  120  can provide to a dispatched thread  132  to direct it where to go to acquire primitive  118 A and dequeue a work item  116 . In some embodiments, primitive  118 A includes a highest execution priority associated with an enqueued item  116 , which manager  120  may use to determine whether to dispatch a thread  132  and to determine the execution priority at which the thread  132  should be dispatched—thus, manager  120  may not dispatch a lower priority thread  132  to perform a higher priority work item  116 . In some embodiments, primitive  118 B stores an indication of whether a thread  112  currently holds primitive  118 A after synchronously enqueuing a work item  116 . Based on this information, manager  120  may instruct a dispatched thread  132  to unblock the thread  112  after performing the work item  116  or may delay dispatching another thread  132  if it would be at a lower execution priority and unable to override primitive  118 A. In short, use of primitive  118 B in various embodiments may allow the kernel (and more specifically manager  120  in the illustrated embodiment) to have greater insight into what is occurring in user space  102  with respect to queues  114  beyond merely knowing that an application  110  has made a request to dispatch a worker thread  132 . Through having this greater insight, in various embodiments, the kernel can make more intelligent decisions on how to process work items  116  and deliver kernel events  126 . 
     Turning now to  FIG. 2 , a block diagram of a queue tree  200  is depicted. As noted above, in some embodiments, queues  114  are a collection of queues arranged in a manner that also implements a queue. Accordingly, in the illustrated embodiment, this arrangement is depicted as queue tree  200 . As shown in  FIG. 2 , tree  200  may have a base queue  114 A that has an input coupled to the outputs of higher-level queues  114 B and  114 C. These queues  114 B and C may also be coupled to even higher-level queues, such as queue  114 D, and so forth. 
     In various embodiments, different higher-level queues  114  are operable to store different types of content. For example, as shown, queue  114 B may store kernel events  126 , which may be from a specific event source (e.g., another application providing IPCs) or group of sources (e.g., WiFi and cellular network interface cards (NICs) of system  10 ). Queue  114 C may store work items  116 , which are enqueued by one or more threads  112 . Based on the content being stored, in various embodiment, queues  114  may be associated with different execution priorities. For example, as shown, queue  114 C may be a high-priority queue (e.g., because it stores high priority items  116 A from a user-interface thread  112 ), while queue  114 B may be a lower priority queue  114  having lower-priority kernel events  126 A. 
     In such an embodiment, base queue  114 A may be a priority queue operable to select elements to output based on their respective priorities. Accordingly, queue  114 A may cause higher-priority work items  116 A to be dequeued before lower-priority kernel events  126 A. In various embodiments, base queue  114  is a serial queue that enqueues or dequeues one element at a time as controlled by synchronization primitive  118 A. In controlling base queue  114 A in this manner, synchronization primitive  118 A may control access to the entire tree  200 . In some embodiments, primitive  118 A is collocated with base queue  114 A, so that the location of base queue  114 A can easily be determined based on the location of primitive  118 A. 
     Although not depicted, in some embodiments, kernel queues  124  may be arranged in a similar queue tree  200  in which higher priority kernel events  126  are placed into higher priority queues  124  and lower priority kernel events  126  are placed into lower priority queues  124 . 
     Turning now to  FIG. 3 , a block diagram of synchronization primitives  118 A and  118 B is depicted. As noted above, in various embodiments, primitives  118 A and  118 B may store additional information beyond what is used to merely control access to queues  114 . Accordingly, in the illustrated embodiment, synchronization primitive  118 A includes a synchronization primitive identifier  312 , lock  314 , work item list  316 , synchronization waiter list  318 , highest priority  320 , contention flag  322 , and kernel identity flag  324 . Synchronization primitive  118 B includes synchronization primitive identifier  312 , current servicer thread  332 , synchronization owner  334 , event list  336 , synchronization waiter list  318 , and highest priority  320 . Notably, primitive  118 B includes at least a portion of the information included in primitive  118 A. In some embodiments, primitives  118 A and  118 B may include more (or less) elements than shown in  FIG. 3 . 
     Synchronization primitive identifier  312 , in one embodiment, is an identifier that uniquely identifies a particular synchronization primitive  118 A from other primitives  118 A maintained by the same application  110  or other applications  110 . In some embodiments, identifier  312  is an address in memory where the primitive  118 A is located. As noted above and discussed with  FIG. 4B , manager  120  may provide this identifier  312  to a dispatched thread  132  to indicate where thread  132  is to go to acquire primitive  118 A (and also locate base queue  114 A). As shown, this identifier  312  may also be stored in primitive  118 B in order to associate that primitive  118 B (and thus the information that it includes) with its corresponding primitive  118 A. 
     Lock  314 , in one embodiment, is the specific data structure within primitive  118 A that controls access to a collection of queues  114 . This data structure may include a Boolean value indicating whether primitive  118 A is currently held or available for acquisition. In various embodiments, lock  314  may be read by a thread  112  or  132  attempting to acquire primitive  118 A. If primitive  118 A is currently available, the thread  112  or  132  may alter the value of lock  314  to indicate that primitive  118 A is now held while the thread  112  or  132  enqueues or dequeues elements in queues  114 . If primitive  118 A is unavailable, the thread  112  or  132  may add itself to synchronization waiter list  318 . 
     Work item list  316 , in one embodiment, is a list of work times  116  enqueued in queues  114 . In some embodiments, list  316  prioritizes work items  116  based on their respective priorities. In various embodiments, a dispatched thread  132  may read the contents of list  316  to determine metadata about what it is dequeuing. 
     Synchronization waiter list  318 , in one embodiment, is a list of threads  112  or  132  waiting to acquire primitive  118 A. As noted above, threads  112  or  132  may be added to list  318  if they are unable to acquire primitive  118 A. After a thread  112  or  132  has released primitive  118 A, it may examine list  318  to determine who should be contacted to indicate that primitive  118 A is available for acquisition. In some embodiments, list  318  indicates a respective execution priority associated with each listed thread  112  or  132 . In such an embodiment, the releasing thread  112  or  132  may notify the highest priority thread that primitive  118 A is available for acquisition. 
     Highest priority  320 , in one embodiment, indicates the highest execution priority of any element enqueued in a collection of queues  114 . In some embodiments, manager  120  may examine the copy of priority  320  in primitive  118 B to determine the appropriate execution priority for a thread  132  being dispatched. In some embodiments, a thread  112  enqueuing a work item  116  may examine priority  320  and compare the value of priority  320  with the propriety of the work item  116  being enqueued to determine whether to issue another request for a higher-priority thread  132  because the item  116  being enqueued has a higher priority. In some embodiments, the thread  112  may also determine to not issue a thread request if a previous request was just issued for another pending work item  116  having the same priority (or a lower priority). In some embodiments, priority  320  may be set to a particular value (e.g., −1) if nothing is enqueued to indicate that queues  114  are empty. 
     Contention flag  322 , in one embodiment, indicates whether primitive  118 A is contended—i.e., one or more threads  112  or  132  are trying to acquire primitive  118 A while it is currently held by another thread  112  or  132 . In various embodiments, flag  322  may be set if list  318  is not empty in order to cause a thread  112  or  132  releasing primitive  118 A to examine list  318 . 
     Kernel identity flag  324 , in one embodiment, indicates whether a corresponding synchronization primitive  118 B has been instantiated by manager  120  in kernel space  104 . 
     Current servicer thread  332 , in one embodiment, identifies the current thread  132  (or threads  132 ) dispatched to deliver events  126  and/or perform work items  116 . In some embodiment, manager  120  may examine this value  332  to determine whether a thread  132  has already been dispatched (and thus whether to dispatch another thread  132 ). In some embodiments, this value  332  may also indicate the execution priority at which the thread  132  was dispatched. Accordingly, manager  120  may also determine from this value  332  whether a higher priority thread  132  should be dispatched to service a newly received, higher priority work item  116  or event  126 . 
     Synchronization owner thread  334 , in one embodiment, identifies a thread  112  that has enqueued a work item  116  synchronously and still holds/owns primitive  118 A. Manager  120  may use this value to determine whether to instruct a thread  132  to unblock an owner thread  112 . In some embodiments, this value  334  may also indicate the priority of the owner thread—thus, manager  120  may determine to not issue a thread  132  for some other task if the thread  132  would be at a lower priority and would be unable to override primitive  118 A. 
     Event list  336 , in one embodiment, is a list of kernel events  126  in kernel queues  124 . In some embodiments, list  336  prioritizes kernel events  126  based on their respective priorities. In various embodiments, manager  120  may read list  336  to determine the execution priority for a thread  132  being dispatched to deliver an event  126 ; a dispatched thread  132  may read the contents of list  336  to determine what events  126  to deliver to queues  114 . 
     In some embodiments, the primitive  118 B may be maintained by a synchronization primitive manager included in queue manager  120  and discussed next with respect to  FIGS. 4A and 4B . As the values  312 - 336  of primitives  118 A and  118 B are altered they may correspond to various states in finite state machines discussed below with respect to  FIGS. 5A and 5B . 
     Turning now to  FIG. 4A , a block diagram of a synchronization primitive manager  400  is depicted. In some embodiments, queue manager  120  may include multiple synchronization primitive managers  400 , which each maintain a respect primitive  118 B. Thus, while various actions may be described herein by manager  400 , these actions may be more generally described as being performed by queue manager  120  or the kernel including manager  120 . In the illustrated embodiment, manager  400  services a registration request  402 . Additional system calls are discussed below with respect to  FIG. 4B . 
     As noted above, an application  110  may submit requests (shown as kernel-event registration request  402 ) to register for receiving kernel events  126  responsive to the occurrences of particular events. For example, an application may issue request  402  to be receive a kernel event  126  indicating when traffic on a particular TCP/IP port is received. In response to receiving a request  402 , manager  400  may instantiate one or more filters  410  that are executable to monitor particular event sources  404  for the registered events and enqueue kernel events  126  in kernel queues  124  for subsequent delivery. For example, manager  400  may create a filter that monitors a NIC. In response to detecting traffic associated with the particular TCP/IP port, the filter  410  may provide information about the detection for inclusion in a kernel event  126 . In some embodiments, a request  402  and a filter  410  may correspond to a BSD function call to kevent( ) and a knote, respectively. 
     Turning now to  FIG. 4B , another block diagram of synchronization primitive manager  400  is depicted. In the illustrated embodiment, manager  400  services thread requests  414 . 
     As noted above, once a thread  112  has enqueued a work item  116 , thread  112  may issue a request (shown as a thread request  414 ) to have a thread  132  dispatched to operate on the work item  116 . In some embodiments, this request  414  may include any of the content discussed above with respect to primitive  118 A such as an identifier  312 , list  318 , and priority  320 . In response to the receiving a request  414 , manager  400  may update primitive  118 B based on the included information (or instantiate primitive  118 B if it does not currently exist) and determine whether to dispatch a thread  132  responsive to the request  414 . As noted above, this determination may be based on whether a previous thread  132  has already been dispatched to service another work item  116  or deliver an event  126 , the priority of the new work item  116 , the availability of threads  132  in thread pool  130 , etc. 
     If manager  400  does determine to dispatch a thread  132 , manager  400  may issue a request  422  to the thread pool  130  to cause a thread  132  to be dispatched. In the illustrated embodiment, this request  422  includes the identifier  312  of the primitive  118 A associated with the queue  114  including the item  116 , a list  336  of any events  126  to be delivered, a list  318  of any waiting threads  112  to be unblocked responsive to primitive  118 A becoming available, and the priority  320  at which the thread  132  is to execute. In some embodiments, request  422  may include more (or less) information—e.g., a request  422  may include multiple identifiers  312  to cause a thread  132  to service multiple queues  114  associated with different primitives  118 A of an application  110 . In some embodiments, however, a dispatch request  422  may not include the kernel events  126  being delivered; rather, as shown in the illustrated, a worker thread  132  may issue a request  432  once it is in user space  102  to have events  126  provided from queues  124  for delivery to application  110 . (Although not depicted, in various embodiments, manager  400  issues similar requests to requests  422  for delivering kernel events  126  when no work items  116  are enqueued.) 
     Turning now to  FIG. 5A , a block diagram of a finite state machine (FSM)  500 A associated with user-space synchronization primitive  118 A is depicted. FSM  500 A is one embodiment of an FSM having various states  510 - 540  associated with the processing of work items  116 . In some embodiments, FSM  500 A may include more (or less) states than shown. 
     Idle or suspended state  510 , in one embodiment, is an initial state in which no work items  116  or kernel events  126  are enqueued in queues  114 . If a thread  112  asynchronously enqueues a work item  116 , FSM  500 A may transition to state  530  causing the awakening of a manager  400  to dispatch a thread  132 . If, however, the thread  112  is synchronously enqueuing a work item  116 , FSM  500 A proceeds to state  520 . Notably, this transition does not trigger a system call  122  in the illustrated embodiment as shown in  FIG. 5A . In some embodiments, the transition from state  510  to state  530  (or state  520  to state  530 ) may cause the instantiation of primitive  118 B. 
     Uncontended synchronous owner state  520 , in one embodiment, is a state in which a thread  112  has obtained ownership of primitive  118 A in order to obtain mutual exclusion of queues  114  when there is not already an owner of primitive  118 A. For example, a thread  112  may acquire primitive  118 A for various reasons in order to prevent other threads from dequeuing items  116  and/or events  126 . If the thread releases the primitive  118 A and there are enqueued asynchronous work items  116 , FSM  500 A transitions to state  530  causing manager  400  to be awoken to dispatch a thread  132 , which can now acquire primitive  118 A. If, however, another thread  112  attempts to acquire primitive  118 A while primitive  118 A is still being held, FSM  500 A proceeds to state  540 . 
     Asynchronous draining state  530 , in one embodiment, is a state in which a thread  132  has been dispatched to user space  102  and is dequeuing work items  116  for processing. If the work items  116  are successfully performed, FSM  500 A may return back to state  510  causing manager  400  to quiescent. If another thread attempts to acquire primitive  118 A (i.e., primitive  118 A becomes contented), the original thread owner may be overridden until ownership can be handed off when FSM  500 A transitions to state  540 . 
     Contended synchronous owner state  540 , in one embodiment, is a state in which one or more threads  112  have attempted to acquire primitive  118 A while it is held by another thread  112  or  132 . As noted above, if the thread  112  or  132  attempting to acquire primitive  118 A is a higher-priority thread, the original thread holding primitive  118 A may be overridden to expedite handing off of ownership to the new thread requesting ownership. While waiting in state  540 , one or more additional threads  112  may attempt to obtain the primitive  118 A causing additional overrides and additional threads  112  being added to waiter list  318 . 
     Turning now to  FIG. 5B , a block diagram of a finite state machine (FSM)  500 B for kernel-space synchronization primitive  118 B is depicted. FSM  500 B is one embodiment of an FSM having various states  550 - 590  associated with the delivery of kernel events  126 . In some embodiments, FSM  500 B may include more (or less) states than shown. 
     FSM  500 B may begin at state  550 A in which an application  110  has yet to send a kernel-event registration request  402  asking for the monitoring of an event. In response to a request  402  being issued, manager  400  may add a filter  410  causing FSM  500 B to transition to state  550 B in which one or more filters  410  are analyzing event sources  404 . If the filters  410  are deleted, FSM  500 B returns to state  550 A. If a filter  410  detects an event or a thread request  414  is received, FSM  500 B transitions to state  560 . 
     State  560 , in one embodiment, is a state in which a thread  132  has been dispatched to user space  102 , but has yet to start delivery of kernel events  126 . While at state  560 , one or more additional filters  410  may detect events and have kernel events  126  enqueued in kernel queues  124 . In response to the thread  132  issuing a kernel-event request  432  and receiving kernel events  126  to be delivered, FSM  500 B may transition to state  570 . 
     State  570 , in one embodiment, is a state in which a dispatched thread  132  attempts to enqueue received kernel events  126  in queues  114 . At the end of enqueuing events  126 , the thread  132  may attempt to acquire primitive  118 A in order to begin executing enqueued work items  116 . If primitive  118 A cannot be acquired to start dequeuing items  116 , the thread  132  may issue, to manager  120 , a negative acknowledgment (Nack) indicating that the transition to state  580  failed, causing FSM  500 B to transition to state  590 . If the thread  132  is able to acquire the primitive  118 A, the thread  132  may issue, to manager  400 , an acknowledgement (Ack) to indicate successful delivery, causing FSM  500 B to transition to state  580 . While at state  570 , one or more filters  410  may detect events. 
     State  580 , in one embodiment, is a state in which a thread  132  has delivered kernel events  126  and has now transitioned to dequeuing work items  116 /draining queues  114  to perform the work items  116 . Once one work item  116  has been completed, thread  132  may return to queues  114  for a next item  116 . While at state  580 , one or more filters may detect events, and thread  132  may ask for those events  126  to deliver them. A thread  112  may also issue another registration request  402  to monitor for new events. If a thread  132  has successfully completed each item  116  and delivered each event  126 , thread  132  may return to pool  130  in kernel space  104 , causing FSM  500 B to return to state  550 B. If, however, a higher priority thread  112  or  132  acquires the primitive  118 A (e.g., because a higher priority thread synchronously acquired the primitive before the dispatched thread managed to do so), FSM  500 B transitions to state  590 . 
     State  590 , in one embodiment, is a state in which the dispatched thread  132  has blocked (or returned to thread pool  130 ) because it does not have the ability to acquire primitive  118 A and dequeue items  116  because primitive  118 A is contended. FSM  500 B may transition to state  560  if the primitive  118 A becomes available to the blocked thread  132 . 
     Turning now to  FIG. 6A , a flow diagram of a method  600  is depicted. Method  660  is one embodiment of a method that may be performed by an application executing on a computer system such as application  110 . In many instances, performance of method  600  may allow an application to more efficiently perform work items via a thread pool than relying solely on application-spawned threads. 
     In step  605 , an application instantiates a queue (e.g., a queue  114 ) and a synchronization primitive (e.g., primitive  118 A). The queue maintains a set of work items (e.g., items  116 ) to be operated on by a thread pool (e.g., pool  130 ) maintained by a kernel (e.g., a kernel including queue manager  120 ). The synchronization primitive controls access to the queue by a plurality of threads (e.g., threads  112  and  132 ) including threads of the thread pool. In some embodiments, an input of the queue is operable to receive work items from a plurality of queues associated with different execution priorities (e.g., queues  114 B and  114 C passing items to queue  114 A), and the queue is a priority queue operable to select ones of the received work items based on the different execution priorities. 
     In step  610 , the first thread enqueues a first work item in the queue. In some embodiments, the first thread enqueues the first work item without acquiring the synchronization primitive. In some embodiments, step  610  includes the first thread storing an execution priority of the first work item in the synchronization primitive. In various embodiments, the synchronization primitive stores metadata (e.g., elements  312 - 324 ) about work items enqueued in the queue, and the kernel is executable to instantiate a data structure (e.g., primitive  118 B) that is accessible to the kernel and that stores, at least, a portion of the metadata (e.g., elements  312 ,  318 , and  320 ) including the stored execution priority. 
     In step  615 , the first thread issues a system call (e.g., thread request  414 ) to the kernel to request that the kernel dispatch a thread (e.g., a thread  132 ) of the thread pool to operate on the first work item. In various embodiments, the dispatched thread is executable to acquire the synchronization primitive, dequeue the first work item from the queue, and operate on the first work item. In some embodiments, the first thread sends an identifier of the synchronization primitive (e.g., identifier  312 ) to the kernel, which is executable to convey (e.g., via dispatch request  422 ) the identifier to the dispatched thread to cause the dispatched thread to acquire the synchronization primitive controlling access to the queue and to dequeue the first work item from the queue. In some embodiments, the first thread sends, via the system call, an execution priority (e.g., priority  320 ) associated with the first work item to the kernel, and the kernel is executable to dispatch the dispatched thread at the execution priority. 
     In some embodiments, method  600  further includes the application sending, to the kernel, a request (e.g., a registration request  402 ) to receive a notification about an occurrence of an event, the kernel being executable to detect the occurrence of the event and to provide the notification (e.g., a kernel event  126 ) to the dispatched thread to cause the dispatched thread to store the notification in the queue. In such an embodiment, a thread of the application retrieves the notification from the queue. In some embodiments, method  600  includes a second thread of the application enqueuing a second work item in the queue, comparing the stored execution priority with an execution priority associated with the second item, and determining, based on the comparing, whether to issue a system call to the kernel to request that the kernel dispatch another thread of the thread pool to operate on the second work item. 
     Turning now to  FIG. 6B , a flow diagram of a method  630  is depicted. Method  630  is one embodiment of a method that may be performed by a kernel such as a kernel including queue manager  120 . In many instances, performance of method  630  may allow a kernel to more efficiently manage performance of work items via a thread pool. 
     In step  635 , a kernel maintains a thread pool (e.g., thread pool  130 ) having a plurality of threads (e.g., threads  132 ) executable to operate on work items (e.g., work items  116 ) supplied by a plurality of applications. 
     In step  640 , the kernel receives a first system call (e.g., a thread request  414 ) indicating that a first of the plurality of applications has enqueued a first work item into a queue (e.g., a queue  114 ) associated with the first application. In some embodiments, the kernel, in response to the first system call, instantiates a data structure (e.g., primitive  118 B) corresponding to the synchronization primitive. In some embodiments, the kernel stores, in the data structure, a priority (e.g., a priority  320 ) associated with the first work item. In some embodiments, the first system call indicates that a thread of the application has acquired the synchronization primitive and blocked awaiting performance of the first work item. 
     In step  645 , the kernel provides one of the plurality of threads from the thread pool to perform the enqueued first work item, the thread being executable to acquire a synchronization primitive (e.g., primitive  118 A) controlling access to the queue prior to dequeuing the first work item and performing the first work item. In some embodiments, the kernel stores an indication (e.g., current servicer thread  332 ) that the thread has been provided to perform the first work item. In such an embodiment, method  630  may include the kernel receiving a second system call indicating that the first application has enqueued a second work item in the queue and, based on the stored indication, determining whether to provide another thread from the thread pool to perform the second item. In some embodiments, the indication is stored in the data structure instantiated in step  640 , and the data structure further includes an address (e.g., identifier  312 ) of the synchronization primitive. In such an embodiment, the kernel conveys the address to the provided thread to direct the provided thread to dequeue the first work item from the queue. In some embodiments, the determining whether to provide the other thread is based on the stored priority in step  640 . In some embodiments, the kernel instructing the provided thread to unblock the thread of the application in response to performing the first work item. 
     In some embodiments, method  630  includes, prior to providing the thread from the thread pool, the kernel receiving a request to deliver a message to the first application, the message being associated with a priority that is higher than a priority of the first work item, and the kernel providing another thread from the thread pool. In such an embodiment, the other thread is executable to override the synchronization primitive and enqueue the message in the queue. In various embodiments, method  630  includes the kernel receiving, from the first application, a request to be notified in response to an occurrence of an event, and the kernel, in response to determining that the event has occurred, providing another thread from the thread pool to enqueue a notification (e.g., kernel event  126 ) for the occurrence of the event in the queue. In some embodiments, the queue (e.g., queue tree) comprises a plurality of queues (e.g., queues  114 A-C) including a first queue operable to store the first work item and a second queue operable to store the notification of the event. 
     Turning now to  FIG. 6C , a flow diagram of a method  660  is depicted. Method  660  is one embodiment of a method that may be performed by a kernel such as a kernel including queue manager  120 . In many instances, performance of method  630  may allow a kernel to more efficiently provide notifications to an application. 
     Method  660  begins in step  665  with a kernel receiving, from a first application (e.g., application  110 ), a request (e.g., a registration request  402 ) to be notified in response to an occurrence of an event. In step  670 , the kernel detects that the event has occurred (e.g., via a filter  410 ). In step  675 , the kernel dispatches, from a thread pool (e.g., pool  130 ), a first thread (e.g., thread  132 ) executable to store a notification (e.g., kernel event  126 ) of the occurrence of the event in one of a plurality of queues (e.g., queues  114 ) associated with the first application. In various embodiments, a thread (e.g., thread  112 ) of the application is executable to retrieve the notification from the queue by acquiring a synchronization primitive (e.g., primitive  118 A) that controls access to the plurality of queues. 
     In some embodiments, method  660  includes the kernel receiving, from the first application, a system call (e.g., a thread request  414 ) indicating that a thread of the first application has enqueued a work item in one of the plurality of queues. Method  660  further includes the kernel dispatching a second thread from the thread pool, the second thread being executable to acquire the synchronization primitive that controls access to the plurality of queues, retrieve the work item from one of the plurality of queues, and perform the work item for the first application. In some embodiments, the first thread is the second thread. In some embodiments, method  660  includes the kernel receiving a request to deliver a message from a second application to the first application. Method  660  further includes the kernel dispatching, from the thread pool, a second thread executable to store the message in one of the plurality of queues such that a thread of the application is executable to retrieve the stored message. 
     Exemplary Computer System 
     Turning now to  FIG. 7 , a block diagram of an exemplary computer system  700  is depicted. Computer system  700  is one embodiment of a computer system that may be used to implement computer system  10 . In the illustrated embodiment, computer system  700  includes a processor subsystem  720  that is coupled to a system memory  740  and I/O interfaces(s)  760  via an interconnect  780  (e.g., a system bus). I/O interface(s)  760  is coupled to one or more I/O devices  770 . Computer system  700  may be any of various types of devices, including, but not limited to, a server system, personal computer system, network computer, an embedded system, etc. Although a single computer system  700  is shown in  FIG. 7  for convenience, system  700  may also be implemented as two or more computer systems operating together. 
     Processor subsystem  720  may include one or more processors or processing units configured to execute program instructions to perform functionality described herein. In various embodiments of computer system  700 , multiple instances of processor subsystem  720  may be coupled to interconnect  780 . In various embodiments, processor subsystem  720  (or each processor unit within  720 ) may contain a cache or other form of on-board memory. 
     System memory  740  is usable store program instructions executable by processor subsystem  720  to cause system  700  perform various operations described herein. For example, memory  740  more store program instructions to implement application  110 , queue manager  120 , and/or thread pool  130 . System memory  740  may be implemented using different physical, non-transitory memory media, such as hard disk storage, floppy disk storage, removable disk storage, flash memory, random access memory (RAM—SRAM, EDO RAM, SDRAM, DDR SDRAM, RAMBUS RAM, etc.), read only memory (PROM, EEPROM, etc.), and so on. Memory in computer system  700  is not limited to primary storage such as memory  740 . Rather, computer system  700  may also include other forms of storage such as cache memory in processor subsystem  720  and secondary storage on I/O Devices  770  (e.g., a hard drive, storage array, etc.). In some embodiments, these other forms of storage may also store program instructions executable by processor subsystem  720  to perform operations described herein. 
     I/O interfaces  760  may be any of various types of interfaces configured to couple to and communicate with other devices, according to various embodiments. In one embodiment, I/O interface  760  is a bridge chip (e.g., Southbridge) from a front-side to one or more back-side buses. I/O interfaces  760  may be coupled to one or more I/O devices  770  via one or more corresponding buses or other interfaces. Examples of I/O devices  770  include storage devices (hard drive, optical drive, removable flash drive, storage array, SAN, or their associated controller), network interface devices (e.g., to a local or wide-area network), or other devices (e.g., graphics, user interface devices, etc.). In one embodiment, computer system  700  is coupled to a network via a network interface device  770  (e.g., configured to communicate over WiFi, Bluetooth, Ethernet, etc.). 
     Although specific embodiments have been described above, these embodiments are not intended to limit the scope of the present disclosure, even where only a single embodiment is described with respect to a particular feature. Examples of features provided in the disclosure are intended to be illustrative rather than restrictive unless stated otherwise. The above description is intended to cover such alternatives, modifications, and equivalents as would be apparent to a person skilled in the art having the benefit of this disclosure. 
     The scope of the present disclosure includes any feature or combination of features disclosed herein (either explicitly or implicitly), or any generalization thereof, whether or not it mitigates any or all of the problems addressed herein. Accordingly, new claims may be formulated during prosecution of this application (or an application claiming priority thereto) to any such combination of features. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the appended claims.