精华内容
下载资源
问答
  • 对于《编程美》上没有提供答案提示的1.184.11两节,本文将综合网络上有的部分资料,深入挖掘解题思路,并对目前尚未找到满意答案的1.18节问题2给出算法解答。阅读本文需要了解古典概型(百度/维基)组合数...

      对于《编程之美》上没有提供答案和提示的1.18和4.11两节,本文将综合网络上已有的部分资料,深入挖掘解题思路,并对目前尚未找到满意答案的1.18节问题2给出算法解答。阅读本文需要了解古典概型(百度/维基)和组合数(百度/维基)的含义,以及扫雷游戏中的各种符号。

      《编程之美》上关于扫雷的概率有两道题:1.18挖雷游戏和4.11扫雷游戏的概率。后者在网上已经有了令人满意的解答,前者我还没发现,相关内容也很少。经过近一天的研究,提出了一个自己的解法。这篇博文的写作过程,同时也是我整理思路的过程。可能有的读者还没有看过这两道题,或者看了之后记不大清楚了,先把两个问题贴在下面:

    1.18 挖雷游戏

    问题1:如果想给游戏增加一个功能键,点击就能查看剩余所有未标识的方块是否有地雷的概率。如何实现?

    问题2:如果上一个问题太难了,可以先让程序先标识所有有地雷的方块。

    4.11 扫雷游戏的概率

          

    在一个16*16的地雷阵中,有40个地雷。用户点击了两下,出现如图4-21的局面。分析图4-22所示的这个局部。

    问题1:当游戏中有40个地雷没有发现时,A、B、C三个方块有地雷的概率(P(A),P(B),P(C))各是多少?

    问题2:这个局面共有16*16=256个方块,P(A)、P(B)、P(C)的相互大小关系和当前局面中总雷数有关系么?比如从10个逐渐变化到240个,三者曲线如何变化、会不会相交?(建议用Matlab做解)

      1.18节的问题2比较好解,而且可以同时标记必然没有地雷的方块;但问题1就困难了,暂且放一边;读了4.11节之后,会发现解4.11节的方法是可以用来理解1.18节的问题的。本文的主要方法就是使用网络上对4.11节提供的解法和1.18节问题2的辅助功能,来完成问题1的解答。

      先要明确地强调一点,1.18节的问题1、2与一些所谓的自动扫雷算法是不同的:对于确定为无雷的方块,并不做点击动作;也即仅作概率分析,而不实际地翻开来确认并获得更多信息。因此,有的自动扫雷算法可能每次并不是选择无雷概率最大的方块,包含了一些启发式的尝试。而这里将会对当前状态所有方块是否有雷的概率进行分析。比如http://www.verydemo.com/demo_c173_i10167.html,我觉得这就是个似是而非的自动扫雷解法,要保持当前状态来标注概率,又没让你挖开看看,你知道的太多了,不对,应该是你做的太过火了。

      为了便于阅读,我将一些定义(包括我自己的定义)做成了锚点,如果阅读时忘记了前面的含义可以点击链接来查看。

      这里先引入“8邻接”的定义。这个定义来源于图形学,如下图,像素P周围的这8个像素就是P的8邻接像素。对应于扫雷问题,同样的可以对一个方块定义它的8邻接方块。

    分析:

      待标识概率的方块可以根据是否与已经标识的方块是8邻接的分为两种,如果是,称之为“邻接方块”,反之则是“非邻接方块”。前者可以按照已标识的方块提供的信息来辅助判断,后者只能取平均概率。对应于原书的例图,“邻接方块”是两条黑线之间、既未挖开也未标记为有地雷的方块:

      对于这两种方块,其有地雷的概率计算方法是不一样的,下面会逐一分析。

      为了简化原图,同时解答1.18节问题1,先对必然有雷(即P(此方块有雷)=1)和必然无雷(即P(此方块有雷)=0)的方块进行标识,并且把用旗子标识为“有雷”的地区当作已知是有雷的方块。步骤如下:

    (1)(去掉插旗子的方块)把这张图中已经标识为有雷的区域周围8个邻接区域计数减1,并把标识为雷的区域的雷挖掉。同时,对于从1减为0的方块,还要把它8邻接的所有未标识方块标为无雷。这个操作在解问题2之后可以用来进一步转化,从而解决问题1。

    等价转化如下图,其中红色方块是经过转化的区域,红色方块且不含数字的标识此方块已无可用信息。具体来说它是由三种方块转化而来:

    原先标有数字的,此时它的8邻接区域雷已排完;

    原先是雷的,将其有雷概率标记为1;

    原先无雷的,将其有雷概率标记为0。

    注意:它是一种新的已标识方块,而不是是否有雷未确定的未标识方块。

    (2)(标记必有雷和必无雷的方块)对所有不为0的区域,先计算周围方块必有雷的方块。判断规则:标为“x”的方块如果有x个8邻接的未标识方块,那么必有雷。同时,由于这是由逻辑判断得出的必有雷的区域,不是先前插上旗的,游戏剩余雷数计数器没有变化,需要记录推理出的雷数,并在剩余雷数中减去。

    (3)重复(1)(2)的转化,直到标识完毕。在这个过程中,所有地雷概率为0和1的邻接方块已经被处理且标记,问题2得到求解。上图转化为:

    并且,在这个过程中标记P(此块有雷)=1的方块一共10个,加上之前扫出的3个,那么40个雷还剩下27个。

    这里再次强调,虽然有的方块在处理中标记为P(此块有雷)=0,即必然无雷,但这只是逻辑推理,并不代表我们真的点开了这个方块,它实际的数字是未知的,本身并不能提供周围8邻接的雷数信息,只能间接地提示它的8邻接方块的8邻接中少了一颗雷而已。

    (4)接下来是处理最后一部分,也即P(此方块有雷)非0非1的部分。这里借鉴了一个解答《编程之美》问题4.11思路,原内容来自任晓祎的博文,但是这个页面我是打不开的,好在转载的人多,比如这里。另外还有一篇从一般情况入手的博文可以参考。

    先简单阐述一下其思想。(如果这部分没看懂没关系,看懂上面链接的两篇就可以理解后面的思路):

      “子雷区”定义为所有已知信息方块的8邻接中所有未挖开未标记方块以及这些已知信息方块的并集,例如以下几个图中的子雷区是黑框标出的部分,也是我在上面两条黑线包围的部分中未挖开未标记的部分。可见,“子雷区”和“邻接方块”是类似的,只不过"子雷区"描述的是这些方块的总体外加一些已知信息,"邻接方块"描述的是个体。下面你会看到使用这个定义的方便之处。

    思想:

      对于M大小的雷区,其中共有N个雷;已知信息和待判断位置位于一个M'大小的子雷区,先分析子雷区一共可能有多少个雷;对于每一种雷数,分析其分布的情况总数,在乘以余下的雷在子雷区之外的分布情况,其和就是所有的分布情况。待判断位置有雷的概率是它在这些情况中有雷的情况数/所有分布情况(根据古典概型),写成公式如下:

    现在继续处理(4)中获得的子雷区。标记“?”的定义为“结合点”,对它讨论可以把一个复杂的子雷区分成多个简单的子雷区。比较巧合的是,《编程之美》1.18这个图,先假设再分情况讨论时会发现有种情况是不成立的,另一种情况只有唯一的可能:

    这里举一个和上文图不同的例子说明子雷区分别求解的过程。先做出“结合点无雷”假设的假设后,把子雷区分为这样两个不相交的子雷区

    这时,要求解A处有雷的概率就稍微简单了些。与单独求解一个区域中点是否有雷的概率相比,这些子雷区之间的关系是:

    所有子雷区的雷数+非子雷区的雷数+已确定是雷的雷数 = 总雷数。

      利用从上述两篇博文中获得的思路,分析如下(这部分的公式是在Word里打的,HTML编辑器玩的不熟,直接截了个图粘上来):

    对于不在任何一个子雷区的其余所有点,取任一个点X进行分析:

    如果结合点分情况讨论,那么计算方法类似,可以表示为:

    这样,对于原图中所有点是否有雷的概率,都能给出了。

      这下所有点的概率都能求了,似乎1.18节问题1也能解决了。对(1)(2)(3)这三步是这样的,维护好包含有用信息的方块和邻接方块的数据结构,这么标出来所有P=0和P=1的方块是不难的,然而第 (4)步就犯难了:如何把子雷区划分成多个子雷区结合点怎么找?

      先回避这个问题,让计算机扬长避短,直接在未划分的子雷区搜索所有可能的地雷分布情况数,并统计在特定位置有雷的情况数,概率也就能算出来了。这时的子雷区已经很小了,处理起来不会很慢,不过要注意不能忽略子雷区以外的非邻接方块中地雷的分布情况。

      如果非要直面这个问题,让计算机像人一样找结合点、划分子雷区、按结合点分情况计数当然也可以,但是编码难度大,计算也未必快。可以注意到,与含有信息的已挖开方块相连的邻接方块其实最多只有一层,并且是一条直线。如果一个含有信息的已挖开方块与两层邻接方块相连,那么相连的地方就是待讨论的点,如下图所示,红色和蓝色是两条邻接方块的一层,紫色是邻接点。接下来就是像人一样分情况讨论了,但由于实际划分很复杂,而且这个所谓的讨论其实还是让计算机去进行可能情况的搜索,可能性能还不如上面的直接去搜索快一些。另外,我这里给出的规律是自己总结的,不确定是否有疏漏,可靠性有限。

    具体的编码就略过了,主要过程是简化原图+搜索算法。按照(1)~(4)步,完全可以写出伪代码框架。

    另外预先设计了几个FAQ,当然各位看官如果有什么问题,不要吝惜留言啊!

    Q:1.18节标题是“挖雷游戏”,4.11节标题成了“扫雷游戏”,居然不一样!

    A:其实这也是我想吐槽的地方:前后不一致,《编程之美》里可是不少,从代码的语言到这小小的标题。

    Q:既然有的方块是否有雷能直接判断出来,为什么不挖开从而获得更多信息?

    A:这个问题我在正文里强调了两遍了,直接点击这个链接跳转过去再读一遍吧。

    Q:在4.11中,按3*5区域中有3个雷还是2个雷进行了分情况计数。为什么不用全概率公式(百度/维基)?

    A:P(A)=P(A|B1)*P(B1) + P(A|B2)*P(B2) + ... + P(A|Bn)*P(Bn),A={A点有雷的概率},Bi={3*5区域中有i个雷的概率},

      嗯,看上去很清楚,P(A|Bi)是容易计算了。但是P(Bi)你怎么获得?

    Q:为什么对一些定义提供了两个链接?

    A:事实上我觉得文中出现的几个定义,百度百科比维基百科阐述的清楚一些。当然有的人不喜欢百度,为了照顾他们的情绪我把维基百科中的定义也附上了。

    Q:分析了大半天,最后还是用搜索的方法,真失望。

    A:是啊,我也有点失望。但我已经尽力剪枝了,剪到步骤(4) 才权衡是更精细的剪枝开销大还是从这里开始搜索开销大。毕竟结合点的情况太多了,没有进行很简单的抽象。这还是比一开始就搜索要好很多了吧?

    Q:我需要的是源代码……

    A:其实我可以直截了当地告诉你,博主在windows编程方面非常之poor,以至于现阶段是不可能给你写出源代码的。自己努力吧!当然,如果你搞定了,记得把源码发给我一份^ ^

    Q:任晓祎的博文打不开,那些转载里的图片也看不了,更不会用MATLAB,可还是想看看4.11的三条曲线。

    A:这个希望还是能满足的。不过注意到由于地雷数N是离散的,实际上绘出来的是散点图,如下:

    我甚至把MATLAB代码都给你了,直接粘到m文件里就能重现这个图像:

     n = 10:1:240;
     m = 256;
     %P(A)
     p1 = (2*n -4)./(3*m+7*n-56);
     plot(n,p1,'r')
     hold on
     %P(B)
     p2 = (n -2)./(10*m-7*n-126);
     plot(n,p2,'g')
     hold on
     %P(C)
     p3 = (20*m -17*n-246)./(50*m - 35*n - 570);
     plot(n,p3,'b')
     legend('P(A)','P(B)','P(C)')

    不过要注意的是,在图像中,P(B)看上去与P(A)和P(C)相交,但真的是这样么?别忘了这三条其实不是连续的曲线,而是离散的点的连线。

    令P(A) = P(B),解得N1 = 2,N2 = 4196/21,都不是10至240之间的整数,所以P(A)和P(B)其实没有公共点。

    再看看P(B)和P(C),这里解方程比较复杂,直接把图像放大了看,交点似乎是221。带入P(B)和P(C)的表达式,二者不相等,只是很近似。

    结论是曲线看上去是相交的,但实际上并没有公共点。怎么样,没有被你的眼睛欺骗吧?

    Q:博主,你的XX式子中的XX算错了/扫雷图中XX格分析错了。

    A:本文中所有式子和图形标记我都进行了两遍计算/检查了两遍,虽然仍有可能有遗漏的地方,不过也请您先验证一下自己的论断吧,如果确实有错我会改正的。

    展开全文
  • 在上一篇笔者有提到,平台不一定都提供货到付款服务,因此京东、唯品会亚马逊在提交订单时需要选择支付方式,而淘宝天猫则是在...在三个状态,买家都可以取消订单,发货的订单买家可以直接取消,发货的订单需
  • 设计模式状态模式

    2021-06-09 14:46:55
    在一些平台,比如淘宝订单,经常会有不同的状态,拍下付款,拍下付款,发货,发货等等,那么,代码如何实现? 一般思路 一般思路来说,就是设定一些值来表示状态,然后通过if、else来判断,然后依次...

    应用场景分析

    在一些平台中,比如淘宝订单中,经常会有不同的状态,已拍下未付款,拍下已付款,未发货,已发货等等,那么,代码中如何实现?
    一般思路
    一般思路来说,就是设定一些值来表示状态,然后通过if、else来判断,然后依次比对。但是,如果代码已经写好了,现在业务扩展,需要添加新状态,怎么办?是不是就要改变之前写好的代码了?在if、else中添加新逻辑,这样的话,就违反开闭原则了。
    状态模式
    用状态模式,就是利用接口和抽象类的抽象功能,有一个状态的统一接口,然后,所有的具体状态实现接口,并具体实现不同方法。这样,当需要添加状态时,就只需要新实现一个子类就行了,不需要对之前的代码进行修改,符合开闭原则。

    状态模式

    在状态模式(State Pattern)中,类的行为是基于它的状态改变的。这种类型的设计模式属于行为型模式。

    在状态模式中,我们创建表示各种状态的对象和一个行为随着状态对象改变而改变的 context 对象。

    关键代码:通常命令模式的接口中只有一个方法。而状态模式的接口中有一个或者多个方法。而且,状态模式的实现类的方法,一般返回值,或者是改变实例变量的值。也就是说,状态模式一般和对象的状态有关。实现类的方法有不同的功能,覆盖接口中的方法。状态模式和命令模式一样,也可以用于消除 if…else 等条件选择语句。

    展开全文
  • 世纪星进销存2002年正式推出,一般软件不同的是世纪星进销存软件的开发人员直接...7、发票管理可以独立使用也可与采购、销售结合使用,提供发票汇总、发票明细、开票采购单及销售单一览、开票结算等报表
  • Android自定义View系列进度指示控件

    千次阅读 2015-10-18 11:21:07
    今天为大家介绍另一个自定义View——进度指示器,这个在电商App支付宝等经常遇到。如在电商App买一个东西会有如下步骤: 下订单——>支付完成——>发货——>交易完成 先使用我们的自定义View来展示一下...

    我开通微信公众号啦,如果大家喜欢我的文章,欢迎大家关注我的微信号,我会定期为大家推送Android中的热门知识。
    二维码

    今天为大家介绍另一个自定义View——进度指示器,这个在电商App和支付宝等中经常遇到。如在电商App中买一个东西会有如下步骤:
    下订单——>支付完成——>已发货——>交易完成
    先使用我们的自定义View来展示一下上面的步骤吧
    这里写图片描述

    如上图所示,步骤未完成时是灰色(可指定),当步骤完成时显示成绿色(可指定),并且最后一个完成的任务有光晕效果。
    同样,我们看看这个自定义View是如何实现的吧。
    由于需要自定义 “完成颜色”和“未完成颜色”等属性,所以我们需要定义如下属性:

    <?xml version="1.0" encoding="utf-8"?>
    <resources>
        <declare-styleable name="StepView">
            <attr name="lineheight" format="dimension"></attr>
            <attr name="smallradius" format="dimension"></attr>
            <attr name="largeradius" format="dimension"></attr>
            <attr name="undonecolor" format="color"></attr>
            <attr name="donecolor" format="color"></attr>
            <attr name="totalstep" format="integer"></attr>
            <attr name="completestep" format="integer"></attr>
        </declare-styleable>
    </resources>
    

    这些属性的意义如下:
    lineheight :表示指示器中线条的高度
    smallradius:表示指示器中圆点的半径
    undonecolor:表示没有完成的步骤的颜色
    donecolor:表示已经完成步骤的颜色
    totalstep:表示总步骤数
    completestep:表示已经完成的步骤

    如果你还需要自定义其他属性,也可以在这里自行添加。
    接下来我们看看代码的实现吧,我们分两部分实现:
    1、StepBar部分,这部分主要用来显示进度条部分
    2、SetpView部分,这部分主要依赖StepBar完成titile显示

    在Android目前存在的View中,没有具备类似功能的View,所以我们不能通过继承某个View来实现,而是需要通过继承普通的View,并完成View绘制的三部曲(measure,layout,draw)。
    首先看第一部曲:

        /**
         * View的绘制的第一阶段调用
         * @param widthMeasureSpec
         * @param heightMeasureSpec
         */
        @Override
        protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
            super.onMeasure(widthMeasureSpec, heightMeasureSpec);
            int width=getDefaultWidth();
            if(MeasureSpec.UNSPECIFIED!=MeasureSpec.getMode(widthMeasureSpec)){
                width=MeasureSpec.getSize(widthMeasureSpec);
            }
    
            int height=120;
            if(MeasureSpec.UNSPECIFIED!=MeasureSpec.getMode(heightMeasureSpec)){
                height=MeasureSpec.getSize(heightMeasureSpec);
            }
            Log.d(TAG, "onMeasure-->width:" + width + " height:" + height);
            setMeasuredDimension(width, height);
    
        }

    onMeasure 方法中,首先判断MeasureSpec 中的mode部分是否为MeasureSpec.UNSPECIFIED,如果是的,则宽度通过getDefaultWidth() 方法获取,高度为120,如果不是,那么拿到widthMeasureSpec/heightMeasureSpec中的size部分。如果你对于为什么这样做的原因不清楚,欢迎你阅读我的关于View绘制相关文章:
    Android中View的绘制机制源码分析一
    Android中View的绘制机制源码分析二
    Android中View的绘制机制源码分析三
    Android中View的绘制机制源码分析四

    第二部曲:

        /*
         * 在View的绘制的第二阶段(layout)中,当尺寸发生变化时调用
         * 注意:第二阶段本来是调用onLayout方法,此方法是在onLayout方法中被调用
         * @param w
         * @param h
         * @param oldw
         * @param oldh
         */
        @Override
        protected void onSizeChanged(int w, int h, int oldw, int oldh) {
            super.onSizeChanged(w, h, oldw, oldh);
            //计算位置
            mCenterY=this.getHeight()/2;
            mLeftX=this.getLeft()+getPaddingLeft();
            mLeftY=mCenterY-mLineHeight/2;
            mRightX=this.getRight()-getPaddingRight();
            mRightY=mCenterY+mLineHeight/2;
            Log.d(TAG,"onSizeChanged->mLeftX:"+mLeftX);
            Log.d(TAG, "onSizeChanged->mRightX:" + mRightX);
            if(mTotalStep>1){
                mDistance=(mRightX-mLeftX)/(mTotalStep-1);
                Log.d(TAG,"onSizeChanged->mDistance:"+mDistance);
            }
        }

    本来第二部应该改写的时onDraw() 方法的,但这里改写的却是onSizeChange() 方法,由于这里我只关注View的大小改变,并且onSizeChange() 方法是在 onDraw() 中被调用(只有尺寸发生变化才会调用),在onSizeChange() 方法中我们计算了自定义View的纵向中心位置,左边坐标,右边左边,小圆点之间的距离等等。在这里可以思考一下,为啥要在这里计算尺寸相关变量?这个问题我已经在View的绘制机制相关文章做出了解答。

    下面看看最重要的第三部曲:

    
        /**
         * View的绘制的第三阶段调用
         * @param canvas
         */
        @Override
        protected void onDraw(Canvas canvas) {
            super.onDraw(canvas);
            if(mTotalStep<=0 || mCompleteStep<0 || mCompleteStep>mTotalStep){
                return;
            }
            Paint mCirclePaint=new Paint();
            mCirclePaint.setAntiAlias(true);
            mCirclePaint.setStyle(Paint.Style.FILL);
            mCirclePaint.setColor(mUnDoneColor);
    
            canvas.drawRect(mLeftX,mLeftY,mRightX,mRightY,mCirclePaint);
            float xLoc=mLeftX;
            //画所有的步骤(圆形)
            for(int i=0;i<mTotalStep;i++){
                canvas.drawCircle(xLoc, mLeftY, mSmallRadius, mCirclePaint);
                xLoc=xLoc+mDistance;
            }
    
            //画已经完成的步骤(圆形加矩形)
            xLoc=mLeftX;
            mCirclePaint.setColor(mDoneColor);
            for(int i=0;i<mCompleteStep;i++){
                if(i>0){
                    canvas.drawRect(xLoc-mDistance,mLeftY,xLoc,mRightY,mCirclePaint);
                }
                canvas.drawCircle(xLoc, mLeftY, mSmallRadius, mCirclePaint);
    
    
                //画当前步骤(加光晕效果)
                if(i==mCompleteStep-1){
                    mCirclePaint.setColor(getTranspartColorByAlpha(mDoneColor,0.2f));
                    canvas.drawCircle(xLoc, mLeftY, mLargeRadius, mCirclePaint);
                }else {
                    xLoc=xLoc+mDistance;
                }
    
            }
        }

    onDraw() 方法中,主要是对UI进行绘制,分为三个步骤:

    1. 绘制横线
    2. 根据总步骤的个数,绘制小圆点
    3. 绘制已经完成步骤的小圆点(颜色和未完成的步骤不同),并未最后一个完成步骤添加光晕效果

    StepBar的主要逻辑已经介绍完了,下面介绍一下SetpView的逻辑,在使用的时候,我们只会使用SetpView,SetpView是对SetpBar的一个封装,并提供了title的属性。

    SetpView的UI布局:

    <?xml version="1.0" encoding="utf-8"?>
    <merge
        xmlns:android="http://schemas.android.com/apk/res/android"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:orientation="vertical"
        >
        <FrameLayout
            android:id="@+id/step_title"
            android:layout_gravity="left"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            >
        </FrameLayout>
        <com.gavin.step.StepBar
            android:id="@+id/step_bar"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_below="@id/step_title"
            android:paddingLeft="30dp"
            android:paddingRight="30dp"
            />
    </merge>

    这个布局很简单,相信不用我介绍,我们直接看SetpView的代码部分吧

    public StepView(Context context) {
            super(context);
            init(context,null,0);
        }
    
        public StepView(Context context, AttributeSet attrs) {
            super(context, attrs);
            init(context, attrs, 0);
        }
    
        public StepView(Context context, AttributeSet attrs, int defStyleAttr) {
            super(context, attrs, defStyleAttr);
            init(context, attrs, defStyleAttr);
        }
        @TargetApi(Build.VERSION_CODES.LOLLIPOP)
        public StepView(Context context, AttributeSet attrs, int defStyleAttr, int defStyleRes) {
            super(context, attrs, defStyleAttr, defStyleRes);
            init(context,attrs,defStyleAttr);
        }
    
        private void init(Context mContext,AttributeSet attrs,int defStyleAttr){
            LayoutInflater.from(mContext).inflate(R.layout.step_view,this,true);
            mStepBar=(StepBar)this.findViewById(R.id.step_bar);
            mTitleGroup=(FrameLayout)this.findViewById(R.id.step_title);
            TypedArray array = mContext.obtainStyledAttributes(attrs,R.styleable.StepView,defStyleAttr,0);
    
            mStepBar.setLineHeight(array.getDimensionPixelOffset(R.styleable.StepView_lineheight, StepBar.DEFAULT_LINE_HEIGHT));
            mStepBar.setSmallRadius(array.getDimensionPixelOffset(R.styleable.StepView_smallradius, StepBar.DEFAULT_SMALL_CIRCLE_RADIUS));
            mStepBar.setLargeRadius(array.getDimensionPixelOffset(R.styleable.StepView_largeradius, StepBar.DEFAULT_LARGE_CIRCLE_RADIUS));
            mStepBar.setUnDoneColor(array.getColor(R.styleable.StepView_undonecolor, StepBar.COLOR_BAR_UNDONE));
            mStepBar.setDoneColor(array.getColor(R.styleable.StepView_undonecolor, StepBar.COLOR_BAR_DONE));
            mStepBar.setTotalStep(array.getInteger(R.styleable.StepView_totalstep, 0));
            mStepBar.setCompleteStep(array.getInteger(R.styleable.StepView_completestep, 0));
    
            //在StepBar布局完成之后开始添加title
            mStepBar.getViewTreeObserver().addOnGlobalLayoutListener(new ViewTreeObserver.OnGlobalLayoutListener(){
    
                @Override
                public void onGlobalLayout() {
                    initStepTitle();
                    if (Build.VERSION.SDK_INT < Build.VERSION_CODES.JELLY_BEAN) {
                        mStepBar.getViewTreeObserver().removeGlobalOnLayoutListener(this);
                    } else {
                        mStepBar.getViewTreeObserver().removeOnGlobalLayoutListener(this);
                    }
                }
            });
            array.recycle();
        }
    

    这里我们主要看看init() 方法,这个方法是在构造函数中被调用,主要用来解析自定义属性的,关于自定义属性的逻辑我不在多说,这里主要看为SetpBar添加title的逻辑,我并没有直接在init() 方法中调用添加title的逻辑,而是等SetpBar第二部曲完成之后才添加title的逻辑。为什么呢?先看看添加title的逻辑再来解答此问题吧

    private void initStepTitle(){
            if(mStepTitles==null){
                return;
            }
            mTitleGroup.removeAllViews();
    
            if(mStepTitles.size()!=mStepBar.getTotalStep()){
                throw new IllegalStateException("设置的Title的个数和步骤数不一致!");
            }
            int stepNum=mStepBar.getTotalStep();
            for(int i=1;i<=stepNum;i++){
                final float stepPos=mStepBar.getPositionByStep(i);
                final TextView title=new TextView(this.getContext());
                title.setText(mStepTitles.get(i - 1));
                title.setSingleLine();
                title.getViewTreeObserver().addOnGlobalLayoutListener(new ViewTreeObserver.OnGlobalLayoutListener() {
                    @Override
                    public void onGlobalLayout() {
                        title.setTranslationX(stepPos - title.getMeasuredWidth() / 2);
                        if (Build.VERSION.SDK_INT < Build.VERSION_CODES.JELLY_BEAN) {
                            title.getViewTreeObserver().removeGlobalOnLayoutListener(this);
                        } else {
                            title.getViewTreeObserver().removeOnGlobalLayoutListener(this);
                        }
                    }
                });
                FrameLayout.LayoutParams lp=new FrameLayout.LayoutParams(LinearLayout.LayoutParams.WRAP_CONTENT,LinearLayout.LayoutParams.WRAP_CONTENT);
                mTitleGroup.addView(title,lp);
            }
        }
    

    由于在添加title的时候,需要用到小圆点的位置,这个位置只有SetpBar的第二部曲完成之后才可以确定,这就是为什么在刚才需要在SetpBar第二部曲完成之后才能添加title.

    好了,步骤指示器的代码逻辑介绍完了,如果有什么问题欢迎留言讨论…
    代码下载地址

    展开全文
  • 不能满足现阶段汽车发展的需求,E/E 架构升级成为智能网联汽车 展的关键。E/E 架构升级包括硬件、软件、通信架构三大升级,(由下至 上)芯片+操作系统+中间件+应用算法软件+数据构建核心技术闭环,汽 车操作...
  • 服务器响应请求,回网页内容。 浏览器解析网页内容。 网络爬虫要做的,简单来说,就是实现浏览器的功能。通过指定url,直接返回给用户所需要的数据,而不需要一步步人工去操纵浏览器获取。 抓取 这一步,你要...
  • 意思就是,我进入一个页面的时候(登录的情况下) 页面使用jquery自动调用的ajax的方法,在一大堆微博的人之中识别出来哪个是我已经关注的,那些没有关注,没关注的显示“关注”关注的就显示“关注”,提供...
  • EnumPrinterDrivers 枚举指定系统中已安装的打印机驱动程序 EnumPrinters 枚举系统中安装的打印机 EnumPrintProcessorDatatypes 枚举由一个打印处理器支持的数据类型 EnumPrintProcessors 枚举系统中可用的打印...
  • java发送短信AT指令

    热门讨论 2012-11-08 22:03:40
    /**短信接收*/ private String recver;//短信接收 /**时间*/ private Date date; public String getSmstext() { return smstext; } public void setSmstext(String smstext) { this.smstext = smstext...
  • 当一个连接某个处于ESTABLISHED状态的连接有关系时,就被认为是RELATED的了。换句话说,一个连接要想是RELATED的,首先要有一个ESTABLISHED的连接。这个ESTABLISHED连接再产生一个主连接之外的连接,这个新的...
  • Squid 中文权威指南

    2011-08-19 13:38:16
    假如你获取一个编译的使用某个参数值的squid 到另一个使用不同参数值的系统,可能会遇到问题。 另一个理由是许多squid 功能在编译时必须被激活。假如你获取一个别人编译的squid文件,它不包含你所需要的功能...
  • BetaFast 公司 BetaFast是一流的Betamax租赁亭的提供商。 浏览种类繁多的电影并立即开始租借! 发行版 已经发布了两个易受攻击的应用程序。 其中一就是BetaFast,这是一个主要的Betamax租赁亭,采用三层体系... 已发
  • 中文API支持库(1.0-0

    2009-04-17 08:28:19
    如果它是从同一个进程中发出来的,则返回FALSE(此时,该函数没有任何效果)。 _发送消息() 调用一个窗口的窗口函数,将一条消息发给那个窗口。除非消息处理完毕,否则该函数不会返回。返回值由具体的消息决定。 _...
  • I P报文的源目的地址,或者给某种通信报文分配较多 的带宽,读者就能够进一步加强进出网络的报文的安全性控制能力。本章将讨论两种特性: T C P拦截网络地址转换(Network Address Tr a n s l a t i o n,N...
  • c# 加密解密相关代码

    热门讨论 2011-09-06 11:04:59
    某种特殊的方法,更改有信息的内容,使得授权的用户即使得到 了加密信息,如果没有正确解密的方法,也无法得到信息的内容。谈 到加密的话题,一些读者一定非常感兴趣,而且会联想到复杂的加密 算法,本实例主要...
  • fc one.txt two.txt > 3st.txt 对比二个文件并把不同处输出到3st.txt文件,"> ""> >" 是重定向命令 at id号 开启注册的某个计划任务 at /delete 停止所有计划任务,用参数/yes则不需要确认就直接停止 at ...
  • slots editor 进行信号槽的关联,其中,Sender 设为enterBtn,Signal 设为clicked(),Receive 设为myDlg,Slot 设为accept()。这样就实现了单击 这个按钮使这个对话框关闭并发出Accepted 信号的功能。下面我们将...
  • Linux tcp拥塞控制

    2020-11-27 22:20:18
    绿色部门表示发送方可发送但发送的序列号(也表示接收方通知的接收窗口),蓝色和绿色两部分之和即为接收端通知的接收窗口,对应发送端的snd_wnd字段,最右边表示发送方不能发送的序列号。紫色区域最右边的值对应...

    1、滑动窗口

    滑动窗口是发送方根据接收方的接收窗口来控制发送速率的手段,接收发的滑动窗口可分成以下四个部分,最左边的紫色表示发送方已发送并且接收发已经确认的序列号,蓝色部分表示发送方已经发送但接收方还未确认的序列号,绿色部门表示发送方可发送但未发送的序列号(也表示接收方通知的接收窗口),蓝色和绿色两部分之和即为接收端通知的接收窗口,对应发送端的snd_wnd字段,最右边表示发送方不能发送的序列号。紫色区域最右边的值对应tcp的snd_una,蓝色最左侧对应tcp的snd_next;在数据包传输过程中,snd_una、snd_next一直在增加,整个窗口呈现出不断向右侧滑动的状态。

    接收窗口发送:

    接收端回复发送端时,在数据包发送流程,会根据当前接收socket内存信息获取一个接收窗口,填充到tcp头的window字段;

    static int tcp_transmit_skb(struct sock *sk, struct sk_buff *skb, int clone_it,
    			    gfp_t gfp_mask)
    {
    	...
    	tcp_options_write((__be32 *)(th + 1), tp, &opts);
    	skb_shinfo(skb)->gso_type = sk->sk_gso_type;
    	if (likely(!(tcb->tcp_flags & TCPHDR_SYN))) {
    		th->window      = htons(tcp_select_window(sk));
    		tcp_ecn_send(sk, skb, th, tcp_header_size);
    	} else {
    		/* RFC1323: The window in SYN & SYN/ACK segments
    		 * is never scaled.
    		 */
    		th->window	= htons(min(tp->rcv_wnd, 65535U));
    	}
    }

    接收端更新窗口时机:

    发送端会将接收端的接收窗口记录在tcp的snd_wnd里,主要有两个时机更新:

    1)、tcp建联时

    tcp服务端在收到第三次握手时,记录接收端的窗口;

    int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb)
    {
    	...
    	switch (sk->sk_state) {
    	case TCP_SYN_RECV:
    		if (!acceptable)
    			return 1;
    
    		if (!tp->srtt_us)
    			tcp_synack_rtt_meas(sk, req);
    
    		/* Once we leave TCP_SYN_RECV, we no longer need req
    		 * so release it.
    		 */
    		if (req) {
    			inet_csk(sk)->icsk_retransmits = 0;
    			reqsk_fastopen_remove(sk, req, false);
    		} else {
    			/* Make sure socket is routed, for correct metrics. */
    			icsk->icsk_af_ops->rebuild_header(sk);
    			tcp_init_congestion_control(sk);
    
    			tcp_mtup_init(sk);
    			tp->copied_seq = tp->rcv_nxt;
    			tcp_init_buffer_space(sk);
    		}
    		smp_mb();
    		tcp_set_state(sk, TCP_ESTABLISHED);
    		sk->sk_state_change(sk);
    
    		/* Note, that this wakeup is only for marginal crossed SYN case.
    		 * Passively open sockets are not waked up, because
    		 * sk->sk_sleep == NULL and sk->sk_socket == NULL.
    		 */
    		if (sk->sk_socket)
    			sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT);
    
    		tp->snd_una = TCP_SKB_CB(skb)->ack_seq;
    		tp->snd_wnd = ntohs(th->window) << tp->rx_opt.snd_wscale;
    		tcp_init_wl(tp, TCP_SKB_CB(skb)->seq);
    
    		if (tp->rx_opt.tstamp_ok)
    			tp->advmss -= TCPOLEN_TSTAMP_ALIGNED;
    
    		if (req) {
    			/* Re-arm the timer because data may have been sent out.
    			 * This is similar to the regular data transmission case
    			 * when new data has just been ack'ed.
    			 *
    			 * (TFO) - we could try to be more aggressive and
    			 * retransmitting any data sooner based on when they
    			 * are sent out.
    			 */
    			tcp_rearm_rto(sk);
    		} else
    			tcp_init_metrics(sk);
    
    		if (!inet_csk(sk)->icsk_ca_ops->cong_control)
    			tcp_update_pacing_rate(sk);
    
    		/* Prevent spurious tcp_cwnd_restart() on first data packet */
    		tp->lsndtime = tcp_time_stamp;
    
    		tcp_initialize_rcv_mss(sk);
    		tcp_fast_path_on(tp);
    		break;
    	}
    	...
    }

    2)、tcp接收慢路径

    static int tcp_ack_update_window(struct sock *sk, const struct sk_buff *skb, u32 ack,
    				 u32 ack_seq)
    {
    	struct tcp_sock *tp = tcp_sk(sk);
    	int flag = 0;
    	u32 nwin = ntohs(tcp_hdr(skb)->window);
    
    	if (likely(!tcp_hdr(skb)->syn))
    		nwin <<= tp->rx_opt.snd_wscale;
    
    	//ack表示接收端本次确认的序列号,ack_seq表示接收方发送本次ack数据包所使用的序列号
    	//如果:
    	//1、接收方本次有新确认的数据包
    	//2、发送发所使用的序列号比上次更新接收窗口时使用的序列号大
    	//3、发送发使用的序列号与上次更新窗口时使用的序列号相同,但接收窗口值变大(发送方重传?,并且重传数据包通知的接收窗口变大)
    	if (tcp_may_update_window(tp, ack, ack_seq, nwin)) {
    		flag |= FLAG_WIN_UPDATE;
    		tcp_update_wl(tp, ack_seq);
    
    		if (tp->snd_wnd != nwin) {
    			tp->snd_wnd = nwin;
    
    			/* Note, it is the only place, where
    			 * fast path is recovered for sending TCP.
    			 */
    			tp->pred_flags = 0;
    			tcp_fast_path_check(sk);
    
    			if (nwin > tp->max_window) {
    				tp->max_window = nwin;
    				tcp_sync_mss(sk, inet_csk(sk)->icsk_pmtu_cookie);
    			}
    		}
    	}
    
    	tcp_snd_una_update(tp, ack);
    
    	return flag;
    }
    

    发送方的流量控制

    当发送方需要发送数据包时,会检验当前接收方是否有足够的接收窗口,从这里的流程看,发送方会校验接收方至少要有1个接收窗口才能正常发送,当接收端没有足够的接收窗口时,发送端会暂停发送,从这里也可以看出,发送窗口(snd_wnd)主要是用于流量控制,防止接收端的接收速率跟不上发送端的发送速率。

    static bool tcp_write_xmit(struct sock *sk, unsigned int mss_now, int nonagle,
    			   int push_one, gfp_t gfp)
    {
    	...
    	max_segs = tcp_tso_segs(sk, mss_now);
    	//从下一个要发送的数据开始遍历
    	while ((skb = tcp_send_head(sk))) {
    		...
    
    		if (unlikely(!tcp_snd_wnd_test(tp, skb, mss_now))) {
    			is_rwnd_limited = true;
    			break;
    		}
    		...
    	}
    	...
    }
    
    static bool tcp_snd_wnd_test(const struct tcp_sock *tp,
    			     const struct sk_buff *skb,
    			     unsigned int cur_mss)
    {
    	u32 end_seq = TCP_SKB_CB(skb)->end_seq;
    
    	if (skb->len > cur_mss)
    		end_seq = TCP_SKB_CB(skb)->seq + cur_mss;
    
    	return !after(end_seq, tcp_wnd_end(tp));
    }

     

    2、拥塞窗口(snd_cwnd)

    拥塞窗口主要是用于控制数据包在链路上的传输,避免过多的数据包发送到链路上导致拥塞丢包,拥塞窗口对应tcp的snd_cwnd字段。拥塞控制算法主要就是根据链路的状态(传统拥塞算法主要是看丢包、乱序等,bbr算法主要是根据检测到的链路带宽及最小时延)调节拥塞窗口的大小,初始化时,会为每个tcp连接分配一个10的初始拥塞窗口。

    void tcp_init_sock(struct sock *sk)
    {
        ...
    
    	/* So many TCP implementations out there (incorrectly) count the
    	 * initial SYN frame in their delayed-ACK and congestion control
    	 * algorithms that we must have the following bandaid to talk
    	 * efficiently to them.  -DaveM
    	 */
    	tp->snd_cwnd = TCP_INIT_CWND;
    	...
    }

    3、拥塞控制

    拥塞控制算法主要包含几个流程:慢启动、拥塞避免、快恢复、快重传等状态;

    慢启动流程 && 拥塞避免:

    tcp为每个连接分配一个snd_ssthresh,当snd_cwnd小于snd_ssthresh时,每ack一个数据包,snd_cwnd就加1,此时的snd_cwnd呈现比较快速的增长阶段。

    1)、snd_ssthresh初始化

    snd_ssthresh会初始化一个0x7fffffff的值;

    void tcp_init_sock(struct sock *sk)
    {
    	...
    	/* See draft-stevens-tcpca-spec-01 for discussion of the
    	 * initialization of these values.
    	 */
    	tp->snd_ssthresh = TCP_INFINITE_SSTHRESH;
    	...
    }

    2)、snd_ssthresh更新

    判断当snd_cwnd小于snd_ssthresh时,处于慢启动流程,由于snd_ssthresh初始化的值是一个很大的值,因此如果用snd_cwnd跟snd_ssthresh初始化比较,显然没有意义;当tcp正常ack数据时,会进入pkts_acked,最终调用cubic的处理函数bictcp_acked,在bictcp_acked里,判断当snd_cwnd小于snd_ssthresh,并且snd_cwnd大于16时就会将snd_ssthresh更新成当前的snd_cwnd;

    static void bictcp_acked(struct sock *sk, const struct ack_sample *sample)
    {
    	const struct tcp_sock *tp = tcp_sk(sk);
    	struct bictcp *ca = inet_csk_ca(sk);
    	u32 delay;
    
    	/* Some calls are for duplicates without timetamps */
    	if (sample->rtt_us < 0)
    		return;
    
    	/* Discard delay samples right after fast recovery */
    	if (ca->epoch_start && (s32)(tcp_time_stamp - ca->epoch_start) < HZ)
    		return;
    
    	delay = (sample->rtt_us << 3) / USEC_PER_MSEC;
    	if (delay == 0)
    		delay = 1;
    
    	/* first time call or link delay decreases */
    	if (ca->delay_min == 0 || ca->delay_min > delay)
    		ca->delay_min = delay;
    
    	/* hystart triggers when cwnd is larger than some threshold */
    	if (hystart && tcp_in_slow_start(tp) &&
    	    tp->snd_cwnd >= hystart_low_window)
    		hystart_update(sk, delay);
    }
    

    接收端在收到ack时,判断如果当前不处于快恢复或loss状态,并且数据正常ack,则进入tcp_cong_avoid流程,这里会根据当前snd_cwnd与snd_ssthresh的关系决定当前的snd_cwnd如何增长;

    static void bictcp_cong_avoid(struct sock *sk, u32 ack, u32 acked)
    {
    	struct tcp_sock *tp = tcp_sk(sk);
    	struct bictcp *ca = inet_csk_ca(sk);
    
    	if (!tcp_is_cwnd_limited(sk))
    		return;
    
    	if (tp->snd_cwnd <= tp->snd_ssthresh) {
    		if (hystart && after(ack, ca->end_seq))
    			bictcp_hystart_reset(sk);
    		//acked返回非0表示,增加完拥塞窗口后,拥塞窗口已经超过了阀值snd_ssthresh
    		//正常慢启动流程,这里返回0,snd_cwnd += acked,每ack一个数据包,拥塞窗口加1
    		acked = tcp_slow_start(tp, acked);
    		if (!acked)
    			return;
    	}
    	//到了这里说明已经完成慢启动,进入拥塞避免阶段
    	//首先先计算一个阈值ca->cnt,表示ack多少个数据才增加一个拥塞窗口
    	bictcp_update(ca, tp->snd_cwnd, acked);
    	//更新拥塞窗口值
    	tcp_cong_avoid_ai(tp, ca->cnt, acked);
    }
    

    快恢复状态:

    当tcp数据包乱序时,接收端会回复重复的ack,当接收端收到可疑的ack或重复ack时,会调用tcp_fastretrans_alert修改当前的拥塞状态,在tcp_fastretrans_alert里会判断如果当前处于open状态,并且乱序包已经超过乱序阀值,判断当前有数据包丢失,进入快恢复阶段,调用tcp_entry_recovery;

    进入快恢复状态,cubic首先将snd_ssthresh降为当前拥塞窗口的717/1024倍,然后将拥塞窗口降为当前网络上的数据包个数(tcp_packets_in_flight + 1),然后重新进入慢启动流程;

    void tcp_cwnd_reduction(struct sock *sk, int newly_acked_sacked, int flag)
    {
    	struct tcp_sock *tp = tcp_sk(sk);
    	int sndcnt = 0;
    	int delta = tp->snd_ssthresh - tcp_packets_in_flight(tp);
    
    	if (newly_acked_sacked <= 0 || WARN_ON_ONCE(!tp->prior_cwnd))
    		return;
    
    	tp->prr_delivered += newly_acked_sacked;
    	if (delta < 0) {
    		u64 dividend = (u64)tp->snd_ssthresh * tp->prr_delivered +
    			       tp->prior_cwnd - 1;
    		sndcnt = div_u64(dividend, tp->prior_cwnd) - tp->prr_out;
    	} else if ((flag & FLAG_RETRANS_DATA_ACKED) &&
    		   !(flag & FLAG_LOST_RETRANS)) {
    		sndcnt = min_t(int, delta,
    			       max_t(int, tp->prr_delivered - tp->prr_out,
    				     newly_acked_sacked) + 1);
    	} else {
    		sndcnt = min(delta, newly_acked_sacked);
    	}
    	/* Force a fast retransmit upon entering fast recovery */
    	sndcnt = max(sndcnt, (tp->prr_out ? 0 : 1));
    	tp->snd_cwnd = tcp_packets_in_flight(tp) + sndcnt;
    }
    

    快恢复状态退出:

    在进入快恢复阶段时,tcp会保存当时的snd_next到high_seq,每次ack时,tcp判断当前处于非open状态都会进入tcp_fastretrans_alert,在tcp_fastretrans_alert里,判断如果snd_uan大于high_seq,那说明之前未ack的数据现在都已经ack了,已经没有数据空洞了,此时可以退出快恢复,重新回到open状态;

    static void tcp_fastretrans_alert(struct sock *sk, const int acked,
    				  const int prior_unsacked,
    				  bool is_dupack, int flag)
    {
    	...
    	/* D. Check state exit conditions. State can be terminated
    	 *    when high_seq is ACKed. */
    	if (icsk->icsk_ca_state == TCP_CA_Open) {
    		WARN_ON(tp->retrans_out != 0);
    		tp->retrans_stamp = 0;
    	} else if (!before(tp->snd_una, tp->high_seq)) {  
    		/* high_seq表示进入快恢复状态时的snd_next值,如果snd_una比high_seq大
    			那说明已经有新数据得到ack了,因此以下流程判断是否可以退出快恢复状态*/
    		switch (icsk->icsk_ca_state) {
    		case TCP_CA_CWR:
    			/* CWR is to be held something *above* high_seq
    			 * is ACKed for CWR bit to reach receiver. */
    			if (tp->snd_una != tp->high_seq) {
    				tcp_end_cwnd_reduction(sk);
    				tcp_set_ca_state(sk, TCP_CA_Open);
    			}
    			break;
    
    		case TCP_CA_Recovery:
    			if (tcp_is_reno(tp))
    				tcp_reset_reno_sack(tp);
    			if (tcp_try_undo_recovery(sk))
    				return;
    			tcp_end_cwnd_reduction(sk);
    			break;
    		}
    	}
    	...
    }

    当tcp退出快恢复状态时,snd_cwnd、snd_ssthresh从当前值与进入快恢复时的值两者间取更大的那个作为回到open状态时的snd_cwnd和snd_ssthresh;

    static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
    {
    	struct tcp_sock *tp = tcp_sk(sk);
    
    	if (unmark_loss) {
    		struct sk_buff *skb;
    
    		tcp_for_write_queue(skb, sk) {
    			if (skb == tcp_send_head(sk))
    				break;
    			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
    		}
    		tp->lost_out = 0;
    		tcp_clear_all_retrans_hints(tp);
    	}
    
    	if (tp->prior_ssthresh) {
    		const struct inet_connection_sock *icsk = inet_csk(sk);
    
    		if (icsk->icsk_ca_ops->undo_cwnd)
    			//设置退出快恢复状态的cwnd
    			tp->snd_cwnd = icsk->icsk_ca_ops->undo_cwnd(sk);
    		else
    			tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh << 1);
    
    		//设置退出快恢复状态的snd_ssthresh
    		if (tp->prior_ssthresh > tp->snd_ssthresh) {
    			tp->snd_ssthresh = tp->prior_ssthresh;
    			TCP_ECN_withdraw_cwr(tp);
    		}
    	} else {
    		tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh);
    	}
    	tp->snd_cwnd_stamp = tcp_time_stamp;
    	tp->undo_marker = 0;
    }
    

    上图的icsk->icsk_ca_ops->undo_cwnd最终会调用到bictcp_undo_cwnd里;

    static u32 bictcp_undo_cwnd(struct sock *sk)
    {
    	struct bictcp *ca = inet_csk_ca(sk);
    
    	//退出loss或recovery时,snd_cwnd取当前snd_cwnd与进入loss或recovery时的snd_cwnd的最大值
    	return max(tcp_sk(sk)->snd_cwnd, ca->loss_cwnd);
    }

    快重传:

    针对不同的拥塞算法,快重传的条件也不一样:

    1)、reno

    收到3个重复的ack;

    static void tcp_fastretrans_alert(struct sock *sk, const int acked,
    				  const int prior_unsacked,
    				  bool is_dupack, int flag)
    {
    	...
    	/* E. Process state. */
    	switch (icsk->icsk_ca_state) {
    	case TCP_CA_Recovery:
    		if (!(flag & FLAG_SND_UNA_ADVANCED)) {
    			if (tcp_is_reno(tp) && is_dupack)
    				tcp_add_reno_sack(sk);
    		} else {
    			if (tcp_try_undo_partial(sk, acked, prior_unsacked))
    				return;
    			/* Partial ACK arrived. Force fast retransmit. */
    			do_lost = tcp_is_reno(tp) ||
    				  tcp_fackets_out(tp) > tp->reordering;
    		}
    		if (tcp_try_undo_dsack(sk)) {
    			tcp_try_keep_open(sk);
    			return;
    		}
    		break;
    	case TCP_CA_Loss:
    		tcp_process_loss(sk, flag, is_dupack);
    		if (icsk->icsk_ca_state != TCP_CA_Open)
    			return;
    		/* Fall through to processing in Open state. */
    	default:
    		if (tcp_is_reno(tp)) {
    			if (flag & FLAG_SND_UNA_ADVANCED)
    				tcp_reset_reno_sack(tp);
    			if (is_dupack)
    				//reno算法时,每收到一个重复ack,sack_out加1,直到
    				//sack_out到达乱序阀值3时,触发重传
    				tcp_add_reno_sack(sk);
    		}
    	...
    }

    验证过程:

    通过packetdrill构造数据报文,同时结合ss命令查看:

    关闭rack: echo 0 >  /proc/sys/net/ipv4/tcp_recovery;

    关闭fack: echo 0 >/proc/sys/net/ipv4/tcp_fack;

    关闭sack: echo 0 > /proc/sys/net/ipv4/tcp_sack;

    packetdrill脚本:

    // Test fast retransmit with 4 packets outstanding, receiver sending SACKs.
    // In this variant the receiver supports SACK.
    
    // Establish a connection.
    0   socket(..., SOCK_STREAM, IPPROTO_TCP) = 3
    +0  setsockopt(3, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
    
    +0  bind(3, ..., ...) = 0
    +0  listen(3, 1) = 0
    
    +0  < S 0:0(0) win 32792 <mss 1000,sackOK,nop,nop,nop,wscale 7>
    +0  > S. 0:0(0) ack 1 <...>
    
    +.1 < . 1:1(0) ack 1 win 257
    +0  accept(3, ..., ...) = 4
    
    // Send 1 data segment and get an ACK, so cwnd is now 4.
    +0  write(4, ..., 1000) = 1000
    +0  > P. 1:1001(1000) ack 1
    
    +.1 < . 1:1(0) ack 1001 win 257
    
    // Write 10 data segments.
    +0  write(4, ..., 10000) = 10000
    +0  > P. 1001:10001(9000) ack 1
    
    //连续收到3个重复ack
    +.1 < . 1:1(0) ack 1001 win 257 <sack 3001:4001,nop,nop>
    +.1 < . 1:1(0) ack 1001 win 257 <sack 4001:5001,nop,nop>
    +.1 < . 1:1(0) ack 1001 win 257 <sack 5001:6001,nop,nop>
    
    //重传1001:2001数据包
    +.0  > . 1001:2001(1000) ack 1
    
    // Receiver ACKs all data.
    //所有消息包都ack,关闭socket连接
    +1 < . 1:1(0) ack 10001 win 257

    每隔一小段时间,捕获一次ss状态,从ss的状态显示看,当重复ack个数未满3个时,tcp保持在乱序状态(1---open),当收到第3个重复ack时,tcp状态为快恢复状态,并对第一个未ack的数据包标记loss,然后重传;

    2)、sack

    当sack的个数大于等于乱序阀值(默认3)时,tcp就会开始标记loss状态,标记的时候,从write队列最开始的skb开始标记,直至被标记loss的skb的右侧的sack个数为3为止。如下所示,一共发送10个skb,其中第4、7、9、10四个包被sack,那tcp计算此时fack_out=10,sack_out=4,loss_out=5;

    3)、fack

    echo 1 >/proc/sys/net/ipv4/tcp_fack启用fack

    fack是sack的更进一步优化,当使用fack时,sack的数据包个数不再需要超过乱序阀值,fack只关心收到的最大的sack数据包相比snd_una的间距是否超过乱序阀值,当超过时就会开始标记loss,fack标记loss时,从write队列最左侧开始标记,直至待标记的skb距离最大sack的skb的间距为reordering-1为止;

    如下,发送10个skb,其中第4、9个skb被sack,那此时fack_out=9,loss_out=5;

     

    4)、rack

    echo 1 >  /proc/sys/net/ipv4/tcp_recovery启用rack;

    rack相比fack又更进一步,rack是根据skb的发送时间来判断消息包是否丢失,tcp每发送一个skb时,都会为其分配一个时间戳信息,当sack时,rack机制判断那些在被sack的数据包之前发送的,并且相比被sack的数据包的时间间距到达一定间隔时,就判断该数据包为丢失,进而进入快恢复状态,然后重传被标记丢失的数据包。

    tcp发送数据包时,设置当前的发送时间:

    static int tcp_transmit_skb(struct sock *sk, struct sk_buff *skb, int clone_it,
    			    gfp_t gfp_mask)
    {
    	...
    	if (clone_it) {
    		//标记数据包发送时间
    		skb_mstamp_get(&skb->skb_mstamp);
    		TCP_SKB_CB(skb)->tx.in_flight = TCP_SKB_CB(skb)->end_seq
    			- tp->snd_una;
    		tcp_rate_skb_sent(sk, skb);
    
    		if (unlikely(skb_cloned(skb)))
    			skb = pskb_copy(skb, gfp_mask);
    		else
    			skb = skb_clone(skb, gfp_mask);
    		if (unlikely(!skb))
    			return -ENOBUFS;
    	}
    	...
    }

    当发送端收到sack报文时,开始标记sack标记时,进入rack更新流程:   

    static u8 tcp_sacktag_one(struct sock *sk,
    			  struct tcp_sacktag_state *state, u8 sacked,
    			  u32 start_seq, u32 end_seq,
    			  int dup_sack, int pcount,
    			  const struct skb_mstamp *xmit_time)
    {
    	...
    	if (!(sacked & TCPCB_SACKED_ACKED)) {
    		tcp_rack_advance(tp, sacked, end_seq, xmit_time);
    	...
    }

    rack更新流程主要是记录当前最新的sack数据包的发送时间及序列号等信息:

    /*当接收端收到sack时,进入该函数,记录被sack的消息包的发送时间及序列号*/
    void tcp_rack_advance(struct tcp_sock *tp, u8 sacked, u32 end_seq,
    		      const struct skb_mstamp *xmit_time)
    {
    	u32 rtt_us;
    
    	//如果skb比上一次标记rack的skb的发送时间更早,或者序列号更小,则不处理
    	if (tp->rack.mstamp.v64 &&
    	    !tcp_rack_sent_after(xmit_time, &tp->rack.mstamp,
    				 end_seq, tp->rack.end_seq))
    		return;
    
    	rtt_us = skb_mstamp_us_delta(&tp->tcp_mstamp, xmit_time);
    	if (sacked & TCPCB_RETRANS) {
    		/* If the sacked packet was retransmitted, it's ambiguous
    		 * whether the retransmission or the original (or the prior
    		 * retransmission) was sacked.
    		 *
    		 * If the original is lost, there is no ambiguity. Otherwise
    		 * we assume the original can be delayed up to aRTT + min_rtt.
    		 * the aRTT term is bounded by the fast recovery or timeout,
    		 * so it's at least one RTT (i.e., retransmission is at least
    		 * an RTT later).
    		 */
    		if (rtt_us < tcp_min_rtt(tp))
    			return;
    	}
    	//设置sack数据包的发送时间及序列号信息
    	tp->rack.rtt_us = rtt_us;
    	tp->rack.mstamp = *xmit_time;
    	tp->rack.end_seq = end_seq;
    	tp->rack.advanced = 1;
    }
    

    在tcp_fastretrans_alert流程判断如果有开启rack,则进入rack标记loss的流程:tcp_rack_identify_loss;

    如果有开启rack,则根据sack数据包的时间戳判断未sack的数据包是否丢包,在标记loss流程里会更新tp->lost_out计数,等回到tcp_fastretrans_alert里,函数tcp_time_to_recover判断lost_out非零,则进入recovery状态。如果没有需要标记loss的数据包,则根据剩余时间启动定时器,定时器超时,重新检测。

    static void tcp_rack_detect_loss(struct sock *sk, u32 *reo_timeout)
    {
    	struct tcp_sock *tp = tcp_sk(sk);
    	struct sk_buff *skb;
    	u32 reo_wnd;
    
    	*reo_timeout = 0;
    	/* To be more reordering resilient, allow min_rtt/4 settling delay
    	 * (lower-bounded to 1000uS). We use min_rtt instead of the smoothed
    	 * RTT because reordering is often a path property and less related
    	 * to queuing or delayed ACKs.
    	 */
    	reo_wnd = 1000;
    	if ((tp->rack.reord || !tp->lost_out) && tcp_min_rtt(tp) != ~0U)
    		reo_wnd = max(tcp_min_rtt(tp) >> 2, reo_wnd);
    
    	tcp_for_write_queue(skb, sk) {
    		struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
    
    		if (skb == tcp_send_head(sk))
    			break;
    
    		/* Skip ones already (s)acked */
    		if (!after(scb->end_seq, tp->snd_una) ||
    		    scb->sacked & TCPCB_SACKED_ACKED)
    			continue;
    
    		//tp->rack.mstamp表示sack的包的发送时间,tp->rack.end_seq表示sack数据包的序列号
    		//如果skb比被sack的数据的发送时间更早,或者序列号更小,那说明有可能这个skb是丢了
    		if (tcp_rack_sent_after(&tp->rack.mstamp, &skb->skb_mstamp,
    					tp->rack.end_seq, scb->end_seq)) {
    			/* Step 3 in draft-cheng-tcpm-rack-00.txt:
    			 * A packet is lost if its elapsed time is beyond
    			 * the recent RTT plus the reordering window.
    			 */
    			//tp->tcp_mstamp为最新ack(sack)的发送时间
    			//计算skb从发送到现在的时间距离
    			u32 elapsed = skb_mstamp_us_delta(&tp->tcp_mstamp,
    							  &skb->skb_mstamp);
    			//如果后发送的skb已经被sack,旧的还没有sack,并且时间超过rtt+窗口阀值
    			//则认为之前的包已经丢失,rack对其标记loss
    			//tp->rack.rtt_us表示sack的数据包的发送到现在的时间距离
    			//这个remaining的意思是,如果sack的数据包与比它更早发送出去但还未被sack的数据包
    			//的时间间隔超过1000us与1/4 rtt两个时间相对大的那个,那说明还未被sack的数据包可能是已经丢了,标记loss
    			s32 remaining = tp->rack.rtt_us + reo_wnd - elapsed;
    
    			if (remaining < 0) {
    				tcp_rack_mark_skb_lost(sk, skb);
    				continue;
    			}
    
    			/* Skip ones marked lost but not yet retransmitted */
    			if ((scb->sacked & TCPCB_LOST) &&
    			    !(scb->sacked & TCPCB_SACKED_RETRANS))
    				continue;
    			//如果时间还未超时,则启动超时定时器,如果定时器超时,则超时处理函数又进入tcp_rack_detect_loss重新检测
    			/* Record maximum wait time (+1 to avoid 0) */
    			*reo_timeout = max_t(u32, *reo_timeout, 1 + remaining);
    
    		} else if (!(scb->sacked & TCPCB_RETRANS)) {
    			/* Original data are sent sequentially so stop early
    			 * b/c the rest are all sent after rack_sent
    			 */
    			break;
    		}
    	}
    }
    

    验证过程:

    开启rack: echo 1 >/proc/sys/net/ipv4/tcp_recovery;

    先发送一个数据包,然后延时一定时间再发送第二个数据包;然后packetdrill构造直接sack第二个数据包;此时ss可以看到发送端标记了一个loss,并且进入了recovery状态,说明这个loss并非rto超时标记的,而是rack标记的。

    packetdrill脚本:

    // Establish a connection.
    0   socket(..., SOCK_STREAM, IPPROTO_TCP) = 3
    +0  setsockopt(3, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
    
    +0  bind(3, ..., ...) = 0
    +0  listen(3, 1) = 0
    
    +0  < S 0:0(0) win 32792 <mss 1000,sackOK,nop,nop,nop,wscale 7>
    +0  > S. 0:0(0) ack 1 <...>
    
    +.8 < . 1:1(0) ack 1 win 257
    +0  accept(3, ..., ...) = 4
    
    // 发送第1个skb
    +0  write(4, ..., 1000) = 1000
    +0  > P. 1:1001(1000) ack 1
    
    //第2个skb延时发送
    +.1  write(4, ..., 1000) = 1000
    
    //第二个skb被sack
    +0 < . 1:1(0) ack 1 win 257 <sack 1001:2001, nop,nop>
    

    LOSS状态

    rto定时器超时后,进入loss状态(tcp_enter_loss),进入loss状态后,先调整snd_ssthresh,然后将cwnd降为1;

    void tcp_enter_loss(struct sock *sk)
    {
    	const struct inet_connection_sock *icsk = inet_csk(sk);
    	struct tcp_sock *tp = tcp_sk(sk);
    	struct net *net = sock_net(sk);
    	struct sk_buff *skb;
    	bool new_recovery = icsk->icsk_ca_state < TCP_CA_Recovery;
    	bool is_reneg;			/* is receiver reneging on SACKs? */
    	bool mark_lost;
    
    	/* Reduce ssthresh if it has not yet been made inside this window. */
    	if (icsk->icsk_ca_state <= TCP_CA_Disorder ||
    	    !after(tp->high_seq, tp->snd_una) ||
    	    (icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) {
    		tp->prior_ssthresh = tcp_current_ssthresh(sk);
    		//进入loss,调整慢启动阀值snd_ssthresh
    		tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
    		tcp_ca_event(sk, CA_EVENT_LOSS);
    		tcp_init_undo(tp);
    	}
    	//进入loss后,将cwnd拥塞窗口降为1
    	tp->snd_cwnd	   = 1;
    	tp->snd_cwnd_cnt   = 0;
    	tp->snd_cwnd_stamp = tcp_time_stamp;
    	...
    }

     

    展开全文
  • JIRA管理思路

    2017-07-03 16:47:00
    刚刚开始用Jira的时候,只是觉得这是一个方便的bug管理系统,可以将在测试过程所发现的bug录入... 因起初只是使用者,因而并有站在一个管理者的角度上来看JIRA在项目管理的作用意义。因此今日再看时,已发...
  • **曾经觉得自己的重要电子邮件正在埋葬在提醒通知下,即你没有准备删除/存档/地址?此扩展允许您隐藏标有特定的Gmail标签或一组标签的消息。当你想看到一种类型的东西时,标签很棒。例如,假设您创建规则以...
  • 在因特网协议族(Internet protocol suite),TCP层是位于IP层上,应用层下的中间层。不同主机的应用层之间经常需要可靠的、像管道一样的连接,但是IP层不提供这样的流机制,而是提供不可靠的包交换。 [1] ...
  • 提高网站安全性 [变更] 处理缺货登记时回复用户留言或者评论时增加自动给客户邮件通知功能 [变更] 在配送方式新建配送区域时,增加选择所辖地区的提示 [变更] 后台订单详情页点“去发货”按钮后变更为进入...
  • Merit Money 应用程序在波兰的敏捷成功的软件公司成功。 他们的员工每天都在使用它。 我每周一期待的最棒的时刻一就是启动该应用程序,看看我获得了多少荣誉以及为了什么。 阅读同事的评论确实提高了我的整体...
  • java基础入门教程

    热门讨论 2009-04-29 21:36:10
    通 过 颁发 许 可 证 的 办 法 来 允 许 各 家 公 司 把Java虚 拟 机 Java的Applets类库 嵌 入 他 们 开 的 操 作 系 统 ,这 样 各 类 开 人 员 就 能更 容易 地 选 择 多种 平 台 来 使 用 Java语 言 编 ...
  • 客户、单号、产品、数量、单价、销售金额、应收金额、收金额、收款日期、调整金额、收余额等),并按客户统计其期初应收、销售金额合计、应收金额合计、收金额合计、调整金额合计、收余额合计应收余额...
  • 分页是Web应用程序最常用到的功能一,在ASP.NET,虽然自带了一个可以分页的DataGrid(asp.net 1.1)GridView(asp.net 2.0)控件,但其分页功能并不尽如人意,如可定制性差、无法通过Url实现分页功能等,...
  • realplayer

    2010-08-18 10:57:02
    您接受使用本软件(或)服务视同您仔细阅读此许可协议,理解此许可协议并同意接受其条款条件的约束。 您可以选择是否使用随同本软件一起提供的任何第三方软件,包括任何第三方插件。 如果您选择使用此类第三方...
  • 分页是Web应用程序最常用到的功能一,在ASP.NET,虽然自带了一个可以分页的DataGrid(asp.net 1.1)GridView(asp.net 2.0)控件,但其分页功能并不尽如人意,如可定制性差、无法通过Url实现分页功能等,...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 151
精华内容 60
关键字:

未发之中已发之和