操作系统实习报告.doc

实习一 处理器调度一、实习内容选择一个调度算法，实现处理器调度。二、实习目的在采用多道程序设计的系统中，往往若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占有处理器。本实习模拟在单处理器情况下的处理器调度，加深了解处理器调度的工作。三、实习题目设计一个按优先数调度算法实现处理器调度的程序。提示：(1) 假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为：进程名、指针、要求运行时间、优先数、状态。进程名P1P5。指针按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。要求运行时间假设进程需要运行的单位时间数。优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。(2) 每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。(3) 处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。(4) 进程运行一次后，若要求运行时间不等于0，则将它加入队列，否则，将状态改为“结束”，退出队列。(5) 若就绪队列为空，结束，否则，重复(3)。四、数据结构及符号说明进程的定义：struct pcb /* 定义进程控制块PCB */ char name10; /*进程名*/char state; /*进程状态，就绪或者完成*/int super; /*进程优先级*/int needtime; /*进程所需时间*/int runtime; /*进程已完成时间*/struct pcb* link; /*指向下一进程*/函数说明：1.void insert()功能：进程优先级排列函数，比较进程优先级，将其插入适当的位置。参数：super,依据进程优先级super来确定进程的插入位置。调用：被进程控制块函数和进程就绪函数调用。2.void input()功能：进程控制块函数参数：num,i,name,super,needtime调用：主函数main（）调用3. void disp(PCB * pr)功能：进程显示函数，用于显示当前进程。参数：name,state,super,needtime,runtime调用：被进程查看函数check（）调用4. void check()功能：进程查看函数，用于显示当前运行进程和就绪队列状态。参数：PCB* pr pr=ready调用：被主函数main（）调用5. void destroy()功能：进程撤消函数，用于当进程运行结束时，撤消进程。参数：p-name调用：被进程就绪函数running（）调用6. void running()功能：进程就绪函数，当进程运行时间到，置进程就绪状态。参数：p-runtime调用：被主函数main（）调用7. main()功能：主函数五、程序流程图六、实验源程序#include #include #include #define getpch(type) (type*)malloc(sizeof(type)struct pcb /* 定义进程控制块PCB */ char name10; char state; int super; int needtime; int runtime; struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB; void sort() /* 建立对进程进行优先级排列函数*/ PCB *first, *second; int insert=0; if(ready=NULL)|(p-super)(ready-super) /*优先级最大者,插入队首*/ p-link=ready; ready=p; else /* 进程比较优先级,插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) if(p-super)(second-super) /*若插入进程比当前进程优先数大,*/ /*插入到当前进程前面*/ p-link=second; first-link=p; second=NULL; insert=1; else /* 插入进程优先数最低,则插入到队尾*/ first=first-link; second=second-link; if(insert=0) first-link=p; int input() /* 建立进程控制块函数*/ int i,num; printf(n 请输入进程数?); scanf(%d,&num); for(i=0;iname); printf(n 输入进程优先数:); scanf(%d,&p-super); printf(n 输入进程运行时间:); scanf(%d,&p-needtime); printf(n); p-runtime=0;p-state=w; p-link=NULL; sort(); /* 调用sort函数*/ return num; void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/ printf(n qname t state t super t ndtime t runeedtime n); printf(|%st,pr-name); printf(|%ct,pr-state); printf(|%dt,pr-super); printf(|%dt,pr-needtime); printf(|%dt,pr-runtime); printf(n); void check() /* 建立进程查看函数 */ PCB* pr; printf(n * 当前正在运行的进程是:%s,p-name); /*显示当前运行进程*/ disp(p); pr=ready; printf(n *当前就绪队列状态为:n); /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr-link; void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/ printf(n 进程 %s 已完成.n,p-name); free(p); void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ (p-runtime)+; if(p-runtime=p-needtime) destroy(); /* 调用destroy函数*/ else (p-super)-; p-state=w; sort(); /*调用sort函数*/ main() /*主函数*/ int len,h=0; char ch; len=input(); while(len!=0)&(ready!=NULL) ch=getchar(); h+; printf(n The execute number:%d n,h); p=ready; ready=p-link; p-link=NULL; p-state=R; check(); running(); printf(n 按任一键继续.); ch=getchar(); printf(nn 进程已经完成.n); ch=getchar(); 实习二 主存空间的分配和回收一、实习内容主存储器空间的分配和回收。二、实习目的通过本实习帮助理解在不同的存储管理方式下应怎样进行存储空间的分配和回收。三、实习题目第一题：在可变分区管理方式下采用首次适应算法实现主存分配和回收。提示：(1) 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。假定内存大小为128K，初始状态见右图。空闲区说明表格式为：起始地址指出空闲区的起始地址；长度一个连续空闲区的长度；状态有两种状态，一种是“未分配”状态，另一种是“空表目”状态。(2) 采用首次适应算法分配。运行时，输入一系列分配请求和回收请求。四、程序流程为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：起 址长 度状 态第一栏14 K12 K未 分 配第二栏32 K96 K未 分 配MM空 表 目空 表 目MM其中：起址指出一个空闲区的主存起始地址。 长度指出从起始地址开始的一个连续空闲的长度。 状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的分配算法流程图：回收算法流程图： 六、实验源程序#include #include #include #define n 10 /*假定系统允许的最大作业为，假定模拟实验中n值为10*/#define m 10 /*假定系统允许的空闲区表最大为m，假定模拟实验中m值为10*/#define minisize 100structfloat address; /*已分分区起始地址*/float length; /*已分分区长度，单位为字节*/int flag; /*已分配区表登记栏标志，用0表示空栏目*/used_tablen; /*已分配区表*/structfloat address; /*空闲区起始地址*/float length; /*空闲区长度，单位为字节*/int flag; /*空闲区表登记栏标志，用0表示空栏目，用1表示未分配*/free_tablem; /*空闲区表*/void allocate(char J,float x)/*采用首次适应算法分配x大小的空间*/ int i,k; float ad; k=-1; for(i=0;i=x&free_tablei.flag=1) if(k=-1|free_tablei.lengthfree_tablek.length) k=i; if(k=-1)/*未找到可用空闲区，返回*/ printf(无可用空闲区n); return; /*找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于msize大小，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划出一部分分配*/if(free_tablek.length-x=minisize)free_tablek.flag=0;ad=free_tablek.address;x=free_tablek.length;elsefree_tablek.length=free_tablek.length-x;ad=free_tablek.address+free_tablek.length;/*修改已分配区表*/i=0;while(used_tablei.flag!=0&i=n) /*无表目填写已分分区*/printf(无表目填写已分分区，错误n);/*修正空闲区表*/if(free_tablek.flag=0)/*前面找到的是整个空闲分区*/free_tablek.flag=1;else/*前面找到的是某个空闲分区的一部分*/free_tablek.length=free_tablek.length+x;return;else/*修改已分配表*/used_tablei.address=ad;used_tablei.length=x;used_tablei.flag=J;return;/*主存分配函数结束*/void reclaim(char J)/*回收作业名为J的作业所占主存空间*/int i,k,j,s,t;float S,L;/*寻找已分配表中对应登记项*/s=0;while(used_tables.flag!=J|used_tables.flag=0)&s=n)/*在已分配表中找不到名字为J的作业*/printf(找不到该作业n);return;/*修改已分配表*/used_tables.flag=0;/*取得归还分区的起始地址S和长度L*/S=used_tables.address;L=used_tables.length;j=-1;k=-1;i=0;/*寻找回收分区的空闲上下邻，上邻表目k，下邻表目j*/while(im&(j=-1|k=-1)if(free_tablei.flag=1)if(free_tablei.address+free_tablei.length=S)k=i;/*找到上邻*/if(free_tablei.address=S+L)j=i;/*找到下邻*/i+;if(k!=-1)if(j!=-1)/* 上邻空闲区，下邻空闲区，三项合并*/free_tablek.length=free_tablej.length+free_tablek.length+L;free_tablej.flag=0;else/*上邻空闲区，下邻非空闲区，与上邻合并*/free_tablek.length=free_tablek.length+L;elseif(j!=-1)/*上邻非空闲区，下邻为空闲区，与下邻合并*/free_tablej.address=S;free_tablej.length=free_tablej.length+L;else/*上下邻均为非空闲区，回收区域直接填入*/*在空闲区表中寻找空栏目*/t=0;while(free_tablet.flag=1&t=m)/*空闲区表满,回收空间失败,将已分配表复原*/printf(主存空闲表没有空间,回收空间失败n);used_tables.flag=J;return;free_tablet.address=S;free_tablet.length=L;free_tablet.flag=1;return;/*主存回收函数结束*/main( )int i,a;float x;char J;/*空闲分区表初始化：*/free_table0.address=10240;free_table0.length=102400;free_table0.flag=1;for(i=1;im;i+)free_tablei.flag=0;/*已分配表初始化：*/for(i=0;in;i+)used_tablei.flag=0;while(1)printf(选择功能项（0-退出,1-分配主存,2-回收主存,3-显示主存）n);printf(选择功项(03) :);scanf(%d,&a);switch(a)case 0: exit(0); /*a=0程序结束*/case 1: /*a=1分配主存空间*/printf(输入作业名J和作业所需长度x: );scanf(%*c%c%f,&J,&x);allocate(J,x);/*分配主存空间*/break;case 2: /*a=2回收主存空间*/printf(输入要回收分区的作业名);scanf(%*c%c,&J);reclaim(J);/*回收主存空间*/break;case 3: /*a=3显示主存情况*/*输出空闲区表和已分配表的内容*/printf(输出空闲区表：n起始地址 分区长度 标志n);for(i=0;im;i+)printf(%6.0f%9.0f%6dn,free_tablei.address,free_tablei.length, free_tablei.flag);printf( 按任意键,输出已分配区表n);getch();printf( 输出已分配区表：n起始地址 分区长度 标志n);for(i=0;in;i+)if(used_tablei.flag!=0)printf(%6.0f%9.0f%6cn,used_tablei.address,used_tablei.length, used_tablei.flag);elseprintf(%6.0f%9.0f%6dn,used_tablei.address,used_tablei.length, used_tablei.flag);break;default:printf(没有该选项n);/*case*/*while*/*主函数结束*/实习三 磁盘存储空间的分配和回收一、实习内容模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。二、实习目的磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习使学生掌握磁盘存储空间的分配和回收算法。三、实习题目第二题：用位示图管理磁盘存储空间提示：(1) 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。位示图的形式与实习二中的位示图一样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。(2) 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共8个柱面，每个柱面有两个磁道（盘面），每个磁道分成4个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号位数4磁道号= 位数4物理记录号= (3) 归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。按照（2）中假设的盘组，归还块在位示图中的位置计算如下：字节号=柱面号位数=磁道号4+物理记录号(4) 设计申请一块磁盘空间和归还一块磁盘空间的程序。要求能显示或打印程序运行前和运行后的位示图；分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。(5) 假定已有如表4-1的磁盘空间被占用了，现在要申请五块磁盘空间，运行分配程序，按（4）中要求显示或打印运行的结果。然后再归还如表4-2的空间，运行回收程序，按（4）中的要求显示或打印运行结果。表4-1柱面号磁道号物理记录号001002010013100112表4-2柱面号磁道号物理记录号002010101四、数据结构及符号说明1数据结构说明：/*物理地址*/typedef struct address int cylinder; /*柱面号*/ int track; /*磁道号*/ int block; /*块号*/address;块的物理地址。可直接通过这来寻址。便于和位示图坐标进行转换。/*文件*/ typedef struct file int length; /*文件长度*/ block *head; /*文件的第一个块*/file;文件长度用来定量表明文件所需的空间大小，即物理块数。2函数说明/*初始化磁盘空间，用位示图表示*/void initialize()功能：按照题目要求，初始化磁盘空间，使用位示图来表示相应块的分配情况。参数：无。使用全局变量bitmap。调用：被主函数main()调用来初始化程序。/*转换。将位示图的坐标转换为物理地址*/address transform(int x,int y)功能：将位示图的坐标转换为相应块的物理地址。参数：int x,int y。 x，y表示位示图的坐标。调用：被cmalloc(file &list)调用计算物理地址。/*显示分配或回收文件的位示图或物理地址*/ void display(file list, bool s)功能：分配时把分配到的磁盘空间的物理地址显示出来，归还时把归还块对应于位示图的字节号和位数显示出来。参数：file list, bool s。调用：被cmalloc(file &list)和cfree (file list)调用。/*显示位示图*/void dis_map()功能：将位示图输出。参数：无。调用全局变量bitmap调用：被cmalloc(file &list)和cfree (file list)调用。/*分配文件需求空间*/ bool cmalloc(file &list)功能：依据文件的需求空间在位示图中找足够数目的空闲块。成功则分配且返回true。否则，返回false。参数：file &list。找到的物理块插入到list链表中。调用：被request()调用。/*回收已分配文件空间*/void cfree(file list)功能：回收作业job在内存中所占的空间。参数：file list。回收文件list的物理块。调用：被release()调用。/*请求分配程序*/ void request()功能：若有分配请求，则分配空间。参数：无。调用全局变量List,bitmap。调用：调用cmalloc(file &list)来分配磁盘空间。/*请求回收程序*/ void release()功能：若有回收请求，则回收空间。参数：无。调用全局变量List,bitmap。调用：调用cfree(file list)来回收文件list的磁盘空间。五、程序流程图 NNNYYYYNY开始构造初始磁盘分配情况，用位示图来表示显示此时磁盘的分配情况输入操作请求操作请求是分配？文件需求空间小于磁盘空闲块分配内存空间显示出错信息操作请求是回收？操作请求是退出?磁盘中存在此文件？退出程序输出归还块对应于位示图的字节号和位数输入错误N将位示图中的相应块置为“已分配”将位示图中的相应块置为“未分配”输出分配到的磁盘空间的物理地址六、实验源程序#include #include #define CYLINDER 8 /*一个盘组共 CYLINDER 个柱面*/#define TRACK 2 /*每个柱面有 TRACK 个磁道*/#define BLOCK 4 /*每个磁道分成 BLOCK 个物理记录*/#define T_BYTE CYLINDER /*位示图横坐标：字节数*/#define T_BIT TRACK*BLOCK /*位示图纵坐标：位数*/#define N 20 /*文件的最大个数*/bool bitmapT_BYTET_BIT; /*位示图定义*/int blocknum = T_BYTE * T_BIT; /*空闲块数目*/int n = 0; /*文件的编号*/*物理地址*/typedef struct address int cylinder; /*柱面号*/ int track; /*磁道号*/ int block; /*块号*/address; /*已分配给文件的块*/ typedef struct block address addr; /*块的物理地址*/ struct block *next; /*下一块*/block; /*文件*/ typedef struct file int length; /*文件长度*/ block *head; /*文件的第一个块*/file;file ListN; /*文件定义*/*初始化磁盘空间，用位示图表示*/void initialize() int c,t,b; /*将所有的块设为为分配*/ for(int i = 0; i T_BYTE; i+) for(int j = 0; j addr.cylinder,p-addr.track,p-addr.block); p = p-next; else /*显示回收文件的各块的位示图坐标*/ printf(回收文件在位示图中的位置: n); while (p != NULL) /*未显示完所有的块*/ i = p-addr.cylinder; /*物理地址转换为位示图坐标*/ j = p-addr.track * BLOCK + p-addr.block; printf(%d %dn,i,j); p = p-next; /*显示位示图*/void dis_map() int i, j; printf(当前位示图分配情况:n); for (i = 0;i T_BYTE;i+) for (j = 0;j blocknum) /*分配文件的需求空间大于空闲空间大小*/ return false; else for (int i = 0;i T_BYTE;i+) for (int j = 0;j addr = transform(i,j); list.head-next = NULL; p = list.head; /*使用p来构造文件链表*/ else /*不是头块，加在链表后面*/ q = (block *)malloc(sizeof(block); q-addr = transform(i,j); q-next = NULL; p-next = q; p = p-next; t+;blocknum-; /*磁盘空闲块减1*/ if (t = list.length) /*已分配给文件足够空间*/ return true; /*回收已分配文件空间*/void cfree(file list) block *p; int i, j; p = list.head; if (list.head = NULL) printf(文件已经回收，不存在!n); else while (p != NULL) /*未全部回收完*/ i = p-addr.cylinder; j = p-addr.track * BLOCK + p-addr.block; /*物理地址转换成位示图坐标*/ bitmapij = 0; /*设此块为未分配*/ p = p-next; /*请求分配程序*/ void request() bool s = 0; int size; printf(请输入文件所需要的大小:n); scanf(%d,&size); if (size n) /*磁盘中没有要回收的文件*/ printf(无此文件!n); else cfree(Listfile); /*回收*/ display(Listfile,s); /*显示分配文件的块*/ dis_map(); /*显示位示图*/ Listfile.head = NULL; Listfile.length = 0; /*将文件链表置空*/ int main() int order; initialize(); /*初始化*/ dis_map(); /*显示初始的位示图*/ while(1) printf(输入命令(1-请求分配，2-请求回收，0-退出程序)：n); scanf(%d,&order); if (order = 1) /*请求分配*/ request(); else if (order = 2) /*请求回收*/ release(); else if (order = 0) /*退出程序*/ exit(0); else printf(输入错误!n);