计算机操作系统
实验二 进程调度
1．目的和要求
通过这次实验，理解进程调度的过程，进一步掌握进程状态的转变、进程调度的策略，进一步体会多道程序并发执行的特点，并分析具体的调度算法的特点，掌握对系统性能的评价方法。
2．实验内容
阅读教材《计算机操作系统》第二章和第三章，掌握进程管理及调度相关概念和原理。
编写程序模拟实现进程的轮转法调度过程，模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。假设初始状态为：有n个进程处于就绪状态，有m个进程处于阻塞状态。采用轮转法进程调度算法进行调度(调度过程中，假设处于执行状态的进程不会阻塞)，且每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程。
程序要求如下：
1）输出系统中进程的调度次序；
2）计算CPU利用率。
3．实验环境
Windows操作系统、VC++6.0 C语言
4．设计思想
每个进程有一个进程控制块（ PCB—type）表示。进程控制块可以包含如下信息：进程名（pid），需要运行时间（cpu—time），进程状态（state）等等。进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是执行 2，就绪 1、阻塞0。就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的运行时间减1，然后把它插入就绪队列尾部等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。当就绪队列的进程全都完成以后将阻塞进程队首进程插入到就绪队列尾部以便下次进行调用，反复直到阻塞队列为空，进程全部执行完成则退出。
5．源程序
#include <stdio.h>
#include <stdlib.h>
struct PCB_type
{
int pid ; //进程名
int state ; //进程状态 2--表示"执行"状态1--表示"就绪"状态 0--表示"阻塞"状态
int cpu_time ; //运行需要的CPU时间（需运行的时间片个数）
};
struct QueueNode{
struct PCB_type PCB;
struct QueueNode *next;
};
//并设全程量：
struct QueueNode *ready_head=NULL, //ready队列队首指针
*ready_tail=NULL , //ready队列队尾指针
*blocked_head=NULL, //blocked队列队首指针
*blocked_tail=NULL; //blocked队列队尾指针
int static use_cpu,unuse_cpu;
/*定义进程的数目*/
//读入假设的数据，设置系统初始状态
void start_state()
{
int m,n,i;
struct QueueNode *p;
printf("输入就绪状态进程和阻塞状态进程个数 n,m:");
scanf("%d%d",&n,&m);
printf("就绪进程状态\n");
p=(struct QueueNode *)malloc(sizeof(struct QueueNode ));
p->next=NULL;
ready_head=ready_tail=p;
for(i=0;i<n;i++)
{
struct QueueNode *p;
p=(struct QueueNode *)malloc(sizeof(struct QueueNode ));
p->next=NULL;
printf("Enter %d process pid:",i+1);
scanf("%d",&p->PCB.pid);
printf("Enter %d process cpu_time:",i+1);
scanf("%d",&p->PCB.cpu_time);
p->PCB.state=1;
ready_tail->next=p;
ready_tail=p;
}
p=ready_head->next;
i=1;
printf("\n");
while(p)
{
printf("第%d个进程:%d %d和%d\n",i,p->PCB.pid,p->PCB.state,p->PCB.cpu_time);
p=p->next;
i++;
}
printf("阻塞进程状态");
p=(struct QueueNode *)malloc(sizeof(struct QueueNode ));
p->next=NULL;
blocked_head=blocked_tail=p;
for(i=0;i<m;i++)
{
struct QueueNode *p;
p=(struct QueueNode *)malloc(sizeof(struct QueueNode ));
p->next=NULL;
printf("Enter %d process pid:",i+1);
scanf("%d",&p->PCB.pid);
printf("Enter %d process cpu_time:",i+1);
scanf("%d",&p->PCB.cpu_time);
p->PCB.state=0;
blocked_tail->next=p;
blocked_tail=p;
}
p=blocked_head->next;
i=1;
printf("\n");
while(p)
{
printf（"第%d个进程:%d %d和%d\n",i
,p->PCB.pid,p->PCB.state,p->PCB.cpu_time);
p=p->next;
i++;
}
}
//模拟调度
void dispath()
{
struct QueueNode *p;
int x=0,t;
printf("输入时间片t:");
scanf("%d",&t);
use_cpu=0;
unuse_cpu=0;
while(ready_head!=ready_tail || blocked_head!=blocked_tail)
{
if (ready_head!=ready_tail)
{
p=ready_head->next;
ready_head->next=p->next;
p->next=NULL;
if(ready_head->next==NULL)
ready_tail=ready_head;
p->PCB.state =2;
printf("进程%d\n",p->PCB.pid);
p->PCB.cpu_time--;
use_cpu++;
if (p->PCB.cpu_time>0)
{
p->PCB.state =1;
ready_tail->next =p;
ready_tail=p;
}
else
{
printf("进程%d已完成\n",p->PCB.pid);
free(p);
}
}
else
{
unuse_cpu++;
}
x++;
if(blocked_head!=blocked_tail && x==t)
{
p=blocked_head->next;
blocked_head->next=p->next;
if(blocked_head->next==NULL)
blocked_tail=blocked_head;
//p->next=NULL;
ready_tail->next=p;
ready_tail=p;
p->next=NULL;
x=0;
}
}
printf("%d\n",unuse_cpu);
printf("%d\n",use_cpu);
}
//计算CPU利用率
void calculate()
{
double f;
f=(double)use_cpu/use_cpu+unuse_cpu;
printf("PCB的利用率为%lf",f);
}
void main()
{
start_state();
dispath();
calculate();
}
6．实例运行结果
7．实验总结
这是第一次操作系统实验，用c语言编写模拟进程调度算法。由于c语言学了很长时间了，好多东西都忘了，所以最初在实验室的两个小时都毫无头绪，尽管老师已经给了一些代码，还把主要地方的流程图给了我们，还是觉得有难度。许老师看我们毫无进展，就集中给我们讲解了一下，一步步告诉我们怎么写，听完老师的讲解，自己也能回忆起一些c的知识，老师讲完后自己在开始写就觉得轻松了许多。通过操作系统实验让我认识到自己知识掌握的还不够牢靠，学过的知识不能灵活的运用，以后再学习过程中一定不要丢三落四，学过的知识还是要多巩固。希望下次实验可以做的更好。
实验三 可变分区存储管理
1．目的和要求
通过这次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。
2．实验内容
编写程序模拟实现内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。
假定系统的内存共640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。
3．实验环境
Windows操作系统、VC++6.0
C语言
4．设计思想
首先定义自由链和占用链两个链表结点，当申请内存分配时，自由链释结点刚好等于要申请的内存时直接分配，大于时剪切满足要求的分配；并将结点插入到占用链尾部，并修改尾部指针。作业完成释放内存时，先在占用链表中找到要释放的内存地址，修改相邻结点指针，再在自由链中寻找适合释放的内存大小的位置并插入进去。主要子函数有模拟分配函数和模拟回收函数，并在主函数中调用。
5．源程序
#include<stdio.h>
#include<stdlib.h>
struct freelink{
int len, address; // len为分区长度 address为分区起始地址
struct freelink *next;
};
//内存占用区用链表描述，其结点类型描述如下：
struct busylink{
char name; // 作业或进程名 name=’S’ 表示OS占用
int len , address;
struct busylink *next;
};
//并设全程量：
struct freelink *free_head=NULL; //自由链队列（带头结点）队首指针
struct busylink *busy_head=NULL, //占用区队列队（带头结点）首指针
*busy_tail=NULL; //占用区队列队尾指针
void start(void) /* 设置系统初始状态*/
{
struct freelink * p;
struct busylink *q;
free_head=(struct freelink*)malloc(sizeof(struct freelink));
free_head->next=NULL; // 创建自由链头结点
busy_head=busy_tail=(struct busylink*)malloc(sizeof(struct busylink));
busy_head->next=NULL; // 创建占用链头结点
p=( struct freelink *)malloc(sizeof(struct freelink));//自由链头结点
p->address=64;
p->len=640-64; ///（OS占用了64K）
p->next=NULL;
free_head->next=p;
q=( struct busylink *)malloc(sizeof(struct busylink));//占用链头结点
q->name='S'; /* S表示操作系统占用 */
q->len=64;
q->address=0;
q->next=NULL;
busy_head->next=q;
busy_tail=q;
}
/*模拟内存分配*/
void requireMemo(char name, int require)
{
struct busylink *p;
struct freelink *u,*v,*w;
if(free_head->next->len>=require)
{
p=(struct busylink*)malloc(sizeof(struct busylink));
p->name=name;
p->address=free_head->next->address;
p->len=require;
p->next=NULL;
busy_tail->next=p;
busy_tail=p;
w=free_head->next;
free_head->next=w->next;
if(w->len==require)
free(w);
else //为w寻找合适的位置插入
{
w->address=w->address+require;
w->len=w->len-require;
u=free_head;
v=free_head->next;
while(v!=NULL&&v->len>w->len)
{
u=v;
v=v->next;
}
u->next=w;
w->next=v;
}
}
else
printf("Can't allocate");
}
/* 模拟内存回收*/
void freeMemo(char name)
{
struct busylink *q,*p;
struct freelink *u,*w,*v;
int address,len;
q=busy_head;
p= busy_head->next;
while(p!=NULL&&p->name!=name)
{
q=p;
p=p->next;
}
if(p==NULL)
printf("%c is not exist",name);
else
{
if(p==busy_tail)
busy_tail=q;
q->next=p->next;
len=p->len;
address=p->address;
free(p);
//在自由链中为p寻找合适的位置插入
w=( struct freelink*) malloc(sizeof(struct freelink));
w->len=len;
w->address=address;
u=free_head;
v=free_head->next;
while(v!=NULL&&v->len>w->len)
{
u=v;
v=v->next;
}
u->next=w;
w->next=v;
}
}
/* 模拟系统过了time 时间*/
void past(int time)
{
printf("系统过了%d时间\n",time);
}
/* 输出内存空闲情况（自由链的结点） */
void printlink()
{
struct freelink *p;
int len=0;
p=free_head->next;
printf("此时空闲区状态:起始地址为%d\n",free_head->next->address);
while(p!=NULL)
{
len+=p->len;
p=p->next;
}
printf("此时内存的空闲量%d\n",len);
}
void printlink2()
{
struct busylink *p;
int len=0;
p=busy_head->next;
printf("此时占用区状态:起始地址为%d\n",busy_head->next->address);
while(p!=NULL)
{
len+=p->len;
p=p->next;
}
printf("此时内存的占用量%d\n",len);
printf("\n");
}
void main()
{
start();
printlink();
printlink2();
past(1);
requireMemo('A',8);
requireMemo('B',16);
requireMemo('C',64);
requireMemo('D',124);
printlink();
printlink2();
past(2);
freeMemo('C');
printlink();
printlink2();
past(3);
requireMemo('E',50);
printlink();
printlink2();
freeMemo('D');
printlink();
printlink2();
}
6．运行结果
7．实验总结
这次实验做起来相对比较轻松，一方面老师上课时将主要思想详细讲解了一遍，实验指导书上流程图也相对比较详细，另一方面，由于上次实验，自己对C语言的一些知识点也回忆起来不少，和上次一样，也主要涉及链表和指针，参考流程图很快便将代码写完了。但调试却花了一定的时间，由于开始在写输出内存空闲量和占用量时将输出语句直接写成printf（“空闲区空闲量为%d：”，free_head—>next—>len）运行后总觉得结果有问题，后来自己仔细想想又动手画一画觉得这里出现了问题，应该用循环语句将所有结点的内存大小相才行，语句改好后再运行，结果就对了。从这次实验，我觉得调试的过程是不简单的，但却很有意义，自己在调试过程中可以进一步了解自己的程序，把自己当电脑来一步步执行自己的程序，便可以很快找出问题所在。虽然是模拟分区存储管理，但通过这个实验也让自己对内存的分配与回收有了更深的了解。
实验四 操作系统存储管理实验
一、实验目的：
1、通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。
2、通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
二、实验环境：
VC 6.0++
三、实验内容
1、设计页面置换程序，模拟实现下面三种页面置换算法：
FIFO、LRU、OPT算法设计一个请求页式存储管理方案。
2、设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 实现下面三种算法：
首次适应算法 ，最佳适应算法 ，最差适应算法
四、实验设计原理
1、页式存储系统打破存储分配的连续性，使得一个程序的逻辑地址空间可以分布在若干个离散的内存块上，从而达到充分利用内存，提高内存效率的目的。
页式存储系统将内存分为等长的若干区域，每个区域即一个页面。在对用户程序进行分配时，由系统调用页面置换算法对程序地址进行分配。常用页面置换算法有如下几种：
理想页面（OPT）置换算法：发生缺页时，有些页面在内存中将很快被访问，而其他页可能要到10、100或1000条指令后才被访问，对每个页面首次访问前要执行的指令数进行标记，置换掉最大的标记数页面。
先进先出（FIFO）置换算法：发生缺页时，总是选择最先装入的页面调出。
最近最少使用（LRU）置换算法：发生缺页时，总是选择距离现在最长时间没有使用的页面调出，而将使用过的页面放在最近位置。
2、分区分配
分区管理是能满足多道程序运行的最简单的存储管理方案。其基本思想是把内存划分成若干个连续区域，成为分区，每个分区装入一个运行程序。分区的方式可以归纳成固定分区和可变分区。
五、算法设计与流程
程序设计流程图如下：
1、页面置换算法流程图：
1、页面置换算法程序设计如下：
#include<iostream.h>
#define M 40
#define N 10//可用内存页面
struct Pro//页面结构体
{
int num;
int time;
};
int Input(int m, Pro p[])
{
cout<<"请输入实际页数：";
do
{
cin>>m;
if(m>M) cout<<"数目太多，请重试"<<endl;
else break;
}while(1);
cout<<endl<<"请输入各页面号"<<endl;
for(int i=0;i<m;i++)
{
cin>>p[i].num;
p[i].time=0;
}
return m;
}
void Print(Pro *page, int n)//打印当前的页面
{
for(int i=0; i<n; i++)
cout<<page[i].num<<" ";
cout<<endl;
}
int Search(int e, Pro *page, int n)//在内存页面中查找
{
for(int i=0; i<n; i++)
if(e==page[i].num)
return i;
return -1;
}
int Max(Pro *page, int n)
{
int e=page[0].time, i=0;
while(i<n) //找出离现在时间最长的页面
{
if(e < page[i].time)
e=page[i].time;
i++;
}
for(i=0; i<n; i++)
if(e==page[i].time)
return i;
return -1;
}
int Compfu(Pro *page, int i, int t, Pro p[])
{
int count=0;
for(int j=i; j<M; j++)
{
if(page[t].num==p[j].num ) break;
else count++;
}
return count;
}
int main()
{
int nu;
cout<<"可用内存页面数:"<<endl;
cin>>nu;
if(nu>N)
{
cout<<"页面过大"<<endl;
return 0;
}
Pro p[M];
Pro page[N];
char c;
int m=0/*实际页数*/, t=0/*页面循环*/;
float n=0; //缺页次数
m = Input(m, p);
do{
for(int i=0; i<nu; i++)//初始化页面基本情况
{
page[i].num=0;
page[i].time=2-i;
}
/*int j=0,count=1;
page[0].num=p[0].num;
int i=1,k=1;
while(i<N)
{
int flag=1;
for(j=0;j<i;j++)
if(p[k].num==page[i].num)
{n++;flag=0;break;}
if(flag==1){page[i].num=p[k].num;i++;}
count++;k++;
}*/
i=0;
cout<<"f:FIFO页面置换"<<endl;
cout<<"l:LRU页面置换"<<endl;
cout<<"o:OPT页面置换"<<endl;
cout<<"按其它键结束"<<endl;
cin>>c;
if(c=='f')//FIFO页面置换
{
n=0;
cout<<"页面置换情况: "<<endl;
while(i<m)
{
if(Search(p[i].num, page, nu)>=0) i++;//找到相同的页面
else
{
if(t==nu) t=0;
n++;//缺页次数加1
page[t].num=p[i].num;
Print(page, nu);
t++;
i++;
}
}
cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;
}
i=0;
if(c=='l')//LRU页面置换
{
n=0;
cout<<"页面置换情况： "<<endl;
while(i<m)
{
if(Search(p[i].num, page, nu)>=0)
{
int j=Search(p[i].num, page, nu);
for(int k=j; k>0; k--)
page[k].num=page[k-1].num;
page[k].num=page[j].num;
i++;
}
else
{
if(t==nu) t=0;
n++;
for(int k=nu-1; k>0; k--)
page[k].num=page[k-1].num;
page[k].num=p[i].num;
Print(page, nu);
t++;
i++;
}
}
cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;
}
if(c=='o')//OPT页面置换
{
n=0;
while(i<m)
{
if(Search(p[i].num, page, nu)>=0) i++;
else
{
int temp=0, cn;
for(t=0; t<nu; t++)
{
if(temp < Compfu(page, i, t, p))
{
temp=Compfu(page,i,t,p);
cn=t;
}
}
page[cn]=p[i];
n++;
Print(page, nu);
i++;
}
}
cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;
}
}while(c=='f'||c=='l'||c=='o');
return 0;
}