220400 -
! .
681.32
: . . .
. 220400 - / . . . -., .
.. , , 1998, 70 .
220400.
, .
. 7. . 35. .: 15 .
: . . . .. (),
. . . .. ().
-
1. .
2. , , .
3. .
4. 1000 .
5. , , , , .
6. .
7. , , .
8. , , .
9. . . .
10. .
11. , , .
1
|
|
- .
:
- ;
- 3;
- ;
- 4.
- .
SPT
. , , , SPT (Shortest-processing-task-first), ti, .. t1£t2£...£tL.
i i-1
ui zi ui= S tj, S tj-
j=1 j=1
, ti-
.
, u* . , u* u , , (a1,...,aL) , ak al, tal£ tak l>k, u, (a1,...,aL), ai - , i- , i=I,L. , ak al .
,
,
,
l>k, tal£ tak. , . (1,...,L) , t1£...£tL, , u* SPT .
RR
, , . SPT, , .
, , , , , RR (RoundRobin). .
l O, . q, . q, . .
. . , , , q. , l , s (1-s) . , , k ( k-1 k - ),
|
|
pk=sk-1(1-s), k=1,2,...
, Q q , , , Q / q, ,
, .
J, t . m , mq ³ t (.. m , ). J. J W1 . N1 ,
L=l+ls+ls2+¼+lsn+¼=l/(1-s)
( ) q. W1 {pk} , k .
W1= S kpk.
pk (m=1/q)
Si i ( ).
p`i =Lpi-1 - mpi - Lpi + mpi+1,
æ
í p`i =Lpi-1 - (m+L)pi + mpi+1, i=1,2,...
è p`0 = -Lp0 + mp1.
,
.
, .. , t¥.
Lpi-1 - (m+L)pi + mpi+1=0, i=1,2,...
- Lp0 + mp1=0,
p0 + p1 +... + pi +... =1.
p1 p0:
p1 = L/m* p0 ;
i=1.
: . k-
, .
,
.
pk
.
q J, q. , W1q . W1q J l . , sW1 W1 . J W2 :
W2 = lW1q + lq + sW1.
W1,
Wi = l Wi-1q + lq + s Wi-1 = r/(1-r).
J, m ,
wm = q = mqr/(1-r).
wm , Wi , J m . J
Um = wm +mq = mq/(1-r),
r = lq/(1-s) = lq/(q/Q) = lQ . wm , t=mq . w
,
, .
w wm:
.
, (mq>Q) , , (mq<Q) .
|
|
FB
. FB (foreground-background). :
O1. , O1, q. , . O2, O3,O4,...,On. . O1, . O2 , O1. Om , O1,..., Om-1 . , On, .
FB, , . , . FB . , , I,..., n n l1,..., ln. , .. , . O1, On. , , , Om , Om-1, m=2,n.
. , , . . , .. , , .
, , . , . , , , . . , , . .
|
|
, . STD (System Task Directory) , . STD. 0.1.
, . :
;
, ;
- ( ).
, . , , , .
. : .
,
[x] X; Ln ;
Lq , q, .
, . r Op. p=1,..., n
qp=2p-1q,
q , O1 .
, O1, O2, O3, O4,... q,2q,4q,8q,... .
1. ?
n ;
n ;
n .
2. SPT?
n ;
n ;
n .
3. SPT?
n ;
n ;
n .
4. RR(round-robin)?
n ;
n ;
n .
5. RR . ,
n ;
n ;
n .
6. ?
n ;
n ;
n .
7. RR
n ;
n ;
n .
8. FB(foreground-background)?
n ;
n ;
n , n-1 .
9. FB
n ;
n ;
n .
10.
n ;
n ;
n .
|
|
1. ( ).
2. SPT RR.
3. I II :
;
- .
:
(R);
(L).
R=40; L=5; LK<3 | |
R=50; L=6; LK<3 | |
R=60; L=7; LK<4 | |
R=70; L=8; LK<4 | |
R=40; L=7; LK<4 | |
R=60; L=6; LK<3 | |
R=50; L=5; LK<3 | |
R=70; L=9; LK<5 | |
R=80; L=7; LK<4 | |
R=60; L=4; LK<3 | |
R=50; L=7; LK<4 | |
R=70; L=7; LK<4 |
5.1.
5.2.
5.3.
5.4.
2
: LPT.
:
- ;
- 3;
- ;
- 4.
- .
n , L ;
t i, i = 1,..., L. , () , . . , 2- (3,3,2,2,2) . :
a)
)
T = T0 = θ
)
, - c, 0
q = max { max ti, 1/n *å ti }
q 0. , max t i - , (1/n *å ti), , , .. 100% .
n = 2 , NP-, .. , L. , , - , 0. , , , . , - .
1959 . n-1 .
q.
n=2,L=4, :(5,4,3,2).
q = max {5, 1/2 *(5+4+3+2) } =7.
, ,
:
.
, n-1 ( , ) .
, n-1.
L=n+1 t i = n, i= 1, n+1.
q = max { n, 1/n * (n+1)*n = n+1, , , :
T=n+1=q
, , n-1, . , n-1 . , [0,n+1]. , , n-1. 2 ( P k P l) . Z ik Z il [0,n] ( t=0, , Z ik Z il). t, t`, , n £ t < t` £ n+1, [ t, t` ] , .
, , , n-1, .