Justin3go

English

简体中文

English

简体中文

Appearance

操作系统内存分配模拟程序 ​

✨文章摘要（AI生成）

笔者在这篇博客中实现了一个操作系统内存分配的模拟程序，主要包含内存管理的基本操作和多种分配算法。首先，程序设置了内存的最大容量，并定义了空闲和已分配内存的表格。接着，作者实现了三个主要的内存分配算法：首次适应算法、循环首次适应算法和最佳/最差动态分区分配算法。这些算法通过遍历空闲内存表，寻找合适的内存块进行分配，并在进程完成后回收内存，合并相邻的空闲块以提高内存利用率。

在测试部分，笔者通过一系列分配任务演示了内存分配的过程，并展示了不同算法在内存分配中的效果。最终，程序不仅展示了内存的实时状态，还有效地模拟了操作系统在实际运行中的内存管理策略。

通用配置 ​

python
import pandas as pd

MAX_MEMORY = 2**15  # 32kb
freeTable = pd.DataFrame(columns=['start', 'size', 'status'])
busyTable = pd.DataFrame(columns=['start', 'size', 'status'])
schedule = []  # 假设等待中的进程按照 FIFO 的调度策略进行调度，这里没有记录进程 ID

freeTable = freeTable.append([{'start': 0, 'size': MAX_MEMORY, 'status': 0}])
test = [[10*2**10, 3], [2*2**10, 5], [1*2**10, 2], [12*2**10, 4], [1*2**10, 3], [25*2**10, 2], [2*2**10, 1]]

# 回收
# -->运行一个时间步[status--,减到 0 表示运行完成，空闲]
def step():
  global freeTable, busyTable, schedule
  # 批量减 1
  busyTable['status'] -= 1
  # 找出所有运行完[为 0]的进程
  finishTable = busyTable.loc[busyTable['status'] == 0]
  # 从已分配表中删除
  busyTable = busyTable.drop(busyTable[busyTable['status'] == 0].index)
  # 边添加边回收
  for index, row in finishTable.iterrows():  # 开始遍历
    print('[%s %s]开始处理' % (row['start'], row['size']), '*'*50)
    # 根据起始地址进行升序排序
    freeTable = freeTable.sort_values('start', ascending=True)
    # 找到上下相邻-->假设小的在上，这个无所谓
    upOne = freeTable.loc[freeTable['start']+freeTable['size'] == row['start']]
    downOne = freeTable.loc[row['start']+row['size'] == freeTable['start']]
    # 合并
    IsMerge = 0
    if len(upOne) != 0:
      # 直接将上面的 size 变大
      print('上相邻合并......')
      mergeIndex1 = (freeTable[freeTable['start'] == int(upOne['start'])]).index[0]
      freeTable.loc[mergeIndex1, 'size'] += row['size']
      IsMerge = 1
    if len(downOne) != 0:
      # 修改起始地址，并变大
      print('下相邻合并......')
      mergeIndex2 = (freeTable[freeTable['start'] == int(downOne['start'])]).index[0]
      freeTable.loc[mergeIndex2, 'start'] = row['start']
      freeTable.loc[mergeIndex2, 'size'] += row['size']
      IsMerge = 1
    # 如何没有合并[不相邻]就直接加入
    if not IsMerge:
      print('无上下相邻......')
      freeTable = freeTable.append([{'start': row['start'], 'size': row['size'], 'status': row['status']}])
    # 重新编号
    busyTable.reset_index(drop=True, inplace=True)   
    freeTable.reset_index(drop=True, inplace=True)

首次适应算法 ​

python
# 首次适应算法-->添加一个进程
def FirstAdapt(size, status):
  global freeTable, busyTable, schedule
  # 传入所需大小以及时间
  freeTable = freeTable.sort_values('start', ascending=True)  # 根据起始地址进行升序排序
  IsAssigned = 0  # 标志位-->是否已分配
  for index, row in freeTable.iterrows():  # 开始遍历
    # 判断是否有剩余空间可以分配
    if row['size'] >= size:
      # 记录在已分配表当中
      busyTable = busyTable.append(
          [{'start': row['start'], 'size':size, 'status':status}])
      # 更新空闲分区表
      row['start'] = row['start'] + size
      row['size'] = row['size'] - size
      IsAssigned = 1
      print("[ %s, %s ]---已经分配成功......." % (size, status))
      break
  # 重新编号
  busyTable.reset_index(drop=True, inplace=True)
  
  if not IsAssigned:
    print("[ %s, %s ]---没有空闲空间，等待中......." % (size, status))
    schedule.append([size, status])

循环首次适应 ​

和上面相比就添加一个变量记录每次的起始位置

python
startAddress = 0
# 循环首次-->添加一个进程
def LoopFirstAdapt(size, status):
  global freeTable, busyTable, schedule, startAddress
  # 传入所需大小以及时间
  freeTable = freeTable.sort_values('start', ascending=True)  # 根据起始地址进行升序排序
  IsAssigned = 0  # 标志位-->是否已分配
  for index, row in freeTable.iterrows():  # 开始遍历
    # 判断是否有剩余空间可以分配
    if row['size'] >= size:
      # 记录在已分配表当中
      busyTable = busyTable.append(
          [{'start': row['start'], 'size':size, 'status':status}])
      # 更新空闲分区表
      row['start'] = row['start'] + size
      row['size'] = row['size'] - size
      IsAssigned = 1
      print("[ %s, %s ]---已经分配成功......." % (size, status))
      break
  # 重新编号
  busyTable.reset_index(drop=True, inplace=True)
  
  if not IsAssigned:
    print("[ %s, %s ]---没有空闲空间，等待中......." % (size, status))
    schedule.append([size, status])

最佳动态分区分配 ​

以 size 进行升序排序，其余不变

python
# 首次适应算法-->添加一个进程
def FirstAdapt(size, status):
  global freeTable, busyTable, schedule
  # 传入所需大小以及时间
  freeTable = freeTable.sort_values('size', ascending=True)  # 根据大小进行升序排序
  IsAssigned = 0  # 标志位-->是否已分配
  for index, row in freeTable.iterrows():  # 开始遍历
    # 判断是否有剩余空间可以分配
    if row['size'] >= size:
      # 记录在已分配表当中
      busyTable = busyTable.append(
          [{'start': row['start'], 'size':size, 'status':status}])
      # 更新空闲分区表
      row['start'] = row['start'] + size
      row['size'] = row['size'] - size
      IsAssigned = 1
      print("[ %s, %s ]---已经分配成功......." % (size, status))
      break
  # 重新编号
  busyTable.reset_index(drop=True, inplace=True)
  
  if not IsAssigned:
    print("[ %s, %s ]---没有空闲空间，等待中......." % (size, status))
    schedule.append([size, status])

最差动态分区分配 ​

以 size 进行降序排序，其余不变

python
# 首次适应算法-->添加一个进程
def FirstAdapt(size, status):
  global freeTable, busyTable, schedule
  # 传入所需大小以及时间
  freeTable = freeTable.sort_values('size', ascending=False)  # 根据大小进行降序排序
  IsAssigned = 0  # 标志位-->是否已分配
  for index, row in freeTable.iterrows():  # 开始遍历
    # 判断是否有剩余空间可以分配
    if row['size'] >= size:
      # 记录在已分配表当中
      busyTable = busyTable.append(
          [{'start': row['start'], 'size':size, 'status':status}])
      # 更新空闲分区表
      row['start'] = row['start'] + size
      row['size'] = row['size'] - size
      IsAssigned = 1
      print("[ %s, %s ]---已经分配成功......." % (size, status))
      break
  # 重新编号
  busyTable.reset_index(drop=True, inplace=True)
  
  if not IsAssigned:
    print("[ %s, %s ]---没有空闲空间，等待中......." % (size, status))
    schedule.append([size, status])

测试 ​

分配任务 ​

python
for size, status in test:
  FirstAdapt(size, status)
[ 10240, 3 ]---已经分配成功.......
[ 2048, 5 ]---已经分配成功.......
[ 1024, 2 ]---已经分配成功.......
[ 12288, 4 ]---已经分配成功.......
[ 1024, 3 ]---已经分配成功.......
[ 25600, 2 ]---没有空闲空间，等待中.......
[ 2048, 1 ]---已经分配成功.......
python
print(schedule)
[[25600, 2]]
python
freeTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
02867240960
python
busyTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
00102403
11024020485
21228810242
313312122884
42560010243
52662420481
### CPU 运行一个时间步
python
step()
[26624 2048]开始处理 **************************************************
下相邻合并......
python
print(schedule)
[[25600, 2]]
python
busyTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
00102402
11024020484
21228810241
313312122883
42560010242
python
freeTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
02662461440

CPU 运行一个时间步 ​

python
step()
[12288 1024]开始处理 **************************************************
无上下相邻......
python
print(schedule)
[[25600, 2]]
python
busyTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
00102401
11024020483
213312122882
32560010241
python
freeTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
02662461440
11228810240
### CPU 运行一个时间步
python
step()
[0 10240]开始处理 **************************************************
无上下相邻......
[25600 1024]开始处理 **************************************************
下相邻合并......
python
print(schedule)
[[25600, 2]]
python
busyTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
01024020482
113312122881
python
freeTable
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
startsizestatus
00102400
11228810240
22560071680