郭大維臺灣大學：資訊工程學研究所黃志源Huang, Chih-YuanChih-YuanHuang2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53701本論文的主要目的在於針對USB和IEEE-1394這兩種I/O共通匯流排界面，探討資源分配的系統架構，並提出具服務品質保證的即時排程演算法。本論文可分成三個部份：首先對於USB 1.1的系統中，我們以循環執行式(cyclic-executive-based)的頻寬預留和排程的方法來達成isochronous傳輸型式的服務品質保證，此頻寬預留和排程的方法會根據USB裝置對頻寬的需求來預留所需之頻寬。我們接著探索USB 2.0和1.1這兩種裝置結合時的服務品質保證的問題。對於週期性(如isochronous和interrupt傳輸型式)的請求，保證預留匯流排的頻寬並做可排程的測試；對於非週期性(如control和bulk傳輸型式)的請求，我們提出一種機率性的效能分析方法。本論文的第三部份，探討IEEE-1394服務品質保證的問題，對於週期性(isochronous傳輸型式)的請求，我們提出對於頻寬保留的機制和策略；對於非同步(asynchronous傳輸型式)的請求,探討服務品質保證的問題和一種機率性的效能分析架構。最後，對於IEEE-1394裝置的放置問題，我們提出一個最佳化的拓撲組態重組演算法，使得系統中任意兩個裝置能達到最佳的傳輸速度。對於以上所提出的方法，我們在Linux的平台上做一些效能的評估，並獲得令人滿意的結果。This thesis aims at the proposing of I/O common bus interface system architectures and real-time scheduling algorithms for resources allocation of USB and IEEE-1394 device requests in a Quality-of-Service (QoS) fashion. We first propose a cyclic-executive-based bandwidth reservation and scheduling method to support QoS guarantees over USB 1.1, especially for those isochronous bus activities. The proposed bandwidth reservation and scheduling method could reserve USB bandwidth for devices in an on-demand fashion. We then explore the resource allocation of USB 2.0 and 1.1 device requests jointly in a Quality-of-Service (QoS) fashion. Periodic requests, such as isochronous and interrupt transfers, are guaranteed with preservation of bus bandwidth and schedulability tests. Sporadic requests, such as control and bulk transfer, are serviced with probabilistic performance analysis. For the third part of this thesis, we exploit the QoS services of IEEE-1393. In particular, we propose a bandwidth reservation mechanism and its policy for isochronous requests, such as those from cameras. We then address the QoS support issue for asynchronous requests, such as those from disks, and then an analytic framework for probability-based QoS analysis. This thesis is concluded by the proposing of an optimal topology configuration algorithm for IEEE-1394 devices. The capability of this work is demonstrated with performance evaluations over a Linux system prototype, for which we have encouraging results.Contents 1 Introduction . . . . . . . . . . . . . . . .13 1.1 Introduction . . . . . . . . . . . . . . . . . . . . 13 1.2 Organization of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Related Work 19 2.1 Resource Reservation in Real-Time Operating Systems . . . . . . . . 19 2.2 Resource Scheduling in USB and IEEE-1394 . . . . . 21 3 I/O Common Bus Subsystems 23 3.1 USB Subsystems . . . . . ... . . . . . . . . . . . . 23 3.1.1 A USB 1.1 Subsystem . . . . .. . . . . . . . . . . 23 3.1.2 A USB 2.0 Subsystem . . . . . . . .. . . . . . . . 27 3.2 An IEEE-1394 Subsystem . . . . . . . . . . . . . . . 30 4 QoS Guarantees for USB 1.1 Subsystems 33 4.1 Introduction . . . . . . . . . . . . . . . . . . 33 4.2 Overview - A Cyclic-Executive-Based Method . . . . . 36 4.3 A Period Modification Policy and Admission Control . . . . . . . 37 4.4 Insertions of Endpoint and Transfer Descriptors . . 40 4.5 USB Bandwidth Utilization Further Improvement . . . 45 5 QoS Guarantees for USB 2.0 Subsystems . . . . . 49 5.1 Introduction . . . .. . . . . . . . . . . . . . . 49 5.2 Overview . . . . . . . . . . . . . . . . . . . . . 51 5.3 QoS Guarantees for Periodic Requests . . . . . . . . . . . . . . . . . 53 5.3.1 A Fixed-Rate Service Policy . . . . . . . . . . . . . . . . . . . 53 5.3.2 A Workload Re-insertion Algorithm - Bandwidth Utilization Optimization . . . . . 56 5.3.3 A Binary Encoding Algorithm for PeriodModification - AMultiple- QH Approach . . . . . . . . . . . . . . . . 60 5.4 Probabilistic QoS Analysis for Sporadic Transfers . .63 6 QoS Guarantees for IEEE-1394 Subsystems . . . .69 6.1 Introduction . . . . . . . . . . . . . . . . . . . 69 6.2 Overview . . . . . . . . . . . . . . . . . . . . . 71 6.3 QoS Guarantees for Periodic Requests . . . . . . . 73 6.3.1 A Period Modification Policy and Admission Control . . . . . 73 6.3.2 Protocol Overhead Minimization Policy . . . . . 75 6.4 Probabilistic QoS Analysis for Sporadic Transfers . .77 6.5 Topology Re-Configuration for Bandwidth Improvement 81 7 Performance Evaluation . . . . . . . . . 85 7.1 Experiments for USB 1.1 Subsystem . . . . . . . . 85 7.1.1 Experimental Environments and Performance Metrics 85 7.1.2 Overheads Due to Bandwidth Reservation . . . . . . 88 7.1.3 Bandwidth Reservation and Workload Distribution .. 92 7.2 Experiments for USB 2.0 Subsystem . . . . . . . . . 94 7.2.1 Bandwidth Utilization . . . . . . . . . . . . . . 94 7.2.2 Probabilistic QoS Analysis . . . . . . . . . . . . 96 7.2.3 Bandwidth Reservations - Realistic Workloads . . . 98 7.3 Experiments for IEEE-1394 Subsystem . . . . . . . . 99 7.3.1 Bandwidth Reservations - Isochronous Requests . . 100 7.3.2 Probabilistic QoS Analysis - Asynchronous Requests . 102 8 Conclusion . . . . .105774413 bytesapplication/pdfen-US服務品質USBIEEE-1394QoSthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53701/1/ntu-95-D89922002-1.pdf