ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



ǹ̶˫ͷʵʱ㷨о*
ХƼڷҡʤ
ժҪ¸һʵʱǹ̶˫ͷϵͳʽģ.ôģеÿ˫ͷ̶໥ĴűۣܹѰҴŵ.Ըôϵͳо3ʵʱ㷨.ģʵԳֹڵ㷨ãΪ˶ԳֹʵʱĴ.ͬʱ˹̶˫ͷǹ̶˫ͷ֮ܲ.ʵڷǹ̶˫ͷ̵ͷԶѰҴŵ˷ǹ̶˫ͷ̵ܱȹ̶˫ͷ̵Ҫ.
ؼʡǹ̶˫ͷ̣ʵʱ̵㷨I/Oģʵ飬.
ͼšTP316
Study of Real-time Disk Scheduling for Two-headed Mirrored Disk with Autonomous Heads
QIN Xiao,PANG Li-ping,HAN Zong-fen,LI Sheng-li
(School of Computer Science and TechnologyHuazhong University of Science and Technology Wuhan430074)
AbstractA real-time model for two-headed mirrored disks with autonomous heads is proposed in this paper. Two-headed disks (THD) in this system have two independent arms which can seek cylinder autonomously. Three real-time disk-scheduling algorithms are presented for such disk systems. According to simulation experiments, the algorithm which is called ignore missed deadlines (IGM-EDF) has the best performance, because IGM-EDF does not process those real-time requests which have missed deadlines. The comparison between two-headed mirrored disk with fixed heads(FTMD) and the disk system with autonomous heads (ATMD) is also analyzed in this paper. Because two heads in THD can seek cylinder independently, the performance of ATMD is better than that of FTMD.
Key wordsTwo-headed mirrored disk with autonomous heads, real-time disk scheduling, I/O request, simulation experiment, performance evaluations.
˫ͷϵͳģ.һģǹ̶˫ͷ̣ģ͵Ĵűͷͷ㶨.ӦһI/OʱͷͬʱƶһͷƶI/OĴŵϣһͬķƶͬľ룬ģPageWood19811.ף2,3ݷֱо˸ģ͵ȷ(first come first serve,FCFS)SCAN㷨.һǷǹ̶˫ͷģִͣģ໥ĴűۣܶѰҴŵḶ́4.ף5,6ݷֱоģ͵Ĵͷƽƶ͵ݵ㷨.ף7ݶģ͵ƽҵʱо.ϵͳɶɣÿ̵ͬ.I/OǶѡͷĴŵĴȥɶддϣ8.˫ͷϵͳɶ˫ͷɣÿ˫ͷ̴洢ͬ.ף9,10ݷֱо˸ôϵͳĲλͶѰʱȵ㷨.ף11ݼ˫ͷϵͳĴͷƽѰ.
ʵʱݿϵͳʵʱϢϵͳӦԽԽ㷺ЩʵʱӦҪʵʱI/O֧.ף12˻UNIXʵʱI/O㷨.ף13˫ͷϵͳʵʱ㷨.ף14,15о˵ͷ̺˫ͷ̵ʵʱ㷨ף15ݽо˹̶˫ͷϵͳ(two-headed mirrored disk with fixed headsFTMD).ҪǶԷǹ̶˫ͷϵͳ(two-headed mirrored disk with autonomous headsATMD)ʵʱ㷨ܽзȽִģ͵ʵʱܲ.
1ǹ̶˫ͷϵͳʵʱģ
ʵʱI/Oнֹ.ʵʱ㷨ڽеʱʹýֹ.ʵʱģͰ77ϵͳ.ǹ̶˫ͷģ.
1. ÿ˫ͷ̶ΪһԪ,THD=(id,st,rtio,h1,h2),idǴ̵ıţstǴ̵ǰ״̬̾æͿ״̬THD.st=BUSY|FREErtioǴTHDI/Oh1h2 ʾͷλãh1h2h1ʣ1,MCh2ʣ1,MCݣMCʾ̵ŵ.
2. ˫ͷϵͳΪһ̼.ϵͳk˫ͷ̣TMD={d1,d2,...,dk};diһTHD,i=1,2,...,k.TMDӼTMD=FSBSFSBS=,FSǿд̼,BSæ̼FS={d|d.st=FREE,dTMD},BS={d|d.st=BUSY,dTMD}.
3. ʵʱI/OʾΪһԪ:RTIO=(rw,c,dk,at,dl).rwI/OͣI/O֣д󣬼rw=READ|WRITEcRTIOҪʵڵĴŵţʵʱI/OҪdkΪdkʣ1,k|ANY-THDdk=ANY-THDʱϵͳеκδ̶ӦʵʱI/OatʵʱI/Oĵʱ䣻dlʵʱI/OɵĽֹ.
4. ˫ͷϵͳеI/OI/O󼯺RSüཻӼRS=WSSS,WSSS=WSǵȴI/OɵļϣڵõϵͳI/OSS.WSk+1Ӽ,Ϊ:WS=RDSWTS1WTS2...WTSk,WSежRDS,RDS={rtio|rtio.rw=READ,rtioWS},WSедdiWTSi,WTSi={rtio|rtio.rw=WRITE,rtio.dk=i,rtioWS},i=1,2,...,k.
5. ڽֹdI/OýֹΪĽֹޣΪĽֹ.dt+Act(n)ʱ,ֹd㣬򲻿㣻I/Oʴ̵ʱAct(n),tǵǰʱ.һI/OĽֹǿģƸI/OǿI/O󣬷ΪI/O.
6. NMS(di)ʾΪI/O󼯺ϣüеʵʱI/OǿI/O󣬼NMS(di)={rtio|rtio.dlΪĽֹ,rtioRDSWTSi}MS(di)ʾΪI/O󼯺ϣMS=(RDSWTSi)-NMS.NMS(di)MS(di)=,NMS(di)MS(di)=RDSWTSi.
7. 庯AH-Seek(d,r)书ǼdӦI/OrʱdĴͷƶľ.AH-Seek(d,r)=|d.h1-r.c||d.h1-r.c||d.h2-r.c|ʱAH-Seek(d,r)=|d.h2-r.c||d.h1-r.c|>|d.h2-r.c|ʱ.
˫ͷϵͳģʱϵͳȷ״̬.
1. WSеRDSWTSiཻ
iʣ1,k(RDSWTSi=).
2. WSеWTSཻ֮
i,jʣ1,k(ijWTSiWTSj =).
3. ̴æ״̬ӦI/OһSSУ
diTMD (di.st=BUSYdi.rtioSS).
4. һ״̬ǿ,ҽӦκI/O񣬲SSûһI/O󱻸ôӦ
diTMD(di.st=FREEdi.rtio=NULLrtioSS(rtio.dki)).
5. ̲ͬͬʱӦһͬI/O
di,djTMD(di.st=BUSY,dj.st=BUSY,ijdi.rtiodj.rtio).
6. дָֻܱĴӦ
diTMD(di.st=BUSY,di.rtio.rw=WRITEdi.rtio.dk=i).
7. һI/OǶϵͳеһ̿Ӧö
rtioRTIO(rtio.rw=READrtio.dk=ANY-THD).
2ʵʱ̵㷨
̵㷨ɲͷɣ15.ǽһ߲URTIOתΪͲRTIO󣬲ɵRTIOWSУϵͳкʵĿд̣ѡôжλI/OWSSS.ϵͳдdiһI/OʱͷŹִУSSɾȥ.ûȴdiӦͷŸộ򰴵ԭѡʵ󣬲̷ʹ.ͷŹнʹõȲSchedule(RDSWTSi)Ľо5ֵ㷨.ȷͶѰʱȵ㷨(short seek-time first,SSTF)ʵʱ㷨9,10.ֹȵ㷨(earliest deadline first,EDF)ڵʱǵȽֹȵʵʱI/OEDFI/OǷ.ڿֹȵ㷨(feasible-earliest deadline first,F-EDF)㷨,ֻЩȵʵʱI/Oȵ.WSеI/O󶼲ʱF-EDFSSTF㷨еȣΪȵȺѲҪ.Գֹڵ㷨(ignore missed deadline-earliest deadline first,IGM-EDF)ֻȿI/OвI/O󽫱ϵͳԵ.ںܶӲʵʱӦУʵʱI/Oڳֹʱú壬,IGM-EDF㷨ʵʱI/OֱӴWSɾ.棬ֱ5ֵ㷨.
ȷ㷨(FCFS).
(1) ѡ rtioRDSWTSirtioRDSWTSi(rtio.atrtio.at);
(2) rtio;
(3) FCFS㷨.
Ѱʱȵ㷨(SSTF).
(1) ѡrtioRDSWTSirtioRDSWTSi (AH-Seek(di,rtio)AH-Seek(di,rtio));
(2) rtio;
(3) SSTF㷨.
ֹȵ㷨(EDF).
(1) ѡrtioRDSWTSi,rtioRDSWTSi(rtio.dlrtio.dl); 
(2)  rtio;
(3) EDF㷨.
ֹڵ㷨(F-EDF).
(1) IF(NMS) THEN DO next step; ELSE DO step (3);
(2) ѡ rtioNMS rtioNMS(rtio.dlrtio.dl); goto (4);
(3) ѡ rtioRDSWTSi rtioRDSWTSi(AH-Seek(di,rtio)AH-Seek(di,rtio));
(4) rtio;
(5) F-EDF㷨.
Գֹڵ㷨(IGM-EDF).
(1) IF(NMS) THEN DO next step; ELSE rtio=NULL; DO step (3);
(2) ѡ rtioNMSrtioNMS(rtio.dlrtio.dl );
(3) IF(MS) THEN  rtioMS(rtioWSֱɾ);
(4)  rtio;
(5) 㷨IGM-EDF.
3ģģ
ģʵʵʱI/Oĵһɹ̣ÿI/O֮ʱAһֲָFA(x)=P{Ax}=1-e-*XЦʵʱI/OĵʣλǸ/s.ÿʵвI/OΪ300 000ҸʵʱI/Oĵ໥.I/OдڵĴŵcһڣ1,MCϾȷֲMC=2000.ÿʵʱI/OӦʱI/OеĵȴʱԼ/д̵ķʱ.ʹʽ(1)/д̵ķʱ䣺
Act(n)=DFsqrt(n)+DCms(1)
nΪͷƶĴŵ,DFΪͷѰʱ,DCΪƽתʱƽݴʱ֮.̸ü1.
1ʵдϵͳ

ŵDiskFactorDiskConstant
20000.889.66ms

ֹʱʽ(2). 
d=Art+Act(n)+Skt,(2)
ArtI/Oĵʱ䣬Sktɳʱ䣻ɳʱһڣMin-Slack,Max-SlackϾȷֲ.ģʵеһҪָǳʱ(percentage of missed deadlines,PMD).ʽ(3)PMD.
Missed Deadlines%=(Missed read requests+Missed write requests)*100/Total requests.
(3)
ָܵƽҵʱ(average seek time,AST)ƽӦʱ(average respond time,ART).ʵ2.
2ģʵ

ֵ
T-requestI/O300 000
Kǹ̶˫ͷ̸110
I/O10210
PRQ10%100%
Min-SlackСɳʱ10ms
Max-Slackɳʱ45ms
Distance̶˫ͷ̵Ĵͷ1001000

4ܷ
4.1ʵ1
ʵȽ˸㷨PMDֵ.ϵͳ4˫ͷ̣PRQֵΪ100%.ͼ1˷ǹ̶˫ͷģ3ֵ㷨PMDֵFCFSEDFPMDһģF-EDFIGM-EDFͬ,EDFIGM-EDFͼ1ʡȥ.,F-EDFIGM-EDF㷨ڸָ¶õ.I/Oʽϵ͵(<70 No./Sec.),㷨PMDֵûкԵĲI/Oؽϴʱ(=150 No./Sec.),F-EDFPMDֱFCFSSSTFļ81.2%43.0%.F-EDF5㷨õģΪȵҿʵʱI/O.SSTFڵ2λFCFS.

ͼ1PRQ=100%,k=4ǹ̶˫ͷ
̵PMDֵI/O֮Ĺϵ
ATMDģܺFTMDģܣ15ȽϷ֣I/Oʽϴʱģ͵ԵĲͬ.磬I/OΪ150 No./Sec.ʱFCFSF-EDF㷨ԣFTMDģ͵PMDֱֵATMDģ͵PMDֵ17.0%8.2%ʹSSTFʱATMDPMDֵFTMDPMDֵҪ16.4%.
4.2ʵ2
ͼ23ֱʾATMDģ͵ASTART.ͼ2ʾSSTFASTֵʼI/OʵӶӣȻSSTFAST˵Ӷ𽥽.F-EDFƽҵʱ俪ʼI/OʵӶӵúܿ죬Ȼٶȱúܻ.ͼ3пԿ㷨I/Oغܵʱ𶼺Сڸ߸£SSTFƽӦʱٵģIGM-EDFART֮FCFSƽӦʱ࣬ΪSSTF㷨ʹűƽѰϵͳЧʺܸ.ͨȽATMDģͺFTMDģͣ15ݵASTARTǵóڵ͸ص£ִģ͵ܺܽӽI/OؽϸʱATMDģ͵FCFSF-EDF㷨ֱܷFTMDģ͵ҪãATMDģ͵SSTFIGM-EDF㷨ȴFTMDģͲһЩ.ͼ4ʾIGM-EDF㷨ƽҵʱ.ģͬص㣺ϵͳд̵ĸǶ٣ASTֵŸصӶӣȻﵽһȶֵ(FTMDȶֵΪ14.8msATMDȶֵ14.6ms).

ͼ2PRQ=100%,k=4ǹ̶˫ͷ̣
ƽҵʱI/O֮Ĺϵ

ͼ3PRQ=100%,k=4ǹ̶˫ͷ̣
ƽӦʱI/O֮Ĺϵ

ͼ4PRQ=100%,ƽҵʱI/O֮
ĹϵʹIGM EDF㷨д̸߶
4.3ʵ3
ʵо㷨PRQĹϵ.ϵͳ4˫ͷ̣˺㶨Ϊ50 No./Sec..ʵеĦָǸ߲I/O󵽴ʣϵͳͲI/OʦsysǦ,kPRQĺ
sys=f(,k,PRQ)=read+write=PRQ+(1-PRQ)k=PRQ+(1-PRQ)kݦˣ(4)
ЦreadwriteֱʾͲдĵ.ʽԿk=1ʱPRQΪֵPRQ=100%;kΪֵʱsysһ.ͼ5ʡFCFSIMG-EDFݣΪFCFSEDFPMDƣIMG-EDFĳʱF-EDFһ.ͼпɿ,۶Ϊ٣F-EDFIGM-EDFܶõģFCFSEDFǲǰ.㷨ͬPMDֵPRQӶ.Ϊʽ(4)пԿk1Ҹ߲I/O󵽴ʦ˺㶨ǰ£PRQԽСsysԽߣϵͳʵʸҲԽߣԳʱҲԽ.ʹF-EDF㷨PMDֵPRQΪ30%90%ʱֱΪ25.3%5.9%.֤ڱʵ£PRQͬʱATMDFTMD15ݵFCFSEDFĳʱʽͬͼԿPRQС70%ʱATMDģ͵SSTFF-EDF㷨ĳʱʾԵFTMDģ.

ͼ5k=4,I/O=50No./Sec.
볬ʱ֮ϵ
4.4ʵ4
ʵоϵͳд̸֮Ĺϵ.I/O󵽴Ϊ40No./Sec.,PRQ=70%̸110.EDFĳʱʽԵFCFSʡEDFĽ.ͼ6ʾ̸6ʱFCFSPMDֵ12.5%12.2%֮,EDFPMDֵȶ11.2%11.1%֮.е㷨PMD̸ֵӶͣҵ̸4,͵ķȱúС(4ӵ10ʱF-EDFĳʱʽ8.9%8.2%FCFS㷨ĳʱʽ14.0%12.2%).ʵָ,ڶʽϸʱ˫ͷϵͳܱȵ˫ͷϵͳõʵʱI/O󣬲ҵ̸4ʱϵͳд̸Ӳʹи.,ϵͳĴ̸Ϊ4ʱʹϵͳܽӽ.ȽATMDFTMDִģͣϵͳI/OزܸߣҶʽϴǰ£FTMDģͶԣ̸4ԺSSTFF-EDFPMDֵܽӽF-EDFPMDֵԵSSTFATMDF-EDF㷨PMDֵԸSSTF㷨PMDֵ.

ͼ6I/O=40No./Sec.=70%
5
˫ͷϵͳʵʱо.һʺʵʱ˫ͷϵͳʽģͣΪ˫ͷϵͳ3ʵʱ㷨3ʵʱ㷨ͳķʵʱ㷨ģ.о˷ǹ̶˫ͷϵͳ.оָ,ǹ̶˫ͷ̵Ҫȹ̶˫ͷ̵Խ.ڽеоǣоֲʽʵʱļϵͳϵṹԷֲʽʵʱļĿԤԽнģͷ.
*оõԤĿ.
ͨѶϵˣХ人430074ѧһ58-501
߼飺Х1974˶ʿҪоΪֲʽʵʱϵͳϵͳ.
ƼŮ1944ڣҪоΪ/ֲʽƣֲʽʵʱϵͳ.
ڷңŮ1950ڣҪоΪֲʽʵʱϵͳ.
ʤ1952ڣҪоΪ/ֲʽϵͳ.
ߵλѧѧ뼼ѧԺ人430074
οף
1Page I P, Wood R T. Empirical analysis of a moving disk head model with two heads separated by a fixed number of tracks. The Computer Journal, 1981,24(4):339341
2Calderbank A R, Coffman E G, Flatto L. A note extending the analysis of two-headed disk systems to more general seek-time characteristics. IEEE Transactions on Computers, 1989,38(11):15841586
3Manolopoulos Y, Kollias J G. Performance of a two-headed system when serving database queries under the scan policy. ACM Transactions on Database System, 1989,14(3):425442
4Deighton K. Time to travel to target cylinders on non-linear discs with two independent seek arms. Information and Software Technology, 1995,37(12):709712
5Deighton K. The number of cylinders traveled for a single device. Database Technology Journal, 1992,4(2):9396
6ХƼ.˫ͷϵͳݵȲ.ƣ1998,19(6):814
(Qin Xiao, Pang Li-ping. Elevator scheduling for two-headed disk system. Computer Engineering and Design, 1998,19(6):814)
7Deighton K. Average time to travel on two headed non-linear discs. The Computer Journal, 1995,38(10):811817
8Lo R W, Matloff N S. Probabilistic limit on the virtual size of replicated disc systems. IEEE Transactions on Knowledge and Data Engineering, 1992,4(1):99102
9ХƼ.λ˫ͷ̵ĵ㷨.ѧ,1998,21(12):11191124
(Qin Xiao, Pang Li-ping. Disk scheduling for two-headed mirrored disk systems using parallel positioning. Chinese Journal of Computers, 1998,21(12):11191124)
10ХƼ.˫ͷ̵SSTF㷨.ƣ1999:20(1):710
(Qin Xiao, Pang Li-ping. SSTFa disk scheduling for two-headed mirrored disk systems. Computer Engineering and Design, 1999:20(1):710
11Vakali A, Manolopoulos Y. Parallel data paths in two-headed disk systems. Information and Software Technology, 1997,39(12):125135
12Ƽ,Х.ʵʱI/Oʵ.ֹ,1997,25(2):4145
(Pang Li-ping, Qin Xiao. Analysis and design of I/O subsystem for real-time operating system. Computer and Digital Engineering, 1997,25(2):4145)
13Х,ڷ,Ƽ.˫ͷϵͳʵʱ㷨.ѧѧ,1998,26(10):6365
(Qin Xiao, Han Zong-fen, Pang Li-ping. Real-time scheduling for two-headed disk system. Journal of Huazhong University of Science and Technology, 1998,26(10):6365)
14Qin Xiao, Pang Li-ping, Han Zong-fen et al. Real-time disk scheduling for mirrored disk systems. In: Zhang Li-chen ed. Proceedings of the 23rd IFAC/IFIP Workshop on Real-time Programming. UK: Elsevier Science Publishers, 1998. 157158
15Х,Ƽڷ.˫ͷ̵ʵʱ㷨.ѧ,1999,22(2):212217
(Qin Xiao, Pang Li-ping, Han Zong-fen. Design and performance evaluation of real-time disk scheduling for two-headed mirrored disk systems. Chinese Journal of Computers, 1999,22(2):212217)
ոڣ1998-06-02޸ڣ1998-09-23
