Real-Time Systems - Lecture 6: Multiprocessor Scheduling, Resource access control, and Synchronization

Nội dung text: Real-Time Systems - Lecture 6: Multiprocessor Scheduling, Resource access control, and Synchronization

1. Real-time systems Lecture 6: Multiprocessor Scheduling, Resource access control, and Synchronization Cuong Pham-Quoc Based on Chapter 9 of Liu’s book Computer Science Program 1
2. Outline • Multiprocessor • Task assignment – Execution-based – Execution and communication-based – Execution, communication, and resource-based Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 2
3. Model of multiprocessor • Systems can contain more than one processors – Multiprocessor systems (tightly coupled) vs. Distributed systems (loosely coupled) – Identical/Homogeneous vs. Heterogeneous processors • Heterogeneous processors: each job can execute on some types of processors but not all types – Different processors may have different speeds • We use !" to denote a processor type " which consists of #" processors – In total, the number of processors in a system consisting of $ types * of processors is # = ∑'() #' Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 3
4. Local vs. Remote resources • Assume that each resource resides on a processor – The scheduler of the processor controls the access to the resource – The critical sections jobs accessing the resource execute on the processor • Resource models in multicore systems – MPCP (Multiprocessor Priority-Ceiling Protocol) model – End-to-End model Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 4
5. MPCP resource model • Definitions: – Synchronization processor of a resource is the processor hosting the resource – Local processor of a job is the processor on which the job is released – Local resource for a job is the resource that resides on the local processor of the job – Remote resource vs. local resource – A global resource is required by jobs that have different local processors • MPCP model: – The critical section during which the job uses a resource executes on the synchronization processor of the resource Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 5
6. Example • Consider a system consisting three jobs !1, !2, and !3. The system have two processors %1 and %2 synchronizing two resources a printer and a file server, respectively – !1 and !2 are local to %1 while !3 is a local job on %2 – !1 requires the printer, !3 requires the file server while !2 requires both Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 6
7. Interprocessor communication Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 7
8. Task assignment • Task assignment in multiprocessor systems: – Tasks in an application real-time system are partitioned into modules – Modules are assigned and bound to processors • Purposes: – Determine how many processors of each type needed – How tasks should be partitioned – On which processor each application module executes • Task assignment can be done on-line or off-line • Need to take into account when making task assignment – Execution time – Communication cost – Resource access cost Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 8
9. Based on execution time requirements • Appropriate for some systems such as shared memory communication systems – Communication cost and resource access cost are negligible • Using Bin-packing formulation – ! periodic tasks put into " “modules” – The smaller number of processors required, the better the assignment Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 9
10. Simple bin-packing formulation • Simple bin-packing formulation – Given ! periodic tasks whose utilization " > 1, impossible for single core execution – Call %& is utilization task & for & = 1,2, , ! – For EDF algorithm, utilization of tasks in module should be no greater than 1 • Constrain the utilization of all tasks in each module to be equal or less than "’ < 1 to have space for aperiodic jobs • For RM, "’ < "-. = ln2 • First-fit algorithm – Tasks are assigned one by one in arbitrary order – 1& is assigned after & − 1 tasks have been assigned – 1& is assigned to 34 if total utilization of all task assigned to 34 and %& < "’ when 1& cannot be assigned to 31, 32, , 3567 Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 10
11. Rate-Monotonic First-fit (RMFF) • Motivation: ) – !"#(%) = %(2* − 1) – Variable-size Bin-packing formulation • RMFF – Tasks are sorted in nondecreasing order according to their periods – Tasks are assigned in the following order in the first-fit manner – A task -. is assigned to a processor if the total utilization of -. and / tasks already assigned to the processor is equal or smaller than !"#(/ + 1) Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 11
12. Example • Consider the following tasks %& '& assigned to processors by the (2, 1) 0.500 RMFF algorithm (2.5, 0.1) 0.040 – !1: (2, 1), (2.5, 0.1), (4.5, 0.1), (6, (3, 1) 0.333 1), (8.5, 0.1) (4, 1) 0.250 – !2: (3, 1), (4, 1), (7, 1) (4.5, 0.1) 0.022 – !3: (5, 1), (8, 1), (9, 1) • The optimal assignment needs 3 (5, 1) 0.200 processors (6, 1) 0.167 (7, 1) 0.143 – !1: (2, 1), (3, 1), (6, 1) – !2: (4, 1), (5, 1), (7, 1), (8, 1), (9, 1) (8, 1) 0.125 – !3: (2.5, 0.1), (4.5, 0.1), (8.5, 0.1) (8.5, 0.1) 0.012 (9, 1) 0.111 Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 12
13. Rate-Monotonic Small Task • Motivation: – RMFF doesn’t take simply periodic into consideration • RMST: assigning tasks according to !" value instead of #" like RMFF – !$ = &'()#$ − &'()#$ – Sort tasks according to Xi – A task is schedulable when assigned to processor +, if and only if • -$ + /0 ≤ max &52, 1 − 90&52 , where 90 = max ! − min ! for all tasks assigned to +k Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 13
14. Example % ( • Consider the tasks set as before %& '& ID & & (2, 1) 0.500 % (2, 1) 0 – !1: (2, 1), (4, 1), (8, 1), (8.5, 0.1) 1 – !2: (4.5, 0.1), (9, 1), (2.5, 0.1), (5, (2.5, 0.1) 0.040 %2 (4, 1) 0 1), (6, 1) (3, 1) 0.333 %3 (8, 1) 0 – !3: (3, 1), (7, 1) (4, 1) 0.250 %4 (8.5, 0.1) 0.087 (4.5, 0.1) 0.022 %5 (4.5, 0.1) 0.170 (5, 1) 0.200 %6 (9, 1) 0.170 (6, 1) 0.167 %7 (2.5, 0.1) 0.322 (7, 1) 0.143 %8 (5, 1) 0.322 (8, 1) 0.125 %9 (3, 1) 0.585 (8.5, 0.1) 0.012 %10 (6, 1) 0.585 (9, 1) 0.111 %11 (7, 1) 0.807 Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 14
15. Minimize total communication cost • Requirements: – Minimize the number of processors – Minimize communication cost among tasks in different modules • Cost for communication: – Volume of data exchanged – Bandwidth of the connection links • Assignment process – Tasks partition: assign tasks into modules using task parameters – Modules assignment: mapping modules to processors, taking into account the characteristics of the underlying network used to support interprocessor communication Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 15
16. Partition problem • Notations: – !",$: communication cost between any pair of tasks %& and %' • It can be amount of data exchanged • Example: two periodic tasks %& and %', !",$ can be total volume of data exchanged between the tasks during any hyperperiod – (",): interference cost that is incurred when tasks %& and %* are placed in the same processor • Can also be used as external constraints – +",$: is 1 when & = *; otherwise it is 0 – -",$: is 1 when task %& is placed in the 'th processor; otherwise it is 0 Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 16
17. Partition problem • Assume that we need to partition ! tasks into " processors – The maximum allowed total utilization #′% of all task in the %th module • The problem can be solved by integer linear programming – Find values of &',), for * = 1, 2, , ! and % = 1, 2, , " that satisfy the following constraints: • &',) = 0, 1 for * = 1, 2, , ! and % = 1, 2, , " 3 • ∑)12 &',) = 1 for * = 1, 2, , ! 4 • ∑'12 5' &',) ≤ #′) – and minimize the cost function 4 44 4 4 • 7898:; ∑'12 ∑ ', ),; + A',<>),;] Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 17
18. Example • Consider the following tasks assigned to 2 processors with their communication graph !1 10 !3 15 !5 2 !7 ID !" #" !1 (2, 1) 0.50 7 13 8 25 10 !2 (3, 1) 0.33 9 !3 (4, 1) 0.25 !2 !4 !6 !8 !4 (5, 1) 0.20 !5 (6, 1) 0.17 ,-.-/0 = 7 23,325,5 + 23,525,3 + 10 23,328,5 + 23,528,3 !6 (10, 1) 0.10 + 9 25,32:,5 + 25,52:,3 + 13 28,32:,5 + 28,52:,3 !7 (15, 1) 0.07 + 15 28,32:,5 + 28,52;,3 + 8 2:,32;,5 + 2:,52;,3 ! (25, 1) 0.04 8 +25 2;,32<,5 + 2;,52<,3 + 2 2;,32=,5 + 2;,52=,3 +10(2=,32?,5 + 2=,52?,3) Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 18
19. Module assignment • If processors are connected by a broadcast network or bus or crossbar, the cost of interprocessor communication among all processors are the same • Otherwise, need to embed the task graph of modules on the resource graph of processors to minimize a cost function: – The average (or maximum) number of hops between modules – The average (or maximum) weighted number of hops Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 19
20. Integration of task and resource assignments • MPCP model: – Resource utilization: the usage of a resource !" by a task #$ is given by %&,( • Graph partitioning formulation: assignment graph – Each task, processor, or resource in the system is represented by a vertex – Three types of edges: • There is a task-task edge between two task vertices Ti and Tj if they communicate, )&,( is the edge weight • There is a task processor (or resource processor) edge if the task (or resource) is constrained to be assigned to the processor • There is a task resource edge if the task uses the resource, %&,( is the edge weight • The problem is now to find an m-way cut of the assignment graph that satisfies the schedulability constraint and has the minimum cut size – NP-hard problem Lecture 6: Multiprocessor systems - (c) Cuong Pham-Quoc 20