我们可以在单线程程序中有竞争条件吗？

Question

你可以在这里找到关于什么是竞争条件的非常好的解释.

我最近看到很多人对竞争条件和线程做出令人困惑的陈述.

我了解到竞争条件只能在线程之间发生.但我看到的代码看起来像竞争条件,在事件和基于异步的语言中,即使程序是单线程,如在Node.js,GTK +等.

我们可以在一个线程程序中遇到竞争条件吗？

Answer 1

所有示例都是一种非常接近Javascript的虚构语言.

短:

1. 竞争条件只能在两个或多个线程之间发生.我们不能在单个线程进程中具有竞争条件(例如,在单个线程中,非I/O执行程序).

2. 但在许多情况下,单个线程程序可以:

   1. 给出类似于竞争条件的情况,例如在具有事件循环的基于事件的程序中,但不是真实的竞争条件

   2. 触发其他线程之间或与其他线程的竞争条件,例如:

      1. 其他程序,如客户
      2. 库线程或服务器

I)竞争条件只能在两个或多个线程之间发生

只有当两个或多个线程尝试访问共享资源而不知道其他线程的未知指令同时修改共享资源时,才会发生竞争条件.这给出了未确定的结果.(这非常重要.)

单个线程进程只不过是一系列已知指令,因此即使指令的执行顺序在代码中不易读取,也会产生确定的结果.

II)但我们并不安全

II.1)与种族条件相似的情况

许多编程语言通过事件或信号实现异步编程功能,由主循环或事件循环处理,检查事件队列并触发侦听器.这方面的例子是Javascript,libuevent,reactPHP,GNOME GLib ......有时,我们可以找到似乎是竞争条件的情况,但事实并非如此.

调用事件循环的方式始终是已知的,因此即使指令的执行顺序不易读取(或者如果我们不知道库也无法读取),也会确定结果.

例:

setTimeout(
  function() { console.log("EVENT LOOP CALLED"); },
  1
); // We want to print EVENT LOOP CALLED after 1 milliseconds

var now = new Date();
while(new Date() - now < 10) //We do something during 10 milliseconds

console.log("EVENT LOOP NOT CALLED");

在Javascript输出中总是(你可以在node.js中测试):

EVENT LOOP NOT CALLED
EVENT LOOP CALLED

因为,当堆栈为空(所有函数都已返回)时,将调用事件循环.

请注意,这只是一个示例,并且在以不同方式实现事件的语言中,结果可能不同,但仍然由实现决定.

II.2)其他线程之间的竞争条件,例如:

II.2.i)与客户等其他计划

如果其他进程正在请求我们的进程,我们的程序不以原子方式处理请求,并且我们的进程在请求之间共享一些资源,则客户端之间可能存在竞争条件.

例:

var step;
on('requestOpen')(
  function() {
    step = 0;
  }
);

on('requestData')(
  function() {
    step = step + 1;
  }
);

on('requestEnd')(
  function() {
    step = step +1; //step should be 2 after that
    sendResponse(step);
  }
);

在这里,我们有一个经典的竞赛条件设置.如果请求在另一个结束之前打开,step则将重置为0.如果requestData在requestEnd两个并发请求之前触发了两个事件,则步骤将达到3. 但这是因为我们将事件序列视为未确定.我们期望程序的结果大部分时间未确定,输入未确定.

实际上,如果我们的程序是单线程,给定一系列事件,结果仍然总是被确定.竞争条件是客户之间.

有两种方法可以理解这件事:

• 我们可以将客户视为我们程序的一部分(为什么不呢？),在这种情况下,我们的程序是多线程的.故事的结局.
• 更常见的是,我们可以认为客户不属于我们的计划.在这种情况下,他们只是输入.当我们考虑一个程序是否有确定的结果时,我们会在给出输入的情况下这样做.否则,即使是最简单的程序return input;也会产生不确定的结果.

注意 :

• 如果我们的进程以原子方式处理请求,那么就像客户端之间存在互斥锁一样,并且没有竞争条件.
• 如果我们可以识别请求并将变量附加到请求的每一步都相同的请求对象,则客户端之间没有共享资源,也没有竞争条件

II.2.ii)使用库线程

在我们的程序中,我们经常使用产生其他进程或线程的库,或者只使用其他进程执行I/O(并且I/O总是未确定).

示例:

databaseClient.sendRequest('add Me to the database');

databaseClient.sendRequest('remove Me from the database');

这可以触发异步库中的竞争条件.如果sendRequest()在将请求发送到数据库之后但在请求真正执行之前返回,则会出现这种情况.我们立即发送另一个请求,我们无法知道在评估第二个请求之前是否会执行第一个请求,因为数据库在另一个线程上工作.程序和数据库进程之间存在竞争条件.

但是,如果数据库与程序在同一个线程上(在现实生活中并不经常发生),则在处理请求之前sendRequest将无法返回.(除非请求排队,但在这种情况下,结果仍然是确定的,因为我们确切地知道如何以及何时读取队列.)

结论

简而言之,单线程程序并非免于竞争条件.但它们只能在外部程序的其他线程之间或之间发生.我们的计划结果可能未确定,因为我们的计划从其他计划收到的输入未确定.