2

People often say "writing lock-free program is hard", "writing correct lock-free program is even harder", "when you do concurrent programming, you need to think in terms of transactions."

What does transaction exactly mean?

I understand that when executing a program, the operating system scheduler may let the program enter and exit the CPU many times, and the exact code location where the program is paused by the scheduler is indeterministic, which makes concurrent programming hard, since the execution flows among several threads may interleave in all kinds of ways.

So does transaction mean a single CPU instruction or instructions executed in the same CPU entry? For example, in the following code 

 x = x1 + x2 + x3;

is it possible that x1 + x2 is computed in one CPU entry, and the addition of (temporary for the sum of x1, x2) + x3 is computed in another CPU entry, and the assignment = to x is done in a third CPU entry?

Allanqunzi
  • 3,230
  • 1
  • 26
  • 58

3 Answers3

1

It is like in databases. Some instructions, that should only be executed (like) all at once without interruptions. 'Atomic operations' is another name. https://www.threadingbuildingblocks.org/docs/help/tbb_userguide/Atomic_Operations.htm

There are no strict rules about how to achieve transaction. The most straightforward way is lock. There is no guarantee about the CPU unit. So the actual answer is - yes, it is possible (or at least you should treat it like that). And the same CPU still doesn't guarantee anything, as threading hell is about the same on a single CPU unit machine.

Morgun Dmytro
  • 35
  • 9
1

Transaction, a concept at the application level, refers to what is also known as an atomic operation.

It is the same concept as database transactions, where the database maintains consistency by executing transactions, gathered from multiple parallel sessions, serially.

At the CPU level, there are also atomic operations (which are typically not called transactions) which deal with updating memory. Instructions themselves can be interrupted. Complex instructions could read memory, perform an operation on it, and then write it back. The cmpxchg) instruction reads memory, compares it with a register value, and conditionally writes it back. It is possible that the memory is changed in the mean time by another CPU. A special opcode prefix whose mnemonic is LOCK prevents such modification by other CPUs.

Yes, it is possible that the statement x = x1 + x2 + x3 executes across 3 CPU's, though in practice this won't occur, as there is a performance penalty for the scheduler to transfer one application thread to another CPU. Also, 3 interrupts would have to occur within a few CPU clock cycles.

Community
  • 1
  • 1
Kenney
  • 9,003
  • 15
  • 21
0

A transaction is an all or nothing operation, either you succeed all the way or everything is as if it never happened as far as the state of the data is concerned.

If you have a bank transaction you better be sure that what is withdrawn from your account arrives at the intended recipient or nothing happened. If your account would go into negative and the bank stops the withdrawal it should also stop the deposit at the other end or there will be some $$$ that end up missing at the banks bottom line.

Surt
  • 15,501
  • 3
  • 23
  • 39