Scribd
Upload
4 views7 pages

HEFT Algorithm Solution

The document outlines the HEFT algorithm and its application in task scheduling with various tasks and priorities. It includes calculations for task priorities and resource allocation, detailing the earliest finish times for multiple tasks across different processors. The task priority list and resource allocation strategy are also presented, indicating how tasks are managed and scheduled efficiently.

Uploaded by

Bisma Maqbool
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views7 pages

HEFT Algorithm Solution

The document outlines the HEFT algorithm and its application in task scheduling with various tasks and priorities. It includes calculations for task priorities and resource allocation, detailing the earliest finish times for multiple tasks across different processors. The task priority list and resource allocation strategy are also presented, indicating how tasks are managed and scheduled efficiently.

Uploaded by

Bisma Maqbool
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Name: Pakiza Amin

HEFT Algorithm
cS-001
Reg #: FA24-P

t1 7
17 13
3 29

(t3
30

3
16

8
(79

42
a 7

719

Task
i7 P1 P2 ‫الت‬
171 125 148
t2 133 114 123.5
t3 26 131 78.5
th
57 145 192 168.5
120 184 152
78
t6 10 152
t7 114 30 72
78 126
50 88
t9 191 65 128
tl0 3 2 2.5

1. Tasie Priority list genoration:


Yank y = Wi + max +
upward rankR)b-level Calcalations: 2
Yantz (0) 2.5+0=2.5

YanR (0a) = 12 8 +7+ 2-5)-137-5


Yank (8) = 88 +42+2°5)=732-5
Yanle (07)= 72 t+2•5) =183.5

ran2 (tes = 81+eelS + 132.5)= 218.5

rank Lts) = 152 +"57 + 137-51=1346.5


rank(04) = 168:57 max( 7+137.5, 11+ 132.5)
168.5t max ( 144-52 143.5)
2 168.5+ 144.5 = 1313
Vank (#3) = 78.5 + max( 16+833 -178

Vank(62) = 123.5 + max(30+ 137.5, 3+132°5)


= 123.5+ max 167.5 135.5)
= 123.5 + 167.5 = 291

Yane (02) = 148+ max(177291, 314178,29+313


13+346.5,7+218.5)
= 148+ max( 308, 2095 342,
359.5, 225-5)
=148+ 359.5 = [507.51
Task priority list:

たかがっ2,tot3っで,48,3003
2. Resource Allocation:

EFT(N: Pi) = Wjj +EST (Ni, PS)


(AFT(nm)
favailIi]:
max
EST(ni: P) = max mEPracn,)
+ Cm,i)

Task 2 lentry node) = t, (pred=0)

EFT(t1sP1) =171 + man&0, max(0)} =171

maxf0, mancos } =125


EFT (t1 P2) = 125+

goes to P2
EFFLE, B t1
at 195 tim
e units
e
P2 is aveilabl

Task 52 ts (pred.= 1)
1,
, max (125+1
ma
3)3:258
EPT(ts, Pi) = 120 + ma
ma xx o
=309
max1125+013
25,, ma
$125
EFT (t5, P2)= 184+ man

ts goes to Pi
.
258 time unit
D is available at

→ Task 4= ty (pred. = 1)
EFT(tu, Pi) = 145 + max 9258, max/125+29}=403
EF TLt4,82) = 192 + max 9125, max(126+0)}- 317
tu goes to P

is aveilable at 317 time unifEFT(


P2
Task 2= t2 (pred. =1)

EFT(ts. таx3
P,) = 133+ ma x 258, max(125+17)
391

EFT(42, Po) = 114+ mox & 317, mox (125t0sf


=431

tz goes do Pi
391 time unts.
Pi is available at

Task 6 = t6 (pred. =1)


25 +7)}
EFT(t6, Pi) = 10 + mon
max & 391, mox(1
d 9771d3 2402
,χous +e5, σ216 (oοξεί)κααι

2 469

goes to Pi
to
at yo1 time urits-
Pi is available

→Task 3= t3 (pred. = 1)

EFTLt3 Pi)= 26+ max &401, max (125 +-303


=427

You might also like