In distributed real-time applications, the static 2 Phase Locking with High priority (S2PL-HP) protocol may resolve data conflict(s) among transactions executing concurrently. S2PL-HP is virtuously free from the prior...
详细信息
In distributed real-time applications, the static 2 Phase Locking with High priority (S2PL-HP) protocol may resolve data conflict(s) among transactions executing concurrently. S2PL-HP is virtuously free from the priority inversion that may arise due to executing-executing conflict-both the transactions in the execution phase. However, its performance may degrade because of other problems, i.e., cyclic restart and unnecessary abort, starvation of transactions of longer length, and system resource wastage. We propose a new priority inheritance (PRIN) centered locking protocol to resolve the above problems. PRIN checks the wastage of system resources by preventing cyclic restart and unnecessary abort using the priority inheritance approach. It is also free from deadlock and reduces the effects of lengthy transaction starvation. The system performance is measured using the transaction miss percentage metric. We developed the simulator to assess the performance of the proposed protocol;the results confirm that our system, PRIN, achieves 1.05 x-1.23 x performance improvement over the state-of-the-art systems.
This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method to make it applicable to more general environme...
详细信息
This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method to make it applicable to more general environments. PIBT is an effective algorithm that introduces a priority to each agent, and at each timestep, the agents, in descending order of priority, decide their next neighboring locations in the next timestep through communications only with the local agents. Unfortunately, PIBT is only applicable to environments that are modeled as a bi-connected area, and if it contains dead-ends, such as tree-shaped paths, PIBT may cause deadlocks. However, in the real-world environment, there are many dead-end paths to locations such as the shelves where materials are stored as well as loading/unloading locations to transportation trucks. Our proposed method enables MAPD tasks to be performed in environments with some tree-shaped paths without deadlock while preserving the PIBT feature; it does this by allowing the agents to have temporary priorities and restricting agents’ movements in the trees. First, we demonstrate that agents can always reach their delivery location without deadlock. Our experiments indicate that the proposed method is very efficient, even in environments where PIBT is not applicable, by comparing them with those obtained using the well-known token passing method as a baseline.
High priority two phase locking (HP2PL) concurrency control algorithm can be used for accessing of data items to resolve conflicts amongst the concurrently executing transactions. Inclusion of priority inversion and d...
详细信息
ISBN:
(纸本)9783319723440;9783319723433
High priority two phase locking (HP2PL) concurrency control algorithm can be used for accessing of data items to resolve conflicts amongst the concurrently executing transactions. Inclusion of priority inversion and data inaccessibility are the most undesirable problems in transactions' execution which seriously affect the system performance. Previously developed protocols for resolving such issues put a lot of messages and time overhead which is not desirable. In distributed real-time database system (DRTDBS), basic aim is to minimize the number of transactions missing their deadline. This can be achieved by minimizing commit time. In this paper, A One Phase priority inheritance Commit Protocol (OPPIC) has been proposed specifically reducing one round of message transfer among coordinator and participating cohorts' sites in case of priority inversion problem at any of the cohort of low priority transaction. Focus of this protocol is to minimize the priority inversion duration that in turn minimizes commit time. A distributed database system is simulated for measuring the performance of this protocol with 2PC and PIC protocols. The results confirm the significant improvement in system performance with the OPPIC protocol.
Scheduling and synchronization algorithms for uniprocessor real-time systems benefit from the rich theory of schedulability analysis, and yet translating these algorithms to practical implementations can be challengin...
详细信息
ISBN:
(纸本)9783319478463;9783319478456
Scheduling and synchronization algorithms for uniprocessor real-time systems benefit from the rich theory of schedulability analysis, and yet translating these algorithms to practical implementations can be challenging. This paper presents a Java model of the priority inheritance protocol for mutual exclusion, as implemented in the RTEMS open-source real-time operating system. We verified this model using Java Pathfinder to detect potential data races, deadlocks, and priority inversions. JPF detected a known bug in the RTEMS implementation, which we modified along with the Java model. Verification of the modified model showed the absence of data races, deadlocks, and established nine protocol-specific correctness properties.
In distributed real-time database system, utilizing a priority inheritance mechanism may help in reducing the priority inversion duration of a conflicting (and waiting) high priority transaction. However, mere integra...
详细信息
In distributed real-time database system, utilizing a priority inheritance mechanism may help in reducing the priority inversion duration of a conflicting (and waiting) high priority transaction. However, mere integration of the priority inheritance scheme with classic 2PC is not enough and may lead to performance degradation. The two main problems that arise because of such integration are considerably longer 'priority-Inherit' message dissemination time and extra message overhead. In addition, the explosion of priority inheritance events in the system might lead to the increased miss percentage for high-priority transactions. To address the above-mentioned problems, a Sophisticated Time and message utilization centered priority inheritance (STEP) concomitant protocol is designed which brings down the overhead (time & message) by simply requiring of single round intelligent message transfer and eliminates priority de-boosting part of the general priority inheritance mechanism. Moreover, it also keeps a check on the no. of priority inheritance events occurrences with the help of real-time monitoring of priority inversions' percentage in the system and thereby makes sure that high priority transaction miss percentage does not increase in an uncontrolled manner. The extensive performance study suggests that STEP protocol performs considerably well compared to the existing state-of-the-art protocols.
A write transaction intending to access data already accessed by the group of transactions in read mode may starve. The situation may even become worse with the simultaneous occurrence of the priority inversion if the...
详细信息
A write transaction intending to access data already accessed by the group of transactions in read mode may starve. The situation may even become worse with the simultaneous occurrence of the priority inversion if the priority level of the requesting write transaction is higher than that of the highest priority lock holding read transaction from the group of transactions currently holding the conflicting data in read mode. A Reads-write Avoid starvation and priority Inversion period Declined (RAPID) commit protocol has been proposed that efficiently resolves the above problem by declining the priority inversion duration optimistically through lessening the number of reader transactions either requested or currently holding the conflicting data item in read mode by aborting some of them (if possible). The simulation results show that the RAPID outperforms 2PC and PIC protocol. (C) 2020 The Authors. Published by Elsevier B.V. on behalf of King Saud University.
RT-Linux is a kind of embedded Linux, its real time performance is relative high among numerous kind of embedded Linux, but it requires the operation system have high real time performance and using priority inheritan...
详细信息
ISBN:
(纸本)9780769549323;9781467356527
RT-Linux is a kind of embedded Linux, its real time performance is relative high among numerous kind of embedded Linux, but it requires the operation system have high real time performance and using priority inheritance protocol to solve the priority reverse problem in RT-Linux. In order to trace the system roundly, a kernel trace tool is designed, and used this tool to test the improvement. The test results show that the work eliminated the priority reverse problem, and advanced the real time performance of RT-Linux.
The two-phase locking with high priority (2PL-HP) protocol is a broadly used concurrency control protocol as it better handles the priority inversion problem. However, its performance might get degraded due to the inc...
详细信息
The two-phase locking with high priority (2PL-HP) protocol is a broadly used concurrency control protocol as it better handles the priority inversion problem. However, its performance might get degraded due to the inclusion of cyclic restart, deadlock, unnecessary abort, pseudo-priority inversion, and starvation. To overcome the above problems, this paper proposes a Reduction of long transactions starvation effect, Avoidance of deadlock and pseudo-priority inversion, and Conditional-restart for an Efficient resource utilization (RACE) concurrency control protocol. The RACE specifically aims at reducing the transaction miss percent by eliminating the following problems-deadlock through dividing the execution stage in the locking phase and processing phase, the cyclic restart through prejudging its occurrence, and the pseudo-priority inversion that may occur with an intermediate lock holder low priority cohort. Moreover, it reduces unnecessary transaction aborts through the utilization of the priority inheritance method and saves long transactions from being starved to some extent by ensuring fair chances of their completion. Simulation results confirm up to 11% improvement in transactions miss percent and up to 38% reduction in transactions' rollbacks in RACE protocol over 2PL-HP and extended 2PL-HP.
In this paper, a mechanism is presented for reducing priority inversion in multiprogrammed computing systems. Contrary to well-known approaches from the literature, this paper tackles cases where the dependency relati...
详细信息
In this paper, a mechanism is presented for reducing priority inversion in multiprogrammed computing systems. Contrary to well-known approaches from the literature, this paper tackles cases where the dependency relationships among tasks cannot be known in advance to the operating system. The presented mechanism allows tasks to explicitly declare aforementioned relationships, enabling the operating system scheduler to take advantage of such information and trigger priority inheritance, resulting in reduced priority inversion. We present the prototype implementation of the concept within the Linux kernel in the form of modifications to the standard Portable Operating System Interface (POSIX) condition variable code, along with an extensive evaluation, including a quantitative assessment of the benefits for applications making use of the technique and comprehensive overhead measurements. In addition, we present an associated technique for the theoretical schedulability analysis of a system using the new mechanism, which is useful to determine whether all tasks can meet their deadlines or not, in the specific scenario of tasks interacting only through remote procedure calls and under partitioned scheduling.
The primary(1) performance objective in distributed real-time database systems (DRTDBS) is to minimize the number of transactions missing their deadlines. Demanding nature of this objective makes traditional approache...
详细信息
ISBN:
(纸本)9781450363419
The primary(1) performance objective in distributed real-time database systems (DRTDBS) is to minimize the number of transactions missing their deadlines. Demanding nature of this objective makes traditional approaches and even existing approaches inadequate. The past researches have been mostly devoted to outspreading traditional transaction processing methods to resolve the issues. However, for the design of DRTDBS, new policies/protocols must be designed to resourcefully handle the concurrent execution of transactions. Our aim is to develop new concurrency control protocols, commit protocols and to compare their performance with existing protocols. Another plan is to extend our work to nested transaction model, replication environment and possibly mobile environment.
暂无评论