Kwok-Bun Yue, Sadegh Davari, Ted Leibfried · 1996
The priority ceiling protocol (PCP) is an effective protocol for minimizing priority inversions in real-time scheduling. Priority inversion occw-s when a high priority task is blocked by a low priority task, such as at a shared semaphore or a protected operation. PCP guarantees the absence of chained priority inversion or deadlock. The ceiling locking (CL) priority on protected objects of Ada-95 also has these properties but has some limitations.
Cited by 8Open access
Zhang Bo-ying · 2007
Priority ceiling protocol is a priority-driven preemptive protocol, it avoids deadlocks and guarantees that any task is blocked at most once. Dang Van Hung and Philip Chan [6] formally specified and verified both properties in [6]. In their proof, the state function HiPripcp is not defined explicitly, which makes the proof details hard to follow. To solve this problem, a new approach is presented to verify the blocked at most once property of this protocol. With duration calculus, we specify the priority ceiling protocol and give a specific definition to HiPripcp. From the specification, we formally verify the properties of this protocol. Our approach relies less on HiPripcp, this makes the proof details easy to follow. Further, this approach can be used to verify the similar properties of protocols of real-time database systems.
Cited by 0
Dániel Kiss · 2011
This paper introduces a modified version of the priority ceiling protocol (PCP) by applying adaptive techniques to approximate the optimal priorities. The proposed algorithm keeps the boundaries of the original PCP algorithm, while it increases the fairness of the scheduling as well as the possibility to use it in dynamically configured systems. Intelligent algorithms occasionally are used in embedded systems due to mostly runtime problems. The proposed algorithm fulfills the requirements of the safety critical systems and can effectively be applied in embedded systems, as well. Furthermore a benchmarking system for scheduling algorithms is introduced, which can advantageously be applied to compare different scheduling algorithms executed with the same configuration. Finally the performance of the modified algorithm versus the original one will be analyzed.
Cited by 4
Bruno Dutertre · 2002
We present a case study in formal specification and tool-assisted verification of real-time schedulers, based on the priority ceiling protocol. Starting from operational specifications of the protocol, we obtain rigorous proofs of both synchronization and timing properties, and we derive a schedulability result for sporadic tasks.
Cited by 29
Lihchyun Shu, Michal Young, Ragunathan Rajkumar · 1994
Cited by 0
D Silambarasan, Ramanatha Venkatesan M · 2016
Cited by 1
Bruno Dutertre · 1999
Common real-time operating systems rely on priority-based, preemptive scheduling. Re-source sharing in such systems potentially leads to priority inversion: processes of high priority can be prevented from entering a critical section and be delayed by processes of lower priority. Since uncontrolled priority inversion can cause high-priority processes to miss their deadlines, a real-time operating system must use resource-sharing mechanisms that limit the effects of priority inversion. The priority ceiling protocol is one such mech-anism. It ensures mutual exclusion and absence of deadlocks, and minimizes the length of priority inversion periods. This paper presents a formal specification and analysis of the protocol using PVS and the rigorous proof of associated schedulability results. Chapter 1
Cited by 0
Bao Zi, Yu Wang · 2005
This paper describes a version of the priority - ceiling protocol. This Protocol prevents deadlock and transitive blocking among jobs. When it is used, a job that never self- suspend is blocked at most once, and the duration of blocking is bounded from above by the maximum execution time of critical sections of lower - priority jobs.
Cited by 0
Michael A. Squadrito · 1996
Concurrency control algorithms that are used in a real-time database must satisfy the timing requirements of the transactions as well as maintain the consistency of the data. Concurrency control techniques vary in the amount of concurrency they allow in a system. As more concurrency is allowed, it is more likely that transactions will meet their timing constraints. In lock-based concurrency control techniques, the problem of deadlock must be addressed. Additionally, if these techniques are used in a real-time system, the problem of priority inversion must be addressed. The priority ceiling protocols prevent deadlock and bound priority inversion in a realtime system. The original protocol was designed to be used with exclusive locking. The read/write priority ceiling protocol was developed later to allow more concurrency in realtime databases that use read/write locking. Since neither protocol uses the semantics of objects, they are not appropriate for use with semantic concurrency con...
Cited by 0
1999
Abstract Common real-time operating systems rely on priority-based, preemptive scheduling. Resource sharing in such systems potentially leads to priority inversion: processes of high priority can be prevented from entering a critical section and be delayed by processes of lower priority. Since uncontrolled priority inversion can cause highpriority processes to miss their deadlines, a real-time operating system must use resource-sharing mechanisms that limit the effects of priority inversion. The priority ceiling protocol is one such mechanism. It ensures mutual exclusion and absence of deadlocks, and minimizes the length of priority inversion periods. This paper presents a formal specification and analysis of the protocol using PVS and the rigorous proof of associated schedulability results. Chapter 1 Introduction Fixed-priority, preemptive scheduling is being increasingly used in real-time safetycritical applications. This approach to real-time scheduling is more flexible than static scheduling, and the runtime behavior of a system is still sufficiently predictable to obtain guarantees that timing constraints are satisfied. Many theoretical results provide such guarantees for different classes of systems, with different assumptions about tasks and deadlines [19, 20, 32, 37]. Subtle issues arise in this context when processes of different priorities are allowed to share resources. Mutual exclusion can cause high-priority tasks to be blocked and delayed by tasks of lower priority. To still obtain guarantees that timing constraints are satisfied, one must ensure that the delays caused by blocking are bounded and that the bounds can be determined statically. Since high-priority tasks are usually the most urgent, it is also important to minimize blocking delays. The priority ceiling protocol is a resource allocation mechanism introduced by Sha et al. [33, 34] that achieves these two objectives. The protocol ensures mutual exclusion, minimizes blocking, prevents deadlocks, and allows a bound on blocking to be computed statically.
Cited by 0
Maroua Gasmi, Olfa Mosbahi, Mohamed Khalgui et al. · 2014
This research paper deals with reconfigurable real-time systems to be adapted to their environment under user requirements. A reconfiguration scenario is a run-time software operation that allows the addition, removal and update of real-time OS tasks which can share resources and should meet corresponding deadlines. We propose a new Reconfigurable Priority Ceiling Protocol (denoted by RPCP) that avoids deadlocks after any reconfiguration scenario and changes the priorities of tasks in order to reduce their response and blocking times, and to meet their deadlines. This protocol requires the use of two virtual processors in order to guarantee the non-interruption of execution during the reconfiguration step. We develop a tool that encodes this protocol which is applied to a case study.
Cited by 5Open access
High-priority Ada Tasks, John B. Goodenough, John B. Goodenough et al. · 1988
The ideas and findings in this report should not be construed as an official DoD position. It is published in the interest of scientific and technical information exchange. FOR THE COMMANDER (signature on file)
Cited by 0
Martin D. Schwarz, Helmut Seidl, Vesal Vojdani et al. · 2011
We consider programs for embedded real-time systems which use priority-driven preemptive scheduling with task priorities adjusted dynamically according to the immediate ceiling priority protocol. For these programs, we provide static analyses for detecting data races between tasks running at different priorities as well as methods to guarantee transactional execution of procedures. Beyond that, we demonstrate how general techniques for value analyses can be adapted to this setting by developing a precise analysis of affine equalities.
Cited by 17
Kam-Yiu Lam, Joseph Kee‐Yin Ng · Journal of Systems Architecture · 2000
Cited by 6
Michael Squadrito, Lisa Cingiser DiPippo, Victor Fay Wolfe · 1996
This paper presents the Affected Set Priority Ceiling (ASPC) concurrency control protocol for real-time object-oriented databases. The protocol is based on a combination of a semantic locking technique and priority ceiling techniques. The paper specifies six criteria for real-time concurrency control: high concurrency, deadlock prevention, predictability, temporal consistency enforcement, logical consistency enforcement, and simplicity. It then demonstrates how previous semantic locking techniques and previous priority ceiling protocols each fail to meet several of these criteria, while the ASPC protocol meets all of them except for active temporal consistency support. An implementation, results from synthetic workload tests, and an analysis based on the six criteria are presented for the ASPC protocol. 1 Introduction Concurrency control techniques for real-time database systems must satisfy more requirements than concurrency control techniques in traditional database systems. Among t...
Cited by 0
Albert M. K. Cheng, Fan Jiang · 2005
Context switching between concurrent tasks is a pure operating system overhead which wastes CPU cycles. This paper describes a technique to reduce the number of context switches which are caused by task synchronization. Our method disallows a higher-priority task to preemptively seize the CPU if it will be blocked by a lower-priority task in the future. This protocol is applicable to real-time systems that use preemptive priority scheduling with binary semaphores to enforce mutual exclusion. We show that this protocol does not affect task completion times and so is especially suitable for synchronization in real-time systems where meeting tasks' timing constraints is more
Cited by 0
Kam-yiu Lam, Joseph Kee-yin Ng · 1999
Priority Ceiling Protocol (PCP) is a well-known resource access protocol for hard real-time systems. However, it has a problem of ceiling blocking which imposes a great hindrance to task scheduling in mixed real-time systems where tasks may have different criticality. In this paper, a new resource access protocol called the Conditional Abortable Priority Ceiling Protocol (CA-PCP) is proposed. It resolves the problem of ceiling blocking by incorporating a conditional abort scheme into the PCP. The new protocol inherits all the desirable properties of the PCP and the Ceiling Abort Protocol (CAP) which is yet another modification of the PCP. In the proposed protocol, a condition is defined to control the abort of a job so that the schedulability of the system will not be affected. Performance study has been done to compare the CA-PCP with the PCP. The results indicate that CA-PCP can significantly improve the performance of a system if the lengths of the abortable critical sections are well chosen. Keywords: Priority Ceiling Protocol, Real-time Scheduling, Task Scheduling 1
Cited by 0
Ricardo J. Santos, Arnaldo S. R. Oliveira, Almeida, Luís · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · 2013
Real-time systems are typically reactive systems implemented with a set of concurrent tasks running on top ofan executive or operating system. Due to concurrent task execution and access to shared resources, it is fundamental thatthe execution of critical regions is performed in a safe way,i.e. controlled by appropriate synchronization primitives (e.g.semaphores). To reduce the sources of unbounded priority inversions the semaphores must be managed by protocols adequate for real-time systems. This paper describes some protocols used for such purposes, namely the Priority Inheritance Protocol (PIP), the Priority Ceiling Protocol (PCP) and the Stack Resource Policy (SRP).Keywords: real-time systems; shared resource access; semaphore management protocols; priority inheritance protocol; priority ceiling protocol; stack resource policy
Cited by 0Open access
Hiroaki Takada, Ken Sakamura · 1994
Making critical sections abortable is a promising approach to reducing priority inversions. To improve the schedulability of a system using abortable critical sections, the maximum number of abortions should be decreased. In this paper, we propose a real-time synchronization protocol named the ceiling abort protocol (CAP) which introduces a new priority-based abort scheme to the priority ceiling protocol. Our proposed protocol can make the maximum number of abortions smaller than with the conventional priority abort scheme. A method to determine an upper bound on the number of abortions under the CAP is presented, and a schedulability analysis of the protocol is illustrated. Some extensions of the CAP are also discussed. 1 Introduction Priority inversion, the state in which a higher priority job is blocked by lower priority jobs due to resource sharing, is a major cause to degrade schedulability in hard real-time systems. Making critical sections abortable is a promising approach to ...
Cited by 0
Theodore Johnson · 1993
In this paper, we present a new approach to synchronization in real-time systems. Existing methods for synchronization in real-time systems are pessimistic, and use blocking to enforce concurrency control. Protocols such as the priority ceiling protocol have been proposed to reduce the priority inversion that occurs when low priority tasks block high priority tasks. However, the priority ceiling protocol still allows a low priority task to block a high priority task, and requires the use of a static-priority scheduler. We propose optimistic synchronization methods as an alternative to pessimistic synchronization methods. Our synchronization algorithms never allow a low priority task to block a high priority task, and can be used with dynamic-priority schedulers. We show how the current research in non-blocking concurrent objects and in low-overhead uniprocessor synchronization can be synthesized to implement low-overhead optimistic synchronization. 1 Introduction The schedul...
Cited by 0