trAvis - MANAGER
Edit File: brinch-hansens-arrows.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Brinch-Hansens Arrows — Varnish version 5.2.1 documentation</title> <link rel="stylesheet" href="../_static/classic.css" type="text/css" /> <link rel="stylesheet" href="../_static/pygments.css" type="text/css" /> <script type="text/javascript"> var DOCUMENTATION_OPTIONS = { URL_ROOT: '../', VERSION: '5.2.1', COLLAPSE_INDEX: false, FILE_SUFFIX: '.html', HAS_SOURCE: true }; </script> <script type="text/javascript" src="../_static/jquery.js"></script> <script type="text/javascript" src="../_static/underscore.js"></script> <script type="text/javascript" src="../_static/doctools.js"></script> <link rel="index" title="Index" href="../genindex.html" /> <link rel="search" title="Search" href="../search.html" /> <link rel="top" title="Varnish version 5.2.1 documentation" href="../index.html" /> <link rel="up" title="Poul-Hennings random outbursts" href="index.html" /> <link rel="next" title="SSL revisited" href="ssl_again.html" /> <link rel="prev" title="Varnish - 10 going on 50" href="10goingon50.html" /> </head> <body role="document"> <div class="related" role="navigation" aria-label="related navigation"> <h3>Navigation</h3> <ul> <li class="right" style="margin-right: 10px"> <a href="../genindex.html" title="General Index" accesskey="I">index</a></li> <li class="right" > <a href="ssl_again.html" title="SSL revisited" accesskey="N">next</a> |</li> <li class="right" > <a href="10goingon50.html" title="Varnish - 10 going on 50" accesskey="P">previous</a> |</li> <li class="nav-item nav-item-0"><a href="../index.html">Varnish version 5.2.1 documentation</a> »</li> <li class="nav-item nav-item-1"><a href="index.html" accesskey="U">Poul-Hennings random outbursts</a> »</li> </ul> </div> <div class="document"> <div class="documentwrapper"> <div class="bodywrapper"> <div class="body" role="main"> <div class="section" id="brinch-hansens-arrows"> <span id="phk-brinch-hansens-arrows"></span><h1>Brinch-Hansens Arrows<a class="headerlink" href="#brinch-hansens-arrows" title="Permalink to this headline">ΒΆ</a></h1> <p>As you may have noticed, I am a bit of a IT-history nerd, and we do have some rather important early IT history in Denmark.</p> <p>If you have a solid CS background, you have undoubtedly heard about both dining philosophers and Brinch-Hansens work in multiprogramming.</p> <p>Multiprogramming is fundamentally hard, because you cannot have one thread holding lock A trying to get lock B, while another holds lock B trying to get lock A.</p> <p>Brinch-Hansen did a lot of both theoretical and practical work in the area of multiprogramming and being both good at it and one of the pioneers, he was awarded the ACM Turing Prize for it.</p> <p>You can read more about him here: <a class="reference external" href="http://brinch-hansen.net/">Brinch-Hansen Archive</a></p> <p>Along the way he came up with a trivial and practical way to guarantee that a given multiprogramming system was free of deadlocks: Draw the locking order and make sure all the arrows point to the right.</p> <p>When we started working with multi-core systems in FreeBSD, we were sure to have deadlocks in our future, and we adopted and expanded a facility called "WITNESS" originally written for BSDI, which keeps an eye on Brinch-Hansens arrows in real time.</p> <p>Historically I have been pretty good at avoiding deadlocks, it seems to come natural to me to think about locking order, but not everybody feels that way about them, and WITNESS have caught a lot of "Ohh, didn't think about <em>that</em>" situations over the years.</p> <p>It is no accident that Varnish has a very simple locking structure, but as we add more and more flexibility and extensibility to Varnish it grows a little here and there, and I managed to introduce a lock-order reversal the other day - my first in about five years I think.</p> <p>Since I'm obviously getting old and slipping up here, I though it was about time I carried out the Brinch-Hansen check on Varnish.</p> <p>I briefly pondered porting WITNESS into Varnish, but it's 3k lines and we have extremely good code coverage in our regression tests so I decided to KISS and do it as post-processing.</p> <p>I have added default-off debug code to emit VSL "Witness" records, taught varnishtest how to enable that code, and added a small python script to process the records into a nice plot:</p> <img alt="../_images/brinch_hansens_arrows_1.svg" src="../_images/brinch_hansens_arrows_1.svg" /><p>And yo and behold: All the arrows point to the right.</p> <p><em>phk</em></p> </div> </div> </div> </div> <div class="sphinxsidebar" role="navigation" aria-label="main navigation"> <div class="sphinxsidebarwrapper"> <h4>Previous topic</h4> <p class="topless"><a href="10goingon50.html" title="previous chapter">Varnish - 10 going on 50</a></p> <h4>Next topic</h4> <p class="topless"><a href="ssl_again.html" title="next chapter">SSL revisited</a></p> <div role="note" aria-label="source link"> <h3>This Page</h3> <ul class="this-page-menu"> <li><a href="../_sources/phk/brinch-hansens-arrows.txt" rel="nofollow">Show Source</a></li> </ul> </div> <div id="searchbox" style="display: none" role="search"> <h3>Quick search</h3> <form class="search" action="../search.html" method="get"> <div><input type="text" name="q" /></div> <div><input type="submit" value="Go" /></div> <input type="hidden" name="check_keywords" value="yes" /> <input type="hidden" name="area" value="default" /> </form> </div> <script type="text/javascript">$('#searchbox').show(0);</script> </div> </div> <div class="clearer"></div> </div> <div class="related" role="navigation" aria-label="related navigation"> <h3>Navigation</h3> <ul> <li class="right" style="margin-right: 10px"> <a href="../genindex.html" title="General Index" >index</a></li> <li class="right" > <a href="ssl_again.html" title="SSL revisited" >next</a> |</li> <li class="right" > <a href="10goingon50.html" title="Varnish - 10 going on 50" >previous</a> |</li> <li class="nav-item nav-item-0"><a href="../index.html">Varnish version 5.2.1 documentation</a> »</li> <li class="nav-item nav-item-1"><a href="index.html" >Poul-Hennings random outbursts</a> »</li> </ul> </div> <div class="footer" role="contentinfo"> © Copyright 2010-2014, Varnish Software AS. Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.4.9. </div> </body> </html>