不均衡数据集的分类模型学习方法

简介

不均衡数据集指的是在分类问题中,数据集的两个类别之间的数量差别到达100:1,1000:1甚至10000:1的情况。当然,有些时候在多分类问题(multiclass classification)中也会出现。

如何在不均衡的数据集(imbalanced data)下进行学习,是一个很重要的问题,原因是这样的数据集会很大程度上限制我们的分类模型的准确性,正如文章所说——

“大部分标准的分类算法都期待一个均衡的类别分布,以及相近的误分类损失”。

在不均衡数据集的研究中,主要的领域有医疗分析、欺诈检测、网络入侵识别、溢油检测等。一个非常经典的数据集是乳腺摄影数据集(Mammography Data Set),在这个数据集中,有若干医学摄影图片以及其对应的二分类标签「健康」,「癌性」。

Image result for mammography data set
Mammography Data Set

在这个数据集中,有10923例阴性以及260例阳性。使用传统分类算法,非常容易出现的情况就是,阴性以几乎100%的正确率被成功分类,但是阳性的分类正确性却低至10%以下,在这个情境下,就是多达234例阳性样本被误诊。

在这一类数据集下,我们的目标就变成了在不严重损害大类(major class)的准确性的基础上,尽量让小类(minor class)的分类准确性提高。

不均衡问题的特性

内在不均衡和外在不均衡

数据集不均衡的成因可能是内在的(intrinsic)或者外在的(extrinsic),如之前所述的肿瘤识别,由于样本在真实世界的分布本身就是不均匀的,所以是内在不均衡。

另一方面,还会有一些情况,原本均匀分布的样本数据,由于采样偏差,导致最终进入数据集的时候样本不均匀了,这种情况则被称之为外在不均衡。这个情况最为著名的就是“欺诈检测”数据集。因为真实世界中,那些欺诈者,基本在申请阶段就已经被拒贷了,而我们无法获取到“如果他们借了钱,会不会逾期”,进而无法进入我们的训练数据集。

类间不均衡和类中不均衡

类间不均衡与类中不均衡同样值得注意,正如下图所示,在一些比较复杂的数据上,不仅不同的类别个数相差巨大,同一类样本之间,也会有不同的概念。对于小类别中间的小样本,样本数极少(underrepresented),分类器非常难以学习到完整的分类函数。

图a)只包含了类间不均衡,即五角星表示的“小类”样本个数远小于“圆圈”代表的“大类”,
图b)则同时包含了类间不均衡、类中不均衡、重叠、噪音等等……

小样本问题(small sample size problem)是传统不均衡问题之外的新兴研究方向,讲的是数据的维度和样本的个数显著不均衡。比较有代表性的有人脸识别、基因序列分析等。对于单纯的小样本问题,传统的做法有数据降维等措施。但是倘若小样本问题和类别不均衡同时存在,不仅小类中的样本数量过于稀缺,而且也会导致传统的解决算法无法归纳出有效的分类函数。是以后的研究重点。

不均衡数据集学习的state-of-art算法

当标准的学习算法遇上不均衡数据时,归纳出来的用于描述小类的规则通常比描述大类的规则要少要弱。这既是由于标签数量上的差别,又是由于小类的样本由于数量少本身可信度就较低。

基于采样的算法

Random Sampling

分为随机过采样(random oversampling)和随机欠采样(random undersampling),随机过采样的思路是从小类里面,随机复制若干样本点,加到原来的集合中,使数据集均衡。而随机欠采样则是从大类里面,随机删除若干样本点,使得数据集分布均衡。

随机欠采样可能导致遗失某些重要的信息,而随机过采样则有过拟合风险。

Informed Undersampling

首先讲讲Easy Ensemble算法,这个算法很简单,使用多次随机欠采样,每次都训练一个分类器,然后再将每次欠采样训练出来的分类器组合到一起,形成最终的分类器。

接着是Balance Cascade算法,这个算法是一个迭代算法。

  1. 在大类样本集合S_{maj}中选择一个子集E满足|E| = |S_{min}|
  2. 使用N = {E \cup S_{min}}进行训练,得到分类器
  3. 过滤出N中所有被正确归类的大类中的样本N_{maj}^*
  4. N_{maj}^*中的样本点剔除S_{maj},回到第1步

还有基于KNN的采样算法,该算法使用的四个规则来筛选出比较重要的大类样本点,用这些重要的样本点进行模型的训练。

  • NearMiss-1方法选择与“三个最接近的小类样本”的平均距离最小的大类样本点;
  • NearMiss-2方法选择与“三个最远的少数类样本”的平均距离最小的大类样本点;
  • NearMiss-3方法为每个小类样本选择给定数量的最接近的大类样本点,以确保每个小类样本点都被一些大类样本点包围;
  • “最大距离”方法选择了大多数类的样本点,这些样本点与“平均距离是最近的三个少数类”距离最大。

研究发现,其中NearMiss-2获得的结果较好。

Synthetic Sampling With Data Generation

合成少数子过采样技术(the synthetic minority oversampling technique, SMOTE)对于每个小类样本,寻找同为小类的K近邻,并使用插值法随机选取其连线中间的一个点最为一个新的过采样点。

(1)   \begin{equation*}x_{new} = x_i + (\hat{x_i} - x_i) \times \delta\end{equation*}

具体来说,上式中x_i为小类中的一个样本点,\hat{x_i}x_i的位于小类集合中的K近邻之一,\delta是一个随机[0,1]区间内实数。

Adaptive Synthetic Sampling

先介绍Borderline-SMOTE算法,和普通SMOTE算法不同的是,Borderline-SMOTE算法对于每一个小类样本点,都统计了其最近邻居中大类和小类的样本点个数。

  • 如果小类邻居多于一半,则该点是内部点,记为SAFE
  • 如果小类邻居少于一半,则该点是边界点,记为DANGER
  • 如果小类邻居为0,则该点为噪声,记为NOISE

统计完成后,使用DANGER集合点进行SMOTE的过采样算法。

ADASYN算法在此基础上又做了优化,去掉了“一半”这个人为的常数。使得过采样更加的自然。

(2)   \begin{equation*}G = (|S_{maj}| - |S_{min}|) \times \beta\end{equation*}

这里面\beta \in [0,1]是一个人为设计的常数,G是描述了“究竟小类需要补充多少个样本点?”

接下来,对于每一个小类样本点计算

(3)   \begin{equation*}\Gamma_i = \frac{\Delta_i / K}{Z}\end{equation*}

其中\Delta_i表示样本点的K近邻中有多少属于大类S_{maj}KZ用于归一化,使得\sum_{\Gamma_i} = 1

最终,每一个点按照下面式子,计算需要生成的点的个数,并使用SMOTE算法的方式进行过采样

(4)   \begin{equation*}g_i = \Gamma_i \times G\end{equation*}

Sampling With Data Clean Technique

Tomek link是一个基于数据清洗的技术,适用于一个经过过采样之后的数据集。其目的是为了解决“由于过采样导致的类别存在边界覆盖,进而影响分类器训练”这个问题。

其核心思想是找到两个离的很近的x_i \in  S_{maj}x_j \in S_{min},令d(x_i, x_j)表示x_ix_j的距离,那么(x_i, x_j)被称为Tomek link当且仅当不存在x_k,满足d(x_i, x_k) < d(x_i, x_j)d(x_j, x_k) < d(x_i, x_j)

Tomek link的出现意味着x_ix_j要不然有一个是噪音,要不然就是他们两个位于分类的交界处。将他们同时删除(或删除大类的那一个),可以有效的防止出现类别边界模糊,有利于提高分类器效果。

Cluster-Based Sampling Method

基于聚类的采样算法可以保证类间的不均衡也被关注。

具体来说,该算法首先使用迭代的方式,找到不同的团,这里使用了经典的KNN算法——

  1. 在两个类别中,分别随机选择K个团中心;
  2. 对于每个样本点,都被归类到最近的团中心;
  3. 团中心进行重新计算,用当前所有归类到该团的样本的坐标均值作为新一轮迭代的团中心;
  4. 跳至第2步

接着,将不同的团使用过采样的方式放大到同等规模。如下图所示——

Integration of Sampling and Boosting

SMOTEBoost 算法分为若干轮,每一轮都涉及到重新采样,使用递增的方式建立模型。每一轮,都着重采样哪些不能被上一轮模型所解释的样本。这样,分类器会逐渐习惯去拟合哪些少数的样本,因为他们更大概率会不能被上一轮的模型分类。

对于DataBoost-IM算法来说,则依照一定的比例来采样那些不容易被学习的样本。

基于修改成本函数的算法

一些对于成本敏感的学习算法,使用成本(cost)函数来量化误分类的程度。与其像基于采样的算法构造均衡的数据分布,不如直接设计一个不同的算是度量,使之能够适应不均衡的数据。

Cost-Sensitive Learning Framework

我们定义C(Min, Maj)表示将大类样本误分类为小类的成本,C(Maj, Min)则相反。那么成本敏感(cost-sensitive)学习的目标就是最小化训练集的总体成本,也就是所谓的贝叶斯条件风险(Bayes Conditional Risk)。

这个函数也可以非常容易的扩充到多标签的分类中,具体C矩阵定义如下——

此时,条件风险被定义为

(5)   \begin{equation*}R(i|x) = \sum_i{P(j|x)C(i,j)}\end{equation*}

这里P(j|x)被定义为给定样本x,实际上为类别j的概率。

通常的分类器,都默认分类错误有1的代价,而分类正确没有代价——

(6)   \begin{equation*} C(i,j) = \left\{ \begin{aligned} 1 & (i \neq j) \\ 0 & (i=j) \end{aligned} \right.\end{equation*}

而在非均衡学习中,我们需要保证有C(Maj, Min) > C(Min, Maj),以使得分类器能够更好地分辨大类小类。而接下来的算法,一大特点就是都使用了不同的办法,来讲我们认为定义的成本矩阵放到具体算法实现中——

  • 第一类技术将误分类成本作为数据空间权重应用于数据集;
  • 第二类将成本最小化成本的技巧运用在模型组合上;
  • 最后一类技术将对成本敏感的函数或特性直接纳入分类模型中,以便将对成本敏感的框架拟合到这些分类器的结果中。

Cost-Sensitive Dataspace Weighting with Adaptive Boosting

这里涉及了AdaBoost系列算法,包括AdaBoost.M1,AdaC1,AdaC2,AdaCost,CSB1,CSB2。以AdaBoost.M1为例讲解这类算法的核心思路——

对于数据集迭代,每一轮拥有不同的权值D_{t}(i)

(7)   \begin{equation*}D_{t+1}(i) = D_t(i) exp(-\alpha_t h_t(x_i) y_i) / Z_t\end{equation*}

其中\alpha_t = \frac{1}{2} ln(\frac{1-\epsilon_t}{\epsilon_t})。这个式子的粗略理解是如果一个样本被误分类,那么下一轮迭代将拥有更大的权值。

Cost-Sensitive Decision Trees

决策树的叶子节点是类别,非叶子节点是规则。建立决策树的过程是从上到下,逐层挑选一个最有分类性的规则,并将样本按照这个规则递归到两个子树处理。

Contact-lens decision tree
决策树

决策树有两个步骤,第一个是从上到下的分裂,第二个是从下到上的修建。

决策树的分裂使用了不纯度函数(impurity function),这个函数是否超过特定阈值决定了一个节点的分裂与否。不同的不纯度函数对于不均衡数据有不同的敏感度,比如传统的准确率函数就非常敏感,而Gini函数、熵函数(Entropy)、DKM函数就不那么敏感。其中,DKM函数生成的未修剪决策树相对较小。

决策树的修剪有利于增加其普遍性,但是对于不均衡数据,决策树的修剪可能会减掉小类的样本,降低模型准确度。类似于Laplace修剪技术也被提出用于让决策树的修剪不那么糟糕。

Cost-Sensitive Neural Networks

一个神经网络,会构造基于模型输出与目标距离的损失函数

(8)   \begin{equation*}E(\omega) = \frac{1}{2} \sum(t_k - o_k)^2\end{equation*}

其中\omega是模型权值,t_k,o_k分别是模型的目标与输出。在每一轮迭代,神经网络都会计算每个权值对于损失函数的梯度,用这个梯度更新权值,使得网络误差函数更小。

(9)   \begin{equation*}\Delta \omega_n = -\eta \nabla_{\omega} E(\omega_n)\end{equation*}

其中\eta是学习速率,\nabla_{\omega}是梯度算子。

成本敏感学习可以以下面四种方式引入模型——

  1. 成本敏感可以体现在对最终估计概率的修正上面
  2. 模型输出o_k可以被修正为成本敏感
  3. 学习速率可以被修正为成本敏感
  4. 误差函数最小化中的误差可以是成本敏感的

这四种方式都各有非常多的研究成果,这里就略去不谈。

基于核函数的算法和主动学习

Kernel-Based Learning Framework

这里讨论支持向量机(SVM)在不均衡数据集下的研究。由于支持向量机试图最小化总误差,因此它们天生就有优化大类样本的偏好。在一个理想模型里面,大类小类通过一条直线分隔,SVM分类的界限将远远偏离实际的界限。

Integration of Kernel Methods with Sampling Methods

大量研究都尝试将采样算法与SVM结合,其中比较有代表性的是GSVM-RU,将GSVM与欠采样算法结合。通过迭代的算法,每一轮迭代,都将大类中被定为支持向量的样本点移出。实现欠采样的目标。

位于最大间隔超平面边界上的点被称为支持向量

Kernel Modification Methods for Imbalanced Learning

直接修改核函数也是很多研究者研究的方向,这些研究的共同点是尝试向原来的SVM添加一个模块或替换一个模块,实现对不平衡数据的支持。包括了LOO-AUC、PSVM、P2PKNNC等等算法

Active Learning Methods for Imbalanced Learning

主动学习通过某种策略找到未进行类别标注的样本数据中最有价值的数据,交由专家进行人工标注后,将标注数据及其类别标签纳入到训练集中迭代优化分类模型,改进模型的处理效果。

在主动学习领域,文章指出,主动学习和基于核函数的学习算法有共通之处,所以有必要放在一起讨论。比如说,一个在SVM算法中靠近超平面的样本点就是比较有意义的。当然,如果遇到了数据不均衡,主动学习也会有很多需要研究的问题。

Additional Methods for Imbalanced Learning

不均衡数据的处理方式还有很多无法被分类到之前类别的算法。比如所有的多标签算法、小样本数量的处理算法、基于单个标签的学习算法等等。

评价指标

使用下表来定义正/负样本被模型正确/错误分类的个数,是后续统计指标的基本依赖变量——

True positives(TP):  被正确地划分为正例的个数,即实际为正例且被分类器划分为正例的实例数;
False positives(FP): 被错误地划分为正例的个数,即实际为负例但被分类器划分为正例的实例数;
False negatives(FN):被错误地划分为负例的个数,即实际为正例但被分类器划分为负例的实例数;
True negatives(TN): 被正确地划分为负例的个数,即实际为负例且被分类器划分为负例的实例数。 

单数值指标

这里假设小类为正类(positive),大类为负类(negative),有准确率(accuracy)和错误率(error rate)

(10)   \begin{equation*}Accuracy = \frac{TP+TN}{P_C+N_C}\end{equation*}

(11)   \begin{equation*}ErrorRate = 1 - Accuracy\end{equation*}

(12)   \begin{equation*}Precesion = \frac{TP}{TP+FP}\end{equation*}

(13)   \begin{equation*}Recall = \frac{TP}{TP+FN}\end{equation*}

(14)   \begin{equation*}F\_{Measure} = \frac{(1+\beta)^2 \cdot Recall \cdot Precesion}{\beta^2 \cdot Recall + Precesion}\end{equation*}

(15)   \begin{equation*}G\_{Mean} = \sqrt{\frac{TP}{TP+FN} \times \frac{TN}{TN+FP}}\end{equation*}

对于(1)(2)来说,虽然比较符合常理,但是容易被欺骗,比如对于5%正类,95%负类的数据,全部分类为负类可以达到95%正确率。这类“对于分布敏感”的指标不是用于不均衡数据集的算法效果评估。

对于精准率(3)来说,描述了“对于所有被分类器预测为正的样本,有多少预测对了?”
对于召回率(4)来说,描述了“有多少真正是正的类别,被正确预测了?”
通过观察公式,可以发现,精准率(3)是数据分布敏感的,而召回率(4)是数据分布不敏感的。
如果使用恰当的话,精准率和召回率已经足以描述用以评价分类器好坏的所有信息了。

F-Measures(5)是精准率率和召回率的合并,并用参数\beta调整双方的权重

G-Mean(6)则使用了正类准确率和负类准确率的比例来刻画分类器的偏好。

上面这些单变量指标虽然已经足够好了,但是还是没法解决一个问题“如何比较两个分类器孰好孰坏?”

ROC曲线

定义真阳性率(TPRate)和假阳性率(FPRate)

(16)   \begin{equation*}TP\_Rate = \frac{TP}{P_C}; FP\_Rate = \frac{FP}{N_C}\end{equation*}

ROC曲线的空间是一个二维平面,横坐标为假阳性率,纵坐标为真阳性率。

对于硬标签分类器(hard-type classifier),输出是类别标签,其效率可以用一个坐标点(FPR, TPR)画在ROC空间上。我们知道完美分类是A(0,1),也就是说越靠近A,分类器的效果越好,而灰色部分则是表示分类器没有随机分类好。

一个软标签分类器(soft-type classifier),输出是类别属于“正类”的概率,这种情况下,我们可以画出一条ROC曲线,在这种情况下,我们可以用曲线下方的面积来衡量分类器的效果。

PR曲线

研究发现ROC曲线有些时候会把模型的结果看的过于乐观,而PR曲线(Precession-Recall Curve)则是为了弥补这一缺憾的。

曲线和ROC曲线的唯一区别在于,ROC曲线使用(FPR, TPR)刻画分类器的效果,而PR曲线则用(Precesion, Recall)来刻画分类器效果。

比较两个曲线的公式,我们会发现FP_Rate在N_C非常大的时候,无法捕捉到FP的数量变化。

代价曲线

代价曲线(Cost Curve)尝试解释的问题是“一个分类器在处理先验概率不同样本表现如何?”。在ROC曲线中的每一个点都对应了代价曲线里面的一条线。

在ROC曲线中的坐标(FP, TP),都可以计算出期望的代价

(17)   \begin{equation*}E(C) = (1-TP-FT)\times PCF(+)+FP\end{equation*}

其中E(C)是期望代价,PCF(+)是样本为正的先验概率。

我们可以将手中若干可用的分类器的代价直线下方区域求交,获得的面积就是代价曲线,该曲线的含义是在“已知先验概率的条件下选择分类器,能够达到的最小期望代价是多少?”

多分类问题的拓展指标

上述的很多指标都可以拓展到多标签分类问题中,包括多标签ROC,M-Measures,Misclassification Cost……

未来我们该怎么做?

了解不均衡分类算法的本质

现在的很多研究都是偏技术的,为某个问题设计了一个巧妙地算法,能够优化某一个评价指标。但是这些算法究竟如何优化了模型表现,并没有人能够说清楚。

  1. 与从原始分布学习相比,什么样的假设会使不平衡学习算法更好地工作?
  2. 应该在多大程度上平衡原始数据集?
  3. 不平衡的数据分布如何影响学习算法的计算复杂度?
  4. 在数据分布不平衡的情况下,普遍的误差范围是多少?
  5. 对于特定的算法和应用领域,是否有一种通用的理论方法可以减轻学习不平衡数据集的障碍?

需要一个标准化的评价体系

上面讲的那些基于曲线的评价指标非常重要,需要行业能够有意识的将其纳入评价指标,这样才能有助于模型的迭代比较。

增量数据上的不均衡学习

在网络监控,流媒体,网络挖掘领域,数据往往是增量到达的,在增量学习如果存在不平衡该怎么办,有以下几个问题需要思考:

  1. 如果在学习期间的中间引入不平衡,我们如何自主调整学习算法?
  2. 我们是否应该考虑在增量学习期间重新平衡数据集?如果是这样,我们怎么能做到这一点呢?
  3. 我们如何积累经验并利用这些知识自适应地改进从新数据中的学习?
  4. 当新引入的概念也不平衡时(即概念漂移的不平衡问题),我们如何处理这种情况?

半监督学习与不均衡数据集

半监督学习中,同时存在带标注和不带标注的数据,这个时候,如果存在不平衡又改如何处理,思考如下问题:

  1. 如何识别未标记的数据示例是来自平衡的还是不平衡的底层分布?
  2. 给定一个带有标签的不平衡训练数据,有哪些有效的方法来恢复未标记的数据示例?
  3. 在给定不平衡标记数据的恢复过程中(通过传统的半监督学习技术),可能会引入什么样的偏差?

参考资料

原始论文:He, H., & Garcia, E. A. (2009). Learning from imbalanced data. IEEE Transactions on knowledge and data engineering21(9), 1263-1284.

机器学习模型性能评估二:代价曲线与性能评估方法总结:https://zhuanlan.zhihu.com/p/53781144

机器学习基础(1)- ROC曲线理解:https://www.jianshu.com/p/2ca96fce7e81

adaboost.M1与adaboost.M2差别比较:https://blog.csdn.net/tyh70537/article/details/76675098

浅析trapframe与context的原理与区别

TRAPFRAME与CONTEXT的区别

在ucore操作系统中,trapframecontext是很容易混淆的两个结构,他们都会出现在线程的调度中。实际上,结构体trapframe用于切换优先级、页表目录等,而context则是用于轻量级的上下文切换。从技术上来看,两者的区别在于context仅仅能够切换普通寄存器,而trapframe可以切换包括普通寄存器、段寄存器以及少量的控制寄存器。

*在看后续内容之前,你需要提前了解汇编语言、栈、C函数调用的实现。

TRAPFRAME结构体

trapframe定义如下——

struct trapframe {
    struct pushregs tf_regs;
    uint16_t tf_gs;
    uint16_t tf_padding0;
    uint16_t tf_fs;
    uint16_t tf_padding1;
    uint16_t tf_es;
    uint16_t tf_padding2;
    uint16_t tf_ds;
    uint16_t tf_padding3;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding4;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding5;
} __attribute__((packed));

这个结构体中,依次储存了——

  • 目标寄存器
  • gs, fs, es, ds 段寄存器
  • trap_no, err 用于储存中断信息
  • eip, cs, eflags 用于储存陷阱(trap)返回后的目的地址
  • esp, ss 在权限发生变化时,用于指示新的栈的位置

有两个地方使用了trapframe,一个是中断调用,另一个是进程切换。两者对于trapframe的使用有相似之处,但也并不完全相同。

中断调用中使用TRAPFRAME

trapframe在中断中,在前期负责中断信息的储存,后期负责中断的恢复。同时,trapframe结构体是位于栈中的,其生成和使用都是通过栈的pushpop命令实现的,这将在后面详细解释。

中断发生时,下面代码,将一系列信息压到栈中。这些信息在后续的,trap(struct trapframe *tf)函数中,被对齐到了tf结构体中。

.globl __alltraps                                                                                                                  
__alltraps:                                                                                                                        
    # push registers to build a trap frame                                                                                         
    # therefore make the stack look like a struct trapframe                                                                        
    pushl %ds                                                                                                                      
    pushl %es                                                                                                                      
    pushl %fs                                                                                                                      
    pushl %gs                                                                                                                      
    pushal                                                                                                                         
                                                                                                                                   
    # load GD_KDATA into %ds and %es to set up data segments for kernel
    movl GD_KDATA, %eax     movw %ax, %ds     movw %ax, %es      # push %esp to pass a pointer to the trapframe as an argument to trap()     pushl %esp      # call trap(tf), where tf=%esp     call trap</code></pre> <!-- /wp:code -->  <!-- wp:paragraph --> 中断处理完成后,需要恢复原来的运行状态,此时,按顺序将之前push的所有信息pop出来即可。 <!-- /wp:paragraph -->  <!-- wp:code --> <pre class="wp-block-code"><code>    # call trap(tf), where tf=%esp     call trap      # pop the pushed stack pointer     popl %esp      # return falls through to trapret... .globl __trapret __trapret:     # restore registers from stack     popal      # restore %ds, %es, %fs and %gs     popl %gs     popl %fs     popl %es     popl %ds      # get rid of the trap number and error code     addl0x8, %esp
    iret

当然,倘若读者认为trapframe仅仅像这样中规中矩的实现信息的保存,那就太小看他了。我们发现,在调用call trap之后,有一句popl %esp,而后续恢复的信息完全是基于该%esp进行定位的,那么在中断处理内存中,如果我们强行修改%esp成为我们希望接下来运行的代码段的trap描述,那么经过__trapret代码恢复trapframe后,你就可以让程序跳转到任何你希望的地方。

比如下面代码就实现了内核态到用户态的切换。

    if (tf->tf_cs == KERNEL_CS) {                                                                                              
        cprintf("T_SWITH_TOU\n");                                                                                              
        userframe =  *tf;                                                                                                      
        userframe.tf_cs = USER_CS;                                                                                             
        userframe.tf_ds = USER_DS;                                                                                             
        userframe.tf_es = USER_DS;                                                                                             
        userframe.tf_ss = USER_DS;                                                                                             
        //userframe.tf_fs = USER_DS;                                                                                           
        userframe.tf_eflags |= FL_IOPL_MASK;                                                                                   
        userframe.tf_esp = (uint32_t)tf + sizeof(struct trapframe) - 8;                                                        
        *((uint32_t *)tf - 1) = (uint32_t)&userframe;                                                                     
    } 

其中*((uint32_t *)tf - 1)这个位置的值就是之后popl %esp恢复的%esp的值。

进程切换中CONTEXT的作用

context的结构体定义如下,可以看到,其中储存了所有的用户寄存器的值。

// Saved registers for kernel context switches.                                                                                    
// Don't need to save all the %fs etc. segment registers,                                                                          
// because they are constant across kernel contexts.                                                                               
// Save all the regular registers so we don't need to care                                                                         
// which are caller save, but not the return register %eax.                                                                        
// (Not saving %eax just simplifies the switching code.)                                                                           
// The layout of context must match code in switch.S.                                                                              
struct context {                                                                                                                   
    uint32_t eip;                                                                                                                  
    uint32_t esp;                                                                                                                  
    uint32_t ebx;                                                                                                                  
    uint32_t ecx;                                                                                                                  
    uint32_t edx;                                                                                                                  
    uint32_t esi;                                                                                                                  
    uint32_t edi;                                                                                                                  
    uint32_t ebp;                                                                                                                  
};                     

context结构体干的事情也很简单,可以用switch_to函数囊括,即保存一系列寄存器,并恢复一系列寄存器。在C++中,switch_to是拥有两个context结构体为参数的函数switch_to(&(prev->context), &(next->context)); ,其实现如下——

switch_to:                      # switch_to(from, to)

    # save from's registers
    movl 4(%esp), %eax          # eax points to from
    popl 0(%eax)                # save eip !popl
    movl %esp, 4(%eax)          # save esp::context of from
    movl %ebx, 8(%eax)          # save ebx::context of from
    movl %ecx, 12(%eax)         # save ecx::context of from
    movl %edx, 16(%eax)         # save edx::context of from
    movl %esi, 20(%eax)         # save esi::context of from
    movl %edi, 24(%eax)         # save edi::context of from
    movl %ebp, 28(%eax)         # save ebp::context of from

    # restore to's registers
    movl 4(%esp), %eax          # not 8(%esp): popped return address already
                                # eax now points to to
    movl 28(%eax), %ebp         # restore ebp::context of to
    movl 24(%eax), %edi         # restore edi::context of to
    movl 20(%eax), %esi         # restore esi::context of to
    movl 16(%eax), %edx         # restore edx::context of to
    movl 12(%eax), %ecx         # restore ecx::context of to
    movl 8(%eax), %ebx          # restore ebx::context of to
    movl 4(%eax), %esp          # restore esp::context of to

    pushl 0(%eax)               # push eip

    ret

进程切换中TRAPFRAME的作用

那是不是进程的切换就可以直接用switch_to函数呢?答案是否定的,因为switch_to仅仅保存、恢复了普通寄存器,无法实现优先级跳转、段寄存器修改等等。这时,就要借助trapframe了。

由于switch_to函数跳转后,将调到context.eip位置。而这个跳转我们没法完全实现进程切换,所以我们可以将其设置为一个触发二级跳转的函数,forkret

proc->context.eip = (uintptr_t)forkret;
proc->context.esp = (uintptr_t)(proc->tf);

其中,forkret定义如下(current是当前进程,也就是进程切换的目标进程),forkret不同于switch_to,它尝试使用trapframe作为进程切换的手段,而相比于contexttrapframe的功能就强大多了。

static void
forkret(void) {
    forkrets(current->tf);
}

而forkrets定义如下——

.globl __trapret
__trapret:
    # restore registers from stack
    popal

    # restore %ds, %es, %fs and %gs
    popl %gs
    popl %fs
    popl %es
    popl %ds

    # get rid of the trap number and error code
    addl $0x8, %esp
    iret

.globl forkrets
forkrets:
    # set stack to this new process's trapframe
    movl 4(%esp), %esp
    jmp __trapret

现在,又回到了中断恢复的那一段代码,而其中的逻辑也完全相同。最终,进程跳转目标进程的入口,而该入口的地址,被存放在proc->tf中。下面是kernel_threadtrapframe初始化代码,也能佐证最终调用函数入口fn被储存在了eip中。

// kernel_thread - create a kernel thread using "fn" function                                                                      
 // NOTE: the contents of temp trapframe tf will be copied to                                                                       
 //       proc->tf in do_fork-->copy_thread function                                                                                
 int                                                                                                                                
 kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {                                                                
     struct trapframe tf;                                                                                                           
     memset(&tf, 0, sizeof(struct trapframe));                                                                                      
     tf.tf_cs = KERNEL_CS;                                                                                                          
     tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;                                                                                    
     tf.tf_regs.reg_ebx = (uint32_t)fn;                                                                                             
     tf.tf_regs.reg_edx = (uint32_t)arg;                                                                                            
     tf.tf_eip = (uint32_t)kernel_thread_entry;                                                                                     
     return do_fork(clone_flags | CLONE_VM, 0, &tf);                                                                                
 }                                                                                                                                  

浅析文本摘要算法(Document Summarization)

概述

文本摘要算法,指的是在一篇文章中,摘要出核心观点的算法。主流的文本摘要算法生成一篇文章的摘要,摘要长度在3~4句话左右。

历史

在深度学习算法出现之前,人们使用了贪心算法、图算法来研究文本摘要。同时,为了衡量一段生成的摘要是否和标准摘要(gold summary)相似,学术界提出了一系列标准,这些标准现在广泛用于文本摘要算法的模型评价,其中最为常用的就是ROUGE – A Package for Automatic Evaluation of Summarieszz中提到的ROUGE-x系列算法。

深度学习提出后,LSTM/GRU作为摘要生成的强有力工具,一举打破传统算法的效果。最为主流的摘要生成模型是基于抽取式和生成式的,这两种模型将在后面详述。

随着深度学习的发展,很多其他算法也被引入。如一些文章使用强化学习,直接尝试训练一个能够获得最高ROUGE得分的模型。一些文章借助机器视觉方向的研究,优化模型结构。也有文章训练模型,判断句子相对于文章的重要性,进而间接实现摘要提取。

抽取式和生成式文本摘要

既然是摘要,那么显然,摘要中很大一部分都应该是原文中出现过的词语。同时,基于语法的考虑,也需要引入一些没有在原文中出现的词。

这时,就引出了文本摘要算法的两大学派—— 抽取式(extractive)和生成式(abstractive)。

  • extractive算法希望直接从文本中,抽出若干词语,连成一句话。词汇的抽取通常使用循环神经网络,配合注意力机制。得到“下一个词”可能是谁的概率分布。
  • abstractive算法希望从词汇表中,直接选出“下一个词”。

不论是abstractive的文本摘要,还是extractive的文本摘要,模型都由两个部分构成的,即一个编码器(encoder)和一个解码器(decoder)。

  • 对于编码器来说,通常都是将输入文本导入一个循环神经网络,生成出一个上下文特征向量c
  • 对于解码器来说,通常也是使用一个循环神经网络。以编码器生成的表征原文的上下文特征向量c,和之前生成的词汇{y_1, y_2, \dots, y_t},生成出摘要的下一个词y_t

数据集

当前研究人员多使用CNN/DailyMail作为数据集,在该数据集中,每一组数据是一个新闻稿,平均每篇文章39句话。同时还有一个“多句”的摘要。

著名论文

Get To The Point: Summarization with Pointer-Generator Networks

这篇文章提出了一个Pointer-Generator模型,既可以通过Pointer拷贝原文的文字,也可以通过Generator生成不存在原文中的文本。这两个模型通过一个开关p_{gen}进行选择——

P(w) = p_{gen} P_{vocab}(w) + (1-p_{gen})\sum_{i:w_i=w} a_i^t

其中P_{vocab}表示从词汇表中选择一个单词的概率分布,而a_i则是从原文选择第i个词汇的概率分布。

在此基础上,本文还提出了一种称之为覆盖率机制(coverage mechanism)的方式,用以解决抽取式摘要中最容易出现的内容重复的问题。

SummaRuNNer: A Recurrent Neural Network based Sequence Model for Extractive Summarization of Documents

这篇文章核心目标是仅仅是在“句子级别”进行摘要,即从原文中选择若干适合作为摘要的句子。该文章使用两层GRU,依次在“词语”级别和“句子”级别总结信息,最终获得一个可以表征全局性质的向量d。接着,再参考句子级别的特征向量s_i、全局特征向量d、以及RNN的隐状态h_i,生成对于句子的评分。

Ranking Sentences for Extractive Summarization with Reinforcement Learning

这篇文章的核心目标是给一篇文章的句子按照与主题的相关度进行排序,文章指出,在之前的方法中,通常是训练模型,使得对于每一个句子的估价尽量靠近一个指定的ground-true。但提升对于ground-true的近似并不一定能够提高模型的ROUGE评分。因此,文章提出使用强化学习的方式,直接学习句子的label,进一步最大化ROUGE评分(注意,这里ROUGE评价指标是不可导的,因此才需要用到强化学习)。

Neural Document Summarization by Jointly Learning to Score and Select Sentences

这篇文章仍然是句子级别摘要的算法,其思想借鉴了MMR算法,在MMR算法中,借助一个建立在语句集合中的评分函数r(S),迭代选择能够最大化加入后r(S')值的句子。即

g(S_i) = r(S_{t-1} \cap {S_i}) - r(S_{t-1})

g(S_i)可以看做在选择了S_{t-1}后,第i篇文章S_i的评分。使用神经网络结构去学习g(S_i)即可实现——能够参考之前选取句子集合信息的语句选择算法。

BanditSum: Extractive Summarization as a Contextual Bandit

这篇文章也是借助强化学习尝试拟合文本的ROUGE得分,并且提出了新的结构用于防止摘要倾向于前面的句子。

Bottom-Up Abstractive Summarization

这篇文章与Pointer-Generator相似,不过为了解决前文中文本拷贝倾向于拷贝整句话的bug。在输入给Pointer-Generator模型之前,先给输入的文本加了一个mask,过滤掉其中一部分,这样就导致文本不再倾向于拷贝连续的内容。

DeepChannel: Salience Estimation by Contrastive Learning for Extractive Document Summarization

这篇文章训练模型,拟合P(D|S),即给定摘要S,能够恢复原文D的概率。而函数P(D|S)的训练,可以借助文章D,摘要S,一句不重要的话S_2这三部分进行训练。生成P(D|S)后,再使用贪心算法构造摘要集合。

Recurrent Attention Network on Memory for Aspect Sentiment Analysis 阅读笔记

原文链接:[pdf-embedder url=”https://mhy12345.xyz/wp-content/uploads/2018/09/Recurrent-Attention-Network-on-Memory-for-Aspect-Sentiment-Analysis.pdf” title=”Recurrent Attention Network on Memory for Aspect Sentiment Analysis” download=”on”]

Abstract

文章提出了一个基于神经网络的,提取“关键词的情感倾向”的模型,拥有如下特点:

  • 创造了一种称之为“加权记忆(weighted-memory)”的机制
  • 使用GRU实现注意力(attention)

Introduction

提出问题

“I bought a mobile phone, its camera is wonderful but the battery life is short”

这一部分,以一个句子的情感分析为例进行分析。在分析中,我们需要对于每一个关键词(target),分析其情感语义,比如camera对应wonderful。选取最近情感词是通常手段,但是显然这种手段会在某些精心构造的句子中失效,比如下面这句话蕴含了中性情感而非消极情感。

“Its camera is not wonderful enough.”

针对上述问题,TD-LSTM是一个解决方案,这种解决方案也有一个缺点,就是特征的传递是逐词的,这在长句子中,当目标(target)与特征词(feature word)相距很远时,又会出现问题。进一步,注意力机制被引入,已表征特征重要性。然而,当实际的注意力点较多时,这种机制的表现也不太好。

“Except Patrick, all other actors don’t play well”

上述的问题便是这片文章准备解决的东西。

引入模型

模型层次结构依次为——

  • 一个双向LSTM生成一系列“记忆片(memory slice)”
  • 所有的内存片按照距离目标词(target)的相对距离加权,使得句子里不同的目标词拥有不同的特征向量
  • 在生成的加权记忆片中,使用注意力机制合并,这里使用的是循环层GRU

在本文中,就如何组合不同的注意力这个问题,提出了新的解决方案。从某一个方面来看,比较像一个普通人的认知——最初看到句子的最开头,然后在继续阅读的过程中不停“注意到”知识,并在最后将注意力集中的几个语言拼接。

对于Introduction中的最后一句话,我们通常会先看到“Except”,接着被“don’t play well”吸引,最终对于“Patrick”生成一种积极的情感。在本文之前,多数文章提出的结构都无法解决多注意力的问题。而我们提出结构中的GRU曾可以很好的解决。

Related Work

对于特定实体的感情分类问题,有很多传统做法基于规则、统计概率,这些做法不是有繁琐的模型构造,就是需要依赖很多额外的语法信息。

这时神经网络就可以发挥作用了~神经网络本身曾被用在语法分析,句子整体情感分析,诸如有名的递归神经网络(Recursive NN)。然而,递归神经网络在语法分析低效的非标准文本(比如推特评论等短文本)中效果不好。

对于指定目标的情感分析,曾经有人提到过TD_LSTM算法,这个算法将需要的目标词放在中间,从两边分别使用LSTM传递信息。这种做法在长句子中效果会大幅减弱,因为很远的情感词必须经过非常多层才能到达终点。

最后,神经图灵机在2014年被提出,其中定义的注意力机制被证明在很多地方适用。其创新之处是引入了外部储存,大大提高了神经网络的能力!从某种方面来说,本文就是在这个模型基础上修改而成的。

Our Model

右图是文章提出模型的结构。

在输入层,所有输入的文本都通过经典的wordtovec算法,将每个词压缩为一个d维向量。

接下来,使用了双向LSTM神经网络(BLSTM)提取每一个词的“记忆信息” u_t,实际上,这种实现方式就是普通的bi-directional-lstm。

接下来,对于不同的位置,有一个二次加权,成为“加权记忆”(weighted memory),加权的意义不太清楚,可能使得较远的信息更容易传播吧。具体来说,文中的加权含义将以中心词的两端t_{max}距离的词,按照距离中心的距离线性加权拼接在一起。

最后,文章使用GRU层将加权记忆再“捣鼓”一番,这里的“捣鼓”是指循环N词,每次通过上一次“捣鼓”的记忆e_{t-1},以及整个“加权记忆”得到第t个“注意力”的加权矩阵,进而通过GRU的形式更新e_t,关于选择GRU模型的原因,文章解释说因为GRU的参数较少。

Experiments

表现优于传统模型

Conclusions and Future Work

在这一部分,作者谈到了选择固定个注意力(Attention)显得有些冗余,在未来的工作中会考虑自适应注意力个数能够得到更好的结果。

点评

在Introduction模块,文章点出了在NLP领域,各种算法面临的共同问题,这种归纳确实很有意思。关于这类模型共同的要点罗列如下——

  • 如何将单词编码,至少本文还是用的经典算法
  • 如何解决远距离传输问题,本文使用weighted-memory机制
  • 如何在不增加太多参数的条件下,增加模型的“深度”,对应了本文中多注意力机制
  • 如何尽量在模型的选择上减少训练参数,对应本文的GRU选取

这篇文章中Related Work里面提到的神经图灵机感觉会很有意思,之后可以找一找相关的论文阅读一下,虽然在NLP方面感觉有些束手束脚,但是在其他领域可能会有很大的作为。

对于本文提到的模型,却是可以看出是仿照人类对于句子阅读的认知,每一个步骤都可以通过人类阅读的认知来解释,不过这种仿照是否能够带来很好的效果就不太好说了。至少文章写的是效果很好,那就姑且相信吧。

由于读的比较粗,关于每一层输出的具体维数还是有点晕,可能也有作者没有表述清楚的锅。

A Hierarchical Neural Autoencoder for Paragraphs and Documents

论文链接:A Hierarchical Neural Autoencoder for Paragraphs and Documents

这篇文章的核心目标是:输入一个文段,通过神经网络,将该文段压缩为一个低维特征向量,尽可能的记住尽量多的东西,再通过神经网络,将低维特征向量映射回原文段。整个模型就是一个自编码器(Autoencoder)。

其中,模型输入的文段是一个包含若干句话的文段,其中每句话又包含若干单词,单词可以用词向量算法转化为向量表示。模型运用了LSTM模型以及Autoencoder模型的思想,在这里就不赘述了。

paper提出的模型有三个,都是从LSTM出发改良而成的,分别是:基础LSTM,带有层次信息的LSTM,带有层次信息和注意力机制的LSTM。这三种模型的流程图如下:

第一个模型就是将一个LSTM的模型的尾部接到第二个LSTM模型的头部完成的。显然,由于LSTM本身对于信息的承载量优先,而一篇文章通常由上千个单词组成,完全无法指望LSTM能够提取出太多有用的信息。

第二个模型,增添了层次结构,其设计初衷就是为了解决第一个模型的不足之处:单词本身携带的信息太少了,要让模型从一篇文章中定位到一个关键词太过复杂。解决方式是在“文段”和“单词”之间增添一个过渡桥梁,即“句子”。通过一个LSTM从句子中提取出一个特征向量,对于每个句子提出的特征向量,我们再通过另一层LSTM提取出文段的特征向量。

第三个模型就比较玄学了。可以感性理解其优于第二个模型的地方。即,由于LSTM每次只提取最后一个Cell的输出,等同于默认了最后一个Cell的输入,即最后一个词是最重要的,这与实际不符。因此对于压缩器LSTM的所有节点,同时增加一个判别器D,可以通过该节点本身的输出与最终编码器总结出来的特征向量,求出一个类似于相关程度的量v。实际上解码器所获得的输入,应该是每个Cell的v值通过类softmax的函数进行加权求和得到的。用这样的特征向量替代之前的特征向量,等于说将重要的东西变得更重要了。

总之,这篇文章里面的内容其实挺基础的,LSTM本身是15年发明出来的东西,在现在已经有3年的时间了,很多特性已经被挖掘出来,Autoencoder思想则更早。也就是说时效性可能已经过了。

不过算法本身非常的general,可以套用到NLP中的很多地方,我们需要做的还有实现词向量算法。

无锁数据结构设计 之 详解C++内存顺序(Memory Order)


内存顺序概述

内存顺序,这是一个很大很大很大的坑,在介绍atomic原子类型的时候,就已经提及过,但是由于本身概念理解起来非常困难,所以没有细讲。现在就让我们仔细看看这是什么一个神奇的东西吧。

先通过一系列简单的代码片段,看一看内存顺序是如何定义的:

std::atomic<bool> x;
x.store(true,std::memory_order_seq_cst);
std::atomic<bool> flag = ATOMIC_VAR_INIT(false);

bool expected = false;
while(!flag.compare_exchange_strong(expected, true, std::memory_order_acquire))
    expected = false;
flag.store(false, std::memory_order_release);

可见,memory_order一般情况下是加在有内存操作的函数(如store、load等)后面,比如上面程序中的std::memory_order_release ,特别的由于函数compare_exchange_weak在失败、成功之后存在两种不同的内存操作策略,因此它可以传入两个memory_order分别指示成功(success)和失败(failure)后不同的操作策略:

bool compare_exchange_weak (T& expected, T val,
           memory_order success, memory_order failure) noexcept;

 

内存顺序原理

好了,废话不多说,为了让读者理解内存顺序,我们将分别解释内存顺序、操作可见性等概念

内存顺序,顾名思义,是由于内存操作重排带来的不确定性。

CPU中的缓存机制曾经大幅提高了内存访问速度,这个机制将内存中经常访问的区域拷贝到了缓存中以加快速度。这种策略使得内存的读写的目标不一定是内存中的值,而是有可能仅仅是该值在缓存中的一个副本。

在单核处理器下,并不会出现任何问题,毕竟所有线程的缓存是共用的,也就是说不存在缓存同步的问题。在多核的情况下,问题就会比较复杂了,每一个核都有自己独立的L1缓存,若两个核共享内存,就需要解决缓存同步的问题。内存重排就是处理器(编译器)设计者为了平衡缓存同步的时间开销,和程序不稳定性之后得到的一个较好的解决方式。

不仅仅缓存会导致内存操作的重排,编译器也可能为了优化速度重排操作,当然,这些重排也是建立在不影响单线程程序正确性的情况下。不过,编译器的优化非常好处理,在解决好处理器优化后,编译器优化自然而然可以解决,因此我们这里就不深入讨论。

【注:在 之前的文章 中,我曾介绍过内存顺序可以用多人写作的版本控制来理解,单独线程的本地修改对于自身来说是一定有序的,但是这些修改要传递到远程的代码库中,则是一个可能发生顺序交换的不确定事件。  】

#include <atomic>
#include <thread>
#include <assert.h>
std::atomic<bool> x,y;
std::atomic<int> z;
void write_x_then_y()
{
    x.store(true,std::memory_order_relaxed);
    y.store(true,std::memory_order_relaxed);
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_relaxed));
    if(x.load(std::memory_order_relaxed))
        ++z;
}
int main() {
    x=false;
    y=false;
    z=0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load()!=0);
}

以上面的程序为例子:函数write_x_then_y 依次写了变量x和y,而函数read_y_then_x 在确认变量y已经被写之后读入x。从常理上来说,此时z++ 是一定会被执行的。但是从运行结果上来看,assert可能被触发!

假设编译器没有优化汇编层面x和y的写入次序。实际上,是由于缓存机制,导致不同变量在其他线程看来更新的顺序是不同的。这就是内存顺序所刻画的问题。其中,本程序中,x的赋值操作可能不会被其他线程所看到,这就是所谓的不可见

从可见性方面重新叙述内存顺序的问题——一个线程的内存操作对于其他线程来说是不可见的。一种可能的情况是:

  • 线程A:写x,写y
  • 线程B:发现x先于y被赋值
  • 线程C:发现y先于x被赋值

联想之前说的缓存机制,确实会是这样的。

所以内存顺序memory_order是什么呢,memory_order是编译器指定常规的非原子内存访问如何围绕原子操作排序。

初步理解内存顺序

下面是我对于内存顺序的理解,由于在x8-64的机器上,内存顺序的问题本身不容易触发,所以下面的所有解释都没有经过验证,但是是我通过阅读网络上各种“不靠谱”的文献之后,经过自己筛选总结出的一套可信的解释。

memory_order_acquire & memory_order_release

在各种资料中,这两个内存顺序标记都是组合使用的,一个比较直观的理解是:线程A的release标记写操作W_A和线程B的acquire标记读操作R_B组合,可以达到:

  1. 线程A中的所有W_A之前的写操作,相对于W_A对齐,也就是说W_A操作完成后,线程A所有写操作完成
  2. 线程B中的所有R_B之后的读操作,相对于R_B对齐,也就是说R_A操作开始时,线程B的所有读操作尚未开始
  3. 线程A的W_A在线程B的R_B之前读入

综合上面三条性质,我们发现,acquire-release操作成功将线程A和线程B分割开来。

memory_order_relaxed

不进行内存顺序限制,即对于某一条语句,倘若运用了memory_order_relaxed标记,则其储存顺序对于其他线程不可见。那么什么时候使用这个标记呢?

既然acquire-release通过标记线程A的最后一个写操作,和线程B的第一个读操作,实现了线程的顺序要求,那么除了这两个操作之外的其他操作,实际上是可以直接用memory_order_relaxed的

无锁数据结构设计 之 通过atomic实现自旋锁

这是mhy12345的无锁数据结构教程的第二篇,通过atomic<bool>实现自旋锁。对,你没有听错,用无锁数据结构实现一个锁 >_<

自旋锁,顾名思义,通过自旋来实现线程加锁的工具。一个最简单的demo如下

bool flag = false;
 
void func()
{
    while (!flag);
    flag = true;
    //TODO1
    flag = false;
    //TODO2
}

看起来这是一个很机智的做法。程序进入时将一个共享bool变量赋值为true,而在另一个程序准备进入时,检查到该bool变量已经为true了,就放弃进入,开始用while语句自旋。

自旋锁流程
自旋锁流程

不过对于一个多线程程序,其他线程可以在任意位置接入,比如这个程序的第4行和第5行不是一个原子操作,倘若这个时候恰好另一个线程获得了控制权,读取到flag值为false,继续执行,但是在释放flag之前控制权有转会了第一个线程,由于第一个线程已经执行了取值操作,也默认flag为false,继续执行,导致受保护数据被重复访问。产生问题。

这时候,一个非常自然的想法就是:我们能不能把对flag的操作换成原子数据类型操作呢?答案是肯定的!

std::atomic<bool> flag = ATOMIC_VAR_INIT(false);

void func()
{
    bool expected = false;
    while(!flag.compare_exchange_weak(expected, true, std::memory_order_acquire))
        expected = false;
    //TODO1
    flag.store(false, std::memory_order_release);
}

当程序执行到第六行时,准备进入临界区//TODO ,首先判断flag是否为false,如果不是,说明已经有一个程序在临界区中间了。否则将flag赋值为true,自己进入临界区。

一点细节是,如果进入临界区失败,则true值会被赋予expected,这是我们需要在while语句中恢复expected的值。

memory_order是什么呢?请看:无锁数据结构设计 之 详解C++内存顺序(Memory Order)

 

参考资料:

https://blog.poxiao.me/p/spinlock-implementation-in-cpp11/

http://blog.csdn.net/yockie/article/details/8838661

 

无锁数据结构设计 之 原子数据类型Atomic介绍

  • 这是mhy12345的无锁数据结构教程的第一篇,原子数据类型介绍。在阅读这篇文章之前,先安利一本这方面叙述非常详细的书《C++并发编程实战》(C++ Concurrency IN ACTION)
  • 想要详细了解无锁编程可移步无锁编程教程,里面从原理上介绍了atomic类型。

原子操作,即不可分割的操作,这样的操作在观察者看来,要不然就做完了,要不然就没有做完。原子操作本身是数据库中的一个概念,举一个例子,“在数据库中删除name为mhy12345的数据项,并且添加一个myh54321的数据项”对应了一个用户改名操作。这种操作如果从中间断开,只完成了一半,会产生灾难性后果。

为了使得我们数据结构能在多线程环境下安全运行,并且尽量不使用锁mutex(时间开销太大),原子数据类型就成了最佳选择方案。C++11提供了一系列原子数据类型,包含在头文件<atomic>里面,我们首先介绍原子数据类型的模板std::atomic<T> a ,这是一个泛类型模板,支持极少数原子操作——

a.load();//获得a的值
a.store(x);//将新值存在a里面
a.exchange(x);//将x的值存入a,并返回原来的值
a.compare_exchange_weak(x,y);//将a的值与x比较,如果相等则将y存在a里面,否则将x的值变为a内部储存的值,返回是否储存成功
a.compare_excahnge_strong(x,y);//基本同上
a = <non-atomic-instance-of-T>; //等同于store

对于上述的原子操作函数,我们可以理解为函数的调用不会由于进程调度而被切断。例如其中的compare_excahnge_strong(x,y) 函数,在单线程情况下,等同于一个if语句——

//将a的值与x比较,如果相等则将y存在a里面,否则将x的值变为a内部储存的值,返回是否储存成功
if (a == x) {
    a = y;
    return true;
}else {
    x = a;
    return false;
}

在多线程情况下,该if语句是可以被进程调度切断,这在某些情况下是我们不希望发生的,而这时,我们可以将这个语句用compare_excahnge_strong 实现。

每一种操作还有一个内存顺序参数memory_order可以选择,这方面内容将在无锁数据结构设计 之 详解C++内存顺序(Memory Order)中介绍。不过,现在,我们可以直接忽略参数中所有memory_order相关项。

接下来,我们将详细介绍这几个函数——

void store( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
void store( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;

T load( std::memory_order order = std::memory_order_seq_cst ) const noexcept;
T load( std::memory_order order = std::memory_order_seq_cst ) const volatile noexcept;

T operator=( T desired ) noexcept;
T operator=( T desired ) volatile noexcept;

前三个函数并不需要太详细的讲解,因为赋值、读取操作本身在我们的理解中就已经不可分割了,实际上,在当今大多数处理器上,即使一个普通的int的读写也都是原子的。

T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;
/*Atomically replaces the underlying value with desired. The operation is    read-modify-write operation. Memory is affected according to the value of order.*/

exchange(x)在我学习期间基本没有看到过使用,不过含义也非常简单:将desired储存,返回是原来的值。本质就是一个数据交换的方式。

bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order success, 
                            std::memory_order failure ) noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order success, 
                            std::memory_order failure ) volatile noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order order =
                                std::memory_order_seq_cst ) noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order order =
                                std::memory_order_seq_cst ) volatile noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order success, 
                              std::memory_order failure ) noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order success, 
                              std::memory_order failure ) volatile noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order order = 
                                  std::memory_order_seq_cst ) noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order order = 
                                  std::memory_order_seq_cst ) volatile noexcept;
/*Atomically compares the object representation of this with the object representation of expected, as if by std::memcmp, and if those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in this into expected (performs load operation). */

定义很多,只用看第一条定义就好了,将变量的值与expected比较,如果相等就用desired更新,返回true,否则返回false,将变量的值放在expected里面。其等价的伪代码在前文已经写过了。

也许读者会问:这个函数看起来非常奇怪,真的在实际工程中会用吗?其实,这两个函数才是atomic的精粹所在!

无论是互斥锁实现,还是无锁栈,无锁队列的实现,都需要用到这些函数。具体细节可以移步 无锁数据结构设计 之 通过atomic实现自旋锁

看了这些文章,可能又有了新的疑惑,我怎么没看出来compare_exchange_strong 和compare_exchange_weak 有什么区别?

其实答案很简单,compare_exchange_weak 可以理解为compare_exchange_strong 的一个有bug,但是更加高效的实现——

在一些特殊情况下,即使expected和变量的值是相同的,也有可能返回false,不过这样一个bug对于最常见的情况:将函数放在一个while循环中并不会产生影响,下面是一个典型的compare_exchange_weak 放在while循环中的例子。在该例子中,如果少数情况条件判断将本应返回true的情况判断成了false,也并不会导致什么问题(只是多执行一遍while循环罢了)

expected = count.load();
desired = expected+1
while(!count.compare_exchange_weak(expected,desired)) {
    desired = expected + 1;
}

所以说如果我们并没有意图通过函数返回值判断是否expected与变量的值确实不同,或者对于错误有容许度,我们完全可以用weak替换strong。

 

参考资料:

Cplusplus reference:http://en.cppreference.com/w/cpp/atomic/atomic