Real-Time Systems - Chapter 5: Resource access control protocols

Nội dung text: Real-Time Systems - Chapter 5: Resource access control protocols

1. REAL-TIME SYSTEMS Chapter 5: Resource access control protocols Computer Science Program
2. Main contents • Definitions of resources • Resource access control: – Non-preemptable critical sections – Basic priority inheritance protocol – Basic priority ceiling protocol – Stack-based priority ceiling protocol Real-time systems (c) Cuong Pham-Quoc 2
3. Fundamentals • Additional resources, along with processors, required for jobs to be executed – So far, we ignores resources for scheduling processors • Resources may represent: – Hardware devices such as sensors and actuators – Disk or memory capacity, buffer space – Software resources: mutexes, locks, queues, etc. • This chapter discusses: – How resource contention affects the execution behavior and schedulability of jobs – How various resource access-control protocols work to reduce the undesirable effect of resource contention – How well these protocols succeed in achieving this goal Real-time systems (c) Cuong Pham-Quoc 3
4. Definitions and notations • Assume a system with ρ types of resource named R1, R2, , Rρ – Each resource Ri comprises viindistinguishable units • Resources with a (practically) infinite number of units have no effect on scheduling; and so are ignored – Each unit of resource is used in a non-preemptable and mutually exclusive manner; resources are serially reusable • E.g., when a unit of a resource Ri is granted to a job, this unit is no longer available to other jobs until the job frees the unit – If a resource can be used by more than one job at a time, we model that resource as having many units, each used mutually exclusively Real-time systems (c) Cuong Pham-Quoc 4
5. Locks • Assume a lock-based concurrency control mechanism – A job wanting to use nk units of resource Rk, it executes a lock, denoted L(Rk, nk), to request the resource • L(Rk) if nk = 1 – When the job is finished with the resources, it unlocks them, denoted U(Rk, nk) • U(Rk) if nk = 1 – If a lock request fails, the requesting job is blocked and loses the processor; when the requested resource becomes available, it is unblocked • A job holding a lock cannot be preempted by a higher priority job needing that lock • Resources are released in the last-in-first-out order Real-time systems (c) Cuong Pham-Quoc 5
6. Critical sections • The segment of a job that begins at a lock and ends at a matching unlock is a critical section – Use the expression [R, n; e] to represent a critical section regarding n units ofR, with the critical section requiring e units of execution time – Critical sections may nest if a job needs multiple simultaneous resources J3 : [R1; 14[R4,3; 9[R5,4; 3]]] Real-time systems (c) Cuong Pham-Quoc 6
7. Conflict and blocking • Two jobs conflict with one another if some of the resources they require are of the same type – They contend for a resource if one job requests a resource that the other job has already been granted • When the scheduler does not grant nk units of resource Rk to the job requesting them, the lock request L(Rk, nk) of the job fails (or is denied) – The job is blocked and loses the processor – The job is unblocked when the scheduler grants it nk units of resource Rk Real-time systems (c) Cuong Pham-Quoc 7
8. Example • Consider three jobs (ri, di, ei) scheduled by EDF, assume that there is only one resource R: – J1 = (6,14,5); J2 = (2,17,7); and J3 = (0,18,6) – Critical sections: J1 = [R; 2]; J2 = [R; 4]; and J3 = [R; 4] – Locks: • J1: L(R) at 8 • J2: L(R) at 4 • J3: L(R) at 1 Real-time systems (c) Cuong Pham-Quoc 8
9. Resource access control • A resource access-control protocol, or simply an access-control protocol, is a set of rules that govern: – when and under what conditions each request for resource is granted and – how jobs requiring resources are scheduled. • More detail the undesirable effects of resource contention – Priority inversion – Deadlock – Time anomalies Real-time systems (c) Cuong Pham-Quoc 9
10. Priority inversion • Priority inversion occurs when a low-priority job executes while some ready higher-priority job waits Real-time systems (c) Cuong Pham-Quoc 10
11. Time anomalies • Consider the previous three jobs but the critical section of J3 is changed to J3 = [R; 2.5] – Shortened by 1.5 – Expected all jobs should complete sooner Real-time systems (c) Cuong Pham-Quoc 11
12. Deadlock • Deadlock can result from piecemeal acquisition of resources; classic example of two jobs needing resources RX and RY Real-time systems (c) Cuong Pham-Quoc 12
13. Additional terminologies • A higher-priority job Jh is said to be directly blocked by a lower- priority job Jl when Jl holds some resource whichJh requests and is not allocated • Wait-for-graph – A cyclic path indicates a deadlock – A path from higher job to lower priority job is a directed block Resource & units Wait-for-edge ownership-edge Real-time systems (c) Cuong Pham-Quoc 13
14. Notations • A periodic task Ti has a critical section [R, x; y] if every job in Ti requires at most x unit of R for y units of time • Denote: Ti = (ϕi, pi, ei, Di; [R, x; y]) – T1 = (50,30; [R3; 10[R2; 5]] – T2 = (100,20; [R2; 7[R3; 2]][R3; 3]) • Parameters are not relevant: Ti = (ϕi, pi, ei, Di, ci) – ci: maximum critical section Real-time systems (c) Cuong Pham-Quoc 14
15. Resource access control protocols • Non-preemptable Critical Sections - NPCS • Priority inheritance protocol • Basic priority ceiling protocol • Stack-based priority ceiling protocol Real-time systems (c) Cuong Pham-Quoc 15
16. NON-PREEMPTABLE CRITICAL SECTIONS Real-time systems (c) Cuong Pham-Quoc
17. Non-preemptable critical sections • Simplest resource access control protocol: – When a jobs acquires a resource it is scheduled with highest priority in a non- preemptable manner – Deadlock can never occur • Advantage: – Simplicity – Can be used for both fixed and dynamic priority • Disadvantage: – Every job can be blocked by every lower-priority job with a critical section, even if there is no resource conflict; very poor timing performance • Blocking time of Ti due to resource conflict in a n−periodic task system: – bi(rc) = max (ck) i+1≤k≤n – Tasks are indexed in order of nonincreasing priority Real-time systems (c) Cuong Pham-Quoc 17
18. NPCS, b1(rc) = 5 Uncontrolled - Priority inversion Real-timesystems Pham-Quoc Cuong (c) 18
19. PRIORITY INHERITANCE PROTOCOL Real-time systems (c) Cuong Pham-Quoc
20. Basic priority inheritance protocol • Aim: to adjust the scheduling priorities of jobs during resource access, to reduce the duration of timing anomalies • Constraints: – Works with any pre-emptive, priority-driven scheduling algorithm – Does not require any prior knowledge of the jobs’ resource requirements – Does not prevent deadlock, but if some other mechanism used to prevent deadlock, ensures that no job can block indefinitely due to uncontrolled priority inversion • We discuss the basic priority-inheritance protocol which assumes there is only 1 unit of resource Real-time systems (c) Cuong Pham-Quoc 20
21. Basic priority inheritance protocol • Assumptions (for all of the following protocols): – Each resource has only 1 unit – The priority assigned to a job according to a standard scheduling algorithm is its assigned priority – At any time t, each ready job Jk is scheduled and executes at its current priority, πk(t), which may differ from its assigned priority and may vary with time • The current priority πl(t) of a job Jl may be raised to the higher priority πh(t) of another job Jh • In such a situation, the lower-priority job Jl is said to inherit the priority of the higher-priority job Jh, and Jl executes at its inherited priority πh(t) Real-time systems (c) Cuong Pham-Quoc 21
22. Rules of Basic priority inheritance protocol 1. Scheduling Rule: – Ready jobs are scheduled on the processor preemptively in a priority-driven manner according to their current priorities – At its release time t, the current priority π(t) of every job J is equal to its assigned priority – The job remains at this priority except under the condition stated in rule 3 2. Allocation Rule: When a job J requests a resource R at time t, – if R is free, R is allocated to J until J releases the resource, and – if R is not free, the request is denied and J is blocked. 3. Priority-Inheritance Rule: – When the requesting job J becomes blocked, the job Jl which blocks J inherits the current priority π(t) of J – The job Jl executes at its inherited priority π(t) until it releases R; at that time, the priority of Jl returns to its priority πl(t) at the time t when it acquires the resource R Real-time systems (c) Cuong Pham-Quoc 22
23. Example • Consider three jobs (ri, di, ei) scheduled by EDF, assume that there is only one resource R: – J1 = (2,14,5); J2 = (5,17,5); and J3 = (0,18,7) – Critical sections: J1 = [R; 2]; J2 = [R; 0]; and J3 = [R; 5] – Locks: • J1: L(R) at 3 • J3: L(R) at 1 • Already discussed with – Uncontrolled – NPCS Real-time systems (c) Cuong Pham-Quoc 23
24. Uncontrolled - Priority inversion Non-Preemptable Critical Sections Real-time systems (c) Cuong Pham-Quoc 24 Basic priority inheritance protocol Basic priority inheritance
25. Complex example • Consider jobs as shown in the table Job ri ei Priority J1 7 3 1 [R1; 1] J2 5 3 2 [R2; 1] J3 4 2 3 J4 2 6 4 [R1; 4 [R2; 1.5]] J5 0 6 5 [R2; 4] • Jobs J1, J2, J4, and J5 attempt to lock their first resource after one unit of execution; J4 accesses R2 after an additional 2 units of execution Real-time systems (c) Cuong Pham-Quoc 25
26. Real-time systems (c) Cuong Pham-Quoc 26
27. Basic priority inheritance protocol • Properties of the Priority-inheritance Protocol – Simple to implement, does not require prior knowledge of resource requirements – Jobs exhibit different types of blocking • Direct blocking due to resource locks • Priority-inheritance blocking • Transitive blocking – Deadlock is not prevented • Although it can be prevented by using additional protocols in parallel – Can reduce blocking time compared to non-preemptable critical sections, but does not guarantee to minimize blocking Real-time systems (c) Cuong Pham-Quoc 27
28. BASIC PRIORITY CEILING PROTOCOL Real-time systems (c) Cuong Pham-Quoc
29. Basic priority ceiling protocol • The priority-ceiling protocol extends the priority-inheritance protocol to prevent deadlocks and to further reduce the blocking time • Key assumptions: – The assigned priorities of all jobs are fixed (e.g. RM scheduling, not EDF) – The resources required by all jobs are known a priori • Need two additional terms to define the protocol: – The priority ceiling of any resource Rk is the highest priority of all the jobs that require Rk and is denoted by Π(Rk) – At any time t, the current priority ceiling Π(t) of the system is equal to the highest priority ceiling of the resources that are in use at the time – If all resources are free, Π(Rk) is equal to Ω, a nonexistent priority level that is lower than the lowest priority level of all jobs Real-time systems (c) Cuong Pham-Quoc 29
30. Rules of basic priority ceiling protocol 1. Scheduling rule: – At its release time t, the current priority π(t) of every job J is equal to its assigned priority. The job remains at this priority except under the condition stated in rule 3. – Every ready job J is scheduled preemptively and in a priority-driven manner at its current priority π(t). 2. Allocation rule: whenever a job J requests a resource R at time t, one of the following two conditions occurs: – R is held by another job. J’s request fails and J becomes blocked – R is free • If J’s priority π(t) is higher than the current priority ceiling, R is allocated to J • If J’s priority π(t) is not higher than the ceiling Π(t) of the system, R is allocated to J only if J is the job holding the resource(s) whose priority ceiling is equal to Π(t); otherwise, J’s request is denied, and J becomes blocked • Unlike priority inheritance: can deny access to an available resource Real-time systems (c) Cuong Pham-Quoc 30
31. Rules of basic priority ceiling protocol 3. Priority-inheritance rule: – When the requesting job, J, becomes blocked, the job Jl which blocks J inherits the current priority π(t) of J – Jl executes at its inherited priority until the time when it releases every resource whose priority ceiling is equal to or higher than π(t); at that time, the priority of Jl returns to its priority πl(t′) at the time t′ when it was granted the resource(s) Real-time systems (c) Cuong Pham-Quoc 31
32. Example • Consider that complex example above Real-time systems (c) Cuong Pham-Quoc 32
33. Basic priority ceiling protocol • If resource access in a system of preemptable, fixed priority jobs on one processor is controlled by the priority-ceiling protocol: – Deadlock can never occur – A job can be blocked for at most the duration of one critical section • There is no transitive blocking under the priority-ceiling protocol • Differences between the priority-inheritance and priority-ceiling protocols: – Priority inheritance is greedy, while priority ceiling is not • The priority ceiling protocol may withhold access to a free resource, causing a job to be blocked by a lower-priority job which does not hold the requested resource – termed avoidance blocking – The priority ceiling protocol forces a fixed order onto resource accesses, thus eliminating deadlock Real-time systems (c) Cuong Pham-Quoc 33
34. Deadlock avoidance example • Consider three jobs as shown in the table below Job ri ei Prority J1 3.5 4 1 [R1; 1.5] J2 1 4 2 [R2;2[R3;1]] J3 0 5.5 3 [R3;4[R2;2.5]] – J1 requires R1 after 1 unit of execution time – J2 requires R2 after 1.5 unit of execution time; and R3 after requiring R2 0.5 unit of execution – J3 requires R3 after 0.5 unit of execution; and R2 after requiring R3 1 unit of execution Real-time systems (c) Cuong Pham-Quoc 34
35. Uncontrolled Non-preemptive Priority-inheritance Priority-ceiling Real-time systems (c) Cuong Pham-Quoc 35
36. Enhancing the priority ceiling protocol • The basic priority ceiling protocol gives good performance, but the defining rules are complex • Also, can result in high context switch overheads due to frequent blocking if many jobs contend for resources • This has led to two modifications to the protocol: – The stack-based priority ceiling protocol – The ceiling priority protocol Real-time systems (c) Cuong Pham-Quoc 36
37. STACK-BASED PRIORITY CEILING PROTOCOL Real-time systems (c) Cuong Pham-Quoc
38. Stack-based priority ceiling protocol 1. Ceiling: When all resources are free, Π(t) = Ω; Π(t) updated each time a resource is allocated or freed – Π(t) current priority ceiling of all resources in currently use – Ω non-existing lowest priority level 2. Scheduling: – After a job is released, it is blocked from starting execution until its assigned priority is higher than Π(t) – Non-blocked jobs are scheduled in a pre-emptive priority manner 3. Allocation: Whenever a job requests a resource, it is allocated the resource • The allocation rule looks greedy, but the scheduling rule is not Real-time systems (c) Cuong Pham-Quoc 38
39. Example • Consider jobs as shown in the table Job ri ei Priority J1 7 3 1 [R1; 1] J2 5 3 2 [R2; 1] J3 4 2 3 J4 2 6 4 [R1; 4 [R2; 1.5]] J5 0 6 5 [R2; 4] • Jobs J1, J2, J4, and J5 attempt to lock their first resource after one unit of execution; J4 accesses R2 after an additional 2 units of execution Real-time systems (c) Cuong Pham-Quoc 39
40. Real-time systems (c) Cuong Pham-Quoc 40
41. Deadlock avoidance • When a job begins to execute, all the resources it will ever need during its execution are free – Otherwise, if one of the resources it will need is not free, the ceiling of the system is equal to or higher than its priority • When a job J is preempted, all the resources the preempting job will require are free, ensuring that the preempting job can always complete so J can resume. • ⇒ Consequently, deadlock can never occur Real-time systems (c) Cuong Pham-Quoc 41
42. Priority-ceiling protocol in dynamic priority systems • The priority-ceiling protocol assumes fixed priority scheduling • In a dynamic priority system, the priorities of the periodic tasks change over time, while the set of resources required by each task remains constant – The priority of each resource may change over time • What happens if T1 uses resource X, but T2 does not? – Priority ceiling of X is 1 for 0 ≤ t ≤ 4, becomes 2 for 4 ≤ t ≤ 5, etc. even though the set of resources required by the tasks remains unchanged Real-time systems (c) Cuong Pham-Quoc 42
43. Priority-ceiling protocol in dynamic priority systems • We can still use the priority-ceiling protocol to control resource accesses – updating the priority ceiling of each resource and the ceiling of the system each time task priorities change • For job-level fixed-priority systems (EDF, LIFO) – Each job in a task has a fixed priority once it is scheduled, but may be scheduled at different priority to other jobs in the task – Update the priority ceilings of all jobs each time a new job is introduced; use until updated on next job release Real-time systems (c) Cuong Pham-Quoc 43
44. Example • Consider three periodic tasks as follows – T1 = (0.5,2.0,0.2; [R1; 0.2]); – T2 = (3.0,1.5; [R2; 0.7]); accesses R2 after 0.3 unit of execution time – T3 = (5.0,1.2; [R1; 1.0[R2; 0.4]]); accesses R1 after 0.2 unit of execution time and accesses R2 after R1 0.2 unit of time • The priority ceilings of the two resources R1 and R2 are updated at times 0, 0.5, 2.5, 3, 4.5, 5, 6, and so on Real-time systems (c) Cuong Pham-Quoc 44
45. Real-time systems (c) Cuong Pham-Quoc 45
46. The end Computer Science Program