Welcome to my blog

Memory management

The functions include virtual address, address transformation, memory allocation and reclamation, memory expansion, memory sharing, and memory protection. Continuous allocation refers to the allocation of contiguous memory space to a user program. Continuous allocation has two modes: single continuous storage management and partition storage managementCopy the code

The way memory is allocated

Single continuous storage management

System area and user area. The application is loaded into the user area and can use the full space of the user area. Its characteristic is, the most simple, suitable for single user, single task operating system. CP/M and DOS 2.0 followed this approach. The biggest advantage of this approach is that it is easy to manage.Copy the code

Partition storage management

Partitioned storage management divides memory into equal or unequal partitions, with one partition occupied by the operating system and the rest used by applications, each occupying one or more partitions. Although partitioned storage management can support concurrency, it is difficult to share memory partitions.Copy the code

Fixed partition

Fixed partitioning is characterized by the partitioning of memory into several contiguous partitions of fixed size. Partition sizes can be equal: this approach is only appropriate for concurrent execution of multiple identical programs (dealing with multiple objects of the same type). Partition sizes can also vary:Copy the code

Dynamic partitioning

Partition allocation for dynamic partitioning is to find a free partition larger than or equal to the size required by the program. If it is larger than the required size, the partition is split into two partitions, one of which is the required size and marked "occupied", and the other is the remaining size and marked "idle". The order of partition allocation is usually from low memory to high memory. One of the problems with dynamic partition release is merging adjacent free partitions into one large free partition. First fit method (NRST-FIT) : according to the partition in the order of memory search from the beginning, find the first partition to meet the requirements for allocation. The allocation and release time performance of the algorithm is good, and the large free partition can be reserved at the high end of memory. However, with the continuous partition of low-end partitions, more small partitions will be generated, and the cost of searching time will increase each time allocation. Next adaptation method (cycle first adaptation algorithm next FIT) : according to the order of partition in memory, from the last partition allocation from the search (to the last {area to start from the beginning}, find the first partition to meet the requirements for allocation. The allocation and release time performance of the algorithm is good, so that the free partition is distributed more evenly, but the large free partition is not easy to retain. Best-fit: According to the order of partition in memory, search from the beginning to find the smallest size difference between the required free partition for allocation. Individually, the outer fragment is small; But on the whole, there will be more external fragmentation and the advantage is that large free partitions can be retained. Worst-fit: Search for the largest free partition in memory by partition order and allocate it. Basically do not leave small idle partition, not easy to form external fragments. However, because large free partitions are not reserved, it is difficult to meet the requirements of processes that need large memory.Copy the code

Partner system

Compromise between fixed partition and dynamic partition When you need to allocate a storage space of length N to a process, first compute an I value such that 2 ^ (i-1) < n ≤ 2 ^ I, and then look in the linked list of free partitions of size 2 ^ I. If found, the free partition is allocated to the process. Otherwise, it indicates that the free partition of length 2 ^ I is exhausted, and then look in the free partition list of size 2 ^ (I + 1). If there is a free partition of 2 ^ (I + 1), divide the free partition into two equal partitions. These two partitions are called a pair of partners. One partition is used for configuration and the other is added to the free partition list of size 2 ^ I. If the size of the free partition 2 ^ (I + 1) does not exist, search for the size of the free partition 2 ^ (I + 2). If the size of the free partition is found, split it twice: The first time, split it into two partitions of size 2^(I + 1), one for allocation, and one to be added to the free partition list of size 2^(I + 1); The second time, split the first free partition for allocation into two 2^ I partitions, one for allocation, and add the other to the free partition list of size 2^ I. If still not found, continue to look for a free partition of size 2 ^ (I + 3), and so on.Copy the code

Memory crunch (address shuffling)

Move the occupied partitions towards memory and merge the free partitions into one free partition.Copy the code

Covering technology

The goal of introducing overlay technology is to run larger programs in a smaller amount of available memory. This technique is commonly used in multiprogram systems in conjunction with partitioned storage management.Copy the code

Switching technology

Considerations Considerations Swap technology, when multiple programs are executing concurrently, can send a temporarily unavailable program (process) to considerations to get free memory space to load a new program (process), or one that is in the ready state while being saved in considerations. The unit of exchange is the address space of the entire process. Switching technology is often used in multi-program systems or small time-sharing systems because most of these systems are managed by partition storage. Used with partitioned storage management, it is also known as "swap" or "roll-in/roll-out." Suspends a process in memory, saves the entire process's address space into the swap area of external memory (swap out), and reads the address space of the blocked and ready process into memory and sends the process to the ready queue (swap in).Copy the code

Memory allocation

Page and section storage management

Address space: the source program after the compilation of the target program, it exists in the address range, which is called the address space. An address space is a collection of logical addresses. Storage space: a collection of physical units in main memory that store information. The numbers of these units are called physical addresses. Storage space is a collection of physical addresses. Based on the basic unit used for allocation, discrete allocation can be divided into the following three management modes: page storage management, segment storage management, and segment-page storage management. Segment-page storage management is a combination of the first two.Copy the code

Page storage management

The logical address space of the program is divided into fixed-size pages and the physical memory into page frames of the same size. When the program is loaded, any page can be put into any page box in memory, these page boxes do not need to be continuous, so as to achieve discrete allocation. This method requires the hardware support of CPU to realize the mapping between logical address and physical address. In the page storage management mode, the address structure is composed of two parts, the first part is the page number, and the second part is the page address W (displacement). There is no external fragment, and each internal fragment is no more than one page. It is convenient to change the size of the space occupied by the program (mainly refers to the increase of dynamically generated data with the program running, the required address space increases accordingly).Copy the code

Data structures for page management

In a pager system, the address given by the instruction is divided into two parts: the logical page number and the in-page address. Principle: The memory management unit (MMU) in the CPU obtains the physical page frame NUMBER based on the logical page number by querying the process page table. Then add the physical page frame number and the page address to form the physical page number. If the internal offset address is displayed by querying the process page table, the physical page number is obtained. Page number P=INT[A/L], page address W=A MOD L Physical address: Physical block number x page size + Page offset = 28683Copy the code

Segment storage management

A page is a fixed area of equal length in the physical space of main memory. The advantage of paging is that the page length is fixed, which makes the page table easy to construct, easy to manage, and free of external fragmentation. The disadvantage of paging is that the page length is independent of the logical size of the program. For example, at some point a subroutine may have one part in main memory and another part in secondary memory. This hampers programming independence and makes things difficult for switch-in and switch-out handling, storage protection, and storage sharing. Another method of dividing addressable storage is called segmentation. A segment is an area whose length can change dynamically according to the natural boundaries of a program. Typically, programmers divide different types of data such as subroutines, operands, and constants into different segments, and each program can have multiple segments of the same type. The address space of a job is divided into segments, each of which defines a set of logical information. Example program segment, data segment, etc. Each segment is addressed from 0 and takes a contiguous address space. The length of the segment is determined by the length of the corresponding logical information group, so the length of the segment is not equal. The address space of the entire job is two-dimensional. Each program sets a segment table. Each entry in the segment table corresponds to a segment, and each entry contains at least three fields: the valid bit (indicating whether the segment has been called into main memory), the segment address (the initial address of the segment in real memory), and the segment length (recording the actual length of the segment). Absolute address = Find the start address in the segment table according to the segment number + the segment address (if the segment address exceeds the upper limit, the program interrupt event "Address out of bounds" will be generated to achieve storage protection)Copy the code

The title

We know that the logical space address is 2^m bytes (that is, the length of the logical address is m bits), and we know that the page size is 2^n bytes. So we could have 2 to the m minus n pages. So the page number portion will take up m-N bits, and then n bits, to store the page offset. For example, if the page size is 4B and the logical memory is 32B (8 pages), the page number of logical address 0 is 0, and page number 0 corresponds to frame 5, so the logical address is mapped to the physical address 5*4+0=20. Logical address 3 maps physical address 5 x 4+3=23. Logical address 13(4*3+1, page number 3, offset 1 because frame number 5) is mapped to physical address 21. 13/4 = 3 13 mod 4 = 1 5 * 4 + 1 = 21 Page logical addresses are continuous, segment logical addresses can be discontinuous page addresses are one-dimensional, segment addresses are two-dimensional paging is done by the operating system, segment is user-determined segment page management, The address image table is a segment table per process and a page table per segmentCopy the code