{"id":1080,"date":"2013-06-26T01:00:00","date_gmt":"2013-06-25T23:00:00","guid":{"rendered":"https:\/\/www.fussylogic.co.uk\/blog\/?p=1080"},"modified":"2013-06-26T11:17:49","modified_gmt":"2013-06-26T10:17:49","slug":"invisible-races","status":"publish","type":"post","link":"https:\/\/www.fussylogic.co.uk\/blog\/?p=1080","title":{"rendered":"Invisible Races"},"content":{"rendered":"<p>When you\u00e2\u20ac\u2122re writing multi-threaded applications, the problem you are working hardest to avoid is that of data races. Here\u00e2\u20ac\u2122s an example (assume a 32-bit x86 system):<\/p>\n<pre class=\"sourceCode C\"><code class=\"sourceCode c\"><span class=\"dt\">int<\/span> global = <span class=\"dv\">0<\/span>;\n\n<span class=\"dt\">void<\/span> thread1() {\n    global += <span class=\"dv\">1<\/span>;\n}\n\n<span class=\"dt\">void<\/span> thread2() {\n    global = <span class=\"bn\">0x10000<\/span>;\n}<\/code><\/pre>\n<p>The race here is pretty obvious. Two threads are accessing the same bit of memory. I\u00e2\u20ac\u2122ve discussed <a href=\"http:\/\/www.fussylogic.co.uk\/blog\/?tag=interrupts\">these sorts of races<\/a> before when an interrupt handler acts just like another thread. You have no control of when each thread gets control of the CPU, or even if the two threads are running simultaneously on multiple cores.<\/p>\n<p>The solution is to wrap the shared variable in a lock, as we\u00e2\u20ac\u2122ll have seen and done plenty of times before.<\/p>\n<p>Now consider this:<\/p>\n<pre class=\"sourceCode C\"><code class=\"sourceCode c\"><span class=\"dt\">char<\/span> c1 = <span class=\"dv\">0<\/span>;\n<span class=\"dt\">char<\/span> c2 = <span class=\"dv\">0<\/span>;\n\n<span class=\"dt\">int<\/span> x, y;\n\n<span class=\"dt\">void<\/span> thread1() {\n    c1 = <span class=\"dv\">1<\/span>;\n    x = c1;\n}\n\n<span class=\"dt\">void<\/span> thread2() {\n    c2 = <span class=\"dv\">1<\/span>;\n    y = c2;\n}<\/code><\/pre>\n<p>The question for the class is this:<\/p>\n<blockquote>\n<p>What are <code>x<\/code> and <code>y<\/code> after these two threads have completed?<\/p>\n<\/blockquote>\n<p>I\u00e2\u20ac\u2122m sure you\u00e2\u20ac\u2122ll realise that the very existence of the question means that the answer \u00e2\u20ac\u01531 and 1\u00e2\u20ac\u009d, is not correct.<\/p>\n<p>The answer is actually any of, with no ability to specify:<\/p>\n<ul>\n<li>0 and 0<\/li>\n<li>1 and 0<\/li>\n<li>0 and 1<\/li>\n<li>1 and 1<\/li>\n<\/ul>\n<p>\u00e2\u20ac\u0153What? How?\u00e2\u20ac\u009d I hear you cry (it\u00e2\u20ac\u2122s what I cried when it was explained to me). There is no shared variable between the two threads. <code>c1<\/code> and <code>x<\/code> are isolated in <code>thread1()<\/code> and <code>c2<\/code> and <code>y<\/code> are isolated in <code>thread2()<\/code>. Unfortunately, no, that isn\u00e2\u20ac\u2122t true.<\/p>\n<p>The key observation to make is that <code>c1<\/code> and <code>c2<\/code> are chars on a 32-bit system, and nothing stops the compiler and linker from allocating these two variables to adjacent bytes in memory. It\u00e2\u20ac\u2122s not possible to access a single byte on a 32-bit system; you have to read all four bytes that make up the word, modify the 8 of them that you\u00e2\u20ac\u2122re interested in and put 32 back. Even if the processor has nice instructions to hide that from you, that\u00e2\u20ac\u2122s what it\u00e2\u20ac\u2122s doing in the background. Read-modify-write is the hole through which all race conditions drive \u00e2\u20ac\u201c another thread can be scheduled any time between the read and the write, and trample all over you.<\/p>\n<p>Modern compilers are meant to prevent this, although short of only allocating 32-bits for every 8-bit value, I\u00e2\u20ac\u2122m not entirely sure how they do that.<\/p>\n<p>Terrified? Me too.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When you\u00e2\u20ac\u2122re writing multi-threaded applications, the problem you are working hardest to avoid is that of data races. Here\u00e2\u20ac\u2122s an example (assume a 32-bit x86 system): int global = 0; void thread1() { global += 1; } void thread2() { global = 0x10000; } The race here is pretty obvious. Two threads are accessing the\u2026 <span class=\"read-more\"><a href=\"https:\/\/www.fussylogic.co.uk\/blog\/?p=1080\">Read More &raquo;<\/a><\/span><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[65,6,81],"_links":{"self":[{"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1080"}],"collection":[{"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1080"}],"version-history":[{"count":2,"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1080\/revisions"}],"predecessor-version":[{"id":1082,"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1080\/revisions\/1082"}],"wp:attachment":[{"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1080"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1080"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.fussylogic.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}