Atomicity Post: 50804

Sponsored Content

Top Forums Programming Atomicity Post 50804 by S.P.Prasad on Monday 3rd of May 2004 06:56:38 AM

05-03-2004

Registered User

First of all I would like to state that the pseudo-code I have written in my initial post needs modification. Instead of writing LOCK () and REL() as two separate functions, it would be only one subroutine LOCK_REL() implementing the pseudo-code.

Quote:

How are the variables shared - using shared memory?

Yes. This concept is already implemented in the project. All I need to is add up the required variables.

Quote:

No, you can also use a single lock for all resources, so that you might get heavy lock contention but still permit multiple processes to operate independently.

I studied the pseudo-code but that's what exactly we do not want. For example there are 10 process. Assume 2 different process would like to implement LOCK on the array and while 3 different process tries to REL the LOCK on the same array. Only one of the process should succeed for a specific array operation.

Further more of the remaining 5, 3 different process are trying to implement LOCK on 3 different arrays and 2 are REL two separate arrays, then they very well should. I mean they should not wait other wise timing would become a major issue i.e. time to process one transaction would increase.

Here's a sample view of what I would like to implement atomically:

Process'xx'1'xxxxx'2'xxxxx'3'xxxx'4'xxxxx'5'xxxxx'6'
Array'xxxx'A'xxxxx'B'xxxxx'C'xxxx'D'xxxxx'E'xxxxx'F'

xxxxxxxx ..... xxxx..... xx..... xxxx..... xxx......xxx.........
xxxxxxxxL(D)xxxxL(D)xxR(D)xxxxL(E)xxxR(F)xxxL(A)
xxxxxxxx ..... xxxx..... xx..... xxxx..... xxx......xxx.........

Where L stands for LOCK and R stands for REL the lock on array passed as arguments and value at array index 1 states whether array is locked ( value 1 ) or unlock ( value 0 ) . Please ignore the x's as I have put it for alignment purpose

I hope that I am clear in my requirement.

Thanks in advance.

Last edited by S.P.Prasad; 05-03-2004 at 09:55 AM..

S.P.Prasad

View Public Profile for S.P.Prasad

Find all posts by S.P.Prasad

LEARN ABOUT DEBIAN

bup-margin

bup-margin(1)						      General Commands Manual						     bup-margin(1)

NAME

       bup-margin - figure out your deduplication safety margin

SYNOPSIS

       bup margin [options...]

DESCRIPTION

       bup margin  iterates  through  all  objects  in	your  bup repository, calculating the largest number of prefix bits shared between any two
       entries.  This number, n, identifies the longest subset of SHA-1 you could use and still encounter a collision between your object ids.

       For example, one system that was tested had a collection of 11 million objects (70 GB), and bup margin returned 45.  That  means  a  46-bit
       hash  would be sufficient to avoid all collisions among that set of objects; each object in that repository could be uniquely identified by
       its first 46 bits.

       The number of bits needed seems to increase by about 1 or 2 for every doubling of the number of objects.  Since SHA-1 hashes have 160 bits,
       that  leaves 115 bits of margin.  Of course, because SHA-1 hashes are essentially random, it's theoretically possible to use many more bits
       with far fewer objects.

       If you're paranoid about the possibility of SHA-1 collisions, you can monitor your repository by running bup margin occasionally to see	if
       you're getting dangerously close to 160 bits.

OPTIONS

       --predict
	      Guess  the offset into each index file where a particular object will appear, and report the maximum deviation of the correct answer
	      from the guess.  This is potentially useful for tuning an interpolation search algorithm.

       --ignore-midx
	      don't use .midx files, use only .idx files.  This is only really useful when used with --predict.

EXAMPLE

	      $ bup margin
	      Reading indexes: 100.00% (1612581/1612581), done.
	      40
	      40 matching prefix bits
	      1.94 bits per doubling
	      120 bits (61.86 doublings) remaining
	      4.19338e+18 times larger is possible

	      Everyone on earth could have 625878182 data sets
	      like yours, all in one repository, and we would
	      expect 1 object collision.

	      $ bup margin --predict
	      PackIdxList: using 1 index.
	      Reading indexes: 100.00% (1612581/1612581), done.
	      915 of 1612581 (0.057%)

SEE ALSO

       bup-midx(1), bup-save(1)

BUP

       Part of the bup(1) suite.

AUTHORS

       Avery Pennarun <apenwarr@gmail.com>.

Bup unknown-															     bup-margin(1)