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