C 语言中的临时协同程序

• 下载源代码 - 2.49 KB

引言

本文的原标题是“无线程的线程”。实际上，我早就该把它叫做“在C语言中实现简易协程”！

本文的目的是演示如何创建可以在任意点返回然后恢复执行的函数。如果你以前用过 Python 或 C#，本文中描述的机制就像是“yield”关键字。

因为一个方法可以返回中间结果并恢复执行，我们实际上可以按顺序调用两个或更多的方法，从而实现协程的效果。

关于线程的背景知识

在 Windows 操作系统中，线程是基本的执行单元，而一个执行单元是按特定顺序（或流程）运行的一组指令。一个进程是一个或多个（看似）并行执行的线程的宿主。我之所以说“看似”，是因为如果你用的是单处理器机器，那么一次只能运行一条指令；但是，如果我们 T 时刻运行属于一个线程的指令，然后在 T+1 时刻运行属于另一个线程的指令，只要切换得足够快，看起来就像两个线程在同时运行。

考虑单线程进程的情况

int main()
{
    char name[100];
    printf("Enter your name:");
    gets(name)
    printf("You entered: %s\n", name);
    return 0;
}

这个程序将从第一条指令执行到最后一条指令（因为没有分支），并且不会被中断，因为它是一个单线程进程。

现在，假设你有两个方法想“并行”运行；为此，你需要为每个方法创建一个线程，通常会发生以下情况：

int method1()
{
    printf("method1: instruction 1");
    printf("method1: instruction 2");
    printf("method1: instruction 3");
    printf("method1: instruction 4");
    return 0;
}

int method2()
{
    printf("method2: instruction 1");
    printf("method2: instruction 2");
    printf("method2: instruction 3");
    printf("method2: instruction 4");
    printf("method2: instruction 5");
    printf("method2: instruction 6");
    return 0;
}

1. 操作系统选择一个线程开始执行：可以是线程 #1，线程 #2，或线程 #n。
2. 操作系统（根据线程优先级和其他条件）给予该线程一些时间来执行它的一部分指令。
3. 操作系统决定是时候挂起该线程，并将执行权让给另一个线程，这通常涉及：
   1. 保存当前执行上下文：操作系统需要保存当前执行线程的状态和所有变量（寄存器）。
   2. 挂起当前线程。
   3. 选择下一个要恢复的线程。
   4. 恢复该线程之前保存的状态。
   5. 一旦下一个线程的状态被恢复，操作系统就继续该线程的执行。
4. 只要有线程在运行，步骤 2 和 3 就会重复。

仅为说明起见，当我们并行运行线程 #1 和线程 #2 时，可能会显示如下输出：

method2: instruction 1
method2: instruction 2
method1: instruction 1
method2: instruction 3
method2: instruction 4
method1: instruction 2
.
.
.

注意线程 #1 和线程 #2 的执行是如何以一种交错的顺序（在两个线程之间）发生的。如果你有多个 CPU，那么你就可以实现真正的并行执行，因为每个 CPU 都可以运行一个线程，也就没有必要为了运行另一个线程而中断一个线程了。

需要注意的是，执行中断不是发生在高级代码指令层面（例如 C++ 的 cout 或 C 的 printf()）；而是发生在机器指令层面。这意味着一个 printf() 语句可以转换成许多机器指令，而 printf() 本身在完全执行完之前可能会被中断很多次。

在接下来的部分，我将使用“原子”这个词，它仅仅指我们可以中断的最小指令。在高级语言中，语句可以被认为是原子语句（或最小执行指令）。

简易协程

既然我们已经介绍了多线程的工作原理，现在是时候向你展示如何模仿这样一个系统了。

我们的主要目标是能够先运行方法 #1 中的指令 #1，然后能运行方法 #2 中的指令 #1，接着在方法 #1 中从指令 #2 处恢复执行，在两个或多个方法之间来回切换，直到所有方法执行完毕。

为了实现这一点，我们需要能够保存当前正在执行的指令编号，并且不再重复执行它。为此，我们需要设计我们自己的“程序计数器”或“指令指针”变量，它将保存我们所在的指令位置，以及一种为每条指令编号的方法（以便模拟寻址方案）。让我们看看这个：

int method1()
{
    static int pc = 1; // get's initialized once
    
    if (pc == 1)
        printf("method1: instruction 1\n");
    if (pc == 2)
        printf("method1: instruction 2\n");
    if (pc == 3)
        printf("method1: instruction 3\n");
    if (pc == 4)
        printf("method1: instruction 4\n");
    if (pc == 5)
    {
        pc = 1;
        return -1; // mark end of execution
    }   
    pc++;
    
    return 0;
}

如果你看这段代码，像这样调用 method1()：

while (method1() != -1) { }

这是非常直观的！你会注意到，通过这个简单的方法，我们成功地在每次调用该方法时运行一条指令。但我敢打赌，你觉得它在很多方面都不太实用：

1. 我们需要通过硬编码来为每条指令编号。
2. 我们无法真正地从头开始重置一个方法的执行。
3. 任何非静态变量在每次函数被调用时都会丢失其状态。
4. 等等...

我们不打算解决所有问题；相反，我们将使用 C++ 宏来解决问题（1），以自动化指令寻址，并使上面的代码更优雅一些。

现在，我们将引入一个局部变量来为我们计算指令，而不是硬编码指令编号，所以代码变成这样：

int method1()
{
    static int pc = 1; // get's initialized once
    int pci = 1; // local variable that counts the instructions
    
    if (pc == pci++) // pci is ONE
        printf("method1: instruction 1\n");
    if (pc == pci++) // pci++ is TWO
        printf("method1: instruction 2\n");
    if (pc == pci++) //
        printf("method1: instruction 3\n");
    if (pc == pci++)
        printf("method1: instruction 4\n");
        
    if (pc == pci++)
    {
        pc = 1;
        return -1; // mark end of execution
    }   
    pc++;
    
    return 0;
}

这样，就不再需要硬编码任何东西，问题就为我们解决了；我们所需要做的就是创建一些宏。

// We use it in the start of the method so that it declares
// the needed address tracking and instruction pointer tracking
#define ATOMIC_METHOD_BEGIN(name) \
  static int _counter = 1; \
  int _pci = 1;

// We use it to enclose the smallest instruction that we can interrupt
#define ATOMIC_STATEMENT(x) \
  if (_pci++ == _counter) \
  { \
    x; \
  }
  
// We use this macro to denote the end of the function.
// It returns -1 so that we know it is over with execution  
#define ATOMIC_METHOD_END \
  _counter++; \
  ATOMIC_STATEMENT(_counter = 1; return -1)

如果我们实现这些宏，代码就会变得更清晰。

int method1()
{
  ATOMIC_METHOD_BEGIN(method1);

  ATOMIC_STATEMENT(printf("m1:step1\n"));
  ATOMIC_STATEMENT(printf("m1:step2\n"));
  ATOMIC_STATEMENT(printf("m1:step3\n"));
  ATOMIC_STATEMENT(printf("m1:step4\n"));

  ATOMIC_METHOD_END;
  return 0;
}

很酷，是吧？！现在让我们创建另一个方法，然后以交错的方式运行这两个方法来模拟多线程。

int method2()
{
  ATOMIC_METHOD_BEGIN(method2);

  ATOMIC_STATEMENT(printf("m2:step1\n"));
  ATOMIC_STATEMENT(printf("m2:step2\n"));
  ATOMIC_STATEMENT(printf("m2:step3\n"));
  ATOMIC_STATEMENT(printf("m2:step4\n"));

  ATOMIC_METHOD_END;
  return 0;
}

现在，让我们来写一个小型且简单的线程执行调度器；这个算法将在每个方法中调用一条指令，直到所有方法都返回 -1。

int simple_thread_controller(int count, ...)
{
  typedef int (*atomic_method_t)(void);
  va_list args;
  int i;

  atomic_method_t *methods = new atomic_method_t[count];
  int *done = new int[count];

  for (i=0;i<count;i++)
    done[i] = 0;

  va_start(args, count);

  for (i=0;i<count;i++)
    methods[i] = va_arg(args, atomic_method_t);

  va_end(args);

  do 
  {
    int exec_something = 0;
    for (i=0;i<count;i++)
    {
      // skip done statement
      if (done[i])
        continue;

      if (methods[i]() == -1)
        done[i] = 1;
      else
        exec_something = 1;
    }
    if (!exec_something)
      break;
  } while(true);

  delete [] methods;
  delete [] done;

    return 0;
}

我们这样测试它：

int main()
{
  simple_thread_controller(2, method1, method2);
  return 0;
}

可中断的 for 循环？

这些酷炫的技巧远非模仿线程的实用解决方案，但它们确实展示了我们如何仅使用高级语言的功能来实现伪线程。那么，控制结构和重复结构怎么办呢？答案是你可以将任何东西封装在一个 ATOMIC_STATEMENT 宏中，例如：

ATOMIC_STATEMENT(for (int i=0;i<10;i++) { printf("Hello world!\n") });

然而，我并不满足于只创建原子语句，我想创建可中断的 for 循环，它们可以保存自己的状态，并在每次进入或退出方法时恢复状态。

让我们定义一下定义一个 for 循环所需的基本结构：

1. 计数器变量
2. 循环的开始/结束值
3. 计数器递增过程

所以，如果我们能够保存这些状态变量，再结合我们之前可中断的方法调用，我们就能轻松实现原子的 for 循环。

这里有一个建议的解决方案：

int test_method3()
{
  //ATOMIC_METHOD_BEGIN(method3);
  static int _counter = 1; 
  int _pci = 1;

  // DECLARE FOR
  static int _i, _i_counter_start;
  int _i_start = 1, _i_end = 4;

  // BEGIN FOR
  if (_pci++ == _counter)
  {
    _i_counter_start = _counter;
    _i = _i_start;
  }

  ATOMIC_STATEMENT(printf("i=%d\n", _i));

  // FOR END
  if (_pci++ == _counter)
  {
    if (_i < _i_end)
    {
      _counter = _i_counter_start;
      _i++;
    }
  }

  //ATOMIC_METHOD_END 
  if (_pci++ == _counter) 
  { 
    _counter = 1; 
    return -1; 
  }  
  
  _counter++;

  return 0;
}

注意我们是如何首先需要声明 for 循环的状态变量，然后用一种方式标记循环的开始，最后用一种方式判断我们是否应该再次循环以及应该跳到哪个起始点。现在，将这些代码收缩成优雅的宏，我们可以得到：

#define ATOMIC_DECLARE_FOR(v, s, e) \
  static int v, _##v##_counter_start ; \
  int _##v##_start = s, _##v##_end = e;

#define ATOMIC_FOR_BEGIN(v) if (_pci++ == _counter) \
  { \
    _##v##_counter_start = _counter; \
    v = _##v##_start; \
  } \

#define ATOMIC_FOR_END(v) \
  ATOMIC_STATEMENT( if (v < _##v##_end) { _counter = _##v##_counter_start; v++; } )

#define ATOMIC_FOR_START(v, s, e) \
    ATOMIC_DECLARE_FOR(v, s, e); ATOMIC_FOR_BEGIN(v);

代码就变成了：

int method3()
{
  ATOMIC_METHOD_BEGIN(method3);

  ATOMIC_FOR_START(i, 1, 10);
  {
      ATOMIC_STATEMENT(printf("i=%d\n", i));
  }
  ATOMIC_FOR_END(i);

  ATOMIC_METHOD_END;

  return 0;
}

你知道同样这段代码允许嵌套 for 循环吗？你会感到惊讶吗？

int method3()
{
  ATOMIC_METHOD_BEGIN(method3);

  ATOMIC_FOR_START(i, 1, 10);
  {
    ATOMIC_FOR_START(j, 1, i);
    {
      ATOMIC_STATEMENT(printf("*"));
    }
    ATOMIC_FOR_END(j);
    ATOMIC_STATEMENT(printf("\n"));
  }
  ATOMIC_FOR_END(i);

  ATOMIC_METHOD_END;

  return 0;
}

你能猜到输出会是什么吗？

如果我们通过 simple_thread_controller() 运行所有这三个方法，将会产生以下输出：

m1:step1
m2:step1
m1:step2
m2:step2
m1:step3
m2:step3
*m1:step4
m2:step4

**
***
****
*****
******
*******
********
*********
**********

如果你使用 Windows 线程 API 运行同样这些方法，你大概会得到类似的输出。

结论

本文是为教学目的和探索某一想法而写的。希望它能挑战你的思维，并让你学到一些东西。它深受 COMPEL 脚本工具的启发。对于热心的读者，我把编写更多宏和更高级的线程控制器作为练习留给你们 :)