{"id":37,"date":"2011-11-17T02:36:46","date_gmt":"2011-11-17T02:36:46","guid":{"rendered":"http:\/\/newrsbook.cs.aau.dk\/?page_id=37"},"modified":"2011-11-17T02:39:28","modified_gmt":"2011-11-17T02:39:28","slug":"project-ideas","status":"publish","type":"page","link":"https:\/\/rsbook.cs.aau.dk\/?page_id=37","title":{"rendered":"Project Ideas"},"content":{"rendered":"<p>Further Exercises and Project Ideas Using <a title=\"http:\/\/www.uppaal.com\/\" href=\"http:\/\/www.uppaal.com\/\" rel=\"nofollow\">Uppaal<\/a>.<\/p>\n<ul>\n<li>A list with 27 suggested exercises is available <a title=\"http:\/\/www.cs.aau.dk\/~kgl\/ESV04\/exercises\/index.html\" href=\"http:\/\/www.cs.aau.dk\/%7Ekgl\/ESV04\/exercises\/index.html\" rel=\"nofollow\">here<\/a>.<\/li>\n<li>The book <a title=\"http:\/\/www.greenteapress.com\/semaphores\/\" href=\"http:\/\/www.greenteapress.com\/semaphores\/\" rel=\"nofollow\">&#8220;The little book of semaphores&#8221;<\/a> by <a title=\"http:\/\/allendowney.com\/\" href=\"http:\/\/allendowney.com\/\" rel=\"nofollow\">Allen B. Downey<\/a> presents semaphore-based solutions to many concurrency problems, ranging from classical ones (like the barbershop) to tricky and obscure problems (like the Sushi bar). All of these problems are a suitable source of student projects on modelling and verification using Uppaal. (The pointer to Downey&#8217;s book is courtesy of <a title=\"http:\/\/www.cs.ru.nl\/~fvaan\/\" href=\"http:\/\/www.cs.ru.nl\/%7Efvaan\/\" rel=\"nofollow\">Frits Vaandrager<\/a>.)<\/li>\n<li>Using Uppaal (or the Concurrency Workbench, if you prefer) model the mutual exclusion algorithm proposed by Murray A. Eisenbeng and Michael R. McGuire (<a title=\"http:\/\/portal.acm.org\/citation.cfm?id=355606.361895\" href=\"http:\/\/portal.acm.org\/citation.cfm?id=355606.361895\" rel=\"nofollow\">&#8220;Further comments on Dijkstra&#8217;s concurrent programming control problem&#8221;<\/a>, Communications of the ACM 15(11):999 (November 1972)) for three processes, and establish that the algorithm does guarantee mutual exclusion. The code for process <em>i<\/em> is given below.<\/li>\n<\/ul>\n<pre>do {\r\n \/\/ Acquire lock\r\n while(1) {\r\n   flag[i] = WantIn;\r\n   j = turn;\r\n   while (j\u00a0!= i) {\r\n     if (flag[j]\u00a0!= idle)\r\n       j = turn;\r\n     else\r\n       j = (j + 1) % n;\r\n   }\r\n   flag[i] = InCS;\r\n   j = 0;\r\n   while ((j &lt; n) &amp;&amp; (j == i || flag[j]\u00a0!= InCS))\r\n     j++;\r\n   if ((j &gt;= n) &amp;&amp; (turn == i || flag[turn] == Idle))\r\n     break; \/\/ Acquired lock, Leave while loop\r\n }\r\n turn = i;\r\n -- Critical Section --\r\n \/\/ Release Lock\r\n j = (turn + 1) % n;\r\n while (flag[j] == Idle)\r\n   j = (j + 1) % n;\r\n turn = j;\r\n flag[i] = Idle;\r\n -- Remainder Section\r\n} while (1);<\/pre>\n<p>The shared variable turn is initialized to a number between 0 and n-1 (inclusive). All elements of the flag array are initialized to Idle. A process can be in any state in the set {Idle, WantIn, InCS}.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Further Exercises and Project Ideas Using Uppaal. A list with 27 suggested exercises is available here. The book &#8220;The little book of semaphores&#8221; by Allen B. Downey presents semaphore-based solutions to many concurrency problems, ranging from classical ones (like the barbershop) to tricky and obscure problems (like the Sushi bar). All of these problems are [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-37","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=\/wp\/v2\/pages\/37","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=37"}],"version-history":[{"count":3,"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=\/wp\/v2\/pages\/37\/revisions"}],"predecessor-version":[{"id":40,"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=\/wp\/v2\/pages\/37\/revisions\/40"}],"wp:attachment":[{"href":"https:\/\/rsbook.cs.aau.dk\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}