实验三 进程调度
实验目
道程序设计中常干进程时处绪状态必须某种策略决定进程优先占处理机引起进程调度实验模拟单处理机情况处理机调度问题加深进程调度理解
二 实验求
1. 设计进程调度算法进程数定
2. 包含种调度算法加实现
3. 输出进程调度程——进程状态链表等
三 参考例
1. 题目——优先权法轮转法
简化假设
1) 进程计算型(IO)
2) 进程状态:readyrunningfinish
3) 进程需CPU时间时间片单位确定
2. 算法描述
1) 优先权法——动态优先权
前运行进程完时间片优先权减常数
2) 轮转法
开始
键盘输入进程数n调度方法选择
优先权法?
轮转法
产生n进程进程产生PCB机数产生进程优先权进程需CPU时间
优先权n进程拉成绪队列
初始化数结构区
链首进程投入运行
时间片进程需CPU时间减1优先权减3输出进程运行情况
需CPU时间0?
撤销进程
绪队列空?
结束
进程插入绪队列
N
Y
N
Y
Y
B
N
四 实验流程图
产生n进程进程机数产生进程轮转时间片数进程需时间片数已占CPU时间片数置0
进程产生先次序拉成绪队列链
链首进程投入运行
时间片进程需时间片数减1已占CPU时间片数加1
输出进程运行情况
进程需时间片数0?
撤销该进程
绪队列空?
占CPU时间片数轮转时间片数?
占CPU时间片数置0
该进程插入绪队列尾
B
N
Y
N
Y
Y
结束
N
注意:
1. 产生种机数取值范围加限制需CPU时间限制1~20间
2. 进程数n太通常取4~8
3. 动态数结构
4. 独立编程
5. 少三种调度算法
6. 请图形方式PCB调度图形成动画显示
五.实验程:
(1)输入:进程流文件(1txt)中存储系列执行进程 作业包括四数项:
进程名 进程状态(1绪 2等 3运行) 需时间 优先数(0级高)
进程0 1 50 2
进程1 2 10 4
进程2 1 15 0
进程3 3 28 5
进程4 2 19 1
进程5 3 8 7
输出 进程执行流等时间均等时间
程序包括FIFO算法优先数调度算法时间片轮转调度算法
(2)程序代码
#include
#include
#include
const int block_time10 定义时间片长度10秒
const int MAXPCB100 定义进程数
定义进程结构体
typedef struct node
{
char name[20]
int status
int time
int privilege
int finished
int wait_time }pcb
pcb pcbs[MAXPCB]
int quantity
初始化函数
void initial()
{
int i
for(i0i
strcpy(pcbs[i]name)
pcbs[i]status0
pcbs[i]time0
pcbs[i]privilege0
pcbs[i]finished0
pcbs[i]wait_time0
}
quantity0
}
读数函数
int readData()
{
FILE *fp
char fname[20]
int i
cout<<请输入进程流文件名
cin>>fname
if((fpfopen(fnamer))NULL)
{
cout<<错误文件开请检查文件名<
else
{
while(feof(fp))
{
fscanf(fps d d dpcbs[quantity]name&pcbs[quantity]status
&pcbs[quantity]time&pcbs[quantity]privilege)
quantity++
} 输出读入数
cout<<输出读入数<
cout<< <
return(1)
}
return(0)
}
重置数供算法
void init()
{
int i
for(i0i
pcbs[i]finished0 pcbs[i]wait_time0
}
}
先进先出算法
void FIFO()
{
int ij int total
输出FIFO算法执行流
cout<
cout<< <
}
total0
for(i0i
cout<<总等时间<
优先数调度算法
void privilege()
{
int ijp
int passed_time0
int total
int queue[MAXPCB]
int current_privilege1000
for(i0i
current_privilege1000
for(j0j
if((pcbs[j]finished0)&&(pcbs[j]privilege
current_privilegepcbs[j]privilege
}
}
queue[i]p
pcbs[p]finished1
pcbs[p]wait_time+passed_time
passed_time+pcbs[p]time
}
输出优先数调度执行流
cout<
cout<< <
total0
for(i0i
cout<<总等时间<
时间片轮转调度算法
void timer()
{
int ijnumberflag1
int passed_time0
int max_time0
int round0
int queue[1000]
int total0
while(flag1)
{
flag0
number0
for(i0i
if(pcbs[i]finished0)
{ number++ ji }
}
if(number1)
{ queue[total]j total++ pcbs[j]finished1 }
if(number>1)
{
for(i0i
if(pcbs[i]finished0)
{ flag1
queue[total]i
total++
if(pcbs[i]time
pcbs[i]finished1
}
}
}
}
round++
}
if(queue[total1]queue[total2])
{ total }
cout<
cout<
}
显示
void version()
{
cout<< ********************* 进程调度 ********************
cout<
void main()
{
int flag
version()
initial()
flagreadData()
if(flag1)
{ FIFO()
init()
privilege()
init()
timer()
}
}
(3)运行结果:
输入进程流文件名1txt出输出结果:
实验二 银行家算法
实验目
死锁会引起计算机工作僵死操作系统中必须防止实验目学生独立高级语言编写调试系统动态分配资源简单模拟程序解死锁产生条件原采银行家算法效防止死锁发生加深课堂讲授知识理解
二 实验求
设计n进程享m系统资源系统进程动态申请释放资源系统进程申请动态分配资源
系统显示进程申请释放资源系统动态分配资源程便户观察分析
三 数结构
1. 利资源量Available 含m元素数组中元素代表类利资源数目初始值系统中配置该类全部资源数目数值该类资源分配回收动态改变果Available(j)k标系统中现Rj类资源k
2. 需求矩阵Maxn×m矩阵定义系统中n进程中进程m类资源需求果Max(ij)k表示进程i需Rj类资源数目k
3. 分配矩阵Allocationn×m矩阵定义系统中类资源前分配进程资源数果Allocation(ij)k表示进程i前已分Rj类资源数目kAllocation i表示进程i分配量矩阵Allocation第i行构成
4. 需求矩阵Needn×m矩阵表示进程需类资源数目果Need(ij)k表示进程i需Rj类资源k完成务Need i表示进程i需求量矩阵Need第i行构成
述三矩阵间存关系:Need(ij)Max(ij)Allocation(ij)
四 银行家算法
Request i 进程Pi 请求量Request i (j)k表示进程Pi请求分配Rj类资源kPi发出资源请求系统述步骤进行检查:
1. 果Request i ≤Need转步骤2否认出错请求资源数已超前需求量
2. 果Request i ≤Available转步骤3否表示系统中尚足够资源满足Pi申请Pi必须等
3. 系统试探性资源分配进程Pi修改面数结构中数值:
Available Available Request i
Allocation i Allocation i+ Request i
Need i Need i Request i
4. 系统执行安全性算法检查次资源分配系统否处安全状态果安全正式资源分配进程Pi完成次分配否试探分配作废恢复原资源分配状态进程Pi等
假定系统5进程(p0p1p2p3p4)三类资源(ABC)种资源数量分1057T0时刻资源分配情况图:
Max Allocation Need Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
( 2 3 0 )
P1 3 2 2 2 0 0 1 2 2
(3 0 2 ) (0 2 0 )
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
五 安全性算法
1. 设置两量
Work:表示系统提供进程继续运行类资源数目包含m元素开始执行安全性算法时Work Available
Finish:表示系统否足够资源分配进程运行完成开始Finish(I)false足够资源分配进程Pi时令Finish(i)true
2. 进程集合中找满足述条件进程
Finish(i) false
Need i ≤work
找执行步骤3否执行步骤4
3. 进程Pi获资源利执行直完成释放出分配资源应执行
Work work + Allocation i
Finish(i)true转步骤2
4. 进程Finish(i)true表示系统处安全状态否系统处安全状态
六 系统流程图
开 始
输入资源数m 类资源总数初始化Available量
输入进程数ni1
输入进程i需求量max
i≤n
max≤资源总数
提示错误重新输入
i加1
选进程作前进程
输入该进程资源请求量Request
调银行家算法安全性算法完成分配出提示
该进程Need量0
该进程已运行结束
Need矩阵0
进程运行结束
结 束
N
Y
Y
N
N
Y
初始化need 矩阵
N
Y
七.银行家算法程序代码
#include
#include
#include
using namespace std
typedef struct Max1 资源需求量
{
int m_a
int m_b
int m_c
}Max
typedef struct Allocation1 已分配资源数
{
int a_a
int a_b
int a_c
}Allocation
typedef struct Need1 需资源数
{
int n_a
int n_b
int n_c
}Need
struct Available1 利资源量
{
int av_a
int av_b
int av_c
} q
struct pr 定义结构
{
char name
Max max
Allocation allocation
Need need
int finishflag
}p[5]
char na[5]
********************************************
void init() 读入文件1txt
{
cout<<进程需资源数NEED:<
fpfopen(1txtr+) 开文件1txt
for(int i0i<5i++)
{
fscanf(fpcdddddd\n&p[i]name&p[i]maxm_a&p[i]maxm_b
&p[i]maxm_c&p[i]allocationa_a&p[i]allocationa_b&p[i]allocationa_c)
p[i]needn_ap[i]maxm_ap[i]allocationa_a
p[i]needn_bp[i]maxm_bp[i]allocationa_b
p[i]needn_cp[i]maxm_cp[i]allocationa_c
cout<
} { << < return 1 data data<<> data<
fclose(fp) 关闭文件
}
***********************************************
int fenpei()分配资源
{
cout<
for(int j0j<5j++)
p[j]finishflag0
while(finishcnt<5)
{
for(int i0i<5i++)
{
if(p[i]finishflag0&&qav_a>p[i]needn_a&&qav_b>p[i]needn_b&&qav_c>p[i]needn_c)
{
qav_a+p[i]allocationa_a
qav_b+p[i]allocationa_b
qav_c+p[i]allocationa_c
p[i]finishflag1
finishcnt++
na[k++]p[i]name
break
}
}
count++禁止循环
if(count>5)return 0
}
return 1
}
****************************************************
int shq() 申请资源
{
int m0i0j0k0 m进程号 ijk申请三类资源数
cout<<请输入进程号请求资源数目<
if(i
if(i
p[m]allocationa_a+i
p[m]allocationa_b+j
p[m]allocationa_c+k
p[m]needn_ap[m]maxm_ap[m]allocationa_a
p[m]needn_bp[m]maxm_bp[m]allocationa_b
p[m]needn_cp[m]maxm_cp[m]allocationa_c
cout<<进程需资源数NEED<<'\n'
for(int w0w<5w++)
cout<
}
else
cout<
else
cout<
}
********************************************
void main()
{
int flag
char c
cout<< ******** 银 行 家 算 法******** <
init()
qav_a10 种资源数量
qav_b5
qav_c7
while(flag)
{
for(int i0i<5i++)
{
qav_a p[i]allocationa_a
qav_b p[i]allocationa_b
qav_c p[i]allocationa_c
}
if(fenpei())
{
cout<<样配置资源安全<
for(int k0k<5k++)
cout<<><
if(c'y'||c'Y')
{
if(shq())continue
else break
}
else flag0
}
else
{flag0
cout<<安全<
}
八.运行结果
实验三 存储理
. 实验目
存储理功合理分配空间请求页式理种常虚拟存储理技术
实验目通请求页式理中页面置换算法模拟设计解虚拟存储技术特点掌握请求页式存储理页面置换算法
二. 实验容
(1) 通计算算法命中率较算法优劣时考虑户存容量命中率影响
页面失效次数次访问相应指令时该指令应页存中次数
实验中假定页面1k户虚存容量32k户存容量4页32页
(2) produce_addstream通机数产生指令序列320条指令
A 指令址述原生成:
1) 50指令序执行
2) 25指令均匀分布前址部分
3) 25指令均匀分布址部分
B 具体实施方法:
1) [0319]指令址间机选取起点m
2) 序执行条指令执行址m+1指令
3) 前址[0m+1]中机选取条指令执行该指令址m’
4) 序执行条指令址m’+1指令
5) 址[m’+2319]中机选取条指令执行
6) 重复述步骤1)~5)直执行320次指令
C 指令序列变换称页址流
户虚存中k存放10条指令排列虚存址320条指令虚存中存放方式:
第0条~第9条指令第0页(应虚存址[09])
第10条~第19条指令第1页(应虚存址[1019])
第310条~第319条指令第31页(应虚存址[310319])
方式户指令组成32页
(3) 计算输出属算法存容量命中率
1) 先进先出算法(FIFO)
2) 少算法(LRU)
3) 佳淘汰算法(OPT)
4) 少访问页面算法(LFR)
中3)4)选择容
开 始
生成址流
输入算法号S
1≤S≤4
形成址页号
户存空间msize2
Msize≤32
OPT()
FIFO()
LRU()
LFU()
Msize加1
S
否算法继续
结 束
N
Y
1
2
3
4
Y
N
提示出错重新输入
三. 系统框图
四.页面置换算法程序代码:
#include
#include
#include
const int MAXSIZE1000定义页面数
const int MAXQUEUE3定义页框数
typedef struct node
{ int loaded int hit
}page
page pages[MAXQUEUE] 定义页框表
int queue[MAXSIZE]
int quantity 初始化结构函数
void initial()
{
int i
for(i0i
pages[i]loaded1
pages[i]hit0 }
for(i0i
queue[i]1
}
quantity0
} 初始化页框函数
void init()
{
int i
for(i0i
pages[i]loaded1
pages[i]hit0
}
} 读入页面流
void readData()
{
FILE *fp
char fname[20]
int i
cout<<请输入页面流文件名
cin>>fname
if((fpfopen(fnamer))NULL)
{
cout<<错误文件开请检查文件名
}
else
{
while(feof(fp))
{
fscanf(fpd &queue[quantity])
quantity++
}
}
cout<<读入页面流
for(i0i
cout<
} FIFO调度算法
void FIFO()
{
int ijpflag
int absence0
p0
cout<
for(i0i
for(j0j
if(pages[j]loadedqueue[i])
{ flag1 }
}
if(flag0)
{
if(absence>MAXQUEUE)
{ cout<
p(p+1)MAXQUEUE
absence++
}
}
absenceMAXQUEUE
cout<
{
int absence0
int ij
int flag
for(i0i
cout<
for(iMAXQUEUEi
for(j0j
if(queue[i]pages[j]loaded)
{ flagj }
} CAUTION pages[0]队列头
if(flag1)
{
缺页处理
cout<
pages[j]pages[j+1]
}
pages[MAXQUEUE1]loadedqueue[i]
absence++ }
else
{
页面已载入
pages[quantity]pages[flag]
for(jflagj
pages[j]pages[j+1]
}
pages[MAXQUEUE1]pages[quantity]
}
}
cout<
void version()
{
cout<< *******************虚拟存储理器页面调度****************<
void main()
{
version()
initial()
readData()
FIFO()
init()
LRU()
init()
init()
}
四. 运行结果
运行程序前先新建页面流文件文件(格式*txt)文件中存储系列页面号(页面号整数表示空格作分隔符)模拟换入页面例: 14 5 18 56 20 25 6 3 8 17
实验四 磁盘调度
实验目:
磁盘高速容量旋转型直接存取存储设备作计算机系统辅助存储器担负着繁重输入输出工作现代计算机系统中时会干求访问磁盘输入输出求系统采种策略佳次序执行访问磁盘请求磁盘访问时间受寻道时间T影响需采合适寻道算法降低寻道时间实验求学生模拟设计磁盘调度程序观察调度程序动态运行程通实验学生理解掌握磁盘调度职
二 实验题目:
模拟电梯调度算法磁盘进行移臂操作
三 提示求:
1 假设磁盘盘面磁盘移动头磁盘
2 磁盘供进程享存储设备磁盘时刻进程服务进程访问某磁盘时想访问该磁盘进程必须等直磁盘次工作结束进程提出输入输出请求处等状态时电梯调度算法干等访问者中选择进程访问磁盘设置驱动调度进程
3 磁盘处理器行工作磁盘进程服务时占处理器进程提出磁盘(里求访问磁道)动态申请访问磁道设置接受请求进程
4 模拟两进程执行考虑机数确定二者允许序程序结构图参考附图:
5 接受请求进程建立张进程请求IO表指出等访问磁盘进程求访问磁道表格式:
进程名
求访问磁道号
6 磁盘调度功查请求IO表等访问进程时电梯调度算法(SCAN算法)中选择等访问进程指定求访问磁道SCAN算法参考课第九章算法模拟框图略
7 图1中初始化工作包括:初始化请求IO表设置置前移臂方前磁道号假设程序运行前请求IO表中已干进程(4~8)申请访问相应磁道
四 实验报告:
1 实验题目
2 程序中数结构说明
3 印源程序附注释
4 实验结果容:印请求IO表前磁道号移臂方选中进程名求访问磁道否体现电梯调度(SCAN)算法
5 体会问题
五 附图:
开始
初始化
磁盘调度
机数>12
继续?
接受请求
输入[01]区间机数
结束
六.磁盘调度程序代码:
#include
#include
using namespace std
typedef struct node
{
int data
struct node *next
}Node
void main()
{
void fcfs(Node *intint)声明先先服务函数FCFS
void sstf(Node *intint)声明短寻道时间优先函数SSTF
void scan(Node *intint)声明扫描函数SCAN
void print(Node *) 输出链表函数
Node *head*p*q 建立链表
int itc0fs c链表长度f开始磁道号s选择算法
head(Node *)malloc(sizeof(Node))
head>nextNULL
qhead
cout<< **************磁盘调度算法***************<
cin>>it
while(it0)
{
p(Node *)malloc(sizeof(Node))
p>nextNULL
p>datait
q>nextp
qp
cin>>it
c++
}
cout<<号磁道开始
cin>>f f磁道号
print(head)
cout<<链表长度<
cin>>s
while(s0)
{
switch(s)
{
case 1cout<<选择先先服务算法FCFS<
break
case 2cout<<选择短寻道时间优先算法SSTF<
break
case 3cout<<选择电梯调度算法(扫描算法SCAN)<
break
}
cout<<退出请选0继续请选123
cin>>s
}
}
***********************************************************
void fcfs(Node *headint cint f)先先服务算法
{
void print(Node *)
Node *l*m*n
float num0 num均寻道长度
lhead>next
for(int i0i
num+abs(l>dataf)
fl>data
ll>next
}
numnumc
cout<<先先服务寻道序<
cout<<均寻道长度<
*****************************************************************
void sstf(Node *headint cint f)短寻道时间优先算法
{
void print(Node *)
Node *p*q*r*s*l*m
l(Node *)malloc(sizeof(Node))
l>nextNULL
ml
qhead
phead>next
shead
rhead>next
float num0
for(int i0i
int minabs(fr>data)
for(int j0j
pp>next
qq>next
if(abs(fp>data)
minabs(fp>data)
rp
sq
}
}
num+abs(fr>data)
fr>data
s>nextr>next
r>nextNULL
m>nextr
mr
qhead
phead>next
shead
rhead>next
}
numnumc
cout<<短寻道时间优先序<
cout<<均寻道长度<
***************************************************************
void scan(Node *headint cint f)扫描算法(电梯调度算法)
{
void print(Node *)
int minmaxi0j0
float num0
Node *p*q*r*s*m*n*x*y
r(Node *)malloc(sizeof(Node))存放开始磁道磁道
r>nextNULL
sr
m(Node *)malloc(sizeof(Node))存放开始磁道磁道
m>nextNULL
nm
x(Node *)malloc(sizeof(Node))
x>nextNULL
yx
qhead
phead>next
while(p>nextNULL)
{
if(p>dataf>0)
{
q>nextp>next
p>nextNULL
n>nextp
np
pq>next
i++
}
else
{
q>nextp>next
p>nextNULL
s>nextp
sp
pq>next
j++
}
}
if(p>data>f)
{
n>nextp
np
i++
}
else
{
s>nextp
sp
j++
}
qr 开始磁道磁道排序
pr>next
while(q>next>nextNULL)
{
qq>next
pq>next
maxq>data
while(p>nextNULL)
{
if(p>data>max)
{
maxp>data
p>dataq>data
q>datamax
maxq>data
}
pp>next
}
if(p>data>max)
{
maxp>data
p>dataq>data
q>datamax
maxq>data
}
}
print(r)
qm
pm>next
while(q>next>nextNULL)
{
qq>next
pq>next
minq>data
while(p>nextNULL)
{
if(p>data
minp>data
p>dataq>data
q>datamin
minq>data
}
pp>next
}
if(p>data
minp>data
p>dataq>data
q>datamin
minq>data
}
}
print(m)
xm
p>nextr>next
yx>next
while(y>nextNULL)
{
num+abs(fy>data)
fy>data
yy>next
}
num+abs(fy>data)
numnumc
cout<<扫描算法序<
cout<<均寻道长度<
*****************************************************
void print(Node *head) 输出链表
{
Node *p
phead>next
cout<<单链表显示
if(pNULL)
{
cout<<单链表空
}
else if(p>nextNULL)
{
cout<
}
else
{
while(p>nextNULL)
{
cout<
pp>next
}
cout<
}
七.运行结果:
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档