OS缓冲管理中数据处理时间函数研究

张刚园，邱传曦

(西华师范大学 计算机学院，四川 南充 637009)

在现代操作系统中，几乎所有的I/O设备在与处理机交换数据时都用到了缓冲区。操作系统的缓冲技术大致可分为单缓冲、双缓冲、多缓冲、循环缓冲(环形缓冲)、缓冲池等。本文仅研究单缓冲和双缓冲机制下系统对数据块处理的时间函数。

1 存在的问题

在块设备输入时，从磁盘把1个数据块(缓冲区装满即为一个数据块，最后一块可能装不满)输入到缓冲区的时间为T，将缓冲区中的数据块传送到用户区的时间为M，CPU对一个数据块的计算时间为C，则系统对1个数据块处理的时间，对单缓冲而言,多数著作认为是Max(T,C)+M[1-6]；对双缓冲而言，文献[1-2,4]给出的结论是可以粗略地认为是Max(C，T)，文献[3]给出的时间函数为Max(T，M+C)，文献[5-6]给出的结论是:当CT时为Max(C,T)+M。而文献[7-10]未对数据块处理时间进行分析。

综合分析上述结论，主要存在如下问题：

(1)缺乏前提条件

上述系统对1个数据块的处理时间结论，缺乏如下前提条件：系统中只有输入进程和计算进程，按单道方式运行和非抢占方式调度，进程切换所花时间忽略不计。缺乏这些条件，则上述结论不成立。

(2)忽略了缓冲区大小与工作区大小对数据块处理时间的影响

上述文献中在单缓冲机制得出的对1个数据块的处理时间函数，在缓冲区大小与工作区大小相同时成立，而在缓冲区远小于工作区时，则不成立；在双缓冲机制下，给出的数据块处理时间的结论不一致，不完整，完全没有考虑缓冲区大小和工作区大小对处理时间的影响，对问题的分析不够全面。

2 单缓冲机制下数据处理时间函数分析

2.1 单缓冲区工作机制

单缓冲是系统所提供的最简单类型缓冲区设置，如图1所示。当用户进程发出一I/O请求时，系统为其分配一个缓冲区。对于块设备来说，先将1个数据块输入到缓冲区，然后将缓冲区中的数据传送到工作区，最后由系统对其进行计算处理[1]。

2.2 单缓冲机制下数据块处理时间函数的分析

当数据块为1时，系统对该数据块处理的总时间为T+M+C；而要处理大量的数据块时，分为如下几种情况。

2.2.1 缓冲区大小等于工作区大小

1)T

假设T=10，M=1，C=20。该情况下单缓冲工作过程图和数据块处理时间表如图2及表1所示：

表1 数据块处理时间表(缓冲区大小=工作区大小，T

从图2和表1可知：数据块传输完成后即可开始第1数据块的计算,同时进行后一数据块的输入，即Ti与Ci-1两个操作并行；由于缓冲区大小=工作区大小，所以后一数据块必须等待前一数据块计算完成后才能开始传输，即Ci-1完成后进行Mi操作。

由上述可得，当T

2)T>C

假设T=20，M=1，C=10。该情况下单缓冲工作过程图和数据块处理时间表如图3及表2所示：

表2 数据块处理时间表(缓冲区大小=工作区大小，T>C)

从图3和表2可知：数据块输入完成后开始数据块的传输，传输完成后开始第1数据块的计算，同时进行后1数据块的输入，即Ti与Ci-1两个操作并行；由于T>C，后1数据块输入完成时，工作区已经被“抽空”，所以后1数据块可以立即传入工作区。此时，除第1数据块外，系统对后续的每一数据块的处理时间为M+T，即Max(C,T)+M。

所以，在缓冲区大小等于工作区大小时，系统对每一数据块处理的时间函数为Max(C,T)+M。

2.2.2 缓冲区大小远小于工作区大小

在此情况下，数据块由缓冲区传送到工作区不受影响，缓冲区装满即可传送至工作区。

1)T

假设T=10，M=1，C=20。该情况下单缓冲工作过程图和数据块处理时间表如图4及表3所示：

表3 数据块处理时间表(缓冲区大小<<工作区大小，T

从图4和表3可知：数据块输入完成时即可传输数据块，传输完成时开始后1数据块的输入，由于缓冲区远小于工作区，所以输入完成后可以立即传入工作区。此时，Ti+Mi与Ci-1两个操作并行。所以，此情况下除第1数据块外，系统对每1数据块的处理时间为C；进一步分析当T

表4 数据块处理时间表(缓冲区大小<<工作区大小，T>C )

2)T>C

假设T=20，M=1，C=10。该情况下单缓冲工作过程图和数据块处理时间表如图5及表4所示

从图5和表4可知：数据块输入完成时开始传输，传输完成时开始计算，同时进行下个数据块的输入，即Ti与Ci-1两个操作并行，此时，除第1数据块外，系统对每个数据块的处理时间为T+M，即可表示为Max(T，C)+M。

所以，除第1块数据块外，在缓冲区大小远小于工作区大小时，当T+MC时，处理时间为T+M。即系统对每一块数据的处理时间为Max(T+M,C)。

综上所述，在缓冲区大小等于工作区大小时，系统对每一数据块处理的时间函数为Max(C,T)+M；在缓冲区大小远小于工作区大小时，系统对每一块数据的处理时间函数为Max(T+M,C)。

3 双缓冲机制下数据处理时间函数分析

3.1 双缓冲区工作机制

为了提高输入/输出设备的速度效率，提高系统的并行能力，在内存中开辟双缓冲区。双缓冲区是指操作系统为一个用户分配两个缓冲区，如图3.1所示。在输入数据时，首先输入设备将数据输入缓冲区1，在缓冲区1装满后在输入缓冲区2。如果缓冲区1已经被输入数据装满，在操作系统将缓冲区1中的数据取到工作区期间，缓冲区2可以接收输入数据。如果缓冲区2已经被输入数据装满，在操作系统将缓冲区2中的数据取到工作区期间，缓冲区1可以接收输入数据。缓冲区1和缓冲区2交替使用，只要缓冲区中的数据输入到工作区后，处理器就可以执行用户进程[1]。

3.2 双缓冲机制下数据块处理的时间函数分析

当系统只处理1个数据块时，系统对该数据块的处理时间同单缓冲一致；当需要处理的数据仅有2个数据块时，处理的总时间为Max(C,T)+T+M+C；而要处理大量的数据块时，分为如下几种情况。

3.2.1 缓冲区大小等于工作区大小

1)T

假设T=10，M=1，C=20。该情况下双缓冲工作过程图和数据块处理时间表如图7及表5所示：

从图7和表5可知：除前2个数据块外，与图2和表1完全一致，所以在该情况下系统处理1个数据块的时间函数为Max(C,T)+M，这与文献[1-2，4]结论显然不同，虽然M比T或C小得多，但如果处理的数据块数量特别大时，偏差就会很大 。

表5 数据块处理时间表(缓冲区大小=工作区大小，T

2)T>C

假设T=20，M=1，C=10。该情况下双缓冲工作过程图和数据块处理时间表如图8及表6所示：

从图8和表6可知：数据块输入完成后开始传输数据，同时将下一数据块向缓冲区2输入，传输完成时开始计算。即Ti与Mi-1+Ci-1两个操作并行，所以，此情况下除前2个数据块外，系统对每一个数据块的处理时间为T，进一步分析当C

表6 数据块处理时间表(缓冲区大小=工作区大小，T>C)

所以，在缓冲区大小等于工作区大小时，除前2个数据块外，当T>M+C时，处理时间为T；当T

3.2.2 缓冲区大小远小于工作区大小

1)T

假设T=10，M=1，C=20。该情况下双缓冲工作过程图和数据块处理时间表如图9与表7所示：

表7 数据块处理时间表(缓冲区大小<<工作区大小，T

从图9和表7可知：数据块输入完成后进行数据传输，同时下一数据块开始输入，计算完成便进行下一数据块的计算。所以，Ti+Mi与 Mi-1+Ci-1两个操作并行，当T+M

2)T>C

假设T=20，M=1，C=10。该情况下双缓冲工作过程图和数据块处理时间表如图10及表8所示：

表8 数据块处理时间表(缓冲区大小<<工作区大小，T>C)

从图10和表8可知：数据块输入完成后进行数据传输，同时下一数据块开始输入，传输完成便进行计算。因此，Ti与Mi-1+Ci-1两个操作并行，当T>C+M时，该情况下数据的处理时间为T。进一步分析当C

所以，在缓冲区大小远小于工作区大小时，当TC时，处理时间为T。除前2块数据块外，系统对每一块数据的处理时间为Max(T,C)。在深入分析发现输入、传输、输出三个过程是并行的，由于数据的传输在内存中进行速度非常的快，即M远小于T和C，所以可得到上述结论，也可以把这种情况下的时间函数准确表示为Max(T,M,C)。

综上所述在缓冲区大小等于工作区大小时，系统对每一数据块的处理时间为Max(T,C+M)；当缓冲大小远小于工作区大小时，系统对每一块数据处理时间为Max(T,M,C)。

4 总结

在系统按单道方式运行，并按非抢占方式调度，进程切换所花时间忽略不计的前提下，在单缓冲机制中，当缓冲区大小等于工作区大小时，系统对1个数据块的处理时间函数为Max(C,T)+M；当缓冲区远小于工作区大小，系统对每块数据块的计算函数也为Max(C,T+M)；在双缓冲机制中，当缓冲区大小等于工作区大小时，系统对1个数据块的处理时间函数为Max(T,C+M)。当T

参考文献：

[1] 汤小丹，梁红兵，哲凤屏，等.计算机操作系统[M].第四版.西安:西安电子科技大学出版社，2014.

[2] STALLINGS W.Operating systems internals and design principles[M].6th ed.北京：机械工业出版社，2010.

[3] 许曰滨，孙英华，赵 毅，等.计算机操作系统[M].第一版.北京：北京邮电大学出版社，2007.

[4] 范 策，李 畅，黄红桃，等.操作系统教程[M].第一版.北京：北京清华大学学研大厦A座，2011.

[5] 费翔林，骆 斌.操作系统教程[M].第五版.北京:高等教育出版社，2014.

[6] 孙钟秀，费翔林，骆 斌，等.操作系统教程[M].第三版.北京:高等教育出版社，2003.

[7] 张丽芬，刘美华.操作系统原理教程[M].第三版.北京:电子工业出版社，2013.

[8] 谢青松.操作系统原理[M].第一版.北京:人民邮电出版社，2005.

[9] 王 红.操作系统原理及运用(Linux)[M].第一版.北京：中国水利电出版社，2005.

[10] DAVIS W S，RAJKUMAR T M.Operating Systems:Systematic View[M].5th ed.北京：电子工业出版社，2003.