4.5 差分链表

在嵌入式操作系统中，为了管理任务的等待时间，时间到就进行调度，使用一种特殊的链表，称为差分链表。

在差分时间链中，链头指针表示当前时刻，每个块表示一个事件，块中所包含的计时值并非当前时刻到该事件被激活时刻的绝对计数，而是该事件到上一事件的相对值。通过该事件块和先于它的所有事件块的计数值之和来表示该事件激活时刻的到当前时刻的时间距离。下面有些图做说明。

如图4.4所示，在当前时刻，对象A需要等待3个时间单位被激活，对象B需要等待5（3+2）个时间单位被激活，对象C需要等待10（3+2+5）个时间单位被激活。

如图4.5所示，在当前时刻，如果有一个等待9个时间单位的对象E需要插到队列中，由于9-3-2=4，而9-3-2-5=-1，因此对象E需要插到差分链中介于对象B和对象C之间的位置。

图4.4 三个节点的差分链表

图4.5 插入一个节点后的差分链表

假设链表为a，链上的元素为ai，前一个元素为ai-1，后一个元素为ai+1，val(ai)是时间，表示前一个事件结束后过val（ai）时间就到下一个事件了。假设第一个事件在0时刻发生，那么第i个事件发生的时间，就是之前所有节点之和。

1.插入算法

插入一个m时间发生的事件，先要计算插入位置，，则插入i后。新插入的ai′的值是，如果不是末尾，则ai+1的值也要做改变，变为val(ai+1)-val(ai′)。

2.删除算法

删除一个m时间发生的事件，过程和插入一样，只是计算不同。先要找到删除点，然后删除节点ai。如果不是末尾，那么就把后一个元素的值加上刚才删掉的值。

对于差分时间链，系统每接收到一个tick（时钟中断），就修订链首对象的时间值。如果链表对象的时间单位为tick，则每发生一个tick，链首对象的时间值就减1。当减到0时，链首对象就被激活，并从差分时间链中取下来，下一个对象又成为链首对象。这种算法是基于时间的调度算法。