郑州大学信息工程学院大四计科外教实时处理

ECTE431-ECTE931 Real-Time Computing Example Paper Solution 1 Provided by the lecturer for revision purpose. QUESTION 1 10 marks a) Define real-time systems. 4 marks Solution: o A real-time system is a system with explicit timing requirements. o The system must respond to external inputs within a specified period. o Failure to meet the timing requirements is as bad as producing the wrong outputs. o An example of real-time systems: MPEG video and audio encoder (30 frames/s) b) Describe briefly three major scheduling approaches for real-time systems. 6 marks Solution: Clock-driven scheduling approach o Scheduling decisions are made at specific time instants, which are typically chosen a priori. o Typically, a hardware timer is used to provided periodic time instants, at which the scheduler wakes up and selects the next jobs to execute. o Suitable for systems that consist of mostly deterministic and periodic tasks. Weighted round-robin scheduling approach o Jobs are given weights and are placed in a circular FIFO queue. o Processors time is divided into equal time slices. o When it is job Jis turn, it will execute for wi time slices before being pre-emptied for the next job in queue. o New jobs execute almost immediately. This approach is suitable for incremental producer/consumer jobs. Priority-driven scheduling approach o At any scheduling decision time, among the eligible jobs, the one with the highest priority is selected for execution. o This approach tries to make locally optimal decisions and is also known as greedy scheduling. o Examples are first-in-first-out, shortest-execution-time- first, earliest-deadline-first. ECTE431-ECTE931 Real-Time Computing Example Paper Solution 2 Provided by the lecturer for revision purpose. QUESTION 2 10 marks a) Explain frame scheduling and the major operations of a cyclic executive. 6 marks Solution: Frame scheduling o Scheduling decisions are made periodically rather than at arbitrary time. o The hyperperiod is divided into equal time intervals called frames. o Scheduling decisions are made only at the beginning of every frame. This means no preemption is allowed within each frame, and there is no need for adjusting the timer. Cyclic executive o Cyclic executive uses a scheduling table. o The table has F entries where F is the number of frames in a major cycle. o Each entry L(k), called a scheduling block, is a list of job slices to be executed in frame k. o At each timer interrupt, the cyclic executive takes over the processor. It then calls a periodic task server to execute the job slices in the current block. o The remaining time in a frame is used to run aperiodic jobs. b) The following system of three periodic tasks is executed according to a cyclic schedule: T1 = (3, 2), T2 = (4, 1) and T3 = (6, 3) Find the appropriate frame sizes. 4 marks Solution: The frame size must satisfy three constraints: max( ) i fe /Hf is an integer 2gcd(,) ii fpfD The hyper-period: H = 6 First constraint: f 2 Second constraint: H = 12 = f = 1, 2, 3, 4, 6, 12 Third constraint: 2f gcd(f,3) 3 2f gcd(f,4) 4 2f gcd(f,6) 6 The third constraint implies that f 3. Hence, we only need to check if f = 2 and f = 3 satisfy the third constraint. The answer is f = 2. ECTE431-ECTE931 Real-Time Computing Example Paper Solution 3 Provided by the lecturer for revision purpose. QUESTION 3 10 marks Consider a priority-driven system with three periodic tasks: T1 = (3, 1), T2 = (4, 1) and T3 = (6, 2) a) Assume that jobs with the same priorities are ordered according to the first-in-first-out rule. Construct the earliest-deadline-first (EDF) schedule of the system for the time interval 0, 12). Is the system schedulable? 4 marks Solution: Task set The system is schedulable. b) Construct the rate-monotonic (RM) schedule of the system for the time interval 0, 12). 4 marks Solution: The system is schedulable. c) Find the maximum execution time of task T1 so that the system is definitely schedulable according to the EDF rule. 2 marks Solution: For EDF: system is schedulable if U = e1/3 + 1/4 + 2/6 1 Hence, the maximum e1 is 1.25. ECTE431-ECTE931 Real-Time Computing Example Paper Solution 4 Provided by the lecturer for revision purpose. QUESTION 4 10 marks a) State the differences between scheduling aperiodic and sporadic jobs in a priority-driven system. 3 marks Solution: Aperiodic jobs have soft deadlines. There are three ways they can be executed. o Background execution: Aperiodic jobs are given the lowest priority and executed in the background. o Interrupt-driven execution: Aperiodic jobs are given the highest priority and preempt the currently executing job o Polled execution: Aperiodic jobs are placed in a queue. A periodic task is created to service the aperiodic queue. Sporadic jobs have hard deadlines. o When a sporadic job arrives, an acceptance test is performed to ensure that it can complete on time without affecting periodic jobs and already accepted sporadic jobs. o Accepted sporadic jobs are ordered using the EDF rule. o In fixed-priority systems, a sporadic server is usually used to service sporadic jobs. o In deadline-driven systems, sporadic jobs are scheduled with periodic jobs using the EDF rule. b) List and differentiate the servers that can be used to execute aperiodic jobs in priority-driven scheduling. 3 marks Solution: o Polling server: When there is no aperiodic job, the server terminates immediately and clears it budget. Any aperiodic job that arrives late must wait until the next polling period. o Deferrable server: When there is no aperiodic job, the server releases the CPU but still keeps it budget. Subsequently, any aperiodic job that arrives in the same polling period can execute immediately, provided that there is some budget remaining. o Sporadic server: When there is no aperiodic or sporadic job, the server keeps waiting in its allocated time slot. The three servers are similar in that they are periodic tasks that are created in order to service aperiodic and sporadic tasks. ECTE431-ECTE931 Real-Time Computing Example Paper Solution 5 Provided by the lecturer for revision purpose. c) A system has two periodic tasks T1 = (3,1) and T2 =(4,1). A deferrable server of period 2 and execution budget es is used to service aperiodic jobs. Suppose the server and the periodic tasks are scheduled according to the EDF rule. What is the maximum possible execution budget of the server so that the system is schedulable? 4 marks Solution: Task Ti is schedulable if 1 (1)1 min(,) n kss s k kki epe u DpD or 1 (1)1 / s s is u Uu Dp Total utilization of periodic tasks: U = e1/p1 + e2/p2 = 1/3 + 1/4 = 7/12 Two constraints must be satisfied: o Task 1: 1 (1)5/12 3/2 s s u u o Task 2: 1 (1)5/12 4/2 s s u u Solving the first equation gives 0.28 s u or 2.22 s u Solving the second equation gives 0.31 s u or 2.69 s u Since us 1, we require 0.28 s u Therefore the maximum execution time is 0.28 x 2 = 0.56 ECTE431-ECTE931 Real-Time Computing Example Paper Solution 6 Provided by the lecturer for revision purpose. QUESTION 5 10 marks a) Compare the operations and merits of the following resource-access control protocols: i) the priority-inheritance, and ii) the priority-ceiling. 3 marks Solution: Both protocols o Each job has two types of priorities: default priority given by the scheduling algorithm such as RM or EDF, and current priority that can be changed dynamically according to the access control protocol. o If a job holds a resource and thereby blocking a higher- priority job, it inherits the current priority of the blocked job. Priority-inheritance protocol o When a job requests a resource, if the resource is available, the request is always granted. o The priority-inheritance protocol can lead to deadlocks. Priority-ceiling protocol o Each resource R is given a priority ceiling R, which is the highest priority among the jobs that need R. o The system is given a priority ceiling sytem(t), which is the highest priority among the resources that are currently in use. o When a job requests a resource and the resource is available, the request is granted only if the job has a priority greater than the system priority system(t), or the job holds a resource with priority equal to system(t). o The priority-ceiling protocol can prevent deadlocks. b) A system has three periodic tasks T1 = (3,1), T2 = (4,1.5) and T3 = (6,1), and two resources X and Y. The critical sections of the tasks are given as follows. T1: X; 0.4 T2: Y; 0.8 T3: X; 0.5; Y; 0.6 The system is scheduled according to the rate-monotonic algorithm and the priority-ceiling protocol. i) Find the maximum blocking times of the tasks due to the resource constraints. ii) Apply the appropriate test to determine if the tasks are schedulable. 7 marks ECTE431-ECTE931 Real-Time Computing Example Paper Solution 7 Provided by the lecturer for revision purpose. Solution: i) resource graph Directly blocked by Inheritance blocked by Avoidance blocked by T1 T2 T3 T1 T2 T3 T1 T2 T3 T1 0.5 T2 0.6 0.5 0.5 T3 Maximum blocking time of T1 = max(row T1): b1 = 0.5 Maximum blocking time of T2 = max(row T2): b2 = 0.6 Maximum blocking time of T3: b3 = 0 ii) Taking into account the blocking time due to resource constraints, the time-demand function for periodic task Ti is 1 1 ( ) for 0 i iiiki k k t w tbeetp p T1: 1( ) 0.5 1 for 03 w tt T2: 1( ) 0.6 1.51 for 04 3 t w tt T3: 1( ) 11 + 1.5 for 06 34 tt w tt Based on the plots of the time-demand functions, task T1 and T3 are schedulable because their time-demand functions cut the line f(t) = t. Task T2 is not schedulable. 01234567 0 1 2 3 4 5 6 7 t Time Demand Functions T1 T2 T3 f(t)=t ECTE431-ECTE931 Real-Time Computing Example Paper Solution 8 Provided by the lecturer for revision purpose. QUESTION 6 10 marks Explain the following terms in relation to multi-processor scheduling a) First-fit algorithm 2 marks b) Rate-monotonic first-fit algorithm 2 marks c) Greedy protocol 2 marks d) Release guard protocol 2 marks e) Proportional deadline 2 marks Solution: First-fit algorithm o It is a heuristic algorithm for task assignment problem, i.e. assigning periodic tasks to multiple processors so that (i) a minimum number of processors are used and (ii) tasks assigned on each processor are schedulable. o Each processors total utilization must not exceed a preset value U. o Tasks are allocated one by one in an arbitrary order. o For each task, if it can be added to an existing processor P without exceeding the processors capacity U, then we assign the task to P. Otherwise, we assign the task to a new processor. Rate-monotonic first-fit algorithm o Another heuristic algorithm for task assignment. o Tasks are allocated in the order of n