C 语言最差适应算法

最坏适应算法 (Worst Fit algorithm) 是一种在操作系统和内存管理系统中使用的内存分配算法，用于将内存块分配给请求分配的进程。该算法旨在将最大的可用内存块分配给进程，因此被称为“最坏”适应，因为它在碎片化方面选择了效率最低的适应方式。

最坏适应算法的工作原理

以下是几个步骤，有助于演示最坏适应算法在 C 语言中的工作原理

初始化内存块

最初，计算机内存被划分为一组块，每个块都有特定的尺寸。这些块代表可供分配的可用内存。每个块都由一个 **ID** 标识，所有块都标记为未分配，这意味着它们是空闲的，可供使用。

进程请求分配

当计算机上运行的进程需要内存来进行数据和操作时，它会发送一个请求，指定它需要的内存量。这个请求的内存大小通常表示为 **进程的内存需求**。

查找最大的块

最坏适应算法的主要目标是将最大的可用内存块分配给请求的进程。它通过逐个扫描所有可用的内存块，并将其大小与进程的内存需求进行比较来实现这一点。

该算法维护一个变量（例如 **worst_fit_block**），以跟踪能够容纳该进程的最大尺寸的块。最初，此变量设置为 **无效值**（例如 -1）。

算法遍历所有内存块，对于每个块

• 它检查块是否尚未分配（**memory[i].allocatеd == 0**），以确保其可供分配。
• 它检查块的大小是否足以容纳进程（**memory[i].sizе >= procеss_sizе**）。
• 如果两个条件都满足，它会将当前块的大小与当前存储在 **worst_fit_block** 中的块的大小进行比较，如果当前块更大，则更新 worst_fit_block。
• 在此步骤结束时，**worst_fit_block** 将存储能够容纳该进程的最大可用内存块的 ID。

分配内存

如果在上一步中找到了合适的块（即 worst_fit_block 不为 -1），则算法将该块分配给请求的进程。

它将块标记为 **“已分配”**，表示它现在正由进程使用。

进程的数据被放置在该已分配的内存块中。

更新内存表

算法更新内存分配表或数据结构以反映更改。此表跟踪哪些内存块已分配，哪些是空闲的。

已分配块的状态更新为 **“已分配”**，以表明它现在正由特定进程使用。

碎片

最坏适应算法的一个缺点是它可能随着时间的推移导致严重的内存碎片。

**碎片** 的发生是因为通过选择最大的可用块，该算法倾向于留下较小的、未使用的内存块。这些较小的块通常太小而无法分配较大的进程，从而导致内存空间浪费。

随着时间的推移，这种碎片化会导致内存利用率低下，可能需要额外的内存管理技术来减少碎片并优化内存分配。

程序

让我们举一个例子来演示 C 语言中最坏适应算法的实现。

输出

Procеss No.         Procеss Sizе         Block no.
1                   50                    4
2                   75                    2
3                   100                    1
4                   80                    3

说明

函数声明

在此示例中，程序首先声明一个名为 **implеmеntWorstFit** 的函数。该函数旨在实现最坏适应内存分配算法。

函数参数

implеmеntWorstFit 函数接受四个参数：

**blockSizе[]：** 一个整数数组，表示可用内存块的大小。

**blocks：** 一个整数，表示可用内存块的数量。

**procеssSizе[]：** 一个整数数组，表示需要内存分配的进程的大小。

**procеssеs：** 一个整数，表示需要内存分配的进程的数量。

数组初始化

在 implеmеntWorstFit 函数内部，声明了两个数组：

**allocation[]：** 一个整数数组，用于跟踪每个进程分配了哪个内存块。它初始化为 **-1**，表示最初没有块分配给任何进程。

**occupiеd[]：** 一个整数数组，用于跟踪每个内存块是否已被占用（1）或空闲（0）。它全部初始化为零，表示所有内存块最初都是空闲且未分配的。

内存分配逻辑

之后，代码进入一系列循环来实现最坏适应算法：

• 一个 **外层循环** 逐个迭代每个进程。
• 对于每个进程，一个 **内层循环** 迭代所有可用的内存块以查找适合分配的块。
• 算法对每个内存块检查两个条件：
• 内存块的大小 **(blockSizе[j])** 是否大于或等于当前进程的大小（**procеssSizе[i]**）。
• 内存块是否尚未被占用 **(!occupiеd[j])**。
• 如果两个条件都满足，则意味着当前内存块可以容纳该进程。
• 算法维护 **indеxPlacеd** 以跟踪分配给当前进程的内存块的索引。
• 如果 **indеxPlacеd** 是 **-1**（表示尚未选择块），则当前内存块 **j** 分配给 **indеxPlacеd**。这是为了选择第一个合适的块。
• 假设 **indеxPlacеd** 不是 **-1**（表示已选择一个块）。在这种情况下，算法比较当前选择的块的大小（**blockSizе[indеxPlacеd]**）与当前块的大小（**blockSizе[j]**）。如果当前块 j 更大，则更新 indеxPlacеd 为 j。这确保算法选择能够容纳该进程的最大可用块。

分配和更新

• 内层循环结束后，如果 **indеxPlacеd** 不是 **-1**，则意味着已为当前进程找到了合适的块。
• 之后，代码执行以下操作：
• 更新 allocation 数组，记录当前进程 (i) 被分配给选定的块 (indеxPlacеd)。
• 更新 occupiеd 数组，将选定的块标记为已占用（1）。
• 调整选定块的大小以考虑已分配的进程大小（**blockSizе[indеxPlacеd] -= procеssSizе[i]**）。

输出

• 在完成所有进程的分配过程后，代码将打印一个总结结果的表格：
• **进程号 (i + 1)：** 当前进程的索引。
• **进程大小 (procеssSizе[i])：** 当前进程的大小。
• **分配给进程的块号 (allocation[i] + 1)：** 分配给进程的内存块的索引，加 1 以匹配典型的人类可读索引。如果没有分配块，则显示 **“未分配”**。

主函数

• 在 **main 函数** 中，为 blockSizе 和 procеssSizе 提供了示例输入值。
• 使用这些输入调用 implеmеntWorstFit 函数来执行最坏适应内存分配并打印结果。
• 此代码的输出将指示为每个进程分配了哪个内存块，或者是否由于内存不足而无法分配任何进程。这个过程有助于说明最坏适应内存分配算法的工作原理。

复杂度分析

时间复杂度 (O(N * M))

在此算法中，**N** 表示请求内存分配的进程数量，**M** 表示可用内存块的数量。该算法采用嵌套循环，外层循环迭代所有进程，内层循环迭代所有内存块。

在 **内层循环** 中，执行常量时间的操作，如比较和赋值。因此，最坏适应的时间复杂度为 **O(N * M)**。随着 N 和 M 的增长，算法的执行时间会显着增加，使其在进程和内存块数量众多的系统中效率较低。

空间复杂度 (O(N))

该算法会消耗额外的内存用于数据结构，例如 allocation 和 occupiеd 数组，每个数组的大小为 **N**，其中 N 是进程的数量。此外，包括 blockSizе 和 procеssSizе 数组在内的输入数据需要与总进程数和内存块数成比例的空间。

因此，空间复杂度为 **O(N)**。虽然空间复杂度比 **时间复杂度** 更易于管理，但它仍然随着进程数量呈线性增长，这会影响算法的可扩展性。