汇编网

帐号密码


多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页首页上一页下一页尾页

算法讲堂
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。现本栏目的内容处于不断添加中，请随时关注。

算法讲堂－》首次适应算法实现【源代码】

    ;动态存储分配 Dynamic Memory Distribution Algorithm
;算法详细讲解和算法演示请参考《首次适应算法【讲解】》及《首次适应算法【演示程序说明及下载】》
;
;在系统运行初期，整个内存区基本上分割为两大部分：
;                低地址区包含若干占用块（系统占用）；
;                高地址区（即分配后的剩余部分）
;随着用户进入系统，先后提出存储请求，系统则依次进新分配。
;经过一段时间后，有的用户运行结束，它所占用的内存区变为空闲块，
;使得整个内存区呈现出大小不同或相同的占用块和空闲块交错相隔的状态。
;此时要实现存储分配，我们采取了一种策略，即用户一旦运行结束，
;便将它占用的内存区释放成为空闲块，同时，每当新的用户请求分配内存时，
;系统需要查看整个内存区中所有的空闲块，并从中找出一个合适的空闲块分配给它。
;实现这样的策略，系统需要建立一张记录所有空闲块的"可利用空间表"。

;可利用空间表：
;有目录表和链表两种实现形式，我们实现链表形式。
;链表形式的可利用空间表，表中的一个节点表示一个空闲块，
;系统每次进行回收或分配即是在可利用空间表中插入或删除一个节点。

;采取的分配方法：
;系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。
;因此可利用空间表中的节点即空闲块的大小也是随意的。
;通常，操作系统中的可利用空间表就是这样的情况。

;当可利用空间表中有若干个满足用户请求的空闲块，采取什么样的策略进行分配呢？
;
;----首次适应算法(First Fit) 支持内存合并
;
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
;可利用空间表节点定义：
;tag 状态标志 0:空闲        1:占用   1 byte
;size 块大小（字节）            2 byte
;link 相邻块首地址 SA:OA         4 byte
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
assume cs:code,ds:data

null equ 0
true equ 1
false equ 0

block_Tag_Len equ 1
block_Size_Len equ 2
block_Link_OA_Len equ 2
block_Link_SA_Len equ 2
block_Head_Len equ block_Tag_Len+block_Size_Len+block_Link_OA_Len+block_Link_SA_Len

spare_Tag equ 0
use_Tag equ 1
;-------------------------------------------------------------------------------;
;-------------------------------------------------------------------------------;
data segment
         Copyright db 'Copyright (c) 2007  www.asmedu.net','$';版权声明字符串
         use_Head_Pointer dw 0
         pointer_OA_Len equ $-use_Head_Pointer
         use_Head_Pointer_SA dw 0
         pointer_SA_Len equ $-use_Head_Pointer_SA

         spare_Head_Pointer dw 0,0

data ends
;-------------------------------------------------------------------------------;
;-------------------------------------------------------------------------------;
code segment

start:
    ;相关准备工作
    ;算法调用
    call init_System ;初始化相关参数
    mov ax,10h;为新任务申请10hbyte的内存空间，ax指示空间大小
    call allot

    mov ax,1;释放1号任务占用内存空间，ax指示任务号
    call reclaim

    call exit;退出

exit:
        call cls
        mov ax,4c00h
    int 21h

;-------------------------------------------------------------------------------
;--Arithmetic Implementation----------------------------------------------------
;--动态存储分配之首次适应算法实现-----------------------------------------------
;--1 equ success or true -------------------------------------------------------
;--0 equ failure or false-------------------------------------------------------
;-------------------------------------------------------------------------------;
init_System:;系统初始化操作成功返回 (bx) = 1,失败返回 (bx) = 0
        push ax;保存现场
        push bx
        push cx
        push dx
        push ds

        mov ax,user_Area;将头指针head_Pointer指向空闲块
        mov cx,ax
        mov dx,offset spare_Area
        mov ax,data
        mov ds,ax

        mov bx,offset use_Head_Pointer;初始化占用链表头指针
        mov word ptr [bx],null
        mov word ptr [bx+pointer_OA_Len],null

        mov bx,offset spare_Head_Pointer;初始化空闲链表头指针
        mov [bx],dx
        mov [bx+pointer_OA_Len],cx

        mov ds,cx;初始化空闲块user_Area
        mov bx,dx
        mov byte ptr [bx],spare_Tag
        mov word ptr [bx+block_Tag_Len],spare_Area_Size
        mov word ptr [bx+block_Tag_Len+block_Size_Len],null
        mov word ptr [bx+block_Tag_Len+block_Size_Len+block_Link_OA_Len],null

        pop ds;恢复现场
        pop dx
        pop cx
        pop bx
        pop ax
        ret
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
allot:;分配空间首次适应 (ax)申请空间大小 (bx) = 0申请失败 (bx) = 1 申请成功块头作为节点放入占用块链表(cx):(dx)返回分配块的首地址
        push ax
        push si
        push ds
        push es
allot_Check:;扫描可利用空间表
        mov bx,data
        mov ds,bx
        mov bx,offset spare_Head_Pointer
        mov dx,[bx]
        mov cx,[bx+pointer_OA_Len]
allot_Checks:
        mov bx,cx;检验块地址是否有效为空则返回
        add bx,dx
        cmp bx,null
        je allot_Failure
        mov ds,cx
        mov bx,dx
        push cx
        push dx
        mov dx,[bx+block_Tag_Len];block_Size
        sub dx,block_Head_Len;要把当前块的块头空间排除在外         将来分配出去的块的块头空间默认在申请块大小内
        cmp dx,ax;当前块的有效空间是否大于等于申请块
        jnb can_Allot
        pop dx
        pop cx
        mov dx,[bx+block_Tag_Len+block_Size_Len];定位下一个空闲块
        mov cx,[bx+block_Tag_Len+block_Size_Len+block_Link_OA_Len]
        jmp short allot_Checks

can_Allot:        ;把当前块的一部分分配
        pop dx
        pop cx
        mov dx,bx
        add dx,[bx+block_Tag_Len]
        sub dx,ax;(dx)新块的偏移地址 = 当前块地址(bx)+当前块大小([bx+block_Tag_Len])-申请块大小(ax)
        mov cx,ds;(cx)新块的段地址
        sub word ptr [bx+block_Tag_Len],ax;当前块大小调整;还应该判断 size 是否为 0

        mov ds,cx
        mov bx,dx
        mov word ptr [bx],use_Tag
        mov word ptr [bx+block_Tag_Len],ax;申请块大小
        push ax;保存申请块大小

        mov ax,data;将占用表表头指针作为新节点的 block_Link
        mov es,ax
        mov si,offset use_Head_Pointer
        mov ax,es:[si]
        mov word ptr [bx+block_Tag_Len+block_Size_Len],ax
        mov ax,es:[si+pointer_OA_Len]
        mov word ptr [bx+block_Tag_Len+block_Size_Len+block_Link_OA_Len],ax

        mov word ptr es:[si],dx;把节点插入到占用表中作为新表头
        mov word ptr es:[si+pointer_OA_Len],cx

        mov ds,cx;模拟使用内存空间
        mov bx,dx
        add bx,block_Head_Len
        pop cx
        sub cx,block_Head_Len
uses:
        mov byte ptr [bx],'1'
        inc bx
        loop uses

        mov bx,true
        jmp short allot_Ret

allot_Failure:
        sub bx,bx
allot_Ret:
        pop es
        pop ds
        pop si
        pop ax
        ret
;-------------------------------------------------------------------------------;
;-------------------------------------------------------------------------------;
reclaim:;回收空间由ax传入撤销任务号 (cx):(dx)->释放块块头 ;注意内存的合并问题   操作成功返回 (bx) = 1,失败返回 (bx) = 0
        push ax;保护现场
        push cx
        push dx
        push di
        push si
        push ds
        push es

        call address_Task;返回撤销任务的地址信息 (cx):(dx)
        cmp bx,false
        jne reclaim_Continue
        jmp reclaim_Failure

reclaim_Continue:
        push cx;保存块地址信息
        push dx

        mov ds,cx;清空块空间
        mov bx,dx
        mov si,bx
        add si,block_Head_Len
        mov cx,[bx+block_Tag_Len]
        sub cx,block_Head_Len;循环次数 = 当前块大小 - 块头长度
clear_Area:
        mov byte ptr [si],'0'
        inc si
        loop clear_Area;清空完毕

        pop bx
        pop ax
        push ax
        push bx
        mov di,1
        call find_Previous;找到回收块(ax):(bx)前驱(es):(si)
        cmp bx,false
        je to_Reclaim_Failure
        cmp ax,1
        je reclaim_Normal_Hit
        jmp short reclaim_Head_Hit

to_Reclaim_Failure:
        jmp before_Reclaim_Failure

reclaim_Normal_Hit:;将块从占用链表中移除（前驱非表头情况）回收块(ax):(bx)
        pop bx
        pop ax
        mov ds,ax;回收块(ds):(bx)
        mov ax,[bx+block_Tag_Len+block_Size_Len]
        mov es:[si+block_Tag_Len+block_Size_Len],ax
        mov ax,[bx+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        mov es:[si+block_Tag_Len+block_Size_Len+pointer_OA_Len],ax
        jmp into_Spare_Link
reclaim_Head_Hit:        ;将块从占用链表中移除（前驱是表头情况）
        pop bx
        pop ax
        mov ds,ax
        mov ax,[bx+block_Tag_Len+block_Size_Len]
        mov es:[si],ax
        mov ax,[bx+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        mov es:[si+pointer_OA_Len],ax
into_Spare_Link:;将块链接到可利用空间表中回收块ds:bx入链表
        mov ax,data
        mov es,ax
        mov si,offset spare_Head_Pointer
        mov ax,es:[si]
        mov [bx+block_Tag_Len+block_Size_Len],ax
        mov ax,es:[si+pointer_OA_len]
        mov [bx+block_Tag_Len+block_Size_Len+pointer_OA_Len],ax

        mov ax,bx;可利用空间表表头spare_Head_Pointer->回收块(ds):(bx)
        mov es:[si],ax
        mov ax,ds
        mov es:[si+pointer_OA_Len],ax

        mov byte ptr [bx],spare_Tag;回收块标志域(ds):(bx).tag = spares_Tag

        call combination;合并可合并的空闲块

        mov bx,true
        jmp short reclaim_Ret
before_Reclaim_Failure:;调整栈
        pop dx
        pop        cx
reclaim_Failure:;失败返回
        sub bx,bx
reclaim_Ret:
        pop es;恢复现场
        pop ds
        pop si
        pop di
        pop dx
        pop cx
        pop ax
        ret
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
address_Task:;由ax传入任务号;就是返回当前占用链表中的第(ax)个元素  返回任务的内存首地址(cx):(dx)         操作成功返回 (bx) = 1,失败返回 (bx) = 0
        push ax;保存现场
        push ds

        push ax

        mov ax,data;从占用表表头开始遍历
        mov ds,ax
        mov bx,offset use_Head_Pointer
        mov dx,[bx]
        mov cx,[bx+pointer_OA_Len]
addresss:
        mov ax,cx
        add ax,dx
        cmp ax,null
        je address_Task_Failure;到达链表尾部，说明不存在所给任务号对应的块

        pop ax
        cmp ax,0
        je address_Task_Success;每遍历一个占用块，任务号自减 1 ，当任务号减为 0 时，说明当前(cx):(dx)指向的块即为任务号对应块
        dec ax
        push ax
        mov ds,cx
        mov bx,dx
        mov dx,[bx+block_Tag_Len+block_Size_Len]
        mov cx,[bx+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        jmp short addresss;继续查看下一任务
address_Task_Success:
        mov bx,true
        jmp short address_Task_Ret
address_Task_Failure:
        pop ax
        sub bx,bx
address_Task_Ret:
        pop ds;恢复现场
        pop ax
        ret
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
combination:;内存空闲块合并
        push ax;保存现场
        push bx
        push cx
        push dx
        push si
        push ds
        push es
        mov ax,data;遍历每个节点，找到与当前节点可合并的其他节点即合并
        mov ds,ax
        mov bx,offset spare_Head_Pointer

        mov dx,[bx]
        mov cx,[bx+pointer_OA_Len]
combinations:
        mov ax,cx
        add ax,dx
        cmp ax,null
        je combination_Ret
        call find_Com_Block
        cmp bx,0
        je check_Next_Block
        call combination_Operate
        jmp short combination_Ret

check_Next_Block:
        mov ds,cx
        mov bx,dx
        mov dx,[bx+block_Tag_Len+block_Size_Len]
        mov cx,[bx+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        jmp short combinations

combination_Ret:
        pop es;恢复现场
        pop ds
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret
;-------------------------------------------------------------------------------;
;-------------------------------------------------------------------------------;
find_Com_Block:;寻找(cx):(dx)的内存地址相邻块找到由(es):(si)传回并返回(bx) = 1  ,失败返回 (bx) = 0
        push ax
        push cx
        push dx
        push ds

        mov ax,data
        mov ds,ax
        mov bx,offset spare_Head_Pointer
        mov si,[bx]
        mov es,[bx+pointer_OA_Len]
finds:
        mov ax,es
        add ax,si
        cmp ax,null
        je find_Com_Failure

        mov ax,dx
        mov ds,cx
        mov bx,dx
        add ax,[bx+block_Tag_Len]
        cmp ax,si;检验(es):(si)是(cx):(dx)的后续内存空间
        je find_Com_Success
        mov ax,si
        add ax,es:[si+block_Tag_Len]
        cmp ax,dx;检验(es):(si)是(cx):(dx)的前驱内存空间
        jne find_Com_Continue

find_Com_Success:
        mov bx,true
        jmp find_Com_Block_Ret;找到，返回
find_Com_Continue:
        mov ax,es
        mov ds,ax
        mov bx,si
        mov si,[bx+block_Tag_Len+block_Size_Len]
        mov es,[bx+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        jmp short finds
find_Com_Failure:
        sub bx,bx
find_Com_Block_Ret:
        pop ds
        pop dx
        pop cx
        pop ax
        ret
;------------------------------------------------------------------------------;
;------------------------------------------------------------------------------;
combination_Operate:;合并两个相邻块(cx):(dx)和(es):(si)  成功返回(bx) = 1  ,失败返回 (bx) = 0
        push ax
        push cx
        push dx
        push si
        push di
        push ds
        push es

        mov ax,dx
        mov ds,cx
        mov bx,dx
        add ax,[bx+block_Tag_Len]
        cmp ax,si
        je com;检验(es):(si)是(cx):(dx)的后继内存空间
        mov ax,es;交换节点信息
        mov es,cx
        mov cx,ax
        mov bx,si
        mov si,dx
        mov dx,bx
com:;(es):(si)是(cx):(dx)的后继内存空间 es:si->cx:dx，删除es:si节点，改cx:dx块大小
        mov ax,es
        mov bx,si
        push es;保存相关节点信息
        push si

        mov di,0
        call find_Previous;返回es:si 前驱 es:si
        cmp bx,false
        je to_Com_Operate_Failure
        mov di,es;;恢复相关节点信息
        mov ds,di
        mov bx,si
        pop si
        pop es;es:si 前驱 ds:bx

        cmp ax,0
        je com_Oper_Head_Hit
        jmp short com_Oper_Normal_Hit
to_Com_Operate_Failure:
        jmp short combination_Operate_Failure

com_Oper_Normal_Hit:
        mov ax,es:[si+block_Tag_Len+block_Size_Len];前驱为非头节点删除es:si节点
        mov [bx+block_Tag_Len+block_Size_Len],ax
        mov ax,es:[si+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        mov [bx+block_Tag_Len+block_Size_Len+pointer_OA_Len],ax
        jmp com_Change_Size
com_Oper_Head_Hit:;前驱是头节点删除es:si节点
        mov ax,es:[si+block_Tag_Len+block_Size_Len]
        mov [bx],ax
        mov ax,es:[si+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        mov [bx+pointer_OA_Len],ax

com_Change_Size:;改cx:dx块大小
        mov ds,cx
        mov bx,dx
        mov ax,es:[si+block_Tag_Len]
        add [bx+block_Tag_Len],ax

        mov cx,[bx+block_Tag_Len];清除空闲块中的内容皆置为 '0'
        sub cx,block_Head_Len
        mov si,bx
        add si,block_Head_Len
update_Block:
        mov byte ptr [si],'0'
        inc si
        loop update_Block

        mov bx,true
        jmp combination_Operate_Ret

combination_Operate_Failure:
        pop si
        pop es
        sub bx,bx

combination_Operate_Ret:
        pop es
        pop ds
        pop si
        pop di
        pop dx
        pop cx
        pop ax
        ret
;-------------------------------------------------------------------------------;
;-------------------------------------------------------------------------------;
find_Previous:;查找 (ax):(bx)的前驱节点由 (es):(si)返回 (ax)返回是否是头节点 (bx)返回找到与否
        push cx
        push dx
        push ds

        push ax
        push bx

        mov ax,data;遍历占用链表找到它的前驱
        mov es,ax
        cmp di,0
        je check_Spare
        mov si,offset use_Head_Pointer
        jmp short check_Ready
check_Spare:
        mov si,offset spare_Head_Pointer
check_Ready:
        mov dx,es:[si]
        mov cx,es:[si+pointer_OA_Len]
        mov ax,cx
        add ax,dx
        cmp ax,null;检验头结点是否为空，为空：链表为空，失败返回
        jne go_On_Find
to_Find_Previous_Failure:
        jmp find_Previous_Failure;负责栈的清理工作
go_On_Find:;继续头结点的检查
        pop bx
        pop ax
        push ax
        push bx
        cmp cx,ax
        jne pass
        cmp dx,bx
        jne pass
        jmp short prev_Head_Hit;头结点即是前驱结点
orientation_Prev:;定位前驱节点
        mov ax,cx
        add ax,dx
        cmp ax,null;检验结点是否为空，为空：已遍历到链表末尾节点，失败返回
        je to_Find_Previous_Failure
        pop bx
        pop ax;(ax):(bx)
        push ax
        push bx
        cmp cx,ax
        jne pass
        cmp dx,bx
        jne pass
        jmp short prev_Normal_Hit;如果找到前驱，则es:si就是前驱块的地址
pass:;将后继节点置为待检验结点
        mov es,cx
        mov si,dx
        mov dx,es:[si+block_Tag_Len+block_Size_Len]
        mov cx,es:[si+block_Tag_Len+block_Size_Len+pointer_OA_Len]
        jmp short orientation_Prev;向上跳转，继续定位前驱节点

prev_Normal_Hit:
        mov ax,1
        jmp find_Previous_Success
prev_Head_Hit:
        mov ax,0
find_Previous_Success:
        mov bx,true
        jmp find_Previous_Ret
find_Previous_Failure:
        sub bx,bx
find_Previous_Ret:
        pop dx
        pop cx
        pop ds
        pop dx
        pop cx
        ret
;--------------------------------------------------------------------------------
;----算法定义完毕----------------------------------------------------------------
;--------------------------------------------------------------------------------
code ends
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
user_Area segment;用户区内存,大小可自定义
        spare_Area db 100h dup('0')
        spare_Area_Size equ $-spare_Area
user_Area ends
;--------------------------------------------------------------------------------;
;--------------------------------------------------------------------------------;
end start

[07/10/11]

Email: asmedu@163.com