Protothread 简介

  cheney

Protothreads 是一种 轻量的无堆栈多线程实现方式,设计用于内存严重受限的系统,例如,底层嵌入式系统或传感网络的节点等。实际上这种线程可以被称作协程.
Protothreads 是一个非常轻量化的,无堆栈式的多线程的,基于事件驱动的上下文切换系统,每个线程还不需要独立的栈空间。Protothreads 目的就是不用复杂的状态机和真正的多线程但是能实现并发执行。Protothreads 是在一个 C 函数中有选择的执行代码块。项目主页:https://github.com/gburd/pt

##主要特色:
- 没有硬件相关的代码 - Protothreads 是用纯 C 编写的。
- 不使用可能出错的函数,类似 longjmp()的没有
- 非常小的 RAM 占用量 - 每个线程只有两个字节。
- 可以独立使用,也可以和 OS 一起使用。
- 提供非阻塞的等待功能,没有用到多线程和堆栈切换。

##应用举例:
- 内存受限的系统
- 事件驱动协议栈
- 底层嵌入式系统
- 传感网络节点

下文有 示例程序可供参考,和 Protothreads API 详细描述。
Protothreads 是在 BSD 许可证协议下发布的,允许 商业和非商业 的用途。唯一需要付出的就是信任。更多的信息和新版的软件可以在 Protothreads 的主页找到: http://www.sics.se/~adam/pt/

###作者:
Protothreads 是由 Adam Dunkels «adam@sics.se» 编写,以及 Oliver Schmidt «ol.sc@web.de» 的帮助。

###使用 Protothreads
在工程中使用 Protothreads 是非常容易的:拷贝 pt.h lc.h lc-switch.h 文件到工程的头文件索引目录,用到 Protothreads 的文件全部 #include "pt.h" 。译者注,全部都是头文件,没有别的文件了。

###Protothreads
在内存受限的系统中,例如底层嵌入式系统,传统的多线程可能占用太多的资源。传统的多线程方式,会为每个线程分配独立的栈,这显然是浪费的,这些栈占用了可用内存的很大一部分。

Protothreads 相较于传统多线程解决方案最大的优势就是非常轻量:单个的 Protothreads 线程不需要独立的堆栈空间。当然,所有的 Protothreads 线程运行在同一个栈空间上,通过栈缠绕 (stack rewinding)实现上下文切换,这在内存受限的系统上是非常有利的。单个的 Protothreads 只需要两个字节的内存空间。而且,Protothreads 是用纯 C 编写的,不需要任何硬件相关的汇编代码。

###局部变量
因为 Protothreads 在上下文切换时不保存栈内容,Protothreads 块中的局部变量不一定是当前的值。也就是说,局部变量应该非常非常小心的使用,如果有任何疑问,不要在 Protothreads 段中使用局部变量。

###调度器
Protothreads 的驱动方式是不停的调用运行状态的线程函数。每次函数被调用,Protothreads 会运行到块结束或者主动退出。这样 Protothreads 的调度器就实现了。

###实现
Protothreads 是基于本地状态机的,完全使用标准 C 实现,本地状态机提供一个当前调度的详细状态,但是不提供任何调度历史和本地变量。本地状态机有很多种方式实现 :
1. 通过使用特殊的汇编机器码
2. 通过使用标准 C 结构
3. 通过使用汇编器扩展

第一种方法是通过保存和恢复进程状态,也包括栈指针,单个线程需要 16 到 32 字节的内存。具体占用多少和设计有关。

标准 C 方式实现,每个线程只需要两个字节的状态位,隐蔽的利用 C 语言的 witch() 函数,类似 Duff’s Device 方式运行。

有些编辑器有 C 扩展功能,直接实现了 Protothreads 的功能,例如, GCC 支持 label pointers 这种实现方式需要 4 个字节的 RAM 。

一个小例子

以下是一个非常简单的程序:两个线程等待对方去切换两个标志。通过这个例子能让你明白怎样初始化 Protothreads ,怎样调度他们。

/**
 * This is a very small example that shows how to use
 * protothreads. The program consists of two protothreads that wait
 * for each other to toggle a variable.
 */

/* We must always include pt.h in our protothreads code. */
#include "pt.h"

#include <stdio.h> /* For printf(). */

/* Two flags that the two protothread functions use. */
static int protothread1_flag, protothread2_flag;

/**
 * The first protothread function. A protothread function must always
 * return an integer, but must never explicitly return - returning is
 * performed inside the protothread statements.
 *
 * The protothread function is driven by the main loop further down in
 * the code.
 */
static int
protothread1(struct pt *pt)
{
  /* A protothread function must begin with PT_BEGIN() which takes a
     pointer to a struct pt. */
  PT_BEGIN(pt);

  /* We loop forever here. */
  while(1) {
    /* Wait until the other protothread has set its flag. */
    PT_WAIT_UNTIL(pt, protothread2_flag != 0);
    printf("Protothread 1 running\n");

    /* We then reset the other protothread's flag, and set our own
       flag so that the other protothread can run. */
    protothread2_flag = 0;
    protothread1_flag = 1;

    /* And we loop. */
  }

  /* All protothread functions must end with PT_END() which takes a
     pointer to a struct pt. */
  PT_END(pt);
}

/**
 * The second protothread function. This is almost the same as the
 * first one.
 */
static int
protothread2(struct pt *pt)
{
  PT_BEGIN(pt);

  while(1) {
    /* Let the other protothread run. */
    protothread2_flag = 1;

    /* Wait until the other protothread has set its flag. */
    PT_WAIT_UNTIL(pt, protothread1_flag != 0);
    printf("Protothread 2 running\n");
    
    /* We then reset the other protothread's flag. */
    protothread1_flag = 0;

    /* And we loop. */
  }
  PT_END(pt);
}

/**
 * Finally, we have the main loop. Here is where the protothreads are
 * initialized and scheduled. First, however, we define the
 * protothread state variables pt1 and pt2, which hold the state of
 * the two protothreads.
 */
static struct pt pt1, pt2;
int
main(void)
{
  /* Initialize the protothread state variables with PT_INIT(). */
  PT_INIT(&pt1);
  PT_INIT(&pt2);
  
  /*
   * Then we schedule the two protothreads by repeatedly calling their
   * protothread functions and passing a pointer to the protothread
   * state variables as arguments.
   */
  while(1) {
    protothread1(&pt1);
    protothread2(&pt2);
  }
}

第二个例子

这个例子向你展示了怎样实现一个简单的软件锁。允许你实现一个必须输入四个数字的口令才能解开的装置。

锁一直等待数字的输入,如果输入了正确的数字,锁会打开。每次输入之间有时间限制,正确的口令输入正确了,也还要校验之后没有更多的输入了才真正开锁。

/*
 * Copyright (c) 2004-2005, Swedish Institute of Computer Science.
 * All rights reserved. 
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met: 
 * 1. Redistributions of source code must retain the above copyright 
 *    notice, this list of conditions and the following disclaimer. 
 * 2. Redistributions in binary form must reproduce the above copyright 
 *    notice, this list of conditions and the following disclaimer in the 
 *    documentation and/or other materials provided with the distribution. 
 * 3. Neither the name of the Institute nor the names of its contributors 
 *    may be used to endorse or promote products derived from this software 
 *    without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 
 * SUCH DAMAGE. 
 *
 * This file is part of the protothreads library.
 *
 * Author: Adam Dunkels <adam@sics.se>
 *
 * $Id: example-codelock.c,v 1.5 2005/10/06 07:57:08 adam Exp $
 */

/*
 *
 * This example shows how to implement a simple code lock. The code
 * lock waits for key presses from a numeric keyboard and if the
 * correct code is entered, the lock is unlocked. There is a maximum
 * time of one second between each key press, and after the correct
 * code has been entered, no more keys must be pressed for 0.5 seconds
 * before the lock is opened.
 *
 * This is an example that shows two things:
 * - how to implement a code lock key input mechanism, and
 * - how to implement a sequential timed routine.
 *
 * The program consists of two protothreads, one that implements the
 * code lock reader and one that implements simulated keyboard input.
 *
 *
 */

#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h>
#include <sys/time.h>
#endif
#include <stdio.h>

#include "pt.h"

/*---------------------------------------------------------------------------*/
/*
 * The following definitions are just for the simple timer library
 * used in this example. The actual implementation of the functions
 * can be found at the end of this file.
 */
struct timer { int start, interval; };
static int  timer_expired(struct timer *t);
static void timer_set(struct timer *t, int usecs);
/*---------------------------------------------------------------------------*/
/*
 * This example uses two timers: one for the code lock protothread and
 * one for the simulated key input protothread.
 */
static struct timer codelock_timer, input_timer;
/*---------------------------------------------------------------------------*/
/*
 * This is the code that has to be entered.
 */
static const char code[4] = {'1', '4', '2', '3'};
/*---------------------------------------------------------------------------*/
/*
 * This example has two protothread and therefor has two protothread
 * control structures of type struct pt. These are initialized with
 * PT_INIT() in the main() function below.
 */
static struct pt codelock_pt, input_pt;
/*---------------------------------------------------------------------------*/
/*
 * The following code implements a simple key input. Input is made
 * with the press_key() function, and the function key_pressed()
 * checks if a key has been pressed. The variable "key" holds the
 * latest key that was pressed. The variable "key_pressed_flag" is set
 * when a key is pressed and cleared when a key press is checked.
 */
static char key, key_pressed_flag;

static void
press_key(char k)
{
  printf("--- Key '%c' pressed\n", k);
  key = k;
  key_pressed_flag = 1;
}

static int
key_pressed(void)
{
  if(key_pressed_flag != 0) {
    key_pressed_flag = 0;
    return 1;
  }
  return 0;
}
/*---------------------------------------------------------------------------*/
/*
 * Declaration of the protothread function implementing the code lock
 * logic. The protothread function is declared using the PT_THREAD()
 * macro. The function is declared with the "static" keyword since it
 * is local to this file. The name of the function is codelock_thread
 * and it takes one argument, pt, of the type struct pt.
 *
 */
static
PT_THREAD(codelock_thread(struct pt *pt))
{
  /* This is a local variable that holds the number of keys that have
   * been pressed. Note that it is declared with the "static" keyword
   * to make sure that the variable is *not* allocated on the stack.
   */
  static int keys;

  /*
   * Declare the beginning of the protothread.
   */
  PT_BEGIN(pt);

  /*
   * We'll let the protothread loop until the protothread is
   * expliticly exited with PT_EXIT().
   */
  while(1) {

    /*
     * We'll be reading key presses until we get the right amount of
     * correct keys.
     */ 
    for(keys = 0; keys < sizeof(code); ++keys) {

      /*
       * If we haven't gotten any keypresses, we'll simply wait for one.
       */
      if(keys == 0) {

        /*
         * The PT_WAIT_UNTIL() function will block until the condition
         * key_pressed() is true.
         */
        PT_WAIT_UNTIL(pt, key_pressed());
      } else {
        
        /*
         * If the "key" variable was larger than zero, we have already
         * gotten at least one correct key press. If so, we'll not
         * only wait for the next key, but we'll also set a timer that
         * expires in one second. This gives the person pressing the
         * keys one second to press the next key in the code.
         */
        timer_set(&codelock_timer, 1000);

        /*
         * The following statement shows how complex blocking
         * conditions can be easily expressed with protothreads and
         * the PT_WAIT_UNTIL() function.
         */
        PT_WAIT_UNTIL(pt, key_pressed() || timer_expired(&codelock_timer));

        /*
         * If the timer expired, we should break out of the for() loop
         * and start reading keys from the beginning of the while(1)
         * loop instead.
         */
        if(timer_expired(&codelock_timer)) {
          printf("Code lock timer expired.\n");
          
          /*
           * Break out from the for() loop and start from the
           * beginning of the while(1) loop.
           */
          break;
        }
      }

      /*
       * Check if the pressed key was correct.
       */
      if(key != code[keys]) {
        printf("Incorrect key '%c' found\n", key);
        /*
         * Break out of the for() loop since the key was incorrect.
         */
        break;
      } else {
        printf("Correct key '%c' found\n", key);
      }
    }

    /*
     * Check if we have gotten all keys.
     */
    if(keys == sizeof(code)) {
      printf("Correct code entered, waiting for 500 ms before unlocking.\n");

      /*
       * Ok, we got the correct code. But to make sure that the code
       * was not just a fluke of luck by an intruder, but the correct
       * code entered by a person that knows the correct code, we'll
       * wait for half a second before opening the lock. If another
       * key is pressed during this time, we'll assume that it was a
       * fluke of luck that the correct code was entered the first
       * time.
       */
      timer_set(&codelock_timer, 500);      
      PT_WAIT_UNTIL(pt, key_pressed() || timer_expired(&codelock_timer));

      /*
       * If we continued from the PT_WAIT_UNTIL() statement without
       * the timer expired, we don't open the lock.
       */
      if(!timer_expired(&codelock_timer)) {
        printf("Key pressed during final wait, code lock locked again.\n");
      } else {

        /*
         * If the timer expired, we'll open the lock and exit from the
         * protothread.
         */
        printf("Code lock unlocked.\n");
        PT_EXIT(pt);
      }
    }
  }

  /*
   * Finally, we'll mark the end of the protothread.
   */
  PT_END(pt);
}
/*---------------------------------------------------------------------------*/
/*
 * This is the second protothread in this example. It implements a
 * simulated user pressing the keys. This illustrates how a linear
 * sequence of timed instructions can be implemented with
 * protothreads.
 */
static
PT_THREAD(input_thread(struct pt *pt))
{
  PT_BEGIN(pt);

  printf("Waiting 1 second before entering first key.\n");
  
  timer_set(&input_timer, 1000);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));

  press_key('1');
  
  timer_set(&input_timer, 100);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('2');

  timer_set(&input_timer, 100);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('3');

  timer_set(&input_timer, 2000);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('1');

  timer_set(&input_timer, 200);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('4');

  timer_set(&input_timer, 200);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('2');
  
  timer_set(&input_timer, 2000);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('3');

  timer_set(&input_timer, 200);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('1');

  timer_set(&input_timer, 200);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('4');

  timer_set(&input_timer, 200);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('2');
  
  timer_set(&input_timer, 100);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('3');

  timer_set(&input_timer, 100);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('4');

  timer_set(&input_timer, 1500);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('1');

  timer_set(&input_timer, 300);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('4');

  timer_set(&input_timer, 400);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('2');

  timer_set(&input_timer, 500);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  press_key('3');

  timer_set(&input_timer, 2000);
  PT_WAIT_UNTIL(pt, timer_expired(&input_timer));
  
  PT_END(pt);
}
/*---------------------------------------------------------------------------*/
/*
 * This is the main function. It initializes the two protothread
 * control structures and schedules the two protothreads. The main
 * function returns when the protothread the runs the code lock exits.
 */
int
main(void)
{
  /*
   * Initialize the two protothread control structures.
   */
  PT_INIT(&input_pt);
  PT_INIT(&codelock_pt);

  /*
   * Schedule the two protothreads until the codelock_thread() exits.
   */
  while(PT_SCHEDULE(codelock_thread(&codelock_pt))) {
    PT_SCHEDULE(input_thread(&input_pt));
    
    /*
     * When running this example on a multitasking system, we must
     * give other processes a chance to run too and therefore we call
     * usleep() resp. Sleep() here. On a dedicated embedded system,
     * we usually do not need to do this.
     */
#ifdef _WIN32
    Sleep(0);
#else
    usleep(10);
#endif
  }

  return 0;
}
/*---------------------------------------------------------------------------*/
/*
 * Finally, the implementation of the simple timer library follows.
 */
#ifdef _WIN32

static int clock_time(void)
{ return (int)GetTickCount(); }

#else /* _WIN32 */

static int clock_time(void)
{
  struct timeval tv;
  struct timezone tz;   
  gettimeofday(&tv, &tz); 
  return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

#endif /* _WIN32 */

static int timer_expired(struct timer *t)
{ return (int)(clock_time() - t->start) >= (int)t->interval; }

static void timer_set(struct timer *t, int interval)
{ t->interval = interval; t->start = clock_time(); }
/*---------------------------------------------------------------------------*/

##第三个例子
接下来的例子展示了如可使用 信号量 来实现一个缓冲区。这个例子使用了三个线程: 一个生产者,产生元素,一个消费者,消耗元素,和一个驱动线程,调度生产者和消费者。

不需要实现互斥块的功能,因为 Protothread 隐含了只有一个线程能拿到执行权的线程——所有的线程都是不能被抢占的。

/*
 * Copyright (c) 2004-2005, Swedish Institute of Computer Science.
 * All rights reserved. 
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met: 
 * 1. Redistributions of source code must retain the above copyright 
 *    notice, this list of conditions and the following disclaimer. 
 * 2. Redistributions in binary form must reproduce the above copyright 
 *    notice, this list of conditions and the following disclaimer in the 
 *    documentation and/or other materials provided with the distribution. 
 * 3. Neither the name of the Institute nor the names of its contributors 
 *    may be used to endorse or promote products derived from this software 
 *    without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 
 * SUCH DAMAGE. 
 *
 * This file is part of the protothreads library.
 *
 * Author: Adam Dunkels <adam@sics.se>
 *
 * $Id: example-buffer.c,v 1.5 2005/10/07 05:21:33 adam Exp $
 */

#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h>
#endif
#include <stdio.h>

#include "pt-sem.h"
 
#define NUM_ITEMS 32
#define BUFSIZE 8

static int buffer[BUFSIZE];
static int bufptr;

static void
add_to_buffer(int item)
{
  printf("Item %d added to buffer at place %d\n", item, bufptr);  
  buffer[bufptr] = item;
  bufptr = (bufptr + 1) % BUFSIZE;
}
static int
get_from_buffer(void)
{
  int item;
  item = buffer[bufptr];
  printf("Item %d retrieved from buffer at place %d\n",
         item, bufptr);
  bufptr = (bufptr + 1) % BUFSIZE;
  return item;
}

static int
produce_item(void)
{
  static int item = 0;
  printf("Item %d produced\n", item);
  return item++;
}

static void
consume_item(int item)
{
  printf("Item %d consumed\n", item);
}

static struct pt_sem full, empty;
 
static 
PT_THREAD(producer(struct pt *pt))
{
  static int produced;
  
  PT_BEGIN(pt);
  
  for(produced = 0; produced < NUM_ITEMS; ++produced) {
  
    PT_SEM_WAIT(pt, &full);
    
    add_to_buffer(produce_item());
    
    PT_SEM_SIGNAL(pt, &empty);
  }

  PT_END(pt);
}
 
static 
PT_THREAD(consumer(struct pt *pt))
{
  static int consumed;
  
  PT_BEGIN(pt);
 
  for(consumed = 0; consumed < NUM_ITEMS; ++consumed) {
    
    PT_SEM_WAIT(pt, &empty);
    
    consume_item(get_from_buffer());    
    
    PT_SEM_SIGNAL(pt, &full);
  }
 
  PT_END(pt);
}
 
static 
PT_THREAD(driver_thread(struct pt *pt))
{
  static struct pt pt_producer, pt_consumer;
 
  PT_BEGIN(pt);
  
  PT_SEM_INIT(&empty, 0);
  PT_SEM_INIT(&full, BUFSIZE);
 
  PT_INIT(&pt_producer);
  PT_INIT(&pt_consumer);
 
  PT_WAIT_THREAD(pt, producer(&pt_producer) &
                     consumer(&pt_consumer));
 
  PT_END(pt);
}


int
main(void)
{
  struct pt driver_pt;

  PT_INIT(&driver_pt);

  while(PT_SCHEDULE(driver_thread(&driver_pt))) {

    /*
     * When running this example on a multitasking system, we must
     * give other processes a chance to run too and therefore we call
     * usleep() resp. Sleep() here. On a dedicated embedded system,
     * we usually do not need to do this.
     */
#ifdef _WIN32
    Sleep(0);
#else
    usleep(10);
#endif
  }
  return 0;
}