在物流产业迅猛发展的今天, 各种产品流通变得十分频繁, 在产品流通的过程中, 仓库的需求日益增多, 各种大型仓库应运而生。这种经营性仓库的出现, 极大方便了各种物品在运输过程中的临时中转问题, 对经济和社会的发展起到了积极的作用。但这种仓库的性质决定了日常的活动中, 物品入库出库频繁, 每次入库所需的空间不固定, 出库也可能分几次完成, 使得日常管理复杂。因此, 对仓库的优化管理十分必要。

在高速信息化的今天, 利用计算机来实现仓库的管理十分普及, 对仓库管理的信息化, 可把人们从繁琐的工作中解脱出来。但一般的仓库管理系统都只是把人工的操作电脑化, 有物品入库就查找有没有空余仓库, 如果有就入库, 并登记分别在哪些仓库, 把相关的信息录入到计算机中, 出库时把相应的仓库设置为空。这样只是把以前的手工登记操作改成了用计算机来完成的这样一个过程, 实质上并没有完全达到优化管理的目的。如果在业务较多, 入库出库操作频繁的情况下, 很容易使在一次入库的物品可能存放在几个不同的地方, 从而影响工作效率。本文针对这种情况, 利用动态存储原理中的首次拟合法来实现对货物入库时的仓库分配和出库时仓库的回收管理, 实现对库房资源的充分利用和优化管理。

动态存储管理的基本问题是在操作系统进行内存分配时, 在多任务系统中, 如何根据用户“请求”分配内存?当用户使用完毕后, 又如何回收“释放”的内存。在系统运行过程中, 用户申请的内存可能很大, 如要实现一个大作业, 也有可能很小, 只是一个内存变量。不管在什么样的动态存储管理系统中, 在开始时, 整个内存区都是一个“空闲块”, 随着用户的进入, 提出存储请求, 系统则根据需求进行分配, 系统运行一段时间后, 随着用户的退出, 它所占用的内存块变成“空闲块”。在系统的运行过程中, 不断有用户提出申请分配内存和用户完成退出系统回收内存, 使得整个内存区域形成了一个“占用块”和“空闲块”相互交错的状态。系统每次分配给用户的都是一个连续的内存块, 如果这时再有大作业申请, 系统就有可能在内存空闲空间足够, 但没有足够大的连续空间的情况下, 造成申请失败的情况。所以在动态存储分配中, 在用户退出时, 系统立即回收内存空间, 为了使物理空闲地址相邻的空闲块形成一个较大的结点, 如果相邻的左右块都为空闲块, 则进行合并, 把两个或三个空闲块合并成一个较大的空闲块, 以备大作业使用。动态存储管理就是在多任务的操作系统中不断实现对用户需求内存的分配与回收的过程, 尽可能满足用户的需要。

进行动态存储管理可使用不同的方法来实现, 如可利用空间表、边界表示法、伙伴系统等, 本文主要讨论可利用空间表的方法。可利用空间表来实现对内存的管理和分配, 系统刚开始工作时, 可利用空间表是一个只有一个大小为整个内存区的结点, 随着系统的运行, 空间的不断申请与回收, 可利用空间表中结点的大小和个数也随之改变。在可利用空间表中, 结点的大小不同, 就存在一个如何分配的问题, 如要申请一个大小为m的内存块, 系统中有多个空闲块都可以满足要求, 这时系统会如何进行分配呢?通常有三种分配策略:首次拟合法、最佳拟合法和最差拟合法。一般说来, 首次拟合法的分配时间最短, 能更快地实现用户的要求;最佳拟合法一般不会占用大空间, 保证大作业的申请成功;最差拟合法使可利用空间表中的结点大小均匀, 不容易出现碎片, 适用于分配范围较窄的情况。可根据实现情况选择不同的分配策略。

计算机对内存的管理采用动态存储的原理来实现, 而在现实生活的仓库管理与计算机的内存管理十分相似, 都存在不断申请和回收空间的问题。在进行仓库管理时, 可采用动态存储的原理来实现对仓库管理的优化。其基本思想是:对所有的仓库进行编号, 由于每次用户的需求空间大小不固定, 可利用首次拟合法来实现对存储空间的分配和回收。建立两个表, 一个是可用仓库表 (存储空闲的仓库信息, 按地址有序) , 一个是已用仓库表 (存储单次入库的已使用库房信息, 无需有序) 。系统运行前, 已用仓库表为空, 可用仓库表只有一个结点 (整个库房) 。系统运行时, 当有物品要求入库时, 采用首次拟合法, 在可用空间表中找到满足要求的可用空间, 把物品入库, 如果空间大小刚好满足要求, 则把整个空间大小分配给当前用户。否则把该空间分成两部分, 已用部份添加到已用空间表中, 剩余部份仍留在可用空间表中。当物品出库时, 如果一次入库的物品全部出库, 则回收空间, 把该部分空间添加到可用空间表中;如果只有部分出库, 把空间分成两部分, 一部份仍然保留在已用空间表中, 另一部分进行回收。

对存储结构的定义分为可用仓库表和已用仓库表两部份。由于入库和出库的操作会涉及到对结点的增加或删除, 采用链表的存储结构, 存储结构定义如下。

可用仓库表结构的定义 (restspace) 用头指针headrest指向, 如图1所示。

图1 可用仓库表结构  下载原图

已用仓库表结构的定义 (usedspace) 用头指针headused指向, 如图2所示。

图2 已用仓库表结构  下载原图

在这里, 仓库的基本存储空间可视存储的类型来进行定义, 可以大到一个库房, 也可以小到一个抽屉。

在开始时, 所有仓库为空, 可用仓库表中只有一个结点, BeginNum为1, EndNum为仓库的最后一个编号, Size为仓库总容量;已用仓库表为空。当货物需要入库时, 采用分配算法对其分配仓库, 当货物需要出库时, 采用回收算法进行仓库的回收。

采用首次匹配的方法来实现对仓库的分配, 具体的算法如下。

假设需要的空间大小为N, 从可用仓库表中按首次拟合法找到第一个不小于N的空闲空间, 其空间大小为M, 分配给用户, 如果M等于N, 则把这个空间加到已用仓库表中, 如果M大于N, 则从开始处把空间的前N个空间加到已用仓库表中, 修改可用仓库表, 把找到的空间块的大小Size设为:M-N, BeginNum设为BeginNum+N即可。

当货物从仓库中移出时, 进行仓库的回收。根据物品存放的信息, 找到物品存放的结点, 如果该结点的物品全部出库, 则把这段仓库从已用仓库表中删除, 插入到可用仓库表中, 否则把已用仓库表分成两部份, 把已用仓库表的该结点的大小改变, 并把剩下的部分插入到可用仓库表中。

具体算法如下:

本文采用动态存储管理的原理来实现对仓库的优化管理, 在进行仓库分配时, 采用首次拟合法来分配仓库, 并且在可用仓库表中按地址的有序进行存储, 并采用单链表来实现, 具有线性表和链表的优点, 简化了在回收空间时的合并算法。首次拟合法适用于结点大小范围较广的情况, 适用于一般仓库管理的优化。