Summer is in school, every day I have some mathematics and foreign languages, I can't get the time written. It happens to have the kernel code analysis of Leon's UNIX version 6, considering that the school has never trained our "reading comprehension code" course, it will decide to read. At this time, I found this code as a verse, simple and beautiful. Don't bear exclusive, I don't know if you have time to distinguish the "poetry" of this line. I want to look at or take it out. It is not difficult to understand the algorithm, and learn together with you.
This time, let's take a look at some of the content of the operating system store management.
Memory space When assigned to the process, there are several algorithms to allocate space for newly created or researched processes. Of course, we assume that the storage management program knows the memory to be assigned.
The simplest algorithm is first adapted to fit the algorithm. The storage manager searches along the memory segment list until the first enough free area is found unless the size of the idle area is like the size of the space to be allocated, otherwise it is divided into two parts, and part is assigned to the process, The other part is still an unallocated area.
Next FIT is a small change in the first adaptation algorithm. Its work mode is the same as the first adaptation algorithm. Different, each time you find a suitable idle area, you record the position at the time, start searching from the last place, and does not start from the beginning.
There are several algorithms that are common. One is the best fit algorithm, which finds the smallest free area that happens to be used. Of course, if you find a largest free area, it is another algorithm. Also, it is a Quick Fit that sets a separate linked list to the idle area of those commonly used.
I remember that when learning the operating system, the eyes are staring behind the algorithms. What should I use in the actual operating system? Now understand, the algorithm is practical, simple and efficient is best.
We look at the UNIX kernel code, huh, take a look at the actual operating system algorithm implementation.
as follows:
/ * percy description:
* This file is malloc.c, the main process is Malloc and MFree,
* Manage storage resources.
* Orchestration mode Follow Leon's UNIX version 6 kernel source code arrangement method,
* Is the original 2500 row to 2599 lines.
* The editor is a VS.NET built-in editor.
* 2003/8/15
* /
#
/ *
* /
/ *
* Structrue of the coremap and swapmap
* Arrays.consists of non-Zero Count
* And Base Address of That Many
* Contiuous Units.
* (The Coremap Unit IS 64 BYTES,
* The swapmap unit is 512 bytes)
* The Addresses Are Increasing and
* The list is terminated with the
* First Zero Count.
* /
Struct Map
{
Char * m_size;
Char * m_addr;
}
/ * ----------------------------- * /
/ *
* Allocate Size Units from the Siven
* map.return the base of the allocate
* Space.
* Algorithm is first Fit.
* /
Malloc (MP, SIZE)
Struct Map * MP;
{
Register int A;
Register struct map * bp;
For (BP = MP; BP-> M_SIZE; BP ) {
IF (bp-> m_size> = size) {
A = bp-> m_addr;
BP-> m_addr = size;
IF ((bp-> m_size = - size) == 0)
Do {
BP ;
(bp-1) -> m_addr = bp-> m_addr;
} while ((bp-1) -> m_size = bp-> m_size);
Return (a);
}
}
Return (0);
}
/ * ----------------------------- * /
/ *
* Free the Previously Allocated Space AA
* of size units INTO The Specified Map.
* Sort aa Into Both Map and Combine ON
* One or Both Ends if Possible.
* /
Mfree (MP, SIZE, AA)
Struct Map * MP;
{
Register struct map * bp;
Register Int T;
Register int A;
a = aa;
For (bp = mp; bp-> m_addr <= a && bp-> m_size! = 0; bp );
IF (BP> MP && (BP-1) -> M_ADDR (BP-1) -> m_size == a) {
(bp-1) -> m_size = size;
IF (a size == bp-> m_addr) {
(bp-1) -> m_size = bp-> m_size;
While (bp-> m_size) {
BP ;
(bp-1) -> m_addr = bp-> m_addr;
(bp-1) -> m_size = bp-> m_size;
}
}
} else {
IF (a size == bp-> m_addr && bp-> m_size) {
BP-> m_addr = - size;
BP-> m_size = size;
} else if (size) do {
T = bp-> m_addr;
BP-> m_addr = a;
A = T;
T = bp-> m_size;
BP-> M_SIZE = SIZE;
BP ;
} while (size = t);
}
}
/ * ----------------------------------- * /
We have two processes, this time you look at Malloc, let's take a look, this is the implementation of the algorithm.
For (BP = MP; BP-> M_SIZE; BP ) {
IF (bp-> m_size> = size) {
A = bp-> m_addr;
BP-> m_addr = size;
/ * ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---- * // * If it is not 0 this here, it is not 0 ... * /
IF ((bp-> m_size = - size) == 0)
Do {
BP ;
(bp-1) -> m_addr = bp-> m_addr;
} while ((bp-1) -> m_size = bp-> m_size);
/ * ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---- * /
Return (a);
}
}
Return (0);
If it is not 0 there, it means that the idle area found is larger than the space to be allocated, which may be this in memory:
Then execute:
A = bp-> m_addr;
BP-> m_addr = size; / * In fact, this sentence, in the IF judgment, you don't forget * / bp-> m_size = - size; return (a);
If the idle area is as big as the space to be assigned, it is a bit trouble, because the MP linked list will need you to finish, the situation in the memory may be as follows:
Look at the action (do-while):
IF ((bp-> m_size = - size) == 0)
Do {
BP ;
(bp-1) -> m_addr = bp-> m_addr;
} while ((bp-1) -> m_size = bp-> m_size);
This is to allocate this space out.
This program, I want to understand a little C language basis, but if you want to modify it, it is not easy. For this algorithm, it is almost unrelated. However, it plays such an important role in the entire system (UNIX6). I often think that if I write the program, what is it? !
Another process is Mfree, it is a bit trouble, let's talk about it next time; but now, can you analyze it?
Finally, what you want to prepare, let's modify the kernel of the operating system. Oh, the allocation algorithm is changed to the Best Fit, how should this program written?
