{"id":8651,"date":"2014-04-02T08:32:09","date_gmt":"2014-04-02T12:32:09","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=8651"},"modified":"2014-04-02T08:32:09","modified_gmt":"2014-04-02T12:32:09","slug":"mcs-locks-and-qspinlocks","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2014\/04\/02\/mcs-locks-and-qspinlocks\/","title":{"rendered":"MCS Locks and qspinlocks"},"content":{"rendered":"<p><a href=\"http:\/\/lwn.net\/Articles\/590243\/\">Jonathan Corbet<\/a> (via <a href=\"https:\/\/twitter.com\/optshiftk\/status\/450823579907538944\">Kyle Sluder<\/a>):<\/p>\n<blockquote cite=\"http:\/\/lwn.net\/Articles\/590243\/\"><p>Note that the use of an atomic swap operation on the main lock means that\n<i>only<\/i> CPU&nbsp;2 can have a pointer to CPU&nbsp;1&rsquo;s\n<tt>mcs_spinlock<\/tt> structure.  So there is no need for atomic operations\nwhen making changes to that structure, though some careful programming is\nstill needed to make sure that changes are visible to CPU&nbsp;1 at the\nright times.<\/p>\n<p>Once this assignment is done, CPU 2 will spin on the <tt>locked<\/tt> value in <i>its own<\/i><tt>mcs_spinlock<\/tt> structure rather than the value in the main lock.\nIts spinning will thus be entirely CPU-local, not touching the main lock\nat all.  This process can go on indefinitely as contention for the lock\nincreases, with each CPU placing itself in line behind those that are\nalready there, and each CPU spinning on its own copy of the lock.  The\npointer in the &ldquo;main&rdquo; lock, thus, always indicates the tail of the queue of\nwaiting CPUs.<\/p>\n<p>[&#8230;]<\/p>\n<p>An MCS lock, thus, is somewhat more complicated than a regular spinlock. But that added complexity removes much of the cache-line bouncing from the contended case; it also is entirely fair, passing the lock to each CPU in the order that the CPUs arrived.<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"<p>Jonathan Corbet (via Kyle Sluder): Note that the use of an atomic swap operation on the main lock means that only CPU&nbsp;2 can have a pointer to CPU&nbsp;1&rsquo;s mcs_spinlock structure. So there is no need for atomic operations when making changes to that structure, though some careful programming is still needed to make sure that [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[289,800,845,448,74,138,71],"class_list":["post-8651","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-concurrency","tag-kernel","tag-linux","tag-opensource","tag-optimization","tag-programming"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/8651","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=8651"}],"version-history":[{"count":0,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/8651\/revisions"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=8651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=8651"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=8651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}