Search

While data deduplication is an important data compression technique that removes copies of repeated data to enhance storage utilization, security and privacy risks arise since sensitive or delicate user data are at risk to both insider and outsider attacks. A distinct negative factor to performance of the technique is data fragmentation, which not only slows down the restoration process but also leads to massive power consumption. In this paper, we address this problem from the perspective of data layout. The kernel point of our method is a novel RAID-5-based cross grouping data layout (CGDL). We introduce a selective deduplication algorithm (SDD) to perform data replication and restoration. A new CGDL-based disk scheduling algorithm (LDP) is also proposed that predicts location dependence to save energy by eliminating the redundant disk read/write operations. We evaluate our new method on the Linux MD (multiple device) driver modules. The experiments show that, under a 10 disks 3 groups storage configuration, our method drastically (by 20%) improves restoration efficiency with only 7.6% reduction on the deduplication ratio, while reducing 23% power consumption.

Storage reliability of massive amounts of data is the basis for deep learning, and continuous data protection (CDP) technology is an effective means of ensuring it. The method of storing CDP historical data, represented by TRAP-Array parity logs, effectively reduces the overheads of storage capacity, but it increases the risk of historical data loss due to the absence of the RAID protection mechanism for the parity data. This paper proposes a design method for a fault-tolerant and energy-efficient continuous data protection system (FTEECDP), which is composed of SSD mirror array, TRAP parity generation logic and S-RAID disk array. Taking the SSD mirror array as the source data volume of the system to provide the I/O service of the upper applications, FTEECDP improves the throughput of the system. This method also takes S-RAID as the CDP log volume to store the TRAP parity logs. When the disk data error occurs, the error data will be recovered from the data redundancy information of S-RAID, thus protecting the TRAP parity chain from being destroyed and improving the reliability of the TRAP parity logs. The experiment shows that in the continuous data protection system, the CDP logs stored as the TRAP parity can greatly reduce the storage space overheads and reduce the system energy consumption. In addition, with the disk scheduling algorithm, S-RAID shifts the disk grouping without any data requests into a standby state, thus further reducing the energy consumption of the system.

Modern data centers usually use virtual machine technology to host various big data applications in a single physical machine, not only enhancing the server utilization, but also providing them with the hardware-level isolation. However, in a typical virtualized environment an extra software layer called virtual machine monitor (VMM) is often interposed between the hardware resource and guest operating system (virtual machine, VM), shielding the specific user-process semantic inside a running VM. As a result, it obstructs the disk I/O scheduler of VMM to acquire the accurate information of a user-process (often a big data application), and thus proposes a challenge on the I/O request scheduling as well as the disk resource management at the granularity of VM user-process. Eventually, the disk I/O performance of a virtualized system is sub-optimal. This paper introduces an improved disk I/O scheduling framework for the virtualized system. It aims at bridging the semantic gap between physical disk I/O scheduler and VM user-process, providing a fair sharing of disk I/O resource among concurrent VMs. At the same time, it improves the overall disk I/O performance through a novel method for creating the image file of VM. Besides, an extra scheduling algorithm is proposed to further refine the storage performance. Finally, we implement these improvements on Xen hypervisor and conduct extensive experiments to verify our framework. The experimental result shows that our work improve the performance of read-intensive, write-intensive and mixed workloads up to 9, 10.7 and 20% respectively.

This paper presents a new scheme of I/O scheduling on storage servers of distributed/parallel file systems, for yielding better I/O performance. To this end, we first analyze read/write requests in the I/O queue of storage server (we name them block I/Os), by using our proposed technique of horizontal partition. Then, all block requests are supposed to be divided into multiple groups, on the basis of their offsets. This is to say, all requests related to the same chunk file will be grouped together, and then be satisfied within the same time slot between opening and closing the target chunk file on the storage server. As a result, the time resulted by completing block I/O requests can be significantly decreased, because of less file operations on the corresponding chunk files at the low-level file systems of server machines. Furthermore, we introduce an algorithm to rate a priority for each group of block I/O requests, and then the storage server dispatches groups of I/Os by following the priority order. Consequently, the applications having higher I/O priorities, e.g. they have less I/O operations and small size of involved data, can finish at a earlier time. We implement a prototype of this server-side scheduling in the PARTE file system, to demonstrate the feasibility and applicability of the proposed scheme. Experimental results show that the newly proposed scheme can achieve better I/O bandwidth and less I/O time, compared with the strategy of First Come First Served, as well as other server-side I/O scheduling approaches.

As the computing power of high-performance computing (HPC) systems is developing to exascale, the storage systems are stretched to their limits to process the growing I/O traffic. Researchers are building storage systems on top of compute node-local fast storage devices (such as NVMe SSD) to alleviate the I/O bottleneck. However, user jobs have varying requirements of I/O bandwidth; therefore, it is a serious waste of expensive storage devices to have them on all compute nodes and build them into a global storage system. In addition, current node-local storage systems need to cope with the challenging small I/O and rank 0 I/O pattern from HPC workloads. In this paper, we presented a workload-aware temporary cache (WatCache) to meet above challenges. We designed a workload-aware node allocation method to allocate fast storage devices to jobs according to their I/O requirements and merged the devices of the jobs into separate temporary cache spaces. We implemented a metadata caching strategy that reduces the metadata overhead of I/O requests to improve the performance of small I/O. We designed a data layout strategy that distributes consecutive data that exceeds a threshold to multiple devices to achieve higher aggregate bandwidth for rank 0 I/O. Through extensive tests with several I/O benchmarks and applications, we have validated that WatCache offers linearly scalable performance, and brings significant performance promotions to small I/O and rank 0 I/O patterns.

This paper addresses the problem of scheduling n jobs on a single machine and on m identical parallel machines to minimize the completion time variance of jobs. This problem of scheduling jobs on parallel machines is motivated by a case study in an automobile ancillary unit. First, a heuristic to solve the single-machine scheduling problem is proposed. The parallel-machine scheduling problem is solved in two phases: job-allocation phase and job-sequencing phase. Two heuristics are proposed in the job-allocation phase, whereas in the job-scheduling phase, the single-machine scheduling approach is used. In this paper, both versions of parallel-machine scheduling problem (restricted and unrestricted) are considered. A good upper bound is obtained using a genetic algorithm, to evaluate the performance of the proposed heuristics for the parallel-machine scheduling problem. An extensive computation evaluation of the proposed heuristics is presented for both single-machine scheduling problem and the parallel-machine scheduling problem (especially considering the case study), along with the comparison of performances with the existing heuristics in the literature.

Lately, fast storage devices are rapidly increasing in social network services, cloud platforms, etc. Unfortunately, the traditional Linux I/O stack is designed to maximize performance on disk-based storage. Emerging byte-addressable and low-latency non-volatile memory technologies (e.g., phase-change memories, MRAMs, and the memristor) provide very different characteristics, so the disk-based I/O stack cannot lead to high performance. This paper presents a high performance I/O stack for the fast storage devices. Our scheme is to remove the concept of block and to simplify the whole I/O path and software stack, which results in only two layers that are the byte-capable interface and the byte-aware file system called BAFS. We aim to minimize I/O latency and maximize bandwidth by eliminating the unnecessary layers and supporting byte-addressable I/O without requiring changes to applications. We have implemented a prototype and evaluated its performance with multiple benchmarks. The experimental results show that our I/O stack achieves 6.2 times on average and up to 17.5 times performance gains compared to the existing Linux I/O stack.

In Parallel File Systems (PFSs), a data file I/O request may be divided into multiple I/O sub-requests across the storage system. The latency of the original I/O request depends on the finish time of the last sub-request. Due to application multiplexing and various file data layouts employed in PFS, data servers may have very different workloads. Thus, the performance penalty caused by the finish time of different sub-requests can be significant. The Dispatch Time Aligning (DTA) I/O scheduling algorithm focuses on improving system throughput by prioritizing lagged sub-requests in PFS I/O requests. The DTA algorithm associates sub-requests from the same I/O request, detects and prioritizes the lagged-behind sub-requests. The dual-queue scheduling scheme in DTA provides I/O request latency control while improving system throughput. Simulation results show that the DTA algorithm can provide up to 83 % higher total system throughput than the Earliest Deadline First algorithm, while offering similar latency guarantees.

The performance gap between compute and storage is fairly considerable. This results in a mismatch between the application needs from storage and what storage can deliver. The full potential of storage devices cannot be harnessed till all layers of I/O hierarchy function efficiently. Despite advanced optimizations applied across various layers along the odyssey of data access, the I/O stack still remains volatile. The problems associated due to the inefficiencies in data management get amplified in Big Data shared resource environments. The Linux OS (host) block layer is the most critical part of the I/O hierarchy, as it orchestrates the I/O requests from different applications to the underlying storage. Unfortunately, despite it’s significance, the block layer, essentially the block I/O scheduler, hasn’t evolved to meet the needs of Big Data. We have designed and developed two contention avoidance storage solutions, collectively known as “BID: Bulk I/O Dispatch” in the Linux block layer specifically to suit multi-tenant, multi-tasking shared Big Data environments. Hard disk drives (HDDs) form the backbone of data center storage. The data access time in HDDs is majorly governed by disk arm movements, which usually occurs when data is not accessed sequentially. Big Data applications exhibit evident sequentiality but due to the contentions amongst other I/O submitting applications, the I/O accesses get multiplexed which leads to higher disk arm movements. BID schemes aim to exploit the inherent I/O sequentiality of Big Data applications to improve the overall I/O completion time by reducing the avoidable disk arm movements. In the first part, we propose a dynamically adaptable block I/O scheduling scheme BID-HDD for disk based storage. BID-HDD tries to recreate the sequentiality in I/O access in order to provide performance isolation to each I/O submitting process. Through trace driven simulation based experiments with cloud emulating MapReduce benchmarks, we show the effectiveness of BID-HDD which results in 28–52% lesser time for all I/O requests than the best performing Linux disk schedulers. In the second part, we propose a hybrid scheme BID-Hybrid to exploit SCM’s (SSDs) superior random performance to further avoid contentions at disk based storage. BID-Hybrid is able to efficiently offload non-bulky interruptions from HDD request queue to SSD queue using BID-HDD for disk request processing and multi-q FIFO architecture for SSD. This results in performance gain of 6–23% for MapReduce workloads when compared to BID-HDD and 33–54% over best performing Linux scheduling scheme. BID schemes as a whole is aimed to avoid contentions for disk based storage I/Os following system constraints without compromising SLAs.

Transaction processing performance council benchmark C (TPC-C) is the de facto standard for evaluating the performance of high-end computers running on-line transaction processing applications. Differing from other standard benchmarks, the transaction processing performance council only defines specifications for the TPC-C benchmark, but does not provide any standard implementation for end-users. Due to the complexity of the TPC-C workload, it is a challenging task to obtain optimal performance for TPC-C evaluation on a large-scale high-end computer. In this paper, we designed and implemented a large-scale TPC-C evaluation system based on the latest TPC-C specification using solid-state drive (SSD) storage devices. By analyzing the characteristics of the TPC-C workload, we propose a series of system-level optimization methods to improve the TPC-C performance. First, we propose an approach based on SmallFile table space to organize the test data in a round-robin method on all of the disk array partitions; this can make full use of the underlying disk arrays. Second, we propose using a NOOP-based disk scheduling algorithm to reduce the utilization rate of processors and improve the average input/output service time. Third, to improve the system translation lookaside buffer hit rate and reduce the processor overhead, we take advantage of the huge page technique to manage a large amount of memory resources. Lastly, we propose a locality-aware interrupt mapping strategy based on the asymmetry characteristic of non-uniform memory access systems to improve the system performance. Using these optimization methods, we performed the TPC-C test on two large-scale high-end computers using SSD arrays. The experimental results show that our methods can effectively improve the TPC-C performance. For example, the performance of the TPC-C test on an Intel Westmere server reached 1.018 million transactions per minute.

Providing differentiated service in a consolidated storage environment is a challenging task. To address this problem, we introduce FAIRIO, a cycle-based I/O scheduling algorithm that provides differentiated service to workloads concurrently accessing a consolidated RAID storage system. FAIRIO enforces proportional sharing of I/O service through fair scheduling of disk time. During each cycle of the algorithm, I/O requests are scheduled according to workload weights and disk-time utilization history. Experiments, which were driven by the I/O request streams of real and synthetic I/O benchmarks and run on a modified version of DiskSim, provide evidence of FAIRIO's effectiveness and demonstrate that fair scheduling of disk time is key to achieving differentiated service in a RAID storage system. In particular, the experimental results show that, for a broad range of workload request types, sizes, and access characteristics, the algorithm provides differentiated storage throughput that is within 10% of being perfectly proportional to workload weights; and, it achieves this with little or no degradation of aggregate throughput. The core design concepts of FAIRIO, including service-time allocation and history-driven compensation, potentially can be used to design I/O scheduling algorithms that provide workloads with differentiated service in storage systems comprised of RAIDs, multiple RAIDs, SANs, and hypervisors for Clouds.

As the number of nodes in high performance computing (HPC) systems increases, collective I/O becomes an important issue and I/O aggregators are the key factors in improving the performance of collective I/O. When an HPC system uses non-exclusive scheduling, a different number of CPU cores per node can be assigned for MPI jobs; thus, I/O aggregators experience a disparity in their workloads and communication costs. Because the communication behaviors are influenced by the sequence of the I/O aggregators and by the number of CPU cores in neighbor nodes, changing the order of the nodes affects the communication costs in collective I/O. There are few studies, however, that seek to incorporate steps to adequately determine the node sequence. In this study, it was found that an inappropriate order of nodes results in an increase in the collective I/O communication costs. In order to address this problem, we propose the use of specific heuristic methods to regulate the node sequence. We also develop a prediction function in order to estimate the MPI-IO performance when using the proposed heuristic functions. The performance measurements indicated that the proposed scheme achieved its goal of preventing the performance degradation of the collective I/O process. For instance, in a multi-core cluster system with the Lustre file system, the read bandwidth of MPI-Tile-IO was improved by 7.61% to 17.21% and the write bandwidth of the benchmark was also increased by 17.05% to 26.49%.

Disk management is an increasingly important aspect of operating systems research and development because it has great effect on system performance. As the gap between processor and disk performance continues to increase in modern systems, access to mass storage is a common bottleneck that ultimately limits overall system performance. In this paper, we propose hardware architecture of a new genetic based real-time disk scheduling method. Also, to have a precise simulation, a neural network is proposed to simulate seek-time of disks. Simulation results showed the hardware implementation of proposed algorithm outperformed software implementation in term of execution time, and other related works in terms of number of tasks that miss deadlines and average seeks.

A new scheduling model in which both two-agent and position-dependent processing times exist simultaneously is considered in this paper. Two agents compete to perform their respective jobs on a common single machine, and each agent has his own criterion to optimize. The job position-dependent processing time is characterized by increasing or decreasing function dependent on the position of a job in the sequence. We introduce an aging effect and a learning effect into the two-agent single-machine scheduling, where the objective is to minimize the total completion time of the first agent with the restriction that the maximum cost of the second agent cannot exceed a given upper bound. We propose the optimal properties for the considered scheduling problems and then present the optimal polynomial time algorithms to solve the two scheduling problems, respectively.

In this work, we develop energy-aware disk scheduling algorithm for soft real-time I/O. Energy consumption is one of the major factors which bar the adoption of hard disk in mobile environment. Heat dissipation of large scale storage system also calls for an energy-aware scheduling technique to further increase the storage density. The basic idea in this work is to properly determine the I/O burst size so that device can be in standby mode between consecutive I/O bursts and that it can satisfy the soft real-time requirement. We develop an elaborate model which incorporates the energy consumption characteristics, overhead of mode transition in determining the appropriate I/O burst size and the respective disk operating schedule. Efficacy of energy-aware disk scheduling algorithm greatly relies on not only disk scheduling algorithm itself but also various operating system and device firmware related concerns. It is crucial that the various operating system level and device level features need to be properly addressed within disk scheduling framework. Our energy-aware disk scheduling algorithm successfully addresses a number of outstanding issues. First, we examine the effect of OS and hard disk firmware level prefetch policy and incorporate its effect in our disk scheduling framework. Second, our energy aware scheduling framework can allocate a certain fraction of disk bandwidth to handle sporadically arriving non real-time I/O's. Third, we examine the relationship between lock granularity of the buffer management and energy consumption. We develop a prototype software with energy-aware scheduling algorithm. In our experiment, proposed algorithm can reduce the energy consumption to one fourth if we use energy-aware disk scheduling algorithm. However, energy-aware disk scheduling algorithm increases buffer requirement significantly, e.g., from 4 to 140 KByte. We carefully argue that the buffer overhead is still justifiable given the cost of DRAM chip and importance of energy management in modern mobile devices. The result of our work not only provides the energy efficient scheduling algorithm but also provides an important guideline in capacity planning of future energy efficient mobile devices.

We consider the problem of estimating the average tour length of the asymmetric TSP arising from the disk scheduling problem with a linear seek function and a probability distribution on the location of I/O requests. We provide a law of large numbers expression, for the expected tour size and compute it explicitely in the most interesting cases. We also provide finer asymptotic estimates in the case of a uniform request distribution. Our methods relate disk scheduling to the problem of finding the longest increasing subsequence in a permutation. Our tour length estimates also answer questions on the asymptotics of the connect-the dots problem with Lipschitz functions which was raised in Adv. Appl. Probab. 37, 571–603 (2005). In the last section we show that all the above problems can be interpreted naturally, in terms of Lorentzian geometry. We generalize the main results to this setting.

Reward-based scheduling has been investigated for flexible applications in which an approximate but timely result is acceptable. Meanwhile, significant research efforts have been made on voltage scheduling which exploits the tradeoff between the processor speed and the energy consumption. In this paper, we address the combined scheduling problem of maximizing the total reward of hard real-time systems with a given energy budget. We present an optimal off-line algorithm and an efficient on-line algorithm for jobs with their own release-times/deadlines under Earliest-Deadline-First (EDF) scheduling. Experimental results show that the solution computed by the on-line algorithm is no more than 14% worse than the theoretical optimal solution obtained by the optimal off-line algorithm.

This paper addresses the 2-cyclic identical part scheduling in a no-wait robotic flowshop where exactly two parts enter and two parts leave the production line during each cycle. This problem was previously proved to be polynomially solvable in O(N8log N) time, where N is the number of tanks in the production line. This paper proposes an improved algorithm with reduced complexity O(N5log N).

Disk mirroring or RAID level 1 stores the same data twice, on two independent disks, to ensure that all single disk failures can be tolerated. This high storage overhead is acceptable in view of the drop in storage cost per gigabyte and rapidly increasing disk capacities. Disk access time, on the other hand, is improving at a very slow pace, so that another important advantage of disk mirroring is the doubling of the disk access bandwidth in processing read requests. Efficient routing of read requests to disks and local disk scheduling can be used to improve performance even further. We are primarily concerned with two RAID1 configurations: (i) source-initiated routing with the independent queues--IQ method; (ii) destination-initiated routing with the shared queue--SQ method. Static, dynamic, and affinity-based (AB) routing methods are used to distribute requests with the IQ method. We compare the performance of various IQ and SQ based routing policies using a random number-driven simulation. While there is some improvement in performance with the more sophisticated routing policies, performance is dominated by the local disk scheduling policy. The SQ method allows resource sharing, so that it tends to outperform the IQ based routing, but it requires the scheduler to keep track of the state of the disk drives. As a further means to improve performance, we consider the effect of prioritizing reads with respect to writes, transposed data allocation, and replicating data more than twice.

We put forward an optimal disk schedule withn disk requests and prove its optimality mathematically. Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first (SPFF). This algorithm is based on the shortes path of disk head motion constructed by all the pendent requests. From view of the head-moving distance, it has the stronger globality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system’s different demands.

Mirrored disks or RAID1 is a popular disk array paradigm, which in addition to fault-tolerance, doubles the data access bandwidth. This is important in view of rapidly increasing disk capacities and the slow improvement in disk access time. Caching of dirty data blocks in a non-volatile storage (NVS) cache allows the destaging of dirty blocks to be deferrable, so as to improve the response time of read requests by giving them a higher priority than write requests. Destaging of dirty blocks in batches to take advantage of disk geometry entails in lowered disk utilization due to writes and improved performance for reads. Polyzois et al. [12] propose a scheduling policy for mirrored disks equipped with an NVS cache, so that one disk processes read requests, while the other disk is processing a write batch according to the CSCAN policy. We propose an improved scheduling policy as follows: (i) eliminating the forced idleness caused by the batch processing paradigm for write requests, i.e., allowing write requests to be processed individually; (ii) using SATF or even an exhaustive search, to reduce destaging time compared to CSCAN; (iii) introducing a threshold for the number of read requests, which when exceeded defers the destaging of dirty blocks. We compare these two scheduling policies with each other and also against prioritizing the processing of reads versus writes: (i) the head-of-the-line (HOL) priority queueing discipline, (ii) SATF with conditional priorities. It follows from simulation results that the new method outperforms Polyzois' method, which is even outperformed by the HOL priority policy. SATF with conditional priorities slightly outperforms the proposed method from the viewpoint of its throughput and response time, but is susceptible to more variability in response time.

We propose a network-attached storage system that can support guaranteed Quality of Service (QoS), called POPNet Storage. The special policy of date access and disk scheduling is enable users to access files quickly and directly with guaranteed QoS in the POPNet Storage. The POPNet Storage implements a measurement-based admission control algorithm (PSMBAC) to determine whether to admit a new data access request stream and admit as many requests as possible while meeting the QoS guarantees to its clients. The data reconstruction algorithms in the POPNet Storage also put more emphasis on data availability and guaranteed QoS, thus it is designed to complete the data recovery as soon as possible and at the same time provide the guaranteed QoS for high-priority data access. The experiment results show that the POP-Net Storage can provide more significant performance, reliability, and guaranteed QoS than conventional storage systems.

APEX is an adaptive disk scheduling framework with Quality-of-Service (QoS) support designed for environments with highly varying disk bandwidth usage. APEX is based on a three-layer scheduling architecture: (1) the upper layer realizes different service classes using a set of queues; (2) the mid-layer distributes available disk bandwidth among these queues; and (3) the lower layer is handled by the disk itself, which does the final ordering of disk requests. We demonstrate the use of APEX in an example scenario, a Learning-on-Demand (LoD) application supported by a multimedia system, where students can search for and playback multimedia-based learning material. In this paper, we present the scheduling concepts of APEX which are based on an extended token bucket algorithm. The disk requests scheduled for service are assembled into batches in order to exploit the intelligence of modern disks. Combined with a specialized work-conservation scheme, this enables APEX to apply bandwidth where it is needed, without the loss of efficiency. We demonstrate, through simulations, that APEX provides both higher throughput and lower response times than other mixed-media disk schedulers while still avoiding deadline violations for real-time requests. We also show its robustness with respect to misaligned bandwidth allocation.

Multimedia presentations (e.g., lectures, digital libraries) normally include discrete media objects such as text and images along with continuous media objects such as video and audio. Objects composing a multimedia presentation need to be delivered based on the temporal relationships specified by the author(s). Hence, even discrete media objects (that do not normally have any real-time characteristics) have temporal constraints on their presentations. Composition of multimedia presentations may be light (without any accompanying video or large multimedia data) or heavy (accompanied by video for the entire presentation duration). The varying nature of the composition of multimedia presentations provides some flexibility for scheduling their retrieval. In this paper, we present a min-max skip round disk scheduling strategy that can admit multimedia presentations in a flexible manner depending on their composition. We also outline strategies for storage of multimedia presentations on an array of disks as well as on multi-zone recording disks.

We study on-line scheduling on a batch machine with infinite capacity. We present a flexible on-line scheduling algorithm that aims at minimizing the makespan and achieves the optimal competitive ratio of $(1+\sqrt{5})/2$ .

Without any additional cost, all the disks on the nodes of a cluster can be connected together through CEFT-PVFS, an RAID-10 style parallel file system, to provide a multi-GB/s parallel I/O performance. I/O response time is one of the most important measures of quality of service for a client. When multiple clients submit data-intensive jobs at the same time, the response time experienced by the user is an indicator of the power of the cluster. In this paper, a queuing model is used to analyze in detail the average response time when multiple clients access CEFT-PVFS. The results reveal that response time is with a function of several operational parameters. The results show that I/O response time decreases with the increases in I/O buffer hit rate for read requests, write buffer size for write requests and the number of server nodes in the parallel file system, while the higher the I/O requests arrival rate, the longer the I/O response time. On the other hand, the collective power of a large cluster supported by CEFT-PVFS is shown to be able to sustain a steady and stable I/O response time for a relatively large range of the request arrival rate.

A multimedia file system supports diverse application classes that access data with heterogeneous characteristics. In this paper, we describe our experiences in the design and implementation of the Symphony multimedia file system. We first discuss various methodologies for designing multimedia file systems and examine their trade-offs. We examine the design requirements for such file systems and argue that to efficiently manage the heterogeneity in application requirements and data characteristics, a multimedia file system should enable the coexistence of multiple data-type-specific and application-specific techniques. We describe the architecture and novel features of Symphony and then demonstrate their efficacy through an experimental evaluation. Our results show that Symphony yields a factor of 1.9 improvement in text response time over conventional disk scheduling algorithms while continuing to meet the real-time requirements of video clients. Finally, we reflect upon the lessons learned from the Symphony project.

The ever growing needs of large multimedia systems cannot be met by magnetic disks due to their high cost and low storage density. Consequently, cheaper and denser tertiary storage systems are being integrated into the storage hierarchies of these applications. Although tertiary storage is cheaper, the access latency is very high due to the need to load and unload media on the drives. This high latency and the bursty nature of I/O traffic result in the accumulation of I/O requests for tertiary storage. We study the problem of scheduling these requests to improve performance. In particular we address the issues of scheduling across multiple tapes or disks as opposed to most other studies which consider only one or two media. We focus on algorithms that minimize the number of switches and show through simulation that these result in near-optimal schedules. For single drive libraries an efficient algorithm that produces optimal schedules is developed. For multiple drives the problem is shown to be NP-Complete. Efficient and effective heuristics are presented for both single and multiple drives. The scheduling policies developed achieve significant performance gains over naive policies. The algorithms are simple to implement and are not restrictive. The study encompasses all types of storage libraries handling removable media, such as tapes and optical disks.

Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees.

In this paper, we present the Cello disk scheduling framework for meeting the diverse service requirements of applications. Cello employs a two-level disk scheduling architecture, consisting of a class-independent scheduler and a set of class-specific schedulers. The two levels of the framework allocate disk bandwidth at two time-scales: the class-independent scheduler governs the coarse-grain allocation of bandwidth to application classes, while the class-specific schedulers control the fine-grain interleaving of requests. The two levels of the architecture separate application-independent mechanisms from application-specific scheduling policies, and thereby facilitate the co-existence of multiple class-specific schedulers. We demonstrate that Cello is suitable for next generation operating systems since: (i) it aligns the service provided with the application requirements, (ii) it protects application classes from one another, (iii) it is work-conserving and can adapt to changes in work-load, (iv) it minimizes the seek time and rotational latency overhead incurred during access, and (v) it is computationally efficient.

In the past, much emphasis has been given to the data throughput of VOD servers. In Interactive Video-on-Demand (IVOD) applications, such as digital libraries, service availability and response times are more visible to the user than the underlying data throughput. Data throughput is a measure of how efficiently resources are utilized. Higher throughput may be achieved at the expense of deteriorated user-perceived performance metrics such as probability of admission and queuing delay prior to admission. In this paper, we propose and evaluate a number of strategies to sequence the admission of pending video requests. Under different request arrival rates and buffer capacities, we measure the probability of admission, queueing delay and data throughput of each strategy. Results of our experiments show that simple hybrid strategies can improve the number of admitted requests and reduce the queuing time, without jeopardizing the data throughput. The techniques we propose are independent of the underlying disk scheduling techniques used. So, they can be employed to improve the user-perceived performance of VOD servers, in general.

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(Nlog F) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N F /F F−2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.

Excessive buffer requirement to handle continuous-media playbacks is an impediment to cost- effective provisioning for on-line video retrieval. Given the skewed distribution of video popularity, it is expected that often there are concurrent playbacks of the same video file within a short time interval. This creates an opportunity to batch multiple requests and to service them with a single stream from the disk without violating the on-demand constraint. However, there is a need to keep data in memory between successive uses to do this. This leads to a buffer space trade-off between servicing a request in memory mode vs. servicing it in disk-mode. In this work, we develop a novel algorithm to minimize the buffer requirement to support a set of concurrent playbacks. One of the beauties of the proposed scheme is that it enables the server to dynamically adapt to the changing workload while minimizing the total buffer space requirement. Our algorithm makes a significant contribution in decreasing the total buffer requirement, especially when the user access pattern is biased in favor of a small set of files. The idea of the proposed scheme is modeled in detail using an analytical formulation, and optimality of the algorithm is proved. An analytical framework is developed so that the proposed scheme can be used in combination with various existing disk-scheduling strategies. Our simulation results confirm that under certain circumstances, it is much more resource efficient to support some of the playbacks in memory mode and subsequently the proposed scheme enables the server to minimize the overall buffer space requirement.

Real-time disk scheduling (RTDS) is important for time-critical multimedia applications. In conventional approaches of real-time disk scheduling, such as SCAN-EDF, the seek-optimizing SCAN scheme is applied to reduce the disk service time of the real-time EDF schedule. Since only tasks with the same deadline are seek-optimized, the obtained improvement of SCAN-EDF is limited. In this paper, based on the maximum-scannable-group (MSG) concept, a deadline-modification-scan (DMS or DM-SCAN) algorithm is proposed. Our algorithm uses MSG to automatically decide the suitable task groups for seek-optimizing. Based on the MSG concept, we repeatedly apply DMS to further increase disk throughput to support more tasks. We have implemented the proposed algorithm on UnixWare 2.01. The appropriate problem behaviors and parameter values to yield good solutions are investigated. Experiments show that DMS is better than conventional approaches in both the obtained disk throughput and the supported tasks. Moreover, our proposed approach can schedule task sets that are not schedulable by EDF and SCAN-EDF.

In this paper, we address the problem of providing different levels of performance guarantees or quality ofservice for disk I/O. We classify disk requests into threecategories based on the provided level of service. We propose an integrated scheme that provides different levels ofperformance guarantees in a single system. We propose andevaluate a mechanism for providing deterministic servicefor variable-bit-rate streams at the disk. We will show that,through proper admission control and bandwidth allocation,requests in different categories can be ensured of performance guarantees without getting impacted by requests inother categories. We evaluate the impact of scheduling policy decisions on the provided service. We also quantify theimprovements in stream throughput possible by using statistical guarantees instead of deterministic guarantees in thecontext of the proposed approach.

In contrast to pure video servers, advanced multimedia applications such as digital libraries or teleteaching exhibit a mixed workload with massive access to conventional, “discrete” data such as text documents, images and indexes as well as requests for “continuous data”, like video and audio data. In addition to the service quality guarantees for continuous data requests, quality-conscious applications require that the response time of the discrete data requests stay below some user-tolerance threshold. In this paper, we study the impact of different disk scheduling policies on the service quality for both continuous and discrete data. We provide a framework for describing various policies in terms of few parameters, and we develop a novel policy that is experimentally shown to outperform all other policies.

This paper presents the design and analysis of two scheduling algorithms for a reservation-based medium access control (MAC) protocol for wavelength division multiplexed (WDM) multi-channel optical networks. The network architecture is based on a passive star topology with one tunable transmitter and receiver (TT-TR) per node. The main objective of scheduling algorithm design is to reduce the computation time while maximizing the utilization of the network resources. In this paper, we propose two scheduling schemes called SEQSAM (SEQuential Scheduling AlgorithM) and BALSAM (BALanced Scheduling AlgorithM). Let M denote the number of nodes, C the number of channels, and K the maximum number of packets transmitted by one node to another. SEQSAM uses the M × M traffic demand matrix--obtained during the reservation phase of the MAC protocol--to compute a collision-free schedule for the nodes of the network. BALSAM uses the modified MULTI-FIT algorithm (MMFT) [1] to convert the M × M matrix into a corresponding M × C matrix, which is input to the IBS (Interval Based Scheduling) algorithm [2] that schedules the requests of the nodes. The overall time complexity of SEQSAM is O(M3) compared to BALSAM algorithm's time complexity of O(M2CK + M2 + MlogM). Note that the lower bound for any scheduling algorithm operating on a M × M matrix is O(M2). A simulation-based performance study that considers network utilization, computation time, tuning latency, average packet latency and throughput for 1.2 Gbps and 2.4 Gbps data streams is presented.

Video-on-demand (VOD) servers need to be efficiently designed in order to support a large number of users viewing the same or different videos at different rates. While considering a disk-array based VOD server, use of a shared buffer at the server end may be more economical than the sole use of dedicated buffers at each user’s end. In this paper, we propose a simple buffer sharing architecture that may be used when disk-array based video servers are used. Our aim is to support the maximum number of users for a given number of video server disks while employing a simple scheme requiring less buffer space. The number of video segment retrievals that can occur within a certain time (the service round) is maximum when the scan disk scheduling algorithm is used. Consequently, we shall assume use of the scan algorithm for disk retrieval. The VOD server has a buffer manager that directs retrieved segments to appropriate buffer locations depending on their release and deadlines. The release and deadlines of segments are such that buffer requirement at the user’s set-top box is minimized to two video segments while avoiding video starvation and buffer overflow at the user’s end. We propose a novel scheme for the operation of the shared buffer that aims at increasing buffer utilization and decreasing cell loss due to buffer overflow. An ATM based broadband network is assumed and all segments are stored in buffers as fixed length ATM cells. We also use a novel scheme for grouping frames into segments and illustrate its advantages over earlier ones.

In this paper we study three popular on-line disk scheduling algorithms, FCFS, SSTF, and LOOK, using competitive analysis. Our results show that, in a competitive sense, the performance of LOOK is better than those of SSTF and FCFS. As a by-product, our analysis also reveals quantitatively the role played by the size of the window, which in our model is a waiting buffer that holds a fixed number of requests waiting to be serviced next. The window, in some sense, offers the lookahead ability which is mentioned in several on-line problems.

We present a producer-consumer model of multimedia-on-demand (MOD) servers. The producer retrieves media data from a disk and places it into a set of buffers, while the consumer sends out the data in the buffers to the users. We develop for the producer a buffer-inventory-based dynamic scheduling (BIDS) algorithm that guarantees non-zero inventory and non-overflow of data in the buffers to meet the continuity requirement and no-loss of data for each media stream. The algorithm can deal with heterogeneous me dia streams as well as the transient circumstances upon service completions and arrivals of new requests. To smooth out the impact of bursty data of variable-bit-rate media streams and therefore increase the maximum admissible load of requests, we also introduce into the scheduling scheme a time-scale-dependent peak consumption rate and a virtual cycle time. Based on BIDS, an effective admission control mechanism can be easily established by checking two simple conditions respectively on the overall system load and buffer size. Our algorithm is very easy to implement. Experiments carried out with an actual disk system and real video stream data verify that it is more robust compared to static scheduling algorithms previously proposed in the literature, especially when handling variable-bit-rate media streams.

This paper discusses the recent research on decomposition techniques in single-machine scheduling. A variety of orderings between adjacent and nonadjacent jobs in an optimal scheduling are presented. A list of decomposition rules is given that enable one to solve large size instances of six single-machine models. A partition technique is also developed to determine the optimal completion times of a general earliness-tardiness model for a given arrangement of jobs.

A growing set of applications require access to digital video and audio. In order to provide playback of such continuous media (CM), scheduling strategies for CM data servers (CMS) are necessary. In some domains, particularly defense and industrial process control, the timing requirements of these applications are strict and essential to their correct operation. In this paper we develop a scheduling strategy for multiple access to a CMS such that the timing guarantees are maintained at all times. First, we develop a scheduling strategy for the steady state, i.e., when there are no changes in playback rate or operation. We derive an optimal Batched SCAN (BSCAN) algorithm that requires minimum buffer space to schedule concurrent accesses. The scheduling strategy incorporates two key constraints: (1) data fetches from the storage system are assumed to be in integral multiples of the block size, and (2) playback guarantees are ensured for frame-oriented streams when each frame can span multiple blocks. We discuss modifications to the scheduling strategy to handle compressed data like motion-JPEG and MPEG.Second, we develop techniques to handle dynamic changes brought about by VCR-like operations executed by applications. We define a suite of primitive VCR-like operations that can be executed. We show that an unregulated change in the BSCAN schedule, in response to VCR-like operations, will affect playback guarantees. We develop two general techniques to ensure playback guarantees while responding to VCR-like operations: passive and active accumulation. Using user response time as a metric we show that active accumulation algorithms outperform passive accumulation algorithms. An optimal response-time algorithm in a class of active accumulation strategies is derived. The results presented here are validated by extensive simulation studies.

In many scheduling problems, an arriving job is stored in an input buffer until it starts to be processed. Also, it may be necessary to hold a partially completed preempted job in an input buffer until processing of this job resumes. In the scheduling literature, most problems have been studied using the implicit assumption that the buffer has infinite capacity. We study preemptive single machine scheduling problems where the buffer capacity is finite. In this scheduling environment, jobs may be lost either because of insufficient input buffer capacity, or because due date requirements cannot be met. We examine problems where the objective is to minimize the weighted or unweighted number of lost jobs. Various assumptions about the generality of the data are examined. We present a complexity classification for various problems, either by deriving an efficient algorithm, or by proving that such an algorithm is unlikely to exist.

Classical scheduling theory assumed that a task may require for its processing only one processor at a time. This assumption is not obvious in the context of new parallel computer systems and parallel algorithms. In this work, we consider preemptive deterministic scheduling of multiprocessor tasks, each of which may require a set of processors at a time. In general, tasks may appear in the system in different moments of time. We will also consider the problem of scheduling such tasks in time windows on particular processors. The existence of low-order polynomial time algorithms for the above problems with C max and L max criteria will be analyzed. The general case of the problem can be solved using a linear programming approach.

We examine issues related to the design of a storage server for video-on-demand (VOD) applications. The storage medium considered is magnetic disks or arrays of disks. We investigate disk scheduling policies, buffer management policies and I/O bus protocol issues. We derive the number of sessions that can be supported from a single disk or an array of disks and determine the amount of buffering required to support a given number of users. Furthermore, we propose a scheduling mechanism for disk accesses that significantly lowers the buffer-size requirements in the case of disk arrays. The buffer size required under the proposed scheme is independent of the number of disks in the array. This property allows for striping video content over a large number of disks to achieve higher concurrency in access to a particular video object. This enables the server to satisfy hundreds of independent requests to the same video object or to hundreds of different objects while storing only one copy of each video object. The reliability implications of striping content over a large number of disks are addressed and two solutions are proposed. Finally, we examine various policies for dealing with disk thermal calibration and the placement of videos on disks and disk arrays.

The single machine group scheduling problem is considered. Jobs are classified into several groups on the basis of group technology, i.e. jobs of the same group have to be processed jointly. A machine set-up time independent of the group sequence is needed between each two consecutive groups. A schedule specifies the sequence of groups and the sequence of jobs in each group. The quality of a schedule is measured by the criteriaF 1, ...,F m ordered by their relative importance. The objective is to minimize the least important criterionF m subject to the schedule being optimal with respect to the more important criterionF m−1 which is minimized on the set of schedules minimizing criterionF m−2 and so on. The most important criterion isF 1, which is minimized on the set of all feasible schedules. An approach to solve this multicriterion problem in polynomial time is presented if functionsF 1, ...,F m have special properties. The total weighted completion time and the total weighted exponential time are the examples of functionsF 1, ...,F m−1 and the maximum cost is an example of functionF m for which our approach can be applied.

We present a new algorithm for resource-constrained scheduling for digital signal processing (DSP) applications when the number of processors is fixed and the objective is to obtain a schedule with the minimum iteration period. This type of scheduling is best suited for moderate speed applications where conservation of area and power is more important than speed. We define and make use of newgraph dependent constraints to obtain a lower bound estimate on the iteration period for any data-flow graph. By satisfying these constraints before performing the scheduling task, we can restrict the design space and can generate valid schedules in less time than previously reported. The graph dependent constraints provide a more accurate lower bound estimate on the iteration period than previously published results. This new scheduling algorithm exploits the iterative nature of DSP algorithms and uses aniterative-loop based scheduling approach. This resource scheduling algorithm has been incorporated in the Minnesota ARchitecture Synthesis (MARS) system. Our approach exploits inter-iteration and intra-iteration precedence constraints and incorporates implicit retiming and pipelining to generate optimal and near optimal schedules.

In the classical scheduling theory, it is widely assumed that a task can be processed by only one processor at a time. With the rapid development of technology, this assumption is no longer valid. In this work we present a problem of scheduling tasks, each of which requires for its processing a set of processors simultaneously and which can be executed on several alternative sets of processors. Scheduling algorithms based on dynamic and linear programming are presented that construct minimum length non-preemptive and preemptive schedules, respectively. Results of computational experiments are also reported.

This paper describes the design and implementation of a continuous media file server intended for use in emerging video-on-demand applications. The main focus and contribution of the paper is in scheduling and admission-control algorithms for accessing the server's processor and storage resources. The scheduling algorithms support multiple classes of tasks with diverse performance requirements and allow for the co-existence of guaranteed real-time requests with sporadic, and unsolicited requests. The scheduler maintains performance guarantees for real-time streams in the presence of unpredictably varying non-real-time traffic while ensuring system stability even during overloads. A prototype video file server was implemented on an Intel 486 platform. Performance results show that a large number of streams can be supported, while maintaining efficient utilization of system resources.

In this paper, we consider the problem of scheduling customers in a real-time system in which all customers are required to be serviced. Such a non-removal system can be distinguished from a removal real-time system in which customers can be removed prior to completing service. We describe and evaluate a simple paradigm for mapping policies for removal systems to policies for non-removal systems. We show that several policies known to be optimal for removal systems map into policies which are also optimal for non-removal systems. The paper concludes with an application of this paradigm to scheduling of requests with real-time constraints on disk subsystems. ___________ This work is supported, in part, by the Office of Naval Research under contract N00014-87-K-0796. ******************************************************************************