Showing posts with label os6. Show all posts
Showing posts with label os6. Show all posts

Thursday, August 13, 2009

Multiprocessor Scheduling

In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.

Real-Time Scheduling

>Static table-driven approach
>For periodic tasks.
>Input for analysis consists of : periodic arrival time, execution time, ending time, priorities.
>Inflexible to dynamic changes.
>General policy: earliest deadline first.
>Static priority-driven preemptive scheduling
>For use with non-RT systems: Priority based preemptive scheduling.
>Priority assignment based on real-time constraints.
>Example: Rate monotonic algorithm
>Dynamic planning-based scheduling
>After the task arrives before execution begins, a schedule is prepared that includes the new as >well as the existing tasks.
>If the new one can go without affecting the existing schedules than nothing is revised.
>Else schedules are revised to accommodate the new task.
>Remember that sometimes new tasks may be rejected if deadlines cannot be met.
>Dynamic best-effort scheduling:
>used in most commercial RTs of today
>tasks are periodic, no static scheduling is possible
some short-term scheduling such as shortest deadline first is used.
>Until the task completes we do not know whether it has met the deadline.

Thread Scheduling

>An application can be implemented as a set of threads that cooperate and execute concurrently in the same address space. Criteria: When related threads run in parallel pert. improves.
>Load sharing: pool of threads, pool of processors.
>Gang scheduling: Bunch of related threads scheduled together.
>Dedicated processor assignment: Each program gets as many processors as there are parallel threads.
>Dynamic scheduling: More like demand scheduling.