本小节基于内核堆区管理器的特点提出了使用静态页身份数组的方法,以避免对现有内核数据结构的依赖。此外,该方法还支持监控程序对静态数组的随机访问。然而,当监控程序和其他内核程序同时访问PIA数组项时,仍然存在数据同步问题。例如,当监控程序正在读取PIA数组项时,另一个内核程序可能正在对这个数组项进行更新操作。若不解决这种同步问题,读取PIA数组项内容的一致性将无法得到保证,进而导致监控程序无法正确获取内核堆区的守卫值。
在介绍内核巡航算法之前,本小节将首先讨论由于共享PIA所产生的竞争条件。怎样处理这些竞争条件是半同步算法设计的关键。本小节将访问PIA的程序分为三类:监控程序、请求分配堆区页面的内核程序和请求释放堆区页面的内核程序。当监控程序和内核程序同时访问PIA数组项时,将随之产生各种竞争条件。
5.4.2.1 非原子性的写操作问题
由于更新PIA数组项的操作并不是原子操作,因此如果允许多个程序同时修改同一PIA数组项,将产生竞争条件,并可能破坏该数组项中内容的一致性。虽然可以使用基于加锁的同步机制来解决这一问题,但是该方法可能会给系统带来较大的性能开销,并且还可能阻塞操作系统对内核堆区的正常操作。
5.4.2.2 非原子性的读操作问题
当监控程序正在读取某个PIA数组项时,另一个内核程序可能正在对该数组项中的内容进行更新。又由于更新PIA数组项的操作不是原子操作,所以监控程序可能无法正确获取PIA数组项的内容。(www.xing528.com)
5.4.2.3 边检查边使用的问题
当监控程序正在对内核堆区中某个内存页面进行检查时,恰好该页面可能正从内核堆区移出。因此,监控程序很可能会产生误报信息。为此,可采用两次检查标记的方法来判断守卫值发生变化的页面是由于竞争条件造成的还是因为发生了真正的缓冲区溢出。具体来说,在每一个PIA数组项中保存了一个标记(flag)字段。如果该字段为1,则表明该物理页面被内核堆区使用;反之,则表明该内存页面没有被内核堆区使用。当某个内存页面从内核堆区移出时,内核程序将把PIA数组项中标记字段清零。如果监控程序此时检测到PIA数组项所对应的内存页面发生了缓冲区溢出,将会进一步检查PIA数组项中的标记,以确认该页面是否还在内核堆区中。只有当内核堆上缓冲区的守卫值被改变并且PIA数组项中对应标记为1时,监控程序才能真正报告缓冲区溢出。然而,这种方法仍然无法避免以下将要讨论的ABA问题。
5.4.2.4 ABA问题
ABA问题发生于以下情况:当一个程序在某个内存位置读取到A时,该程序为了确定下一次该位置的值没有发生变化,就再次读取该位置的值,并且和前一次读取的值A进行比较。如果相同,则说明该位置的值没有发生变化。然而,在两次读操作之间可能发生其他操作,例如其他程序可能会修改该位置的值,将其从A改成B,然后又改回成A。在Kruiser系统中,监控程序可以通过两次读取PIA数组项中的标记,判断对应的内存页面是否仍然被内核堆区所使用。因为相关的内核程序可能会在这两次读操作之间将对应内存页面从内核堆区移出,然后又可能将该页面重新移入内核堆区,所以两次检查标记的方法仍然不能消除由ABA问题带来的误报。
与基于现有数据结构的方法相比,本小节并没有避免数据的同步问题,而是将其转移至PIA数组中。然而基于该静态数据结构,作者提出半同步非阻塞算法,使Kruiser能在不产生误报和不影响系统性能的前提下解决以上所有问题。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。