竞态条件 race condition data race

竞态条件 race condition

Race condition - Wikipedia https://en.wikipedia.org/wiki/Race_condition

A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of the possible behaviors is undesirable.

The term race condition was already in use by 1954, for example in David A. Huffman's doctoral thesis "The synthesis of sequential switching circuits".^[1]

Race conditions can occur especially in logic circuits, multithreaded or distributed software programs.

Software[edit]

A race condition arises in software when a computer program, to operate properly, depends on the sequence or timing of the program's processes or threads. Critical race conditions cause invalid execution and software bugs. Critical race conditions often happen when the processes or threads depend on some shared state. Operations upon shared states are done in critical sections that must be mutually exclusive. Failure to obey this rule can corrupt the shared state.

A data race is a type of race condition. Data races are important parts of various formal memory models. The memory model defined in the C11 and C++11 standards specify that a C or C++ program containing a data race has undefined behavior.^[3]^[4]

A race condition can be difficult to reproduce and debug because the end result is nondeterministic and depends on the relative timing between interfering threads. Problems of this nature can therefore disappear when running in debug mode, adding extra logging, or attaching a debugger. Bugs that disappear like this during debugging attempts are often referred to as a "Heisenbug". It is therefore better to avoid race conditions by careful software design.

Example[edit]

Assume that two threads each increment the value of a global integer variable by 1. Ideally, the following sequence of operations would take place:

Thread 1	Thread 2		Integer value
			0
read value		←	0
increase value			0
write back		→	1
	read value	←	1
	increase value		1
	write back	→	2

In the case shown above, the final value is 2, as expected. However, if the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong. The alternative sequence of operations below demonstrates this scenario:

Thread 1	Thread 2		Integer value
			0
read value		←	0
	read value	←	0
increase value			0
	increase value		0
write back		→	1
	write back	→	1

In this case, the final value is 1 instead of the correct result of 2. This occurs because here the increment operations are not mutually exclusive. Mutually exclusive operations are those that cannot be interrupted while accessing some resource such as a memory location.

Data race[edit]

Not all regard data races as a subset of race conditions.^[5] The precise definition of data race is specific to the formal concurrency model being used, but typically it refers to a situation where a memory operation in one thread could potentially attempt to access a memory location at the same time that a memory operation in another thread is writing to that memory location, in a context where this is dangerous. This implies that a data race is different from a race condition as it is possible to have nondeterminism due to timing even in a program without data races, for example, in a program in which all memory accesses use only atomic operations.

This can be dangerous because on many platforms, if two threads write to a memory location at the same time, it may be possible for the memory location to end up holding a value that is some arbitrary and meaningless combination of the bits representing the values that each thread was attempting to write; this could result in memory corruption if the resulting value is one that neither thread attempted to write (sometimes this is called a 'torn write'). Similarly, if one thread reads from a location while another thread is writing to it, it may be possible for the read to return a value that is some arbitrary and meaningless combination of the bits representing the value that the memory location held before the write, and of the bits representing the value being written.

On many platforms, special memory operations are provided for simultaneous access; in such cases, typically simultaneous access using these special operations is safe, but simultaneous access using other memory operations is dangerous. Sometimes such special operations (which are safe for simultaneous access) are called atomic or synchronization operations, whereas the ordinary operations (which are unsafe for simultaneous access) are called data operations. This is probably why the term is data race; on many platforms, where there is a race condition involving only synchronization operations, such a race may be nondeterministic but otherwise safe; but a data race could lead to memory corruption or undefined behavior.

Example definitions of data races in particular concurrency models[edit]

The precise definition of data race differs across formal concurrency models. This matters because concurrent behavior is often non-intuitive and so formal reasoning is sometimes applied.

The C++ standard, in draft N4296 (2014-11-19)], defines data race as follows in section 1.10.23 (page 14)^[6]

Two actions are potentially concurrent if

they are performed by different threads, or

they are unsequenced, and at least one is performed by a signal handler.

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below [omitted]. Any such data race results in undefined behavior.

The parts of this definition relating to signal handlers are idiosyncratic to C++ and are not typical of definitions of data race.

The paper Detecting Data Races on Weak Memory Systems^[7] provides a different definition:

"two memory operations conflict if they access the same location and at least one of them is a write operation... "Two memory operations, x and y, in a sequentially consistent execution form a race 〈x,y〉, iff x and y conflict, and they are not ordered by the hb1 relation of the execution. The race 〈x,y〉, is a data race iff at least one of x or y is a data operation.

Here we have two memory operations accessing the same location, one of which is a write.

The hb1 relation is defined elsewhere in the paper, and is an example of a typical "happens-before" relation; intuitively, if we can prove that we are in a situation where one memory operation X is guaranteed to be executed to completion before another memory operation Y begins, then we say that "X happens-before Y". If neither "X happens-before Y" nor "Y happens-before X", then we say that X and Y are "not ordered by the hb1 relation". So, the clause "...and they are not ordered by the hb1 relation of the execution" can be intuitively translated as "...and X and Y are potentially concurrent".

The paper considers dangerous only those situations in which at least one of the memory operations is a "data operation"; in other parts of this paper, the paper also defines a class of "synchronization operations" which are safe for potentially simultaneous use, in contrast to "data operations".

The Java Language Specification^[8] provides a different definition:

Two accesses to (reads of or writes to) the same variable are said to be conflicting if at least one of the accesses is a write...When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race...a data race cannot cause incorrect behavior such as returning the wrong length for an array.

A critical difference between the C++ approach and the Java approach is that in C++, a data race is undefined behavior, whereas in Java, a data race merely affects "inter-thread actions".^[8] This means that in C++, an attempt to execute a program containing a data race could (while still adhering to the spec) crash or could exhibit insecure or bizarre behavior, whereas in Java, an attempt to execute a program containing a data race may produce undesired concurrency behavior but is otherwise (assuming that the implementation adheres to the spec) safe.

https://zh.wikipedia.org/wiki/競爭危害

竞争冒险（race hazard）又名竞态条件、竞争条件（race condition），它旨在描述一个系统或者进程的输出依赖于不受控制的事件出现顺序或者出现时机。此词源自于两个信号试着彼此竞争，来影响谁先输出。

举例来说，如果计算机中的两个进程同时试图修改一个共享内存的内容，在没有并发控制的情况下，最后的结果依赖于两个进程的执行顺序与时机。而且如果发生了并发访问冲突，则最后的结果是不正确的。

竞争冒险常见于不良设计的电子系统，尤其是逻辑电路。但它们在软件中也比较常见，尤其是有采用多线程技术的软件。

实例

计算机存储器或者磁盘设备里，如果同时发出大量数据指令的时候，竞争冒险可能发生。计算机尝试覆盖相同或者旧的数据，而此时旧的数据仍在被读取。结果可能是下面的一个或者多个情况：机器死机、出现非法操作并退出程序、错误的读取旧数据、或者错误的写入新数据。
网络上，竞争冒险会在：多用户同时试图访问同一个可用消息沟道时，产生。在系统同意访问前没有计算机能得到消息沟道被占用的提醒。统计上说这种情况通常发生在极端长延迟时间的网络里，譬如地球同步卫星。解决之道是用户预先产生优先级列表。然而黑客可以利用这种竞争冒险获取非法访问网络的权利。
数字电路，由于逻辑部件输出对输入有一个响应延迟，因此可能在输出上出现一个不希望有的脉冲信号。被称为Electronics glitch。使用卡诺图以发现并消除这类问题。

1.2 What is a Data Race? (Sun Studio 12: Thread Analyzer User's Guide) https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.html

1.2 What is a Data Race?

The Thread Analyzer detects data-races that occur during the execution of a multi-threaded process. A data race occurs when:

two or more threads in a single process access the same memory location concurrently, and
at least one of the accesses is for writing, and
the threads are not using any exclusive locks to control their accesses to that memory.

When these three conditions hold, the order of accesses is non-deterministic, and the computation may give different results from run to run depending on that order. Some data-races may be benign (for example, when the memory access is used for a busy-wait), but many data-races are bugs in the program.

The Thread Analyzer works on a multi-threaded program written using the POSIX thread API, Solaris thread API, OpenMP, Sun parallel directives, Cray parallel directives, or a mix of the above.

1.3 What is a Deadlock? (Sun Studio 12: Thread Analyzer User's Guide) https://docs.oracle.com/cd/E19205-01/820-0619/geokj/index.html

1.2 What is a Data Race?

The Thread Analyzer detects data-races that occur during the execution of a multi-threaded process. A data race occurs when:

two or more threads in a single process access the same memory location concurrently, and
at least one of the accesses is for writing, and
the threads are not using any exclusive locks to control their accesses to that memory.

The Thread Analyzer works on a multi-threaded program written using the POSIX thread API, Solaris thread API, OpenMP, Sun parallel directives, Cray parallel directives, or a mix of the above.