精华内容
下载资源
问答
  • 用于并行计算的多线程数据结构

    千次阅读 2014-07-05 13:14:15
    用于并行计算的多线程数据结构,第 1 部分: 设计并发数据结构 大家都在谈论并行计算;这个主题非常热门。本文是讨论多线程结构的两篇系列文章的第一篇,介绍如何使用 POSIX 库在多线程环境中设计并发数据...

    用于并行计算的多线程数据结构,第 1 部分: 设计并发数据结构

    大家都在谈论并行计算;这个主题非常热门。本文是讨论多线程结构的两篇系列文章的第一篇,介绍如何使用 POSIX 库在多线程环境中设计并发数据结构。

    Arpan Sen, 独立作家

    2011 年 7 月 07 日

    • +内容

    简介

    现在,您的计算机有四个 CPU 核;并行计算 是最时髦的主题,您急于掌握这种技术。但是,并行编程不只是在随便什么函数和方法中使用互斥锁和条件变量。C++ 开发人员必须掌握的关键技能之一是设计并发数据结构。本文是两篇系列文章的第一篇,讨论如何在多线程环境中设计并发数据结构。对于本文,我们使用 POSIX Threads 库(也称为 Pthreads;见 参考资料 中的链接),但是也可以使用 Boost Threads 等实现(见 参考资料 中的链接)。

    本文假设您基本了解基本数据结构,比较熟悉 POSIX Threads 库。您还应该基本了解线程的创建、互斥锁和条件变量。在本文的示例中,会相当频繁地使用 pthread_mutex_lockpthread_mutex_unlockpthread_cond_waitpthread_cond_signal 和pthread_cond_broadcast

    设计并发队列

    我们首先扩展最基本的数据结构之一:队列。我们的队列基于链表。底层列表的接口基于 Standard Template Library(STL;见 参考资料)。多个控制线程可以同时在队列中添加数据或删除数据,所以需要用互斥锁对象管理同步。队列类的构造函数和析构函数负责创建和销毁互斥锁,见 清单 1

    清单 1. 基于链表和互斥锁的并发队列
    #include <pthread.h>
    #include <list.h> // you could use std::list or your implementation 
    
    namespace concurrent { 
    template <typename T>
    class Queue { 
    public: 
       Queue( ) { 
           pthread_mutex_init(&_lock, NULL); 
        } 
        ~Queue( ) { 
           pthread_mutex_destroy(&_lock);
        } 
        void push(const T& data);
        T pop( ); 
    private: 
        list<T> _list; 
        pthread_mutex_t _lock;
    }
    
    };

    在并发队列中插入和删除数据

    显然,把数据放到队列中就像是把数据添加到列表中,必须使用互斥锁保护这个操作。但是,如果多个线程都试图把数据添加到队列中,会发生什么?第一个线程锁住互斥并把数据添加到队列中,而其他线程等待轮到它们操作。第一个线程解锁/释放互斥锁之后,操作系统决定接下来让哪个线程在队列中添加数据。通常,在没有实时优先级线程的 Linux® 系统中,接下来唤醒等待时间最长的线程,它获得锁并把数据添加到队列中。清单 2 给出代码的第一个有效版本。

    清单 2. 在队列中添加数据
    void Queue<T>::push(const T& value ) { 
           pthread_mutex_lock(&_lock);
           _list.push_back(value);
           pthread_mutex_unlock(&_lock);
    }

    取出数据的代码与此类似,见 清单 3

    清单 3. 从队列中取出数据
    T Queue<T>::pop( ) { 
           if (_list.empty( )) { 
               throw ”element not found”;
           }
           pthread_mutex_lock(&_lock); 
           T _temp = _list.front( );
           _list.pop_front( );
           pthread_mutex_unlock(&_lock);
           return _temp;
    }

    清单 2 和 清单 3 中的代码是有效的。但是,请考虑这样的情况:您有一个很长的队列(可能包含超过 100,000 个元素),而且在代码执行期间的某个时候,从队列中读取数据的线程远远多于添加数据的线程。因为添加和取出数据操作使用相同的互斥锁,所以读取数据的速度会影响写数据的线程访问锁。那么,使用两个锁怎么样?一个锁用于读取操作,另一个用于写操作。清单 4 给出修改后的 Queue 类。

    清单 4. 对于读和写操作使用单独的互斥锁的并发队列
    template <typename T>
    class Queue { 
    public: 
       Queue( ) { 
           pthread_mutex_init(&_rlock, NULL); 
           pthread_mutex_init(&_wlock, NULL);
        } 
        ~Queue( ) { 
           pthread_mutex_destroy(&_rlock);
           pthread_mutex_destroy(&_wlock);
        } 
        void push(const T& data);
        T pop( ); 
    private: 
        list<T> _list; 
        pthread_mutex_t _rlock, _wlock;
    }

    清单 5 给出 push/pop 方法的定义。

    清单 5. 使用单独互斥锁的并发队列 Push/Pop 操作
    void Queue<T>::push(const T& value ) { 
           pthread_mutex_lock(&_wlock);
           _list.push_back(value);
           pthread_mutex_unlock(&_wlock);
    }
    
    T Queue<T>::pop( ) { 
           if (_list.empty( )) { 
               throw ”element not found”;
           }
           pthread_mutex_lock(&_rlock);
           T _temp = _list.front( );
           _list.pop_front( );
           pthread_mutex_unlock(&_rlock);
           return _temp;
    }

    设计并发阻塞队列

    目前,如果读线程试图从没有数据的队列读取数据,仅仅会抛出异常并继续执行。但是,这种做法不总是我们想要的,读线程很可能希望等待(即阻塞自身),直到有数据可用时为止。这种队列称为阻塞的队列。如何让读线程在发现队列是空的之后等待?一种做法是定期轮询队列。但是,因为这种做法不保证队列中有数据可用,它可能会导致浪费大量 CPU 周期。推荐的方法是使用条件变量 — 即 pthread_cond_t 类型的变量。在深入讨论语义之前,先来看一下修改后的队列定义,见 清单 6

    清单 6. 使用条件变量的并发阻塞队列
    template <typename T>
    class BlockingQueue { 
    public: 
       BlockingQueue ( ) { 
           pthread_mutex_init(&_lock, NULL); 
           pthread_cond_init(&_cond, NULL);
        } 
        ~BlockingQueue ( ) { 
           pthread_mutex_destroy(&_lock);
           pthread_cond_destroy(&_cond);
        } 
        void push(const T& data);
        T pop( ); 
    private: 
        list<T> _list; 
        pthread_mutex_t _lock;
        pthread_cond_t _cond;
    }

    清单 7 给出阻塞队列的 pop 操作定义。

    清单 7. 从队列中取出数据
    T BlockingQueue<T>::pop( ) { 
           pthread_mutex_lock(&_lock);
           if (_list.empty( )) { 
               pthread_cond_wait(&_cond, &_lock) ;
           }
           T _temp = _list.front( );
           _list.pop_front( );
           pthread_mutex_unlock(&_lock);
           return _temp;
    }

    当队列是空的时候,读线程现在并不抛出异常,而是在条件变量上阻塞自身。pthread_cond_wait 还隐式地释放 mutex_lock。现在,考虑这个场景:有两个读线程和一个空的队列。第一个读线程锁住互斥锁,发现队列是空的,然后在 _cond 上阻塞自身,这会隐式地释放互斥锁。第二个读线程经历同样的过程。因此,最后两个读线程都等待条件变量,互斥锁没有被锁住。

    现在,看一下 push() 方法的定义,见 清单 8

    清单 8. 在阻塞队列中添加数据
    void BlockingQueue <T>::push(const T& value ) { 
           pthread_mutex_lock(&_lock);
           const bool was_empty = _list.empty( );
           _list.push_back(value);
           pthread_mutex_unlock(&_lock);
           if (was_empty) 
               pthread_cond_broadcast(&_cond);
    }

    如果列表原来是空的,就调用 pthread_cond_broadcast 以宣告列表中已经添加了数据。这么做会唤醒所有等待条件变量 _cond 的读线程;读线程现在隐式地争夺互斥锁。操作系统调度程序决定哪个线程获得对互斥锁的控制权 — 通常,等待时间最长的读线程先读取数据。

    并发阻塞队列设计有两个要注意的方面:

    • 可以不使用 pthread_cond_broadcast,而是使用 pthread_cond_signal。但是,pthread_cond_signal 会释放至少一个等待条件变量的线程,这个线程不一定是等待时间最长的读线程。尽管使用 pthread_cond_signal 不会损害阻塞队列的功能,但是这可能会导致某些读线程的等待时间过长。
    • 可能会出现虚假的线程唤醒。因此,在唤醒读线程之后,要确认列表非空,然后再继续处理。清单 9 给出稍加修改的 pop() 方法,强烈建议使用基于 while 循环的 pop() 版本。
    清单 9. 能够应付虚假唤醒的 pop() 方法
    T BlockingQueue<T>::pop( ) { 
           pthread_cond_wait(&_cond, &_lock) ;
           while(_list.empty( )) { 
               pthread_cond_wait(&_cond) ;
           }
           T _temp = _list.front( );
           _list.pop_front( );
           pthread_mutex_unlock(&_lock);
           return _temp;
    }

    设计有超时限制的并发阻塞队列

    在许多系统中,如果无法在特定的时间段内处理新数据,就根本不处理数据了。例如,新闻频道的自动收报机显示来自金融交易所的实时股票行情,它每 n 秒收到一次新数据。如果在 n 秒内无法处理以前的一些数据,就应该丢弃这些数据并显示最新的信息。根据这个概念,我们来看看如何给并发队列的添加和取出操作增加超时限制。这意味着,如果系统无法在指定的时间限制内执行添加和取出操作,就应该根本不执行操作。清单 10 给出接口。

    清单 10. 添加和取出操作有时间限制的并发队列
    template <typename T>
    class TimedBlockingQueue { 
    public: 
       TimedBlockingQueue ( );
        ~TimedBlockingQueue ( );
        bool push(const T& data, const int seconds);
        T pop(const int seconds); 
    private: 
        list<T> _list; 
        pthread_mutex_t _lock;
        pthread_cond_t _cond;
    }

    首先看看有时间限制的 push() 方法。push() 方法不依赖于任何条件变量,所以没有额外的等待。造成延迟的惟一原因是写线程太多,要等待很长时间才能获得锁。那么,为什么不提高写线程的优先级?原因是,如果所有写线程的优先级都提高了,这并不能解决问题。相反,应该考虑创建少数几个调度优先级高的写线程,把应该确保添加到队列中的数据交给这些线程。清单 11 给出代码。

    清单 11. 把数据添加到阻塞队列中,具有超时限制
    bool TimedBlockingQueue <T>::push(const T& data, const int seconds) {
           struct timespec ts1, ts2;
           const bool was_empty = _list.empty( );
           clock_gettime(CLOCK_REALTIME, &ts1);
           pthread_mutex_lock(&_lock);
           clock_gettime(CLOCK_REALTIME, &ts2);
           if ((ts2.tv_sec – ts1.tv_sec) <seconds) {
           was_empty = _list.empty( );
           _list.push_back(value);
           {
           pthread_mutex_unlock(&_lock);
           if (was_empty) 
               pthread_cond_broadcast(&_cond);
    }

    clock_gettime 例程返回一个 timespec 结构,它是系统纪元以来经过的时间(更多信息见 参考资料)。在获取互斥锁之前和之后各调用这个例程一次,从而根据经过的时间决定是否需要进一步处理。

    具有超时限制的取出数据操作比添加数据复杂;注意,读线程会等待条件变量。第一个检查与 push() 相似。如果在读线程能够获得互斥锁之前发生了超时,那么不需要进行处理。接下来,读线程需要确保(这是第二个检查)它等待条件变量的时间不超过指定的超时时间。如果到超时时间段结束时还没有被唤醒,读线程需要唤醒自身并释放互斥锁。

    有了这些背景知识,我们来看看 pthread_cond_timedwait 函数,这个函数用于进行第二个检查。这个函数与 pthread_cond_wait 相似,但是第三个参数是绝对时间值,到达这个时间时读线程自愿放弃等待。如果在超时之前读线程被唤醒,pthread_cond_timedwait 的返回值是0清单 12 给出代码。

    清单 12. 从阻塞队列中取出数据,具有超时限制
    T TimedBlockingQueue <T>::pop(const int seconds) { 
           struct timespec ts1, ts2; 
           clock_gettime(CLOCK_REALTIME, &ts1); 
           pthread_mutex_lock(&_lock);
           clock_gettime(CLOCK_REALTIME, &ts2);
    
           // First Check 
           if ((ts1.tv_sec – ts2.tv_sec) < seconds) { 
               ts2.tv_sec += seconds; // specify wake up time
               while(_list.empty( ) && (result == 0)) { 
                   result = pthread_cond_timedwait(&_cond, &_lock, &ts2) ;
               }
               if (result == 0) { // Second Check 
                   T _temp = _list.front( );
                  _list.pop_front( );
                  pthread_mutex_unlock(&_lock);
                  return _temp;
              }
          }
          pthread_mutex_unlock(&lock);
          throw “timeout happened”;
    }

    清单 12 中的 while 循环确保正确地处理虚假的唤醒。最后,在某些 Linux 系统上,clock_gettime 可能是 librt.so 的组成部分,可能需要在编译器命令行中添加 –lrt 开关。

    使用 pthread_mutex_timedlock API

    清单 11 和 清单 12 的缺点之一是,当线程最终获得锁时,可能已经超时了。因此,它只能释放锁。如果系统支持的话,可以使用pthread_mutex_timedlock API 进一步优化这个场景(见 参考资料)。这个例程有两个参数,第二个参数是绝对时间值。如果在到达这个时间时还无法获得锁,例程会返回且状态码非零。因此,使用这个例程可以减少系统中等待的线程数量。下面是这个例程的声明:

    int pthread_mutex_timedlock(pthread_mutex_t *mutex,
           const struct timespec *abs_timeout);

    设计有大小限制的并发阻塞队列

    最后,讨论有大小限制的并发阻塞队列。这种队列与并发阻塞队列相似,但是对队列的大小有限制。在许多内存有限的嵌入式系统中,确实需要有大小限制的队列。

    对于阻塞队列,只有读线程需要在队列中没有数据时等待。对于有大小限制的阻塞队列,如果队列满了,写线程也需要等待。这种队列的外部接口与阻塞队列相似,见 清单 13。(注意,这里使用向量而不是列表。如果愿意,可以使用基本的 C/C++ 数组并把它初始化为指定的大小。)

    清单 13. 有大小限制的并发阻塞队列
    template <typename T>
    class BoundedBlockingQueue { 
    public: 
       BoundedBlockingQueue (int size) : maxSize(size) { 
           pthread_mutex_init(&_lock, NULL); 
           pthread_cond_init(&_rcond, NULL);
           pthread_cond_init(&_wcond, NULL);
           _array.reserve(maxSize);
        } 
        ~BoundedBlockingQueue ( ) { 
           pthread_mutex_destroy(&_lock);
           pthread_cond_destroy(&_rcond);
           pthread_cond_destroy(&_wcond);
        } 
        void push(const T& data);
        T pop( ); 
    private: 
        vector<T> _array; // or T* _array if you so prefer
        int maxSize;
        pthread_mutex_t _lock;
        pthread_cond_t _rcond, _wcond;
    }

    在解释添加数据操作之前,看一下 清单 14 中的代码。

    清单 14. 在有大小限制的阻塞队列中添加数据
    void BoundedBlockingQueue <T>::push(const T& value ) { 
           pthread_mutex_lock(&_lock);
           const bool was_empty = _array.empty( );
           while (_array.size( ) == maxSize) { 
               pthread_cond_wait(&_wcond, &_lock);
           } 
           _ array.push_back(value);
          pthread_mutex_unlock(&_lock);
          if (was_empty) 
              pthread_cond_broadcast(&_rcond);
    }

    锁是否可以扩展到其他数据结构?

    当然可以。但这是最好的做法吗?不是。考虑一个应该允许多个线程使用的链表。与队列不同,列表没有单一的插入或删除点,使用单一互斥锁控制对列表的访问会导致系统功能正常但相当慢。另一种实现是对每个节点使用锁,但是这肯定会增加系统的内存占用量。本系列的第二部分会讨论这些问题。

    对于 清单 13 和 清单 14,要注意的第一点是,这个阻塞队列有两个条件变量而不是一个。如果队列满了,写线程等待 _wcond 条件变量;读线程在从队列中取出数据之后需要通知所有线程。同样,如果队列是空的,读线程等待 _rcond 变量,写线程在把数据插入队列中之后向所有线程发送广播消息。如果在发送广播通知时没有线程在等待 _wcond 或 _rcond,会发生什么?什么也不会发生;系统会忽略这些消息。还要注意,两个条件变量使用相同的互斥锁。清单 15 给出有大小限制的阻塞队列的 pop() 方法。

    清单 15. 从有大小限制的阻塞队列中取出数据
    T BoundedBlockingQueue<T>::pop( ) { 
           pthread_mutex_lock(&_lock);
           const bool was_full = (_array.size( ) == maxSize);
           while(_array.empty( )) { 
               pthread_cond_wait(&_rcond, &_lock) ;
           }
           T _temp = _array.front( );
           _array.erase( _array.begin( ));
           pthread_mutex_unlock(&_lock);
           if (was_full)
               pthread_cond_broadcast(&_wcond);
           return _temp;
    }

    注意,在释放互斥锁之后调用 pthread_cond_broadcast。这是一种好做法,因为这会减少唤醒之后读线程的等待时间。

    结束语

    本文讨论了几种并发队列及其实现。实际上,还可能实现其他变体。例如这样一个队列,它只允许读线程在数据插入队列经过指定的延时之后才能读取数据。请通过 参考资料 进一步了解 POSIX 线程和并发队列算法。


    用于并行计算的多线程数据结构,第 2 部分: 设计不使用互斥锁的并发数据结构

    本文是讨论多线程结构的两篇系列文章的第二篇,介绍关于实现基于互斥锁的并发链表的设计方法,讨论如何设计不使用互斥锁的并发数据结构。

    Arpan Sen, 独立作家

    2011 年 7 月 11 日

    • +内容

    简介

    本文是本系列的最后一篇,讨论两个主题:关于实现基于互斥锁的并发链表的设计方法和设计不使用互斥锁的并发数据结构。对于后一个主题,我选择实现一个并发堆栈并解释设计这种数据结构涉及的一些问题。用 C++ 设计独立于平台的不使用互斥锁的数据结构目前还不可行,所以我选用 GCC version 4.3.4 作为编译器并在代码中使用 GCC 特有的 __sync_* 函数。如果您是 WIndows® C++ 开发人员,可以考虑使用 Interlocked* 系列函数实现相似的功能。

    并发单向链表的设计方法

    清单 1 给出最基本的并发单向链表接口。是不是缺少什么东西?

    清单 1. 并发单向链表接口
    template <typename T>
    class SList { 
       private: 
           typedef struct Node { 
                T data;
                Node *next;
                Node(T& data) : value(data), next(NULL) { }
           } Node; 
           pthread_mutex_t _lock;
           Node *head, *tail;  
       public: 
           void push_back(T& value);
           void insert_after(T& previous, T& value); // insert data after previous
           void remove(const T& value);
           bool find(const T& value);  // return true on success 
           SList(  );
           ~SList(  ); 
    };

    清单 2 给出 push_back 方法定义。

    清单 2. 把数据添加到并发链表中
    void SList<T>::push_back(T& data)
    { 
        pthread_mutex_lock(&_lock);
        if (head == NULL) { 
            head = new Node(data);
            tail = head;
        } else { 
            tail->next = new Node(data);
            tail = tail->next;
        }
        pthread_mutex_unlock(&_lock);
    }

    现在,假设一个线程试图通过调用 push_back 把 n 个整数连续地添加到这个链表中。这个接口本身要求获取并释放互斥锁 n 次,即使在第一次获取锁之前已经知道要插入的所有数据。更好的做法是定义另一个方法,它接收一系列整数,只获取并释放互斥锁一次。清单 3 给出方法定义。

    清单 3. 在链表中插入数据的更好方法
    void SList<T>::push_back(T* data, int count) // or use C++ iterators 
    { 
        Node *begin = new Node(data[0]);
        Node *temp = begin;
        for (int i=1; i<count; ++i) {
            temp->next = new Node(data[i]);
            temp = temp->next;
        }
            
        pthread_mutex_lock(&_lock);
        if (head == NULL) { 
            head = begin;
            tail = head;
        } else { 
            tail->next = begin;
            tail = temp;
        }
        pthread_mutex_unlock(&_lock);
    }

    优化搜索元素

    现在,我们来优化链表中的搜索元素 — 即 find 方法。下面是几种可能出现的情况:

    • 当一些线程正在迭代链表时,出现插入或删除请求。
    • 当一些线程正在迭代链表时,出现迭代请求。
    • 当一些线程正在插入或删除数据时,出现迭代请求。

    显然,应该能够同时处理多个迭代请求。如果系统中的插入/删除操作很少,主要活动是搜索,那么基于单一锁的方法性能会很差。在这种情况下,应该考虑使用读写锁,即 pthread_rwlock_t。在本文的示例中,将在 SList 中使用 pthread_rwlock_t 而不是 pthread_mutex_t。这么做就允许多个线程同时搜索链表。插入和删除操作仍然会锁住整个链表,这是合适的。清单 4 给出使用 pthread_rwlock_t 的链表实现。

    清单 4. 使用读写锁的并发单向链表
    template <typename T>
    class SList { 
       private: 
           typedef struct Node { 
               // … same as before 
           } Node; 
           pthread_rwlock_t _rwlock; // Not pthread_mutex_t any more!
           Node *head, *tail;  
       public: 
           // … other API remain as-is
           SList(  ) : head(NULL), tail(NULL) { 
               pthread_rwlock_init(&_rwlock, NULL);
           } 
           ~SList(  ) { 
               pthread_rwlock_destroy(&_rwlock);
               // … now cleanup nodes 
           } 
    };

    清单 5 给出链表搜索代码。

    清单 5. 使用读写锁搜索链表
    bool SList<T>::find(const T& value)
    { 
        pthread_rwlock_rdlock (&_rwlock);
        Node* temp = head;
        while (temp) { 
             if (temp->value == data) {
                  status = true;
                  break;
             }
             temp = temp->next;
        }
        pthread_rwlock_unlock(&_rwlock);
        return status;
    }

    清单 6 给出使用读写锁的 push_back 方法。

    清单 6. 使用读写锁在并发单向链表中添加数据
    void SList<T>::push_back(T& data)
    { 
        pthread_setschedprio(pthread_self( ), SCHED_FIFO);
        pthread_rwlock_wrlock(&_rwlock);
        // … All the code here is same as Listing 2
        pthread_rwlock_unlock(&_rwlock);
    }

    我们来分析一下。这里使用两个锁定函数调用(pthread_rwlock_rdlock 和 pthread_rwlock_wrlock)管理同步,使用pthread_setschedprio 调用设置写线程的优先级。如果没有写线程在这个锁上阻塞(换句话说,没有插入/删除请求),那么多个请求链表搜索的读线程可以同时操作,因为在这种情况下一个读线程不会阻塞另一个读线程。如果有写线程等待这个锁,当然不允许新的读线程获得锁,写线程等待,到现有的读线程完成操作时写线程开始操作。如果不按这种方式使用 pthread_setschedprio 设置写线程的优先级,根据读写锁的性质,很容易看出写线程可能会饿死。

    下面是对于这种方式要记住的几点:

    • 如果超过了最大读锁数量(由实现定义),pthread_rwlock_rdlock 可能会失败。
    • 如果有 n 个并发的读锁,一定要调用 pthread_rwlock_unlock n 次。

    允许并发插入

    应该了解的最后一个方法是 insert_after。同样,预期的使用模式要求调整数据结构的设计。如果一个应用程序使用前面提供的链表,它执行的插入和搜索操作数量差不多相同,但是删除操作很少,那么在插入期间锁住整个链表是不合适的。在这种情况下,最好允许在链表中的分离点(disjoint point)上执行并发插入,同样使用基于读写锁的方式。下面是构造链表的方法:

    • 在两个级别上执行锁定(见 清单 7):链表有一个读写锁,各个节点包含一个互斥锁。如果想节省空间,可以考虑共享互斥锁 — 可以维护节点与互斥锁的映射。
    • 在插入期间,写线程在链表上建立读锁,然后继续处理。在插入数据之前,锁住要在其后添加新数据的节点,插入之后释放此节点,然后释放读写锁。
    • 删除操作在链表上建立写锁。不需要获得与节点相关的锁。
    • 与前面一样,可以并发地执行搜索。
    清单 7. 使用两级锁定的并发单向链表
    template <typename T>
    class SList { 
       private: 
           typedef struct Node { 
                pthread_mutex_lock lock;
                T data;
                Node *next;
                Node(T& data) : value(data), next(NULL) { 
                    pthread_mutex_init(&lock, NULL);
                }
                ~Node( ) { 
                    pthread_mutex_destroy(&lock);
                }
           } Node; 
           pthread_rwlock_t _rwlock; // 2 level locking 
           Node *head, *tail;  
       public: 
           // … all external API remain as-is
           } 
    };

    清单 8 给出在链表中插入数据的代码。

    清单 8. 使用双重锁定在链表中插入数据
    void SList<T>:: insert_after(T& previous, T& value)
    { 
        pthread_rwlock_rdlock (&_rwlock);
        Node* temp = head;
        while (temp) { 
             if (temp->value == previous) {
                  break;
             }
             temp = temp->next;
        }
        Node* newNode = new Node(value);
        
        pthread_mutex_lock(&temp->lock);
        newNode->next = temp->next;
        temp->next = newNode;
        pthread_mutex_unlock(&temp->lock);
    
        pthread_rwlock_unlock(&_rwlock);
        return status;
    }

    基于互斥锁的方法的问题

    到目前为止,都是在数据结构中使用一个或多个互斥锁管理同步。但是,这种方法并非没有问题。请考虑以下情况:

    • 等待互斥锁会消耗宝贵的时间 — 有时候是很多时间。这种延迟会损害系统的可伸缩性。
    • 低优先级的线程可以获得互斥锁,因此阻碍需要同一互斥锁的高优先级线程。这个问题称为优先级倒置(priority inversion ) (更多信息见 参考资料 中的链接)。
    • 可能因为分配的时间片结束,持有互斥锁的线程被取消调度。这对于等待同一互斥锁的其他线程有不利影响,因为等待时间现在会更长。这个问题称为锁护送(lock convoying)(更多信息见 参考资料 中的链接)。

    互斥锁的问题还不只这些。最近,出现了一些不使用互斥锁的解决方案。话虽如此,尽管使用互斥锁需要谨慎,但是如果希望提高性能,肯定应该研究互斥锁。

    比较并交换指令

    在研究不使用互斥锁的解决方案之前,先讨论一下从 80486 开始在所有 Intel® 处理器上都支持的 CMPXCHG 汇编指令。清单 9 从概念角度说明这个指令的作用。

    清单 9. 比较并交换指令的行为
    int compare_and_swap ( int *memory_location, int expected_value, int new_value) 
    { 
      int old_value = *memory_location;
      if (old_value == expected_value) 
         *memory_location = new_value;
      return old_value;
    }

    这里发生的操作是:指令检查一个内存位置是否包含预期的值;如果是这样,就把新的值复制到这个位置。清单 10 提供汇编语言伪代码。

    清单 10. 比较并交换指令的汇编语言伪代码
    CMPXCHG OP1, OP2 
    if ({AL or AX or EAX} = OP1) 
           zero = 1               ;Set the zero flag in the flag register 
           OP1 = OP2
    else
           zero := 0              ;Clear the zero flag in the flag register 
           {AL or AX or EAX}= OP1

    CPU 根据操作数的宽度(8、16 或 32)选择 AL、AX 或 EAX 寄存器。如果 AL/AX/EAX 寄存器的内容与操作数 1 的内容匹配,就把操作数 2 的内容复制到操作数 1;否则,用操作数 2 的值更新 AL/AX/EAX 寄存器。Intel Pentium® 64 位处理器有相似的指令 CMPXCHG8B,它支持 64 位的比较并交换。注意,CMPXCHG 指令是原子性的,这意味着在这个指令结束之前没有可见的中间状态。它要么完整地执行,要么根本没有开始。在其他平台上有等效的指令,例如 Motorola MC68030 处理器的 compare and swap (CAS) 指令有相似的语义。

    我们为什么对 CMPXCHG 感兴趣?这意味着要使用汇编语言编写代码吗?

    需要了解 CMPXCHG 和 CMPXCHG8B 等相关指令是因为它们构成了无锁解决方案的核心。但是,不必使用汇编语言编写代码。GCC (GNU Compiler Collection,4.1 和更高版本)提供几个原子性的内置函数(见 参考资料),可以使用它们为 x86 和 x86-64 平台实现 CAS 操作。实现这一支持不需要包含头文件。在本文中,我们要在无锁数据结构的实现中使用 GCC 内置函数。看一下这些内置函数:

    bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)
    type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

    __sync_bool_compare_and_swap 内置函数比较 oldval 和 *ptr。如果它们匹配,就把 newval 复制到 *ptr。如果 oldval 和 *ptr 匹配,返回值是 True,否则是 False。__sync_val_compare_and_swap 内置函数的行为是相似的,只是它总是返回旧值。清单 11 提供一个使用示例。

    清单 11. GCC CAS 内置函数的使用示例
    #include <iostream>
    using namespace std;
     
    int main()
    {
       bool lock(false);
       bool old_value = __sync_val_compare_and_swap( &lock, false, true); 
       cout >> lock >> endl; // prints 0x1
       cout >> old_value >> endl; // prints 0x0
    }

    设计无锁并发堆栈

    既然了解了 CAS,现在就来设计一个并发堆栈。这个堆栈没有锁;这种无锁的并发数据结构也称为非阻塞数据结构清单 12 给出代码接口。

    清单 12. 基于链表的非阻塞堆栈实现
    template <typename T> 
    class Stack { 
        typedef struct Node { 
                              T data;
                              Node* next;
                              Node(const T& d) : data(d), next(0) { } 
                            } Node;
        Node *top; 
        public: 
           Stack( ) : top(0) { }
           void push(const T& data);
           T pop( ) throw (…); 
    };

    清单 13 给出压入操作的定义。

    清单 13. 在非阻塞堆栈中压入数据
    void Stack<T>::push(const T& data) 
    { 
        Node *n = new Node(data); 
        while (1) { 
            n->next = top;
            if (__sync_bool_compare_and_swap(&top, n->next, n)) { // CAS
                break;
            }
        }
    }

    压入(Push)操作做了什么?从单一线程的角度来看,创建了一个新节点,它的 next 指针指向堆栈的顶部。接下来,调用 CAS 内置函数,把新的节点复制到 top 位置。

    从多个线程的角度来看,完全可能有两个或更多线程同时试图把数据压入堆栈。假设线程 A 试图把 20 压入堆栈,线程 B 试图压入 30,而线程 A 先获得了时间片。但是,在 n->next = top 指令结束之后,调度程序暂停了线程 A。现在,线程 B 获得了时间片(它很幸运),它能够完成 CAS,把 30 压入堆栈后结束。接下来,线程 A 恢复执行,显然对于这个线程 *top 和 n->next 不匹配,因为线程 B 修改了 top 位置的内容。因此,代码回到循环的开头,指向正确的 top 指针(线程 B 修改后的),调用 CAS,把 20 压入堆栈后结束。整个过程没有使用任何锁。

    弹出操作

    清单 14 给出从堆栈弹出数据的代码。

    清单 14. 从非阻塞堆栈弹出数据
    T Stack<T>::pop( ) 
    { 
        if (top == NULL) 
           throw std::string(“Cannot pop from empty stack”);
        while (1) { 
            Node* next = top->next;
            if (__sync_bool_compare_and_swap(&top, top, next)) { // CAS
                return top->data;
            }
        }
    }

    用与 push 相似的代码定义弹出操作语义。堆栈的顶存储在 result 中,使用 CAS 把 top 位置更新为 top->next 并返回适当的数据。如果恰在执行 CAS 之前线程失去执行权,那么在线程恢复执行之后,CAS 会失败,继续循环,直到有有效的数据可用为止。

    结果好就一切都好

    不幸的是,这种堆栈弹出实现有问题 — 包括明显的问题和不太明显的问题。明显的问题是 NULL 检查必须放在 while 循环中。如果线程 P 和线程 Q 都试图从只剩一个元素的堆栈弹出数据,而线程 P 恰在执行 CAS 之前失去执行权,那么当它重新获得执行权时,堆栈中已经没有可弹出的数据了。因为 top 是 NULL,访问 &top 肯定会导致崩溃 — 这显然是可以避免的 bug。这个问题也突显了并发数据结构的基本设计原则之一:决不要假设任何代码会连续执行。

    清单 15 给出解决了此问题的代码。

    清单 15. 从非阻塞堆栈弹出数据
    T Stack<T>::pop( ) 
    { 
        while (1) { 
            if (top == NULL) 
               throw std::string(“Cannot pop from empty stack”);
            Node* next = top->next;
            if (top && __sync_bool_compare_and_swap(&top, top, next)) { // CAS
                return top->data;
            }
        }
    }

    下一个问题比较复杂,但是如果您了解内存管理程序的工作方式(更多信息见 参考资料 中的链接),应该不太难理解。清单 16 展示这个问题。

    清单 16. 内存的回收利用会导致 CAS 出现严重的问题
    T* ptr1 = new T(8, 18);
    T* old = ptr1; 
    // .. do stuff with ptr1
    delete ptr1;
    T* ptr2 = new T(0, 1);
    
    // We can't guarantee that the operating system will not recycle memory
    // Custom memory managers recycle memory often
    if (old1 == ptr2) { 
       …
    }

    在此代码中,无法保证 old 和 ptr2 有不同的值。根据操作系统和定制的应用程序内存管理系统的具体情况,完全可能回收利用已删除的内存 — 也就是说,删除的内存放在应用程序专用的池中,可在需要时重用,而不返回给系统。这显然会改进性能,因为不需要通过系统调用请求更多内存。尽管在一般情况下这是有利的,但是对于非阻塞堆栈不好。现在我们来看看这是为什么。

    假设有两个线程 — A 和 B。A 调用 pop 并恰在执行 CAS 之前失去执行权。然后 B 调用 pop ,然后压入数据,数据的一部分来自从前面的弹出操作回收的内存。清单 17 给出伪代码。

    清单 17. 序列图
    Thread A tries to pop
    Stack Contents: 5 10 14 9 100 2
    result = pointer to node containing 5 
    Thread A now de-scheduled
    
    Thread B gains control 
    Stack Contents: 5 10 14 9 100 2
    Thread B pops 5
    Thread B pushes 8 16 24 of which 8 was from the same memory that earlier stored 5
    Stack Contents: 8 16 24 10 14 9 100 2
    
    Thread A gains control 
    At this time, result is still a valid pointer and *result = 8 
    But next points to 10, skipping 16 and 24!!!

    纠正方法相当简单:不存储下一个节点。清单 18 给出代码。

    清单 18. 从非阻塞堆栈弹出数据
    T Stack<T>::pop( ) 
    { 
        while (1) { 
            Node* result = top;
            if (result == NULL) 
               throw std::string(“Cannot pop from empty stack”);      
            if (top && __sync_bool_compare_and_swap(&top, result, result->next)) { // CAS
                return top->data;
            }
        }
    }

    这样,即使线程 B 在线程 A 试图弹出数据的同时修改了堆栈顶,也可以确保不会跳过堆栈中的元素。

    结束语

    本系列讨论了如何设计支持并发访问的数据结构。您已经看到,设计可以基于互斥锁,也可以是无锁的。无论采用哪种方式,要考虑的问题不仅仅是这些数据结构的基本功能 — 具体来说,必须一直记住线程会争夺执行权,要考虑线程重新执行时如何恢复操作。目前,解决方案(尤其是无锁解决方案)与平台/编译器紧密相关。请研究用于实现线程和锁的 Boost 库,阅读 John Valois 关于无锁链表的文章(见 参考资料 中的链接)。C++0x 标准提供了 std::thread 类,但是目前大多数编译器对它的支持很有限,甚至不支持它


    展开全文
  • 多线程的那点儿事(之多线程数据结构

    万次阅读 多人点赞 2011-12-09 21:05:35
    所以,我们在编写多线程的时候,就需要考虑一下如何在数据结构中插入锁。当然,有些数据结构是没有锁的,所以自然这个锁并不一定是必须的。  比如说,我们编写一个多线程堆栈,应该怎么做呢, typedef s
    【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】
    

        要想编写多线程,那就要使用锁。而在软件编写中,数据结构是少不了的。所以,我们在编写多线程的时候,就需要考虑一下如何在数据结构中插入锁。当然,有些数据结构是没有锁的,所以自然这个锁并不一定是必须的。

        比如说,我们编写一个多线程堆栈,应该怎么做呢,

    typedef struct _STACK
    {
        void* pData;
        int maxLen;
        int top;
        void* hLock;
        
        STATUS (*push)(struct _STACK* pStack, void* pData, int size);
        STATUS (*pop)(struct _STACK* pStack, void* pData, int size);   
    }STACK;
        (1) 初始化操作

    STACK* get_new_stack(void* pData, int len, void* pLock)
    {
        STACK* pStack;
          
        if(NULL == pData || 0 == len)
            return NULL;
    
        pStack = (STACK*)malloc(sizeof(STACK));
        assert(NULL != pStack);
    
        memset(pStack, 0, sizeof(STACK));
        pStack->pData  = pData;
        pStack->maxLen = len;
        
        if(NULL != pLock)
            pStack->hLock = pLock;
    
        return pStack;
    }  
        (2) 添加数据
    STATUS push(struct _STACK* pStack, void* pData, int size)
    {
        assert(NULL != pStack && NULL != pData);
    
        if(NULL != pStack->hLock)
            WaitForSingleObject((HANDLE)pStack->hLock, INFINITE);
    
        if(pStack->top == pStack->maxLen){
            if(NULL != pStack->hLock)
                ReleaseMutex((HANDLE)pStack->hLock);
            
            return ERROR;
        }
    
        memmove((char*)pStack->pData + size * pStack->top, (char*)pData, size);
        pStack->top ++;
        
        if(NULL != pStack->hLock)
            ReleaseMutex((HANDLE)pStack->hLock);        
    
        return OK;
    }
        (3) 对2进行优化,因为判断的条件比较复杂

    #define STACK_CHECK_LOCK(hLock) \
    do{\
        if(hLock)\
            WaitForSingleObject((HANDLE)hLock, INFINITE);\
    }while(0)
    
    #define STACK_CHECK_UNLOCK(hLock) \
    do{\
        if(hLock)\
            ReleaseMutex((HANDLE)hLock);\
    }while(0)
        所以,2的代码可以修改为,

    STATUS push(struct _STACK* pStack, void* pData, int size)
    {
        assert(NULL != pStack && NULL != pData);
    
        STACK_CHECK_LOCK(pStack->hLock);
    
        if(pStack->top == pStack->maxLen){
            STACK_CHECK_UNLOCK(pStack->hLock);
            return ERROR;
        }
    
        memmove((char*)pStack->pData + size * pStack->top, (char*)pData, size);
        pStack->top ++;
        
        STACK_CHECK_UNLOCK(pStack->hLock);      
        return OK;
    }

    总结:
        (1)  一般来说,比较好的数据结构要兼有多线程和没有多线程两种情况
        (2)  如果需要用其他的锁代替mutex,直接换掉就可以,十分方便


    展开全文
  • 线程数据结构

    千次阅读 2009-12-26 22:24:00
    除非显式地声明,否则,你可以假设以下讨论的内容既适合用户模式的线程,也适用于内核模式的线程。在系统级别上,Windows线程是由...而且,Windows子系统进程(Csrss)为Windows进程中创建的每个线程维护了一个平行结构

    除非显式地声明,否则,你可以假设以下讨论的内容既适合用户模式的线程,也适用于内核模式的线程。

    在系统级别上,Windows线程是由一个线程块执行体(ETHREAD)来表示的,如图6.7所示。ETHREAD块和它所指向的结构都位于系统地址空间中,唯一的例外是线程环境快(TEB),它位于进程地址空间中。而且,Windows子系统进程(Csrss)为Windows进程中创建的每个线程维护了一个平行结构。另外,对于那些调用了任何一个Windows子系统USERGDI函数的线程,Windows子系统内核模式部分(Win32k.sys)为它维护了一个称为W32THREAD的数据结构,线程的ETHREAD块指向此结构。

    6.7中的大多数字段的意义已经很明了,不用多说了。第一个字段是内核线程块(KTHREAD)。紧随其后的是线程标识信息、进程标识信息(包括一个指向所有进程的指针,因而可以访问它的环境信息)、安全信息(包括一个指向访问令牌的指针以及身份模拟信息),最后是与LPC消息和待处理I/O请求有关的字段。关于ETHREAD块的信息,你可以使用内核调试器的lkd> dt nt!_ethread(对应进程的是_eprocess)命令来显示其数据结构。

    现在让我们来看一看两个关键的线程数据结构:KTHREADTEBKTHREAD块包含了Windows内核为这些正在运行的线程执行线程调度和同步而需要访问的信息。它的布局结构如图6.8所示。

    关于KTHREAD块的信息,你可以使用内核调试器的lkd> dt nt!_kthread(对应进程的是_kprocess)命令来显示其数据结构。

    6.9所示的TEB是本节中介绍的唯一位于进程地址空间中的数据结构。

    TEB存储了有关映像加载器和各种Windows DLL的环境信息。因为这些组件运行在用户模式下,所以它们需要一个在用户模式下可写的数据结构。为什么该结构位于进程地址空间中而不是位于系统地址空间中呢?因为系统空间只能在内核模式下才可写。通过内核调试器的lkd> dt nt!thread命令你可以看到TEB的地址,同样,你也可以用lkd> dt nt!_teb(对应进程的是_peb)命令来查看TEB的数据结构。

    线程的上下文

    线程的上下文本质上是一组处理器的寄存器,有正在执行程序中的指针及堆栈指针。上下文及其转换的过程根据处理器的结构不同会有所不同。我们可以调用内核调试器的lkd> dt nt!_context命令来观察上下文的数据结构。

    一个典型的上下文转换需要保存和重载以下的数据:

    • 程序计数器;
    • 处理器状态寄存器;
    • 其他寄存器的内容;
    • 用户模式和内核模式的栈指针;
    • 指向运行的线程的地址空间的指针,也就是进程的页表项。

    内核将旧线程的这些信息保存到当前内核模式的属于旧线程的栈中,然后更新栈指针,再将

    栈指针保存到旧线程的KTHREAD模块中。接着,内核栈指针就会指向新线程的内核栈,新线程的上下文将被装载。如果新的线程是属于不同的进程,系统将装载它的页表目录项到一个特殊的处理器寄存器中,让它的地址空间有效。如果有需要发送的内核APC被挂起,中断级别是1的中断产生。否则,控制权将交给新线程保存的程序计数器,线程重新执行。

     

    说明:

    本文摘自《Windows Internals》第6章《进程、线程和作业》6.1《线程的内部机理》

    展开全文
  • 进程和线程数据结构

    千次阅读 2017-05-18 09:57:20
    1、程序的运行时 数据结构 2、进程相关的数据结构 (linux进程) 3、Windows进程数据结构及创建流程
    展开全文
  • 线程上下文数据结构

    千次阅读 2010-07-02 08:47:00
    线程上下文数据结构 WINDOWS 中定义了一个CONTEXT 结构,该结构包含了特定处理器上的寄存器数据。系统使用CONTEXT 结构执行各种内部操作。目前,已经存在为Intel 、MIPS 、Alpha 和PowerPC ...
  • JAVA线程安全相关数据结构使用建议

    千次阅读 2017-08-02 14:31:29
    什么是线程安全的数据结构? 简单的说就是不同线程可以访问同一份数据时,它们对这份数据的访问是无序的随机的,是你不可控的。比如说你的房间谁都可以进来,但是你不确定他们谁先来谁后来或者可能同时来。你想让...
  • Java:简述Java中满足线程安全的数据结构 所谓 线程安全 就是:一段操纵共享数据的代码能够保证在同一时间内被多个线程执行而仍然保持其正确性的,就被称为是线程安全的。 线程安全是保证执行业务逻辑正确的基本...
  • Vector,HashTable是线程安全的集合类,不过,这两种类是很早的用法,现在一般要尽量少采用 set –没有重复项目的集合 有三种特定类型的集可用 ...TreeSet-基于(平衡)树的数据结构 List ArrayList(数组表)-类似于Ve
  • 简介 现在,您的计算机有四个 CPU 核;...本文是两篇系列文章的第一篇,讨论如何在多线程环境中设计并发数据结构。对于本文,我们使用 POSIX Threads 库(也称为 Pthreads;见 参考资料 中的链接),但是也可以使用
  • 上篇文章《c语言数据结构实现-数组队列/环形队列》讲述了数组队列的原理与实现,本文编写一个双线程进行速度测试 线程的工作方式分别也有三种:线程完全异步的机制、使用sem保证实时线程同步、使用条件变量保持同步 ...
  • 在python中,提供的线程是内核级的,python的线程切换主要有两种方式 1.一个线程当进行sleep,i/o操作时这是别的线程就有机会获得GIL,还有一种是,在py2中,当一个线程无中断的运行了1000个字节(py3中是15毫秒)...
  • //查找的时候,如果地址对应数据的key不对,那就 + 1查找。。 //浪费了空间,Hashtable是基于数组实现 //查找个数据 一次定位; 增删 一次定位; 增删查改 都很快 //浪费空间,数据太多,重复定位定位,效率就下去了...
  • 线程私有数据TSD

    千次阅读 2013-11-03 10:50:21
    仅在某个线程中有效,但却可以跨多个函数访问,比如程序可能需要每个线程维护一个链表,而使用相同的函数操作,最简单的办法就是使用同名而不同变量地址的线程相关数据结构。这样的数据结构可以由Posix线程库维护,...
  • Linux系统编程——线程私有数据

    万次阅读 2015-06-11 14:36:30
    比如在程序里可能需要每个线程维护一个链表,而会使用相同的函数来操作这个链表,最简单的方法就是使用同名而不同变量地址的线程相关数据结构。这样的数据结构可以由 Posix 线程库维护,成为线程私有数据 (Thread-...
  • C/C++ Users Journal October, 2004锁无关的(Lock-Free)数据结构在避免死锁的同时确保线程继续 Andrei Alexandrescu刘未鹏 译Andrei Alexandrescu是华盛顿大学计算机科学系的在读研究生,也是《Modern C++ Design...
  • VC 线程

    千次阅读 2016-09-02 09:28:14
    //线程数据结构 typedef struct ThreadData { XXXXXXDlg* pDlg; //窗口指针 int inttype = 0; BOOL Booltype = true; CString str = ""; }THREADDATA; THREADDATA* pThreadData = new THREADDATA; ...
  • 在单线程程序中,我们经常要用到"全局变量"以实现多个函数间共享数据, 然而在多线程...POSIX线程库通过维护一定的数据结构来解决这个问题,这个些数据称为(Thread-specific-data或 TSD)。 相关函数如下: int pthr
  • 线程间无需特别的手段进行通信,因为线程间可以共享数据结构,也就是一个全局变量可以被两个线程同时使用。不过要注意的是线程间需要做好同步,一般用mutex。可以参考一些比较新的UNIX/Linux编程的书,都会提到Posix...
  • 【Linux】Linux线程私有数据

    千次阅读 2018-09-10 16:52:08
    线程私有数据 在单线程程序中,函数经常使用全局变量或静态变量,这是不会影响程序的正确性的,但如果线程调用的函数使用全局变量或静态变量,则很可能引起错误。因为这些函数使用的全局变量和静态变量无法为不同的...
  • 线程与私有数据

    千次阅读 2011-02-13 10:13:00
    转载自:... <br />比如在程序里可能需要每个线程维护一个链表,而会使用相同的函数来操作这个链表,最简单的方法就是使用同名而不同变量地址的线程相关数据结构。这样
  • 转载自 警惕多线程环境string、vector、protobuf等自增长数据结构的隐性内存泄露 说明:遇到类似内存问题,猜测是同样的原因。测试中。。。 最近工作上一个模块内存泄露,内存缓慢增涨,存在oom的风险,很多人搞了...
  • Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的...
  • FS寄存器指向当前活动线程的TEB结构线程结构) 偏移 说明 000 指向SEH链指针 004 线程堆栈顶部 008 线程堆栈底部 00C SubSystemTib 010 FiberData 014 ArbitraryUserPointer 018 FS段寄存器在内存中的...
  • Java多线程学习(吐血超详细总结)

    万次阅读 多人点赞 2015-03-14 13:13:17
    本文主要讲了java中多线程的使用方法、线程同步、线程数据传递、线程状态及相应的一些线程函数用法、概述等。
  • 线程私有数据

    千次阅读 2015-08-18 09:45:23
    在多线程程序中,经常要用全局变量来实现多个函数间的数据共享。由于数据空间是共享的,因此全局变量也为所有线程共有。 测试代码如下: [cpp] view plaincopy #include  #...
  • linux线程私有数据详解

    千次阅读 2016-08-22 22:07:00
    在单线程程序中,函数经常使用全局变量或静态变量,这是不会影响程序的正确性的,但...而解决这一问题的一种方式就是使用线程私有数据线程私有数据采用了一种被称为一键多值的技术,即一个键对应多个数值。访问数据时都

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 773,407
精华内容 309,362
关键字:

线程的数据结构

数据结构 订阅