<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
I do currently still use the critical section "throughout 'all' of AssignSlot".<BR>
The memory barrier doesn't replace it there. Just makes it carefully ordered so other readers see things reasonably well.<BR>
<BR>
I DO suspect the locking in AssignSlot can be reduced but haven't done so yet.<BR>
Maybe it doesn't work out.<BR>
<BR>
- Jay<BR><BR> <BR>
<HR id=stopSpelling>
From: hosking@cs.purdue.edu<BR>To: jay.krell@cornell.edu<BR>Date: Wed, 11 Nov 2009 09:23:59 -0500<BR>CC: m3devel@elegosoft.com<BR>Subject: Re: [M3devel] FreeSlots/lookup slot locking<BR><BR>
<DIV><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="WORD-WRAP: break-word"><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="WORD-WRAP: break-word"><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV><SPAN style="FONT-SIZE: medium" class=ecxApple-style-span><FONT class=ecxApple-style-span color=#0000ff face="'Gill Sans'">It's not the allocation I worry about.</FONT></SPAN></DIV>
<DIV><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255); FONT-SIZE: medium" class=ecxApple-style-span>How do you avoid two threads getting the same slot?</SPAN></DIV></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></DIV></SPAN></DIV></SPAN></DIV><BR>
<DIV>
<DIV>On 11 Nov 2009, at 01:11, Jay K wrote:</DIV><BR class=ecxApple-interchange-newline>
<BLOCKQUOTE><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxhmmessage>Tony:<BR><BR>> Also, I am unconvinced that the current implementation of AssignSlot can ever<BR>> be correct without the critical section. It requires atomic update of both<BR>> the slots array pointer (with the new slots) *and* the array elements. This<BR>> requires a proper CS instead of non-blocking synchronization.<BR><BR> <BR>I don't see it.<BR>I could be wrong.<BR> <BR>The writes are done within a critical section, to avoid racing with other writers.<BR> <BR>Writes interact with readers in that:<BR> <BR> SUBARRAY (new_slots^, 0, n) := slots^;<BR>finish writing to the array elements<BR>MemoryBarrier<BR> slots := new_slots;<BR><BR> <BR>so readers don't see slots unless it has been fully initialized.<BR> <BR>AssignSlots should also be able to be lock free via InterlockedCompareExchangePointer.<BR> <BR> <BR> - Jay<BR> <BR></DIV></SPAN></BLOCKQUOTE></DIV><BR> </body>
</html>