Scheduling
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 Scheduling as PDF for free.
More details
- Words: 1,930
- Pages: 9
EEET1262 Real Time Systems Design
Assignment 2: Scheduling
Lecturer: Prof. Roy Ferguson ([email protected]) Submision Date: 2007/05/14
Students:
Wilson Castillo Bautista ([email protected])
Subject Code: EEET1262 Real Time Systems Design
Melbourne, May 4th, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Table of Contents 1 2 3 4
Introduction ......................................................................................................................................4 Question 1 .........................................................................................................................................4 Question 2 .........................................................................................................................................7 References ........................................................................................................................................9
RMIT University © 2007 School of Electrical and Computer Engineering
2 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Table of Figures Figure 1: Conventions used for timing diagrams (Buttazzo G C, 1997) .........................................5 Figure 2: Timing Diagram for tasks set Question 1) case a).............................................................5 Figure 3: Timing Diagram for tasks set Question1) case b)..............................................................6 Figure 4: Timing Diagram for tasks set Question1) case c) ..............................................................6 Figure 5: Timing Diagram using EDF scheduling algorithm for tasks set Question 1) case c) ...7
Table of Tables Table 1: Utilisation Bound U(n)...............................................................................................................4 Table 2: Tasks set Question 1) Case a) ................................................................................................5 Table 3: Tasks set Question 1) Case b) ................................................................................................5 Table 4: Tasks set Question 1) case c) .................................................................................................6
RMIT University © 2007 School of Electrical and Computer Engineering
3 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Scheduling 1
Introduction
Every system designed to execute a specific function is composed by different process. Each process requests frequently the exclusive use of the CPU; and very often, there are situations where two process are simultaneously ready to run. Then, the operating system is responsible to define which process is going to run every time. And this is done by a part of the operating system called the scheduler associated with a scheduling algorithm. Scheduling is the assignation, in a multiprogrammed application, of the CPU to processes in order to make the whole program behave accordingly to its design. Generally, there are two types of scheduling; preemptive and nonpreemtive. The former is when the CPU can be taken away from a process and nonpreemtive is when the CPU cannot be taken away. This assignment has to do with some practical exercises related with scheduling (Ferguson, R C, 2007).
2
Question 1
For each of the following cases, determine whether the set of task is schedulable using rate monotonic scheduling, given the utilisation bound table as follows: Number of Tasks n 1 2 3 4 Infinity
Utilisation Bound U(n) 1.000 0.8284 0.7798 0.7568 0.6931
Table 1: Utilisation Bound U(n)
Show working including timing diagrams (for the Completion Time Theorem) where required. If the entire set of 4 tasks is not schedulable determine the subset of task that are schedulable. For cases that fail the Utilisation Bound test also give the timing diagrams showing the execution of these tasks sets using the Earliest Deadline First (EDF) scheduling algorithm, starting with all tasks being released simultaneously. For EDF if instances of different tasks have the same deadline then the one with the earliest release time has the priority. a) Task
Period T
T1
12
RMIT University © 2007 School of Electrical and Computer Engineering
Computation Time C 3
Utilisation U 0.25
4 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
T2 T3 T4
15 3 20 3 25 5 Utilisation Bound U(4)
0.20 0.15 0.20 0.8
Table 2: Tasks set Question 1) Case a)
For this first case the Utilisation Bound Test fails because it is 0.8 which is bigger that 0.7568 as can be seen in Table 1. It means that these set of tasks exceed the processor utilisation. However, the fact that this test fails gives nothing to say about the feasibility of the set (Buttazzo G C, 1997). Therefore, it is necessary to draw the timing diagram for this set of tasks. For this the conventions showed in Figure 1 are used. And the length of the time line to be drawn is determined by the longest period (Burns A and Wellings A, 1996). In this case T4 with period T = 25. Figure 2 shows the diagram and as it can be seen of all of the tasks reach their deadline which means the set of tasks are schedulable. This confirms that the Utilisation Bound Test is sufficient but not necessary and in the cases where the set of tasks passes the test, it will meet all deadline; however, if the test fails, nothing can be said about that (Burns A and Wellings A, 1996).
Process Release Time
Deadline met
Pre-empted
Deadline missed
Excecuting
Figure 1: Conventions used for timing diagrams (Buttazzo G C, 1997)
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Figure 2: Timing Diagram for tasks set Question 1) case a)
b) Task T1 T2 T3 T4
Computation Time C 12 3 15 3 20 3 25 3 Utilisation Bound U(4)
Period T
Utilisation U 0.25 0.20 0.15 0.12 0.72
Table 3: Tasks set Question 1) Case b)
RMIT University © 2007 School of Electrical and Computer Engineering
5 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
In this case the set of task passes the Utilisation Bound Test and this give a certainty that the set is schedulable and all of the tasks will meet their deadlines. This can be seen in Figure 3
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Time
Figure 3: Timing Diagram for tasks set Question1) case b)
c) Computation Time C 12 3 15 3 20 5 25 5 Utilisation Bound U(4)
Task
Period T
T1 T2 T3 T4
Utilisation U 0.25 0.20 0.25 0.20 0.90
Table 4: Tasks set Question 1) case c)
This case the set fails the Utilization Bound Test. Figure 4 shows its time diagram and as it can be seen Task 4 misses its first deadline at t = 25, which means that the set of processes is not schedulable.
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Time
Figure 4: Timing Diagram for tasks set Question1) case c)
Any combination of three processes will pass the Utilisation Bound Test because it would be less than U(3) = 0.7798. UT1,T2,T3 = U1 + U2 + U3= 0.70 < 0.7798 UT1,T2,T4 = U1 + U2 + U4 = 0.65 < 0.7798 UT2,T3,T4 = U2 + U3 + U4 = 0.65 < 0.7798 UT1,T3,T4 = U1 + U3 + U4 = 0.70 < 0.7798
RMIT University © 2007 School of Electrical and Computer Engineering
6 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Figure 5 shows the executing of this set of tasks using the Earliest Deadline First (EDF) scheduling algorithm. As it can be seen all of the tasks meet their deadline, which means that using EDF algorithm the set of tasks is schedulable.
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31
32
33
34
35
36
37
38
39
40
Time
Figure 5: Timing Diagram using EDF scheduling algorithm for tasks set Question 1) case c)
3
Question 2
An embedded system contains the following independent software tasks:
Task M: Alarm Monitoring A set of 8 alarm sensors are connected to the processor via a slow-speed serial interface. It takes 75 milliseconds to transmit each individual monitoring transaction (for one alarm) across the link. The serial link is buffered so a delay in reading a transaction can be tolerated. Processing each individual monitoring transaction takes 20 milliseconds. The 8 alarms must each be scanned once every second. It is assumed that the alarms are scanned in sequence.
Task D: Display Driving A standard monitor is used to display the system status. The display subsystem has a dedicated graphics board. The display must be updated 25 times per second and it takes a maximum of 10 milliseconds to perform update.
Task C: Control The system performs closed-loop control of a multi-axis robot at a rate of 12 Hz, with a maximum processing time of 15 milliseconds for each loop.
Task L: Data Logging A data logging process runs four times a second, and takes a maximum of 25 milliseconds each time it runs. a) Develop a cyclic schedule for scheduling this set of processes. What is the major cycle period?. What is the minor cycle period?. Give the processes schedule for one major cycle. Note: The gcd test cannot be used as the task periods are not all integers.
RMIT University © 2007 School of Electrical and Computer Engineering
7 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Task D C M L
Scheduling Student: Wilson Castillo (s3143667)
Computation Time C (ms) 1/24 = 41.67 10 (1/24)*2 = 83.33 15 (1/24)*3 = 125 20 (1/24)*6 = 250 25 Utilisation Bound U(4) Period T (ms)
Utilisation U 0.24 0.18 0.16 0.10 0.68
Table 5: CPU Utilisation time
The major cycle is MCT = 250 ms. The minor cycle is mct = 1/24 = 41.667 ms mct
0 1 2 3 4 5
D D D D D D
C M C L C M
Figure 6: Timing Sequence. Question 2) part a)
b) How would you allow for an additional aperiodic task (Task A) that has a minimum period of 200 milliseconds, with an execution time of 12 milliseconds for each release?. Task D C M A L
Computation Time C (ms) 1/24 = 41.67 10 (1/24)*2 = 83.33 15 (1/24)*3 = 125 20 (1/24)*4.8 = 200 12 (1/24)*6 = 250 25 Utilisation Bound U(4) Period T (ms)
Utilisation U 0.24 0.18 0.16 0.06 0.10 0.74
Table 6: Adding a new aperiodic task A (T = 200ms, C = 12ms)
Being A an aperiodic task, it can be inserted at any slot time in 1 and 4. This is shown in the following figure.
mct
0 1 2 3 4 5
D D D D D D
C
A M
C L C
A M
Figure 7: New Task (A) added
RMIT University © 2007 School of Electrical and Computer Engineering
8 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
4
Scheduling Student: Wilson Castillo (s3143667)
References
Burns A, Wellings A, 1996, Real-Time Systems and Programming Languages, Second Edition, Addison-Wesley, Harlow, England. Buttazo G C, 1997, Hard Real-Time Computing Systems. Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, USA. Ferguson R C, 2007, Assignment 2, 2007, EEET1262 Real-Time Systems Design, School of Electrical and Computer Engineering, RMIT University, Melbourne, Australia. Ferguson R C, 2007, Real-Time Systems Design, Lecture Notes, School of Electrical and Computer Engineering, RMIT University, Melbourne, Australia Tanenbaum A S, 2001, Modern Operating Systems, Second Edition, Prentice Hall, Upper Saddle River, USA
RMIT University © 2007 School of Electrical and Computer Engineering
9 of 9 Melbourne, 14th May, 2007
Assignment 2: Scheduling
Lecturer: Prof. Roy Ferguson ([email protected]) Submision Date: 2007/05/14
Students:
Wilson Castillo Bautista ([email protected])
Subject Code: EEET1262 Real Time Systems Design
Melbourne, May 4th, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Table of Contents 1 2 3 4
Introduction ......................................................................................................................................4 Question 1 .........................................................................................................................................4 Question 2 .........................................................................................................................................7 References ........................................................................................................................................9
RMIT University © 2007 School of Electrical and Computer Engineering
2 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Table of Figures Figure 1: Conventions used for timing diagrams (Buttazzo G C, 1997) .........................................5 Figure 2: Timing Diagram for tasks set Question 1) case a).............................................................5 Figure 3: Timing Diagram for tasks set Question1) case b)..............................................................6 Figure 4: Timing Diagram for tasks set Question1) case c) ..............................................................6 Figure 5: Timing Diagram using EDF scheduling algorithm for tasks set Question 1) case c) ...7
Table of Tables Table 1: Utilisation Bound U(n)...............................................................................................................4 Table 2: Tasks set Question 1) Case a) ................................................................................................5 Table 3: Tasks set Question 1) Case b) ................................................................................................5 Table 4: Tasks set Question 1) case c) .................................................................................................6
RMIT University © 2007 School of Electrical and Computer Engineering
3 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Scheduling 1
Introduction
Every system designed to execute a specific function is composed by different process. Each process requests frequently the exclusive use of the CPU; and very often, there are situations where two process are simultaneously ready to run. Then, the operating system is responsible to define which process is going to run every time. And this is done by a part of the operating system called the scheduler associated with a scheduling algorithm. Scheduling is the assignation, in a multiprogrammed application, of the CPU to processes in order to make the whole program behave accordingly to its design. Generally, there are two types of scheduling; preemptive and nonpreemtive. The former is when the CPU can be taken away from a process and nonpreemtive is when the CPU cannot be taken away. This assignment has to do with some practical exercises related with scheduling (Ferguson, R C, 2007).
2
Question 1
For each of the following cases, determine whether the set of task is schedulable using rate monotonic scheduling, given the utilisation bound table as follows: Number of Tasks n 1 2 3 4 Infinity
Utilisation Bound U(n) 1.000 0.8284 0.7798 0.7568 0.6931
Table 1: Utilisation Bound U(n)
Show working including timing diagrams (for the Completion Time Theorem) where required. If the entire set of 4 tasks is not schedulable determine the subset of task that are schedulable. For cases that fail the Utilisation Bound test also give the timing diagrams showing the execution of these tasks sets using the Earliest Deadline First (EDF) scheduling algorithm, starting with all tasks being released simultaneously. For EDF if instances of different tasks have the same deadline then the one with the earliest release time has the priority. a) Task
Period T
T1
12
RMIT University © 2007 School of Electrical and Computer Engineering
Computation Time C 3
Utilisation U 0.25
4 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
T2 T3 T4
15 3 20 3 25 5 Utilisation Bound U(4)
0.20 0.15 0.20 0.8
Table 2: Tasks set Question 1) Case a)
For this first case the Utilisation Bound Test fails because it is 0.8 which is bigger that 0.7568 as can be seen in Table 1. It means that these set of tasks exceed the processor utilisation. However, the fact that this test fails gives nothing to say about the feasibility of the set (Buttazzo G C, 1997). Therefore, it is necessary to draw the timing diagram for this set of tasks. For this the conventions showed in Figure 1 are used. And the length of the time line to be drawn is determined by the longest period (Burns A and Wellings A, 1996). In this case T4 with period T = 25. Figure 2 shows the diagram and as it can be seen of all of the tasks reach their deadline which means the set of tasks are schedulable. This confirms that the Utilisation Bound Test is sufficient but not necessary and in the cases where the set of tasks passes the test, it will meet all deadline; however, if the test fails, nothing can be said about that (Burns A and Wellings A, 1996).
Process Release Time
Deadline met
Pre-empted
Deadline missed
Excecuting
Figure 1: Conventions used for timing diagrams (Buttazzo G C, 1997)
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Figure 2: Timing Diagram for tasks set Question 1) case a)
b) Task T1 T2 T3 T4
Computation Time C 12 3 15 3 20 3 25 3 Utilisation Bound U(4)
Period T
Utilisation U 0.25 0.20 0.15 0.12 0.72
Table 3: Tasks set Question 1) Case b)
RMIT University © 2007 School of Electrical and Computer Engineering
5 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
In this case the set of task passes the Utilisation Bound Test and this give a certainty that the set is schedulable and all of the tasks will meet their deadlines. This can be seen in Figure 3
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Time
Figure 3: Timing Diagram for tasks set Question1) case b)
c) Computation Time C 12 3 15 3 20 5 25 5 Utilisation Bound U(4)
Task
Period T
T1 T2 T3 T4
Utilisation U 0.25 0.20 0.25 0.20 0.90
Table 4: Tasks set Question 1) case c)
This case the set fails the Utilization Bound Test. Figure 4 shows its time diagram and as it can be seen Task 4 misses its first deadline at t = 25, which means that the set of processes is not schedulable.
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Time
Figure 4: Timing Diagram for tasks set Question1) case c)
Any combination of three processes will pass the Utilisation Bound Test because it would be less than U(3) = 0.7798. UT1,T2,T3 = U1 + U2 + U3= 0.70 < 0.7798 UT1,T2,T4 = U1 + U2 + U4 = 0.65 < 0.7798 UT2,T3,T4 = U2 + U3 + U4 = 0.65 < 0.7798 UT1,T3,T4 = U1 + U3 + U4 = 0.70 < 0.7798
RMIT University © 2007 School of Electrical and Computer Engineering
6 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Scheduling Student: Wilson Castillo (s3143667)
Figure 5 shows the executing of this set of tasks using the Earliest Deadline First (EDF) scheduling algorithm. As it can be seen all of the tasks meet their deadline, which means that using EDF algorithm the set of tasks is schedulable.
T1 T2 T3 T4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31
32
33
34
35
36
37
38
39
40
Time
Figure 5: Timing Diagram using EDF scheduling algorithm for tasks set Question 1) case c)
3
Question 2
An embedded system contains the following independent software tasks:
Task M: Alarm Monitoring A set of 8 alarm sensors are connected to the processor via a slow-speed serial interface. It takes 75 milliseconds to transmit each individual monitoring transaction (for one alarm) across the link. The serial link is buffered so a delay in reading a transaction can be tolerated. Processing each individual monitoring transaction takes 20 milliseconds. The 8 alarms must each be scanned once every second. It is assumed that the alarms are scanned in sequence.
Task D: Display Driving A standard monitor is used to display the system status. The display subsystem has a dedicated graphics board. The display must be updated 25 times per second and it takes a maximum of 10 milliseconds to perform update.
Task C: Control The system performs closed-loop control of a multi-axis robot at a rate of 12 Hz, with a maximum processing time of 15 milliseconds for each loop.
Task L: Data Logging A data logging process runs four times a second, and takes a maximum of 25 milliseconds each time it runs. a) Develop a cyclic schedule for scheduling this set of processes. What is the major cycle period?. What is the minor cycle period?. Give the processes schedule for one major cycle. Note: The gcd test cannot be used as the task periods are not all integers.
RMIT University © 2007 School of Electrical and Computer Engineering
7 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
Task D C M L
Scheduling Student: Wilson Castillo (s3143667)
Computation Time C (ms) 1/24 = 41.67 10 (1/24)*2 = 83.33 15 (1/24)*3 = 125 20 (1/24)*6 = 250 25 Utilisation Bound U(4) Period T (ms)
Utilisation U 0.24 0.18 0.16 0.10 0.68
Table 5: CPU Utilisation time
The major cycle is MCT = 250 ms. The minor cycle is mct = 1/24 = 41.667 ms mct
0 1 2 3 4 5
D D D D D D
C M C L C M
Figure 6: Timing Sequence. Question 2) part a)
b) How would you allow for an additional aperiodic task (Task A) that has a minimum period of 200 milliseconds, with an execution time of 12 milliseconds for each release?. Task D C M A L
Computation Time C (ms) 1/24 = 41.67 10 (1/24)*2 = 83.33 15 (1/24)*3 = 125 20 (1/24)*4.8 = 200 12 (1/24)*6 = 250 25 Utilisation Bound U(4) Period T (ms)
Utilisation U 0.24 0.18 0.16 0.06 0.10 0.74
Table 6: Adding a new aperiodic task A (T = 200ms, C = 12ms)
Being A an aperiodic task, it can be inserted at any slot time in 1 and 4. This is shown in the following figure.
mct
0 1 2 3 4 5
D D D D D D
C
A M
C L C
A M
Figure 7: New Task (A) added
RMIT University © 2007 School of Electrical and Computer Engineering
8 of 9 Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Assignment 2 Laboratory Report
4
Scheduling Student: Wilson Castillo (s3143667)
References
Burns A, Wellings A, 1996, Real-Time Systems and Programming Languages, Second Edition, Addison-Wesley, Harlow, England. Buttazo G C, 1997, Hard Real-Time Computing Systems. Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, USA. Ferguson R C, 2007, Assignment 2, 2007, EEET1262 Real-Time Systems Design, School of Electrical and Computer Engineering, RMIT University, Melbourne, Australia. Ferguson R C, 2007, Real-Time Systems Design, Lecture Notes, School of Electrical and Computer Engineering, RMIT University, Melbourne, Australia Tanenbaum A S, 2001, Modern Operating Systems, Second Edition, Prentice Hall, Upper Saddle River, USA
RMIT University © 2007 School of Electrical and Computer Engineering
9 of 9 Melbourne, 14th May, 2007
Related Documents
Scheduling
June 2020 19
Scheduling
June 2020 12
Scheduling
July 2020 9
Scheduling
November 2019 12
Scheduling-aggrement.pdf
December 2019 17