文档介绍：第四章原则的运用
应用设备通道的缓冲区验证
应用设备通道(Application Device Channels)允许应用程序直接读写网络适配器的存储区域来进行网络收发。
需要一种隔离应用程序的保护机制:
内核为每个应用程序分配一组用于网络收发的内存页,并用这组内存页设置网络适配器。
网络适配器必须保证每个应用程序只能从分配给它的内存页中读写。
问题
功能需求:
当应用程序P发出读写请求时,适配器必须验证请求中指定的页属于P的合法页集合。
朴素的解决方案:
将合法页的页号组织在一个线性表中,适配器顺序检查。验证的代价为O(n) ,n为合法页的数量。
问题:
如果n很大,如何加速验证的过程?
分析
运用P15,设计更好的数据结构:
哈希表:平均查找时间O(1),但冲突概率小的哈希函数计算复杂度高,最差性能不能保证。
二分查找:可以提供lonN的最坏查找时间,但当N较大时开销也比较大(要求排序)。
分析
运用P15,设计更好的数据结构:
哈希表:平均查找时间O(1),但冲突概率小的哈希函数计算复杂度高,最差性能不能保证。
二分查找:可以提供logN的最坏查找时间,但当N较大时开销也比较大(要求排序)。
采用系统思维:
令应用程序在请求中传递一个线索,帮助适配器快速找到指定的页。(P9,在模块接口中传递线索)
解决方案
适配器将不同应用的合法页号保存在不同的数组中。
应用在读写请求中向适配器传递一个句柄,指出指定的页号在数组中的索引。
适配器使用该句柄快速查找并验证页号。
最坏情况性能:一次数组查找,一次比较操作。
ATM流量控制调度器
ATM是一种面向连接的网络:
通信前先建立虚电路(VC),然后在VC上传输长度为53字节的信元(cell)。
ATM适配器可同时支持几百条已经建立的VC。
每条VC上使用流量控制限制其发送速度。
VC上的流量控制:
VC每隔一定的时间获得一些credit,每个credit可以发送一个信元。
VC状态表