{"id":2582,"date":"2023-12-21T14:03:44","date_gmt":"2023-12-21T13:03:44","guid":{"rendered":"https:\/\/oopm.org\/?page_id=2582"},"modified":"2024-11-26T14:35:38","modified_gmt":"2024-11-26T13:35:38","slug":"54-1-implementing-lock-and-semaphore","status":"publish","type":"page","link":"https:\/\/oopm.org\/?page_id=2582","title":{"rendered":"16.1 Implementing Lock and Semaphore"},"content":{"rendered":"<div class=\"pdfprnt-buttons pdfprnt-buttons-page pdfprnt-top-right\"><a href=\"https:\/\/oopm.org\/index.php?rest_route=wpv2pages2582&print=pdf\" class=\"pdfprnt-button pdfprnt-button-pdf\" target=\"_blank\"><img decoding=\"async\" src=\"https:\/\/oopm.org\/wp-content\/plugins\/pdf-print\/images\/pdf.png\" alt=\"image_pdf\" title=\"View PDF\" \/><\/a><a href=\"https:\/\/oopm.org\/index.php?rest_route=wpv2pages2582&print=print\" class=\"pdfprnt-button pdfprnt-button-print\" target=\"_blank\"><img decoding=\"async\" src=\"https:\/\/oopm.org\/wp-content\/plugins\/pdf-print\/images\/print.png\" alt=\"image_print\" title=\"Print Content\" \/><\/a><\/div>\n<p class=\"wp-block-paragraph\">As mentioned, we need a basic synchronization mechanism in order to define both the low-level synchronization mechanisms and the high-level synchronization mechanisms.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In order to implement synchronization mechanisms, we rely on using an <em>atomic operation<\/em>. An operation is <em>atomic<\/em> if it cannot be interrupted while its is being executed. We have previously seen (section <script>mkRef(\"Other issues in parallel programming\");<\/script>) that incrementing an integer like <code>n := n + 1<\/code> is not an atomic operation. Reading a value is atomic, just as writing a value is atomic.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A common example of an atomic operation available on computers and accessible from a programming language is <em>compare-and-swap<\/em>. It compares the contents of a memory location with a given value and, only if they are the same, modifies the location to the given value. The operation returns a value that indicates if the operation succeeded.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Our programming language has a <code>cmpAndSwap<\/code> operation that may be applied to an <code>integer<\/code>. Suppose we have an <code>integer<\/code> variable <code>mutex<\/code>:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>mutex: <strong>var<\/strong> integer<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">We may apply <code>cmpAndSwap<\/code> in the following way:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>B: <strong>var<\/strong> Boolean\nB := mutex.cmpAndSwap(v1,v2)<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If <code>mutex = v1<\/code>, then nothing happens and <code>cmpAndSwap<\/code> returns true.<\/li>\n\n\n\n<li>If <code>mutex &lt;&gt; v1<\/code>, then <code>cmpAndSwap<\/code> assigns <code>v2<\/code> to mutex and returns false.<\/li>\n\n\n\n<li>The execution of <code>cmpAndSwap<\/code> is atomic, i.e. the execution cannot be interrupted.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Suppose we want to use an integer variable to keep track of whether or not a parallel object is in a critical region. In th example below, the variable <code>mutex<\/code> may have the value 0 or 1. Zero (0) indicates that no other parallel objects in the critical regions, and one (1) indicates the opposite.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A parallel object attempting to reserve the <code>mutex<\/code> then repeatedly tries to write a one (1) to <code>mutex<\/code> until a zero is returned:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>mutex: <strong>var<\/strong> integer\n...\nloop: do\n   if (mutex.cmpAndSwap(1,1)) :then\n      -- operation failed, try again\n      restart(loop)\n-- operation succeeded, enter critical region\n...\nmutex := 0<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">If a one is returned by <code>cmpAndSwap<\/code>, the mutex is busy and som other parallel object is in its critical region. If zero is returned the <code>mutex<\/code> is free and <code>cmapAndSwap<\/code> assigns it a one and enters it critical region.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Implementing Lock<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">We may now show how to implement the <code>Lock<\/code> class:<\/p>\n\n\n\n<pre class=\"wp-block-code has-tiny-font-size\"><code><strong>class<\/strong> Lock: \n<strong>    <\/strong>mutex: <strong>var<\/strong> integer\n    get: \n       loop: <strong>do<\/strong> \n          if (mutex.cmpAndSwap(1,1)) :then \n             restart(loop)\n    free:<mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-foreground-color\"> <\/mark>\n       mutex := 0\n    mutex := 0<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Class <code>Lock<\/code> has two method <code>get<\/code> and <code>free<\/code>. <code>Get<\/code> does the same as in the previous example, and <code>free<\/code> assigns zero to <code>mutex<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Implementing Semaphore<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Here we show how to implement a counting semaphore using a lock. Class <code>Semaphore<\/code> has the two methods <code>wait<\/code> and <code>signal<\/code>, and it has two private objects <code>mutex<\/code> and <code>Q<\/code> (short for Queue).<\/p>\n\n\n\n<pre class=\"wp-block-code has-tiny-font-size\"><code><strong>class<\/strong> Semaphore(cnt: <strong>var<\/strong> integer)\n   -- Implementation of a counting semaphores\n   -- cnt is the initial value of the semaphore\n   -- requires: cnt &gt; 0\n   wait:\n      mutex.get -- attempt to get the Lock\n      cnt := cnt - 1\n      if (cnt &lt; 0) :then\n         disable -- is this needed?\n         Q.insert(TheActiveProcess)\n         enable\n         mutex.free\n         theActiveProcess.suspend\n      :else\n         mutex.free\n   signal:\n      mutex.get\n      cnt := cnt + 1\n      if(cnt &lt;= 0) :then\n         P := Q.removeNext\n         disable\n         P.mkActive -- P.wakeUp?\n         enable\n      mutex.free\n   %private\n   mutex: <strong>obj<\/strong> Lock\n   Q: <strong>obj<\/strong> OrderedList(GeneralProcess) <\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The <code>wait<\/code>-method attempts to get the <code>mutex<\/code>. If it succeeds it decrements the counter <code>cnt<\/code>. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If <code>cnt<\/code> becomes less than 0, the <code>Semaphore<\/code> cannot grant more resources. It then inserts <code>theActiveProcess<\/code> into its local queue, releases the <code>mutex<\/code> and suspends execution. <code>theActiveProcess<\/code> is a predefined variable (so its declaration is not shown above) that refers to the current active <code>Process<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If <code>cnt<\/code> is greater than or equal to zero, it just releases the <code>mutex<\/code> since there was at least one free resource.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The <code>signal<\/code>-method also attempts to get the <code>mutex<\/code> and if it succeeds it increments <code>cnt<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If <code>cnt<\/code> is less than or equal to zero it means that some processes is waiting in the queue <code>Q<\/code> to get the lock. It thus removes the next element in <code>Q<\/code> and makes it active and releases the <code>mutex<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">if <code>cnt<\/code> is greater than zero, no processes are waiting to request a resource &#8211; it then just releases the <code>mutex<\/code>. <\/p>\n<div style=\"display:flex; gap:10px;justify-content:center\" class=\"wps-pgfw-pdf-generate-icon__wrapper-frontend\">\n\t\t<a  href=\"https:\/\/oopm.org?action=genpdf&amp;id=2582\" class=\"pgfw-single-pdf-download-button\" ><img src=\"https:\/\/oopm.org\/wp-content\/plugins\/pdf-generator-for-wp\/admin\/src\/images\/PDF_Tray.svg\" title=\"Generate PDF\" style=\"width:auto; height:45px;\"><\/a>\n\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>As mentioned, we need a basic synchronization mechanism in order to define both the low-level synchronization mechanisms and the high-level synchronization mechanisms. In order to implement synchronization mechanisms, we rely on using an atomic operation. An operation is atomic if it cannot be interrupted while its is being executed. We have previously seen (section ) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1972,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2582","page","type-page","status-publish","hentry"],"mb":[],"mfb_rest_fields":["title","gutenberg_elementor_mode"],"_links":{"self":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/2582","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2582"}],"version-history":[{"count":34,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/2582\/revisions"}],"predecessor-version":[{"id":9877,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/2582\/revisions\/9877"}],"up":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/1972"}],"wp:attachment":[{"href":"https:\/\/oopm.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}