Homework (Week 8) Term 2, 2021 Announcements Course Outline Course Schedule Ed Forum Glossary Maths Resources Moodle - Lecture Recordings Assignment 0 Spec TeX Guide Web Submission Assignment 1 Spec TeX Guide Web Submission Assignment 2 Spec Web Submission Java Resources Monitors Video Multithreading Video Semaphores Video Volatile Video Web Tutorials Week 1 Homework Thursday Slides Condensed Thursday Slides Wednesday Slides Condensed Wednesday Slides Week 2 Homework Thursday Code Thursday Notes Thursday Slides Condensed Thursday Slides Wednesday Code Week 3 Homework Promela Code Thursday Code Thursday Slides Condensed Thursday Slides Wednesday Slides Condensed Wednesday Slides Week 4 Homework Thursday Code Thursday Slides Condensed Thursday Slides Wednesday Code and Notes Wednesday Slides Condensed Wednesday Slides Week 5 Homework Thursday Slides Condensed Thursday Slides Wednesday Code and Notes Wednesday Slides Condensed Wednesday Slides Week 7 Homework Thursday Notes Thursday Slides Condensed Thursday Slides Wednesday Notes Wednesday Slides Condensed Wednesday Slides Week 8 Homework Thursday Slides Condensed Thursday Slides Wednesday Code Wednesday Slides Condensed Wednesday Slides Week 9 Homework Thursday Notes Thursday Slides Wednesday Notes Wednesday Slides Condensed Wednesday Slides Week 10 Old Exams Thursday Slides Wednesday Notes Wednesday Slides Old Exam Papers final05s2 final06s2 final07s2 final08s2 final09s2 final10s2 final11s2 final13s2 final14s2 final17s2 Homework (Week 8) Table of Contents 1. Ricart-Agrawala Algorithm (5 points) 2. Token-Passing (5 points) 3. Bounded bypass (3 points) Submission: Due on Thursday, 29th of July, 4pm Sydney Time. Please submit using the CSE Give System either online or via this command on a CSE terminal: give cs3151 hw7 hw7.pdf
1 Ricart-Agrawala Algorithm (5 points) Pseudocode of the Ricart-Agrawala Algorithm is: a) Suppose that we exchanged the lines p8 and p9–p11 in Main, i.e. \(\textsf{requestCS} \leftarrow \textsf{false}\) now executes after the for loop (instead of executing before the for loop). Suppose furthermore that it's possible for \(\textbf{Receive}\) to preempt \(\textbf{Main}\) at these locations. Provide an example in which the modified algorithm is no longer correct. b) In \(\textbf{Receive}\), can the statement \(\textsf{p2:}\ \textsf{highestNum} \leftarrow \textsf{max}(\textsf{highestNum}, \textsf{requestNum})\) be replaced by \(\textsf{p2:}\ \textsf{highestNum} \leftarrow \textsf{requestNum}\)? Why? Justify your answer and provide an example. In both parts of this question, you can sketch diagrams in addition to textual explanations. However, if your textual explanations are clear, such diagrams might be unnecessary. 2 Token-Passing (5 points) Pseudocode of the Ricart-Agrawala Token-passing Algorithm is: a) In node \(i\), can the value of \(\textsf{requested}[j]\) be less than the value of \(\textsf{granted}[j]\) for \(j \neq i\)? Why? Justify your answer. b) In node \(i\), can the value of \(\textsf{requested}[j]\) be greater than the value of \(\textsf{granted}[j]\) for \(j \neq i\)? Why? Justify your answer. 3 Bounded bypass (3 points) Under Ben-Ari's basic model—that is, reliable asynchronous message passing with possible reordering of messages—does any of the two algorithms by Ricart and Agrawala above satisfy bounded bypass? Justify your answer. 2021-08-05 tor 15:45 Announcements RSS
