【读书笔记-《30天自制操作系统》-12】Day13

本篇的内容仍然是定时器的相关讲解。上一篇内容中对于中断程序做了许多优化，但是这些优化到底起了多少作用呢？本篇用一种测试方法来进行测试。然后本篇继续引入链表与哨兵的概念，进一步加快超时的中断处理。

1. 主程序简化

开发过程到了这一步，程序的代码量已经不少了。但其中其实有很多重复和可以简化的地方。
比如在显示窗口的时候多次出现了如下代码：

		boxfill8(buf_win, 160, COL8_C6C6C6, 40, 28, 119, 43);
		putfonts8_asc(buf_win, 160, 40, 28, COL8_000000, s);
		sheet_refresh(sht_win, 40, 28, 120, 44);

这里其实可以将以上代码写成一个函数进行调用：

void putfonts8_asc_sht(struct SHEET *sht, int x, int y, int c, int b, char *s, int l)
{
	boxfill8(sht->buf, sht->bxsize, b, x, y, x + l * 8 - 1, y + 15);
	putfonts8_asc(sht->buf, sht->bxsize, x, y, c, s);
	sheet_refresh(sht, x, y, x + l * 8, y + 16);
	return;
}

这样可以节省不少的基本类似的重复代码。

接下来是主程序中的这一部分：

		if (fifo8_status(&keyfifo) + fifo8_status(&mousefifo) + fifo8_status(&timerfifo)
				+ fifo8_status(&timerfifo2) + fifo8_status(&timerfifo3) == 0) {
			io_sti();
		} 
		……

可以看出这样的代码也很冗长，有优化的空间。我们可以将鼠标、键盘与定时器在产生中断时写入同一个缓冲区，根据写入内容的不同来判断产生的是哪一种中断：

• 0-1： 光标闪烁用定时器
• 3： 3s定时器
• 10： 10s定时器
• 256-511： 键盘输入(从键盘控制器中读入的值再加上256)
• 512-767： 鼠标输入(从键盘控制器中读入的值再加上512)

这样一个缓冲区就可以进行处理多种中断，不需要建立多个缓冲区了。但是此前的8位缓冲区能处理的数据只有255，因此需要扩充一下，这里使用int型来替代之前的8位缓冲区。

struct FIFO32
{
	int *buf;
	int p, q, size, free, flags;
}

除了buf扩充为int型，其他参数的意义保持不变。
当然这里修改之后，使用fifo的其他位置也要进行相应的修改。

2. 性能优化测试

前面做了这么多优化，具体效果如何呢？下面用一些方法来进行测试。

测试的方法是修改主程序，恢复变量count，完全不显示计数，全力执行"count++"语句，当到了10s超时的时候，再显示count的值。

同样的程序运行多次，count显示的最终数值还是会有所差异，而且差异还不小。这主要是模拟器的原因，作者用真机进行测试，结果就稳定的多了。

用优化前和优化后的程序分别执行这个测试，count显示的数值差别还是很明显的，说明中断处理的速度确实得到了提升。

3. 引入链表与哨兵继续加速中断处理

在上一篇中，我们对定时器进行了移位操作。前面已经使用过类似的方法，这样做的缺点在于如果定时器很多，这样的移位操作肯定是很费时间的。有什么好办法呢？

这里作者实际上引入了链表的概念。

在定时器TIMER的结构体中，引入了next变量，用于存放下一个即将超时的定时器地址。

struct TIMER {
	struct TIMER *next;
	unsigned int timeout, flags;
	struct FIFO32 *fifo;
	int data;
};

这样通过当前的定时器，就可以找到下一个定时器。在内存的物理空间上，两个定时器并不是挨着的，但是通过next中保存的地址连在了一起，就像一条铁链一样一环扣一环，被称为链表。
链表相比于数组的优势就在于很方便插入和删除，而不用像前一篇使用数组保存排序好的定时器时，插入或删除都需要将后面的定时器进行整体移位。在链表中插入或删除都只需要修改前后两个定时器的next值即可，这样链条仍然是连在一起的。

在此基础上就可以很方便地修改中断处理函数：

void inthandler20(int *esp)
{
	int i;
	struct TIMER *timer;
	io_out8(PIC0_OCW2, 0x60);	
	timerctl.count++;
	if (timerctl.next > timerctl.count) {
		return;
	}
	timer = timerctl.t0; /* 首先将最前面的地址赋值给timer */
	for (i = 0; i < timerctl.using; i++) {
		if (timer->timeout > timerctl.count) {
			break;
		}
		/* 超时 */
		timer->flags = TIMER_FLAGS_ALLOC;
		fifo32_put(timer->fifo, timer->data);
		timer = timer->next; /* 将下一定时器的地址赋给timer */
	}
	timerctl.using -= i;

	/* 取代移位功能 */
	timerctl.t0 = timer;

	/* 设置timerctl.next */
	if (timerctl.using > 0) {
		timerctl.next = timerctl.t0->timeout;
	} else {
		timerctl.next = 0xffffffff;
	}
	return;
}

这里需要说明一下，timerctl中的next表示下一个超时时刻，而timer中的next表示的是下一个超时的定时器的地址，不能混淆。每当有一个定时器超时，将这个定时器取下，并将下一个即将超时的定时器地址放在timerctl的timers[0]元素。其实timers[]数组中的其他元素都不需要了，只需要一个元素t0用来记录链表的起始位置，于是将TIMERCTL结构体进行了修改。

struct TIMERCTL {
	unsigned int count, next, using;
	struct TIMER *t0;
	struct TIMER timers0[MAX_TIMER];
};

在timer_settime函数中，我们仍然需要根据超时时间将这个定时器插入到链表的特定位置上：

void timer_settime(struct TIMER *timer, unsigned int timeout)
{
	int e;
	struct TIMER *t, *s;
	timer->timeout = timeout + timerctl.count;
	timer->flags = TIMER_FLAGS_USING;
	e = io_load_eflags();
	io_cli();
	timerctl.using++;
	if (timerctl.using == 1) {
		/* 处于运行状态的定时器只有1个 */
		timerctl.t0 = timer;
		timer->next = 0; /* 没有下一个超时的定时器了 */
		timerctl.next = timer->timeout;
		io_store_eflags(e);
		return;
	}
	t = timerctl.t0;/* 此时t是链表的起始位置*/
	if (timer->timeout <= t->timeout) {
		/* 插入链表最前面位置的情况 */
		timerctl.t0 = timer;
		timer->next = t; /* 放在t前面 */
		timerctl.next = timer->timeout;
		io_store_eflags(e);
		return;
	}
	/* 在链表中寻找插入的位置 */
	for (;;) {
		s = t;
		t = t->next;/*s用来保存前一个位置*/
		if (t == 0) {
			break; /* 链表最后面 */
		}
		if (timer->timeout <= t->timeout) {
			/* 插入到s和t之间时 */
			s->next = timer; /* s的下一个是timer */
			timer->next = t; /* timer的下一个是t */
			io_store_eflags(e);
			return;
		}
	}
	/* 放在最后 */
	s->next = timer;
	timer->next = 0;
	io_store_eflags(e);
	return;
}

如图所示：

到这里作者还是不满足。因为在将新的定时器插入链表中时，需要考虑四种情况：

• 当前链表中没有定时器，插入的定时器是第一个
• 当前定时器插入到链表最前面
• 当前定时器插入到s和t之间
• 当前定时器插入到链表的最后面

导致代码还是比较冗长。为了对这4种情况进行简化，引入了哨兵的概念。

在初始化的时候，将最后一个定时器的超时时间设置为0xffffffff。这个超时时间是不会达到的，因为前面引入的时间调整程序每隔一段时间会修改当前时刻。用作者的话说，这是家里的留守者，所以被称为哨兵。修改init_pit如下：

void init_pit(void)
{
	int i;
	struct TIMER *t;
	io_out8(PIT_CTRL, 0x34);
	io_out8(PIT_CNT0, 0x9c);
	io_out8(PIT_CNT0, 0x2e);
	timerctl.count = 0;
	for (i = 0; i < MAX_TIMER; i++) {
		timerctl.timers0[i].flags = 0; /* 没有使用 */
	}
	t = timer_alloc(); /* 取得一个空闲的定时器 */
	t->timeout = 0xffffffff;
	t->flags = TIMER_FLAGS_USING;
	t->next = 0; /* 处于链表末尾的定时器 */
	timerctl.t0 = t; /* 当前只有一个哨兵，所以链表的开头也是它 */
	timerctl.next = 0xffffffff; /* 哨兵的超时时刻，永远不会达到 */
	return;
}

在时刻调整程序中，需要避开对哨兵超时时刻的调整。

而加入哨兵之后，timer_settime函数中需要考虑的情况就减少为两种：

• 当前链表中没有定时器(不会出现此种情况，由于哨兵的存在，链表中至少有一个定时器)
• 当前定时器插入到链表最前面
• 当前定时器插入到s和t之间
• 当前定时器插入到链表的最后面(不会出现此种情况，哨兵总是在最后面)

因此timer_settime函数可用进行简化：

void timer_settime(struct TIMER *timer, unsigned int timeout)
{
	int e;
	struct TIMER *t, *s;
	timer->timeout = timeout + timerctl.count;
	timer->flags = TIMER_FLAGS_USING;
	e = io_load_eflags();
	io_cli();
	t = timerctl.t0;
	if (timer->timeout <= t->timeout) {
		/* 插入链表最前面的情况 */
		timerctl.t0 = timer;
		timer->next = t; /* t当前是链表的初始位置，在初始位置之前插入 */
		timerctl.next = timer->timeout;
		io_store_eflags(e);
		return;
	}
	/* 寻找插入位置 */
	for (;;) {
		s = t;
		t = t->next;
		if (timer->timeout <= t->timeout) {
			/* 插入s和t之间的情况 */
			s->next = timer;
			timer->next = t;
			io_store_eflags(e);
			return;
		}
	}
}

同样inthandler20函数也可用得到精简：

void inthandler20(int *esp)
{
	struct TIMER *timer;
	io_out8(PIC0_OCW2, 0x60);	
	timerctl.count++;
	if (timerctl.next > timerctl.count) {
		return;
	}
	timer = timerctl.t0; /* timer从链表的起始位置开始 */
	for (;;) {
		if (timer->timeout > timerctl.count) {
			break;
		}
		/* 超时的定时器 */
		timer->flags = TIMER_FLAGS_ALLOC;
		fifo32_put(timer->fifo, timer->data);
		timer = timer->next; /* 指向链表中的下一个定时器 */
	}
	/* 更新链表的起始地址*/
	timerctl.t0 = timer;
	timerctl.next = timer->timeout;
	return;
}

变量using用来记录当前运行中的定时器数量，配合数组timers定位当前的定时器应该插入到数组的哪个位置。但现在变量using已经不需要了。无论是从链表中删除定时器，还是向链表中插入定时器，通过链表都可以轻松实现。

这样关于超时中断的优化就全部做完了。从中可以更好地理解到链表在随机插入与删除元素时相比于数组的优越性。

下一篇的主要内容是提高分辨率与键盘输入。敬请期待。