采用最佳适应算法可变分区

第四章复习题一、单项选择题1. 在可变分区存储管理中，若采用最先适应分配算法宜将空闲区按（B）次序登记在空闲区表中。

A. 地址递减B. 地址递增C. 长度递减D. 长度递增2. 采用固定分区存储管理的计算机系统中（D）的做法是错误的。

A. 为作业分配的分区不能小于作业长度B. 可同时在多个分区中各装一个作业C. 不允许多个作业同时存放在一个分区中D. 一个分区中可同时装入多个作业3. 不适宜采用虚拟存储管理技术的存储管理方式是（D）。

A. 页式B. 段式C. 段页式D. 可变分区4. 在多道程序设计系统中，采用了页式存储管理。

如果允许并行工作的道数为n(n>1)，则系统中同时建立的页表数一定为（C）。

A. 1B. nC. <=nD. n+15. 在单用户连续存储管理中，可供用户使用的主存区域起始地址存放在（B）。

A. 基址寄存器B. 界限寄存器C. 限长寄存器D. 相联寄存器6. 重定位的含义是（C）。

A. 把主存中的一个程序从一个区域重新定位到另一个区域B. 把绝对地址转换成逻辑地址C. 把逻辑地址换砖成绝对地址D. 把辅助存储器中的程序定位到主存的某个区域7. 在分页式存储管理中，逻辑地址由页号和页内地址两部分组成。

因而，分页的工作是在（C）时进行的。

A. 用户编制程序B. 地址转换C. 操作系统装入作业D. 系统初始化8. 采用固定分区存储管理的计算机系统中（D）的做法是错误的。

A. 为作业分配的分区不能小于作业长度B. 可同时在多个分区中各装一个作业C. 不允许多个作业同时存放在一个分区中D. 一个分区中可同时装入多个作业9. 在分页式虚拟存储管理中，若发现所要访问的页面不在主存储器中，则硬件要产生一个（C）中断。

A. I/OB. 缺段C. 缺页D. 访管10. 主存储器的每个存储单元都有一个地址与其对应，假定这些地址用n个二进制位来区分，则主存储器的容量为（D）。

A. 2n个字B. 2n-1个字C. 2n-1个字节D. 2n个字节11. LRU页面调度算法总是选择（C）页面调出。

第1章一、填空1．计算机由硬件系统和软件系统两个部分组成，它们构成了一个完整的计算机系统。

2．按功能划分，软件可分为系统软件和应用软件两种。

3．操作系统是在裸机上加载的第一层软件，是对计算机硬件系统功能的首次扩充。

4．操作系统的基本功能是处理机（包含作业）管理、存储管理、设备管理和文件管理。

5．在分时和批处理系统结合的操作系统中引入“前台”和“后台”作业的概念，其目的是改善系统功能，提高处理能力。

6．分时系统的主要特征为多路性、交互性、独立性和及时性。

7．实时系统与分时以及批处理系统的主要区别是高及时性和高可靠性。

8．若一个操作系统具有很强的交互性，可同时供多个用户使用，则是分时操作系统。

9．如果一个操作系统在用户提交作业后，不提供交互能力，只追求计算机资源的利用率、大吞吐量和作业流程的自动化，则属于批处理操作系统。

10．采用多道程序设计技术，能充分发挥CPU 和外部设备并行工作的能力。

二、选择1．操作系统是一种B 。

A．通用软件B．系统软件C．应用软件D．软件包2．操作系统是对C 进行管理的软件。

A系统软件B．系统硬件C．计算机资源D．应用程序3．操作系统中采用多道程序设计技术，以提高CPU和外部设备的A 。

A．利用率B．可靠性C．稳定性D．兼容性4．计算机系统中配置操作系统的目的是提高计算机的B 和方便用户使用。

A．速度B．利用率C．灵活性D．兼容性5．C 操作系统允许多个用户在其终端上同时交互地使用计算机。

A．批处理B．实时C．分时D．多道批处理6．如果分时系统的时间片一定，那么D ，响应时间越长。

A．用户数越少B．内存越少C．内存越多D．用户数越多三、问答1．什么是“多道程序设计”技术？它对操作系统的形成起到什么作用？答：所谓“多道程序设计”技术，即是通过软件的手段，允许在计算机内存中同时存放几道相互独立的作业程序，让它们对系统中的资源进行“共享”和“竞争”，以使系统中的各种资源尽可能地满负荷工作，从而提高整个计算机系统的使用效率。

学号专业计算机科学与技术姓名实验日期2017/11/23教师签字成绩实验报告【实验名称】基于顺序搜索的动态分区分配算法(二)【实验目的】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。

采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。

采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。

【实验原理】C++语言程序设计数据结构最佳适应算法最坏适应算法数据结构和符号说明1、boolROM[N];//定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcbnum[20];//定义作业数组，最大支持20个作业3、typedefstructPcb//定义作业结构体，包括名称，开始时间，大小，是否执行状态{charname[10];intstart;intsize;intstate=0;}pcb;主要函数：voidfind_free_rom()；//寻找空闲区voidsort1()；//对空闲区进行排序从小到大voidsort1()；//对空闲区进行排序从大到小voidshow()；//显示函数voidinsert_pcb1(pcb&a)；//最佳适应算法voidinsert_pcb2(pcb&a)；//最坏适应算法voidinit();//初始化函数算法流程图：最佳适应算法：最坏适应算法：#include<stdio.h>#include<string.h>#defineN1024boolROM[N];intp=0;intcount=0;intfree_rom_counter=0;//空闲区数目typedefstructPcb//进程结构体{charname[10];intstart;intsize;//大小intstate=0;//状态}pcb;pcbnum[20];//进程数组typedefstructFree_rom//空闲区结构体{intnum;intstart;intend;intspace;//空闲区大小}Free_room;Free_romfree_rom[100];//空闲区数组voidshow()//显示空闲区信息{printf("****************************************************************\n\n" );printf("空闲区名\t开始地址\t\t大小\t\t结束地址\t\t\n");for(inti=1;i<=free_rom_counter;i++)printf("%d\t\t%d\t\t\t%d\t\t%d\t\t\n",free_rom[i].num,free_rom[i].start,free_ rom[i].space,free_rom[i].end);printf("\n");printf("****************************************************************\n\n" );}voidfind_free_rom()//寻找空闲区，更新空闲区数组{free_rom_counter=0;inti,j,p;for(i=0;i<N;i++)if(ROM[i]==0){p=i;for(j=i;j<N;j++){if(ROM[j]==0){i=j;continue;}if(ROM[j]==1)//找到就更新信息{free_rom_counter++;free_rom[free_rom_counter].num=free_rom_counter;free_rom[free_rom_counter].start=p;free_rom[free_rom_counter].end=j-1;free_rom[free_rom_counter].space=j-p;i=j+1;break;}}if(j==N&&ROM[j-1]==0)//对最后一个内存进行特殊处理{free_rom_counter++;free_rom[free_rom_counter].num=free_rom_counter;free_rom[free_rom_counter].start=p;free_rom[free_rom_counter].end=j-1;free_rom[free_rom_counter].space=j-p;}}}voidsort1()//最佳适应算法对空闲区从小到大排序{find_free_rom();Free_roma;for(inti=1;i<free_rom_counter;i++)for(intj=1;j<free_rom_counter;j++)if(free_rom[j].space>free_rom[j+1].space){a=free_rom[j];free_rom[j]=free_rom[j+1];free_rom[j+1]=a;}}voidsort2()//最坏适应算法对空闲区从大到小排序{find_free_rom();Free_roma;for(inti=1;i<free_rom_counter;i++)for(intj=1;j<free_rom_counter;j++)if(free_rom[j].space<free_rom[j+1].space){a=free_rom[j];free_rom[j]=free_rom[j+1];free_rom[j+1]=a;}}voidinit()//初始化{for(inti=0;i<N;i++)ROM[i]=0;}voidinput(pcb&a)//输入{charname[10];printf("输入进程名\n");scanf("%s",&);printf("输入进程大小\n");scanf("%d",&a.size);}voidinsert_pcb1(pcb&a)//最佳适应算法插入进程{find_free_rom();sort1();inti,j,k;for(i=1;i<=free_rom_counter;i++)//判断插入if(a.size<=free_rom[i].space){for(j=free_rom[i].start;j<free_rom[i].start+a.size;j++) ROM[j]=1;a.state=1;a.start=free_rom[i].start;num[count++]=a;break;}if(i==free_rom_counter+1)//插入失败printf("可用空间不足!\n");}voidinsert_pcb2(pcb&a)//最坏适应算法插入{find_free_rom();sort2();inti,j,k;for(i=1;i<=free_rom_counter;i++)if(a.size<=free_rom[i].space){for(j=free_rom[i].start;j<free_rom[i].start+a.size;j++)//寻找ROM[j]=1;a.state=1;a.start=free_rom[i].start;num[count++]=a;break;}if(i==free_rom_counter+1)//插入失败printf("可用空间不足!\n");}voidDelete(pcb&a)//内存中释放进程{inti;for(i=a.start;i<a.start+a.size;i++)ROM[i]=0;//更新内存信息，更新进程状态数组a.state=0;printf("删除成功\n");find_free_rom();}intmain()//主函数{init();find_free_rom();intchoose1;intchoose;charname[10];printf("1、最佳适应算法\n");//主界面printf("2、最坏首次适应算法\n");scanf("%d",&choose1);pcba;do{printf("\n\n1、插入进程\n");printf("2、删除进程\n");printf("3、显示进程信息\n");printf("4、显示空余内存信息\n");scanf("%d",&choose);if(choose==1)//选择{input(a);if(choose1==1)insert_pcb1(a);elseinsert_pcb2(a);}elseif(choose==2){printf("输入删除进程的名字\n");scanf("%s",&name);for(inti=0;i<count;i++)if(!strcmp(num[i].name,name))Delete(num[i]);}elseif(choose==3){printf("****************************************************************\n\n" );printf("进程名\t\t开始地址\t\t大小\t\t结束地址\t\t\n");//输出内存信息for(inti=0;i<count;i++)if(num[i].state!=0)printf("%s\t\t%d\t\t\t%d\t\t%d\t\t\n",num[i].name,num[i].start,num[i].size,nu m[i].size+num[i].start-1);printf("\n****************************************************************\n\ n");}elseif(choose=4){find_free_rom();show();}elsebreak;}while(1);return0;}截图：构造如下空闲区：此时插入一个进程G，大小为80H，应插入到第二块空闲区再插入一个大小为30的进程H，应插入到第三块中再插入一个小进程，大小为5，插入到第二块空闲区，查看进程信息和空闲区信息：最佳适应算法成立。

操作系统习题（附参考答案）一、单选题（共100题，每题1分，共100分）1、下列存储器中，速度最快的是（）。

A、内存B、寄存器C、CacheD、磁盘正确答案：B2、时钟中断事件属于（）中断事件。

A、程序B、自愿性C、外部D、输入/输出正确答案：C3、可变分区存储管理系统中，若采用最佳适应分配算法，“空闲区表”中的空闲区可按（）顺序排列。

A、大小从大到小B、大小从小到大C、地址从大到小D、地址从小到大正确答案：B4、从静态的角度看，下列选项中哪一个是进程必须拥有而程序所没有的？（）A、常量数据B、全局变量C、进程控制块D、代码正文正确答案：C5、（）不是管程的组成部分。

A、对局部于管程内的数据结构设置初始值的语句B、对管程内数据结构进行操作的一组过程C、局部于管程的共享数据结构D、管程外过程调用管程内数据结构的说明正确答案：D6、下列关于父进程和子进程的叙述中，正确的是（）。

A、子进程执行完了，父进程才能执行B、父进程创建了子进程，因此父进程执行完了，子进程才能执行C、撤销子进程时，应该同时撤销父进程D、撤销父进程时，应该同时撤销子进程正确答案：D7、某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。

该系统可能会发生死锁的K的最小值是（）。

A、3B、4C、2D、5正确答案：B8、分页虚拟存储管理系统中，若采用FIFO页面置换算法，则当分配的物理页面数增加时，缺页中断的次数（）。

A、减少B、可能增加也可能减少C、增加D、不变正确答案：B9、产生内存抖动的主要原因是（）。

A、内存空间太小B、CPU运行速度太慢C、CPU调度算法不合理D、页面置换算法不合理正确答案：D10、（）存储管理兼顾了段式在逻辑上清晰和页式在存储管理上方便的优点。

A、分页B、段页式C、可变分区D、分段正确答案：B11、发生死锁的必要条件有四个，要预防死锁的发生，可以破坏这四个必要条件，但破坏（）条件是不太实际的。

操作系统练习题+参考答案一、单选题（共100题，每题1分，共100分）1、若系统中有5个并发进程涉及某个相同的变量A，则变量A的相关临界区由（）个临界区构成。

A、1B、3C、5D、6正确答案：C2、在分页虚拟存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页面数量的增加而增加。

下列算法中，可能出现Belady现象的是（）。

①LRU算法②FIFO 算法③OPT算法A、仅2B、仅1、2C、仅1、3D、仅2、3正确答案：A3、下列关于管道通信的叙述中，正确的是（）。

A、一个管道可以实现双向数据传输B、管道的容量仅受磁盘容量大小的限制C、进程对管道进行读操作和写操作都可能被阻塞D、一个管道只能有一个读进程或一个写进程对其操作正确答案：C4、不属于基本操作系统的是（）。

A、网络操作系统B、实时操作系统C、分时操作系统D、批处理操作系统正确答案：A5、采用SPOOLing技术的目的是（）。

A、提高独占设备的利用率B、提高程序的运行速度C、提高主机的效率D、减轻用户的编程负担正确答案：A6、在（）的控制下，计算机系统能及时处理由过程控制反馈的数据，并作出响应。

A、分时操作系统B、实时操作系统C、批处理操作系统D、多处理机操作系统正确答案：B7、在分页虚拟存储管理中，当发现要访问的页面不在主存时，则由硬件发出（）。

A、输入输出中断B、时钟中断C、缺页中断D、越界中断正确答案：C8、（）可以用来解决临界区问题。

A、时间片轮转算法B、银行家算法C、LRU算法D、Test正确答案：D9、可变分区存储管理系统中，若采用最佳适应分配算法，“空闲分区表”中的空闲区应该按（）顺序排列。

A、地址从大到小B、大小从大到小C、地址从小到大D、大小从小到大正确答案：D10、进程从运行状态转换到阻塞状态可能是由于（）。

A、现运行进程执行了signal操作B、现运行进程时间片用完C、现运行进程执行了wait操作D、进程调度程序的调度正确答案：C11、（）不是进程的特征。

沈阳工程学院学生实验报告（课程名称：操作系统）实验题目：可变分区存储管理班级计算机131 学号********** 姓名杨光成地点实训F608 指导教师吕海华王黎明实验日期: 2015 年 5 月19 日cin>>flag;free(flag);}else if(choice==0) break; //退出else //输入操作有误{cout<<"输入有误，请重试！"<<endl;continue;}}}图12、分配主存（如图2）Status alloc(int ch)}}图23、首次适应(如图3)Status First_fit(int request){//为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;while(p){if(p->data.state==Free && p->data.size==request)图34、最佳适应（如图4和图5）Status Best_fit(int request){int ch; //记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最小空间和最佳位置{if(p->data.state==Free && (p->data.size>=request) ){q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;}return OK;}图4图55、最差适应（如图6）Status Worst_fit(int request){int ch; //记录最大剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最大空间和最佳位置{if(p->data.state==Free && (p->data.size>=request) )q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;}return OK;}图6图76、主存回收和显示主存分配情况（如图8）Status free(int flag){DuLNode *p=block_first;for(int i= 0; i <= flag; i++)if(p!=NULL)p=p->next;elsereturn ERROR;p->data.state=Free;if(p->prior!=block_first && p->prior->data.state==Free)//与前面的空闲块相连{cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n";DuLNode *p=block_first->next;cout<<"分区号\t起始地址\t分区大小\t状态\n\n";while(p){cout<<" "<<flag++<<"\t";cout<<" "<<p->data.address<<"\t\t";cout<<" "<<p->data.size<<"KB\t\t";if(p->data.state==Free) cout<<"空闲\n\n";else cout<<"已分配\n\n";p=p->next;}cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n"; }图8。

学号专业姓名实验日期教师签字成绩实验报告【实验名称】采用可变式分区管理，使用首次获最佳适应算法实现内存分配与回收【实验目的与原理】1、理解首次获最佳适应算法的内涵，并熟练掌握该算法。

2、学会可变式分区管理的原理是即在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。

3、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区没有时应将空闲区一分为二。

为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。

4、当一个作业执行完成时，作业所占用的分区应归还给系统。

作业的释放区与空闲区的邻接分以下四种情况考虑：①释放区下邻（低地址邻接）空闲区；②释放区上邻（高地址邻接）空闲区③释放区上下都与空闲区邻接；④释放区与空闲区不邻接。

【实验内容】#include<stdio.h>#include<iostream>#include<string>using namespace std;const int MAXJOB=100;//定义表最大记录数typedef struct node{int front;int length;char data[20];}job;job frees[MAXJOB];//定义空闲区表int free_quantity;job occupys[MAXJOB];//定义已分配区表int occupy_quantity;//初始化函数void initial(){int i;for(i=0;i<MAXJOB;i++){frees[i].front=-1;frees[i].length=0;strcpy(frees[i].data,"free");occupys[i].front=-1;occupys[i].length=0;strcpy(occupys[i].data," ");}free_quantity=0;occupy_quantity=0;}//创建空闲分区表int creatfree(){FILE *fp;char fname[20];cout<<"请输入空闲区数据文件来源的文件名:"; cin>>fname;if((fp=fopen(fname,"r"))==NULL){cout<<"错误,文件打不开,请检查文件名"<<endl; }else{while(!feof(fp)){fscanf(fp,"%d\t%d\n",&frees[free_quanti ty].front,&frees[free_quantity].length);free_quantity++;}cout<<"空闲的分区表已建立！\n";return 1;}return 0;}void sort()//将free空间安首地址从小到大的顺序排列{int i,j,p;for(i=0;i<free_quantity-1;i++){p=i;for(j=i+1;j<free_quantity;j++){if(frees[j].front<frees[p].front){p=j;}}if(p!=i){frees[free_quantity]=frees[i];frees[i]=frees[p];frees[p]=frees[free_quantity];}}}//显示函数void show(){int i;cout<<endl<<"----------------------------------------------------------"<<endl;cout<<"当前空闲表:"<<endl;cout<<" 起始地址长度状态"<<endl;for(i=0;i<free_quantity;i++){cout.setf(2);cout.width(12);cout<<frees[i].front;cout.width(10);cout<<frees[i].length;cout.width(8);cout<<frees[i].data<<endl;}cout<<endl<<"----------------------------------------------------------"<<endl;cout<<"当前已分配表:"<<endl;cout<<" 起始地址长度占用作业名"<<endl;for(i=0;i<occupy_quantity;i++){cout.setf(2);cout.width(12);cout<<occupys[i].front;cout.width(10);cout<<occupys[i].length;cout.width(8);cout<<occupys[i].data<<endl;}cout<<endl<<"----------------------------------------------------------"<<endl;}//最先适应分配算法void assign(){char job_name[20];int job_length;int i,j,flag,t;cout<<"请输入新申请内存空间的作业名和空间大小:";cin>>job_name;cin>>job_length;flag=0;for(i=0;i<free_quantity;i++){if(frees[i].length>=job_length)//如果空闲空间I的长度〉作业长度{flag=1; //空闲标志位就置1 }}if(flag==0){cout<<endl<<"对不起,当前没有能满足你申请长度的空闲内存,请稍候再试！"<<endl;}else{t=0;i=0;while(t==0)//为空闲区间的时候{if(frees[i].length>=job_length){t=1;}i++;//如果空闲空间I的长度不大于作业长度，I加一，判断下一个空间}i--;occupys[occupy_quantity].front=frees[i] .front;strcpy(occupys[occupy_quantity].data,jo b_name);occupys[occupy_quantity].length=job_len gth;occupy_quantity++;if(frees[i].length>job_length)//如果空间的长度大于作业的长度，{frees[i].front+=job_length;frees[i].length-=job_length;}else{for(j=i;j<free_quantity-1;j++){frees[j]=frees[j+1];}free_quantity--;cout<<"内存空间成功:)"<<endl;}}}//撤消作业void cancel(){char job_name[20];int i,j,flag,p=0;int front;int length;cout<<"请输入要撤消的作业名:";cin>>job_name;flag=-1;for(i=0;i<occupy_quantity;i++){if(!strcmp(occupys[i].data,job_name))//当输入作业名匹配时{flag=i;front=occupys[i].front;length=occupys[i].length;}}if(flag==-1){cout<<"没有这个作业名"<<endl;}else{//加入空闲表for(i=0;i<free_quantity;i++){if((frees[i].front+frees[i].length)==fr ont)//上空{if(((i+1)<free_quantity)&&(frees[i+1].f ront==front+length))//下空{frees[i].length=frees[i].length+frees[i +1].length+length;for(j=i+1;j<free_quantity;j++){frees[j]=frees[j+1];}free_quantity--;p=1;}else{frees[i].length+=length;p=1;}}if(frees[i].front==(front+length))//下空上不空{frees[i].front=front;frees[i].length+=length;//第i 个空闲区间的长度=第i个空闲区间的长度+lengthp=1;}}if(p==0)//上下空闲区都不空{frees[free_quantity].front=front;frees[free_quantity].length=length;free_quantity++;}//删除分配表中的该作业for(i=flag;i<occupy_quantity;i++){occupys[i]=occupys[i+1];}occupy_quantity--;}}void main(){int flag=0;int t=1;int chioce=0;cout<<"*********** xxxxxxxxx***********\n"; initial();flag=creatfree();while(flag==1){sort();cout<<" 可变分区存储管理模拟系统"<<endl;cout<<" 1.申请空间 "<<endl;cout<<" 2.撤消作业 "<<endl;cout<<" 3.显示空闲表和分配表"<<endl;cout<<" 0.退出"<<endl;cout<<"请选择:";cin>>chioce;switch(chioce){case 1:assign();break;case 2:cancel();break;case 3:show();break;case 0:flag=0;break;default:cout<<"选择错误!"<<endl;}}}实验结果显示：【实验小结】本实验难度在两个方面，一是首次最佳适应算法assign()，这里我用的是结构体数组来存储空闲分区；二是对已分配分区的释放，这里同样采取结构体数组来存储已分配分区，用cancle（）函数来实现。

主 题题： 《操作系统原理》学习笔记内 容容：《操作系统原理操作系统原理》》学习笔记学习笔记三三————存储管理存储管理存储管理主存储器又称为内存储器，它是处理机可以直接访问的存储器。

主存速度快，但容量有限。

存储管理主要是对主存的管理，同时也涉及到主存和外存交换信息。

一、存储管理的目的与功能计算机的系统结构是以内存储器为中心。

受系统地址总线的限制，内存空间并不能做的很大。

16位地址总线，内存最大64KB 。

32位地址总线，内存最大4GB 。

在多道系统中，多个用户作业要同时使用有限的内存空间。

内存储器成为系统的“瓶颈”资源。

如何充分利用和有效管理内存空间，是操作系统必须完成的主要任务。

在多道系统中，存储管理的目的是为系统中并发运行的多道作业提供相互独立的存储空间，并为用户使用存储器提供方便。

主存储器的存储空间分为两个部分：系统区：用于存放操作系统的程序和数据。

用户区：存放系统应用程序和用户的程序和数据。

存储管理主要是对用户区的存储空间进行管理。

操作系统中存储管理的功能主要有五个方面：存储分配。

为进入系统的多个作业合理地分配存储空间每个作业的程序及其数据存放在内存空间的什么区域。

使用连续的内存区域，还是把它分成若干块来占用不连续的存储空间。

合理组织作业占用的空间，以达到既便于程序运行时存取信息，又能够最大限度地减小空间的浪费，使内存空间得到充分的利用地址变换。

用户作业调入内存空间时所处的位置是根据内存空间当时的状况决定的。

一般情况下，同一个程序在每次调入内存时所占用的位置是完全不同的。

为了保证程序在使用内存的不同区域时仍能正确地执行，必须把在程序执行时要访问的存储单元的位置，由用户在编制程序时所定的地址变换成它们在内存的实际地址。

地址变换又称为地址重定位。

存储保护。

在整个内存空间中既存放着系统的程序和数据，又有多个用户的程序和数据。

保证系统的程序和数据不被用户非法访问和破坏。

保证每一个用户信息的安全。

操作系统常见题解析及模拟题内容【例 2】对一个将页表存放在内存中的分页系统:（1）如访问内存需要0． 2μs，有效访问时间为多少?（2）如果加一快表，且假定在快表中找到页表项的机率高达90％，则有效访问时间又是多少( 假定查快表需花的时间为0)?答：（ 1）有效访问时间为：2×0． 2=0 ． 4μs（2）有效访问时间为：0． 9×0． 2+(1 — 0．9) ×2×0． 2＝ 0． 22 ps。

【例 3】某系统采用页式存储管理策略，拥有逻辑空间32 页，每页 2K ，拥有物理空间1M 。

（1）写出逻辑地址的格式。

（2）若不考虑访问权限等，进程的页表有多少项?每项至少有多少位 ?（3）如果物理空间减少一半，页表结构应相应作怎样的改变?答：（ 1）该系统拥有逻辑空间32 页，故逻辑地址中页号必须用 5 位来描述：而每页为2K ，因此，页内地址必须用11 位来描述，这样可得到它的逻辑地址格式如下：1511 100页号页内地址(2) 每个进程最多有32 个页面，因此，进程的页表项最多为32 项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块块号，1M 的物理空间可分成29 个内存块，故每个页表项至少有9 位(3) 如果物理空间减少一半，则页表中页表项数仍不变，但每项的长度可减少 1 位。

【例 4】已知某分页系统，主存容量为64K，页面大小为1K ，对一个 4 页大的作业，其0、l 、 2、3 页分别被分配到主存的2、4、 6、 7 块中。

(1)将十进制的逻辑地址 1023、 2500、 3500、 4500 转换成物理地址。

(2)以十进制的逻辑地址 1023 为例画出地址变换过程图。

答： (1)对上述逻辑地址，可先计算出它们的页号和页内地址(逻辑地址除以页面大小，得到的商为页号，余数为页内地址)，然后通过页表转换成对应的物理地址。

①逻辑地址1023： 1023／ 1K ，得到页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为2×1K+1023=3071 。

一、单项选择题1．要保证一个程序在主存中被改变了存放位置后仍能正确执行,则对主存空间应采用（）技术。

A．动态重定位B．静态重定位C．动态分配D．静态分配2．固定分区存储管理把主存储器划分成若干个连续区，每个连续区称一个分区。

经划分后分区的个数是固定的，各个分区的大小（）。

A．是一致的B．都不相同C．可以相同，也可以不相同,但根据作业长度固定D．在划分时确定且长度保持不变3．采用固定分区方式管理主存储器的最大缺点是（）。

A．不利于存储保护B．主存空间利用率不高C．要有硬件的地址转换机构D．分配算法复杂4．采用可变分区方式管理主存储器时，若采用最优适应分配算法，宜将空闲区按（）次序登记在空闲区表中。

A．地址递增B．地址递减C．长度递增D．长度递减5．在可变分区存储管理中，某作业完成后要收回其主存空间，该空间可能要与相邻空闲区合并。

在修改未分配区表时，使空闲区个数不变且空闲区始址不变的情况是（)空闲区。

A．无上邻也无下邻B．无上邻但有下邻C．有上邻也有下邻D．有上邻但无下邻6．在可变分区存储管理中，采用“紧凑"技术可以（）。

A．汇集主存中的空闲区B．增加主存容量C．缩短访问周期D．加速地址转换7．页式存储管理中的页表是由（）建立的。

A．操作员B．系统程序员C．用户D．操作系统8．采用页式存储管理时，重定位的工作是由（）完成的。

A．操作系统B．用户C．地址转换机构D．主存空间分配程序9．采用段式存储管理时，一个程序如何分段是在（）决定的。

A．分配主存时B．用户编程时C．装人作业时D．程序执行时10．采用段式存储管理时,一个程序可以被分成若干段，每一段的最大长度是由( ）限定的。

A．主存空闲区的长度B．硬件的地址结构C．用户编程时D．分配主存空间时11．实现虚拟存储器的目的是（)。

A．扩充主存容量B．扩充辅存容量C．实现存储保护D．加快存取速度12．LRU页面调度算法是选择( ）的页面先调出.A．最近才使用B．最久未被使用C．驻留时间最长D．驻留时间最短13．若进程执行到某条指令时发生了缺页中断，经操作系统处理后，当该进程再次占用处理器时,应从（）指令继续执行。

存储器管理一、填空题1．常用的内存管理方法有①、②、③、④、⑤。

2．作业的地址空间指的是①，地址空间中的地址称为②。

内存地址的集合为③，它的地址称为④。

3．在存储器的管理中，常用的方式来摆脱主存容量的限制。

4．虚拟存储器的容量是由计算机系统的①和②确定的。

5．分区式分配可分为①和②。

6．固定分区，一般采用①重定位法；可变分区，一般采用②重定位法。

7．可变分区的主存分配算法有①、②和③。

8．实现虚拟存储技术，需要有一定的物质基础，其一是①，其二是②，其三是③9．对换技术也是一种在多道环境下用于的方法之一。

10．在分区式的管理中，各用户进程和作业所要求的内存容量要受到的限制，可以使用覆盖和交换技术来扩充内存。

11．在页式存储管理中，内存的物理地址空间被划分成大小相等的①，进程的虚拟地址空间被划分成相应的若干②。

12．页式管理中，页式虚地址与内存物理地址的映射是由①和②完成的。

13．在页式管理中，页表一般驻留在①的某个固定区域，取一个数据或指令至少要访问②次内存。

14．请求页式管理是一种①页式管理，它的②与静态页式管理相同，也是通过查找③来完成的，但是静态页式管理要求作业或进程在④全部装入⑤。

15．页式虚拟存储管理中，页表中“标志位”的作用是，一般系统的页表中还设置有“改变位”，其作用是判断某页是否在内存中被改变。

16．在请求页式管理中，当硬件地址变换机构发现所需的页不在①时，产生②中断信号，由③作出相应的处理。

17．置换（淘汰）算法是当系统发生缺页时，在内存中没有①时被调用的，它的目的是选出一个被②的页面。

如果内存中有足够的③存放所调入的页，则不必使用④。

18．在页式管理中，“主存分配表”的作用是①，它是整个系统②。

“主存分配表”可采用③方法。

19．在段式管理中，分配内存是以①为单位，每段分配一个②区。

由于各段长度③，所以这些存储区的大小不一，而且同一进程的各段之间不要求④。

20．在段式管理中，每个段是一个有意义的①，所以段的②和③更有意义，同时也容易实现。

可变分区的四种回收算法引言在操作系统中，内存管理是一个重要的任务。

在进行内存分配时，如果使用固定大小的分区，会导致内存碎片问题，导致大量的空闲内存无法被有效利用。

为了解决这一问题，可变分区管理算法被提出。

本文将详细探讨可变分区的四种回收算法，包括首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。

一、首次适应算法首次适应算法是一种简单直观的内存分配算法。

它的思想是按照请求的顺序查找可用的空闲分区，并将其分配给请求的作业。

首次适应算法的具体步骤如下： 1. 遍历可用分区列表，查找第一个大于等于作业大小的空闲分区。

2. 如果找到了合适的分区，将作业分配给该分区，并更新分区表。

3. 如果没有找到合适的分区，作业将等待。

首次适应算法的优点是简单易懂，易于实现。

然而，它可能会导致较大的碎片和低内存利用率。

二、最佳适应算法最佳适应算法是一种更高效的内存分配算法。

它的思想是在可用分区中找到最小的适合作业大小的空闲分区，并将其分配给请求的作业。

最佳适应算法的具体步骤如下： 1. 遍历可用分区列表，找到最小的大于等于作业大小的空闲分区。

2. 如果找到了合适的分区，将作业分配给该分区，并更新分区表。

3. 如果没有找到合适的分区，作业将等待。

最佳适应算法的优点是可以减少碎片和提高内存利用率。

然而，它的查找过程可能更耗时，因为需要遍历所有的可用分区。

三、最坏适应算法最坏适应算法是一种与最佳适应算法相反的内存分配算法。

它的思想是在可用分区中找到最大的适合作业大小的空闲分区，并将其分配给请求的作业。

最坏适应算法的具体步骤如下： 1. 遍历可用分区列表，找到最大的大于等于作业大小的空闲分区。

2. 如果找到了合适的分区，将作业分配给该分区，并更新分区表。

3. 如果没有找到合适的分区，作业将等待。

最坏适应算法的优点是可以减少外部碎片的产生。

然而，它可能会导致大量的内部碎片和较低的内存利用率。

四、快速适应算法快速适应算法是一种结合了首次适应算法和最佳适应算法的内存分配算法。

实验题目：可变分区存储管理一、实验目的可变分区存储管理方式是操作系统中存储管理的重要方式，其主要思想是用户作业进行连续存储，每次按照用户的请求，如果内存中有能满足用户作业大小的空闲区，就采用不同的算法分配给用户，否则，不分配，可变分区容易产生外零头。

分区分配算法包括最佳适应算法、最坏适应算法、首次适应算法等。

通过本实验可加深学生对存储器管理方式的把握以及分配算法的理解，并提高程序设计的能力。

二、实验环境个人PC机WindowsXP操作系统I5-2400CPU 3.10Ghz 2GB内存C-Free C语言程序设计软件三、实验的重点和难点可变分区的的收回四、实验内容利用C语言或C++语言或Java语言实现可变分区存储管理，具体要求如下：1. 以一个一维数组模拟内存，数组类型为整型，共计1000个元素；2. 用一个单链表表示可变分区空闲表，链表每个结点表示一个空闲区，每个结点信息包括起始地址、大小。

3. 分区分配算法采用最佳适应算法、首次适应算法，并将算法用函数实现。

4. 自己假设几个作业，包括作业的名称、大小，进入系统的顺序。

5. 初始内存中没有任何作业，随着用户输入的每一个作业的到来，动态为其分配内存。

6. 使用的算法用户要能够随时更换。

五、实验结果或实验代码(1) 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数可以调整。

当要装入一个作业时，根据作业需要的内存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若没有，则作业等待。

随着作业的装入、完成，内存空间被分割成许多大大小小的分区。

有的分区被作业占用，有的分区空闲。

例如，某时刻内存空间占用情况如图1所示。

为了说明那些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如表1所示。

表1 空闲区说明表图1 内存空间占用情况62241其中，起始地址指出个空闲区的内存起始地址，长度指出空闲区的大小。

第四章存储器管理一、判断题1.在固定分区分配中,每个分区的大小是（）。

A.相同B.随作业长度变化C.可以不同但预先固定D.可以不同但根据作业长度固定2.在可变分区分配中，首次适应算法的空闲区是（）。

A.按地址递增顺序连在一起B.始端指针表指向最大空闲区C.按大小递增顺序连在一起D.寻找从最大空闲区开始3.在可变分区分配中，最佳适应算法的空白区是（）。

A.按大小递减顺序连在一起B.按大小递增顺序连在一起C.按地址由小到大排列D.按地址由大到小排列4.设内存的分配情况如下图所示。

若要申请一块40K的内存空间，采用最佳适应算法，则所申请到的分区首址为（）。

A．100K B．190K C．330K D．410K5. 有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。

系统中空闲区按三种算法组成的空闲区队列如下图所示。

其中，（）对该作业序列合适。

A．首次适应法 B. 最佳适应法 C. 最坏适应法 D. 无算法6.在可变式分区存储管理中的拼接技术可以（）。

A.集中空闲区B.增加主存容量C.缩短访问周期D.加速地址转换7.支持程序浮动的地址转换机制是( ) 。

A、动态重定位B、静态重定位C、页式地址转换D、段式地址转换8. 采用页式存储管理的系统中，若地址用32位表示，其中20位表示页号，，则每页的大小为（）。

A. 212B. 220C. 224D. 2329. 在一个页式存储管理系统中, 页表内容如下所示:若页的大小为4K, 则地址转换机构将逻辑地址0转换成的物理地址为（）。

A. 8192B. 4096C. 2048D. 102410. 无快表的基本页式存储管理中，每次从主存中取指令或取操作数，至少要（）次访问主存。

A 0次B 1次C 2次D 3次11. 某段表的内容表示如下:逻辑地址(2，154)对应的物理地址为（）。

A. 120K+2B. 480K+154C. 30K+154D. 发生越界中断12．在段页式存储管理系统中，内存等分成（），程序按逻辑模块划分成若干（）。

操作系统原理试题题库含答案(3)1、下述解决死锁的方法中,属于死锁避免策略的是( )。

A、银行家算法B、资源有序分配法C、资源分配图化简法D、撤消进程法正确答案： A2、进程有三种基本状态,可能的状态转换是( )。

A、就绪态到运行态、等待态到就绪态、运行态到等待态B、就绪态到运行态、就绪态到等待态、等待态到运行态C、就绪态到运行态、等待态到就绪态、等待态到运行态D、运行态到就绪态、就绪态到等待态、等待态到运行态正确答案： A3、在存储管理中,采用地址变换机构的目的是()A、加快进程空间寻址B、提高CPU效率C、进程空间保护和内存共享D、便于有效分配内存正确答案： A4、关于碎片的说法以下哪个是正确的（）。

A、静态页式存储管理中不存在碎片B、段页式存储管理中存在外碎片,但是不存在内碎片C、段式存储管理不存在内碎片D、页式存储管理既存在内碎片,也存在外碎片正确答案： C5、在面向用户的调度准则中,( )是选择分时系统中进程调度算法的重要准则。

A、响应时间快B、平均周转时间短C、截止时间的保证D、优先权高的作业能获得优先服务正确答案： A6、C语言编程中的printf函数属于（）。

A、系统调用B、原语C、自定义函数D、库函数正确答案： A7、关于进程的运行、就绪和阻塞三个状态,下列观点正确的是（）。

A、每个进程从创建到撤消都要经历这三个状态B、每个进程从创建到撤消,各个状态只能经历一次C、某些进程可以从阻塞状态转化为运行状态D、某些进程可以从运行状态转化为就绪状态正确答案： D8、在操作系统中引入线程的目的是____。

A、使多个程序能并发执行B、提高资源的利用率C、提高系统的吞叶量D、减少程序并发执行时的时空开销正确答案： D9、位示图方法可用于_____。

A、盘空间的管理B、盘的驱动调度C、文件目录的查找D、页式虚拟存贮管理中的页面调度正确答案： A10、一个进程是( )。

A、协处理器执行的程序B、一个独立的程序+数据集C、 PCB结构与程序和数据的集合D、一个独立的程序正确答案： C11、与计算机硬件关系最密切的软件是( )A、编译程序B、数据库管理程序C、游戏程序D、操作系统正确答案： D12、为了兼顾短作业和长时间等待的作业,应采用( )。

第三章一、填空1．将作业相对地址空间的相对地址转换成内存中的绝对地址的过程称为地址重定位。

2．使用覆盖与对换技术的主要目的是提高内存的利用率。

3．存储管理中，对存储空间的浪费是以内部碎片和外部碎片两种形式表现出来的。

4．地址重定位可分为静态重定位和动态重定位两种。

5．在可变分区存储管理中采用最佳适应算法时，最好按尺寸法来组织空闲分区链表。

6．在分页式存储管理的页表里，主要应该包含页号和块号两个信息。

7．静态重定位在程序装入时进行，动态重定位在程序执行时进行。

8．在分页式存储管理中，如果页面置换算法选择不当，则会使系统出现抖动现象。

9．在请求分页式存储管理中采用先进先出（FIFO）页面淘汰算法时，增加分配给作业的块数时，缺页中断的次数有可能会增加。

10．在请求分页式存储管理中，页面淘汰是由于缺页引起的。

二、选择1．虚拟存储器的最大容量是由 A 决定的。

A．内、外存容量之和 B．计算机系统的地址结构C．作业的相对地址空间 D．作业的绝对地址空间2．采用先进先出页面淘汰算法的系统中，一进程在内存占3块（开始为空），页面访问序列为1、2、3、4、1、2、5、1、2、3、4、5、6。

运行时会产生 D 次缺页中断。

A．7 B．8 C．9 D．10从图3-8中的“缺页计数”栏里可以看出应该选择D。

图3-8 选择题2配图3．系统出现“抖动”现象的主要原因是由于 A 引起的。

A．置换算法选择不当 B．交换的信息量太大C．内存容量不足 D．采用页式存储管理策略4．实现虚拟存储器的目的是 D 。

A．进行存储保护 B．允许程序浮动C．允许程序移动 D．扩充主存容量5．作业在执行中发生了缺页中断，那么经中断处理后，应返回执行 B 指令。

A．被中断的前一条 B．被中断的那条C．被中断的后一条 D．程序第一条6．在实行分页式存储管理系统中，分页是由 D 完成的。

A．程序员B．用户C．操作员D．系统7．下面的 A 页面淘汰算法有时会产生异常现象。

CH4 应用题参考答案1 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。

分别用FIFO、OPT和LRU算法，对分配给程序3个页框、4个页框、5个页框和6个页框的情况下，分别求出缺页中断次数和缺页中断率。

答：只要把表中缺页中断次数除以20，便得到缺页中断率。

2 在一个请求分页虚拟存储管理系统中，一个作业共有5页，执行时其访问页面次序为：(1) 1、4、3、1、2、5、1、4、2、1、4、5。

(2) 3、2、1、4、4、5、5、3、4、3、2、1、5。

若分配给该作业三个页框，分别采用FIFO和LRU面替换算法，求出各自的缺页中断次数和缺页中断率。

答：(1) 采用FIFO为9次，9/12=75%。

采用LRU为8次，8/12=67%。

(2) 采用FIFO和LRU均为9次，9/13=69%。

3 一个页式存储管理系统使用FIFO、OPT和LRU页面替换算法，如果一个作业的页面走向为：(1) 2、3、2、1、5、2、4、5、3、2、5、2。

(2) 4、3、2、1、4、3、5、4、3、2、1、5。

(3 )1、2、3、4、1、2、5、1、2、3、4、5。

当分配给该作业的物理块数分别为3和4时，试计算访问过程中发生的缺页中断次数和缺页中断率。

答：(1) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。

使用LRU为7次，7/12=58%。

使用OPT为6次，6/12=50%。

作业的物理块数为4块，使用FIFO为6次，6/12=50%。

使用LRU为6次，6/12=50%。

使用OPT为5次，5/12=42%。

(2) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。

使用LRU为10次，10/12=83%。

使用OPT为7次，7/12=58%。

作业的物理块数为4块，使用FIFO为10次，10/12=83%。

使用LRU为8次，8/12=66%。

可变分区分配算法
可变分区分配算法是一种内存管理技术，用于将可用的内存空间分配给进程。

这种算法允许进程使用不同大小的内存块，并且可以在运行时动态地改变它们的大小。

可变分区分配算法通常使用两种不同的数据结构来管理内存：空闲块列表和已分配块列表。

空闲块列表包含所有未被占用的内存块，而已分配块列表则包含所有已被占用的内存块。

当一个进程需要内存时，操作系统会从空闲块列表中选择一个足够大的未被占用的内存块，并将其标记为已被占用。

如果没有足够大的空闲块，则操作系统会将多个小的空闲块合并成一个大的空闲块，然后再进行分配。

当一个进程释放了它所使用的内存时，该内存块会被标记为空闲，并添加到空闲块列表中。

如果相邻的两个空闲块可以合并成一个更大的空闲块，则操作系统会执行合并操作以减少碎片化。

可变分区分配算法有多种实现方式，其中最常见的是首次适应算法、最佳适应算法和最差适应算法。

首次适应算法是一种简单的可变分区分配算法，它从空闲块列表的开头开始查找，找到第一个足够大的空闲块并将其分配给进程。

这种算法的优点是实现简单，但会导致碎片化问题。

最佳适应算法是一种更高级的可变分区分配算法，它从空闲块列表中查找最小的足够大的空闲块并将其分配给进程。

这种算法可以减少碎片化问题，但需要更多的计算资源。

最差适应算法与最佳适应算法相反，它选择最大的足够大的空闲块并将其分配给进程。

这种算法可以减少外部碎片问题，但会导致内部碎片问题。

总之，可变分区分配算法是一种重要的内存管理技术，它可以提高系统性能和资源利用率。

不同的实现方式有不同的优缺点，在选择时需要根据具体情况进行权衡。