Memory management

Non-free memory management

knowledge

Address space

An address space is a set of addresses that a process can use to address memory.

Each process has its own address space, but some processes may want to share the address space.

Base address register and address change register

When base-address registers and indexed registers are used, the program is loaded to successive locations in memory and no relocation is required during loading. When a process runs, the starting physical address of the program is loaded into the base address register, and the length of the program is loaded into the indexing register.

Base address register: The starting location of data storage memory

Indexing register: Stores the length of an application

What are the steps required to make a user source program executable in memory?
  • Compilation (the compiler compiles the source program to form the target module),
  • Linking (linking compiled modules and library functions by the linker),
  • Load (Memory is loaded by a loader
The way a program is loaded
  • Absolute load: given the absolute address, the loading module can be directly loaded into the specified memory, its logical address and the actual memory address is exactly the same, without address transformation. Only suitable for single-channel application environment.
  • Relocatable loading mode: the logical address is different from the actual address during loading, so the logical address needs to be changed. The address transformation is completed once during loading and will not be changed later.
  • Dynamic loading: after the module is loaded into the memory, the logical address in the module is not immediately converted into physical address, and the conversion is delayed until the program runs. The loading address is the logical address, which needs the support of the relocation register.
Relocation, static relocation, dynamic relocation
  • Relocation: Load-time modification of instruction and data addresses in a target program
  • Static relocation: address change is done once at load time and is not changed afterwards
  • Dynamic relocation: Postponing address translation until the program is actually running
What are the continuous allocation methods of memory?
  • Single contiguous allocation: The entire user space of memory is exclusive to the program
  • Fixed partition allocation: The entire user space is divided into multiple regions of fixed size (partition sizes can be equal or unequal), and only one job is loaded into each region
  • Dynamic partition allocation: Memory space is dynamically allocated based on the actual needs of the process
  • Dynamically relocatable partition allocation: Memory space is allocated dynamically according to the actual needs of the process, and a program must be loaded into contiguous memory space
What are the dynamic partition allocation algorithms based on sequential search? What is the main idea of the algorithm?
  • FF, the first time adaptation algorithm, requires the chain of free partitions to be linked in increasing order of address, starting from the first address, until it finds a free partition with a satisfactory size
  • NF, cyclic first time algorithm, starts the search from the next free partition of the last found free partition until it finds a free partition of sufficient size
  • BF, the best adaptive algorithm, finds the minimum allocation of free partitions that meet the requirements. In order to speed up the search, the free partitions are required to be sorted according to increasing capacity
  • WF, the worst adaptive algorithm, finds the largest free partition allocation that meets the requirements. It requires the free partitions to be sorted in descending order of capacity, and only looks at whether the first partition meets the requirements
exchange
Definition:

The program that cannot run temporarily in memory is transferred to the swap area of the disk, and the program that can run on the disk is transferred to the memory

Commutation type:

Overall swap (process swap), with the process as the unit, the system needs to support functional swap space management, process swap in and process swap out

Page (segment) swap, which is called partial swap on a page or segment of a process to support virtual storage systems

Management of exchange space

The file area is used to store all kinds of files, and the swap area is used to store the process swapped out from the process

  • The target
    • The goal of the file area – to improve the utilization of file storage space, and then to improve the speed of file access
    • The goal of swap space management is to improve the speed at which processes can swap in and out, and then file storage utilization
  • The data structure
    • A chain of free partitions, each table containing the first address and size of the swap area, represented by the block number and number of blocks, respectively

Basic page management principle, address transformation process
Principle 1.
  • Divide the address space of a user program into fixed-size areas called pages or pages
  • In-page fragmentation: Unusable fragmentation that occurs when a process’s pages are not filled
  • The page size ranges from 1KB to 8KB
  • Address structure: page number P+ displacement W(i.e. page address), P can calculate the number of pages in the address space, W can calculate the size of each page
    • (P=INT[ \frac{A}{L}]),(d=[A] MOD L)
    • P is the page number, L is the page size, D is the in-page address, and A is the logical address
  • Page table: in the paging system, each page of a process is allowed to be stored discretely in any physical block of memory. For each process, a page image table, referred to as the page table, is established to achieve the address mapping from the page number to the physical block number
2. Address switching mechanism

Realize the transformation from logical address to physical address, with the help of page table to complete

  • Basic address change mechanism
    • Set only one Page Table Register (PTR, page-table Register) to store the start address and length of the Page Table in memory
    • When accessing data, the effective address (relative address) is divided into page number and in-page address, and the page table is retrieved by the page number. The comparison between the previous page number and the page table length is retrieved to prevent the address from crossing the boundary. If no, the start address of the page table is converted to the position of the entry in the page table to obtain the physical block number and load it into the physical address register. At the same time, the in-page address is entered into the in-block address field of the physical address register.
    • Page table In memory, the CPU accesses a data twice. The first time, the CPU accesses the page table in memory, finds the physical block number of the corresponding page, and splices the block number with the offset of the page to form a physical address. The second access is to get (or write to) the required data from the first address
  • Address changing mechanism with fast table
    • To increase access speed, set Associative Memory, also known as fast table, to store the currently accessed page entries. This allows the physical block number corresponding to the page to be read directly from the fast table. If the fast table is full, the OS must find page table entries that are no longer needed and swap them out.
3. Memory access validity period

The total time of retrieving data from the process to find the corresponding physical unit in memory after the address transformation.

Any system with paging faces two main problems:

  • The mapping between virtual addresses and physical addresses must be fast
  • If the virtual address space is large enough, then the page table is large enough
Accelerated paging mechanism

Large memory page table

Multistage page table

The basic principle of segmental system, address transformation process
1. The reason for introducing the segment-storage management mode

It mainly meets the following requirements of users and programmers:

[1], easy to program

Users divide their jobs into logically managed segments, each addressed from 0 and with its own name and length. Therefore, the logical address you want to access is determined by the segment name (segment number) and the in-segment offset (in-segment address).

[2] Information sharing

When realizing the sharing of programs and data, it is based on the logical unit of information. Pages in the paging system are only physical units (blocks) of information and have no complete meaning, while segments are logical units of information. In order to realize segment sharing, it is hoped that storage management can adapt to the organization mode of user program segment.

[3] Information protection

[4] Dynamic growth

Some segments grow with the use of the program. And there’s no way to know in advance exactly how big the data segment will grow.

[5] Dynamic linking

Dynamic linking means that several target segments are not linked together before the job runs. To run, the main program corresponding to the target program into memory and start running, when there is a need to call a section in the process of running, the section will be called into memory and linked. Visible dynamic linking also requires segments as a unit of management.

2. Basic principle of segmented system

Segment number + intra-segment address

The segment number can be used to calculate the maximum number of segments in a job, and the segment address can be used to calculate the maximum length of each segment

In segmented storage management, the address space of a job is divided into segments, each of which defines a set of logical information

3. The segment table

Set up a segment mapping table for each process in the system, referred to as “segment table”. Each segment holds one entry in the table. The start address (base address) and length of the segment are recorded. Segment tables can be stored in a set of registers to improve access speed, but it is more common to put segment tables in memory.

After the segment table is configured, the executing process can find the memory area corresponding to each segment by looking up the segment table.

Segment tables are used to map logical segments to physical memory areas.

4. Address switching mechanism

In order to realize the transformation function from logical address to physical address, a segment table register is set up in the system, which is used to store the segment table start address and segment table length TL. During address transformation, the system compares the segment number S in the logical address with the segment table length TL. If S>TL, the segment number is too large. Access out of bounds, then generated out of bounds interrupt signal; If the threshold is not exceeded, the physical memory address to be accessed is obtained based on the start address of the segment table, the segment number of the segment and the internal address of the segment.

When the segment table is in memory, every time a data is accessed, it needs to be accessed twice. The solution is similar to the paging system. Set up an associated register to store the most recently used segment table entries.

The main difference between paging and segmentation

A) Page is the physical unit of information, while paging is a discrete allocation method to reduce the external oddment of memory and improve the utilization rate of memory; The segment is the logical unit of information, which contains a group of information with relatively complete meaning. The purpose of segment is to better meet the needs of users.

B) The size of a page is fixed and determined by the system. The logical address is divided into page number and in-page address by the system, which is realized by the hardware of the machine. Therefore, there can only be a page of one size in the system; The length of the segment is not fixed and depends on the program written by the user. It is usually divided by the compiler according to the nature of the information when compiling the source program.

C) Paging job address space is one-dimensional, paging is completely a system behavior, that is, a single linear address space, programmers only need to use a memory, can represent an address; The segment address space is two-dimensional. Segment is user behavior. When identifying an address, programmer should give both segment name and segment address.

Basic principles of segment-page storage management and address shuffling process
1. Fundamentals

The user program is segmented and paging within segments, giving each segment a segment name. In the segment-page system, the address structure is composed of three parts: the segment number, the page number within the segment and the address within the page.

2. Address change process

Configure a segment table register that stores the segment table start address and segment table length TL. Compare whether the segment number and TL are out of bounds, obtain the start address of the segment table from the register of the segment table, find the corresponding page table according to the start address of the page table in the segment table, and find the physical block in memory according to the storage block of the page table to obtain the physical address.

3. Number of visits

In a segmented system, memory is accessed three times in order to obtain a single instruction or data:

① Access the segment table in memory to obtain the start address of the page table

② Access the page table in memory, extract the physical block number of the page, and form a physical address with the page address

Access to actually retrieve instructions or data from the address obtained by the second access

Multiple access to memory, execution speed is reduced, so a buffer register is added in the address shuffling mechanism. Each time it is accessed, it must use the segment number and page number to retrieve the cache. If the matching entry is found, the physical block number of the corresponding page can be obtained from it, which is used to form the physical address with the address in the page. If no matching entry is found, the memory needs to be accessed again.

Free memory management

How to monitor memory

  • Bitmap
  • Free Lists

Storage management using bitmaps

Storage management using linked lists

Virtual memory management

Locality principle

concept

A local rule in the execution of a program, that is, the execution of the program is limited to one part and, accordingly, the storage it accesses is limited to one region within a short period of time.

performance

Spatial limitations: Addresses accessed by a program may be concentrated within a certain range over a period of time, typically in order of execution

Time limitation: an instruction (data) in a program is executed (access) and may be executed again (access) shortly thereafter. This is typically caused by a large number of loops in the program.

Definition and characteristics of virtual memory

define

Virtual memory refers to a memory system that has the function of call in and replace, and can expand the memory capacity logically.

Characteristics of the
1. Many times

Programs are allowed to be loaded into memory multiple times

2. The exchange

Allows code and data that is not currently in use to be moved from memory to the swap area of external memory

3. The virtual sex

The memory capacity can be logically expanded so that the memory capacity seen by the user is much larger than the actual memory capacity

Principle and hardware of request paging storage management

The principle of

On the basis of the paging system, the page virtual storage system formed by the request paging function and page replacement function is added, allowing the user program to load only a few pages of the program and data can start running, through the above functions will be running pages into memory, while temporarily not running pages out of the external storage.

Hardware support
1. Page table mechanism for paging requests

A data structure formed by additional fields added to a purely paged page-table mechanism to translate logical addresses into physical addresses

2. Missing page interrupt mechanism

A page-missing interrupt occurs whenever a page needed by a user program is no longer in memory

3. Address switching mechanism

Page replacement algorithm (Opt, FIFO, LRU), missing page rate calculation

1 – Optimal algorithm

The pages selected for obsolescence are those that will never be used again, or that will not be accessed for the maximum (future) time

2-FIFO

Always weed out the page that enters memory first, that is, the page that stays in memory the longest

3-LRU

Select the most recently unused page for elimination

0. Hardware support

The LRU needs to configure a shift register for each page in memory to record the use of the process on each page in memory

The LRU also requires a special stack to hold the page numbers of the individual pages currently in use

Principle and hardware of request segmented storage management

The principle of

In a request segmentation system, only a few segments (not all segments) need to be called before the program can run. When the accessed segment is not in memory, you can request the OS to call the missing segment into memory.

Hardware support
1. Request segment table mechanism

The primary data structure required for segmented request management is the request segment table

2. Missing section interrupt mechanism

Whenever a program is found to be accessing a broken memory, a missing segment interrupt mechanism generates an interrupt signal, and the OS calls the required segment into memory. Interrupts are generated and processed during the execution of an instruction. Multiple interrupts may occur, but it is not possible for an instruction to be split in two segments.

3. Address switching mechanism

Address shuffling is required when the accessed segment is no longer in memory. The specific approach is to first call the missing segment into memory, and modify the segment table, and then use the segment table for address transformation.

Section sharing and protection

The Shared segment table

Record the segment number, segment length, memory start address, state (exists bits), external village start address, shared process count (count)

Allocation and reclamation of shared segments
1. Allocate shared segments

When the first process that uses the shared segment makes a request, the system allocates a physical area for the shared segment, calls in the shared segment, modifies the corresponding segment table (the memory address of the segment) and the shared segment table, and sets count to 1. When other processes need to invoke this segment, you only need to modify the corresponding segment table and the shared segment table, and then run count :=count+1.

2. Recycle the shared segment

If a process that shares a shared segment does not use the segment any more, modify the segment table and the shared segment table and run count :=count-1. If the last process that shares this segment does not need this segment any more, the system reclaims the physical area of this shared segment and modifies the shared segment table (deleting this entry).

Protection of segmented management
1. IP address violation protection

First, the segment table length in the segment table register is compared with the segment number in the logical address. If the segment number exceeds the bounds, an out-of-bounds interrupt will be generated.

Then the segment length in the segment table is compared with the in-segment displacement in the logical address. If the in-segment displacement is larger than the segment length, the out-of-bounds interrupt will also occur.

Note: In a system where segment dynamic growth is allowed, the allowable intra-segment displacement is greater than the segment length.

Access control protection (Access control protection)

Sets an access control field in the segment table that specifies how the segment is accessed.

3. Environmental protection mechanism

The ring protection mechanism is a kind of perfect protection mechanism. In this mechanism, low-numbered rings are given higher priority.

OS core is in the 0 ring; Some important utilities and operating system services occupy the middle ring; Normal applications are arranged on the outer ring.

In a ring system, program access and invocation should follow certain rules:

  • A program can access data in same-ring or lower-privileged ring
  • A program can call services in a same-ring or higher-privileged ring

Cause of jitter

Running process in the system too much at the same time, the assigned to each process of physical block is too little, can’t satisfy the basic requirement of the normal operation of process, make each process at run time, the frequent lack of pages, must ask paging system, which makes the process used in most of the time page replacement, processor efficiency declined sharply.