Minix Memory Management
1 Overview
Minix is divided into four layers during design, as shown in the following figure, the first and second layers are process management and I / O tasks, a core-based core, memory management (MMORY Manager, below) ) Is not part of the kernel, which is located on the third layer above the kernel, mainly processed by Fork, Exec, BRK, etc. System calls involved in memory access. It communicates between it and the kernel.
This article first introduces the most basic part of memory management: the allocation and recycling of physical memory, then describes system calls related to memory allocation, such as Fork, Exec, BRK, signal processing, etc., which will involve process management and file systems. Through this paper, everyone will have a general understanding of MINIX's memory management, and can clearly see how the executable code is loaded, and the resource is all executed.
Note: Appendix A is consistent in the line number and "operating system: design and implementation" of the program below.
2 allocation and recycling of physical memory
Memory management has a lot of strategies, such as exchange, paging, segmentation, segment form, etc., Minix's memory management is very simple: neither page is not exchanged. The Storage Manager saves a list of empty holes arranged in accordance with the memory address. When the system calls fork or exec, the system is specially used for the first adaptation algorithm to find a sufficiently large void. Once a program is loaded into the memory, it will remain in the original position until the end of the run, it will never be replaced or moved to other locations of memory, and the space assigned to it will not grow or shrink.
Physical memory management mainly includes the following functions:
1. Memory initialization: When the MM is started, it needs to initialize the memory cavity table.
2. Assign the memory of the specified size
3. Release a previously allocated memory
4. Return the size of the current maximum vacuum
The data structure of the empty list is as follows:
18820 #define nr_holes 128 / * max # entries in hole table * /
18821 #define nil_hole (struct hole *) 0
18822
18823 Private struct hole {
18824 Phys_Clicks H_Base; / * The start address of the empty hole * /
18825 Phys_Clicks H_len; / * The length of the empty pass * /
18826 struct hole * h_next; / * Pointing the next empty hole * /
18827} Hole [nr_holes];
18830 Private Struct Hole * Hole_Head; / * Pointer To First Hole * /
18831 Private struct hole * free_slots; / * ptr to list of unused Table Slots * /
The above data structure description, there are 128 items in the empty table, and each entry is connected to a linked list through the pointer.
Pointer Hole_Head points to the first hole, the meaning of free_slots will explain below
Since MM uses a very simple strategy, its data structure is also very simple, and the operation is nothing more than the traversal of the linked list, increased, delete, etc., people who have learned the "Data Structure" course should be easy to understand.
2.1 Distribution of memory
18840 Public Phys_Clicks Alloc_Mem (ClickS)
18841 Phys_Clicks ClickS; / * The size of the memory block to be assigned * /
18842 {
18843 / * Allocate a Block of Memory from the Free List Using First Fit. The Block18844 * Consists of a sequence of contrate Bytes, Whose Length in Clickses IS
18845 * Given By 'ClickS'. A Pointer to The Block is Retund. The Block IS
18846 * ALWAYS ON A Click Boundary. This Procedure Is Called When Memory IS
18847 * NEEDED for for for for for for for for for for.
18848 * /
18849
18850 Register struct hole * hp, * prev_ptr;
18851 Phys_Clicks Old_base;
18852
18853 hp = Hole_Head; / * Start traversing from the linked table * /
18854 While (hp! = Nil_hole) {
18855 IF (hp-> h_len> = clicks) {
18856 / * We Found a Hole That Is Big ENOUGH. USE IT. * /
18857 OLD_BASE = HP-> h_base; / * Remember the old base address * /
18858 hp-> h_base = clicks; / * Modify the base address of the hole * /
18859 hp-> h_len - = clicks; / * Modify the length of the hole * /
18860
18861 / * If the void is not used, return directly, Old_base is what is asked * /
18862 IF (hp-> h_len! = 0) Return (OLD_BASE);
18863
18864 / * The whole empty hole is running, put the hole in a free list * /
18865 DEL_SLOT (Prev_PTR, HP);
18866 RETURN (OLD_BASE);
18867}
18868
18869 prev_ptr = HP;
18870 hp = hp-> h_next;
18871}
18872 RETURN (No_MEM);
18873}
The code is relatively simple, start traversing from the head of the empty list, find a sufficiently size, modify the base address and length of the hole, worth noting that the del_slot function:
18926 Private void del_slot (prev_ptr, hp)
18927 Register Struct Hole * prev_ptr; / * Pointer to Hole Entry Just Ahead of 'HP' * /
18928 Register struct hole * hp; / * Pointer to Hole Entry to be removed * /
18929 {18930 / * Remove An entry from the Hole List. This Procedure IS Called WHEN A
18931 * Request to Allocate Memory Removes a hole in its entirety, thus reducing
18932 * The number of holes in memory, and requiring the elimination of one
18933 * Entry in the Hole List.
18934 * /
18935
18936 if (HP == Hole_HEAD)
18937 HOLE_HEAD = HP-> h_next;
18938 else
18939 prev_ptr-> h_next = hp-> h_next;
18940
18941 hp-> h_next = free_slots;
18942 free_slots = HP;
18943}
The meaning of this code is to remove the holes pointed to by the HP from the empty chain table, which is a basic linked list. Then add HP to the head of Free_Slots, this time you should understand the meaning of Free_slots, point to the head of a linked list, which saves a series of voids, these voidatures are: There is no space that can be assigned, Or say its h_len domain is 0, which is actually an empty data structure. Below we will also see the usage of free_slots.
2.2 Release Memory
18879 Public Void Free_MEM (Base, Clicks)
18880 Phys_Clicks Base; / * The base address of the memory block to be released * /
18881 Phys_Clicks ClickS; / * The length of the memory to be released * /
18882 {
18883 / * RETURN A Block of Free Memory To The Hole List. The Parameters Tell Where
18884 * The Block Starts in Physical Memory and How Big It Is. The Block is Added
18885 * to the Hole List. If it is contiguous with an existing hole on Either End,
18886 * It is merged with the hole or holes.
18887 * /
18888
18889 Register struct hole * hp, * new_ptr, * prev_ptr;
18890
18891 IF (ClickS == 0) Return;
18892 IF ((new_ptr = free_slots) == nil_hole) PANIC ("Hole Table Full", NO_NUM;
18893 new_ptr-> h_base = base;
18894 new_ptr-> h_len = clicks;
18895 free_slots = new_ptr-> h_next;
/ * 18891 to 18895 line: Take the first hole on the free_slots linked list, so that the base address and length is the value to be released, and remove free_slots to the next element * / 18896 hp = Hole_HEAD;
18897
18898 / * New_PTR Now points to a hole that can be reassigned, the following needs to put the empty cave referred to in New_PTR to the appropriate location of the empty list. The clearance list that needs attention is to be ranked from the base address from small to large. * /
18901
18902 if (HP == NIL_HOLE || Base <= hp-> h_base) {
18903 / * Put it directly to the head of the empty hole * /
18904 new_ptr-> h_next = HP;
18905 Hole_Head = New_PTR;
18906 MERGE (new_ptr);
18907 RETURN;
18908}
18909
18910 / * Need to find a suitable location * /
18911 While (hp! = Nil_hole&& base> hp-> h_base) {
18912 prev_ptr = HP;
18913 hp = hp-> h_next;
18914}
18915
18916 / * Insert new empty cavity after prev_ptr * /
18917 New_PTR-> h_next = prev_ptr-> h_next;
18918 prev_ptr-> h_next = new_ptr;
18919 MERGE (prev_ptr); / * sequence is 'prev_ptr', 'new_ptr', 'hp' * /
18920}
Used in the memory of the Merge function:
18949 Private void Merge (HP)
18950 Register Struct Hole * Hp; / * Ptr to Hole To Merge with ITS Successors * /
18951 {
/ * From the hole pointed from the HP, find two holes backwards, if these three voids are continuous (ie, a void's base address plus length is equal to the base site of the late hole), the three cavity merge * /
18958 Register Struct Hole * Next_ptr;
18959
18960 / * if 'hp' Points to the lasthole, no merging is possible. If it does not,
18961 * Try to Absorb ITS Success Portor IT and Free The Successor's Table Entry.
18962 * /
18963 IF ((Next_PTR = HP-> h_next) == nil_hole) Return;
18964 IF (hp-> h_base hp-> h_len == next_ptr-> h_base) {
18965 hp-> h_len = next_ptr-> h_len; / * first one gets second one's mem * / 18966 del_slot (hp, next_ptr);
Else {
18968 hp = next_ptr;
18969}
18970
18971 / * IF 'HP' Now Points To The Last Hole, Return; OtherWise, Try To Absorb ITS
18972 * Successor INTO IT.
18973 * /
18974 IF ((Next_PTR = HP-> h_next) == nil_hole) Return;
18975 IF (hp-> h_base hp-> h_len == next_ptr-> h_base) {
18976 hp-> h_len = next_ptr-> h_len;
18977 DEL_SLOT (HP, Next_PTR);
18978}
18979}
2.3 Get the size of the maximum vacuum
18985 public phys_clicks max_hole ()
18986 {
18987 / * Scan the Hole List and return the largest hole. * /
18988
18989 Register struct hole * hp;
18990 Register Phys_Clicks Max;
18991
18992 hp = Hole_HEAD;
18993 MAX = 0;
18994 While (hp! = Nil_hole) {
18995 IF (hp-> h_len> max) max = hp-> h_len;
18996 hp = hp-> h_next;
18997}
18998 RETURN (MAX);
18999}
The code is very simple, no longer explained.
2.4 Empty Initialization
19005 Public Void Mem_init (Total, Free)
19006 Phys_Clicks * Total, * Free; / * Memory Size Summaries * /
19007 {
19018 Register struct hole * hp;
19019 Phys_Clicks Base; / * Base Address of Chunk * /
19020 Phys_Clicks Size; / * Size of Chunk * /
19021 Message Mess;
19022
19023 / * first form a linked list, let free_slots point to the head, Hole_Head points to null * /
19024 for (HP = & HOLE [0]; HP <& Hole [nr_holes]; hp ) hp-> h_next = HP 1;
19025 Hole [nr_holes-1] .h_next = nil_hole; 19026 Hole_Head = NIL_HOLE;
19027 free_slots = & hole [0];
/ * The following loop constantly sends a message to the kernel, get information information of physical memory * /
19033 * free = 0;
19034 for (;;) {
19035 mess.m_type = sys_mem;
19036 IF (Sendrec (Systask, & Mess)! = OK) PANIC ("BAD SYS_MEM?", NO_NUM);
19037 Base = Mess.m1_i1;
19038 size = mess.m1_i2;
19039 IF (size == 0) Break; / * no more? * /
19040
19041 Free_MEM (Base, Size); / * Note that each release here will eventually form an empty chain table * /
19042 * Total = Mess.m1_i3;
19043 * free = size;
19044}
19045}
Explanation: Since the MM and kernel are separate, they can only communicate between them, the Me_init send a message to Systask, get a memory message, MiniX will eventually call the following functions:
15424 Private INT DO_MEM (M_PTR)
15425 Register Message * m_ptr; / * Poin REQUEST message * /
15426 {
15427 / * RETURN The base and size of the next chunk of memory. * /
15428
15429 Struct Memory * MEMP;
15430
15431 for (Memp = MEM; MEMP <& MEM [NR_MEMS]; MEMP) {
15432 m_ptr-> m1_i1 = memp-> base;
15433 m_ptr-> m1_i2 = MEMP-> SIZE;
15434 m_ptr-> m1_i3 = Tot_Mem_Size;
15435 MEMP-> SIZE = 0;
15436 IF (m_ptr-> m1_i2! = 0) Break; / * Found a chunk * /
15437}
15438 RETURN (OK);
15439}
Note: The Do_Mem function will find a single size of the 0 memory return. It writes the base address to the music m1_i1 domain, write the length to m1_i2, write the total memory size to the m1_i3 domain, so that MEM_INIT can Read.
Later we will see more code that uses messages and kernels.
