ALEXANDRIA UNIVERSITY FACULTY OF ENGINEERING DEPARTMENT OF COMPUTER SCIENCE AND AUTOMATIC CONTROL A REAL-TIME DISK SCHEDULING ALGORITHM FOR MULTIMEDIA STORAGE SERVERS A thesis submitted in partial fulfillment for the degree of Master of Science By Sameh Mohamed Ibrahim Elnikety B.Sc., Faculty of Engineering, Alexandria University, 1996 Supervised by Prof. Dr. Mohamed S. Abougabal Department of Computer Science and Automatic Control Faculty of Engineering, Alexandria University Prof. Dr. Ahmed A. El Nahas Department of Computer Science and Automatic Control Faculty of Engineering, Alexandria University Dr. Walid G. Aref Department of Computer Science and Automatic Control Faculty of Engineering, Alexandria University Alexandria 1999 We certify that we have read this thesis and that in our opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Master of Science. Examination Committee: Prof. Dr. Mohamed S. Abougabal Department of Computer Science and Automatic Control Faculty of Engineering Alexandria University Prof. Dr. Ahmed A. Belal Department of Computer Science and Automatic Control Faculty of Engineering Alexandria University Prof. Dr. Mohamed Z. Abdel Mageed Department of Electrical Engineering Faculty of Engineering Al-Azhar University For the Faculty Council: Prof. Dr. Hassan A. Farag Vice dean for Graduate Studies and Research Faculty of Engineering Alexandria University i ACKNOWLEDGMENT My deepest gratitude and appreciation are due to Prof. Dr. Mohamed S. Abougabal, for his major part in the preparation of this work. Thanks for his persistent direction and constructive guidance throughout the work. My deepest thanks to Prof. Dr. Ahmed El Nahas for his valuable advice and support in early cooperation and preparation of this work. I would like to express my deepest gratitude to Dr. Walid G. Aref for his great help and valuable directions. I appreciate his early suggestion of this research point. His support and encouragement have been invaluable. ii ABSTRACT Emerging multimedia applications require the underlying multimedia storage server to be able to efficiently support a diverse group of activities. Existing real-time disk scheduling algorithms do not support the whole spectrum of disk request types that is required by server-based multimedia applications. This thesis presents a new technique for the disk queue organization and proposes a real-time disk scheduling algorithm that is able to efficiently support the whole spectrum of disk request types serviced by multimedia storage servers. The complexity analysis of the proposed algorithm is studied and its correctness is established. A simulation model is developed to assess the performance of the algorithm with comparison to other existing algorithms. The simulation model is validated and verified. Simulation results demonstrate that the proposed algorithm is superior to other existing algorithms. iii TABLE OF CONTENTS ACKNOWLEDGEMENT • • • • • • i ABSTRACT • • • • • • • • ii TABLE OF CONTENTS • • • • • • • iii LIST OF FIGURES • • • • • • • v LIST OF TABLES • • • • • • • vii LIST OF SYMBOLS • • • • • • • viii 1 INTRODUCTION • • • • • • • 1 1-1 General • • • • • • • • 1 1-2 Motivation And Scope Of The Work • • • • 1 1-3 Organization Of The Thesis • • • • • 3 2 LITERATURE SURVEY • • • • • • 4 2-1 Introduction • • • • • • • 4 2-2 Nature Of The Disk Scheduling Problem • • • 4 2-3 Taxonomy Of Existing Real-Time Disk Scheduling Algorithms • 6 2-4 Need To Extend Existing Real-Time Disk Scheduling Algorithms 16 2-5 Conclusion • • • • • • • 16 3 PROPOSED REAL-TIME DISK SCHEDULING ALGORITHM (SCAN-RT3) • • • 17 3-1 Introduction • • • • • • • 17 3-2 General Description Of The Algorithm • • • • 17 iv 3-3 Main Subroutines Of Algorithm SCAN-RT3 • • • 22 3-4 Main Cases Of Algorithm SCAN-RT3 • • • • 33 3-5 Complexity Analysis Of Algorithm SCAN-RT3 • • • 48 3-6 Termination And Correctness Of Algorithm SCAN-RT3 • • 50 3-7 Conclusion • • • • • • • 54 4 EXPERIMENTS AND RESULTS • • • • • 57 4-1 Introduction • • • • • • • 57 4-2 System Model • • • • • • • 57 4-3 Experimental Results For Algorithms EDF, SCAN-RT1, And SCAN-RT3 • • • • • • • 66 4-4 Experimental Results For Algorithms SCAN-RT2, And SCAN-RT3 68 4-5 Experimental Results For Combined Video-On-Demand And Video Editing Applications • • • • • 71 4-6 Other General User Mix Ratios • • • • • 83 4-7 Conclusion • • • • • • • 90 5 CONCLUSIONS AND FUTURE EXTENSIONS • • • 91 5-1 Conclusions • • • • • • • 91 5-2 Future Extensions • • • • • • 92 REFERENCES • • • • • • • 94 v LIST OF FIGURES Figure Title Page Figure 2-1 Components of a disk access 5 Figure 2-2 Taxonomy of real-time disk scheduling algorithms 6 Figure 3-1 Disk queue organization for multi-partitioning 18 Figure 3-2 Double linked list representing the disk queue 19 Figure 3-3 Revised taxonomy of real-time disk scheduling algorithms 56 Figure 4-1 Architecture of a multimedia storage server 58 Figure 4-2 Window to generate the disk requests 62 Figure 4-3 Rdl loss rate for algorithms EDF, SCAN-RT1 and SCAN-RT3 66 Figure 4-4 Rdl loss rate for algorithms SCAN-RT2 and SCAN-RT3 68 Figure 4-5 Rdl delay time for algorithms SCAN-RT2 and SCAN-RT3 69 Figure 4-6 Wnn delay time for algorithms SCAN-RT2 and SCAN-RT3 69 Figure 4-7 Rdl loss rate for algorithm SCAN-RT3 71 Figure 4-8 Rdl delay time for algorithm SCAN-RT3 72 Figure 4-9 Wnn delay time for algorithm SCAN-RT3 72 Figure 4-10 Rnn delay time for algorithm SCAN-RT3 73 Figure 4-11 Read disk requests loss rate for algorithms SCAN-RT2 and SCAN-RT3 74 Figure 4-12 Read disk requests delay time for algorithms SCAN-RT2 and SCAN-RT3 75 Figure 4-13 Wnn delay time for algorithms SCAN-RT2 and SCAN-RT3 75 Figure 4-14 Wnn delay time for algorithm SCAN-RT3 78 Figure 4-15 Wnn delay time for algorithm SCAN-RT3 78 Figure 4-16 Rdl loss rate for algorithm SCAN-RT3 79 vi Figure 4-17 Rdl delay time for algorithm SCAN-RT3 79 Figure 4-18 Wnn delay time for algorithm SCAN-RT3 80 Figure 4-19 Rnn delay time for algorithm SCAN-RT3 80 Figure 4-20 Rdl loss rate for algorithm SCAN-RT3 81 Figure 4-21 Rdl delay time for algorithm SCAN-RT3 81 Figure 4-22 Wnn delay for algorithm SCAN-RT3 82 Figure 4-23 Rnn delay time for algorithm SCAN-RT3 82 Figure 4-24 Rdl loss rate for user mix ratio 1 83 Figure 4-25 Rdl delay time for user mix ratio 1 83 Figure 4-26 Wnn delay time for user mix ratio 1 84 Figure 4-27 Rnn delay time for user mix ratio 1 84 Figure 4-28 Wdn delay time for user mix ratio 1 85 Figure 4-29 Rdl loss rate for user mix ratio 2 86 Figure 4-30 Rdl delay time for user mix 2 86 Figure 4-31 Wnn delay time for user mix ratio 2 87 Figure 4-32 Rnn delay time for user mix ratio 2 87 Figure 4-33 Wdl loss rate for user mix ratio 2 88 Figure 4-34 Wdl delay time for user mix ratio 2 88 Figure 4-35 Rdn delay time for user mix ratio 3 89 vii LIST OF TABLES Table Title Page Table 1-1 Classification of disk requests for a multimedia storage server 2 Table 2-1 Existing real-time disk scheduling algorithms 16 Table 3-1 Deadline computation for different disk request types 22 Table 3-2 Summary of existing real-time disk scheduling algorithms 55 Table 4-1 Disk parameters 60 Table 4-2 Mix ratios for video-on-demand and video editing 77 viii LIST OF SYMBOLS Symbol Meaning Page Rdl Read disk request which has a soft deadline and can be lost 2 Rdn Read disk request which has a soft deadline and can not be lost 2 Rnl Read disk request which has no deadline and can be lost 2 Rnn Read disk request which has no deadline and can not be lost 2 Wdl Write disk request which has a soft deadline and can be lost 2 Wdn Write disk request which has a soft deadline and can not be lost 2 Wnl Write disk request which has no deadline and can be lost 2 Wnn Write disk request which has no deadline and can not be lost 2 1 CHAPTER ONE INTRODUCTION 1-1 GENERAL Video-on-demand and video authoring tools are emerging as very interesting and challenging multimedia applications. They require special hardware and networking protocols that can accommodate the real-time demands of these applications as well as the high bandwidth that they need. During the past few years, non-linear editing systems have gained increased popularity. These systems are widely applied in the entertainment industry and in TV newsrooms. While most existing systems are analog, products providing support for digital editing are emerging from many vendors such as Avid, Hewlett-Packard, Panasonic, Quantel, Sony and Tecktronix [1]. An important component of such a system is a multimedia storage server that can display and record digital video. The complexity in the design of such a storage server arises due to the wide range of applications to be supported. These applications include video-on-demand, video authoring, real-time recording, computer vision, and video conferencing. 1-2 MOTIVATION AND SCOPE OF THE WORK With the current many-fold increase in CPU processing power and network 2 bandwidth, it is inevitable that multimedia data will be as available as text data today [2, pp 1-5]. The storage and retrieval of multimedia data requires real-time disk scheduling algorithms which support different disk request types. Table 1-1 illustrates all the types of read and write disk requests which are serviced by a multimedia storage server for different applications [1]. Each disk request can be a read or a write request, may have a soft deadline or not, and can be lost or can not be lost. Request symbol Type Soft deadline Can be lost Applications Rdl Read Yes Yes Video-on-demand playback Rdn Read Yes No Editor previewing data after editing, computer vision Rnl Read No Yes Does not really exist because if there is no deadline, then it can always be serviced Rnn Read No No Editor downloading a media clip for editing, metadata reading Wdl Write Yes Yes Low quality real-time recording (for example, archival of a video conferencing session) Wdn Write Yes No High quality real-time recording (for example, from cameras in a site) Wnl Write No Yes Does not really exist because if there is no deadline, then it can always be serviced Wnn Write No No Editor writing data after editing, metadata updates Table 1-1: Classification of disk requests for a multimedia storage server Existing real-time disk scheduling algorithms support only video servers which use Rdl and Wnn disk request types for storing digital video and reading digital video for broadcasting. Current video servers are very efficient only when reading digital video for broadcasting as in video-on-demand systems. There is a bad need to extend existing video servers into multimedia storage servers which support the applications listed in this section. These applications require 3 all the disk request types listed in table 1-1. Therefore, a real-time disk scheduling algorithm should be devised to support all these disk request types. In this thesis, a real-time disk scheduling algorithm that supports all disk request types is proposed, verified and proven to be practical. 1-3 ORGANIZATION OF THE THESIS The remaining of the thesis is organized as follows: in chapter two, existing realtime disk scheduling algorithms are surveyed, a taxonomy is proposed, and the need to extend existing algorithms to extend the functionality of video servers into multimedia storage servers is established. In chapter three, the proposed algorithm is presented, its complexity is studied, and its correctness is established. In chapter four, the proposed algorithm is implemented and verified, and the simulation results show that the proposed algorithm is superior to other existing algorithms. Finally, the conclusion of the work and some possible future extensions are presented in chapter five. 4 CHAPTER TWO LITERATURE SURVEY 2-1 INTRODUCTION In this chapter, existing real-time disk scheduling algorithms are surveyed and a taxonomy is proposed. Also, the need to extend existing algorithms is established. The disk scheduling problem is discussed in section 2-2. A taxonomy of the existing real-time disk scheduling algorithms for multimedia storage servers is suggested along with a discussion of their features in section 2-2. The need to extend existing algorithms is established in section 2-3. Finally, the chapter is concluded in section 2-4. 2-2 NATURE OF THE DISK SCHEDULING PROBLEM To service a disk request, several operations take place [3, pp 361-363]. First, the disk head must be moved to the appropriate cylinder (seek time). Then, the portion of the disk on which the disk page is stored must be rotated until it is immediately under the disk head (latency time). Then, the disk page must be made to spin by the disk head (transmission time). The above components needed to service a disk request are illustrated in figure 2-1. 5 Figure 2-1: Components of a disk access Queues build up for each disk because the inter-arrival time of the disk requests can be smaller than the time required by the disk to service a disk request. Disk scheduling involves a careful examination of the pending disk requests to determine the most efficient way to service the disk requests. The disk scheduling problem involves reordering the disk requests in the disk queue so that the disk requests will be serviced with the minimum mechanical motion by employing seek optimization and latency optimization. The disk scheduling problem can be reduced to the travelling salesman problem which is a classical graph theory problem known to be NP-complete. Thus, the disk scheduling problem is an NP-complete problem [4]. The desirable characteristics of the disk scheduling algorithms are maximizing throughput, being fair, minimizing the mean response time, and minimizing the variance of the response times (predictability) [3, pp 364-365]. Traditionally, disk Latency time Transmission time Seek time Disk head 6 scheduling algorithms have mainly been concerned with increasing the bandwidth utilization of the disks, by ordering disk requests so that the seek time is minimized. Heuristic algorithms such as Shortest Seek Time First (SSTF), SCAN and Circular SCAN address this problem. When real-time constraints are imposed on disk requests, minimizing seek time alone is not sufficient [4]. Real-time algorithms should address both minimizing the seek time and satisfying the timing constrains. Existing real-time disk scheduling algorithms are discussed in the following section. 2-3 TAXONOMY OF EXISTING REAL-TIME DISK SCHEDULING ALGORITHMS Close study of existing real-time disk scheduling algorithms for multimedia storage servers suggests the taxonomy depicted in figure 2-2. The classification is based on whether the scheduling algorithm handles the disk request mainly based on its position on the disk (the position is determined by the cylinder number and the sector number) or based on the its deadline. Figure 2-2: Taxonomy of existing real-time disk scheduling algorithms Each algorithm maintains one disk queue where incoming disk requests are stored. EDF (Rdl) [6] sorting on disk request deadline SCAN-RT1 (Rdl) [6] SCAN-RT2 (Rdl, Wnn) [1] sorting on disk request position Real-time disk scheduling algorithms 7 Disk requests are serviced from the front of the queue (queue head). A newly-arrived disk request is inserted somewhere in the disk queue. Normally, the disk queue is implemented as a double linked list [5]. Each node of the double linked list represents one disk request. The double linked list is detailed in subsection 3-2-2. These algorithms are detailed below. For each algorithm, the input, output, and its functionality are described in pseudo code. This format is used throughout out the thesis. 2-3-1 Algorithm Earliest Deadline First The Earliest Deadline First Algorithm, EDF, handles only Rdl disk requests. An Rdl disk request is a read disk request which has a soft deadline and can be lost. This algorithm attempts to service disk requests according to their deadlines [6]. Thus, the disk request that has the earliest deadline in the disk queue is serviced first. This means that the disk requests are sorted according to their deadlines and stored in the disk queue. As an extension of the algorithm, when there is a tie (this means two or more disk requests have the same deadline), the algorithm sorts the disk requests in scan order according to their cylinder numbers. These ties are very improbable in the case of multimedia storage servers. The algorithm is detailed below. 2-3-1-1 Algorithm EDF input disk_request: the disk request to be scheduled. output returns true if insertion is successful and false otherwise. 8 function 1. loop starting from the queue head and moving backward towards the queue tail 2. if the deadline of disk_request is before the deadline of the current disk request, and disk_request can be inserted such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then insert the disk_request, return true, and stop 3. if it is not possible to insert the disk request, reject disk_request and return false 4. stop. complexity time complexity: O(n) node accesses are needed space complexity: O(n) nodes are needed n is the number of disk requests in the disk queue. 2-3-1-2 Discussion of the EDF algorithm This algorithm does not try to optimize the disk bandwidth utilization, thus limiting the capacity of the multimedia storage server. The performance of this algorithm compared to the other relevant algorithms is shown in figure 4-3. This algorithm is suitable only for handling Rdl disk requests under light loads, which is the case for a limited number of viewers in a video-on-demand system. 9 This algorithm uses a double linked list where each node of the double linked list represents one disk request. The time complexity of inserting a new disk request into the disk queue is measured by the number of node accesses required. The time complexity is O(n) because when inserting a new disk request, O(n) node accesses are needed to maintain the disk queue sorted by the deadlines of the disk requests, and to check that the deadlines of other pending disk requests are not violated. Where n is the number of disk requests in the disk queue, which is the number of nodes in the double linked list that represents the disk queue. 2-3-2 Algorithm SCAN – Real-Time 1 The SCAN – Real-Time 1 algorithm, SCAN-RT1, is a modification of the SCAN algorithm [7, pp 345-352]. This algorithm handles only Rdl disk requests. An Rdl disk request is a read disk request which has a soft deadline and can be lost. SCAN attempts to optimize the disk operation by servicing the disk requests in scan order. SCAN-RT1 attempts to honor the real-time constraints without excessively affecting the disk bandwidth utilization. SCAN-RT1 is similar to the SCAN algorithm in optimizing the seek time. However, it schedules disk requests in a manner that maximizes the number of disk requests that meet their deadline. This is accomplished as follows. When a new disk request arrives, it is inserted in the disk queue in the scan order, only if the insertion does not potentially violate the deadlines of the other pending disk requests and its own deadline. Otherwise, the disk request is appended to the end of the queue if it is expected that the disk request will be serviced before its deadline. A disk request that can not be inserted in scan order nor appended at the end of the queue is rejected and 10 considered lost. 2-3-2-1 Algorithm SCAN-RT1 input disk_request: the disk request to be scheduled. output returns true if insertion is successful and false otherwise. function 1. loop starting from the queue tail in the disk queue and moving forward towards the queue head 2. if the disk_request can be inserted in scan order such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then insert the disk_request, return true, and stop 3. if it is not possible to insert the disk request, reject disk_request and return false 4. stop. complexity time complexity: O(n) node accesses are needed space complexity: O(n) nodes are needed n is number of disk requests in the disk queue. 11 2-3-2-2 Discussion of the SCAN-RT1 algorithm This algorithm is suitable for handling Rdl disk requests, which are required by viewers in a video-on-demand system. The performance of this algorithm compared to other relevant algorithms is outlined in figure 4-3. This algorithm uses a double linked list where each node of the double linked list represents one disk request. The time complexity of inserting a new disk request into the disk queue is measured by the number of node accesses required. O(n) node accesses are needed to insert a newly-arrived Rdl disk request, to maintain the disk queue sorted in scan order, and to check that the deadlines of other pending disk requests are not violated. Where n is the number of disk requests in the disk queue, which is the number of nodes in the double linked list that represents the disk queue. 2-3-3 Algorithm SCAN – Real-Time 2 The SCAN – Real-Time 2 algorithm, SCAN-RT2, is an extension of the algorithm SCAN-RT1 in order to handle both read and write disk requests [1]. This algorithm handles only Rdl and Wnn disk requests. An Rdl disk request is a read disk request which has a soft deadline and can be lost. A Wnn disk request is a write disk request which has no deadline and can not be lost. In this algorithm Rdl disk requests are handled exactly as Rdl disk requests in the algorithm SCAN-RT1. However, the write disk requests that are given to the multimedia storage server have to be buffered in the main memory buffers of the multimedia storage server. Thus, to avoid buffer overflow, a deadline for each write disk request is computed such that the buffer never overflows. 12 2-3-3-1 Computing the deadline of read and write disk requests The read disk requests have deadlines imposed by the multimedia streams which are viewed by the users. In a video editing session, the write disk requests that take place during the session belong to the Wnn category. The Wnn disk request type has the characteristics listed below. 1. Any Wnn disk request to be written to the disk is already pre-stored in a main memory buffer pool. 2. A Wnn disk request has no real-time deadline. Therefore, it can afford longer delays than Rdl disk requests. 3. Although it does not have a deadline, a Wnn disk request can not be kept indefinitely in main memory due to the risk of loss in case of system crash or power failure. It has to be fulfilled some time in the future, to avoid buffer overflow. The longest possible duration that a write disk request can be put in hold is a system parameter. 4. A Wnn disk request can not be lost due to system load. Regardless of the system load, a Wnn disk request has to be fulfilled by the system at some point in time. Therefore, the deadline associated with the Wnn disk requests would have to be artificially computed by the multimedia storage server based on the number of available buffers and the expected arrival rate of write disk requests. The following formula is used to compute the deadline of a newly-arrived Wnn disk request. 13 deadline = present time + (free buffer space)/(arrival rate of Wnn disk requests) {2-1} 2-3-3-2 Algorithm SCAN-RT2 input disk_request: the disk request to be scheduled. output returns true if insertion is successful and false otherwise. function 1. compute the deadline of disk_request as outlined in subsection 2-2-3-1 2. if disk_request is a read disk request then 3. loop starting from the queue tail in the disk queue and moving forward towards the queue head 4. if the disk_request can be inserted in scan order such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then insert the disk_request, return true, and stop 5. if it is not possible to insert the disk request, then reject disk_request, and return false 6. stop 7. else {disk_request is a write disk request} 8. loop starting from the queue tail in the disk queue and moving forward towards the queue head 14 9. if the disk_request can be inserted in scan order such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then insert the disk_request, return true, and stop 10. loop starting from the queue tail in the disk queue and moving forward towards the queue head 11. if disk_request can be inserted in scan order such that its deadline is not violated, then insert the disk_request 12. if disk_request is not inserted then 13. append disk_request at the disk queue tail 14. loop starting from the queue head in the disk queue and moving backward towards the queue tail 15. if the deadline of the current disk is violated 16. switch type of current disk request 17. case type Rdl: 18. delete Rdl disk request from the disk queue and reject the Rdl disk request 19. case type Wnn: 20. re-insert the Wnn disk request at the queue head as well as all other Wnn disk requests whose deadlines are violated. 15 21. return true 22. stop. complexity time complexity: O(n2) node accesses are needed space complexity: O(n) nodes are needed n is the number of disk requests in the disk queue. 2-3-3-3 Discussion of the SCAN-RT2 algorithm This algorithm is an attempt to handle the case of viewers and editors in video-ondemand and video authoring systems. In fact, it does not handle the Rnn disk request type which is needed by editors in video authoring systems. The algorithm replaces Rnn disk requests (which can not be lost) with Rdl disk requests (which can be lost). Thus, SCAN-RT2 does not provide full functionality for viewers and editors which is needed in a combined video-on-demand and video editing system as in a TV newsroom. This algorithm uses a double linked list where each node of the double linked list represents one disk request. The time complexity of inserting a new disk request into the disk queue is measured by the number of node accesses required. O(n2) node accesses are needed to insert a newly-arrived disk request, to maintain the disk queue sorted in scan order, and to check that the deadlines of other pending disk requests are not violated. Where n is the number of disk requests in the disk queue, which is the number of nodes in the double linked list that represents the disk queue. 16 2-4 NEED TO EXTEND EXISTING REAL-TIME DISK SCHEDULING ALGORITHMS The main features of existing real-time disk scheduling algorithms for multimedia storage servers are summarized in table 2-1. Algorithm Applications supported Disk request types that are handled Complexity EDF Video-on-demand Rdl Time: O(n) Space: O(n) SCAN-RT1 Video-on-demand Rdl Time: O(n) Space: O(n) SCAN-RT2 Video-on-demand and partial support for video editing Rdl, Wnn Time: O(n2) Space: O(n) Table 2-1: Existing real-time disk scheduling algorithms Close study of table 2-1 reveals that these algorithms do not handle all the types of disk requests listed in table 1-1. Even the combined video-on-demand and video editing applications, which require the disk request types Rdl, Wnn and Rnn, are not fully handled because only the disk request types Rdl and Wnn are handled. Thus, it is evident that existing algorithms should be modified to handle all the types of disk requests. 2-5 CONCLUSION Existing real-time disk scheduling algorithms are studied and taxonomized. It is shown that the existing algorithms handle only the Rdl and the Wnn disk request types. Other disk requests, namely Wdn, Rdn, Wdl, and Rnn, which are essential for multimedia storage servers, can not be handled. A real-time disk scheduling algorithm which can handle all types of disk requests, which are listed in table 1-1, is proposed and studied in depth in the next chapter. 17 CHAPTER THREE PROPOSED REAL-TIME DISK SCHEDULING ALGORITHM (SCAN-RT3) 3-1 INTRODUCTION The need for an algorithm that supports all types of the disk requests listed in table 1-1 was established in the previous chapter. In this chapter, this algorithm is proposed and studied in depth. A general description of the algorithm is presented in section 3- 2. The main subroutines of the algorithm are detailed in section 3-3. The main cases of the algorithm are detailed in section 3-4. The complexity analysis of the algorithm is discussed in section 3-5. The termination and correctness of the algorithm are proven in section 3-6. Finally, the chapter is concluded in section 3-7. 3-2 GENERAL DESCRIPTION OF THE ALGORITHM This section provides a general description of the proposed algorithm. The proposed algorithm is referred to as SCAN-RT3. The algorithm employs a novel disk queue organization which is depicted in subsection 3-3-1. The data structure used to implement the proposed disk queue organization is described in subsection 3-2-2. The algorithm uses a priority order to schedule the different types of disk requests. This priority order is explained in subsection 3-2-3. The main inputs and outputs of the 18 proposed algorithm are outlined in subsection 3-2-4 and subsection 3-2-5, respectively. The computation of deadlines of the different types of disk requests is detailed in subsection 3-2-6. 3-2-1 Disk Queue Organization For the algorithm SCAN-RT2 [1], it was suggested to have two scan order partitions in the disk queue. The first scan order partition, which is called the current partition, is used as usual to insert newly-arrived disk requests. The second scan order partition, which is called the next partition, should be used only when a newly-arrived disk request could not be inserted in the first scan order partition, which is the current partition, without violating the deadline of any pending disk requests. This technique was not studied. The proposed algorithm handles disk request types that can afford to wait in the disk queue for a relatively long time. For example, Rnn disk requests, which do not have deadlines, may afford to remain in the disk queue for a much longer time than Rdl disk requests, which have stringent deadlines. This suggests the possibility of using several scan order partitions. This new technique is called multi-partitioning. The proposed algorithm uses multi-partitioning, this means several scan order partitions, to maintain the different types of pending disk requests. Figure 3-1: Disk queue organization for multi-partitioning Disk server disk requests in scan order partition 0 disk requests in scan order partition 1 disk requests in scan order partition n-1 disk requests in scan order partition n ... 19 3-2-2 Data Structures Employed By The Algorithm The algorithm uses a double linked list [8, pp 203-248] to implement the multipartition disk queue. Each node of the double linked list represents one disk request. Each queue node contains one disk request along with its attributes, the next pointer and the prev pointer. The attributes include the disk position, the type of disk request, the address of the user, and a pointer to a page in the write buffer for write requests. The next pointer points to the next node if it exists. The prev pointer points to the previous node if it exists. Figure 3-2 illustrates the double linked list used to represent the disk queue. Figure 3-2: Double linked list representing the disk queue A newly-arrived disk request is inserted somewhere in the disk queue, including both queue ends. The next disk request to be served is the disk request at the queue head. The double linked list is used because it is convenient for bi-directional traversal of queue nodes, simple insertion, and deletion of queue nodes. disk server next prev next prev next prev . . . queue head queue tail queue node 20 3-2-3 Priority Order Of The Different Disk Request Types The following priority order is used by the algorithm to schedule disk requests. (highest priority) Wdn, Wnn, Rdn, Wdl, Rdl, Rnn (lowest priority) Generally, write disk requests are assigned a higher priority than read disk requests. Also, disk requests that can not be lost are assigned a higher priority than disk requests that can be lost. Finally, disk requests that have deadlines are assigned a higher priority that disk requests that do not have a deadline. In this manner, the Wdn disk request type has more priority than the Wnn disk request type because the Wdn disk request type has a deadline by definition. The Wnn disk request type has more priority than Rdn disk request type because the Wnn disk request type is a write disk request. The Rdn disk request type has more priority than the Wdl disk request type because the Rdn disk request type can not be lost. The Wdl disk request type has more priority than Rdl disk request type because the Wdl disk request type is a write disk request. The Rdl disk request type has more priority than the Rnn disk request type because the Rdl disk request type has a deadline. Indefinite postponement is avoided by aging [3, pp 158-159]. This is accomplished by assigning a system wide deadline for all disk requests. More details on assigning deadlines to the disk requests are presented in subsection 3-3-6. 3-2-4 Inputs Of The Algorithm The inputs of the algorithm are (1) the newly-arrived disk request to scheduled, and (2) the disk queue that is implemented as a double linked list. 21 3-2-5 Outputs Of The Algorithm The outputs of the algorithm are (1) the disk queue that is implemented as a double linked list which may or may not include the newly-arrived disk request, and (2) some statistical performance measures. 3-2-6 Computing The Deadline Of A Disk request The deadlines assigned to the disk requests are soft deadlines because the multimedia storage server supports non-critical real-time tasks [9, pp 9-11]. Firstly, the disk requests that need to be serviced have deadlines which depend on the bandwidth of the multimedia stream used to generate these disk requests. Secondly, the write disk requests, namely, the Wdn, Wnn, and Wdl disk request types, that are given to the multimedia storage server have to be buffered in the main memory buffers of the multimedia storage server. Thus, to avoid buffer overflow, a deadline for each write disk request is computed such that the buffer never overflows. The following formula is used to compute the deadline of a newly-arrived write disk request. deadline = present time + (free buffer space) / (arrival rate of write disk requests) {3-1} Thirdly, The disk requests that do not have a deadline (types Wnn, Rnn) are assigned an artificial deadline to (1) prevent indefinite postponement, and (2) avoid losing disk requests in the case of a system crash. This deadline is a system parameter and it is typically much less binding than other deadlines. 22 The method of computing the deadlines of all types of disk requests is summarized in table 3-1. If there are more than one deadline for a single disk request type, the disk request is assigned the tighter deadline. Type Deadline 1 (introduced by the bandwidth of the required multimedia stream) Deadline 2 (introduced by the scheduling algorithm to avoid the overflow of the write buffer) Deadline 3 (introduced by the system to avoid indefinite postponement and loss of data in the case of a system crash) Wdn Deadline enforced by the type of the multimedia stream Computed by equation 3-1 System write deadline Wnn Computed by equation 3-1 System write deadline Rdn Deadline enforced by the type of the multimedia stream System read deadline Wdl Deadline enforced by the type of the multimedia stream Computed by equation 3-1 System write deadline Rdl Deadline enforced by the type of the multimedia stream System read deadline Rnn System read deadline Table 3-1: Deadline computation for different disk request types 3-3 MAIN SUBROUTINES OF ALGORITHM SCAN-RT3 The algorithm employs ten main subroutines. The main subroutines, which are used repeatedly by the algorithm, are detailed in the following subsections. For each subroutine, the input, output and its functionality are described in pseudo code. The number of node accesses is used as a measure of the time complexity of the subroutines. The time complexity is expressed as a function of n, where n is the number of disk requests in the disk queue, which is the number of nodes in the double linked list that represents the disk queue. All these subroutines access the main data structure of the algorithm, which is the double linked list that represents the disk queue. The overall complexity of the algorithm is discussed in section 3-5. 23 3-3-1 try_insert_in_scan_order ( disk_request, start, end ) input disk_request: the disk request to be inserted in the disk queue start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output returns true if insertion is successful and false otherwise. function 1. loop starting from the start position in the disk queue and moving forward towards the end position 2. if the disk_request can be inserted in scan order such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then insert the disk_request and return true 3. if it is not possible to insert the disk request, return false 4. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 24 3-3-2 insert_in_scan_order( disk_request, start, end ) input disk_request: the disk request to be inserted in the disk queue start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output there is no output. function 1. loop starting from the start position in the disk queue and moving forward towards the end position 2. if the disk_request can be inserted in scan order such that its deadline is not violated, then insert the disk_request and stop 3. if it is not possible to insert the disk_request, halt 4. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 25 3-3-3 try_promote ( disk_request, start, end ) input disk_request: the disk request to be re-inserted in the disk queue start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output returns true if re-insertion is successful and false otherwise. function 1. loop starting from the start position in the disk queue and moving forward towards the end position 2. if the disk_request can be re-inserted in scan order such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then re-insert the disk_request and return true 3. if it is not possible to insert the disk_request, return false 4. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 26 3-3-4 promote( disk_request, start, end ) input disk_request: the disk request to be re-inserted in the disk queue start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output there is no output. function 1. loop starting from the start position in the disk queue and moving forward towards the end position 2. if the disk_request can be re-inserted in scan order such that its deadline is not violated, then re-insert the disk_request 3. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 27 3-3-5 try_demote( disk_request, start, end ) input disk_request: the disk request to be re-inserted in the disk queue start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output returns true if re-insertion is successful and false otherwise. function 1. loop starting from the end position in the disk queue and moving backward towards the start position 2. if the disk_request can be re-inserted in scan order such that its deadline is not violated and the insertion does not result in the violation of the deadline of any other pending disk requests, then re-insert the disk_request and return true 3. if it is not possible to insert the disk_request, return false 4. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 28 3-3-6 demote( disk_request, start, end ) input disk_request: the disk request to be re-inserted in the disk queue start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output there is no output. function 1. loop starting from the end position in the disk queue and moving backward towards the start position 2. if the disk_request can be re-inserted in scan order such that its deadline is not violated, then re-insert the disk_request 3. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 29 3-3-7 delete( disk_request ) input disk_request: the disk request which is a node in the disk queue to be deleted. output there is no output. function 1. let the next node, if existing, point to the previous node of disk_request instead of disk_request 2. let the previous node, if existing, point to the next node of disk_request instead of disk_request 3. stop. complexity time complexity: O(1) node accesses are needed n is the number of disk requests in the disk queue. 30 3-3-8 get_violated_pending_disk_request( start, end) input start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output returns a disk request whose deadline is violated or null if such a disk request can not be found. function 1. loop starting from the end position in the disk queue and moving backward towards the start position 2. if the deadline of the current disk request is violated, then return the current disk request and stop 3. return null 4. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 31 3-3-9 select_victim( type, start, end) input type: the type of the victim disk request to search for start: the start location in the disk queue at which the search begins end: the end location in the disk queue at which the search ends. output returns a disk request whose type is as given above and whose deadline is not violated, or null if such a disk request can not be found. function 1. loop starting from the start position in the disk queue and moving forward towards the end position 2. if the type of the current disk request is as specified and the deadline of the current disk request is not violated, then return the current disk request and stop 3. return null 4. stop. complexity time complexity: O(n) node accesses are needed n is the number of disk requests in the disk queue. 32 3-3-10 kill( disk_request ) input disk_request: the disk request to be deleted and never to be used again. output there is no output. function 1. let the next node, if existing, point to the previous node of disk_request instead of disk_request 2. let the previous node, if existing, point to the next node of disk_request instead of disk_request 3. reclaim the memory used by the disk_request node 4. stop. complexity time complexity: O(1) node accesses are needed n is the number of disk requests in the disk queue. 33 3-4 MAIN CASES OF ALGORITHM SCAN-RT3 The proposed algorithm has six main cases for scheduling newly-arrived disk requests. These cases represent the core of the algorithm. The six cases are: 1. inserting a Wdn disk request in the disk queue 2. inserting a Wnn disk request in the disk queue 3. inserting an Rdn disk request in the disk queue 4. inserting a Wdl disk request in the disk queue 5. inserting an Rdl disk request in the disk queue 6. inserting an Rnn disk request in the disk queue. These cases are detailed in the following subsections. For each case, the input, output and the handling of the disk request are described in pseudo code. The number of node accesses is taken as a measure of the time complexity of the algorithm. The time complexity is expressed as a function of n, where n is the number of disk requests in the disk queue, which is the same as the number of nodes in the double linked list that represents the disk queue. The time complexity of the algorithm is discussed in more detail in section 3-5. 34 3-4-1 Inserting A Wdn Disk Request In The Disk Queue input Wdn_disk_request: the newly-arrived disk request to be inserted in the disk queue. output there is no output. function 1- compute the deadline of Wdn_disk_request as outlined in table 3-1 2- if( try_insert_in_scan_order( Wdn_disk_request, queue.tail, queue.head ) = true ) 3- then stop 4- insert_in_scan_order( Wdn_disk_request, queue.tail, queue.head ) 5- pending_request = get_violated_pending_disk_request( queue.tail, Wdn_disk_request ) 6- while( pending_request <> null ) 7- switch ( type of pending_request ) 8- case Wdn and Wnn: 9- if( try_promote( pending_request, pending_request, queue.head ) = false ) 10- victim = select_victim( type Rnn, queue.tail, pending_request ) 11-while( victim <> null and pending_request is still violated ) 12- try_demote( victim, queue.tail, pending_request ) 13- victim = select_victim( type Rnn, queue.tail, pending_request ) 14- if( deadline of pending_request is still violated ) 15- victim = select_victim( type Rdl, queue.tail, pending_request ) 16- while( victim <> null and pending_request is still violated ) 17- try_demote( victim, queue.tail, pending_request ) 18- victim = select_victim( type Rdl, queue.tail, pending_request ) 19- if( deadline of pending_request is still violated ) 20- victim = select_victim( type Wdl, queue.tail, pending_request ) 21- while( victim <> null and pending_request is still violated ) 35 22- try_demote( victim, pending_request, queue.tail ) 23- victim = select_victim(type Wdl, queue.tail, pending_request) 24- if( deadline of pending_request is still violated ) 25- victim = select_victim(type Rdn, queue.tail, pending_request) 26- while(victim <> null and pending_request is still violated) 27- try_demote( victim, queue.tail, pending_request ) 28- victim = select_victim( type Wdl, queue.tail, pending_request ) 29- if( deadline of pending_request is still violated ) 30- promote(pending_request, pending_request, queue.head) 31- case Rdn: 32- if( not try_promote( pending_request, pending_request, queue.head ) ) 33- victim = select_victim( type Rnn, queue.tail, pending_request ) 34- while( victim <> null and pending_request is still violated ) 35- try_demote( victim, queue.tail, pending_request ) 36- victim = select_victim( type Rnn, queue.tail, pending_request ) 37- if( deadline of pending_request is still violated ) 38- victim = select_victim( type Rdl, queue.tail, pending_request ) 39- while( victim <> null and pending_request is still violated ) 40- try_demote( victim, queue.tail, pending_request ) 41- victim = select_victim( type Rdl, queue.tail, pending_request ) 36 42- if( deadline of pending_request is still violated ) 43- victim = select_victim( type Wdl, queue.tail, pending_request ) 44- while( victim <> null and pending_request is still violated ) 45- try_demote( victim, queue.tail, pending_request ) 46- victim = select_victim(type Wdl, queue.tail, pending_request) 47- if( deadline of pending_request is still violated ) 48- promote( pending_request, pending_request, queue.head ) 49- case Wdl: 50- if( try_promote( pending_request, pending_request, queue.head ) = false ) 51- victim = select_victim( type Rnn, queue.tail, pending_request ) 52- while( victim <> null and pending_request is still violated ) 53- try_demote( victim, queue.tail, pending_request ) 54- victim = select_victim( type Rnn, queue.tail, pending_request ) 55- if( deadline of pending_request is still violated ) 56- kill( pending_request ) 57- case Rdl: 58- if( not try_promote( pending_request, pending_request, queue.head ) ) 59- victim = select_victim( type Rnn, queue.tail, pending_request ) 60- while( victim <> null and pending_request is still violated ) 61- try_demote( victim, queue.tail, pending_request ) 62- victim = select_victim( type Rnn, queue.tail, pending_request ) 63- if( deadline of pending_request is still violated ) 64- kill( pending_request ) 65- case Rnn: 66- try_promote( pending_request, pending_request, queue.head ) 37 67- pending_request = get_violated_pending_disk_request( queue.tail, Wdn_disk_request ) 68- stop. complexity time complexity: O(n2) node accesses are needed space complexity: O(n) node are needed n is the number of disk requests in the disk queue. 38 3-4-2 Inserting A Wnn Disk Request In The Disk Queue input Wnn_disk_request: the newly-arrived disk request to be inserted in the disk queue. output there is no output. function 1- compute the deadline of Wnn_disk_request as outlined in table 3-1 2- if( try_insert_in_scan_order( Wnn_disk_request, queue.tail, queue.head ) = true ) 3- then stop 4- insert_in_scan_order( Wnn_disk_request, queue.tail, queue.head ) 5- pending_request = get_violated_pending_disk_request( queue.tail, Wnn_disk_request ) 6- while( pending_request <> null ) 7- switch ( type of pending_request ) 8- case Wdn and Wnn: 9- if( try_promote( pending_request, pending_request, queue.head ) = false ) 10- victim = select_victim( type Rnn, queue.tail, pending_request ) 11-while( victim <> null and pending_request is still violated ) 12- try_demote( victim, queue.tail, pending_request ) 13- victim = select_victim( type Rnn, queue.tail, pending_request ) 14- if( deadline of pending_request is still violated ) 15- victim = select_victim( type Rdl, queue.tail, pending_request ) 16- while( victim <> null and pending_request is still violated ) 17- try_demote( victim, queue.tail, pending_request ) 18- victim = select_victim( type Rdl, queue.tail, pending_request ) 19- if( deadline of pending_request is still violated ) 20- victim = select_victim( type Wdl, queue.tail, pending_request ) 21- while( victim <> null and pending_request is still violated ) 39 22- try_demote( victim, pending_request, queue.tail ) 23- victim = select_victim(type Wdl, queue.tail, pending_request) 24- if( deadline of pending_request is still violated ) 25- victim = select_victim(type Rdn, queue.tail, pending_request) 26- while(victim <> null and pending_request is still violated) 27- try_demote( victim, queue.tail, pending_request ) 28- victim = select_victim( type Wdl, queue.tail, pending_request ) 29- if( deadline of pending_request is still violated ) 30- promote(pending_request, pending_request, queue.head) 31- case Rdn: 32- if( not try_promote( pending_request, pending_request, queue.head ) ) 33- victim = select_victim( type Rnn, queue.tail, pending_request ) 34- while( victim <> null and pending_request is still violated ) 35- try_demote( victim, queue.tail, pending_request ) 36- victim = select_victim( type Rnn, queue.tail, pending_request ) 37- if( deadline of pending_request is still violated ) 38- victim = select_victim( type Rdl, queue.tail, pending_request ) 39- while( victim <> null and pending_request is still violated ) 40- try_demote( victim, queue.tail, pending_request ) 41- victim = select_victim( type Rdl, queue.tail, pending_request ) 40 42- if( deadline of pending_request is still violated ) 43- victim = select_victim( type Wdl, queue.tail, pending_request ) 44- while( victim <> null and pending_request is still violated ) 45- try_demote( victim, queue.tail, pending_request ) 46- victim = select_victim(type Wdl, queue.tail, pending_request) 47- if( deadline of pending_request is still violated ) 48- promote( pending_request, pending_request, queue.head ) 49- case Wdl: 50- if( try_promote( pending_request, pending_request, queue.head ) = false ) 51- victim = select_victim( type Rnn, queue.tail, pending_request ) 52- while( victim <> null and pending_request is still violated ) 53- try_demote( victim, queue.tail, pending_request ) 54- victim = select_victim( type Rnn, queue.tail, pending_request ) 55- if( deadline of pending_request is still violated ) 56- kill( pending_request ) 57- case Rdl: 58- if( not try_promote( pending_request, pending_request, queue.head ) ) 59- victim = select_victim( type Rnn, queue.tail, pending_request ) 60- while( victim <> null and pending_request is still violated ) 61- try_demote( victim, queue.tail, pending_request ) 62- victim = select_victim( type Rnn, queue.tail, pending_request ) 63- if( deadline of pending_request is still violated ) 64- kill( pending_request ) 65- case Rnn: 66- try_promote( pending_request, pending_request, queue.head ) 41 67- pending_request = get_violated_pending_disk_request( queue.tail, Wnn_disk_request ) 68- stop. complexity time complexity: O(n2) node accesses are needed space complexity: O(n) node are needed n is the number of disk requests in the disk queue. 42 3-4-3 Inserting An Rdn Disk Request In The Disk Queue input Rdn_disk_request: the newly-arrived disk request to be inserted in the disk queue. output there is no output. function 1- compute the deadline of Rdn_disk_request as outlined in table 3-1 2- if( try_insert_in_scan_order( Rdn_disk_request, queue.tail, queue.head ) = true ) 3- then stop 4- insert_in_scan_order( Rdn_disk_request, queue.tail, queue.head ) 5- pending_request = get_violated_pending_disk_request( queue.tail, Rdn_disk_request ) 6- while( pending_request <> null ) 7- switch ( type of pending_request ) 8- case Wdn and Wnn: 9- if( try_promote( pending_request, pending_request, queue.head ) = false ) 10- victim = select_victim( type Rnn, queue.tail, pending_request ) 11-while( victim <> null and pending_request is still violated ) 12- try_demote( victim, queue.tail, pending_request ) 13- victim = select_victim( type Rnn, queue.tail, pending_request ) 14- if( deadline of pending_request is still violated ) 15- victim = select_victim( type Rdl, queue.tail, pending_request ) 16- while( victim <> null and pending_request is still violated ) 17- try_demote( victim, queue.tail, pending_request ) 18- victim = select_victim( type Rdl, queue.tail, pending_request ) 19- if( deadline of pending_request is still violated ) 20- victim = select_victim( type Wdl, queue.tail, pending_request ) 21- while( victim <> null and pending_request is still violated ) 43 22- try_demote( victim, pending_request, queue.tail ) 23- victim = select_victim(type Wdl, queue.tail, pending_request) 24- if( deadline of pending_request is still violated ) 25- victim = select_victim(type Rdn, queue.tail, pending_request) 26- while(victim <> null and pending_request is still violated) 27- try_demote( victim, queue.tail, pending_request ) 28- victim = select_victim( type Wdl, queue.tail, pending_request ) 29- if( deadline of pending_request is still violated ) 30- promote(pending_request, pending_request, queue.head) 31- case Rdn: 32- if( not try_promote( pending_request, pending_request, queue.head ) ) 33- victim = select_victim( type Rnn, queue.tail, pending_request ) 34- while( victim <> null and pending_request is still violated ) 35- try_demote( victim, queue.tail, pending_request ) 36- victim = select_victim( type Rnn, queue.tail, pending_request ) 37- if( deadline of pending_request is still violated ) 38- victim = select_victim( type Rdl, queue.tail, pending_request ) 39- while( victim <> null and pending_request is still violated ) 40- try_demote( victim, queue.tail, pending_request ) 41- victim = select_victim( type Rdl, queue.tail, pending_request ) 44 42- if( deadline of pending_request is still violated ) 43- victim = select_victim( type Wdl, queue.tail, pending_request ) 44- while( victim <> null and pending_request is still violated ) 45- try_demote( victim, queue.tail, pending_request ) 46- victim = select_victim(type Wdl, queue.tail, pending_request) 47- if( deadline of pending_request is still violated ) 48- promote( pending_request, pending_request, queue.head ) 49- case Wdl: 50- if( try_promote( pending_request, pending_request, queue.head ) = false ) 51- victim = select_victim( type Rnn, queue.tail, pending_request ) 52- while( victim <> null and pending_request is still violated ) 53- try_demote( victim, queue.tail, pending_request ) 54- victim = select_victim( type Rnn, queue.tail, pending_request ) 55- if( deadline of pending_request is still violated ) 56- kill( pending_request ) 57- case Rdl: 58- if( not try_promote( pending_request, pending_request, queue.head ) ) 59- victim = select_victim( type Rnn, queue.tail, pending_request ) 60- while( victim <> null and pending_request is still violated ) 61- try_demote( victim, queue.tail, pending_request ) 62- victim = select_victim( type Rnn, queue.tail, pending_request ) 63- if( deadline of pending_request is still violated ) 64- kill( pending_request ) 65- case Rnn: 66- try_promote( pending_request, pending_request, queue.head ) 45 67- pending_request = get_violated_pending_disk_request( queue.tail, Rdn_disk_request ) 68- stop. complexity time complexity: O(n2) node accesses are needed space complexity: O(n) node are needed n is the number of disk requests in the disk queue. 46 3-4-4 Inserting A Wdl Disk Request In The Disk Queue input Wdl_disk_request: the newly-arrived disk request to be inserted in the disk queue. output there is no output. function 1- compute the deadline of Wdl_disk_request as outlined in table 3-1 2- if( try_insert_in_scan_order( Wdl_disk_request, queue.tail, queue.head) = true ) 3- then stop 4- position = queue.tail 5- while(position <> queue.head ) 6- insert_in_scan_order( Wdl_disk_request, position, queue.head ) 7- pending_request = get_violated_pending_request( queue.tail, Wdl_disk_request ) 8- while(the deadline of pending_request is still violated) 9- switch ( type of pending_request ) 10- case Wdn, Wnn, Rdn, Wdl: 11- victim = select_victim( type Rnn, Wdl_disk_request, queue.tail ) 12- while( victim <> null and the deadline of pending_request is still violated ) 13- delete( victim ) 14- stack_push( victim ) 15- victim = select_victim( type Rnn, Wdl_disk_request, queue.tail ) 16- if ( the deadline of pending_request is no longer violated ) 17- then 18- victim = pop() 19- while( victim <> null ) 20- if( not try_insert_in_scan_order( victim ) ) 21- then append_at_queue_tail( victim ) 22- victim = pop() 23- stop 24- else 25- delete( Wdl_disk_request ) 26- victim = pop() 27- while( victim <> null ) 47 28- re-insert victim in the same old position 29- victim = pop() 30- case Rdl: 31- victim = select_victim( type Rnn, Wdl_disk_request, queue.tail ) 32- while( victim <> null and the deadline of pending_request is still violated ) 33- delete( victim ) 34- stack_push( victim ) 35- victim = select_victim( type Rnn, Wdl_disk_request, queue.tail ) 36- if ( the deadline of pending_request is no longer violated ) 37- then 38- victim = pop() 39- while( victim <> null ) 40- if( not try_insert_in_scan_order( victim ) ) 41- then append_at_queue_tail( victim ) 42- victim = pop() 43- stop 44- else 45- kill( pending_request ) 46- victim = pop() 47- while( victim <> null ) 48- re-insert victim in the same old position 49- victim = pop() 50- case Rnn: 51- try_promote( pending_request, Wdl_disk_request, queue.head ) 52- stop 53- if( the deadline of pending_request is no longer violated ) 54- stop 55- position = next partition 48 56- kill( Wdl_disk_request ) 57- stop. complexity time complexity: O(n2) node accesses are needed space complexity: O(n) node are needed n is the number of disk requests in the disk queue. 49 3-4-5 Inserting An Rdl Disk Request In The Disk Queue input Rdl_disk_request: the newly-arrived disk request to be inserted in the disk queue. output there is no output. function 1- compute the deadline of Rdl_disk_request as outlined in table 3-1 2- if( try_insert_in_scan_order( Rdl_disk_request, queue.tail, queue.head ) = true ) 3- then stop 4- position = queue.tail 5- while( position <> queue.head ) 6- insert_in_scan_order( Rdl_disk_request, position, queue.head ) 7- pending_request = get_violated_pending_request( queue.tail, Rdl_disk_request ) 8- while(the deadline of pending_request is still violated) 9- switch ( type of pending_request ) 10- case Wdn, Wnn, Rdn, Wdl, Rdl: 11- victim = select_victim( type Rnn, Rdl_disk_request, queue.tail ) 12- while( victim <> null and the deadline of pending_request is still violated ) 13- delete( victim ) 14- stack_push( victim ) 15- victim = select_victim( type Rnn, Rdl_disk_request, queue.tail ) 16- if ( the deadline of pending_request is no longer violated ) 17- then 18- victim = pop() 19- while( victim <> null ) 20- if( not try_insert_in_scan_order( victim ) ) 21- then append_at_queue_tail( victim ) 22- victim = pop() 23- stop 24- else 25- victim = pop() 26- while( victim <> null ) 27- re-insert victim in the same old position 50 28- victim = pop() 29- case Rnn: 30- try_promote( pending_request, Rdl_disk_request, queue.head ) 31- stop 32- if(the deadline of pending_request is no longer violated ) 33- stop 34- position = next partition 35- kill( Rdl_disk_request ) 36- stop. complexity time complexity: O(n2) node accesses are needed space complexity: O(n) node are needed n is the number of disk requests in the disk queue. 51 3-4-6 Inserting An Rnn Disk Request In The Disk Queue input Rnn_disk_request: the newly-arrived disk request to be inserted in the disk queue. output there is no output. function 1- compute the deadline of Rnn_disk_request as outlined in table 3-1 2- if( try_insert_in_scan_order( Rnn_disk_request, queue.tail, queue.head ) ) 3- then stop 4- append_at_queue_tail( Rnn_disk_request ) 5- stop. complexity time complexity: O(n) node accesses are needed space complexity: O(n) node are needed n is the number of disk requests in the disk queue. 52 3-5 COMPLEXITY ANALYSIS OF ALGORITHM SCAN-RT3 The number node accesses is taken as the measure of the time complexity of the algorithm. As established below, the time complexity of the algorithm is O(n2), where n is the number of pending disk requests stored in the disk queue at the time of inserting of a newly-arrived disk request. This is the same as the number of nodes in the double linked list that represents the disk queue. For the insertion of a Wdn disk request as explained in subsection 3-4-1, step 2, 4, and 5 each takes O(n) comparisons. The while loop in step 6 can be repeated O(n) times. For the group of step from 8 to 30, each while loop, in steps 11, 16, 21, and 26, is only repeated one or two times at most, not O(n) times because it is sufficient to handle the very first few disk requests. This handling will result in having the deadline of the other disk requests not violated as their deadline was violated in the first place due to the insertion of only one disk request. For the steps 9, 10, 12, 13, 15, 17, 18, 20, 22, 23, 25, 27, 28, and 30, each takes O(n) comparisons. Thus, the time complexity of this group of code is O(n). Similarly, for the groups of code from step 31 to step 48, from step 49 to step 56, from step 57 to step 64, and from step 65 to step 66, each group takes O(n) comparisons. Step 67 takes O(n) comparisons. In this manner, the steps from step 7 to step 67 are responsible for the O(n2) time complexity order, as they take O(n) comparisons and they are repeated O(n) times by the while loop in step 6. Therefore, the time complexity of inserting a Wdn disk request is O(n2). Exactly the same analysis applies for inserting a Wnn disk request in subsection 3- 53 4-2, and an Rdn disk request in subsection 3-4-3. Thus, the time complexity of inserting a Wnn disk request is O(n2) and the time complexity of inserting an Rdn disk request is O(n2). For the insertion of a Wdl disk request as explained in subsection 3-4-4, step 2 takes O(n) comparisons. The while loop in step 5 can be repeated O(n) times. Step 6 takes O(n) comparisons. The while loop in step 8 is repeated one or two times only, not O(n) times because it is sufficient to handle the very first few disk requests whose deadlines are violated regardless of the queue length. Step 11 takes O(n) comparisons whereas the while loop in step 12 is repeated one or two times only. Similarly, step 31 takes O(n) comparisons and the while loop in step 32 is repeated only one or two times. In this manner, the steps 6, 11, and 31 are responsible for the O(n2) as each takes O(n) comparisons and each is repeated O(n) by the while loop in step 5. Therefore, the time complexity of inserting a Wdl disk request is O(n2). For the insertion of an Rdl disk request as explained in subsection 3-4-5, step 2 takes O(n) comparisons. The while loop in step 5 can be repeated O(n) times. Step 6 takes O(n) comparisons. The while loop in step 8 is repeated one or two times only, not O(n) times because it is sufficient to handle the very first few disk requests whose deadlines are violated regardless of the queue length. Step 11 takes O(n) comparisons whereas the while loop in step 12 is repeated one or two times only. In this manner, the steps 6, and 11 responsible for the O(n2) as each takes O(n) comparisons and each is repeated O(n) by the while loop in step 5. Therefore, the time complexity of inserting an Rdl disk request is O(n2). 54 For the insertion of an Rnn disk request as explained in subsection 3-4-6, step 2 takes O(n) comparisons. Therefore, the time complexity of inserting an Rnn disk request is O(n). The number of the nodes representing the disk requests is taken as the measure of the algorithm space complexity. The space complexity of the algorithm is O(n), where n is the number of disk requests in the disk queue which is the same as the number of nodes in the double linked list that represents the disk queue. The double linked list is responsible for the O(n) space complexity of algorithm. Thus, it is established that the overall time complexity of the algorithm is O(n2) and the space complexity is O(n). 3-6 TERMINATION AND CORRECTNESS OF ALGORITHM SCAN-RT3 This section proves the termination and establishes informally the correctness of the proposed algorithm. It should be noted that the algorithm is a best-effort heuristic. The search space of the problem is all the permutations of all the n pending disk requests in the disk queue which is (n!). 3-6-1 Termination For the insertion of a Wdn disk request as explained in subsection 3-4-1, steps 1, 2, 3, 4, and 5 take only finite steps. The while loop in step 6 has to terminate because each pending disk request, whose deadline is violated, is handled and there is only a finite number of them. The while loops in steps 11, 16, 21, 26, 34, 39, 44, 52, and 60 all terminate because there is always a finite number of victims that can be selected at 55 any time. Exactly the same method applies for inserting a Wnn disk request in subsection 3- 4-2, and an Rdn disk request in subsection 3-4-3. Thus, the insertion of a Wnn disk request and the insertion of an Rdn disk request must terminate as established above. For the insertion of a Wdl disk request as explained in subsection 3-4-4, steps 1, 2, 3, and 4 take only finite steps. The while loop in step 5 has to terminate because it loops from the queue tail to the queue head. The while loop in step 8 terminates because there is always a finite number of pending disk requests whose deadlines are violated. The while loops in steps 12, 19, 27, 32, 39 and 47 all terminate because there is always a finite number of victims that can be selected at any time. For the insertion of an Rdl disk request as explained in subsection 3-4-5, steps 1, 2, 3, and 4 take only finite steps. The while loop in step 5 has to terminate because it loops from the queue tail to the queue head. The while loop in step 8 terminates because there is always a finite number of pending disk requests whose deadlines are violated. The while loops in steps 12, 19, and 26 all terminate because there is always a finite number of victims that can be selected at any time. For the insertion of an Rnn disk request as explained in subsection 3-4-6, steps 1, 2, 3, 4, and 5 take only finite steps. Thus, the insertion must terminate after a finite number of steps. Thus, the above arguments prove the termination of the algorithm. 56 3-6-2 Correctness For the insertion of a Wdn disk request as explained in subsection 3-4-1, step 1 assigns a deadline for the disk request. Step 2 attempts to insert the disk request safely. If it terminates successfully, then the newly-arrived disk request will be inserted in scan order such that its deadline and the deadlines of all other pending disk requests are not violated. If step 2 does not terminate successfully, the algorithm attempts to insert the disk request in scan order such that its deadline is not violated. Some other disk requests may get their own deadlines violated due to this insertion. To recover this problem, in step 8, the algorithm attempts to select some lower priority disk requests as victims and to demote them down the disk queue. This is done only if this results in accommodating the pending disk request whose deadline is violated. Similarly, in step 31, the algorithm attempts to select some lower priority disk requests as victims. In step 49, the algorithm attempts to select some Rnn disk requests as victims and to demote them if this results in accommodating the Wdl pending disk request or the Wdl pending disk request is rejected to accommodate the newly-arrived Wdn disk request according to the priority order. Similarly, in step 57, the algorithm attempts to select some Rnn disk requests as victims and to demote them if this results in accommodating the Rdl pending disk request or the Rdl pending disk request is rejected to accommodate the newly-arrived Wdn disk request according to the priority order. If all these attempts fail, the newly-arrived Wdn will be rejected and the systems will be halted. Thus, an attempt is made to insert the newly-arrived Wdn disk request in scan order such that its deadline is not violated as well as the deadlines of other pending disk requests. 57 Exactly the same arguments apply for the insertion of a Wnn disk request in subsection 3-4-2, and an Rdn disk request in subsection 3-4-3. For the insertion of a Wdl disk request as explained in subsection 3-4-4, step 1 assigns a deadline for the disk request. Step 2 attempts to insert the disk request safely. If it terminates successfully, then the newly-arrived disk request will be inserted in scan order such that its deadline and the deadlines of all other pending disk requests are not violated. If step 2 does not terminate successfully, the algorithm attempts to insert the disk request in scan order such that its deadline is not violated. Some other disk requests may get their own deadlines violated due to this insertion. To recover this problem, in step 10, the algorithm attempts to select some Rnn disk requests as victims and to demote them down the disk queue. This is done only if this results in accommodating the pending disk request whose deadline is violated. In step 31, the algorithm attempts to select some Rnn disk requests as victims and to demote them down the disk queue if this results in accommodating the pending disk request or the Rdl pending disk request is rejected to accommodate the newly-arrived Wdl disk request according the priority order. If all these attempts fail, the newly-arrived Wdl disk request will be rejected. Thus, an attempt is made to insert the newly-arrived Wdl disk request in scan order such that its deadline is not violated as well as the deadlines of other pending disk requests. For the insertion of an Rdl disk request as explained in subsection 3-4-5, step 1 assigns a deadline for the disk request. Step 2 attempts to insert the disk request safely. If it terminates successfully, then the newly-arrived disk request will be inserted in scan order such that its deadline and the deadlines of all other pending disk 58 requests are not violated. If step 2 does not terminate successfully, the algorithm attempts to insert the disk request in scan order such that its deadline is not violated. Some other disk requests may get their own deadlines violated due to this insertion. To recover this problem, in step 10, the algorithm attempts to select some Rnn disk requests as victims and to demote them down the disk queue. This is done only if it results in accommodating the newly-arrived disk request. Otherwise, the newlyarrived disk request is rejected. Thus, an attempt is made to insert the newly-arrived Rdl disk request in scan order such that its deadline is not violated as well as the deadlines of other pending disk requests. For the insertion of an Rnn disk request as explained in subsection 3-4-6, step 1 assigns a deadline for the disk request. Step 2 attempts to insert the disk request safely. If it terminates successfully, then the newly-arrived disk request will be inserted in scan order such that its deadline and the deadlines of all other pending disk requests are not violated. If step 2 does not terminate successfully, the algorithm appends the disk request to the disk queue tail. Thus, the newly-arrived Rnn disk request is inserted in scan order without violating the deadline of any other pending disk request. From the above discussion, the overall correctness of the algorithm is informally established. 3-7 CONCLUSION In this chapter, algorithm SCAN-RT3, which is a real-time disk scheduling algorithm for multimedia storage servers, is proposed. This algorithm overcomes the 59 shortages of existing real-time disk scheduling algorithms which were discussed in section 2-4. The proposed algorithm handles the disk request types Wdn, Wnn, Rdn, Wdl, Rdl, and Rnn. It uses the multi-partitioning technique to maintain several scan order partitions in the disk queue. The time complexity and the space complexity of the algorithm are studied. Also, the correctness of the algorithm is established. The main features of the proposed algorithm and the existing real-time disk scheduling algorithms for multimedia storage servers, which were discussed in section 2-3, are summarized in table 3-2. Algorithm Applications supported Disk request types that are handled Complexity EDF Video-on-demand Rdl Time: O(n) Space: O(n) SCAN-RT1 Video-on-demand Rdl Time: O(n) Space: O(n) SCAN-RT2 Video-on-demand and partial support for video editing Rdl, Wnn Time: O(n2) Space: O(n) Proposed Algorithm SCAN-RT3 Full support for all the above applications as well as those listed in table 1-1 Rdl, Wnn, Rnn, Wdn, Wdl, Rdn Time: O(n2) Space: O(n) Table 3-2: Summary of existing real-time disk scheduling algorithms The algorithm SCAN-RT3, can be added to the proposed taxonomy depicted in figure 2-2. The revised taxonomy is depicted in figure 3-3. 60 Figure 3-3: Revised taxonomy of real-time disk scheduling algorithms In the next chapter, a model is developed for a multimedia storage server, and the performance of the proposed algorithm is studied and compared to the existing realtime disk scheduling algorithms. EDF (Rdl) [6] sorting on disk request deadline SCAN-RT1 (Rdl) [6] SCAN-RT2 (Rdl, Wnn) [1] SCAN-RT3 multi-partition (Rdl, Wnn, Rnn Wdn, Wdl, Rdn) sorting on disk request position Real-time disk scheduling algorithms 61 CHAPTER FOUR EXPERIMENTS AND RESULTS 4-1 INTRODUCTION A real-time disk scheduling algorithm (SCAN-RT3) for multimedia storage servers was proposed in the previous chapter. In this chapter, a simulation model, implementing the proposed algorithm, is developed. Several experiments are conducted to assess the performance of the proposed algorithm. The system model, and the model validation and verification are presented in section 4-2. In section 4-3, a study of the performance of the algorithms EDF, SCAN-RT1 and SCAN-RT3 is presented. In section 4-4, a study of the performance of the algorithms SCAN-RT2 and SCAN-RT3 is conducted. In section 4-5, the performance of the algorithm SCAN-RT3 for combined video-on-demand, and video editing is investigated. In section 4-6, the performance of the algorithm SCAN-RT3 for various user mix ratios is studied. Finally, the chapter is concluded in section 4-7. 4-2 SYSTEM MODEL In this section, a model is proposed for a multimedia storage server. A general description of the model is outlined in subsection 4-2-1. The disk subsystem is described in subsection 4-2-2. The parameters of the systems are discussed in 62 subsection 4-2-3. The validation and verification of the model are established in subsections 4-2-4 and 4-2-5, respectively. The experimentation environment is detailed in subsection 4-2-6. 4-2-1 General Description Of The Multimedia Storage Server The experiments are based on a discrete-event simulator that models the PanaViss multimedia storage server used in [1]. Users are connected to the multimedia storage server through a high speed network [10, pp 236-242], for example an ATM network [11]. The multimedia server has several disk storage units that are fully interconnected through an ATM backbone network. The disk storage units are called disk storage servers and each disk storage server is a separate single-processor machine. The architecture of the multimedia storage server is outlined in figure 4-1. Figure 4-1: Architecture of a Multimedia Storage Server The server supports MPEG-encoded video streams. Each stream is broken into user terminal External Network Multimedia Storage Server ATM Backbone Network System Control Manager and File Distributer user terminal user terminal . . . Disk Storage Server Disk Storage Server Disk Storage Server . . . 63 fixed length pieces, termed media blocks. The size of a media block is the same as the size of a disk page. The media blocks for a given video stream are stored distributively through the whole file system of the multimedia storage server to achieve load balancing and fault tolerance [12]. The system control manager and file distributor is responsible for distributing the media blocks thought the whole file system as well as updating the necessary metadata. Each disk storage server has two threads. The first thread handles the user requests and the second thread retrieves and stores the requested media blocks. The different threads of the multimedia storage servers communicate with each other by sending messages via the ATM backbone network. The first thread handles the requests of the users assigned to the disk storage server. When the admission control algorithm admits a new user to a disk storage server, the first thread retrieves a list of pointers to all media blocks of the requested video stream. Then, the first thread sends read or write disk requests on behalf of the user to the second thread of the disk storage server and to the instances of the second thread running on other disk storage servers. The second thread is responsible for retrieving the media blocks from the local file system (which is mounted on the RAID), and for storing media blocks to the local file system. 64 For video-on-demand, users are connected to the external network using set-top boxes that have the following functions: decoding MPEG-encoded video data, providing user interface for virtual VCR function requests and communicating with the disk storage server. For video editing, users are connected to the external network using multimedia workstations that enable the users to edit the video clips. 4-2-2 Disk Model Used In The Multimedia Storage Server The multimedia storage server uses several disk storage units which are called disk storage servers. Each disk storage server has one RAID (Redundant Array of Inexpensive/Independent Disks) [13]. A RAID consists of a group disks. The parameters of the type of the disk drive used are listed in table 4-1 [1]. Disk Parameter Value Type Quantum XP32150 No. of cylinders 3832 Tracks/Cylinder 10 Sector size 512 Bytes Rotation Speed 7200 RPM Average Seek 8.5 mSec Seek cost function 0.8 + 0.002372(d) +0.125818(Öd) Disk Size 2.1 GBytes File Block Size 64 KBytes Transfer Speed 4.9 – 8.2 MBytes/sec Disks per RAID 5 (4 data 1 Parity) Table 4-1: Disk parameters In this disk storage server, the data distribution scheme is coarse grained striping and the redundancy mechanism is separate parity disk [14]. The disk simulation is based on the analytic model presented in [15]. To calculate the time required to service a disk request, it is required to compute the seek time, thee latency time, and the transmission time as described below. 65 The seek time is the time required by the disk head to move from its current cylinder to the cylinder of the disk request to be serviced. It can be computed using the seek cost function in table 4-1. Parameter d is the number of cylinders traveled by the disk head, which is equal to the absolute difference between the cylinder number of the current disk head position and the cylinder number of the disk request. The latency time (or rotational delay) is the time required for the disk page to rotate from its position, when the disk head reaches the cylinder number on which the disk page is located, to a position adjacent to the disk head. Latency time can be computed using the number of disk revolutions per minute (RPM), which is listed in table 4-1. The time required for one disk revolution is the reciprocal of the rotation speed. Latency time is expressed as a fraction of the time required for one disk revolution. The transmission time (or transfer time) is the time for the disk page to spin by the disk head. The transmission time is equal to the disk page size divided by the transmission rate (transfer rate). The transmission rate is determined by the track size and the time of one disk revolution. 4-2-3 Parameters Of The System The simulated multimedia storage server provides access to MPEG1 steams. MPEG1 steams have a bandwidth of 1.5 MBits/sec [16, pp 160-163]. The system wide deadline for write disk requests and read disk requests, referred to 66 in table 3-1, is selected as 10 seconds to prevent indefinite postponement, and to prevent the loss of data in the case of a system crash. For the Wdn, Rdn, Wdl, and Rdl disk request types, the deadline introduced by the bandwidth of the multimedia stream (MPEG1 video) is 350 mSec as computed below. (disk page size)/(multimedia bandwidth) = (64k * 8) / (1.5 M) = 350 mSec {4-1} The write buffer size is taken to be proportionate to the number of users who perform the writing operations, this means users who issue the disk requests of the types Wdn, Wnn, and Wdl [17, pp 240-245]. Each disk has a separate write buffer [1]. The arrival of new users is modeled by a Poisson process [18, pp 405 - 409]. Initially the mean inter-arrival time of users is taken to be five minutes. By conducting a sensitivity analysis study, it is found that the mean inter-arrival time does not affect the results as long as it is more than 350 mSec which is typical. As the users access MPEG1 steams, each user issues a disk request every 350 mSec as established above. Thus, if a time window of 350 mSec is considered, each user must issue exactly one disk request in the time window. The Poisson process used to model the arrivals of new users is responsible for the distribution of the disk requests in the time window as shown in figure 4-2. Figure 4-2: Window to generate the disk requests 0 mSec 350 mSec disk request 67 The length of a single run is initially chosen to read or write a 160 minute video clip. It is found that it is sufficient to consider short video clips whose length is as short as eight minutes because the system reaches its steady state quickly. 4-2-4 Validation Of The System Validation is “solving the correct problem” [18, pp 298-301]. The following points establish the validity of the system. 1. The model used for the multimedia storage server is a model for a commercial multimedia storage server [1]. 2. The disk model is analytical [15]. 3. The system parameters are provided by similarity to existing systems. For example, modeling the arrivals of users using a Poisson process is well justified. Other system parameters are justified as explained in subsection 4-2-3. 4-2-5 Verification Of The System Verification is “solving the problem correctly” [18, pp 298-301]. The following points are carried out to verify the system. 1. The results of the experiments were compared to similar results that are published in the literature. 2. The disk model was verified by tracing many representative cases and the measured statistical variables are the as same as expected. For example, the measured average seek time for the disk was the same as the average seek time provided by the disk manufacturer. 3. The proposed algorithm and the other simulated algorithms were verified by tracing many representative cases using exhaustive paper and pencil verification. 68 4. For the results of the experiments, output data analysis was carried out to ensure a stable mean with low variance by controlling the single run length and the number of repetitions. 4-2-6 Experimentation Environment The simulator and the proposed algorithm were implemented using the C programming language. The Microsoft Visual C++ (version 5) compiler is used to generate the executable code. To run the experiments, seven Compaq DeskPro 6000 (Intel Pentium II 233 Mega Hz processor, and 32 MBytes Ram), running Microsoft Windows NT workstation version 4, were used concurrently. The duration of the experiments was about 1700 computer hours. The number of repetitions for each run is variable. Each run is repeated, until the loss rate and the average delay time are almost constant. Only a 2% change in the mean of the statistical measure is allowed with monotonically decreasing variance of the statistical measure. For each experiment, the x-axis represents the number of users per disk storage server. The y-axis represents either the loss rate (as a percentage) of the disk requests or the average delay time (in seconds) taken to serve a disk request. The problem is of a discrete nature. Continuous curves are used instead of histograms. This is more convenient for comparing different algorithms and for 69 studying the general trend of the system. The plotted curves are in reality a group of discrete points but are represented with continuous curves for convenience. Simulation runs were conducted for each point on the x-axis. To compute a single point on the plotted curves, the required number of users is obtained through the Poisson process described above following the input user mix ratio. Then, the time window, which is used to generate the disk requests, is constructed. Thus, the generation of the disk requests is initiated (arrivals of disk requests) and the disk requests are served by the disk units using the analytic model (service of disk requests). The outputs of the system, which are loss rates and delay times, are monitored. This process is repeated to compute the mean as established above. The performance of the different real-time disk scheduling algorithms is assessed by comparing the loss ratio of Rdl and Wdl disk requests, and the delay time of all the other types of the disk requests. The maximum number of users that can be supported at a 3% Rdl loss ratio is considered for each algorithm. The 3% Rdl loss rate guarantees a quality of service for video-on-demand users such that only one frame of the thirty frames per second is lost. 70 4-3 EXPERIMENTAL RESULTS FOR ALGORITHMS EDF, SCAN-RT1, AND SCAN-RT3 In this experiment, algorithms that handle Rdl disk requests are compared. The performance of algorithms EDF, SCAN-RT1, and SCAN-RT3 is assessed. The Rdl disk request type is used in video-on-demand applications, where all users are viewers and issue only Rdl disk requests. The write buffer size is zero. For this experiment, as only Rdl disk requests are considered, the difference between algorithms SCAN-RT1 and SCAN-RT3 is due to multi-partitioning only. Figure 4-3: Rdl loss rate for algorithms EDF, SCAN-RT1, and SCAN-RT3 Figure 4-3 shows that at a 3% Rdl loss rate, algorithm EDF can support up to 63 users, algorithm SCAN-RT1 can support up to 76 users, and algorithm SCAN-RT3 can support up to 77 users. The algorithm SCAN-RT3 has the least Rdl loss rate, then the algorithm SCANRdl loss rate 0 3 6 9 12 15 18 21 24 27 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate SCAN-RT3 SCAN-RT1 EDF 71 RT1, followed by the algorithm EDF. Therefore, SCAN-RT3 and SCAN-RT1 are superior to EDF. Also, SCAN-RT3 is marginally better than SCAN-RT1 due to the effect of multi-partitioning. 72 4-4 EXPERIMENTAL RESULTS FOR ALGORITHMS SCAN-RT2 AND SCAN-RT3 In this experiment, algorithms which handle Rdl and Wnn disk requests are compared. The performance of SCAN-RT2 and SCAN-RT3 is assessed. The user mix ratio is Rdl : Wnn = 3 : 1, meaning that half users are viewers (issuing Rdl disk requests as in a video-on-demand application) and the other half are editors (issuing an equal number of Rdl and Wnn disk requests as in a video authoring application). The handling of Rdl and Wnn disk requests is only a partial support for combined video editing and video-on-demand applications because Rnn disk requests, which are issued by editors, are not handled. The write buffer size is 80 disk pages per disk storage server. For this experiment, as only Rdl and Wnn disk requests are considered, the difference between algorithm SCAN-RT2 and SCAN-RT3 is due to multi-partitioning only. Figure 4-4: Rdl loss rate for algorithms SCAN-RT2 and SCAN-RT3 Rdl loss rate 0 1 2 3 4 5 6 7 8 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate SCAN-RT2 SCAN-RT3 73 Figure 4-5: Rdl delay time for algorithms SCAN-RT2 and SCAN-RT3 Figure 4-6: Wnn delay time for algorithms SCAN-RT2 and SCAN-RT3 Figures 4-4 through 4-6 show that at a 3% Rdl loss rate, algorithm SCAN-RT2 can Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds SCAN-RT2 SCAN-RT3 Rdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds SCAN-RT2 SCAN-RT3 74 support up to 76 users at a Wnn delay time of 122 mSec, and algorithm SCAN-RT3 can support up to 77 users at a Wnn delay time of 134 mSec. The algorithm SCAN-RT3 has the least Rdl loss rate, then the algorithm SCANRT2. Considering the Wnn delay time, the algorithm SCAN-RT2 has lesser Wnn delay time, then the algorithm SCAN-RT3. The time complexity of these algorithms is O(n2). Therefore, SCAN-RT3 is marginally better than SCAN-RT2, at the same order of complexity, and at the cost of a slight increase in the Wnn delay time. 75 4-5 EXPERIMENTAL RESULTS FOR COMBINED VIDEO-ON-DEMAND AND VIDEO EDITING APPLICATIONS In a video-on-demand application, users (viewers) issue Rdl disk requests. For a video editing application, users (editors) issue Rnn and Wnn disk requests. As editors buffer the media clips at their terminals, the number of the Rnn disk requests is expected to be equal to the number of the Wnn disk requests. Algorithm SCAN-RT3 is able to handle the disk request types Rdl, Wnn and Rnn. Thus, it is able to fully support video editing and video-on-demand applications. 4-5-1 Experiment For Half Viewers And Half Editors In this experiment, only the performance of algorithm SCAN-RT3 is assessed. The user mix ratio is viewers : editors = 1 : 1, which is Rdl : Wnn : Rnn = 2 : 1 : 1. The write buffer size is 80 disk pages per disk storage server. Figure 4-7: Rdl loss rate for algorithm SCAN-RT3 Rdl loss rate 0 1 2 3 4 5 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 users % loss rate 76 Figure 4-8: Rdl delay time for algorithm SCAN-RT3 Figure 4-9: Wnn delay time for algorithm SCAN-RT3 Rdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 77 Figure 4-10: Rnn delay time for algorithm SCAN-RT3 Figures 4-7 through 4-10 show that at a 3% Rdl loss rate, algorithm SCAN-RT3 can support up to 80 users at a Wnn delay time of 154 mSec, and an Rnn delay time of 251 mSec. Rnn delay time 0 0.2 0.4 0.6 0.8 1 1.2 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 users seconds 78 4-5-2 Comparison Between Algorithm SCAN-RT2 And SCAN-RT3 For Half Viewers And Half Editors In this experiment, the performance of algorithm SCAN-RT2 and SCAN-RT3 is assessed. The user mix ratio is viewers : editors = 1 : 1 and the number of buffers is 80 per disk storage server. The first algorithm, SCAN-RT2, can only handle Rdl and Wnn disk requests. The second algorithm, SCAN-RT3, can handle Rdl, Wnn, Rnn disk requests. Thus, it fully supports all the required disk requests. Figure 4-11: Read disk requests loss rate for algorithms SCAN-RT2 and SCAN-RT3 Read requests loss rate 0 1 2 3 4 5 6 7 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate SCAN-RT2 SCAN-RT3 79 Figure 4-12: Read disk requests delay time for algorithms SCAN-RT2 and SCAN-RT3 Figure 4-13: Wnn delay time for algorithms SCAN-RT2 and SCAN-RT3 Figures 4-11 through 4-13 show that at a 3% read requests loss rate, algorithm SCAN-RT2 can support up to 77 users at a Wnn delay time of 146 mSec, and algorithm SCAN-RT3 can support up to 82 users at a Wnn delay time of 466 mSec. Close study of the above figures reveals that algorithm SCAN-RT3 has less read disk requests loss rate than algorithm SCAN-RT2. The time complexity of both algorithms is O(n2). Thus, the proposed algorithm resulted in lower loss rate for the Read requests delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds SCAN-RT2 SCAN-RT3 Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds SCAN-RT2 SCAN-RT3 80 read disk requests at the expense of a higher delay for the Wnn disk requests. Also, the proposed algorithm is able to support the functionality required by the editors as they introduce Rnn disk requests which can not be lost. This experiment clearly shows the contribution of the proposed algorithm. The algorithm SCAN-RT3 provides full functionality and better performance. Thus, it is possible to support more users by using the proposed algorithm rather than other existing algorithms. 81 4-5-3 Other User Mix Ratios Of Viewers And Editors For Algorithm SCANRT3 In this subsection, three other user mix ratios for the case of combined video-ondemand and video editing applications are presented. The performance of the algorithm SCAN-RT3 is outlined in these experiments. In a video-on-demand application, users (viewers) issue Rdl disk requests. For a video editing application, users (editors) issue Rnn and Wnn disk requests. The different user mix ratios for editors and viewers are listed in table 4-1. Viewers : editors ratio Subsection 0.00 : 1.00 Subsection 4-5-3-1 0.25 : 0.75 Subsection 4-5-3-2 0.50 : 0.50 Subsection 4-5-1 0.75 : 0.25 Subsection 4-5-3-3 1.00 : 0.00 Section 4-3 Table 4-2: Mix ratios for video-on-demand and video editing 4-5-3-1 User mix ratio 1 for viewers and editors In this experiment, the case of combined video-on-demand and video editing applications is considered. The performance of the algorithm SCAN-RT3 is outlined for the ratio of viewers : editors = 0 : 8. This means that Rdl : Wnn : Rnn = 0 : 4 : 4. The write buffer size is 160 disk pages per disk storage server. 82 Figure 4-14: Wnn delay time for algorithm SCAN-RT3 Figure 4-15: Wnn delay time for algorithm SCAN-RT3 Figures 4-14 and 4-15 outline the performance of the algorithm for this experiment. The algorithm can support at most 72 users per each disk storage server. At 72 users, the Rnn delay is 266 mSec. Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Rnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 83 4-5-3-2 User mix ratio 2 for viewers and editors In this experiment, the case of combined video-on-demand and video editing applications is considered. The performance of the algorithm SCAN-RT3 is outlined for the ratio of viewers : editors = 2 : 6. This means Rdl : Wnn : Rnn = 2 : 3 : 3. The write buffer size is 120 disk pages per disk storage server. Figure 4-16: Rdl loss rate for algorithm SCAN-RT3 Figure 4-17: Rdl delay time for algorithm SCAN-RT3 Rdl loss rate 0 0.05 0.1 0.15 0.2 0.25 0.3 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate Rdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 84 Figure 4-18: Wnn delay time for algorithm SCAN-RT3 Figure 4-19: Rnn delay time for algorithm SCAN-RT3 Figures 4-16 through 4-19 outline the performance of the algorithm for this experiment. The algorithm can support at most 73 users per each disk storage server. At 73 users, the Rnn delay is 209 mSec and the Rdl loss rate is 0.26%. Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Rnn delay time 0 0.05 0.1 0.15 0.2 0.25 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 85 4-5-3-3 User mix ratio 3 for viewers and editors In this experiment, the case of combined video-on-demand and video editing applications is considered. The performance of the algorithm SCAN-RT3 is outlined for the ratio of viewers : editors = 6 : 2. This means Rdl : Wnn : Rnn = 6 : 1 : 1. The write buffer size is 40 disk pages per disk storage server. Figure 4-20: Rdl loss rate for algorithm SCAN-RT3 Figure 4-21: Rdl delay time for algorithm SCAN-RT3 Rdl loss rate 0 1 2 3 4 5 6 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate Rdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 86 Figure 4-22: Wnn delay time for algorithm SCAN-RT3 Figure 4-23: Rnn delay time for algorithm SCAN-RT3 Figures 4-20 through 4-23 outline the performance of the algorithm for this experiment. At 3% Rdl loss rate, the algorithm can support up to 78 users with a Wnn delay time of 132 mSec and the Rnn delay time of 151 mSec. Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Rnn delay time 0 0.05 0.1 0.15 0.2 0.25 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 87 4-6 OTHER GENERAL USER MIX RATIOS 4-6-1 User Mix Ratio 1 The user mix ratio in this experiment is typically encountered in the case of high quality real-time recording of a football match. The performance of the algorithm SCAN-RT3 is outlined for the user mix ratio viewer : editor : high quality recording = 8 : 1 : 1. This means that Rdl : Wnn : Rnn : Wdn = 16 : 1 : 1 : 2. The write buffer size is 48 disk pages per disk storage server. Figure 4-24: Rdl loss rate for user mix ratio 1 Figure 4-25: Rdl delay time for user mix ratio 1 Rdl loss rate -1 0 1 2 3 4 5 6 7 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate Rdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 88 Figure 4-26: Wnn delay time for user mix ratio 1 Figure 4-27: Rnn delay time for user mix ratio 1 Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Rnn delay time 0 0.05 0.1 0.15 0.2 0.25 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 89 Figure 4-28: Wdn delay time for user mix ratio 1 Figures 4-24 through 4-28 outline the performance of the algorithm for this experiment. The algorithm can support up to 78 users at 3% Rdl loss rate with low delay times for all disk request types. Wdn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 90 4-6-2 User Mix Ratio 2 The user mix ratio in this experiment is typically encountered in the case of low quality real-time recording of a football match. The performance of the algorithm SCAN-RT3 is outlined for the user mix ratio viewer : editor : low quality recording = 8 : 1 : 1 which is Rdl : Wnn : Rnn : Wdl = 16 : 1 : 1 : 2. The write buffer size is 48 disk pages per disk storage server. Figure 4-29: Rdl loss rate for user mix ratio 2 Figure 4-30: Rdl delay time for user mix 2 Rdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Rdl loss rate -1 0 1 2 3 4 5 6 7 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate 91 Figure 4-31: Wnn delay time for user mix ratio 2 Figure 4-32: Rnn delay time for user mix ratio 2 Wnn delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds Rnn delay time 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 92 Figure 4-33: Wdl loss rate for user mix ratio 2 Figure 4-34: Wdl delay time for user mix ratio 2 Figures 4-29 through 4-34 outline the performance of the algorithm for this experiment. The algorithm can support up to 78 users at 3% Rdl loss rate with low delay times for all disk request types and a very small Wdl loss rate. Wdl loss rate -0.01 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users % loss rate Wdl delay time 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 users seconds 93 4-6-3 User Mix Ratio 3 This experiment represents a previewing application where video streams are retrieved from the multimedia storage server for synchronous playback without allowing any losses. The performance of the algorithm SCAN-RT3 is outlined where all users are Rdn viewers. The write buffer size is zero disk pages per disk storage server. Figure 4-35: Rdn delay time for user mix ratio 3 Figure 4-35 outlines the performance of the algorithm for this experiment. At most 43 users per disk storage server can be supported with a loss rate of zero. This means all Rdn disk requests are fulfilled. Rdn delay time 0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 0.02 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 users seconds 94 4-6-4 User Mix Ratio 4 In this experiment, a theoretical user mix ratio is used to show the performance of the algorithm when all the types of the disk requests depicted in table 1-1 are used. The performance of the algorithm SCAN-RT3 is assessed for the user mix ratio Rdl : Wnn : Rnn : Wdn : Wdl : Rdn = 1 : 1: 1 : 1 : 1 : 1. The write buffer size is 160 disk pages per disk storage server. It is found that at most 63 users can be supported at a 0.0048% Rdl loss rate and 0.0046% Wdl loss rate. The delay times for Rdl, Rdn, Wnn, Rnn, Wdl, Wdn disk requests are 59.3, 59.6, 59.7, 60.4, 59.2, 59.7 mSec respectively. 4-7 CONCLUSION In this chapter, a simulation model for a multimedia storage server is described. A simulation study is conducted to assess the performance of the proposed algorithm. The proposed algorithm is found to be superior to other existing algorithms. Several experiments are conducted to find the performance of the algorithm under different user mix ratios. 95 CHAPTER FIVE CONCLUSIONS AND FUTURE EXTENSIONS 5-1 CONCLUSIONS This thesis considers the problem of real-time disk scheduling for multimedia storage servers. A survey of existing real-time disk scheduling algorithms for multimedia storage servers was conducted. The need to extend existing algorithms was established after a close study of the existing algorithms. A proposed algorithm which handles all types of the disk requests, namely Wdn, Wnn, Rdn, Wdl, Rdl, and Rnn was proposed. The proposed algorithm was detailed, its time and space complexity analyses were discussed, and the proof of termination and correctness were established. The algorithm employed a new technique, which is called multi-partitioning, for the disk queue organization. Multi-partitioning is used in order to maintain several scan order partitions in the disk queue. A simulation study was conducted to assess the performance of the proposed 96 algorithm compared to other existing real-time disk scheduling algorithms for multimedia storage servers. The performance of the proposed algorithm was studied for different user mix ratios. It was established that the proposed algorithm handles all the disk request types efficiently. Thus, the objectives of the work were accomplished. 5-2 FUTURE EXTENSIONS Numerous problems of multimedia storage servers need to be investigated. When building multimedia storage servers, solutions for those problems are handled in a case-by-case basis. It is required to provide solutions that are general, robust, and scalable. Firstly, the following list presents some points of the proposed algorithm that need to be investigated. 1. Much more user mix ratios should be studied. 2. The algorithm uses a double linked list to represent the disk queue. Other data structures, for example spatial data structures, should be investigated to be employed by the proposed algorithm. 3. Other media types, such as audio and images, and other video stream types, such as MPEG-2 and AVI, should be studied. 4. The performance of the algorithm should be studied in the presence of the failure of some disk units. 5. The use of a single shared buffer instead of a separate buffer for each disk is expected to give better buffer management. 6. Equation 3-1, which is used to assign a deadline for each write disk request, uses a computed arrival rate of the write disk requests. The effect of over 97 estimation and under-estimation of the arrival rate should be studied. 7. Extend the algorithm to accommodate other types of constrains such as those imposed by prefetching application-controlled file caching [19]. 8. Mathematical analysis of the algorithm should be conducted to find the probability distribution of the types of the disk requests in the disk queue for a given user mix ratio. 9. Prove the correctness of the algorithm formally by using invariance relations. Secondly, the following open problems are related to the work in this thesis. 1. It is required to develop an admission control algorithm based on the proposed algorithm. An admission control algorithm should admit a new user only if it guarantees a minimum quality of service required by this new user as well as current users. 2. Data placement algorithms should be used to guarantee load balancing for all system units, even in the presence of a failure of some unites [20]. 3. It is required to develop algorithms that optimize the use of the server-side buffers and the client-side buffers for the optimal bandwidth allocation strategy for the delivery of multimedia data [21]. 4. It is required to employ real-time disk scheduling algorithms in the design of high performance web servers that support multimedia data, because it is expected that all users will access the multimedia data through fast web connections [22]. 98 REFERENCES [1] W. Aref, I. Kamel, N. Niranjan, and S. Ghandharizadeh, “Disk Scheduling for Displaying and Recording Video in Non-Linear News Editing Systems”, International Conference in Multimedia and Computer Networks, San Jose, California, 1997. [2] P. Agnew, and A. Kellerman, Distributed Multimedia: Technologies, Applications, and Opportunities in the Digital Information Industry, ACM Press and Addison-Wesley 1996 [3] H. Deitel, An Introduction to Operating Systems, Second Edition, Addison- Wesley Publishing Company 1990. [4] H. Vin, A. Goyal, and P. Goyal, “Algorithms for Designing Large-Scale Multimedia Servers”, Computer Communications, Vol. 18, No. 3, 1995 [5] P. Shenoy and H. Vin, “Cello: A Disk Scheduling Framework for Next-generation Operating Systems”, ACM SIGMETRICS’98, 1998 [6] A. Reddy, and J.Wylie, “I/O Issues in a Multimedia System”, IEEE Computer, March 1994. [7] A. Silberschatz, J. Peterson, and P. Galvin, Operating System Concepts, Third Edition, Addison-Wesley Publishing Company 1991. [8] Bryan Flamig, Practical Data Structures in C++, John Wiley & Sons, Inc., 1993. [9] C. Krishna, and K. Shin, Real-Time Systems, McGraw-Hill 1997. [10] F. Flckiger, Understanding Networked Multimedia: Applications and Technology, Prentice Hall 1995. [11] S. Dixit, and P. Skelly, "MPEG-2 over ATM for Video Dial Tone Networks: Issues and Strategies", IEEE Network, October 1995. [12] D. Gemmll, H. Vin, D. Kandlur, P. Rangan, and L. Rowe, "Multimedia Storage Servers: A Tutorial", IEEE Computer, May 1995. [13] A. Chervenak, “Performance Measurements of the First RAID Prototype”, M.S. thesis, University of California at Berkeley, 1990. [14] G. Ganger, B. Worthington, R. Hou, and Y. Patt, "Disk Arrays: High- Performance, High-Reliability Storage Subsystems", IEEE Computer, March 1994. 99 [15] C. Ruemmler, and J. Wilkes, "An Introduction to Disk Drive Modeling", IEEE Computer, March 1994. [16] J. Watkinson, Compression in Video & Audio, Focal Press, 1995. [17] V. Subrahmanian, and S. Jajodia, Multimedia Database Systems, Issues and Research Directions, Springer, 1996. [18] A. Law, and W. Kelton, Simulation Modeling and Analysis, Second Edition, McGraw-Hill 1991. [19] P. Cao, E. Felten, A. Karlin, and K. Li, “Implementation and Performance of Integrated Application-Controlled File Caching, Prefetching and Disk Scheduling”, ACM Transactions on Computer Systems, November 1996 [20] B. Ozden, R. Rastogi, P. Shenoy, and A. Silberschatz, "Fault-Tolerant Architecture for Continuous Media Servers", ACM SIGMOD 1996. [21] W. Feng, F. Jahanian, S. Sechrest, “An Optimal Bandwidth Allocation Strategy For The Delivery Of Compressed Prerecorded Video”, Multimedia Systems, Springer-Verlag 1997. [22] K. Kalpio, and J. Salminen "Media Server for Multimedia Database System Case: Video-on-Demand", Presented in the "Fundamentals and Trends in Multimedia Databases" seminar in Sjkulla, Finland, November 1996. |
RAID data recovery, Mac data recovery, Unix data recovery, Linux data recovery, Oracle data recovery, CD data recovery, Zip data recovery, DVD data recovery , Flash data recovery, Laptop data recovery, PDA data recovery, Ipaq data recovery, Maxtor HDD, Hitachi HDD, Fujitsi HDD, Seagate HDD,
Hewlett-Packard HDD, HP HDD, IBM HDD, MP3 data recovery, DVD data recovery, CD-RW data recovery, DAT data recovery, Smartmedia data recovery, Network data recovery, Lost data recovery, Back-up expert data recovery, Tape data recovery, NTFS data recovery, FAT 16 data recovery, FAT 32 data recovery, Novell data recovery, Recovery tool data recovery, Compact flash data recovery, Hard drive data recovery, IDE data recovery, SCSI data recovery, Deskstar data recovery, Maxtor data recovery, Fujitsu HDD data recovery, Samsung data recovery, IBM data recovery, Seagate data recovery, Hitachi data recovery, Western Digital data recovery, Quantum data recovery, Microdrives data recovery, Easy Recovery, Recover deleted data , Data Recovery, Data Recovery Software, Undelete data, Recover, Recovery, Restore data, Unerase deleted data, unformat, Deleted, Data Destorer, fat recovery, Data, Recovery Software, File recovery, Drive Recovery, Recovery Disk , Easy data recovery, Partition recovery, Data Recovery Program, File Recovery, Disaster Recovery, Undelete File, Hard Disk Rrecovery, Win95 Data Recovery, Win98 Data Recovery, WinME data recovery, WinNT 4.x data recovery, WinXP data recovery, Windows2000 data recovery, System Utilities data recovery, File data recovery, Disk Management recovery, BitMart 2000 data recovery, Hard Drive Data Recovery, CompactFlash I, CompactFlash II, CF Compact Flash Type I Card,CF Compact Flash Type II Card, MD Micro Drive Card, XD Picture Card, SM Smart Media Card, MMC I Multi Media Type I Card, MMC II Multi Media Type II Card, RS-MMC Reduced Size Multi Media Card, SD Secure Digital Card, Mini SD Mini Secure Digital Card, TFlash T-Flash Card, MS Memory Stick Card, MS DUO Memory Stick Duo Card, MS PRO Memory Stick PRO Card, MS PRO DUO Memory Stick PRO Duo Card, MS Memory Stick Card MagicGate, MS DUO Memory Stick Duo Card MagicGate, MS PRO Memory Stick PRO Card MagicGate, MS PRO DUO Memory Stick PRO Duo Card MagicGate, MicroDrive Card and TFlash Memory Cards, Digital Camera Memory Card, RS-MMC, ATAPI Drive, JVC JY-HD10U, Secured Data Deletion, IT Security Firewall & Antiviruses, PocketPC Recocery, System File Recovery , RAID