操作系统课程设计实践报告

南通大学计算机科学与技术学院

操作系统实验报告

班级：软件工程121

姓名：金凯 学号：1102052019 指导老师：戴树贵 时间：19周一周

1

程序流程图一览 开始的图形界面 处理机管理 先优 时来先 间先级 轮服调 转务 度 法

页面替换 最先最佳进近页先最面出 少替 使用 移臂调度 银行家算法 先最电死来短梯锁先查调的服找度 避务 时 免 间 2

实验内容 1.处理机管理

FCFS：在多道程序或多任务系统中，系统中同时处于就绪态的进程又若干个，也就是说能运行的进程数远远大于处理机个数，为了使系统中的各个进程能有条不紊的运行，必须选择某种调度策略，以选择一进程占用处理机。

RR:如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务FCFS (first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行，但性能却不大好。

如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。 优先级调度：（1）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。（2）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。

①先来先服务

int fcfs()/*先来先服务算法*/ {

fcfsinput();

float time_temp=0; int i;

int number_schedul;

time_temp=tasks[0].come_time; for(i=0;itasks[i].run_begin_time=time_temp;

tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time; tasks[i].run_flag=1;

time_temp=tasks[i].run_end_time; number_schedul=i;

tasks[number_schedul].order=i+1; }

fcfsoutput(); return 0; }

int fcfsinput() /*进程参数的初始化，按照教材127页最上面的表格*/ {

3

task_struct tt; int i,j;

//初始化进程数 counter=3;

//初始化每个到达系统的时间 tasks[0].come_time=rand()%9; tasks[1].come_time=rand()%9; tasks[2].come_time=rand()%9;

for(i=1;i<3;i++) {

for(j=0;j<3-i;j++) { if(tasks[j].come_time>tasks[j+1].come_time) { tt=tasks[j]; tasks[j]=tasks[j+1]; tasks[j+1]=tt; } } }

//初始化每个进程估计运行的时间

tasks[0].run_time=28;tasks[1].run_time=9; tasks[2].run_time=3; //初始化每个进程的名字 tasks[0].name='A';tasks[1].name='B';tasks[2].name='C'; cout<<\"************************先来先服务算法************************\"<tasks[i].run_begin_time=0; tasks[i].run_end_time=0; tasks[i].order=0; tasks[i].run_flag=0; }

return 0; }

int fcfsoutput() /*调度结果输出*/ { int i;

float turn_round_time=0,f1,w=0;

cout<<\"作业名 到达时间 运行时间 开始时间 停止时间 运行次序 周转时间\"<4

f1=tasks[i].run_end_time-tasks[i].come_time; turn_round_time+=f1; w+=(f1/tasks[i].run_time);

cout<<\" \"<cout<<\"平均周转时间：\"<cout<<\" \"; return 0; }

②优先级调度

int ps() /*优先级调度*/ {

psinput();

float temp_time=0; int i=0,j;

int number_schedul,temp_counter; int max_priority;

max_priority=tasks[i].priority; j=1;

while ((jif (tasks[j].priority>=tasks[i].priority) {

max_priority=tasks[j].priority; i=j; } j++;

} /*查找第一个被调度的进程*/ /*对第一个被调度的进程求相应的参数*/ number_schedul=i;

tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;

tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;

tasks[number_schedul].run_flag=1;

temp_time=tasks[number_schedul].run_end_time; tasks[number_schedul].order=1; temp_counter=1;

while (temp_counter5

{

max_priority=0;

for(j=0;jif((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag)) if (tasks[j].priority>max_priority) {

max_priority=tasks[j].priority; number_schedul=j; } }

tasks[number_schedul].run_begin_time=temp_time;

tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;

tasks[number_schedul].run_flag=1;

temp_time=tasks[number_schedul].run_end_time; temp_counter++;

tasks[number_schedul].order=temp_counter; }

psoutput(); return 0; }

int psinput() /*进程参数的初始化*/ { int i;

//初始化进程数 counter=3;

//初始化每个到达系统的时间

tasks[0].come_time=4;tasks[1].come_time=5;tasks[2].come_time=6; //初始化每个进程估计运行的时间

tasks[0].run_time=5;tasks[1].run_time=10;tasks[2].run_time=8; //初始化每个进程的名字 tasks[0].name='A';tasks[1].name='B';tasks[2].name='C'; //初始化优先级 tasks[0].priority=rand()%5+3;tasks[1].priority=rand()%3;tasks[2].priority=rand()%3; cout<<\"****************************优先级调度算法****************************\"<tasks[i].run_begin_time=0; tasks[i].run_end_time=0;

6

tasks[i].order=0; tasks[i].run_flag=0; }

return 0; }

int psoutput() /*调度结果输出*/ { int i;

float turn_round_time=0,f1,w=0;

cout<<\"作业名 到达时间 运行时间 开始时间 停止时间 优先级 运行次序 周转时间\"<for(i=0;i<1;i++) {

f1=tasks[i].run_end_time-tasks[i].come_time; turn_round_time+=f1; w+=(f1/tasks[i].run_time);

cout<<\" \"<<for(i=1;if1=tasks[i].run_end_time-tasks[i].come_time; turn_round_time+=f1; w+=(f1/tasks[i].run_time);

cout<<\" \"<<cout<<\"平均周转时间：\"<③时间片轮转法

int rr() {

int n=3,num=0; node *head=NULL; node *tail=NULL;

cout<<\"*********************时*********************\"<间片轮转调度算法

7

for(int i=0;inode *temp=new node; if(i==0)strcpy(temp->name,\"A\"); if(i==1)strcpy(temp->name,\"B\"); if(i==2)strcpy(temp->name,\"C\"); temp->need_time=rand()%4+1;

temp->state='R'; //初始状态每个进程均为运行态 temp->allocation=0; //初始时进程均不占用cpu

num+=temp->need_time; //用num来限制循环的次数

if(!head) {

tail=head=temp; } else {

tail->next=temp; tail=temp;

tail->next=head; } }

node *p; p=head;

cout<cout<<\"进程\"<<'\'<<\"剩余时间\"<<'\'<<\"占用cpu时间\"<name<<'\'<<\" \"<need_time<<'\'<<'\'<allocation<<'s'<next; }

cout<<\" \"<name<<'\'<<\" \"<need_time<<'\'<<'\'<allocation<<'s'<node *q; int label=1; int i=1;

while(label==1&&i<=num) { cout<while(!p->need_time)

8

{ p=p->next; }

if(p->need_time) { p->need_time--; p->allocation++; if(p->need_time==0) { p->state='E'; } label=1; p=p->next; }

cout<<\"执行\"<cout<<\"进程\"<<'\'<<\"剩余时间\"<<'\'<<\"占用cpu时间\"<\"<need_time<<'\'<<'\'<allocation<<'s'<next; }

cout<<\"

\"<need_time<<'\'<<'\'<allocation<<'s'<cout<\"<name<<'\'<<\" \"<name<<'\'<<\" 9

2.页面替换算法

FIFO先进先出页面替换算法，基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性最大。

LRU最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。

OPT最佳页面替换算法，当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页面。

①最佳页面替换算法

void OPT() { int length; int opt[100]={0}; int pageLength; int optPage[100]={0}; int compare[100]={0}; int compares=1; int i,j,k; cout<<\"**************************************************\"<最佳页面调度算法

10

int flag=0;

for(j=1;j<=pageLength;j++) { if(opt[i]==optPage[j]) { flag=1; j=pageLength+1; } else if(optPage[j]==0) { optPage[j]=opt[i]; j=pageLength+1; flag=1; } }

if(flag==1){ } else { for(j=1;j<=pageLength;j++) { for(int k=i;k<=length;k++) { if(optPage[j]==opt[k]) { k=length+1; } else { compare[compares]++; } } compares++; } for(k=1;k=compare[k+1]) { compare[k+1]=compare[k]; } else { } } flag=compare[pageLength];

11

}

}

for(k=1;k<=pageLength;k++) { if(flag==compare[k]) { flag=k; k=pageLength+1; } } cout<<\" →淘汰\"<cout<cout<for(int s=1;s<=pageLength;s++){ cout<cout<②先进先出页面替换算法

void FIFO(){

int length; int fifo[100]={0}; int pageLength; int fifoPage[100]={0}; int i,j; cout<<\" ***********************先进先出页面调度算法**************************\"<12

fifo[i]=rand()%5+1; cout<for(i=1;i<=length;i++){ int flag=0; for(j=1;j<=pageLength;j++){ if(fifo[i]==fifoPage[j]){ flag=1; j=pageLength+1; }else if(fifoPage[j]==0){ fifoPage[j]=fifo[i]; j=pageLength+1; flag=1; } } if(flag==1) { } else { cout<<\" for(j=1;j<=pageLength;j++){ fifoPage[j]=fifoPage[j+1]; } fifoPage[pageLength]=fifo[i]; } cout<}

→淘汰\"<③最近最少使用页面替换算法

void LRU() { int length; int lru[100]={0}; int pageLength; int lruPage[100]={0}; int i,j; cout<<\" ***********************最近最少使用页面替换算法***********************\"<0;cc--){ lruPage[cc]=lruPage[cc-1]; } lruPage[1]=lru[i]; flag=1; j=pageLength+1; }else if(lruPage[j]==0){ for(int vv=j;vv>0;vv--){ lruPage[vv]=lruPage[vv-1]; } lruPage[1]=lru[i]; j=pageLength+1; flag=1; } }

14

}

}

if(flag==1) { } else { cout<<\" →淘汰\"<0;j--){ lruPage[j]=lruPage[j-1]; } lruPage[1]=lru[i]; }

cout<cout<for(int s=1;s<=pageLength;s++){ cout<cout<3.移臂调度

FCFS

先来先服务驱动调度算法中，移动臂是随机移动的，不考虑各I/O请求之

间的相对次序和移动臂当前所处的位置，进程等待I/O请求的时间会很长，寻道性能较

差。

SSTF

最短查找时间优先驱动调度算法考虑I/O请求之间的区别，总是执行查找

时间最短的请求，与FCFS算法相比有较好的寻道性能。

电梯调度算法，每次总是选择沿移动臂的移动方向最近的那个柱面，若同一柱

面上有多个请求，还需进行旋转优化。如果当前移动方向上没有访问请求时，就改变移动臂的移动方向，然后，处理所遇到的最近的I/O请求。

15

①先来先服务算法

void ybfcfs(){ int num=100; int currentNum=rand()%100; int justNum; int length=6; int fcfs[100]={0}; int sum=0; cout<<\"*************************先来先服务调***********************\"<cout<<\"默认磁盘柱面数量为100\"<②最短查找时间算法

void sstf(){ int num=100; int currentNum=rand()%100; int justNum=rand()%100; int length=6; int compare[100]={0}; int sstf[100]={0}; int finalSstf[100]={0}; int sum=0; cout<<\"***************************最短查找时*************************\"<度算算法

法

16

间cout<<\"默认磁盘柱面数量为100\"<cout<<\"当前存取臂的位置为：\"<for(i=1;i<=length;i++){ sstf[i]=rand()%100; cout<for(i=1;isstf[j+1]){ k=sstf[j+1]; sstf[j+1]=sstf[j]; sstf[j]=k; } } }

for(i=1;i<=length;i++)

{ //找出夹在currentNum值的两个数 i，i-1 if(currentNum>sstf[i]){ }else{ k=i; i=length+1; } }

int height; int low;

finalSstf[1]=currentNum; int flag=1;

sstf[0]=10000000; int len=length; for(j=1;j<=len;){ height=abs(currentNum-sstf[k]); low = abs(currentNum-sstf[k-1]); flag++; if(height>=low){ finalSstf[flag]=sstf[k-1]; currentNum=sstf[k-1]; k=k-1; sum=sum+low; }else{

17

//

finalSstf[flag]=sstf[k]; sum=sum+height; currentNum=sstf[k]; } for(int ll=k;llcout<cout<}

③电梯调度算法

void dianti(){ cout<<\"***************************电梯*************************\"<int num=100; int currentNum=rand()%100; int justNum=31; int length=6; int dianti[100]={0}; int finalDianti[100]={0}; int sum=0; int i; cout<<\"默认磁盘柱面数量为100\"<dianti[j+1]){

调度算法

18

k=dianti[j+1]; dianti[j+1]=dianti[j]; dianti[j]=k; } } }

for(i=1;i<=length;i++){ //找出夹在currentNum值的两个数 i，i-1 if(currentNum>dianti[i]){} else { k=i; i=length+1; } }

finalDianti[1]=currentNum; int flag=1;

for(i=k;iflag++;

finalDianti[flag]=dianti[length]; for(i=k-1;i>0;i--) { flag++; finalDianti[flag]=dianti[i]; }

finalDianti[flag+1]=dianti[1];

cout<<\"存取臂移动序列为： \"<cout<cout<<\"存取臂移动总量为： \"<}

19

4.银行家算法

银行家算法：Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。其基本思想是：系统中的所有进程放入一个进程集合，先把资源试探性地分配给它。然后找出剩余资源能满足最大需求量的进程，进行分配。

void print(int *Max, int *Allocation, int *Need, int *Available,int p,int r) {

int i, j ,flag=1;

cout<<(\"进程号 请求的 占用的 C-A:需要的\")<cout<<\"P[i] Claim Allocation Need Available\"<//这是一个表头，下面是英文，上面用汉字说明作用 for(i=0;ifor(j=0;j}

cout<<'\'; //制表符，用于排列，无特殊意义 for(j=0;j}

可用 20

}

}

cout<<'\'; for(j=0;jcout<<'\'; if(flag==1) { }

cout<for(j=0;jcout<<*(Available+j)<<\" \"; cout<<*(Need+i*r+j)<<\" \";

bool checkSafe(int *Need,int *Allocation,int *Available,int p,int r) {

int i=0, j=0, k=0, m=0, count=0, flag1=0, flag2=0;

int *list, *Work; // 设置工作向量Work，安全序列list，均用指针来做。数组太麻烦了

bool *Finish; Work = new int[r];

// 完成标志Finish

21

Finish = new bool[p]; list = new int[p];

// 初始化完成标志Finish，默认为false for(i=0;i*(Finish+i) = false;

// 初始化工作向量Work for(i=0;i*(Work+i) = *(Available+i);

// 进行安全检查 while(k*(Work+j)) { flag1 = 0;

break;

22

}

}

flag1 = 1;

}

// 若flag1==1 即Finish[i]为true ,且需求向量小于工作向量，则该进程可以获得资源

if(flag1==1) { } else { }

if(count==5)

count++; for(j=0;j*(Finish+m) = true; *(list+k) = m; count = 0; k++;

*(Work+j) += *(Allocation+m*r+j);

23

break;

m++; if(m==5)

m=0;

}

// 若所有进程的*(Finish+i)==true,表示系统处于安全状态 for(i=0;i} else { flag2 =1; }

}

delete[] Work; delete[] Finish;

// 若系统处于安全状态，则输出存在的安全序列，否则安全检测算法结束24

if(flag2==1) { cout<<\"存在安全序列：\"; for(i=0;icout<<\"P\"<<*(list+i)<<\" \";

cout<} else { return false;

}

}

int sisuo() {

int p=5,r=3,i; // 进程数为5，资源数为3

// Max为5*3的最大需求矩阵，Available为可利用资源向量，

// Allocation为5*3的分配矩阵，Need为5*3的需求矩阵,请求向量Request1 int *Max, *Available, *Allocation, *Need, *Request1;

Max = new int[p*r];

25

Available = new int[r]; Allocation = new int[p*r]; Need = new int[p*r]; Request1 = new int[r];

// 初始化Max矩阵 // 7 5 3 // 3 2 2 // 9 0 2 // 2 2 2 // 4 3 3

*(Max+0*r+0) = 7;*(Max+0*r+1) = 5;*(Max+0*r+2) = 3; *(Max+1*r+0) = 3;*(Max+1*r+1) = 2;*(Max+1*r+2) = 2; *(Max+2*r+0) = 9;*(Max+2*r+1) = 0;*(Max+2*r+2) = 2; *(Max+3*r+0) = 2;*(Max+3*r+1) = 2;*(Max+3*r+2) = 2; *(Max+4*r+0) = 4;*(Max+4*r+1) = 3;*(Max+4*r+2) = 3;

// 初始化Allocation矩阵 // 0 1 0 // 2 0 0 // 3 0 2 // 2 1 1 // 0 0 2

*(Allocation+0*r+0) = 0;*(Allocation+0*r+1) = 1;*(Allocation+0*r+2) = 0;

26

*(Allocation+1*r+0) = 2;*(Allocation+1*r+1) = 0;*(Allocation+1*r+2) = 0; *(Allocation+2*r+0) = 3;*(Allocation+2*r+1) = 0;*(Allocation+2*r+2) = 2; *(Allocation+3*r+0) = 2;*(Allocation+3*r+1) = 1;*(Allocation+3*r+2) = 1; *(Allocation+4*r+0) = 0;*(Allocation+4*r+1) = 0;*(Allocation+4*r+2) = 2;

// 初始化可利用资源向量Available // 3 3 2

*(Available+0) = 3; *(Available+1) = 3; *(Available+2) = 2;

// 初始化Need矩阵,c-a for(i=0;i}

// 打印初始化数据

cout<<\"T0时刻的系统资源分配情况：\"<// p1请求资源矩阵为 Request1（1,0,2）

*(Request1+0) = rand()%2+0;*(Request1+1) =rand()%2+0;*(Request1+2) = rand()%2+0;

cout<<\"P1进程的请求向量为： \";

27

for(int j=0;j}

cout<// 请求资源数与最大需求资源数进行逐一比较 int flag = 0; for(i=0;i*(Need+1*r+i)) { flag = 0; break;

} else { flag = 1; }

}

// 若请求资源数小于最大需求资源数，则进行资源分配判断，否则算法结束if(flag==1) {

// 请求资源数与剩余资源数进行逐一比较

28

int flag2 = 0; for(int i=0;i*(Available+i)) { flag = 0; break;

} else { flag2 = 1; }

}

// 若请求资源数小于最大需求资源数，则进行试探分配，否则算法结束if(flag2==1)

{ // 系统试探着进行资源分配 for(int i=0;i}

29

// 试探分配完成后，对该状态进行安全检测，若通过检测，则分配， // 否则本次试探分配作废，恢复原来资源分配状态 if(checkSafe(Need,Allocation,Available,p,r)) { } else {

cout<<\"分配资源后系统处于不安全状态，系统不分配该资源！\"<30

cout<<\"分配资源后系统处于安全状态，可进行分配！\"<cout<<\"为进程分配资源后，T1时刻系统资源分配情况：\"<cout<<\"测试结果：符合银行家算法，可以防止死锁\"<*(Available+i) += *(Request1+i); *(Allocation+1*r+i) -= *(Request1+i); *(Need+1*r+i) += *(Request1+i);

}

}

else { cout<<\"请求资源出错，无足够资源可分配！\"<}

}

else { cout<<\"请求资源出错，请求资源数不能大于需求资源数！\"<}

delete[] Max; delete[] Available; delete[] Allocation; delete[] Need; delete[] Request1; return 0;

}

31

可以运行的程序代码如下：

#include #include using namespace std;

int fcfsoutput(); /*调度结果输出*/ int fcfsinput(); //进程参数的初始化 int psinput(); int psoutput(); void kaishi(); #define MAX 10

struct node //建立链表来存放进程数据 {

char name[5]; //进程名称

int need_time; //所需要的时间 int allocation; //占用cpu的情况

char state; //目前的状态 R为运行，E为运行完毕 node *next; //链表的尾结点 };

struct task_struct {

char name; /*进程名称*/ int number; /*进程编号*/ float come_time; /*到达时间*/ float run_begin_time; /*开始运行时间*/ float run_time; /*运行时间*/ float run_end_time; /*运行结束时间*/ int priority; /*优先级*/ int order; /*运行次序*/ int run_flag; /*调度标志*/ }tasks[MAX];

int counter; /*实际进程个数*/ int fcfs()/*先来先服务算法*/ {

fcfsinput();

float time_temp=0; int i;

int number_schedul;

time_temp=tasks[0].come_time; for(i=0;itasks[i].run_begin_time=time_temp;

tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;

32

tasks[i].run_flag=1;

time_temp=tasks[i].run_end_time; number_schedul=i;

tasks[number_schedul].order=i+1; }

fcfsoutput(); return 0; }

int fcfsinput() /*进程参数的初始化，按照教材127页最上面的表格*/ { task_struct tt; int i,j;

//初始化进程数 counter=3;

//初始化每个到达系统的时间 tasks[0].come_time=rand()%9; tasks[1].come_time=rand()%9; tasks[2].come_time=rand()%9;

for(i=1;i<3;i++) {

for(j=0;j<3-i;j++) { if(tasks[j].come_time>tasks[j+1].come_time) { tt=tasks[j]; tasks[j]=tasks[j+1]; tasks[j+1]=tt; } } }

//初始化每个进程估计运行的时间 tasks[0].run_time=28; tasks[1].run_time=9; tasks[2].run_time=3;

//初始化每个进程的名字 tasks[0].name='A'; tasks[1].name='B'; tasks[2].name='C';

33

cout<<\"************************先来先服务算法************************\"<tasks[i].run_begin_time=0; tasks[i].run_end_time=0; tasks[i].order=0; tasks[i].run_flag=0; }

return 0; }

int fcfsoutput() /*调度结果输出*/ { int i;

float turn_round_time=0,f1,w=0;

cout<<\"作业名 到达时间 运行时间 开始时间 停止时间 运行次序 周转时间\"<f1=tasks[i].run_end_time-tasks[i].come_time; turn_round_time+=f1; w+=(f1/tasks[i].run_time);

cout<<\" \"<cout<<\"平均周转时间：\"<cout<<\" \"; return 0; }

/*-------------------------------------------------------------------------------------------*/ int ps() /*优先级调度*/ {

psinput();

float temp_time=0; int i=0,j;

int number_schedul,temp_counter; int max_priority;

max_priority=tasks[i].priority; j=1;

while ((j34

if (tasks[j].priority>=tasks[i].priority) {

max_priority=tasks[j].priority; i=j; } j++;

} /*查找第一个被调度的进程*/ /*对第一个被调度的进程求相应的参数*/ number_schedul=i;

tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;

tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;

tasks[number_schedul].run_flag=1;

temp_time=tasks[number_schedul].run_end_time; tasks[number_schedul].order=1; temp_counter=1;

while (temp_countermax_priority=0;

for(j=0;jif((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag)) if (tasks[j].priority>max_priority) {

max_priority=tasks[j].priority; number_schedul=j; } }

tasks[number_schedul].run_begin_time=temp_time;

tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;

tasks[number_schedul].run_flag=1;

temp_time=tasks[number_schedul].run_end_time; temp_counter++;

tasks[number_schedul].order=temp_counter; }

psoutput(); return 0; }

int psinput() /*进程参数的初始化*/

35

{ int i;

//初始化进程数 counter=3;

//初始化每个到达系统的时间 tasks[0].come_time=4; tasks[1].come_time=5; tasks[2].come_time=6;

//初始化每个进程估计运行的时间 tasks[0].run_time=5; tasks[1].run_time=10; tasks[2].run_time=8;

//初始化每个进程的名字 tasks[0].name='A'; tasks[1].name='B'; tasks[2].name='C'; //初始化优先级 tasks[0].priority=rand()%5+3; tasks[1].priority=rand()%3; tasks[2].priority=rand()%3; cout<<\"****************************优先级调度算法****************************\"<tasks[i].run_begin_time=0; tasks[i].run_end_time=0; tasks[i].order=0; tasks[i].run_flag=0; }

return 0; }

int psoutput() /*调度结果输出*/ { int i;

float turn_round_time=0,f1,w=0;

cout<<\"作业名 到达时间 运行时间 开始时间 停止时间 优先级 运行次序 周转时间\"<for(i=0;i<1;i++) {

f1=tasks[i].run_end_time-tasks[i].come_time; turn_round_time+=f1; w+=(f1/tasks[i].run_time);

cout<<\" \"<36

<<for(i=1;if1=tasks[i].run_end_time-tasks[i].come_time; turn_round_time+=f1; w+=(f1/tasks[i].run_time);

cout<<\" \"<<cout<<\"平均周转时间：\"</*-------------------------------------------------------------------------------------*/ int rr() {

int n=3,num=0; node *head=NULL; node *tail=NULL;

cout<<\"*********************时间片轮转调度算法*********************\"<for(int i=0;inode *temp=new node; if(i==0)strcpy(temp->name,\"A\"); if(i==1)strcpy(temp->name,\"B\"); if(i==2)strcpy(temp->name,\"C\"); temp->need_time=rand()%4+1;

temp->state='R'; //初始状态每个进程均为运行态 temp->allocation=0; //初始时进程均不占用cpu

num+=temp->need_time; //用num来限制循环的次数

if(!head) {

tail=head=temp; } else

37

{

tail->next=temp; tail=temp;

tail->next=head; } }

node *p; p=head;

cout<cout<<\"进程\"<<'\'<<\"剩余时间\"<<'\'<<\"占用cpu时间\"<name<<'\'<<\" \"<need_time<<'\'<<'\'<allocation<<'s'<next; }

cout<<\" \"<name<<'\'<<\" \"<need_time<<'\'<<'\'<allocation<<'s'<node *q; int label=1; int i=1;

while(label==1&&i<=num) { cout<while(!p->need_time) { p=p->next; }

if(p->need_time) { p->need_time--; p->allocation++; if(p->need_time==0) { p->state='E'; } label=1; p=p->next; }

cout<<\"执行\"<cout<<\"进程\"<<'\'<<\"剩余时间\"<<'\'<<\"占用cpu时间\"<38

while(q!=tail) { cout<<\" \"<name<<'\'<<\" \"<need_time<<'\'<<'\'<allocation<<'s'<next; }

cout<<\" \"<name<<'\'<<\" \"<need_time<<'\'<<'\'<allocation<<'s'<cout</*---------------------------------------------------------------------------------------------*/ void print(int *Max, int *Allocation, int *Need, int *Available,int p,int r) { int i, j ,flag=1; cout<<(\"进程号 请求的 占用的 C-A:需要的\")<//这是一个表头，下面是英文，上面用汉字说明作用 for(i=0;i可用 Need 39

{ for(j=0;jbool checkSafe(int *Need,int *Allocation,int *Available,int p,int r) { int i=0, j=0, k=0, m=0, count=0, flag1=0, flag2=0; int *list, *Work; // 设置工作向量Work，安全序列list，均用指针来做。数组太麻烦了 bool *Finish; // 完成标志Finish Work = new int[r]; Finish = new bool[p]; list = new int[p]; // 初始化完成标志Finish，默认为false for(i=0;i*(Work+j)) { flag1 = 0; break; } flag1 = 1; }

40

}

// 若flag1==1 即Finish[i]为true ,且需求向量小于工作向量，则该进程可以获得资

源 if(flag1==1) { for(j=0;j// 若所有进程的*(Finish+i)==true,表示系统处于安全状态 for(i=0;idelete[] Work; delete[] Finish;

// 若系统处于安全状态，则输出存在的安全序列，否则安全检测算法结束

41

if(flag2==1) { cout<<\"存在安全序列：\"; for(i=0;iint sisuo() { int p=5,r=3,i; // 进程数为5，资源数为3 // Max为5*3的最大需求矩阵，Available为可利用资源向量， // Allocation为5*3的分配矩阵，Need为5*3的需求矩阵,请求向量Request1 int *Max, *Available, *Allocation, *Need, *Request1; Max = new int[p*r]; Available = new int[r]; Allocation = new int[p*r]; Need = new int[p*r]; Request1 = new int[r]; // 初始化Max矩阵 // 7 5 3 // 3 2 2 // 9 0 2 // 2 2 2 // 4 3 3 *(Max+0*r+0) = 7;*(Max+0*r+1) = 5;*(Max+0*r+2) = 3; *(Max+1*r+0) = 3;*(Max+1*r+1) = 2;*(Max+1*r+2) = 2; *(Max+2*r+0) = 9;*(Max+2*r+1) = 0;*(Max+2*r+2) = 2; *(Max+3*r+0) = 2;*(Max+3*r+1) = 2;*(Max+3*r+2) = 2; *(Max+4*r+0) = 4;*(Max+4*r+1) = 3;*(Max+4*r+2) = 3; // 初始化Allocation矩阵 // 0 1 0 // 2 0 0

42

// 3 0 2 // 2 1 1 // 0 0 2

*(Allocation+0*r+0) = 0;*(Allocation+0*r+1) = 1;*(Allocation+0*r+2) = 0; *(Allocation+1*r+0) = 2;*(Allocation+1*r+1) = 0;*(Allocation+1*r+2) = 0; *(Allocation+2*r+0) = 3;*(Allocation+2*r+1) = 0;*(Allocation+2*r+2) = 2; *(Allocation+3*r+0) = 2;*(Allocation+3*r+1) = 1;*(Allocation+3*r+2) = 1; *(Allocation+4*r+0) = 0;*(Allocation+4*r+1) = 0;*(Allocation+4*r+2) = 2;

// 初始化可利用资源向量Available // 3 3 2

*(Available+0) = 3; *(Available+1) = 3; *(Available+2) = 2; // 初始化Need矩阵,c-a for(i=0;i// 打印初始化数据

cout<<\"T0时刻的系统资源分配情况：\"<// p1请求资源矩阵为 Request1（1,0,2）

*(Request1+0) = rand()%2+0;*(Request1+1) =rand()%2+0;*(Request1+2) = rand()%2+0;

cout<<\"P1进程的请求向量为： \"; for(int j=0;jcout<// 请求资源数与最大需求资源数进行逐一比较 int flag = 0; for(i=0;i*(Need+1*r+i)) { flag = 0; break; } else { flag = 1;

43

}

}

// 若请求资源数小于最大需求资源数，则进行资源分配判断，否则算法结束 if(flag==1) { // 请求资源数与剩余资源数进行逐一比较 int flag2 = 0; for(int i=0;i*(Available+i)) { flag = 0; break; } else { flag2 = 1; } }

// 若请求资源数小于最大需求资源数，则进行试探分配，否则算法结束 if(flag2==1) { // 系统试探着进行资源分配 for(int i=0;i// 试探分配完成后，对该状态进行安全检测，若通过检测，则分配， // 否则本次试探分配作废，恢复原来资源分配状态 if(checkSafe(Need,Allocation,Available,p,r)) { cout<<\"分配资源后系统处于安全状态，可进行分配！\"<44

} else { cout<<\"分配资源后系统处于不安全状态，系统不分配该资源！\"</*----------------------------------------------------------------------------------*/ void OPT() { int length; int opt[100]={0}; int pageLength; int optPage[100]={0}; int compare[100]={0}; int compares=1; int i,j,k; cout<<\"***************************最佳页面调度***********************\"<算法45

cout<<\"时刻t\"<<'\'; for(i=0;i}cout<for(i=1;i<=length;i++) { compares=1; for(int ll=1;ll<=100;ll++) { compare[ll]=0; } int flag=0; for(j=1;j<=pageLength;j++) { if(opt[i]==optPage[j]) { flag=1; j=pageLength+1; } else if(optPage[j]==0) { optPage[j]=opt[i]; j=pageLength+1; flag=1; } } if(flag==1){ } else { for(j=1;j<=pageLength;j++) { for(int k=i;k<=length;k++) { if(optPage[j]==opt[k]) { k=length+1; }

46

else { compare[compares]++; } } compares++; } for(k=1;k=compare[k+1]) { compare[k+1]=compare[k]; } else { } } flag=compare[pageLength]; for(k=1;k<=pageLength;k++) { if(flag==compare[k]) { flag=k; k=pageLength+1; } } cout<<\" →淘汰\"</*--------------------------------------------------------------------------------*/ void FIFO(){

47

int length; int fifo[100]={0}; int pageLength; int fifoPage[100]={0}; int i,j; cout<<\" ***********************先进先出页面调度算法**************************\"<→淘汰\"<cout</*----------------------------------------------------------------------------------*/ void LRU() { int length; int lru[100]={0}; int pageLength; int lruPage[100]={0}; int i,j; cout<<\" ***********************最近最少使用页面替换算法***********************\"<0;cc--){ lruPage[cc]=lruPage[cc-1]; }

49

lruPage[1]=lru[i]; flag=1; j=pageLength+1; }else if(lruPage[j]==0){ for(int vv=j;vv>0;vv--){ lruPage[vv]=lruPage[vv-1]; } lruPage[1]=lru[i]; j=pageLength+1; flag=1; } } if(flag==1) { } else { cout<<\" →淘汰\"<0;j--){ lruPage[j]=lruPage[j-1]; } lruPage[1]=lru[i]; } cout</*----------------------------------------------------------------------------------*/ void ybfcfs(){ int num=100; int currentNum=rand()%100; int justNum; int length=6; int fcfs[100]={0};

50

int sum=0; cout<<\"*************************先来先服务调度算法

***********************\"<找时算法

51

间

for(i=1;isstf[j+1]){ k=sstf[j+1]; sstf[j+1]=sstf[j]; sstf[j]=k; } } }

for(i=1;i<=length;i++)

{ //找出夹在currentNum值的两个数 i，i-1 if(currentNum>sstf[i]){ }else{ k=i; i=length+1; } }

int height; int low;

finalSstf[1]=currentNum; int flag=1;

sstf[0]=10000000; int len=length; for(j=1;j<=len;){ height=abs(currentNum-sstf[k]); low = abs(currentNum-sstf[k-1]); flag++; if(height>=low){ finalSstf[flag]=sstf[k-1]; currentNum=sstf[k-1]; k=k-1; sum=sum+low; }else{ finalSstf[flag]=sstf[k]; sum=sum+height; currentNum=sstf[k]; } for(int ll=k;ll52

cout<void dianti(){ cout<<\"***************************电梯调度算*************************\"<dianti[j+1]){ k=dianti[j+1]; dianti[j+1]=dianti[j]; dianti[j]=k; } } } for(i=1;i<=length;i++){ //找出夹在currentNum值的两个数 i，i-1 if(currentNum>dianti[i]){} else { k=i; i=length+1; }

法

53

} finalDianti[1]=currentNum; int flag=1; for(i=k;i0;i--) { flag++; finalDianti[flag]=dianti[i]; } finalDianti[flag+1]=dianti[1]; cout<<\"存取臂移动序列为： \"<void chuliqi() { int n; cout<>n; switch(n) { case 1: fcfs();kaishi(); break; case 2: ps();kaishi(); break; case 3: rr();kaishi(); break; case 4: kaishi();kaishi(); break; } }

void yemian() { int n; cout<54

cin>>n; switch(n) { case 1: OPT();kaishi(); break; case 2: FIFO();kaishi(); break; case 3: LRU();kaishi(); break; case 4: kaishi();kaishi(); break; } }

void yibi() { int n; cout<>n; switch(n) { case 1: ybfcfs();kaishi(); break; case 2: sstf();kaishi(); break; case 3: dianti();kaishi(); break; case 4: kaishi();kaishi(); break; } }

void kaishi() { cout<>n; switch(n) { case 1: chuliqi(); break; case 2: sisuo(); break; case 3: yemian(); break; case 4: yibi(); break; default: cout<<\"错误请重新选择！\"<int main(void) { cout<<\" -----------------操作系统课程设计-----------------\"<55

}

心得体会：

通过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我对于银行家算法有了更详尽的认识：死锁避免方法能支持更多的进程并发执行，让在可行的情况下让进程充分利用资源，而是动态的确定是否分配资源给提出请求的进程。在这个算法中如果一个资源的分配会导致下一步死锁，系统便拒绝本次分配。在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该记得释放资源。从这次实验中我发现我对于c++掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。

此外我还更深入的理解了各个进程调度算法，及实现过程。在编写程序时查询了很多资料，间接提高了我的搜索能力。在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。

特别是设计先来先服务调度算法和强占式短进程优先调度算法的时候，对进程的调度算法有了更好的直观接触。对进程管理中的等待队列，就绪队列，优先级，强占式等概念有了更深刻的印象。

在设计此模拟操作系统的课设中，也加深了对c++知识的把握。解决了一些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。另外，我觉得我们的实验课题都是比较有代表性的，不仅体现了操作系统的知识点，也体现了其他学科的相关知识。这三个程序用了多天的时间进行分析和修改，虽然辛苦，但收获颇多！

2013年7月5日 14：54分 完

56