Hi

Situation:

i am making a table that containg multiple entries. there are two or more thread that are accessing the entries in the table. When the entry is accessed by one thread that entry MUST not be accessed be any other thread. Logical solution is to have a mutex for each entry.

Problem:

The problem is that it costs too much on memory and the size of each entry is increased TOO much :( and having a single mutex for the whole table is also not acceptable as it will block too often.

Proposed solution:

So instead of have a mutex, i have a 32-bit value for each entry .If the entry is in use, i set a sigle bit in the flag register. When any thread comes to use the entry, it first checks that bit. If it is not set (the entry is not in use), it is set and when it is no longer in use, it is reset. if the bit is already set, it means that the entry is in use and that thread does not access the entry. Its like having a boolean (IN-USE) flag for each entry in the table.

Problem with solution:

The only problem that i can think of is that, the time between the code checks the bit in flag, and when it set the bit is critical and MUST be done in a single execution, i.e no thread-switching between these two instructions. because if the thread switch between the two points, the other thread may also see that flag is not set and it will also access the entry. this situation is not good.

Question:

1) Is there any way to ensure that the checking of flag and setting it is done without swithching thread.
2) Is there any other way to go about the problem
3) The OS do the same thing somehow. Does anyone know how does the OS do it. Although it can as it control both the mutex and thread-switching
4) Can there be some ASM instruction that can check a condition and if that condition is true, set a flag, all in one instruction.

hoping for some answers :)

goto
Posted on 2002-11-05 00:05:04 by goto
What's wrong with using EnterCriticalSection ?

There's a whole set of SETXX instructions that set or clear AL based on the values of eflags, if that's what you are looking for. But it won't set a flag in memory.
Posted on 2002-11-05 02:12:21 by micmic

What's wrong with using EnterCriticalSection ?

There's a whole set of SETXX instructions that set or clear AL based on the values of eflags, if that's what you are looking for. But it won't set a flag in memory.

SETXX can set a flag in either memory or register...
but I don't think SETXX will do the job...


To goto,
1. Yes, you can code it like this,
invoke Sleep, 0
mov eax, address_of_mutex
cmp , NOT_OCCUPIED
jne wait
......

Passing 0 for dwMilliseconds means to discard the remainder of its time slice. Next time windows switches to this thread, the following code will run continuously (just a few clock cycles :) ).

2 & 3. Yes. If it's to be time critlcal and the table has many entries, better use critical sections, they're faster than kernel objects and you can even specify the spin count before EnterCriticalSection comes into sleep
(sdk says EnterCriticalSectionSpinCount doesn't exist in 95).
Posted on 2002-11-05 03:15:27 by C.Z.
if you were to put
mov eax, flag ;.......(a)
mov flag, 1 ;.......(b)
cmp eax, 1
je tryagainlater

would another thread have time to intrude
between (a) and (b) ?

or, using ffffffffh (instead of 1 )
sar flag
jc tryagainlater
mov flag, -1 ; now in use
code
mov flag, 0 ; finished
Posted on 2002-11-05 04:07:25 by argus
To Argus:
Another thread can intrude between any 2 instructions in any thread, if currrent thread is not of a realtime priority.
Posted on 2002-11-05 04:13:32 by Vaxon
i see, vaxxon

multithreading is not something i'm familiar with
..(among a whole host of other things!) ...:)


thank you
Posted on 2002-11-05 04:31:04 by argus
Probably not the most efficient, but in the main thread you could set up a
custom queue which could handle this.

So main thread (or a dedicated queue thread) has a queue. during idle
time it can check the queue for new entries. If the queue is not empty it
will pop the first one off and it will check the status. In other words, only
one thread is able to make the determination if access is grantable or not.
The whole thing can be coded using custom user messages like

invoke SendMessage, hQueue, QUEUE_CHECKSTATUS, ThisThreadID, Location
(add a queue entry)

Upon getting this the queue thread will check and send a message
back to giving access or not...

Just an idea to bat around if the others dont pan out...
Posted on 2002-11-05 08:51:51 by Graebel
Just read your post briefly, but here's what I have done for similar situations in the past: bts.

BTS will simultaneously set a bit in a memory value *and* copy that bit to the carry flag. By setting the bit you are indicating that you want to use the corresponding value in a particular thread. You just have to check the carry flag to see if the other thread was using it before you.

BTS can also be used with the LOCK prefix if you have multiple processors. If you only have one, though, you won't need to use LOCK

--Chorus
Posted on 2002-11-05 09:39:51 by chorus
thanks for all the help ppl :)

i have an anothere idea.

Can we stop the switching of thread by masking all the interrupts between checking of flag and setting of flag. No interrupts means no break in the execution of code and no thread switching, or am i wrong to assume that ?

goto
Posted on 2002-11-06 00:33:07 by goto
i asked the same questions on some other messageboard, and i will like to share this answer with u all and ask about ur comments on this


> 4) Can there be some ASM instruction that can check a condition and if
> that condition is true, set a flag, all in one instruction.

Yes, but believe it or not that's not enough. For example, suppose you
do a single instruction increment of a memory register on two processors
at the same time. The increment could be internally implemented as
read/modify/write. If the two processors work concurrently, they will
both read, both modify, and then both write. Oops, two increments just
became one.
Posted on 2002-11-06 00:57:34 by goto
How about:

mov eax,1
xchg Flag,eax
cmp eax,1
je Abort

The critical part is just one instruction (xchg) :grin:
Posted on 2002-11-06 01:07:41 by Qweerdy
goto, that's what the LOCK prefix is for, to prevent multiple processors from having the problem you describe...

It slows things down however...

--Chorus
Posted on 2002-11-06 18:09:57 by chorus

goto, that's what the LOCK prefix is for, to prevent multiple processors from having the problem you describe...

It slows things down however...

--Chorus
...and as Qweerdy points out, XCHG with memory has an implied LOCK and is the easiest solution to the problem. The CMPXCHG instruction was also created to make mutexes easier to code, but still requires the LOCK prefix.

A flag is not even needed to solve this problem: while the object is in use just NULL the pointer to indicate that it is being used and restore the pointer when done:
	mov esi, Table ; array of pointers

xor ebx, ebx
_1: xchg ebx, [esi]
add esi, 4
; do not need to test for end of Table if dummy object for each thread is at end of table!
test ebx, ebx
je _1

...do something...

mov [esi-4], ebx
; or during debug...
; xchg ebx, [esi-4]
; if ebx <> 0 ERROR!
; (should never happen)
Very little overhead in terms of execution speed and no overhead in terms of size. :)
Posted on 2002-11-06 20:50:31 by bitRAKE
1) Is there any way to ensure that the checking of flag and setting it is done without swithching thread.
The functions InterlockedCompareExchange, InterlockedExchangeAdd, InterlockedDecrement, InterlockedExchange, and InterlockedIncrement provide a simple mechanism for synchronizing access to a variable that is shared by multiple threads. The threads of different processes can use this mechanism if the variable is in shared memory.

Internally these functions are very simple and use xchg, xadd, cmpxchg to do the job.
Posted on 2002-11-07 04:02:13 by Four-F
bitRAKE,
not sure how mov eax,1/xchg Table[4*index],eax/cmp eax,1/je @@Somewhere is simpler than bts Table,index/jc @@Somewhere ??
Furthermore, using xchg you're using up to 4 bytes per flag instead of 1 bit.

Regardless, considering all solutions, I think yours is the best.
Posted on 2002-11-07 09:39:02 by chorus
chorus, there is no flag. ;) The object pointer in the array is set to zero to indicate it is in use. goto was concerned with the memory cost of having many entries in the table each with their own mutex data. I show a way to have no additional data and be thread safe. Imagine this senerio:

Thread 1: Test flag A
Thread 2: Test flag A
Thread 1: Flag okay, use object A!
Thread 2: Flag okay, use object A!

How does the method you suggest prevent this? Just imagine how bad this gets with mulitple processors. Now the method I propose (it is not mine - it has been used for decades) results in the following:

Thread 1: Swap in null for object pointer A
Thread 2: Swap in null for object pointer A
Thread 1: Not zero pointer, use object A.
Thread 2: Zero pointer, try next object.

It is important to look at the granularity of the code, taking into account where instructions can be interrupted, or (in a multi-processor system) where concurrent execution can occur. LOCK prevents concurrent execution on multi-processor systems. I have a dual system here to test on, too.
Posted on 2002-11-07 12:49:31 by bitRAKE
bitRAKE, it was Qweerdy's method that mentioned a Flag, ditto for mine. Both would require auxiliary storage. The method you proposed doesn't (and hence, that's why I like that one the best :))

As for preventing multiple threads accessing the same object, it's very simple:

Suppose you define



Array dd 32 dup (?)
FlagTable dd 0


the FlagTable is just a bit array representing whether or not a particular entry in Array is in use. 0 indicating no. 1 indicating yes.

Suppose your thread wants to access element at index eax. You have to set the corresponding bit, but also you want to know if someone was already using the entry.

BTS tells you this, because it copies the bit into the carry flag. If the carry flag was set than another thread was using it. If not, then it's free to use.

I use this in a server I've programmed to allocate send and recv buffers for overlapped I/O. It works quite well, and really only uses 2 lines of code. The only thing to be concerned about is the LOCK prefix. As you mentioned, XCHG implies the LOCK whereas BTS does not. For my application, that's fine because I'm only using a single processor computer, and if I can do without it, I will. Once you start getting into multiple processors though you really have no choice.
Posted on 2002-11-07 14:42:06 by chorus

bitRAKE,
not sure how mov eax,1/xchg Table[4*index],eax/cmp eax,1/je @@Somewhere is simpler than bts Table,index/jc @@Somewhere ??
Furthermore, using xchg you're using up to 4 bytes per flag instead of 1 bit.

Regardless, considering all solutions, I think yours is the best.

I don't see why it is the best.
bitRake method takes 32 times more memory and ~ the same amont of clocks against bit operations.
Posted on 2002-11-07 15:25:29 by The Svin

Hi

Situation:

i am making a table that containg multiple entries. there are two or more thread that are accessing the entries in the table. When the entry is accessed by one thread that entry MUST not be accessed be any other thread. Logical solution is to have a mutex for each entry.

Problem:

The problem is that it costs too much on memory and the size of each entry is increased TOO much :( and having a single mutex for the whole table is also not acceptable as it will block too often.

Proposed solution:

So instead of have a mutex, i have a 32-bit value for each entry .If the entry is in use, i set a sigle bit in the flag register. When any thread comes to use the entry, it first checks that bit. If it is not set (the entry is not in use), it is set and when it is no longer in use, it is reset. if the bit is already set, it means that the entry is in use and that thread does not access the entry. Its like having a boolean (IN-USE) flag for each entry in the table.

Problem with solution:

The only problem that i can think of is that, the time between the code checks the bit in flag, and when it set the bit is critical and MUST be done in a single execution, i.e no thread-switching between these two instructions. because if the thread switch between the two points, the other thread may also see that flag is not set and it will also access the entry. this situation is not good.

Question:

1) Is there any way to ensure that the checking of flag and setting it is done without swithching thread.
2) Is there any other way to go about the problem
3) The OS do the same thing somehow. Does anyone know how does the OS do it. Although it can as it control both the mutex and thread-switching
4) Can there be some ASM instruction that can check a condition and if that condition is true, set a flag, all in one instruction.

hoping for some answers :)

goto


1.If you care of memory use bits not dwords as flags
2.If you set bit that you expect to be zero and flags
not set after operation as they should be when when zero bit is set - it indicates that bit was changed and give you additional chance to exit.
bt - test bit
bts - set bit checking if it was set before.
Posted on 2002-11-07 15:42:55 by The Svin


I don't see why it is the best.
bitRake method takes 32 times more memory and ~ the same amont of clocks against bit operations.
Please, re-read - there is no flag = zero more memory used.

chorus, good to see you understand the limitations of the method. It would be a nasty bug to find on a multi-processor system. :)

p.s. Wonder how hyper-threading effects these methods?
Posted on 2002-11-07 16:34:38 by bitRAKE