赵晓萍的操作系统课程设计
我们都任务是模拟一种可重定位分区的内存分配器，需要实现这些功能：
-
可重定位分区的内存分配算法
-
对内存占用情况可视化
-
静态重定位和动态重定位的过程
-
紧凑功能。
在实现具体功能之前，让我们讨论一个典型的内存分配器需要完成的工作，并理解我们即将实现的几个算法的具体细节。
内存动态分区是一种典型的现代操作系统内存管理技术。它将系统内存划分为多个不同大小的分区，以便在运行时分配给进程使用。各种分配算法可以用来决定如何将这些分区分配给不同的进程。
在课堂中，我接触了最常见的这几种算法：首次适应算法（First Fit）、最佳适应算法（Best Fit）、最坏适应算法（Worst Fit）、下次适应算法（Next Fit）。这些分配算法各有优缺点，选择哪种算法取决于系统的需求和性能目标。
同时，内存碎片管理是一个重要的考虑因素，因为它可以影响系统的性能和内存利用率。一些系统可能会使用混合算法，根据不同情况选择合适的分配策略。此外，还有其他高级的内存管理技术，如虚拟内存和分页/分段，用于更有效地管理内存资源。在本次课程设计中，我们会通过紧凑技术来减少内存碎片并提供更大空间。
可重定位分区分配是一种内存管理技术，它允许进程在内存中被加载到不同的位置，而无需重新编写或重新链接程序。这种技术使得多个进程可以并发执行，并在不同的内存位置上加载，以便更好地利用内存资源。
有两种主要的可重定位分区分配方式：动态重定位和静态重定位。我们本次课程设计会同时实现这两种方式，并比较他们的差异。用一句话概括说，这两者之间的主要区别在于重定位的时机和方式：动态重定位的重定位发生在运行时，静态重定位的重定位发生在编译时（链接时）。
"紧凑"技术可以帮助我们在内存中有效地利用可用分区空间，并减少内存碎片，从而提高内存利用率。
当内存中的分区分配和释放导致空闲分区分散在内存中时，常常会出现外部碎片问题。紧凑操作的目的是通过将已分配的分区移到一起，以便形成一个或多个大的连续空闲分区，以容纳新的进程。
当执行紧凑操作时，系统会将已分配的分区向内移动，以填充分散的空隙，从而创建更大的连续空闲空间。这就是紧凑技术的过程。
在理解了这些核心理念之后，我们就可以开始我们的系统设计了。
- 可视化模块
在这里我们通过 Tkinter 绘制一个内存页面占用图。
该模块运行在主线程，并且会每隔 100ms 抓取一次内存分配器和进程的数据，并刷新主界面。
- 内存管理器模块
这个模块会模拟固定大小的内存页面，运行内存分配算法，并对外提供三个接口：分配内存、回收内存、占用查询接口。
这是我们主要的内存调度过程的地方。我们将会在此处实现动态分配技术、紧缩算法。
- 执行器模块
该模块会提供给内存管理器一个具体的内存操作序列。具体地说，它以一个特定的顺序，让内存调度器给特定进程分配内存、回收内存，并触发紧缩。我们就是用它来输入测试样例。
同时，执行器也会切换动态和静态分配模式，输出日志，并把算法的内在过程可视化。
我们选用 Python 作为编程语言，使用 Tkinter 库进行可视化。这是为了提高开发效率，也能比较方便的快速实现我们的具体算法。另外，Python 灵活的列表结构也方便了我们模拟内存的占用情况。
先介绍一下两种重定向算法的实现思路
动态重定位是在程序运行时进行的，而不是在程序加载到内存之前。程序在运行前不知道自己即将分配的真实地址。
具体做法是：在运行时刻，为每一个进程在运行开始的时候分配一个基地址（Base Address），然后将程序中的地址引用（例如，跳转指令或变量引用）与该基地址相加，来得到实际操作的内存地址。这个过程发生在运行时。
而在静态重定位中，程序提前被编辑器或链接器修改，以使其内部地址引用已经包括了实际的内存地址。程序在运行前就知道自己即将分配的真实地址。
和上文相同，每一个进程在初始化的时刻被分配一个基地址（Base Address），然后将程序中的地址引用（例如，跳转指令或变量引用）与该基地址相加，来得到实际操作的内存地址。这个过程发生在编译时刻。
理解了以上理念之后，我们可以开始设计我们的具体系统了。
在 Tkinter 图形库中，没有可用的控件让我们展示内存占用情况。所幸，Tkinter 暴露了相对底层一些的接口 Canvas，允许我们手动绘制矩形，并对其中的内容上色。
期望的结果如下：
图 1 内存可视化效果
具体地，构建类 MemoryTable，实现最关键的部分 Canvas 绘制使用了如下代码
page_width = 800 // self.num_pages
# Create memory page rectangles and store references
for i in range(self.num_pages):
x1 = i * page_width
x2 = (i + 1) * page_width
y1 = 0
y2 = 0 + 40
rectangle =
self.canvas.create_rectangle(x1, y1, x2, y2,
fill="white", outline="black")
self.page_rectangles.append(rectangle)代码 1 Canvas 绘图操作
我们需要准备两种序列：一个是静态重定位的操作序列，以及一个动态重定位的操作序列。
静态重定位操作序列和动态重定位操作序列的区别是：动态操作序列的指令内容不需要包含内存具体位置，分配位置在运行过程中动态决定；而静态重定位的操作序列已经包含了具体分配的位置，它是提前被计算好的。
而无论如何，一个序列内包含若干个顺序的操作，每一种操作可以是
-
新建进程并给其分配内存
-
销毁进程并回收内存
-
执行紧凑操作
具体地，可以看我们的例子：
("allocate", "Process A", 3),
("allocate", "Process B", 4),
("allocate", "Process C", 2),
("free", "Process B"),
("compact",),
("allocate", "Process D", 2),
("free", "Process A"),
("compact",),
("allocate", "Process E", 3),
("free", "Process C"),
("compact",),
("free", "Process D"),
("compact",),
("free", "Process E"),
("compact",),代码 2 操作序列样例
其中，每一个操作是一个 Python 元组，包含操作类型、进程名字和内存数量。
上面的样例是一个静态重定位的操作序列，我们可以通过一个简单的算法来提前计算静态的分配位置：假设所有内存不释放，给内存区域顺序地分配进程，我们就得到了每个进程的偏移位置。
以下给出具体的计算偏移的代码：
def calculate_static_sequence(self):
current_index = 0
self.static_hard_sequence.clear()
for action in self.action_sequence:
if action[0] == "allocate":
self.static_hard_sequence.append(
("hard_allocate", action[1], current_index, action[2]))
current_index += action[2]
elif action[0] == "free":
self.static_hard_sequence.append(("free", action[1]))
elif action[0] == "compact":
self.static_hard_sequence.append(("compact",))代码 3 计算静态重定向偏移
这样，我们准备好了操作序列，用于操作内存控制器。
这部分是最核心的内容，我们的内存分配器要实现分配、回收和查询三大接口。
首先，实现。它需要做这些事情：
在内存中查找足够大的空闲内存块以容纳指定大小的进程。存储了找到的空闲内存块的起始地址。
检查是否找到了足够大的空闲内存块。如果没有找到，则抛出异常，表示内存已满。
将进程名称（process_name）与内存地址（addr）和进程大小（size）关联起来，将这些信息存储在 memory_mapping 字典中，以便跟踪哪个进程占用了哪些内存。 将进程名称与颜色关联起来，以标识进程。列表中轮流选择颜色。 将分配的内存块填充为进程名称，以标识该内存块已被分配给哪个进程。
而给静态重定向使用的函数简单很多，它会强制给对应位置分配内存，而不必寻找可用位置，因为在运行前就计算好了。除此之外，它和动态重定向的分配函数没有区别。 释放函数更为简单，由于内存控制器自己已经记录了进程和空间的映射关系，所以可以直接用进程名释放对应的内存区域。 另外，我们需要输出染色的进程列表，不同的进程占用的内存段落会被染上不同的颜色用于渲染。我们准备一个颜色列表并迭代即可。
def get_colored_list(self):
res = [] # 返回染色进程列表
for status in self.memory:
if status is not None and status not in res:
res.append(self.color_mapping[status])
elif status is None:
res.append("white")
return res代码 4 内存占用染色
最后，我们要实现一个紧凑算法，用于整理内存碎片。
它的思路也特别简单：清理干净内存，并顺序地从大到小重新分配内存。这样我们就消灭了内存碎片。
def do_compact(self): # get all memory mapping, sort by address # then erase all memory # allocate them again
sorted_mapping = sorted(
self.memory_mapping.items(), key=lambda x: x[1][0])
cp = self.memory_mapping.copy()
for process_name, process_mapping in cp.items():
self.free(process_name)
for process_name, process_mapping in sorted_mapping:
self.allocate(process_name, process_mapping[1])代码 5 紧凑算法实现
至此，核心的内存控制器已经完成。
在我们的模拟系统中，有两个任务在并发执行。第一个是可视化窗口的主线程，第二个是执行操作序列的上下文任务。可视化窗口每隔 100ms 会主动从内存控制器中获得最新数据，而操作序列在另一个线程里一直顺序执行。
在整个系统中，无论是窗口、上下文还是内存控制器，都有且只有一个实例。因此，很容易想到，只要把每个类都做成线程安全的单例，我们就可以保证三个过程之间安全的相互调用。
单例模式是一种提供全局唯一访问点的一种设计模式。线程安全的单例模式通过简单的互斥锁来保证安全。
我们对现有类型进行直接改造，只需要让所有的类继承 SingletonMeta 即可：
class SingletonMeta(type):
_instances = {}
_lock: Lock = Lock()
def __call__(cls, *args, **kwargs):
with cls._lock:
if cls not in cls._instances:
instance = super().__call__(*args, **kwargs)
cls._instances[cls] = instance
return cls._instances[cls]代码 5 线程安全的单例元
最后，我们在入口点创建新的线程即可让任务并发运行。
以下提供部分截图，完整执行过程请参考文档末附件视频。
图 2 启动时选择模式
图 3 内存可视化样例
我们在这次可视化中可以看到两种分配模式的优劣。
动态重定位允许多个进程加载到内存的不同位置，因此它更灵活，但需要在每次内存访问时执行地址计算，因此可能会稍微减慢程序的执行速度。
静态重定位的主要好处是程序在运行时不需要执行额外的地址计算，因为地址已经在程序中静态地确定。这使得程序的执行速度更快。
总的来说，动态重定位提供了更大的灵活性，允许多个进程在内存中加载到不同的位置，但可能会增加运行时的开销。静态重定位在运行时更加高效，但限制了多个进程在内存中的位置。
在这次课程设计中，我们深刻理解了几种内存分配的机制。
通过手动实现可重定位分区的内存分配算法，并且对内存占用情况可视化，我们分析了静态重定位和动态重定位的过程，认识到了两者的主要区别。
同时，我们实现了紧凑功能，认识到了内存碎片的产生，并学习了一种处理内存碎片的办法。