操作系统—河海大学文天学院.docVIP

河海大学文天学院操作系统课程设计 姓 名: 胡 德 伟 班 级: 08级计算机科学与技术四班 指导老师: 邓老师 时 间: 2010.12.10实验一 进程调度一、实验目的通过一个简单的进程调度模拟程序的实现，加深对进程调度算法，进程切换的理解。 二、实验内容采用动态优先数的方法，编写一进程调度程序模拟程序。模拟程序只进行相应的调度模拟操作，不需要实际程序。 提示：(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名指针要求运行时间优先数状态其中，进程名作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。指针按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。要求运行时间假设进程需要运行的单位时间数。优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实习是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。(5) 进程运行一次后，若要求运行时间?0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。三进程调度处理过程当前进程是否用完计时中断处理中断总处理过程 计时中断 修改g_needReschedule为 true 否 是 g_needReschedule执行调度算法选择下一个进程 是 否 切换到下一个进程（此进程可以是原来的进程也可以是调度算法选择的进程） 四源程序分析 /*08计算机 学号:08031421*/操作系统,进程调度 用链表实现#include #include #include #include typedef struct pcb/进程的PCB块 char id;/进程名 char state;/进程的状态 int prior;/进程的优先级 int time;/进程的时间 pcb *next;/指向结构体的指针pcb,*plist;void insert(plist &head,pcb *p)/动态的根据条件，将链表插入到合适的位置中去 pcb *s,*r; if(head-next=NULL) /如果head 指针为空,则应该插入到对头 head-next=p; p-next=NULL; else s=head; r=s-next; while(r!=NULL&r-prior=p-prior)/根据s,r的位置去确定p的插入的位置 s=r; r=r-next; /找到新节点q的插入位置，循环后，q节点应该处于结点s,r之间,/如果r为空,则未尾结点 p-next=r; s-next=p; pcb *m; /cout*endl; coutendl; plist p; p=head;cout进程id 进程优先级 进程所需的运行时间 进程的状态next) p=p-next; cout id prior time state; coutnext; if(m-time=0) coutid进程已经运行完毕,要从链表中删除next=head-next-next; /将该结点从链表中删除 else head-next=m-next;/对头结点进行重新插入 insert(head,m); cout*endlendl; void create(plist &head,int n)/表示链表的长度是可变的 int i; pcb *p; for(i=0;in;i+) p=(plist)malloc(sizeof(pcb);cout请输入第i+1个进程名:(字符型)优先级:(整型) 运行时间:(整型) p-idp-priorp-time; p-state=r; /初始的转台全部为r insert(head,p); /将结点插入到合理的位置 void yunxing(plist &head)/对头结点进行的操作 pcb *m; cout开始进程调度; coutnext!=NULL) m=head-next; cout进程idprior=m-prior-1; m-time=m-time-1;if(m-time=0) /如果头结点已经运行完,将状态改为ehead-next-state=e;showjincheng(head);void main()clock_t start,finish;double shijian;int a; /进程数int b; /是否确认do /确认用户的选择,如果输入错误,可以重新输入do /控制进程的数目在合理的范围内 system(cls); coutendl*endl; coutendl姓名：胡德伟endl; coutendl学号：08031421endl; coutendl班级：08计算机四班endl;coutendl指导老师：邓老师endl; coutendl实验一：进程调度endl; coutendl*endl;couta; if(a=10|a=10) cout您所创建的进程数不能大于10，请重新输入endl;else cout您所创建的进程数不能为负数，请重新输入=10|a0); cout您所创建的进程数为aendl; cout确认请按1,重新输入进程数请按0b; if(b=0) system(cls); couta; while (b=0);cout尊敬的用户,您所创建的进程数为anext=NULL;create(head,a);/通过插入的方法构造链表coutendl;cout初始化创建的进程为:endl;start=clock();showjincheng(head); /显示链表的内容yunxing(head); /对进程进行操作的过程coutendlendl;cout所有的进程都已经运行结束了！endl;coutendl;finish=clock();shijian=double(finish-start)/CLOCKS_PER_SEC;cout程序的执行时间为shijianmsendl;coutendl;实验二 存储管理一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计 , 了解虚拟存储技术的特点 , 掌握请求页式存储管理的页面置换算法。二、实验内容通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成 : 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25% 的指令是均匀分布在后地址部分。具体的实施方法是 :在 0,319 的指令地址之间随机选取一起点 m;顺序执行一条指令;在前地址0,m+1中随机选取一条指令并执行 , 该指令的地址为 m; 顺序执行一条指令 , 其地址为 m+1;在后地址 m+2,319 中随机选取一条指令并执行 ;重复上述步骤 , 直到执行 320 次指令。(1) 将指令序列变换成为页地址流设：页面大小为 1K;用户内存容量为 4 页到 32 页 ;用户虚存容量为 32K 。在用户虚存中 , 按每 K 存放 10 条指令排列虚存地址 , 即 320 条指令在虚存中的存放方式为 :第 0 条 第 9 条指令为第 0 页 ( 对应虚存地址为 0,9);第 10 条 第 19 条指令为第 1 页 ( 对应虚存地址为 10,19 ) ;第 310 条 第 319 条指令为第 31 页 ( 对应虚存地址为 310,319) 。按以上方式 , 用户指令可组成 32 页。(2) 计算并输出下述各种算法在不同内存容量下的命中率。 先进先出的算法 (FIFO)； 最近最久未使用算法 (LRU);命中率 = 1 - 页面失效次数页地址流长度在本实验中 , 页地址流长度为 320, 页面失效次数为每次访问相应指令时 , 该指令所对应的页不在内存的次数。 三、虚拟内存实现原理图内存分配和回收机制 请求页机制交换机制地址映射机制缓存和刷新机制4 源程序分析 /*08计算机4班*/#include #include /队列#include /获取系统的时间using namespace std; typedef struct /页面的结构体信息int id; /页面的id号int staytime; /在内存中的停留的时间int unusualtime; /多久未被使用的时间Cpage;deque queue; /可以直接的使用队列的方法deque interPage; /内存中的页面deque exterPage; /外存中页面int xianzaiweizhi;int lacknum2 =0,0; /缺失的页面数int getRandNum(int range) /返回0,range)范围内的整数 return int(rand()%range); /根据srand函数得到随机数void InitDevice() /初始化运行队列 按照25% 50% 25%的标准生成 srand(int(time(NULL); /通过调用系统时间,产生随机数,并强制的转化成整型 int yehao = getRandNum(320); /随机选择第一条指令 queue.push_back(yehao); /将其插入队列 if(yehao 319) queue.push_back(yehao+1); /顺序执行下一条指令 while(queue.size() 320) /一直运行到队列中的个数等于320 yehao = getRandNum(yehao); /跳转到m1属于0,m-1 queue.push_back(yehao); /将m1插入队列 if(yehao 319) queue.push_back(yehao+1); /将m1+1插入队列 int temp = 320 - (yehao + 2); yehao = yehao+2+getRandNum(temp);/跳转到m2属于m+2,319 queue.push_back(yehao); /插入队列 if(yehao 320) /如果队列中的个数大于320,则把多余的队列进行出栈的操作 queue.pop_back();void InitMemoryQueue() /初始化页面 xianzaiweizhi = 0; exterPage.clear(); /对外存的页面进行清除 interPage.clear(); /对内存的页面进行清除 for(int i=0;i32;i+) Cpage temp; temp.id = i; temp.staytime = 0; /停留时间和未使用的时间都初始化未0 temp.unusualtime = 0; exterPage.push_back(temp); /将产生的页面进行入队的操作 int shuyunageyemian(int cmdId) /通过强制转换成整数的形式判断指令属于哪个页面 return int(cmdId/10);int yemianzhuantai(int PageId,bool sign) /分别在内外存中查找页面存在返回位置不存在返回-1if(sign) /在内存中进行查找 for(int i=0;iinterPage.size();i+) if(PageId = interPagei.id) return i; else /在外存中进行查找 for(int j=0;jexterPage.size();j+) if(PageId = exterPagej.id) return j; return -1; /如果内外存中都不在的话，返回-1 void directFlod(int PageId) /当内存空间还有剩余时直接调入 int status = yemianzhuantai(PageId,false); if(status = -1) return; interPage.push_back(exterPagestatus); /向内存插入exterPage.erase(exterPage.begin()+status); /从外存删除队列开始的位置加上偏移量int fifo() /FIFO算法中查找在内存中呆了最久的页面 int max = 0; for(unsigned i=1;iinterPagemax.staytime) /找到在内存中停留时间时间最长 max = i; return max; /返回停留时间最长的最大值int lru() /LRU算法中查找最久未使用的页面 int max = 0; for(int j=0;jinterPagemax.unusualtime) /找到最久未被使用的算法max = j;return max; /返回未被使用的最大值bool Manage(int count,int PageId) /当内存已经满了需要按照算法调度 int status = yemianzhuantai(PageId,false); /获取执行页面在外存中的索引地址 if(status = -1) return false; int targetStatus = 0; if(count = 0) targetStatus = fifo(); /根据fifo算法内存中需要交换的位置 else if(count = 1) targetStatus = lru(); /根据lru算法内存中需要交换的位置 interPagetargetStatus.staytime = 0; /将要交换的内存/页面的停留时间和最近多久未被使用的时间进行初始化为0 interPagetargetStatus.unusualtime = 0; swap(exterPagestatus,interPagetargetStatus); /内外层中的页面进行交换 return true;void run(int count) while(xianzaiweizhi 320) /如果现在的位置在合理的范围内 for(int i=0;iinterPage.size();i+) /对内存中的页面进行操作 interPagei.staytime+; /内存页面的停留时间+ interPagei.unusualtime+; /内存页面未使用的时间+ int PageId = shuyunageyemian(queuexianzaiweizhi+); int status = -1; /找到当前将要执行的指令的页面号,初始化为-1 if(status =yemianzhuantai(PageId,true) != -1) /如果查找的页面/在内存中,将最近最久时间标记为0,并结束本次的操作 interPagestatus.unusualtime = 0; continue; /如果不在内存中,所执行的操作 lacknumcount+; /缺失的页面数+1 if(interPage.size()4) /内存的队列未满,将该页面从外存中调入到内存中去 directFlod(PageId); /调入的操作 else Manage(count,PageId); /内存的队列已满,则根据算法进行调换 void main() coutendl*endl;coutendl姓名：胡德伟endl;coutendl学号：08031421endl;coutendl班级：08计算机四班endl;coutendl指导老师：邓老师endl;coutendl实验二:存储管理endl;coutendl*endl;InitDevice();int i; /循环的控制int b; /换行的控制int flag; /进行何种操作的控制b=0;coutendl产生的随机数为:endl;for(i=0;i=319;i+) coutqueuei ; b+; if(b%12=0) coutendl; coutendl;int count = 0;while(count2) InitMemoryQueue(); run(count); count+;do /由用户选择输出的结果cout*请输入您要进行的操作*endl;cout*1.先进先出的算法调度*endl;cout*2.最近最久未使用的算法调度*flag;if(flag=1) /先进先出的算法调度 cout先进先出的算法调度的缺页率为:endl; cout(double)lacknum0/320*100%endl;else if(flag=2) /最近最久的算法调度 cout最近最久未使用的算法调度的缺页率为:endl; cout(double)lacknum1/320*100%endl;cout是否继续(1.继续 0.退出)flag; while (flag=1); /满足此条件,重新做里面的内容system(PAUSE); 实验三 文件系统设计一、实验目的通过一个简单多用户文件系统的设计 , 加深理解文件系统的内部功能及内部实现。二、实验内容为 Linux 系统设计一个简单的二级文件系统。要求做到以下几点 : (1) 可以实现下列几条命令 ( 至少 4 条) ;login 用户登录dir 列文件目录create 创建文件delete 删除文件open 打开文件close 关闭文件read 读文件write 写文件(2) 列目录时要列出文件名、物理地址、保护码和文件长度 ;(3) 源文件可以进行读写保护。三程序流程图开始选择操作？ 删除文件打开文件创建文件 否结束注销写文件读文件 是4 部分源程序1. Read函数函数功能：从系统文件上读取文件数据到文件缓冲区函数参数：文件指针，缓冲区地址，需要读出文件的字节数。函数返回值：若读取成功，返回实际读取的文件数。 Static int Reand( struct File*file, void*buf ,ulong_t numBytes) Struct PFAT_file*pfatfile=(struct PFAT_file*) file-fsData; Struct PFAT_Instance*instance=(struct PAFT_Instance*) File-mountpoint-fsData; Ulong_t start=file-filepos; Ulong_t end=file-filepos+numBytes; Ulong_t startblock,endblock,curblock; Ulong_t i;/*若读的文件长度大于INT_MAX，则返回无效*/If (numBytesINT_MAX)Return EINVALID;/*确保读取的文件的长度是有效的 ，若读取的位置超出文件范围，则无效*/If (start=file-endpos|endfile-endpos|endfilepos,numBytes,file-endpos);Return EINVALID;/*检测需要读取的数据是否都在文件缓冲区中*/Startblock=(start % SECTOR_SIZE)/SECTOR_SIZE;Endblock=round_up_block(end)/SECTOR_SIZE;/*遍历文件系统，查取需要读取的文件块*/Curlock=pfatfile-entry-firstblock;For(i=0;i=stratblock)Int rc=0；/*对文件进行互斥锁，确保每次仅有一个进程对文件进行读取*/Mutex_lock(&pfatfile-lock);If(!Is_Bit_set(pfatfile-validlockSet,i)/*读一个磁盘快到文件数据缓冲区*/Dubeg(reading file bloock %lu (devic block%lu)n,i,curblock);Rc=block_read(file-mountpoint-dev,curblock,pfatfile-fileDatecache+i*SECTOR_SIZE);If(rc=0)/*置该块的已读标记*/Set_bit(pfatfile-validblockset,i);Mutex_unlock(&pfatfile-lock);If (rc!=0)Return rc;/*继续读下一块数据*/Ulong_t nextblock=instance-fatcurblock;Curblock=nextblock;/*将缓冲区数据复制到调用读函数的进程缓冲区*/Memcpy(buf,pfatfile-filedatacache+start,numBytes);Debug(read satisfiled!n);Reurn numbytes;2. Write()函数函数功能：将文件缓冲区的数据些入文件系统函数参数：文件指针，缓冲区地址，写入文件的字节数。函数返回值:错误标志EACCESS。Static int write(struct file *file,void*buf,ulong_t numBytes)/*因为文件系统是只读的，所以不允许写入，直接返回标志*/Return EACCESS;3. OPEN()函数函数功能：打开文件系统文件。函数参数：文件系统加载点指针，路径名，打开方式，文件指针。Statitc int open(struct mount_point*mountpoint,const char*path,int mode,struct file *pfile) Int rc=0;Struct PFAT_instance *instance=(struct PFAT_instance*)Mountpoint-fsdata;Directoryentry*entry;Struct PAFT_file *pfatfile=0;Stru