Groups > comp.programming.threads > #805

Re: Bakery algorithm - multithreading

Path	csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.posted.cloud9consultinginc!news.posted.cloud9consultinginc.POSTED!not-for-mail
NNTP-Posting-Date	Tue, 27 Dec 2011 14:42:46 -0600
Newsgroups	comp.programming.threads
From	"A. Bolmarcich" <aggedor@earl-grey.cloud9.net>
Subject	Re: Bakery algorithm - multithreading
References	<c8a777ad-e492-4d99-bff7-63f2d8415600@v24g2000yqk.googlegroups.com>
Message-ID	<slrnjfkbe6.doj.aggedor@earl-grey.cloud9.net> (permalink)
User-Agent	slrn/0.9.8.0 (FreeBSD)
Date	Tue, 27 Dec 2011 14:42:46 -0600
Lines	58
X-Usenet-Provider	http://www.giganews.com
NNTP-Posting-Host	168.100.1.1
X-Trace	sv3-PvxdsaARXMpCjiNhP0dbc8gJER2Qsna3eiD/iWMCSiaPdLT0DSCZIOTh0Z0OBvkww5sTq1xAJwOK081!OtXO9iYqLANdtcEwJIIiZBfEln8iFHpX/WCnMsTcMb9+DmxgU1GB5uUikIpgNsxJTdhArrHTboE3!m9gTISDEohaQ70NUPng=
X-Abuse-and-DMCA-Info	Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info	Otherwise we will be unable to process your complaint properly
X-Postfilter	1.3.40
X-Original-Bytes	2924
Xref	x330-a1.tempe.blueboxinc.net comp.programming.threads:805

Show key headers only | View raw

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.

Back to comp.programming.threads | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web