SUMMARY This paper presents algorithms for concurrently reading and modifying a red‐black tree (RBTree). The algorithms allow wait‐free, linearly scalable lookups in the presence of concurrent inserts and deletes. They have deterministic response times for a given tree size and uncontended read performance that is at least 60% faster than other known approaches. The techniques used to derive these algorithms arise from a concurrent programming methodology called relativistic programming. Relativistic programming introduces write‐side delay primitives that allow the writer to pay most of the cost of synchronization between readers and writers. Only minimal synchronization overhead is placed on readers. Relativistic programming avoids unnecessarily strict ordering of read and write operations while still providing the capability to enforce linearizability. This paper shows how relativistic programming can be used to build a concurrent RBTree with synchronization‐free readers and both lock‐based and transactional memory‐based writers. Copyright © 2013 John Wiley & Sons, Ltd.

Read-copy update (RCU) is a synchronization technique that often replaces reader-writer locking because RCU's read-side primitives are both wait-free and an order of magnitude faster than uncontended locking. Although RCU updates are relatively heavy weight, the importance of read-side performance is increasing as computing systems become more responsive to changes in their environments. RCU is heavily used in several kernel-level environments. Unfortunately, kernel-level implementations use facilities that are often unavailable to user applications. The few prior user-level RCU implementations either provided inefficient read-side primitives or restricted the application architecture. This paper fills this gap by describing efficient and flexible RCU implementations based on primitives commonly available to user-level applications. Finally, this paper compares these RCU implementations with each other and with standard locking, which enables choosing the best mechanism for a given workload. This work opens the door to widespread user-application use of RCU.

Media streaming over TCP has become increasingly popular because TCP's congestion control provides remarkable stability to the Internet. Streaming over TCP requires adapting to bandwidth availability, but unforunately, TCP can introduce significant latency at the application level, which causes unresponsive and poor adaptation. This article shows that this latency is not inherent in TCP but occurs as a result of throughput-optimized TCP implementations. We show that this latency can be minimized by dynamically tuning TCP's send buffer. Our evaluation shows that this approach leads to better application-level adaptation and it allows supporting interactive and other low-latency applications over TCP.

The advent of multi-core and multi-threaded processor architectures highlights the need to address the well-known shortcomings of the ubiquitous lock-based synchronization mechanisms. The emerging transactional-memory synchronization mechanism is viewed as a promising alternative to locking for high-concurrency environments, including operating systems. This paper presents a constructive critique of locking and transactional memory: their strengths, weaknesses, and challenges

This paper describes the results of the first comprehensive analysis of a range of popular on-line, multiplayer, game servers. The results show that the traffic behavior of these servers is highly predictable and can be attributed to the fact that current game designs target the saturation of the narrowest, last-mile link. Specifically, in order to maximize the interactivity of the game itself and to provide relatively uniform experiences between players playing over different network speeds, on-line games typically fix their usage requirements in such a way as to saturate the network link of their lowest speed players. While the traffic observed is highly predictable, the traces also indicate that these on-line games provide significant challenges to current network infrastructure. As a result of synchronous game logic requiring an extreme amount of interactivity, a close look at the trace reveals the presence of large, highly periodic, bursts of small packets. With such stringent demands on interactivity, routers must be designed with enough capacity to quickly route such bursts without delay.

We provide a performance comparison of generated Infopipes that have been translated and the Spi/XlP variant of Infopipe specification into executable code. Infopipes are abstractions to support information flow applications. These tools are evaluated through a realistic application: a continuous image streaming program. We implement the application in C and compare its performance to both a hand-written application and one that uses SunRPC.

Traditionally, real-time scheduling mechanisms have been used to provide predictable scheduling latency but these mechanisms are difficult to use in general-purpose operating systems (OSs) because they require precise specification of thread requirements in terms of low-level resources such as CPU cycles. In a general-purpose environment such a specification may not be statically available. In this paper, we present the design, implementation and evaluation of a novel feedback-based real-rate scheduler that automatically infers thread requirements and thus makes it easier to use real-time scheduling mechanisms in general-purpose OSs. The real-rate controller uses thread-specified time-stamps that indicate a thread's progress to estimate resource requirements. The goal of the controller is to regulate the overallocation of resources and the delay experienced by a thread. It meets these goals by using gain compensation and by choosing an appropriate sampling period for the controller that depends only on the granularity of thread time-stamps. A key benefit of the real-rate approach is that it can be easily applied in a general-purpose environment across different applications because the controller does not require any tuning.

In this paper we explore the use of priority progress streaming (PPS) for video surveillance applications. PPS is an adaptive streaming technique for the delivery of continuous media over variable bit-rate channels. It is based on the simple idea of reordering media components within a time window into priority order before transmission. The main concern when using PPS for live video streaming is the time delay introduced by reordering. In this paper we describe how PPS can be extended to support live streaming and show that the delay inherent in the approach can be tuned to satisfy a wide range of latency constraints while supporting fine-grain adaptation.

This paper presents a general design strategy for streaming media applications in best effort computing and networking environments. Our target application is video on demand using personal computers and the Internet. In this scenario, where resource reservations and admission control mechanisms are not generally available, effective streaming must be able to adapt in a responsive and graceful manner. The design strategy we propose is based on a single simple idea, priority data dropping, or priority drop for short. We evaluate the efficacy of priority drop as an adaptation tool in the video and networking domains. Our technical contribution with respect to video is to show how to express adaptation policies and how to do priority-mapping, an automatic translation from adaptation policies to priority assignments on the basic units of video. For the networking domain, we present priority-progress streaming, a real-time best-effort streaming protocol. We have implemented and released a prototype video streaming system that incorporates priority-drop video, priority mapping, and priority-progress streaming. Our system demonstrates a simple encode once, stream anywhere model where a single video source can be streamed across a wide range of network bandwidths, on networks saturated with competing traffic, all the while maintaining real-time performance and gracefully adapting quality.

Abstract Applications that process continuous information flows are challenging to write because the application programmer must deal with flow‐specific concurrency and timing requirements, necessitating the explicit management of threads, synchronization, scheduling and timing. We believe that middleware can ease this burden, but many middleware platforms do not match the structure of these applications, because they focus on control‐flow centric interaction models such as remote method invocation. Indeed, they abstract away from the very things that the information‐flow centric programmer must control. This paper describes Infopipes—a new high‐level abstraction for information flow applications—and a middleware framework that supports them. Infopipes handle the complexities associated with control flow and multi‐threading, relieving the programmer of these tasks. Starting from a high‐level description of an information flow pipeline, the framework determines which parts of a pipeline require separate threads or coroutines, and handles synchronization transparently to the application programmer. The framework also gives the programmer the freedom to write or reuse components in a passive style, even though the configuration will actually require the use of a thread or coroutine. Conversely, it is possible to write a component using a thread and know that the thread will be eliminated if it is not needed in a pipeline. This allows the most appropriate programming model to be chosen for a given task, and existing code to be reused irrespective of its activity model. Copyright © 2003 John Wiley & Sons, Ltd.

This paper describes the results of a 500 million packet trace of a popular on-line, multi-player, game server. The results show that the traffic behavior of this heavily loaded game server is highly predictable and can be attributed to the fact that current game designs target the saturation of the narrowest, last-mile link. Specifically, in order to maximize the interactivity of the game and to provide relatively uniform experiences between all players, on-line games typically fix their usage requirements in such a way as to saturate the network link of their lowest speed players. While the traffic observed is highly predictable, the trace also indicates that these on-line games provide significant challenges to current network infrastructure. Due to synchronous game logic requiring an extreme amount of interactivity, a close look at the trace reveals the presence of large, highly periodic, bursts of small packets. With such stringent demands on interactivity, routers must be designed with enough capadty to quickly route such bursts without delay. As current routers are designed for bulk data transfers with larger packets, a significant, concentrated deployment of online game servers will have the potential for overwhelming current networking equipment.

When executing soft real-time tasks in a shared processor, it is important to properly allocate the computational resources such that the quality of service requirements of each task are satisfied. In this paper we propose Adaptive Reservations, based on applying a feedback scheme to a reservation based scheduler After providing a precise mathematical model of the scheduler, we describe how this model can be used for synthesising the controller by applying results from control theory. Finally, we show the effectiveness of our method by simulation and by experiments with an MPEG player running on a modified Linux kernel.

The Internet's ubiquity amply motivates us to harness it for video distribution, however, its best-effort service model is in direct conflict with video's inherent timeliness requirements. Today, the Internet is unrivaled in its rich composition, consisting of an unparalleled assortment of networks and hosts. This richness is the result of an architecture that emphasizes interoperability over predictable performance. From the lowest levels, the Internet architecture prefers the best effort service model. We feel current solutions for media-streaming have yet to adequately address this conflict between timeliness and best-effort service.We propose that streaming-media solutions targetted at the Internet must fully embrace the notion of graceful degradation, they must be architected with the expectation that they operate within a continuum of service levels, adjusting quality-resource trade-offs as necessary to achieve timeliness requirements. In the context of the Internet, the continuum of service levels spans across a number oftime scales, ranging from sub-second timescales to timescales as long as months and years. We say sub-second timescales in relation to short-term dynamics such as network traffic and host workloads, while timescales of months and years relate to the continuous deployment of improving network, compute and storage infrastructure.We support our thesis with a proposal for a streaming model which we claim is simple enough to use end-to-end, yet expressive enough to tame the conflict between real-time and best-effort personalities of Internet streaming. The model is called Priority-Progress streaming. In this proposal, we will describe the main features of Priority-Progress streaming, which we have been implemented in a software-based streaming video system, called the Quasar pipeline.Our work is primarily concerned with the class of streaming applications. To prevent confusion, we now clarify the important distinction between streaming and other forms of distribution, namely download. For a video, we assume download is defined so that the transfer of the video must complete before the video is viewed. Transfer and viewing are temporally sequential. With this definition, it is a simple matter to employ Quality-adaptive video. One algorithm would be to deliver the entire video in the order from low to high quality components. The user may terminate the download early, and the incomplete video will automatically have as high quality as was possible. Thus, Quality-adaptive download can be implemented in an entirely best-effort, time-insensitive, fashion. On the other hand, we assume streaming means that the user views the video at the same time that the transfer occurs. Transfer and viewing are concurrent. There are timeliness requirements inherent in this definition, which can only be reconciled with best-effort delivery through a time-sensitive adaptive approach.

Specialization has been recognized as a powerful technique for optimizing operating systems. However, specialization has not been broadly applied beyond the research community because current techniques based on manual specialization, are time-consuming and error-prone. The goal of the work described in this paper is to help operating system tuners perform specialization more easily. We have built a specialization toolkit that assists the major tasks of specializing operating systems. We demonstrate the effectiveness of the toolkit by applying it to three diverse operating system components. We show that using tools to assist specialization enables significant performance optimizations without error-prone manual modifications. Our experience with the toolkit suggests new ways of designing systems that combine high performance and clean structure.

The availability of tremendous computation power coupled with widespread connectivity have fueled the development of real-time environmental observation and forecasting systems (EOFS).

This talk will present a systems-centric view of the opportunities, effectiveness, and challenges of applying specialization techniques to operating systems. The first part of the talk will focus on our experiences using manual and then tool-assisted specialization in the systematic optimization of legacy operating systems software. These experiences were gained in the Synthetix project which explored the use of static, dynamic and incremental optimistic specialization in a variety of operating system contexts, including file system calls in HP-UX, Linux signal delivery, Berkeley packet filter processing, and Sun RPC. The second part of the talk will focus on the lessons learned in Synthetix, the implications for systems, and the key opportunities and challenges for future research.

Hot swapping technology combined with pervasive heterogeneous networks empowers mobile laptop users to select the best network device for their current environment.Unfortunately, the majority of systemsoftwareremains'%ustomized"foraparticularnehvorkconfiguration, and assumes that many characteristics associated with the network environment remain invariant over the runtime of the software.Mobility causes changes in the environment and nullifies many of these assumptions.This leads to severeloss in system functionality when resources are lost, and failure to benefit when resources are gained.This paper describes Physical Media Independence (PMI), an architecture for dynamically diverse network interface management.PMI addresses three issuesconcemingdynamicnehvork configuration.First, a model for device availability is proposed to accurately determine when a network device is operational.Second, a structured methodology is used to construct adapters that reconfigure the system when the set of available devices change.The methodology breaks traditional layering using a meta-interface to pass events and information among layers, allowing each layer to adapt in a manner best suited to it.Third, we examine the effect of transparent and non-transparent reconfiguration operations on a variety of applications.We find that adaptive, resource intensive applications behave more efficiently when informed of device availability events.We compare the functionality of an adaptive application running on top of a adaptive operating system (OS) with and without cross-layer notifications.

No abstract available.

Conventionaloperating system code is written to deal with all possible system stat es, and performs considerable interpretation to determine the current system state before taking action.A consequence of this approach is that kernel calls which perform little actual work take a long time to execute.To address this problem, we use specialized operating system code that reduces interpretation for common cases, but still behaves correctly in the fully general case.We describe how specialized operating system code can be generated and bound wtcrementally as the information on which it depends becomes available.We extend our specialization techniques to include the notion of optimistic in c remental specialization n: a technique for generating specialized kernel code optimistically for system states that are likely to occur, but not certain.The ideas outlined in this paper allow the conventional kernel design tenet of "optimizing for the common case" to be extended to the domain of adaptive operating systems.We also show that aggressive use of specialization can produce in-kernel implementations of operating system functionality with performance comparable to user-level implementations.We demonstrate that these ideas are applicable in realworld operating systems by describing a re-implementation of the HP-UX file system.Our specialized read system call reduces the cost of a single byte read by a factor of 3, and an 8 KB read by 26~o, while preserving the semantics of the HP-UXread call.By relaxing the semantics of HP-UX read we were able to cut the cost of a single byte read system call by more than an order of magnitude.1

Adaptive load distribution is necessary for parallel applications to co-exist effectively with other jobs in a network of shared, heterogeneous workstations. We present three methods that provide such support for PVM applications. Two of these methods, MPVM (migratable PVM) and UPVM (user-level PVM), adapt to changes in the workstation environment by transparently migrating the virtual processors (VPs) of the parallel application. A VP in MPVM is a Unix process, while UPVM defines lightweight process-like VPs. The third method, ADM (adaptive data movement), is a programming methodology for writing programs that perform adaptive load distribution through data movement. These methods are discussed and compared in terms of effectiveness, usability and performance.>

Article Free Access Share on Incremental partial evaluation: the key to high performance, modularity and portability in operating systems Authors: Charles Consel View Profile , Calton Pu View Profile , Jonathan Walpole View Profile Authors Info & Claims PEPM '93: Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationAugust 1993 Pages 44–46https://doi.org/10.1145/154630.154635Online:01 August 1993Publication History 20citation287DownloadsMetricsTotal Citations20Total Downloads287Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

People use various techniques to reduce the complexity of realtime multiparty conversational interaction. These techniques—formal meetings, for example—generally restrict the format of the interaction in an attempt to reduce the amount of control information which must be processed by each conversant. This allows the conversants to concentrate more on domain specific information but severely reduces the efficiency of interaction. Previous approaches to the design of computer-mediated interaction (CMI) systems have largely attempted to automate such mechanisms. This paper examines the current state of research in the area of CMI systems and suggests a new direction for research in this area based on the utilisation of control information to increase communicative efficiency. To demonstrate the practical application of these ideas, an initial design for a CMI system which uses the concept of virtual conversants is presented. The CMI system assumes the burden of processing control information and presents to each conversant: a two party interaction model for control information a multiparty interaction model for domain information.

The authors argue that immutability is a suitable base on which to build distributed software engineering environments. They discuss the various approaches to maintaining consistency in immutable object systems and compare D.P. Reed's model of time domain addressing (ACM Trans. Comput. Syst., vol.1, no.1, p.3-23, Feb. 1983), with their own model of domain relative addressing. They demonstrate the suitability of domain relative addressing for use in distributed-software engineering environments.>