Scheduling Algorithms for Multiprogramming in a Hard Real

Scheduling Algorithms For Multiprogramming In A Hard Real-Free PDF

  • Date:17 Aug 2020
  • Views:8
  • Downloads:0
  • Pages:16
  • Size:953.44 KB

Share Pdf : Scheduling Algorithms For Multiprogramming In A Hard Real

Download and Preview : Scheduling Algorithms For Multiprogramming In A Hard Real


Report CopyRight/DMCA Form For : Scheduling Algorithms For Multiprogramming In A Hard Real


Transcription:

Scheduling Algorithms for Multiprogramming 47, scheduling algorithms for this type of programming are studied both are priority. driven and preemptive meaning that the processing of any task is interrupted by. a request for any higher priority task The first algorithm studied uses a fixed. priority assignment and can achieve processor utilization on the order of 70 percent. or more The second scheduling algorithm can achieve full processor utilization by. means of a dynamic assignment of priorities A combination of these two algo. rithms is also discussed,2 Background, A process control computer performs one or more control and monitoring functions. The pointing of an antenna to track a spacecraft in its orbit is one example of such. functions Each function to be performed has associated with it a set of one or. more tasks Some of these tasks are executed in response to events in the equipment. controlled or monitored by the computer The remainder are executed in response to. events in other tasks None of the tasks may be executed before the event which. requests it occurs Each of the tasks must be completed before some fixed time has. elapsed following the request for it Service within this span of time must be guaran. teed categorizing the environment as hard real time 1 in contrast to soft. real time where a statistical distribution of response times is acceptable. Much of the available literature on multiprogramming deals with the statistical. analysis of commercial time sharing systems 2 contains an extensive bibliography. Another subset deals with the more interesting aspects of scheduling a batch. processing facility or a mixed batch time sharing facility usually in a multiple. processor configuration 3 8 A few papers directly attack the problems of hard. real time programming Manacher 1 derives an algorithm for the generation of. task schedules in a hard real time environment but his results are restricted to the. somewhat unrealistic situation of only one request time for all tasks even though. multiple deadlines are considered Lampson 9 discusses the software scheduling. problem in general terms and presents a set of ALGOLmultiprogramming procedures. which could be software implemented or designed into a special purpose scheduler. For the allocation of resources and for the assignment of priorities and time slots. he proposes a program which computes estimated response time distributions based. on the timing information supplied for programs needing guaranteed service He. does not however describe the algorithms which such a program must use. The text by Martin 10 depicts the range of systems which are considered to be. real time and discusses in an orderly fashion the problems which are encountered. in programming them Martin s description of the tight engineering management. control that must be maintained over real time software development is empha. tically echoed in a paper by Jirauch 11 on automatic checkout system software. These discussions serve to emphasize the need for a more systematic approach to. software design than is currently in use,3 The Environment. To obtain any analytical results about program behavior in a hard real time en. vironment certain assumptions must be made about that environment Not all of. Journal of the Assomation for Computing Machinery Vol 20 No I January 1973. 48 O L L I U AND J W L A Y L A N D, these assumptions are absolutely necessary and the effects of relaxing them will be. discussed in a later section, A1 The requests for all tasks for which hard deadlines exist are periodic with.
constant interval between requests, A2 Deadlines consist of run ability constraints only i e each task must be. completed before the next request for it occurs, A3 The tasks are independent in that requests for a certain task do not depend. on the initiation or the completion of requests for other tasks. A4 Run time for each task is constant for that task and does not vary with. time Run time here refers to the time wbich is taken by a processor to execute the. task without interruption, A5 Any nonperiodic tasks in the system are special they are initialization or. failure recovery routines they displace periodic tasks while they themselves are. being run and do not themselves have hard critical deadlines. Assumption A1 contrasts with the opinion of Martin 2 but appears to be valid. for pure process control Assumption A2 eliminates queuing problems for the in. dividual tasks For assumption A2 to hold a small but possibly significant amount. of buffering hardware must exist for each peripheral function Any control loops. closed within the computer must be designed to allow at least an extra unit sample. delay Note that assumption A3 does not exclude the situation in which the. occurrence of a task re can only follow a certain fixed number say h r of occur. rences of a task r Such a situation can be modeled by choosing the periods of tasks. r and re so that the period of re is N times the period of T and the Nth request for. r will coincide with the 1st request for re and so on The run time in assumption. A4 can be interpreted as the maximum processing time for a task In this way the. bookkeeping time necessary to request a successor and the costs of preemptions can. be taken into account Because of the existence of large main memories out of which. programs are executed and the overlapping of transfers between main and auxiliary. storage and program execution in modern computer systems assumption A4. should be a good approximation even if it is not exact These assumptions allow the. complete characterization of a task by two numbers its request period and its. run time Unless stated otherwise throughout this paper we shall use r l T2 r. to denote m periodic tasks with their request periods being T1 T T and. their run times being C1 C2 Cm respectively The request rate of a task is. defined to be the reciprocal of its request period. A scheduling algorithm is a set of rules that determine the task to be executed at a. particular moment The scheduling algorithms to be studied in this paper are pre. emptive and priority driven ones This means that whenever there is a request for a. task that is of higher priority than the one currently being executed the running. task is immediately interrupted and the newly requested task is started Thus the. specification of such algorithms amounts to the specification of the method of. assigning priorities to tasks A scheduling algorithm is said to be static if priorities are. assigned to tasks once and for all A static scheduling algorithm is also called a fixed. priority scheduling algorithm A scheduling algorithm is said to be dynamic if priori. ties of tasks might change from request to request A scheduling algorithm is said to. be a mixed scheduling algorithm if the priorities of some of the tasks are fixed yet the. priorities of the remaining tasks vary from request to request. Journal of the Association for Computing Machinery Vol 20 No 1 January 1973. Scheduling Algorithms for Multiprogramming 49,4 A Fixed Priority Scheduling Algorithm. In this section we derive a rule for priority assignment t h a t yields an optimum. static scheduling algorithm An important concept in determining this rule is t h a t of. the critical instant for a task The deadline of a request for a task is defined to be the. time of the next request for the same task For a set of tasks scheduled according to. some scheduling algorithm we say t h a t an overflow occurs at time t if t is the deadline. of an unfulfilled request For a given set of tasks a scheduling algorithm is feasible if. the tasks are scheduled so t h a t no overflow ever occurs We define the response time. of a request for a certain task to be the time span between the request and the end of. the response to t h a t request A critical instant for a task is defined to be an instant at. which a request for that task will have the largest response time A critical time zone. for a task is the time interval between a critical instant and the end of the response. to the corresponding request of the task We have the following theorem. THEOREM 1 A critical instant for any task occurs whenever the task is requested. simultaneously with requests for all higher priority tasks. PROOF Let i 2 Tm denote a set of priority ordered tasks with r being. the task with the lowest priority Consider a particular request for t h a t occurs at. tl Suppose t h a t between tl and tl Tm the time at which the subsequent request. of rm occurs requests for task T i m occur at t2 t2 T t2 t 2T t2 P. kT as illustrated in Figure 1 Clearly the preemption of T b y r will cause a certain. amount of delay in the completion of the request for r t h a t occurred at tl unless. the request for is completed before t2 Moreover from Figure 1 we see imme. diately t h a t advancing the request time t2 will not speed up the completion of. The completion time of m is either unchanged or delayed by such advancement. Consequently the delay in the completion of r is largest when t coincides with tl. Repeating the argument for all T i 2 m 1 we prove the theorem. One of the values of this result is t h a t a simple direct calculation can determine. whether or not a given priority assignment will yield a feasible scheduling algorithm. Specifically if the requests for all tasks at their critical instants are fulfilled before. their respective deadlines then the scheduling algorithm is feasible As an example. consider a set of two tasks r and T2 with T1 2 T2 5 and C1 1 C2 1 If we. let T be the higher priority task then from Figure 2 a we see t h a t such a priority. assignment is feasible Moreover the value of C2 can be increased at most to 2 b u t. not further as illustrated in Figure 2 b On the other hand if we let T2 be the higher. priority task then neither of the values of C and C2 can be increased beyond 1 as. illustrated in Figure 2 c,I t2 k l T,t2 t2 C i t2 Ti t 2 I ZT i t 2 kT i I.
FIG 1 E x e c u t i o n of r b e t w e e n r e q u e s t s for r. Journal of the Association for Computing Machinery Vol 20 No I January 1973. 50 C L LIU AND J W LAYLAND,I 2 3 4 5 I 2 5 4 5,Tzl I I l Tzl l l l I l. CRITICALTIM ZONE CRITICAL TIME ZONE,CRITICAL TIME ZONE. F G 2 Schedules for two tasks, The result in Theorem 1 also suggests a priority assignment that is optimum in the. sense that will be stated in Theorem 2 Let us motivate the general result by con. sidering the case of scheduling two tasks 72 and Let T1 and T be the request. periods of the tasks with T Te If we let r be the higher priority task then. according to Theorem 1 the following inequality must be satisfied 2. T Ti J Ci C T 1, If we let r2 be the higher priority task then the following inequality must be satis. LT2 T C LT TLI C2 LT2 T j T T2, 2 implies 1 In other words whenever the T T2 and C C2 are such that the.
task schedule is feasible with 75 at higher priority than n it is also feasible with n. at higher priority than 75 but the opposite is not true Thus we should assign higher. priority to n and lower priority to vs Hence more generally it seems that a. reasonable rule of priority assignment is to assign priorities to tasks according to. their request rates independent of their run times Specifically tasks with higher. request rates will have higher priorities Such an assignment of priorities will be. known as the rate monotonic priority assignment As it turns out such a priority. assignment is optimum in the sense that no other fixed priority assignment rule can. schedule a task set which cannot be scheduled by the rate monotonic priority. assignment, I t should be pointed o u t t h a t 1 is necessary b u t n o t sufficient to g u a r a n t e e the feasibility of. t h e p r i o r i t y assignment, L x denotes the largest integer smaller t h a n or equal to x x denotes the smallest in. teger larger t h a n or equal to x, Journal of the Associationfor Computing Machinery Vol 20 No 1 January 1973. Scheduling Algorithms for Multiprogramming 51, THEOREM 2 I f a feasible priority assignment exists for some task set the rate. monotonic priority assignment is feasible for that task set. PROOF Let r l r2 rm be a set of m tasks with a certain feasible priority. assignment Let r and re be two tasks of adjacent priorities in such an assignment. with r being the higher priority one Suppose that T T Let us interchange the. priorities of r and re It is not difficult to see that the resultant priority assignment. is still feasible Since the rate monotonic priority assignment can be obtained from. any priority ordering by a sequence of pairwise priority reorderings as above we. prove the theorem,5 Achievable Processor Utilization.
At this point the tools are available to determine a least upper bound to processor. utilization in fixed priority systems We define the processor utilization factor to be. the fraction of processor time spent in the execution of the task set In other words. the utilization factor is equal to one minus the fraction of idle processor time Since. CjT is the fraction of processor time spent in executing task r for m tasks the. utilization factor is, Although the processor utilization factor can be improved by increasing the values of. the C s or b y decreasing the values of the T s it is upper bounded by the require. ment that all tasks satisfy their deadlines at their critical instants I t is clearly. analysis of commercial time sharing systems 2 contains an extensive bibliography Another subset deals with the more interesting aspects of scheduling a batch processing facility or a mixed batch time sharing facility usually in a multiple processor configuration 3 8 A few papers directly attack the problems of hard real time programming Manacher 1 derives an algorithm for the

Related Books