文章目录
一、实验内容(1)优先权法、轮转法(2) 算法描述
二、流程图动态优先级(左)——轮转法(右)
三、实现思路四、完整代码及输出(1)完整代码(2)输出
一、实验内容
(1)优先权法、轮转法
简化假设 1) 进程为计算型的(无I/O) 2) 进程状态:ready、running、finish 3) 进程需要的CPU时间以时间片为单位确定
(2) 算法描述
1) 优先权法——动态优先权 当前运行进程用完时间片后,其优先权减去一个常数。 2) 轮转法
参考书本:计算机操作系统第四版 汤小丹 梁红兵等编
二、流程图
动态优先级(左)——轮转法(右)
三、实现思路
(1)如何表示进程,一个进程应该包含哪些必要信息 在操作系统中,每个进程都有一个专用数据结构PCB——进程控制块来记录os所需的,用于描述进程的当前情况以及管理进程运行的全部信息。一般包含进程标识符、处理机状态、进程调度信息,进程控制信息四个部分。
本实验只是模拟处理机调度,所以我选择创建一个pcb类来表示进程,该PCB类的属性包括进程序号id(表示到达的先后顺序)、状态state、开始执行时间starttime、执行结束时间endtime、所需执行时间cputime,剩余执行时间restoftime,已运行时间runtime。还包括显示pcb的方法。
我将所有的进程保存在一个列表中,表示他们都是0时刻进入内存,id表示到达顺序。
具体代码如下
class PCB :
def __init__(self
, id, prior
, cputime
) :
self
.id = id
self
.prior
= prior
self
.dy_prior
= prior
self
.cputime
= cputime
self
.runtime
= 0
self
.restoftime
= cputime
self
.state
= 0
self
.starttime
= 0
self
.endtime
= 0
def outSituation_dy(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + '\t' +"动态优先级:%-3d" + " 当前状态:%-7s" + " 进程所需CPU时间:%-2d" +
" 还需时间:" + str(self
.restoftime
))%(self
.dy_prior
,state_temp
,self
.cputime
))
def outSituation_rr(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + " 当前状态:%-7s" + " 进程所需CPU时间:%-2d" +
" 还需时间:" + str(self
.restoftime
))%(state_temp
,self
.cputime
))
def outall_dy(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + '\t' +"静态优先级:%-3d" + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间:%-2d" +
" 结束运行时间:%-3d"+" 还需时间:" + str(self
.restoftime
))%(self
.prior
,state_temp
,self
.cputime
,self
.starttime
,self
.endtime
,))
def outall_rr(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间:%-2d" +
" 结束运行时间:%-3d"+" 还需时间:" + str(self
.restoftime
))%(state_temp
,self
.cputime
,self
.starttime
,self
.endtime
,))
(2)只要输入进程数并选择算法,初始化的进程队列全部是随机产生。代码如下
def init(num
) :
pcbList
= []
for i
in range(num
) :
pcbList
.append
(PCB
(i
, random
.randint
(1, 9), random
.randint
(1, 20)))
print("刚生成的各进程")
for i
in pcbList
:
i
.outSituation_dy
()
print('\n')
return pcbList
(3)在动态优先级中,采用冒泡排序来给队列优先级排序。相同优先级,先到达的排在前面。
(4)在流程图中,存在就绪队列。我只有一个存放pcb的列表。所以我每次执行完队首进程,将当前进程列表重新排序,保证每次执行的队首进程永远是可执行的优先级最大的进程。
四、完整代码及输出
(1)完整代码
import random
class PCB :
def __init__(self
, id, prior
, cputime
) :
self
.id = id
self
.prior
= prior
self
.dy_prior
= prior
self
.cputime
= cputime
self
.runtime
= 0
self
.restoftime
= cputime
self
.state
= 0
self
.starttime
= 0
self
.endtime
= 0
def outSituation_dy(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + '\t' +"动态优先级:%-3d" + " 当前状态:%-7s" + " 进程所需CPU时间:%-2d" +
" 还需时间:" + str(self
.restoftime
))%(self
.dy_prior
,state_temp
,self
.cputime
))
def outSituation_rr(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + " 当前状态:%-7s" + " 进程所需CPU时间:%-2d" +
" 还需时间:" + str(self
.restoftime
))%(state_temp
,self
.cputime
))
def outall_dy(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + '\t' +"静态优先级:%-3d" + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间:%-2d" +
" 结束运行时间:%-3d"+" 还需时间:" + str(self
.restoftime
))%(self
.prior
,state_temp
,self
.cputime
,self
.starttime
,self
.endtime
,))
def outall_rr(self
) :
state_temp
= ''
if self
.state
== 0:
state_temp
= 'ready'
elif self
.state
== 1:
state_temp
= 'running'
elif self
.state
== 2 :
state_temp
= 'finish'
print(("进程:" + str(self
.id) + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间:%-2d" +
" 结束运行时间:%-3d"+" 还需时间:" + str(self
.restoftime
))%(state_temp
,self
.cputime
,self
.starttime
,self
.endtime
,))
def init(num
) :
pcbList
= []
for i
in range(num
) :
pcbList
.append
(PCB
(i
, random
.randint
(1, 9), random
.randint
(1, 20)))
print("刚生成的各进程")
for i
in pcbList
:
i
.outSituation_dy
()
print('\n')
return pcbList
def sort_dy_pcblist(pcbList
):
for i
in range(1,len(pcbList
)):
for j
in range(0,len(pcbList
)-1):
if pcbList
[i
].dy_prior
> pcbList
[j
].dy_prior
:
pcbList
[i
], pcbList
[j
] = pcbList
[j
], pcbList
[i
]
for i
in range(len(pcbList
)-1):
if pcbList
[i
].dy_prior
== pcbList
[i
+1].dy_prior
:
if pcbList
[i
].id > pcbList
[i
+1].id:
pcbList
[i
],pcbList
[i
+ 1] = pcbList
[i
+ 1], pcbList
[i
]
if pcbList
[0].state
== 2 :
for i
in range(1,len(pcbList
)):
if pcbList
[i
].state
== 0 :
pcbList
[i
],pcbList
[0] = pcbList
[0],pcbList
[i
]
break
return pcbList
def sort_rr_pcblist(pcbList
):
pcbList
.append
(pcbList
[0])
del pcbList
[0]
if pcbList
[0].state
== 2 :
for i
in range(1,len(pcbList
)):
if pcbList
[i
].state
== 0 :
pcbList
[i
],pcbList
[0] = pcbList
[0],pcbList
[i
]
break
return pcbList
def dy_prior_method(pcbList
) :
count
= 0
while pcbList
[0].state
== 0:
print("这是第%d次时间片"%count
)
if pcbList
[0].dy_prior
== pcbList
[0].prior
:
pcbList
[0].starttime
= count
pcbList
[0].state
= 1
pcbList
[0].runtime
+= 1
pcbList
[0].dy_prior
-= 3
pcbList
[0].restoftime
-= 1
for i
in pcbList
:
i
.outSituation_dy
()
if pcbList
[0].restoftime
== 0:
pcbList
[0].state
= 2
pcbList
[0].endtime
= count
else :
pcbList
[0].state
= 0
sort_dy_pcblist
(pcbList
)
count
+= 1
print(" 动态优先级 总 体 情 况 ")
Turnaround_time
= 0
daiquan_time
= 0
for j
in range(len(pcbList
)):
for i
in pcbList
:
if i
.id == j
:
i
.outall_dy
()
for i
in pcbList
:
Turnaround_time
+= i
.endtime
- i
.starttime
+1
daiquan_time
+= (i
.endtime
-i
.starttime
+1)/i
.cputime
print(('平均周转时间:%.2f'+' 平均带权周转时间%.2f')%(Turnaround_time
/len(pcbList
),daiquan_time
/len(pcbList
)))
def rr_method(pcbList
) :
rr_time
= random
.randint
(1,5)
count
= 0
time
= 0
while pcbList
[0].state
== 0 :
print("这是第%d次时间片"%count
)
time
+= 1
if pcbList
[0].dy_prior
== pcbList
[0].prior
:
pcbList
[0].starttime
= count
pcbList
[0].dy_prior
= 21
pcbList
[0].state
= 1
pcbList
[0].runtime
+= 1
pcbList
[0].restoftime
-= 1
for i
in pcbList
:
i
.outSituation_rr
()
if pcbList
[0].restoftime
== 0:
pcbList
[0].state
= 2
pcbList
[0].endtime
= count
sort_rr_pcblist
(pcbList
)
time
= 0
else :
pcbList
[0].state
= 0
if time
== rr_time
:
time
= 0
sort_rr_pcblist
(pcbList
)
count
+= 1
print(" 轮转法 总 体 情 况 ")
print("轮转时间片 q = "+str(rr_time
))
Turnaround_time
= 0
daiquan_time
= 0
for j
in range(len(pcbList
)) :
for i
in pcbList
:
if i
.id == j
:
i
.outall_rr
()
for i
in pcbList
:
Turnaround_time
+= i
.endtime
- i
.starttime
+ 1
daiquan_time
+= (i
.endtime
- i
.starttime
+ 1) / i
.cputime
print(('平均周转时间:%.2f' + ' 平均带权周转时间%.2f') % (Turnaround_time
/ len(pcbList
), daiquan_time
/ len(pcbList
)))
def main() :
pcbNum
= int(input("输入进程数量(4,8):"))
print("请从以下方法中选择一种进程调度方法")
print("(1)动态优先级法 (2)轮转法")
method
= int(input())
pcbList
= init
(pcbNum
)
if method
== 1 :
dy_prior_method
(pcbList
)
else :
rr_method
(pcbList
)
if __name__
== '__main__' :
main
()
(2)输出
先输出随机数生成的原始进程数据再输出每个时间片的进程运行情况最后输出进程的总体执行情况(周转时间等)
只展示轮转法的部分输出