| 1. |
- Pathan, Risat, 1979, et al.
(författare)
-
Temporal Partitioning on Multicore Platform
- 2014
-
Ingår i: European Space Agency, (Special Publication) ESA SP. - 0379-6566. - 9789292212896 ; SP 725
-
Konferensbidrag (refereegranskat)abstract
- This paper addresses the problem of ensuring temporal partitioning according to the ARINC-653 standard for integrating multiple applications on the same multicore platform. To employ temporal partitioning, we propose the design and analysis of a hierarchical scheduling framework (HSF) for multicore platform. In HSF, each application has a server task, which is mapped to one of the physical cores of the multicore platform. The HSF framework is based on scheduling at two-levels: (i) a system-level scheduler for each core schedules the server tasks that are mapped to that core, and (ii) a task-level scheduler for each application schedules the tasks of the application. This paper presents the design and analysis of this two-level HSF that can be used to ensure temporal partitioning and meeting all the deadlines of each application tasks. The effectiveness of our technique is demonstrated using real-world space applications provided by RUAG Space Sweden AB.
|
|
| 2. |
- Fathollah Nejad Asl, Negin, 1982, et al.
(författare)
-
On probabilistic analysis of disagreement in synchronous consensus protocols
- 2014
-
Ingår i: 10th European Dependable Computing Conference, EDCC 2014; Newcastle upon Tyne; United Kingdom; 13 May 2014 through 16 May 2014. - 9781479938032 ; , s. 23-34
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a probabilistic analysis of disagreement for a family of simple synchronous consensus algorithms aimed at solving the 1-of-n selection problem in presence of unrestricted communication failures. In this problem, a set of n nodes are to select one common value among n proposed values. There are two possible outcomes of each node's selection process: decide to select a value or abort. We have disagreement if some nodes select the same value while other nodes decide to abort. Previous research has shown that it is impossible to guarantee agreement among the nodes subjected to an unbounded number of message losses. Our aim is to find decision algorithms for which the probability of disagreement is as low as possible. In this paper, we investigate two different decision criteria, one optimistic and one pessimistic. We assume two communication failure models, symmetric and asymmetric. For symmetric communication failures, we present the closed-form expressions for the probability of disagreement. For asymmetric failures, we analyse the algorithm using a probabilistic model checking tool. Our results show that the choice of decision criterion significantly influences the probability of disagreement for the 1-of-n selection algorithm. The optimistic decision criterion shows a lower probability of disagreement compare to the pessimistic one when the probability of message loss is less than 30% to 70%. On the other hand, the optimistic decision criterion has in general a higher maximum probability of disagreement compared to the pessimistic criterion.
|
|
| 3. |
- Fathollah Nejad Asl, Negin, 1982, et al.
(författare)
-
On reliability analysis of leader election protocols for virtual traffic lights
- 2013
-
Ingår i: Dependable Systems and Networks Workshop (DSN-W), 2013 43rd Annual IEEE/IFIP Conference on. - 2325-6648. - 9781479901814
-
Konferensbidrag (refereegranskat)abstract
- This paper addresses the problem of leader electionin virtual traffic lights. A virtual traffic light (VTL) isa self-organizing traffic control system that allows road vehiclesequipped with vehicle-to-vehicle communication facilities toimplement the function of a traffic light without the supportof a roadside installation. Previous research has shown thatit is impossible to construct a leader election protocol thatguarantees agreement among the participating vehicles in thepresence of massive communication failures. The paper addressesthe problem of calculating the probability of disagreement insituations where a large number of protocol messages are lost dueto communication interference, so-called communication greyouts.To this end, we present a probabilistic analysis of a familyof simple round-based consensus algorithms that solve the 1-of-n selection problem. We propose to use these algorithms forthe core logic of a VTL leader election protocol (LEP). Ouranalysis shows that the probability of disagreement depends on:i) the number of vehicles involved in the leader election, ii) thenumber of rounds of message exchange, iii) the probability ofmessage loss, and iv) the decision criterion used by the LEP. Wepropose an optimistic and a pessimistic decision criteria for theproposed 1-of-n selection algorithms. The analysis encompass twoprobabilistic failure models, one for symmetric communicationfailures and one for asymmetric communication failures.
|
|
| 4. |
- Fathollah Nejad Asl, Negin, 1982, et al.
(författare)
-
On the Probability of Unsafe Disagreement in Group Formation Algorithms for Vehicular Ad Hoc Networks
- 2016
-
Ingår i: Dependable Computing Conference (EDCC), 2015 Eleventh European. ; , s. 256-267
-
Konferensbidrag (refereegranskat)abstract
- We address the problem of group formation in automotive cooperative applications using wireless vehicle-to-vehicle communication. Group formation (GF) is an essential step in bootstrapping self-organizing distributed applications such as virtual traffic lights. We propose a synchronous GF algorithm and investigate its behaviour in the presence of an unbounded number of asymmetric communication failures (receive omissions). Given that GF is an agreement problem, we know from previous research that it is impossible to design a GF algorithm that can guarantee agreement on the group membership in the presence of an unbounded number of messages losses. Thus, under this assumption, disagreement is an unavoidable outcome of a GF algorithm. We consider two types of disagreement(failure modes): safe and unsafe disagreement. To reduce the probability of unsafe disagreement, our algorithm uses a localoracle to estimate the number of nodes that are attempting to participate in the GF process. (Such estimates can be provided by roadside sensors or local sensors in a vehicle such as cameras.)For the proposed algorithm, we show how the probability of unsafe and safe disagreement varies for different system settings as a function of the probability of message loss. We also show how these probabilities vary depending on the correctness of the local oracles. More specifically, our results show that unsafe disagreement occurs only if the local oracles underestimates the number of participating nodes.
|
|
| 5. |
- Fathollah Nejad Asl, Negin, 1982, et al.
(författare)
-
Probabilistic Analysis of a 1-of-n Selection Algorithm using a Moderately Pessimistic Decision Criterion
- 2013
-
Ingår i: Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC. - 1541-0110. - 9780769551302 ; , s. 68-77
-
Konferensbidrag (refereegranskat)abstract
- In this paper we are concerned with the fundamental problem of reaching agreement among a set of distributed processes in presence of an unbounded number of communication failures. We present a probabilistic analysis of a family of synchronous consensus algorithms that aim to solve the 1-ofn selection problem. In this problem, a set of n nodes are to select one common value among a set of n proposed values. There are two possible outcomes of each node's selection process: it can decide either to select a value, or to abort. Agreement implies that all nodes select the same value, or all nodes decide to abort. We know from previous research that it is impossible to guarantee agreement if there is no upper bound on the number of communication failures that can occur. Our aim is to study how the probability of disagreement varies for different decision criteria. The decision criterion consists of the logical expressions that determine whether a process will select a value or decide to abort based on its view of the system state. In this paper we propose and analyse a moderately pessimistic decision criterion. We compared this decision criterion with an optimistic and a pessimistic decision criterion, which we have investigated in our previous work. Our results show that the moderately pessimistic decision criterion for most configurations has a lower maximum probability of disagreement compared with the two other decision criteria. Furthermore, it provides a compromise between the optimistic and the pessimistic approaches since it reduces the probability of disagreement without increasing excessively the probability of agreeing to abort.
|
|
| 6. |
- Gu, Xiaozhe, et al.
(författare)
-
Design and analysis for dual priority scheduling
- 2018
-
Ingår i: Proceedings - 2018 IEEE 21st International Symposium on Real-Time Computing, ISORC 2018. - 9781538658475 ; , s. 164-173
-
Konferensbidrag (refereegranskat)abstract
- This paper considers Dual Priority (DP) scheduling of constrained deadline sporadic tasks on uniprocessor. The initial fixed priority of each job of a task is promoted to a higher priority (called, promoted priority) after a fixed time interval (called, promotion point) relative to the release time of that job. DP scheduling alters the default preemptive behavior of traditional fixed priority (FP) scheduling to efficiently utilize the processor as close as possible to that of the optimal earliest deadline first (EDF) scheduler. In this paper, we address some of the main challenges of DP scheduling including derivation of a sufficient schedulability test, determination of promotion point of each task1. To the best of our knowledge, this test is the first schedulability test for DP scheduling applicable to constrained deadline sporadic tasks. The test is applicable for any given promotion points of the tasks and has pseudo-polynomial time complexity. We also propose two different heuristics to assign the promotion points, and experimental results show that the proposed test achieves performance very close to that of EDF scheduling.
|
|
| 7. |
- Nordlander, Johan, et al.
(författare)
-
Unambiguous Semantics In Automotive Timing Modeling
- 2010
-
Ingår i: Proceedings of the 1st Workshop on Critical Automotive applications: Robustness & Safety (CARS '10) in Conjunction With The 8th European Dependable Computing Conference (EDCC-8), Valencia, Spain, 2010.. - New York, New York, USA : ACM Press. - 9781605589152 ; , s. 39-42
-
Konferensbidrag (refereegranskat)abstract
- This paper shows how the ITEA2 research project TIMMO has chosen to model timing constraints for delays and for synchronization in an unambiguous way. The shown timing model is valid even in systems where jitter and over- and under-sampling appears. These timing constraints can be used to model timing by augmenting both the AUTOSAR and EAST-ADL2 languages. The unambiguous semantics enables the use of timing models for building safety cases and for precise communication between different parties involved in safety-critical automotive applications. © 2010 ACM.
|
|
| 8. |
|
|
| 9. |
- Pathan, Risat, 1979
(författare)
-
Design of an efficient ready queue for earliest-deadline-first (EDF) scheduler
- 2016
-
Ingår i: Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016. - 1530-1591. - 9783981537062 ; , s. 293-296
-
Konferensbidrag (refereegranskat)abstract
- Although dynamic-priority-based EDF algorithm is known to be theoretically optimal for scheduling sporadic real-time tasks on uniprocessor, fixed-priority (FP) scheduling is mostly used in practice. One of the main reasons for FP scheduling being popular in the industry is its efficient implementation: operations on the ready queue can be done in constant time. On the other hand, ready queue of EDF scheduler is generally implemented as a priority queue, for example, using a binary min-heap data structure in which (insertion/deletion) operation cannot be done in constant time. This paper proposes a new design of ready queue for EDF scheduler: a simple data structure for the ready queue and efficient operations to insert and remove task control blocks (TCBs) to and from the ready queue are proposed. Insertion of a TCB of a newly released job (that cannot preempt the currently-executing job) is done in non-constant time. However, insertion of a TCB of a preempted job or the removal of the TCB of job having the highest EDF priority from the ready queue can be done in constant time. Simulation using randomly generated task sets shows that the overhead of managing jobs in our proposed ready queue for EDF scheduler is significantly lower than that of other approaches. We believe that theoretically optimal EDF algorithm implemented based on our proposed ready-queue data structure will make EDF popular in industry.
|
|
| 10. |
|
|
