Talk:Mutual exclusion
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions. |
| Start | rated as start-Class on the assessment scale |
| Top | rated as Top-importance on the assessment scale |
Which of the following algorithm give the right solution for mutual exclusion? a. Disabling interrupts b. Lock variables c. Strict alternation d. Peterson’s solution e. TSL instruction
Taken from the main page:
- One intriguing non-classical scheme sends messages between pieces of code. This permits priority inversions, and increases latency but makes deadlocks unlikely.
It was proven decades ago (Herlihy?) that message-passing systems are incapable of achieving system-wide wait-free or lock-free consensus. I fail to see how this proposal is anything stronger. Have I missed something? -- Chris Purcell 23:42, 6 January 2006 (UTC)
Contents |
[edit] MuTeX
There is also a LaTeX extension called MuTeX
[edit] Mutex
Should Mutex redirect to lock instead? —Preceding unsigned comment added by 128.113.139.187 (talk) 13:57, 10 December 2007 (UTC)
[edit] Selective Concurrent Access
I was faced with the challenge of being able to very efficiently access a linked list by many threads concurrently, without blocking each other on traversal while at the same time restricting concurrent access by all but the one thread during insertion or deletion. This was a selective concurrent method that I used. - C. Jutzi - Jan 2008
[edit] CHALLENGE
- The first two sections of code can be executed by any number of threads concurrently without restriction, but must restrict any other thread from concurrently accessing either of the other two sections of code.
- The other two sections need have exclusive access to resources and must restrict each other as well as the first two.
[edit] EXAMPLE:
- a) traverse link list code section 1..
- b) traverse link lint code section 2..
- c) insert to linked list
- d) remove form linked list
A Traverse List B Traverse List C Add Link D Remove Link
lock (foo) lock (foo) do { do {
f_dont = true; f_dont = true lock(foo) lock(foo)
unlock (foo) unlock (foo) if (!f_dont) if (!f_dont)
... ... break break
< critical section > < critical section > unlock(foo) unlock(foo)
... ... } while (1) } while (1)
f_dont = false f_dont = false ... ...
< critical section > < critical section >
... ...
unlock (foo) unlock (foo)
[edit] Example Code - Lock
I needed a very fast lock/unlock solution. EnterCriticalSection and LeaveCriticalSection from Microsoft (TM) were way too slow for what I needed. This solution does not work like CriticalSections in Microsoft. In this case the same thread will block if called recursively. Here is a working solution for the Intel (TM) Architecture. It uses in-line assembler and the bit test and set as well as the bit test and reset. Interesting that all the searching on the internet for such a code sample did not result in anything. It was simpler to just open my ia32 user manual :-). The one thing I had to dig harder on was the "lock" key word for the in-line _asm which made it autonomous. I still didn't quite understand why it doesn't work without it, given that if I was swapped out between the bit test and set and the SETC that the result would be the same. I'm assuming the swap would include the full state. I'm still missing something. It does not work without it. I'd love to hear why.
You can use differing bit-fields in the "iLock" for different locks. Much more space efficient than dedicating an entire "CriticalSection", but then again, I used to program with cards and 64K was all we had :-). You decide.. - C. Jutzi - Jan 2008
unsigned int iLock
/****************************************************************/
/* */
/* Proceedure: MYLOCK () */
/* */
/* Description: */
/* Simple Lock */
/* */
/* Assumptions: */
/* iLock is shared */
/* calling thread only locks once i.e. not recursive */
/* */
/****************************************************************/
void MYLOCK()
{
int icarry;
do {
_asm {
Lock BTS iLock,0x01
SETC icarry
}
} while (icarry != 0);
}
/******************************************************************/
/* */
/* Proceedure: MYUNLOCK () */
/* */
/* Description: */
/* Simple UnLock */
/* */
/* Assumptions: */
/* iLock is shared */
/* calling thread only unlocks once i.e. not recursive */
/* */
/******************************************************************/
void MYUNLOCK()
{
int icarry;
_asm
{
Lock BTR iLock,0x01
SETC icarry
}
_ASSERT(icarry);
}
