Mutex

The term mutual exclusion or mutex ( abbr. For English mut ual ex clusion ) refers to a group of processes with which the problem of the critical section is released. Mutex procedures prevent concurrent processes or threads from changing uncoordinated data structures used together at the same time or at different times, as a result of which the data structures can get into an inconsistent state, even if the actions of each individual process or thread in themselves maintain consistency. Mutex procedures coordinate the timing of concurrent processes / threads in such a way that other processes / threads are excluded from the execution of critical sections if a process / thread is already in the critical section (the data structure changes).

Mutex methods are assigned to the class of methods for process or thread synchronization and are of central importance for any system of concurrent processes / threads with modifying access to shared data or data structures, e.g. B. also for client / server systems with independent client processes or threads that access a database server at the same time or at different times.

Demarcation

The term mutex is not defined uniformly. Often it is used differently in theoretical computer science than in specific programming languages. This section tries to give the most common definition of the terms.

• Mutex :
  • The procedure for ensuring mutual exclusion (see article introduction).
  • An object (or data structure) that enforces mutual exclusion. Most programming languages ​​that support concurrent processes know one. It is by no means identical to a binary semaphore , since semaphores can be released by other activity carriers.

• Semaphore (s) in computer science is a data structure for controlling exclusive access to data, with or without a connection to a task scheduler. The general meaning of semaphore goes back to the optical telegraphy with signal masts ( English semaphore telegraph ).
• Monitor is a mechanism for controlling exclusive access to data in connection with the scheduler of a real-time operating system (RTOS) or a language that supports multithreaded processing, e.g. B. in Java . Conceptually, the semaphore and monitor technology are related.
• Lock mechanisms are used toblockaccess from other parties while processing is in progress, for example file locks when writing to a file or locking a specific revision in a version management system .
• A critical section ( critical section or critical region ) is that part of the executable code in which there is undisturbed access to data due to the mutex. A critical section must not be interrupted

• from another thread that wants to access the same mutex protected data,
• from another thread, which would possibly extend the mutex access inadmissibly because it interrupts the accessing thread for a long time.

Definitions of terms

• Polling is a mechanism for continuous queries in computer science, for example, whether a lock ( lock ) is still active or if a semaphore is free. Polling is an alternative to control via a scheduler.
• Active waiting (eng. Busy-waiting ) is a continuous polling for a mutex release. Polling does not need to (and should not!) Take place unnecessarily often. It makes sense to combine active waiting with a thread delivery to a scheduler control for a defined period of time with a “sleep” call (to deliver computing time or to save power).
• Spinlock is the combination of lock and polling.
• Process synchronization is the general term for the coordination of the timing of several concurrent processes or threads . It does not matter whether it is a matter of threads in a program, programs on a computer or processes in a distributed system . With regard to Mutex, the processes only need to be synchronized for the short period of mutex access and only to the extent that they do not access at the same time. A general process synchronization is not connected with this.
• Interprocess communication is the collective term for methods for data exchange between processes and for achieving process synchronization. A mutex itself is not a means of interprocess communication, but rather the exchange of data, which may be protected by a mutex, can be such a means.

Mechanisms for realizing a mutex

Semaphore or monitor

In order to achieve mutual exclusion, the data object is assigned a control element that must be observed by a process (or a thread ) whenever it executes program code that accesses this data object (so-called critical sections ). The effect is that the process has to wait if someone else is currently accessing this data. It must be prevented that

• Processing begins as soon as another thread is processing or just reading the data consistently,
• processing is interrupted and another thread is doing competing processing, which can lead to inconsistency as well
• Another process is using the inconsistent data during processing.

A semaphore indicates that the thread is starting processing. Before this, it is tested whether the semaphore is not occupied by another thread. In this case the thread has to wait. It can either query the semaphore with cyclical polling until it is free, or the thread stores its own thread identification on the semaphore in its queue and goes into the waiting state.

If the semaphore is free, it is used. Other threads that now want to access are prevented from doing so as described above. The processing of the data must be completed in a limited period of time so that there is no deadlock in the entire system.

After finishing the data processing, the semaphore must be released again. In a real-time operating system, the release is supported by its scheduler. It is tested whether other threads are waiting for this semaphore, these threads are set to "ready" ( readyToRun ) and processed according to their priority.

The Java programming language has a standard solution for this problem that is an integral part of the programming language. This is shown in the following example:

 synchronized(obj)
 {
   int a = obj.w;
   a = a + 1;
   obj.w = a;
 }

The processing of the data is noted in the synchronizedassociated program block in {}. This is a critical section . The concurrent access is prevented by means of the object objthat also contains the relevant data (here the variable w). Any other thread that also synchronized(obj)calls has to wait until this program section has ended. A semaphore with a connection to the scheduler of the Java virtual machine , which in turn depends on the scheduler of the RTOS according to its specific implementation , is attached to the object obj, more precisely to its base class, which is called in Java . In the original Java documentation, the term monitor is used for this concept . Object

Another variation in Java is to mark a method as synchronized:

 synchronized void increment(int w)
 {
   int a = w;
   a = a + 1;
   w = a;
 }

Here the entire method is marked as a critical section. increment(w)shall be a method of the class that takes the parameter w. increment(w)You don't need to do anything else at the point in the program that is called.

Lock

A lock mechanism is similar to the monitor or semaphore mechanism, but is especially designed for access by multiple processes in distributed systems. The concept can be refined using read-write locks so that processes that only read data do not interfere with one another - this is particularly common for accessing files and databases .

Active and passive waiting

If a mutex is pronounced, then another process or thread is not allowed to access it. The other process / thread can then

1. do nothing more than wait for the access that is under Mutex, or
2. perform other tasks and wait for access, or
3. deny access.

In the first case, the other thread can wait passively. Control of the waiting thread can be transferred to a scheduler; the thread is only continued again when the mutex is free. However, this assumes that the thread that occupies the mutex is also integrated in the same scheduler, and that the scheduler recognizes the mutex and its release. This is usually the case with several threads of a process, but it can also be implemented with several processes under a common operating system kernel.

In the second case, the other thread may not be allowed to wait passively, otherwise the other tasks will not be carried out. Example: A high-priority thread has to execute a regulation cyclically. In addition, it has to transfer measured values ​​to another thread, which this thread reads out under the protection of a mutex (due to data consistency). If the reading thread pronounces the mutex, then the regulation thread may not store the values, but must carry out its regulation tasks. As a result, he has to query the mutex in the following cycle and store the values ​​later. The second case always leads to a cyclical query (polling) .

Polling may also be necessary in the first case, precisely when the two processes are not connected via a common scheduler. In the case of a lock, this leads to the need to use the spin lock . In general, there is talk of active waiting (busy waiting) , which is a form of polling. A highly cyclical query of the mutex control element should be avoided during active waiting. As a rule, a call is a useful way. wait(millisekunden)

The third case, discarding access, is usually used if a later value would overwrite the original entry - knowing this future status, the currently non-writable value can then be discarded immediately.

Support of Mutex by programming languages ​​and operating systems

Some programming languages support Mutex as part of the language itself, particularly Concurrent Pascal , Ada , Java, or C # . For almost all languages ​​there are libraries that implement a mutex system (e.g. pthreads in C), and this is often even part of the standard API or the runtime environment .

A good implementation of Mutex is only possible with an operating system whose scheduler supports such concepts. On other systems (especially real-time systems ), spin locks have to be used, which considerably impair the system performance through busy waiting .

It is generally sufficient if an operating system or a runtime environment offers a subset of mutex, semaphore, monitor, lock or critical section. Any of these principles can be modeled by any other from the group .

Testing in applications with mutex code parts (in multithreaded applications)

The three classic test options for software

• Module test: Test of an algorithm with defined input conditions, often as a single-step test of instructions, in order to cover as many applications as possible,
• Code review: Review of the software according to formal criteria and with a critical eye,
• Practical test: testing the software under real conditions

are just as applicable to multithreaded applications as to simpler applications. But there are some special features to consider:

Practical test

Multithreading errors may not occur at all under normal operating conditions. A statement test error-free, i.e. software error-free, is inconclusive. Errors may occur if conditions are changed that do not seem to have anything to do with the relevant part of the program. The causes are timing shifts, changes in the use of resources or the like. Only then is the existing error stimulated. You have to carry out a practical test under a large number of changing operating conditions in order to get a reliable test result.

Module test

The classic module test is supposed to check the correctness of an algorithm. This is typically a single-threaded affair. You can, however, incorporate targeted multithread test conditions into a module test, in which a thread change is forced by additional commands at known critical points. The other thread is then to be programmed, for example, in such a way that the same resource is accessed in a targeted manner. This enables the module test to test whether the programmed mutex algorithm works.

In C or C ++, macros or compiler switches can be used to leave these code parts in the source code without them leading to a loss of runtime efficiency when compiling the end application:

  EnterCriticalSection(semaphore)
  {
    myValues->x = 5;
    TEST_Threadswitch(25);
    ...
  }

The macro

TEST_Threadswitch()

can be defined empty in the production code. It can contain any commands for testing.

In other programming languages ​​such as Java, in which there is no macro option, such thread change stimuli can be implemented in a test environment by calling interface methods.In practice, these interface methods can then be replaced with empty implementations or, as in the example, the pointer zero:

  synchronized(myValues)
  {
    if(testThreadswitch != null){ testThreadswitch.doit(25); }
    ...
  }

The test code should not remain in the productive software. This is to be evaluated in a similar way to leaving test adapter plugs on hardware assemblies: It depends on the number of pieces. In the case of large quantities, one can and must afford an extensive type test so that the end product can be manufactured without test adaptations. However, if the number of pieces is lower and reworking cannot be ruled out, then test instructions should remain in it. This allows you to repeat the tests over and over again if necessary.

Code review

A code review can be used to systematically check whether all data accesses to a certain instance or a class or a structure type are provided with a mutex. It may have been forgotten at one point. This is not noticeable in the module test because it was not considered at all. In the practical test, the critical case does not initially arise because it is a rather hidden condition. The systematic sifting through of all accesses to the data in question brings the problem to light. Certain auxiliary programs can help with this.

In C or C ++ something like this can be achieved with additional programs like lint . In more modern programming languages ​​such as Java, properties of code analysis are or are more likely to be language components. In Java, you can forget a synchronized keyword to access data. A method that is declared as synchronized is, however, automatically thread-safe with regard to its own class: All access to data of the own instance takes place under a mutex. However, this is not a panacea, as synchronized methods can block too much. The entire method may not need to run under a mutex.

Problems related to Mutex

The mutual exclusion involves the risk of deadlocks (deadlocks) in which none of the processes can proceed more because one process is blocking others. A vivid example of this is the philosopher problem . Such deadlocks can be avoided by suitable planning of the program sequence, for example according to the Peterson algorithm or the Dekker algorithm .

Another problem is the mostly inconsistent implementation or definition of the behavior in the event of multiple (recursive) calls to a mutex lock from a thread. Some systems use a counter here to handle this behavior. Other systems block the thread (similar to a semaphore), return an error message or the behavior can be adjusted.

In addition, there is also the problem that with at least three threads with different priorities, the thread with medium priority can block the thread with the highest priority if the thread with the lowest priority is currently accessing a resource. This problem is called priority inversion .

See also

• Non-sequential programming
• Transaction system

literature

• Rainer Oechsle: Parallel programming with Java threads . 1st edition. Fachbuchverlag Leipzig, 2001, ISBN 978-3-446-21780-5 , p. 176 .
• Andrew S. Tanenbaum: Modern Operating Systems (=  Pearson Studies - IT ). 3rd updated edition. Addison-Wesley, 2009, ISBN 978-3-8273-7342-7 , pp. 1248 (English: Modern Operating Systems .).
• James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986 . In: Distrib. Comput. tape 16 , no. 2-3 . Springer-Verlag, September 2003, ISSN  0178-2770 , p. 75-110 , doi : 10.1007 / s00446-003-0088-6 .
• M. Raynal, D. Beeson: Algorithms for mutual exclusion . MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3 .

Web links

Wiktionary: Mutex  - explanations of meanings, word origins, synonyms, translations