Abstract Actors are a popular mechanism for indirectly expressing concurrency. This article examines an implementation in the concurrent dialect of C++, C++, which runs actors on shared‐memory multi‐processor computers. The C++ actor system targets 32–256+ multi‐core shared‐memory computers that form the backbone of high‐performance computing, rather than distributed actor communication or robust execution via parentage fallback used by other actor systems. Five new mechanisms are presented to achieve expressibility, robustness, high performance, and scalability of actor applications across multiple cores: explicit life time (storage management) of actors and messages, combining actors and coroutines, a forward message‐trace and backward message‐return for debugging and failures, a new promise call‐back for ask sends, and an actor implementation that inverts the actor execution‐model by decoupling actor mailboxes with high levels of sharding. Microbenchmarks compare the new actor features with CAF, Protoactor, and classic and typed Akka.

Summary C∀ is a polymorphic, nonobject‐oriented, concurrent, backwards compatible extension of the C programming language. This paper discusses the design philosophy and implementation of its advanced control‐flow and concurrent/parallel features, along with the supporting runtime written in C∀. These features are created from scratch as ISO C has only low‐level and/or unimplemented concurrency, so C programmers continue to rely on library approaches like pthreads. C∀ introduces modern language‐level control‐flow mechanisms, like generators, coroutines, user‐level threading, and monitors for mutual exclusion and synchronization. The runtime provides significant programmer simplification and safety by eliminating spurious wakeup and monitor barging. The runtime also ensures multiple monitors can be safely acquired in a deadlock‐free way, and this feature is fully integrated with all monitor synchronization mechanisms. All control‐flow features integrate with the C∀ polymorphic type‐system and exception handling, while respecting the expectations and style of C programmers. Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming languages.

Summary This paper presents new starvation‐free hardware‐assisted and software‐only algorithms for the N‐thread mutual‐exclusion problem. The hardware‐assisted versions use a single atomic‐CAS instruction and no fences. The software‐only algorithms simulate the CAS instruction using a variation of Burns‐Lamport (1 fence) or Lamport's fast algorithm (3 fences). The algorithms are based on Attiya et al, where every thread in the critical section chooses its successor (if one is available). While Attiya et al use a binary tree for this purpose, it can also be done with a linear search. Surprisingly, all software‐only algorithms perform equally well under maximal contention on three different computer architectures; the hardware‐assisted versions perform better under minimal contention. The new algorithms are between −5% to 50% slower for maximal contention than the starvation‐free first‐come first‐served hardware‐assisted MCS algorithm, which uses two atomic instructions (fetch‐store and CAS); they are between 10% to 50% slower than MCS for minimal contention.

Summary This paper presents a newstarvation‐freesoftware algorithm for theN‐thread mutual‐exclusion problem. In the absence of contention, the algorithm requires only eight write and four read operations to enter and leave the critical section; to the best of our knowledge, this is optimal. For algorithmswith starvation, five write and two read read operations are optimal. In the presence of contention, the algorithm has excellent performance comparable to the best‐known software solutions using only atomic load and store and to a hardware‐assisted lock (MCS) using stronger atomic primitives and used within the Linux kernel. It is rare for software‐only algorithms for mutual exclusion to perform well for both minimal and maximal contention workloads, making the new algorithm largely self‐tuning when exposed to swings in access patterns.

Summary The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems. This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more. Nevertheless, C, which was first standardized almost 30 years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the C project (pronounced “C for all”) is to create an extension of C that provides modern safety and productivity features while still ensuring strong backward compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honor the C programming style; for instance, adding object‐oriented or functional programming with garbage collection is a nonstarter for many C developers. Specifically, C is designed to have an orthogonal feature set based closely on the C programming paradigm, so that C features can be added incrementally to existing C code bases, and C programmers can learn C extensions on an as‐needed basis, preserving investment in existing code and programmers. This paper presents a quick tour of C features, showing how their design avoids shortcomings of similar features in C and other C‐like languages. Experimental results are presented to validate several of the new features.

Summary Dekker's algorithm was thought to be safe in an environment without atomic reads or writes where bits flicker or scramble during simultaneous operations. A counter‐example is presented showing Dekker's algorithm is unsafe without atomic read. A modification to the original algorithm is presented making it RW‐safe, allowing threaded systems to be built on low cost/power hardware without atomic read/write. Correctness is verified by means of invariants and UNITY logic. A performance comparison is made for several two‐thread software mutual‐exclusion algorithms to see if the RW‐safe Dekker is competitive. A subset of the two‐thread solutions are then compared in two N‐thread tournament algorithms. The performance results show that the additional checks in the RW‐safe Dekker do not disadvantage the algorithm in comparison with other two‐thread algorithms. The RW‐safe N‐thread tournament algorithms are competitive with the hardware‐assisted Mellor‐Crummey and Scott algorithm. Copyright © 2015 John Wiley & Sons, Ltd.

Summary Software solutions for mutual exclusion developed over a 30‐year period, starting with complex ad hoc algorithms and progressing to simpler formal ones. While it is easy to dismiss software solutions for mutual exclusion, as this family of algorithms is antiquated and most platforms support atomic hardware instructions, there is still a need for these algorithms in threaded, embedded systems running on low‐cost processors lacking atomic instructions. WhileN‐thread solutions are usually short (10–25 lines of code), each is ingenious with exceptionally subtle aspects, often making it difficult to prove correctness or construct an implementation. This work examines correctness and performance of the implementations. An extensive survey of existing algorithms is presented, with explanations of the intuition behind the algorithms and how they work. Several errors were found and corrections made, as well as a few small improvements, in the existing algorithms; two new high‐performance algorithms were developed. Finally, a worst‐case high‐contention performance experiment is performed to compare the algorithms and contrast them with three common locks based on hardware atomic instructions. The results show our two new algorithms are highly competitive with an equivalent hardware lock (Mellor‐Crummey and Scott) over a range of 1–32 processors. Hence, threading is a viable alternative to event‐driven programming for complex embedded systems without atomic instructions. Copyright © 2014 John Wiley & Sons, Ltd.

In this paper, we study how web-server architecture and implementation affect performance when trying to obtain high throughput on a 4-core system servicing static content. We focus on static content as a growing numbers of servers are dedicated to workloads comprised of songs, photos, software, and videos chunked for HTTP downloads. Two representative static-content workloads are used: one serviced entirely from the file-system cache and the other requires significant disk I/O. We focus on 4-core systems as: 1) it is a widely used configurations in data-centers and cloud services, 2) recent studies show large SMP systems may operate more efficiently when subdivided into smaller subsystems, 3) understanding performance with a smaller number of cores is essential before scaling to a larger number of cores, 4) and 4-cores may be sufficient for many web servers.

In this paper, we extensively tune and then compare the performance of web servers based on three different server architectures. The μserver utilizes an event-driven architecture, Knot uses the highly-efficient Capriccio thread library to implement a thread-per-connection model, and WatPipe uses a hybrid of events and threads to implement a pipeline-based server that is similar in spirit to a staged event-driven architecture (SEDA) server like Haboob.

This paper reaffirms that fixed-priority with preemption threshold (FPPT) is an important form of real-time scheduling algorithm, which fills the gap between fixed-priority preemptive (FPP) and fixed-priority nonpreemptive (FPNP). When a task set is schedulable by FPPT, there may exist multiple valid preemption threshold assignments, which provide useful scheduling options. All valid assignments form a solution space that is delimited by a minimal and maximal assignment. A mechanism is presented to generate part of the valid assignments once the minimal and maximal assignments are known. The known algorithm to compute the minimal assignment starts at FPP, and the known algorithm to compute the maximal assignment starts from any valid assignment. This paper presents algorithms to compute the minimal and maximal assignments starting from FPNP, and the proofs for the correctness of these algorithms are also presented.

This discussion addresses a number of urban legends about concurrency in an attempt to separate the myth from the fact. These legends are as follows: 1 concurrent = parallel; 2 coroutining = concurrency; 3 synchronization = mutual exclusion; 4 Dekker < Peterson; 5 concurrency = library; 6 inheritance anomaly = major concurrency problem; 7 signalling = hints; 8 spurious wakeup = efficiency. Identifying and understanding the fundamental concepts underlying concurrency is essential to the field. Equally important is not to confuse sequential and concurrent concepts. Finally, approaches based solely on efficiency are insufficient to justify a weak or difficult to use concurrent concept or construct. Copyright © 2005 John Wiley & Sons, Ltd.

An implicit (automatic) signal monitor uses a waituntil predicate statement to construct synchronization, as opposed to an explicit-signal monitor using condition variables and signal/wait statements for synchronization. Of the two synchronization approaches, the implicit-signal monitor is often easier to use and prove correct, but has an inherently high execution cost. Hence, its primary use is for prototyping concurrent systems using monitors, where speed and accuracy of software development override execution performance. After a concurrent system is working, any implicit-signal monitor that is a performance bottleneck can be converted to an explicit-signal monitor. Unfortunately, many monitor-based concurrency systems provide only explicit-signal monitors, precluding the design benefits of implicit-signal monitors.This article presents a historical look at the development of the implicit-signal monitor in relation to its counterpart the explicit-signal monitor. An analysis of the different kinds of implicit-signal monitors shows the effects certain design decisions have on the problems that can be solved and the performance of the solutions. Finally, an extensive discussion is presented on simulating an implicit-signal monitor via different explicit-signal monitors. These simulations are reasonably complex, depending on the kind of explicit-signal monitor available for the simulation and the desired semantics required for the implicit-signal monitor. Interestingly, the complexity of the simulations also illustrates certain deficiencies with explicit-signal monitors, which are discussed in detail. Performance comparisons are made among the different simulations with monitors from the concurrent systems PThreads, Java, and μC++.

The primary goal of a real-time system is predictability. Achieving this goal requires all levels of the system to work in concert to provide fixed worst-case execution-times. Un-fortunately, many real-time systems are overly restrictive, providing only ad-hoc scheduling facilities and basic concurrent functionality. Ad-hoc scheduling makes developing, verifying, and maintaining a real-time system extremely difficult and time consuming. Basic concurrent functionality forces programmers to develop complex concurrent programs without the aid of high-level concurrency features.Encouraging the use of sophisticated real-time theory and methodology, in conjunction with high-level concurrency features, requires flexibility and extensibility. Giving real-time programmers access to the underlying system data-structures makes it possible to interact with the system to incorporate new ideas and fine-tune specific applications. This paper explores this approach by examining its effect on a selection of crucial real-time issues: real-time monitors, timeouts, dynamic-priority scheduling and basic priority inheritance. The approach is implemented in μC++.

It is no longer possible to consider exception handling as a secondary issue in language design, or even worse, a mechanism added after the fact via a library approach. Exception handling is a primary feature in language design and must be integrated with other major features, including advanced control flow, objects, coroutines, concurrency, real-time, and polymorphism. Integration is crucial as there are both obvious and subtle interactions between exception handling and other language features. Unfortunately, many exception handling mechanisms work only with a subset of the features and in the sequential domain. A framework for a comprehensive, easy to use, and extensible exception handling mechanism is presented for a concurrent, object-oriented environment. The environment includes language constructs with separate execution stacks, e.g. coroutines and tasks, so the exception environment is significantly more complex than the normal single-stack situation. The pros and cons of various exception features are examined, along with feature interaction with other language mechanisms. Both exception termination and resumption models are examined in this environment, and previous criticisms of the resumption model, a feature commonly missing in modern languages, are addressed.

Three pointer based parallel join algorithms are presented and analyzed for environments in which secondary storage is made transparent to the programmer through memory mapping. P.A. Buhr et al. (1992) show that data structures such as B Trees, R Trees and graph data structures can be implemented as efficiently and effectively in this environment as in a traditional environment using explicit I/O. We show how higher order algorithms, in particular parallel join algorithms, behave in a memory mapped environment. A quantitative analytical model has been developed to conduct performance analysis of the parallel join algorithms. The model has been validated by experiments.

Article μDatabase: parallelism in a memory-mapped environment (research summary) Share on Authors: Peter A. Buhr Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Anil K. Goel Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Naomi Nishimura Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Prabhakar Ragde Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 196–199https://doi.org/10.1145/237502.237547Online:24 June 1996Publication History 0citation143DownloadsMetricsTotal Citations0Total Downloads143Last 12 Months0Last 6 weeks0 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 SiteGet Access

Abstract We present a design, including its motivation, for introducing concurrency into C++. The design work is based on a set of requirements and elementary execution properties that generate a corresponding set of programming language constructs needed to express concurrency. The new constructs continue to support object‐oriented facilities such as inheritance and code reuse. Features that allow flexibility in accepting and subsequently postponing servicing of requests are provided. Currently, a major portion of the design is implemented, supporting concurrent programs on shared‐memory uniprocessor and mulitprocessor computers.

Abstract This paper presents a general model for dealing with abnormal events during program execution and describes how this model is implemented in the μSystem. (The μSystem is a library of C definitions that provide light‐weight concurrency on uniprocessor and multiprocessor computers running the UNIX operating system.) Two different techniques can be used to deal with an abnormal event: an exception, which results in an exceptional change in control flow from the point of the abnormal event; and an intervention, which is a routine call from the point of the abnormal event that performs some corrective action. Users can define named exceptions and interventions in conjunction with ones defined by the μSystem. Exception handlers and intervention routines for dealing with abnormal events can be defined/installed at any point in a program. An exception or intervention can then be raised or called, passing data about the abnormal event and returning results for interventions. Interventions can also be activated in other tasks, like a UNIX signal. Such asynchronous interventions may interrupt a task's execution and invoke the specified intervention routine. Asynchronous interventions are found to be useful to get another task's attention when it is not listening through the synchronous communication mechanism.

Abstract This paper presents a description of the μSystem, which is a library of C routines that provide light‐weight concurrency on uniprocessor and multiprocessor computers running the UNIX operating system. A discussion of the run‐time structure of a μSystem program is given, which includes the following concepts: coroutines, tasks, virtual processors and clusters. Next the routines that implement these concepts are discussed in detail. Finally, some performance figures from the μSystem are given and discussed, followed by a comparison of the μSystem with other similar systems.