OS操作系统课程实验指导书附运行截图

实验1使用动态优先权的进程调度算法的模拟

1、实验目的

（1）加深对进程概念的理解

（2）深入了解系统如何组织进程，创建进程

（3）进一步认识如何实现处理机调度

2、实验内容

（1）实现对N个进程采用动态优先权优先算法的进程调度。

（2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：

进程标识数ID。

进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高。

进程已占用的CPU时间CPUTIME。

进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0。

进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，将进入阻塞状态。

进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，将转换成就绪状态。

进程状态STATE。

队列指针NEXT，用来将PCB排成队列。

（3）优先数改变的原则：

进程在就绪队列中停留一个时间片，优先数加1。

进程每运行一个时间片，优先数减3。

（4）假设在调度前，系统中有5个进程，它们的初始状态如下：

ID 0 1 2 3 4

PRIORITY 9 38 30 29 0

CPUTIME 0 0 0 0 0

ALLTIME 3 3 6 3 4

STARTBLOCK 2 -1 -1 -1 -1

BLOCKTIME 3 0 0 0 0

STATE ready ready ready ready ready

（5）为了清楚的观察各进程的调度过程，程序应将每个时间片内的情况显示出来，参照的具体格式如下：RUNNING PROG：i

READY-QUEUE：->id1->id2

BLOCK-QUEUE：->id3->id4

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = == = =

ID 0 1 2 3 4

PRIORITY P0 P1 P2 P3 P4

CUPTIME C0 C1 C2 C3 C4

ALLTIME A0 A1 A2 A3 A4

STARTBLOCK T0 T1 T2 T3 T4

BLOCKTIME B0 B1 B2 B3 B4

STATE S0 S1 S2 S3 S4

3、实验结果（给出编写的程序源代码和运行结果的截图）

【程序代码】

#include

#include

#define N 5

// 进程状态

enum STATE { Ready, Run, Block, Finish };

// PCB数据结构

struct PCB {

int id; // 标志数

int priority; // 优先数

int cpuTime; // 已占CPU时间

int allTime; // 还需占CPU时间int blockTime; // 已被阻塞的时间int startBlock; // 开始阻塞时间

STATE state; // 进程状态

PCB *pre; // PCB的前指针

PCB *nxt; // PCB的后指针};

int id[N] = {0, 1, 2, 3, 4};

int priority[N] = {9, 38, 30, 29, 0};

int cpuTime[N] = {0, 0, 0, 0, 0};

int allTime[N] = {3, 3, 6, 3, 4};

int startBlock[N] = {2, -1, -1, -1, -1};

int blockTime[N] = {3, 0, 0, 0, 0};

void QuePush(PCB *process, PCB *queHead)

{

process->pre = NULL;

process->nxt = queHead->nxt;

if (queHead->nxt != NULL) {

queHead->nxt->pre = process;

}

queHead->nxt = process;

}

void quePop(PCB *process, PCB *queHead)

{

if (process->pre != NULL) {

process->pre->nxt = process->nxt;

} else {

queHead->nxt = process->nxt;

}

if (process->nxt != NULL) {

process->nxt->pre = process->pre;

}

process->pre = process->nxt = NULL;

}

void queWalk(PCB *queHead)

{

PCB *pro = queHead->nxt;

if (pro == NULL) {

printf("(没有进程啦)\n");

return;

}

while (pro != NULL)

{

printf("id: %d, priority: %d, cpuTime: %d, alltime: %d,blockTime: %d,state:%d,startblock: %d\n", pro->id, pro->priority, pro->cpuTime, pro->allTime, pro->blockTime, pro->state, pro->startBlock);

pro = pro->nxt;

}

}

int readyQueNum; // 就绪队列的进程数量

PCB readyQueHead; // 就绪队列的头部

PCB *readyMaxProcess; // 就绪队列中优先级最高的进程

void readyQuePush(PCB *process)

{

readyQueNum ++;

process->state = Ready;

QuePush(process, &readyQueHead);

}

PCB* readyQuePop()

{

readyQueNum --;

quePop(readyMaxProcess, &readyQueHead);

return readyMaxProcess;

}

// 每个时间片，更新就绪队列里进程的信息void readyQueUpdate()

{

int maxPriority = -1;

PCB *pro = readyQueHead.nxt;

if (pro == NULL) {

// 就绪队列没有进程

readyMaxProcess = NULL;

return;

}

while (pro != NULL)

{

pro->priority ++;

if (pro->priority > maxPriority) {

maxPriority = pro->priority;

readyMaxProcess = pro;

}

pro = pro->nxt;

}

}

// 返回就绪队列最高优先级的值

int readyMaxPriority()

{

return readyMaxProcess->priority;

}

// 查看就绪队列里进程的信息

void readyQueWalk()

{

printf("就绪队列里的进程信息为：\n");

queWalk(&readyQueHead);

}

#define EndBlockTime 3 // 进程最长被阻塞时间

int blockQueNum; // 阻塞队列的进程数量

PCB blockQueHead; // 阻塞队列的头部

PCB *blockMaxProcess; // 阻塞队列中优先级最高的进程

// 进程插入到阻塞队列

void blockQuePush(PCB *process)

{

blockQueNum ++;

process->blockTime = 0;

process->state = Block;

if (process->blockTime != -1) {

QuePush(process, &blockQueHead);

}

}

// 优先级最高的进程出列

PCB* blockQuePop()

{

blockQueNum --;

quePop(blockMaxProcess, &blockQueHead);

return blockMaxProcess;

}

// 每个时间片，更新阻塞队列里进程的信息

void blockQueUpdate()

{

int maxPriority = -1;

PCB *pro = blockQueHead.nxt;

while (pro != NULL)

{

pro->blockTime ++;

if (pro->blockTime >= EndBlockTime) {

PCB *process = pro;

pro = pro->nxt;

// 阻塞时间到，调入就绪队列

blockQueNum --;

quePop(process, &blockQueHead);

readyQuePush(process);

} else if (pro->priority > maxPriority) {

// 更新阻塞队列里优先级最高的进程指针

maxPriority = pro->priority;

blockMaxProcess = pro;

pro = pro->nxt;

}

}

}

// 查看阻塞队列里进程的信息

void blockQueWalk()

{

printf("阻塞队列里的进程信息为：\n");

queWalk(&blockQueHead);

}

// 初始化数据

void initData()

{

// 初始化就绪队列和阻塞队列

readyQueNum = blockQueNum = 0;

readyMaxProcess = blockMaxProcess = NULL;

readyQueHead.pre = readyQueHead.nxt = NULL;

blockQueHead.pre = blockQueHead.nxt = NULL;

// 初始化进程进入就绪队列

int i, maxPriority = -1;

for (i = 0; i < N; i ++)

{

// 分配一个PCB的内存空间

PCB *pro = (PCB *)malloc(sizeof(PCB));

// 给当前的PCB赋值

pro->id = id[i];

pro->priority = priority[i];

pro->cpuTime = cpuTime[i];

pro->allTime = allTime[i];

pro->blockTime = blockTime[i];

pro->startBlock = startBlock[i];

if (pro->allTime > 0) {

// 插入到就绪队列中

readyQuePush(pro);

// 更新就绪队列优先级最高的进程指针

if (pro->priority > maxPriority) {

maxPriority = pro->priority;

readyMaxProcess = pro;

}

}

}

}

// 模拟cpu执行1个时间片的操作

void cpuWord(PCB *cpuProcess)

{

cpuProcess->priority -= 3;

if (cpuProcess->priority < 0) {

cpuProcess->priority = 0;

}

cpuProcess->cpuTime ++;

cpuProcess->allTime --;

// 显示正执行进程的信息：

printf("CPU正执行的进程信息为：\n");

printf("id: %d, pri: %d, alltime: %d\n", cpuProcess->id,

cpuProcess->priority, cpuProcess->allTime);

}

int main()

{

int timeSlice = 0; // 模拟时间片

int cpuBusy = 0; // 模拟cpu状态

PCB *cpuProcess = NULL; // 当前在cpu执行的进程

initData(); // 初始化

// 模拟进程调度

while (1)

{

if (readyQueNum == 0 && blockQueNum == 0 && cpuBusy == 0) { // 就绪队列、阻塞队列和cpu无进程，退出

break;

}

if (cpuBusy == 0) {

// cpu空闲，选择一个进程进入cpu

if (readyQueNum > 0) {

// 选择绪队列优先级最高的进程

cpuProcess = readyQuePop();

} else {

// 就绪队列没有进程，改为选择阻塞队列优先级最高的进程

cpuProcess = blockQuePop();

}

cpuProcess->cpuTime = 0;

cpuProcess->state = Run;

cpuBusy = 1;

cpuProcess->startBlock --;

}

timeSlice ++;

printf("\n第%d个时间片后：\n", timeSlice);

// 模拟cpu执行1个时间片的操作

cpuWord(cpuProcess);

if (cpuProcess->allTime == 0) {

cpuProcess->state = Finish;

// 释放已完成进程的PCB

free(cpuProcess);

cpuBusy = 0;

}

// 更新就绪队列和阻塞队列里的进程信息

blockQueUpdate();

readyQueUpdate();

// 查看就绪队列和阻塞队列的进程信息

readyQueWalk();

blockQueWalk();

if ((cpuProcess -> startBlock) > 0) {

blockQuePush(cpuProcess);

cpuProcess = readyQuePop();

}

else {

if (cpuBusy == 1 && readyQueNum > 0 && cpuProcess->priority < readyMaxPriority())

{

readyQuePush(cpuProcess);

cpuProcess = readyQuePop();

}

}

}

printf("\n模拟进程调度算法结束2145115 刘成路\n");

return 0;

}

【运行截图】

实验2使用动态分区分配方式的模拟

1、实验目的

（1）了解动态分区分配方式中使用的数据结构和分配算法

（2）加深对动态分区存储管理方式及其实现过程的理解。

2、实验内容

（1）分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。

（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：

?作业1申请130KB。

?作业2申请60KB。

?作业3申请100KB。

?作业2释放60KB。

?作业4申请200KB。

?作业3释放100KB。

?作业1释放130KB。

?作业5申请140KB。

?作业6申请60KB。

?作业7申请50KB。

?作业6释放60KB。

分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。

3、实验结果（给出编写的程序源代码和运行结果的截图）

【程序代码（首次适应算法）】

按照地址大小排序

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

struct ready_node{//就绪的进程

int id;//进程编号

int flag;//表是进程的状态，1：表示进入内存，0：表示从内存撤出

int size;//进程长度

};

struct free_node{//空闲区域表的结构体，首地址和长度

int id;//保存在该区域的进行号

int start;//首地址

int len;//长度

};

vector free_list;//保存空闲区域表的内容，分别是区域首址和区域长度vector used_list;//保存已占用区域表的内容，分别是区域首址和区域长度queue ready_list;//就绪的进程队列，主要保存第一次匹配为成功的进程queue wait_list;//等待的进程队列

//函数定义

int cmp(free_node a,free_node b);//定义排序的比较方式

void Show();//显示空闲区域表和已占用表的信息

void Init();//初始化等待序列

void Alloc(ready_node node);//动态分区分配函数

void Free(ready_node node);//回收过程函数

void Oper_FIRO();//操作函数

void Print();//显示最后控制台的空想区域表的状态,输入文件中

int main()

{

//重定向输入输出，对文件进行操作

freopen("input.txt","r",stdin);

freopen("output8.txt","w",stdout);

Init();//一定先进行初始化

printf("2145115 刘成路\n");

Oper_FIRO();

return 0;

}

int cmp(free_node a,free_node b){//定义排序的比较方式

return a.start

}

void Show(){//显示空闲区域表和已占用表的信息

sort(free_list.begin(),free_list.end(),cmp);//操作之前首先按首地址从小到大排序printf("-----------------------\n");

printf("| 空闲链表的使用情况: |\n");

printf("-----------------------\n");

printf("---------------\n");

printf("| 首址| 长度|\n");

printf("---------------\n");

for(int i=0;i

printf("| %3d | %3d |\n",free_list[i].start,free_list[i].len);

printf("---------------\n");

}

printf("-------------------------\n");

printf("| 已占用链表的使用情况: |\n");

printf("-------------------------\n");

printf("----------------------------\n");

printf("|运行进程| 首址| 长度|\n");

printf("----------------------------\n");

for(int i=0;i

printf("| %3d | %3d | %3d |\n",used_list[i].id,used_list[i].start,used_list[i].len);

printf("----------------------------\n");

}

}

void Init(){//初始化等待序列

free_node fnod;

fnod.start=0; fnod.len=640;//初始化空闲表

free_list.push_back(fnod);

ready_node node;

while(scanf("%d%d%d",&node.id,&node.flag,&node.size)!=EOF){

wait_list.push(node);

//cout<

}

}

void Alloc(ready_node node){//动态分区分配函数

sort(free_list.begin(),free_list.end(),cmp);//操作之前首先按首地址从小到大排序

//cout<

free_node fnod;

int ok=0;//表示是否匹配成功

vector::iterator it;//定义迭代器

for(it=free_list.begin();it!=free_list.end();++it){

//cout<<(*it).start<

if(((*it).len) >= node.size){

//记录已占用空间

fnod.len=node.size;

fnod.start=(*it).start;

fnod.id=node.id;

used_list.push_back(fnod);//放入已占用区域表

(*it).start+=node.size;

(*it).len-=node.size;//修改空闲区域表的信息

if((*it).len==0){//剩余空闲长度为0，移除这个空闲区域

free_list.erase(it);

}

ok=1;//已找到匹配

break;

}

}

if(ok==0){//证明当前进程没有匹配成功，则放入就绪队列

ready_list.push(node);

}

printf("进程%d申请进入内存,内存占用大小为%dkb：\n",node.id,node.size);

Show();

}

void Free(ready_node node){//回收过程函数

//释放内存的过程中，进程正常都会在内存中出现，这里就假设释放的进程全部合法

free_node fnod;

vector::iterator it;//定义迭代器

for(it=used_list.begin();it!=used_list.end();++it){

if(((*it).id) == node.id){//找到撤销进程

//回收空闲空间，并放入空闲区域白哦，此时不用记录进程号，因为好没有进程占有空间

fnod.start=(*it).start;

fnod.len=node.size;

free_list.push_back(fnod);//放入空闲区域表

(*it).len-=node.size;//修改占用区域表的信息

if((*it).len==0){//撤销内存后，剩余的占有空间为0，移除这个空闲区域

used_list.erase(it);

}

break;

}

}

printf("进程%d申请撤销,收回内存大小为%dkb：\n",node.id,node.size);

Show();

}

void Oper_FIRO(){//操作函数

ready_node node;

while(!ready_list.empty()){//首先操作第一次未匹配的进程，此队列中只有进入内存的进程，

//只组要调用分配函数Alloc()即可，不用调用回收函数Free() node=ready_list.front();//取出队首元素

ready_list.pop();//出队

Alloc(node);

}

while(!wait_list.empty()){//操作等待数列，有分配和回收两个过程

node=wait_list.front();

wait_list.pop();

if(node.flag==1){//申请进入内存的进程

Alloc(node);

}

else{//要撤出内存的进程

Free(node);

}

}

}

void Print(){//显示最后控制台的空想区域表的状态,输入文件中

//cout<

sort(free_list.begin(),free_list.end(),cmp);//操作之前首先按首地址从小到大排序for(int i=0;i

printf("%d %d\n",free_list[i].start,free_list[i].len);

}

}

【运行结果截图（首次适应算法）】

【程序代码（最佳适应算法）】

最佳适应算法按照空闲分区从大到小的顺序进行形成空闲分区链

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

struct ready_node{//就绪的进程

int id;//进程编号

int flag;//表是进程的状态，1：表示进入内存，0：表示从内存撤出

int size;//进程长度

};

struct free_node{//空闲区域表的结构体，首地址和长度

int id;//保存在该区域的进行号

int start;//首地址

int len;//长度

};

vector free_list;//保存空闲区域表的内容，分别是区域首址和区域长度vector used_list;//保存已占用区域表的内容，分别是区域首址和区域长度queue ready_list;//就绪的进程队列，主要保存第一次匹配为成功的进程queue wait_list;//等待的进程队列

//函数定义

int cmp(free_node a,free_node b);//定义排序的比较方式

void Show();//显示空闲区域表和已占用表的信息

void Init();//初始化等待序列

void Alloc(ready_node node);//动态分区分配函数

void Free(ready_node node);//回收过程函数

void Oper_FIRO();//操作函数

void Print();//显示最后控制台的空想区域表的状态,输入文件中

int main()

{

//重定向输入输出，对文件进行操作

freopen("input.txt","r",stdin);

freopen("output8.txt","w",stdout);

Init();//一定先进行初始化

printf("2145115 刘成路\n");

Oper_FIRO();

return 0;

}

int cmp(free_node a,free_node b){//定义排序的比较方式

return a.len

}

void Show(){//显示空闲区域表和已占用表的信息

sort(free_list.begin(),free_list.end(),cmp);//操作之前首先按首地址从小到大排序

printf("-----------------------\n");

printf("| 空闲链表的使用情况: |\n");

printf("-----------------------\n");

printf("---------------\n");

printf("| 首址| 长度|\n");

printf("---------------\n");

for(int i=0;i

printf("| %3d | %3d |\n",free_list[i].start,free_list[i].len);

printf("---------------\n");

}

printf("-------------------------\n");

printf("| 已占用链表的使用情况: |\n");

printf("-------------------------\n");

printf("----------------------------\n");

printf("|运行进程| 首址| 长度|\n");

printf("----------------------------\n");

for(int i=0;i

printf("| %3d | %3d | %3d |\n",used_list[i].id,used_list[i].start,used_list[i].len);

printf("----------------------------\n");

}

}

void Init(){//初始化等待序列

free_node fnod;

fnod.start=0; fnod.len=640;//初始化空闲表

free_list.push_back(fnod);

ready_node node;

while(scanf("%d%d%d",&node.id,&node.flag,&node.size)!=EOF){

wait_list.push(node);

//cout<

}

}

void Alloc(ready_node node){//动态分区分配函数

sort(free_list.begin(),free_list.end(),cmp);//操作之前首先按首地址从小到大排序

//cout<

free_node fnod;

int ok=0;//表示是否匹配成功

vector::iterator it;//定义迭代器

for(it=free_list.begin();it!=free_list.end();++it){

//cout<<(*it).start<

if(((*it).len) >= node.size){

//记录已占用空间

fnod.len=node.size;

fnod.start=(*it).start;

fnod.id=node.id;

used_list.push_back(fnod);//放入已占用区域表

(*it).start+=node.size;

(*it).len-=node.size;//修改空闲区域表的信息

if((*it).len==0){//剩余空闲长度为0，移除这个空闲区域

free_list.erase(it);

}

ok=1;//已找到匹配

break;

}

}

if(ok==0){//证明当前进程没有匹配成功，则放入就绪队列

ready_list.push(node);

}

printf("进程%d申请进入内存,内存占用大小为%dkb：\n",node.id,node.size);

Show();

}

void Free(ready_node node){//回收过程函数

//释放内存的过程中，进程正常都会在内存中出现，这里就假设释放的进程全部合法

free_node fnod;

vector::iterator it;//定义迭代器

for(it=used_list.begin();it!=used_list.end();++it){

if(((*it).id) == node.id){//找到撤销进程

//回收空闲空间，并放入空闲区域白哦，此时不用记录进程号，因为好没有进程占有空间

fnod.start=(*it).start;

fnod.len=node.size;

free_list.push_back(fnod);//放入空闲区域表

(*it).len-=node.size;//修改占用区域表的信息

if((*it).len==0){//撤销内存后，剩余的占有空间为0，移除这个空闲区域

used_list.erase(it);

}

break;

}

}

printf("进程%d申请撤销,收回内存大小为%dkb：\n",node.id,node.size);

Show();

}

void Oper_FIRO(){//操作函数

ready_node node;

while(!ready_list.empty()){//首先操作第一次未匹配的进程，此队列中只有进入内存的进程，

//只组要调用分配函数Alloc()即可，不用调用回收函数Free() node=ready_list.front();//取出队首元素

ready_list.pop();//出队

Alloc(node);

}

while(!wait_list.empty()){//操作等待数列，有分配和回收两个过程

node=wait_list.front();

wait_list.pop();

if(node.flag==1){//申请进入内存的进程

Alloc(node);

}

else{//要撤出内存的进程

Free(node);

}

}

}

void Print(){//显示最后控制台的空想区域表的状态,输入文件中

//cout<

sort(free_list.begin(),free_list.end(),cmp);//操作之前首先按首地址从小到大排序

for(int i=0;i

printf("%d %d\n",free_list[i].start,free_list[i].len);

}

}

【运行截图（最佳适应算法）】