Transaction processing in transactional memory

The present invention relates to transaction processing in transaction memory.

Parallel programming for shared memory multiprocessor systems includes multithreaded performance and allows access to the same data. Multithreading runs on a multiprocessor, multiprocessor core, or other class of parallel processing that is connected to memory shared between processors. The shared memory model is the most commonly deployed method of multithreaded transmission. Thereby, a multithreaded program can be created in much the same way as a sequential program. To run the shared memory model, parallel programming is careful to avoid parallel access and use of shared data, which can lead to race conditions and other undesired situations such as their equivalents.

Locking is a common solution to avoid the problem of parallel access to shared data. Locking is primarily based on the assumption that a variable accessed by one thread can be attempted by another thread, but that variable can only be used by one thread at a time. Locking allows one thread to control a variable until it is unlocked, and to prevent other threads from modifying the variable. Lock-based protocols are well known, but are often considered difficult to use. The use of locks with coarse particle size protects relatively large data, but the use of locks with coarse particle size usually does not process efficiently. Threads block each other even when they do not interfere, and such locks are a source of contention. Alternatively, the use of locks at a finer granularity can alleviate scalability issues, but the locks pose other problems. The reason is that the convention of locking, which guarantees accuracy and avoids deadlocks, is complex and error-prone.

Another solution is to implement an application that uses transactional memory. When a transactional memory system manages a thread's memory access by executing the thread and attempts to access the same memory location in a conflicting manner by two or more threads, it rolls back or originates the effect of the thread. Try to return to. Transaction memory systems can be implemented using hardware and / or software components. A software-based transactional memory system can make a software runtime library and / or a runtime execution environment meaningful and / or use a compiler. Transaction memory is shared on the assumption that variables read by one thread are unlikely to be modified by another thread, and therefore variables can be shared without severe adverse effects on program scalability. Often implemented as a compiler-level parallel control mechanism for controlling access to memory. However, tracking memory access in a transactional memory system can possibly add overhead to the execution of the program.

One advantage of transactional memory in coarse lock-based protocols is increased parallelism. In transaction memory, threads do not have to wait for access to data. Different threads can safely and simultaneously modify different parts of a data structure that are normally protected under the same lock. In many realistic parallel programs, despite the overhead of retrying a failed transaction, contention rarely occurs, so a coarse-grained lock-based protocol that starts with a few processors or processor cores. Performance is improved by using.

Despite being the subject of transaction memory guarantees and extensive research, there are obstacles to widespread use and acceptance. For example, programmers are hesitant to use transaction memory because they are unfamiliar with transaction memory and lack practical user-friendly practices.

This overview is provided in simple form to provide an excerpt of the concepts described further in the detailed description. This summary is not intended to identify the main or essential features of the claims, nor is it intended to be used to limit the scope of the claims.

This disclosure aims to integrate the concept of transaction memory at the compiler level into higher level traditional transaction processing (such as database transactions). Atomic blocks at the compiler level are designated as atomic block transactions and can contain atomic and independent features. Behavior within this atomic block transaction involves enlisting the resource manager from the available resource manager repository. The repository can manage transaction memory, including a pre-programmed memory resource manager. As seen in traditional transactions, the commit protocol can be used to determine if the operation was successful and the result can be exposed outside the transaction. However, unlike traditional transactions, this transaction does not necessarily fail if some of the actions are not valid. Rather, memory conflicts cause rollbacks of all resource managers, including memory, and re-execution of atomic block transactions. The re-execution can be repeated as long as necessary until all operations, including those of the memory resource manager, are successfully enabled.

The accompanying drawings are included for further understanding of the embodiments, incorporated into this specification, and form part of the specification. These drawings are provided to show the embodiments and to explain the principles of the embodiments with descriptions. Other embodiments, and many of the intended advantages of the embodiments, will be readily recognized as they become better understood with reference to the detailed description below. The elements of these drawings are not necessarily scale ratios that are related to each other. Similar reference numbers indicate corresponding similar parts.

<figref num="1">FIG. 6 is a block diagram showing one of many possible examples of computing devices that implement the features of the present disclosure.</figref><figref num="2">It is a block diagram which shows an example of the transaction memory processing system executed in the example of the computing system of FIG.</figref><figref num="3">It is a flow chart which shows an example of the process used in the transaction memory processing system of FIG.</figref><figref num="4">It is a schematic diagram which shows an example of the process of the commit protocol of FIG. 2 with respect to time series.</figref>

Reference is made to the accompanying drawings in the following detailed description. These accompanying drawings provide detailed description, and in these drawings, by way of example, show specific embodiments in which the present invention can be carried out. It is understood that other embodiments can be used and structural or logical changes can be made without departing from the scope of the invention. Therefore, the following detailed description is not taken in a limited sense, and the scope of the invention is defined by the appended claims. It is understood that the features of the various exemplary embodiments described herein can be combined with each other unless otherwise noted.

FIG. 1 shows an exemplary computer system that can be adopted as an operating environment and includes a computing device such as the computing device 100. In a basic configuration, the computing device 100 typically includes a processor architecture with at least two processors (ie, processor 102) and memory 104. Depending on the exact configuration and type of computing device, memory 104 may be volatile (such as random access memory), non-volatile (such as ROM (read only memory), flash memory), or these. It can be a combination of the two. This basic configuration is shown by line 106 in FIG. Computing devices can take several forms, one or more. Such forms include personal computers, servers, handheld devices, consumer electronics (such as video game consoles), or anything else.

The computing device 100 can also have additional features / functions. For example, computing device 100 includes, but is not limited to, magnetic or optical disks, or semiconductor memory, or flash storage devices, such as, but not limited to, removable storage 108 and non-detachable storage 110. It can also include storage (detachable and / or non-detachable). Computer storage media are volatile and non-volatile, removable and removable in any suitable method or technique for storing information such as computer-readable instructions, data structures, program modules, or other data. Includes non-detachable media. Memory 104, removable storage 108, and non-detachable storage 110 are all examples of computer storage media. Computer storage media include RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, DVD (digital versatile). disc), or other optical storage, magnetic cassette, magnetic tape, magnetic disk storage or other magnetic storage device, USB (universal serial bus) flash drive, flash memory card, or other flash storage device, or desired information Including, but not limited to, any other medium that can be used to store and be accessible by the compute device 100. Any such computer storage medium can be part of the computing device 100.

The computing device 100 includes one or more communication connections 114 that allow the computing device 100 to communicate with other computers / applications / users 115. The computing device 100 can also include an input device (s) 112 such as a keyboard, a pointing device (eg, a mouse), a pen, a voice input device, and a touch input device. The computing device 100 can also include an output device (s) 111 such as a display, a speaker, and a printer.

The computing system 100 can be configured to run operating system software programs and one or more software applications that make up the system platform. In one example, the computing system 100 includes a software component called a runtime environment. The runtime environment can be included as part of the operating system or later as a software download. The run-time environment typically contains pre-coded solutions to common programming problems to help software developers create software programs, such as applications, to run in the run-time environment. .. The run-time environment typically also includes virtual machines, which allow software applications to run in the run-time environment, eliminating the need for programmers to consider the performance of a particular processor 102. There are many examples of run-time environments, including Microsoft's .Net CLR (Common Language Routine) in Redmond, Washington, and C ++ routines.

FIG. 2 shows an example of the transaction memory processing system 200. The transaction memory processing system 200 can be called in the runtime environment to support atomic block transaction 202. Atomic block transaction 202 can be an atomic block of software code in a thread. Atomic block transaction 202 includes transaction boundaries 201, 203. Transaction boundaries 201 and 203 represent atomic blocks and identify the code involved in the transaction memory processing system 200. Atomic block transaction 202 is shown to include at least transaction memory operation 204, but also a second, i.e., non-memory operation 206. Transaction memory operation 204 provides a transaction memory memory operation. Other actions, such as actions that affect variables and actions that have side effects, can be included in atomic block transactions. System 200 includes at least one memory resource manager corresponding to at least one memory operation, such as memory resource manager 208 corresponding to transactional memory operation 204. System 200 has at least one non-memory resource that corresponds to at least one non-memory operation, such as the non-memory resource manager 210 that participates in transaction 202 corresponding to the second non-memory operation 206 in this example. Can include managers. The resource managers 208 and 210 manage resources 212 and 214 suitable for the operations involved in transaction 202, respectively. The behavior of resource managers 208 and 210 is coordinated with transaction manager 216. Transaction manager 216 works with resource managers 208 and 210 to ensure the atomicity and independence of transaction 202. Transa Action manager 216 implements commit protocol 218. Resource managers 208 and 210 are also involved in commit protocol 218. In another example, an atomic block transaction can include three or more operations that correspond to multiple resource managers and resources.

Transaction 202 is a sequence of actions combined with each other performed by a single thread. Threads complete data modification in shared memory with or without consideration of other threads running concurrently on other processors. In any case, after the transaction completes, the transaction memory verifies that no other thread has made any changes to the accessed data at the same time. If the changes are enabled and the activation is successful, the enabled changes are immutable in the commit operation. If the activation fails, the changes are undone or "rolled back" and transaction 202 is rerun until the activation is successful.

Transaction 202 possesses the characteristics of atomicity and independence. Transactions are atomic and instantaneous and logical. If one operation fails, all transactions fail. Furthermore, since the transaction is independent of other threads, the variable is not exposed to other threads in the intermediate state. In some embodiments, independence is provided only to threads running within a transaction, but threads accessing data without transaction protection may encounter intermediate states in simultaneous transactions. Absent. When the end of the block is reached, the transaction is committed, failed (aborted) or rolled back, and re-executed. Therefore, the unit that commits or fails is transaction 202 rather than the entire process. The state returns to its original form rather than exposing the intermediate state. In this respect, transaction 202 is typically shown at the compiler level and is similar to a database technology transaction, i.e., a database transaction, except that it includes transaction memory. However, unlike a typical traditional transaction (eg, a database transaction), transaction 202 can be re-executed until successful.

The resource manager exists in the conventional transaction processing and manages the resources involved in the transaction. However, traditional transaction processing has so far not been used to make it automatically independent and to synchronize simultaneous access to memory. Traditional transaction processing uses a locking or transaction memory mechanism that is not connected to a traditional transaction. A feature of this example is that transaction memory management is part of a traditional transaction system, combining transaction memory with the atomic nature of traditional failures, unlike traditional transactions that do not control access to shared memory. It means that there is. The transactional memory proposal does not provide the common failure atomicity across memory and other resources. The complexity of error handling in transactional memory proposals often prevents applications from recording from a combination of partial failures or memory conflicts. Developers still provide recovery capabilities by manually creating solutions for a limited set of errors that they know how to deal with. As a result, developers suffer from productivity and quality consequences. In addition, creating a manual error-handling solution is a non-trivial task for developers. However, the examples of the present disclosure provide the atomic nature of failure by incorporating transaction memory into conventional transaction processing. Therefore, it appears that all supported actions have been performed, or nothing has been performed. The runtime environment can use the transaction memory mechanism as a pre-programmed resource manager for memory. Pre-programmed resource managers for other proper behavior can be included in libraries or repositories that can be called in the runtime environment when such resources are used.

A suitable resource manager does not exist in the resource manager's pre-programmed library In many cases, the program developer can write the resource manager to use into the program or add it to the library. This can be done in the standard way used in traditional transaction processing, which is more reliable than manually creating an error handling solution without the transaction processing system 200.

In addition, the resource managers used in traditional transactions have the characteristics of atomicity, consistency, isolation, and durability (ACID). Transaction processing in transaction memory, on the other hand, does not require consistency and persistence features. As a result, the examples of resource managers 208, 210 can be implemented as volatile resource managers rather than persistent resource managers. Volatile Resource Manager stores their state in volatile memory and does not support transaction state recovery. Therefore, developing a volatile resource manager is significantly easier than developing a persistent resource manager. For transaction processing system 200, the volatile resource manager uses fewer system resources than the persistent resource manager. An example of transaction manager 216, which works well with multiple volatile resource managers, is the available lightweight transaction manager. This transaction manager can significantly reduce the overhead that results from a more persistent transaction manager. Other examples can include a persistence transaction manager or a resource manager.

Resource managers 208, 210 automatically participate in transaction 202 and commit or roll back to the changes made to those states, depending on the outcome of the transaction. The run-time environment can automate transaction participation and transaction management for transaction resources 212, 214. Upon participation of resources 212 and 214 in transaction 202, the resource informs the transaction manager that actions 204 and 206 want to perform the work of the transaction contrary to the resource. Next, the operations 204 and 206 perform actions contrary to the resources 212 and 214. In the absence of functional errors or conflicts, transaction manager 216 applies commit protocol 218 and requests resources 212, 214 through resource managers 208, 210 to commit the changes made to that state. To do. If either resource manager 208 or 210 encounters an error, transaction manager 216 triggers rollback of all changes made within the transaction by actions 204 and 206. Otherwise, transaction manager 216 will commit the transaction. In either case, transaction manager 216 can communicate the decision to resource managers 208, 210.

In one example, the memory resource manager 208 initially acts as a transaction manager before another resource manager participates in transaction 202. If no other resource behavior occurs, the resource manager 208 can run itself without the higher level transaction manager 216. Once another resource manager, such as the non-memory resource manager 210, joins, the transaction processing system 200 advances transaction 202 from a "memory-only transaction" to a transaction that employs transaction manager 216. The memory resource 208 becomes the resource manager.

Figure 3 shows an example of the process used in transaction processing combined with transaction memory with reference number 300. At reference number 302, transaction 202 executes in the example of transaction memory processing system 200. A transactional action (s) calls a resource. At reference number 304, the process requests that the appropriate resource manager automatically join to work with the resource. The resource manager checks and determines if it is already requested in the transaction. If not requested, the resource manager will join before the corresponding action is taken. Resource Manager 210 manages affected memory changes under the control of transactional memory. Then at reference number 306, the action can be applied to the resource. At reference number 306, other actions in that transaction also run through a properly joined resource manager.

At reference number 308, at the end of the transaction, or near, transaction manager 216 calls commit protocol 218 to determine whether the transaction should be rolled back or the changes are committed in the event of a conflict with another thread. to decide. The commit protocol 218 in one example can be a one-phase commit protocol, such as when only one resource manager participates in a transaction. The commit protocol 218 in another example can be a two-phase commit protocol that includes a preparation phase 310 and a commit phase 314.

In particular, when a request to commit is received from the application, transaction manager 216 can use the two-phase commit protocol 218. The two-phase commit protocol 218 was all solicited at reference number 310 by calling a method on each of the participating resource managers 208, 210 to get the corresponding vote on the transaction. Start the participant preparation phase. Each of the resource managers 208, 210 votes for either commit or rollback by calling the prepare or rollback method, respectively. For example, a memory-driven resource manager 208 can vote to commit in the absence of memory conflicts. In the second phase of commit protocol 218, the transaction manager appropriately receives one vote from all resource managers and commits, or receives at least one vote and rolls back. respond. At reference number 312, if the transaction manager receives an all-matched commit vote from all resource managers, at reference number 314, transaction manager 216 invokes the commit method for each resource manager. This transaction manager has all the preparation methods activated. The resource manager then makes the changes permanent and completes the commit. Next, after the transaction 202 is released, the application is advanced at the reference number 316. At reference number 312, if any resource manager votes uncommit in the preparatory phase, the process behaves as follows on failure.

Failures caused by memory conflicts, as identified by Memory Resource Manager 208, can be distinguished from failures identified by non-memory resource managers that participated in the transaction. For example, a failure caused by a memory conflict can result in automatic re-execution of the transaction at reference number 318. In general, an application containing transaction 202 is unaware of the redo when it finally succeeds. In some embodiments, a failure identified by another resource manager, such as the resource manager 210 other than memory, causes the transaction to fail and not be re-executed. For example, if one or more non-memory resource managers vote against committing a transaction, and the memory resource manager votes to commit the transaction, the transaction does not rerun. At reference number 318, if memory resource manager 208 votes against a transaction commit, 320 at reference number 318, even though some or all of the non-memory resource managers vote for the commit. Rollback to 302 occurs through. In this example, re-execution occurs. The reason is that failures in non-memory resource managers may have been the result of memory conflicts. If all resource managers vote to commit the transaction, at reference number 314, the transaction commits.

Figure 4 shows an example of process 400 with a two-phase commit protocol. This commit protocol can be implemented at or near the end of transaction 202. This commit protocol can be run as elements 308 and 310 described above. The operation of the memory resource manager 208 and the transaction manager 216 is shown with reference to the simultaneous parallel time series 402, 404. The memory resource manager 208 (and other resource managers such as manager 210 or other applicable ones) sends a notice of participation 406 to transaction manager 216 that he is interested in voting in a particular transaction. When the code with the transaction ends, notification 406 notifies transaction manager 216 that transaction manager 216 is ready to start commit protocol 218. At reference number 408, the transaction manager issues a readiness command to the memory resource manager 208 and any other resource manager participating in the transaction.

After receiving the preparation command at the reference number 408, the resource managers 208 and 210 at the reference number 410 start the process of validating the respective objects. In the case of a memory resource manager, this can mean that the memory resource manager determines if there was a conflict with another thread. At reference number 412, the resource manager reports the validation result as a vote in the vote provided to transaction manager 216. If there are no conflicts, Memory Resource Manager 208 votes for commit. Alternatively, the memory resource manager 208 either votes uncommit or rejects either vote for commits from other resource managers.

If all of the resource managers vote for commit, at reference number 414, transaction manager 216 sends a commit command to all resource managers participating in the transaction, such as memory resource manager 208 and resource manager 210. Any memory changes resulting from an atomic block transaction will commit their shared state and be exposed to other threads. For memory resource managers, transactional memory does not expose any of the transaction's independent work until it receives a commit command. The work of such a commit involves unlocking, writing back (writing back) buffer memory changes, or revoking provisional memory changes. At reference number 416, once the transaction's behavior commits, the application proceeds. At reference number 418, process 400 can process other commit requests for the application waiting in the queue.

In one example, the operation of the two-phase commit protocol occurs in the order of process 400. In these examples, the transaction manager commit order is synchronized with the readiness directive and the receipt of votes from the resource manager. In another example, the transaction memory processing system is capable of translating into a pessimistic lock and avoiding participation in process 400. Alternatively, a transactional memory processing system that can guarantee the memory involved in a transaction is removed from all other memory involved in a transactional memory atomic block that can operate out of order.

The transaction memory processing system 200 can also provide the use of transactions within a transaction, that is, nested transactions. In such cases, commit protocol 218 leaves the nesting flat or nested, as in database transactions. In a flat, nested transactions look like an atomic block. If the transaction is rolled back, re-execute all transactions, including nested transactions. Alternatively, the transaction memory processing system can support partial rollback, where the nested transaction is re-executed until it commits.

Combining transaction processing with transaction memory benefits productivity. Developers can rely on the resource manager's pre-programmed code rather than writing special code to achieve error handling and failure atomicity. All memory access can be automatically included within the scope of an atomic block transaction by implementing transactional memory. The reason is that the lexical range of atomic blocks and transactions is the same. This also allows developers to avoid writing code at all combinations of addresses where one action succeeds and another does not.

Transaction resources are supported on platforms supported by Microsoft Corporation in Redmond, Washington. The platform is marketed under the trade name Microsoft SQL Server, Transaction Message Queuing (MSMQ), and the Windows Vista Transactional File System and Transactional Registry. Includes databases such as things. Transactions are DTC (Distributed Transaction Coordinator) available from Windows operating system version NT4, MTS in Windows versions prior to Windows XP, or KTM (Kernel Transaction) first available in Windows Vista. It can be created and managed using transaction management products such as those offered by Microsoft under the trade name Manager). In management code such as .NET commercially available from Microsoft, a feature of system transactions is to provide an interface for management application programs that use DTC and provide its own LTM (lightweight transaction manager). LTM also provides a mechanism for creating volatile resource managers such as memory resource managers. Such a volatile resource manager participates in a transaction along with other resource managers such as database SQL.

Although specific embodiments are shown and described herein, various alternative and / or equivalent embodiments are presented herein to those skilled in the art without departing from the scope of the invention. , And it will be appreciated that it can be replaced with the particular embodiment described. This application is intended to include any modification or modification of the particular embodiment discussed herein. Therefore, the present invention is intended to be limited only by the claims and their equivalents.