3.6
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View 3.6 as PDF for free.
More details
- Words: 500
- Pages: 3
Real Time System by Jane W. S. Liu Chapter 4.2 Solution
1 of 3
about:reader?url=http://targetiesnow.blogspot.com/2013/10/real-time-sy...
targetiesnow.blogspot.com
Real Time System by Jane W. S. Liu Chapter 4.2 Solution 3 minutes
Q.4.2: The execution times of the jobs in the precedence graph in figure 4P-2 are all equal to 1, and their release times are identical. Give a non preemptive optimal schedule that minimizes the completion time of all jobs on three processors. Describe briefly the algorithm you used to find the schedule.
Sol: Execution time of all jobs equal to 1. Release times are identical, non preemptive optimal solution:
04/13/2019, 6:03 PM
Real Time System by Jane W. S. Liu Chapter 4.2 Solution
2 of 3
about:reader?url=http://targetiesnow.blogspot.com/2013/10/real-time-sy...
Next Topic: Q.4.4: Consider a system that has five periodic tasks, A, B, C, D, and E, and three processors P1, P2, P3. The periods of A, B, and C are 2 and their execution times are equal to 1. The periods of D and E are 8 and their execution times are 6. The phase of every task is 0, that is, the first job of the task is released at time 0. The relative deadline of every task is equal to its period. a) Show that if the tasks are scheduled dynamically on three processors according to the LST algorithm, some jobs in the system cannot meet their deadlines. b) Find a feasible schedule of the five tasks on three processors. SOLUTION Previous Topic: Q.4.1: The feasible interval of each job in the precedence graph in figure 4P-1 is given next to its name. The execution time of all jobs are equal to 1.
a) Find the effective release times and deadlines of the jobs in the 04/13/2019, 6:03 PM
Real Time System by Jane W. S. Liu Chapter 4.2 Solution
3 of 3
about:reader?url=http://targetiesnow.blogspot.com/2013/10/real-time-sy...
precendence graph in Figure 4P-1. b) Find an EDF schedule of the jobs. c) A job is said to be at level i if the length of the longest path from the job to jobs that have no successors is i. So, jobs J3, J6 and J9 are at level 0, jobs J2, J5 and J8 are at level 1, and so on. Suppose that the priorities of the jobs are assigned based on their levels, the heigher the level, the higher the priority. Find a priority-drive schedule of the jobs in Figure 4P-1 according to this priority assignment. :ABOUT THE BOOK: Real Time System by Jane W. S. Liu (Pearson), the book builds on the student's background in Operating System, Embedded System. It covers techniques for scheduling, resource access control, and validation that are, or are likely to be, widely used in real time computing and communication systems. Each algorithm, protocol, or mechanism is defined by pseudo code or simple rules that can serve as a starting point of implementation. With few exceptions, each scheduling algorithm is accompanied that your application will meet its real time requirement when scheduling according to the algorithm.
04/13/2019, 6:03 PM
1 of 3
about:reader?url=http://targetiesnow.blogspot.com/2013/10/real-time-sy...
targetiesnow.blogspot.com
Real Time System by Jane W. S. Liu Chapter 4.2 Solution 3 minutes
Q.4.2: The execution times of the jobs in the precedence graph in figure 4P-2 are all equal to 1, and their release times are identical. Give a non preemptive optimal schedule that minimizes the completion time of all jobs on three processors. Describe briefly the algorithm you used to find the schedule.
Sol: Execution time of all jobs equal to 1. Release times are identical, non preemptive optimal solution:
04/13/2019, 6:03 PM
Real Time System by Jane W. S. Liu Chapter 4.2 Solution
2 of 3
about:reader?url=http://targetiesnow.blogspot.com/2013/10/real-time-sy...
Next Topic: Q.4.4: Consider a system that has five periodic tasks, A, B, C, D, and E, and three processors P1, P2, P3. The periods of A, B, and C are 2 and their execution times are equal to 1. The periods of D and E are 8 and their execution times are 6. The phase of every task is 0, that is, the first job of the task is released at time 0. The relative deadline of every task is equal to its period. a) Show that if the tasks are scheduled dynamically on three processors according to the LST algorithm, some jobs in the system cannot meet their deadlines. b) Find a feasible schedule of the five tasks on three processors. SOLUTION Previous Topic: Q.4.1: The feasible interval of each job in the precedence graph in figure 4P-1 is given next to its name. The execution time of all jobs are equal to 1.
a) Find the effective release times and deadlines of the jobs in the 04/13/2019, 6:03 PM
Real Time System by Jane W. S. Liu Chapter 4.2 Solution
3 of 3
about:reader?url=http://targetiesnow.blogspot.com/2013/10/real-time-sy...
precendence graph in Figure 4P-1. b) Find an EDF schedule of the jobs. c) A job is said to be at level i if the length of the longest path from the job to jobs that have no successors is i. So, jobs J3, J6 and J9 are at level 0, jobs J2, J5 and J8 are at level 1, and so on. Suppose that the priorities of the jobs are assigned based on their levels, the heigher the level, the higher the priority. Find a priority-drive schedule of the jobs in Figure 4P-1 according to this priority assignment. :ABOUT THE BOOK: Real Time System by Jane W. S. Liu (Pearson), the book builds on the student's background in Operating System, Embedded System. It covers techniques for scheduling, resource access control, and validation that are, or are likely to be, widely used in real time computing and communication systems. Each algorithm, protocol, or mechanism is defined by pseudo code or simple rules that can serve as a starting point of implementation. With few exceptions, each scheduling algorithm is accompanied that your application will meet its real time requirement when scheduling according to the algorithm.
04/13/2019, 6:03 PM
Related Documents
36
November 2019 53
36
November 2019 50
36
June 2020 34
36
May 2020 43
36
August 2019 66
36
April 2020 44More Documents from ""
Oracle 3 Tier Architecture Diagrams
October 2019 32
Arun.pdf
October 2019 28
Experimental Design By Arun Kumar Mishra Iftm
June 2020 18
1524465249009ggmiaddis7muhtgw.pdf
May 2020 16