Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #800 > unrolled thread

Bakery algorithm - multithreading

Back to article view | Back to comp.programming.threads

Contents

  Bakery algorithm - multithreading persres <persres@gmail.com> - 2011-12-23 14:30 -0800
    Re: Bakery algorithm - multithreading "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2011-12-27 14:42 -0600

#800 — Bakery algorithm - multithreading

Hi,
   I saw this code from the book (http://www.faculty.idc.ac.il/gadi/
book.htm)  -

choosing[i] = true
number[i] = 1 + max(number[1], number[2],...., number[n])
choosing[i] = false
for j = 1 to n do
       wait_until(choosing[j] = false)
       wait_until(number[j] = 0 or  (number[j], j ) >= (number[i],
i)  )        ------> Step 6
od
critical section
number[i] = 0


The code for max is -
l1 = 0
for l2 = 1 to n do
      l3 = number[l2]
      if l1 < l3 then l1 = l3 fi
od


A simple algorithm to synchronise n processes. In the above code i is
for process i. The number and choosing are shared registers.

I don't understand why we need the array choosing. After all, the
condition in step 6 should ensure that process i and process j can
never get into the critical section at the same time.

Can some one see through this and say if the array choosing can be
removed.
Thanks

[toc] | [next] | [standalone]

#805

On 2011-12-23, persres <persres@gmail.com> wrote:
> Hi,
>    I saw this code from the book (http://www.faculty.idc.ac.il/gadi/
> book.htm)  -
>
> choosing[i] = true
> number[i] = 1 + max(number[1], number[2],...., number[n])
> choosing[i] = false
> for j = 1 to n do
>        wait_until(choosing[j] = false)
>        wait_until(number[j] = 0 or  (number[j], j ) >= (number[i],
> i)  )        ------> Step 6
> od
> critical section
> number[i] = 0
>
>
> The code for max is -
> l1 = 0
> for l2 = 1 to n do
>       l3 = number[l2]
>       if l1 < l3 then l1 = l3 fi
> od
>
>
> A simple algorithm to synchronise n processes. In the above code i is
> for process i. The number and choosing are shared registers.
>
> I don't understand why we need the array choosing. After all, the
> condition in step 6 should ensure that process i and process j can
> never get into the critical section at the same time.
>
> Can some one see through this and say if the array choosing can be
> removed.

If the array choosing or the wait_until(choosing[j] = false) is removed,
two processes may be in the critical section at the same time.  The
following sequence of events is possible.

- process 2 does max(number[1:n]) and gets 0

- process 1 does max(number[1:n]) and gets 0

- process 2 does number[2] = 1 + 0 (0 gotten slightly earlier for
max(number[1:n])

- process 2 enters critical section, the wait_until is true for all j
((number[1] = 0) and (number[2],2) >= (number[2],2))

- process 1 does number[1] = 1 + 0 (0 gotten slightly earlier for
max(number[1:n])

- process 1 enters critical section, the wait_until is true for all j (
(number[1],1) >= (number[1],1)) and (number[2],2) >= (number[1],1))

The array choosing is used so that while process i is determine the value
to store in number[i] no other process uses number[i] to determine whether
it may enter the critical section.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web