Talk:Mutual exclusion

Untitled

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— Preceding unsigned comment added by 202.150.91.82 (talk • contribs) 01:41, 26 September 2005

---

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)

Mutual Exclusion Principle

The Critical section problem can be solved by employing a principle called mutual exclusion which supply stated means that only one of the processes is allowed to execute in its critical section at a time; that is, no two processes can be under execution simultaneously inside a critial section . Execution of one process in a critical section excludes the possibility of execution of another process in that critical section. —Preceding unsigned comment added by 59.94.179.178 (talk) 04:00, 6 March 2009 (UTC)
Edited by Parthi

MuTeX

There is also a LaTeX extension called MuTeX

Mutex

Should Mutex redirect to lock instead? —Preceding unsigned comment added by 128.113.139.187 (talk) 13:57, 10 December 2007 (UTC)

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

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.
• Mutual Exclusion for a second and two of our threads want to increment a shared variable, conveniently called i with a nice and simple command such as i++.

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)

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);

}

Your bit handling instructions need to perform two memory cycles: a READ cycle to get a byte/word into the processor register to perform TEST on a selected bit, then a WRITE cycle to store the modified value. I suspect the hardware interrupt can suspend the instruction execution in the middle, between those cycles. If this happens when a thread attempts to LOCK a free critical section, and if the interrupt handling routine decides to switch threads, then the new thread may get a successful LOCK, then the control returns to the suspended thread, which already 'knows' the section is free, and locks it, too. Eventually you have two threads inside the section.
Even if I'm wrong about BTS suspension, there is another scenario possible in multi-CPU system: the CPU may perform its READ cycle between READ and WRITE cycles of another CPU. Then two (or more) threads running on separate CPUs may step into the section at the same time. The lock keyword makes a CPU to perform the READ-MODIFY-WRITE sequence as uninterruptible — no other bus master unit will access the memory until the sequence finishes. This prevents interleaving R-M-W cycles of different CPUs and guarantees BTS and BTR instructions work as expected. --CiaPan (talk) 21:18, 12 October 2009 (UTC)

Spin-Locks as anti-patterns

I have a problem with the phrase: "Unfortunately, spin locks and busy waiting take up excessive processor time and power and are considered anti-patterns in almost every case." which this is true for a lot of cases on a single-core system.

I work in game development and on a multi-core/processor system spin locks are a life saver. I deal with critical sections that usually execute in less than a nano-second, and the overhead with other locks that force a context switch is many thousands times greater than 'spinning'.

I have no problem with calling them an anti-pattern in some cases, but 'most cases'? I think saying 'most cases' is biased towards the problem you are working with and should be changed to 'some cases'. Without an explanation this could give out a negative perception towards spin locks, that in my industry is a very positive pattern in 'most cases'. --203.122.208.21 (talk) 05:28, 6 July 2011 (UTC)

Proposed merge with Critical section

Critical sections are defined as those parts of a program that require mutual exclusion. I think it makes more sense to have one article about both concepts. QVVERTYVS (hm?) 08:51, 25 May 2015 (UTC)

Yeah, I agree. I don't see any reason to have them separated.--FutureTrillionaire (talk) 01:05, 23 September 2015 (UTC)

Then again, mutex is only one of the three requirements for a solution to the critical section problem. The other two are progress and bounded waiting.[1] --FutureTrillionaire (talk) 01:33, 23 September 2015 (UTC)

That's a good point. I'll remove the {{merge}} tags for now; I guess the critical section article needs a thorough rewrite before we decide to merge or not. QVVERTYVS (hm?) 07:51, 23 September 2015 (UTC)