第一篇：《操作系统原理》算法总结
《操作系统原理》算法总结
一、进程(作业)调度算法
先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。
短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。
时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。
优先数调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。
响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。
多级队列调度算法 基本概念：
作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)
作业平均周转时间(T)＝周转时间/作业个数
作业带权周转时间（Wi）＝周转时间/运行时间
响应比＝（等待时间＋运行时间）/运行时间
二、存储器连续分配方式中分区分配算法
首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。
循环首次适应算法：每次分配均从上次分配的位置之后开始查找。
最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。
三、页面置换算法
最佳置换算法（OPT)：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。
先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。
最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。
最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。
四、磁盘调度
先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置
最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题
扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。
循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。
第二篇：操作系统实验报告(clock算法)
实验四 页面置换算法
一、实验目的
本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。
二、实验要求
基本要求：描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。
1）初始化：输入作业可占用的总页框数，初始化置空。
2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用； 3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。
4）显示当前分配淘汰序列：显示淘汰的页号序列。
描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。
三、实验内容
1)基本原理
时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面，如图所示。
当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。2)算法流程设计
主函数流程: STEP1:输入分配的页框数，页面访问次数和要访问的页面号序列 STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值yehao和访问位值a。开始时页号均为-1，访问位为0.STEP3：测试数据。具体算法是依要访问的页面号，调用find()函数查找是否已经存在于内存中。若存在，则修改其访问位为1.若不存在，触发缺页中断，调用tihuan()函数。最后，打印当前内存状态。如此循环直至测试串都访问完毕。3)主要函数实现
a)Makenode(double)函数：用于初始化一个节点。
b)Find（double）函数：依据输入的页号，查询内存中是否已存在此页面。若存在返回值1，不存在返回值0.c)Tihuan（double）函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指针扫过的页面访问位置0，新加入的页面访问位置1。替换后指针下移。
d)Print_state()函数：打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位置。
4)测试数据
输入：
输入分配的页框数 3 输入页面访问次数 15 输入要访问的页面号序列 3 4 2 6 4 3 7 4 3 6 3 4 8 4 6 输出（仅最后一项）：
5)结果分析
以下是clock算法对应输入页面号序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6的分析表
四、实验总结
1.加深对clock算法的理解。通过与其他算法的比较，我也了解了他们的异同之处。Clock算法其实是一种改进的第二次机会算法，它通过设置访问位，找到最早最不常访问的页面，即标号为0的页面。之所以叫clock算法，依我理解是将内存中的排列顺序附上时间的概念，clock指针扫过的页面要将他们1置0就是基于这个思想，因为他们都是没被访问的，且在时钟上的排列按照访问时间顺序。这样就保证了每次替换的都是最早进来的且不最常访问的页面。
2.在时钟内存结构的代码实现上，我使用了自建的单循环链表，对其进行顺序地遍历即可实现时钟指针的移动。另外通过全局变量node *r（时钟）node *start（开始页面项）node *r_prev（时钟指针的前驱）的设置，方便了有关算法的实现。
3.此算法较为简单，还有一种改进版的clock算法，增加了一个修改位，表示页框是否被修改过。这样的设计更加符合现在操作系统的调度原则。
参考文献
[1]（美）Stanley B.Lippman 等 著 李师贤 等 译.C++ Primer中文版（第4版）.人民邮电出版社, 2006-03-01 [2] 蒋爱军，李师贤，梅晓勇 著.C++ Primer习题解答（第4版）.人民邮电出版社, 2007-02-01 [3] 塔嫩鲍姆（Tanenbaum.A.S），陈向群，马洪兵 著.现代操作系统（原书第3版）.机械工业出版社, 2009-07-01 [4] 张尧学，史美林，张高.计算机操作系统教程.清华大学出版社, 2006-10-01 [5] 王晓东 著.数据结构（STL框架）.清华大学出版社, 2009-09-01
第三篇：操作系统银行家算法实验报告
实验四
死锁
一、实验目的
当系统的总资源数m小于或等于所有进程对对资源的最大需求时，就可能产生 死锁。死锁会引起计算机系统的瘫痪。银行家算法是在实现资源分配时避免死锁的一个著名算法，该算法是在能确保系统处于安全状态时才把资源分配给申请者。通过本实验使学生能进一步理解死锁的概念，并能选择一个算法来避免死锁。
二、实验题目
系统中有m个同类资源被n个进程共享，每个进程对资源的最大需求数分别为S1, S2,…,Sn，且 Max(Si)<=m,(i=1,2,…n)。进程可以动态地申请资源和释放资源。编写一个程序，现银行家算法，当系统将资源分配给某一进程而不会死锁时，就分配之。否则，推迟分配，并显示适当的信息。
三、数据结构
主要数据结构:
Struct aa { void Print();//用于打印输出表格的函数 void Input();//用于输入的函数
void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 }；
四、银行家算法的流程图 开始初始化资源类数c=3，进程数t=5初始化Available[c]，Max[t][c]，Allocation[t][c]，Need[t][c]，Request[c]输入进程数iInt f=0f 五、源代码 #include void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 //定义初始化数组 int Available[c], Max[t][c], Allocation[t][c], Need[t][c], Request[c]; int in;//用户选择的进程号 int main(int argc, char *argv[]){ int i;char ch='Y';cout<<“初始化数据如下：”< cout<<“试分配完成!”< cout<<“需要继续实验吗?（y-继续 n终止）”;} else if(ch=='N'||ch=='n'){ cout<<“感谢您的使用，祝您愉快!”< void Print(){ int i,j;cout<<“ 进程个数 ： ”< void Input(){ for(int j=0;j { for(int m=0;m void tryfenpei(int i){ for(int f=0;f //安全检测函数 void checksafe(int s){ int Work, flag, temp[t], i,j,l=0,k=0;bool Finish[t];for(i=0;i } if(l==5)//一共有三类资源A B C，一条进程下面的安全性检测只检测了A类。如果A类通过了，那么还要判断B类，C类。否则不用 { for(i=0;i } i=s;//s传递进来赋给i，s是用户输入的进程号（有主函数里的in传递进来）while(i if(Finish[i]==false&&Need[i][j]<=Work){ Work=Work+Allocation[i][j];Finish[i]=true;temp[k]=i;//cout<<“temp=”< 六、执行结果： 七、实验总结 通过本次实验了解到用银行家算法来预防死锁是可靠的，但也是非常保守的，因为它限制了进程对资源的存取，从而降低了进程的并发运行程度。死锁检测并不限制进程对资源的申请，只要有，就分配，但这也可能造成死锁。但由于死锁并不是经常发生的，故大大提高了系统运行的效率。 总之，通过本实验，使我进一步加深理解和掌握银行家算法。 《计算机操作系统》 学号：班级：软技姓名：张靖伟 课 程 设 计 报 告 4班 1367003270 目录 实验：进程调度算法——时间片轮转算法 2 实验：银行家算法3 实验：分区分配算法——4 实验：页面置换算法——5 实验：磁盘调度算法—— BF和FF FIFO和LRU SCAN和SSTF 1实验：进程调度算法——时间片轮转算法 1.实验设计说明 用时间片轮转算法模拟单处理机调度。 （1）建立一个进程控制块PCB来代表。PCB包括：进程名、到达时间、运行时间和进程后的状态。 进程状态分为就绪（R）和删除（C）。 （2）为每个进程任意确定一个要求运行时间和到达时间。 （3）按照进程到达的先后顺序排成一个队列。再设一个指针指向队首和队尾。（4）执行处理机调度时，开始选择对首的第一个进程运行。（5）执行： a)输出当前运行进程的名字； b)运行时间减去时间片的大小。 （6）进程执行一次后，若该进程的剩余运行时间为零，则删除队首，并将该进程的状态置为C；若不为空，则将向后找位置插入。继续在运行队首的进程。 （7）若进程队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。 2.实验代码 /*****************时间片轮转调度算法*******************/ #include char pname[N];int runtime;/*进程名*/ /*服务时间*/ int arrivetime;/*到达时间*/ char state;/*进程状态*/ struct pcb*next;/*连接指针*/ }PCB;typedef struct back_team/*后备队列定义*/ { PCB*first,*tail;}BACK_TEAM;typedef struct pre_team/*就绪队列定义*/ { PCB*first,*tail;}PRE_TEAM;PCB*creat()/*创建PCB*/ { char s[N];printf(“请输入进程名：n”);scanf(“%s”,s);printf(“请输入进程服务时间(/秒)：n”);int t;scanf(“%d”,&t);PCB*p=(PCB*)malloc(sizeof(PCB));strcpy(p->pname,s);p->runtime=t;printf(“请输入进程到达时间(/秒)：n”);scanf(“%d”,&t);p->arrivetime=t;p->state='R';p->next=NULL;getchar();return p;} PCB*copy(PCB*p)/*复制一个进程*/ { } PCB*getnext(PCB*p,BACK_TEAM*head)/*得到队列中下一个进程*/ { } void del(BACK_TEAM*head,PRE_TEAM*S)/*释放申请的空间*/ { PCB*p=head->first->next;while(p){ free(head->first);head->first=p;PCB*s=head->first;if(!p)return NULL;if(!p)return NULL;PCB*s=(PCB*)malloc(sizeof(PCB));strcpy(s->pname,p->pname);s->next=NULL;s->arrivetime=p->arrivetime;s->runtime=p->runtime;s->state=p->state;return s;while(strcmp(s->pname,p->pname))s=s->next;return s->next; } } p=p->next;head->first=head->tail=NULL;free(head);free(S);BACK_TEAM*creatbt(BACK_TEAM*head)/*创建后备队列*/ { } bool recognize(PRE_TEAM*s1)/*判断运行是否结束*/ { if(!s1||!s1->first)return false;PCB*p=creat();if(!head->first)else head->tail->next=p;head->first=p;head->tail=p;return head;if(s1->first==s1->tail) if(s1->first->state!='C')else return false;return true;PCB*test=s1->first;while(test!=s1->tail&&(test->state!='C'))test=test->next;if(test==s1->tail) } return true;else return false;PCB*run(PRE_TEAM*s)/*在CPU中运行*/ { if(!s->first){ } printf(“%dt%st”,time,s->first);s->first->runtime--;time++;if(s->first->runtime<=0){ } PCB*p=s->first;s->first->state='C';printf(“%cn”,s->first->state);s->first=p->next;free(p);if(!s->first){ } goto next;s->tail=NULL;spe=false;return NULL;spe=false;return NULL;printf(“%cn”,s->first->state);next:PCB*head=s->first; } int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*创建就绪队列*/ { int i=0;if(!head2->first) if(HEAD){ } if(c){ } head2->first=head2->tail=HEAD;return 1;head2->first=c;c->next=HEAD;head2->tail=HEAD;return 1;s->first=head->next;if(!s->first){ } head->next=NULL;return head;s->tail=NULL;spe=true;if(head2->first==head2->tail){ } else { } if(*test){ } if(c){ } head2->tail->next=c;head2->tail=c;if(head2->first->arrivetime!=time)for(i=0;i } if(c->arrivetime!=time){ } head2->tail->next=c;head2->tail=c;time++;return 1;if(HEAD){ head2->tail->next=HEAD; } } head2->tail=HEAD;return 1;int main(void){ BACK_TEAM*head1=(BACK_TEAM*)malloc(sizeof(BACK_TEAM));head1->first=head1->tail=NULL;PRE_TEAM *head2=(PRE_TEAM*)malloc(sizeof(PRE_TEAM));head2->first=head2->tail=NULL;char ask;int num=0;bool test=true;do{ printf(“要创建进程吗(y/n):”);if((ask=getchar())=='y'||ask=='Y'){ } else if(ask=='n'||ask=='N')else return 1;break;head1=creatbt(head1);num++;}while(1);PCB*p=copy(head1->first);PCB*HEAD=NULL;head2->first=head2->tail=copy(head1->first);printf(“时刻t进程名t状态n”); } while(spe||recognize(head2)){ } del(head1,head2);return 1;CREAT(HEAD,head2,&test,p);HEAD=run(head2);p=copy(getnext(p,head1));3.实验结果 和不马上运行: 当有两个进程的时候 当有多个进程的时候： 4.实验结果分析 RR算法：每次调度时，把CPU分配给队首进程，并且令其执行一个时间片，时间片的大小从几个ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便依据此信号来停止该进程的执行；并且把它送往就绪队列的队尾；然后，再把处理剂分配给就绪队列中的新队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内相应所有用户的请求.2实验：银行家算法 1.实验设计说明 1.该算法通过建立几个简单的二维数组Available,Max,Allocation,Need简单的模拟银行家算法和安全性算法，每个二维数组默认[][0]为A资源，[][1]为B资源，[][2]为C资源,默认有5个进程 2.程序首先要输入各个进程的三种资源的情况，包括每个进程最大的需求量，已经分配的资源量和现在还需要的资源量，以及系统现在剩余的资源量。3.程序会判断输入的信息是否在程序的规定范围内，正确才运行。 4．在执行安全算法开始时，Work∶=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true 5.从进程集合中找到一个能满足下述条件的进程： Finish［i］=false;并且 Need［i,j］≤Work［j］； 若找到，执行6，否则，执行7。 6.当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;然后继续执行5。 7.如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 2.实验代码 #include return false;printf(“p%d可以运行n”,p);Work[0]+=Allocation[p][0];Work[1]+=Allocation[p][1];Work[2]+=Allocation[p][2];Finish[p]=1;while(num<=25){ if(!Finish[i]&&(Need[i][0]<=Work[0])&&(Need[i][1]<=Work[1])&&(Need[i][2]<=Work[2])) { printf(“p%d可以运行n”,i); Work[0]+=Allocation[i][0]; Work[1]+=Allocation[i][1]; Work[2]+=Allocation[i][2]; Finish[i]=1; } num++; i=(i+1)%5; if(i==p) i++;} for(m=0;m<5;m++) if(Finish[m]==0) break;if(m==5) return true;else { printf(“系统处于不安全状态!n”); return false;} } void Banker(int p,int i,int j,int k){ int able[3]={Available[0],Available[1],Available[2]};int need[3]={Need[p][0],Need[p][1],Need[p][2]};int allocation[3]={Allocation[p][0],Allocation[p][1],Allocation[p][2]};if(i<=Need[p][0]&&j<=Need[p][1]&&k<=Need[p][2]) if(i<=Available[0]&&j<=Available[1]&&k<=Available[2]) { Available[0]-=i; Available[1]-=j; Available[2]-=k; Allocation[p][0]+=i; Allocation[p][1]+=j; Allocation[p][2]+=k; Need[p][0]-=i; Need[p][1]-=j; Need[p][2]-=k; if(!Safe(p)) { Available[0]=able[0],Available[1]=able[1],Available[2]=able[2]; Need[p][0]=need[0],Need[p][1]=need[1],Need[p][2]=need[2]; Allocation[p][0]=allocation[0],Allocation[p][1]=allocation[1],Allocation[p][2]=allocation[2]; printf(“系统可能发生死锁!n”); } } else printf(“等待!系统资源不足!n”);else printf(“错误!申请的资源错误!n”);} int main(void){ int i,j,k=0,p;printf(“请输入进程的三种资源的情况max{a,b,c} allocation{a,b,c} need{a,b,c}:n”);for(i=0;i<5;i++){ for(j=0;j<3;j++) scanf(“%d”,&Max[i][j]); for(j=0;j<3;j++) scanf(“%d”,&Allocation[i][j]); for(j=0;j<3;j++) scanf(“%d”,&Need[i][j]);} printf(“请输入Available{a,b,c}情况:”);for(i=0;i<3;i++) scanf(“%d”,&Available[i]);printf(“MaxtAllotNeedtAvain”);for(i=0;i<5;i++){ for(j=0;j<3;j++) printf(“%d ”,Max[i][j]); printf(“t”); for(j=0;j<3;j++) printf(“%d ”,Allocation[i][j]); printf(“t”); for(j=0;j<3;j++) printf(“%d ”,Need[i][j]); printf(“t”); if(k!=4) printf(“n”); k++;} for(i=0;i<3;i++)printf(“%d ”,Available[i]);printf(“n请输入要申请的进程和资源<0~4>:”);scanf(“%d %d %d %d”,&p,&i,&j,&k);if(p>=0&&p<=4)Banker(p,i,j,k);else printf(“没有此进程!”);return 1;} 3.实验结果 4.实验结果分析 这个实验只是简单的演示了进程申请资源之后的进程运行的其中一个运行序列，因为这个算法课本上已经有详细的解说，所以这个程序并没有把算法的过程展现出来，只展现了进程的运行序列结果，另外，如果申请错误的话程序会有不同的结果 有时会发生死锁 实验：分区分配算法——BF和FF 1.实验设计说明 1.这个算法模拟的是对内存空间的管理，这个程序用了一个简单的二维数组模拟分区表。2.程序首先要输入固定的五个分区的大小和始址，其次要输入作业的大小和实现的算法，由于这个程序把FF和BF放到一个程序中，便于比较两个算法。 首次适应算法FF(First Fit)把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表 最佳适应算法BF（Best Fit） 首先把分区表按空间大小从小到大排序。然后把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表 2.实验代码 #include int i,j;for(j=0;j<3;j++) for(i=0;i<5;i++) if(ta[i][1]>=job[j]){ } ta[i][1]-=job[j];ta[i][2]+=job[j];break;if(i==5)printf(“内存不足!请等待!n”); } printf(“空闲区t大小t始址n”);for(j=0;j<5;j++){ } for(i=0;i<3;i++)printf(“%dt”,ta[j][i]);printf(“n”);void BestFit(int job[3]){ int j1,temp1,temp2,temp3,i,j;for(j1=0;j1<3;j1++){ for(i=0;i<5;i++) for(j=0;j<4;j++) if(table[j][1]>table[j+1][1]){ temp1=table[j][0];temp2=table[j][1];temp3=table[j][2]; table[j][0]=table[j+1][0];table[j][1]=table[j+1][1];table[j][2]=table[j+1][2]; } table[j+1][0]=temp1;table[j+1][1]=temp2;table[j+1][2]=temp3; } if(i==5)printf(“内存不足!请等待!n”);printf(“空闲区t大小t始址n”);for(j=0;j<5;j++){ } for(i=0;i<3;i++)printf(“%dt”,table[j][i]); } for(i=0;i<5;i++) if(table[i][1]>=job[j1]){ } table[i][1]-=job[j1];table[i][2]+=job[j1];break;printf(“n”);void main(){ int table1[5][3],job[3],j,i;printf(“请输入5个空分区的大小和始址：”);for(i=0;i<5;i++){ } for(j=0;j<5;j++){ } printf(“请输入3个要运行作业的大小：”);for(i=0;i<3;i++)scanf(“%d”,&job[i]);for(i=0;i<3;i++)printf(“%dt”,table[j][i]);table[i][0]=i+1;table1[i][0]=i+1;for(j=1;j<3;j++){ } scanf(“%d”,&table[i][j]);table1[i][j]=table[i][j];printf(“n”);printf(“请输入要实现的算法1(FF)2(BF):”); } char c;scanf(“%d”,&i);getchar();if(i==1){ } else if(i==2){ } BestFit(job);printf(“还要实现FF吗(y/n)”);if((c=getchar())=='y')FirstFit(job,table1);FirstFit(job,table1);printf(“还要实现BF吗(y/n)”);if((c=getchar())=='y')BestFit(job);3.实验结果 4.实验结果分析 首先输入分区表的分区情况，然后输入运行作业的大小，选择要实现的算法。第一个作业是96，所以找到第四个分区，第四个分区变为122，316，接着到第二个作业20，然后把第一个分区分给第二个作业，则第一个分区信息变为122，316，到第三个作业时，由于内存表中没有比第三个请求的分区还大的分区，所以会提示内存不足； 然后到BF算法，因为是按空间大小排序的，所以第一个作业96被分配给了已经排好序的内存为96的第五个分区，第二个作业被分配给大小为36的分区，第三个作业被分配给内存大小为218的分区，然后又对剩余空间再次排队，用来给下一批作业分配。实验：页面置换算法——FIFO和LRU 1实验设计说明 程序设置了两个结构体,freeBlock和jobQueue,其中freeBlock代表物理块,初次创建物理块时,物理块的计时器time=0,还有代表作业的index=-1;物理块有添加和删除的功能，每一次添加或删除都要初始化物理块。并且可以重复添加和删除，这样可以很好的测试算法的性能。2.算法设计的思想是：进入物理块时间越长的则物理块的计时器数值越大，如果物理块中有要访问的页面，则那个含页面的物理块的计数器变成1；并且物理块要满才会发生置换，于是设置了物理块计数器Time； 2.实验代码 #include jobQueue*job=(jobQueue*)malloc(sizeof(jobQueue));job->index=num;job->next=NULL;if(!head){ jobQueue*j=head;while(j->next)j=j->next;j->next=job;head=job;else } } return head;freeBlock*creat(freeBlock*head){ } freeBlock*inse(freeBlock*head){ } freeBlock*dele(freeBlock*head){ freeBlock*test=head;while(test){ } freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=head;head=free;return head;test->index=-1;test->time=0;test=test->next;freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=NULL;if(head)free->next=head;head=free;return head; } freeBlock*test=head;while(test){ } freeBlock*f=head;head=f->next;free(f);return head;test->index=-1;test->time=0;test=test->next;bool check(freeBlock*free,int j){ } void LRU(freeBlock*free,jobQueue*job){ int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ freeBlock*f=free;while(f){ } return false;if(f->index==j)return true;f=f->next; } size++;ftest=ftest->next;printf(“LRU置换页面为：”);while(jtest){ ftest=free;while(ftest){ } ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ if(ftest->index==jtest->index){ } ftest->time++;if(Time } } } } time=0;Time=0;break;if(ftest->time==Time){ } ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void FIFU(freeBlock*free,jobQueue*job){ int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ } size++;ftest=ftest->next; printf(“FIFU置换页面为：”);while(jtest){ ftest=free;while(ftest){ } ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ } if(ftest->time==Time)time=0;Time=0;break;if(ftest->index==-1){ } ftest->time++;if(Time } } } { } ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void main(){ int num,ch,p;freeBlock*block=NULL;jobQueue*job=NULL;printf(“请输入物理块数目：”);scanf(“%d”,&p);for(int i=0;i } job=creat(job,ch);FIFU(block,job);LRU(block,job);while(true){ printf(“增加物理块（1）减少物理块（2）,否则按任意键scanf(”%d“,&num);if(num==1){ } else if(num==2){ printf(”要减少几块：“);scanf(”%d“,&ch);if(ch>=p){ } for(i=0;i } } } FIFU(block,job);LRU(block,job);else ；break;3.实验结果 4.实验结果分析 程序开始要输入物理块数目和作业个数,然后再输入作业.在测试后可以随意添加或删除物理块来测试算法的性能。实验：磁盘调度算法——SCAN和SSTF 1.实验设计说明 算法定义了一个双向链表，利用双向链表可以很好的进行方向的转换，且双向链表的中有代表磁盘号的标识符index；两个算法均采用访问完一个磁盘序列时删除该序列，其中scan算法实现时有点麻烦，首先要找到当前磁盘号序列的Max最大值和最小值Min及指向他们的指针pmax，pmin，另外还要找到当前磁头的相邻的两个访问序列信息psmax，psmin；还有一个重要的标志，那就是访问的方向test；当遇到最大值或最小值时，便会反置test的值，也就是访问的方向 2.实验代码 #include printf(“请输入磁道队列以-1结束！n”);int ch;memory*head=NULL,*tail,*p;scanf(“%d”,&ch);while(ch!=-1){ p=(memory*)malloc(sizeof(memory));p->index=ch;p->left=p->right=NULL; } } if(!head)head=p;else { } tail=p;scanf(“%d”,&ch);tail->right=p;p->left=tail;return head;void SSTF(memory*head,int index){ int index1=index,num;memory*p1=head,*p,*p2=NULL;while(true){ num=abs(p1->index-index1);p=p1;while(p){ } if((abs(p->index-index1))<=num){ } p=p->right;num=abs(p->index-index1);if(p!=p1)p2=p;p=p1->right;if(p2){ } else { printf(“%d ”,p1->index);index1=p2->index;printf(“%d ”,p2->index);p2->left->right=p2->right;if(p2->right)p2->right->left=p2->left;free(p2);p2=NULL; } } } index1=p1->index;if(!p){ } else { } p=p1;p1=p1->right;free(p);continue;free(p1);break;void SCAN(memory*head,int index){ int index1=index,num,test,max=0,min=199,Max,Min;printf(“请输入磁头查询方向<0正向><1负向>!n”);scanf(“%d”,&test);memory*p1=head,*p,*p2=NULL,*pmax,*pmin,*psmax=NULL,*psmin=NULL; while(p1){ } p1=head;while(p1){ if(!test){ if(!test){ } else { } p1=p1->right;pmin=p1;if(p1->index<=min)Min=min=p1->index;pmax=p1;if(p1->index>=max)Max=max=p1->index; } } pmin=p1;if(p1->index<=min)Min=min=p1->index; else { } p1=p1->right;pmax=p1;if(p1->index>=max)Max=max=p1->index;p1=head;while(true){ num=abs(p1->index-index1);p=p1;while(p){ if(!test){ if(p->index>=index1&&p->index<=max) } } if((abs(p->index-index1))<=num){ } psmin=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;else { } p=p->right;if(p->index<=index1&&p->index>=min) if(abs(p->index-index1)<=num){ } psmax=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;if(p2) { if(!test){ } else { index1=psmax->index;p=psmax;if(index1==Min){ } test=0;Max=Min=-1;p1=pmin;index1=psmin->index;p=psmin;if(index1==Max){ } test=1;Min=Max=-1;p1=pmax; } printf(“%d ”,index1);if(!test){ } else { if(psmax)if(psmin){ } else { } psmax->right->left=psmax->left;if(psmax->left) psmax->left->right=psmax->right;psmin->left->right=psmin->right;if(psmin->right) psmin->right->left=psmin->left;free(psmin);free(psmax); } } { } else { } psmin->right->left=psmin->left;if(psmin->left) psmin->left->right=psmin->right;psmax->left->right=psmax->right;if(psmax->right) psmax->right->left=psmax->left;free(psmax);free(psmin);else { if(!test){ if(p1->index==Max){ test=1; } } Min=Max=-1;else { } if(psmax){ } else { } printf(“%d ”,index1);index1=psmin->index;p=psmin;index1=psmax->index;p=psmax;if(p1->index==Min){ } test=0;Max=Min=-1; } } } if(p->left&&!p->right){ } else if(p->right&&!p->left){ } else if(!p->right&&!p->left){ } free(p);free(p);break;p1=p->right;p1->left=NULL;p1=p->left;p1->right=NULL;p2=psmax=psmin=NULL;void main(){ int p,t;memory*head=creat();printf(“请输入磁头当前的位置(0-199)”);scanf(“%d”,&p);printf(“要进行的算法：<0:SCAN><1:SSTF>”);scanf(“%d”,&t);if(!t)SCAN(head,p);else SSTF(head,p);} 3.实验结果 4.实验结果分析 输入要访问的磁盘号，然后选择要实现的算法就可以看到结果，当选0（正向）的时候由于当前的磁头在143处，所以要访问的磁盘号就必须大于143，当最大的磁盘号访问完时，就转向小于143的磁盘开始由大向小访问，选1的话则相反。最短寻道时间算法是从整个队列中选择距离磁头最近的访问，算法的实现运用了绝对值的概念 1.死锁：各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。 2.设备驱动程序：驱动物理设备和DMA控制器或I/O控制器等直接进行I/O操作的子程序的集合。负责设置相应设备的有关寄存器的值，启动设备进行I/O操作，指定操作的类型和数据流向等。 3.SPOOLING系统：外围设备同时联机操作。在SPOOLING系统中多台外围设备通过 通道或DMA器件和主机与外存连接起来。作业的输入输出过程由主机中的操作系统控制。 4.覆盖技术：一个程序并不需要一开始就把他的全部指令和数据都装入内存后在执 行。在单CPU系统中，每一时刻事实上只能执行一条指令。因此可以把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被放在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。 5.交换技术：先将内存某部分的程序或数据写入外存交换区，再从外存交换区调入指 定 的程序或数据到内存中来，并让其执行的一种内存扩充技术。 6.进程：并发执行的程序在执行过程中分配和管理资源的基本单位。 7.通道：一个独立于CPU的专管输入输出控制的处理机，他控制设备与内存直接进 行数据交换。他有自己的通道指令，这些通道指令受CPU启动，并在操作结束后向CPU发中断信号。 8.线程：他是进程的一部分，有时被成为轻权进程或轻量级进程，也是CPU调度的基本单位。 9.临界区：不允许多个并发进程交叉执行的一段程序。 10.临界资源：临界区占用的资源 11.块设备：将信息存储在固定大小的块中，每个块都有自己的地址。 12.字设备：在I/O传输过程中以字符为单位进行传输的设备。 13.作业：在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。 14.文件系统：操作系统中与管理文件有关的软件和数据称为文件系统。他负责为用户 建立撤销读写修改和复制文件，还负责完成对文件的按名存取和进行存取控制。 15.互斥：不允许两个以上的共享该资源的并发进程同时进入临界区 16.同步：异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程。 17.抖动：由于内存页面置换算法选择不当，致使刚被调出内存的页又要马上被调回内 存，调回内存不久又马上被调出内存，如此反复的局面。 18.虚拟存储器：将进程中的目标代码、数据等的虚拟地址组成的虚拟空间成为虚拟存 储器。 19.中断：是指计算机在执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，带处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。 20.局部性原理：程序总是趋向于使用最近使用过的数据和指令，也就是程序执行时所 访问的存储器地址不是随机的，而是相对的簇集，这种簇集包含数据和指令两部分。程序局部性包括时间局部性和空间局部性。程序的时间局部性：程序即将用到的信息可能就事目前正在使用的信息。程序的空间局部性：程序即将用到的信息可能与 21.22.23.24.25.26.27.28.29.30.31.目前正在使用的信息在空间上相邻或临近。进程控制块（Process Control Block）：PCB是 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。文件控制块（FCB）：文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。资源分配图：用于分析死锁的一种图，由资源结点、进程结点、分配边和请求边组成。竞态：多个并发进程共享数据的结果错误，其值不可确定，取决这些进程执行的相对速度。i-节点：UNIX型文件系统中，一种用于存储文件控制信息的数据结构，每个文件对应拥有一个这样的数据块，组织并存储于外存特定的一些盘块中。内核：实现操作系统的最基本功能、常驻内容并要求CPU在核心态方式下运行的代码和相关数据结构。信号量：操作系统内容定义和管理的一种特殊数据结构，提供了初始化、增值和减值等操作供进程调用，以实现进程互斥或同步。逻辑地址：程序设计员在程序中使用的地址。管程：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据 管道：是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据，也能使进程同步执行操作。驱动调度：系统运行时，同时会有很多个访问辅助储存器的进程请求输入输 出操作，操作系统必须采取一种调度策略，使其能按最佳的次序执行各访问请求。第四篇：操作系统课程设计六种算法
第五篇：操作系统原理术语解析总结
点击咨询 