OS缓冲管理中数据处理时间函数研究
2018-07-05张刚园邱传曦
张刚园，邱传曦
(西华师范大学 计算机学院，四川 南充 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]给出的结论是:当C
综合分析上述结论，主要存在如下问题：
(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+M 综上所述，在缓冲区大小等于工作区大小时，系统对每一数据块处理的时间函数为Max(C,T)+M；在缓冲区大小远小于工作区大小时，系统对每一块数据的处理时间函数为Max(T+M,C)。 为了提高输入/输出设备的速度效率，提高系统的并行能力，在内存中开辟双缓冲区。双缓冲区是指操作系统为一个用户分配两个缓冲区，如图3.1所示。在输入数据时，首先输入设备将数据输入缓冲区1，在缓冲区1装满后在输入缓冲区2。如果缓冲区1已经被输入数据装满，在操作系统将缓冲区1中的数据取到工作区期间，缓冲区2可以接收输入数据。如果缓冲区2已经被输入数据装满，在操作系统将缓冲区2中的数据取到工作区期间，缓冲区1可以接收输入数据。缓冲区1和缓冲区2交替使用，只要缓冲区中的数据输入到工作区后，处理器就可以执行用户进程[1]。 当系统只处理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 所以，在缓冲区大小远小于工作区大小时，当T 综上所述在缓冲区大小等于工作区大小时，系统对每一数据块的处理时间为Max(T,C+M)；当缓冲大小远小于工作区大小时，系统对每一块数据处理时间为Max(T,M,C)。 在系统按单道方式运行，并按非抢占方式调度，进程切换所花时间忽略不计的前提下，在单缓冲机制中，当缓冲区大小等于工作区大小时，系统对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.
3 双缓冲机制下数据处理时间函数分析
3.1 双缓冲区工作机制
3.2 双缓冲机制下数据块处理的时间函数分析
4 总结
