1.1.1.1 FIFO/XM V2.0
与FIFO/XM V1.0相比，FIFO/XM V2.0有两处改进，1）Lock-Free机制的使用避免了阻塞竞争机制的使用，2）将FIFO模块从XtratuM内核中分离。在FIFO/XM V1.0中，基于阻塞机制的信号量和中断屏蔽被使用，从而降低了系统的吞吐率和事件相应速度。尤其是低优先级域可能阻塞高优先级域，从而引起实时域的无法接受和无法预料的延迟。因此，在FIFO/XM V2.0中，基于阻塞的竞争条件被抛弃而引入了Lock-Free机制。
基于Lock-Free机制的FIFO通常是一个链表，一次数据的读写是一个存储在节点上的数据块。通常，链表节点的建立通过静态或动态的内存分配。静态分配虽然可以节约时间，但是要消耗大量被锁住的内存，并且如果数据块小的话，会有大量内存浪费，对于内存相对匮乏的嵌入式系统，显然静态节点不合适。采用动态节点分配方法的话，不仅存在上面这种问题，同时还具有效率低的问题。因此，对于嵌入式实时系统域，基于链表的两种FIFO实现方法都存在缺陷。在FIFO/XM V2.0中，我们采用一个数组作为FIFO。众所周知，数组FIFO具有最大的优势是实现简单，但是，采用数组FIFO还有下面几个原因[42]。
l 每一个FIFO只占用20字节存放控制信息，也就是说，无论FIFO的最大存储数据有多大，其额外内存空间只有20字节；
l 静态内存空间避免了运行时内存分配。
在FIFO/XM V2.0中，FIFO是一个具有固定内存大小的循环队列，并且，每一个FIFO具有独立的控制区，用来保存控制信息。在控制区域里面，TOP和BOTTOM标记是两个重要的成员，它们分别指向FIFO的头和尾。 因此，在写操作中，TOP标示会被使用，而在读操作中，BOTTOM标示会被使用。下面的两段代码分别给出了FIFO的读写函数算法。
integer read(fd, dst, count)
BEGINE
...
do {
old_bottom = fifo[i].bottom;
new_bottom = old_bottom + read_size;
read_data();
} while(!CAS(&fifo[i].bottom, old_bottom, new_bottom))
...
END
integer write (fd,srct, count)
BEGINE
...
do {
old_top = fifo[i][fifo_num].top ;
new_top = old_top + write_size;
write_data();
while(!CAS(&fifo[i][fifo_num].top, old_top, new_top));
...
END
从算法中可以看出，CAS操作通过检查TOP和BOTTOM的值来判断读或者写操作是否被中断。但是在传统的策略中，它们的取值范围是从0到FIFO_SIZE。因此，当前存在一个很高的概率，就是老的BOTTOM值与中断后修改的新BOTTOM值相等，从而迷惑了任务的判断能力。为了降低这种冲突，在实现过程中，TOP和BOTTOM的取值范围是从0到0xFFFFFFFF。当然，在数值使用之前，TOP和BOTTOM的数值会被转换成有效的索引。
在FIFO访问中，有四种潜在的抢占场合：RR(读任务抢占读任务)，RW(读任务抢占写任务)，WR(写任务抢占读任务)，以及WW(写任务抢占写任务)。上面给出的算法，仅仅可以避免RR，RW，和WR问题，对于WW问题，该算法无法避免，为此，系统采用的是阻塞型写操作方式。因此，在设备使用中，应该尽量避免多个任务向同一个FIFO里面写数据。图2-13给出了RR问题模型。
图2-11. RR问题模型
图2-13中，低优先级任务读取数据时被高优先级任务中断，部分数据被高优先级任务读出，当具有低优先级的任务重新被唤醒时，低优先级任务检查出BOTTOM数值已经发生改变，从而判断有高优先级任务被抢占自己并读取数据并导致数据发生变化，根据判断结果，低优先级任务重新从FIFO中读取数据。从而可以避免阻塞高优先级任务并且保持数据的一致性。
1.1.1.2 FIFO/XM V3.0
在FIFO/XM V3.0中，丢弃了V1.0和V2.0中的读写Hypercalls，并且FIFO的数据内存和控制内存被映射到上层域内核空间，另外，FIFO/XM V3.0支持更多的FIFO操作功能。
前面的章节中已经介绍了内存映射，即如何通过创建页表来连接虚拟内存和物理内存。XtratuM系统如何完成内存映射，即建立页表的过程将在下面的内容中介绍。
创建页表之前需要准备两个重要资源，虚拟内存空间和物理地址空间。连续虚拟内存空间主要包含虚拟地址和虚拟地址空间大小。物理地址空间包含物理内存地址(可以是连续的，也可以是以页为单位离散的)，以及物理内存。物理内存将会从虚拟地址开始被映射到应用域虚拟地址空间中，其中物理内存是在FIFO模块加载时分配，并且常驻内存。内存映射时，首先，虚拟内存空间地址被转换为PGD索引和PTE索引。其次，检验PGD[PGD_INDEX]的标记位，如果“被占用”位被设置，则表明对应的PTE已经被分配，否则的话，新的保存PTE检索的物理页将会被分配用以保存相应检索号。再次，检查PTE[PTE_INDEX]标记位，PTE标记位的处理不同于PGD标记处理。如果相应的位被设置，则表明该域对应的虚拟地址空间已经被分配或占用，映射过程将会被中断，否则，物理地址将会被填入相应检索项中。
在XtratuM系统中，系统只提供了一套内存管理策略，当域被加载时，物理内存被映射的新域的虚拟地址空间，当域被卸载时，相应页表和内存被释放。依照通用内存管理策略，域在卸载时，FIFO物理内存也将会被释放，由于FIFO的物理内存被多个域映射到各自的虚拟地址空间中，FIFO物理内存的释放将会导致其它域无法安全访问该段内存，从而可能导致系统崩溃。因此，为了支持FIFO这种特殊的内存映射机制，在FIFO/XM中，内存映射表中添加了新的标志位：PAGE_SHARED。当FIFO物理内存地址空间被映射时，PAGE_SHARED位被设置，同样，在域被卸载时，标有PAGE_SHARED的PTE索引仅仅被清除，其对应的物理内存不会被释放。FIFO内存映射的算法如下。
long allocate_fdata_page (pd, vaddress, index, alloc_page)
BEGIN
...// Same as the allocate_user_page()
if [pte item of vaddress is used]
BEGIN
return 0;
END
else
BEGIN
//in the allocate_user_page ()
//allocate new physical memory.
//In the allocate_fdata_page,
//only calls get_fifo_data_page_addr routine
page = get_fifo_data_page_addr(index);
fill the pte entry tabl;e
//set the flag value
//_PAGE_PRESENT | _PAGE_RW | _PAGE_USER
set the flag value (_PAGE_PRESENT | _PAGE_RW | _PAGE_USER | _PAGE_ACCESSED);
//_PAGE_ACCESSED marks the page is shared.
return address.
END;
END;
在域的虚拟地址空间中，物理内存是从0x2000000地址开始被映射的。前面的地址空间被域保留给设备的I/O地址。在域空间中，被使用的虚拟地址从0x2000000到0x2304000。在XtratuM系统中，FIFO的物理内存从0x2c00000开始映射。第一页用来存放FIFO设备的控制信息。后面的内存用来存放FIFO数据页，从而域直接对FIFO内存空间访问提供了可能性。除了在FIFO/XM V3.0中添加内存映射机制以外，在FIFO系统中，新的FIFO控制操作被添加。用户可以通过FIFO提供的ioctl()函数对FIFO进行控制。图2-14给出了FIFO/XM V3.0的结构模型。
图2-12. FIFO/XM V3.0结构