下载文档原格式
操作系统第4章练习题操作系统常见题解析及模拟题内容第4章存储器管理4.1典型例题解析【例1】某系统采用动态分区分配方式管理内存，内存空间为640k，高端40k用来存放操作系统。
在内存分配时，系统优先使用空闲区低端的空间。
对下列的请求序列：作业1申请130k、作业2申请60k、作业3申请100k、作业2释放60k、作业4申请200k、作业3释放100k、作业1释放130k、作业5申请140k、作业6申请60k、作业7申请50k、作业6释放60k，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。
动作首次适应算法最佳适应算法空闲分区已分配分区己分配分区空闲分区（始址，大(作业，始址，大小)（作业，始址，大小)(始址，大小)小)130,470190,410l，o，1301，o，1302,130,601，o，1302,130,603,190,100l，0,1303,190,100l，0,1303,190,1004,290,200l，0，1304,290,2004,290,2004,290,2005,0,1404,290,2005,0，1406,490,604,290,2005，o，1406,490,607,550,504,290,2005,0，1407,550,50130,470190,410l，0,1302,130,60作业1申请130kl，0,130作业2申请60k1,0,130作业3申请100k2,130,603,190,100作业2释放60kl，0,1303,190,100290,310130,60290,310130,60490,1lo130，160490,1100,290490,110140，150490,110200,90490,110290,310130,60290,310130,60490.110490，110130，160490,1100,290490，110140，150550,50140,1501，o，130作业4申请200k3,190,1004,290,200作业3释放100k作业l释放130k作业5申请140kl，0，1304,290,2004,290,2004,290,2005,0,1404,290,2005，o，1406,140,604,290,2005,0,1406,140,607，200,504,290,2005,0,1407,200,50作业6申请60k作业7申请50k250,40490,110140,60250,40490,110140,150作业6释放60k490,60140，1501操作系统常见题解析及模拟题内容请问：采用首次适应环境算法和最佳适应环境算法展开上述内存的分配和废旧后，内存的实际采用情况分别例如图(a)和(b)右图。
动态分区分配方式的模拟动态分区分配方式是计算机中内存管理的一种重要方式。
在动态分区分配方式中，内存空间被分割为多个不同大小的分区，每个分区可以被进程占用。
当一个进程需要内存时，系统会为其分配一个适当大小的分区，进程结束后，该分区将会被释放出来供其他进程使用。
为了更好地理解动态分区分配方式的原理和实际运作，可以通过模拟的方法来观察和分析。
下面是一个简单的动态分区分配方式的模拟过程：假设我们有一块容量为6400KB的内存，要模拟分配4个进程的情况。
这4个进程的内存需求分别是1000KB，2000KB，500KB和300KB。
首先，我们可以将内存划分为几个分区，每个分区的大小根据需要进行调整。
可以设置整块内存为一块分区（大小为6400KB），或者划分成多个较小的分区。
由于这里有4个进程需要分配内存，我们可以为它们设置4个分区，分别为P1，P2，P3和P41.初始状态：内存：[6400KB]（未分配）进程：P1，P2，P3，P4（空）2.分配P1：内存：[1000KB]（P1）、[5400KB]（未分配）进程：P1，P2，P3，P4P1占用了1000KB的内存，剩余空间为5400KB。
3.分配P2：内存：[1000KB]（P1）、[2000KB]（P2）、[3400KB]（未分配）进程：P1，P2，P3，P4P2占用了2000KB的内存，剩余空间为3400KB。
4.分配P3：内存：[1000KB]（P1）、[2000KB]（P2）、[500KB]（P3）、[2900KB]（未分配）进程：P1，P2，P3，P4P3占用了500KB的内存，剩余空间为2900KB。
5.分配P4：内存：[1000KB]（P1）、[2000KB]（P2）、[500KB]（P3）、[300KB]（P4）、[2600KB]（未分配）进程：P1，P2，P3，P4P4占用了300KB的内存，剩余空间为2600KB。
在模拟的过程中，我们可以看到进程在内存中的分配情况和未分配内存的变化。
循环首次适应的动态分区分配算法模拟1.初始化内存空间为一个整体的空闲块。
2.当进程请求内存空间时，多次内存空闲块的循环链表，直到找到一个合适大小的空闲块为止。
3.如果找到了合适的空闲块，则将其划分为两个部分，一个部分给予进程使用，另一个部分保留为新的空闲块。
4.如果未找到合适的空闲块，则表示内存空间不足，需要进行深度缺页异常处理。
以下是一个循环首次适应算法的模拟过程：1.假设一个内存空间大小为1000KB，初始时为一个整体的空闲块。
2.进程A请求100KB的内存空间，开始内存空闲块链表。
3.如果找到合适的空闲块（大小≥100KB），则将其划分为两个部分，一个部分分配给进程A，另一个部分保留为新的空闲块。
4.进程B请求200KB的内存空间，继续内存空闲块链表。
5.如果找到合适的空闲块（大小≥200KB），则将其划分为两个部分，一个部分分配给进程B，另一个部分保留为新的空闲块。
6.进程C请求150KB的内存空间，继续内存空闲块链表。
7.找到合适的空闲块（大小≥150KB），将其划分为两个部分，一个部分分配给进程C，另一个部分保留为新的空闲块。
8.进程D请求300KB的内存空间，继续内存空闲块链表。
但此时已经循环了一次，仍未找到合适的空闲块。
9.进行深度缺页异常处理，即向操作系统申请更多的内存空间。
10.操作系统分配一块500KB的空闲块给进程D。
11.继续内存空闲块链表，找到合适的空闲块（大小≥300KB）。
12.将其划分为两个部分，一个部分分配给进程D，另一个部分保留为新的空闲块。
13.进程E请求250KB的内存空间，继续内存空闲块链表。
14.找到合适的空闲块（大小≥250KB），将其划分为两个部分，一个部分分配给进程E，另一个部分保留为新的空闲块。
15.当所有进程运行完毕后，剩余的空闲块可以继续加入链表，供下一次的分配请求使用。
总结起来，循环首次适应算法通过循环链表合适大小的空闲块来满足进程的内存需求，能够最大限度地利用内存空间，避免了内存碎片的产生。
最好适应动态分区分配算法模拟动态分区分配算法是操作系统中的一种管理内存分配的方法，它可以根据实际需求动态地分配和回收内存。
在动态分区分配算法中，内存被划分为多个较小的区域，每个区域可以被分配给一个进程使用。
当一个进程结束后，它所占用的内存可以被回收，并重新分配给其他进程使用。
以下是一个模拟动态分区分配算法的例子。
假设系统中有4个进程需要申请内存空间，它们的大小分别是：P1（100KB）、P2（200KB）、P3（400KB）、P4（300KB）。
本例中我们采用首次适应算法（First Fit）来模拟动态分区分配。
首次适应算法是指内存分区按大小顺序排列，当有一个进程需要内存分配时，系统从低地址到高地址进行，找到一个能满足所需大小的内存分区即可。
以下是该算法的详细步骤：1.初始化内存分区列表。
假设系统中的内存总大小为1000KB，起始地址为0KB，结束地址为1000KB。
此时内存分区列表为空。
2.进程P1申请100KB的内存空间。
内存分区列表，找到第一个大小大于等于100KB的空闲分区，假设为Q1（大小为200KB）。
将分区Q1划分为两个部分：一个部分给进程P1使用，大小为100KB；另一个部分留作未分配区，大小为100KB。
更新内存分区列表，添加两个分区：分区Q1（已分配给P1）和分区Q2（未分配区，大小为100KB）。
此时内存分区列表为：Q1（100KB，已分配给P1）、Q2（100KB，未分配区）。
3.进程P2申请200KB的内存空间。
内存分区列表，找到第一个大小大于等于200KB的空闲分区，假设为Q3（大小为400KB）。
将分区Q3划分为两个部分：一个部分给进程P2使用，大小为200KB；另一个部分留作未分配区，大小为200KB。
更新内存分区列表，添加两个分区：分区Q3（已分配给P2）和分区Q4（未分配区，大小为200KB）。
此时内存分区列表为：Q1（100KB，已分配给P1）、Q2（100KB，未分配区）、Q3（200KB，已分配给P2）、Q4（200KB，未分配区）。
动态分区分配算法描述一、引入动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？二、首次适应算法（First Fit）算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
三、最佳适应算法（Best Fit）算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。
因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。
如何实现：空闲分区按容量递增次序链接。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。
因此这种方法会产生很多的外部碎片。
四、最坏适应算法(Worst Fit)又称最大适应算法（Largest Fit）算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。
每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
重新排序：空闲分区按容量递减次序链接缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。
如果之后有“大进程”到达，就没有内存分区可用了。
五、邻近适应算法（Next Fit）算法思想：首次适应算法每次都从链头开始查找的。
这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。
如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
动态分区分配方式的模拟实验原理说明一、引言动态分区分配方式是操作系统中的一种内存管理方式，它将内存分为若干个不同大小的分区，根据进程的需求动态地分配内存。
在实际应用中，动态分区分配方式广泛应用于多任务操作系统中，如Windows、Linux等。
本文将介绍动态分区分配方式的模拟实验原理。
二、动态分区分配方式的基本原理动态分区分配方式是指在内存空间中按照进程需要划分出若干个不同大小的空间块，每个空间块可以被一个进程占用。
当有新进程需要内存时，操作系统会在空闲的空间块中选择一个大小合适的空间块给该进程使用。
当进程结束时，该进程所占用的空间块就会被释放出来，成为空闲块。
三、模拟实验环境搭建为了模拟动态分区分配方式，我们需要搭建一个虚拟机环境。
首先需要安装一款虚拟机软件（如VMware Workstation），然后安装一个操作系统（如Windows）。
接下来，在虚拟机中安装Visual Studio等开发工具。
四、模拟实验步骤1.设计数据结构为了方便管理内存空间，我们需要设计一种数据结构来存储内存块的信息。
我们可以使用链表来实现这一功能，每个节点表示一个内存块，包括该内存块的起始地址、大小以及状态（已分配或未分配）等信息。
2.初始化内存空间在模拟实验中，我们需要初始化一段虚拟内存空间。
我们可以使用一个数组来表示整个内存空间，并将其划分为若干个大小不同的空间块。
同时，我们需要将这些空间块的信息存储到链表中。
3.模拟进程请求内存在模拟实验中，我们需要模拟多个进程同时请求内存的情况。
当一个进程请求内存时，操作系统会根据其所需的内存大小，在空闲的空间块中选择一个合适的块分配给该进程，并将该块标记为已分配状态。
4.模拟进程释放内存当一个进程结束时，它所占用的内存块就会被释放出来，成为空闲块。
此时操作系统会更新链表信息，并将该块标记为未分配状态。
5.显示当前内存使用情况在模拟实验过程中，我们需要不断地显示当前的内存使用情况。
实验五动态分区分配算法的模拟为了更好地理解动态分区分配算法的工作原理，我们可以进行一次模拟实验。
在实验中，我们将模拟一个内存分区，并使用动态分区分配算法来管理这些分区。
首先，让我们定义一个内存大小为1000字节的分区。
我们假设这个内存中包含几个已分配的分区和几个空闲的分区。
我们使用首次适应算法来进行分区的首次适应分配。
首先，我们将整个内存空间标记为空闲状态，并创建一个初始的空闲链表。
我们假设初始时只有一个空闲分区，大小为1000字节，起始地址为0。
现在，假设有一个进程请求分配一个250字节大小的内存空间。
我们首先检查空闲链表，找到一个大小大于等于250字节的空闲分区。
在这种情况下，我们发现第一个空闲分区的大小是1000字节，所以我们将它拆分成250字节的已分配分区和750字节的空闲分区。
我们在已分配分区上标记一个进程编号，并将空闲分区加入空闲链表。
接下来，假设我们的进程需要申请500字节的内存空间。
在这种情况下，我们需要查找一个大小大于等于500字节的空闲分区。
我们发现第一个可用的空闲分区大小是750字节，我们将它拆分为已分配的500字节和剩余的250字节的空闲分区。
然后，我们假设有进程释放了先前分配的250字节的内存空间。
当一个进程释放分配的内存空间时，我们需要合并相邻的空闲分区。
在这种情况下，释放的分区位于地址0，大小为250字节，并且其下一个分区是地址500，大小为500字节的空闲分区。
因此，我们将这两个分区合并为一个大小为750字节的空闲分区。
接下来，我们假设另一个进程将请求600字节的内存空间。
根据首次适应算法，我们将在第一个满足条件的空闲分区进行分配。
在这种情况下，我们将分配200字节的空闲分区和分配400字节的空闲分区拆分为600字节的已分配分区和空闲分区。
最后，假设一个进程请求200字节的内存空间。
根据首次适应算法，我们在第一个满足条件的空闲分区进行分配。
在这种情况下，我们将250字节的空闲分区拆分为200字节的已分配分区和50字节的空闲分区。
使用动态分区分配方式的模拟
1内容
（1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。
其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：•作业1申请130KB。
•作业2申请60KB。
•作业3申请100KB。
•作业2释放60KB。
•作业4申请200KB。
•作业3释放100KB。
•作业1释放130KB。
•作业5申请140KB。
•作业6申请60KB。
•作业7申请50KB。
•作业6释放60KB。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
2、示例程序：
//Tittle: 使用动态分区算法的模拟
//author: XuYongzhen
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef struct DuLNode{
struct DuLNode *prior;
struct DuLNode *next;
int address;
int jsize;
int jnumber;//显示分区被那个作业占用，显示零则为空闲分区；
}DuLNode,*DuLinkList ;
void CreatList(DuLinkList &L){
DuLinkList p=(DuLinkList)malloc(sizeof(DuLNode));
L->next=p;
L->jnumber=100;//为释放头结点后面的结点空间做统一化处理
p->prior=L;
p->next=NULL;
p->jsize=600;
p->address=0;
p->jnumber=0;
}
void RequestList(DuLinkList &L,int job,int size){
cout<<"作业"<<job<<"申请"<<size<<"KB的空间"<<endl;
DuLinkList p=L->next;
while((p->jnumber>0||p->jsize<size)&&p)
p=p->next;
if(p==NULL)
cout<<"没有适合的空间分配"<<endl;
else{
DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
s->jnumber=job;
s->jsize=size;
s->address=p->address;
p->address=p->address+s->jsize;
p->jsize=p->jsize-s->jsize;
DuLinkList t=L->next;
while(t){
if(t->jnumber==0)
cout<<"空闲分区：始址="<<t->address<<"大小="<<t->jsize<<endl;
else
cout<<"已分配的分区：作业号="<<t->jnumber<<"始址="<<t->address<<"大小="<<t->jsize<<endl;
t=t->next;
}//while
cout<<endl;
}//else
}//RequestList
void FreeList(DuLinkList &L,int job){
cout<<"作业"<<job<<"释放"<<endl;
DuLinkList p=L->next;
while(p->next&&p->jnumber!=job)
p=p->next;
if(p->prior->jnumber==0 && p->next->jnumber==0){
//p的前后都是空闲分区,则合并三者
DuLinkList s=p->next;
DuLinkList q=p->prior;
p->prior->next=p->next;
p->next->prior=p->prior;
s->prior->next=s->next;
s->next->prior=p->prior;
q->jsize=p->jsize+s->jsize+q->jsize;
}
if(p->prior->jnumber==0 && p->next->jnumber!=0){
//回收区与插入点的前一个分区相临接
DuLinkList q=p->prior;
p->prior->next=p->next;
p->next->prior=p->prior;
q->jsize=p->jsize+q->jsize;
}
if(p->prior->jnumber!=0 && p->next->jnumber==0){
//回收区与插入点的后一个分区相临接
DuLinkList q=p->next;
p->prior->next=p->next;
p->next->prior=p->prior;
q->address=p->address;
q->jsize=p->jsize+q->jsize;
}
if(p->prior->jnumber!=0 && p->next->jnumber!=0)
//回收区去插入点前后的两个空闲分区都不相临接
p->jnumber=0;
DuLinkList t=L->next;
while(t){
if(t->jnumber==0)
cout<<"空闲分区：始址="<<t->address<<"大小="<<t->jsize<<endl;
else
cout<<"已分配的分区：作业号="<<t->jnumber<<"始址="<<t->address<<"大小="<<t->jsize<<endl;
t=t->next;
}
cout<<endl;
}
void main(){
DuLinkList L=(DuLinkList)malloc(sizeof(DuLNode));
CreatList(L);
RequestList(L,1,130);
RequestList(L,2,60);
RequestList(L,3,100);
FreeList(L,2);
RequestList(L,4,200);
FreeList(L,3);
FreeList(L,1);
RequestList(L,5,140);
RequestList(L,6,60);
RequestList(L,7,50);
FreeList(L,6);
}。
