请介绍一种程序的空间分配的方法

其基本思想是将内存划分成若干固定大小的分区，每个分区中最多只能装入一个作业。当作业申请内存时，系统按一定的算法为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，造成存储空间浪费。

1、空间的分配与回收

系统设置一张“分区分配表”来描述各分区的使用情况，登记的内容应包括：分区号、起始地址、长度和占用标志。其中占用标志为“0”时，表示目前该分区空闲；否则登记占用作业名（或作业号）。有了“分区分配表”，空间分配与回收工作是比较简单的。

2、地址转换和存储保护

固定分区管理可以采用静态重定位方式进行地址映射。

为了实现存储保护，处理器设置了一对“下限寄存器”和“上限寄存器”。当一个已经被装入主存储器的作业能够得到处理器运行时，进程调度应记录当前运行作业所在的分区号，且把该分区的下限地址和上限地址分别送入下限寄存器和上限寄存器中。处理器执行该作业的指令时必须核对其要访问的绝对地址是否越界。

3、多作业队列的固定分区管理

为避免小作业被分配到大的分区中造成空间的浪费，可采用多作业队列的方法。即系统按分区数设置多个作业队列，将作业按其大小排到不同的队列中，一个队列对应某一个分区，以提高内存利用率。

二、可变分区存储管理

可变分区存储管理不是预先将内存划分分区，而是在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等。这种处理方式使内存分配有较大的灵活性，也提高了内存利用率。但是随着对内存不断地分配、释放 *** 作会引起存储碎片的产生。

1、空间的分配与回收

采用可变分区存储管理，系统中的分区个数与分区的大小都在不断地变化，系统利用“空闲区表”来管理内存中的空闲分区，其中登记空闲区的起始地址、长度和状态。当有作业要进入内存时，在“空闲区表”中查找状态为“未分配”且长度大于或等于作业的空闲分区分配给作业，并做适当调整；当一个作业运行完成时，应将该作业占用的空间作为空闲区归还给系统。

可以采用首先适应纯纳算法、最佳（优）适应算法和最坏适应算法三种分配策略之一进行内存分配。

2、地址转换和存储保护

可变分区存储管理一般采用动态重定位的方式，为实现地址重定位和存储保护，系统设置相启裤宴应的硬件：基址/限长寄存器（或上界/下界寄存器）、加法器、比较线路等。

基址寄存器用来存放程序在内存的起始地址，限长寄存器用来存放程序的长度。处理机在执行时，用程序中的相对地址加上基址寄存器中的基地址，形成一个绝对地址，并将相对地址与限长寄存器进行计算比较，检查是否发生地址越界。

3、存储碎片与程序的移动

所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，无法再利用悄银。如果内存中碎片很多，将会造成严重的存储资源浪费。解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（紧凑技术）。移动技术除了可解决碎片问题还使内存中的作业进行扩充。显然，移动带来系统开销加大，并且当一个作业如果正与外设进行I/O时，该作业是无法移动的。

/*

请设计程序解决“波松分酒问题”

问题如下：

某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，

仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？

抽象分析:

b = 大容器,也表示容积

s = 小差销容器,也表示容积

(f),(h),(e) 状态f=满, e=空空庆衡, h=数字,表示容量

运算一: b(f) - s(e) => b(b - s), s(f)

变例b(h) - s(e) => b(h - s), s(f)

运算二: b(e) + s(f) => b(s), s(e)

变例b(h) + s(f) => b(f), s(s - b + h)

引出b(f) - s(h)

b(h) - s(h)

b(e) + s(h)

b(h) + s(h)

如果以瓶中酒的数量为节点, 通过一次以上运算可达到节点之间认为连斗做通.

此题可转化为一个有向图的搜索问题.

即找出.指定节点(12, 0, 0) 和 (6, 6, 0)之间的最小路径.

*/

#include <cstdio>

#include <deque>

#include <map>

#include <utility>

#include <queue>

static int big_max_value[] =

{

12, 8, 12

}

static int small_max_value[] =

{

8, 5, 5

}

static const int big_offset[] =

{

0, 1, 0

}

static const int small_offset[] =

{

1, 2, 2

}

//节点定义

class Node

{

unsigned char mBig

unsigned char mMid

unsigned char mSmall

public:

static void InitMaxValue(int max1, int max2, int max3)

{

big_max_value[0] = max1

big_max_value[1] = max2

big_max_value[2] = max1

small_max_value[0] = max2

small_max_value[1] = max3

small_max_value[2] = max3

}

Node() : mBig(0), mMid(0), mSmall(0)

{

}

Node(unsigned char a, unsigned char b, unsigned char c) : mBig(a), mMid(b), mSmall(c)

{

}

enum OPCODE

{

BIG_OP_MIDDLE = 0,

MIDDLE_OP_SMALL,

BIG_OP_SMALL,

OP_LAST

}

//减运算

void sub(OPCODE op)

{

int big_max = big_max_value[op]

int small_max = small_max_value[op]

char&big = *(reinterpret_cast<char*>(this) + big_offset[op])

char&small = *(reinterpret_cast<char*>(this) + small_offset[op])

if (big >(small_max - small))

{

big -= (small_max - small)

small = small_max

}

else

{

small += big

big = 0

}

}

//加运算

void add(OPCODE op)

{

int big_max = big_max_value[op]

int small_max = small_max_value[op]

char&big = *(reinterpret_cast<char*>(this) + big_offset[op])

char&small = *(reinterpret_cast<char*>(this) + small_offset[op])

if (small >big_max - big)

{

small -= big_max - big

big = big_max

}

else

{

big += small

small = 0

}

}

bool check(int value)

{

if (mBig == value || mMid == value || mSmall == value)

{

return true

}

return false

}

void print() const

{

printf("status [%d]=%2d, [%d]=%2d, [%d]=%2dn", big_max_value[0], mBig, big_max_value[1], mMid,

small_max_value[2], mSmall)

}

//相等性判定

friend bool operator==(Node const &a, Node const &b)

{

return memcmp(&a, &b, sizeof(Node)) == 0

}

friend bool operator <(Node const &a, Node const &b)

{

return memcmp(&a, &b, sizeof(Node)) <0

}

}

template <class T>

void Search(T start, int value)

{

typedef std::pair<T, T>NodeValueType

typedef std::map<T, T>NodeSet

typedef NodeSet::iterator NodeSetIter

typedef std::queue<NodeValueType, std::deque<NodeValueType>>NodeQueue

NodeSet visited

NodeQueue searchQueue

NodeValueType last

searchQueue.push(std::make_pair(start, start))

while (!searchQueue.empty())

{

NodeValueType cur = searchQueue.front()

searchQueue.pop()

visited.insert(cur)

if (cur.first.check(value))

{

last = cur

break

}

for (int i = 0i <Node::OP_LASTi++)

{

Node next1 = cur.first

next1.sub(static_cast<Node::OPCODE>(i))

if (visited.find(next1) == visited.end())

{

searchQueue.push(std::make_pair(next1, cur.first))

}

Node next2 = cur.first

next2.add(static_cast<Node::OPCODE>(i))

if (visited.find(next2) == visited.end())

{

searchQueue.push(std::make_pair(next2, cur.first))

}

}

}

NodeSetIter cur = visited.find(last.first)

while (!(cur->first == start))

{

cur->first.print()

cur = visited.find(cur->second)

}

cur->first.print()

}

int main()

{

puts("某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，n"

"仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？n")

for (int i = 0i <12i++)

{

printf("---查找取得%d品脱的最少步骤,逆序------------n", i)

Search(Node(12, 0, 0), i)

}

puts("再解一个由13品脱啤酒，却一个9品脱和一个5品脱的容器n")

Node::InitMaxValue(13, 9, 5)

for (int i = 0i <12i++)

{

printf("---查找取得%d品脱的最少步骤,逆序------------n", i)

Search(Node(13, 0, 0), i)

}

return 0

}

实际上的最后一步,结果应是(6,6,0)但事实上我只做到出现一个6的情况.原因是并非所有结果都有两个相同的值.以下是我做出来的12,8,5的最优解法:

某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，

仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？

---查找取得0品脱的最少步骤,逆序------------

status [12]=12, [8]= 0, [5]= 0

---查找取得1品脱的最少步骤,逆序------------

status [12]= 1, [8]= 8, [5]= 3

status [12]= 9, [8]= 0, [5]= 3

status [12]= 9, [8]= 3, [5]= 0

status [12]= 4, [8]= 3, [5]= 5

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

---查找取得2品脱的最少步骤,逆序------------

status [12]= 2, [8]= 5, [5]= 5

status [12]= 7, [8]= 5, [5]= 0

status [12]= 7, [8]= 0, [5]= 5

status [12]=12, [8]= 0, [5]= 0

---查找取得3品脱的最少步骤,逆序------------

status [12]= 4, [8]= 3, [5]= 5

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

---查找取得4品脱的最少步骤,逆序------------

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

---查找取得5品脱的最少步骤,逆序------------

status [12]= 7, [8]= 0, [5]= 5

status [12]=12, [8]= 0, [5]= 0

---查找取得6品脱的最少步骤,逆序------------

status [12]= 1, [8]= 6, [5]= 5

status [12]= 1, [8]= 8, [5]= 3

status [12]= 9, [8]= 0, [5]= 3

status [12]= 9, [8]= 3, [5]= 0

status [12]= 4, [8]= 3, [5]= 5

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

---查找取得7品脱的最少步骤,逆序------------

status [12]= 7, [8]= 0, [5]= 5

status [12]=12, [8]= 0, [5]= 0

---查找取得8品脱的最少步骤,逆序------------

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

---查找取得9品脱的最少步骤,逆序------------

status [12]= 9, [8]= 3, [5]= 0

status [12]= 4, [8]= 3, [5]= 5

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

---查找取得10品脱的最少步骤,逆序------------

status [12]=10, [8]= 2, [5]= 0

status [12]= 5, [8]= 2, [5]= 5

status [12]= 5, [8]= 7, [5]= 0

status [12]= 0, [8]= 7, [5]= 5

status [12]= 7, [8]= 0, [5]= 5

status [12]=12, [8]= 0, [5]= 0

---查找取得11品脱的最少步骤,逆序------------

status [12]=11, [8]= 0, [5]= 1

status [12]= 3, [8]= 8, [5]= 1

status [12]= 3, [8]= 4, [5]= 5

status [12]= 8, [8]= 4, [5]= 0

status [12]= 8, [8]= 0, [5]= 4

status [12]= 0, [8]= 8, [5]= 4

status [12]= 4, [8]= 8, [5]= 0

status [12]=12, [8]= 0, [5]= 0

注意这个解法通用性很强,还可以解其它的组合:如最后的13,9,5.