计算机与信息工程系实验报告
班级 计算机1001 姓名 李双贺 时间 2011.11.09 地点 A504
实验名称 存储器管理——动态分区的分配与回收
实验目的
目的是在学习操作系统理论知识的基础上，对操作系统整体的一个模拟。研究计算机操作系统的基本原理和算法，掌握操作系统的存储器管理的首次适应算法、循环首次适应算法、最佳适应算法的基本原理和算法。提高运用操作系统知识和解决实际问题的能力；并且锻炼自己的编程能力、创新能力以及开发软件的能力。使学生掌握基本的原理和方法，最后达到对完整系统的理解。
实验内容
内存调度策略可采用首次适应算法、循环首次适应算法和最佳适应法等，并对各种算法进行性能比较。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。
实验结果
存储管理动态分区分配及回收算法
介绍
存储管理是操作系统中一个重要的功能模块，负责管理计算机的内存资源。本文将详细探讨存储管理中的动态分区分配及回收算法。
动态分区分配
动态分区分配算法是指根据进程的内存需求，在内存中动态地创建分区，并将进程加载到相应的分区中。下面是几种常见的动态分区分配算法。
1. 首次适应算法
首次适应算法是最简单、最直观的动态分区分配算法。它从内存的起始位置开始搜索，找到第一个能满足进程需求的分区即可。具体步骤如下：
1. 初始化内存的空闲分区表，记录内存中每个空闲分区的起始地址和长度。
2. 当一个进程需要分配内存时，遍历空闲分区表，找到第一个大小能满足进程需求的分区。
3. 如果找到了合适的分区，将进程加载到该分区，并更新空闲分区表。
4. 如果没有找到合适的分区，则提示内存不足。
首次适应算法的优点是简单、快速，但可能会导致碎片问题。
2. 最佳适应算法
最佳适应算法是指选择与进程需求最接近的、且大小大于等于进程需求的分区。具体步骤如下：
1. 初始化内存的空闲分区表。
2. 当一个进程需要分配内存时，遍历空闲分区表，找到满足进程需求的最小分区。
3. 如果找到了合适的分区，将进程加载到该分区，并更新空闲分区表。
4. 如果没有找到合适的分区，则提示内存不足。
最佳适应算法能最大程度地减少碎片问题，但执行效率较低。 3. 最差适应算法
最差适应算法是指选择与进程需求最接近的、且大小大于等于进程需求的最大分区。具体步骤如下：
1. 初始化内存的空闲分区表。
2. 当一个进程需要分配内存时，遍历空闲分区表，找到满足进程需求的最大分区。
3. 如果找到了合适的分区，将进程加载到该分区，并更新空闲分区表。
4. 如果没有找到合适的分区，则提示内存不足。
最差适应算法能最大程度地降低内存碎片，但执行效率相对较低。
4. 快速适应算法
快速适应算法是一种基于空闲分区表大小的快速搜索算法。具体步骤如下：
第1章 绪论
内容提要：
◆ 数据结构研究的内容。
针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。
数据结构涵盖的内容：
◆ 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
数据——所有能被计算机识别、存储和处理的符号的集合。
数据元素——是数据的基本单位，具有完整确定的实际意义。
数据对象——具有相同性质的数据元素的集合，是数据的一个子集。
数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：
Data_Structure=（D, R）
数据类型——是一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，
它由基本的数据类型构成。
◆ 算法的定义及五个特征。
算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输
出的计算步骤。
算法的基本特性：输入、输出、有穷性、确定性、可行性
◆ 算法设计要求。
①正确性、②可读性、③健壮性、④效率与低存储量需求
◆ 算法分析。
时间复杂度、空间复杂度、稳定性
学习重点：
◆ 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运
算） 。
◆ 用计算语句频度来估算算法的时间复杂度。
关注公众号【大学资料宝典】，获取大学各科期末复习资料+海量网课资源
第二章 线性表
内容提要：
◆线性表的逻辑结构定义，对线性表定义的操作。
线性表的定义：用数据元素的有限序列表示
◆线性表的存储结构：顺序存储结构和链式存储结构。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一
定相邻。通过指针来实现！
◆线性表的操作在两种存储结构中的实现。
数据结构的基本运算：修改、插入、删除、查找、排序
1)修改——通过数组的下标便可访问某个特定元素并修改之。
数据结构
线性数据结构部分：
⼀、填空题1. 数据结构包括数据的逻辑结构、 数据的储存结构 和数据的运算三个⽅⾯。
2. 数据结构包括 逻辑结构 、数据的存储结构和数据的运算三个⽅⾯。
3. 在算法“正确”的前提下，评价算法主要有两个指标是：时间复杂度和 空间复杂度 。
4. 在算法“正确”的前提下，衡量算法效率的主要指标是： 时间复杂度 及空间复杂度。
5. 线性数据结构的逻辑特征是有且仅有⼀个 开始结点 和⼀个终端结点，且所有结点都最多只有⼀个直接前趋和⼀个 直接后继。6. 线性数据结构的逻辑特征是有且仅有⼀个开始结点和⼀个终端结点，且所有结点都最多只有⼀个 直接前趋 和⼀个直接后继。7. 数据的存储结构包含有 顺序存储结构 、 链式存储结构 、 索引存储结构 和 散列存储结构 等四种基本的映像⽅法。
8. 数据存储结构的四种基本形式是： 顺序 存储结构、 链式 存储结构、索引存储结构以及散列存储结构。
9. 若频繁地对线性表进⾏插⼊与删除操作，该线性表应采⽤ 链式 存储结构。
10. 线性链表中数据元素的组成：⼀是数据元素的值，⼆是直接后继元素的 地址的指针 ，这两部分信息组成数据元素的存储映像，即结点。11. 带头结点的单向链表L为空的判定条件是 L->next==null 。
12. 在⼀个单链表中p所指结点之后插⼊s所指结点时,应执⾏s->next= p->next 和p->next= s 的操作。
13. 要在⼀个单链表中p所指结点之后插⼊⼀个⼦链表，⼦链表第⼀个结点的地址为s，⼦链表最后⼀个结点的地址为t, 则应执⾏操作：t->next=p->next 和 p->next=s 。
14. 单链表的结点的数据类型是：
typedef struct node{
int data; /*数据部分*/
struct node *next；/*指向下⼀个结点的指针*/
} LinkList;
LinkList *p, *q;
