Methods and apparatus for executing code while avoiding interference

[0002] The present invention generally relates to systems for executing or otherwise performing code on one or more processors within a computerized device, and more particularly, to systems and techniques for atomically executing critical code without interference from interruptions or from other processors.

[0003] Conventional computer systems and computerized devices include one or more central processing units (CPUs) or processors that can operate to execute or otherwise perform software programs that are encoded as a series of logic instructions within a memory system accessible to the processor(s). Such computer systems also typically include an operating system program encoded within the memory system. The operating system operates as a control program that controls or governs when the processor is able to execute other programs such as user processes. Multitasking operating systems allow a single processor within a conventional computer system to execute multiple processes or threads in a back-to-back or time-sliced manner such that each process is able to move forward and make progress in its execution by utilizing a portion of processor cycles for execution. The terms process and thread will be used throughout this description interchangeably to denote a related set of logic instructions that a processor can perform (e.g., execute, interpret, run, etc.).

[0004] Some conventional computer systems include multiple processors that can operate under control of a multiprocessing operating system. Such a multiprocessing operating system controls the execution of multiple processes across the range of available processors in the computerized device. As an example of a multiprocessing computer system in operation, an operating system may begin to execute a user process on a first processor for a period of time until an interrupt of some sort occurs to that user process. Perhaps the interrupt is caused when the processor executes an instruction in the user process that requires access to data stored within a disk drive coupled to the computer system. As a result of such an input/output (I/O) request, the operating system suspends execution of the user process on the first processor while other software (e.g., an I/O process) and/or circuitry within the computer system handles any required processing associated with the I/O interrupt. When the operating system later detects that handling of the interrupt is complete and the requested data is now available for the user process, the operating system then reschedules execution of the user process on the same processor, or possibly on a second or other processor since the first processor may have already been rescheduled and may be currently executing another process. In this manner, multiprocessing operating system can “migrate” execution of processes from one processor to another to achieve greater overall processing throughput.

[0005] Certain software programs that execute as processes in conventional computer systems sometimes include a requirement that portions of code within the process be executed in an “atomic” or undisturbed manner. These portions of code in a process or program are often referred to as “critical code” or “critical sections”. Generally, critical code is a series of one or more logic instructions associated with a process, such as microcode, machine language instructions, or even high-level language instructions, which a processor in the computer system must execute from start to finish without any interference. Typical sources of interference are interruptions and actions performed by other processes such as remote actions. Interference is generally defined as an external modification or change made (i.e., by code other than the critical code or the process containing the critical code) to data, memory contents, register contents, flags, or other information that is related to (e.g., referenced by) the critical code.

[0006] There are a number of reasons why a process may contain a series of instructions (i.e., critical code) that must be executed atomically (i.e., without interference). As an example, some conventional computer systems include memory systems that operate as shared memory. Shared memory may be, for example, main memory that allows two or more software processes to access the same set of memory locations during their execution. Processes can use shared memory for such functions as interprocess communication, process synchronization and for other reasons. When a process contains a series of instructions that operate on shared memory locations, it is often preferable that those instructions be executed atomically as critical code in order to ensure that the content of the shared memory is accurately maintained. If an operating system interrupts a sequence of critical code instructions that access the shared memory before the critical code sequence completes full execution (i.e., before the sequence completes execution from start to end), the state or contents of the shared memory might be unreliable upon return to execution of the critical code at the point of interruption since other processes or code that may have executed during the interruption may have caused interference to the shared memory. This is one example of interference caused by an interruption.

[0007] Software and computer system developers have created a number of conventional techniques to allow a sequence of critical code instructions in a process to execute in an atomic manner to ensure that interference caused by interruptions is avoided. One such conventional technique is an atomic instruction used within software code called a “compare and swap” (CAS) instruction. Generally, a CAS instruction provides a technique for depositing a value into a memory location while guaranteeing that processing leading up to the CAS instruction is not interrupted.

[0008] In operation, prior to execution of the CAS instruction, a processor executes a load instruction to fetch a value from a known memory location M. This memory location M is typically the target memory location to which data must be written to in an atomic manner (i.e., without interference). Then, a processor executes one or more critical code instructions in the code to perform any required critical code processing. Finally, the processor executes the CAS instruction typically as the last instruction at the end of the critical section of code. The CAS instruction receives a set of parameters including an old value, a new value, and an address of the memory location M. The CAS instruction obtains ownership of the shared memory or cache at the location M specified by the address parameter and then obtains the value of data stored at this location. The CAS instruction then compares the value obtained from location M with the old value parameter provided to the CAS instruction. If the old value (i.e., the parameter) equals the value obtained from the location of the address M (i.e., the value placed there are the beginning of the critical code section), then the CAS instruction can assume that no interference has taken place to this memory location and the CAS instruction proceeds to store the new value at that location M. The CAS instruction also returns the new value as output. In the alternative, if the old value parameter does not equal the value that the CAS instructions retrieves from the location of the address M, then the CAS instruction can infer that some processing has disturbed or caused interference to the original value at memory location M. In such cases, the CAS instruction does not write to memory, but does return the value fetched from location M. Upon such an indication, the processor can re-execute the critical code by jumping to the start of the critical code (i.e., by jumping back to the initial store instruction) in another attempt to execute the critical code form start to end without interference.

[0009] A typical conventional process uses the CAS instruction at the end of critical code to form a loop that continually attempts to successfully execute the critical code ending with the CAS instruction each time this instruction fails. In this manner, a process operating the CAS instruction will not continue execution beyond the critical code section until the CAS instruction is able to be successfully completed one time, thus guaranteeing that all of the critical code has been completely performed and the new value is placed into the memory location specified by the address parameter without interference from any interruptions that may have occurred during execution of all critical code preceding the CAS instruction (beginning with the original or old value being loaded from the memory location that the CAS instruction eventually checks).

[0010] An example of the CAS instruction is shown in the following code segment:

[0011] RETRY:

[0012] LD M→TMP;

[0013] TMP+1→TMP2; (interruption causing interference might occur here)

[0014] CAS M,TMP,TMP2;

[0015] IF TMP!=TMP2 GOTO RETRY;

[0016] As shown in the example above, a processor executes the LD instruction to load the contents of memory location M into the TMP variable. Next, a sequence of one or more instructions are executed to manipulate data. In this example the variable TMP2 is set to the value of TMP+1. During this processing, an interruption causing interference might occur causing a change to the memory location M. After processing all instructions that require atomic execution has been completed, the CAS instruction stores the contents of TMP2 into memory location M if and only if TMP and M are the same. After the CAS instruction, a test is done to check to determine if TMP and TMP2 are the same. If they are, the CAS instruction executed successfully and atomically. If not, then this processing repeats until the CAS instruction is successfully completed. The CAS instruction might fail, for instance, if another processor operates a process which accesses data at the memory location M thus causing interference, or if an interrupt occurred between the LD and the CAS, and another thread executed on the processor in the interim, that thread may have modified location M, rendering the values in TMP and TMP2 registers “stale” (i.e., out of date with respect to memory).

[0017] Another conventional technique that provides for atomic execution of critical code sections is called a “load linked store conditional” or LL/SC technique. Generally, the load linked store conditional technique involves the use of two processor instructions: a load linked (LL) instruction followed by a store conditional (SC) instruction. The two instructions operate much like conventional load and store instructions except that the LL instruction, in addition to doing a simple load, has a side effect of setting a user transparent bit called a load link bit. The load link bit forms a “breakable link” between the LL instruction and a subsequently executed SC instruction. The SC instruction performs a simple store to memory if and only if the load link bit is set when the SC instruction is executed. If the load link bit is not set, then the store will fail to execute. The success or failure of the SC instruction is indicated in a register after the execution of the SC instruction. For example, the processor may load such a register with a “1” in case of a successful store or may load the register with a “0” if the store was unsuccessful due to the load link bit being reset. The load link bit may be reset by hardware or software (i.e., changed from the state induced from the original LL instruction) upon occurrence of events that have the potential to modify the memory location from which the LL originally loaded data, and that occur during execution of the sequence of code between the LL instruction and the SC. In other words, a section of critical code that must be executed atomically can be inserted between the LL and SC instructions and the SC instruction will only store data to a specified memory location (i.e., the data being modified by the atomic code instructions) if the load link bit is not reset.

[0018] An example of where a link can be broken between an LL and SC instruction on a multiprocessor system is when an “invalidate” occurs to a cache line of shared memory which is the subject of the LL. In other words, the link might be broken between the LL and the SC instructions if the processor that executes the LL observes an external update to the cache line, or if an intervention of snoop operation invalidates the line associated with the bit. The link may also be broken by the completion of a return from an exception (i.e., interrupt). It may be the case, for example, that an interrupt to the critical code occurs after execution of the LL instruction but before the SC instruction. During the interrupt, some other processor may have successfully completed a store operation to that same shared data which causes the load link bit to be reset. To avoid interference, the software or hardware will explicitly break the link when returning from the operating system back into the interrupted critical code. This will result in the subsequent SC failing.

[0019] An example of pseudocode that illustrates the load linked store conditional technique is as follows (with the text in parenthesis indicating the nature of the processing performed):

[0020] RETRY:

[0021] LL M→TMP; (load link bit set)

[0022] TMP+1→TMP2; (interruption causing interference and resetting the load link bit might occur here)

[0023] SC TMP2, M; (only store if load link bit still set)

[0024] IF FAILED_BIT=1GOTO RETRY;

[0025] As shown in the example above, the processor executes the LL instruction that operates to load the contents of memory location M into the TMP variable. The LL instruction further sets the load link bit. Next, a sequence of one or more instructions are executed to manipulate data. In this example the variable TMP2 is set to the value of TMP+1. During this processing, an interruption causing interference might occur causing the load link bit to be reset. After processing all instructions that require atomic execution is complete, the SC instruction stores the contents of TMP2 into memory location M if and only if load link bit set by the LL instruction is still set (i.e., is not reset). After the SC instruction, a test is done to check a failure bit (FAILED_BIT) in a processor status register associated with the processor executing this critical code to determine if the SC instruction executed successfully. If the FAILED_BIT equals 1, processing returns to the RETRY location in order to again attempt to execute this section of critical code. This processing repeats until the SC is successfully completed. The SC instruction might fail, for instance, if another processor operates a process which accesses data at the memory location M, thus causing the load link bit to be reset (i.e., thus causing interference).

[0026] Another conventional technique used to ensure atomic execution of critical code instructions is referred to as a lock/unlock technique. The lock/unlock technique can be used, for example, in situations where a portion of shared user level code must be executed atomically. When a user level process enters a section of shared critical code, the first instruction that is executed is a lock instruction which attempts to gain ownership of and set a flag indicating a user level process is in the process of executing this section of critical code. When the user level process succeeds in owning and setting this flag, the process can then execute the remainder of the critical code with or without interruption(s). When the process has completed execution of the critical code instructions, the final instruction the process executes to complete the critical code is an unlock instruction which clears the lock flag thus allowing another user level process to gain ownership of the lock flag and to execute this section of shared critical code. No process is allowed to execute this section of shared critical code until it owns the lock flag. If a user level process is interrupted during execution of a critical section of code, that user level process continues to “own” the lock on that section of code and other user level processes (as well as the interrupted process) are blocked from executing that section of code until the interrupt has been handled and processing returns to complete execution of the shared critical code by the user level process that owns the lock on the critical code. That process then completes execution of that section of critical code after the interrupt and performs the unlock instruction to free that critical section of code for ownership and execution by another user level process. Since no other processes could execute the critical code section during the interrupt, it is assumed that interference did not occur.

[0027] Conventional techniques for ensuring the correct atomic operation of critical code in a computer system without interference (due to interruptions, the action of other processors, or other causes) suffer from certain deficiencies. In particular, conventional critical section execution techniques such as compare and swap and load linked store conditional perform testing at the end of a section of critical code to determine if an interruption causing interference occurred sometime during execution of the critical code. If the critical code section contains many instructions (i.e., is lengthy), then an interruption or remote action that causes interference to the critical code near the start may not be detected until the end of the complete execution of the critical code section at which point the compare and swap or load linked store conditional are performed. In other words, such techniques may involve the processing of unnecessary critical code instructions prior to the detection of the interference and then subsequent re-execution of the critical code section from the beginning. Any critical code instructions which are executed after the occurrence of the interruption causing interference but prior to the operation of the compare and swap or load linked store conditional instruction are simply overhead instructions which consume valuable processing cycles.

[0028] In addition, techniques such as compare and swap and load linked store conditional cause re-execution of the critical code from a point that corresponds to the beginning of the critical code section. Accordingly, during execution of a critical code section containing numerous instructions, an interruption that causes interference that occurs towards the end of the execution of such instructions (i.e., thus many critical code instructions were executed prior to the interference from interruption) requires that all critical code instructions be re-executed again, even though some of such critical code instructions were properly executed the first time without interference.

[0029] Further still, conventional critical code execution techniques that guarantee atomic execution of the critical code provide no ability to detect interference immediately upon return from an interruption. Accordingly, the drawbacks mentioned above of unnecessarily executing critical code instructions prior to detecting interference cause unnecessary processor overhead.

[0030] The lock/unlock technique for ensuring atomic execution of critical code introduces another problem called the “convoy” problem. In the lock/unlock technique, once a first user process obtains ownership and sets the lock flag and begins execution of a critical code section, other user processes are unable to enter the critical code section and remain blocked until completion of the critical code section by the first user process. This can be problematic since the first user process might be interrupted for a prolonged period of time during execution of the critical code. Such an interrupt, whether or not causing interference, can impose a significant delay on the execution of the first user process as well as the other user processes that are blocked from entering the critical code section due to their inability to obtain ownership of the lock flag. In other words, the interruption delay imposed on the first user process is further imposed on other user processes that remain blocked while awaiting ownership of the critical code. Accordingly, those other user processes are “convoyed” until the first user process interruption is complete and the first user process completes execution of the critical code section and unlocks the lock flag.

[0031] In addition, lock/unlock techniques can also suffer from a problem known as the priority inversion effect. In such situations, a low priority process might obtain a lock on a portion of critical code. This low priority process might then be preempted by the operating system for a higher priority process. During execution, the higher priority process might require access to the critical code, but cannot do so due to the lock on this code still existing from the lower priority process. In such cases, the higher priority process is impeded by the lower priority process due to the lock.

[0032] These and other constraints of conventional techniques for atomically executing critical code sections can significantly increase the amount of processing time spent by a process in an attempt to fully execute a critical code section while avoiding the effects of interference caused by interruptions.

[0033] Embodiments of the invention provide the ability to execute critical code sections in an atomic manner without interference. Certain embodiments can significantly avoid certain drawbacks discussed above with respect to conventional techniques for atomically executing of critical code. One embodiment of the invention operates in a computerized device to register a critical code section (or a thread or process containing critical code) with an operating system for invocation of a critical execution manager in the event of an interruption to the critical code. The registration process can cause the operating system to store the address bounds of the critical code in a data structure for use by the critical execution manager upon returning from handling an interruption to execution of the critical code. Registration can also “register” the critical execution manager as code that is to be invoked upon returning from an interruption to the thread containing the critical code.

[0034] In one implementation, for registration to take place, a hook into the operating system can be exploited to indicate to the operating system that the critical execution manager is the code that is to be executed upon returning from all interruptions to the thread containing the critical code. Generally, the process containing the critical code informs the operating system of its intent to use the invention prior to entering critical code by registering a “call-back” address of code containing the critical execution manager with the kernel.

[0035] A processor then executes the thread and the thread may alternate between executing normal code and critical code. If an interrupt occurs during normal code execution, no special action is taken and the interrupt is handled normally. However, if the interrupt occurs while in the critical code, since registration is done just prior to entry into the critical code, upon completion of interrupt handling, processing returns to the call back address of the critical execution manager. In other words, once the operating system handles the interrupt, the operating system invokes execution of the critical execution manager configured according to embodiments of this invention. The critical execution manager is able to detect if the interrupt occurred in the critical code and can detect if an interference signal indicates a reset value. In other words, the critical execution manager is able to detect whether or not the interruption could potentially cause interference to critical code based upon a value of an interference signal. According to different embodiments of the invention, the interference signal can be set or can otherwise indicate the reset value in a number of ways. In a conservative implementation, the interference signal can be set during execution of the critical code to indicate that a reset operation is required on the critical code in the event of any interruption to the execution of the critical code, whether or not that interruption actually causes interference to information (e.g., processor or memory information) related to the critical code.

[0036] If, after returning from the interruption, the interference signal indicates a reset value, the critical execution manager performs a reset operation on the critical code to reset the current state of the critical code to avoid interference from handling the exception or interruption. The critical execution manager then returns processing to execution of the critical code using the current state of the critical code. Embodiments of the invention can determine if the interference signal indicates a reset value, for example, by detecting an interference signal set as a result of execution of the critical code, or by determining that a second thread was executed by a processor associated with the first thread (i.e., the thread containing the critical code) during handling of the interruption of the first thread, or by detecting that the thread containing the critical code has been migrated to a processor that is different that a processor upon which the thread was executing at a time of the interruption. Generally, the two preconditions that the critical execution manager can detect to indicate a reset value is present is that an interruption (i.e., preemption) or migration of a process occurred and that execution was taking place in the critical section at that time.

[0037] Once the critical execution manager determines that the interference signal indicates a reset value, the reset operation can be performed in a variety of ways according to different embodiments of the invention. Generally, the operation of performing the reset operation includes replacing current processor information (e.g., a current program counter) existing within the current state of the critical code with processor information obtained from the registered or saved state of the critical code (or of the registered thread) in order to allow the operation of returning to execution of the critical code to begin execution (e.g., restart) of the critical code without interference from handling the interruption. In this manner, the critical execution manager can use the registered state of the critical code saved prior to handling interruption to update the current state of the critical code that exists upon returning to the critical code after handling interruption.

[0038] According to embodiments of the invention, the state of critical code (i.e., the save state and/or a current state) can include information including processor information related to the critical code such as register values, flag settings or other processor specific information. The state of critical code can also include memory information that is related to the critical code such as addresses and/or values of memory locations referenced by instructions within the critical code.

[0039] In some embodiments of the invention, the operation of detecting if an interference signal indicates a reset value can include detecting that a thread containing the critical code has been migrated to a processor that is different than a processor upon which that thread was executing at the time of the interruption. In such a case, the reset operation can include receiving (e.g., as part of the interference signal) an identification of a processor upon which the critical code is scheduled to execute next and then adjusting memory references of offsets that are associated with the critical code for the processor upon which the critical code is scheduled to execute next in order to allow the critical code to properly reference processor specific data during operation of returning to execution of the critical code on the new processor. Accordingly, if after interruption the critical code is now migrated to another processor, the memory information associated with a new processor can be properly accessed by the critical code using the processor identification to computer address offsets into processor specific memory thus allowing the critical code to continue to operate properly.

[0040] Once embodiments detect that the interference signal indicates a reset value, embodiments of the invention can operate in a variety of unique ways to resume execution of the critical code. In particular, some embodiments of the invention are able to perform a “roll-back” or abort operation as part of the reset operation in order to restart the critical code from its beginning while in ensuring that the current state of the critical code is reset to a state that existed prior to occurrence of the interruption. This roll-back operation allows the operation of returning to execution of the critical code to begin execution of the critical code without interference from handling interruption. In particular, in the “roll-back” embodiments of the invention, the registered state of the critical code identifies the start of execution of the beginning of the critical code. Also in the roll-back embodiments, the reset operation (e.g., modifying current processor information existing within the current state of the critical code with registered thread information) includes resetting a program counter for the critical code to reference an instruction existing at the beginning of the critical code in response to the interruption. In doing so, upon returning to execution of the critical code, such execution begins at the start or beginning of the critical code and the current state of the code is exactly as it was upon initial entry into the critical code the first time it was executed.

[0041] Other embodiments of the invention can utilize a roll-forward operation to avoid interference caused by interruptions. In roll-forward embodiments of the invention, the operating system kernel inherently save a state of the critical code in response to the interruption to the execution of the critical code. Then, after handling the interruption and detecting that the interference signal indicates a reset value, the critical execution manager can restore, modify or reset a program counter for the critical code to reference an instruction that was interrupted in the critical code by referencing the kernel information indicating this state. This embodiment can also reload register information associated with the critical code from the registered state of the critical code. The register information can contain information related to the critical code at the time of the interruption. In a critical section of code, upon returning from an interruption, intermediate values in registers may be “stale.” In one embodiment, the critical execution manager causes execution to resume at a special location that operates as a repair entry point that contains code to refresh the stale register values and then transfer control back an appropriate location in the critical code, which may be the interrupted location (roll-forward) or the beginning of the critical section (roll-back).

[0042] In the roll-forward embodiments, when returning to execution of the critical code after the interruption and after the reset operation, such execution begins at the instruction that was interrupted in the critical code as now referenced by the program counter for the critical code. In other words, this embodiment performs a roll-forward operation that causes the critical code to resume execution at the point of interruption instead of returning to the beginning of the critical code. This avoids having to re-execute critical code instructions that previously executed prior to the interruption that caused the interference.

[0043] Other embodiments of the invention are also able to perform the reset operation using one or more compensation transactions. Compensation transactions generally allow such embodiments to undo or reverse changes made to processor information such as register values related to the critical code that may have been modified by the interruption. Alternatively, compensation transactions can undo changes made to variables or registers by the critical code prior to the interruption point, but after commencing execution of the code. In other words, compensation transactions can either undo interference by compensating for such interference or in an alternative configuration, can undo operations performed by the prior execution of the critical code up to the point of interruption. As an example, if another processor accesses shared memory or registers referenced by the critical code during the interruption, the compensation transactions can detect this change and can reverse or undo this change in order to restore the processor or memory information to a state that existed prior to the interruption thus compensating for the interruption. This is useful in roll-forward embodiments to reestablish a register state as it existed at the beginning of the critical section so that when the program counter is set to reference the beginning of the critical code, the execution of the critical code can being having a complete state that is unmodified due to interference. In an alternative arrangement of the use of compensation transactions such as may be employed in roll-back embodiments, if some instructions in the critical code execute prior to an interruption to add ten to a variable, the compensation instructions might subtract ten from this variable value prior to returning to execution at the beginning of the critical code (in a roll-back embodiment) to thus re-establish the state of the critical code section as it appeared at its initial start. Conventional techniques for returning to execution of the critical code can fail in this regard as they simply return to execution of the start of the critical code but do nothing to prevent, reverse, undo or compensate for modification of register contents or other contents such as memory locations that may have occurred during interruption.

[0044] According to one embodiment of the invention, the techniques above apply to user level processes or threads that operate on processor specific data. In other words, the critical code is associated with a user thread that is executing on a specific processor within a multi-processing computerized device and further more, the critical code will be accessing data that is specifically and uniquely associated with the processor (e.g., processor specific data). In addition, the techniques of the invention do not require locking mechanisms (i.e., are lock-free or mutual exclusion free) and thus avoid issues such as the convoy problem associated with conventional techniques for executing critical code.

[0045] Embodiments of the invention can be implemented as methods in a process or as circuitry or hardware or as software or a combination of hardware and software within a computerized device or as software encoded within a computer readable medium. In particular, other embodiments of the invention include a computer system, such as a computerized device, workstation, handheld or laptop computer, or other device configured with software and/or circuitry to process all of the method operations disclosed herein as embodiments of the invention. In such embodiments, the computerized device is capable of executing critical code without interference and includes a processor and a memory encoded with an operating system, critical code, and a critical execution manager. An interconnection mechanism couples the processor and the memory and the processor executes critical code, the critical execution manager and the operating system causing the processor to perform the operations of embodiments of the invention as explained herein. In other words, a computerized device such as a computer that is programmed to operate as explained herein is considered an embodiment of the invention.

[0046] Other arrangements of embodiments of the invention that are disclosed herein include software programs to perform the method embodiment steps and operations summarized above and disclosed in detail below. As an example, an operating system configured with a critical execution manager that operates as explained herein is considered an embodiment of the invention. Alternatively, the critical execution manager may be implemented in a user process, or partly in an operating system and partly in one or more user space processes, or in any combination thereof. More particularly, a computer program product is disclosed which has a computer-readable medium including computer program logic encoded thereon that, when executed on at least one processor with a computing system or computerized device, causes the processor to perform the operations (e.g., the methods and steps) disclosed herein as embodiments of the invention. Such arrangements of the invention are typically provided as software, code and/or other data (e.g., data structures) arranged or encoded on a computer readable medium such as an optical medium (e.g., CD-ROM), floppy or hard disk or other a medium such as firmware or microcode in one or more ROM or RAM or PROM chips or as an Application Specific Integrated Circuit (ASIC). The software or firmware or other such configurations can be installed onto a computer system to cause the computer system to perform the techniques explained herein as embodiments of the invention.

[0047] It is to be understood that the system of the invention can be embodied strictly as a software program, as software and hardware, or as hardware alone. Example embodiments of the invention may be implemented within computer systems, computer program products, operating systems and software applications manufactured by Sun Microsystems of Palo Alto, California, USA.

[0048] The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of embodiments of the invention, as illustrated in the accompanying drawings and figures in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, with emphasis instead being placed upon illustrating the embodiments, principles and concepts of the invention.

[0049] FIG. 1 illustrates an example of a computerized device that executes a thread containing critical code and that is equipped with a critical execution manager configured according to one embodiment of the invention.

[0050] FIG. 2 is a flow chart of processing steps performed according to one embodiment of the invention to allow execution of critical code while avoiding interference from interruptions.

[0051] FIG. 3 illustrates a process control flow and timing diagram that shows operations of embodiments of the invention.

[0052] FIG. 4 is a more detailed example of an operation and processing flow diagram that shows execution of a thread containing critical code while avoiding interference caused by interruptions according to one embodiment of the invention.

[0053] FIGS. 5 and 6 are a flow chart of processing steps that illustrate details of processing performed according to one embodiment of the invention to avoid interference caused by interruptions to the execution of critical code.

[0054] Embodiments of the invention provide mechanisms and techniques to execute critical code in an atomic manner while avoiding interference caused by interruptions to execution of the critical code. In particular, embodiments of the invention allow processes such as user-level threads to execute sections of critical code without requiring synchronization techniques to be employed such as those commonly utilized in conventional systems to avoid interference for interruptions. Embodiments of the invention may be utilized by user level processes or threads that operate in a multiprocessing environment which allows for migration of the user level processes or threads between processors in order to insure that those processes can atomically execute critical code without using synchronization techniques between other user processes. In addition, the multiprocessing environment may be one in which each processor in a computerized device has an associated segment or portion of processor specific data that the critical code references during execution. Such embodiments of the invention allow migration interruptions to the critical code while avoiding interference caused by differences in memory references within the critical code to the processor specific data depending upon which processor the critical code is migrated to during interruption.

[0055] In an example implementation, one embodiment of the invention registers a user level process or thread containing critical code with a device driver program called a critical execution manager that is integrated into an operating system in a computerized device. The critical execution manager may also reside (e.g., may execute) in whole or in part within user space or as a user program (i.e., may be split between the operating system and a user space critical execution manager program). The registration process provides the operating system and the critical execution manager with an indication of the starting point of the critical code within the code of the user process or thread. The registration procedure further instructs the operating system to invoke the critical execution manager upon returning from handling an interruption to the execution of the critical code.

[0056] A processor then begins execution of the user process containing the critical code until an interruption to the execution of the critical code occurs. At this point, the processor control passes to the kernel of the operating system that saves a state of the user process containing the critical code. As an example, a typical operating system saves register contents and program counter information indicating the location of the interrupt to the critical code in a kernel data structure within the operating system. Thereafter, the operating system handles the interruption. Handling the interruption may entail servicing an I/O request, rescheduling the user thread for future execution, migrating the user thread to another processor within a computerized device, or similar operations. After handling the interruption, processor control is passed to the critical execution manager that the operating system invokes due to the registration procedure, instead of returning to execution of the critical code that was originally interrupted. In other words, the registration procedure instructs the operating system to return control to the critical execution manager instead of the critical code itself upon return from handling interruption to the critical code.

[0057] At this point, the critical execution manager determines if critical code was interrupted and detects (i.e., determines) if an interference signal related to the critical code indicates the reset value. As an example, the critical execution manager can make a determination if the interruption occurred to the user process during execution of the critical code. As another example, the critical execution manager may determine that in interference signal indicates a reset value in the event that the user process is now scheduled to be executed on a processor is different than the processor upon which the critical code was executing at the time of interruption. If the interference signal indicates a reset value, the critical execution manager performs a reset operation on the critical code to reset the current state of the critical code to allow execution of the critical code while avoiding interference that may have been caused from handling the interruption.

[0058] Depending upon which embodiment of the invention is in use, the reset operation can perform either a roll-back operation which allows the critical code to be re-executed from the beginning, and thus resets the current state of the critical code to start or entry point to the critical code. In another embodiment of the invention, the critical execution manager can perform a roll-forward operation which allows the critical code to be re-executed from the point of interruption (as opposed to the beginning) and resets the current state of the critical code to a state existing at the time of the interruption. In an embodiment of the invention that provides for a roll-back operation, the critical execution manager can further utilize compensation transactions to undo, reverse or compensate for the effects of register or other interference caused by the interruption, thus allowing the critical code to be re-executed while avoiding interference from the interruption.

[0059] In either case, the critical execution manager is capable of allowing execution of the critical code while avoiding the effects of interference caused by the interruption. As an example, if the interruption results in a second process executing on the processor upon which the critical code was executing just prior to the interruption, the second process may corrupt information related to the critical code such as memory information or processor information (e.g., register contents). Accordingly, the reset operation performed by the critical execution manager is capable of reversing the effects of such interference in order to allow the critical code to resume execution but without requiring the critical code to use synchronization techniques such as those conventional techniques discussed above.

[0060] In situations where the user level process or thread operates in a multiprocessing environment, the interference signal that the operating system provides to the critical execution manager after handling the interruption can include an identification of the processor upon which the user process containing the critical code is scheduled to execute next. Accordingly, in one embodiment of the invention, the critical execution manager reset operation can further include adjusting an offset used to compute addressing information into processor specific memory for data referenced by the critical code based upon a processor identification received as part of the interference signal. In other words, if the critical code is migrated from one processor to another and each processor references processor specific memory that is not shared by other processors, the offset to critical code data in such processor specific memory for each different processor can be different. Accordingly, the critical execution manager can obtain the identification of the processor upon which the critical execution code is scheduled to execute next and can determine the appropriate offset to the data such that the critical code can be re-executed on the alternative processor using proper offsets thus avoiding interference from the migration.

[0061] FIG. 1 illustrates a computerized device 100 (of which there may be more than one) configured according to one example embodiment of the invention. The computerized device 100 may be any type of computerized device or system such as personal computer, workstation, portable computing device (e.g., laptop, palmtop or handheld computer), dedicated device, or the like. The example computerized device 100 includes an interconnection mechanism 105 (e.g., a data bus and/or circuitry) which couples a memory 120 (e.g., any computer readable medium such as random access memory (RAM) and/or read only memory (ROM), programmable memory, or even a disk or storage medium) and one or more central processing units referred to as processors 110 (two this example, processor A 110-1 and processor B 110-2).

[0062] The memory 120 is encoded with first and second non-operating system processes 150-1 and 150-2 that in this example are user threads or processes. The processes 150-1 and 150-2 can interact 163, 164 with the operating system 130 in order to be scheduled for execution upon one or both of the processors 110-1 and 110-2. The first non-operating system process 150-1 includes a section of critical code 160 that, for proper operation, requires atomic execution within the first non-operating system process 150-1. The memory is further encoded with an operating system 130 and a critical execution manager 140 configured according to one embodiment of the invention. The operating system 130 includes a kernel and the critical execution manager 140 includes portions that are integrated with the operating system 130 (e.g., integrated into the kernel, as will be explained). Other portions of the critical execution manager 140 execute within user process space.

[0063] Also illustrated within the memory 120 are two reserved areas called memory information A 170-1 and memory information B 170-2. Each of the memory information areas 170 is a memory buffer, cache, or local allocation buffer (LAB) associated with and reserved for processes that operate on one of the respective processors 110. In this example, memory information A 170-1 is an area of the memory 120 that is reserved for reference by processes or threads (e.g., 150-1 or 50-2) that execute upon or within processor A 110-1, whereas memory information B 170-2 is an area of the memory 120 that is reserved for access and use by processes or threads (e.g., 150-1 or 150-2) that execute upon or within processor B 110-2. The addresses or offsets of memory information A 170-1 and B 170-2 are different from one another. Since in this example the sets of memory information 170-1 and 170-2 are respectively reserved for use by processes executing on a respective processors 110-1 and 110-2, the memory accesses 165 through 168 represent access to these sets of memory information 150 during execution that process on one of those processors.

[0064] Each processor 110 includes a respective set of processor information 115. Processor information 115 on either processor A 110-1 or processor B 110-2 represents the contents of processor specific information related to a thread or process operating at that point in time upon that processor 110. In other words, processor information is the processor state (i.e., during execution) or saved processor state (during interrupt handling) related to a thread or process. As an example, if processor A 110-1 is executing critical code 160, then processor information A 115-1 includes the contents or values of a program counter for the critical code 160, as well as the set of values associated with any registers, flags, processor status words, or other information associated with the critical code 160. Likewise, processor information B 115-2 represents similar information for any code or any process executing at any point in time on processor B 110-2.

[0065] Quite often, a section of critical code can complete execution without interrupts. However, in cases where critical code execution is interrupted, according to the general operation of embodiments of the invention, a processor is able to execute the critical code 160 of the process 150-1 and after an interrupt to the execution of the critical code occurs and is handled by the operating system 130, the operating system 130 activates the critical execution manager 140 with an interference signal 163. Based on the interference signal 163, the critical execution manager can determine if execution was interrupted in the critical code 160 and can perform a reset operation 162 on the critical code 160 in order to allow execution of the critical code 160 to continue while avoiding interference from the interruption and without requiring synchronization procedures such as conventional load linked store conditional or compared and swap techniques. An interference signal represents a potential interference condition or risk or exposure to which a process may be subject. The interference signal itself may not imply that interference actually occurred, but indicates that interference may have occurred during an interruption or other interference to a process that was executing. Reference is now made to the flow chart of processing steps in FIG. 2 that illustrate an example operation of embodiments of the invention with respect to the example computerized device illustrated in FIG. 1.

[0066] FIG. 2 is a flow chart of processing steps performed by a computerized device equipped with a critical execution manager configured according to one embodiment of the invention that allows execution of the critical code 160 while avoiding interference caused by interruption to the critical code 160. The description of the processing steps shown in FIG. 2 will be provided in conjunction with reference to an example operation of the invention as illustrated in FIG. 1.

[0067] In step 200, a processor 110-1 within the computerized device begins execution of a thread (e.g., first non-operating system process 150-1) containing critical code 160. At some point either before or during the execution of the thread 150-1, the computerized device 100 performs step 201 in which the processor A 110-1 performs logic instructions either within the critical code 160, within the program that provides the thread 150-1 (i.e., within a user process that at some point will access the critical code), within the operating system 130 or existing within some other process (e.g., a system registration service) which registers the critical code 160 (or registers the entire thread or process containing the critical code) with the operating system 130 for invocation of the critical execution manager 140 in the event of an interruption occurring to the critical code 160. Specific details of the registration process of the critical code 160 will be provided later.

[0068] For purposes of this example, registration generally causes the critical execution manager 140 to become aware of or have knowledge of the location such as a beginning address of the critical code 160 within the thread 150-1. In addition, registration activates a hook into the operating system 130 which indicates to the operating system 130 that if an interruption occurs during execution of the thread 151 (or to execution of just the critical code 160), then after handling the interruption and upon returning to execution of the critical code, the operating system 130 is to transfer execution to the critical execution manager 140. Stated differently, registration entails indicating, to the operating system 130, a beginning address or starting point for the critical code 160 as well as a pointer to code for the critical execution manager 140 which the operating system 130 will execute upon completion of handling an interruption to the thread 150-1 containing the critical code 160. Registration thus informs the operating system that the thread will be accessing critical sections of code and wishes to receive notification of potential interference. Thus a thread not accessing or using critical sections does not need to register and would not require use of the invention.

[0069] Next, in step 202, the computerized device 100, and specifically processor A 110-1 begins execution of the critical code 160 until an interruption to the execution of the critical code 160 occurs. During execution of the critical code 160, the critical code 160 executing within the first user thread 150-1 accesses 166 memory information A 170-1 which is, as explained above, is a local allocation buffer in the memory 120 reserved for use by processes that execute on processor A 110-1. At some point during the operation of step 202, the processor 110-1 interrupts the execution of the critical code 160. There may be various reasons why the operating system 130 interrupts execution of the critical code 160. As an example of such an interrupt, a multitasking time slice algorithm implemented within the operating system 130 may determine that a time slice allocated to the user thread 150-1 has expired and thus resources of the processor A 110-1 are now to be allocated to another process. It is to be understood that other types of interrupts can occur as well, such as page faults, I/O interrupts that activate a higher priority thread, and so forth. These are examples of preemption interrupts that lead to involuntary context switching. In other words, the processor is taken from the thread.

[0070] Next, in step 203, the operating system 130 handles the interruption. Continuing based on the example interruption suggested above, during handling of the interruption, the operating system 130 may execute a second non-operating system process 150-2 such as a second user thread 40 on the processor A 110-1. The operating system may also reschedule execution of the thread 150-1 on another processor, such as processor B 110-2.

[0071] In step 204, after handling the interruption (step 203) that occurred in step 202, the operating system 130 invokes execution of the critical execution manager 140 due to the registration of the first non-operating system process (i.e., user thread) 150-1 with the operating system 130 (that took place in step 201). According to one embodiment of the invention, the registration process that takes place in step 201 registers the code associated with the critical execution manager 140 as a device driver within the operating system 130 using a scheduler activation hook incorporated into the operating system 130. Such a scheduler activation hook causes the operating system 130 to transition from kernel mode back into user mode by transferring processor control to the critical execution manager code 140 instead of returning to the original process which was interrupted, which in this case is the thread 150-1 containing the critical code 160. Accordingly, by registering the critical execution manager 140 as a device driver to be activated by the scheduler activation hook into the operating system 130, when the critical code 160 is interrupted in step 203, the operating system transfers processing control to the critical execution manager 140 in step 204 instead of returning processing control back to the processing thread 150 which was originally interrupted (i.e., the code 160).

[0072] In step 205, the computerized device 100 executes code within the critical execution manager 140 to detect if an interference signal 163 indicates a reset value. The critical execution manager 140 receives the interference signal 163 as part of a callback from the operating system 130 upon completion of handling interrupt. Generally, a callback is a redirection or diversion mechanism that the operating system uses in this invention when returning from kernel-space to user-space. Instead of resuming executing at the next user instruction in the interrupted process (e.g., in the critical code) as would normally be the case, due to the registration process, the callback causes execution to resume execution at the registered user space address of the critical execution manager. Typically, the operating system passes a program counter or instruction pointer (i.e., an address) of an instruction in the critical execution manager to execute next (as specified during registration).

[0073] In one embodiment of the invention, the interference signal 163 also causes the critical execution manager 163 to receive a processor identification indicating an identity of the processor 110-1 or 110-2 upon which the thread 150-1 containing the critical code 160 is scheduled to execute next. In other words, interference signal 163 can identify the processor upon which the operating system 130 is scheduled to again begin execution of the critical code 160. In addition, the interference signal 163 can contain processor information A 115-1 that identifies or contains information related to the state of the critical code 160 as it existed at the time of the interruption. As an example, this information can include register values and a program counter or instruction pointer identifying the instruction within the critical code 160 that was interrupted.

[0074] As will be explained in more detail shortly, the interference signal 163 can indicate a reset value under a variety of circumstances and the reset value operates as a trigger condition to the critical execution manager 140 to perform a reset operation on the critical code in order to avoid any actual or possible interference which may have been caused by the interruption to execution of the critical code 160. Generally then, the purpose of the reset value is to flag or otherwise indicate such interference situations and to trigger the reset operation by the critical execution manager 140.

[0075] There are various ways for the critical execution manager 140 to be informed by the operating system that first, an interruption occurred in critical code, and second, for the critical execution manager to determine that the interruption either caused or is considered to have caused interference. As an example, in a conservative implementation of one embodiment of the invention, any interruption at all to the critical code 160 may prompt the operating system to provide an interference signal 163 that indicates a reset value. In other words, whether interference actually occurred or not, the existence of an interruption to critical code can be considered grounds to perform a reset operation. In another example, if the operating system migrates the interrupted thread to another processor, then the interference signal can contain a processor identity that is different that a formerly saved processor identity. In another example, if any user thread executed during the interrupt (but the processor identity might be still the same), then the operating system may provide an interference signal to the critical execution manager 140.

[0076] Once processor control is transferred to the critical execution manager 140, to determine if the interruption occurred during execution of critical code, in one configuration, the critical code 160 may contain a critical code flag instruction that is executed upon entry into the critical code 160 in order to set the interference signal to indicate a reset value. The critical execution manager 140 can detect the setting of this interference signal to infer interference occurred. In another configuration, the critical code 160 may contain an idiomatic instruction which when executed utilizes critical code registers reserved for such data or instructions. At least one of such critical code registers can contain a value at the time of interruption that indicates a reset value and which the critical execution manager 140 can detect. In still another implementation, the critical execution manager 140 can obtain access to the registration or other critical code or thread saved state data structure(s) (e.g., maintained in or by the kernel or saved as part of the registration procedure) to obtain the address bounds of the critical code 160. Using this information, the critical execution manager 140 can detect interruption of the critical code based on the value of the current program counter or instruction pointer, captured or saved by the kernel at the time of interruption that indicates or identifies whether of not that instruction is within the address bounds of the critical code 160 that was interrupted. In yet another configuration, the critical execution manager 140 can detect interruption of the critical code 160 if such an interruption occurred during execution of a blocking call instruction that sets a flag or other indicator, since such an instruction would only be used within the critical code 160.

[0077] It is to be understood that these are example techniques to determine if the interruption occurred during execution of critical code, and if so, if the interference signal 163 indicates a reset value. Other techniques can be used as well. It is also to be understood that a portion of the critical execution manager 140 can be built into or configured to operate as part of the operating system 130 and thus some or all of the aforementioned functionality need not be natively present in the operating system.

[0078] In step 205, if the critical execution manager 140 detects that the interference signal 163 indicates a reset value, processing proceeds to step 206.

[0079] In step 206, the critical execution manager 140 performs a reset operation on the critical code to reset the current state of the critical code to allow execution of the critical code while avoiding interference caused from handling the interruption. The interference, such as another process modifying memory or register information associated with the interrupted critical code 160, may or may not actually exist. In any event, if the interference signal indicates a reset value, the critical execution manager 140 performs a reset operation nonetheless.

[0080] As will be explained shortly, different types of reset operations are possible depending upon which embodiment of the invention is used. Generally, a roll-back reset operation is possible in which the critical execution manager 140 resets the current state of the critical code 160 in order to resume execution of the critical code 160 from its beginning or start point. In an alternative embodiment of the invention, the reset operation comprises a roll-forward technique in which processing can proceed from the point of interruption within the critical code 160. Each of these techniques will be explained in detail below.

[0081] After processing the reset operation in step 206, processing proceeds to step 207 at which point the computerized device 100 returns to execution of the critical code using the current state of the critical code.

[0082] Also as illustrated by the flow chart of processing steps shown in FIG. 2, in step 205, if the critical execution manager 140 determines that an interference signal 163 does not indicate a reset value, processing also proceeds to step 207 to return to execution of the critical code 160 without performing a reset operation.

[0083] Following the processing of step 207, processing proceeds back to step 202 to continue execution of the critical code either until the critical code 160 is complete or until another interruption occurs to the critical code at which point the processing explained above from step 203 through 207 is repeated.

[0084] According to the aforementioned processing techniques, embodiments of the invention allow critical code operating within a first process or thread such as a non-operating system user thread 150-1 to execute in the presence of interruptions which may cause interference to the critical code 160. Since the operating system 130 is configured to return processing control to the critical execution manager 140 instead of returning control to the critical code 160, the critical execution manager 140 can make a determination if a reset operation is required in order to avoid interference caused by the interruption. If the reset operation is required, the critical execution manager can perform either a roll-back or roll-forward reset operation and then can cause whichever processor 110-1 or 110-2 is scheduled to execute the critical code 160 next to begin execution of the critical code while avoiding any actual or possible interference from the interruption.

[0085] FIG. 3 illustrates an example of a timing and processing flow control diagram for operation of a processing thread 150 that contains critical code 160 which experiences an interruption within a computerized device configured according to example embodiments of the invention.

[0086] As illustrated in FIG. 3, a timeline 290 progresses from left to right in the figure. FIG. 3 also indicates, in parallel with the timeline 290, the beginning 252 and ending 260 of this example critical code 160.

[0087] Beginning on the left-hand side of the timeline 290 at location 250, a processor 110 within a computerized device begins execution of a thread 150-1 containing critical code 160. At location 251, either before, at the moment of, or during execution of the thread 150 (or upon entry into execution of the critical code), processing within the computerized device 100 registers the critical code 160 with a critical execution manager registrar 140-1. This registration processing in one embodiment of the invention identifies the address locations of the beginning of the critical code (i.e., location 252 in FIG. 3) to the operating system 130 and further operates the aforementioned scheduler activation technique in order to register the critical execution manager 140 as a device driver which should be operated upon returning from an interrupt to the critical code. Execution of the thread then continues to location 252 at which point the processor begins or enters execution of the critical code 160. Execution of the critical code continues until location 253 at which point an interrupt to execution of the critical code 160 occurs.

[0088] In response to the interrupt occurring at location 253, processing control is passed to the kernel 345 of the operating system in order to handle the interrupt at location 254. Within the operating system 130, the kernel interrupt handler 350 handles the interrupt. As illustrated in this example, the kernel 345 may at this point begin execution of another thread (e.g., 150-2 in FIG. 1) or process upon the processor 110-1 which was previously executing the critical code 160. This may cause interference to data or information related to the critical code 160. Alternatively, the kernel may decide during handling of the interrupt that the thread containing the critical code 160 is to be migrated to a different processor in a multiprocessing computerized device 100. This is another example of interference, since the state of the processor specific memory information 170-2 (FIG. 1) for processor B 110-2 will be different that the state of the processor specific memory information 170-1 which the critical code 160 was previously accessing prior to the interruption. As an example, the offsets to data in each of these sets of memory information 170-1 and 170-2 may be different.

[0089] In any event, after handling of the interrupt is complete, the kernel 345 invokes execution of the critical execution manager reset operator 140-2 at location 255. As noted above, this occurs due to the registration procedure previously performed at location 251 in which the operating system is instructed or otherwise informed that the critical execution manager reset operator 140-2 is a device driver that should be executed by the operating system 130 upon completion of an interruption to the registered thread 150-1 containing the critical code 160.

[0090] The critical execution manager reset operator 140-2 in this embodiment of the invention operates in user space and includes a reset manager 140-4 and an interference signal detector 140-3. Generally, the interference signal detector 140-3 can detect if the interruption occurred in critical code 160 (e.g., by using the registered address bounds of the critical code in comparison with kernel interrupt saved state information, such as a program counter address of the interrupted instruction or by other methods) to determine that critical code 160 was actually interrupted (as opposed to the interruption occurring elsewhere in the thread 150-1). Next, the interference signal detector 140-3 can determine if the interference signal (255 in FIG. 3 or 163 in FIG. 1) indicates a reset value in a variety of ways depending upon which embodiment of the invention is implemented.

[0091] In one embodiment of the invention, the interference signal detector 140-3 can detect that the interference signal indicates a reset value by examining the interference signal (e.g., the value of a flag or register) set as a result of the operation of execution of the critical code. According to another embodiment of the invention, the interference signal detector 140-4 can detect that the interference signal indicates a reset value by determining that a second thread or process (e.g., 150-2 in FIG. 1) was executed on a processor (e.g., 110-1) associated with the first thread containing the critical code 160 during handling of the interruption (e.g., by conferring with the kernel in the operating system 130). In other words, if another thread (e.g., 150-2) executed on the same processor (e.g., 110-1) as the thread (150-1) that contains the critical code 160 (i.e., the thread that was interrupted), an interference signal 163 indicates a reset value and the interference signal detector 140-4 detects this condition. In still a further embodiment, the interference signal detector 140-4 can utilize a processor identification contained within the interference signal 163 to determine that the thread containing the critical code 160 has been migrated to a processor that is different than a processor upon which that thread was executing at the time of interruption. In still another configuration, the interference signal may indicate a reset value if another registered thread (i.e., another thread that has also registered itself as requiring use of the critical section in an atomic manner) has run on the processor during the interrupt time period. In such a case, if other unregistered thread ran, there may be no need to perform a reset operation as it may be assumed that such threads do not access critical code and thus interference could not occur.

[0092] In another embodiment of the invention, the portion of the critical execution manger 140 that is integrated into the operating system 130 may or may not be required to deliver an upcall containing the interference signal 163 from the kernel space to the criticial execution manager portion 140 that operates in user space if one of the aforementioned conditions are not met. In other words, the operating system can be configured with a portion of the critical execution manager 140 that makes a determination if a reset operation is required based one or more on the aforementioned conditions and indicates this in the interference signal 163. If no interference condition(s) exists, then a call from the operating system 130 to the user space portion of the critical execution manager 140 might be avoided altogether and processing can resume in the thread at the point of interruption. Thus, if there is no chance of interference or there is none detected, the thread can resume execution at the point of interruption, as shown in FIG. 3 by the processing path 199.

[0093] Once the interference signal detector 140-4 performs the processing of step 205 from FIG. 2 to determine that an interference signal indicates a reset value, the reset manager 140-3 performs the processing of step 206 as discussed above to perform the reset operation on the critical code.

[0094] According to one embodiment of the invention, the reset manager 140-3 can perform the reset operation using a roll-back operation as shown at location 256-1 in FIG. 3 in order to return execution to the beginning of the critical code at location 252. According to another embodiment of the invention, the reset manager 143 can perform a roll-forward operation as indicated at location 256-2 in FIG. 3 in order to return execution to the point at which the interrupt occurred in the critical code (i.e., location 253 in FIG. 3).

[0095] In this manner, the critical execution manager reset operator 140-2 can either roll-forward or roll-back the current state of the critical code 160 to either the beginning of the critical code or to the point in the critical code at which the interrupt occurred in order to avoid interference from the interruption. As will be explained in detail shortly, both the roll-forward and roll-back operations allow a general resetting of the state of the critical code 160 such that any modifications, for example, to processor registers, instruction pointers or shared memory locations which are modified or changed during interruption will have no effect on further execution of the critical code. This results in the critical code 160 being subsequently executed atomically no matter how many interrupts occur during execution of the critical code. In other words, the processing flow illustrated in FIG. 3 can repeat until the critical code is able to execute from the beginning at location 252 to the critical code section end at location 260.

[0096] In one embodiment of the invention, any instructions within the critical code 160 that cause memory information to be saved or committed such as writing the contents of registers out to the appropriate set of memory information 170-1 or 170-2 are performed towards the end 260 of the critical code 160. In this manner, the reset operation can be assured that the critical code has not made modifications or commitments to shared memory that might be accessible to other processes or threads in the event of interruption. It is noted that processing path 259 in FIG. 3 is shown for completeness and illustrates normal execution flow for an interrupt without the use of the invention.

[0097] FIG. 4 illustrates a more detailed architecture and processing flow diagram of a computerized device configured according to one embodiment of the invention that implements the aforementioned processing techniques. The processing flow illustrated in FIG. 4 is similar to that of FIG. 3 in that a timeline 390 progresses from left to right. The operation of the architecture and processing flow illustrated in FIG. 4 will be discussed in relation to the flow chart of processing steps shown in FIGS. 5 and 6 that show more detailed processing operations of one embodiment of the invention.

[0098] In step 400 in FIG. 5, the operating system 130 in FIG. 4 begins execution of a first thread on processor A 110-1 (FIG. 1) at location 351. During execution, the first thread 150-1 accesses 321-1 processor information A 115-1 associated with the processor A 110-1 and further accesses 165-1 memory information A 170-1 which is processor specific memory information reserved for use by processes executing on processor A 110-1.

[0099] In step 401, the critical code 160 is registered with the operating system 130 at location 352 in FIG. 4 using the critical execution manager registrar 141. The registration process within step 209 results of the creation 303 of the first thread saved state 341 within the operating system 130. In one embodiment, the first thread saved state may simply be the address of an instruction in the critical execution manager 140 to which processing is to be transferred upon return from an interrupt to the thread 150-1. Note that such a registration process can be done at any time prior to or during execution of the critical code 160.

[0100] Specifically according to this registration procedure, in step 402, the critical execution manager registrar 140-1 stores at least one address associated with the critical code 160 with the operating system 130 in a computerized device as the first thread saved state (associated with the first thread 150-1). The stored address indicates a location of the critical code in which the operation of returning to execution of the critical code can begin. In another embodiment of step 402, the entire address range of critical code instructions is stored.

[0101] Next, in step 403, the critical execution manager registrar 140-1 registers the critical code 160 such that the operating system 130 will invoke execution of the critical execution manager 140 (i.e., the critical execution manager interference signal detector 140-3) instead of the critical code 160 after handling an interruption. This registration process can be achieved in one embodiment of the invention using “ioctl” (i.e., input output control) calls to the scheduler activation hook within an operating system 130 in order to register the critical execution manager interference signal detector 140-3 as a device driver that is to be activated upon returning in the operating system from an interruption to the critical code 160.

[0102] After registration is complete, processing proceeds to step 404 at which point the processor executes normal thread code and the critical code 160 until an interruption or trap occurs to the critical code 160 as indicated at location 353 in FIG. 4. In certain embodiments of the invention, during execution of the critical code 160, the interference signal 163 may be set via setting a flag, register or other indicator to indicate a reset value and hence a reset operation may be required, as shown in step 405 in FIG. 5.

[0103] In one embodiment of the invention as shown in step 406, a critical code flag instruction may be executed to set the interference signal to indicate a reset value. The critical code flag instruction may be an instruction that sets a processor status word flag to indicate that execution has entered into an area of critical code and thus interference must be avoided in the event of any interruption. Upon exit of the critical code, such a flag can be cleared by a similar critical code flag instruction in order to indicate that execution is no longer proceeding within critical code 160.

[0104] In another embodiment of the invention as shown in step 407, the critical code executes a blocking call instruction which can produce a result that the critical execution manager reset operator 140-3 can interpret as a reset value for the interference signal 163.

[0105] In yet another embodiment of the invention, execution of the critical code can involve operation or execution of an idiomatic instruction that uses special registers reserved for critical code operations only. A value in one or more of such registers can be used as a trigger for the interference signal to indicate a reset value.

[0106] Once execution of the critical code is interrupted in step 404, processing proceeds to step 409 at which point the operating system handles the interruption as shown in FIG. 4 at location 354. In the embodiment illustrated in FIG. 4, a kernel interrupt handler 350 handles the interruption that may cause interference to processor information 115 or memory information 170 associated with the interrupted critical code 160. Upon returning to (e.g., entering or vectoring into) the kernel at location 354 in FIG. 4, in order to handle the interruption, the operating system kernel interrupt handler 350 stores the processor information A 115-1 as part of its standard kernel data structures for any process which is interrupted. This processing is shown at location numeral 354-1 in which the kernel interrupt handler 350 deposits this information into the first thread saved state 341. In other words, when the operating system 130 interrupts an executing process, the operating system 130 saves register information and program counter information identifying the interruption point within the code of the interrupted process.

[0107] As will be explained shortly, this information may be of used to the critical execution manager reset operator upon performing a roll-forward reset operation, as well as for determining (as explained above) that the interruption occurred within the critical code 160.

[0108] Different types of interference are illustrated in FIG. 4 at locations 310-1 through 310-3. In particular, the kernel interrupt handler 350 may schedule a second thread 150-2 to execute on processor A 110-1. This in and of itself may be considered interference for purposes of embodiments of this invention. Alternatively, interference may occur when the second thread 150-2 accesses 310-1 processor information A 115-1 or when the second thread 150-2 accesses memory information A 170-1 during its execution. Alternatively, the second thread may execute critical code 160 which is shared critical code thus disturbing the state of the shared data accessible to the critical code 160.

[0109] In any event, after the operating system handles interruption in step 409, processing proceeds to step 410.

[0110] In step 410, the operating system 130 completes handling of the interruption and operates the scheduler activation to activate the critical execution manager reset operator 140-3 as a device driver. Recall that the critical execution manager interference signal detector 140-3 was registered as a device driver to be executed upon returning from interruption to the first thread 150-1 (or upon interruption to the critical code 160). This is illustrated by the interference signal 163 in FIG. 4 entering in the operating system 130 into the critical execution manager (i.e., into the interference signal detector 140-3). The interference signal 163 passed from the kernel interrupt handler 350 to the critical execution manager interference signal detector 140-3 (i.e., to the registered instruction) allows the critical execution manager interference signal detector 140-3 to determine if a reset operation is required or not on the critical code 160.

[0111] Directing attention now to the continuation of processing at step 411 at the top of FIG. 6, the critical execution manager interference signal detector 140-3 receives the interference signal 163 containing processor identification information 330 and containing or otherwise identifying the first thread saved state information 341 maintained within the operating system 130. That is, in this example embodiment of the invention and as illustrated in FIG. 4 at locations 163 and 357, the critical execution manager interference signal detector 140-3 receives the processor identification 330 within the interference signal 163. This signal can also identify the kernel data structures 341 or first thread saved state that includes the saved state of the interrupted process (the first thread 150-1 in this example). As a result of receiving this information, the critical execution manager interference signal detector 140-3 is able to determine which processor 110-1 or 110-2 the critical code 160 is scheduled (i.e., by the operating system) to execute upon next and is able to access the kernel and/or registered or first thread saved state information 341 that existed (or that was registered) prior to the interruption of the critical code 160 and that was saved during registration.

[0112] In step 412, the critical execution manager reset operator 140-2 operates the interference signal detector 140-3 (illustrated in FIGS. 3 and 4) in order to detect if the interference signal 163 indicates a reset value. As noted above, the interference signal 163 contains or provides a pointer to the first thread saved state information 341, which may contain values copied from kernel data structures and/or registration information (i.e., first thread saved state). Accordingly, in step 412, if the critical execution manager interference signal detector 140-3 determines that a program counter or instruction pointer within the saved state references or contains an address of an instruction that exists within the address range of the registered critical code 160, then the critical execution manager interference signal detector perator 140-3 can infer or determine that the interruption took place during execution of a critical code instruction. In other words, since the critical code 160 is registered with the critical execution manager registrar 141 in order to save the address range of critical code instructions associated with the first thread 150-1, then upon occurrence of the interruption, the critical execution manager interference signal detector 140-3 can compare the instruction pointer of the interrupted instruction with the address range of the critical code to determine if the interrupted instruction is part of a critical code. Other techniques as noted above can be used to determine that critical code was being executed at the time of interruption.

[0113] Once it is determined that the interruption occurred during operation or execution of the critical code, the critical execution manager interference signal detector 140-3 performs one or more of steps 413 through 415 to determine if the interference signal indicates a reset value. In a conservative implementation as illustrated in step 413 in FIG. 6, the critical execution manager interference signal detector 140-3 determines if the reset value was set during execution of the critical code. This may be done when the critical execution manager interference signal detector 140-3 simply identifies that the critical code 160 was interrupted. Alternatively, an instruction such as a critical code flag instruction may have to have been executed within the critical code in order to set a flag or other signal or value indicating that the interrupted instruction is part of the critical code 160.

[0114] In another embodiment of the invention shown in step 414, the critical execution manager interference signal detector 140-3 can determine if a second thread executed on a processor that interrupted the critical code. In such a case, it may be that interference is caused by the second thread (e.g., 150-2, also registered to access the critical code in this example) referencing processor or memory information 115, 170 related to the critical code 160.

[0115] In yet another embodiment of the invention as illustrated in step 415, the critical execution manager reset operator 140-3 can determine if the thread containing the critical code 160 has been scheduled for migration to another processor (e.g., 110-2) other than the processor (e.g., 110-1) upon from which it was interrupted.

[0116] It is to be understood that these are examples of techniques for determining that an interference signal 163 indicates a reset value in which case the critical execution manager reset operator 143 performs a reset operation. Other techniques may be used as well to determine that interference may be present upon attempting to return to execution of critical code that was interrupted for any reason. Any of such techniques may be employed to set the value of interference signal 163 to indicate a reset value or to otherwise trigger, in some other manner, operation of the critical execution manager reset operator 140-3 in order to perform a reset operation.

[0117] In step 416, the critical execution manager reset operator performs a reset operation as indicated at location 358 in FIG. 4. According to different embodiments of the invention, the reset operation may be carried out using a roll-back operation or a roll-forward operation as respectively illustrated by steps 417 and 420 in FIG. 6.

[0118] In the roll-back operation technique as illustrated in step 417, the critical execution manager reset operator 143 performs a roll-back operation to reset the current state of the critical code to allow execution to return to the start of the critical code 160. This was illustrated above with respect to FIG. 3 at location 256-1.

[0119] Details of one embodiment of a roll-back operation are illustrated with respect to steps 418 and 419 in FIG. 6.

[0120] In step 418, the roll-back operation includes resetting a program counter to reference an address (e.g., a starting address) associated with the critical code stored within the operating system during the registering process. This address may be the beginning address of the first instruction of the critical code. Accordingly, step 418 modifies a program counter which references the instruction that was interrupted to now reference an instruction existing at the beginning of the critical code.

[0121] Next, in step 419, an optional procedure is performed according to one embodiment of the invention in which the critical execution manager reset operator 143 performs at least one compensation transaction to reset register interference of registers associated with the critical code that were disturbed or otherwise modified by the interruption. In particular, in step 419, the compensation transaction (one or more) is performed to undo or reverse any modification to register contents associated with the critical code that may have resulted due to the interruption in order to bring the register contents back to the way it existed at the start of the critical code 160.

[0122] To illustrate the usefulness of a compensation transaction, consider the following scenario: in a roll-back operation that does not utilize a compensation transaction, the program counter is reset to point to be the beginning of the critical code. Then, upon returning to execution of the critical code, processing can proceed using the current set of register values associated with the critical code. However, certain register values may have been modified during processing which occurs during the interruption, or alternatively, the register contents associated with the critical code is only as good as the contents which existed just prior to the interruption, as saved by the kernal. In such cases, the operation of step 419 of performing one or more compensation transactions can be used to reverse effects on interruption processing which modified contents of registers associated with the critical code. Alternatively, compensation transactions can be used to undo register operations of the critical code to revert the register state to the way it existed at the time of the beginning of the critical code. In this manner, the critical code can execute from its beginning due to the processing of step 418 and step 419 and the register contents is accurately represented for use by the critical code 160.

[0123] According to the roll-forward operation illustrated in step 420, the critical execution manager reset operator 143 can perform a roll-forward operation to reset the current state of the critical code to allow the return to execution of the critical code at the point of interruption of the critical code. This is illustrated in FIG. 3 as discussed above at location numeral 256-2. According to the role forward technique, processing does not revert to the beginning of the critical code 160. Instead, register and processor information and program counter information are reset as obtained from the first thread saved state information 341 saved in response to the kernel interrupt handler 350 processing the interruption of the critical code 160 at location 354 in FIG. 4. In other words, the roll-forward operation can rely on the kernel data structures which maintain the state of an interrupted process in order to refresh the state (registers, program counter, flags, etc.) prior to beginning execution of the critical code processing at the point in which it was interrupted.

[0124] Accordingly, in step 421, the critical execution manager reset operator 143 accesses processor information related to the interrupted thread 150-1 as saved within the first thread saved state information 341. This processor information can include register values, flag values, program or instruction pointer information and other information that is related to the execution of the critical code immediately prior to the interruption.

[0125] Next, in step 422, the role forward operation resets the program counter for the critical code to reference the instruction that was interrupted.

[0126] Next, in step 423, the critical execution manager reset operator 143 reloads register information obtained from access to the stored processor information (e.g., stored in 341) from step 421. Essentially then, the roll-forward operation is similar to conventional operating system techniques for returning to execution of an interrupted process by referencing the former program counter information and register information associated with the process in order to begin execution of the process again, except that the roll-forward reset operation can further rely on step 424, to be discussed next, in order to avoid interference from the interruption.

[0127] After either the roll-forward or roll-back operation has been completed in order to reset the current state of the critical code to execution point, in step 424, the reset operation is continued by the critical execution manager reset operator 143 which uses processor identification information 330 received in interference signal 163 to adjust an address offset of data referenced by the critical code 160 within memory information 170 associated with a processor 110 upon which the critical code 160 is scheduled to execute next. In other words, the processor identification 330 received within the interference signal 163 allows the critical execution manager reset operator 140-3 to insure that memory references made by the critical code 160 upon re-execution properly correspond to memory information 170 associated with the appropriate processor 110 which is to next execute the critical code. As an example, if the critical code 160 is migrated to execute on another processor that is different from the processor upon which the critical code was interrupted from, the identity of this new processor which is to execute the critical code can be utilized by the critical execution manager reset operator 143 in step 424 to adjust offsets for all memory addresses that reference memory locations within the new set of memory information 170 that is respectively related to the new processor which is to execute the critical code. Since offsets to data structures utilized by critical code can be different in each set of memory information 170 which is respectively associated with a distinct respective processor 110, the processor identification can be used by the critical execution manager 140 in step 424 to adjust such address offsets accordingly.

[0128] After processing the reset operation in step 416, processing control is then released from the critical execution manager reset operator 143 to return to execution of the critical code 160 is shown at location 359 within FIG. 4.

[0129] In this manner, the aforementioned techniques allow for execution of critical code while sustaining interruptions to the critical code and while also avoiding interference caused by such interruptions. In addition, no locking or unlocking techniques are required for operation of embodiments of the invention and thus conventional techniques that present problems such as a convoy problem are avoided. Further still, since portions of the critical execution manager 140 can operate with the user space, embodiments of the invention make atomic execution of critical code fully available to user processes. Further still, embodiments of the invention do not rely upon placement of predefined values into memory locations that can be modified by interrupt processing which then must be tested upon return to critical code.

[0130] The following appendix (Appendix A) contains the contents of a paper describing operational details and advantages of certain embodiments of the invention. The contents of the appendix and its teachings are to be considered part of the specification and detailed description of embodiments of the invention disclosed herein. It is also to be understood that embodiments of the invention described in this appendix a net intended to be limiting of any of the other embodiments discussed above.

[0131] Those skilled in the art will understand that there can be many variations made to the embodiments explained above while still achieving the same objective of those embodiments and the invention in general. Such variations are intended to be covered by the scope of this invention. As such, the foregoing descriptions of embodiments of the invention are not intended to be limiting. Rather, any limitations to the invention are presented in the claims that follow Appendix A.

[0132] The following paper entitled “ACCURATE PER-PROCESSOR RESOURCE ALLOCATION IN THE PRESENCE OF PREEMPTION” is to be considered part of the disclosure of the present invention and describes example embodiments thereof.

[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]