智能网络磁盘系统的任务排序研究.pdf

第36卷第9期
计算机工程
2010年5月
b.36
9
Computer Engineering
May 2010
软件技术与数据库
文章编号1000-3428(2010)09-0041-03文标识码:A
中图分类号TP311
智能网络磁盘系统的任务排序研究
刘娜,赵跃龙
(华南理工大学计算机科学与工程学院,广州510640)
摘晏:針对智能网络磁盘存储系统中已有的排序算法会导致大量任务长期得不到响应而引起的“饥饿现象,对该算法进行改进。将任
务划分成步骤链并根据步骤链的执行时间及权重计算出p因子,设定P因子的浮动限△6和所在任务的已执行时间限r。实验结果表明
改进的排序算法能很好地解决“饥饿”现象,使任务的加权总完成时间近似最优。
关词:智能络磁盘;排序算法;时间复杂性;三元组
Study ont'ask Schedule in Intelligent Network Disk System
LIU Min-na, ZHAO Yue-long
(School of Computer Science and Engineering, South China University of Technology, Guangzhou 510640)
T Abstract To overcome the starvation phenomena caused by the existing algorithm for the response time of a ot of ass is longer in the
Inte nt Network Disk(ND sysem an improved algoithm is preseed n the algrithm, factors of asks are computed by the execution time
and weight of se chains, and the range of fac ors and the limit of e ed time of tasks are set Expmenal results demonstrate that it sols
the starvation phenomena at a certain extent and makes the weighted total completion time approximately best.
fkey words Intelligent Network Disk(ND) hedule algorithm; time complexity; triple
1概述
主IND选举产生后,在当前开始的一个时间段内,该主IND
Internet技术的飞速发展及多媒体的应用导致了信息量不仅要存储相关信息,而且最主要的是要接收客户端的任务,
的燝炸性增长,如何有效地存储这些信息日益成为人们关注并且把任务分配给相关的辅JND集群
的焦点。除了不断地增加各种存储介质的容量,大量的研究
过一段时间后再次选出另外一个主IND并且使当前的主
人员对各种存储结构进行了研究,目前广泛应用的存備结构IND变为辅IND。在IND中,主IND只有一个,它的主要作
主有NAS和SAN2。但是,这2种结构都存在各自的问用是作为一个对外接口接收任务。其具体结构如图1所示
题:如NAS虽然实现了数椐流和控制流的分开管理,但是
存在单点失效问题;SAN虽然可以取得较快的速度,但枃建
9 5p
LO求
和维护成本歸贵。
智能网络量
针对上述问题,文献[3]提出了一种新的存储结构一智
能网络磁盘( Intelligent Network Disk,IND)存储。智能网络磁
)
D请求
盘存储系统采用选举制度,选出一个主[ND和许多辅IND
p
主IND主要用于接收任务,将任务按照某种方式分配给各个
I/O请求
箱ND。文献[4」提出了一种排序算法,该算法把未加工的连
Z O
P
续的任务串成链,根据各个步聚的权重和处理时间的比值,
算出所有未加工链的权重和时间的比值,从中选取比值最大
的链执行。该算法可以使加权总完成时间最优,但会导致权
重较小的任务长期得不到响应而引起操作系统中出现“饥饿
因1智网特盘存系坑结
现象。本文通过对已有历史数据的研究,对该排序算法进行3ND中任务的处理
改进,使其更适用于IND的具体应用情况。
在每个时刻都会有批量的任务到达,而且每个任务的优
2智能网络磁盘存储系统的体系结构
先级及处理时间各不相同。如何在考虑优先级的情况下使这
智能络磁盘存储系统主婆由各个ND构成,这里的磁些任务的加权完成时间最短,并且能够兼顾公平原则,孤不
盘不仅具有简单的存储功能,而且具有一定的智能性,即具会使有些任务长期得不到响应,这是本文最关心的问题。任
有进行1/0处理、数据分布处理、容错等功能。因为在IND金项目:国家自然科学基金资助项目(60573145);教育部博土点基
存储系统中,每个IND都直接面向网络用户,任何一个IND金资助项目(200805610019;湖南省自然科学基金资助项目(O5J
都具有响应客户端任务的能力(只要它“空闲”),所以当网30120);广州市科技计划基金资助项目(20071-200403)
络中某个文件任务随机到达时,可能发生“存储竟争”的无作者介:刘娜(1985-),女,硕土研究生,主研方向:网络存
序性现象。为了避免这种现象发生,各个IND通过某种智能赵跃龙,教授、将士、博土生导师
算法自动选举一个IND作为主IND,其他的都是辅IND。在收務日期:2001010E-mal:liuminna(@sina.com
万方数据