My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
  Advanced search   Search tips   Subscriptions
Issue 9: 2.10 Exercise 10
1 person starred this issue and may be notified of changes. Back to list
Status:  Verified
Owner:  sergeypr...@gmail.com
Closed:  Sep 2014


 
Project Member Reported by sergeypr...@gmail.com, Sep 4, 2014
Exercise 11. Programmers at the Flaky Computer Corporation designed the protocol
shown in Fig. 2.15 to achieve n-threadmutual exclusion. For each question,
either sketch a proof, or display an execution where it fails.
 Does this protocol satisfy mutual exclusion?
 Is this protocol starvation-free?
 is this protocol deadlock-free?

1 class Flaky implements Lock {
2   private int turn;
3   private boolean busy = false;
4   public void lock() {
5     int me = ThreadID.get();
6     do {
7       do {
8         turn = me;
9       } while (busy);
10      busy = true;
11    } while (turn != me);
12   }
13   public void unlock() {
14   busy = false;
15  }
16 }
Figure 2.15 The Flaky lock used in Exercise 11.
Sep 4, 2014
Project Member #1 sergeypr...@gmail.com
1. Does this protocol satisfy mutual exclusion?
I do not know how to describe it

2. Is this protocol deadlock-free?
Поток №1 прошел строчку 8 (turn = me) и записал в turn 1, и перешел например в 10 строчку.
Контекст процесса переключился на поток №2.
Поток #3 прошел строчку 8 (turn = me) и записал в turn 2, и пошел дальше.
При этом поток №1 теперь не выйдет из цикла, так как 11 строчка while (turn != me) -> while (1 != 2) будет все время выполняться

3. Is this protocol starvation-free?
Starvation-free не может быть так как он deadlock

Sep 16, 2014
Project Member #2 sh.ba...@gmail.com
on first question answer is - *YES*
if not:
- at least two threads read (busy==false). 
- then both threads already write (turn=me).
- therefore only one thread will read (turn==me)‏

so, on second question your answer is NO, am I right ?

and you are right in your answer on the third question :) well done

for deeply understanding you can read additional materials like attached one.
CHAP5.ppt
1.7 MB   Download
Status: Verified
Sep 18, 2014
Project Member #3 sergeypr...@gmail.com
2.Yes, it is no deadlock-free. (I forgot to write it)
from CHAP5.ppt - I undertand that mutual exclusion - it is "только один поток может быть одновременно в расширяемом ресурсе" - то есть в критической секции.

Powered by Google Project Hosting