Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > A bit resistant to disruption

Reply
Thread Tools

A bit resistant to disruption

 
 
Francois Grieu
Guest
Posts: n/a
 
      02-09-2010
Seebs wrote:
> On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>>> void
>>> bToggle(void) {
>>> int t;
>>> if (eRead(2)) {
>>> t = eRead(1);
>>> eErase(0);
>>> if (t)
>>> eProgram(0); // [B]
>>> eErase(2); // [A]
>>> }
>>> t = eRead(0);
>>> eErase(1);
>>> if (t)
>>> eProgram(1);
>>> eProgram(2);
>>> eErase(0);
>>> if (!t)
>>> eProgram(0);
>>> eErase(2);
>>> }

>
>> This one is incorrect. Assume a disruption where I inserted [A]; now
>> cell 2 is uncertain. Assume cell 2 is read as 1 during the next bToggle,
>> and a disruption occurs at [B]; now cells 0 and 2 are uncertain, and
>> bRead can return 0 (if cells 2 and 0 are read as 0) or 1 (if cell 2 is
>> read as 0 and cell 0 is read as 1).

>
> Okay, I misunderstood the spec. I thought that an erase necessarily
> either worked or failed to work, and couldn't leave a cell indeterminate.
> Re-reading the spec, I see that isn't correct. That does make this a
> lot trickier.
>
>> Hint: there's nothing to prevent bRead from invoking eErase or/and eProgram.

>
> True. I'm not sure how it matters, though; a hypothetical user can just run
> bToggle() over and over without ever hitting bRead(), so I can't usefully
> rely on anything it does, I don't think.


Notice that after one (or several) disrupted bToggle(), the next
undisrupted bRead() can return anything. One attractive option is thus
that this undisrupted bRead() does cleanup so that the next undisrupted
bRead() will return the right value.

> I'm assuming this has to work
> in the general case, not just in the specific example case given.


Yes. But if you can make some bRead()/bToggle() that work in my use
case, it is easy to exhibit a fully correct bRead()/bToggle2(): just define

void bToggle2(void )
{
(void) bRead();
bToggle();
}

The proof is left as a relatively easy exercise to the reader.

> I suspect this could be solved with another bit, but I'm too sleepy to figure
> out how right now.


Good night..

Francois Grieu
 
Reply With Quote
 
 
 
 
Seebs
Guest
Posts: n/a
 
      02-09-2010
On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>> // Read a designated EEPROM cell; always returns 0 or 1.
>> extern int eRead(int j);
>> // Erase a designated EEPROM cell.
>> // After undisrupted eErase, eRead returns 0 until eProgram is invoked.
>> extern void eErase(int j);
>> // Program a designated *ERASED* EEPROM cell.
>> // After undisrupted eProgram, eRead returns 1 until eErase is invoked.
>> // Programming a cell that is not erased cause undefined behavior.
>> extern void eProgram(int j);


[re: my first attempt]
> This one is incorrect. Assume a disruption where I inserted [A]; now
> cell 2 is uncertain. Assume cell 2 is read as 1 during the next bToggle,
> and a disruption occurs at [B]; now cells 0 and 2 are uncertain, and
> bRead can return 0 (if cells 2 and 0 are read as 0) or 1 (if cell 2 is
> read as 0 and cell 0 is read as 1).
>
> Hint: there's nothing to prevent bRead from invoking eErase or/and eProgram.


I get it! The risk here is that if eRead() returns unreliable results,
future queries of the same bit may not yield the same results, resulting
in inconsistent flow through the program logic; in particular, attempts
might be made to modify things based on spurious data.

So.

int
bSureOf(int j) {
if (eRead(j)) {
eErase(j);
eProgram(j);
return 1;
} else {
eErase(j);
return 0;
}
}

int
bRead(void) {
if (bSureOf(2)) {
return eRead(1);
} else {
return eRead(0);
}
}

void
bToggle(void) {
int t;
if (bSureOf(2)) {
t = eRead(1);
eErase(0);
if (t)
eProgram(0);
eErase(2);
}
t = eRead(0);
eErase(1);
if (t)
eProgram(1);
eProgram(2);
eErase(0);
if (!t)
eProgram(0);
eErase(2);
}

We start with all bits clear. bSureOf(2) erases 2, just to be cautious,
but returns 0. We read a bit. We erase bit 1 (also clear at the moment,
but who cares), and don't program it. So far, nothing has been changed.
At this point, we start trying to write 2. If this is interrupted, two
possibilities exist:

1. The attempted read in the next hit of bSureOf() comes up 0; we
forcibly erase bit 2, and trust bit 0, which was correct.
2. The attempted read in the next hit of bSureOf() comes up 1; we
forcibly erase-and-write bit 2, and trust bit 1, which was correct.

Either way, if we get past any check on bit 2, we have a
correct and consistent state. Thus, eventually we come to the eErase(0),
which occurs only when bit 2 is definitely known to be set to 1. We now
try to set bit 0 to its new value. Once that happens, we try to clear
bit 2. If we succeed, all is well -- bit 2 is clear, bit 0 is the toggled
state. If we are interrupted, one of two things can happen on the next
read:

1. The attempted read in bSureOf(2) comes up 0; we forcibly erase
bit 2, and we continue to use the new, toggled, state of bit 0. Our
behavior is consistent.

2. The attempted read in bSureOf(2) comes up 1; we try to write bit
2, and if we succeed, we fall back on the not-yet-toggled state of bit
1. Since the toggle was interrupted, this behavior is acceptable.

3. The attempted read in bSureOf(2) comes up 1; we try to write bit
2, but are interrupted somewhere during it. It is still ambiguous whether
the toggle has succeeded, but no matter what happens, if bRead() returns,
we will have either toggled or failed to toggle the bit.

If bit 2 is set, then bit 1 has definitely been set to the most recently
returned value. (It is possible that we've since tried to store a toggled
value in bit 0, but if we were interrupted, we haven't returned it so we
don't need to show that new value yet.) If bit 2 is not set, then bit 0
definitely holds either the last returned value, or the most recently toggled
value. Either way, before we return, we commit to bit 2's perceived state.
If that is interrupted, that's okay -- eRead() doesn't return a value, because
it was disrupted, so we haven't returned a wrong value.

.... I think.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
 
 
 
Francois Grieu
Guest
Posts: n/a
 
      02-09-2010
Seebs wrote:
> On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>>> // Read a designated EEPROM cell; always returns 0 or 1.
>>> extern int eRead(int j);
>>> // Erase a designated EEPROM cell.
>>> // After undisrupted eErase, eRead returns 0 until eProgram is invoked.
>>> extern void eErase(int j);
>>> // Program a designated *ERASED* EEPROM cell.
>>> // After undisrupted eProgram, eRead returns 1 until eErase is invoked.
>>> // Programming a cell that is not erased cause undefined behavior.
>>> extern void eProgram(int j);

>
> [re: my first attempt]
>> This one is incorrect. Assume a disruption where I inserted [A]; now
>> cell 2 is uncertain. Assume cell 2 is read as 1 during the next bToggle,
>> and a disruption occurs at [B]; now cells 0 and 2 are uncertain, and
>> bRead can return 0 (if cells 2 and 0 are read as 0) or 1 (if cell 2 is
>> read as 0 and cell 0 is read as 1).
>>
>> Hint: there's nothing to prevent bRead from invoking eErase or/and eProgram.

>
> I get it! The risk here is that if eRead() returns unreliable results,
> future queries of the same bit may not yield the same results, resulting
> in inconsistent flow through the program logic; in particular, attempts
> might be made to modify things based on spurious data.


Yes. See below

> So.
>
> int
> bSureOf(int j) {
> if (eRead(j)) {
> eErase(j);
> eProgram(j);
> return 1;
> } else {
> eErase(j);
> return 0;
> }
> }
>
> int
> bRead(void) {
> if (bSureOf(2)) {
> return eRead(1);
> } else {
> return eRead(0);
> }
> }
>
> void
> bToggle(void) {
> int t;
> if (bSureOf(2)) {
> t = eRead(1);
> eErase(0);
> if (t)
> eProgram(0); // [B]
> eErase(2);
> }
> t = eRead(0);
> eErase(1);
> if (t)
> eProgram(1);
> eProgram(2);
> eErase(0); // [A]
> if (!t)
> eProgram(0);
> eErase(2);
> }


Assume that on a bToggle(), a disruption occurs where I added [A], tus
with cell 2 fully programmed. Assume the next disruption occurs in the
next bToggle(), which will thus take the branch where I added [B].
Assume this disruption is during the eProgram(0) on the left of [B],
leaving cell 0 undefined, and cell 2 fully programmed.
An undisrupted bRead now returns eRead(0), which is unspecified, and
leaves cell 2 fully programmed. Thus two undisrupted bRead() without a
bToggle() in between can return different results. Bust.

[snip]
Francois Grieu
 
Reply With Quote
 
Francois Grieu
Guest
Posts: n/a
 
      02-09-2010
[I messed up my earlier reply, sorry; let me try again]

Seebs wrote :
> On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>>> // Read a designated EEPROM cell; always returns 0 or 1.
>>> extern int eRead(int j);
>>> // Erase a designated EEPROM cell.
>>> // After undisrupted eErase, eRead returns 0 until eProgram is invoked.
>>> extern void eErase(int j);
>>> // Program a designated *ERASED* EEPROM cell.
>>> // After undisrupted eProgram, eRead returns 1 until eErase is invoked.
>>> // Programming a cell that is not erased cause undefined behavior.
>>> extern void eProgram(int j);

>
> [re: my first attempt]
>> This one is incorrect. Assume a disruption where I inserted [A]; now
>> cell 2 is uncertain. Assume cell 2 is read as 1 during the next bToggle,
>> and a disruption occurs at [B]; now cells 0 and 2 are uncertain, and
>> bRead can return 0 (if cells 2 and 0 are read as 0) or 1 (if cell 2 is
>> read as 0 and cell 0 is read as 1).
>>
>> Hint: there's nothing to prevent bRead from invoking eErase or/and eProgram.

>
> I get it! The risk here is that if eRead() returns unreliable results,
> future queries of the same bit may not yield the same results, resulting
> in inconsistent flow through the program logic; in particular, attempts
> might be made to modify things based on spurious data.


Yes. See below

> So.
>
> int
> bSureOf(int j) {
> if (eRead(j)) {
> eErase(j); // [C]
> eProgram(j);
> return 1;
> } else {
> eErase(j);
> return 0;
> }
> }
>
> int
> bRead(void) {
> if (bSureOf(2)) {
> return eRead(1);
> } else {
> return eRead(0);
> }
> }
>
> void
> bToggle(void) {
> int t;
> if (bSureOf(2)) {
> t = eRead(1);
> eErase(0);
> if (t)
> eProgram(0); // [B]
> eErase(2);
> }
> t = eRead(0);
> eErase(1);
> if (t)
> eProgram(1);
> eProgram(2);
> eErase(0); // [A]
> if (!t)
> eProgram(0);
> eErase(2);
> }
>


We get a fist disruption at [A]. Cell 2 is fully programmed. Next
disruption is when bToggle() is doing eProgram(0) on the left of [B].
Cell 0 is undefined. We then do bRead() which is disrupted during
bSureOf(2), after eErase(2) at [C]. Now cell 2 is erased, and an
undisrupted bRead() returns eRead(0), which is unspecified. Two
undisrupted bRead() without a bToggle() in betwwen can thus return
different values. Bust.

[snip]
Francois Grieu
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      02-09-2010
On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
> [I messed up my earlier reply, sorry; let me try again]


No worries. I already found a bug in this one, which is that if we're
currently pointing at cell 1, and cell 1 and cell 0 are different, multiple
successive bRead() calls could inadvertantly flip back to cell 0 without
a toggle.

Hmm.

Does an eErase() of a cell which is already zero risk creating indeterminacy,
or does it stay zero regardless of disruptions?

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / (E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
Francois Grieu
Guest
Posts: n/a
 
      02-09-2010
Seebs wrote:
> On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>> [I messed up my earlier reply, sorry; let me try again]

>
> No worries. I already found a bug in this one, which is that if we're
> currently pointing at cell 1, and cell 1 and cell 0 are different, multiple
> successive bRead() calls could inadvertantly flip back to cell 0 without
> a toggle.
>
> Hmm.
>
> Does an eErase() of a cell which is already zero risk creating indeterminacy,


No. I wanted that to be implied by "After undisrupted eErase, eRead
returns 0 until eProgram is invoked." and confirmed by "An EEPROM cell
can be left neither erased nor programmed by a disrupted eErase unless
that cell was already erased".

> or does it stay zero regardless of disruptions?


I stays zero.

It took some effort to have the maker of the EEPROM assert that. I have
strong arguments towards the conjecture that the problem can't be solved
if this insurance is removed.


Francois Grieu
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      02-09-2010
On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>> Does an eErase() of a cell which is already zero risk creating indeterminacy,

>
> No. I wanted that to be implied by "After undisrupted eErase, eRead
> returns 0 until eProgram is invoked." and confirmed by "An EEPROM cell
> can be left neither erased nor programmed by a disrupted eErase unless
> that cell was already erased".
>
>> or does it stay zero regardless of disruptions?

>
> I stays zero.


Okay.

> It took some effort to have the maker of the EEPROM assert that. I have
> strong arguments towards the conjecture that the problem can't be solved
> if this insurance is removed.


I believe you are correct.

So, it seems like the key gimmick would be to have values where "0" is a
safe state, so if they look to be 0, you can set them to 0 unconditionally.

Hmm. This is pretty tricky. I am pretty sure it's doable, but everything
I've come up with so far ends up in a case where you can't tell which bit
is indeterminate, and trying to stabilize them risks leaving two bits
indeterminate.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / (E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
Moi
Guest
Posts: n/a
 
      02-10-2010
On Tue, 09 Feb 2010 08:15:20 +0100, Francois Grieu wrote:

> Moi wrote :
>> On Mon, 08 Feb 2010 07:26:45 +0100, Francois Grieu wrote:
>>

>
>> I think that your failed eeprom_reset_bit() and eeprom_set_bit()
>> operations are more or less equivalent to Lamport's "sending messages
>> to another process". Messages can be lost in transit, your
>> eeprom-operations can fail because of a crash.
>> The only difference is that in the eeprom-case there is a sort of
>> tri-state logic; in the case of lost messages the domain stays
>> restricted to just two cases.

>
> Yes I see your point. One redeeming difference is that things are
> strictly sequential / singe-process in my case.


Yes, but in fact, messages are the building blocks of any kind
of atomicity / serialisation. A message can be recieved (and processed)
or not.


IMHO your eeprom-casus is in essence a sychronisation problem; there
may be a difference (in state) between the eeprom and what the program
knows. Sending (lossy) messages to and from the eeprom helps the program to
adapt its views. (or impose its will on the poor eeprom
The fact that there is only one "writer" makes it simpler than concurrency
problems, but not basically different.


BTW is there an elegant way to emulate a faulty eeprom by e.g. a diskfile ?
something like:
{ write random value to cell; sync;
wait a second;
write good value to cell; sync;
}??

(with the exception of erasing an empty cell, which should always be a no-op)

BTW, I think I need 3 bits to store one non-lossy bit.
AvK

 
Reply With Quote
 
Francois Grieu
Guest
Posts: n/a
 
      02-10-2010
Moi wrote:
> On Tue, 09 Feb 2010 08:15:20 +0100, Francois Grieu wrote:
>
>> Moi wrote :
>>> On Mon, 08 Feb 2010 07:26:45 +0100, Francois Grieu wrote:
>>>
>>> I think that your failed eeprom_reset_bit() and eeprom_set_bit()
>>> operations are more or less equivalent to Lamport's "sending messages
>>> to another process". Messages can be lost in transit, your
>>> eeprom-operations can fail because of a crash.
>>> The only difference is that in the eeprom-case there is a sort of
>>> tri-state logic; in the case of lost messages the domain stays
>>> restricted to just two cases.

>> Yes I see your point. One redeeming difference is that things are
>> strictly sequential / singe-process in my case.

>
> Yes, but in fact, messages are the building blocks of any kind
> of atomicity / serialisation. A message can be recieved (and processed)
> or not.
>
>
> IMHO your eeprom-casus is in essence a sychronisation problem; there
> may be a difference (in state) between the eeprom and what the program
> knows. Sending (lossy) messages to and from the eeprom helps the program to
> adapt its views. (or impose its will on the poor eeprom
> The fact that there is only one "writer" makes it simpler than concurrency
> problems, but not basically different.


Agreed.
>
> BTW is there an elegant way to emulate a faulty eeprom by e.g. a diskfile ?
> something like:
> { write random value to cell; sync;
> wait a second;
> write good value to cell; sync;
> }??


[OT] behavior of diskfiles under power disruption is notoriously
erratic; many hard disks have a write cache and some reorder writes..[/OT].

I'm thinking of a testbed program that does a randomized simulation,
using setjmp/longjmp to gracefully exit eProgram/eErase.

One issue is to zero the global or/and static variables on restart; for
now I only see these solutions:
- impose a special convention to the code under test;
- implement a C interpreter;
- assume things on the addresses of global or/and static variable;
- restart the test program using a script;
- restart the test program using system() from a supervising C program.

> (with the exception of erasing an empty cell, which should always be a no-op)
>
> BTW, I think I need 3 bits to store one non-lossy bit.


I come to the same conclusion. My best (hopefully) correct solution uses
at most 5 eErase() or eProgram() for the first bRead(), 2 eErase() or
eProgram() for the first subsequent bToggle(), 1 eErase or eProgram for
another subsequent bToggle().


Francois Grieu
 
Reply With Quote
 
Moi
Guest
Posts: n/a
 
      02-10-2010
On Wed, 10 Feb 2010 13:28:35 +0100, Francois Grieu wrote:

> Moi wrote:


>>
>> BTW is there an elegant way to emulate a faulty eeprom by e.g. a
>> diskfile ? something like:
>> { write random value to cell; sync;
>> wait a second;
>> write good value to cell; sync;
>> }??

>
> [OT] behavior of diskfiles under power disruption is notoriously
> erratic; many hard disks have a write cache and some reorder
> writes..[/OT].


But, in this case it is just what we want!


>> BTW, I think I need 3 bits to store one non-lossy bit.

>
> I come to the same conclusion. My best (hopefully) correct solution uses
> at most 5 eErase() or eProgram() for the first bRead(), 2 eErase() or
> eProgram() for the first subsequent bToggle(), 1 eErase or eProgram for
> another subsequent bToggle().
>


Mine uses one bit_set() or bit_erase() per toggle.
initialisation (after possible crash) is a bit more expensive;
2 or 3 bitops.

BTW: can I rely on the program to crash (and be restarted) on a glitch,
or should the program test itself whether an operation succeeded ?

AvK

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Disruption & Market Control Lawrence D'Oliveiro NZ Computing 8 04-03-2008 11:48 PM
Script disruption with Macromedia Flash HellPope Huey Firefox 4 08-16-2005 07:42 PM
How water resistant is a water resistant lens? Derek Fountain Digital Photography 2 03-18-2005 11:30 AM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit,Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new! Ionizer Computer Support 1 01-01-2004 07:27 PM
Re: adsl service disruption JM Computer Support 0 07-22-2003 07:53 AM



Advertisments