{"id":5207,"date":"2017-03-01T21:30:00","date_gmt":"2017-03-01T21:30:00","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/transactional-memory\/"},"modified":"2023-06-26T12:20:46","modified_gmt":"2023-06-26T12:20:46","slug":"transactional-memory","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/transactional-memory\/","title":{"rendered":"Transactional Memory"},"content":{"rendered":"<p>Transactional memory is based on the idea of a transaction from the database theory. Transactional memory shall make the handling of threads a lot easier. That is for two reasons. <a href=\"https:\/\/www.modernescpp.com\/index.php\/threads-sharing-data\">Data races <\/a>and <a href=\"https:\/\/www.modernescpp.com\/index.php\/the-risk-of-mutexes\">deadlocks <\/a>disappear. Transactions are composable.<\/p>\n<p><!--more--><\/p>\n<p>A transaction is an action that has the properties <strong>A<\/strong>tomicity, <strong>C<\/strong>onsistency,<strong> I<\/strong>solation, and<strong> D<\/strong>urability (ACID). Except for the durability, all properties hold for transactional memory in C++; therefore, only three short questions are left.<\/p>\n<h2>ACI(D)<\/h2>\n<p>What means atomicity, consistency, and isolation mean for an atomic block consisting of some statements?<\/p>\n<div style=\"background: #ffffff none repeat scroll 0% 0%; overflow: auto; width: auto; border-width: 0.1em 0.1em 0.1em 0.8em;\">\n<pre style=\"margin: 0px; line-height: 125%;\">atomic{\r\n  statement1;\r\n  statement2;\r\n  statement3;\r\n}\r\n<\/pre>\n<\/div>\n<ul>\n<li><strong>Atomicity: <\/strong>Either all or no statement of the block is performed. <strong><br \/> <\/strong><\/li>\n<li><strong>Consistency: <\/strong>The system is always in a consistent state. All transactions build a total order.<\/li>\n<li><strong>Isolation: <\/strong>Each transaction runs in total isolation from the other transactions.<strong><br \/> <\/strong><\/li>\n<\/ul>\n<p>How are these properties guaranteed? A transaction remembers its initial state. Then the transaction will be performed without synchronization. If a conflict happens during execution, the transaction will be interrupted and put to its initial state. This rollback causes the transaction will be executed once more. If the initial state of the transaction even holds at the end, the transaction will be committed.<\/p>\n<p>A transaction is a kind of speculative activity that is only committed if the initial state holds. It is in contrast to a mutex, an optimistic approach. A transaction is performed without synchronization. It will only be published if no conflict with its initial state happens. A mutex is a pessimistic approach. At first, the mutex ensures that no other thread can enter the critical region. The thread will enter the critical region only if it is the exclusive owner of the mutex, and hence, all other threads are blocked.<\/p>\n<p>C++ supports transactional memory in two flavors: synchronized blocks and atomic blocks.<\/p>\n<\/p>\n<h2>Transactional Memory<\/h2>\n<p>Up to now, I only wrote about transactions. No, I will write more specifically about synchronized blocks and atomic blocks. Both can be encapsulated in the other. Specifically, synchronized blocks are not atomic blocks because they can execute <span style=\"font-family: courier new,courier;\">transaction-unsafe <\/span>code<span style=\"font-family: courier new,courier;\">.<\/span> This may be code like the output to the console, which can not be made undone. This is the reason why synchronized blocks are often called relaxed.<\/p>\n<h3>Synchronized Blocks<\/h3>\n<p>Synchronized blocks behave as a global lock that protects them. This means all synchronized blocks obey a total order; therefore, all changes to a synchronized block are available in the next synchronized block. There is a <span style=\"font-family: Courier New,Courier,monospace;\">synchronize-with<\/span> relation between the synchronized blocks. Because synchronized blocks behave as a global lock that protects them, they can not cause a deadlock. While a classical lock protects a memory area from explicit threads, the global lock of a synchronized block protects from all threads. That is the reason why the following program is well-defined:<\/p>\n<div style=\"background: #ffffff none repeat scroll 0% 0%; overflow: auto; width: auto; border-width: 0.1em 0.1em 0.1em 0.8em;\">\n<table>\n<tbody>\n<tr>\n<td>\n<pre style=\"margin: 0px; line-height: 125%;\"> 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26<\/pre>\n<\/td>\n<td>\n<pre style=\"margin: 0px; line-height: 125%;\"><span style=\"color: #888888;\">\/\/ synchronized.cpp<\/span>\r\n\r\n<span style=\"color: #557799;\">#include &lt;iostream&gt;<\/span>\r\n<span style=\"color: #557799;\">#include &lt;vector&gt;<\/span>\r\n<span style=\"color: #557799;\">#include &lt;thread&gt;<\/span>\r\n\r\n<span style=\"color: #333399; font-weight: bold;\">int<\/span> i<span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>;\r\n\r\n<span style=\"color: #333399; font-weight: bold;\">void<\/span> <span style=\"color: #0066bb; font-weight: bold;\">increment<\/span>(){\r\n  synchronized{ \r\n    std<span style=\"color: #333333;\">::<\/span>cout <span style=\"color: #333333;\">&lt;&lt;<\/span> <span style=\"color: #333333;\">++<\/span>i <span style=\"color: #333333;\">&lt;&lt;<\/span> <span style=\"background-color: #fff0f0;\">\" ,\"<\/span>;\r\n  }\r\n}\r\n\r\n<span style=\"color: #333399; font-weight: bold;\">int<\/span> <span style=\"color: #0066bb; font-weight: bold;\">main<\/span>(){\r\n  \r\n  std<span style=\"color: #333333;\">::<\/span>cout <span style=\"color: #333333;\">&lt;&lt;<\/span> std<span style=\"color: #333333;\">::<\/span>endl;\r\n    \r\n  std<span style=\"color: #333333;\">::<\/span>vector<span style=\"color: #333333;\">&lt;<\/span>std<span style=\"color: #333333;\">::<\/span><span style=\"color: #008800; font-weight: bold;\">thread<\/span><span style=\"color: #333333;\">&gt;<\/span> vecSyn(<span style=\"color: #0000dd; font-weight: bold;\">10<\/span>);\r\n  <span style=\"color: #008800; font-weight: bold;\">for<\/span>(<span style=\"color: #008800; font-weight: bold;\">auto<\/span><span style=\"color: #333333;\">&amp;<\/span> thr<span style=\"color: #333333;\">:<\/span> vecSyn)\r\n    thr <span style=\"color: #333333;\">=<\/span> std<span style=\"color: #333333;\">::<\/span><span style=\"color: #008800; font-weight: bold;\">thread<\/span>([]{ <span style=\"color: #008800; font-weight: bold;\">for<\/span>(<span style=\"color: #333399; font-weight: bold;\">int<\/span> n <span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>; n <span style=\"color: #333333;\">&lt;<\/span> <span style=\"color: #0000dd; font-weight: bold;\">10<\/span>; <span style=\"color: #333333;\">++<\/span>n) increment(); });\r\n  <span style=\"color: #008800; font-weight: bold;\">for<\/span>(<span style=\"color: #008800; font-weight: bold;\">auto<\/span><span style=\"color: #333333;\">&amp;<\/span> thr<span style=\"color: #333333;\">:<\/span> vecSyn) thr.join();\r\n  \r\n  std<span style=\"color: #333333;\">::<\/span>cout <span style=\"color: #333333;\">&lt;&lt;<\/span> <span style=\"background-color: #fff0f0;\">\"<\/span><span style=\"color: #666666; font-weight: bold; background-color: #fff0f0;\">\\n\\n<\/span><span style=\"background-color: #fff0f0;\">\"<\/span>;\r\n  \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Although variable <span style=\"font-family: Courier New,Courier,monospace;\">i <\/span>in line 7 is a global variable and the operations in the synchronized block is <span style=\"font-family: courier new,courier;\">transaction-unsafe,<\/span> the program is well-defined. The access to <span style=\"font-family: courier;\">i<\/span> and <span style=\"font-family: courier new,courier;\">std::cout<\/span> happens in total order. That is due to the synchronized block.<\/p>\n<p><span style=\"font-family: Helvetica,Arial,sans-serif;\">The output of the program is not so thrilling. The values for i are written in an increasing sequence, separated by a comma, only for completeness.<\/span><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5205\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/03\/synchronized.png\" alt=\"synchronized\" width=\"700\" height=\"152\" style=\"margin: 15px;\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/03\/synchronized.png 766w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/03\/synchronized-300x65.png 300w\" sizes=\"auto, (max-width: 700px) 100vw, 700px\" \/><\/p>\n<p>What about data races? You can have them with synchronized blocks. Only a minor modification is necessary.<\/p>\n<div style=\"background: #ffffff none repeat scroll 0% 0%; overflow: auto; width: auto; border-width: 0.1em 0.1em 0.1em 0.8em;\">\n<table>\n<tbody>\n<tr>\n<td>\n<pre style=\"margin: 0px; line-height: 125%;\"> 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36<\/pre>\n<\/td>\n<td>\n<pre style=\"margin: 0px; line-height: 125%;\"><span style=\"color: #008000;\">\/\/ nonsynchronized.cpp<\/span>\r\n\r\n<span style=\"color: #0000ff;\">#include &lt;chrono&gt;<\/span>\r\n<span style=\"color: #0000ff;\">#include &lt;iostream&gt;<\/span>\r\n<span style=\"color: #0000ff;\">#include &lt;vector&gt;<\/span>\r\n<span style=\"color: #0000ff;\">#include &lt;thread&gt;<\/span>\r\n\r\n<span style=\"color: #0000ff;\">using<\/span> <span style=\"color: #0000ff;\">namespace<\/span> std::chrono_literals;\r\n\r\n<span style=\"color: #2b91af;\">int<\/span> i= 0;\r\n\r\n<span style=\"color: #2b91af;\">void<\/span> increment(){\r\n  synchronized{ \r\n    std::cout &lt;&lt; ++i &lt;&lt; <span style=\"color: #a31515;\">\" ,\"<\/span>;\r\n    std::this_thread::sleep_for(1ns);\r\n  }\r\n}\r\n\r\n<span style=\"color: #2b91af;\">int<\/span> main(){\r\n  \r\n  std::cout &lt;&lt; std::endl;\r\n    \r\n  std::vector&lt;std::<span style=\"color: #0000ff;\">thread<\/span>&gt; vecSyn(10);\r\n  std::vector&lt;std::<span style=\"color: #0000ff;\">thread<\/span>&gt; vecUnsyn(10);\r\n    \r\n  <span style=\"color: #0000ff;\">for<\/span>(<span style=\"color: #0000ff;\">auto<\/span>&amp; thr: vecSyn)\r\n    thr = std::<span style=\"color: #0000ff;\">thread<\/span>([]{ <span style=\"color: #0000ff;\">for<\/span>(<span style=\"color: #2b91af;\">int<\/span> n = 0; n &lt; 10; ++n) increment(); });\r\n  <span style=\"color: #0000ff;\">for<\/span>(<span style=\"color: #0000ff;\">auto<\/span>&amp; thr: vecUnsyn)\r\n    thr = std::<span style=\"color: #0000ff;\">thread<\/span>([]{ <span style=\"color: #0000ff;\">for<\/span>(<span style=\"color: #2b91af;\">int<\/span> n = 0; n &lt; 10; ++n) std::cout &lt;&lt; ++i &lt;&lt; <span style=\"color: #a31515;\">\" ,\"<\/span>; });\r\n    \r\n  <span style=\"color: #0000ff;\">for<\/span>(<span style=\"color: #0000ff;\">auto<\/span>&amp; thr: vecSyn) thr.join();\r\n  <span style=\"color: #0000ff;\">for<\/span>(<span style=\"color: #0000ff;\">auto<\/span>&amp; thr: vecUnsyn) thr.join();\r\n  \r\n  std::cout &lt;&lt; <span style=\"color: #a31515;\">\"\\n\\n\"<\/span>;\r\n  \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>&nbsp;<\/p>\n<p>To observe the data race, I let the synchronized block sleep for a nanosecond (line 15). At the same time, I access <span style=\"font-family: courier;\">std::cout<\/span> without using a synchronized block (line 29); therefore, I launch ten threads that increment the global variable <span style=\"font-family: courier;\">i<\/span>. The output shows the issue.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5206\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/03\/nonsynchronizedEdit.png\" alt=\"nonsynchronizedEdit\" width=\"700\" height=\"204\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/03\/nonsynchronizedEdit.png 766w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/03\/nonsynchronizedEdit-300x87.png 300w\" sizes=\"auto, (max-width: 700px) 100vw, 700px\" \/><\/p>\n<p>I put red circles around the issues in the output. These are the spots at which <span style=\"font-family: courier;\">at least two threads use std::cout<\/span> simultaneously. The C++11 standard guarantees that the characters will be written in an atomic way that is only an optical issue. But what is worse is that the variable<span style=\"font-family: courier;\"> i <\/span>is written by at least two threads. This is a data race. Therefore the program has undefined behavior. If you look carefully at the output of the program you see that 103 is written twice.<\/p>\n<p>The total order of synchronized blocks also holds for atomic blocks.<\/p>\n<h3>Atomic Blocks<\/h3>\n<p>You can execute <span style=\"font-family: courier new,courier;\">transaction-unsafe<\/span> code in a synchronized block but not an atomic one. Atomic blocks are available in the forms: <span style=\"font-family: courier new,courier;\">atomic_noexcept, atomic_commit<\/span>, and <span style=\"font-family: courier new,courier;\">atomic_cancel<\/span>. The suffixes&nbsp; <span style=\"font-family: courier new,courier;\">_noexcept, _commit<\/span>, and <span style=\"font-family: courier new,courier;\">_cancel<\/span> define&nbsp;how an atomic block should manage an exception.<\/p>\n<ul>\n<li><span style=\"font-family: courier new,courier;\"><strong>atomic_noexcept: <\/strong><\/span>If an exception throws,&nbsp; <span style=\"font-family: courier new,courier;\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/utility\/program\/abort\">std::abort<\/a> <\/span>will be called, and the program aborts<strong>.<\/strong><span style=\"font-family: courier new,courier;\"><strong><br \/> <\/strong><\/span><\/li>\n<li><strong><span style=\"font-family: courier new,courier;\">atomic_cancel: <\/span><\/strong>In the default case, <span style=\"font-family: courier new,courier;\">std::abort<\/span> is called. That will not hold if a <span style=\"font-family: courier new,courier;\">transaction-safe<\/span> exception throws that is responsible for the ending of the transaction. In this case, the transaction will be canceled, put to its initial state, and the exception will be thrown.<strong><span style=\"font-family: courier new,courier;\"><br \/> <\/span><\/strong><\/li>\n<li><strong><span style=\"font-family: courier new,courier;\">atomic_commit: <\/span><\/strong>The transaction will be committed normally if an exception is thrown.<span style=\"font-family: courier new,courier;\"> <\/span><\/li>\n<\/ul>\n<p><strong><span style=\"font-family: courier new,courier;\">transaction-safe<\/span> exceptions:<\/strong> <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/memory\/new\/bad_alloc\" title=\"cpp\/memory\/new\/bad alloc\">std::bad_alloc<\/a><\/span>, <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/memory\/new\/bad_array_length\" title=\"cpp\/memory\/new\/bad array length\">std::bad_array_length<\/a><\/span>, <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/memory\/new\/bad_array_new_length\" title=\"cpp\/memory\/new\/bad array new length\">std::bad_array_new_length<\/a><\/span>, <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/types\/bad_cast\" title=\"cpp\/types\/bad cast\">std::bad_cast<\/a><\/span>, <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/types\/bad_typeid\" title=\"cpp\/types\/bad typeid\">std::bad_typeid<\/a><\/span>, <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/error\/bad_exception\" title=\"cpp\/error\/bad exception\">std::bad_exception<\/a><\/span>, <span class=\"t-lc\"><a href=\"http:\/\/en.cppreference.com\/w\/cpp\/error\/exception\" title=\"cpp\/error\/exception\">std::exception<\/a><span style=\"font-family: courier new,courier;\">, <\/span><\/span>and all exceptions that are derived from them are<span style=\"font-family: 'courier new', courier;\"> transaction-safe<\/span>.<\/p>\n<h3>transaction_safe versus transaction_unsafe Code<\/h3>\n<p>You can declare a function as <span style=\"font-family: courier new,courier;\">transaction_safe<\/span> or attach the <span style=\"font-family: courier new,courier;\">transaction_unsafe<\/span> attribute to it.<\/p>\n<div style=\"background: #ffffff none repeat scroll 0% 0%; overflow: auto; width: auto; border-width: 0.1em 0.1em 0.1em 0.8em;\">\n<pre style=\"margin: 0px; line-height: 125%;\"><span style=\"color: #2b91af;\">int<\/span> transactionSafeFunction() transaction_safe;\r\n\r\n[[transaction_unsafe]] <span style=\"color: #2b91af;\">int<\/span> transactionUnsafeFunction();\r\n<\/pre>\n<\/div>\n<p><span style=\"font-family: courier new,courier;\">transaction_safe<\/span> is part of the type of a function. But what does <span style=\"font-family: courier new,courier;\">transaction_safe<\/span> mean? A <span style=\"font-family: courier new,courier;\">transaction_safe<\/span> function is, according to the proposal <a href=\"https:\/\/isocpp.org\/files\/papers\/n4265.html\">N4265<\/a>, a function that has a <span style=\"font-family: courier new,courier;\">transaction_safe<\/span> definition. This holds if the following properties do not apply to its definition.<\/p>\n<ul>\n<li>It has a <span style=\"font-family: courier new,courier;\">volatile<\/span> parameter or a <span style=\"font-family: courier new,courier;\">volatile<\/span> variable.<\/li>\n<li>It has <span style=\"font-family: courier new,courier;\">transaction-unsafe<\/span> statements.<\/li>\n<li>If the function uses a constructor or destructor of a class in its body with a <span style=\"font-family: courier new,courier;\">volatile<\/span> non-static member.<\/li>\n<\/ul>\n<p>Of course, this definition of <span style=\"font-family: courier new,courier;\">transaction_safe<\/span> is insufficient because it uses <span style=\"font-family: courier new,courier;\">transaction_unsafe<\/span>. You can read proposal <a href=\"https:\/\/isocpp.org\/files\/papers\/n4265.html\">N4265<\/a> and get the answer to what <span style=\"font-family: Courier New,Courier,monospace;\">transaction_unsafe <span style=\"font-family: Helvetica,Arial,sans-serif;\">means.<\/span><br \/> <\/span><\/p>\n<h2>What&#8217;s next?<\/h2>\n<p>The <a href=\"https:\/\/www.modernescpp.com\/index.php\/task-blocks\">next post<\/a> is about the fork-join paradigm. To be specific, it&#8217;s about task blocks.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Transactional memory is based on the idea of a transaction from the database theory. Transactional memory shall make the handling of threads a lot easier. That is for two reasons. Data races and deadlocks disappear. Transactions are composable.<\/p>\n","protected":false},"author":21,"featured_media":5205,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[367],"tags":[482,509],"class_list":["post-5207","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-multithreading-c-17-and-c-20","tag-outdated","tag-transactional-memory"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5207","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5207"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5207\/revisions"}],"predecessor-version":[{"id":6881,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5207\/revisions\/6881"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5205"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}