Ktl-icon-tai-lieu

Scheduling

Được đăng lên bởi Vương Xương Linh
Số trang: 27 trang   |   Lượt xem: 1458 lần   |   Lượt tải: 0 lần
Thoai Nam

Scheduling on UMA
Multiprocessors
Schedule:
allocation of tasks to processors

Dynamic scheduling
– A single queue of ready processes
– A physical processor accesses the queue to run the next
process
– The binding of processes to processors is not tight

Static scheduling
– Only one process per processor
– Speedup can be predicted
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Static scheduling
– An application is modeled as an directed acyclic graph (DAG)
– The system is modeled as a set of homogeneous processors
– An optimal schedule: NP-complete

Scheduling in the runtime system
– Multithreads: functions for thread creation, synchronization, and
termination
– Parallelizing compilers: parallelism from the loops of the sequential
programs

Scheduling in the OS
– Multiple programs must co-exist in the same system

Administrative scheduling
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

A parallel program is a
collection of tasks, some
of which must be
completed before others
begin
Deterministic model:
The execution time needed
by each task and the
precedence relations
between tasks are fixed
and known before run time

T1
-------2
T4
-------2
T2
------3
T3
-------1

T6
-------3

T5
-------3

Task graph
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

T7
-------1

Processors

Gantt chart indicates the time each task
spends in execution, as well as the
processor on which it executes
T4
T3

1

T2
2

3

T5
4

5

Time

T4
-------2
T2
------3

T6

T1

T1
-------2

6

T3
-------1

T7
7

8

9

T6
-------3

T5
-------3

T7
-------1

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

If all of the tasks take unit time, and the task graph is a
forest (i.e., no task has more than one predecessor), then a
polynomial time algorithm exists to find an optimal schedule
If all of the tasks take unit time, and the number of
processors is two, then a polynomial time algorithm exists to
find an optimal schedule
If the task lengths vary at all, or if there are more than two
processors, then the problem of finding an optimal schedule
is NP-hard.

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Graham’s list scheduling algorithm
T = {T1, T2,…, Tn}
a set of tasks
µ: T → (0,∞)
a function associates an execution time with each task
A partial order < on T
L is a list of task on T
Whenever a processor has no work to do, it instantaneously
removes from L the first ready task; that is, an unscheduled
task whose predece...
Để xem tài liệu đầy đủ. Xin vui lòng
Scheduling - Người đăng: Vương Xương Linh
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
27 Vietnamese
Scheduling 9 10 98