论述"增减法"的公平性

协调者：

管理着一张使用情况表,每个用户（工作站）在表中都有一个条目(称为惩罚点),初值为0。

惩罚点计算：

1.当有重要的事件(请求、处理机变为空闲、经过一段时间)发生时,给协调者发送消息以更新使用情况表;

2.进程创建时,若要在外执行,向协调者请求处理机,若不能满足,则惩罚点值-1(细节见图);

3.若工作站有进程在远程工作站上运行,则惩罚点值按时间段+n(在远程运行的进程数);

4.当一个工作站无请求且没有远程运行的进程时,惩罚点值按时间段-1,直至为0。

处理机分配：

当一个处理机变成空闲时,首先满足分数最低的正在等待的工作站申请。

对图的简单说明：

1. 进程1到达，但是没有分配到处理机，故工作站的惩罚点减1
2. 进程1分配到处理机，故工作站的惩罚点加1
3. 进程2到达，没有分配到处理机，同时进程1在执行，工作站惩罚点加1（为什么不是0？ 之后会论证）
4. 进程2分配到处理机，进程1仍在运行，故工作站的惩罚点加2
5. 进程1结束，进程2仍在运行，故工作站的惩罚点加1
6. 进程2结束，当前工作站无进程运行，故工作站的惩罚点减1，直到惩罚点为0

公平性：

使用惩罚点可以为正、零或负值。正值表示工作站(用户)占有处理机，负值表示工作站(用户)需要处理机，零表示正常。当一个处理机空闲时，拥有最低惩罚点的用户的进程将得到处理机。因此，没有处理机的工作站(用户)或等了很久的工作站(用户)总会得到满足。

不足：

无法解决进程优先级问题。当所有处理机被占用，此时出现一个优先级高的进程，但是无法被立即执行。

论证说明中标红的部分：

假如工作表1中，A点进程2和进程1相互抵消，惩罚点加0。此时引入另外一个工作表2，惩罚点为0,存在进程申请处理机请求，并且无其它进程在处理机上运行。假如这时有一台处理机空闲，但是协调者可能将处理机分配给工作表1,因为工作表1和工作表2的惩罚点都为0。这明显就是不公平的行为。

（网上证明，更为清晰）假设工作表Ⅰ的惩罚点在A-B点均抵消为0，则其到C点时惩罚点为4，有进程②在处理机1上运行；若另有工作表Ⅱ同样有类似的进程①在处理机2运行，但在A点没有新进程生成，则其到C点时惩罚点为5，无进程在处理机上运行。此时协调者会根据情况表优先为工作表Ⅰ分配处理机，这明显是不公平的。该算法做出调整后，工作表Ⅰ在C点的惩罚点为7，工作表Ⅱ在C点的惩罚点值为5，则工作表Ⅱ将优先被分配资源，确保了“增”的公平性；相应地，当工作表未占有且不需要资源时，它们的惩罚点值会按时间以相同的速率向零点移动，确保了“减”的公平性。

参考：https://wenku.baidu.com/view/42fb6523cd1755270722192e453610661ed95a7b.html