��������� ������������� ���������� �������

  ����� ���� �������� ���������� ������ � ������� ����� � ����������� �� ��� ������������ ����� ����������. ����� �������, �������� ������� ����������� ������ ������� �����, �����-�� ����� ����� ������ �� ����� � ������� ������ ���.
�. ��������

��� ������������ ��������� ������ ������� �� ��������� ������ ����������� �� ����� ���������� ������. ������������ ���������, ����� �������, ������������������� ������������, ����� ������� ����������� �� ����� ���������� ���������. � �������� �����, � ��, � ������ ������� ������� �������������� ����� � ��� �� ���������� ��������� ������ � ���� ��. �� �� ������ ������� ����������� ��������� ����� ����������� ������� ����� �������� ���������, ��� ������������. ������� ��������� ����� � ���, ��� ��� ����������� ��������� ������� �������������� � � ������� ����� ��������� � ����������� ���������� �� ����� ���������� ������. ��� ������������ �� ������������� ����� ��������� ������������ ����������� ������������ �� ����������� ������ ���, ����� ������������� ������ ����� �������������� ��� �������������� ����������� ��������. ����� �������, ������������ �������������� ������ ������� ������� ����� ������� � ��������� ������� (������� ���������� � ������� ������� ������������ �������������) �������� ������� ������ �������� ��������� �������� ��������� ������, ���������� ����� ��� �����.
������ ������������������ �������� ������ � ������� �� ��� ����� �������� � ����, ��� ��� ��������� ������ ����� ������� �� ����� ���������� �������, � ������� ��������� �������� ����� ���������� ��������, ���� ���� ����� ���� ��������� ��������� ������ ������� ������ ���������. ��� ������� ���������� ������������� ������ (���. 4.3). ������ ���������� ����� ������ ������ � ������� ������������ (��� ����� ���������� ������������ ����� ���������� �����). ����� ����, ������� ���������� ������ ������� ����������� ������. ���������� ����� ����� ������ ���������� ������� ����. � �������, ������������ ���������� ��������� ������������� ������ ��� ����� � ������� ����� ������� ��� ���������� �������.
� ����������� �� �������� ������ ������������ ��������� ��������� ������ ��������� ������ ������. ��������, ��������� ����� �������� ����� ����������� ������� ��� ���������� ������������� ��������. ��� ������ ��������� ������� ����� �������������� � ������ ��������� �������� ���.
�������� ��������, ����� ����� ������������� � �������, �������� ����, � ������� ��� ����������. ��� ��������� ������ ��������� ������ � �����-��� ���������, �. �. ����������, ��������� � �������� ����������� ������� ����� ������� � ��������� �������.
�������� ����� ��������, ����� ��������� �� ������� ������ ����� ����������� �� ������ � ����� ���� ����������� ��������� �������������� ������, ����������� ������� ������ ������ � ����� ���������� ��������� �������. ��������, ������� realloc() � ������ ����������� ������� UNIX ����� ���� ������������ ������ ��� ���� ����.

���. 4.3. ������� ������������

� ����������� ������������ �������� ������ �������� ������, ����� ���
malloc/free/realloc � �, new/dispose � Pascal � �. �., ��� �������, ������������ ���������, ������������ �� �������� ����� ������: ��������� ����������� ����� ���������� ������� � ��������� ������� � ����������� �� ����� ��������� �������.
�������, ��������� ������� � ������ �� ������ �������. ���� �� ���� ������� ��������� ���������� �����, �������� ����� ��������� ���������, ������� "�������� �����" ������ ���������������� ���������� (������ 4.2).

������ 4.2. ������ ������������������ �������� ������

while(TRUE) {
void * bl = malloc(random (10)); /* ��������� ������ �� 0 �� 10 ���� */ void * �2 = malloc(random(lO)+10); � ........ �� 10 �� 20 ���� */
if(� == NULL && �2 == NULL) /* ���� ������ ��� */
break; /* ����� �� ����� */
free(b1);
void * �� = malloc(150);
/* ������ �����, ������ �� ����� �������� */

� ���������� ���������� ����� ��������� ��� ��������� ������ ����� "�������� �� �����": ����� ������ ����� ���������� ������� ����� �������� ������� ���� �������� ������� (���. 4.4)

���. 4.4. ��������� ������ ��������� ������� 4.2

� �������, ������ 4.2 ����� ������������� ��������. � �������� ���������� ����� �������� ����������� �����, � ����� ����������� ����� ��������� ���������, ��� ������� ��������� � ������������� �������� ���������� �����.
����������� ������ �������� �� ��� �������������, ��� ������� �������� ��� ����� ������, ������ ������� ������������� ������������ � ��������� �� �����. ���� �� ����������� ������� ��������� ����� 32 ������, ������� ������� ������������ ��� ������ �� �������: �� ������ ������ ����� ���������� ���� ����. �� ��� ���� �� ���������� � �������� ���������, ������� ���������� ���������� �������������: ���� ������� ����� �������� ������ �����, ������� 32 ������, � ��� ������� ����� 15 ��� 47 ����, �� 17 ���� �� ���� �������� �������� (���. 4.5).

���. 4.5. ���������� ������������

��� ������ ������ ������� ���������, ��� ������ ��� ������ ������������ �������, � ��� ������� ������ ������������ ������������ ����������. �������� ������ ������� �� �������� ������� �������������� �����. ������ ������ ��������������� � ���, ��� � ������ ����� � ������� �������� �������� ������� ���������, �. �. ��������� ������� ������ � ���������� ����� , ��� N� ���������� ���������� ������, s� ������ ������� ���������, � � ������� ������ �����. �������� ��� �������, �� ������� ��������� ��� �������� ������: ,�. �. ������ ������� ������ � ����������� ������� ������� ���������.
���� ������� ������ ����� ������� � �������� ���������, ���� ������� ������ ��������, �� ��� ����� ���� ������� ������ ������� �������� ������. ���, ���� s = , ���� ������� ���� 50% ������, ��� ������ ����������� �� ������� �������: ���� ������������� ���� ���� ������ ���������� ����������, �������� ������ ��� "����"; ���� ���� �� ���� �������, �� ��� ���� ��������� ��� ����������� �����, ���� �� ������� �������� ����� ����. ������ �������� ������ ������������ �������������� ������������� ������ �� �����, �� �� ������������ �������� ����� ������ ������� ����������� ��������.
�������� ���������� ������������� ������ ������������� ��� � 50-� ����. ����� ������������ �������� ���� �������� ��������� � [���� 2000] � ������ ������ ���������.
������ ��� ��������� ����� ������ ������������ � ��������������� ��������� ������. ������ ������ ���� ��������������� ��� ����, ����� �� ���� � ����� ������ ����� ���� ������� ����� ����. �������, ���� ��� �������� �� ���������� ����� ������������ ����� ������, �� ����� ������ ��������� ��������� ������ � ������ ��������� ��������� �� ���������� ����. ��� ������ �������� ���������� � ����� ������������ ���������������� �������. ���� ������ � ���, ��� ������ ��������� ��� ����������� ��������� ������ ��������� �� �� ������ � ������������ � �������, ������� ��� ����� ���������� ��������������� ������ ����� ���������.
����� � ������ ����� ������� ����� ���������: �� ���������� ������� ����������� (first fit) �����, �� �����, ������ �������� ����� ����� � ��������� � �������� ����������� (best fit), �, �������, �� ���������� ������ �������� �����, �������� ����������� (worst fit).
������������� ��������� worst fit ����� ����� ����� ��� � ��������� � ����������� ������ �� �������� �������. ��� ����� �������� ��������� ������ (������ ������� ������ ����, � ���� �� ������������ �����, �� � ������ �������� ����� ��������, ��� ��������� ������ ���), �� ������� �������� ��� ������������ ������: ����� ������� � ��������������� ������ ��������������� � (n), ��� n � ������ ������.
�������� ����� � ��������������� ������ ��� ���� � ����� ������� ���������� � (n + log(n)) � ���������� ����������� �� ���������� ������. ������������� ���-������ ��� �������� �������� ������� ��������� �������� � ���������� ���������, ������� ���� � ����� �� �����������. �� �������� ��������� worst fit ������������ ��� ���������� ������������ � �������� ��������, �������� � HPFS, �� �� ������ ������� �� ������������� ��� ������������� ����������� ������ ������ ����������.
���� ����� ��������� ��������������� ������. ��� ���������� �������� ����������� �� ������� ������������� ���� ������, � �� ����� ��� ������ ���������� ����� ��������� � ����� �����, � ������� ����� ������ ����� ������. ��������� ������ � ������� �� ��������� ���������� ���������� ������ � ������ ����������. (��������, �������� � ������� �����������, ����� �������������� ��������� ��� �����������.)
� ����� ������ best fit ����������� ������������ ������. �������������, ���� �� ����� ���� � �������� ������ ���������, �� ������ �������� "�����" � �������� ��� ��� ����� ��������� ����. �������, ��� � ������ best fit ������� ������ ����� "������" ����� ���������, � �� � ����� ������� ������� ���������� ������ ������, ������� ���������� ����������, ��� ��� ������������ ����� ���� ������.
� ��� ���������, ����� �� ��������� ����� ���������� ������������� ��������, ���� ���������� ���� �� ������ � ��������� best fit ����� ��������� �����������. ������ ���������� ������������� ������ ������������ �� ����� ������, � � ��� ������ ������������ ��������� first fit.
��� ������������� first fit � �������� ��������������� ������� ��������� ������������� ��������. ���� ������ ��� ������������� ������ � ������ � ���� �� �����, �� ������� �����, ������������� ����� � ������, ����� ���� ���������. ��������������, ������ ����� ����� ������������ � ������ ������, ��� �������� ������� ����� ������ (���. 4.6). ������� ������ ������ � ���� �������� ������� � ���, ����� ������������� ������ �� � ����� �����������, �� � ������. ����� ����������� � ��� ����� ������� ����� ����������� � ���������: ������ �������� ���������, � ������ ����� ���������� � ���� �����, ��� �� ������������ � ������� ���. � ��� �� ����� ����������� �������������� �����. � ���������� ������ ����� ���������� �������������� � ������� "��������������" �� ���������.

���. 4.6. ��������������

����������� ��������� ������������� ������������� ������ ������ ������ ��� ���� ������ ��������, � ������ � ����������� ��������� ������. �������������, ������, ���� �� ����� ��� ��������� ������ �� ������ ��������� � �� ����� ������� �� ��� ���� ���� � 100 ��������. �� ���� ��� ��� ����� ����������� � ������ ���� �� ������, � �� �� ����� �� ��� ���� ���������� � ��� ������ �����������.
����� ����, ���� �� ����� ���������� ����� � �����, ��� ������������ ���� ��������� ������ ��������� brkievel, �� �� �����, ������ ��������� ����� ����� � ������, ������ ��������� �������� brkievel �, ����� �������, ������� �������� ������ �������.
���������� ���� ��� ������, ��� ���, ��� �� ����� � �����, � ��� ��� ��������� ����� � ������. ����� ������, ��� ��� ����� ������ ��������. �������������, ��� ����������� ����� � �������� �� ������ ����� �� � ������ ���������, ��� �� ���������, ��� ��� �� ���. ��� ����� �� ������ ����������� ���� ������. ��� ���� �� ���� ��������� ������ ����� ��������� ����������� ����������� ������ ��������� ������ �� ������.
������� ����� ���������� � ����������� ����� ��������� �� ����������� �������� ������. ������� ������ ��� ����, �� �������� � ������, ������� ���������� ���������� ������ ����� � ������� � ���, ��� �� ��������� � ������� ����� �� ��� ����� ������. ������ �����, � �� �����. ���� � ���, ��� ��������� �������� ���������� �����, ����� ������� � ��� ������ ����� � ������ ��� ������. ������ ����� ����� �������� ������� �� �����, ������� � �����, � ������ ����� ������ ����� ������� ������. �� �86 � �������� ������ ��� �� ���, �� ��� ������ �������� �������� ���������.
����, �� ��������� � ����� ��� ����� � ���� ����� ���, ������ ����� ����. � ��� ����� �� ���������� ������ �����. ���������� ������������ ����������, ������� �������� ����. ��� ���� �� �������������, ��� �������� ���� ����� ��������������, ���� ���� ��������, � ��������������, ���� ���� �����. ����� ������� � ��������, ����� ������ ����� ��������� ��� ���������� (���. 4.7).
����������, ��� �� ����������� ���� � ������� addr. �������, ��� addr ����� ��� word *, � ��� ���������� � ���� ����� ����� �������������� ����� ����� ������������� � ������, ��� � ����� �. ��� ���� ����� ���������, �������� �� ����� ����� ���, �� ������ ���������� ����� � ������� addr 2. ���� ��� ������������, �� ����� �����, � �� ������ �������� ��� � ����� (���. 4.8). ���� �� ��� ������������, �� �� ����� ����� ���������� ����� ������ ����� ����� ��� addr - addr[-2].
��������� ����� ������ �����, �� ����� ����� ���������� ���� ���� � ������ addr, ��� ����� ������ ������� �������� �����-������������ � �������� �� � ����������� ������ �������� �����. ��� ���� �� ����� ����� ��������� ������������� ���� � ������ � ��������� ������ ��� ������!

���. 4.7. ������ �����

������� ������� �������������� � �����, ������� ����� ����. ������������ ������� ������� � ���, ��� ����� ������ ���-���� ����� ��������� �� ������ ��������� ������.
����������, ������ ����� ����� ������������� ��� ������ ���������� �������, ������������� ���� ��� ���� �� ���� ��������� ������: ���������������� ������, ����������� � ���� ��� �������, ��� � ��������� �����, � ���������������� �� ������. �������������� ������������ ������������ ��������� ������� � ���, ��� �� ����� ����������� ����� ������, ��� ������������ ������������ ������ �����, ������ � ������ �� �������� ����� � ������ ���� ��������� � ��� �������������� �����. �������������, �� � ����� ������ ����� ��������� ��� ������� ������ ������ � ��������� � ���, ��� ��� ��������� ����� ����� � ������, ��� � ��� ����� ������ ��������� �����, ��� ���� ������� � ������ �� ��������� � �. �.

���. 4.8. ����������� � �������������� ������ �����

 

����������
��� ������������� ������� ������������, ��� ��� ��� ����������� ��������� ��������� ������ ������ � �����������, � ������� � ����������� �� Zortech C/C++ �������, ��� "������� ������������, ������� ��� ����� [ ������ ������ � ����������� � ����. ���.], �������� � �������� ��� ����" ([Zortech v3.xj).

����, ��������� �� ��������� ������������� ���������� ������������� ������������� ������ �������� �������� ������ ����� � ������������ ��������� ������ � ��������������� ��������� ������ � ������� �� �������� first fit. ���� �������� ������������ ���������� ������������������ ����� ��� ���� ��������� ������������� ������, ������������ � ���������� ����������.
�������� ������ ����� ��� ��������� ��������� ������ � ������ 60-�. � ������� ������� ������������ ����� [����, 2000], ���� �������� ���������� ��� ��������� "������������ � ������������� ������". � ����������� �������� ������������ � ����� ������� ��������� ������������, �� ������ �������� ������ ���������� ����� ������� ����� �� ��������� ���' ��������� �� ������������� �����. � ���� ������, ����������� ��� ����������� ������������ ������������� ��������� ������ (� ���������, ���������� ����������� ���������� ����� �) ���������� ������� ��������� ������ �����. ������ ��������� ������� ���� ������ ����, ��� ����, ���� ��������� ���� ������������ ������ � ����������� �������.
���������� maiioc � ���������� GNU LibC (���������� ����������� ���-������ ����� � � ������ freeware ������� GNU Not Unix) (������ 4.3) ���������� ��������� ���������: ����� �������� ����� 4096 ���� ���������� ���������� first fit �� ����������� ���������� ������ � �������������� ����������� ���������, � ������������� ��� ������ ������, ������� � �������� ����� ������ ����� �� �������� ������ �����. ��� ���������� ������� ����� ����� ����� ������, ������� 4096 ������.
����� �������� ������� ������������ � ������� � ���������, ����������������� �������� ������, ��� � ��������� ����� ��������� ���������. �������� ���� �������� ���������� ����������� (���. 4.9). � ������� �� ��������� ���������, �� �� ���������� ��� ������������ ������ ���������. ������ �����, �� ��������� 4-������������ ���� �� ��������� ����������� �������. ����, ��������, ���� ��������� ������� ������� �� 514 � 296 ���� ������, �� ����� �������� ��������� � 1024 � 512 ���� ��������������. ��� ��� ��������� ����� �������� ������ ����� � 4 ���������, � ������ ��� ����� �������� �� ������ ���������. ��� ����������� �������� �� ��������� ������ �� ������� ����� �������������� ��������� ��������� ���� ������. ���� ���� �� ���� �������� ����� �����, ���� ���� ��������� �������. ����� �� ������������� ��������� ��������, ���� ������������ � ���.
��������� ������ �������� �� ������ � ������ �������, � � ��������� ������������ ������� _heapihfo. ��������� ��������� �� �� ����������� ������������������ ��������� ������, � �� ������ 4096 ���� ������ (� ������� 4.3 ������ ��� �������� ��������� ��������� BLOCKSIZE). ��������� ����� �� ����� ��������� ������ ��������� � _heapinfo, ������ �������� �� 4096 �������� �������������� ����� �� ������ ����.
��� ������������������� ������ ��������� ������ ��������� (�����-��������) � ������ ������������ �������, � �������� ����������� ����. ��������� �����, ��� � � ��������� ������ �����, �� ����� ����� ����� ������� �������������� ������� ������ � ���������� �� � ������� ����������� �������.
��� ����������������� ������ ��������� ������ ������ ���������, ������� ������� ���������� � ������ ���������. ����� ����, ��� ��������� ��������� ������ ������� ���������� � ����� ������ � ��������� ����
������� ������� � ������ _f raghead.
������������ ��������� ������ �������� ������ �����, ��� ����������� � ������������ ��������� ������ �����, �� ��������� ����� ������ ��������� ������ � ������� ����� ����� ������� ������������������. ������� o���� �����, ����������� ������������ ����������� ��� �� ������ ����������, ���������� ������� �����������, ������� � ����������� �����-�� ��������� ��������� �������� ������ ����������� �������.

���. 4.9. ��������� � ���������� malloc �� GNU LibC

������ 4.3. ���������� malloc/f��� � GNU LibC. �������__default_morecore ��������� � ������� 4.1.

malloc.�
/* �������������� ������ 'malloc'.
Copyright 1990, 1991, 1992 Free Software Foundation �������� � ��� 1989 Mike Haertel.
GNU � Library �������� ��������� ����������� ������������;
�� ������ ���������� ������ ����� �/��� �������������� �� � ������������
� ����������� GNU General Public License ������ 2 ��� (�� ������ ������) ����� ����� ������� ������.
���������� GNU � ���������������� � �������, ��� ��� ����� �������, �� ��� �����-���� ��������; ���� ��� ������ �������������� ��������
������������ �������� ��� ����������� ��� ���������� ����.
��������� ��. GNU General Public License.
�� ������ ���� �������� ����� GNU General Public License ������ �
GNU � Library; ��. ���� COPYING. ���� �� �� �� ��������, �������� �� ������: Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
� ������� ����� ��������� �� ����������� ����� �� ������ mike@ai.rait.edu, ��� Mike Haertel �/� Free Software Foundation. */
# ifndef _MALLOC_INTERNAL
#define _MALLOC_INTERNAL tinclude <malloc.h>
#endif
#ifdef __ELF_
ipragma weak malloc = __libc_malloc
#endif

/* ��� ������������� �������� �������������� ������. */
__ptr_t (*__morecore) __� ((ptrdiff_t __size))
= __default_morecore_init;
/* ��������������� ������������� ���������� ������� (hook) ��� xmalloc' */
void (*__malloc_initialize_hook) __P ((void));
__ptr_t (*_malloc_hook) __P ((size_t __size)) ;
/* ��������� �� ��������� ������� �����. */ char *_heapbase;
* ������� �������������� ������� � ������. �����������
����� align/__free (�� malloc/free). */
malloc_info *_heapinfo;
/* ���������� �������������� �������. */ static size_t heapsize;
/* ������ ������ � �������������� �������. */ size_t _heapindex;
/* ������������ ���������� �������� � �������������� ������� */ size_t _heaplimit;
#if 1 /* Adapted from Mike */
/* ������� ������� ������, ����������� ��� ������� �� ��������
����������. */
int _fragblocks[BLOCKLOG];
#endif
/* ������ ��������� ���������� �� ��������.
*/ struct list _fraghead[BLOCKLOG];
/* ���������������� ����������.
*/ size_t __chunks_used; size_t _bytes_used; size_t _chunks_free; size_t _bytes_free;
/* ����� �� �� ����? */
/* Are you experienced? */
int malloc initialized;
/* ����������� ����������. */
static __ptr_t align __P ((size_t));
static __ptr_t
align (size)
size_t size; {
__ptr_t result;
unsigned long int adj;
[result = (*__morecore) (size);
adj = (unsigned long int) ((unsigned long int) ((char *) result -
(char *) NULL)) % BLOCKSIZE; lit (adj != 0)
{
adj = BLOCKSIZE - adj; (void) (*_morecore) (adj); result = (char *) result + adj;
}
return result;
/* ��������� ��� � ���������, ��� � ��� ����. */
/* Set everything up and remember that we have.
*/ static int initialize _ P ( (void) ) ; static int initialize ()
{ if ( malloc initialize hook)
(*__malloc_initialize_hook) ();
heaps ize = HEAP / BLOCKSIZE;
_heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info) ) ;
if (_heapinfo == NULL)
return 0;
memset (_heapinfo, 0, heapsize * sizeof (malloc_info) ) ; _heapinfo [0] . f ree. size = 0;
_heapinfo[0] .free. next = _heapinfo[0] . free.prev = 0; _heapindex = 0;
_heapbase = (char *) _heapinfo; __malloc_initialized = 1; return 1;
/* �������� ����������� ������, �������������
��� ��������� ������� ���������� ���� �� ���� �������������. static _ ptr_t morecore _ P ( (size_t) ) ; static _ ptr_t ,�������� (size)
size_t size;
_ ptr_t result;
malloc_info *newinfo, *oldinfo;
size_t newsize;
result = align (size) ; if (result == NULL) return NULL;
/* ���������, ����� �� ��� ��������� ������� ����������. */ if ((size_t) BLOCK ((char *) result + size) > heapsize) I
newsize = heapsize;
while ( (size_t) BLOCK ((char *) result + size) > newsize)
newsize *= 2;
newinfo = (malloc_info *) align (newsize * sizeof (malloc_info) ) if (newinfo == NULL) {
(* _ morecore) (-size); return NULL; }
memset (newinfo, 0, newsize * sizeof (malloc_info) ) ; memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info) ) ; oldinfo = _heapinfo;
newinfo[BLOCK (oldinfo) ] .busy. type = 0; newinfo [BLOCK (oldinfo) ] .busy. info. size
= BLOCKIFY (heapsize * sizeof (malloc_info) ) ; _heapinfo = newinfo; _free_internal (oldinfo) ; heapsize = newsize;
_heaplimit = BLOCK ((char *) result + size) ; return result; I
/* �������� ������ �� ����. */ ptr t
����� 4. ���������� �����������
libcjnalloc (size) size_t size;
I
ptr_t result;
size t block, blocks, lastblocks, start; register size_t i; struct list *next;
/* ��������� ��������� �������� malloc (0) . �� ��� ���������. */
lif �
if (size == 0)
return NULL; #endif
if (! malloc initialized) if ( '.initialize () ) return NULL;
if ( _ malloc_hook != NULL)
return (*__malloc_hook) (size) ;
if (size < sizeof (struct list) ) size = sizeof (struct list) ;
/* ���������� �������� ���������� �� ��������� ������� �������. */ if (size <= BLOCKSIZE / 2) {
/* ��������� ������� �������� �������� �����.
���������� �������� �������� ������� ���������.
*/ register size_t log = 1; � size; while ( (size /= 2) != 0)
/* ����������� ������ ���������� �� ������� ����������
��������� ��������� �������. */ next = _f raghead[ log] .next; if (next != NULL)
I
�������� � ������������ �������
/* ������� ��������� ��������� ����� �������.
���������� �������� �� ������ ���������� � ������� ���. �������� �������� ����� nfree � first.
*/ result = ( _ ptr_t) next; next->prev->next = next->next; if (next->next != NULL)
next->next->prev = next->prev; block = BLOCK (result); if
( � _heapinf � [block] .busy. info. frag. nfree != 0)
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) next->next � (char *) NULL) % BLOCKSIZE) � log;
/* �������� ����������. */
++_chunks_used;
_bytes_used += 1 � log;
--_chunks_f ree ;
_bytes_free -= 1 � log; t
else
/* ��� ��������� ���������� ��������� �������. ������� ����� ����� ����; �������� ��� �� ��������� � ������� ������. */ result = _ libc_malloc (BLOCKSIZE) ; if (result == NULL)
return NULL; #if 1 /* Adapted from Mike */
++_fragblocks [log] ; #endif
/* ������� ��� ���������, ����� �������, � ������ ���������. */ for (i = 1; i < (size_t) (BLOCKSIZE � log); ++i) I
next = (struct list *) ((char *) result + (i � log)); next->next = _fraghead[log] .next; next->prev = &_fraghead[log] ; next->prev->next = next; if (next->next != NULL) next->next->prev = next;
}
/* ���������������� �������� nfree � first ��� ����� �����. */ block = BLOCK (result); _heapinf�[block].busy.type = log;
_heapinf�[block].busy.info.frag.nfree = i � I; heapinfo[block].busy.info.frag.first = i � 1;
_chunks_free += (BLOCKSIZE � log) - 1;
_bytes_free += BLOCKSIZE - (1 � log); _bytes_used -= BLOCKSIZE - (1 � log);
} else
{
/* ������� ������� �������� ���� ��� ������ ������.
����������� ������ ��������� ����������, ������� � �����, ��� �� ���� � ��������� ���. ���� �� ������� ������ ����, �� ��������� ���������� �������� �����, �� ������ ����� ��������� ��� ������ � �������. */
blocks = BLOCKIFY (size);
start = block = _heapindex;
while (_heapinf�[block].free.size < blocks)
block = _heapinf�[block].free.next; if (block == start)
/* ���������� ����� ������ [������] � �������.
���������, �� ����� �� ����� ������ ������������ ���������� ���������� �����; ���� ��� ���, ��� �� ���� ����� ����������� ��� �����.
*/ block = _heapinfo[0].free.prev; lastblocks = _heapinf�[block].free.size; if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
(*__morecore) (0) == ADDRESS (block + lastblocks) &&
(morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL)
tif 1
/* Adapted from Mike */ �
�������� ��������, ��� morecore() ����� ��������
� ������� � ������������ �������
��������� ���������� �����, ���� ��� ���������� ������� ������������ � ������ ����� ������� ��������� � ��������� ������. */ block = _heapinfo[0].free.prev;
_heapinf�[block].free.size += blocks � lastblocks; #else
_heapinf�[block].free.size = blocks; tendif
_bytes_free += (blocks - lastblocks) * BLOCKSIZE; continue; }
result = raorecore (blocks * BLOCKSIZE); if (result == NULL)
return NULL; block = BLOCK (result);
_heapinf�[block].busy.type = 0; _heapinfo[block].busy.info.size = blocks;
++ chunks used;

_bytes_used += blocks * BLOCKSIZE; return result;
/* � ���� ����� �� [��� ��� �����] ����� ���������� ������ � ������ ���������. ������, ��� ������� ��, ��� ��� �����, �� ������. */ result = ADDRESS (block); if (_heapinf�[block].free.size > blocks) {
/* ����, ������� �� �����, ����� ��������� �������,
��� ��� ������������ ��� ������ ����� � ������ ���������. */ _heapinf�[block + blocks].free.size
= _heapinfo[block].free.size - blocks; _heapinfo[block + blocks].free.next
= _heapinf�[block].free.next; _heapinfo[block + blocks].free.prev
= _heapinf�[block].free.prev;
_heapinfo[_heapinfo[block].free.prev].free.next = _heapinfo[_heapinfo[block].free.next].free.prev
= _heapindex = block + blocks
else
I^H
/* ���� ����� ������������� ������ �������, �������
������ ������� ��� �� ������. */ _heapinfo[_heapinfo[block] .free. next] .free.prev
= _heapinf � [block] . free.prev; _heapinfo[_heapinfo[block] .free.prev] .free. next
= _heapindex = _heapinf � [block] . free. next; � chunksf ree ;
_heapinf � [block] .busy. type = 0;
_heapinf � [block] .busy . info. size = blocks;
++_chunks_used;
_bytes_used += blocks * BLOCKSIZE;
_bytes_free -= blocks * BLOCKSIZE;
return result;
free. c:
/* ���������� ���� ������, ���������� "malloc1.
Copyright 1990, 1991, 1992 Free Software Foundation �������� � ��� 1989 Mike Haertel.
GNU � Library �������� ��������� ����������� ������������; �� ������ ������������������ �� �/��� �������������� �� � ������������ � ����������� GNU General Public License ������ 2 ��� (�� ������ ������) ����� ����� ������� ������.
���������� GNU � ���������������� � �������, ��� ��� ����� �������, �� ��� �����-���� ��������; ���� ��� ������ �������������� ��������
������������ �������� ��� ����������� ��� ���������� ����.
��������� ��. GNU General Public License.
� ������� ����� ��������� �� ����������� ����� �� ������ mike@ai.mit.edu, ��� Mike Haertel �/� Free Software Foundation. */
#ifndef _MALLOC_INTERNAL #define _MALLOC_INTERNAL tinclude <malloc.h> tendif
#ifdef __ELF_
tpragma weak free = __libc_free
#endif
/^��������������� ������������� ���������� ������� (hook) ��� 4free'. */ void (*__free_hook) __P ((__ptr_t __ptr));
/* ������ ������, ���������� memalign. */ struct alignlist *_aligned_blocks = NULL;
/* ������� ������ � ����. ���������� 'free' �� �� ��������
__free_hook ���� ���� �� ���������. */
void _free_internal (ptr)
__ptr_t ptr;
{
int type;
size_t block, blocks;
register size_t i;
struct list *prev, *next;
block = BLOCK (ptr);
type = _heapinf�[block].busy.type; switch (type) { case 0:
/* ������� ��� ����� ������ ���������� ��� ����� ������. */ � chunks used;
-I�----
_bytes_used -= heapinfo [block] .busy. info. size * BLOCKSIZE; bytes_free += heapinfo [block] .busy. info. size * BLOCKSIZE;
/* ����� ��������� �������, �������������� ����� � ������ ��������� .
������ ����� � ���������� �����, � �������� ���� ���������. ��� ����� ���� ������������� ��� ��������, � ������� ��������� ���������. */ i = _heapindex; if (i > block)
while (i > block)
i = _heapinfo[i) . free.prev; else { do
i = __heapinfo[i] . free. next; while (i > 0 && i < block) ; i = _heapinfo [i] . free.prev; 1
/* ����������, ��� �������� ���� ���� � ������ ���������. */
if (block == i + _heapinfo[i] . free. size) {
/* ����� ���� ���� � ��� ����������������. */ _heapinfo[i] .free. size += _heapinfo [block] .busy. info. size/block = i;
else
/* ������������� �������� ���� ���� � ������ ���������. */
_heapinf � [block] . free. size = _heapinfo [block] .busy. info. size;
_heapinf � [block] .free. next = _heapinfo[i] . free. next;
_heapinf � [block] . free.prev = i;
_heapinfo[i] .free. next = block;
_heapinf � [_heapinfo [block] .free. next] .free.prev = block;
++chunksfree;
/* ������, ��������� ���� �������, ���������, �� ����� �� ��
����� ��� � ��� �������������� (�������� ��� ������������� �� ������ � ��������� �������) . */
if (block + _heapinf � [block] . free. size == heapinfo [block] .free. next)
{ _heapinfo [block] .free. size
+= _heapinfo [_heapinfo [block] .free. next] . free. size; _heapinfo [block] .free. next
= _heapinfo[_heapinfo[block] .free. next] . free. next ; _heapinf � [_heapinfo[block] .free. next] .free. prev = block; � chunksf ree ;
/* ���������, �� ����� �� �� ������� ������ �������. */
blocks = _heapinf � [block] .free. size;
if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
&& (*_morecore) (0) == ADDRESS (block + .blocks)) {
register size_t bytes = blocks * BLOCKSIZE; _heaplimit -= blocks;
(*__morecore) (-bytes); _heapinf � [_heapinf � [block] .free. prev] .free. next
= _heapinf � [block] . free. next; _heapinfo[_heapinfo[block] .free. next] .free. prev
= _heapinf � [block] . free. prev; block = _heapinf � [block] . free. prev; � _chunks_f ree ; _bytes_free -= bytes;
/* ���������� ��������� �����, ���������� � ����� �����. */
_heapindex = block; break;
default:
/* ������� ��������� ����������. */
�_chunks_used; _bytes_used -= 1 � type; ++_chunks_free; bytes_free += 1 � type;
/* �������� ����� ������� ���������� ��������� � ���� �����.
*/ prev = (struct list *) ((char *) ADDRESS (block) +
(_heapinfo[block].busy.info.frag.first � type));
#if 1 /* Adapted from Mike */
if (_heapinf�[block].busy.info.frag.nfree == (BLOCKSIZE � type) - 1
&& _fragblocks[type] > 1) #else
if (_heapinf�[block].busy.info.frag.nfree == (BLOCKSIZE � type) - 1)
#endif
lif 1 #endii
/* ���� ��� ��������� ����� ����� ��������, ������� �� �� ������ ���������� � ���������� ������ ����. */ /* Adapted from Mike */
� _f ragblocks [type] ;
next = prev;
for (i = 1; i < (size_t) (BLOCKSIZE � type)
next = next->next; prev->prev->next = next; if (next != NULL)
next->prev = prev->prev; _heapinf � [block] .busy. type = 0; _heapinf � [block] .busy . info. size = 1;
/* ������ �� ��������� ����������.
*/ ++_chunks_used; _bytes_used += BLOCKSIZE; _chunks_free -= BLOCKSIZE � type; _bytes_free -= BLOCKSIZE;
libc free (ADDRESS (block));
I
else if ( heapinf�[block].busy.info.frag.nfree != 0)

/* ���� ��������� ��������� ����� ����� ��������, �������� ���� �������� � ������ ���������� ����� ������� ���������� ��������� ����� �����. */
next = (struct list *) ptr;
next->next = prev->next;
next->prev = prev;
prev->next = next;
if (next->next != NULL) next->next->prev = next;
++_heapinf�[block].busy.info.frag.nfree;
else
/* � ���� ����� ��� ��������� ����������, ������� �������� ���� �������� � ������ ���������� � ������������, ��� ��� ������ ��������� �������� � ���� �����. */
prev = (struct list *) ptr;
_heapinfo [block] .busy. info. frag. nfree = 1;
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) ptr - (char *) NULL) % BLOCKSIZE � type) ; prev->next = _fraghead[type] .next; prev->prev = &_fraghead[type] ; prev->prev->next = prev; if (prev->next != NULL)
prev->next->prev = prev;
break;
/* ������� ������ � ����. */ void
_ libc_free (ptr) _ ptr_t ptr; {
register struct alignlist *1;
if (ptr == NULL) return;
for (1 = _aligned_blocks; 1 != NULL; 1 = l->next) if (l->aligned == ptr)
{
l->aligned = NULL;
/* �������� ������� ������ ��� ���������. */
ptr = l->exact;
break;
if ( _ free_hook != NULL) (* _ free_hook) (ptr) ;
else
_free_internal (ptr) ;
#include <gnu-stabs . h>
#ifdef elf_alias
elf_alias (free, cfree) ;
#endif

� �������� ����������� ����� ��������� ��������� ������������� ������ ������� ������ ����������� �����, ��� ������ ��� ������������ ��� ����� ��������� �������. ��� ���� ����� ��������� ��������, ������� �������� �� ������������� (����������, ���������) ����� ���� ����� ���������� ���� ������, ���� ���� ������������ ����� � ���, ��� ����������� ����� �� ����������.
����� ����� ������ ��� ������, ���� ��� ��������� ����� ���������� ������������� �������� (���. 4.10). �� ���������� ����� ������� ������� � ���� ������. ���� � ������ ������ ���������� ������� ������ ���, �� ������� � ������ ������ �������� �������. ���� ��� ���-�� ����, �� ��������� ���� ���� �� �����, ���� ������ ������������� ���������, � ������... ������, ���� ������� ��������� ������ �� ������ ���� �����, ��� �� ����� ������ � ��������?
��� ������� ���� �������� ��� ���������� ������ �����-���� ����������� �� ������� ���������� ������. ��������, ����� �����������, ����� ��� ������� ��������� ������ ��������� (������������������ ����� �����, � ������� Fi+1 = Fi + Fi-1. � ���� ������, ���� ��� ����� Fi ����, � � ������� ���� ������ ���� ������� Fi+1, �� ����� ����� �������� ��� ����� � ���� ���������� �������, � ������ � Fi-1, ������� ���� �� ��������. ��, ����� ����������� �� ������ �������� � ���������� ������������, �� ��� �� ������ ��� ����� �� ��������������� ����� ������ �����?

���. 4.10. ��������� ������ ������������� ��������

�� ��������, ����� ��������� �� ������������. ����� �� ������, ��-��������, �������� ������������� ��������� ���������� ������ Fi, ������� �� ������ ���������� ������� �����. ������ ������� � ��������� ����������� ��������� ������ �� �������� �������� � ���� �������� �������. ���� ������� ���������� ����� ��������, ������� ������������ ���������������� ������� ������ ����� ������� ������������ � ��������� ����� 2: 512 ����, 1 �����, 2 ����� � �. �. ����� ��������� ���������� ���������� ��������� (���. 4.11).
���� �� ����������� ����� ������ ������� � �������� ����������� ������ ��� �� ������������. ����� �����-�������� ���������� ������� ��������������� ���������������� ���� � ������ ������ �����. ����� ������ ���������, �������� �� ���� �������. ���� �� ��������, �� �� ���������� ������� � ���� ����� �������� �������, � �. �. ���� � ��������� ������ ����� ������ �� ��������� � (log(Smax)-log(Smin)), ��� Smax � Smin ����������, ��������������, ������������ � ����������� ������� ������������ ������. ��� ������ �������� ��������� ������ ��������� ��� ��������, � ������� ���������� ��������������� ����� ������� � ��������, ���
����� ��������� �������. ����� ���� �������� ��� ��� �������� ������������ ��� ��������� ������ ������ ���� ��.

���. 4.11. �������� ���������

���������� � ����� ������� �������� ���������� ���������� ���� �������. ��������, ��� ��������� ������ Novell Netware ������� �� 4 �������� � ����� 16 ���� (��� ������ ��������� 16, 32, 48, 64 �����), 3 �������� � ����� 64 ����� (��� ������ ��������� 128, 192, 256 ����) � ���������� �������� � ����� 256 ���� (�� 512 ���� �� 4 �����). ��� �������� �������� ������� ���������� ������� ��������. ���������, ��� ����������� ������ � ������ ��������� �������, �������� ���� ���������� ���������, � Netware ����������� �� ������������.
��������, ���� ������� �������� ���������� ��� ��������� ���������� ������ ������ ������������, ��� � ���� ��� ��������� ������� ��� ��� ������, �� �� �������� �������� ����� ����� ����������� ����������. ������ �����, ������� ������ ���������� ��������� ������, ���� ���������� ������� ���������� �������. ��������� ��������� ������� ������ �� ���������� ����� �������� � ������ ��� ���������� �� ���������� ������ �� ��������� �������� ������� �������� �������� ����� �����.
�������� ������ � ���������������� ������ ����� ���������� ��������, �� ���� ���������, ��� ��� �������� ������ �� ���� �������� � ������ ������� ������ �������, �������� ����� ������ ��-�� ���������������� �����. ������� ��� ������� ��������� �������� ������ ��������������� �������� ��������� ������� � ������ �� ������, ������ �� ��������� ��� ������ �� ���� �������. � ������ �������, � �������� ��������� ������� ������������� ������, ������� �� ��� ����� �� � ��������� ������� � ����������, � �������� ����� ������������, ���� � �� ������ ���������� ���������.