操作系统课设报告.doc

操作系统课程设计报告时间：2013-1-72013-1-18地点：信息技术实验中心计算机科学与技术专业2010级01班06号赖敏2013-1-18目录一 课程设计的目的和意义3二 进程调度算法模拟31 设计目的32 设计要求33 使用动态优先权的进程调度算法的模拟4三 动态分区分配方式模拟111 设计目的112 设计要求113 模拟算法的实现123.3.1 首次适应算法133.3.2 最佳适应算法13四 请求调页存储管理方式模拟181 设计目的182 设计要求183 模拟算法的实现184.3.1OPT算法184.3.2FIFO算法214.3.3LRU算法22五 简单文件系统的实现241 设计目的242 设计要求243 模拟算法的实现25六 总结40一 课程设计的目的和意义操作系统课程设计是计算机科学与技术专业的重要实践性教学环节。在进行了专业基础课程和操作系统原理课程学习的基础上，设计或分析一个实际的操作系统旨在加深对计算机硬件结构和系统软件的认识，初步掌握操作系统组成模块和应用接口的使用方法，提高进行工程设计和系统分析的能力，为毕业设计及以后的工程实践打下良好的基础。通过课程设计, 加深对操作系统各资源管理模块的理解,掌握操作系统的基本原理及功能, 具有初步分析实际操作系统、设计、构造和开发现代操作系统的基本能力1、巩固和加深对操作系统原理的理解，提高综合运用本课程所学知识的能力。2、培养学生选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际操作系统的分析设计、编程调试，掌握系统软件的分析方法和工程设计方法。4、能够按要求编写课程设计报告书，能正确阐述设计和实验结果、正确绘制系统和程序框图。5、通过课程设计，培养学生严谨的科学态度，严肃认真的工作作风和团队协作精神。二 进程调度算法模拟1 设计目的通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。2 设计要求（1）用C语言来实现对N个进程采用动态优先算法的进程调度；（2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：l 进程标识符idl 进程优先数priority，并规定优先数越大的进程，其优先权越高；l 进程已占用的CPU时间cputime；l 进程还需占用的CPU时间alltime，当进程运行完毕时，alltime变为0；l 进程的阻塞时间startblock，表示当进程再运行startblock个时间片后，进程将进入阻塞状态；l 进程被阻塞的时间blocktime，表示已阻塞的进程再等待blocktime个时间片后，将转换成就绪态l 进程状态state；l 队列指针next，用来将PCB排成队列（3）优先数改变的原则：l 进程在就绪队列中呆一个时间片，优先数增加1l 进程每运行一个时间片，优先数减3。（4）假设在调度前，系统中有5个进程，它们的初始状态如下：ID01234PRIORITY93830290CPUTIME00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEREADYREADYREADYREADYREADY（5）为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来，参照的具体格式如下：RUNNING PROG： iREADY_QUEUE:-id1-id2BLOCK_QUEUE:-id3-id4=ID 01234PRIORITY P0P1P2P3P4CPUTIME C0C1C2C3C4ALLTIME A0A1A2A3A4STARTBLOCK T0T1T2T3T4BLOCKTIME B0B1B2B3B4STATE S0S1S2S3S43 使用动态优先权的进程调度算法的模拟（1） 流程图如图1.3.1：NYNYNY开始创建N个进程并初始化pcbN根据进程状态初始化阻塞队列和就绪队列在就绪队列中找出优先权最大的进程运行进程运行完毕即alltime=0删除该进程运行一个时间片就绪队列中其他进程优先数prority+1进程运行完毕优先数priority-3结束阻塞就绪转换进程调入就绪队列或阻塞队列1.3.1- 动态优先权进程调度流程图（2） 实验效果图：1）输入进程的初始状态进行初始化如图1.3.2：1.3.2- 初始化进程状态2）运行部分结果如图1.3.3：1.3.3- 运行结果（3）实验关键代码：#define N 5 /默认进程数 int count;/定义进程结构体 typedef struct pcbint id; /进程id号int priority; /进程优先权int cputime; /占用cpu时间int alltime; /进程运行完成时间int startblock; /进程开始阻塞时间int blocktime; /进程阻塞到恢复就绪时间char state; /进程状态pcb* next; /指向下一个进程指针pcb,*pcb_link;/初始化进程 pcb_link initTask(pcb pcb) int i; char c; pcb_link plink=(pcb_link)malloc(sizeof(pcb); /就绪队列创建头指针 plink-next=NULL; printf(请初始化%d个进程：n,N);printf(ID ); /初始化进程idfor(i=0;iN;i+) pcbi.id=i; printf(%-8d,i);printf(nn);printf(PRIORITY ); /初始化进程优先权for(i=0;iN;i+)scanf(%d,&pcbi.priority);printf(n);printf(CUPTIME ); /初始化进程占用cpu时间for(i=0;iN;i+) scanf(%d,&pcbi.cputime);printf(n);printf(ALLTIME ); /初始化进程需要运行时间for(i=0;iN;i+) scanf(%d,&pcbi.alltime);printf(n);printf(STARTBLOCK ); /初始化进程开始阻塞时间for(i=0;iN;i+) scanf(%d,&pcbi.startblock);printf(n);printf(BLOCKTIME ); /初始化进程阻塞到恢复就绪时间for(i=0;iN;i+) scanf(%d,&pcbi.blocktime);printf(n);printf(STATE ); /初始化进程状态for(i=0;iN;i+) c=getchar(); while(c= |c=n) c=getchar(); pcbi.state=c;for(i=0;inext=&pcb0; 就绪队列return plink; */在就绪队列中找到优先数最大的进程 int maxPriority(pcb_link ready_q)pcb_link p;p=ready_q-next;int prog,max;max=prog=INT_MIN;while(p)if(p-prioritymax) prog=p-id; max=p-priority;p=p-next; return prog; /进程运行函数 void run(pcb_link ready_q,pcb_link block_q,int prog) pcb_link p,running_p=NULL; if(-1prog&prognext; while(p) if(p-id=prog) running_p=p; /running_p指向运行的进程 else p-priority+=1; /就绪队列中其他进程priority+1 p=p-next; running_p-priority-=3; /* running_p-cputime+=1; running_p-alltime-=1; if(running_p-startblock0) running_p-startblock-=1; 改变运行进程 if(running_p-alltime=0) 的信息和状态 running_p-state=F; else if(running_p-startblock!=0) running_p-state=R; else running_p-state=B; */ p=block_q-next; while(p) p-blocktime-=1; if(p-blocktime=0) /判断阻塞队列中进程状态是否变成就绪状态 p-state=R; p=p-next; /进程调入或调出就绪队列函数 void ready_or_block(pcb_link ready_q,pcb_link block_q,int prog,pcb pcb)pcb_link p,q,ready_end,block_end,t;ready_end=block_end=t=NULL;p=ready_q;while(p-next) p=p-next;ready_end=p; /就绪队列尾指针q=block_q;p=block_q-next;while(p) if(p-state=R) t=p; q-next=t-next; /* 阻塞队列中就绪进程 t-next=ready_end-next; 插到就绪队列尾部 ready_end-next=t; */ ready_end=t; /修改就绪队列尾指针 else q=p;p=q-next; block_end=q;if(prog-1&prognext; if(pcbprog.state=B) /* while(p-id!=prog&p) q=p; 运行后进程变成阻塞状态p=p-next; 插到阻塞进程尾部 q-next=p-next; p-next=block_end-next; block_end-next=p; /修改阻塞队列尾指针 */ else if(pcbprog.state=R) while(p-id!=prog&p) q=p; p=p-next; if(p-next) q-next=p-next; p-next=ready_end-next; ready_end-next=p; else /* count+; while(p-id!=prog&p) 进程运行完毕 q=p; 进程计数器count+p=p-next; 并删除该进程 q-next=p-next; */ int main(void)pcb pcbN; /创建进程数组pcb_link ready,block; /创建就绪和阻塞队列头指针int program;count=0; /进程计数器初始为0block=(pcb_link)malloc(sizeof(pcb); block-next=NULL;ready=initTask(pcb); /初始化进程printf(nnn运行过程:n);while(countN)program=maxPriority(ready);run(ready,block,program);ready_or_block(ready,block,program,pcb); print(program,ready,block,pcb);三 动态分区分配方式模拟1 设计目的了解动态分区分配方式中使用的数据结构和分配算法并进一步加深对动态分区存储管理方式及其实现过程的理解。2 设计要求（1）用C语言或C+语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端空间。（2）假设初始状态如下，可用的内存空间为640KB，并有下列请求序列：l 作业1 申请 130KB l 作业2 申请 60KBl 作业3 申请 100KBl 作业2 释放 60KBl 作业4 申请 200KBl 作业3 释放 100KBl 作业1 释放 130KBl 作业5 申请 140KBl 作业6 申请 60KBl 作业7 申请 50KBl 作业6 释放 60KB 请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。3 模拟算法的实现NY开始初始化空闲分区初始化各任务选择分区模式，输入F首次适应算法分区最佳首次适应算法分区初始化各任务结束算法流程图如图2.3.1：2.3.1- 动态分区分配流程图3.3.1 首次适应算法首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要求的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。算法代码如下：void alloc(space free,task tsk,int task_id)int i;for(i=0;i=tsktask_id.size) /找到第一个够分的空间块 freei.size-=tsktask_id.size; tsktask_id.workplace=i; break; if(i=free_block) printf(任务%d分配空间失败n,task_id); /分配失败输出/释放任务空间void fre(space free,task tsk,int task_id) int work; work=tsktask_id.workplace; freework.size+=tsktask_id.size; /空间块空间增加 tsktask_id.workplace=-1;3.3.2 最佳适应算法最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直接分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。最佳适应算法和首次适应算法的不同之处是，在为进程分配和释放一个空间后对分区链表进行一次从小到大的排序。算法代码如下：/没分配完一个分区或进程释放空间，对分区链表进行排序void sort(space_link slink)space_link tp,t,p,q;tp=(space_link)malloc(sizeof(space); /创建临时头指针，用来指向已排序的分区tp-next=NULL;t=slink-next;slink-next=t-next;t-next=tp-next;tp-next=t;t=slink-next;while(t)q=tp;p=tp-next;while(p)if(t-sizep-size) /找到待排序的分区在有序链表里的位置q=p;p=p-next;elsebreak;slink-next=t-next; /*t-next=p;q-next=t; 插入有序链表t=slink-next; */slink-next=tp-next;free(tp);关键实验代码如下：#define free_block 5 /空闲分区块数 #define free_space 640 /空闲分区总数 #define N 7 /任务数 /定义分区块 typedef struct spaceint id; /分区块idint size; /分区块大小space *next; /指向下一个分区块space,*space_link;/定义任务结构体 typedef struct taskint id; /任务idint size; /任务需要空间大小int workplace; /申请到的空间块task,*task_link;/初始化分区 space_link init_space(space free)int i,sum,a;space_link sh;sum=0;a=40; /初始大小40sh=(space_link)malloc(sizeof(space);for(i=0;ifree_block;i+) freei.id=i; /初始分区块idif(ifree_block-1) freei.size=a; /初始分区块大小else freei.size=free_space-sum; /剩余空间都分在最后一块sum+=a;a+=40;for(i=0;inext=&free0; */return sh; /返回链表头指针 /初始化任务 void init_task(task_link tsk,int task_id,int size)tsk-id=task_id;tsk-size=size;tsk-workplace=-1; /申请到的空间块初始为-1int main(void)space spafree_block;task tskN;space_link space_head;char c;space_head=init_space(spa);printf( 动态分区分配方式的模拟n);printf(亲输入分区方式，F用首次适应算法分配，B用最佳适应算法分配nn);printf(请选择分配方式:);scanf(%c,&c);printf(nn);if(c=F) /首次适应算法init_task(&tsk0,0,130); /初始任务0alloc(spa,tsk,0); /给任务0分配空间print(space_head); /输出分区状态init_task(&tsk1,1,60); alloc(spa,tsk,1);print(space_head);init_task(&tsk2,2,100);alloc(spa,tsk,2);print(space_head);fre(spa,tsk,1); /释放任务1空间print(space_head);init_task(&tsk3,3,200);alloc(spa,tsk,3);print(space_head);fre(spa,tsk,2);print(space_head);fre(spa,tsk,0);print(space_head);init_task(&tsk4,4,140);alloc(spa,tsk,4);print(space_head);init_task(&tsk5,5,60);alloc(spa,tsk,5);print(space_head);init_task(&tsk6,6,50);alloc(spa,tsk,6);print(space_head);fre(spa,tsk,5);print(space_head);else if(c=B) /最佳首次适应算法 init_task(&tsk0,0,130);alloc(spa,tsk,0);sort(space_head);print(space_head);init_task(&tsk1,1,60);alloc(spa,tsk,1);sort(space_head);print(space_head);init_task(&tsk2,2,100);alloc(spa,tsk,2);sort(space_head);print(space_head);fre(spa,tsk,1);sort(space_head);print(space_head);init_task(&tsk3,3,200);alloc(spa,tsk,3);sort(space_head);print(space_head);fre(spa,tsk,2);sort(space_head);print(space_head);fre(spa,tsk,0);sort(space_head);print(space_head);init_task(&tsk4,4,140);alloc(spa,tsk,4);sort(space_head);print(space_head);init_task(&tsk5,5,60);alloc(spa,tsk,5);sort(space_head);print(space_head);init_task(&tsk6,6,50);alloc(spa,tsk,6);sort(space_head);print(space_head);fre(spa,tsk,5);sort(space_head);print(space_head);运行结果图如图2.3.2：2.3.2- 运行结果四 请求调页存储管理方式模拟1 设计目的熟练掌握操作系统中请求调页方式的存储管理算法。2 设计要求1) 假设每个页面中可以存放10条指令，分配给一个作业的内存块数为4；2) 用C语言模拟一作业的执行过程，改作业共320条指令，即其地址空间为32页，目前他的所有页还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转到下一条指令，如果所访问指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存；如果4个内存块中均有内容， 则需进行页面置换；最后显示其物理地址，并转向下一条指令。在所有的320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3) 置换算法请分别采用OPT、FIFO和LRU；4) 作业中的指令顺序按如下原则生成：l 50%的指令顺序执行；l 25%的指令跳转到当前地址前（目标地址随机生成）；l 25%的指令跳转到当前地址后（目标地址随机生成）；具体的实施方法是： 在0，319的指令地址之间随机选取一条起始执行指令，其序号为m； 顺序执行下一条指令，即序号为m+1的指令； 通过随机数跳转到前地址部分0,m-1中的某条指令处，其序号为； 顺序执行下一条指令，其地址为+1的指令； 通过随机数跳转到后地址部分+2,319中的某条指令处，其序号为； 顺序执行下一跳指令，即序号为+1的指令； 重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。3 模拟算法的实现4.3.1 OPT算法OPT算法关键代码如下：void opt(memory*m,pagepag)int i,j,m1,m2,m3,p,order_id,a3203,bBLOCK_N=-1,-1,-1,-1;/数组a用来存放320执行指令，数组b用来存放当前内存块中指令count_order=i=j=0; /初始化指令数组 for(j;j320;j+)aj0=-1;aj1=INT_MAX;aj2=-1; /随机生成320条指令m1=random_order(0,319); p=belong_page(m1);order_id=belong_orderId(m1);pagp.ordorder_id.state=1;ai0=p;ai2=m1;i+; /数组a的下标加1count_order+; /指令计数器加1if(m1+1320)p=belong_page(m1+1); /顺序执行下一条指令order_id=belong_orderId(m1+1);pagp.ordorder_id.state=1; /修改指令状态ai0=p; /指令所在页号存入ai0ai2=m1+1; /指令号存入数组ai2 /printf(%dn,ai0);i+;count_order+; /指令计数器加1while(count_order-1) m2=random_order(0,m1-1); /跳转到前地址指令 p=belong_page(m2); order_id=belong_orderId(m2); pagp.ordorder_id.state=1; ai0=p; ai2=m2; /存入数组a /printf(%dn,ai0); i+; count_order+; /指令计数器加1 if(m2+1320) /顺序执行下一条指令 p=belong_page(m2+1); order_id=belong_orderId(m2+1); pagp.ordorder_id.state=1; ai0=p; ai2=m2+1; /存入数组a/printf(%d,ai0);i+; count_order+; /指令计数器加1 if(m2+2320) /跳到后地址指令 m3=random_order(m2+2,319); /随机生成指令 p=belong_page(m3); order_id=belong_orderId(m3); pagp.ordorder_id.state=1; ai0=p; /页号存入ai0 ai2=m3; /指令号存入ai2 /printf(%dn,ai0);i+; count_order+; /指令计数器加1 if(m3+1320) /顺序执行下一条指令 p=belong_page(m3+1); order_id=belong_orderId(m3+1); pagp.ordorder_id.state=1; /修改指令状态，标记为1 ai0=p; ai2=m3+1;/printf(%d,ai0);i+; count_order+; /指令计数器加1 for(i=0;i320-1;i+) for(j=i+1;j320;j+) if(aj0=ai0) ai1=j; /找到下一个同页号的位置for(i=0;iblockm-point=-1) /内存块没有装满pagai0.workplace=m-point;m-blockm-point=ai0;m-point=(m-point+1)%BLOCK_N; /指向下一个内存块的位置bm-point=ai2; /数组b记录指令号print(*m); /输出内存块状态printf(n); else /内存块已满，需置换 m2=-1; for(j=0;jm2)m2=am11;m3=j; /在数组b中找到需置换的指order_id=bm3; p=belong_page(order_id); /计算页号m1=pagp.workplace;pagp.workplace=-1; /修改被置换页的状态bm3=ai2; /新指令替换原指令m-blockm1=ai0; /内存块替换pagai0.workplace=m1; /修改新指令的页状态print(*m); /输出内存状态printf(n); count+; /缺页数加1else /页号在内存块中 for(j=0;jblockm-point=-1) /内存块不满pagpg.workplace=m-point;m-blockm-point=pg;m-point=(m-point+1)%BLOCK_N; /指向下一个内存块print(*m); /输出内存块状态else /内存块已满pagm-blockm-point.workplace=-1; /修改被替换页状态pagpg.workplace=m-point; /修改指令所在页状态m-blockm-point=pg; /新页存入内存块m-point=(m-point+1)%BLOCK_N; /指向下一个内存块print(*m); /输出内存状态count+; /缺页数加1 pagpg.ordid.state=1;count_order+; /指令计数器加1 4.3.3 LRU算法void lru(memory*m,int order_id,page pag,stack *s)int pg=belong_page(order_id); /计算页号int id=belong_orderId(order_id); /计算所在页的idint middle,i;if(pagpg.ordid.state=0) /指令未被执行if(pagpg.workplace=-1) /页不在内存块中 if(m-blockm-point=-1) /内存块未满m-blockm-point=pg; /页存入内存块pagpg.workplace=m-point; /修改页状态m-point=(m-point+1)%BLOCK_N; /指向下一个内存块s-sts-top=pg; /页压入栈s-top+; /栈顶指针加1print(*m); /输出内存状态else /内存已满pagpg.workplace=pags-sts-bottom.workplace; /修改页状态pags-sts-bottom.workplace=-1; /修改被置换页状态for(i=s-bottom;itop-1;i+) s-sti=s-sti+1; s-sti=pg; /栈顶存入新页m-blockpagpg.workplace=pg;print(*m); count+; /缺页数加1elsefor(i=s-bottom;itop;i+) if(s-sti=pg) middle=i; for(i=middle;itop-1;i+) s-sti=s-sti+1; /修改栈中页的顺序 s-sti=pg; pagpg.ordid.state=1;count_order+; /指令数加1实验关键代码如下：#define ORDER_N 10#define PAGE_N 32#define BLOCK_N 4int count; /缺页计数器int count_order; /指令计数器/定义指令结构体typedef struct order int id;int belong;int state;order;/定义页结构体typedef struct pageorder ordORDER_N;int workplace;page;定义内存结构体typedef struct memoryint blockBLOCK_N;int point;memory;/定义栈typedef struct stackint stBLOCK_N;int top;