Search

The article describes a test system designed for verification of the real-time operating system (RTOS) for embedded systems, which was developed and used at the Scientific Research Institute for System Analysis of the Russian Academy of Sciences (SRISA RAS). This Unix-like operating system is based on the POSIX and ARINC-653 programming standards. Of course, there exists specialized software for automation of testing of Unix-like systems: Avocado, LAVA, Linux Test Project, Linux Distribution Checker, Open POSIX Test Suite, UnixBench, etc. But the use of such ready-made software systems is not always convenient, because they either contain only highly specialized test suites, or support only certain hardware, or do not contain a flexible configuration system. Therefore, the researchers at the SRISA RAS developed their own original test system. The task was to create a convenient testing tool for both software testers and programmers. Many years of experience in using the test system has shown the effectiveness of its use to improve the quality of software products, reduction of time spent on testing and analysis of results, maximally automate software testing process, speed up the process of developing new software versions, and simplify the process of debugging, finding and fixing errors by software developers. [ABSTRACT FROM AUTHOR]

Aurora OS is a POSIX-compatible mobile Linux distribution designed for enterprise and business purposes. The main application area of devices based on Aurora OS is corporations in Russia. For example, such devices are used by field workers to receive tasks and send reports. The reports are generated by filling out complex forms with a large number of input fields and options to choose from. Speech recognition allows to significantly speed up this process. Aurora OS has no built-in tools to implement such functions, so developers of software for field workers need to use a third-party solution. There are several voice recognition engines for POSIX-compatible systems, but only those that support the Russian language, can work locally on devices, and have a free license are suitable for the task. The only solution for the task that meets the criteria is the Kaldi engine. However, it depends on libraries implemented using Fortran, and Aurora OS does not support this programming language. Therefore, it was necessary to develop a way to use software implemented in Fortran in an environment that does not have a native support for it. This paper proposes an approach for solving such a problem, which can be applied to all similar cases.

In this paper, we describe DiOS , a lightweight model operating system, which can be used to execute programs that make use of POSIX APIs. Such executions are fully reproducible: running the same program with the same inputs twice will result in two exactly identical instruction traces, even if the program uses threads for parallelism. DiOS is implemented almost entirely in portable C and C++: although its primary platform is DiVM , a verification-oriented virtual machine, it can be configured to also run in KLEE, a symbolic executor. Finally, it can be compiled into machine code to serve as a user-mode kernel. Additionally, DiOS is modular and extensible. Its various components can be combined to match both the capabilities of the underlying platform and to provide services required by a particular program. Components can be added to cover additional system calls or APIs or removed to reduce overhead. The experimental evaluation has three parts. DiOS is first evaluated as a component of a program verification platform based on DiVM. In the second part, we consider its portability and modularity by combining it with the symbolic executor KLEE. Finally, we consider its use as a standalone user-mode kernel. [ABSTRACT FROM AUTHOR]

Whereas Perl-compatible regular expression matchers typically exhibit some variation of leftmost-greedy semantics, those conforming to the posix standard are prescribed leftmost-longest semantics. However, the posix standard leaves some room for interpretation, and Fowler and Kuklewicz have done experimental work to confirm differences between various posix matchers. The Boost library has an interesting take on the posix standard, where it maximises the leftmost match not with respect to subexpressions of the regular expression pattern, but rather, with respect to capturing groups. In our work, we provide the first formalisation of Boost semantics, analyze the complexity of regular expression matching when using Boost semantics, and provide efficient algorithms for both online and multipass matching. [ABSTRACT FROM AUTHOR]

Summary: In this paper we study the performance of POSIX submatch extraction algorithms based on nondeterministic finite automata (NFA). We propose an algorithm that combines Laurikari tagged NFA and extended Okui‐Suzuki disambiguation. The algorithm works in worst‐case O(n m2 t) time and O(m2) space (including preprocessing), where n is the length of input, m is the size of the regular expression with bounded repetition expanded and t is the number of capturing groups and subexpressions that contain them. On real‐world benchmarks our algorithm performs close to the O(n m t) complexity of leftmost‐greedy matching, although on artificial benchmarks it can be significantly slower. We propose a lazy version of the algorithm that runs much faster, but requires O(n m2) space. We show that the Kuklewicz algorithm is slower in practice, and the backward matching algorithm proposed by Cox is incorrect. [ABSTRACT FROM AUTHOR]

This paper deals with the reconfigurable real-time systems that should be adapted to their environment under real-time constraints. The reconfiguration allows moving from one implementation to another by adding/removing/modifying parameters of real-time software tasks which should meet related deadlines. Implementing those systems as threads generates a complex system code due to the large number of threads, which may lead to a reconfiguration time overhead as well as the energy consumption and the memory allocation increase. Thus this paper proposes a multiobjective optimization approach for reconfigurable systems called MO2R2S for the development of a reconfigurable real-time system. Given a specification, the proposed approach aims to produce an optimal design while ensuring the system feasibility. We focus on three optimization criteria: 1) response time; 2) memory allocation; and 3) energy consumption. To address the portability issue, the optimal design is then transformed to an abstract code that may in turn be transformed to a concrete code which is specific to a procedural programming (i.e., POSIX) or an object-oriented language (i.e., RT-Java). The MO2R2S approach allows reducing the number of threads by minimizing the redundancy between the implementation sets. By an experimental study, such optimization permits to decrease the memory allocation by 28.89%, the energy consumption by 40.2%, and the response time by 61.32%. [ABSTRACT FROM AUTHOR]

Safety-critical automotive applications require predictable and deterministic execution to not miss the timing requirements. Logical Execution Time (LET) is a paradigm already established in the automotive industry to improve the predictability and correctness of time-critical applications. Despite LET being already part of the AUTOSAR Classic standard, no prior work has addressed the design of this model on POSIX-based operating systems, which will be the base of next-generation automotive Electronic Control Units (ECUs). This paper proposes and discusses possible LET design approaches for these novel systems. Different implementations are then evaluated and compared through the WATERS Challenge automotive application running on a multi-core heterogeneous hardware platform. [ABSTRACT FROM AUTHOR]

The Linux operating system has been employed to execute numerous real-time applications. However, it is limited to support soft real-time systems by two scheduling policies: First-In-First-Out and Round Robin. For real-time systems with critical constraints, the soft real-time support and these scheduling policies are still insufficient. In this work, the Earliest Deadline First scheduling policy, which has been shown in theory to be an optimal one in uniprocessor systems, is introduced as an extension of the Linux kernel. This policy is implemented into the real-time class, without the necessity of defining an additional class. The Linux kernel affords capabilities of a hard real-time operating system by an RT-Preempt patch, enabling the use of Linux to implement hard realtime systems. The integration is compliant with the POSIX real-time and thread standards, ensuring applications portability, employing the CLIBC library. In order to validate the proposed implementation, a set of experiments is conducted, showing that a real-time system that cannot be feasibly scheduled using existing policies, attains feasibility when it is scheduled using the integrated Earliest Deadline First policy [ABSTRACT FROM AUTHOR]

Regular expressions are often ambiguous. We present a novel method based on Brzozowski's derivatives to aid the user in diagnosing ambiguous regular expressions. We introduce a derivative-based finite state transducer to generate parse trees and minimal counter-examples. The transducer can be easily customized to either follow the POSIX or Greedy disambiguation policy and based on a finite set of examples it is possible to examine if there are any differences between POSIX and Greedy. [ABSTRACT FROM AUTHOR]

Two current trends in the real-time and embedded systems are the multiprocessor architectures and the partitioning technology that enables several isolated applications with different criticality levels to share the same computer. This paper presents a real-time platform for multiprocessor and partitioned systems, in which communication requirements are also considered. The paper describes the adaptation of MaRTE OS (a monoprocessor real-time operating system) to the XtratuM hypervisor for the multiprocessor Intel x86 architecture. This adaptation makes two contributions to ease the development process of future mixed-criticality applications: firstly, it integrates the hypervisor technology and the fully partitioned scheduling in a multiprocessor environment, and secondly, it provides the basis to interconnect partitioned and non-partitioned applications via a homogeneous communication subsystem. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The performance of computing devices is increasing day by day, the storage devices are not capable to reach with this benchmark. The compute and storage resources are forming two parts of the shared network. This paper is presenting a storage middleware called HyCache+ to reduce the high bi-section bandwidth of the parallel computing systems. The middleware uses Programmable Operating System (POSIX) interface to the end users to swap the data with the high capacity network attached storage. The system uses a 2-layer scheduling approach. The HyCache+ can be deployed on the IBM Blue Gene / P supercomputers for the performance comparison. [ABSTRACT FROM AUTHOR]

In this paper we present Ariadne , a compiler that extracts parallelism from recursive function calls. Ariadne takes as input C code enhanced with directives for recursive functions and automatically produces code for multi-core architectures. It produces code for the POSIX standard, the OpenMP model and the Cilk programming language, which run on a wide variety of computing systems. Ariadne also produces code for SL, a programming language proposed for the SVP processor and model. This is of special interest, since we can map certain function calls onto SVP, which contain inherent parallelism that cannot efficiently be expressed in other programming models. Ariadne is the only compiler that extracts parallelism from various forms of recursive functions using directives. It is also the only compiler that handles all forms of reduction operations for addition, subtraction, multiplication and division. The experimental results are very promising showing significant speedups in all benchmarks. [ABSTRACT FROM AUTHOR]

One of the fundamental requirements of entertainment applications is interactivity with users. The mobile device such as the smartphone, however, does not guarantee it due to the limit of the application processor's computing power, memory size and available electric power of the battery. This paper proposes a methodology to boost responsiveness of interactive applications by taking advantage of the parallel architecture of mobile devices which, for instance, have dual-core, quad-core or octa-core. To harness the multi-core architecture, it exploits the POSIX thread, a platform-independent thread library to be able to be used in various mobile platforms such as Android, iOS, etc. As a useful application example of the methodology, a heavy matrix calculation function was transformed to a parallelized version which showed around 2.5 ~ 3 times faster than the original version in a real-world usage environment. [ABSTRACT FROM AUTHOR]

Main features of Baget 2.0 and Baget 3.0 Russian real-time operating systems (RTOSs) are discussed. Their similarities and differences are examined. Ways of further development of RTOS Baget are considered. [ABSTRACT FROM AUTHOR]

A number of commercial real-time operating system are available. A real-time operating system (RTOS) supports real-time applications and embedded systems. Real-time applications have the requirement to meet task deadlines in addition to the logical correctness of the results. This paper focuses on pre-requisites for an RTOS to be POSIX compliant and discuss task scheduling in RTOSs. We survey the prominent commercial RTOSs and present a comparison of their scheduling properties. We conclude by discussing the results of the comparison and suggest future research directions in task scheduling in real-time operating systems. [ABSTRACT FROM AUTHOR]

Abstract: Choosing an appropriate cluster file system for a specific high performance computing application is challenging and depends mainly on the specific application I/O needs. There is a wide variety of I/O requirements: Some implementations require reading and writing large datasets, others out-of-core data access, or they have database access requirements. Application access patterns reflect different I/O behavior and can be used for performance testing. This paper presents the programmable I/O benchmarking tool Parabench. It has access patterns as input, which can be adapted to mimic behavior for a rich set of applications. Using this benchmarking tool, composed patterns can be automatically tested and easily compared on different local and cluster file systems. Here we introduce the design of the proposed benchmark, focusing on the Parabench programming language, which was developed for flexible pattern creation. We also demonstrate here an exemplary usage of Parabench and its capabilities to handle the POSIX and MPI-IO interfaces. [ABSTRACT FROM AUTHOR]

Abstract: We present results from the second pilot project in the international Verification Grand Challenge: a formally verified specification of a POSIX-compliant file store using the Z/Eves theorem prover. The project’s overall objective is to build a verified file store for space-flight missions. Our specification of the file store is based on Morgan and Sufrin’s specification of the UNIX filing system; the proof and its mechanisation in Z/Eves are novel. We show how our work contributes towards building a verified software repository: a set of general theories, proof techniques, and experiments reusable across different domains. [Copyright &y& Elsevier]

For pt. 1 see ibid., vol.11, no.2, p.50-56, (2008). This paper provides an explanation of a distributed measurement system based on proprietary software. It describes applications based mainly on free and open source software (FOSS). It is an interesting alternative to proprietary solutions as it offers greater flexibility in software development, better protection of customers' rights, and guaranteed open access to data. FOSS is based on the IEEE standards 1003, also known as POSIX or ISO/IEC 9945. In this paper, it is shown that the same objectives met with proprietary solutions can be achieved with FOSS, if not even better than with proprietary software. [ABSTRACT FROM PUBLISHER]

Abstract: This paper aims to define an interface for the Controller Area Network (CAN) data-link layer that both fits well with the IEEE Std 1003.1 socket paradigm, and allows the user to access the full range of capabilities implemented by CAN interface controllers. At the same time, this paper also attempts to set up a detailed set of specifications and guidelines for the actual implementation of the proposed interface. [Copyright &y& Elsevier]

Abstract: JCilk extends the serial subset of the Java language by importing the fork-join primitives spawn and sync from the Cilk multithreaded language, thereby providing call-return semantics for multithreaded subcomputations. In addition, JCilk transparently integrates Java’s exception handling with multithreading by extending the semantics of Java’s try and catch constructs, but without adding new keywords. This extension is “faithful” in that it obeys Java’s ordinary serial semantics when executed on a single processor. When executed in parallel, however, an exception thrown by a JCilk computation causes its sibling computations to abort, which yields a clean semantics in which the enclosing cilk try block need only handle a single exception. The exception semantics of JCilk allows programs with speculative computations to be programmed easily. Speculation is essential in order to parallelize programs such as branch-and-bound or heuristic search. We show how JCilk’s linguistic mechanisms can be used to program the “queens” puzzle and a parallel alpha–beta search. We have implemented JCilk’s semantic model in a prototype compiler and runtime system, called JCilk-1. The compiler implements continuations in a novel fashion by introducing goto statements into Java. The JCilk-1 runtime system shadows the dynamic hierarchy of cilk try blocks using a “try tree”, allowing the system to chase down side computations that must be aborted. Performance studies indicate that JCilk’s exception mechanism incurs minimal overhead, contributing at most a few percent on top of the cost for a spawn/return. [Copyright &y& Elsevier]

SystemC is committed to support the requirements for an integrated, HW/SW co-design flow, thus allowing the development of complex, multiprocessing, Systems-on Chip (MpSoC). To make this possible, efficient modeling and simulation methodologies for Real-Time, Embedded (RT/E) SW in SystemC have to be developed, so that the designer can verify and refine the application SW together with the rest of the elements of the platform. Accurate modeling of the application SW requires an accurate model of the RTOS. Nevertheless, low-level, dynamic timing characteristics of the RTOS such as time-slicing, priority-based preemptive scheduling, interrupts and exceptions do not have a direct implementation in SystemC. In this paper, techniques are proposed to accurately model the detailed RTOS functionality on top of the SystemC execution kernel. The model allows timed-simulation and refinement of the RT/E SW code in SystemC. The simulation technology has been applied to the development of a high-level, POSIX simulation library in SystemC. The library allows the designer a fast, sufficiently accurate, timed simulation of the application SW running on top of POSIX. As most current RTOSs support this standard, the library is portable to different development frameworks. The library provides the required infrastructure for a complete, multiprocessing, HW/SW co-simulation environment at different abstraction levels using SystemC. [ABSTRACT FROM AUTHOR]

We present a method for the security analysis of realistic models over off-the-shelf systems and their configuration by formal, machine-checked proofs. The presentation follows a large case study based on a formal security analysis of a CVS-Server architecture. The analysis is based on an abstract architecture (enforcing a role-based access control), which is refined to an implementation architecture (based on the usual discretionary access control provided by the POSIX environment). Both architectures serve as a skeleton to formulate access control and confidentiality properties. Both the abstract and the implementation architecture are specified in the language Z. Based on a logical embedding of Z into Isabelle/HOL, we provide formal, machine-checked proofs for consistency properties of the specification, for the correctness of the refinement, and for security properties. [ABSTRACT FROM AUTHOR]

A real-time operating system (RTOS) supports applications that must meet deadlines in addition to providing logically correct results. This paper reviews pre-requisites for an RTOS to be POSIX 1003.1b compliant and discusses memory management and scheduling in RTOS. We survey the prominent commercial and research RTOSs and outline steps in system implementation with an RTOS. We select a popular commercial RTOS within each category of real-time application and discuss its real-time features. A comparison of the commercial RTOSs is also presented. We conclude by discussing the results of the survey and suggest future research directions in the field of RTOS. [ABSTRACT FROM AUTHOR]

Operating systems form a foundation for robust application software, making it important to understand how effective they are at handling exceptional conditions. The Ballista testing system was used to characterize the handling of exceptional input parameter values for up to 233 POSIX functions and system calls on each of 16 widely used operating system (OS) implementations. This identified ways to crash systems with a single call, ways to cause task hangs within OS code, ways to cause abnormal task termination within OS and library code, failures to implement defined POSIX functionality, and failures to report unsuccessful operations. Overall, only 55 percent to 76 percent of the exceptional tests performed generated error codes, depending on the operating system being tested. Approximately 6 percent to 19 percent of tests failed to generate any indication of error despite exceptional inputs. Approximately 1 percent to 3 percent of tests revealed failures to implement defined POSIX functionality for unusual, but specified, situations. Between 18 percent and 33 percent of exceptional tests caused the abnormal termination of an OS system call or library function, and five systems were completely crashed by individual system calls with exceptional parameter values. The most prevalent sources of these robustness failures were illegal pointer values, numeric overflows, and end-of-file overruns. There is significant opportunity for improving exception handling within OS calls and especially within C library functions. However, the role of signals vs. error return codes is both controversial and the source of divergent implementation philosophies, forming a potential barrier to writing portable, robust applications. [ABSTRACT FROM AUTHOR]

The goal of the GUARDS project is to design and develop a generic fault-tolerant computer architecture that can be built from predefined standardised components. The architecture favours the use of commercial off-the-shelf (COTS) hardware and software components. However, the assessment and selection of COTS components is a non-trivial task as it requires balancing a myriad of requirements from end-users and the preliminary architecture design. In this paper, we present the requirements and assessment criteria for a specific COTS software component, the operating system kernel. As an interface specification constitutes a major compatibility criterion for the selection of COTS components in GUARDS, a particular emphasis is placed on operating system conformance to the POSIX 1003.1 standard. We discuss the general lessons learned from the assessment process and raise a number of questions relevant to the assessment of any COTS software component. [ABSTRACT FROM AUTHOR]