7 G4 T! l% K& ]. k! J7 t7 I. }' x
优先级调度算法
; d* M2 |5 ^! V }$ M8 z$ D算法介绍3 V: \, D" |5 s, @' S
优先调度算法的类型(用于作业调度)( ?# S9 W2 _/ J1 ?/ d
1)非抢占式优先权调度算法 $ c, e" K' I+ ?' f' E
系统一旦把处理机分配给优先权最高的进程后,便一直执行下去,至完成。 9 S/ Y, \9 M( @1 @0 H( Y
2)抢占式优先权调度算法 ! J& m4 w. {, ]- z9 q; S
只要系统中出现一个新的就绪进程,就进行优先权比较 。若出现优先权更高的进程,则立即停止当前执行,并将处理机分配给新到的优先权最高的进程。 优先权类型2 H" i# D) E, v7 x) }
1)静态优先权 9 V: q3 G4 z1 z
静态优先权在创建进程时确定,且在进程的整个运行期间保持不变。! V2 X2 B/ k# y4 Z* l! A* \
![]() 2)动态优先权
3 z, R) j/ J3 Z0 R) t: C![]() 算法实现抢占式动态优先权: ![]()
; o4 ~- @" f, u0 I$ v) APS:本人认为非抢占式静态优先权没有实际价值。
m* \/ o& o0 I. b9 [8 @; m
4 V8 A, R q' u7 ~; j# @7 \#include <stdio.h>
' J7 B' C8 A. a/ K `/ k) M- S0 i9 d A }. m
- M1 U, F8 N/ m& l; I0 e
1 i' f4 a9 h$ }7 E
#include <stdlib.h> # {) r7 v0 \, U: Q/ ]: y7 y% E$ A0 i
+ k) O' r% d5 x2 Q ?+ @
- 4 I% P8 Q( i% j, I8 f
; c5 E5 ^( H$ r: t
#include <string.h>
0 @/ ]# N, L1 X2 {; w( ?1 Y) {7 E1 c B4 r# p4 K1 }
0 H3 g# I! A3 h' c$ x3 ?" R3 D" I8 n4 n
typedef struct node
$ w% h' d7 H4 J" ]+ _4 l3 r) o( P
4 J3 P$ Q# Q# |" H9 [8 B5 H2 i
F" H8 m/ s; ?- u1 P: j% C5 j) e$ O6 b( q l2 k7 K4 M" @
{
% \: Z6 L# d; X! [3 y3 i* _% P: T4 R$ Z8 X9 {, F
- ' G/ ^5 `/ Z. `# x
% P$ B; z q8 j- J( y7 g- U& p char name[10]; /*进程标识符*/ % a5 q8 ], D$ ?8 R2 K" C
8 x, g% D2 _7 I2 L" U
; j- k6 j: L. M9 r
& \$ j$ o% U4 K2 z3 W* x/ ]- G$ S& y6 } a int prio; /*进程优先数*/ Y( ~' Z% |1 { @- f5 Q7 X
; P9 _9 z. R n* h. R
- & F. L6 x4 J& H% h" j
6 X! O: h( u9 H
int round; /*进程时间轮转时间片*/
$ Q5 Q( s2 n3 j! {$ w) z8 o H7 f1 h p3 y) m- T. V+ \2 B
$ F% O# B6 k! Y1 `3 O! k* p+ w% h8 `( a R( G; o k- b
int cputime; /*进程占用CPU时间*/
) ?+ d6 @ B. ~% j: X% d2 A/ M* \+ h2 n \1 m1 z! {1 H" c4 E
- . d& c1 x% j" p4 t; y" u: V5 `; O
) r- ~; K6 O1 U3 S% K6 S4 [% Z int needtime; /*进程到完成还要的时间*/ 4 m) y% n1 C; t. e6 S+ z# H
. D5 L8 g8 S$ O5 H' s7 Z
* I7 g$ E: a% T7 @9 }
+ J, C& n! ~. d7 s0 l. |2 H8 j! | int count; /*计数器*/
0 J9 G9 G) ^6 C- `
5 I) B+ V( v$ Q- 9 n+ g& f+ a, b( F& _
8 \7 d x k% F" ?7 [& a! W char state; /*进程的状态*/ 0 H) n* B7 |, \( S# c- S
; E1 h: [. ]3 E* k% i- a- B% i
- $ q' }3 J6 y! }! A+ ^8 S, I
( ^& g u0 ^! V \6 X0 k
struct node *next; /*链指针*/
/ I0 A+ O' L( r; y( G& w9 h! U( H$ H0 N
/ b% q" t! P; Y1 P! i `! u
9 s0 a4 y; c9 m7 P0 U6 U}PCB; % Y. B" r* n. A
; }2 u8 A" B& y M8 W/ v2 K
- 6 {2 }6 y& P- f4 M
5 q0 T; {0 ^* g9 A6 d; ^
PCB *finish,*ready,*tail,*run; /*队列指针*/ - W' F$ ~% G2 w3 D
C3 |6 a4 z6 n7 {3 b+ @8 n
- 8 |+ d- H# ^) Y1 D/ c7 l6 F$ Q
: U3 M; t2 X& Z; Q" n4 Jint N; /*进程数*/
7 k& Q+ Q/ N" p9 O$ p/ |0 [/ K) r, Q8 `8 i2 H" h$ x9 b
- 7 ?' p8 `, G* Y2 T' z4 e1 r6 f5 O$ S
# k9 O" {5 C2 a/*将就绪队列中的第一个进程投入运行*/ ; X- b4 R4 D4 f- b3 N9 T, J
! J3 h* R. B! k! |
2 O- J; K+ A6 n9 d1 i0 g0 B% ?5 C* D1 @% y6 l
firstin()
$ s# |5 C3 v3 ^. F# J- \" C
: @: @- `3 H' Z5 U- 6 v+ l; c" K0 P" |" Z# P1 l
0 E3 ~! h# l1 X* ?& {/ U8 O2 B{ ( j' l1 C5 g, G/ q6 r0 G
8 N5 H% p: R0 ?8 {/ m
* m8 C% x: o) \2 e% F6 a0 o& O( z+ V2 L4 @; }1 p5 A9 h0 i
run=ready; /*就绪队列头指针赋值给运行头指针*/
2 d9 n7 X8 E) _
p7 k7 v! A }, @ y2 n* X) Z- 1 ~' L3 J& @) |7 f! q1 A* i: a
, n5 T0 W m* j2 m/ V2 C run->state='R'; /*进程状态变为运行态*/
, I/ A% h2 z8 q
( s. n- f1 t" P7 r* _, t
# q: x/ D1 |; X( x! Z
$ X3 W# E% U D/ C* L7 |: ^ ready=ready->next; /*就绪对列头指针后移到下一进程*/
3 N0 h- u, c1 s" G2 B# p! j% x! _. [6 L D
- . Z6 p) M; n0 L
- m# K( `* F6 Q} 2 ]3 b- |$ B0 z \! | t) e% b( ]
' _$ [; _, ^/ m* Y7 O# V0 \
- {- d q2 \! F( l3 ?! s% t
2 k V" ~/ W5 w' n" N. B* X
/*标题输出函数*/ 4 I) Q- Z$ e F
1 R+ j) x5 W- \* Z
- 5 ^4 ]) _4 j" U8 W' o0 [% ~
4 g! ^" ]) M+ ovoid prt1(char a) 5 P' d7 ]: ~+ n9 y
! |- e5 a9 V' q- p# d+ ]
, O' A* J0 D1 \* _) f" i+ D& T7 j/ l2 d) F: P3 W
{
3 y' S, t1 n+ }, M3 E N4 T$ I8 @
6 x( N4 k0 o; a$ o7 X
5 W, L# \# a$ Y( e6 v. k+ m$ O2 w) w5 O4 a
if(toupper(a)=='P') /*优先数法*/ . a$ W& N5 ?* v( E/ ^1 Z" u
+ n8 t* K* D% a% ?6 f4 E: E- # b* p3 @) F2 G' S4 a
; F, j" K, ~; L9 @+ v
printf(" 进程号 cpu时间 所需时间 优先数 状态\n"); ! B, l; G" Q* |( l7 A
) w$ s2 k2 Q/ {% C8 n3 m- Y - 0 e4 S0 w9 m- d) G" s! y
4 E3 @; E+ p1 s6 [% k/ \ else + B5 ]! x* V6 B, Z* T9 K' m+ C4 e
5 @5 J9 h+ `5 `( i% p7 M
- * H% t6 M( I+ a# |+ R$ w
9 U2 ?, {' A1 M* T
printf(" 进程号 cpu时间 所需时间 记数 时间片 状态\n");
) ~ X+ m0 t/ r! w' y4 B. |
; Q8 L& Y8 o2 J2 m: }# C - 5 B: H. N# L0 o3 k+ m4 w& j, J
7 R6 D$ z& `1 u/ j/ y
} 8 B$ B; |3 a6 U: _( h: ?
$ D G7 [4 M! Y5 l/ X. {% Z& z9 O - ( I# C* v0 N1 g3 a% n( d
, V% S7 _$ t$ A! M4 v/*进程PCB输出*/
8 S- A8 h3 V6 {' Z0 c7 c! S, ?0 y
$ R& [6 n+ |9 ~, T$ D
+ ^' u6 u! h" z% ^7 m8 I* d, B+ Y- t) u7 \; J5 ]4 H/ N/ p6 W3 I
void prt2(char a,PCB *q) # F3 d, ?7 \+ Y
' n8 z- G3 ^6 H* X9 g" |0 H
! ]5 n$ `6 N( }. S4 L/ I' Q+ R1 U V
{
3 ~8 j& h- H! b. D0 Y. \8 l0 d& I. _
- , G4 D* J2 I t# m q L0 J8 c
/ n( G& G( I/ c. J' Z, Q
if(toupper(a)=='P') /*优先数法的输出*/
( g( h8 Z9 G6 J7 W( s. P% x
% F! E4 U+ N( F! t4 ^ - + d4 q2 [' I. @4 k: ^
2 A/ p. z% K8 @) r4 ]7 ^
printf(" %-10s%-10d%-10d%-10d %c\n",q->name, / L" `0 O) [' |4 w4 d
/ L, Z& [8 B) e, G+ I; T3 B
, U7 W8 e9 u' B1 Y2 m* m' \: F+ O; W; @! g1 Q* W
q->cputime,q->needtime,q->prio,q->state);
: Z9 W6 u7 r# d3 _1 d* K! r# {* Y8 i4 T- ^+ s
- * I1 _5 R3 ~5 H3 v$ `
2 H% t. X/ j* b3 _2 s4 o" ]+ t! [" v else/*轮转法的输出*/ % H7 Y7 i9 f# e
/ c5 Y y! d; G9 D6 Q& G& {% H- }
- ' L: L* e7 b8 Q" V& ]2 D
9 o" c# J$ X% D: _! u, y( e
printf(" %-10s%-10d%-10d%-10d%-10d %-c\n",q->name, + R5 _' j1 T9 H' y. S/ b) g4 _
' d5 W& F) O& K6 H3 _
8 ^7 J8 g: |' f) {6 b4 o( d% {! L+ A! }& }: O
q->cputime,q->needtime,q->count,q->round,q->state); 8 V6 G3 e, w2 s8 c
T1 z! o" b: g* y2 _7 \9 q5 t
( N; W$ O: I8 f [. B: s7 C8 r& \
}
3 x; Y/ F; y% @. Z% g; m* d; G
! Q& b8 P. C' f
! J7 r: k$ z3 ]
3 ?1 t; w+ z/ j$ C' B5 V6 L3 ~% k- |/*输出函数*/ : s$ x5 t( t5 I1 t' f( {
9 f3 r' b$ g/ ~9 k% n
- ; R; `+ x, o& l s0 [2 `
]0 r+ a- g0 |9 j& ?1 rvoid prt(char algo) ) V9 P; n3 M) m, F2 A
* S! V, M9 m5 J1 Y1 C9 M
* C0 i+ |& F4 m2 w5 B7 t9 H# x. ~+ I$ q
{
: B3 _6 a; R. [3 `' o: I0 [" [5 H0 C$ N2 Z
, i. g( V6 e; e! U1 U) v
' `- ?0 j) ~0 \: Y( N PCB *p; . k( o. m0 y2 z9 R" N' I6 I) \
( \0 Q* Q" t% `* k
- * t; f. ^* G$ m. e4 \* k3 M) O( V
, m2 e$ e! w w1 B
prt1(algo); /*输出标题*/ , d( l# L) y2 M5 L! e5 P; g
, H2 E4 [+ b2 L, k1 m - 6 d# @ P" B2 d S# h6 d9 l
4 ?9 g7 u. \( o4 K$ J, o+ s if(run!=NULL) /*如果运行指针不空*/
! A$ @% c; ~1 ]* z" {+ |$ A/ ^. L/ _9 k( i' S9 r. m- r
- " L: u1 Z) r Q4 C
: \' U2 Q' f7 ~* y$ @% m6 ]4 V prt2(algo,run); /*输出当前正在运行的PCB*/
6 o- D. f9 L$ l7 t" h- i( [6 z! I1 v$ W/ C2 I, A/ f6 `* b! ?1 D0 G
- $ \( v, {5 j' k3 Y7 _- E
% [! [3 Z6 @9 W+ p4 H! Y6 [ p=ready; /*输出就绪队列PCB*/ * N$ P y* ?; N! N" t4 z, H# G0 S
8 T0 q3 d1 l. d - + D- N4 j) f: X1 u9 r( z* f
3 z8 @2 ]. r+ @& b% E' Y* l% Q
while(p!=NULL) : I, a v3 \$ G! O
; V) P5 z/ a. y( f+ q- M7 D- K
: H) o0 V2 [# ?$ V0 u, i; p( x; w) m. e
{
, f# T( a* f" s( @# v& [) s" P2 w; ^# @4 k
& N9 `/ F5 k2 t2 j7 C" R
; Z1 N5 x. S i prt2(algo,p); 9 E/ _* Y7 _' T: n' T
0 G' I( H* w- a3 z. H- p
! F! l1 Y/ k" D# x. e# ?3 w2 A; N0 ]8 [+ u2 [+ H: f5 h$ ^
p=p->next;
- \9 y0 y# h$ h4 P7 Q- x3 g
+ k) R/ K5 G& A% I3 {' T0 R- # q1 G% ?7 u+ {: ?' v, p
% E7 w+ \/ S) {$ P0 z, w5 F9 l
}
6 B9 L' w: j4 N5 d0 n: }4 H- {5 [* K
& j5 v2 |; O9 {$ M% S3 ~( v. V, h }
" i" Z" }# _( M9 G4 Y0 R
* F5 @" B3 Z+ S: b0 y p=finish; /*输出完成队列的PCB*/
1 J! M, T$ J; }" |
7 E+ `# X. I- e% f; g
4 c8 S0 h! m" [/ ]7 e2 p4 d Z4 t
4 @( q; p) I+ T' {5 S while(p!=NULL) % Q0 c- F) i/ E; v+ E# m+ F& [
# R% e" L b8 ]! a! f
+ p$ z% D4 {# G) q. I! J2 y; j3 I* P0 C2 B$ b% F, D* f
{ ! {$ }' n3 `3 Y w1 W+ q4 M
# T6 Y( e0 C3 u( _& P- ! G% {" m' s! a: s% {
5 [4 j# {/ x" O+ u( e prt2(algo,p); " T" }, n6 [5 C# e$ X3 N; z
" o* d' q( t0 J" z - ' O5 J3 c# [* V; t3 B- ~- }
u9 a5 h. r/ @) i$ y# j p=p->next;
8 ?7 b* w9 \- U8 A' ]) m0 J
3 n! Y1 I7 G5 `7 L6 j7 P
! ^& E& s! r) h9 o; L- H; _+ O' K* J
}
2 x! w# `" h4 z% e; C7 U `3 C7 A/ N% h. f! O1 x! y
% V: O3 ~. {: y4 F8 F0 @% B
- ~+ Z1 J( T: h& M" u$ Q getchar(); /*压任意键继续*/ ; m R0 m7 I* K
6 o K) V4 m7 n# E
! O+ P5 L% h# ~
, w8 _( x1 G8 h9 X+ W1 t} : R t( b/ G8 r- a
* N% e) _/ n7 u# W& w3 L- 0 k4 D9 z5 f! o/ Z% w
' M0 @: T1 r4 \6 `( ~/*优先数的插入算法*/ + x9 m2 l2 ^+ L4 B" T* Z2 H
7 P$ U9 Q3 |* j7 `' S O
8 E. u5 P. r6 e9 m" n( h- A8 u- P, f# t
, k. l# y4 P [9 V" {8 K* hinsert1(PCB *q) ( k& E0 M3 Z, F. A& D, G
. }: c; o+ g( K2 h" Q% \4 f- 3 l( t' U* e, ^# J7 i
+ N |- ~2 _3 m1 _0 [% L
{
7 S" i% T/ j' ]0 B3 \9 X, _! [- y/ O; l+ \' H
6 `) a- T0 z. f
{1 q; `, I0 }2 ~8 i. z PCB *p1,*s,*r;
) [5 n: m8 H9 Z3 w t, C
1 W5 e2 {* \( [) f/ a- 4 M( e2 E- P( M
! s8 L- p- l! e3 [! ^3 g8 [4 I: [ int b; 7 A$ R8 v" v, l/ L- ?' M
) u9 ~4 x" s# G
- T" ?; x9 p) R8 D$ y
1 m' |$ d' F+ ?& l, f# U) ^) e s=q; /*待插入的PCB指针*/
$ O4 B! `; G) U! S( R/ f% e h9 @
8 n/ A1 ?/ t0 l! A. Q( ]+ O4 `, p- & f3 X+ T) W; r: ]# }/ x# [% k8 E
% n1 M+ V$ i2 G% B5 f! b p1=ready; /*就绪队列头指针*/ $ n5 ~* t5 q) i/ K
9 L. h& b/ a% h+ s8 j7 T
5 A- ^# Q( r2 E- _" v {0 ~' A
- v* o& }' {, J( R r=p1; /*r做p1的前驱指针*/ 3 |; H* M) y' Y) [* q1 L8 ]+ d4 o
6 {+ l+ X7 T: C: _
' n! Q m/ g2 k
6 z7 s% L+ |4 k4 I! F b=1; 8 N, }0 C6 U3 V8 o N, h" F9 T( T
$ J2 \/ R2 {' s/ T& n& U
- : F% P, F( V/ Q7 W
/ Z5 R8 r( I- u
while((p1!=NULL)&&b) /*根据优先数确定插入位置*/
* Y" i1 v0 i& m7 s( R* f. J$ N% P( C5 R9 ?
. D4 V: l, F: L' M0 S% ]8 U6 n2 n R# k3 n+ V
if(p1->prio>=s->prio)
" J6 Y j2 v6 @" b# j* y2 I
# X5 y) L4 N$ j8 q4 c- & Z8 l3 u, P4 N6 A7 b
N T" y7 z( I, u9 T { 8 ~* H9 U$ e g( d. u
1 x, Q' R: t" z! X9 _5 q* I+ F& B, j
- 2 o+ L& m2 ]$ I2 n
1 c5 m3 e; O4 m8 V0 a6 N7 p r=p1; ! X7 p i: N4 Y+ [* O; s
& E( L9 c* V( L% f7 ^ x) Q
) c; G* @4 e- g+ k3 h( u9 d; a5 K7 I$ F0 G
p1=p1->next; ' q9 U7 l. S2 L
5 D4 ]/ B7 p% q/ s1 |+ K
- " v/ k2 `: E9 {. @; m
$ L2 V" Q3 d w* y$ v* G
}
4 @2 Q5 B% Z* i4 j
' N0 r5 A+ H3 R; \* ~( ]8 H
( l: k/ }- `0 t, Q
) L8 f# n5 V* I$ {& F4 ^ else ; \ B8 X( ~" K; u' | O0 ^
9 h$ C: V4 a/ l! ?
/ q3 I& C: d, \& ?! ?; L' N
, I, S' l, Z" D# N b=0;
& ^: J4 P) L6 m3 m3 d! J
3 U0 G& S; \! c: P1 Q
0 ]: i1 w5 i+ { T& B! i/ U+ K8 K' \$ G3 T2 v' J$ H
if(r!=p1) /*如果条件成立说明插入在r与p1之间*/ & Z' C. q$ n1 @: q1 }2 t' a
# b9 [6 Y% O0 u+ i' l9 T) J
4 v; C+ [3 {! J6 m# j
* X$ ]' x- s3 \) Y) ]# ~ { 5 @) r) W/ \' V1 h" T
5 ^5 R4 y! ~! J+ _- & L# @* v# e# p2 t
. j+ H+ U. f0 B0 t( ^9 I
r->next=s; ?9 {+ |% @1 o2 l, @! m, m
f1 I& q$ b% ?0 m2 T" y, F - . }1 J5 ~9 n$ U
4 a& o+ s7 u. H
s->next=p1;
: P& F: u" F( s: t' M
/ l1 ~6 c4 j. y* e& O- v1 U2 [6 b - e! q0 K3 ]; { R5 `' Z/ s
, X% T, l, T$ H# O
}
/ t) o3 K* E; L' e) @8 `' k q/ z. R( U- ]) H
- ' T( m9 @1 h' E
0 g I& G$ W- N: ]6 f* q( Q0 W else + e1 h- l6 ~$ g0 {5 D* G, q
9 l% b+ v+ f, a6 d" M - ' L) [" [0 P" x9 t$ ?. o! D6 N" ~
0 \) k6 G0 _# d+ A& g1 c { & K6 m! r6 B. M+ ~
' \# ?4 u3 D$ t2 I - 6 M# ?) t7 F" f9 r8 h7 M/ {1 Y! T
( U% v# g) a9 r. m ?. I H
s->next=p1; /*否则插入在就绪队列的头*/
) |% N2 m# { r7 D
: R4 V1 m' \* H ^) J- n. G - : w( N1 n4 y+ J( j. E
" [ ~( Z! p5 t9 j+ k/ w ready=s; 4 ~# C% R2 |+ T) A3 B0 }. [
; p# r4 }4 W: F, B, g2 b
9 k' p1 a* b- x m6 i" X& P3 C, L2 C i* O
}
5 A. W: R/ c0 K! C% U$ `$ W7 L1 b8 I# T4 f
% y+ l L1 V9 E& H
0 _3 V, _- F& j7 b' Q9 z' ^+ Z} ! v& \; M8 y7 A' ^" g- h
( Z$ S6 e& a/ s m
- , r" t3 ^; [2 f1 j, y3 S5 P
# M: Z5 q) }, s/ U9 t
/*优先数创建初始PCB信息*/
* c& h0 e) G+ D; f+ S! t, N) p: S
" t8 C" F/ e+ \( _: E
( b) ?5 s3 m' q4 z( I- {! Y# P) y, t! D: o4 R) l& a
void create(char alg)
+ q. f! i% h5 p8 w4 n h
, l3 ~: r& d8 ~" S- 7 X P6 e6 X7 S8 R7 z
% t6 h' V+ E& i) H/ m1 G P
{ H, ]2 V3 T0 c( o3 m
8 @5 s7 n; \7 k7 t% F6 w+ d - ( ~. W: h+ Q+ s, S, F/ w# U( m
4 J$ `' X7 Z$ A PCB *p; 1 `8 U; f3 ^1 v! v" v# G
9 U) y$ p# S- U7 O
- / R( _: M+ N. Z! L
, N9 I5 @' N! X6 u+ o1 _1 B int i,time; P" J- m2 w. g0 O5 k: l- H
: X4 v% h( L. y0 E% G" ~
a; B6 Y6 O: K6 x1 M5 X. G$ s
4 G' l V4 Z) I5 G char na[10]; 7 r" `( B4 W, O g) f0 i
# _# U( ?& @0 v; y+ H
3 {" E! J7 P% }: w0 H3 u5 ^+ P7 Y" t2 W
ready=NULL; /*就绪队列头指针*/ 9 h: o1 H9 V: k! l
) t4 z+ ^! B; S/ o7 v: _
/ \( V& D, t+ ^1 b9 ]" I# q, j8 c9 [7 l5 o5 ^$ }6 W# Q, H
finish=NULL; /*完成队列头指针*/
H$ j+ F6 w+ \3 `! }; S$ x# i* P4 S' X7 s5 y
- * N+ k, ^: o; B1 L9 P( q& V5 s3 a
9 k# _! |5 ]. G run=NULL; /*运行队列指针*/
4 {" u/ ^ `) y, X9 i1 z5 |5 a' p0 x8 t
+ i z% C( [' s( V" H9 s. U' L, V8 o/ r/ G/ Q( v
printf("输入进程号和运行时间:\n"); /*输入进程标识和所需时间创建PCB*/
+ \' U2 q/ b4 r# L3 \: a, i+ @1 V4 o5 E c1 O# x# Z" {
- 7 G* m* N% B+ y% A/ [ |
9 i" [5 k6 B6 w" D. y! A5 | for(i=1;i<=N;i++)
( _0 Z" o: I; g- X1 z! }
; j( N* }# D. U - 5 s1 @% s L: w) R
& R# g* u* k4 x( Q* j% m { 4 l( L$ v& k5 S, S
' }" m$ @& ~. s3 k; a9 y1 q
5 |( Y6 |1 @% `, J7 o1 h" E
# B/ |" U; R, s7 W. M p=(PCB *)malloc(sizeof(PCB)); 4 D8 C: a5 Q' p; [
J1 g* d4 w" T- l- ! D4 t4 F) I% i& n) X# Z
2 K! Y2 u7 ~. ]3 x8 f
scanf("%s",na);
( ?+ M; a3 o6 Y# T u5 {
0 R) o, f, I; A% `' ^1 S, m
: z8 |6 F# m; H
7 [; q4 t1 X: F scanf("%d",&time);
5 j1 Q( S5 e9 h4 x- c. J# b2 c Q4 t
+ ]4 z- `' D" O( L: w, _. n
5 a; r c8 [! \5 n" k6 H$ r* o5 s- e
% m5 F( s* U+ g) C& _1 N9 ? strcpy(p->name,na);
$ o6 C! {- j6 j- E: V( p
: t6 B! L# T6 w- n. G& g
" n! B; d, {/ z5 j; d( p7 K0 U" G! Z* x! w/ Q' L: i8 `% X
p->cputime=0;
0 F T& q) S' H' d" l3 `% i, D. W
7 q8 t. }9 r# N- ) @8 x: `) ]& D% \/ Z( A) F" Q! j
7 n8 M' `: N$ H5 j& L p->needtime=time; ' I2 R% t# q2 v, s
9 b$ J# [9 s; [
A A. A8 B' Y6 K5 {
+ f0 s% `3 k# {& z p->state='w'; ' T1 L. E! M% X4 C+ L, ]6 P- k
+ v; X; V9 B2 s4 `; X( ]. v
5 q# x3 w8 h, o5 z8 O" a9 P0 N( b# M w6 T% n( {1 S
p->prio=50-time;
$ {' ^1 E5 w! B: Q; Y
) Y- x0 r4 b# O- 4 g3 r" x# m2 Y) Y6 Q$ H
* r3 w3 Y. K; X& p l1 v- n
if(ready!=NULL) /*就绪队列不空调用插入函数插入*/ ' F' z4 S4 T) c+ b1 i8 k* |
) [( M: A& i. v
; D# f2 u. l6 B
9 G( q' ^9 N% h& Z insert1(p); * j' v" a& `, K
- S: M* p0 i, Q5 U
J( b7 a. x$ Z5 v; P6 S; d
' P7 f* v/ H7 Y else * c- ^ g# s* C; p
+ O0 c: p+ _; F w0 T9 _
- 2 _6 n+ z7 _, u; J& X. r: \: W2 K9 i
2 {/ O; C6 @0 ?3 Y { . s0 p/ G2 s5 q/ x& h4 A' h5 D/ }
. q* H8 A9 D' ^4 L) }2 D, c4 F
1 y8 o- k9 y! g+ x5 T
: Y9 C U6 _9 S. U# o7 e7 B* h p->next=ready; /*创建就绪队列的第一个PCB*/ 3 C! A- z) n1 q* [
3 z7 y4 t2 N% @' J8 |) m
; I; S" `, F: s
5 k+ _% H- R2 w8 l. _: [ ready=p;
) j* `3 S# F* J, N% w# H
' I- x' z; {& h2 ]2 v- * e; v! z/ A2 I1 _
5 ?* C+ u! ] K2 V. o. t
}
/ {+ J& d& }, Y3 Y+ T2 y0 S0 C+ V+ b1 K
- : H$ B' O, N; V+ z5 P! N. L# o
! ~; T+ Y( g* d# ]7 z( c/ |9 v8 h } ' I; T a/ ]* r" i
* F E, z3 e. _4 ~1 ?
* B) P G& R; f$ T! n
6 ^% B. a) H5 [% J printf(" 优先数算法输出信息:\n"); * u, r: d8 W" u* ]! {
& [/ l$ k8 F7 W. W& w8 O$ t3 G
[. l1 p& Q) q: j" p4 b! C
+ R7 m5 x. U3 r" O' t! N printf("************************************************\n");
9 b; ]: f+ r0 M, u. u- M7 ]$ z6 x* O [0 l% C
- 2 n; j4 D: f4 w/ D0 M: C
, \! ?( A: X9 U4 Z* E7 |% ~ prt(alg); /*输出进程PCB信息*/
2 N) a- p/ _+ h
P; R+ c5 T/ O" l# K
" _0 m; X2 \2 O4 Y* g. h4 o0 A9 K4 w# \# ^( |. T
run=ready; /*将就绪队列的第一个进程投入运行*/ - e: `% X+ F! ] N) J
/ [% w; i5 _4 w) l# g0 h: w) V
! b1 \9 V7 }0 h) ? Y4 K7 k
( t1 i& d/ ?( k7 h' g' p; n ready=ready->next; 0 f( B9 K/ y& g% \' g
4 l8 b# t5 i! P8 }8 s
' s4 u9 f. s! H) i0 | h& _/ d
1 A/ [) Z# h/ B, y3 a- M run->state='R';
# T5 ^# _+ K" Z; ~3 x% Z6 Y6 L) M6 |2 E, m4 x# }# t
- % V3 v4 u0 t8 w' k: O
9 i( z4 t b' y" I" O# z5 e% ~/ F} 1 X7 Y" u9 M' v% z0 P
+ g( k! x: p. n& S4 D+ c - ) P1 [3 F; }) _) ]
i7 Z8 u! O) O! i9 l; I7 k, p/ S+ a8 n/*优先数调度算法*/
0 X6 B3 O, d& K/ k/ X6 v
- T4 l' ?( Y6 {& U) l - 0 |9 L8 u6 Q o; ?' S
1 s2 x9 z4 b: F" u7 N2 ^! {priority(char alg) & A% Q6 k. _/ Q2 |* t
+ z9 ^. z: R, c
- " A1 C W; {. r5 n0 G# v
8 G. B0 e' O+ T+ E, [) Y, @' @
{ - Q/ q% v% z# {; J1 l# c1 @; {
4 w4 @$ ]. K/ d! ?2 E- x$ A - % N) `( _1 \2 P
' Y* S V. T; j& O) s% [
while(run!=NULL) /*当运行队列不空时,有进程正在运行*/ / D$ B& Q: z5 X* F
* G3 D2 p5 k) R P: H# M* q/ n - 0 S, A8 _) O. ~# k( `& k
. O+ h$ K( R) {" N { 1 W4 L% }! k9 p& A; z6 Z5 I: N4 |
O- U. g" T5 F/ h' D& {
- 9 Q6 I+ {2 B: x ]9 e( ]7 m2 n
4 ~; T* }, b" X$ j& R run->cputime=run->cputime+1; 6 L. m$ B5 v' ^" S9 q% Q9 T
' ]* M2 L n/ X8 W
/ h7 I& O$ ?9 U& z- b, f# [: `. k- j
run->needtime=run->needtime-1; . d& K8 ~: _9 R. ]. j8 V
5 ~& [* k# E: [" ^
- + C+ ^& {5 s) D" t' S6 j0 h
) K. S6 E; R! Z- k+ N run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/
) b* |) f" E- }1 I$ S: Y
, o5 @/ Y( {, | - / k/ x7 [2 I' [1 P8 Y4 {
( K4 N' L' G3 N$ g" T& T PCB *p;
; W' Z% l* }5 y4 Y! r/ Z' l* W. ~4 `: J* Q5 U
- 2 r% ^( Z( b. j- }
3 p" H& f, e0 [1 ^
p=ready;
0 x4 b: K" M; B- ^' l* i
6 D/ n' k* d( H+ N
/ l. u- ^# y+ ^# {# _% N5 G2 Y* x% G! h4 c- z
while(p!=NULL)
, q9 [( C- j% ?0 D4 e4 F- `7 [, Z$ V% t( U: H( Q
- 6 @5 E8 @2 R- b
6 Z. I7 D V: ^7 M { ) b+ b' e3 `" X" ?. r
; R4 Z& ]# I3 G0 A8 ^5 ~" m, i
: M! j0 i8 E, w5 A/ `- e: Z5 T ?& I$ t% R/ t
p->prio=p->prio+1; /*每等待一次优先数升高1个单位*/ - z( _9 f2 R9 Y! A4 L, L' S7 f
$ ^' v6 Q' E& U& T3 b
. P: s6 }2 F& o0 S2 g' E) X8 h9 g8 G+ |6 n) h# ?# i* k9 S! ^3 P; X
p=p->next;
# ^' Y/ c/ O: @7 m! I
5 S6 r! D" E* ]" a$ I, T$ y- 7 m' J6 }5 P# ^0 A3 y" R
& Q4 x, [% S8 w) p) x } : g3 R7 Z" ~( L
/ A3 I/ c3 U b% Q- a) T) P
2 K5 n4 l9 g. a& p
, X7 |, o+ D$ ?) O if(run->needtime==0) /*如所需时间为0将其插入完成队列*/
' s' D& C% L# f9 A9 c1 I% ?" R8 o! X
" z" B9 A: I/ J9 N6 }6 X; o
7 j" Y6 b1 I/ p% Z- o {
1 _" I- p) s- B2 {1 N I# B1 [- P" q
/ [( F; v1 z, a. S7 Q' X; h
) X: d8 A z" E1 F) b7 w
3 U5 P+ ^: F) q run->next=finish; / T" F- n, P N. {0 [
" y# z/ x9 A$ L% \) c/ P9 G
- : G" v9 r7 s v Q# h
% e4 m9 K/ H1 | finish=run;
, r F& l9 J m! G/ c4 i) V: y& K' l" S7 y
9 k5 g5 {& Q! G- D/ W9 h/ i
' N4 T6 f* R( O! \0 A run->state='F'; /*置状态为完成态*/ 7 T% Z: b( H, W$ l
, S, B8 T/ ^ ]7 R
6 L7 P: y1 { ]" Y$ p
9 K8 i2 g- c3 \0 q" ?& m$ h run=NULL; /*运行队列头指针为空*/ - P4 M! p2 ?7 i2 y7 ?& v$ K
0 K) P4 i, l4 I# y' V( L4 h8 g$ ]+ U
/ T3 Z& e- C- C) \! T
4 o1 r6 ]9 I8 d) E% z% g if(ready!=NULL) /*如就绪队列不空*/
' E: j9 }' n& _
+ a) I/ m0 L- h. U+ o# @- 1 ^: w0 K+ l8 I \8 f
" s" F$ u/ b* P" ?
{ / l2 Y- F5 n1 C+ \' r' i* g
2 k. c q9 A* v: k$ t1 e( y1 u - 6 {7 v. P, |. e' C
, w# ]1 P* I: J: x2 w. [4 Z0 Q
firstin(); /*将就绪对列的第一个进程投入运行*/
2 M5 f9 D. R# E& U; `( N
* c% U! S0 H6 S; V1 q2 ` - : y! z8 F! }" s( F
& M6 u/ `; u3 _$ z$ z5 [; }5 {- R$ t
}/ s# k- |2 L; E4 w5 G
) z7 C5 q& s1 T& ~
5 R6 t0 J$ E9 r( c& H, m/ b2 h7 H. }
} + \. J: B- p5 w
9 s8 J. K Y; r
- 6 z5 P1 L7 O {7 g- G# t7 G
0 c( o) l7 K* ] J& |
else /*没有运行完同时优先数不是最大,则将其变为就绪态插入到就绪队列*/ 4 ?9 J0 X0 R: p* F% v, L
, x2 o! n% N; M* S1 x$ Z* E
- ! }% @, C1 R: ?
; T, a9 s# u. R" q5 K( {( s: k
if((ready!=NULL)&&(run->prio<ready->prio))
/ T& X1 U. \- H$ k$ k8 W9 |6 x$ d( Z% A/ O
/ ?; e# i z- |6 E
: c; N" o- U, l0 a% a0 S0 z {
$ l0 M' B! U/ d' G& A' p. q# C4 q
4 e8 }& s& @6 M2 T4 q# \5 ]$ l7 `) }/ g, [9 ?- U a
run->state='W'; ( s v& I; J5 S
) A: X8 m& a* a! w7 @
- ; }- g9 S. p( g/ g, _1 x
4 I+ K# i" @' j) M' o insert1(run);
* ]9 g4 X0 K: n% z% t; h/ w$ J. R, R; v3 }2 z/ P# D2 D3 Q: w
' k g* B& _# B. q$ \7 f/ a6 Z$ c2 C9 s( h: {: i9 n( w6 H
firstin(); /*将就绪队列的第一个进程投入运行*/ " _7 J# M" d8 s6 b1 h( T, i+ P
/ g8 Y' G) p D' x0 o; d
- k& G; o" f, p2 G G `8 E: Y+ t6 N* M, S+ c0 |
}
* \, ^9 F- b: j, H0 o; z8 d2 ~# O; a4 w' K) x" b
- 3 D3 c, o: \ C. l; ~9 w
* z4 L2 F7 W8 {. a4 x: X
prt(alg); /*输出进程PCB信息*/ $ r k" i/ w% W# ?: R! W( z
$ Y) @1 s: d2 |8 Q! j
2 A9 B! M- d1 S7 [! f- p0 l; O' o! U+ E: ]: L) K" a9 b- u3 i
} 9 f" b, t& s2 B. j! Y5 V
0 o2 _# m1 H: A: @) i* K
/ ^5 R2 |% _- w9 d/ t
' ^$ w/ z1 L7 Q2 _} ) T( e: }- C. d
5 q* `5 i1 X# H- E7 [
7 z7 M% o7 ] ^% R2 R {9 {+ K
$ u" A+ U- ` ^& @1 l9 D/*主函数*/
( o3 \7 q# a# F& c C3 L* g: w L
; k- K8 d, ]! v& H
* |& c5 r m: I W- h2 u8 s+ F
main()
3 S4 |- b* \& v0 _3 `! w" w1 X, e. _
- $ f: a E) e- m5 {; O3 ]" O
! K8 G5 L2 l# D# S3 |: G; F7 G
{ . T8 f5 E1 I9 Q9 i
9 a6 u. Y) |" }1 |( n0 Q - 1 G1 M8 m* i# H
6 ?6 W/ i1 v- ^) F char algo; /*算法标记*/
& k& l+ I7 l* I4 L3 p m1 k
+ L, F+ a" A: C) m; [+ O: {
$ u6 p5 o# S4 Y9 g% ^2 c0 d
. H- p" ~2 D: |/ F# T% Y7 B1 K printf("输入P确定算法:优先数算法\n");
6 ^. k [, o6 E% H8 X6 Y; {# A w
9 M0 k/ p6 E/ h# e
2 h. x! m2 _ |7 ]1 X5 T scanf("%c",&algo); /*输入字符确定算法*/
, O6 L- p6 [5 @; S( H
; y/ m# _3 K& X( n2 X! [- 7 D8 @" [( [5 Z
5 |& K+ o! z0 E printf("输入进程数:\n"); , |4 F& [& i7 B
3 X, u9 I S# t) ?
- y2 W* O) x# ]& |
8 Q" u) n1 I1 ?, q scanf("%d",&N); /*输入进程数*/ : h0 v# W* r5 U! x- R
( B- e2 }! n5 k* l9 S
- 7 h8 j3 W# `+ b, ^
! o" V0 d, ?7 f# f
if(algo=='P'||algo=='p')
; W) w4 d6 R6 u7 d* p8 J2 z/ E6 ^) E4 X/ y' M
- : L* N+ w* F! }& K; m
; W& C$ B* _0 Y, ^' p { 5 o, w w2 K# e% q
8 T8 W& n- B5 e: L - * s6 J- B; I, c) V" {1 ~) F& x
! y! H0 ?* c* E; `% Y& [% f create(algo); /*优先数法*/ 6 U( w3 B4 O: [0 F3 q, J
, ?9 U; S) a3 P+ z6 w
+ U" |4 D; ^6 p o- m% w
5 r6 `: O4 V+ w priority(algo); * W( e2 g) c6 }0 W& I1 V, W
2 C5 m) \& L- G* Y- I" m
. O4 p: x* ~% i7 k
) _) z$ {! N2 V' O: V } ) U; u2 h a" J! v; S5 c1 R3 v
' g( R; }9 N0 t) S& r$ v/ R
$ t; t* _& q' f4 K
* c1 w+ Z+ R0 S}
9 m" m3 N$ j( G
* f" ?- _. p7 t6 ~8 ^0 V; C1 j5 y R! K" x) }
! x' q, [. A1 y/ n输出结果:/ E/ }7 O& q2 i
![]()
; Z7 F, ^$ p% i) Y' Z! |& N$ U原文:https://blog.csdn.net/weixin_40962955/article/details/80072769 : s; s: F, z6 H. m2 i( u
9 `4 y! J$ K, d. }7 m5 S8 T
|