Electrical computers and digital data processing systems: input/ – Access locking
Reexamination Certificate
2001-11-20
2004-09-28
Ray, Gopal C. (Department: 2111)
Electrical computers and digital data processing systems: input/
Access locking
C710S263000, C710S266000, C710S048000, C710S269000
Reexamination Certificate
active
06799236
ABSTRACT:
FIELD OF THE INVENTION
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.
BACKGROUND OF THE INVENTION
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.).
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.
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.
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.
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.
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.
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
Dice David
Garthwaite Alexander T.
Chapin & Huang LLC
Chapin, Esq. Barry W.
Ray Gopal C.
Sun Microsystems Inc.
LandOfFree
Methods and apparatus for executing code while avoiding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for executing code while avoiding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for executing code while avoiding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214497