操作系统实验报告

}

{ }

while(fst->next != NULL) { fst = fst->next; }

in ->next = fst ->next; fst ->next = in;

//将进程插入到完成队列尾部 void InsertFinish(PCB *in) { PCB *fst; fst = finish; if(finish == NULL) { in->next = finish; finish = in; } else { while(fst->next != NULL) { fst = fst->next; } in ->next = fst ->next; fst ->next = in; } }

//优先级调度输入函数 void PrioCreate() { PCB *tmp; int i;

cout<<\：\ for(i = 0;i < num; i++) { if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL) { cerr<<\ exit(1); }

cin>>tmp->name; getchar();

cin>>tmp->needtime; tmp ->cputime = 0; tmp ->state ='W';

tmp ->prio = 50 - tmp->needtime; //设置其优先级，需要的时间越多，优先级越低 tmp ->round = 0; tmp ->count = 0;

InsertPrio(tmp); //按照优先级从高到低，插入到就绪队列 }

cout<<\进程名\\t优先级\\tcpu时间\\t需要时间\\t进程状态\\t计数器\

}

//时间片输入函数 void TimeCreate() { PCB *tmp; int i; cout<<\输入进程名字和进程时间片所需时间：\ for(i = 0;i < num; i++) { if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL) { cerr<<\ exit(1); } cin>>tmp->name; getchar(); cin>>tmp->needtime; tmp ->cputime = 0; tmp ->state ='W'; tmp ->prio = 0; tmp ->round = 2; tmp ->count = 0; InsertTime(tmp); } printf(\进程名\\t轮数\\tcpu时间\\t需要时间\\t进程状态\\t计数器\\n\ }

//按照优先级调度，每次执行一个时间片 void Priority() { int flag = 1; GetFirst(); while(run != NULL)

{ Output1(); while(flag) {

run->prio -= 3; //优先级减去三 run->cputime++; //CPU时间片加一 run->needtime--;//进程执行完成的剩余时间减一 if(run->needtime == 0)//如果进程执行完毕，将进程状态置为F，将其插入到完成队列 { run ->state = 'F'; run->count++; InsertFinish(run); flag = 0; } else //将进程状态置为W，入就绪队列 { run->state = 'W'; run->count++; //进程执行的次数加一 InsertTime(run); flag = 0; } } flag = 1; GetFirst(); //继续取就绪队列队头进程进入执行队列 } }

void RoundRun() //时间片轮转调度算法 { int flag = 1; GetFirst(); while(run != NULL) { Output2(); while(flag) { run->count++; run->cputime++; run->needtime--; if(run->needtime == 0) //进程执行完毕 {

run ->state = 'F'; InsertFinish(run); flag = 0; }

else if(run->count == run->round)//时间片用完 { run->state = 'W'; run->count = 0; //计数器清零，为下次做准备 InsertTime(run); flag = 0; } } flag = 1; GetFirst(); } }

int main(void) { int n;

cout<<\：\ cin>>num; getchar();

cout<<\进程调度算法模拟----------------------\ cout<<\ 1、优先数调度算法\ cout<<\ 2、循环轮转调度算法 \ cout<<\

cout<<\：\cin>>n; switch(n) { case 1: cout<<\优先数调度:\ PrioCreate(); Priority(); Output1(); break; case 2: cout<<\循环轮转算法:\ TimeCreate(); RoundRun();

}

Output2(); break; case 0: exit(1); break; default: cout<<\ break; }

cout<

3.实验结果

课程名称: 进程调度模拟算法 分院: _______信息科学与技术 班级: _______1101-2班

姓名:________冯小兰______ 实验日期 2014 年5月日 评分 教师签名

课程名称：进程调度模拟算法 计算机科学与技术 分院 信1101-2 班 组 桌号 实验者姓名：___冯小兰 实验日期 2014年 月 日

评分 教师签名

一、实验目的

进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法实验要求

二. 实验过程

1． 准备

A 拿到题目后,首先是查看第三版计算机操作系统课本上有关进程调度算法的知识,上网查有关看进程调度更详细讲解的课件,在弄懂算法后,开始构思编程.

B 看C语言程序设计有关结构体的知识以及数据结构有关队列的相关知识,为编程做准备.

C 编写程序. 2 主要流程和源代码 程序设计主要流程:

每个进程有三种状:执行状态（RUN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 进程控制块结构如下：

NAME——进程标示符

PRIO/ROUND——进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME——进程累计占用CPU的时间片数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针

进程的就绪态和等待态均为链表结构，共有四个指针如下： RUN——当前运行进程指针 READY——就需队列头指针 TAIL—— 就需队列尾指针 FINISH—— 完成队列头指针 源代码:

#include #include #include #include using namespace std; typedef struct node {

char name[20]; //进程的名字 int prio; //进程的优先级

int round; //分配CPU的时间片

int cputime; //CPU执行时间

int needtime; //进程执行所需要的时间

char state; //进程的状态，W——就绪态，R——执行态，F——完成态 int count; //记录执行的次数 struct node *next; //链表指针 }PCB; int num;

PCB *ready=NULL,*run=NULL,*finish=NULL; //定义三个队列，就绪队列，执行队列和完成队列 void GetFirst() //取得第一个就绪队列节点 {

run = ready;

if(ready!=NULL) {

run ->state = 'R'; ready = ready ->next; run ->next = NULL; } }

//优先级输出队列 void Output1() { PCB *p; p = ready; cout<<\进程名\\t优先级\\tcpu时间\\t需要时间\\t进程状态\\t计数器\ while(p!=NULL) { cout<name<<\<<\ p = p->next; } p = finish; while(p!=NULL) { cout<name<<\<<\ p = p->next; } p = run; while(p!=NULL) {

cout<name<<\<<\ p = p->next; } }

//轮转法输出队列 void Output2() { PCB *p; p = ready; printf(\进程名\\t轮数\\tcpu时间\\t需要时间\\t进程状态\\t计数器\\n\ while(p!=NULL) { cout<name<<\te<<\ p = p->next; } p = finish; while(p!=NULL) { cout<name<<\te<<\ p = p->next; } p = run; while(p!=NULL) { cout<name<<\te<<\ p = p->next; } }

//创建优先级队列，规定优先数越小，优先级越低 void InsertPrio(PCB *in) { PCB *fst,*nxt; fst = nxt = ready; if(ready == NULL) //如果队列为空，则为第一个元素 {

in->next = ready; ready = in; }

else //查到合适的位置进行插入 {

if(in ->prio >= fst ->prio) //比第一个还要大，则插入到队头 { in->next = ready; ready = in; } else { }

while(fst->next != NULL) //移动指针查找第一个比它小的元素的位置进行插入 { nxt = fst; fst = fst->next; }

if(fst ->next == NULL) //已经搜索到队尾，则其优先级数最小，将其插入到队尾{ in ->next = fst ->next; fst ->next = in; }

else //插入到队列中 { nxt = in; in ->next = fst; }

即可 }

}

//将进程插入到就绪队列尾部 void InsertTime(PCB *in) { PCB *fst; fst = ready; if(ready == NULL) { in->next = ready; ready = in; } else

4 遇到的问题

在思考上出现的一个问题是,队列是先进先出的,在优先级算法中怎么来向链表中插入新的进程,使其能够按优先级排序.第一想到的是用数组,这样在插入进程时容易对进程排序.但不如链表方便,所以,就想用链表,自己用链表并不是很熟练.

5 实验总结

通过本次实验，我学到了进程调度算法，了解了进程调度是CPU管理的核心，不同的调度算法会使得进程运行时间不同,运行的先后顺序也不同,这就会有一个算法选择的问题.掌握了用C语言实现进程调度算法的模拟，提高了编程能力,以及对进程调度算法的理解。

课程名称：存储管理动态分区分配及回收算法 计算机科学与技术 分院 信1101-2 班

实验者姓名：___冯小兰 实验日期 2014年 月 日

评分 教师签名

一、实验目的

通过存储管理动态分区管理实验，了解操作系统分区有关内容，理解计算机系统的资源如何组织，操作系统是怎样管理这些系统资源的。通过此次实验，我进一步理解在计算机动态管理分区分配的知识。 二、实验要求

本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同分配算法的特点。 三、实验过程

1． 准备

（一）主程序

1、定义分区描述器node，包括 3个元素： （1）adr——分区首地址 （2）size——分区大小

（3）next——指向下一个分区的指针 2、定义 3个指向node结构的指针变量： （1）head1——空闲区队列首指针

（2）back1——指向释放区node结构的指针

（3）assign——指向申请的内存分区node结构的指针 3、定义 1个整形变量：

free——用户申请存储区的大小（由用户键入） （二）过程

1、定义check过程，用于检查指定的释放块（由用户键入）的合法性 2、定义assignment1过程，实现First Fit Algorithm 3、定义assignment2过程，实现Best Fit Algorithm

4、定义acceptment1过程，实现First Fit Algorithm的回收算法 5、定义acceptment2过程，实现Best Fit Algorithm的回收算法 6、定义print过程，打印空闲区队列 （三）执行

程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。

（四）输出

要求每执行一次，输出一次空闲区队列情况，内容包括： 编号 首址 终址 大小 （五）源代码

#include #include #include

#define MAX_SIZE 32767 typedef struct node {

int id; int adr; int size; struct node *next; }Node;

Node *head1,*head2,*back1,*back2,*assign; int request;

int check(int add,int siz,char c) {

Node *p,*head; int check=1; if(add<0||siz<0)

check=0;/*地址和大小不能为负*/ if(c=='f'||c=='F') head=head1; else

head=head2; p=head->next;

while((p!=NULL)&&check)

if(((addadr)&&(add+siz>p->adr))||((add>=p->adr)&&(addadr+p->size))) check=0; else

p=p->next; if(check==0)

printf(\输入释放区地址或大小有错误！！！\\n\ return check; }

void init() {

Node *p;

head1=(Node*)malloc(sizeof(Node)); head2=(Node*)malloc(sizeof(Node)); p=(Node*)malloc(sizeof(Node)); head1->next=p; head2->next=p; p->size=MAX_SIZE; p->adr=0; p->next=NULL; p->id=0; }

Node* assignment1(int num,int req)

{

Node *before,*after,*ass;

ass=(Node*)malloc(sizeof(Node)); before=head1;

after=head1->next; ass->id=num; ass->size=req;

while(after->size

before=before->next; after=after->next; }

if(after==NULL) {

ass->adr=-1; } else {

if(after->size==req) {

before->next=after->next; ass->adr=after->adr; } else {

after->size-=req; ass->adr=after->adr; after->adr+=req; } }

return ass; }

void acceptment1(int address,int siz,int rd) {

Node *before,*after; int insert=0;

back1=(Node*)malloc(sizeof(Node)); before=head1;

after=head1->next; back1->adr=address; back1->size=siz; back1->id=rd; back1->next=NULL; while(!insert&&after)

{//将要被回收的分区插入空闲区（按首址大小从小到大插入）

if((after==NULL)||((back1->adr<=after->adr)&&(back1->adr>=before->adr))) {

before->next=back1; back1->next=after; insert=1; } else {

before=before->next; after=after->next; } }

if(insert) {

if(back1->adr==before->adr+before->size) {//和前边分区合并

before->size+=back1->size; before->next=back1->next; free(back1); }

else if(after&&back1->adr+back1->size==after->adr) {//和后边分区合并

back1->size+=after->size; back1->next=after->next; back1->id=after->id; free(after); after=back1; }

printf(\首先分配算法回收内存成功！\\n\ } else

printf(\首先分配算法回收内存失败！\\n\}

Node* assignment2(int num,int req) {

Node *before,*after,*ass,*q; ass=(Node*)malloc(sizeof(Node)); q=(Node*)malloc(sizeof(Node)); before=head2;

after=head2->next; ass->id=num; ass->size=req; while(after->size

{

before=before->next; after=after->next; }

if(after==NULL) {

ass->adr=-1; } else {

if(after->size==req) {

before->next=after->next; ass->adr=after->adr; } else {

q=after;

before->next=after->next; ass->adr=q->adr; q->size-=req; q->adr+=req; before=head2;

after=head2->next; if(after==NULL) {

before->next=q; q->next=NULL; } else {

while((after->size)<(q->size)) {

before=before->next; after=after->next; }

before->next=q; q->next=after; } } }

return (ass); }

void acceptment2(int address,int siz,int rd)

{

Node *before,*after; int insert=0;

back2=(Node*)malloc(sizeof(Node)); before=head2;

after=head2->next; back2->adr=address; back2->size=siz; back2->id=rd; back2->next=NULL; if(head2->next==NULL) {//空闲队列为空 head2->next=back2;

head2->size=back2->size; } else

{//空闲队列不为空 while(after) {

if(back2->adr==after->adr+after->size) {//和前边空闲分区合并

before->next=after->next; after->size+=back2->size; back2=after; } else {

before=before->next; after=after->next; } }

before=head2;

after=head2->next; while(after) {

if(after->adr==back2->adr+back2->size) {//和后边空闲区合并

before->next=after->next; back2->size+=after->size; } else {

before=before->next;

after=after->next; } }

before=head2;

after=head2->next; while(!insert)

{//将被回收的块插入到恰当的位置（按分区大小从小到大）

if(after==NULL||((after->size>back2->size)&&(before->sizesize))) {

before->next=back2; back2->next=after; insert=1; break; } else {

before=before->next; after=after->next; } } }

if(insert)

printf(\最佳适应算法回收内存成功！\\n\else

printf(\最佳适应算法回收内存失败！！\\n\}

void print(char choice)//输出空闲区队列信息 {

Node *p;

if(choice=='f'||choice=='F') p=head1->next; else

p=head2->next; if(p) {

printf(\空闲区队列的情况为：\\n\ printf(\编号\\t首址\\t终址\\t大小\\n\ while(p) {

printf(\ p=p->next; } }

}

void menu()//菜单及主要过程 {

char chose;

int ch,num,r,add,rd; while(1) {

system(\

printf(\ printf(\最先适应算法\\n\ printf(\最佳适应算法\\n\ printf(\退出程序\\n\

printf(\ printf(\ scanf(\

if(chose=='e'||chose=='E') exit(0); else {

system(\ while(1) {

if(chose=='f'||chose=='F') printf(\最先适应算法:\\n\ if(chose=='b'||chose=='B') printf(\最佳适应算法:\\n\

printf(\ printf(\分配内存\\n\ printf(\回收内存\\n\ printf(\查看内存\\n\ printf(\返回\\n\

printf(\ printf(\ scanf(\ fflush(stdin); switch(ch) { case 1:

printf(\输入申请的分区大小：\ if(chose=='f'||chose=='F') assign=assignment1(num,r); else

assign=assignment2(num,r);

if(assign->adr==-1) {

printf(\分配内存失败！\\n\ } else

printf(\分配成功！分配的内存的首址为:%d\\n\ break; case 2:

printf(\输入释放的内存的首址：\ printf(\输入释放的内存的大小：\ printf(\输入释放的内存的编号：\ if(check(add,r,chose)) {

if(chose=='f'||chose=='F') acceptment1(add,r,rd); else

acceptment2(add,r,rd); }

break;

case 3:print(chose);break; case 4:menu(); break; } } } } }

void main()//主函数 {

init(); menu(); }

（六）运行结果

四．实验心得

通过这次实验我练习了用C语言写系统软件，对操作系统中动态可变分区存储管理有了更深刻的了解。刚开始编程时并没有什么思路，查阅相关书籍，浏览网上的论坛，查看数据结构书本后，才对这次实验有了编程思路，但是最大的心得是：在编程中总会遇到各种意想不到问题，一定要耐心解决。在解决一个个问题的同时，自己的编程能力也在提高。