操作系统 课程设计(论文)
设计（论文）题目 进程调度与主存空间的分配与回收
学院名称 信息科学与技术学院
专业名称 软件工程
学生姓名
学生学号
任课教师
设计（论文）成绩
二零一五年一月十五日
实验一 进程调度
一、 实验目的
用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。
二、实验内容和要求
编写并调试一个模拟的进程调度程序，采用“简单时间片轮转法”调度算法对五个进程进行调度。
每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已运行时间、进程状态等等。
进程的到达时间及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪 W（Wait）、运行R（Run）两种状态之一。
就绪进程获得 CPU后都只能运行一个时间片。用运行时间加1来表示。
如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应分配时间片给就绪队列中排在该进程之后的进程，并将它插入就绪队列队尾。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。
三、实验主要仪器设备和材料
硬件环境：IBM-PC或兼容机
软件环境：C语言编程环境
四、实验原理及设计方案
1、进程调度算法：采用多级反馈队列调度算法。其基本思想是：当一个新进程进入内在后，首先将它放入第一个队列的末尾，按FCFS原则排队等待高度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行，以此类推。
2、实验步骤:
（1）按先来先服务算法将进程排成就绪队列。
（2）检查所有队列是否为空，若空则退出，否则将队首进程调入执行。
（3）检查该运行进程是否运行完毕，若运行完毕，则撤消进程，否则，将该进程插入到下一个逻辑队列的队尾。
（4）是否再插入新的进程,若是则把它放到第一逻辑队列的列尾。
（5）重复步骤（2）、（3）、（4），直到就绪队列为空。
五、流程图
是
是
六、结果过程及截图
初始化队列
输入所有进程后的进程信息如下：
按Y键继续运行进程：
按Y键继续运行进程：
运行若干次后的状态：
添加新的进程：
七、源代码
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
#define TIME 2//时间片长度
typedef struct pcb{//进程管理块
char name[10];//进程名字
char state; //进程状态
int queue; //进程所在的队列
int ntime; //进程需要运行的时间
int rtime; //进程已经运行的时间
int etime; //进程在本队列可运行的时间片
struct pcb *link;
}PCB;
PCB *ready = NULL, *pinsert = NULL, *pfend = NULL,*p =NULL; //就绪队列，进程插入位置的变量
int geti() //使用户仅能输入整数
{
char ch;
int i = 0;
fflush(stdin);
ch = getchar();
while(ch == '\n'){
printf("\tf输入不能为空..请重新输入\n");
fflush(stdin);
ch = getchar();
}
while(ch != '\n'){
if(ch > '9' || ch < '0'){
printf("\t输入有误!!输入只能为正整数，请重新输入...\n");
fflush(stdin);
i = 0;
ch = getchar();
}else{
i = i*10 + (ch - '0');
ch = getchar();
}
}
return i;
}
void findpos()//更新状态量
{
PCB *ps = pfend;
if(!ps || !ps -> link || (ps-> link->queue - ps->queue) > 1)
pinsert = ps;
else{
while (ps->link && ps ->link->queue != (pfend ->queue +2))
ps = ps->link;
pinsert = ps;
}
}
void insert()//插入进程
{
if(!ready ){
ready = p;
pfend = p;
pinsert = p;
}else if(ready ->queue == 1){//第一队列存在
p->link = pfend->link;
pfend->link = p;
pfend = p;
findpos();
}
else{
p->link = ready;
ready = p;
findpos();
}
}
void input()/*建立进程控制块函数*/
{
int i,num;
printf("\n请输入进程的个数?");
num = geti();
for(i=0; i < num; i++)
{
printf("\n进程号No.%d:\n",i+1);
p=getpch(PCB);
printf("\n输入进程名:");
scanf("%s",p->name);
printf("\n输入进程运行时间:");
p ->ntime = geti();
printf("\n");
p->rtime=0;
p->state='w';
p->queue =1;
p->etime = TIME;
p->link=NULL;
insert();/*调用insert函数*/
}
}
void disp(PCB *pr)/*建立进程现实函数，用于显示当前进程*/
{
printf("\nname\t state\t queue\t ntime\t rtime\t在队列可停留时间\t \n");
printf("|%s\t",pr->name);
printf(" |%c\t",pr->state);
printf(" |%d\t",pr->queue);
printf(" |%d\t",pr->ntime);
printf(" |%d\t",pr->rtime);
printf(" |%d\t",pr->etime);
printf("\n");
}
void check()/*建立进程查看函数*/
{
PCB *pr;
printf("\n ****当前正在运行的进程是:%s",ready->name);/*显示当前运行的进程*/
disp(ready);
pr= ready ->link;
printf("\n****当前就绪队列状态为:\n");/*显示就绪队列状态*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
void sort()//调整进程队列
{
if(!ready->link ||ready->queue < ready->link->queue) return;
p = ready ->link;
ready ->link = pinsert ->link;
pinsert ->link = ready;
pinsert = ready;
ready = p;
if (ready && ready -> queue == pinsert ->queue){
findpos();
}
}
void addnew()//添加新的进程
{
if(ready ->queue != 1){
(ready -> queue)++;
ready->etime *= 2;
ready -> state='w';
sort();/*调用sort函数*/
input();
}
else{
input();
}
}
void destroy()/*建立进程撤销函数(进程运行结束，撤销进程)*/
{
printf("\n进程[%s]已完成.\n",ready->name);
p = ready;
ready = ready->link;
free(p);
if (ready && ready -> queue == pinsert ->queue)
findpos();
}
void running()/*建立进程就绪函数(进程运行时间到，置就绪状态)*/
{
(ready -> rtime)++;
ready ->etime --;
if(ready->rtime == ready->ntime){
destroy();
return;
}else if(ready ->etime == 0){
int time = 2;
(ready -> queue)++;
for(int i = 2; i != ready->queue; ++i)
time *= 2;
ready->etime = time;
ready -> state='w';
sort();/*调用sort函数*/
}
}
void main()
{
char ch;
input();
while(ready != NULL)
{
printf("\nThe execute name:%s\n",ready ->name);
ready ->state = 'R';
check();
running();
printf("\n按i键添加新进程....按其他任意键继续运行...");
fflush(stdin);
ch = getchar();
if (ch == 'i'|| ch=='I')
addnew();
}
printf("\n\n 进程已经完成\n");
getchar();
}
实验二 主存空间的分配与回收
一、实验目的
熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。
二、实验内容和要求
主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。
可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。
实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。
三、实验原理及设计方案
1、循环首次适应算法
在该算法中，把主存中所有空闲区按其物理地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区表或链中。
2、实验步骤
（1）初始化空闲分区；
（2）反复对现有的空闲分区进行进程创建和撤消，即内存分配和回收；
（3）退出。
3、流程图
四、结果过程及截图
初始化主存大小后的状态
按1后分配一块内存：
按1后分配一块内存：
按2释放内存：
八、源代码
#include <stdio.h>
#include <malloc.h>
#include<conio.h>
#define getMEM() (MEM*)(malloc(sizeof(MEM)))
typedef struct Memory{//可用分区链表节点
int base;//基地址
int size;//大小
struct Memory *next;
}MEM;
MEM *pm = getMEM();//可用分区的链表头
MEM *temp;//
int SIZE;//总的内存的大小，由用户输入
int geti()//让用户只能输入正整数
{
char ch;
int i = 0;
fflush(stdin);
ch = getchar();
while(ch == '\n'){
printf("\tf输入不能为空..请重新输入\n");
fflush(stdin);
ch = getchar();
}
while(ch != '\n'){
if(ch > '9' || ch < '0'){
printf("\t输入有误!!输入只能为正整数，请重新输入...\n");
fflush(stdin);
i = 0;
ch = getchar();
}else{
i = i*10 + (ch - '0');
ch = getchar();
}
}
return i;
}
bool check(MEM* pm, int base, int size){//检查用户输入的合法性
MEM *p = pm;
p = pm;
while(p->next){
if(p->base + p->size <= base && base <= p->next->base && p->next->base >= base + size){
return true;
}
p= p ->next;
}
if(!p->next && p->base + p->size < SIZE){
if(p->base + p->size <= base && base <= SIZE && SIZE >= base + size)
return true;
}
return false;
}
bool release(MEM *pm, int base, int size){//释放内存空间
MEM *p = pm;
if(!check(pm, base ,size)){
return false;
}
while(p->next){
if(base + size <= p->next->base)
break;
p = p->next;
}
if(base == p->base + p->size){//低地址相邻
if(p ->next && p->next->base == base + size){//释放区上下都相邻
p->size += size + p->next->size;
temp = p->next;
p->next = p->next->next;
free(temp);
}else{//仅与地地址相邻
p->size += size;
}
}else if (p->next && p->next->base == base +size){//仅高地址相邻
p->next->base = base;
p->next->size += size;
}else{//释放区上下与空闲区都不相邻
temp = getMEM();
temp->size = size;
temp->base = base;
temp->next = p->next;
p->next = temp;
}
return true;
}
int allocMem(MEM *pm, int size){//分配内存空间
MEM *p = pm;
int base;
while(p->next){
if(p->next->size >= size)
break;
p = p->next;
}
if(!p->next)
return -1;
if(p->next->size == size){//空闲分区大小刚好等于所需分区
base = p->next->base;
p->next = p->next->next;
}else{
p->next->size -= size;
base = p->next->base;
p->next->base += size;
}
return base;
}
void print(MEM *pm){//打印空闲分区表和空闲分区链
MEM *p = pm->next;
puts("\n****************************空闲内存分区链:******************************\n");
puts("基地址\t\t\t\t大小\n");
while(p){
printf("%d\t\t\t\t%d\n",p->base,p->size);
p = p->next;
}
puts("\n****************************主存空间占用情况表:******************************\n");
puts("基地址\t\t\t\t大小\n");
p = pm;
while(p->next){
printf("%d\t\t\t\t%d\n",p->base + p->size, p->next->base - p->size - p->base);
p= p ->next;
}
if(p->base + p->size < SIZE)
printf("%d\t\t\t\t%d\n", p->base + p->size, SIZE- p->base - p->size);
}
void init(){//初始化总内存大小和空闲分区链的头结点
pm->base = 0;
pm->size = 0;
pm->next = getMEM();
puts("请输入可用内存空间大小: ");
SIZE = geti();
pm->next->size = SIZE;
pm->next->base = 0;
pm->next->next =NULL;
}
int main()
{
int size = 0,base = 0;
int ch;
init();
print(pm);
while(1){
puts("分配空间请按1,释放空间请按2\n");
ch = getche();
if( ch == '1'){
puts("\n请输入需要分配的空间大小: ");
size =geti();
if((base = allocMem(pm, size)) == -1)
puts("空闲内存分区大小不足\n");
else{
printf("\n分配内存成功,此次分配的内存基地址为%d\n",base);
print(pm);
}
}else if(ch == '2'){
puts("\n请输入要释放内存的基地址: ");
base = geti();
puts("\n请输入要释放内存的大小: ");
size = geti();
if(release(pm, base, size)){
puts("\n释放内存成功!!!!\n");
print(pm);
}else{
puts("非法操作,您所给的内存范围没有被分配出去:\n");
}
}
}
return 0;
}
