Real-Time Systems - Chapter 3: Clock-driven scheduling

Nội dung text: Real-Time Systems - Chapter 3: Clock-driven scheduling

1. REAL-TIME SYSTEMS Chapter 3: Clock-driven scheduling Computer Science Program
2. Lecture outline • Assumptions and notation for clock-driven scheduling • Handling periodic jobs – Static, clock-driven schedules and the cyclic executive • Handling aperiodic jobs – Slack stealing • Handling sporadic jobs • Advantages and disadvantages of clock driven scheduling Real-time systems (c) Cuong Pham-Quoc 2
3. Assumptions • Clock-driven scheduling applicable to deterministic systems • A restricted periodic task model: – The parameters of all periodic tasks are known a priori – For each mode of operation, system has a fixed number, n, periodic tasks • Each job in Ti is released pi units of time after the previous job in Ti; i.e., ri,k = ri,k−1 + pi • Each job Ji,k is ready for execution at its release time ri,k • Variations in the inter-release times of jobs in a periodic task are negligible – Aperiodic jobs may exist • Assume that the system maintains a single queue for aperiodic jobs • Whenever the processor is available for aperiodic jobs, the job at the head of this queue is executed – There are no sporadic jobs • Recall: sporadic jobs have hard deadlines, aperiodic jobs do not Real-time systems (c) Cuong Pham-Quoc 3
4. Notations • The 4-tuple Ti = (ϕi, pi, ei, Di) refers to a periodic task Ti with phase ϕi, period pi, execution time ei, and relative deadline Di – Default phase ϕi = 0, default relative deadline is the period (Di = pi) – Omit elements of the tuple that have default values • Example T1 = (1,10,3,6) ϕ1 d1,1 r1,2 d1,2 e1 p1 J1,1 J1,2 0 1 2 3 4 5 6 7 8 9 10 11 • Another examples: T2 = (10,3,6); T2 = (10,3) Real-time systems (c) Cuong Pham-Quoc 4
5. Clock-driven scheduling • Static, timer-driven schedule (version 1.0): – Schedule calculated offline at design time – Can use complex algorithms to optimize some characteristics of the system – Relies on accurate timer interrupts, based on execution times of tasks • Structured cycle schedule (version 2.0): – Make scheduling decisions on-line at periodic intervals – Easier to implement Real-time systems (c) Cuong Pham-Quoc 5
6. Static, timer-driven • This schedule specifies exactly when each job executes (off-line) – During run-time, the scheduler dispatches the jobs according to this schedule – All deadline are surely met (as long as no job ever over-run) – Constructing a static schedule for the first hyper-period • If utilization of system, U, is less than 1 Real-time systems (c) Cuong Pham-Quoc 6
7. Example • Consider a system consisting 4 periodic tasks – T1 = (4,1) – T2 = (5,1.8) – T3 = (20,1) – T4 = (20,2) • Hyper-period H = LCM(4,5,20) = 20 – The entire schedule consists of replicated segments of length 20 • Can construct an arbitrary static schedule to meet all deadline – For example: The schedule can be obtained by any algorithm • Real-time systems (c) Cuong Pham-Quoc 7
8. Implementation Pre-computed schedule Heap memory timer Task code Task code • The pre-computed schedule table: k entries: – tk: decision time; T(tk): a task or idle (I) • At each tk: processor sets timer to expire and request an interrupt at the next decision time (tk + 1) – If T(tk) = I, execute a waiting aperiodic task – Otherwise, start the next job in task T(tk) Real-time systems (c) Cuong Pham-Quoc 8
9. Structure cycle schedule • Make scheduling decisions at periodic intervals (frames) of length f • Execute a fixed list of jobs with each frame, disallowing pre-emption except at frame boundaries – Need to define an appropriate frame size • Require phase of each periodic task to be a non-negative integer multiple of the frame size – The first job of every task is released at the beginning of a frame – ϕ = k × f where k is a non-negative integer decision points Real-time systems (c) Cuong Pham-Quoc 9
10. Structure cycle schedule • Major cycle: frames in a hyper-period • Gives two benefits: – Scheduler can easily check for overruns and missed deadlines at the end of each frame – Can use a periodic clock interrupt, rather than programmable timer Real-time systems (c) Cuong Pham-Quoc 10
11. Frame size constraints • How to choose frame size? The frame size should satisfy the three following constraints – To avoid preemption, want jobs to start and complete execution within a single frame: f ≥ max(e1, e2, . . . , en) (Eq. 1) – To minimize the number of entries in the cyclic schedule, the hyper-period should be an integer multiple of the frame size (⇒ f divides evenly into the period of at least one task): ∃i : mod(pi, f ) = 0 (Eq. 2) – To allow scheduler to check that jobs complete by their deadline, should be at least one frame boundary between release time of a job and its deadline: 2 × f − gcd(pi, f ) < Di, for i = 1,2, ,n (Eq. 3) Real-time systems (c) Cuong Pham-Quoc 11
12. Constraint - 2 • To minimize the number of entries in the cyclic schedule, the hyper-period should be an integer multiple of the frame size: ∃i : mod(pi, f ) = 0 • Proof: ⇒ H – Hyper-period H is divided into F frames F = is integer number f lcm(p ) lcm i – H = (pi) ⇒ F = is an integer number f – mod(lcm(pi), pi) = 0,∀i lcm(p i mod – is an integer if and only if ∃i : (pi, f ) = 0 f Real-time systems (c) Cuong Pham-Quoc 12
13. Contraints - 3 • 2 × f − gcd(pi, f ) < Di, for i = 1,2, ,n so that there exists at least one full frame between release time and deadline of any job • Proof: – Theorem: the minimum separation of the task release time (t′) from the corresponding frame start time (t) considering all instances of a task Ti is at least gcd( f, pi) – Assume 0 < t′ − t < gcd( f, pi) = g (1) th th ⇒ – Consider the frame k and job n of Ti;(1) 0 < n × pi − k × f < g p f ⇔ 0 < n × i − k × < 1: always not true g g Real-time systems (c) Cuong Pham-Quoc 13
14. Example • Question: Consider a system with 4 independent periodic tasks: T1 = (4,1.0); T2 = (5,1.8); T3 = (20,1.0); T4 = (20,2.0). What is the largest feasible frame size? • Answer: – Constraint 1: f ≥ 2.0 – Constraint 2: f = {20,10,5,4,2,1} – Constraint 3: • Check by task by task Real-time systems (c) Cuong Pham-Quoc 14
15. Example • Constraint 3: g = 2 × f − gcd(pi, f ) < Di • Assume f = 2 • Assume ⇒ f = 20 – Checking with T1 = (4,1.0) D1 = 4 – Checking with T = (4,1.0) ⇒ D = 4 1 1 • f = 2 ⇒ g = 2 × 2 − gcd(4,2) = 2 • f = 20 ⇒ g = 2 × 20 − gcd(20,4) = 36 (rejected) (accepted) • Assume ⇒ f = 10 – Checking with T2 = (5,1.8) D2 = 5 – Checking with ⇒ T1 = (4,1.0) D1 = 4 • f = 2 ⇒ g = 2 × 2 − gcd(5,2) = 3 • f = 10 ⇒ g = 2 × 10 − gcd(10,4) = 18 (rejected) (accepted) ⇒ • Assume f = 5 – Checking with T3 = (20,1.0) D3 = 20 – Checking with ⇒ T1 = (4,1.0) D1 = 4 • f = 2 ⇒ g = 2 × 2 − gcd(20,2) = 2 (accepted) • f = 5 ⇒ g = 2 × 5 − gcd(5,4) = 9 (rejected) Checking with ⇒ • Assume f = 4 – T4 = (20,2.0) D4 = 20 ⇒ – Checking with T1 = (4,1.0) D1 = 4 • f = 2 ⇒ g = 2 × 2 − gcd(20,2) = 2 (accepted) • f = 4 ⇒ g = 2 × 4 − gcd(4,4) = 4 (accepted) ⇒ • ⇒ the frame size f = 2 satisfies all 3 constraints – Checking with T2 = (5,1.8) D2 = 5 • f = 4 ⇒ g = 2 × 4 − gcd(5,4) = 7 (rejected) Real-time systems (c) Cuong Pham-Quoc 15
16. Another example • Question: Consider a system with three tasks: T1 = (5,1), T2 = (7,2), T3 = (8,3). What is the largest feasible frame size? • Answer: – Constraint 1: f ≥ 3.0 – Constraint 2: possible candidates f = {8,7,5,4,2,1} – Constraint 3: f = 2.0 If we choose the frame size f = 2, it will not satisfy the first constraint What should we do? Real-time systems (c) Cuong Pham-Quoc 16
17. Job slices • Sometimes, a system cannot meet all three frame size constraints simultaneously • Can often solve by partitioning a job with large execution time into slices (sub-jobs) with shorter execution times/deadlines – Gives the effect of preempting the large job, so allow other jobs to run – Sometimes need to partition jobs into more slices than required by the frame size constraints, to yield a feasible schedule • Example: – Consider a system with T1 = (4,1), T2 = (5,2,5), T3 = (20,5) – Cannot satisfy constraints: Eq.1 ⇒ f ≥ 5 but Eq.3 ⇒ f ≤ 4 – Solve by splitting T3 into T3,1 = (20,1), T3,2 = (20,3) and T3,3 = (20,1) • Other possible splits exist; pick based on application domain knowledge – Result can be scheduled with f = 4 Real-time systems (c) Cuong Pham-Quoc 17
18. Building a Structured cyclic schedule • To construct a cyclic schedule, we need to make three kinds of design decisions: – Choose a frame size based on constraints – Partition jobs into slices – Place slices in frames • These decisions cannot be taken independently: – Ideally want as few slices as possible, but may be forced to use more to get a feasible schedule Real-time systems (c) Cuong Pham-Quoc 18
19. Implementation: a cyclic executive • Modify previous table-driven cyclic scheduler to be frame based, schedule all types of jobs in a multi-threaded system • Table that drives the scheduler has F entries, where – Each corresponding entry L(k) lists the names of the job slices that are scheduled to execute in frame k; called a scheduling block – Each job slice implemented by a procedure, to be called in turn • Cyclic executive executed by the clock interrupt that signals the start of a frame: – Determines the appropriate scheduling block for this frame – Executes the jobs in the scheduling block in order – Starts job at head of the aperiodic job queue running for remainder of frame • Less overhead than pure table driven cyclic scheduler, since only interrupted on frame boundaries, rather than on each job Real-time systems (c) Cuong Pham-Quoc 19
20. Aperiodic jobs • Aperiodic jobs arrive on irregular intervals • Placed on idle slots in the schedule • In case an aperiodic job arrives when another aperiodic job is executing, the later job is placed in a FIFO queue until the first job is completed aperiodic Queue Processor periodic Queue Real-time systems (c) Cuong Pham-Quoc 20
21. Schedule aperiodic • Typically: – Scheduled in the background – Their execution may be delayed • But: – Aperiodic jobs are typically results of external events • Therefore: – The sooner the completion time, the more responsive the system – Minimizing response time of aperiodic jobs becomes a design issue • Approach: – Execute aperiodic jobs ahead of periodic jobs whenever possible – This is called Slack Stealing Real-time systems (c) Cuong Pham-Quoc 21
22. Slack stealing • xk: amount of time allocated to slices executed during frame Fk • sk: Slack during frame Fk : sk = f − xk • A natural way to improve the response times of aperiodic jobs is by executing the aperiodic jobs ahead of the periodic jobs whenever possible • The cyclic executive can execute aperiodic jobs for sk amount of time without causing jobs to miss deadlines Real-time systems (c) Cuong Pham-Quoc 22
23. Example First major cycle in the cyclic schedule of the periodic tasks Aperiodic jobs with execution times and release times Aperiodic tasks scheduled with cyclic schedule Slack stealing (c): response times: A1 = 6.5; A2 = 1.5; A3 = 5.5 => average response time = 4.5 (d): response times: A1 = 4.5; A2 = 0.5; A3 = 2.5 => average response time = 2.5 Real-time systems (c) Cuong Pham-Quoc 23
24. Sporadic jobs • Reminder: sporadic jobs have hard deadlines; the release time and the execution time are not known a priori. Worst- case execution time are known when job is released. • Need acceptance test: l S(c, l) = ∑ Si i=c IF S(c,l) < e THEN • Acceptance test pseudo code: reject job; ELSE accept job; schedule execution; END; Real-time systems (c) Cuong Pham-Quoc 24
25. Scheduling accepted jobs • Static scheduling: – Schedule as large a slice of the accepted job as possible in the current frame – Schedule remaining portions as late as possible • Mechanism: – Append slices of accepted job to list of periodic-task slices in frames where they are scheduled • If more than one sporadic job arrives at once, they should be queued for acceptance in EDF order Real-time systems (c) Cuong Pham-Quoc 25
26. Example deadline execution time S1 & S4 are rejected while S2 & S3 are accepted Please note that: when doing acceptance test for S4, accounting for S2 & S3 needed Real-time systems (c) Cuong Pham-Quoc 26
27. Clock-driven scheduling: disadvantages • Inflexible – Pre-compilation of knowledge into scheduling tables means that if anything changes materially, have to redo the table generation – Best suited for systems which are rarely modified once built • Other disadvantages: – Release times of all jobs must be fixed – All possible combinations of periodic tasks that can execute at the same time must be known a priori, so that the combined schedule can be precomputed – The treatment of aperiodic jobs is very primitive • Unlikely to yield acceptable response times if a significant amount of soft real-time computation exists Real-time systems (c) Cuong Pham-Quoc 27
28. Summary • We have discussed: – Static, clock-driven schedules and the cyclic executive – Handling aperiodic jobs • Slack stealing – Handling sporadic jobs – Advantages and disadvantages of clock driven scheduling • Clock-driven scheduling applicable to static systems, small number of aperiodic jobs • The next lecture begins our study of priority scheduling for more dynamic environments Real-time systems (c) Cuong Pham-Quoc 28
29. Exercise 1. Each of the following systems of periodic tasks is scheduled and executed according to a cyclic schedule. For each system, choose an appropriate frame size. Preemptions are allowed, but the number of preemptions should be kept small. a) (6, 1), (10, 2), and (18, 2). b) (8, 1), (15, 3), (20, 4), and (22, 6). c) (4, 0.5), (5, 1.0), (10, 2), and (24, 9). d) (5, 0.1), (7, 1.0), (12, 6), and (45, 9). e) (9, 5.1, 1, 5.1), (8, 1), (13, 3), and (0.5, 22, 7, 22). f) (7, 5, 1, 5), (9, 1), (12, 3), and (0.5, 23, 7, 21) g) (10, 1, 12), (15, 1.5, 11), (21, 12, 15), and (32, 4, 24). Real-time systems (c) Cuong Pham-Quoc 29
30. Exercise 2. A system uses the cyclic EDF algorithm to schedule sporadic jobs. The cyclic schedule of periodic tasks in the system uses a frame size of 5, and a major cycle contains 6 frames. Suppose that the initial amounts of slack time in the frames are 1, 0.5, 0.5, 0.5, 1, and 1. a) Suppose that a sporadic job S1(23,1) arrives in frame 1, sporadic jobs S2(16,0.8) and S3(20,0.5) arrive in frame 2. In which frame are the accepted sporadic jobs scheduled b) Suppose that an aperiodic job with execution time 3 arrives at time 1 (together with sporadic jobs above). When will it be completed, if the system does not do slack stealing? Real-time systems (c) Cuong Pham-Quoc 30