Managing timers in a multiprocessor environment

Timers are managed in a multiprocessing environment. Some timers are local to a given logical processor; such a local timer is inserted on and will be canceled only from that logical processor. Other timers are global to a logical processor. A global timer which was inserted on a given logical processor may be canceled from that logical processor or from another logical processor. Global timers are serviced in response to expiration of an associated local timer.

BACKGROUND

Multiprocessor environments have been designed in various configurations. In a given configuration, all of the processors may be functionally equal, whereas in another configuration some processors may differ from other processors by virtue of having different hardware capabilities, different software assignments, or both. Depending on the configuration, processors may be tightly coupled to each other on a single bus, or they may be loosely coupled. In some configurations the processors share a central memory, in some they each have their own local memory, and in some configurations both shared and local memories are present.

Within a multiprocessor environment, a given process may need some ability to determine or measure time. Time measurement can be useful in a process that executes at a low level near the hardware, and in a process that executes at a higher level. Timers can be used for various purposes, such as calculating an elapsed time, yielding control to share a processor among different processes, or creating a timestamp, to name a few.

Hardware components used for timing may include one or more Advanced Configuration and Power Interface timers, Advanced Programmable Interrupt Controller timers, and other counters, clocks, timers, and/or interrupt generators. Software uses such hardware components to help provide timing services within a given system.

SUMMARY

In some embodiments, a distinction is made between local timers and global timers. A local timer is associated with one logical processor. For example, a local timer which was inserted to run on a particular logical processor will be canceled from that same logical processor. A global timer may be associated with a virtual processor, and a global timer therefore may run on different logical processors at different times. For example, a global timer which was inserted on a particular logical processor may be canceled either from that logical processor or from another logical processor.

In some embodiments, global timers are synchronized with locks to prevent race conditions, whereas local timers are lockless to reduce overhead.

In some embodiments, global timers are associated with a dedicated local timer. The expiration time of the dedicated local timer is set to the earliest expiration time specified for any of the associated global timers. The global timers are tested for expiration only if their dedicated local timer expires. Accordingly, global timer synchronization overhead may be reduced by using a dedicated local timer to reduce tests for global timer expiration.

The examples given are merely illustrative. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. Rather, this Summary is provided to introduce—in a simplified form—some concepts that are further described below in the Detailed Description. The innovation is defined with claims, and to the extent this Summary conflicts with the claims, the claims should prevail.

DETAILED DESCRIPTION

Overview

Local timers and global timers are defined and managed in a multiprocessing environment. Local timers are local to a given logical processor. For example, a local timer may be used only within a hypervisor and be hidden from virtual machines that are hosted by the hypervisor. By contrast, a global timer may be created at the request of a virtual processor that is running in a virtual machine, and the global timer therefore travels with the virtual processor as it runs on different logical processors at different times. Synchronization, and hence the overhead of managing synchronization locks, may be required for global timers but not be required for local timers. If local timers are set more frequently than global timers, then keeping local timers lockless reduces synchronization overhead.

To further reduce synchronization overhead, global timers can be associated with a dedicated local timer. The expiration time of the dedicated local timer is set to the earliest expiration time specified for any of the associated global timers. The global timers are then tested for expiration only if their dedicated local timer expires. Thus, overhead is reduced by avoiding some of the tests for global timer expiration that would be performed if a dedicated local timer was not used. Locking operations while handling timer expiration are needed only when a dedicated local timer expires during a given hypervisor execution interval. During other hypervisor execution intervals, regular local timers (timers that are not dedicated to handling global timers) can be serviced without using locks.

Reference will now be made to exemplary embodiments such as those illustrated in the drawings, and specific language will be used herein to describe the same. But alterations and further modifications of the features illustrated herein, and additional applications of the principles illustrated herein, which would occur to one skilled in the relevant art(s) and having possession of this disclosure, should be considered within the scope of the claims.

As used herein, a “multiprocessing computer system” may include, for example, one or more servers, motherboards, processing nodes, personal computers (portable or not), personal digital assistants, cell or mobile phones, and/or device(s) providing a plurality of processors controlled at least in part by instructions. The instructions may be in the form of software in memory and/or specialized circuitry. In particular, although it may occur that many embodiments run on server computers, other embodiments may run on other computing devices, and any one or more such devices may be part of a given embodiment.

As used herein, a “logical processor” is a single independent hardware thread. For example a hyperthreaded quad core chip running two threads per core has eight logical processors. A “virtual processor” is a processing unit within a virtual machine. In some cases a virtual processor is mapped in a fixed manner to one particular logical processor throughout execution of an application program and/or other software. In other cases, however, a virtual processor may be mapped dynamically during execution to multiple different logical processors, one at a time.

As used herein, “timer” should be read in context because it may refer to a local timer, a global timer, or both. A “local timer” for a logical processor is always inserted on and canceled from that logical processor. A “global timer” may be canceled from a different logical processor than the logical processor on which the global timer was originally inserted. Unless indicated otherwise, both local and global timers are meant when “timer” is used without “local” or “global” as a qualifier. It will also be understood that in one context “timer” can refer to a timer considered as a whole, whereas in another context “timer” can refer to a part of a timer implementation, such as a timer data structure or a function call to create a timer. A “timer component” is a software component that contains timers for multiple logical processors.

As used herein, a “hypervisor” is a software platform which supports multiple virtual machines. For example, a hypervisor may be used to run several operating systems at the same time on a host computer.

As used herein, a “list” of items is a structure (however implemented) that includes at least one such item, and other types of items are not necessarily excluded. For instance, a “list of local timers” includes at least one local timer. Likewise, a list containing at least one local timer continues to be a “list of local timers” even if an item that is not a local timer is added to the list.

As used herein, terms referring to data structures are only as specific as their express qualifiers. For example, without further qualification, the term “list” includes both linked lists and lists implemented using an array. “Links” includes pointers and/or handles. “Linked list” includes both singly linked lists and doubly linked lists. “Doubly linked list” includes both circular doubly linked lists and other doubly linked lists. Also, whenever reference is made to a data structure, it is understood that the data structure configures a computer-readable memory, as opposed to simply existing on paper, in a programmer's mind, or as a transitory signal on a wire, for example.

Operating Environments

With reference toFIG. 1, an operating environment100for an embodiment may include, for instance, a multiprocessing computer system102. Human users104may interact with the multiprocessing computer system102by using screens, keyboards, and other peripheral equipment106. Storage devices and/or networking devices may be considered peripheral equipment106in some embodiments. Other computer systems (not shown), which may themselves be multiprocessors or not, may interact with the multiprocessing computer system102by using one or more network connections via network interface equipment108.

The multiprocessing computer system102includes at least two logical processors110. The multiprocessing computer system102also includes one or more memories112. The memories112may be volatile, non-volatile, fixed in place, removable, magnetic, optical, and/or of other types. In particular, a configured medium114such as a CD, DVD, memory stick, or other removable non-volatile memory medium may become functionally part of the multiprocessing computer system102when inserted or otherwise installed, making its content accessible for use by processors110. The removable configured medium114is an example of a memory112. Other examples of memory112include built-in RAM, ROM, hard disks, and other storage devices which are not readily removable by users104.

The medium114is configured with instructions116that are executable by a processor110. The medium114is also configured with data118(possibly including data structures) which is created, modified, referenced, and/or otherwise used by execution of the instructions116. The instructions116and the data118configure the memory112/medium114in which they reside; when that memory is a functional part of a given computer system102, the instructions116and data118also configure that computer system102. For clarity of illustration, memories112are shown in a single block inFIG. 1, but it will be understood that memories may be of different physical types, and that a virtual environment120and other items shown in the Figures may reside partially or entirely within one or more memories112, thereby configuring those memories.

A plurality of virtual environments120configure the memory(ies)112of the illustrated computer system102. Each virtual environment120may include, for example, one or more application programs122which run on top of an operating system124, which runs in turn on top of a virtual machine126. Different application programs122and/or different operating systems124may run in different virtual environments120. Different virtual machines126may also be running in different virtual environments120.

A hypervisor128runs in between the virtual machines126and a raw hardware130layer. The hypervisor includes at least one timer component132. The hypervisor128also includes other components134, such as a scheduler that assigns processors110to tasks/threads/processes/etc. In some embodiments the virtual machines126are considered part of the hypervisor128. One suitable hypervisor128is the Microsoft® Hyper-V™ hypervisor (marks of Microsoft Corporation), but embodiments are not limited to articles, methods, or systems involving the Hyper-V™ hypervisor.

Hardware130in a hardware layer includes processors110, memories112, interrupt sources136, and other hardware138. Interrupt sources136may include Advanced Configuration and Power Interface timers, Advanced Programmable Interrupt Controller timers, and other counters, clocks, timers, and/or interrupt generators. Other hardware138may include controllers, converters, power sources, graphics engines, and I/O devices, for example.

FIG. 2shows an alternative operating environment200. Unlike the first operating environment100, this alternative operating environment200includes a multiprocessor operating system202running on the hardware130, instead of a hypervisor128. Like operating systems124, the multiprocessor operating system202provides a platform for application programs122, and perhaps even for some of the same application programs122that run elsewhere in a virtual environment120. Unlike the first operating environment100, however, this alternative operating environment200has only one operating system, so all application programs122running in operating environment200must be compatible with the multiprocessor operating system202.

Like the hypervisor128, the multiprocessor operating system202includes a timer component132. The timer component132in the multiprocessor operating system202does not necessarily provide the same functionality in the same way as the timer component132in the hypervisor. Similarly, the multiprocessor operating system202includes a scheduler and other components134, albeit not necessarily the exact same components134as in the hypervisor.

In a given operating environment, the multiprocessing computer system may run any operating system124and/or any multiprocessor operating system202having a timer component132as taught herein, and may use any network interface equipment108, now known or hereafter formed. An operating environment may include one or more multiprocessing computer systems that are clustered, client-server networked, and/or peer-to-peer networked. Some operating environments include a stand-alone (non-networked) multiprocessing computer system.

Systems

Referring now toFIGS. 1 through 3, some embodiments include a computer system configured for multiprocessing, such as a multiprocessing computer system102running virtual machines126, or a multiprocessing computer system with hardware130running a multiprocessor operating system202. Such a multiprocessing computer system includes at least one memory112configured with executable instructions116, and a plurality of logical processors110which manage timers300when executing at least a portion of the instructions.

In particular, some embodiments include at least one local timer302, which is characterized as local to a logical processor110in that, by execution of instructions116, the local timer302was inserted on and will be canceled from that logical processor110. Some embodiments include at least one global timer304, which is characterized as global to a logical processor110in that the global timer304was inserted by instructions running on that logical processor110and may be canceled by instructions running on that logical processor or by instructions running on another logical processor.

In some embodiments, the multiprocessing computer system is further characterized in that the global timer304is serviced by execution of the instructions116in response to expiration of a local timer302. Depending on the embodiment, servicing a global timer may include operations such as checking to see whether the global timer has expired, positioning the global timer in a list or other arrangement of timers, sending a signal if the global timer has expired, invoking a callback routine if the global timer has expired, and/or programming a hardware interrupt source136based at least in part on an expiration time stated in the global timer.

Some embodiments include a configured computer-readable storage medium114, which is an example of a memory112. In a multiprocessing environment, memory112may include disks (magnetic, optical, or otherwise), RAM, EEPROMS or other ROMs, and/or other configurable memory. A general-purpose memory112, which may be removable or not, and may be volatile or not, is configured with data structures and data118and instructions116, from a removable medium114and/or another source such as a network connection, to thereby form a configured medium in the form of configured memory112which is capable of causing a multiprocessing system to perform timer management steps and provide timer functionality disclosed herein.FIGS. 1 through 3thus help illustrate configured storage media embodiments, as well as system embodiments and method embodiments.

In some embodiments, peripheral equipment106such as human user I/O devices (screen, keyboard, mouse, microphone, speaker, motion sensor, etc.) will be present in operable communication with one or more processors110and memory112. However, an embodiment may also be deeply embedded in a system, such that no human user104interacts directly with the embodiment.

In some embodiments, networking interface equipment108such as a packet-switched network interface card, a wireless transceiver, or a telephone network interface, for example, will be present in the multiprocessing system. However, an embodiment may also communicate through direct memory access, removable nonvolatile media, or other information storage-retrieval and/or transmission approaches, or an embodiment in a computer system may operate without communicating with other computer systems.

In some embodiments, the multiprocessing computer system includes a hypervisor128. Instructions for managing timers300, such as instructions116which insert local timers302on a logical processor110and instructions116which cancel local timers302from a logical processor110, are located within the hypervisor128, in a timer component132.

The instructions116may include a timer API306, such as a procedure that can be called by an operating system124to create a global timer304, and a procedure the operating system can call to cancel a specified global timer304. In some embodiments, the API is part of a timer component. In some, the API is outside the timer component but calls on the timer component to create a global timer. Timers may be specified in the API306by text strings, handles, GUIDS, pointers, and/or other identifiers. The timer API306may provide various capabilities for timers associated with a given process/thread/task and/or with a given logical processor, such as single-shot global timers304, modulated periodic global timers304, lazy periodic global timers304, global timers304that send a signal on expiration, and global timers304that invoke on expiration a callback routine identified by the timer API caller.

In one embodiment, all instructions that directly access local timers302are hidden from the hosted operating systems124. That is, local timers302are accessed only by the hypervisor128code, and only global timers304can be created or identified in a public procedure of the timer API306.

In some embodiments, a global timer304includes a callback routine to be invoked if the global timer expires. The callback routine may be identified by a memory pointer, an index, a handle, or another routine identifier.

One embodiment includes a hypervisor128which executes instructions116on the logical processors110, and a plurality of operating systems124, each of which executes instructions on at least one logical processor110. The hypervisor128includes one or more instructions which disable interrupts after the hypervisor receives control from an operating system. The hypervisor128also includes at least one instruction116to service a timer by programming a hardware interrupt source136before passing control back up to an operating system124. In some embodiments, interrupt disabling and/or interrupt enabling are performed by hypervisor code located outside the timer component.

In general, interrupts may be caused by I/O devices, timers, special memory accesses, and/or other sources. In one embodiment, at least some interrupts are disabled inside the hypervisor128. As a result, the hypervisor code need not handle the case in which a timer interrupt occurs during handling of a timer interrupt. If an interrupt occurs during hypervisor execution, the interrupt is undetected until control returns up to the operating system124level. The time spent within the hypervisor is kept short, e.g., less than one hundred microseconds, before control is passed back up to the operating system124level. From the operating system124level, the hypervisor128looks like hardware, at least with regard to operating speeds. In one embodiment, locks to control access to local timers302are not used within the hypervisor128. Avoiding interrupts and locks within the hypervisor128may increase hypervisor scalability with respect to the number of logical processors110present in a system.

In one embodiment, there is no periodic time tick within the hypervisor128, but a fine grained passage of time is achieved by letting the hypervisor execute only for a short while before passing control back to the operating system124level. Shortness of time may be defined in terms of real time, e.g., a time less than one hundred microseconds is an example of a short time. Shortness may also be defined pragmatically, e.g., a length of time less than the average response time of any attached peripheral device106is considered short. On leaving the hypervisor128, a hardware interrupt is programmed to bring control back to the hypervisor and then interrupts are enabled before control is passed back to the virtual machine.

In one embodiment, the multiprocessing computer system operates without requiring a central data structure for synchronizing time across multiple logical processors110. Global times on different logical processors110may be out of sync with one another.

Although the Figures show a timer component132and other components134in separate blocks, a given embodiment may include timer-related instructions116in one or more components, modules, processes, tasks, routines, functions, structures, classes, handlers, and so on. In one embodiment, for example, the system includes a scheduler component134which sets expiration times in global timers304, and hence may be viewed as containing timer component132instructions.

Timers300may be implemented using records, struts, classes, or other data structures, using a list, tree, bucket, or other arrangement, for example. Two timer structures400,500are illustrated inFIGS. 4 and 5. Embodiments are not limited to the timer structures shown.

A processor id field402identifies a logical processor110corresponding to a timer300that is represented by the timer structure400.

One or more link404fields, such as memory pointers, handles, or array indices, identify other timer structures400that are associated with the particular timer structure in a given arrangement.

An expiration time406field, such as a time data structure composed of one or more counters, specifies a time at which the timer is considered to have expired. In some embodiments, the timer effectively expires on or at any time after the specified expiration time406, but not before; no prediction is easily made as to when the timer will be checked for expiration. In other embodiments, a timer effectively expires on the specified expiration time406, or very near that time, because timers are checked frequently for expiration.

An expiration action408field specifies an action to be taken on or after expiration of the timer represented by the timer structure400. In some cases, no action is expressly specified; a given timer300may have been created in a given embodiment to cause an action which always occurs in that embodiment when that type (global, local) of timer is serviced. In some cases, the expiration action408specified is a signal, such as sending a message, setting a bit flag, etc. In some cases, the expiration action408specified is a callback routine to be invoked and executed.

A configuration410field specifies configuration values. For example, the role of a timer with respect to processors (global, local) may be implicit in the position of the timer structure400within a data arrangement, or it may be explicit in a configuration field bit value. If the timer structure400represents a global timer304, then the configuration410may specify that the global timer304is periodic (recurring) and may specify the timer's period. The timer's period may also be stored in a separate place such as a period412field. Conversely, the configuration410may specify that the global timer304is not periodic, namely, that it is a one-shot.

Configuration410bits may also specify whether a periodic global timer304is modulated or lazy. In one embodiment, periodic global timer expirations may be delayed or missed because the logical processor used to mark them was unavailable to the timer component132. After a logical processor has been unavailable for at least one period of a timer, a modulated periodic global timer304shortens the timer's period until the timer catches up, giving periodic expirations more frequently than would otherwise occur. A lazy periodic global timer defers expiration until the processor is available; some expirations may be skipped entirely.

Operations implemented in other contexts might be characterized as lazy in some sense. Within the Windows NT (mark of Microsoft) kernel, for example, a request that the kernel/Hardware Abstraction Layer switch interrupt request level does not always cause an immediate write to hardware. Also, the x64 architecture allows an exception to be generated whenever an operation that uses the floating point unit is encountered, and in some instances the kernel lazily switches floating point state in a manner similar to lazy switching of cold registers.

A timer ID414field contains a handle, GUID, or other global timer304identifier. The timer ID may be returned by an API function that creates a global timer304, so that the timer ID is available to identify that global timer in a subsequent API call to cancel that global timer, if necessary.

Timer structure500omits the processor ID field402because the identity of the processor on which the timer structure500is inserted is implicit in the timer structure's location in memory112. The list links502in timer structure500are pointers to other instances of timer structure500in a linked list. Some of the many suitable linked list arrangements are shown inFIGS. 6 through 8, and will be discussed further below. The expiration action field in timer structure500is an expiration callback routine pointer504, which gives the memory address of a routine to be invoked when the timer represented by the timer structure500expires and is being serviced. Configuration410values are omitted from timer structure500, because they are either not provided in a given embodiment or they are implicit in the location of the timer structure500in memory112relative to other data118. A variation of timer structure500which includes a timer ID414can be used to represent global timers304; local timers302do not require the timer ID field because they are not visible outside the hypervisor128.

Timer structures400,500may be part of a timer component132. In some timer component132embodiments, timer structure field values are part of the timer component data118, and procedures for setting expiration times, reading expiration times, and otherwise using the timer structures are part of the timer component instructions116.

With reference now toFIGS. 6 through 8, local timers302and global timers304may configure a memory112in various ways, depending on the embodiment. One aspect of several embodiments is that global timers304are associated with local timers302in such a way that global timer structures are checked for expiration only when their corresponding local timer expires. Because local timers are inserted and canceled on a given processor110, associating global timers with local timers reduces or eliminates the need for spinlocks or other timer synchronization mechanisms, which helps make timer component132code simpler, faster, more robust, and more scalable.

FIG. 6shows an example arrangement600of timer300structures configuring a memory112. In this arrangement600and similar arrangements, global timers and local timers may be implemented using timer structure400and/or timer structure500, for example. Global timers are indicated inFIGS. 6 through 8for convenience as boxes labeled with a “G” for global and with reference number304. Local timers are indicated as boxes labeled with an “L” for local and with reference number302. List links502are indicated by arrows.

The arrangement600includes a linked list602of global timers. The list602is associated with a dedicated local timer302by a link606from that local timer's structure to a global timer304structure in the list602of global timers. This dedicated local timer302is an element of a linked list604of local timers, whose first element is identified by a head pointer608. The lists602and604shown are doubly linked circular lists, but other types of list may also be used in a given embodiment, and it is not required that both lists602,604be the same type. Indeed, arrangements other than lists could be used, such as a sorted tree.

One embodiment in a multiprocessing system includes a list containing local timers302for a given logical processor110. Another list contains global timers304for that logical processor110, and the list of global timers is associated by at least one link with one local timer in the list of local timers.

FIG. 7shows an alternative arrangement700configuring a memory112. In this arrangement700, two dedicated local timers302in a list of local timers each have an associated list of global timers304.FIG. 8shows another arrangement800, in which one list802configuring memory includes only local timers302which have no associated global timer304, and another “list”804always containing a single dedicated local timer302links to a list806containing any global timers304inserted on the processor110. More generally, the number of global timer lists, the number of global timers in each list, and the number of local timers, may each vary in different embodiments and/or at different times during execution of a hypervisor128or a multiprocessor operating system202that uses lists of timer structures.

Not every item shown in the Figures need be present in every embodiment. Although some possibilities are illustrated here in text and drawings by specific examples, embodiments may depart from these examples. For instance, specific features of an example may be omitted, renamed, grouped differently, repeated, instantiated in hardware and/or software differently, or be a mix of features appearing in two or more of the examples.

Methods

FIG. 9illustrates some method embodiments in a flowchart900. In a given embodiment zero or more illustrated steps of a method may be repeated, perhaps with different parameters or data to operate on. Steps in an embodiment may also be done in a different order than the top-to-bottom order that is laid out in the Figure. Steps may be performed serially, in a partially overlapping manner, or fully in parallel. The order in which flowchart900is traversed to indicate the steps performed during a method may vary from one performance of the method to another performance of the method. The flowchart traversal order may also vary from one method embodiment to another method embodiment. Steps may also be omitted, combined, renamed, regrouped, or otherwise depart from the illustrated flow, provided that the method performed is operable and conforms to at least one claim.

During a local timer code executing902step, a logical processor110executes instructions116which operate on at least one local timer302. The executed code may be part of a hypervisor128or part of a multiprocessor operating system202, for example. Results of executing902local timer code may vary. Executing902local timer code may include, in particular, performing other steps shown inFIG. 9such as inserting906a local timer302in a list, canceling908a local timer302, checking914a local timer302for expiration, sending918a signal in response to expiration of a local timer302, invoking920a callback routine to which a local timer302contains an expiration callback routine pointer504, setting924a local timer302expiration time406, re-inserting930a local timer302, and/or programming936a hardware interrupt which causes one of the foregoing steps.

During a global timer code executing904step, a logical processor110executes instructions116which operate on at least one global timer304. The executed code may be part of a hypervisor128or part of a multiprocessor operating system202, for example. Results of executing904global timer code may vary. Executing904global timer code may include, in particular, performing other steps shown inFIG. 9such as inserting910a global timer304in a list, canceling912a global timer304, checking916a global timer304for expiration, sending918a signal in response to expiration of a global timer304, invoking920a callback routine to which a global timer304contains an expiration callback routine pointer504, setting926a global timer304expiration time406, re-inserting930a global timer304, and/or programming936a hardware interrupt which causes one of the foregoing steps.

During a local timer inserting906step, a local timer302is inserted on a particular logical processor110. This may be achieved, for example, by allocating memory and populating that memory with data to thereby insert a timer structure, such as timer structure400or timer structure500, on a list, such as list604or list802, which is associated with the logical processor110. A list604or list802may be associated with a logical processor110expressly by a processor ID, or implicitly by a relative position in a memory112, for example.

During a local timer canceling908step, a local timer302previously inserted on a particular logical processor110is canceled. This may be achieved, for example, by adjusting list links502to exclude a timer structure400,500from a list or other arrangement, and then marking as available the memory previously allocated to that timer structure.

During a global timer inserting910step, a global timer304is inserted on a particular logical processor110. This may be achieved, for example, by allocating memory and populating that memory with data to thereby insert a timer structure such as timer structure400or timer structure500on a list such as list602or list806which is associated with the logical processor110. A list of global timers may be associated with a logical processor by associating the list of global timers with a local timer302of that logical processor, for example.

During a global timer canceling912step, a global timer304previously inserted on some logical processor110is canceled. This may be achieved, for example, by adjusting list links502to exclude a timer structure400,500from a list or other arrangement, and then marking as available the memory previously allocated to that timer structure. Cancellation of a global timer from one logical processor110may be initiated (and in some embodiments may be fully performed) by instructions116that are running on that processor110, or by instructions that are running on a different processor110. For example, a virtual processor that is running the global timer may have been moved from the original logical processor to another logical processor. Locks or other synchronization mechanisms are used when canceling or otherwise modifying global timers, in order to prevent race conditions.

During a local timer expiration checking914step, a local timer302is checked for expiration. This may be achieved, for example, by comparing an expiration time406in a timer structure for the local timer302with a logical processor's local time counter to see if the expiration time has been reached or passed. The local time counter may be based, for example, on one or more register values obtained from a hardware130device such as an Advanced Configuration and Power Interface or an Advanced Programmable Interrupt Controller.

During a global timer expiration checking916step, a global timer304is checked for expiration. When global timers304are associated with local timers302as discussed herein (e.g. by a link606), checking a local timer can be sufficient to determine that an associated global timer has not yet expired. Only if the associated local timer has expired will the global timer(s) be checked.

During a signal sending918step, familiar tools and techniques are used to send a signal, e.g., to another process and/or to another processor, in response to expiration of a timer. Sending918a signal is an example of an expiration action408available in some embodiments.

During a callback routine invoking920step, familiar tools and techniques are used to invoke (pass control to while preserving present context) a callback routine in response to expiration of a timer. The callback routine code may be inline, or it may be identified by an expiration callback routine pointer504, or an index, for example.

During a timer servicing922step, an expiration action408is taken for an expired timer300, and the timer is then canceled (if it was a one-shot) or re-inserted (if it is periodic). An expiration action408may specify sending918a signal and/or invoking920a callback routine, for example.

During a local timer expiration setting924step, an expiration time is set for a local timer302. This may be achieved, for example, by placing a value in an expiration time406field. If the local timer302has one or more associated global timers304, then in some embodiments the expiration time406in the local timer302is set to the minimum (earliest time) of the expiration time(s) of the associated global timer(s), in order to help reduce or eliminate accesses to the global timer(s) when checking916them for expiration.

During a global timer expiration setting926step, an expiration time is set for a global timer304. This may be achieved, for example, by placing a value in an expiration time406field of a timer structure400,500that helps implement the global timer304.

During a global timer requesting928step, a hosted operating system124, for example, uses an API306call to request creation of a global timer304. In some embodiments, local timers302are not visible through the API306. The global timer request928may specify an expiration time expressly, or implicitly by some previously established or default value. The global timer request928may specify configuration values, such as whether the timer is to be periodic with a specified period412or is to be a one-shot, and if periodic whether the timer is lazy. The request928may also specify an expiration action408, such as a signal or a callback routine.

During a timer re-inserting930step, a timer300is re-inserted in a list or other arrangement of structures. Re-insertion930may be done to keep timers in a list or tree sorted in order according to their respective expiration times. Re-insertion930may be accomplished by changing links404or list links502, so that when the linked arrangement is traversed the timers are encountered in the desired order.

During an interrupt disabling932step, some or all interrupts are disabled. This may be achieved, e.g., by executing a processor-specific instruction designed to disable interrupts, or by setting/clearing a bit or bits in an interrupt mask.

During an interrupt enabling934step, disabled interrupts are re-enabled. This may be achieved, e.g., by executing a processor-specific instruction designed to enable interrupts, or by toggling the bit or bits in an interrupt mask that were used to disable interrupts.

During a hardware interrupt programming936step, an interrupt source136is programmed to cause a later interrupt on a given processor110. For example, a countdown value may be set within an interrupt controller chip or chipset, such that an interrupt will generated after a specified number of hardware clock cycles.

During an associating938step, one or more global timers304are associated with a local timer302such that the local timer's expiration time is the earliest of the expiration times of the associated global timers. That is, if the expiration time in this local timer has not yet been reached, then the expiration time of the associated global timers will also not yet have been reached. A local timer having such associated global timers is sometimes referred to herein as a “dedicated” local timer. Some embodiments allow only one dedicated local timer per processor110(e.g., as shown inFIGS. 6 and 8), while other embodiments allow multiple dedicated timers (e.g., as shown inFIG. 7) for a given logical processor. The global timers may be associated938with a dedicated local timer by one or more links404, for example, such as the link606.

In some embodiments, steps shown inFIG. 9are performed in a coordinated manner to provide timer management.

For example, in one embodiment a hypervisor128provides a timer component132that allows callers within the hypervisor to insert906/910a timer300by specifying the expiration time for the timer and an optional callback routine to invoke920when the timer expires. If no callback routine is specified then the caller is sent918a signal to indicate that the timer expired. The timer may be cancelled908/912at any time. A timer may be inserted906/910at any time and if the timer has already been inserted then it is automatically cancelled908/912from its current location and then inserted930again, to maintain the desired order of timers.

In one embodiment, the timer component132allows callers to manage both local timers302and global timers304. A local timer302is inserted906and cancelled908on a particular logical processor110. A global timer304may be cancelled912from a different logical processor than the logical processor110on which it was originally inserted. Synchronization is used to manage global timers, e.g., by allowing changes to a global timer only by a caller that has obtained a lock for that global timer.

In one embodiment, the timer component132programs936the hardware130on a processor110to deliver a hardware interrupt to the processor110at the earliest expiration time406of any local timer302or global timer304currently inserted on this processor110. The timer component132also provides a timer interrupt handier308which fields the hardware interrupt. The timer interrupt handler308services each expired timer by invoking920the timer's callback routine or sending918a signal to the caller that the timer has expired.

By programming936the hardware130layer to deliver an interrupt on the earliest upcoming expiration of an inserted timer, timers with fine resolution can be supported. The timer resolution can be driven by the resolution supported by the hardware, in the sense that finer timer interrupt resolution in hardware permits finer timer resolution in software. In one embodiment, if there are no inserted timers present on a processor110then hardware interrupt sources136are programmed (expressly or implicitly) to not deliver an interrupt, thereby saving the overhead of a wasted interrupt.

Some embodiments use one API306to manage local timers302and a different API306to manage global timers304. In some embodiments, callers within a hypervisor128use an API306to insert and cancel local timers302. In some embodiments, local timers302are maintained in a per-processor list, e.g., as shown inFIGS. 6 through 8. The timers in the list are maintained in increasing order of the expiration time so the timer to expire the earliest is at the head of the list. Interrupts are disabled932in some hypervisors128so there is no need for mutual exclusion between a timer interrupt handler308servicing the timers and any API306calls. This design avoids synchronization overhead for local timers302and reduces overhead for global timers304.

Some embodiments include a dedicated local timer302to service global timers304. A separate per-processor list, such as a list602or a list806, is maintained for global timers304inserted on a processor110. This list of global timers304is also ordered on expiration time, like the list of local timers302. Synchronization is required while inserting910or canceling912global timers from the list. A per-processor local timer302is used to service the global timers304; the list of global timers is associated938with the dedicated local timer, e.g., by a link606. An expiration callback routine pointer504for this dedicated local timer is set to point to a routine that examines the list of global timers for expired global timers and invokes the expiration action408routine or signal of each expired global timer.

Some embodiments insert910a global timer304in the following manner. Links404are set such that the global timer304is added to the processor's list of global timers. If this newly inserted global timer304is added to the head of the list of global timers, then the associated local timer302which is dedicated for servicing global timers is (re-)inserted in the list of local timers. The expiration time406of this dedicated local timer is set to the expiration time of the global timer304which is at the head of the list of global timers.

Some embodiments service922a global timer304in the following manner. Upon expiration of a dedicated local timer for global timers, the callback routine of the dedicated local timer is invoked920to service expired global timers that are associated938with the expired dedicated local timer. Each expired global timer304is removed from the list of global timers, and that expired global timer's expiration action408routine is invoked. If no global timers remain on the global timer list then the dedicated local timer is not re-inserted in the list of local timers. Otherwise the dedicated local timer is inserted in the list of local timers and is set to expire at the same time as the global timer which is now at the front of the list of global timers.

An embodiment may reduce or remove synchronization overhead for timers. In some embodiments, local timers are programmed (inserted or cancelled) at a higher frequency than global timers. In some embodiments, local timers have a finer resolution than global timers. By using a local timer to service the global timers, a timer interrupt handler only needs to examine the list of local timers for expired timers; the global timers are serviced automatically if the local timer inserted on their behalf has expired. Similarly, a routine to program936the hardware to the earliest upcoming expiration time among all local and global timers on the processor can directly use the expiration time of the local timer at the head of the list. Since the global timers on the processor are not considered in either case, the embodiment helps keep these performance sensitive routines simple and free from mutual exclusion considerations. When local timers are handled more frequently than global timers, using dedicated local timers as described herein thus results in greater efficiency.

Some embodiments include a method for managing timers for multiple logical processors110. An executing902step executes computer instructions116which manage local timers302. Executing computer instructions116which manage local timers302may include maintaining a list of local timers which are sorted in increasing order according to their respective expiration times406. An executing904step executes computer instructions116which manage global timers304. A servicing step services922global timers304for a given logical processor110only in response to expiration of a dedicated local timer302for that logical processor110, namely a local timer with which the global timers are associated938by a link606.

Some embodiments include the step of requesting928insertion of a global timer304; this request may be made, for example, by a hosted operating system124. In some embodiments, the step of servicing global timers occurs in response to invocation920of a callback routine for a dedicated local timer, namely, the local timer that is associated with the global timers. In some, the step of servicing922global timers includes examining a list of global timers, finding an expired global timer in the list, and performing an expiration action408for the expired global timer. Some embodiments include the steps of determining that at least one global timer304is associated with the local timer, (re)inserting906/930the local timer in a list of local timers, and setting924the local timer to expire at the earliest expiration time that is specified for any global timer304that is associated (e.g., by a link606) with the local timer.

Configured Media

Some embodiments provide a storage medium configured with computer data and computer instructions, such as data118and instructions116, for performing a method of managing timers as discussed above. The storage medium which is configured may be a memory112, for example, and in particular may be a removable storage medium114such as a CD, DVD, or flash memory.

The method characterized by the configured medium may be, for example, a method for managing timers for multiple logical processors110in an environment100which also contains a hypervisor128and a plurality of hosted virtual machines126. The computer data118may include local timer302structures and global timer304structures and arrangements, such as those illustrated inFIGS. 4 through 8.

In some embodiments, the method includes executing902computer instructions which manage the local timer structures such that a local timer structure for a logical processor is always inserted on and canceled from that logical processor; executing904computer instructions which manage the global timer structures such that a global timer structure for a logical processor that was inserted on one logical processor may be canceled from that logical processor or from another logical processor; and associating938via insertions906,910,930and a link such as link606the global timer structures for a logical processor110with one of the local timer structures for that logical processor. In some embodiments, the computer data118configuring the storage medium includes a doubly linked list of local timer structures, e.g., a list604. In some, the computer data118includes a linked list of global timer structures and a link in a local timer structure associating938the linked list of global timer structures with the local timer structure. Regardless of the type of list or other arrangement used, which may be different in different embodiments, the hypervisor128provides timers for the hosted virtual machines. The hypervisor128may also provide timers for internal hypervisor usage, such as a time slice timer. In particular, global timers may be used by hypervisor components in addition to being used by hosted virtual machines.

In some embodiments, the computer instructions116do not provide any of the hosted virtual machines with direct access to local timer structures. As a result, hosted virtual machines may only request insertion of global timers; the local timers are hidden from the hosted virtual machines.

In some embodiments, the computer instructions116read an earliest upcoming expiration time406from a local timer structure of a logical processor110and then program936a hardware interrupt to occur for the logical processor no sooner than the earliest expiration time. This earliest expiration time is the earliest of the expiration times of all of the timers then present on the logical processor110.

CONCLUSION

Although particular embodiments are expressly illustrated and described herein as methods, configured media, or systems, it will be appreciated that discussion of one type of embodiment also generally extends to other embodiment types. For instance, the descriptions of methods in connection withFIG. 9also help describe configured media, as well as the operation of systems like those described in connection withFIGS. 1though8. It does not follow that limitations from one embodiment are necessarily read into another. In particular, methods are not limited to the data structures and arrangements presented while discussing systems.

Reference has been made to the figures throughout by reference numerals. Any apparent inconsistencies in the phrasing associated with a given reference numeral, in the figures or in the text, should be understood as simply broadening the scope of what is referenced by that numeral.

As used herein, terms such as “a” and “the” are inclusive of one or more of the indicated item or step. In particular, in the claims a reference to an item generally means at least one such item is present and a reference to a step means at least one instance of the step is performed.

All claims as filed are part of the specification.

While exemplary embodiments have been shown in the drawings and described above, it will be apparent to those of ordinary skill in the art that numerous modifications can be made without departing from the principles and concepts set forth in the claims. Although the subject matter is described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above the claims. It is not necessary for every means or aspect identified in a given definition or example to be present or to be utilized in every embodiment. Rather, the specific features and acts described are disclosed as examples for consideration when implementing the claims.

All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope to the full extent permitted by law.