Supervisory control for real-time scheduling of periodic and sporadic tasks with resource constraints

In the framework of supervisory control of timed discrete event systems, this paper addresses the design problem of a real-time scheduler that meets stringent time constraints of periodic tasks and sporadic tasks which exclusively access shared resources. For this purpose, we present the timed discrete event models of execution of periodic tasks and sporadic tasks and resource access for shared resources. Based on these models, we present the notion of deadlock-free and schedulable languages that contain only deadline-meeting sequences which do not reach deadlock states. In addition, we present the method of systematically computing the largest deadlock-free and schedulable language, and it is also shown that schedulability analysis can be done using this language. We further show that the real-time scheduler achieving the largest deadlock-free and schedulable language is optimal in the sense that there are no other schedulers to achieve schedulable cases more than those achieved by the optimal scheduler.     

Verification of resource controller processes

Shared resources and the processes that control them play a critical role in the functioning of concurrent systems. A shared resource is viewed as an abstract data type consisting of the definition of the resource and the operations on it, with additional synchronization constraints. Here we present a technique for verifying resource controllers using the formalism of temporal logic. Properties of the operations on a given shared resource are first verified. This is followed by the verification of invariant and liveness properties of the controller. The technique is illustrated by its application to resource controller tasks in Ada. As a prerequisite for accomplishing this, we specify the semantics of Ada tasking primitives.     

Specification and Proof Techniques for Serializers

This paper presents a specification language, implementation mechanism, and proof techniques for problems involving the arbitration of concurrent requests to shared protected resources whose integrity must be preserved. This mechanism is the serializer, which may be described as a kind of protection mechanism, in that it prevents improper orders of access to a protected resource. Serializers are a more structured form of the monitor mechanism of Brinch Hansen and Hoare.     

Decentralized semaphore support in a virtual shared-memory system

Distributed shared memory has increasingly become a desirable programming model on which to program multicomputer systems. Such systems strike a balance between the performance attainable in distributed-memory multiprocessors and the ease of programming on shared-memory systems. In shared-memory systems, concurrent tasks communicate through shared variables, and synchronization of access to shared data is an important issue. Semaphores have been traditionally used to provide this synchronization. In this paper we propose a decentralized scheme to support semaphores in a virtual shared-memory system. Our method of grouping semaphores into semaphore pages and caching a semaphore at a processor on demand eliminates the reliability problems and bottlenecks associated with centralized schemes. We compare the performance of our scheme with a centralized implementation of semaphores and conclude that our system performs better under high semaphore access rates as well as larger numbers of processors.     

Deadlock prevention in concurrent real-time systems

To meet consistency requirements found in concurrent applications, a process must be guaranteed that it will be able to use all resources in a set ofpassive resources (such as shared data structures). To provide predictable execution time required in real-time systems, a process also needs guaranteed access to at least one of a set ofactive resources (such as processors) associated with each passive resource. As such, a concurrent real-time-process has AND-OR resource requirements. If locking is used to provide exclusive access to resources, deadlock is possible since processes can request additional resources while holding other resources. Deadlock detection and recovery techniques and deadlock avoidance techniques typically involve preempting resources or terminating processes, and are therefore inappropriate for real-time systems that require the execution time of processes to be predictable. This paper describes a general resource request condition that we proveprevents deadlock in AND-OR systems. It also describes how we use this AND-OR deadlock prevention technique in a concurrent real-time system.This work is supported in part by the following grants: ONR N000014-89-J-1131 and ARO DAAG-29-84-k-0061.     

A minimal property for characterizing deadlock-free programs

A fundamental issue in the development of concurrent programs is the resource allocation problem. Roughly speaking, it consists of providing some mechanism to avoid race conditions in the access of shared resources by two or more concurrent processes. For such a task, maybe the most widely mechanism consists of using critical sections.Unfortunately, it is also widely-known that programs which use several critical sections may suffer from deadlocks. In this paper, we identify a program property, namely, being stopper-free, which can be used to know if programs are deadlock-free. Indeed, since we have proved that programs are deadlock-free if and only if they do not have any stopper, thus looking for a stopper is equivalent to identifying a situation where a program may suffer a deadlock.     

Processes, Tasks, and Monitors: A Comparative Study of Concurrent Programming Primitives

Three notations for concurrent programming are compared, namely CSP, Ada, and monitors. CSP is an experimental language for exploring structuring concepts in concurrent programming. Ada is a general-purpose language with concurrent programming facilities. Monitors are a construct for managing access by concurrent processes to shared resources. We start by comparing "lower-level" communication, synchronization, and nondeterminism in CSP and Ada and then examine "higher-level" module interface properties of Ada tasks and monitors.     

Cache-Based Synchronization in Shared Memory Multiprocessors

In shared memory multiprocessors, efficient synchronization is imperative to assure good performance. There are two aspects to the “cost” of a synchronization operation: the first is the waiting time at synchronization points, and the second is the intrinsic overhead in performing the operation. The overhead has two components. The first component deals with contention resolution for synchronization operation among competing processors. The second component deals with the shared data accesses that the processor has to perform once it enters a synchronization region. We present a mechanism to reduce the overhead of performing synchronization operations in a cache-based shared memory multiprocessor. The mechanism is based on the intuitive notion that parallel programs invariably use synchronization operations to govern the access to shared data. Traditional multiprocessor cache protocols treat synchronization accesses the same way as normal read/write memory accesses, leading to inefficiencies in performing synchronization operations which ultimately limit the scalability of such systems. The key idea in our approach is to combine synchronization with the coherence maintenance for the cached data. Each cache line maintains states for synchronization as well as for cache coherence, and the cache protocol ensures the correctness of the synchronization operations and the coherence of the data at these synchronization points. To assess the performance gain due to the proposed mechanism, simulation studies are performed using a workload model that represents a dynamic scheduling paradigm which forms the core of several parallel programs. Results from simulation studies show that the proposed cache-based synchronization performs significantly better than traditional cache coherence approaches.     

数据库并发事务的控制

现代数据库作为多用户共享访问的资源,在各种事务的并发操作中,数据库系统和应用程序框架如何保证数据的一致性和正确性是一个不可回避的问题。本文结合实际编程对数据库并发事务的处置原理和机制进行探讨。     

Linux同步机制研究

在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上,更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。同步通常是为了达到多线程协同的目的而设计的一种机制。在Linux内核中有相应的技术实现,包括原子操作、信号量、读写信号量、自旋锁和等待队列。     

Resource sharing among real-time components under multiprocessor clustered scheduling

In this paper we propose a general synchronization protocol for resource sharing among independently-developed real-time applications (components) on multi-core platforms. This protocol is a generalization of a previously proposed synchronization protocol (MSOS). In our proposed protocol, each component is statically allocated on a dedicated subset of processors (called cluster). A component has its own internal scheduler by which its tasks are scheduled. In this paper we focus on multiprocessor global fixed-priority preemptive scheduling algorithms to be used to schedule the tasks inside each component. Sharing the local resources is handled by the Priority Inheritance Protocol (PIP). For sharing the global resources (inter-component resource sharing) we have studied usage of FIFO and Round-Robin queues for access the resources across the components and usage of FIFO and prioritized queues inside the components. We have derived schedulability analysis for the different queue handling alternatives and compared their performance by using experimental evaluations. Finally, we have shown that the integration phase can be formulated in the form of a nonlinear integer programming problem where solution techniques in this domain can be used to minimize the total number of processors required to guarantee the schedulability of all components. As a proof of concept we have only provided the formulation for FIFO queues.     

Software transactional memories: an approach for multicore programming

The recent advance of multicore architectures and the deployment of multiprocessors as the mainstream computing platforms have given rise to a new concurrent programming impetus. Software transactional memories (STM) are one of the most promising approaches to take up this challenge. The aim of a STM system is to discharge the application programmer from the management of synchronization when he/she has to write multiprocess programs. His/her task is to decompose his/her program into a set of sequential tasks that access shared objects, and to decompose each task in atomic units of computation. The management of the required synchronization is ensured by the associated STM system. This paper presents two existing STM systems, and a new one based on time-window mechanism. The paper, which focuses mainly on STM principles, has an introductory and survey flavor.     

A Calculus and logic of resources and processes

Recent advances in logics for reasoning about resources provide a new approach to compositional reasoning in interacting systems. We present a calculus of resources and processes, based on a development of Milner’s synchronous calculus of communication systems, SCCS, that uses an explicit model of resource. Our calculus models the co-evolution of resources and processes with synchronization constrained by the availability of resources. We provide a logical characterization, analogous to Hennessy–Milner logic’s characterization of bisimulation in CCS, of bisimulation between resource processes which is compositional in the concurrent and local structure of systems. An erratum to this article can be found at     

<Emphasis FontCategory="NonProportional">rt-muse</Emphasis>: measuring real-time characteristics of execution platforms

Operating systems code is often developed according to principles like simplicity, low overhead, and low memory footprint. Schedulers are no exceptions. A scheduler is usually developed with flexibility in mind, and this restricts the ability to provide real-time guarantees. Moreover, even when schedulers can provide real-time guarantees, it is unlikely that these guarantees are properly quantified using theoretical analysis that carries on to the implementation. To be able to analyze the guarantees offered by operating systems’ schedulers, we developed a publicly available tool that analyzes timing properties extracted from the execution of a set of threads and computes the lower and upper bounds to the supply function offered by the execution platform, together with information about migrations and statistics on execution times. rt-muse evaluates the impact of many application and platform characteristics including the scheduling algorithm, the amount of available resources, the usage of shared resources, and the memory access overhead. Using rt-muse, we show the impact of Linux scheduling classes, shared data and application parallelism, on the delivered computing capacity. The tool provides useful insights on the runtime behavior of the applications and scheduler. In the reported experiments, rt-muse detected some issues arising with the real-time Linux scheduler: despite having available cores, Linux does not migrate SCHED_RR threads which are enqueued behind SCHED_FIFO threads with the same priority.     

基于经济模型的资源代理

网格计算是为解决大规模资源密集型问题而提出的新一代计算平台,是当前并行和分布处理技术的一个发展方向,而资源管理是计算网格的关键技术之一。对各种各样可利用资源的整合和管理是网格应用的基础,而资源的分布性、动态性、异构性、自治性和需要协调一致性使得网格资源的管理调度成为一个棘手的问题。目前基于市场的经济资源管理和调度算法非常适合计算网格中的资源管理问题,但有调度价格不能更改、负载平衡等问题。文中提出了“网格环境下基于经济模型的资源代理”,依靠多维QoS指导的调度策略和经济模型的启发式调节资源价格,改进和优化计算网格资源的分配。     

Time-predictable synchronization support with a shared scratchpad memory

Multicore processors need to communicate when working on shared tasks. In classical systems, this is performed via shared objects protected by locks, which are implemented with atomic operations on the main memory. However, access to shared main memory is already a bottleneck for multicore processors. Furthermore, the access time to a shared memory is often hard to predict and therefore problematic for real-time systems.This paper presents a shared on-chip memory that is used for communication and supports atomic operations to implement locks. Access to the shared memory is arbitrated with time division multiplexing, providing time-predictable access. The shared memory supports extended time slots so that a processor can execute more than one memory operation atomically. This allows for the implementation of locking and other synchronization primitives.We evaluate this shared scratchpad memory with synchronization support on a 9-core version of the T-CREST multicore platform. Worst-case access latency to the shared scratchpad is 13 clock cycles. Access to the atomic section under full contention, when every processor core wants access to acquire a lock, is 135 clock cycles.     

An efficient grid scheduling strategy for data parallel applications

Scheduling large-scale application in heterogeneous grid systems is a fundamental NP-complete problem that is critical to obtain good performance and execution cost. To achieve high performance in a grid system it requires effective task partitioning, resource management and load balancing. The heterogeneous and dynamic nature of a grid, as well as the diverse demands of applications running on the grid, makes grid scheduling a major task. Existing schedulers in wide-area heterogeneous systems require a large amount of information about the application and the grid environment to produce reasonable schedules. However, this required information may not be available, may be too expensive to collect, or may increase the runtime overhead of the scheduler such that the scheduler is rendered ineffective. We believe that no one scheduler is appropriate for all grid systems and applications. This is because while data parallel applications in which further data partitioning is possible can be further improved by efficient management of resources, smart selection of resources and load balancing can be possible, in functional/not-dividable-task parallel applications such partitioning is either not possible or difficult or expensive in term of performance. In this paper, we propose a scheduler for data parallel applications (SDPA) which offers an efficient task partitioning and load balancing strategy for data parallel applications in grid environment. The proposed SDPA offers two major features: maintaining job priority even if insufficient number of free resources is available and pre-task assignment to cut the idle time of nodes. The SDPA selects nodes smartly according to the nature of task and the nodes’ resources availability. Simulation results conducted reveal that SDPA achieves performance improvement over reported strategies in the reviewed literature in terms of execution time, throughput and waiting time.     

Client-side straggler-aware I/O scheduler for object-based parallel file systems

Object-based parallel file systems have emerged as promising storage solutions for high-performance computing (HPC) systems. Despite the fact that object storage provides a flexible interface, scheduling highly concurrent I/O requests that access a large number of objects still remains as a challenging problem, especially in the case when stragglers (storage servers that are significantly slower than others) exist in the system. An efficient I/O scheduler needs to avoid possible stragglers to achieve low latency and high throughput. In this paper, we introduce a log-assisted straggler-aware I/O scheduling to mitigate the impact of storage server stragglers. The contribution of this study is threefold. First, we introduce a client-side, log-assisted, straggler-aware I/O scheduler architecture to tackle the storage straggler issue in HPC systems. Second, we present three scheduling algorithms that can make efficient decision for scheduling I/Os while avoiding stragglers based on such an architecture. Third, we evaluate the proposed I/O scheduler using simulations, and the simulation results have confirmed the promise of the newly introduced straggler-aware I/O scheduler.     

基于P2P的制造资源搜索引擎的研究与实现

资源共享是网格技术追求的目标之一,基于中心服务器的集中式系统虽然具有易控制、维护方便等优点,但同时带来了很多问题,如中心服务器会成为整个系统的瓶颈、通信效率较低、检索资源的范围仅仅局限于资源的提供者等。P2P中对等点（Peer）之间通过直接互连,实现动态共享资源。本文结合P2P的网络特点,构建了一个面向制造业的资源共享平台——制造资源搜索引擎（Manufacturing Resource Search Engine,MRSE）,对其中的关键技术进行了研究、提出了基于XML的资源搜索策略,给出了XML的两种同步机制,并且在快速原型制造网格中实现了制造资源搜索引擎。     

协同环境中基于RBAC模型的访问控制策略

协同系统具有动态性和群体性的特点,其权限管理比传统软件系统复杂。传统数据库系统中的访问控制机制比较简单,远不能满足协同系统的要求。针对共享资源访问控制策略的授权方式复杂、授权粒度不细致的问题,引入角色机制,把角色访问并发控制策略应用到系统中,设计基于角色的系统功能权限的位映射算法。该算法降低了授权管理的复杂性,增强了系统安全性。