《网络算法学》课程教学资源（PPT课件讲稿）第四章 原则的运用

第四章原则的运用

第四章 原则的运用

4.1应用设备通道的缓冲区验证 *应用程序通常必须通过系统调用收发包: *只有内核可以与网络适配器直接交互 *由内核统一操纵J/O设备便于实现应用程序之间的 隔离 *但是系统调用引入了开销 *应用设备通道( Application Device Channels): *为降低开销,允许应用程序直接读写网络适配器的 存储区域来进行网络收发

4.1 应用设备通道的缓冲区验证  应用程序通常必须通过系统调用收发包：  只有内核可以与网络适配器直接交互  由内核统一操纵I/O设备便于实现应用程序之间的 隔离  但是系统调用引入了开销  应用设备通道（Application Device Channels）：  为降低开销，允许应用程序直接读写网络适配器的 存储区域来进行网络收发

应用设备通道的基本思想 基本思想: *将网络适配器内存看成是主存的一部分,采用虚拟存储 系统进行管理 *将网络适配器内存划分成一系列物理页,预先为每个应 用分配一定数量的物理页,并映射给应用程序使用 *由于空间有限,数据包存放在位于主存的包缓冲区中, 适配器内存中只存放包缓冲区的描述符 *收发数据包之前,应用将需要使用的包缓冲区描述符写 入适配器内存,供适配器使用 *需要一种隔离应用程序的保护机制: *保证每个应用只能读写分配给它的包缓冲区

应用设备通道的基本思想  基本思想：  将网络适配器内存看成是主存的一部分，采用虚拟存储 系统进行管理  将网络适配器内存划分成一系列物理页，预先为每个应 用分配一定数量的物理页，并映射给应用程序使用  由于空间有限，数据包存放在位于主存的包缓冲区中， 适配器内存中只存放包缓冲区的描述符  收发数据包之前，应用将需要使用的包缓冲区描述符写 入适配器内存，供适配器使用  需要一种隔离应用程序的保护机制：  保证每个应用只能读写分配给它的包缓冲区

隔离应用程序的保护机制 *操作系统将映射给每个应用的物理内存页页号告知适配器 *适配器检查应用程序给出的页号是否在合法的页号集合中 Memory CPU Page X Application P Receive next Kernel acket into Page A Page A Valid list for P Xy…L,A| ADAPTOR NETWORK FIGURE In application device channels, the network adaptor is given a set of valid pages (X, Y, L, A, etc. for a given application P. When application P makes a request to receive data into page A, the adaptor must check if A is in the valid list before allowing the receive

隔离应用程序的保护机制  操作系统将映射给每个应用的物理内存页页号告知适配器  适配器检查应用程序给出的页号是否在合法的页号集合中

问题 *功能需求: *当应用程序P发出读写请求时,适配器验证请 求中指定的页在P的合法页集合中 *朴素的解决方案: *将合法页的页号组织在一个线性表中,适配器 顺序检查。验证的代价为on),n为合法页的 数量 问题: *如果n较大,如何加速验证的过程?

问题  功能需求：  当应用程序P发出读写请求时，适配器验证请 求中指定的页在P的合法页集合中  朴素的解决方案：  将合法页的页号组织在一个线性表中，适配器 顺序检查。验证的代价为O(n) ，n为合法页的 数量  问题：  如果n较大，如何加速验证的过程？