Search

Many computer systems, such as those for open system environments or multimedia services, need an efficient schedulability test for online admission control of new jobs. Although various polynomial time schedulability tests have been proposed, they often fail to decide the schedulability of the system precisely when the system is heavily loaded. On the other hand, most precise schedulability tests proposed to date have a high complexity and may not be suitable for online tests. In this paper, we present new efficient online schedulability tests for both the periodic process model and the multiframe process model in uniprocessor environments. The schedulability tests are shown to be more precise and efficient than any existing polynomial-time schedulability tests. Moreover, the tests can be done incrementally as each new task arrives at the system. Our proposed tests can also be used for the multiframe model where a task may have different computation times in different periods. We show the performance of the proposed schedulability tests in several simulation experiments. [ABSTRACT FROM AUTHOR]

We propose a class of real-time data access protocols called SSP (Similarity Stack Protocol). The correctness of SSP schedules is justified by the concept of similarity which allows different but sufficiently timely data to be used in a computation without adversely affecting the outcome. SSP schedules are deadlock-free, subject to limited blocking, and do not use locks. We give a schedulability bound for SSP and also report simulation results which show that SSP is especially useful for scheduling real-time data access on multiprocessor systems. Finally, we present a variation of SSP which can be implemented in an autonomous fashion in the sense that scheduling decisions can be made with local information only. [ABSTRACT FROM AUTHOR]

With the advance of hardware and software technology, modern phased array radars are now built with commercial-off-theshelf (COTS) components, and it opens up a new era in real-time resource scheduling of digital signal processing. This paper targets the essential issues in building a component-oriented Signal Processor (SP), which is one of the two major modules in modern phased array radars. We propose a simple but effective task allocation policy and a real-time scheduling algorithm to address the design objectives of SP's. We are able to bound the number of processing units needed for a component-oriented SP in the design time, while everything was done empirically in the past. A series of experiments was done to demonstrate the strength of our methodology. [ABSTRACT FROM AUTHOR]

While there has been a significant amount of research in real-time concurrency control, little work has been done in logging and recovery for real-time databases. This paper proposes a two-version approach which considers both real-time concurrency control and recovery. We propose a network-server-based architecture and algorithms which can not only reduce the blocking time of higherpriority transactions and improve the response time of client-side read-only transactions, but also provide a diskless runtime logging mechanism and an efficient and predictable recovery procedure. The performance of the algorithms was verified by a series of simulation experiments by comparing the algorithms with the well-known Priority Ceiling Protocol (PCP), the Read/Write PCP, the New PCP, and the 2-version two-phase locking protocol, for which we have very encouraging results. The schedulability of higher-priority transactions and the response time of client-side read-only transactions were all greatly improved. [ABSTRACT FROM AUTHOR]

Investigates a class of rate-based real-time scheduling algorithms based on the idea of general processor sharing. Review of related works; Discussion of the Earliest-Completion-Time scheduling algorithm; Performance evaluation.

Examines the proposed concept of priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. Details on the computing resources of multiprocessor computer systems; Role of real-time concurrency control on database consistency; Use of performance metrics.

Presents a study which formalized the concept of similarity that has been used as an ad hoc basis by application engineers to provide more flexibility in concurrency control. Semantics of real-time transactions; Correctness criteria; Synchronization; Suggestions for future research.

Presents information on a study which described a similarity-based load adjustment for static real-time transaction systems. Principles for similarity-based load adjustment; Simulation results; Conclusions.

An introduction is presented in which editors discuss various research papers within the issues focused on issues of operating systems for sensor networks covering topics including, data centric sensor, Guaranteed Time Slot (GTS) mechanism, and hybrid data delivery protocol.

While the capacity of flash-memory storage systems keeps increasing significantly, an effective and efficient management of flash-memory space has become a critical design issue. Different granularities in space management impose different management costs and mapping efficiency. In this paper, we will explore an address translation mechanism (AddrTM) that can dynamically and adaptively switch between different granularities in the mapping of logical block addresses into physical block addresses in flash-memory management. The objective is to provide high performance in address mapping and space utilization and, at the same time, to have the main memory requirements, the garbage collection overhead, and the system initialization time under proper management. The experimental results show that the proposed adaptive mechanism can provide better performance improvement and practicability than other well-known coarse-grained management mechanisms over realistic workloads. [ABSTRACT FROM AUTHOR]

Power-aware routing in wireless ad hoc networks has been extensively explored in recent years, and various routing metrics were developed for the prolongation of network lifetime. This work studies power-aware routing so as to maximize the minimum remaining energy of all nodes after routing. This routing metric, referred to as Maximum-Residual Routing, aims at maintaining the minimum remaining energy as high as possible so as to delay the fist failure time of nodes in the network. In this paper, a polynomial-time optimal algorithm is proposed for Maximum-Residual Multicasting. We then show that Maximum-Residual Aggregating is $${\mathcal{NP}}$$-hard and that, unless $${\mathcal{P = NP}},$$ its minimization version cannot be approximated within a ratio better than (2 − ε) for any ε > 0. The proposed routing algorithm for Maximum-Residual Multicasting can be applied to existing routing protocols, especially those based on the link-state approach. The capability of the algorithm was evaluated by a series of experiments, for which we have very encouraging results in network lifetime and load balance. [ABSTRACT FROM AUTHOR]

Motivated by the strong demand for flash memory with enhanced reliability, this work attempts to achieve improved flash-memory endurance without substantially increasing overhead and without excessively modifying popular implementation designs such as the Flash Translation Layer protocol (FTL), NAND Flash Translation Layer protocol (NFTL), and Block-Level flash translation layer protocol (BL). A wear-leveling mechanism for moving data that are not updated is proposed to distribute wear-leveling actions over the entire physical address space, so that static or rarely updated data can be proactively moved and memory-space requirements can be minimized. The properties of the mechanism are then explored with various implementation considerations. A series of experiments based on a realistic trace demonstrates the significantly improved endurance of FTL, NFTL, and BL with limited system overhead. [ABSTRACT FROM AUTHOR]

Flash memory has been widely adopted in various consumer products for information storage, especially for embedded systems. With strong demands on product designs for overhead control and performance requirements, vendors must have an effective design for the mapping of logical block addresses (LBAs) and physical addresses of data over flash memory. This paper targets such an essential issue by proposing a configurable mapping method that could trade the main-memory overhead with the system performance under the best needs of vendors. A series of experiments is conducted to provide insights on different configurations and the proposed method, compared to existing implementations. [ABSTRACT FROM AUTHOR]

In recent years, many modern phased-array radars are built with commercial off-the-shelf components, and the functions of many hardware components are also reimplemented by software modules. In such systems, radar tasks could be modeled as distributed real-time tasks which require end-to-end deadline guarantees and have precedence constraints. Different from most previous work on either algorithms with restrictions in resource utilization or heuristics without analytical ways for schedulability guarantees, the objective of this paper is to propose a joint real-time scheduling algorithm for both transmitter/receiver and signal processor workloads with an analytical framework for offline probabilistic analysis and online admission control. The strength of our approach is verified by analysis results and a series of experiments based on a real phased-array radar for air defense frigates [18]. [ABSTRACT FROM AUTHOR]

Discusses the concepts of extremely and critically utilizing task set and an approach to find the utilization bound as a function of the information about the task set. Preemptive fixed-priority scheduling; Rate-monotonic priority assignment; Linear programming; Bound algorithms.

Third Generation Partnership Project working group proposes the high-speed downlink packet access to speed up downlink transmission for the universal mobile telecommunication system, where the time-division-based high-speed downlink shared-channel (HS-DSCH) approach is adopted. Our previous work proposed the shared-channel assignment and scheduling (SCAS) scheme to efficiently schedule the DSCH to serve different connections, which guarantees the requested transmission rate for each connection. However, limitations exist in the SCAS scheme: 1) the requested transmission rates of connections must be two's power numbers of the basic transmission rate and 2) all served connections should be rescheduled while a new request is granted, which introduces extra rescheduling overhead to the system. This paper proposes the elastic shared-channel assignment and scheduling (eSCAS) scheme to overcome these limitations. We formally prove the correctness of the eSCAS scheme. An analytical model and simulation experiments are conducted to compare the performance for eSCAS and SCAS. Our study shows that eSCAS can significantly improve the acceptance rate for new connections without increasing the rescheduling overhead. [ABSTRACT FROM AUTHOR]

Abstract??TheUniversal Mobile Telecommunications System(UMTS) adopts the WCDMA technology as the radio access interface to provide variable transmission rate services. There are four classes of connections identified in UMTS, which are the conversational, streaming, interactive, and background connections. To efficiently utilize radio bandwidth, the shared channel approach is proposed to deliver the packets for the interactive and background connections. This paper proposes a ?Shared-Channel Assignment and Scheduling? (SCAS) algorithm to periodically allocate shared channels to serve interactive and background connections. We conduct formal mathematical proofs and simulation experiments to investigate the performance of the SCAS algorithm. We formally prove that with SCAS, a shared channel can be fully utilized (i.e., the utilization of a shared channel can be up to 100%) to serve the interactive connections. Our analysis indicates that compared with the previously proposed shared channel allocation and scheduling algorithms, there are less computation and communication overheads introduced in the SCAS algorithm. The results of the simulation experiments indicate that it is preferred to set up the Transmission Time Interval (TTI; that is, the unit of time interval for shared channel allocation) smaller to optimize the performance of the SCAS algorithm, including the shared channel utilization and the average waiting time of a connection before getting transmission service. [ABSTRACT FROM AUTHOR]