La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Realization of the highly integrated distributed real time safety critical system MELODY [Elektronische Ressource] / von Jon Arthur Lind

De
136 pages
Ajouté le : 01 janvier 1999
Lecture(s) : 15
Signaler un abus


Realization of the Highly Integrated
Distributed Real-Time Safety-Critical System
MELODY
Dissertation
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
der Universität Dortmund
am Fachbereich Informatik
von
Jon Arthur Lind
Dortmund
1999
Tag der mündlichen Prüfung: Januar 26,1999
Dekan/Dekanin: Prof. Dr. Heinrich Müller
Gutachter:Prof. Dr. Horst F. Wedde
Prof. Dr. Heiko Krumm
Table of Contents
List of Figures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i v
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
Chapter 1: Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Key Issues in Distributed Safety-Critical Real-Time Systems . . . . . . . . . . . . . . . . . 1
1.2 Direction and Goals of the Thesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Chapter 2: Previous and Related Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter 3: MELODY Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Task Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.1 Criticality and relative degrees of Criticality . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.2 Sensitivity and relative degrees of Sensitivity . . . . . . . . . . . . . . . . . . . . . . 12
3.2 File Model 13
3.3 Task Life Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Chapter 4: File Server. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1 File Server Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1.1 Delayed Insertion Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1.2 File Server Client Allocation Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.3er Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.4 Physical File Access Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.5 File History. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.6 Task History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 File Server Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.1 File Server Client Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.2er Server Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Chapter 5: Task Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1 Task Scheduler Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Task Scheduler Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Chapter 6: File Assigner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1 File Assigner Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1.1 File Assigner Lock Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.1.2 File Assigner Client Functionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.1.3 File Assigner Server Functionality 54
6.1.4 File Assigner Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 File Assigner Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.2.1 File Assigner Client Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.2.2 File Assigner Server Implementation 59
Chapter 7: Run-Time Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.1 Run-Time Monitor Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
ii
7.1.1 Task Scheduler/File Server Integration Controller Sub-Server. . . . . . . . . 64
7.1.2 Task Monitor Sub-Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.1.3 File Monitor Sub-Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.1.4 Run-Time Monitor Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.2 Run-Time Monitor Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.2.1 Task Scheduler/File Server Integration Controller Services . . . . . . . . . . . 68
7.2.2 Task Monitor Services. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2.3 File Monitor Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Chapter 8: File System Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8.1 Read Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
8.2 Even Mix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.3 Write Dominance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Chapter 9: File Server/Task Scheduler Integration Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.1 Low Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9.2 Middle Criticality87
9.3 High Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Chapter 10: File Assigner Integration Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
10.1 Read Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
10.2 Even Mix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
10.3 Write Dominance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Chapter 11: Task Monitoring Integration Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
11.1 Deadline Failure Rate Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
11.2 Survivability Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
11.2.1 Low Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
11.2.2 Medium Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
11.2.3 High Competition109
Chapter 12: Conclusion and Future Outlook113
Appendix:
A Communication Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
B Time Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
C Source Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
List of Figures
Figure 3-1: Safety-Critical Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Figure 3-2: Frame of Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Figure 3-3: Frame of Sensitivity. . 12
Figure 3-4: Task Execution Phases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Figure 3-5: MELODY Modules at each node. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Figure 4-1: File Server Client/Server Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Figure 4-2: Read Allocation Handling Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Figure 4-3: Write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Figure 4-4: File Server Client / Server Modules 35
Figure 4-5: MELODY File Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Figure 6-1: File Assigner Client/Server Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Figure 6-2: Get Local Public Copy Protocol 52
Figure 6-3: Reduce Number of Public Copies Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Figure 6-4: Delete Local Public Copy Protocol 53
Figure 6-5: Emergency Reduction of Public Copies Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Figure 6-6: File Assigner: Task Scheduler-Oriented Integration Model . . . . . . . . . . . . . . . . . . . 56
Figure 6-7: File Assigner: File Server Oriented Inte . . . . . . . . . . . . . . . . . . . . . . . 57
Figure 6-8: File Server/File Assigner Control Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Figure 7-1: Run-Time Monitor Sub-Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Figure 7-2: Reading Task Instance Sub-Deadlines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Figure 7-3: Writing T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Figure 7-4: Run-Time Monitor Services Intergration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Figure 8-1: Read Dominance ( C [9..15]/R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75j j
Figure 8-2: CR [9..12]) 75j j
Figure 8-3: C [9..15]/R [12..15]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76j j
Figure 8-4: Read Dominance ( C [7..13]/R [6..9]) 76j j
Figure 8-5: CR [9..12]) 76j j
Figure 8-6: C [7..13]/R [12..15]) 76j j
Figure 8-7: Read Dominance ( C [5..11]/R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76j j
Figure 8-8: CR [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76j j
Figure 8-9: C [5..11]/R [12..15]) 77j j
Figure 8-10: Even Mix ( C [9..15]/ R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77j j
Figure 8-11: Ev C [9..15]/R [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77j j
Figure 8-12: Even Mix ( CR [12..15]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78j j
Figure 8-13: Ev C [7..13] / R [6..9]) 78j j
Figure 8-14: Even Mix ( C [7..13] / R [9..12]) 78j j
Figure 8-15: Ev C [7..13]/R [12..15]) 78j j
Figure 8-16: Even Mix ( C [5..11] / R [6..9]) 78j j
Figure 8-17: Ev CR [9..12]) 78j j
Figure 8-18: Even Mix ( C [5..11] / R [6..9]) 79j j
Figure 8-19: Ev CR [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79j j
Figure 8-20: Even Mix ( C [5..11]/R [12..15]) 79j j
iv
Figure 8-21: Write Dominance ( C [9..15]/R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80j j
Figure 8-22: CR [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80j j
Figure 8-23: C [9.15]/R [12.15])80j j
Figure 8-24: Write Dominance ( C [7..13]/R [6..9])80j j
Figure 8-25: CR [9..12])81j j
Figure 8-26: C [7.13]/R [12.15])81j j
Figure 8-27: Write Dominance ( C [5..11]/R [6..9])81j j
Figure 8-28: CR [9..12])81j j
Figure 8-29: C [5.11]/R [12.15])81j j
Figure 9-1: Low Criticality (Period=10, FTh=1, STh1=1, STh2=1). . . . . . . . . . . . . . . . . . . . . . 86
Figure 9-2: Low Criticality (Period=50, FTh=1, STh1=1, STh2=1)86
Figure 9-3: Low Criticality (Period=90, FTh=1, STh1=1, STh2=1)86
Figure 9-4: Low Criticality (Period=90, FTh=1, STh1=1, STh2=5)86
Figure 9-5: Low Criticality (Period=90, FTh=3, STh1=1, STh2=5)86
Figure 9-6: Low Criticality (Period=90, FTh=5, STh1=1, STh2=5). . . . . . . . . . . . . . . . . . . . . . 86
Figure 9-7: Low Criticality (Period=90, FTh=5, STh1=3, STh2=3)87
Figure 9-8: Low Criticality (Period=90, FTh=5, STh1=1, STh2=1)87
Figure 9-9: Low Criticality (Period=90, FTh=5, STh1=3, STh2=5)87
Figure 9-10: Low Criticality (Period=90, FTh=5, STh1=5, STh2=5)87
Figure 9-11: Middle Criticality (Period=10, FTh=1, STh1=1, STh2=1) . . . . . . . . . . . . . . . . . . . 88
Figure 9-12: Middle Criticality (Period=50, FTh=1, STh1=1, STh2=1)88
Figure 9-13: Middle Criticality (Period=90, FTh=1, STh1=1, STh2=1)88
Figure 9-14: Middle Criticality (Period=90, FTh=1, STh1=1, STh2=5)88
Figure 9-15: Middle Criticality (Period=90, FTh=3, STh1=1, STh2=5)88
Figure 9-16: Middle Criticality (Period=90, FTh=5, STh1=1, STh2=5) . . . . . . . . . . . . . . . . . . . 88
Figure 9-17: Middle Criticality (Period=90, FTh=5, STh1=3, STh2=5)89
Figure 9-18: Middle Criticality (Period=90, FTh=5, STh1=5, STh2=5)89
Figure 9-19: Middle Criticality (Period=90, FTh=5, STh1=3, STh2=3)90
Figure 9-20: Middle Criticality (Period=90, FTh=5, STh1=1, STh2=1)90
Figure 9-21: High Criticality (Period=10, FTh=1, STh1=1, STh2=1) . . . . . . . . . . . . . . . . . . . . . 91
Figure 9-22: High Criticality (Period=50, FTh=1, STh1=1, STh2=1)91
Figure 9-23: High Criticality (Period=90, FTh=1, STh1=1, STh2=1)91
Figure 9-24: High Criticality (Period=90, FTh=1, STh1=1, STh2=5)91
Figure 9-25: High Criticality (Period=90, FTh=3, STh1=1, STh2=5)91
Figure 9-26: High Criticality (Period=90, FTh=5, STh1=1, STh2=5) . . . . . . . . . . . . . . . . . . . . . 91
Figure 9-27: High Criticality (Period=90, FTh=5, STh1=3, STh2=5)92
Figure 9-28: High Criticality (Period=90, FTh=5, STh1=5, STh2=5)92
Figure 9-29: High Criticality (Period=90, FTh=5, STh1=3, STh2=3)92
Figure 9-30: High Criticality (Period=90, FTh=5, STh1=1, STh2=1)92
Figure 10-1: File Assigner: Task Scheduler Oriented Integration Model . . . . . . . . . . . . . . . . . . . 94
Figure 10-2: File Assigner: File Server Oriented Inte . . . . . . . . . . . . . . . . . . . . . . 94
Figure 10-3: Read Dominance ( C [9..15] / R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96j j
Figure 10-4: CR [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96j j
Figure 10-5: C [9.15]/R [12.15])96j j
Figure 10-6: Read Dominance ( C [7..13] / R [6..9])96j j
Figure 10-7: C [7.13] / R [9.12])96j j
Figure 10-8: CR [12.15])96j jv
Figure 10-9: Read Dominance ( C [5..11] / R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97j j
Figure 10-10: C [5.11]/R [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97j j
Figure 10-11: Read Dominance(C [5.11]/R [12.15]) 97j j
Figure 10-12: Even Mix ( C [9..15]/R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98j j
Figure 10-13: Ev CR [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98j j
Figure 10-14: Even Mix ( C [9..15]/R [12..15]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98j j
Figure 10-15: Even Mix ( C [7..13]/R [6..9]) 98j j
Figure 10-16: Ev CR [9..12]) 98j j
Figure 10-17: Even Mix ( C [7..13]/R [12..15]) 98j j
Figure 10-18: Ev C [5..11]/R [6..9]) 99j j
Figure 10-19: Even Mix ( CR [9..12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99j j
Figure 10-20: Ev C [5..11]/R [12..15]) 99j j
Figure 10-21: Write Dominance ( C [9..15]/R [6..9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100j j
Figure 10-22: C [9.15]/R [9.12]) 100j j
Figure 10-23: C [9.15]/R [12.15]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100j j
Figure 10-24: Write Dominance ( C [7..13]/R [6..9]) 100j j
Figure 10-25: C [7.13]/R [9.12]) 100j j
Figure 10-26: C [7.3]/R [12.15]) 100j j
Figure 10-27: Write Dominance ( C [5..11]/R [6..9]) 101j j
Figure 10-28: C [5.11]/R [9.12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101j j
Figure 10-29: C [5.11]/R [12.15]) 101j j
Figure 11-1: Writing Task Profile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Figure 11-2: Reading T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Figure 11-3: Low Competition ( C [7-11]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107j
Figure 11-4: Lo C [6-10]) 107j
Figure 11-5: Lo C [5-9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108j
Figure 11-6: Low Competition ( C [4-8]) 108j
Figure 11-7: Medium Competition ( C [8-12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108j
Figure 11-8: C [7-11]) 108j
Figure 11-9: C [6-10]) 109j
Figure 11-10: C [5-9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109j
Figure 11-11: High Competition ( C [8-12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110j
Figure 11-12: C [7-11]) 110j
Figure 11-13: C [6-10]) 110j
Figure 11-14: High Competition ( C [5-9]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110j
Figure A-1: MELODY Communication Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Figure B-2: Clock Variance without any Time Synchronization. . . . . . . . . . . . . . . . . . . . . . . . . 120
Figure B-3: MELODY Time Synchronization Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Figure B-4: Synchronization (Allo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 12
Figure B-5: Synchronization (Bronto) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Figure B-6: Synchronization (Edmonto) 121
Figure B-7: Synchronization (Plateo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Figure B-8: Synchronization (Titano) 121
Figure B-9:yranno) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121List of Algorithms
Algorithm 4-1: Delayed Insertion Access Request Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Algorithm 4-2: Delayed Insertion Schedule Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Algorithm 4-3: Delayed Insertion Release Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Algorithm 4-4: Delayed Insertion Call Back Acknowledgment Handler . . . . . . . . . . . . . . . . . . 22
Algorithm 4-5: Begin Location Phase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Algorithm 4-6: Begin Acquisition Phase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Algorithm 4-7: Begin Allocation Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Algorithm 4-8: Begin Locking Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Algorithm 4-9: Begin Computation Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Algorithm 4-10: Complete Computation Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Algorithm 4-11: Begin Task Instance Abort30
Algorithm 4-12: Located File Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Algorithm 4-13: Acquired File Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Algorithm 4-14: Allocated File Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Algorithm 4-15: Locked File Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Algorithm 4-16: Called-Back File Copy .32
Algorithm 4-17: Done File Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Algorithm 4-18: File Distribution Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Algorithm 4-19: Update Task History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Algorithm 4-20: Relative Criticality of a Task Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Algorithm 4-21: Relative Sensitivity of a T. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Algorithm 4-22: Estimated Execution Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Algorithm 4-23: Read Acquire File Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Algorithm 4-24: Read Release File Copy36
Algorithm 4-25: Write Request File Copy37
Algorithm 4-26: Write Lock File Copy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3
Algorithm 4-27: Write Unlock File Copy38
Algorithm 4-28: Write Release File Copy38
Algorithm 4-29: Write Refresh File Copy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Algorithm 4-30: Handle Physical Write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3
Algorithm 4-31:ysical Read0 4
Algorithm 4-32: Update Write Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 4
Algorithm 4-33: Update Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4
Algorithm 5-1: Run Task Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4
Algorithm 6-1: Priority Insertion Access Request Handler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Algorithm 6-2: Priority Insertion Release Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Algorithm 6-3: Priority Insertion Call Back Acknowledgment Handler. . . . . . . . . . . . . . . . . . . 50
Algorithm 6-4: Check Move Copy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Algorithm 6-5: Check Create Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5
Algorithm 6-6: Check Delete Copy8 5
Algorithm 6-7: Get FA Lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Algorithm 6-8: Granted FA Lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59vii
Algorithm 6-9: Release FA Lock. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59
Algorithm 6-10: Released FA Lock. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59
Algorithm 6-11: Allow Replication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
Algorithm 6-12: Allow Relocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
Algorithm 6-13: Allow Delete. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Algorithm 6-14: Request FA Lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
Algorithm 6-15: Release FA Lock. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
Algorithm 7-1: Handle New Instance Creation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Algorithm 7-2: Check Task Scheduler Invocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Algorithm 7-3:Write Sub-Deadline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Algorithm 7-4: Check Read Sub Deadline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Algorithm A-1: Receive File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Algorithm A-2: Send File. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118Acknowledgments
I would like to first thank my advisor Professor Dr. Horst F. Wedde. I feel indebted for the
guidance and support he has extended to me over the years that we have known each other. He put an
extraordinary amount of time and effort into developing and reviewing this thesis. Without his effort I
would not have been able to write this thesis. His effort and dedication has meant more to me than I
can say. Thank you very much!
I would also like to take this time to thank the other members of my committee, Professor Dr.
Heiko Krumm, Professor Dr. Norbert Fuhr and Dr. Peter Buchholz. The time and effort spent reviewing
this thesis is of great value to me.
To Bernd Klein, I am forever grateful for his invaluable time and effort in reviewing this thesis.
To all my colleagues at Lehrstuhl III, thank you all for the wonderful work environment and
introduction to german culture and society. It has been a great experience that would not have been
without you all.
To my wife, Heidi, I dedicate this thesis. For without her endless support and dedication
throughout, along with her valued assistant in reviewing, this thesis would never have been completed.
It’s a strong person that can endure through it all to see the end of this chapter in our life, and the
beginning of the next. Thank you very much.
Additionally, I would like to thank my parents, Alfred and Norma, to whom this would not have
been possible without some crucial guidance over the years. I also would like to thank all my family
and relatives for the encouragement throughout the duration of my thesis.

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin