tailieunhanh - distributed operating system phần 5

Tham khảo tài liệu 'distributed operating system phần 5', công nghệ thông tin, đồ họa - thiết kế - flash phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | SEC. REAL-TIME DISTRIBUTED SYSTEMS 237 A third preemptive dynamic algorithm first computes for each task the amount of time it has to spare called the laxity slack . For a task that must finish in 200 msec but has another 150 msec to run the laxity is 50 msec. This algorithm called least laxity chooses the task with the least laxity that is the one with the least breathing room. None of the algorithms above are provably optimal in a distributed system but they can be used as heuristics. Also none of them takes into account order or mutex constraints even on a uniprocessor which makes them less useful in practice than they are in theory. Consequently many practical systems use static scheduling when enough information is available. Not only can static algorithms take side constraints into account but they have very low overhead at run time. Static Scheduling Static scheduling is done before the system starts operating. The input consists of a list of all the tasks and the times that each must run. The goal is to find an assignment of tasks to processors and for each processor a static schedule giving the order in which the tasks are to be run. In theory the scheduling algorithm can run an exhaustive search to find the optimal solution but the search time is exponential in the number of tasks Ullman 1976 so heuristics of the type described above are generally used. Rather than simply give some additional heuristics here we will go into one example in detail to show the interplay of scheduling and communication in a real-time distributed system with nonpreemptive static scheduling Kopetz et aL 1989 . Let us assume that every time a certain event is detected task 1 is started on processor A as shown in Fig. 4-30. This task in turn starts up additional tasks both locally and on a second processor B. For simplicity we will assume that the assignment of tasks to processors is dictated by external considerations which task needs access to which I O device and is not a